Fast elliptic-curve cryptography on the Cell Broadband Engine

Neil Costigan; Peter Schwabe

Paper 2009/016

Fast elliptic-curve cryptography on the Cell Broadband Engine

Neil Costigan and Peter Schwabe

Abstract

This paper is the first to investigate the power of the Cell Broadband Engine for state-of-the-art public-key cryptography. We pre- sent a high-speed implementation of elliptic-curve Diffie-Hellman (ECDH) key exchange for this processor, which needs 697080 cycles on one Syn- ergistic Processor Unit for a scalar multiplication on a 255-bit elliptic curve, including the costs for key verification and key compression. This cycle count is independent of inputs therefore protecting against timing attacks. This speed relies on a new representation of elements of the underlying finite field suited for the unconventional instruction set of this architec- ture. Furthermore we demonstrate that an implementation based on the multi- precision integer arithmetic functions provided by IBM's multi-precision math (MPM) library would take at least 2227040 cycles. Comparison with implementations of the same function for other archi- tectures shows that the Cell Broadband Engine is competitive in terms of cost-performance ratio to other recent processors such as the Intel Core 2 for public-key cryptography. Specifically, the state-of-the-art Galbraith-Lin-Scott ECDH software per- forms 27370 scalar multiplications per second using all four cores of a 2.5GHz Intel Core 2 Quad Q9300 inside a $296 computer, while the new software reported in this paper performs 27474 scalar multiplications per second on a Playstation 3 that costs just $221. Both of these speed reports are for high-security 256-bit elliptic-curve cryptography.

Note: Added cycle counts for Montgomery reduction and some minor typo corrections

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Published elsewhere. Unknown where it was published
Keywords: Cell Broadband Engine elliptic-curve cryptography (ECC)efficient implementation
Contact author(s): peter @ cryptojedi org
History: 2009-04-01: last of 4 revisions; 2009-01-13: received; See all versions
Short URL: https://ia.cr/2009/016
License: CC BY

BibTeX

@misc{cryptoeprint:2009/016,
      author = {Neil Costigan and Peter Schwabe},
      title = {Fast elliptic-curve cryptography on the Cell Broadband Engine},
      howpublished = {Cryptology ePrint Archive, Paper 2009/016},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/016}},
      url = {https://eprint.iacr.org/2009/016}
}