Efficient Semi-Systolic Finite Field Multiplier Using Redundant Basis

Authors: Hyun-Ho Lee, Kee-Won Kim

Abstract:

The arithmetic operations over GF(2m) have been extensively used in error correcting codes and public-key cryptography schemes. Finite field arithmetic includes addition, multiplication, division and inversion operations. Addition is very simple and can be implemented with an extremely simple circuit. The other operations are much more complex. The multiplication is the most important for cryptosystems, such as the elliptic curve cryptosystem, since computing exponentiation, division, and computing multiplicative inverse can be performed by computing multiplication iteratively. In this paper, we present a parallel computation algorithm that operates Montgomery multiplication over finite field using redundant basis. Also, based on the multiplication algorithm, we present an efficient semi-systolic multiplier over finite field. The multiplier has less space and time complexities compared to related multipliers. As compared to the corresponding existing structures, the multiplier saves at least 5% area, 50% time, and 53% area-time (AT) complexity. Accordingly, it is well suited for VLSI implementation and can be easily applied as a basic component for computing complex operations over finite field, such as inversion and division operation.

Keywords: Finite field, Montgomery multiplication, systolic array, cryptography.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1126730

References:

[1] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography, Boca Raton, FL, CRC Press, 1996.
[2] R. E. Blahut, Theory and Practice of Error Control Codes, Reading, MA, Addison-Wesley, 1983.
[3] N. Kobliz, “Elliptic Curve Cryptography,” Math. Computation, vol. 48, no. 177, pp. 203-209, Jan. 1987.
[4] P. Montgomery, “Modular multiplication without trial division,” Math. Comput., vol. 44, no. 170, pp. 519-521, Apr. 1985.
[5] C. Koc, and T. Acar, “Montgomery multiplication in GF(2k),” Des. Codes Cryptogr., vol. 14, no. 1, pp. 57-69, Apr. 1998.
[6] C. Y. Lee, J. S. Horng, and I. C. Jou, “Low-complexity bit-parallel systolic Montgomery multipliers for special classes of GF(2m),” IEEE Trans. Comput., vol. 54, no. 9, pp. 1061-1070, Sep. 2005.
[7] A. Hariri and A. Reyhani-Masoleh, “Bit-serial and bit-parallel Montgomery multiplication and squaring over GF(2m),” IEEE Trans. Comput., vol. 58, no. 10, pp. 1332-45, Oct. 2009.
[8] A. Hariri and A. Reyhani-Masoleh, “Concurrent error detection in Montgomery multiplication over binary extension fields,” IEEE Trans. Comput., vol. 60, no. 9, pp. 1341-53, Sep. 2011.
[9] K. W. Kim and W. J. Lee, “Efficient cellular automata based Montgomery AB2 multipliers over GF(2m),” IETE Technical Review, vol. 31, no. 1, pp. 92-102, May 2014.
[10] K. W. Kim and J. C. Jeon, “Polynomial basis multiplier using cellular systolic architecture,” IETE Journal of Research, vol. 60, no. 2, pp. 194-199, Jun. 2014.
[11] S. H. Choi and K. J. Lee, “Low complexity semisystolic multiplication architecture over GF(2m),” IEICE Electron. Express, vol. 11, no. 20, pp. 20140713, Oct. 2014.
[12] K. W. Kim and J. C. Jeon, “A semi-systolic Montgomery multiplier over GF(2m),” IEICE Electonics Express, vol. 12, no. 21, pp. 20150769, Nov. 2015.
[13] C. W. Chiou, C. Y. Lee, A. W. Deng, and J. M. Lin, “Concurrent error detection in Montgomery multiplication over GF(2m),” IEICE Trans. Fund. Electron. Commun. Comput. Sci., vol. E89-A, no. 2, pp. 566-574, Feb. 2006.
[14] W.T. Huang, C.H. Chang, C.W. Chiou and F.H. Chou, “Concurrent error detection and correction in a polynomial basis multiplier over GF(2m),” IET Inf. Secur., vol. 4, no. 3, p. 111-124, Sep. 2010.
[15] K. W. Kim and S. H. Kim, “A low latency semi-systolic multiplier over GF(2m),” IEICE Electron. Express, vol. 10, no. 13, pp. 20130354, July 2013.
[16] C. Y. Lee, C. W. Chiou and J. M. Lin, “Concurrent error detection in a polynomial basis multiplier over GF(2m),” J. Electron. Test., vol. 22, no. 2, pp. 143-150, Apr. 2006.
[17] R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications. Cambridge Univ. Press, 1986.
[18] H. Wu, M.A. Hasan, I.F. Blake and S. Gao, “Finite field multiplier using redundant representation,” IEEE Trans. Comput. Vol.51, No.11, pp.1306-1316, 2002.
[19] A. H. Namin, H. Wu and M. Ahmadi, “A New Finite Field Multiplier Using Redundant Representation”, IEEE Trans. Computers, Vol.57, No.5, pp. 716-720, May 2008.