Case Study: Building a Public-Key Note Drop from Scratch

"We stand today on the brink of a revolution in cryptography." — Whitfield Diffie and Martin Hellman, New Directions in Cryptography (1976)

Executive Summary

In the first case study you broke a careless RSA deployment. Here you will build one — carefully — end to end. The product is NoteDrop: a tiny service that lets anyone leave a private note for a recipient who has published a public key, with the recipient the only person able to read it. You will generate a key pair from chosen primes (§25.4), encode a short text message into integer blocks, encrypt each block to the public key, and decrypt with the private key — and then you'll bolt on the Chinese-Remainder-Theorem decryption speedup that real RSA libraries use (the §25.5 "right proof" turned into running code, a roughly $4\times$ win). Every number is hand-derived; nothing is executed.

This is the §25.4 Project Checkpoint grown into a complete, if miniature, system — the foundation the Chapter 39 capstone (Track A) extends with padding and signatures. Where Case Study 1 was an attacker's walkthrough, this is a builder's: you assemble each algorithm, state the correctness claim for it, and confirm the round trip by hand.

Skills applied

  • Implementing RSA key generation with the extended Euclidean algorithm for the private exponent (§25.4, Chapter 22–23).
  • Encoding text as integer message blocks with $0 \le m < n$, the precondition RSA requires (§25.4).
  • Encrypting and decrypting with fast modular exponentiation (pow(b, e, n) = the Chapter 23 mod_pow).
  • Building the CRT decryption path (§25.5) and arguing it returns the same plaintext, faster.
  • Stating, for each component, the correctness property it must satisfy and where the chapter proves it.

Background: from one checkpoint function to a usable tool

The §25.4 Project Checkpoint gave you three functions — rsa_keygen_from_primes, rsa_encrypt, rsa_decrypt — that round-trip a single integer. A usable note drop needs three more things around that core:

  1. a way to turn a string into a list of integers each below $n$ (encoding), and back (decoding);
  2. encryption/decryption of a whole message (a list of blocks), not one number;
  3. for realism, the CRT-accelerated decryption that production code uses.

We will build all three on top of the chapter's core, keeping the canonical Toolkit signatures so the pieces compose with dmtoolkit (§4 of the style bible). No new mathematics is needed — only the §25.4 algorithm and the §25.5 proof, assembled into a system.

🔗 Connection: This is the RSA thread's payoff state. Chapters 22–23 built numbertheory.py (mod_inverse, fast modular exponentiation); Chapter 24 began crypto.py; §25.4 completed the RSA core. NoteDrop is what that core is for: encrypting a real message to a published key, the thing the whole of Part IV was building toward.

Phase 1: Key generation

The recipient runs this once. Pick two distinct primes and a legal public exponent, then derive the private exponent with the extended Euclidean algorithm (§25.4). For a hand-traceable build, take $$p = 17,\quad q = 23,\quad e = 5.$$ Then $n = pq = 391$ and $\phi(n) = (p-1)(q-1) = 16\cdot 22 = 352$. Check the §25.4 legality condition: $\gcd(5, 352) = 1$ (since $352 = 5\cdot 70 + 2$, $5 = 2\cdot 2 + 1$, $2 = 2\cdot 1$, last nonzero remainder $1$). ✓ A private exponent therefore exists — exactly the §25.4 🔗 Connection: the condition in step 3 is what makes step 4 solvable.

Compute $d = 5^{-1} \bmod 352$ with the extended Euclidean algorithm. Running the chapter's mod_inverse loop (initial old_r, r = a % m, m = (5, 352)), the rows $(\text{old_r}, r, \text{old_s}, s)$ evolve as:

step $q = \lfloor \text{old\_r}/r\rfloor$ old_r r old_s s
init — 5 352 1 0
1 0 352 5 0 1
2 70 5 2 1 $-70$
3 2 2 1 $-70$ 141
4 2 1 0 141 $-352$

The loop stops when $r = 0$; it returns $\text{old\_s} \bmod m = 141 \bmod 352 = 141$. So $d = 141$. Verify: $ed = 5\cdot 141 = 705 = 2\cdot 352 + 1$, so $ed \equiv 1 \pmod{352}$. ✓

def mod_inverse(a, m):
    """Extended Euclidean algorithm (Chapter 22-23 Toolkit). Returns a^{-1} mod m."""
    old_r, r = a % m, m
    old_s, s = 1, 0
    while r != 0:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
    return old_s % m

def rsa_keygen_from_primes(p, q, e):
    """Public/private key pair from primes p, q and exponent e (Project Checkpoint, 25.4)."""
    n = p * q
    phi = (p - 1) * (q - 1)
    d = mod_inverse(e, phi)            # exists iff gcd(e, phi) == 1
    return (n, e), d

