Advaned Encryption Standard

AES is a symmetric encryption algorithm, which means it uses the same key for both encryption and decryption. It is used in many protocols, including TLS, which establishes a secure HTTP connection, also known as HTTPS. As you read this article, AES is probably protecting the data exchanged between this website and your device.

At its core, AES is an SP-network, operating on a 4×4 matrix of 16 bytes called the state.

The algorithm consists of multiple rounds. A round consists of four state transformations, with each step designed to provide confusion and diffusion properties that a good encryption algorithm usually has.

Let’s take a high-level overview of encryption and decryption, and then I will discuss each procedure in more detail.

Encryption

In short, the AES encryption process begins with key expansion; multiple round keys are derived from the main encryption key. After that, we simply perform rounds of operations: SubBytes, ShiftRows, MixColumns, and AddRoundKey.

Take a look at this diagram:

Decryption

For decryption we do almost the same, but in reverse order, using inverse versions of the operations: InvSubBytes, InvShiftRows, InvMixColumns, and AddRoundKey.

Also, note that in decryption, AddRoundKey comes before InvMixColumns to maintain mathematical properties.

Let’s now look in more detail at each procedure.

Key Expansion

Before processing anything, we need round keys. They can be computed from the main encryption key using a specific algorithm called AES Key Schedule.

We will produce N+1 keys, where N is the number of main rounds. For example, in AES-256 we have 14 main rounds; we will generate 15 keys. One extra key is needed for the initial round.

We split our main key into words. In this context, a word is 4 bytes. So, one round key is 4 words, and its size is 16 bytes.

Initial words are just words of the main encryption key.

New words are computed through a combination of XOR operations with a previous word, depending on position, modified by special transformations.

When generating every Nth word (where N is the main key length in words), we rotate bytes one position left (RotWord), substitute them using sbox (SubWord), and the result is XORed with a round constant.

For AES-256, an additional SubWord operation occurs halfway through each expansion cycle.

We compute words until all round keys are completed.

Below are visual explanations of how the key schedule works for each key size. Sometimes it’s easier to explain using images than words.

Once the key is expanded, we can go through core transformations starting with the SubBytes.

SubBytes

This is a non-linear substitution step where each byte is replaced with another according to a predetermined lookup table called the S-box.

The S-box table has 256 unique values. These are all possible values a single byte can have.

ShiftRows

In the ShiftRows step, each row does a cyclic left shift:

• R1: stays in place
• R2: moves 1 byte left
• R3: moves 2 bytes left
• R4: moves 3 bytes left

MixColumns

In the MixColumns step, each column is multiplied with a fixed 4x4 matrix over the Galois Field GF(2⁸).

This multiplication is not a standard dot product, but it’s a similar idea.

We represent each byte as a polynomial like this:

b7·x^7 + b6·x^6 + b5·x^5 + b4·x^4 + b3·x^3 + b2·x^2 + b1·x + b0

The “addition” during the matrix multiplication is performed using bitwise XOR, and the “multiplication” involves polynomial multiplication followed by a modular reduction using the irreducible polynomial x⁸+x⁴+x³+x+1.

This operation implements diffusion, where each cell depends on all other cells in the same column, making ciphertext hard to analyze.

Note: In the final round, we skip the MixColumn step to make decryption easier and also avoid extra computations.

AddRoundKey

In this step, each byte of the state is matrix combined with the corresponding byte of the round key using the XOR operation.

By the way, there’s no need for a separate InvAddRoundKey step for decryption because applying the second XOR undoes the first one.

Operation Modes

To encrypt data larger than a single block, modes of operation, such as ECB, CBC, CTR, and GCM, are used. These modes determine how to securely apply encryption repeatedly across multiple blocks.

Here’s a visual example of CBC mode:

Padding Schemes

Plaintext isn’t always an exact multiple of AES’s block size, which is 16 bytes. To fill the remaining space, padding schemes are used. The well-known padding schemes are PKCS#7, ANSI X.923, and zero padding.

PKCS#7 adds N bytes of value N to complete a block. It always pads, even when data perfectly fits in 16 bytes, adding an extra full padding block.

ANSI X.923 sets the last padding byte to the length of padding and fills the rest with zeros. It also adds an additional padding block if no padding is needed.

Zero padding simply fills the empty space with zeros, though this can cause issues if the plaintext naturally ends with zeros.

Performance

AES was chosen as a standard not just because it performs good encryption, but also because it does it very fast.

Intel and AMD have even implemented direct CPU instructions for AES encryption.

Also, instead of performing polynomial multiplication in the MixColumns step on the fly, the results for all possible byte values can be precalculated and stored in lookup tables. Lookup table access time is usually O(1), which is constant time.

Thank you for reading this article about Advanced Encryption Standard. Have a good day!

You can check out the full AES-256-CBC implementation written by me in the C language in this repository.