×

Parallel Itoh-Tsujii multiplicative inversion algorithm for a special class of trinomials. (English) Zbl 1215.11118

Summary: We derive a novel parallel formulation of the standard Itoh-Tsujii algorithm for multiplicative inverse computation over the field \(\text{GF}(2^m)\). The main building blocks used by our algorithm are: field multiplication, field squaring and field square root operators. It achieves its best performance when using a special class of irreducible trinomials, namely, \(P(x) = x^m + x^k + 1\), with \(m\) and \(k\) odd numbers and when implemented in hardware platforms. Under these conditions, our experimental results show that our parallel version of the Itoh-Tsujii algorithm yields a speedup of about 30% when compared with the standard version of it. Implemented in a Virtex 3200E FPGA device, our design is able to compute multiplicative inversion over \(\text{GF}(2^{193})\) after 20 clock cycles in about \(0.94\mu S\).

MSC:

11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11Y16 Number-theoretic algorithms; complexity
05B25 Combinatorial aspects of finite geometries
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Itoh T and Tsujii S (1998). A fast algorithm for computing multiplicative inverses in GF(2 m ) using normal basis. Inf Comput 78: 171–177 · Zbl 0672.68015 · doi:10.1016/0890-5401(88)90024-7
[2] Feng GL (1989). A VLSI architecture for fast inversion in GF(2 m ). IEEE Trans Comput 38(10): 1383–1386 · doi:10.1109/12.35833
[3] Takagi N, Yoshiki J and Tagaki K (2001). A fast algorithm for multiplicative inversion in GF(2 m ) using normal basis. IEEE Trans Comput 50(5): 394–398 · doi:10.1109/12.926155
[4] Hasan MA (2001) Efficient computation of multiplicative inverses for cryptographic applications. In: Proceedings of the 15th IEEE symposium on computer arithmetic, Vail, Colorado, USA
[5] Yen S (1997). Improved normal basis inversion in GF(2 m ). IEE Electron Lett 33(3): 196–197 · doi:10.1049/el:19970172
[6] Gutub AA-A, Tenca AF, Savas E, Koc CK (2002) Scalable and unified hardware to compute montgomery inverse in GF(p) and GF(2 n ). In: Proceedings of the Cryptographic hardware and embedded systems–CHES 2002, 4th international workshop, redwood shores, vol 2523, CA, USA, pp 484–499 · Zbl 1020.94520
[7] Rodríguez-Henríquez F, Saqib NA, Cruz-Cortés N (2005) A fast implementation of multiplicative inversion over GF(2 m ). In: Proceedings of the international symposium on information technology (ITCC 2005), vol 1, Las Vegas, Nevada, USA, pp 574–579
[8] Guajardo J and Paar C (2002). Itoh–tsujii inversion in standard basis and its application in cryptography and codes. Des Codes Cryptogr 25: 207–216 · Zbl 1030.11070 · doi:10.1023/A:1013860532636
[9] Knuth DE (1997). The art of computer programming. Addison-Wesley, Reading, MA · Zbl 0895.68055
[10] Rodríguez-Henríquez F, Morales-Luna G, López-Hernández J (2006) Low complexity bit-parallel square root computation over GF(2 m ) for all trinomials. Cryptology ePrint Archive, Report 2006/133, http://eprint.iacr.org/. · Zbl 1388.65207
[11] Wu H (2000). On complexity of squaring using polynomial basis in GF(2 m ). In: Stinson, STD (eds) Workshop on selected areas in cryptography (SAC 2000), vol LNCS 2012., pp 118–129. Springer, Berlin
[12] Wu H (1999) Low complexity bit-parallel finite field arithmetic using polynomial basis. in: Proceedings of the cryptographic hardware and embedded systems–CHES 1999, first international workshop. ser. Lecture notes in computer science, vol 1717. Springer, Berlin, pp 280–291 · Zbl 0976.94026
[13] IEEE standards documents (2004) IEEE P1363: standard specifications for public key cryptography. Draft Version D18. IEEE, http://grouper.ieee.org/groups/1363/
[14] Fong K, Hankerson D, López J and Menezes A (2004). Field inversion and point halving revisited. IEEE Trans Comput 53(8): 1047–1059 · doi:10.1109/TC.2004.43
[15] Fong K, Hankerson D, López J and Menezes A (2004). Field inversion and point halving revisited. IEEE Trans Comput 53(8): 1047–1059 · doi:10.1109/TC.2004.43
[16] Menezes AJ, Oorschot PC and Vanstone SA (1996). Handbook of applied cryptography. CRC Press, Boca Raton, FL
[17] Rodríguez-Henríquez F, Morales-Luna G, Saqib NA, Cruz-Cortés N (2007) A parallel version of the Itoh-Tsujii multiplicative inversion algorithm. In: Proceedings of International Workshop on Applied Reconfigurable Computing (ARC2007), Lecture notes in computer science, Mangaratiba, Brazil, March 2007, Vol 4419. Springer, pp. 226–237
[18] Rodríguez-Henríquez F, Saqib NA and Díaz-Pérez A (2004). A fast parallel implementation of elliptic curve point multiplication over GF(2 m ). Elsevier J Microprocessors Microsyst 28(8): 329–339 · Zbl 05461927 · doi:10.1016/j.micpro.2004.03.003
[19] Goodman J and Chandrakasan AP (2001). An energy-efficient reconfigurable public-key cryptography processor. IEEE J Solid-State Circuits 36(11): 1808–1820 · doi:10.1109/4.962304
[20] Bednara M, Daldrup M, Shokrollahi J, Teich J, von zur Gathen J (2002) Reconfigurable implementation of elliptic curve crypto algorithms. In: Proceedings of the 9th reconfigurable architectures workshop (RAW-02), Fort Lauderdale, FL, USA
[21] Lutz J (2003) High performance elliptic curve cryptographic co-processor. Master’s thesis, University of Waterloo
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.