Fast and Efficient Generalized Galois Field Fixed Field Constant Multiplier

University of Massachusetts, Lowell
posted on 01/14/2009

• request more info 
•   
•  LICENSE ONLINE

In 2000, Rijndael was chosen by NIST has chosen as the Advanced Encryption Algorithm that will be the new worldwide encryption standard in the industry. Previous Data Encryption Standards were designed for hardware implementation whereas Rijndael was chosen for both hardware and software implementation.

The Rijndael algorithm requires Galois Field (GF) fixed field constant multiplication. The standard method for implementing this type of multiplication in software and hardware employs large, fixed arrays of look-up-tables. Implementations based on look-up-tables are optimized for speed at the cost of additional logic resources. However, in each case, the implementation must be completely regenerated when changing to a new algorithm with a new Galois Field fixed field constant matrix. The problems with this approach cause degradation in the performance of a system and increase the processing time substantially. From a hardware standpoint, the calculation requires a significant amount of both gates and real estate on a chip. Chips continue to be smaller in size to accommodate devices such as ultra-lite laptops, PDAs, MP3 players, and wireless devices. While chips are getting smaller, they are also designed with multiple functions and features that take up significant real estate.

The present invention by Dr. Adam Elbirt and Dr. Christof Paar is a process and hardware solution that helps to reduce the hardware resource requirements by a factor of 21 for calculating the GF fixed field constant multiplications without degrading performance. Furthermore, it also significantly improves software throughput versus software-only implementations by factors ranging from 10 to over 3043 depending on the processor word size. This technology is versatile and may be implemented targeting processors with 8-bit to 64-bit processor word sizes. The invention reduces the required number of gates (from ˜ 131,000 to ˜ 6,500), thereby requiring considerably less real estate and enabling the circuit to be incorporated as a component on a chip.