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]
| 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.
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 40 |
| Era | 1929 |
| Security | Broken |
| Inventor | Lester S. Hill |
| Year | 1929 |
| Key Type | Invertible key matrix (n×n) |
| Broken By | Known plaintext attack (matrix algebra) |