Method and device for constructing elliptic curves

An elliptic curve application device that uses elliptic curves, comprising

• elliptic curve construction means for determining parameters of an elliptic curve E which is defined over a finite field GF(p) and offers a high level of security, p being a prime,
• wherein the elliptic curve constructing means includes an elliptic curve construction device which includes
• random number generating means for generating a random number;
• parameter generating means for selecting the parameters of the elliptic curve E
• using the generated random number, in such a manner that a probability of a discriminant of the elliptic curve E having any square factor is lower than a predetermined threshold value;
• finitude judging means for judging whether the elliptic curve E defined by the selected parameters has any point whose order is finite on a rational number field;
• order computer means for computing an order m of the elliptic curve E when the finitude judging means judges that the elliptic curve E does not have any point whose order is finite on the rational number field;
• security judging means for judging whether a condition that the computed order m is a prime not equal to the prime p is satisfied;
• repeat controlling means for controlling the random number generating means, the parameter generating means, the finitude judging means, the order computing means, and the security judging means respectively to repeat random number generation, parameter selection, finitude judgment, order computation, and security judgment until the condition is satisfied;
• and
• parameter outputting means for outputting the selected parameters when the condition is satisfied.

An elliptic curve construction method used in an elliptic curve construction device equipped with random number generating means, parameter generating means, finitude judging means, order computing means, security judging means, repeat controlling means, and parameter outputting means, for determining parameters of an elliptic curve E which is defined over a finite field GF(p) and offers a high level of security, p being a prime, the elliptic curve construction method comprising:

• a random number generating step performed by the random number generating means, for generating a random number;
• a parameter generating step performed by the parameter generating means, for selecting the parameters of the elliptic curve E using the generated random number, in such a manner that a probability of a discriminant of the elliptic curve E having any square factor is lower than a predetermined threshold value;
• a finitude judging step performed by the finitude judging means, for judging whether the elliptic curve E defined by the selected parameters has any point whose order is finite on a rational number field;
• an order computing step performed by the order computer means, for computing an order m of the elliptic curve E when the finitude judging step judges that the elliptic curve E does not have any point whose order is finite on the rational number field;
• a security judging step performed by the security judging means, for judging whether a condition that the computed order m is a prime not equal to the prime P is satisfied;
• a repeat controlling step performed by the repeat controlling means, for controlling the random number generating step, the parameter generating step, the finitude judging step, the order computing step, and the security judging step respectively to repeat random number generation, parameter selection, finitude judgement, order computation, and security judgement until the condition is satisfied;
• and
• a parameter outputting step performed by the parameter outputting means for outputting the selected parameters when the condition is satisfied.

A computer-readable storage medium storing an elliptic curve construction program used in an elliptic curve construction device equipped with random number generating means, parameter generating means, finitude judging means, order computing means, security judging means, repeat controlling means, and parameter outputting means, for determining parameters of an elliptic curve E which is defined over a finite field GF(p) and offers a high level of security, p being a prime, the elliptic curve construction program comprising:

• a random number generating step performed by the random number generating means, for generating a random number;
• a parameter generating step performed by the parameter generating means, for selecting the parameters of the elliptic curve E using the generated random number, in such a manner that a probability of a discriminant of the elliptic curve E having any square factor is lower than a predetermined threshold value;
• a finitude judging step performed by the finitude judging means, for judging whether the elliptic curve E defined by the selected parameters has any point whose order is finite on a rational number field;
• an order computing step performed by the order computer means, for computing an order m of the elliptic curve E when the finitude judging step judges that the elliptic curve E does not have any point whose order is finite on the rational number field;
• a security judging step performed by the security judging means, for judging whether a condition that the computed order m is a prime not equal to the prime p is satisfied;
• a repeat controlling step performed by the repeat controlling means for controlling the random number generating step, the parameter generating step, the finitude judging step, the order computing step, and the security judging step respectively to repeat random number generation, parameter selection, finitude judgement, order computation, and security judgement until the condition is satisfied;
• and
• a parameter outputting step performed by the parameter outputting means for outputting the selected parameters when the condition is satisfied.

An elliptic curve construction apparatus for determining parameters of an elliptic curve E which is defined over a finite field GF(p) and offers a high level of security, p being a prime, the elliptic curve construction apparatus comprising:

• random number generating unit for generating a random number;
• parameter generating unit for selecting the parameters of the elliptic curve E using the generated random number, in such a manner that a probability of a discriminant of the elliptic curve E having any square factor is lower than a predetermined threshold value;
• finitude judging unit for judging whether the elliptic curve E defined by the selected parameters has any point whose order is finite on a rational number field;
• order computer unit for computing an order m of the elliptic curve E when the finitude judging unit judges that the elliptic curve E does not have any point whose order is finite on the rational number field;
• security judging unit for judging whether a condition that the computed order m is a prime not equal to the prime p is satisfied;
• repeat controlling unit for controlling the random number generating unit, the parameter generating unit, the finitude judging unit, the order computing unit, and the security judging unit respectively to repeat random number generation, parameter selection, finitude judgement, order computation, and security judgement until the condition is satisfied;
• and
• parameter outputting unit for outputting the selected parameters when the condition is satisfied.