© The Institution of Engineering and Technology
Modular inversion is a fundamental process in several cryptographic systems. It can be computed in software or hardware, but hardware computation has been proven to be faster and more secure. This research focused on improving an old scalable inversion hardware architecture proposed in 2004 for finite field GF(p). The architecture comprises two parts, a computing unit and a memory unit. The memory unit holds all the data bits of computation whereas the computing unit performs all the arithmetic operations in word (digit) by word bases such that the design is scalable. The main objective of this paper is to show the cost and benefit of modifying the memory unit to include shifting, which was previously one of the tasks of the scalable computing unit. The study included remodeling the entire hardware architecture removing the shifter from the scalable computing part and embedding it in the non-scalable memory unit instead. This modification resulted in a speedup to the complete inversion process with an area increase due to the new memory shifting unit. Several design schemes have been compared giving the user the complete picture to choose from depending on the application need.
References
-
-
1)
-
Feldhofer, M., Trathnigg, T., Schnitzer, B.: `A self-timed arithmetic unit for elliptic curve cryptography', Proc. Euromicro Symp. on Digital System Design (DSD), 2002.
-
2)
-
I. Blake ,
G. Seroussi ,
N. Smart
.
Elliptic curves in cryptography.
-
3)
-
N. Takagi
.
Modular inversion hardware with a redundant binary representation.
IEICE Trans. Inform. Syst.
,
8 ,
863 -
869
-
4)
-
S. Fenn ,
M. Benaissa ,
D. Taylor
.
GF(2m) multiplication and division over the dual basis.
IEEE Trans. Computers
,
3 ,
319 -
327
-
5)
-
M. Ercegovac ,
T. Lang ,
J. Moreno
.
(1999)
Introduction to Digital System.
-
6)
-
P. Montgomery
.
Modular multiplication without trail division.
Mathematics Computation
,
170 ,
519 -
521
-
7)
-
Zhou, T., Wu, X., Bai, G., Chen, H.: `New algorithm and fast VLSI implementation for modular inversion in galois field GF(p)', IEEE Int. Conf. on Communications, Circuits and Systems, 2002, 2, p. 1491–1495.
-
8)
-
N. Takagi
.
A VLSI algorithm for modular division based on the binary GCD algorithm.
IEICE Trans. Fundamentals of Electron., Commun. Computer Sciences
,
5 ,
724 -
728
-
9)
-
C. McIvor ,
M. McLoone ,
J. McCanny
.
Improved montgomery modular inverse algorithm.
Electron. Lett.
,
18 ,
1110 -
1111
-
10)
-
G. Feng
.
A VLSI architecture for fast inversion in GF(2m).
IEEE Trans. Computers
,
10 ,
1383 -
1386
-
11)
-
E. Savas ,
C. Koc
.
The montgomery modular inverse–revisited.
IEEE Trans. Computers
,
7 ,
763 -
766
-
12)
-
T. Kobayashi ,
H. Morita
.
Fast modular inversion algorithm to match any operation unit.
IEICE Trans. Fundamentals
,
5 ,
733 -
740
-
13)
-
M. Kovac ,
N. Ranganathan ,
M. Varanasi
.
SIGMA: A VLSI systolic array implementation of galois field GF(2m) based multiplication and division algorithm.
IEEE Trans. VLSI
,
1 ,
22 -
30
-
14)
-
Hasan, M.A.: `Efficient computation of multiplicative inverse for cryptographic applications', Proc. 15th IEEE Symp. on Computer Arithmetic, 2001.
-
15)
-
http://www.mentor.com/partners/hep/AsicDesignKit/dsheet/ami05databook.html, Mentor Graphics Co., ASIC Design Kit., accessed January 2006.
-
16)
-
Dormale, G., Bulens, P., Quisquater, J.: `An improved montgomery modular inversion targeted for efficient implementation on FPGA', Int. Conf. on Field-Programmable Technology (FPT), 2004, p. 441–444.
-
17)
-
D. Hankerson ,
J. Menezes ,
J. Hernandez
.
(2000)
Software implementation of elliptic curve cryptography over binary fields.
-
18)
-
Fiaz, F., Masud, S.: `Design and implementation of a hardware divider in finite field', National Conf. on Emerging Technologies, 2004.
-
19)
-
Daly, A., Marnane, W., Popovici, E.: `Fast modular inversion in the montgomery domain on reconfigurable logic', Irish Signals and Systems Conf. (ISSC), 2003, p. 362–367.
-
20)
-
Tawalbeh, L., Tenca, A., Park, S., Koc, C.: `A dual-field modular division algorithm and architecture for application specific hardware', Thirty-Eighth Asilomar Conf. on Signals, Systems and Computers, 2004, 1, p. 483–487.
-
21)
-
Gutub, A., Tenca, A., Koc, C.: `Scalable VLSI architecture for GF(p) montgomery modular inverse computation', IEEE Computer Society Annual Symp. on VLSI (ISVLSI), 2002, Pittsburgh, Pennsylvania.
-
22)
-
Gutub, A., Tenca, A.: `Efficient scalable hardware architecture for montgomery inverse computation in GF(P)', IEEE Workshop on Signal Processing Systems (SIPS), 2003, p. 93–98.
-
23)
-
C. Wang ,
T. Truong ,
H. Shao ,
L. Deutsch ,
J. Omura ,
I. Reed
.
VLSI architectures for computing multiplications and inverses in GF(2m).
IEEE Trans. Computers
,
8 ,
709 -
717
-
24)
-
T. Zhou ,
X. Wu ,
G. Bai ,
H. Chen
.
Fast GF(p) modular inversion algorithm suitable for VLSI implementation.
Electron. Lett.
,
14 ,
706 -
707
-
25)
-
J. Guo ,
C. Wang
.
Systolic array implementation of Euclid's algorithm for inversion and division in GF(2m).
IEEE Trans. Computers
,
10 ,
1161 -
1167
-
26)
-
A. Gutub ,
A. Tenca
.
Efficient scalable VLSI architecture for montgomery inversion in GF(p).
Integration, The VLSI J.
,
2 ,
103 -
120
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt_20060183
Related content
content/journals/10.1049/iet-cdt_20060183
pub_keyword,iet_inspecKeyword,pub_concept
6
6