Day 77 — DH & RSA story (literacy)

Updated

July 30, 2026

Day 77 — Diffie–Hellman and RSA as mathematical stories

Stage VII · concept day
Goal: Follow the algebra of Diffie–Hellman key agreement and RSA encrypt/decrypt with toy parameters; state discrete log and factoring hardness as assumptions; practice parameter literacy; no production implementation.

Why this matters

Public-key ideas are applications of modular exponentiation, inverses, and Euler’s theorem. Understanding the story demystifies protocol diagrams. Misunderstanding leads to cargo-cult crypto. This day is mathematical literacy with toy numbers.

Important

Not production crypto. No implement-RSA lab, no “roll your own” protocol. Toy moduli only. Real systems use vetted libraries, padding schemes, modern curves/parameters, and constant-time engineering far beyond this course. Attack names appear as awareness only.

Theory

One-way intuition

A function \(f\) is easy to compute but hard to invert (informally) if \(y=f(x)\) is cheap given \(x\), yet recovering \(x\) from \(y\) is infeasible at scale.

Direction DH world RSA world
Easy \(g^a\bmod p\) given \(g,a,p\) \(m^e\bmod n\) given \(m,e,n\)
Believed hard (generic) Discrete log: given \(g,p,g^a\bmod p\), find \(a\) Factor \(n=pq\); or extract \(e\)-th roots without trapdoor

These are assumptions, not theorems you prove today.

Discrete logarithm problem (statement)

Definition (DLP). Given prime \(p\), generator (or base) \(g\), and \(h\equiv g^x\bmod p\), recover the secret exponent \(x\) (often in \(\{0,\ldots,p-2\}\)).

Hardness (literacy). For carefully chosen large \(p\) and \(g\), no efficient classical algorithm is known for general DLP; hardness is an assumption underlying DH and many classical public-key systems. (Quantum algorithms change the story — awareness only: Shor.)

Diffie–Hellman key exchange (math)

Public parameters: large prime \(p\) and base \(g\) (often a generator mod \(p\), or element of large order).

Protocol algebra:

  1. Alice picks secret \(a\), sends \(A\equiv g^a\bmod p\).
  2. Bob picks secret \(b\), sends \(B\equiv g^b\bmod p\).
  3. Alice computes \(K\equiv B^a=(g^b)^a=g^{ab}\bmod p\).
  4. Bob computes \(K\equiv A^b=(g^a)^b=g^{ab}\bmod p\).

Shared secret: \(K=g^{ab}\bmod p\).

Eavesdropper sees: \(p,g,A,B\). Computing \(K\) from these is the Computational Diffie–Hellman (CDH) problem; extracting \(a\) from \(A\) is DLP. CDH is not known to be equivalent to DLP in all groups, but both are believed hard in standard groups.

What DH does not provide alone: authentication (man-in-the-middle is a protocol issue). Literacy: math equality of keys ≠ full secure channel.

RSA key generation (math)

  1. Choose distinct large primes \(p,q\).
  2. Compute modulus \(n=pq\) and \(\varphi(n)=(p-1)(q-1)\) (or \(\lambda(n)=\mathrm{lcm}(p-1,q-1)\) in modern variants — awareness).
  3. Choose encryption exponent \(e\) with \(\gcd(e,\varphi(n))=1\) (common toy/historic \(e=3\) or \(65537\) in practice).
  4. Compute \(d\) with \(ed\equiv 1\pmod{\varphi(n)}\) (modular inverse via extended Euclid).
  5. Public key: \((n,e)\). Private key: \(d\) (and usually \(p,q\) retained for speed/CRT).

RSA encrypt / decrypt theorem

