keeping secrets

First things first: cryptography works by turning messages into numbers. It can be as simple as A=1, B=2, C=3, etc.

Second: the simplest and most unbreakable system of cryptography is what's called a one-time pad. It's a long string of random numbers that are applied to your message. This can be done using a relatively simple operation -- for example, adding the two numbers, then subtracting 26 from any that are equal to 27 or more. If someone else has the same one-time pad they can decrypt the message. This works great, and if you implement it right is a truly unbreakable system. Unfortunately it also doesn't really solve the original problem: how to distribute a message without having to worry about it falling into the wrong hands. You've just replaced messages — now the original is safe, but if the one-time pad falls into the wrong hands your secret will be revealed.

An easier to use system arrived with the development of key-based cryptography. This doesn't solve the problem of keeping the key secret, but it at least makes the one-time pads easier to distribute by shortening them to a brief message — they're usually a little longer than a paragraph of random garbage) — without making the code easy to break.

The next advance was the big one. In the seventies two guys named Diffie and Hellman invented public key cryptography, an idea that's just impossibly neat. Metaphor time: imagine you've got two magic keys. Both can be used to lock any door, but it still matters which key you use, because only the other key can then unlock it. Key A can unlock doors that have been sealed with Key B, and vice versa. Neither key can open doors that it has locked.

That's the situation here. The Diffie-Hellman method can be used to generate mathematical keys that can each unlock messages encrypted by the other. A user generates a key pair -- a public key and a private key. There isn't really a difference except that one is kept secret. The other — the public key — is made available to anyone, obviously enough.

Now if you want to send a secure message to somebody you simply have to take his well-known public key, encrypt a message, and send it to him. He then uses his private key to decrypt it. If he needs to send a message back, he uses your own public key to encode the reply.

The only way to beat this method is to figure out a way to very quickly factor extremely large numbers, which nobody has done (at least not without getting killed by the NSA prior to announcing their discovery). Anyone besides me remember Sneakers? Well, factoring is what the magic black box in the movie did. In fact, the irritating Eurotrash professor guy even namechecked a real technique (the Number Sieve, if I remember correctly) during his character-establishing session of incomprehensible gibberish. Notwithstanding movie magic, public key cryptography systems are commonly set up such that doing the factoring necessary to break them would take all of the planet's computers working in unison for several millennia.

Another handy feature of public key cryptography is that it can be used to guarantee who's sending a message, in a process called "signing". A sender encrypts a message using his private key, then puts it out for public consumption. Anyone who cares to can decrypt it because the sender's public key is well-known — but if they can decrypt it, they can rest assured that the encrypter was the person to whom the public key corresponds.

This is used in a lot of ways, but the one that's most familiar to me is the Xbox. By default, the machine comes with Microsoft's public key built into it, which it uses to decode every game disc inserted into the machine. In this way only Microsoft can produce programs that run on the Xbox. What a modchip does isn't to break the encryption system -- it's to bypass it, letting you run code on the machine that hasn't been signed with Microsoft's private key.

Finally, it's worth pointing out that the biggest vulnerability of this system is in how the public keys get handed out. A man-in-the-middle attack involves someone distributing a fake public key while pretending to be someone else. There are some elaborate ways of avoiding this that aren't really worth going into, but it basically boils down to somebody in the system having a public key that you can trust. For example, your web browser comes with a handful of digital certificates from trusted sources -- when you connect to a secure website, those certificate authorities, which can be trusted, handle the verification of the remote website's identity.

Make sense? Well, just try to remember the magic key bit. The next time I pick up this topic I'll start talking about actual pieces of software that let you do cool things from work.