access icon free High-performance and high-speed implementation of polynomial basis Itoh–Tsujii inversion algorithm over GF(2 m )

© The Institution of Engineering and Technology
Received 19/10/2015, Accepted 27/04/2016, Revised 05/04/2016, Published 01/03/2017

In this study high-performance and high-speed field-programmable gate array (FPGA) implementations of polynomial basis Itoh–Tsujii inversion algorithm (ITA) over GF(2 m ) constructed by irreducible trinomials and pentanomials are presented. The proposed structures are designed by one field multiplier and k -times squarer blocks or exponentiation by 2 k , where k is a small positive integer. The k -times squarer blocks have an efficient tree structure with low critical path delay, and the multiplier is based on a proposed high-speed digit-serial architecture with minimum hardware resources. Furthermore, to reduce the computation time of ITA, the critical path of the circuit is broken to finer path using several registers. The computation times of the structure on Virtex-4 FPGA family are 0.262, 0.192 and 0.271 µs for GF(2163), GF(2193) and GF(2233), respectively. The comparison results with other implementations of the polynomial basis Itoh–Tsujii inversion algorithm verify the improvement in the proposed architecture in terms of speed and performance.

Inspec keywords: trees (mathematics); flip-flops; logic design; field programmable gate arrays; polynomials; multiplying circuits

Other keywords: Virtex-4 FPGA family; hardware resources; tree structure; digit-serial architecture; polynomial basis Itoh-Tsujii inversion algorithm; path delay; pentanomials; ITA; field multiplier; k-times squarer blocks; field-programmable gate array; registers; irreducible trinomials

Subjects: Combinatorial mathematics; Digital circuit design, modelling and testing; Logic circuits; Algebra; Combinatorial mathematics; Logic and switching circuits; Logic design methods; Algebra

