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

*To*: ben@algroup.co.uk*Subject*: Re: comments on client auth*From*: Bill Stewart <stewarts@ix.netcom.com>*Date*: Fri, 21 Jun 1996 01:09:00 -0700*Cc*: spki@c2.org*Sender*: owner-spki@c2.org

>> 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!

**Re: comments on client auth***From*: Ben Laurie <ben@gonzo.ben.algroup.co.uk>

- Prev by Date:
**Re: comments on client auth -Reply** - Next by Date:
**Private keys and the emperor's clothes** - Next by thread:
**Re: SDSI name interpretation** - Index(es):