Generating Diffie-Hellman parameters

I'm trying to implement a diffie-hellman key exchange in c++, and I'm struggling with my missing understanding of math / group theory. Let's say I found a large prime number p - how can I find a generator g?

Restricted by the multiprecision library that I have to use, only a few basic operations (+, *, -, /, pow, modExp, modMult, mod, gcd, isProbablyPrime, genRandomBits, and a few more) are available.

I read that in a cyclic finite group $Z_q$ where $q$ is a safe prime, every element is a generator of that group. So I assume I should start by generating a safe prime $q$ first:

Pseudocode:

// find a safe prime q
WHILE NOT isProbablyPrime(q)
WHILE NOT isProbablyPrime(p)
p = genRandomBits(1024)
q = 2*p+1

But how do I now find a generator for $Z_q$?

• "I'm struggling with my missing understanding of math / group theory"; if you don't know the basics, might I suggest you rely on a standard library (such as OpenSSL), rather than trying to hack something together yourself??? Nov 14 '16 at 20:58

Just stick to the standard algorithm, also remember that you are working in $\mathbb{Z}_p^*$.
Select $q$ with at least $2k$ bits, that means you are targeting $k$ bits security. In the RFC at least 160 bits is recommended for $q$. In addition select a prime $p$ with at least 1024-bit.
Regarding the generator, we know that every generator will generate the subgroup of order $2q$ or $q$. The reason that $g=2$ is chosen is that is desirable for faster computations of modular exponentiation.
You will find all the information regarded to Diffie-Hellman implementation in RFC. Also there's a method for generating $p$,$q$ and alternatively $g$, if desired.
• This answer is more likely to confuse kevwasd than inform him. "Select $q$ with at least $2k$ bits...", that might be decent advice if he were using a small subgroup; it doesn't make much sense for a safe prime (where $q$ needs to be much larger). And, I'm not sure what you mean by multiplying $\log_2(k)$ by $\log_2(q)$; adding them might make more sense (but is off topic for safe primes) Nov 14 '16 at 20:53
• I agree with you in that the answer can confuse the user. $q$ just needs to have at least 160bits, that's why I mention 2k-bit security. Regarding the logarithmic expression, $p$ needs 1024 bits and due that it's been obtained by $(k.q+1)$ then it depends on the multiplication of $k$ and $q$ bits. However, I'm going to remove that expression. Nov 14 '16 at 21:03
• Wait, for every safe prime $q$, you can use $g=2$ as a generator? Nov 16 '16 at 7:54
• The safe prime is $p$ being $p=2q+1$. $g=2$ is a generator since the order of the subgroup generated by $g$ is $p-1=2q$ or a prime factor of $2q$. Thus $q$ will be its order. Summarizing, yes it will be a generator. Nov 16 '16 at 15:01