The Advanced Encryption Standard (AES)

Try a demo of the protocol

The math and definitions explained

In cryptography we often encrypt and sign messages that contains characters, but asymmetric key cryptosystems (Alice and Bob uses different keys) such as RSA and ElGamal are based on arithmetic operations on integer. And symmetric key cryptosystems (Alice and Bob uses the same key) such as DES and AES are based on bitwise operations on bits (a bit is either equal 0 or 1 and is an abbreviation for binary digit). Therefore, we have to convert the characters into integers or bits before we apply the cryptosystem to the message.

Because a computer can only handle bits, there already exists a method for converting characters into integers or bits, that uses the ASCII (American Standard Code for Information Interchange) table. A part of the ASCII table from Wikipedia is listed in the following table (notice that the binary representation on the Wikipedia site is only seven bits but we use eight bits, i.e. we have prepended an extra 0):

Character Decimal Hexadecimal Binary
(space) 32 20 00100000
! 33 21 00100001
\( \vdots \) \( \vdots \) \( \vdots \) \( \vdots \)
A 64 40 01000001
B 66 42 01000010
\( \vdots \) \( \vdots \) \( \vdots \) \( \vdots \)
a 97 61 01100001
b 98 62 01100010
\( \vdots \) \( \vdots \) \( \vdots \) \( \vdots \)

E.g. if Alice wants to send the message "Hey Bob!" encrypted to Bob with a symmetric key cryptosystem, she first converts it into its integer representation and then into its binary representation:

\( \eqalign{ H &\rightarrow 72 &&\rightarrow 01001000 \\ e &\rightarrow 101 &&\rightarrow 01100101 \\ y &\rightarrow 121 &&\rightarrow 01111001 \\ &\rightarrow 32 &&\rightarrow 00100000 \\ B &\rightarrow 66 &&\rightarrow 01000010 \\ o &\rightarrow 111 &&\rightarrow 01101111 \\ b &\rightarrow 98 &&\rightarrow 01100010 \\ ! &\rightarrow 33 &&\rightarrow 00100001 } \)

I.e. the message "Hey Bob!" is represented with integers as "72 101 121 32 66 111 98 33" and in binary as "01001000 01100101 01111001 00100000 01000010 01101111 01100010 00100001".

In math we are all familiar with the arithmetic operations such as addition, subtraction, multiplication and division. However, a computer works on bit strings, i.e. strings of 0's and 1's, and therefore needs similar operations when given two bit strings. The most important bitwise operations are NOT, AND, OR and XOR. In the following we give the result of the operations with one or two bits as input.

The NOT operation is often represented as !:

  • \( !0 = 1\)
  • \( !1 = 0\)

The AND operation is represented as \( \wedge \):

  • \( 0 \wedge 0 = 0\)
  • \( 1 \wedge 0 = 0\)
  • \( 0 \wedge 1 = 0\)
  • \( 1 \wedge 1 = 1\)

The OR operation is represented as \( \vee \):

  • \( 0 \vee 0 = 0\)
  • \( 1 \vee 0 = 1\)
  • \( 0 \vee 1 = 1\)
  • \( 1 \vee 1 = 1\)

The XOR (exclusive OR) operation is represented as \( \oplus \):

  • \( 0 \oplus 0 = 0\)
  • \( 1 \oplus 0 = 1\)
  • \( 0 \oplus 1 = 1\)
  • \( 1 \oplus 1 = 0\)

Alice and Bob's adversary Eve can make the following types of attacks on a symmetric key cryptosystem such as DES and AES:

  • Ciphertext only attack: Eve tries to guess the key used to encrypt an observed ciphertext sent between Alice and Bob.
  • Known plaintext attack: Eve somehow know the plaintext of an observed ciphertext sent between Alice and Bob and tries to guess the key.
  • Chosen plaintext attack (CPA): Eve cheats Alice or Bob to encrypt a message of her choice and with her knowledge of the ciphertext and plaintext she tries to guess the used key.
  • Chosen ciphertext attack (CCA): Eve can send a ciphertext to Alice or Bob and they return the decrypted message. With her knowledge of the ciphertext and plaintext she tries to guess the used key.

Symmetric key cryptosystems can be divided into two groups; deterministic and probabilistic cryptosystems. A deterministic cryptosystem such as DES and AES uses no randomness during the encryption, i.e. the same plaintext encrypted twice with the same key returns always the same ciphertext (which can be observed by Eve). This problem can be solved with a probabilistic cryptosystem such as the various modes of operations there exists for DES and AES, which uses randomness in form of an initialization vector.

