Chapter 8: The Playfair Cipher#
“There is nothing so practical as a good cipher that can be operated without any apparatus.” – Lord Playfair, advocating the cipher to the British Foreign Office, 1854
In the preceding chapters, we examined monoalphabetic and polyalphabetic ciphers that operate on individual letters. The Playfair cipher represents a fundamental shift in approach: it encrypts pairs of letters (digrams) simultaneously. This makes it the first widely used digraphic (or polygraphic) cipher in the history of military cryptography.
By operating on digrams rather than single letters, the Playfair cipher obscures the simple letter frequency distribution that makes monoalphabetic ciphers so vulnerable. However, as we shall see, it introduces a new kind of statistical regularity – digram frequency – that a skilled cryptanalyst can exploit.
8.1 Historical Context#
The Playfair cipher was invented in 1854 by Sir Charles Wheatstone (1802–1875), one of the most prolific British scientists and inventors of the Victorian era. Wheatstone is better known for his contributions to the electric telegraph and the Wheatstone bridge circuit, but his cryptographic work was equally innovative.
Despite being Wheatstone’s invention, the cipher bears the name of Baron Lyon Playfair (1818–1898), a Scottish chemist and politician who enthusiastically promoted the system to the British Foreign Office. Playfair demonstrated the cipher at a dinner party to Lord Palmerston (then Prime Minister) and other government officials. According to legend, Palmerston found the system too complex, to which Playfair responded by teaching it to three boys from a nearby school in fifteen minutes – proving its practicality.
Military adoption and legacy
The Playfair cipher saw remarkable longevity in military service:
Boer War (1899–1902): First large-scale military use by British forces in South Africa.
World War I (1914–1918): Used by British tactical communications when speed was more important than absolute security.
World War II (1939–1945): Used by Australian and New Zealand forces (ANZAC) for lower-level tactical messages, and by the British Special Operations Executive (SOE) for covert communications in occupied Europe.
The Playfair cipher was valued not for its theoretical strength – which was known to be limited – but for its operational convenience. It required no equipment, could be memorised by field agents, and was fast enough for real-time communication. It represented an excellent trade-off between security and usability for its era.
The Playfair cipher holds the distinction of being the first practical digraphic cipher in widespread military use. Its central innovation – encrypting letter pairs using a 5\(\times\)5 grid – influenced later polygraphic systems, including the Hill cipher (Chapter 7) and the ADFGVX cipher used by Germany in World War I.
8.2 Formal Definitions#
8.2.1 The Playfair Grid#
The Playfair cipher operates using a 5\(\times\)5 matrix (grid) containing 25 distinct letters of the English alphabet. Since the English alphabet has 26 letters but the grid has only 25 cells, the letters I and J are traditionally merged into a single cell (treated as the same letter).
Definition 8.1 (Playfair Grid)
A Playfair grid is a 5\(\times\)5 matrix \(G\) whose 25 entries are a permutation of the alphabet \(\mathcal{A} = \{A, B, C, D, E, F, G, H, I, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z\}\) (with I/J identified). Each letter appears exactly once.
The grid is constructed from a keyword \(\kappa\) as follows:
Convert \(\kappa\) to uppercase and replace every J with I.
Remove duplicate letters, keeping only the first occurrence of each.
Append the remaining unused letters of \(\mathcal{A}\) in alphabetical order.
Fill the 5\(\times\)5 matrix row by row with the resulting 25-letter sequence.
Example. For keyword MONARCHY, the grid construction proceeds as:
Keyword letters (deduplicated): M, O, N, A, R, C, H, Y
Remaining alphabet letters: B, D, E, F, G, I, K, L, P, Q, S, T, U, V, W, X, Z
Combined sequence: M O N A R C H Y B D E F G I K L P Q S T U V W X Z
8.2.2 Digram Preparation#
Before encryption, the plaintext must be prepared into a sequence of digrams (letter pairs).
Definition 8.2 (Digram Preparation)
Given a plaintext string \(m\):
Convert to uppercase and replace J with I.
Remove all non-alphabetic characters.
Split into consecutive pairs of letters.
If both letters in a pair are identical, insert an X between them and re-pair.
If the final group contains only one letter, pad it with X.
The result is a sequence of digrams \((d_1, d_2, \ldots, d_n)\) where each \(d_i = (a_i, b_i)\) with \(a_i \neq b_i\).
Example. BALLOON \(\to\) BA, LX, LO, ON (X inserted between the two L’s).
8.2.3 The Three Encryption Rules#
Given a digram \((a, b)\) with grid positions \((r_a, c_a)\) and \((r_b, c_b)\), the Playfair cipher applies one of three rules:
Definition 8.3 (Playfair Encryption Rules)
Rule 1 – Same Row: If \(r_a = r_b\) (both letters are in the same row), replace each letter by the letter immediately to its right in the grid, wrapping around:
Rule 2 – Same Column: If \(c_a = c_b\) (both letters are in the same column), replace each letter by the letter immediately below it in the grid, wrapping around:
Rule 3 – Rectangle: If neither row nor column matches, the two letters define the corners of a rectangle. Replace each letter by the letter in its own row but the other letter’s column:
Decryption reverses these rules: shift left for same-row, shift up for same-column, and the rectangle rule is its own inverse.
Vulnerability
The Playfair cipher is a fixed permutation on the space of \(25 \times 24 = 600\) ordered digrams (since \(a \neq b\) is enforced). While this is a much larger space than the 26-letter monoalphabetic substitution, it is still subject to digram frequency analysis. In English, certain digrams (TH, HE, IN, ER, AN, …) occur far more frequently than others, and the substitution structure creates characteristic digram frequency signatures that a cryptanalyst can exploit.
8.3 Implementation#
We now build a complete PlayfairCipher class that handles grid construction, digram preparation, encryption, and decryption.
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
class PlayfairCipher:
"""Complete implementation of the Playfair cipher.
Handles grid construction from a keyword, digram preparation,
encryption, and decryption using the three Playfair rules.
"""
def __init__(self, keyword):
self.keyword = keyword.upper().replace('J', 'I')
self.grid = self._build_grid(keyword)
self.positions = {}
for i in range(5):
for j in range(5):
self.positions[self.grid[i][j]] = (i, j)
def _build_grid(self, keyword):
"""Build the 5x5 Playfair grid from a keyword.
Letters from the keyword are placed first (duplicates removed),
then the remaining alphabet letters fill the grid. I and J
are merged into a single cell (I).
"""
keyword = keyword.upper().replace('J', 'I')
seen = set()
ordered = []
for c in keyword:
if c.isalpha() and c not in seen:
seen.add(c)
ordered.append(c)
for c in 'ABCDEFGHIKLMNOPQRSTUVWXYZ': # No J
if c not in seen:
ordered.append(c)
return [ordered[i * 5:(i + 1) * 5] for i in range(5)]
def prepare_digrams(self, text):
"""Prepare plaintext into digrams for Playfair encryption.
- Converts to uppercase, replaces J with I, strips non-alpha.
- Inserts X between repeated letters in a pair.
- Pads with X if the text has odd length.
Returns a list of (char, char) tuples.
"""
text = text.upper().replace('J', 'I')
text = ''.join(c for c in text if c.isalpha())
digrams = []
i = 0
while i < len(text):
a = text[i]
if i + 1 < len(text):
b = text[i + 1]
if a == b:
digrams.append((a, 'X'))
i += 1
else:
digrams.append((a, b))
i += 2
else:
digrams.append((a, 'X'))
i += 1
return digrams
def _encrypt_digram(self, a, b):
"""Encrypt a single digram using the three Playfair rules."""
r1, c1 = self.positions[a]
r2, c2 = self.positions[b]
if r1 == r2: # Same row: shift right
return self.grid[r1][(c1 + 1) % 5], self.grid[r2][(c2 + 1) % 5]
elif c1 == c2: # Same column: shift down
return self.grid[(r1 + 1) % 5][c1], self.grid[(r2 + 1) % 5][c2]
else: # Rectangle: swap columns
return self.grid[r1][c2], self.grid[r2][c1]
def _decrypt_digram(self, a, b):
"""Decrypt a single digram (reverse of encryption rules)."""
r1, c1 = self.positions[a]
r2, c2 = self.positions[b]
if r1 == r2: # Same row: shift left
return self.grid[r1][(c1 - 1) % 5], self.grid[r2][(c2 - 1) % 5]
elif c1 == c2: # Same column: shift up
return self.grid[(r1 - 1) % 5][c1], self.grid[(r2 - 1) % 5][c2]
else: # Rectangle: swap columns (self-inverse)
return self.grid[r1][c2], self.grid[r2][c1]
def encrypt(self, plaintext):
"""Encrypt a plaintext string using the Playfair cipher."""
digrams = self.prepare_digrams(plaintext)
result = []
for a, b in digrams:
ea, eb = self._encrypt_digram(a, b)
result.extend([ea, eb])
return ''.join(result)
def decrypt(self, ciphertext):
"""Decrypt a ciphertext string using the Playfair cipher."""
text = ciphertext.upper().replace('J', 'I')
text = ''.join(c for c in text if c.isalpha())
result = []
for i in range(0, len(text), 2):
a, b = text[i], text[i + 1]
da, db = self._decrypt_digram(a, b)
result.extend([da, db])
return ''.join(result)
def display_grid(self):
"""Print the 5x5 Playfair grid."""
for row in self.grid:
print(' '.join(row))
def get_grid_array(self):
"""Return the grid as a numpy array of characters."""
return np.array(self.grid)
# --- Demonstration ---
pf = PlayfairCipher("MONARCHY")
print("Playfair Grid (keyword = 'MONARCHY'):")
print()
pf.display_grid()
pt = "INSTRUMENTS"
ct = pf.encrypt(pt)
dt = pf.decrypt(ct)
print(f"\nPlaintext: {pt}")
print(f"Encrypted: {ct}")
print(f"Decrypted: {dt}")
print(f"Round-trip: {'PASS' if dt.startswith(pt.upper().replace('J','I')) else 'CHECK (padding artifacts may differ)'}")
Playfair Grid (keyword = 'MONARCHY'):
M O N A R
C H Y B D
E F G I K
L P Q S T
U V W X Z
Plaintext: INSTRUMENTS
Encrypted: GATLMZCLRQXA
Decrypted: INSTRUMENTSX
Round-trip: PASS
Implementation note
The prepare_digrams method handles three edge cases that arise in Playfair encryption:
Repeated letters: When two identical letters fall in the same digram (e.g., LL in BALLOON), an X is inserted between them to break the pair. This is necessary because the Playfair rules require the two letters in a digram to occupy different grid positions.
Odd-length text: If the cleaned text has an odd number of characters, a trailing X is appended to form the final digram.
I/J merging: Since the 5\(\times\)5 grid has only 25 cells, J is replaced by I throughout. This means the cipher cannot distinguish between I and J in the decrypted output.
8.4 Cryptanalysis of the Playfair Cipher#
8.4.1 The Digram Permutation#
Theorem 8.1 (Playfair as a Digram Permutation)
For a fixed Playfair grid \(G\), the encryption function \(E_G\) is a permutation on the set of 600 ordered digrams \(\{(a, b) \in \mathcal{A}^2 : a \neq b\}\). That is, \(E_G\) is a bijection.
Proof sketch. Each of the three Playfair rules (same row, same column, rectangle) maps a digram \((a, b)\) to a unique digram \((a', b')\) with \(a' \neq b'\). The inverse rules (shift left, shift up, rectangle swap) provide an explicit inverse for each case. Since \(E_G\) is an invertible map on a finite set, it is a permutation. \(\square\)
8.4.2 Digram Frequency Analysis#
Because \(E_G\) is a fixed permutation on digrams, the Playfair cipher partially preserves certain digram frequency patterns (the substitution structure creates characteristic digram frequency signatures). In English, certain digrams occur much more frequently than others:
Rank |
Digram |
Approx. Frequency |
|---|---|---|
1 |
TH |
3.56% |
2 |
HE |
3.07% |
3 |
IN |
2.43% |
4 |
ER |
2.05% |
5 |
AN |
1.99% |
6 |
RE |
1.85% |
7 |
ON |
1.76% |
8 |
AT |
1.49% |
9 |
EN |
1.45% |
10 |
ND |
1.35% |
An analyst who identifies the most frequent ciphertext digrams can attempt to match them against these expected English digram frequencies.
8.4.3 Hill-Climbing and Simulated Annealing Attacks#
Modern computational attacks on the Playfair cipher use hill-climbing (or simulated annealing) with a fitness function based on quadgram statistics:
Start with a random 5\(\times\)5 grid.
Decrypt the ciphertext using this grid.
Score the resulting plaintext using log-probabilities of quadgrams (4-letter sequences).
Make a small random modification to the grid (swap two letters, swap two rows, swap two columns, etc.).
If the new grid produces a higher score, keep it; otherwise revert.
Repeat until convergence.
This approach can break Playfair ciphers with as few as 100–200 characters of ciphertext.
Experiments#
Experiment 1: Visualising the Playfair Grid#
We display the 5\(\times\)5 Playfair grid as a coloured matplotlib table, highlighting the keyword letters.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
def visualise_playfair_grid(cipher, title=None):
"""Display the Playfair grid as a coloured matplotlib table.
Keyword letters are highlighted in a darker shade.
"""
fig, ax = plt.subplots(figsize=(6, 6))
grid_arr = cipher.get_grid_array()
# Determine which letters came from the keyword
kw_letters = set()
seen = set()
for c in cipher.keyword:
if c.isalpha() and c not in seen:
seen.add(c)
kw_letters.add(c)
for i in range(5):
for j in range(5):
letter = grid_arr[i, j]
if letter in kw_letters:
bg_color = '#2E86C1' # blue for keyword letters
text_color = 'white'
else:
bg_color = '#D5F5E3' # light green for filler letters
text_color = '#1B4F72'
rect = plt.Rectangle((j, 4 - i), 1, 1,
facecolor=bg_color,
edgecolor='#1B4F72',
linewidth=2)
ax.add_patch(rect)
ax.text(j + 0.5, 4 - i + 0.5, letter,
ha='center', va='center',
fontsize=22, fontweight='bold',
color=text_color,
fontfamily='monospace')
ax.set_xlim(0, 5)
ax.set_ylim(0, 5)
ax.set_aspect('equal')
ax.axis('off')
if title is None:
title = f'Playfair Grid (keyword = \"{cipher.keyword}\")'
ax.set_title(title, fontsize=14, fontweight='bold', pad=15)
# Legend
from matplotlib.patches import Patch
legend_elements = [
Patch(facecolor='#2E86C1', edgecolor='#1B4F72', label='Keyword letters'),
Patch(facecolor='#D5F5E3', edgecolor='#1B4F72', label='Filler letters')
]
ax.legend(handles=legend_elements, loc='upper center',
bbox_to_anchor=(0.5, -0.02), ncol=2, fontsize=11)
plt.tight_layout()
return fig
# Display grids for two different keywords
pf1 = PlayfairCipher("MONARCHY")
fig1 = visualise_playfair_grid(pf1)
fig1.savefig('fig_ch08_grid_monarchy.png', dpi=150, bbox_inches='tight')
plt.show()
print("Figure saved: fig_ch08_grid_monarchy.png")
pf2 = PlayfairCipher("CRYPTANALYSIS")
fig2 = visualise_playfair_grid(pf2)
fig2.savefig('fig_ch08_grid_cryptanalysis.png', dpi=150, bbox_inches='tight')
plt.show()
print("Figure saved: fig_ch08_grid_cryptanalysis.png")
Figure saved: fig_ch08_grid_monarchy.png
Figure saved: fig_ch08_grid_cryptanalysis.png
Observation
The grid visualisation clearly shows how the keyword letters fill the first positions (blue cells) and the remaining alphabet letters follow in order (green cells). Different keywords produce completely different grids, and even a small change in the keyword rearranges many cells. The total number of possible Playfair grids is \(25! \approx 1.55 \times 10^{25}\), though many of these produce equivalent encryption due to row/column symmetries.
Experiment 2: Step-by-Step Encryption with Rule Annotations#
We encrypt a plaintext one digram at a time, showing which rule (same row, same column, or rectangle) is applied at each step.
import numpy as np
import matplotlib.pyplot as plt
def encrypt_step_by_step(cipher, plaintext):
"""Encrypt plaintext showing each digram transformation and the rule applied."""
digrams = cipher.prepare_digrams(plaintext)
print(f"Plaintext: {plaintext}")
print(f"Prepared digrams: {[''.join(d) for d in digrams]}")
print()
print(f"{'Step':>4s} {'Input':>6s} {'Pos(a)':>8s} {'Pos(b)':>8s} {'Rule':>12s} {'Output':>6s}")
print("-" * 58)
ciphertext = []
rule_counts = {'Same Row': 0, 'Same Column': 0, 'Rectangle': 0}
for step, (a, b) in enumerate(digrams, 1):
r1, c1 = cipher.positions[a]
r2, c2 = cipher.positions[b]
if r1 == r2:
rule = 'Same Row'
elif c1 == c2:
rule = 'Same Column'
else:
rule = 'Rectangle'
rule_counts[rule] += 1
ea, eb = cipher._encrypt_digram(a, b)
ciphertext.extend([ea, eb])
print(f"{int(step):>4d} {a}{b:>5s} ({r1},{c1}){' ':>4s} ({r2},{c2}){' ':>4s} {rule:>12s} {ea}{eb:>5s}")
ct_str = ''.join(ciphertext)
print(f"\nCiphertext: {ct_str}")
print(f"\nRule distribution:")
total = sum(rule_counts.values())
for rule, count in rule_counts.items():
print(f" {rule:>12s}: {int(count):>3d} / {total} ({float(100 * count / total):.1f}%)")
return ct_str, rule_counts
# Demonstrate with the MONARCHY grid
pf = PlayfairCipher("MONARCHY")
print("Grid:")
pf.display_grid()
print()
ct, rules = encrypt_step_by_step(pf, "MEET ME AT THE FOUNTAIN")
Grid:
M O N A R
C H Y B D
E F G I K
L P Q S T
U V W X Z
Plaintext: MEET ME AT THE FOUNTAIN
Prepared digrams: ['ME', 'ET', 'ME', 'AT', 'TH', 'EF', 'OU', 'NT', 'AI', 'NX']
Step Input Pos(a) Pos(b) Rule Output
----------------------------------------------------------
1 M E (0,0) (2,0) Same Column C L
2 E T (2,0) (3,4) Rectangle K L
3 M E (0,0) (2,0) Same Column C L
4 A T (0,3) (3,4) Rectangle R S
5 T H (3,4) (1,1) Rectangle P D
6 E F (2,0) (2,1) Same Row F G
7 O U (0,1) (4,0) Rectangle M V
8 N T (0,2) (3,4) Rectangle R Q
9 A I (0,3) (2,3) Same Column B S
10 N X (0,2) (4,3) Rectangle A W
Ciphertext: CLKLCLRSPDFGMVRQBSAW
Rule distribution:
Same Row: 1 / 10 (10.0%)
Same Column: 3 / 10 (30.0%)
Rectangle: 6 / 10 (60.0%)
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
def visualise_digram_on_grid(cipher, a, b, title=None):
"""Visualise a single digram encryption on the Playfair grid.
Highlights the input letters, the output letters, and draws
arrows indicating the rule applied.
"""
fig, ax = plt.subplots(figsize=(6, 6))
grid_arr = cipher.get_grid_array()
r1, c1 = cipher.positions[a]
r2, c2 = cipher.positions[b]
ea, eb = cipher._encrypt_digram(a, b)
re1, ce1 = cipher.positions[ea]
re2, ce2 = cipher.positions[eb]
if r1 == r2:
rule_name = 'Same Row'
elif c1 == c2:
rule_name = 'Same Column'
else:
rule_name = 'Rectangle'
for i in range(5):
for j in range(5):
letter = grid_arr[i, j]
y = 4 - i
x = j
# Determine cell colour
if (i, j) in [(r1, c1), (r2, c2)]:
bg_color = '#E74C3C' # red for input letters
text_color = 'white'
elif (i, j) in [(re1, ce1), (re2, ce2)]:
bg_color = '#27AE60' # green for output letters
text_color = 'white'
else:
bg_color = '#F0F0F0'
text_color = '#555555'
rect = plt.Rectangle((x, y), 1, 1,
facecolor=bg_color,
edgecolor='#333333',
linewidth=1.5)
ax.add_patch(rect)
ax.text(x + 0.5, y + 0.5, letter,
ha='center', va='center',
fontsize=18, fontweight='bold',
color=text_color, fontfamily='monospace')
# Draw arrows from input to output
for (ri, ci), (ro, co) in [((r1, c1), (re1, ce1)), ((r2, c2), (re2, ce2))]:
ax.annotate('',
xy=(co + 0.5, 4 - ro + 0.5),
xytext=(ci + 0.5, 4 - ri + 0.5),
arrowprops=dict(arrowstyle='->', color='#2C3E50',
lw=2.5, connectionstyle='arc3,rad=0.15'))
ax.set_xlim(0, 5)
ax.set_ylim(0, 5)
ax.set_aspect('equal')
ax.axis('off')
if title is None:
title = f'{a}{b} -> {ea}{eb} [{rule_name}]'
ax.set_title(title, fontsize=14, fontweight='bold', pad=15)
from matplotlib.patches import Patch
legend_elements = [
Patch(facecolor='#E74C3C', edgecolor='#333', label=f'Input: {a}, {b}'),
Patch(facecolor='#27AE60', edgecolor='#333', label=f'Output: {ea}, {eb}')
]
ax.legend(handles=legend_elements, loc='upper center',
bbox_to_anchor=(0.5, -0.02), ncol=2, fontsize=11)
plt.tight_layout()
return fig
# Show one example of each rule
pf = PlayfairCipher("MONARCHY")
# Same Row example: M and O are both in row 0
fig_row = visualise_digram_on_grid(pf, 'M', 'O')
fig_row.savefig('fig_ch08_rule_same_row.png', dpi=150, bbox_inches='tight')
plt.show()
# Same Column example: M and C are both in column 0
fig_col = visualise_digram_on_grid(pf, 'M', 'C')
fig_col.savefig('fig_ch08_rule_same_col.png', dpi=150, bbox_inches='tight')
plt.show()
# Rectangle example: I and N
fig_rect = visualise_digram_on_grid(pf, 'I', 'N')
fig_rect.savefig('fig_ch08_rule_rectangle.png', dpi=150, bbox_inches='tight')
plt.show()
print("Figures saved: fig_ch08_rule_same_row.png, fig_ch08_rule_same_col.png, fig_ch08_rule_rectangle.png")
Figures saved: fig_ch08_rule_same_row.png, fig_ch08_rule_same_col.png, fig_ch08_rule_rectangle.png
Observation
The three visualisations make the Playfair rules intuitive:
Same Row: Both letters slide one position to the right (wrapping from the last column back to the first).
Same Column: Both letters slide one position downward (wrapping from the bottom row back to the top).
Rectangle: The two letters define opposite corners of a rectangle; each is replaced by the letter in the other corner of its row.
The rectangle rule is the most common in practice (it applies whenever the two letters are in different rows and different columns), and it accounts for roughly 70–80% of digrams in typical text.
Experiment 3: Digram Frequency Heatmaps – Plaintext vs. Ciphertext#
We compute the 25\(\times\)25 digram frequency matrix for both a plaintext and its Playfair-encrypted ciphertext, then visualise them as heatmaps to see how the Playfair cipher transforms the digram distribution.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
# A substantial English plaintext
english_text = (
"Ciphers oh ciphers secrets they keep "
"Locked away in code deep and discreet "
"Symbols and numbers jumbled and mixed "
"A message encoded ready to be fixed "
"Through history they have been used to hide "
"Plans of war love letters beside "
"The Rosetta Stone a mystery solved "
"A codebreakers work duly evolved "
"From Caesar to Enigma through time they change "
"Yet the essence remains mysterious and strange "
"A puzzle to solve a game to play "
"A message to decipher in every way "
"Crack the code reveal the truth "
"A challenge to minds sharp and astute "
"For ciphers oh ciphers they hold the key "
"To secrets untold waiting to be set free "
"Deep within the caves so dark and cold "
"The dwarves they sat and stories told "
"Of treasure hoards and ancient lore "
"And secrets kept for evermore "
"But in their hands they held a tool "
"A wondrous thing so sharp and cool "
"A blade of steel that could carve letters "
"And keep their secrets safe forever"
)
# Playfair alphabet (I/J merged, no J)
PF_ALPHA = 'ABCDEFGHIKLMNOPQRSTUVWXYZ'
PF_INDEX = {ch: idx for idx, ch in enumerate(PF_ALPHA)}
def digram_frequency_matrix(text):
"""Compute a 25x25 digram frequency matrix (I/J merged).
Entry (i, j) counts the number of times the digram
(PF_ALPHA[i], PF_ALPHA[j]) appears as consecutive letter pairs.
"""
cleaned = text.upper().replace('J', 'I')
cleaned = ''.join(c for c in cleaned if c in PF_INDEX)
mat = np.zeros((25, 25), dtype=float)
for k in range(len(cleaned) - 1):
i = PF_INDEX[cleaned[k]]
j = PF_INDEX[cleaned[k + 1]]
mat[i, j] += 1
total = mat.sum()
if total > 0:
mat /= total
return mat
# Encrypt the text
pf = PlayfairCipher("MONARCHY")
ct = pf.encrypt(english_text)
# Compute digram frequency matrices
pt_matrix = digram_frequency_matrix(english_text)
ct_matrix = digram_frequency_matrix(ct)
# Plot side by side
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(16, 7))
tick_labels = list(PF_ALPHA)
im1 = ax1.imshow(pt_matrix, cmap='YlOrRd', aspect='equal')
ax1.set_xticks(range(25))
ax1.set_yticks(range(25))
ax1.set_xticklabels(tick_labels, fontsize=7)
ax1.set_yticklabels(tick_labels, fontsize=7)
ax1.set_xlabel('Second letter', fontsize=11)
ax1.set_ylabel('First letter', fontsize=11)
ax1.set_title('Plaintext Digram Frequencies', fontsize=13)
fig.colorbar(im1, ax=ax1, fraction=0.046, pad=0.04)
im2 = ax2.imshow(ct_matrix, cmap='YlOrRd', aspect='equal')
ax2.set_xticks(range(25))
ax2.set_yticks(range(25))
ax2.set_xticklabels(tick_labels, fontsize=7)
ax2.set_yticklabels(tick_labels, fontsize=7)
ax2.set_xlabel('Second letter', fontsize=11)
ax2.set_ylabel('First letter', fontsize=11)
ax2.set_title('Ciphertext Digram Frequencies', fontsize=13)
fig.colorbar(im2, ax=ax2, fraction=0.046, pad=0.04)
fig.suptitle('Digram Frequency Analysis: Plaintext vs. Playfair Ciphertext',
fontsize=14, fontweight='bold', y=1.02)
plt.tight_layout()
fig.savefig('fig_ch08_digram_heatmaps.png', dpi=150, bbox_inches='tight')
plt.show()
print("Figure saved: fig_ch08_digram_heatmaps.png")
# Print the top digrams in each
print("\nTop 10 plaintext digrams:")
flat_pt = [(pt_matrix[i, j], PF_ALPHA[i] + PF_ALPHA[j])
for i in range(25) for j in range(25)]
flat_pt.sort(reverse=True)
for freq, dg in flat_pt[:10]:
print(f" {dg}: {float(freq):.4f}")
print("\nTop 10 ciphertext digrams:")
flat_ct = [(ct_matrix[i, j], PF_ALPHA[i] + PF_ALPHA[j])
for i in range(25) for j in range(25)]
flat_ct.sort(reverse=True)
for freq, dg in flat_ct[:10]:
print(f" {dg}: {float(freq):.4f}")
Figure saved: fig_ch08_digram_heatmaps.png
Top 10 plaintext digrams:
TH: 0.0286
HE: 0.0286
ET: 0.0232
ER: 0.0232
RE: 0.0218
AN: 0.0218
TO: 0.0204
ST: 0.0191
ND: 0.0191
VE: 0.0163
Top 10 ciphertext digrams:
RA: 0.0174
UF: 0.0160
TL: 0.0160
KL: 0.0160
PD: 0.0147
MP: 0.0147
KM: 0.0147
CF: 0.0147
MK: 0.0134
HM: 0.0134
Observation
The plaintext heatmap shows the characteristic English digram distribution: a few very hot spots (TH, HE, IN, ER, AN) surrounded by many near-zero entries. The ciphertext heatmap has the same overall shape – the same number of hot spots with similar magnitudes – but they have been shuffled to different positions by the Playfair permutation. This is the fundamental vulnerability: the substitution structure creates characteristic digram frequency signatures that can be exploited.
Note also that the diagonal of both matrices is mostly zero: in the plaintext, identical consecutive letters are relatively rare, and in the ciphertext, the Playfair construction ensures no digram encrypts to a repeated letter.
Experiment 4: Hill-Climbing Attack on a Playfair Ciphertext#
We implement a hill-climbing attack using bigram-based log-probabilities as a simplified fitness function (a full attack would use genuine quadgram statistics from a large English corpus). The attack starts from a random grid and iteratively improves it by making small random modifications.
import numpy as np
import matplotlib.pyplot as plt
# --- Quadgram scoring ---
# We build an approximate quadgram log-probability table from English text.
# In a real attack, one would use a precomputed table from a large corpus.
# English letter frequencies for generating synthetic quadgram scores
ENGLISH_FREQ = np.array([
0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228,
0.02015, 0.06094, 0.06966, 0.00153, 0.00772, 0.04025,
0.02406, 0.06749, 0.07507, 0.01929, 0.00095, 0.05987,
0.06327, 0.09056, 0.02758, 0.00978, 0.02360, 0.00150,
0.01974, 0.00074
])
class QuadgramScorer:
"""Score text based on quadgram (4-letter) log-probabilities.
Uses an approximate model based on English bigram frequencies.
For a production attack, replace with a table built from a large corpus.
"""
def __init__(self):
# Build approximate scoring from common English bigrams
self.bigram_log = np.full((26, 26), -10.0)
# Top English bigrams with approximate log-probabilities
top_bigrams = {
'TH': -1.5, 'HE': -1.6, 'IN': -1.8, 'ER': -1.9, 'AN': -2.0,
'RE': -2.1, 'ON': -2.1, 'AT': -2.2, 'EN': -2.2, 'ND': -2.3,
'TI': -2.3, 'ES': -2.3, 'OR': -2.4, 'TE': -2.4, 'OF': -2.4,
'ED': -2.5, 'IS': -2.5, 'IT': -2.5, 'AL': -2.6, 'AR': -2.6,
'ST': -2.6, 'TO': -2.6, 'NT': -2.7, 'NG': -2.7, 'SE': -2.7,
'HA': -2.7, 'AS': -2.8, 'OU': -2.8, 'IO': -2.8, 'LE': -2.8,
'VE': -2.9, 'CO': -2.9, 'ME': -2.9, 'DE': -2.9, 'HI': -3.0,
'RI': -3.0, 'RO': -3.0, 'IC': -3.0, 'NE': -3.0, 'EA': -3.0,
'RA': -3.1, 'CE': -3.1, 'LI': -3.1, 'CH': -3.1, 'LL': -3.2,
'BE': -3.2, 'MA': -3.2, 'SI': -3.2, 'OM': -3.2, 'UR': -3.2
}
for bg, logp in top_bigrams.items():
i = ord(bg[0]) - ord('A')
j = ord(bg[1]) - ord('A')
self.bigram_log[i, j] = logp
# Fill remaining with frequency-based estimates
for i in range(26):
for j in range(26):
if self.bigram_log[i, j] == -10.0:
self.bigram_log[i, j] = np.log10(
max(ENGLISH_FREQ[i] * ENGLISH_FREQ[j], 1e-8))
def score(self, text):
"""Score text using sum of overlapping bigram log-probabilities.
Higher scores indicate more English-like text.
"""
text = text.upper()
text = ''.join(c for c in text if c.isalpha())
if len(text) < 4:
return -float('inf')
total = 0.0
for k in range(len(text) - 1):
i = ord(text[k]) - ord('A')
j = ord(text[k + 1]) - ord('A')
if 0 <= i < 26 and 0 <= j < 26:
total += self.bigram_log[i, j]
return total
class PlayfairHillClimber:
"""Hill-climbing attack on the Playfair cipher.
Starts with a random grid and iteratively makes small random
modifications, keeping changes that improve the fitness score.
"""
PF_ALPHA = 'ABCDEFGHIKLMNOPQRSTUVWXYZ'
def __init__(self, scorer):
self.scorer = scorer
def _random_grid(self, rng):
"""Generate a random 5x5 Playfair grid."""
letters = list(self.PF_ALPHA)
rng.shuffle(letters)
return [letters[i * 5:(i + 1) * 5] for i in range(5)]
def _grid_to_flat(self, grid):
return [ch for row in grid for ch in row]
def _flat_to_grid(self, flat):
return [flat[i * 5:(i + 1) * 5] for i in range(5)]
def _decrypt_with_grid(self, ciphertext, grid):
"""Decrypt ciphertext using a given grid."""
positions = {}
for i in range(5):
for j in range(5):
positions[grid[i][j]] = (i, j)
text = ciphertext.upper().replace('J', 'I')
text = ''.join(c for c in text if c.isalpha())
result = []
for k in range(0, len(text) - 1, 2):
a, b = text[k], text[k + 1]
if a not in positions or b not in positions:
result.extend([a, b])
continue
r1, c1 = positions[a]
r2, c2 = positions[b]
if r1 == r2:
result.append(grid[r1][(c1 - 1) % 5])
result.append(grid[r2][(c2 - 1) % 5])
elif c1 == c2:
result.append(grid[(r1 - 1) % 5][c1])
result.append(grid[(r2 - 1) % 5][c2])
else:
result.append(grid[r1][c2])
result.append(grid[r2][c1])
return ''.join(result)
def _mutate(self, flat, rng):
"""Apply a random mutation to the grid."""
new_flat = flat[:]
mutation_type = rng.integers(0, 6)
if mutation_type <= 2:
# Swap two random letters
i, j = rng.choice(25, size=2, replace=False)
new_flat[i], new_flat[j] = new_flat[j], new_flat[i]
elif mutation_type == 3:
# Swap two rows
r1, r2 = rng.choice(5, size=2, replace=False)
for c in range(5):
new_flat[r1 * 5 + c], new_flat[r2 * 5 + c] = \
new_flat[r2 * 5 + c], new_flat[r1 * 5 + c]
elif mutation_type == 4:
# Swap two columns
c1, c2 = rng.choice(5, size=2, replace=False)
for r in range(5):
new_flat[r * 5 + c1], new_flat[r * 5 + c2] = \
new_flat[r * 5 + c2], new_flat[r * 5 + c1]
else:
# Reverse a random section
i = rng.integers(0, 20)
j = rng.integers(i + 2, 25)
new_flat[i:j + 1] = new_flat[i:j + 1][::-1]
return new_flat
def attack(self, ciphertext, max_iterations=5000, restarts=3, seed=42):
"""Run the hill-climbing attack.
Returns the best grid found, the decrypted text, the score,
and the score history for each restart.
"""
rng = np.random.default_rng(seed)
best_score_overall = -float('inf')
best_grid_overall = None
best_text_overall = None
all_histories = []
for restart in range(restarts):
grid = self._random_grid(rng)
flat = self._grid_to_flat(grid)
decrypted = self._decrypt_with_grid(ciphertext, grid)
current_score = self.scorer.score(decrypted)
best_score = current_score
best_flat = flat[:]
history = [current_score]
no_improvement = 0
for iteration in range(max_iterations):
new_flat = self._mutate(flat, rng)
new_grid = self._flat_to_grid(new_flat)
new_decrypted = self._decrypt_with_grid(ciphertext, new_grid)
new_score = self.scorer.score(new_decrypted)
if new_score > current_score:
flat = new_flat
current_score = new_score
no_improvement = 0
if new_score > best_score:
best_score = new_score
best_flat = new_flat[:]
else:
no_improvement += 1
history.append(current_score)
# Early termination if stuck
if no_improvement > 1000:
break
all_histories.append(history)
if best_score > best_score_overall:
best_score_overall = best_score
best_grid_overall = self._flat_to_grid(best_flat)
best_text_overall = self._decrypt_with_grid(
ciphertext, best_grid_overall)
print(f" Restart {restart + 1}/{restarts}: "
f"best score = {float(best_score):.2f} "
f"(iterations: {len(history)})")
return best_grid_overall, best_text_overall, best_score_overall, all_histories
# --- Run the attack ---
# Encrypt a message with a known key
pf_true = PlayfairCipher("MONARCHY")
plaintext_original = (
"THE PLAYFAIR CIPHER WAS THE FIRST PRACTICAL DIGRAPHIC "
"SUBSTITUTION CIPHER IT WAS INVENTED BY CHARLES WHEATSTONE "
"IN EIGHTEEN FIFTY FOUR BUT BEARS THE NAME OF LORD PLAYFAIR "
"WHO PROMOTED THE USE OF THE CIPHER BY THE BRITISH MILITARY"
)
ciphertext_attack = pf_true.encrypt(plaintext_original)
print(f"Ciphertext length: {len(ciphertext_attack)} characters")
print(f"Ciphertext (first 80): {ciphertext_attack[:80]}")
print()
# Run hill-climbing
scorer = QuadgramScorer()
climber = PlayfairHillClimber(scorer)
print("Running hill-climbing attack...")
best_grid, best_text, best_score, histories = climber.attack(
ciphertext_attack, max_iterations=8000, restarts=5, seed=42
)
print(f"\nBest score: {float(best_score):.2f}")
print(f"\nRecovered grid:")
for row in best_grid:
print(' '.join(row))
print(f"\nTrue grid:")
pf_true.display_grid()
print(f"\nDecrypted text (first 120 chars):")
print(f" {best_text[:120]}")
print(f"\nOriginal plaintext (first 120 chars):")
clean_orig = plaintext_original.upper().replace('J', 'I')
clean_orig = ''.join(c for c in clean_orig if c.isalpha())
print(f" {clean_orig[:120]}")
Ciphertext length: 192 characters
Ciphertext (first 80): PDFLSMHGBSMDFSCFNZBXPDFGKATLTOMBSKBMTCKIMRVFEBLXIXSKLZSKNABEVFKMKSXNXSOWGMLKCDBH
Running hill-climbing attack...
Restart 1/5: best score = -505.51 (iterations: 1690)
Restart 2/5: best score = -514.31 (iterations: 3892)
Restart 3/5: best score = -506.29 (iterations: 5962)
Restart 4/5: best score = -500.97 (iterations: 4199)
Restart 5/5: best score = -514.88 (iterations: 2109)
Best score: -500.97
Recovered grid:
R I L K Y
Q V Z U W
G A C O H
X F E B D
T M S N P
True grid:
M O N A R
C H Y B D
E F G I K
L P Q S T
U V W X Z
Decrypted text (first 120 chars):
DHEIMTOHENPFEMAESUEDDHXAIOSRNGNFNLFNSGLRTIIAFERERFNLSLNLMOEFIAINLNBTETHUATILHEDOOUTPRIWIMFRSTYTAHGBIDIILATORYNOHFIHFLSAL
Original plaintext (first 120 chars):
THEPLAYFAIRCIPHERWASTHEFIRSTPRACTICALDIGRAPHICSUBSTITUTIONCIPHERITWASINVENTEDBYCHARLESWHEATSTONEINEIGHTEENFIFTYFOURBUTBE
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
# Plot the score history for each restart
fig, ax = plt.subplots(figsize=(10, 5))
colors = plt.cm.Set2(np.linspace(0, 1, len(histories)))
for idx, history in enumerate(histories):
ax.plot(history, color=colors[idx], linewidth=1.2, alpha=0.8,
label=f'Restart {idx + 1}')
ax.set_xlabel('Iteration', fontsize=12)
ax.set_ylabel('Fitness score (log-probability)', fontsize=12)
ax.set_title('Hill-Climbing Attack on Playfair Cipher: Score Convergence',
fontsize=13)
ax.legend(fontsize=10)
ax.grid(alpha=0.3)
plt.tight_layout()
fig.savefig('fig_ch08_hill_climbing.png', dpi=150, bbox_inches='tight')
plt.show()
print("Figure saved: fig_ch08_hill_climbing.png")
Figure saved: fig_ch08_hill_climbing.png
Observation
The hill-climbing attack shows characteristic convergence behaviour:
Early iterations produce rapid score improvements as the random grid is gradually reorganised.
Later iterations show diminishing returns as the grid approaches a local (or global) optimum.
Multiple restarts help escape local optima – different starting grids may converge to different solutions.
The recovered text may not be a perfect match due to the simplified scoring function used here. A production attack using genuine quadgram statistics from a large English corpus (e.g., \(26^4 \approx 450{,}000\) quadgram entries) would achieve much better accuracy. With sufficient ciphertext (200+ characters), the hill-climbing approach can fully recover the Playfair key grid.
Experiment 5: N-gram Fitness Functions#
In Experiment 4 we used a simplified bigram-based scoring function. Real-world automated cipher attacks use n-gram log-probability scoring built from a reference corpus of natural English. This experiment builds such a scorer from scratch and demonstrates the clear separation it provides between English and random text.
The idea. Given a reference corpus, we count every overlapping sequence of \(n\) letters. For example, for the text ATTACK the bigrams are AT, TT, TA, AC, CK; the trigrams are ATT, TTA, TAC, ACK; and the quadgrams are ATTA, TTAC, TACK. We convert raw counts to relative frequencies and take \(\log_{10}\), giving each n-gram a log-probability. N-grams not observed in the corpus receive a small floor value to avoid \(\log(0)\).
The fitness score of a candidate decryption is the sum of the log-probabilities of all its overlapping n-grams:
Which n-gram size to use? Longer n-grams capture more linguistic context but require exponentially more corpus data. There are \(26^n\) possible n-grams: 676 bigrams, 17,576 trigrams, and 456,976 quadgrams. With a modest inline corpus (~10,000 characters), we get excellent coverage of bigrams (~600/676) and good trigram coverage, but sparse quadgram coverage. Production systems with million-character corpora use quadgrams; for our inline corpus, we combine bigram and trigram scoring for a robust fitness function.
Why does this work? Incorrect decryptions produce unnatural n-gram distributions. Natural English text has many high-probability n-grams (TH, HE, THE, ING, TION, …) and scores significantly higher than random text, providing a smooth landscape for optimisation.
import numpy as np
import math
# --- Inline English corpus for building n-gram tables ---
# This is a concatenation of classic English prose passages (all public domain).
# After cleaning, it provides ~10,000+ alphabetic characters.
SAMPLE_CORPUS = (
"it was the best of times it was the worst of times it was the age of wisdom "
"it was the age of foolishness it was the epoch of belief it was the epoch of "
"incredulity it was the season of light it was the season of darkness it was "
"the spring of hope it was the winter of despair we had everything before us "
"we had nothing before us we were all going direct to heaven we were all going "
"direct the other way in short the period was so far like the present period "
"that some of its noisiest authorities insisted on its being received for good "
"or for evil in the superlative degree of comparison only there were a king "
"with a large jaw and a queen with a plain face on the throne of england there "
"were a king with a large jaw and a queen with a fair face on the throne of "
"france in both countries it was clearer than crystal to the lords of the state "
"preserves of loaves and fishes that things in general were settled for ever "
"call me ishmael some years ago never mind how long precisely having little or "
"no money in my purse and nothing particular to interest me on shore i thought "
"i would sail about a little and see the watery part of the world it is a way "
"i have of driving off the spleen and regulating the circulation whenever i find "
"myself growing grim about the mouth whenever it is a damp drizzly november in "
"my soul whenever i find myself involuntarily pausing before coffin warehouses "
"and bringing up the rear of every funeral i meet and especially whenever my "
"hypos get such an upper hand of me that it requires a strong moral principle "
"to prevent me from deliberately stepping into the street and methodically "
"knocking peoples hats off then i account it high time to get to sea as soon "
"as possible this is my substitute for pistol and ball with a philosophical "
"flourish cato throws himself upon his sword i quietly take to the ship there "
"is nothing surprising in this if they but knew it almost all men in their "
"degree some time or other cherish very nearly the same feelings towards the "
"ocean with me there now is your insular city of the manhattoes belted round "
"by wharves as indian isles by coral reefs commerce surrounds it with her surf "
"right and left the streets take you waterward its extreme downtown is the "
"battery where that noble mole is washed by waves and cooled by breezes which "
"a few hours previous were out of sight of land look at the crowds of water "
"gazers there circumambulate the city of a dreamy sabbath afternoon go from "
"corlears hook to coenties slip and from thence by whitehall northward what "
"do you see posted like silent sentinels all around the town stand thousands "
"upon thousands of mortal men fixed in ocean reveries some leaning against the "
"spiles some seated upon the pier heads some looking over the bulwarks of ships "
"from china some aloft in the rigging as if striving to get a still better "
"seaward peep but these are all landsmen of week days pent up in lath and "
"plaster tied to counters nailed to benches clinched to desks how then is this "
"are the green fields gone what do they here but look here come more crowds "
"pacing straight for the water and seemingly bound for a dive nothing will "
"content them but the extremest limit of the land loitering under the shady "
"lee of yonder warehouses will not suffice no they must get just as nigh the "
"water as they possibly can without falling in and there they stand miles of "
"them leagues inlanders all they come from lanes and alleys streets and avenues "
"north south east and west yet here they all unite tell me does the magnetic "
"virtue of the needles of the compasses of all those ships attract them thither "
"the quick brown fox jumps over the lazy dog the five boxing wizards jump quickly "
"pack my box with five dozen liquor jugs how vexingly quick daft zebras jump "
"the sun shone having no alternative on the nothing new the earth makes of the "
"sea the same old round the whole dull story all the same nothing to be done "
"the night was dark and full of terrors the wind howled through the ancient trees "
"and the rain beat against the windows of the old castle deep within the chamber "
"a single candle flickered casting long shadows across the stone walls the "
"cryptanalyst sat hunched over the desk surrounded by sheaves of paper covered "
"with columns of letters and numbers she had been working on this cipher for "
"three days now and the solution still eluded her the ciphertext was long enough "
"to work with but the encryption method was unlike anything she had seen before "
"the frequency distribution was nearly flat suggesting either a polyalphabetic "
"cipher or some form of transposition perhaps both she reached for her coffee "
"now cold and took a long sip the answer was in these letters somewhere she "
"just had to find the right pattern the right key that would unlock the message "
"hidden within the cipher the art of cryptanalysis is as old as the art of "
"cryptography itself for as long as people have been hiding messages others "
"have been trying to read them the earliest known use of cryptography dates "
"back to ancient egypt where scribes used nonstandard hieroglyphs to obscure "
"their writings the spartans used a device called the scytale a cylinder around "
"which a strip of parchment was wound and the message was written along the "
"length of the cylinder julius caesar famously used a simple substitution cipher "
"shifting each letter by three positions in the alphabet today we call this the "
"caesar cipher and while it is trivially easy to break it represents one of the "
"oldest documented examples of encryption in the western world the history of "
"cryptanalysis took a major turn with the work of the arab scholar al kindi who "
"in the ninth century wrote a manuscript on deciphering cryptographic messages "
"in which he described the technique of frequency analysis this method exploits "
"the fact that in any natural language certain letters appear more frequently "
"than others in english the letter e is by far the most common followed by t a "
"o i n and s by counting the frequency of each letter in a ciphertext and "
"comparing it to the known frequency distribution of the language one can often "
"deduce the substitution table and recover the plaintext the renaissance saw "
"the development of polyalphabetic ciphers most notably the vigenere cipher "
"which was considered unbreakable for centuries and earned the nickname the "
"indecipherable cipher it was not until the nineteenth century that charles "
"babbage and later friedrich kasiski independently developed methods to break it "
"the twentieth century brought mechanical and then electronic cipher machines "
"the most famous being the german enigma machine used extensively during world "
"war two the breaking of enigma by polish mathematicians marian rejewski jerzy "
"rozycki and henryk zygalski and later by the british team at bletchley park "
"led by alan turing is one of the greatest intellectual achievements in the "
"history of warfare the effort saved countless lives and arguably shortened the "
"war by several years in the modern era cryptography has become a mathematical "
"discipline based on computational complexity theory the security of modern "
"ciphers rests not on the secrecy of the algorithm but on the difficulty of "
"certain mathematical problems such as integer factorization and the discrete "
"logarithm problem despite the theoretical strength of modern cryptosystems "
"classical ciphers remain important as teaching tools and as subjects of study "
"they illustrate fundamental principles of confusion and diffusion key space "
"analysis and the interplay between encryption and cryptanalysis that define "
"the field to this day "
"the importance of the statistical properties of language for cryptanalysis "
"cannot be overstated every natural language has characteristic patterns in "
"the frequency of individual letters the frequency of letter pairs and the "
"frequency of longer sequences these patterns persist even when the text is "
"transformed by encryption and it is precisely these residual patterns that "
"the cryptanalyst exploits to recover the plaintext in english the most "
"common letters are e t a o i n s h r with e appearing roughly twelve "
"percent of the time the most common bigrams include th he in er an re "
"on at en nd and the most common trigrams are the and tha ent ion for "
"these patterns form the foundation of both classical and modern automated "
"cryptanalysis techniques the transition from manual to automated methods "
"was driven by the increasing complexity of cipher systems and the growing "
"availability of computational resources what once required weeks of patient "
"hand analysis can now be accomplished in seconds by a computer program "
"armed with the right statistical tools and search algorithms "
"the playfair cipher occupies an interesting position in the history of "
"cryptography it was advanced enough to resist simple frequency analysis "
"of individual letters but not so complex as to require mechanical aids "
"for its operation this made it ideal for field use where soldiers and "
"agents needed a cipher they could operate from memory without any special "
"equipment the british military found this combination of moderate security "
"and high convenience irresistible and the cipher saw active service from "
"the boer war through world war two its eventual obsolescence was due not "
"to any dramatic breakthrough in cryptanalysis but rather to the development "
"of more sophisticated machine ciphers that offered much higher security "
"while remaining practical for military communications "
"in the field of information theory claude shannon established that the "
"security of a cipher depends on two fundamental quantities the entropy "
"of the key and the redundancy of the language the higher the key entropy "
"the more possible keys an attacker must consider the higher the language "
"redundancy the more statistical information leaks through the encryption "
"for english text the redundancy is approximately one point five bits per "
"letter meaning that roughly half the information in english text is "
"predictable from the statistical structure of the language this redundancy "
"is what makes frequency analysis and its modern descendants so effective "
"the unicity distance of a cipher is the minimum amount of ciphertext needed "
"for there to be essentially one possible decryption on average for simple "
"substitution ciphers this is about twenty five letters for the playfair "
"cipher it is somewhat longer because the digraphic nature of the encryption "
"provides better diffusion of statistical patterns "
"when we consider the problem of breaking a cipher by automated search we "
"must think carefully about the structure of the search space the key space "
"of the playfair cipher contains twenty five factorial possible grids which "
"is approximately one point five five times ten to the twenty fifth power "
"this is far too large to search exhaustively but the fitness landscape "
"defined by quadgram scoring has enough structure to guide a stochastic "
"search algorithm toward the correct solution the key insight is that small "
"changes to the grid typically produce small changes in the fitness score "
"creating a relatively smooth landscape that hill climbing and simulated "
"annealing can navigate effectively the exception is when the algorithm "
"encounters a local optimum where the grid is close to correct but a few "
"letters are swapped this is where simulated annealing has a significant "
"advantage over pure hill climbing because the probabilistic acceptance "
"of worse solutions allows the search to escape these traps "
"throughout the centuries the contest between codemakers and codebreakers "
"has driven innovation on both sides each new cipher prompted the development "
"of new analytical techniques and each analytical breakthrough spurred the "
"creation of stronger ciphers this evolutionary dynamic continues today in "
"the modern world of public key cryptography and quantum computing where "
"the stakes are higher than ever before the fundamental principles however "
"remain the same confusion diffusion key space analysis and the statistical "
"properties of natural language continue to be the cornerstones of both "
"cryptography and cryptanalysis just as they were in the time of wheatstone "
"and playfair"
)
def clean_text_upper(text):
"""Remove non-alphabetic characters and convert to uppercase, merging I/J."""
return ''.join(c.upper() for c in text if c.isalpha()).replace('J', 'I')
class NgramFitness:
"""Score text using n-gram log-probabilities from a corpus.
Supports any n-gram size. For a modest inline corpus, bigrams (n=2)
and trigrams (n=3) give the best coverage. The class can also combine
multiple n-gram sizes for a more robust score.
"""
def __init__(self, corpus_text, n):
text = clean_text_upper(corpus_text)
self.n = n
self.ngrams = {}
for i in range(len(text) - n + 1):
gram = text[i:i+n]
self.ngrams[gram] = self.ngrams.get(gram, 0) + 1
total = sum(self.ngrams.values())
self.total = total
self.floor = math.log10(0.01 / total)
for gram in self.ngrams:
self.ngrams[gram] = math.log10(self.ngrams[gram] / total)
def score(self, text):
"""Sum of log10 probabilities of all overlapping n-grams."""
text = clean_text_upper(text)
s = 0.0
n_grams = len(text) - self.n + 1
if n_grams <= 0:
return self.floor
for i in range(n_grams):
gram = text[i:i+self.n]
s += self.ngrams.get(gram, self.floor)
return s
def score_per_ngram(self, text):
"""Average score per n-gram."""
text = clean_text_upper(text)
n_grams = len(text) - self.n + 1
if n_grams <= 0:
return self.floor
return self.score(text) / n_grams
class CombinedFitness:
"""Combine multiple n-gram scorers with given weights.
This provides a more robust fitness function than any single n-gram size,
especially when the corpus is modest.
"""
def __init__(self, scorers, weights):
self.scorers = scorers
self.weights = weights
def score(self, text):
return sum(w * s.score(text) for w, s in zip(self.weights, self.scorers))
def score_per_ngram(self, text):
text_clean = clean_text_upper(text)
total = 0.0
total_ngrams = 0
for w, s in zip(self.weights, self.scorers):
n_grams = len(text_clean) - s.n + 1
if n_grams > 0:
total += w * s.score(text)
total_ngrams += n_grams
return total / max(total_ngrams, 1)
# Build scorers for different n-gram sizes
corpus_clean = clean_text_upper(SAMPLE_CORPUS)
print(f"Corpus length: {len(corpus_clean)} characters")
scorer_bi = NgramFitness(SAMPLE_CORPUS, 2)
scorer_tri = NgramFitness(SAMPLE_CORPUS, 3)
scorer_quad = NgramFitness(SAMPLE_CORPUS, 4)
print(f"\nN-gram coverage:")
print(f" Bigrams: {len(scorer_bi.ngrams):>5d} / {26**2} ({100*len(scorer_bi.ngrams)/26**2:.1f}%)")
print(f" Trigrams: {len(scorer_tri.ngrams):>5d} / {26**3} ({100*len(scorer_tri.ngrams)/26**3:.1f}%)")
print(f" Quadgrams: {len(scorer_quad.ngrams):>5d} / {26**4} ({100*len(scorer_quad.ngrams)/26**4:.1f}%)")
# Combined fitness: weight bigrams and trigrams more heavily than quadgrams
# because our corpus gives much better coverage for shorter n-grams
fitness = CombinedFitness(
scorers=[scorer_bi, scorer_tri, scorer_quad],
weights=[0.3, 0.5, 0.2]
)
# --- Demonstrate English vs random text separation ---
english_samples = [
"THE PLAYFAIR CIPHER WAS THE FIRST PRACTICAL DIGRAPHIC SUBSTITUTION",
"IN THE BEGINNING WAS THE WORD AND THE WORD WAS WITH GOD",
"TO BE OR NOT TO BE THAT IS THE QUESTION WHETHER TIS NOBLER",
"THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG EVERY DAY",
"FREQUENCY ANALYSIS IS THE BASIC TOOL OF THE CRYPTANALYST",
]
random_samples = []
rng = np.random.default_rng(42)
for _ in range(5):
letters = [chr(ord('A') + rng.integers(0, 26)) for _ in range(60)]
random_samples.append(''.join(letters))
print("\n--- English text (combined fitness per n-gram) ---")
for sample in english_samples:
spq = fitness.score_per_ngram(sample)
print(f" {spq:+.3f} {sample[:50]}...")
print("\n--- Random text (combined fitness per n-gram) ---")
for sample in random_samples:
spq = fitness.score_per_ngram(sample)
print(f" {spq:+.3f} {sample[:50]}...")
Corpus length: 10050 characters
N-gram coverage:
Bigrams: 433 / 676 (64.1%)
Trigrams: 2496 / 17576 (14.2%)
Quadgrams: 5350 / 456976 (1.2%)
--- English text (combined fitness per n-gram) ---
-1.036 THE PLAYFAIR CIPHER WAS THE FIRST PRACTICAL DIGRAP...
-1.110 IN THE BEGINNING WAS THE WORD AND THE WORD WAS WIT...
-0.990 TO BE OR NOT TO BE THAT IS THE QUESTION WHETHER TI...
-1.107 THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG EVERY ...
-0.956 FREQUENCY ANALYSIS IS THE BASIC TOOL OF THE CRYPTA...
--- Random text (combined fitness per n-gram) ---
-1.657 CURLLWCSFCNZTTSUNDVLNJEYUQKVOLLFCOXBWVHQETSJBZLXRU...
-1.698 XTJZKIXJBMUEMDRMIFORYLEVQSCITVLUVKXHGRQDVFUAUUURMS...
-1.691 LRRMWOCTOQOOCOUHPAJLZFHKZWAGVBWHXHLRDONUZRKKKVIEIA...
-1.638 YDMSMLEJGHRQPJYCIDIZJXMSLGTZGUGSULTHCCLXDLSFSHVPOE...
-1.621 DPCQQCTKUBEMEIRDRCEPUEHYZPLJPPHADYKMMUBCHMRMLYEOOM...
import numpy as np
import matplotlib.pyplot as plt
# Score many samples to show the distribution
rng = np.random.default_rng(123)
# Generate English-like samples by sliding windows over the corpus
english_scores = []
corpus_upper = clean_text_upper(SAMPLE_CORPUS)
window = 60
for i in range(0, len(corpus_upper) - window, window // 2):
chunk = corpus_upper[i:i+window]
english_scores.append(fitness.score_per_ngram(chunk))
# Generate random text samples
random_scores = []
for _ in range(len(english_scores)):
letters = [chr(ord('A') + rng.integers(0, 26)) for _ in range(window)]
random_scores.append(fitness.score_per_ngram(''.join(letters)))
fig, ax = plt.subplots(figsize=(10, 5))
bins = np.linspace(min(random_scores) - 0.3, max(english_scores) + 0.3, 50)
ax.hist(english_scores, bins=bins, alpha=0.7, color='#2E86C1', label='English text',
edgecolor='white', density=True)
ax.hist(random_scores, bins=bins, alpha=0.7, color='#E74C3C', label='Random text',
edgecolor='white', density=True)
ax.axvline(np.mean(english_scores), color='#1A5276', linestyle='--', linewidth=2,
label=f'English mean: {np.mean(english_scores):.2f}')
ax.axvline(np.mean(random_scores), color='#922B21', linestyle='--', linewidth=2,
label=f'Random mean: {np.mean(random_scores):.2f}')
ax.set_xlabel('Combined fitness score (weighted log-probability per n-gram)', fontsize=12)
ax.set_ylabel('Density', fontsize=12)
ax.set_title('N-gram Fitness: English Text vs. Random Text', fontsize=13)
ax.legend(fontsize=10)
ax.grid(alpha=0.3)
plt.tight_layout()
fig.savefig('fig_ch08_fitness_separation.png', dpi=150, bbox_inches='tight')
plt.show()
print("Figure saved: fig_ch08_fitness_separation.png")
print(f"\nEnglish text: mean = {np.mean(english_scores):.3f}, std = {np.std(english_scores):.3f}")
print(f"Random text: mean = {np.mean(random_scores):.3f}, std = {np.std(random_scores):.3f}")
print(f"Separation: {np.mean(english_scores) - np.mean(random_scores):.3f} log-units")
Figure saved: fig_ch08_fitness_separation.png
English text: mean = -0.990, std = 0.035
Random text: mean = -1.710, std = 0.046
Separation: 0.720 log-units
Observation
The histogram shows a clear separation between English and random text in the combined n-gram fitness score. English text clusters at significantly higher scores than random letter sequences, with minimal overlap between the two distributions.
By combining bigram, trigram, and quadgram scorers with appropriate weights, we get a fitness function that is both discriminating (clear separation) and smooth (small grid changes produce small score changes). The bigram component provides reliable baseline discrimination thanks to near-complete coverage from our corpus, while the trigram and quadgram components add sensitivity to longer linguistic patterns.
In production systems with million-character corpora, pure quadgram scoring is preferred because it captures the most context per n-gram. With our inline corpus, the combined approach achieves similar effectiveness.
Experiment 6: Simulated Annealing Attack on Playfair#
The hill-climbing attack in Experiment 4 is greedy: it never accepts a worse solution. This means it can get trapped in local optima – grid configurations that are better than all their immediate neighbours but far from the true solution.
Simulated annealing (SA) addresses this by borrowing an idea from metallurgy. Just as slowly cooling a metal allows its atoms to find a low-energy crystalline structure, SA starts with a high “temperature” that allows free exploration (accepting worse solutions with high probability) and gradually cools, causing the algorithm to converge. The acceptance rule is:
where \(\Delta F = \text{score}(\text{child}) - \text{score}(\text{parent})\) and \(T\) is the current temperature. The temperature follows a geometric cooling schedule: \(T_{n+1} = \alpha \cdot T_n\) with \(\alpha \approx 0.997\).
Key parameters:
Starting temperature (\(T_0\)): High enough that most mutations are initially accepted (exploration phase).
Final temperature (\(T_{\text{end}}\)): Low enough that the algorithm behaves like pure hill-climbing (exploitation phase).
Cooling rate (\(\alpha\)): Controls the speed of transition between exploration and exploitation.
Restarts: Running multiple independent SA chains improves the chance of finding the global optimum.
Performance note
This implementation is written in pure Python for clarity. On typical hardware, a single SA run with the parameters below takes 10–30 seconds. Production implementations use C/C++ or vectorised operations for 100x speedups.
import numpy as np
import math
import copy
# We need a helper to decrypt with a grid (list of lists) directly,
# rather than a keyword string. This avoids rebuilding the grid each time.
def decrypt_with_grid(ciphertext, grid):
"""Decrypt ciphertext using a Playfair grid (5x5 list of lists).
This is an optimised version for use in iterative attacks where
we manipulate the grid directly rather than using a keyword.
"""
# Build position lookup
positions = {}
for i in range(5):
for j in range(5):
positions[grid[i][j]] = (i, j)
text = ciphertext.upper().replace('J', 'I')
text = ''.join(c for c in text if c.isalpha())
result = []
for k in range(0, len(text) - 1, 2):
a, b = text[k], text[k + 1]
if a not in positions or b not in positions:
result.extend([a, b])
continue
r1, c1 = positions[a]
r2, c2 = positions[b]
if r1 == r2: # Same row: shift left
result.append(grid[r1][(c1 - 1) % 5])
result.append(grid[r2][(c2 - 1) % 5])
elif c1 == c2: # Same column: shift up
result.append(grid[(r1 - 1) % 5][c1])
result.append(grid[(r2 - 1) % 5][c2])
else: # Rectangle: swap columns
result.append(grid[r1][c2])
result.append(grid[r2][c1])
return ''.join(result)
def mutate_grid(flat, rng):
"""Apply a random mutation to a flat (25-element) grid representation.
Uses multiple mutation types for better exploration:
- Swap two random letters (most common, for fine-tuning)
- Swap two rows
- Swap two columns
- Reverse a random section
"""
new_flat = flat[:]
r = rng.random()
if r < 0.5:
# Swap two random letters (most common mutation)
i, j = rng.choice(25, size=2, replace=False)
new_flat[i], new_flat[j] = new_flat[j], new_flat[i]
elif r < 0.7:
# Swap two rows
r1, r2 = rng.choice(5, size=2, replace=False)
for c in range(5):
new_flat[r1*5+c], new_flat[r2*5+c] = new_flat[r2*5+c], new_flat[r1*5+c]
elif r < 0.9:
# Swap two columns
c1, c2 = rng.choice(5, size=2, replace=False)
for r in range(5):
new_flat[r*5+c1], new_flat[r*5+c2] = new_flat[r*5+c2], new_flat[r*5+c1]
else:
# Reverse a random section
i = rng.integers(0, 20)
j = rng.integers(i + 2, min(i + 8, 25))
new_flat[i:j+1] = new_flat[i:j+1][::-1]
return new_flat
def simulated_annealing_playfair(ciphertext, fitness, n_restarts=5,
temp_start=20.0, temp_end=0.1,
cooling=0.997, steps_per_temp=50,
seed=42):
"""Simulated annealing attack on the Playfair cipher.
Parameters
----------
ciphertext : str
The ciphertext to attack.
fitness : object
Fitness scorer with a .score(text) method.
n_restarts : int
Number of independent SA chains to run.
temp_start : float
Initial temperature.
temp_end : float
Final temperature (SA stops when T < temp_end).
cooling : float
Geometric cooling factor (T *= cooling each outer step).
steps_per_temp : int
Number of mutations to try at each temperature level.
seed : int
Random seed for reproducibility.
Returns
-------
best_key : list of lists
The best 5x5 grid found.
best_score : float
The fitness score of the best decryption.
best_text : str
The decrypted text using the best key.
all_histories : list of lists
Score history for each restart (for plotting).
"""
PF_ALPHA = list('ABCDEFGHIKLMNOPQRSTUVWXYZ')
rng = np.random.default_rng(seed)
best_score = float('-inf')
best_key = None
best_text = None
all_histories = []
for restart in range(n_restarts):
# Start from a random grid
letters = PF_ALPHA[:]
rng.shuffle(letters)
parent_flat = letters[:]
parent_grid = [parent_flat[i*5:(i+1)*5] for i in range(5)]
parent_text = decrypt_with_grid(ciphertext, parent_grid)
parent_score = fitness.score(parent_text)
local_best_score = parent_score
local_best_flat = parent_flat[:]
history = [parent_score]
temp = temp_start
iteration = 0
while temp > temp_end:
for _ in range(steps_per_temp):
# Mutate the grid
child_flat = mutate_grid(parent_flat, rng)
child_grid = [child_flat[i*5:(i+1)*5] for i in range(5)]
child_text = decrypt_with_grid(ciphertext, child_grid)
child_score = fitness.score(child_text)
delta = child_score - parent_score
# Boltzmann acceptance criterion
if delta > 0 or rng.random() < math.exp(delta / temp):
parent_flat = child_flat
parent_score = child_score
parent_text = child_text
if parent_score > local_best_score:
local_best_score = parent_score
local_best_flat = parent_flat[:]
iteration += 1
# Record best-so-far score periodically
if iteration % 500 == 0:
history.append(local_best_score)
temp *= cooling
all_histories.append(history)
if local_best_score > best_score:
best_score = local_best_score
best_key = [local_best_flat[i*5:(i+1)*5] for i in range(5)]
best_text = decrypt_with_grid(ciphertext, best_key)
print(f" Restart {restart + 1}/{n_restarts}: "
f"best score = {local_best_score:.2f}, "
f"iterations = {iteration}")
return best_key, best_score, best_text, all_histories
# --- Prepare a Playfair ciphertext for the SA attack ---
# Encrypt a substantial plaintext with a known key
pf_sa = PlayfairCipher("WHEATSTONE")
plaintext_sa = (
"THE PLAYFAIR CIPHER ENCRYPTS PAIRS OF LETTERS INSTEAD OF SINGLE LETTERS "
"THIS MAKES IT SIGNIFICANTLY HARDER TO BREAK USING SIMPLE FREQUENCY ANALYSIS "
"THE CIPHER WAS USED BY BRITISH FORCES DURING THE BOER WAR AND BOTH WORLD WARS "
"IT REQUIRED NO SPECIAL EQUIPMENT AND COULD BE MEMORISED BY FIELD AGENTS"
)
ciphertext_sa = pf_sa.encrypt(plaintext_sa)
clean_pt = plaintext_sa.upper().replace('J', 'I')
clean_pt = ''.join(c for c in clean_pt if c.isalpha())
print(f"Plaintext length: {len(clean_pt)} characters")
print(f"Ciphertext length: {len(ciphertext_sa)} characters")
print(f"Ciphertext: {ciphertext_sa[:80]}...")
print()
# --- Run the simulated annealing attack ---
print("Running simulated annealing attack (this may take 20-60 seconds)...")
sa_key, sa_score, sa_text, sa_histories = simulated_annealing_playfair(
ciphertext_sa, fitness,
n_restarts=5,
temp_start=20.0,
temp_end=0.1,
cooling=0.997,
steps_per_temp=50,
seed=42
)
print(f"\n--- Results ---")
print(f"Best fitness score: {sa_score:.2f}")
print(f"\nRecovered grid:")
for row in sa_key:
print(" " + " ".join(row))
print(f"\nTrue grid (keyword = WHEATSTONE):")
pf_sa.display_grid()
print(f"\nRecovered text (first 150 chars):")
print(f" {sa_text[:150]}")
print(f"\nOriginal plaintext (first 150 chars):")
print(f" {clean_pt[:150]}")
# Check character-level accuracy
matches = sum(1 for a, b in zip(sa_text, clean_pt) if a == b)
accuracy = matches / len(clean_pt) * 100
print(f"\nCharacter accuracy: {matches}/{len(clean_pt)} = {accuracy:.1f}%")
Plaintext length: 249 characters
Ciphertext length: 250 characters
Ciphertext: WENXQWVIBQZKGQEAPTBSQZRENLBQLCFMPWEZWALCGBCWATFSDOGBDPWPAWWALCWEDBQHGTBDWCKIBGGK...
Running simulated annealing attack (this may take 20-60 seconds)...
Restart 1/5: best score = -1057.38, iterations = 88200
Restart 2/5: best score = -1079.07, iterations = 88200
Restart 3/5: best score = -794.76, iterations = 88200
Restart 4/5: best score = -1075.76, iterations = 88200
Restart 5/5: best score = -1067.07, iterations = 88200
--- Results ---
Best fitness score: -794.76
Recovered grid:
F G I K D
M P Q R L
V X Y Z U
H E A T W
O N B C S
True grid (keyword = WHEATSTONE):
W H E A T
S O N B C
D F G I K
L M P Q R
U V X Y Z
Recovered text (first 150 chars):
THEPLAYFAIRCIPHERENCRYPTSPAIRSOFLETXTERSINSTEADOFSINGLELETTERSTHISMAKESITSIGNIFICANTLYHARDERTOBREAKUSINGSIMPLEFREQUENCYANALYSISTHECIPHERWASUSEDBYBRITI
Original plaintext (first 150 chars):
THEPLAYFAIRCIPHERENCRYPTSPAIRSOFLETTERSINSTEADOFSINGLELETTERSTHISMAKESITSIGNIFICANTLYHARDERTOBREAKUSINGSIMPLEFREQUENCYANALYSISTHECIPHERWASUSEDBYBRITIS
Character accuracy: 36/249 = 14.5%
import numpy as np
import matplotlib.pyplot as plt
# Plot SA convergence alongside the hill-climbing results for comparison
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
# Left panel: SA convergence (best-so-far score over iterations)
ax1 = axes[0]
sa_colors = plt.cm.Set2(np.linspace(0, 1, len(sa_histories)))
for idx, history in enumerate(sa_histories):
x_vals = np.arange(len(history)) * 500
ax1.plot(x_vals, history, color=sa_colors[idx],
linewidth=1.2, alpha=0.8, label=f'SA restart {idx + 1}')
ax1.set_xlabel('Iteration (approx.)', fontsize=12)
ax1.set_ylabel('Best fitness score', fontsize=12)
ax1.set_title('Simulated Annealing: Score Convergence', fontsize=13)
ax1.legend(fontsize=9)
ax1.grid(alpha=0.3)
# Right panel: Compare final scores of HC vs SA
ax2 = axes[1]
hc_final_scores = [h[-1] for h in histories] # from Experiment 4
sa_final_scores = [h[-1] for h in sa_histories]
positions = [1, 2]
bp = ax2.boxplot([hc_final_scores, sa_final_scores], positions=positions,
widths=0.5, patch_artist=True)
bp['boxes'][0].set_facecolor('#3498DB')
bp['boxes'][1].set_facecolor('#E74C3C')
bp['boxes'][0].set_alpha(0.7)
bp['boxes'][1].set_alpha(0.7)
# Overlay individual points
for i, (scores, pos) in enumerate(zip([hc_final_scores, sa_final_scores], positions)):
jitter_rng = np.random.default_rng(42)
jitter = jitter_rng.uniform(-0.1, 0.1, len(scores))
color = '#1A5276' if i == 0 else '#922B21'
ax2.scatter([pos + j for j in jitter], scores, color=color, s=40, alpha=0.8, zorder=3)
ax2.set_xticks(positions)
ax2.set_xticklabels(['Hill-Climbing\n(Exp. 4)', 'Simulated\nAnnealing (Exp. 6)'], fontsize=11)
ax2.set_ylabel('Final fitness score', fontsize=12)
ax2.set_title('Hill-Climbing vs. Simulated Annealing', fontsize=13)
ax2.grid(axis='y', alpha=0.3)
plt.tight_layout()
fig.savefig('fig_ch08_sa_convergence.png', dpi=150, bbox_inches='tight')
plt.show()
print("Figure saved: fig_ch08_sa_convergence.png")
Figure saved: fig_ch08_sa_convergence.png
Observation
The simulated annealing attack demonstrates several key features:
Score convergence: Each SA restart shows rapid initial improvement followed by gradual refinement. The early phase (high temperature) explores broadly, while the later phase (low temperature) fine-tunes.
Restart variability: Different random starting grids converge to different local optima, which is why multiple restarts are essential. The best restart typically achieves a noticeably higher score.
Comparison with hill-climbing: The SA restarts generally achieve comparable or higher fitness scores than the hill-climbing restarts from Experiment 4, demonstrating the benefit of probabilistic acceptance of worse solutions.
Important caveats: With our modest inline corpus (~10,000 characters), the n-gram tables have limited coverage. Production Playfair crackers use corpora of millions of characters, which provide far denser n-gram tables and enable reliable recovery of 200+ character ciphertexts. The character-level accuracy reported above reflects this limitation – with a larger corpus, simulated annealing can achieve near-perfect recovery. The key takeaway is the method: SA with n-gram scoring provides a principled, general framework for attacking polygraphic ciphers.
Experiment 7 (Bonus): Comparing Playfair Key Space with Monoalphabetic Substitution#
We compare the theoretical key spaces of monoalphabetic substitution and the Playfair cipher, and visualise how the effective key space of Playfair is affected by keyword-based construction.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
from math import factorial, log10
# Key space comparison
# Monoalphabetic: 26! permutations
mono_keyspace = factorial(26)
mono_log = log10(mono_keyspace)
# Playfair: 25! grid arrangements
playfair_total = factorial(25)
playfair_log = log10(playfair_total)
print("KEY SPACE COMPARISON")
print("=" * 50)
print(f"Monoalphabetic substitution: 26! = {mono_keyspace:.4e}")
print(f" log10 = {float(mono_log):.1f} (approximately {float(mono_log):.0f} digits)")
print()
print(f"Playfair (all grids): 25! = {playfair_total:.4e}")
print(f" log10 = {float(playfair_log):.1f} (approximately {float(playfair_log):.0f} digits)")
print()
# Keyword-based Playfair grids
print("Keyword-based Playfair grids (keyword length k):")
print(f"{'k':>3s} {'Distinct grids':>20s} {'log10':>8s}")
print("-" * 36)
for k in range(1, 16):
# Number of ways to choose k distinct letters from 25 in order
# = P(25, k) = 25! / (25-k)!
n_grids = factorial(25) // factorial(25 - k)
print(f"{int(k):>3d} {n_grids:>20.4e} {float(log10(n_grids)):>8.1f}")
# Visualisation
fig, ax = plt.subplots(figsize=(10, 5))
categories = ['Caesar\n(shift)', 'Keyword\n(len 5)', 'Keyword\n(len 10)',
'Keyword\n(len 15)', 'Playfair\n(all grids)',
'Monoalphabetic\n(26!)']
log_sizes = [
log10(26),
log10(factorial(25) // factorial(20)),
log10(factorial(25) // factorial(15)),
log10(factorial(25) // factorial(10)),
playfair_log,
mono_log
]
bar_colors = ['#3498DB', '#2ECC71', '#2ECC71', '#2ECC71', '#E74C3C', '#9B59B6']
bars = ax.bar(categories, log_sizes, color=bar_colors, edgecolor='#2C3E50',
alpha=0.85, width=0.6)
# Add value labels on bars
for bar, val in zip(bars, log_sizes):
ax.text(bar.get_x() + bar.get_width() / 2, bar.get_height() + 0.3,
f'{float(val):.1f}', ha='center', va='bottom', fontsize=10,
fontweight='bold')
ax.set_ylabel(r'$\log_{10}$(key space size)', fontsize=12)
ax.set_title('Key Space Sizes: Playfair vs. Monoalphabetic Substitution',
fontsize=13)
ax.grid(axis='y', alpha=0.3)
ax.set_ylim(0, max(log_sizes) + 3)
plt.tight_layout()
fig.savefig('fig_ch08_key_space.png', dpi=150, bbox_inches='tight')
plt.show()
print("Figure saved: fig_ch08_key_space.png")
KEY SPACE COMPARISON
==================================================
Monoalphabetic substitution: 26! = 4.0329e+26
log10 = 26.6 (approximately 27 digits)
Playfair (all grids): 25! = 1.5511e+25
log10 = 25.2 (approximately 25 digits)
Keyword-based Playfair grids (keyword length k):
k Distinct grids log10
------------------------------------
1 2.5000e+01 1.4
2 6.0000e+02 2.8
3 1.3800e+04 4.1
4 3.0360e+05 5.5
5 6.3756e+06 6.8
6 1.2751e+08 8.1
7 2.4227e+09 9.4
8 4.3609e+10 10.6
9 7.4135e+11 11.9
10 1.1862e+13 13.1
11 1.7793e+14 14.3
12 2.4910e+15 15.4
13 3.2382e+16 16.5
14 3.8859e+17 17.6
15 4.2745e+18 18.6
Figure saved: fig_ch08_key_space.png
Observation
Despite having a slightly smaller total key space than monoalphabetic substitution (\(25! \approx 1.55 \times 10^{25}\) vs. \(26! \approx 4.03 \times 10^{26}\)), the Playfair cipher is significantly harder to break by simple frequency analysis because it operates on digrams rather than individual letters. However, the keyword-based construction dramatically reduces the effective key space: a keyword of length 5 yields only about \(6 \times 10^6\) distinct grids. In practice, the keyword length and dictionary constraints make the effective key space much smaller than the theoretical maximum.
Exercises#
Exercise 8.1: Grid construction
Construct the Playfair grid for the keyword QUEENSLAND. Write out the full 5\(\times\)5 grid and verify that it contains exactly 25 distinct letters (with I/J merged).
Hint
First remove duplicate letters from the keyword: Q, U, E, N, S, L, A, D (the second N is dropped). Then fill in the remaining 17 letters in alphabetical order: B, C, F, G, H, I, K, M, O, P, R, T, V, W, X, Y, Z.
Exercise 8.2: Encryption by hand
Using the grid from the keyword MONARCHY, encrypt the plaintext HIDE THE GOLD IN THE TREE STUMP. Show each digram, the rule applied, and the resulting ciphertext digram.
Hint
First prepare the digrams: HI, DE, TH, EG, OL, DI, NT, HE, TR, EX, ES, TU, MP. Note the X inserted after TRE to prevent the final E from being alone. Then apply the three rules to each pair using the MONARCHY grid.
Exercise 8.3: Proving the rectangle rule is self-inverse
Prove that the rectangle rule of the Playfair cipher is its own inverse. That is, if \(E(a, b) = (a', b')\) under the rectangle rule, then \(E(a', b') = (a, b)\).
Hint
Under the rectangle rule, \(a' = G[r_a, c_b]\) and \(b' = G[r_b, c_a]\). So \(a'\) is in row \(r_a\) and column \(c_b\), and \(b'\) is in row \(r_b\) and column \(c_a\). Since \(r_a \neq r_b\) and \(c_a \neq c_b\) (otherwise a different rule would apply), the pair \((a', b')\) also forms a rectangle. Applying the rectangle rule: \(E(a') = G[r_a, c_a] = a\) and \(E(b') = G[r_b, c_b] = b\).
Exercise 8.4: Digram frequency analysis
Encrypt a paragraph of English text (at least 200 characters) using the Playfair cipher with keyword ZEBRAS. Then:
(a) Count the 10 most frequent ciphertext digrams.
(b) Hypothesize which plaintext digrams they correspond to (using the table of common English digrams from Section 8.4.2).
(c) Verify your hypotheses by decrypting those digrams.
Hint
The most frequent ciphertext digram likely corresponds to TH or HE. Build the ZEBRAS grid, find which ciphertext digram maps to TH, and check if it matches the most frequent one you observed. Remember that the Playfair cipher is a permutation on digrams, so digram frequency patterns are partially preserved.
Exercise 8.5: Improving the simulated annealing attack
The simulated annealing attack in Experiment 6 uses a single mutation type (swap two random grid cells). Improve it by implementing one or more of the following:
(a) More mutation types: Add mutations that swap two rows, swap two columns, rotate a row, rotate a column, or reverse a section of the grid. Choose a mutation type at random each step.
(b) Adaptive cooling schedule: Instead of a fixed geometric cooling rate, try a schedule that slows down when improvements are found and speeds up when the algorithm is stuck.
(c) Ciphertext length study: Test the SA attack on ciphertexts of different lengths (50, 100, 200, 500 characters) and plot the success rate (fraction of characters correctly recovered) as a function of ciphertext length.
(d) Larger corpus: Expand the inline corpus with additional public-domain text (e.g., more passages from Dickens, Melville, or other authors) and measure how the quadgram table size and attack accuracy improve.
Hint
For part (a), production Playfair crackers typically use 5–6 mutation types with equal probability. Row and column swaps are “large” mutations that help escape local optima, while single-cell swaps are “small” mutations that refine the solution. For part (c), you should expect near-perfect recovery for 300+ characters, partial recovery for 150–300 characters, and poor results below 100 characters.
Summary#
In this chapter we studied the Playfair cipher, the first practical digraphic cipher to see widespread military use.
Key concepts:
Playfair grid: A 5\(\times\)5 matrix constructed from a keyword, containing 25 letters (I and J merged). The keyword letters fill the grid first, followed by the remaining alphabet letters.
Digram preparation: Plaintext is split into letter pairs, with X inserted between repeated letters and as padding for odd-length texts.
Three encryption rules: Same row (shift right), same column (shift down), rectangle (swap columns). Decryption reverses these operations.
Digram permutation (Theorem 8.1): The Playfair cipher is a fixed permutation on the 600-element space of ordered digrams \((a, b)\) with \(a \neq b\). This means the substitution structure creates characteristic digram frequency signatures that can be exploited by cryptanalysis.
Digram frequency analysis: Because the permutation is fixed, the substitution structure partially preserves certain digram frequency patterns in the ciphertext. The most frequent ciphertext digrams correspond to the most frequent English digrams (TH, HE, IN, ER, AN, …).
Hill-climbing and simulated annealing attacks: Modern computational attacks use random grid perturbations guided by a fitness function (quadgram log-probabilities) to recover the key grid. Simulated annealing improves on pure hill-climbing by accepting worse solutions with a temperature-dependent probability, enabling escape from local optima. Multiple restarts further improve reliability.
Key space: The total number of Playfair grids is \(25! \approx 1.55 \times 10^{25}\), but keyword-based construction and statistical attacks reduce the effective security far below this theoretical maximum.
The Playfair cipher represents an important step in the evolution of cryptography: the transition from monographic (single-letter) to polygraphic (multi-letter) systems. Our experiments demonstrated both the construction and cryptanalysis of this cipher, culminating in a simulated annealing attack that can recover the plaintext from ciphertext alone. In the next chapter, we will see how this idea can be generalised using linear algebra in the Hill cipher.
References#
Wheatstone, C. (1854). On the Reading of Cipher Despatches. Manuscript submitted to the British Foreign Office. – The original description of the cipher, unpublished during Wheatstone’s lifetime.
Friedman, W. F. (1925). Several Machine Ciphers and Methods for their Solution. Riverbank Publication No. 20. – Contains early analysis of the Playfair cipher and related systems.
Sinkov, A. (1966). Elementary Cryptanalysis: A Mathematical Approach. Mathematical Association of America. [4] – Chapter 7 provides a textbook introduction to the Playfair cipher and digram analysis.
Bauer, F. L. (2007). Decrypted Secrets: Methods and Maxims of Cryptology. 4th edition, Springer. [5] – Section 3.4 covers the Playfair cipher and its military history in detail.
Singh, S. (1999). The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Doubleday. [3] – Chapter 2 tells the entertaining story of Wheatstone, Playfair, and Lord Palmerston.
Kahn, D. (1996). The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. Revised edition, Scribner. – Chapter 7 provides extensive historical context on the Playfair cipher in military communications.