Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-09-03
2002-08-06
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06430588
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to an elliptic-curve arithmetic method and an apparatus therefor and, more particularly, to an apparatus and method for implementing information security techniques (elliptic-curve cryptosystem/signature, factoring) and a recording medium having recorded thereon a program for implementing the method.
Elliptic-curve cryptosystems are now receiving attention as next-generation cryptosystems that will assume a key role in an era of electronic commerce, because they achieve the same level of security as do presently dominating cryptosystems but with a far shorter key length. However, conventional elliptic-curve cryptosystems have some problems in the processing speed for encryption and decryption and in the security level, and much study has been made for higher processing speed and for a higher level of security all over the world.
In the implementation of a public key cryptography or digital signature scheme over an elliptic curve, the processing time is mostly spent on m-multiplications over the elliptic curve. In general, the cryptography or signature scheme uses an elliptic curve defined over a finite field GF(q). Let the defined elliptic curve be represented by E/GF(q), where q is a prime or any power of a prime. In many of conventional mounting methods a prime or 2
n
(n is one or greater integer) is used as q.
It is possible to define an addition and a doubling for a point P over the elliptic curve. These addition and doubling will hereinafter be referred to as “elliptic curve addition” and “elliptic curve doubling” in distinction from ordinary additions and doublings. Of points over the elliptic curve, the identity element of addition will be represented by O. It is customary in the art to construct the m-multiplications (m is 2 or greater integer) by the combined use of the “elliptic curve addition” and the “elliptic curve doubling.” In this specification, the GF(q)-rational point refers to that one of points defined over an elliptic curve whose coordinates are expressed by the element of GF(q).
In some cases, a “Frobenius map” may also be used to compute the m-multiplications. This scheme will hereinafter be called a “base-&phgr; expansion method. Goblitz et al. have proposed a method for m-multiplying a GF(2
k
)-rational point (k is 2 or greater integer) over the elliptic curve E/GF(2) defined over the finite field GF(2). As described below, however, this method accelerates the multiplication only when q is very small.
Next, a description will be given of the elliptic curve and the Frobenius map.
Let F/GF(q) denote an elliptic curve defined over the finite field GF(q). For a group E(GF(q
k
)) of GF(q
k
)-rational points over E/GF(q), it is possible to define the multiplication using such a Frobenius map p as mentioned below.
Definition 1 (Frobenius Map)
The Frobenius map is defined by an endomorphism as
&phgr;: (x, y)→(x
q
, y
q
)
for a point P=(x, y), where x, y&egr;EGF(q)′, on the elliptic curve. GF(q)′ is an algebraic closure of GF(q).
The Frobenius map &phgr; is an endomorphism over the elliptic curve. Letting m-multiplied map P→mP be represented by [[m]], it satisfies the following equation:
&phgr;
2
−[[t]]&phgr;+[[q]]=[[0]], −2{square root over (q)}<t<2{square root over (q)} (1)
Equation (1) has an imaginary root and permits a multiplication different from [[m]] with &phgr;. &phgr; is a value that is determined uniquely to a given elliptic curve, and it can be calculated by known methods.
The calculation of the Frobenius map can usually be conducted faster than the elliptic curve addition. For example, in the case of representing an element of GF(q
k
) by using a normal basis, the Frobenius map can be computed only by the element replacement and the computing time is negligible.
Let &agr; denote a generator of the normal basis. In the normal basis representation, an element a&egr;EGF(q
k
) is represented by a=[a
0
, a
1
, . . . , a
k-1
] using a
i
&egr;EGF(q) which provides
a
=
∑
i
=
0
k
-
1
a
i
α
qi
(
2
)
At this time, a
q
=[a
k−1
, a
0
, a
1
, . . . , a
k−2
], and the map &phgr; can be applied by the element replacement.
In the base-&phgr; expansion method, the first step is to transform mP using &phgr; as follows:
mP
=
∑
i
=
0
r
c
i
φ
i
P
(
3
)
where −q<c
i
<q and r≅k.
Koblitz presented an m-multiplication algorithm for GF(2
k
))-rational points over E/GF(2) through utilization of the base-&phgr; expansion method (N. Koblitz. “CM-Curves with Good Cryptographic Properties,” CRYPTO' 91, pp.279-287 (1991)). And, Solinas proposed an improved version of the algorithm (J. A. Solinas, “An Improved Algorithm for Arithmetic on a Family of Elliptic Curves,” CRYPTO' 97, pp.357-371 (1997)). With these algorithms, −1≦c
i
1 and the m-multiplication can be computed by a maximum of r Frobenius map calculations and elliptic curve additions.
For example, on the elliptic curve E/GF(2):y
2
+xy=x
3
+1, it can be regarded that &phgr;=[[(−1+{square root over (−7)})/2]]. In the case of obtaining 9P without using the base-&phgr; expansion method, the following equation is used:
9P=(2×2×2+1)P (4)
The calculation of Equation (4) requires three “elliptic curve doublings” and one “elliptic curve addition” (a total of four computations).
On the other hand, the use of &phgr; provides the following equation:
9P=(&phgr;
5
−&phgr;
3
+1)P (5)
The calculation of Equation (5) can be conducted by two “elliptic curve additions” since the calculation of &phgr;
5
P and &phgr;
3
P takes negligible time. Hence, the computational time can be made shorter than in the case of using Equation (3).
Conventionally, a fast algorithm by the base-&phgr; expansion method is applied mainly to elliptic curves defined over GF(q
k
) for a small integer q, but theoretically, it can be applied in more general cases. In such an instance, however, since the coefficient c
i
in Equation (3) becomes 0≦|c
i
|<q, the operating time for the c
i
-multiplication is not negligible when q in GF(q
k
) is large. For instance, in Equation (5) in the prior art example, |c
i
| is 0 or 1 and the operating time for the c
i
-multiplication is negligible.
In this instance, the conventional method, if used intact, is not always faster than the method which does not use &phgr;. That is why the base-&phgr; expansion method has been applied only when q is small.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide an arithmetic method which permits m-multiplication over an elliptic curve defined over a finite field GF(q
k
) by the base-&phgr; expansion method irrespective of the magnitude of a prime q, and apparatus for implementing the arithmetic method and a recording medium having recorded thereon a program for implementing the method,
According to the present invention, there is provided an elliptic-curve arithmetic method for m-multiplying a rational point P over an elliptic curve E/GF(q) defined over a finite field, the method comprising the steps of:
inputting a rational point P, a Frobenius map &phgr; defined over the elliptic curve E/GF(q), an integer k and a prime q equal to or greater than 3 by input means;
calculating integers r and c
i
which satisfy the following equation, by using the Frobenius map &phgr;
m
=
∑
i
=
0
r
-
1
c
i
φ
i
where 0≦i<r, 0≦r≦k and −q≦c
1
≦q;
calculating the following r points P
0
to P
r−1
:
P
0
=P
P
1
=&phgr;P
P
2
=&phgr;
2
P
:
P
r−1
=&phgr;
r−1
P
by generating means supplied with the rational point P and the integers r and c
i
;
calculating the fo
Hoshino Fumitaka
Kobayashi Kunio
Kobayashi Tetsutaro
Morita Hikaru
Connolly Bove & Lodge & Hutz LLP
Malzahn David H.
Nippon Telegraph and Telephone Corporation
LandOfFree
Apparatus and method for elliptic-curve multiplication and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for elliptic-curve multiplication and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for elliptic-curve multiplication and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2955345