1. I want to generate a random elliptic curve over a prime field. What are the conditions I should satisfy?

  2. For the NIST recommended standard ECC-224 bit curve with prime $p=2^{224}-2^{96}+1$, a reduction technique is given by $(z_1+z_2+z_3-z_4-z_5) \bmod{p}$, what is the logic behind in this?

  • $\begingroup$ Just checking, you want to generate a curve or a point on a curve? A curve over a finite field or infinite or either? $\endgroup$ – mikeazo Feb 28 '13 at 14:04
  • $\begingroup$ i want to generate a random curve over prime field... $\endgroup$ – venkat Mar 1 '13 at 15:43
  • $\begingroup$ I don't understand question #2 at all. Can you help me understand? $\endgroup$ – mikeazo Mar 1 '13 at 15:59
  • $\begingroup$ NIST recommended standard ECC-224 bit, prime value is 2^224-2^96+1. 224 bit * 224 bit multiplication results 448 bit output. which can be converted back over field 224 bit, NIST standard has given one formula ((z1+z2+z3-z4-z5) mod prime )). what is mathematical logic beind in this formula. $\endgroup$ – venkat Mar 2 '13 at 14:36
  • $\begingroup$ I have updated the question to make #2 a little better. Can you make sure I didn't change the meaning? Also, what are the $z$ values? $\endgroup$ – mikeazo Mar 3 '13 at 13:43

There are several conditions that might need to be satisfied, depending on your needs. At a bare minimum the curve you generate needs to have a large prime subgroup. To determine this one can use any number of point counting algorithms, or alternatively use the complex multiplication method to generate a curve with the desired number of points.

Beyond large prime subgroup you may also want the twist to have a large prime subgroup to avoid attacks based on sending points on the twist. Point validation is another way to avoid them.

Sometimes a specific cofactor is required for certain parametrizations of the curve that can lead to more efficient calculations.

For details you can see DJB's analysis of his choices for Curve25519, as well as papers cited by the Explicit Formula Database. http://hyperelliptic.org/EFD/bib.html


Baring other requirements that you did not explain:

An elliptic curve can be written as $y^2=x^3+ax+b$. To generate a random curve over a prime field, choose $a,b$ at random from the prime field.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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