The Theorem that Won the War: 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).