Cryptology ePrint Archive: Report 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.
Category / Keywords: implementation / Cell Broadband Engine, elliptic-curve cryptography (ECC), efficient implementation
Date: received 7 Jan 2009, last revised 1 Apr 2009
Contact author: peter at cryptojedi org
Available format(s): PDF | BibTeX Citation
Note: Added cycle counts for Montgomery reduction and some minor typo
corrections
Version: 20090401:084815 (All versions of this report)
Short URL: ia.cr/2009/016
[ Cryptology ePrint archive ]