Alice and Bob want to send each other secret messages, but they have never met, and Eve hears everything they say. To lock messages they need a secret number that only the two of them know. How do you agree on a secret when someone is always listening?

Think of paint. Mixing two paints is easy, but nobody can pull a mixed paint apart again. Diffie-Hellman does the same thing with numbers:

Diffie-Hellman is a key exchange, not an encryption scheme: two parties agree on a shared secret over a public channel. Redux models it from the eavesdropper's side. Eve is passive: she knows the public parameters (p, g) and both public values A = g^a mod p and B = g^b mod p, and wants the shared secret s = g^ab mod p, or the message encrypted with it.

In message mode, (p,g,a,b,"TEXT"), the instance string contains both private keys and the plaintext so that Redux can run the exchange for you; the problem keeps only p, g, A, B and the ciphertext. Note that positions 3 and 4 are private keys here, and public values in Eve's-view instances (p,g,A,B).

In Diffie-Hellman, "mixing" means this: multiply together as many 2s as your secret number, divide by 59, and keep only the remainder, the amount left over. Alice's secret is 13, so she works out 2 × 2 × ... × 2 with 13 twos, which is 8,192. That is 138 × 59 with 50 left over, so Alice sends 50.

59 is a prime number: it divides evenly only by 1 and itself. That matters for the math, but you don't need the details here.

Change the secret numbers below and watch both of them land on the same shared secret.

Public: a prime p and a generator g of the multiplicative group mod p (here 2 has order 58 = p − 1, so its powers run through every value 1 ... 58). Alice picks a, sends A = g^a mod p; Bob picks b, sends B = g^b mod p. Both compute s = g^ab: Alice as B^a, Bob as A^b.

Recovering a from (p, g, A) is the discrete logarithm problem (DLP). Computing g^ab from g^a and g^b is the computational Diffie-Hellman problem (CDH); solving the DLP solves CDH, and no better route is known for well-chosen groups.

Now Alice and Bob share the secret 40, and Eve doesn't. Alice turns each letter into a number (A = 1, B = 2, ..., Z = 26, space = 27), multiplies it by 40, divides by 59 and sends the remainder. H is 8; 8 × 40 = 320, which is 5 × 59 with 25 left over, so H is sent as 25.

To unlock, Bob multiplies by 31 instead and keeps the remainder after dividing by 59. Why 31? Bob finds it by trying 40 × 1, 40 × 2, 40 × 3, ... until the remainder is 1: 40 × 31 = 1,240, which is 21 × 59 with 1 left over. That means multiplying by 31 undoes multiplying by 40. So 25 × 31 = 775, which is 13 × 59 with 8 left over: H again.

Type your own message below to see each letter locked.

Message mode encrypts each symbol as c = m · s mod p and decrypts with m = c · s⁻¹ mod p, where s⁻¹ = 31 (40 · 31 = 1240 = 21 · 59 + 1). Codes must stay below p, so message mode requires p > 27.

Instance checks: p ≥ 3, 1 < g < p; in Eve's view 1 ≤ A, B ≤ p − 1; in message mode 1 ≤ a, b ≤ p − 2 and only letters and spaces (lower case is accepted; the answer comes back in upper case). Whether p is prime and g a generator is not checked up front: the attacks find out, as an attacker would (section 9).

Eve knows the starting number 2, the prime 59, and Alice's mix, 50. If she can find out how many twos went into 50, she has Alice's secret, and then she can do exactly what Alice did to get the shared secret 40.

The simplest way: list the remainders of 2, 2 × 2, 2 × 2 × 2, and so on, one more two each time, until she reaches 50. Each new remainder is just the previous one doubled (taking off 59 if it goes past). Below, the list is laid out 8 to a row, so the square in row 1, column 5 is the one with 1 × 8 + 5 = 13 twos. The big number in each square is the remainder; the small one in the corner (on wider screens) counts the twos. Eve starts from 1, before any twos, so 13 twos is her 14th try. Press the button to watch her search.

The default solver in Redux's problem definition. It walks x = 0, 1, 2, ... computing g^x mod p by one multiplication per step until g^x = A, then sets s = B^x mod p and decrypts each symbol with s⁻¹. Up to p − 1 multiplications: linear in p, exponential in its bit length.

With Alice's secret, Eve rebuilds the shared secret and unlocks every letter. Press play to watch her notebook fill in. It is the same table Redux shows, with Redux's own explanations. A few row names are friendlier here: Redux says "public value" for a mix and "private key" for a secret number.

The step table below replays the solver's recorded steps for the default instance, with Redux's own text. Switch to baby-step giant-step to compare (section 6).

Here is the Diffie-Hellman page in Redux, and what each part does.

The Diffie-Hellman page (/Diffie-Hellman in Redux_Frontend). The parts below map onto Redux's problem interface: the instance, the chosen solver, the chosen visualization, and the verifier.

