How does RSA work?

1. The one-way idea behind RSA

Multiplying two large prime numbers is easy. Taking the answer apart again — factoring it back into those primes — is astonishingly hard. That gap is the entire foundation of RSA.

Think of it like mixing paint. Combining two colours takes a second; separating the mixture back into the originals is effectively impossible. RSA builds a lock out of exactly that asymmetry: the public key everyone can use to lock a message, and the private key only you hold to unlock it.

RSA was published in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman — the R, S and A of the name. Nearly fifty years later it still protects a large share of internet traffic.

2. Generating the keys, step by step

RSA key generation is five steps. Each one is ordinary arithmetic — the security comes from the size of the numbers, not the complexity of the operations.

Encrypting and decrypting are then a single operation each:

3. A full worked example

Let's run the whole algorithm with numbers small enough to verify yourself.

• Pick primes: p = 61, q = 53
• Modulus: n = 61 × 53 = 3233
• Totient: φ(n) = 60 × 52 = 3120
• Public exponent: e = 17 (shares no factor with 3120)
• Private exponent: d = 2753, because 17 × 2753 = 46801 = 15 × 3120 + 1

Now encrypt the number m = 65 (which is ASCII for the letter "A"):

Anyone can compute that using only the public key. To reverse it you need d:

Those exponents look enormous, but modular exponentiation by squaring keeps every intermediate number small — which is why your phone can do this with 600-digit numbers in milliseconds.

4. Why can't attackers just reverse it?

An attacker sees n, e and the ciphertext c. To recover the message they need d, and to get d they need φ(n), and to get that they need p and q. So the whole system reduces to one question: can you factor n?

For a 2048-bit modulus, the best known classical algorithms would take longer than the age of the universe on all the computers on Earth. Nobody has proven factoring is hard — it's an assumption — but it has resisted the world's best mathematicians for five decades.

This is also why key size matters. 512-bit RSA was broken in the 1990s; 768-bit fell in 2009. Today 2048-bit is the minimum, and 3072- or 4096-bit is recommended for long-lived secrets.

5. Will quantum computers break RSA?

Yes — in principle. In 1994 Peter Shor found a quantum algorithm that factors integers efficiently, which would collapse RSA entirely. A sufficiently large, error-corrected quantum computer doesn't exist yet, but the threat is real enough that NIST has already standardised replacements.

That's the "harvest now, decrypt later" concern: an adversary could record encrypted traffic today and decrypt it once quantum hardware matures. Anything that must stay secret for decades should already be migrating.

The replacements are built on different mathematics — mostly lattice problems that neither classical nor quantum computers know how to solve efficiently.

6. Frequently asked questions

Is RSA still secure in 2026?

Yes, with adequate key sizes (2048-bit minimum, 3072-bit preferred). Its long-term future is limited by quantum computing, which is why post-quantum migration is underway.

What's the difference between RSA and AES?

RSA is asymmetric — different keys to lock and unlock — and is slow, so it's used to exchange keys and sign data. AES is symmetric — one shared key — and is fast, so it encrypts the actual data. Real systems use both together.

Why is e usually 65537?

It's prime and its binary form (10000000000000001) has only two 1-bits, so encryption needs very few squaring steps. It's also large enough to avoid the small-exponent attacks that plague e = 3.

Can RSA encrypt long messages?

Not directly — the message must be smaller than n. In practice RSA encrypts a short symmetric key, and that key encrypts the real data.

What is RSA signing?

The same math in reverse: you use your private key to produce a signature anyone can check with your public key. It proves the message came from you and wasn't altered.

Keep going