Hill cipher

The Hill cipher was proposed by the American mathematician Lester S. Hill in 1929 in The American Mathematical Monthly. It is the first cipher to explicitly use linear algebra — a historical bridge between classical cryptography and modern block ciphers (DES, AES).

Principle

Hill works on blocks of n letters rather than individual characters. Each block is seen as a vector of n integers (alphabet rank: A = 0, …, Z = 25). The key is a square n × n matrix invertible modulo 26.

Encryption:

C = K · P mod 26

Decryption uses the modular inverse of K:

P = K⁻¹ · C mod 26

For K to be invertible mod 26, its determinant must be coprime to 26 (i.e. odd and not divisible by 13).

Example (2×2 matrix)

Plaintext CIPHERCHRONICLEX (padded to 16 letters to fit blocks of 2), key:

      | 3  2 |
  K = | 5  7 |   (det = 21 − 10 = 11, coprime with 26 ✓)

Encrypting block CI = [2, 8]:

  | 3·2 + 2·8 |   | 22 |   |  W |
  | 5·2 + 7·8 | = | 66 | = | 14 |  →  WO
                       mod 26

Continuing on all blocks of CIPHERCHRONICLEX:

CI → WO     PH → HU     ER → UJ     CH → UH
RO → BB     NI → DR     CL → CJ     EX → GZ

Ciphertext: WOHUUJUHBBDRCJGZ.

Variants

• 3×3 Hill — 3×3 matrices, triplet blocks. Larger keyspace.
• Hill-like moderns — DES, AES and every symmetric block cipher descend from Hill’s idea, adapted to non-linear maps over GF(2ⁿ).
• Cramer-Shoup, LWE — modern post-quantum ciphers still rest on linear algebra over finite fields.

Weaknesses

• Known-plaintext attack: if the attacker knows n pairs (P, C), he gets a linear system of n equations in n unknowns and recovers K. Instant with a computer.
• No semantic security: two identical plaintext blocks produce identical ciphertext blocks — the text’s structure stays visible.
• For small n (2 or 3), the invertible-matrix space sits in the tens of thousands; brute-forceable.

That’s why, while mathematically elegant, Hill is never used alone in modern practice. Its descendants (DES, AES) add non-linearity (S-boxes) to resist linear cryptanalysis.

In CipherChronicle

Hill is a gateway to modern ciphers. Its grids can let the player directly manipulate matrices, giving a more mathematical and technical feel — a contrast with the pure shift of Caesar.