Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
1998-07-22
2002-03-12
Barron, Jr., Gilberto (Department: 2132)
Cryptography
Particular algorithmic function encoding
Public key
C708S491000, C708S492000, C713S174000
Reexamination Certificate
active
06356636
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates, in general, to multipliers and, more particularly, to a cryptographic multiplier.
Rivest-Shamir-Adleman (RSA) is a widely used cryptographic algorithm that provides high security for digital data transfers between electronic devices. The modular exponentiation mathematics of the RSA algorithm can be efficiently computed using Montgomery's method for modular reduction based on a hardware multiplier. Modular exponentiation of large integers can be efficiently computed with repeated modular multiplications and the efficiency of the overall RSA computation is directly related to the speed of the multiplier. Hardware multiplier architectures use pipelining techniques for the massive parallel computations of the Montgomery algorithm. A pipelined hardware multiplier computing the Montgomery algorithm can provide speed and silicon area tradeoffs that provide both a high performance and a cost effective solution. In addition, the pipelined integer modular multiplier offers lower power which is required for many applications.
The cryptosystem facilitated by the RSA algorithm offers a high level of security but is expensive to implement. Although the mathematics of the RSA algorithm with modular exponentiation are straight forward, efficient hardware implementation is not straight forward. With increasing demand for faster cryptographic operations and higher performance, hardware modular multiplier architecture improvements are needed to ensure high levels of security.
Accordingly, it would be advantageous to have a modular exponentiation and multiplication system that achieves high performance, low cost, and low-power for implementation in an integrated circuit. A need exists for a multiplication system that achieves high performance by computing the Montgomery algorithm in fewer clock cycles than in prior art systems. A further need exists for a multiplication system that is adaptable to operands having an increased number of bits.
REFERENCES:
patent: 4064400 (1977-12-01), Akushsky et al.
patent: 4722067 (1988-01-01), Williams
Eldridge et al, Hardware Implementation of Montgomery's Modular Multiplication Algorithm, IEEE, 1993.*
Koc et al., Carry-save Adders for Computing the product AB mod N, Electronics Letters, pp. 899-900, 1990.*
Iwamura et al., High-Speed Implementation Methods for RSA Scheme, EUROCRYPT92, 1992.*
Seong-Min, et al. New Modular Multiplication Algorithm for Fast Modular Exponetiation, EUROCRYPT96, 1996.*
C. Walter, Montgomery's Multiplication Technique: How to Make it Smaller and Faster, 1999.*
Jia-Lin, A Pipelined Architecture of Fast Modular Multiplication for RSA Cryptopgraphy, 1995.
Buss John Michael
Dworkin James Douglas
Foster Robert I.
Tesch Rodney C.
Torla Michael J.
Barron Jr. Gilberto
King Robert L.
LandOfFree
Circuit and method for fast modular multiplication does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circuit and method for fast modular multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit and method for fast modular multiplication will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2857288