A Fast Modular Inversion FPGA Implementation over GF(2m) using Modified x2n Unit

Modular inversion is an important step in Elliptic Curve Cryptography (ECC). Itoh-Tsujii's algorithm (ITA) is a commonly applied modular inversion algorithm. This paper proposes a novel architecture of modular inversion implementation based on ITA. The modular multiplier and 2
ⁿ
units are modified into non-iterative logic to increase clock frequency. Least-clock-cycle-ITA and High-speed-ITA architectures are proposed to minimize latency in different situations. Both architectures are implemented on FPGA Virtex-5. LCC-ITA completes modular inversion in 9 clock cycles with maximum clock frequency 126.1MHz, while HS-ITA completes two modular inversions in 20 clock cycles with maximum clock frequency 177.6MHz. The performance of the proposed architectures is 56% and 134% higher than the best work before.