Breaking the Hill Cipher

Breaking the Hill Cipher: When Two Letter-Pairs Beat Any Search

Introduction

Every breaker on this site so far has attacked ciphertext and nothing else: brute force for Caesar and the simplified Enigma, bounded search for Autokey, simulated annealing scored against real-English statistics for Substitution and Playfair. Every one of those techniques exists because the attacker has only the scrambled message and has to guess at a key that makes some statistical property of the decryption look like English.

The Hill cipher breaks that pattern entirely, in both directions. Its own guide names “known plaintext vulnerability” as the cipher’s headline weakness, and for good reason: because Hill encryption is nothing but matrix multiplication in modular arithmetic, it’s linear. And linear systems can be solved, not just searched. Give an attacker just two matched pairs of plaintext and ciphertext letters, and the entire key matrix falls out of a single matrix inversion. No scoring function, no restarts, no statistical signal required at all. This post builds that attack, and along the way makes explicit just how different a threat model “the attacker knows a plaintext fragment” really is from “the attacker has ciphertext alone.”

Table of Contents

• Why This Needs Known Plaintext, Not Just Ciphertext
• The Attack: Solving K = C × P⁻¹
• A Worked Example
• Python Implementation
• Interactive Visualizer
• Hill vs. The Other Breakers on This Site
• Limitations of This Attack
• FAQ
• References

Why This Needs Known Plaintext, Not Just Ciphertext

A 2×2 Hill key has “only” 26⁴ = 456,976 possible matrices. That’s smaller than the simplified Enigma breaker’s 17,576-position search once you throw out every matrix whose determinant isn’t coprime with 26 (roughly three-quarters of them aren’t). In principle, a ciphertext-only brute force scoring each candidate decryption with digram or quadgram statistics, the same way the Enigma and Playfair breakers work, is entirely possible for a 2×2 matrix.

It’s also the wrong tool for the job here, for a reason specific to this cipher. Every other cipher on this site is nonlinear in some way that a wrong key genuinely garbles the output in a way statistics can detect. A wrong Caesar shift, a wrong substitution mapping, a wrong Playfair key square all produce text with the wrong letter-pair fingerprint. A Hill cipher’s plaintext-to-ciphertext relationship is linear. An attacker just needs any two matched letter-pairs, whether guessed, intercepted, or simply known because messages in the real world often start predictably (a greeting, a date, a standard header). The moment they have that, the key isn’t a matter of statistics at all anymore. It’s the unique, exact solution to a system of linear equations. Reaching for a statistical search when an exact algebraic solution exists would be strictly worse: slower, and only ever approximately right where the linear algebra is exactly right. This breaker builds the technique that’s actually appropriate for a linear cipher: solve it.

The Attack: Solving K = C × P⁻¹

The Hill cipher encrypts each 2-letter block as c = K·p (mod 26), where p and c are 2-element vectors and K is the 2×2 key matrix. Line up two known plaintext blocks as the columns of a matrix P, and their corresponding ciphertext blocks as the columns of a matrix C. The same relationship holds at the matrix level: C = K·P (mod 26).

Throughout this article, “line up as columns” means literally that: each known letter-pair becomes one column of a 2×2 matrix, not a row, so P’s first column is the first plaintext block and its second column is the second block, and C is built the same way from the matching ciphertext.

That’s a system with exactly one unknown, K, and it has a closed-form solution whenever P is invertible mod 26:

K = C · P⁻¹ (mod 26)

Four steps turn that into an algorithm:

1. Pick two known plaintext blocks and their matching ciphertext. This breaker assumes the known plaintext (the “crib”) sits at the very start of the message. That’s the most common real-world case, and the simplest to reason about.
2. Check that P is invertible mod 26. Its determinant needs to share no common factor with 26: not even, not a multiple of 13. If the first two blocks happen to be degenerate, try the next pair further into the crib; this breaker does exactly that automatically, the same way a cryptanalyst working by hand would.
3. Invert P. This is the identical computation the encryption-side Hill visualizer already does for ordinary decryption: the modular inverse of the determinant, combined with the adjugate matrix.
4. Multiply: K = C · P⁻¹ (mod 26). Done: the entire key, from four known letters.

