Diffie–Hellman: A Secret Agreed in Public

Alice sends gᵃ mod p, Bob sends gᵇ mod p, and both arrive at gᵃᵇ mod p without either of them sending it. Eve sees every number that crossed the wire. Step through the exchange, then through her attack, and change p and g to find out what makes her job short.

Worked example — Diffie–Hellman: A Secret Agreed in Public

Alice's public number	8
Bob's public number	19
The shared secret	2
Values the shared secret can take	22 of 22
Brute-force tries for this A	7 (at worst 22)
Pohlig–Hellman tries for this A	8 (at worst 13)
Eve's secret, from her x	2

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Diffie–Hellman: A Secret Agreed in Public

In a Diffie–Hellman key exchange two parties agree a secret number over a channel anyone can read. They fix a prime p and a base g in public. Each picks a private exponent, publishes g to that power mod p, and raises the other's published number to their own exponent: (gᵇ)ᵃ = (gᵃ)ᵇ = gᵃᵇ mod p. Undoing it means solving a discrete logarithm: given A = gᵃ mod p, find an x with gˣ ≡ A (mod p). Diffie and Hellman wrote in 1976 that they could see no way to get the shared secret from the public numbers without one, and had no proof that there is none. The order of g is the least n ≥ 1 with gⁿ ≡ 1 (mod p); g is a generator when its order is p − 1.

What each symbol means

p: the prime modulus, public
g: the base, public
a, b: Alice's and Bob's private exponents
A, B: their public numbers, gᵃ mod p and gᵇ mod p
x: the exponent Eve finds; any x with gˣ ≡ A works, so she finds a mod the order of g
ord(g): the order of g: how many different values the shared secret can take

Assumes: p is a prime from 5 to 1,999, g any base from 2 to p − 2, and a and b run from 1 to p − 2. A try is one comparison of a computed power with a target, and both counts include the try that succeeds. Each Pohlig–Hellman digit is found by trying its candidates in order, which is how Pohlig and Hellman describe it for a small factor; for a large one they also give a search that trades memory for time, and the page does not run it. Diffie and Hellman's own example was a prime of about 200 bits, for which they put a logarithm at around 2¹⁰⁰ operations.

At 257, the base 2 leaves only sixteen possible secrets 🖖

Press A loop of 16. 257 is prime, so A and B look as though they could be any of 256 numbers. But 2⁸ = 256, which is −1 mod 257, so 2¹⁶ = 1, and the powers of 2 go round a loop of 16: 1, 2, 4, 8, 16, 32, 64, 128, 256, 255, 253, 249, 241, 225, 193, 129. Those are the shaded cells. Whatever a and b are, gᵃᵇ is one of them, and here it is 129. Eve's brute force stops after 14 tries and can never need more than 16, and the x it finds, 13, is not Alice's 77: it agrees with it mod 16, which is all the exponent can carry. A prime modulus does not protect you from this. Of the 254 bases from 2 to 255, 126 are not generators, and two of them, 16 and 241, leave only four possible secrets. At 263, where p − 1 = 2 × 131, the order of every base from 2 to 261 is 131 or 262.

Twin primes, 811 tries against 21 🖖

Press p − 1 in small pieces. 1621 is prime and 1620 = 2² · 3⁴ · 5, so Pohlig–Hellman never searches the 1,620 powers of g. It finds a mod 4 two candidates at a time, a mod 81 three at a time and a mod 5 among five, then joins the pieces with the Chinese remainder theorem: at worst 2·2 + 4·3 + 5 = 21 tries, and 15 here, where brute force needs 1,235. Now choose 1619 in the table of primes near p. It is two smaller, and 1618 = 2 × 809: one piece of 809 candidates, at worst 811 tries, and 427 for the same a. Eve's work is set by the largest prime factor of p − 1, not by p. Over the 301 primes this page accepts, Pohlig–Hellman's worst case never exceeds that factor by more than 25, it is under a tenth of brute force's at 172 of them, and in 146 of the 300 steps from one prime to the next it goes down. Pohlig and Hellman put it flatly in 1978: when p − 1 has only small prime factors, exponentiation mod p “is not a good one-way function”.

The safer base is not a generator 🖖

