0
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ For the Legendre leak Decisional Diffie-Hellman: compute Legendre symbol of $g^{ab}$ from $g^a$ and $g^b$? $\endgroup$
    – kelalaka
    Oct 11, 2023 at 14:48
  • 1
    $\begingroup$ I think this covers first dot. How to find generator 𝑔 in a cyclic group? $\endgroup$
    – kelalaka
    Oct 11, 2023 at 14:52
  • $\begingroup$ 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. $\endgroup$
    – poncho
    Oct 11, 2023 at 14:55
  • $\begingroup$ @poncho 𝑔=2 generates the subgroup of size 𝑞 if 𝑝≡7(mod8) how do 7 and 8 appear here? $\endgroup$
    – pacman
    Oct 13, 2023 at 9:37
  • $\begingroup$ @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... $\endgroup$
    – poncho
    Oct 13, 2023 at 12:07

1 Answer 1

1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – pacman
    Oct 12, 2023 at 7:22
  • $\begingroup$ 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? $\endgroup$
    – pacman
    Oct 12, 2023 at 7:30
  • 1
    $\begingroup$ @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 $\endgroup$
    – poncho
    Oct 12, 2023 at 13:05
  • $\begingroup$ 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? $\endgroup$
    – pacman
    Oct 13, 2023 at 4:39

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.