Chapter 2 — Matrices & the Hill Cipher

Chapter 1 ended with a conviction: any cipher that touches bytes one at a time is just a renaming. The fix is to mix several symbols in one stroke — and the mathematical machine for “combine several numbers at once, reversibly” is the matrix.

This chapter builds matrix arithmetic over \(\mathbb{Z}_n\), constructs the Hill cipher (1929 — the first cipher designed with algebra rather than gadgets), lets the lab’s instruments condemn it, and then breaks it outright with two blocks of known plaintext. The same objects return later as AES’s MixColumns step (Chapter 3) and as the lattices inside ML-KEM (Chapter 6).

You’ll need: Chapter 1’s mod_inverse. Nothing about matrices is assumed.

2.1 Vectors, Matrices, and Mixing

A vector is a column of numbers; a matrix is a grid. The product \(K\vec{p}\) combines every entry of \(\vec{p}\) into every entry of the result — each output is a weighted sum of all inputs:

\[ K\vec{p} \;=\; \begin{pmatrix} 3 & 2 \\ 7 & 5 \end{pmatrix} \begin{pmatrix} 8 \\ 1 \end{pmatrix} = \begin{pmatrix} 3\cdot 8 + 2\cdot 1 \\ 7\cdot 8 + 5\cdot 1 \end{pmatrix} = \begin{pmatrix} 26 \\ 61 \end{pmatrix} \equiv \begin{pmatrix} 0 \\ 9 \end{pmatrix} \pmod{26} \]

That last step is the only new ingredient: we do ordinary matrix arithmetic, then reduce every entry mod \(n\). Code it both ways — honest loops first, then numpy:

def mat_vec_mod(K, p, n):
    '''K (list of rows) times vector p, every entry reduced mod n.'''
    return [sum(K[i][j] * p[j] for j in range(len(p))) % n for i in range(len(K))]

def mat_mul_mod(A, B, n):
    '''Matrix product A·B mod n.'''
    return [[sum(A[i][k] * B[k][j] for k in range(len(B))) % n
             for j in range(len(B[0]))] for i in range(len(A))]

K = [[3, 2],
     [7, 5]]
print("K·(8,1) mod 26 =", mat_vec_mod(K, [8, 1], 26))   # matches the math above

import numpy as np
Kn = np.array(K)
print("numpy agrees   :", (Kn @ np.array([8, 1])) % 26)
K·(8,1) mod 26 = [0, 9]
numpy agrees   : [0 9]

2.2 Undoing a Matrix: Determinants mod n

Encryption with \(K\) is only useful if some \(K^{-1}\) undoes it: \(K^{-1}K \equiv I \pmod n\), where \(I\) is the identity matrix (1s on the diagonal — the “multiply by 1” of the matrix world).

For a \(2\times 2\) matrix the classical formula is

\[ K = \begin{pmatrix} a & b \\ c & d \end{pmatrix}, \qquad K^{-1} = \det(K)^{-1} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}, \qquad \det(K) = ad - bc \]

Over the reals you need \(\det(K) \neq 0\). Over \(\mathbb{Z}_n\) the requirement is stronger and should look familiar from Chapter 1: \(\det(K)\) must have a multiplicative inverse mod \(n\), i.e. \(\gcd(\det K, n) = 1\). The whole matrix inverts exactly when one ordinary number does.

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

def mod_inverse(a, n):
    g, x, _ = extended_gcd(a % n, n)
    if g != 1:
        raise ValueError(f"{a} has no inverse mod {n} (gcd = {g})")
    return x % n

def mat_det2(K):
    return K[0][0] * K[1][1] - K[0][1] * K[1][0]

def mat_inv2_mod(K, n):
    '''Inverse of a 2x2 matrix mod n (raises if det not invertible).'''
    d_inv = mod_inverse(mat_det2(K), n)
    a, b, c, d = K[0][0], K[0][1], K[1][0], K[1][1]
    return [[(d_inv * d) % n, (d_inv * -b) % n],
            [(d_inv * -c) % n, (d_inv * a) % n]]

K_inv = mat_inv2_mod(K, 26)
print("K⁻¹ mod 26      =", K_inv)
print("K⁻¹·K mod 26    =", mat_mul_mod(K_inv, K, 26), "  <- identity, as required")
K⁻¹ mod 26      = [[5, 24], [19, 3]]
K⁻¹·K mod 26    = [[1, 0], [0, 1]]   <- identity, as required

2.3 The Hill Cipher

Lester Hill’s 1929 idea: chop the message into blocks of \(m\) symbols and encrypt each block as a vector:

