Performance of finite field arithmetic in an elliptic curve cryptosystem

The computational cost of encryption is a barrier to wider application of a variety of data security protocols. Virtually all research on elliptic curve cryptography (ECC) provides evidence to suggest that ECC can provide a family of encryption algorithms that require fewer computational resources for implementation than do current widely used methods. This efficiency is obtained since ECC allows much shorter key lengths for equivalent levels of security. This paper suggests how improvements in execution of ECC algorithms can be obtained by changing the representation of the elements of the finite field of the ECC algorithm. Specifically, this research compares the time complexity of ECC computation over a variety of finite fields with elements expressed in the polynomial basis (PB) and normal basis (NB). Results presented here suggest that NB representations reduce the average aggregate time to perform basic ECC operations by a factor of 40 compared to the time required for operations in PB representation. A comparison of execution times for ECC and discrete log implementations of the ElGamal protocol is also presented