Case Study: Breaking an Affine Cipher with Modular Inverses

"The enemy knows the system being used." — Claude Shannon (Shannon's maxim)

Executive Summary

You are handed an intercepted message encrypted with an affine cipher — a classical substitution cipher whose entire mechanism is one line of modular arithmetic, $c \equiv (a\,m + b) \pmod{26}$. Your job is not to build the cipher but to break it: to recover the secret key $(a, b)$ from a small crib of known plaintext, then decrypt the rest. Every step is an application of this chapter — deciding when the key is even valid (§23.3, the inverse-existence condition), solving a pair of linear congruences for the key (§23.2–23.3), inverting the encryption map (§23.3), and counting the keyspace to judge how weak the cipher really is. By the end you will have used the modular inverse not as an abstract object but as a cryptanalytic weapon, and you will understand exactly why the affine cipher is a teaching toy and not a real defense.

This is an analysis-heavy case study: almost no new code, but a great deal of hand-derivation. We will compute residues, solve congruences, and check our work by re-encrypting — the discipline that separates "I think I broke it" from "here is the key, and here is the proof it is the key."

Skills applied

• Translating an encryption scheme into a congruence and reading off when its key is invertible (§23.3).
• Solving a system of two linear congruences for two unknowns by elimination and modular inversion.
• Computing a modular inverse by the extended Euclidean algorithm (§23.3, Chapter 22).
• Counting a keyspace with the totient (§23.6) and judging cryptographic strength.
• Verifying a recovered key by re-encryption — proof, not hope.

Background

The affine cipher in one congruence

Letters are numbers: $\texttt{A} = 0, \texttt{B} = 1, \dots, \texttt{Z} = 25$. The affine cipher picks two key numbers $a$ and $b$ in $\mathbb{Z}_{26}$ and encrypts each plaintext letter $m$ to

$$c \equiv a\,m + b \pmod{26}.$$

The "$a$" scales (multiplies) and the "$b$" shifts (adds) — hence affine, a linear map plus a constant. The Caesar cipher is the special case $a = 1$. Decryption must undo both operations: subtract $b$, then divide by $a$. But §23.2 warns us there is no free division in $\mathbb{Z}_{26}$ — we can only "divide by $a$" if $a$ has an inverse. So the decryption rule is

$$m \equiv a^{-1}(c - b) \pmod{26},$$

and this only makes sense when $a^{-1}$ exists.

🔗 Connection. "When does $a^{-1}$ exist modulo $26$?" is exactly Theorem 23.3: precisely when $\gcd(a, 26) = 1$. This is not a side condition — it is the rule that decides which keys are even legal. A cipher designer who picks $a = 13$ has built a machine that cannot be decrypted, because $\gcd(13, 26) = 13 \ne 1$ and §23.2's pitfall bites: the map $m \mapsto 13m + b$ is not injective.

Why this matters for a security analyst

Classical ciphers are still everywhere — in CTF challenges, in legacy systems, in the "encryption" some applications roll themselves. An analyst's first move against any unknown scheme is to ask: what is the mathematical structure, and where is it weak? For the affine cipher the structure is a single invertible affine map over $\mathbb{Z}_{26}$, and the weakness is glaring: the key has only two unknowns, so two known plaintext–ciphertext pairs pin it down completely. Shannon's maxim at the top of this study is the assumption we make throughout: the attacker knows the system (affine over $\mathbb{Z}_{26}$); only the key $(a, b)$ is secret. Our task is to show how little that secrecy buys.

The intercept

We intercept the ciphertext

IHHWV› (we'll work the first letters)  ->  ciphertext: I H H W V ...

and, from context (a leaked header, a guessed greeting — the usual sources of a crib), we believe the plaintext begins with the word HE. So we have a known-plaintext foothold: two pairs.

These two pairs are all we need. (We will treat the rest of the ciphertext after recovering the key.)

💡 Intuition. The affine key $(a, b)$ has two unknowns, and the encryption rule is linear in those unknowns once $m$ and $c$ are fixed: $c \equiv a\,m + b$. Two data points determine a line. The only twist is that "the line" lives in $\mathbb{Z}_{26}$, so solving for the slope $a$ means dividing by a difference — which means a modular inverse.

Phase 1: Set up the key-recovery congruences

Substitute each known pair into $c \equiv a m + b \pmod{26}$.

From pair 0 ($m = 7, c = 8$): $$8 \equiv 7a + b \pmod{26}. \tag{1}$$

From pair 1 ($m = 4, c = 7$): $$7 \equiv 4a + b \pmod{26}. \tag{2}$$

Two congruences, two unknowns $a$ and $b$. This is a linear system over $\mathbb{Z}_{26}$, and we solve it the way we solve any two-by-two linear system: eliminate one unknown by subtraction.

The strategy first. Subtract (2) from (1) to kill $b$. That leaves a single linear congruence in $a$ alone — and by §23.3 we solve it by multiplying through by a modular inverse. Once we have $a$, back-substitute into either equation to get $b$ by a plain subtraction (no inverse needed for $b$, since its coefficient is $1$).

Phase 2: Solve for the multiplier $a$

Subtract (2) from (1), using the subtraction rule of Theorem 23.2 (we may subtract congruences): $$8 - 7 \equiv (7a + b) - (4a + b) \pmod{26}, \qquad \text{i.e.} \qquad 1 \equiv 3a \pmod{26}. \tag{3}$$

Now (3) is a linear congruence $3a \equiv 1 \pmod{26}$ — which is literally the statement that $a$ is the inverse of $3$ modulo $26$. Before solving, check it is solvable: $\gcd(3, 26) = 1$, so by Theorem 23.3 a unique solution exists. Find $3^{-1} \bmod 26$ with the extended Euclidean algorithm (Chapter 22, as in §23.3). The descending steps: $$26 = 8 \cdot 3 + 2, \qquad 3 = 1 \cdot 2 + 1, \qquad 2 = 2 \cdot 1.$$ Back-substitute to write $1$ as a combination of $3$ and $26$: $$1 = 3 - 1 \cdot 2 = 3 - (26 - 8\cdot 3) = 9 \cdot 3 - 1 \cdot 26.$$ So $9 \cdot 3 = 27 \equiv 1 \pmod{26}$, giving $3^{-1} \equiv 9 \pmod{26}$. Therefore from (3), $$a \equiv 9 \cdot 1 = 9 \pmod{26}.$$

So the multiplier is $a = 9$. Sanity check that $a$ is a legal key: $\gcd(9, 26) = 1$, so $9$ is invertible modulo $26$ — good, this is a key the cipher could actually have used (had $\gcd(a, 26)$ come out $\ne 1$, we would know our crib was wrong).

⚠️ Common Pitfall. It is tempting, on reaching $3a \equiv 1 \pmod{26}$, to "divide both sides by $3$" and write $a \equiv 1/3$. There is no $1/3$ in $\mathbb{Z}_{26}$. The legal move is to multiply both sides by $3^{-1} = 9$. The two feel the same in ordinary arithmetic, but only the second is defined here — and it is defined precisely because $\gcd(3, 26) = 1$ (Theorem 23.3).

Phase 3: Solve for the shift $b$

Back-substitute $a = 9$ into equation (1), $8 \equiv 7a + b \pmod{26}$: $$8 \equiv 7 \cdot 9 + b = 63 + b \pmod{26}.$$ Reduce $63 \bmod 26$: $63 = 2 \cdot 26 + 11$, so $63 \equiv 11$. Thus $8 \equiv 11 + b \pmod{26}$, and $$b \equiv 8 - 11 = -3 \equiv 23 \pmod{26}.$$ (The residue of $-3$ is $-3 + 26 = 23$.) So the recovered key is $(a, b) = (9, 23)$.

Cross-check against the other equation. A recovered key must satisfy both pairs, not just the one we used. Plug $(9, 23)$ into equation (2), $7 \equiv 4a + b \pmod{26}$: $$4 \cdot 9 + 23 = 36 + 23 = 59, \qquad 59 \bmod 26 = 59 - 2\cdot 26 = 7. \ \checkmark$$ Both pairs are satisfied. We have not merely found a key consistent with one data point — we have verified the key against an independent second point. That is the difference between a guess and a break.

🔄 Check Your Understanding We used pairs 0 and 1, whose plaintext difference was $m_0 - m_1 = 7 - 4 = 3$, and that $3$ became the coefficient in $3a \equiv 1$. What would have gone wrong if the two crib letters had been, say, A and N (values $0$ and $13$), giving a difference of $13$?

Answer

The elimination step would produce $\Delta c \equiv 13 a \pmod{26}$, but $\gcd(13, 26) = 13 \ne 1$, so $13$ has no inverse modulo $26$ (Theorem 23.3). We could not solve for $a$ uniquely — the congruence would have either no solution or $13$ solutions (Theorem 23.4). The moral: a crib whose letter difference shares a factor with $26$ is useless for recovering $a$. Pick crib letters whose value difference is coprime to $26$.

Phase 4: Build the decryption map and read the message

With the key known, decryption is the inverse affine map from the Background: $$m \equiv a^{-1}(c - b) \pmod{26}.$$ We need $a^{-1} = 9^{-1} \bmod 26$. Run the extended Euclidean algorithm on $9$ and $26$: $$26 = 2 \cdot 9 + 8, \qquad 9 = 1 \cdot 8 + 1, \qquad 8 = 8 \cdot 1.$$ Back-substitute: $1 = 9 - 1\cdot 8 = 9 - (26 - 2\cdot 9) = 3 \cdot 9 - 1 \cdot 26$. So $3 \cdot 9 = 27 \equiv 1 \pmod{26}$, giving $9^{-1} \equiv 3 \pmod{26}$.

The decryption rule is therefore $$m \equiv 3\,(c - 23) \pmod{26}.$$

Apply it to the intercepted ciphertext I H H W V (values $8, 7, 7, 22, 21$), reducing at every step (the §23.2 habit):

The first two letters decrypt to HE, matching our crib — a final confirmation the key is right. The five-letter plaintext is HEEXU. (In a real intercept you would feed the whole ciphertext through the same rule and read a sentence; here the point is that every letter is one subtraction, one multiplication, and a reduction modulo $26$.)

Here is the decryption distilled into the chapter's mod_inverse, so you can check the hand-work against the mechanism (do not run it — the output is hand-derived above):

# Affine decryption built from this chapter's mod_inverse (do not execute).
def ext_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    g, s1, t1 = ext_gcd(b, a % b)
    return (g, t1, s1 - (a // b) * t1)

def mod_inverse(a, m):
    g, s, _ = ext_gcd(a % m, m)
    return s % m if g == 1 else None

def affine_decrypt(cipher_vals, a, b, m=26):
    a_inv = mod_inverse(a, m)          # 9^{-1} mod 26 = 3
    return [(a_inv * (c - b)) % m for c in cipher_vals]

print(affine_decrypt([8, 7, 7, 22, 21], 9, 23))   # I H H W V  ->  H E E X U
# Expected output:
# [7, 4, 4, 23, 20]

Phase 5: How weak is this, really? Counting the keyspace

We broke the cipher with two known letters. The structural reason is that the keyspace is tiny, and the totient (§23.6) measures exactly how tiny.

• The shift $b$ can be any of the $26$ residues: $26$ choices.
• The multiplier $a$ must be a unit modulo $26$ — coprime to $26$ — so the number of legal $a$ values is $\phi(26)$. Since $26 = 2 \cdot 13$ with $2, 13$ distinct primes, $\phi(26) = \phi(2)\phi(13) = 1 \cdot 12 = 12$.

So the total number of valid affine keys is $$\phi(26) \times 26 = 12 \times 26 = 312.$$

A keyspace of $312$ is trivially brute-forceable — a program could try all $312$ keys and pick the decryption that looks like English in microseconds, with no crib at all. The known-plaintext attack we ran is faster and cleaner, but even the laziest attack succeeds. Contrast this with RSA (Chapter 25), whose keyspace is governed by $\phi(n)$ for an $n$ with hundreds of digits: there the same totient that here yields $12$ legal multipliers instead yields an astronomically large, unsearchable space. The mathematics is identical; only the size of $n$ separates a toy from a fortress.

🚪 Threshold Concept: structure is the attack surface. The affine cipher fell not to cleverness but to its algebraic structure — it is an invertible affine map with two parameters, so two equations expose it. Modern cryptography's central design goal is to build functions with no usable structure: where knowing many input–output pairs tells you nothing about the key. RSA's security rests on a structure (modular exponentiation) whose inverse requires factoring — the trapdoor of §23.6. The lesson that carries forward: when you analyze any cipher, find the equation the key satisfies, and count how many observations it takes to solve it.

Discussion Questions

1. We recovered $(a, b)$ from two known-plaintext pairs. Argue carefully that two pairs are not merely sufficient but, in general, necessary: with only one pair $(m_0, c_0)$, how many keys $(a, b)$ are consistent with it? (Count them using §23.3.)
2. The elimination step required the plaintext difference $m_0 - m_1$ to be coprime to $26$. Suppose an analyst has a long crib. Describe an algorithm for choosing which two crib positions to use so that the recovery is guaranteed to work, and tie the choice to Theorem 23.3.
3. Why is $a = 13$ an illegal affine key, and what exactly goes wrong with the encryption map if you use it? Relate your answer to injectivity and to the §23.2 pitfall about cancellation.
4. The keyspace is $\phi(26) \times 26 = 312$. If we worked modulo a prime $p = 29$ instead of $26$, how many legal multipliers would there be, and why does a prime modulus maximize the number of legal $a$ values for a given size? (Use $\phi(p) = p - 1$ from §23.6.)
5. Shannon's maxim says the attacker knows the system. Suppose, instead, the attacker did not know the modulus was $26$. Would that meaningfully strengthen the cipher? Argue why "hiding the system" (often called security through obscurity) is a poor substitute for a large keyspace.

Your Turn: Extensions

• Option A (full ciphertext-only break). Forget the crib. Write affine_bruteforce(cipher_vals) that tries all $312$ legal keys (loop $a$ over the units modulo $26$ via gcd, $b$ over $0\dots25$), decrypts under each, and returns every candidate. Then score candidates by letter frequency (English's E, T, A are common) and report the most likely plaintext. State why this works without any known plaintext.
• Option B (two-pair solver). Generalize Phases 1–3 into recover_affine_key(m0, c0, m1, c1, n=26) that returns (a, b) or None (when $\gcd(m_0 - m_1, n) \ne 1$). Use mod_inverse. Test it on the pairs from this study and confirm it returns $(9, 23)$.
• Option C (the linear cipher's cousin). The Hill cipher generalizes the affine cipher to matrices over $\mathbb{Z}_{26}$, encrypting blocks of letters at once. Read about its decryption condition (the key matrix must be invertible modulo $26$, i.e. its determinant must be a unit) and explain, in two sentences, how it is the same Theorem 23.3 condition one dimension up.

Key Takeaways

1. An affine cipher is one congruence, $c \equiv am + b \pmod{26}$ — and so is its analysis. Every step of the break is a chapter operation: an inverse-existence check, a linear-congruence solve, a modular inverse, a re-encryption verification.
2. "Divide by $a$" means "multiply by $a^{-1}$," and that requires $\gcd(a, 26) = 1$. The inverse-existence theorem (23.3) is not fine print; it decides which keys are legal and which crib letters are usable.
3. Recovering a two-parameter key needs two observations. The keyspace size, $\phi(26) \times 26 = 312$, both explains the cipher's weakness and demonstrates the totient (§23.6) doing concrete counting work.
4. Verify by re-encrypting. A recovered key is only a break once it satisfies an independent second pair; checking against equation (2) is the proof, not the decryption itself.
5. Same math, different scale, opposite verdict. The very totient that exposes this toy is what secures RSA — the structure is shared; only the size of the modulus makes one breakable and the other not (Chapter 25).