In a good deterministic cryptosystem there should be no relation between the plaintext and ciphertext whatsoever when the key is unknown, i.e. encryption in a deterministic cryptosystem should behave like a truly random function. If this is the case we say that the encryption function is a pseudo-random function (PRF) and the cryptosystem is PRF-secure if Eve's advantage in guessing correct in the following game is negligible:

Eve sends a message \( m \) to an oracle and it returns a ciphertext \( c \) where \( c \) is either an encryption of \( m \) using the encryption function of the cryptosystem or an encryption of \( m \) using a truly random function. Eve then tries to guess which encryption function the oracle used.

With a probabilistic cryptosystem we can achieve higher security compared to a deterministic cryptosystem and therefore we require that Eve can't tell the difference between a real encryption of hers message \( m \) and an encryption of a random message with no relation at all to \( m \). We say that a probabilistic cryptosystem is CPA-secure if Eve's advantage in guessing correct in the following game is negligible:

Eve sends a message \( m \) to an oracle and it returns a ciphertext \( c \) where \( c \) is either an encryption of \( m \) or a random message with the same length as \( m \). Eve then tries to guess what \( c \) is an encryption of.

Hence, if a probabilistic cryptosystem is CPA-secure the only information that a ciphertext leaks is the length of the encrypted message.

The cryptography explained

Until 1999 had the Data Encryption Standard (DES) been the standard algorithm for encryption but due to its short 56-bit keys and 64-bit blocks, NIST (the National Institute of Standards and Technology) began the process of choosing its replacement, the Advanced Encryption Standard (AES).

NIST created an open competition where they required that AES has blocks of 128-bit and support keys of 128-, 192 and 256-bit. Initial in 1998 was 21 cryptosystems submitted where 15 met all the necessary criteria and were announced as the AES candidates. Later in 1999 were the five candidates MARS, RC6, Rijndael, Serpent and Twofish chosen by NIST as the finalists and were evaluated accordingly to the three criteria: security, efficiency (in both hardware and software) and implementation. They where all believed to be secure and none was superior in all three of the criterias but Rijndael had a good balance between the three criterias and was in 2000 announced as the AES. The Rijndael cipher was invented by the Belgian cryptographers J. Daemen and V. Rijmen and was adopted as a standard in 2001, replacing DES.

AES is an iterated cipher with plaintexts and ciphertexts of 128-bit where Alice and Bob uses the same 128-, 192-, or 256-bit key \( K \) for encrypting and decrypting. Because Alice and Bob uses the same key AES is called a symmetric key cryptosystem where e.g. Alice sends the key to Bob with an asymmetric cryptosystem such as RSA or ElGamal. The reason why symmetric key cryptosystems are used when they first have to use an asymmetric cryptosystem to exchange the key, is because they are much faster than asymmetric cryptosystems.

A big difference between the following description of DES and an asymmetric cryptosystem is that we will operate with bits and their bitwise operations instead of integers and their arithmetic operations. And hence, plaintexts and ciphertexts are sometimes referred to as blocks in symmetric cryptosystems because they are bitstrings.

AES is similar to DES because it during encryption and decryption repeats a basic operation multiple times. The names of the used operations in AES are: state, addRoudKey, subBytes, shiftRows and mixColumns (see below for a description of each operation). If the key \( K \) is 128-bit AES uses 10 rounds (iterations), a 192-bit key uses 12 rounds and a 256-bit key uses 14 rounds where we denote the number of rounds as \( n \), i.e. \( n = 10 \), \( n = 12 \) or \( n = 14 \).

As we will describe later uses AES an operation called addRoundKey \( n+1 \) times, that XOR two 128-bit strings: the current state \( s \) (see below) and the current round key \( K^{i} \). But as previously described agrees Alice and Bob only on a single 128-, 192, or 256-bit key \( K \). To solve this problem they uses a key schedule that diverts from the key \( K \) the \( n+1 \) round keys \( K^{1}, K^{2}, \dots, K^{n+1} \) where \( K^{i} \) is a certain permuted selection of bits from \( K \).

