How Mathematicians Broke Enigma: Permutation Groups and Conjugation

The one-sentence version

Each keypress on Enigma applies a permutation to the 26 letters. The Polish mathematician Rejewski noticed that when you multiply the permutations for the first few letters of a given day, the cycle type of the product depends only on the rotor positions and not on the plugboard, because the plugboard acts by conjugation, and conjugation doesn't change cycle type. This let him sidestep the plugboard first, shrinking an astronomically large key space to a size that could be looked up in a table.

This article has three layers:

The intuition: how Enigma works and its fatal weaknesses
Real-world use: the Polish breakthrough, Turing's Bombe and the influence on modern cipher design
The mathematics: permutations, cycle decomposition, conjugation, Rejewski's theorem and a worked example

Layer 1: The Intuition

1.1 Enigma is a "substitution machine that keeps changing its table"

The simplest substitution cipher shuffles the alphabet: A→Q, B→W and so on. It is easy to break, because letter frequencies (E is the most common) give it away.

Enigma's improvement: the substitution table changes with every keypress.

Rotors: each rotor contains fixed wiring (a permutation). With each keypress, the rightmost rotor steps one position, carrying over like an odometer.
Reflector: sends the current back through the rotors a second time.
Plugboard: swaps 10 pairs of letters with cables. This step contributes the great majority of the key space.

The total number of keys is on the order of $10^{23}$ . The German military considered it unbreakable.

1.2 Two "conveniences" that became fatal weaknesses

Encryption and decryption are the same operation. Because of the reflector, if A encrypts to G, then G encrypts to A. Operators don't have to switch modes, which is convenient.
No letter ever encrypts to itself. This is also caused by the reflector.

Turing's team later exploited the second point heavily: if you can guess the plaintext of some ciphertext (a weather report is sure to contain "WETTER"), you can slide that word along the ciphertext and rule out every position where a letter matches itself.

1.3 A third weakness: repeated sending

In the 1930s, German operators began each message by sending the 3-letter "message key" twice in a row (6 letters in all), to guard against transmission errors. This means the 1st and 4th ciphertext letters come from the same plaintext letter, as do the 2nd and 5th, and the 3rd and 6th. This is exactly where Rejewski got in.

Layer 2: Real-World Use

The intelligence (code-named Ultra) had a huge effect on the Battle of the Atlantic. A common claim is that it shortened the war by about two years, but estimates like this are hard to verify precisely.
Bletchley Park later also broke the more complex Lorenz cipher machine, and built Colossus to do it, one of the earliest programmable electronic computers.

Lessons for today:

The problem with Enigma	The modern principle
Security relied on keeping the machine's structure secret	Kerckhoffs's principle: the algorithm is fully public, and only the key is secret
The message key was sent twice	Protocol design must not leak relationships between plaintexts
A letter never encrypts to itself	Cipher output must be indistinguishable from random; any bias is a way in
Fixed-format messages ("WETTER")	Ciphers must resist known-plaintext attacks

Layer 3: The Mathematics

3.1 Permutations and cycles

All permutations of the 26 letters form the symmetric group $S_{26}$ . Any permutation can be written uniquely as a product of disjoint cycles, such as

$\sigma = (A\ C\ F)(B\ D)(E)\cdots$

meaning A→C→F→A, B↔D, and E stays fixed. The multiset of cycle lengths is called the cycle type; the one above is "one 3-cycle, one 2-cycle…".

A single Enigma encryption is an involution with no fixed points: it consists of 13 transpositions, and multiplying it by itself gives the identity. This is the algebraic statement of "encryption and decryption are the same" (involution) and "no letter encrypts to itself" (no cycles of length 1).

3.2 Conjugation doesn't change cycle type

A basic fact from abstract algebra: for any $\tau \in S_n$ ,

$\tau\, (a_1\ a_2\ \cdots\ a_k)\, \tau^{-1} = \big(\tau(a_1)\ \tau(a_2)\ \cdots\ \tau(a_k)\big).$

In other words, conjugation only renames the letters in the cycles, and not one cycle length changes. So $\sigma$ and $\tau\sigma\tau^{-1}$ have exactly the same cycle type. Two permutations in $S_n$ are conjugate if and only if they have the same cycle type.

A worked example: conjugation is renaming

In $S_5$ , take $\sigma = (1\ 2\ 3)(4\ 5)$ , and let $\tau$ be $1\mapsto 2,\ 2\mapsto 4,\ 3\mapsto 5,\ 4\mapsto 1,\ 5\mapsto 3$ .

Writing it straight down with the "renaming" rule: $\tau\sigma\tau^{-1} = (\tau(1)\ \tau(2)\ \tau(3))(\tau(4)\ \tau(5)) = (2\ 4\ 5)(1\ 3).$

Verify one point: $\tau\sigma\tau^{-1}(2)$ . First $\tau^{-1}(2) = 1$ , then $\sigma(1) = 2$ , then $\tau(2) = 4$ . The result is $4$ , matching $(2\ 4\ 5)$ .

Both have the cycle type "one 3-cycle + one 2-cycle".

3.3 Rejewski's observation

Let $E_i$ be the encryption permutation at position $i$ on a given day. Then

$E_i = S^{-1}\, T_i\, S,$

where $S$ is the plugboard (itself an involution, $S^{-1} = S$ ), and $T_i$ is the permutation of the rotors plus the reflector at that position.

Because the message key was sent twice, if a plaintext letter $x$ encrypts to $y_1$ at position 1 and to $y_4$ at position 4, then $E_4 E_1$ ( $E_1$ is an involution, so applying $E_1$ first goes from $y_1$ back to $x$ ) sends $y_1$ to $y_4$ . Collecting the openings of a few dozen messages from one day lets you write out the product permutation $E_4 E_1$ completely, without knowing any plaintext.

The key step:

$E_4 E_1 = S^{-1} T_4 S \cdot S^{-1} T_1 S = S^{-1}\,(T_4 T_1)\,S.$

The plugboard $S$ merely performs a conjugation on the outside. So the cycle type of $E_4E_1$ equals the cycle type of $T_4T_1$ , and is completely unaffected by the plugboard.

Rejewski's team then went through the roughly 100,000 combinations of rotor order and starting position, recording the cycle types of $E_4E_1$ , $E_5E_2$ and $E_6E_3$ for each in a card catalog (using a device called the "cyclometer"). After intercepting each day's messages, they computed these three cycle types, looked them up to pin down the rotor settings, and then solved the plugboard separately.

Another theorem

Rejewski also used this: in the product of two involutions with no fixed points, cycles of equal length always come in pairs. So the cycle type of $E_4E_1$ looks like "two $a$ -cycles, two $b$ -cycles…", which is a good way to check data for copying errors.

Summary

Layer	Key points
Intuition	Each keypress changes the substitution table, but the reflector means "no letter encrypts to itself"
Algebra	Each encryption is a fixed-point-free involution in $S_{26}$ ; the plugboard is a conjugation
Breakthrough	Conjugation doesn't change cycle type, so the plugboard is "eliminated" and rotor settings can be looked up
Lessons	Kerckhoffs's principle, no repetition, output indistinguishable from random