The Theorem that Won the War: Part 3.3 – Breaking the Full Enigma

Now let's turn to the full Enigma system. With three rotors, the message key would consist of three letters. Let the unknown letters be \(\alpha\), \(\beta\), \(\gamma\). Using the daily key, these would be encrypted and sent twice. Suppose Allied codebreakers listened in, and found that \(\alpha\beta\gamma\ \alpha\beta\gamma\), encrypted using the daily code, was \(xkr \, bjs\).

Because we know that this is a three-letter sequence sent twice, then \(x\) and \(b\) are different Enigma encryptions of the same (unknown) letter \(\alpha\). Since \(x\) was the first letter of the message, this tells us

\[E_{1}(\alpha)=x\]

Since \(E_{1}(\alpha) = x\), it follows that cycle decomposition of \(E_{1}\) contains the transposition \((\alpha x)\).

Similarly \(b\), the fourth letter of the message, was encrypted using \(E_{4}\), so we know

\[E_{4}(\alpha)=b\]

and so the cycle decomposition of \(E_{4}\) contains the transposition \((\alpha b)\). Consequently, \(E_{4}E_{1}(x) = b\), so \(E_{4}E_{1}\) must include some cycle \((\ldots xb \ldots)\).

If we could obtain enough messages (and the British generally could), we can extend this cycle. For example, suppose we had another encrypted message key \(bha \, ttr\). Again, the first and third letters are the encryptions of the same plaintext, so this tells us \(E_{4}E_{1}(b) = t\), which allows us to extend our orbit; consequently, \(E_{4}E_{1}\) contains a cycle \(\ldots xbt \ldots\).

As a more detailed example, suppose we intercepted the following encrypted message keys:

\[\begin{array}{ccccc}jju\, ltl   &  \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,     &vxk\, ujs   &    \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,   &edi\, mvd &       &cvk\, nas\\ iro\, afc &     \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,    &urq\, wfo  &      \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,      &wgj\, iug           &      \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,        &sfb \,fbj \end{array}\]

The first intercept \(jju\, ltl\) tells us \(E_{4}E_{1}(j) = l\). This tells us \(E_{4}E_{1}\) includes a cycle \((\ldots jl \ldots)\). Unfortunately, no other intercept has \(l\) in the first position, nor \(j\) in the fourth, so we can't extend our knowledge of the cycle.

The second intercept is \(vxk\, ujs\). This tells us \(E_{4}E_{1}(v) = u\). Notice the sixth intercept is \(urq\, wfo\), which tells us \(E_{4}E_{1}(u) = w\).

The seventh intercept is \(wgj\, iug\), which tells us \(E_{4}E_{1}(w) = i\). Then the fifth intercept \(iro\, afc\) tells us \(E_{4}E_{1}(i) = a\). Put together, we see that \(E_{4}E_{1}\) must contain a cycle \((\ldots vuwia \ldots)\).

In this way, while we don't know the permutations \(E_{4}\) or \(E_{1}\) separately, we can recover cycles in their product \(E_{4}E_{1}\). In a similar way, by looking at the second and fifth letters of each message key, we can begin to recover the cycle decomposition of \(E_{5}E_{2}\); and the third and sixth letters of the message keys will allow us to begin to recover the cycle decomposition of \(E_{6}E_{3}\). In general, the Allies were able to intercept enough encrypted message keys to recover the full cycle decomposition of these products; the Enigma Theorem could then be used to limit the possibilities for the \(E_{i}\)s.

For example, suppose we find \(E_{4}E_{1}\) has cycle decomposition

\[E_{4}E_{1} = (xjlr)(pmhk)(aut)(ocd)(sfe)(yvg)(b)(i)(n)(q)(w)(z),\]

where we could again omit the 1-cycles, but we include them for clarity.

Consider the two 4-cycles. The Enigma Theorem guarantees the transpositions that make up \(E_{1}\) and \(E_{4}\) consist of one of \(x\), \(j\), \(l\), \(r\) with one of \(p\), \(m\), \(h\), \(k\): for example, \((xk)\). Thus, while there are 22 ´ 21 ´ 20 ´ 19 = 175,560 possible transpositions \((x\alpha)\), \((j\beta)\), \((l\gamma)\), \((r \delta)\), the Enigma theorem reduces this down to 24 possibilities. We can then use trial-and-error to determine the actual transpositions in \(E_{4}\) and \(E_{1}\). This last part was handled by the first electromechanical computers: first by the Polish bomba kryptologiczna (“cryptologic bomb” in Polish), and later by Turing's “bombe”. In this way, the Poles, and later the Bletchley Park group, were able to determine the internal wirings of the Enigma rotors and subsequently decrypt most German military communications.

Figure 20. Wartime photograph of a Bletchley Park Bombe, 1945.
Photographer unknown. Wikimedia Commons, public domain.

It’s worth pointing out that this analysis is only possible because of the reflector. Because of the reflector, all Enigma permutations are proper involutions. Sigint efforts gave the Allies knowledge of products of Enigma permutations, and the Enigma Theorem allowed those permutations to be “factored” into the individual Enigma permutations.

To explore these ideas further, continue to the Activities for Part 3.3 (Breaking the Full Enigma).

Return to the overview of Part 3 (Breaking Enigma).

Skip to the Conclusion.