A three-rotor Enigma machine on display at the National Cryptologic Museum of the American security agency. At the top, the rotors; in the middle, the lamps; below, the keyboard; at the front, the plugboard.
A three-rotor Enigma machine on display at the National Cryptologic Museum of the American security agency. At the top, the rotors; in the middle, the lamps; below, the keyboard; at the front, the plugboard.National Security Agency · Wikimedia Commons · public domain

The Enigma looked like a typewriter inside a wooden box. The operator pressed a letter on the keyboard and another letter lit up on a panel of lamps. A second operator wrote down the letters that lit up, and that sequence was sent by radio, in Morse code. At the other end, an operator with an identical machine, set up the same way, typed in the enciphered message and read the original text on the lamps.

Between key and lamp, the electric current ran through a maze: a plugboard, three rotors with crossed wires inside, a reflector that sent the current back, the three rotors again and the plugboard again. And with each key press the first rotor turned one position, changing the whole maze.

Counting the keys

The Germans trusted the Enigma because of the number of possible settings. Let us count them for the army model of 1939, with the combinatorics Pascal taught us.

The rotors. Three rotors are chosen from a box of 5, and the order matters:

$$5\cdot4\cdot3=60.$$

The starting positions. Each rotor starts at one of 26 letters:

$$26^3=17\,576.$$

The plugboard. Ten cables join letters in pairs, swapping them. How many ways are there to form 10 pairs from 26 letters? Put the 26 letters in a row, in any of the $26!$ orders, and form the pairs from the first 20, two at a time. The last 6 are left unplugged, and their order does not matter: divide by $6!$. The order of the 10 pairs does not matter: divide by $10!$. The order within each pair does not matter: divide by $2^{10}$. The result is

$$\frac{26!}{6!\cdot10!\cdot2^{10}}=150\,738\,274\,937\,250.$$

The total. Multiplying:

$$60\cdot17\,576\cdot150\,738\,274\,937\,250\approx1.59\times10^{20}.$$

That is about 159 quintillion keys, not counting the rotor rings. Testing a million keys a second, it would take some five million years to try them all.

The flaw

The reflector had a practical advantage: with the same setting, the machine served both to encipher and to decipher. But it brought a birth defect: since the current always came back by a different path, no letter could be enciphered as itself. An A never became an A.

That looks like very little, and it was decisive. The cryptanalysts knew that many messages contained predictable words, which they called cribs: the 6 o’clock weather report began with WETTERVORHERSAGE, and many reports said KEINE BESONDEREN EREIGNISSE, “nothing to report”. To find out where the crib sat in the enciphered message, it was enough to slide it along the text and discard every position where some letter coincided with the enciphered letter beneath it.

Q F Z W R W I K T Y R E S X B F O G K U H Q
W E T T E R V O R H E R S A G E              ← S over S: impossible
        W E T T E R V O R H E R S A G E      ← no coincidence: possible

In the first position, the S of the crib would fall on an enciphered S, which the Enigma never does: the position is discarded. Four places further on, no letter coincides, and the position remains a candidate.

The bombe

Rebuild of the Turing–Welchman bombe at Bletchley Park. Each set of three coloured drums imitates the three rotors of an Enigma; the machine tested positions in sequence, eliminating those that contradicted the crib.
Rebuild of the Turing–Welchman bombe at Bletchley Park. Each set of three coloured drums imitates the three rotors of an Enigma; the machine tested positions in sequence, eliminating those that contradicted the crib.Mike Peel · Wikimedia Commons · CC BY-SA 4.0

The Poles Marian Rejewski, Jerzy Różycki and Henryk Zygalski had been reading Enigma messages since 1932 and had built a machine for it, the bomba. In July 1939, weeks before the invasion of Poland, they handed everything over to the British and French. But the Germans had made the Enigma more complicated, and the Polish method depended on a habit they had dropped.

Turing designed a new, more general machine based on cribs. The idea was logical: a crib placed in a position imposes links between letters, such as “if A is plugged to E, then, three steps later, T is plugged to R”. These implications form loops, and a wrong rotor setting soon leads to a contradiction, such as “A is plugged to A and to B at the same time”. The bombe ran through the 17,576 rotor positions electrically and stopped only at those that did not produce a contradiction. Gordon Welchman added a “diagonal board” that made the search much more efficient. The first bombe began working in March 1940; by the end of the war there were more than two hundred.

Exercise: and with 8 rotors?

The German navy chose the 3 rotors from a box of 8. How many rotor orders were there?

$8\cdot7\cdot6=336$, more than five times the army’s 60. That is why the naval Enigma, the one Turing attacked, was the hardest.

Exercise: a single cable

How many ways are there to plug in a single cable on the plugboard? And two cables?

One cable is a choice of a pair of letters: $\binom{26}2=\frac{26\cdot25}2=325$. For two cables, choose the first pair, then the second among the 24 remaining letters, and divide by 2 because the order of the cables does not matter: $\frac{325\cdot276}{2}=44\,850$. The general formula gives the same: $\frac{26!}{22!\cdot2!\cdot2^2}=44\,850$.

Sources: Andrew Hodges, Alan Turing: The Enigma (1983) · Simon Singh, The Code Book (1999) · The Turing–Welchman Bombe, The National Museum of Computing.

All topics on Alan Turing · ← The universal machine: the program is data too · Banburismus: weighing evidence in decibans →

Image credits.