Paper 2005/358

Normal Basis Multiplication Algorithms for GF(2n) (Full Version)

Haining Fan, Duo Liu, and Yiqi Dai

Abstract

In this paper, we propose a new normal basis multiplication algorithm for GF(2n). This algorithm can be used to design not only fast software algorithms but also low complexity bit-parallel multipliers in some GF(2n)s. Especially, for some values of n that no Gaussian normal basis exists in GF(2n), i.e., 8|n, this algorithm provides an alternative way to construct low complexity normal basis multipliers. Two improvements on a recently proposed software normal basis multiplication algorithm are also presented. Time and memory complexities of these normal basis multiplication algorithms are compared with respect to software performance. It is shown that they have some specific behavior in different applications. For example, GF(2571) is one of the five binary fields recommended by NIST for ECDSA (Elliptic Curve Digital Signature Algorithm) applications. In this field, our experiments show that the new algorithm is even faster than the polynomial basis Montgomery multiplication algorithm: 525 us v. 819 us.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. It includes all omitted data in two published paper.
Keywords
Finite fieldnormal basisMassey-Omura multiplieroptimal normal basis.
Contact author(s)
fan_haining @ yahoo com
History
2006-08-03: revised
2005-10-09: received
See all versions
Short URL
https://ia.cr/2005/358
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/358,
      author = {Haining Fan and Duo Liu and Yiqi Dai},
      title = {Normal Basis Multiplication Algorithms for GF(2n) (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2005/358},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/358}},
      url = {https://eprint.iacr.org/2005/358}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.