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

*To*: "David P. Kemp" <dpkemp@missi.ncsc.mil>*Subject*: Re: comments on client auth*From*: Ben Laurie <ben@gonzo.ben.algroup.co.uk>*Date*: Thu, 20 Jun 1996 19:23:05 +0100 (BST)*Cc*: spki@c2.org*In-Reply-To*: <199606201623.MAA01542@argon.ncsc.mil> from "David P. Kemp" at Jun 20, 96 12:23:58 pm*Reply-To*: ben@algroup.co.uk*Sender*: owner-spki@c2.org

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.

**Re: comments on client auth***From*: dpkemp@missi.ncsc.mil (David P. Kemp)

- Prev by Date:
**Re: comments on client auth** - Next by Date:
**Re: comments on client auth -Reply** - Next by thread:
**Re: SDSI name interpretation** - Index(es):