Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2003-03-11
2008-12-02
Ngo, Chuong D (Department: 2193)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S492000, C380S028000
Reexamination Certificate
active
07461115
ABSTRACT:
Modular multiplication of two elements X(t) and Y(t), over GF(2), where m is a field degree, may utilize field degree to determine, at least in part, the number of iterations. An extra shift operation may be employed when the number of iterations is reduced. Modular multiplication of two elements X(t) and Y(t), over GF(2), may include a shared reduction circuit utilized during multiplication and reduction. In addition, a modular multiplication of binary polynomials X(t) and Y(t), over GF(2), may utilize the Karatsuba algorithm, e.g., by recursively splitting up a multiplication into smaller operands determined according to the Karatsuba algorithm.
REFERENCES:
patent: 4251875 (1981-02-01), Marver et al.
patent: 4852098 (1989-07-01), Brechard et al.
patent: 2002/0044649 (2002-04-01), Gallant et al.
patent: 2003/0093450 (2003-05-01), Chen
patent: 2003/0123655 (2003-07-01), Lambert et al.
patent: 2004/0158597 (2004-08-01), Ye et al.
Alekseev, V. B., “From the Karatsuba Method for Fast Multiplication of Numbers to Fast Algorithms for Discrete Functions,” Proceedings of the Steklov Institute of Mathematics, vol. 218, 1997, pp. 15-22.
Guajardo, Jorge, and Paar, Christof, “Efficient Algorithms for Elliptic Curve Cryptosystems,” ECE Department, Worcester Polytechnic Institute, 100 Institute Road, Worcester, MA 01609, USA, pp. 1-16 (CRYPTO '97, Springer-Verlag, LNCS 1294, pp. 342-356, 1997).
Weimerskirch, André and Paar, Christof, “Generalizations of the Karatsuba Algorithm for Polynomial Multiplication,” Communication Security Group, Department of Electrical Engineering & Information Sciences, Ruhr-Universität Bochum, Germany; submitted to Design, Codes and Cryptography, Mar. 2002, pp. 1-23.
Blake-Wilson, S., “Additional ECC Groups for IKE”, IPSec Blake-Wilson, Dierks, Hawk—Working Group, Jul. 23, 2002, pp. 1-17.
Gupta, V., “ECC Cipher Suites for TLS”, Blake-Wilson, Dierks, Hawk—TLS Working Group, Aug. 2002, pp. 1-31.
Standards for Efficient Cryptography, “SEC 2: Recommended Elliptic Curve Domain Parameters”, Certicom Research, Sep. 20, 2000, pp. i-45.
“RFC 2246 on the TLS Protocol Version 1.0”, http://www.ietf.org/mail-archive/ietf-announce/Current/msg02896.html, Mar. 26, 2003, 2 pages, including Dierks, T., “The TLS Protocol Version 1.0”, Dierks & Allen, Jan. 1999, pp. 1-80.
Song, Leilei and Parhi, Keshab K., “Low-Energy Digit-Serial/Parallel Finite Field Multipliers”, Journal of VLSI Signal Processing 19, 1988, pp. 149-166.
Agnew, G.B., et al., An Implementation of Elliptic Curve Cryptosystems Over F2155, IEEE Journal on Selected Areas in Communications, vol. 11, No. 5, Jun. 1993, pp. 804-813.
Halbutogullari, A. and Koc, Cetin K., “Mastrovito Multiplier for General Irreducible Polynomials”, IEEE Transactions on Computers, vol. 49, No. 5, May 2000, pp. 503-518.
Yanik, T., et al., “Incomplete reduction in modular arithmetic”, IEE Proc.—Comput. Digit. Tech., vol. 149, No. 2, Mar. 2002, pp. 46-52.
Blum, Thomas and Paar, Christof, “High-Radix Montgomery Modular Exponentiation on Reconfigurable Hardware”, IEEE Transactions on Computers, vol. 50, No. 7, Jul. 2001, pp. 759-764.
Gao, L.; Shrivastava, S.; Lee, H.; Sobelman, G., A Compact Fast Variable Key Size Elliptic Curve Cryptosystem Coprocessor, Proceedings of the Seventh Annual IEEE Symposium on Field-Programmable Custon Computing Machines, 1998.
Ernst, M.; Klupsch, S.; Hauck, O.; Huss, S.A., Rapid Prototyping for Hardware Accelerated Elliptic Curve Public-Key Cryptosystems, 12thIEEE Workshop on Rapid System Prototyping, Monterey, CA, Jun. 2001; pp. 24-29.
Orlando, G.; Paar, C., Aug. 2000, A High-Performance Reconfigurable Elliptic Curve Processor for GF(2m), CHES 2000 Workshop on Cryptographic Hardware and Embedded Systems, Springer-Verlag, Lecture Notes in Computer Science 1965; pp. 41-56.
Lopez, J.; Dahab, R., Aug. 1999, Fast Multiplication on Elliptic Curves over GF(2m) without Precomputation, CHES '99 Workshop on Cryptographic Hardware and Embedded Systems, Springer-Verlag, Lecture Notes in Computer Science 1717; pp. 316-327.
Hankerson, D.; Hernandez, J.L.; Menezes, A., Aug. 2000, Software Implementation of Elliptic Curve Cryptography over Binary Fields, CHES '2000 Workshop on Cryptographic Hardware and Embedded Systems, Springer-Verlag, Lecture Notes in Computer Science 1965; pp. 1-24.
Koblitz, Neal, “Elliptic Curve Cryptosystems”, Mathematics of Computation, vol. 48, No. 177, Jan. 1987, pp. 203-209.
Schroeppel, R.; Orman, H.; O'Malley, S., 1995, Fast Key Exchange with Elliptic Curve Systems, Advances in Cryptography, Crypto '95, Springer-Verlag, Lecture Notes in Computer Science 963; pp. 43-56.
Woodbury, A.D.; Bailey, D.V.; Paar, C., Sep. 2000, Elliptic Curve Cryptography on Smart Cards Without Coprocessors, The Fourth Smart Card Research and Advanced Applications (CARDIS2000) Conference, Bristol, UK; pp. 71-92.
Miller, V., Use of Elliptic Curves of Cryptography, In Lecture Notes in Computer Science 218; Advances in Crytology—CRYPTO '85, pp. 417-426, Springer-Verlag, Berlin, 1986.
Itoh, Toshiya and Tsujii, Shigeo, “A Fast Algorithm for Computing Multiplicative Inverses in GF(2m) Using Normal Bases”, Information and Computation vol. 78, No. 3, 1988, pp. 171-177.
Bednara, M., et al., “Reconfigurable Implementation of Elliptic Curve Crypto Algorithms”, Proceedings of the International Parallel and Distributed Processing Symposium, IEEE Computer Society, 2002, 8 pages.
U.S. Department of Commerce/National Institute of Standards and Technology, “Digital Signature Standard (DSS)”, Federal Information Processing Standards Publication, Jan. 27, 2000, pp. 1-74.
Blake-Wilson, Simon et al., “ECC Cipher Suites for TLS”, Blake-Wilson, Dierks, Hawk—TLS Working Group Mar. 15, 2001, pp. 1-22.
Goodman, James, et al., “An Energy-Efficient Reconfigurable Public-Key Cryptography Processor”, IEEE Journal of Solid-State Circuits, vol. 36, No. 11, Nov. 2001, pp. 1808-1820.
Shantz, Sheueling Chang, “From Euclid's GCD to Montgomery Multiplication to the Great Divide”, Sun Microsystems, Jun. 2001, pp. 1-10.
Blake, Ian; Seroussi, Gadiel; & Smart, Nigel, Elliptic Curves in Cryptography, London Mathematical Society Lecture Note Series 265, Cambridge University Press, United Kingdom, 1999; pp. vii-204.
U.S. Appl. No. 10/387,007, entitled “Hardware Accelerator for Elliptic Curve Cryptography”, filed Mar. 11, 2003.
U.S. Appl. No. 10/387,104, entitled “Generic Implementations of Elliptic Curve Cryptography Using Partial Reduction”, filed Mar. 11, 2003.
U.S. Appl. No. 10/387,008, entitled “Generic Modular Multiplier Using Partial Reduction”, filed Mar. 11, 2003.
Brown Russell A.
Chang-Shantz Sheueling
Eberle Hans
Gupta Vipul
Gura Nils
Kowert Robert C.
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Ngo Chuong D
Sun Microsystems Inc.
LandOfFree
Modular multiplier does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Modular multiplier, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modular multiplier will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4031382