How does the AES encryption algorithm work?

Question

I’d like to understand how the encryption algorithm works AES (Advanced Encryption Standard). I seek didactic answers, which make me understand the processes used by the algorithm step-by-step, emphasizing the logical and mathematical part, and if possible, bit operations.

Note that I do not ask for code examples, although they are valid for the explanation.

Answer 1

AES is a cryptographic primitive intended to compose symmetric encryption and decryption systems (i.e. the same key to encrypt and decrypt). It is a block cipher, that is, it operates in blocks of fixed size (128 bits, or 16 bytes). Like any block cipher, it can be transformed into a block cipher flow cipher (in order to operate on data of arbitrary size) through a mode of operation, But that’s beside the point here. Can work with 128, 192 or 256 bit keys (the Rijndael algorithm, which originated AES, allows more key sizes).

In other words, it is an algorithm whose direct function (cipher) receives as inputs a 128-bit block (message) and a key of the chosen size, and returns an output also 128-bit (cipher). The inverse function (decipher) receives as input a 128-bit block (cipher) and returns as output a 128-bit block. If the key is the correct key, this output will be identical to the original message.

The goal of a successful cipher is that it is impractical to discover the original message if you only have the encrypted message, but not the encryption key. To do so, we try to minimize any visible correlation between input and output, so that the same (and/or key) can be deduced simply by observing a very large number of ciphers (or message/cipher pairs). For this, a series of "rounds" is used (or rounds) in which bytes undergo non-linear but reversible transformations (i.e. to decipher, the inverse of the same operations is simply performed in reverse order).

Finite Bodies

All operations in AES treat input bytes as one finite body (Finite Fields, or Galois Fields) in 2⁸. It means that:

• There is a set [0,255] (which are all possible values for a byte) and one of these elements is called "zero" (in this case, the 0);
• There is an operation, which we will call "addition", which applies to any two elements in that set and whose result is also an element of that set. This operation must be associative, commutative, have neutral element, and each element must have an inverse;
  • In this case, we define "addition" as "OR exclusive" - XOR.
• There is an operation, which we will call "multiplication", with characteristics similar to "addition". Except for the "zero" element, which has no inverse (and the neutral element of multiplication is called "one"). Multiplication also needs to be distributive in relation to addition.
  • "Multiplication" shall be defined below.

For those who have no experience with mathematics, it’s good to point out that we are defining "addition", "multiplication", "zero" and "one" - these names do not necessarily have anything to do with the usual arithmetic operations we do in the set of Natural or Real numbers (the Natural or Integer, for example, do not form bodies with the + and * usual, because there is no x within these sets such that 2*x=1; the Reals form a body, but infinity). There is no "subtraction", "division", etc.

The addition, as already stated, was defined as the XOR. Multiplication is more complex: first treat each operand as if it were a polynomial based on its binary representation (e.g..: 6 - 110 - flipped x^2 + x, and 11 - 1011 - flipped x^3 + x + 1), multiply them, then divide the result by a "reducing agent". The rest of the division (interpreted again as a number) will then be the result of multiplication. In the case of AES, the chosen reducing agent was:

x^8 + x^4 + x^3 + x + 1

So that multiply 6 for 11 is the same as doing

(x^2 + x)*(x^3 + x + 1) mod (x^8 + x^4 + x^3 + x + 1)
=[(x^5 + x^3 + x^2) + (x^4 + x^2 + x)] mod (x^8 + x^4 + x^3 + x + 1)
=(x^5 + x^4 + x^3 + x) mod (x^8 + x^4 + x^3 + x + 1)
=111010 mod 100011011
=111010
=58

Note that the coefficients are "summed" using the XOR, not the common sum: when summed x^2 with x^2 the result is zero, and not 2*x^2. Think of that sum as 1*x^2 + 1*x^2 = (1 xor 1)*x^2 = 0*x^2 = 0. The body GF(2^8) was built on the basis of GF(2) (binary field, where the sum is XOR and the multiplication is AND), so its polynomials have only 0 or 1 as coefficients. For more details, Wikipedia in English has an article on arithmetic in finite fields, including a specific subsection on Rijndael.

Wikipedia has a simplified algorithm which is equivalent to this multiplication of polynomials, but much less expensive (see at the end of the section).

