Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-01-11
2002-08-13
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06434585
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is related to co-pending and commonly assigned application Ser. No. 08/828,368, entitled “High-Speed Modular Exponentiator,” by Gregory A. Powell, Mark W. Wilson, Kevin Q. Truong, and Christopher P. Curren, filed Mar. 28, 1997, now U.S. Pat. No. 6,282,290 which application is hereby incorporated by reference herein.
This application is also related to co-pending and commonly assigned application Ser. No. 09/050,573, entitled “High Speed Montgomery Value Calculation,” by Matthew S. McGregor, filed Mar. 30, 1998, now U.S. Pat. No. 6,240,436 which application is also hereby incorporated by reference herein.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to cryptographic systems, and more particularly, to a highly efficient multiplier for performing modular reduction operations integral to cryptographic key calculations.
2. Description of Related Art
Cryptographic systems are commonly used to restrict unauthorized access to messages communicated over otherwise insecure channels. In general, cryptographic systems use a unique key, such as a series of numbers, to control an algorithm used to encrypt a message before it is transmitted over an insecure communication channel to a receiver. The receiver must have access to the same key in order to decode the encrypted message. Thus, it is essential that the key be communicated in advance by the sender to the receiver over a secure channel in order to maintain the security of the cryptographic system; however, secure communication of the key is hampered by the unavailability and expense of secure communication channels. Moreover, the spontaneity of most business communications is impeded by the need to communicate the key in advance.
In view of the difficulty and inconvenience of communicating the key over a secure channel, so-called public key cryptographic systems are proposed in which a key may be communicated over an insecure channel without jeopardizing the security of the system. A public key cryptographic system utilizes a pair of keys in which one is publicly communicated, i.e., the public key, and the other is kept secret by the receiver, i.e., the private key. While the private key is mathematically related to the public key, it is practically impossible to derive the private key from the public key alone. In this way, the public key is used to encrypt a message, and the private key is used to decrypt the message.
Such cryptographic systems often require computation of modular exponentiations of the form y=b
e
mod n, in which the base b, exponent e and modulus n are extremely large numbers, e.g., having a length of 1,024 binary digits or bits. If, for example, the exponent e were transmitted as a public key, and the base b and modulus n were known to the receiver in advance, a private key y could be derived by computing the modular exponentiation. It would require such a extremely large amount of computing power and time to factor the private key y from the exponent e without knowledge of the base b and modulus n, that unauthorized access to the decrypted message is virtually precluded as a practical matter.
A drawback of such cryptographic systems is that calculation of the modular exponentiation remains a daunting mathematical task even to an authorized receiver using a high speed computer. With the prevalence of public computer networks used to transmit confidential data for personal, business and governmental purposes, it is anticipated that most computer users will want cryptographic systems to control access to their data. Despite the increased security, the difficulty of the modular exponentiation calculation will substantially drain computer resources and degrade data throughput rates, and thus represents a major impediment to the widespread adoption of commercial cryptographic systems.
Accordingly, a critical need exists for a high speed modular exponentiation method and apparatus to provide a sufficient level of communication security while minimizing the impact to computer system performance and data throughput rates.
SUMMARY OF THE INVENTION
In accordance with the teachings of the present invention, a highly efficient method and apparatus is disclosed for performing operations required for modular exponentiation. The apparatus is especially well suited for implementing multiplications using the Montgomery algorithm.
The efficient multiplier architecture uses a preload register, coupled to a multiplier at a second input port via a KN bit bus to load the value of the “a” multiplicand in the multiplier in a single clock pulse. The “b” multiplicand (which is also KN bits long) is supplied to the multiplier N bits at a time from a memory via an N bit bus coupled to a multiplier. The multiplier multiplies the N bits of the “b” multiplicand by the KN bits of the “a” multiplicand and provides that product at a multiplier output N bits at a time, where it can be supplied to the memory.
The efficient multiplication method using the foregoing architecture is also described. The method begins by providing KN bits of the multiplicand “a” from a preload register to a second multiplier input port in a single clock pulse. Then, N bits of the multiplicand “b” are provided to a first multiplier input port, also in a single clock pulse. The KN bits of the number “a” are multiplied by the K bits of the number “b” until all of the KN bits of the “b” multiplicand are provided to the first multiplier input port and multiplied by the KN bits of the “a” multiplicand. When completed, these operations result in an output number, which is then transmitted to the memory, where it can be made available for further processing.
In accordance with the deterministic behavior of the Montgomery algorithm, one embodiment of the present invention loads a predicted (future) value for multiplicand “a” into the preload register while multiplication operations on the current “a” and “b” multiplicands are being performed. This technique further reduces the clock cycles necessary to load and multiply the parameters.
A more complete understanding of the computationally efficient multiplier will be afforded to those skilled in the art, as well as a realization of additional advantages and objects thereof, by a consideration of the following detailed description of the preferred embodiment. Reference will be made to the appended sheets of drawings which will first be described briefly.
REFERENCES:
patent: 5121431 (1992-06-01), Wiener
patent: 5274707 (1993-12-01), Schlafly
patent: 5420815 (1995-05-01), Nix et al.
patent: 5794028 (1998-08-01), Tran
Comba, P.G., “Exponentiation Cryptosystems on the IBM PC”,IBM Systems Journal, vol. 29, No. 4, Jan. 1, 1990, pp. 526-538.
Bond, Dieter et al., “Optimized Software Implementations of the Modular Exponentiation on General Purpose Microprocessors”,Computers & Security Journal, vol. 8, No. 7, Nov. 1, 1989, pp. 621-630.
Shand, M. et al., “Fast Implementations of RSA Cryptography”, Proceedings of the Symposium on Computer Arithmetic, Windsor, Ontario, 11thSymposium, Jun. 29-Jul. 2, 1993, IEEE, pp. 252-259.
Quisquater, J.J. et al., “Fast Decipherment Algorithm for RSA Public-Key Cryptosystem”,Electronics Letters, vol. 18, No. 21, Oct. 14, 1982, pp. 905-907.
Koc, Cetin Kaya et al., “Analyzing and Comparing Montgomery Multiplication Algorithms”,IEEE Micro, vol. 16, No. 3, Jun. 1, 1996, pp. 26-33.
Copy of European Search Report for related European Patent Application No. 98 301 533.0.
Le Thuan P.
McGregor Matthew Scott
Foley & Lardner
Malzahn David H.
Rainbow Technologies, Inc.
LandOfFree
Computationally efficient modular multiplication method 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 Computationally efficient modular multiplication method and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computationally efficient modular multiplication method and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2905891