References

    1. 1)
      • 16. Deschamps, J.P., Imaña, J.L., Sutter, G.D.: ‘Hardware implementation of finite-field arithmetic’ (McGraw-Hill, New York, 2009, 1st edn.).
    2. 2)
      • 32. Rebeiro, C., Mukhopadhyay, D.: ‘Power attack resistant efficient FPGA architecture for Karatsuba multiplier’. Proc. of the 21st Int. Conf. on VLSI Design, IEEE Computer Society, Washington, DC, USA, 2008, pp. 706–711.
    3. 3)
      • 11. Knuth, D.E.: ‘The art of computer programming’ (Addison-Wesley, Reading, MA, 1997, 3rd edn.).
    4. 4)
      • 31. Rodriguez-Henriquez, F., Saqib, N.A., Diaz-Perez, A.: ‘A fast parallel implementation of elliptic curve point multiplication over GF(2m)’, Microprocess. Microsyst., 2004, 28, (5–6), pp. 329–339.
    5. 5)
      • 22. Fan, J., Verbauwhede, I.: ‘A digit-serial architecture for inversion and multiplication in GF(2m)’. Proc. of the IEEE Workshop on Signal Processing Systems, 8–10 October 2008, Washington, DC, pp. 7–12.
    6. 6)
      • 15. Rodriguez-Henriquez, F., Saqib, N.A., Diaz-Perez, A., et al: ‘Cryptographic algorithms on reconfigurable hardware’ (Springer, New York, 2006, 1st edn.).
    7. 7)
      • 17. Cohen, H., Frey, G., Avanzi, R., et al: ‘Handbook of elliptic and hyperelliptic curve cryptography’ (CRC Press, Boca Raton, 2006, 1st edn.).
    8. 8)
      • 6. Venkatasubramani, V.R., Murali, N., Rajaram, S.: ‘An improved quad Itoh-Tsujii algorithm for FPGAs’, IEICE Electron. Express, 2013, 10, (18), pp. 1–6.
    9. 9)
      • 9. Parrilla, L., Lloris, A., Castillo, E., et al: ‘Minimum-clock-cycle Itoh-Tsujii algorithm hardware implementation for cryptography applications over GF(2m) fields’, Electron. Lett., 2012, 48, (18), pp. 1126–1128.
    10. 10)
      • 8. Sinha Roy, S., Rebeiro, C., Mukhopadhyay, D.: ‘Generalized high speed Itoh-Tsujii multiplicative inversion architecture for FPGAs’, Integr. VLSI J., 2012, 45, (3), pp. 307–315.
    11. 11)
      • 10. Brauer, A.: ‘on addition chains’, Bull. Amer. Math. Soc., 1939, 45, (10), pp. 736–739.
    12. 12)
      • 20. Bosma, W., Cannon, J., Playoust, C.: ‘The magma algebra system I: The user language’, J. Symb. Comput., 1997, 24, pp. 235–265.
    13. 13)
      • 19. Wu, H.: ‘Low complexity bit-parallel finite field arithmetic using polynomial basis’. Proc. of Cryptographic Hardware and Embedded Systems-CHES 1999, (LNCS 1717), pp. 280–291.
    14. 14)
      • 5. Sinha Roy, S., Rebeiro, C., Mukhopadhyay, D.: ‘Accelerating Itoh-Tsujii multiplicative inversion algorithmfor FPGAs’. Proc. of the 21st edition of the Great Lakes Symp. on Great Lakes Symp. on VLSI, 2011, pp. 67–72.
    15. 15)
      • 13. Guajardo, J., Paar, C.: ‘Itoh-Tsujii inversion in standard basis andits application in cryptography and codes’, Des. Codes Cryptogr., 2002, 25, (2), pp. 207–216.
    16. 16)
      • 33. Rebeiro, C., Mukhopadhyay, D.: ‘Hybrid masked Karatsuba multiplier for GF(2233)’. Proc. of the 11th IEEE VLSI Design and Test Symp., Calcutta, India, August 8–11, 2007, pp. 379–387.
    17. 17)
      • 29. Morales-Sandoval, M., Feregrino-Uribe, C., Kitsos, P.: ‘Bit-serial and digit-serial GF(2m) Montgomery multipliers using linear feedback shift registers’, IET Comput. Digit. Tech., 2011, 5, (2), pp. 86–94.
    18. 18)
      • 23. Pan, J.S., Lee, C.Y., Kumar Meher, P.: ‘Low-latency digit-serial and digit-parallel systolic multipliers for large binary extension fields’, IEEE Trans. Circuits Syst. I Reg. Pap., 2013, 60, (12), pp. 3195–3204.
    19. 19)
      • 3. Rodrıiguez-Henrıiquez, F., Morales-Luna, G., Saqib, N.A., et al: ‘Parallel Itoh-Tsujii multiplicative inversion algorithm for a special class of trinomials’, Des. Codes Cryptogr., 2007, 45, (1), pp. 19–37.
    20. 20)
      • 18. Xiong, X., Fan, H.: ‘GF(2m) bit-parallel squarer using generalized polynomial basis for new class of irreducible pentanomials’, Electron. Lett., 2014, 50, (9), pp. 655–657.
    21. 21)
      • 28. Kim, C.H., Hong, C.P., Kwon, S.: ‘A digit-serial multiplier for finite field GF(2m)’, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2005, 13, (4), pp. 476–483.
    22. 22)
      • 2. Rodrıiguez-Henrıiquez, F., Saqib, N.A., Cruz-Cortes, N.: ‘A fast implementation of multiplicative inversion over GF (2m)’. Proc. of the Int. Conf. on Information Technology: Coding and Computing (ITCC05), 2005, vol. 1, pp. 574–579.
    23. 23)
      • 12. Kodali, R.K., Amanchi, C.N., Kumar, S., et al: ‘FPGA implementation of Itoh-Tsujii inversion algorithm’. Proc. of the IEEE Int. Conf. on Recent Advances and Innovations in Engineering (ICRAIE-2014), May 09–11, 2014, Jaipur, India, pp. 1–5.
    24. 24)
      • 26. Lee, T.-Y., Liu, M.-J., Fan, C.-C., et al: ‘Low complexity digit-serial multiplier over GF(2m) using Karatsuba technology’. Seventh Int. Conf. on Complex, Intelligent, and Software Intensive Systems, 2013, pp. 461–466.
    25. 25)
      • 24. Kim, C.H., Kwon, S., Hong, C.P.: ‘A fast digit-serial systolic multiplier for finite field GF(2m)’. Proc. of the IEEE Conf. Destin Automation Conf. Asia and south pacific, ASP-DAC, 2005, vol. 2, pp. 1268–1271.
    26. 26)
      • 21. Jia-feng, X., Jian-jun, H., Wei-hua, G.: ‘Low latency systolic multipliers for finite field GF(2m) based on irreducible polynomials’ (Central South University Press, Springer-Verlag Berlin Heidelberg, 2012), pp. 1283–1289.
    27. 27)
      • 27. Kumar, S., Wollinger, T., Paar, C.: ‘Optimum digit serial GF(2m) multipliers for curve-based cryptography’, IEEE Trans. Comput., 2006, 55, (10), pp. 1306–1311.
    28. 28)
      • 4. Rebeiro, C., Sinha Roy, S., Mukhopadhyay, D.: ‘Revisiting the Itoh-Tsujii inversion algorithm for FPGA platforms’, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2011, 19, (8), pp. 1508–1512.
    29. 29)
      • 25. Kim, C.H., Han, S.D., Hong, C.P.: ‘Digit-serial systolic multiplier for finite field GF(2m)’. IEE Proc. on 14th Annual IEEE Int. Conf. of ASIC/SOC, 2001, pp. 361–365.
    30. 30)
      • 14. Hankerson, D., Menezes, A., Vanstone, S.: ‘Guide to elliptic curve cryptography’ (Springer, New York, 2003, 1st edn.).
    31. 31)
      • 1. Itoh, T., Tsujii, S.: ‘A fast algorithm for computing multiplicative inverses in GF(2m) using normal bases’, Inf. Comput., 1988, 78, (3), pp. 171–177.
    32. 32)
      • 7. Sinha Roy, S., Rebeiro, C., Mukhopadhyay, D.: ‘Theoretical modeling of the Itoh-Tsujii inversion algorithm for enhanced performance on k-LUT based FPGAs’. Proc. of the IEEE Conf. Design, Automation and Test (DATE), 14–18 March 2011, pp. 1–6.
    33. 33)
      • 30. Rodriguez-Henriquez, F., Koc, C.K.: ‘On fully parallel karatsuba multipliers for GF(2m)’. Proc. of the Int. Conf. on Computer Science and Technology (CST), Cancun, Mexico, 2003, pp. 405–410.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2015.0461
Loading

Related content

content/journals/10.1049/iet-ifs.2015.0461
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading