The Code Book (45 page)
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 453
x
(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 3
x
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
Y
x
(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 7
x
(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
.
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 7
x
(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
Y
x
(mod
P
). Alice and Bob have chosen values for
Y
and
P
, and hence have agreed on the one-way function
7
x
(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.