Fast and Generic Inversion Architectures Over GF(2m) Using Modified Itoh-Tsujii Algorithms

Finite field inversion is the most computationally intensive field operation in public-key cryptographic algorithms such as elliptic curve cryptography. In this brief, we propose two inversion acceleration techniques for the Itoh-Tsujii algorithm (ITA) over binary extended field. First, we reformulate the ternary-ITA algorithm to generalize the primitive one, so that a universal algorithm procedure for all fields is achieved. Next, we devise a parallel-ITA algorithm to advance the parallelism of ITA. These two techniques are implemented on FPGA platform, and it is experimentally shown that a fast ternary-ITA inverter supporting all NIST fields can be obtained, with 22.9% timing improvement on average compared to the ITA inverter. In addition, the parallel-ITA inverter is a more balancing design that achieves averagely 25.7% of timing decrease compared to the ITA inverter while maintaining 31.3% reduction of area-time product compared to the ternary-ITA inverter.