Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-03-30
2001-05-29
Swann, Tod R. (Department: 2767)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C380S046000, C380S028000
Reexamination Certificate
active
06240436
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to cryptographic systems, and more particularly, to a method and apparatus for performing high speed computations of a value used in execution of the Montgomery algorithm for an arbitrary modulus size.
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. As a representative example, consider an exponentiation 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.
One technique in reducing the computations required to perform cryptographic evaluations is to use an algorithm postulated by P. L. Montgomery in “Modular Multiplication without Trial Division,” published in the Mathematics of Computation, vol. 48, n. 177, January 1987, pp. 243-264, which is hereby incorporated by reference herein. This algorithm is known as “Montgomery's Method.” To perform this algorithm, a Montgomery value defined as 2
2k
mod(n) must be computed, where n is the modulus, k is the number of bits representing the n modulus, and the expression A mod(n) denotes the modular reduction of A by n.
One of the more computationally intense calculations performed in determining the Montgomery value is the computation of 2
k+1
mod(n), or the modular reduction of 2
k+1
by n. The number of subtractions required to complete the reduction are a function of both the modulus n and the operand size of the processor, and hence, for a given value of modulus n, a processor size of suitable operand size to reduce the number of required computations can be selected. Unfortunately, cryptographic systems usually require modular reduction capability for arbitrary modulus values, and processors with fixed operand sizes are poorly suited to efficiently compute 2
k+1
mod(n) in such cases.
As is apparent from the above, there is a need in the cryptographic art for an apparatus and method for performing modular reductions and for determining the value of 2
2k
mod(n) for arbitrary modulus sizes in conjunction with fixed processor operand capacities. The present invention satisfies that need.
SUMMARY OF THE INVENTION
In accordance with the teachings of the present invention, a method and apparatus for performing high-speed computations of a Montgomery value is provided.
The method begins by configuring a first register such that there is a one in the 2
(h*m)+1
bit position of the first register and a zero in all less significant registers in the register, where m is a processor operand size and b is the smallest integer such that the product (h*m) is not less than k. Then, k bits representing the value of the modulus n are loaded into a second register and shifted in the most significant bit direction until the most significant non-zero bit of n is at the (h*m)−1 bit position. This shifts the most significant bit of modulus n in such a way as to assure that the subtractive operations which follow are reduced.
Next, the value in the second register (representing the modulus n) is repeatedly subtracted from the first register (which contains 2
(h*m)+1
) until the value of the first register is less than the value of the modulus n. At the end of this step, the value of 2
(h*m)+1
mod(n) is in the first register. Then, this value is repeatedly squared log
2
(k) times, yielding 2
2k
mod(n).
The apparatus comprises a processor for accepting and performing operations on an m-bit operand where m is an integer greater than one, a first register for storing a number representing 2
(h*m)+1
, and a second register including a first integer multiple of m bit positions. The second register is configured to store an arbitrary modulus n such that the most significant non-zero bit of the modulus n is at a bit position defined by a second integer multiple of m. In one embodiment, the foregoing bit configuration of n in the second register is provided by bit shifting the modulus n a suitable number of times.
REFERENCES:
patent: 5274707 (1993-12-01), Schlafly
patent: 5513133 (1996-04-01), Cressel et al.
patent: 0 601 907 A2 (1994-06-01), None
patent: 0 785 503 A1 (1997-07-01), None
Montgomery, “Modular Multiplication Without Trial Division,” Mathematics of Computation, vol. 44, No. 170, pp. 519-521, Apr. 1985.*
European Search Report in EP 98 30 8207 dated Jul. 27, 1999.
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, 11th Symposium, 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.
Foley & Lardner
Kabakoff Steve
Rainbow Technologies, Inc.
Swann Tod R.
LandOfFree
High speed montgomery value calculation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High speed montgomery value calculation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed montgomery value calculation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2462415