Schneier on Security

How well do these kinds of results scale? If an 80-Opteron cluster can do this kind of thing in five months, can something the power of Blue Gene/L do this kind of factoring in a few hours or even minutes? If so, how does this play into the abilities of large entities to break more common encryption routines?

@Jarrod

No, at this point it does not scale like that. Its still a hard problem. In other words, Blue Gene would struggle to factor a number much larger in any reasonable time frame.

So doubling the time is takes to sign with RSA, will make factoring *much* harder than double. The trick is that you want signatures to be safe for 20 years. Which means on todays computers you do have to wait a miniute or two for a signature.

The weak link in signing is currently the hash. You can sign with a 4096-bit RSA key, but if you're using something like SHA-1 for the hashing process, you can't count on two decades of security. I'm not sure we even have a hash function right now we could count on to provide 20 years of security.

@ denis bider

Yes you are totaly correct. There are hash schemes based on fatoring with proofs, i belive. But they really are slow. Real slow, and so no signing schemes uses them as the hash.

I was using this as a example for hard problem of Factoring.

There is now a fast hash based upon factoring, known as VSH. Do a web search.

@greg

Wasn't Jarrod asking if something like Blue Gene could factor *the same* number in a shorter time?....not a larger number in an equivalent time.

Z

Regarding Blue Gene/L etc:
No you can't simply scale it. The problem is that the factoring is divided into two phases, only the first of which is primarily compute-bound (and consequently, goes about twice as fast if you have twice as many machines, or the same number with twice the clock rate, etc). The second part of the problem is memory and communication bound. This makes it difficult to make simple comparisons -- for one thing, so far as I know the memory capacity of the Opteron cluster hasn't yet been published, and it also depends on how much is cache vs. DRAM, etc.

Having said that, we can probably guesstimate that the first phase, which took 3 months on the 80 x 2.2GHz Opterons, would have taken the order of an hour and a half on the 280 Tfps Blue Gene/L.