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

Re: comments on client auth

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.
References: