Carry-save Montgomery modular exponentiation on reconfigurable hardware

In this paper we present a hardware implementation of the RSA algorithm for public-key cryptography. Basically, the RSA algorithm entails a modular exponentiation operation on large integers, which is considerably time-consuming to implement. To this end, we adopted a novel algorithm combining the Montgomery´s technique and the carry-save representation of numbers. A highly modular, bit-slice based architecture has been designed for executing the algorithm in hardware. We also propose an FPGA-based implementation of the architecture developed. The characteristics of the algorithm, the regularity of the architecture, and the data-flow aware placement of the FPGA resources resulted in a considerable performance improvement, as compared to other implementations presented in the literature.