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):

Introduction

The Advanced Encryption Standard most known as AES is one of the most used ciphers nowadays. Created by Vinent Rijmen and Joan Daemen under the name Rijndael, it won the NIST competition that resulted in its standardization in 2001 to replace older algorithms such as DES (and its variant 3DES). In fact, it is six times faster than 3DES.

AES encrypts a block of 16 bytes only at a time, though ciphertexts tend to be much longer. To accomodate this, cipherexts are cut in blocks of 16 bytes using an operating mode [see future section on mode]. We only focus on the encryption of a single block.

The array of 16 bytesare arranged from up to bottom, column by column inmatrix. During the encryption, the state of this matrix changes and results in a 16-bytes ciphertextwhose output can be read following the same ordering:

A key is involved and three sizes are possible: 128, 192, or 256 bits. Depending of the size, there are a few differences which will be explained later. For now, it is sufficient to know that round keys are derived from this master key.

Our interest is to look at what goes inside the transformation between the plaintext and the ciphertext. Basically, there are four operations on the state matrix, each important for the security of AES:

• AK: add round key;

• SR: shift row;

• SB: substitution box;

All these operations are executed a several number of times in what are called rounds to mix the plaintext enough. A look on the flow of an encryption is given in the figure below.

Two particular cases can be noticed:

• the first round is preceded by an additional AK;

• last round is missing MC.

The number of rounds NR is different depending on the master key length:

This page gives a description of the four operations that compose a round of AES. Each has been designed to satisfy criterias, one of them is that all must be invertible.

Add Round Key

Round keys are derived from the master key (see the Key Schedule section) and are all composed of 16 bytes. We simply xor byte by byte the state by the bytes of the round key in the according position.

Its inverse is itself: if we xor again, we get back the original value of the state.

Mix Columns

This operation mixes each column of the state independently from each other: each byte of the column is replaced by a (slightly different) combination of the four bytes of the column.

Let the quadruplet of elements of a column, the operation MC is done by multiplying with a matrix .

The calculations are performed in the finite field. If you are not familiar enough with the notions, you can skip to the next part and retain that this operation is also invertible using another matrix.

This matrix is circulant: each row is the same as the one above but is shifted by one column. So we can construct it in one line of SageMath (recall that the bytes 02 and 03 correspond respectively to and in the field):

Inverse of Mix Column

It is needed to reverse MC for the decryption process. Fortunately, there exists a matrix such that , the identity matrix.

Shift Rows

This operation shifts the rows of the state in the following manner:

The rows are shifted from top to bottom respectively by an offset of 0, 1, 2 or 3 columns to the left. Bytes that overflow on the left are put back to the right of the row.

The inverse is almost the same: the rows are shifted to the right instead by the same offsets and exceeding bytes are put back to the left.

Substitution Box

The precedent operations shuffle the plaintext in such a way that any modification of a byte has an impact to the whole state after several rounds. Though, this is not enough as those operations are linear: it means that the ciphertext could be expressed as linear equations from the plaintext and the master key. From a known couple plaintext/ciphertext it would be easy to solve the system and find the key.

The substitution box is the operation that breaks the linearity: each byte of the state is replaced by another following the table below.

Let sbox the name of this table, then for any bytes b1 and b2, we have

which is the desired property.

Though, this is not enough and the design of the sbox is made to include a sufficient algebraic complexity. The construction of the sbox table is done in two steps:

1. An elementis replaced by ( has no inverse and is mapped to );

2. An affine transformation on the coefficients of :

The table we gave above has been construted with SageMath and applying the two steps:

The inverse of the table is simple to produce: we only need to reverse the match between an input and its output.