pub, d = rsa_keygen_from_primes(17, 23, 5)
print(pub, d)
# Expected output:
# (391, 5) 141

The correctness claim for this phase. The returned $d$ satisfies $ed \equiv 1 \pmod{\phi(n)}$ because mod_inverse returns the Bézout coefficient of $e$ from the extended Euclidean algorithm, and that coefficient is the modular inverse exactly when $\gcd(e, \phi(n)) = 1$ — the existence criterion proved in Chapter 23. Without that gcd condition, the inverse would not exist and the build would be ill-defined.

The recipient publishes $(n, e) = (391, 5)$ and keeps $d = 141$ (and discards/guards $p, q, \phi$, per §25.4 — each reveals $d$).

🔄 Check Your Understanding Why was $e = 5$ a legal choice here but $e = 2$ would not be? Compute $\gcd(2, 352)$.

Answer

$352$ is even, so $\gcd(2, 352) = 2 \ne 1$. By the §25.4 condition (and the Chapter 23 existence criterion), no inverse of $2$ modulo $352$ exists, so there would be no private exponent — the key generation would fail. $e$ must be coprime to $\phi(n)$; $5$ is, $2$ is not.

Phase 2: Encoding text into message blocks

RSA encrypts an integer $m$ with $0 \le m < n$ (§25.4). Our modulus is small ($n = 391$), so we encode one character per block using its ASCII code, which for uppercase letters lies in $65$–$90$ — safely below $391$, and (unlike the $A=0,\dots,Z=25$ scheme) large enough to avoid the §25.6 tiny-message trap for these toy parameters. The sender will drop the note "HI".

Character ASCII code = block $m$ $m < n = 391$?
H 72 yes
I 73 yes 
def encode(text):
    """Turn a string into a list of integer blocks (one char each) via ASCII codes."""
    return [ord(ch) for ch in text]

def decode(blocks):
    """Inverse of encode: integer blocks back to a string."""
    return "".join(chr(b) for b in blocks)

print(encode("HI"))
# Expected output:
# [72, 73]

⚠️ Common Pitfall: Each block must be strictly less than $n$. If we tried to pack two characters into one block (e.g., $72\cdot 256 + 73 = 18505$), the block would exceed $n = 391$ and encryption would silently lose information — $m$ and $m + n$ encrypt identically. Real RSA uses a modulus thousands of bits wide precisely so that large, padded blocks still satisfy $0 \le m < n$. Here, with a tiny $n$, one character per block is the safe choice.

Phase 3: Encrypt the whole message

Encrypting a message is just encrypting each block with $c \equiv m^{e}\bmod n$ (§25.4). With $e = 5 = (101)_2 = 4 + 1$, each block needs two squarings and one multiply.

Block H ($m = 72$): $$72^{2} = 5184 \equiv 101,\quad 72^{4} = 101^{2} = 10201 \equiv 35,\quad 72^{5} = 35\cdot 72 = 2520 \equiv 174 \pmod{391}.$$ (Reductions: $5184 = 13\cdot 391 + 101$; $10201 = 26\cdot 391 + 35$; $2520 = 6\cdot 391 + 174$.)

Block I ($m = 73$): $$73^{2} = 5329 \equiv 246,\quad 73^{4} = 246^{2} = 60516 \equiv 302,\quad 73^{5} = 302\cdot 73 = 22046 \equiv 150 \pmod{391}.$$ (Reductions: $5329 = 13\cdot 391 + 246$; $60516 = 154\cdot 391 + 302$; $22046 = 56\cdot 391 + 150$.)

So the encrypted note is the block list $[174, 150]$.

def rsa_encrypt(m, pub):
    n, e = pub
    return pow(m, e, n)                      # m^e mod n  (fast modular exponentiation)

def encrypt_message(text, pub):
    return [rsa_encrypt(m, pub) for m in encode(text)]

cipher = encrypt_message("HI", pub)          # pub = (391, 5)
print(cipher)
# Expected output:
# [174, 150]

💡 Intuition: Encryption is the "snap the padlock shut" step of §25.3 applied block by block. Anyone with the public key $(391, 5)$ can produce $[174, 150]$; only the holder of $d = 141$ can turn it back into "HI". The note can now cross any wire the eavesdropper controls.

Phase 4: Decrypt — the straightforward way

The recipient applies $m \equiv c^{d}\bmod n$ to each block (§25.4). By the §25.5 correctness theorem this returns the original blocks, hence the original text. We trust the theorem, but let us confirm one block independently in Phase 5 via CRT; for now, the contract is:

def rsa_decrypt(c, priv, n):
    return pow(c, priv, n)                   # c^d mod n

