[46523] in Cypherpunks
Re: 2047 bit keys in PGP
daemon@ATHENA.MIT.EDU (Rick Busdiecker)
Thu Jan 4 23:53:20 1996
Reply-To: Rick Busdiecker <rfb@lehman.com>
From: Rick Busdiecker <rfb@lehman.com>
To: Cedric Tefft <CedricT@datastorm.com>
Cc: cypherpunks@toad.com
In-Reply-To: Your message of "Thu, 04 Jan 1996 14:12:00 PST."
<30EC5109@ms-mail.datastorm.com>
Date: Thu, 04 Jan 1996 23:42:35 -0500
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'.
