From: hfinney@shell.portal.com
Date: Fri, 24 Jun 94 10:00:53 PDT
To: cypherpunks@toad.com
Subject: Re: WARNING!
Message-ID: <199406241702.KAA19766@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


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