The Man Who Knew Too Much: Alan Turing and the Invention of the Computer (Great Discoveries)

by David Leavitt

  Back at Princeton, Turing had built an electronic multiplier capable of enciphering messages by multiplying large binary numbers together. Although the idea was crude, it foretold the cryptographic method—based on the multiplication of immense prime numbers—that today protects our credit card numbers when we shop on the Internet. It had no bearing, however, on the German ciphers with which Turing and his colleagues were now presented. Instead, these were highly complex variations on the most basic cipher of all, the so-called monoalphabetic cipher.

  To understand how a monoalphabetic cipher works, xibauswe rgw xinnib weeie that occurs when one’s fingers slip on the typewriter keyboard. “Consider the common error” comes out as “xibauswe rgw xinnib weeie.” Now imagine that one is obliged to make sense of a long passage typed with the fingers misaligned: the text appears meaningless. Because we know, however, that the misalignment has resulted in each letter of the alphabet being replaced by another letter, common sense tells us that we should look for repeated three-letter sequences that might represent enciphered versions of the most common word in English, “the.” If we were looking at a long stretch of text ciphered according to the finger-slip method, we might notice lots of instances of the sequence “rgw.” Assuming, then, that “rgw” is “the,” we take the message and replace all the r’s with t’s, the g’s with h’s, and the w’s with e’s. Soon we begin to see other familiar words taking shape. It’s rather like an acrostic, which is why monoalphabetic ciphers (which date back to the Middle Ages) are so simple to break. At the heart of the matter is probability—in particular, letter distribution: you use as your guide a knowledge of the statistical frequency with which individual letters appear in English or whatever other language the plain text is written in. (In English, the most common letter is E, the least common Z.)

  Building on the basic principle of substitution, however, one can construct a much more complex cipher, of a sort known as a polyalphabetic cipher. A good example is the Vigenère cipher, which has its origins in the fifteenth century but came into more frequent use in the late nineteenth century. Essentially, a Vigenère cipher works by means of the construction of a “tableau” in which the plaintext letters are listed across the top and the “key” letters along the left side. (For concision’s sake, I have included here a tableau written out only as far as the twelfth position, L; the reader can assume that a full tableau would continue in the same fashion through Z.)

  To use this cipher, the sender and recipient need only agree on a keyword. Let’s say the keyword is DELILAH and that the message I want to encode is “Be at Grantchester at three.” I then replace each letter in my plaintext message with the corresponding letter in the column marked by the appropriate letter in the keyword:

  My message now begins EILBRRHQGSLD. . . . With the same keyword, the receiver can decipher it and get the plaintext. This cipher differs from a simple monoalphabetic cipher in that, obviously, each letter is enciphered by use of a different substitution alphabet; therefore the cipher cannot be broken by simply looking for repeating sequences of letters and guessing what they might represent.

  But it can be broken. The trick, as with all ciphers, is to look for a point of vulnerability and then take ruthless advantage of it until the fortifications collapse. In any polyalphabetic cipher, the obvious weak point is a dependence on repetition; in the example given above, the keyword DELILAH is seven letters long, which means that in a long message, the first, eighth, fifteenth, and twenty-second letters are all being coded with the same monoalphabetic cipher, as are the second, ninth, sixteenth, and twenty-third letters, the third, tenth, seventeenth, and twenty-fourth letters, etc. In principle, then, in order to have a shot at deciphering the message, you would need to have a keyword that was not terribly long; you would need to know its length; and you would need to possess a large enough body of enciphered text to allow for several repetition cycles. You would then break the text into units the length of the keyword and align them in order to study the letter frequencies.

  Unfortunately, code breakers rarely have this kind of information to hand. To make matters more complicated for them, as an extra security measure, most users of polyalphabetic ciphers would alter the order of letters within the keyword according to a prearranged scheme; that is, they would agree to begin ciphering one day with HDELILA, the next with AHDELIL, the next with LAHDELI. What was needed was a theoretical leap forward, and not surprisingly, the first mathematician to recognize the most promising route of attack was none other than Charles Babbage, creator of the analytic engine. As Simon Singh explains in The Code Book, Babbage’s stroke of genius was to step back from the microanalysis of letter frequencies in a sequence of enciphered text and instead treat the sequence as if it had been randomly generated. Essentially Babbage was enacting a statistical analysis of letter repetitions—a method that Solomon Kullback, building on the work of his mentor, William Friedman, would formalize in the article “Statistical Methods,” published in 1938 in Cryptanalysis.

  Here’s how it works.* Let’s say that we have a sequence that is twenty-four letters long. We can break it into two segments of twelve letters each and then align them. Statistically, the chance, say, that P will appear in position 7 in the first twelve-letter segment is 1 in 26, as is the chance that P will appear in position 7 in the second segment. This means that the chance of P’s appearing in position 7 in both segments is , or .15 percent. But the chance of any letter’s appearing in the same position in both segments is , or 3.8 percent. On the other hand, if the two aligned segments have actually been ciphered using the same keyword, the two letters in each position will be part of a monoalphabetic substitution, and the P in position 7 in the first segment will be the enciphered form of the same letter as the P in position 7 in the second segment. In any stretch of English text, E has a 12 percent chance of appearing at any given position, which means that in two aligned segments of text ciphered with the same keyword, the letter that has been substituted for E has a , or 1.4 percent, chance of appearing in the same position in both segments. A similar percentage can be worked out for each of the other twenty-five letters in the alphabet, and when these values are averaged, you get a rate of coincidence around 6.7 percent. It is therefore possible to shift the alignment of the enciphered text segments in relationship to each other and perform a frequency analysis on each pair. If the rate jumps from 3.8 percent to 6.7 percent, you know that you have stumbled upon two segments ciphered with the same keyword, and you can proceed from there, applying the same acrostic puzzle method that you would use in the case of a monoalphabetic cipher.

  As the weaknesses in the Vigenère cipher and others of its kind became apparent, cryptographers began seeking out refinements by means of which the ciphers they used could be rendered more resistant to cryptanalysis. One approach was to create a keyword the same length as the message; as Singh observes, however, this approach ended up proving only slightly less vulnerable than the original method, since the cryptanalyst could simply fit common words such as “the” into the cipher text at various points, and then see if the substitution generated a segment of key that might likely be a portion of an English word. If testing out the word “the” generated the letters XGT, you could pretty much assume that you were on the wrong track. On the other hand, if the substitution led to DAY, you would know, at the very least, to continue your investigation, since this letter sequence is a common one in English.

  A further refinement involved the replacement of keywords by randomly generated key sequences of letters that had no meaning in English (or whatever language was the basis for the cipher). This resulted in an unbreakable cipher, but one with the huge disadvantage that its use required the generation of a great quantity of randomly generated letter sequences. In the years before the computer, such sequences were nearly impossible to create. In addition, there was the problem of distributing the key sequences among the operators in the network. In principle this could have been done through the printing
