cryptography.education / public-key / rsa

RSA, step by step — and why textbook RSA is broken

Key generation, encryption, decryption and signing, one operation at a time. The extended Euclidean algorithm is shown as a Bézout table with the coefficient recurrence worked out row by row, because that is the step students always lose; modular exponentiation is traced bit by bit, square and multiply. Then the page shows what textbook RSA fails at — deterministic ciphertexts, small messages under a low exponent, and the same message sent to several recipients — so that the reason OAEP and PSS exist is a demonstration rather than a claim. Every number is computed by the implementation on this page and cross-checked in the browser by a second, independently written implementation.

Textbook RSA, live — break it three ways

The core on this page is deliberately textbook RSA: no padding, so the ciphertext is just c = m^e mod n of the raw message integer. Everything below is computed live, and the same key the stepper is using is reused here, so the numbers line up with the walkthrough above. Each of the three panels recovers something it should not be able to recover — that is the argument for OAEP and PSS, and it is stronger than any sentence saying so.

1. Encryption is deterministic — so it is not IND-CPA

Encrypt the identical message twice with the same public key. A real scheme must produce different ciphertexts each time (randomised padding); textbook RSA produces the identical integer. An eavesdropper then knows any repeated ciphertext is a repeated message, without breaking anything: a guessing attack on a small message space is enough. Try it with a message like yes or no and compare.

2. Small message, low exponent — a plain integer e-th root

If the message is small enough that m^e < n, then the modular reduction never happens and the ciphertext is exactly m^e over the integers. No key is needed to invert that: an ordinary integer e-th root recovers m in milliseconds. This is why e = 3 is only acceptable with a padding scheme that spreads the message across the whole modulus. The panel uses the textbook exponent e = 3 regardless of the exponent above; it computes the root live with Newton's method on integers, and also reports a bound on which messages are exposed.

3. The same message to several recipients — CRT recovery

Håstad's broadcast attack. If the same unpadded message is sent to several recipients each with e = 3 and different moduli n_i that are pairwise coprime, the ciphertexts are c_i = m³ mod n_i. The Chinese Remainder Theorem reconstructs M = m³ mod (n₁n₂n₃), and since m is small, M = m³ exactly — so one integer cube root recovers the message with no private key at all. All three keys here are generated live on this page from three independent prime pairs. The lesson is not "don't use 3": it is that security must never depend on the message happening to be small, which is precisely what randomised padding guarantees.

Padding is not optional. RSA encryption needs a randomised, message-recovering encoding — OAEP (RFC 8017 §7.1) — and RSA signatures need a randomised, hashed encoding — PSS (RFC 8017 §8.1). Every failure above disappears once the input to the modular exponentiation is a full-width, structured, randomised value rather than the message itself or m re-encoded as a bare integer.

Notation

p, q	Two large secret primes. Their product is public; the primes are the trapdoor. Very roughly, a 2048-bit modulus means two 1024-bit primes.
n = p·q	The modulus. Public. Its bit length (2048/3072/4096) names the key size. Recovering p and q from n is integer factorisation, believed hard.
φ(n)	Euler's totient, = (p−1)(q−1) because p and q are prime. The order of the multiplicative group ℤ_n*. Secret in practice.
λ(n)	The Carmichael function, lcm(p−1, q−1). The true group exponent: λ(n) \| φ(n), so d ≡ e⁻¹ (mod λ(n)) also works and is what real keys use. λ(n) = φ(n)/gcd(p−1,q−1).
e	The public exponent. Must satisfy gcd(e, λ(n)) = 1 so that an inverse exists. 65537 = 2¹⁶+1 is the standard choice.
d	The private exponent, d = e⁻¹ mod λ(n) (here we show d = e⁻¹ mod φ(n), see the note on the step). Because (m^e)^d ≡ m, d is the decryption key and the signature key.
(n, e)	The public key. Anyone may have it.
(n, d)	The private key — plus p and q and everything derivable from them. Keep all of it.
m	The message as an integer in [0, n). In real RSA this is a padded encoding, never the raw text.
c = m^e mod n	Encryption, equally the signature verification operation.
m = c^d mod n	Decryption, equally the signature generation operation.
square-and-multiply	Computing m^e mod n in ≈log₂e modular multiplications by reading the exponent's bits, squaring each time and multiplying in when the bit is 1. This is the whole of "modular exponentiation".
H(m)	A hash of the message. Signature schemes sign a digest, not a message, because RSA can only exponentsiate something smaller than n.

Glossary

The one-way function: integer factorisation

RSA's security assumption is that computing p and q from n = p·q is hard, while computing n from p and q takes one multiplication. Nobody has proved factorisation is hard; the evidence is decades of effort and the fact that the best known algorithms (the number field sieve) cost sub-exponential but still super-polynomial time — around 2¹¹² operations for a 2048-bit modulus, with ~2⁸⁰ classical memory-free variants for the best attacks. Multiplication is one instruction; its inverse is a research programme.

The private key is d, but everything secret is derivable from p and q. Equivalently, anyone who can factor n has the private key, so "RSA is broken" and "this modulus is factored" are the same statement.

Why e must be coprime to φ(n) (and to λ(n))

Decryption works because (m^e)^d ≡ m. That identity holds when ed ≡ 1 modulo the order of the group element m, and λ(n) = lcm(p−1, q−1) is an exponent of the whole group, with φ(n) a multiple of it. So we need a d with ed ≡ 1 (mod λ(n)), and such a d exists iff gcd(e, λ(n)) = 1 — Bézout's identity guarantees the modular inverse precisely in that case, and returns nothing otherwise. If you pick e sharing a factor with p−1 or q−1, no private exponent exists at all and the key is unusable; the page refuses such a key rather than inventing a d.

