Design and Implementation of Efficient Modulo 2n±1 Multipliers and their Application in Cryptography

Abstract

Residue Number System (RNS) is often adopted to implement long and repetitive multiplications of cryptographic and signal processing algorithms. To sustain the competitive advantages of RNS over two's complement system, a new low power and low area modulo multipliers for the well-established {2ⁿ-1, 2ⁿ, 2ⁿ+1} based RNS are proposed. The proposed modulo 2ⁿ-1 and modulo 2ⁿ+1 multipliers are based on the radix-8 Booth encoding technique. The requisite hard multiples in the critical path are generated by fast, customized parallel-prefix adders. Among the various techniques found in the cryptographic realm, the RSA algorithm constitutes the most widely adopted public-key scheme. The RSA algorithm entails a modular exponentiation operation on large integers, which is considerably time-consuming to implement. This can be replaced with fast modulo multiplication operations.