Public-Key Cryptography

Every construction in Chapter 1 begins with a key both parties already hold. In a network of $n$ parties, pairwise symmetric keys number $\binom{n}{2} = O(n^2)$: roughly half a million for a thousand users, five hundred billion for a million. Each key must be generated, transported over a channel that is already confidential, stored and destroyed when a party leaves. The arithmetic is the smaller problem. The bootstrapping is the obstacle, since a symmetric key can only be established over a channel that is already secure. Two consequences follow. The secrets each party holds grow with the network, so one compromised machine exposes every conversation it joined, and two parties who have never met (a shop and a first-time customer) have no shared history to derive a key from.

Diffie and Hellman proposed a solution in 1976: split the key in two. Every party gets a public key that may be published in a directory and a matching private key that never leaves them. Anyone can encrypt to Bob using material Bob himself made public; only Bob can decrypt. The number of keys collapses to $O(n)$, and public keys require integrity alone, so the confidential distribution channel disappears.

Common mistake. A received public key can be trusted at face value. The key distribution problem shrinks, but authenticity remains: without a binding of key to owner, a man in the middle substitutes his own key and reads everything.

The price is that public-key encryption can never be unconditionally secure. An adversary holding $\mathit{pk}$ can, in unbounded time, encrypt every candidate message and compare, or search for a private key consistent with the public one, so perfect secrecy in Shannon's sense is unattainable and every scheme rests on a computational assumption. The scheme also does not replace symmetric encryption, because exponentiation modulo a 3072-bit number is thousands of times more expensive per byte than The Advanced Encryption Standard (AES). The practical norm is hybrid encryption, or key encapsulation: the public-key scheme runs once, to transport or agree a short session key. The traffic is then encrypted under that key with an authenticated symmetric scheme. TLS (Transport Layer Security) is built this way, and Chapter 3 treats it in detail.

Worked number. A $2048$-bit modulus holds $256$ bytes; Optimal Asymmetric Encryption Padding with SHA-256 leaves $256 - 66 = 190$. So one Rivest-Shamir-Adleman operation carries a $16$-byte Advanced Encryption Standard key, and AES encrypts the gigabytes.

The trapdoors of this chapter are built from arithmetic modulo an integer. Division is the operation that fails. The structure of that failure determines the rest of the chapter.

For $n > 0$ and any integer $a$ there are unique $q$ and $r$ with $a = qn + r$ and $0 \le r < n$; write $a \bmod n = r$. Two integers are congruent, $a \equiv b \pmod n$, when $n$ divides $a - b$, equivalently when they leave the same remainder. Congruence is an equivalence relation compatible with addition and multiplication, so the $n$ residue classes form a commutative ring $\Z_n = (\{0, 1, \dots, n-1\}, +, \cdot)$.

An element $a$ has a multiplicative inverse exactly when $\gcd(a, n) = 1$, by Bézout's identity: some $u, v$ satisfy $au + nv = \gcd(a,n)$, and when that gcd is $1$ the identity reduces modulo $n$ to $au \equiv 1$. If $\gcd(a,n) = d > 1$ then every multiple of $a$ is a multiple of $d$ modulo $n$, so $1$ is unreachable.

When $n$ is prime every nonzero residue is coprime to it, so $\Z_p$ is a field and $\Z_p^{*} = \{1, \dots, p-1\}$ has order $p-1$. Moreover $\Z_p^{*}$ is cyclic: some $g$ generates it, its successive powers running through every element exactly once. There are $\varphi(p-1)$ such generators. No efficient formula produces one; they are found by testing candidates.

Inverses are computed by the Euclidean algorithm, which rests on $\gcd(a,b) = \gcd(b, a \bmod b)$ for $a \ge b > 0$ and terminates in $O(\log \min(a,b))$ divisions; tracking the quotients while running it yields the Bézout coefficients, and hence the inverse.

Public-key schemes exponentiate numbers hundreds of digits long. Naive repetition would take exponentially many multiplications and would leave no way to invert exponentiation deliberately. Both problems are solved by the fact that exponents live in a group of known order, and can be reduced.

