Hill cipher

How it works

Lester S. Hill published this cipher in 1929, the first that used linear algebra. The letters are cut into blocks of $n$, each block becomes a vector $p$ of numbers (A = 0, …, Z = 25) and is multiplied by an $n \times n$ key matrix: $c = K p \bmod 26$. With $K$ given by GYBNQKURP, ACT becomes POH.

Decryption needs the inverse matrix modulo 26, $K^{-1} = (\det K)^{-1} \operatorname{adj} K$. It exists exactly when $\gcd(\det K, 26) = 1$, that is, when the determinant is odd and not a multiple of 13; other keys lose information and are refused. Some books use row vectors, $c = p K$, which is the same cipher with the transposed matrix.

One block depends on all its letters, so single letter frequencies are mixed up. But the cipher is linear: $n$ blocks of known plaintext with their ciphertext give a matrix equation $C = K P$, and $K = C P^{-1}$ falls out at once (choosing blocks for which $P$ is invertible modulo 26). A known plaintext attack breaks it completely.