Exercises: Cryptography — From Caesar Cipher to RSA

DataField.Dev

Exercises: Cryptography — From Caesar Cipher to RSA

These build from mechanical warm-ups (shift a few letters by hand) to full RSA round-trips, correctness proofs, code, and modeling. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md; do them before you peek. Every exercise stays inside what the chapter taught — the shift and substitution ciphers (§25.1), the key-distribution problem (§25.2), the public-key / trapdoor idea (§25.3), RSA's three algorithms (§25.4), the correctness proof via Euler and CRT (§25.5), and RSA's security and pitfalls (§25.6).

A working convention. Letters are numbered $A=0, B=1, \dots, Z=25$, exactly as in §25.1. "Reduce mod $n$ after every multiplication" is the §25.4 discipline; obey it in every hand computation.

Part A — Warm-ups (⭐)

25.1 † Encrypt the plaintext MATH with the shift cipher using key $k = 7$. Then decrypt your ciphertext with the same key to confirm you recover MATH. Show the arithmetic $c \equiv m + k \pmod{26}$ for each letter.

25.2 Caesar's cipher is the shift cipher with which specific key $k$? In one sentence, state the size of the shift cipher's key space and why one of those keys is useless.

25.3 † A substitution cipher uses an arbitrary permutation of the 26 letters as its key. State the size of its key space as a factorial, and give its approximate value and approximate bit-length (both appear in §25.1).

25.4 For the RSA hand example of §25.4 with $p = 5$, $q = 11$, compute $n$ and $\phi(n)$ from the definitions. Then list which of $e \in \{2, 3, 4, 5\}$ are legal public exponents, and for each illegal one name the condition it violates.

25.5 † You are told a public key is $(n, e) = (55, 3)$ and the matching private exponent is $d = 27$. Verify the key relationship $ed \equiv 1 \pmod{\phi(n)}$ by hand (you found $\phi(55)$ in 25.4), and say in one sentence what that congruence guarantees about encrypt-then-decrypt.

Part B — Prove it (⭐⭐)

25.6 † (Scaffolded — fill in the missing steps.) Complete the main-case RSA correctness proof of §25.5 for a message $m$ with $\gcd(m, n) = 1$. Fill each blank:

Because $ed \equiv 1 \pmod{\phi(n)}$ (by the choice of $d$ in key generation), there is an integer $k \ge 0$ with $ed = \underline{\hphantom{xxxxxx}}$.
Therefore $(m^e)^d = m^{ed} = m^{\,1 + k\phi(n)} = m \cdot \big(\underline{\hphantom{xxxxx}}\big)^{k}$.
Since $\gcd(m, n) = 1$, \underline{\hphantom{xxxxxxxxxx}}'s theorem gives $m^{\phi(n)} \equiv \underline{\hphantom{xx}} \pmod{n}$.
Substituting, $(m^e)^d \equiv m \cdot 1^{k} = \underline{\hphantom{xx}} \pmod{n}$. $\blacksquare$

State, in one final sentence, the one hypothesis on $m$ this argument needed and why §25.5 had to add a second proof to remove it.

25.7 Prove that the shift cipher's decryption inverts its encryption: for every $m \in \mathbb{Z}_{26}$ and every key $k$, decrypting $c \equiv m + k \pmod{26}$ by $m' \equiv c - k \pmod{26}$ recovers $m' = m$. Name the single algebraic property of $\mathbb{Z}_{26}$ that makes this work (the §25.1 🔗 Connection callout names it).

25.8 † Prove the direction of RSA security that is a theorem (not the assumption): if an attacker can factor the public modulus $n = pq$, then the attacker can recover the private exponent $d$ from the public key $(n, e)$. Make each step explicit, and name the chapter-23 algorithm used at the final step.

