CS PAPERS DEEP-READ · PAPER 40

RSA Public-Key Cryptosystem

Rivest, Shamir, Adleman · MIT · CACM 1978

What did this paper do?

That little padlock in your browser bar, every online payment, every message no one else can read — almost all of it stands on RSA. In 1977 three people at MIT (Rivest, Shamir, Adleman) built the first genuinely usable "public lock, private key" encryption scheme: the lock you can hand out to everyone, the key only you hold. Today's global HTTPS, digital signatures, and secure payments all trace back to this one paper.

The pain of the old world

Before it, encryption was like an ordinary lock: the same key both locks and unlocks the door. That created a deadlock — to send a stranger a secret message, you first had to get that key safely into their hands; but if you already had a secure channel to pass the key, why encrypt at all? "To communicate securely, first communicate securely" — a chicken-and-egg trap. Billions of stranger-pairs worldwide would each have to secretly swap a key in advance. It simply couldn't scale.

The idea

RSA splits the key in two: a public lock and a private key — and crucially, what the lock closes, only the key can open; the lock can't reopen it. You scatter your public lock like a business card; anyone wanting to send you a secret snaps their message shut with your lock — but once locked, even they can't reopen it. Only you, holding the private key, can. Two total strangers can now communicate securely without ever swapping a secret in advance. The deadlock is broken.

What makes it hold?

The secret hides in an arithmetic fact a schoolchild understands yet the fastest supercomputer chokes on: multiply two very large prime numbers together and you're done in an instant; but hand someone that product and ask which two primes made it, and essentially no one can compute the answer. Like stirring two paints into a new color in a second — then trying to separate them again.

Your "public lock" is essentially that giant product; your "private key" is the pair of primes only you know. Others can use the product to scramble a message (lock it), but without that pair of primes they can't untangle it back (unlock it). Bigger numbers mean more safety — today's numbers are so large that all the world's computers running to the end of the universe couldn't crack them.

Run it backward: signatures

The lock-and-key can also be played in reverse: you "stamp" a document with your private key, and anyone can check it with the public lock you handed out — confirming "this really is from you, and not a word was changed" — because only you hold the private key. This is a digital signature: online contracts, software updates, and certificates all rely on it to prove "I am who I say I am."

Remember one thing

Split the key into a "public lock + private key" — the lock goes to everyone, only you can open it — resting on "multiplying two big primes is easy, factoring the product back is nearly impossible." Strangers communicate securely with no secret swapped in advance, and run backward it also signs. The cost: it's slow (used only to lock one small key), and a future quantum computer could break it.

Want the public/private data-flow diagram, the real formulas, and how the "trapdoor" works? → switch to the deep read

In one sentence

RSA gave the first practical public-key cryptosystem: everyone holds a key pair — a public (n, e) and a private d; anyone can encrypt or verify with your public key, only you can decrypt or sign with the private one. It realizes "encryption" as a single modular exponentiation c = m^e mod n, with security resting on the assumption that factoring large integers is hard: knowing the public n still doesn't yield the private d, because that would require factoring n into two large primes. This paper turned Diffie–Hellman's year-old public-key concept into a concrete, computable algorithm.

Glossary

Cryptography: the study of turning messages into gibberish only an intended party can read, and of verifying a message's authenticity.
Symmetric cipher: the traditional scheme where the same key encrypts and decrypts (e.g., today's AES); fast, but both sides must first secretly share that key.
Public-key cryptography: each person holds a key pair — public key shared, private key kept; one key encrypts and only the other can decrypt, with no pre-shared secret. RSA is its first practical realization.
Prime: an integer divisible only by 1 and itself (2, 3, 5, 61…). Every integer factors uniquely into a product of primes.
Factoring: recovering "which primes multiply to this large integer." Multiplying forward is fast; splitting back is brutally slow — RSA's lifeblood.
Modular arithmetic (mod): "keep only the remainder after division," like a clock wrapping around — 15 mod 12 = 3. Wrapping scrambles and hides the original number.
Modular exponentiation: computing m^e mod n ("multiply m by itself e times, then take the remainder mod n"). Fast algorithms make this instant even for hundred-digit numbers.
Trapdoor one-way function: easy forward, brutally hard to reverse — unless you hold a secret (the trapdoor), which makes reversing easy. RSA's private key is that trapdoor.
Digital signature: an "electronic seal" made with the private key; anyone can verify with the matching public key that it truly came from the owner and was not tampered with.

Where it sits

The authors are Ron Rivest, Adi Shamir, and Leonard Adleman, all then at MIT; the paper was written in 1977 and published in Communications of the ACM in February 1978. It directly follows Diffie and Hellman's 1976 New Directions in Cryptography — which proposed the concept of public keys and digital signatures plus key exchange, but gave no complete scheme that could both encrypt and sign. RSA turned that vision into a computable algorithm for the first time. The three won the 2002 Turing Award. (Later-declassified records show Clifford Cocks at Britain's GCHQ had privately devised an equivalent scheme back in 1973, but secrecy kept it from publication or historical influence.)