of pads, on each page of which a different random sequence would be listed. The operators would use the sequence indicated for a given day, then at the end of the day tear it off and throw it away. Unfortunately, the logistics involved both in printing the pads and in getting them to all the operators in the network, especially during wartime, proved in the end so cumbersome as to render the system more or less unusable.

  The next logical step was to build a cipher machine. The first cipher disc, made from copper, was built in the fifteenth century. In the nineteenth century Thomas Jefferson invented a “cipher cylinder,” a device consisting of discs printed with letters in different sequences mounted on an axle. A similar “cipher wheel” was used by the Confederacy during the Civil War. These devices, however, merely mechanized the work of feeding a letter through the Vigenère cipher; the cipher text that resulted was no less impervious to attack for having been generated by a machine.

  What was needed was a machine that would not only speed up the processes of encipherment and decipherment but actually augment security by subjecting the letters fed into it to extra scrambling. This breakthrough came about in the 1920s, with the more or less simultaneous invention in the Netherlands, Sweden, the United States, England, and Germany of a type of machine of which the German version—the Enigma—would become the most successful exemplar.* The Enigma was the brainchild of the German engineer Arthur Scherbius, who exhibited his device for the first time at the Congress of the International Postal Union in Bern, Switzer-land, with the ambition of selling it to businessmen concerned that their competitors would intercept their telegrams. As it happened, the Enigma ended up being something of a flop with its target audience: it was both too expensive and, at twelve kilos, too heavy to appeal to bottom-line oriented German entrepreneurs. Several years later, however, the machine came to the attention of the client that would make Scherbius’s career: the German government, which bought a slew of the machines and adapted them for military use.

  Like that of the personal computer—which in many ways it foreshadowed—the Enigma’s apparent simplicity and ease of use belied an ingenious and highly complex internal mechanism. It looked like a typewriter and was no more difficult to use. However, unlike its English cousin, the Typex, the Enigma could not print and had no slot for paper. Instead, mounted above the keyboard, the letters on which were arranged as on a German typewriter, there was an array of twenty-six lamps each labeled with a letter of the alphabet and set up in exactly the same formation as the keyboard itself. Above the array of lamps, in turn, there was a hinged lid fitted with three tiny windows. When you lifted the lid, you would see the three rotors that were the key elements of the Enigma’s engineering, each fitted with a movable ring also marked with the twenty-six letters of the alphabet. The three rotors could be removed and rearranged in any of six possible orders.

  Operating the machine required no knowledge whatsoever of what went on inside it. Indeed, all that sender and recipient needed to agree upon in advance was the key code, the rotor order, and the ring setting. The idea was that the daily settings would be printed either in books or on sheets of paper collected in pads, copies of which would be distributed to everyone in the sending and receiving network; every morning the senders and recipients would “program” their Enigma with the settings for that day, before proceeding with encryption.

  Say you had to send a message. You would first look up the ring setting, rotor order, and three-letter key for the day; next, having fixed the settings, you would move the rotors themselves so that the key—let’s say it’s ATM—showed through the three windows on the lid. Finally, you would take your message and type it into the Enigma one letter at a time. If the first letter in the message was E, you would type E, the machine would whir and click, and then one of the lamps—let’s say the one marked U—would light up. Proceeding in this fashion, you would encipher the entire message, noting down each letter, and then transmit the ciphered message via telegraph or radio in Morse code. The receiver would then set his Enigma machine to exactly the same settings, feed in the ciphered message, and—lo and behold—the plaintext would emerge. For this was the genius of the Enigma machine. Its engineering not only guaranteed unparalleled security; it allowed for encipherment and decipherment using the same settings. In other words, if feeding an E into an Enigma programmed to certain settings produced a U, then feeding a U into an Enigma programmed to the same settings produced an E. In terms of its fundamental design, the machine differed little from most of its predecessors, which also relied on a system of rotating disks; what made it unique was that it put the letters fed into it through a battery of extra permutations, and did so with extraordinary speed.

  The most essential elements of the engineering were the three rotors, which were arranged in three slots from left to right. On the left and right side of each removable rotor were twenty-six contact points corresponding to the twenty-six letters of the alphabet: the surrounding rings were printed with the letters themselves, in alphabetical order, and could be moved around the rotor, thus altering which letter corresponded to which contact point on a daily basis. (One day, for instance, A might be at contact point 17, the next at contact point 3, and so on.)

  The Enigma Machine, employed by the Germans to encrypt classified and sensitive messages during World War II. (HultonArchive/Getty Images)

  Inside each rotor a mass of wires connected the contact points on the right face to those on the left. This wiring, though arbitrary, was fixed; that is to say, even though the rotors could be placed in different orders, all the rotors in all the Enigma machines in the system were wired alike. This insured that rotor 1 on the sender’s Enigma would have wiring identical to that of rotor 1 on the recipient’s Enigma. And since the rotor order was one of the elements fixed in advance, there was no chance of cross-wiring.

  A series of switches connected the rightmost of the rotors to the keyboard. In the commercial Enigma, the letters on the keyboard were linked up with the contact points on the first rotor in the same order as that found on the keyboard; in the military Enigma, however, the wiring had been changed, and one of the first challenges the code breakers faced was to figure out what the new order was. Because the top row of letters on a German typewriter reads QWERTZUIO (as opposed to the QWERTYUIOP found on American typewriters), Dilwyn Knox, one of the first Englishmen to take on the Enigma, referred to the mysterious new letter order as the “qwertzu.” Though Knox feared that this order might prove so arbitrary as to defy analysis, to his great surprise, a group of Polish cryptanalysts led by Marian Rejewski quickly determined that in the military model of the Enigma, the Germans had simply connected the letters on the keyboard to the contact points on the first rotor in alphabetical order. This was the first of several instances in which German laziness and lack of imagination ended up aiding the code breakers in their effort to defeat the machine.

  When a letter was typed into the Enigma, current flowed from the keyboard into the rightmost rotor, which then shifted one position, thus changing the letter’s identity. The current continued through the other two rotors, with a substitution occurring in each position. Next the current entered a “reflector,” a half-width disk at the left end of the machine with contacts only on its right side. The reflector connected pairs of letters, replacing the incoming letter with a second one, which would then be sent back through the three rotors for another series of substitutions. Its function was to guarantee that no letter typed into the Enigma could be enciphered as itself; it was also responsible for the Enigma’s property of being able to serve as both an encipherment and a decipherment machine.

  A last element—incorporated into the military Enigmas—was a “stecker” board, rather resembling an old-fashioned telephone switchboard and located at the base of the machine, with twenty-six jacks (or “steckers”) into which cables could be plugged. On these machines the positions of the steckers also had to be agreed upon in advance. Steckered pairs of letters would be swapped both be
