ed25519_exts_ref.py 8.6 KB

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