The practical content is that exponents may be reduced modulo $\varphi(n)$: if $x \equiv y \pmod{\varphi(n)}$ then $a^x \equiv a^y$ for every unit $a$, so a seventy-digit exponent collapses to something smaller than $n$. Equally important, the map $x \mapsto x^{e}$ on $\Z_n^{*}$ can be inverted by anyone who knows $\varphi(n)$: choose $d$ with $ed \equiv 1 \pmod{\varphi(n)}$ and then $(x^{e})^{d} = x^{1 + k\varphi(n)} = x$. That is RSA. The trapdoor is knowledge of $\varphi(n)$; the modulus $n$ alone gives no inverse.

A small example fixes the ideas. $\Z_{10}^{*} = \{1,3,7,9\}$ has order $\varphi(10) = 4$. The element $3$ generates it: $3^{0} \equiv 1$, $3^{1} \equiv 3$, $3^{2} \equiv 9$, $3^{3} \equiv 7$ and $3^{4} \equiv 1$ closes the cycle. The element $7$ also has order $4$; the element $9$ has order $2$. Euler's theorem is visible as the fact that every one of these orders divides $4$.

Exponentiation itself is done by square and multiply: read the exponent in binary, square the running value at every bit position and multiply in the base wherever the bit is $1$. Computing $a^{x} \bmod n$ costs about $\log_2 x$ squarings and at most $\log_2 x$ multiplications on numbers the size of $n$. That is what makes the forward direction cheap; no analogous trick is known for going backwards.

Common mistake. Factoring has been proved hard, which is why RSA is safe. No such proof exists. The belief rests on decades of failed attempts, and breaking RSA is not even proved equivalent to factoring the modulus.

RSA key generation needs large primes on demand, and nothing about the definition of a prime suggests they can be recognized quickly: trial division takes $\Theta(\sqrt{n})$ steps, exponential in the bit length. Density is settled by the prime number theorem: the number of primes up to $n$ is asymptotically $n / \ln n$, so a random $1024$-bit odd integer is prime with probability roughly $2 / \ln(2^{1024}) \approx 1/355$ and a few hundred candidates suffice. Every integer factors into primes (Euclid) and does so uniquely up to order (Gauss), which is what makes factoring a well-posed target in the first place.

Recognition is settled too. Agrawal, Kayal and Saxena gave a deterministic polynomial-time primality test in 2002. In practice nobody uses it: the randomized tests are far faster. A failure probability of $2^{-128}$ is not a real risk.

The second verdict is where the trouble is. A composite $n$ with $a^{n-1} \equiv 1 \pmod n$ is a Fermat pseudoprime to the base $a$, and $a$ is a Fermat liar; the smallest base-$2$ example is $341 = 11 \cdot 31$. There are infinitely many pseudoprimes for every base, and infinitely many Carmichael numbers, composites for which every base coprime to $n$ is a liar. The smallest is $561 = 3 \cdot 11 \cdot 17$, on which the Fermat test is wrong for all $320$ admissible bases, and repetition cannot help.

Two problems carry almost all of classical public-key cryptography. Neither is proved hard. Their conjectured hardness is what every scheme in this chapter is priced against.

Integer factoring. Given $N = p \cdot q$ for primes of comparable size, find $p$ and $q$. Trial division up to $\sqrt{N}$ costs about $\sqrt{N}/\ln \sqrt{N}$ divisions, exponential in $\log N$. The better algorithms are all sub-exponential: Pollard's rho and $p-1$ methods, the quadratic sieve and the general number field sieve, whose heuristic running time is $\exp\big(O((\log N)^{1/3}(\log\log N)^{2/3})\big)$. The RSA factoring challenges calibrate this: RSA-768, a $232$-digit modulus, was factored in 2009 after roughly two years of computation spread over a large network of machines. Current moduli are $2048$ or $3072$ bits; $768$-bit moduli are obsolete.

Worked number. In February 2020 Boudot, Gaudry, Guillevic, Heninger, Thomé and Zimmermann factored RSA-250, an $829$-bit modulus, at a cost of about $2700$ core-years. $1024$-bit RSA sits near end of life; $2048$-bit stays out of classical reach.

