The Code Book (46 page)

At this point it is worth stressing that although Diffie had conceived of the general concept of an asymmetric cipher, he did not actually have a specific example of one. However, the mere concept of an asymmetric cipher was revolutionary. If cryptographers could find a genuine working asymmetric cipher, a system that fulfilled Diffie’s requirements, then the implications for Alice and Bob would be enormous. Alice could create her own pair of keys: an encryption key and a decryption key. If we assume that the asymmetric cipher is a form of computer encryption, then Alice’s encryption key is a number, and her decryption key is a different number. Alice keeps the decryption key secret, so it is commonly referred to as Alice’s
private key
. However, she publishes the encryption key so that everybody has access to it, which is why it is commonly referred to as Alice’s
public key
. If Bob wants to send Alice a message, he simply looks up her public key, which would be listed in something akin to a telephone directory. Bob then uses Alice’s public key to encrypt the message. He sends the encrypted message to Alice, and when it arrives Alice can decrypt it using her private decryption key. Similarly, if Charlie, Dawn or Edward want to send Alice an encrypted message, they too can look up Alice’s public encryption key, and in each case only Alice has access to the private decryption key required to decrypt the messages.

The great advantage of this system is that there is no toing and froing, as there is with Diffie—Hellman–Merkle key exchange. Bob does not have to wait to get information from Alice before he can encrypt and send a message to her, he merely has to look up her public encryption key. Furthermore, the asymmetric cipher still overcomes the problem of key distribution. Alice does not have to transport the public encryption key securely to Bob: in complete contrast, she can now publicize her public encryption key as widely as possible. She wants the whole world to know her public encryption key so that anybody can use it to send her encrypted messages. At the same time, even if the whole world knows Alice’s public key, none of them, including Eve, can decrypt any messages encrypted with it, because knowledge of the public key will not help in decryption. In fact, once Bob has encrypted a message using Alice’s public key, even he cannot decrypt it. Only Alice, who possesses the private key, can decrypt the message.

This is the exact opposite of a traditional symmetric cipher, in which Alice has to go to great lengths to transport the encryption key securely to Bob. In a symmetric cipher the encryption key is the same as the decryption key, so Alice and Bob must take enormous precautions to ensure that the key does not fall into Eve’s hands. This is the root of the key distribution problem.

Returning to padlock analogies, asymmetric cryptography can be thought of in the following way. Anybody can close a padlock simply by clicking it shut, but only the person who has the key can open it. Locking (encryption) is easy, something everybody can do, but unlocking (decryption) can be done only by the owner of the key. The trivial knowledge of knowing how to click the padlock shut does not tell you how to unlock it. Taking the analogy further, imagine that Alice designs a padlock and key. She guards the key, but she manufactures thousands of replica padlocks and distributes them to post offices all over the world. If Bob wants to send a message, he puts it in a box, goes to the local post office, asks for an “Alice padlock” and padlocks the box. Now he is unable to unlock the box, but when Alice receives it she can open it with her unique key. The padlock and the process of clicking it shut is equivalent to the public encryption key, because everyone has access to the padlocks, and everyone can use a padlock to seal a message in a box. The padlock’s key is equivalent to the private decryption key, because only Alice has it, only she can open the padlock, and only she can gain access to the message in the box.

The system seems simple when it is explained in terms of padlocks, but it is far from trivial to find a mathematical function that does the same job, something that can be incorporated into a workable cryptographic system. To turn asymmetric ciphers from a great idea into a practical invention, somebody had to discover an appropriate mathematical function. Diffie envisaged a special type of one-way function, one that could be reversed under exceptional circumstances. In Diffie’s asymmetric system, Bob encrypts the message using the public key, but he is unable to decrypt it—this is essentially a one-way function. However, Alice is able to decrypt the message because she has the private key, a special piece of information that allows her to reverse the function. Once again, padlocks are a good analogy—shutting the padlock is a one-way function, because in general it is hard to open the padlock unless you have something special (the key), in which case the function is easily reversed.

Diffie published an outline of his idea in the summer of 1975, whereupon other scientists joined the search for an appropriate one-way function, one that fulfilled the criteria required for an asymmetric cipher. Initially there was great optimism, but by the end of the year nobody had been able to find a suitable candidate. As the months passed, it seemed increasingly likely that special one-way functions did not exist. It seemed that Diffie’s idea worked in theory but not in practice. Nevertheless, by the end of 1976 the team of Diffie, Hellman and Merkle had revolutionized the world of cryptography. They had persuaded the rest of the world that there was a solution to the key distribution problem, and had created Diffie–Hellman–Merkle key exchange—a workable but imperfect system. They had also proposed the concept of an asymmetric cipher—a perfect but as yet unworkable system. They continued their research at Stanford University, attempting to find a special one-way function that would make asymmetric ciphers a reality. However, they failed to make the discovery. The race to find an asymmetric cipher was won by another trio of researchers, based 5,000 km away on the East Coast of America.

Prime Suspects

“I walked into Ron Rivest’s office,” recalls Leonard Adleman, “and Ron had this paper in his hands. He started saying, ‘These Stanford guys have this really blah, blah, blah.’ And I remember thinking, ‘That’s nice, Ron, but I have something else I want to talk about.’ I was entirely unaware of the history of cryptography and I was distinctly uninterested in what he was saying.” The paper that had made Ron Rivest so excited was by Diffie and Hellman, and it described the concept of asymmetric ciphers. Eventually Rivest persuaded Adleman that there might be some interesting mathematics in the problem, and together they resolved to try to find a one-way function that fitted the requirements of an asymmetric cipher. They were joined in the hunt by Adi Shamir. All three men were researchers on the eighth floor of the MIT Laboratory for Computer Science.

