2026-10-15 · algebra · cryptography

A cipher you can break with two equations

What "one-to-one" and "onto" actually buy you, why f(x) = ax + b mod 26 is a cipher only when a is chosen carefully, and why the same mistake still shows up in production code.

I'm working through chapter 2 of Elements of Modern Algebra (Gilbert & Gilbert) — the integers, divisibility, congruences, and the cryptography section at the end — and the affine cipher is the first place the abstract definitions of one-to-one and onto turn into something you can hold. Not the cipher wheel — the map itself, and what has to be true about it before it's usable.

Two properties, one job

A function f: A → B is one-to-one (injective) if different inputs always land on different outputs. It's onto (surjective) if every element of B gets hit by something. A function that is both is a bijection, and a bijection is exactly a function you can undo: every output points back to one and only one input.

That's the whole requirement for encryption. If two plaintext letters could map to the same ciphertext letter, the receiver has no way to know which one you meant. One-to-one isn't a nicety; it's the difference between a cipher and a hash.

Useful shortcut. On a finite set mapped to itself — like the 26 letters to the 26 letters — one-to-one and onto imply each other. If 26 inputs land on 26 distinct outputs, you've used every output. So you only have to check one of them.

The affine map

Number the alphabet A=0 … Z=25. An affine cipher is

E(x) = (a·x + b) mod 26

Two integers are the key: a is a multiplier, b is a shift. (The Caesar shift is the special case a = 1.)

Here's the catch. Try a = 2, b = 0:

A(0) → 0 → A N(13) → 26 mod 26 → 0 → A

A and N both encrypt to A. The map is not one-to-one, so it can't be decrypted. The reason is that 2 shares a factor with 26. In general:

E(x) = ax + b mod 26 is a bijection if and only if gcd(a, 26) = 1.

The valid multipliers are a ∈ {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25} — twelve of them. Times 26 choices of b gives 312 possible keys. Remember that number.

Try it

a (multiplier) b (shift)

plaintext

Decrypting with the key

To undo E, solve for x. Subtracting b is easy. Dividing by a isn't — there's no division mod 26 — but because gcd(a, 26) = 1 there is a number a⁻¹ with a · a⁻¹ ≡ 1 (mod 26). Then:

D(y) = a⁻¹ · (y − b) mod 26

With a = 5, b = 8: 5 × 21 = 105 = 4·26 + 1, so a⁻¹ = 21. Encrypting H (7): 5·7 + 8 = 43 ≡ 17 = R. Decrypting R: 21 · (17 − 8) = 189 ≡ 7 = H. Round trip.

That inverse exists because the map is one-to-one. The algebra and the security requirement are the same fact.

Decrypting without the key

This is the fun part. Suppose you intercept ciphertext and have no idea what a and b are. Two observations finish it:

English has a lopsided letter distribution. E is the most common letter; T is usually second. In any affine ciphertext longer than a sentence or two, the most frequent ciphertext letter is almost certainly E's image.
Two plaintext/ciphertext pairs give two linear equations in two unknowns.

Say the most common ciphertext letter is C and the second is Z. Guess E → C and T → Z:

4a + b ≡ 2    (E=4, C=2)
19a + b ≡ 25  (T=19, Z=25)

Subtract the first from the second: 15a ≡ 23 (mod 26). The inverse of 15 mod 26 is 7 (since 15·7 = 105 ≡ 1), so a ≡ 23·7 = 161 ≡ 5. Back-substitute: b ≡ 2 − 20 ≡ 8. Key recovered: (5, 8). Two frequency counts, one subtraction, one multiplication.

If the guess was wrong, the decrypted text is gibberish and you try the next pair. With only 312 keys, even brute force takes a laptop no measurable time. A cipher with a keyspace you can enumerate on a napkin is a puzzle, not a lock.

Where this actually shows up

The affine map is weak as a cipher, but the structure is everywhere.

Random number generators. A linear congruential generator is xₙ₊₁ = (a·xₙ + c) mod m — the exact same map, iterated. It's fast, it's in rand() in a lot of C libraries, and it's predictable for precisely the reason the cipher is: a couple of outputs let you solve for the parameters. That's why "I used rand() for the session token" is a finding, not a design.
Hashing and table probing. Multiply-and-add mod a table size is a standard hash step. The gcd condition reappears as "pick a multiplier coprime to the table size so the probe sequence visits every slot" — onto, in other words.
Modern block ciphers. AES is also a bijection — on 128-bit blocks instead of single letters, with a keyspace of 2¹²⁸ instead of 312, and built so that no small number of known plaintext/ciphertext pairs yields a solvable system. The known-plaintext attack above is the threat model the entire design exists to defeat. Same requirement (invertible), same attack class (solve for the key), wildly different scale.
Sanity-checking an ID scheme. If someone obfuscates sequential IDs with "multiply by a constant and mod," you now know how to recover the constant from two IDs. Obfuscation isn't encryption, and this is the two-line proof.

