Re: Truly Stealthy PGP

[Hal <hfinney@shell.portal.com>]

From: hughes@ah.com (Eric Hughes)
> What I suggest is making the exponent (the encrypted session key)
> completely random over the length assigned to it, since that's
> visible, and just live with a slightly non-flat distribution of
> exponents mod n.  It turns out that this can be made to work just
> fine.
> 
> n is the modulus.  Divide L by n to get L = t * n + s, s in [0,n).
> Assume x is random in [0,L).  The entropy of x mod n is
>    E = log L/t - s(t+1)/L log( 1 + 1/t )
> 
> What is the smallest value of E?  In other words, what's the upper
> bound of the randomness we can lose?  It happens when when t = 1 and
> when n = L/2+1.  This maximize the expression in t and maximizes s at
> n-2.  This minimum value of E is
> 
>    E_min = log L - ( ln 2 - 2/L ln 2 )
> 
> In other words, the most entropy we can lose is two bits.  That's
> right, only two bits.  Since the entropy of the session key is the
> length of the modulus, for a 1000 bit key the entropy loss is
> negligible.

I'm not sure the point of this entropy calculation.  For the case n =
L/2+1, t=1, it seems to me that the RSA-encrypted session key (sk^e mod n)
is never going to have the high bit set, so with K such messages it should
be possible to tell that something is going on with probability 1 - 2^-K.

> Therefore, my recommendation is that the session key representation be
> chosen randomly over [0,2^k) and to use as an actual session key this
> value mod n.  The effective entropy loss is small enough not to worry
> about.
> 
> Eric
> 

If the session key is chosen from [0,L), still the encrypted session
key m = sd^e mod n will be uniform in [0,n).  I don't quite follow here
how exactly we go from something uniform in [0,n) to something uniform in
[0,L), if that is what Eric is proposing.

Hal