Rivest, Shamir and Adleman formed a perfect team. Rivest is a computer scientist with a tremendous ability to absorb new ideas and apply them in unlikely places. He always kept up with the latest scientific papers, which inspired him to come up with a whole series of weird and wonderful candidates for the one-way function at the heart of an asymmetric cipher. However, each candidate was flawed in some way. Shamir, another computer scientist, has a lightning intellect and an ability to see through the debris and focus on the core of a problem. He too regularly generated ideas for formulating an asymmetric cipher, but his ideas were also inevitably flawed. Adleman, a mathematician with enormous stamina, rigor and patience, was largely responsible for spotting the flaws in the ideas of Rivest and Shamir, ensuring that they did not waste time following false leads. Rivest and Shamir spent a year coming up with new ideas, and Adleman spent a year shooting them down. The threesome began to lose hope, but they were unaware that this process of continual failure was a necessary part of their research, gently steering them away from sterile mathematical territory and toward more fertile ground. In due course, their efforts were rewarded.

In April 1977, Rivest, Shamir and Adleman spent Passover at the house of a student, and had consumed significant amounts of Manischewitz wine before returning to their respective homes some time around midnight. Rivest, unable to sleep, lay on his couch reading a mathematics textbook. He began mulling over the question that had been puzzling him for weeks—is it possible to build an asymmetric cipher? Is it possible to find a one-way function that can be reversed only if the receiver has some special information? Suddenly, the mists began to clear and he had a revelation. He spent the rest of that night formalizing his idea, effectively writing a complete scientific paper before daybreak. Rivest had made a breakthrough, but it had grown out of a yearlong collaboration with Shamir and Adleman, and it would not have been possible without them. Rivest finished off the paper by listing the authors alphabetically; Adleman, Rivest, Shamir.

The next morning, Rivest handed the paper to Adleman, who went through his usual process of trying to tear it apart, but this time he could find no faults. His only criticism was with the list of authors. “I told Ron to take my name off the paper,” recalls Adleman. “I told him that it was his invention, not mine. But Ron refused and we got into a discussion about it. We agreed that I would go home and contemplate it for one night, and consider what I wanted to do. I went back the next day and suggested to Ron that I be the third author. I recall thinking that this paper would be the least interesting paper that I will ever be on.” Adleman could not have been more wrong. The system, dubbed RSA (Rivest, Shamir, Adleman) as opposed to ARS, went on to become the most influential cipher in modern cryptography.

Figure 65
Ronald Rivest, Adi Shamir and Leonard Adleman. (
photo credit 6.3
)

Before exploring Rivest’s idea, here is a quick reminder of what scientists were looking for in order to build an asymmetric cipher:

(1) Alice must create a public key, which she would then publish so that Bob (and everybody else) can use it to encrypt messages to her. Because the public key is a one-way function, it must be virtually impossible for anybody to reverse it and decrypt Alice’s messages.

(2) However, Alice needs to decrypt the messages being sent to her. She must therefore have a private key, some special piece of information, which allows her to reverse the effect of the public key. Therefore, Alice (and Alice alone) has the power to decrypt any messages sent to her.

At the heart of Rivest’s asymmetric cipher is a one-way function based on the sort of modular functions described earlier in the chapter. Rivest’s one-way function can be used to encrypt a message-the message, which is effectively a number, is put into the function, and the result is the ciphertext, another number. I shall not describe Rivest’s one-way function in detail (for which see
Appendix J
), but I shall explain one particular aspect of it, known simply as
N
, because it is
N
that makes this one-way function reversible under certain circumstances, and therefore ideal for use as an asymmetric cipher.

N
is important because it is a flexible component of the one-way function, which means that each person can choose a different value of
N
, and personalize the one-way function. In order to choose her personal value of
N
, Alice picks two prime numbers,
p
and
q
, and multiplies them together. A prime number is one that has no divisors except itself and 1. For example, 7 is a prime number because no numbers except 1 and 7 will divide into it without leaving a remainder. Likewise, 13 is a prime number because no numbers except 1 and 13 will divide into it without leaving a remainder. However, 8 is not a prime number, because it can be divided by 2 and 4.

So, Alice could choose her prime numbers to be
p
= 17,159 and
q
= 10,247. Multiplying these two numbers together gives
N
= 17,159 × 10,247 = 175,828,273. Alice’s choice of
N
effectively becomes her public encryption key, and she could print it on her business card, post it on the Internet, or publish it in a public key directory along with everybody else’s value of N. If Bob wants to encrypt a message to Alice, he looks up Alice’s value of
N
(175,828,273) and then inserts it into the general form of the one-way function, which would also be public knowledge. Bob now has a one-way function tailored with Alice’s public key, so it could be called Alice’s one-way function. To encrypt a message to Alice, he takes Alice’s one-way function, inserts the message, notes down the result and sends it to Alice.

At this point the encrypted message is secure because nobody can decipher it. The message has been encrypted with a one-way function, so reversing the one-way function and decrypting the message is, by definition, very difficult. However, the question remains-how can Alice decrypt the message? In order to read messages sent to her, Alice must have a way of reversing the one-way function. She needs to have access to some special piece of information that allows her to decrypt the message. Fortunately for Alice, Rivest designed the one-way function so that it is reversible to someone who knows the values of
p
and
q
, the two prime numbers that are multiplied together to give
N
. Although Alice has told the world that her value for
N
is 175,828,273, she has not revealed her values for
p
and
q
, so only she has the special information required to decrypt her own messages.