RSA & ECDH, hand-cranked
Asymmetric cryptography rests on two mathematical pillars: integer factorization (RSA) and the elliptic curve discrete logarithm (ECDH). They look nothing alike, but they solve the same problem — letting two strangers agree on a secret in front of an audience. Walk through both, one operation at a time, with primes and curves small enough to follow on paper.
what 'asymmetric' actually means
One key, shared in advance
Alice and Bob already share a secret key. Alice encrypts with it, Bob decrypts with it. Same key both directions. AES is a symmetric cipher.
Problem: how did they get the same key in the first place? You can't send it over the internet — anyone watching would see it. Symmetric crypto needs a pre-existing secure channel.
Two keys, public and private
Each person has a keypair. The public half can be shouted across a stadium. The private half stays at home. Anyone can encrypt to your public key; only you can decrypt with your private key.
This is what lets two strangers — who have never spoken before — agree on a secret in front of an eavesdropper. RSA does it. ECDH does it. Differently.
The deep idea behind both is the trapdoor function — a computation that's easy to do forward and impossibly hard to reverse, unless you happen to know a secret shortcut.
For RSA, the trapdoor is integer factorization. Multiplying two big primes is fast. Recovering the primes from the product is, as far as anyone knows, exponentially slow. The "secret shortcut" is just knowing the primes.
For ECDH, it's the elliptic curve discrete logarithm. Computing
k·G on a curve takes microseconds even when k
is a 256-bit number. Going backwards — given a point P,
find k such that k·G = P — takes the lifetime
of the universe. The "secret shortcut" is just knowing k.
Quantum computers break both by way of Shor's algorithm. That's the whole reason post-quantum cryptography exists. We'll get to that at the end.
RSA, primed
Rivest · Shamir · Adleman, 1977
RSA's whole world is integers and modular arithmetic. Pick two primes
p and q. Their product n = p·q
is the modulus that all arithmetic happens inside.
Knowing n alone doesn't reveal p and q —
and that asymmetry is the whole game.
// step 1 — generate a keypair
Why two primes, and why φ?
The crucial fact RSA leans on is Euler's theorem:
if gcd(m, n) = 1 then mφ(n) ≡ 1 (mod n).
And for n = pq with distinct primes, φ(n) = (p − 1)(q − 1).
Choose any e coprime to φ(n), then find its modular inverse
d — that means e·d ≡ 1 (mod φ(n)). Now
(me)d = me·d = m1 + k·φ(n) ≡ m.
Encryption raises m to e; decryption raises the result
to d; you get m back. The only person who can compute d
is someone who knows φ(n) — which means someone who knows p
and q. Anyone else is stuck factoring n.
In real RSA, p and q are 1024-bit primes,
n is 2048 bits, and e is almost always 65537 —
a small number with binary 10000000000000001, which makes
modular exponentiation cheap.
// step 2 — encrypt, decrypt, sign, verify
Square-and-multiply
Computing me by literally multiplying m by itself
e times would take forever for real-world e = 65537.
Instead, RSA uses square-and-multiply: walk through e's binary digits
left-to-right, square the running result on every bit,
and also multiply by m when the bit is 1.
e = 65537 = 216 + 1 takes only 17 squarings and 1 multiplication.
That's why 65537 is the public exponent everywhere.
The mod n happens after every step, keeping numbers from
blowing up — without it, m65537 would have
millions of digits.
Same algorithm, private exponent
Decryption is exactly the same modular exponentiation — just with
d as the exponent instead of e.
Notice: d is a much bigger number than e.
For real RSA, d is roughly the same size as n (≈2048 bits),
while e is just 17 bits. Decryption is therefore far slower than
encryption — about 100× in software.
Production implementations cheat: they use the Chinese Remainder Theorem
with the original p and q to compute the result
in two half-size operations, recovering most of that lost speed. That
optimization is also where Bleichenbacher's padding-oracle attacks have
historically lived.
(the full square-and-multiply trace is identical to decryption — same exponent d)
Signing is "decryption" of the message
RSA signatures are dual to RSA encryption. To sign, you raise the message (or rather its hash) to your private exponent d. To verify, anyone raises the signature to your public exponent e and checks that they get the message back.
This works because (md)e ≡ m just as much as
(me)d ≡ m — the operations commute.
Real RSA signatures hash the message first (so any-length messages can be
signed), then apply padding (PSS or PKCS#1 v1.5), then exponentiate.
Skipping the hash and signing m directly — like this demo
does — would let an attacker mix signatures together to forge new ones.
Verification needs only the public key
Anyone who knows (n, e) can verify a signature.
Compute se mod n and check it matches the message.
If it does, the signer must have known d — i.e., must have
been the private-key holder.
That's why public keys can be published in directories, embedded in certificates, printed on business cards. They give away nothing about the private key. Verifying a signature is a cheap operation — modular exponentiation with the small public exponent — which is why TLS handshakes are doable at scale.
ECDH, on a curve
Diffie-Hellman, 1976 · over an elliptic curveThe original Diffie-Hellman from 1976 worked over multiplicative groups modulo a prime. ECDH does exactly the same protocol — but on an elliptic curve, where the group operation is "point addition" instead of multiplication. The curve gives you the same one-way property in 256 bits that ordinary DH needs 3072 bits to match.
// the toy curve we'll use
Real ECDH curves like P-256 have ~2256 points on them. Our toy curve has 19. Otherwise the algebra is identical — and the whole point of working with 19 points is that you can list them.
The "discrete log problem" on this curve: given just a point kG,
find k. With 19 possible values, you'd brute-force it by hand in
a minute. With 2256 on P-256, even a planet-sized computer wouldn't
finish before the heat death of the universe.
Draw a line through P and Q. It hits the curve at one more point — call that −R. Reflect across the x-axis to get R = P + Q. Over a finite field the same algebra holds; the "line" just wraps around modulo p.
The group law on a curve
Elliptic-curve "addition" isn't ordinary arithmetic. It's a geometric operation
promoted to algebra. To add two points P and Q, you draw a straight line through them;
that line crosses the curve at exactly one more point; you reflect that
point across the x-axis, and the result is P + Q.
The line's slope is λ = (y_Q − y_P)/(x_Q − x_P). The third
intersection is (λ² − x_P − x_Q, λ(x_P − x_R) − y_P) — that's
−R. Negating the y-coordinate gives R.
Doubling (P + P) uses the tangent line at P instead, with
slope λ = (3x_P² + a) / (2y_P). Same idea: the tangent intersects the
curve at one more point, you reflect it, you get 2P.
Division in λ is modular division — multiplying by the
modular inverse. Don't think of these as fractions; think of them as
integers mod 17.
Repeated addition is the discrete log
"Multiplying" a point G by an integer k just means adding G to itself k times:
kG = G + G + … + G. There's no "k·x" multiplication going on — it's all
point additions strung together.
For real ECDH, k is a 256-bit number, so naïve k-fold addition would take longer than the universe. Instead, implementations use double-and-add (the additive equivalent of square-and-multiply) — k_bits doublings plus ~k_bits/2 additions. Microseconds, not eons.
Going forward — given G and k, compute kG — is fast. Going backward — given G and kG, recover k — is the elliptic curve discrete log problem, and no efficient classical algorithm is known.
● A = aG — Alice's public point
● B = bG — Bob's public point
● abG — the shared secret
Eve sees G, A, B. To recover the shared secret she must compute either a from A=aG or b from B=bG. With 19 options she'd brute force it; with 2256 options on P-256 she gives up.
Why both Alice and Bob arrive at the same point
Alice's calculation: she takes Bob's public point B (which equals bG)
and multiplies by her secret a. She gets a·B = a·(bG) = abG.
Bob's calculation: he takes Alice's public point A (which equals aG)
and multiplies by his secret b. He gets b·A = b·(aG) = baG = abG.
Same point. Same shared secret. Neither ever transmitted their private scalar; the public values A and B don't leak it (discrete log is hard). The shared secret is then fed into a key derivation function (HKDF) to produce a symmetric key for AES.
In real TLS 1.3, this exact protocol — over P-256 or X25519 — happens on every connection. The "ECDHE" in cipher-suite names is the ephemeral version: a, b are freshly randomized per session, so even if Alice's long-term private key leaks tomorrow, today's traffic stays secret. That property is called forward secrecy.
when to use which
| RSA | ECDH / ECDSA | |
|---|---|---|
| Key size for ~128-bit security | 3072 bits | 256 bits |
| What it does well | Encryption, signatures, key transport | Key exchange (ECDH), signatures (ECDSA, EdDSA) |
| What it doesn't do | Direct shared-secret derivation. RSA-KEM exists but is rare. | Encrypting arbitrary data directly. ECDH gives you a shared secret; you encrypt with a symmetric cipher. |
| Speed (typical) | Verify/encrypt: fast (small e). Sign/decrypt: slow. | Both directions fast; ~10–100× faster than equivalent RSA. |
| Side-channel risk | Modular exp leaks via timing, power, faults. Constant-time RSA is hard. | Curve choice matters hugely. P-256 needs constant-time scalar mult; X25519 was designed for it from day one. |
| Maturity | 1977. Oldest deployed asymmetric scheme. Battle-tested, attack-tested. | Standardized 1999 (P-256), 2014 (X25519). Now dominant in TLS 1.3. |
| What modern systems use | Older PKI, S/MIME, code signing, legacy TLS. | Modern TLS (ECDHE + AES-GCM), Signal, SSH, Tor, Bitcoin (secp256k1). |
| Post-quantum status | Broken by Shor's algorithm. | Broken by Shor's algorithm. |
The short version: use ECDH for new things. Smaller keys, faster operations, fewer foot-guns. RSA persists because it's already in certificates, hardware tokens, and deployed PKI — none of which is easy to replace.
Both are doomed in the long run by quantum computers. The transition plan that's already underway: pair ECDH with ML-KEM during this decade (hybrid key exchange), then migrate to ML-KEM-only once we trust the post-quantum side enough to drop the classical fallback.
why both will eventually break
In 1994, Peter Shor showed that a sufficiently large quantum computer can factor integers and compute discrete logarithms in polynomial time. Both problems reduce to the same quantum subroutine — period finding via the quantum Fourier transform.
So the hard problems behind RSA and ECDH share a single quantum vulnerability. A cryptographically relevant quantum computer (CRQC) — somewhere between thousands and millions of logical qubits, depending on whose estimate you trust — would break the entire asymmetric stack we've been building since 1976.
The replacements come from a different mathematical world entirely. ML-KEM (FIPS 203) is built on the difficulty of finding short vectors in lattices — a problem with no known quantum shortcut. ML-DSA (FIPS 204) is built from the same family for signatures. The U.S. government's CNSA 2.0 guidance requires both for protection of classified data by 2033.
Until then, the realistic path is "harvest-now, decrypt-later"-resistant: deploy hybrid schemes that combine X25519 with ML-KEM, so an adversary recording today's traffic can't decrypt it once they finally have a quantum computer. That's what TLS, SSH, and many messaging apps are starting to do as of 2025–2026.