The curve and point addition

After RSA, a second major family of public-key cryptography rose to prominence: elliptic curves, which offer the same security with far smaller keys. But first you need to understand the geometric object on which it is built.

A curve, an equation

An elliptic curve is the set of points (x, y) satisfying an equation of the form:

y^2 = x^3 + a*x + b

where a and b are fixed constants. By varying them, you obtain a whole family of curves. The only condition is that the curve be « smooth », with no sharp point or crossing — technically, 4*a^3 + 27*b^2 != 0.

Here is what such a curve looks like:

            y
            |     .-'''-.
            |    /       \
     -------+---+---------+------ x
            |    \       /
            |     '-...-'

Notice the symmetry about the x-axis: if (x, y) is on the curve, then (x, -y) is too, since y^2 and (-y)^2 are equal. This symmetry is the heart of everything that follows.

Adding two points

The miracle of elliptic curves is that you can define an addition between two points on the curve, whose result is still a point on the curve. This addition has nothing to do with the ordinary addition of coordinates: it is geometric.

To add two points P and Q:

1. Draw the line passing through P and Q.
2. This line intersects the curve again at a third point (a cubic is cut in three points by a line).
3. Reflect this third point about the x-axis. The point obtained is P + Q.

            y
            |        R'  (third intersection)
            |       *
            |   Q  /
            |  * '/
            | ' /
     -------+--/------------------- x
            | /
            |*  P
            |
            |          * P+Q  (reflection of R')

The final reflection is not a detail: without it, the operation would not be associative and would not form a proper algebraic structure.

The case P + P: the tangent

How do you add a point to itself? If P and Q coincide, the « line through the two » becomes the tangent to the curve at P. You take its second intersection point with the curve, then reflect it, exactly as before. The result is written 2P.

The point at infinity

What happens if the line (PQ) is vertical? It then connects P and its mirror -P, and does not intersect the curve anywhere else. For this case we invent a special point, the point at infinity, written O.

This point plays the role of the identity element: for any point P, we have P + O = P. It is the equivalent of zero for ordinary addition. The opposite -P of a point P is simply its reflection (x, -y), and P + (-P) = O.

With this addition, the points of the curve form a complete mathematical structure (a commutative group), on which we will be able to build an entire cryptography.

In summary

• An elliptic curve has the equation y^2 = x^3 + a*x + b and is symmetric about the x-axis.
• You add two points by drawing their line, taking the third intersection with the curve, then reflecting it below the x-axis.
• For P + P, the line becomes the tangent at P.
• The point at infinity O is the identity element; the opposite of P is its reflection, and P + (-P) = O.