Every lesson so far has assumed both parties share a secret key. Public-key cryptography eliminates that assumption. Two parties who have never communicated before can establish a shared secret over a completely public channel.
Alice buys a padlock and sends it to Bob – unlocked, through the mail. Anyone can see the padlock in transit, but only Alice has the key. Bob puts his message in a box, snaps the padlock shut, and mails the box back. Now only Alice can open it. She never sent the key anywhere. The padlock is the public key. The key to the padlock is the private key.
This solves the key distribution problem that symmetric cryptography cannot solve on its own. Two parties can communicate securely without a pre-shared secret and without a trusted courier.
Symmetric cryptography requires one shared secret per pair of communicating parties. A network of 1,000 users needs nearly 500,000 shared keys. Adding one user requires securely distributing a new key to every existing user. Public-key cryptography reduces this to 1,000 key pairs – each user generates their own pair and publishes the public half. The private half never leaves their machine.
RSA, published in 1977, was the first widely deployed public-key cryptosystem. Its security rests on the difficulty of factoring large numbers.
The setup: choose two large primes p and q. Compute n = p * q. Computing n from p and q is trivial. Recovering p and q from n alone – factoring – is computationally infeasible for sufficiently large n. RSA key generation produces a public key (n, e) and a private key (n, d) such that encryption with e can only be reversed with d.
RSA-2048 (a 2048-bit modulus) is the current minimum for security. RSA-4096 provides a larger margin. Key generation, encryption, and especially decryption are computationally expensive compared to symmetric operations.
RSA encryption and decryption involve modular exponentiation with numbers that are thousands of bits long. An RSA-2048 encryption is roughly 1,000 times slower than an AES-256 block encryption. This performance gap is why RSA is never used to encrypt bulk data directly. Instead, RSA encrypts a small symmetric key (32 bytes for AES-256), and the symmetric key encrypts the actual data. This is hybrid encryption, and every major protocol uses it.
Raw textbook RSA is deterministic – the same plaintext always produces the same ciphertext. This leaks information. In practice, RSA always uses a padding scheme. OAEP (Optimal Asymmetric Encryption Padding) is the current standard for encryption. PKCS#1 v1.5 padding is legacy and vulnerable to Bleichenbacher’s attack, a padding oracle that can decrypt RSA ciphertexts by observing server error responses. Use OAEP for encryption. Use PSS for signatures.
Diffie-Hellman (1976) solves a different problem than RSA. It does not encrypt messages. It allows two parties to agree on a shared secret over a public channel, without any prior shared secret.
The protocol: Alice and Bob agree on public parameters (a large prime p and a generator g). Alice picks a secret a, computes g^a mod p, and sends it publicly. Bob picks a secret b, computes g^b mod p, and sends it publicly. Both compute the shared secret: g^(ab) mod p. An eavesdropper sees g^a and g^b but cannot compute g^(ab) – this is the discrete logarithm problem.
The shared secret is then used as a symmetric key (or used to derive one) for bulk encryption.
Given g, p, and g^a mod p, computing a is the discrete logarithm problem. For well-chosen parameters, this is computationally infeasible. The security of Diffie-Hellman, DSA, and elliptic curve cryptography all reduce to variants of this problem. If someone finds an efficient algorithm for discrete logarithms, all three systems break simultaneously.
Static Diffie-Hellman reuses the same secret exponents across sessions. If a private key is later compromised, all past sessions encrypted with it can be decrypted. Ephemeral Diffie-Hellman (DHE or ECDHE) generates fresh key pairs for every session. Even if a long-term private key is compromised, past session keys cannot be recovered because the ephemeral private values were discarded. This property is called forward secrecy. TLS 1.3 mandates ephemeral key exchange for every connection.
Elliptic curve cryptography (ECC) provides the same security guarantees as RSA and classical Diffie-Hellman but with dramatically smaller keys.
A 256-bit elliptic curve key provides security equivalent to a 3072-bit RSA key. The operations are faster, the keys are smaller, the certificates are smaller, and the handshakes are faster. This is why modern systems overwhelmingly prefer ECC.
Curve25519: designed by Daniel Bernstein, used for Diffie-Hellman key exchange (X25519). The standard curve for TLS 1.3, WireGuard, Signal, and SSH. Chosen for performance, simplicity, and resistance to implementation pitfalls.
P-256 (secp256r1): the NIST standard curve. Widely deployed in existing infrastructure. Used in most TLS certificates and AWS/GCP/Azure key management.
The elliptic curve discrete logarithm problem is harder than the classical discrete logarithm problem. The best known algorithms for breaking classical Diffie-Hellman (number field sieve) run in sub-exponential time. The best known algorithms for breaking elliptic curve Diffie-Hellman run in fully exponential time. This gap means ECC achieves equivalent security with much shorter keys – 256 bits instead of 3072 bits – resulting in faster computation, lower bandwidth, and smaller storage for certificates and key material.
The NIST P-256 curve parameters were generated using a seed whose origin was never fully explained. Some cryptographers suspect the parameters could have been chosen to introduce a backdoor – similar to the confirmed backdoor in Dual_EC_DRBG, a NIST random number generator influenced by the NSA. Curve25519 was designed with fully transparent parameter selection (the constants are derived from nothing-up-my-sleeve numbers), which is one reason it is preferred in modern protocols.
No production system uses asymmetric encryption alone for data. The performance cost is prohibitive and the message size is limited. Instead, every protocol uses hybrid encryption:
The asymmetric component runs once per session to solve the key distribution problem. The symmetric component handles all data encryption at hardware-accelerated speeds.
RSA can only encrypt data smaller than its modulus – roughly 245 bytes for RSA-2048 with OAEP padding. Even if there were no size limit, encrypting a 1 GB file with RSA would take minutes. AES-256-GCM encrypts the same file in milliseconds with hardware acceleration. Hybrid encryption provides the best of both: the key distribution properties of asymmetric crypto and the speed of symmetric crypto.
TLS handshake: the client and server perform ECDHE (typically X25519) to establish a shared secret. This secret is used to derive symmetric keys for AES-GCM or ChaCha20-Poly1305. The entire handshake completes in one round trip in TLS 1.3. Every HTTPS page load, every API call over TLS, begins with this exchange.
SSH keys: running ssh-keygen generates an asymmetric key pair. Ed25519 (based on Curve25519) is the recommended type. The public key goes in ~/.ssh/authorized_keys on the server. During connection, the client proves possession of the private key without transmitting it, and both sides perform ECDHE to establish session keys.
PGP/GPG: encrypting an email with PGP generates a random symmetric key, encrypts the email with that key, then encrypts the symmetric key with the recipient’s RSA or ECC public key. The recipient decrypts the symmetric key with their private key, then decrypts the email. This is hybrid encryption applied to asynchronous messaging.
Generating a key pair is easy. The hard problems are all operational. How can a public key be verified to actually belong to the claimed entity? TLS uses certificate authorities – a hierarchical trust model. PGP uses a web of trust – a decentralized model. SSH uses trust-on-first-use (TOFU) – the server’s key is accepted the first time and changes trigger an alert. Each model has different failure modes, and all of them have been exploited in the real world.
This lesson establishes:
Next: Digital Signatures