Public-key & signatures

Prerequisites

• Modular arithmetic: reduction, modular inverses, and modular exponentiation
• Primes, factoring, and the greatest common divisor
• Cryptographic hash functions as fixed-length message digests
• The difference between encryption and digital signatures, at a conceptual level
• Slope of the line through two points (for the chord-and-tangent rule)
• For the extension: vectors, a basis, and the idea of a short lattice vector

Learning outcomes

1. Students will be able to compute an RSA keypair (n, φ(n), e, d) from two small primes and explain why d is taken as the inverse of e modulo φ(n).
2. Students will be able to demonstrate that textbook RSA is deterministic and malleable, and contrast it with randomized RSA-OAEP encryption of the same plaintext.
3. Students will be able to trace how Håstad's broadcast attack and Bleichenbacher's padding-oracle attack recover plaintext without the private key, and identify the exponent or padding choice each attack exploits.
4. Students will be able to perform elliptic-curve point addition and scalar multiplication over the reals and over a finite field, and compare double-and-add with repeated addition to explain why reversing k·P (the ECDLP) is hard.
5. Students will be able to derive an ECDSA private key from two signatures that reuse a nonce, and justify how RFC 6979 deterministic nonces block that recovery.

Sequence

Educational RSA: Runs about 29 minutes against the 25 planned. The earlier figure came from a cut-savings claim rather than a recount, and some of those savings were Fix / Extend items, which are homework and cost no class time; counted step by step, the cut freed about four minutes, not ten.

Each exhibit opens in its own site. Roles: Intro builds the idea, Break it has students cause the failure, Fix shows the construction that holds, and Extension is optional depth.

Hand-out: every worksheet in this module, in sequence order

What students hand in

Accept-or-reject sheet. A verdict of accept or reject on each scheme the sequence exercises, each verdict tied to a value from the student's own Record tables rather than to a claim printed on the page. Each reject has to name the failure it rests on and what an observer learns from published values alone; each accept has to name what the page says that acceptance still depends on.

It is drawn from what the worksheets already produce, so it adds no new task. Values differ from run to run, so there is no key to mark against: what a marker is reading is whether each claim is tied to something the student recorded, and whether the reasoning from it holds.

Discussion questions

1. Textbook RSA and RSA-OAEP both compute m^e mod n. What does OAEP's randomized padding change about what an eavesdropper or attacker learns, and which of the attacks you ran in Educational RSA and RSA Forge would it stop?
2. The weak RSA key, the factoring wall and the subgroup walk each fall quickly on toy parameters. Why does an attack that works on small numbers not show that RSA or elliptic-curve cryptography is broken, and what decides how long the same attack takes at real sizes?
3. Bleichenbacher's oracle answers only 'conformant' or 'not conformant'. Why is one bit per query enough to recover the plaintext, and what does that imply for how a server should handle decryption errors?
4. ECDSA nonce reuse and (in the extension) the nonce-lattice attack both recover d from public signatures. What does each attacker need, which failure does RFC 6979 remove from the trust path, and what does it leave to the implementation?
5. Given the trade-offs the labs present (key and signature size, padding pitfalls, nonce fragility, deterministic signing), when would you choose RSA-PSS, ECDSA with RFC 6979, or Ed25519 for a new signing system?

Instructor notes

These notes are public, and they are conceptual on purpose: they describe what students should notice and why, never the specific values a run produces.

Expected observations

