有限域乘法核心解析)
如果你已经开始用 C 语言写 AES多半会遇到这样一个阶段SubBytes 查表简单AddRoundKey 就是异或甚至密钥扩展也能照猫画虎但一走到行移位和列混淆就开始怀疑人生。行移位还好说无非是把状态矩阵里的字节挪个位置列混淆就麻烦了矩阵乘法里出现的 2、3 这些系数对应的不是普通整数乘法而是在 GF(2^8) 有限域上的运算第一次接触的人很容易在这里卡住甚至代码能跑但结果和标准测试向量怎么都对不上。我见过不少初学者把 AES 当成一个“背代码”的练习实际上 AES 是特别适合拿来练 C 语言的综合项目要操作字节数组、处理二维索引、写位运算、做边界检查还要理解一点抽象代数。这篇文章不打算把 AES 的每个细节重新讲一遍而是聚焦在行移位和列混淆这两个环节把原理说透把 C 语言实现一步一步写清楚再分享我实际调试中踩过的那些坑。无论你是在做课程设计、嵌入式项目还是单纯想搞明白 FIPS 197 文档里那几张表格这篇文章都能用上。1. 先搞清楚AES整体架构行移位和列混淆到底在干嘛1.1 SPN结构和Feistel结构的区别AES 不是 Feistel 网络编译器里的“对称加密”大类下DES 一系的算法才是 Feistel 结构每轮只处理一半数据左半边和右半边通过轮函数互相搅和。AES 走的是完全不同的路线它属于代换-置换网络也就是 SPN 结构每一轮会把整个 128 位状态同时拿来做非线性代换和线性扩散所以轮函数里每一步都有明确分工。明白这个背景之后再看行移位和列混淆就不会觉得它们是“莫名其妙的两步”了。SPN 结构要成立必须同时满足两个条件一是要有非线性层这就是 SubBytes 做的事用 S 盒提供混淆二是要有线性扩散层让任何一位明文的改变能快速波及整个状态这就是 ShiftRows 和 MixColumns 的职责。很多初学者只记住了“AES 有四个步骤”却没有意识到这四个步骤其实是一个安全设计如果没有 ShiftRows 这种跨列操作状态矩阵的每一列永远只在自己列内变换攻击者完全可以把 16 字节分组拆成 4 个独立的 4 字节向量来分别处理AES 的强度会断崖式下降。用生活一点的话说SubBytes 像是给每个字节单独换了个马甲而 ShiftRows 和 MixColumns 是负责让整个队伍彻底打散重组。行移位把不同列之间的字节混在一起列混淆又把每一列内部的四个字节线性混合成新的四个字节两者配合起来才能达到“改一个位满盘皆变”的雪崩效应。这正是前两轮之后状态里的每一个输出字节都同时依赖几乎所有输入字节的原因。1.2 一轮完整流程和“扩散”的本质AES 一轮的标准顺序是AddRoundKey 先做一次轮密钥异或然后 SubBytes 逐字节代换ShiftRows 做行循环移位MixColumns 做列混合最后再执行一次 AddRoundKey。最后一轮比较特殊会把 MixColumns 去掉只保留 SubBytes、ShiftRows、AddRoundKey。很多人在写代码时把这四个步骤的顺序搞错尤其是把 AddRoundKey 和 SubBytes 的顺序记反结果就是中间状态对不上。这四个步骤在 AES 里的作用可以简单归类步骤类型作用AddRoundKey密钥相关将轮密钥异或进状态密钥由此进入分组运算SubBytes非线性代换S 盒逐字节替换提供混淆抵抗线性分析ShiftRows字节置换行移位让列与列之间产生交叉扩散MixColumns线性混合列混淆把一列内 4 字节混合成新的 4 字节需要注意ShiftRows 解决的是“列与列之间没有交流”的问题MixColumns 解决的是“同一列内字节之间没有混合”的问题。一套组合拳下来扩散既发生在列间也发生在列内AES 才能在两轮左右让雪崩效应铺满整个状态。2. 行移位实现索引搞清楚代码就成功了一半2.1 状态矩阵怎么存二维数组还是16字节AES 的状态矩阵永远是 4×4 字节用 C 语言实现时最常见也最直观的做法是声明成uint8_t state[4][4]把state[r][c]当成第 r 行第 c 列来用。FIPS 197 文档里描述状态时通常按列展开成一串字节比如输入的 16 字节会按“先列后行”的顺序填充第 1 个字节放到state[0][0]第 2 个字节放到state[1][0]第 3 个放到state[2][0]第 4 个放到state[3][0]第 5 个放到state[0][1]依此类推。也有不少人喜欢用一维数组uint8_t state[16]因为底层内存布局更直白而且和传入的明文缓冲区可以直接memcpy。在一维数组里state[4 * c r]就是第 r 行第 c 列的字节。两种方式没有本质区别但对行移位来说二维数组的可读性明显更好因为你一眼就能看出“第 1 行左移 1 位”是在做什么。嵌入式场景如果极其在意内存布局可以继续用一维数组但在函数内部定义一个static inline的访问宏避免到处写4 * c r导致索引算错。我自己的习惯是初学、验证算法阶段用二维数组上了项目、需要和硬件 AES 引擎对接时再改成连续缓冲区。原因很简单二维数组保留了矩阵语义打印调试时也直观不容易在行和列之间迷失方向。等逻辑完全跑通了再优化成一维布局成本很低。2.2 ShiftRows的C语言实现与验证行移位的规则一句话就能说清第 0 行不动第 1 行循环左移 1 字节第 2 行循环左移 2 字节第 3 行循环左移 3 字节。这里的“循环左移”指的是行内字节向列号增大的方向移动从列 3 出去的字节回到列 0。第 3 行左移 3 位其实等价于循环右移 1 位所以实现时可以少写几次赋值。直接给出一段可编译的 C 代码#include stdint.h void shift_rows(uint8_t s[4][4]) { uint8_t t; // 第1行循环左移1字节 t s[1][0]; s[1][0] s[1][1]; s[1][1] s[1][2]; s[1][2] s[1][3]; s[1][3] t; // 第2行循环左移2字节相当于交换列0-列2列1-列3 t s[2][0]; s[2][0] s[2][2]; s[2][2] t; t s[2][1]; s[2][1] s[2][3]; s[2][3] t; // 第3行循环左移3字节等价于循环右移1字节 t s[3][3]; s[3][3] s[3][2]; s[3][2] s[3][1]; s[3][1] s[3][0]; s[3][0] t; }这段代码手动展开了所有赋值因为 4×4 矩阵太小用两层 for 循环反而要引入取模运算和查表读起来也不如这种“平铺直叙”的方式直观。如果你喜欢通用写法可以用移位表static const uint8_t shift_r[4] {0, 1, 2, 3}; void shift_rows_generic(uint8_t s[4][4]) { uint8_t tmp[4]; for (int r 1; r 4; r) { for (int c 0; c 4; c) { tmp[c] s[r][(c shift_r[r]) % 4]; } for (int c 0; c 4; c) { s[r][c] tmp[c]; } } }如果你想验证代码对不对可以用手工可算的输入。假设初始状态是uint8_t state[4][4] { {0xdb, 0xf2, 0x01, 0x89}, {0x13, 0x0a, 0x01, 0x23}, {0x53, 0x22, 0x01, 0x45}, {0x45, 0x5c, 0x01, 0x67} };ShiftRows 之后第 1 行的13 0a 01 23变成0a 01 23 13第 2 行53 22 01 45变成01 45 53 22第 3 行45 5c 01 67变成67 45 5c 01第 0 行保持不变。这个小例子非常适合用来检查实现跑一遍代码对着看比直接上 FIPS 197 的标准向量容易定位多了。2.3 逆行移位与实现细节解密的时候需要 InvShiftRows方向正好反过来第 1 行循环右移 1 字节第 2 行循环右移 2 字节第 3 行循环右移 3 字节。代码只需要把shift_rows里每行的移动方向改一下即可这里就不再贴完整代码了只提醒一个容易被忽略的细节加密时第 1 行左移 1、第 3 行等价右移 1用的是“补位”的方式手工打开解密时第 1 行改右移、第 3 行改左移赋值方向要彻底反过来不能只改一半。另外一个和二维数组相关的 C 语言坑是函数参数退化。void shift_rows(uint8_t s[4][4])这种写法传入的其实是指向uint8_t[4]的指针所以定义成uint8_t state[4][4]后直接调用shift_rows(state)没问题。但如果你把状态定义成一维数组uint8_t state[16]再强行传给uint8_t s[4][4]形参编译器会警告类型不匹配运行时的列索引计算也会一塌糊涂。遇到这种切换不如干脆重新设计访问宏不要用强转硬塞。嵌入式平台如果不想用% 4运算通用版本可以写成(c shift_r[r]) 3因为 4 是 2 的整数次幂位与运算比取模快一点。不过现代编译器对除以常数 4 的取模通常也有优化非极端场景不需要刻意考虑。3. 列混淆实现GF(2^8)乘法是核心3.1 有限域乘法不是普通乘法xtime的来历列混淆是初学 AES 时最容易劝退的地方因为那个 4×4 矩阵里的 2 和 3看着像普通整数实际运算规则却完全不同。AES 把每个字节都当成一个以 0 和 1 为系数的多项式整个运算在 GF(2^8) 有限域上进行加法和减法都对应异或乘法则是多项式乘法再模一个不可约多项式m(x) x^8 x^4 x^3 x 1写成十六进制就是 0x11B。为什么要选这个多项式因为它是 AES 设计者精心挑选的不可约多项式可以保证域上的每一个非零元素都有逆元这是列混淆可逆、AES 能解密的数学基础。在 GF(2^8) 里乘以 2也就是乘上多项式 x可以这样理解把字节左移一位如果最高位是 1说明左移后出现了 x^8 项需要再异或 0x1B 做模约简。这个操作有一个专门的名字叫 xtime。C 语言实现特别短static uint8_t xtime(uint8_t x) { return (uint8_t)((x 1) ^ ((x 0x80) ? 0x1B : 0x00)); }先取出最高位判断是否溢出再决定要不要异或 0x1B。要注意的一点是x 1在 C 语言里会先被提升成 int 类型再执行所以对 uint8_t 变量来说左移后高 8 位并不会自动消失赋值回 uint8_t 时才截断。上面代码里的(uint8_t)强转就是为了明确截断行为避免不同编译器产生警告或意外结果。有了 xtime任意字节 a 乘字节 b 就可以像做竖式乘法一样完成从 b 的最低位开始如果当前位是 1就把 a 累加进结果每处理一位a 就做一次 xtimeb 右移一位。这就是通用 GF(2^8) 乘法函数static uint8_t gmul(uint8_t a, uint8_t b) { uint8_t p 0; while (b) { if (b 1) { p ^ a; } a xtime(a); b 1; } return p; }这段代码的逻辑和十进制乘法竖式几乎一样只不过加法换成了异或乘 2 换成了 xtime。建议第一次接触的人拿0x0a乘0x03手算一遍0x03的最低位是 1结果先累加0x0a右移一位后最低位变成 1同时a变成xtime(0x0a) 0x14再累加一次得到0x0a ^ 0x14 0x1e。这个结果和普通整数乘法的 30 恰好相同但千万别被误导——换一个字节就可能完全不一致了。比如0x80乘0x02xtime 会得到0x80 1 ^ 0x1B 0x1B整数乘法却是 0x100完全是另一个量级。3.2 MixColumns的C语言实现列混淆的操作对象是状态的每一列标准的 4×4 矩阵乘法如下所示所有运算都在 GF(2^8) 上| s0 | | 2 3 1 1 | | s0 | | s1 | | 1 2 3 1 | | s1 | | s2 | | 1 1 2 3 | | s2 | | s3 | | 3 1 1 2 | | s3 |展开写成逐字节计算的公式就是s0 2·s0 ⊕ 3·s1 ⊕ 1·s2 ⊕ 1·s3s1 1·s0 ⊕ 2·s1 ⊕ 3·s2 ⊕ 1·s3s2 1·s0 ⊕ 1·s1 ⊕ 2·s2 ⊕ 3·s3s3 3·s0 ⊕ 1·s1 ⊕ 1·s2 ⊕ 2·s3由于列混淆只用到系数 1、2、3其中乘 1 保持不变乘 2 就是 xtime乘 3 等于乘 2 再异或自己所以并不需要每次调通用 gmul。可以准备两个极短的工具函数static uint8_t mul2(uint8_t x) { return xtime(x); } static uint8_t mul3(uint8_t x) { return xtime(x) ^ x; }然后混列函数这样写void mix_columns(uint8_t s[4][4]) { for (int c 0; c 4; c) { uint8_t a0 s[0][c]; uint8_t a1 s[1][c]; uint8_t a2 s[2][c]; uint8_t a3 s[3][c]; s[0][c] mul2(a0) ^ mul3(a1) ^ a2 ^ a3; s[1][c] a0 ^ mul2(a1) ^ mul3(a2) ^ a3; s[2][c] a0 ^ a1 ^ mul2(a2) ^ mul3(a3); s[3][c] mul3(a0) ^ a1 ^ a2 ^ mul2(a3); } }这里有一个非常容易犯的错如果直接在循环里读s[0][c]、s[1][c]边读边写会把还没有参与计算的旧值覆盖掉。比如计算s[0][c]时要使用s[1][c]的原始值如果先写回s[0][c]后面计算s[1][c]时用到s[0][c]就会拿错。所以必须先把一列的四个字节拷贝到局部变量 a0、a1、a2、a3 里全部计算完再一次写回。这个顺序问题是列混淆实现里最常见的 bug没有之一。还是用前面那个状态矩阵的例子。ShiftRows 之后第一列的四个字节是db 0a 01 67通过上面的公式算出来第一列应该变成d5 ab 7a b3。你在调试时就拿这一列验证如果输出不对几乎可以肯定是 GF 乘法或者循环里的覆盖顺序出了问题。3.3 性能优化思路查表法与T-tables看到上面gmul函数里有一个 while 循环初学者可能会担心性能。实际加密库确实很少用这种逐位循环来实现 MixColumns更常见的做法是查表法。因为 MixColumns 只涉及乘 1、乘 2、乘 3可以预先准备两张 256 字节的表一张存mul2[x]一张存mul3[x]运行时直接查表替换 xtime 调用速度立刻就把 while 循环甩开一大截。更进一步OpenSSL 等密码库使用的 T-tables 会把 SubBytes、ShiftRows、MixColumns 合并成四张 1024 字节的大表每一轮只要查 4 次表、做 4 次异或就能一次性完成三个步骤。这种表驱动实现性能很好但需要注意代码体积明显增大而且有些实现里查表的索引可能依赖密钥或密文数据在侧信道攻击面前有点敏感。现在 x86 平台普遍有 AES-NI 硬件指令性能优化的优先级早就变了不过在嵌入式环境或者纯学习场景手写查表法依然是理解 AES 内部结构的好素材。对初学者来说我建议不要一开始就上查表法。先用 xtime 和 mul2/mul3 把逻辑跑对中间状态能和标准文档对上再去折腾优化。优化永远是在正确性之后的事顺序反了只会让调试难度翻倍。3.4 逆列混淆的系数来源解密时要用逆列混淆 InvMixColumns对应的逆矩阵系数不再是 2 和 3而是 14、11、13、9| s0 | | 14 11 13 9 | | s0 | | s1 | | 9 14 11 13 | | s1 | | s2 | | 13 9 14 11 | | s2 | | s3 | | 11 13 9 14 | | s3 |这里的 14、11、13、9 在 GF(2^8) 里分别就是 0x0E、0x0B、0x0D、0x09。它们不是随手写出来的而是通过求矩阵的逆得到的。因为在 GF(2^8) 中每个非零元素都有乘法逆元所以原始的 MixColumns 矩阵一定可逆求逆之后就得到这组新系数。实现逆列混淆时可以照抄 MixColumns 的结构只是把系数换成 9、11、13、14然后调用通用 gmulvoid inv_mix_columns(uint8_t s[4][4]) { for (int c 0; c 4; c) { uint8_t a0 s[0][c]; uint8_t a1 s[1][c]; uint8_t a2 s[2][c]; uint8_t a3 s[3][c]; s[0][c] gmul(a0, 14) ^ gmul(a1, 11) ^ gmul(a2, 13) ^ gmul(a3, 9); s[1][c] gmul(a0, 9) ^ gmul(a1, 14) ^ gmul(a2, 11) ^ gmul(a3, 13); s[2][c] gmul(a0, 13) ^ gmul(a1, 9) ^ gmul(a2, 14) ^ gmul(a3, 11); s[3][c] gmul(a0, 11) ^ gmul(a1, 13) ^ gmul(a2, 9) ^ gmul(a3, 14); } }这段代码验算起来也更麻烦因为乘 14、乘 11 这类运算没法一眼看出结果所以解密调试时不要手工硬算直接用标准向量整体比对即可。工程上可以预先给 9、11、13、14 各建一张 256 字节查表把解密 MixColumns 也变成查表异或。4. 把行移位和列混淆装进完整的轮函数4.1 轮函数代码骨架单独看 ShiftRows 和 MixColumns 很容易理解但它们真正发挥作用是在 AES 的轮函数里。一个典型的 AES 轮函数骨架大概长这样void aes_round(uint8_t state[4][4], const uint8_t round_key[16], int last_round) { // SubBytes: 逐字节查 S 盒 for (int r 0; r 4; r) { for (int c 0; c 4; c) { state[r][c] sbox[state[r][c]]; } } // ShiftRows: 行移位 shift_rows(state); // MixColumns: 列混淆最后一轮不做 if (!last_round) { mix_columns(state); } // AddRoundKey: 异或轮密钥 add_round_key(state, round_key); }这里sbox是 FIPS 197 附录 A 里给出的 256 字节标准 S 盒篇幅太长就不在文章里贴全表了网上很容易找到完整数组。需要注意的是AES 的状态是 4×4 矩阵但轮密钥通常以连续 16 字节表示按列填充进矩阵后再异或。add_round_key里如果直接操作二维状态可以从round_key[4 * c r]取值void add_round_key(uint8_t state[4][4], const uint8_t rk[16]) { for (int c 0; c 4; c) { for (int r 0; r 4; r) { state[r][c] ^ rk[4 * c r]; } } }把这段代码放到你自己的工程里时建议把sbox声明成const放在函数外部避免每次调用都重新初始化。嵌入式环境里还可以把它放到 flash 段减少 RAM 占用。4.2 AES-128完整加密流程中对齐完整的 AES-128 加密流程是先做一次初始 AddRoundKey然后重复 9 轮“SubBytes ShiftRows MixColumns AddRoundKey”最后做一轮“SubBytes ShiftRows AddRoundKey”。AES-192 是 12 轮AES-256 是 14 轮密钥扩展的轮密钥数量也跟着变化。如果你只是验证行移位和列混淆不需要一次把密钥扩展也写完可以直接用预先准备好的轮密钥数组来跑一两个轮函数的测试。一个值得反复强调的点最后一轮千万不要调用 MixColumns。很多人写完代码后加密结果只有最后几个字节不对查来查去发现是最后多混了一列这在初学阶段非常普遍。另一个常见问题是轮密钥的排列方式。FIPS 197 把轮密钥写成连续的 16 字节序列每一轮取其中 16 字节作为 round key如果你从某个库或者在线工具里抄来的测试向量没有注意字节序异或进状态之后中间状态全乱很难定位到底是密钥扩展错了还是轮函数错了。我的建议是先固定用一个自己熟悉的测试向量比如 FIPS 197 附录 B 的例子把每一轮中间状态都打印出来和文档一行行对。4.3 用FIPS 197测试向量验证正确性FIPS 197 文档本身就是最好的验证工具。它里面给了完整的 AES-128 示例明文是00112233445566778899aabbccddeeff密钥是000102030405060708090a0b0c0d0e0f最终密文是69c4e0d86a7b0430d8cdb78070b4c55a。更关键的是它在附录里列出了每一轮开始时的状态值你可以在自己的实现里逐个阶段打印状态和文档对比就能精确知道是哪一步出了问题。具体做法是给代码加一个打印函数void print_state_flat(const char *tag, uint8_t s[4][4]) { printf(%s: , tag); for (int c 0; c 4; c) { for (int r 0; r 4; r) { printf(%02x , s[r][c]); } } printf(\n); }注意这个打印顺序是“先列后行”因为 FIPS 197 里表示状态时是一串连续字节从state[0][0]开始依次state[1][0]、state[2][0]、state[3][0]、state[0][1]……如果你的打印函数按行打印和文档的值对比时会容易看花眼。按列打印才能和标准向量直接对应。测试时不要只跑最终结果那只能告诉你“对还是不对”没法告诉你“错在哪一步”。正确做法是在每一轮的关键节点打印状态比如初始 AddRoundKey 之后、SubBytes 之后、ShiftRows 之后、MixColumns 之后全部打印出来和 FIPS 197 的中间值比对。只要其中某一步不一致马上能锁定是哪段代码的问题。5. 常见问题与排查技巧5.1 “aes什么模式每次加密结果都不一样”如果你在网上搜索过 AES大概率会看到一个问题为什么我用同一个密钥加密同一段明文每次结果都不一样这里要澄清一点AES 的分组加密算法本身是完全确定性的同样的明文、同样的密钥经过同样的轮函数输出必然相同。真正导致“每次结果不一样”的是分组密码的工作模式。ECB 模式最直接就是把明文切成 16 字节块每块用同一个密钥做 AES所以相同明文块会有相同密文块也因此泄露模式信息实践中不推荐使用。CBC、CTR、CFB、OFB、GCM 这些模式会引入初始向量 IV 或者随机 nonce每次加密时随机生成一个所以同一个明文加密后会得到不同密文。这个“随机”不是 AES 分组算法本身带来的而是模式设计的一部分。你在实现或调试 AES 算法时如果只关心行移位、列混淆这些轮函数逻辑用 ECB 模式甚至直接操作状态矩阵就够了别把模式的随机性混进来否则会误以为自己的 AES 写错了。5.2 内存越界和非法地址排查AES 在 C 语言里最常见的运行时错误不是算法逻辑错误而是内存越界。比如状态矩阵声明成uint8_t state[4][4]访问时不小心写成state[4][c]或state[r][4]编译器不一定报错但已经踩到了数组外的内存。再比如轮密钥AES-128 的扩展密钥长 176 字节如果你只分配了 16 字节的数组后面的轮次一访问rk[16]就会越界轻则数据被改重则直接段错误。排查这些问题的第一个利器是编译器的 sanitizer。用 GCC 或 Clang 编译时加上-fsanitizeaddress,undefined -g再运行程序越界和未定义行为会直接报出具体文件和行号。这个方法对 AES 这类数组密集的代码特别友好。第二个利器是 gdb可以在可疑的内存写操作上打断点用watch监视某个变量看它是在哪一行被改掉的。还有一个基础但经常被忽略的习惯输入缓冲区必须检查长度。假如你的 AES 函数接收const uint8_t *input和size_t len至少要在入口断言len 16。很多非法地址问题的根源不是 AES 内部逻辑而是调用方传了一个长度不足的缓冲区AES 一读就越界了。固定 16 字节分组的情况下我通常直接定义uint8_t in[16]、uint8_t out[16]能用栈数组就不用 malloc既减少内存管理负担也避免一堆空指针判断。5.3 调试C语言AES实现的几个习惯写 AES 这种多步骤算法调试习惯直接决定你能多快定位问题。第一个习惯是每个变换之后都打印状态。不要怕打印输出太多刚开始调试时宁可打印到怀疑人生也不要跳过中间步骤直接看最终密文。第二个习惯是单独测试每个小函数。ShiftRows 和 MixColumns 都可以独立成一个单元测试输入一组手工可算的数据断言输出符合预期等所有独立函数都过了再拼完整的轮函数。第三个习惯是注意一维数组和二维数组之间的索引一致性。如果你在项目里混用两种布局很容易出现“明明逻辑没问题结果就是不对”的诡异现象。解决方案是给状态访问写一个 get/set 宏或者干脆统一用二维数组直到最后的性能优化阶段再换布局。第四个习惯是使用十六进制打印而不是十进制。AES 的字节值用%02x输出一眼就能和文档里的十六进制表对上用十进制反而让你多一步换算。最后再分享一个我个人的习惯我学 AES 时没有急着一次把全部 10 轮写完而是先把 ShiftRows、MixColumns 拆成独立小函数每个函数配一个 main 去跑用前面那种手工可算的状态做输入打印结果比对。等这两个函数确认无误再拼轮函数最后用 FIPS 197 的标准向量做整体测试。这样看起来多花了一点时间实际上省掉的是“整个算法出错却不知道在哪一步”的长时间抓狂。行移位和列混淆这两个名字听起来很工程骨子里却是扎实的代数思路一旦理清你不仅掌握了 AES 的扩散机制以后看 SM4、Twofish 这些同样用有限域矩阵变换的算法也会顺畅很多。
AES行移位与列混淆的C语言实现：GF(2^8)有限域乘法核心解析
如果你已经开始用 C 语言写 AES多半会遇到这样一个阶段SubBytes 查表简单AddRoundKey 就是异或甚至密钥扩展也能照猫画虎但一走到行移位和列混淆就开始怀疑人生。行移位还好说无非是把状态矩阵里的字节挪个位置列混淆就麻烦了矩阵乘法里出现的 2、3 这些系数对应的不是普通整数乘法而是在 GF(2^8) 有限域上的运算第一次接触的人很容易在这里卡住甚至代码能跑但结果和标准测试向量怎么都对不上。我见过不少初学者把 AES 当成一个“背代码”的练习实际上 AES 是特别适合拿来练 C 语言的综合项目要操作字节数组、处理二维索引、写位运算、做边界检查还要理解一点抽象代数。这篇文章不打算把 AES 的每个细节重新讲一遍而是聚焦在行移位和列混淆这两个环节把原理说透把 C 语言实现一步一步写清楚再分享我实际调试中踩过的那些坑。无论你是在做课程设计、嵌入式项目还是单纯想搞明白 FIPS 197 文档里那几张表格这篇文章都能用上。1. 先搞清楚AES整体架构行移位和列混淆到底在干嘛1.1 SPN结构和Feistel结构的区别AES 不是 Feistel 网络编译器里的“对称加密”大类下DES 一系的算法才是 Feistel 结构每轮只处理一半数据左半边和右半边通过轮函数互相搅和。AES 走的是完全不同的路线它属于代换-置换网络也就是 SPN 结构每一轮会把整个 128 位状态同时拿来做非线性代换和线性扩散所以轮函数里每一步都有明确分工。明白这个背景之后再看行移位和列混淆就不会觉得它们是“莫名其妙的两步”了。SPN 结构要成立必须同时满足两个条件一是要有非线性层这就是 SubBytes 做的事用 S 盒提供混淆二是要有线性扩散层让任何一位明文的改变能快速波及整个状态这就是 ShiftRows 和 MixColumns 的职责。很多初学者只记住了“AES 有四个步骤”却没有意识到这四个步骤其实是一个安全设计如果没有 ShiftRows 这种跨列操作状态矩阵的每一列永远只在自己列内变换攻击者完全可以把 16 字节分组拆成 4 个独立的 4 字节向量来分别处理AES 的强度会断崖式下降。用生活一点的话说SubBytes 像是给每个字节单独换了个马甲而 ShiftRows 和 MixColumns 是负责让整个队伍彻底打散重组。行移位把不同列之间的字节混在一起列混淆又把每一列内部的四个字节线性混合成新的四个字节两者配合起来才能达到“改一个位满盘皆变”的雪崩效应。这正是前两轮之后状态里的每一个输出字节都同时依赖几乎所有输入字节的原因。1.2 一轮完整流程和“扩散”的本质AES 一轮的标准顺序是AddRoundKey 先做一次轮密钥异或然后 SubBytes 逐字节代换ShiftRows 做行循环移位MixColumns 做列混合最后再执行一次 AddRoundKey。最后一轮比较特殊会把 MixColumns 去掉只保留 SubBytes、ShiftRows、AddRoundKey。很多人在写代码时把这四个步骤的顺序搞错尤其是把 AddRoundKey 和 SubBytes 的顺序记反结果就是中间状态对不上。这四个步骤在 AES 里的作用可以简单归类步骤类型作用AddRoundKey密钥相关将轮密钥异或进状态密钥由此进入分组运算SubBytes非线性代换S 盒逐字节替换提供混淆抵抗线性分析ShiftRows字节置换行移位让列与列之间产生交叉扩散MixColumns线性混合列混淆把一列内 4 字节混合成新的 4 字节需要注意ShiftRows 解决的是“列与列之间没有交流”的问题MixColumns 解决的是“同一列内字节之间没有混合”的问题。一套组合拳下来扩散既发生在列间也发生在列内AES 才能在两轮左右让雪崩效应铺满整个状态。2. 行移位实现索引搞清楚代码就成功了一半2.1 状态矩阵怎么存二维数组还是16字节AES 的状态矩阵永远是 4×4 字节用 C 语言实现时最常见也最直观的做法是声明成uint8_t state[4][4]把state[r][c]当成第 r 行第 c 列来用。FIPS 197 文档里描述状态时通常按列展开成一串字节比如输入的 16 字节会按“先列后行”的顺序填充第 1 个字节放到state[0][0]第 2 个字节放到state[1][0]第 3 个放到state[2][0]第 4 个放到state[3][0]第 5 个放到state[0][1]依此类推。也有不少人喜欢用一维数组uint8_t state[16]因为底层内存布局更直白而且和传入的明文缓冲区可以直接memcpy。在一维数组里state[4 * c r]就是第 r 行第 c 列的字节。两种方式没有本质区别但对行移位来说二维数组的可读性明显更好因为你一眼就能看出“第 1 行左移 1 位”是在做什么。嵌入式场景如果极其在意内存布局可以继续用一维数组但在函数内部定义一个static inline的访问宏避免到处写4 * c r导致索引算错。我自己的习惯是初学、验证算法阶段用二维数组上了项目、需要和硬件 AES 引擎对接时再改成连续缓冲区。原因很简单二维数组保留了矩阵语义打印调试时也直观不容易在行和列之间迷失方向。等逻辑完全跑通了再优化成一维布局成本很低。2.2 ShiftRows的C语言实现与验证行移位的规则一句话就能说清第 0 行不动第 1 行循环左移 1 字节第 2 行循环左移 2 字节第 3 行循环左移 3 字节。这里的“循环左移”指的是行内字节向列号增大的方向移动从列 3 出去的字节回到列 0。第 3 行左移 3 位其实等价于循环右移 1 位所以实现时可以少写几次赋值。直接给出一段可编译的 C 代码#include stdint.h void shift_rows(uint8_t s[4][4]) { uint8_t t; // 第1行循环左移1字节 t s[1][0]; s[1][0] s[1][1]; s[1][1] s[1][2]; s[1][2] s[1][3]; s[1][3] t; // 第2行循环左移2字节相当于交换列0-列2列1-列3 t s[2][0]; s[2][0] s[2][2]; s[2][2] t; t s[2][1]; s[2][1] s[2][3]; s[2][3] t; // 第3行循环左移3字节等价于循环右移1字节 t s[3][3]; s[3][3] s[3][2]; s[3][2] s[3][1]; s[3][1] s[3][0]; s[3][0] t; }这段代码手动展开了所有赋值因为 4×4 矩阵太小用两层 for 循环反而要引入取模运算和查表读起来也不如这种“平铺直叙”的方式直观。如果你喜欢通用写法可以用移位表static const uint8_t shift_r[4] {0, 1, 2, 3}; void shift_rows_generic(uint8_t s[4][4]) { uint8_t tmp[4]; for (int r 1; r 4; r) { for (int c 0; c 4; c) { tmp[c] s[r][(c shift_r[r]) % 4]; } for (int c 0; c 4; c) { s[r][c] tmp[c]; } } }如果你想验证代码对不对可以用手工可算的输入。假设初始状态是uint8_t state[4][4] { {0xdb, 0xf2, 0x01, 0x89}, {0x13, 0x0a, 0x01, 0x23}, {0x53, 0x22, 0x01, 0x45}, {0x45, 0x5c, 0x01, 0x67} };ShiftRows 之后第 1 行的13 0a 01 23变成0a 01 23 13第 2 行53 22 01 45变成01 45 53 22第 3 行45 5c 01 67变成67 45 5c 01第 0 行保持不变。这个小例子非常适合用来检查实现跑一遍代码对着看比直接上 FIPS 197 的标准向量容易定位多了。2.3 逆行移位与实现细节解密的时候需要 InvShiftRows方向正好反过来第 1 行循环右移 1 字节第 2 行循环右移 2 字节第 3 行循环右移 3 字节。代码只需要把shift_rows里每行的移动方向改一下即可这里就不再贴完整代码了只提醒一个容易被忽略的细节加密时第 1 行左移 1、第 3 行等价右移 1用的是“补位”的方式手工打开解密时第 1 行改右移、第 3 行改左移赋值方向要彻底反过来不能只改一半。另外一个和二维数组相关的 C 语言坑是函数参数退化。void shift_rows(uint8_t s[4][4])这种写法传入的其实是指向uint8_t[4]的指针所以定义成uint8_t state[4][4]后直接调用shift_rows(state)没问题。但如果你把状态定义成一维数组uint8_t state[16]再强行传给uint8_t s[4][4]形参编译器会警告类型不匹配运行时的列索引计算也会一塌糊涂。遇到这种切换不如干脆重新设计访问宏不要用强转硬塞。嵌入式平台如果不想用% 4运算通用版本可以写成(c shift_r[r]) 3因为 4 是 2 的整数次幂位与运算比取模快一点。不过现代编译器对除以常数 4 的取模通常也有优化非极端场景不需要刻意考虑。3. 列混淆实现GF(2^8)乘法是核心3.1 有限域乘法不是普通乘法xtime的来历列混淆是初学 AES 时最容易劝退的地方因为那个 4×4 矩阵里的 2 和 3看着像普通整数实际运算规则却完全不同。AES 把每个字节都当成一个以 0 和 1 为系数的多项式整个运算在 GF(2^8) 有限域上进行加法和减法都对应异或乘法则是多项式乘法再模一个不可约多项式m(x) x^8 x^4 x^3 x 1写成十六进制就是 0x11B。为什么要选这个多项式因为它是 AES 设计者精心挑选的不可约多项式可以保证域上的每一个非零元素都有逆元这是列混淆可逆、AES 能解密的数学基础。在 GF(2^8) 里乘以 2也就是乘上多项式 x可以这样理解把字节左移一位如果最高位是 1说明左移后出现了 x^8 项需要再异或 0x1B 做模约简。这个操作有一个专门的名字叫 xtime。C 语言实现特别短static uint8_t xtime(uint8_t x) { return (uint8_t)((x 1) ^ ((x 0x80) ? 0x1B : 0x00)); }先取出最高位判断是否溢出再决定要不要异或 0x1B。要注意的一点是x 1在 C 语言里会先被提升成 int 类型再执行所以对 uint8_t 变量来说左移后高 8 位并不会自动消失赋值回 uint8_t 时才截断。上面代码里的(uint8_t)强转就是为了明确截断行为避免不同编译器产生警告或意外结果。有了 xtime任意字节 a 乘字节 b 就可以像做竖式乘法一样完成从 b 的最低位开始如果当前位是 1就把 a 累加进结果每处理一位a 就做一次 xtimeb 右移一位。这就是通用 GF(2^8) 乘法函数static uint8_t gmul(uint8_t a, uint8_t b) { uint8_t p 0; while (b) { if (b 1) { p ^ a; } a xtime(a); b 1; } return p; }这段代码的逻辑和十进制乘法竖式几乎一样只不过加法换成了异或乘 2 换成了 xtime。建议第一次接触的人拿0x0a乘0x03手算一遍0x03的最低位是 1结果先累加0x0a右移一位后最低位变成 1同时a变成xtime(0x0a) 0x14再累加一次得到0x0a ^ 0x14 0x1e。这个结果和普通整数乘法的 30 恰好相同但千万别被误导——换一个字节就可能完全不一致了。比如0x80乘0x02xtime 会得到0x80 1 ^ 0x1B 0x1B整数乘法却是 0x100完全是另一个量级。3.2 MixColumns的C语言实现列混淆的操作对象是状态的每一列标准的 4×4 矩阵乘法如下所示所有运算都在 GF(2^8) 上| s0 | | 2 3 1 1 | | s0 | | s1 | | 1 2 3 1 | | s1 | | s2 | | 1 1 2 3 | | s2 | | s3 | | 3 1 1 2 | | s3 |展开写成逐字节计算的公式就是s0 2·s0 ⊕ 3·s1 ⊕ 1·s2 ⊕ 1·s3s1 1·s0 ⊕ 2·s1 ⊕ 3·s2 ⊕ 1·s3s2 1·s0 ⊕ 1·s1 ⊕ 2·s2 ⊕ 3·s3s3 3·s0 ⊕ 1·s1 ⊕ 1·s2 ⊕ 2·s3由于列混淆只用到系数 1、2、3其中乘 1 保持不变乘 2 就是 xtime乘 3 等于乘 2 再异或自己所以并不需要每次调通用 gmul。可以准备两个极短的工具函数static uint8_t mul2(uint8_t x) { return xtime(x); } static uint8_t mul3(uint8_t x) { return xtime(x) ^ x; }然后混列函数这样写void mix_columns(uint8_t s[4][4]) { for (int c 0; c 4; c) { uint8_t a0 s[0][c]; uint8_t a1 s[1][c]; uint8_t a2 s[2][c]; uint8_t a3 s[3][c]; s[0][c] mul2(a0) ^ mul3(a1) ^ a2 ^ a3; s[1][c] a0 ^ mul2(a1) ^ mul3(a2) ^ a3; s[2][c] a0 ^ a1 ^ mul2(a2) ^ mul3(a3); s[3][c] mul3(a0) ^ a1 ^ a2 ^ mul2(a3); } }这里有一个非常容易犯的错如果直接在循环里读s[0][c]、s[1][c]边读边写会把还没有参与计算的旧值覆盖掉。比如计算s[0][c]时要使用s[1][c]的原始值如果先写回s[0][c]后面计算s[1][c]时用到s[0][c]就会拿错。所以必须先把一列的四个字节拷贝到局部变量 a0、a1、a2、a3 里全部计算完再一次写回。这个顺序问题是列混淆实现里最常见的 bug没有之一。还是用前面那个状态矩阵的例子。ShiftRows 之后第一列的四个字节是db 0a 01 67通过上面的公式算出来第一列应该变成d5 ab 7a b3。你在调试时就拿这一列验证如果输出不对几乎可以肯定是 GF 乘法或者循环里的覆盖顺序出了问题。3.3 性能优化思路查表法与T-tables看到上面gmul函数里有一个 while 循环初学者可能会担心性能。实际加密库确实很少用这种逐位循环来实现 MixColumns更常见的做法是查表法。因为 MixColumns 只涉及乘 1、乘 2、乘 3可以预先准备两张 256 字节的表一张存mul2[x]一张存mul3[x]运行时直接查表替换 xtime 调用速度立刻就把 while 循环甩开一大截。更进一步OpenSSL 等密码库使用的 T-tables 会把 SubBytes、ShiftRows、MixColumns 合并成四张 1024 字节的大表每一轮只要查 4 次表、做 4 次异或就能一次性完成三个步骤。这种表驱动实现性能很好但需要注意代码体积明显增大而且有些实现里查表的索引可能依赖密钥或密文数据在侧信道攻击面前有点敏感。现在 x86 平台普遍有 AES-NI 硬件指令性能优化的优先级早就变了不过在嵌入式环境或者纯学习场景手写查表法依然是理解 AES 内部结构的好素材。对初学者来说我建议不要一开始就上查表法。先用 xtime 和 mul2/mul3 把逻辑跑对中间状态能和标准文档对上再去折腾优化。优化永远是在正确性之后的事顺序反了只会让调试难度翻倍。3.4 逆列混淆的系数来源解密时要用逆列混淆 InvMixColumns对应的逆矩阵系数不再是 2 和 3而是 14、11、13、9| s0 | | 14 11 13 9 | | s0 | | s1 | | 9 14 11 13 | | s1 | | s2 | | 13 9 14 11 | | s2 | | s3 | | 11 13 9 14 | | s3 |这里的 14、11、13、9 在 GF(2^8) 里分别就是 0x0E、0x0B、0x0D、0x09。它们不是随手写出来的而是通过求矩阵的逆得到的。因为在 GF(2^8) 中每个非零元素都有乘法逆元所以原始的 MixColumns 矩阵一定可逆求逆之后就得到这组新系数。实现逆列混淆时可以照抄 MixColumns 的结构只是把系数换成 9、11、13、14然后调用通用 gmulvoid inv_mix_columns(uint8_t s[4][4]) { for (int c 0; c 4; c) { uint8_t a0 s[0][c]; uint8_t a1 s[1][c]; uint8_t a2 s[2][c]; uint8_t a3 s[3][c]; s[0][c] gmul(a0, 14) ^ gmul(a1, 11) ^ gmul(a2, 13) ^ gmul(a3, 9); s[1][c] gmul(a0, 9) ^ gmul(a1, 14) ^ gmul(a2, 11) ^ gmul(a3, 13); s[2][c] gmul(a0, 13) ^ gmul(a1, 9) ^ gmul(a2, 14) ^ gmul(a3, 11); s[3][c] gmul(a0, 11) ^ gmul(a1, 13) ^ gmul(a2, 9) ^ gmul(a3, 14); } }这段代码验算起来也更麻烦因为乘 14、乘 11 这类运算没法一眼看出结果所以解密调试时不要手工硬算直接用标准向量整体比对即可。工程上可以预先给 9、11、13、14 各建一张 256 字节查表把解密 MixColumns 也变成查表异或。4. 把行移位和列混淆装进完整的轮函数4.1 轮函数代码骨架单独看 ShiftRows 和 MixColumns 很容易理解但它们真正发挥作用是在 AES 的轮函数里。一个典型的 AES 轮函数骨架大概长这样void aes_round(uint8_t state[4][4], const uint8_t round_key[16], int last_round) { // SubBytes: 逐字节查 S 盒 for (int r 0; r 4; r) { for (int c 0; c 4; c) { state[r][c] sbox[state[r][c]]; } } // ShiftRows: 行移位 shift_rows(state); // MixColumns: 列混淆最后一轮不做 if (!last_round) { mix_columns(state); } // AddRoundKey: 异或轮密钥 add_round_key(state, round_key); }这里sbox是 FIPS 197 附录 A 里给出的 256 字节标准 S 盒篇幅太长就不在文章里贴全表了网上很容易找到完整数组。需要注意的是AES 的状态是 4×4 矩阵但轮密钥通常以连续 16 字节表示按列填充进矩阵后再异或。add_round_key里如果直接操作二维状态可以从round_key[4 * c r]取值void add_round_key(uint8_t state[4][4], const uint8_t rk[16]) { for (int c 0; c 4; c) { for (int r 0; r 4; r) { state[r][c] ^ rk[4 * c r]; } } }把这段代码放到你自己的工程里时建议把sbox声明成const放在函数外部避免每次调用都重新初始化。嵌入式环境里还可以把它放到 flash 段减少 RAM 占用。4.2 AES-128完整加密流程中对齐完整的 AES-128 加密流程是先做一次初始 AddRoundKey然后重复 9 轮“SubBytes ShiftRows MixColumns AddRoundKey”最后做一轮“SubBytes ShiftRows AddRoundKey”。AES-192 是 12 轮AES-256 是 14 轮密钥扩展的轮密钥数量也跟着变化。如果你只是验证行移位和列混淆不需要一次把密钥扩展也写完可以直接用预先准备好的轮密钥数组来跑一两个轮函数的测试。一个值得反复强调的点最后一轮千万不要调用 MixColumns。很多人写完代码后加密结果只有最后几个字节不对查来查去发现是最后多混了一列这在初学阶段非常普遍。另一个常见问题是轮密钥的排列方式。FIPS 197 把轮密钥写成连续的 16 字节序列每一轮取其中 16 字节作为 round key如果你从某个库或者在线工具里抄来的测试向量没有注意字节序异或进状态之后中间状态全乱很难定位到底是密钥扩展错了还是轮函数错了。我的建议是先固定用一个自己熟悉的测试向量比如 FIPS 197 附录 B 的例子把每一轮中间状态都打印出来和文档一行行对。4.3 用FIPS 197测试向量验证正确性FIPS 197 文档本身就是最好的验证工具。它里面给了完整的 AES-128 示例明文是00112233445566778899aabbccddeeff密钥是000102030405060708090a0b0c0d0e0f最终密文是69c4e0d86a7b0430d8cdb78070b4c55a。更关键的是它在附录里列出了每一轮开始时的状态值你可以在自己的实现里逐个阶段打印状态和文档对比就能精确知道是哪一步出了问题。具体做法是给代码加一个打印函数void print_state_flat(const char *tag, uint8_t s[4][4]) { printf(%s: , tag); for (int c 0; c 4; c) { for (int r 0; r 4; r) { printf(%02x , s[r][c]); } } printf(\n); }注意这个打印顺序是“先列后行”因为 FIPS 197 里表示状态时是一串连续字节从state[0][0]开始依次state[1][0]、state[2][0]、state[3][0]、state[0][1]……如果你的打印函数按行打印和文档的值对比时会容易看花眼。按列打印才能和标准向量直接对应。测试时不要只跑最终结果那只能告诉你“对还是不对”没法告诉你“错在哪一步”。正确做法是在每一轮的关键节点打印状态比如初始 AddRoundKey 之后、SubBytes 之后、ShiftRows 之后、MixColumns 之后全部打印出来和 FIPS 197 的中间值比对。只要其中某一步不一致马上能锁定是哪段代码的问题。5. 常见问题与排查技巧5.1 “aes什么模式每次加密结果都不一样”如果你在网上搜索过 AES大概率会看到一个问题为什么我用同一个密钥加密同一段明文每次结果都不一样这里要澄清一点AES 的分组加密算法本身是完全确定性的同样的明文、同样的密钥经过同样的轮函数输出必然相同。真正导致“每次结果不一样”的是分组密码的工作模式。ECB 模式最直接就是把明文切成 16 字节块每块用同一个密钥做 AES所以相同明文块会有相同密文块也因此泄露模式信息实践中不推荐使用。CBC、CTR、CFB、OFB、GCM 这些模式会引入初始向量 IV 或者随机 nonce每次加密时随机生成一个所以同一个明文加密后会得到不同密文。这个“随机”不是 AES 分组算法本身带来的而是模式设计的一部分。你在实现或调试 AES 算法时如果只关心行移位、列混淆这些轮函数逻辑用 ECB 模式甚至直接操作状态矩阵就够了别把模式的随机性混进来否则会误以为自己的 AES 写错了。5.2 内存越界和非法地址排查AES 在 C 语言里最常见的运行时错误不是算法逻辑错误而是内存越界。比如状态矩阵声明成uint8_t state[4][4]访问时不小心写成state[4][c]或state[r][4]编译器不一定报错但已经踩到了数组外的内存。再比如轮密钥AES-128 的扩展密钥长 176 字节如果你只分配了 16 字节的数组后面的轮次一访问rk[16]就会越界轻则数据被改重则直接段错误。排查这些问题的第一个利器是编译器的 sanitizer。用 GCC 或 Clang 编译时加上-fsanitizeaddress,undefined -g再运行程序越界和未定义行为会直接报出具体文件和行号。这个方法对 AES 这类数组密集的代码特别友好。第二个利器是 gdb可以在可疑的内存写操作上打断点用watch监视某个变量看它是在哪一行被改掉的。还有一个基础但经常被忽略的习惯输入缓冲区必须检查长度。假如你的 AES 函数接收const uint8_t *input和size_t len至少要在入口断言len 16。很多非法地址问题的根源不是 AES 内部逻辑而是调用方传了一个长度不足的缓冲区AES 一读就越界了。固定 16 字节分组的情况下我通常直接定义uint8_t in[16]、uint8_t out[16]能用栈数组就不用 malloc既减少内存管理负担也避免一堆空指针判断。5.3 调试C语言AES实现的几个习惯写 AES 这种多步骤算法调试习惯直接决定你能多快定位问题。第一个习惯是每个变换之后都打印状态。不要怕打印输出太多刚开始调试时宁可打印到怀疑人生也不要跳过中间步骤直接看最终密文。第二个习惯是单独测试每个小函数。ShiftRows 和 MixColumns 都可以独立成一个单元测试输入一组手工可算的数据断言输出符合预期等所有独立函数都过了再拼完整的轮函数。第三个习惯是注意一维数组和二维数组之间的索引一致性。如果你在项目里混用两种布局很容易出现“明明逻辑没问题结果就是不对”的诡异现象。解决方案是给状态访问写一个 get/set 宏或者干脆统一用二维数组直到最后的性能优化阶段再换布局。第四个习惯是使用十六进制打印而不是十进制。AES 的字节值用%02x输出一眼就能和文档里的十六进制表对上用十进制反而让你多一步换算。最后再分享一个我个人的习惯我学 AES 时没有急着一次把全部 10 轮写完而是先把 ShiftRows、MixColumns 拆成独立小函数每个函数配一个 main 去跑用前面那种手工可算的状态做输入打印结果比对。等这两个函数确认无误再拼轮函数最后用 FIPS 197 的标准向量做整体测试。这样看起来多花了一点时间实际上省掉的是“整个算法出错却不知道在哪一步”的长时间抓狂。行移位和列混淆这两个名字听起来很工程骨子里却是扎实的代数思路一旦理清你不仅掌握了 AES 的扩散机制以后看 SM4、Twofish 这些同样用有限域矩阵变换的算法也会顺畅很多。
