How Diffie–Hellman works
Whitfield Diffie and Martin Hellman's method doesn't encrypt anything by itself. It lets two people, usually called Alice and Bob, agree on a shared secret number while an eavesdropper (Eve) watches everything they send. They then use that number as the key for some other cipher.
The exchange
- Alice and Bob agree, in public, on a large prime p and a base g.
- Alice picks a secret number a and sends A = ga mod p. Bob picks a secret b and sends B = gb mod p.
- Alice computes Ba mod p, and Bob computes Ab mod p. Both get the same number, s = gab mod p, because (gb)a = (ga)b.
Being Eve
Eve sees p, g, A and B, but not a or b. To get s, she has to recover one of the secrets: a from A = ga, or b from B = gb. That's a discrete logarithm. Then she does what that person would do. Either side works, and both give the same s.
A discrete log is only practical when p − 1 splits into fairly small primes. The Pohlig–Hellman method then breaks the search into one small search per prime factor. Puzzles pick primes like that.
The whole thing with tiny numbers
What the puzzle gives you
Everything Alice and Bob send each other: the agreed prime and base, plus one number from each of them. Puzzles often show this as a conversation, so work out who sent which number.
Already know a or b?
If the puzzle gives away either secret, fill it in and the worksheet skips the search.
Pick a side
Recover one person's secret, then do what that person would do. Either side gives the same shared secret.
Break p − 1 into primes
The discrete-log search splits into one smaller search for each prime factor of p − 1. The biggest factor decides how long it takes, so that's the first thing to find out.
The discrete logarithm
Show the Pohlig–Hellman pieces
For each prime power dividing the order of the base, the page raises both sides to a power that leaves a much smaller problem. Small pieces are solved by baby-step giant-step, a lookup table of powers. Big pieces are solved by Pollard's rho, which takes random-looking walks on every processor core until two walks land on the same number. The Chinese Remainder Theorem then glues the pieces into one exponent.
The shared secret
With one secret in hand, do that person's last step.
What happens next
Diffie–Hellman only agrees on a key; it doesn't encrypt anything. If the puzzle also gives a message, that message is probably still encrypted, with another cipher that uses s as its key. In a puzzle that's often a classical cipher. The key might be the whole number s, only some of its digits (the first few, say), or s turned into letters, so look at how the puzzle describes the message. That cipher is the next thing to work out.