Hill Cipher
Matrix multiplication encrypts blocks — and linear relations enable a known-plaintext attack.
Known plaintext attack (matrix algebra)
Why This Matters
Lester Hill’s cipher illustrates block encryption through matrix multiplication. Its linear structure also gives a particularly clear known-plaintext attack. AES uses linear algebra in MixColumns, but the complete AES cipher includes nonlinear operations and is not simply a larger Hill cipher.
Lester S. Hill published his matrix-based system in the American Mathematical Monthly in 1929. It maps groups of letters through an invertible matrix modulo the alphabet size. The system provides a useful introduction to linear algebra in cryptography without establishing a direct historical influence on every later matrix-based design.
Hill also explored mechanical implementation. The cryptanalytic limitation illustrated here follows from the linear equations themselves; no assertion about widespread deployment is needed to demonstrate it.
Convert letters to numbers (A=0, B=1…Z=25). Arrange plaintext in column vectors of length n. Multiply by an invertible n×n key matrix modulo 26.
Key matrix K (2×2): Plaintext: HI = [7, 8]
| 3 3 |
| 2 5 | C = K × P mod 26
= [3×7+3×8, 2×7+5×8] mod 26
= [45, 54] mod 26
= [19, 2]
= TC
Decryption uses the matrix inverse: P = K⁻¹ × C mod 26. Not all matrices have inverses mod 26 — the key matrix must be chosen carefully.
About this demo: To guarantee that Decrypt exactly restores your original message, this demo reversibly escapes the letters X, Q, and Z (as ZA, ZB, ZC) before enciphering, so padding and filler X can never be confused with a real letter. Messages containing X, Q, or Z therefore produce slightly different ciphertext than a strictly classical Hill cipher would. Odd-length messages are padded with a trailing X, and the key matrix must be invertible mod 26 — the demo rejects singular matrices.
For an n×n Hill key, collect n matched plaintext/ciphertext blocks as the columns of matrices P and C. When P is invertible modulo 26 — that is, gcd(det(P), 26) = 1 — the key follows directly: K = C × P⁻¹ mod 26. Merely knowing n blocks does not guarantee this condition. If it fails, more observations or a more general solution of the linear congruences may be needed. The cipher remains vulnerable because the relation is linear.
Enough information: the two blocks HI and LL give P = [[7, 11], [8, 11]], whose determinant is −11, coprime to 26. Matched with ciphertext TC and OZ, they recover K = [[3, 3], [2, 5]], the demo’s default key.
Not enough information: AA and AB both map to AA and DF under either K = [[3, 3], [2, 5]] or K = [[5, 3], [2, 5]]. Both keys are valid, but these two known blocks do not distinguish them. These examples use classical A = 0 blocks; remember the demo’s X/Q/Z escaping when analyzing other inputs.
Reading: Joshua Holden, The Mathematics of Secrets: Cryptography from Caesar Ciphers to Digital Encryption (2017), §§1.6–1.7. The invertibility check above specifies when the direct matrix-inverse recovery works.
| Concept from Hill Cipher | Modern Evolution |
|---|---|
| Matrix multiplication as cipher operation | AES MixColumns: matrix multiplication over GF(2⁸) for diffusion |
| Multiple letters encrypted together | Block cipher: AES processes 128-bit (16-byte) blocks simultaneously |
| Linear structure = linear algebra attack | AES SubBytes prevents the complete cipher from being one linear matrix transformation |
| Exhibit | 7 of 172 |
| Era | 1929 |
| Trust | Broken |
| Inventor | Lester S. Hill |
| Year | 1929 |
| Key Type | Invertible key matrix (n×n) |
| Broken By | Known plaintext attack (matrix algebra) |
Sources and Reading
Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, Handbook of Applied Cryptography (1997), §7.3.2, p. 240; David Kahn, The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet, revised edition (1996), on Hill’s 1929 publication. The worked matrix products and inverse conditions are independently checkable.