Generating Diffie-hellman parameters (generator)

Question

I'm trying to implement a diffie-hellman key exchange. 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, isPrime, genRandomPrime, genRandomBits, and a few more) are available.

Would it work to look for a safe prime q, so that every number n for which gcd(n,q) == 1 should be a generator, right?

Answer 1

You basically answered your question. Just the test gcd(n,q)==1 is not necessary since q is prime. It means that any number n, such that n < q does not have common factor with q and gcd(n,q) will always output 1.

You can check whether q=2p + 1 is prime number. If so, then ord(Zq) = q-1 = (2p+1)-1 = 2p. Since ord(x) | ord(Zq) for every x in Zq ord(x)=2 or ord(x)=p or ord(x)=2p. Thus you just need to check whether your randomly chosen element x from {2,...,q-1} is of order 2. If not then it is of order p or 2p and you can use it as a generator.

Answer 2

As a rule, don't ask programmers questions about cryptography. Cryptography is subtle and, as a result, difficult in invisible ways that lead readily to self-deception about one's own competence. Instead, ask cryptographers (many of which are also programmers). Stack Exchange has a cryptography board, where this question has already been answered.

https://crypto.stackexchange.com/questions/29926/what-diffie-hellman-parameters-should-i-use

I could quibble with the advice there, but it's basically sound. Unless you really want to learn the relevant mathematics, I'd defer to authorities; they're cited in the answer above.

As to the mathematics question you ask, here's a tiny introduction. The multiplicative group modulo a prime p has size p-1. (See Fermat's Little Theorem.) The order of any element must divide p-1. The most favorable case is where p-1=2q, where q is also prime.