The Theorem that Won the War: Part 3.1 – Cycle Decompositions

To begin to unravel how having two different encryptions for the same letter helped the Allies break the full Enigma code, we start with our paper Enigma.

Since our paper Enigma has only one keyboard rotor, we only need to specify one initial position, so our message key would consist of a single letter. Suppose this unknown letter is \(\alpha\). This would be encrypted by \(E_{1}\) and again by \(E_{2}\); note that these encryptions would be based on the daily key. Other users would choose other message keys, but again encrypt them using the daily key, and we might accumulate a set of intercepted encrypted message keys, say \[\begin{array}{ccccc}cf            &ed       &da       &ae       &fb\end{array}.\]

Let's consider \(cf\). By assumption, this a repetition of our message key \(\alpha\); in other words, it is an encryption, using the daily key, of the “message” \(\alpha\alpha\), in which the first \(\alpha\) is encrypted using \(E_{1}\) and the second \(\alpha\) is encrypted using \(E_{2}\).

Since the first \(\alpha\) is encrypted as \(c\), we know that \(E_{1}(\alpha) = c\); and since \(E_{1}\) is a proper involution—and so it can be expressed as a product of transpositions—we know that \(E_{1}\) includes the transposition \((\alpha c )\). By the same reasoning, we know that \(E_{2}(\alpha) = f\), so \(E_{2}\) must contain the cycle \((\alpha f)\).

Now consider \(E_{2}E_{1}\). Since \(E_{1}\) contains the transposition \((\alpha c)\), and \(E_{2}\) contains the transposition \((\alpha f )\), it follows that \(E_{2}E_{1}(c) = f\).

Note that \(E_{2}E_{1}\) is not an Enigma encryption, so we don't know if it can be written as a product of transpositions. What we do know is part of an orbit of \(E_{2}E_{1}\), namely \(c \rightarrow f\). This means the cycle decomposition of \(E_{2}E_{1}\) contains a cycle of the form \((\ldots cf\ldots)\).

By a similar argument, the intercepted message code \(ed\) means that \(E_{1}(\beta) = e\) and \(E_{2}(\beta) = d\), where \(\beta\) is the unknown message key; consequently, we know part of an orbit of \(E_{2}E_{1}\), \(e\rightarrow d\), so the cycle decomposition of \(E_{2}E_{1}\) contains a cycle of the form \((\ldots ed\ldots)\).

Now consider \(da\). This tells us part of an orbit of \(E_{2}E_{1}\), namely \(d\rightarrow a\). But we already know \(e \rightarrow d\), which means we can extend our orbit. The intercepted \(ae\) tells \(a\rightarrow e\), which closes the orbit: \[e\rightarrow d \rightarrow a\rightarrow e\] and gives us one cycle \((eda)\) in the cycle decomposition of \(E_{2}E_{1}\).

Likewise, the intercepted \(fb\) allows us to extend the other orbit to  \[c\rightarrow f \rightarrow a.\] Note that we are assuming a six-letter alphabet, so \(b\) must be mapped back to \(c\), giving us the cycle \((cfb)\); consequently, \(E_{2}E_{1} = (eda)(cfb)\).

To explore these ideas further, continue to the Activities for Part 3.1 (Cycle Decomposition).

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

Skip to the overview of Part 3.2 (Rejewski’s Theorems).