Press A base of prime order. At 263 the base 2 is not a generator: its powers repeat after 131, so only 131 secrets are possible. Type g = 5, a generator, and twice as many are. Look at Pohlig–Hellman's worst case for it: 133 tries, 2 of them on the last binary digit of a, because A¹³¹ is 1 when a is even and 262, which is −1, when a is odd. A generator gives that digit away at every odd prime, since p − 1 is even. Go back to g = 2. Its order, 131, is prime, so Pohlig–Hellman has nothing to split, and its worst case is 131 tries, the same as brute force. The generator doubled the number of possible secrets and handed Eve one bit of the secret for nothing: from A and B alone she can tell whether it is a square mod 263. Every power of 2 is a square, so with g = 2 there is nothing to tell.

Problem solved in full

Recover Alice's secret at p = 101 5 steps
Alice and Bob use p = 101 and g = 2. Eve sees A = 12 and B = 53. Find an x with 2ˣ ≡ 12 (mod 101) by Pohlig–Hellman, count the tries, and use x to get the shared secret. Then say what the same attack would cost at p = 65,537.

Open this problem in the tool
1. 100 = 2² · 5², so x is fixed by x mod 4 and x mod 25. The order of 2 divides 100, and 2⁵⁰ = 100 and 2²⁰ = 95 are both different from 1, so the order is 100 itself: 2 is a generator.
  
  $100 = 2^{2} \cdot 5^{2}, 2^{50} \equiv 100, 2^{20} \equiv 95 (both \neq = 1) \Rightarrow ord (2) = 100$
2. Mod 4, γ = 2⁵⁰ = 100, which is −1. The first binary digit: 12⁵⁰ = 100, so d = 1, on the second try. Take it out: 12 · 2⁻¹ = 12 · 51 = 612 ≡ 6, and 6²⁵ = 100, so the next digit is 1 as well, again on the second try. x ≡ 1 + 1 · 2 = 3 (mod 4).
  
  $1 2^{50} \equiv 100 \Rightarrow d_{0} = 1; 12 \cdot 2^{- 1} = 12 \cdot 51 \equiv 6, 6^{25} \equiv 100 \Rightarrow d_{1} = 1; x \equiv 3 (mod 4)$
3. Mod 25, γ = 2²⁰ = 95, whose powers are 1, 95, 36, 87, 84. The first base-5 digit: 12²⁰ = 95, so d = 1, on the second try. Take it out: 6⁴ = 1,296 ≡ 84, so the next digit is 4, on the fifth try. x ≡ 1 + 4 · 5 = 21 (mod 25).
  
  $9 5^{0..4} = 1, 95, 36, 87, 84; 1 2^{20} \equiv 95 \Rightarrow d_{0} = 1; 6^{4} = 1296 \equiv 84 \Rightarrow d_{1} = 4; x \equiv 21 (mod 25)$
4. The numbers below 100 that are 21 mod 25 are 21, 46, 71 and 96, and only 71 is 3 mod 4. So x = 71, after 2 + 2 + 2 + 5 = 11 tries, where the worst case is 2·2 + 2·5 = 14. Brute force would have tried 0 to 71, 72 tries. The shared secret is 53⁷¹ mod 101 = 35.
  
  $x \in {21, 46, 71, 96}, x \equiv 3 (mod 4) \Rightarrow x = 71; 2 + 2 + 2 + 5 = 11 tries, at worst 2 \cdot 2 + 2 \cdot 5 = 14$
5. 65,537 = 2¹⁶ + 1 is prime, and p − 1 = 2¹⁶. Pohlig–Hellman takes its sixteen binary digits one at a time, two candidates each: at worst 32 tries, where brute force could need 65,536. Pohlig and Hellman worked this very case, p = 2ⁿ + 1, before the general one.
  
  $s = B^{x} = 5 3^{71} mod 101 = 35; 65537 = 2^{16} + 1 : at worst 16 \cdot 2 = 32 tries$
Answer

x = 71, after 11 tries (at worst 14), and the shared secret is 35. At p = 65,537 the attack needs at most 32 tries. The page stops at 1,999, so that figure is arithmetic and not a run.

$x = 71, 11 tries, s = 35$

Learning path

How codes are broken

References (2)

The exchange itself, the definition's sentence that its authors could see no way round a logarithm and had no proof, and the 200-bit example in `assumes`: Whitfield Diffie and Martin E. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory 22(6), 644–654, November 1976. §III, p. 649.
The second insight's quotation, the digit-by-digit search the page runs, and the worked problem's p = 2ⁿ + 1: Stephen C. Pohlig and Martin E. Hellman, "An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance," IEEE Transactions on Information Theory 24(1), 106–110, January 1978. §III–IV, pp. 107–110.

By the 42Math team · Reviewed against published sources. Corrections welcome.