Fast Montgomery modular multiplication and RSA cryptographic processor architectures

Abstract

New, generic silicon architectures for implementing Montgomery's multiplication algorithm are presented. These use carry save adders (CSAs) to perform the large word length additions required by this algorithm when used for RSA encryption and decryption. It is shown that using a four-to-two CSA with two extra registers rather than a five-to-two CSA leads to a useful reduction in the critical path of the multiplier, albeit at the expense of a small increase in circuitry. For operand lengths of 1536-bits and greater, the percentage gain in data throughput rate outweighs the percentage increase in silicon area. Moreover, for a 2048-bit operand length, typical of what is required in many future generation applications, the gain in data throughput is 27.9% compared with a 9.9% increase in area. The practical application of this approach has been demonstrated by applying this to the design of RSA processor architectures with 512-bit and 1024-bit key sizes. The resulting Montgomery multiplier and RSA processor performance results presented are the fastest reported to date in the literature.