# ECCHacks

A gentle introduction
to elliptic-curve cryptography

 The clock: Real clock Clock addition
 Finiteness: Finite fields Finite clocks Clock crypto
 Elliptic curves: Edwards curves Edwards addition

## Finite fields

Reduction modulo 7 is the operation that reads an integer, divides the integer by 7 to produce a quotient and remainder, and outputs the remainder. Math people write "x mod 7" for the reduction of x modulo 7. Python people write "x % 7":

```     for n in range(0,20):
print n,n%7

# output: 0 0
# output: 1 1
# output: 2 2
# output: 3 3
# output: 4 4
# output: 5 5
# output: 6 6
# output: 7 0
# output: 8 1
# output: 9 2
# output: 10 3
# output: 11 4
# output: 12 5
# output: 13 6
# output: 14 0
# output: 15 1
# output: 16 2
# output: 17 3
# output: 18 4
# output: 19 5
```

The output is always in the set {0,1,2,3,4,5,6}. Warning: C also has an "x % 7", but most compilers produce a negative remainder if x is negative, and we don't want negative remainders; the same operation in C is "((x % 7) + 7) % 7".

## A finite field

F7 means the set {0,1,2,3,4,5,6} with the following overloaded arithmetic operations:

• +: Given two elements x,y of F7, output (x+y) mod 7. For example, given 2 and 5, output 0.
• -: Given two elements x,y of F7, output (x-y) mod 7. For example, given 2 and 5, output 4.
• *: Given two elements x,y of F7, output (x*y) mod 7. For example, given 2 and 5, output 3.

These operations, together with 0 and 1, satisfy all the equations that you expect: for example, x*(y-z) = x*y-x*z.

Here's how to define an "F7" type in Python with its own +,-,*, separate from the integer +,-,*. First let's define an initializer F7(x) converting an integer x into x mod 7, and some output functions:

```     class F7:
def __init__(self,x):
self.int = x % 7
def __str__(self):
return str(self.int)
__repr__ = __str__

# examples:
print F7(2)
# output: 2
print F7(6)
# output: 6
print F7(7)
# output: 0
print F7(10)
# output: 3
```

Now we can define +,-,* operations for this type:

```     F7.__add__ = lambda a,b: F7(a.int + b.int)
F7.__sub__ = lambda a,b: F7(a.int - b.int)
F7.__mul__ = lambda a,b: F7(a.int * b.int)

# examples:
print F7(2) + F7(5)
# output: 0
print F7(2) - F7(5)
# output: 4
print F7(2) * F7(5)
# output: 3
```

Let's also allow equality tests and inequality tests:

```     F7.__eq__ = lambda a,b: a.int==b.int
F7.__ne__ = lambda a,b: a.int!=b.int

# examples:
print F7(7) == F7(0)
# output: True
print F7(10) == F7(3)
# output: True
print F7(-3) == F7(4)
# output: True
print F7(0) != F7(1)
# output: True
print F7(0) != F7(2)
# output: True
print F7(1) != F7(2)
# output: True
print F7(7) != F7(0)
# output: False
print F7(10) != F7(3)
# output: False
print F7(-3) != F7(4)
# output: False
print F7(0) == F7(1)
# output: False
print F7(0) == F7(2)
# output: False
print F7(1) == F7(2)
# output: False
```

## Division, and the field concept

The equations 1*1=1, 2*4=1, 3*5=1, 6*6=1 in F7 show that 1, 2, 3, 4, 5, 6 have reciprocals in F7: 1/1 = 1, 1/2 = 4, 1/3 = 5, 1/4 = 2, 1/5 = 3, 1/6 = 6. 0 doesn't have a reciprocal: there's nothing you can multiply 0 by to obtain 1.

We don't say field, and don't use the F notation, unless the nonzero elements are exactly the elements with reciprocals. For example, the integers modulo 10 aren't a field (and there isn't an F10), since the set {1,2,3,4,5,6,7,8,9} of nonzero integers modulo 10 isn't the same as the set {1,3,7,9} of integers modulo 10 with reciprocals. As another (nitpicky) example, the integers modulo 1 aren't a field, since the set {} of nonzero integers modulo 1 isn't the same as the set {0} of integers modulo 1 with reciprocals.

## More finite fields

For every prime number p (2 or 3 or 5 or 7 or 11 or ...), Fp is the finite field of integers modulo p:

```     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
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

# examples:
F1009 = F(1009)
print F1009(-1) == F1009(1008)
# output: True
print F1009(6) != F1009(5)
# output: True
print F1009(101) + F1009(1000) == F1009(92)
# output: True
print F1009(101) - F1009(1000) == F1009(110)
# output: True
print F1009(101) * F1009(1000) == F1009(100)
# output: True
print F1009(101) / F1009(1000) == F1009(213)
# output: True
```

There are also "non-prime" finite fields (of sizes 4, 8, 9, 16, 25, 27, 32, ...), but we won't need those for ECCHacks.

The __div__ function above uses "Fermat's little theorem", which says that you can compute the reciprocal of any nonzero x in Fp by computing xp-2. There are other division methods, but the Fermat method is very simple to implement, and its performance is tolerable even when p is very large.

Version: This is version 2014.12.27 of the finitefield.html web page.