Sequential Type-I Optimal Normal Basis Multiplier and Multiplicative Inverse in GF(2m)

Che Wun Chiou; Chiou-Yng Lee; Yun-Chi Yeh

doi:10.6180/jase.2010.13.4.08

Sequential Type-I Optimal Normal Basis Multiplier and Multiplicative Inverse in GF(2m)

Computer Science and Information Engineering

Che Wun Chiou This email address is being protected from spambots. You need JavaScript enabled to view it.¹, Chiou-Yng Lee² and Yun-Chi Yeh³

¹Department of Computer Science and Information Engineering, Ching Yun University, Chung-Li, Taiwan 320, R.O.C.
²Department of Computer Information and Network Engineering, Lunghwa University of Science and Technology, Taoyuan, Taiwan 333, R.O.C.
³Department of Electronic Engineering, Ching Yun University, Chung-Li, Taiwan 320, R.O.C.

Received: February 27, 2008
Accepted: June 11, 2009
Publication Date: December 1, 2010

Download Citation: ||https://doi.org/10.6180/jase.2010.13.4.08

ABSTRACT

This study presents a novel sequential Type-I optimal normal basis multiplier in GF(2^m) with a regular structure. The proposed multiplier has a slightly higher space complexity than the Reyhani-Masoleh-Hasan’s (RMH) multiplier, but is 27% faster than the RMH multiplier. Furthermore, the proposed multiplier is highly regular, modular, expandable and well-suited to VLSI implementation. A new normal basis inverter based on the proposed multiplier is also invented. The proposed inverter provides better time-area complexity than existing inverters as with large m.

Keywords: Cryptography, Finite Field, Multiplication, Normal Basis, Multiplicative Inverse, VLSI

REFERENCES

