I didn’t. But working out why taught me more about RSA than any tutorial ever did, because it forced me to find the exact spot where the security lives and poke it.

This post builds RSA from nothing, walks up to that spot, and then documents — with real code, real timings, and a real GPU — everything that happens when you push on it. If you can follow a bit of modular arithmetic, you can follow all of it.

Part I — RSA from scratch

The impossible-sounding problem

Normal encryption has an obvious flaw. If I scramble a message with a key, you need the same key to unscramble it — so I have to get the key to you somehow. But if I could send you a key secretly, I could just send the message secretly and skip the whole thing.

Public-key cryptography solves this with something that sounds like a contradiction:

A key that locks but cannot unlock.

I publish my locking key to the entire world. Anyone can lock a message to me. Nobody can unlock it — not even them, not even holding the locking key. Only my separate, secret unlocking key works.
(more…)