\[E(\vec{p}) = K\vec{p} \bmod n \qquad D(\vec{c}) = K^{-1}\vec{c} \bmod n\]

This is a genuine block cipher — the first ever designed algebraically. Each ciphertext byte depends on every byte of its block, which already beats everything in Chapter 1.

Over bytes (\(n = 256 = 2^8\)), \(\gcd(\det K, 256) = 1\) just means \(\det K\) must be odd. We force that when deriving the key matrix from key bytes: making both diagonal entries odd and one off-diagonal entry even guarantees \(ad - bc\) = odd − even = odd. As a lab specimen:

import os
from lib.notebook import algorithm, with_key, AlgorithmContext, quick_test

KEY = os.urandom(4)

def key_matrix(key: bytes):
    '''2x2 key matrix with guaranteed-odd determinant (ad odd, bc even).'''
    return [[key[0] | 1, key[1] & 0xFE],
            [key[2],     key[3] | 1]]

@algorithm("Hill-2x2")
@with_key(KEY)
class Hill:
    '''Hill cipher over bytes: 2-byte blocks, E(p) = K·p mod 256.'''

    BLOCK = 2

    def encrypt(self, data: bytes, ctx: AlgorithmContext) -> bytes:
        K_ = key_matrix(ctx.key)
        if len(data) % self.BLOCK:                       # pad to block size
            data = data + bytes(self.BLOCK - len(data) % self.BLOCK)
        out = bytearray()
        for i in range(0, len(data), self.BLOCK):
            out += bytes(mat_vec_mod(K_, list(data[i:i + self.BLOCK]), 256))
        return bytes(out)

    def decrypt(self, data: bytes, ctx: AlgorithmContext) -> bytes:
        K_inv_ = mat_inv2_mod(key_matrix(ctx.key), 256)
        out = bytearray()
        for i in range(0, len(data), self.BLOCK):
            out += bytes(mat_vec_mod(K_inv_, list(data[i:i + self.BLOCK]), 256))
        return bytes(out)

quick_test(Hill())
Testing: Hill-2x2
Input: b'Hello, PyCryption!'
----------------------------------------
Encrypt: <AlgorithmResult: 18 bytes, 0.031ms>
Decrypt: <AlgorithmResult: 18 bytes, 0.027ms>
Round-trip successful!

2.4 Lab Tie-In: a Better Cipher, Still Condemned

Bytes now influence each other within a block — progress. But blocks don’t influence each other, and the map is linear, which the instruments will expose:

  • ECB canary: identical plaintext blocks → identical ciphertext blocks. Worse, \(K \cdot \vec{0} = \vec{0}\): a run of zero bytes encrypts to zero bytes. Linear maps can’t hide the zero vector.
  • Avalanche: flipping one plaintext bit changes only its own 2-byte block — about \(\tfrac{8}{8192} \approx 0.1\%\) of a 1 KB ciphertext, when ~50% is healthy.
from lib.notebook import analyze_output, ecb_canary, adapt
from lib.algorithms import Aes256GcmAlgorithm

hill = Hill()
aes = adapt(Aes256GcmAlgorithm, os.urandom(32), name="AES-256-GCM")

print("Hill encrypts 8 zero bytes to:", hill.encrypt(bytes(8)).output.hex(), " <- linearity leaks!")
print()
canary = ecb_canary(hill)
print(f"ECB canary: {canary['duplicate_blocks']} duplicate blocks out of {canary['blocks_scanned']} scanned")
panel = analyze_output(hill, sample_size=4096, trials=8)
print("Hill verdict:", panel["flags"], f"(avalanche {panel['avalanche_pct']}%)")
panel = analyze_output(aes, sample_size=4096, trials=8)
print("AES  verdict:", panel["flags"] or "CLEAN", f"(avalanche {panel['avalanche_pct']}%)")
Hill encrypts 8 zero bytes to: 0000000000000000  <- linearity leaks!

ECB canary: 63 duplicate blocks out of 64 scanned
Hill verdict: ['weak-avalanche', 'ecb-pattern'] (avalanche 0.08%)
AES  verdict: CLEAN (avalanche 49.83%)

2.5 Breaking It: the Known-Plaintext Attack

Here is the deeper lesson, and it’s the reason modern ciphers are aggressively non-linear. Because encryption is a matrix product, the key satisfies a linear equation an attacker can solve.

Stack two plaintext blocks as the columns of a matrix \(P\), their ciphertext blocks as columns of \(C\). Then

\[C = K P \pmod{256} \quad\Longrightarrow\quad K = C P^{-1} \pmod{256}\]

If the attacker knows (or guesses — headers, greetings, file magic bytes) two plaintext blocks whose matrix \(P\) is invertible, the key falls out by arithmetic. No search, no luck:

