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

Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/28832 |

Date | 23 July 2002 |

Creators | Mhaidat, Khaldoon |

Contributors | Tenca, Alexandre F. |

Source Sets | Oregon State University |

Language | en_US |

Detected Language | English |

Type | Thesis/Dissertation |

Page generated in 0.0014 seconds