ECCHacks

Clock cryptography

[Python snippets]

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:

• Alice generates a large integer as her secret key and multiplies this integer by a standard base point on a standard safe clock to obtain her public key.
• Bob generates a large integer as his secret key and multiplies this integer by the same standard base point to obtain his public key.
• Alice multiplies her secret key by Bob's public key to obtain a secret shared between Alice and Bob.
• Bob multiplies his secret key by Alice's public key to obtain the same secret.
• Alice and Bob then use the shared secret to authenticate and encrypt any number of messages.

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