Diffie-Hellman
Two people who have never met agree on a number, in public, while somebody reads every message. That sounds impossible and is arithmetic. Everything that crossed the wire is printed on this page and it still does not help her. Then the prime is made small enough that it does help her, because the security here is not a property of the protocol: it is a property of how long the search takes.
New to public-key cryptography? Start here
All of this is modular arithmetic: ordinary whole-number arithmetic where you divide by a fixed number at the end and keep only the remainder. A clock does it -- nine hours after five o'clock is two, not fourteen. Nothing here is bigger than the modulus, and nothing is a fraction.
The one operation that matters is raising a number to a power and taking the remainder. It is easy to do and, for a large enough modulus, nobody knows how to undo it: given the answer, finding the power it was raised to is the discrete logarithm problem, and the fastest known methods are still far too slow. That gap between easy forwards and hard backwards is the whole of the security.
So this is not a code that hides a message. It is a way for two people to end up holding the same number without ever sending it, which they then use as a key for something else. The page makes the modulus small at the end, and then the search is not too slow, and it stops working in front of you.
Hard, not impossible
Nothing in this topic is unbreakable, and that is a claim about these machines rather than about cryptography. Each of them rests on an operation that is cheap in one direction and expensive in the other, and expensive means a number of steps so large that doing them costs more than the secret is worth. The one-time pad is the standing exception: it is not hard to break, it is impossible, and it is impractical for almost everything, which is why the rest of this topic buys difficulty instead.
That makes every claim here a claim with a date on it. Secure means secure for this long, against someone with this much to spend, assuming nobody finds a shortcut. The machines in this topic each rest on one of those one-way operations, and each is worth asking the same question about: what exactly would an attacker have to do, and how much of it.
A shared secret, everything that was sent, and the size at which the eavesdropper wins
1 Two private numbers, neither of which crosses the wire
Each side picks a number and keeps it. Nothing on this page ever sends these, and the eavesdropper's column below never contains them.
2 What does cross it, in full
The prime and the generator are public, and so are the two mixed numbers. This is the entire conversation: four numbers, all of them visible to anybody listening.
- the prime, public
- 20,749
- the generator, public
- 5 (does not reach every residue)
- what one side sent
- 15,028
- what the other sent
- 3,679
3 The same shared secret, arrived at from both ends
Each side raises what it received to the power of what it kept. Different arithmetic on each side, and the same answer, which is the whole trick.
- one side computes
- 19,047
- the other computes
- 19,047
- do they match
- yes, and neither sent it
4 Shrink the prime until the eavesdropper wins, and count the attempts
Now make the prime small. The eavesdropper has the prime, the generator and both public numbers, and she simply tries every exponent until one fits. The attempts are counted, and the count is the only thing standing between her and the secret.
- attempts before she found one
- 317
- the exponent she used
- 317
- was it the one they picked
- yes
- the secret she ended up with
- 19,047 — the same secret
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| both sides arrive at 2 having computed different things | yes | A raised B's public to its own private, B did the mirror, and neither exponent crossed |
| the shared secret is not among the 4 numbers that crossed: 23, 5, 8, 19 | yes | an eavesdropper with all of them still has to solve for an exponent |
| the generator 5 is a primitive root of 23, so the exponent can be anything below 22 | yes | a generator of smaller order would quietly shrink the search an attacker has to do |
| the eavesdropper recovers the same secret, 2, in 6 attempts | yes | she solves for an exponent that BEHAVES like the private key, which is weaker than needing the key itself |
| a larger prime costs her more: 6 attempts at 23 against 13 at 97 | yes | the honest gap between this page and a real exchange is entirely the size of that number |
With a prime of 20,749 the eavesdropper tried 317 exponents before one fitted. Everything she used is in the rows above. A real exchange uses a prime of two thousand bits and the same search does not finish.
What is real here, and what is not
These primes are toys, and the real ones are unimaginably larger
Everything here fits in a browser's ordinary numbers, so the largest prime on the slider is six figures. A modern finite-field exchange uses a prime of two thousand bits or more, and RFC 7919's groups start at 2048. Much key agreement now uses elliptic curves instead, which this page does not model. The arithmetic is the same and the size is not the whole of it: the search Eve runs here is exhaustion, which is the attack small enough to watch and not the best one known, and the page's own next stage shows that the exponent's search space and the generator's order matter as well as the size of the prime.
The eavesdropper does not need your private key, only one that behaves like it
When the generator does not reach every residue, several exponents produce the same public value, and any of them reproduces the shared secret. The readout says whether she recovered the number that was actually chosen or merely an equivalent one, because on some of these primes she recovers an equivalent one and it works just as well. That is why the order of the generator matters as much as the size of the prime.
A small private exponent is found instantly, whatever the prime is
Brute force counts up from one, so an exchange that keeps a small number is broken in as many attempts as that number, on a prime of any size. Drag the private sliders down and watch the attempt count collapse while the prime stays put. The security needs the exponent to be large and unpredictable, not just the prime to be large.
There is no authentication here at all
This is the exchange as the 1976 paper describes it, and it establishes a shared secret with whoever is on the other end. It does not establish who that is. An attacker who can change messages rather than only read them can run the exchange twice, once with each side, and sit in the middle of it. Diffie and Hellman knew: the same paper spends its section IV on what it calls the one-way authentication problem, and asks for a public file of keys “protected from unauthorized modification”. What is missing here is the answer, not the question. None of the machinery that came to supply it, certificates and signed key exchanges, is on this page.