How Does Diffie-Hellman Key Exchange Work? Secrets Agreed in Public

In 1976 the practical problem in cryptography was not encryption. Good ciphers existed. The problem was that two parties could use one only if they already shared a key, and sharing a key meant couriers and codebooks printed in advance: a bank with a thousand correspondent branches needed a thousand keys delivered by hand. Whitfield Diffie and Martin Hellman’s answer, published that November, was that two strangers can agree on a shared secret while conducting the entire negotiation in public.

Here is how Diffie-Hellman key exchange works. The two parties publicly agree on a large prime $p$ and a base $g$ . Alice chooses a secret integer $a$ and transmits $A = g^a \bmod p$ . Bob chooses a secret integer $b$ and transmits $B = g^b \bmod p$ . Each then raises the value they received to their own secret exponent: Alice computes $B^a = (g^b)^a = g^{ab}$ , Bob computes $A^b = (g^a)^b = g^{ab}$ , both reduced modulo $p$ . They now hold the same number, and neither of them ever transmitted it. The eavesdropper has $p$ , $g$ , $A$ and $B$ , and from those four quantities there is no known efficient way to reach $g^{ab} \bmod p$ .

The whole protocol rests on a single asymmetry. Computing $g^a \bmod p$ from $a$ is cheap: a few thousand multiplications even for a number with hundreds of digits. Recovering $a$ from $g^a \bmod p$ is the discrete logarithm problem, and no known algorithm does it in reasonable time for well-chosen parameters. Exponentiation is a one-way street. The rest of this article verifies that claim, catalogues the ways implementations get it wrong, and says honestly how much we actually know about the hardness.

A complete exchange with numbers you can check

Take $p = 23$ and $g = 5$ , both public — an attacker is assumed to know them from the start, and in real deployments they come from a standards document. Let Alice’s secret be $a = 6$ and Bob’s be $b = 15$ .

Alice computes $5^6 \bmod 23$ . Rather than forming $15625$ , reduce as you go: $5^2 = 25 \equiv 2$ , so $5^4 \equiv 2^2 = 4$ , and $5^6 = 5^4 \cdot 5^2 \equiv 4 \cdot 2 = 8$ . So $A = 8$ .

Bob computes $5^{15} \bmod 23$ . From the same partial results $5^8 \equiv 4^2 = 16$ , and $5^{15} = 5^8 \cdot 5^4 \cdot 5^2 \cdot 5 \equiv 16 \cdot 4 \cdot 2 \cdot 5$ : here $16 \cdot 4 = 64 \equiv 18$ , then $18 \cdot 2 = 36 \equiv 13$ , then $13 \cdot 5 = 65 \equiv 19$ . So $B = 19$ .

Now the shared value. Alice raises Bob’s number to her own secret: $19^6 \bmod 23$ . Since $19 \equiv -4$ , we get $19^2 \equiv 16$ , $19^4 \equiv 16^2 = 256 \equiv 3$ , and $19^6 \equiv 3 \cdot 16 = 48 \equiv 2$ . Bob raises Alice’s number to his: $8^{15} \bmod 23$ . Because $8 = 5^6$ here, $8^{15} = 5^{90}$ , and the order of $5$ modulo $23$ is $22$ , so $5^{90} = 5^{88} \cdot 5^2 \equiv 5^2 \equiv 2$ . Both arrive at $2$ .

Quantity	Alice	Bob	What the eavesdropper sees
Public parameters	$p = 23$ , $g = 5$	$p = 23$ , $g = 5$	$p = 23$ , $g = 5$
Private exponent	$a = 6$	$b = 15$	nothing
Transmitted value	$A = 5^6 \equiv 8$	$B = 5^{15} \equiv 19$	$8$ and $19$
Received value	$19$	$8$	—
Own computation	$19^6 \equiv 2$	$8^{15} \equiv 2$	cannot perform it
Shared secret	$2$	$2$	unknown

