Loading learning content...
RSA's security has been tested by decades of the world's best mathematicians and cryptographers. Since its publication in 1977, RSA has withstood continuous attack, and properly implemented RSA with adequate key sizes remains secure against all known classical attacks.
But security is not absolute—it's measured in computational effort, advances in algorithms, and emerging technologies. Understanding RSA's security strength requires examining:
This analysis is essential for making informed decisions about key sizes, system lifetimes, and cryptographic migration strategies.
By the end of this page, you will understand: why integer factorization is believed to be computationally hard, the history of factoring records and their implications, how to choose appropriate RSA key sizes, the real timeline for quantum threats, how RSA compares to elliptic curve cryptography, and how the cryptographic community is preparing for the post-quantum era.
RSA's security rests on a fundamental asymmetry in computational complexity: multiplication is easy, but factorization is hard.
The Factoring Problem (FACTOR):
Given a composite integer n = p × q (where p and q are large primes), find p and q.
The RSA Problem (RSA):
Given (n, e, c) where c = m^e mod n, find m.
These problems are related but not identical:
Is Factoring NP-Complete?
The integer factorization problem is:
This places factoring in a complexity "gray zone"—harder than P, but probably not as hard as NP-complete. This intermediate hardness is actually ideal for cryptography: hard enough for security, but with well-understood structure.
The security of RSA is based on a hardness assumption, not a proof. No one has proven that factoring is hard—we simply observe that despite centuries of effort by brilliant mathematicians, no efficient algorithm has been found. A breakthrough algorithm could theoretically appear tomorrow. This is why cryptographic agility—the ability to switch algorithms—is important.
Why Factoring Seems Hard
Several observations support the belief that factoring is computationally difficult:
Long History: Factoring has been studied since ancient Greece. Despite 2,000+ years of mathematical development, no efficient algorithm has emerged.
Best Algorithms Are Subexponential: The General Number Field Sieve (GNFS), the best known algorithm, has complexity:
O(exp((64/9)^(1/3) × (ln n)^(1/3) × (ln ln n)^(2/3)))
This is faster than exponential but much slower than polynomial—it's called L-notation: L_n[1/3, c].
No Qualitative Improvements Since 1990: GNFS was developed in the early 1990s. Despite massive computational advances, algorithmic progress has stalled.
Strong Motivation: Banks, governments, and tech companies all rely on factoring being hard. If an easy solution existed, there would be enormous incentive to find it.
Related Problems Remain Hard: Problems like the discrete logarithm (basis for DSA, Diffie-Hellman) share similar structure and difficulty, suggesting a fundamental barrier.
The history of factoring records provides concrete data for assessing RSA security and choosing key sizes. Each record represents the cutting edge of what is computationally feasible.
The RSA Factoring Challenge (1991-2007)
RSA Laboratories published a series of challenge numbers for researchers to factor, offering cash prizes. These challenges established benchmarks for RSA security:
The challenge was discontinued because increasing key sizes had made further records impractical with available resources.
| Number | Bits | Year | Method | Effort (core-years) |
|---|---|---|---|---|
| RSA-100 | 330 | 1991 | Quadratic Sieve | ~1 |
| RSA-129 | 426 | 1994 | Quadratic Sieve | ~5000 MIPS-years |
| RSA-130 | 430 | 1996 | GNFS | ~1000 |
| RSA-155 | 512 | 1999 | GNFS | ~8000 MIPS-years |
| RSA-640 | 640 | 2005 | GNFS | ~30 core-years |
| RSA-768 | 768 | 2009 | GNFS | ~2000 core-years |
| RSA-250 | 829 | 2020 | GNFS | ~2700 core-years |
| RSA-1024 | 1024 | — | — | Not yet factored |
| RSA-2048 | 2048 | — | — | Estimated 10^15 core-years |
What the Records Tell Us
512-bit RSA is broken: Factored in 1999, trivially factorable today. Never use 512-bit keys.
768-bit RSA is broken: Factored in 2009. Still takes significant resources but achievable by well-funded organizations.
1024-bit RSA is deprecated: Not yet publicly factored, but likely within reach of nation-state adversaries. NIST recommends discontinuing use by 2030.
2048-bit RSA is currently secure: Conservative estimates suggest 2048-bit factoring would require computational resources equivalent to ~10^15 core-years—far beyond any current capability.
Key size doubling ≠ double difficulty: Due to GNFS's sub-exponential complexity, doubling key size from 1024 to 2048 bits increases factoring difficulty by roughly 10^12 (a trillion times), not just 2x.
The Trend:
Factoring capability improves by roughly 10-15 bits per year due to:
This rate suggests 1024-bit factoring might become feasible around 2030-2035 for well-funded adversaries.
In 1977, the RSA inventors suggested that a 125-digit (415-bit) modulus would be secure for millions of years. It was factored in 1994. In 1999, 512-bit was still common in export-grade cryptography. Today we know 2048-bit is the minimum. The lesson: be conservative with key sizes, and plan for algorithm migration.
Understanding the best attacks against RSA helps us choose appropriate key sizes and understand the security margin.
The General Number Field Sieve (GNFS)
GNFS is the fastest known algorithm for factoring general integers larger than about 100 digits. It works in several phases:
GNFS Complexity:
L_n[1/3, (64/9)^(1/3)] ≈ L_n[1/3, 1.923]
In L-notation: L_n[α, c] = exp(c × (ln n)^α × (ln ln n)^(1-α))
For 1024-bit n: ~2^86 operations
For 2048-bit n: ~2^116 operations
For 3072-bit n: ~2^138 operations
| Key Size | GNFS Operations | Equivalent Symmetric Bits | Security Level |
|---|---|---|---|
| 512-bit | ~2^63 | ~63-bit | Completely broken |
| 768-bit | ~2^76 | ~76-bit | Broken (factored 2009) |
| 1024-bit | ~2^86 | ~86-bit | Deprecated (weak) |
| 2048-bit | ~2^116 | ~112-bit | Standard (secure) |
| 3072-bit | ~2^138 | ~128-bit | High security |
| 4096-bit | ~2^156 | ~140-bit | Maximum practical |
| 7680-bit | ~2^192 | ~192-bit | Theoretical only |
Other Attack Methods
Special Number Field Sieve (SNFS): Faster than GNFS for numbers with special forms (like Mersenne numbers). RSA moduli are not susceptible as they're products of random primes.
Pollard's p-1 Method: Fast if p-1 has only small prime factors. Mitigated by using "strong primes."
Pollard's Rho: Generic factoring method, O(n^(1/4)) complexity. Too slow for cryptographic-size numbers.
Elliptic Curve Method (ECM): Finds small factors efficiently. Useful as a pre-filter before GNFS. If factors are balanced (similar size), ECM doesn't help.
Lattice Attacks (Coppersmith): Can recover plaintexts or factors under specific conditions (small exponents, partial key exposure). Mitigated by proper padding and key management.
Direct RSA Problem Attacks: No attack on the RSA problem (finding m from c = m^e mod n) is known that doesn't effectively factor n.
A system is only as strong as its weakest link. If you're using AES-256 (256-bit security), pairing it with 2048-bit RSA (112-bit equivalent) creates an imbalance. For balanced security: AES-128 pairs with RSA-3072 (~128-bit), AES-256 pairs with RSA-15360 (~256-bit equivalent, impractical). This is why ECC is preferred for high security levels—ECC-521 provides ~256-bit security with practical key sizes.
Quantum computers pose an existential threat to RSA. In 1994, Peter Shor discovered a quantum algorithm that factors integers in polynomial time, reducing what would take billions of years on classical computers to hours or minutes on a sufficiently powerful quantum computer.
Shor's Algorithm Complexity:
O((log n)^2 × (log log n) × (log log log n))
This is polynomial in the number of bits—qualitatively different from the sub-exponential GNFS. A 2048-bit RSA modulus that would take 10^15 years to factor classically could be factored in hours with a large enough quantum computer.
Current State of Quantum Computing (2024-2025):
Timeline Estimates:
Researchers estimate a cryptographically relevant quantum computer (CRQC) capable of breaking 2048-bit RSA might emerge:
The uncertainty is enormous. Quantum computing could advance rapidly, or hit insurmountable engineering barriers.
The "Harvest Now, Decrypt Later" Threat
Even though quantum computers can't break RSA today, adversaries may be recording encrypted traffic now, planning to decrypt it when quantum computers become available. For secrets that must remain confidential for decades (medical records, state secrets, long-term business strategies), the quantum threat is already relevant.
This motivates the current push toward post-quantum cryptography, even before quantum computers are cryptographically capable.
Unlike classical computing where security degrades gradually (1024-bit becomes weak, then 768-bit, then 512-bit...), quantum computing creates a cliff. Once a quantum computer can run Shor's algorithm at scale, ALL RSA key sizes become equally broken overnight. There is no "post-quantum RSA"—the algorithm itself must be replaced.
Choosing the right RSA key size depends on: the required security level, the expected lifetime of the system, performance constraints, and compliance requirements.
NIST Recommendations (SP 800-57, 2020):
NIST defines security levels based on "bits of security"—the work factor to break the system:
| Security Level | Bits | RSA Equivalent | Status |
|---|---|---|---|
| Legacy | 80 | 1024 | Disallowed after 2013 |
| Standard | 112 | 2048 | Current minimum |
| High | 128 | 3072 | Recommended for most uses |
| Maximum | 192 | 7680 | Impractical (use ECC instead) |
| Ultra | 256 | 15360 | Theoretical only |
For RSA specifically, NIST recommends:
| Use Case | Recommended Key Size | Rationale |
|---|---|---|
| Short-term TLS certificates (1-2 years) | 2048-bit | Adequate for certificate lifetime |
| Long-term CA certificates (10+ years) | 4096-bit | Must remain secure for decades |
| Code signing (long-lived software) | 4096-bit | Software may be in use for decades |
| SSH server keys | 3072-bit or higher | Servers often run for many years |
| New system design (2025+) | 3072-bit minimum | Plan for 10-15 year system lifetime |
| High-security environments | 4096-bit + PQC hybrid | Belt and suspenders approach |
| Post-quantum preparation | N/A | Transition to CRYSTALS-Kyber, Dilithium |
Performance Trade-offs
Larger keys are slower. RSA performance scales roughly with the cube of key size:
| Key Size | Key Gen Time | Signature Time | Verification Time |
|---|---|---|---|
| 2048-bit | ~100ms | ~2ms | ~0.1ms |
| 3072-bit | ~400ms | ~5ms | ~0.2ms |
| 4096-bit | ~1s | ~10ms | ~0.4ms |
(Approximate times on a modern CPU; actual performance varies)
For high-performance applications, consider:
Compliance Requirements:
For new systems in 2025+: Use 3072-bit RSA as the minimum, or preferably switch to ECDSA (P-384 or Ed25519) for signatures and ECDHE for key exchange. Begin planning your post-quantum migration now—hybrid schemes (classical + PQC) are available for testing.
Recognizing the quantum threat, the cryptographic community has been developing post-quantum cryptography (PQC)—algorithms believed to resist both classical and quantum attacks. In 2024, NIST completed a multi-year competition and standardized the first post-quantum algorithms.
NIST Post-Quantum Standards (2024):
Key Encapsulation (replacing RSA key exchange):
Digital Signatures (replacing RSA signatures):
These algorithms are based on mathematical problems believed to resist quantum attacks:
| Property | RSA-2048 | ML-KEM-768 (Kyber) | ML-DSA-65 (Dilithium) |
|---|---|---|---|
| Type | Key exchange & signatures | Key encapsulation only | Signatures only |
| Public key size | 256 bytes | 1,184 bytes | 1,952 bytes |
| Private key size | ~1KB (with CRT) | 2,400 bytes | 4,000 bytes |
| Ciphertext/signature | 256 bytes | 1,088 bytes | 3,293 bytes |
| Key gen speed | Slow (~100ms) | Fast (~0.015ms) | Fast (~0.1ms) |
| Encrypt/sign speed | Fast (~0.1ms) | Fast (~0.02ms) | Fast (~0.3ms) |
| Decrypt/verify speed | Slow (~2ms) | Fast (~0.02ms) | Fast (~0.3ms) |
| Quantum resistant | ❌ No | ✓ Yes | ✓ Yes |
The Transition Timeline
2024-2027: Early adoption begins
2025-2030: Industry adoption
2030-2035: Classical deprecation begins
2035-2040+: Full transition
Hybrid Approach:
During the transition, systems may use hybrid cryptography—combining a classical algorithm (RSA, ECDH) with a post-quantum algorithm (Kyber). If either one is secure, the combination is secure. This protects against:
Elliptic Curve Cryptography (ECC), developed in the 1980s, offers the same security as RSA with much smaller keys. Understanding the comparison helps in choosing the right algorithm for your use case.
Security Equivalence:
| ECC Key Size | RSA Equivalent | Security Level |
|---|---|---|
| 160-bit | 1024-bit | 80-bit (deprecated) |
| 224-bit | 2048-bit | 112-bit |
| 256-bit | 3072-bit | 128-bit |
| 384-bit | 7680-bit | 192-bit |
| 521-bit | 15360-bit | 256-bit |
ECC achieves equivalent security with 10-15x smaller keys.
Why ECC is More Efficient:
RSA security grows logarithmically with key size—you need exponentially larger keys for linear security increases. ECC security grows linearly—doubling key size approximately doubles security.
This stems from the underlying math:
ECC has a "tighter" security/key-size relationship.
When to Use RSA:
When to Use ECC (ECDSA, EdDSA, ECDH):
In Practice:
Most modern systems support both. TLS 1.3 supports ECDHE (ECC-based key exchange) and either RSA or ECDSA signatures. The trend is clearly toward ECC:
Neither RSA nor ECC provides quantum resistance. Shor's algorithm breaks both equally (though ECC requires fewer qubits to break). The post-quantum transition affects both—choosing RSA over ECC for "quantum safety" is not a valid strategy. Choose based on current performance and compatibility needs.
We've comprehensively analyzed RSA's security strength—from the fundamental hardness assumptions through quantum threats to practical key size decisions. This knowledge enables informed decisions about cryptographic system design.
Module Complete:
You have now completed the comprehensive study of the RSA algorithm. You understand:
This knowledge forms an essential foundation for understanding modern network security, from TLS connections to digital certificates to secure messaging systems.
Congratulations! You have mastered the RSA algorithm—one of the most important cryptographic systems in computing history. You understand not just how RSA works, but why it works, when it's secure, and how to use it properly. This knowledge will serve you well in any role involving network security, cryptographic systems, or secure software development.