Method and device for constructing elliptic curves

Details Method and device for constructing elliptic curves Method and device for constructing elliptic curves

2000-01-24

2003-08-26

Smithers, Matthew (Department: 2134)

Cryptography

Particular algorithmic function encoding

Public key

C380S028000, C708S492000

Reexamination Certificate

active

06611597

ABSTRACT:

This application is based on an application No. H11-15592 filed in Japan, the content of which is hereby incorporated by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to elliptic curve arithmetic operation techniques and elliptic curve application techniques.
2. Description of the Prior Art
In recent years, the use of elliptic curves is becoming popular in the encrypted communications technology. Cryptosystems that employ elliptic curves rely for their security on the difficulty of solving a discrete logarithm problem.
Representative examples of the discrete logarithm problem are problems based on finite fields and problems based on elliptic curves. Such problems are described in detail in Neal Koblitz,
A Course in Number Theory and Cryptography,
Springer-Verlag (1987).
Elliptic Curve Discrete Logarithm Problem
The elliptic curve discrete logarithm problem is the following.
Let E(GF(p)) be an elliptic curve defined over a finite field GF(p), with a point G on the elliptic curve E, given when the order of E is divisible by a large prime, being set as a base point. Here, “the order of the elliptic curve” means the number of points on the elliptic curve whose coordinates are in GF(p). This being so, the problem is to find an integer x such that
Y=xG
where Y is a given point on E, if such an integer x exists.
Here, p is a prime and GF(p) contains p elements.
Conditions for Secure Elliptic Curves
Given that various cryptanalysis attacks against elliptic curve discrete logarithm problems have been devised over the years, it is of great importance to construct a secure elliptic curve to strengthen the elliptic curve cryptosystem against these attacks.
In this specification, “constructing an elliptic curve” roughly means to determine the parameters a and b of an elliptic curve which is given by an equation
y{circumflex over ( )}
2
=x{circumflex over ( )}
3
+ax+b
where the sign {circumflex over ( )} represents a repeated multiplication, such as x{circumflex over ( )}3=x×x×x.
To be secure against all existing cryptanalysis attacks, an elliptic curve over the finite field GF(p) must satisfy the conditions:
(a) the order of the elliptic curve is not equal to any of p−1, p, and p+1; and
(b) the order of the elliptic curve has a large prime factor.
In other words, checking the order of the elliptic curve allows the security of the elliptic curve to be assessed.
According to T. Okamoto & K. Ohta Encryption,
Zero Knowledge Proof, and Number Theory,
Kyoritsu (1995), pp.155~156, when the above conditions are satisfied, computation time required to solve the elliptic curve discrete logarithm problem is exponential time in the largest prime factor of the elliptic curve order.
Methods of Constructing Elliptic Curves
There are mainly two elliptic curve construction methods that are:
{circle around (1)} elliptic curve construction using the CM (Complex Multiplication) method; and
{circle around (2)} elliptic curve construction using an order computation algorithm.
Although {circle around (1)} can construct an elliptic curve easily, it cannot choose an elliptic curve at random. For details of this method, see A. Miyaji “On Ordinary Elliptic Curve Cryptosystems”
ASIACRYPT'
91, Springer-Verlag (1991), pp.460~469. Meanwhile, {circle around (2)} can construct a random elliptic curve, though it takes considerable time to do so.
Prior Art Example 1
Elliptic Curve Construction using an Order Computation Algorithm
The following introduces the method of constructing an elliptic curve using an algorithm to compute the order of the elliptic curve, with reference to FIG.
1
. For details on this method, see N. Koblitz “Elliptic Curve Implementation of Zero-Knowledge Blobs”
J. Cryptology,
vol.4, no.3 (1991), pp.207~213.
First, a random number is generated (S
901
), and parameters which define the elliptic curve are generated using the random number (S
902
). Next, the order of the elliptic curve is computed using the generated parameters (S
903
). The computed order is checked whether it satisfies one or more predetermined conditions for secure elliptic curves, to assess the security of the elliptic curve (S
904
). If and only if the order satisfies the conditions, the generated elliptic curve parameters are outputted. If the order does not satisfy the conditions, the procedure returns to step S
901
to repeat the random number generation, the parameter generation, the order computation, and the security judgement, until an elliptic curve whose order satisfies the conditions in step S
904
is found.
This method which employs an order computation algorithm requires long computation time. Especially, it takes much time to compute the order of the elliptic curve.
One example of algorithms used to compute orders of elliptic curves is an algorithm proposed by Schoof. This algorithm is a polynomial time algorithm. The polynomial time algorithm referred to here is an algorithm whose computation time is polynomial time. The computation time of Schoof's algorithm per se is not practical.
Prior Art Example 2
Elliptic Curve Order Computation according to the SEA Algorithm
Atkin and Elkies have proposed several improvements of Schoof's algorithm and so have designed the SEA (Schoof-Elkies-Atkin) algorithm.
This algorithm is detailed in R. Lercier & F. Morain “Counting the Number of Points on Elliptic Curves over Finite Fields: Strategies and Performances” EUROCRYPT'95, Springer-Verlag (1995), pp.79~94.
The SEA algorithm computes t mod L{circumflex over ( )}n (n=1, 2, 3, . . . ). This can be done by calculating an eigenvalue of a map called the Frobenius map. More specifically, k is found from an equation
(
&agr;{circumflex over ( )}p,&bgr;{circumflex over ( )}p
)=
k
(&agr;,&bgr;)
where (&agr;,&bgr;) is an L-division point on an elliptic curve E and k(&agr;,&bgr;) is a point on E after exponentiating the point (&agr;,&bgr;) by k. This is carried out through computation on the elliptic curve E on a residue class ring of polynomials in variable &agr; and &bgr; with elements of GF(p) as coefficients, the moduli of the ring being polynomials &bgr;{circumflex over ( )}
2
−f(&agr;) and h(&agr;). Computational complexity of the inversion of a polynomial is greater than computational complexity of the multiplication of a polynomial, so that a 3-tuple coordinate is used in this computation. Here, projective coordinate is employed as the 3-tuple coordinate, as the projective coordinate has been conventionally used for elliptic curves over finite fields. Conventional projective coordinate is described in Miyaji, Ono & Cohen “Efficient Elliptic Curve Exponentiation”
Advances in Cryptology
-
Proceedings of ICICS
'97, Lecture Notes in Computer Science, Springer-Verlag (1997), pp.282-290.
Prior Art Example 3
Calculation of the Exponentiation Point k(&agr;,&bgr;) on the Elliptic Curve E
Exponentiating the point (&agr;,&bgr;) on the elliptic curve E by k is done by splitting the exponentiation into additions and doublings and performing the additions and the doublings in the following way.
Suppose (&agr;,&bgr;) is transformed to (&agr;:&bgr;:1), and (&agr;:&bgr;:1) is interpreted as (X(&agr;):&bgr;×Y(&agr;):Z(&agr;) (where X(&agr;)=&agr; and Y(&agr;)=Z(&agr;)=1).
Note here that “( , )” and “( : : )” represent affine coordinates and projective coordinates, respectively.
Assume
P
1
=(
X
1
(&agr;):&bgr;×
Y
1
(&agr;):
Z
1
(&agr;))
P
2
=(
X
2
(&agr;):&bgr;×
Y
2
(&agr;):
Z
2
(&agr;))
P
3
=
P
1
+P
2
=(
X
3
(&agr;):&bgr;×
Y
3
(&agr;):
Z
3
(&agr;))
In this specification, the operators × and * in an addition formula or a doubling formula both denote a multiplication. In the addition formula or the doubling formula, a multiplication which appears for the first time in the formula is expressed by the operator *, whereas a multiplication which has already appeared is expressed by the operator ×. The number of mul

Affiliated with

Also associated with

Rating

Method and device for constructing elliptic curves does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and device for constructing elliptic curves, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for constructing elliptic curves will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3128514