The right-hand column is the one that matters pedagogically. The eavesdropper knows $23$ , $5$ , $8$ and $19$ . She does not know $6$ or $15$ , and she cannot combine $8$ and $19$ into $2$ by any group operation available to her: $8 \cdot 19 = 152 \equiv 14$ , which is $g^{a+b}$ , not $g^{ab}$ . Multiplying the public values gives the sum of the exponents, not the product, and the sum is useless. To get the product she needs an exponent itself — which with $p = 23$ she obtains instantly, by trying all 22 powers of 5. That is the entire difficulty: nothing in the structure resists brute force, so security comes only from an enormous search space. Real deployments use $p$ of 2048 bits or more, or elliptic curve groups where 256 bits suffice.

Why exponentiation is cheap: square-and-multiply

Computing $g^a \bmod p$ by multiplying $g$ by itself $a - 1$ times is hopeless when $a$ has 256 bits. The standard method instead reads the binary expansion of the exponent from left to right, squaring at every bit and multiplying by $g$ whenever the bit is 1.

Take $g = 7$ , $p = 101$ , $a = 45$ . In binary, $45 = 101101_2$ . Start with $x = 1$ and process the bits:

Bit	$x$ before	After squaring	After multiplying by 7 if bit is 1
1	$1$	$1$	$7$
0	$7$	$49$	$49$
1	$49$	$78$	$41$
1	$41$	$65$	$51$
0	$51$	$76$	$76$
1	$76$	$19$	$32$

So $7^{45} \equiv 32 \pmod{101}$ . Spot-check row three: $49^2 = 2401$ and $2401 - 23 \cdot 101 = 78$ . The exponent accumulates as the bits are consumed — after three bits it is $101_2 = 5$ , and indeed $7^5 = 16807 \equiv 41 \pmod{101}$ , the value in that row.

The cost is one squaring per bit plus one multiplication per 1-bit: at most $2\log_2 a$ modular multiplications, on average about $1.5 \log_2 a$ . Here that is 10 non-trivial operations against 44 for naive repeated multiplication; for a 2048-bit exponent it is roughly 3000 instead of $2^{2048}$ . In the language of asymptotic analysis, exponentiation is $O(\log a)$ group operations while the naive method is $O(a)$ — exponential in the length of the input. That gap is what makes public-key cryptography possible at all.

The discrete logarithm problem

Work in the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^\times$ , the nonzero residues modulo a prime $p$ . This group is cyclic of order $p - 1$ , so some $g$ generates it and every nonzero residue is a power of $g$ . The discrete logarithm problem is: given $g$ and $h$ with $h \equiv g^x \pmod p$ , find $x$ .

Over the positive reals the analogous problem is trivial, because $t \mapsto g^t$ is increasing, so you can bisect. Modulo $p$ that structure is destroyed. The powers of 5 modulo 23, in order of exponent, run $5, 2, 10, 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, 3, 15, 6, 7, 12, 14, 1$ . Knowing $5^6 = 8$ tells you nothing about where $9$ sits. There is no order to exploit and no gradient to follow.

What is actually known about the cost? Two families of algorithms matter. Generic algorithms treat the group as a black box with only multiplication available, and the best of these — baby-step giant-step, and Pollard’s rho for logarithms — run in time $O(\sqrt{n})$ for a group of order $n$ , using either $O(\sqrt n)$ storage or almost none. Baby-step giant-step is the easy one to see: write $x = i\lceil\sqrt n\rceil + j$ , tabulate $g^{j}$ for $j$ up to $\sqrt n$ , then scan over $i$ for a match. The square-root bound is provably optimal for generic algorithms, which is why a 256-bit elliptic curve group gives about 128 bits of security.

