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'.