Chapter 1 — Modular Arithmetic

Every cipher in this lab — from the Caesar wheel to ML-KEM — is arithmetic in a finite world: numbers that wrap around instead of growing forever. This chapter builds that world from scratch.

You’ll need: comfort with variables and exponents. You’ll leave with: congruences, modular inverses, and two working ciphers that the lab’s own instruments will judge (spoiler: harshly).

This is the mathematics companion to the General Cryptography concept tour. Concepts there, mechanics here.

1.1 Wrap-Around Arithmetic

A clock answers “what time is it 5 hours after 10:00?” with 3:00, not 15:00. That’s arithmetic modulo 12.

We write

\[a \equiv b \pmod{n}\]

read “a is congruent to b mod n”, meaning \(a\) and \(b\) leave the same remainder when divided by \(n\). So \(15 \equiv 3 \pmod{12}\), and \(26 \equiv 0 \pmod{26}\).

Python’s % operator computes remainders — with one pleasant guarantee: the result always lands in \(\{0, 1, \dots, n-1\}\), even for negative numbers.

print(15 % 12)    # 5 hours after 10:00
print(26 % 26)    # a full alphabet wraps to the start
print(-3 % 26)    # Python keeps remainders non-negative: -3 ≡ 23 (mod 26)
print((17 + 20) % 26, (17 * 20) % 26)  # add and multiply, then reduce
3
0
23
11 2

The crucial property: you can reduce before or after arithmetic and get the same answer.

