by Simon Singh
In 1974, Diffie, still an itinerant cryptographer, paid a visit to IBM’s Thomas J. Watson Laboratory, where he had been invited to give a talk. He spoke about various strategies for attacking the key distribution problem, but all his ideas were very tentative, and his audience was skeptical about the prospects for a solution. The only positive response to Diffie’s presentation was from Alan Konheim, one of IBM’s senior cryptographic experts, who mentioned that someone else had recently visited the laboratory and given a lecture that addressed the issue of key distribution. That speaker was Martin Hellman, a professor from Stanford University in California. That evening Diffie got in his car and began the 5,000 km journey to the West Coast to meet the only person who seemed to share his obsession. The alliance of Diffie and Hellman would become one of the most dynamic partnerships in cryptography.
Martin Hellman was born in 1945 in a Jewish neighborhood in the Bronx, but at the age of four his family moved to a predominantly Irish Catholic neighborhood. According to Hellman, this permanently changed his attitude to life: “The other kids went to church and they learned that the Jews killed Christ, so I got called ‘Christ killer.’ I also got beat up. To start with, I wanted to be like the other kids, I wanted a Christmas tree and I wanted Christmas presents. But then I realized that I couldn’t be like all the other kids, and in self-defense I adopted an attitude of ‘Who would want to be like everybody else?’ ” Hellman traces his interest in ciphers to this enduring desire to be different. His colleagues had told him he was crazy to do research in cryptography, because he would be competing with the NSA and their multibillion-dollar budget. How could he hope to discover something that they did not know already? And if he did discover anything, the NSA would classify it.
Just as Hellman was beginning his research, he came across The Codebreakers by the historian David Kahn. This book was the first detailed discussion of the development of ciphers, and as such it was the perfect primer for a budding cryptographer. The Codebreakers was Hellman’s only research companion, until September 1974, when he received an unexpected phone call from Whitfield Diffie, who had just driven across the Continent to meet him. Hellman had never heard of Diffie, but grudgingly agreed to a half-hour appointment later that afternoon. By the end of the meeting, Hellman realized that Diffie was the best-informed person he had ever met. The feeling was mutual. Hellman recalls: “I’d promised my wife I’d be home to watch the kids, so he came home with me and we had dinner together. He left at around midnight. Our personalities are very different-he is much more counterculture than I am-but eventually the personality clash was very symbiotic. It was just such a breath of fresh air for me. Working in a vacuum had been really hard.”
Since Hellman did not have a great deal of funding, he could not afford to employ his new soulmate as a researcher. Instead, Diffie was enrolled as a graduate student. Together, Hellman and Diffie began to study the key distribution problem, desperately trying to find an alternative to the tiresome task of physically transporting keys over vast distances. In due course they were joined by Ralph Merkle. Merkle was an intellectual refugee, having emigrated from another research group where the professor had no sympathy for the impossible dream of solving the key distribution problem. Says Hellman:
Ralph, like us, was willing to be a fool. And the way to get to the top of the heap in terms of developing original research is to be a fool, because only fools keep trying. You have idea number 1, you get excited, and it flops. Then you have idea number 2, you get excited, and it flops. Then you have idea number 99, you get excited, and it flops. Only a fool would be excited by the 100th idea, but it might take 100 ideas before one really pays off. Unless you’re foolish enough to be continually excited, you won’t have the motivation, you won’t have the energy to carry it through. God rewards fools.
The whole problem of key distribution is a classic catch-22 situation. If two people want to exchange a secret message over the phone, the sender must encrypt it. To encrypt the secret message the sender must use a key, which is itself a secret, so then there is the problem of transmitting the secret key to the receiver in order to transmit the secret message. In short, before two people can exchange a secret (an encrypted message) they must already share a secret (the key).
When thinking about the problem of key distribution, it is helpful to consider Alice, Bob and Eve, three fictional characters who have become the industry standard for discussions about cryptography. In a typical situation, Alice wants to send a message to Bob, or vice versa, and Eve is trying to eavesdrop. If Alice is sending private messages to Bob, she will encrypt each one before sending it, using a separate key each time. Alice is continually faced with the problem of key distribution because she has to convey the keys to Bob securely, otherwise he cannot decrypt the messages. One way to solve the problem is for Alice and Bob to meet up once a week and exchange enough keys to cover the messages that might be sent during the next seven days. Exchanging keys in person is certainly secure, but it is inconvenient and, if either Alice or Bob is taken ill, the system breaks down. Alternatively, Alice and Bob could hire couriers, which would be less secure and more expensive, but at least they have delegated some of the work. Either way, it seems that the distribution of keys is unavoidable. For two thousand years this was considered to be an axiom of cryptography—an indisputable truth. However, there is a thought experiment that seems to defy the axiom.
Figure 63 Martin Hellman. (photo credit 6.2)
Imagine that Alice and Bob live in a country where the postal system is completely immoral, and postal employees will read any unprotected correspondence. One day, Alice wants to send an intensely personal message to Bob. She puts it inside an iron box, closes it and secures it with a padlock and key. She puts the padlocked box in the post and keeps the key. However, when the box reaches Bob, he is unable to open it because he does not have the key. Alice might consider putting the key inside another box, padlocking it and sending it to Bob, but without the key to the second padlock he is unable to open the second box, so he cannot obtain the key that opens the first box. The only way around the problem seems to be for Alice to make a copy of her key and give it to Bob in advance when they meet for coffee. So far, I have just restated the same old problem in a new scenario. Avoiding key distribution seems logically impossible—surely, if Alice wants to lock something in a box so that only Bob can open it, she must give him a copy of the key. Or, in terms of cryptography, if Alice wants to encipher a message so that only Bob can decipher it, she must give him a copy of the key. Key exchange is an inevitable part of encipherment—or is it?
Now picture the following scenario. As before, Alice wants to send an intensely personal message to Bob. Again, she puts her secret message in an iron box, padlocks it and sends it to Bob. When the box arrives, Bob adds his own padlock and sends the box back to Alice. When Alice receives the box, it is now secured by two padlocks. She removes her own padlock, leaving just Bob’s padlock to secure the box. Finally she sends the box back to Bob. And here is the crucial difference: Bob can now open the box because it is secured only with his own padlock, to which he alone has the key.
The implications of this little story are enormous. It demonstrates that a secret message can be securely exchanged between two people without necessarily exchanging a key. For the first time we have a suggestion that key exchange might not be an inevitable part of cryptography. We can reinterpret the story in terms of encryption. Alice uses her own key to encrypt a message to Bob, who encrypts it again with his own key and returns it. When Alice receives the doubly encrypted message, she removes her own encryption and returns it to Bob, who can then remove his own encryption and read the message.
It seems that the problem of key distribution might have been solved, because the doubly encrypted scheme requires no exchange of keys. However, there is a fundamental obstacle to implementing a system in which Alice encrypts, Bob encrypts, Alice decrypts and Bob decrypts. The problem is the order in which the encrypti
ons and decryptions are performed. In general, the order of encryption and decryption is crucial, and should obey the maxim “last on, first off.” In other words, the last stage of encryption should be the first to be decrypted. In the above scenario, Bob performed the last stage of encryption, so this should have been the first to be decrypted, but it was Alice who removed her encryption first, before Bob removed his. The importance of order is most easily grasped by examining something we do every day. In the morning we put on our socks, and then we put on our shoes, and in the evening we remove our shoes before removing our socks-it is impossible to remove the socks before the shoes. We must obey the maxim “last on, first off.”
Some very elementary ciphers, such as the Caesar cipher, are so simple that order does not matter. However, in the 1970s it seemed that any form of strong encryption must always obey the “last on, first off” rule. If a message is encrypted with Alice’s key and then with Bob’s key, then it must be decrypted with Bob’s key before it can be decrypted with Alice’s key. Order is crucial even with a monoalphabetic substitution cipher. Imagine that Alice and Bob have their own keys, as shown on the next page, and let us take a look at what happens when the order is incorrect. Alice uses her key to encrypt a message to Bob, then Bob reencrypts the result using his own key; Alice uses her key to perform a partial decryption, and finally Bob attempts to use his key to perform the full decryption.
The result is nonsense. However, you can check for yourself that if the decryption order were reversed, and Bob decrypted before Alice, thus obeying the “last on, first off” rule, then the result would have been the original message. But if order is so important, why did the padlock system seem to work in the anecdote about locked boxes? The answer is that order is not important for padlocks. I can apply twenty padlocks to a box and undo them in any order, and at the end the box will open. Unfortunately, encryption systems are far more sensitive than padlocks when it comes to order.
Although the doubly padlocked box approach would not work for real-world cryptography, it inspired Diffie and Hellman to search for a practical method of circumventing the key distribution problem. They spent month after month attempting to find a solution. Although every idea ended in failure, they behaved like perfect fools and persevered. Their research concentrated on the examination of various mathematical functions. A function is any mathematical operation that turns one number into another number. For example, “doubling” is a type of function, because it turns the number 3 into 6, or the number 9 into 18. Furthermore, we can think of all forms of computer encryption as functions because they turn one number (the plaintext) into another number (the ciphertext).
Most mathematical functions are classified as two-way functions because they are easy to do, and easy to undo. For example, “doubling” is a two-way function because it is easy to double a number to generate a new number, and just as easy to undo the function and get from the doubled number back to the original number. For example, if we know that the result of doubling is 26, then it is trivial to reverse the function and deduce that the original number was 13. The easiest way to understand the concept of a two-way function is in terms of an everyday activity. The act of turning on a light switch is a function, because it turns an ordinary lightbulb into an illuminated lightbulb. This function is two-way because if a switch is turned on, it is easy enough to turn it off and return the light-bulb to its original state.
However, Diffie and Hellman were not interested in two-way functions. They focused their attention on one-way functions. As the name suggests, a one-way function is easy to do but very difficult to undo. In other words, two-way functions are reversible, but one-way functions are not reversible. Once again, the best way to illustrate a one-way function is in terms of an everyday activity. Mixing yellow and blue paint to make green paint is a one-way function because it is easy to mix the paint, but impossible to unmix it. Another one-way function is the cracking of an egg, because it is easy to crack an egg but impossible then to return the egg to its original condition. For this reason, one-way functions are sometimes called Humpty Dumpty functions.
Modular arithmetic, sometimes called clock arithmetic in schools, is an area of mathematics that is rich in one-way functions. In modular arithmetic, mathematicians consider a finite group of numbers arranged in a loop, rather like the numbers on a clock. For example, Figure 64 shows a clock for modular 7 (or mod 7), which has only the 7 numbers from 0 to 6. To work out 2 + 3, we start at 2 and move around 3 places to reach 5, which is the same answer as in normal arithmetic. To work out 2 + 6 we start at 2 and move around 6 places, but this time we go around the loop and arrive at 1, which is not the result we would get in normal arithmetic. These results can be expressed as:
2 + 3 = 5 (mod 7) and 2 + 6 = 1 (mod 7)
Modular arithmetic is relatively simple, and in fact we do it every day when we talk about time. If it is 9 o’clock now, and we have a meeting 8 hours from now, we would say that the meeting is at 5 o’clock, not 17 o’clock. We have mentally calculated 9 + 8 in (mod 12). Imagine a clock face, look at 9, and then move around 8 spaces, and we end up at 5:
9 + 8 = 5 (mod 12)
Rather than visualizing clocks, mathematicians often take the shortcut of performing modular calculations according to the following recipe. First, perform the calculation in normal arithmetic. Second, if we want to know the answer in (mod x), we divide the normal answer by x and note the remainder. This remainder is the answer in (mod x). To find the answer to 11 × 9 (mod 13), we do the following:
11 × 9= 99
99 ÷ 13 = 7, remainder 8
11 × 9= 8 (mod 13)
Functions performed in the modular arithmetic environment tend to behave erratically, which in turn sometimes makes them one-way functions. This becomes evident when a simple function in normal arithmetic is compared with the same simple function in modular arithmetic. In the former environment the function will be two-way and easy to reverse; in the latter environment it will be one-way and hard to reverse. As an example, let us take the function 3x. This means take a number x, then multiply 3 by itself x times in order to get the new number. For example, if x = 2, and we perform the function, then:
3x = 32 = 3 × 3 = 9.
In other words, the function turns 2 into 9. In normal arithmetic, as the value of x increases so does the result of the function. Hence, if we were given the result of the function it would be relatively easy to work backward and deduce the original number. For example, if the result is 81, we can deduce that x is 4, because 34 = 81. If we made a mistake and guessed that x is 5, we could work out that 35 = 243, which tells us that our choice of x is too big. We would then reduce our choice of x to 4, and we would have the right answer. In short, even when we guess wrongly we can home in on the correct value of x, and thereby reverse the function.
Figure 64 Modular arithmetic is performed on a finite set of numbers, which can be thought of as numbers on a clock face. In this case, we can work out 6 + 5 in modular 7 by starting at 6 and moving around five spaces, which brings us to 4.
However, in modular arithmetic this same function does not behave so sensibly. Imagine that we are told that 3x in (mod 7) is 1, and we are asked to find the value of x. No value springs to mind, because we are generally unfamiliar with modular arithmetic. We could take a guess that x = 5, and we could work out the result of 35 (mod 7). The answer turns out to be 5, which is too big, because we are looking for an answer of just 1. We might be tempted to reduce the value of x and try again. But we would be heading in the wrong direction, because the actual answer is x = 6.
In normal arithmetic we can test numbers and can sense whether we are getting warmer or colder. The environment of modular arithmetic gives no helpful clues, and reversing functions is much harder. Often, the only way to reverse a function in modular arithmetic is to compile a table by calculating the function for many values of x until the right answer is found. Table 25 shows the result of calculating several values of the function
in both normal arithmetic and modular arithmetic. It clearly demonstrates the erratic behavior of the function when calculated in modular arithmetic. Although drawing up such a table is only a little tedious when we are dealing with relatively small numbers, it would be excruciatingly painful to build a table to deal with a function such as 453x (mod 21,997). This is a classic example of a one-way function, because I could pick a value for x and calculate the result of the function, but if I gave you a result, say 5,787, you would have enormous difficulty in reversing the function and deducing my choice of x. It took me just seconds to do my calculation and generate 5,787, but it would take you hours to draw up the table and work out my choice of x.
Table 25 Values of the function 3x calculated in normal arithmetic (row 2) and modular arithmetic (row 3). The function increases continuously in normal arithmetic, but is highly erratic in modular arithmetic.
After two years of focusing on modular arithmetic and one-way functions, Hellman’s foolishness began to pay off. In the spring of 1976 he hit upon a strategy for solving the key exchange problem. In half an hour of frantic scribbling, he proved that Alice and Bob could agree on a key without meeting, thereby disposing of an axiom that had lasted for centuries. Hellman’s idea relied on a one-way function of the form Yx (mod P). Initially, Alice and Bob agree on values for Y and P. Almost any values are fine, but there are some restrictions, such as Y being smaller than P. These values are not secret, so Alice can telephone Bob and suggest that, say, Y = 7 and P = 11. Even if the telephone line is insecure and nefarious Eve hears this conversation, it does not matter, as we shall see later. Alice and Bob have now agreed on the one-way function 7x (mod 11). At this point they can begin the process of trying to establish a secret key without meeting. Because they work in parallel, I explain their actions in the two columns of Table 26.
