Hill Cipher
Linear algebra enters cryptography — and is immediately defeated
Why This Matters
Lester Hill’s 1929 cipher was the first to use matrix multiplication as a cryptographic operation — bringing linear algebra into cryptography and influencing cipher design principles that persist in modern algorithms like AES’s MixColumns.
Lester Hill was a mathematics professor at Hunter College who applied linear algebra to cryptography in 1929. His cipher was the first to use matrix multiplication as a cryptographic operation — a genuinely innovative idea that would influence cipher design for decades.
Hill published his system in the American Mathematical Monthly and later built a machine to implement it. The cipher saw some mechanical use but was never widely adopted for serious communications — its known-plaintext vulnerability was recognized quickly.
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]
| 6 24 |
| 1 13 | C = K × P mod 26
= [6×7+24×8, 1×7+13×8] mod 26
= [234, 111] mod 26
= [0, 7]
= AG
Decryption uses the matrix inverse: P = K⁻¹ × C mod 26. Not all matrices have inverses mod 26 — the key matrix must be chosen carefully.
If an attacker knows just n plaintext-ciphertext pairs (where n is the matrix dimension), they can set up a system of linear equations and solve for the key matrix directly using linear algebra. For a 2×2 key, two known pairs are sufficient. This makes the Hill cipher catastrophically weak in any environment where the attacker can observe plaintext-ciphertext pairs.
| 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-letter) blocks simultaneously |
| Linear structure = linear algebra attack | AES non-linearity: S-boxes prevent linear algebraic attacks |
| Exhibit | 06 of 37 |
| Era | 1929 |
| Security | Broken |
| Inventor | Lester S. Hill |
| Year | 1929 |
| Key Type | Invertible key matrix (n×n) |
| Broken By | Known plaintext attack (matrix algebra) |