1020 bits and counting

| Comments (2) |
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:
  • Special numbers which are (relatively) easy to factor.
  • Actual RSA moduli formed by multiplying two large primes.

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.

2 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.

The actual math of what they did is here.

Leave a comment