Diffie-Hellman key exchange

Diffie-Hellman key exchange lets two people who have never met agree on a secret key over a channel anyone can listen to. Whitfield Diffie and Martin Hellman published it in 1976. It was the first public answer to a problem that had stalled cryptography for centuries: how do you share a key without already sharing a secret? Each side picks a private number and sends a public number derived from it. Each then combines its own private number with the other's public number, and both land on the same secret, which the listener can't compute.

Try it

Nothing here leaves your browser; secrets come from your browser's secure random number generator.

Start with the paint picture, then run the small group, p = 23 and g = 5. The standalone Diffie-Hellman tool page goes into more detail on each part.

How it works

Alice and Bob agree, in public, on a large prime p and a number g. With p = 23 and g = 5:

1. Alice picks a secret a = 4 and sends Bob A = g^a mod p = 5⁴ mod 23 = 4.
2. Bob picks a secret b = 3 and sends Alice B = g^b mod p = 5³ mod 23 = 10.
3. Alice computes B^a mod p = 10⁴ mod 23 = 18.
4. Bob computes A^b mod p = 4³ mod 23 = 18.

Both hold 18, which is g^ab mod p. Neither sent it. Each computed it from the other's public number and their own secret. An eavesdropper knows p, g, 4 and 10 and wants 18. She can get it if she can find a or b, which is a discrete logarithm. With p = 23 that takes seconds by hand. With a 2,048-bit prime (617 digits), no known algorithm can do it, and the exchange is safe. The same arithmetic runs through the three-pass protocol, the discrete logarithm tool and the treasure-chest puzzle.

History: three people, then two, then the world

Ralph Merkle, a student at Berkeley, devised a public-key scheme called Merkle's puzzles in 1974. It was impractical, but it showed the idea was possible. Diffie and Hellman, at Stanford, then published New Directions in Cryptography in 1976 with the key exchange that carries their names. Hellman has asked for it to be called Diffie–Hellman–Merkle. The paper also laid out the whole idea of public-key encryption and digital signatures, though not a working scheme for them. That came a year later as RSA. As the RSA history also shows, Britain's GCHQ had found the idea in secret a few years earlier, and it was published only in 1997. The key exchange was patented in the US (patent 4,200,770), and the patent expired in 1997.

What can go wrong

• No authentication. The exchange agrees a key with someone, not with a particular person. A man in the middle can run one exchange with Alice and another with Bob, and relay everything. Real protocols add authentication, with certificates or signatures, to prove who's at the other end.
• Weak groups. In 2015 the Logjam attack showed that servers still accepted "export-grade" 512-bit groups, and that a very large share of the internet used a few widely shared 1,024-bit primes, for which a determined attacker could precompute most of the work. The fix is a prime of at least 2,048 bits, or an elliptic curve.
• Quantum computers. Shor's algorithm computes discrete logarithms efficiently, so it breaks Diffie-Hellman in prime fields and on elliptic curves alike (post-quantum cryptography).
• Reused secrets. If a server reuses its secret, stealing it later exposes every past session. Picking a new secret every time, an ephemeral exchange, gives forward secrecy, which is why TLS uses ephemeral Diffie-Hellman.

Where it's used today

Almost every secure connection starts with a Diffie-Hellman exchange, usually on an elliptic curve (ECDH) as in TLS 1.3, SSH and Signal's key agreement. The exchange yields a shared number, and a key derivation turns it into keys for a symmetric cipher such as AES-GCM. The 2,048-bit group in the tool comes from RFC 3526. It's a safe prime defined by a formula involving the digits of π, which makes it hard to suspect that anyone chose it to hide a backdoor.

The code

// Diffie-Hellman key agreement with BigInt. p is a prime and g a generator, both public; a and b are the two secret exponents.
function modPow(base, exp, mod) {
  var result = 1n;
  base %= mod;
  while (exp > 0n) { if (exp & 1n) result = result * base % mod; base = base * base % mod; exp >>= 1n; }
  return result;
}

function exchange(p, g, a, b) {
  var A = modPow(g, a, p);              // Alice sends g^a
  var B = modPow(g, b, p);              // Bob sends g^b
  return {
    A: A, B: B,
    alice: modPow(B, a, p),             // (g^b)^a
    bob: modPow(A, b, p)                // (g^a)^b: the same number, g^(ab)
  };
}

Common questions