For the integers modulo $p$ , however, the group is not a black box: residues have arithmetic structure, and index-calculus methods exploit it. The best known algorithms here are variants of the number field sieve, with conjectural sub-exponential running time of the form $L_p[1/3, c] = \exp\!\big((c + o(1))(\log p)^{1/3}(\log\log p)^{2/3}\big),$ with $c = (64/9)^{1/3} \approx 1.923$ for general primes; multiple-field variants have shaved the constant to about $1.902$ . Sub-exponential is much faster than $\sqrt p$ , which is exactly why prime-field Diffie-Hellman needs 2048-bit moduli while elliptic curves get away with 256 bits.

Now the honest part. No one has proved that the discrete logarithm problem is hard. There is no theorem saying it cannot be solved in polynomial time; the bounds above describe the best algorithms anyone has found, not a floor on what is findable. A proof of hardness would resolve questions at least as deep as P versus NP. The security of Diffie-Hellman is therefore a conjecture backed by fifty years of concerted and unsuccessful attack, not a mathematical guarantee. This is the same epistemic position as RSA, whose security rests on the unproved hardness of integer factoring, and indeed as essentially all of deployed public-key cryptography.

What the protocol actually needs: a finite cyclic group

Read the protocol again and notice how little of it is about integers. Alice sends $g^a$ , Bob sends $g^b$ , both compute $g^{ab}$ . The only facts used are that exponentiation is well defined and that it commutes in the exponent, $(g^a)^b = (g^b)^a$ . The integers modulo $p$ are one setting; they are not the setting.

The abstract requirement is a finite cyclic group, written multiplicatively, in which exponentiation is cheap and the discrete logarithm problem is hard. (Strictly, security needs the computational Diffie-Hellman assumption — that $g^{ab}$ is hard to compute from $g^a$ and $g^b$ — and for most protocol proofs the stronger decisional version.) Any structure meeting those conditions gives the same protocol, which is a textbook illustration of what group theory buys you: the proof of correctness is three lines of exponent arithmetic and never mentions what the elements are.

The practically important instantiation is the group of points on an elliptic curve over a finite field. There, point addition plays the role of multiplication, repeated addition the role of exponentiation, and the discrete logarithm problem has resisted index-calculus attacks, so only the generic $O(\sqrt n)$ algorithms apply. That is why elliptic-curve Diffie-Hellman achieves comparable security with parameters an eighth the size, and why it carries most internet traffic today. The protocol is identical; only the group changed.

Parameters, safe primes, and why the raw shared value is not a key

A correct protocol with careless parameters is insecure, and Diffie-Hellman has several such traps.

First, the base $g$ must generate a large subgroup. The order of $g$ divides $p - 1$ , and the exchange takes place inside the subgroup $g$ generates; if that subgroup has order 11, the attacker searches 11 possibilities. By Pohlig and Hellman’s algorithm, a discrete logarithm in a group of order $n = \prod q_i^{e_i}$ collapses to the hardest prime-power factor: solve it in each small factor and glue the answers with the Chinese remainder theorem. A group order that is a product of small primes is worthless no matter how large $p$ is.

The standard defence is a safe prime, $p = 2q + 1$ with $q$ also prime. Then $p - 1 = 2q$ has only the factors 2 and $q$ , so every element other than $1$ and $-1$ generates a subgroup of order $q$ or $2q$ and Pohlig-Hellman gains nothing beyond one bit. Our toy modulus has this shape: $23 = 2 \cdot 11 + 1$ with $11$ prime, and $5$ has order 22, the full group.

Second, unvalidated inputs invite small-subgroup confinement. Suppose Alice, instead of a legitimate $g^a$ , sends $22 \equiv -1$ modulo 23, an element of order 2. Then Bob computes $22^b \bmod 23$ , which is $1$ when $b$ is even and $22$ when $b$ is odd; with $b = 15$ it is $22$ . His shared secret now takes one of two values, and which one it is reveals the parity of his exponent. Repeat with elements of other small orders and the attacker extracts the secret piece by piece. The defence is to reject received values outside the expected subgroup — check that the received $Y$ satisfies $Y \neq 0, \pm 1$ and $Y^q \equiv 1 \pmod p$ — or to use a group whose structure makes the check unnecessary, as X25519 does by design.

