Welcome, guest | Sign In | My Account | Store | Cart

This is a re-implementation of the ed25519 signature algorithm as proposed on this page : http://ed25519.cr.yp.to/python/ed25519.py.

Do not use for production, only for the eyes o_O

Code is tab indented, space indentation kills kitten...

Python, 154 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#!/usr/bin/env python3

"""
this code is a cleaned version of http://ed25519.cr.yp.to/python/ed25519.py for python3

code released under the terms of the GNU Public License v3, copyleft 2015 yoochan
"""

import collections
import hashlib
import os
import random

Point = collections.namedtuple('Point', ['x', 'y'])

key_mask = int.from_bytes(b'\x3F' + b'\xFF' * 30 + b'\xF8', 'big', signed=False)

class Ed25519() :
	
	length = 256

	def __init__(self) :
		self.q = 2**255 - 19
		self.l = 2**252 + 27742317777372353535851937790883648493
		self.d = -121665 * self.inverse(121666)
		
		self.i = pow(2, (self.q - 1)//4, self.q)
		
		self.B = self.point(4 * self.inverse(5))
		
	def to_hash(self, m) :
		return hashlib.sha512(m).digest()
		
	def from_bytes(self, h) :
		""" pick 32 bytes, return a 256 bit int """
		return int.from_bytes(h[0:self.length//8], 'little', signed=False)
		
	def to_bytes(self, k) :
		return k.to_bytes(self.length//8, 'little', signed=False)
		
	def as_key(self, h) :
		return 2**(self.length-2) + (self.from_bytes(h) & key_mask)
		
	def secret_key(self) :
		""" pick a random secret key """
		m = os.urandom(1024)
		h = self.to_hash(m)
		k = self.as_key(h)
		return self.to_bytes(k)
		
	def public_key(self, sk) :
		""" compute the public key from the secret one """
		h = self.to_hash(sk)
		a = self.as_key(h)
		c = self.outer(self.B, a)
		return self.point_to_bytes(c)
		
	def inverse(self, x) :
		return pow(x, self.q - 2, self.q)
		
	def sign(self, message, secret_key, public_key) :
		s_h = self.to_hash(secret_key)
		s_d = self.as_key(s_h)
		
		m_h = self.to_hash(s_h[self.length//8:self.length//4] + message)
		m_d = self.from_bytes(m_h)
		
		R = self.outer(self.B, m_d)
		
		r_h = self.to_hash(self.point_to_bytes(R) + public_key + message)
		r_d = m_d + self.from_bytes(r_h) * s_d
		
		return self.point_to_bytes(R) + self.to_bytes(r_d % self.l)
		
	def verify(self, message, signature, public_key) :
		r_b = signature[0:self.length//8]
		r_h = self.to_hash(r_b + public_key + message)
		r_d = self.from_bytes(r_h)
		
		s_d = self.from_bytes(signature[self.length//8:self.length//4])
		b_j = self.outer(self.B, s_d)
		
		P = self.bytes_to_point(public_key)
		p_j = self.outer(P, r_d)
		
		R = self.bytes_to_point(r_b)
		
		return b_j == self.inner(R, p_j)
		
	def recover(self, y) :
		""" given a value y, recover the preimage x """
		p = (y*y - 1) * self.inverse(self.d*y*y + 1)
		x = pow(p, (self.q + 3)//8, self.q)
		if (x*x - p) % self.q != 0:
			x = (x * self.i) % self.q
		if x % 2 != 0 :
			x = self.q - x
		return x
		
	def point(self, y) :
		""" given a value y, recover x and return the corresponding P(x, y) """
		return Point(self.recover(y) % self.q, y % self.q)
	
	def is_on_curve(self, P) :
		return (P.y*P.y - P.x*P.x - 1 - self.d*P.x*P.x*P.y*P.y) % self.q == 0
		
	def inner(self, P, Q) :
		""" inner product on the curve, between two points """
		x = (P.x*Q.y + Q.x*P.y) * self.inverse(1 + self.d*P.x*Q.x*P.y*Q.y)
		y = (P.y*Q.y + P.x*Q.x) * self.inverse(1 - self.d*P.x*Q.x*P.y*Q.y)
		return Point(x % self.q, y % self.q)
		
	def outer(self, P, n) :
		""" outer product on the curve, between a point and a scalar """
		if n == 0:
			return Point(0, 1)
		Q = self.outer(P, n//2)
		Q = self.inner(Q, Q)
		if n & 1:
			Q = self.inner(Q, P)
		return Q
		
	def point_to_bytes(self, P) :
		return (P.y + ((P.x & 1) << 255)).to_bytes(self.length//8, 'little')
		
	def bytes_to_point(self, b) :
		i = self.from_bytes(b)
		y = i % 2**(self.length - 1)
		x = self.recover(y)
		if (x & 1) != ((i >> (self.length-1)) & 1) :
			x = self.q - x
		return Point(x, y)

if __name__ == '__main__' :
	def hexit(s) :
		return ''.join("{0:02X}".format(i) for i in reversed(s))
		
	ecc = Ed25519()
	
	alice_sk = b'alicealicealicealicealicealiceal' # ecc.secret_key()
	alice_pk = ecc.public_key(alice_sk)
	
	assert(hexit(alice_pk) == 'AFA095BF733298216D0E88A0F2A4FEB15E5FEB73E7FA7522B67594FD2EF770D6')
	
	message = 'foo bar'.encode('utf8')
	signature = ecc.sign(message, alice_sk, alice_pk)
	
	import cProfile
	cProfile.run("ecc.sign(message, alice_sk, alice_pk)")
	
	assert(ecc.verify(message, signature, alice_pk))
	cProfile.run("ecc.verify(message, signature, alice_pk)")
	
	print("code test: OK")
	
Created by yota on Mon, 21 Sep 2015 (GPL3)
Python recipes (4591)
yota's recipes (13)

Required Modules

  • (none specified)

Other Information and Tasks

  • Licensed under the GPL 3
  • Viewed 8491 times
  • Revision 2 (updated 8 years ago)