|Abstract or Summary
- The spread of the internet and communications techniques increases the necessity
for security in applications that involves sharing or exchange of secret or private infor-
mation. Public-key cryptography is widely used in establishing secure communication
channels between the users on the Internet, for E-commerce transactions, and in net-
work security protocols. Public-key cryptography relies on algorithms from computer
arithmetic, number theory and algebra. The modular arithmetic operations, modular
division, and modular multiplication over ¯nite ¯elds (GF(p) and GF(2n)) are exten-
sively used in many public-key cryptosystems, such as RSA, ElGamal cryptosystem,
Di±e-Hellman key exchange algorithm, elliptic curve cryptography (ECC), and the Dig-
ital Signature Standard including the Elliptic Curve Digital Signature Algorithm. In
our research, we have mainly concentrated on hardware realization of the ECC since it
seems to provide similar amount of security using smaller key size.
The modular multiplication operation with a large modulus is very important in
many public-key cryptosystems. One of the most e±cient ways to compute modular mul-
tiplication is the Montgomery algorithm. Many e±cient Montgomery multiplier designs
were proposed up to now. On the other hand, computing modular division (inverse) is
a time-consuming process and cannot be avoided completely. It was claimed that a gain
in performance can be obtained when implementing the division (inverse) in hardware. In this work, we propose, with a mathematical proof, an e±cient uni¯ed division
algorithm to compute the modular division operation in GF(p) and GF(2n). The al-
gorithm uses a counter to keep track of the di®erence between two ¯eld elements and
this way eliminates the need for comparisons which are usually expensive and time-
consuming. An hardware architecture implementing the algorithm is also proposed.
The uni¯ed division algorithm is integrated with a uni¯ed Montgomery multipli-
cation algorithm to obtain a novel Uni¯ed Division/Multiplication Algorithm (UDMA).
The UDMA computes division (inverse) and multiplication in a very e±cient way in
both GF(p) and GF(2n) ¯elds. Also, we propose a uni¯ed hardware architecture that
e±ciently supports all operations in the UDMA and uses carry-save uni¯ed adders for re-
duced critical path delay, making the proposed architecture faster than other previously
Experimental results obtained by synthesizing the hardware design for AMI 0:5¹m
CMOS technology and FPGA V ertixII chip (xc2vp50 ¡ 7ff148 technology) are shown
and compared with other proposed dividers and multipliers.