Paper 2012/309

Fast and compact elliptic-curve cryptography

Mike Hamburg

Abstract


Elliptic curve cryptosystems have improved greatly in speed over the past few years. In this paper we outline a new elliptic curve signature and key agreement implementation which achieves record speeds while remaining relatively compact. For example, on Intel Sandy Bridge, a curve with about $2^{250}$ points produces a signature in just under 60k clock cycles, verifies in under 169k clock cycles, and computes a Diffie-Hellman shared secret in under 153k clock cycles. Our implementation has a small footprint: the library is under 55kB. We also post competitive timings on ARM processors, verifying a signature in under 626k Tegra-2 cycles. We introduce faster field arithmetic, a new point compression algorithm, an improved fixed-base scalar multiplication algorithm and a new way to verify signatures without inversions or coordinate recovery. Some of these improvements should be applicable to other systems.

Note: 9/7/2012: Added a citation for Longa and Sica's work. Changed "prediction" to "look-ahead" in discussion of Hisil's mixed projective/extended coordinates, to make it clear that the prediction is certain. Removed verification with no x-coordinate; added verification with precomputation. Made it clear that this software sets records for ECC signing and verification, but not for key exchange.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
elliptic curve cryptosystempublic-key cryptographydigital signatures
Contact author(s)
mhamburg @ cryptography com
History
2012-09-07: revised
2012-06-03: received
See all versions
Short URL
https://ia.cr/2012/309
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/309,
      author = {Mike Hamburg},
      title = {Fast and compact elliptic-curve cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2012/309},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/309}},
      url = {https://eprint.iacr.org/2012/309}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.