That is, an AES implementation [not optimized] could for example create a distinct data type to represent each byte of the inputs/outputs/keys and give its own implementation of "addition" and "multiplication" (overloading the usual ones, if the programming language allows). That would simplify logic at the expense of performance.

big Disclaimer: nay I’m suggesting that laymen implement AES [to use in practice] - I don’t trust myself to implement cryptographic algorithms, let alone anyone reading this... I put this only for didactic purposes, a real implementation needs to worry even about things like Channel Attacks side (ex.: timing and fault).

• Note: From now on, whenever I speak in "add" or "multiply" I refer to operations in GF(2⁸), except where otherwise indicated.

Rijndael S-Box

Based on this finite field arithmetic, a query table was designed (lookup table) calling for Rijndael S-Box, intended to transform one byte into another, in a non-linear way. Two tables are used: one for the direct function and the other for the inverse.

• First, the multiplicative inverse of the byte is calculated (i.e. a byte such that multiplied by it results in "one"). Zero has no inverse, so it maps to zero anyway.

• Then the eight bits of the result are submitted to a related transformation, to make the method more resistant against algebraic attacks:

  [1 0 0 0 1 1 1 1][b0]   [1]
  [1 1 0 0 0 1 1 1][b1]   [1]
  [1 1 1 0 0 0 1 1][b2]   [0]
  [1 1 1 1 0 0 0 1][b3] + [0]
  [1 1 1 1 1 0 0 0][b4]   [0]
  [0 1 1 1 1 1 0 0][b5]   [1]
  [0 0 1 1 1 1 1 0][b6]   [1]
  [0 0 0 1 1 1 1 1][b7]   [0]
  

This table is designed to be resistant to Criptanalysis linear or differential, and allowing the replacement of the related transformation by another case backdoor in the future. For practical purposes, it is an invertible function whose output does not resemble the input at all (i.e. small changes in the input produce seemingly random differences in the output).

Key Expansion

As has been said, the AES has several rounds of calculation, which part of the original message, applies a series of transformations in it, and reaches the final result (the cipher). I’ll call the data being worked out "state" (state):

estado = mensagem
estado = round(estado)
estado = round(estado)
estado = round(estado)
...
estado = round(estado)
cifra = estado

In each state, the original encryption key is not used, but a series of keys derived from it. This derivation uses an algorithm called Rijndael Key Schedule, and is complex in itself to be fully explained here (despite the implementation is apparently short). I will give only an overview, therefore:

• AES operates on 128-bit blocks as seen, but uses 128-bit, 192-bit or 256-bit keys; the key expansion algorithm therefore produces a 128-bit subkey set - one for each round of the algorithm (which by the way also depends on the key size: are 10, 12 or 14 rounds, respectively).
• Starting from the original key, a series of operations is made involving the rotation (shift) of the last 4 bytes, its transformation according to the S-Box, and the addition with a power of 2. There is a small variation in the steps according to the key size used.
  • By "power of 2", I mean 2 multiplied by itself N times, in GF(2⁸). As you can see in this table, values are quite different from integer arithmetic.
• Once enough bytes have been produced for all rounds of the algorithm, the key expansion.

Rounds

The algorithm works in rounds, or rounds, so that in each of them a series of reversible operations is done over the state. The goal is that each byte of the input is "combined" with several bytes of the key, so that small changes in both the key and the message cause significant changes in the cipher (see Confusion and Diffusion). In other words, one wants to avoid that part of the cipher depends only on part of the key, which would break the problem of deciphering a large key by deciphering several smaller keys (which could be done by brute force).

Note: State bytes are commonly represented in a 4x4 array. This matrix is by column, not by line (as in most popular programming languages). That is, the 16 bytes are arranged as follows:

b0   b4   b8   b12
b1   b5   b9   b13
b2   b6   b10  b14
b3   b7   b11  b15

When "row" or "column" is mentioned, it refers to the 4 bytes of the state corresponding to the above representation.

1. In the first round, the status is added to the key of that round;

   estado = estado ^ chave(0)
   

