Case Study 1 — Breaking and Unbreaking a Code: The Inverse Matrix in Cryptography

DataField.Dev

Case Study 1 — Breaking and Unbreaking a Code: The Inverse Matrix in Cryptography

Field: cryptography / computer science. The inverse matrix is the decryption key of the Hill cipher; invertibility mod 26 is exactly the condition that a message can be decoded.

The problem

In 1929 the mathematician Lester Hill published a cipher that was, for its time, genuinely clever: instead of substituting one letter for another (the kind of code you can crack with a frequency table over breakfast), it mixed blocks of letters together using matrix multiplication. The encryption is a linear transformation; the decryption is its inverse. Hill's cipher is a perfect, self-contained illustration of this chapter's thesis — that an invertible matrix is a reversible transformation and its inverse is the undo — with one beautiful twist: the arithmetic happens not over the real numbers but over the integers modulo 26, the size of the alphabet. That twist sharpens the invertibility question into something you can hold in your hand: exactly which key matrices can be decoded?

We turn each letter into a number, A = 0 through Z = 25. To encrypt with a $2\times 2$ key matrix $K$, we group the plaintext into pairs, treat each pair as a column vector $\mathbf{p}$, and compute the ciphertext vector $$\mathbf{c} = K\mathbf{p} \bmod 26.$$ Every pair of letters is transformed by the same matrix $K$ — exactly as every point of the plane was transformed by the same matrix in Chapter 7, and every pixel by the same color matrix in §9.5. To decrypt, we must undo the transformation: recover $\mathbf{p}$ from $\mathbf{c}$. And undoing a matrix transformation is precisely what $K^{-1}$ does: $$\mathbf{p} = K^{-1}\mathbf{c} \bmod 26.$$ The decryption key is the inverse matrix. If $K$ has no inverse (mod 26), the cipher is undecodable — a useless code that scrambles messages beyond recovery, the cryptographic version of Figure 9.2's irreversible collapse.

Encrypting a message

Take Hill's classic key $$K = \begin{bmatrix} 3 & 3 \\ 2 & 5 \end{bmatrix},$$ and encrypt the word HELP. Numerically, H = 7, E = 4, L = 11, P = 15, so our two column vectors are $\mathbf{p}_1 = (7, 4)$ and $\mathbf{p}_2 = (11, 15)$. Apply $K$ as a weighted sum of columns (Chapter 7) and reduce mod 26: $$K\mathbf{p}_1 = 7\begin{bmatrix}3\\2\end{bmatrix} + 4\begin{bmatrix}3\\5\end{bmatrix} = \begin{bmatrix}21 + 12\\14 + 20\end{bmatrix} = \begin{bmatrix}33\\34\end{bmatrix} \equiv \begin{bmatrix}7\\8\end{bmatrix} \pmod{26},$$ which is (7, 8) = HI. Likewise $K\mathbf{p}_2 = (11\cdot 3 + 15\cdot 3,\ 11\cdot 2 + 15\cdot 5) = (78, 97) \equiv (0, 19) = $ AT. So HELP encrypts to HIAT — and notice the two L's in the plaintext have vanished into different letters, which is exactly why block ciphers resist frequency analysis: the same letter encrypts differently depending on its partner.

# Hill cipher encryption: c = K p (mod 26).
import numpy as np, string
alphabet = string.ascii_uppercase
to_num   = lambda s: [alphabet.index(ch) for ch in s]
to_text  = lambda v: "".join(alphabet[int(x) % 26] for x in v)

K = np.array([[3, 3], [2, 5]])
plain = "HELP"
pairs = [to_num(plain)[i:i+2] for i in range(0, len(plain), 2)]
cipher = [ (K @ np.array(p)) % 26 for p in pairs ]
print("ciphertext:", "".join(to_text(c) for c in cipher))

ciphertext: HIAT

Decrypting: the inverse matrix, modulo 26

To read HIAT back, we need $K^{-1} \bmod 26$. Over the real numbers, the $2\times 2$ shortcut from §9.5 gives $K^{-1} = \frac{1}{\det K}\begin{bmatrix}5 & -3 \\ -2 & 3\end{bmatrix}$, with $\det K = 3\cdot 5 - 3\cdot 2 = 9$. But we're working mod 26, so "divide by 9" must become "multiply by the modular inverse of 9 mod 26" — the number $d^{-1}$ with $9 \cdot d^{-1} \equiv 1 \pmod{26}$. A quick search (or the extended Euclidean algorithm) finds $9 \cdot 3 = 27 \equiv 1 \pmod{26}$, so the modular inverse of the determinant is $3$. Then $$K^{-1} \equiv 3\begin{bmatrix}5 & -3 \\ -2 & 3\end{bmatrix} = \begin{bmatrix}15 & -9 \\ -6 & 9\end{bmatrix} \equiv \begin{bmatrix}15 & 17 \\ 20 & 9\end{bmatrix} \pmod{26},$$ using $-9 \equiv 17$ and $-6 \equiv 20$ (mod 26). This is the decryption key. Apply it to the ciphertext pair $\mathbf{c}_1 = (7, 8)$: $$K^{-1}\mathbf{c}_1 = 7\begin{bmatrix}15\\20\end{bmatrix} + 8\begin{bmatrix}17\\9\end{bmatrix} = \begin{bmatrix}105 + 136\\140 + 72\end{bmatrix} = \begin{bmatrix}241\\212\end{bmatrix} \equiv \begin{bmatrix}7\\4\end{bmatrix} \pmod{26} = \text{HE}.$$ The H and E are back. The crucial sanity check is that $K^{-1}K \equiv I \pmod{26}$ — the inverse really undoes the key, just as $A^{-1}A = I$ in the body of the chapter, only now the identity emerges after the mod:

