Multiply 61 by 53 in your head and you'll have 3233 within a minute. Now hand a friend the number 3233 and ask which two primes produced it. They'll get there, but only by trudging through candidate after candidate. That lopsidedness, trivial one way, laborious the other, does not go away as numbers grow. It gets catastrophically worse, and RSA turns the catastrophe into a lock.

RSA is the most famous member of the asymmetric family described in how encryption actually works: systems where a public key locks and a different, private key unlocks. Published in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT (a mathematician at Britain's GCHQ, Clifford Cocks, had found essentially the same scheme in 1973, but it stayed classified for decades), RSA was the first practical public-key system and ran much of the internet's trust for forty years.

The trapdoor idea

Cryptographers call RSA's core a trapdoor one-way function: an operation easy to compute forward, infeasible to reverse, unless you hold one extra piece of information, the trapdoor, which makes reversing easy again.

For RSA, the forward direction is multiplying two large primes, each hundreds of digits long. Any laptop does it in microseconds. The reverse direction is factoring: given only the product, recover the primes. For numbers of the size RSA uses, the best known classical algorithms would need longer than the age of the universe. The trapdoor is simply knowing the primes, because whoever knows them can compute everything the private key requires.

So the key generation story is almost anticlimactic. Pick two big random primes, call them p and q. Multiply them into n. Publish n (plus a small helper number) as your public key. Keep p and q secret; they are your private key's foundation. You have announced a puzzle to the world and kept the answer in your pocket.

What's missing is how a message gets locked with n and unlocked with p and q. That runs on modular arithmetic, which sounds worse than it is: it's clock arithmetic, where numbers wrap around. On an ordinary clock, 9 + 4 = 1, because 13 wraps past 12. RSA does its multiplications on a "clock" with n positions.

A worked example you can check by hand

Real RSA uses primes hundreds of digits long, but the machinery is identical with tiny ones, so let's build a toy key pair with p = 3 and q = 11.

Step 1: the modulus. n = 3 × 11 = 33. Our arithmetic will wrap around at 33. This n is public.

Step 2: the secret count. Compute (p − 1)(q − 1) = 2 × 10 = 20. This number (Euler's totient, if you want the jargon) counts how the multiplication structure inside the clock behaves, and here is the crucial point: computing it requires knowing p and q. From n = 33 alone you'd have to factor first. This is exactly where the trapdoor lives.

Step 3: the public exponent. Pick a number e that shares no factors with 20. Take e = 3. The public key is the pair (n = 33, e = 3).

Step 4: the private exponent. Find d such that e × d leaves remainder 1 when divided by 20. Since 3 × 7 = 21 = 20 + 1, we get d = 7. The private key is d = 7, and only someone who knew the 20, which means someone who knew p and q, could compute it.

Encrypting. Represent the message as a number m smaller than 33; say m = 4. Ciphertext = m^e mod n, meaning raise to the power e, then take the remainder after dividing by n. So 4³ = 64, and 64 mod 33 = 31. The ciphertext is 31.

Decrypting. Compute 31⁷ mod 33. There's a mental shortcut: on a 33-clock, 31 is the same as −2. And (−2)⁷ = −128. Add 33s until positive: −128 + 132 = 4. The original message reappears. That's the whole trick: exponentiation by e scrambles, exponentiation by d exactly unscrambles, and a theorem of Euler from the 1700s guarantees the round trip always lands on the original.

An eavesdropper sees n = 33, e = 3, and the ciphertext 31. To find d, they need the 20, and for that they must factor 33. With 33 that takes a second; with a 617-digit n it takes geological time. The toy and the real thing differ only in the size of that wall.

One more elegant feature: run the machine in reverse gear, exponentiating with your private d first, and anyone can verify the result with your public e. That produces digital signatures, proof that only the private key holder could have generated a message. In practice you sign a document's hash rather than the document itself, which is one reason the fingerprint machinery in hash functions explained matters so much.

Why 2048 bits

If factoring is so hard, why do RSA keys need to be monsters, at least 2048 bits (about 617 decimal digits) by current NIST guidance? Because factoring, while hard, is nowhere near as hard as blind guessing. Mathematicians have spent centuries sharpening factoring algorithms, and the best of them, the general number field sieve, exploits deep structure in numbers to run astronomically faster than trial division.

The public record makes the scaling visible. RSA-250, a 829-bit modulus, was factored in 2020 using roughly 2700 core-years of computation. That sounds like a lot until you notice it's rentable by a determined organization. But the difficulty compounds so violently with size that the steps between key sizes are chasms: 1024-bit keys are now considered insecure and deprecated outright, while 2048 bits still sits beyond any classical effort anyone can credibly assemble — though current guidance already treats it as a legacy size, recommending 3072 bits or more where secrets must hold for decades. The margin between the record and the deployed size is the whole security argument, and it's why key size recommendations creep upward over decades. It's also why, as explained in symmetric vs asymmetric encryption, a 2048-bit RSA key is roughly comparable to only a 112-bit symmetric key: the attacker gets to use factoring, not guessing.

The quantum cloud on the horizon

In 1994, Peter Shor showed that a sufficiently large quantum computer could factor numbers efficiently, collapsing the wall RSA is built on. Not "faster brute force," but a genuinely different kind of computation that dissolves the problem. The same algorithm breaks elliptic-curve cryptography.

The machines that exist are nowhere close: Shor's algorithm at cryptographic scale needs millions of error-corrected qubits, and current devices offer noisy hundreds-to-thousands. But cryptography plans in decades, and encrypted traffic recorded today can be stored and decrypted by a future machine, the "harvest now, decrypt later" problem. So the migration began early: NIST finalized its first post-quantum standards in 2024, built on lattice problems that resist Shor's algorithm, and browsers and messaging apps have been rolling out hybrid key exchanges, which is already reshaping the handshake described in what TLS actually does.

The takeaway

RSA is one idea executed beautifully: hide two primes inside a product, let the world lock messages with the product, and keep the primes as your trapdoor. The arithmetic is humble enough to run with 3 and 11 on the back of an envelope, and the security is nothing more mysterious than the verified, decades-long gap between multiplying and factoring. It's a satisfying piece of machinery to carry around in your head, the kind of thing NerdSip's daily five-minute reads are made of, and it's also a technology in graceful retirement: still guarding much of the internet, while its quantum-proof successors move in next door.