« Steelcape and Firewall Traversing VPNs | Main | ECRYPT slides »

May 21, 2007

1020 bits and counting

As is widely known, the RSA cryptosystem is based on the problem of factoring large numbers which are the product of two large primes. So, whenever progress is made in factoring, that gives us some information about how secure RSA is against brute-force attacks. There are two kinds of relevant benchmarks here:

The latter are substantially harder to factor.

On March 6, a team factored a 307 digit (1020 bit) special number using three large clusters. Wall clock time was 11 months. The largest non-special number ever factored was RSA 640 (640 bits), factored in 2005, at a cost of 20 2.2 GHz Opteron years. For comparison, 1024 bits is sort of the standard size for RSA keys (though most paranoid security types recommend larger keys). Given the gap between general and special numbers, we're likely still a ways off from the point where it's practical for an attacker to go after a single person's RSA key, even at 1024 bits.

Posted by ekr at May 21, 2007 2:20 PM | Filed under:

Comments

I think you're right about the economics of attacking an individual's keys, but high value keys such as keys used in the financial industry for signatures might be valuable enough to go after.


My advice right now is for people to move high value keys to longer lengths, and to move low value keys to longer lengths when it is convenient and if the application will not have its performance significantly degraded.


In other words, it is reasonable to lengthen keys, but unreasonable to think it is an imminent threat for low value targets. Attacks only get better with time, though, so if upgrading is cheap and easy, one might as well upgrade. If upgrading is expensive or difficult and there is little to be gained by attacking you in particular, there is no urgency.

Posted by: Perry E. Metzger at May 21, 2007 6:13 PM

The actual math of what they did is here.

Posted by: Paul Hoffman at May 22, 2007 3:37 PM