Finite field arithmetic

Rijndael (standardised as AES) uses the characteristic 2 finite field with 256 elements, which can also be called the Galois field GF(2⁸). It employs the following reducing polynomial for multiplication:

x⁸ + x⁴ + x³ + x + 1.

For example, {53} • {CA} = {01} in Rijndael's field because

	(x6 + x4 + x + 1)(x7 + x6 + x3 + x)
=	(x13 + x12 + x9 + x7) + (x11 + x10 + x7 + x5) + (x8 + x7 + x4 + x2) + (x7 + x6 + x3 + x)
=	x13 + x12 + x9 + x11 + x10 + x5 + x8 + x4 + x2 + x6 + x3 + x
=	x13 + x12 + x11 + x10 + x9 + x8 + x6 + x5 + x4 + x3 + x2 + x

and

	x13 + x12 + x11 + x10 + x9 + x8 + x6 + x5 + x4 + x3 + x2 + x mod x8 + x4 + x3 + x1 + 1
=	(11111101111110 mod 100011011)
=	{3F7E mod 11B} = {01}
=	1 (decimal)

The latter can be demonstrated through long division (shown using binary notation, since it lends itself well to the task. Notice that exclusive OR is applied in the example and not arithmetic subtraction, as one might use in grade-school long division.):

                        
          11111101111110 (mod) 100011011
         ^100011011     
          01110000011110
          ^100011011    
           0110110101110
           ^100011011   
            010101110110
            ^100011011  
             00100011010
              ^100011011  
               000000001

(The elements {53} and {CA} are multiplicative inverses of one another since their product is 1.)

Multiplication in this particular finite field can also be done using a modified version of the "peasant's algorithm". Each polynomial is represented using the same binary notation as above. Eight bits is sufficient because only degrees 0 to 7 are possible in the terms of each (reduced) polynomial.

This algorithm uses three variables (in the computer programming sense), each holding an eight-bit representation. a and b are initialized with the multiplicands; p accumulates the product and must be initialized to 0.

At the start and end of the algorithm, and the start and end of each iteration, this invariant is true: a b + p is the product. This is obviously true when the algorithm starts. When the algorithm terminates, a or b will be zero so p will contain the product.

• Run the following loop eight times (once per bit). It is OK to stop when a or b is zero before an iteration:
  1. If the rightmost bit of b is set, exclusive OR the product p by the value of a. This is polynomial addition.
  2. Shift b one bit to the right, discarding the rightmost bit, and making the leftmost bit have a value of zero. This divides the polynomial by x, discarding the x⁰ term.
  3. Keep track of whether the leftmost bit of a is set to one and call this value carry.
  4. Shift a one bit to the left, discarding the leftmost bit, and making the new rightmost bit zero. This multiplies the polynomial by x, but we still need to take account of carry which represented the coefficient of x⁷.
  5. If carry had a value of one, exclusive or a with the hexadecimal number 0x1b (00011011 in binary). 0x1b corresponds to the irreducible polynomial with the high term eliminated. Conceptually, the high term of the irreducible polynomial and carry add modulo 2 to 0.
• p now has the product

This algorithm generalizes easily to multiplication over other fields of characteristic 2, changing the lengths of a, b, and p and the value 0x1b appropriately.

When developing algorithms for Galois field computation on small Galois fields, a common performance optimization approach is to find a generator g and use the identity:

${\displaystyle ab=g^{\log _{g}(ab)}=g^{\log _{g}(a)+\log _{g}(b)}}$

to implement multiplication as a sequence of table look ups for the log_g(a) and g^y functions and an integer addition operation. This exploits the property that every finite field contains generators. In the Rijndael field example, the polynomial x + 1 (or {03}) is one such generator. A necessary but not sufficient condition for a polynomial to be a generator is to be irreducible.

An implementation must test for the special case of a or b being zero, as the product will also be zero.

This same strategy can be used to determine the multiplicative inverse with the identity:

${\displaystyle a^{-1}=g^{\log _{g}\left(a^{-1}\right)}=g^{-\log _{g}(a)}=g^{|g|-\log _{g}(a)}}$

Here, the order of the generator, |g|, is the number of non-zero elements of the field. In the case of GF(2⁸) this is 2⁸ − 1 = 255. That is to say, for the Rijndael example: (x + 1)²⁵⁵ = 1. So this can be performed with two look up tables and an integer subtract. Using this idea for exponentiation also derives benefit:

${\displaystyle a^{n}=g^{\log _{g}\left(a^{n}\right)}=g^{n\log _{g}(a)}=g^{n\log _{g}(a){\pmod {|g|}}}}$

This requires two table look ups, an integer multiplication and an integer modulo operation. Again a test for the special case a = 0 must be performed.

However, in cryptographic implementations, one has to be careful with such implementations since the cache architecture of many microprocessors leads to variable timing for memory access. This can lead to implementations that are vulnerable to a timing attack.

