Enigma Machine

One of the very first computers was built to break the Nazi “enigma” codes in WW2. It was a hard problem because the “enigma” machine, used to make secret codes, had so many unique configurations. Every day the Nazis would choose a new configuration and if the Allies could figure out the daily configuration, they could read all enemy messages. One solution was to try all configurations until one produced legible German. This begs the question: How many configurations are there?

The WW2 machine built to search different enigma configurations.

The enigma machine has three rotors. Each rotor can be set to one of 26 different positions. How many unique configurations are there of the three rotors?

Using the steps rule of counting: $26 \cdot 26 \cdot 26 = 26^3 = 17,576$.

Whats more! The machine has a plug board which could swap the electrical signal for letters. On the plug board, wires can connect any pair of letters to produce a new configuration. A wire can’t connect a letter to itself. Wires are indistinct. A wire from ‘K’ to ’L’ is not considered distinct from a wire from ‘L’ to ’K’. We are going to work up to considering any number of wires.

The engima plugboard. For electrical reasons, each letter has two jacks and each plug has two prongs. Semantically this is equivalent to one plug location per letter.

One wire: How many ways are there to place exactly one wire that connects two letters?

Chosing 2 letters from 26 is a combination. Using the combination formula: ${26 \choose 2} = 325$.

Two wires: How many ways are there to place exactly two wires? Recall that wires are not considered distinct. Each letter can have at most one wire connected to it, thus you couldn’t have a wire connect ‘K’ to ‘L’ and another one connect ‘L’ to ‘X’

There are ${26 \choose 2}$ ways to place the first wire and ${24 \choose 2}$ ways to place the second wire. However, since the wires are indistinct, we have double counted every possibility. Because every possibility is counted twice we should divide by 2: $$ \text{Total} = \frac{ {26 \choose 2} \cdot {24 \choose 2} }{2} = 44,850 $$

Three wires: How many ways are there to place exactly three wires?

There are ${26 \choose 2}$ ways to place the first wire and ${24 \choose 2}$ ways to place the second wire. There are now ${22 \choose 2}$ ways to place the third. However, since the wires are indistinct, and our step counting implicitly treats them as distinct, we have overcounted each possibility. How many times is each pairing of three letters overcounted? It's the number of permutations of three distinct objects: 3! $$ \text{Total} = \frac{ {26 \choose 2} \cdot {24 \choose 2} \cdot {22 \choose 2}}{3!} = 3,453,450 $$ There is another way to arrive at the same answer. First we are going to choose the letters to be paired, then we are going to pair them off. There are ${26 \choose 6}$ ways to select the letters that are being wired up. We then need to pair off those letters. One way to think about pairing the letters off is to first permute them (6! ways) and then pair up the first two letters, the next two, the next two, and so on. For example, if our letters were {A,B,C,D,E,F} and our permutation was BADCEF, then this would correspond to wiring B to A and D to C and E to F. We are overcounting by a lot. First, we are overcounting by a factor of 3! since the ordering of the pairs doesn’t matter. Second, we are overcounting by a factor of $2 ^ 3$ since the ordering of the letters within each pair doesn’t matter. $$ \text{Total} = {26 \choose 6} \frac{6!}{3! \cdot 2^3} = 3,453,450 $$

Arbitrary wires: How many ways are there to place $k$ wires, thus connecting $2 \cdot k$ letters? During WW2 the Germans always used a fixed number of wires. But one fear was that if they discovered the Enigma machine was cracked, they could simply use an arbitrary number of wires.

The set of ways to use exactly $i$ wires is mutually exclusive from the set of ways to use exactly $j$ wires if $i \neq j$ (since no way can use both exactly $i$ and $j$ wires). As such $ \text{Total} = \sum_{k=0}^{13} \text{Total}_k $ Where Total$_k$ is the number of ways to use exactly $k$ wires. Continuing our logic for ways to used exact number of wires: $$ \text{Total}_k = \frac{\prod_{i=1}^{k} {28 - 2i \choose 2} }{k!} $$ Bringing it all together: $$ \begin{align} \text{Total} &= \sum_{k=0}^{13} \text{Total}_k \\ &= \sum_{k=0}^{13} \frac{\prod_{i=1}^{k} {28 - 2i \choose 2} }{k!} \\ &= 532,985,208,200,576 \end{align} $$

The actual Enigma used in WW2 had exactly 10 wires connecting 20 letters allowing for 150,738,274,937,250 unique configuration. The enigma machine also chose the three rotors from a set of five adding another factor of ${5 \choose 3} = 60$.

When you combine the number of ways of setting the rotors, with the number of ways you could set the plug board you get the total number of configurations of an enigma machine. Thinking of this as two steps we can multiply the two numbers we earlier calculated: 17,576 · 150,738,274,937,250 · 60 $\approx 159 \cdot 10^{18}$ unique settings. So, Alan Turing and his team at Blechly Park went on to build a machine which could help test many configurations -- a predecessor to the first computers.