Cryptology ePrint Archive: Report 2010/335

Analysis of Efficient Techniques for Fast Elliptic Curve Cryptography on x86-64 based Processors

Patrick Longa, and Catherine Gebotys

Abstract: In this work, we analyze and present experimental data evaluating the efficiency of several techniques for speeding up the computation of elliptic curve point multiplication on emerging x86-64 processor architectures. In particular, we study the efficient combination of such techniques as elimination of conditional branches and incomplete reduction to achieve fast field arithmetic over GF(p). Furthermore, we study the impact of (true) data dependencies on these processors and propose several generic techniques to reduce the number of pipeline stalls, memory reads/writes and function calls. We also extend these techniques to field arithmetic over GF(p^2), which is utilized as underlying field by the recently proposed Galbraith-Lin-Scott (GLS) method to achieve higher performance in the point multiplication. By efficiently combining all these methods with state-of-the-art elliptic curve algorithms we obtain high-speed implementations of point multiplication that are up to 31% faster than the best previous published results on similar platforms. This research is crucial for advancing high-speed cryptography on new emerging processor architectures.

Category / Keywords: Implementation / Elliptic curve cryptosystem, point multiplication, field arithmetic scheduling, incomplete reduction, data dependence, pipeline stall, x86-64 instruction set, software implementation.

Date: received 8 Jun 2010, last revised 9 Jun 2010

Contact author: plonga at uwaterloo ca

Available format(s): PDF | BibTeX Citation

Version: 20100613:182001 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]