Secure parameter generating device and parameter generating method in algebraic curve crytography

Abstract

The Stickelberger element computing device computes a Stickelberger element ω in an ab cyclotomic; the Jacobian addition candidate value computing device computes the Jacobian addition candidate value j and a prime number p corresponding to the Jacobian addition candidate value j, based on the prime number a, the prime number b, the size n of an encryption key, and the Stickelberger elementω; the order candidate value computing device computes a class H consisting of a plurality of candidate values for the order of the Jacobian group of an algebraic curve, based on the prime number a, the prime number b, and the Jacobian addition candidate value j; the security judging device searches for a candidate value h meeting a security condition such as almost prime number characteristic from the class H; and the parameter deciding device computes a parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a, the prime number b, and the prime number p.

Claims

What is claimed is:

1. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0, comprising:

an input means for receiving two different prime numbers (a, b) specifying degree of complexity of a curve and size (n) of an encryption key to be used;

a Stickelberger element computing devices for computing a Stickelberger element (ω) in an ab cyclotomic, based on the prime number (a) and the prime number (b);

a Jacobian addition candidate value computing device for computing Jacobian addition candidate value j corresponding to the two different prime numbers a and b, and a prime number p corresponding to the Jacobian addition candidate value j, based on the prime number (a), the prime number (b), the size (n) of an encryption key, and the Stickelberger element (ω);

an order candidate value computing device for computing a class H consisting of a plurality of candidate values for order of a Jacobian group of an algebraic curve specified by the prime number a and the prime number b, based on the prime number a, the prime number b, and the Jacobian addition candidate value j;

a security judging device for searching for a candidate value h meeting a security condition such as almost prime number characteristic from the class H, according to the class H;

a parameter deciding device for computing a parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a, the prime number b, and the prime number p, based on the prime number a, the prime number b, the prime number p, and the candidate value h; and

an output device for supplying the parameter of the algebraic curve computed by said parameter deciding device to an algebraic curve cryptographic public key system.

2. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 1, further comprising:

an a-storing means, a b-storing means, and an n-storing means for respectively storing the prime number a, the prime number b, and the size n of the encryption key received by said input means;

a ω-storing means for storing a Stickelberger element ω computed by said Stickelberger element computing device;

a p-storing means and a i-storing means for respectively storing the prime number p and the Jacobian addition candidate value j computed by said Jacobian addition candidate value computing device;

an H-storing means for storing the class H computed by said order candidate value computing device; and

an h-storing means for storing the candidate value h found by said security judging device.

3. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 1, further comprising:

said Stickelberger element computing device for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, λ indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b.

4. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 1, further comprising:

said Jacobian addition candidate value computing device for generating α at random, which is an algebraic integer ω generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element ω, and computing the Jacobian addition candidate value j by use of the equation j=γ^ω.

5. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 1, further comprising:

said Stickelberger element computing device for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b; and

said Jacobian addition candidate value computing device for generating α at random, which is an algebraic integer γ generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element o), and computing the Jacobian addition candidate value j by use of the equation j=γ^ω.

6. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 1, further comprising: said order candidate value computing device for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K|Q(1+(-ζ)^kj) (where Norm_{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}.

7. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 1, further comprising:

said Stickelberger element computing device for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b; and

said order candidate value computing device for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K|Q(1+(-ζ)^kj) (where Norm_{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}.

8. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 1, further comprising:

said Jacobian addition candidate value computing device for generating α at random, which is an algebraic integer γ generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element ω, and computing the Jacobian addition candidate value j by use of the equation j=γ^ω; and

said order candidate value computing device for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K|Q(1+(-ζ)^kj) (where Norm_{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}.

9. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 1, further comprising:

said Stickelberger element computing device for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b;

said Jacobian addition candidate value computing device for generating α at random, which is an algebraic integer γ generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element ω, and computing the Jacobian addition candidate value j by use of the equation j=γ^ω; and

said order candidate value computing device for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K|Q(1+(-ζ)^kj) (where Norm_{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}.

10. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 1, further comprising:

said parameter deciding device for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹Y_a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer m from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying p, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

11. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 1, further comprising:

said Stickelberger element computing device for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b; and

said parameter deciding device for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer in from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying p, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

12. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 1, further comprising:

said Jacobian addition candidate value computing device for generating α at random, which is an algebraic integer γ generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element ω, and computing the Jacobian addition candidate value j by use of the equation j=γ^ω; and

said parameter deciding device for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer m from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying p, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

13. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 1, further comprising:

said order candidate value computing device for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K|Q(1+(-ζ)^kj) (where Norm_{K|Q}, is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}; and

said parameter deciding device for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer in from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying p, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

14. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+ζX^b+1=0 as claimed in claim 1, further comprising:

said Stickelberger element computing device for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b;

said Jacobian addition candidate value computing device for generating α at random, which is an algebraic integer γ generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element ω, and computing the Jacobian addition candidate value j by use of the equation j=γ^ω; and

said parameter deciding device for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer in from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying p, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

15. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 1, further comprising:

said Stickelberger element computing device for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] f the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b;

said order candidate value computing device for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K/Q(1+(-ζ)^kj) (where Norm_{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}; and

said parameter deciding device for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer in from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying p, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

16. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 1, further comprising:

said Jacobian addition candidate value computing device for generating α at random, which is an algebraic integer γ generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element co, and computing the Jacobian addition candidate value j by use of the equation j=γ^ω;

said order candidate value computing device for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K/Q(1+(-ζ)^kj) (where Norm_{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}; and

said parameter deciding device for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer m from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying p, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

17. A secure parameter generating device in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 1, further comprising:

said Stickelberger element computing device for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b;

said Jacobian addition candidate value computing device for generating α at random, which is an algebraic integer γ generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element c, and computing the Jacobian addition candidate value j by use of the equation j=γ^ω;

said order candidate value computing device for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K/Q(1+(-ζ)^kj) (where Norm_{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}; and

said parameter deciding device for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer m from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying p, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

18. A secure parameter generating method in an algebraic curve cryptography having the definitions expression of αY^a+βX^b+1=0, comprising the steps of:

a Stickelberger element computing procedure for computing a Stickelberger element ω in an ab cyclotomic, respectively based on two different prime numbers a and b specifying degree of complexity of curve;

a Jacobian addition candidate value computing, procedure for computing Jacobian addition candidate value j corresponding to the two different prime numbers a and b, and a prime number p corresponding to the Jacobian addition candidate value j, respectively based on the prime number a, the prime number b, the size n of an encryption key, and the Stickelberger element ω;

an order candidate value computing procedure for computing a class H consisting of a plurality of candidate values for order of a Jacobian group of an algebraic curve specified by the prime number a and the prime number b, respectively based on the prime number a, the prime number b, and the Jacobian addition candidate value j;

a security judging procedure for searching for a candidate value h meeting a security condition such as almost prime number characteristic from the class H, according to the class H; and

a parameter deciding procedure for computing a parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a, the prime number b, and the prime number p, respectively based on the prime number a, the prime number b the prime number p, and the, candidate value h; and

supplying said parameter to an algebraic curve cryptographic public key system.

19. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising:

a procedure for storing a Stickelberger element o computed by said Stickelberger element computing procedure into said ω-storing means;

a procedure for respectively storing the prime number p and the Jacobian addition candidate value j computed by said Jacobian addition candidate value computing procedure into said p-storing means and j-storing means;

a procedure for storing the class H computed by said order candidate value computing procedure into said H-storing means; and

a procedure for storing the candidate value h found by said security judging procedure into said h-storing means.

20. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising:

said Stickelberger element computing procedure for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b.

21. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising:

said Jacobian addition candidate value computing procedure for generating α at random, which is an algebraic integer γ generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element c, and computing the Jacobian addition candidate value j by use of the equation j=γ^ω.

22. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising:

said Stickelberger element computing procedure for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b; and

said Jacobian addition candidate value computing procedure for generating α at random, which is an algebraic integer γ generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element ω, and computing the Jacobian addition candidate value j by use of the equation j=γ^ω.

23. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising:

said order candidate value computing procedure for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K/Q(1+(-ζ)^kj) (where Norm_{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}.

24. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising:

said Stickelberger element computing procedure for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b; and

said order candidate value computing procedure for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K/Q(1+(-ζ)^kj) (where Norm_{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}.

25. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising:

said Jacobian addition candidate value computing procedure for generating α at random, which is an algebraic integer 1 generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element co, and computing the Jacobian addition candidate value j by use of the equation j=γ^ω; and

said order candidate value computing procedure for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K/Q(1+(-ζ)^kj) (where Norm_{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}.

26. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising:

said Stickelberger element computing procedure for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b;

said Jacobian addition candidate value computing procedure for generating α at random, which is an algebraic integer γ generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element 0), and computing the Jacobian addition candidate value j by use of the equation j=γ^ω; and

said order candidate value computing procedure for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K/Q(1+(-ζ)^kj) (where Norm_{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}.

27. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising:

said parameter deciding procedure for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer in from 1 to b inclusively, computing ζ the h-fold of an element in the Jacobian group indicated by the point G, and supplying p, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

28. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising:

said Stickelberger element computing procedure for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b; and

said parameter deciding procedure for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer in from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying p, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

29. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising:

said Jacobian addition candidate value computing procedure for generating α at random, which is an algebraic integer γ generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element ω, and computing the Jacobian addition candidate value j by use of the equation j=γ^ω; and

said parameter deciding procedure for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer in from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying p, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

30. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising:

said order candidate value computing procedure for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K/Q(1+(-ζ)^kj) (where Norm_{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}; and

said parameter deciding procedure for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer in from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying p, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

31. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising: said Stickelberger element computing procedure for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b;

said Jacobian addition candidate value computing procedure for generating α at random, which is an algebraic integer γ generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element ω, and computing the Jacobian addition candidate value j by use of the equation j=γ^ω; and

said parameter deciding procedure for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer m from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying p, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

32. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising:

said Stickelberger element computing procedure for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b;

said order candidate value computing procedure for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K/Q(1+(-ζ)_kj) (where Norm{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}; and

said parameter deciding procedure for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer in from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying P, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

33. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising:

said Jacobian addition candidate value computing procedure for generating α at random, which is an algebraic integer γ generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element c, and computing the Jacobian addition candidate value j by use of the equation j=γ^ω; said order candidate value computing procedure for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Nomr_K/Q(1+(-ζ)^kj) (where Norm_{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}; and

said parameter deciding procedure for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number Pi and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer in from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying p, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

34. A secure parameter generating method in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0 as claimed in claim 18, further comprising:

said Stickelberger element computing procedure for computing the Stickelberger element ω by use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b;

said Jacobian addition candidate value computing procedure for generating α at random, which is an algebraic integer 1 generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element ω, and computing the Jacobian addition candidate value j by use of the equation j=γ^ω;

said order candidate value computing procedure for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K/Q(1+(-ζ)^kj) (where Norm_{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}; and

said parameter deciding procedure for requiring the primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer in from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying P, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

35. A computer readable memory storing a program for generating a secure parameter in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0, which, when executing on a computer causes the computer to carry out the steps comprising:

a Stickelberger element computing procedure for computing a Stickelberger element co in an ab cyclotomic, respectively based on two different prime numbers a and b specifying degree of complexity of curve;

a Jacobian addition candidate value computing procedure for computing Jacobian addition candidate value j corresponding to the two different prime numbers a and b, and a prime number p corresponding to the Jacobian addition candidate value j, respectively based on the prime number a, the prime number b, the size n of an encryption key, and the Stickelberger element ω;

an order candidate value computing procedure for computing a class H consisting of a plurality of candidate values for order of a Jacobian group of an algebraic curve specified by the prime number a and the prime number b, respectively based on the prime number a, the prime number b, and the Jacobian addition candidate value j;

a security judging procedure for searching for a candidate value h meeting a security condition such as almost prime number characteristic from the class H, according to the class H; and

a parameter deciding procedure for computing a parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a, the prime number b, and the prime number p, respectively based on the prime number a, the prime number b, the prime number p, and the candidate value h.

36. A computer readable memory storing a program for generating a secure parameter in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0, which, when executing on a computer causes the computer to carry out the steps comprising:

a Stickelberger element computing procedure for computing the Stickelberger element ωby use of the equation ω=Σ_t[<t/a>+<t/b>]ó_{-t^-1} (where, t runs on a typical series of irreducible residue class with ab used as a divisor, [λ] indicates the maximum integer not exceeding a rational number λ, <λ> indicates a fractional portion λ-[λ] of the rational number λ, ó_t indicates Galois mapping ζ→ζ^t in the ab cyclotomic (ζ is the primitive ab root of 1)), based on the prime number a and the prime number b.

37. A computer readable memory storing a program for generating a secure parameter in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0, which, when executing on a computer causes the computer to carry out the steps comprising:

a Jacobian addition candidate value computing procedure for generating α at random, which is an algebraic integer γ generating a prime ideal of a cyclotomic K generated by the primitive ab root of 1 and whose absolute norm becomes the prime number p of bit length 2n/(a-1)(b-1) or so, based on the prime number a, the prime number b, the size n of the encryption key, and the Stickelberger element ω, and computing the Jacobian addition candidate value j by use of the equation j=γ^ω.

38. A computer readable memory storing a program for generating a secure parameter in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0, which, when executing on a computer causes the computer to carry out the steps comprising:

an order candidate value computing procedure for computing a candidate value h_k for the order of the Jacobian group of an algebraic curve specified by the parameters a and b, using the equation h_k=Norm_K/Q(1+(-ζ)^kj) (where Norm_{K|Q} is a norm mapping in the ab cyclotomic K), as for each k that is an integer from 1 to 2ab inclusively, when ζ is the primitive ab root of 1, based on the prime number a, the prime number b, and the Jacobian addition candidate value j, and computing the class of the candidate values, H={h₁,h₂, . . . ,h_2ab}.

39. A computer readable memory storing a program for generating a secure parameter in an algebraic curve cryptography having the definition expression of αY^a+βX^b+1=0, which, when executing on a computer causes the computer to carry out the steps comprising:

a parameter deciding procedure for requiring he primitive a root ζ_a and the primitive b root ζ_b of 1 with the prime number p used as the divisor, based on the prime number a, the prime number b, the prime number p, and the candidate value h, generating a random point G over an algebraic curve defined by the equation ζ_a¹, Y^a+ζ_b^mX^b+1=0, as for each integer 1 from 1 to a inclusively and each integer in from 1 to b inclusively, computing the h-fold of an element in the Jacobian group indicated by the point G, and supplying p, ζ_a¹, and ζ_b^m as the parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a and the prime number b if the result is equal to an identity element in the Jacobian group.

Description

BACKGROUNDS OF THE INVENTION

1. Field of the Invention

The present invention relates to a secure parameter generating device, a generating method, and a storing medium in a discrete logarithm cryptography (hereinafter, referred to an algebraic curve cryptography), and more particularly to a secure parameter generating device and its generating method in a discrete logarithm cryptography using Jacobian group of algebraic curve.

2. Description of the Related Art

A discrete logarithm cryptography is a public key system based on the difficulty of a discrete logarithm problem on a given finite field. In order to keep the security of cryptography, the order of the finite field must be almost a prime number, that is, a factor of small integer and large integer. The algebraic curve cryptography that is one of the discrete logarithm cryptography needs to use an algebraic curve such that the order of the Jacobian group is almost a prime number.

In the case of an elliptic curve that is the simplest algebraic curve, an efficient algorithm of calculating the order of the Jacobian group over any elliptic curve is known. The detailed description is shown in, for example, "Counting points on elliptic curves over finite fields", Journal de Theorie des Nombres, de Bordeaux 7 (1995), 219-254, Institute de Mathematique de Bordeaux, written by Rene Schoof. The elliptic curve such that the order of the Jacobian group is almost a prime factor can be obtained as follows, by using the above algorithm.