International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Junjie Jiang
Jing Chen
Jian Wang
Duncan S. Wong
Xiaotie Deng
Download:
URL: http://eprint.iacr.org/2008/066
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2008-17743,
  title={High Performance Architecture for Elliptic Curve Scalar Multiplication over GF(2^m)},
  booktitle={IACR Eprint archive},
  keywords={implementation /},
  url={http://eprint.iacr.org/2008/066},
  note={ duncan@cityu.edu.hk 13915 received 6 Feb 2008},
  author={Junjie Jiang and Jing Chen and Jian Wang and Duncan S. Wong and Xiaotie Deng},
  year=2008
}