Abstract
Finite field arithmetic is the building block of public-key cryptographic schemes, which are used widely for security and privacy of consumer electronics hardware and software systems. Since inversion is the most expensive finite field arithmetic operation, this paper proposes a novel, fast, and compact inverter over binary fields based on the traditional extended Euclidean algorithm (EEA). The proposed design outperforms the reported inverters in terms of area and speed. A modified EEA algorithm is presented and the design space of inversion over {\text{GF}}(2^{m}) is explored in order to allow for parallelism and concurrency, resolving the disturbing issues of variables alignment, before and during each inversion iteration. Polynomial division and multiplication are revisited, in order to derive their iterative equations, which are suitable for systolic array implementation. Then, a concurrent divider/multiplier is developed using a systematic methodology, while the resulting systolic architecture is utilized to build the EEA-based inverter. Finally, the complexity of the proposed design is analyzed and compared with efficient inverters in the literature, showing the lowest area-time complexity.