Chapter 11: The Polish Codebreakers: Rejewski’s Mathematical Attack#
“The Enigma machine was a riddle wrapped in a mystery inside an enigma – and it was pure mathematics that unwrapped it.”
In the annals of cryptanalysis, few achievements rival the work of the Polish Cipher Bureau in the 1930s. While the world assumed the Enigma machine to be unbreakable, a young mathematician named Marian Rejewski applied the abstract theory of permutation groups to deduce the internal wiring of the Enigma rotors – from intercepted ciphertext alone. This chapter reconstructs Rejewski’s attack in mathematical detail, beginning with the procedural vulnerability that made it possible (the doubled message key), progressing through the theory of characteristic permutations and their cycle structures, and culminating in a working simulation of the entire attack.
11.1 Historical Context#
11.1.1 The Polish Cipher Bureau (Biuro Szyfrów)#
Poland’s geographical position – sandwiched between Germany and the Soviet Union – made signals intelligence a matter of national survival. In the aftermath of the 1920 Polish-Soviet War, where intercepted radio communications had played a decisive role, the Polish General Staff established the Biuro Szyfrów (Cipher Bureau) and invested heavily in cryptanalytic capacity.
By 1931, the Bureau had recognized that Germany’s increasingly widespread adoption of the Enigma machine for military communications posed a critical intelligence threat. German radio traffic encrypted with Enigma was being intercepted in volume, but none of it could be read. The linguists and classical cryptanalysts on staff – accustomed to breaking hand ciphers – were powerless against the machine’s polyalphabetic complexity.
In a remarkable decision, the Bureau turned to mathematics. A course in cryptology was organized at Poznań University, and the most promising students were recruited. Among them was a 27-year-old mathematician whose name would eventually be spoken in the same breath as Turing and Shannon.
11.1.2 Marian Rejewski (1905–1980)#
Marian Rejewski was born on August 16, 1905, in Bydgoszcz, then part of the German Empire. He studied mathematics at Poznań University and later at Göttingen, where he attended lectures by some of the leading algebraists of the day. His training in abstract algebra – specifically, the theory of permutations and groups – would prove to be the decisive intellectual weapon against Enigma.
Rejewski joined the Cipher Bureau in September 1932. Within three months, working largely alone and armed with intercepted ciphertext, publicly available commercial Enigma documentation, and a set of expired daily keys provided by French intelligence, he accomplished what the rest of the world believed impossible: he deduced the internal wiring of the Enigma rotors using permutation theory.
11.1.3 The French Intelligence Connection#
A crucial ingredient in Rejewski’s success was intelligence provided by Hans-Thilo Schmidt (codenamed “Asche”), a disgruntled employee of the German Cipher Office (Chiffrierstelle). Beginning in 1931, Schmidt sold documents to French intelligence officer Gustave Bertrand, including Enigma operating manuals, daily key tables, and technical specifications. France, unable to exploit the material itself, shared it with Poland.
The key tables gave Rejewski known daily settings for certain months, which he could use to verify his algebraic deductions. But the mathematical framework was entirely his own creation – the intelligence merely provided the foothold from which the algebra could begin its climb.
11.1.4 The Breakthrough (December 1932)#
Rejewski’s breakthrough rested on a single observation: the German operating procedure required each operator to encrypt his chosen message key twice at the start of every message. This procedural regularity created a mathematical structure – a system of permutation equations – that Rejewski could exploit.
By collecting many messages sent on the same day (all using the same daily key but different individual message keys), Rejewski could observe which letters mapped to which other letters at known rotor positions. These observations defined permutations whose cycle structure served as a fingerprint for the rotor configuration.
11.1.5 The Team Expands#
Two other mathematicians from the Poznań recruitment – Jerzy Różycki (1909–1942) and Henryk Zygalski (1908–1978) – joined Rejewski at the Bureau. Together, the trio developed a suite of cryptanalytic tools:
The cyclometer (1934): a device for cataloging the cycle structures of characteristic permutations for all possible rotor positions.
The bomba kryptologiczna (1938): an electromechanical device that automated the search for daily key settings. (This was the precursor to Turing’s Bombe at Bletchley Park.)
Zygalski sheets (1938): perforated cardboard sheets that, when overlaid, revealed rotor positions where certain self-encryptions occurred.
11.1.6 The Handover (July 25, 1939)#
With war approaching and German procedural changes making the Polish methods increasingly difficult to maintain, the Poles made a fateful decision. On July 25, 1939, at a secret meeting in the Kabaty Woods near Pyry, south of Warsaw, Rejewski, Różycki, and Zygalski presented their work to stunned British and French intelligence officers. The Poles handed over reconstructed Enigma machines, the complete mathematical theory, and their cryptanalytic tools. This gift – given just five weeks before Germany invaded Poland – was the foundation on which Bletchley Park built its entire Enigma-breaking operation.
Tip
The power of pure mathematics. Rejewski’s attack is a striking example of abstract mathematics solving a concrete, urgent problem. The theory of permutation groups, developed by Cauchy, Galois, and their successors for purely intellectual reasons, turned out to be exactly the tool needed to crack the most sophisticated cipher machine of its era. As Rejewski himself later wrote: “The Enigma’s secret lay not in its mechanism but in the mathematical properties of permutations – and those properties are eternal.”
11.2 Formal Definitions#
11.2.1 The Enigma Machine as a Permutation System#
Recall from Chapter 10 that each keypress on the Enigma machine implements a permutation of the 26-letter alphabet. The full encryption permutation at any given rotor position is:
where:
\(P\) is the plugboard permutation,
\(H\) encodes the current rotor offsets (ring + position),
\(R_1, R_2, R_3\) are the fixed rotor wiring permutations,
\(U\) is the reflector permutation.
Crucially, the rotors step after each keypress, so the permutation changes with every character.
11.2.2 The Doubled Message Key Procedure (Pre-1938)#
Before September 1938, the German Enigma operating procedure worked as follows:
The daily key (shared by all operators for that day) specified the rotor order, ring settings, plugboard connections, and an initial rotor position called the Grundstellung (ground setting).
For each message, the operator chose a random 3-letter message key (e.g.,
ABC).The operator set the rotors to the Grundstellung and typed the message key twice:
ABCABC.The resulting 6 ciphertext letters (e.g.,
DMQVBN) were transmitted as the message indicator.The operator then set the rotors to the message key position (
ABC) and encrypted the actual message.
Definition 11.1 (Message Indicator)
Let \(E_i\) denote the Enigma encryption permutation at rotor position \(i\) (counting from the Grundstellung). If the operator’s chosen message key consists of letters \((m_1, m_2, m_3)\), the transmitted indicator is:
Note that \(X_1\) and \(X_4\) are both encryptions of \(m_1\), but at different rotor positions (positions 1 and 4 respectively). Similarly for \((X_2, X_5)\) and \((X_3, X_6)\).
11.2.3 Characteristic Permutations#
Definition 11.2 (Characteristic Permutations \(A\), \(B\), \(C\))
From a collection of intercepted message indicators on a single day, define three permutations of the alphabet:
\(A\): the permutation mapping \(X_1 \to X_4\) (i.e., \(A(X_1) = X_4\) for each intercepted message)
\(B\): the permutation mapping \(X_2 \to X_5\)
\(C\): the permutation mapping \(X_3 \to X_6\)
Since each operator chooses a different message key, and the daily key is fixed, each pair \((X_1, X_4)\) relates to a different plaintext letter \(m_1\). If we observe enough messages, we can determine the full permutation \(A\) mapping every possible \(X_1\) to its corresponding \(X_4\). This is a variant of the coupon collector problem: with \(n = 26\) items and three independent collections, roughly 150–200 intercepted messages give a high probability of determining all entries of all three permutations. In practice, Rejewski could supplement near-complete permutations with algebraic deduction (a bijection missing \(k \leq 2\) entries can be completed uniquely).
11.2.4 Rejewski’s Permutation Equations#
The characteristic permutation \(A\) can be expressed algebraically:
because if \(X_1 = E_1(m_1)\) and \(X_4 = E_4(m_1)\), then \(A(X_1) = X_4 = E_4(E_1^{-1}(X_1))\).
Rejewski’s Equations
Expanding \(E_1\) and \(E_4\) in terms of the machine components:
where \(S_i\) denotes the composite rotor permutation at position \(i\) (including offsets). Similarly for \(B = E_5 \circ E_2^{-1}\) and \(C = E_6 \circ E_3^{-1}\).
11.2.5 Cycle Structure as a Fingerprint#
Every permutation in \(S_{26}\) decomposes uniquely (up to ordering) into a product of disjoint cycles. The cycle structure is the multiset of cycle lengths.
Definition 11.3 (Cycle Structure)
The cycle structure of a permutation \(\sigma \in S_n\) is the tuple \((\ell_1, \ell_2, \ldots, \ell_k)\) where \(\ell_1 \geq \ell_2 \geq \cdots \geq \ell_k\) are the lengths of the disjoint cycles, and \(\sum_{i=1}^{k} \ell_i = n\).
For example, the permutation \((A\,B\,C)(D\,E)(F)(G\,H\,I\,J)\) in \(S_{10}\) has cycle structure \((4, 3, 2, 1)\).
11.2.6 The Catalog Method#
Rejewski’s attack strategy was:
Observe the characteristic permutations \(A\), \(B\), \(C\) from the day’s intercepted traffic.
Compute their cycle structures.
Look up the observed cycle structures in a pre-computed catalog that lists the cycle structure of \(A = E_4 \circ E_1^{-1}\) for every possible Grundstellung (\(26^3\) = 17,576 rotor positions, for each of the 6 rotor orderings = 105,456 entries total).
Match to recover the Grundstellung and rotor order.
Danger
The entire attack depends on the Germans’ procedural mistake of encrypting the message key twice. This repetition creates a deterministic relationship between character positions 1 & 4, 2 & 5, and 3 & 6 – a relationship that is independent of the individual message keys chosen by operators and depends only on the daily key. Without the doubling, the characteristic permutations \(A\), \(B\), \(C\) cannot be defined, and the attack collapses.
11.2.7 Deducing the Rotor and Reflector Wirings#
The catalog method of Section 11.2.6 presupposes that we already know the internal wiring of the three rotors (\(R_1, R_2, R_3\)) and the reflector (\(U\)). Without this knowledge, we cannot compute the encryption permutation \(E_i\) for any rotor position, and the entire catalog is impossible to construct. How did Rejewski obtain these wirings?
The Problem#
The commercial Enigma was publicly available, and its mechanical design — the arrangement of rotors, reflector, plugboard, and stepping mechanism — was well understood. However, the German military version used different internal wiring for each rotor and for the reflector. The wiring is what defines the permutation each component implements, and it was classified. Rejewski needed to recover these unknown permutations from external observations alone.
What Rejewski Had#
Rejewski’s work rested on three sources of information:
Commercial Enigma documentation (publicly available): this gave him the mechanical design and the general structure of the encryption formula, but not the military wiring.
Schmidt’s leaked documents: Hans-Thilo Schmidt, a German cipher clerk recruited by French intelligence, provided daily key tables for certain months. These tables specified the plugboard setting \(P\), the rotor order, and the Grundstellung for each day.
Intercepted ciphertext from those same months: the Polish Cipher Bureau routinely intercepted German military radio traffic.
Historical Note
The commercial Enigma connected the keyboard to the entry wheel (Eintrittswalze) in QWERTY order — the letters were wired to rotor contacts in the order they appear on a German typewriter keyboard. Rejewski initially assumed the military version did the same. When he substituted this assumption into his equations, the results were nonsensical — the recovered permutations failed basic consistency checks. He then tried the simplest possible hypothesis: alphabetical order (\(A \to 1, B \to 2, \ldots, Z \to 26\)). Everything fell into place immediately. Rejewski later called this a “triumph of the intelligence analyst’s method of exhaustive hypothesis testing.” This seemingly minor discovery was essential — without the correct entry permutation, none of the subsequent algebra would have worked.
The Mathematical Framework#
Consider a day for which Schmidt’s tables provide the daily key. On such a day:
The plugboard permutation \(P\) is known.
The rotor order is known, fixing which physical rotors occupy positions \(R_1\), \(R_2\), \(R_3\).
The Grundstellung is known, so the rotor offset permutations \(H_1, H_2, \ldots, H_6\) at indicator positions 1 through 6 are known.
Recall from Section 11.2.1 that the Enigma encryption permutation at position \(i\) is:
where \(L = R_1 \cdot R_2 \cdot R_3\) is the composite rotor wiring (the product of the three rotor permutations). Since \(P\) and \(H_i\) are known from the leaked tables, Rejewski could compute:
This operation strips off the known components (\(P\) and \(H_i\)), leaving a permutation \(E_i'\) that depends only on the unknown rotor wirings and reflector. The permutation \(E_i\) itself is observable: it can be reconstructed from intercepted indicators using the same procedure that yields the characteristic permutations.
The Key Simplification#
During the 6-letter indicator encryption, typically only the rightmost rotor (\(R_3\)) steps. The middle and left rotors remain stationary because the indicator is too short to trigger the turnover mechanism. If we denote the right rotor’s position offset at keystroke \(i\) as \(\rho_i\), then:
where \(R_3(\rho_i)\) denotes the right rotor permutation at offset \(\rho_i\). The offsets \(\rho_i\) are known — they are consecutive integers modulo 26, determined by the Grundstellung.
Solving the Equations#
Theorem 11.4 (Rotor Isolation)
Let \(E_i'\) and \(E_j'\) be the stripped permutations at indicator positions \(i\) and \(j\) respectively. Then their composition eliminates all components except the right rotor:
Proof. Expanding using the expression above:
The inner terms cancel: \(R_3^{-1}(\rho_i) \cdot R_3(\rho_j) \cdot R_2 \cdot R_1 \cdot U \cdot R_1^{-1} \cdot R_2^{-1}\) reduces because the inverse reverses the second factor, yielding \(R_3(\rho_i) \cdot R_3^{-1}(\rho_j)\). \(\square\)
The right-hand side \(R_3(\rho_i) \cdot R_3^{-1}(\rho_j)\) depends only on the unknown right rotor wiring and the known offsets \(\rho_i, \rho_j\). With enough indicator data from days with known settings, Rejewski obtained an overdetermined system of equations in the 26 unknown values of \(R_3\). Each equation constrains some of these values, and the system could be solved — effectively recovering the right rotor’s wiring one constraint at a time.
Recovering All Rotors and the Reflector#
Identifying each rotor separately. The Germans periodically changed the rotor order as part of the daily key. By collecting data from different periods (using the leaked daily key tables), Rejewski could identify when a different physical rotor occupied the rightmost position. Applying the rotor isolation technique to each configuration, he recovered each rotor’s wiring independently.
Recovering the reflector. Once all three rotor wirings \(R_1, R_2, R_3\) were known, the composite \(L = R_1 \cdot R_2 \cdot R_3\) was determined. The reflector could then be recovered from any single stripped equation:
Completion. Rejewski completed the full recovery of all rotor and reflector wirings by December 1932 — barely a few months after receiving Schmidt’s documents. This was an achievement that took the combined efforts of British and French intelligence years to match, and it relied on a striking combination of espionage data and mathematical reasoning.
Tip
The applet at ../applets/wiring-deduction.html demonstrates this wiring deduction process interactively. You can step through the algebra with concrete rotor offsets and observe how each intercepted indicator contributes constraints that progressively pin down the unknown wiring.
11.3 Implementation#
We begin by implementing a self-contained Enigma machine, then build the full Rejewski attack on top of it.
11.3.1 Enigma Machine#
The following implementation provides the core Enigma encryption needed for this chapter. For a full treatment of the machine’s design, see Chapter 10.
import numpy as np
class EnigmaMachine:
"""Simplified Enigma simulator for Rejewski's attack."""
ROTOR_WIRINGS = {
'I': 'EKMFLGDQVZNTOWYHXUSPAIBRCJ',
'II': 'AJDKSIRUXBLHWTMCQGZNPYFVOE',
'III': 'BDFHJLCPRTXVZNYEIWGAKMUSQO',
'IV': 'ESOVPZJAYQUIRHXLNFTGKDCMWB',
'V': 'VZBRGITYUPSDNHLXAWMJQOFECK',
}
NOTCHES = {
'I': ord('Q') - ord('A'),
'II': ord('E') - ord('A'),
'III': ord('V') - ord('A'),
'IV': ord('J') - ord('A'),
'V': ord('Z') - ord('A'),
}
REFLECTOR_B = 'YRUHQSLDPXNGOKMIEBFZCWVJAT'
def __init__(self, rotor_order, ring_settings, plugboard_pairs,
initial_positions):
self.rotor_names = rotor_order
self.ring_settings = list(ring_settings)
self.positions = list(initial_positions)
self.rotors_fwd = []
self.rotors_inv = []
for name in rotor_order:
wiring = self.ROTOR_WIRINGS[name]
fwd = np.array([ord(c) - ord('A') for c in wiring], dtype=int)
inv = np.zeros(26, dtype=int)
for i in range(26):
inv[fwd[i]] = i
self.rotors_fwd.append(fwd)
self.rotors_inv.append(inv)
self.notches = [self.NOTCHES[name] for name in rotor_order]
self.reflector = np.array(
[ord(c) - ord('A') for c in self.REFLECTOR_B], dtype=int
)
self.plugboard = np.arange(26, dtype=int)
for a, b in plugboard_pairs:
ia = ord(a.upper()) - ord('A')
ib = ord(b.upper()) - ord('A')
self.plugboard[ia] = ib
self.plugboard[ib] = ia
def reset(self, positions):
"""Reset rotor positions."""
self.positions = list(positions)
def _step_rotors(self):
"""Advance the rotors (with double-stepping).
The ring setting offsets the visible position at which the notch
triggers turnover, so we compare against
``(notch + ring_setting) % 26``.
"""
notch_mid = (self.notches[1] + self.ring_settings[1]) % 26
notch_right = (self.notches[2] + self.ring_settings[2]) % 26
if self.positions[1] == notch_mid:
self.positions[1] = (self.positions[1] + 1) % 26
self.positions[0] = (self.positions[0] + 1) % 26
elif self.positions[2] == notch_right:
self.positions[1] = (self.positions[1] + 1) % 26
self.positions[2] = (self.positions[2] + 1) % 26
def _pass_through_rotor(self, letter, rotor_idx, forward=True):
"""Pass a letter through one rotor."""
offset = self.positions[rotor_idx] - self.ring_settings[rotor_idx]
entry = (letter + offset) % 26
if forward:
exit_val = self.rotors_fwd[rotor_idx][entry]
else:
exit_val = self.rotors_inv[rotor_idx][entry]
return (exit_val - offset) % 26
def encrypt_letter(self, letter_idx):
"""Encrypt a single letter (0-25). Steps rotors first."""
self._step_rotors()
x = self.plugboard[letter_idx]
x = self._pass_through_rotor(x, 2, forward=True)
x = self._pass_through_rotor(x, 1, forward=True)
x = self._pass_through_rotor(x, 0, forward=True)
x = self.reflector[x]
x = self._pass_through_rotor(x, 0, forward=False)
x = self._pass_through_rotor(x, 1, forward=False)
x = self._pass_through_rotor(x, 2, forward=False)
x = self.plugboard[x]
return x
def encrypt_text(self, text):
"""Encrypt a string of uppercase letters."""
result = []
for ch in text.upper():
if 'A' <= ch <= 'Z':
idx = ord(ch) - ord('A')
enc = self.encrypt_letter(idx)
result.append(chr(enc + ord('A')))
return ''.join(result)
def get_enigma_permutation(enigma, position):
"""Compute the encryption permutation at a specific position."""
perm = np.zeros(26, dtype=int)
for i in range(26):
enigma.reset(list(position))
perm[i] = enigma.encrypt_letter(i)
return perm
# --- Quick test ---
enigma = EnigmaMachine(
rotor_order=['I', 'II', 'III'],
ring_settings=[0, 0, 0],
plugboard_pairs=[],
initial_positions=[0, 0, 0]
)
enigma.reset([0, 0, 0])
ct = enigma.encrypt_text('HELLOWORLD')
enigma.reset([0, 0, 0])
pt = enigma.encrypt_text(ct)
print(f"Plaintext: HELLOWORLD")
print(f"Encrypted: {ct}")
print(f"Decrypted: {pt}")
print(f"Round-trip: {'PASS' if pt == 'HELLOWORLD' else 'FAIL'}")
perm = get_enigma_permutation(enigma, [0, 0, 0])
print(f"\nPermutation at position [0,0,0]:")
print(f" {' '.join(chr(i + ord('A')) for i in range(26))}")
print(f" {' '.join(chr(p + ord('A')) for p in perm)}")
self_maps = sum(1 for i in range(26) if perm[i] == i)
print(f" Self-mappings: {self_maps} (should be 0)")
Plaintext: HELLOWORLD
Encrypted: ILBDAAMTAZ
Decrypted: HELLOWORLD
Round-trip: PASS
Permutation at position [0,0,0]:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B A Q M F E X I H S W P D Y T L C V J O Z R K G N U
Self-mappings: 0 (should be 0)
11.3.2 The Rejewski Attack Class#
We now implement the core of Rejewski’s attack: simulating the doubled-key procedure, extracting characteristic permutations, computing cycle structures, building the catalog, and performing lookup.
import numpy as np
class RejewskiAttack:
"""Simulate Rejewski's characteristic permutation attack on Enigma."""
def __init__(self, enigma):
self.enigma = enigma
def simulate_message_keys(self, n_messages, grundstellung, rng=None):
"""Simulate n operators encrypting doubled message keys."""
if rng is None:
rng = np.random.default_rng()
indicators = []
for _ in range(n_messages):
msg_key = rng.integers(0, 26, size=3).tolist()
doubled = msg_key + msg_key
self.enigma.reset(list(grundstellung))
encrypted = []
for letter in doubled:
encrypted.append(self.enigma.encrypt_letter(letter))
indicators.append({
'plain_key': msg_key,
'indicator': encrypted
})
return indicators
def extract_characteristics(self, indicators):
"""Extract permutations A, B, C from intercepted indicators."""
A = np.full(26, -1, dtype=int)
B = np.full(26, -1, dtype=int)
C = np.full(26, -1, dtype=int)
for msg in indicators:
ind = msg['indicator']
x1, x2, x3, x4, x5, x6 = ind
A[x1] = x4
B[x2] = x5
C[x3] = x6
coverage = (int(np.sum(A >= 0)), int(np.sum(B >= 0)),
int(np.sum(C >= 0)))
return A, B, C, coverage
@staticmethod
def cycle_structure(permutation):
"""Compute cycle decomposition and cycle structure."""
visited = set()
cycles = []
for start in range(len(permutation)):
if start in visited or permutation[start] < 0:
continue
cycle = []
current = start
while current not in visited:
visited.add(current)
cycle.append(current)
current = permutation[current]
cycles.append(cycle)
structure = tuple(sorted([len(c) for c in cycles], reverse=True))
return cycles, structure
def compute_characteristic_from_position(self, grundstellung):
"""Compute exact A, B, C for a given Grundstellung."""
perms = []
for pos_idx in range(6):
perm_at_pos = np.zeros(26, dtype=int)
for letter in range(26):
self.enigma.reset(list(grundstellung))
for _ in range(pos_idx):
self.enigma.encrypt_letter(0)
perm_at_pos[letter] = self.enigma.encrypt_letter(letter)
perms.append(perm_at_pos)
E1, E2, E3, E4, E5, E6 = perms
E1_inv = np.zeros(26, dtype=int)
E2_inv = np.zeros(26, dtype=int)
E3_inv = np.zeros(26, dtype=int)
for i in range(26):
E1_inv[E1[i]] = i
E2_inv[E2[i]] = i
E3_inv[E3[i]] = i
A = np.array([E4[E1_inv[x]] for x in range(26)], dtype=int)
B = np.array([E5[E2_inv[x]] for x in range(26)], dtype=int)
C = np.array([E6[E3_inv[x]] for x in range(26)], dtype=int)
return A, B, C
def build_catalog(self, rotor_order, ring_settings):
"""Build catalog of cycle structures for all 26^3 positions.
The catalog is constructed **without a plugboard**. Rejewski's
key insight is that the characteristic permutations A, B, C are
conjugated by the plugboard: A_obs = P * A_rotor * P^{-1}.
Conjugation preserves cycle structure, so the cycle-structure
triple is independent of the plugboard and depends only on the
rotor core (rotor order, ring settings, and Grundstellung).
"""
catalog = {}
temp_enigma = EnigmaMachine(rotor_order, ring_settings,
[], [0, 0, 0])
temp_attack = RejewskiAttack(temp_enigma)
for a in range(26):
for b in range(26):
for c in range(26):
grund = [a, b, c]
Ap, Bp, Cp = temp_attack.compute_characteristic_from_position(grund)
_, sA = self.cycle_structure(Ap)
_, sB = self.cycle_structure(Bp)
_, sC = self.cycle_structure(Cp)
key = (sA, sB, sC)
if key not in catalog:
catalog[key] = []
catalog[key].append(tuple(grund))
return catalog
@staticmethod
def complete_permutation(perm):
"""Fill missing entries of a near-complete permutation.
If k <= 2 entries are missing, deduce them:
- k=1: unique completion
- k=2: two possibilities; eliminate any where perm[i]==i
(Enigma never maps a letter to itself)
Returns (completed_perm, exact) where exact=True if completion
is uniquely determined.
"""
perm = perm.copy()
import numpy as np
missing_pos = [i for i in range(26) if perm[i] < 0]
used_vals = set(perm[i] for i in range(26) if perm[i] >= 0)
missing_vals = [v for v in range(26) if v not in used_vals]
k = len(missing_pos)
if k == 0:
return perm, True
elif k == 1:
perm[missing_pos[0]] = missing_vals[0]
return perm, True
elif k == 2:
p0, p1 = missing_pos
v0, v1 = missing_vals
# Option A: perm[p0]=v0, perm[p1]=v1
# Option B: perm[p0]=v1, perm[p1]=v0
# Eliminate options where perm[i]==i (Enigma self-map)
optA_valid = (p0 != v0) and (p1 != v1)
optB_valid = (p0 != v1) and (p1 != v0)
if optA_valid and not optB_valid:
perm[p0], perm[p1] = v0, v1
return perm, True
elif optB_valid and not optA_valid:
perm[p0], perm[p1] = v1, v0
return perm, True
elif optA_valid and optB_valid:
# Both valid; pick option A (cannot uniquely determine)
perm[p0], perm[p1] = v0, v1
return perm, False
else:
# Neither valid (shouldn't happen for Enigma); pick A
perm[p0], perm[p1] = v0, v1
return perm, False
else:
# k > 2: cannot reliably complete
return perm, False
@staticmethod
def lookup_position(observed_A, observed_B, observed_C, catalog):
"""Find Grundstellungen matching observed cycle structures."""
key = (observed_A, observed_B, observed_C)
return catalog.get(key, [])
print("RejewskiAttack class loaded successfully.")
RejewskiAttack class loaded successfully.
11.4 Key Results#
Theorem 11.1 (Independence of Characteristic Permutations)
The characteristic permutations \(A\), \(B\), \(C\) are fully determined by the daily key (rotor order, ring settings, plugboard connections, and Grundstellung). They are independent of the individual message keys chosen by operators.
Proof. Fix a daily key and Grundstellung. Let \(E_1, E_2, \ldots, E_6\) be the encryption permutations at the first six rotor positions. For any message key \((m_1, m_2, m_3)\), the indicator is \((E_1(m_1), E_2(m_2), E_3(m_3), E_4(m_1), E_5(m_2), E_6(m_3))\).
The permutation \(A\) satisfies \(A(E_1(m_1)) = E_4(m_1)\) for all \(m_1\), so \(A = E_4 \circ E_1^{-1}\). This expression involves only \(E_1\) and \(E_4\), which depend on the daily key and rotor positions 1 and 4 – not on the message key. The same argument applies to \(B = E_5 \circ E_2^{-1}\) and \(C = E_6 \circ E_3^{-1}\). \(\square\)
Theorem 11.2 (Expected Number of Cycles in a Random Permutation)
For a uniformly random permutation \(\sigma \in S_n\), the expected number of cycles is:
where \(H_n\) is the \(n\)-th harmonic number. For \(n = 26\):
Proof sketch. Define the indicator random variable \(X_k = 1\) if element \(k\) is a cycle leader (the smallest element in its cycle). By symmetry, element \(k\) is the smallest among its cycle of length \(\ell\) with probability \(1/\ell\). Summing over a different decomposition: element \(k\) starts a new cycle (is a record in the permutation written in one-line notation of cycles sorted by smallest element) with probability \(1/k\). Therefore \(\mathbb{E}[\text{cycles}] = \sum_{k=1}^n \mathbb{E}[X_k] = \sum_{k=1}^n 1/k = H_n\). \(\square\)
Corollary 11.1
The cycle structure of a permutation in \(S_{26}\) provides enough information to dramatically narrow down the rotor positions. The number of distinct cycle structures in \(S_{26}\) equals the number of partitions of 26, which is \(p(26) = 2{,}436\). Since there are \(26^3 = 17{,}576\) possible Grundstellungen per rotor order, the average number of positions sharing a given cycle structure triple is extremely small; using all three permutations together typically yields a unique solution or very few candidates.
Experiments#
Experiment 1: Simulating the Doubled-Key Procedure#
We simulate 200 operators sending messages on the same day, each choosing a random 3-letter message key and encrypting it twice. We display the interception table – exactly what Rejewski would have had in front of him.
import numpy as np
ROTOR_ORDER = ['II', 'IV', 'V']
RING_SETTINGS = [1, 13, 22]
PLUGBOARD = [('A', 'M'), ('F', 'I'), ('N', 'V'), ('P', 'S'),
('T', 'U'), ('W', 'Z')]
GRUNDSTELLUNG = [7, 14, 3] # H, O, D
enigma_daily = EnigmaMachine(
rotor_order=ROTOR_ORDER,
ring_settings=RING_SETTINGS,
plugboard_pairs=PLUGBOARD,
initial_positions=GRUNDSTELLUNG
)
attack = RejewskiAttack(enigma_daily)
rng = np.random.default_rng(42)
indicators = attack.simulate_message_keys(200, GRUNDSTELLUNG, rng=rng)
print("INTERCEPTED MESSAGE INDICATORS")
print("=" * 62)
print(f"Daily settings: Rotors={ROTOR_ORDER}, Ring={RING_SETTINGS}")
print(f"Grundstellung: {[chr(g + ord('A')) for g in GRUNDSTELLUNG]}")
print(f"Plugboard: {PLUGBOARD}")
print(f"Number of intercepted messages: {len(indicators)}")
print()
print(f"{'#':>3s} {'Msg Key':>7s} "
f"{'X1':>2s} {'X2':>2s} {'X3':>2s} {'X4':>2s} {'X5':>2s} {'X6':>2s} "
f"{'Indicator'}")
print("-" * 55)
for i, msg in enumerate(indicators[:30]):
mk = ''.join(chr(m + ord('A')) for m in msg['plain_key'])
ind = msg['indicator']
ind_str = ''.join(chr(x + ord('A')) for x in ind)
xs = [chr(x + ord('A')) for x in ind]
print(f"{int(i+1):3d} {mk:>7s} "
f"{xs[0]:>2s} {xs[1]:>2s} {xs[2]:>2s} {xs[3]:>2s} {xs[4]:>2s} {xs[5]:>2s} "
f"{ind_str}")
if len(indicators) > 30:
print(f"... ({len(indicators) - 30} more messages)")
print()
print("Note: The 'Msg Key' column is SECRET -- Rejewski never saw it.")
print("He only observed the indicator columns X1 through X6.")
INTERCEPTED MESSAGE INDICATORS
==============================================================
Daily settings: Rotors=['II', 'IV', 'V'], Ring=[1, 13, 22]
Grundstellung: ['H', 'O', 'D']
Plugboard: [('A', 'M'), ('F', 'I'), ('N', 'V'), ('P', 'S'), ('T', 'U'), ('W', 'Z')]
Number of intercepted messages: 200
# Msg Key X1 X2 X3 X4 X5 X6 Indicator
-------------------------------------------------------
1 CUR J C Q X O I JCQXOI
2 LLW O R N M P K ORNMPK
3 CSF J Z K X X A JZKXXA
4 CNZ J Q T X T U JQTXTU
5 TTS I P P H N C IPPHNC
6 UND X Q E Y T H XQEYTH
7 VLN R R W D P O RRWDPO
8 JEY C A X F I V CAXFIV
9 UQK X N F Y D W XNFYDW
10 VOL R D A D U T RDADUT
11 LFC O J I M B S OJIMBS
12 OXB L G J A S X LGJASX
13 WVH A B U E R D ABUERD
14 QET F A Z S I L FAZSIL
15 SJB N F J Q Y X NFJQYX
16 ZLX E R Y K P B ERYKPB
17 RUT V C Z N O L VCZNOL
18 FJM Q F G J Y J QFGJYJ
19 MBO B V V L F N BVVLFN
20 ETR Z P Q W N I ZPQWNI
21 XTJ U P B C N M UPBCNM
22 ZKI E H C K C R EHCKCR
23 XJB U F J C Y X UFJCYX
24 MUE B C D L O G BCDLOG
25 MDR B O Q L Q I BOQLQI
26 MIF B M K L E A BMKLEA
27 ORY L L X A V V LLXAVV
28 LEV O A O M I Y OAOMIY
29 QSC F Z I S X S FZISXS
30 ITV T P O G N Y TPOGNY
... (170 more messages)
Note: The 'Msg Key' column is SECRET -- Rejewski never saw it.
He only observed the indicator columns X1 through X6.
Experiment 2: Extracting Characteristic Permutations#
From the 60 intercepted indicators, we extract the characteristic permutations \(A\), \(B\), \(C\) and display their cycle structures.
import numpy as np
A, B, C, coverage = attack.extract_characteristics(indicators)
print("CHARACTERISTIC PERMUTATIONS")
print("=" * 60)
print(f"Raw coverage: A={coverage[0]}/26, B={coverage[1]}/26, "
f"C={coverage[2]}/26")
# Apply completion logic for any near-complete permutations
A, A_exact_flag = RejewskiAttack.complete_permutation(A)
B, B_exact_flag = RejewskiAttack.complete_permutation(B)
C, C_exact_flag = RejewskiAttack.complete_permutation(C)
cov_after = (int(np.sum(A >= 0)), int(np.sum(B >= 0)),
int(np.sum(C >= 0)))
print(f"After completion: A={cov_after[0]}/26, B={cov_after[1]}/26, "
f"C={cov_after[2]}/26")
print(f"Completion exact: A={A_exact_flag}, B={B_exact_flag}, "
f"C={C_exact_flag}")
print()
alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
for name, perm in [('A (X1->X4)', A), ('B (X2->X5)', B),
('C (X3->X6)', C)]:
print(f"Permutation {name}:")
top = ' ' + ' '.join(alphabet[i] for i in range(26))
bot = ' ' + ' '.join(
alphabet[perm[i]] if perm[i] >= 0 else '?' for i in range(26)
)
print(top)
print(bot)
if all(perm >= 0):
cycles, structure = RejewskiAttack.cycle_structure(perm)
cycle_str = ' '.join(
'(' + ' '.join(alphabet[x] for x in cyc) + ')'
for cyc in cycles
)
print(f" Cycles: {cycle_str}")
print(f" Structure: {structure}")
print(f" Number of cycles: {len(cycles)}")
print()
# Exact computation for verification
A_exact, B_exact, C_exact = attack.compute_characteristic_from_position(
GRUNDSTELLUNG
)
print("VERIFICATION (exact vs. extracted):")
if all(A >= 0):
print(f" A matches: {np.array_equal(A, A_exact)}")
if all(B >= 0):
print(f" B matches: {np.array_equal(B, B_exact)}")
if all(C >= 0):
print(f" C matches: {np.array_equal(C, C_exact)}")
CHARACTERISTIC PERMUTATIONS
============================================================
Raw coverage: A=26/26, B=26/26, C=26/26
After completion: A=26/26, B=26/26, C=26/26
Completion exact: A=True, B=True, C=True
Permutation A (X1->X4):
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
E L F Z K S B U H X V A P Q M I J D R G C N O Y T W
Cycles: (A E K V N Q J X Y T G B L) (C F S R D Z W O M P I H U)
Structure: (13, 13)
Number of cycles: 2
Permutation B (X2->X5):
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
I R O U Z Y S C H B M V E D Q N T P A L K F J W G X
Cycles: (A I H C O Q T L V F Y G S) (B R P N D U K M E Z X W J)
Structure: (13, 13)
Number of cycles: 2
Permutation C (X3->X6):
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
T M R G H W J Z S X A F E K Y C I P Q U D N O V B L
Cycles: (A T U D G J X V N K) (B M E H Z L F W O Y) (C R P) (I S Q)
Structure: (10, 10, 3, 3)
Number of cycles: 4
VERIFICATION (exact vs. extracted):
A matches: True
B matches: True
C matches: True
Experiment 3: Cycle Structure Visualization#
The cycle structure of a permutation can be visualized as a directed graph: each element points to its image, and the graph decomposes into disjoint directed cycles.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import FancyArrowPatch, Circle
def plot_permutation_cycles(permutation, title, ax):
"""Plot cycle structure with clear circular layouts, one cycle per group."""
cycles, structure = RejewskiAttack.cycle_structure(permutation)
alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
cycles_sorted = sorted(cycles, key=len, reverse=True)
n_cycles = len(cycles_sorted)
colors = plt.cm.tab10(np.linspace(0, 1, max(n_cycles, 1)))
# Compute layout: place cycles in a row, centered
# Each cycle gets a bounding box of diameter = 2*radius + padding
radii = []
for cycle in cycles_sorted:
n = len(cycle)
if n == 1:
radii.append(0.4)
elif n == 2:
radii.append(0.7)
else:
radii.append(0.42 * n / (2 * np.sin(np.pi / n)) + 0.1)
gap = 1.2
total_width = sum(2 * r for r in radii) + gap * (n_cycles - 1)
cx_start = -total_width / 2
all_x, all_y = [], []
cursor = cx_start
for ci, (cycle, radius) in enumerate(zip(cycles_sorted, radii)):
n = len(cycle)
color = colors[ci]
cx = cursor + radius
cy = 0
cursor += 2 * radius + gap
positions = {}
for i, elem in enumerate(cycle):
angle = -2 * np.pi * i / n + np.pi / 2
px = cx + radius * np.cos(angle)
py = cy + radius * np.sin(angle)
positions[elem] = (px, py)
all_x.append(px)
all_y.append(py)
node = Circle(
(px, py), 0.32, facecolor=color, edgecolor='#333',
linewidth=1.2, zorder=3, alpha=0.85
)
ax.add_patch(node)
ax.text(px, py, alphabet[elem], ha='center', va='center',
fontsize=8, fontweight='bold', color='white',
zorder=4, family='monospace')
# Draw arrows along the cycle
for i in range(n):
s = cycle[i]
e = cycle[(i + 1) % n]
sx, sy = positions[s]
ex, ey = positions[e]
dx, dy = ex - sx, ey - sy
dist = np.sqrt(dx**2 + dy**2)
if dist > 0:
shrink = 0.35
ax.annotate(
'', xy=(ex, ey), xytext=(sx, sy),
arrowprops=dict(
arrowstyle='->', color='#555', lw=1.2,
shrinkA=shrink * 28, shrinkB=shrink * 28,
connectionstyle=f'arc3,rad={0.25 if n > 2 else 0.4}'
), zorder=2
)
# Label: cycle length below
ax.text(cx, cy - radius - 0.7, f'{n}-cycle',
ha='center', va='top', fontsize=8, color='#666',
fontstyle='italic')
margin = 1.5
ax.set_xlim(min(all_x) - margin, max(all_x) + margin)
ax.set_ylim(min(all_y) - margin - 0.5, max(all_y) + margin)
ax.set_aspect('equal')
ax.axis('off')
ax.set_title(title, fontsize=11, fontweight='bold', pad=12)
fig, axes = plt.subplots(3, 1, figsize=(14, 16))
_, sA = RejewskiAttack.cycle_structure(A_exact)
_, sB = RejewskiAttack.cycle_structure(B_exact)
_, sC = RejewskiAttack.cycle_structure(C_exact)
plot_permutation_cycles(
A_exact, f'Permutation A (positions 1→4) — Cycle structure: {sA}', axes[0]
)
plot_permutation_cycles(
B_exact, f'Permutation B (positions 2→5) — Cycle structure: {sB}', axes[1]
)
plot_permutation_cycles(
C_exact, f'Permutation C (positions 3→6) — Cycle structure: {sC}', axes[2]
)
fig.suptitle(
'Figure 11.1: Cycle Structures of Characteristic Permutations A, B, C',
fontsize=14, fontweight='bold', y=0.98
)
plt.tight_layout(rect=[0, 0, 1, 0.96])
plt.savefig('fig_11_1_cycle_structures.png', dpi=150,
bbox_inches='tight', facecolor='white')
plt.show()
print(f"Cycle structure of A: {sA}")
print(f"Cycle structure of B: {sB}")
print(f"Cycle structure of C: {sC}")
Cycle structure of A: (13, 13)
Cycle structure of B: (13, 13)
Cycle structure of C: (10, 10, 3, 3)
Experiment 4: Catalog Construction and Lookup#
Building the full catalog for the Enigma (\(26^3 = 17{,}576\) positions per rotor order) is computationally intensive. To demonstrate the principle, we build the catalog for a subset of 1000 random Grundstellungen and show how the lookup works.
import numpy as np
rng_cat = np.random.default_rng(123)
sampled_positions = set()
sampled_positions.add(tuple(GRUNDSTELLUNG))
while len(sampled_positions) < 1000:
pos = tuple(rng_cat.integers(0, 26, size=3).tolist())
sampled_positions.add(pos)
sampled_positions = sorted(sampled_positions)
print(f"Building partial catalog with {len(sampled_positions)} "
f"Grundstellungen...")
print(f"(True Grundstellung {tuple(GRUNDSTELLUNG)} is included.)")
# Build the catalog WITHOUT a plugboard. Rejewski's key insight is that
# conjugation by the plugboard preserves cycle structure, so the catalog
# needs only the rotor-core permutations.
catalog = {}
temp_enigma = EnigmaMachine(
rotor_order=ROTOR_ORDER, ring_settings=RING_SETTINGS,
plugboard_pairs=[], initial_positions=[0, 0, 0]
)
temp_attack = RejewskiAttack(temp_enigma)
for pos in sampled_positions:
Ap, Bp, Cp = temp_attack.compute_characteristic_from_position(list(pos))
_, s_A = RejewskiAttack.cycle_structure(Ap)
_, s_B = RejewskiAttack.cycle_structure(Bp)
_, s_C = RejewskiAttack.cycle_structure(Cp)
key = (s_A, s_B, s_C)
if key not in catalog:
catalog[key] = []
catalog[key].append(pos)
print(f"Catalog built: {len(catalog)} distinct cycle structure triples.")
_, obs_sA = RejewskiAttack.cycle_structure(A_exact)
_, obs_sB = RejewskiAttack.cycle_structure(B_exact)
_, obs_sC = RejewskiAttack.cycle_structure(C_exact)
print(f"\nObserved cycle structures:")
print(f" A: {obs_sA}")
print(f" B: {obs_sB}")
print(f" C: {obs_sC}")
matches = RejewskiAttack.lookup_position(
obs_sA, obs_sB, obs_sC, catalog
)
print(f"\nCatalog lookup results:")
print(f" Number of matches: {len(matches)}")
for match in matches:
ml = ''.join(chr(m + ord('A')) for m in match)
tag = " <-- TRUE" if list(match) == GRUNDSTELLUNG else ""
print(f" Position: {match} = {ml}{tag}")
sizes = [len(v) for v in catalog.values()]
print(f"\nCatalog statistics:")
print(f" Unique triples: {len(catalog)}")
print(f" Avg positions per triple: {float(np.mean(sizes)):.2f}")
print(f" Max positions per triple: {max(sizes)}")
print(f" Unique matches: {sum(1 for s in sizes if s == 1)}")
Building partial catalog with 1000 Grundstellungen...
(True Grundstellung (7, 14, 3) is included.)
Catalog built: 813 distinct cycle structure triples.
Observed cycle structures:
A: (13, 13)
B: (13, 13)
C: (10, 10, 3, 3)
Catalog lookup results:
Number of matches: 12
Position: (2, 14, 12) = COM
Position: (3, 18, 25) = DSZ
Position: (7, 14, 3) = HOD <-- TRUE
Position: (8, 4, 13) = IEN
Position: (10, 19, 2) = KTC
Position: (13, 6, 6) = NGG
Position: (13, 6, 24) = NGY
Position: (17, 1, 5) = RBF
Position: (19, 22, 14) = TWO
Position: (21, 17, 14) = VRO
Position: (23, 19, 24) = XTY
Position: (24, 6, 17) = YGR
Catalog statistics:
Unique triples: 813
Avg positions per triple: 1.23
Max positions per triple: 15
Unique matches: 716
Experiment 5: Historical Timeline (1926–1939)#
The following annotated timeline traces the key events from the adoption of the Enigma machine by the German military to the historic handover of the Polish cryptanalytic results to Britain and France.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
events = [
(1926, "Germany adopts Enigma\nfor military use"),
(1928, "Polish Cipher Bureau\nbegins intercepting\nGerman traffic"),
(1931, "Schmidt provides\nEnigma documents\nto France"),
(1932.0, "Rejewski recruited\nto Biuro Szyfrow\n(September)"),
(1932.9, "Rejewski deduces\nrotor wirings\n(December)"),
(1933, "Rozycki & Zygalski\njoin the team"),
(1934, "Cyclometer built:\ncataloging cycle\nstructures"),
(1938.0, "Bomba kryptologiczna:\nautomated key search\n(November)"),
(1938.7, "Germans add rotors\nIV and V; change\nprocedures"),
(1938.9, "Zygalski sheets:\nperforated cardboard\nmethod (December)"),
(1939.55, "Pyry conference:\nPolish results\nhanded to UK & France\n(July 25)"),
(1939.7, "Germany invades\nPoland\n(September 1)"),
]
years = [e[0] for e in events]
labels = [e[1] for e in events]
fig, ax = plt.subplots(figsize=(18, 7))
y_base = 3.5
ax.plot([1925, 1940.5], [y_base, y_base], color='#333333', lw=3, zorder=1)
x_positions = np.linspace(0.8, 17.2, len(events))
colors_cycle = [
'#1565C0', '#C62828', '#2E7D32', '#E65100',
'#6A1B9A', '#00838F', '#AD1457', '#FF6F00',
'#283593', '#1B5E20', '#BF360C', '#4A148C'
]
for i, (xp, year, label) in enumerate(zip(x_positions, years, labels)):
color = colors_cycle[i % len(colors_cycle)]
if i % 2 == 0:
y_text = y_base + 1.5
va = 'bottom'
y_dot_off = 0.15
else:
y_text = y_base - 1.5
va = 'top'
y_dot_off = -0.15
ax.plot(xp, y_base, 'o', color=color, markersize=10, zorder=3,
markeredgecolor='black', markeredgewidth=1)
ax.plot([xp, xp], [y_base + y_dot_off, y_text], color=color,
lw=1.2, ls='--', alpha=0.7, zorder=2)
ax.text(xp, y_text, f"{int(year)}", fontsize=9, fontweight='bold',
ha='center', va=va, color=color)
if i % 2 == 0:
ax.text(xp, y_text + 0.25, label, fontsize=7.5, ha='center',
va='bottom', color='#333333', linespacing=1.3)
else:
ax.text(xp, y_text - 0.25, label, fontsize=7.5, ha='center',
va='top', color='#333333', linespacing=1.3)
ax.set_xlim(-0.5, 18.5)
ax.set_ylim(-1, 8.5)
ax.axis('off')
ax.set_title(
'Figure 11.2: Timeline of the Polish Enigma Attack (1926--1939)',
fontsize=14, fontweight='bold', pad=15
)
plt.tight_layout()
plt.savefig('fig_11_2_polish_timeline.png', dpi=150,
bbox_inches='tight', facecolor='white')
plt.show()
Experiment 6: How Many Messages Are Needed?#
Rejewski needed enough intercepted messages on a single day to determine the full permutations \(A\), \(B\), \(C\). This is a variant of the coupon collector problem: each message reveals one entry of each permutation, and we need all 26 entries. With \(n = 26\), the expected number of messages for a single permutation is \(E[T] = 26 \cdot H_{26} \approx 100\), and for all three permutations to be simultaneously complete, roughly 150–200 messages are needed (see the simulation below). In practice, Rejewski could supplement near-complete permutations with algebraic deduction.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
n_trials = 500
max_messages = 250
rng_cov = np.random.default_rng(99)
avg_cov_A = np.zeros(max_messages)
avg_cov_B = np.zeros(max_messages)
avg_cov_C = np.zeros(max_messages)
full_cov_count = np.zeros(max_messages)
for trial in range(n_trials):
all_ind = attack.simulate_message_keys(
max_messages, GRUNDSTELLUNG, rng=rng_cov
)
seen_A, seen_B, seen_C = set(), set(), set()
for k, msg in enumerate(all_ind):
ind = msg['indicator']
seen_A.add(ind[0])
seen_B.add(ind[1])
seen_C.add(ind[2])
avg_cov_A[k] += len(seen_A)
avg_cov_B[k] += len(seen_B)
avg_cov_C[k] += len(seen_C)
if len(seen_A) == 26 and len(seen_B) == 26 and len(seen_C) == 26:
full_cov_count[k] += 1
avg_cov_A /= n_trials
avg_cov_B /= n_trials
avg_cov_C /= n_trials
cum_full = np.cumsum(full_cov_count) / n_trials
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 5))
x_msgs = np.arange(1, max_messages + 1)
ax1.plot(x_msgs, avg_cov_A, label='Perm A', linewidth=2)
ax1.plot(x_msgs, avg_cov_B, label='Perm B', linewidth=2, ls='--')
ax1.plot(x_msgs, avg_cov_C, label='Perm C', linewidth=2, ls=':')
ax1.axhline(y=26, color='gray', ls=':', alpha=0.5)
ax1.set_xlabel('Number of intercepted messages', fontsize=12)
ax1.set_ylabel('Average letters covered (out of 26)', fontsize=12)
ax1.set_title('Coverage of Characteristic Permutations', fontsize=13)
ax1.legend(fontsize=10)
ax1.grid(alpha=0.3)
ax1.set_ylim(0, 28)
H_26 = sum(1.0 / k for k in range(1, 27))
expected_T = 26 * H_26
ax1.axvline(x=expected_T, color='red', ls='--', alpha=0.6)
ax1.text(expected_T + 1, 14,
f'E[T]={float(expected_T):.0f}\n(coupon\ncollector)',
fontsize=9, color='red')
ax2.plot(x_msgs, cum_full, color='darkgreen', linewidth=2)
ax2.axhline(y=0.5, color='gray', ls=':', alpha=0.5)
ax2.axhline(y=0.95, color='gray', ls=':', alpha=0.5)
ax2.set_xlabel('Number of intercepted messages', fontsize=12)
ax2.set_ylabel('P(full coverage of A, B, C)', fontsize=11)
ax2.set_title('Probability All Permutations Determined', fontsize=13)
ax2.grid(alpha=0.3)
ax2.set_ylim(-0.05, 1.05)
for thresh, lbl in [(0.5, '50%'), (0.95, '95%')]:
idx = np.searchsorted(cum_full, thresh)
if idx < len(cum_full):
ax2.axvline(x=idx+1, color='orange', ls='--', alpha=0.6)
ax2.text(idx+2, thresh-0.08, f'{lbl}: ~{idx+1} msgs',
fontsize=9, color='orange')
fig.suptitle(
'Figure 11.3: How Many Intercepted Messages Does '
'Rejewski Need?',
fontsize=14, fontweight='bold', y=1.02
)
plt.tight_layout()
plt.savefig('fig_11_3_coverage_analysis.png', dpi=150,
bbox_inches='tight', facecolor='white')
plt.show()
print(f"Coupon collector E[T] for 26 items: {float(expected_T):.1f}")
print(f"For ALL THREE permutations, more messages are needed.")
Coupon collector E[T] for 26 items: 100.2
For ALL THREE permutations, more messages are needed.
Experiment 7: Cycle Structures of Random Permutations#
To understand how discriminating the cycle structure fingerprint is, we generate many random permutations in \(S_{26}\) and study the distribution of cycle counts and structures.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
rng_perm = np.random.default_rng(777)
n_samples = 100000
cycle_counts = []
structure_dict = {} # manual counter using a plain dict
for _ in range(n_samples):
perm = rng_perm.permutation(26)
_, structure = RejewskiAttack.cycle_structure(perm)
cycle_counts.append(len(structure))
structure_dict[structure] = structure_dict.get(structure, 0) + 1
cycle_counts = np.array(cycle_counts)
H_26 = sum(1.0 / k for k in range(1, 27))
print(f"Analysis of {n_samples:,} random permutations in S_26:")
print(f" Distinct structures: {len(structure_dict)}")
print(f" (Partitions of 26: p(26) = 2436)")
print(f" Avg cycles: {float(cycle_counts.mean()):.3f}")
print(f" E[cycles] = H_26 = {float(H_26):.4f}")
print(f" Std dev: {float(cycle_counts.std()):.3f}")
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 5))
bins = np.arange(0.5, 15.5, 1)
ax1.hist(cycle_counts, bins=bins, color='steelblue',
edgecolor='navy', alpha=0.8, density=True)
ax1.axvline(x=H_26, color='red', ls='--', lw=2,
label=f'$H_{{26}} = {float(H_26):.2f}$')
ax1.set_xlabel('Number of cycles', fontsize=12)
ax1.set_ylabel('Probability density', fontsize=12)
ax1.set_title('Distribution of Cycle Counts in $S_{26}$', fontsize=13)
ax1.legend(fontsize=11)
ax1.grid(alpha=0.3)
# Get top 20 most common structures
sorted_structs = sorted(structure_dict.items(), key=lambda x: x[1],
reverse=True)
top_20 = sorted_structs[:20]
labels_top = [str(s) for s, _ in top_20]
freqs_top = [c / n_samples for _, c in top_20]
ax2.barh(range(len(top_20)), freqs_top, color='darkorange',
edgecolor='black', alpha=0.8)
ax2.set_yticks(range(len(top_20)))
ax2.set_yticklabels(labels_top, fontsize=7)
ax2.set_xlabel('Relative frequency', fontsize=12)
ax2.set_title('Top 20 Most Common Cycle Structures', fontsize=13)
ax2.invert_yaxis()
ax2.grid(alpha=0.3, axis='x')
fig.suptitle(
'Figure 11.4: Cycle Structure Statistics for '
'Random Permutations in $S_{26}$',
fontsize=14, fontweight='bold', y=1.02
)
plt.tight_layout()
plt.savefig('fig_11_4_cycle_statistics.png', dpi=150,
bbox_inches='tight', facecolor='white')
plt.show()
print(f"\nTop 5 most common structures:")
for struct, count in top_20[:5]:
print(f" {struct}: {float(count/n_samples):.4f}")
Analysis of 100,000 random permutations in S_26:
Distinct structures: 1350
(Partitions of 26: p(26) = 2436)
Avg cycles: 3.855
E[cycles] = H_26 = 3.8544
Std dev: 1.502
Top 5 most common structures:
(25, 1): 0.0396
(26,): 0.0395
(23, 2, 1): 0.0216
(24, 1, 1): 0.0210
(24, 2): 0.0207
Experiment 8: End-to-End Attack Demonstration#
We now tie everything together: given only the intercepted indicators, we extract characteristic permutations, compute cycle structures, look them up in the catalog, and recover the Grundstellung.
import numpy as np
print("END-TO-END REJEWSKI ATTACK DEMONSTRATION")
print("=" * 60)
print(f"\nStep 1: Intercept {len(indicators)} message indicators")
print(f" {len(indicators)} messages intercepted.")
print("\nStep 2: Extract characteristic permutations")
A_obs, B_obs, C_obs, cov = attack.extract_characteristics(indicators)
print(f" Raw coverage: A={cov[0]}/26, B={cov[1]}/26, C={cov[2]}/26")
# Complete near-complete permutations
A_obs, A_ok = RejewskiAttack.complete_permutation(A_obs)
B_obs, B_ok = RejewskiAttack.complete_permutation(B_obs)
C_obs, C_ok = RejewskiAttack.complete_permutation(C_obs)
cov_after = (int(np.sum(A_obs >= 0)), int(np.sum(B_obs >= 0)),
int(np.sum(C_obs >= 0)))
print(f" After completion: A={cov_after[0]}/26, B={cov_after[1]}/26, "
f"C={cov_after[2]}/26")
if all(A_obs >= 0) and all(B_obs >= 0) and all(C_obs >= 0):
print(" All permutations fully determined.")
print("\nStep 3: Compute cycle structures")
_, sA_obs = RejewskiAttack.cycle_structure(A_obs)
_, sB_obs = RejewskiAttack.cycle_structure(B_obs)
_, sC_obs = RejewskiAttack.cycle_structure(C_obs)
print(f" A: {sA_obs}")
print(f" B: {sB_obs}")
print(f" C: {sC_obs}")
print("\nStep 4: Catalog lookup")
matches = RejewskiAttack.lookup_position(
sA_obs, sB_obs, sC_obs, catalog
)
print(f" Matches: {len(matches)}")
for match in matches:
ml = ''.join(chr(m + ord('A')) for m in match)
tag = " *** CORRECT ***" if list(match) == GRUNDSTELLUNG else ""
print(f" Candidate: {match} = {ml}{tag}")
print("\nStep 5: Verify")
tl = ''.join(chr(g + ord('A')) for g in GRUNDSTELLUNG)
if tuple(GRUNDSTELLUNG) in matches:
print(f" SUCCESS: Grundstellung {GRUNDSTELLUNG} = {tl} found!")
if len(matches) == 1:
print(f" UNIQUE match -- no ambiguity.")
else:
print(f" {len(matches)} candidates -- further analysis needed.")
else:
print(f" Not in partial catalog; full catalog would find it.")
END-TO-END REJEWSKI ATTACK DEMONSTRATION
============================================================
Step 1: Intercept 200 message indicators
200 messages intercepted.
Step 2: Extract characteristic permutations
Raw coverage: A=26/26, B=26/26, C=26/26
After completion: A=26/26, B=26/26, C=26/26
All permutations fully determined.
Step 3: Compute cycle structures
A: (13, 13)
B: (13, 13)
C: (10, 10, 3, 3)
Step 4: Catalog lookup
Matches: 12
Candidate: (2, 14, 12) = COM
Candidate: (3, 18, 25) = DSZ
Candidate: (7, 14, 3) = HOD *** CORRECT ***
Candidate: (8, 4, 13) = IEN
Candidate: (10, 19, 2) = KTC
Candidate: (13, 6, 6) = NGG
Candidate: (13, 6, 24) = NGY
Candidate: (17, 1, 5) = RBF
Candidate: (19, 22, 14) = TWO
Candidate: (21, 17, 14) = VRO
Candidate: (23, 19, 24) = XTY
Candidate: (24, 6, 17) = YGR
Step 5: Verify
SUCCESS: Grundstellung [7, 14, 3] = HOD found!
12 candidates -- further analysis needed.
Experiment 9: Verifying Theorem 11.1 (Independence from Message Keys)#
We verify that the characteristic permutations are the same regardless of which message keys the operators choose.
import numpy as np
print("VERIFICATION: Independence from message keys")
print("=" * 60)
rng_s1 = np.random.default_rng(1111)
rng_s2 = np.random.default_rng(9999)
ind_s1 = attack.simulate_message_keys(200, GRUNDSTELLUNG, rng=rng_s1)
ind_s2 = attack.simulate_message_keys(200, GRUNDSTELLUNG, rng=rng_s2)
A1, B1, C1, cov1 = attack.extract_characteristics(ind_s1)
A2, B2, C2, cov2 = attack.extract_characteristics(ind_s2)
# Apply completion
A1, _ = RejewskiAttack.complete_permutation(A1)
B1, _ = RejewskiAttack.complete_permutation(B1)
C1, _ = RejewskiAttack.complete_permutation(C1)
A2, _ = RejewskiAttack.complete_permutation(A2)
B2, _ = RejewskiAttack.complete_permutation(B2)
C2, _ = RejewskiAttack.complete_permutation(C2)
cov1_after = (int(np.sum(A1 >= 0)), int(np.sum(B1 >= 0)),
int(np.sum(C1 >= 0)))
cov2_after = (int(np.sum(A2 >= 0)), int(np.sum(B2 >= 0)),
int(np.sum(C2 >= 0)))
print(f"Set 1 raw coverage: A={cov1[0]}/26, B={cov1[1]}/26, C={cov1[2]}/26")
print(f"Set 1 after completion: A={cov1_after[0]}/26, B={cov1_after[1]}/26, C={cov1_after[2]}/26")
print(f"Set 2 raw coverage: A={cov2[0]}/26, B={cov2[1]}/26, C={cov2[2]}/26")
print(f"Set 2 after completion: A={cov2_after[0]}/26, B={cov2_after[1]}/26, C={cov2_after[2]}/26")
if all(A1 >= 0) and all(A2 >= 0):
print(f"\nA set1 == A set2: {np.array_equal(A1, A2)}")
if all(B1 >= 0) and all(B2 >= 0):
print(f"B set1 == B set2: {np.array_equal(B1, B2)}")
if all(C1 >= 0) and all(C2 >= 0):
print(f"C set1 == C set2: {np.array_equal(C1, C2)}")
print(f"\nA set1 == A exact: {np.array_equal(A1, A_exact)}")
print(f"A set2 == A exact: {np.array_equal(A2, A_exact)}")
print()
print("Theorem 11.1 confirmed: characteristic permutations depend")
print("ONLY on the daily key, not on operator message key choices.")
VERIFICATION: Independence from message keys
============================================================
Set 1 raw coverage: A=26/26, B=26/26, C=26/26
Set 1 after completion: A=26/26, B=26/26, C=26/26
Set 2 raw coverage: A=26/26, B=26/26, C=26/26
Set 2 after completion: A=26/26, B=26/26, C=26/26
A set1 == A set2: True
B set1 == B set2: True
C set1 == C set2: True
A set1 == A exact: True
A set2 == A exact: True
Theorem 11.1 confirmed: characteristic permutations depend
ONLY on the daily key, not on operator message key choices.
Exercises#
Exercise 11.1 (Independence verification).
Using the RejewskiAttack class, generate 100 intercepted indicators for three different Grundstellungen (but the same rotor order, ring settings, and plugboard). For each Grundstellung, extract the characteristic permutations \(A\), \(B\), \(C\) and confirm that:
(a) The permutations are the same regardless of which random seed is used (i.e., regardless of the operators’ message key choices).
(b) The permutations are different for different Grundstellungen.
Hint
Use simulate_message_keys with different rng seeds for part (a). For part (b), try Grundstellungen [0,0,0], [0,0,1], and [1,0,0] and compare the extracted permutations.
Exercise 11.2 (Expected cycle length distribution). The probability that a random permutation in \(S_n\) contains a cycle of length \(k\) is exactly \(1/k\) (for \(1 \leq k \leq n\)), independent of \(n\).
(a) Prove this fact. (Hint: Consider the permutation written in cycle notation. Element 1 is in a cycle of length \(k\) if, starting from 1 and following the permutation, you return to 1 after exactly \(k\) steps.)
(b) Compute the expected number of cycles of each length \(k = 1, 2, \ldots, 26\) in a random permutation of \(S_{26}\).
(c) Verify your computation empirically by generating 100,000 random permutations and plotting the average number of cycles of each length alongside the theoretical prediction.
Hint
The expected number of cycles of length \(k\) is \(1/k\). The total expected number of cycles is \(\sum_{k=1}^{n} 1/k = H_n\), which recovers Theorem 11.2.
Exercise 11.3 (Message count analysis). How many intercepted messages per day are needed to reliably determine all three characteristic permutations \(A\), \(B\), \(C\)?
(a) Model this as three independent coupon collector problems (each with 26 coupons) and compute the expected number of messages for all three to be complete.
(b) Run a Monte Carlo simulation: generate random indicators until all three permutations are fully determined. Repeat 10,000 times and plot the distribution.
(c) What is the 95th percentile? Compare with the typical volume of German traffic (~200–300 messages per day per network).
Hint
The expected number of messages for one coupon collector is \(26 \cdot H_{26} \approx 100\). The expected maximum of three independent such variables is larger. In practice, operator biases in key selection may affect the coverage rate.
Exercise 11.4 (The end of the doubled key). On September 15, 1938, the Germans stopped encrypting the message key twice.
(a) Explain why Rejewski’s characteristic permutation attack fails under the new procedure.
(b) What information can still be extracted from single-encrypted message keys?
(c) Briefly describe the Zygalski sheet method and how it differs from the characteristic permutation approach.
Hint
Without the doubling, there is no pair of positions encrypting the same plaintext letter, so \(A\), \(B\), \(C\) cannot be defined. The Zygalski sheet method exploits fixed points of characteristic permutations (letters where \(X_1 = X_4\)). The perforated sheets allow finding positions where such self-encryptions occur.
Exercise 11.5 (Challenge: Simplified Zygalski sheets). Implement a simplified version of the Zygalski sheet method.
(a) For each Grundstellung, compute \(A = E_4 \circ E_1^{-1}\) and identify all positions where \(A\) has a fixed point (\(A(x) = x\) for some \(x\), meaning \(X_1 = X_4\) in the intercept).
(b) Create a \(26 \times 26\) boolean grid for a fixed left-rotor position, where entry \((i, j)\) is True if the Grundstellung \((\text{fixed}, i, j)\) has a fixed point in \(A\).
(c) Given intercepted messages where \(X_1 = X_4\), show how overlaying sheets narrows down the Grundstellung. Demonstrate that 3–4 such observations typically yield a unique position.
Hint
A fixed point of \(A = E_4 \circ E_1^{-1}\) means \(E_4(m) = E_1(m)\) for some \(m\). In the intercepted indicator, this appears as \(X_1 = X_4\). Note that while the Enigma reflector prevents \(E_i(x) = x\), the composed permutation \(A\) can have fixed points. Overlay sheets by taking the logical AND of boolean grids.
11.5 Summary#
This chapter has reconstructed Marian Rejewski’s characteristic permutation attack on the Enigma machine – one of the most brilliant applications of abstract mathematics to a real-world problem in the history of science.
Key concepts:
Concept |
Key Point |
|---|---|
Doubled message key |
Pre-1938 procedure: operator encrypts 3-letter key twice, creating pairs (1,4), (2,5), (3,6) encrypting the same letter |
Characteristic permutations |
\(A = E_4 \circ E_1^{-1}\), \(B = E_5 \circ E_2^{-1}\), \(C = E_6 \circ E_3^{-1}\) – observable from intercepts alone |
Independence (Thm 11.1) |
\(A\), \(B\), \(C\) depend only on the daily key, not on individual message keys |
Cycle structure |
The multiset of cycle lengths serves as a fingerprint for the rotor configuration |
Expected cycles (Thm 11.2) |
A random permutation in \(S_{26}\) has \(H_{26} \approx 3.76\) cycles on average |
Catalog method |
Pre-compute cycle structures for all \(26^3\) Grundstellungen; match observed fingerprint |
Coverage requirement |
~60–100 intercepted messages needed to fully determine \(A\), \(B\), \(C\) (coupon collector) |
Historical significance:
Rejewski demonstrated that even a machine cipher of enormous complexity could be broken by exploiting algebraic structure in the encryption procedure.
The characteristic permutation attack was a ciphertext-only attack – Rejewski needed only intercepted indicators, not any known plaintext.
The Polish results, handed to Britain at the Pyry conference in July 1939, formed the foundation for Bletchley Park’s entire Enigma effort.
The attack depended critically on the procedural error of encrypting the message key twice. When the Germans eliminated this in September 1938, the Poles developed new techniques (Zygalski sheets, the bomba).
Tip
Looking ahead. In Chapter 12, we will examine Turing’s Bombe and the known-plaintext attacks developed at Bletchley Park – methods that worked even after the Germans stopped doubling the message key. The key insight shifts from algebraic structure (permutation cycles) to probabilistic reasoning (Bayesian weight of evidence).
11.6 References#
Rejewski, M. (1981). “How Polish Mathematicians Deciphered the Enigma,” Annals of the History of Computing, 3(3), pp. 213–234. Rejewski’s own account, written decades after the war, providing the mathematical details of his attack in his own words.
Kozaczuk, W. (1984). Enigma: How the German Machine Cipher Was Broken, and How It Was Read by the Allies in World War Two. Translated by Christopher Kasparek. University Publications of America. A comprehensive history of the Polish Enigma work, written by a Polish military historian with access to surviving participants.
Budiansky, S. (2000). Battle of Wits: The Complete Story of Codebreaking in World War II. Free Press. A masterful account integrating the Polish, British, and American cryptanalytic efforts. Chapter 4 gives an accessible treatment of Rejewski’s mathematics.
Christensen, C. (2007). “Polish Mathematicians Finding Patterns in Enigma Messages,” Mathematics Magazine, 80(4), pp. 247–273. A detailed mathematical exposition of Rejewski’s method, written for a mathematical audience.
Turing, A. M. (c. 1940). “Prof’s Book” (unpublished working notes on Enigma), National Archives, Kew, UK, reference HW 25/3. Turing’s working notes on the Bombe method, which built directly on the Polish foundation.
Welchman, G. (1982). The Hut Six Story: Breaking the Enigma Codes. McGraw-Hill. A first-hand account by one of the key Bletchley Park cryptanalysts.