[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: comments on client auth
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
References: