Patent ID: 6778666
Filing Date: 2004-08-17
Classification: H04L

Abstract:
A method used in constructing an elliptic curve cryptosystem with an underlying field Fp of characteristic p, the method using a computer system and comprising the steps of:(a) selecting a predetermined value of CM discriminant D; (b) constructing a prime p such that a decomposition of p=a2+Db2, where the values of a and b are integers; (c) generating an elliptic curve utilizing said CM discriminant D, said elliptic curve having the equation y2=x3+Ax+B where A and B are integers; (d) computing possible numbers of points Ni on said elliptic curve; (e) computing maximal prime divisors qi for the computed numbers of points Ni; (f) selecting a maximum value from the computed prime divisors qi which satisfies predetermined security requirements as an elliptic curve order q and selecting the corresponding N number of points; (g) selecting coefficients A and B for said elliptic curve equation such that the elliptic curve has N number of points and elliptic curve order of q; (h) determining whether the elliptic curve has a non-zero discriminant; (i) selecting a point Q on said elliptic curve as an initial group generator if the elliptic curve is determined to have a non-zero discriminant in step (h) such that the order of the point Q equals the elliptic curve order q; and (j) outputting parameters p, A, B, N, q, and Q to construct the elliptic curve cryptosystem.