# Why using q = (p - 1)/2 for discrete log Diffie-Hellman scalar operations and not p?

As defined in RFC 3526 the prime $$p$$ and generator $$g$$ are known. The prime $$p$$ defined there is a safe prime, which can also be expressed as $$p=2q+1$$ with $$q$$ prime. The amount of elements in this group G is $$\operatorname{ord}(G)=p-1$$.

Why does Diffie-Hellman use$$\bmod q$$ for scalar operations, where $$q=(p-1)/2$$ and for element's operation it uses$$\bmod p$$, as an example:

$$c=77777\bmod q$$, i.e. $$c=77777\bmod (p-1)/2$$

$$E=g^c\bmod p$$

Why can't scalars be of$$\bmod p$$ as well ($$c=77777\bmod p$$), since order of a group is $$\operatorname{ord}(G)=p-1$$?

Following this idea, why then, if $$q$$ is chosen for scalar modulo, we are not performing
$$\bmod q$$ for elements as well? I.e. $$E=g^c\bmod q$$, since therefore group order should be $$\operatorname{ord}(G')=q-1$$?

Also I don't understand why $$a=(p-1)$$, $$g^a\bmod p=1$$ and at the same time we have $$g^q\bmod p=1$$.

Like $$g^a=g^q$$?

Diffie-Hellman in the multiplicative group modulo $$p$$ performs all operations modulo $$p$$:

• Alice chooses random secret $$u$$, sends $$U=g^u\bmod p$$
• Bob chooses random secret $$v$$, sends $$V=g^v\bmod p$$
• Alice computes $$s=V^u\bmod p$$
• Bob computes $$s=U^b\bmod p$$
• Alice and Bob now have a shared secret $$s$$. Further steps of the protocol can use $$s$$ as key to a key derivation function, etc...

The parameters $$p$$ in RFC 3526 are such that $$p$$ is an odd prime, $$q=(p-1)/2$$ is prime, and $$g=2$$ has large prime order $$q$$ [equivalently $$2^q\bmod p=1\,$$].

In the execution of Diffie-Hellman, the quantity $$q$$ appears only optionally, and typically only as the upper bound for $$u$$ and $$v$$. A much smaller range can be used, and speeds-up the protocol.

We can prove that Alice and Bob get the same $$s$$ without introducing $$q$$ in the proof: it's enough that $$\left(g^u\right)^v=g^{(u\,v)}=g^{(v\,u)}=\left(g^v\right)^u$$, thus the same holds after reduction modulo $$p$$.

It's strictly optional to make the quantity $$q$$ appear in other equations like $$g^{(u\,v)}\bmod p=g^{(u\,v\bmod q)}\bmod p$$. This holds because we can write $$u\,v=k\,q+(u\,v\bmod q)$$, thus $$g^{(u\,v)}=g^{(k\,q+(u\,v\bmod q))}=\left(g^q\right)^k\,g^{(u\,v\bmod q)}$$, thus reducing$$\bmod p$$ we get \begin{align}g^{(u\,v)}\bmod p&=\,\bigl(\left(g^q\bmod p\right)^k\bigr)\,\bigl(g^{(u\,v\bmod q)}\bigr)\bmod p\\ &=\,\bigl(1^k\bigr)\,\bigl(g^{(u\,v\bmod q)}\bigr)\bmod p\\ &=\,g^{(u\,v\bmod q)}\bmod p\end{align}

Why can't scalars be of$$\bmod p$$ ?

Because in general, if does not hold that $$g^x\bmod p=g^{(x\bmod p)}\bmod p$$. Appropriate modulus in the exponent include

• the order of $$g$$ modulo $$p$$, that is the smallest strictly positive integer $$i$$ such that $$g^i\bmod p=1$$, which is $$i=(p-1)/2=q$$ when $$g=2$$ for the $$p$$ in RFC 3526.
• the order of the multiplicative group modulo $$p$$, that is the number of integers in $$[0,p)$$ that are coprime with $$p$$, equivalently the Euler totient for $$p$$, which is $$p-1$$ when $$p$$ is prime.
• $$\lambda(p)$$ where $$\lambda$$ is the Carmichael function, which also is $$p-1$$ when $$p$$ is prime.

order of a group is $$\operatorname{ord}(G)=p−1$$

Yes that holds for the multiplicative group modulo $$p$$. For $$p$$ and $$g$$ in RFC 3526, the order of $$g$$ is $$\operatorname{ord}(g)=(p−1)/2=q$$. Notice that $$g$$ is a generator of the subgroup of quadratic residues modulo $$p$$, not of the full group!

If we write $$a=p-1$$ as in the question, then it holds $$g^a\bmod p=1$$, as a consequence of $$p$$ being prime, and $$\gcd(p,g)=1$$ [since $$g=2$$ and $$p$$ is odd], per Fermat's little theorem.

It holds $$g^a\bmod p\,=\,g^q\bmod p$$, because both sides of the equation are $$1$$. For the right-hand side, that's by choice of $$p$$ and $$g$$ in RFC 3526.

It does not hold $$g^a=g^q$$ in the ring of integers, as maybe considered in the end of the question.

• Actually, for the last sentence, if we have $a=p-1$, then $g^a = g^q$ is true... Commented Jul 16 at 13:58
• @poncho: $g^a\equiv g^q\pmod p$ is true, and in the butlast paragraph of my answer I state and explain the equivalent $g^a\bmod p\,=\,g^q\bmod p$. But my reading of the question, based on it's last two paragraphs, is that the OP means $g^a=g^q$ in $\mathbb Z$, which does not hold. I've clarified the last sentence of my answer.
– fgrieu
Commented Jul 16 at 16:00
• @fgrieu so in DH 2048bit group we have a generator of 2, but that is not the DH 2048bit whole generator, am I correct? Because that generator of 2 will only create a subgroup of quadratic residues, and NOT the whole group. Am I correct in that? But DH 2048bit group is cyclic group as well, so is there any other generator that generates the whole DH 2048bit group (where all quadratic residues and non-residues are included)? Commented Jul 16 at 18:55
• @ojacomarket: Yes your understanding is correct when it comes to the 2048-bit MODP Group, or any full multiplicative group modulo $p$ such that $p=2q+1$ with $p$ and $q$ prime and such that for $g=2$ we have $g^q\bmod p=1$. Yes the full group has order $p-1=2q$ and is cyclic too, and has $q-1$ generators. These are the $g'$ such that ${g'}^q\bmod q=p-1$ and ${g'}^2\bmod p\ne1$. We can find one such $g'$ by trial and error. The smallest is always a prime. It's $g'=11$ for the 2048-bit group in RFC 3526.
– fgrieu
Commented Jul 16 at 19:08

Why Diffie-Hellman uses $$\bmod q$$ for scalar operations, where $$q=(p-1)/2$$ and for elements' operation it uses $$\bmod p$$

Other than the fact that DH doesn't actually do operations on scalars (it selects random scalars, and raises values to the power of the scalar, that's it), if it did, it would, in fact, compute them modulo $$q$$.

