© The Institution of Engineering and Technology
A Montgomery's algorithm in GF(2m) based on the Hankel matrix–vector representation is proposed. The hardware architecture obtained from this algorithm indicates low-complexity bit-parallel systolic multipliers with irreducible trinomials. The results reveal that the proposed multiplier saves approximately 36% of space complexity as compared to an existing systolic Montgomery multiplier for trinomials. A scalable and systolic Montgomery multiplier is also developed by applying the block-Hankel matrix–vector representation. The proposed scalable systolic architecture is demonstrated to have significantly less time–area product complexity than existing digit-serial systolic architectures. Furthermore, the proposed architectures have regularity, modularity and local interconnectability, making them highly appropriate for VLSI implementation.
References
-
-
1)
-
‘M74HC08, Quad 2-Input AND Gate’, STMicroelectronics 2001, http://www.st.com/stonline/books/pdf/docs/1885.pdf.
-
2)
-
S.T.J. Fenn ,
D. Taylor ,
M. Benaissa
.
A dual basis bit-serial systolic multiplier for GF(2m).
Integr. VLSI J
,
139 -
149
-
3)
-
P.L. Montgomery
.
Modular multiplication without trial division.
Math. Comput.
,
519 -
521
-
4)
-
Mentens, N., Őrs, S.B., Preneel, B.: `An FPGA implementation of an elliptic curve processor over GF(2', Proc. 2004 Great Lakes Symp. on VLSI (GLSVLSI 2004), 2004, p. 454–457.
-
5)
-
N.-Y. Kim ,
K.-Y. Yoo
.
Digit-serial AB2 systolic architecture in GF(2m).
IEE Proc., Circuits Devices Syst.
,
6 ,
608 -
614
-
6)
-
C.Y. Lee ,
E.H. Lu ,
J.Y. Lee
.
Bit-parallel systolic multipliers for GF(2m) fields defined by all-one and equally-spaced polynomials.
IEEE Trans. Comput.
,
5 ,
385 -
393
-
7)
-
C. Paar ,
P. Fleischmann ,
P. Soria-Rodriguez
.
Fast arithmetic for public-key algorithms in Galois fields with composite exponents.
IEEE Trans. Comput.
,
10 ,
1025 -
1034
-
8)
-
C.Y. Lee
.
Low complexity bit-parallel systolic multiplier over GF(2m) using irreducible trinomials.
IEE Proc., Comput. Digit. Tech.
,
1 ,
39 -
42
-
9)
-
Gutub, A.A.-A., Tenca, A.F., Savas, E., Koc, C.K.: `Scalable and unified hardware to compute Montgomery inverse in GF(', Cryptographic hardware and embedded systems – CHES 2002, 2002, LNCS, 2523.
-
10)
-
‘M74HC86, Quad exclusive OR gate’, STMicroelectronics 2001http://www.st.com/stonline/books/pdf/docs/2006.pdf.
-
11)
-
R. Lidl ,
H. Niederreiter
.
(1997)
Finite fields.
-
12)
-
C.W. Chiou ,
C.Y. Lee ,
A.W. Deng ,
J.M. Lin
.
Concurrent error detection in Montgomery multiplication over GF(2m).
IEICE Trans. Fundam.
,
2 ,
566 -
574
-
13)
-
R. Lidl ,
H. Niederreiter
.
(1994)
Introduction to finite fields and their applications.
-
14)
-
C.Y. Lee ,
E.H. Lu ,
L.F. Sun
.
Low-complexity bit-parallel systolic architecture for computing AB2+C in a class of finite field GF(2m).
IEEE Trans. Circuits Syst. II
,
5 ,
519 -
523
-
15)
-
O. Nibouche ,
A. Bouridane ,
M. Nibouche
.
Architectures for Montgomery's multiplication.
IEE Proc., Comput. Digit. Tech.
,
6 ,
361 -
368
-
16)
-
C. Lee ,
J. Horng ,
I. Jou ,
E. Lu
.
Low-complexity bit parallel systolic Montgomery multipliers for special classes of GF(2m).
Trans. Comput.
,
9 ,
1061 -
1070
-
17)
-
Kwon, S., Kim, C.H., Hong, C.P.: `Unidirectional two dimensional systolic array for multiplication in GF(2', 6thInt. Workshop on Fuzzy Logic and Applications, WILF 2005, 2006, LNCS, 3849, p. 420–426.
-
18)
-
C.Y. Lee ,
C.W. Chiou ,
J.M. Lin
.
Concurrent error detection in a bit-parallel systolic multiplier for dual basis of GF(2m).
J. Electron. Test Theory Appl.
,
5 ,
539 -
549
-
19)
-
N.Y. Kim ,
H.S. Kim ,
K.Y. Yoo
.
Computation of AB2 multiplication in GF(2m) using low-complexity systolic architecture.
IEE Proc., Circuits Devices Syst.
,
2 ,
119 -
123
-
20)
-
C.-L. Wang ,
J.-L. Lin
.
Systolic array implementation of multipliers for finite fields GF(2m).
IEEE Trans. Circuits Syst.
,
7 ,
796 -
800
-
21)
-
`Digital signature standard', FIPS Publication 186-2, January 2000.
-
22)
-
B.B. Zhou
.
A new bit-serial systolic multiplier over GF(2m).
IEEE Trans. Comput.
,
6 ,
749 -
751
-
23)
-
Savas, E., Tenca, A.F., Koç, Ç.K.: `A scalable and unified multiplier architecture for finite fields GF(', Cryptographic hardware and embedded systems – CHES 2000, 2000, LNCS, 1965, p. 281–296.
-
24)
-
Ç.K. Koç ,
T. Acar
.
Montgomery multiplication in GF(2k).
Des. Codes Cryptogr.
,
57 -
69
-
25)
-
M74HC279, Quad S̄-R̄ Latch’, STMicroelectronics 2001http://www.st.com/stonline/books/pdf/docs/1937.pdf.
-
26)
-
B. Sunar ,
C.K. Koc
.
Mastrovito multiplier for all trinomials.
IEEE Trans. Comput.
,
5 ,
522 -
527
-
27)
-
C.Y. Lee ,
C.W. Chiou
.
Design of low-complexity bit-parallel systolic Hankel multipliers to implement multiplication in normal and dual bases of GF(2m).
IEICE Trans. Fundam.
,
11 ,
3169 -
3179
-
28)
-
S.M. Kang ,
Y. Leblebici
.
(1999)
CMOS digital integrated circuits-analysis and design.
-
29)
-
H. Wu
.
Montgomery multiplier and squarer for a class of finite fields.
IEEE Trans. Comput.
,
5 ,
521 -
529
-
30)
-
N. Weste ,
K. Eshraghian
.
(1985)
Principles of CMOS VLSI design, a system perspective.
-
31)
-
J.H. Guo ,
C.L. Wang
.
Digit-serial systolic multiplier for finite fields GF(2m).
IEE Proc., Comput. Digit. Tech.
,
2 ,
143 -
148
-
32)
-
S.Y. Kung
.
(1988)
VLSI array processors.
-
33)
-
C.H. Kim ,
C.P. Hong ,
S. Kwon
.
A digit-serial multiplier for finite field GF(2m).
IEEE Trans. VLSI
,
4 ,
476 -
483
-
34)
-
C.W. Chiou ,
C.Y. Lee ,
A.W. Deng ,
J.M. Lin
.
Efficient VLSI implementation for Montgomery multiplication in GF(2m).
Tamkang J. Sci. Eng.
,
4 ,
365 -
372
-
35)
-
M74HC257, Quad 2 Channel Multiplexer (3-State), STMicroelectronics 2001http://www.st.com/stonline/books/pdf/docs/1932.pdf.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds_20060314
Related content
content/journals/10.1049/iet-cds_20060314
pub_keyword,iet_inspecKeyword,pub_concept
6
6