The Code Book (22 page)

The onetime pad cipher overcomes all previous weaknesses. Imagine that the message attack the valley at dawn has been enciphered as in
Figure 30
, sent via a radio transmitter and intercepted by the enemy. The ciphertext is handed to an enemy cryptanalyst, who then attempts to decipher it. The first hurdle is that, by definition, there is no repetition in a random key, so the method of Babbage and Kasiski cannot break the onetime pad cipher. As an alternative, the enemy cryptanalyst might try placing the word the in various places, and deduce the corresponding piece of the key, just as we did when we attempted to decipher the previous message. If the cryptanalyst tries putting the at the beginning of the message, which is incorrect, then the corresponding segment of key would be revealed as WXB, which is a random series of letters. If the cryptanalyst tries placing the so that it begins at the seventh letter of the message, which happens to be correct, then the corresponding segment of key would be revealed as QKJ, which is also a random series of letters. In other words, the cryptanalyst cannot tell whether the trial word is, or is not, in the correct place.

In desperation, the cryptanalyst might consider an exhaustive search of all possible keys. The ciphertext consists of 21 letters, so the cryptanalyst knows that the key consists of 21 letters. This means that there are roughly 500,000,000,000,000,000,000,000,000,000 possible keys to test, which is completely beyond what is humanly or mechanically feasible. However, even if the cryptanalyst could test all these keys, there is an even greater obstacle to be overcome. By checking every possible key the cryptanalyst will certainly find the right message—but every wrong message will also be revealed. For example, the following key applied to the same ciphertext generates a completely different message:

Figure 30
Three sheets, each a potential key for a onetime pad cipher. The message is enciphered using Sheet 1.

If all the different keys could be tested, every conceivable 21-letter message would be generated, and the cryptanalyst would be unable to distinguish between the right one and all the others. This difficulty would not have arisen had the key been a series of words or a phrase, because the incorrect messages would almost certainly have been associated with a meaningless key, whereas the correct message would be associated with a sensible key.

The security of the onetime pad cipher is wholly due to the randomness of the key. The key injects randomness into the ciphertext, and if the ciphertext is random then it has no patterns, no structure, nothing the cryptanalyst can latch onto. In fact, it can be mathematically proved that it is impossible for a cryptanalyst to crack a message encrypted with a onetime pad cipher. In other words, the onetime pad cipher is not merely believed to be unbreakable, just as the Vigenère cipher was in the nineteenth century,
it really is absolutely secure
. The onetime pad offers a guarantee of secrecy: the Holy Grail of cryptography.

At last, cryptographers had found an unbreakable system of encryption. However, the perfection of the onetime pad cipher did not end the quest for secrecy: the truth of the matter is that it was hardly ever used. Although it is perfect in theory, it is flawed in practice because the cipher suffers from two fundamental difficulties. First, there is the practical problem of making large quantities of random keys. In a single day an army might exchange hundreds of messages, each containing thousands of characters, so radio operators would require a daily supply of keys equivalent to millions of randomly arranged letters. Supplying so many random sequences of letters is an immense task.

Some early cryptographers assumed that they could generate huge amounts of random keys by haphazardly tapping away at a typewriter. However, whenever this was tried, the typist would tend to get into the habit of typing a character using the left hand, and then a character using the right hand, and thereafter alternate between the two sides. This might be a quick way of generating a key, but the resulting sequence has structure, and is no longer random—if the typist hits the letter D, from the left side of the keyboard, then the next letter is predictable in as much as it is probably from the right side of the keyboard. If a onetime pad key was to be truly random, a letter from the left side of the keyboard should be followed by another letter from the left side of the keyboard on roughly half the occasions.

Cryptographers have come to realize that it requires a great deal of time, effort and money to create a random key. The best random keys are created by harnessing natural physical processes, such as radioactivity, which is known to exhibit truly random behavior. The cryptographer could place a lump of radioactive material on a bench, and detect its emissions with a Geiger counter. Sometimes the emissions follow each other in rapid succession, sometimes there are long delays—the time between emissions is unpredictable and random. The cryptographer could then connect a display to the Geiger counter, which rapidly cycles through the alphabet at a fixed rate, but which freezes momentarily as soon as an emission is detected. Whatever letter is on the display could be used as the next letter of the random key. The display restarts and once again cycles through the alphabet until it is stopped at random by the next emission, the letter frozen on the display is added to the key, and so on. This arrangement would be guaranteed to generate a truly random key, but it is impractical for day-to-day cryptography.

