ECCHacks

Finite clocks

[Python snippets]

As an alternative to the real clock one can use the integer clock: all pairs of integers (x,y) satisfying the equation x²+y²=1. The real clock has infinitely many points, while the integer clock has only four points: namely, (0,1), (1,0), (0,-1), and (-1,0); i.e., "12:00", "3:00", "6:00", and "9:00".

A larger example is the clock modulo 7. This clock consists of all pairs of integers modulo 7 satisfying this equation. The following Python script prints all points on the clock modulo 7:

     for x in range(7):
       for y in range(7):
         if (x*x+y*y) % 7 == 1:
           print (x,y)
     
     # output: (0, 1)
     # output: (0, 6)
     # output: (1, 0)
     # output: (2, 2)
     # output: (2, 5)
     # output: (5, 2)
     # output: (5, 5)
     # output: (6, 0)

We can use the original clockadd function to add points on this clock, after we've defined +,-,* for the field of integers modulo 7:

     P1 = (F7(2),F7(5))
     P2 = (F7(1),F7(0))
     print clockadd(P1,P2)
     # output: (5, 5)
     print clockadd(P2,P1)
     # output: (5, 5)
     P3 = (F7(5),F7(5))
     print clockadd(clockadd(P1,P2),P3)
     # output: (1, 0)
     print clockadd(P1,clockadd(P2,P3))
     # output: (1, 0)

The above script to print all clock points becomes much slower if you replace 7 by a larger prime, but clock addition remains fast:

     p = 1000003
     Fp = F(1000003)
     P = (Fp(1000),Fp(2))
     P2 = clockadd(P,P)
     print P2
     # output: (4000, 7)
     P3 = clockadd(P2,P)
     print P3
     # output: (15000, 26)
     P4 = clockadd(P3,P)
     P5 = clockadd(P4,P)
     P6 = clockadd(P5,P)
     print P6
     # output: (780000, 1351)
     print clockadd(P3,P3)
     # output: (780000, 1351)

There are faster ways to write down all points on a larger clock, but clock cryptography uses primes and clocks that are so large that there isn't even enough time in the universe to look at all the points, while clock addition remains fast.