I want to generate a random elliptic curve over a prime field. What are the conditions I should satisfy?
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?
Tell me more
×
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.
|
|
|||||||||||
|
|
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. |
||||
|
|
