Efficient finite field arithmetic with cryptographic applications

Abstract

Finite field multiplication is one of the most useful arithmetic operations and has applications in many areas such as signal processing, coding theory and cryptography. However, it is also one of the most time consuming operations in both software and hardware, which makes it pertinent to develop a fast and efficient implementation. We propose four improved FPGA multiplication implementations using the Karatsuba and Fast Fourier Transform algorithms over GF (2n). We also implement the hyperelliptic curve coprocessor and compare the results of our finite field arithmetics on the ring arithmetics. Three of our implementations are based on the Karatsuba algorithm which has a running time of O (n1.585). Our final implementation is based on Fast Fourier Transform algorithm who's running time is O (nlog(n)). They are a significant increase from the classical schoolbook algorithm which has a running time of O (n2). We then approximate the ring arithmetic's performance in our hyperelliptic curve coprocessor by applying our finite field implementations. We had improvements of up to 96 percent over the classical multiplier. We conclude that we have the most efficient ring arithmetic FPGA implementation with regards to area and speed.