Re: Comments on NSA (was: "Pyrrhus Cracks RSA?")

Well, doesn't it make some sense given the utility of prime numbers in
cryptography, that the NSA, or anyone else interested in breaking codes for that
matter, would have simply dedicated a computer or two to the long-term project
of determining all of the prime numbers under x bits long?  Granted this would
take a while, but the NSA has the time, the computers, and the other resources
necessary to do this.  Having all of these prime numbers would greatly reduce
the effort necessary to crack PGP/RSA-type cryptosystems which rely on prime
numbers.  It would reduce the number of factors a brute-force attack would
have to check dramatically.  Or am I completely off-base?


					Mephisto
-------------------------------------------------------------------------
To find out more about the anon service, send mail to help@anon.penet.fi.
Due to the double-blind, any mail replies to this message will be anonymized,
and an anonymous id will be allocated automatically. You have been warned.
Please report any problems, inappropriate use etc. to admin@anon.penet.fi.

> 
> Well, doesn't it make some sense given the utility of prime numbers in
> cryptography, that the NSA, or anyone else interested in breaking codes for that
> matter, would have simply dedicated a computer or two to the long-term project
> of determining all of the prime numbers under x bits long?  Granted this would
> take a while, but the NSA has the time, the computers, and the other resources
> necessary to do this.  Having all of these prime numbers would greatly reduce
> the effort necessary to crack PGP/RSA-type cryptosystems which rely on prime
> numbers.  It would reduce the number of factors a brute-force attack would
> have to check dramatically.  Or am I completely off-base?
> 
> 
> 					Mephisto

Quoting from the FAQ (Bruce Schneier's "Applied Cryptography") pp. 213:

   1. If everyone needs prime numbers, won't we run out? No, Santa would
      never run out of prime numbers for all the good little boys and 
      girls. In fact, there are over 10^150 primes of length 512 bits or
      less. (For numbers of size N, the probability that a random number
      is prime is one in log N.) There are only 10^84 atoms in the universe.
      [...]

Go directly to your bookstore, do not pass GO, do not collect $200 (you
only need about $50, including tax) and buy this book.

-- 
----------------                                             /\ 
Douglas Barnes            cman@illuminati.io.com            /  \ 
Chief Wizard         (512) 447-8950 (d), 447-7866 (v)      / () \
Illuminati Online          metaverse.io.com 7777          /______\

re:  generating all primes less than 2^x

>Granted this would
>take a while, but the NSA has the time, the computers, and the other resources
>necessary to do this.  

The basic fact of number theory here is the prime number theorem,
which says that (for the purposes of this problem) the number of
primes less than N approaches N/ln N.  For N=2^192 (say, for cracking
384 bit PGP keys), that number is 2^192/133, which is about 2^185.
The number of bits necessary to store all of these primes is even
larger.  A gigabyte is only 2^38 bits.

In plainer language, there's just too many to store.  This same
calculation also explains why there will never be a shortage of
primes.

Eric