fore and after the encipherment process took place: to give an example, P might be steckered as V, which would mean that when the operator of the Enigma typed in a P it would immediately be replaced by a V, which would in turn be put through the encipherment process. Along the same lines, if at the end of the encipherment process a C emerged, it might be replaced by a J, assuming that C and J were likewise steckered. Although in principle all twenty-six letters could be steckered in thirteen pairs, during the early years of the Enigma system only six pairs of letters were steckered; later this number was increased to ten. One of the principal challenges the code breakers faced was determining which the letters were.

  From a statistical standpoint, the sheer multitude of scramblings to which the Enigma subjected any incoming plaintext made it close to impregnable. In contrast to the Vigenère cipher, in which the sequence of monoalphabetic ciphers began again with each repetition of the keyword, an Enigma would have to run through the full cycle of all three rotors—a stretch of more than 17,000 letters—before a key sequence would repeat. (Three rotors with twenty-six contact points each meant that there were 263, or 17,576, possible routes that a letter could take.) In addition, the rotors could be removed and arranged in any one of the six different orders. Later, the German military added two extra rotors, making it possible to arrange three out of five in any of six orders, for a total of sixty possible rotors orders; later still, the total quantity of rotors was increased to eight. The adjustability of the ring setting allowed for further complication, since the ring on each rotor could be shifted into any of 26 positions, for a total of 676 positions when all three rings were taken into account. Finally, a stecker board consisting of only six cables could generate 100,391,791,500 further permutations.