The problem and the motivation

Before 1976 all ciphers were symmetric: same key to lock and unlock. That raised two intractable problems.

First, key distribution: to talk secretly, two parties must first share a key — but how do you get that key there safely? If you already had a secure channel for it, why encrypt at all? A chicken-and-egg deadlock. Worse, N people talking pairwise need about N²/2 distinct keys — unmanageable at scale. Second, digital signatures: in the physical world a signature or seal proves "I sent this, unaltered," but with symmetric crypto both sides share one key, so either could forge the other — you cannot prove to a third party who really signed.

Diffie–Hellman pointed the way — split the encrypt/decrypt capability into two asymmetric halves, and negotiate a shared key over a public channel — but they built no concrete scheme that could encrypt an arbitrary message and also sign. The missing piece was a suitable trapdoor one-way function: anyone can compute forward (everyone can encrypt), only the private-key holder can compute backward (only I can decrypt). RSA supplied it.

The core idea

The trapdoor one-way function: turning "hard" into a foundation

For public-key crypto to work you need an operation where given the public key anyone can compute forward (encrypt), but reversing it (decrypt) is infeasible unless you hold the private-key "trapdoor." RSA's trapdoor lives in the gulf between "easy to multiply" and "hard to factor" — multiplying two big primes is instant, yet splitting the product back into primes stalls even the best algorithms and hardware.

Fig 1 · Trapdoor: multiplying p·q into n is instant; factoring n back into p, q is brutal — the wider the gap, the safer, while whoever knows p, q (the private-key holder) skips past it.

Making keys: from two primes to a public/private pair

Key generation is four steps, each only elementary number theory:

