#!/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")
Diff to Previous Revision
--- revision 1 2015-09-21 12:55:10
+++ revision 2 2015-09-21 12:58:34
@@ -1,7 +1,7 @@
#!/usr/bin/env python3
"""
-this code is a cleaned version of http://ed25519.cr.yp.to/python/ed25519.py for 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
"""
@@ -49,7 +49,7 @@
return self.to_bytes(k)
def public_key(self, sk) :
- """ compute the public key out of the random one """
+ """ compute the public key from the secret one """
h = self.to_hash(sk)
a = self.as_key(h)
c = self.outer(self.B, a)
