ed25519_exts_ref.py 7.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234
  1. #!/usr/bin/python
  2. # Copyright 2014-2015, The Tor Project, Inc
  3. # See LICENSE for licensing information
  4. """
  5. Reference implementations for the ed25519 tweaks that Tor uses.
  6. Includes self-tester and test vector generator.
  7. """
  8. import slow_ed25519
  9. from slow_ed25519 import *
  10. import os
  11. import random
  12. import slownacl_curve25519
  13. import unittest
  14. import binascii
  15. import textwrap
  16. #define a synonym that doesn't look like 1
  17. ell = l
  18. # This replaces expmod above and makes it go a lot faster.
  19. slow_ed25519.expmod = pow
  20. def curve25519ToEd25519(c, sign):
  21. u = decodeint(c)
  22. y = ((u - 1) * inv(u + 1)) % q
  23. x = xrecover(y)
  24. if x & 1 != sign: x = q-x
  25. return encodepoint([x,y])
  26. def blindESK(esk, param):
  27. h = H("Derive temporary signing key" + param)
  28. mult = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2))
  29. s = decodeint(esk[:32])
  30. s_prime = (s * mult) % ell
  31. k = esk[32:]
  32. assert(len(k) == 32)
  33. k_prime = H("Derive temporary signing key hash input" + k)[:32]
  34. return encodeint(s_prime) + k_prime
  35. def blindPK(pk, param):
  36. h = H("Derive temporary signing key" + param)
  37. mult = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2))
  38. P = decodepoint(pk)
  39. return encodepoint(scalarmult(P, mult))
  40. def 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 = ''.join([h[i] for i in range(b/8,b/4)])
  44. assert len(k) == 32
  45. return encodeint(a)+k
  46. def publickeyFromESK(h):
  47. a = decodeint(h[:32])
  48. A = scalarmult(B,a)
  49. return encodepoint(A)
  50. def signatureWithESK(m,h,pk):
  51. a = decodeint(h[:32])
  52. r = Hint(''.join([h[i] for i in range(b/8,b/4)]) + m)
  53. R = scalarmult(B,r)
  54. S = (r + Hint(encodepoint(R) + pk + m) * a) % l
  55. return encodepoint(R) + encodeint(S)
  56. def newSK():
  57. return os.urandom(32)
  58. # ------------------------------------------------------------
  59. MSG = "This is extremely silly. But it is also incredibly serious business!"
  60. class SelfTest(unittest.TestCase):
  61. def _testSignatures(self, esk, pk):
  62. sig = signatureWithESK(MSG, esk, pk)
  63. checkvalid(sig, MSG, pk)
  64. bad = False
  65. try:
  66. checkvalid(sig, MSG*2, pk)
  67. bad = True
  68. except Exception:
  69. pass
  70. self.failIf(bad)
  71. def testExpand(self):
  72. sk = newSK()
  73. pk = publickey(sk)
  74. esk = expandSK(sk)
  75. sig1 = signature(MSG, sk, pk)
  76. sig2 = signatureWithESK(MSG, esk, pk)
  77. self.assertEquals(sig1, sig2)
  78. def testSignatures(self):
  79. sk = newSK()
  80. esk = expandSK(sk)
  81. pk = publickeyFromESK(esk)
  82. pk2 = publickey(sk)
  83. self.assertEquals(pk, pk2)
  84. self._testSignatures(esk, pk)
  85. def testDerivation(self):
  86. priv = slownacl_curve25519.Private()
  87. pub = priv.get_public()
  88. ed_pub0 = publickeyFromESK(priv.private)
  89. sign = (ord(ed_pub0[31]) & 255) >> 7
  90. ed_pub1 = curve25519ToEd25519(pub.public, sign)
  91. self.assertEquals(ed_pub0, ed_pub1)
  92. def testBlinding(self):
  93. sk = newSK()
  94. esk = expandSK(sk)
  95. pk = publickeyFromESK(esk)
  96. param = os.urandom(32)
  97. besk = blindESK(esk, param)
  98. bpk = blindPK(pk, param)
  99. bpk2 = publickeyFromESK(besk)
  100. self.assertEquals(bpk, bpk2)
  101. self._testSignatures(besk, bpk)
  102. # ------------------------------------------------------------
  103. # From pprint.pprint([ binascii.b2a_hex(os.urandom(32)) for _ in xrange(8) ])
  104. RAND_INPUTS = [
  105. '26c76712d89d906e6672dafa614c42e5cb1caac8c6568e4d2493087db51f0d36',
  106. 'fba7a5366b5cb98c2667a18783f5cf8f4f8d1a2ce939ad22a6e685edde85128d',
  107. '67e3aa7a14fac8445d15e45e38a523481a69ae35513c9e4143eb1c2196729a0e',
  108. 'd51385942033a76dc17f089a59e6a5a7fe80d9c526ae8ddd8c3a506b99d3d0a6',
  109. '5c8eac469bb3f1b85bc7cd893f52dc42a9ab66f1b02b5ce6a68e9b175d3bb433',
  110. 'eda433d483059b6d1ff8b7cfbd0fe406bfb23722c8f3c8252629284573b61b86',
  111. '4377c40431c30883c5fbd9bc92ae48d1ed8a47b81d13806beac5351739b5533d',
  112. 'c6bbcce615839756aed2cc78b1de13884dd3618f48367a17597a16c1cd7a290b']
  113. # From pprint.pprint([ binascii.b2a_hex(os.urandom(32)) for _ in xrange(8) ])
  114. BLINDING_PARAMS = [
  115. '54a513898b471d1d448a2f3c55c1de2c0ef718c447b04497eeb999ed32027823',
  116. '831e9b5325b5d31b7ae6197e9c7a7baf2ec361e08248bce055908971047a2347',
  117. 'ac78a1d46faf3bfbbdc5af5f053dc6dc9023ed78236bec1760dadfd0b2603760',
  118. 'f9c84dc0ac31571507993df94da1b3d28684a12ad14e67d0a068aba5c53019fc',
  119. 'b1fe79d1dec9bc108df69f6612c72812755751f21ecc5af99663b30be8b9081f',
  120. '81f1512b63ab5fb5c1711a4ec83d379c420574aedffa8c3368e1c3989a3a0084',
  121. '97f45142597c473a4b0e9a12d64561133ad9e1155fe5a9807fe6af8a93557818',
  122. '3f44f6a5a92cde816635dfc12ade70539871078d2ff097278be2a555c9859cd0']
  123. PREFIX = "ED25519_"
  124. def writeArray(name, array):
  125. print "static const char *{prefix}{name}[] = {{".format(
  126. prefix=PREFIX,name=name)
  127. for a in array:
  128. h = binascii.b2a_hex(a)
  129. if len(h) > 70:
  130. h1 = h[:70]
  131. h2 = h[70:]
  132. print ' "{0}"\n "{1}",'.format(h1,h2)
  133. else:
  134. print ' "{0}",'.format(h)
  135. print "};\n"
  136. def comment(text, initial="/**"):
  137. print initial
  138. print textwrap.fill(text,initial_indent=" * ",subsequent_indent=" * ")
  139. print " */"
  140. def makeTestVectors():
  141. comment("""Test vectors for our ed25519 implementation and related
  142. functions. These were automatically generated by the
  143. ed25519_exts_ref.py script.""", initial="/*")
  144. comment("""Secret key seeds used as inputs for the ed25519 test vectors.
  145. Randomly generated. """)
  146. secretKeys = [ binascii.a2b_hex(r) for r in RAND_INPUTS ]
  147. writeArray("SECRET_KEYS", secretKeys)
  148. comment("""Secret ed25519 keys after expansion from seeds. This is how Tor
  149. represents them internally.""")
  150. expandedSecretKeys = [ expandSK(sk) for sk in secretKeys ]
  151. writeArray("EXPANDED_SECRET_KEYS", expandedSecretKeys)
  152. comment("""Public keys derived from the above secret keys""")
  153. publicKeys = [ publickey(sk) for sk in secretKeys ]
  154. writeArray("PUBLIC_KEYS", publicKeys)
  155. comment("""The curve25519 public keys from which the ed25519 keys can be
  156. derived. Used to test our 'derive ed25519 from curve25519'
  157. code.""")
  158. writeArray("CURVE25519_PUBLIC_KEYS",
  159. (slownacl_curve25519.smult_curve25519_base(sk[:32])
  160. for sk in expandedSecretKeys))
  161. comment("""Parameters used for key blinding tests. Randomly generated.""")
  162. blindingParams = [ binascii.a2b_hex(r) for r in BLINDING_PARAMS ]
  163. writeArray("BLINDING_PARAMS", blindingParams)
  164. comment("""Blinded secret keys for testing key blinding. The nth blinded
  165. key corresponds to the nth secret key blidned with the nth
  166. blinding parameter.""")
  167. writeArray("BLINDED_SECRET_KEYS",
  168. (blindESK(expandSK(sk), bp)
  169. for sk,bp in zip(secretKeys,blindingParams)))
  170. comment("""Blinded public keys for testing key blinding. The nth blinded
  171. key corresponds to the nth public key blidned with the nth
  172. blinding parameter.""")
  173. writeArray("BLINDED_PUBLIC_KEYS",
  174. (blindPK(pk, bp) for pk,bp in zip(publicKeys,blindingParams)))
  175. comment("""Signatures of the public keys, made with their corresponding
  176. secret keys.""")
  177. writeArray("SELF_SIGNATURES",
  178. (signature(pk, sk, pk) for pk,sk in zip(publicKeys,secretKeys)))
  179. if __name__ == '__main__':
  180. import sys
  181. if len(sys.argv) == 1 or sys.argv[1] not in ("SelfTest", "MakeVectors"):
  182. print "You should specify one of 'SelfTest' or 'MakeVectors'"
  183. sys.exit(1)
  184. if sys.argv[1] == 'SelfTest':
  185. unittest.main()
  186. else:
  187. makeTestVectors()