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

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.

Authors:

• Yong-Je Choi
• Moo-Seop Kim
• Hang-Rok Lee
• Ho-Won Kim

Keywords:

• Elliptic Curve Cryptosystem
• Crypto Algorithm
• Polynomial Basis
• Optimal Normal Basis
• Security.

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