2. In subsequent rounds:

   1. each state byte is transformed to S-Box;

      para cada byte b no estado:
          estado[b] = S(estado[b])
      

   2. Then the lines are rotated to the left, as follows:

      a00 a01 a02 a03   <<0   a00 a01 a02 a03
      a10 a11 a12 a13   <<1   a11 a12 a13 a10
      a20 a21 a22 a23   <<2   a22 a23 a20 a21
      a30 a31 a32 a33   <<3   a33 a30 a31 a32
      

   3. Then in each column of the array your bytes are combined with all other bytes in the same column; that step nay occurs in the last round.

      The detailed description of this step can be seen here. What is done is to take each column of the matrix and multiply it by a fixed matrix, resulting in the new column values:

      [a00]   [2 3 1 1][a00]
      [a10] = [1 2 3 1][a10]
      [a20]   [1 1 2 3][a20]
      [a30]   [3 1 1 2][a30]
      
      a00 = 2*a00 ^ 3*a10 ^ 1*a20 ^ 1*a30
      a10 = 1*a00 ^ 2*a10 ^ 3*a20 ^ 1*a30
      a20 = 1*a00 ^ 1*a10 ^ 2*a20 ^ 3*a30
      a30 = 3*a00 ^ 1*a10 ^ 1*a20 ^ 2*a30
      
      ... (idem pras demais colunas)
      

      By my understanding, multiplication continues to be multiplication in GF(2⁸), but in this case there is a simpler description of it: x*1 é x, x*2 é x<<1 and x*3 é x<<1 ^ x. If the result is greater than 255, do x ^ 0x1B.

   4. Finally, add the round key to the state.

      estado = estado ^ chave(i)   # onde i é o número da rodada
      

Summary

This series of operations (add key, replace, mix/exchange) is called "Substitution-Permutation Network", or SP-network. Here is a graphical representation of the process, with 3 rounds:

Decipher

The process of deciphering simply consists of applying the inverse of these same operations, in the reverse order naturally. Often it changes nothing between encrypting and decrypting (e.g..: a xor b xor b = a), in others some adaptation is needed:

1. Instead of starting with estado = mensagem and end with cifra = estado, now we start with estado = cifra and end with mensagem = estado;

2. The key expansion is equal; at the beginning of each round the corresponding round key is added (remembering that we are now doing the rounds backwards), and at the end add the key of the first round;

3. To undo step 3 (column mix) of each round where it applies (i.e. all except the first and the last), use the inverse matrix to that described above:

   [a00]   [14  11  13   9][a00]
   [a10] = [ 9  14  11  13][a10]
   [a20]   [13   9  14  11][a20]
   [a30]   [11  13   9  14][a30]
   

   (as this time there are no "shortcuts" for multiplication, it is common to use another lookup table instead of counting on time. Here has the relevant tables.)

4. Step 2 is simply a shift right instead of left...

5. To undo step 1, use a lookup table which corresponds to the inverse of S-Box.

Answer 2

First of all, my reply merely seeks to add content to the reply from mgibsonbr, which is already quite complete. I had to make a theoretical foundation for my Course Completion Work. I think it would be very selfish of me to leave everything I wrote on paper, so I decided to share what I wrote with the community. Some improvements are still needed and I think I may have made some mistakes, because the algorithm is very complex. If this happens, feel free to edit my answer.

1 - Cryptography

According to Bond et al. (2003), encrypting data means converting it so that it can only be deciphered and read by authorized users, so data encryption requires an algorithm to be applied to this data. The way of writing logic is called an algorithm, which, according to Cormen et al. (2002, p. 3), is nothing more than any well-defined computational procedure that takes some value or set of values as input and produces some value or set of values as output. Therefore, an algorithm is a sequence of computational steps that transform the input into the output. In this way, an encryption algorithm is a mathematical procedure that contains an input, the data to be encrypted, performs a processing mathematician based on a key, and generates a output: encrypted data (KUROSE; ROSS, 2010; BOND et al., 2003; RAPPAPORT, 2009; STALLINGS, 2008; FOROUZAN; FEGAN, 2008). Forouzan and Fegan (2008) explains some terms used when referring to cryptography, according to him:

1. Cipher: are the encryption and decryption algorithms
2. Key: is a number or set of numbers on which the cipher operates.

2 - Symmetric Encryption

