RSA Cryptanalysis: Factoring and Future Threats
What you'll learn: How attackers might break RSA encryption now and in the future, and what timeline we're facing for quantum threats.
The Core Weakness: Factoring Large Numbers
RSA's security depends entirely on one hard mathematical problem: factoring the product of two large prime numbers back into those primes. Remember from lesson 141—RSA starts by picking two secret primes p and q, then publishes their product n = p × q. If an attacker can factor n back into p and q, they can reconstruct your private key and decrypt everything.
Think of it like mixing two paint colors together. It's easy to mix red and blue to get purple, but extremely hard to separate purple back into exactly the original red and blue. Factoring is that "unmixing" problem—but only temporarily hard.
Current Factoring Algorithms
Classical computers use algorithms like the General Number Field Sieve (GNFS) to factor numbers. These methods work, but take impractically long for RSA keys of 2048 bits or larger. This is why we confidently use RSA today—factoring a 2048-bit number would take thousands of years with current technology.
However, Moore's Law and algorithmic improvements mean we must continually increase key sizes. What's secure today won't be forever.
The Quantum Threat: Shor's Algorithm
In 1994, mathematician Peter Shor discovered an algorithm that lets quantum computers factor large numbers exponentially faster than classical computers. A sufficiently powerful quantum computer running Shor's algorithm could break RSA 2048 in hours or days, not millennia.
Current timeline: Experts estimate 10-30 years before quantum computers powerful enough to break RSA exist. This sounds distant, but data encrypted today could be harvested and decrypted later—a "store now, decrypt later" attack.
Key Takeaway: RSA's security relies on factoring being hard; classical factoring improves slowly, but quantum computers with Shor's algorithm will eventually break RSA entirely, driving the urgent need for post-quantum cryptography.