1
$\begingroup$

For $p=2q+1$,where p and q are primes, we have subgroups of order $p−1$, $q$, $2$ and $1$. To find $G_q$, usually we just check that $g^q\bmod p=1$ and that's it.

However,here it's mentioned that there is a chance (very unlikely but still) that a group satisfying $g^q\bmod p=1$ is of order $1$ or $2$.

Ok, suppose we start checking whether $g^q\bmod p$ is equal to $1$ starting from $g=2$ (to eliminatie $g=1$). I don't see how a subgroup can satisfy $g^q\bmod p=1$ and be of order $2$ (so $g^2\bmod p=1$ too). It seems that for all even $a$ in $g^a\bmod p$ the result is $1$. On the other hand, since $p$ is a prime and $g^q\bmod p=1$ holds, then for all odd $a$ odd it's equal to $1$ too. I fail to see, how any generater except $g =1$ can satisfy it. Do we rally need to chech that $g^2\bmod p$ is not $1$?

Additional question, is it a good idea to check all integers in the increasing order starting from $g=2$? Is there any security issues related to a small $g$? Suppose, in the real ElGamal implementation with $p$ of 1024-bits or 2048-bits, I check all $g$ from $2$ till I find the $G_q$ subgroup generator.

Improve this question
$\endgroup$
4
  • $\begingroup$ Is it implicit in the question that $q$ is prime (as $p$ is said to be, explicitly but incidentally)? $\endgroup$
    – fgrieu ♦
    Commented Feb 7, 2018 at 17:57
  • $\begingroup$ @fgrieu, q is prime and p is a safe prime. At least they are both supposed to be primes. I'm not sure you can be certain when you work with 1024+ bits numbers. However, in FIPS 186-4 (Appendix A.1.2.1) there is a method for prime generation so that numbers are guaranteed to be prims. $\endgroup$
    – pintor
    Commented Feb 8, 2018 at 9:03
  • $\begingroup$ It is worth stating in the question itself that $q$ is prime. In FIPS 186-4, for DSA (the only scheme there relying on the difficulty of the discrete logarithm modulo $p$), $\ (p-1)/2$ is not prime. Rather, $p=2\alpha q+1$ with $p$ a large prime (e.g. 2048-bit) and a $q$ less large prime (e.g. 256-bit). That drastically changes how the generator $g$ is established. $\endgroup$
    – fgrieu ♦
    Commented Feb 8, 2018 at 9:44
  • $\begingroup$ @fgrieu Thank you for pointing this out. I've edited the question. $\endgroup$
    – pintor
    Commented Feb 8, 2018 at 10:50

2 Answers 2

Reset to default
3
$\begingroup$

Do we rally need to chech that $g^2 \bmod p$ is not $1$?

The only values of $g$ for which this is true are $g=1$ and $g=p-1$; avoid those two values, and you don't need that check.

Additional question, is it a good idea to check all integers in the increasing order starting from $g=2$?

Well, there's no specific security reason to say that's a bad idea, however there are easier ways:

  • If we select $p \equiv 7 \pmod 8$, then $g=2$ will always be of order $q$

  • $g=4$ will always have order $q$ (as it is always a quadratic residue).

Is there any security issues related to a small $g$?

No, there are no issues. We can show that solving the CDH problem with respect to a small $g$ is no easier than the general case.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you. As for the easier way, we can be certain that a quadratic residue will always generate a group of order q. Does it mean, that g=4 is a generator of an order q subgroup for any safe prime p > 4 $\endgroup$
    – pintor
    Commented Feb 8, 2018 at 9:24
  • $\begingroup$ @pintor: Yes, it does mean that. As you point out, the only subgroups are of sizes 1, 2, $q$ and $p-1$. It's not 1 and (if $p \ne 5$) not 2. As $4=2^2$ is a quadratic residue, it's not $p-1$, hence the only possibility is $q$ $\endgroup$
    – poncho
    Commented Feb 8, 2018 at 13:33
4
$\begingroup$

Assuming you have the same setting as the linked question (in particular $q$ is prime, it's true: you cannot have $g^2 = 1\bmod p$ and $g^q = 1\bmod p$ simultaneously unless $g=1$ or $q=2$.

It's important to notice that if the condition $g^q = 1\bmod p$ is satisfied and $g$ is not the identity, then $g$ will be a generator.

I think that what PulpSpy means in the answer you linked is that either you're lucky and $g^q = 1\bmod p$, with $g$ not the identity, or you're not lucky and $g^2 = 1\bmod p$ (not both congruences simultaneously), in which case you have to try again with another $g$.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ To amplify this: It's a straightforward theorem of group theory that if $g^x$ is the identity for $x \ne 0$, then $\operatorname{ord}(g) \mid x$. If $g^2 \equiv 1 \pmod p$ and $q$ is odd, then $\operatorname{ord}(g) = 2$ and we obviously cannot have $2 = \operatorname{ord}(g) \mid q$, which means we cannot have $g^q \equiv 1 \pmod p$. $\endgroup$
    – Squeamish Ossifrage
    Commented Feb 7, 2018 at 18:05
  • $\begingroup$ Thanks @SqueamishOssifrage, I was in a rush and couldn't fill in the details $\endgroup$
    – Daniel
    Commented Feb 7, 2018 at 18:17

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.