Return to search

Prototyping a scalable Montgomery multiplier using field programmable gate arrays (FPGAs)

Modular Multiplication is a time-consuming arithmetic operation because it
involves multiplication as well as division. Modular exponentiation can be performed
as a sequence of modular multiplications. Speeding the modular multiplication
increases the speed of modular exponentiation. Modular exponentiation and modular
multiplication are heavily used in current cryptographic systems. Well-known
cryptographic algorithms, such as RSA and Diffie-Hellman key exchange, require
modular exponentiation operations. Elliptic curve cryptography (ECC) needs modular
multiplication.
Information security is increasingly becoming very important. Encryption and
Decryption are very likely to be in many systems that exchange information to secure,
verify, or authenticate data. Many systems, like the Internet, cellular phones, hand-held
devices, and E-commerce, involve private and important information exchange
and they need cryptography to make it secure.
There are three possible solutions to accomplish the cryptographic
computation: software, hardware using application-specific integrated circuits
(ASICs), and hardware using field-programmable gate arrays (FPGAs). The software
solution is the cheapest and most flexible one. But, it is the slowest. The ASIC
solution is the fastest. But, it is inflexible, very expensive, and needs long
development time. The FPGA solution is flexible, reasonably fast, and needs shorter
development time.
Montgomery multiplication algorithm is a very smart and efficient algorithm
for calculating the modular multiplication. It replaces the division by a shift and
modulus-addition (if needed) operations, which are much faster than regular division.
The algorithm is also very suitable for a hardware implementation. Many designs have
been proposed for fixed precision operands. A word-based algorithm and the scalable
Montgomery multiplier based on this algorithm have been proposed later. The scalable
multiplier can be configured to meet the design area-time tradeoff. Also, it can work
for any operand precision up to the memory capacity.
In this thesis, we develop a prototyping environment that can be used to verify
the functionality of the scalable Montgomery multiplier on the circuit level. All the
software, hardware, and firmware components of this environment will be described.
Also, we will discuss how this environment can be used to develop cryptographic
applications or test procedures on top of it.
We also present two FPGA designs of the processing unit of the scalable
Montgomery multiplier. The FPGA design techniques that have been used to optimize
these designs are described. The implementation results are analyzed and the designs
are compared against each other. The FPGA implementation of the first design is also
compared against its ASIC implementation. / Graduation date: 2003

Identiferoai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/28832
Date23 July 2002
CreatorsMhaidat, Khaldoon
ContributorsTenca, Alexandre F.
Source SetsOregon State University
Languageen_US
Detected LanguageEnglish
TypeThesis/Dissertation

Page generated in 0.0018 seconds