Checking an answer

The verifier, and why the certificate carries the key

The Result panel shows the answer and lets you check any answer you type. Redux calls a proposed answer a certificate. Here it has two parts, Alice's secret number and the message: (13,"HELLO WORLD"). Why the secret number too? Redux can't check a message on its own, because only someone who knows a secret number can make the shared secret. With Alice's secret it can: it checks that 13 twos really give 50, makes the shared secret from it, and locks your message to compare with what Eve intercepted.

The Default Diffie-Hellman Verifier checks g^a mod p = A for 0 ≤ a ≤ p − 2, then computes s = B^a mod p, re-encrypts the proposed message and compares it with c. A message or a shared secret alone could not be verified from public values: deciding whether a candidate equals g^ab is the decisional Diffie-Hellman problem (DDH), assumed hard. The private key is an efficiently checkable witness, which is why the problem is declared in NP: Diffie-Hellman = {<p, g, A, B> | some a with 0 <= a <= p - 2 has g^a = A (mod p)}.

Look at the grid again: Alice's secret is just row × 8 + column. Eve doesn't need to walk through every square to find which row and column 50 sits in. In 1971 Daniel Shanks found a shortcut, now called baby-step giant-step:

1. Baby steps: Eve works out the first row only, 8 squares: 1, 2, 4, 8, 16, 32, 5, 10.
2. Giant steps: she starts from Alice's 50 and moves up one row at a time.
   • One row down = 8 more twos = multiply by 20 (8 twos make 256, which leaves 20).
   • So one row up = undo that = multiply by 3, because 20 × 3 = 60, which leaves 1.
   So each giant step is "multiply by 3 and keep the remainder".
3. As soon as a giant step lands on a number from her first row, she knows the column, and the number of jumps is the row.

Shanks (1971). Let m = ⌈√(p − 1)⌉ = 8 and write a = i·m + j with 0 ≤ i, j < m. Store the baby steps g^j for j < m in a hash table, then compute the giant steps γ_i = A · (g^−m)ⁱ for i = 0, 1, ... until γ_i = g^j; then a = i·m + j. Here g⁻⁸ mod 59 = 3.

Cost: about 2√p multiplications and √p stored values instead of p, a square-root speed-up that is still exponential in the bit length. Pollard's rho matches the time with constant memory; Pohlig-Hellman reduces the problem to the largest prime factor of p − 1 (here 59 = 2 · 29 + 1 is a safe prime, so that factor is 29). For generic algorithms, which use only the group operation, about √q operations are necessary in a group of prime order q (Shoup, 1997), which is why elliptic-curve groups, where nothing better than generic attacks is known, need only about 256-bit keys.

59 has 2 digits, so Eve finds Alice's secret in a moment. Real primes have hundreds of digits. With the slow method, each extra digit makes the list 10 times longer. For a 40-digit prime, the slow method needs a number of tries with about 40 digits; the shortcut needs a number of steps with about 20 digits. That is a huge saving, but still hopeless for big primes. Slide to see what that means for a computer doing a billion steps every second.

Rough operation counts against the size of p in bits, constants ignored: brute force ~2^b; baby-step giant-step and Pollard's rho ~2^b/2; the number field sieve for discrete logs, the best known classical method for prime fields, ~exp(1.923 (ln p)^1/3 (ln ln p)^2/3), the same shape as for factoring; Shor's algorithm ~b³ quantum gates. The vertical axis is logarithmic: each gridline is 10²⁰ times the one below.

A quantum computer works by the rules of very tiny particles. For most jobs it isn't faster than a normal computer, but for a few special puzzles it is enormously faster. Unmixing Diffie-Hellman's numbers is one of them.

In 1994 Peter Shor found the method, now called Shor's algorithm (an algorithm is a step-by-step method). A big enough quantum computer running it could find Alice's secret from the numbers Eve sees, even for the sizes used today. Today's quantum computers are much too small and make too many errors to break real Diffie-Hellman, but people are already switching to new kinds of locks that quantum computers can't pick easily. The elliptic-curve versions used widely today fall to Shor's algorithm too.

Shor's algorithm (1994) solves discrete logarithms in time polynomial in log p. It evaluates f(x, y) = g^x A^y mod p = g^{x + a y} on a superposition of (x, y) and applies the quantum Fourier transform to both inputs; a measurement gives (u, v) with v ≡ a·u (mod r), where r is the order of g, so a = v · u⁻¹ mod r whenever u is invertible mod r. The same algorithm breaks elliptic-curve Diffie-Hellman, and resource estimates (Roetteler, Naehrig, Svore and Lauter, 2017) find that elliptic-curve keys need fewer qubits to break than RSA moduli of comparable classical strength. Exercise 5 in section 9 does the classical post-processing for one measurement.