Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
1997-08-08
2001-07-10
Barron, Jr., Gilberto (Department: 2131)
Cryptography
Particular algorithmic function encoding
Public key
C380S028000
Reexamination Certificate
active
06259790
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a public key cryptosystem in which an encryption key is publicly disclosed while a decryption key is kept in secret, and more particularly, to a secret communication and authentication scheme based on a public key cryptosystem which can improve a decryption speed while maintaining an equivalent security level as the known public key cryptosystem such as RSA (Rivest-Shamir-Adleman) cryptosystem and Rabin cryptosystem and resolving problems associated with the known public key cryptosystem.
2. Description of the Background Art
In the field of communication, the cryptographic techniques are indispensable for protecting communication contents from a wiretapping or a forgery. In particular, the public key cryptosystem which only requires a simple key management is effective and has been widely used. The representative public key cryptosystems include the RSA cryptosystem which uses the modular exponent calculation and the Rabin cryptosystem which uses the encryption function in a form of a quadratic polynomial in modulo a product of two prime numbers, both of which are already in practical use.
Here, the RSA cryptosystem and the Rabin cryptosystem will be briefly described in this order. Note that, in the following description, (mod N) denotes a calculation in modulo N, ≡ denotes a congruence, LCM denotes the least common multiplier, GCD denotes the greatest common divisor, [A] denotes the Gaussian symbol for the largest integer not exceeding a number A, and (B) denotes a square root of a number B.
[Basic Principles of RSA Cryptosystem]
An encryption key of the RSA cryptosystem is given by a set (e, N) and a corresponding decryption key is given by a set (d, N), where e and N are public keys and d is a secret key. N is a product of two prime numbers (N=pq), and a set of prime numbers p and q for generating N is also referred to as a secret key.
Denoting a plaintext by M and a ciphertext by C, algorithms for the encryption E and the decryption D can be expressed by the following equations (1) and (2).
C=E
(
M
)=
M
e
(mod
N
) (1)
M=D
(
C
)=
C
d
(mod
N
) (2)
Here, it is assumed that M and C are integers in a range between 0 and N−1. If the original message is larger than N, the original message is to be divided into blocks of size N and the encryption and the decryption are to be applied block by block.
The encryption and the decryption are the one-to-one and onto mapping. Consequently, when M and C are represented by M for short, the following equation (3) holds.
D
(
E
(
M
))=
E
(
D
(
M
))=
M
(3)
More specifically, the following equation (4) holds.
M
ed
≡M
(mod
N
) (4)
The procedure for generating the cipher keys e, d and N such that the equation (4) holds for all M is as follows.
<Key Generation in RSA Cryptosystem>
First, arbitrary two large and mutually different prime numbers p and q are selected, and their product N=pq is calculated (first step).
Next, the least common multiplier L of (p−1) and (q−1) is calculated, and an arbitrary small integer e which is relatively prime with respect to L and smaller than L is selected (second step). That is:
L=LCM
(
p−
1,
q−
1) (5)
GCD
(
e, L
)=1, 1
<e<L
(6)
Next, using e and L obtained at the second step, the following congruence (7) is solved to obtain d (third step).
ed≡
1 (mod
L
) (7)
In order to obtain d from the congruence (7), it is possible to use the Euclidean algorithm.
Note that this generation procedure selects e at the second step first and then calculate d at the third step, but it is also possible to select d first and then calculate e if desired.
<Authentication Using RSA Cryptosystem>
The authenticated communication using the RSA cryptosystem is carried out as follows.
First, a sender hashes an authentication message by using a hash function h so as to obtain an authenticator h(M).
Next, the authenticator h(M) is encrypted by using the sender's secret key d so as to obtain an encrypted authenticator S.
Next, a set of the encrypted authenticator S and the authentication message M are sent from the sender to a receiver. That is:
S≡
(
h
(
M
)
d
(mod
N
) (8)
When this set of the encrypted authenticator S and the authentication message M is received, the receiver decrypts the encrypted authenticator S by using the public key e of the sender, so as to obtain the authenticator h(M). That is:
h
(
M
)≡(
S
)
e
(mod
N
) (9)
Next, the received authentication message M is hashed by using the hash function h so as to obtain an authenticator h(M)
o
. Then, the decrypted authenticator h(M) and the authenticator h(M)
o
obtained by hashing the authentication message M are compared to judge the authenticity. Namely, when they coincide the authentication message is judged as authentic and when they don't the authentication message is judged as not authentic.
In this manner, the RSA type public key cryptosystem device can also be used as an authenticated communication device by applying the public key calculation and the secret key calculation in reverse order.
Note that it is also possible to combine this authenticated communication with the secret communication so as to realize the authenticated secret communication in which a set of the encrypted authenticator S and the authentication message M is further encrypted by using the public key of the receiver.
[Basic Principles of Rabin Cryptosystem]
An encryption key of the Rabin cryptosystem is given by a set (b, N) and a decryption key is given by a set (b, p, q), where b and N are public keys and p and q are secret keys and N=pq.
Denoting a plaintext by M and a ciphertext by C, algorithm for the encryption E can be expressed by the following equation (10).
C=E
(
M
)=
M
(
M+b
) (mod
N
) (10)
On the other hand, algorithm for the decryption D corresponds to the solving of the following equation (11) for M.
M
2
+Mb−C≡
0 (mod
N
) (11)
Here, N is a product of two large prime numbers p and q, that is:
N=pq
(12)
so that the above equation (11) is equivalent to the following simultaneous congruences (13) and (14).
M
2
+Mb−C≡
0 (mod
p
) (13)
M
2
+Mb−C≡
0 (mod
q
) (14)
In other words, the decryption in the Rabin cryptosystem can be carried out only by an entity which knows the secret keys p and q. Also, the security of the Rabin cryptosystem relies on the difficulty in factoring N.
The decryption D amounts to obtaining M which simultaneously satisfies both congruences (13) and (14), and can be expressed by the following equations (15) and (16).
M=D
(
C
)=−
b/
2±((
b/
2)
2
+C
) (mod
p
) (15)
M=D
(
C
)=−
b/
2±((
b/
2)
2
+C
) (mod
q
) (16)
Here, b/2 (mod p) in the equation (15) represents an integer s which satisfies 2s≡b (mod p). Note that 2 and p are relatively prime so that it is always possible to obtain only one s.
Also, ((b/2)
2
+C) (mod p) in the equation (15) represents a non-negative integer t which satisfies t
2
≡(b/2)
2
+C (mod p). Assuming that t exists and p is a prime number in a form of 4&agr;+3 (&agr;: integer), (b/2)
2
+C becomes the quadratic residue in mod p so that t can be easily obtained by the following equation (17).
t
=((
b/
2)
2
+C
)
&agr;+1
(mod
p
) (17)
The equation (16) can also be solved similarly as the equation (15).
The encryption function E of the Rabin cryptosystem is defined for all integers in a range of [0, N−1] as should be apparent from the above equation (10), so that every plaintext can be encrypted. Also, the encryption function E is a single-valued function, so that a cip
Naito Shozo
Takagi Tsuyoshi
Barron Jr. Gilberto
Kilpatrick & Stockton LLP
Leaning Jeffrey Scott
Nippon Telegraph and Telephone Corporation
LandOfFree
Secret communication and authentication scheme based on... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Secret communication and authentication scheme based on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Secret communication and authentication scheme based on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2553933