RSA: The Internet’s Favorite Math Trick (Until Quantum Computers Show Up)

Most people use cryptography every day. They log into websites. They check their bank balances. They send messages. They order things they absolutely do not need from online retailers at 2:00 AM.

Almost nobody thinks about the mathematics making all of this possible. And honestly? That’s probably healthy. Because the deeper you go into cryptography, the more it starts to resemble a cult dedicated to prime numbers.

Today we’re talking about RSA (Rivest-Shamir-Adleman) Algorithm. This is one of the most important cryptographic algorithms ever invented and the reason countless internet transactions remained secure for decades. It’s based on a paper that was first published in 1977.

At its core, RSA is built on a surprisingly simple idea that Multiplying large prime numbers is easy. Factoring them back apart is hard.

Human civilization looked at this fact and collectively decided, “Excellent. Let’s build the global economy on it.”

Here’s how the algorithm works.

Step One: Find Two Prime Numbers

Let’s pick two prime numbers:

• 61
• 53

We’re picking these specific numbers in this example because 1) they happen to both be prime numbers and 2) this is the example used in the original RSA paper.

Multiply them together:

61 × 53 = 3233

Congratulations. You’ve just performed the foundational operation behind one of the most influential cryptographic systems ever created.

Your number, 3233, becomes part of the public key.

Everybody gets to see it.

Nobody cares.

At least not yet.

Step Two: Summon Euler From The Grave

Cryptographers cannot simply leave well enough alone.

Instead of stopping at multiplication, they invoke a famous piece of number theory called Euler’s Totient Function.

For a number that is the product of two primes:

φ(n) = (p − 1)(q − 1)

So:

φ(3233) = 60 × 52 = 3120

If you’re wondering why we’re doing this, don’t worry.

Thousands of software engineers use RSA every day without remembering why we’re doing this.

Step Three: Choose A Public Exponent

Choose a number e, called the encryption exponent, such that

• 1 < e < Φ(3233) = 3120, and
• gcd(e, Φ(3233)) = 1, that is e should be co-prime with Φ(3233).

For our example:

e = 17

Note, 1 < 17 < 3120 and gcd(17, 3120)= 1.

This becomes part of the public key.

The public key is now:

(3233, 17)

This information can be shared with the entire planet.

Print it on a billboard.

Tattoo it on a yak.

Erect as many meaningless corporate policies surrounding securing the public X509 certificate (public key) as you want — even though your web servers spit it out on every TLS connection to every browser.

Doesn’t matter.

It’s public information per the spec, the algorithm, and the math.

Step Four: Compute The Secret Number

Now we calculate d, the decryption exponent, such that:

• (d * e) ≡ 1 mod Φ(3233) = 3120, that is d is modular multiplicative inverse of e mod Φ(3233) = 3120.
• We can have multiple values of d that satisfy (d * e) ≡ 1 mod Φ(n**)**, but it does not matter which value we choose as all of them are valid keys and will result into same message on decryption.

This is where the magic happens. We need a number such that:

17d ≡ 1 (mod 3120)

After some mathematical wizardry (that we don’t bother going into here):

d = 2753

This becomes the private key. Or, (3122, 2753), ie, (n, d).

The public key can be shared with everyone.

The private key should be protected with the same level of paranoia normally reserved for nuclear launch codes and fantasy football passwords. Somehow, the corporate chain-of-trust key material processes seem to fall short more-often-than-not.

Encryption

Suppose we want to encrypt the number:

65

RSA encryption is astonishingly simple:

Raise the message to the power of e.

Then take the remainder when dividing by n.

In our example:

65^17 mod 3233 = 2790

The encrypted message becomes:

2790

Somehow we’ve transformed 65 into 2790.

Mathematicians are very proud of this.

Decryption

To recover the original message, we use d:

2790²⁷⁵³ mod 3233

The result:

65

The original message returns.

Like a magic trick performed by someone with an advanced degree in number theory and poor social skills.

Why Does This Work?

This is where RSA becomes genuinely clever.

Euler’s theorem tells us that certain exponent operations eventually loop back on themselves.

The public exponent and private exponent are carefully chosen so that:

• Encryption scrambles the message.
• Decryption perfectly reverses the process.

It’s essentially a giant mathematical lock and key mechanism built from modular arithmetic.

We weaponized remainders.

What Is Modular Arithmetic?

Imagine a clock.

If it’s 11 o’clock and three hours pass, you don’t get 14 o’clock.

You get 2 o’clock.

The numbers wrap around.

Mathematicians call this modular arithmetic.

Normal people call it “a clock.”

RSA performs all of its calculations inside a giant mathematical clock containing numbers hundreds of digits long.

Why Attackers Can’t Just Calculate The Private Key

The public key contains:

• n
• e

But to compute the private key, an attacker must know the original prime factors (recall, we choose those at the beginning of this blog post):

• p
• q

That means they must factor n. For our tiny example 3233, that’s easy. For a real RSA key, good luck. Modern RSA keys are typically 2048 bits or larger.

Factoring those numbers with classical computers is so difficult that the heat death of the universe begins to look like a practical project timeline.

The Tiny Problem Called Quantum Computing

RSA’s security depends on factoring being hard.

Then, quantum computing arrived and said that’s a lovely security assumption you have there. A quantum algorithm known as Shor’s Algorithm can factor large numbers dramatically faster than classical computers.

The entire RSA security model suddenly develops a concerning expiration date. It’s a bit like discovering your bank vault is secure against every burglar on Earth but vulnerable to one very specific wizard who may or may not appear in twenty years.

We’re exploring quantum computing as part of this series.

Why RSA Was Revolutionary

Despite its looming quantum problems, RSA changed everything. For decades it enabled:

• Secure web browsing
• Online banking
• Digital signatures
• VPNs
• Email encryption
• Software verification

Entire industries depended on the fact that multiplying primes is easy while factoring them is hard. Which is an absolutely ridiculous foundation for modern civilization when you think about it.

And yet it worked.

Beautifully.

Summary

Most people do not need to know how RSA works. In the same way most people do not need to know how jet engines work.

Or, power grids.

Or, why printers become possessed whenever you’re in a hurry.

Or, why only an odd number of socks exit the dryer even though an even number of socks went in.

But, RSA remains one of humanity’s most elegant mathematical achievements.

It took prime numbers, modular arithmetic, and a few centuries of number theory and transformed them into a system capable of securing the internet.

Not bad for a bunch of mathematicians playing with remainders.

Notes

• AI / GenAI / ChatGPT / etc were not used to generate the text of this article.
• ChatGPT was used to generate the images.
• I used em dashes in my writing before the current GenAI wave was a thing. Not planning on changing now.
• Names have been changed to protect the guilty.
• None of the hostnames or users used in examples actually exist.
• Feel free to post any comments or suggestions below.