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

The math and definitions explained

Historical Background

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

Historical timeline:

• 1997: NIST announces competition for AES
• 1998: 21 algorithm submissions received
• 1999: 15 submissions advance as AES candidates
• 2000: Rijndael selected as the winner
• 2001: NIST publishes AES as FIPS 197 standard
• 2003: U.S. government approves AES for classified information
• 2001-Present: No practical cryptanalytic attacks discovered

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.

Key AES Properties:

• Block size: 128 bits
• Key sizes: 128, 192, or 256 bits
• Rounds: 10 (128-bit key), 12 (192-bit key), or 14 (256-bit key)
• Structure: Substitution-permutation network
• Core operations: SubBytes (substitution), ShiftRows (permutation), MixColumns (mixing), AddRoundKey (key addition)
• Mathematical foundation: Operations in finite field GF(2^8)

AES Block & Algorithm Structure

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

Key Schedule

As explained earlier, AES employs the addRoundKey operation \( n+1 \) times, which XORs the current state \( s \) with the current round key \( K^{i} \). However, 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 \).

Core AES Operations

The State Representation

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

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

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

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

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

Encryption and Decryption Process

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+1} \) is used in the \( i \)-th round (for \( i = 1, 2, \ldots, n-1 \)).
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^{n-i+1} \) is used in the \( i \)-th round (for \( i = 1, 2, \ldots, n-1 \)).
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).

Security Properties

AES is considered highly secure for the following reasons:

• Key Length: AES supports 128, 192, and 256-bit keys, making brute force attacks computationally infeasible.
• Confusion: The SubBytes operation provides strong non-linearity.
• Diffusion: The ShiftRows and MixColumns operations ensure that changes to one byte affect many bytes in subsequent rounds.
• Resistance to Known Attacks: AES has withstood extensive cryptanalysis for over two decades.

The best known attacks against AES are still largely theoretical and require computational resources far beyond what is currently possible.

Practical Applications

AES is widely used in various applications and protocols:

• TLS/SSL: Securing web communications
• File Encryption: Protecting sensitive documents
• Wi-Fi Security: WPA2/WPA3 protocols
• VPN Technologies: Securing private network communications

Common AES modes of operation include:

• ECB (Electronic Codebook): The simplest mode, but not recommended for most applications
• CBC (Cipher Block Chaining): Each block's encryption depends on the previous block's ciphertext
• CTR (Counter): Converts block cipher into stream cipher by encrypting sequential counter values
• GCM (Galois/Counter Mode): Provides both encryption and authentication

See the "Modes of operation" page for more information.

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