def decrypt_message(cipher, d, n):
    return decode([rsa_decrypt(c, d, n) for c in cipher])

plain = decrypt_message([174, 150], d, pub[0])   # d = 141, n = 391
print(plain)
# Expected output:
# HI

The blocks decrypt to $72, 73$, which decode maps back to "HI". The round trip closes because $ed = 705 \equiv 1 \pmod{352}$, so by §25.5, $(m^{e})^{d}\equiv m \pmod{391}$ for every block — even were a block $0$ or a multiple of $17$ or $23$, the general-case (CRT) proof covers it.

Phase 5: The CRT decryption speedup (build the "right proof" into code)

Real RSA libraries do not decrypt with one big $c^{d}\bmod n$. They use the recipient's secret factors $p, q$ to decrypt modulo each prime and recombine with the Chinese Remainder Theorem — the exact structure of the §25.5 general-case proof, and about $4\times$ faster because the exponents and moduli are half-size. Let us build it and check it recovers the same block.

The method, for a ciphertext block $c$ with private factors $p, q$ and exponent $d$:

  1. Reduce the exponent modulo each prime's order using Fermat: compute $d_p = d \bmod (p-1)$ and $d_q = d \bmod (q-1)$. Here $d_p = 141 \bmod 16 = 13$ (since $141 = 8\cdot 16 + 13$) and $d_q = 141 \bmod 22 = 9$ (since $141 = 6\cdot 22 + 9$).
  2. Compute the two partial plaintexts $m_p = c^{d_p}\bmod p$ and $m_q = c^{d_q}\bmod q$.
  3. Recombine $m_p, m_q$ into $m \bmod n$ with CRT.

Take the first block, $c = 174$.

Mod $p = 17$: $174 \equiv 4 \pmod{17}$ (since $174 = 10\cdot 17 + 4$). Then $m_p = 4^{13}\bmod 17$. Squaring: $4^{2} = 16 \equiv -1$, so $4^{4} \equiv 1$, hence $4^{13} = 4^{8}\cdot 4^{4}\cdot 4^{1} \equiv 1\cdot 1\cdot 4 = 4$. So $m_p = 4$.

Mod $q = 23$: $174 \equiv 13 \pmod{23}$ (since $174 = 7\cdot 23 + 13$). Then $m_q = 13^{9}\bmod 23$. Squaring: $13^{2} = 169 \equiv 8$; $13^{4} = 8^{2} = 64 \equiv 18 \equiv -5$; $13^{8} = (-5)^{2} = 25 \equiv 2$; so $13^{9} = 13^{8}\cdot 13 \equiv 2\cdot 13 = 26 \equiv 3$. So $m_q = 3$.

CRT recombine: find $m$ with $m \equiv 4 \pmod{17}$ and $m \equiv 3 \pmod{23}$, $0 \le m < 391$. The answer is $m = 72$: indeed $72 = 4\cdot 17 + 4 \equiv 4 \pmod{17}$ and $72 = 3\cdot 23 + 3 \equiv 3 \pmod{23}$. This matches the Phase-4 plaintext block H = 72 exactly — by a completely independent computation, confirming the round trip.

def crt(residues, moduli):
    """Chinese Remainder Theorem (Chapter 23 numbertheory.crt). Smallest nonneg solution."""
    N = 1
    for mod in moduli:
        N *= mod
    x = 0
    for r, mod in zip(residues, moduli):
        Ni = N // mod
        x += r * Ni * mod_inverse(Ni, mod)
    return x % N

def rsa_decrypt_crt(c, p, q, d):
    """Decrypt one block via CRT: ~4x faster than c^d mod (p*q)."""
    mp = pow(c, d % (p - 1), p)              # c^d mod p, exponent shrunk by Fermat
    mq = pow(c, d % (q - 1), q)              # c^d mod q
    return crt([mp, mq], [p, q])            # recombine to m mod p*q

print(rsa_decrypt_crt(174, 17, 23, 141))
# Expected output:
# 72

The CRT path returns $72$ — the same block as Phase 4's pow(174, 141, 391) — but it raised $174$ to the 13th and 9th powers modulo small primes instead of to the 141st power modulo $391$. That is the §25.5 insight ("prove it mod $p$, prove it mod $q$, glue with CRT") turned into a real performance optimization.

🔗 Connection: This is the precise reason §25.5 bothered with the harder, CRT-based proof instead of stopping at the Euler-only "main case." The general proof is not just more rigorous — it is the blueprint for how fast RSA actually decrypts. The math you proved and the code that ships are the same structure.

🔄 Check Your Understanding Run the CRT path on the second block, $c = 150$, and confirm it returns $73$. (You need $150 \bmod 17$, $150 \bmod 23$, then $4^{13}\bmod 17$ and the corresponding power mod 23.)

