Subject: Re: PKINIT open issues

From: Jonathan Trostle <[email-masked]>
Date: Fri, 23 Apr 2004 11:56:39 -0400 (EDT)

> * Is b(g^x)^y mod p a random element of the set of all possible
>   (g^x)^y mod p assuming a good generator g and good prime p, random x
>   and random y?  I believe the answer is trivially yes.

I'm not sure what the b in b(g^x)^y means. But (g^x)^y mod p is a random
element if x or y is random. A good prime p is typically a safe prime; i.e.,
p = 2q + 1 where q is a prime. That prevents small subgroup attacks. So
there need to be restrictions on p to ensure that (g^x)^y mod p is a
random element from a large subgroup (size q in this case).

>  * What is the distribution of (g^x)^y mod p?  I don't know, but I
>   suspect that the cardinality is sufficiently high that the
>   distribution is not horrible.

The distribution is uniform, assuming that either x or y is chosen 
uniformly from a range that is any multiple of p-1.

> * How much information is lost by the DH exchange.  I.E.  what is the
>   cardinality of (g^x)^y mod p?  I believe the answer is approximately
>   1/2 to 1/4 the size of p for well-chosen p.

(g^x)^y mod p is, on average, about half the size of p-1. So if p has 1024
bits, then (g^x)^y mod p has 1023 bits on average.

Jonathan

---

From: Sam Hartman <[email-masked]>
Date: Fri, 23 Apr 2004 13:07:50 -0400

>>>>> "Jonathan" == Jonathan Trostle <[email-masked]> writes:

    >> * What is the distribution of (g^x)^y mod p?  I don't know, but
    >> I suspect that the cardinality is sufficiently high that the

    Jonathan> The distribution is uniform, assuming that either x or y
    Jonathan> is chosen uniformly from a range that is any multiple of
    Jonathan> p-1.

I figured the distribution had to be close to uniform for a safe prime
and reasonable group size (not 2) but couldn't prove it on the fly.

The distribution was the interesting question; I think everyone
realized that determining the MSB of a DH exchange was as hard as
breaking the exchange.  What we were unclear about is whether the
distribution would be skewed enough to produce bad symmetric keys.