① Randomly pick two large primes p, q; multiply to get n = p·q (the modulus, hundreds of decimal digits).
② Compute φ(n) = (p−1)(q−1) (Euler's totient, intuitively "how many numbers from 1 to n are coprime to n"; you need p, q to compute it).
③ Choose a public exponent e coprime to φ(n) (commonly 65537).
④ Find d such that e·d ≡ 1 (mod φ(n)) — i.e., d is the "inverse of e modulo φ(n)," computed instantly by the extended Euclidean algorithm.

So: public key = (n, e), published; private key = d (along with p, q), kept secret. The crux: d is determined by e and φ(n), and φ(n) in turn needs p, q; an outsider sees only n, so to get φ(n) they must first factor n — which is exactly the hard problem.

Encrypt and decrypt: one modular-exponent round trip

Encode the message as a number m smaller than n. Encryption is one modular exponentiation: c = m^e mod n (use the public key to scramble m into ciphertext c). Decryption is another: m = c^d mod n (use the private key to restore c back to m). The two exponents e, d act like a pair of inverse dials — turn e then turn d, and you land exactly back where you started.

Why does it come back around? Because a number-theory fact guarantees m^(e·d) ≡ m (mod n) — since we chose e·d ≡ 1 (mod φ(n)), raising to the e-th then the d-th power circles all the way around modulo n and returns to m (the machinery is Euler's theorem / Fermat's little theorem; the derivation can be skipped, the intuition being "e and d cancel each other modulo φ(n)"). An attacker sees (n, e, c); to solve for m they need d; to get d they need φ(n); to get φ(n) they need to factor n into p, q — every route loops back to the factoring problem.

A real small example (numbers tiny for illustration; real ones are hundreds of digits): take p=61, q=53, so n=3233, φ(n)=3120; take e=17, giving d=2753 (since 17×2753=46801=15×3120+1). Encrypt m=65: 65^17 mod 3233 = 2790; decrypt 2790^2753 mod 3233 = 65, back exactly.

Fig 2 · Encrypt/decrypt: the sender scrambles m into c with "my" public (n,e); c travels an open channel where an eavesdropper lacking d can't recover m; only I, holding d, compute c^d mod n to restore m.

Run it backward: digital signatures

RSA's symmetric beauty is that the two keys can swap roles. To sign, reverse it: the author computes s = m^d mod n with the private key to stamp the message, and anyone computes s^e mod n with the public key — if it restores m, it proves "this truly came from the private-key holder, unaltered," since only they have d and no one else can forge an s that verifies. This made publicly verifiable, non-repudiable electronic signatures possible for the first time. (Real systems hash the message before signing and add proper padding — see limitations.)

Key results

As a 1978 algorithm paper, its "result" is not a benchmark but presenting and arguing the scheme itself is workable and secure: correctness is guaranteed rigorously by m^(e·d) ≡ m (mod n); security reduces to "no efficient algorithm factors n into p, q or derives the private key from the public one." The authors estimated that, with the factoring algorithms of the day, breaking an n of about 200 decimal digits (≈664 bits) would take astronomical time. They also posed the famous RSA-129 challenge (a 129-digit number) with a prize for factoring it — solved only in 1994 by thousands of machines working together, confirming in reverse that "factoring really is hard; only the safety margin must keep rising with compute." Today's practical keys are commonly 2048 bits or larger.

Why it mattered

RSA turned public-key crypto from "a beautiful idea" into a deployable engineering reality, propping up the trust backbone of the modern digital world: the browser–server handshake in HTTPS/TLS, digital certificates and certificate authorities (CAs), PGP email encryption, code and software-update signing, and early e-commerce and online banking all long centered on RSA. It turned "encrypt" and "sign" — things that previously required a pre-shared secret or in-person notarization — into operations any two strangers can perform over an open network. The three authors not only won the Turing Award but founded RSA the company, pushing the algorithm across the whole industry. Without it, there is no internet on which we can safely pay, log in, and communicate.

Limitations and criticism

Slow, unfit for bulk encryption: modular exponentiation is orders of magnitude slower than symmetric ciphers, so in practice RSA almost never encrypts the body directly — instead hybrid encryption uses RSA to encrypt a random symmetric key, and a fast cipher like AES handles the body.
"Textbook RSA" is insecure; padding is mandatory: raw m^e mod n is deterministic (same plaintext always yields the same ciphertext, open to dictionary matching) and malleable (c₁·c₂ is the ciphertext of m₁·m₂, exploitable). Real systems require proper padding (OAEP for encryption, PSS for signatures); Bleichenbacher's attack on the old PKCS#1 v1.5 padding once compromised many systems.
Implementation is full of pitfalls: weak randomness in prime generation, keys sharing a prime factor, small exponents without padding (Coppersmith / Håstad broadcast attacks), and timing/side channels can all break a mathematically sound RSA in practice.
Security is an assumption, not a proof: factoring has never been proven hard, nor has "breaking RSA requires factoring" been proven; a breakthrough in factoring would sink RSA.
The quantum sword of Damocles: Shor's algorithm (1994) shows a sufficiently large quantum computer factors large integers efficiently, fully breaking RSA — the direct driver of today's migration to post-quantum cryptography (PQC).
Not the earliest: GCHQ's Cocks had privately derived an equivalent construction back in 1973, but secrecy kept it unpublished — RSA was the independent and first public invention.

The essentials

① In one line: the first practical public-key scheme — public (n,e) lets anyone encrypt/verify, private d lets only you decrypt/sign.

② The pain: symmetric crypto has the "key distribution" deadlock (to communicate securely, first communicate securely) and can't "prove to a third party who signed"; RSA breaks it with two asymmetric keys.

③ Trapdoor: security rests on "multiplying big primes is easy, factoring the product back is brutal"; whoever knows p, q skips the hard part.

④ Keygen: n=p·q, φ=(p−1)(q−1), pick e, find d≡e⁻¹ (mod φ); d needs φ, φ needs p, q.

⑤ Round trip: encrypt c=m^e mod n, decrypt m=c^d mod n, coming back via m^(ed)≡m (mod n) (Euler/Fermat).

⑥ Reverse = signature: sign s=m^d mod n with the private key, verify s^e mod n with the public one — publicly verifiable, non-repudiable.

⑦ Impact: the foundation of HTTPS/TLS, digital certificates, PGP, and software signing; the trio won the 2002 Turing Award.

⑧ Limits: slow (hence hybrid encryption); insecure raw, needs OAEP/PSS padding; implementation pitfalls; security is an assumption; Shor's algorithm lets a quantum computer break it, driving post-quantum migration.