Cryptography

Given a prime , we can form the finite field . Elliptic curve cryptography is based on elliptic curves over this field for a large prime (usually). It does this by exploiting the hardness of the Discrete Logarithm Problem in large abelian groups.

Abelian group structure

A complex elliptic curve gets an abelian group structure for free via transport of structure from its relation to the quotient of the complex plane by the associated lattice. For elliptic curves over finite fields, we don't have this liberty (as far as I'm aware), but we do still have an abelian group structure that is defined more concretely.

Given an elliptic curve , and points , we can form the line joining these points with some straightforward coordinate geometry:

An elliptic curve is an algebraic curve of degree 3, and the line we just constructed is an algebraic curve of degree 1. Bézout's theorem tells us this line intersects the elliptic curve at exactly 3 points. 2 of these points are known to us, they are and because we constructed it that way. Some random maths theorem tells us that the third point is either on the curve or is the distinguished point , call it . The result of is the point obtained by reflecting about the -axis.

This operation gives the structure of an abelian group. The interesting subgroup is the set of -rational points: where . This forms a subgroup because polynomial magic or something, and is denoted . Since is a finite field, must be a finite abelian group.

Cryptography parameters

For the purposes of cryptography, one needs to choose a generator point . This is usually chosen so that the order of is a prime number.

All calculations are now done in the subgroup generated by . The cofactor of is defined to be the index of the subgroup (the number of cosets), which by Lagrange's Theorem must be a positive integer. Usually one wants to be small, preferrably equal to 1.

ECDLP

Treating the abelian group as a -module we can compute for , multiples of the generator , which are also elements of . The Elliptic Curve Discrete Logarithm Problem (ECDLP) is the question of computing given and . Good elliptic curves have hard ECDLP, providing the security for whatever this is used for.