From: jamesd@echeque.com
Date: Sat, 2 Mar 1996 17:32:12 +0800
To: perry@piermont.com
Subject: Re: Problems with certificates.
Message-ID: <199603020912.BAA28408@dns1.noc.best.net>
MIME-Version: 1.0
Content-Type: text/plain




jamesd@echeque.com writes:
>> If if we colonized every planet in the galaxy, and every planet had a 
>> trillion people, and every single person on every planet generated a billion 
>> keys a second for a billion billion years, not one pair would match, assuming
>> they were generated from truly random seeds.

At 03:19 AM 3/2/96 -0500, Perry E. Metzger wrote:
>Well, lets see. For a 1024 bit key, a birthday match is a 1 in 2^512
>proposition, assuming that a key could be any random 1024 bit number.
>Assuming 100 million planets:
>
>100000000*(10^12)*(10^9)*60*60*24*365*(10^9)*(10^9)=
>    3153600000000000000000000000000000000000000000000000000
>2^512=
>   134078079299425970995740249982058461274793658205923933777235614437217\
>   640300735469768018742981669034276900318581864860508537538828119465699\
>   46433649006084096
>
>However, the density of prime numbers isn't so high as to make the
>probability truly 1/2^512 -- indeed, I would guess it is much
>lower. However, you may indeed be right.

The number of prime numbers less than n is n/ln(n).  Presumably the number
of valid PGP keys is somewhat larger.

Assume 768 bit PGP keys: 

The number of randomly selected 768 bit primes that you would need for a
reasonable chance of a birthday collision is 1.708E104

Which is 

170 800 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 

A number substantially larger than 
3 153 600 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000

 ---------------------------------------------------------------------
              				|  
We have the right to defend ourselves	|   http://www.jim.com/jamesd/
and our property, because of the kind	|  
of animals that we are. True law	|   James A. Donald
derives from this right, not from the	|  
arbitrary power of the state.		|   jamesd@echeque.com