Third, and routinely misunderstood: $g^{ab} \bmod p$ is not a key. A uniformly distributed group element is not a uniformly distributed bit string. A prime-field element is a number below $p$ , so some leading bit patterns are impossible; it is always a quadratic residue when the subgroup has prime order $q$ , so its Legendre symbol is predictable; and its 2048 bits carry only the entropy of the exponent. Feeding such a structured object into a block cipher as key material is exactly the mismatch that breaks security proofs. The shared value is therefore run through a key-derivation function, typically HKDF built on hash functions, which extracts the entropy into an indistinguishable-from-random key of the right length while binding in transcript data.

The man-in-the-middle attack

Everything so far concerns a passive eavesdropper. Against an attacker who can modify traffic, plain Diffie-Hellman fails completely, and this is the point most short explanations skate over.

The protocol authenticates nothing: Alice receives a number and has no way to know it came from Bob. So let Mallory sit on the wire. Alice sends $A = g^a$ ; Mallory intercepts it, picks his own secret $m$ and sends $M = g^m$ to Bob. Bob, seeing a well-formed public value, replies with $B = g^b$ ; Mallory intercepts that too and sends $M$ to Alice. Alice computes $M^a = g^{ma}$ , Bob computes $M^b = g^{mb}$ , and Mallory computes both, as $A^m$ and $B^m$ . He now shares one key with Alice and a different key with Bob. Every message Alice encrypts, he decrypts, reads, optionally alters, re-encrypts under Bob’s key and forwards. Both endpoints see a session that works, and nothing in the mathematics is violated: the protocol did what it promises, which is to establish a shared secret with whoever is at the other end of the wire.

In our toy numbers, Mallory with $m = 9$ sends $5^9 \equiv 11$ to both sides; Alice derives $11^6$ , Bob derives $11^{15}$ , and Mallory derives the same two as $8^9$ and $19^9$ modulo 23. Two encrypted sessions, both readable by him.

The fix is not a better group but authentication: the exchange must be tied to something an attacker cannot forge. Either the public values are signed with a long-term key whose ownership is attested by a certificate chain, or both parties mix a pre-shared secret or password into the derivation, as password-authenticated key exchange protocols do. This is the entire reason TLS certificates exist. The certificate encrypts nothing; it asserts that the party signing these Diffie-Hellman values controls the name on it. A browser’s invalid-certificate warning says precisely that the attack above cannot be ruled out. For the adjacent problem of proving you know a secret without revealing it, see zero-knowledge proofs.

Perfect forward secrecy and ephemeral Diffie-Hellman

Ephemeral Diffie-Hellman means generating a fresh pair $(a, g^a)$ for every session and destroying the secret exponent afterwards. The long-term key signs the ephemeral values; it never derives them. The cipher suite names DHE and ECDHE carry an E for exactly this.

The payoff is perfect forward secrecy. An adversary records a session today and five years from now compromises the server and extracts its long-term private key. He can impersonate the server going forward, but he cannot decrypt the recording: the session key came from $a$ and $b$ , which lived in memory for the duration of the handshake and are gone. There is no mathematical path from the signing key to the session key, because the signing key never touched the derivation.

Contrast static RSA key transport, the dominant TLS mode for years. There the client picks the session secret, encrypts it under the server’s long-term RSA public key, and sends it; the ciphertext travels on the wire, where it can be recorded. Anyone who later obtains the server’s private key decrypts that ciphertext and recovers the entire conversation — retroactively, for every session ever recorded under that key. One key compromise, years of traffic. That is why mass traffic retention was a rational strategy for a well-resourced adversary, and why forward secrecy became a requirement.

