The Aha-Moment of Public-Key Encryption

A small idea behind the huge topic

I started my deep dive into cryptography six months ago. I wanted to deconstruct its internals into basic building blocks and then build them back up again. One simple idea kept pulling me forward—fascinating me and motivating me to go deeper: how can a crowd of absolute strangers—over the internet, an inherently insecure medium—exchange information securely?

I won’t lie: I honestly expected to find one simple answer that would “click” and give me an Aha moment. Instead, I fell into a rabbit hole. One idea led to another; one logical structure interacted with—and depended on—another. Math, history, logic, statistics. Topics and disciplines intertwined into a complicated, sophisticated ornament. No final answers—only more questions, theories, experiments, and try-and-fail stories. Stories of absolute trust and absolute failure, of elegant ideas that didn’t work, of intuition that misled, and of randomness that won. Brilliant people built brilliant solutions—some failed, then came new solutions, and new solutions again, until something finally held. The long, long, long road to security… Yes, it was a fascinating journey. And in the end, I finally understood how the philosopher’s stone of public-key encryption works.

As we saw in the previous articles, the first challenge was to build a secure and reliable way for two peers—who know each other and share a secret key—to communicate. It doesn’t sound difficult, yet it took more than ten articles to show how to do it properly (and how many ways it can go wrong).

The next challenge is to achieve the same goal for… strangers… who share no key at all.

I want to keep it short this time. The internet is full of articles that implement protocols and asymmetric ciphers. Here I just want to show the core idea as simply as possible. I want to give you the Aha moment I was searching for—and then point you to deeper references if you’re interested in real-world usage and implementation. Or we can go further: tell me what topic you want next, and I’ll happily write about it.

So, let the show begin—and please follow my hands very carefully.

---

The “Aha-math” behind public-key encryption

Let’s take two prime numbers (numbers divisible only by 1 and themselves):

p = 3
q = 11

These will be the foundation of everything that follows.

Now let’s multiply them:

n = p * q = 3 * 11 = 33

This number, n, will be our modulus.

Modulo arithmetic simply means that numbers “wrap around” after reaching a certain value. If the result of an operation (addition, multiplication, etc.) is larger than the modulus, we divide by the modulus and take the remainder.

For example:

result = 23 + 11 = 34
result = 34 % 33 = 1

Because 34 divided by 33 leaves a remainder of 1.

You can imagine modulo arithmetic as an infinite array that keeps repeating the same sequence of numbers:

modulo_array_33 = [0,1,2,3,...,31,32,0,1,2,3,...,31,32,0,...]

So when we compute:

print(modulo_array_33[34])
# 1

We “wrap around” and land back at 1.

---

Next, let’s consider all numbers from 1 to 33:

S = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32}

Now we ask: how many of these numbers do not share a common divisor with 33?

In other words, how many numbers are relatively prime to 33?

There is a beautiful formula for that:

f = (p-1)*(q-1) = (3-1)*(11-1) = 2*10 = 20

So there are 20 numbers that are relatively prime to 33.

This number f is known as Euler’s totient of n. It plays a central role in RSA.

---

Now the most mystical part begins.

We need to choose a number e that is relatively prime to 20.

e = 3

3 and 20 share no common factors — so this works.

Now comes the heart of the magic.

We need to find a number d such that:

e * d ≡ 1 (mod f)
3 * d ≡ 1 (mod 20)

We are looking for a number d that, when multiplied by 3, leaves remainder 1 after division by 20.

It turns out:

d = 7

Because:

3 * 7 = 21
21 % 20 = 1

You’ll be surprised — at least, I was. At this point we’ve already built everything we need for public-key encryption. Now let me show you.

---

Suppose we want to encrypt the number:

m = 4

Our public key is two numbers that we previously created:

public_key = (n, e) = (33, 3)

To encrypt:

ciphertext = m**e mod(n) = 4**3 % 33 = 64 % 33 = 31

So the ciphertext is:

31

Now we decrypt using the private key d = 7:

message = ciphertext**d mod(n) = 31**7 % 33 = 27512614111 % 33 = 4 # 0_o

4

Exactly the original message.

---

And this — in its purest, smallest, most transparent form — is how RSA works.

Why does it work?

In the small examples, it almost feels like a trick: we raise a number to one power, then to another, and somehow everything “cancels out” and the original message comes back. But what’s really happening is simpler—and honestly, more beautiful. When you work modulo a number, powers don’t grow forever; they eventually start repeating. You’re operating inside a finite world, so exponentiation can’t keep producing “new” values indefinitely—at some point it must loop. In our tiny example the loop is short, so you can literally watch it happen by hand. RSA chooses the public exponent and the private exponent so that, together, they make you go “one full loop plus one extra step.” Encryption moves you forward along that loop, and decryption moves you forward again in a way that lands you exactly back at the starting point. With small numbers the cycle is visible; with real RSA it’s the same mechanism, just scaled to cycles that are unimaginably large. The math isn’t magic—it’s controlled movement inside a huge circular system, with the steps chosen so that going forward twice brings you back home.

It took me a while to understand the math behind this. If you want the deeper, more formal explanation, I highly recommend Appendix A of A Graduate Course in Applied Cryptography: https://toc.cryptobook.us/book.pdf

Why is it secure?

In the examples above I deliberately used tiny numbers (like 3, 11, and 33) because that’s the only way to see the whole mechanism with your own eyes and not drown in computation. But with numbers that small, RSA is basically a toy: anyone can factor n in seconds, reconstruct the hidden structure, and “unlock” everything. In real life it’s the same exact workflow—just scaled up brutally. p and q are enormous primes (hundreds of digits), so n becomes massive. It’s still easy to multiply two huge primes and publish n, but it becomes practically impossible to run that process backwards and recover the original primes from n. And that’s the whole point: if you can’t factor n, you can’t rebuild the private key. Small numbers help you understand the idea; huge numbers are what make the idea survive contact with the real world.

If you want a more implementation-oriented walkthrough of RSA, here’s a practical reference: https://www.geeksforgeeks.org/computer-networks/rsa-algorithm-cryptography/

Final word

I deliberately kept this article as small and abstract as possible—not to avoid details, but to show the core idea behind the whole concept. There are many related topics that go deeper and wider: real-world protocols, padding schemes, key formats, attacks, implementation traps, and all the practical engineering that turns “nice math” into something you can safely deploy. It’s an endless rabbit hole, and it makes no sense to cram all of it into one post.

What I wanted here was the quintessence: one core idea. The mechanism. The “Aha.” And I hope it landed.

Thank you for staying with me for so long. With this, I’m closing my cryptography series and moving on to the next technologies.

As always, I’m open to suggestions and requests—feel free to drop me a note ;)