This repository contains a C "golden model" of the AES-128 Key Expansion (Key Schedule) algorithm, written before the hardware implementation. The goal of this document is not to describe the C code line-by-line, but to nail down the algorithm itself — the data flow, the math, and the state that has to exist at any given moment — so that translating it into RTL is a mechanical exercise rather than a discovery process.
AES doesn't encrypt with a single key. It encrypts with a sequence of
round keys, one per round (plus one extra for the initial AddRoundKey
before round 1). Key Expansion is the algorithm that takes the
original cipher key and deterministically expands it into all the round
keys needed for the full encryption (or decryption) process.
For AES-128:
| Parameter | Symbol | Value | Meaning |
|---|---|---|---|
| Key length (words) | Nk |
4 | Original key is 4 × 32-bit words (128 bits) |
| Block size (words) | Nb |
4 | Each round key is also 4 × 32-bit words |
| Number of rounds | Nr |
10 | AES-128 has 10 rounds |
| Total words generated | Nb·(Nr+1) |
44 | One 4-word round key for rounds 0–10 |
So the entire output of key expansion is an array of 44 32-bit words,
W[0..43]. W[0..3] is just the original key. Every block of 4
consecutive words after that (W[4..7], W[8..11], …, W[40..43]) is the
round key for round 1, 2, … 10.
This is exactly what Keyexpansion() in main.c computes and prints.
For i from 4 to 43:
if i mod Nk == 0:
W[i] = W[i-4] XOR ( SubWord( RotWord( W[i-1] ) ) XOR Rcon[i/Nk] )
else:
W[i] = W[i-4] XOR W[i-1]
That's the entire algorithm. Everything else in the code exists only to implement these three building blocks:
RotWord— a cyclic left rotation of a 4-byte word by one byte.SubWord— apply the AES S-Box to each of the 4 bytes independently.Rcon— XOR only the most significant byte of the word with a round-dependent constant.
The "every 4th word is special" rule is the only branch in the whole
algorithm, and it exists because Nk == Nb == 4 for AES-128 — the
special transformation runs once per round, on the last word of the
previous round key, to "kick off" the next round key.
W[0] = (w[0] << 24) | (w[1] << 16) | (w[2] << 8) | w[3];The original key arrives as 16 bytes (w[0..15]). AES treats data as
big-endian 32-bit words — byte 0 is the most significant byte of the
word. This packing step is just a byte-to-word reshape; it carries no
cryptographic meaning, but it's the layout every later step assumes.
uint8_t temp = w[0];
w[0]=w[1]; w[1]=w[2]; w[2]=w[3]; w[3]=temp;Takes bytes [b0,b1,b2,b3] → [b1,b2,b3,b0]. In hardware this is free
— it's a wire reordering, not logic. No gates, no LUTs, just rewiring
which byte lane feeds which S-box input.
for (int i = 0; i < 4; i++) w[i] = sbox[w[i]];Each byte is independently looked up in the 256-entry AES S-Box. In hardware, this is 4 parallel 8-bit → 8-bit lookups. The S-box can be implemented as a ROM/LUT (most common for FPGA) or as combinational logic built from the underlying GF(2⁸) inverse + affine transform (used when minimizing area on ASICs, at the cost of more logic levels).
w[0] = w[0] ^ rcon[round_index];Only the top byte of the word is XORed with a constant that depends
on the round number (round_index = i/4). The rcon[] table in the code
is precomputed — these are successive powers of x (i.e. 0x02) in
AES's GF(2⁸) field. In hardware you'd typically store this as a small
constant ROM indexed by round number, same as in the C model — there's no
reason to recompute it on the fly.
if (i % 4 == 0) {
// copy W[i-1] into bytes, RotWord -> SubWord -> Rcon, repack
temp_arr = mutated_word ^ W[i-4];
} else {
temp_arr = W[i-1] ^ W[i-4];
}
W[i] = temp_arr;This is the recurrence from §2, implemented exactly. Note structurally:
- Every word needs
W[i-4](the word from one round key ago). - Every 4th word additionally needs
W[i-1]passed through Rotate → Sub → Rcon. - The other three words in a round key just need
W[i-1]directly, XORed withW[i-4].
This observation matters a lot for hardware: it tells you exactly what state you must keep alive across cycles (see §4).
A few things fall directly out of the algorithm and should shape the hardware architecture, before any Verilog/VHDL is written:
-
It's inherently sequential, not parallel.
W[i]depends onW[i-1]andW[i-4]. You cannot compute roundn's key without already having roundn-1's key. This naturally suggests an iterative datapath: one round key computed per clock (or per few clocks), reusing the same Rotate/Sub/Rcon hardware each round, rather than 10 copies of the round-key logic unrolled in space. -
Only one word per round actually needs the expensive path. Of the 4 words generated per round, only the first goes through RotWord → SubWord → Rcon. The other 3 are a single XOR. So you only need one S-box instance (4 parallel byte-lookups) per key-expansion round, not four — a meaningful area saving if you're tight on LUTs/ROM.
-
The S-box is the only "real" combinational logic. RotWord is just wiring. Rcon is a constant XOR. The XOR-with-
W[i-4]is trivial. SubWord (the S-box) is the one block worth thinking about as a separate, reusable, possibly shared hardware unit — especially since the AES data path (if you're building a full AES core, not just key expansion) also needs an S-box forSubBytes. Sharing one S-box block between key expansion and the cipher data path is a very common area optimization. -
Minimal state needed. You don't need to store all 44 words at once if you're streaming round keys out as they're produced. You only ever need the last 4 words (
W[i-4..i-1]) to compute the next one. That's 128 bits of register state, not 44×32 = 1408 bits — relevant if area/registers are scarce. -
Indexing (
i % 4,i / 4) becomes a small round counter in hardware, not a divide/modulo. SinceNk = 4is fixed for AES-128,i % 4 == 0is just "are we on the first word of a new round" — a 2-bit counter wrapping every 4 cycles — andi / 4is the round number, a simple counter that increments once every 4 words.
The key used in this code,
2b7e151628aed2a6abf7158809cf4f3c
is the standard AES-128 test key from FIPS-197, Appendix A.1. This is
intentional and useful: the expected round keys for this exact key are
published in the spec, so the printed output of Keyexpansion() can be
checked byte-for-byte against a known-good reference before any of this
logic is translated to hardware. Doing that check now, in software, is
far cheaper than debugging a mismatch after it's in RTL and simulation.
Suggested next step: before writing the hardware, diff the program's
printed W[i] values against the FIPS-197 Appendix A.1 table for all 44
words. Only move to RTL once that matches exactly.
| Algorithm step | Hardware nature | Notes |
|---|---|---|
| Pack key into words | Wiring / reshape | No logic |
RotWord |
Wiring | Byte-lane reorder, zero gates |
SubWord |
ROM/LUT or combinational logic | 4× 8-bit S-box lookups |
Rcon |
Constant XOR | Small constant ROM indexed by round |
W[i-4] XOR (...) |
XOR gates | 32-bit XOR, every word |
| Overall structure | Iterative / sequential | One round key per "tick"; reuse one S-box |
| State to retain | 128 bits | Just the last 4 words, not the full 44 |
This C model exists to pin down exactly this data flow with a working, testable reference before committing to a clocked design.