RSA

Every time you see a padlock in your browser, a piece of mathematics from 1977 is quietly at work. RSA — named for Rivest, Shamir and Adleman, who published it in 1978 — was the first practical way to let two strangers exchange secrets without ever sharing a password in advance.

The whole trick rests on one lopsided fact about numbers. Take two large prime numbers and multiply them: a computer does it in microseconds. Now take only their product and try to recover the two primes — factor it back. Nobody knows a fast way to do that, and people have tried for centuries.

That gap between easy forward and hard backward is what a one-way function means. RSA turns it into a lock: multiplying builds the lock in public, while factoring — the only obvious way to pick it — stays out of reach.

Here is RSA shrunk down to numbers you can read. Pick two small primes, and the demo builds a public key (used to encrypt) and a private key (used to decrypt). Send a number through and watch it come back.

<p class="hint">{{hint}}</p>
<div class="row">
  <label>{{label_p}} <select id="p"></select></label>
  <label>{{label_q}} <select id="q"></select></label>
  <label>{{label_m}} <input id="m" type="number" min="2" value="9"></label>
</div>
<button id="gen" type="button">{{btn_gen}}</button>
<pre id="out" class="out">{{btn_prompt}}</pre>
<div class="btns">
  <button id="break" type="button" class="danger">{{btn_break}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="attack" class="attack"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.row { display: flex; gap: .8rem; flex-wrap: wrap; margin: .4rem 0 .7rem; }
label { font-size: .85rem; font-weight: 600; color: #1d3557; display: flex; flex-direction: column; gap: .25rem; }
select, input { font: 600 14px ui-monospace, monospace; padding: .35rem .5rem; border: 1px solid #adb1b8; border-radius: 6px; min-width: 5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.danger { background: #e63946; border-color: #c92f3c; }
.out { background: #f3f6f9; border: 1px solid #cdd9e3; border-radius: 8px; padding: .7rem .8rem;
       font: 600 13px ui-monospace, monospace; color: #1d3557; white-space: pre-wrap; line-height: 1.6; margin: .3rem 0 .7rem; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
.attack { font: 600 13px ui-monospace, monospace; color: #c92f3c; margin-top: .6rem;
          white-space: pre-wrap; line-height: 1.6; min-height: 1em; }
.attack.ok { color: #0a7d33; }

// Code not found

Then press Break it. Because the primes are tiny, the attacker can simply factor the public modulus, rebuild the private key, and read your message. With real RSA the modulus has hundreds of digits and that same factoring step would take longer than the age of the universe. The security is not magic — it is entirely the difficulty of factoring.

How safe is RSA, really? The honest answer is unsettling: nobody has proven it is hard to break.

• Encrypting and decrypting are easy. Modular exponentiation — the core operation — runs in polynomial time, so the legitimate parties are always fast.
• Breaking it means factoring. Recovering the private key from the public one comes down to splitting the modulus into its two primes. The best known classical algorithm, the general number field sieve, is sub-exponential — far faster than trying every divisor, but still far too slow at real key sizes.
• No proof of hardness exists. Factoring lives in NP, but it is not known to be NP-complete, and no one has shown it cannot be done quickly. If a fast factoring algorithm were found — or if P vs NP collapsed the gap — RSA would fall overnight.
• Quantum changes everything. In 1994 Peter Shor gave an algorithm that factors in polynomial time on a quantum computer. Large enough quantum hardware does not yet exist, but its mere possibility is why the world is migrating to post-quantum cryptography.

So RSA's strength is a conjecture we lean on, not a theorem we own. It has survived decades of attack, which is reassuring — but its security rests on the unproven belief that factoring is hard.

"Let anyone lock a message, but only one person open it" is exactly the shape of trust the internet needs, and RSA was the first tool to deliver it:

• Secure web traffic: TLS handshakes long used RSA to exchange the keys that protect your browsing session behind that little padlock.
• Digital signatures: run RSA backwards and you can sign a document — anyone can verify it came from you, but only you could have produced it.
• Software updates and certificates: your devices trust an update because it carries a signature only the vendor's private key could create.
• The whole public-key idea: RSA proved one-way functions could be practical, opening the door to Diffie–Hellman, elliptic curves and the entire field of public-key cryptography.

Understand RSA and you understand the bargain the internet quietly makes a billion times a day: convenience now, resting on the belief that factoring stays hard tomorrow.

RSA is a beautiful piece of leverage: from a single asymmetry — multiplying primes is trivial, factoring their product is not — it built a way for strangers to trust each other across an open network. Encrypting stays instant; breaking it stays, as far as anyone can show, out of reach.

But the lock is only as strong as the conjecture under it. The day someone factors quickly — by clever mathematics or a working quantum machine running Shor's algorithm — the padlocks pop open. RSA is not a fortress proven impregnable; it is a wager that factoring is hard, and so far the bet has held.