Even if you could fabricate enough random keys, there is a second problem, namely the difficulty of distributing them. Imagine a battlefield scenario in which hundreds of radio operators are part of the same communications network. To start with, every single person must have identical copies of the onetime pad. Next, when new pads are issued, they must be distributed to everybody simultaneously. Finally, everybody must remain in step, making sure that they are using the right sheet of the onetime pad at the right time. Widespread use of the onetime pad would fill the battlefield with couriers and bookkeepers. Furthermore, if the enemy captures just one set of keys, then the whole communication system is compromised.

It might be tempting to cut down on the manufacture and distribution of keys by reusing onetime pads, but this is a cryptographic cardinal sin. Reusing a onetime pad would allow an enemy cryptanalyst to decipher messages with relative ease. The technique used to prize open two pieces of ciphertext encrypted with the same onetime pad key is explained in
Appendix G
, but for the time being the important point is that there can be no shortcuts in using the onetime pad cipher. The sender and receiver must use a new key for every message.

A onetime pad is practicable only for people who need ultrasecure communication, and who can afford to meet the enormous costs of manufacturing and securely distributing the keys. For example, the hotline between the presidents of Russia and America is secured via a onetime pad cipher.

The practical flaws of the theoretically perfect onetime pad meant that Mauborgne’s idea could never be used in the heat of battle. In the aftermath of the First World War and all its cryptographic failures, the search continued for a practical system that could be employed in the next conflict. Fortunately for cryptographers, it would not be long before they made a breakthrough, something that would reestablish secret communication on the battlefield. In order to strengthen their ciphers, cryptographers were forced to abandon their pencil-and-paper approach to secrecy, and exploit the very latest technology to scramble messages.

The Development of Cipher Machines—from Cipher Disks to the Enigma

The earliest cryptographic machine is the cipher disk, invented in the fifteenth century by the Italian architect Leon Alberti, one of the fathers of the polyalphabetic cipher. He took two copper disks, one slightly larger than the other, and inscribed the alphabet around the edge of both. By placing the smaller disk on top of the larger one and fixing them with a needle to act as an axis, he constructed something similar to the cipher disk shown in
Figure 31
. The two disks can be independently rotated so that the two alphabets can have different relative positions, and can thus be used to encrypt a message with a simple Caesar shift. For example, to encrypt a message with a Caesar shift of one place, position the outer A next to the inner B—the outer disk is the plain alphabet, and the inner disk represents the cipher alphabet. Each letter in the plaintext message is looked up on the outer disk, and the corresponding letter on the inner disk is written down as part of the ciphertext. To send a message with a Caesar shift of five places, simply rotate the disks so that the outer A is next to the inner F, and then use the cipher disk in its new setting.

Even though the cipher disk is a very basic device, it does ease encipherment, and it endured for five centuries. The version shown in
Figure 31
was used in the American Civil War.
Figure 32
shows a Code-o-Graph, a cipher disk used by the eponymous hero of
Captain Midnight
, one of the early American radio dramas. Listeners could obtain their own Code-o-Graph by writing to the program sponsors, Ovaltine, and enclosing a label from one of their containers. Occasionally the program would end with a secret message from Captain Midnight, which could be deciphered by loyal listeners using the Code-o-Graph.

The cipher disk can be thought of as a “scrambler,” taking each plaintext letter and transforming it into something else. The mode of operation described so far is straightforward, and the resulting cipher is relatively trivial to break, but the cipher disk can be used in a more complicated way. Its inventor, Alberti, suggested changing the setting of the disk during the message, which in effect generates a polyalphabetic cipher instead of a monoalphabetic cipher. For example, Alberti could have used his disk to encipher the word goodbye, using the keyword LEON. He would begin by setting his disk according to the first letter of the keyword, moving the outer A next to the inner L. Then he would encipher the first letter of the message, g, by finding it on the outer disk and noting the corresponding letter on the inner disk, which is R. To encipher the second letter of the message, he would reset his disk according to the second letter of the keyword, moving the outer A next to the inner E. Then he would encipher o by finding it on the outer disk and noting the corresponding letter on the inner disk, which is S. The encryption process continues with the cipher disk being set according to the keyletter O, then N, then back to L, and so on. Alberti has effectively encrypted a message using the Vigenère cipher with his first name acting as the keyword. The cipher disk speeds up encryption and reduces errors compared with performing the encryption via a Vigenère square.

Figure 31
A U.S. Confederate cipher disk used in the American Civil War. (
photo credit 3.4
)