1

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.

pintor
  • 558
  • 3
  • 14
  • Is it implicit in the question that $q$ is prime (as $p$ is said to be, explicitly but incidentally)? – fgrieu Feb 07 '18 at 17:57
  • @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. – pintor Feb 08 '18 at 09:03
  • 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. – fgrieu Feb 08 '18 at 09:44
  • @fgrieu Thank you for pointing this out. I've edited the question. – pintor Feb 08 '18 at 10:50

2 Answers2

4

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$.

Daniel
  • 3,942
  • 1
  • 18
  • 34
  • 4
    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$. – Squeamish Ossifrage Feb 07 '18 at 18:05
  • Thanks @SqueamishOssifrage, I was in a rush and couldn't fill in the details – Daniel Feb 07 '18 at 18:17
3

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.

poncho
  • 147,019
  • 11
  • 229
  • 360
  • 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 – pintor Feb 08 '18 at 09:24
  • @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$ – poncho Feb 08 '18 at 13:33