Hardware implementation of a novel inversion algorithm

Abstract

Computation of multiplicative inverses in finite fields GF (p) and GF (2/sup n/) is the most time consuming operation in elliptic curve cryptography especially when affine coordinates are used. Since the existing algorithms based on extended Euclidean algorithm do not permit a fast software implementation, projective coordinates, which eliminate almost all of the inversion operations from the curve arithmetic, are preferred. In this paper, a hardware implementation of inversion algorithms for both binary extension and prime fields is presented. The algorithms are varying slightly from the Montgomery inverse algorithm. A hardware structure, using multiword format is implemented on chip, which allows scalability with a broader precision range