The group law on elliptic curves, worked through
Why adding points on an elliptic curve gives a group, checked on a curve with 19 points, and why the discrete logarithm stays hard anyway.
Elliptic-curve cryptography rests on two operations: adding two points, and “multiplying” a point by an integer . The security assumption is that cannot be recovered efficiently from and . That statement hides two separate questions. Why is point addition a group operation at all, associative, with an identity and inverses? And why is undoing the multiplication hard when the formulas involved are high-school algebra?
The formulas take a few lines to derive. After that, everything is checked on a curve over with exactly 19 points: small enough to do on paper, and small enough to test every case by machine. The last part is about what such a small example cannot tell you.
The curve and the point at infinity
Let be a field whose characteristic is neither 2 nor 3, and pick with . The elliptic curve
consists of all solutions plus one extra point . The condition on and means that has no repeated root, so the curve has no cusp and no self-intersection, and every point has a unique tangent line. The curve violates it: it has a cusp at the origin, and the tangent construction below breaks down there.
comes from projective geometry. Written homogeneously, the equation is . Setting forces , which leaves the single point . Every vertical line passes through it.
Chords and tangents
Over the reals, addition has a picture. The line through two points and on the curve meets it in a third point , and is defined as the reflection of in the -axis.
The useful fact is that can be computed without taking any roots. Take and with , and the line through both:
Substituting it into the curve equation and collecting terms gives a monic cubic,
two of whose roots, and , are already known. By Vieta’s formulas the three roots add up to minus the coefficient, so and
lies on the line. Reflecting flips the sign of the second coordinate, and substituting gives
Only field operations appear, so the same formulas work over any field, including , where there is nothing left to draw.
The remaining cases:
- Doubling, : the chord becomes the tangent. Differentiating implicitly, , so . The point of contact is a double root, which gives ; the formula for is unchanged.
- , : the line is vertical and its third intersection is , so . This includes doubling a point with , whose tangent is vertical.
- as a summand: .
Which axioms are easy
Closure, identity, inverses and commutativity are immediate. is the identity. The inverse of is , because the line through the two is vertical. The line through and is the line through and , so the operation is commutative. And the formulas produce coordinates in that satisfy the curve equation by construction.
Associativity is a different matter. Nothing in the picture suggests that , and none of the known proofs is short. Washington gives a fairly elementary one in Section 2.4 of his book. Silverman derives it in Chapter III from the Riemann–Roch theorem: the map identifies the points with the group of degree-zero divisor classes, whose operation is associative for free. If you only know the group law through its formulas, it is worth knowing that this is where the work is hidden.
What a small curve allows instead is brute force: check every triple. That proves nothing about other curves, but it is very good at catching mistakes, as the end of this post shows.
A curve with 19 points
The curve
is a standard textbook example; Paar and Pelzl use it in Chapter 9. The non-singularity condition holds, since .
To list its points, test for each from 0 to 16 whether is a square modulo 17. Nine values of qualify, each with two square roots , which gives 18 points, plus :
| x | 0 | 3 | 5 | 6 | 7 | 9 | 10 | 13 | 16 |
|---|---|---|---|---|---|---|---|---|---|
| y | 6, 11 | 1, 16 | 1, 16 | 3, 14 | 6, 11 | 1, 16 | 6, 11 | 7, 10 | 4, 13 |
Hasse’s theorem bounds the count by , which here means somewhere between about 9.75 and 26.25. Since 19 is prime, Lagrange’s theorem does the rest: every point other than has order 19, so the group is cyclic and any such point generates it.
Doubling . Division now means multiplying by an inverse mod 17. The tangent slope is . Here and (because ), so , and
So . To check: , and .
Adding and . The chord slope is , so and , that is, . Carrying on gives all multiples up to , here in pairs:
| k | kP | 19 − k | (19 − k)P |
|---|---|---|---|
| 1 | (5, 1) | 18 | (5, 16) |
| 2 | (6, 3) | 17 | (6, 14) |
| 3 | (10, 6) | 16 | (10, 11) |
| 4 | (3, 1) | 15 | (3, 16) |
| 5 | (9, 16) | 14 | (9, 1) |
| 6 | (16, 13) | 13 | (16, 4) |
| 7 | (0, 6) | 12 | (0, 11) |
| 8 | (13, 7) | 11 | (13, 10) |
| 9 | (7, 6) | 10 | (7, 11) |
The pairing shows the only visible regularity: and share their -coordinate. Down the columns, the coordinates follow no pattern.
Fast in one direction
Nobody computes with additions. Double-and-add walks through the bits of from the top: double at every bit, add when the bit is
- For the intermediate results are , then and , then , then and . An -bit scalar costs doublings and at most additions, so about 510 group operations for a 256-bit .
The other direction
Given and , find . For the table says . With 19 points, looking it up is the whole algorithm. The real question is how the cost grows with the group order .
Baby-step giant-step (Shanks) writes with , stores the baby steps for , and walks with giant steps until it lands on a stored point. Here , the stored points are , and . The first giant step, , is not stored; the second, , is the baby step . Hence .
Both time and memory grow like . Pollard’s rho method (1978) needs about the same number of steps, on average roughly , with constant memory.
Why nothing much better is known. Shoup proved in 1997 that any generic algorithm, one that uses only group operations and ignores how elements are encoded, needs group operations, where is the largest prime factor of the group order. In that model, baby-step giant-step and rho are optimal. In , index calculus beats the bound by exploiting the fact that integers factor into small primes. For points on a general elliptic curve over a prime field, no comparable notion is known, and neither is an algorithm that does substantially better than .
For scale: secp256k1, the curve Bitcoin uses, is over the prime field with . Its group order is a prime just below (cofactor 1), so rho needs about group operations.
Where intuition misleads
Simple formulas, simple inversion. The addition formulas are easy to invert: given and , subtracting gives . What is hard is counting how many times was added, and the formulas say nothing about that. Its hardness is an assumption, not a theorem. Shoup’s bound covers generic algorithms only, and the toy table is no evidence at all, since every problem with 19 elements is easy.
Large group, secure group. What matters is the largest prime factor of the group order. If splits into small primes, the Pohlig–Hellman method reduces the logarithm to logarithms in the small subgroups, and the cost is set by the largest factor. That is why curves in use have prime order or a tiny cofactor.
Prime order is enough. It is not. If (an anomalous curve), Smart’s 1999 method solves the logarithm in polynomial time. If the embedding degree, the smallest with , is small, the MOV attack of Menezes, Okamoto and Vanstone moves the problem into , where index calculus applies. SEC 1 therefore requires, when validating curve parameters, that for all and that . The toy curve fails this independently of its size: , so its embedding degree is 9. secp256k1 passes.
Correct maths, correct code. The case distinctions (, , ) are a known source of bugs. Double-and-add has a second problem: whether an addition happens depends on a bit of the secret scalar, which can show up in timing or power consumption. Implementations therefore use fixed operation sequences such as the Montgomery ladder, which RFC 7748 specifies for X25519, or complete addition formulas without special cases, such as those Renes, Costello and Batina give for prime-order curves.
Checking it by machine
This program contains everything above: addition with all cases, double-and-add, point counting, an exhaustive test of the group axioms, and baby-step giant-step.
from math import isqrt
p, a, b = 17, 2, 2
O = None # point at infinity
def on_curve(P):
return P is O or (P[1] ** 2 - (P[0] ** 3 + a * P[0] + b)) % p == 0
def neg(P):
return O if P is O else (P[0], -P[1] % p)
def add(P, Q):
if P is O: return Q
if Q is O: return P
(x1, y1), (x2, y2) = P, Q
if x1 == x2 and (y1 + y2) % p == 0:
return O # P + (-P)
if P == Q:
lam = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
else:
lam = (y2 - y1) * pow(x2 - x1, -1, p) % p
x3 = (lam * lam - x1 - x2) % p
return (x3, (lam * (x1 - x3) - y1) % p)
def mul(k, P): # double-and-add
R = O
for bit in bin(k)[2:]:
R = add(R, R)
if bit == "1":
R = add(R, P)
return R
points = [O] + [(x, y) for x in range(p) for y in range(p) if on_curve((x, y))]
assert len(points) == 19
for P in points: # identity, inverse, commutative
assert add(P, O) == P and add(P, neg(P)) is O
for Q in points:
assert add(P, Q) == add(Q, P) and on_curve(add(P, Q))
for R in points: # associative: 19³ = 6859 triples
assert add(add(P, Q), R) == add(P, add(Q, R))
G, Q = (5, 1), (13, 7)
assert mul(2, G) == (6, 3) and mul(3, G) == (10, 6) and mul(19, G) is O
m = isqrt(len(points) - 1) + 1 # ⌈√19⌉ = 5
baby = {mul(j, G): j for j in range(m)}
giant, step = Q, neg(mul(m, G))
for i in range(m):
if giant in baby:
print("log =", i * m + baby[giant]) # log = 8
break
giant = add(giant, step)
The exhaustive test earns its keep. Drop the factor 2 from the tangent slope, and all 18 doublings land off the curve while 1152 of the 6859 triples violate associativity. Return the third intersection instead of , and stops being the identity for every point on the curve, with 6498 failing triples. Neither mistake shows up if you only check a few examples by hand that were produced with the same wrong formula.
Further reading
- Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, 2nd edition, CRC Press 2008. Chapter 2 (the group law; Section 2.4, proof of associativity) and Chapter 5 (the discrete logarithm problem: baby-step giant-step, rho, MOV, anomalous curves).
- Joseph H. Silverman, The Arithmetic of Elliptic Curves, 2nd edition, Springer 2009 (Graduate Texts in Mathematics 106). Chapter III, §2 and §3.
- Christof Paar, Jan Pelzl, Understanding Cryptography, Springer 2010. Chapter 9, with the curve over .
- Victor Shoup, Lower Bounds for Discrete Logarithms and Related Problems, Eurocrypt 1997 (revised version).
- Nigel P. Smart, The Discrete Logarithm Problem on Elliptic Curves of Trace One, Journal of Cryptology 12 (1999), pp. 193–196.
- Alfred Menezes, Tatsuaki Okamoto, Scott Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Transactions on Information Theory 39(5), 1993, pp. 1639–1646.
- Standards for Efficient Cryptography Group, SEC 1: Elliptic Curve Cryptography, version 2.0, 2009, Section 3.1.1.2.1 (parameter validation), and SEC 2: Recommended Elliptic Curve Domain Parameters, version 2.0, 2010, Section 2.4.1 (secp256k1).
- Adam Langley, Mike Hamburg, Sean Turner, RFC 7748: Elliptic Curves for Security, 2016, Section 5 (the Montgomery ladder for X25519 and X448).
- Joost Renes, Craig Costello, Lejla Batina, Complete addition formulas for prime order elliptic curves, Eurocrypt 2016.
- The script behind every number in this post is in the
repository of this site at
tests/articles/ecc_toy_curve.py; the figure comes fromtests/articles/ecc_chord_svg.py --lang en.