2
$\begingroup$

First step in DH & ECDH is to choose a random prime $p$. Then you choose a generator $g$ for the group $\mathbb Z_p^*$. How do you find a generator? Likewise in ECDH, you would need to find a generator which generates all the points in the elliptic curve? How is this done?

$\endgroup$
9
  • 2
    $\begingroup$ These are different questions since the groups are different. This dupe for the second question. Is every point on an elliptic curve of a prime order group a generator?. And this for the first from math: How to find a generator of a cyclic group. Or, are you asking how the standards chose the base points? For example, Curve25519 chooses the first $x$ satisfying the equation. $\endgroup$
    – kelalaka
    Jan 29 at 12:07
  • 1
    $\begingroup$ The question is a dupe of How to find generator g in a cyclic group?, except that the body of that other one implicitly restricts to $\mathbb Z_p^*$. $\endgroup$
    – fgrieu
    Jan 29 at 12:12
  • $\begingroup$ You don't need a generator of the whole group, only a sufficiently large subgroup. For $Z_p^*$ the group order is always even thus composite, so it is common to use a generator with order $(p-1)/2$ at most and sometimes less. For the NIST/X9 curves over $F_p$ fields the curve order is prime, but not for the less-used $F_{2^m}$ fields nor the more-used Bernstein curves 25519 and 448. $\endgroup$ Jan 30 at 1:16
  • $\begingroup$ @kelalaka - I did not understand the answer to the linked elliptic curve question. He says that every element in a group of prime order is a generator of the group. This is true, but is it relevant? Any description of ECDH I have read doesn't say that you choose an elliptic curve group of prime order $\endgroup$
    – user93353
    Jan 30 at 1:19
  • $\begingroup$ @kelalaka - ` Or, are you asking how the standards chose the base points?` - do the standards specific what is the generator for any group used for PKI? Is this only for ECDH or even for DH? $\endgroup$
    – user93353
    Jan 30 at 1:21
4
$\begingroup$

In the case of Diffie-Hellman Key Exchange (DHKE or DH) in the multiplicative group $\mathbb Z_p^*$, the recommendable practice is to pick a prime $p$ and generator $g$ from RFC 3526, which gives these parameters for bit size $k$ of $p$ in $\{1536,2048,3072,4096,6144,8192\}$. These $(p,g)$ obey the criterion below:

  1. $p$ is a prime such that $q=(p-1)/2$ is prime, that is $p$ a safe prime. Since the order of an element $g$ of the group is a divisor of $p-1$, that order can only be $1$, $2$, $q$, or $2\,q$, which simplifies finding¹/checking the order of a candidate $g$:

    • If $g\bmod p=1$, then the order of $g$ is $1$.
    • If $g\bmod p=p-1$, then the order of $g$ is $2$.
    • If $g^q\bmod p=1$, then the order of $g$ is $q$, half the group order. Such $g$ are used in RFC 3526.
    • Otherwise (that is if $g^q\bmod p=p-1$ ), the order of $g$ is $2\,q$, that is $g$ is a generator of the whole group. There is no good reason to prefer such $g$, and they have the drawback that given $a=g^x\bmod p$, it's trivial to tell if $x$ is even or odd by checking if $a^q\bmod p$ is $1$ or not.
  2. It is picked $g=2$, because

  3. The low-order 64 bits of $p$ are set. This can be used to simplify Montgomery modular multiplication. Combined with (1) and $p>7$, that implies $p\bmod24=23$, and the order of $g=2$ is $q$. Notably, that goes against a check in OpenSSL.

  4. The high-order 66 bits of $p$ are set, making $p$ near a power of two. This can be used to simplify modular reduction modulo $p$, by making it easy to find a most likely correct new digit/limb for the quotient in Euclidean division in base $2^b$ for $b\le32$ (and somewhat higher).

  5. The next high-order bit of $p$ is clear, making $p$ not so close to a power of two that the Special Number Field Sieve applies.

  6. The other bits make $p$ a nothing-up-my-sleeves number: for a $k$-bit modulus, it is used $p=2^k-2^{k-64}-1+2^{64}\,\left\lfloor2^{k-130}\pi+i\right\rfloor$ with the smallest $i$ such that $p\bmod3=2$ [which for a given $k$ determines $i\bmod 3$ ], $p$ is prime, $q=(p-1)/2$ is prime, and $2^q\bmod p=1$.

Of course, $k$ is chosen as a compromise between speed and security of DH. $k=2048$ is considered a minimum today. Message size grows as $k$. Execution time grows as $k^3$ in naive implementations of DH using textbook multiplication and secrets the size of $p$. While performance can be considerably improved by using better multiplication algorithms, and smaller secrets, DH in $\mathbb Z_p$ with secure-enough parameters is outperformed by a competent implementation of ECDH, see next section.

Note: An alternative practice, with no direct benefic in DH but common in signature because it allows a drastic reduction in signature size, is to use $(p,g)$ making the powers of $g$ modulo $p$ a Schnorr Group of order a prime $q$ of size much smaller than $p$, yet enough for security. We first choose prime $q$ with about twice as many bits as the desired security level, and $p=2\,q\,r+1$ for (even) $r$ making $p$ a prime of suitable size (e.g. 256-bit $q$, 3072-bit $p$). We pick some $h$ (e.g. $h=2$), compute $g\gets h^r\bmod p$, and check that does not happen to be $1$.


In the case of ECDH, that is DH in the group of points of an Elliptic Curve over some finite field $\mathbb F_{p^d}$ for prime $p$, the recommendable practice is to pick a standard curve and generator from some reference. A common one is SEC2, which includes the NIST curves of FIPS 186-4. Another is Curve25519. Yet another is RFC 5639, which gives the Brainpool curves.

Restricting to $d=1$ (that is curves on $\mathbb F_p$ for some large prime $p$, though not as large as needed for security of DH in the group $\mathbb Z_p^*$ ), practice is to use curves of prime order $q$, such that any point except the neutral $\infty$ has order $q$. It's proven that the choice of generator (aka base point) does not make the discrete logarithm problem much easier. How the generator is actually chosen varies. Sometime it's secret, lost, rediscovered, see this.

When we can't or didn't chose the curve to be of prime order, practice it to use a curve of known order of the form $h\,q$ where $q$ is prime and $h$ is as small as possible. This makes it easy to check the order of a point, and ascertain it's a multiple of $q$ (or exactly $q$, which is typical).

How a curve's order is found (aka point counting) is quite involved. That's one good reason why we have standard curves.


¹ A general method to find the order $i$ of an arbitrary $g$ in $\mathbb Z_p^*$ with $p$ prime is to test $i$ in increasing order among the divisors of $p-1$ (the order of such $\mathbb Z_p^*$ ), and stop at the first $i$ with $g^i\bmod p=1$. This generalizes to any group, and is applicable when we know the factorization of the group order.

$\endgroup$
2
  • $\begingroup$ Wow! This is a fantastic answer. Thank you very much! $\endgroup$
    – user93353
    Jan 30 at 10:40
  • 1
    $\begingroup$ One note on point 2; because $p \equiv 7 \pmod 8$ for all the RFC 3526 modulii, $g=2$ always has order $q$; this means that the lsbit of the exponents will not be leaked. $\endgroup$
    – poncho
    Jan 30 at 15:09

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.