How to get the order of a group generator in DH?

Question

For a DH parameter prime, if the generator $g$ is 2, how do I get the order $q$?

Answer 1

A generator $g$ means that $g$ generates the group $\langle g \rangle =G$. Therefore the order of the group $ord(G)$ is equal to the order of the generator $ord(g)$.

If $2$ ( or any other element) is not a generator that is $\langle 2 \rangle \neq G$ then the element $2$ forms a subgroup under the group operation. Then the order of $2$ must divide the order of the group, $ord(2) | ord(G)$ by the Lagrange's theorem;

if $H$ is a subgroup of a finite group $G$, then the order of $H$ divides the order of $G$

Diffie-Hellman Key Exchange can be used with multiplicative and additive groups. DHKE represents the multiplicative version and ECDH is the additive version with the Elliptic Curves over a finite field $E(K)$.

For the multiplicative group To find the order, factor the $ord(G)$ then find the smallest factor $x$ , $x|ord(G)$, such that $g^x = 1$, where $g^x$ means $$g^x = \underbrace{a \cdot a \cdot a \cdots a}_{x\text{ times}}.$$

In the additive group like ECC, you need to check that $[x]G = \mathcal{O}$ where $\mathcal{O}$ is the identity element of the curve, $G$ is a base element and $[x]G$ means $$[x]G = \underbrace{a + a + a + a}_{x\text{ times}}.$$

Both can be checked efficiently,

• for the multiplicative group; square-and-multiply algorithm
• and for the ECC; double-and-add algorithm.

In the DHKE, in practice, we chose a safe prime $p = 2 q +1$ where $q$ is another prime and called Sophie Germain prime. In this case, the order of $G$ is only divisible by 2 and $q$, then we can choose the $g$ as the generator of the subgroup $H$ of order $q$. Since $q$ is a prime, then any element of $H$ is a generator. Take a random, or find the smallest element $x$, such that $g^2 \neq 1$ and $g^q =1 $ then we have a generator.

In the safe prime case, we have 4 possible groups orders $\{1,2,q,2q\}$ and the groups are $\{1\},\{1,-1\}$, the quadratic residues, and the whole group. In this case, to find a generator with order $q$ quadratic residues is enough, and quadratic non-residues will have $2q$ order, other than the $\{1,-1\}$. To pick a generator, the law of quadratic residues can be used. The results are in Poncho's answer;

The theory behind this is the Second Supplement to Law of Quadratic Reciprocity; \begin{align}\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} \label{1}\tag{1} \end{align} and there is an elemtary proof of the above statement and $\left(\frac{2}{p}\right)$ is the multiplicative Legendry Symbol.

• $2$ is a square modulo $p$ if and only if $p\equiv\pm 1\mod 8$ and thus the order is $q$.
• $2$ is not a square modulo $p$ if and only if $p\equiv\pm 3\mod 8$ and thus the order is $2q$.

If you are looking for some examples see RFC 2412, Appendix E ‘The Well-Known Groups’).

In the case of ECDH, the process a bit more complex, We don't need to choose curves with a prime number of rational points like NIST P-224 where every element is a generator, however, it doesn't have twist security and side-channel free Montgomery ladder.

Answer 2

To extend kelalaka's answer, if $p$ is a safe prime (that is, if $p = 2q+1$ with $q$ prime), then:

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

• If $p \equiv 3 \pmod 8$, then the order of $g=2$ will be $2q$

• If $p = 5$ (the only other possibility), then the order of $g=2$ is 4 (that is, $2q$)