Engineering/Mathematics/Applied cryptography

The RSA Cryptosystem

RSA is three lines of number theory and forty years of implementation lessons. The mathematics has never been broken; almost every practical failure has come from padding, parameter choice, fault handling or the random number generator.

Application
Computing
Widely deployed
≈17 min read
Synthesis of the library

ed ≡ 1Key equationModulo λ(n). Everything else follows from Euler's theorem.

3072 bitsCurrent guidanceFor long-term confidentiality, roughly equivalent to a 128-bit symmetric key.

×4CRT speed-upThe private operation via the Chinese remainder theorem, with mandatory result verification.

NeverTextbook RSADeterministic, malleable and multiplicative. Padding is not optional — it is part of the scheme.

Executive summary

RSA takes a modulus n = pq and a public exponent e coprime to λ(n) = lcm(p−1, q−1). The private exponent is d ≡ e⁻¹ (mod λ(n)). Encryption raises to the power e, decryption to the power d, and Euler's theorem makes the two inverse.

This page assembles most of the library. Prime generation supplies p and q; the extended Euclidean algorithm produces d; Chinese remaindering accelerates the private operation; and the security argument rests on the difficulty of factoring, bounded by the number field sieve.

Setupn = pq, e, d

Two random primes, a public exponent, and its inverse modulo λ(n).

Operationsx ↦ x^e, x ↦ x^d

Modular exponentiation; the private direction uses CRT for a fourfold speed-up.

CorrectnessEuler's theorem

ed ≡ 1 (mod λ(n)) makes the two maps inverse on all of ℤ_n.

SecurityFactoring assumption

Recovering d from (n,e) is equivalent to factoring n; the raw problem is only conjecturally equivalent.

Contents

Key generation and operations

Generate two primes
Random p and q of half the modulus bit length, with the top two bits set so that n has exactly the nominal size. They must be independently generated from a well-seeded cryptographic source.
Check the separation condition
|p − q| must not be small, or Fermat factorization succeeds instantly. Independently generated primes satisfy this with overwhelming probability, but the check is cheap.
Form the modulus and compute λ(n)
n = pq and λ(n) = lcm(p−1, q−1).
Choose the public exponent
e = 65537 is standard: prime, only two bits set, so encryption and verification cost 17 squarings and one multiplication.
Compute the private exponent
d ≡ e⁻¹ (mod λ(n)) by the extended Euclidean algorithm. It exists exactly when gcd(e, λ(n)) = 1; otherwise regenerate a prime.
Precompute CRT parameters
d_p, d_q, q⁻¹ mod p for the accelerated private operation.
Destroy the intermediates
Zero p, q and λ(n) in any memory not intended to hold them.

Theorem T1

Correctness

For every x ∈ ℤ_n, x^ed ≡ x (mod n). Proof: ed = 1 + kλ(n), so for units the claim follows from x^λ(n) ≡ 1. For non-units, check modulo p and q separately — if p ∣ x both sides vanish modulo p, and Fermat's little theorem handles the other factor — then recombine by the Chinese remainder theorem.

Cost of the operations
Operation	Exponent	Cost at 2048 bits
Encrypt / verify	e = 65537	17 squarings, 1 multiplication — sub-millisecond
Decrypt / sign, direct	d, full size	≈ 3000 modular multiplications
Decrypt / sign, CRT	d_p, d_q, half size	≈ 4× faster than direct
Key generation	—	Dominated by prime search: hundreds of candidates

Contents

Why textbook RSA is unusable

The raw function is not an encryption scheme

Encrypting m as m^e mod n is deterministic, so identical plaintexts produce identical ciphertexts and a small message space can be searched exhaustively. It is also multiplicatively homomorphic: (m₁m₂)^e = m₁^em₂^e, which enables blinding attacks against both encryption and signatures. Padding is what turns the trapdoor permutation into a scheme.

Attacks on unpadded RSA
Attack	Condition	Effect
Dictionary attack	Small or guessable message space	Recover the plaintext by encrypting candidates
Multiplicative blinding	Chosen-ciphertext access	Obtain a signature or decryption of a chosen value
Håstad broadcast	Same small e, same message to e recipients	Recover the message by CRT and an integer e-th root
Franklin–Reiter and Coppersmith	Related messages under the same modulus	Recover both messages
Signature forgery	Multiplicative structure	Forge a signature on a product of previously signed values

None of these attacks the factoring problem; they exploit the algebraic structure that padding is designed to destroy.

Standardised padding
Scheme	Purpose	Status
PKCS #1 v1.5 encryption	Encryption	Legacy; vulnerable to Bleichenbacher-style oracle attacks unless implemented with extreme care
OAEP	Encryption	Recommended; provably secure in the random oracle model
PKCS #1 v1.5 signature	Signature	Still widely deployed; acceptable with strict verification
PSS	Signature	Recommended; randomised with a tight security proof

Bleichenbacher's 1998 attack against PKCS #1 v1.5 encryption keeps reappearing in new forms because implementations leak whether padding was well formed. Constant-time, error-indistinguishable handling is mandatory.

Contents

Parameter and implementation attacks

