RNS-Based Elliptic Curve Point Multiplication for Massive Parallel Architectures

Samuel Antao, Jean-Claude Bajard, Leonel Sousa
Instituto Superior Tecnico/INESC-ID, Technical University of Lisbon, Lisbon, Portugal
The Computer Journal, 2011


   title={RNS-Based Elliptic Curve Point Multiplication for Massive Parallel Architectures},

   author={Ant{~a}o, S. and Bajard, J.C. and Sousa, L.},

   journal={The Computer Journal},


   publisher={Br Computer Soc}


Download Download (PDF)   View View   Source Source   



Acceleration of cryptographic applications on massive parallel computing platforms, such as Graphic Processing Units (GPUs), becomes a real challenge concerning practical implementations. In this paper, we propose a parallel algorithm for Elliptic Curve (EC) point multiplication in order to compute EC cryptography on these platforms. The proposed approach relies on the usage of the Residue Number System (RNS) to extract parallelism on high-precision integer arithmetic. Results suggest a maximum throughput of 9827 EC multiplications per second and minimum latency of 29.2 ms for a 224-bit underlying field, in a commercial Nvidia 285 GTX GPU. Performances up to an order of magnitude better in latency and 122% in throughput are achieved regarding other approaches reported in the related art. An experimental analysis of the scalability, based on OpenCL descriptions of the proposed algorithms, suggest that further advantage can be obtained from the proposed RNS approach for GPUs and EC curves supported by underlying finite fields of smaller size, regarding implementations on general purpose multi-cores.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: