Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-10-05
2002-07-02
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06415310
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a remainder calculating method and apparatus, a modular-multiplication method and apparatus, and a recording medium, which are suitable for a remainder calculation, a modular-multiplication in RSA encryption processing, elliptic curve encryption processing of a public key cryptosystem. In particular, the present invention relates to a remainder calculating method and apparatus, a modular-multiplication method and apparatus, and a recording medium, which can carry out a calculation at a high speed with the use of Montgomery algorithm (see Modular Multiplication Without Trial Division. Peter L. Montgomery, Mathematics of Computation, Volume 44, Number 170, April 1985 pp. 519-521).
In recent years, the development of a computer network has rapidly increased an opportunity to retrieve a data base, or to send and receive electronic information such as an electronic mail and electronic news via a network. Moreover, an on-line shopping service or the like is provided by making use of the computer network. However, with the development of the computer network, the following problems have been pointed out; more specifically, electronic data on the network is tapped or falsified, and a certain person pretends to be another person so as to receive service without charge. In particular, tapping is easy in a network using a radio communication; for this reason, it is desired to take suitable measures for preventing the tapping.
In order to solve the aforesaid problems, an encryption electronic mail system and a user certification system using cryptography are proposed, and then, are being introduced into various networks. Therefore, it is a matter of course that encryption is an indispensable technology in the computer network. As one of the above cryptography, there is a public key cryptosystem which is suitable for digital signature, that is, for certification. However, a large quantity of processing is required for encryption/decryption;
for this reason, it is desired to carry out the encryption/decryption processing at a high speed, and various high-speed algorithms have been published.
The above cryptosystem is largely classified into two, that is, a secret key cryptosystem and a public key cryptosystem. The secret key cryptosystem is a system such that a sender and a receiver mutually have the same cryptographic key so as to carry out a cryptographic communication. More specifically, in the secret key cryptosystem, a certain message is encrypted on the basis of a secret cryptographic key, and thereafter, is sent to a receiver. Then, the receiver decrypts the encrypted message with the use of the cryptographic key so as to return it to the original message, and thus, obtains an information.
The public key cryptosystem is a system such that a sender encrypts a message with the use of a published receiver's public key, so as to send it to the receiver, and then, the receiver decrypts the encrypted message with the use of his secret key, and thus, a communication is performed. More specifically, in the public key cryptosystem, the public key is a key used for encryption, and the secret key is a key used for decrypting a message encrypted by the public key, and further, the message encrypted by the public key can be decrypted by only secret key.
In the aforesaid secret key cryptosystem, a key, in which a private individual must keep in secret, requires by the number of communicating partners, and the total number of required keys is n(n−1)/2 in the case of n person network. Moreover, the secret key cryptosystem has a problem that a secret key must be distributed according to a certain method with respect to a partner who makes a communication for the first time. In order to solve the problem, a key control center is established in a large scale network, and the private individual keeps only secret key between the center and himself. In the case of carrying out a cryptographic communication, a method of obtaining a secret key with the communicating partner from the center is employed. In this case, the total number of secret keys is n.
On the other hand, in the public key cryptosystem, a key, in which a private individual should keep in secret, is only his own secret key, and the total number of required secret keys is n in the case of n person network. Moreover, a public key may be only distributed with respect to a partner who makes a communication for the first time, and a key control center is established. Then, n users' public keys are registered in a public board, and a method of obtaining a public key of the communicating partner from the center is employed. In this case, the center merely prevents a falsification of the public key, and has no need of keeping the public key in secret. However, in the public key cryptosystem, the number of bits of the public key is much as compared with the secret key cryptosystem; for this reason, a file size required for storing it becomes large.
In the case of certification, in the secret key cryptosystem, for example, a message to be sent is compressed and converted with the use of a secret key, and then, is sent in a state of being added to a sending text. In a receiving end, the message is compressed and converted, and then, makes a comparison. In this case, however, send/receive is carried out with the use of the same key; for this reason, a receiver can counterfeit a certification data. On the contrary, the public key cryptosystem makes use of the feature that it is only person himself to encrypt the message with the use of the secret key. A sender compresses and converts the message, and then, encrypts it with the use of the secret key, and thus, sends it in a state of being added to a sending text. On the other hand, the receiver decrypts the added data with the use of sender's public key, and then, makes a comparison with the message similarly compressed and converted. In this case, the receiver can not make an illegal act.
As described above, in the certification system, the technology of public key cryptosystem is indispensable. However, the public key cryptosystem has a severe problem that a large quantity of processing is required for encryption/decryption. For this reason, in general, the secret key cryptosystem of high speed processing is used for an encryption of message, and the public key cryptosystem is used for certification, and thus, the above two cryptosystems are often used in combination with each other.
The public key cryptosystem mainly includes an RSA cryptosystem and an elliptic curve cryptosystem. In particular, the elliptic curve cryptosystem is noticeable because a small number of bits is required for obtaining the same safety as the RSA cryptosystem. In the elliptic curve cryptosystem, there are a cryptosystem defined on a prime field and a cryptosystem defined on two extension fields, and both cryptosystems are based on a discrete logarithm problem on an elliptic curve. A basic calculation of the elliptic curve cryptosystem is an addition of points on an elliptic curve. The following is a description on an additive algorithm in points on an elliptic curve on a prime field. (Additive algorithm in points on an elliptic curve on a prime field)
elliptic curve: y
2
=x
3
+ax+b (mod N), N: prime number
two points to be added: (X
1
, y
1
), (x
2
, y
2
)
additive result: (x
3
, y
3
)
An addition on points is expressed as follows
x
3
=&lgr;
2
−x
1
−x
2
(mod
N
);
y
3
=&lgr;(x
1
−x
3
)−y
1
(mod
N
);
&lgr;=(
y
2
−y
1
)/(
x
2
−x
1
) (mod
N
)
In general, N, a, b, x
1
, y
1
, x
2
and y
2
are integers each of which has a size of about 160 bits. In the elliptic curve cryptosystem, a great many of the above basic calculations are repeatedly carried out; as a result, a large quantity of multiple precision multiplications and remainder calculations are carried out. For this reason, various high-speed methods such as approximate method, remainder table system, Montgomery&apos
Takenaka Masahiko
Torii Naoya
Fujitsu Limited
Malzahn David H.
Staas & Halsey , LLP
LandOfFree
Remainder calculating method, modular-multiplication method,... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Remainder calculating method, modular-multiplication method,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Remainder calculating method, modular-multiplication method,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2826244