Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.


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;

share|improve this question

1 Answer 1

up vote 2 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 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.

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
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
1  
probably you should add last comment to your answer. Thank you. –  ted May 5 '12 at 12:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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