The Diffie-Hellman key exchange explained

For thousands of years, sending a secret message meant first sharing a secret key in person or by courier. In 1976 two researchers at Stanford showed that two parties could create a shared key out of thin air, by exchanging messages in full view of anyone. The idea opened the era of public key cryptography and is still at work every time a browser shows a padlock.

Alice and Bob on either side of a public channel, each mixing a common yellow paint with a secret colour, both ending with the same blend while Eve watches
Alice and Bob on either side of a public channel, each mixing a common yellow paint with a secret colour, both ending with the same blend while Eve watches

The key distribution problem

A cipher like AES is only as safe as its key, and both sides need the same key. Before 1976 the key had to be delivered secretly: by diplomatic bag, trusted courier or code books printed in advance. For two strangers who want to talk securely right now, for example a shop and a customer on the internet, that is impossible. Whitfield Diffie and Martin Hellman's paper New Directions in Cryptography solved the problem with a method that needs no prior secret at all.

Arithmetic on a clock

The exchange uses modular arithmetic: calculations on a clock with p hours, where p is a large prime. Powers on this clock behave in a remarkable way. If g is a primitive root, the numbers g, g², g³, … mod p jump around and visit every hour from 1 to p − 1 before repeating, in an order that looks random. Computing gᵃ mod p is fast, with about as many multiplications as a has binary digits. Undoing it is not.

The exchange step by step

Alice and Bob agree openly on p and g. Alice chooses a secret a and sends A = gᵃ mod p; Bob chooses a secret b and sends B = gᵇ mod p. Alice computes Bᵃ = (gᵇ)ᵃ and Bob computes Aᵇ = (gᵃ)ᵇ, both mod p. Because the order of exponents does not matter, both get g^(ab) mod p. With the classic small example p = 23, g = 5, a = 6 and b = 15, Alice sends 8, Bob sends 19, and both arrive at the shared secret 2.

The discrete logarithm problem

Eve sees p, g, A and B. If she could find a from A = gᵃ mod p, she could compute the secret just as Alice does. This is the discrete logarithm problem. The best known classical algorithms, such as the number field sieve, are far faster than trying every exponent but still need time that grows faster than any power of the number of digits. With primes of 2048 bits the problem is out of reach for any computer that exists. Whether something faster is possible is unknown, and the security of the exchange rests on that belief.

Man in the middle

Diffie-Hellman protects against a listener but not against an impostor. Mallory, sitting between Alice and Bob, can run one exchange with each of them and pass messages along, reading everything. The defence is authentication: in HTTPS the server signs its part of the exchange with a key certified by a trusted authority, so the browser knows it is really talking to the right site. Key exchange and signatures always go together.

Who invented it?

Diffie and Hellman published in 1976, building on ideas of Ralph Merkle, whom Hellman later asked to be credited too. In 1997 the British intelligence agency GCHQ revealed that its mathematicians had got there first: James Ellis had the idea of public key cryptography in 1970, Clifford Cocks found an RSA-like system in 1973, and Malcolm Williamson discovered the same key exchange in 1974, all kept secret for over twenty years.

Martin Hellman (left) and Whitfield Diffie (right), 1977
Martin Hellman (left) and Whitfield Diffie (right), 1977
Ralph Merkle at the Singularity Summit in 2007.
Ralph Merkle at the Singularity Summit in 2007.

Diffie-Hellman today

Modern connections mostly use elliptic curve Diffie-Hellman, which gives the same security with much shorter numbers, for example the curve X25519 in TLS 1.3, Signal and WhatsApp. Using a fresh pair of secrets for every connection gives forward secrecy: even if a server's long-term key is stolen later, past conversations stay safe. Weak parameters remain a danger, as the Logjam attack of 2015 showed for old 512-bit primes, and a large quantum computer running Shor's algorithm would break both classic and elliptic curve Diffie-Hellman, which is why post-quantum key exchanges are now being deployed alongside them.

Explore it

Open the Diffie-Hellman visualizer to follow the five steps on a board of what Alice, the public channel and Bob know, as paint and as numbers. Choose primes from 23 up to 2,147,483,647, set the secrets yourself, and let Eve attack by trying every exponent: watch her succeed instantly on small primes and see how the estimated search time grows as the prime gets longer.

Frequently asked questions

Is Diffie-Hellman the same as RSA?

No, though both are public key methods from the 1970s. RSA, published in 1977, can encrypt and sign with a public and a private key and relies on the difficulty of factoring large numbers. Diffie-Hellman only agrees on a shared secret and relies on the discrete logarithm problem.

How big are the numbers in practice?

Classic Diffie-Hellman uses primes of at least 2048 bits, about 617 decimal digits, and often 3072 or 4096 bits. Elliptic curve versions use keys of 256 bits or so for comparable security.

Why does each extra bit double Eve's work?

A prime with one more bit is about twice as large, so there are about twice as many exponents to try. Real attacks are cleverer than trying every exponent, but their cost still grows very quickly with the size of the prime.

Why do Alice and Bob need a prime?

With a prime modulus every number from 1 to p − 1 has an inverse and primitive roots exist, so the powers of g cover all the possibilities. Safe primes, where (p − 1)/2 is also prime, are often chosen to rule out shortcuts that use small factors of p − 1.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Open the Diffie-Hellman visualizer