An RSA encryption implementation method using residue signed-digit arithmetic circuits

This paper proposes an RSA encryption method using a sequential modular multiplication based on residue signed-digit (SD) number arithmetic. For a large modulus m with a length of (p+1)-bit used as a key in RSA public-key cryptosystem, a complement of m, m* = m - 2^p, with the p-digit SD number representation is used to calculate the modular operations. By introducing a p-digit radix-two SD number system into the residue arithmetic, a modular addition is easily implemented by using two SD adders for a modulus M, and no carry propagations will arise during the additions. In order to reduce the hardware cost and the delay time of the SD adders, we present a new architecture using binary numbers for the intermediate sum and carry within the SD adder. We also give a new architecture with the proposed residue SD adders to realize a faster modular multiplication. The design result shows that a modular multiplier can be improved in computing time and area based on the presented method.