The Math Behind RSA #4: Breaking RSA and the Rise of Elliptic Curve Cryptography

This article has a more math-focused version with formal proofs on Folio . In the previous three parts, we built RSA from the ground up: modular arithmetic, Euler's theorem, and a working Python implementation. Now we tear it all down. This final article explores why RSA is showing its age, how elliptic curve cryptography (ECC) offers a compelling alternative, and what the quantum future holds. Part I: Attacks on RSA The Factoring Arms Race RSA's security rests on a single assumption: factoring the product of two large primes is computationally hard. But "hard" is a moving target. Trial Division — The naive approach tests every integer up to n\sqrt{n} n ​ . For a 2048-bit modulus, that means checking roughly 210242^{1024} 2 1024 candidates. Completely infeasible. Fermat's Factorization — If pp p and qq q are close together, we can write n=a2−b2=(a+b)(a−b)n = a^2 - b^2 = (a+b)(a-b) n = a 2 − b 2 = ( a + b ) ( a − b ) and search for aa a near n\sqrt{n} n ​ . This is why good RSA implemen