A subtlety worth knowing: it is not quite true that you must have gcd(e, φ(n)) = 1 for correctness when you define d mod φ(n) — with d ≡ e⁻¹ mod φ(n), the identity ed = 1 + kφ(n) still yields m^ed ≡ m for every m coprime to n by Euler, and for the non-coprime cases by the CRT argument. What is actually required is gcd(e, λ(n)) = 1, and with a prime modulus and e = 65537 both branches coincide in practice. The page checks the condition that matters and says which one it checked.

Why e = 65537 — and why e = 3 is not wrong by itself

65537 = 2¹⁶+1 is prime, so gcd(65537, λ(n)) = 1 except for the astronomically unlikely case that λ(n) is a multiple of 65537. Its binary form is 10000000000000001: fifteen zeros then two ones, so square-and-multiply performs 17 squarings and exactly one multiplication — the cheapest possible exponent that is not tiny. It is also large enough that the small-message failure (panel 2) essentially never applies, and old implementations that skipped the 2⁴+1 = 17 and 3 branches are the historical reason Fermat numbers are avoided below 65537.

e = 3 is not broken on its own. It satisfies all the arithmetic requirements, is even faster, and is perfectly safe when combined with a proper encoding — some systems (old X.509 roots, ISO 9796, and PSS with e = 3) use it. It is dangerous for exactly two reasons: a small exponent makes the raw-message failure far easier to hit, and it makes the broadcast case trivial, since three honest signatures of the same short value already suffice. The right conclusion is neither "3 is banned" nor "3 is fine", but "the encoding is what supplies the security, not the exponent".

Public operation vs private operation

Encrypting uses the public key (m^e mod n) and anyone can do it; decrypting uses the private key (c^d mod n) and only the holder can. Because the public key is public, encryption provides no authentication at all: any sender could have produced that ciphertext. Anyone who can read a public key can forge a message to that key's owner.

Signing uses the private key (s = H(m)^d mod n) and anyone can verify with the public key (s^e mod n = H(m)). Here the asymmetry does the opposite job: only the key holder could have produced s, so this gives integrity and non-repudiation, and no confidentiality. Same arithmetic, opposite key order, opposite guarantee.

Why signing is not the same as encrypting

Mechanically, RSA signing and RSA decryption are the same operation: raise something to the power d modulo n. That is exactly why textbook RSA must never be used for either without an encoding. In the raw scheme, the "signature" of m is the ciphertext of a decryption of m — so the two operations are interchangeable, and an attacker can turn one into the other: ask a signer to sign a value that is really a ciphertext and you have decrypted it (a chosen-message attack, and the reason a signature oracle must never be usable as a decryption oracle).

Three consequences follow, and all of them are structural. (1) The inputs must be typed and encoded differently: OAEP for encryption is a randomised, message-recovering encoding; PSS for signatures is a randomised, hashed encoding with a salt. They are deliberately incompatible. (2) The threat model flips. For encryption the attacker holds the public key and wants the plaintext; for signatures the attacker wants a valid signature and may choose messages, so the scheme must be existentially unforgeable under chosen message attack (EUF-CMA) — a notion that is not even expressible for a deterministic raw signature, where the signature is a fixed function of the message. (3) The key must be typed: a key pair generated for one purpose must not be used for the other, or an attack against the weaker direction leaks the stronger one.

What real RSA is — key sizes, encodings, and what comes next

Key sizes. 1024-bit RSA is deprecated and practically factored-adjacent; 2048-bit is the current floor, 3072-bit matches ~128-bit security, and 4096-bit is a common conservative choice with a noticeable performance cost. Picking a key size is choosing a bit-security target: 2048 → ~112 bits, 3072 → ~128 bits, 1536 and below → do not use.

Standard encodings. Encryption is RSAES-OAEP (RFC 8017 §7.1) and signatures are RSASSA-PSS (RFC 8017 §8.1). PKCS#1 v1.5 encryption is the older encoding and its randomised structure is not provably secure — Bleichenbacher's attack (1998) and its successors mean it should not be used for new work; PKCS#1 v1.5 signatures with a correct implementation are still widely deployed for compatibility, but PSS is preferred. The raw RSAES-PKCS1-v1_5 oracle was the root cause of decades of padding-oracle breaks.

Size limit. RSA can encrypt only a value smaller than n, and with OAEP the usable payload for a 2048-bit key is roughly 190–256 bytes depending on hash. RSA is therefore never used to encrypt bulk data. The shape is hybrid encryption: KEM + DEM — RSA-OAEP (acting as a key encapsulation mechanism) wraps a random symmetric key, and that key drives AES-GCM or ChaCha20-Poly1305 (the data encapsulation mechanism) over the actual message. This is exactly the shape of TLS 1.3's key schedule, except TLS 1.3 dropped RSA key transport in favour of ephemeral (EC)DHE and uses the certificate only for authentication.

Migration direction. RSA is being replaced by elliptic-curve signatures — ECDSA (FIPS 186-4, P-256/P-384) and EdDSA/Ed25519 (RFC 8032) — because they reach the same security at far smaller keys (256-bit Ed25519 ≈ 3072-bit RSA) and much faster verification. For post-quantum resistance, NIST standardised ML-KEM (FIPS 203, from CRYSTALS-Kyber) for key establishment and ML-DSA (FIPS 204, from CRYSTALS-Dilithium) and SLH-DSA (FIPS 205, from SPHINCS+) for signatures. "Harvest now, decrypt later" is the reason for migrating key establishment first: Shor's algorithm breaks RSA, ECDSA and EdDSA alike, symmetric cryptography only loses half its security margin.