Discrete logarithm. Let $p$ be prime and $g$ a generator of $\Z_p^{*}$, so every $y \in \Z_p^{*}$ equals $g^{x}$ for some $x \in \{0, \dots, p-2\}$. Given $(p, g, y)$, find $x$. Forward evaluation costs $O(\log x)$ multiplications by square and multiply; the best known inversion is again sub-exponential, by index calculus. Generic algorithms that treat the group as a black box (Shanks's baby-step giant-step, Pollard's rho) cost $\Theta(\sqrt{q})$ in a group of order $q$, the bound elliptic curves live at.

The animation below plots the orbit of a generator. The forward map is fast and structurally simple, while the inverse has no exploitable structure: the values do not increase, do not cluster and do not approach the target as the exponent approaches the answer, so a hill-climbing search has no information to guide it.

Common mistake. A $2048$-bit RSA key gives $2048$ bits of security. The general number field sieve factors far faster than brute force: the National Institute of Standards and Technology rates $2048$-bit RSA at about $112$ bits, like a $112$-bit symmetric key.

The security definition comes before the constructions. RSA and ElGamal are later measured against it. A definition that only forbids recovering the whole message is too weak to be useful, since a scheme that leaks all but the last bit would satisfy it. The history of public-key encryption is largely a history of schemes that met a weak definition and fell to an attack outside it.

The one forbidden query is the subtle part. If $\Adv$ can transform $c$ into some related $c' \neq c$ whose decryption reveals something about $m$, the restriction is vacuous and the scheme falls, so CCA security is in effect a non-malleability requirement. It is also the notion that matches practice, because real receivers decrypt attacker-chosen ciphertexts all day and their behavior (even just an error message) is an oracle.

What went wrong. In 1998 Bleichenbacher read Secure Sockets Layer sessions through one signal: whether decrypted padding was valid. About a million chosen ciphertexts sufficed. Padding checks must stay silent and uniform; Optimal Asymmetric Encryption Padding removes the oracle entirely.

RSA in its bare form instantiates the $e$-th power map of section 3. It is correct, it is efficient and it fails every security definition of section 6, which makes it the most instructive broken scheme in the subject.

A worked example with small numbers. Take $p = 61$ and $q = 53$, so $N = 3233$ and $\varphi(N) = 60 \cdot 52 = 3120$, and choose $e = 17$, coprime to $3120$. The extended Euclidean algorithm gives $e^{-1} \bmod 3120 = 2753$, and reducing it modulo $\mathrm{lcm}(60, 52) = 780$ yields the smaller equivalent exponent $d = 413$, valid because $780$ is a multiple of both $60$ and $52$, so Fermat's little theorem modulo each prime gives $m^{780} \equiv 1$ for every $m$ coprime to $N$. Encrypting $m = 65$ gives $c = 65^{17} \bmod 3233 = 2790$. Decrypting gives $2790^{413} \bmod 3233 = 65$.

Messages must first be encoded as integers in $\Z_N$. The encoding is a real design task. Exponentiation uses square and multiply. Decryption is usually done modulo $p$ and $q$ separately, recombining by CRT. A small public exponent ($e = 3$ or $e = 65537$) makes encryption and verification fast and public keys compact, at the cost of two constraints: $e$ must stay coprime to $\varphi(N)$, which slightly complicates prime generation, and short messages become dangerous.

Common mistake. RSA encrypts your message directly. One padded Rivest-Shamir-Adleman operation fits under $190$ bytes, so real systems encrypt a random Advanced Encryption Standard key with Optimal Asymmetric Encryption Padding and let AES carry the actual data.

The attacks of section 7 all target the scheme. The underlying hardness remains intact. Separating the two is what lets the scheme be repaired.

Factoring breaks RSA: from $p$ and $q$ one computes $\varphi(N) = (p-1)(q-1)$ and hence $d$, so the RSA assumption is at least as strong as the factoring assumption. The converse is not known, since computing $e$-th roots might conceivably be easier than factoring. No approach to RSA has ever beaten factoring the modulus, so in practice the two are priced identically. Knowledge of $d$, incidentally, does yield the factorization, even though the reduction runs only one way.

The repair is randomized padding. Encrypting $r \| m$ for fresh random $r$ destroys determinism immediately: the same message now has exponentially many ciphertexts, and decryption simply discards $r$. It also disrupts the multiplicative structure, because a ciphertext that Eve multiplies decrypts to something whose padding is malformed with overwhelming probability. The receiver rejects it.