• Educational RSA: Generate lists p, q, n, φ(n), e and d as a trace; the mod-n clock shows e·d written as a multiple of φ plus one; ticking the tamper checkbox flips the signature verdict from VALID to INVALID. Re-derived against the live page 2026-09-22.
• Educational RSA: 'Factor it!' breaks the small key and shows the recovered primes, the reconstructed d and a decryption made with it, while the 2048-bit card's button stays disabled and its cost is labeled a projection that is never run. Encrypting the same text twice with textbook RSA repeats the ciphertext, the OAEP comparison does not, and the malleability rows show a ciphertext product decrypting to a·b. The square-and-multiply trace opens on the small exponent and reports four operations against a naive three, so read it as the comparison the page prints rather than as a saving; the saving appears once the real exponent is selected. Re-derived against the live page 2026-09-22.
• RSA Forge: in Pick Your Config, the e = 3 / no-padding choice has its message recovered, while the e = 65537 / OAEP choice runs the same CRT and cube-root steps and does not recover it; the manual Håstad flow shows N, M = m³ and the recovered message. Every error this exhibit reports — pressing a button out of order included — is announced only to a screen reader, so an out-of-order press looks like a dead button. Press in the order the worksheet gives. Re-derived against the live page 2026-09-22.
• RSA Forge: during the Bleichenbacher run the interval bar narrows and plaintext bytes light up left to right, and the result is checked by re-encryption; in You Are the Oracle mode a wrong answer can steer the attack to a value the page flags as not verified. Re-derived against the live page 2026-09-22.
• EC Point Arithmetic: the construction and the λ, x₃, y₃ readout update together as P and Q move; the 𝔽ₚ view applies the same law to a lattice of points; double-and-add reaches the same k·G as repeated addition with far fewer operations, and repeated addition declines a large k while saying how cheap double-and-add would be; walking the toy subgroup eventually lands on Q and reports the step count. The reflection and the third intersection are drawn on the canvas but never written to the text readout, and the ECDLP panel keeps one fixed secret until New secret is pressed, so a whole class walking the subgroup on a fresh load reports the same answer. Re-derived against the live page 2026-09-22.
• ECDSA Forge: in the toy attack both signatures show the same r, the recovered d matches the real key, and a new signature minted with it verifies; equal message hashes or a degenerate nonce produce an explanation instead of a result. Run Full Compromise reveals the victim key; RFC 6979 repeats r when the same message is signed again, and the attack against RFC 6979 reports that it is blocked. The curve menu in the first exhibit also governs the 256-bit compromise and the RFC 6979 panel, and switching it leaves earlier sample rows in place, so reset the samples before reading a list. Re-derived against the live page 2026-09-22.
• Nonce Lattice (extension): the page starts a run as soon as it loads, using the configuration last saved in that browser or the default MSB setting; bit-leak presets end with a byte-for-byte key match, the Defender (RFC 6979) preset fails and explains why, and settings below the information floor fail with a diagnostic. The feasibility badge is computed from the leak size and signature count alone, so it can read FEASIBLE on a run that recovers nothing and INFEASIBLE on the nonce-reuse run that recovers the key every time; the worksheet turns that into a question rather than hiding it. Re-derived against the live page 2026-09-22.

Common misconceptions

• A textbook RSA round trip that decrypts correctly is not a scheme fit for real use: the labs show textbook RSA is deterministic and malleable, and real systems add OAEP for encryption and PSS for signatures. Re-derived against the live page 2026-09-22.
• Educational RSA hashes with a 64-bit FNV-1a toy hash, not SHA-256, and labels those signatures forgeable; its VALID verdict demonstrates the verify equation, not a production-grade signature. Re-derived against the live page 2026-09-22.
• A larger modulus does not stop Håstad or Bleichenbacher: they exploit a small exponent without padding and a PKCS#1 v1.5 padding oracle, and RSA Forge states that the mathematics are identical at real key sizes and only scale differs.
• Toy-size breaks do not mean the underlying problems are easy: small moduli and small subgroups fall because they are small, and the labs set them beside 2048-bit RSA and secp256k1 to show the gap. Re-derived against the live page 2026-09-22.
• The smooth curve is the picture, not the cryptosystem: real elliptic-curve cryptography runs the same group law over a finite field, where the curve becomes a scatter of points.
• RFC 6979 nonces do repeat r when the same message is signed twice; the protection is that different messages get different nonces, and ECDSA Forge notes this rests on HMAC-SHA-256 behaving as a pseudorandom function, so a collision is negligibly unlikely rather than impossible.
• Extension: the lattice attack does not break a correct signer; Nonce Lattice's signer deliberately hands the attacker known nonce bits.

Conceptual answers

