by Simon Singh
Having followed the stages in Table 26, you will see that, without meeting, Alice and Bob have agreed on the same key, which they can use to encipher a message. For example, they could use their number, 9, as the key for a DES encryption. (DES actually uses much larger numbers as the key, and the exchange process described in Table 26 would be performed with much larger numbers, resulting in a suitably large DES key.) By using Hellman’s scheme, Alice and Bob have been able to agree on a key, yet they did not have to meet up and whisper the key to each other. The extraordinary achievement is that the secret key was agreed via an exchange of information on a normal telephone line. But if Eve tapped this line, then surely she also knows the key?
Let us examine Hellman’s scheme from Eve’s point of view. If she is tapping the line, she knows only the following facts: that the function is 7x (mod 11), that Alice sends α = 2 and that Bob sends β = 4. In order to find the key, she must either do what Bob does, which is turn α into the key by knowing B, or do what Alice does, which is turn β into the key by knowing A. However, Eve does not know the value of A or B because Alice and Bob have not exchanged these numbers, and have kept them secret. Eve is stymied. She has only one hope: in theory, she could work out A from α, because α was a consequence of putting A into a function, and Eve knows the function. Or she could work out B from β, because β was a consequence of putting B into a function, and once again Eve knows the function. Unfortunately for Eve, the function is one-way, so whereas it was easy for Alice to turn A into α and for Bob to turn B into β, it is very difficult for Eve to reverse the process, especially if the numbers are very large.
Table 26 The general one-way function is Yx (mod P). Alice and Bob have chosen values for Y and P, and hence have agreed on the one-way function 7x (mod 11).
Bob and Alice exchanged just enough information to allow them to establish a key, but this information was insufficient for Eve to work out the key. As an analogy for Hellman’s scheme, imagine a cipher that somehow uses color as the key. First, let us assume that everybody, including Alice, Bob and Eve, has a three-liter pot containing one liter of yellow paint. If Alice and Bob want to agree on a secret key, each of them adds one liter of their own secret color to their own pot. Alice might add a peculiar shade of purple, while Bob might add crimson. Each sends their own mixed pot to the other. Finally, Alice takes Bob’s mixture and adds one liter of her own secret color, and Bob takes Alice’s mixture and adds one liter of his own secret color. Both pots should now be the same color, because they both contain one liter of yellow, one liter of purple and one liter of crimson. It is the exact color of the doubly contaminated pots that is used as the key. Alice has no idea what color was added by Bob, and Bob has no idea what color was added by Alice, but they have both achieved the same end. Meanwhile, Eve is furious. Even if she intercepts the intermediate pots she cannot work out the color of the final pots, which is the agreed key. She might see the color of the mixed pot containing yellow and Alice’s secret color on its way to Bob, and she might see the color of the mixed pot containing yellow and Bob’s secret color on its way to Alice, but in order to work out the key she really needs to know Alice and Bob’s original secret colors. However, Eve cannot work out Alice and Bob’s secret colors by looking at the mixed pots. Even if she takes a sample from one of the mixed paints, she cannot unmix the paint to find out the secret color, because mixing paint is a one-way function.
Hellman’s breakthrough came while he was working at home late one night, so by the time he had finished his calculations it was too late to call Diffie and Merkle. He had to wait until the following morning to reveal his discovery to the only two other people in the world who had believed that a solution to the key distribution problem was even possible. “The muse whispered to me,” says Hellman, “but we all laid the foundations together.” Diffie immediately recognized the power of Hellman’s breakthrough: “Marty explained his system of key exchange in all its unnerving simplicity. Listening to him, I realized that the notion had been at the edge of my mind for some time, but had never really broken through.”
The Diffie-Hellman-Merkle key exchange scheme, as it is known, enables Alice and Bob to establish a secret via public discussion. It is one of the most counterintuitive discoveries in the history of science, and it forced the cryptographic establishment to rewrite the rules of encryption. Diffie, Hellman and Merkle publicly demonstrated their discovery at the National Computer Conference in June 1976, and astonished the audience of cryptoexperts. The following year they filed for a patent. Henceforth, Alice and Bob no longer had to meet in order to exchange a key. Instead, Alice could just call Bob on the phone, exchange a couple of numbers with him, mutually establish a secret key and then proceed to encrypt.
Although Diffie-Hellman-Merkle key exchange was a gigantic leap forward, the system was not perfect because it was inherently inconvenient. Imagine that Alice lives in Hawaii, and that she wants to send an e-mail to Bob in Istanbul. Bob is probably asleep, but the joy of e-mail is that Alice can send a message at any time, and it will be waiting on Bob’s computer when he wakes up. However, if Alice wants to encrypt her message, then she needs to agree a key with Bob, and in order to perform the key exchange it is preferable for Alice and Bob to be on-line at the same time—establishing a key requires a mutual exchange of information. In effect, Alice has to wait until Bob wakes up. Alternatively, Alice could transmit her part of the key exchange, and wait 12 hours for Bob’s reply, at which point the key is established and Alice can, if she is not asleep herself, encrypt and transmit the message. Either way, Hellman’s key exchange system hinders the spontaneity of e-mail.
Hellman had shattered one of the tenets of cryptography and proved that Bob and Alice did not have to meet to agree a secret key. Next, somebody merely had to come up with a more efficient scheme for overcoming the problem of key distribution.
The Birth of Public Key Cryptography
Mary Fisher has never forgotten the first time that Whitfield Diffie asked her out on a date: “He knew I was a space buff, so he suggested we go and see a launch. Whit explained that he was leaving that evening to see Skylab take off, and so we drove all night, and we got there at about 3 A.M. The bird was on the path, as they used to say in those days. Whit had press credentials, but I didn’t. So when they asked for my identification and asked who I was, Whit said ‘My wife.’ That was 16 November 1973.” They did eventually marry, and during the early years Mary supported her husband during his cryptographic meditations. Diffie was still being employed as a graduate student, which meant that he received only a meager salary. Mary, an archaeologist by training, took a job with British Petroleum in order to make ends meet.
While Martin Hellman had been developing his method of key exchange, Whitfield Diffie had been working on a completely different approach to solving the problem of key distribution. He often went through long periods of barren contemplation, and on one occasion in 1975 he became so frustrated that he told Mary that he was just a failed scientist who would never amount to anything. He even told her that she ought to find someone else. Mary told him that she had absolute faith in him, and just two weeks later Diffie came up with his truly brilliant idea.
He can still recall how the idea flashed into his mind, and then almost vanished: “I walked downstairs to get a Coke, and almost forgot about the idea. I remembered that I’d been thinking about something interesting, but couldn’t quite recall what it was. Then it came back in a real adrenaline rush of excitement. I was actually aware for the first time in my work on cryptography of having discovered something really valuable. Everything that I had discovered in the subject up to this point seemed to me to be mere technicalities.” It was midafternoon, and he had to wait a couple of hours before Mary returned. “Whit was waiting at the door,” she recalls. “He said he had something to tell me and he had a funny look on his face. I walked in and he said, ‘Sit down, please, I want to talk to you. I believe that I have made a great discovery—I know
I am the first person to have done this.’ The world stood still for me at that moment. I felt like I was living in a Hollywood film.”
Diffie had concocted a new type of cipher, one that incorporated a so-called asymmetric key. So far, all the encryption techniques described in this book have been symmetric, which means that the unscrambling process is simply the opposite of scrambling. For example, the Enigma machine uses a certain key setting to encipher a message, and the receiver uses an identical machine in the same key setting to decipher it. Similarly, DES encipherment uses a key to perform 16 rounds of scrambling, and then DES decipherment uses the same key to perform the 16 rounds in reverse. Both sender and receiver effectively have equivalent knowledge, and they both use the same key to encrypt and decrypt-their relationship is symmetric. On the other hand, in an asymmetric key system, as the name suggests, the encryption key and the decryption key are not identical. In an asymmetric cipher, if Alice knows the encryption key she can encrypt a message, but she cannot decrypt a message. In order to decrypt, Alice must have access to the decryption key. This distinction between the encryption and decryption keys is what makes an asymmetric cipher special.
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.