Look-up table-based large finite field multiplication in memory constrained cryptosystems

Many cryptographic systems use multiplication in the finite field GF(2(n)) for their underlying computations. In the recent past, a number of look-up table-based algorithms have been proposed for the software implementation o f GF(2(n)) multiplication. Look-up table-based algorithms can provide speed advantages, but they either require a large memory space or do not fully u tilize the resources of the processor on which the software is executed. In this work, an algorithm for GF(2(n)) multiplication is proposed which can alleviate this problem. In each iteration of the proposed algorithm, a grou p of bits of one of the input operands are examined and two look-up tables are accessed. The group size determines the table sizes, but does not affec t the utilization of the processor resources. It can be used for both softw are and hardware realizations and is particularly suitable for implementati ons in memory constrained environment, such as smart cards and embedded cry ptosystems.