5

If you combined every microprocessor on earth into one humongous computational cluster, how large RSA-keys could you factor in reasonable time (lets say a few years)?

I know from reading the answers to this question that the next real life goal is 1024 bit, but I'm more interesting in purely theoretical answers here.

monoceres
  • 231
  • 1
  • 2
  • 6

1 Answers1

5

The current record for RSA-breaking is 768 bits. The only known algorithm which is sufficiently efficient for these key sizes to be envisioned at all is the General Number Field Sieve. This algorithm consists in two big parts, the sieving and then some heavy linear algebra.

When GNFS was first used to crack a 512-bit RSA key, the sieving was the bottleneck; it requires lots of machines with amounts of RAM which were non-trivial at that time. However, for bigger keys, it is the linear algebra which becomes the bottleneck, because it is not easy to parallelize, and requires one really big computer with a lot (a lot) of fast (very fast) RAM.

With all the computers on Earth, you could do the sieving for a 1024-bit factorization effort; all it takes is some thousands of computers with a few dozen gigabytes of RAM each. However, for the corresponding linear algebra, all these computers would amount to nothing. Instead, you have to build a new, special purpose computer with a new architecture.

For instance, consider the biggest supercomputers in existence. They are all accumulation of many microprocessors -- they are CPU-oriented supercomputers, very good at number-crunching on tasks which can be made adequately parallel (many computations per data transfer unit). For the second half of GNFS, you need a RAM-oriented supercomputer, better at data transfers between CPU than actual computations. The theoretical architecture for such a computer has been studied, and we have some good reasons to believe that it is technologically feasible, but it would still be a very substantial effort, beginning right at the chip foundry step.

Summary: even with a botnet controlling all of Earth's computers, you would not crack a 1024-bit RSA key. With all of Apple's cash, you could probably build a special-purpose machine which can crack a 1024-bit RSA key (but good luck with doing that discreetly: you cannot spend billions of dollars without showing up, at least, on economic statistics). For bigger keys (e.g. 1536 bits or more): don't even think about it.

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • 1
    The general assessment I heard is that the NSA probably would be able to build a supercomputer to crack RSA 1024. But that they probably won't actually do it for now, since there are more useful ways (such as building a huge datastore together with datamining) to spend their money. – CodesInChaos Apr 25 '13 at 12:44