Introduction

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.

Build a Keypair

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">Pick two small primes. The demo multiplies them into a public modulus <b>n</b>, derives a public key <b>e</b> and a private key <b>d</b>, then encrypts and decrypts a number. Multiplying is instant — <b>factoring n back</b> is what an attacker must do, and here it’s easy only because the primes are tiny.</p>
<div class="row">
  <label>prime p <select id="p"></select></label>
  <label>prime q <select id="q"></select></label>
  <label>message m <input id="m" type="number" min="2" value="9"></label>
</div>
<button id="gen" type="button">Build keypair &amp; encrypt</button>
<pre id="out" class="out">Press the button to build a keypair.</pre>
<div class="btns">
  <button id="break" type="button" class="danger">Break it (factor n)</button>
  <button id="reset" type="button" class="ghost">Clear</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// RSA in miniature. Security rests on a one-way gap: multiplying two primes is
// easy, factoring the product n = p*q is believed hard. Here the primes are tiny,
// so the "attacker" factors n by trial division and rebuilds the private key d —
// exactly the attack that becomes infeasible when n has hundreds of digits.
const PRIMES = [3,5,7,11,13,17,19,23,29,31,37,41,43,47];

function gcd(a,b){ while(b){ [a,b]=[b,a%b]; } return a; }
// modular exponentiation: base^exp mod m, without overflow
function modpow(base,exp,m){ let r=1n; base%=m; while(exp>0n){ if(exp&1n) r=(r*base)%m; exp>>=1n; base=(base*base)%m; } return r; }
// modular inverse of e mod phi via extended Euclid
function modinv(e,phi){ let [old_r,r]=[e,phi],[old_s,s]=[1n,0n];
  while(r!==0n){ const q=old_r/r; [old_r,r]=[r,old_r-q*r]; [old_s,s]=[s,old_s-q*s]; }
  return ((old_s%phi)+phi)%phi; }

function fillSelect(id,def){ const el=document.getElementById(id); el.innerHTML='';
  PRIMES.forEach(p=>{ const o=document.createElement('option'); o.value=p; o.textContent=p; if(p===def)o.selected=true; el.appendChild(o); }); }
fillSelect('p',11); fillSelect('q',13);

let state=null; // {p,q,n,e,d,m,c}

function gen(){
  document.getElementById('attack').textContent='';
  document.getElementById('attack').className='attack';
  const p=parseInt(document.getElementById('p').value);
  const q=parseInt(document.getElementById('q').value);
  const out=document.getElementById('out');
  if(p===q){ out.textContent=`Pick two DIFFERENT primes (p ≠ q).`; state=null; return; }
  const n=BigInt(p)*BigInt(q);
  const phi=BigInt(p-1)*BigInt(q-1);
  // choose public exponent e coprime to phi
  let e=3n; while(gcd(e,phi)!==1n) e+=2n;
  const d=modinv(e,phi);
  let m=BigInt(parseInt(document.getElementById('m').value||'0'));
  if(m<2n||m>=n){ out.textContent=fmt(`Message m must satisfy 2 ≤ m < n = %n%. Try a smaller m.`, { n: n }); state=null; return; }
  const c=modpow(m,e,n);          // encrypt with public key
  const back=modpow(c,d,n);       // decrypt with private key
  state={p,q,n,e,d,m,c};
  out.textContent =
    fmt(`Public key  : (n=%n%, e=%e%)   ← anyone can use this to encrypt
Private key : (n=%n%, d=%d%)   ← kept secret
n = p*q = %p% * %q% = %n%   (built by one easy multiplication)

encrypt: c = m^e mod n = %m%^%e% mod %n% = %c%
decrypt: m = c^d mod n = %c%^%d% mod %n% = %back%%v%`, { n: n, e: e, d: d, p: p, q: q, m: m, c: c, back: back, v: back===m? '  ✓ recovered!' : '  ✗ mismatch' });
}

function attack(){
  const box=document.getElementById('attack');
  if(!state){ box.textContent=`Build a keypair first.`; box.className='attack'; return; }
  const {n,e,c}=state;
  // The attacker only knows the PUBLIC values n, e, c. Factor n by trial division.
  let steps=0, f=0n;
  for(let i=2n;i*i<=n;i++){ steps++; if(n%i===0n){ f=i; break; } }
  if(f===0n){ box.textContent=`n is prime — not a valid RSA modulus.`; return; }
  const p2=f, q2=n/f;
  const phi2=(p2-1n)*(q2-1n);
  const d2=modinv(e,phi2);          // attacker rebuilds the private key
  const m2=modpow(c,d2,n);          // and decrypts the ciphertext
  box.className='attack ok';
  box.textContent =
    fmt(`Attacker sees only public n=%n%, e=%e%, c=%c%.
Factored n in %steps% trial divisions:  n = %p2% * %q2%
Rebuilt φ(n)=(%p2%-1)(%q2%-1)=%phi2%  →  private d=%d2%
Decrypted stolen message:  c^d mod n = %m2%   %v%

With real RSA n has ~600 digits and this factoring step is infeasible.`, { n: n, e: e, c: c, steps: steps, p2: p2, q2: q2, phi2: phi2, d2: d2, m2: m2, v: m2===state.m?`✓ matches the secret!`:'' });
}

document.getElementById('gen').addEventListener('click',gen);
document.getElementById('break').addEventListener('click',attack);
document.getElementById('reset').addEventListener('click',()=>{ state=null;
  document.getElementById('out').textContent=`Press the button to build a keypair.`;
  document.getElementById('attack').textContent=''; document.getElementById('attack').className='attack'; });
gen();
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/rsa/Content licensed under CC BY-NC 4.0.