Speeding Up finite Field Inversion for Cryptographic Applications

摘要

In elliptic curves cryptography, the curves are always defined over a particular finite field to provide the required cryptographic services. Currently, such services are the engine of most network security applications in practice. Scalar multiplication is the core operation of most such cryptographic services. Scalar multiplication performs field inversion very frequently in the underlying finite field. Field inversion is the most time-consuming operation that requires a special attention. Therefore, by accelerating field inversion, in addition to their inherent high level of security, such cryptographic services are executed fast. In finite extension fields GF(pm) with the extension degree m, accelerating field inversion by following Fermatu27s approach is reduced to the problem of finding a clever way to compute an exponentiation, which is a function of the fieldu27s extension degree m. By applying the concept of short addition chains combined with the idea of decomposing (m-1) into several factors plus a remainder, with some restrictions applied, field inversion in such fields is computed very fast. Two field inversion algorithms are proposed based on the suggested methods above. They are mainly proposed for extension fields of characteristic p two and three using normal basis representation. Fast Frobenius map operation proposed and extended to higher characteristic extension fields. Both algorithms, relative to existing inversion algorithms, require the minimal number of field multiplications, the second costly operations, those necessary to perform the exponentiation for field inversion. The obtained results confirmed the validity of the proposed ideas herein.