Message \(m\) with \(0\le m<n\) and typically \(\gcd(m,n)=1\) for the clean Euler argument (real systems use padding so \(m\) is structured).

  • Encrypt: \(c\equiv m^e\bmod n\).
  • Decrypt: \(m'\equiv c^d\bmod n\).

Theorem (RSA correctness, Euler form). If \(\gcd(m,n)=1\) and \(ed\equiv 1\pmod{\varphi(n)}\), then \[ m^{ed}\equiv m\pmod n. \] Proof sketch. \(ed=1+t\varphi(n)\), so \[ m^{ed}=m\cdot (m^{\varphi(n)})^t\equiv m\cdot 1^t\equiv m\pmod n \] by Euler’s theorem. (When \(\gcd(m,n)\neq 1\), correctness still holds for \(n=pq\) by CRT + Fermat on each prime factor — sketch: prove \(m^{ed}\equiv m\pmod p\) and mod \(q\).)

Parameter size literacy (order of magnitude)

Era / culture RSA modulus \(n\) Notes
Toy classroom \(10^2\)–\(10^4\) For hand arithmetic only
Historical 512-bit broken Do not use
Modern ballpark 2048-bit+ RSA common; 3072+ for long term Follow current standards, not this book
DH primes / groups Large safe primes or standard named groups Use standards

Moral: classroom \(n=55\) explains algebra; it provides zero security.

Attacks awareness (names only)

Know the names and one-line idea; do not implement:

Name One-line idea
Trial division / Fermat factoring Factor small or close \(p,q\)
Pollard’s rho / NFS Subexponential factoring families
Wiener’s attack Small private \(d\) vulnerable
Hastad broadcast Same \(m\), small \(e\), many moduli
Plain RSA without padding Multiplicative malleability; dictionary attacks on small \(m\)
Man-in-the-middle on raw DH No authentication of \(A,B\)
Timing / side channels Engineering leak of \(d\) or bits (not number theory alone)

What this day is not

  • Not a substitute for a cryptography engineering course.
  • Not a license to use raw RSA or textbook DH in software.
  • Not covering elliptic curves, AEAD, signatures, TLS handshake details.

Worked examples

Example 1 — Tiny DH.
\(p=23\), \(g=5\). Alice \(a=6\): \(A=5^6\bmod 23\). \(5^2=25\equiv 2\), \(5^4\equiv 4\), \(5^6=5^4\cdot 5^2\equiv 4\cdot 2=8\bmod 23\).
Bob \(b=15\): \(B=5^{15}\bmod 23\). (Compute stepwise: \(5^1=5\), \(5^2=2\), \(5^3=10\), \(5^4=4\), \(5^5=20\), … or binary.)
Shared: \(K=B^6\bmod 23=A^{15}\bmod 23\). Verify both paths with careful powering — the equality is the lesson.

Example 2 — Tiny RSA keygen.
\(p=5\), \(q=11\), \(n=55\), \(\varphi=4\cdot 10=40\). Choose \(e=3\) (\(\gcd(3,40)=1\)). Inverse: \(3d\equiv 1\pmod{40}\) ⇒ \(d=27\) because \(81\equiv 1\pmod{40}\).

Example 3 — RSA encrypt/decrypt.
\(m=7\), \(c=7^3=343\bmod 55\). \(343=6\cdot 55+13\) ⇒ \(c=13\). Decrypt: \(13^{27}\bmod 55\). Use successive squaring or Euler: since \(\gcd(13,55)=1\), \(13^{40}\equiv 1\), and \(27\) is smaller — compute carefully by hand or stepwise: \(13^2=169\equiv 4\pmod{55}\), \(13^4\equiv 16\), \(13^8\equiv 36\), etc. Final should return \(7\). (Do the full ladder in exercises.)

Example 4 — Why \(ed\equiv 1\pmod{\varphi(n)}\).
\(ed=1+t\varphi(n)\) feeds Euler directly. If you only had \(ed\equiv 1\pmod n\), that would be wrong modulus for exponents.

Example 5 — Failed \(e\).
\(n=55\), \(\varphi=40\), \(e=5\): \(\gcd(5,40)=5\neq 1\), no inverse \(d\).

Example 6 — DLP toy.
\(p=23\), \(g=5\), \(h=8\). Find \(x\) with \(5^x\equiv 8\pmod{23}\). From Example 1, \(x=6\) works. Brute force is fine for \(p=23\); impossible by hand for \(300\)-digit \(p\).

Example 7 — Correctness when \(\gcd(m,n)\neq 1\).
\(m=5\), \(n=55\), \(e=3\), \(d=27\). Then \(m\) shares factor with \(n\). Still \(m^{ed}\equiv m\pmod{55}\) holds by CRT argument — check numerically small powers if desired.

Example 8 — Parameter literacy.
A \(10\)-bit prime is \(\sim 3\) digits; a \(1024\)-bit modulus is \(\sim 308\) decimal digits. Classroom RSA is not “almost real.”

Exercises

A. Discrete log and DH

  1. State the discrete log problem carefully with all inputs/outputs.
  2. With \(p=11\), \(g=2\), compute \(2^a\bmod 11\) for \(a=1,\ldots,10\). Is \(g\) a generator?
  3. DH toy: \(p=11\), \(g=2\), \(a=4\), \(b=3\). Compute \(A\), \(B\), and shared \(K\) both ways.
  4. Why does an eavesdropper who can solve DLP break this DH instance?
  5. Explain MITM on DH in one paragraph (protocol, not algebra failure).

B. RSA keygen

  1. For \(p=7\), \(q=13\), compute \(n\), \(\varphi(n)\). Find an \(e\) with \(1<e<\varphi(n)\) and \(\gcd(e,\varphi)=1\). Compute \(d\).
  2. Same for \(p=11\), \(q=17\), \(e=7\).
  3. Show that \(e=21\) fails for \(n=55\) (\(\varphi=40\)).
  4. Prove: if \(ed\equiv 1\pmod{\varphi(n)}\) and \(\gcd(m,n)=1\) then \(m^{ed}\equiv m\pmod n\).
  5. Why is the private key \(d\) not simply \(1/e\) in rationals?

C. Encrypt/decrypt (toy)

  1. Using \(n=55\), \(e=3\), \(d=27\), encrypt \(m=8\) and decrypt the ciphertext (hand modular powering).
  2. Encrypt \(m=9\) with the same key; decrypt.
  3. Verify \(ed=81=2\cdot 40+1\).
  4. If someone publishes \(p\) and \(q\) by mistake, show how to compute \(d\) from \(e\).
  5. Explain why encrypting \(m=0\) or \(m=1\) is a terrible idea in textbook RSA (no padding).

D. Literacy and attacks (names)

  1. Match attack name to description: Wiener / Hastad / NFS / MITM / no padding.
  2. Why must \(p\) and \(q\) be large and not too close (Fermat factoring intuition)?
  3. Parameter literacy: roughly how many decimal digits is a \(2048\)-bit integer? (Use \(\log_{10}2\approx 0.301\).)
  4. List three things a production system needs beyond textbook RSA math.
  5. One paragraph: what hardness assumption underlies RSA confidentiality in the textbook model?

E. Stretch

  1. Prove RSA correctness via CRT: show \(m^{ed}\equiv m\pmod p\) and mod \(q\) when \(n=pq\), \(ed\equiv 1\pmod{\varphi(n)}\).
  2. Compute a full successive-squaring table for \(13^{27}\bmod 55\) from Example 3.
  3. Compare DH shared secret computation count (two exponentiations per party after receipt) vs RSA encrypt (one exp).
  4. If \(\varphi(n)\) is leaked but not \(p,q\), is recovering \(d\) from \(e\) easy? What about factoring from \(\varphi(n)\)?
  5. Write a half-page “threat model” paragraph separating math hardness from protocol/authentication/side channels.

Deep dive — RSA correctness via CRT (full sketch)

Let \(n=pq\), \(ed=1+t\varphi(n)=1+t(p-1)(q-1)\). Need \(m^{ed}\equiv m\pmod p\) and \(\pmod q\).

Mod \(p\): If \(p\mid m\) then both sides \(0\). If \(p\nmid m\), Fermat: \(m^{p-1}\equiv 1\pmod p\), so \[ m^{ed}=m\cdot m^{t(p-1)(q-1)}=m\cdot (m^{p-1})^{t(q-1)}\equiv m\cdot 1\equiv m\pmod p. \] Similarly mod \(q\). By CRT (since \(p,q\) coprime), \(m^{ed}\equiv m\pmod{n}\).

This removes the \(\gcd(m,n)=1\) hypothesis needed for the pure Euler argument.

Deep dive — what “hardness” means in this volume

Phrase Meaning here
“Believed hard” No efficient classical algorithm known for general large instances; not a theorem that none exists
“Toy breakable” Brute force / factoring by hand works
“Parameter literacy” Orders of magnitude for real moduli; not a security proof
“Attack name awareness” Recognize the failure mode in prose; no exploit development

Additional worked examples

Example 9 — Full tiny RSA cycle.
\(p=3,q=11,n=33,\varphi=20\). \(e=3\), \(d=7\) because \(21\equiv 1\pmod{20}\).
\(m=4\): \(c=4^3=64\equiv 31\pmod{33}\). Decrypt \(31^7\bmod 33\).
\(31\equiv -2\), \((-2)^7=-128\equiv -128+4\cdot 33=-128+132=4\pmod{33}\). ✓

Example 10 — DH shared secret equality.
Always \((g^b)^a=g^{ba}=g^{ab}=(g^a)^b\) in any abelian exponent arithmetic — the group is multiplicative mod \(p\).

Example 11 — Bad \(e\).
\(\varphi=20\), \(e=5\): \(\gcd(5,20)=5\neq 1\), inverse fails.

Example 12 — Public vs private.
Publishing \(n,e\) is intended. Publishing \(\varphi(n)\) essentially reveals factoring (solve for \(p,q\) from \(n\) and \(\varphi=(p-1)(q-1)\)).

Example 13 — Digit count.
\(2048\) bits: \(2048\cdot\log_{10}2\approx 2048\cdot 0.3010\approx 616\) decimal digits.

Example 14 — Dictionary attack on textbook RSA.
If \(m\) is a short PIN \(0000\)–\(9999\), attacker computes \(c'=m^e\bmod n\) for all PINs and compares to \(c\) — no factoring needed. Padding randomizes \(m\).

More exercises

  1. Keygen \(p=5,q=17\); choose \(e=3\) if valid; find \(d\); encrypt \(m=10\).
  2. Show recovering \(d\) from \(e,\varphi\) is extended Euclid.
  3. Explain why \(e=65537\) is popular (culture: high Hamming weight of \(2^{16}+1\) is \(2\) — fast public ops).
  4. DH with \(p=23,g=5,a=7,b=4\): compute \(A,B,K\).
  5. Given \(n=77\) and \(\varphi(n)=60\), factor \(n\) by solving quadratic for \(p,q\).
  6. List five things textbook RSA omits that TLS-class systems need (bullets).
  7. Write a half-page: “I will never implement RSA from this day for production because…”

Selected mini-solutions

  1. \(A=2^4=16\equiv 5\pmod{11}\), \(B=2^3=8\), \(K=8^4\bmod 11\) or \(5^3\bmod 11\).
  2. \(n=91\), \(\varphi=72\); e.g. \(e=5\), find \(d\) with \(5d\equiv 1\pmod{72}\).
  3. \(2048\cdot 0.301\approx 616\) digits.
  4. Successive squaring table for \(13^{27}\bmod 55\) should return \(7\).

Common pitfalls

Pitfall Fix
Thinking toy RSA is “educationally secure” Algebra ≠ security
Reducing exponents mod \(n\) Exponents reduce mod \(\varphi(n)\)
Implementing crypto from this chapter Use libraries and standards
Confusing DLP with factoring Different problems; both are assumptions
Forgetting authentication on DH Shared math key without identity binding
Leaking \(p,q\) or \(\varphi(n)\) Equivalent to breaking private key

Synthesis — DH/RSA literacy workout

S1. State DLP with all inputs/outputs; state CDH in one sentence.

S2. DH: \(p=19\), \(g=2\), \(a=5\), \(b=7\) — compute \(A,B,K\) (hand powering).

S3. RSA: \(p=7,q=19\); pick valid \(e\); find \(d\); encrypt \(m=5\).

S4. Prove Euler-form correctness \(m^{ed}\equiv m\pmod n\) when \(\gcd(m,n)=1\).

S5. Why is publishing \(\varphi(n)\) catastrophic?

S6. Match: Wiener / Hastad / MITM / no-padding — one-line each.

S7. Decimal digits in a \(3072\)-bit modulus (\(\log_{10}2\approx 0.3010\)).

S8. Write 6 sentences: boundary between this day’s algebra and production crypto engineering.

Checkpoint

  • Can run tiny DH and explain \(g^{ab}\)
  • Can keygen tiny RSA: \(n,e,d\) with \(ed\equiv 1\pmod{\varphi(n)}\)
  • Can encrypt/decrypt a toy message by hand
  • Can state DLP and RSA factoring assumptions
  • Knows attack names and parameter literacy orders of magnitude
  • Exercises A–D done; synthesis attempted

Two personal takeaways:

  1. …
  2. …

Deeper theory — RSA correctness checklist (both proofs)

Path A — Euler (needs \(\gcd(m,n)=1\)).
\(ed=1+t\varphi(n)\) ⇒ \(m^{ed}=m\cdot(m^{\varphi(n)})^t\equiv m\cdot 1\equiv m\pmod n\).

Path B — CRT (works for all \(m\)).
Prove \(m^{ed}\equiv m\pmod p\) and \(\pmod q\) separately via Fermat, then combine. This is the industrial-strength correctness story for textbook RSA math.

\(\lambda(n)\) note. Modern specs often use \(ed\equiv 1\pmod{\lambda(n)}\) with \(\lambda=\mathrm{lcm}(p-1,q-1)\mid\varphi(n)\). Same correctness; sometimes smaller \(d\). Awareness only.

Deeper theory — what the eavesdropper sees (DH)

Public transcript: \((p,g,A,B)=(p,g,g^a,g^b)\).
Passive adversary goals:

  1. Recover \(a\) or \(b\) (DLP).
  2. Recover \(K=g^{ab}\) without necessarily recovering \(a\) or \(b\) (CDH).
  3. Distinguish \(K\) from random (DDH — decision Diffie–Hellman; awareness).

Active adversary: can replace \(A\) or \(B\) (MITM) unless identities are bound by signatures/MACs — protocol layer, not pure algebra failure of \(g^{ab}=g^{ba}\).

Worked examples — complete toy cycles

Example 15 — Full DH with \(p=23\), \(g=5\), \(a=6\), \(b=5\).
\(A=5^6\equiv 8\pmod{23}\) (from earlier).
\(B=5^5=3125\bmod 23\): \(5^2\equiv 2\), \(5^4\equiv 4\), \(5^5\equiv 20\pmod{23}\).
Alice: \(K=B^a=20^6\bmod 23\). Bob: \(K=A^b=8^5\bmod 23\).
Compute \(20^2=400\equiv 9\pmod{23}\) (\(23\cdot 17=391\), \(400-391=9\)); continue carefully until both get the same \(K\). Equality is the check.

Example 16 — RSA full ladder \(n=55\), \(e=3\), \(d=27\), \(m=8\).
\(c=8^3=512\bmod 55\): \(55\cdot 9=495\), \(c=17\).
Decrypt \(17^{27}\bmod 55\) by successive squaring:
\(17^2=289\equiv 14\pmod{55}\) (\(55\cdot 5=275\), \(289-275=14\)),
\(17^4\equiv 14^2=196\equiv 31\), \(17^8\equiv 31^2=961\equiv 26\) (\(55\cdot 17=935\), \(961-935=26\)),
\(17^{16}\equiv 26^2=676\equiv 16\pmod{55}\) (\(55\cdot 12=660\)).
\(27=16+8+2+1\) ⇒ \(17^{27}\equiv 16\cdot 26\cdot 14\cdot 17\bmod 55\). Multiply step by step; result must be \(8\).

Example 17 — Factoring from \(\varphi\).
\(n=77\), \(\varphi=60\). Then \(p+q=n-\varphi+1=77-60+1=18\), \(pq=77\). Roots of \(t^2-18t+77=0\): \((t-7)(t-11)=0\). Factors \(7,11\).

Extra exercises — literacy with numbers

  1. DH: \(p=19\), \(g=2\), \(a=10\), \(b=3\) — compute \(A,B,K\).
  2. RSA: \(p=11\), \(q=13\), \(e=7\) — find \(d\); encrypt \(m=2\).
  3. Prove Path B correctness sketch mod \(p\) carefully for \(p\nmid m\) and \(p\mid m\).
  4. Show that if \(d\) is known and \(e,n\) public, recovering \(p,q\) is still not “immediate arithmetic” from \(d\) alone without more work — but leaking \(\varphi\) is enough (contrast).
  5. Parameter: how many bits in a number with \(100\) decimal digits? (Use \(\log_2 10\approx 3.322\).)
  6. List four production requirements beyond \(c=m^e\bmod n\).
  7. Explain malleability: given \(c=m^e\), attacker sends \(c'= (2^e)c\equiv (2m)^e\) — textbook RSA multiplies messages.
  8. Write a 8–10 sentence “I will use libraries because…” paragraph covering padding, side channels, parameter choice, and review.

Mini-solutions (selected)

  1. \(n=143\), \(\varphi=120\); \(7d\equiv 1\pmod{120}\) — extended Euclid for \(d\).
  2. \(100/\log_{10}2\approx 100/0.3010\approx 332\) bits.
  3. \((2m)^e=2^e m^e\equiv 2^e c\pmod n\).

Closing synthesis card

Story Algebra checkpoint
DH shared secret \(g^{ab}\) both ways
RSA \(d\) \(ed\equiv 1\pmod{\varphi(n)}\)
RSA decrypt \(m^{ed}\equiv m\pmod n\)
Hardness DLP / factoring assumptions
Practice Toy only; libraries in production

Tomorrow

Day 78 — Chinese Remainder Theorem.