by Simon Singh
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)
Figure 32 Captain Midnight’s Code-o-Graph, which enciphers each plaintext letter (outer disk) as a number (inner disk), rather than a letter.
The important feature of using the cipher disk in this way is the fact that the disk is changing its mode of scrambling during encryption. Although this extra level of complication makes the cipher harder to break, it does not make it unbreakable, because we are simply dealing with a mechanized version of the Vigenère cipher, and the Vigenère cipher was broken by Babbage and Kasiski. However, five hundred years after Alberti, a more complex reincarnation of his cipher disk would lead to a new generation of ciphers, an order of magnitude more difficult to crack than anything previously used.
In 1918, the German inventor Arthur Scherbius and his close friend Richard Ritter founded the company of Scherbius & Ritter, an innovative engineering firm that dabbled in everything from turbines to heated pillows. Scherbius was in charge of research and development, and was constantly looking for new opportunities. One of his pet projects was to replace the inadequate systems of cryptography used in the First Wo
rld War by swapping pencil-and-paper ciphers with a form of encryption that exploited twentieth-century technology. Having studied electrical engineering in Hanover and Munich, he developed a piece of cryptographic machinery that was essentially an electrical version of Alberti’s cipher disk. Called Enigma, Scherbius’s invention would become the most fearsome system of encryption in history.
Scherbius’s Enigma machine consisted of a number of ingenious components, which he combined into a formidable and intricate cipher machine. However, if we break the machine down into its constituent parts and rebuild it in stages, then its underlying principles will become apparent. The basic form of Scherbius’s invention consists of three elements connected by wires: a keyboard for inputting each plaintext letter, a scrambling unit that encrypts each plaintext letter into a corresponding ciphertext letter, and a display board consisting of various lamps for indicating the ciphertext letter. Figure 33 shows a stylized layout of the machine, limited to a six-letter alphabet for simplicity. In order to encrypt a plaintext letter, the operator presses the appropriate plaintext letter on the keyboard, which sends an electric pulse through the central scrambling unit and out the other side, where it illuminates the corresponding ciphertext letter on the lampboard.
The scrambler, a thick rubber disk riddled with wires, is the most important part of the machine. From the keyboard, the wires enter the scrambler at six points, and then make a series of twists and turns within the scrambler before emerging at six points on the other side. The internal wirings of the scrambler determine how the plaintext letters will be encrypted. For example, in Figure 33 the wirings dictate that:
typing in a will illuminate the letter B, which means that a is encrypted as B,
typing in b will illuminate the letter A, which means that b is encrypted as A,
typing in c will illuminate the letter D, which means that c is encrypted as D,
typing in d will illuminate the letter F, which means that d is encrypted as F,
typing in e will illuminate the letter E, which means that e is encrypted as E,
typing in f will illuminate the letter C, which means that f is encrypted as C.
The message cafe would be encrypted as DBCE. With this basic setup, the scrambler essentially defines a cipher alphabet, and the machine can be used to implement a simple monoalphabetic substitution cipher.
However, Scherbius’s idea was for the scrambler disk to automatically rotate by one-sixth of a revolution each time a letter is encrypted (or one-twenty-sixth of a revolution for a complete alphabet of 26 letters). Figure 34(a) shows the same arrangement as in Figure 33; once again, typing in the letter b will illuminate the letter A. However, this time, immediately after typing a letter and illuminating the lampboard, the scrambler revolves by one-sixth of a revolution to the position shown in Figure 34(b). Typing in the letter b again will now illuminate a different letter, namely C. Immediately afterward, the scrambler rotates once more, to the position shown in Figure 34(c). This time, typing in the letter b will illuminate E. Typing the letter b six times in a row would generate the ciphertext ACEBDC. In other words, the cipher alphabet changes after each encryption, and the encryption of the letter b is constantly changing. With this rotating setup, the scrambler essentially defines six cipher alphabets, and the machine can be used to implement a polyalphabetic cipher.
The rotation of the scrambler is the most important feature of Scherbius’s design. However, as it stands the machine suffers from one obvious weakness. Typing b six times will return the scrambler to its original position, and typing b again and again will repeat the pattern of encryption. In general, cryptographers are keen to avoid repetition because it leads to regularity and structure in the ciphertext, symptoms of a weak cipher. This problem can be alleviated by introducing a second scrambler disk.
Figure 33 A simplified version of the Enigma machine with an alphabet of just six letters. The most important element of the machine is the scrambler. By typing in b on the keyboard, a current passes into the scrambler, follows the path of the internal wiring, and then emerges so as illuminate the A lamp. In short, b is encrypted as A. The box to the right indicates how each of the six letters is encrypted.
Figure 34 Every time a letter is typed into the keyboard and encrypted, the scrambler rotates by one place, thus changing how each letter is potentially encrypted. In (a) the scrambler encrypts b as A, but in (b) the new scrambler orientation encrypts b as C. In (c), after rotating one more place, the scrambler encrypts b as E. After encrypting four more letters, and rotating four more places, the scrambler returns to its original orientation.
Figure 35 is a schematic of a cipher machine with two scramblers. Because of the difficulty of drawing a three-dimensional scrambler with three-dimensional internal wirings, Figure 35 shows only a two-dimensional representation. Each time a letter is encrypted, the first scrambler rotates by one space, or in terms of the two-dimensional diagram, each wiring shifts down one place. In contrast, the second scrambler disk remains stationary for most of the time. It moves only after the first scrambler has made a complete revolution. The first scrambler is fitted with a tooth, and it is only when this tooth reaches a certain point that it knocks the second scrambler on one place.
In Figure 35(a), the first scrambler is in a position where it is just about to knock forward the second scrambler. Typing in and encrypting a letter moves the mechanism to the configuration shown in Figure 35(b), in which the first scrambler has moved on one place, and the second scrambler has also been knocked on one place. Typing in and encrypting another letter again moves the first scrambler on one place, Figure 35(c), but this time the second scrambler has remained stationary. The second scrambler will not move again until the first scrambler completes one revolution, which will take another five encryptions. This arrangement is similar to a car odometer—the rotor representing single miles turns quite quickly, and when it completes one revolution by reaching “9,” it knocks the rotor representing tens of miles forward one place.
The advantage of adding a second scrambler is that the pattern of encryption is not repeated until the second scrambler is back where it started, which requires six complete revolutions of the first scrambler, or the encryption of 6 × 6, or 36 letters in total. In other words, there are 36 distinct scrambler settings, which is equivalent to switching between 36 cipher alphabets. With a full alphabet of 26 letters, the cipher machine would switch between 26 × 26, or 676 cipher alphabets. So by combining scramblers (sometimes called rotors), it is possible to build an encryption machine which is continually switching between different cipher alphabets. The operator types in a particular letter and, depending on the scrambler arrangement, it can be encrypted according to any one of hundreds of cipher alphabets. Then the scrambler arrangement changes, so that when the next letter is typed into the machine it is encrypted according to a different cipher alphabet. Furthermore, all of this is done with great efficiency and accuracy, thanks to the automatic movement of scramblers and the speed of electricity.
Figure 35 On adding a second scrambler, the pattern of encryption does not repeat until 36 letters have been enciphered, at which point both scramblers have returned to their original positions. To simplify the diagram, the scramblers are represented in just two dimensions; instead of rotating one place, the wirings move down one place. If a wire appears to leave the top or bottom of a scrambler, its path can be followed by continuing from the corresponding wire at the bottom or top of the same scrambler. In (a), b is encrypted as D. After encryption, the first scrambler rotates by one place, also nudging the second scrambler around one place—this happens only once during each complete revolution of the first wheel. This new setting is shown in (b), in which b is encrypted as F. After encryption, the first scrambler rotates by one place, but this time the second scrambler remains fixed. This new setting is shown in (c), in which b is encrypted as B.
Before explaining in detail how Scherbius intended his encryption machine to be used, i
t is necessary to describe two more elements of the Enigma, which are shown in Figure 36. First, Scherbius’s standard encryption machine employed a third scrambler for extra complexity—for a full alphabet these three scramblers would provide 26 × 26 × 26, or 17,576 distinct scrambler arrangements. Second, Scherbius added a reflector. The reflector is a bit like a scrambler, inasmuch as it is a rubber disk with internal wirings, but it differs because it does not rotate, and the wires enter on one side and then reemerge on the same side. With the reflector in place, the operator types in a letter, which sends an electrical signal through the three scramblers. When the reflector receives the incoming signal it sends it back through the same three scramblers, but along a different route. For example, with the setup in Figure 36, typing the letter b would send a signal through the three scramblers and into the reflector, whereupon the signal would return back through the wirings to arrive at the letter D. The signal does not actually emerge through the keyboard, as it might seem from Figure 36, but instead is diverted to the lampboard. At first sight the reflector seems to be a pointless addition to the machine, because its static nature means that it does not add to the number of cipher alphabets. However, its benefits become clear when we see how the machine was actually used to encrypt and decrypt a message.
Figure 36 Scherbius’s design of the Enigma included a third scrambler and a reflector that sends the current back through the scramblers. In this particular setting, typing in b eventually illuminates D on the lampboard, shown here adjacent to the keyboard.
An operator wishes to send a secret message. Before encryption begins, the operator must first rotate the scramblers to a particular starting position. There are 17,576 possible arrangements, and therefore 17,576 possible starting positions. The initial setting of the scramblers will determine how the message is encrypted. We can think of the Enigma machine in terms of a general cipher system, and the initial settings are what determine the exact details of the encryption. In other words, the initial settings provide the key. The initial settings are usually dictated by a codebook, which lists the key for each day, and which is available to everybody within the communications network. Distributing the codebook requires time and effort, but because only one key per day is required, it could be arranged for a codebook containing 28 keys to be sent out just once every four weeks. By comparison, if an army were to use a onetime pad cipher, it would require a new key for every message, and key distribution would be a much greater task. Once the scramblers have been set according to the codebook’s daily requirement, the sender can begin encrypting. He types in the first letter of the message, sees which letter is illuminated on the lampboard, and notes it down as the first letter of the ciphertext. Then, the first scrambler having automatically stepped on by one place, the sender inputs the second letter of the message, and so on. Once he has generated the complete ciphertext, he hands it to a radio operator who transmits it to the intended receiver.