Lecture 6 · Thursday 09 October 2025

RSA, ElGamal, pairings, signatures, Public-Key Infrastructure (PKI) and Identity-Based Encryption (IBE)

The densest lecture of the course so far: two encryption schemes, four hardness assumptions, two group families, a signature scheme, an infrastructure and an alternative to that infrastructure, all resting on the arithmetic assembled two days earlier.

Deck: 02_Crypto_101_Asym.pdf Chapter 2

Before ThisWhere Lecture 5 Left Off

Lecture 5 closed the symmetric world and laid the groundwork for leaving it. The Minicrypt tour (the world where only symmetric cryptography is possible) showed that one-way functions suffice for everything symmetric. The implication chain stops there because nothing in Minicrypt yields public-key encryption. The number theory that followed supplied the missing structure: the ring $\mathbb{Z}_n$ (the integers modulo $n$) and the group $\mathbb{Z}_n^{*}$, invertibility exactly for residues coprime to the modulus, the extended Euclidean algorithm, Euler's theorem and Fermat's little theorem and the resulting reduction of exponents modulo $\varphi(n)$ (Euler's totient, the count of residues coprime to $n$). Primality testing gave a way to generate keys and exposed the Fermat test's Carmichael numbers (composite numbers that pass the test). The lecture ended on the two conjecturally hard problems (integer factoring and the discrete logarithm) and on the key distribution problem that motivates all of it.

This LectureWhat It Adds

The lecture turns hard problems into schemes, and then asks repeatedly whether the schemes are secure, usually finding that they are not, and using the failure to motivate the repair.

The lecture begins with the syntax of public-key encryption and its two security notions, Chosen-Plaintext Attack (CPA) and Chosen-Ciphertext Attack (CCA), written as games. Because the adversary holds the encryption key, no encryption oracle (a service that encrypts messages on request) is needed. A deterministic scheme is immediately broken for the same reason. Textbook RSA (the raw scheme without padding) then arrives as the canonical example, correct and efficient but insecure three separate ways: deterministic, so dictionary attacks work; multiplicative, so one decryption query breaks CCA security; and vulnerable on short messages when $e$ is small. The RSA assumption is separated from the scheme, factoring is shown to imply it, and padding is introduced as the repair, with PKCS #1 v1.5 (the Public-Key Cryptography Standards padding format) as the concrete format.

ElGamal follows as a scheme randomized by construction, and with it the Diffie-Hellman assumptions: Computational Diffie-Hellman (CDH), Decisional Diffie-Hellman (DDH) and the implication chain down to the discrete logarithm. The central subtlety is that DDH is false in $\mathbb{Z}_p^{*}$ (the nonzero residues modulo the prime $p$), which is why prime-order subgroups exist. Elliptic curves then appear as a better group for the same assumptions, and pairings as a group with extra structure that breaks DDH outright while enabling constructions no ordinary group supports. The last third turns to authenticity: digital signatures and unforgeability, RSA signing and its forgeries, Full-Domain Hash (hashing the message into the whole RSA domain) as the fix, then public-key infrastructures, X.509 (the standard certificate format) and the web of trust, and finally identity-based encryption with the Boneh-Franklin scheme, whose correctness is a single application of bilinearity.

Study PlanWhat to Read, in Lecture Order

  1. Chapter 2 §6: Public-key encryption and its security definitions. Learn the Chosen-Plaintext Attack (CPA) and Chosen-Ciphertext Attack (CCA) games as games. The argument that determinism is fatal is two lines and worth being able to reproduce.
  2. §7: Textbook RSA. The construction, the correctness proof from Euler's theorem and the three breaks. The animation walks the malleability attack (reshaping a ciphertext so it decrypts to a related plaintext) through exact small numbers; the lab lets the reader pick the primes and run the attack.
  3. §8: The RSA assumption and padding. Why factoring implies the RSA assumption, and what the PKCS #1 v1.5 (Public-Key Cryptography Standards) block is for, byte by byte. The converse implication is not known.
  4. §9: ElGamal and the Diffie-Hellman assumptions. The scheme, Computational Diffie-Hellman (CDH) and Decisional Diffie-Hellman (DDH) and the Legendre-symbol attack (an efficient test for squares modulo $p$) that makes DDH false in $\mathbb{Z}_p^{*}$ (the nonzero residues modulo $p$). The animation shows the commuting square; the lab computes the offending Legendre symbol for the reader's own parameters.
  5. §10: Elliptic curves and pairings. The chord-and-tangent group law, why $256$ bits of curve match $3072$ bits of RSA and the bilinearity animation. Note what a pairing costs as well as what it buys.
  6. §11: Digital signatures and unforgeability. The Existential Unforgeability under Chosen-Message Attack (EUF-CMA) game, the two forgeries against plain RSA signing and which hash property blocks which.
  7. §12: Public-key infrastructures. Certificates, X.509 (the standard certificate format), chains, revocation and the web of trust. The examinable content here is conceptual. No mathematics in this section is examinable.
  8. §13: Identity-based encryption. The four algorithms, the Indistinguishability under Chosen-Plaintext Attack for Identity-Based Schemes (IND-ID-CPA) game and Boneh-Franklin. Be able to write the decryption identity out; it is the pairing law applied once.

PracticeExercises for This Lecture