Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1# ed25519.py - Optimized version of the reference implementation of Ed25519
2#
3# Written in 2011? by Daniel J. Bernstein <djb@cr.yp.to>
4# 2013 by Donald Stufft <donald@stufft.io>
5# 2013 by Alex Gaynor <alex.gaynor@gmail.com>
6# 2013 by Greg Price <price@mit.edu>
7#
8# To the extent possible under law, the author(s) have dedicated all copyright
9# and related and neighboring rights to this software to the public domain
10# worldwide. This software is distributed without any warranty.
11#
12# You should have received a copy of the CC0 Public Domain Dedication along
13# with this software. If not, see
14# <http://creativecommons.org/publicdomain/zero/1.0/>.
16"""
17NB: This code is not safe for use with secret keys or secret data.
18The only safe use of this code is for verifying signatures on public messages.
20Functions for computing the public key of a secret key and for signing
21a message are included, namely publickey_unsafe and signature_unsafe,
22for testing purposes only.
24The root of the problem is that Python's long-integer arithmetic is
25not designed for use in cryptography. Specifically, it may take more
26or less time to execute an operation depending on the values of the
27inputs, and its memory access patterns may also depend on the inputs.
28This opens it to timing and cache side-channel attacks which can
29disclose data to an attacker. We rely on Python's long-integer
30arithmetic, so we cannot handle secrets without risking their disclosure.
31"""
33import hashlib
36__version__ = "1.0.dev0"
39b = 256
40q = 2**255 - 19
41l = 2**252 + 27742317777372353535851937790883648493
44def H(m):
45 return hashlib.sha512(m).digest()
48def pow2(x, p):
49 """== pow(x, 2**p, q)"""
50 while p > 0:
51 x = x * x % q
52 p -= 1
53 return x
56def inv(z):
57 r"""$= z^{-1} \mod q$, for z != 0"""
58 # Adapted from curve25519_athlon.c in djb's Curve25519.
59 z2 = z * z % q # 2
60 z9 = pow2(z2, 2) * z % q # 9
61 z11 = z9 * z2 % q # 11
62 z2_5_0 = (z11 * z11) % q * z9 % q # 31 == 2^5 - 2^0
63 z2_10_0 = pow2(z2_5_0, 5) * z2_5_0 % q # 2^10 - 2^0
64 z2_20_0 = pow2(z2_10_0, 10) * z2_10_0 % q # ...
65 z2_40_0 = pow2(z2_20_0, 20) * z2_20_0 % q
66 z2_50_0 = pow2(z2_40_0, 10) * z2_10_0 % q
67 z2_100_0 = pow2(z2_50_0, 50) * z2_50_0 % q
68 z2_200_0 = pow2(z2_100_0, 100) * z2_100_0 % q
69 z2_250_0 = pow2(z2_200_0, 50) * z2_50_0 % q # 2^250 - 2^0
70 return pow2(z2_250_0, 5) * z11 % q # 2^255 - 2^5 + 11 = q - 2
73d = -121665 * inv(121666) % q
74I = pow(2, (q - 1) // 4, q)
77def xrecover(y):
78 xx = (y * y - 1) * inv(d * y * y + 1)
79 x = pow(xx, (q + 3) // 8, q)
81 if (x * x - xx) % q != 0:
82 x = (x * I) % q
84 if x % 2 != 0:
85 x = q - x
87 return x
90By = 4 * inv(5)
91Bx = xrecover(By)
92B = (Bx % q, By % q, 1, (Bx * By) % q)
93ident = (0, 1, 1, 0)
96def edwards_add(P, Q):
97 # This is formula sequence 'addition-add-2008-hwcd-3' from
98 # http://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html
99 (x1, y1, z1, t1) = P
100 (x2, y2, z2, t2) = Q
102 a = (y1 - x1) * (y2 - x2) % q
103 b = (y1 + x1) * (y2 + x2) % q
104 c = t1 * 2 * d * t2 % q
105 dd = z1 * 2 * z2 % q
106 e = b - a
107 f = dd - c
108 g = dd + c
109 h = b + a
110 x3 = e * f
111 y3 = g * h
112 t3 = e * h
113 z3 = f * g
115 return (x3 % q, y3 % q, z3 % q, t3 % q)
118def edwards_double(P):
119 # This is formula sequence 'dbl-2008-hwcd' from
120 # http://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html
121 (x1, y1, z1, t1) = P
123 a = x1 * x1 % q
124 b = y1 * y1 % q
125 c = 2 * z1 * z1 % q
126 # dd = -a
127 e = ((x1 + y1) * (x1 + y1) - a - b) % q
128 g = -a + b # dd + b
129 f = g - c
130 h = -a - b # dd - b
131 x3 = e * f
132 y3 = g * h
133 t3 = e * h
134 z3 = f * g
136 return (x3 % q, y3 % q, z3 % q, t3 % q)
139def scalarmult(P, e):
140 if e == 0:
141 return ident
142 Q = scalarmult(P, e // 2)
143 Q = edwards_double(Q)
144 if e & 1:
145 Q = edwards_add(Q, P)
146 return Q
149# Bpow[i] == scalarmult(B, 2**i)
150Bpow = []
153def make_Bpow():
154 P = B
155 for i in range(253):
156 Bpow.append(P)
157 P = edwards_double(P)
160make_Bpow()
163def scalarmult_B(e):
164 """
165 Implements scalarmult(B, e) more efficiently.
166 """
167 # scalarmult(B, l) is the identity
168 e = e % l
169 P = ident
170 for i in range(253):
171 if e & 1:
172 P = edwards_add(P, Bpow[i])
173 e = e // 2
174 assert e == 0, e
175 return P
178def encodeint(y):
179 bits = [(y >> i) & 1 for i in range(b)]
180 return bytes(
181 [sum([bits[i * 8 + j] << j for j in range(8)]) for i in range(b // 8)]
182 )
185def encodepoint(P):
186 (x, y, z, t) = P
187 zi = inv(z)
188 x = (x * zi) % q
189 y = (y * zi) % q
190 bits = [(y >> i) & 1 for i in range(b - 1)] + [x & 1]
191 return bytes(
192 [sum([bits[i * 8 + j] << j for j in range(8)]) for i in range(b // 8)]
193 )
196def bit(h, i):
197 return (h[i // 8] >> (i % 8)) & 1
200def publickey_unsafe(sk):
201 """
202 Not safe to use with secret keys or secret data.
204 See module docstring. This function should be used for testing only.
205 """
206 h = H(sk)
207 a = 2 ** (b - 2) + sum(2**i * bit(h, i) for i in range(3, b - 2))
208 A = scalarmult_B(a)
209 return encodepoint(A)
212def Hint(m):
213 h = H(m)
214 return sum(2**i * bit(h, i) for i in range(2 * b))
217def signature_unsafe(m, sk, pk):
218 """
219 Not safe to use with secret keys or secret data.
221 See module docstring. This function should be used for testing only.
222 """
223 h = H(sk)
224 a = 2 ** (b - 2) + sum(2**i * bit(h, i) for i in range(3, b - 2))
225 r = Hint(bytes([h[j] for j in range(b // 8, b // 4)]) + m)
226 R = scalarmult_B(r)
227 S = (r + Hint(encodepoint(R) + pk + m) * a) % l
228 return encodepoint(R) + encodeint(S)
231def isoncurve(P):
232 (x, y, z, t) = P
233 return (
234 z % q != 0
235 and x * y % q == z * t % q
236 and (y * y - x * x - z * z - d * t * t) % q == 0
237 )
240def decodeint(s):
241 return sum(2**i * bit(s, i) for i in range(0, b))
244def decodepoint(s):
245 y = sum(2**i * bit(s, i) for i in range(0, b - 1))
246 x = xrecover(y)
247 if x & 1 != bit(s, b - 1):
248 x = q - x
249 P = (x, y, 1, (x * y) % q)
250 if not isoncurve(P):
251 raise ValueError("decoding point that is not on curve")
252 return P
255class SignatureMismatch(Exception):
256 pass
259def checkvalid(s, m, pk):
260 """
261 Not safe to use when any argument is secret.
263 See module docstring. This function should be used only for
264 verifying public signatures of public messages.
265 """
266 if len(s) != b // 4:
267 raise ValueError("signature length is wrong")
269 if len(pk) != b // 8:
270 raise ValueError("public-key length is wrong")
272 R = decodepoint(s[: b // 8])
273 A = decodepoint(pk)
274 S = decodeint(s[b // 8 : b // 4])
275 h = Hint(encodepoint(R) + pk + m)
277 (x1, y1, z1, t1) = P = scalarmult_B(S)
278 (x2, y2, z2, t2) = Q = edwards_add(R, scalarmult(A, h))
280 if (
281 not isoncurve(P)
282 or not isoncurve(Q)
283 or (x1 * z2 - x2 * z1) % q != 0
284 or (y1 * z2 - y2 * z1) % q != 0
285 ):
286 raise SignatureMismatch("signature does not pass verification")