ed25519_exts_ref.py (9291B)
1 #!/usr/bin/python 2 # Copyright 2014-2019, The Tor Project, Inc 3 # See LICENSE for licensing information 4 5 """ 6 Reference implementations for the ed25519 tweaks that Tor uses. 7 8 Includes self-tester and test vector generator. 9 """ 10 11 # Future imports for Python 2.7, mandatory in 3.0 12 from __future__ import division 13 from __future__ import print_function 14 from __future__ import unicode_literals 15 16 import slow_ed25519 17 from slow_ed25519 import * 18 19 import os 20 import random 21 import slownacl_curve25519 22 import unittest 23 import binascii 24 import textwrap 25 26 #define a synonym that doesn't look like 1 27 ell = l 28 29 # This replaces expmod above and makes it go a lot faster. 30 slow_ed25519.expmod = pow 31 32 def curve25519ToEd25519(c, sign): 33 u = decodeint(c) 34 y = ((u - 1) * inv(u + 1)) % q 35 x = xrecover(y) 36 if x & 1 != sign: x = q-x 37 return encodepoint([x,y]) 38 39 def blindESK(esk, param): 40 mult = 2**(b-2) + sum(2**i * bit(param,i) for i in range(3,b-2)) 41 s = decodeint(esk[:32]) 42 s_prime = (s * mult) % ell 43 k = esk[32:] 44 assert(len(k) == 32) 45 k_prime = H(b"Derive temporary signing key hash input" + k)[:32] 46 return encodeint(s_prime) + k_prime 47 48 def blindPK(pk, param): 49 mult = 2**(b-2) + sum(2**i * bit(param,i) for i in range(3,b-2)) 50 P = decodepoint(pk) 51 return encodepoint(scalarmult(P, mult)) 52 53 def expandSK(sk): 54 h = H(sk) 55 a = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2)) 56 k = bytes(h[i] for i in range(b//8,b//4)) 57 assert len(k) == 32 58 return encodeint(a)+k 59 60 def publickeyFromESK(h): 61 a = decodeint(h[:32]) 62 A = scalarmult(B,a) 63 return encodepoint(A) 64 65 def signatureWithESK(m,h,pk): 66 a = decodeint(h[:32]) 67 r = Hint(bytes([h[i] for i in range(b//8,b//4)]) + m) 68 R = scalarmult(B,r) 69 S = (r + Hint(encodepoint(R) + pk + m) * a) % l 70 return encodepoint(R) + encodeint(S) 71 72 def newSK(): 73 return os.urandom(32) 74 75 def random_scalar(entropy_f): # 0..L-1 inclusive 76 # reduce the bias to a safe level by generating 256 extra bits 77 oversized = int(binascii.hexlify(entropy_f(32+32)), 16) 78 return oversized % ell 79 80 # ------------------------------------------------------------ 81 82 MSG = "This is extremely silly. But it is also incredibly serious business!" 83 84 class SelfTest(unittest.TestCase): 85 86 def _testSignatures(self, esk, pk): 87 sig = signatureWithESK(MSG, esk, pk) 88 checkvalid(sig, MSG, pk) 89 bad = False 90 try: 91 checkvalid(sig, MSG*2, pk) 92 bad = True 93 except Exception: 94 pass 95 96 self.failIf(bad) 97 98 def testExpand(self): 99 sk = newSK() 100 pk = publickey(sk) 101 esk = expandSK(sk) 102 sig1 = signature(MSG, sk, pk) 103 sig2 = signatureWithESK(MSG, esk, pk) 104 self.assertEquals(sig1, sig2) 105 106 def testSignatures(self): 107 sk = newSK() 108 esk = expandSK(sk) 109 pk = publickeyFromESK(esk) 110 pk2 = publickey(sk) 111 self.assertEquals(pk, pk2) 112 113 self._testSignatures(esk, pk) 114 115 def testDerivation(self): 116 priv = slownacl_curve25519.Private() 117 pub = priv.get_public() 118 119 ed_pub0 = publickeyFromESK(priv.private) 120 sign = (ord(ed_pub0[31]) & 255) >> 7 121 ed_pub1 = curve25519ToEd25519(pub.public, sign) 122 123 self.assertEquals(ed_pub0, ed_pub1) 124 125 def testBlinding(self): 126 sk = newSK() 127 esk = expandSK(sk) 128 pk = publickeyFromESK(esk) 129 param = os.urandom(32) 130 besk = blindESK(esk, param) 131 bpk = blindPK(pk, param) 132 bpk2 = publickeyFromESK(besk) 133 self.assertEquals(bpk, bpk2) 134 135 self._testSignatures(besk, bpk) 136 137 def testIdentity(self): 138 # Base point: 139 # B is the unique point (x, 4/5) \in E for which x is positive 140 By = 4 * inv(5) 141 Bx = xrecover(By) 142 B = [Bx % q,By % q] 143 144 # Get identity E by doing: E = l*B, where l is the group order 145 identity = scalarmult(B, ell) 146 147 # Get identity E by doing: E = l*A, where A is a random point 148 sk = newSK() 149 pk = decodepoint(publickey(sk)) 150 identity2 = scalarmult(pk, ell) 151 152 # Check that identities match 153 assert(identity == identity2) 154 # Check that identity is the point (0,1) 155 assert(identity == [0,1]) 156 157 # Check identity element: a*E = E, where a is a random scalar 158 scalar = random_scalar(os.urandom) 159 result = scalarmult(identity, scalar) 160 assert(result == identity == identity2) 161 162 # ------------------------------------------------------------ 163 164 # From pprint.pprint([ binascii.b2a_hex(os.urandom(32)) for _ in xrange(8) ]) 165 RAND_INPUTS = [ 166 '26c76712d89d906e6672dafa614c42e5cb1caac8c6568e4d2493087db51f0d36', 167 'fba7a5366b5cb98c2667a18783f5cf8f4f8d1a2ce939ad22a6e685edde85128d', 168 '67e3aa7a14fac8445d15e45e38a523481a69ae35513c9e4143eb1c2196729a0e', 169 'd51385942033a76dc17f089a59e6a5a7fe80d9c526ae8ddd8c3a506b99d3d0a6', 170 '5c8eac469bb3f1b85bc7cd893f52dc42a9ab66f1b02b5ce6a68e9b175d3bb433', 171 'eda433d483059b6d1ff8b7cfbd0fe406bfb23722c8f3c8252629284573b61b86', 172 '4377c40431c30883c5fbd9bc92ae48d1ed8a47b81d13806beac5351739b5533d', 173 'c6bbcce615839756aed2cc78b1de13884dd3618f48367a17597a16c1cd7a290b', 174 'c6bbcce615839756aed2cc78b1de13884dd3618f48367a17597a16c1cd7a290b', 175 'c6bbcce615839756aed2cc78b1de13884dd3618f48367a17597a16c1cd7a290b'] 176 177 # From pprint.pprint([ binascii.b2a_hex(os.urandom(32)) for _ in xrange(8) ]) 178 BLINDING_PARAMS = [ 179 '54a513898b471d1d448a2f3c55c1de2c0ef718c447b04497eeb999ed32027823', 180 '831e9b5325b5d31b7ae6197e9c7a7baf2ec361e08248bce055908971047a2347', 181 'ac78a1d46faf3bfbbdc5af5f053dc6dc9023ed78236bec1760dadfd0b2603760', 182 'f9c84dc0ac31571507993df94da1b3d28684a12ad14e67d0a068aba5c53019fc', 183 'b1fe79d1dec9bc108df69f6612c72812755751f21ecc5af99663b30be8b9081f', 184 '81f1512b63ab5fb5c1711a4ec83d379c420574aedffa8c3368e1c3989a3a0084', 185 '97f45142597c473a4b0e9a12d64561133ad9e1155fe5a9807fe6af8a93557818', 186 '3f44f6a5a92cde816635dfc12ade70539871078d2ff097278be2a555c9859cd0', 187 '0000000000000000000000000000000000000000000000000000000000000000', 188 '1111111111111111111111111111111111111111111111111111111111111111'] 189 190 PREFIX = "ED25519_" 191 192 def writeArray(name, array): 193 print("static const char *{prefix}{name}[] = {{".format( 194 prefix=PREFIX,name=name)) 195 for a in array: 196 h = binascii.b2a_hex(a) 197 if len(h) > 70: 198 h1 = h[:70] 199 h2 = h[70:] 200 print(' "{0}"\n "{1}",'.format(h1.decode('utf-8'),h2.decode('utf-8'))) 201 else: 202 print(' "{0}",'.format(h.decode('utf-8'))) 203 print("};\n") 204 205 def comment(text, initial="/**"): 206 print(initial) 207 print(textwrap.fill(text,initial_indent=" * ",subsequent_indent=" * ")) 208 print(" */") 209 210 def makeTestVectors(): 211 comment("""Test vectors for our ed25519 implementation and related 212 functions. These were automatically generated by the 213 ed25519_exts_ref.py script.""", initial="/*") 214 215 216 comment("""Secret key seeds used as inputs for the ed25519 test vectors. 217 Randomly generated. """) 218 secretKeys = [ binascii.a2b_hex(r) for r in RAND_INPUTS ] 219 writeArray("SECRET_KEYS", secretKeys) 220 221 comment("""Secret ed25519 keys after expansion from seeds. This is how Tor 222 represents them internally.""") 223 expandedSecretKeys = [ expandSK(sk) for sk in secretKeys ] 224 writeArray("EXPANDED_SECRET_KEYS", expandedSecretKeys) 225 226 comment("""Public keys derived from the above secret keys""") 227 publicKeys = [ publickey(sk) for sk in secretKeys ] 228 writeArray("PUBLIC_KEYS", publicKeys) 229 230 comment("""The curve25519 public keys from which the ed25519 keys can be 231 derived. Used to test our 'derive ed25519 from curve25519' 232 code.""") 233 writeArray("CURVE25519_PUBLIC_KEYS", 234 (slownacl_curve25519.smult_curve25519_base(sk[:32]) 235 for sk in expandedSecretKeys)) 236 237 comment("""Parameters used for key blinding tests. Randomly generated.""") 238 blindingParams = [ binascii.a2b_hex(r) for r in BLINDING_PARAMS ] 239 writeArray("BLINDING_PARAMS", blindingParams) 240 241 comment("""Blinded secret keys for testing key blinding. The nth blinded 242 key corresponds to the nth secret key blidned with the nth 243 blinding parameter.""") 244 writeArray("BLINDED_SECRET_KEYS", 245 (blindESK(expandSK(sk), bp) 246 for sk,bp in zip(secretKeys,blindingParams))) 247 248 comment("""Blinded public keys for testing key blinding. The nth blinded 249 key corresponds to the nth public key blidned with the nth 250 blinding parameter.""") 251 writeArray("BLINDED_PUBLIC_KEYS", 252 (blindPK(pk, bp) for pk,bp in zip(publicKeys,blindingParams))) 253 254 comment("""Signatures of the public keys, made with their corresponding 255 secret keys.""") 256 writeArray("SELF_SIGNATURES", 257 (signature(pk, sk, pk) for pk,sk in zip(publicKeys,secretKeys))) 258 259 260 261 if __name__ == '__main__': 262 import sys 263 if len(sys.argv) == 1 or sys.argv[1] not in ("SelfTest", "MakeVectors"): 264 print("You should specify one of 'SelfTest' or 'MakeVectors'") 265 sys.exit(1) 266 if sys.argv[1] == 'SelfTest': 267 unittest.main() 268 else: 269 makeTestVectors()