|Abstract or Summary
- 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
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
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.