Re: 2047 bit keys in PGP

[Cedric Tefft <CedricT@datastorm.com>]

> 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