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