# How do I find the order of the subgroup in a Diffie-Hellman key exchange?

I'm implementing the Diffie-Hellman key exchange as specified in RFC 4253 for SSH.

Here's an extract from the RFC:

The following steps are used to exchange a key. In this, C is the client; S is the server; p is a large safe prime; g is a generator for a subgroup of GF(p); q is the order of the subgroup; ...

The prime and generator to use are chosen based on the specific key exchange algorithm chosen (in the SSH sense, a key exchange algorithm includes the algorithm used, e.g Diffie Hellman, as well as the parameters for that algorithm, so not all Diffie Hellman based key exchange algorithms are the same). For example, diffie-hellman-group1-sha1 uses Oakley Group 2.

Checking the RFC that defines that group, I can find a clear definition of what the value of p should be (2^1024 - 2^960 - 1 + 2^64 * { [2^894 pi] + 129093 }) and of what the value of g should be (2). But I can't find what the value of q should be.

So, more generally, how can I compute q - the order of the subgroup - given p and g? Alternatively, if q is not meant to be trivially computable, where can I find a definition of what its value should be? I have looked at quite a few posts before writing this one, and all of them seem to imply that q is a well-known value, so I'm surprised that I haven't been able to find a clear defintion of it anywhere.

But I can't find what the value of q should be.

For that group, the size of the subgroup is $$q = (p-1)/2$$.

However, I do have these comments:

• That's a MODP group of size 1024 - that is currently considered too small (even though no discrete log over such a group has been publicly performed). When we use a MODP group, we typically use larger ones, such as the 2048 or larger ones from RFC 3526 (such as the 'diffie-hellman-group14-sha1' mentioned in RFC 4253). For those groups, we also have $$q = (p-1)/2$$.

• The SSH RFC 4253 says to select a random value $$x$$ from 1 to $$q-1$$; this turns out to be too conservative (that is, it makes the operation slower than necessary); selecting a value $$x$$ from 1 to (say) $$2^{256}$$ is sufficient - it yields good security, and makes the computation of $$g^x \bmod p$$ and $$pub^x \bmod p$$ (where $$pub = g^y \bmod p$$ is the other side's keyshare) quicker

So, more generally, how can I compute q

If you don't know the factorization of $$p-1$$, this can be a difficult problem. Fortunately, the SSH RFC specifies that $$p$$ is a 'safe prime', that is, a prime for which $$(p-1)/2$$ is also prime. With that, the size of the group generated (assuming a nonsilly $$g$$) is either $$p-1$$ or $$(p-1)/2$$ (and it's easy to tell which). Even easier, if $$g=2$$ and $$p \equiv 7 \bmod 8$$, then it will always be $$(p-1)/2$$