Fast and Generic Inversion Architectures Over src='/images/tex/25826.gif' alt='mbox{GF}(2^m)'> 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.