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?

  • $\begingroup$ 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. $\endgroup$ Jul 20, 2013 at 19:16

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.