Generic implementations of elliptic curve cryptography using...

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

2011-04-19

2011-04-19

Malzahn, David H (Department: 2193)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

07930335

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.
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, et al., “Efficient Algorithms for Elliptic Curve Cryptosystems” ECE Department, Worcest Polytechnic Institute, 100 Institute Road, Worcester, MA 01609, USA, pp. 1=16 (CRYPTO '97, Springer-Verlag, LNCS 1294, pp. 342-356, 1997).
Weimerskirch, et al., “Generalizations of the Karatsuba Algorithm for Polynomial Multiplication,” Communication Security Group, Dept. of Electrical Engineering & Information Sciences, Ruhr-Universitat Bochum, German; submitted to Design, Codes and Cryptography, Mar. 2002, pp. 1-23.
Miller, V., Use of Elliptic Curves of Cryptograph, In Lecture Notes in Computer Scient 218; Advances in Cryptography—CRYPTO '85, pp. 417-426, Springer-Verlag, Berlin, 1986.
Itoh, Toshiya, et al., “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.
Blake-Wilson,Simon, et al., “ECC Cipher Suites for TLS,” lake-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 Shueuling Chang, “From Euclid's GCD to Montgomery Multiplication to the Great Divide,” Sun Microsystems, Inc. Jun. 2001, pp. 1-10.
Blake, Ian, et al., “Elliptic Curves in Cryptography,” London Mathematical Society Lecture Note Series 265, Cambridge University Press, U.K., 1999, pp. vii-204.
U.S. Appl. No. 10/387,007, entitled “Hardware Accelerator for Elliptic Curve Cryotograpy,”.
U.S. Appl. No. 10/387,009, entitled “Modular Multiplier”.
U.S. Appl. No. 10/387,008, entitled “Generic Modular Multiplier Using Partial Reduction”.
Blake-Wilson, S., “Additional ECC Groups for IKE,” lake-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.
Agnew, G.B., et al., “An Implementaion of Elliptic Curve Cryptosystems Over F2155,” IEEE Journal on Selected Areas in Communications, vol. 11, No. 5, Jun. 1993, pp. 804-813.
Halbutogullari, A., et al., “Mastrovio 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,” IEEE Proc. Computer Digit. Tech., vol. 149, No. 2, Mar. 2002, pp. 46-52.
Blum, et al., “High-Radix Montgomery Modluar Exponentiation on Reconfigurable Hardware,” IEEE Transactions on Computers, vol. 50, No. 7, Jul. 2001, pp. 759-764.
Gao, L, et al., “A Compact Fast Variable Key Size Elliptic Curve Cryptosystem Coprocessor,” Proc. of the Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 1998.
Ernst, M, et al., “Rapid Prototyping for Hardware Accelerated Elliptic Curve Public-Key Cryptosystems”, 12th IEEE Workshop on Rapid System Prototyping, Monterey, CA, Jun. 2001, pp. 24-29.
Orlando, G., et al., “A High-Performance Reconfigurable Elliptic Curve Processor for GF(2m)”, CHES 2000 Workshop on Cryptogrpahic Hardware and Embedded Systems, Springer-Verlag, Lecture Notes in Computer Science 1965, pp. 41-56.
Lopez, J., et al., “Fast Multiplication on Eliptic 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, Aug. 1999.
Hankerson, D., et al., “Software Impelementation of Elliptic Curve Cryptograph over Binary Fields,” CHES 2000 Workshop on Cryptographic Hardware and Embedded Systems, Springer-Verlag, Lecture Notes in Computer Science 1965, pp. 1-24, Aug. 2000.
Koblitz, Neal, “Elliptic Curve Cryptosystems,” Mathematics of Computation, vol. 48, No. 177, Jan. 1987, pp. 203-209.
Schroeppel, R., et al., “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., et al, “Elliptic Curve Cryptography on Smart Cards Without Coprocessors,” The Fourth Smart Card Research and Advanced Applications (CARDIS2000) Conference, Bristol, UK, pp. 71-92, Sep. 2000.

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-2676339