Hill Cipher — a linear block cipher that known-plaintext breaks in one matrix inversion

Hill cipher encrypts fixed-size blocks as c = K·p mod m for an n×n matrix key K over Z_m; because encryption is a linear map, n independent known plaintext/ciphertext vector pairs are enough to solve for K directly — no brute force, no statistical cryptanalysis.

The signal that betrays it

- Fixed-size numeric or letter blocks, block length n almost always 2 or 3 in CTF challenges (bigger n makes hand-verification and challenge design harder for the author, so it's rare). - The challenge hands you (or names) a "key matrix," gives the key as a list of lists / 2D array, or the prompt literally says "Hill cipher." - Ciphertext is visibly a linear function of plaintext mod m — no S-boxes, no non-linear mixing, usually m = 26 for letter ciphers but can be 256 or another modulus for byte-oriented variants. - Decryption talk in the challenge/source revolves around a determinant, a modular inverse, or "invertibility" of the key — that vocabulary is specific to matrix ciphers and is a strong tell on its own.

Known-plaintext attack (the whole game)

collect n linearly-independent plaintext vectors as the columns of an n×n matrix P, and the matching ciphertext vectors as the columns of C. Then

`` K = C · P⁻¹ mod m ``

recovers the key matrix in one step — no search, no guessing. This is the textbook weakness of the cipher: with n² known plaintext/ciphertext character pairs (n² unknowns in K, n² equations), the linear system is fully determined and (usually) solvable by standard linear algebra.

Requirement, and the one thing that trips people up

P itself must be invertible mod m, i.e. gcd(det P, m) = 1. If the known-plaintext blocks you happened to be given are linearly dependent mod m, P⁻¹ does not exist and the attack silently fails (or crashes) — the fix is not a smarter algorithm, it's picking a different set of n known plaintext blocks (or, if you control the plaintext, choosing blocks you know in advance are independent, e.g. the standard basis vectors, which makes K fall out of C directly with zero computation).

Decrypting once you have (or recovered) K

compute K⁻¹ mod m via the adjugate/cofactor matrix and the modular inverse of det(K), rather than fighting with fraction-based Gaussian elimination. Field-tested implementation:

```python from sympy import Matrix

def mat_inv_mod(K, m): K = Matrix(K) det = int(K.det()) % m di = pow(det, -1, m) # modular inverse of the determinant adj = K.adjugate() return [[(di * int(adj[i, j])) % m for j in range(K.shape[1])] for i in range(K.shape[0])]

def recover_key(P, C, m): # P, C: n x n known pairs, columns = vectors Pinv = Matrix(mat_inv_mod(P, m)) return [[int(x) % m for x in row] for row in (Matrix(C) * Pinv)] ```

When det is not invertible mod m (gcd(det, m) != 1 — with the common m = 26, this means det is even or a multiple of 13): two field-tested ways forward, in order of how often each fixes it — 1. Swap in a different set of n known plaintext blocks and recompute; most of the time another combination of known pairs gives an invertible P. 2. If that's not possible (fixed, limited known-plaintext), factor m into coprime prime-power components and solve the linear system independently mod each factor, then recombine the per-factor solutions with Chinese Remainder Theorem — recombining residues across coprime moduli.

What does NOT work

- Brute-forcing the key matrix. For m = 26, n = 3 the keyspace is on the order of 26⁹ — far outside CTF time budgets, and completely unnecessary: the linear-algebra recovery above is exact and instant once you have n independent pairs. Reaching for brute force here is a sign you haven't recognized the cipher as linear yet. - Computing a matrix inverse mod m without checking invertibility first. Standard inverse routines will either throw or silently return garbage if gcd(det P, m) != 1 — always check the gcd before trusting the recovered K, rather than debugging a wrong key downstream. - Treating it like a substitution or transposition cipher. Frequency analysis and hill-climbing on n-gram statistics are the right tools for Permutation Cipher — frequencies survive intact, only position is scrambled and Substitution & Shift Cipher — recovered by letter-frequency, not by algebra, but Hill cipher's block is mixed by matrix multiplication, not a fixed letter mapping or reordering — those statistical methods don't recover K directly. They can still be useful indirectly, to guess a plausible plaintext crib that then seeds the known-plaintext pairs the linear attack needs, but that's a different role than in a pure substitution cipher.

Related: Permutation Cipher — frequencies survive intact, only position is scrambled Substitution & Shift Cipher — recovered by letter-frequency, not by algebra Chinese Remainder Theorem — recombining residues across coprime moduli Linear Algebra over GF(2) — solving bit-level unknowns as a linear system mod 2