One more step matters in practice: verify K against the rest of the known crib, not just the two blocks used to derive it. If the crib is longer than four letters, re-encrypting all of it with the recovered K should reproduce the corresponding ciphertext exactly. If it doesn’t, the crib probably isn’t actually sitting where it was assumed to be. That’s a real, useful signal that the attacker’s guess about the message’s structure was wrong, not a flaw in the math.

A Worked Example

Using the visualizer’s default crib (ATTACKATDAWN, the same demo plaintext the encryption-side Hill visualizer starts with) against its default ciphertext:

1. The first two blocks of the crib, AT and TA, already form an invertible plaintext matrix:

   P = [ 0  19 ]      C = [ 12   5 ]
       [19   0 ]          [ 19  17 ]

   (A = 0, T = 19: the four corners of P are exactly those two letters’ numeric values, arranged as the two known blocks side by side. C is built the same way from the ciphertext’s first four letters, MTFR.)

2. det(P) = (0)(0) − (19)(19) ≡ 3 (mod 26), and gcd(3, 26) = 1. That’s invertible on the first try, so there’s no need to search further into the crib.

3. Inverting P gives P⁻¹ = [[0, 11], [11, 0]] (mod 26). Multiplying that against C gives the key:

   K = C · P⁻¹ (mod 26) = [ 3  2 ]
                           [ 5  1 ]

4. Re-encrypting the full 12-letter crib with this K reproduces MTFRAUMTJPOT (the ciphertext’s first 12 letters) exactly, confirming the key before it’s trusted with anything else.

5. Applying K⁻¹ to the rest of the ciphertext recovers a coherent passage. It’s the one this article uses to describe its own attack:

   “Attack at dawn, because a two by two key matrix turns every pair of plaintext letters into a linear combination of the key’s rows, so knowing just two matched plaintext and ciphertext blocks is enough to solve for the entire key by matrix inversion. No searching, no guessing. Just linear algebra turning the attacker’s known fragment into the full secret key, and from there the rest of the message falls open immediately.”

Python Implementation

The interactive visualizer above runs this exact attack in JavaScript: same block search, same modular matrix inversion, same crib verification. Here’s the same attack in Python.

Key Features

• The same fallback search as the visualizer: recover_key tries consecutive block pairs starting from the beginning of the crib until it finds an invertible one, rather than assuming the very first pair works.
• Reuses genuine decryption math: inverse2 is the same determinant/adjugate computation any Hill cipher implementation needs for ordinary decryption. Recovering the key doesn’t require any cryptanalysis-specific linear algebra beyond what encryption already uses.
• Exact, not probabilistic: unlike this site’s statistical breakers, there’s no score to report and no “close but not quite” outcome. Either the crib produces an invertible block and the recovered key checks out against the rest of it, or it doesn’t.

Code

# hill_breaker.py
#
# Breaks a 2x2 Hill cipher via a known-plaintext attack: given a short
# crib assumed to start the message, plus the matching ciphertext, the
# entire key matrix falls out of a single modular matrix inversion --
# K = C * P^-1 (mod 26). No brute force, no scoring, no search: this is
# exact linear algebra, and it's exactly the vulnerability the base Hill
# cipher guide names as this cipher's primary weakness.

A = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'


def clean(text):
    return ''.join(c for c in text.upper() if c in A)


def prepare_text(text):
    return text + 'X' if len(text) % 2 != 0 else text


def mod(n, m):
    return n % m


def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y


def mod_inverse(a, m):
    g, x, _ = egcd(a % m, m)
    return x % m if g == 1 else None


def det2(mat):
    return mod(mat[0][0] * mat[1][1] - mat[0][1] * mat[1][0], 26)


def inverse2(mat):
    d = det2(mat)
    inv_d = mod_inverse(d, 26)
    if inv_d is None:
        return None
    adj = [
        [mat[1][1], -mat[0][1]],
        [-mat[1][0], mat[0][0]],
    ]
    return [[mod(v * inv_d, 26) for v in row] for row in adj]


def mat_mul2(a, b):
    return [[mod(sum(a[i][k] * b[k][j] for k in range(2)), 26) for j in range(2)] for i in range(2)]