# Attacker knows two plaintext blocks and observes their ciphertexts.
p_blocks = [[3, 7], [2, 5]]                       # plaintext blocks (det of P is odd)
ct = hill.encrypt(bytes(p_blocks[0]) + bytes(p_blocks[1])).output
c_blocks = [list(ct[0:2]), list(ct[2:4])]

# Stack blocks as COLUMNS: P[i][j] = j-th block's i-th entry
P = [[p_blocks[0][0], p_blocks[1][0]], [p_blocks[0][1], p_blocks[1][1]]]
C = [[c_blocks[0][0], c_blocks[1][0]], [c_blocks[0][1], c_blocks[1][1]]]

K_recovered = mat_mul_mod(C, mat_inv2_mod(P, 256), 256)
K_actual = key_matrix(KEY)
print("recovered key matrix:", K_recovered)
print("actual key matrix   :", K_actual)
assert K_recovered == K_actual
print("\n4 bytes of known plaintext = total key recovery. Linearity is fatal.")
recovered key matrix: [[59, 64], [147, 215]]
actual key matrix   : [[59, 64], [147, 215]]

4 bytes of known plaintext = total key recovery. Linearity is fatal.

Exercises

NoteExercise 1 — Multiply by hand

Compute \(\begin{pmatrix} 2 & 1 \\ 3 & 4 \end{pmatrix}\begin{pmatrix} 5 \\ 6 \end{pmatrix} \bmod 26\) by hand, then verify with mat_vec_mod.

Top: \(2\cdot5 + 1\cdot6 = 16\). Bottom: \(3\cdot5 + 4\cdot6 = 39 \equiv 13 \pmod{26}\). Result: \((16, 13)\).

NoteExercise 2 — Invertibility census

Which of these are invertible mod 26? \(A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}\), \(B = \begin{pmatrix} 3 & 1 \\ 4 & 2 \end{pmatrix}\), \(C = \begin{pmatrix} 5 & 1 \\ 2 & 3 \end{pmatrix}\). (Compute each determinant, then ask: \(\gcd(\det, 26) = 1\)?)

\(\det A = -2 \equiv 24\): \(\gcd(24, 26) = 2\) — not invertible. \(\det B = 2\): \(\gcd(2,26)=2\) — not invertible. \(\det C = 13\): \(\gcd(13, 26) = 13\) — not invertible! All three fail; mod 26 is a minefield because 26 = 2·13. (This is why working mod a prime — or forcing odd determinants mod 256 — makes life easier.)

NoteExercise 3 — Run the attack yourself

Re-run the known-plaintext attack with different plaintext blocks of your choosing. When does it fail? (Try blocks whose matrix \(P\) has an even determinant.)

The attack needs \(P\) invertible mod 256, i.e. \(\det P\) odd. Blocks like \((2,4)\) and \((6,8)\) give an even determinant and mat_inv2_mod raises — the attacker just picks a different pair of known blocks. In practice messages contain plenty.

# --- Self-check: run me. All asserts should pass silently. -------------
assert mat_vec_mod([[2, 1], [3, 4]], [5, 6], 26) == [16, 13]        # Exercise 1

for M, invertible in [([[1, 2], [3, 4]], False),                     # Exercise 2
                      ([[3, 1], [4, 2]], False),
                      ([[5, 1], [2, 3]], False)]:
    g, _, _ = extended_gcd(mat_det2(M) % 26, 26)
    assert (g == 1) == invertible

bad_P = [[2, 6], [4, 8]]                                             # Exercise 3
try:
    mat_inv2_mod(bad_P, 256)
    assert False, "even determinant should not invert mod 256"
except ValueError:
    pass
print("✓ all self-checks passed")
✓ all self-checks passed

Where Matrices Go Next

The Hill cipher died of linearity, but its skeleton is everywhere in modern cryptography:

  • AES (Chapter 3) keeps a matrix multiplication as its MixColumns step — over the finite field \(GF(2^8)\) instead of \(\mathbb{Z}_{256}\) — but sandwiches it between non-linear S-boxes so the known-plaintext attack has nothing linear to solve.
  • Lattices (Chapter 6) are the set of integer combinations of a matrix’s columns. ML-KEM — the post-quantum specimen you’ve already benchmarked in this lab — hides secrets by adding noise to a matrix equation \(A\vec{s} + \vec{e}\), turning easy linear algebra into a problem believed hard even for quantum computers.

Same objects, two destinies: matrices alone are breakable; matrices plus non-linearity (or noise) run the modern world.

Next: Chapter 3 — Groups, Rings & Finite Fields (in progress).

Back to top