Project 22: Matrix Cipher Encoder

A self-contained deep-dive from the canonical Math from Foundations to Machine Learning curriculum.

  • Difficulty: Intermediate
  • Time: 1-2 weeks
  • Language: Python
  • Prerequisites: Projects 10 and 20
  • Source: HS P06

What You Will Build

Build a Hill-cipher-style educational encoder that turns text blocks into numeric vectors, multiplies them by a key matrix modulo an alphabet size, and reverses the process with a modular matrix inverse. The program must generate or accept keys, reject keys that cannot be inverted in the chosen modulus, preserve a documented policy for spaces and punctuation, pad incomplete blocks, and show the numeric work for at least one block. Include a key-analysis command reporting determinant, greatest common divisor, modular inverse, and round-trip status. This is not presented as secure modern cryptography; its purpose is to make matrix invertibility, modular arithmetic, and reversible transformations concrete.

Real World Outcome

Running the CLI on MEET AT NINE produces ciphertext, a block-by-block transformation trace, and a successful decrypted message. Supplying a bad key produces a precise diagnostic such as “determinant 6 shares factor 2 with modulus 26; no inverse exists” instead of corrupt output.

Core Question

What exact mathematical property makes a matrix transformation reversible when arithmetic wraps around a finite alphabet?

Concepts You Must Understand First

  1. Modular arithmetic: addition and multiplication occur in residue classes. Revisit Project 10 and modular inverse via the extended Euclidean algorithm.
  2. Determinants and invertibility: over modulus m, nonzero determinant is insufficient; gcd(det(K), m) must equal 1.
  3. Matrix-vector multiplication: text blocks must follow one consistent row- or column-vector convention. See Lay et al., Linear Algebra and Its Applications.
  4. Adjugate inverse in 2D: for a small matrix, multiply the adjugate by the modular inverse of its determinant.
  5. Encoding contracts: alphabet, case folding, padding, and unsupported characters must be deterministic.

Build Milestones

  1. Define a text-to-number mapping and prove its round trip independently of encryption.
  2. Encrypt fixed-size blocks with a 2x2 key and display every intermediate vector.
  3. Implement determinant and modular inverse checks, then derive the inverse key matrix.
  4. Decode arbitrary-length messages with deterministic padding removal and punctuation policy.
  5. Add seeded key generation plus property tests over many valid messages and keys.

Hints in Layers

  1. Begin with alphabet size 26 and a known invertible key; verify one block by hand.
  2. Normalize every intermediate matrix entry modulo m, including negative values in the inverse.
  3. Generate candidates until the determinant is coprime to m; never assume a random matrix is usable.

Common Pitfalls and Debugging

  • Symptom: encryption works but decryption returns nonsense. Cause: key determinant has no modular inverse or vector orientation changed. Fix: print K_inv @ K mod m and require identity before accepting the key.
  • Symptom: only some messages round-trip. Cause: padding or punctuation handling is ambiguous. Fix: specify an encoded length or reversible escape policy and test boundary-sized messages.
  • Symptom: inverse entries are negative or too large. Cause: ordinary inverse arithmetic leaked into modular arithmetic. Fix: reduce every result modulo the alphabet size.

Definition of Done

  • Valid keys satisfy K_inv @ K ≡ I (mod m) in tests.
  • Invalid keys are rejected with determinant and gcd diagnostics.
  • Empty, short, exact-block, and multi-block messages behave deterministically.
  • The CLI shows one transparent numerical encryption/decryption trace.
  • At least 100 seeded property cases round-trip correctly.
  • Documentation states clearly why this historical cipher is not secure today.

Previous: Project 21 · Complete learning path · Next: Project 23