1
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Okay that makes sense. I had seen the squaring elsewhere but it didn't provide an explanation, so i was a little wary... Thanks! $\endgroup$
    – Chris C
    Commented Apr 12, 2013 at 23:17
  • $\begingroup$ P.S. - do you have any sources for this? I'd like to reference something other than stackoverflow :) $\endgroup$
    – Chris C
    Commented Apr 12, 2013 at 23:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Barack Obama
    Commented Apr 12, 2013 at 23:46
  • $\begingroup$ 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. $\endgroup$
    – Barack Obama
    Commented Apr 13, 2013 at 0:02
  • $\begingroup$ I'm not a very mathematically oriented person (nor cryptography), just doing some CS homework. Sorry! Thank you very much for all the help. $\endgroup$
    – Chris C
    Commented Apr 13, 2013 at 0:08
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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!) $\endgroup$
    – Barack Obama
    Commented Apr 13, 2013 at 0:31
  • $\begingroup$ 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. $\endgroup$
    – Henrick Hellström
    Commented Apr 13, 2013 at 10:46
  • $\begingroup$ Thanks for the additional information! I had seen the use of 2 in several papers. $\endgroup$
    – Chris C
    Commented Apr 13, 2013 at 14:33

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.