Declaration of Authorship
- 格式：pdf
- 大小：276.32 KB
- 文档页数：58
Efficient Hardware Architectures for
Modular Multiplication
by
David Narh Amanor
A Thesis
submitted to
The University of Applied Sciences Offenburg, Germany
In partial fulfillment of the requirements for the
Degree of Master of Science
in
Communication and Media Engineering
February, 2005
Approved:
Prof. Dr. Angelika Erhardt Prof. Dr. Christof Paar
Thesis Supervisor Thesis Supervisor
Declaration of Authorship
“I declare in lieu of an oath that the Master thesis submitted has been produced by
me without illegal help from other persons. I state that all passages which have
been taken out of publications of all means or unpublished material either whole or
in part, in words or ideas, have been marked as quotations in the relevant
passage. I also confirm that the quotes included show the extent of the original
quotes and are marked as such. I know that a false declaration will
have legal consequences.”
David Narh Amanor
February, 2005
ii
Preface
This thesis describes the research which I conducted while completing my
graduate work at the University of Applied Sciences Offenburg, Germany.
The work produced scalable hardware implementations of existing and newly
proposed algorithms for performing modular multiplication.
The work presented can be instrumental in generating interest in the hardware
implementation of emerging algorithms for doing faster modular multiplication, and
can also be used in future research projects at the University of Applied Sciences
Offenburg, Germany, and elsewhere.
Of particular interest is the integration of the new architectures into existing public-
key cryptosystems such as RSA, DSA, and ECC to speed up the arithmetic.
I wish to thank the following people for their unselfish support throughout the entire
duration of this thesis.
I would like to thank my external advisor Prof. Christof Paar for providing me with
all the tools and materials needed to conduct this research. I am particularly
grateful to Dipl.-Ing. Jan Pelzl, who worked with me closely, and whose constant
encouragement and advice gave me the energy to overcome several problems I
encountered while working on this thesis.
I wish to express my deepest gratitude to my supervisor Prof. Angelika Erhardt for
being in constant touch with me and for all the help and advice she gave
throughout all stages of the thesis. If it was not for Prof. Erhardt, I would not have
had the opportunity of doing this thesis work and therefore, I would have missed
out on a very rewarding experience.
I am also grateful to Dipl.-Ing. Viktor Buminov and Prof. Manfred Schimmler,
whose newly proposed algorithms and corresponding architectures form the basis
of my thesis work and provide the necessary theoretical material for understanding
the algorithms presented in this thesis.
Finally, I would like to thank my brother, Mr. Samuel Kwesi Amanor, my friend and
Pastor, Josiah Kwofie, Mr. Samuel Siaw Nartey and Mr. Csaba Karasz for their
diverse support which enabled me to undertake my thesis work in Bochum.
iii
Abstract
Modular multiplication is a core operation in many public-key cryptosystems, e.g.,
RSA, Diffie-Hellman key agreement (DH), ElGamal, and ECC. The Montgomery
multiplication algorithm [2] is considered to be the fastest algorithm to compute X*Y
mod M in computers when the values of X, Y and M are large.
Recently, two new algorithms for modular multiplication and their corresponding
architectures were proposed in [1]. These algorithms are optimizations of the
Montgomery multiplication algorithm [2] and interleaved modular multiplication
algorithm [3].
In this thesis, software (Java) and hardware (VHDL) implementations of the
existing and newly proposed algorithms and their corresponding architectures for
performing modular multiplication have been done. In summary, three different
multipliers for 32, 64, 128, 256, 512, and 1024 bits were implemented, simulated,
and synthesized for a Xilinx FPGA. The implementations are scalable to any
precision of the input variables X, Y and M.
This thesis also evaluated the performance of the multipliers in [1] by a thorough
comparison of the architectures on the basis of the area-time product.
This thesis finally shows that the newly optimized algorithms and their
corresponding architectures in [1] require minimum hardware resources and offer
faster speed of computation compared to multipliers with the original Montgomery
algorithm.
iv
