Bob prints the key for letters to him right in the newspaper. How can that key lock a letter but not open it?
Bob wants anyone to be able to write to him in secret, even people he has never met. He prints a key in the newspaper: “encrypt your letters to me with this”. Eve reads the newspaper too. Can it be that Eve holds the very same key and still can’t read a single letter to Bob?
It sounds like nonsense. In every familiar cipher, from Caesar to AES, the same key both locks and unlocks. Whoever knows how to encrypt also knows how to decrypt: just do everything in reverse. Publishing such a key means publishing the secret itself.
In 1976 Diffie and Hellman showed how two people can agree on a shared key in public. But you have to agree anew with every correspondent, and both have to be online at the same time. In the same paper they described a better dream: a cipher with two different keys — a public one to lock and a private one to unlock. They did not know how to build it.
RSA is a public-key cipher: Bob has two keys, and they are different. He hands the public key to everyone and shows the private one to nobody. Everyday life has the same idea — a padlock.
Bob hands out open padlocks to everyone and keeps their key. Alice puts a letter in a box and snaps Bob’s padlock shut on it: no key is needed for that. The box travels to Bob by ordinary post. Eve has Bob’s padlock too, but a padlock can only snap shut.
Simplification: a real padlock can be picked. RSA’s number padlock has a lock pick too — factoring n — but on huge numbers it doesn’t work.
RSA locks with the same operation as Diffie–Hellman: raise a number to a power and take the remainder of a division. What is new is elsewhere: Bob builds the modulus n himself out of two secret primes, and those primes are what let him compute the key. All the examples below use the game’s numbers, where n = 33.
Bob picks two random prime numbers p and q — numbers divisible only by 1 and themselves. In real keys each is 1024 bits long or more, about 309 decimal digits. He hands out their product n = p × q and keeps p and q secret. Multiplying two numbers is easy. Finding which primes a product is made of is hard when the numbers are huge.
Example: p = 3, q = 11, n = 3 × 11 = 33.
Bob computes φ = (p − 1)(q − 1) and picks the padlock’s power e — a number with no common divisors with φ. In real keys it is almost always e = 65537. From e and φ he finds the key’s power d: one for which e · d leaves remainder 1 when divided by φ. The public key is the pair (n, e), the private key is d. Finding d takes φ, and finding φ takes p and q.
Example: φ = 2 × 10 = 20, e = 3, d = 7, because 3 · 7 = 21 = 1 · 20 + 1.
The letter is a number m smaller than n: text is turned into numbers first. Alice takes Bob’s public key and computes c = me mod n. That is “snapping the padlock shut”. The power is worked out in stages: multiply, take the remainder, multiply, take the remainder. The answer is the same as raising to the whole power at once, but the numbers don’t grow. Otherwise no computer could cope with the power 65537 and numbers hundreds of digits long. The number c is sent in the open: without d it is useless.
Example: m = 4. 4 × 4 = 16; 16 × 4 = 64 = 1 · 33 + 31. So c = 31.
Bob raises c to his secret power d with the same modulus and gets the original m. There is no new operation: the method is the same, only the power differs.
Example: 317 mod 33 in stages: 31 · 31 = 961 → 4; 4 · 31 = 124 → 25; 25 · 31 = 775 → 16; 16 · 31 = 496 → 1; 1 · 31 = 31; 31 · 31 = 961 → 4. Bob got m = 4.
Alice raised m to the power e, Bob raised the result to the power d. Together that is me·d. And Bob chose e · d to be 1 more than some multiple of φ. Remainders modulo n have a property (Euler’s theorem): such a power brings every number back to where it was. That is why cd = me·d = m mod n. You can picture it like this: the padlock shuffles the numbers from 0 to n − 1 like cards in a deck, and every number has its own place. The key leads back along the same lines.
Example: 3 · 7 = 21 = 1 · 20 + 1, and 421 mod 33 = 4.
Ronald Rivest, Adi Shamir and Leonard Adleman of MIT spent a year looking for the function Diffie and Hellman had dreamed of. Rivest and Shamir proposed schemes, Adleman broke them. A working scheme on two primes appeared in April 1977; the letters RSA are their initials. In August Martin Gardner wrote about the cipher in Scientific American and published a puzzle: a 129-digit number and a phrase encrypted with it, with a $100 prize. It was solved only in 1994: about 600 volunteers spent eight months factoring the number over the internet. The phrase turned out to be “The Magic Words are Squeamish Ossifrage”.
Britain’s GCHQ got there first here too. In 1973 the young mathematician Clifford Cocks read his colleague James Ellis’s note on “non-secret encryption” and in a single evening found the same two-prime scheme — almost four years before Rivest, Shamir and Adleman. MIT’s patent on RSA ran in the US until September 2000; after that the algorithm became free.
RSA still works all around you, though these days it signs more often than it encrypts:
Most websites’ certificates are signed with RSA, and the browser uses that signature to check that the key really belongs to this site. Sending the connection key with RSA, on the other hand, was banned in TLS 1.3: that is now the job of the Diffie–Hellman exchange.
On the first connection a server or router shows the fingerprint of its public key, and often it is an RSA key. With it the device proves that you are talking to it and not to an impostor.
PGP email, signatures on programs and updates, chip bank cards — anywhere the author has to be checked without ever meeting them.
Both algorithms belong to public-key cryptography, and both compute powers modulo a number, so they are often confused. The difference is in what they do. In the Diffie–Hellman exchange Alice and Bob swap public numbers and each computes the shared key on their own side. Nothing is encrypted there, and both have to take part at the same time. In RSA Bob already has a padlock handed out to everyone in advance: Alice takes it and locks the letter on her own, even if Bob is offline right now.
| Question | RSA | Diffie–Hellman |
|---|---|---|
| What it is for | To lock a letter for one recipient or to sign your own | For two people to get a shared key that later encrypts their messages |
| Must the other side be online | No: Alice already has Bob’s padlock | Yes: each must contribute their own secret number |
| What is sent | The letter itself, locked with the padlock | Only public numbers; neither the letter nor the key is in the channel |
| Keys | Bob’s padlock and key last for years | The secret numbers are chosen anew for every conversation |
| Eve’s hard problem | Split n into two primes | Find the secret number from the public one (discrete logarithm) |
| Analogy | An open padlock | Paints mixed by two people |
Russian standards have no RSA at all. Signatures are made under GOST R 34.10-2012 on elliptic curves, and the shared key is derived with VKO (see the article on Diffie–Hellman). The public key here is a point on a curve, not a product of two primes, so there is nothing to factor. Security rests on a different hard problem — the discrete logarithm.
Locking a letter directly with the public key is not the custom under GOST either: the public key is used only to sign and to derive a shared key, and the letter is then encrypted with a symmetric cipher. In fact, the RSA world does nearly the same: RSA usually locks not the letter itself but a random key for AES.
Yet RSA turns up in Russia every day. Ordinary browsers don’t understand GOST, so even the website certificates issued since 2022 by the national certification authority of the Ministry of Digital Development are signed with RSA. For GOST connections the authority has a separate certificate chain, but such sites open only in browsers that support GOST, such as Yandex Browser.
In the game you will build the key yourself, lock and open a letter, and then try to break it as Eve. What to do:
Both schemes have a key pair, public and private, but the hard problems underneath are different, and so is what they can do:
| Parameter | RSA | GOST R 34.10-2012 |
|---|---|---|
| What the key is made of | Two large primes and their product | A secret number and a point on an elliptic curve |
| Hard problem | Factoring | Discrete logarithm on a curve |
| Key size for ≈ 128-bit security | 3072 bits | 256 bits |
| What it can do | Encryption (with OAEP) and signatures | Signatures; the shared key via VKO |
| Year | 1977 | 2012 (before it, GOST R 34.10-2001) |
| Standard | PKCS #1 (RFC 8017) | GOST R 34.10-2012 (RFC 7091), TC 26 |
RSA numbers are factored with the same number field sieve that threatens Diffie–Hellman, so the security is the same too: 2048 bits roughly equal a 112-bit symmetric key, and 128 bits take 3072. How the records grew: RSA-129 (426 bits) was factored in 1994, RSA-768 in 2009, RSA-250 (829 bits) in 2020. 2048 bits is still very far off, but keys shorter than 2048 bits are considered unsafe today.
The number 65537 = 216 + 1 is prime, and in binary it has only two ones, so a letter can be locked in 17 multiplications. A very small e, such as 3, is dangerous without added randomness: when m3 is smaller than n, the division changes nothing, and Eve simply takes the cube root of c. The game shows this for m = 2 and 3: 23 = 8 is smaller than 33, and c = 8.
In 2012 two research groups collected millions of RSA public keys from the internet and compared them in pairs. Tens of thousands of keys turned out to share prime factors, mostly on routers, network cameras and other devices that created their key right after first power-on, before they had any good randomness. If two n share a p, Euclid’s algorithm finds it in a fraction of a second, and both keys are broken. Primes must be not only huge but truly random.
Shor’s algorithm on a quantum computer would factor n as quickly as it would solve the Diffie–Hellman problem. For RSA the signatures matter most, and their replacement is already prepared: the post-quantum signature standards ML-DSA (FIPS 204) and SLH-DSA (FIPS 205). The second is interesting because it relies only on hash functions, with no number theory at all.
Now you know how to lock a letter with a key everyone has, and why the hardness of factoring alone is not enough
In the game you will choose your own primes, build the padlock’s tape and see Eve read the letter without any factoring