How RSA Encryption Works: The Math Behind Public-Key Cryptography

You want to buy something online. Your card number needs to travel across a network that anyone could be listening to, to a server you've never met and share no secret code with.

How do you lock a message so that only one specific person can open it, when you've never exchanged a key with them and every step of your conversation is public?

The answer is sitting behind the lock icon in your browser right now. It's called RSA, and it works because of one strange fact about numbers: multiplying two big primes together is fast. Taking that answer apart again is, for all practical purposes, impossible.

A padlock anyone can close, but only one person can open

Picture an open padlock sitting on a table in public. Anyone can pick it up and snap it shut around a box. That takes no skill and no secret.

But only one person, the one holding the actual metal key, can open it again.

That's the entire idea behind public-key cryptography. The open padlock is your public key. Anyone can grab it and lock a message for you. The metal key is your private key. Only you have it, and only it can undo what the padlock did.

RSA is one specific, very clever way to build a padlock and key pair out of pure arithmetic. And hey, notice what that requires: an action that's trivial to do in one direction, and something close to impossible to undo without the key. Multiplication turns out to be exactly that action.

Multiplying is easy. Undoing it is brutally hard

Take two prime numbers, say 61 and 53. Multiply them: 3233. That took one step.

Now suppose someone hands you just the number 3233 and asks: "which two primes multiply together to make this?" You'd have to start guessing divisors: 2, 3, 5, 7, 11... and check each one. Eventually you'd land on 53. For a four-digit number that's a minor annoyance.

But watch what happens as the number of digits grows.

Slide it up a few notches. The multiply step stays exactly as fast, always one step, no matter how big p and q get. But the factoring bar creeps, then crawls, then barely moves at all. The number of divisors you need to check grows roughly with the square root of n, which means it grows exponentially with the number of digits.

Real RSA keys use primes with over 300 digits each. Multiplying them together still takes a computer a fraction of a millisecond. Factoring the result back apart, with every computer on Earth working together using the best known algorithms, would take far longer than the universe has existed.

That gap, easy one way, impossible the other, is the entire security of RSA. It's called a one-way function, and it's the raw material everything else is built from.

Turning two primes into a padlock and a key

So we have a one-way function. Now we need to turn it into an actual lock and key. Here's the recipe.

Pick two prime numbers, $p$ and $q$. Multiply them to get $n = p \times q$. This $n$ becomes part of your public padlock, the part anyone can see.

Next, compute $\varphi(n) = (p-1)(q-1)$. This counts something specific: how many numbers less than $n$ share no common factor with it. You never publish this number. It only exists to help build the key, and it depends on knowing $p$ and $q$ separately, which is exactly the information factoring is supposed to protect.

Now pick a small number $e$ that shares no common factor with $\varphi(n)$. This becomes your public exponent. The pair $(n, e)$ together is your public key, your open padlock.

Finally, find the number $d$ that satisfies:

In words: multiply $e$ by $d$, divide by $\varphi(n)$, and the remainder is 1. This $d$ is computed using the extended Euclidean algorithm, a fast, direct method, not a search. And $d$ is your private key. It only comes out of the arithmetic if you know $\varphi(n)$, which only comes out of the arithmetic if you know $p$ and $q$.

Try a few different prime pairs. Every single number in that chain, $n$, $\varphi(n)$, $e$, $d$, falls out of just two starting primes. Whoever generated the key is the only one who ever saw $p$ and $q$ directly. Everyone else only sees $n$, and cracking $n$ back into $p$ and $q$ is the hard problem from the last section.

What "encrypt" actually computes

We have a public key $(n, e)$ and a private key $(n, d)$. But what does locking a message actually look like as arithmetic?

Take your message, turned into a number $m$ smaller than $n$. Encryption computes:

That "mod n" part means: do the exponentiation, then keep only the remainder after dividing by $n$. Picture a clock face with $n$ positions instead of 12. Every time your running total would go past $n$, it wraps back around to zero and keeps going.

Computers don't multiply $m$ by itself $e$ times in a row, that would be slow for large $e$. Instead they use a trick called repeated squaring: square the current value, and if the current bit of the exponent is 1, multiply in one more copy of $m$. Repeat once per bit of $e$. A handful of squarings gets you $m^e \bmod n$ in a tiny fraction of the steps a naive approach would need.

Change $e$ and press play. Watch the dot walk around the circle, one squaring at a time, sometimes with an extra multiply thrown in when a bit is set. That walk, landing on a final point, is the entire encryption step.

Decryption is the same operation with the private exponent: $m = c^d \bmod n$. It works and lands you back on the original message because of a fact from number theory called Euler's theorem, which guarantees that raising $m$ to the power $e \times d$ and reducing mod $n$ gets you back to $m$, precisely because $e$ and $d$ were built to satisfy $e \times d \equiv 1 \pmod{\varphi(n)}$.

Locking and unlocking a real message

Let's run the whole thing end to end with small, real numbers: $p = 11$, $q = 13$, so $n = 143$ and $\varphi(n) = 120$. That gives public exponent $e = 7$ and private exponent $d = 103$.

Slide $m$ around. Every value takes the same round trip: lock it with $(n, e)$, get back a scrambled $c$, unlock it with $(n, d)$, and land exactly back on $m$. The two operations are inverses of each other by construction.

Now click "try to break it." An eavesdropper watching the wire sees $n$, $e$, and $c$. Not $d$. To read your message the way you can, they'd need $d$, and to get $d$ they need $\varphi(n)$, and to get $\varphi(n)$ they need $p$ and $q$ separately. Their only path in is factoring $n$ back apart.

For $n = 143$ that takes a handful of tries. For a real key with a 300-digit $n$, that same path is the wall from the second section: technically possible, practically never.

Why 2048 bits is the number you keep seeing

You'll see RSA described as "2048-bit" or "4096-bit." That's just the size of $n$ in binary digits. Bigger $n$ means bigger primes, which means a bigger gap between how fast multiplying is and how slow factoring is.

2048 bits was chosen because it sits comfortably past the point where factoring becomes infeasible with current classical computers and known algorithms, while still being fast enough to compute with billions of times a day across the internet. It's a moving target: as computers get faster, the safe minimum size creeps up, which is why 1024-bit keys, standard twenty years ago, are considered too weak today.

There's one asterisk worth knowing about. A quantum computer running Shor's algorithm could factor large numbers efficiently, which would break RSA's one-way function entirely. Large enough quantum computers don't exist yet, but it's the reason cryptographers are already rolling out post-quantum replacements. The math in this post isn't going anywhere. The specific hardness assumption it leans on might, eventually, need a successor.

The short version

RSA works because multiplying two large primes is fast, and factoring the result back apart is, for large enough primes, beyond the reach of any computer we know how to build. That asymmetry lets you publish a "lock" (the pair $n$ and $e$) that anyone can use to scramble a message to you, while only you hold the "key" (the exponent $d$) built from the two primes nobody else ever saw.

Every encrypted page you've ever loaded ran exactly this arithmetic, just with primes hundreds of digits longer than the toy examples here. Same padlock. Same key. Just numbers too big to crack.

All visualizations are interactive React components running entirely in your browser. The factoring race and the attacker simulation use real trial division on the actual numbers shown, not simulated timings. No libraries beyond React.