src/test/ed25519_exts_ref.py

   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()