Hill Cipher
A block cipher that encrypts letter vectors using matrix multiplication modulo 26.
History & context
The Hill cipher is famous because it brings linear algebra into cryptography. Instead of substituting letters one at a time, it encrypts blocks (pairs, triples, etc.), which can better obscure single-letter frequencies. Its key weakness is linearity: with enough known plaintext/ciphertext pairs, the key matrix can be solved directly. In puzzle settings, it’s still interesting because it produces ciphertext that looks structured but not easily solvable by basic frequency methods.
How Hill Cipher works
1) Choose block size n (e.g., 2). 2) Choose an invertible key matrix K modulo 26. 3) Convert plaintext into vectors of length n. 4) Encrypt: C = K·P (mod 26). 5) Decrypt: P = K⁻¹·C (mod 26). Invertibility is crucial: det(K) must be coprime with 26 so that det(K) has a modular inverse.
Core rules
- Work mod 26 (or mod m if using a different alphabet).
- Key matrix must be invertible mod 26 (det(K) must have an inverse).
- Plaintext is grouped into fixed-size blocks; padding may be added.
- Because it’s linear, known plaintext can reveal the key quickly.
Worked example
How to encode / decode
Step-by-step
- Choose block size n (2 is common for puzzles).
- Pick an n×n key matrix K that is invertible mod 26.
- Normalize plaintext to letters (decide how to handle spaces/punctuation).
- Convert letters to numbers A=0..Z=25, group into blocks of n, pad if needed.
- Compute C = K·P (mod 26), convert back to letters.
How to break a Hill Cipher
Hill is vulnerable to known-plaintext attacks. If you know enough plaintext blocks and their corresponding ciphertext blocks, you can solve for K with linear algebra modulo 26. Without known plaintext, brute force is only feasible for tiny block sizes with small constrained key spaces. In practice, you’d use heuristic scoring or exploit puzzle constraints (e.g., known header, known word list).
Practical checklist
- If you have known plaintext/ciphertext: collect n blocks, set up equations, solve for K mod 26.
- Check invertibility and validate by encrypting/decrypting additional blocks.
- If no known plaintext: try guessing common cribs and solving for K.
- For puzzles: use scoring (tetragrams) across candidate keys if the search space is constrained.
What frequency looks like
Hill disrupts monogram frequency more than monoalphabetic ciphers because letters influence each other within a block. However, it is still structured: ciphertext remains alphabetic and often has more uniform-looking distributions than Caesar/Affine. Bigram/trigram patterns are not preserved in the same way as transposition; instead, blocks behave like mixed substitutions.
- Monograms may look flatter than standard English.
- Text remains alphabetic and structured (unlike random bytes/encodings).
- If block size is small (2), some repeating patterns can still occur in ciphertext.
- Known-plaintext is the real killer; frequency alone won’t solve it.
Mini example
Common mistakes
- Using a matrix that isn’t invertible mod 26.
- Mixing different A=0 vs A=1 indexing conventions across tools.
- Forgetting padding rules (changes last block).
- Assuming spaces are included in the alphabet (most Hill implementations do letters-only).
Variants
- Different modulus/alphabet sizes (include digits, punctuation).
- Block size 3 or more (harder to brute force).
- Affine Hill (adds a vector offset).
Practice
Practice with n=2 first: pick a valid matrix, encrypt a sentence, then try recovering the key from a few known blocks.
Try these prompts
- Use K=[[3,3],[2,5]] to encrypt a short message and verify decoding.
- Given plaintext/ciphertext pairs of 2-letter blocks, solve for K mod 26.
- Try different padding letters and see how ciphertext changes.
- Try n=3 with a known invertible matrix and observe how much harder it looks.