October 27th, 2005

amused, silly, ha ha only serious

Best way to wake up:

Singing along to a good song.

Sorrow drips into your heart through a pinhole
Just like a faucet that leaks, but there is comfort in the sound
But while you debate half-empty or half-full
It slowly rises, your love is gonna drown...
  • Current Mood
    dorky dorky
  • Tags
amused, silly, ha ha only serious

The beauty of Diffie-Hellman

I read about an algorithm called Diffie-Hellman Key Exchange yesterday. Basically, it's a way for two people to come up with the same number without allowing a third person who's listening in on them figure out what the number is.

It's not even that mathematically difficult; the only math you need that most people don't know is called a modulus. Modulus is used a lot by programmers; it really just means divide and take the remainder. (Remember remainders from third-grade long division?) So when I write Something mod X, that means divide Something by X and take the remainder.

Without further ado, the algorithm:

Alice and Bob want to communicate securely. Unfortunately, the only communications medium they have available to them is a telephone line which Eve, an eavesdropper, has tapped. (Or maybe it's an Internet connection and Eve has access to the routers between them, or it's a shortwave radio that Eve can listen in on, or it's snail-mailed postcards and Eve works at the post office. It doesn't matter—the principle is the same.) They have some kind of encryption available to them, but they need a shared secret value to use as a key.

  1. Alice and Bob agree on a large random prime number, P, and a small prime number, g. (g is often 2 or 5; P should be hundreds of digits long.) They can do this beforehand and are free to reuse these values. They need not be kept secret.
  2. Alice generates a large random number a, which does not need to be prime. She then calculates a′ = ga mod P and sends that to Bob over the insecure line. The operation needed to get a from ga mod P given g and P is called a discrete logarithm, and is very slow and difficult to perform.
  3. Bob generates a large random number b, calculates b′ = gb mod P and sends it to Alice over the insecure line. Note that this also requires a discrete logarithm to reverse.
  4. Alice calculates K = (b′)a mod P. Bob calculates K = (a′)b mod P. Both Alice and Bob arrive at the same K because gba mod P is just another way of writing gab mod P.
  5. Alice and Bob use K as the key to an encryption algorithm, and happily communicate in complete secrecy. Eve, having only the fairly useless values of g, P, ga mod P, and gb mod P, can't understand what they're saying.

That's actually not too bad for a field famed for its mathematical difficulty. And it's very elegant: there are few secrets (just a, b, and the shared secret K), it's built on elementary-school arithmetic, it scales to your computational resources (you could do it with pencil and paper, a calculator, a handheld, a PC, or a supercomputer, each time using larger numbers), and it very cleverly leverages a difficult problem in math. And the context of this makes it even more amazing—Diffie-Hellman was the first time anybody figured out how to communicate securely over an insecure channel without needing a secure one to set things up.

You could teach this to sixth-graders. Actually, I kind of wish they would teach it to sixth-graders; it's certainly more interesting than anything I studied in sixth-grade math.