Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1999-03-26
2002-05-28
Barron, Jr., Gilberto (Department: 2131)
Cryptography
Particular algorithmic function encoding
C380S028000, C380S030000, C708S492000, C708S606000
Reexamination Certificate
active
06396926
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a scheme for fast realization of encryption, decryption and authentication which is suitable for data concealment and communicating individual authentication in communications for a digital TV, a pay-per-view system of the satellite broadcast, a key distribution in the information distribution, electronic mails, electronic transactions, etc.
2. Description of the Background Art
In recent years, in the field of communications, various types of cryptographic techniques have been proposed because the cryptographic technique can be effectively used for the protection of secrecy between communicating parties such as the concealment of information to be transmitted. The performances of such a cryptographic technique can be evaluated in terms of the security level of cryptosystem and the speed of encryption/decryption. Namely, the cryptosystem for which the security level is high and the encryption/decryption speed is high is a superior cryptosystem.
Among such cryptographic techniques, there is a type of public key cryptosystem that uses the modular exponent calculations, known as RSA (Rivest Shamir Adleman) cryptosystem, which is already in practical use. In this RSA cryptosystem, it has been shown that the plaintext can be obtained from the ciphertext if the prime factoring of the public key can be made (see R. Rivest, A. Shamir and L. Adleman; “A method for obtaining digital signatures and public-key cryptosystems”, Comm. ACM, Vol. 21, No. 2, pp. 120-126 (1978)).
The public key cryptosystem such as RSA cryptosystem has its security based on the computational difficulty for obtaining the secret key from the public key which is a publicly disclosed information, so that the security level can be increased as much when a size of the public key is increased. On the other hand, the RSA cryptosystem has been associated with a drawback that it requires a considerable amount of time for encryption/decryption because it carries out higher degree modular exponent calculations and therefore the required amount of calculations is large.
The encryption/decryption can be made faster by reducing the degree of the modular exponent calculations, for example, but that will require the reduction of the size of the public key and that in turn causes the lowering of the cryptosystem security.
In the following, the RSA cryptosystem will be described in further detail.
First, mutually different arbitrary prime numbers p and q are set as the first secret key, and the first public key n is obtained as:
n=pq
while the least common multiple L of (p−1) and (q−1) is obtained as:
L=
1 cm(
p−
1
, q−
1).
Then, an arbitrary integer e is set as the second public key, and the second secret key d given by:
ed≡
1(mod
L
)
is obtained using the Euclidean division algorithm.
Then, a plaintext M and its ciphertext C can be expressed as follow:
C≡M
e
(mod
n
),
M≡C
d
(mod
n
).
Here, the value of the second public key e can be rather small like 13, for instance, so that the encryption processing can be made very fast, but the value of the second secret key d has a size nearly equal to n so that the decryption processing will be quite slow.
On the other hand, the processing amount of the modular exponent calculations is proportional to the cube of the size of a number, so that by utilizing this property, the Chinese remainder theorem can be used in order to make the decryption processing faster.
The decryption processing using the Chinese remainder theorem proceeds as follows.
d
p
≡d
(mod
p−
1),
d
q
≡d
(mod
q−
1),
uq
≡1(mod
p
),
M
p
≡C
dp
(mod
p
),
M
q
≡C
dq
(mod
q
),
M
≡((
M
p
−M
q
)
u
(mod
p
))
q+M
q
,
where u is an inverse of q modulo p.
Here, the size of each of p, q, d
p
and d
q
is a half of the size of n so that the modular exponent calculations module p or q can be processed eight times faster, and as a result, the decryption processing as a whole can be made four times faster.
Also, the RSA cryptosystem can be easily cryptoanalyzed if the prime factoring of n can be made. Currently, the potentially threatening prime factoring algorithms include the number field sieve method and the elliptic curve method.
The required amount of calculations is of a quasi-exponential order of the size of n in the number field sieve method and of a quasi-exponential order of the size of a prime number in the elliptic curve method. The elliptic curve method is practically not a problem because of its high order calculations and large coefficients. On the other hand, the number field sieve method has a record for the prime factoring of the largest number realized so far, which is about 140 figures in decimal. Consequently, attacks using these methods are not threatening in practice if n is 1024 bits or so.
In addition, there are cases where a public key cryptosystem apparatus can be used as an authentication apparatus by reversing the public key and secret key calculations in general.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a new scheme for encryption, decryption and authentication which is capable of overcoming the problems associated with the conventionally known RSA cryptosystem as described above.
More specifically, objects of the present invention are:
(1) to realize an encryption/decryption scheme which has the same security level compared with the known RSA cryptosystem on rational integer ring,
(2) to realize an encryption/decryption scheme for which the encryption/decryption processing is faster than the conventional RSA cryptosystem,
(3) to realize an encryption/decryption scheme which can also be utilized as an authentication scheme such that a single apparatus can be used for both the cipher communications and the authentication, and
(4) to realize an authentication scheme for which the authenticator generation and the verification are faster than the known authentication scheme based on the conventional RSA cryptosystem.
According to one aspect of the present invention there is provided an encryption method, comprising the steps of: setting N (≧2) prime numbers p
1
, p
2
, . . . , p
N
as a first secret key, and a product p
1
k1
p
2
k2
. . . p
N
kN
as a first public key n, where k
1
, k
2
, . . . , kN are arbitrary positive integers; determining a second public key e and a second secret key d which satisfy:
ed≡
1(mod
L
)
where L is a least common multiple of p
1
−1, p
2
−1, . . . , p
N−
1, using the first secret key; and obtaining a ciphertext C from a plaintext M according to:
C≡M
e
(mod
n
)
using the first public key n and the second public key e.
According to another aspect of the present invention there is provided a decryption method for decrypting a ciphertext C obtained from a plaintext M according to:
C≡M
e
(mod
n
)
using a first secret key given by N (≧2) prime numbers p
1
, p
2
, . . . , p
N
, a first public key n given by a product p
1
k1
p
2
k2
. . . p
N
kN
where k
1
, k
2
, . . . , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy:
ed≡
1(mod
L
)
where L is a least common multiple of p
1
−1, p
2
−1, . . . , p
N
−1, the method comprising the steps of: obtaining residues M
p1k1
, M
p2k2
, . . . , M
pNkN
modulo p
1
k1
, p
2
k2
, . . . , p
N
kN
respectively, of the plaintext M using a prescribed loop calculation with respect to the first secret key p
1
, p
2
, . . . , p
N
; and recovering the plaintext M by applying Chinese remainder theorem to the residues M
p1k1
, M
p2k2
, . . . , M
pNkN
.
According to another aspect of the present invention there is provided an authentication method for authenticating an authentication message sent from a sender to a receiver, comprising the steps of: (a) setting at the sender side a first secret key given by N (≧2) prime numbers p
1
, p
2
, . . . , p
N
, a first public key n given by a product
Naito Shozo
Takagi Tsuyoshi
Barron Jr. Gilberto
Kilpatrick & Stockton LLP
Nippon Telegraph & Telephone Corporation
Seal James
LandOfFree
Scheme for fast realization of encrytion, decryption 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 Scheme for fast realization of encrytion, decryption and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheme for fast realization of encrytion, decryption and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2860656