Fast inversion in GF(2m) with normal basis using hybrid-double multipliers

作者：Azarderakhsh R; Jarvinen K; Dimitrov V

来源：IEEE Transactions on Computers, 2014, 63(4): 1041-1047.

DOI：10.1109/TC.2012.265

• ASIC
• binary extension field
• codes
• cryptography
• Finite field
• hybrid-double multiplier
• inversion
• Itoh-Tsujii
• normal basis

Fast inversion in finite fields is crucial for high-performance cryptography and codes. We present techniques to exploit the recently proposed hybrid-double multipliers for fast inversions in binary fields GF(2m) with normal bases. A hybrid-double multiplier computes a double multiplication, the product of three elements in GF(2m), with a latency comparable to the latency of single multiplication of two elements. Traditional approaches, such as Itoh-Tsujii, cannot utilize hybrid-double multipliers. We devise a new inversion algorithm based on ternary representations that exploits their potential. The algorithm reduces the latency of inversion significantly for the fields recommended by NIST if hybrid-double multipliers are employed. For example, the algorithm computes an inversion in GF(2163) with only five double multiplications whereas the Itoh-Tsujii algorithm requires nine single or double multiplications. We propose a new inverter architecture using this new algorithm and a hybrid-double multiplier. We show that it is faster than the existing techniques by providing ASIC synthesis results using 65-nm CMOS technology. For example, our inverter for GF(2163) achieves about 34 percent shorter computation time than an inverter using the Itoh-Tsujii algorithm and a single multiplier.

• 单位
  1; Aalto University; The University of Calgary; University of calgary; United States; 2