Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
2005-11-08
2005-11-08
Caldwell, Andrew (Department: 2137)
Cryptography
Particular algorithmic function encoding
Public key
C708S491000, C708S606000
Reexamination Certificate
active
06963645
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 comprising 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 a method for performing modular exponentiation which takes advantage of processing element chain partitioning and the Chinese Remainder Theorem.
REFERENCES:
patent: 5321752 (1994-06-01), Iwamura et al.
patent: 5513133 (1996-04-01), Cressel et al.
patent: 5742530 (1998-04-01), Gressel et al.
patent: 5764554 (1998-06-01), Monier
patent: 6282290 (2001-08-01), Powell et al.
patent: 2332542 (1999-06-01), None
Compaq Computer Corporation. “Cryptography Using Compaq MultiPrime Technology in a Parallel Processing Environment”. Electronic Commerce Technical Brief, Jan. 2000.
Schneier, Bruce. Applied Cryptography, 2nd Edition. John Wiley and Sons, Inc., 1996. pp. 249-250, 466-474.
Menezes, et al. Handbook of Applied Cryptography. CRC Press, 1997. pp. 610-613.
Tenca, Alexandre and Cetin Koc. “A Scalable Architecture for Montgomery Multiplication”. Cryptographic Hardware and Embedded Systems: First International Workshop, CHES '99, Aug. 1999. pp. 94-108.
Koc, et al. “Analyzing and Comparing Montgomery Multiplication Algorithms”. IEEE Micro, vol. 16, Issue 3, Jun. 1999. pp. 26-33.
Kornerup, Peter, “A Systolic, Linear-Array Multiplier for a Class of Right-Shift Algorithms,” IEEE Transactions 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.
Chen Chin-Long
Condorelli Vincenzo
Search Douglas S.
Caldwell Andrew
Cutter Lawrence D.
Davis Zachary A
International Business Machines - Corporation
LandOfFree
Method for implementing the chinese remainder theorem does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for implementing the chinese remainder theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for implementing the chinese remainder theorem will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3478097