Circuits for calculating modular multiplicative inverse

Details Circuits for calculating modular multiplicative inverse Circuits for calculating modular multiplicative inverse

2005-12-20

2005-12-20

Barrón, Jr., Gilberto (Department: 2131)

Cryptography

Particular algorithmic function encoding

C708S135000, C708S209000, C708S103000, C380S030000

Reexamination Certificate

active

06978016

ABSTRACT:
The modular exponentiation function used in public key encryption and decryption systems is implemented in a standalone engine having at its core modular multiplication circuits which operate in two phases which share overlapping hardware structures. The partitioning of large arrays in the hardware structure, for multiplication and addition, into smaller structures results in a multiplier design which includes a series of nearly identical processing elements linked together in a chained fashion. As a result of the two-phase operation and the chaining together of partitioned processing elements, the overall structure is operable in a pipelined fashion to improve throughput and speed. The chained processing elements are constructed so as to provide a partitionable chain with separate parts for processing factors of the modulus. In this mode, the system is particularly useful for exploiting characteristics of the Chinese Remainder Theorem to perform rapid exponentiation operations. A checksum mechanism is also provided to insure accurate operation without impacting speed and without significantly increasing complexity. While the present disclosure is directed to a complex system which includes a number of features, the present application is particularly directed to the incorporation and integration of circuits used for calculating a modular multiplicative inverse used as an input parameter to the process.

REFERENCES:
patent: 5321752 (1994-06-01), Iwamura et al.
patent: 5448639 (1995-09-01), Arazi
patent: 5513133 (1996-04-01), Cressel et al.
patent: 5764554 (1998-06-01), Monier
patent: 6546104 (2003-04-01), Shimbo et al.
patent: 2002/0059353 (2002-05-01), Koc et al.
Modular Multiplication Without Trial Division (Montgomery, Mathematics of Computation, vol. 44, No. 170, pp. 519-521, Apr. 1985).
Kornerup, Peter, “A Systolic, Linear-Array Multiplier for a Class of Right-Shift Algorithms,” IEEE Transacti ns on Computers, vol. 43, No. 8, Aug., 1994, pp. 892-898.
Montgomery, Peter, “Modular Multiplication Without Trial Division, ” Mathematics of Computation, vol. 44, No. 170, Apr. 1985, pp 519-521.

Affiliated with

Also associated with

Rating

Circuits for calculating modular multiplicative inverse does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Circuits for calculating modular multiplicative inverse, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuits for calculating modular multiplicative inverse will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3519643