Elliptic curves for ECDSA

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?

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 3.1.3.2 "Point Selection" in SEC1v2, where it computes a generator from a seed $S$. It is more convoluted since it generates points verifiably at random.

• where n is ?.. Though the real problem is to find a point with a prime order.
– ted
Commented May 4, 2012 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$. Commented May 4, 2012 at 12:46