Symmetric encryption is the type of encryption that uses the same key to encrypt and decrypt the data (FOROUZAN; FEGAN, 2008). Generally symmetric encryption algorithms are quite sophisticated and use 56-bit or 128-bit keys. Due to the size and mathematical probability of the number and complexity of the key, an encryption algorithm cannot be easily reversed, meaning that without the key, the encrypted data would take hundreds of years to be deciphered in a brute force attack, if, only if, the algorithm that encrypted this data is sufficiently robust (BOND et al., 2003).

Symmetric encryption is used to guarantee the confidentiality of certain data and ensures that only authorized recipients, those who know the decryption key, can recover the original data (BOND et al., 2003).

An example of symmetric cipher is the AES algorithm, Advanced Encryption Standard, which is an evolution of DES and was developed because the DES key was too short. AES is a very complex cyclic cipher and has been designed with three key sizes: 128, 192 or 256 bits (FOROUZAN; FEGAN, 2008).

3 - Asymmetric Cryptography

Asymmetric cryptography is one that uses different algorithms of symmetric cryptography and requires the use of two keys: the private key, which is kept secret by the owner and used to encrypt data, and the public key, which is known to persons authorised by the private key owner and is used to decrypt the data (FOROUZAN; FEGAN, 2008). However, if a data is encrypted with the public key, only the private key owner can decipher this data (BOND et al., 2003)

4 - The AES algorithm

The Advanced Encryption Standard algorithm, or simply AES, is a 128-bit (16-byte) block symmetric encryption algorithm, developed since 1997 by Vincent Rijmen and Joan Daemen, and announced on 26 November 2001 by NIST, (National Institute of Standards and Technology) US National Institute of Standards and Technology in free translation (NIST, 2001)¹.

The AES algorithm has 128-bit keys, 192 or 256 bits or 16, 24 and 32 bytes respectively. Key means the digital data set on which the cipher operates (FOROUZAN; FEGAN, 2008). Because it is a symmetric encryption algorithm with 128-bit blocks, the encryption function, which is the function responsible for transforming and shuffling the data, takes 16-byte (128-bit) blocks at a time and also returns 16 bytes per time. It is called the set of blocks that will be encrypted from "message", and the set returned by the "cipher" encryption function. The decryption process is done analogously, however, contrary to the encryption process, and therefore receives a set of encrypted blocks (cipher) and returns the identical message to the original, if only if the key is the same as the one used to encrypt the data. The encryption process can also be called encryption or even "cryptography", in the same way that the decryption process is synonymous with "decryption"or "decryption"(NIST, 2001). Figure 1 shows a pseudocode of the AES algorithm, the steps of the algorithm are explained later.

Figure 1 - AES pseudo code

Source: Adapted from NIST (2001, our translation)

5 - The State

Internally, AES algorithm operations are performed on a two-dimensional array of bytes called "State" (s). The state consists of an array organized in 4 columns of bytes, each containing 4 bytes, 16 bytes in total, and the values of each byte vary from 0 to 255. During the encryption or decryption process, the 128-bit (16-byte) blocks are copied to this array so that responsible operations are performed the functioning of the algorithm in this copy (NIST, 2001). Figure 2 illustrates the input blocks, the State array and the output blocks, and each item corresponds to one byte:

Figure 2 - Input Blocks, State and Output Blocks

Source: Adapted from NIST (2001, our translation)

6 - Addition operation

The addition is nothing more than a sum of the bits, known as the XOR operation (OR Exclusive), also called "exclusive disjunction". It is a logical operation between two operands that results in a true logical value if, and only if, exactly one of the operands has true value. It can be synthesized as a difference detector between two logical operands (NIST, 2001) and is represented by.

7 - Multiplication operation

In the case of the AES algorithm, multiplication is the polynomial representation GF(2⁸) (indicated by ), that is, corresponds to the multiplication of modulo polynomials in irreducible polynomials of degree 8. A polynomial is irreducible if its only divisors are one and the same (NIST, 2001, our translation). For the AES algorithm, this irreducible polynomial is: ²

or {01}{1b} in hexadecimal notation.

For example, 57 83 = C1 because:

The x⁷ + x⁶ + 1, obtained as a result, can be written as x⁷ + x⁶ + 0x + 0x + 0x + 0x + 0x + 1 corresponds to: {11000001} in binary, which is equivalent to {C1} hexadecimal.

Agents 2x² and 2x were cut because these polynyms only have 0 and 1 as factors, so even factors saw 0 and odd factors saw 1.