The AES encryption algorithm \( E_{K} \), as illustrated in Figure 1, executes the following steps:

  1. First is the plaintext \( m \) (a 128-bit block) converted into a state \( s \) (a 128-bit block) and the state \( s \) is XORed with the first round key \( K^{1} \) using the addRoundKey operation.
  2. Then are the operations subBytes, shiftRows, mixColumns and addRoundKey executed \( n-1 \) times on the state \( s \) where the round key \( K^{i} \) is used in the \( i \)-th round.
  3. Next are the operations subBytes, shiftRows and addRoundKey executed on the state \( s \) (notice that it's the same operations as in step (2) except the mixColumns operation) where addRoundKey XOR the state and the last round key \( K^{n+1} \). Finally is the state \( s \) converted into the ciphertext \( c \) (a 128-bit block).

The AES decryption algorithm \( D_{K} \), as illustrated in Figure 2, is the encryption algorithm executed in reverse order (with the round keys used in reverse order). And hence, all the used operations in the decryption algorithm are the inverse operations of the encryption algorithm where addRoundKey is its own inverse. \( D_{K} \) executes the following steps:

  1. First is the ciphertext \( c \) (a 128-bit block) converted into a state \( s \) (a 128-bit block) and the state \( s \) is XORed with the last round key \( K^{n+1} \) using the addRoundKey operation.
  2. Then are the operations shiftRowsInv, subBytesInv, addRoundKey and mixColumnsInv executed \( n-1 \) times on the state \( s \) where the round key \( K^{i} \) is used in the \( i \)-th round.
  3. Next are the operations shiftRowsInv, subBytesInv and addRoundKey executed on the state \( s \) (notice that it's the same operations as in step (2) except the mixColumnsInv operation) where addRoundKey XOR the state and the first round key \( K^{1} \). Finally is the state \( s \) converted into the plaintext \( m \) (a 128-bit block).
Figure 1: The AES encryption algorithm \( E_{K} \)
Figure 2: The AES decryption algorithm \( D_{K} \)

The state operation converts the 128-bit input block \( x \) (the plaintext \( m \) in the encryption algorithm and the ciphertext \( c \) in the decryption algorithm) into the state matrix \( s \) as illustrated in Figure 3. The state matrix consists of four rows and four columns where each entry represents 1 byte (8 bits), i.e. the 16 bytes (128 bits) input block \( x \) is divided into the 16 blocks \( s_{1}, s_{2}, \dots, s_{16} \) each of 1 byte (8 bits).

We also needs the inverse operation stateInv as illustrated in Figure 4 where the state matrix \( s \) is converted into the 128-bit output block \( y \) (the ciphertext \( c \) in the encryption algorithm and the plaintext \( m \) in the decryption algorithm), i.e. \( y = s_{1} \| s_{2} \| \cdots \| s_{16} \) where \( \| \) is the concatenation operator.

Figure 3: The \( state \) operation
Figure 4: The \( stateInv \) operation

The addRoundKey operation as illustrated in Figure 5 XOR the 128-bit state \( s \) with the current 128-bit round key \( K^{i} \). One property of the XOR operator is that it's its own inverse.

Figure 5: The \( addRoundKey \) operation

The subBytes operation substitutes each entry in the state matrix \( s \) with a value from the S-box \( S \) where Figure 6 illustrates the case for the first entry \( s_{1} \). Because each entry in the state matrix \( s \) represents 1 byte (8 bits) they can be converted into a two digit hexadecimal number where the first digit represents a row in the S-box and the second digit represents a column in the S-box. The output of the subBytes operation is then the chosen entry in the S-box.

The S-box \( S \) (see below) is a look-up table with 16 rows and 16 columns where each row is a permutation of hexadecimal numbers. Compared to the eight S-boxes in DES which are "randomly" permutation of the integers between 0 and 15 (the permutations were chosen to prevent certain types of attacks, especially a method called differential cryptanalysis), the entries in the single AES S-box are defined accordingly to operations in the group of polynomials \( \mathbb{F}_{2^{8}}[X] \). This group is also sometimes referred to as the Galois field and denoted by \( GF(2^{8}) \).

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

To clarify the use of the S-box we give an example: Assume we are given the entry \( s_{1} = a8 \). The hexadecimal number \( a \) represents a row and \( 8 \) represents a column in the S-box \( S\). The entry \( a8 \) in the S-box is the hexadecimal number \( 5c \), i.e. \( S(s_{1}) = S(a8) = 5c \).

During decryption is the inverse S-box \( S^{-1} \) used in the operation subBytesInv as illustrated in Figure 7, which correspond to the inverse operations in the group \( \mathbb{F}_{2^{8}}[X] \).

Figure 6: The \( subBytes \) operation during encryption
Figure 7: The \( subBytesInv \) operation during decryption

The shiftRows operation shifts the second row one time to the left, the third row two times to the left and the fourth row three times to the left as illustrated in Figure 8. The inverse operation shiftRowsInv illustrated in Figure 9 makes the same shifts to the opposite side, i.e. the second row is shifted one time to the right, the third row two times and the fourth row three times.

Figure 8: The \( shiftRows \) operation during encryption
Figure 9: The \( shiftRowsInv \) operation during decryption

The mixColumns operation multiply each column in the state matrix \( s \) with a fixed matrix \( M \), i.e. we treat the column and \( M \) as elements (polynomials) from the group \( \mathbb{F}_{2^{8}}[X] \) and multiply them. Figure 10 illustrates the case with the first column. The group \( \mathbb{F}_{2^{8}}[X] \) is the same as the one describe above during the S-box. In the inverse operation mixColumnsInv is the inverse matrix \( M^{-1} \) used (Figure 11 illustrates the case with the first column).

Figure 10: The \( mixColumns \) operation during encryption
Figure 11: The \( mixColumnsInv \) operation during decryption
The protocol
Key exchange
Alice and Bob agree on the 128-, 192-, or 256-bit key \( K \).
Encryption
Alice:
Uses the key \( K \) in the key schedule to generate the \( n+1 \) 128-bit round keys \( K^{1}, K^{2}, \dots, K^{n+1} \) where \( n = 10 \) if \( K \) is 128-bit, \( n = 12 \) if \( K \) is 192-bit and \( n = 14 \) if \( K \) is 256-bit.
Uses the round keys in the order \( K^{1}, K^{2}, \dots, K^{n+1} \) in the AES encryption algorithm \( E_{K} \) to encrypt the message \( m \) by \( c = E_{K}(m) \).
Alice sends the 128-bit ciphertext \( c \) to Bob.
Decryption
Bob:
Uses the key \( K \) in the key schedule to generate the \( n+1 \) 128-bit round keys \( K^{1}, K^{2}, \dots, K^{n+1} \) where \( n = 10 \) if \( K \) is 128-bit, \( n = 12 \) if \( K \) is 192-bit and \( n = 14 \) if \( K \) is 256-bit.
Uses the round keys in the reverse order \( K^{n+1}, K^{n}, \dots, K^{1} \) in the AES decryption algorithm \( D_{K} \) to decrypt the ciphertext \( c \) by \( m = D_{K}(c) \).

Try a demo of the encryption scheme here.

Example

In the following example we will write the keys, plaintext and ciphertext in hexadecimal notation. Remember that the hexadecimal digits \( 0, 1, \dots, 9, a, b, \dots, f \) represents the decimal digits from 0 to 15. And each of these decimal digits can be written as four bits, e.g. the number 4 in binary is \( 0100 \) and 15 is \( 1111 \). I.e. we can convert four bits to one hexadecimal digit which implies that for 128 bits we need 32 hexadecimal digits, for 192 bits we need 48 and for 256 bits we need 64.

Alice wants to send an encrypted message \( m \) to Bob using the AES algorithm. They first agree on a 128-bit key \( K = 2b7e151628aed2a6abf7158809cf4f3c \) and both generates the \( n+1 = 10+1 = 11 \) 128-bit round keys with the key schedule:

\( \eqalign{ K^{1} &= 2b7e151628aed2a6abf7158809cf4f3c \\ K^{2} &= a0fafe1788542cb123a339392a6c7605 \\ &\vdots \\ K^{11} &= d014f9a8c9ee2589e13f0cc8b6630ca6 } \)

Alice then encrypts the 128-bit message \( m = 3243f6a8885a308d313198a2e0370734 \) using the round keys in the order \( K^{1}, K^{2}, \dots K^{11} \) and sends the 128-bit ciphertext \( c = E_{K}(m) = 3925841d02dc09fbdc118597196a0b32 \) to Bob.

Bob decrypts the received ciphertext with the round keys in the reverse order \( K^{11}, K^{10}, \dots K^{1} \) by computing \( m = D_{K}(c) = 3243f6a8885a308d313198a2e0370734 \).