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).

 

 

NOTE: In the following, we'll gradually scale our way up towards the full Enigma encryption on 26 letters.

1. Suppose \(E_{1}, E_{2} \) are two Enigma permutations, and \(E_{1} \) contains \((\alpha c) \) while \(E_{2} \) contains \((\alpha f) \). You should assume both contain a number of other transpositions as well.
   1. Prove: \(E_{2}E_{1} ( c) = f \). (In particular, why can we disregard the effect of the other transpositions in \(E_{2}, E_{1} \)?)
   2. Suppose \(E_{1}, E_{2} \) contained the same transposition \((\alpha\beta) \). Find \(E_{2}E_{1}(\alpha) \) and \(E_{2}E_{1}(\beta) \).
2. Suppose \(\sigma = (ab)(cd)(ef) \) and \(\tau = (ab)(cf)(de) \) are two permutations on six symbols.
   1. Find the product \(\sigma\tau \).
   2. Classify the cycles in the product \(\sigma\tau \). In particular: How many 1-cycles? How many 2-cycles? How many 3-cycles?
   3.  \((ab) \) is in both \(\sigma \) and \(\tau \). What do you notice about \(a, b \) in the product \(\sigma\tau \)?
   4. The transposition \((cd) \) is in \(\sigma \). What do you notice about \(c, d \) in the product \(\sigma\tau \)?
   5. The transposition \((de) \) is in \(\tau \). What do you notice about \(d, e \) in the product \(\sigma\tau \)?
3. Suppose \(\alpha = (ab)(cd)(ef)(gh) \) and \(\beta = (ad)(bg)(ce)(fh) \) are two permutations on eight symbols.
   1. Find the product \(\alpha\beta \).
   2. Classify the cycles in the product \(\alpha\beta \). In particular: How many 1-cycles? How many 2-cycles? How many 3-cycles?
   3. What do you notice about the elements of each transposition of \(\alpha \)?
4. Suppose \(\mu = (ab)(ce)(dj)(fg)(kl)(hi) \) and \(\nu = (aj)(cd)(db)(fk)(gl)(hi) \) are two permutations on twelve symbols.
   1. Find \(\mu\nu \).
   2. Classify the cycles in the product \(\mu\nu \).
   3. Suppose \((xy) \) is a transposition in exactly one of \(\mu \) or \(\nu \). What can you say about \(x, y \) in the product \(\mu\nu \)?
5. Note that all the preceding involutions are proper. Suppose \(\kappa = (ab)(cd)(ef) \) and \(\lambda = (ac)(be) \) are two permutations on six symbols.
   1. Find \(\kappa\lambda \).
   2. What happens with products of proper involutions that does not happen when one of the involutions is not proper?

Return to the overview of Part 3.1 (Cycle Decomposition).

