From: owner-cypherpunks To: cypherpunks Subject: Re: 2047 bit keys in PGP Date: Thursday, January 04, 1996 11:29AM
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.
[snip] No law says the attack has to be brute force. What about the birthday attack, differential cryptanalysis, etc? True, I believe neither of those examples are applicable to RSA, but factoring is, and it's _much_ more efficient than brute force searches. There might be other algorithems out there (or as yet undiscovered) that are more efficient than current factoring algorithms are (or ever hope to be). If your attacker has an algorithm whereby he has to search less than the full keyspace, he has effectively reduced the size of your key. Essentially, his attack is the same order of magnitude as a brute force search of this new reduced keyspace (call it "effective" keyspace for convenience). The greater difference between the effective keyspace and the real keyspace (determined by his cracking algorithm), the larger I need to make my real key to compensate. If his algorithm effectively cuts my keyspace in half, I need to make it twice as large as I would need if my attacker's best algorithm were brute force.
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."
Hmmm... Well, the 384-bit Blacknet PGP key was cracked in just a few months. How? Certainly parallelism helped, but the main reason is that they were factoring keys rather than searching the full keyspace by brute force. I don't know about you, but I'm certainly not going to stop increasing the size of my key simply because it can't be cracked by brute force. - Cedric