# ElGamal: Generation of “g” value?

I haven't been able to find a clear explanation on this (and I'm probably just confused in general). I have the following parameters of ElGamal signatures:

• $p$ = safe prime
• $q = (p-1)/2$
• $g$ = an element of $F_p$ with order $q$.
• $r$ = random $1 < r < q$
• $s$ = private key
• $Y$ = public key, $Y = g^s$

My question is, is there an easy way to generate a $g$ value, or should I just generate a random value, then check that it is in the group?

If $q$ is prime (which is a common additional constraint) then the possible orders for a random $F_p$ between $2$ and $p-2$ inclusive is either $q$ or $2q$ so you can avoid having to check the order by picking one at random, squaring it and using the result.

• Okay that makes sense. I had seen the squaring elsewhere but it didn't provide an explanation, so i was a little wary... Thanks! – Chris C Apr 12 '13 at 23:17
• P.S. - do you have any sources for this? I'd like to reference something other than stackoverflow :) – Chris C Apr 12 '13 at 23:23
• If your maths knowledge is such that you can't see the truth of this when it's pointed out to you then the best solution is for you to brush up on your maths rather than for me to find someone who agrees with me. – Barack Obama Apr 12 '13 at 23:46
• However, if you look at Appendix A.2 of FIPS 186-3 (the Digital Signature Standard) you will find a more comprehensive treatment of similar issues which boils down to pretty much the same thing. – Barack Obama Apr 13 '13 at 0:02
• I'm not a very mathematically oriented person (nor cryptography), just doing some CS homework. Sorry! Thank you very much for all the help. – Chris C Apr 13 '13 at 0:08

As an alternative solution to the correct answer that Barack has posted, if you have $p=7 \bmod 8$, then the selection $g=2$ works just fine. In this case, $g=2$ is a quadratic residue (and hence has order $(p-1)/2$). In addition, you can show that if you can decrypt ElGamal messages with $g=2$, then you can decrypt ElGamal messages with any $g$; hence we might as well use a $g$ that makes (at least) the encryption operation somewhat more efficient.

• I have experienced people being quite negative about efficiency gains from having $g=2$. I haven't investigated so I have no opinion. Also, I found abc's answer to this post which would lead people (wrongly) to believe that $g=2$ is insecure for signatures in all cases. Perhaps you may care to leave a comment on the linked question to set the record straight for posterity. You have the gravitas I do not.. (yet!) – Barack Obama Apr 13 '13 at 0:31
• The efficiency gains from having $g = 2$ depends on how modular exponentiation is implemented. You will get maximum effect if you use left-to-right exponentiation and replace multiplication by $g$ with adding the intermediary result with itself, subtract $p$ and pick that difference as the intermediary result if it is non-negative. – Henrick Hellström Apr 13 '13 at 10:46
• Thanks for the additional information! I had seen the use of 2 in several papers. – Chris C Apr 13 '13 at 14:33