A Hardware-Accelerated ECDLP with High-Performance Modular Multiplication

Elliptic curve cryptography (ECC) has become a popular public key cryptography standard. The security of ECC is due to the difficulty of solving the elliptic curve discrete logarithm problem (ECDLP). In this paper, we demonstrate a successful attack on ECC over prime field using the Pollard rho algorithm implemented on a hardware-software cointegrated platform. We propose a high-performance architecture for multiplication over prime field using specialized DSP blocks in the FPGA. We characterize this architecture by exploring the design space to determine the optimal integer basis for polynomial representation and we demonstrate an efficient mapping of this design to multiple standard prime field elliptic curves. We use the resulting modular multiplier to demonstrate low-latency multiplications for curves secp112r1 and P-192. We apply our modular multiplier to implement a complete attack on secp112r1 using a Nallatech FSB-Compute platform with Virtex-5 FPGA. The measured performance of the resulting design is 114 cycles per Pollard rho step at 100？MHz, which gives 878？K iterations per second per ECC core. We extend this design to a multicore ECDLP implementation that achieves 14.05？M iterations per second with 16 parallel point addition cores. 1. Introduction Elliptic curve cryptosystems (ECC), independently introduced by Miller [1] and Koblitz [2], have now found significant place in the academic literature, practical applications, and security standards. Their popularity is mainly because their shorter key sizes offer high levels of security relative to other public key cryptosystems, such as RSA. The security of ECC relies on the difficulty of elliptic curve discrete logarithmic problem (ECDLP) [3]. By definition, ECDLP is to find an integer for two points and on an elliptic curve defined over a finite field such that Here, denotes the scalar multiplication with . The Pollard rho method [4] is the strongest known attack against ECC today. This method solves ECDLP by generating points on the curve iteratively using a pseudorandom iteration function such that . Since the elliptic curve is defined over a finite field, is finite and the walk will eventually encounter the same point twice resulting in a collision. When a collision occurs, the ECDLP is solved (for well-chosen form of ; see Section 3). Several optimizations to the Pollard rho method have been proposed to allow independent parallel walks [5], better iteration functions [6, 7], and more efficient collision detection [8]. There have been several different approaches to implement Pollard rho