8
$\begingroup$

I was looking out to find optimum generator for an elliptic curve $E$ over a prime field $\mathbb F_p$. I found the following algorithm:

  1. Choose random point $P$ on the curve.
  2. Find the order of a generator $\ell$.
  3. Calculate the number of points $n=\#E(\mathbb F_p)$.
  4. Calculate the cofactor $h=n/\ell$.
  5. Calculate a generator as $G=[h]P$.

Here I can find $n=\#E(\mathbb F_p)$ using Schoof's algorithm. I need to find $\ell$. How is that possible? How can I find the order of a generator/base point of an elliptic curve defined over a prime field?

$\endgroup$
  • 1
    $\begingroup$ This might help: how to find a primitive point on an elliptic curve $\endgroup$ – baconSoda Feb 22 '17 at 4:21
  • 1
    $\begingroup$ For cryptographic purposes, the group order should be prime. This means, you should use the subgroup of E with the biggest prime order. That implies that your randomly chosen point P may not be optimal. I would suggest the following algorithm: First factor #E and choose the biggest prime factor q. Then choose random points P until one of it satisfies P*q = 0. $\endgroup$ – user27950 Feb 22 '17 at 5:55
  • $\begingroup$ I'm voting to close this question as off-topic because it is about general mathematics. $\endgroup$ – fkraiem Feb 22 '17 at 6:34
  • 5
    $\begingroup$ @fkraiem: As a mathematician, you can surely give me an exact definition what question refers to cryptography and what to general mathematics ;-) $\endgroup$ – user27950 Feb 22 '17 at 11:54
6
$\begingroup$

Due to the Pohlig-Hellman algorithm, the hardness of discrete logarithms is dominated by the largest prime factor $\ell$ of the group order $n$. In particular, one typically works in a subgroup of order $\ell$ of the curve group, since the additional factors $h$ in a generator's order would not significantly contribute to security.

In that, note that $\ell$ depends on the group order $n$: You cannot just decide for some order $\ell$ and then find a point $G$ of that order on an arbitrary fixed curve, since it general such a point will not exist. (However, there is the complex multiplication method, which generates a new curve of given order.) Therefore, steps 2 and 3 of the algorithm given in the question must be swapped: You first compute the curve group order $n$, factor it, and determine $\ell$ from the factorization. (And if $\ell$ is too small, you should start over with a new curve. For example, Curve25519 has cofactor $h=8$.)

Other than that, the algorithm is fine, except that you might want to check whether $G=\infty$ and start over in that case. However, this only happens with probability $1/\ell$, so it should never occur in practice for cryptographically-sized curves. (Moreover, you would compute and factor the group order only once and find a good $P$ afterwards, but this does not impact the expected runtime much as $P$ usually is good at the first try.)

Thus, we have the following algorithm:

  1. Compute the curve order $n=\#E(\mathbb F_p)$.
  2. Factor $n$ to determine its largest prime factor $\ell$. (Note that you do not need to fully factor $n$: If the remainder after removing a few "small" divisors is not prime, the cofactor is going to be too big anyway.)
  3. Compute the cofactor $h=n/\ell$. If $h$ is "too big", start over with a new curve.
  4. Choose a random point $P\in E(\mathbb F_p)$ and let $G=[h]P$.
  5. If $G$ is the point at infinity, go back to choosing a new $P$. Else, $G$ has order $\ell$.
$\endgroup$
  • $\begingroup$ Doesn't Pohlig-Hellman only apply to multiplicative groups? $\endgroup$ – user13741 Feb 22 '17 at 19:15
  • 1
    $\begingroup$ @user13741 No, Wikipedia is wrong in this respect (and it has long been on my to-do list to improve that article). The algorithm applies to any finite abelian group, as long as a factorization of the group order is known. $\endgroup$ – yyyyyyy Feb 22 '17 at 20:23

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.