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

The math and definitions explained

Until 1999, the Data Encryption Standard (DES) served as the standard algorithm for encryption. However, due to its relatively short 56-bit keys and 64-bit blocks, NIST (the National Institute of Standards and Technology) began the process of selecting a replacement, which became known as the Advanced Encryption Standard (AES).

NIST established an open competition with specific requirements: AES must use 128-bit blocks and support keys of 128, 192, and 256 bits. Initially, in 1998, 21 cryptosystems were submitted, of which 15 met all the necessary criteria and advanced as AES candidates. In 1999, NIST narrowed the field to five finalists: MARS, RC6, Rijndael, Serpent, and Twofish. These were evaluated according to three criteria: security, efficiency (in both hardware and software implementations), and ease of implementation. While all finalists were considered secure, and none excelled in all three criteria, Rijndael demonstrated the best overall balance and was announced as the AES winner in 2000. The Rijndael cipher, developed by Belgian cryptographers Joan Daemen and Vincent Rijmen, was officially adopted as a standard in 2001, replacing DES.

AES is an iterated cipher that processes plaintexts and ciphertexts of 128 bits, where Alice and Bob use the same 128-, 192-, or 256-bit key \( K \) for both encryption and decryption. Because both parties use identical keys, AES is classified as a symmetric key cryptosystem. For example, Alice can securely transmit the key to Bob using an asymmetric cryptosystem such as RSA or ElGamal. The reason symmetric key cryptosystems are used, even though an asymmetric cryptosystem is needed to exchange the key, is that symmetric systems operate significantly faster than asymmetric cryptosystems.

A fundamental distinction between the following description of AES and asymmetric cryptosystems is that AES operates with bits and bitwise operations rather than integers and arithmetic operations. As a result, plaintexts and ciphertexts in symmetric cryptosystems are often referred to as blocks because they consist of bitstrings.

AES resembles DES in that it repeatedly executes a series of basic operations during encryption and decryption. The specific operations used in AES are: state, addRoundKey, subBytes, shiftRows, and mixColumns (each described in detail below). If the key \( K \) is 128 bits, AES performs 10 rounds (iterations); a 192-bit key requires 12 rounds, and a 256-bit key requires 14 rounds. We denote the number of rounds as \( n \), meaning \( n = 10 \), \( n = 12 \), or \( n = 14 \) depending on the key length.

As we will explain later, AES employs the addRoundKey operation \( n+1 \) times, which XORs two 128-bit strings: the current state \( s \) (described below) and the current round key \( K^{i} \). However, as previously mentioned, Alice and Bob initially agree on only a single 128-, 192-, or 256-bit key \( K \). To address this requirement, they use a key schedule that derives from the key \( K \) the \( n+1 \) round keys \( K^{1}, K^{2}, \dots, K^{n+1} \), where each \( K^{i} \) represents a specific permuted selection of bits from \( K \).

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

1. First, the plaintext \( m \) (a 128-bit block) is 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, the operations subBytes, shiftRows, mixColumns, and addRoundKey are executed \( n-1 \) times on the state \( s \), where the round key \( K^{i} \) is used in the \( i \)-th round.
3. Next, the operations subBytes, shiftRows, and addRoundKey are executed on the state \( s \) (note that these are the same operations as in step (2), except that the mixColumns operation is omitted), where addRoundKey XORs the state with the last round key \( K^{n+1} \). Finally, the state \( s \) is 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). All operations in the decryption algorithm are the inverse operations of those in the encryption algorithm, except for addRoundKey, which is its own inverse. \( D_{K} \) executes the following steps:

1. First, the ciphertext \( c \) (a 128-bit block) is 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, the operations shiftRowsInv, subBytesInv, addRoundKey, and mixColumnsInv are executed \( n-1 \) times on the state \( s \), where the round key \( K^{i} \) is used in the \( i \)-th round.
3. Next, the operations shiftRowsInv, subBytesInv, and addRoundKey are performed on the state \( s \) (note that these are the same operations as in step (2), except that the mixColumnsInv operation is omitted). Here, addRoundKey XORs the state with the first round key \( K^{1} \). Finally, the state \( s \) is converted back into the plaintext \( m \) (a 128-bit block).

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

The inverse operation, stateInv, is illustrated in Figure 4. In this process, the state matrix \( s \) is converted back into the 128-bit output block \( y \) (the ciphertext \( c \) in the encryption algorithm or the plaintext \( m \) in the decryption algorithm). This conversion is represented as \( y = s_{1} \| s_{2} \| \cdots \| s_{16} \), where \( \| \) denotes the concatenation operator.

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

The subBytes operation substitutes each entry in the state matrix \( s \) with a corresponding value from the S-box \( S \), as Figure 6 demonstrates for the first entry \( s_{1} \). Since each entry in the state matrix \( s \) represents 1 byte (8 bits), it can be expressed as a two-digit hexadecimal number. The first digit identifies a row in the S-box, and the second digit identifies a column. The output of the subBytes operation is the value located at that specific position in the S-box.

The S-box \( S \) (shown below) is a lookup table with 16 rows and 16 columns, where each row contains a permutation of hexadecimal numbers. Unlike the eight S-boxes in DES, which featured "random" permutations of integers from 0 to 15 (carefully selected to resist specific types of attacks, particularly differential cryptanalysis), the entries in the single AES S-box are mathematically defined according to operations in the polynomial group \( \mathbb{F}_{2^{8}}[X] \). This mathematical structure is also commonly 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 with an example: Suppose we have the entry \( s_{1} = a8 \). The hexadecimal digit \( a \) identifies the row, while \( 8 \) identifies the column in the S-box \( S \). The value at this intersection is the hexadecimal number \( 5c \), so \( S(s_{1}) = S(a8) = 5c \).

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

The shiftRows operation shifts the second row one position to the left, the third row two positions to the left, and the fourth row three positions to the left, as illustrated in Figure 8. The inverse operation, shiftRowsInv (illustrated in Figure 9), applies the same shifts but in the opposite direction: the second row shifts one position to the right, the third row shifts two positions to the right, and the fourth row shifts three positions to the right.

The mixColumns operation multiplies each column in the state matrix \( s \) with a fixed matrix \( M \). In this process, both the column and \( M \) are treated as elements (polynomials) from the group \( \mathbb{F}_{2^{8}}[X] \) and multiplied accordingly. Figure 10 illustrates this operation for the first column. The group \( \mathbb{F}_{2^{8}}[X] \) is the same mathematical structure described earlier in the S-box section. In the inverse operation mixColumnsInv, the inverse matrix \( M^{-1} \) is used instead (as illustrated for the first column in Figure 11).

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 computing \( 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 computing \( m = D_{K}(c) \).

Try a demo of the encryption scheme here.

Example

In the following example, we present keys, plaintext, and ciphertext using hexadecimal notation. Recall that hexadecimal digits \( 0, 1, \dots, 9, a, b, \dots, f \) correspond to decimal values from 0 to 15. Each of these decimal values can be represented as four binary bits; for example, the decimal number 4 in binary is \( 0100 \) and 15 is \( 1111 \). Since four bits convert to one hexadecimal digit, a 128-bit value requires 32 hexadecimal digits, a 192-bit value requires 48 hexadecimal digits, and a 256-bit value requires 64 hexadecimal digits.

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

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

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

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