Implementation and Analysis of Elliptic Curve Cryptosystems over Polynomial basis and ONB

Authors: Yong-Je Choi, Moo-Seop Kim, Hang-Rok Lee, Ho-Won Kim

Abstract:

Polynomial bases and normal bases are both used for elliptic curve cryptosystems, but field arithmetic operations such as multiplication, inversion and doubling for each basis are implemented by different methods. In general, it is said that normal bases, especially optimal normal bases (ONB) which are special cases on normal bases, are efficient for the implementation in hardware in comparison with polynomial bases. However there seems to be more examined by implementing and analyzing these systems under similar condition. In this paper, we designed field arithmetic operators for each basis over GF(2233), which field has a polynomial basis recommended by SEC2 and a type-II ONB both, and analyzed these implementation results. And, in addition, we predicted the efficiency of two elliptic curve cryptosystems using these field arithmetic operators.

Keywords: Elliptic Curve Cryptosystem, Crypto Algorithm, Polynomial Basis, Optimal Normal Basis, Security.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330375

References:

[1] Certicom research , The Elliptic Curve Cryptosystem, Certicom, April 1997.
[2] Darrel Hankerson, Julio Lopez Hernandez, Alfred Menezes, Software Implementation of Elliptic Curve Cryptography over Binary Fields, CHES 2000, page 1-24. 2000.
[3] Certicom research, "SEC 2 : Recommended Elliptic Curve Domain Parameters", October 1999.
[4] Richard Schroeppel, Hilarie Orman, Sean O'Malley, "Fast Key Exchange with Elliptic Curve Systems", TR-95-03(Tucson, AZ: University of Arizona, Computer Sciences Department, 1995)
[5] Mastrovito, E. D. : 'VLSI architectures for computations in Galois fields'PhD Thesis, Linkoping University, Department of Electrical Engineering, Linkoping, Sweden, 1991.
[6] Sunar, B. and Koc, C. K.: 'Mastrovisto multiplier for all trinomials', IEEE Trans. Comput. 1999, 48, (5), pp. 522-527.
[7] Wu, H. : 'Bit-parallel finite field multiplier and square using polynomial basis', IEEE Trans. Comput., 2002, 51, (7), pp. 750-758.
[8] Chiou, C. W, Chou F. H. and Shu S. F : 'Low-complexity finite field multiplier using irreducible trinomials', Electron. Lett., 2003, 39, (24), pp. 1709-1711
[9] Huapeng Wu, Anwar Hasan, " Finite Field Multiplier Using Redundant Representation" , IEEE Transactions on Computers, Vol 51, No 11, November 2002 .
[10] HoWon Kim, Thomas Wollinger, YongJe Choi, Kyoil Chung, and Christof Paar, "Hyperelliptic Curve Coprocessors on a FPGA," The 5th International Workshop on Information Security Applications (WISA 2004), Aug. 23-25, 2004, JeJu, Korea (LNCS: SCI-E)
[11] Y.J. Choi, K.-Y. Chang, D.W. Hong and H.S. Cho, "Hybrid multiplier for GF(2m) defined by some irreducible trinomials" Electronics Letter, Volume 40 852-853, Number 14, 8th July 2004.
[12] C. K. Koc, and B. Sunar, "Low-Complexity Bit-Parallel Canonical and Normal Basis Multipliers for a Class of Finite Fields", IEEE Trans on Comp. Vol 47, No 3, March 1998.
[13] J. Omura and J. Massey, "Computational Method and Apparatus for Finite Field Arithmetic" U.S. Patent Number 4,587,627