def clockadd(P1,P2): x1,y1 = P1 x2,y2 = P2 x3 = x1*y2+y1*x2 y3 = y1*y2-x1*x2 return x3,y3 def F(p): # caveat: caller must ensure that p is prime class F: def __init__(self,x): self.int = x % p def __str__(self): return str(self.int) __repr__ = __str__ def __eq__(a,b): return a.int == b.int def __ne__(a,b): return a.int != b.int def __add__(a,b): return F(a.int + b.int) def __sub__(a,b): return F(a.int - b.int) def __mul__(a,b): return F(a.int * b.int) def __div__(a,b): # caveat: caller must ensure that b is nonzero return a*F(pow(b.int,p-2,p)) return F def scalarmult(n,P): # caveat: caller must ensure that n is nonnegative # caveat: n is limited by python's recursion limit if n == 0: return (Fp(0),Fp(1)) if n == 1: return P Q = scalarmult(n//2,P) Q = clockadd(Q,Q) if n % 2: Q = clockadd(P,Q) return Q # examples: p = 1000003 Fp = F(p) P = (Fp(1000),Fp(2)) print scalarmult(6,P) # output: (780000, 1351) print scalarmult(1000004,P) # output: (0, 1) print scalarmult(123456789123456789123456789,P) # output: (541230, 236193) # toy example of clock DH: import random alicesecret = random.randrange(2**256) alicepublic = scalarmult(alicesecret,P) bobsecret = random.randrange(2**256) bobpublic = scalarmult(bobsecret,P) aliceshared = scalarmult(alicesecret,bobpublic) bobshared = scalarmult(bobsecret,alicepublic) print aliceshared == bobshared