The Hill Cipher is a classical polygraphic substitution cipher invented by Harold Hill in 1929. Unlike simple substitution ciphers, which encode one letter at a time, the Hill Cipher operates on blocks of letters, using linear algebra and matrix multiplication over modular arithmetic. This allows it to encode multiple letters simultaneously, providing greater resistance to frequency analysis.
Each block of plaintext letters is treated as a vector and multiplied by an invertible key matrix modulo 26 (for the 26-letter alphabet). Decoding requires the inverse of this matrix, making the Hill Cipher both symmetric and mathematically precise.
Hill Cipher: Encoding
To encode, first select a block size and an invertible key matrix. Convert each letter to a numeric value (A=0, B=1, ..., Z=25). Multiply each plaintext vector by the key matrix modulo 26. For example, using a 2×2 key matrix to encrypt “HI”:
Plaintext: H I
Numeric: H=7, I=8
Key Matrix (2x2):
[3 3]
[2 5]
Multiply modulo 26:
Cipher Vector = Key Matrix × Plaintext Vector mod 26
Calculation:
C1 = (3*7 + 3*8) mod 26 = (21+24) mod 26 = 45 mod 26 = 19 → T
C2 = (2*7 + 5*8) mod 26 = (14+40) mod 26 = 54 mod 26 = 2 → C
Ciphertext: T C
Each pair of plaintext letters is encoded as a pair of ciphertext letters. Larger block sizes use larger matrices, increasing security and complexity.
Hill Cipher: Decoding
Decoding requires the inverse of the key matrix modulo 26. Multiply each ciphertext vector by the inverse matrix to recover the original plaintext:
Ciphertext: T C
Numeric: T=19, C=2
Inverse Key Matrix (2x2):
[5 21]
[24 15]
Multiply modulo 26:
Plaintext Vector = Inverse Matrix × Cipher Vector mod 26
Calculation:
P1 = (5*19 + 21*2) mod 26 = (95+42) mod 26 = 137 mod 26 = 7 → H
P2 = (24*19 + 15*2) mod 26 = (456+30) mod 26 = 486 mod 26 = 8 → I
Plaintext: H I
Hill Cipher: Notes
The Hill Cipher demonstrates the application of linear algebra to cryptography. Its security depends on the choice of an invertible key matrix; if the matrix is not invertible modulo 26, decryption is impossible. While strong against classical frequency attacks, it is vulnerable to modern known-plaintext attacks. It also illustrates an early use of polygraphic substitution and matrix-based encryption, influencing later cryptosystems.