# 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 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?

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.
• 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 May 4 '12 at 12:46