I'm trying to implement parameters generation for ECDSA according to SEC1 v2.0:

Input: The approximate security level in bits = t is {80, 112, 128, 192, 256}  
 Output: Elliptic curve domain parameters over Fp: T = (p, a, b, G, n, h)

Here's the 2nd step of the algorithm:

  1. Select elements $(a, b)$ is $F_p$ to determine the elliptic curve $E(F_p)$ defined by the equation:

$E : y^2 = x^3 + ax + b \bmod p$,

a base point $G = (G_x, G_y)$ on $E(F_p)$, a prime $n$ which is the order of $G$, and an integer $h$ which is the cofactor $h = E(F_p)/n$, subject to the following constraints:

  • $4a^3 + 27b^2 \neq 0 \bmod p$
  • $E(Fp) \neq p$.

  • $p^B \neq 1 \bmod n \space\forall\space 1 <= B < 100$
  • $h <= 2 ^{(t/8)}$
  • $n−1$ and $n+1$ should each have a large prime factor $r$, which is large in the sense that $log_n(r) > (19/20)$.

I haven't understood a lot of things in 2nd step.

  1. How to select a and b for E(Fp)? Should it be done randomly just to satisfy 4a^3 + 27b^2 != 0(mod p) ? Yes it should, as far as i've understood.
  2. How to find #E(Fp) -- the cardinality of E(Fp)? -- Schoof or SEA algorithm.
  3. How to choose generator -- $G = (G_x, G_y)$ and find its order $n$? -- Random point should be chosen on a curve. Again not pretty sure about it.
    EDIT: The point has to have a prime order. How can a point be chosen with a prime order?

1 Answer 1


It is easier to generate a point with order $n$ than to find out the order of a random point:

  • Generate a random point $G'$ (generate random $x$ and solve for $y$)
  • Compute $G = hG'$ (multiply by cofactor)

This is guaranteed to generate a point $G$ with order either $n$ or $1$ (the point at infinity). The chance of generating the point at infinity is negligible, but you can check for it and regenerate $G$ if you want.

This procedure is described in section "Point Selection" in SEC1v2, where it computes a generator from a seed $S$. It is more convoluted since it generates points verifiably at random.

  • $\begingroup$ where n is ?.. Though the real problem is to find a point with a prime order. $\endgroup$
    – ted
    Commented May 4, 2012 at 5:34
  • 2
    $\begingroup$ You can find $n$ by factoring the order of the curve, which you have found with e.g. Schoof's algorithm. Then $n$ will be the largest factor, and $h$ is the order divided by $n$. $\endgroup$
    – Conrado
    Commented May 4, 2012 at 12:46
  • 2
    $\begingroup$ probably you should add last comment to your answer. Thank you. $\endgroup$
    – ted
    Commented May 5, 2012 at 12:14

Your Answer

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

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