Going Public

So secret-key systems are schizophrenic---they need secret, but shared, keys. And they need many keys too. If a thousand of us have to share secrets with each other using a secret-key system, we could need half a million shared keys---every pair of us using the system might have to have our own shared secret key.

Of course, we can distribute keys securely, say by armed courier, but that's expensive and slow. So the more shared secret keys we need, the more expensive the system becomes. Further, the more of us who have to know a key, the more insecure the system is and the harder it is to change keys if there's a security breach.

All in all, it was a wretched way to work, but for several thousand years no one could think of anything better. Then the computer led to something revolutionary. And because of it, it's now possible for any of us to have as much privacy as major governments have. In 1975, two computer professionals, Whitfield Diffie and Martin Hellman, invented public-key systems, in which everyone has two keys, one private and one public. Each person keeps the private key secret, but can learn anyone else's public key. The private key is for decrypting, the public key for encrypting; and a computer using certain mathematical procedures ensures that neither is guessable from the other.

To see what a difference that makes, imagine that encryption procedures are locks. To send a message in a secret-key system, both Alice and Bob must have copies of the key opening the lock. Alice writes a message, puts it in a box, locks the box, then sends the locked box to Bob. Bob then uses his duplicate of the key to open the box and read the message. But in a public-key system, Alice and Bob each have their own separate private keys, and they each have their own public locks that those keys open. These locks are like padlocks: anyone can snap them shut, but only their owner can open them again. So, for example, although anyone at all can send anyone else a box locked with Bob's lock, only Bob can open it.

Imagine now that all the users of a public-key system are in a large room with a wall full of padlocks attached to a bulletin board. Each padlock has a label identifying its owner, and there are many copies of each padlock. Anyone can walk up to the wall, pull down any padlock, and lock a box containing some secrets with it. But only the padlock's owner can reopen that box. So to send a message to Bob, Alice writes the message, puts it in a box, locks the box with a copy of Bob's public lock, then sends the locked box to Bob. Bob then uses his private key to unlock the box and read the message. It's as if we all have our own personal mailbox, which only we can open but which anyone can drop mail into.

Such a seemingly innocuous system has consequences. First, Bob and Alice no longer need either a secure channel or a shared secret key. Everyone in the room could know that Bob and Alice are exchanging secret messages. Second, we now need only as many locks as there are people, rather than a lock for each pair of people. A thousand of us would need only a thousand locks, rather than half a million. Third, even Alice can't decrypt her own encrypted message to Bob; once she locks a box with his lock, not even she can open it. Fourth, Bob and Alice don't even have to know or trust each other.

Of course, computers are essential here---to make it impossible for anyone to derive information about a user's private key given the user's public lock. That wouldn't be true of real padlocks, because we could take them apart and so create a key to open them. But as far as we know now, computers make it virtually impossible to do that. We think.

The Real McCoy