High speed modular exponentiator

Details High speed modular exponentiator High speed modular exponentiator

1997-03-28

2001-08-28

Swann, Tod (Department: 2132)

Cryptography

Particular algorithmic function encoding

C380S285000, C380S260000, C380S044000, C380S045000, C380S030000, C708S808000, C708S851000, C713S152000, C713S400000

Reexamination Certificate

active

06282290

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to cryptographic systems, and more particularly, to a highly efficient modular exponentiator 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 modular exponentiator for a cryptographic system is provided.
The cryptographic system comprises a processing unit having a modular exponentiator that is adapted to receive a first communicated signal and derive a second signal therefrom by computation of a modular exponentiation of the form b
e
mod n based on the first signal. The modular exponentiator divides the modular exponentiation into first and second portions respectively having a modulus value of approximately half of an original modulus value n of the modular exponentiation. Each portion of the modular exponentiation is factored into respective pluralities of smaller modular exponentiations having precalculated exponent values. The respective pluralities of smaller modular exponentiations are then calculated and recombined together.
Particularly, the modular exponentiation is divided into portions in accordance with the Chinese remainder theorem, in which the first portion of the modular exponentiation comprises a component b
e
p
mod p and the second portion of the modular exponentiation comprises a component b
e
q
mod q in which p and q are prime numbers having a product equal to n. The exponents e
p
and e
q
of the modular exponentiation portions relate to the original exponent e as e mod (p−1) and e mod (q−1), respectively. The exponents e
p
and e
q
are factored by use of an exponent bit-scanning technique in which the exponent is loaded into a register having a shiftable window of a size substantially less than the corresponding size of the register. In the exponent bit-scanning technique, a pre-computed value is selected which comprises the base b raised to a selected power equivalent to a portion of the exponent e read through the window. The pre-computed value is squared a number of times corresponding to successive bit shifts of the window relative to the exponent e. The multiplying operation utilizes a Montgomery multiplication process having a speed-up routine for squaring operations.


REFERENCES:
patent: 4200770 (1980-04-01), Hellman et al.
patent: 5400403 (1995-03-01), Fahn et al.
Quisquater et al., Fast Decipherment for RSA Public-Key Cryptosystem, Oct. 14, 1982, Electronic Letters, vol. 18, No. 21, pp. 905-907.*
Menezes et al., Handbook of Applied Cryptography, 1996, pp. 613-627.*
Schneier, Applied Cryptography, Second Edition, 1995, pp. 242-245, 249, 250, and 466-470, Oct. 1982.*
MicroSentinelUX™, Securing the future of software—Developer's Guide, Rainbow Technologies, Irvine, CA 92718, 1992; 107 pages.
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.
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.
Copy of European Search Report for related European Patent Application No. 98 301 533.0.
Victor, An Efficient RSA Hardware Implementation, by Orup et al., Lecture Notes In Computer Science (Advances In Cryptology-Eurocrypt '90), Springer- Verlag, 1991, pp. 245-252.
Fast Implementation Of RSA Cryptography, by Shand et al., 11th Symposium On Computer Arithmetic, IEEE, pp. 252-259.
Analyzing And Comparing Montgomery Multiplication Algorithms, by Koc et al., IEEE Micro, Jun. 1996, pp. 26-33.

Affiliated with

Also associated with

Rating

High speed modular exponentiator 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 modular exponentiator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed modular exponentiator will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2536691