SUNY Geneseo Department of Mathematics
Wednesday, November 10
INTD 105 17
Fall 2021
Prof. Doug Baldwin
(No.)
Based on information from Simon Singh, The Code Book, and Hugh Sebag-Montefiore, Enigma: The Battle for the Code.
The total number of possible Enigma keys is the number of rotor settings times the number of plugboard configurations.
Recall that an Enigma consists of a set of rotors that scramble letters, preceded and followed by a plugboard that swaps pairs of letters.
Total rotor settings: in a 3-rotor Enigma, the operator used any 3 rotors from a set of 5, in any order, which means 5 × 4 × 3 = 60 different ways rotors could be loaded into the machine. Then each rotor could start in one of 26 different positions, for 26 × 26 × 26 = 17576 combinations of possible starting rotor positions. The product of these two numbers is 1054560 ways the rotors on an Enigma could be configured.
Total plugboard configurations: the plugboard swapped characters in pairs. For the first swap, the operator could choose any of 26 first letters, to swap with any of 25 other letters (since you can’t swap a letter with itself). But the total number of pairings is really only half of this, since pairing, for example, A and Q is the same as pairing Q with A. So the first swap can happen in any of 26 × 25 / 2 ways. The second swap can start with any of the 24 remaining letters, and pair it with any of 23, for 24 × 23 / 2 ways to do the second swap. Standard German procedure was to swap 10 pairs, so the total number of ways those swaps could happen was (26 × 25 × 24 × 23 × … × 8 × 7) / (2 × 2 × 2 × … × 2), where there are a total of 10 2s in the denominator. This number works out to about 5.5×1020.
The bottom line is that if you’re trying to break Enigma by brute force, the plugboard is your real enemy. So…
Marian Rejewski, a Polish cryptographer working just before war broke out, seems to have been the first to realize that it was possible to have patterns in an Enigma code that depended only on the rotors, not on the plugboard. He developed a machine called the “bomby” that exploited such patterns in ways the German army communicated per-message rotor settings.
Turing’s big insight was that there is also a way to analyze rotor configurations separately from the plugboard in any Enigma communication, if you have a crib (known plaintext). It was lucky that Turing realized this, since shortly after war started the Germans changed their method for communicating message settings. Turing knew about Rejewski’s bomby, and the name “bombe” is based on that name, although Turing’s bombes were completely different internally from Rejewski’s. Rejewski didn’t work on or know about the British bombes.
Turing’s idea used “loops” of plaintext-ciphertext pairs, i.e., situations in which one of the letters in a plaintext-ciphertext pair appeared in another pair elsewhere in the message, and the other letter from that pair appeared in yet another, and so forth, until finally the other letter in the last pair was the same as the other letter in the first pair. He then imagined the output letter from one pair being fed into another Enigma as the input for the next pair (the second Enigma having its rotors moved ahead by the right amount to correspond to where the rotors of a single Enigma encrypting the original message would have been by the time they got to this next pair). In this situation, the plugboards cancel out, leaving just the rotors to determine how letters are encoded. By chaining a whole series of plugboard-less Enigma simulations together, with the output of the last fed back into the input of the first, Turing created a machine that could complete an electrical circuit through all the Enigma simulations when the rotor settings were ones that could have produced the ciphertext (or at least those letters from it in the loop) from the plaintext.
A key phrase here is “could have produced.” Once a bombe identified a possible set of rotor settings, someone had to check them by hand to see if they actually decrypted the entire message in question, to infer plugboard connections (which, it turns out, you can do plug by plug once you know rotor settings and a crib, so finding the right plugboard configuration became much easier than searching through all 5.5×1020 possible combinations.)
Can you find other loops in the sample text? Can you invent and encrypt other plausible cribs (e.g., “weather,” “weather report,” “convoy,” etc.) and find loops?
(No-one did in the time available.)
Argumentation, practice linking evidence and logic to persuade.