[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
P=(n^k-(1+2+...+k)n^(k-1))/n^k=1-k*(k+1)/2*n
>
> 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.
Cheers,
Ben.
>
> > 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.
References: