1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This question is wrong. The group order is part of the group specification in DHKE. There’s no concept of “getting group order from the generator”. $\endgroup$
    – Gee Law
    Dec 24, 2020 at 19:04

2 Answers 2

1
$\begingroup$

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,

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Nice extension, thanks, $\endgroup$
    – kelalaka
    Dec 24, 2020 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.