Re: 2047 bit keys in PGP
I really don't see the point of using a key larger than 2048 bits. Any larger key would actually be harder to factor than brute forcing the IDEA keyspace. Very little security would be gained from using a key larger than 3000 bits. Of course, one can always argue that improved factoring methods would require that an RSA public key be longer than 3000 bits to have equal security to IDEA. However, I doubt that factoring methods will improve that much.
nobody will ever need more than 640K or RAM? i wouldn't underestimate the ability of technology to grow at a pace that is beyond our wildest dreams-especially with this network serving as a virtual office/lab. of course, ymmv. <><><><><><><><><><><><><><><><><><><><><><><><><><><><><> the Forest will always be there...and anybody who is Friendly with Bears can find it. - A. A. Milne
In article <v02130503ad119cbfdece@[205.231.67.43]>, netdog <netdog@dog.net> wrote:
nobody will ever need more than 640K or RAM? i wouldn't underestimate the ability of technology to grow at a pace that is beyond our wildest dreams-especially with this network serving as a virtual office/lab. of course, ymmv.
Order of magnitude check: There is a very well-defined limit to the size of key that can be broken by brute force, independent of your "wildest dreams" as to the growth of technology. It's the Laws of Thermodynamics. For a symmetric algorithm for which any value of the appropriate length n is a possibly valid (and equally likely) key, there are 2^n keys to try in a brute-force search. From Applied Crypto, 2nd ed, pp157-158, setting or clearing one bit takes at _least_ 4.4*10^-16 erg of energy. For symmetric keys of size 256, then, you would need more than 10^61 erg (that's 10^45 GJ) of energy just to _enumerate_ the states. For comparison, this about 10 billion times larger than the output of a typical supernova. (Ibid.)
From the same source:
"These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space." Thus this situation is quite different from the 640K of RAM scenario. It's more like "who would ever need more RAM than you could get by storing a bit on every subatomic particle in the universe". It's not a matter of what resources you can imagine using, but rather, what resources are in the universe, able to be used. - Ian "First post of the morning; it shows, doesn't it..."
Ian Goldberg wrote:
Order of magnitude check:
There is a very well-defined limit to the size of key that can be broken by brute force, independent of your "wildest dreams" as to the growth of technology. It's the Laws of Thermodynamics.
For a symmetric algorithm for which any value of the appropriate length n is a possibly valid (and equally likely) key, there are 2^n keys to try in a brute-force search. From Applied Crypto, 2nd ed, pp157-158, setting or clearing one bit takes at _least_ 4.4*10^-16 erg of energy. For symmetric keys of size 256, then, you would need more than 10^61 erg (that's 10^45 GJ) of energy just to _enumerate_ the states. For comparison, this about 10 billion times larger than the output of a typical supernova. (Ibid.)
Although your point is quite valid, there is always the possibility of some technological advance that invalidates these calculations. It is possible that quantum crypto will some day make brute forcing 256 bit keys practical. (Of course, my knowledge about quantum crypto couldn't fill a thimble, so maybe I'm wrong.) These results also apply only to symmetric key ciphers and have no relation to the difficulty of breaking RSA. The techniques for factoring large numbers have come a long way in the recent past and it would not be much of a surprise for them to take another large leap. All that being said, I believe that 128 bits is sufficient for a symmetric key and 2048 for a public key. Our paranoia would be far better directed at as yet unknown attacks on the algoritms involved or the specific implementations of cryptographic systems. Paul Kocher's recent timing attack is a perfect example of what we should be afraid of. -- Sure we spend a lot of money, but that doesn't mean | Tom Weinstein we *do* anything. -- Washington DC motto | tomw@netscape.com
participants (3)
-
iagoldbe＠csclub.uwaterloo.ca -
netdog＠dog.net -
Tom Weinstein