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
-
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},
url = {https://eprint.iacr.org/2008/066}
}