Cryptology ePrint Archive: Report 2014/852

Faster ECC over $\mathbb{F}_{2^{521}-1}$

Robert Granger and Michael Scott

Abstract: In this paper we present a new multiplication algorithm for residues modulo the Mersenne prime $2^{521} - 1$. Using this approach, on an Intel Haswell Core i7-4770, constant-time variable-base scalar multiplication on NIST's (and SECG's) curve P-521 requires 1,073,000 cycles, while on the recently proposed Edwards curve E-521 it requires just 943,000 cycles. As a comparison, on the same architecture openSSL's ECDH speed test for curve P-521 requires 1,319,000 cycles. Furthermore, our code was written entirely in C and so is robust across different platforms. The basic observation behind these speedups is that the form of the modulus allows one to multiply residues with as few word-by-word multiplications as is needed for squaring, while incurring very little overhead from extra additions, in contrast to the usual Karatsuba methods.

Category / Keywords: implementation / elliptic curve cryptography, performance, P-521, E-521, Edwards curves, generalised repunit primes

Original Publication (with minor differences): IACR-PKC-2015

Date: received 17 Oct 2014, last revised 23 Mar 2015

Contact author: robbiegranger at gmail com

Available format(s): PDF | BibTeX Citation

Note: This version now has cache-safe implementation timings.

Version: 20150323:184505 (All versions of this report)

Short URL: ia.cr/2014/852

Discussion forum: Show discussion | Start new discussion