Re: 2047 bit keys in PGP

> 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

From: Cedric Tefft <CedricT@datastorm.com>
    Date: Thu, 04 Jan 96 14:12:00 PST

    >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?

Factoring a 384-bit number is not equivalent to searching a 384-bit
keyspace.  Consider that there are 78498 primes less than 1000000.
This means that you can do a brute force search of a keyspace of under
17-bits to find a prime factor of any composite number less than
1000000000000 -- a bit under 40 bits.  I've done this to verify the
results of an implementation of the Rabin-Miller primality test on
relatively small numbers.  I'm not sure how many primes there are with
192 or fewer bits, but it's far fewer than 2^384.

There are better techniques around for factoring large numbers than
this sort of brute force testing.  While I didn't follow the thread
very closely, they probably used the quadratic sieve or number field
sieve algorithm.  See Schneier's _Applied_Cryptography_ for more on
factoring, including references to more detailed works.

--
Rick Busdiecker                        Please do not send electronic junk mail!
 net: rfb@lehman.com or rfb@cmu.edu    PGP Public Key: 0xDBD9994D
 www: http://www.cs.cmu.edu/afs/cs.cmu.edu/user/rfb/http/home.html
 send mail, subject "send index" for mailbot info, "send pgp key" gets my key
A `hacker' is one who writes code.  Breaking into systems is `cracking'.