Using an efficient way to compute the product of a Toeplitz matrix and a vector, a sub-quadratic arithmetic complexity scheme for field multiplication over binary extension fields has recently been proposed by Fan and Hasan. The scheme has been developed using a shifted polynomial basis for the representation of the field elements and has been stated to be applicable to the conventional polynomial basis, although with an increased gate delay for some field defining polynomials. The conventional polynomial basis is widely used in practice and is part of
different recommendations and standards for cryptographic applications. In this article, we give additional details of the sub-quadratic complexity algorithm for the case of the polynomial basis by presenting efficient transformation matrices for a class of low weight field defining polynomials, namely trinomials.
In FIPS 186-2, NIST recommends several finite fields to be used in the elliptic curve digital signature algorithm (ECDSA). Of the ten recommended finite fields, five are binary extension fields with degrees ranging from 163 to 571. The performance of the underlying field operations (i.e. addition and multiplication) directly affect the performance of the ECDSA algorithm. In this paper we discuss a high performance look-up table-based VLSI architecture which performs multiplication over a given finite field. First we present the architecture in a general form which can be implemented for any finite field and corresponding reduction polynomial. Following, we discuss a prototype implementation of the multiplier for the binary extension field with degree 163. The prototype is capable of performing a finite field multiplication in .06 microseconds when implemented on a Xilinx XCV2000E FPGA.