TLS 1.3, specified in RFC 8446, resolved this by amputation. Static RSA and static Diffie-Hellman cipher suites were removed from the protocol, so every key exchange mechanism it offers provides forward secrecy. RSA survives there only as a signature algorithm. Key agreement is ephemeral, full stop.

Logjam: when everyone shares the same prime

The theory can be sound and the deployment still broken. In May 2015 a team of fourteen researchers — among them David Adrian, Karthikeyan Bhargavan, Pierrick Gaudry, Matthew Green, J. Alex Halderman, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann — published Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice, describing the Logjam attack.

Two observations combined. The first was legacy: 1990s United States export regulations had left many servers willing to negotiate deliberately weakened 512-bit export-grade Diffie-Hellman groups, and a man-in-the-middle could rewrite the handshake to force both sides onto that group unnoticed, because the messages carrying the group parameters were not adequately protected.

The second is the mathematically interesting one. The number field sieve splits into a precomputation stage that depends only on the prime $p$ , and a cheap individual-logarithm stage that depends on the target. Break the precomputation once for a given prime and every subsequent discrete logarithm in that prime’s group becomes fast. Meanwhile implementations did not generate fresh primes; they shipped a handful of hard-coded ones, and the team reported that a single 512-bit prime covered the great majority of vulnerable servers supporting the export suites. One expensive computation, amortised across most of the affected internet. Their estimates extended the argument upward: a well-funded academic effort could manage 768 bits, and a nation-state could plausibly afford the precomputation for a small number of 1024-bit groups, after which those groups would fall in close to real time. The recommendation was 2048 bits or more, with the reuse of standard primes treated as the structural problem. The general lesson: a computation too expensive to mount against one connection may be affordable when a hundred million connections share one parameter set.

Who invented it, and when

Diffie and Hellman’s paper, New Directions in Cryptography, appeared in the IEEE Transactions on Information Theory, volume IT-22, number 6, November 1976, pages 644 to 654. It introduced public-key cryptography, described the key exchange, and posed the digital signature problem that RSA would answer the following year.

Ralph Merkle’s contribution belongs in the account. His work on public key distribution was cited in the paper as a submitted manuscript, he is named alongside Diffie and Hellman on the resulting patent, and Hellman has publicly argued that the scheme should be called Diffie-Hellman-Merkle key exchange, since the concept of public key distribution was Merkle’s. The shorter name has stuck anyway. In March 2016 the Association for Computing Machinery awarded Diffie and Hellman the 2015 A. M. Turing Award for inventing public-key cryptography.

There is also a prior history, classified at the time. At the British signals agency GCHQ, James Ellis conceived what he called non-secret encryption, writing it up in an internal report dated January 1970; he had an existence proof but no practical construction. Clifford Cocks, who joined the agency in 1973, found a workable scheme that year which amounts to RSA. Malcolm Williamson, a school friend of Cocks who had joined around the same time, found a scheme equivalent to Diffie-Hellman key exchange — sources place this in 1974, with some giving 1973. All of it stayed secret until GCHQ declassified the work in December 1997, by which time the public algorithms had been deployed worldwide for two decades. Ellis died in November 1997, weeks before the announcement.

State the attribution carefully. The classified discoveries were earlier and genuine. The public ones were independent — Cocks himself has said there is no evidence of any leak — and they were the ones that changed anything, because an idea kept in a safe secures neither a bank’s correspondent network nor anybody’s web browser.

The quantum caveat

Shor’s algorithm, published in 1994, solves integer factoring and the discrete logarithm problem in polynomial time on a sufficiently large quantum computer. The discrete logarithm case applies to prime-field and elliptic-curve Diffie-Hellman alike; elliptic curves, whose advantage against classical attack is the absence of index calculus, gain nothing here. The one-way street becomes two-way.

The machine does not exist. Current hardware is many orders of magnitude short in both qubit count and error rate of what breaking 2048-bit or 256-bit parameters requires, and nobody can responsibly predict when or whether it will arrive. The threat is nevertheless live, for one reason: recorded traffic. An adversary storing ciphertext now can decrypt it whenever the machine appears — the harvest-now-decrypt-later problem.

