The Code Book (44 page)

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 encryptions 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 3
^x
. 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:

3
^x
= 3
²
= 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 3
⁴
= 81. If we made a mistake and guessed that
x
is 5, we could work out that 3
⁵
= 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 3
^x
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 3
⁵
(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.