Diffie–Hellman key exchange

Two people who have never met need a shared password, but the only channel between them is a megaphone in a crowded room. Everything they say, an eavesdropper hears. And yet they can still walk away knowing a number she can't — using nothing but a one-way arithmetic trick.

What you're seeing

Alice and Bob first agree, out loud, on two public numbers: a prime p and a base g. Then each picks a private number — Alice's a, Bob's b — and tells no one. Each publishes only g raised to their secret, wrapped around p: Alice shouts A, Bob shouts B. Eve hears p, g, A and B — everything.

Now the magic. Alice takes Bob's public B and raises it to her secret a; Bob takes A and raises it to his secret b. Both are really computing g to the power a×b — the same number, reached from two directions — so they land on an identical secret without either exponent ever crossing the room.

Eve is stuck. To copy the trick she'd need one of the private exponents, which means undoing "g to the what? gives A" — the discrete logarithm. For the toy primes here she can just try every power (drag p to 23 and her whole search is a couple dozen guesses). The bars below count that simplest attack. Cleverer methods than brute force exist — they're what actually decides how big p has to be — yet even the best known ones still blow up fast enough that at the ~2048-bit primes real systems use, no attack comes close to finishing. Meanwhile Alice's and Bob's work barely moves. Drag p up and watch the two bars split apart: that widening gap is the security.

The rule, exactly. Public: prime p, generator g (a primitive root, so its powers cycle through every nonzero residue). Alice sends A = g^a mod p, B = g^b mod p and the shared secret is B^a = A^b = g^ab mod p. Verified in node (improve/verify/44-diffie.js): across 400 random exchanges over ten primes both sides land on the identical value and it always equals g^ab mod p; the eavesdropper's brute-force discrete log recovers the secret for every toy prime; and the work ratio Eve/Alice climbs from ~3× at p = 23 to ~768× at p = 12289 — the one-way gap widening on cue. Negative controls: a base that isn't a primitive root only reaches a small subgroup of residues (why g must be a generator), and the public product A·B mod p — which equals g^a+b — is not the secret g^ab, confirming no public combination of the overheard numbers yields the key; you genuinely need a private exponent.

← the cabinet · Thought Toys — a cabinet of explorable explanations. Exhibit 44.