Reconfigurable Architecture to Speed-up Modular Exponentiation

Diffie-Hellman and RSA encryption/decryption involve computationally intensive cryptographic operations such as modular exponentiation. Computing modular exponentiation using appropriate pre-computed pairs of bases and exponents was first proposed by Boyko et al. In this paper, we present a reconfigurable architecture for pre-computation methods to compute modular exponentiation and thereby speeding up RSA and Diffie-Hellman like protocols. We choose Diffie-Hellman key pair (a, g a mod p) to illustrate the efficiency of Boyko et al's scheme in hardware architecture that stores pre-computed values a i and corresponding g a i in individual block RAM. We use a Pseudo-random number generator (PRNG) to randomly choose a i values that are added and corresponding g a i values are multiplied using modular multiplier to arrive at a new pair (a, g a mod p). Further, we present the advantage of using Montgomery and interleaved methods for batch multiplication to optimise time and area. We show that a 1024-bit modular exponentiation can be performed in less than 73μs at a clock rate of 200MHz on a Xilinx Virtex 7 FPGA.