Chapter 3: Public-Key Cryptography¶
Public-key (asymmetric) cryptography uses mathematically linked key pairs: a public key for encryption or signature verification, and a private key for decryption or signing. It solves the key distribution problem that makes symmetric cryptography awkward at scale.
Before public-key cryptography, every pair of communicating parties needed to securely exchange a shared secret out-of-band — by courier, phone, or in person. For \(n\) parties, that’s \(O(n^2)\) pairwise secrets to manage. Public-key cryptography collapses this: each party publishes one public key, and anyone can now initiate a secure channel with them without any prior coordination. The tradeoff is speed — asymmetric operations are roughly 1000x slower than AES, which is why real protocols use public-key crypto only to bootstrap a symmetric session key, then switch to symmetric encryption for bulk data.
3.1 RSA¶
3.1.1 Key Generation and Core Operations¶
Definition 3.1 (RSA Key Generation)
-
Choose large random primes \(p, q\) (each \(\sim k/2\) bits); set \(n = pq\).
-
Compute \(\lambda(n) = \mathrm{lcm}(p-1, q-1)\) (Carmichael’s totient).
-
Choose \(e\) with \(1 < e < \lambda(n)\) and \(\gcd(e, \lambda(n)) = 1\); typically \(e = 65537\).
-
Compute \(d \equiv e^{-1} \pmod{\lambda(n)}\) via extended Euclidean algorithm.
-
Public key: \((n, e)\). Private key: \((n, d)\) (with \(p, q\) for CRT optimization).
Encryption: \(c = m^e \bmod n\) Decryption: \(m = c^d \bmod n\)
The choice \(e = 65537 = 2^{16} + 1\) is near-universal in practice. It has only two set bits in binary, which minimizes the number of multiplications in the square-and-multiply exponentiation. More importantly, \(e = 3\) (the smallest valid choice) creates dangerous edge cases: for messages \(m < n^{1/3}\), the ciphertext \(c = m^3 \bmod n = m^3\) doesn’t even reduce modulo \(n\), leaking \(m\) by simply taking the cube root of \(c\) over the integers. \(e = 65537\) avoids all such small-exponent pathologies.
Theorem 3.1 (RSA Correctness)
If \(\gcd(m, n) = 1\) (true with overwhelming probability for random \(m\)):
since \(ed \equiv 1 \pmod{\lambda(n)}\), so \(m^{ed} = m^{1 + k\lambda(n)} = m \cdot (m^{\lambda(n)})^k \equiv m \cdot 1 \equiv m\).
Example 3.1 (RSA with Small Numbers)
Let \(p = 11\), \(q = 13\), so \(n = 143\), \(\lambda(n) = \mathrm{lcm}(10, 12) = 60\).
Choose \(e = 7\) (since \(\gcd(7, 60) = 1\)). Then \(d = 7^{-1} \bmod 60 = 43\) (check: \(7 \times 43 = 301 = 5 \times 60 + 1\)).
Encrypt \(m = 9\): \(c = 9^7 \bmod 143 = 9\).
Decrypt: \(c^d = 9^{43} \bmod 143 = 9\). ✓
3.1.2 RSA Padding Schemes¶
Textbook RSA is Insecure
Unpadded RSA has multiple vulnerabilities: small message exponent attacks, multiplicative homomorphism (given \(c_1 = m_1^e\) and \(c_2 = m_2^e\), compute \(c_1 c_2 = (m_1 m_2)^e\)), and chosen-ciphertext attacks. Always use proper padding.
The multiplicative homomorphism of textbook RSA is a particularly sharp pitfall in practice. A TLS server that decrypts under RSA and returns different error messages for different failure modes is a decryption oracle. The Bleichenbacher 1998 attack exploits PKCS#1 v1.5 padding errors in exactly this way: the server reveals whether the decrypted plaintext starts with the two bytes 0x00 0x02, which is enough of a one-bit oracle to reconstruct the full plaintext after about \(10^6\) queries. The ROBOT attack in 2017 showed this vulnerability was still present in major TLS implementations, including some from F5 and Citrix, nearly two decades after it was first documented.
RSAES-OAEP (RFC 8017): For encryption.
where masks are derived from a mask generation function (MGF1-SHA-256). OAEP is IND-CCA2 secure in the random oracle model.
RSASSA-PSS: For signatures. Probabilistic; provably secure; recommended over PKCS#1 v1.5.
PKCS#1 v1.5: Legacy; vulnerable to Bleichenbacher’s 1998 padding oracle attack (ROBOT attack, 2017 — still present in \(27\%\) of top-million domains). Avoid for new systems.
OAEP works by randomizing the message before the RSA operation using a hash-based mask. The randomization means identical messages produce different ciphertexts on each encryption (no determinism), which breaks the multiplicative structure that textbook RSA leaks. The MGF1 function serves as a random oracle in the security proof, which is why OAEP’s security only holds in the random oracle model — a limitation worth knowing but not usually a practical concern with SHA-256 as the underlying hash.
3.1.3 RSA Key Size Recommendations¶
| Modulus | Classical Security | Quantum Security | Status |
|---|---|---|---|
| 1024 bits | \(< 80\) bits | Broken | Deprecated |
| 2048 bits | 112 bits | Broken | Minimum; avoid for new deployments |
| 3072 bits | 128 bits | Broken | Acceptable to 2030 |
| 4096 bits | 140 bits | Broken | Recommended now |
RSA offers no quantum resistance. Shor’s algorithm factors \(n\) in polynomial time on a quantum computer, recovering \(p\) and \(q\) and thus the private key \(d\). No key size makes RSA quantum-safe — this is fundamental, not fixable by using larger keys. Organizations planning for long-term data confidentiality (data encrypted today that must remain secret past 2030) should begin transitioning to post-quantum algorithms (ML-KEM, ML-DSA) now. “Harvest now, decrypt later” attacks are a real threat: adversaries can store today’s RSA-encrypted traffic and decrypt it retroactively once quantum computers mature.
3.2 Diffie-Hellman Key Exchange¶
Definition 3.2 (Finite-Field DH (FFDH))
Let \(p\) be a prime, \(g\) a generator of \(\mathbb{Z}_p^*\). Alice and Bob exchange:
-
Alice: \(a \leftarrow_\$ [2, p-2]\); send \(A = g^a \bmod p\).
-
Bob: \(b \leftarrow_\$ [2, p-2]\); send \(B = g^b \bmod p\).
-
Shared secret: \(S = A^b \bmod p = B^a \bmod p = g^{ab} \bmod p\).
DH solves a subtle but profound problem: two parties who have never met can establish a shared secret over a public channel, even with a passive eavesdropper recording every message. The insight is that the eavesdropper sees \(g^a\) and \(g^b\), but computing \(g^{ab}\) from those two values is the CDH problem — believed hard in properly chosen groups. Neither party ever transmits their secret exponent \(a\) or \(b\); they only transmit the one-way images.
DH Group Requirements
The DH group must be large enough to resist index calculus. NIST recommends:
-
RFC 3526 groups: Group 14 (2048-bit) minimum; Group 15/16 (3072/4096-bit) preferred.
-
RFC 7919 FFDHE groups: pre-standardized for TLS 1.3.
-
Avoid: groups \(< 2048\) bits, Oakley Group 1/2, non-standard custom groups.
The group choice matters beyond just the prime size. Using a custom non-standard group is dangerous because the group might have weak structure: a small order, a smooth order (whose factorization has many small prime factors), or a subgroup of known discrete logarithm. RFC 7919’s named groups were specifically chosen with large safe-prime orders to resist these attacks. Any implementation that allows configuring an arbitrary DH group should be treated as a security defect.
Logjam Attack (2015)
Researchers showed that 512-bit DH (export-grade) could be broken in hours using number field sieve precomputation. Many TLS servers were downgraded to 512-bit DH via FREAK-like negotiation. State-level adversaries could precompute logs for common 768/1024-bit groups used by millions of servers.
Defense: Disable DHE \(<\) 2048-bit; prefer ECDHE; use RFC 7919 named groups.
3.3 Elliptic Curve Schemes¶
3.3.1 ECDSA (Elliptic Curve Digital Signature Algorithm)¶
Definition 3.3 (ECDSA)
Parameters: curve \(E\), generator \(G\) of prime order \(n\), hash function \(H\).
Key generation: \(d \leftarrow_\$ [1, n-1]\); \(Q = dG\) (public key).
Signing message \(m\):
-
\(k \leftarrow_\$ [1, n-1]\) (ephemeral, random, unique per signature)
-
\(R = kG\); \(r = R_x \bmod n\) (x-coordinate of \(R\))
-
\(s = k^{-1}(H(m) + r \cdot d) \bmod n\)
-
Signature: \((r, s)\)
Verification of \((r, s)\) on message \(m\):
-
\(w = s^{-1} \bmod n\)
-
\(u_1 = H(m) \cdot w \bmod n\); \(u_2 = r \cdot w \bmod n\)
-
\((x, y) = u_1 G + u_2 Q\)
-
Valid if \(x \equiv r \pmod{n}\)
The verification step works because expanding \(u_1 G + u_2 Q = H(m) w G + r w (dG) = w(H(m) + rd) G = (w \cdot ks) G = k G = R\). The signer picks a random \(k\), computes a “commitment” \(R = kG\), then reveals \(r = R_x\) (a one-way image of the commitment) and a response \(s\) that ties \(r\) to the message and private key. A verifier who knows the public key \(Q = dG\) can reconstruct \(R\) without knowing \(k\) or \(d\), because the math collapses correctly.
ECDSA Nonce Reuse — Catastrophic
If the ephemeral key \(k\) is reused for two signatures \((r, s_1)\) and \((r, s_2)\) on messages \(m_1, m_2\):
From this, \(k\) can be recovered, and then the private key:
Real-world impact: Sony PlayStation 3 (2010) — static \(k = 1\) used for all firmware signatures, secret key extracted; Bitcoin wallets with weak RNG compromised; HTTPS servers with broken PRNG exposed private keys.
The PlayStation 3 break is a textbook example of catastrophic nonce failure. Sony used \(k = 1\) in their ECDSA implementation, which meant every firmware signature had the same value of \(r = G_x \bmod n\). Two signatures with the same \(r\) immediately reveals \(k = 1\) from the signature equation, and then \(d\) follows by simple arithmetic. The entire firmware signing key was recovered from just two signatures, and custom firmware could be signed as if it were official Sony software. This failure cost Sony control over their console security and was entirely avoidable.
3.3.2 EdDSA (Edwards-Curve Digital Signature Algorithm)¶
EdDSA (RFC 8032) addresses ECDSA’s nonce-sensitivity by deriving \(k\) deterministically:
where \(b_{\text{prefix}}\) is part of the private key. Because \(k\) depends on both key and message, reuse is structurally impossible.
The deterministic nonce derivation is the key design win: signing the same message twice always produces the same signature, because \(k\) is determined by the combination of private key and message. There’s no external randomness to fail. EdDSA also doesn’t require an inverse modulo \(n\) during signing — the signature computation is a scalar multiplication and a few additions, which is simpler to implement correctly. The simpler implementation path means fewer opportunities for side-channel leakage through timing differences.
Ed25519 (Curve25519 + SHA-512):
-
\(\sim 128\)-bit security; 64-byte signatures; 32-byte public key
-
Constant-time operations: resistant to timing side-channels
-
\(\sim 70{,}000\) verifications/second on modern hardware
-
Used in: SSH (host keys), TLS 1.3, Tor, Signal, Age encryption
from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey
# Key generation
private_key = Ed25519PrivateKey.generate()
public_key = private_key.public_key()
# Sign
message = b"This message is authenticated"
signature = private_key.sign(message) # 64 bytes
# Verify (raises InvalidSignature on failure)
public_key.verify(signature, message)
# Serialize public key (32 bytes)
pub_bytes = public_key.public_bytes_raw()
3.3.3 X25519 (ECDH with Curve25519)¶
X25519 (RFC 7748) is the Diffie-Hellman function on Curve25519, using the Montgomery ladder for constant-time scalar multiplication:
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
# Alice
alice_private = X25519PrivateKey.generate()
alice_public = alice_private.public_key()
# Bob
bob_private = X25519PrivateKey.generate()
bob_public = bob_private.public_key()
# Shared secret computation
alice_shared = alice_private.exchange(bob_public) # 32 bytes
bob_shared = bob_private.exchange(alice_public) # 32 bytes
assert alice_shared == bob_shared
# Derive actual key via HKDF (raw shared secret is NOT a key --- must be hashed)
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
derived_key = HKDF(
algorithm=hashes.SHA256(),
length=32,
salt=None,
info=b"handshake"
).derive(alice_shared)
The comment in the code about hashing the raw shared secret before use is not optional. The raw X25519 output is a group element, not uniformly random — it lives in a specific subgroup and has algebraic structure. Passing it through HKDF removes that structure and produces a uniformly distributed key. Skipping this step can leak information about the shared secret or produce keys with predictable bias.
3.4 ElGamal Encryption¶
Definition 3.4 (ElGamal)
Group \(G\) of prime order \(q\), generator \(g\). Secret key \(x\); public key \(h = g^x\).
Encrypt \(m \in G\): choose \(r \leftarrow_\$ [1, q-1]\); ciphertext \(= (g^r, m \cdot h^r)\).
Decrypt \((c_1, c_2)\): \(m = c_2 \cdot (c_1^x)^{-1} = c_2 \cdot h^{-r}\).
ElGamal encryption is semantically secure under the DDH assumption: an adversary who can’t distinguish \(g^{ab}\) from a random group element also can’t distinguish encryptions of different messages. The ciphertext \((g^r, m \cdot h^r)\) hides \(m\) because the masking value \(h^r = g^{xr}\) is computationally indistinguishable from random, which means \(m \cdot h^r\) reveals nothing about \(m\) to an observer who doesn’t know \(x\) or \(r\).
ElGamal on elliptic curves underlies ECIES (Elliptic Curve Integrated Encryption Scheme), the EC analog used in many protocols.
3.5 RSA vs ECC Comparison¶
ECC provides equivalent security with much smaller keys, resulting in faster operations and smaller certificates. The table below maps security levels across algorithm families.
| Security | RSA/DH | ECC | AES | SHA |
|---|---|---|---|---|
| 80 bits | 1024 bits | 160 bits | 80 bits | 160 bits |
| 112 bits | 2048 bits | 224 bits | 112 bits | 224 bits |
| 128 bits | 3072 bits | 256 bits | 128 bits | 256 bits |
| 192 bits | 7680 bits | 384 bits | 192 bits | 384 bits |
| 256 bits | 15360 bits | 512 bits | 256 bits | 512 bits |
The key size difference isn’t just about storage — it directly affects performance. Generating an RSA-3072 key pair is noticeably slower than generating an ECDSA P-256 key pair, and RSA signature verification at equivalent security levels is considerably slower than Ed25519 verification. On constrained devices (smart cards, IoT sensors, embedded controllers), this matters enormously: an Ed25519 verify might take milliseconds while RSA-3072 verify takes seconds. The size difference also affects TLS handshake latency: smaller certificates mean fewer packets, which matters on high-latency mobile connections.
3.6 Hybrid Encryption¶
Public-key encryption is orders of magnitude slower than symmetric encryption and can’t encrypt arbitrary-length messages efficiently. Hybrid encryption solves both:
-
Generate random symmetric key \(K\) (e.g., 256-bit AES key).
-
Encrypt \(K\) with recipient’s public key: \(C_K = \mathrm{RSAES\text{-}OAEP}(pk, K)\).
-
Encrypt message with \(K\): \(C_M = \mathrm{AES\text{-}256\text{-}GCM}(K, M)\).
-
Send \((C_K, C_M)\).
This is the basis of TLS, PGP, CMS (S/MIME), and virtually all asymmetric encryption in practice. Modern KEM+DEM (Key Encapsulation Mechanism + Data Encapsulation Mechanism) formalizes this construction.
The KEM/DEM split is more than organizational convenience. A KEM produces a key and an encapsulation; a DEM encrypts data under that key. Separating these two functions allows you to swap out the KEM independently of the DEM — exactly the kind of modularity needed for post-quantum migration. NIST’s ML-KEM (FIPS 203) is a post-quantum KEM designed to be a drop-in replacement for ECDH/RSA key encapsulation: swap the KEM, keep the AES-GCM DEM, and the system gains quantum resistance without redesigning the bulk encryption layer.
Exercises¶
Exercise 3.1
Generate an RSA-2048 key pair in Python (using the cryptography library). Encrypt a 32-byte random message with OAEP-SHA256. Decrypt and verify. Time the operations.
Exercise 3.2
Explain the Bleichenbacher attack on PKCS#1 v1.5 RSA encryption. Why does the oracle (invalid padding \(\to\) error response) allow the attacker to decrypt any ciphertext?
Exercise 3.3 (ECDSA Nonce Recovery)
Suppose an ECDSA signer uses the same \(k\) for two messages with hashes \(h_1 = 10\) and \(h_2 = 20\), over a group of order \(n = 37\), yielding \(r = 13\), \(s_1 = 15\), \(s_2 = 25\). Recover \(k\) and the private key \(d\).
Exercise 3.4
Compare ECDSA and EdDSA: which is more resistant to implementation errors? Which provides stronger security guarantees? Why does EdDSA derive \(k\) deterministically?
Exercise 3.5
Implement a hybrid encryption scheme in Python: use X25519 for key agreement, HKDF-SHA256 for key derivation, and AES-256-GCM for symmetric encryption. Document each step.
Exercise 3.6
A certificate authority uses RSA-1024 as its signing key in a legacy system. A security team proposes migrating to (a) RSA-4096, (b) ECDSA P-256, (c) Ed25519. Compare these options on: security level, signature size, verification speed, and post-quantum considerations.