[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: dpkemp@missi.ncsc.mil (David P. Kemp)*Subject*: Re: comments on client auth*From*: Bill Sommerfeld <sommerfeld@apollo.hp.com>*Date*: Thu, 20 Jun 1996 15:49:57 -0400*Cc*: spki@c2.org*In-Reply-To*: dpkemp's message of Thu, 20 Jun 1996 12:23:58 -0400. <199606201623.MAA01542@argon.ncsc.mil>*Sender*: owner-spki@c2.org

Ok, let's see if I can remember my math and rederive that formula.. The chance of collision between 2 people selecting from N choices is... 1/N Assuming that the first two chose uniquely, the chance that the third person chose a unique value is 2/N combining the two, you get a probability of 1/N + (1-1/N)(2/N) adding a third, you get: 1/N + (1-1/N)(2/N) + (1-1/N)(1-2/N)(3/N) for K people, if N is much larger than K, you can treat the (1-i/N) terms as equal to 1 (this is a conservative estimate) which reduces to (1+2+3+...+(K-1))/N or (K)*(K-1)/2N now, if N is 2**256 (assuming only 256 bits of entropy per key) and K is 2**32 (4 billion), you get a chance that there will be a collision *anywhere* of roughly 2**64/2**257 which reduces to 1/(2**193). i.e., there's a greater chance that someone will be able to guess your triple-des session key than there will ever be a public key collision in a population of 4 billion. The chance of a bug (and that bug can be either a defect, or an eavesdropper :-) ) in the random number generator is much higher.. - Bill

**Re: comments on client auth***From*: dpkemp@missi.ncsc.mil (David P. Kemp)

- Prev by Date:
**Re: comments on client auth** - Next by Date:
**Re: comments on client auth -Reply** - Next by thread:
**Re: SDSI name interpretation** - Index(es):