Prototyping of Scalable Montgomery Multiplier using Field Programmable Gate Arrays (FPGAs)

M. Khaldoon

M.S. Thesis, Department of Electrical & Computer Engineering, Oregon State University, July 23, 2002.

Abstract

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 will have a great impact on 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 ASICs solution is the fastest. But, it is inflexible, very expensive, and needs long development time. The FPGAs solution is flexible, 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) operation, which are much faster. The algorithm is also very suitable for a hardware implementation. Many designs have been proposed for fixed precision operands. A word-based algorithm has been proposed later and the scalable Montgomery multiplier is based on this modified algorithm. This multiplier can be configured to meet the design area-time tradeoff. Also, it can work for any operand precision up to maximum design memory capability.

In this thesis, we will 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 on top of it.

In this thesis, we will also present two FPGA designs of the multiplication unit of the scalable Montgomery multiplier. The FPGA design techniques that have been used to optimize these designs will be described. Their implementation results will be analyzed and compared against each other. The FPGA implementation of the first one will be compared against its ASIC implementation.