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 for$f$is

We can check with SageMath that it is irreducible:

F2 = GF(2)
K.<x> = F2[]
f = x^8 + x^4 + x^3 + x + 1
f.is_irreducible()
# True

Matching Bytes as Finite Field Elements

A byte $b$ is composed of 8 bits $(b_7, \ldots, b_0)_2$ and is matched to a polynomial as

Polynomial Reduction

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

(x^8 + x^6 + x^4 + 1) % f
# x^6 + x^3 + x

R = K.quotient(f)
R(x^8 + x^6 + x^4 + 1)
# xbar^6 + xbar^3 + xbar

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

F.<x> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)
x^8 + x^6 + x^4 + 1
# x^6 + x^3 + x

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:

def F_to_hex(a):
    return ZZ(a.integer_representation()).hex()

b = x^4 + x^3 + x + 1
F_to_hex(b)
# '1b'

Addition

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

Multiplication

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

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

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

b = x^7 + x^5 + x^4 + x^2 + 1
F_to_hex(b)
# 'b5'
(2*0xb5 & 0xff) ^^ 0x1b).hex() == F_to_hex(x*b)    # the xor in Sage is "^^"
# True

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 bytes$(p_0,\ldots,p_{15})$are arranged from up to bottom, column by column in$4 \times 4$matrix. During the encryption, the state of this matrix changes and results in a 16-bytes ciphertext$(c_0,\ldots,c_{15})$whose 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;

• MC: MixColumn.

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 $(a_0, a_1, a_2, a_3)$ the quadruplet of elements of a column, the operation MC is done by multiplying with a matrix $M$.

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 $x$and $x+1$ in the field):

# we construct the matrix
# (we use the finite field F constructed in the previous page)
M = Matrix.circulant([x, x + 1, 1, 1])
M
# [    x x + 1     1     1]
# [    1     x x + 1     1]
# [    1     1     x x + 1]
# [x + 1     1     1     x]

# We multiply a column
col1 = vector([F.random_element() for i in range(4)])
col1
# (x^6 + x + 1, x^7 + x^4 + x^2, x^6 + x^4 + x^3 + x^2, x^7 + x^6 + x^4 + x^3 + x^2)
col2 = M*col1
col2
# (x^7 + x^5 + 1, x^6 + x^3, x^4, x^7 + x^5 + x^3 + x^2 + x)

Inverse of Mix Column

It is needed to reverse MC for the decryption process. Fortunately, there exists a matrix $N$ such that $M\times N = N \times M = \textrm{Id}$, the identity matrix.

N = M^-1
N
# [x^3 + x^2 + x   x^3 + x + 1 x^3 + x^2 + 1       x^3 + 1]
# [      x^3 + 1 x^3 + x^2 + x   x^3 + x + 1 x^3 + x^2 + 1]
# [x^3 + x^2 + 1       x^3 + 1 x^3 + x^2 + x   x^3 + x + 1]
# [  x^3 + x + 1 x^3 + x^2 + 1       x^3 + 1 x^3 + x^2 + x]

# hexadecimal representation
for row in N:
    print([F_to_hex(a) for a in row])
# ['e', 'b', 'd', '9']
# ['9', 'e', 'b', 'd']
# ['d', '9', 'e', 'b']
# ['b', 'd', '9', 'e']

col3 = N*col2
col3 == col1
# True

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 element$a$is replaced by $b = a^{-1}$ ($0$ has no inverse and is mapped to $0$);

2. An affine transformation on the coefficients of $a$:

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

def construct_sbox():
    mat = Matrix.circulant(vector(GF(2), [1,0,0,0,1,1,1,1]))
    sbox = []
    for a in range(256):
        # convert a byte value to field element
        b = sum(((a >> i) & 1)*x^i for i in range(8))
        # first step: map to inverse
        if b != 0:
        b = b^-1
        # second step:
        # affine transformation using a vector space over GF(2)
        b = mat*vector(b) + vector(GF(2), [1, 1, 0, 0, 0, 1, 1, 0])
        # convert the vector as an integer in [0, 255]
        sbox.append(sum(ZZ(b[i]) << i for i in range(8)))
    return sbox

sbox = construct_sbox()
for i in range(16):
    print([f'{a:02x}' for a in sbox[16*i : 16*(i + 1)]])
# ['63', '7c', '77', '7b', 'f2', '6b', '6f', 'c5', '30', '01', '67', '2b', 'fe', 'd7', 'ab', '76']
# ['ca', '82', 'c9', '7d', 'fa', '59', '47', 'f0', 'ad', 'd4', 'a2', 'af', '9c', 'a4', '72', 'c0']
# ['b7', 'fd', '93', '26', '36', '3f', 'f7', 'cc', '34', 'a5', 'e5', 'f1', '71', 'd8', '31', '15']
# ['04', 'c7', '23', 'c3', '18', '96', '05', '9a', '07', '12', '80', 'e2', 'eb', '27', 'b2', '75']
# ['09', '83', '2c', '1a', '1b', '6e', '5a', 'a0', '52', '3b', 'd6', 'b3', '29', 'e3', '2f', '84']
# ['53', 'd1', '00', 'ed', '20', 'fc', 'b1', '5b', '6a', 'cb', 'be', '39', '4a', '4c', '58', 'cf']
# ['d0', 'ef', 'aa', 'fb', '43', '4d', '33', '85', '45', 'f9', '02', '7f', '50', '3c', '9f', 'a8']
# ['51', 'a3', '40', '8f', '92', '9d', '38', 'f5', 'bc', 'b6', 'da', '21', '10', 'ff', 'f3', 'd2']
# ['cd', '0c', '13', 'ec', '5f', '97', '44', '17', 'c4', 'a7', '7e', '3d', '64', '5d', '19', '73']
# ['60', '81', '4f', 'dc', '22', '2a', '90', '88', '46', 'ee', 'b8', '14', 'de', '5e', '0b', 'db']
# ['e0', '32', '3a', '0a', '49', '06', '24', '5c', 'c2', 'd3', 'ac', '62', '91', '95', 'e4', '79']
# ['e7', 'c8', '37', '6d', '8d', 'd5', '4e', 'a9', '6c', '56', 'f4', 'ea', '65', '7a', 'ae', '08']
# ['ba', '78', '25', '2e', '1c', 'a6', 'b4', 'c6', 'e8', 'dd', '74', '1f', '4b', 'bd', '8b', '8a']
# ['70', '3e', 'b5', '66', '48', '03', 'f6', '0e', '61', '35', '57', 'b9', '86', 'c1', '1d', '9e']
# ['e1', 'f8', '98', '11', '69', 'd9', '8e', '94', '9b', '1e', '87', 'e9', 'ce', '55', '28', 'df']
# ['8c', 'a1', '89', '0d', 'bf', 'e6', '42', '68', '41', '99', '2d', '0f', 'b0', '54', 'bb', '16']

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