Hill Cipher

Cryptography · Axiom Academy

Matrix-based polygraphic substitution cipher using linear algebra 1. Lester Hill's Innovation (1929) Lester S. Hill introduced a revolutionary approach to cryptography by applying linear algebra to encrypt blocks of plaintext simultaneously. Historical Context: This was groundbreaking because it was one of the first ciphers to be practically impossible to break without knowing the key, especially when using large block sizes. The Hill Cipher encrypts by multiplying a key matrix K with plaintext vector P, then taking the result modulo 26. Convert plaintext letters to numbers (A=0, B=1, ..., Z=25) Group into blocks matching the key matrix size Multiply each plaintext vector by the key matrix Take results modulo 26 to get ciphertext numbers For decryption to work, the key matrix must be invertible modulo 26. This means: The determinant of K must be coprime to 26 (gcd(det(K), 26) = 1) Valid determinant values: must share no factors with 26 = 2 × 13 Invalid: Any multiple of 2 or 13 Without this property, the matrix has no inverse mod 26, making decryption impossible. 4. Decryption: P = K^(-1)C mod 26 To decrypt, we multiply the ciphertext by the inverse of the key matrix (modulo 26). Finding the Matrix Inverse mod 26: Find the modular multiplicative inverse: det(K)^(-1) mod 26 K^(-1) = det(K)^(-1) × adj(K) mod 26 Let's encrypt "HELP" using a 2×2 key matrix. First block: [3,3; 2,5] × [7; 4] = [33; 34] ≡ [7; 8] mod 26 → HI

This is the written version of the interactive lesson above. See the full Cryptography course.