Diffie–Hellman: Agreeing on a Secret in a Room Full of Listeners

Made with

Claude Opus 5.5Anthropic

Labels

Transcript

Imagine Alice and Bob want to talk privately. They have never met, and every word they say travels through a crowded room. Anyone can listen. Anyone can write down every message. To encrypt their conversation, they need a shared secret key, a number that only the two of them know. But how do you agree on a secret, when everything you say is overheard? In nineteen seventy-six, Whitfield Diffie and Martin Hellman published an answer. It sounds impossible, so let's start with paint. First, Alice and Bob agree, out loud, on a common colour: yellow. Everyone hears it. Then each of them picks a secret colour, and tells no one. Alice picks red. Bob picks blue. Alice mixes her red into the yellow, and gets orange. Bob mixes his blue into the yellow, and gets green. Now they swap those mixtures, in public. The listeners see yellow, orange, and green. Here is the trick. Alice takes Bob's green, and adds her own secret red. Bob takes Alice's orange, and adds his own secret blue. Both pots now hold yellow, red and blue: the very same brown. That brown is their shared secret. Why can't the listeners make it? Mixing orange and green doesn't work; that has too much yellow. To get the brown, you would need to pull the red back out of the orange. Mixing paint is easy. Unmixing it is hard. So the recipe is: a public starting point, a private ingredient on each side, swap the mixtures, then add your own ingredient again. Computers don't mix paint, so we need a mathematical kind of mixing: something easy to do, and hard to undo. It comes from clock arithmetic. On a twelve hour clock, fifteen o'clock is three o'clock. You go round once, and keep the remainder. We write: fifteen mod twelve equals three. Now take a clock with twenty-three positions, numbered zero to twenty-two. Start at five, and keep multiplying by five, wrapping around each time. Five. Twenty-five wraps to two. Ten. Fifty wraps to four. Twenty. A hundred wraps to eight. The hand jumps around the dial with no obvious pattern. Going forward is easy: multiply, and wrap. Going backward, asking how many steps it took to land on eight, is the hard part. Now the real exchange. Alice and Bob publicly agree on two numbers: a prime, p equals twenty-three, and a base, g equals five. Alice secretly picks a equals six. She computes five to the sixth, mod twenty-three: multiply by five and wrap, six times. Five, two, ten, four, twenty, eight. So Alice sends eight. Bob secretly picks b equals fifteen. Five to the fifteenth, mod twenty-three, follows the same path, and keeps going, all the way to nineteen. Bob sends nineteen. Now each of them adds their own secret again. Alice takes Bob's nineteen, and raises it to her six. Nineteen, sixteen, five, three, eleven, two. Bob takes Alice's eight, and raises it to his fifteen. Fifteen steps later, he also lands on two. They both have the number two, and it was never sent. It matches because each of them has really computed five to the power six times fifteen, which is ninety. Just like the paint, the order of mixing doesn't matter. So, in public: five, twenty-three, eight and nineteen. Kept secret: six, fifteen, and the shared key, two. What can an eavesdropper, Eve, do? She knows five, twenty-three, eight and nineteen. To find the key, she needs Alice's six or Bob's fifteen. That means answering: five to what power, mod twenty-three, gives eight? This is called the discrete logarithm problem. With twenty-three, it's trivial. Eve just tries every power. Five, two, ten, four, twenty, eight. Found it: six. Then she computes nineteen to the sixth, and she has the key. That's why real systems use primes around two thousand and forty-eight bits long, numbers with more than six hundred digits, or a variant built on elliptic curves. Alice and Bob's work still takes a fraction of a second. But on ordinary computers, no known method finds the secret exponent in any reasonable time. There is one catch. Diffie Hellman, on its own, doesn't tell Alice who she is talking to. An attacker in the middle, call her Mallory, could intercept both messages, run one exchange with Alice and a separate one with Bob, and quietly relay everything, reading it all along the way. Alice and Bob would each share a key, but with Mallory. The fix is authentication. In HTTPS, the server signs its part of the exchange, and a certificate vouches that the signing key really belongs to that website. So the next time your browser shows the padlock, remember: a stranger just agreed on a secret with you, in a room full of listeners, using numbers that are easy to mix, and hard to unmix.