High Speed RSA Implementation Based on Modified Booth's Technique and Montgomery's Multiplication for FPGA Platform

Abstract

Rivest, Shamir and Adleman (RSA) encryption algorithm is one of the most widely used and popular public-key cryptosystem. The main step in this algorithm is modular exponentiation which can be done by a sequence of modular multiplication. Thus, modular multiplication is the major factor, in many cryptosystems, e.g. the RSA Two-Key system and in the proposed digital signature standard DSS. One of the most efficient algorithms of modular multiplication is the Montgomery multiplication. In this paper, modified radix-4 modular multiplication was developed based on Booth's multiplication technique. We use CSA (Carry Save Adder) to avoid carry propagation. Also a very fast algorithm was presented and used for computing the modular reduction. We proposed new hardware architecture for optimum implementation of this algorithm. According to our design, for encrypting an n-bit plaintext, we need to about 3/4n (n + 11) clock cycles. We used Xilinx VirtexII and XC4000 series FPGAs (Field Programmable Gate Array). As a result, it is shown that the processor can perform 1024-bit RSA operation in less than 15ms and 50ms at 54.6MHz and 16.1MHz on Xilinx VirtexII and XC4000 series FPGA, respectively. Finally we compared our results with the previous works. We can say that a significant improvement was achieved in terms of time and in terms of used time-area (TA) our work is good.