2
$\begingroup$

For DH key agreement, one must begin with a generator of a cyclic group g.

However, intuitively to me at least, it seems that g may be expensive to calculate for a random cyclic group mod some large prime p.

How is this done efficiently on the fly for Diffie Hellman?

Probably this is naive, however it would seem one must check each element of the group to test it's generative properties...

$\endgroup$

1 Answer 1

4
$\begingroup$

How is this done efficiently on the fly for Diffie Hellman?

For Finite-Field Diffie-Hellman, you usually pick $p$ such that $q=(p-1)/2$ is also prime. Now Lagrange's theorem tells us that every element's order must divide the group order which is $p-1=2q$. This leaves us with four divisors: $1,2,q,2q$. Once you know that, you can simply test that your chosen candidate $g$ doesn't have order $1$ nor $2$ which you can test by checking that $g^2\neq 1\pmod p$. If you now explicitly want either of the other two orders you can test whether $g^q=1\pmod p$ and if yes you have a generator of order $q$ and if not then it has order $2q$. As to whether we can actually find the two interesting cases, Sylow's theorems guarantee this and usually you would start with $g=2$ and count up until you have a suitable candidate.

$\endgroup$
1
  • 2
    $\begingroup$ Alternatively, if $p, (p-1)/2$ are both prime, you can just pick a random $h$ and set $g = h^2 \pmod p$; if $g \ne 1$, then it will always have order $q$. On the third hand, you can have $p, (p-1)/2$ prime and $p \equiv 7 \pmod 8$; in that case, $g=2$ always has order $q$. $\endgroup$
    – poncho
    Nov 14, 2019 at 15:39

Your Answer

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

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