Elliptic Curves: Why Points on a Curve Can Be "Added"

This article has three layers:

1. The intuition: the chord-and-tangent rule and "walking $k$ steps"
2. Real-world use: Bitcoin, Ethereum, Apple Pay, Signal and the PS3 private key leak
3. The mathematics: the group law, curves over finite fields, ECDSA and a worked example over $\mathbb{F}_{17}$

Layer 1: The Intuition

1.1 What an elliptic curve looks like

Elliptic curves have nothing to do with ellipses (the name comes from integrals for the arc length of an ellipse). An elliptic curve is simply the graph of the equation

$$y^2 = x^3 + ax + b$$

and it is symmetric about the $x$-axis. Bitcoin's secp256k1 is about the simplest one: $y^2 = x^3 + 7$.

1.2 The chord-and-tangent rule: how "addition" is defined

Take two points $P$ and $Q$ on the curve:

1. Draw the line through $P$ and $Q$. It always meets the curve at a third point $R'$ (a cubic equation has three roots);
2. Reflect $R'$ across the $x$-axis to get $R$;
3. Define $P + Q = R$.

If $P = Q$, use the tangent at $P$ in place of the line through the two points. If the line is vertical ($P$ and its reflection), the intersection is "at infinity", written $O$, and it serves as the zero element.

Amazingly, this seemingly arbitrary rule is commutative and associative, has a zero element, and gives every point an inverse (its reflection). In other words, the points on the curve form a group.

1.3 Private keys and public keys

• Private key: a very large random integer $k$ (256 bits in Bitcoin);
• Public key: the public base point $G$ added to itself $k$ times, $Q = kG$.

It is like starting from $G$ on a giant, erratically jumping clock face and walking $k$ steps. Given the start and the end, you can hardly work out how many steps were taken. With the "double-and-add" trick, computing $kG$ takes only about $256$ doublings and additions; finding $k$ in reverse takes even the best algorithms about $2^{128}$ steps.

Layer 2: Real-World Use

Why it's preferred over RSA: for the same 128-bit security, an elliptic curve key is 256 bits while RSA needs 3072. Short keys, short signatures and fast computation all matter for phones, smart cards and blockchains.

Layer 3: The Mathematics

3.1 Formulas for the group law

Let $P = (x_1, y_1)$ and $Q = (x_2, y_2)$. First find the slope of the line:

$$\lambda = \begin{cases} \dfrac{y_2 - y_1}{x_2 - x_1}, & P \neq Q \\[2ex] \dfrac{3x_1^2 + a}{2y_1}, & P = Q \ (\text{tangent, by implicit differentiation}) \end{cases}$$

Then

$$x_3 = \lambda^2 - x_1 - x_2,\qquad y_3 = \lambda(x_1 - x_3) - y_1.$$

Derivation: substituting $y = \lambda(x - x_1) + y_1$ into the curve equation gives a cubic with leading term $x^3$ and $x^2$ coefficient $-\lambda^2$. By Vieta's formulas, the three roots sum to $x_1 + x_2 + x_3 = \lambda^2$.

Associativity is the hardest part: expanding the formulas directly is extremely tedious. More elegant proofs use algebraic geometry (the Riemann–Roch theorem or the Cayley–Bacharach theorem); here we simply accept it.

3.2 Moving to a finite field

Cryptography doesn't use the real numbers but a finite field $\mathbb{F}_p$: every division in the formulas above becomes multiplication by a multiplicative inverse modulo $p$. The curve turns into a scatter of discrete points, but the group law formulas don't change at all, and it is still an abelian group.

How many points are there? Hasse's theorem says $\big|\#E(\mathbb{F}_p) - (p+1)\big| \le 2\sqrt{p}$, so the number of points is about $p$. In practice one picks a curve whose point count is a large prime (or a large prime times a small cofactor), so the group is nearly cyclic and has no small subgroups to exploit (see Pohlig–Hellman in "Diffie–Hellman and the Discrete Logarithm").

3.3 A worked example: a curve over $\mathbb{F}_{17}$

3.4 ECDSA, and why reusing $k$ is fatal

Let the base point $G$ have order $n$, with private key $d$, public key $Q = dG$ and message hash $h$.

Signing: choose a random $k$, compute $R = kG$, take $r = R_x \bmod n$, and

$$s = k^{-1}(h + r d) \bmod n.$$

The signature is $(r, s)$. Verification: compute $u_1 = h s^{-1}$ and $u_2 = r s^{-1}$, and check that the $x$-coordinate of $u_1 G + u_2 Q$ equals $r$. (Because $u_1 G + u_2 Q = s^{-1}(h + rd)G = kG$.)

What happens if $k$ repeats: two messages $h_1, h_2$ use the same $k$, so $r$ is the same, and

$$s_1 - s_2 = k^{-1}(h_1 - h_2) \ \Rightarrow\ k = \frac{h_1 - h_2}{s_1 - s_2},\qquad d = \frac{s_1 k - h_1}{r}.$$

Two lines of algebra yield the private key. That is all the mathematics of the PS3 incident. Modern implementations use RFC 6979: $k$ is generated deterministically from the private key and the message hash, which doesn't depend on the quality of a random number generator and guarantees different messages get different values of $k$.

Summary