RSA needs an encoding scheme to introduce randomness. ElGamal is randomized by construction: every encryption carries a fresh exponent from the discrete-logarithm group.

ElGamal is CPA secure. The assumption it needs is the statement that the mask $h^{r}$ looks random.

CDH is what a key exchange needs to be unpredictable, while DDH is what it needs for the shared value to be usable directly as a key. Chapter 3 returns to the protocol; here the assumption is the point.

What went wrong. Logjam (2015) broke $512$-bit export Diffie-Hellman in about a minute per connection after one nation-scale precomputation, and common $1024$-bit groups look within reach of the same method. Use $2048$-bit or elliptic-curve groups.

Nothing in section 9 mentioned $\Z_p^{*}$ except by way of example. ElGamal, and the Diffie-Hellman assumptions with it, need only a cyclic group of known prime order in which exponentiation is cheap. Choosing a different group changes the security per bit dramatically, because index calculus, the sub-exponential attack on discrete logarithms, depends on the arithmetic of the integers and does not transfer.

The group law is geometric before it is algebraic. To add $P$ and $Q$, draw the line through them, take its third intersection with the curve and reflect that point in the $X$-axis; $-P$ is the reflection of $P$, and adding $P$ to itself uses the tangent at $P$ in place of the chord. The group is written additively, so exponentiation becomes scalar multiplication, computed by double-and-add: read the scalar $x$ in binary, doubling the running point at each bit and adding $P$ where the bit is $1$, for about $\log_2 x$ doublings. The discrete-logarithm problem reads: given $P$ and $Q = xP$, find $x$.

On a well-chosen curve the best known attacks are the generic ones. Pollard's rho needs $\Theta(\sqrt{q})$ steps in a group of order $q$, so the field size must be twice the security parameter: a $256$-bit curve delivers roughly $128$ bits of security, matching a $3072$-bit RSA public key. Whether Decisional Diffie-Hellman (DDH) holds depends on the chosen group. That ratio is why elliptic curves dominate deployed key exchange and signatures.

Worked number. Security estimates match across schemes: $1024$-bit RSA or Diffie-Hellman gives about $80$ bits, $2048$-bit about $112$ and $3072$-bit about $128$. A $256$-bit elliptic-curve key already reaches $128$ bits.

Some curves carry additional structure: a pairing, a map into a second group that turns the multiplication of exponents into an operation one can actually perform.

Bilinearity is immediately destructive and immediately constructive. Destructive: DDH is easy in $\mathbb{G}$, since a candidate $Z$ satisfies $Z = g^{ab}$ if and only if $e(g^{a}, g^{b}) = e(g, Z)$, a check anyone can perform. Any protocol whose proof invokes DDH in $\mathbb{G}$ is void on a pairing-friendly curve.

Constructive: bilinearity lets two exponents that were never in the same place be multiplied. That is what section 13 uses to build identity-based encryption. It is also behind short signatures, three-party one-round key agreement and much of the succinct-proof literature.

Encryption protects a message from being read; nothing so far stops an attacker from writing one. The two properties are separate. A signature does not encrypt anything, and public-key encryption does not identify the sender, so deployments that need both must combine them. In the symmetric setting a Message Authentication Code (MAC) authenticates. It requires a shared key and its verdict is meaningful only to the two key holders, since either party could have produced any tag. A signature is the public-key analogue, with a property no MAC has: anyone can verify, and only one party could have signed.

RSA suggests an immediate construction: run the trapdoor backwards. With $\mathit{pk} = (N, e)$ and $\mathit{sk} = (d, p, q)$, sign as $\sigma = m^{d} \bmod N$ and verify by checking $\sigma^{e} \equiv m$. Correctness is Euler's theorem again. Security is absent.

The hash blocks both forgeries. Each block uses a different hash property. The existential forgery now requires, from a chosen $\sigma$, a preimage $m$ with $\Hash(m) = \sigma^{e}$, blocked by one-wayness. Transferring a legitimate signature $\sigma$ from $m$ to another message requires an $m' \neq m$ with $\Hash(m') = \Hash(m)$, blocked by second-preimage resistance. Inducing a signer to sign a benign $m$ whose signature also verifies on a malicious $m'$ requires finding such a pair in advance, blocked by collision resistance, which is why the birthday bound sets the required digest length. The multiplicative attack fails because $\Hash(m_1 m_2) \neq \Hash(m_1)\Hash(m_2)$. RSA-FDH is provably unforgeable under the RSA assumption in the random oracle model. The deployed variant is RSA-PSS (Probabilistic Signature Scheme), which pads the hash with fresh randomness before signing.

