Abstract:
Modular exponentiation and modular multiplication are the most used
operations in current cryptographic systems. Some well-known cryptographic
algorithms, such as RSA, Diffie-Hellman key exchange, and DSA, require modular
exponentiation operations. This is performed with a series of modular multiplications
to the extent of its exponent in a certain fashion depending on the exponentiation
algorithm used.
Cryptographic functions are very likely to be applied in current applications
that perform information exchange to secure, verify, or authenticate data. Most notable
is the use of such applications in Internet based information exchange. Smart cards,
hand-helds, cell phones and many other small devices also need to perform
information exchange and are likely to apply cryptographic functions.
A hardware solution to perform a cryptographic function is generally faster and
more secure than a software solution. Thus, a fast and area efficient modular
exponentiation hardware solution would provide a better infrastructure for current
cryptographic techniques.
In certain cryptographic algorithms, very large precisions are used. Further, the
precision may vary. Most of the hardware designs for modular multiplication and
modular exponentiation are fixed-precision solutions. A scalable Montgomery
Multiplier (MM) to perform modular multiplication has been proposed and can
operate on input values of any bit-size, but the maximum bit-size should be known and
is the limiting factor. The multiplier can calculate any operand size less than the
maximal precision. However, this design's parameters should be optimized depending
on the operand precision for which the design is used.
A software application was developed in C to find the optimized design for the
scalable MM module. It performs area-time trade-off for the most commonly used
precisions in order to obtain a fast and area efficient solution for the common case.
A modular exponentiation system is developed using this scalable multiplier
design. Since the multiplier can operate on any operand size up to a certain maximum
value, the exponentiation system that utilizes the multiplier will inherit the same
capability.
This thesis work presents the design and implementation of an exponentiation
algorithm in hardware utilizing the optimized scalable Montgomery Multiplier. The
design uses a parallel exponentiation algorithm to reduce the total computation time.
The modular exponentiation system experimental results are analyzed and
compared with software and other hardware implementations.
