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.