Efficient Public-key Cryptography using Spectral Arithmetic and Residue Number Systems

This proposal aims to carry out algorithmic complexity analysis and efficient hardware / software designs for public-key cryptography, with the use of novel Montgomery multiplier using residue number systems (RNS) and spectral arithmetic. This work targets reducing run-time requirements and optimizing power consumption for potential real-world applications in many areas including the RSA, ECC and Pairing-based cryptography. First, the classical Montgomery algorithm will be combined with the residue number systems (RNS) to reduce the multiplication complexity by using novel base selection in RNS. Second, the Montgomery algorithm using spectral modular arithmetic, which performs computations in the spectral domain, will be also characterized and implemented. Finally, the RNS-Montgomery and Spectral-Montgomery will be both developed into a software library that can be integrated into public library such as the GNU Multiple Precision Arithmetic Library (GMP), and also developed into area-efficient and time-efficient hardware for FPGA implementations. The scalability and reconfigurability of the hardware designs will be also addressed.