Versatile Montgomery multiplier architectures

Several algorithms for Public Key Cryptography (PKC), such as RSA, Die-Hellman, and Elliptic Curve Cryptography, require modular multiplication of very large oper-ands (sizes from 160 to 4096 bits) as their core arithmetic operation. To perform this operation reasonably fast, general purpose processors are not always the best choice. This is why specialized hardware, in the form of cryptographic co-processors, become more attractive. Based upon the analysis of recent publications on hardware design for modular multiplication, this M.S. thesis presents a new architecture that is scalable with re-spect to word size and pipelining depth. To our knowledge, this is the rst time a word based algorithm for Montgomery's method is realized using high-radix bit-parallel multipliers working with two dierent types of nite elds (unied architecture for GF (p) and GF (2n)). Previous approaches have relied mostly on bit serial multiplication in combination with massive pipelining, or Radix-8 multiplication with the limitation to a single type of nite eld. Our approach is centered around the notion that the optimal delay in bit-parallel multipliers grows with logarithmic complexity with respect to the operand size n, O(log3=2 n), while the delay of bit serial implementations grows with linear i complexity O(n). Our design has been implemented in VHDL, simulated and synthesized in 0.5 CMOS technology. The synthesized net list has been veried in back-annotated timing simulations and analyzed in terms of performance and area consumption. i