Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  CodesInChaos Jul 20 '13 at 19:16
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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