Home page logo

fulldisclosure logo Full Disclosure mailing list archives

Re: Crypto and Primes
From: Andrew <notes () shaw ca>
Date: Sat, 23 Oct 2004 11:25:16 -0700

And .. where would you get all of those primes? My rough estimate says that even if every person on the planet (6,000,000,000) turned on their PC capable of generating random 512 bit primes at the rate of 100 trillion (100,000,000,000,000) primes per second it would still take way more than 1e100 TIMES the age of the universe(!) to even bring the chances of getting a particular 512 bit prime to the odds of 1 in a billion.

Age of the universe given as 18 billion years, which is rounded up to the highest billion years from the oldest estimate, found at: http://www.astro.ucla.edu/~wright/age.html ymmv.

Reality parody. Not to be taken seriously.
Professional driver on a closed course.
Do not try this at home.

 - A

At 07:33 PM 10/22/2004, Jeremy Bishop wrote:
On Friday 22 October 2004 14:31, Daniel Sichel wrote:

> Depending on how rigourous you are being, the large in large numbers
> is a relative term. I know from talking to someone who has worked in
> for real government crypto that there is enough storage space to
> create a lookup db of a good chunk (if not all) of the PGP crypto
> keys in use for common key sizes (512 and 1024). I doubt SSL is less
> vulnerable. I guess there's force, brute force, and brute force with
> taxpayer dollars.

If you are speaking of a database in which you could look up different
keys, of course it's possible.  I suggest http://pgp.mit.edu/ for an
example of such a system.

If you are thinking of the primes involved in these keys, I would like
to direct your attention to this quote:

RSA is typically performed using 512bit prime numbers. There are
approximately 3.778e151 such prime numbers. Using the advanced storage
technology available to the NSA, it should be possible to store a 512
bit number in a single hydrogen atom. A typical universe (e.g. ours)
contains approximately 1e90 hydrogen atoms. If the NSA has hidden
3.778e61 universes in an inconspicious little building in Maryland,
astronomers should notice some deviations in the gravity field in the

(HansM; http://web.ukonline.co.uk/eric.price/humour/hum0110.htm)

A more interesting question might be, in this case, how would a
government know which of those primes have been used.  This information
would be feasible to store, but would require compromising just about
every random number generator in use by the crypto-fanatics who make
use of PGP.

> Also with cheapo Linux clusters I would think a determined
> hackmeister could do a crack on large prime based crypto, whether
> that would be computationally feasible in a relevant time frame, I
> don't know. I do know my gut  tells me SSL is cryptographically weak
> and I refuse to use it in place of IPSEC.

In that case, I assume you are using IPSEC with shared secrets instead
of certificates, no?

The universe does not have laws -- it has habits, and habits can
be broken.
                        -- BSD fortune file

Full-Disclosure - We believe in it.
Charter: http://lists.netsys.com/full-disclosure-charter.html

  By Date           By Thread  

Current thread:
[ Nmap | Sec Tools | Mailing Lists | Site News | About/Contact | Advertising | Privacy ]