[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: comments on client auth
>> Perhaps someone more proficient with numbers could calculate how many
>> certificates would have to exist in the world, each generated with perfect
>> 1024 bit entropy, before there was, say, a 1% chance of a collision.
>
>I can't quite be bothered to solve this for n=2^1024 and P=.99 but for the
>sake of illustration, lets take k=2^100 (=10^33, roughly, or 2*10^23
>certificates per person in the world). Then P=1-2^200/2^1025=1-2^(-825).
>In other words, the probability of a collision is roughly 1 in 10^275.
>Vanishingly small, I would say.
Keys aren't distributed evenly, because prime numbers aren't distributed
evenly; density is roughly proportional to 1/logn, so if you have 1024 bits
of entropy picking a random number, and searching upwards for primes from there,
you'll probably have to pass 693 of them on average (logs base e) to get a
prime.
So it's maybe 2^1015 keys instead of 2^1024, and collisions 26 times more
likely :-)
The effect is much more severe if you're using overly-short keys,
like 384-bits, but it's still excessively unlikely that you'll get any
collisions
unless something's seriously wrong with your RNGs.
# Thanks; Bill
# Bill Stewart +1-415-442-2215 stewarts@ix.netcom.com
# http://www.idiom.com/~wcs
# Dispel Authority!
Follow-Ups: