Asymmetric Key sizes

[Paul Leyland]

>>...
>>It has been possible to break 512 bit keys for several years....
>>...  As for 768-bit keys, they would appear to be resistant to any
>reasonable attack with any reasonable amount of hardware.
>...
>
> I didn't get a clear feeling for what the prudent target should be. Paul
> says (above) that 768-bit keys should be OK now against "reasonable"
> attack. Does this mean the worst realistic case that we can think of for
> the present, and into the "foreseeable" future - a few years? How much 
> more prudent would 1024 bits be? What about putting things the other way
> round?  What's the problem with everyone going for 2048 now and
> (presumably) putting things so far out of reach that attackers
> just give up?

The image I like to propagate is that breaking a 512-bit key today would
take an effort commeasurate with the RSA-129 project.  Breaking a 768-bit
key would take an investment comparable to the Apollo project.  The former
is feasible but not trivial; the latter is possible but not feasible.

If forced to guess, I'd say that a 512-bit factorization will be
demonstrated this year or next, but a 768-bit factorization won't happen in
the next decade.  I'm pretty sure of the first prediction, but somewhat
doubtful about the second.  If I am seriously wrong, I'm in very good
company --- even I won't stick my neck out as far as predicting 40
quadrillion years!  Unless something wonderful happens, a 1024-bit
factorization won't be seen for several decades.

"And the number of the bits shall be 1024.  512 shallt thou not use, neither
shallt thou use 768, excepting that thou shallt go on to 1024.  2048 is
right out!"

Or something like that.


Paul