Chapter 7: The Hill Cipher#
7.1 Introduction: Linear Algebra Enters Cryptography#
In 1929, the American mathematician Lester S. Hill (1891–1961) published a remarkable paper in The American Mathematical Monthly titled “Cryptography in an Algebraic Alphabet.” For the first time in the history of cryptography, a cipher was designed using the full power of linear algebra — specifically, matrix multiplication over modular arithmetic.
“The problem of substitution-encipherment … leads naturally to the consideration of sets of linear substitutions in a modular arithmetic.” — Lester S. Hill, “Cryptography in an Algebraic Alphabet,” 1929
Unlike all previous ciphers, which operated on individual letters or at most pairs, the Hill cipher encrypts blocks of \(n\) letters simultaneously by treating them as vectors in \(\mathbb{Z}_{26}^n\) and multiplying by an invertible \(n \times n\) key matrix. This makes it the first polygraphic cipher based on linear transformations, and the first to completely destroy single-letter frequency statistics.
Hill even obtained a US patent (US1845947) for his invention in 1932. Though the cipher was never widely adopted for military use — it is vulnerable to known-plaintext attacks via simple linear algebra — the Hill cipher remains pedagogically important. It demonstrates both the power and the limitations of linearity in cryptography, foreshadowing the modern principle that nonlinearity (S-boxes) is essential for security.
Tip
The Hill cipher teaches a crucial lesson: algebraic structure that makes a cipher elegant also makes it breakable. The linearity that allows efficient encryption also allows efficient cryptanalysis. This tension between structure and security is a recurring theme throughout modern cryptography.
7.2 Formal Definitions#
Definition 7.1 (Hill Cipher)
Let \(n \geq 1\) be the block size and let \(K\) be an invertible \(n \times n\) matrix over \(\mathbb{Z}_{26}\). The Hill cipher encrypts a plaintext block \(\mathbf{m} = (m_1, \ldots, m_n)^T \in \mathbb{Z}_{26}^n\) as:
Decryption is performed using the modular inverse:
Each letter is mapped to an integer: \(a \mapsto 0, b \mapsto 1, \ldots, z \mapsto 25\).
Definition 7.2 (Invertibility over \(\mathbb{Z}_{26}\))
A matrix \(K\) is invertible modulo 26 if and only if
Since \(26 = 2 \times 13\), the determinant must be coprime to both 2 and 13. Equivalently, \(\det(K) \pmod{26}\) must be one of \(\{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25\}\) — there are 12 valid values out of 26.
Definition 7.3 (Modular Matrix Inverse)
The inverse \(K^{-1} \pmod{26}\) is computed as:
where \(\text{adj}(K)\) is the adjugate (transpose of the cofactor matrix) and \((\det K)^{-1}\) is the modular multiplicative inverse of \(\det(K)\) modulo 26, computed via the extended Euclidean algorithm.
Definition 7.4 (Known-Plaintext Attack)
Given \(n\) known plaintext-ciphertext block pairs \((\mathbf{m}_i, \mathbf{c}_i)\), form the matrices \(M = [\mathbf{m}_1 | \cdots | \mathbf{m}_n]\) and \(C = [\mathbf{c}_1 | \cdots | \mathbf{c}_n]\). If \(M\) is invertible mod 26, the key is recovered as:
Danger
The Hill cipher is completely broken by a known-plaintext attack.
An attacker who knows just \(n\) plaintext-ciphertext pairs (e.g., \(n = 2\) for a \(2 \times 2\) key) can recover the entire key matrix in polynomial time. This makes the Hill cipher unsuitable for any practical security application. Its vulnerability arises from the linearity of the encryption function.
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
class HillCipher:
"""
Hill cipher: polygraphic substitution using matrix multiplication mod 26.
Parameters
----------
key_matrix : array-like
An n x n invertible matrix over Z_26.
"""
def __init__(self, key_matrix):
self.key = np.array(key_matrix, dtype=int) % 26
self.n = self.key.shape[0]
assert self.key.shape == (self.n, self.n), "Key must be square"
det = self._mod_det(self.key, 26)
if np.gcd(det, 26) != 1:
raise ValueError(f"Key not invertible mod 26 (det={det})")
self.key_inv = self._mod_matrix_inverse(self.key, 26)
@staticmethod
def _extended_gcd(a, b):
"""Extended Euclidean algorithm."""
if a == 0:
return b, 0, 1
gcd, x1, y1 = HillCipher._extended_gcd(b % a, a)
return gcd, y1 - (b // a) * x1, x1
@staticmethod
def _mod_inverse(a, m):
"""Modular multiplicative inverse of a mod m."""
a = a % m
gcd, x, _ = HillCipher._extended_gcd(a, m)
if gcd != 1:
raise ValueError(f"No inverse for {a} mod {m}")
return x % m
@staticmethod
def _mod_det(matrix, mod):
"""Compute determinant mod m using integer arithmetic."""
n = matrix.shape[0]
if n == 1:
return int(matrix[0, 0]) % mod
if n == 2:
return int(matrix[0, 0] * matrix[1, 1] - matrix[0, 1] * matrix[1, 0]) % mod
det = 0
for j in range(n):
minor = np.delete(np.delete(matrix, 0, axis=0), j, axis=1)
cofactor = ((-1) ** j) * int(matrix[0, j]) * HillCipher._mod_det(minor, mod)
det = (det + cofactor) % mod
return det % mod
@staticmethod
def _mod_matrix_inverse(matrix, mod=26):
"""Compute the modular inverse of a matrix."""
n = matrix.shape[0]
det = HillCipher._mod_det(matrix, mod)
det_inv = HillCipher._mod_inverse(det, mod)
# Compute cofactor matrix
cofactors = np.zeros((n, n), dtype=int)
for i in range(n):
for j in range(n):
minor = np.delete(np.delete(matrix, i, axis=0), j, axis=1)
cofactors[i, j] = ((-1) ** (i + j)) * HillCipher._mod_det(minor, mod)
adjugate = cofactors.T % mod
return (det_inv * adjugate) % mod
def _text_to_blocks(self, text):
"""Convert text to blocks of n integers."""
text = ''.join(c.lower() for c in text if c.isalpha())
indices = [ord(c) - ord('a') for c in text]
while len(indices) % self.n != 0:
indices.append(ord('x') - ord('a')) # pad with 'x'
return np.array(indices, dtype=int).reshape(-1, self.n)
def _blocks_to_text(self, blocks):
"""Convert blocks back to text."""
return ''.join(chr(int(v) % 26 + ord('a')) for row in blocks for v in row)
def encrypt(self, plaintext):
"""Encrypt plaintext using the Hill cipher."""
blocks = self._text_to_blocks(plaintext)
encrypted = np.array([(self.key @ b) % 26 for b in blocks])
return self._blocks_to_text(encrypted)
def decrypt(self, ciphertext):
"""Decrypt ciphertext using the Hill cipher."""
blocks = self._text_to_blocks(ciphertext)
decrypted = np.array([(self.key_inv @ b) % 26 for b in blocks])
return self._blocks_to_text(decrypted)
def __repr__(self):
det = self._mod_det(self.key, 26)
return f"HillCipher(n={self.n}, det={det})"
# --- Demo ---
K = np.array([[6, 24, 1], [13, 16, 10], [20, 17, 15]])
cipher = HillCipher(K)
print(f"Cipher: {cipher}")
print(f"Key matrix:\n{cipher.key}")
print(f"Inverse matrix:\n{cipher.key_inv}")
pt = "actfast"
ct = cipher.encrypt(pt)
dt = cipher.decrypt(ct)
print(f"\nPlaintext: {pt}")
print(f"Encrypted: {ct}")
print(f"Decrypted: {dt}")
print(f"Correct: {dt.startswith(pt)}")
Cipher: HillCipher(n=3, det=25)
Key matrix:
[[ 6 24 1]
[13 16 10]
[20 17 15]]
Inverse matrix:
[[ 8 5 10]
[21 8 21]
[21 12 8]]
Plaintext: actfast
Encrypted: pohwlgnny
Decrypted: actfastxx
Correct: True
7.3 Key Results#
Theorem 7.1 (General Linear Group)
The set of all invertible \(n \times n\) matrices over \(\mathbb{Z}_{26}\) forms a group under matrix multiplication modulo 26, denoted \(\mathrm{GL}(n, \mathbb{Z}_{26})\). The number of valid Hill cipher keys of block size \(n\) is \(|\mathrm{GL}(n, \mathbb{Z}_{26})|\).
Proof sketch
Closure: If \(A, B\) are invertible mod 26, then \(\det(AB) = \det(A)\det(B)\), which is coprime to 26 since the product of units in \(\mathbb{Z}_{26}\) is a unit. Identity: \(I_n\). Inverses exist by the adjugate formula. Associativity follows from matrix multiplication. \(\blacksquare\)
Theorem 7.2 (Known-Plaintext Key Recovery)
Given \(n\) known plaintext-ciphertext block pairs \((\mathbf{m}_i, \mathbf{c}_i)\) for \(i = 1, \ldots, n\), where \(M = [\mathbf{m}_1 | \cdots | \mathbf{m}_n]\) is invertible mod 26, the key is uniquely determined:
Proof
Since \(\mathbf{c}_i = K \cdot \mathbf{m}_i\) for each \(i\), we have \(C = K \cdot M\). Multiplying both sides on the right by \(M^{-1}\) gives \(K = C \cdot M^{-1}\). \(\blacksquare\)
Observation 7.3 (Frequency Analysis Resistance)
The Hill cipher with block size \(n \geq 2\) destroys the single-letter frequency distribution of plaintext. The index of coincidence of Hill-encrypted text approaches \(\kappa_r = 1/26 \approx 0.0385\) (the random baseline). This flattening is observed for typical keys but is not guaranteed for all invertible Hill cipher keys.
Experiment 1: Step-by-Step 2×2 Encryption#
Let us trace the encryption of “help” using a \(2 \times 2\) key matrix.
import numpy as np
import matplotlib.pyplot as plt
# 2x2 Hill cipher step-by-step
K2 = np.array([[3, 3], [2, 5]])
cipher2 = HillCipher(K2)
print(f"Key K = \n{K2}")
print(f"det(K) mod 26 = {HillCipher._mod_det(K2, 26)}")
print(f"K^(-1) mod 26 = \n{cipher2.key_inv}")
print()
# Encrypt "help" = [7, 4, 11, 15]
plaintext = "help"
blocks = cipher2._text_to_blocks(plaintext)
print(f"Plaintext: '{plaintext}'")
print(f"As numbers: {[ord(c)-ord('a') for c in plaintext]}")
print(f"Blocks: {blocks.tolist()}")
print()
for i, block in enumerate(blocks):
result = (K2 @ block) % 26
letters_in = ''.join(chr(v + ord('a')) for v in block)
letters_out = ''.join(chr(v + ord('a')) for v in result)
print(f"Block {i+1}: {block} ('{letters_in}')")
print(f" K @ [{block[0]}, {block[1]}]^T = [{K2[0,0]}*{block[0]}+{K2[0,1]}*{block[1]}, {K2[1,0]}*{block[0]}+{K2[1,1]}*{block[1]}] = [{K2[0]@block}, {K2[1]@block}]")
print(f" mod 26 = {result.tolist()} ('{letters_out}')")
print()
ct = cipher2.encrypt(plaintext)
dt = cipher2.decrypt(ct)
print(f"Full encryption: '{plaintext}' -> '{ct}'")
print(f"Full decryption: '{ct}' -> '{dt}'")
Key K =
[[3 3]
[2 5]]
det(K) mod 26 = 9
K^(-1) mod 26 =
[[15 17]
[20 9]]
Plaintext: 'help'
As numbers: [7, 4, 11, 15]
Blocks: [[7, 4], [11, 15]]
Block 1: [7 4] ('he')
K @ [7, 4]^T = [3*7+3*4, 2*7+5*4] = [33, 34]
mod 26 = [7, 8] ('hi')
Block 2: [11 15] ('lp')
K @ [11, 15]^T = [3*11+3*15, 2*11+5*15] = [78, 97]
mod 26 = [0, 19] ('at')
Full encryption: 'help' -> 'hiat'
Full decryption: 'hiat' -> 'help'
Experiment 2: Frequency Analysis Failure#
The Hill cipher completely flattens the letter frequency distribution. Let us compare plaintext and ciphertext frequencies.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
import string
import re
# Generate a long English-like text
sample_text = (
"the quick brown fox jumps over the lazy dog and then the fox runs across "
"the field while the dog chases after it through the tall grass and under "
"the bright blue sky the birds sing their morning songs as the sun rises "
"above the mountains casting long shadows across the valley below where "
"the river flows gently through the ancient forest the trees stand tall "
"and proud their leaves rustling in the gentle breeze that carries the "
"sweet scent of wildflowers from the meadow beyond the old stone bridge "
"that spans the river has stood for centuries a testament to the skill "
"of the builders who constructed it long ago in the village nearby the "
"people go about their daily lives tending to their gardens and caring "
"for their animals the children play in the streets laughing and running "
"while the elders sit on their porches watching the world go by with "
"knowing smiles on their weathered faces the baker opens his shop early "
"each morning filling the air with the warm aroma of fresh bread and "
"pastries that draw the hungry villagers from their homes"
) * 3
def clean_text(text):
return re.sub(r'[^a-z]', '', text.lower())
def compute_freq(text):
cleaned = clean_text(text)
return np.array([cleaned.count(c) / len(cleaned) for c in string.ascii_lowercase])
plaintext_long = clean_text(sample_text)
K2 = np.array([[3, 3], [2, 5]])
hill = HillCipher(K2)
ciphertext_long = hill.encrypt(plaintext_long)
freq_plain = compute_freq(plaintext_long)
freq_cipher = compute_freq(ciphertext_long)
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
letters = list(string.ascii_lowercase)
x = np.arange(26)
axes[0].bar(x, freq_plain, color='steelblue', alpha=0.8)
axes[0].set_xticks(x)
axes[0].set_xticklabels(letters)
axes[0].set_title('Plaintext Letter Frequency', fontsize=13, fontweight='bold')
axes[0].set_ylabel('Frequency')
axes[0].set_ylim(0, 0.15)
axes[1].bar(x, freq_cipher, color='crimson', alpha=0.8)
axes[1].set_xticks(x)
axes[1].set_xticklabels(letters)
axes[1].set_title('Hill Cipher (2×2) Ciphertext Frequency', fontsize=13, fontweight='bold')
axes[1].set_ylabel('Frequency')
axes[1].set_ylim(0, 0.15)
axes[1].axhline(y=1/26, color='gray', linestyle='--', alpha=0.5, label='Random (1/26)')
axes[1].legend()
plt.tight_layout()
plt.savefig('hill_frequency_comparison.png', dpi=150, bbox_inches='tight')
plt.show()
print(f"Plaintext std dev of frequencies: {float(freq_plain.std()):.4f}")
print(f"Ciphertext std dev of frequencies: {float(freq_cipher.std()):.4f}")
print(f"Random baseline std dev: {float(0.0):.4f}")
Plaintext std dev of frequencies: 0.0338
Ciphertext std dev of frequencies: 0.0107
Random baseline std dev: 0.0000
Experiment 3: Index of Coincidence Comparison#
We compute the IoC for plaintext and Hill-encrypted text to confirm the destruction of statistical structure.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
import string
def index_of_coincidence(text):
"""Compute the Index of Coincidence."""
text = ''.join(c for c in text.lower() if c.isalpha())
n = len(text)
if n < 2:
return 0.0
counts = np.array([text.count(c) for c in string.ascii_lowercase])
return np.sum(counts * (counts - 1)) / (n * (n - 1))
# Compute IoC for increasing text lengths
lengths = list(range(50, len(plaintext_long), 50))
ioc_plain = [index_of_coincidence(plaintext_long[:l]) for l in lengths]
ioc_cipher = [index_of_coincidence(ciphertext_long[:l]) for l in lengths]
fig, ax = plt.subplots(figsize=(10, 5))
ax.plot(lengths, ioc_plain, 'b-', linewidth=1.5, label='Plaintext', alpha=0.8)
ax.plot(lengths, ioc_cipher, 'r-', linewidth=1.5, label='Hill ciphertext (2×2)', alpha=0.8)
ax.axhline(y=0.0667, color='blue', linestyle='--', alpha=0.4, label='English expected (0.0667)')
ax.axhline(y=1/26, color='red', linestyle='--', alpha=0.4, label='Random expected (0.0385)')
ax.set_xlabel('Text length (characters)', fontsize=12)
ax.set_ylabel('Index of Coincidence', fontsize=12)
ax.set_title('IoC: Plaintext vs. Hill Cipher Ciphertext', fontsize=13, fontweight='bold')
ax.legend(fontsize=10)
ax.grid(alpha=0.3)
plt.tight_layout()
plt.savefig('hill_ioc_comparison.png', dpi=150, bbox_inches='tight')
plt.show()
print(f"Plaintext IoC (full): {float(index_of_coincidence(plaintext_long)):.4f}")
print(f"Ciphertext IoC (full): {float(index_of_coincidence(ciphertext_long)):.4f}")
print(f"English expected: 0.0667")
print(f"Random expected: {float(1/26):.4f}")
Plaintext IoC (full): 0.0677
Ciphertext IoC (full): 0.0411
English expected: 0.0667
Random expected: 0.0385
Experiment 4: Known-Plaintext Attack#
We demonstrate the devastating simplicity of breaking the Hill cipher with known plaintext.
import numpy as np
import matplotlib.pyplot as plt
def hill_kpa_attack(known_plain_blocks, known_cipher_blocks, mod=26):
"""
Known-plaintext attack on the Hill cipher.
Given n plaintext blocks and their corresponding ciphertext blocks,
recover the n x n key matrix.
"""
M = np.array(known_plain_blocks, dtype=int).T # columns are plaintext blocks
C = np.array(known_cipher_blocks, dtype=int).T # columns are ciphertext blocks
M_inv = HillCipher._mod_matrix_inverse(M, mod)
K_recovered = (C @ M_inv) % mod
return K_recovered
# Set up: encrypt with secret key
secret_key = np.array([[3, 3], [2, 5]])
cipher_secret = HillCipher(secret_key)
# Attacker knows 2 plaintext-ciphertext pairs
plain1 = np.array([7, 4]) # "he"
plain2 = np.array([11, 15]) # "lp"
cipher1 = (secret_key @ plain1) % 26
cipher2 = (secret_key @ plain2) % 26
print("=== Known-Plaintext Attack ===")
print(f"Known pair 1: plaintext 'he' = {plain1} -> ciphertext = {cipher1} = '{chr(cipher1[0]+ord('a'))}{chr(cipher1[1]+ord('a'))}'")
print(f"Known pair 2: plaintext 'lp' = {plain2} -> ciphertext = {cipher2} = '{chr(cipher2[0]+ord('a'))}{chr(cipher2[1]+ord('a'))}'")
print()
K_recovered = hill_kpa_attack([plain1, plain2], [cipher1, cipher2])
print(f"True key:\n{secret_key}")
print(f"Recovered key:\n{K_recovered}")
print(f"Keys match: {np.array_equal(K_recovered, secret_key)}")
print()
# Verify by decrypting with recovered key
recovered_cipher = HillCipher(K_recovered)
test_msg = "thehillcipherisbroken"
ct_test = cipher_secret.encrypt(test_msg)
dt_test = recovered_cipher.decrypt(ct_test)
print(f"Test message: '{test_msg}'")
print(f"Encrypted: '{ct_test}'")
print(f"Decrypted (rec): '{dt_test}'")
print(f"Attack success: {dt_test.startswith(test_msg)}")
=== Known-Plaintext Attack ===
Known pair 1: plaintext 'he' = [7 4] -> ciphertext = [7 8] = 'hi'
Known pair 2: plaintext 'lp' = [11 15] -> ciphertext = [ 0 19] = 'at'
True key:
[[3 3]
[2 5]]
Recovered key:
[[3 3]
[2 5]]
Keys match: True
Test message: 'thehillcipherisbroken'
Encrypted: 'avhrftngrnhixwfppaqoel'
Decrypted (rec): 'thehillcipherisbrokenx'
Attack success: True
Experiment 5: Keyspace Analysis#
We compute the fraction of \(2 \times 2\) matrices that are invertible for various moduli.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
def count_invertible_2x2(m):
"""Count invertible 2x2 matrices over Z_m."""
count = 0
for a in range(m):
for b in range(m):
for c in range(m):
for d in range(m):
det = (a * d - b * c) % m
if np.gcd(det, m) == 1:
count += 1
return count
# Compute for small moduli
moduli = list(range(2, 20))
fractions = []
counts = []
for m in moduli:
total = m ** 4
inv = count_invertible_2x2(m)
counts.append(inv)
fractions.append(inv / total)
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
# Fraction plot
colors = ['green' if all(m % p != 0 for p in [2, 3, 5, 7, 11, 13] if p < m) or m in [2,3,5,7,11,13,17,19] else 'steelblue' for m in moduli]
prime_mask = [m in [2, 3, 5, 7, 11, 13, 17, 19] for m in moduli]
axes[0].bar(moduli, fractions, color=['green' if p else 'steelblue' for p in prime_mask], alpha=0.8)
axes[0].set_xlabel('Modulus m', fontsize=12)
axes[0].set_ylabel('Fraction invertible', fontsize=12)
axes[0].set_title('Fraction of Invertible 2×2 Matrices over Z_m', fontsize=13, fontweight='bold')
axes[0].set_xticks(moduli)
axes[0].legend(['Prime', 'Composite'], loc='upper right')
# |GL(2, Z_m)| plot
axes[1].bar(moduli, [np.log10(c) if c > 0 else 0 for c in counts], color='darkorange', alpha=0.8)
axes[1].set_xlabel('Modulus m', fontsize=12)
axes[1].set_ylabel('log₁₀ |GL(2, Z_m)|', fontsize=12)
axes[1].set_title('Size of GL(2, Z_m)', fontsize=13, fontweight='bold')
axes[1].set_xticks(moduli)
plt.tight_layout()
plt.savefig('hill_keyspace_analysis.png', dpi=150, bbox_inches='tight')
plt.show()
# Print for m=26
print(f"\nFor m=26 (standard Hill cipher):")
print(f" Total 2x2 matrices: 26^4 = {26**4}")
inv26 = count_invertible_2x2(26) if 26 <= 19 else None
if inv26 is None:
# Compute analytically: |GL(2, Z_26)| = |GL(2,Z_2)| * |GL(2,Z_13)|
# |GL(2,Z_p)| = (p^2-1)(p^2-p) for prime p
gl2_2 = (4 - 1) * (4 - 2) # 6
gl2_13 = (169 - 1) * (169 - 13) # 168 * 156 = 26208
gl2_26 = gl2_2 * gl2_13
print(f" |GL(2, Z_26)| = |GL(2,Z_2)| × |GL(2,Z_13)| = {gl2_2} × {gl2_13} = {gl2_26}")
print(f" Fraction invertible: {float(gl2_26 / 26**4):.4f}")
print(f" Key space: {gl2_26} (about {float(np.log2(gl2_26)):.1f} bits)")
For m=26 (standard Hill cipher):
Total 2x2 matrices: 26^4 = 456976
|GL(2, Z_26)| = |GL(2,Z_2)| × |GL(2,Z_13)| = 6 × 26208 = 157248
Fraction invertible: 0.3441
Key space: 157248 (about 17.3 bits)
7.4 Exercises#
Exercise 7.1: Encrypt by Hand#
Encrypt the plaintext “CODE” using the \(2 \times 2\) key matrix \(K = \begin{pmatrix} 5 & 8 \\ 17 & 3 \end{pmatrix}\). Show all intermediate computations.
Hint
Convert C=2, O=14, D=3, E=4. Block 1: \(K \cdot (2, 14)^T = (5 \cdot 2 + 8 \cdot 14, 17 \cdot 2 + 3 \cdot 14)^T = (122, 76)^T \equiv (18, 24)^T\) mod 26, giving ‘sy’.
Exercise 7.2: Find the Inverse#
Compute the inverse of \(K = \begin{pmatrix} 7 & 11 \\ 3 & 4 \end{pmatrix}\) modulo 26. Verify by multiplying \(K \cdot K^{-1} \equiv I \pmod{26}\).
Hint
\(\det(K) = 28 - 33 = -5 \equiv 21 \pmod{26}\). Since \(\gcd(21, 26) = 1\), the inverse exists. Find \(21^{-1} \pmod{26}\) using the extended Euclidean algorithm: \(21 \cdot 5 = 105 \equiv 1 \pmod{26}\).
Exercise 7.3: Proof of Invertibility Criterion#
Prove that a matrix \(K\) over \(\mathbb{Z}_m\) is invertible if and only if \(\gcd(\det(K), m) = 1\).
Hint
Use the adjugate formula: \(K^{-1} = \det(K)^{-1} \cdot \text{adj}(K)\). The scalar \(\det(K)^{-1}\) exists in \(\mathbb{Z}_m\) iff \(\gcd(\det(K), m) = 1\).
Exercise 7.4: Chosen-Plaintext Attack#
Design a chosen-plaintext attack on a \(3 \times 3\) Hill cipher. What 3 plaintexts would you choose to make the key recovery as simple as possible?
Hint
Choose the standard basis vectors: \((1,0,0)^T\), \((0,1,0)^T\), \((0,0,1)^T\) — corresponding to “baa”, “aba”, “aab”. Then \(M = I\), so \(K = C \cdot I^{-1} = C\). The ciphertext blocks directly reveal the columns of the key.
Exercise 7.5 (Challenge): Counting Valid Keys#
For the \(2 \times 2\) Hill cipher over \(\mathbb{Z}_{26}\), compute \(|\mathrm{GL}(2, \mathbb{Z}_{26})|\) analytically using the Chinese Remainder Theorem: \(\mathbb{Z}_{26} \cong \mathbb{Z}_2 \times \mathbb{Z}_{13}\).
Hint
By CRT, \(\mathrm{GL}(2, \mathbb{Z}_{26}) \cong \mathrm{GL}(2, \mathbb{Z}_2) \times \mathrm{GL}(2, \mathbb{Z}_{13})\). For a prime \(p\): \(|\mathrm{GL}(2, \mathbb{Z}_p)| = (p^2 - 1)(p^2 - p)\). Compute each factor and multiply.
7.5 Summary and Key Takeaways#
In this chapter, we have studied the Hill cipher, the first polygraphic cipher based on linear algebra:
Matrix encryption. The Hill cipher encrypts \(n\)-letter blocks via multiplication by an \(n \times n\) key matrix over \(\mathbb{Z}_{26}\), completely destroying single-letter frequency statistics.
Invertibility. A key matrix is valid iff its determinant is coprime to 26. The modular inverse is computed via the adjugate formula and the extended Euclidean algorithm.
Known-plaintext vulnerability. The cipher is completely broken by \(n\) known plaintext-ciphertext pairs — a consequence of the linearity of the encryption function.
Frequency resistance but linear weakness. While the Hill cipher resists frequency analysis, its linear structure makes it vulnerable to algebraic attacks.
Tip
The Hill cipher perfectly illustrates a fundamental principle of cryptographic design: algebraic structure that enables efficient encryption also enables efficient cryptanalysis. Modern ciphers (like AES) carefully combine linear operations (MixColumns) with nonlinear operations (SubBytes) to achieve both efficiency and security.
What comes next: In Chapter 8, we study the Playfair cipher, another polygraphic system that operates on digrams using a different geometric approach.
7.6 References#
Hill, L. S. (1929). “Cryptography in an Algebraic Alphabet.” The American Mathematical Monthly, 36(6), 306–312. The original paper introducing the Hill cipher — elegant and readable, showing how linear algebra naturally applies to cryptography.
Hill, L. S. (1931). “Concerning Certain Linear Transformation Apparatus of Cryptography.” The American Mathematical Monthly, 38(3), 135–154. Hill’s follow-up paper with more detailed analysis and larger block sizes.
Overbey, J., Traves, W., and Wojdylo, J. (2005). “On the Keyspace of the Hill Cipher.” Cryptologia, 29(1), 59–72. Detailed analysis of the keyspace size |GL(n, Z_m)| for various n and m.
Stinson, D. R. and Paterson, M. (2018). Cryptography: Theory and Practice, 4th ed. CRC Press. Chapter 2 provides a modern textbook treatment of the Hill cipher and its cryptanalysis.
Eisenberg, M. (1999). “Hill Ciphers and Modular Linear Algebra.” Unpublished lecture notes, University of British Columbia. Clear exposition of the linear algebra behind the Hill cipher, including the CRT decomposition of GL(n, Z_m).