Alan Turing: The Enigma: The Book That Inspired the Film The Imitation Game

by Andrew Hodges

  * The British spying organisation, variously entitled SIS, MI6. Apart from this top-level administrative overlap it was and remained essentially distinct from the cryptanalytic department.

  * David Champernowne also discussed the principle of the chain reaction with Alan after reading an article about it by J. B. S. Haldane in the Daily Worker.

  * That is, for looking at even more zeroes of the zeta-function.

  * He used logarithms to base 8, so this ratio approximated logg3.

  * Alan was wrong.

  4 The Relay Race

  Gliding o’er all, through all,

  Through Nature, Time, and Space,

  As a ship on the waters advancing,

  The voyage of the soul – not life alone,

  Death, many deaths I’ll sing.

  Alan reported next day, 4 September, to the Government Code and Cypher School, which had been evacuated in August to a Victorian country mansion, Bletchley Park. Bletchley itself was a small town of ordinary dullness, a brick-built Urban District in the brickfields of Buckinghamshire. But it lay at the geometric centre of intellectual England, where the main railway from London to the north bisected the branch line from Oxford to Cambridge. Just to the north-west of the railway junction, on a slight hill graced by an ancient church, and overlooking the clay pits of the valley, stood Bletchley Park.

  The trains were busy with the evacuation of 17,000 London children into Buckinghamshire, swelling Bletchley’s population by twenty-five per cent. ‘The few who returned,’ said an urban district councillor, ‘no one on earth would have billeted, and they did the wisest thing eventually to return to the hovels from whence they came.’ In these circumstances, the arrival of a few select gentlemen for the Government Code and Cypher School would have caused little stir, although it was said that when Professor Adcock first arrived at the station, a little boy shouted ‘I’ll read your secret writing, mister!’ in a most disconcerting way. Later on there were complaints by local residents about the do-nothings at Bletchley Park, and it was said that the MP had to be prevented from asking a question in Parliament. They had the pick of accommodation: the few hostelries of mid-Buckinghamshire. Alan was billeted at the Crown Inn at Shenley Brook End, a tiny hamlet three miles north of Bletchley Park, whither he cycled each day. His landlady, Mrs Ramshaw, was one of those who lamented that an able-bodied young man was not doing his bit. Sometimes he helped out in the bar.

  The early days at Bletchley resembled the arrangements of a displaced senior common room, obliged through domestic catastrophe to dine with another college, but nobly doing its best not to complain. In particular there was a strong King’s flavour, with old-timers Knox, Adcock and Birch, and the younger Frank Lucas and Patrick Wilkinson as well as Alan. The shared background in Keynesian Cambridge was probably helpful for Alan. In particular it offered a link with Dillwyn Knox, a figure not generally noted for geniality or acessibility by Alan’s contemporaries. GC and CS was by no means a vast establishment. On 3 September, Denniston wrote1 to the Treasury:

  Dear Wilson,

  For some days now we have been obliged to recruit from our emergency list men of the Professor type who the Treasury agreed to pay at the rate of £600 a year. I attach herewith a list of these gentlemen already called up together with the dates of their joining.

  Alan was not quite the first, for according to Denniston’s list there were nine of these ‘men of the Professor type’ at Bletchley by the time that he arrived with seven others the next day. Over the following year, about sixty more outsiders were brought in.

  The ‘emergency in-take quadrupled the cryptanalytic staff of the Service sections and nearly doubled the total cryptanalytic staff.’ But only three of these first recruits came from the science side. Besides Alan, there were only W. G. Welchman and John Jeffries.* Gordon Welchman was the senior figure, lecturer in mathematics at Cambridge since 1929 and six years older than Alan. His field was algebraic geometry, a branch of mathematics then strongly represented at Cambridge, but one which never attracted Alan; their paths had not crossed before.

  Welchman had not been involved with GC and CS before the outbreak of war as Alan had, and thus found himself, as a newcomer, relegated by Knox to the task of analysing the pattern of German call-signs, frequencies, and so forth. As it transpired, this was a job of immense significance, and his work rapidly brought such ‘traffic analysis’ to a quite new standard. It made possible the identification of the different Enigma key-systems, as was soon to prove so important, and opened GC and CS eyes to a much wider vision of what could be done. But no one could decipher the messages themselves. There was just a ‘small group which, headed by civilians and working on behalf of all three Services, struggled with the Enigma.’ This group consisted first of Knox, Jeffries, Peter Twinn and Alan. They established themselves in the stables building of the mansion, soon dubbed ‘the Cottage’, and developed the ideas that the Poles had supplied at the eleventh hour.

  There was no glamour about ciphers. In 1939 the job of any cipher clerk, although not without skill, was dull and monotonous. But ciphering was the necessary consequence of radio* communication. Radio had to be used for aerial, naval, and mobile land warfare, and a radio message to one was a message to all. So messages had to be disguised, and not just this or that ‘secret message’, as with spies and smugglers, but the whole communication system. It meant mistakes, restrictions, and hours of laborious work on each message, but there was no choice.

  The ciphers used in the 1930s did not depend on any great mathematical sophistication, but on the simple ideas of adding on and substituting. The ‘adding on’ idea was hardly new; Julius Caesar had concealed his communications from the Gauls by a process of adding on three to each letter, so that an A became D, a B became an E, and so on. More precisely, this kind of adding was what mathematicians called ‘modular’ addition, or addition without carrying, because it meant Y becoming B, Z becoming C, as though the letters were arranged around a circle.

  Two thousand years later, the idea of modular addition by a fixed number would hardly be adequate, but there was nothing out-of-date about the general idea. One important type of cipher used the idea of ‘modular addition’, but instead of a fixed number, it would be a varying sequence of numbers, forming a key, that would be added to the message.

  In practice, the words of the message would first be encoded into numerals by means of a standard code-book. The job of the cipher clerk would then be to take this ‘plain-text’, say

  6728 5630 8923,

  and to take the ‘key’ say

  9620 6745 2397,

  and form the cipher-text

  5348 1375 0210

  by modular addition.

  For this to be of any use, however, the legitimate receiver had to know what the key was, so that it could be subtracted and the ‘plain-text’ retrieved. There had to be some system, by which the ‘key’ was agreed in advance between sender and receiver.

  One way of doing this was by means of the one-time principle. This was one of the few sound ideas of 1930s cryptography, as well as the simplest. It required the key to be written out explicitly, twice over, and one copy given to the sender, one to the receiver of the transmission. The argument for the security of this system was that provided the key were constructed by some genuinely completely random process, such as shuffling cards or throwing dice, there could be nothing for the enemy cryptanalyst to go on. Given cipher text ‘5673’, for instance, the analyst might guess that the plain-text was in fact ‘6743’ and the key therefore ‘9930’, or might guess that the plaintext was ‘8442’ and the key ‘7231’, but there would be no way of verifying such a guess, nor reason to prefer one guess to another. The argument depended upon the key being absolutely patternless, and spread evenly over the possible digits, for otherwise the analyst would have reason to prefer one guess to another. Indeed, discerning a pattern in the apparently patternless was essentially the work of the cryptanalyst, as of the scientist
