Elliptic curves: The arithmetic of curves: ECDH, ECDSA, Ed25519

Diffie–Hellman and RSA need numbers of thousands of bits, because sub-exponential algorithms (the number field sieve and its cousins for discrete logarithms) attack the multiplicative structure of the integers. In 1985 Neal Koblitz and Victor Miller, independently, proposed doing the same cryptography in a different group, where no such shortcut was known: the points of an elliptic curve over a finite field. Forty years later there is still none, and elliptic-curve cryptography (ECC) has replaced RSA almost everywhere.

Adding points with a ruler

An elliptic curve, in the form cryptographers use, is the set of solutions of

E : y^{2} = x^{3} + a x + b, 4 a^{3} + 27 b^{2} \neq 0,

together with one extra point $𝒪$ , “at infinity”. The condition rules out cusps and self-crossings. The curve is symmetric about the $x$ -axis. Points can be added: draw the line through $P$ and $Q$ ; it meets the curve in exactly one more point $R^{'}$ ; reflect it across the $x$ -axis to get $P + Q$ . To double a point, use the tangent. A vertical line meets the curve at infinity, so $P + (- P) = 𝒪$ , where $- P$ is the reflection of $P$ .

The chord-and-tangent law over the real numbers. Change the curve with

a

and

b

and move

P

and

Q

along it. The line through them cuts the curve at a third point

- (P + Q)

; its reflection is

P + Q

. When

P = Q

the line is the tangent. With

a = - 2

and

b

small, the curve splits into two pieces, and the law still works.

In coordinates, for $P = (x_{1}, y_{1})$ and $Q = (x_{2}, y_{2})$ with $P \neq - Q$ , let $λ$ be the slope of the line, $λ = (y_{2} - y_{1}) / (x_{2} - x_{1})$ , or $λ = (3 x_{1}^{2} + a) / (2 y_{1})$ for the tangent. Then

x_{3} = λ^{2} - x_{1} - x_{2}, y_{3} = λ (x_{1} - x_{3}) - y_{1} .

Theorem (the group law)

With this addition and $𝒪$ as identity, the points of $E$ form an abelian group. The same formulas, computed in any field $K$ , make $E (K)$ , the points with coordinates in $K$ , a group.

About the proof

Commutativity is clear (the line through $P$ and $Q$ is the line through $Q$ and $P$ ), the identity and inverses come from vertical lines, and closure from the fact that a line meets a cubic in three points counted with multiplicity. Associativity is the hard part: it can be checked by brute-force algebra on the formulas, or proved elegantly with the Cayley–Bacharach theorem on cubics through eight common points, or via the Riemann–Roch theorem, which identifies $E$ with its own Picard group.

Curves over a finite field

Cryptography needs exact, finite arithmetic, so the coordinates live in $𝔽_{p}$ , the integers modulo a prime $p$ . The “curve” becomes a scatter of points with no visible shape, but the formulas, and the group, are the same.

Theorem (Hasse, 1933)

The number of points of $E$ over $𝔽_{p}$ (counting $𝒪$ ) satisfies $| # E (𝔽_{p}) - (p + 1) | \leq 2 \sqrt{p}$ .

So a curve over a 256-bit prime field has about $2^{256}$ points; Schoof's algorithm (1985) counts them exactly, and curves are chosen whose number of points is a large prime (or a small multiple of one), so that the group is cyclic and has no small subgroups to hide in.

The curve

y^{2} = x^{3} + 2 x + 3

over

𝔽_{97}

: every point of it, and the multiples

G, 2 G, 3 G, \dots

of a generator

G

. Press play: the multiples jump around the grid with no pattern you could follow backwards. Given only the final point, recovering

k

is the elliptic-curve discrete logarithm problem. Here a computer finds it instantly by trying all

k

; with 256-bit numbers, no computer can.

The discrete logarithm on a curve

Multiplying a point by a scalar, $k P = P + P + \dots + P$ , is fast by double-and-add (the additive version of square-and-multiply). Undoing it is the elliptic-curve discrete logarithm problem (ECDLP): given $P$ and $Q = k P$ , find $k$ .

Theorem (generic algorithms, Pollard 1978; Shoup 1997)

In a cyclic group of prime order $n$ , Pollard's rho algorithm finds discrete logarithms in about $\sqrt{π n / 2}$ group operations and constant memory. Conversely, any algorithm that uses the group only through its operations (a generic algorithm) needs about $\sqrt{n}$ of them.

Pollard's rho is the birthday paradox again: a pseudorandom walk on the group eventually repeats a point, and a repetition reveals $k$ . For good elliptic curves, nothing better than these generic attacks is known. So security grows with half the bit size of the group order, and the keys are short:

Security	Symmetric	RSA / finite-field DH	Elliptic curve
112 bits	3DES	2,048 bits	224 bits
128 bits	AES-128	3,072 bits	256 bits
192 bits	AES-192	7,680 bits	384 bits
256 bits	AES-256	15,360 bits	512 bits

ECDH and X25519

Elliptic-curve Diffie–Hellman is the protocol of chapter 08 with the new group: Alice sends $a G$ , Bob sends $b G$ , both compute $a b G$ . In 2006 Daniel J. Bernstein published Curve25519, the curve $y^{2} = x^{3} + 486662 x^{2} + x$ over the prime $2^{255} - 19$ , designed so that the fast, simple implementation is also the safe one: every 32-byte string is a valid public key, the computation (the Montgomery ladder) runs in constant time, and there are no special cases to forget. Its key agreement, X25519, is now the default of TLS 1.3, SSH, Signal and WireGuard. The desktop app's “X25519 + AES-GCM” makes a fresh ephemeral key pair for every message, agrees a secret with the recipient's public key and encrypts with AES-GCM: the ECIES pattern.

ECDSA and the nonce

The Elliptic Curve Digital Signature Algorithm, proposed by Scott Vanstone in 1992 and standardised by ANSI (1999) and NIST (2000), signs the hash $h$ of a message with the private key $d$ (public key $Q = d G$ ) on a curve whose base point $G$ has prime order $n$ :

choose a random nonce $k \in [1, n - 1]$ and let $r = (k G)_{x} mod n$ ;
let $s = k^{- 1} (h + r d) mod n$ ; the signature is $(r, s)$ .

The verifier computes $u_{1} = h s^{- 1}$ , $u_{2} = r s^{- 1}$ and accepts if $(u_{1} G + u_{2} Q)_{x} \equiv r$ . ECDSA over the NIST curve P-256 signs most TLS certificates, passkeys and bank cards. Its weak point is the nonce.

Proposition (a reused nonce leaks the key)

If two messages with hashes $h_{1} \neq h_{2}$ are signed with the same nonce $k$ (visible because $r$ is the same), then

k = \frac{h_{1} - h_{2}}{s_{1} - s_{2}} mod n, d = \frac{s_{1} k - h_{1}}{r} mod n .

Proof

$s_{1} k = h_{1} + r d$ and $s_{2} k = h_{2} + r d$ . Subtracting, $(s_{1} - s_{2}) k = h_{1} - h_{2}$ , which gives $k$ ; then the first equation gives $d$ . Even a few biased bits of $k$ across many signatures are enough to recover $d$ with lattice techniques.

In 2010 the fail0verflow group showed that Sony signed PlayStation 3 software with the same $k$ every time, recovered Sony's private key, and could sign anything. In 2013 a bug in Android's random number generator made Bitcoin wallets reuse nonces, and their coins were stolen. The fix is to never draw $k$ at random: derive it from the key and the message (RFC 6979, 2013).

Ed25519

Bernstein, Niels Duif, Tanja Lange, Peter Schwabe and Bo-Yin Yang designed Ed25519 (2011) on an Edwards-form version of Curve25519, with complete addition formulas (no exceptional cases) and a nonce derived deterministically from a hash of the private key and the message. It is fast, its keys are 32 bytes and its signatures 64, and there is no random nonce to get wrong. SSH, Signal, Tor, Git and the Linux kernel's module signing use it; RFC 8032 (2017) and FIPS 186-5 (2023) standardise it.

Which curves to trust

The NIST curves P-256 and P-384 were generated in 1999 from seeds that were never explained. In 2013 the Snowden documents confirmed that the NSA had backdoored Dual_EC_DRBG, an elliptic-curve random number generator standardised by NIST in 2006: whoever knew the secret relation between its two points could predict its output. No weakness has been found in P-256 itself, but the episode made “rigid”, explainable parameters, like Curve25519's, a design requirement (Bernstein and Lange's SafeCurves project). The desktop app offers both families: ECDSA P-256 for compatibility, Ed25519 and X25519 as first choices. All of them, like RSA, fall to Shor's algorithm.

§Adding points with a ruler

§Curves over a finite field

§The discrete logarithm on a curve

§ECDH and X25519

§ECDSA and the nonce

§Ed25519

§Which curves to trust

§Further reading