© The Institution of Engineering and Technology
A high-speed VLSI implementation of a 233-bit serial-in parallel-out finite field multiplier is presented. The proposed design performs multiplication using a reordered normal basis; a permutation of a type II optimal normal basis. The multiplier was realised in a 0.18-µm CMOS technology using multiples of a domino logic block. The multiplier was simulated, and functioned correctly up to a clock rate of 1.587 GHz, achieving greater performance while occupying less area compared to similar designs. The presented design methodology can also be used for other finite field multipliers possessing regular architectures. This multiplier's size of 233 bits is currently recommended by the National Institute of Standards and Technology (NIST) in their elliptic curve digital signature standard (ECDSS), and is used in practice for binary field multiplication in Elliptic Curve Cryptography (ECC).
References
-
-
1)
-
S. Gao ,
S. Vanstone
.
On order of optimal normal basis generators.
Math. Comp.
,
2 ,
1227 -
1233
-
2)
-
G. Agnew ,
R. Mullin ,
I. Onyszchuk ,
S. Vanstone
.
An implementation of elliptic curve cryptosystems over F2155.
IEEE J. Sel. Areas Comm.
,
804 -
813
-
3)
-
Okada, S., Torii, N., Itoh, K., Takenaka, M.: `Implementation of elliptic curve cryptographic coprocessor over ', Proc. Cryptographic Hardware and Embedded Systems (CHES2000), August 2000, p. 25–40.
-
4)
-
Pak-Keung, L., Chiu-Sing, C., Cbeong-Fat, C., Kong-Pang, P.: `A low power asynchronous ', Proc. 2003 Int. Symp. Circuits and Systems, May 2003, 5, p. 337–340.
-
5)
-
Ansari, B., Wu, H.: `Efficient finite field processor for GF(2', Fourth Int. Conf. Information Technology (ITNG), April 2007, p. 1021–1026.
-
6)
-
IEEE: ‘IEEE 1363-2000: standard specifications for public-key cryptography’, August 2002, pp. 1–227.
-
7)
-
Virtual Silicon Technology, Standard Cell Library, 0.18 µm TSMC CMOS process, available through Canadian Microelectronics Corporation, September 1999.
-
8)
-
A.H. Namin ,
H. Wu ,
M. Ahmadi
.
A new finite field multiplier using redundant representation.
IEEE Trans. Comput.
,
5 ,
716 -
720
-
9)
-
Tang, W., Wu, H., Ahmadi, M.: `VLSI implementation of bit-parallel word-serial multiplier in ', Proc. Third Int. IEEE-NEWCAS Conf., June 2005, p. 399–402.
-
10)
-
Gao, S., Sobelman, G.E.: `Improved VLSI designs for multiplication and inversion in ', Proc. 13th Ann. IEEE Int'l ASIC/SOC Conf., 2000, p. 97–101.
-
11)
-
R.C. Mullin ,
I.H. Onyszchuk ,
S.A. Vanstone ,
R.M. Wilson
.
Optimal normal bases in GF(pn).
Discrete Appl. Math.
,
149 -
161
-
12)
-
R. Lidl ,
H. Niederreiter
.
(1994)
Introduction to finite fields and their applications.
-
13)
-
E.R. Berlekamp
.
Bit-serial Reed-Solomon encoders.
IEEE Trans. Inform. Theory
,
6 ,
869 -
874
-
14)
-
G.B. Agnew ,
R.C. Mullin ,
I.M. Onyszchuck ,
S.A. Vanstone
.
An implementation for a fast public-key cryptosystem.
J. Cryptol.
,
63 -
79
-
15)
-
S. Gao ,
J. von zur Gathen ,
D. Panario ,
V. Shoup
.
Algorithms for exponentiation in finite fields.
J. Symb. Comput.
,
879 -
889
-
16)
-
J.P. Uyemura
.
(1999)
CMOS logic circuit design.
-
17)
-
A.J. Menezes ,
P.C. Van Oorschot ,
S.A. Vanstone
.
(1997)
Handbook of applied cryptography.
-
18)
-
M.A. Hasan ,
V.K. Bhargava
.
Division and bit-serial multiplication over GF(2m).
IEE Proc. Comput. Digit. Tech.
,
3 ,
230 -
236
-
19)
-
A. Satoh ,
K. Takano
.
A scalable dual-field elliptic curve cryptographic processor.
IEEE Trans. Comput.
,
4 ,
449 -
460
-
20)
-
H. Wu ,
M.A. Hasan ,
I.F. Blake ,
S. Gao
.
Finite field multiplier using redundant representation.
IEEE Trans. Comput.
,
11 ,
1306 -
1316
-
21)
-
R. Lidl ,
H. Niederreiter
.
(1983)
Finite files.
-
22)
-
A. Reyhani-Masoleh ,
M.A. Hasan
.
Efficient digit-serial normal basis multipliers over GF(2m).
IEEE Trans. Comput.
,
4 ,
428 -
439
-
23)
-
Namin, A.H., Wu, H., Ahmadi, M.: `A bit-serial word-parallel finite field multiplier using redundant basis in ', IASTED Int. Conf. Communication Systems and Networks (AsiaCSN'07), April 2007, p. 171–176.
-
24)
-
T. Itoh ,
S. Tsujii
.
A fast algorithm for computing multiplicative inversie in GF(2m) using normal bases.
Inform. Comput.
,
171 -
177
-
25)
-
Srivastava, P., Pua, A., Welch, L.: `Issues in the design of domino logic circuits', Proc. Eighth Great Lakes Symp. on VLSI, February 1998, p. 108–112.
-
26)
-
Certicom Corp.: ‘Current public-key cryptographic systems’, White paper, http://www.certicom.com (2000).
-
27)
-
Geiselmann, W., Gollmann, D.: `Symmetry and duality in normal basis multiplication', Proc. Applied Algebra, Algebraic Algorithms, and Error Correcting Codes Symp., July 1998, p. 230–238.
-
28)
-
M. Feng
.
A VLSI architecture for fast inversion in GF(2m).
IEEE Trans. Comput.
,
10 ,
1383 -
1386
-
29)
-
D. Hankerson ,
A. Menezes ,
S. Vanstone
.
(2004)
Guide to elliptic curve cryptography.
-
30)
-
A. Reyhani-Masoleh ,
M.A. Hasan
.
Low complexity word-level sequential normal basis multipliers.
IEEE Trans. Comput.
,
2 ,
98 -
110
-
31)
-
(2001)
Federal Information Processing Standard Publication (FIPS Pub 186-3) Digital signature standards.
-
32)
-
Massey, J.L., Omura, J.K.: `Computational method and apparatus for finite field arithmetic', , 1984, US patent application.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds.2008.0331
Related content
content/journals/10.1049/iet-cds.2008.0331
pub_keyword,iet_inspecKeyword,pub_concept
6
6