RSA Explorer

1. Build the Keypair

Prime p

Prime q

Public exponent e

Public key — share freely

n = p × q3233

e17

Private key — never share

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

d = e⁻¹ mod φ(n)2753

Modulus size12 bits

2. Encrypt and Decrypt

What to encrypt

Message m (must be less than n)

Ciphertext c = m^e mod n

Decrypted m = c^d mod n

3. Sign a Message

Signing runs RSA backwards: the private key produces the signature and the public key checks it.

Signature s = m^d mod n

Verification s^e mod n

4. Break It: Factor the Modulus

RSA's entire security is that nobody can recover p and q from n. For small n that is simply false — and everything unravels: factor n, recompute φ(n), recompute d, read the message.

Trial division here gives up past about 10⁷. Real attacks use the number field sieve — but the principle is identical, and it is why production RSA moduli are 2048 bits or more. A 2048-bit modulus has roughly 617 decimal digits.

How RSA Works

c = m^e mod n m = c^d mod n ed = 1 mod phi(n)

Pick two large primes p and q and multiply them: n = pq. Compute φ(n) = (p−1)(q−1), choose a public exponent e coprime to φ(n), and find d = e⁻¹ mod φ(n) with the extended Euclidean algorithm.

Publish (n, e). Keep d secret — and destroy p and q, because either one hands over d immediately.

Decryption works by Euler's theorem: since ed ≡ 1 (mod φ(n)), we have ed = 1 + kφ(n), so c^d = m^ed = m · (m^φ(n))^k ≡ m · 1^k = m.

e = 65537 is the near-universal choice: it is prime, and its binary form 10000000000000001 has only two set bits, so encryption costs just 17 squarings and one multiply.

What Actually Breaks RSA

Not the mathematics — the implementation. The textbook version above is not safe to deploy, for reasons worth knowing:

It is deterministic. The same message always gives the same ciphertext, so an attacker can encrypt guesses and compare. Real RSA pads with randomness (OAEP) before encrypting.
Small messages with small e. If m^e is less than n there is no wraparound at all, and the attacker just takes an ordinary e-th root. Padding fixes this too.
Shared or predictable primes. Two moduli sharing a prime are both broken by one gcd — and large-scale scans of the internet have found exactly that, caused by weak randomness at key generation.
Timing and power leaks. A decryption that branches on the bits of d leaks d. Constant-time implementations exist for this reason.
And eventually, quantum computers. Shor's algorithm factors in polynomial time, which is why post-quantum migration is under way now — recorded traffic can be decrypted later.

Never implement RSA yourself for production. Use a vetted library. Build it once by hand — like this — to understand it, then never again.

RSA, understood rather than memorised