# Decryption via the modular inverse matrix; verify K^{-1} K = I (mod 26).
import numpy as np, string
alphabet = string.ascii_uppercase
to_text  = lambda v: "".join(alphabet[int(x) % 26] for x in v)

K    = np.array([[3, 3], [2, 5]])
Kinv = np.array([[15, 17], [20, 9]])           # 3 * adjugate, reduced mod 26
print("K^{-1} K mod 26 =\n", (Kinv @ K) % 26)   # the identity
cipher = [np.array([7, 8]), np.array([0, 19])]  # HI, AT
recovered = "".join(to_text((Kinv @ c) % 26) for c in cipher)
print("decrypted:", recovered)

K^{-1} K mod 26 =
 [[1 0]
 [0 1]]
decrypted: HELP

$K^{-1}K$ comes back as the identity modulo 26, and HIAT decrypts cleanly to HELP. The whole cipher is the round trip $K^{-1}(K\mathbf{p}) = \mathbf{p}$ — encrypt then decrypt is the do-nothing transformation, which is the chapter's defining equation $A^{-1}A = I$ in cryptographic costume.

When does a Hill key work? Invertibility, sharpened

Here is where the case study earns its place in this chapter. Not every matrix is a usable Hill key. Decryption requires $K^{-1} \bmod 26$ to exist, and the $2\times 2$ shortcut shows the obstruction: you must divide by $\det K$, so $\det K$ must have a modular inverse mod 26. A number has a modular inverse mod 26 if and only if it is coprime to 26 (shares no factor with $26 = 2 \times 13$). So the precise condition is:

$$K \text{ is a usable Hill key} \iff \gcd(\det K,\ 26) = 1.$$

This is the chapter's invertibility story, transplanted to modular arithmetic. Over the reals, $A$ is invertible iff $\det(A) \neq 0$. Over $\mathbb{Z}_{26}$, $K$ is invertible iff $\det(K)$ is a unit — coprime to 26. The role of "nonzero" is played by "coprime to the modulus." A key with even determinant, or determinant divisible by 13, is singular mod 26: it collapses the space of letter-pairs onto a smaller set, mashing distinct plaintexts onto the same ciphertext, and no decryption key can pull them apart — the modular echo of Figure 9.2's flattened square.

# Which 2x2 keys are usable mod 26? Need gcd(det, 26) = 1.
import numpy as np
from math import gcd
for K in [[[3, 3], [2, 5]], [[2, 4], [1, 3]], [[1, 2], [3, 4]]]:
    det = int(round(np.linalg.det(np.array(K)))) % 26
    ok  = gcd(det, 26) == 1
    print(K, " det mod 26 =", det, " usable:", ok)

[[3, 3], [2, 5]]  det mod 26 = 9  usable: True
[[2, 4], [1, 3]]  det mod 26 = 2  usable: False
[[1, 2], [3, 4]]  det mod 26 = 24  usable: False

Only the first key is usable: its determinant 9 is coprime to 26. The second has determinant 2 (shares the factor 2 with 26) and the third has determinant 24 (also even) — both singular mod 26, both undecodable. An honest aside on the cryptography itself: the Hill cipher is not secure by modern standards — it is linear, so an attacker who obtains a few plaintext-ciphertext pairs can recover the key by solving a linear system (using, fittingly, a matrix inverse). Its value today is pedagogical, and it is one of the cleanest demonstrations anywhere that the inverse matrix is the undo, and invertibility is the precise condition for reversibility — whether your scalars live in $\mathbb{R}$ or in $\mathbb{Z}_{26}$.

The takeaway

The Hill cipher makes three of the chapter's ideas tangible. Encryption is a linear transformation ($\mathbf{c} = K\mathbf{p}$), so the same matrix moves every block. Decryption is the inverse transformation ($\mathbf{p} = K^{-1}\mathbf{c}$), the literal rewind, satisfying $K^{-1}K = I$. And invertibility is the gatekeeper — a key works exactly when it is invertible (here, mod 26: $\gcd(\det K, 26) = 1$), the modular reincarnation of $\det \neq 0$. The next time you read that "the determinant must be coprime to the modulus," hear it for what it is: the Invertible Matrix Theorem, speaking the language of number theory. And the next time you see a matrix inverse used to break a cipher, remember that breaking and unbreaking are the same operation — applying $K^{-1}$ — which is the whole point of an inverse.