# Safe primes subgroup in Diffie–Hellman key exchange

I'm trying to understand how the safe primes numbers are used in Diffie–Hellman key exchange. According to wiki:

The order of G should have a large prime factor to prevent use of the Pohlig–Hellman algorithm to obtain a or b. For this reason, a Sophie Germain prime q is sometimes used to calculate p = 2q + 1, called a safe prime, since the order of G is then only divisible by 2 and q. g is then sometimes chosen to generate the order q subgroup of G, rather than G, so that the Legendre symbol of ga never reveals the low order bit of a. A protocol using such a choice is for example IKEv2

I'm trying to figure out the context of the paragraph above with small numbers. q=11 is Sophie Germain prime -> safe prime p=23. Than I need to find g so g is then sometimes chosen to generate the order q subgroup of G.

• Shall I find g so g^11 (mod 23) will result in a number within the order-11 subgroup?

• Or shall I abandon GF(23) and operate in GF(11)?

If you can provide a clear example with some small numbers that illustrate my misunderstanding, please, do it.

• For the Legendre leak Decisional Diffie-Hellman: compute Legendre symbol of $g^{ab}$ from $g^a$ and $g^b$? Commented Oct 11, 2023 at 14:48
• I think this covers first dot. How to find generator 𝑔 in a cyclic group? Commented Oct 11, 2023 at 14:52
• For safe primes, $g=2$ generates the subgroup of size $q$ if $p \equiv 7 \pmod{8}$, it generates the entire group of size $2q$ if $p \equiv 3 \pmod{8}$. In your example, $23 \equiv 7 \pmod{8}$, and so $g=2$ generates a group of size 11. Commented Oct 11, 2023 at 14:55
• @poncho 𝑔=2 generates the subgroup of size 𝑞 if 𝑝≡7(mod8) how do 7 and 8 appear here? Commented Oct 13, 2023 at 9:37
• @pacman: from the law of quadratic residuosity. That is considerably deeper than what is currently puzzling you - I suggest you don't worry about it now... Commented Oct 13, 2023 at 12:07

Well, first off, when you have a safe prime $$p > 5$$, then all the values between $$1$$ and $$p-1$$ fall into four categories:

• Values $$g$$ that have the order $$p-1$$; these values generate all values between $$1$$ and $$p-1$$, that is, $$g^x = a \pmod p$$ has a solution $$x$$ for all values $$1 \le e < p$$. These values of $$g$$ are not quadratic residues, that is, there is no value $$a$$ such that $$a^2 = g \pmod{p}$$

• Values $$g$$ that have the order $$q$$; these values generate half the values between $$1$$ and $$p-1$$, that is, $$g^x = a \bmod p$$ has a solution $$x$$ for half the values of $$a$$. These values $$g$$ are quadratic residues (that is, there is a value $$b$$ such that $$b^2 = g \pmod{p}$$, and every value in the generated group is also a quadratic residue.

• The value $$-1$$ (aka $$p-1$$)

• The value 1

Hence, if we pick a value $$g$$ which is neither $$1$$ nor $$p-1$$, then the order will always be either $$p-1$$ or $$q$$.

With that in mind:

Shall I find $$g$$ so $$g^{11} \pmod {23}$$ will result in a number within the order-11 subgroup?

Well, $$g^q \bmod p$$ will always be either $$1$$ or $$p-1$$. If it is $$1$$, then $$g$$ has order $$q$$ (or $$g=1$$). If it is $$p-1$$, then $$g$$ has order $$p-1$$ (or $$g=p-1$$).

So, it can be used to test $$g$$ to see which group it generates; however you wouldn't want to use the value $$g^q \bmod p$$.

You asked for an example with small numbers; we find that $$2^{11} \bmod 23 = 1$$, hence $$g=2$$ generates the subgroup of size 11. On the other hand, $$5^{11} \bmod 23 = 22$$, hence $$g=5$$ generates the entire group (of size 22).

That works as a test, however you don't need to go to that amount of effort.

If you're looking for a value that generates the prime sized subgroup (and not the subgroup of size 2 :-), one easy option is to pick $$g=4$$. That's obviously not in the first, third or fourth category, and so it must be in the second.

Another, rather less obvious, option is if $$p \equiv 7 \pmod 8$$; if that is true, then $$g=2$$ also generates the subgroup).

Or shall I abandon GF(23) and operate in GF(11)?

Nope; all work is done in $$GF(p)$$

• Thanks for such a detailed explanation. Can u please explain why the fact that 2^11 mod 23 = 1 leads to the conclusion that it generates a subgroup of size 11? Commented Oct 12, 2023 at 7:22
• and one more detail to clarify: is Legendre leak a main reason behind using of subgroup of order q or are there any important reasons behind it? Commented Oct 12, 2023 at 7:30
• @pacman: as for why $2^{11} \bmod 23 = 1$ tells us that the subgroup is size 11; well, we know that $2 \ne 1, 22$, and so cases 3, 4 do not apply. In case 1, the value $g$ has order 22, but this calculation shows that 2 has a smaller order, so the only possibility left is 11. Another way of looking at it: the order of the value $g$ (the smallest value $x>0$ s.t. $g^x = 1$ is the size of the subgroup $g$ generates. We see that $2^{11} = 1$, and so the order of 2 must be a factor of 11. Now, 11 is prime, so the only possibilities are 1 and 11; it's not 1 ($2^1\ne 1$), so the order must be 11 Commented Oct 12, 2023 at 13:05
• I got it. Here crypto.stackexchange.com/a/47266/103942 you explained the difference between subgroup order for p and 2p. Now I realise why subgroup with 2p order leaks 1 bit of the exponent. These facts really helped to connect the dots. Btw, maybe you can recommend some books that cover this topic? Commented Oct 13, 2023 at 4:39