Continue to the overview of Part 3.2 (Rejewski's Theorems).

 

 

In the activities for Part 3.1, you might have noticed some intriguing patterns when proper involutions are multiplied:

• The product of proper involutions consists of pairs of cycles of equal length,
• If \((xy)\) is in both involutions, then \(x, y\) appear as 1-cycles in the product of the involutions,
• If \((xy)\) is in exactly one of a pair of proper involutions, then \(x, y\) appear in different cycles of the same length in the product of the involutions.

These patterns are in fact real, for Rejewski proved:

Rejewski’s Theorem.The product of two proper involutions on the same elements can be expressed as a product of pairs of cycles of the same length.

We'll omit the proof here, though it can be found in Rejewski’s paper [Rejewski 1980].

Mathematicians tend to honor theoretical results: hence “Rejewski’s Theorem”. However, this theorem played little role in breaking Enigma, as it simply provides a theoretical guarantee for an observed fact. One is reminded of Hardy’s claim that pure mathematics is useless—the abstract algebra tells us nothing we didn’t already know.

The theorem that actually broke Enigma is an (unnamed) consequence of Rejewski’s Theorem; Rejewski called it a corollary, though its proof is a little more involved than one would expect from a corollary. As with the main theorem, the proof can be found in [Rejewski 1980]. We’ll take the opportunity to give it a name worthy of its significance and call it:

The Enigma Theorem. Let \(\sigma, \tau\) be proper involutions on the same elements. If a transposition \((xy)\) appears in exactly one of the involutions, \(x, y\) will be in different cycles of the same length in the product \(\sigma\tau\); and if \((xy)\) appears in both, \(x, y\) will appear as a 1-cycle in the product.

Consequently, any transposition in exactly one of the \(\sigma, \tau\) must have its elements split between two equal-length cycles in the product.

For example, suppose \(E_{1}, E_{2}\) are proper involutions on our six-letter alphabet, and our intercepted message keys allow us to determine \(E_{2}E_{1} = (afe)(bdc)\). The Enigma theorem permits us to rule out certain possibilities for our encryptions. For example, neither \(E_{1}\) nor \(E_{2}\) can be \((af)(bd)(ce)\), because if either included the transposition \((af)\), then \(a\), \(f\) would be split among different cycles in the product \(E_{2}E_{1}\), instead of being in the same cycle.

There are in fact 15 possible proper involutions on six elements, and so 15 possibilities for each of \(E_{1}\) and \(E_{2}\), and 225 possibilities for the pair of involutions. However, knowing \(E_{2}E_{1} = (afe)(bdc)\) means that \(E_{1}\) and \(E_{2}\) must be one of

\[\begin{array}{cccccc}P             &=               (ab)(fd)(ec)         &Q         &=               (ab)(fc)(ed)         &R         &=               (ad)(fb)(ec)\\S   &=               (ad)(fc)(eb)         &T          &=               (ac)(fb)(ed)         &U         &=               (ac)(fd)(eb)\end{array}\]

Moreover, by the Enigma Theorem, we know that no transposition appears in both. Thus certain choices can be excluded: For example, \(E_{1} = P\) and \(E_{2} = R\) is ruled out, because both contain \((ec)\). In this way, our 225 possibilities for \(E_{1}\) and \(E_{2}\) reduce to just twelve:

• \(E_{1} = P\) and \(E_{2} = S\), or the reverse,
• \(E_{1} = P\) and \(E_{2} = T\), or the reverse,
• \(E_{1} = Q\) and \(E_{2} = R\), or the reverse,
• \(E_{1} = Q\) and \(E_{2} = U\), or the reverse,
• \(E_{1} = R\) and \(E_{2} = U\), or the reverse,
• \(E_{1} = S\) and \(E_{2} = T\), or the reverse.

At this point, we can use trial-and-error (some trial-and-error is necessary in any cryptographic problem); we find \(RQ = (afe)(bdc)\), so \(E_{2} = R\), \(E_{1} = Q\).

To explore these ideas further, continue to the Activities for Part 3.2 (Rejewski’s Theorems).

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

Skip to the overview of Part 3.3 (Breaking the Full Enigma).

 

 

1. Verify the Enigma Theorem for the products of proper involutions in the activities for Part 3.1.
   (That is, for the products \(\sigma\tau \), \(\alpha\beta \), \(\mu\nu \), and \(\kappa\lambda \) in activities 2, 3, 4, and 5 of Part 3.2, respectively.)
2. Let \(E_{1}\), \(E_{2}\) be proper involution on six elements, where \(E_{2}E_{1} = (ade)(bcf)\).
   1. Find the possibilities for the involutions \(E_{1}\), \(E_{2}\).
   2. Find \(E_{1}\), \(E_{2}\).

Return to the overview of Part 3.2 (Rejewski's Theorems.

Continue to the overview of 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.

 

 

 

Note:  If you want to produce your own Enigma encryptions, there are several online Enigma emulators, such as this one.

1. Suppose the following message keys are intercepted:\[\begin{array}{lllllll}rsw \,\,\,\,     sia               & \,\,\,\,\,\,\,\,\,\,&pos \,\,\,\, eyc               &\,\,\,\,\,\,\,\,\,\,&zlo \,\,\,\,qks               &\,\,\,\,\,\,\,\,\,\,&qju \,\,\,\,fdv   \\   wyn \,\,\,bci &&ylo \,\,\,\,dks        &&vll \,\,\,\,okm    &&mwn \,mxi\\ktz \,\,\,\,ygl    \,&&llx \,\,\,\,pkz      &&iaf \,\,\,vqp         &&hln \,\,\,\,hki  \\  ohb \,\,\,zwt &&nwl\, gxm     &&blw \,\,\,jka       &&dll\,\,\,\,ckm\\all \,\,\,\,\,wkm   &&xln \,\,aki       &&uwl \,\,uxm     &&gll \,\,\,\,\,kkm\\eln \,\,\,rki       &&slk \,\,\,lkr             &&flx \,\,\,ikz               &&cle \,\,\,\,\,nkk\\pln \,\,\,eki    &&jlb \,\,\,xkt       &&spq \,\,\,lax        &&rry \,\,\,\,slb\end{array}\]
   1. Find as much of the cycle decomposition of \(E_{4}E_{1}\) as possible.
   2. Find as much of the cycle decomposition of \(E_{5}E_{2}\) as possible.
   3. Find as much of the cycle decomposition of \(E_{6}E_{3}\) as possible.
2. Suppose \(E_{4}\) and \(E_{1}\) are proper involutions. Prove the following.
   1. If both contain a transposition \((\alpha\beta)\), then \(\alpha, \beta\) will not appear in any cycle in the product \(E_{4}E_{1}\).
   2. If \(E_{1}\) contains the transposition \((\alpha\beta)\) and \(E_{4}\) contains the transposition \((\alpha\gamma)\), then \(E_{4}E_{1}\) contains a cycle that includes \((\ldots \beta\gamma \ldots)\).
3. Most histories of cryptography claim that the allied decryption efforts were easier because Enigma operators didn't use randomly chosen letters, but rather used sequences that were easy to type.
   1. Suppose all operators used the message code \(aaa\, aaa\). If this was the message code used by all operators, would it be harder or easier to recover \(E_{4}E_{1}\), and subsequently the Enigma encryptions \(E_{4}\) and \(E_{1}\)?  Why/why not?
   2. What if instead of random letter sequences, operators chose three letter words?  Use the Enigma emulator to encrypt repeated three letter words as message codes. Would this practice make it easier or harder to recover the Enigma encryptions?  Why/why not?
4. Some histories of cryptography claim that the Germans ended their messages with “Heil Hitler!” This isn’t true, but suppose it was. Would the use of such a standard closing message make it easier to break Enigma? Why/why not?  Suggestion: The first “H” would be encrypted using \(E_{k}\) for some value \(k\) that depended on the message length. Could this be used to recover \(E_{k}\)?

Return to the overview of Part 3.3 (Breaking the Full Enigma).

Continue to the Conclusion.