[1] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Amsterdam: North-Holland, 1977.
[2] R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, New York: Cambridge Univ. Press, 1994.
[3] R. E. Blahut, Fast algorithms for digital signal processing, Reading, Mass.: Addison-Wesley, 1985.
[4] I. S. Reed and T. K. Truong, The use of finite fields to compute convolutions, IEEE Trans. Information Theory, Vol.IT-21, No.2, pp.208-213, March 1975.
[5] B. Benjauthrit and I. S. Reed, “Galois switching functions and their applications,” IEEE Trans. Computers, Vol. C-25, pp.78-86, Jan. 1976.
[6] C. C. Wang and D. Pei, “A VLSI design for computing exponentiation in GF(2^m) and its application to generate pseudorandom number sequences,” IEEE Trans. Computers, Vol.39, No.2, pp.258-262, Feb.1990.
[7] T. C. Bartee and D. J. Schneider, “Computation with finite fields,” Information and Computing, Vol.6, pp.79-98, Mar. 1963.
[8] E. D. Mastrovito, “VLSI architectures for multiplication over finite field GF(2^m),” Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, Proc. Sixth Int’l Conf., AAECC-6, T. Mora, ed., Rome, pp.297-309, July 1988.
[9] E. D. Mastrovito, “VLSI architectures for computations in Galois fields,” PhD thesis, Linköping Univ., Dept. of Electrical Eng., Linköping, Sweden, 1991.
[10] Ç. K. Koç and B. Sunar, “Low-complexity bit-parallel canonical and normal basis multipliers for a class of finite fields,” IEEE Trans. Computers, Vol.47, No.3, pp.353-356, March 1998.
[11] C. Y. Lee, “Low complexity bit-parallel systolic multiplier over GF(2^m) using irreducible trinomials,” IEE Proc.-Comput. Digit. Tech., Vol.150, No.1, pp.39-42, Jan. 2003.
[12] T. Itoh and S. Tsujii, “Structure of parallel multipliers for a class of fields GF(2^m)”, Information and Computation, Vol. 83, pp.21-40, 1989.
[13] M. A. Hasan, M. Wang, V. K. Bhargava, “Modular construction of low complexity parallel multipliers for a class of finite fields GF(2^m),” IEEE Trans. Computers, Vol.41, No.8, pp.962-971, August 1992.
[14] C. Y. Lee, E. H. Lu, and J. Y. Lee, “Bit-parallel systolic multipliers for GF(2^m) fields defined by all-one and equally-spaced polynomials,” IEEE Trans. Computers, Vol.50, No.5, pp.385-393, May 2001.
[15] C. Paar, “A new architecture for a parallel finite field multiplier with low complexity based on composite fields,” IEEE Trans. Computers, Vol.45, No.7, pp.856-861, July 1996.
[16] C. Paar, P. Fleischmann, and P. Roelse, “Efficient multiplier architectures for Galois Fields GF(2⁴ⁿ)”, IEEE Trans. Computers, Vol.47, No.2, pp.162-170, Feb. 1998.
[17] C.W. Chiou, L.C. Lin, F.H. Chou, and S.F. Shu, “Low complexity finite field multiplier using irreducible trinomials,” IEE Electronics Letters, Vol.39, No.24, pp. 1709-1711, Nov. 2003.
[18] P. Kitsos, G. Theodoridis, and O. Koufopavlou, “An efficient reconfigurable multiplier architecture for Galois field GF(2^m),” Microelectronics Journal, Vol.34, No.10, pp.975-980, Oct. 2003.
[19] E. R. Berlekamp, “Bit-serial Reed-Solomon encoders”, IEEE Trans. Information Theory, Vol.IT-28, pp.869-874, 1982.
[20] H. Wu, M. A. Hasan, and I. F. Blake, “New low-complexity bit-parallel finite field multipliers using weakly dual bases,” IEEE Trans. Computers, Vol.47, No.11, pp.1223-1234, November 1998.
[21] H. Wu and M. A. Hasan, “Low complexity bit-parallel multipliers for a class of finite fields,” IEEE Trans. Computers, Vol.47, No.8, pp.883-887, Aug. 1998.
[22] C.Y. Lee and C.W. Chiou, J.M. Lin, “Low-Complexity Bit-Parallel Dual Basis Multipliers Using the Modified Booth’s Algorithm,” Computers & Electrical Engineering, Vol.31, No.7, pp.444-459, Oct. 2005.
[23] J. L. Massey and J. K. Omura, “Computational method and apparatus for finite field arithmetic,” U.S. Patent Number 4,587,627, May 1986.
[24] C. C. Wang, T. K. Truong, H. M. Shao, L. J. Deutsch, J. K. Omura, , and I. S. Reed, “VLSI architectures for computing multiplications and inverses in GF(2^m),” IEEE Trans. Computers, Vol.C-34, No.8, pp.709-717, Aug. 1985.
[25] A. Reyhani-Masoleh and M. A. Hasan, “A new construction of Massey-Omura parallel multiplier over GF(2^m)”, IEEE Trans. Computers, Vol.51, No.5, pp.511-520, May 2002.
[26] A. Reyhani-Masoleh and M. A. Hasan, “Low complexity sequential normal basis multipliers over GF(2^m),” Proc. 16^th IEEE Symposium on Computer Arithmetic, Vol.16, pp.188-195, 2003.
[27] A. Reyhani-Masoleh and M.A. Hasan, “Fast normal basis multiplication using general purpose processors,” IEEE Trans. Computers, Vol.52, No.11, pp.1379-1390, Nov. 2003.
[28] A. Reyhani-Masoleh, “Efficient algorithms and architectures for field multiplication using Gaussian normal bases,” IEEE Trans. Computers, Vol.55, No.1, pp.34-47, Jan. 2006.
[29] A. Reyhani-Masoleh and M. A. Hasan, “Low complexity word-level sequential normal basis multipliers,” IEEE Trans. Computers, Vol.54, No.2, pp.98-110, Feb. 2005.
[30] G.B. Agnew, R.C. Mullin, I.M. Onyszchuk, and S.A. Vanstone, “An implementation for a fast public-key cryptosystem,” Journal of Cryptology, Vol.3, pp.63-79, 1991.
[31] C.Y. Lee and C.W. Chiou, “Efficient Design of Low-Complexity Bit-Parallel Systolic Hankel Multipliers To Implement multiplication in Normal and Dual Bases of GF(2^m),” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science, Vol.E88-A, No.11, pp.3169-3179, Nov. 2005.
[32] C.W. Chiou and C.Y. Lee, “Multiplexer-Based Double-Exponentiation for Normal Basis of GF (2^m),” Computers & Security, Vol.24, No.1, pp.83-86, 2005.
[33] M.A. Hasan, M.Z. Wang, and V.K. Bhargava, “A modified Massey-Omura parallel multiplier for a class of finite fields,” IEEE Trans. Computers, Vol.42, No.10, pp.1278-1280, Oct. 1993.
[34] Applications of Finite Fields, A. J. Menezes, ed., Boston: Kluwer Academic, 1993.
[35] R.J. Baker, H.W. Li, and D.E. Boyce, CMOS-Circuit, Design, Layout, and Simulation, IEEE Press, New York, 1998.
[36] S.M. Kang and Y. Leblebici, CMOS Digital Integrated Circuits-Analysis and Design, McGraw-Hill, 1999.
[37] http://www.st.com/stonline/books/pdf/docs/2006.pdf
[38] http://www.st.com/stonline/books/pdf/docs/1885.pdf
[39] http://www.st.com/stonline/products/literature/ds/1937/m74hc279.pdf
[40] A. Menezes, P. C. Van Oorschot, and S. A. Vanstone, Handbook of applied cryptology, CRC Press, New York, 1997.
[41] Y.T. Horng and S.W. Wei, “Fast inverters and dividers for finite field GF(2^m),” Proc. of 1994 IEE Asia-Pacific Conference on Circuits and Systems, Taiwan, pp.206-211, 5-8 Dec. 1994.