Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
1998-12-17
2002-11-12
Barron, Gilberto (Department: 2132)
Cryptography
Particular algorithmic function encoding
Public key
C380S259000, C380S285000, C713S180000
Reexamination Certificate
active
06480605
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to encryption and decryption devices for use in public-key cryptosystems and a recording medium with their processing programs recorded thereon.
In the transmission and reception of data over a security-free communication channel, cryptosystems are used to guard against wiretapping. In general, cryptosystems fall into two categories: common-key cryptosystem and public-key cryptosystem. In the common-key cryptosystem, encipher and decipher keys are the same, and hence they need to be delivered in secrecy. Furthermore, since this technique requires as many keys as combinations of communication, an increase in the number of sending/receiving stations in the network inevitably causes an increase in the number of keys that must be kept secret.
On the other hand, the public-key cryptosystem uses different keys as encipher and decipher keys. Even if the encipher key is made public, the secrecy of the decipher key could be maintained as long as its computation from the encipher key is infeasible in terms of computational complexity. Accordingly, no delivery of the encipher key is necessary. Moreover, since each sending/receiving station needs only to keep its own decipher key in secrecy, it is also possible to solve the problem of the keys to be held secret. That is, the public-key cryptosystem offers a solution to the problem of key management encountered in the common-key cryptosystem. Another advantage of the public-key cryptosystem over the common-key cryptosystem is the settlement of the problem of key delivery which is the greatest difficulty with the latter; the former does not involve the secret key delivery. Besides, in public-key cryptosystem the same key is shared by the persons concerned, it is impossible to identify which person generated a ciphertext using the common key. With the public-key cryptosystem, however, since each person has his own secret key exclusively, it is possible to identify the person who generated a ciphertext using the secret key. Digital signature schemes utilize this property of public-key cryptosystem.
That is, the use of public-key cryptosystem permits the implementation of digital signature schemes, and ensures verification of the opponent of communication. It is well-known in the art that the public-key cryptosystem can be implemented through utilization of what is called a trapdoor one-way function. A one-way function is one that allows ease in computation in one direction but makes computation in the opposite direction infeasible in terms of computational complexity. The trapdoor one-way function mentioned herein is a one-way function with a trick “knowledge of some secret allows ease in computation in the opposite direction as well.” The trick is called a “trapdoor.”
At present, there are known such yet-to-be-solved problems as listed below.
(a) Integer Factorization Problem (hereinafter referred to as IFP): A problem of factoring an input composite number into its prime factors;
(b) Discrete Logarithm Problem of Multiplicative Group over Finite Field (hereinafter referred to as DLP): A problem of determining, for example, an integer x in y=g
x
satisfying 0≦x≦p for a given element y in a multiplicative group F
p
*=<g>of a finite field F
p
, where p is a prime;
(c) Discrete Logarithm Problem of elliptic curves over Finite Field (hereinafter referred to as ECDLP): A problem of determining, for example, an integer m satisfying P=mG for a point P in a subgroup of E(F
p
) generated from a point G in a group E(F
p
) composed of the entire F
p
-points on an elliptic curve defined over the finite field F
p
.
For the elliptic curve and elliptic curve cryptosystems, see, for example, Menezes, A. J., “Elliptic Curve Public Key Cryptosystems,” Kluwer Academic Publishers (1993) (hereinafter referred to as Literature 1). The cryptosystems described in this literature are typical examples expected to use the one-way function. Typical and practical ones of public-key cryptosystems proposed at present are, for instance, the RSA cryptosystem, the Rabin cryptosystem, the ElGamal cryptosystem, and the elliptic curve cryptosystem (elliptic ElGamal cryptosystem). The RSA and Rabin cryptosystems are based on the intractability of IFP, the ElGamal cryptosystem is based on the intractability of DLP, and the elliptic curve cryptosystem is an Elgamal cryptosystem in a group of points on an elliptic curve over a finite field, which is based on the intractability of ECDLP.
The RSA cryptosystem is disclosed in Rivest, R. L. et al “A Method for Obtaining digital Signatures and Public-Key Cryptosystems,” Communication of the ACM, vol. 21, pp. 120-126 (1978) (hereinafter referred to as Literature 2). The Rabin cryptosystem is disclosed in Rabin, M. O. “Digital signatures and Public-Key Functions as in tractable as Factorization,” MIT, Technical Report, MIT/LSC/TR-212 (1979) (hereinafter referred to as Literature 3). The ElGamal cryptosystem is disclosed in ElGamal, T. “A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,” IEEE Trans. on Information Theory, IT-31, 4, pp. 469-472 (1985) (hereinafter referred to as Literature 4). The elliptic curve cryptosystem was proposed by Miller, V. S. and Kolblitz, N. separately in 1985, and this scheme is described in Miller, V. S. “Use of Elliptic Curves in Cryptography,” Proc. of Crypto '85, LCNCS 218, springer-Verlag, pp. 417-426 (1985) (hereinafter referred to as Literature 5) and in Kolblitz, N., “Elliptic Curve Cryptosystems,” Math. Comp., 48, 177, pp. 203-209 (1987) (hereinafter referred to as Literature 6).
Now, the above-mentioned cryptosystems and their properties will be described concretely.
A description will be given first of how the RSA cryptosystem is constructed. Let p and q be odd primes and choose n, e and d such that they satisfy the following equations:
n=pq
GCD
(
e, LCM
(
p
−1
, q
−1))=1
ed
≡1 (mod
LCM
(
p
−1
, q
−1))
where GCD(a, b) is the greatest common divisor of integers a and b, and LCM(a, b) is the least common multiple of the integers a and b.
The encryption and decryption processes E(M) and D(C) of a message M are defined by the following equations using (n, e) as public keys and (d, p, q) as secret keys.
C≡E
(
M
)≡
M
e
(mod
n
) (1)
M≡D
(
C
)≡
C
d
(mod
n
) (2)
At this time, if M satisfies 0≦M≦n−1, then the following equation holds.
D
(
E
(
M
))=
M
(3)
The Rabin cryptosystem is constructed as follows: Choose p, q and n in the same manner as in the above, and determine the integer b which satisfies 0bn. The encryption process E(M) and the description process D(c) are defined by the following equations using (n, b) as public keys and (p, q) as secret keys.
C
≡
E
(
M
)
≡
M
(
M
+
b
)
(
mod
n
)
(
4
)
M
≡
D
(
C
)
≡
(
-
b
±
(
b
2
+
4
C
)
1
/
2
)
/
2
(
mod
p
)
≡
(
-
b
±
(
b
2
+
4
C
)
1
/
2
)
/
2
(
mod
q
)
(
5
)
The Rabin cryptosystem involves solving simultaneous equations in decryption, but since the quadratic equation possesses two solutions, the calculation in this case brings about four solutions, giving rise to a problem that the decryption cannot uniquely be performed under the above conditions. This can be settled as a problem of system operation by using some additional information for communication; and the Rabin cryptosystem has also been improved for unique description. This is described in Kaoru Krosawa et al., “Public-Key Cryptosystems Using Reciprocals which are as Intractable as Factoring,” Journal of IEICE, Vol. J70-A, No. 11, pp. 1632-1636 (1987) (hereinafter referred as to Literature 7).
The ElGamal cryptosystem is constructed as follows: Let p be a prime. Choose g as one generating element of a modular-p reduced residue class group
Okamoto Tatsuaki
Uchiyama Shigenori
Barron Gilberto
Connolly Bove & Lodge & Hutz LLP
Telegraph and Telephone Corporation
Zand Kambiz
LandOfFree
Encryption and decryption devices for public-key... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Encryption and decryption devices for public-key..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encryption and decryption devices for public-key... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2941750