.

  In the British system, one-time pads were produced, to be used up one at a time. Provided the key was random, no page was used twice, and the pads were never compromised, the system was fool-proof. But it would involve the manufacture of a colossal quantity of key, equal in volume to the maximum that the particular communication link might require. Presumably this thankless task was undertaken by the ladies of the Construction Section of GC and CS, which on the outbreak of war was evacuated not to Bletchley but to Mansfield College, Oxford. As for the system in use, that was no joy either. Malcolm Muggeridge, who was employed in the secret service, found it2

  a laborious business, and the kind of thing I have always been bad at. First, one had to subtract from the groups of numbers in the telegram corresponding groups from a so-called one-time pad; then to look up what the resultant groups signified in the code book. Any mistake in the subtraction, or, even worse, in the groups subtracted, threw the whole thing out. I toiled away at it, getting into terrible muddles and having to begin again …

  Alternatively, a cipher system might be based upon the ‘substitution’ idea. In its simplest form, this was used for puzzle-page cryptograms, such as they had solved in Princeton treasure hunts. It meant that one letter of the alphabet would be substituted for another, according to some fixed rule like:

  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

  K S G J T D A Y O B X H E P W M I Q C V N R F Z U L

  so that TURING would become VNQOPA. Such a simple, or ‘mono-alphabetic’ cipher could easily be solved by looking at letter frequencies, common words, and so forth, and in fact the only point of puzzle-page problems was that the setter would include peculiar words like XERXES to make this difficult. Such a system would be too simple-minded for military application. But there were systems in use in 1939 which were not much more advanced. One sophistication lay in the use of several alphabetic substitutions, used in rotation or according to some other simple scheme. The few manuals and text-books3 of cryptology in existence devoted themselves mainly to such ‘poly-alphabetic’ ciphers.

  Slightly more complex was the use of a system which substituted not for single letters, but for the 676 possible letter pairs. One British cipher system of this period was of this nature, combining the idea with the use of a code book. It was used by the Merchant Navy.4

  The cipher clerk would first have to render the message into Merchant Navy Code, thus:

  Text

  Coded

  Expect to arrive at

  V Q U W

  14 C

  F U D

  40 U

  Q G L

  The next step required an even number of rows, so the clerk would have to add a nonsense word to make it up:

  Balloon

  Z J V Y

  Then the encipherment would be done. The clerk would take the first vertical pair of letters, here VC, and look it up in a table of letter pairs. The table would specify some other pair, say XX. The clerk would continue to go through the message, substituting for each letter pair in this way.

  There was little more to it, except that as with the ‘adding on’ kind of cipher, the process was futile unless the legitimate receiver knew which substitution table was being used. To preface the transmission with ‘Table number 8’, say, would allow the enemy analyst to collect and collate the transmissions enciphered with the same table, and make an attack. There had to be some element of disguise involved. So printed with the table there was another list of eight-letter sequences such as ‘BMTVKZMD’. The clerk would choose one of these sequences and add it to the beginning of the message proper. The receiver, equipped with the same list, could then see which table was being used.

  This simple rule illustrated a very general idea. In practical cryptography, as opposed to the setting of isolated puzzles, there would usually be some part of the message transmitted which did not convey the text itself, but which conveyed instructions on how to decipher it. Such elements of the transmission, which would be disguised and buried within it, were called indicators. Even a one-time pad system might employ indicators, to give a check on which page of the pad was being used. In fact, unless everything were spelt out in advance and in complete, rigid, detail, without any chance of ambiguity or error, there would have to be some form of indicator.

  It must surely have struck Alan, who had been thinking at least since 1936 about ‘the most general kind of code or cipher’, that this mixing of instructions and data within a transmission was reminiscent of his ‘universal machine’, which would first decipher the ‘description number’ into an instruction, and then apply that instruction to the contents of its tape. Indeed any cipher system might be regarded as a complicated ‘mechanical process’ or Turing machine, involving not just the rules for adding or substituting, but rules for how to find, apply and communicate the method of encipherment itself. Good cryptography lay in the creation of an entire body of rules, not in this or that message. And serious cryptanalysis consisted of the work of recovering them; reconstructing the entire mechanical process which the cipher clerks performed, through an analysis of the entire mass of signals.

  Maybe the Merchant Navy cipher system was not the last word in baffling complexity, but for operational use in ordinary ships, it was near the limit of practicality for hand methods. Anyone might dream up more secure systems, but if a ciphering operation became too long and complicated, it would only result in more delays and mistakes. However, if cipher machines were used, to take over part of the clerk’s ‘mechanical process’, the situation could be very different.

  In this respect Britain and Germany were running a symmetrical war, using very similar machines. Virtually every German official radio communication was enciphered on the Enigma machine. The British state relied, less totally, on the Typex. This machine was used throughout the army and in most of the RAF; the Foreign Office and the Admiralty retained their own hand systems depending on books. Enigma and Typex alike mechanised the basic operations of substitution and adding on, in such a way that a more complex system came within practical grasp. They did nothing that could not have been done by the looking up of tables in books, but enabled the work to be done more quickly and accurately.

  There was no secret about the existence of such machines. Everyone knew of it – everyone, at least, who had a 1938 edition of Rouse Ball’s Mathematical Recreations and Essays as a school prize. A revised chapter written by the U.S. Army cryptanalyst, Abraham Sinkov, wheeled out all the antiquated grilles, Playfair ciphers, and so forth, but also mentioned that

  Quite recently there has been considerable research carried on in an attempt to invent cipher machines for the automatic encipherment and decipherment of messages. Most of them employ periodic polyalphabetic systems.

  A ‘periodic’ polyalphabetic cipher would run through some sequence of alphabetic substitutions, and then repeat that sequence.

  The most recent machines are electrical in operation, and in many cases the period is a tremendously large number…. These machine systems are much more rapid and much more accurate than hand methods. They can even be combined with printing and transmitting apparatus so that, in enciphering, a record of the cipher message is kept and the message transmitted; in deciphering, the secret message is received and translated, all automatically. So far as present cryptanalytic methods are concerned, the cipher systems derived from some of these machines are very close to practical unsolvability.

  Nor was there anything secret about the basic Enigma machine. It had been exhibited in 1923, soon after its invention, at the congress of the International Postal Union. It was sold commercially and used by banks. In 1935 the British had created Typex by adding certain attachments to it, while a few years earlier the German cryptographic authorities had modified it in a different way to create the machine which, though bearing the original name of Enigma, was much more effective than the commercially available device.

  This did not mean that the German Enigma with which Al
