Why revoke a key?

[Jerome Baum]

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