An Integrated Prime-Field ECDLP Hardware Accelerator with High-Performance Modular Arithmetic Units
Suvarna Mane, Lyndon Judge, Patrick R. Schaumont · 2011
This paper reports a successful demonstration of Pollard rho algorithm on a hardware-software co-integrated platform. It targets the Elliptic curve discrete logarithmic problem (ECDLP) for a NIST-standardized curve over 112- bit prime field. To the best of our knowledge, this is the first report on fully functional, demonstrated hardware-accelerated ECC cryptanalytic engine. Our implementation uses a highly optimized software implementation as reference [1] and develops a hardware version of it. This paper also describes a novel, generalized architecture for polynomial-basis multiplication over prime field and its extension to a dedicated square module. The resulting modular multiplier completes the multiplication within 14 clock cycles, which is 2.5X lower latency over earlier work [2]. We demonstrate our design on a Nallatech FSB-Compute platform with Virtex-5 FPGA. The implementation efficiently utilizes the dedicated DSP48 cores available in the used FPGA device. The measured performance of the resulting design is 151 cycles per Pollard rho step at 100MHz and upto 660K iterations per second per ECC core. With a multi-core implementation of our design, the performance can be comparable with that of the software implementation on a Cell processor [1]. Though the primary target of this implementation is 112-bit prime field, its design strategy can be applied to other prime field moduli.