Generic implementations of elliptic curve cryptography using...

Details Generic implementations of elliptic curve cryptography using... Generic implementations of elliptic curve cryptography using...

2007-07-03

2007-07-03

Malzahn, D. H. (Department: 2193)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

10387104

ABSTRACT:
A reduction operation is utilized in an arithmetic operation on two binary polynomials X(t) and Y(t) over GF(2), where an irreducible polynomial Mm(t)=tm+am−1tm−1+am−2tm−2+ . . . +a1t+a0, where the coefficients aiare equal to either 1 or 0, and m is a field degree. The reduction operation includes partially reducing a result of the arithmetic operation on the two binary polynomials to produce a congruent polynomial of degree less than a chosen integer n, with m≦n. The partial reduction includes using a polynomial M′=(Mm(t)−tm)*tn−m, or a polynomial M″=Mm(t)*tn−mas part of reducing the result to the degree less than n and greater than or equal to m. The integer n can be the data path width of an arithmetic unit performing the arithmetic operation, a multiple of a digit size of a multiplier performing the arithmetic operation, a word size of a storage location, such as a register, or a maximum operand size of a functional unit in which the arithmetic operation is performed.

REFERENCES:
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.
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 Crypotgraphy, 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,008, entitled “Generic Modular Multiplier Using Partial Reduction”.
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 & Cryptography, Mar. 2002, pp. 1-23.

Affiliated with

Also associated with

Rating

Generic implementations of elliptic curve cryptography using... 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 implementations of elliptic curve cryptography using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generic implementations of elliptic curve cryptography using... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3797717