An FPGA Implementation of Fast Finite Field Multiplication

Data encryption is an important component in digital communications. The efficiency of data encryption algorithms depends on their hardware implementations. This work presents a new modality for elliptic curve cryptographic algorithms using fields programmable gate array (FPGA) hardware units.

The basic operation in elliptic curve cryptography is that of “point multiplication”, which can involve a huge number of ordinary multiplications. Hence it is of utmost importance to optimize multiplication.

In this work we develop a fast algorithm for multiplication in optimal extension fields (OEFs) that is particularly suited for implementation on FPGAs. An OEF is a finite field GF(p^m) such that p is a pseudo Mersenne prime, i.e., a prime of the form 2ⁿ±c, where log₂ c≤ ½n , and an irreducible binomial P(x)=x^m-ω over GF(p).

Arithmetic in an OEF is efficient due to the efficiency of arithmetic in the ground field GF(p) and the simplicity of reduction modulo the irreducible binomial that defines GF(p^m). Making use of the Mastrovito matrix, we can compute a product in GF(p^m) in the polynomial basis using m²+m-1 scalar multiplications and m(m-1) scalar additions, the same operation count as that of the usual method. However, the Mastrovito matrix for an OEF is Toeplitz, i.e., has constant diagonals, which give opportunities for pipelining. Moreover, when the constant term ω is a power of 2, m-1 of the multiplications can be performed via shifts. Thus, we expect our FPGA implementation of this algorithm to be more efficient than the usual algorithm, in both time and area.