Efficient Implementation Of The Sum Of Residues Modular Reduction Using Arithmetic-Friendly RNS Moduli Set

Abstract

Introduction: Due to the importance of public-key cryptography in information and communication security, it is widely employed in various applications for secure communication.

Materials and Methods: multiplication and exponentiation of large numbers are used in cryptography algorithms such as RSA, ElGamal, and elliptic curve cryptography. Results and Discussion: The residue number system in these algorithms is very efficient since calculations are performed on small residues, resulting in a fast arithmetic operation, as well as lower power consumption. The modular reduction of large numbers is one of the main operations in most public-key cryptography systems, which includes large computations in finite fields. This paper presents an efficient implementation of modular reduction. To this end, arithmetic-friendly moduli were selected and employed in the implementation of the improved sum of residues reduction algorithm. The SOR algorithm using the proposed moduli set was described in VHDL language and synthesized on the Xilinx virtex7 FPGA family using ISE14.7 software.

Conclusion: The results showed that, compared to the recent similar works, the implementation of the improved sum of residues algorithm using the proposed moduli set has achieved higher speed and uses less hardware resources.