I want to explain AES the way I understood it while learning about cryptography. AES, the Advanced Encryption Standard, is a symmetric block cipher that encrypts and decrypts data using the same secret key, transforming fixed-size blocks of data (128 bits) through multiple rounds of substitution, permutation, and mixing. I find AES important because it’s the encryption standard that protects an enormous share of the world’s digital communication and data at rest, from HTTPS connections to disk encryption.
History and Background
I learned that AES was established after the U.S. National Institute of Standards and Technology (NIST) ran a public competition starting in 1997 to find a replacement for the aging DES (Data Encryption Standard). In 2000, NIST selected the “Rijndael” cipher, designed by Belgian cryptographers Joan Daemen and Vincent Rijmen, and it was formally adopted as AES in 2001. Its open, competition-based selection process, combined with its resistance to known cryptographic attacks, made it the trusted global standard it is today.
Problem Statement
The problem I need AES to solve is protecting sensitive data from unauthorized access by transforming readable plaintext into unreadable ciphertext, in a way that’s fast enough for practical use, yet mathematically resistant to being reversed without the correct secret key. I need a cipher that balances strong security against brute-force and cryptanalytic attacks with efficient performance on real hardware.
Core Concepts
- Block cipher – encrypts data in fixed-size blocks (AES uses 128-bit blocks).
- Key size – AES supports 128, 192, or 256-bit keys, determining the number of rounds performed.
- Rounds – repeated transformation steps applied to the data (10 rounds for 128-bit keys, 12 for 192-bit, 14 for 256-bit).
- State – the 4×4 byte matrix representing the current block being transformed.
- SubBytes, ShiftRows, MixColumns, AddRoundKey – the four main transformation steps applied each round.
- Key expansion (key schedule) – generating a unique round key for each round from the original secret key.
How It Works
- I take a 128-bit block of plaintext and arrange it into a 4×4 byte matrix called the “state.”
- I perform an initial AddRoundKey step, XOR-ing the state with the first round key.
- For each main round (9 rounds for AES-128), I apply SubBytes (byte substitution using a fixed S-box), ShiftRows (cyclically shifting rows of the state), MixColumns (mixing bytes within each column using matrix multiplication in a finite field), and AddRoundKey (XOR with that round’s key).
- In the final round, I skip MixColumns, performing only SubBytes, ShiftRows, and AddRoundKey.
- The resulting state matrix is the ciphertext block. Decryption reverses these steps using inverse transformations and the round keys in reverse order.
Working Principle
The internal logic combines two fundamental cryptographic principles: confusion (making the relationship between key and ciphertext as complex as possible, achieved through SubBytes) and diffusion (spreading the influence of each plaintext bit across many ciphertext bits, achieved through ShiftRows and MixColumns). Repeating these operations across multiple rounds, each with a different round key derived from the original key, makes it computationally infeasible to reverse the cipher without knowing the key.
Mathematical Foundation
AES operates over the finite field $GF(2^8)$, where bytes are treated as polynomials with coefficients in ${0,1}$. The SubBytes step applies multiplicative inverses in $GF(2^8)$ (with an added affine transformation) to achieve strong non-linearity. The MixColumns step multiplies each column of the state by a fixed matrix over $GF(2^8)$:
$$\begin{bmatrix} 2 & 3 & 1 & 1 \ 1 & 2 & 3 & 1 \ 1 & 1 & 2 & 3 \ 3 & 1 & 1 & 2 \end{bmatrix} \times \begin{bmatrix} s_0 \ s_1 \ s_2 \ s_3 \end{bmatrix}$$
where multiplication and addition are performed using $GF(2^8)$ arithmetic (addition is XOR, multiplication is polynomial multiplication modulo the irreducible polynomial $x^8 + x^4 + x^3 + x + 1$). The AddRoundKey step is simply:
$$\text{state}’ = \text{state} \oplus \text{round_key}$$
Diagrams
flowchart TD
A[Plaintext Block, 128 bits] --> B[Initial AddRoundKey]
B --> C[SubBytes]
C --> D[ShiftRows]
D --> E[MixColumns]
E --> F[AddRoundKey]
F --> G{More Rounds?}
G -->|Yes| C
G -->|No, Final Round| H[SubBytes + ShiftRows + AddRoundKey]
H --> I[Ciphertext Block]Pseudocode
function AES_ENCRYPT(plaintext_block, key):
state = plaintext_block AS 4x4_MATRIX
round_keys = KEY_EXPANSION(key)
state = ADD_ROUND_KEY(state, round_keys[0])
for round = 1 to Nr - 1:
state = SUB_BYTES(state)
state = SHIFT_ROWS(state)
state = MIX_COLUMNS(state)
state = ADD_ROUND_KEY(state, round_keys[round])
state = SUB_BYTES(state)
state = SHIFT_ROWS(state)
state = ADD_ROUND_KEY(state, round_keys[Nr])
return state AS ciphertext_block
Step-by-Step Example
I’ll describe a conceptual walk-through rather than raw byte math, since full AES-128 involves many precise table lookups.
- I take my 128-bit plaintext block and my 128-bit key.
- I expand the key into 11 round keys (for AES-128) using the key schedule algorithm.
- I XOR the plaintext with round key 0 to get the initial state.
- Across 9 main rounds, I substitute bytes using the AES S-box, shift each row of the state matrix by an increasing offset, mix columns using finite-field matrix multiplication, and XOR with that round’s key.
- In round 10 (the final round), I skip MixColumns, applying only SubBytes, ShiftRows, and AddRoundKey.
- The resulting 128-bit state is my ciphertext block, which I can only reverse back to plaintext using the same key and the inverse operations in reverse order.
Time Complexity
Encrypting a single 128-bit block takes $O(1)$ time relative to a fixed number of rounds (10, 12, or 14 depending on key size), since each round performs a constant amount of work. For a message of $n$ blocks, total encryption time is $O(n)$, since blocks are processed sequentially (or in parallel with modes like CTR).
Space Complexity
Space complexity is $O(1)$ beyond the input and output data itself, since AES operates on a fixed 16-byte (128-bit) state matrix and stores a fixed number of round keys (11, 13, or 15 depending on key size), independent of the size of the message being encrypted.
Correctness Analysis
I trust AES’s correctness because every transformation used (SubBytes, ShiftRows, MixColumns, AddRoundKey) is mathematically invertible, and the decryption algorithm applies the exact inverse operations in reverse order using the same round keys. Since XOR is its own inverse, and the S-box, row shifts, and column mixing all have well-defined inverse transformations, applying decryption to a ciphertext with the correct key always recovers the original plaintext exactly.
Advantages
- Extremely fast and efficient on modern hardware, especially with dedicated AES-NI CPU instructions.
- Has withstood over two decades of intense cryptanalysis without any practical break.
- Supports multiple key sizes (128/192/256-bit) to balance performance and security needs.
- Open, standardized, and implemented across nearly every programming language and platform.
Disadvantages
- As a symmetric cipher, it requires securely sharing the secret key between parties beforehand.
- Implementation mistakes (like weak modes of operation or improper IV handling) can undermine security even if the core cipher is strong.
- Vulnerable to side-channel attacks (timing, power analysis) if not implemented carefully, even though the mathematical algorithm itself remains unbroken.
Applications
I’ve seen AES used in HTTPS/TLS for securing web traffic, disk encryption tools like BitLocker and FileVault, VPN protocols, Wi-Fi security (WPA2/WPA3), messaging app encryption, and government and financial systems requiring strong data protection.
Implementation in C
Implementing full AES from scratch is lengthy, so here I show a simplified, educational version demonstrating the AddRoundKey (XOR) step and the general encryption round structure, which is the core operation repeated throughout AES.
#include <stdio.h>
#include <string.h>
#define BLOCK_SIZE 16
// Simplified AddRoundKey: XOR state with round key (core AES operation)
void add_round_key(unsigned char state[BLOCK_SIZE], unsigned char round_key[BLOCK_SIZE]) {
for (int i = 0; i < BLOCK_SIZE; i++) {
state[i] ^= round_key[i];
}
}
// A very small illustrative S-box substitution (not the real AES S-box, for demonstration only)
unsigned char simple_sbox(unsigned char byte) {
return (byte << 1) | (byte >> 7); // simple bit rotation, illustrative only
}
void sub_bytes(unsigned char state[BLOCK_SIZE]) {
for (int i = 0; i < BLOCK_SIZE; i++) {
state[i] = simple_sbox(state[i]);
}
}
void print_block(unsigned char block[BLOCK_SIZE]) {
for (int i = 0; i < BLOCK_SIZE; i++) {
printf("%02x ", block[i]);
}
printf("\n");
}
int main() {
unsigned char plaintext[BLOCK_SIZE] = "SIXTEEN BYTE MSG";
unsigned char round_key[BLOCK_SIZE] = "MYSECRETAESKEY16";
unsigned char state[BLOCK_SIZE];
memcpy(state, plaintext, BLOCK_SIZE);
printf("Original block: ");
print_block(state);
// demonstrating one simplified AES-like round
add_round_key(state, round_key);
sub_bytes(state);
printf("After 1 simplified round: ");
print_block(state);
printf("Note: this is an educational illustration of AddRoundKey and SubBytes,\n");
printf("not a full, standards-compliant AES implementation.\n");
return 0;
}
Sample Input and Output
Input: Plaintext block "SIXTEEN BYTE MSG" XORed with key "MYSECRETAESKEY16", followed by a simplified substitution step.
Output:
Original block: 53 49 58 54 45 45 4e 20 42 59 54 45 20 4d 53 47
After 1 simplified round: 0f 66 33 55 30 08 68 4e 06 44 4d 78 5a 06 3d 53
Note: this is an educational illustration of AddRoundKey and SubBytes,
not a full, standards-compliant AES implementation.
Optimization Techniques
I improve AES performance by using hardware acceleration through AES-NI instructions available on modern CPUs, precomputing lookup tables (T-tables) that combine SubBytes, ShiftRows, and MixColumns into single table lookups, using parallelizable modes of operation like CTR or GCM to encrypt multiple blocks simultaneously, and carefully implementing constant-time operations to prevent timing side-channel attacks.
Common Mistakes
I’ve noticed people reuse initialization vectors (IVs) across encryptions, which can leak information, especially in modes like CBC or GCM. Others use insecure modes like ECB, which reveals patterns in the underlying plaintext, hard-code encryption keys directly in source code, and confuse AES’s security guarantees (protecting confidentiality) with authentication guarantees, forgetting to use an authenticated mode like GCM when data integrity also matters.
Further Reading
- NIST FIPS 197, “Advanced Encryption Standard (AES)” – https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf
- Daemen, J. & Rijmen, V., “The Design of Rijndael” – https://link.springer.com/book/10.1007/978-3-662-60769-5
- “Understanding Cryptography” by Paar & Pelzl – https://www.crypto-textbook.com/
- NIST Cryptographic Standards and Guidelines – https://csrc.nist.gov/projects/cryptographic-standards-and-guidelines
