I want to make a Diffie Hellman key exchange code using Python, but I'm afraid of just randomly picking $g$.

I read on the answer of Thomas Pornin to this question How does one calculate a primitive root for Diffie-Hellman?, that if you use a strong prime, then every number on the group (except $1$ and $p-1$) would have an order of either $p-1$ or $\frac{p-1}{2}$, but I can't find anywhere online a list of big strong primes to use. Anyone knows where can I find one?

Edit: thanks for the generous help of fgrieu I realized I am looking for safe primes, and not strong primes.

  • $\begingroup$ Yes; I hopefully clarified that in my answer. You might want to remove obsolete comment (if you can, can't tell). $\endgroup$ – fgrieu Mar 25 '20 at 18:43

In cryptography, strong primes have been used (with various definitions of that) for RSA, in order to defeat the factorization of the public modulus by Pollard's p-1 and p+1 algorithms, and various other attacks. For this reason, there is no list of standard large strong primes, for that would defeat the purpose in RSA, where the prime factors of the public modulus must be secret.

The Diffie-Hellman key exchange often uses safe primes, which is a prime $p$ such that $\displaystyle q=\frac{p−1}2$ is also a prime. The answer linked to in the question accidentally misuses the word strong prime where safe prime is meant, as noted in comment.

Standard safe primes for use in DH are in RFC 3526. These intentionally use the generator $g=2$ for the subgroup of prime order $\displaystyle q=\frac{p−1}2$. Except perhaps for the 1536-bit one, they are considered large enough to be safe for use right now.

With (safe prime $p$), can I use any number between $2$ and $p−2$ and be guaranteed to have an order of either $p−1$ or $\displaystyle\frac{p−1}2$ ?

Yes. Argument: the order of a subgroup always divides the order of the group, which is $p-1$ for prime $p$. When further $p$ is a safe prime, the order of the group is $2\,q$ with $q$ prime, thus the order of any $g$ is one of $1$, $2$, $q$ or $2q$. Only $1$ has order $1$ and only $p-1$ has order $2$.

But as noted in comment, there is no good reason not to use the generator coming with the prime.

  • $\begingroup$ Thanks a lot for the help so far, last question, with the 6 primes on this link, can I use any number between $2$ and $p-2$ and be guranteed to have an order of either $p-1$ or $\frac{p-1}{2}$ (because I don't want to reuse the same g even if it's a generator, but I want to make sure that every g I pick will be fine for diffie hellman)? $\endgroup$ – Ofek Tevet Mar 25 '20 at 18:47
  • 2
    $\begingroup$ @OfekTevet: why don't you want to reuse $g$ values? What value do you see in changing it? It is known that if you can solve the CDH problem with one $g$ (in either the $p-1$ or $(p-1)/2$ subgroups), you can solve it for any generator... $\endgroup$ – poncho Mar 25 '20 at 18:54
  • 1
    $\begingroup$ Well if you all say I can always use the generator, I will, thanks for the link and the help. $\endgroup$ – Ofek Tevet Mar 26 '20 at 9:49

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.