Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

8

FINITE FIELD OPERATIONS

Finite field operations are used as computation primitives for executing numerous cryptographic algorithms, especially those related with the use of public keys (asymmetric cryptography). Classical examples are ciphering deciphering, authentication, and digital signature protocols based on RSA-type or elliptic curve algorithms. Other classical applications of finite fields are error correcting codes and residue number systems. This chapter proposes algorithms allowing the execution of the main arithmetic operations (addition, subtraction, multiplication) in finite rings Z_m and polynomial rings Z_p[x]/f(x). In the case of Z_m, an exponentiation algorithm based on the Montgomery multiplication concept is also described. If p is prime and f(x) is an irreducible polynomial, then Z_p, Z_p[x]/f(x), GF(p), and GF(pⁿ) are finite fields for which inversion algorithms are proposed.