Posted by bert hubert
Tue, 13 Nov 2007 12:42:00 GMT
Exactly one year ago today, my father passed away, less than a year after my mother did.
Here you can see them in happier times, together with the other subject of this post:
While we mourn their passing today, not all news is bad. I’m happy to announce Mirjam and I are expecting a baby!
We’re very happy, but sad we won’t be able to share the good news with my parents. But: life goes on - which is literally true in this case.
Bert & Mirjam
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
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
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.