Elliptic curves without fear.

In 1985, Victor Miller at IBM and Neal Koblitz at the University of Washington independently proposed the same idea: to base public key cryptography not on the numbers modulo a prime, but on the points of an elliptic curve. The proposal took almost twenty years to catch on, held back by patents, distrust of unfamiliar mathematics and the comfort of RSA. Today elliptic curves protect most of the secure connections on the internet, sign inside the electronic identity documents of many countries and authorize every transaction on the major blockchains.

The reason is a number. For equal security, a 256 bit elliptic curve key replaces a 3072 bit RSA key. This article explains where that difference comes from, starting with something as concrete as adding two points with a ruler.

What an elliptic curve is

Despite the name, it has nothing to do with an ellipse; the name comes from elliptic integrals, which led to their study in the nineteenth century. For cryptography, an elliptic curve is the set of points (x, y) satisfying a Weierstrass equation, plus an extra point called the point at infinity, O:

The remarkable thing is that these points can be added, and the addition has every property one would expect: it is associative and commutative, it has an identity element and every point has an inverse. In other words, they form a group, the same algebraic structure as the numbers modulo p in the article on the foundations, with a different geometry.

The chord and tangent rule

To add two points P and Q, draw the line through both. A cubic cut by a line has, counting multiplicities, three intersections, so the line meets the curve at a third point R. The result is defined as the reflection of R across the horizontal axis. If P = Q, the tangent is used. If the line is vertical, the third point is O, which is why the inverse of (x, y) is (x, y).

That this operation is associative is far from obvious; the proof requires a fair amount of algebraic geometry. But it can be checked in the drawing. The lab lets you move the two points and see the full construction.

From geometry to the finite field

Cryptography does not use the real numbers, which have infinite precision and exploitable continuous properties. It uses the same formulas with arithmetic modulo a prime p. Division is replaced by multiplication by the modular inverse. The curve stops being a line and becomes a cloud of points with integer coordinates, seemingly disordered, but with its group structure fully intact.

How many points does it have? Hasse’s theorem, from 1933, answers with remarkable precision: the number of points on the curve over the field of p elements differs from p + 1 by at most 2√p. For cryptography, curves are chosen whose number of points is prime, or a large prime times a small factor called the cofactor.

Multiplying by a number, and the inverse problem

Adding a point to itself k times is written k · G and is called scalar multiplication. Doing it one addition at a time would be impractical for a 256 bit k, but the double and add method handles it with about 256 doublings and, on average, 128 additions, just like fast exponentiation in modular arithmetic.

Here the decisive difference from RSA appears. For factoring integers or computing discrete logarithms modulo a prime there are subexponential algorithms, from the index calculus family, which exploit the fact that integers break down into small factors. Points on an elliptic curve have no useful notion of “small factors”. For well chosen curves, the best known attack remains generic: Pollard’s rho method, which needs about √n operations. With a 256 bit n, that is 2¹²⁸.

The gap widens with the security level because attacks on RSA are subexponential while attacks on curves are exponential. In practice, this means smaller keys and signatures, faster private key operations and lower power consumption, which is decisive in smart cards and mobile devices. An ECDSA signature over P 256 takes 64 bytes; an RSA signature of comparable strength, 384.

Not every curve will do

Security depends on choosing the curve well, and history records several traps.

• Anomalous curves. If the number of points is exactly p, the discrete logarithm can be solved in polynomial time.
• Low embedding degree. On certain curves, supersingular ones among them, the 1993 attack by Menezes, Okamoto and Vanstone transfers the problem to a finite field where subexponential algorithms do exist.
• Order with small factors. If the group has no large prime subgroup, the Pohlig and Hellman method splits the problem into easy pieces.
• Invalid points. A verifier that does not check that a received point lies on the curve may end up computing on a different, weak curve chosen by the attacker. Validating input points is not optional.

The named curves

For all these reasons, nobody generates their own curve: standardized curves are used, with public, well studied parameters.

Curve25519 deserves a note of its own, because it changed how people think about design. Bernstein did not merely look for a curve with no known weaknesses, but for one in which every decision had a public justification, and in which the simplest implementation was also the secure one. Its signature variant, in Edwards form, has a “complete” addition law: the same formula works for adding, doubling and operating with the identity, with no branches that leak information through computation time. The next article in the series shows how this curve is used in EdDSA and why its signature is deterministic.

← All notes