Rijndael Finite Field

Each byte in AES is viewed as an element of a binary finite field of 256 elements, where it can always be represented as a polynomial of degree at most 7 with coefficients in$\mathbf{F}_2$. The construction of the finite field is made as the quotient ring$\mathbf{F}_2[x]/f(x)$, where$f$is an irreducible polynomial of degree 8 in$\mathbf F_2[x]$so the ring becomes a field.

In AES, the choice foris

We can check with SageMath that it is irreducible:

Matching Bytes as Finite Field Elements

A byte is composed of 8 bits and is matched to a polynomial as

For instance, take the byte 3a whose binary decomposition is and becomes the polynomial

Polynomial Reduction

Polynomials of degree 8 or more can always be reduced, using the fact that in the finite field, we have , so we have the relation

Why not ? In fact, that's also true, but the coefficient are in so the additive inverse of is itself.

In SageMath, this reduction can be produced in one of the following methods.

Method 1: Remainder of an Euclidean division by

Method 2: Image in the quotient ring

Method 3: Using the Finite Field class of SageMath directly.

On this page we use this last method. Also, this helper converts an element of the finite field to the hexadecimal representation of a byte, and could be useful in the examples:

Addition

The addition of two polynomials is done by adding the coefficients corresponding of each monomial:

And as the addition of the coefficients is in, it corresponds to the bitwise xor operation on the byte.

Multiplication

Multiplication of two polynomials is more complex (one example would be the , more efficient than the naive algorithm). For an implementation of AES, it is possible to only use the multiplication by , whose byte representation is 02.

Letan element and we consider the multiplication by:

All coefficients are shifted to a monomial one degree higher. Then, there are two cases:

• Ifis, then we have a polynomial of degree at most 7 and we are done;

• Ifis, we can replacebyduring the reduction phase:

This can be used to implement a very efficient multiplication bywith the byte representation:

1. A bitwise shiftleft operation: (b << 1) & 0xff;

2. Followed by a conditional addition with 1b if the top bit of is .

Here an example in SageMath (we use the finite field construction of method 3):