Hill Cipher
Turn blocks of letters into vectors, multiply by an invertible matrix, and reduce modulo 26.
What is the Hill Cipher?
The Hill cipher uses linear algebra over arithmetic modulo 26. Instead of substituting one letter at a time, it transforms a block of letters together using a key matrix.
A valid key matrix must be invertible modulo 26. For a 2×2 matrix, its determinant must be relatively prime to 26.
The cipher mechanics on this page are self-contained. Science Olympiad event formats, allowed variants, and tournament constraints can change by season; the current official Rules Manual and official clarifications take precedence.
No outside reference is assumed. Work through Foundations → Complete Reference → Encryption → Decryption in order, then use the competition and cryptanalysis sections.
What you need to know
- Use A=0 through Z=25.
- For a 2×2 key K and plaintext vector p, encryption is c = Kp mod 26 .
- Decryption uses the modular inverse matrix: p = K⁻¹c mod 26 .
- Pad the plaintext if its length is not a multiple of the matrix size.
Beginner glossary
| Term | Meaning |
|---|---|
| Vector | An ordered block of letter numbers, usually written as a column. |
| Matrix | A rectangular array of numbers used to mix the vector entries. |
| Determinant | A number computed from the key matrix; it determines whether an inverse exists mod 26. |
| Invertible | A matrix is usable for decryption only if its determinant has a modular inverse mod 26. |
| Block size | The number of letters encrypted together; 2 for a 2×2 matrix, 3 for 3×3. |
Keep this beside you while solving
| Letter | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Value | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
Example key
2×2 inverse recipe
For
K = [[a,b],[c,d]]
, compute
det(K)=ad−bc
. Find
det(K)⁻¹ mod 26
. Then
K⁻¹ = det(K)⁻¹ · [[d,−b],[−c,a]] mod 26
.
c = Kp mod 26
. Keep the same convention for every block.
Determinant test
A determinant is valid when
gcd(det(K),26)=1
. That means it is not divisible by 2 or 13.
How encryption works
Form a vector
HI → [7,8]ᵀ.
Multiply
[[3,3],[2,5]] × [7,8]ᵀ = [45,54]ᵀ.
Reduce mod 26
[45,54] → [19,2].
Convert back
19=T and 2=C, so HI encrypts to TC.
How decryption works
Compute or use K⁻¹
For the example key, K⁻¹=[[15,17],[20,9]] mod 26.
Convert ciphertext
TC → [19,2]ᵀ.
Multiply by K⁻¹
The result is [7,8] mod 26.
Convert back
[7,8] → HI.
How to approach it in Codebusters practice
- Write the letter-number row and key matrix clearly.
- Reduce modulo 26 after each multiplication/addition to keep numbers small.
- Verify invertibility before spending time trying to invert a matrix.
What the problem gives you vs. what you produce
| Part | What to expect |
|---|---|
| You may be given | A key matrix and ciphertext/plaintext. |
| You must find | Blockwise encryption or decryption using modular matrix arithmetic. |
| Fastest first move | Write A=0…Z=25 and verify the determinant/inverse before processing blocks. |
How to attack an unknown or partially known key
- Known plaintext blocks can provide equations for recovering an unknown matrix when enough independent information is available.
- Because blocks mix letters together, ordinary single-letter frequency analysis is less direct than for monoalphabetic substitution.
- A candidate inverse matrix should be checked by verifying K·K⁻¹ ≡ I mod 26.
Follow one example from start to finish
HI → [7,8]ᵀ
[[3,3],[2,5]]
TC
Before moving on, make sure you can answer these without another site:
- Can you explain why an even determinant is invalid mod 26?
- Can you convert HELP into two 2-letter numeric vectors?
- Can you distinguish ordinary division from multiplication by a modular inverse?
Common mistakes
Using A=1 instead of A=0.
Multiplying vectors/matrices in the wrong orientation.
Using an ordinary real-number inverse instead of a modular inverse.
Choosing a matrix whose determinant has no inverse mod 26.
Competition speed strategies
Keep values reduced mod 26 after every row calculation.
For 2×2 matrices, memorize the inverse structure [[d,-b],[-c,a]] times det⁻¹.
Write one vector per line and label plaintext/ciphertext to avoid reversing the direction.
What to remember under time pressure
See every transformation
Use the lab to change inputs and keys, keep the relevant reference material visible, inspect each intermediate transformation, and then read the “How to reverse it” panel so encryption and decryption connect.