Case Study: Building an Affine Cipher — Where the Decryption Key Is a Bézout Coefficient

"The enemy knows the system." — Claude Shannon, paraphrasing Kerckhoffs's principle

Executive Summary

In this build-focused case study you will construct a small but complete encryption tool — the affine cipher — from scratch, and in doing so you will use almost every result in the chapter for real. The affine cipher encrypts a letter $x$ as $E(x) = (a x + b) \bmod 26$. Encryption is easy arithmetic; decryption is where the chapter pays off, because undoing the multiplication by $a$ requires a modular inverse $a^{-1}$, and the only way to compute that inverse is the extended Euclidean algorithm of §22.5 producing a Bézout coefficient. Along the way you will discover why the multiplier $a$ must be coprime to $26$ — not as a rule handed down, but as a theorem you can prove from Euclid's Lemma and Bézout. This is a deliberate dress rehearsal for RSA (Chapter 25): RSA is the affine cipher's serious older sibling, and the move "the private key is a Bézout coefficient of the public key" is identical in both.

Skills applied

• Implementing gcd, ext_gcd, and a Bézout-based mod_inverse (§22.4–22.5).
• Proving, from coprimality and Euclid's Lemma, exactly which keys are valid (§22.5).
• Deriving the decryption formula and verifying $D(E(x)) = x$ by hand and in code.
• Connecting "the inverse exists iff $\gcd(a, 26) = 1$" to the chapter's central identity (§22.5).
• Building incrementally and checking each piece against a hand-traced expected output.

Background

The scenario

You are writing a teaching tool that demonstrates how a classical cipher works end to end. The affine cipher treats the 26 letters $A, B, \dots, Z$ as the integers $0, 1, \dots, 25$ and encrypts each letter independently with two key numbers, a multiplier $a$ and a shift $b$: $$E(x) = (a x + b) \bmod 26.$$ The Caesar cipher is the special case $a = 1$ (shift only). Adding the multiplier $a$ makes the cipher slightly less trivial — but it also introduces a subtlety that is the whole reason this belongs in a number theory chapter: not every $a$ works. Choose $a$ carelessly and decryption becomes impossible, because two different plaintext letters get mapped to the same ciphertext letter and there is no way to tell them apart.

💡 Intuition: Encryption must be reversible. $E$ multiplies by $a$ (mod 26), so decryption must divide by $a$ (mod 26). But there are no fractions in modular arithmetic — "dividing by $a$" means multiplying by the modular inverse $a^{-1}$, the number with $a \cdot a^{-1} \equiv 1 \pmod{26}$. Whether such an inverse exists is precisely the question §22.5 answered: it exists iff $\gcd(a, 26) = 1$. So the cipher's correctness rests directly on Bézout's identity.

Why this matters

Every line you write here returns in Chapter 25, scaled up. RSA encrypts with a public exponent $e$ and decrypts with a private exponent $d$ chosen so that $d$ is the modular inverse of $e$ — i.e. $d$ is a Bézout coefficient of $e$ modulo $\phi(n)$, computed with the very same ext_gcd. If you can build and justify the affine cipher's decryption key today, you have already built RSA's key-recovery machinery; only the surrounding arithmetic changes. The threshold concept of §22.5 — "a modular inverse is a Bézout coefficient" — is the hinge, and this case study is where you turn it.

Phase 1: Build the gcd and the inverse engine

Start with the foundations the cipher will call. These are the chapter's gcd and ext_gcd, plus a thin wrapper that turns a Bézout coefficient into a modular inverse.

def gcd(a, b):
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a

def ext_gcd(a, b):
    """Return (g, x, y) with g = gcd(a, b) and a*x + b*y = g."""
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = ext_gcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)

def mod_inverse(a, m):
    """Return a^{-1} mod m if gcd(a, m) == 1, else None."""
    g, x, _ = ext_gcd(a, m)
    if g != 1:
        return None
    return x % m            # reduce the (possibly negative) Bezout coeff into [0, m)

print(mod_inverse(5, 26))
print(mod_inverse(2, 26))   # gcd(2,26)=2, no inverse
# Expected output:
# 21
# None

