On 2011-10-11 16:54, Robert J. Hansen wrote: > Okay, fine: you can exclude all six-digit numbers (900,000 of them), all > five-digit numbers (90,000 of them), all four-digit numbers (9,000 of > them), all three-digit numbers (900 of them), all two-digit numbers (90 > of them) and all one-digit numbers (ten of them) [*]. You've excluded > 900,000 + 90,000 + 9,000 + 900 + 90 + 10 = one million total numbers out > of the possible ten million. You've reduced the keyspace by 10%.
That "10%" really depends on what you are revealing. Consider a 256-bit key. Telling you that it's "proper" 256 bits (i.e. MSB is 1) I've just halved the search space. I'd guess that revealing that a single base-n digit is non-zero you loose 1/n of the keyspace (base-10: 10%, base-2: 50%). Let's see: given m base-n digits, the keyspace has n^m elements. Revealing one of those digits to be non-zero, the search space is reduced to (n-1)*n^(m-1), so you've lost n^m-(n-1)*n^(m-1) items from your keyspace. That's (n^m-(n-1)*n^(m-1))/n^m of your keyspace, i.e. 1-(n-1)/n = 1/n. So the bit case is the worst-case, and even though I'm paranoid enough for a 4096-bit pubkey, I can sleep well when a 256-bit symmetric key is really worth 255 bits. :-) P.S. where did the [*] go? > If his passphrase has zero margin of safety, he's done something > foolish: his passphrase no longer meets his entropy requirements. On > the other hand, if his passphrase is longer than necessary to meet his > requirements, he can afford to throw out 10% of the potential keyspace > without losing any sleep. > > What he's done here is pretty much exactly what I've described, just in > a different numerical base. > > Tell you what: I'll put my money where my mouth is. The low-order bits > of the primes that comprise my private key are both '1'. Doesn't help > you out very much, does it? ;) Oh, also, "this!" -- PGP: A0E4 B2D4 94E6 20EE 85BA E45B 63E4 2BD8 C58C 753A PGP: 2C23 EBFF DF1A 840D 2351 F5F5 F25B A03F 2152 36DA _______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
