Safe prime modulo groups Zp quadratic residues count in DH groups RFC3526?

Question

Let's create an example with safe primes, suppose we have a group Zp* (operation is multiplication), and where p=23, q=11 and g=2.

Then group elements are {1 2 4 8 16 9 18 13 3 6 12}, so there are exactly q count elements and it turns out that all these elements are quadratic residues modulo p.

However if I take a group Zp* and where p=59, q=29 and g=2, it will generate me a group with p count elements where 50/50 are quadratic and non-quadratic residues modulo p.

How many elements will generate, for example, DH2048bit group and are all they quadratic residues modulo p? Where this guarantee comes from?

I believe that it is a dumb question, but I'm kinda stuck on understanding it...

Answer 1

if I take a group $\mathbb Z_p^*$ where $p=59$, $q=29$ and $g=2$, it will generate me a group with $p$ count elements where $50/50$ are quadratic and non-quadratic residues modulo $p$.

Yes. This happens because $g$ is a quadratic non-residue in $\mathbb Z_p^*$ with $p=59$, as shown by $\left(\frac g p\right)=-1$, equivalently $g^{(p-1)/2}\bmod p=p-1$, hence the group contains quadratic non-residues (the odd powers of $g$) and quadratic residues (the even powers of $g$). It won't happen if $g$ is a quadratic residue (and $p$ and $q-(p-1)/2$ are prime).

In order to build a subgroup of order $q=(p-1)/2$ of the group $\mathbb Z_p^*$ with generator $g$, we want to pick $p$ and $g\in[2,p)$ such that three conditions hold:

• $p$ is prime
• $q=(p-1)/2$ is prime
• $g^q\bmod p=1$

The later condition removes about half of candidates $p$ if we fix $g$, e.g. $g=2$.

The 2048-bit MODP Group of RFC 3526 is built in that way with $g=2$, and a further condition on $p$: that $p=2^i-2^{i-64}+2^{64}\cdot\left\lfloor2^{i-130}\pi+j\right\rfloor-1$ for $i=2048$ and minimal $j\ge0$. This further condition:

• Makes modular reduction modulo $p$ slightly easier than for random $p$ of the same size because the high-order 66 bits are all 1, simplifying estimation of quotient limbs in long division for up to 64-bit limbs,
• yet makes $p$ far enough from an exact power of two that it won't allow special sieving methods to solve the DLP mod $p$ much faster than for a random prime $p$ matching the above conditions, because the 67^th bit is different from the previous.
• Makes Montgomery modular reduction modulo $p$ slightly easier than for random $p$, because the low-order 64 bits (at least) are 1, removing the need for multiplication steps by a quantity $\mu$ that's going to be $1$ for up to 64-bit limbs (see this).
• Makes $p$ an otherwise nothing-up-my-sleeves 2048-bit integer, thanks to $\pi$ and minimal choice of $j$.