Efficient Semi-Systolic Finite Field Multiplier Using Redundant Basis

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.

Authors:

• Hyun-Ho Lee
• Kee-Won Kim

Keywords:

• Finite field
• Montgomery multiplication
• systolic array
• cryptography.

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.