International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 22 October 2014

Robert Granger, Michael Scott
ePrint Report ePrint Report
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 $989,000$ cycles, while on the recently proposed Edwards curve E-521 it requires just $779,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 with no non-compiler optimisations 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.

Expand

Additional news items may be found on the IACR news page.