Secrets in Public: Diffie-Hellman key exchange
Posted by bert hubert Sun, 11 Nov 2007 10:36:00 GMT
While running the risk of turning this blog into a lecture series, I can’t resist. This post will dive into cryptography, and I hope to be able to transfer the sense of wonder that caught me when I first read about Diffie-Hellman key exchange many years ago.
Let’s assume you are in a room with two other people, and that you want to share a secret with one of them, but not with the other. In the tradition of cryptography, we’ll call these three people Alice (you), Bob (your friend) and Eve (who wants to ‘Eavesdrop’ on your secrets).
Let’s also assume that the room is very quiet, so you can’t whisper, and everybody can hear what everybody else is saying. Furthermore, you are far enough away that you can’t pass paper messages.
So how could you (Alice) share a secret with Bob? Anything you want to tell Bob, will be overheard by Eve. You might try to think up a code, but you’ll still have to explain the code, and both Bob and Eve will hear it.
It turns out that using the magic of public key cryptography, this is possible - sharing a secret while people are listening in.
The room with Alice, Bob and Eve is not a very relevant example, but replace Alice by ‘The allied forces’, ‘Bob’ by a resistance fighter equipped with a radio, and ‘Eve’ by the occupying enemy, and things start to make sense.
Or, in today’s terms, replace Bob by Amazon.com, and Eve by a hacker interested in getting your credit card number.
So how does it work?
To send a secret, two things are needed: an ‘algorithm’ and a ‘key’. A famous algorithm is the ‘Caesar cypher’, which consists of shifting all letters by a fixed amount. So an A might become a B, a B would become a C etc etc.
The key in this case is how much you want to shift the letters, in the sample above the key is ‘1’. If the key had been ‘2’, an A would’ve become a C, a B would’ve become a D etc.
Typically, you can discuss the algorithm in public, but you need to keep the key secret. In terms of Alice and Bob, they will be able to communicate in secret once they’ve been able to establish a key that Eve does not know about.
Once everybody has agreed to use the Caesar cypher, the problem shifts to exchanging how many letters we will shift. We can’t just say this out loud, since both Bob and Eve will hear it.
Way back in 1976, Whitfield Diffie and Martin Hellman published the details of what has become known as the Diffie-Hellman key exchange algorithm, although they both credit Ralph Merkle with some of the key ideas.
The process basically works as follows. Alice and Bob each think of a random number, that they keep a secret. Then they both do some calculations based on this number, and say the result of those calculations out loud.
Then both Alice and Bob combine the results of the calculations with their own secret random number, and out pops a shared random secret number. This shared random secret number is now known by Alice and Bob, but not by Eve. And it is this secret that now becomes the key.
How is this possible?
Eve heard both Alice and Bob say a random number, exactly the same numbers that Alice and Bob heard. Yet only Alice and Bob now know the shared secret. How is this possible?
The trick lies in the calculation, by which means Alice and Bob only shared parts of the numbers they chose initially. Then both Alice and Bob combined those parts with their full random numbers.
It is this trick of revealing only parts of random numbers, and then combining the part of the other party with your full number, that leads to a shared secret.
On this page I wrote a very simple Diffie-Hellman example program that runs entirely within your web browser. You can either use it alone, or with a friend - which is the most fun. It works over the phone, or over an instant messenger (IRC, MSN etc). Follow the instructions, encode a message, paste it to your friend, and if your friend followed the instructions, and he pastes the encoded message into the decoder, he should see your secret message!
This is even more fun in a chat room with actual Eve’s present.
Please be aware that the sample is a joke - don’t use it to share real secrets! However, the technology it employs is real, and this truly is how people exchange keys - only the numbers are far larger (300 digits), and the actual encryption is not a Caesar cypher.
So how does it really work?
More information can be found on the wikipedia page about Diffie-Hellman, especially in the ‘external links’ section.