Two Normal Basis Multiplication Algorithms for GF(2n)

For software implementations, word-level normal basis multiplication algorithms utilize the full data-path of the processor, and hence are more efficient than the bit-level multiplication algorithm presented in the IEEE standard P1363-2000. In this paper, two word-level normal basis multiplication algorithms are proposed for GF(2n). The first algorithm is suitable for high complexity normal bases, while the second algorithm is fast for type-I optimal normal bases and low complexity normal bases. Theoretical analyses and experimental results both indicate that the presented algorithms are efficient in GF(2233), GF(2283), GF(2409), and GF(2571), which are four of the five binary fields recommended by the National Institute of Standards and Technology (NIST) for the elliptic curve digital signature algorithm (ECDSA) applications.