Date of Award

2012

Degree Type

Dissertation

Degree Name

Ph.D.

Department

Electrical and Computer Engineering

First Advisor

Wu, Huapeng (Electrical and Computer Engineering)

Keywords

Electrical engineering.

Rights

CC BY-NC-ND 4.0

Abstract

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 Fermat's approach is reduced to the problem of finding a clever way to compute an exponentiation, which is a function of the field's 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.

Share

COinS