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...
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")
|
Tags: cryptography