slownacl_curve25519.py 2.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117
  1. # This is the curve25519 implementation from Matthew Dempsky's "Slownacl"
  2. # library. It is in the public domain.
  3. #
  4. # It isn't constant-time. Don't use it except for testing.
  5. #
  6. # Nick got the slownacl source from:
  7. # https://github.com/mdempsky/dnscurve/tree/master/slownacl
  8. __all__ = ['smult_curve25519_base', 'smult_curve25519']
  9. import sys
  10. P = 2 ** 255 - 19
  11. A = 486662
  12. def expmod(b, e, m):
  13. if e == 0: return 1
  14. t = expmod(b, e // 2, m) ** 2 % m
  15. if e & 1: t = (t * b) % m
  16. return t
  17. def inv(x):
  18. return expmod(x, P - 2, P)
  19. # Addition and doubling formulas taken from Appendix D of "Curve25519:
  20. # new Diffie-Hellman speed records".
  21. def add(n,m,d):
  22. (xn,zn), (xm,zm), (xd,zd) = n, m, d
  23. x = 4 * (xm * xn - zm * zn) ** 2 * zd
  24. z = 4 * (xm * zn - zm * xn) ** 2 * xd
  25. return (x % P, z % P)
  26. def double(n):
  27. (xn,zn) = n
  28. x = (xn ** 2 - zn ** 2) ** 2
  29. z = 4 * xn * zn * (xn ** 2 + A * xn * zn + zn ** 2)
  30. return (x % P, z % P)
  31. def curve25519(n, base):
  32. one = (base,1)
  33. two = double(one)
  34. # f(m) evaluates to a tuple containing the mth multiple and the
  35. # (m+1)th multiple of base.
  36. def f(m):
  37. if m == 1: return (one, two)
  38. (pm, pm1) = f(m // 2)
  39. if (m & 1):
  40. return (add(pm, pm1, one), double(pm1))
  41. return (double(pm), add(pm, pm1, one))
  42. ((x,z), _) = f(n)
  43. return (x * inv(z)) % P
  44. if sys.version < '3':
  45. def b2i(c):
  46. return ord(c)
  47. def i2b(i):
  48. return chr(i)
  49. def ba2bs(ba):
  50. return "".join(ba)
  51. else:
  52. def b2i(c):
  53. return c
  54. def i2b(i):
  55. return i
  56. def ba2bs(ba):
  57. return bytes(ba)
  58. def unpack(s):
  59. if len(s) != 32: raise ValueError('Invalid Curve25519 argument')
  60. return sum(b2i(s[i]) << (8 * i) for i in range(32))
  61. def pack(n):
  62. return ba2bs([i2b((n >> (8 * i)) & 255) for i in range(32)])
  63. def clamp(n):
  64. n &= ~7
  65. n &= ~(128 << 8 * 31)
  66. n |= 64 << 8 * 31
  67. return n
  68. def smult_curve25519(n, p):
  69. n = clamp(unpack(n))
  70. p = unpack(p)
  71. return pack(curve25519(n, p))
  72. def smult_curve25519_base(n):
  73. n = clamp(unpack(n))
  74. return pack(curve25519(n, 9))
  75. #
  76. # This part I'm adding in for compatibility with the curve25519 python
  77. # module. -Nick
  78. #
  79. import os
  80. class Private:
  81. def __init__(self, secret=None, seed=None):
  82. self.private = pack(clamp(unpack(os.urandom(32))))
  83. def get_public(self):
  84. return Public(smult_curve25519_base(self.private))
  85. def get_shared_key(self, public, hashfn):
  86. return hashfn(smult_curve25519(self.private, public.public))
  87. def serialize(self):
  88. return self.private
  89. class Public:
  90. def __init__(self, public):
  91. self.public = public
  92. def serialize(self):
  93. return self.public