Paper 2015/977

Faster point scalar multiplication on NIST elliptic curves over GF(p) using (twisted) Edwards curves over GF(p³)

Michał Wroński

Abstract

In this paper we present a new method for fast scalar multiplication on elliptic curves over GF(p) in FPGA using Edwards and twisted Edwards curves over GF(p³). The presented solution works for curves with prime group order (for example for all NIST curves over GF(p)). It is possible because of using 2-isogenous twisted Edwards curves over GF(p³) instead of using short Weierstrass curves over GF(p) for point scalar multiplication. This problem was considered by Verneuil in [1], but in software solutions it is useless, because multiplication in GF(p³) is much harder than multiplication in GF(p). Fortunately in hardware solutions it is possible to make in FPGA fast multiplication in GF(p³) using parallel computations. Single multiplication in GF(p³) is still a little bit slower than in GF(p) but operations on twisted Edwards curves require less multiplications than operations on short Weierstrass curves. Using these observations results in that scalar multiplication on twisted Edwards curve may be in some situations shorter than scalar multiplication on short Weierstrass curve up to 26%. Moreover, in Edwards and twisted Edwards curves arithmetic it is possible to use unified formula (the same formula for points addition and point doubling) which protects us against some kinds of side channel attacks. We also present full coprocessor for fast scalar multiplication in FPGA using described techniques.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
Edwards curvesTwisted Edwards curvesFinite FieldsPoint scalar multiplication.
Contact author(s)
mwronski @ wat edu pl
History
2015-10-12: received
Short URL
https://ia.cr/2015/977
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/977,
      author = {Michał Wroński},
      title = {Faster point scalar multiplication on NIST elliptic curves over GF(p) using (twisted) Edwards curves over GF(p³)},
      howpublished = {Cryptology ePrint Archive, Paper 2015/977},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/977}},
      url = {https://eprint.iacr.org/2015/977}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.