Journal of Zhejiang University SCIENCE A
ISSN 1673-565X(Print), 1862-1775(Online), Monthly

2009   Vol. 10   No. 6   p. 834~842

Low-complexity multiplexer-based normal basis multiplier over GF(2^m)

Jenn-Shyong HORNG^†1, I-Chang JOU¹, Chiou-Yng LEE²

(¹Institute of Engineering Science and Technology, National Kaohsiung First University of Science and Technology, Taiwan 811, Kaohsiung County)
(²Department of Computer Information and Network Engineering, Lunghwa University of Science and Technology, Taiwan 333, Taoyuan County)
^†E-mail: shyong1@cht.com.tw
Received May 26, 2008; revision accepted Nov. 18, 2008; Crosschecked Apr. 29, 2009

Abstract: We present a new normal basis multiplication scheme using a multiplexer-based algorithm. In this algorithm, the proposed multiplier processes in parallel and has a multiplexer-based structure that uses MUX and XOR gates instead of AND and XOR gates. We show that our multiplier for type-1 and type-2 normal bases saves about 8% and 16%, respectively, in space complexity as compared to existing normal basis multipliers. Finally, the proposed architecture has regular and modular configurations and is well suited to VLSI implementations.

Key words: Finite field multiplication, Normal basis, Gaussian normal basis, Elliptic curve cryptosystem
doi:10.1631/jzus.A0820398             CLC number: TP309

References:

[1] Agnew, G.B., Mullin, R.C., Onyszchuk, I.M., Vanstone, S.A., 1991. An implementation for a fast public-key cryptosystem. J. Cryptol., 3:63-79.

[2] Ash, D.W., Blake, I.F., Vanstone, S.A., 1989. Low complexity normal basis. Discr. Appl. Math., 25(3):191-210.

[3] Byun, G.Y., Kim, H.S., 2003. Low-complexity multiplexer-based multiplier of GF(2^m). IEICE Trans. Inf. Syst., E86-D(12):2684-2690.

[4] Elia, M., Leone, M., 2002. On the inherence space complexity of fast parallel multipliers for GF(2^m). IEEE Trans. Comput., 51(3):346-351.

[5] Hasan, M.A., Wang, M., Bhargava, V.K., 1992. Modular construction of low complexity parallel multipliers for a class of finite fields GF(2^m). IEEE Trans. Comput., 41(8): 962-971.

[6] Hasan, M.A., Wang, M.Z., Bhargava, V.K., 1993. A modified Massey-Omura parallel multiplier for a class of finite fields. IEEE Trans. Comput., 42(10):1278-1280.

[7] IEEE Std. 1363, 2000. IEEE Standard Specifications for Public Key Cryptography. IEEE-SA Standards Board, IEEE/IEE Electronic Library.

[8] Kim, C.H., Kim, Y., Ji, S.Y., Park, I.W., 2006. A New Parallel Multiplier for Type II Optimal Normal Basis. Int. Conf. on Computational Intelligence and Security, 2:1315-1318.

[9] Koc, C.K., Sunar, B., 1998. Low-complexity bit-parallel canonical and normal multipliers for a class of finite fields. IEEE Trans. Comput., 47(3):353-356.

[10] Lee, C.Y., Lu, E.H., Lee, J.Y., 2001. Bit-parallel systolic multipliers for GF(2^m) fields defined by all-one and equally-spaced polynomials. IEEE Trans. Comput., 50(5): 385-393.

[11] Lee, C.Y., Chiou, C.W., Lin, J.M., 2005. Low-complexity bit-parallel dual basis multipliers using the modified Booth’s algorithm. Comput. Electr. Eng., 31(7):444-459.

[12] Lee, C.Y., Chiu, Y.H., Chiou, C.W., 2006. New Bit-parallel Systolic Multiplier Over GF(2^m) Using the Modified Booth’s Algorithm. IEEE Asia Pacific Conf. on Circuits and Systems, p.610-613.

[13] Lidl, R., Niederreiter, H., 1994. Introduction to Finite Fields and Their Applications. Cambridge University Press, New York.

[14] MacWilliams, F.J., Sloane, N.J.A., 1977. The Theory of Error-correcting Codes. Amsterdam, North-Holland.

[15] Massey, J.L., Omura, J.K., 1986. Computational Method and Apparatus for Finite Field Arithmetic. US Patent, No. 4 587 627.

[16] Mullin, R.C., Onyszchuk, I.M., Vanstone, S.A., Wilson, R.M., 1989. Optimal normal basis in GF(pⁿ). Discr. Appl. Math., 22(2):149-161.

[17] Pekmestzi, K.Z., 1999. Multiplexer-based array multipliers. IEEE Trans. Comput., 48(1):15-23.

[18] Reyhani-Masoleh, A., 2006. Efficient algorithms and architectures for field multiplication using Gaussian normal bases. IEEE Trans. Comput., 55(1):34-47.

[19] Reyhani-Masoleh, A., Hasan, M.A., 2002. A new construction of Massey-Omura parallel multiplier over GF(2^m). IEEE Trans. Comput., 51(5):511-520.

[20] Reyhani-Masoleh, A., Hasan, M.A., 2003. Fast normal basis multiplication using general purpose processors. IEEE Trans. Comput., 52(11):1379-1390.

[21] Reyhani-Masoleh, A., Hasan, M.A., 2005. Low complexity word-level sequential normal basis multiplier. IEEE Trans. Comput., 54(2):98-110.

[22] Sunar, B., Koc, C.K., 2001. An efficient optimal normal basis type II multiplier. IEEE Trans. Comput., 50(1):83-88.

[23] Wu, H., 1998. Efficient Computations in Finite Fields with Cryptographic Significance. PhD Thesis, Waterloo University, Ontario.