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

Re: comments on client auth

David P. Kemp wrote:
> > 
> > If key generation were guaranteed to have enough real entropy for the key
> > size, I don't worry about the 2^{-1024} or less chance of duplicate key
> > generation (worse for elliptic curves because keys are smaller, but still
> > infinitessimal).
> I'm not a mathematician, but do I remember being surprised back in high
> school to learn that with 38 people in a room, there's a 50% chance that
> two of them have the same birthday.

According to my calculations, at 23 people the probability is 50.73%.

The probability that k things chosen out of n at random will all be different
is P=n*(n-1)*...*(n-k)/n^k. If k << n, then, to 1st order, this is
> 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.



> > Are you suggesting that a single entity generate all keys so that if there's
> > a weakness it can let out only unique keys and no one becomes aware of the
> > weakness?
> No!
> > ...that a single entity register all public keys, so that it can say "oops,
> > try that one again -- and we're not telling you why"?
> Good question.

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.