From: "Perry E. Metzger" <perry@piermont.com>
Date: Sat, 2 Mar 1996 16:47:18 +0800
To: jamesd@echeque.com
Subject: Re: Problems with certificates.
In-Reply-To: <199603020757.XAA18751@dns1.noc.best.net>
Message-ID: <199603020819.DAA24292@jekyll.piermont.com>
MIME-Version: 1.0
Content-Type: text/plain



jamesd@echeque.com writes:
> At 08:35 AM 3/1/96 -0500, A. Padgett Peterson P.E. Information Security wrote
:
> >Today, each person generates their own PGP key. While it is unlikely that
> >any two will match, it is likely that at some point some two will match
> >(see matching birthdays in a bar - number is less than you would think).
> 
> 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.

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.

None the less, one would hope that the software handled it gracefully
even if the impossible happened...

Perry