The modular reduction by m(x) ensures that the result will be a polynomial binary of degree less than 8, and thus can be represented by one byte. Unlike this, there is no single byte-level operation that corresponds to this multiplication (NIST, 2001, our translation)³.

Therefore, in a simple way, it is understood that the multiplication operation is the representation of the polynomial in its binary representation, made a multiplication of the agents of this equation and later divided by the reducing agent (module operation). The rest of this division will then be the result of the multiplication operation. In the case of AES, the reducing agent mentioned in Equation 2.1

8 - Rijndael S-Box and the Subbyte Step

The Rijndael S-Box, or simply S-Box, is a square, non-linear matrix, used as a substitution table in several byte transformations. It is also used in one-to-one byte key expansion routines. In the AES algorithm it is used in the Subbytes step and during the key expansion (Key Expansion)⁴ (NIST, 2001, our translation).

The Subbytes step, or Subbytes transformation, is a non-linear substitution that operates independently in each byte of the state array using the Rijndael S-Box substitution table (NIST, 2001, our translation). The Rijndael S-Box is revertible, and is constructed by the composition of two transformations⁵:

1. The multiplicative inverse of the byte is calculated, that is, one byte such that multiplied by itself, results in 1. Element 0 (zero) is mapped to itself.
2. An affine transformation is applied, which can be expressed as a matrix:

Similar transformation of the Rijndael S-Box

Source: Adapted from NIST (2001)

During the Subbytes step, the bytes of the State array are replaced from the S-Box, generating different and apparently random values. The S-Box used in this stage is shown in Figure 3.

Figure 3 - S-Box in hexadecimal notation

Source: Adapted from NIST (2001)

For example, if we have the State position_1,1 = {53}, then the value of the substitution will be determined by the intersection of the index line 5 and index column 3 illustrated in Figure 3. Therefore, the result of the substitution in the State position_1,1 will be {ed}.

9 - Shiftrows stage

In the Shiftrows step, the bytes of the last three lines of the state are moved cyclically along different numbers of bytes (offsets) ⁶ (NIST, 2001, our translation). Only the first line is not moved. Figure 4 illustrates this process and highlights the bytes that have been transposed.

Figure 4 - The Shiftrows step

Source: Adapted from NIST (2001)

10 - Mixcolumns Step

The Mixcolumns step operates on the State column by column, and treats each column as a four-term polynomial (NIST, 2001, our translation), according to the following equation⁷:

The columns are considered as polynomials and multiplied by the module x⁴ + 1 with a fixed polynomial a(x), given by the equation:

Therefore, the result of the Mixcolumns step over the State array, which is represented by s (x), is the multiplication of the polynomial described in Equation 2.9 by elements of the array of states s(x) which may be written as:

Being a(x) and s(x) the representation of matrices, and elements of these matrices, it is possible to represent Equation 2.10 in the form of a matrix multiplication, as in the NIST article on AES, so the equivalent representation can be seen in Figure 5 (NIST, 2001).

Figure 5 - Matrix-shaped representation for the Mixcolumns step

Source: Adapted from NIST (2001)

With the result of this multiplication, the four bytes of a column are replaced, element by element, as shown in Figure 6, right after:

Figure 6 - Elements to be replaced in the Mixcolumns step

Source: Adapted from NIST (2001)

After multiplication, the elements s_0,c , s_1,c , s_2,c and s_3,c of the State array, which together form a column c, shall be replaced by the following:'_0,c , s'_1,c , s'_2,c and s'_3,c , concluding the stage Mixcolumns, as shown in Figure 7.

Figure 7 - The Mixcolumns step

Source: NIST (2001)

11 - Addroundkey stage

The Addroundkey step consists of adding a subkey to each byte of the array Status, by means of a bit-by-bit XOR operation (addition). The key is expanded each round using the AES key expansion, so each round uses a different key derived from the original key, as seen in Figure 8.

Figure 8 - The Addroundkey step

Source: NIST (2001)

12 - Decryption

Decryption consists of a process analogous to encryption, but following the reverse order. The AES algorithm receives the encrypted content and if the key is the same as the one used to encrypt, the final result will be the original message. All ESA operations are easily invertible. In a simple way, it is possible, for example, to rotate the columns to the original State in the Shiftrows step, or know what the original byte is by checking the row and column containing the byte in the Subbytes step and reconnecting the previous state.