For binary fields GF(2ⁿ), field multiplication can be implemented using a carryless multiply such as CLMUL instruction set, which is good for n ≤ 64. A multiplication uses one carryless multiply to produce a product (up to 2n − 1 bits), another carryless multiply of a pre-computed inverse of the field polynomial to produce a quotient = ⌊product / (field polynomial)⌋, a multiply of the quotient by the field polynomial, then an xor: result = product ⊕ ((field polynomial) ⌊product / (field polynomial)⌋). The last 3 steps (pclmulqdq, pclmulqdq, xor) are used in the Barrett reduction step for fast computation of CRC using the x86 pclmulqdq instruction.[6]

When k is a composite number, there will exist isomorphisms from a binary field GF(2^k) to an extension field of one of its subfields, that is, GF((2^m)ⁿ) where k = m n. Utilizing one of these isomorphisms can simplify the mathematical considerations as the degree of the extension is smaller with the trade off that the elements are now represented over a larger subfield.[7] To reduce gate count for hardware implementations, the process may involve multiple nesting, such as mapping from GF(2⁸) to GF(((2²)²)²).[8] There is an implementation constraint, the operations in the two representations must be compatible, so explicit use of the isomorphism is needed. More precisely, the isomorphism will be denoted by map(), it is a bijection that maps an element of GF(2^k) to GF((2^m)ⁿ), satisfying: map(a + b) = map(a) + map(b) and map(a b) = map(a) map(b), where the operations on the left side occur in GF(2^k) before mapping and the operations on the right side occur in GF((2^m)ⁿ) after mapping.[9] The isomorphism is usually implemented with a k row by k bit matrix, used to perform a matrix multiply over GF(2) of an element of GF(2^k) treated as a k row by 1 bit matrix. Define α as a primitive element of GF(2^k), and β as a primitive element of GF((2^m)ⁿ). Then β^j = map(α^j) and α^j = map⁻¹(β^j). The values of α and β determine the mapping matrix and its inverse. Since the actual math is performed in GF((2^m)ⁿ), the reducing polynomial for GF((2^m)ⁿ) is usually primitive and β = x in GF((2^m)ⁿ). In order to meet the compatibility constraint for addition and multiplication, a search is done to choose any primitive element α of GF(2^k) that will meet the constraint. In the case where reducing polynomial for GF(2^k) is primitive, an alternate mapping method is possible: the 1 bit coefficients of the reducing polynomial for GF(2^k) are interpreted as m bit elements 0 or 1 of GF(2^m), and there will be m primitive factors of degree n, any of which can be used as the reducing polynomial for GF((2^m)ⁿ). Mapping to a composite field can be generalized to map GF(p^k) to a composite field such as GF((p^m)ⁿ), for p any prime.

Here is some C code which will add and multiply numbers in the characteristic 2 finite field of order 2⁸, used for example by Rijndael algorithm or Reed–Solomon, using the Russian peasant multiplication algorithm:

/* Add two numbers in the GF(2^8) finite field */
uint8_t gadd(uint8_t a, uint8_t b) {
	return a ^ b;
}

/* Multiply two numbers in the GF(2^8) finite field defined 
 * by the modulo polynomial relation x^8 + x^4 + x^3 + x + 1 = 0
 * (the other way being to do carryless multiplication followed by a modular reduction)
 */
uint8_t gmul(uint8_t a, uint8_t b) {
	uint8_t p = 0; /* accumulator for the product of the multiplication */
	while (a != 0 && b != 0) {
        if (b & 1) /* if the polynomial for b has a constant term, add the corresponding a to p */
            p ^= a; /* addition in GF(2^m) is an XOR of the polynomial coefficients */

        if (a & 0x80) /* GF modulo: if a has a nonzero term x^7, then must be reduced when it becomes x^8 */
            a = (a << 1) ^ 0x11b; /* subtract (XOR) the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible */
        else
            a <<= 1; /* equivalent to a*x */
        b >>= 1;
	}
	return p;
}

This example has cache, timing, and branch prediction side-channel leaks, and is not suitable for use in cryptography.

This D program will multiply numbers in Rijndael's finite field and generate a PGM image:

/**
Multiply two numbers in the GF(2^8) finite field defined
by the polynomial x^8 + x^4 + x^3 + x + 1.
*/
ubyte gMul(ubyte a, ubyte b) pure nothrow {
    ubyte p = 0;

    foreach (immutable ubyte counter; 0 .. 8) {
        p ^= -(b & 1) & a;
        auto mask = -((a >> 7) & 1);
        // 0b1_0001_1011 is x^8 + x^4 + x^3 + x + 1.
        a = cast(ubyte)((a << 1) ^ (0b1_0001_1011 & mask));
        b >>= 1;
    }

    return p;
}

void main() {
    import std.stdio, std.conv;
    enum width = ubyte.max + 1, height = width;

    auto f = File("rijndael_finite_field_multiplication.pgm", "wb");
    f.writefln("P5\n%d %d\n255", width, height);
    foreach (immutable y; 0 .. height)
        foreach (immutable x; 0 .. width) {
            immutable char c = gMul(x.to!ubyte, y.to!ubyte);
            f.write(c);
        }
}

This example does not use any branches or table lookups in order to avoid side channels and is therefore suitable for use in cryptography.