Elliptic curves, from the equation to the group

Every elliptic-curve scheme in use rests on one operation: adding two points on a curve. This note builds that operation up from the equation, then carries it out by hand on a curve small enough to draw.

Curve used here
y2 = x3 + 3x + 2 over F97
Its group
103 points, counting the point at infinity. The order is prime, so every point except the identity generates the whole group.
The group law
Chord and tangent, with the point at infinity as the identity
Cost of computing kP
About log2 k doublings, plus an addition for each 1 bit of k

Why elliptic curves

A public-key system needs a group in which one direction is easy and the other is hard. With a point P and an integer k, computing kP = P + P + … + P takes a few hundred group operations even when k has 256 bits. Recovering k from P and kP is the elliptic-curve discrete logarithm problem, and for a well-chosen curve the best known way to solve it is a generic collision search whose cost grows with the square root of the group size.

That is the whole case for elliptic curves. The multiplicative group of a finite field, and the integers modulo an RSA modulus, have more structure, and that structure admits subexponential attacks such as the number field sieve. Their parameters have to be much larger to compensate: a 256-bit elliptic curve is conventionally matched with a 3072-bit RSA modulus.

The curve

Over any field whose characteristic is not 2 or 3, an elliptic curve can be written in short Weierstrass form:

E : y2 = x3 + ax + b,    with 4a3 + 27b2 ≠ 0 The condition rules out cusps and self-crossings, where the group law below would break.

The points of E are the solutions (x, y), together with one extra point O, called the point at infinity, which plays the role of zero. Other shapes of equation describe the same objects with faster formulas: Montgomery curves, used by X25519, and twisted Edwards curves, used by Ed25519, are both elliptic curves that can be rewritten in this form. Over fields of characteristic 2 the equation becomes y2 + xy = x3 + ax2 + b.

Adding two points

PQ−(P + Q)P + Q
y2 = x3 − x + 1 over the real numbers. The line through P and Q meets the curve in exactly one more point; its reflection in the x-axis is P + Q.

Over the real numbers the rule can be drawn. A straight line through two points P and Q of the curve meets it in exactly one more point, counted with multiplicity. Reflecting that third point in the x-axis gives P + Q. To double a point, use the tangent line at P instead. The negative of P = (x, y) is −P = (x, −y), and a vertical line through P and −P meets the curve “at infinity”, which is why P + (−P) = O.

Writing the rule in coordinates gives formulas that make sense over any field. For P = (x1, y1) and Q = (x2, y2) with Q ≠ ±P:

λ = (y2 − y1) / (x2 − x1),    x3 = λ2 − x1 − x2,    y3 = λ(x1 − x3) − y1 For doubling, the slope is the tangent's: λ = (3x12 + a) / (2y1).

With this operation the points form an abelian group. That the operation is associative, (P + Q) + R = P + (Q + R), is not visible in the picture and takes real work to prove; it is the one deep fact in this note, and everything else follows from it.

Over a finite field

Cryptography uses the same formulas over a finite field. Take the prime 97 and the curve y2 = x3 + 3x + 2. Every operation is now arithmetic modulo 97, and dividing means multiplying by an inverse modulo 97. The picture loses its geometry but keeps one piece of it: since (x, y) and (x, −y) are both points, the set is symmetric.

0x = 9696P−P
All 102 affine points of y2 = x3 + 3x + 2 over F97. The picture is symmetric about the dashed line because (x, y) and (x, −y) = (x, 97 − y) are both points; P = (0, 14) and −P are marked.

Add P = (0, 14) to Q = (20, 60). The slope is

λ = (60 − 14) / (20 − 0) = 46 · 20−1 = 46 · 34 = 12   (mod 97) 34 is the inverse of 20 modulo 97, because 20 · 34 leaves remainder 1.
x3 = 122 − 0 − 20 = 27,    y3 = 12 · (0 − 27) − 14 = 50   (mod 97) So P + Q = (27, 50).

