How to agree on a secret in front of everyone

Here is a party trick that shouldn't be possible. Two people who have never met stand at opposite ends of a crowded room and shout numbers at each other. Everyone hears every number. When they're done, the two of them share a secret number — and nobody else in the room can work out what it is.

That's not a metaphor loosely inspired by cryptography. It is, move for move, what your browser did during the TLS handshake that fetched this page. The trick is called Diffie-Hellman key exchange, it dates from 1976, and it's one of the few ideas in computer science that deserves the word beautiful without embarrassment. This essay walks through the whole thing: the protocol, the actual math underneath it — group theory, one proof short enough to carry in your head, and a precise statement of what "hard" means — and the ways it breaks when you hold it wrong. There's also a live playground on this site where you can run exchanges and then switch sides and play the eavesdropper. I recommend losing at that game at least once; it's educational in a way no paragraph can be.

The problem nobody could solve for two thousand years

Encryption has a bootstrapping problem. To send you a secret message, I need a key that only we know. But to agree on that key, I need... a way to send you a secret message. For most of history the answer was physical: couriers with locked briefcases, codebooks handed over in person, and an entire military logistics discipline devoted to key distribution. The cipher was rarely the weak point. Moving the keys was.

In 1976 Whitfield Diffie and Martin Hellman published New Directions in Cryptography, building on an idea of Ralph Merkle's, and dissolved the problem instead of solving it: the two parties never send a key at all. They each build the same key, independently, out of one public conversation plus one private ingredient apiece. (In one of history's better footnotes, Malcolm Williamson at GCHQ had found the same construction in 1974, and it stayed classified until 1997. Being right in secret is a hard way to be right.)

The standard warm-up is paint. Alice and Bob publicly agree on a common color, say a liter of yellow. Each secretly picks a private color — Alice red, Bob teal — and mixes it into a copy of the yellow. They swap the mixtures in full view. Now Alice adds her red to the mixture Bob sent, and Bob adds his teal to the mixture Alice sent. Both arrive at the same muddy yellow-red-teal, because mixing is order-independent. Eve, watching, holds two mixtures she cannot un-mix.

The analogy earns its keep: it shows the shape of the trick, a commutative operation that's easy to do and hard to undo. But paint is training wheels. "You can't unmix paint" is an appeal to kitchen intuition, and cryptography can't run on kitchen intuition. We need an arena where "mixing" is a theorem and "you can't unmix it" is a precisely stated computational assumption. Time to meet the arena.

The arena: multiplication mod p

Pick a prime p and do arithmetic on the numbers \{1, 2, \ldots, p-1\}, multiplying as usual but keeping only the remainder mod p. This structure has a name, \mathbb{Z}_p^{\times}, and it is a group under that multiplication — which is a compact way of making three promises:

Closure. The product of two numbers not divisible by p is not divisible by p (that's exactly what p being prime buys you), so multiplying two elements and reducing mod p lands you back in the set.

Identity. 1 does nothing, as usual.

Inverses. This is the interesting promise. For every a in the set there's an x with ax \equiv 1 \pmod{p}. Why? Because \gcd(a, p) = 1, and Bézout's identity says \gcd(a, p) = 1 means there exist integers x and y with ax + py = 1. Read that equation mod p and the py term vanishes: ax \equiv 1. Division exists here: not as a limit or an approximation, but as a consequence of a fact about integers that Euclid could have proved.

So \mathbb{Z}_p^{\times} is a finite world, p-1 elements big, where you can multiply and divide freely and everything wraps around. Take p = 23 (small enough to hold in your head; it shows up again below) and the world is \{1, \ldots, 22\}, with charming facts like 8 \cdot 3 = 24 \equiv 1, so 3 is "one eighth" of this world.

One more theorem, because it's the engine of everything that follows and its proof takes two lines. Fermat's little theorem: for any a in \mathbb{Z}_p^{\times},

a^{p-1} \equiv 1 \pmod{p}

Proof. Multiply every element of \{1, 2, \ldots, p-1\} by a. Because a is invertible, this map is a bijection — it just shuffles the set. So the product of the shuffled set equals the product of the original set:

\begin{aligned} (a \cdot 1)(a \cdot 2) \cdots (a \cdot (p-1)) &\equiv 1 \cdot 2 \cdots (p-1) \pmod{p} \\ a^{p-1} \, (p-1)! &\equiv (p-1)! \pmod{p} \end{aligned}

(p-1)! is a product of invertible elements, hence invertible — cancel it. Done. \blacksquare

Multiplying by a doesn't add anything to the set; it permutes it, and the exponent p-1 falls out of counting. That's the whole proof. Every exponent in the rest of this essay secretly lives mod p-1 because of it.

Last ingredient: a generator. \mathbb{Z}_p^{\times} is cyclic — there exists an element g whose powers g^1, g^2, \ldots, g^{p-1} visit every element of the group exactly once before cycling. (The proof that a generator always exists is a lovely counting argument: in a field, the polynomial x^d - 1 has at most d roots, and chasing that constraint through Euler's \varphi function forces an element of full order to exist. I'll wave at it rather than prove it; the waving is honest.) For p = 23, g = 5 works: the powers of 5 wander through all twenty-two elements — 5, 2, 10, 4, 20, 8, 17, \ldots — hitting each exactly once. A generator turns exponentiation into a scrambler: the map a \mapsto g^a \bmod p touches every element, in an order that looks like static.

That map is the paint.

The protocol

Everything on the left of the arrows is public; each party keeps one number private.

\begin{aligned} &\textbf{Public, agreed in the open:} \quad \text{a prime } p, \ \text{a generator } g \\[6pt] &\text{Alice: picks secret } a, \ \text{sends } A = g^a \bmod p \\ &\text{Bob: picks secret } b, \ \text{sends } B = g^b \bmod p \\[6pt] &\text{Alice computes } s = B^a \bmod p \\ &\text{Bob computes } s = A^b \bmod p \end{aligned}

They get the same s, and the proof is one line — exponents stack multiplicatively, and multiplication of integers commutes:

B^a = (g^b)^a = g^{ba} = g^{ab} = (g^a)^b = A^b \pmod{p}

Both sides have built g^{ab} \bmod p. Neither ab nor s was ever transmitted. Eve's transcript contains exactly four numbers — p, g, A, B — and her problem is to conjure g^{ab} out of g^a and g^b, without knowing a or b.

Run it once with the toy numbers, because watching it work does something reading can't:

\begin{aligned} p &= 23, \quad g = 5 \\ \text{Alice: } a = 6 &\;\longrightarrow\; A = 5^{6} \bmod 23 = 8 \\ \text{Bob: } b = 15 &\;\longrightarrow\; B = 5^{15} \bmod 23 = 19 \\[6pt] \text{Alice: } s &= 19^{6} \bmod 23 = 2 \\ \text{Bob: } s &= 8^{15} \bmod 23 = 2 \quad \checkmark \end{aligned}

Two strangers, four public numbers, one shared secret. This exact exchange — random safe prime, random generator, fresh secrets — runs live in the Diffie-Hellman playground on this site. Set it to 8-bit primes and you can verify every line with pen and paper; set it to 62-bit and you can feel the door close.

The asymmetry, measured

Everything above says the protocol is correct. Correct is cheap. The value is in the asymmetry: how expensive is playing Alice, versus how expensive is playing Eve?

Alice's job is easy in a precise sense. Computing g^a \bmod p for a huge exponent a does not take a multiplications, because exponents decompose along their binary digits. Take a = 13 = 1101_2:

\begin{aligned} 5^1 &= 5 \\ 5^2 &= 25 \equiv 2 && \text{(square)} \\ 5^4 &\equiv 2^2 = 4 && \text{(square)} \\ 5^8 &\equiv 4^2 = 16 && \text{(square)} \\[6pt] 5^{13} &= 5^8 \cdot 5^4 \cdot 5^1 \equiv 16 \cdot 4 \cdot 5 = 320 \equiv 21 && \pmod{23} \end{aligned}

Square repeatedly, multiply together the powers where the binary digit is 1. That's square-and-multiply: about \log_2 a squarings plus at most as many multiplications, O(\log a) work in total. For a 2048-bit exponent that's roughly three thousand modular multiplications. Your phone does it in less time than it takes the photons of this sentence to reach your eye.

Eve's job is the discrete logarithm problem: given g and A = g^a \bmod p, find a. And here the floor drops out. The scrambler property of generators — powers of g visiting the group in static-shaped order — means there's no visible structure to exploit: knowing g^6 = 8 tells you nothing obvious about where g^7 landed. The naive attack is to try exponents one by one: O(p) work. The classic clever attacks — baby-step giant-step, Pollard's rho — get that down to O(\sqrt{p}) by a meet-in-the-middle trick, and Victor Shoup proved in 1997 that for a generic group (one whose elements you can only multiply and compare, with no further structure) \sqrt{p} is a floor, not a plateau: no generic algorithm does better.

\mathbb{Z}_p^{\times} is not perfectly generic — its elements are integers, and integers have factorizations. Index calculus exploits that, and its best refinement, the general number field sieve, computes discrete logs mod p in subexponential time:

L_p\!\left[\tfrac{1}{3},\, 1.923\right] = \exp\!\Big( (1.923 + o(1)) \cdot (\ln p)^{1/3} \, (\ln \ln p)^{2/3} \Big)

Subexponential is a real crack in the wall. It's why mod-p groups need 2048-bit primes while elliptic curves (same protocol, different group, no index calculus known) get away with 256. But plug in a 2048-bit p and the formula still spits out on the order of 2^{110} operations. The sun will retire first.

So the asymmetry is: O(\log p) to participate, about 2^{110} to eavesdrop. Alice's side grows linearly in the bit-length of the prime; Eve's grows like a weed. Making the honest work slightly harder makes the dishonest work astronomically harder. That's the economic engine of public-key cryptography, stated as two complexity bounds.

Saying "hard" like you mean it

A rigorous essay owes you precision about what, exactly, we're assuming. There are three distinct statements, in strictly increasing order of demand:

• DLP — given g^a, finding a is infeasible.
• CDH (computational Diffie-Hellman) — given g^a and g^b, computing g^{ab} is infeasible. This is what Eve actually needs to do; nobody said she has to recover a on the way. Break DLP and CDH falls immediately (recover a, compute B^a like Alice does). Whether CDH could survive a DLP break in some group is open — the implication is only known one way.
• DDH (decisional Diffie-Hellman) — given g^a, g^b and a candidate value, you can't even tell g^{ab} apart from a random group element. This is the assumption you want when the shared secret feeds a key derivation: not merely "Eve can't compute the key" but "the key looks like noise to her."

The twist: DDH is flat-out false in \mathbb{Z}_p^{\times}, and you can see it leak. Exactly half the elements of \mathbb{Z}_p^{\times} are squares — quadratic residues — namely the even powers of g. Euler's criterion gives a cheap test: A^{(p-1)/2} \bmod p is 1 if A is a residue and p - 1 (that is, -1) if it isn't. But A = g^a is a residue precisely when a is even — so this one exponentiation hands Eve the parity of a. Same for b. And the parity of a and b determines whether ab is even, i.e. whether g^{ab} is a residue. Eve can't compute the shared secret, but she can check whether a candidate has the right residue-status: one honest bit of the secret, leaked, and DDH is dead as stated.

The repair is standard and elegant: pick a safe prime, p = 2q + 1 with q also prime, and run the protocol inside the subgroup of quadratic residues — which has prime order q, no subgroups, no residue test to leak anything. In that subgroup DDH is believed to hold, and "believed" here means: decades of motivated cryptanalysts, no progress. (The playground generates safe primes for exactly this reason — watch the prime it hands you: (p-1)/2 is always prime too.)

How it actually breaks

None of the ways Diffie-Hellman fails in practice involve computing discrete logarithms. That's worth a moment of respect: the math holds; the surroundings give way.

The protocol authenticates nobody. Diffie-Hellman gets you a shared secret with someone — it says nothing about who. Mallory sits in the middle, runs one honest exchange with Alice and another with Bob, and relays traffic between them, decrypting and re-encrypting as it passes through her hands. Every message arrives intact; every byte is read. The fix isn't better math, it's identity: TLS pairs the exchange with certificates and digital signatures, so you're doing Diffie-Hellman with a party who can prove which key they hold. Unauthenticated key exchange is a handshake with a ghost.

Unvalidated inputs. If Bob accepts any A without checking it, Mallory can send him an element of small order — in a non-safe-prime group, one whose powers cycle through just a handful of values — and confine the "shared secret" to a space she can search by lunch. Small-subgroup attacks are why standards say, in bold, validate public keys. Prime-order subgroups make the problem mostly vanish; checking is still hygiene.

Everyone standing under the same wall. The GNFS's cost structure has a quirk: most of the work depends only on p, not on the specific logarithm you want. Precompute for one prime, and every exchange using that prime falls cheaply afterward. The 2015 Logjam attack weaponized this — a huge fraction of the internet's servers shared a few fixed 512-bit "export-grade" primes, so one precomputation broke them wholesale. Moral: hardness assumptions are per-group, and a group the whole world shares is a group worth a nation-state's precomputation budget.

There's also a gift hiding in the protocol's statelessness: nothing stops you from picking fresh secrets a and b for every session and discarding them afterward. Do that — ephemeral Diffie-Hellman, the E in TLS's DHE and ECDHE — and even a catastrophe that leaks a server's long-term keys tomorrow cannot decrypt traffic recorded today. The secrets that built each session key no longer exist. It's called forward secrecy, and it's the reason ephemeral DH is the default posture of the modern web: the exchange your browser ran to fetch this page was almost certainly an elliptic-curve Diffie-Hellman over Curve25519 — same script as above, performed in a group of points on a curve instead of integers mod p, immune (so far) to index calculus, secrets a mere 32 bytes long.

Go lose to a 62-bit prime

Fifty years old this year, and the idea hasn't aged a day: agree on a scrambler in public, each throw a private exponent into it, and let commutativity hand you both the same secret while the transcript hands Eve a problem with a \sqrt{p}-shaped wall in front of it. Correctness is a one-line identity; security is two carefully stated assumptions; the failures are all in the surroundings — identity, validation, shared parameters — where engineering lives.

But don't take the essay's word for the wall. Open the playground, run an exchange with an 8-bit prime, and crack it by hand — with p = 167 you're at most 164 guesses from glory, and it feels great. Then set it to 62 bits and try again. Somewhere around the fortieth wrong guess, with 4 quintillion candidates left, you'll have learned the discrete logarithm problem the way Eve knows it: not as a definition, but as a wall with your handprints on it.