Generic implementations of elliptic curve cryptography using partial reduction

ABSTRACT

Elliptic Curve Cryptography (ECC) is evolving as an attractive alternative to other public-key schemes such as RSA by offering the smallest key size and the highest strength per bit. The importance of ECC has been recognized by the US government and the standards bodies NIST and SECG. Standards for preferred elliptic curves over prime fields GF(p) and binary polynomial fields GF(2^m) as well as the Elliptic Curve Digital Signature Algorithm (ECDSA) have been created. A security protocol based on ECC requires support for different curves representing different security levels. This is particularly true for server applications that are exposed to requests for secure connections with different parameters generated by a multitude of client devices. Reported implementations of ECC over GF(2^m) typically choose to implement each curve as a special case so that modular reduction can be optimized, thus improving the overall performance. In contrast, this paper focuses on generic implementations of ECC point multiplication for arbitrary curves over GF(2^m). We present a novel reduction algorithm that allows hardware and software implementations for variable field degrees m. Though not as high in performance as an implementation optimized for a specific curve, it offers an attractive solution to supporting infrequently used curves or curves not known at the time of the implementation.

REFERENCES

• 1: G. B. Agnew, R. C. Mullin, and S. A. Vanstone. An implementation of elliptic curve cryptosystems over f2 155 . In IEEE Journal on Selected Areas in Communications, 11(5):804--813, June 1993.
• 2: Marcus Bednara , M. Daldrup , Joachim von zur Gathen , J. Shokrollahi , Jürgen Teich, Reconfigurable Implementation of Elliptic Curve Crypto Algorithms, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.284, April 15-19, 2002
• 3: Berlekamp. Algebraic Coding Theory. Aegan Park Press, 1984.
• 4: Ian F. Blake , G. Seroussi , N. P. Smart, Elliptic curves in cryptography, Cambridge University Press, New York, NY, 1999
• 5: S. Blake-Wilson, D. Brown, Y. Poeluev, and M. Salter. Additional ECC Groups For IKE. IETF Internet Draft, July 2002.
• 6: Certicom Research. Sec 2: Recommended elliptic curve domain parameters. Standards for efficient Cryptography Version 1.0, September 2000.
• 7: Sheueling Chang Shantz, From Euclid's GCD to Montgomery Multiplication to the Great Divide, Sun Microsystems, Inc., Mountain View, CA, 2001
• 8: J. Goodman and A. P. Chandrakasan. An energy-efficient recon gurable public-key cryptography processor. IEEE Journal of Solid-State Circuits, 36(11):1808--1820, November 2001.
• 9: V. Gupta, S. Blake-Wilson, B. Möller, and C. Hawk. ECC Cipher Suites for TLS. IETF Internet Draft, August 2002.
• 10: Nils Gura , Sheueling Chang Shantz , Hans Eberle , Sumit Gupta , Vipul Gupta , Daniel Finchelstein , Edouard Goupy , Douglas Stebila, An End-to-End Systems Approach to Elliptic Curve Cryptography, Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, p.349-365, August 13-15, 2002
• 11: A. Halbutoğullari , Çetin K. Koç, Mastrovito Multiplier for General Irreducible Polynomials, IEEE Transactions on Computers, v.49 n.5, p.503-518, May 2000 [doi>10.1109/12.859542]
• 12: Darrel Hankerson , Julio López Hernandez , Alfred Menezes, Software Implementation of Elliptic Curve Cryptography over Binary Fields, Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, p.1-24, August 17-18, 2000
• 13: Toshiya Itoh , Shigeo Tsujii, A fast algorithm for computing multiplicative inverses in GF(2m) using normal bases, Information and Computation, v.78 n.3, p.171-177, Sept. 1988 [doi>10.1016/0890-5401(88)90024-7]
• 14: A. Karatsuba and Y. Ofman. Multiplication of many-digital numbers by automatic computers. Doklady Akad. Nauk, (145):293--294, 1963. Translation in Physics-Doklady 7, 595--596.
• 15: Julio López , Ricardo Dahab, Fast Multiplication on Elliptic Curves over GF(2m) without Precomputation, Proceedings of the First International Workshop on Cryptographic Hardware and Embedded Systems, p.316-327, August 12-13, 1999
• 16: Gerardo Orlando , Christof Paar, A High Performance Reconfigurable Elliptic Curve Processor for GF(2m), Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, p.41-56, August 17-18, 2000
• 17: Richard Schroeppel , Hilarie Orman , Sean W. O'Malley , Oliver Spatscheck, Fast Key Exchange with Elliptic Curve Systems, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.43-56, August 27-31, 1995
• 18: Leilei Song , Keshab K. Parhi, Low-Energy Digit-Serial/Parallel Finite Field Multipliers, Journal of VLSI Signal Processing Systems, v.19 n.2, p.149-166, July 1998 [doi>10.1023/A:1008013818413]
• 19: U.S. Department of Commerce and National Institute of Standards and Technology. Digital signature standard (dss). Federal Information Processing Standards Publication FIPS PUB 186-2, January 2000.
• 20: Adam D. Woodbury , Daniel V. Bailey , Christof Paar, Elliptic curve cryptography on smart cards without coprocessors, Proceedings of the fourth working conference on smart card research and advanced applications on Smart card research and advanced applications, p.71-92, February 2001, Bristol, United Kingdom
• 21: T. Yanik, E. Savas, and Ç . K. Koç. Incomplete reduction in modular arithmetic. IEE Proceedings: Computers and Digital Technique, 149(2), March 2002. Sun, Sun Microsystems, the Sun logo and Sun Fire are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Algorithms

Keywords:
elliptic curve cryptography, modular reduction