\[(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n\]

That means the finite set \(\mathbb{Z}_n = \{0, 1, \dots, n-1\}\) is closed: add or multiply any two members, reduce, and you’re still inside. A finite, self-contained number system — exactly what a cipher needs, because messages are finite.

1.2 The Caesar Cipher: Addition mod 26 (or 256)

The oldest cipher in the book shifts every letter by a fixed key \(k\):

\[E(x) = (x + k) \bmod 26 \qquad D(y) = (y - k) \bmod 26\]

Computers don’t deal in 26 letters but in bytes — an “alphabet” of 256 symbols. Same math, bigger alphabet. Let’s build it as a real lab specimen:

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

@algorithm("Caesar-256")
@with_key(bytes([77]))   # the shift key: k = 77
class Caesar:
    '''E(x) = x + k mod 256, byte by byte.'''

    def encrypt(self, data: bytes, ctx: AlgorithmContext) -> bytes:
        k = ctx.key[0]
        return bytes((b + k) % 256 for b in data)

    def decrypt(self, data: bytes, ctx: AlgorithmContext) -> bytes:
        k = ctx.key[0]
        return bytes((b - k) % 256 for b in data)

quick_test(Caesar())
Testing: Caesar-256
Input: b'Hello, PyCryption!'
----------------------------------------
Encrypt: <AlgorithmResult: 18 bytes, 0.013ms>
Decrypt: <AlgorithmResult: 18 bytes, 0.005ms>
Round-trip successful!

Round-trips fine. Security-wise it’s a disaster — only 256 possible keys, so an attacker tries them all in a microsecond. But it establishes the pattern: encryption is invertible arithmetic in \(\mathbb{Z}_n\). Subtraction undoes addition.

1.3 The Division Problem

What undoes multiplication? If \(E(x) = a \cdot x \bmod 26\), decryption needs to “divide by \(a\)” — but there’s no division in \(\mathbb{Z}_n\). What we need is a multiplicative inverse: a number \(a^{-1}\) with

\[a \cdot a^{-1} \equiv 1 \pmod{n}\]

Then “dividing by \(a\)” is just multiplying by \(a^{-1}\). Try to find one for \(a = 3, n = 26\) by brute force: \(3 \cdot 9 = 27 \equiv 1\). So \(3^{-1} = 9\) in \(\mathbb{Z}_{26}\).

Now try \(a = 13\): the multiples of 13 mod 26 are \(\{0, 13, 0, 13, \dots\}\) — it never hits 1. An inverse exists exactly when \(\gcd(a, n) = 1\) (when \(a\) and \(n\) share no factor). The numbers coprime to \(n\) are the “usable” multipliers.

The extended Euclidean algorithm finds both \(\gcd(a,n)\) and the inverse in one pass — it runs in microseconds even for 2048-bit RSA numbers:

def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    '''Return (g, x, y) such that a*x + b*y = g = 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: int, n: int) -> int:
    '''Return a^-1 mod n. Raises if gcd(a, n) != 1.'''
    g, x, _ = extended_gcd(a % n, n)
    if g != 1:
        raise ValueError(f"{a} has no inverse mod {n} (gcd = {g})")
    return x % n

print("3⁻¹  mod 26 =", mod_inverse(3, 26))
print("7⁻¹  mod 26 =", mod_inverse(7, 26), "   check:", (7 * mod_inverse(7, 26)) % 26)
try:
    mod_inverse(13, 26)
except ValueError as e:
    print("13:", e)
3⁻¹  mod 26 = 9
7⁻¹  mod 26 = 15    check: 1
13: 13 has no inverse mod 26 (gcd = 13)

Fermat’s Little Theorem (a one-line miracle)

When \(n = p\) is prime, every nonzero \(a\) is coprime to \(p\), and Fermat’s little theorem says

\[a^{p-1} \equiv 1 \pmod{p}\]

Multiply both sides by \(a^{-1}\) and you get a formula for the inverse: \(a^{-1} \equiv a^{p-2} \pmod p\). This identity is the engine inside RSA and Diffie–Hellman (Chapter 4). We won’t prove it — but we can interrogate it numerically:

p = 65537  # a prime you'll meet again: the standard RSA public exponent
for a in [2, 3, 1234, 65536]:
    print(f"{a}^(p-1) mod p = {pow(a, p - 1, p)}", "   inverse via Fermat:", pow(a, p - 2, p) == mod_inverse(a, p))
2^(p-1) mod p = 1    inverse via Fermat: True
3^(p-1) mod p = 1    inverse via Fermat: True
1234^(p-1) mod p = 1    inverse via Fermat: True
65536^(p-1) mod p = 1    inverse via Fermat: True

1.4 The Affine Cipher: Multiply and Shift

With inverses in hand we can afford a multiplicative key. The affine cipher uses key \((a, b)\) with \(\gcd(a, n) = 1\):

\[E(x) = (a \cdot x + b) \bmod n \qquad D(y) = a^{-1} \cdot (y - b) \bmod n\]

Over bytes, \(n = 256 = 2^8\), so \(\gcd(a, 256) = 1\) simply means \(a\) must be odd. Build it:

import os

KEY = os.urandom(2)

@algorithm("Affine-256")
@with_key(KEY)
class Affine:
    '''E(x) = a*x + b mod 256; a forced odd so the inverse exists.'''

    def encrypt(self, data: bytes, ctx: AlgorithmContext) -> bytes:
        a, b = ctx.key[0] | 1, ctx.key[1]
        return bytes((a * x + b) % 256 for x in data)

    def decrypt(self, data: bytes, ctx: AlgorithmContext) -> bytes:
        a, b = ctx.key[0] | 1, ctx.key[1]
        a_inv = mod_inverse(a, 256)
        return bytes((a_inv * (y - b)) % 256 for y in data)

quick_test(Affine())
Testing: Affine-256
Input: b'Hello, PyCryption!'
----------------------------------------
Encrypt: <AlgorithmResult: 18 bytes, 0.024ms>
Decrypt: <AlgorithmResult: 18 bytes, 0.026ms>
Round-trip successful!

1.5 Lab Tie-In: Let the Instruments Judge It

The lab’s analysis suite measures ciphertext quality, not just correctness. Two predictions before we run it:

  1. Entropy won’t budge. The affine map is a bijection on single bytes — it renames symbols but can’t flatten their frequencies. English-shaped plaintext stays English-shaped.
  2. Avalanche will be ~0. Flip one plaintext bit and exactly one ciphertext byte changes. A healthy cipher changes ~50% of all ciphertext bits.
from lib.notebook import shannon_entropy, analyze_output, adapt
from lib.algorithms import Aes256GcmAlgorithm

english = (b"the quick brown fox jumps over the lazy dog " * 60)
affine = Affine()
aes = adapt(Aes256GcmAlgorithm, os.urandom(32), name="AES-256-GCM")

print(f"entropy  plaintext        : {shannon_entropy(english):.4f} bits/byte")
print(f"entropy  affine ciphertext: {shannon_entropy(affine.encrypt(english).output):.4f} bits/byte   <- unchanged!")
print(f"entropy  AES ciphertext   : {shannon_entropy(aes.encrypt(english).output):.4f} bits/byte")
print()
panel = analyze_output(affine, sample_size=4096, trials=8)
print("affine 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']}%)")
entropy  plaintext        : 4.3393 bits/byte
entropy  affine ciphertext: 4.3393 bits/byte   <- unchanged!
entropy  AES ciphertext   : 7.9320 bits/byte

affine verdict: ['weak-avalanche', 'ecb-pattern'] (avalanche 0.04%)
AES    verdict: CLEAN (avalanche 50.11%)

The instruments convict the affine cipher on every count the math predicted: identical entropy on structured input, near-zero avalanche, and the ECB canary catches that constant blocks encrypt to constant blocks (\(E(0) = b\), repeated forever).

A byte-wise bijection — any byte-wise bijection — can never be more than a renaming. Real ciphers must mix bytes together. Mixing many symbols at once is precisely what matrices do, and that’s Chapter 2.

Exercises

NoteExercise 1 — Congruence warm-up

Without a computer: what is \(2026 \bmod 7\)? And \((-1) \bmod 26\)?

\(2026 = 289 \cdot 7 + 3\), so \(2026 \equiv 3 \pmod 7\). And \(-1 \equiv 25 \pmod{26}\) (add one full wrap of 26).

NoteExercise 2 — Inverse hunting

Find \(5^{-1} \bmod 26\) by hand (hint: hunt for a multiple of 5 that’s one more than a multiple of 26), then check yourself with mod_inverse.

\(5 \cdot 21 = 105 = 4 \cdot 26 + 1\), so \(5^{-1} \equiv 21 \pmod{26}\).

NoteExercise 3 — Break the affine cipher

The affine key space over bytes is only \(128 \times 256 = 32{,}768\) keys (odd \(a\), any \(b\)). Write a brute-force loop that recovers the key from mystery below, knowing the plaintext starts with b"the ".

for a in range(1, 256, 2):
    for b in range(256):
        if bytes((a * x + b) % 256 for x in b"the ") == mystery[:4]:
            print("key:", a, b)

Single-byte substitution dies to four known bytes of plaintext.

# --- Self-check: run me. All asserts should pass silently. -------------
assert 2026 % 7 == 3                          # Exercise 1
assert -1 % 26 == 25
assert mod_inverse(5, 26) == 21               # Exercise 2
assert (5 * 21) % 26 == 1

# Exercise 3 — the mystery ciphertext and the brute force:
_a, _b = 141, 202
mystery = bytes((_a * x + _b) % 256 for x in b"the wrap-around world is small")
found = [(a, b) for a in range(1, 256, 2) for b in range(256)
         if bytes((a * x + b) % 256 for x in b"the ") == mystery[:4]]
assert (_a, _b) in found, "brute force missed the key!"
print(f"✓ all self-checks passed (brute force found {len(found)} candidate key(s), including the real one)")
✓ all self-checks passed (brute force found 1 candidate key(s), including the real one)

Next: Chapter 2 — Matrices & the Hill Cipher, where we mix many bytes at once and meet the first cipher with actual algebra under the hood — then break it with two blocks of known plaintext.

Back to top