The RSA factoring challenges were set up to address these questions.
Last year RSA-230 was factored, and this week RSA-240 was factored.
This is a 240 digit (795 bit) number, the product of two primes.
Researchers solved two related problems at the same time, factoring RSA-240 and solving a discrete logarithm problem.
Together these problems took about 4,000 core-years to solve.
It’s not clear from the announcement how long it would have taken just to factor RSA-240 alone.
If you were to rent the computing power used, I imagine the cost would be somewhere in the six figures.
This makes 2048-bit and 3072-bit RSA keys look very conservative.
However, the weakest link in RSA encryption is implementation flaws, not the ability to factor big numbers.
Assume for a moment that breaking RSA encryption requires factoring keys.
(This may not be true in theory or in practice.
) How long would it take to factor a 2048 or 3072 bit key?.The time required to factor a number n using the number field sieve is proportional to Here o(1) roughly means terms that go away as n gets larger.
(More on the notation here.
) For simplicity we’ll assume we can ignore these terms.
This suggests that factoring a 2048-bit key is 12 orders of magnitude harder than factoring RSA-240, and that factoring a 3072-bit key is 18 orders of magnitude harder.
However, I don’t think anyone believes that breaking RSA with 2048-bit keys would require a quadrillion core-years.
If the NSA believed this, they wouldn’t be recommending that everyone move to 3072-bit keys.
Why such a large discrepancy?.Here are a few reasons.
As mentioned above, RSA encryption often has exploitable implementation flaws.
And even if implemented perfectly, there is no proof that breaking RSA encryption is as hard as factoring.
And there could be breakthroughs in factoring algorithms.
And large-scale quantum computers may become practical, in which case factoring would become much easier.
.