Chapter 25 — Key Takeaways

Cryptography: From Caesar Cipher to RSA. The one-page card to reread before an exam.

Core definitions

Term One-line definition
Cipher An (encrypt, decrypt) algorithm pair, keyed by a secret; decrypt(encrypt(m)) = m.
Plaintext / ciphertext The message before / after encryption.
Symmetric-key crypto Same shared secret encrypts and decrypts (fast; needs pre-shared key).
Public-key crypto A pair per party: public key (encrypts, published) + private key (decrypts, secret).
Trapdoor function Easy forward, infeasible to invert — except with a secret trapdoor.
Key generation The procedure producing a matched (public, private) key pair.
RSA Public-key system whose trapdoor is "easy to multiply primes, hard to factor the product."
Digital signature (intro) RSA run backwards: sign with $d$, verify with $e$; proves authorship.

Classical ciphers — and exactly how each dies

Cipher Encrypt rule Key space Break
Shift (Caesar = shift 3) $c \equiv m + k \pmod{26}$ 26 brute force (≤ 25 shifts)
Substitution apply a permutation of A–Z $26! \approx 4\times10^{26}$ frequency analysis — structure leaks
Affine (mention) $c \equiv am+b \pmod{26}$, $\gcd(a,26)=1$ $12 \times 26 = 312$ brute force / frequency

Rules of thumb - Always size the key space first. Small key space ⇒ brute force wins. - A large key space is necessary, not sufficient: if the cipher preserves structure (letter frequencies), frequency analysis ignores the key space entirely. - Kerckhoffs's principle: assume the attacker knows the algorithm; only the key is secret.

The two problems public-key crypto solves

Problem Why symmetric crypto fails Public-key fix
Key distribution needs a pre-shared secret; sending it over an open channel needs another secret (infinite regress) publish a lock (public key); keep the key (private key) — no shared secret
Scaling $n$ parties need $\binom{n}{2} = \frac{n(n-1)}{2}$ pairwise keys ($\approx 5\times10^5$ for $n=1000$) $n$ key pairs total — one per party

RSA — the whole system on one line each

Stage Formula / step
Pick primes distinct primes $p, q$; modulus $n = pq$
Totient $\phi(n) = (p-1)(q-1)$
Public exponent choose $e$, $1 < e < \phi(n)$, $\gcd(e, \phi(n)) = 1$ (often $e = 65537$)
Private exponent $d \equiv e^{-1} \pmod{\phi(n)}$ (extended Euclidean algorithm)
Public key $(n, e)$ — published
Private key $d$ — secret; destroy/guard $p, q, \phi(n)$
Encrypt $c \equiv m^{e} \pmod{n}$, for $0 \le m < n$
Decrypt $m \equiv c^{d} \pmod{n}$

Why it works (correctness): $ed \equiv 1 \pmod{\phi(n)} \Rightarrow ed = 1 + k\phi(n) \Rightarrow m^{ed} = m\,(m^{\phi(n)})^{k} \equiv m \pmod n$. - Main case $\gcd(m,n)=1$: Euler's theorem ($m^{\phi(n)} \equiv 1$). - All $m$: prove $m^{ed}\equiv m \pmod p$ and $\pmod q$ (Fermat + the trivial $p\mid m$ case), then glue with the Chinese Remainder Theorem (needs $p \ne q$).

Why it's secure: recovering $d$ from $(n,e)$ is as hard as factoring $n$ — an assumption, not a theorem. - Theorem direction: factor $n$ ⇒ compute $\phi(n)$ ⇒ invert $e$ ⇒ get $d$ ⇒ broken. - Assumption direction: no feasible attack avoids factoring (unproven; akin to trusting P ≠ NP).

Worked numbers to recognize

Example Values
Tiny (hand-traceable) $p=5, q=11, n=55, \phi=40, e=3, d=27$ (since $3\cdot27=81\equiv1$); $m=7 \to c=13 \to m=7$
Standard small $p=61, q=53, n=3233, \phi=3120, e=17, d=2753$; $m=65 \to c=2790 \to m=65$

Verify a private exponent fast: $17 \cdot 2753 = 46801 = 15\cdot3120 + 1$. ✓

Decision aid: "which idea applies?"

Situation Use
Need to share a secret with someone you've never met, over an open wire public-key (RSA)
Bulk-encrypt a large file quickly between two parties who already share a key symmetric (real systems use RSA to exchange a symmetric key, then AES)
Prove you wrote a message (not hide it) digital signature: sign with $d$, verify with $e$
Show a modular-exponent identity for composite $n = pq$ split mod $p$, mod $q$; recombine via CRT
Decide if $d = e^{-1} \bmod \phi(n)$ exists check $\gcd(e, \phi(n)) = 1$

Common pitfalls

Pitfall Fix
Computing $c^d$ as one giant integer use fast modular exponentiation (repeated squaring; Python pow(c,d,n))
Reducing mod $n$ only at the end of a product re-reduce after every multiplication
Treating $ed \equiv 1 \pmod{\phi(n)}$ as $ed = 1$ it means $ed = 1 + k\phi(n)$; the extra $(m^{\phi(n)})^k$ collapses via Euler/Fermat
Deploying textbook RSA ($c=m^e$ only) it's deterministic ⇒ leaks; real RSA adds random padding (OAEP)
Small $e$ with small $m$ (e.g. $e=3$, $m^3 < n$) no wraparound ⇒ integer cube root recovers $m$; padding prevents tiny $m$
Sharing a modulus $n$ across users each user computes others' $d$; every key pair needs a fresh $n$
Proving correctness only for $\gcd(m,n)=1$ patch with the CRT argument so it holds for all $m$

Toolkit additions (crypto.py)

Function Signature Returns
Key gen (from primes) rsa_keygen_from_primes(p, q, e) ((n, e), d) — needs $\gcd(e,(p-1)(q-1))=1$
Key gen (full API) rsa_keygen(bits) random-prime key pair (uses Ch.23 primality test)
Encrypt rsa_encrypt(m, pub) $m^e \bmod n$ via pow(m, e, n)
Decrypt rsa_decrypt(c, priv, n) $c^d \bmod n$ via pow(c, priv, n)

Reuses mod_inverse and fast pow/mod_pow from numbertheory.py (Ch.22–23). Feeds Capstone Track A (Ch.39): an RSA encryption + signature system.

Prerequisite results this chapter leans on

From Result used in RSA
Ch.22 Euclidean / extended Euclidean algorithm; Bézout's identity (⇒ inverse exists iff coprime)
Ch.23 modular arithmetic; modular inverse; fast modular exponentiation; Euler's & Fermat's theorems; CRT; totient $\phi(pq)=(p-1)(q-1)$
Ch.24 $\mathbb{Z}_n$ ring/field structure; group of units has order $\phi(n)$; $\mathbb{Z}_n$ is a field iff $n$ prime
Ch.15 keyspace / key-size sizing
Ch.16 $26!$ substitution keys; $\binom{n}{2}$ pairwise symmetric keys