Cryptography – Particular algorithmic function encoding
Reexamination Certificate
2006-04-11
2006-04-11
Sheikh, Ayaz (Department: 2131)
Cryptography
Particular algorithmic function encoding
C708S103000, C708S135000, C708S200000, C708S490000, C708S501000, C708S502000, C708S503000, C708S504000, C708S505000, C708S523000, C708S524000, C713S174000
Reexamination Certificate
active
07027597
ABSTRACT:
A pre-computation and dual-pass modular operation approach to implement encryption protocols efficiently in electronic integrated circuits is disclosed. An encrypted electronic message is received and another electronic message generated based on the encryption protocol. Two passes of Montgomery's method are used for a modular operation that is associated with the encryption protocol along with pre-computation of a constant based on a modulus. The modular operation may be a modular multiplication or a modular exponentiation. Modular arithmetic may be performed using the residue number system (RNS) and two RNS bases with conversions between the two RNS bases. A minimal number of register files are used for the computations along with an array of multiplier circuits and an array of modular reduction circuits. The approach described allows for high throughput for large encryption keys with a relatively small number of logical gates.
REFERENCES:
patent: 5928315 (1999-07-01), Kobayashi et al.
patent: 5982900 (1999-11-01), Ebihara et al.
patent: 6064740 (2000-05-01), Curiger et al.
patent: 2002/0039418 (2002-04-01), Dror et al.
patent: 2003/0031316 (2003-02-01), Langston et al.
Karl C. Posch “Modulo Reduction in Residue Number Systems” IEEE Transactions on Parallel and Distributed Systems, vol. 6, No. 5, May 1995.
B. Schneier, “Applied Cryptography: Protocols, Algorithms, and Source Code in C”, (New York: John Wiley & Sons), 2nded. 1996, pp. 246-250, pp. 466-474, pp. 483-494.
Cornell University, Computer Science Department, entitled “A Parallel Implementation of RSA”, by David Pearson, dated Jul. 22, 1996, (pp. 1-10).
IEEE Transactions on Computers, vol. 47, No. 7, entitled “An RNS Montgomery Modular Multiplication Algorithm”, by Jean-Claude Bajard, et al., © 1998 IEEE, dated Jul. 1998, (pp. 766-776).
IEEE Transactions on Parallel and Distributed Systems, vol. 6, No. 5, entitled “Modulo Reduction in Residue Number Systems”, by Karl C. Posch, et al., © 1995 IEEE, dated May 1995, (pp. 449-454).
Swiss Federal Institute of Technology (ETH), Integrated Systems Laboratory, entitled “Efficient VLSI Implementation of Modulo (2n ± 1) Addition and Multiplication”, by Reto Zimmerman, undated, (10 pgs.).
RSA Laboratories, RSA Data Security, Inc., entitled “RSA Hardware Implementation”, by Cetin Kaya Koc, Copyright © RSA Laboratories, Version 1.0, dated Aug. 1995,(pp. 1-28).
Electrical & Computer Engineering, Oregon State University, entitled “A Scalable Architecture for Montgomery Multiplication”, by Alexandre F. Tenca and Cetin K. Koc, undated, (15 pgs.).
Proceedings of the 29thAsilomar Conference on Signals, Systems and Computers, School of Electrical Engineering, University of Oklahoma, entitled “A Table-Lookup Scheme for Residue-to-Binary Conversion”, by Chad C. Lamb and L.S. DeBrunner, © 1996 IEEE, (pp. 214-217).
TIMA Laboratory, entitled “Hardware for Computing Modular Multiplication Algorithm”, by Alvaro Bernal and Alain Guyot, undated, (4 pgs).
Dept. Electrical & Electronic Eng., University of Adelaide and Electronic Engineering Division, Cardiff University, entitled “Implementing 1,024-bit RSA Exponentiation on a 32-bit Processor Core”, by B.J. Phillips and N. Burgess, © 2000 IEEE, (11 pgs).
LIM-URA CNRS 1787, CMI, Universite de Provence, France and Dept. of Math and Computer Science, University of Odense, Denmark, entitled “An RNS Montgomery Modular Multiplication Algorithm”, by Jean-Claude Bajard, et al., © 1997 IEEE, (pp. 234-239).
LIRMM, Montpellier, France, Universite de Bretagne Occidentale, Brest, France, and SDU/Odense University, Denmark, entitled “Montgomery Modular Multiplication in Residue Arithmetic”, by Jean-Claude Bajard, et al., dated Nov. 1, 2000, (pp. 1-11).
LIRMM, Montpellier, France, Universite de Bretagne Occidentale, Brest, France, and SDU/Odense University, Denmark, entitled “Modular Multiplication and Base Extensions in Residue Number Systems”, by Jean-Claude Bajard, et al., undated, (7 pgs).
Digital Equipment Corp., Paris Research Laboratory (PRL), entitled “Fast Implementations of RSA Cryptography”, by M. Shand, et al., undated, (9 pgs).
Thesis of Tolga Acar, Electrical & Computer Engineering, Oregon State University, entitled “High-Speed Algorithms & Architectures For Number-Theoretic Cryptosystems”, by Tolga Acar, dated Dec. 4, 1997 © Tolga Acar 1997, (92 pgs).
Maddury Mahesh S.
Stojancic Mihailo M.
Tomei Kenneth J.
Chai Longbit
Cisco Technologies, Inc.
Hickman Palermo & Truong & Becker LLP
Sheikh Ayaz
LandOfFree
Pre-computation and dual-pass modular arithmetic operation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pre-computation and dual-pass modular arithmetic operation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pre-computation and dual-pass modular arithmetic operation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3576558