25.9 Prove that in RSA key generation a private exponent $d$ with $ed \equiv 1 \pmod{\phi(n)}$ exists if and only if $\gcd(e, \phi(n)) = 1$. (You may cite the modular-inverse existence criterion from Chapter 23, which itself comes from Bézout's identity in Chapter 22 — state which result you use at each direction of the "iff.")

25.10 † In the §25.5 general-case proof, the final step concludes $pq \mid (m^{ed} - m)$ from the two facts $p \mid (m^{ed} - m)$ and $q \mid (m^{ed} - m)$. Prove this implication, and exhibit a concrete counterexample showing it would fail if $p$ and $q$ were not coprime (e.g., take $p = q = 2$ and find an integer divisible by 2 but not by 4). State precisely where RSA's "distinct primes" requirement is doing the work.

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention. You may reuse mod_inverse and Python's three-argument pow exactly as the chapter does (pow(b, e, n) is the mod_pow of Chapter 23).

25.11 † Write shift_encrypt(text, k) and shift_decrypt(text, k) that implement the §25.1 shift cipher on uppercase A–Z (leave any non-letter untouched). Demonstrate that decrypting your encryption of "HELLO" with $k = 3$ returns "HELLO". Include the expected output.

25.12 Write letter_frequencies(text) returning (letter, count) pairs most-common-first for A–Z only (this is the attacker's first tool from §25.1). Run it in your head on the chapter's ciphertext "WKLV LV D VHFUHW PHVVDJH" and give the top three pairs as the expected output.

25.13 † Implement the three RSA routines from the Project Checkpoint — rsa_keygen_from_primes(p, q, e), rsa_encrypt(m, pub), rsa_decrypt(c, priv, n) — and use them to round-trip the message $m = 9$ with $p = 5$, $q = 11$, $e = 3$. Hand-derive every number in the expected output (you computed $d = 27$ in Part A). Hint: $9^3 = 729$; reduce mod $55$.

25.14 Write is_legal_public_exponent(e, p, q) that returns True exactly when $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$, for $n = pq$. (Use the Euclidean gcd from Chapter 22; do not import anything.) Give the expected output of calling it with $(e, p, q) = (3, 5, 11)$ and with $(4, 5, 11)$.

Part D — Find the error (⭐⭐)

Each "proof" or claim below is wrong. State precisely which part fails and why; where useful, give a tiny numeric counterexample.

25.15 † Claim: "RSA has been mathematically proven secure, because decryption provably inverts encryption (§25.5)." Identify the conflation of two different claims, and state precisely what §25.6 says RSA's security actually rests on (theorem vs. assumption).

25.16 A student writes the following decryption proof: "Since $ed \equiv 1 \pmod{\phi(n)}$, we have $ed = 1$, so $m^{ed} = m^{1} = m$. Done." This is the exact error flagged in §25.5's 🐛 Find the Error. Restate the mistake in your own words, and for the §25.4 hand example ($e=3, d=27, \phi=40$) compute the true value of $ed$ to show it is emphatically not 1.

25.17 † Claim: "A substitution cipher is secure because its key space, $26! \approx 4\times10^{26}$, is far too large for brute force." Explain why the large key space does not imply security, naming the specific §25.1 attack that breaks the cipher anyway and the single property of the cipher that the attack exploits.

25.18 Claim: "To make RSA faster, two colleagues agree to share the same modulus $n$ but use different public exponents $e_1, e_2$ (with their own private $d_1, d_2$). This is safe because each keeps their own private exponent secret." Identify the §25.6 pitfall this violates and state, in one sentence, what each colleague can now compute about the other.

Part E — Model it (⭐⭐⭐)

25.19 † (Model it.) A hospital network has $n = 1500$ devices that must all communicate pairwise and privately. Management proposes pre-sharing a unique symmetric key between every pair of devices. (a) Using the §25.2 counting, express the number of required keys as a binomial coefficient and evaluate it. (b) The network doubles to $3000$ devices; by what factor does the key count grow, approximately, and why (cite the $\binom{n}{2} \approx n^2/2$ reasoning)? (c) State, in two sentences, how switching to public-key cryptography changes the count and why (what disappears).

25.20 (Model it.) Translate the §25.3 "open padlock" analogy into the precise mathematical objects RSA uses. Make a three-column table whose rows are padlock you hand out, the physical key you keep, locking a box, and opening a locked box, mapping each to (column 2) the RSA object or operation and (column 3) the formula or key component from §25.4. Then state in one sentence which property of the underlying function ("easy forward, hard backward, easy-with-a-secret") makes the analogy faithful, and name that kind of function.

Part F — Conjecture and test (⭐⭐⭐)

25.21 † (Conjecture and test, then prove.) Textbook RSA is deterministic (§25.6): the same plaintext always encrypts to the same ciphertext. (a) Using the public key $(n, e) = (55, 3)$, write a few lines of Python that encrypt every message $m \in \{0, 1, \dots, 10\}$ and print the (m, c) pairs; hand-derive the expected output. (b) From your table, conjecture: is textbook RSA encryption injective on $\{0, \dots, n-1\}$ — i.e., do distinct messages always give distinct ciphertexts? (c) Prove or disprove your conjecture using the correctness theorem of §25.5. (Hint: if $m_1^e \equiv m_2^e \pmod n$, apply the decryption exponent $d$ to both sides.) (d) Explain in one sentence why injectivity is necessary for decryption to make sense, yet determinism is still a security flaw — the §25.6 lesson.

25.22 (Conjecture and test.) The §25.6 "small message, small exponent" leak: with $e = 3$, if the message $m$ satisfies $m^3 < n$ then $c = m^3$ with no modular wraparound, so an attacker just takes an integer cube root. (a) For $n = 3233$ (the chapter's modulus) and $e = 3$, find by hand the largest $m$ for which $m^3 < 3233$, and confirm that for that $m$, $c = m^3$ exactly (no reduction). (b) Write three lines of Python that, given such a $c$, recover $m$ by integer cube root (use round(c ** (1/3))), and give the expected output for your $c$. (c) State the §25.6 fix in one sentence.

Part G — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp. Pull only on results the book has established.

25.23 † (Ch. 24 + 25.) RSA decryption lives in $\mathbb{Z}_n$ with $n = pq$, $p \ne q$ prime. (a) Is $(\mathbb{Z}_n, +, \times)$ a field? Justify in one line by exhibiting a zero divisor. (b) For which $n$ is $\mathbb{Z}_n$ a field? (c) RSA's main-case correctness uses the group of units modulo $n$; state the order of that group and name the theorem (Chapter 24 or 23) that gives $m^{\phi(n)} \equiv 1$ for a unit $m$.

25.24 (Ch. 23 + 25.) Compute $d = e^{-1} \bmod \phi(n)$ for $e = 7$, $p = 11$, $q = 13$ using the extended Euclidean algorithm by hand. Show the table of $(\text{old\_r}, r, \text{old\_s}, s)$ rows, and verify your $d$ by checking $ed \equiv 1 \pmod{\phi(n)}$.

25.25 † (Ch. 23 + 25.) Decrypt the §25.4 ciphertext $c = 13$ under private key $d = 27$, $n = 55$ using fast modular exponentiation by repeated squaring — i.e., reproduce the chapter's computation of $13^{27} \bmod 55$. Write out the squarings $13^{1}, 13^{2}, 13^{4}, 13^{8}, 13^{16} \pmod{55}$, the binary expansion $27 = 16 + 8 + 2 + 1$, and the final product (reducing after every multiplication). Your answer must be $7$.

25.26 (Ch. 15 + 25.) The chapter notes (§25.1, §25.6) that key strength is a counting question. (a) A modern symmetric key is 128 bits; using Chapter 15's product rule, state its key-space size as a power of 2 and as an approximate power of 10. (b) Explain in two sentences why RSA's security is not measured by counting candidate private exponents $d$ (the way a symmetric key space is counted) but by the cost of factoring $n$. (Cite the §25.6 point that $d$ is unique.)

25.27 (Ch. 23 + 25 — Deep Dive.) The §25.5 high-speed decryption trick computes $c^d$ modulo $p$ and modulo $q$ separately and CRT-combines the results, for a roughly $4\times$ speedup. For the key $p = 5$, $q = 11$, $n = 55$, $d = 27$, $c = 13$: (a) compute $13^{27} \bmod 5$ and $13^{27} \bmod 11$ by hand (use Fermat's little theorem to shrink the exponent — note $13 \equiv 3 \pmod 5$ and $13 \equiv 2 \pmod{11}$); (b) CRT-combine the two residues into a value mod 55; (c) confirm it equals the $m = 7$ you got the slow way. State which §25.5 idea this is the computational realization of.

25.28 (Ch. 26 preview — Deep Dive.) RSA hides a message by making it infeasible to read; the next chapter fingerprints data instead. In one short paragraph, contrast the goal of RSA encryption with the goal of a hash function (do not implement anything — just state the difference in purpose, using only the framing of §25.6's closing and the chapter's What's Next).

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards: a clearly stated claim, the correct theorem invoked with its hypothesis named (Euler vs. Fermat vs. CRT — say which and why), reduction mod $n$ after every multiplication, and a clean conclusion. For each implementation, the rubric rewards a hand-derived # Expected output: and reuse of the canonical Toolkit signatures (mod_inverse, pow(b, e, n)).