The code

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

def inv(a, m=26):
    g, x, _ = egcd(a, m)
    if g != 1:
        raise ValueError(f"{a} has no inverse mod {m}: not one-to-one")
    return x % m

def encrypt(text, a, b):
    inv(a)  # fail fast if the key isn't a bijection
    return "".join(chr((a * (ord(c) - 65) + b) % 26 + 65) if c.isalpha() else c
                   for c in text.upper())

def decrypt(text, a, b):
    ai = inv(a)
    return "".join(chr((ai * (ord(c) - 65 - b)) % 26 + 65) if c.isalpha() else c
                   for c in text.upper())

def crack(ct, p1="E", p2="T"):
    """Recover (a, b) from the two most frequent ciphertext letters."""
    from collections import Counter
    top = [c for c, _ in Counter(ch for ch in ct.upper() if ch.isalpha()).most_common(2)]
    x1, x2 = ord(p1) - 65, ord(p2) - 65
    y1, y2 = ord(top[0]) - 65, ord(top[1]) - 65
    a = ((y2 - y1) * inv((x2 - x1) % 26)) % 26
    b = (y1 - a * x1) % 26
    return a, b

The inv function raising on a bad a is the one-to-one check, enforced at the boundary. That's the habit worth taking from this chapter: when a function has to be invertible, make the code refuse to run when it isn't.

The engine underneath: Euclid

Everything above leaned on two facts — "does a have an inverse mod 26?" and "what is it?" — and both come from the same 2,300-year-old algorithm.

Euclid's algorithm finds gcd(a, b) by repeated division: replace the pair (a, b) with (b, a mod b) until the remainder is zero. The last nonzero remainder is the gcd.

gcd(26, 5):  26 = 5·5 + 1
              5 = 1·5 + 0     → gcd = 1

The extended version runs the same steps but keeps track of how each remainder was built from the original a and b. The result is Bézout's identity: integers x, y with ax + by = gcd(a, b). When the gcd is 1, that reads ax ≡ 1 (mod b) — so x is the inverse of a mod b. That's what egcd() in the code above computes, and it's why the function doubles as the one-to-one test: no inverse, no bijection.

From 26 = 5·5 + 1:   1 = 26 − 5·5
So 5·(−5) ≡ 1 (mod 26), and −5 ≡ 21.   Inverse of 5 is 21.  ✓

It runs in a number of steps proportional to the number of digits, not the size of the numbers — which is why it still works when the numbers are 600 digits long. That's about to matter.

From one key to two: RSA

The affine cipher is symmetric: whoever can encrypt can decrypt, because the key is shared and the inverse is cheap to compute. Public-key cryptography asks a stranger question: can we build a bijection where computing the forward direction is easy for everyone, but computing the inverse is easy only for one person?

RSA does it by changing what's hard. In the affine cipher, finding the inverse of a mod 26 is trivial because 26 is small and its factors are known. RSA picks a modulus whose factors are secret, and makes the inverse depend on knowing them.

Pick two large primes p and q. Let n = p·q. Publish n. Keep p and q secret.
Compute φ(n) = (p−1)(q−1) — the count of numbers below n coprime to it. You can only do this if you know p and q.
Pick a public exponent e with gcd(e, φ(n)) = 1. Use the extended Euclidean algorithm to find d with e·d ≡ 1 (mod φ(n)). Publish e; keep d.
Encrypt: c = mᵉ mod n. Decrypt: m = cᵈ mod n.

Same shape as before: a map (m ↦ mᵉ), an inverse (c ↦ cᵈ), and Euclid producing the inverse exponent. The difference is where the secret sits. Anyone can compute mᵉ mod n. Computing d requires φ(n), which requires p and q, which requires factoring n — and nobody knows how to do that efficiently for a 2048-bit n.

Toy numbers, so you can check it by hand:

p = 5, q = 11  →  n = 55,  φ(n) = 4·10 = 40
e = 3  (gcd(3, 40) = 1)
d = 3⁻¹ mod 40 = 27     (3·27 = 81 = 2·40 + 1)   ← extended Euclid

m = 7:   c = 7³ mod 55 = 343 mod 55 = 13
         m = 13²⁷ mod 55 = 7   ✓

The known-plaintext attack from earlier doesn't apply: knowing (m, c) pairs tells you nothing about d, because the relationship runs through φ(n), not through a solvable linear system. That's the whole trick.

Why the book puts these together. Affine cipher: bijection, inverse via Euclid, secret shared. RSA: bijection, inverse via Euclid, secret asymmetric because the inverse depends on a factorization only one party has. Same chapter, same tools, one extra idea.

Source: Gilbert & Gilbert, Elements of Modern Algebra, chapter 2 (the integers; §2.8 cryptography). Worked examples and code are my own.