Chapter 11b: The Zygalski Sheet Method#
Perforated sheets and fixed-point theory — the elegant combinatorial technique that kept Poland reading Enigma from 1938 to 1940.
This chapter bridges Chapter 11 (Rejewski’s cycle-structure attack) and Chapter 12 (Turing’s Bombe). When the Germans introduced two extra rotors in late 1938, Rejewski’s catalog method became impractical. Henryk Zygalski devised a brilliantly simple alternative: instead of cataloging full cycle structures, track only the fixed points of the characteristic permutations.
11b.1 Historical Context#
The Crisis of September 1938#
On September 15, 1938, the German military introduced two additional rotors — IV and V — into service. The number of possible rotor orders jumped from \(3! = 6\) to \(\binom{5}{3} \times 3! = 60\). Rejewski’s catalog now needed to cover ten times as many configurations.
Zygalski’s Insight#
Henryk Zygalski (1908–1978) focused on a single observable property: fixed points. A fixed point of the characteristic permutation \(A\) means that some letter encrypts to itself in the indicator — directly observable from intercepted traffic.
The Sheets#
For each rotor order and each left-rotor starting position, Zygalski created a 26 × 26 grid with holes punched where fixed points exist. Total: \(26 \times 60 = 1{,}560\) sheets, cut by hand with razor blades. Operational from late 1938 through May 1, 1940.
11b.2 Fixed-Point Theory of Permutations#
Definition 11b.1 (Fixed Point)
A fixed point of \(\sigma \in S_n\) is \(x\) such that \(\sigma(x) = x\).
Definition 11b.2 (Derangement)
A derangement is a permutation with no fixed points. Count: \(D_n = n! \sum_{k=0}^{n} (-1)^k / k!\)
Theorem 11b.1 (Fixed-Point Distribution)
For a uniformly random \(\sigma \in S_n\):
\(\mathbb{E}[\text{number of fixed points}] = 1\) (exactly, for all \(n\))
\(\Pr[k \text{ fixed points}] \to e^{-1}/k!\) (Poisson with \(\lambda = 1\))
\(\Pr[\geq 1 \text{ fixed point}] \to 1 - 1/e \approx 0.6321\)
Proof (part 1): \(\mathbb{E}[\sum_i \mathbf{1}[\sigma(i)=i]] = n \cdot (n-1)!/n! = 1\).
Proof (part 3): By inclusion-exclusion, \(\Pr[\exists \text{fp}] = 1 - \sum_{k=0}^{n} (-1)^k/k! \to 1 - e^{-1}\).
Show code cell source
import numpy as np
import math
rng = np.random.default_rng(42)
n_trials = 100_000
fp_counts = np.zeros(n_trials, dtype=int)
for i in range(n_trials):
perm = rng.permutation(26)
fp_counts[i] = np.sum(perm == np.arange(26))
print('Fixed-Point Statistics for Random Permutations in S_26')
print('=' * 57)
print(f' Mean: {fp_counts.mean():.4f} (theory: 1.0000)')
print(f' Pr>=1: {(fp_counts >= 1).mean():.4f} (theory: {1-1/np.e:.4f})')
print()
for k in range(6):
print(f' Pr[{k}]: {(fp_counts==k).mean():.4f} (Poisson: {np.exp(-1)/math.factorial(k):.4f})')
Fixed-Point Statistics for Random Permutations in S_26
=========================================================
Mean: 1.0000 (theory: 1.0000)
Pr>=1: 0.6318 (theory: 0.6321)
Pr[0]: 0.3682 (Poisson: 0.3679)
Pr[1]: 0.3661 (Poisson: 0.3679)
Pr[2]: 0.1858 (Poisson: 0.1839)
Pr[3]: 0.0618 (Poisson: 0.0613)
Pr[4]: 0.0146 (Poisson: 0.0153)
Pr[5]: 0.0031 (Poisson: 0.0031)
Show code cell source
import matplotlib.pyplot as plt
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(13, 5))
max_fp = min(int(fp_counts.max()), 8)
bins = np.arange(-0.5, max_fp+1.5, 1)
ax1.hist(fp_counts, bins=bins, density=True, color='#4f46e5', alpha=0.7, edgecolor='white', label='Observed')
k_vals = np.arange(0, max_fp+1)
ax1.plot(k_vals, [np.exp(-1)/math.factorial(int(k)) for k in k_vals], 'ro-', markersize=8, lw=2, label='Poisson(1)')
ax1.set_xlabel('Number of Fixed Points'); ax1.set_ylabel('Probability')
ax1.set_title('Figure 11b.1: Fixed-Point Distribution', fontweight='bold')
ax1.legend(); ax1.grid(True, alpha=0.3)
ax2.plot(k_vals, [(fp_counts>=k).mean() for k in k_vals], 'o-', color='#4f46e5', markersize=8, lw=2, label='Observed')
ax2.axhline(y=1-1/np.e, color='#059669', ls=':', lw=2, label=f'1-1/e={1-1/np.e:.4f}')
ax2.set_xlabel('k'); ax2.set_ylabel('Pr[>=k fixed points]')
ax2.set_title('Cumulative Probability', fontweight='bold')
ax2.legend(); ax2.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('fig_11b_1_fixed_point_distribution.png', dpi=150, bbox_inches='tight', facecolor='white')
plt.show()
11b.3 The “Female” Indicator (Samiczka)#
Definition 11b.3 (Female)
An indicator \(X_1 X_2 X_3 X_4 X_5 X_6\) has a female at position \(i\) if \(X_i = X_{i+3}\).
Why this reveals a fixed point: If \(X_1 = X_4\), then \(A(X_1) = E_4(E_1^{-1}(X_1)) = E_4(m_1) = X_4 = X_1\). So \(X_1\) is a fixed point of \(A = E_4 \circ E_1^{-1}\).
Etymology: Rejewski called indicator pairs “animals.” When both match, he called it a “female” (samiczka).
Expected frequency: \(\Pr[\text{female at one position}] \approx 0.632\). Probability of at least one female per indicator \(\approx 1 - (1/e)^3 \approx 95\%\).
Show code cell source
import numpy as np
ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ROTOR_WIRINGS = {
'I': 'EKMFLGDQVZNTOWYHXUSPAIBRCJ', 'II': 'AJDKSIRUXBLHWTMCQGZNPYFVOE',
'III': 'BDFHJLCPRTXVZNYEIWGAKMUSQO', 'IV': 'ESOVPZJAYQUIRHXLNFTGKDCMWB',
'V': 'VZBRGITYUPSDNHLXAWMJQOFECK',
}
ROTOR_NOTCHES = {'I': 16, 'II': 4, 'III': 21, 'IV': 9, 'V': 25}
class EnigmaMachine:
def __init__(self, rotor_order=('I','II','III'), initial_positions=(0,0,0), ring_settings=(0,0,0)):
self.rotors_fwd, self.rotors_inv, self.notches = [], [], []
for name in rotor_order:
fwd = np.array([ord(c)-65 for c in ROTOR_WIRINGS[name]], dtype=int)
inv = np.zeros(26, dtype=int); inv[fwd] = np.arange(26)
self.rotors_fwd.append(fwd); self.rotors_inv.append(inv)
self.notches.append(ROTOR_NOTCHES[name])
self.reflector = np.array([ord(c)-65 for c in 'YRUHQSLDPXNGOKMIEBFZCWVJAT'], dtype=int)
self.rings, self.pos = list(ring_settings), list(initial_positions)
def _step(self):
mn, rn = (self.notches[1]+self.rings[1])%26, (self.notches[2]+self.rings[2])%26
if self.pos[1] == mn:
self.pos[1] = (self.pos[1]+1)%26; self.pos[0] = (self.pos[0]+1)%26
elif self.pos[2] == rn:
self.pos[1] = (self.pos[1]+1)%26
self.pos[2] = (self.pos[2]+1)%26
def _through(self, ri, c, fwd=True):
p, r = self.pos[ri], self.rings[ri]
c = (c+p-r)%26
c = (self.rotors_fwd[ri] if fwd else self.rotors_inv[ri])[c]
return (c-p+r)%26
def encrypt_letter(self, x):
self._step()
c = x
for i in [2,1,0]: c = self._through(i,c,True)
c = self.reflector[c]
for i in [0,1,2]: c = self._through(i,c,False)
return int(c)
def get_permutation_no_step(self):
perm = np.zeros(26, dtype=int); saved = list(self.pos)
for x in range(26):
self.pos = list(saved); c = x
for i in [2,1,0]: c = self._through(i,c,True)
c = self.reflector[c]
for i in [0,1,2]: c = self._through(i,c,False)
perm[x] = int(c)
self.pos = saved
return perm
def compute_char_perm(rotor_order, grundstellung, perm_type='A'):
m = EnigmaMachine(rotor_order=rotor_order, initial_positions=grundstellung)
perms = []
for _ in range(6):
m._step(); perms.append(m.get_permutation_no_step())
idx = {'A': (3,0), 'B': (4,1), 'C': (5,2)}
i, j = idx[perm_type]
inv_j = np.zeros(26, dtype=int); inv_j[perms[j]] = np.arange(26)
return perms[i][inv_j]
print('EnigmaMachine and compute_char_perm loaded.')
EnigmaMachine and compute_char_perm loaded.
def simulate_day(rotor_order, grundstellung, n_messages=250, rng=None):
if rng is None: rng = np.random.default_rng()
indicators = []
for _ in range(n_messages):
mk = tuple(rng.integers(0, 26, size=3))
m = EnigmaMachine(rotor_order=rotor_order, initial_positions=grundstellung)
ind = [m.encrypt_letter(letter) for letter in list(mk)+list(mk)]
indicators.append(tuple(ind))
return indicators
def find_females(indicators):
females = {0: set(), 1: set(), 2: set()}
for ind in indicators:
for pos in range(3):
if ind[pos] == ind[pos+3]: females[pos].add(ind[pos])
return {k: sorted(v) for k, v in females.items()}
rng = np.random.default_rng(2024)
ROTOR_ORDER = ('III', 'I', 'II')
GRUNDSTELLUNG = (16, 24, 21)
indicators = simulate_day(ROTOR_ORDER, GRUNDSTELLUNG, n_messages=250, rng=rng)
females = find_females(indicators)
print(f'Rotor order: {ROTOR_ORDER}')
print(f'True Grundstellung: ({ALPHA[GRUNDSTELLUNG[0]]}, {ALPHA[GRUNDSTELLUNG[1]]}, {ALPHA[GRUNDSTELLUNG[2]]})')
print(f'Messages: {len(indicators)}')
for pos in range(3):
print(f' {"ABC"[pos]} females: {[ALPHA[x] for x in females[pos]]} ({len(females[pos])} found)')
Rotor order: ('III', 'I', 'II')
True Grundstellung: (Q, Y, V)
Messages: 250
A females: ['A', 'G', 'L', 'M', 'O', 'T', 'W', 'X'] (8 found)
B females: ['I', 'K'] (2 found)
C females: ['L', 'V'] (2 found)
11b.4 Sheet Construction#
Definition 11b.4 (Zygalski Sheet)
For rotor order, letter \(x\), and left position \(L\), the sheet \(Z_{L,x}\) is a \(26 \times 26\) binary matrix:
Expected hole density: \(\approx 63.2\%\) — each sheet is more hole than card.
Show code cell source
def build_letter_sheet(rotor_order, left_pos, letter, perm_type='A'):
sheet = np.zeros((26,26), dtype=bool)
for M in range(26):
for R in range(26):
A = compute_char_perm(rotor_order, (left_pos, M, R), perm_type)
if A[letter] == letter: sheet[M,R] = True
return sheet
def build_base_sheet(rotor_order, left_pos, perm_type='A'):
sheet = np.zeros((26,26), dtype=bool)
for M in range(26):
for R in range(26):
A = compute_char_perm(rotor_order, (left_pos, M, R), perm_type)
if np.any(A == np.arange(26)): sheet[M,R] = True
return sheet
print(f'Building base sheet for left={ALPHA[GRUNDSTELLUNG[0]]}...')
base_sheet = build_base_sheet(ROTOR_ORDER, GRUNDSTELLUNG[0])
n_holes = np.sum(base_sheet)
print(f'Holes: {n_holes}/676 ({100*n_holes/676:.1f}%)')
Building base sheet for left=Q...
Holes: 270/676 (39.9%)
Show code cell source
from matplotlib.colors import ListedColormap
fig, ax = plt.subplots(figsize=(10, 10))
cmap = ListedColormap(['#1e3a5f', '#e0f2fe'])
ax.imshow(np.where(base_sheet, 1.0, 0.0), cmap=cmap, aspect='equal', interpolation='nearest')
ax.plot(GRUNDSTELLUNG[2], GRUNDSTELLUNG[1], marker='*', color='#dc2626', markersize=18,
markeredgecolor='white', markeredgewidth=1.5, zorder=5)
ax.set_xticks(range(26)); ax.set_xticklabels(list(ALPHA), fontsize=8, fontfamily='monospace')
ax.set_yticks(range(26)); ax.set_yticklabels(list(ALPHA), fontsize=8, fontfamily='monospace')
ax.set_xlabel('Right Rotor Position'); ax.set_ylabel('Middle Rotor Position')
ax.set_title(f'Figure 11b.2: Zygalski Base Sheet\nRotors {ROTOR_ORDER}, Left={ALPHA[GRUNDSTELLUNG[0]]}',
fontweight='bold')
for i in range(27): ax.axhline(i-0.5, color='white', lw=0.3); ax.axvline(i-0.5, color='white', lw=0.3)
plt.tight_layout()
plt.savefig('fig_11b_2_base_sheet.png', dpi=150, bbox_inches='tight', facecolor='white')
plt.show()
11b.5 The Overlay Method#
Observe females from the day’s traffic and record which letter is the fixed point.
Select the sheet \(Z_{L,x}\) for each female letter \(x\).
Overlay (AND): a cell survives only if it has a hole in every sheet.
Narrow: with ~10 females, exactly one cell remains.
Convergence Rate
Each female eliminates ~37% of survivors. Starting from ~427 holes, after 10 females typically 1–2 remain.
fp_A = females[0]
print(f'Fixed points of A: {[ALPHA[x] for x in fp_A]}')
print('\nBuilding letter sheets...')
sheets_A = {}
for x in fp_A:
sheets_A[x] = build_letter_sheet(ROTOR_ORDER, GRUNDSTELLUNG[0], x, 'A')
print(f' {ALPHA[x]}: {np.sum(sheets_A[x])} holes')
print('\n' + '='*60)
print('OVERLAY: Narrowing the Grundstellung')
print('='*60)
combined = np.ones((26,26), dtype=bool)
for i, x in enumerate(fp_A):
combined &= sheets_A[x]
n_s = np.sum(combined)
print(f'\n+ {ALPHA[x]} ({i+1}/{len(fp_A)}): {n_s} surviving')
if n_s <= 10:
for p in np.argwhere(combined):
mark = ' <<< TRUE' if p[0]==GRUNDSTELLUNG[1] and p[1]==GRUNDSTELLUNG[2] else ''
print(f' ({ALPHA[GRUNDSTELLUNG[0]]}, {ALPHA[p[0]]}, {ALPHA[p[1]]}){mark}')
if np.sum(combined) == 1:
w = np.argwhere(combined)[0]
print(f'\nUNIQUE SOLUTION: ({ALPHA[GRUNDSTELLUNG[0]]}, {ALPHA[w[0]]}, {ALPHA[w[1]]})')
else:
print(f'\n{np.sum(combined)} candidates -- add B/C females to resolve.')
Fixed points of A: ['A', 'G', 'L', 'M', 'O', 'T', 'W', 'X']
Building letter sheets...
A: 36 holes
G: 19 holes
L: 32 holes
M: 28 holes
O: 26 holes
T: 27 holes
W: 25 holes
X: 29 holes
============================================================
OVERLAY: Narrowing the Grundstellung
============================================================
+ A (1/8): 36 surviving
+ G (2/8): 3 surviving
(Q, U, Q)
(Q, V, U)
(Q, Y, V) <<< TRUE
+ L (3/8): 2 surviving
(Q, U, Q)
(Q, Y, V) <<< TRUE
+ M (4/8): 1 surviving
(Q, Y, V) <<< TRUE
+ O (5/8): 1 surviving
(Q, Y, V) <<< TRUE
+ T (6/8): 1 surviving
(Q, Y, V) <<< TRUE
+ W (7/8): 1 surviving
(Q, Y, V) <<< TRUE
+ X (8/8): 1 surviving
(Q, Y, V) <<< TRUE
UNIQUE SOLUTION: (Q, Y, V)
Show code cell source
n_f = len(fp_A)
steps = [1, max(2,n_f//3), max(3,2*n_f//3), n_f] if n_f>=4 else list(range(1,n_f+1))
n_p = len(steps)
fig, axes = plt.subplots(1, n_p, figsize=(4*n_p, 4.5))
if n_p == 1: axes = [axes]
cmap2 = ListedColormap(['#94a3b8', '#bbf7d0'])
cp = np.ones((26,26), dtype=bool); pi = 0
for i, x in enumerate(fp_A):
cp &= sheets_A[x]
if (i+1) in steps and pi < n_p:
ax = axes[pi]
ax.imshow(np.where(cp, 1., 0.), cmap=cmap2, aspect='equal', interpolation='nearest')
ax.plot(GRUNDSTELLUNG[2], GRUNDSTELLUNG[1], '*', color='#dc2626', ms=14, mec='white', mew=1)
ax.set_title(f'After {i+1} females\n{np.sum(cp)} surviving', fontsize=10, fontweight='bold')
ax.set_xticks([0,5,10,15,20,25]); ax.set_xticklabels([ALPHA[j] for j in [0,5,10,15,20,25]], fontsize=7)
ax.set_yticks([0,5,10,15,20,25]); ax.set_yticklabels([ALPHA[j] for j in [0,5,10,15,20,25]], fontsize=7)
if pi==0: ax.set_ylabel('Middle Rotor')
ax.set_xlabel('Right Rotor'); pi += 1
fig.suptitle('Figure 11b.3: Overlay Progression', fontsize=13, fontweight='bold', y=1.02)
plt.tight_layout()
plt.savefig('fig_11b_3_overlay_progression.png', dpi=150, bbox_inches='tight', facecolor='white')
plt.show()
11b.6 Complete Attack: Using All Three Permutations#
\(B\) and \(C\) provide independent constraints on the same Grundstellung, making the attack converge faster.
print('Full attack using A, B, and C')
print('='*55)
comb = np.ones((26,26), dtype=bool); total = 0
for pt, pi in [('A',0), ('B',1), ('C',2)]:
fp = females[pi]
if not fp: print(f'\n{pt}: no females'); continue
print(f'\n{pt}: {[ALPHA[x] for x in fp]}')
for x in fp:
sh = build_letter_sheet(ROTOR_ORDER, GRUNDSTELLUNG[0], x, pt)
comb &= sh; total += 1; n_s = np.sum(comb)
print(f' +{ALPHA[x]}: {n_s} surviving')
if n_s <= 3:
for p in np.argwhere(comb):
mark = ' <<< TRUE' if p[0]==GRUNDSTELLUNG[1] and p[1]==GRUNDSTELLUNG[2] else ''
print(f' ({ALPHA[GRUNDSTELLUNG[0]]},{ALPHA[p[0]]},{ALPHA[p[1]]}){mark}')
if n_s == 1: break
if np.sum(comb) == 1: break
w = np.argwhere(comb)
if len(w)==1:
print(f'\nSUCCESS after {total} females: ({ALPHA[GRUNDSTELLUNG[0]]},{ALPHA[w[0][0]]},{ALPHA[w[0][1]]})')
else:
print(f'\n{len(w)} candidates after {total} females.')
Full attack using A, B, and C
=======================================================
A: ['A', 'G', 'L', 'M', 'O', 'T', 'W', 'X']
+A: 36 surviving
+G: 3 surviving
(Q,U,Q)
(Q,V,U)
(Q,Y,V) <<< TRUE
+L: 2 surviving
(Q,U,Q)
(Q,Y,V) <<< TRUE
+M: 1 surviving
(Q,Y,V) <<< TRUE
SUCCESS after 4 females: (Q,Y,V)
11b.7 Searching Across Rotor Orders#
Only the correct rotor order yields a unique survivor — wrong orders give 0 or many.
orders = [('I','II','III'), ('II','IV','I'), ('III','I','V'), ('V','II','IV'), ('I','IV','III')]
print('Rotor Order Search\n' + '='*50)
for o in orders:
c = np.ones((26,26), dtype=bool)
for x in females[0]:
c &= build_letter_sheet(o, GRUNDSTELLUNG[0], x, 'A')
print(f' {o}: {np.sum(c):3d} survivors{" <<<< TRUE" if o==ROTOR_ORDER else ""}')
Rotor Order Search
==================================================
('I', 'II', 'III'): 0 survivors
('II', 'IV', 'I'): 0 survivors
('III', 'I', 'V'): 0 survivors
('V', 'II', 'IV'): 0 survivors
('I', 'IV', 'III'): 0 survivors
Tip
An interactive animated version is available at Zygalski Sheet Simulator.
11b.8 Comparison with Other Methods#
Method |
Exploits |
Data needed |
|---|---|---|
Cycle structure (Ch 11) |
Full cycle structure |
~150 messages |
Zygalski sheets |
Fixed points only |
~250 messages |
Bombe (Ch 12) |
Known-plaintext crib |
1 crib of ~20 chars |
11b.9 Exercises#
Exercise 11b.1 (Fixed-Point Counting) (a) Prove \(\mathbb{E}[\text{number of fixed points}] = 1\) using linearity of expectation. (b) Prove \(D_n = n! \sum (-1)^k/k!\) by inclusion-exclusion.
Hint
Let \(X_i = \mathbf{1}[\sigma(i)=i]\). Then \(\mathbb{E}[\sum X_i] = n \cdot (n-1)!/n! = 1\).
Exercise 11b.2 (Sheet Properties) (a) Expected holes in a base sheet? (b) Formula for females needed to get unique solution?
Exercise 11b.3 (Plugboard Effects) (a) Why doesn’t the plugboard affect whether a female is observable? (b) How does it affect which letter appears?
Hint
\(E = PSP^{-1}\) implies \(E(x)=x \iff S(P(x))=P(x)\). Number of fixed points preserved.
Exercise 11b.4 (Challenge) Implement the full Zygalski attack across all 60 rotor orders. Measure success rate over 50 random configs.
11b.10 Summary#
Concept |
Key Point |
|---|---|
Fixed point |
\(\sigma(x) = x\); expected count = 1 |
Derangement |
No fixed points; probability \(\approx 1/e\) |
Female |
\(X_i = X_{i+3}\) reveals fixed point of \(A\)/\(B\)/\(C\) |
Zygalski sheet |
26×26 grid of fixed-point locations |
Overlay |
AND of sheets narrows to unique Grundstellung |
Looking ahead: Chapter 12 covers what happened when the doubled key was eliminated (May 1940). Turing’s Bombe used known-plaintext cribs instead.
11b.11 References#
Rejewski, M. “How Polish Mathematicians Deciphered the Enigma.” Annals Hist. Computing, 3(3), 1981.
Kozaczuk, W. Enigma. University Publications of America, 1984.
Christensen, C. Mathematics Magazine, 80(4), 2007.
Budiansky, S. Battle of Wits. Free Press, 2000.