How public-key encryption and signing certificates actually work — with live demos you can poke at, animated step-throughs, and the number theory underneath.
Classic (symmetric) encryption uses one key: the same key locks and unlocks. That works fine — AES is symmetric and superb — except for one brutal bootstrap problem: how do Alice and Bob agree on the key in the first place, when everything they send each other can be read in transit?
If Alice sends the key, Eve has the key. Meeting in person doesn't scale to "your browser talking to a server it's never seen." The 1976 breakthrough (Diffie–Hellman, then RSA in 1977) was realizing you can split the key into two halves:
Anyone can encrypt a message to Bob with his public key, but only Bob's private key can decrypt it. Eve can capture the ciphertext and the public key and still be stuck — if the math cooperates. So the entire scheme rests on finding a mathematical operation that's easy in one direction and practically impossible to reverse.
Everything happens "mod n": numbers wrap around like a clock. 17 mod 12 = 5, because 17 o'clock is 5 o'clock. This wrapping destroys information: if I tell you a number is 5 mod 12, you can't know if it was 5, 17, 29, or 41. Ordinary exponentiation is smooth and reversible (logarithms) — but exponentiation mod n jumps around erratically, and reversing it is a famously hard problem.
Pick a number and a modulus. Watch it wrap around the clock.
Enter any numbers. All results are computed mod n.
RSA is built on an asymmetry of effort:
A function easy to compute but hard to invert — unless you know a secret (the factors) — is a trapdoor function. The factors p and q are the trapdoor.
1. Euler's totient. φ(n) counts how many numbers below n share no factor with it. When n = pq for primes p, q:
This is the secret quantity: computing φ(n) without knowing the factors is as hard as factoring itself.
Pick any n and see which numbers 1…n are coprime to it (share no common factor). The count of highlighted cells is φ(n).
Two numbers are coprime (or "relatively prime") if the largest number that divides both of them is 1. That largest common divisor is the GCD (greatest common divisor).
For example: gcd(15, 28) = 1, so they're coprime. But gcd(15, 21) = 3 — they share the factor 3, so they're not coprime.
The Euclidean algorithm finds the GCD by repeated division: divide the larger by the smaller, take the remainder, and repeat until the remainder is 0. The last non-zero remainder is the GCD.
Arrange the numbers 0 to n−1 in a grid with q columns and p rows. A number shares a factor with n = pq only if it's a multiple of p or a multiple of q (or both). In the grid:
This grid uses the primes from the RSA tab (or defaults). Teal = coprime to n. Red = multiple of p. Amber = multiple of q.
2. Euler's theorem. For any m coprime to n:
Raising anything to the φ(n)-th power wraps it back to 1. This gives us a way to build exponents that cancel each other out.
3. Modular inverses. Pick a public exponent e coprime to φ(n). Then there is exactly one d with:
You find d with the extended Euclidean algorithm — cheap if you know φ(n), hopeless if you don't. And now the punchline:
The exponents e and d undo each other, but the link between them runs through φ(n) — which only the keyholder can compute. (n, e) is the public key; d is the private key.
If gcd(e, φ(n)) > 1, then e has no modular inverse mod φ(n) — there is no d such that ed ≡ 1 (mod φ(n)). Without d, decryption is impossible: the exponents can't cancel.
Worse, when gcd(e, φ(n)) = g > 1, the encryption function maps multiple distinct messages to the same ciphertext. There are only n/g possible ciphertext values, meaning information is irreversibly lost. Even an all-knowing being couldn't decrypt — the operation itself is ambiguous.
That's why step 4 of key generation filters e candidates to those coprime with φ(n). In practice, e = 65537 (a Fermat prime) is almost always coprime to φ(n) and is the standard choice.
Pick two primes and watch every step of key generation. Then type a message — each character is encrypted as c = me mod n, then decrypted with the private exponent.
Watch your message travel from Alice to Bob. Eve sees only ciphertext on the wire.
Two lines above just handed you answers — d = … and c = …. Here's the grade-school arithmetic behind each, recomputed live.
We need d with e·d ≡ 1 (mod φ(n)). Divide the larger by the smaller, keep the remainder, repeat — carrying a running coefficient of e. When the remainder hits 1, its coefficient is d.
You never build the huge number me. Instead, keep squaring m (reducing mod n each time), then multiply together only the squares whose bit is 1 in e's binary form.
RSA is thousands of times slower than AES, so nobody encrypts actual data with it. In TLS (the "s" in https), public-key math is used once at the start — to agree on a random symmetric key — and AES does the rest. Public-key crypto is the handshake; symmetric crypto is the workhorse.
Encryption uses the exponents one way; signing uses them the other way:
| Applied by | Operation | Guarantees | |
|---|---|---|---|
| Encrypt | anyone, with public key | c = me mod n | only keyholder can read it |
| Decrypt | keyholder, with private key | m = cd mod n | confidentiality |
| Sign | keyholder, with private key | s = H(m)d mod n | only keyholder could produce it |
| Verify | anyone, with public key | se mod n ≟ H(m) | authenticity + integrity |
Two details matter:
Bob signs a message with his private key from the RSA tab. Real SHA-256 is used. Try tampering after signing — the signature stays the same but verification breaks.
A cryptographic hash function takes input of any length and produces a fixed-size output (256 bits for SHA-256). Three properties make it useful for signatures:
Type two similar strings. Even a one-character difference produces a completely different SHA-256 hash. Each colored block is one byte of the 32-byte output.
Signatures solve integrity, but there's a hole: when your browser connects to yourbank.com and receives a public key, how does it know that key belongs to the bank and not to Eve in the middle?
A certificate binds a public key to an identity — and that binding is itself digitally signed by someone your browser already trusts, a Certificate Authority (CA):
Trust becomes a chain:
| Subject | ISRG Root X1 (Let's Encrypt's root) |
| Public key | RSA-4096 · a3:b1:99:… |
| Signed by | itself — trust is installed, not derived. Your OS ships with ~150 root certs. |
| Subject | Let's Encrypt R11 |
| Public key | RSA-2048 · 7c:e0:41:… |
| Signed by | ISRG Root X1 — verified with the root's public key |
| Subject | CN=yourbank.com |
| Public key | ECDSA P-256 · 04:8f:2a:… |
| Validity | 2026-05-01 → 2026-07-30 (90 days) |
| Signed by | Let's Encrypt R11 — verified with the intermediate's public key |
Root private keys are kept offline in hardware vaults. Day-to-day issuance is done by intermediates, which can be revoked and replaced without touching roots baked into billions of devices.
"Signing certificates" for software work identically — the certificate binds a key to a publisher instead of a domain. The publisher signs the hash of the installer; your OS verifies against the certificate and its trust store. Same math, same chain — that's macOS Gatekeeper, Windows Authenticode, and app store signing.
Before RSA, Diffie and Hellman solved the key-exchange problem directly. Alice and Bob agree on a public prime p and generator g. Each picks a secret number, computes a public value, and exchanges it. Both can then compute the same shared secret — but Eve, who sees only the public values, cannot.
Most new systems use ECC instead of RSA. The same trapdoor idea, built on a different hard problem. An elliptic curve (over a finite field) defines a group operation: you can "add" points on the curve. Given a point P and a scalar k, computing kP (adding P to itself k times) is fast. But given P and kP, finding k is infeasible — this is the elliptic-curve discrete logarithm problem (ECDLP).
The practical payoff: ECC gets the same security with far smaller keys. A 256-bit ECC key provides the same security as a 3072-bit RSA key. Smaller keys mean faster operations, smaller certificates, and less bandwidth — which is why TLS, SSH, and most modern protocols prefer ECDSA or Ed25519.
| System | Hard problem | Typical key size | Security level |
|---|---|---|---|
| RSA | factoring n = pq | 2048–4096 bits | ~112–140 bits |
| ECDSA / Ed25519 | elliptic-curve discrete log | 256 bits | ~128 bits |
| AES (symmetric) | brute force only | 128–256 bits | 128–256 bits |
| ML-KEM (post-quantum) | lattice problems | ~1–1.5 KB | ~128–256 bits |
"~128 bits of security" means the best known attack needs ~2128 operations — a number so large that energy, not time, is the limiting resource.
A large-scale quantum computer running Shor's algorithm would break both factoring and discrete logs in polynomial time — destroying RSA, DH, and ECC. This isn't theoretical hand-waving: it's why TLS is already migrating to ML-KEM (formerly CRYSTALS-Kyber), a lattice-based key encapsulation mechanism whose hard problem (Learning With Errors) resists quantum attack. The same trust-and-certificate architecture, with a new hard problem underneath.
The RSA demo in the previous tabs is "textbook RSA" — c = me mod n with no further processing. This is deterministic: the same message always produces the same ciphertext. An attacker who guesses the message can verify their guess by encrypting with the public key and comparing.
Real RSA uses OAEP (Optimal Asymmetric Encryption Padding): before encryption, the message is mixed with a random value through a series of hash-based operations. This means:
OAEP is mandatory for RSA encryption in all modern standards (PKCS#1 v2.x). The raw modular exponentiation is just the mathematical core; the padding is what makes it a real cryptosystem.
The best known classical algorithm for factoring large numbers is the General Number Field Sieve (GNFS). Its time complexity is sub-exponential but super-polynomial:
This means factoring gets harder much faster than the numbers get bigger. Doubling the key size doesn't just double the work — it increases it by a factor of billions. Here's the approximate scale:
| Key size | Approximate operations | Status |
|---|---|---|
| 512 bits | ~263 | Broken (factored in 1999) |
| 768 bits | ~276 | Broken (factored in 2009, 2 years) |
| 1024 bits | ~286 | Deprecated — feasible for nation-states |
| 2048 bits | ~2112 | Current standard — safe for decades |
| 4096 bits | ~2140 | Conservative choice |
Enter a number and watch trial division try to find its factors. With small numbers it's instant. With larger semiprimes (products of two primes), even trial division starts to struggle — and it's the simplest factoring algorithm.
In 1994, Peter Shor showed that a quantum computer can factor integers in polynomial time by reducing factoring to period-finding — a problem quantum computers solve exponentially faster than classical ones via the quantum Fourier transform.
Shor's algorithm breaks RSA, DH, and ECC. It doesn't break symmetric encryption (AES) or hash functions (SHA-256) — those just need larger keys/outputs to resist Grover's algorithm (which gives a quadratic speedup, not exponential).
Current quantum computers are far too small and noisy to run Shor's on real key sizes. But the threat is "harvest now, decrypt later" — adversaries may be storing encrypted traffic today to decrypt once quantum computers mature. That's why the migration to post-quantum algorithms (ML-KEM, ML-DSA) is happening now, before the threat is realized.