Cryptography and the RNS


The Residue Number System (RNS) is a powerful tool to obtain parallel versions of algorithms. RNS relies in alternative representations of integers, which are operands of several algorithms including the cryptographic ones. In this research thread I focus cryptographic algorithms related to Elliptic Curve (EC) cryptography and I have been rewriting/optimizing these algorithms to obtain efficient parallel versions of them. Specifically, I have been bringing up several key RNS algorithms, including the so called Basis Extension methods. The advantages in obtaining such optimized parallel versions are the following: the computing platforms are evolving to a more yet simple processing cores paradigm, thus these algorithms can extract full advantage of such platforms. An example of such platforms are the Graphical Processing Units (GPUs), but other platforms such as FPGAs can be targeted.

Related Publications:

  • Antão, S., Bajard, J.-C., & Sousa, L. (2010). Elliptic Curve point multiplication on GPUs. IEEE International Conference on Application-specific Systems Architectures and Processors - ASAP (pp. 192–199). Rennes: IEEE. doi:10.1109/ASAP.2010.5541000 (bibtex)

IBM Research  IST link  INESC-ID link  Sips link