Public-Key Cryptography Infrastructures

Public-key cryptography is a wonderfully useful gem of mathematics and computer science a publicly published set of numbers that can be used to encrypt a private message so that it is undecipherable to a snooper.

A public key is a series of 310 digits used to encrypt information sent to the keys owner, lets call him Joe. To decrypt these messages so he can read them, Joe uses his private key, which only he knows. Both the public and the private keys are derived from a pair of large prime numbers according to a relatively simple mathematical formula. In theory, it might be possible to derive the private key from the public key by working the formula backwards. In practice, no one has ever done it and it doesnt look like anyone ever will. Factoring large numbers is so hard that even the most powerful supercomputers in the world cant break an ordinary public key.

In an ideal world, everyone would have a public key that could be used to buy and sell things over the Internet, and engage in secure email communication with friends and strangers alike. There would be a directory on the Internet that would list everyones public key, like numbers in a telephone book. But in the 25 years since public key cryptography was invented, no such infrastructure has been built. Why?

The problem is not technical even the cheapest computers now have the power to handle 1024-bit encryption its economic and sociological. When it became clear that untold riches could be had if only people would entrust their credit card numbers to the Internet, the infrastructure for one-sided public key cryptography using the vendors public key sprang up almost overnight.

If everyone had a public key, it could function as a credit card that would be much less prone to fraud, and allow people to send each other email no one else could read. The reason they dont turns on the question of trust, say Microsoft Research cryptographers Josh Benaloh and Dan Simon.

Lets say Joe is the vice president of the First National Bank. Hes at home one night, when he gets an email from Frank the bank president. It says "I left my car keys in the vault, but I forgot the combination. Please send it to me. Here is a public key that you can use to encrypt the combination so that only I will get it. Key = X3AFK94KSD39SSAJ349SKFM232..." The key may safely encrypt the combination, but unless Joe is absolutely sure that the message and the key really came from Frank, he would be ill advised to send the vault combination.

Now, if there were a central directory, or a series of them, maintained by institutions in which everyone had absolute trust, then Joe could be sure that it was the real Frank he was dealing with, that his data would be safe as it traveled over the wires and no one but Frank could read it.

Some people use public key cryptography to exchange secure messages, but mostly theyre people who already know and trust each other. Most people have never had their email intercepted or exchanged sensitive information over the Internet. Until theres a strong public demand for the infrastructure, no one will build it, says Benaloh. Until the system is so easy to use that you dont even know its there, no one will use it, says Simon.

Preventing public key fraud and abuse turns out to be a tough problem, and a big reason there is no public key infrastructure today. Any directory would have to keep an up-to-date list of the deadbeats who didnt pay their bills and had their keys revoked. Should public keys have an expiration date? How often should they expire? What if someone gets hold of Joes private key? What if someone calls and says hes Joe and someone has stolen his private key and gets Joes key cancelled so that Joe, vacationing in Bali, suddenly finds his credit cut off? The list of problem scenarios goes on and on until the public key system begins to look more exploitable than todays credit card system, says Benaloh.

Perhaps unforeseen developments will motivate entrepreneurs to solve these problems and build a public key infrastructure. Wed like to make it happen, says Benaloh. Idea-wise, were leaders. Implementation-wise, the need has to come first.