Notes:

1. The original reference of the algorithm can be obtained through the link: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf

2. In the polynomial representation, multiplication in GF(2⁸) (denoted by ) Corresponds with the multiplication of polynomials modulo an irreducible polynomial of Degree 8. A polynomial is irreducible if its only divisors are one and itself. For the AES Algorithm, this irreducible polynomial is:

3. The modular reduction by m(x) Nsures that the result will be a Binary polynomial of Degree Less than 8, and Thus can be represented by a byte. Unlike addition, there is no simple Operation at the byte level that Corresponds to this multiplication.

4. Non-linear substitution table used in several byte substitution Transformations and in the Key Expansion routine to perform a one-for-one substitution of a byte value.

5. The Subbytes() Transformation is a Non-linear byte substitution that operates independently on each byte of the State using a substitution table (S-box). This S-box (Fig. 7), which is invertible, is constructed by composing two Transformations.

6. In the Shiftrows() Transformation, the bytes in the last three Rows of the State are Cyclically shifted over Different Numbers of bytes (offsets). The first Row, r = 0, is not shifted.

7. The Mixcolumns() Transformation operates on the State column-by-column, treating each column as a fourterm polynomial as described in Sec. 4.3. The Columns are considered as polynomials over GF(2⁸ ) and multiplied module x 4 + 1 with a Fixed polynomial a(x), Given by:

Sources:

BOND, Martin et al. Learn J2EE in 21 days. [S.l.]: Pearson Education do Brasil, 2003.

CORMEN, Thomas H. et al. Algorithms: theory and practice. Rio de Janeiro: Ed. Elsevier, 2002.

FOROUZAN, Behrouz A.; FEGAN, Sophia Chung. Data Communication and Network Computers. [S.l.]: Mcgraw-Hill, 2008.

KUROSE, James F.; ROSS, Keith W. Computer Network and the Internet: a top-down approach. [S.l.]: Pearson Education, 2010.

RAPPAPORT, Theodore S. Wireless communication: principles and applications. [S.l.]: Pearson Prentice Hall, 2009.

NIST. Announcing the Advanced Encryption standard (aes). Federal Information - Processing Standards Publication 197, n. 197, p. 51, 2001. Available at: <csrc.nist.Gov/Publications/Fips/fips197/Fips-197.pdf>.

Thanks:

To the user mgibsonbr who initially answered this question and showed solidarity by removing my doubts in the comments and in the private chat. Very grateful! Without your knowledge and solidarity, I would never have prepared this answer and my knowledge about the AES algorithm (which is not yet complete and still need to study a lot) would tend to zero.

Answer 3

In cryptography, the Advanced Encryption Standard (AES), also known as Rijndael, is a block cipher adopted as an encryption standard by the US.

It is expected to be used around the world and analyzed extensively, as was its predecessor, the date Encryptation Standard (DES). The AES was announced by the NIST (US National Institute of Standards and Technology) as U.S. FIPS PUB (FIPS 197) on November 26, 2001, after 5 years of a standardization process. It became an effective standard on May 26, 2002. By 2006, AES is already one of the most popular algorithms used for symmetric key encryption.

AES has a 128-bit block size and a 28-bit, 192-bit or 256-bit key size, while Rijndael can be mirrored with keys and block sizes of any 32-bit multiple, with a minimum of 128-bit and a maximum of 256-bit.

The key is expanded using Rijndael’s key scheduling. Most AES calculations are done in a finite field of their own. AES operates on a two-dimensional array of 4x4-position bytes, called state (versions of Rijndael with a larger block size have additional columns in the state).

To encrypt, each AES turn (except the last one) consists of four stages (as already illustrated in the other answers):

1. Addroundkey - each byte of the state is combined with the proper shift (Roundkey) Ubkey; each Ubkey is derived from the main key using the key scheduling algorithm.

2. Subbytes - is a non-linear substitution step where each byte is replaced by another according to a reference table.

3. Shiftrows - is a transposition step where each row of the state is shifted from a certain number of positions.

4. Mixcolumns - is a merge operation that operates on the state columns and combines the four bytes of each column using a linear transformation. The final turn replaces the Mixcolumns stage with a new Addroundkey stage.