The response is key encapsulation mechanisms built on different mathematics. NIST standardised ML-KEM, the module-lattice scheme derived from Kyber, as FIPS 203 in August 2024; its security rests on lattice problems Shor’s algorithm does not address. Deployment has gone hybrid rather than wholesale: browsers and content delivery networks negotiate combinations such as X25519MLKEM768, which runs an elliptic-curve Diffie-Hellman exchange and an ML-KEM encapsulation together and derives the session key from both, so that an attacker must break both. Chrome shipped the ML-KEM form of this hybrid in late 2024 and major CDNs support it. The hedge is deliberate: lattice cryptography is young, and nobody wants to stake the internet on one new assumption.

Fifty years on, the asymmetry Diffie and Hellman exploited is still unproved, still unbroken classically, and now provably breakable by a machine nobody has built — an unusual combination of certainties, and a fair description of where applied cryptography stands.

Frequently asked

How does Diffie-Hellman work?

Both sides publicly agree on a large prime p and a base g. Alice picks a secret exponent a and sends g^a mod p; Bob picks a secret b and sends g^b mod p. Alice raises what she received to her own secret, getting (g^b)^a; Bob does the same, getting (g^a)^b. Both are g^(ab) mod p, so both now hold the same number. An eavesdropper has seen p, g, g^a mod p and g^b mod p, and from those cannot compute g^(ab) mod p by any known efficient method. The shared number is then hashed through a key-derivation function to produce the actual encryption key.

What is the discrete logarithm problem?

Given a prime p, a base g, and a value h with h congruent to g^x mod p, the discrete logarithm problem is to find the exponent x. Over the real numbers the analogous problem is easy, because logarithms are monotone and you can binary-search; modulo p the powers of g jump around in no useful order, so there is nothing to search along. The best known general algorithms for prime fields are number field sieve variants with sub-exponential running time of the form L_p[1/3, c], and generic algorithms that work in any group, such as baby-step giant-step and Pollard rho, cost about the square root of the group order. No proof exists that the problem is intrinsically hard.

Is Diffie-Hellman secure against man in the middle?

No, not on its own. Plain Diffie-Hellman provides confidentiality against a passive eavesdropper but no authentication whatsoever. An active attacker who can modify traffic intercepts Alice's public value, substitutes his own, does the same to Bob, and ends up sharing one key with Alice and a different key with Bob. He decrypts and re-encrypts everything, and both parties see a working encrypted session. The fix is to authenticate the exchange: sign the public values with a long-term key whose authenticity is vouched for by a certificate, or mix in a pre-shared secret. That is precisely the job TLS certificates do.

What is the difference between Diffie-Hellman and RSA?

Diffie-Hellman is a key agreement protocol: neither party chooses the key, it emerges from both contributions, and the hardness assumption is the discrete logarithm problem. RSA is a trapdoor permutation usable for encryption and for signatures, and its hardness assumption is integer factoring. In practice the division of labour in modern TLS is that an elliptic-curve Diffie-Hellman exchange establishes the session key while RSA or an elliptic-curve signature scheme authenticates the parties. RSA can also be used for key transport, where the client encrypts a key to the server's public key, but that mode has no forward secrecy and TLS 1.3 removed it.

What is ephemeral Diffie-Hellman?

Ephemeral Diffie-Hellman means generating a fresh secret exponent, and therefore a fresh public value, for every session, and discarding it when the session ends. The long-term key is used only to sign the ephemeral values, never to derive them. The consequence is perfect forward secrecy: an attacker who records ciphertext today and steals the server's long-term private key next year still cannot decrypt the recording, because the session key was derived from exponents that no longer exist anywhere. In TLS the cipher suites are written DHE and ECDHE, where the E stands for ephemeral.