The reason is this: the order of the subgroup generated by $$g$$ is of size $$q$$; that is, if we consider all the values that $$g^x \bmod p$$ can take on, there are exactly $$q$$ of them (and not $$p-1$$). There are $$p-1$$ values in the group $$\mathbb{Z}_p^*$$, this implies that half of them cannot be expressed in the form $$g^x \bmod p$$.

Accordingly, we have (for example) $$g^a \cdot g^b = g^{(a+b) \bmod q}$$.

Why did the authors of RFC 3526 select things this way? Wouldn't it be more secure if $$g^x \bmod p$$ take on any particular value? Well, no - it turns out that if $$g$$ did generate the entire group (that is, if it was of order $$p-1$$), then it would be easy to find $$x \bmod 2$$ just by looking at $$g^x \bmod p$$ (and this is directly related to the fact that $$p-1$$ has $$2$$ as a factor). What this means is that selecting $$g$$ that would would leak the lsbit of each private exponent in DH. In contrast, the current $$g$$ (with order $$q$$) doesn't leak anything.

Also I don't understand why $$a=(p-1)$$, $$g^a\bmod p=1$$ and at the same time we have $$g^q\bmod p=1$$.

Well, we have $$a = 2q$$, and so (because $$g$$ is of order $$q$$), we have $$g^a = g^{2q} = (g^q)^2 = 1^2 = 1 \pmod{p}$$, and so, yes, we have $$g^a = g^q \pmod{p}$$.

• generator=2 is not a DH group generator? But only a generator of a subgroup, where only quadratic residues are? Commented Jul 16 at 18:56
• @ojacomarket: that is correct; $2$ (with this $p$) is a quadratic residue, and so it generates the subgroup of quadratic residues (which is of size $q$) Commented Jul 16 at 19:02