Doubling P uses the tangent slope (3 · 02 + 3) / (2 · 14) = 59, and gives 2P = (86, 53). Repeating the addition lists the multiples of P: 1P = (0, 14), 2P = (86, 53), 3P = (38, 59), 4P = (16, 13), 5P = (20, 60), 6P = (27, 50), and so on. Q was chosen as 5P, which is why P + Q came out as 6P.

How many points

A curve over Fp has about p + 1 points, and never far from it. Hasse's theorem bounds the difference:

#E(Fp) = p + 1 − t,    with |t| ≤ 2√p t is the trace of Frobenius.

For our curve the interval runs from 78.3 to 117.7, and the actual count is 103: 102 affine points plus O, so t = -5. Counting points on a small curve is a loop over x. Counting them on a 256-bit curve takes Schoof's polynomial-time algorithm, or in practice its refinement by Elkies and Atkin, and it is how standard curves are chosen: generate candidates until the count has the required form.

The group of points is either cyclic or a product of two cyclic groups. What cryptography needs is a large subgroup of prime order n, so that #E = h · n with a small cofactor h. The NIST prime curves and secp256k1 have h = 1; Curve25519 has h = 8 and Curve448 has h = 4. A cofactor is not a weakness in itself, but protocols must keep secret-dependent computation inside the prime-order subgroup, or an attacker can learn the secret modulo h. The Pohlig–Hellman page explains why.

Multiplying a point by an integer

Adding P to itself k times would take k − 1 additions, which is hopeless for a 256-bit k. Double-and-add reads k in binary, from the most significant bit: for each bit, double the running total, and add P when the bit is 1.

Computing 77P from the bits of 77 = 10011012, most significant first. Each row doubles the running total, and adds P when the bit is 1.
bitoperationrunning totalpoint
1start at P1P(0, 14)
0double2P(86, 53)
0double4P(16, 13)
1double, then add P9P(96, 17)
1double, then add P19P(84, 26)
0double38P(79, 79)
1double, then add P77P(24, 30)

That is 6 doublings and 3 additions instead of 76 additions. A 256-bit scalar takes about 255 doublings and, on average, 128 additions. Windowed methods cut the additions further by adding precomputed small multiples of P.

Curves in use

  • P-256, P-384 and P-521 are the NIST prime curves, specified in SP 800-186 and used in TLS certificates, government systems and most hardware security modules.
  • secp256k1, y2 = x3 + 7, is the curve of Bitcoin and Ethereum signatures. Its j-invariant is 0, which gives it an extra endomorphism of order 3: this speeds up scalar multiplication and also speeds up Pollard's rho by a factor of √3.
  • Curve25519, over the prime 2255 − 19, is used for key exchange as X25519 and, in Edwards form, for signatures as Ed25519. It was designed so that simple, constant-time implementations are also the fast ones. Curve448 is its higher-security sibling.

The note on the discrete logarithm problem gives the size of each one's group and what it costs to attack, and the schemes catalogue covers the key-exchange and signature schemes built on them.

Primary sources

  1. J. H. Silverman, The Arithmetic of Elliptic Curves, 2nd edition, Springer GTM 106 (2009)
  2. D. Hankerson, A. Menezes and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer (2004)
  3. R. Schoof, "Elliptic curves over finite fields and the computation of square roots mod p", Mathematics of Computation 44 (1985)
  4. P. L. Montgomery, "Speeding the Pollard and elliptic curve methods of factorization", Mathematics of Computation 48 (1987)
  5. D. J. Bernstein, "Curve25519: new Diffie-Hellman speed records", PKC 2006
  6. NIST SP 800-186, Recommendations for Discrete Logarithm-based Cryptography: Elliptic Curve Domain Parameters (2023)
  7. SECG, SEC 2: Recommended Elliptic Curve Domain Parameters, version 2.0 (2010)
  8. A. Langley, M. Hamburg and S. Turner, "Elliptic Curves for Security", RFC 7748