© 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 nonscalable 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)

I. Blake ,
G. Seroussi ,
N. Smart
.
Elliptic curves in cryptography.

2)

E. Savas ,
C. Koc
.
The montgomery modular inverse–revisited.
IEEE Trans. Computers
,
7 ,
763 
766

3)

T. Kobayashi ,
H. Morita
.
Fast modular inversion algorithm to match any operation unit.
IEICE Trans. Fundamentals
,
5 ,
733 
740

4)

D. Hankerson ,
J. Menezes ,
J. Hernandez
.
(2000)
Software implementation of elliptic curve cryptography over binary fields.

5)

N. Takagi
.
Modular inversion hardware with a redundant binary representation.
IEICE Trans. Inform. Syst.
,
8 ,
863 
869

6)

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

7)

Hasan, M.A.: `Efficient computation of multiplicative inverse for cryptographic applications', Proc. 15th IEEE Symp. on Computer Arithmetic, 2001.

8)

J. Guo ,
C. Wang
.
Systolic array implementation of Euclid's algorithm for inversion and division in GF(2m).
IEEE Trans. Computers
,
10 ,
1161 
1167

9)

S. Fenn ,
M. Benaissa ,
D. Taylor
.
GF(2m) multiplication and division over the dual basis.
IEEE Trans. Computers
,
3 ,
319 
327

10)

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

11)

G. Feng
.
A VLSI architecture for fast inversion in GF(2m).
IEEE Trans. Computers
,
10 ,
1383 
1386

12)

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

13)

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.

14)

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.

15)

T. Zhou ,
X. Wu ,
G. Bai ,
H. Chen
.
Fast GF(p) modular inversion algorithm suitable for VLSI implementation.
Electron. Lett.
,
14 ,
706 
707

16)

C. McIvor ,
M. McLoone ,
J. McCanny
.
Improved montgomery modular inverse algorithm.
Electron. Lett.
,
18 ,
1110 
1111

17)

Dormale, G., Bulens, P., Quisquater, J.: `An improved montgomery modular inversion targeted for efficient implementation on FPGA', Int. Conf. on FieldProgrammable Technology (FPT), 2004, p. 441–444.

18)

Fiaz, F., Masud, S.: `Design and implementation of a hardware divider in finite field', National Conf. on Emerging Technologies, 2004.

19)

Feldhofer, M., Trathnigg, T., Schnitzer, B.: `A selftimed arithmetic unit for elliptic curve cryptography', Proc. Euromicro Symp. on Digital System Design (DSD), 2002.

20)

Tawalbeh, L., Tenca, A., Park, S., Koc, C.: `A dualfield modular division algorithm and architecture for application specific hardware', ThirtyEighth 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)

A. Gutub ,
A. Tenca
.
Efficient scalable VLSI architecture for montgomery inversion in GF(p).
Integration, The VLSI J.
,
2 ,
103 
120

23)

P. Montgomery
.
Modular multiplication without trail division.
Mathematics Computation
,
170 ,
519 
521

24)

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.

25)

M. Ercegovac ,
T. Lang ,
J. Moreno
.
(1999)
Introduction to Digital System.

26)

http://www.mentor.com/partners/hep/AsicDesignKit/dsheet/ami05databook.html, Mentor Graphics Co., ASIC Design Kit., accessed January 2006.
http://iet.metastore.ingenta.com/content/journals/10.1049/ietcdt_20060183
Related content
content/journals/10.1049/ietcdt_20060183
pub_keyword,iet_inspecKeyword,pub_concept
6
6