Circuit and method for fast modular multiplication

Cryptography – Particular algorithmic function encoding – Public key

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFUS-PAI-O-2857288

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.