Take the 2-minute tour ×

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 Fp to determine the elliptic curve E(Fp) defined by the equation:

    E : y^2 = x^3 + ax + b (mod p),

    a base point G = (Gx, Gy) on E(Fp), a prime n which is the order of G, and an integer h which is the cofactor h = #E(Fp)/n, subject to the following constraints:

    • 4a^3 + 27b^2 != 0(mod p).
    • #E(Fp) != p.
    • p^B != 1(mod n) for all 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 = (Gx, Gy) 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?
share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
where n is ?.. Though the real problem is to find a point with a prime order. –  ted May 4 '12 at 5:34
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$. –  Conrado PLG May 4 '12 at 12:46
probably you should add last comment to your answer. Thank you. –  ted May 5 '12 at 12:14

Your Answer