Everything so far assumes the reader of a public key knows whose it is. Drop that assumption and every construction above is exposed to a man-in-the-middle attack, which runs as follows:

Public keys have no need of confidentiality, but authenticity is essential, and supplying it is a separate problem from any of the mathematics above.

Common mistake. Diffie-Hellman key exchange authenticates the two parties. Classic Diffie-Hellman is anonymous key agreement: each side must add signatures or certificates, since otherwise an attacker runs one exchange with Alice, another with Bob and reads both sides.

The standard answer is to sign the binding. A certification authority holds a signing key pair, verifies out of band that a public key belongs to a named party and issues

$$\mathrm{Cert}_{\mathrm{CA} \to A} \gets \mathbf{S}\big(\mathit{sk}_{\mathrm{CA}},\; \mathit{pk}_{A} \,\|\, \text{“Alice”}\big).$$

Anyone holding $\mathit{pk}_{\mathrm{CA}}$ can verify the binding, and Alice's certificate can travel with her key over any channel at all. The trust problem has been reduced from $n$ authentic keys to one. The format of these objects is standardized by the ITU (International Telecommunication Union) as X.509, carrying

• the subject and issuer names;
• the subject's public key and its algorithm;
• a validity interval and a serial number;
• extensions, and the CA's signature over all of the above.

Relying on one CA creates a single point of failure because its compromise makes every binding it issued suspect. Practice therefore uses chains. A root CA certifies intermediate CAs, which certify end entities. A verifier walks the chain from a locally trusted root down to the certificate in hand, checking each signature in turn. Trust propagates along the chain, so a user may belong to several distinct infrastructures at once, linked by cross-certification. What the binding asserts varies, and is often a domain name and nothing more, with the user name retained only for management and auditing.

Certificates must also expire and be revoked, and revocation is the part of PKI that works least well in practice. Every certificate carries a validity interval, so a verifier must check the current time. Choosing the lifetime is a tradeoff, since short lifetimes mean constant reissuance, while long ones widen the window after a key is stolen. Revocation before expiry needs the serial number, which is distinct per certificate; the CA publishes a certificate revocation list naming those withdrawn, and verifiers must fetch it, which means the CA has to stay reachable. CRLs have largely given way to The Online Certificate Status Protocol (OCSP) and to short-lived certificates for this reason.

The alternative to hierarchy is a web of trust, as used by PGP (Pretty Good Privacy). Users sign each other's keys directly. A verifier accepts a key if it is reachable by a sufficiently short chain of signatures from someone already trusted. No trusted party is required; the costs are that trust decisions fall on individual users, that revocation is even harder and that the graph must be connected for a stranger's key to be verifiable at all.

A Public-Key Infrastructure (PKI) exists because a public key is a meaningless string that has to be bound to a name. Shamir asked in 1984 whether the name could simply be the key, so that anyone could encrypt to bob@example.com with no certificate, no lookup and no prior interaction with Bob. He proposed the notion and could not build it; the first realization came from Boneh and Franklin in 2001, using pairings.

That last clause is what makes the definition demanding. The keys of all other identities must be useless against the challenge one, so they cannot be derived from each other in any recoverable way.

The tradeoffs against a PKI fall on both sides. In favor:

• no certificates and no directory lookup;
• Alice can encrypt to a party who has not yet enrolled.

Against:

• The KGC knows every private key, so key escrow is inherent to the design. Escrow is an advantage in a corporation that must read its own mail, and a disqualification almost everywhere else. The KGC is correspondingly the highest-value target in the system, mitigable by splitting the master key across several authorities with threshold techniques.
• Keys cannot be revoked, because the identity cannot be changed. The standard workaround is to encrypt to an identity concatenated with a time period, so keys expire by construction and must be reissued.
• Extraction needs a secure authenticated channel from KGC to user, the same kind of secure channel whose absence motivated public-key cryptography in the first place.