# Diffie-Hellman should size of group be a prime?

When p is a "safe prime", this means that $$(p−1)/2$$ is also prime. We then define $$q=(p−1)2$$. In that situation, the order of any non-zero $$g\mod p$$ (except 1 and p−1) is either $$q$$ or $$2q$$

If it can produce a group of size $$2q$$ then the groups length is by definition not a prime.

Okay, so following this theory, 83 should be regarded as a safe prime.

$$(83-1)/2=41$$ and $$41$$ is a prime.

The length of the subgroup produced by $$2 \mod 83$$ is $$82$$. (can you phrase it like that? Even though it refers to a set/group of congruences by $$2^{1..p-1} \mod p$$?

I can prove it with a little program

const groupSize = (p, g) => {
const group = new Set()
for(let i = BigInt(0); i < p-BigInt(1); i++){
}
console.log(group.size)
}
groupSize(BigInt(83), BigInt(2))


output: 82

This contradicts an answer to one of my previous questions regarding choosing a safe prime.

If h is a factor of the size of the group generated by g, then given $$g^x\mod p$$, we can compute $$h\mod n$$ in $$O(\sqrt h)$$ time. If g generates the entire group, well, its size will be $$p−1$$, which always has a factor of 2 (assuming $$p>2$$), and so we'd be giving away $$x\mod 2$$ for free.

Diffie-Hellman what is the subgroup

This makes me believe that the group cannot be an even number, since it is then a factor of 2?

• Why don't you comment on this under the answer instead of accepting it? May 24 '20 at 19:37
• to which of the answers? @kelalaka May 24 '20 at 19:38
• Whichever one you quoted. A good question should provide the links. Who does know where you take them. 41 is the safe prime 23 is the Sophie Germain prime. May 24 '20 at 19:45

The length of the subgroup produced by $$2\pmod{83}$$ is $$82$$. Can you phrase it like that?

That would be unusual. At least, "length" should be size (cardinality would be very formal). I would use something on the tunes of:

• the order of the multiplicative subgroup generated by $$2$$ modulo $$83$$ is $$82$$.
• $$2$$ has order $$82$$, modulo $$83$$.

The previous answer suggests not to choose $$g=2$$, because it generates the entire multiplicative subgroup $$\Bbb Z_{83}^*$$, that is the set $$[1,83)$$ under multiplication modulo $$83$$, of order $$82$$. Thus (as explained), with $$g=2$$, giving $$y=g^x\bmod 83$$ leaks if $$x$$ is even or odd: just compute $$y^{41}\bmod83$$, and that's $$1$$ if and only if $$x$$ is even.

Instead, we can use $$g=3$$, which has order $$41$$. Or, as pointed in the other answer, $$g=4$$ which always has prime order if $$p$$ and $$q=(p-1)/2$$ are prime.

In what sense do they contradict?

The first one states that, for a safe prime, we have subgroups of size $$q$$ and $$2q$$.

The second one states that we typically use a $$g$$ that generates a subgroup whose size is a prime.

These two statements do not contradict each other; combined, that would mean that (to follow both) we select a $$g$$ that generates a subgroup of size $$q$$. This is always possible (in fact, $$g=4$$ is always such a generator).

Your computations show that, for $$p=83$$, then $$g=2$$ is not such a generator. What that means is that, to follow the advise of the second statement, you'd pick a different generator (and, in fact, $$g=3$$ works, that is, generates a subgroup of size $$q$$, for $$p=83$$)

• I wish I had the privilege to see who's busy writing an answer, so that I don't :-)
– fgrieu
May 24 '20 at 20:41
• Thanks again, this clears my confusion :) May 24 '20 at 20:44