Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
2002-09-24
2004-03-30
Barron, Gilberto (Department: 2132)
Cryptography
Particular algorithmic function encoding
Public key
C380S263000, C713S172000
Reexamination Certificate
active
06714648
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to an IC card (integrated circuit card) capable of processing encryption data or information. More particularly, the invention is concerned with a method capable of executing at a high speed elliptic curve encryption processing in an encryption processing in which hardware designed for executing a high-speed algorithm for a residual multiplication arithmetic (multiplication on the set of integers) is adopted and a device such as an IC card in which the above-mentioned method is adopted.
For having better understanding of the present invention, technical background thereof will first be described in some detail. As an encryption scheme for a public key crypto-system, there is known an RSA encryption scheme which was invented by Rivest, Shamir and Adleman in 1978. The basic principle underlying the RSA encryption will be reviewed below.
Basic Principle of RSA Encryption
Representing a secret key by (d, n), a public key by (e, n), a plaintext by M and a co-processor by c, respectively, then the encryption and the decryption can be represented, respectively, by the calculation formulae mentioned below.
Encryption: C≡M
e
(mod n), and
decryption: M≡C
d
(mod n).
In the above expressions, n is given by p·q where p and g represent large prime numbers, respectively which satisfy the conditions that &lgr;(n)=LCM {(p−1), (q−1)} (where LCM represents a least common multiple), GCD {e, &lgr;(n)}=1 (where GCD represents a greatest common divisor), and that d=e
−1
mod &lgr;(n).
The security of the RSA encryption is ensured by the fact that it is very difficult to factorize n into prime factors. In this conjunction, it is recommended to employ large integers on the order of 1024 bits as the parameters such as e, d, n, M and so forth. In that case, modular multiplication on the set of integers (hereinafter referred to also as the residual multiplication arithmetic) has to be conducted 1534.5 times on an average for a single processing in accordance with the encryption formula C≡M
e
(mod n), when such a binary operation method is resorted to, which is described in detail in D. E. Knuth: “SEMINUMERICAL ALGORITHMS ARITHMETIC”, The Art of Computer Programming, Vol. 2, Addison-Wesley, 1969.
Furthermore, as another encryption scheme belonging to the public key crypto-system, there may be mentioned an elliptic curve encryption processing proposed by Koblitz and Miller independently in 1985. The basic principle underlying this elliptic curve encryption will be reviewed below.
Principle of the Elliptic Curve Encryption
Representing the order of a finite field by a prime number p while representing by a and b the parameters which determine the elliptic curve, a set which includes a set of points capable of satisfying the conditions given by the undermentioned expression and which is added with a virtual point at infinity is referred to as the elliptic curve Ep. For the convenience of illustration, the elliptic curve Ep of concern is presumed to be capable of being represented on the affine coordinate system.
Ep:
y
2
≡x
3
+ax+b
(mod
p
)
Addition between two points P
1
and P
2
on the elliptic curve, i.e., P
3
=P
1
+P
2
(where P
i
=(x
i
, y
i
)), can be defined as follows:
Case where P
1
≠P
2
In this case, the arithmetics as involved will hereinafter be referred to as the elliptic addition arithmetic.
The elliptic addition arithmetic includes addition performed zero times, subtraction performed six times, multiplication performed twice and division performed once, as follows:
&lgr;=(
y
2
−y
1
)/(
x
2
−x
1
),
x
3
=&lgr;
2
−x
1
−x
2
,
and
y
3
=&lgr;(
x
1
−x
3
)−
y
1
Case where P
1
=P
2
In this case, the arithmetic will hereinafter be referred to as the elliptic by-two-multiplication arithmetic.
The elliptic by-two-multiplication arithmetic includes addition performed once, subtraction performed three times, multiplication performed three times and division performed once, as follows:
&lgr;=(3×12+
a
)/2
y
1
, x
3
=&lgr;
2
−2×1
and
y
3
=&lgr;(
x
1
−x
3
)−
y
1
At this juncture, it should be mentioned that all the arithmetic operations mentioned above are performed on a residue system to modulus p.
The security of the elliptic curve encryption described above is based on the fact that when a point derived through multiplication of a point A on the elliptic curve by x (i.e., the point obtained by adding “A” x times) is represented by B(=x·A), extreme difficulty will be encountered in finding the value of x on the basis of the values of the points A and B if known. This feature is known as the elliptic curve discrete logarithm problem. In order to ensure the security comparable to that realized by the 1024-bit RSA encryption described previously, it is recommended that each of the parameters such as p, a, x
i
, y
i
, etc. be an integer on the order of 160 bits.
The arithmetic operation for determining the point (k·P) corresponding to multiplication of a point P by k, which constitutes one of the basic arithmetic operations for the elliptic curve encryption, can be realized by computation in accordance with the addition on the elliptic curve (elliptic curve addition) mentioned above. In this conjunction, it is noted that the modular division on the set of integers (hereinafter also referred to as the residual division arithmetic) has to be conducted in order to determine &lgr;. The residual division arithmetic (i.e., modular division on the set of integers) can generally be coped with by resorting to an algorithm such as an extended Euclidean algorithm or the like, which requires, however, lots of processing times. Such being the circumstances, there is widely adopted the method or scheme for realizing the arithmetics on the elliptic curve by transforming a point on a two-dimensional affine coordinate system into a point on a three-dimensional coordinate system without resorting to the residual division arithmetic processing. For more particulars of this scheme, reference may be made to D. V. Chudnovsky and G. V. Chudnovsky: “SEQUENCES OF NUMBERS GENERATED BY ADDITION IN FORMAL GROUPS AND NEW PRIMALITY AND FACTORIZATION TESTS”, Advances in Applied Mathematics, Vol. 7, pp. 385-434, 1986. By way of example, when the addition arithmetics on the elliptic curve Ep in the two-dimensional affine coordinate system is transformed into addition arithmetics in the three-dimensional projective coordinate system so that the conditions given by x≡X/Z
2
(mod p) and y≡Y/Z
3
(mod p) can be satisfied, the addition arithmetics are defined as follows:
The elliptic addition arithmetic includes addition performed twice, subtraction performed five times, multiplication performed sixteen times and division performed zero times, as follows:
X
3
=R
2
−TW
2
,
2
Y
3
=VR−MW
3
,
and
Z
3
=Z
1
Z
2
W
where
W=X
1
Z
2
2
−X
2
Z
1
2
,
R=Y
1
Z
2
3
−Y
2
Z
1
3
,
T=X
1
Z
2
2
+X
2
Z
1
2
,
M=Y
1
Z
2
3
−Y
2
Z
1
3
,
and
V=TW
2
−2
X
3
.
The elliptic by-two-multiplication arithmetic includes addition performed once, subtraction performed three times, multiplication performed ten times and division performed zero times, as follows:
X
3
=M
2
−2
S,
Y
3
=M
(
S−X
3
)−
T
,
and
Z
3
=2
Y
1
Z
1
where
M=
3
X
1
2
+aZ
1
4
,
S=
4
X
1
Y
1
2
,
and
T=
8
Y
1
4
At this juncture, it should be mentioned that all the arithmetic operations mentioned above are performed on a residue system to modulus p.
As another example of the coordinate transformation methods, there may be mentioned a coordinate transformation to a three-dimensional homogeneous coordinate system such that the conditions given by the following expressions can be satisfied.
x≡X/Z
(mod
p
),
and
y≡Y/Z
Miyazaki Seiji
Takaragi Kazuo
Barron Gilberto
Hitachi , Ltd.
Mattingly Stanger & Malur, P.C.
Zand Kambiz
LandOfFree
IC card equipped with elliptic curve encryption processing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with IC card equipped with elliptic curve encryption processing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and IC card equipped with elliptic curve encryption processing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3185754