Topic · Computation

RSA & One-Way Functions

Multiplying is easy. Factoring is impossible.

Rivest, Shamir and Adleman, 1977 — the first published public-key cryptosystem and still, almost half a century later, the one securing most of the working internet. The Explorer walks through a complete RSA key-generation, encryption, and decryption on small numbers so you can see every step: choose primes, derive the public and private exponents, then encrypt a message and watch the same maths peel it back open.

Discover the story → Open the Explorer

Step one · The asymmetry

One-way functions: easy forward, hard back

Multiplying two huge primes p and q is fast — a few milliseconds on a phone. Recovering p and q from their product n = p · q is not: the best classical algorithm known (the general number field sieve) runs in sub-exponential but super-polynomial time, and a 2048-bit n is comfortably out of reach for every machine ever built. This one-way property — cheap forward, ruinously expensive backward — is the foundation of public-key cryptography. RSA dresses the asymmetry up so that a public key can be handed to anyone and only the holder of the matching private key can read what was written back.

Step two · Key generation

Pick e, derive d via extended Euclid

Compute φ(n) = (p − 1)(q − 1), Euler's totient — the count of integers in [1, n] coprime to n. Pick a small public exponent e coprime to φ(n); 65537 is the canonical choice because it's prime, has only two bits set, and survives every known low-exponent attack. Then compute the private exponent d = e⁻¹ mod φ(n) using the extended Euclidean algorithm: it returns Bézout coefficients (x, y) with e·x + φ(n)·y = 1, and reducing x mod φ(n) gives d. The public key is the pair (n, e); the private key is (n, d). Throw p and q away once d is in hand.

Step three · Encrypt and decrypt

c = m^e mod n, m = c^d mod n

Treat the plaintext m as an integer in [0, n). The ciphertext is c = m^e mod n; decryption is m = c^d mod n. The reason it works comes straight from Euler and Fermat: because ed ≡ 1 mod φ(n), we have m^(ed) = m^(1 + kφ(n)) ≡ m mod n for every m coprime to n (Euler's theorem), and a short argument with the Chinese remainder theorem extends the identity to every m in [0, n). Square-and-multiply turns the giant exponents into a few thousand modular multiplications — fast in practice, mathematically exact.

Step four · Where it stands today

From TLS to the post-quantum migration

RSA is the maths under every TLS handshake your browser still negotiates with an RSA certificate, under SSH host keys, under the code-signing chains that authenticate apps from Apple and Google, under electronic passports and the early generations of blockchain. But in 1994 Peter Shor wrote down a quantum algorithm that factors integers in polynomial time — given a sufficiently large fault-tolerant quantum computer, RSA breaks. None exists yet, but the timeline is uncertain enough that NIST has standardised post-quantum replacements (CRYSTALS-Kyber for key exchange in 2024, CRYSTALS-Dilithium for signatures) and the global migration is already under way.

Worked example · a complete key pair on small numbers

p = 17, q = 11: the textbook RSA key.

The values below show every quantity in one RSA key. The Explorer lets you change p, q and e, then recomputes the rest, including the extended-Euclidean derivation of d, step by step.

Symbol	Value	Meaning
p	17	first prime (kept secret)
q	11	second prime (kept secret)
n	187	modulus (public)
φ(n)	160	Euler totient (secret)
e	7	public exponent, coprime to φ(n)
d	23	private exponent (secret)

Round trip

Encrypt m = 88: c = 88⁷ mod 187 = 11. Decrypt: 11²³ mod 187 = 88. The maths returns the plaintext exactly because 7 · 23 = 161 ≡ 1 mod φ(n) = 160.

← Back to the atlas

Where you meet it

How and where this technique lives in the world today.

TLS / HTTPS

Every padlock icon in your browser involves either RSA or its elliptic-curve cousin (ECDSA) for the initial handshake — billions of times every second.

Digital signatures

Apple's App Store, Google Play and Microsoft Update sign every release with RSA-style public-key cryptography; if forged, malware would spread freely.

Banking & blockchain

SWIFT messages, debit-card chip transactions and most blockchain wallets rely on hard-factoring or hard-discrete-log assumptions equivalent to RSA.

Identity documents

Modern passports (ICAO 9303) contain RSA-signed biometric data; border control verifies the signature against national CAs.

Post-quantum panic

Shor's algorithm breaks RSA on a sufficiently large quantum computer; NIST is in the middle of standardising post-quantum replacements (Kyber, Dilithium).