Elliptic-Curve Diffie–Hellman

Multiplying a point by k means adding it to itself k times. Double-and-add does it in a few steps by reading k in binary. Step through one of the four multiplications; the plot above follows.

Multiplication Alice’s public point: dA · G Bob’s public point: dB · G Alice’s shared point: dA · QB Bob’s shared point: dB · QA

Adding two points is done with formulas, not with a ruler. They come from the chord-and-tangent rule for curves over the real numbers, but over a finite field there is no chord to draw: only the algebra remains, with a modular inverse where a division would be.

Finding d from G and Q = d · G is the elliptic-curve discrete logarithm problem. On a curve this small it is no problem at all.

What is an elliptic curve over a finite field?

The set of pairs (x, y) of residues modulo a prime p with y² ≡ x³ + ax + b, together with one extra point O. The coefficients must satisfy 4a³ + 27b² ≢ 0; otherwise the curve is singular and what follows fails. It is a finite set of points, not a line that can be drawn.

What is the point at infinity?

O is the identity of the group: P + O = P for every point. It has no coordinates, and it is not the pair (0, 0), which may or may not be a point of the curve like any other pair.

What is point addition, and why do the points form a group?

Two points are added by the formulas shown under “Show point-addition mathematics”. The inverse of (x, y) is (x, −y), and a point plus its inverse is O. The sum of two points of the curve is again a point of the curve, the order of adding does not matter, and (P + Q) + R = P + (Q + R). That last fact is far from obvious from the formulas; this page’s tests check it for every triple of points on several small curves.

What is scalar multiplication?

kP = P + P + … + P, with k terms. The order of G is the smallest n ≥ 1 with nG = O; the multiples of G are then n different points, which need not be all the points of the curve. This page asks for a G of prime order, as real systems do.

Why do Alice and Bob get the same point?

d_A · Q_B = d_A(d_B G) = (d_Ad_B)G = d_B(d_A G) = d_B · Q_A

Adding G to itself d_Ad_B times gives the same point however the additions are grouped. It is the same idea as classical Diffie–Hellman, where (g^b)^a = (g^a)^b, in a different group:

What is the elliptic-curve discrete logarithm problem?

Given G and Q_A = d_A · G, find d_A. Computing Q_A takes a few dozen point operations even for enormous scalars; no practical way back is known for properly chosen curves with a subgroup of large prime order.

Why are toy curves insecure?

The default curve has 19 points, so Eve tries at most 18 scalars. Any curve on this page has fewer than 300. A somewhat larger prime would not help: real curves are standardized, with primes of 256 bits or more and many other properties checked by experts. Use the Modern ECDH view to see one at work.

Why does ECDH require authentication?

The exchange shows that two parties computed the same point, not who they are. Someone in the middle can swap each public point for her own and share one secret with Alice and another with Bob. Real protocols authenticate the public keys, for example with signatures or certificates.

Public keys are not secrets. They are shown in the standard SPKI format, as PEM. The fingerprint is the SHA-256 of the key’s bytes: a way to tell keys apart, not proof of whose key it is.

own private key + other’s public key→ECDH→shared bits→HKDF-SHA-256 with salt and info→256-bit key

ECDH gives both sides the same number: the x-coordinate of the shared point. That number is not used as a key directly. It is not uniformly random as a bit string, and one exchange often has to yield several keys. A key derivation function fixes both.

HKDF works in two stages. Extract mixes the shared bits with a salt (random, and public) into one strong intermediate key. Expand stretches that into as many output bytes as are asked for, tagged with an info string that says what the key is for. Both sides must use exactly the same salt, info, hash and length; then equal shared bits give equal keys, and different purposes give unrelated keys.

• ECDH alone does not authenticate anyone. The message “Shared keys match” says that two computations in this page agree, not that Alice and Bob know who the other is.
• An attacker in the middle can replace each public key with her own, and then shares one key with each side. Real protocols authenticate the exchanged keys, for example with digital signatures or certificates.
• A fingerprint helps only if it is compared through a channel that is already trusted.
• The raw shared bits are passed through a key derivation function, as here, and never used directly.
• Comparing the two derived keys inside one page is a demonstration. A real protocol confirms keys by using them, with authenticated encryption.
• This is key agreement only: it encrypts nothing, and it is not a messaging protocol. Private keys are created non-extractable and last only while this page is open; overwriting buffers afterwards is good practice, not a guarantee that JavaScript leaves no copy.