1. Home
2. The AES cryptosystem
3. The protocol explained

The math and definitions 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).

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.

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.

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] \).

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.

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

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 \).