Paper 2008/066

High Performance Architecture for Elliptic Curve Scalar Multiplication over GF(2^m)

Junjie Jiang, Jing Chen, Jian Wang, Duncan S. Wong, and Xiaotie Deng

Abstract

We propose a new architecture for performing Elliptic Curve Scalar Multiplication (ECSM) on elliptic curves over GF(2^m). This architecture maximizes the parallelism that the projective version of the Montgomery ECSM algorithm can achieve. It completes one ECSM operation in about $2(m-1)( \lceil m/D \rceil +4)+m$ cycles, and is at least three times the speed of the best known result currently available. When implemented on a Virtex-4 FPGA, it completes one ECSM operation over GF(2^163) in 12.5us with the maximum achievable frequency of 222MHz. Two other implementation variants for less resource consumption are also proposed. Our first variant reduces the resource consumption by almost 50% while still maintaining the utilization efficiency, which is measured by a performance to resource consumption ratio. Our second variant achieves the best utilization efficiency and in our actual implementation on an elliptic curve group over GF(2^163), it gives more than 30% reduction on resource consumption while maintaining almost the same speed of computation as that of our original design. For achieving this high performance, we also propose a modified finite field inversion algorithm which takes only m cycles to invert an element over GF(2^m), rather than 2m cycles as the traditional Extended Euclid algorithm does, and this new design yields much better utilization of the cycle time.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
duncan @ cityu edu hk
History
2008-02-11: received
Short URL
https://ia.cr/2008/066
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/066,
      author = {Junjie Jiang and Jing Chen and Jian Wang and Duncan S.  Wong and Xiaotie Deng},
      title = {High Performance Architecture for Elliptic Curve Scalar Multiplication over GF(2^m)},
      howpublished = {Cryptology ePrint Archive, Paper 2008/066},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/066}},
      url = {https://eprint.iacr.org/2008/066}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.