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

*To*: Bill Stewart <stewarts@ix.netcom.com>*Subject*: Re: comments on client auth*From*: Ben Laurie <ben@gonzo.ben.algroup.co.uk>*Date*: Fri, 21 Jun 1996 20:30:47 +0100 (BST)*Cc*: ben@algroup.co.uk, spki@c2.org*In-Reply-To*: <199606210813.BAA07889@infinity.c2.org> from "Bill Stewart" at Jun 21, 96 01:09:00 am*Reply-To*: ben@algroup.co.uk*Sender*: owner-spki@c2.org

Bill Stewart wrote: > > >> 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 :-) Good point. Thanks for the correction ;-) Perhaps we should use 1033 bit keys just to be safe <really big grin>. BTW, I also got my base 2 to base 10 conversion wrong. 2^825 is nearer 10^250. Allowing for the correction, that should be around 10^247. Also, I don't quite see the factor of 26 ... for the low likelihood in the example, the factor is 693, not 693^.5, surely? > 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 Even at 384 bits we are still looking at around 10^50:1 for 2^100 keys. This is still an exceedingly large number. BTW, can anyone remember the number of atoms in the known universe? (I seem to remember around 10^30) - I'm still trying to find a vaguely graspable comparison... Cheers, Ben. > 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! > -- Ben Laurie Phone: +44 (181) 994 6435 Freelance Consultant and Fax: +44 (181) 994 6472 Technical Director Email: ben@algroup.co.uk A.L. Digital Ltd, URL: http://www.algroup.co.uk London, England.

**Re: comments on client auth***From*: Bill Stewart <stewarts@ix.netcom.com>

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