Skip to content

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

1 Commit

Folders and files

NameName
Last commit message
Last commit date
 
 
 
 
 
 

Repository files navigation

AES-128 Key Expansion — Software Reference Model

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.


1. What problem is this solving?

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.


2. The core recurrence (FIPS-197, §5.2)

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.


3. Mapping the algorithm onto the C code

3.1 Packing the key into words

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.

3.2 RotWord — rotate

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.

3.3 SubWord — substitute

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

3.4 Rcon — round constant XOR

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.

3.5 The "every 4th word" branch

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 with W[i-4].

This observation matters a lot for hardware: it tells you exactly what state you must keep alive across cycles (see §4).


4. Why this matters before writing RTL

A few things fall directly out of the algorithm and should shape the hardware architecture, before any Verilog/VHDL is written:

  1. It's inherently sequential, not parallel. W[i] depends on W[i-1] and W[i-4]. You cannot compute round n's key without already having round n-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.

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

  3. 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 for SubBytes. Sharing one S-box block between key expansion and the cipher data path is a very common area optimization.

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

  5. Indexing (i % 4, i / 4) becomes a small round counter in hardware, not a divide/modulo. Since Nk = 4 is fixed for AES-128, i % 4 == 0 is just "are we on the first word of a new round" — a 2-bit counter wrapping every 4 cycles — and i / 4 is the round number, a simple counter that increments once every 4 words.


5. Validating correctness

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.


6. Summary

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.

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages