Cryptography – Miscellaneous
Reexamination Certificate
2000-08-15
2004-11-09
Peeso, Thomas R. (Department: 2132)
Cryptography
Miscellaneous
Reexamination Certificate
active
06816594
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a security technique for computer networks, and more particularly to a method for generating an elliptic curve used especially for elliptic curve cryptography, an elliptic curve apparatus, an elliptic curve cryptosystem, and a storage medium storing said method.
BACKGROUND ART
As an elliptic curve for elliptic curve cryptography, a normal form elliptic curve y
2
=f(x) may be used, where f(x)=x
3
+ax+b(a,b&egr;F
p
) where F
p
is a finite field composed of p elements and p is a large prime number. Each set (x
0
,y
0
), where x
0
,y
0
&egr;F
p
, satisfying the equation y
0
2
=f(x
0
) is called a point on the curve. Operation can be performed in the set of all of these points plus a point at infinity, and the number of the points is called a curve order. When a curve order is denoted by n and expressed as n=cl where c is a positive integer, called a cofactor, and 1 is a large prime number, the elliptic curve is called safe if the value of c is small. In a method for generating a safe normal form elliptic curve, described in ANSI X9.62, “Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)”, 1999, a normal form elliptic curve is repeatedly generated at random, and its safety is evaluated based on its curve order until a safe normal form elliptic curve is obtained.
Furthermore, according to “P. L. Montgomery, Speeding the Pollard and Elliptic Curve Methods of Factorization, Math. Comp. 48 (1987) 243-264”, by using the Montgomery type elliptic curve By
2
=X
3
+AX
2
+X(A,B&egr;F
p
), operation can be performed at higher speed than by use of a normal form elliptic curve. A normal form elliptic curve can be transformed to a Montgomery type elliptic curve when a point on the normal form elliptic curve corresponds to a point on the Montgomery type elliptic curve, one to one, and operation on one point coincides with operation on the other. Not all of normal form elliptic curves can be transformed to Montgomery type elliptic curves. Requirements for a normal form elliptic curve to be transformable to a Montgomery type elliptic curve are described in a paper entitled “Calculation Method for Elliptic Curve Cryptographic Operation” by Tetsuya Izu (1999 Symposium on Cryptography and Information Security, Publication vol. 1, 1999, 275-280). The above paper also discloses that the curve order of each Montgomery type elliptic curve is always divisible by 4.
However, the above conventional technique has given no consideration to generation of a normal form elliptic curve transformable to a Montgomery type elliptic curve. Therefore, to generate a safe normal form elliptic curve transformable to a Montgomery type elliptic curve, it is necessary to generate a safe normal form elliptic curve and then determine whether it is transformable to a Montgomery type elliptic curve, and if not, a safe normal form elliptic curve is generated again and the above procedure must be repeated until a safe normal form elliptic curve transformable to a Montgomery type elliptic curve is found. Generally, a process for generating a safe normal form elliptic curve takes longer time than a process for determining whether it can-be transformed to a Montgomery type elliptic curve. Because of this, generation of an elliptic curve having the above properties requires a large amount of time, making it difficult to regularly replace an elliptic curve with a new elliptic curve having the above properties in elliptic curve cryptography to ensure network security. Incidentally, to ensure security against an attack using the Baby-Step-Giant-Step method in which pre-calculation for the attack can be performed by knowing only the respective elliptic curve without knowing the public key, the elliptic curve must be regularly replaced with a new one, and no other effective methods exist. This means that in the above conventional technique, a specific elliptic curve is easily attacked.
It is an object of the present invention to provide a method, an apparatus, an elliptic curve cryptosystem, and a storage medium for generating an elliptic curve to improve operation speed and security.
DISCLOSURE OF INVENTION
To achieve the above object, the present invention provides a method for generating an elliptic curve, comprising the steps of: generating a first elliptic curve, for example, y
2
=x
3
+ax+b; determining whether said first elliptic curve can be transformed to a second elliptic curve, for example, BY
2
=X
3
+AX
2
+X; and determining safety of the first elliptic curve transformable to said second elliptic curve. Here, as the first elliptic curve, an elliptic curve defined over a field of a predetermined prime order may be used. Further, said step of determining whether said first elliptic curve can be transformed to said second elliptic curve includes steps of: determining whether there is &agr; for which f(&agr;)=0 for said first elliptic curve y
2
=f(x)=x
3
+ax+b; and determining whether f′(&agr;) has a square root for &agr; for which f(&agr;)=0. Further, said step of determining the safety of said first elliptic curve includes steps of: extracting information on a curve order of said first elliptic curve; and judging a cofactor based on the information on said curve order. The present invention further provides a method for generating an elliptic curve, comprising the steps of: generating a first elliptic curve y
2
=x
3
+ax+b; generating a second elliptic curve y
2
=x
3
+ar
2
x+br
3
; determining whether said first elliptic curve can be transformed to a third elliptic curve BY
2
=X
3
+AX
2
+X; and when said first elliptic curve can be transformed to said third elliptic curve, judging safety of said first elliptic curve and said second elliptic curve. The present invention provides a method for generating an elliptic curve defined over a prime field in elliptic curve cryptography, comprising the steps of: randomly generating a normal form elliptic curve y
2
=x
3
+ax+b; determining whether said generated normal form elliptic curve y
2
=x
3
+ax+b can be transformed to a Montgomery type elliptic curve BY
2
=X
3
+AX
2
+X; determining divisibility of a curve order of said elliptic curve by 8; collecting information on the curve order of said elliptic curve; and judging a value of a cofactor based on the information on said curve order; wherein a normal form elliptic curve which can be transformed to a Montgomery type elliptic curve and whose cofactor is 4 is generated. The present invention provides an apparatus for generating an elliptic curve, comprising: elliptic curve candidate generating means for generating a first elliptic curve y
2
=x
3
+ax+b; transformability judgement means for determining whether said first elliptic curve can be transformed to a second elliptic curve By
2
=X
3
+AX
2
+X; safety judgement means for determining safety of the first elliptic curve transformable to said second elliptic curve. Here, said transformability judgement means includes: root existence judgement means for determining whether there is &agr; for which f(&agr;)=0 for said first elliptic curve; and square root judgement means for determining whether f′(&agr;) has a square root for a for which f(&agr;)=0. Alternatively, said transformability judgement means includes: root existence judgement means for determining whether there is &agr; for which f(&agr;)=0 for said first elliptic curve; and quadratic residue judgement means for determining whether f′(&agr;) is a quadratic residue for &agr; for which f(&agr;)=0. The present invention provides an apparatus for generating an elliptic curve employed in a cryptosystem in which a first computer and a second computer carry out cryptocommunications with each other, wherein said apparatus re
Hitachi , Ltd.
Mattingly Stanger & Malur, P.C.
Peeso Thomas R.
LandOfFree
Elliptic curve generating method and device, elliptic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Elliptic curve generating method and device, elliptic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Elliptic curve generating method and device, elliptic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3339657