Known attacks and the conditions that enable them
Attack	Condition	Countermeasure
Wiener	d < n^1/4/3	Never choose a small private exponent; derive d from e
Boneh–Durfee	d < n^0.292	Same
Coppersmith partial key exposure	A quarter of the bits of p or d leak	Treat all private material as all-or-nothing
Fermat factorization	\|p−q\| small	Generate primes independently and check the separation
Pollard p−1	p−1 smooth	Random primes of modern size make this negligible
Shared factors across keys	Poor entropy at generation	Well-seeded cryptographic RNG; audit deployed moduli for common factors
Bellcore fault attack	A fault in one CRT half	Verify the signature before releasing it
Timing and power analysis	Secret-dependent execution	Constant-time exponentiation, blinding of base and exponent
Common modulus	One n with several exponent pairs	Never share a modulus between users

Entropy failures are the most common real-world break

Large-scale surveys of deployed TLS and SSH keys have repeatedly found moduli sharing a prime factor, because embedded devices generated keys at first boot before their entropy pools were seeded. Any two such moduli are factored by a single gcd. The mathematics was sound in every case; the sampling was not.

Never reuse a modulus. Any holder of one valid private exponent can factor the modulus, so a shared modulus offers no privacy between its users.
Blind the private operation. Compute (r^ec)^d·r⁻¹ for random r, which decorrelates timing and power traces from the actual ciphertext.
Validate on import. Reject moduli that are even, prime, perfect powers, or share small factors; reject public exponents that are 1 or even.

Contents

Key sizes and the alternatives

Comparable security levels
Symmetric strength	RSA modulus	Finite-field DH	Elliptic curve	Guidance
80 bits	1024 bits	1024 bits	160 bits	Deprecated
112 bits	2048 bits	2048 bits	224 bits	Acceptable near term
128 bits	3072 bits	3072 bits	256 bits	Current recommendation
192 bits	7680 bits	7680 bits	384 bits	High assurance
256 bits	15360 bits	15360 bits	512 bits	Rarely justified for RSA

Figures follow standard equivalence tables derived from extrapolating number field sieve and Pollard rho costs. Note how badly RSA scales: quadrupling the security level requires a fifteenfold larger modulus.

RSA remains competitive for verification. With e = 65537, signature verification is far cheaper than an elliptic curve verification, which is why RSA persists in certificate chains where verification vastly outnumbers signing.
Elliptic curves win on key size and on signing cost, which is why new deployments generally prefer them for key exchange and signatures.
Quantum computing changes the ranking entirely. Shor's algorithm breaks RSA, finite-field Diffie–Hellman and elliptic curves alike in polynomial time. Migration guidance now points to lattice- and hash-based schemes, with hybrid deployments during transition.

Contents

Quick reference and FAQ

The scheme in one table
Item	Value
Public key	(n, e)
Private key	(d, p, q, d_p, d_q, q⁻¹ mod p)
Key equation	ed ≡ 1 (mod λ(n)), λ(n) = lcm(p−1,q−1)
Encrypt	c = OAEP(m)^e mod n
Decrypt	m = OAEP⁻¹(c^d mod n), via CRT
Sign	s = PSS(m)^d mod n, verified before release
Verify	s^e mod n checked against the encoding
Standard exponent	e = 65537

Is breaking RSA provably as hard as factoring?

Recovering the private exponent is equivalent to factoring. Inverting the raw RSA function on a random ciphertext — the RSA problem — is not known to be equivalent; it could conceivably be easier. In practice the best known attack is to factor the modulus.

Why e = 65537 rather than 3?

e = 3 is valid with correct padding but leaves no margin against implementation mistakes such as the Håstad broadcast scenario and Bleichenbacher's signature forgery against sloppy verifiers. 65537 is still only 17 squarings and one multiplication, so the cost of the extra safety is negligible.

Do RSA primes need to be strong primes?

Older standards required p±1 to have large prime factors to resist Pollard's p−1 and Williams' p+1 methods. With random primes of at least 1024 bits, the probability that either applies is negligible, and current standards no longer mandate strong primes.

What should be done with existing 1024-bit RSA keys?

Treat them as end-of-life. They are not known to have been broken publicly, but they are within extrapolated reach of a well-resourced adversary and are already rejected by most modern policies. Migrate to 2048 bits at minimum, and to 3072 bits or elliptic curves for anything requiring long-term confidentiality.

Contents

References and further reading

R. L. Rivest, A. Shamir and L. Adleman, 'A method for obtaining digital signatures and public-key cryptosystems', Communications of the ACM 21 (1978) 120–126.
V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — §7.8 and Chapter 10.
D. Boneh, 'Twenty years of attacks on the RSA cryptosystem', Notices of the AMS 46 (1999) 203–213.
RFC 8017 (PKCS #1 v2.2), IETF, 2016 — OAEP and PSS specifications.
NIST SP 800-57 Part 1 Rev. 5, Recommendation for Key Management, 2020 — key size equivalences.

KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: rsa-cryptosystemReview cycle: annual

The RSA Cryptosystem

Executive summary

Key generation and operations

Generate two primes

Check the separation condition

Form the modulus and compute λ(n)

Choose the public exponent

Compute the private exponent

Precompute CRT parameters

Destroy the intermediates

Correctness

Why textbook RSA is unusable

Parameter and implementation attacks

Key sizes and the alternatives

Quick reference and FAQ

References and further reading

Continue learning

KEVOS Intelligence

Executive summary

Key generation and operations

Generate two primes

Check the separation condition

Form the modulus and compute λ(n)

Choose the public exponent

Compute the private exponent

Precompute CRT parameters

Destroy the intermediates

Correctness

Why textbook RSA is unusable

Parameter and implementation attacks

Key sizes and the alternatives

Quick reference and FAQ

Related pages in this library

References and further reading

Continue learning