mgream@acacia.itd.uts.edu.au (Matthew Gream) writes:

"ER CRAMER" wrote:

...

But what are we talking about here. A 1024 bits key should be save for at least the next 10000 years so who cares if a 5000 bits key could be save for maybe a 1000000 years!!!

After the RSA-129 factoring there was considerable discussion on sci.crypt about how much harder a 1024 bit key would be using current algorithms. There was some disagreement, but it did not seem that a 1024 bit key would be good for 10000 years; as I recall, the time scale was more like a few decades before it would fall to an attack as expensive as RSA-129. Larger keys with 2K bits, OTOH, were good for thousands or millions of years (of course it's hard to extrapolate computer power out that far). Does anyone have more precise numbers?

And if a near polynomial time method is developed for factoring or breaking RSA (or any other PKCS you care to mention), super large keys aren't going to matter a hoot.

People have been talking as though the only possible improvements to factoring algorithms would be to jump to polynomial or near-polynomial time. Obviously it is equally possible that improvements will occur as they have in the past, reductions to the exponents or constant factors but still an exponential algorithm. In such a scenario it is very plausible that 1K bit keys would be unsafe while keys of a few K would be fine. Hal