Cryptography – Particular algorithmic function encoding
Reexamination Certificate
2006-05-16
2006-05-16
Revak, Christopher (Department: 2131)
Cryptography
Particular algorithmic function encoding
C708S491000
Reexamination Certificate
active
07046800
ABSTRACT:
Scalable Montgomery multiplication methods and apparatus are provided that are reconfigurable to perform Montgomery multiplication on operands having arbitrary data precision. The methods perform Montgomery multiplication by combining bit-wise and word-wise operations and exhibit pipelined and parallel operation. Apparatus include a control unit that directs bits of an operand to processing elements that receive words of a second operand and a modulus, and produce intermediate values of a Montgomery product. After an intermediate value of a word of a Montgomery product is obtained in a first processing element based on a selected bit of the first operand, the intermediate value is directed to a second processing element and is updated based on another selected bit of the first operand.
REFERENCES:
patent: 5745398 (1998-04-01), Monier
patent: 6240436 (2001-05-01), McGregor
patent: 6282290 (2001-08-01), Powell et al.
Su et al, “An Improved Montgomery's Algorithm for High-Speed RSA Public-Key Cryptosystem”, Jun. 2, 1999, IEEE Tranactions on Very Large Scale Integration (VLSI) Systems, vol. 7, No. 2, p. 280-284.
Koc et al, “A Reduction Method for Multiplication in Finite Fields”, Aug. 1998, Technical Report, p. 1-16.
Menezes, J. et al.,Handbook of Applied Cryptography, CRC Press, 1996, pp. 600-603.
Even, S., “Systolic Modular Multiplication,”Advances in Cryptology, Proceedings Crypto 90, Lecture Notes in Computer Science, vol. 537, A. J. Menzes et al., eds. pp. 619-624 (1991).
Bosselaers, A. et al., “Comparison of three modular reduction functions,”Advances in Cryptology, Proceedings Crypto 93, pp. 175-186 (1996).
Koç, Ç. et al., “Carry-Save Adders for Computing the Product AB Modulo N,”Electron. Lett., 26:899-900 (1990).
Agnew, G. et al., “Arithmetic Operations in GF(2m),”J. of Cryptology, pp. 3-13 (1993).
Koç, Ç. et al., “Analyzing and Comparing Montgomery Multiplication Algorithms,”IEEE Micro, 16:26-33 (Jun. 1996).
Koç, Ç., “Montgomery reduction with even modulus,”IEE Proc.-Comput. Digit. Tech., 141:314-316 (Sep. 1994).
Paar, C., et al., “Fast Arithmetic Architectures for Public-Key Algorithms over Galois Fields GF((2n)m),”Eurocrypt '97, May 11, 1997, pp. 363-378.
Leu, J., et al., “A Scalable Low-Complexity Digit-Serial VLSI Architecture For RSA Cryptosytem,” inIEEE Workshop on Signal Processing Systems1999, pp. 586-595.
Bartee, T., et al., “Computation with Finite Fields,”Inform. and Control6:79-98 (1963).
Walter, C., “Faster Modular Multiplication by Operand Scaling,” inAdvances in Cryptology Proc.Crypto '91, LNCS 576, J. Feigenbaum, ed., 1992, pp. 313-323.
Bajard, J. et al., An RNS Montgomery Modular Multiplication Algorithm,IEEE Trans. Computers47:766-776 (Jul. 1998).
Koç, Ç., et al., “Montgomery Multiplication in GF(2k),”Designs, Codes and Cryptography14:57-69 (Apr. 1998).
Naccache D., et al., “Cryptographic Smart Cards,” IEEE Micro 16 :14-24 (1996).
Kaliski, Jr., B.S., “The Montgomery Inverse and Its Applications,”IEEE Trans. on Computers 44:1064-1065 (Aug. 1995).
Montgomery, P.L., “Modular Multiplication Without Trial Division,”Math. of Computation 44:519-521 (Apr. 1985).
Koç, Ç.K. et al., “Analyzing and Comparing Montgomery Multiplication Algorithms,”IEEE Micro 16:26-33 (Jun. 1996).
Dhem, J. et al., “SCALPS: Smart Card For Limited Payment Systems,”IEEE Micro 16:42-51 (Jun. 1996).
Diffie, W., Hellman, M.E., “New Directions in Cryptography,”IEEE Trans. on Information Theory 22:644-654 (1976).
Rivest, R.L. et al., “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,”Communications of the ACM 21:120-126 (1978).
Koç, Ç.K., Acar, T., “Fast Software Exponentiation in GF(2k)” inProceedings, 13thSymposium on Computer Arithmetic, pp. 225-231 (Jul. 1997) (T. Lang et al., editors).
Hamano, T. et al., “O(n)-Depth Circuit Algorithm for Modular Exponentiation” inProceedings, 12th Symposium on Computer Arithmetic, pp. 188-192 (Jul. 1995) (S. Knowles, W.H. McAllister, editors).
Orup, H., “Simplifying Quotient High radix Modular Multiplication” inProceedings, 12th Symposium on Computer Arithmetic, pp. 193-199 (Jul. 1995) S. Knowles, W.H. McAllister, editors).
Bernal, A., Guyot, A., “Design of a Modular Multiplier Based on Montgomery's Algorithm” in13thConference on Design of Circuits and Integrated Systems, pp. 680-685 (Nov. 1998).
Eldridge, S.E., Walter, C.D., “Hardware Implementation of Montgomery's Modular Multiplication Algorithm,”IEEE Trans. Computers 42:693-699 (Jun. 1993).
Kornerup, P., “High-Radix Modular Multiplication for Cryptosystems” inProceedings, 11th Symposium on Computer Arithmetic, pp. 277-283 (Jun. 1993) (E. Swartzlander et al., editors).
Walter, C.D., “Space/Time Trade-offs for Higher Radix Modular Multiplication Using Repeated Addition,”IEEE Trans. Computers 46:139-141 (1997).
Royo, A., et al., “Design and Implementation of a Coprocessor for Cryptography Applications,”European Design and Test Conference, pp. 213-217 (Mar. 1997).
Koç, Ç.K., Acar, T., Montgomery Multiplication in GF(2k),Designs, Codes and Cryptography 14:57-69 (1998).
Tenca, A.F., “Variable Long-Precision Arithmetic (VLPA) for Reconfigurable Coprocessor Architectures,” Ph.D. Thesis, University of California at Los Angeles (Mar. 1998).
Koç Çetin K.
Tenca Alexandre F.
Klarquist & Sparkman, LLP
Revak Christopher
State of Oregon Acting by and through the State Board of Higher
LandOfFree
Scalable methods and apparatus for Montgomery 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 Scalable methods and apparatus for Montgomery multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scalable methods and apparatus for Montgomery multiplication will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3562190