# Is generating public key inevitably slow in classic Diffie-Hellman if the private key is large?

Let's say I pick a 3000+ bit prime $p$ for which I also know that $q = (p - 1) / 2$ is a prime. If I've understood correct, then I can pick pretty much any $g$.

Is generating $g^x$ now inevitably slow for any large $x$ regardless of choice of $g$?

Do I still only select some $2n$ bit value for $x$ - where $n$ is the number of desired bits of security - in order to keep the calculation fast?

• I think you can still choose a small value for x (say 256 bits) without losing much security even with a 3000 bit q. A large q is mainly problematic for DSA, not DH. Jul 20, 2013 at 19:16

If $g$ is not in the order-$q$ subgroup, then one can easily calculate the last bit of $x$ from $g^{\hspace{.01 in}x}$.

-

If $\: g=2 \:$ or $\: g=4 \:$ then you can very easily compute small powers of $g$.

You could have a large lookup table for powers of $g$.

For example, you could store $\:g^{\hspace{.01 in}2^{\hspace{.01 in}2\cdot m}}\hspace{-0.02 in},g^{\hspace{.01 in}2^{\hspace{.01 in}(2\cdot m)+1}}\hspace{-0.02 in},g^{\hspace{.01 in}2^{\hspace{.01 in}2\cdot m}+2^{\hspace{.01 in}(2\cdot m)+1}}\:$ for each relevant value of $m$.

However, such a lookup table would make the benefit from
three sentences before this sentence mostly redundant.

You could choose $x$ so that there is a relatively short addition chain from $1$
(and any powers you have stored in a lookup table) to $x$, although this idea may well be vulnerable
to attacks that are similar to attacks on RSA private exponents with low Hamming weight.

-

You do that as long as $g$ is in the order-$q$ subgroup. $\:$ If, for whatever reason, you choose a
$g$ that is not in the order-$q$ subgroup, then you select some $\:(2\hspace{-0.03 in}\cdot\hspace{-0.03 in}n)\hspace{-0.02 in}+\hspace{-0.03 in}1\:$ bit value for $x$ instead.