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