• OAEP mixes a fresh random seed into the message before exponentiation, so equal plaintexts stop producing equal ciphertexts, and a product of ciphertexts decrypts to padding that fails the integrity check instead of to a related message. That removes the equality leak, the multiplicative forgery, and the common m that Håstad's CRT step relies on.
• Each break shown is a search whose size is set by the parameters: trial division up to the square root of n, or walking a subgroup whose size is the group order. The mechanism is the same at real sizes; what changes is the cost, which the labs show growing beyond any feasible computation (a GNFS projection for RSA, and roughly the square root of the group order for generic discrete-log attacks). Re-derived against the live page 2026-09-22.
• RSA is multiplicatively homomorphic, so the attacker can turn the hidden plaintext m into m·s for a chosen s without the key. Each 'conformant' answer proves m·s landed in the valid-padding window, narrowing the interval that contains m until one value remains. Any observable difference between padding failures and other decryption failures recreates the oracle.
• Nonce reuse needs two signatures made with the same nonce, visible as a repeated r, and yields d with two lines of algebra; the lattice attack needs a few known or biased nonce bits across many signatures and stacks them into a Hidden Number Problem. RFC 6979 derives k from the key and the message, which takes the random number generator out of the trust path; leaks of nonce bits through timing or other side channels remain an implementation concern.
• A good answer weighs RSA's larger keys and padding pitfalls, ECDSA's dependence on nonce discipline and its signature malleability unless low-S is enforced, and Ed25519's deterministic-by-design nonces, against interoperability requirements such as TLS certificates, JWT algorithms or existing wallet ecosystems.

Checks

Browser support. Every exhibit in this module, and every step of its worksheet, was run in Chromium, Firefox and WebKit at a desktop width and at a phone width (1280 by 720 and 390 by 720), checked 2026-09-22. One exhibit needs a word of warning:

• ECDSA Forge — the page does not reflow at phone width: it stays about 288px wider than the screen in every engine checked, so it scrolls sideways Last re-derived against the live page 2026-09-22.

Privacy. Opening these exhibits sends nothing to anyone but the site they are served from: no exhibit sets a cookie, and none stores anything beyond the setting that pins its dark theme. The exception:

• Nonce Lattice — loads its web font from Google Fonts, so opening it sends a request to that service.

Detailed check results — engine versions, every step run, transfer sizes, and the source line behind each run-specific verdict. The worksheet drift check reads this module’s anchors manifest.

For your syllabus

How to cite this module’s exhibits

Each exhibit's citation is in the Sequence table above, in that exhibit's own row. Exhibits change as they are improved, so the retrieval date is what says which version you used; it is filled in from your device's clock when the page loads.

@misc{clark_rsa_educational,
  author       = {Clark, Paul A.},
  title        = {Educational RSA},
  howpublished = {\url{https://systemslibrarian.github.io/crypto-lab-rsa-educational/}},
  note         = {Crypto Lab. Accessed [date accessed]}
}

@misc{clark_rsa_forge,
  author       = {Clark, Paul A.},
  title        = {RSA Forge},
  year         = {2026},
  howpublished = {\url{https://systemslibrarian.github.io/crypto-lab-rsa-forge/}},
  note         = {Crypto Lab. Accessed [date accessed]}
}

@misc{clark_ec_point_arithmetic,
  author       = {Clark, Paul A.},
  title        = {Point Arithmetic},
  year         = {2026},
  howpublished = {\url{https://systemslibrarian.github.io/crypto-lab-ec-point-arithmetic/}},
  note         = {Crypto Lab. Accessed [date accessed]}
}

@misc{clark_ecdsa_forge,
  author       = {Clark, Paul A.},
  title        = {ECDSA Forge},
  year         = {2026},
  howpublished = {\url{https://systemslibrarian.github.io/crypto-lab-ecdsa-forge/}},
  note         = {Crypto Lab. Accessed [date accessed]}
}

@misc{clark_nonce_lattice,
  author       = {Clark, Paul A.},
  title        = {Nonce Lattice},
  year         = {2026},
  howpublished = {\url{https://systemslibrarian.github.io/crypto-lab-nonce-lattice/}},
  note         = {Crypto Lab. Accessed [date accessed]}
}

To cite the whole collection, see How to cite.