Worcester Polytechnic Institute Electronic Theses and Dissertations Collection

Title page for ETD etd-0430102-120529

Document Typethesis
Author NameGaubatz, Gunnar
TitleVersatile Montgomery Multiplier Architectures
DepartmentElectrical & Computer Engineering
  • Prof. Berk Sunar, Advisor
  • Prof. Fred J. Looft, Committee Member
  • Prof. John A. McNeill, Committee Member
  • Prof. John A. Orr, Department Head
  • Keywords
  • computer arithmetic
  • modular multiplication
  • public key cryptography
  • montgomery
  • vlsi
  • high radix
  • Date of Presentation/Defense2002-04-26
    Availability unrestricted


    Several algorithms for Public Key Cryptography (PKC), such as RSA, Diffie-Hellman, and Elliptic Curve Cryptography, require modular multiplication of very large operands (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 respect to word size and pipelining depth. To our knowledge, this is the first time a word based algorithm for Montgomery's method is realized using high-radix bit-parallel multipliers working with two different types of finite fields (unified 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 finite field. 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 complexity O(n).

    Our design has been implemented in VHDL, simulated and synthesized in 0.5μ CMOS technology. The synthesized net list has been verified in back-annotated timing simulations and analyzed in terms of performance and area consumption.

  • gaubatz.pdf

  • Browse by Author | Browse by Department | Search all available ETDs

    [WPI] [Library] [Home] [Top]

    Questions? Email etd-questions@wpi.edu
    Maintained by webmaster@wpi.edu