Algorithm and architecture for a Galois field multiplicative arithmetic processor

摘要

We present a new algorithm for generic multiplicative computations of the form ab/c in GF(p/sup m/), including multiplication, inversion, squaring, and division. The algorithm is based on solving a sequence of congruences that are derived from the theory of Grobner bases in modules over the polynomial ring GF(p)[x]. Its corresponding hardware and software architectures can be successfully used in applications such as error control coding and cryptography. We describe a versatile circuit associated with the algorithm for the most important case p=2. The same hardware can be used for a range of field sizes thus permitting applications in which different levels of error control or of security are required by different classes of user. The operations listed are all performed by the hardware in the same number of clock cycles, which prevents certain side-channel attacks. The loss in performance by having 2m iterations for multiplication is compensated by the full parameterization of the Galois field and the ability to perform division and multiplication in parallel.