Secret codes are the oldest application of modular arithmetic. Number the letters $A = 0, B = 1, \dots, Z = 25$ and calculate mod 26. Encrypting is multiplying and adding; decrypting is undoing that, which needs a modular inverse.
Shift cipher (Caesar's): $E(x) = x + b \bmod 26$, undone by $D(y) = y - b$. Affine cipher: $$E(x) = ax + b \bmod 26, \qquad D(y) = a^{-1}(y - b) \bmod 26.$$ The key is the pair $(a, b)$, and $a$ must satisfy $\gcd(a, 26) = 1$.
Why it works
Worked example: Encrypting
- M, A, T, H are $12, 0, 19, 7$.
- $5 \cdot 12 + 8 = 68 \equiv 16$, $\ 5 \cdot 0 + 8 = 8$, $\ 5 \cdot 19 + 8 = 103 \equiv 25$, $\ 5 \cdot 7 + 8 = 43 \equiv 17$.
- $16, 8, 25, 17$ are Q, I, Z, R.
Answer: QIZR.
Worked example: Decrypting
- $5^{-1} \equiv 21 \pmod{26}$, since $5 \cdot 21 = 105 = 4 \cdot 26 + 1$. So $D(y) = 21(y - 8)$.
- Q $= 16$: $21 \cdot 8 = 168 \equiv 12$ (M). I $= 8$: $21 \cdot 0 = 0$ (A).
- Z $= 25$: $21 \cdot 17 = 357 \equiv 19$ (T). R $= 17$: $21 \cdot 9 = 189 \equiv 7$ (H).
Answer: MATH.
Worked example: A bad key
- $13 \cdot 0 = 0$ and $13 \cdot 2 = 26 \equiv 0$, so A and C get the same cipher letter (for any $b$).
- In fact $13x \bmod 26$ is only ever $0$ or $13$, so the cipher uses just two letters.
Answer: $\gcd(13, 26) = 13 \ne 1$.
| $a$ | 1 | 3 | 5 | 7 | 9 | 11 | 15 | 17 | 19 | 21 | 23 | 25 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $a^{-1} \bmod 26$ | 1 | 9 | 21 | 15 | 3 | 19 | 7 | 23 | 11 | 5 | 17 | 25 |
Common mistake
An affine cipher is also weak against a known-plaintext attack: if Eve learns that two plaintext letters $x_1, x_2$ encrypt to $y_1, y_2$, she solves the two congruences $ax_1 + b \equiv y_1$ and $ax_2 + b \equiv y_2$. Subtracting gives $a(x_1 - x_2) \equiv y_1 - y_2 \pmod{26}$, a linear congruence for $a$, and then $b$ follows.
Key idea