1
$\begingroup$

Hi I previously asked a question about Diffie-Hellman parameters but wanted to make sure I got it right.

I need to generate parameters for the SRP protocol. My base strategy is to generate a safe prime q = 2*p + 1 where p is also a prime. I want to use as low generator as possible, preferably "2". Now, all elements of (Z/qZ) is going to have one of the following orders: 1, 2, p or 2*p due to the group having order 2*p, so 2 must generate a subgroup of one of those orders. Since q is large, we can exclude 1 and 2 as possibilities, leaving p and 2*p as the only possible orders of the subgroup. It can be easily determined which it is by simply checking if 2^p = 1 mod q.

Now my question is, which is cryptographically preferred for security against the discrete-log attack? I.e. is it preferred to select p and q such that 2 has order p, or is 2*p preferable? 2*p clearly implies a subgroup twice as big. On the other hand, p is prime. I don't know if there's any special benefit to the subgroup itself having prime order.

$\endgroup$
  • $\begingroup$ BTW: if you select your strong prime $q \equiv 3 \pmod 8$, then $g=2$ is guaranteed to be a primitive element... $\endgroup$ – poncho May 8 '17 at 17:19
2
$\begingroup$

For DH, whether the subgroup is of order $p$ and $2p$ isn't that big of a deal; if it's $2p$, that means that the attacker can deduce one bit of the exponent; that's minimal. As for computing the discrete log, it's effectively equivalent; given an Oracle that can compute the DLog of an element of one order, you can (with one query) compute the DLog of an element of the other.

On the other hand, you're using SRP, and that changes things. For SRP, you MUST use a primitive element, that is, one with order $2p$. If you pick a proper subgroup; that is, a group for which random values in $Z_q$ have a nontrivial probability of not being in the group, the attacker can effectively eliminate many of the possiblities for the secret value from a single exchange; this is a violation of the SRP security policies.

If you want to generate SRP parameters, read the SRP specs; it tells you how to do it - it's important that you follow those (and actually, you're close; it mandates a safe prime;).

$\endgroup$

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.