1
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ "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??? $\endgroup$
    – poncho
    Commented Nov 14, 2016 at 20:58

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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) $\endgroup$
    – poncho
    Commented Nov 14, 2016 at 20:53
  • $\begingroup$ 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. $\endgroup$
    – kub0x
    Commented Nov 14, 2016 at 21:03
  • $\begingroup$ Wait, for every safe prime $q$, you can use $g=2$ as a generator? $\endgroup$
    – user66875
    Commented Nov 16, 2016 at 7:54
  • $\begingroup$ 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. $\endgroup$
    – kub0x
    Commented Nov 16, 2016 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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