LIGHTWEIGHT AND FAST EXPONENTIATION METHODS IN GALOIS FIELDS

Abstract

Algebraic operations in Galois fields present properties that render them suitable for use in implementations of cryptographic primitives. Two fundamental operations of interest are modulo squaring and multiplication, whose implementations can be accelerated by using Galois field algebra. An approach is proposed for the acceleration of the calculation of modulo exponentiation in Galois fields, an operation that is fundamental for a wide spectrum of cryptographic algorithms. The approach is based on two developed procedures, namely fast exponentiation to the square and multiplication with a constant number in Galois fields. The proposed innovative accelerated calculation is attained via the use of the properties of the second order polynomial, the Montgomery group reduction and the derivation of pre-calculated tabular results. The mathematical foundation of the proposed method is given, followed by numerical examples that illustrate its operation. The amount of memory required is also calculated. It has been proved, both theoretically and experimentally that the proposed approach renders possible the acceleration of exponentiation in Galois fields by 5 to 7 times, in comparison with known methods