The previous post used hashing to store passwords, a job that never needs decrypting. When data does need to be read back, we encrypt it. Symmetric encryption (one shared key to lock and unlock, like AES) is fast and strong, but there's one question it can't answer: where do the two sides get the shared key? Your browser has never met viet.sarl's server, yet after a few dozen milliseconds the two share a secret key that nobody listening on the wire knows. This post explains that magic: public-key cryptography.
Roadmap: the key-pair idea, RSA by hand with small numbers, why "textbook" RSA can't be used, Diffie-Hellman, elliptic curves, digital signatures, measured speeds, equivalent key sizes, then quantum computers and ML-KEM. Measured with Python 3.12 and the cryptography 50 library on a real machine.
The idea: a key pair
Instead of one shared key, each side has a pair of keys:
- The public key: given to the whole world, printed in certificates, pasted on GitHub.
- The private key: never leaves its owner's machine.
The two keys are linked by a problem that is easy one way and hard the other. Multiplying two large primes is easy, but factoring their product is extremely hard. From such a pair come three jobs:
| Job | Who uses which key | Example |
|---|---|---|
| Encryption | Anyone encrypts with the public key; only the private-key holder decrypts | Writing to someone you've never met |
| Signature | The private-key holder signs; anyone checks with the public key | TLS certificates, software updates, git commits |
| Key agreement | Each side combines its own private key with the other's public key and gets the same secret | Every TLS and SSH connection |
In practice the first job is rarely applied to data directly. Public-key cryptography is thousands of times slower than symmetric encryption, so it's only used to agree on a symmetric key, and that key encrypts the actual data.
RSA with small numbers
RSA (1977) relies on factoring. Do it once by hand with numbers small enough to see everything:
- Pick two primes: p = 61, q = 53.
- n = p × q = 3233. This part is public.
- φ(n) = (p − 1)(q − 1) = 3120. Only someone who knows p and q can compute it.
- Pick a public exponent e = 17 (coprime with 3120).
- Find d such that e × d leaves remainder 1 when divided by 3120: d = 2753. This is the private key.
The public key is (n = 3233, e = 17), the private key is d = 2753. For the message m = 65:
c = pow(65, 17, 3233) # encrypt: 2790
pow(2790, 2753, 3233) # decrypt: 65
s = pow(65, 2753, 3233) # sign with the private key: 588
pow(588, 17, 3233) # anyone can check: 65
Encrypting and signing are just exponentiation followed by a remainder, in opposite directions. To find d from (n, e) you need φ(n), i.e. you must factor 3233 into 61 × 53. With a 4-digit number that's instant. With a 2048-bit n (617 decimal digits), nobody has managed it. The public record today is 829 bits, which took about 2,700 CPU core-years.
"Textbook" RSA can't be used
The formula above is mathematically correct but not secure used as is:
- Deterministic: the same message always gives the same ciphertext. An eavesdropper guesses "yes" or "no", encrypts both with the public key and compares.
- Mathematical structure: ciphertexts of related messages are related too, so an attacker can transform a ciphertext in a controlled way. A small experiment shows that multiplying the ciphertext by a known value doubles the decrypted plaintext.
So real RSA always comes with structured random padding. Encryption uses OAEP, signing uses PSS. The old PKCS#1 v1.5 padding for encryption caused a string of vulnerabilities over decades, so don't pick it for a new system. Padding also limits length: with RSA-2048 and OAEP-SHA256, one operation can encrypt at most 190 bytes (try 191 and the library refuses). One more reason RSA only wraps a symmetric key, not data.
Diffie-Hellman: agreeing on a secret over a public channel
In 1976, Whitfield Diffie and Martin Hellman published a way for two people who have never met to share a secret even though everything they send is overheard. With small numbers, pick the prime P = 23 and base G = 5 (public):
| An | Binh | |
|---|---|---|
| Pick a secret | a = 6 | b = 15 |
| Send publicly | A = 5⁶ mod 23 = 8 | B = 5¹⁵ mod 23 = 19 |
| Compute the shared secret | B^a = 19⁶ mod 23 = 2 | A^b = 8¹⁵ mod 23 = 2 |
Both get 2, because (G^b)^a = (G^a)^b = G^(ab). The eavesdropper sees 23, 5, 8 and 19, but to get 2 they'd need a from 8 = 5^a mod 23. That's the discrete logarithm problem, easy for 23 but unsolvable for a 2048-bit prime.
Diffie-Hellman alone only stops eavesdropping, not a man in the middle. Someone in the middle can run Diffie-Hellman separately with An and with Binh, then relay everything. To stop that, at least one side must sign what it sends with a key the other trusts. That's exactly what certificates do in TLS (post 5), and host keys in SSH (post 8).
Elliptic curves
Instead of raising integers to powers modulo a number, elliptic-curve cryptography (ECC) "adds points" on a curve of the form y² = x³ + ax + b, over a finite field. Adding a point to itself k times is easy. Given the resulting point, finding k again is hard, just like a discrete logarithm.
The big advantage: the curve problem is much harder for the same key length, because nobody has found shortcuts as good as those for integers. Shorter keys, faster computation:
| Security (bits) | Symmetric | RSA / DH | Elliptic curve |
|---|---|---|---|
| 112 | 3DES | 2048 | 224 |
| 128 | AES-128 | 3072 | 256 (P-256, X25519, Ed25519) |
| 192 | AES-192 | 7680 | 384 |
| 256 | AES-256 | 15360 | 512 |
The table follows NIST's recommendations. To double its security, RSA's key gets 5 times longer, while ECC's only doubles. Widely used curves:
- P-256 (secp256r1): the NIST standard; viet.sarl's TLS certificate uses it.
- Daniel Bernstein's Curve25519: designed to be hard to misuse, running in constant time for every input. X25519 uses it for key agreement, Ed25519 for signatures.
- secp256k1: used by Bitcoin and Ethereum. A "wallet" is really just a private key on this curve.
Digital signatures
Signing isn't "encrypting with the private key". A signature algorithm takes the hash of the data (post 2) and the private key, and produces a signature. Anyone with the public key can check it. A signature proves two things: the data wasn't changed, and the signer holds the private key.
Three signature algorithms come up often: RSA-PSS, ECDSA and Ed25519. ECDSA has a famous weakness: each signature needs a fresh random number, and if that number repeats or is predictable, the private key leaks. Sony's PlayStation 3 lost its signing key in 2010 because it used a fixed number for every signature. Ed25519 avoids this entirely by deriving that number deterministically from the key and the message. That's why it's the recommendation for new systems.
Measured: RSA against elliptic curves
Each operation runs hundreds to thousands of times on one core, signing a 100-byte message:
| Algorithm | Key generation | Sign | Verify | Signature size |
|---|---|---|---|---|
| RSA-2048 | 14 ms (median, 12–67 ms) | 0.299 ms | 0.010 ms | 256 B |
| RSA-3072 | 127 ms (53–171 ms) | 0.876 ms | 0.019 ms | 384 B |
| ECDSA P-256 | 0.006 ms | 0.011 ms | 0.033 ms | 70 B |
| Ed25519 | 0.013 ms | 0.013 ms | 0.032 ms | 64 B |
| X25519 (key agreement) | 0.015 ms per exchange | 32 B public key |
Three takeaways:
- RSA key generation is slow and erratic, because it has to search randomly for large primes: RSA-4096 took between 120 and 750 ms across five runs. Generating an elliptic-curve key is just picking a random number, thousands of times faster. That matters because TLS and SSH make a fresh temporary key pair for every connection.
- Ed25519 signs about 23 times faster than RSA-2048, with a signature 4 times shorter.
- RSA verification is the fastest (e = 65537 is a small exponent). So RSA still suits "sign once, verify millions of times", like a root CA's signature on certificates.
Quantum computers and ML-KEM
In 1994, Peter Shor showed that a large enough quantum computer could factor and solve discrete logarithms in polynomial time. That means RSA, Diffie-Hellman and every elliptic curve would be broken. Symmetric encryption and hash functions only lose half their bits, so AES-256 stays safe.
Nobody has a large enough quantum computer yet. But one threat has already started: "harvest now, decrypt later". Someone recording TLS traffic today might decrypt it 10–15 years from now. Data that must stay secret for a long time, such as medical records or state secrets, is already at risk.
In 2024, NIST standardised the first post-quantum algorithm for key exchange: ML-KEM (formerly Kyber). It's based on a lattice problem nobody knows how to solve quickly, even with a quantum computer. Trying ML-KEM-768 with cryptography:
k = mlkem.MLKEM768PrivateKey.generate()
shared, ciphertext = k.public_key().encapsulate() # the sender
k.decapsulate(ciphertext) == shared # True: the receiver gets the same secret
| X25519 | ML-KEM-768 | |
|---|---|---|
| Public key | 32 B | 1,184 B |
| Sent back | 32 B | 1,088 B |
| Generate / encapsulate / decapsulate | ~0.015 ms | 0.035 / 0.009 / 0.013 ms |
ML-KEM is as fast as elliptic curves. The cost is size: over 1 KB each way instead of 32 bytes.
Because ML-KEM is still new, browsers and servers use a hybrid: run both X25519 and ML-KEM, then mix the two secrets. Breaking the connection means breaking both. Checking viet.sarl with openssl s_client:
Negotiated TLS1.3 group: X25519MLKEM768
Connections to this site are already protected against quantum computers. Cloudflare turns it on by default; the site owner doesn't have to do anything. Post 8 shows that OpenSSH has moved to a similar hybrid.
Post-quantum signatures (ML-DSA, SLH-DSA) have been standardised too, but the move is slower. Their signatures and keys are much larger, and a TLS certificate chain carries several signatures. Besides, a signature only has to be secure at the moment it's checked, so it isn't exposed to "harvest now, decrypt later".
Summary
- Public-key cryptography solves key exchange: the public key goes to the world, the private key stays put. It's used for encryption, signatures and key agreement.
- RSA relies on factoring. By hand: n = 3233, e = 17, d = 2753. Real RSA needs padding: OAEP to encrypt, PSS to sign.
- Diffie-Hellman gives two sides a shared secret over a public channel, but needs a signature alongside to stop a man in the middle.
- Elliptic curves: 256 bits are as strong as RSA-3072. Ed25519 signs about 23 times faster than RSA-2048, with 64 B signatures. RSA verification is still the fastest.
- Quantum computers will break RSA and ECC. ML-KEM is standardised, and viet.sarl already uses X25519MLKEM768 (hybrid).
The next post assembles everything so far into a real protocol: TLS 1.3. The handshake step by step, certificates and the chain of trust, Let's Encrypt, and the two TLS legs behind viet.sarl's padlock.