An Efficient Montgomery Multiplication Algorithm and RSA Cryptographic Processor
Richa Garg, Renu Vig · 2007
New, generic silicon architecture for implementing Montgomery's multiplication algorithm is presented. This paper proposes an efficient Montgomery modular multiplication technique that employs multi-bit shifting and carry-save addition to perform long-integer arithmetic. The gain in data throughput for Montgomery multiplication is approximately 45.49% (for 1024-bit length) and the hardware reduction is 24.27% of the traditional methods. Hence, the corresponding hardware realization is optimal in terms of area and offer higher data throughput for Montgomery multiplication. The practical application of this approach has been demonstrated by applying this to the design of RSA processor architecture with 512-bit and 1024-bit key size. The RSA processor also offers higher throughput (32.18% for 1024-bit) with a slight increase in area (22.4%). This optimization is also technology independent and thus should suit well not only FPGA implementation but also ASIC. The Montgomery design and RSA processor has been evaluated on Xilinx Virtex-4 series for the practical bit lengths of 512, 1024 and 2048. The resulting Montgomery multiplier and the RSA processor performance results presented at the fastest reported to date in literature.