an Turing now had to grapple, was something ahead of its time, or even the best that the technology of the late 1930s could have produced. The only feature of the Enigma that brought it into the twentieth century, or at least the late nineteenth, was that it was indeed ‘electrical in operation’. It used electrical wirings to perform automatically a series of alphabetical substitutions, as shown in the first figure. But an Enigma would be used in a fixed state only for enciphering one letter, and then the outermost rotor would move round by one place, creating a new set of connections between input and output, as shown in the second figure.

  The Basic Enigma

  For the sake of simplicity, the diagram has been drawn for an alphabet of only eight letters, although in fact the Enigma worked on the ordinary 26-letter alphabet. It shows the state of the machine at some particular moment in its use. The lines marked correspond to current-carrying wires. A simple switch system at the input has the effect that if a key (say the B key) is depressed, a current flows (as shown in the diagram by bold lines) and lights up a bulb in the output display panel (in this case, under the letter D). For the hypothetical 8-letter Enigma, the next state of the machine would be:

  For the 26-letter Enigma, there would be 26 × 26 × 26 = 17576 possible states of the rotors. They were geared essentially* like any kind of adding machine or comptometer, so that the middle rotor would move on one step when the first had made a complete revolution, and the innermost move a step when the middle one had made a complete turn. The ‘reflector’, however, would not move, it being a fixed set of wires connecting the outputs of the innermost rotor.

  So the Enigma was polyalphabetic, with a period of 17576. But this was not a ‘tremendously large number’. Indeed, it would require a book only the size of a ready reckoner for all the alphabets to be written out. This mechanism was not, in itself, a leap into a new degree of sophistication. There was also a warning sounded by Rouse Ball in the old 1922 edition of his book that Alan had studied at school: