Cryptography: Caesar, affine cipher and RSA

This week we see an application of the previous week (mod, GCD, Euclid). It is a final exam topic. The question types are fixed: “encrypt/decrypt with this cipher”, “find the inverse of a mod m”, “compute $a^n \bmod m$”, “generate an RSA key, encrypt, decrypt”. Since everything is a hand computation, the numbers are small. Golden rules:

1. Letters start at 0: A = 0, Z = 25. If you take A = 1, the whole answer shifts.
2. Take the mod at every intermediate step. Never let the numbers grow.
3. The modular inverse is found with the extended Euclidean algorithm, and you check it by multiplying and getting 1.
4. For a big exponent use fast exponentiation: write the exponent in binary and square in turn.
5. In RSA, $d$ is an inverse modulo $\varphi(n)$, not modulo $n$.

Basic concepts

The message to be kept secret is the plaintext, and its encrypted form is the ciphertext. Encryption is a function $f$, and decryption is its inverse $f^{-1}$. That is why the encryption function must be a bijection (the functions of week 4 come back here): if two different letters went to the same letter, you could not decrypt.

Shift cipher

$c = f(p) = (p + k) \bmod 26, \qquad p = f^{-1}(c) = (c - k) \bmod 26.$

The special case with $k = 3$ is called the Caesar cipher. Example: encrypt DERS with Caesar.

D E R S  ->  3  4 17 18
+3       ->  6  7 20 21
         ->  G  H  U  V

To decrypt, subtract 3. If the result is negative, add 26: for X = 23, $23 + 3 = 26 \equiv 0$ = A, and decrypting back, $0 - 3 = -3 \equiv 23$ = X.

This cipher is very weak: there are only 26 keys, and you can try them all. A faster way is frequency analysis: in English text the most common letter is E. If the most common letter in the ciphertext is H, then most likely $k = 7 - 4 = 3$. The same idea works for the affine cipher; you just solve a system of two equations with two unknowns ($a$ and $b$) from two letter matches.

Affine cipher

$c = (ap + b) \bmod 26, \qquad \gcd(a, 26) = 1.$

Why is the condition needed? To decrypt you have to “divide” by $a$, so you need the inverse $a^{-1}$ of $a$ mod 26. The inverse exists only if $\gcd(a, 26) = 1$. Decryption:

$p = a^{-1}(c - b) \bmod 26.$

Example: HI with $a = 5$, $b = 8$.

H = 7:  5*7 + 8 = 43,  43 mod 26 = 17  -> R
I = 8:  5*8 + 8 = 48,  48 mod 26 = 22  -> W
Ciphertext: RW

To decrypt you need $5^{-1} \bmod 26$. $5 \cdot 21 = 105 = 4 \cdot 26 + 1$, so $5^{-1} = 21$.

R = 17:  21 * (17 - 8) = 189,  189 mod 26 = 7   -> H
W = 22:  21 * (22 - 8) = 294,  294 mod 26 = 8   -> I

PITFALL · Writing “divide by 5”. There is no division in modular arithmetic. Instead of writing $(c - 8)/5$, you multiply by $5^{-1} = 21$. $9/5$ is not even an integer, but $21 \cdot 9 \bmod 26$ is perfectly an integer.

Modular inverse

$\bar{a}$ is the inverse of $a$ mod $m$: $a\bar{a} \equiv 1 \pmod m$.

Theorem. If $\gcd(a, m) = 1$, then $a$ has an inverse mod $m$.

Proof. Suppose gcd(a, m) = 1. By Bezout's identity there are
integers s and t with  s*a + t*m = 1.
Then s*a = 1 - t*m, so m | (s*a - 1), i.e. s*a ≡ 1 (mod m).
Hence s is an inverse of a modulo m. ∎

In plain words: if you find the Bezout coefficient, you have found the inverse. The method is the extended Euclidean algorithm. Example: $7^{-1} \bmod 40$.

40 = 5*7 + 5
 7 = 1*5 + 2
 5 = 2*2 + 1
Back:  1 = 5 - 2*2
         = 5 - 2*(7 - 5)        = 3*5 - 2*7
         = 3*(40 - 5*7) - 2*7   = 3*40 - 17*7
7 * (-17) ≡ 1 (mod 40)  ->  -17 + 40 = 23
Check: 7 * 23 = 161 = 4*40 + 1

TIP · check on the last line. After finding the inverse, compute $a \cdot \bar{a} \bmod m$. If it is not 1, a sign slipped while substituting back. A ten-second check saves the whole question.

Fast modular exponentiation (repeated squaring)

You don’t compute something like $5^{117} \bmod 23$ by multiplying 117 times. The idea: write $117$ in binary, find the powers $5^1, 5^2, 5^4, 5^8, \dots$ of $5$ by squaring in turn, and multiply the powers whose bit is 1. Take the mod at every step.

$117 = 64 + 32 + 16 + 4 + 1 = (1110101)_2$.

Result: $5^{117} \bmod 23 = 17$. Instead of 117 multiplications we did about 12. That is why the algorithm uses $O(\log n)$ multiplications.

RSA

RSA is a public key system: everyone knows the encryption key, and only the receiver knows the decryption key.

Key generation:

1. Choose two primes: $p$, $q$. $n = pq$.
2. Compute $\varphi(n) = (p-1)(q-1)$.
3. Choose an $e$ with $\gcd(e, \varphi(n)) = 1$.
4. Find $d = e^{-1} \bmod \varphi(n)$.
5. The public key is $(n, e)$, the private key is $d$.

Encryption and decryption:

$C = M^e \bmod n, \qquad M = C^d \bmod n.$

Worked example

$p = 13$, $q = 19$, $e = 5$, message $M = 42$.

n = 13 * 19 = 247
phi = 12 * 18 = 216
gcd(5, 216) = 1  -> e = 5 is valid
d = 5^-1 mod 216:  5 * 173 = 865 = 4*216 + 1  -> d = 173

Encrypt: C = 42^5 mod 247
42^2 = 1764 = 7*247 + 35          -> 35
42^4 = 35^2 = 1225 = 4*247 + 237  -> 237
42^5 = 237 * 42 = 9954 = 40*247 + 74 -> C = 74

Decrypt: 74^173 mod 247 = 42   (with fast exponentiation)

Why does it work? Because $ed \equiv 1 \pmod{\varphi(n)}$, we have $M^{ed} = M^{1 + k\varphi(n)}$. By Fermat’s little theorem, the factors $M^{\varphi(n)}$ collapse to 1 mod $p$ and mod $q$, leaving $M$. On the exam a computation is usually asked, not this proof.

Why is it secure? To find $d$ you need $\varphi(n)$, and for that you need $p$ and $q$. Factoring a small $n$ is easy, but in real RSA $n$ has hundreds of digits and factoring it is practically impossible.

Common mistakes