Trace mod_inverse(5, 26) by hand to trust it. Run the Euclidean divisions: $$26 = 5 \cdot 5 + 1, \qquad 5 = 5 \cdot 1 + 0,$$ so $\gcd(5, 26) = 1$. Back-substitute for Bézout: $1 = 26 - 5 \cdot 5$, i.e. $5 \cdot (-5) + 26 \cdot 1 = 1$. The coefficient of $5$ is $-5$; reducing into range, $-5 \bmod 26 = 21$. Check: $5 \cdot 21 = 105 = 4 \cdot 26 + 1$, so $5 \cdot 21 \equiv 1 \pmod{26}$. The inverse is $21$, exactly as printed. And mod_inverse(2, 26) returns None because $\gcd(2,26) = 2 \ne 1$ — there is no $x$ with $2x \equiv 1 \pmod{26}$, since $2x$ is always even and $1$ is odd.

🔄 Check Your Understanding Why does mod_inverse reduce with x % m at the end instead of returning the raw Bézout coefficient $x$?

Answer

The extended Euclidean algorithm returns a signed coefficient (here $-5$). A cipher key must be a letter index in $\{0, \dots, 25\}$, so we reduce $-5$ to the canonical representative $21$ via the Division Algorithm (x % m). Both $-5$ and $21$ are valid inverses mod $26$; we just want the one in range (§22.5's pitfall about signed coefficients).

Phase 2: Prove which keys are legal before using them

Here is the discipline the chapter buys us: rather than discover bad keys by watching decryption fail, we can prove exactly which multipliers $a$ are valid. This is the build-time check that makes the tool trustworthy.

Claim (valid-key criterion). The affine encryption map $E(x) = (a x + b) \bmod 26$ is a bijection on $\{0, \dots, 25\}$ (hence decryptable) if and only if $\gcd(a, 26) = 1$.

The strategy first. "Decryptable" means invertible means bijective. We show coprimality is exactly what makes $E$ one-to-one. The forward direction uses the modular inverse (Bézout) to build an explicit decryptor; the reverse direction uses Euclid's Lemma to exhibit a collision when $a$ shares a factor with $26$.

Proof. ($\Leftarrow$) Suppose $\gcd(a, 26) = 1$. By Bézout (§22.5) there is an inverse $a^{-1}$ with $a \cdot a^{-1} \equiv 1 \pmod{26}$. Define $D(y) = a^{-1}(y - b) \bmod 26$. Then for any $x$, $$D(E(x)) = a^{-1}\big((a x + b) - b\big) = a^{-1}(a x) = (a^{-1} a) x \equiv x \pmod{26}.$$ So $D$ undoes $E$; $E$ is invertible, hence a bijection.

($\Rightarrow$) Suppose $\gcd(a, 26) = d > 1$. We exhibit two distinct letters with the same ciphertext, so $E$ is not injective. Since $d \mid 26$ and $d > 1$, the number $26/d$ is a positive integer strictly between $0$ and $26$. Consider $x_1 = 0$ and $x_2 = 26/d$. Then $$E(x_2) - E(x_1) = a \cdot \tfrac{26}{d} = \tfrac{a}{d} \cdot 26,$$ and $\tfrac{a}{d}$ is an integer (because $d \mid a$), so $E(x_2) - E(x_1)$ is a multiple of $26$ — meaning $26 \mid (E(x_2) - E(x_1))$, i.e. $E(x_1) = E(x_2) \pmod{26}$. Two distinct letters collide, so $E$ is not invertible. $\blacksquare$

This is more than pedantry: it tells the tool to reject $a = 2, 4, 6, \dots$ (even) and $a = 13$ (the factor of $13$), and accept the multipliers coprime to $26$. We can even list the legal multipliers.

legal_a = [a for a in range(1, 26) if gcd(a, 26) == 1]
print(legal_a)
print(len(legal_a))
# Expected output:
# [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]
# 12

There are exactly $12$ legal multipliers — the integers in $\{1, \dots, 25\}$ coprime to $26 = 2 \cdot 13$ (everything not divisible by $2$ or by $13$). That count, $12$, is the value of Euler's totient $\phi(26)$ — a function that will headline Chapter 23. You have just computed a totient by hand without needing the name yet.

🔗 Connection. "Count the integers below $m$ that are coprime to $m$" is precisely $\phi(m)$, and RSA's whole key schedule revolves around $\phi(n)$. The legal-multiplier count here ($\phi(26) = 12$) is a tiny preview of the quantity that sizes RSA's private-key arithmetic in Chapters 23 and 25.

Phase 3: Build encrypt and decrypt over whole messages

Now assemble the cipher over strings. Map letters to $0$–$25$, transform, map back. We uppercase and ignore non-letters to keep the demonstration clean.

def to_num(ch):  return ord(ch) - ord('A')
def to_chr(n):   return chr(n % 26 + ord('A'))

def affine_encrypt(text, a, b):
    if gcd(a, 26) != 1:
        raise ValueError("multiplier a must be coprime to 26")
    out = []
    for ch in text.upper():
        if ch.isalpha():
            out.append(to_chr((a * to_num(ch) + b) % 26))
        else:
            out.append(ch)
    return "".join(out)

def affine_decrypt(cipher, a, b):
    a_inv = mod_inverse(a, 26)
    if a_inv is None:
        raise ValueError("multiplier a must be coprime to 26")
    out = []
    for ch in cipher.upper():
        if ch.isalpha():
            out.append(to_chr(a_inv * (to_num(ch) - b) % 26))
        else:
            out.append(ch)
    return "".join(out)

a, b = 5, 8
ct = affine_encrypt("MATH", a, b)
print(ct)
print(affine_decrypt(ct, a, b))
# Expected output:
# QIZR
# MATH

Hand-trace the encryption of "MATH" with $a = 5$, $b = 8$ to certify the output letter by letter (using $E(x) = (5x + 8) \bmod 26$):

So "MATH" $\to$ "QIZR", matching the program. Now the round trip, using $D(y) = 21(y - 8) \bmod 26$ (recall $5^{-1} \equiv 21$ from Phase 1):

Decryption returns "MATH". The round trip is not luck — Phase 2 proved $D(E(x)) = x$ for every $x$, and these four rows are four instances of that theorem.

⚠️ Common Pitfall: A subtle but common bug is to reduce before subtracting the shift, writing a_inv * (to_num(ch) - b) without the surrounding % 26, or applying % 26 to (y - b) first and losing a negative value's correct representative. Because Python's % already returns the canonical $0 \le r < 26$ (the Division Algorithm, §22.3), wrapping the whole expression in % 26 is correct even when y - b is negative — e.g. decrypting A (=0) gives 21 * (0 - 8) % 26 = 21 * (-8) % 26 = -168 % 26 = 14, a valid letter. In C or Java the same line would yield a negative index and crash; this is the language portability trap from §22.3.

Phase 4: Stress the build — verify the bijection exhaustively

A cipher you cannot decrypt is worse than useless, so before shipping, test that the round trip is perfect for every letter and every legal key — a finite, exhaustive check that complements the proof (theme four: prove the general fact, then let computation confirm every case in the finite universe).

def round_trips_for_all(a, b):
    """True iff decrypt(encrypt(x)) == x for all 26 letters under key (a, b)."""
    alphabet = [chr(c) for c in range(ord('A'), ord('Z') + 1)]
    return all(affine_decrypt(affine_encrypt(ch, a, b), a, b) == ch
               for ch in alphabet)

legal_a = [a for a in range(1, 26) if gcd(a, 26) == 1]
print(all(round_trips_for_all(a, 8) for a in legal_a))   # every legal key, shift b=8
print(round_trips_for_all(1, 3))                         # Caesar cipher (a=1) is a special case
# Expected output:
# True
# True

The first True says: across all $12$ legal multipliers (with $b = 8$), every one of the $26$ letters survives the round trip — $12 \times 26 = 312$ encrypt/decrypt pairs, all correct. The proof in Phase 2 told us this must hold; the exhaustive test confirms there is no off-by-one or sign bug in the implementation. The proof certifies the algorithm; the test certifies the code. Both are cheap here because the universe is finite — a luxury RSA does not have, which is exactly why RSA leans even harder on the proof.

🐛 Find the Error: A teammate "optimizes" mod_inverse by dropping the coprimality guard: "ext_gcd always returns some x, so just return x % m." Show concretely that for $a = 2$, $m = 26$ this produces a value $x$ for which $2x \not\equiv 1 \pmod{26}$, so the resulting "cipher" silently corrupts messages.

Answer

ext_gcd(2, 26) returns $g = 2$ with, say, $x = 1$ (since $2\cdot 1 + 26\cdot 0 = 2 = g$). Then x % 26 = 1, but $2 \cdot 1 = 2 \not\equiv 1 \pmod{26}$ — it is the inverse of nothing. Decryption would multiply by $1$ instead of a true inverse and return garbage that looks like plaintext. The guard if g != 1: return None is load-bearing: without it the tool fails silently, the worst kind of failure. The math (§22.5) is unambiguous — an inverse exists only when $\gcd(a, m) = 1$.

Phase 5: From affine to RSA — the same key trick, scaled

Step back and notice the architecture you just built, because it is RSA's in miniature:

The only essential differences are that RSA replaces "multiply by $a$" with "raise to the power $e$" (needing modular exponentiation, Chapter 23) and replaces the modulus $26$ with a product of two huge primes (so that computing $\phi(n)$ — and hence the private key — is infeasible without the factorization, Chapter 25). But "the private decryption key is the Bézout coefficient of the public key, computed by the extended Euclidean algorithm" is verbatim the same idea. You did not build a toy; you built the key schedule.

🔗 Connection. Hold the right-hand column in mind through Chapters 23–25. When Chapter 25 says "set $d = \text{mod\_inverse}(e, \phi(n))$," that is the line you wrote in Phase 1, applied to bigger numbers. The affine cipher is the proof that you already understand the heart of RSA's decryption.

Discussion Questions

1. The valid-key proof (Phase 2) used Bézout for the "if" direction and a collision construction for the "only if" direction. Where, precisely, did the "only if" argument use the fact that $d \mid 26$ to guarantee $26/d$ is an integer in range?
2. The affine cipher has $12 \times 26 = 312$ possible keys (12 legal multipliers, 26 shifts). Why is this cipher trivially breakable by brute force, and what does that say about the size of the keyspace as a security parameter (connecting to Chapter 15)?
3. Phase 4 verified the bijection exhaustively because the letter universe has only 26 elements. Explain why RSA cannot be validated the same way, and why that makes the proof of correctness indispensable rather than optional.
4. Suppose you extend the alphabet to include digits and a space, making $m = 37$ (a prime). Which multipliers $a$ become legal now, and why does a prime modulus make the legality test especially simple? (Use Euclid's Lemma / the definition of prime.)
5. The decryption formula is $D(y) = a^{-1}(y - b) \bmod 26$. A student proposes $D(y) = (y - b)/a$. Explain in one sentence why "$/a$" is meaningless here and what object replaces it.

Your Turn: Extensions

• Option A (key generator). Write random_affine_key() that returns a uniformly random legal key $(a, b)$: pick $b \in \{0, \dots, 25\}$ freely and pick $a$ uniformly from the multipliers coprime to $26$ (filter with the chapter's gcd). Argue why filtering by gcd(a, 26) == 1 is exactly the right legality condition.
• Option B (known-plaintext attack). Given two plaintext/ciphertext letter pairs $(x_1, y_1), (x_2, y_2)$, recover the key $(a, b)$: subtract to eliminate $b$, then solve for $a$ using mod_inverse(x_1 - x_2, 26). State the condition under which the attack succeeds (when is $x_1 - x_2$ invertible mod $26$?) and connect it to §22.5.
• Option C (decimal/larger modulus). Reimplement the cipher over a prime modulus $m = 97$ (covering printable ASCII offsets), reusing mod_inverse unchanged. Verify a round trip on a short string by hand-tracing two characters, and note which part of the code did not have to change — and why a prime modulus guarantees every nonzero multiplier is legal.

Key Takeaways

1. The decryption key is a Bézout coefficient. Undoing "multiply by $a$ mod $26$" means multiplying by $a^{-1}$, and $a^{-1}$ comes straight out of ext_gcd (§22.5) — the chapter's most important computational tool, used for real.
2. Coprimality decides legality, and you can prove it. $E$ is invertible iff $\gcd(a, 26) = 1$; the forward direction is Bézout, the reverse is a collision built from a shared factor (Euclid's Lemma territory). Bad keys are rejected at build time, not discovered at decrypt time.
3. Signed Bézout coefficients get reduced into range. ext_gcd may return a negative inverse ($-5$); % 26 lands it on the canonical representative ($21$) via the Division Algorithm (§22.3).
4. Prove the general fact, then test the finite universe. A proof gives $D(E(x)) = x$ for all $x$; an exhaustive check over all 26 letters and 12 keys confirms the code matches the math.
5. This is RSA in miniature. Public key, coprimality requirement, and a private key that is the Bézout coefficient of the public key — the affine cipher rehearses RSA's exact key schedule, with only the operation (multiply vs. exponentiate) and the modulus size changed.