As the name suggests, public keys are not secret; indeed, the Alices of this world often post them on the Internet or attach them to the bottom of their e-mail. When Bob wants to send Alice a secret message, he first converts the text of the message into a number. Perhaps, as before, he transforms "attack" into "5 100 100 5 15 55." Then he obtains Alice's public key—that is, p x q—by looking it up on a Web site or copying it from her e-mail. (Note here that Bob does not use his key to send Alice a message, as in regular encryption. Instead, he uses Alice's key.) Having found Alice's public key, he plugs it into a special algorithm invented by Rivest, Shamir, and Adleman to encrypt the message.
At this point the three mathematicians' cleverness becomes evident. Bob knows the product p x q, because Alice has displayed it on her Web site. But he almost certainly does not know p and q themselves, because they are its only factors, and factoring large numbers is effectively impossible. Yet the algorithm is constructed in such a way that to decipher the message the recipient must know both p and q individually. Because only Alice knows p and q, Bob can send secret messages to Alice without ever having to swap keys. Anyone else who wants to read the message will somehow have to factor p x q. How hard is that? Even if a team of demented government agents spent a trillion dollars on custom computers that do nothing but try random numbers, the Sun would likely go nova before they succeeded. (Rivest, Shamir, and Adleman patented their algorithm and to market it created a company, RSA Data Security, in 1983.)
In the real world, public-key encryption is practically never used to encrypt actual messages. The reason is that it requires so much computation—even on computers, public-key is very slow. According to a widely cited estimate by Schneier, public-key crypto is about a thousand times slower than conventional cryptography. As a result, public-key cryptography is more often used as a solution to the key-management problem, rather than as direct cryptography. People employ public-key to distribute regular, symmetric keys, which are then used to encrypt and decrypt actual messages. In other words, Alice and Bob send each other their public keys. Alice generates a symmetric key that she will only use for a short time (usually, in the trade, called a session key), encrypts it with Bob's public key, and sends it to Bob, who decrypts it with his private key. Now that Alice and Bob both have the session key, they can exchange messages. When Alice wants to begin a new round of messages, she creates another session key. Systems that use both symmetric and public-key cryptography are called hybrid, and almost every available public-key system, such as PGP, is a hybrid.
Solving the key problem, one should note, didn't make encryption easy for novices—it made encryption easier for experts. In 1999 a Carnegie Mellon doctoral student named Alma Whitten asked twelve experienced computer users to send and receive five encrypted e-mail messages apiece with PGP. One couldn't manage it at all; three accidentally sent unencrypted messages; seven created them with the wrong key; two had so much difficulty with the other tasks that they never bothered to send out the public, encrypting half of their keys; two who received properly encrypted messages tried to decrypt their decryption key, rather than the messages. Whitten called her report, cowritten with J. D. Tygar of the University of California at Berkeley, "Why Johnny Can't Encrypt."
Indeed, as mentioned in the profile, Johnny not only can't encrypt, he doesn't encrypt. Fascinating as a mathematical exercise, public-key encryption has yet to make much difference in people's lives.