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

2. 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?

P.S.
Thank you and sorry for my English;

-

## 1 Answer

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 May 4 '12 at 5:34

1
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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 14, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9147490859031677, "perplexity_flag": "middle"}