Low Complexity GF(2^m) Multiplier Based on Iterative Karatsuba Algorithm

Abstract:

The complexity is one important index for Galois Field multiplier. This paper presents one low complexity GF(2^m) multiplier based on iterative Karatsuba algorithm. The multiplication is replaced iteratively by three ones of half-length operands which are performed in parallel. The operands are divided into different width such as 64-bit, 32-bit, 16-bit and so on. For the 2^m*2^m multiplier, we take 128 bit-widthGF(2¹²⁸) multipliers as an example. We implement them on FPGA and count the number of the used LUTs and the used registers. Through analyzing the statistic, we find that, when the width of the two multiplication operands is divided to 8 bit, the multiplier consumes the least resources. Compared with the FPGA implementation of the other previous multiplier, this optimum multiplier can save 50% resources in LUTs and the registers.

• Periodical: Advanced Materials Research (Volumes 546-547)
• Pages: 1409-1414
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.546-547.1409
• Online since: July 2012
• Authors: Yu Long Zhang, Guo Chu Shou, Yi Hong Hu, Zhi Gang Guo
• Keywords: Complexity, Field-Programmable Gate Array (FPGA), Galois Field GF(2^m), Iterative Karatsuba Algorithm, Karatsuba Algorithm, Multiplier

References

[1] Vanstone, S.A., and Oorschot, P.C.: An introduction to error correcting codes with applications, (Kluwer, 1989).

[2] I.S. Reed and X. Chen, Error-Control Coding for Data Networks. Kluwer Academic, (1999).

[3] Z. Dyka, P. Langendoerfer, Area efficient hardware implementation of elliptic curve cryptography by iteratively applying karatsuba's method", Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE, 05), Compute Society pages 70–75, (2005).

DOI: 10.1109/date.2005.67

[4] M. Machhout, M. Zeghid, Efficient Large Numbers Karatsuba-Offman Multiplier Designs for Embedded Systems,. International Journal of Electronics, Circuits and Systems, (2009).

[5] Yan Bai, Guochu Shou, Yihong Hu, Zhigang Guo， High Performance Pipelined Architecture of GHASH, , 2010 IEEE International Conference on Broadband Network & Multimedia Technology.

DOI: 10.1109/icbnmt.2010.5705183

[6] H. Fan, J. Sun, M. Gu, K. -Y. Lam, Overlap-free Karatsuba-Ofman polynomial multiplication algorithms,. IET information security. doi: 10. 1049/iet-ifs. (2009).

DOI: 10.1049/iet-ifs.2009.0039

[7] Jimei Wang, Guochu Shou, Yihong Hu, Zhigang Guo , High-speed architectures for GHASH based on efficient bit-parallel multipliers, , IEEE WCNIS2010.

DOI: 10.1109/wcins.2010.5541846

[8] National David McGrew, John Vi ega, The Galois/Counter Mode of Operation (GCM), Updated submission to NIST Modes of Operation Process, May (2005).

[9] Gang Zhou; Michalik, H; Hinsenkamp, L; Complexity Analysis and Efficient Implementations of Bit Parallel Finite Field Multipliers Based on Karatsuba-Ofman Algorithm on FPGAs,. Very Large Scale Integration (VLSI) Systems, IEEE Transcations; July (2010).

DOI: 10.1109/tvlsi.2009.2020088

[10] A. Satoh, T. Sugawara, T. Aoki; High-Performance Hardware Architectures for Galois Counter Mode", IEEE Transactions on Computers, v 58, n 7, pp.917-930, (2009).

DOI: 10.1109/tc.2008.217

[11] Jia Huo, Guochu Shou, Yihong Hu, Zhigang Guo, The design and FPGA implementation of GF (2128) multiplier for GHASH,. Proceedings-International Conference on Networks Security, Wireless Communication and Trusted Computing, NSWCTC 2009, v 1, pp.554-557.

DOI: 10.1109/nswctc.2009.96

[12] G. Shou, Z. Mao, Y. Hu, Z. Guo and Z. Qian. Low complexity architecture of bit parallel multipliers for GF(2m),. Electronics Letters, Sep. 2010, vol. 46, no. 19, pp.1326-1327.

DOI: 10.1049/el.2010.1710