|A gentle introduction
to elliptic-curve cryptography
The sum of n copies of a clock point P is written nP. Computing nP given n and P is called scalar multiplication; the integer input n is called the scalar.
Scalar multiplication is easy even if the scalar is very large, since you can jump from nP to 2nP with just a single addition:
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)
The clock Diffie–Hellman protocol uses scalar multiplication as follows:
The following example uses the clock modulo 1000003 (which is not safe for serious cryptography, most obviously because it is much too small) and the base point P=(1000,2) shown above:
# 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
Version: This is version 2014.12.27 of the clockcrypto.html web page.