Cryptography – Particular algorithmic function encoding
Reexamination Certificate
2003-03-11
2008-03-18
Sheikh, Ayaz (Department: 2131)
Cryptography
Particular algorithmic function encoding
C380S030000, C708S492000, C713S166000
Reexamination Certificate
active
07346159
ABSTRACT:
An apparatus multiplies a first and a second binary polynomial X(t) and Y(t) over GF(2), where an irreducible polynomial Mm(t)=tm+am−1tm−1+am−2tm−2tm−2+ . . . +a1t+a0, and where the coefficients aiare equal to either 1 or 0, and m is a field degree. The degree of X(t)<n, and the degree of Y(t)<n, and m≦n. The apparatus includes a digit serial modular multiplier circuit coupled to supply a multiplication result of degree ≧m of a multiplication of the first and second binary polynomials. The digit serial modular multiplier circuit includes a first and second register, each being ≦n bits. A partial product generator circuit multiplies a portion of digit size d of contents of the first register and contents of the second register. The partial product generator is also utilized as part of a reduction operation for at least one generic curve.
REFERENCES:
patent: 5347481 (1994-09-01), Williams
patent: 6049815 (2000-04-01), Lambert et al.
patent: 6199087 (2001-03-01), Blake et al.
patent: 2002/0044649 (2002-04-01), Gallant et al.
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 Custom 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”.
U.S. Appl. No. 10/387,009, entitled “Modular Multiplier”.
U.S. Appl. No. 10/387,104, entitled “Generic Implementations of Elliptic Curve Cryptography Using Partial Reduction”.
Eberle Hans
Gura Nils
Doan Trang
Kowert Robert C.
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Sheikh Ayaz
Sun Microsystems Inc.
LandOfFree
Generic modular multiplier using partial reduction does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Generic modular multiplier using partial reduction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generic modular multiplier using partial reduction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3962316