Answer

$150 \equiv 14 \pmod{17}$ (since $150 = 8\cdot 17 + 14$) and $150 \equiv 12 \pmod{23}$ (since $150 = 6\cdot 23 + 12$). The CRT recombination of $m_p$ and $m_q$ yields $73$ — matching I = 73 from Phase 4. (You can shortcut the check: the answer must satisfy $73 \bmod 17 = 5$ and $73 \bmod 23 = 4$, so the partial plaintexts are $m_p = 5$, $m_q = 4$, and CRT on $(5 \bmod 17,\ 4 \bmod 23)$ gives $73$.)

Discussion Questions

  1. NoteDrop encodes one character per block because $n = 391$ is tiny. With a realistic 2048-bit modulus, roughly how many bytes could safely fit in one block, and why does block size scale with $\lceil \log_2 n\rceil$? (Cite the $0 \le m < n$ requirement of §25.4.)
  2. The CRT decryption in Phase 5 needs the secret factors $p$ and $q$, which §25.4 told us to discard or guard. Reconcile this: real implementations keep $p, q$ in the private key precisely for the CRT speedup. What is the security trade-off, and what must never leak?
  3. Phase 5 raised $174$ to the $13$th and $9$th powers instead of the $141$st. For a real key with a 1024-bit $d$, the CRT exponents $d_p, d_q$ are about 512 bits each. Using Chapter 23's cost of modular exponentiation (cubic in the bit length per the schoolbook estimate), argue why this gives the famous "roughly $4\times$" speedup.
  4. NoteDrop, as built, is still textbook RSA — deterministic, unpadded. Which Case Study 1 attack would read a NoteDrop message if the message space were small? What single addition (named in §25.6) would defeat it, and why does it not change the correctness argument of Phases 4–5?
  5. Where, in this build, did the choice "$p$ and $q$ distinct" matter? Point to the specific step (Phase 1 or Phase 5) and tie it to the §25.5 proof's final CRT gluing.

Your Turn: Extensions

  • Option A (generate the primes). The §25.4 Project Checkpoint notes a full rsa_keygen(bits) that generates random primes of a given bit length using primality testing from numbertheory.py. Write the wrapper (do not execute it): pick a bit length, sketch how you would draw a random odd integer and test it for primality, and explain why two fresh, independent primes per key pair matters (recall the §25.6 "never share a modulus" pitfall).
  • Option B (round-trip a full word). Extend the hand build to encrypt "YES" (ASCII $89, 69, 83$) under $(391, 5)$. Compute all three ciphertext blocks by repeated squaring, then verify one of them decrypts correctly via the CRT path. Tabulate your work like Phase 3.
  • Option C (add the signature mode — toward Chapter 39A). §25.6 notes that RSA run backwards — signer raises the message to $d$, anyone verifies by raising to $e$ — produces a digital signature. Using the NoteDrop key, "sign" the block $m = 72$ by computing $s = 72^{141}\bmod 391$ (use the CRT path), then verify $s^{5} \equiv 72 \pmod{391}$. Explain in one sentence why only the holder of $d$ could have produced $s$. This is the seed of Capstone Track A.
  • Option D (encoding robustness). Replace the one-char-per-block encode with a base-256 packing that fits as many bytes as $n$ allows, with explicit padding to a fixed block width. State the invariant your encode/decode pair must satisfy (decode∘encode = identity) and the bound each block must respect ($0 \le m < n$).

Key Takeaways

  1. RSA is small enough to build in full. Key generation (extended Euclid for $d$), encoding, encryption ($m^{e}\bmod n$), and decryption ($c^{d}\bmod n$) compose into a working public-key tool in a few dozen lines — the §25.4 core wrapped in encoding and message handling.
  2. Each component has a stated correctness contract. mod_inverse returns $d$ with $ed \equiv 1 \pmod{\phi(n)}$ *because* $\gcd(e,\phi(n))=1$ (Chapter 23); the round trip closes because of the §25.5 theorem. Build, then state why it is right.
  3. The CRT decryption is the §25.5 proof, executed. Decrypting mod $p$ and mod $q$ and gluing with CRT is both the rigorous general-case proof and the real-world $\sim 4\times$ speedup — the same structure, doing double duty.
  4. Block size is governed by $0 \le m < n$. Encoding must keep every block below the modulus; this is why real RSA uses thousands-of-bit moduli and why our toy build encodes one character at a time.
  5. A correct build is not yet a secure one. NoteDrop works perfectly and is still textbook RSA — deterministic and unpadded. Correctness (Phases 4–5) and security (the §25.6 additions: padding, standard exponent, fresh modulus) are separate jobs; Chapter 39's capstone adds the second.