src/test/ed25519_exts_ref.py

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