0
$\begingroup$

I have found some contradicting answers regarding finding a safe 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++){
        group.add((g**i)%p)
    }
    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?

$\endgroup$
3
  • $\begingroup$ Why don't you comment on this under the answer instead of accepting it? $\endgroup$ – kelalaka May 24 '20 at 19:37
  • $\begingroup$ to which of the answers? @kelalaka $\endgroup$ – Jonas Grønbek May 24 '20 at 19:38
  • $\begingroup$ 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. $\endgroup$ – kelalaka May 24 '20 at 19:45
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

This contradicts an answer

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.