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


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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
duncan @ cityu edu hk
2008-02-11: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.