# Hill cipher

The Hill cipher is a classical symmetric polygraphic cipher that encrypts blocks of letters by multiplying each block, written as a vector of numbers, by a secret key matrix modulo the alphabet size, usually 26. Lester S. Hill of Hunter College introduced it in the paper "Cryptography in an Algebraic Alphabet" in *The American Mathematical Monthly*, volume 36, June-July 1929, pages 306-312, and extended it in a second paper in 1931.<sup>[1](https://sites.math.washington.edu/~king/coursedir/m308a01/Projects/Cryptography.htm)</sup> It was the first general method for applying linear algebra to polygraphic ciphers, and although it is insecure by modern standards, it remains a standard example in cryptography and linear algebra courses.<sup>[2](https://www.apprendre-en-ligne.net/crypto/hill/HillICTCM12.pdf)</sup>

| Key fact | Detail |
|---|---|
| Invention | Lester S. Hill, "Cryptography in an Algebraic Alphabet," *American Mathematical Monthly* 36 (June-July 1929), pp. 306-312; second paper in 1931<sup>[1](https://sites.math.washington.edu/~king/coursedir/m308a01/Projects/Cryptography.htm)</sup> |
| Encryption rule | C = K P mod 26 for an m-by-m key matrix K and plaintext blocks of m letters; decryption is P = K⁻¹ C mod 26<sup>[3](https://www.munotes.in/notes/BSc-Computer-Science/TY-BSc-Computer-Science/Semester-5/Cyber-and-Information-Security/the-hill-cipher/)</sup> |
| Valid key condition | The key must be invertible modulo 26, which requires gcd(det K, 26) = 1<sup>[4](https://math.asu.edu/sites/default/files/hill.pdf)</sup> |
| Key space | About 45,000 valid keys for block size 2 and about 52,000,000,000 for block size 3<sup>[5](https://assets.press.princeton.edu/chapters/s10826.pdf)</sup> |
| Principal weakness | A known-plaintext attack with n known block pairs recovers the key by a single matrix inversion<sup>[6](https://sinapsi.wiki/w/ctf-crypto/p/block-cipher/hill-cipher/)</sup> |
| Ciphertext-only attack | Broken in O(d·13^d) operations for a d x d key over Z₂₆, down from O(d³·26^(d²)), by Khazaei and Ahmadi (2017)<sup>[7](https://www.sciencedirect.com/science/article/pii/S0020019016301338)</sup> |
| Practical status | Not considered sufficiently secure for sensitive applications; used mainly for teaching<sup>[4](https://math.asu.edu/sites/default/files/hill.pdf)</sup> |

## How encryption works

Letters are first converted to numbers, with A = 0 through Z = 25. The plaintext is divided into blocks of n letters, and each block is treated as a column vector. Encryption multiplies the key matrix K by each vector and reduces the result modulo 26; the resulting numbers are read back as letters. For a 2 x 2 key, the ciphertext letters for a pair (x, y) are (ax + by) mod 26 and (cx + dy) mod 26, where a, b, c, and d are the key entries.<sup>[8](https://www.math.stonybrook.edu/~scott/papers/MSTP/crypto/8Hill_Cipher.html)</sup> For example, with the key matrix \( \begin{bmatrix} 5 & 11 \\ 1 & 22 \end{bmatrix} \), the block "NU", corresponding to the vector (13, 20), encrypts to (285, 453), which reduces to (25, 11) modulo 26, the letters "ZL".<sup>[9](https://mathcenter.oxford.emory.edu/site/math125/hillCipher/)</sup>

Decryption applies the inverse matrix. Because the arithmetic is modulo 26, the inverse exists only when the determinant of K has a multiplicative inverse modulo 26, that is, when gcd(det K, 26) = 1; a determinant that is even, a multiple of 13, or zero makes decryption impossible.<sup>[4](https://math.asu.edu/sites/default/files/hill.pdf)</sup> For a 2 x 2 key, the inverse is built from the multiplicative inverse of the determinant ad − bc and the adjugate entries; in one worked example with a = 2, b = 3, c = 5, and d = 6, the determinant is −3 ≡ 23 (mod 26), its inverse is 17, and the deciphering matrix has entries A = 24, B = 1, C = 19, and D = 8.<sup>[8](https://www.math.stonybrook.edu/~scott/papers/MSTP/crypto/8Hill_Cipher.html)</sup> If the message length is not a multiple of the block size, it is padded with an extra letter such as X or Z.<sup>[8](https://www.math.stonybrook.edu/~scott/papers/MSTP/crypto/8Hill_Cipher.html)</sup>

The block size equals the key matrix dimension: a 3 x 3 key uses nine numbers and encrypts triples of letters, and the scheme extends to blocks of six or more letters.<sup>[8](https://www.math.stonybrook.edu/~scott/papers/MSTP/crypto/8Hill_Cipher.html)</sup> Some implementations use a 29-character alphabet, adding a space and two punctuation marks, so that a randomly chosen matrix is more likely to be invertible.<sup>[10](https://dummit.cos.northeastern.edu/docs/cryptography_1_classical_cryptosystems.pdf)</sup>

## What the cipher achieves

Because encryption acts on whole blocks, the Hill cipher masks single-letter frequencies. Repeated digraphs and repeated letters in the plaintext do not produce repeated ciphertext patterns; in one example, the repeated digraphs IS and SS and the repeated letters S and P in "Mississippi" are all disguised.<sup>[11](https://www.cs.uri.edu/cryptography/classical-ciphers/hill/article.html)</sup> Changing one or two plaintext letters can completely change the corresponding ciphertext block, which makes the cipher hard to crack by frequency analysis alone.<sup>[2](https://www.apprendre-en-ligne.net/crypto/hill/HillICTCM12.pdf)</sup> The usefulness of ordinary frequency analysis shrinks rapidly as the block size grows, and a Hill cipher on blocks of six or more letters is not hard to implement.<sup>[8](https://www.math.stonybrook.edu/~scott/papers/MSTP/crypto/8Hill_Cipher.html)</sup>

The number of valid keys grows quickly with block size: about 45,000 for block size 2 and about 52,000,000,000 for block size 3, so brute-force search becomes difficult.<sup>[5](https://assets.press.princeton.edu/chapters/s10826.pdf)</sup>

## Cryptanalysis

**Known-plaintext attack.** The cipher's defining weakness is its linearity. If an attacker knows n plaintext/ciphertext block pairs whose plaintext blocks are linearly independent modulo 26, the equations C = K P form a solvable linear system, and one matrix inversion recovers the entire key.<sup>[6](https://sinapsi.wiki/w/ctf-crypto/p/block-cipher/hill-cipher/)</sup> For a 2 x 2 key, two known digraph pairs give four linear congruences modulo 26 in the four unknown key entries, which can be solved directly.<sup>[12](https://websites.nku.edu/~christensen/1402%20Hill%20cipher.pdf)</sup> Stereotypical message openings and endings often supply the needed known plaintext, and for block size 2 the attack is nearly as easy as legitimate decryption.<sup>[5](https://assets.press.princeton.edu/chapters/s10826.pdf)</sup> For this reason Hill ciphers are not considered sufficiently secure for sensitive applications.<sup>[4](https://math.asu.edu/sites/default/files/hill.pdf)</sup> Modern block ciphers always include a non-linear component precisely to prevent this kind of attack.<sup>[13](https://secgroup.dais.unive.it/teaching/cryptography/known-plaintext-attacks/)</sup>

**Ciphertext-only attack.** The Hill cipher was long believed to resist ciphertext-only attack, and this claim was repeated in several modern cryptography textbooks. A 2017 paper by Shahram Khazaei and Siavash Ahmadi in *Information Processing Letters* (volume 118, pages 25-29) disproved that belief: using a divide-and-conquer technique and the Chinese Remainder Theorem, exploiting the non-uniformity of letter frequencies modulo 2 and modulo 13, they reduced the attack on a d x d Hill cipher over Z₂₆ from O(d³·26^(d²)) to O(d·13^d) for English text.<sup>[7](https://www.sciencedirect.com/science/article/pii/S0020019016301338)</sup>

## History and mechanical implementation

Hill published two papers describing the system: "Cryptography in an Algebraic Alphabet" in 1929 and "Concerning Certain Linear Transformation Apparatus of Cryptography" in *The American Mathematical Monthly*, volume 38, March 1931, pages 135-154.<sup>[1](https://sites.math.washington.edu/~king/coursedir/m308a01/Projects/Cryptography.htm)</sup> The 1931 work introduced extensions, the most important now called the affine Hill cipher, which adds a constant vector to the matrix product, giving ciphertext equations of the form C₁ ≡ k₁P₁ + k₂P₂ + m₁ (mod 26); the additive constants can be anything, and the key remains valid as long as the determinant k₁k₄ − k₂k₃ is relatively prime to 26.<sup>[5](https://assets.press.princeton.edu/chapters/s10826.pdf)</sup>

To counter the objection that the system was too complicated for daily use, Hill built a cipher machine using a series of geared wheels that enciphered blocks of six letters, making it essentially unbreakable by frequency analysis; the machine never caught on.<sup>[5](https://assets.press.princeton.edu/chapters/s10826.pdf)</sup> Hill and Louis Weisner filed a patent application for this "Message Protector" on February 14, 1929, and US patent 1,845,947 was issued on February 16, 1932; the device computed linear functions of a sequence of numbers with respect to a modulus using toothed actuating and answer wheels, and was intended for marking bank checks and other messages.<sup>[14](https://patents.google.com/patent/US1845947A/en)</sup>

The Hill ciphers were never used much, because they were too unwieldy by hand and mechanical cryptography developed along the lines of polyalphabetic rotor machines instead.<sup>[5](https://assets.press.princeton.edu/chapters/s10826.pdf)</sup> Hill taught mathematics at [Hunter College](https://www.edgepedia.org/hunter-college) from 1927 until his retirement in 1960, and his rigorous mathematical approach helped ground cryptography in mathematics.<sup>[15](https://mrajacse.wordpress.com/wp-content/uploads/2012/01/an-introduction-to-cryptography.pdf)</sup>

## Legacy and variants

The Hill cipher's vulnerability to known-plaintext attack has made it unusable in practice, but it retains a pedagogical role in both cryptology and linear algebra, and many university cryptography courses teach it alongside DES and AES as the first block cipher and an exercise in matrix cryptanalysis.<sup>[16](https://arxiv.org/abs/1002.3567)</sup><sup> • </sup><sup>[17](https://www.radford.edu/registrar/course-descriptions/math/math-311.html)</sup> A large body of proposed variants tries to repair the weakness: encrypting each plaintext matrix with a variable-length key derived from a Maximum Distance Separable (MDS) master key,<sup>[18](https://arxiv.org/abs/1210.1940)</sup> generating dynamic invertible key matrices from random vector-space bases,<sup>[19](https://arxiv.org/abs/1909.06781)</sup> and using non-invertible matrices over GF(2) in one-way hash constructions.<sup>[20](https://arxiv.org/abs/1210.1925)</sup> Hill's core idea of encrypting with systems of linear equations regained importance with the advent of digital computers, and it forms a piece of many modern ciphers, which combine such linear layers with non-linear components.<sup>[5](https://assets.press.princeton.edu/chapters/s10826.pdf)</sup>

## References

1. [Paal Schiefloe, "Cryptography: Hill ciphers," University of Washington linear algebra project (2001)](https://sites.math.washington.edu/~king/coursedir/m308a01/Projects/Cryptography.htm)
2. [Murray Eisenberg, "Hill Ciphers: A Linear Algebra Project with Mathematica," University of Massachusetts Amherst](https://www.apprendre-en-ligne.net/crypto/hill/HillICTCM12.pdf)
3. ["The Hill Cipher," B.Sc. Computer Science notes, munotes](https://www.munotes.in/notes/BSc-Computer-Science/TY-BSc-Computer-Science/Semester-5/Cyber-and-Information-Security/the-hill-cipher/)
4. ["Hill Ciphers," School of Mathematical and Statistical Sciences, Arizona State University](https://math.asu.edu/sites/default/files/hill.pdf)
5. [Holden, *The Mathematics of Secrets*, chapter 1, Princeton University Press](https://assets.press.princeton.edu/chapters/s10826.pdf)
6. ["Hill Cipher — known-plaintext breaks it in one matrix inversion," Sinapsi wiki](https://sinapsi.wiki/w/ctf-crypto/p/block-cipher/hill-cipher/)
7. [Khazaei, S., and Ahmadi, S., "Ciphertext-only attack on d x d Hill in O(d·13^d)," *Information Processing Letters* 118 (2017), pp. 25-29](https://www.sciencedirect.com/science/article/pii/S0020019016301338)
8. [Scott Sutherland, "The Hill Cipher," Stony Brook Mathematics](https://www.math.stonybrook.edu/~scott/papers/MSTP/crypto/8Hill_Cipher.html)
9. ["The Hill Cipher," Emory University Math Center](https://mathcenter.oxford.emory.edu/site/math125/hillCipher/)
10. ["1.4.4 The Hill Cipher," cryptography course notes, Northeastern University](https://dummit.cos.northeastern.edu/docs/cryptography_1_classical_cryptosystems.pdf)
11. ["Hill Cipher," University of Rhode Island, Cryptography course](https://www.cs.uri.edu/cryptography/classical-ciphers/hill/article.html)
12. ["Section Seventeen: Hill cipher," Northern Kentucky University, Christensen](https://websites.nku.edu/~christensen/1402%20Hill%20cipher.pdf)
13. ["Known-plaintext attacks," Secgroup, Ca' Foscari University of Venice](https://secgroup.dais.unive.it/teaching/cryptography/known-plaintext-attacks/)
14. [US Patent 1,845,947, "Message Protector," Weisner and Hill, issued February 16, 1932](https://patents.google.com/patent/US1845947A/en)
15. [Bauer, *An Introduction to Cryptography*, second edition, chapter on classical ciphers](https://mrajacse.wordpress.com/wp-content/uploads/2012/01/an-introduction-to-cryptography.pdf)
16. ["A Secure Variant of the Hill Cipher," arXiv:1002.3567](https://arxiv.org/abs/1002.3567)
17. [MATH 311 course description, Radford University](https://www.radford.edu/registrar/course-descriptions/math/math-311.html)
18. ["Variable-length Hill Cipher with MDS Key Matrix," arXiv:1210.1940](https://arxiv.org/abs/1210.1940)
19. ["A Vector Space Approach to Generate Dynamic Keys for Hill Cipher," arXiv:1909.06781](https://arxiv.org/abs/1909.06781)
20. ["A Class of Non Invertible Matrices in GF(2) for Practical One Way Hash Algorithm," arXiv:1210.1925](https://arxiv.org/abs/1210.1925)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Computational and symbolic algebra › Symbolic and algebraic algorithms › Applications of symbolic and algebraic algorithms*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license