def mat_vec_mul2(mat, v):
    return [mod(mat[0][0] * v[0] + mat[0][1] * v[1], 26), mod(mat[1][0] * v[0] + mat[1][1] * v[1], 26)]


def hill_encrypt(text, K):
    text = prepare_text(clean(text))
    out = []
    for i in range(0, len(text), 2):
        v = [A.index(text[i]), A.index(text[i + 1])]
        r = mat_vec_mul2(K, v)
        out.append(A[r[0]] + A[r[1]])
    return ''.join(out)


def hill_decrypt(ciphertext, K):
    k_inv = inverse2(K)
    out = []
    for i in range(0, len(ciphertext), 2):
        v = [A.index(ciphertext[i]), A.index(ciphertext[i + 1])]
        r = mat_vec_mul2(k_inv, v)
        out.append(A[r[0]] + A[r[1]])
    return ''.join(out)


# Tries consecutive block pairs from the start of the crib until it finds
# one whose plaintext matrix is invertible mod 26 -- exactly what a
# cryptanalyst does by hand when the first pair happens to be degenerate.
def recover_key(crib, cipher_prefix):
    n_blocks = len(crib) // 2
    if n_blocks < 2:
        return None

    for b in range(n_blocks - 1):
        p1 = [A.index(crib[b * 2]), A.index(crib[b * 2 + 1])]
        p2 = [A.index(crib[b * 2 + 2]), A.index(crib[b * 2 + 3])]
        P = [[p1[0], p2[0]], [p1[1], p2[1]]]
        d = det2(P)
        if mod_inverse(d, 26) is None:
            continue

        c1 = [A.index(cipher_prefix[b * 2]), A.index(cipher_prefix[b * 2 + 1])]
        c2 = [A.index(cipher_prefix[b * 2 + 2]), A.index(cipher_prefix[b * 2 + 3])]
        C = [[c1[0], c2[0]], [c1[1], c2[1]]]

        P_inv = inverse2(P)
        K = mat_mul2(C, P_inv)
        verified = hill_encrypt(crib, K) == cipher_prefix
        return {'K': K, 'P': P, 'C': C, 'P_inv': P_inv, 'det': d, 'block_used': b, 'verified': verified}

    return None


if __name__ == '__main__':
    ciphertext = "MTFRAUMTJPOTLJGKSOMUXNSTGJQUMCSCMTPPDEQNXFCPULYFQIBVTOHDYBNVDEPHRKULSUZGQSXLVRIRIYMJYBMTACPBBSDNMCEIBVYYEAELIOYBKNSORKQUKIJTDNNEHDYBNVDEANNRCDDNLAGRHSJRAUSUKQPBUCHCAKMDTFRNLADNMHVZHLMCWRSCMTPPHTDIULSUQFPBKQIRURYBSRCYQAMEYBKNSOBCYBMUZHTJOVZHTLZUYBEXDNMTFRAUULWWPBOTXQMGSMZGYBHFTYWZEHRVQWHLZBISANTUBVWBDNHLTYULWMHFBSDNSMMEMGWZWLRVUHMHWASMZXMTIFON"
    crib = 'ATTACKATDAWN'

    result = recover_key(crib, ciphertext[:len(crib)])
    print('Recovered key matrix K:', result['K'])
    print('Block pair used (0-indexed):', result['block_used'])
    print('Verified against full crib:', result['verified'])
    print()

    plaintext = hill_decrypt(ciphertext, result['K'])
    print('Recovered plaintext:')
    print(plaintext)

Running this against the same demo ciphertext as the visualizer produces:

Recovered key matrix K: [[3, 2], [5, 1]]
Block pair used (0-indexed): 0
Verified against full crib: True

Recovered plaintext:
ATTACKATDAWNBECAUSEATWOBYTWOKEYMATRIXTURNSEVERYPAIROFPLAINTEXTLETTERSINTOALINEARCOMBINATIONOFTHEKEYSROWSSOKNOWINGJUSTTWOMATCHEDPLAINTEXTANDCIPHERTEXTBLOCKSISENOUGHTOSOLVEFORTHEENTIREKEYBYMATRIXINVERSIONNOSEARCHINGNOGUESSINGJUSTLINEARALGEBRATURNINGTHEATTACKERSKNOWNFRAGMENTINTOTHEFULLSECRETKEYANDFROMTHERETHERESTOFTHEMESSAGEFALLSOPENIMMEDIATELYX

This matches the visualizer’s own result exactly. The trailing X is the same odd-length padding letter the encryption-side visualizer inserts; the original 343-letter message pads out to an even 344.

For Fun: The Same Thing in About 20 Lines

Same spirit as this site’s other golfed bonus sections: not for learning the algorithm from, just a demonstration of how compactly exact linear algebra reduces once there’s no search loop or statistics table to carry along.

A = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
d2 = lambda m: (m[0][0]*m[1][1] - m[0][1]*m[1][0]) % 26
mi = lambda a, n=26: next((x for x in range(1, n) if a*x % n == 1), None)
def i2(m):
    v = mi(d2(m))
    return v and [[m[1][1]*v % 26, -m[0][1]*v % 26], [-m[1][0]*v % 26, m[0][0]*v % 26]]
mm = lambda a, b: [[sum(a[i][k]*b[k][j] for k in range(2)) % 26 for j in range(2)] for i in range(2)]

def run(t, K):
    o = ''
    for i in range(0, len(t), 2):
        v = [A.index(t[i]), A.index(t[i+1])]
        o += A[(K[0][0]*v[0]+K[0][1]*v[1]) % 26] + A[(K[1][0]*v[0]+K[1][1]*v[1]) % 26]
    return o

def crack(crib, cp):
    for b in range(len(crib)//2 - 1):
        P = [[A.index(crib[b*2]), A.index(crib[b*2+2])], [A.index(crib[b*2+1]), A.index(crib[b*2+3])]]
        Pi = i2(P)
        if not Pi:
            continue
        C = [[A.index(cp[b*2]), A.index(cp[b*2+2])], [A.index(cp[b*2+1]), A.index(cp[b*2+3])]]
        return mm(C, Pi)

if __name__ == '__main__':
    ciphertext = "MTFRAUMTJPOTLJGKSOMUXNSTGJQUMCSCMTPPDEQNXFCPULYFQIBVTOHDYBNVDEPHRKULSUZGQSXLVRIRIYMJYBMTACPBBSDNMCEIBVYYEAELIOYBKNSORKQUKIJTDNNEHDYBNVDEANNRCDDNLAGRHSJRAUSUKQPBUCHCAKMDTFRNLADNMHVZHLMCWRSCMTPPHTDIULSUQFPBKQIRURYBSRCYQAMEYBKNSOBCYBMUZHTJOVZHTLZUYBEXDNMTFRAUULWWPBOTXQMGSMZGYBHFTYWZEHRVQWHLZBISANTUBVWBDNHLTYULWMHFBSDNSMMEMGWZWLRVUHMHWASMZXMTIFON"
    crib = 'ATTACKATDAWN'
    K = crack(crib, ciphertext[:len(crib)])
    print('Recovered K:', K)
    print('Verified against full crib:', run(crib, K) == ciphertext[:len(crib)])
    print()
    Ki = i2(K)
    print('Recovered plaintext:')
    print(run(ciphertext, Ki))

Verified to produce byte-for-byte identical output to the readable version above: K = [[3, 2], [5, 1]], full verification against the crib, and the exact same recovered plaintext. run does double duty as both encrypt and decrypt, exactly the way the readable version’s hill_encrypt/hill_decrypt share their inner loop. Pass it K to encrypt or K’s inverse to decrypt, since a Hill cipher’s decryption is just its own encryption formula with the inverse matrix substituted in. crack collapses the readable version’s block-search loop, matrix construction, and final multiplication into one return per candidate block, stopping at the first invertible one. The crib-verification step is left to the caller here rather than folded in. The one-liner is already doing the actual cryptanalytic work (finding and inverting P), and verification is just calling run again.

Interactive Visualizer

Try it above: paste any known-plaintext crib and its matching ciphertext (or use the default). Watch each step of the linear algebra play out: the plaintext and ciphertext matrices, the modular inversion, the final key, and the verification against the rest of the crib before the whole message gets decrypted.

Hill vs. The Other Breakers on This Site

The contrast is the real lesson here. Every other breaker on this site had to reach for search precisely because there was no shortcut. A wrong Caesar shift or a wrong Playfair square doesn’t hand you an equation to solve, only a statistical smell test to run. Hill is the one classical cipher in this whole series where the “attack” is closer to solving homework than searching a haystack.

Limitations of This Attack

This breaker assumes the known plaintext sits at the very start of the message. That’s the most natural real-world case (a known greeting, header, or date), and it’s what keeps the block alignment unambiguous. But a crib known to occur somewhere in the middle of a longer ciphertext, at an unknown offset, would need the attacker to also search over possible alignments before the same matrix inversion could run. Even that search is far cheaper than a full statistical attack: it’s at most a few dozen candidate offsets to try, each one an instant matrix inversion, not a brute-force sweep over a large key space.

It’s also possible, if unlikely, for the linear algebra to fail outright: if the crib is short and every block pair it offers happens to produce a singular matrix (determinant sharing a factor with 26), there’s no invertible pair left to try. The fallback search across successive block pairs makes this rare in practice, since it only takes one invertible pair among however many the crib offers, but it doesn’t guarantee one exists for a sufficiently short or unlucky crib.

It’s also scoped to the site’s established 2×2 key matrix, matching the encryption-side Hill visualizer. The same technique generalizes cleanly to larger n×n matrices: an attacker just needs n known plaintext blocks (n² known letters) forming an invertible n×n matrix rather than 2 blocks forming an invertible 2×2 one. But modular matrix inversion for n > 2 needs general cofactor-expansion machinery this breaker doesn’t implement.

Finally, this is a known-plaintext attack specifically. It says nothing about breaking Hill from ciphertext alone. That’s a genuinely different, much harder problem, closer to the brute-force-plus-statistics approach the Enigma and Playfair breakers use. It’s deliberately out of scope here: the entire point of this post is that known plaintext turns Hill’s cryptanalysis into something categorically easier than every other cipher on this site, not into a variation on the same search theme.

FAQ

Why doesn’t this breaker just search the ciphertext the way the others do?

Because it doesn’t have to. Hill’s encryption is linear, so two known plaintext-ciphertext letter-pairs turn key recovery into a solvable system of equations rather than a best-fit search. Reaching for statistics when an exact algebraic answer exists would be strictly worse: slower, and only ever approximate where the linear algebra is exact.

How many known letters does this attack actually need?

As few as 4 (two 2-letter blocks), provided those two plaintext blocks happen to form an invertible matrix mod 26. In practice a slightly longer crib (8-12 letters, like the visualizer’s default) is worth having anyway, since it lets the recovered key be verified against more than just the two blocks used to derive it.

What if the first two blocks of the crib aren’t invertible?

This breaker automatically tries the next pair of blocks further into the crib, and keeps going until it finds one that is. That’s the same fallback a cryptanalyst working by hand would use. A crib that’s long enough to offer several candidate block pairs is more robust for exactly this reason.

Does this attack work if the plaintext isn’t at the very start of the message?

Not directly. This breaker assumes the crib and the ciphertext are aligned starting from position 0. If the known plaintext instead occurs somewhere in the middle of a longer message at an unknown offset, an attacker would need to search over possible alignments (or use the ciphertext’s block boundaries as a hint) before the same matrix inversion could be applied.

Is a bigger key matrix (3×3 or larger) safe from this kind of attack?

No. The same idea scales directly. An n×n Hill key needs only n known plaintext blocks (n² known letters) forming an invertible matrix to fall to the identical K = C·P⁻¹ solution; bigger matrices just mean more known letters are needed, not a fundamentally harder attack.

References

1. Wikipedia. “Hill cipher” (Cryptanalysis section). Available at: https://en.wikipedia.org/wiki/Hill_cipher

2. Practical Cryptography. “Hill Cipher.” Available at: http://practicalcryptography.com/ciphers/hill-cipher/

3. Singh, Simon. “The Code Book.” Doubleday, 1999.