src/test/ed25519_exts_ref.py

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