Elliptic and hyperelliptic curves on embedded μP

ABSTRACT

It is widely recognized that data security will play a central role in future IT systems. Providing public-key cryptographic primitives, which are the core tools for security, is often difficult on embedded processor due to computational, memory, and power constraints. This contribution appears to be the first thorough comparison of two public-key families, namely elliptic curve (ECC) and hyperelliptic curve cryptosystems on a wide range of embedded processor types (ARM, ColdFire, PowerPC). We investigated the influence of the processor type, resources, and architecture regarding throughput. Further, we improved previously known HECC algorithms resulting in a more efficient arithmetic.

REFERENCES

• 1: Agnew, G. B., Mullin, R. C., and Vanstone, S. A. 1993. An implementation of elliptic curve cryptosystems over F2155. IEEE J. Select. Areas Commun. 11, 5 (June), 804--813.
• 2: ANSI X9.62-1999. 1999. The Elliptic Curve Digital Signature Algorithm. Tech. rep., ANSI.
• 3: ANSI X9.63-199x. 1998. Elliptic Curve Key Agreement and Key Transport Protocols. Draft, ANSI. Working document.
• 4: ARM. 2000. ARM Evaluator-7T Board User Guide. Available at http://www.arm.com/support/.
• 5: Ian F. Blake , Shuhong Gao , Robert Lambert, Constructive problems for irreducible polynomials over finite fields, Proceedings of the third Canadian workshop on Information theory and applications, p.1-23, July 1993, Rockland, Ontario, Canada
• 6: Ian F. Blake , G. Seroussi , N. P. Smart, Elliptic curves in cryptography, Cambridge University Press, New York, NY, 1999
• 7: N. Boston , T. Clancy , Y. Liow , J. Webster, Genus Two Hyperelliptic Curve Coprocessor, Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, p.400-414, August 13-15, 2002
• 8: Cantor, D. 1987. Computing in Jacobian of a hyperelliptic curve. Math. Comput. 48, 177, 95--101.
• 9: D V Chudnovsky , G V Chudnovsky, Sequences of numbers generated by addition in formal groups and new primality and factorization tests, Advances in Applied Mathematics, v.7 n.4, p.385-434, Dec. 1986 [doi>10.1016/0196-8858(86)90023-0]
• 10: Henri Cohen, A course in computational algebraic number theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 11: Henri Cohen , Atsuko Miyaji , Takatoshi Ono, Efficient Elliptic Curve Exponentiation Using Mixed Coordinates, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.51-65, October 18-22, 1998
• 12: Dierks, T. and Allen, C. 1999. RFC 2246: The TLS Protocol Version 1.0. Corporation for National Research Initiatives, Internet Engineering Task Force, Network Working Group, Reston, Virginia, USA.
• 13: Freier, A. O., Karlton, P., and Kocher, P. C. 1996. The SSL Protocol Version 3.0. Transport Layer Security Working Group Internet-Draft.
• 14: Gerhard Frey , Hans-Georg Rück, A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves, Mathematics of Computation, v.62 n.206, p.865-874, April 1994 [doi>10.2307/2153546]
• 15: Fulton, W. 1969. Algebraic Curves---An Introduction to Algebraic Geometry. W. A. Benjamin, Inc., Reading, M.
• 16: Steven D. Galbraith, Supersingular Curves in Cryptography, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.495-513, December 09-13, 2001
• 17: Gallant, R., Lambert, R., and Vanstone, S. 1998. Improving the parallelized Pollard lambda search on binary anomalous curves. Available at http://www.certicom.com/chal/download/paper.ps.
• 18: Lijun Gao , Sarvesh Shrivastava , Gerald E. Sobelman, Elliptic Curve Scalar Multiplier Design Using FPGAs, Proceedings of the First International Workshop on Cryptographic Hardware and Embedded Systems, p.257-268, August 12-13, 1999
• 19: Gaudry, P. 2000. An algorithm for solving the discrete log problem on hyperelliptic curves. In Advances in Cryptology---EUROCRYPT 2000, B. Preneel, ed. Lecture Notes in Computer Science, vol. 1807. Springer-Verlag, Berlin, Germany, 19--34.
• 20: Pierrick Gaudry , Robert Harley, Counting Points on Hyperelliptic Curves over Finite Fields, Proceedings of the 4th International Symposium on Algorithmic Number Theory, p.313-332, July 02-07, 2000
• 21: Gaudry, P., Hess, F., and Smart, N. P. 2000. Constructive and Destructive Facets of Weil Descent on Elliptic Curves. Tech. Rep. HPL 2000-10, HP Labs. Available at http://www.hpl.hp.com/ techreports/2000/HPL-2000-10.html.
• 22: Christian Günther , Tanja Lange , Andreas Stein, Speeding up the Arithmetic on Koblitz Curves of Genus Two, Proceedings of the 7th Annual International Workshop on Selected Areas in Cryptography, p.106-117, August 14-15, 2000
• 23: Solomon W. Golomb , Soloman Golomb, Shift Register Sequences, Aegean Park Press, Laguna Hills, CA, 1981
• 24: Daniel M. Gordon, A survey of fast exponentiation methods, Journal of Algorithms, v.27 n.1, p.129-146, April 1998 [doi>10.1006/jagm.1997.0913]
• 25: Jorge Guajardo , Christof Paar, Efficient Algorithms for Elliptic Curve Cryptosystems, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.342-356, August 17-21, 1997
• 26: 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
• 27: 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
• 28: Harley, R. 2000. Fast Arithmetic on Genus Two Curves. Available at http://cristal.inria.fr/harley/hyper/. adding.txt and doubling.c.
• 29: IEEE 1999. IEEE P1363 Standard Specifications for Public Key Cryptography. IEEE. Last Preliminary Draft.
• 30: Karatsuba, A. and Ofman, Y. 1963. Multiplication of multidigit numbers on automata. Sov. Phys. Dokl. (English translation) 7, 7, 595--596.
• 31: Kent, S. and Atkinson, R. 1998. RFC 2401: Security Architecture for the Internet Protocol. Corporation for National Research Initiatives, Internet Engineering Task Force, Network Working Group, Reston, Virginia, USA.
• 32: Brian King, An Improved Implementation of Elliptic Curves over GF(2) when Using Projective Point Arithmetic, Revised Papers from the 8th Annual International Workshop on Selected Areas in Cryptography, p.134-150, August 16-17, 2001
• 33: Koblitz, N. 1987. Elliptic curve cryptosystems. Math. Comput. 48, 203--209.
• 34: N. Koblitz, A family of Jacobians suitable for discrete log cryptosystems, Proceedings on Advances in cryptology, p.94-99, February 1990, Santa Barbara, California, United States
• 35: Neal Koblitz, Hyperelliptic cryptosystems, Journal of Cryptology, v.1 n.3, p.139-150, 1989 [doi>10.1007/BF02252872]
• 36: Neal Koblitz, CM-Curves with Good Cryptographic Properties, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.279-287, August 11-15, 1991
• 37: Neal Koblitz , Alfred J. Menezes , Yi-Hong Wu , Robert J. Zuccherato, Algebraic aspects of cryptography, Springer-Verlag New York, Inc., New York, NY, 1998
• 38: Krieger, U. 1997. signature.c. M.S. thesis, Mathematik und Informatik, Universität Essen, Fachbereich 6, Essen, Germany.
• 39: Kuroki, J., Gonda, M., Matsuo, K., Chao, J., and Tsujii, S. 2002. Fast genus three hyperelliptic curve cryptosystems. In The 2002 Symposium on Cryptography and Information Security, Japan---SCIS 2002.
• 40: Lange, T. 2002a. Efficient Arithmetic on Genus 2 Hyperelliptic Curves over Finite Fields via Explicit Formulae. Cryptology ePrint Archive, Report 2002/121. http://eprint.iacr.org/.
• 41: Lange, T. 2002b. Inversion-Free Arithmetic on Genus 2 Hyperelliptic Curves. Cryptology ePrint Archive, Report 2002/147. http:eprint.iacr.org.
• 42: Lange, T. 2002c. Weighted Coordinates on Genus 2 Hyperelliptic Curves. Cryptology ePrint Archive, Report 2002/153. http:eprint.iacr.org.
• 43: Arjen K. Lenstra , Eric R. Verheul, Selecting Cryptographic Key Sizes, Proceedings of the Third International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.446-465, January 18-20, 2000
• 44: 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
• 45: Matsuo, K., Chao, J., and Tsujii, S. 2001. Fast Genus Two Hyperelliptic Curve Cryptosystems. In ISEC2001-31. IEICE.
• 46: Menezes, A., Okamoto, T., and Vanstone, S. 1993. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inf. Theory 39, 5 (Sep.), 1639--1646.
• 47: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 48: Menezes, A. J., Wu, Y. H., and Zuccherato, R. J. 1996. An Elementary Introduction to Hyperelliptic Curves. Personal correspondence.
• 49: Victor S Miller, Use of elliptic curves in cryptography, Lecture notes in computer sciences; 218 on Advances in cryptology---CRYPTO 85, p.417-426, June 1986, Santa Barbara, California, United States
• 50: Miyamoto, Y., Doi, H., Matsuo, K., Chao, J., and Tsuji, S. 2002. A fast addition algorithm of genus two hyperelliptic curve. In The 2002 Symposium on Cryptography and Information Security---SCIS 2002. IEICE, Japan, 497--50. (in Japanese).
• 51: Montgomery, P. 1987. Speeding the Pollard and Elliptic Curve methods of factorization. Math. Comp. 48, 243--264.
• 52: Morain, F. and Olivos, J. 1990. Speeding up the computations on an elliptic curve using addition-subtraction chains. Theor. Inf. Applic. 24, 6, 531--543.
• 53: Motorola. 2000a. MFC5307 User's Manual. http://e-www.motorola.com/collateral/MCF5307-BUM.pdf.
• 54: Motorola. 2000b. MPC823 User's Manual. http://e-www.motorola.com/brdata/PDFDB/docs/ MPC823UM.pdf.
• 55: Mumford, D. 1984. Tata lectures on theta II. In Progress in Mathematics, vol. 43. Birkhäuser.
• 56: Koh-ichi Nagao, Improving Group Law Algorithms for Jacobians of Hyperelliptic Curves, Proceedings of the 4th International Symposium on Algorithmic Number Theory, p.439-448, July 02-07, 2000
• 57: 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
• 58: Pelzl, J. 2002. Hyperelliptic Cryptosystems on Embedded Microprocessor. M.S. thesis, Department of Electrical Engineering and Information Sciences, Ruhr-Universitaet Bochum, Bochum, Germany.
• 59: Pelzl, J., Wollinger, T., and Paar, C. 2003. Low cost security: Explicit formulae for genus-4 hyperelliptic curves. In Tenth Annual Workshop on Selected Areas in Cryptography---SAC 2003. Springer-Verlag, Berlin, Germany.
• 60: Pollard, J. M. 1978. Monte Carlo methods for index computation mod p. Math. Comput. 32, 143 (July), 918--924.
• 61: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 62: Rosner, M. 1999. Elliptic Curve Cryptosystems on Reconfigurable Hardware. M.S. thesis, ECE Department, Worcester Polytechnic Institute, Worcester, Massachusetts, USA.
• 63: Hans-Georg Rück, On the discrete logarithm in the divisor class group of curves, Mathematics of Computation, v.68 n.226, p.805-806, April 1999 [doi>10.1090/S0025-5718-99-01043-1]
• 64: Sakai, Y. and Sakurai, K. 2000. On the practical performance of hyperelliptic curve cryptosystems in software implementation. In IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E83-A NO.4. 692--703. IEICE Trans.
• 65: Yasuyuki Sakai , Kouichi Sakurai , Hirokazu Ishizuka, Secure Hyperelliptic Cryptosystems and Their Performances, Proceedings of the First International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.164-181, February 05-06, 1998
• 66: Scholten, J. and Zhu, J. 2002. Hyperelliptic curves in characteristic 2. Int. Math. Res. Notices 17, 905--917.
• 67: 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
• 68: Silverman, J. H. 1986. The Arithmetic of Elliptic Curves. Springer-Verlag, New York.
• 69: Smart, N. 1999. On the performance of hyperelliptic cryptosystems. In Advances in Cryptology---EUROCRYPT '99, J. Stern, ed. Lecture Notes in Computer Science, vol. 1592. Springer-Verlag, 165--175.
• 70: Jerome A. Solinas, An Improved Algorithm for Arithmetic on a Family of Elliptic Curves, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.357-371, August 17-21, 1997
• 71: Takahashi, M. 2002. Improving Harley algorithms for jacobians of genus 2 hyperelliptic curves. In SCIS. IEICE, Japan. (in Japanese).
• 72: Joachim von zur Gathen, Irreducible trinomials over finite fields, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.332-336, July 2001, London, Ontario, Canada [doi>10.1145/384101.384146]
• 73: Joachim von zur Gathen , Michael Nöcker, Exponentiation in Finite Fields: Theory and Practice, Proceedings of the 12th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.88-113, June 23-27, 1997
• 74: D H Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, v.32 n.1, p.54-62, Jan. 1986 [doi>10.1109/TIT.1986.1057137]
• 75: Wollinger, T. 2001. Computer Architectures for Cryptosystems Based on Hyperelliptic Curves. M.S. thesis, ECE Department, Worcester Polytechnic Institute, Worcester, Massachusetts, USA.
• 76: Wollinger, T. and Paar, C. 2002. Hardware architectures proposed for cryptosystems based on hyperelliptic curves. In Proceedings of the 9th IEEE International Conference on Electronics, Circuits and Systems---ICECS 2002, vol. III. 1159--1163.
• 77: Zierler, N. 1970. On xn + x + 1 over GF(2). Inf. Control 16, 67--69.
• 78: Zierler, N. and Brillhart, J. 1968. On primitive trinomials (mod 2). Inf. Control 13, 541--554.
• 79: Zierler, N. and Brillhart, J. 1969. On primitive trinomials (mod 2): II. Inf. and Control 14, 566--569.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.3 Microcomputers

  E. Data
  E.3 DATA ENCRYPTION

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Design, Performance, Security

Keywords:
Elliptic curves cryptosystem, hyperelliptic curve cryptosystem, implementation