先交代一下背景我在做一个嵌入式通信项目的时候需要在资源很受限的 MCU 上自己实现 AES 加密不能直接搬 OpenSSL。于是把 AES 的每个环节都啃了一遍。过程中发现S 盒和密钥扩展很多人能照着抄真正卡住进度的往往是行移位和列混淆——尤其是列混淆里那个有限域乘法概念一绕代码就崩。这篇文章就把这两个环节彻底讲清楚告诉你为什么要这么设计、C 语言怎么写、调试时容易踩哪些坑。我默认你已经有 AES 的基本概念知道它是分组密码、密钥长度可以是 128/192/256 位。如果你连 AES 一轮有几个步骤都还没记清建议先把状态矩阵和轮函数的关系理顺我会从这块开始。看完这篇你至少能手写出行移位和列混淆的正确实现并且能对照标准向量验证自己的结果。1. 先把 AES 的底子铺好状态矩阵与整体流程1.1 为什么 AES 非要用 4×4 字节矩阵AES 处理的最小单位是字节16 个字节组成一个分组。这 16 个字节在内部被摆放成一个 4×4 的矩阵行索引 r 从 0 到 3列索引 c 从 0 到 3。网上的示意图一堆但你如果直接写 C 代码最容易搞错的是“这 16 个字节到底怎么填进去”。标准里规定的是列优先填充输入明文第 0 字节放在 state[0][0]第 1 字节放在 state[1][0]第 2 字节放在 state[2][0]第 3 字节放在 state[3][0]第 4 字节换到下一列放在 state[0][1]以此类推。也就是说state[r][c] input[r 4 * c];如果你按行优先填充比如直接把 input 的前 4 个字节填到第 0 行后面所有变换全乱套。这个坑我见过太多次很多人 S 盒实现没问题但最后结果不对查了半天发现是字节序填反了。理解这个列优先规则行移位和列混淆才能谈得上。1.2 一轮加密的四个操作顺序怎么记AES 的轮函数顺序是固定的SubBytes字节代换→ ShiftRows行移位→ MixColumns列混淆→ AddRoundKey轮密钥加。这个顺序不是随便定的。SubBytes 处理的是“每个字节内部”的非线性替换它解决的是混淆问题ShiftRows 和 MixColumns 处理的是“字节与字节之间”的位置扩散和线性混合解决的是扩散问题AddRoundKey 用轮密钥把结果混淆一次。逻辑上可以这么记先替身再移位再混合最后加密钥。还有一个经常搞混的点AES-128 一共 10 轮前 9 轮执行完整的四个步骤最后一轮省略 MixColumns。为什么最后一轮不做列混淆因为 MixColumns 是线性变换如果最后一轮还做攻击者可以通过逆运算把最后一轮剥离掉安全性没什么提升反而多一次计算。这是 AES 设计时做过的权衡。你写完整实现的时候循环里要把最后一轮单独处理别图省事统一走一遍。2. 行移位ShiftRows原理、反操作与 C 语言实现2.1 行移位到底在移动什么行移位的规则一句话就能说清楚第 0 行不动第 1 行循环左移 1 个字节第 2 行循环左移 2 个字节第 3 行循环左移 3 个字节。举个例子假设某个中间状态是这样的第0行: 63 7c 77 7b 第1行: ca 82 c9 7d 第2行: b7 fd 93 26 第3行: 04 27 5a 1e行移位之后变成第0行: 63 7c 77 7b 不动 第1行: 82 c9 7d ca 左移1字节 第2行: 93 26 b7 fd 左移2字节 第3行: 1e 04 27 5a 左移3字节它做的事情本质上是打乱列与列之间的字节关系原来同一列的数据经过行移位后会散布到不同的列里。如果没有这一步每一列就只在自己列内部做列混淆字节的位置扩散范围太小。行移位和列混淆配合起来才能把一个字节的变化快速扩散到整个状态矩阵。很多教材喜欢从“扩散”的角度解释我换个生活化的类比你有一排四张桌子每张桌子上有四个杯子。行移位就是把第二排的杯子整体往左推一格、第三排推两格、第四排推三格推到边缘的杯子绕回到右边。这样原本“竖着对齐”的杯子全错开了后面要混合的时候杯子就不会只在同一列里打转。2.2 解密时的逆向行移位行移位是循环位移操作所以逆向操作就是反方向移动第 0 行不动第 1 行循环右移 1 字节第 2 行右移 2 字节第 3 行右移 3 字节。由于第 3 行左移 3 字节等价于右移 1 字节实际实现时有些人会写“第 1 行左移 1、第 2 行左移 2、第 3 行右移 1”这样也能得到正确结果但逻辑上不如“统一右移”清晰。我建议解密函数里单独写一个 inv_shift_rows不要图省事把加密位移反过来硬套否则过两周回来看代码又要重新推导一遍。2.3 三种 C 语言写法里我推荐哪种行移位的 C 实现有很多种我见过三种比较典型的第一种是逐字节交换。代码最啰嗦第 2 行要交换两次、第 3 行要写三个临时变量非常容易手滑写错。第二种是临时数组。先把整行拷出来再按偏移写回去。逻辑最直观不容易错缺点是每次多占一个 uint8_t[4]对嵌入式开发来说可忽略。第三种是宏展开或查表索引。用索引表直接算目标位置效率高但第一次读代码的人基本看不懂。我推荐第二种临时数组版本理由就一条可读性决定可维护性。AES 本身就是靠几个标准向量就能验证的算法正确性比那十几条指令的性能重要得多。下面是推荐写法void shift_rows(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]; } for (int c 0; c 4; c) { s[r][c] tmp[(c r) % 4]; // 左移 r 个字节 } } }对应解密void inv_shift_rows(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]; } for (int c 0; c 4; c) { s[r][c] tmp[(c - r 4) % 4]; // 右移 r 个字节 } } }这里有个小细节模 4 运算在编译器眼里会转换成除法性能不算最优。你如果对性能敏感可以改成“先存 tmp 再按固定下标回填”比如第 1 行直接写 s[1][0] tmp[1], s[1][1] tmp[2]这样省掉取模。但绝大多数场景下取模的开销可以忽略先保证代码没错再说。3. 列混淆MixColumns有限域乘法才是真正的分水岭3.1 列混淆的矩阵乘法系数 2、3、1、1 从哪来行移位处理的是“行方向”的位置扩散列混淆处理的是“列方向”的字节混合。列混淆作用于每一列把列里的 4 个字节通过线性变换重新组合。标准变换是把某一列的 4 个字节看成一个列向量左乘一个 4×4 的矩阵| s0 | | 2 3 1 1 | | s0 | | s1 | | 1 2 3 1 | × | s1 | | s2 | | 1 1 2 3 | | s2 | | s3 | | 3 1 1 2 | | s3 |这里面的“乘”和“加”都不是普通的整数运算。加法是异或乘法是 GF(2^8) 有限域乘法。这一点必须刻在脑子里否则你会发现算出来的结果跟标准答案差得离谱。为什么偏偏选 2、3、1、1 这几个系数因为 AES 设计者希望这个矩阵是 MDS最大距离可分矩阵。MDS 矩阵有个性质输入任意两列不同经过变换后输出的任意两列也一定不同且差分扩散的“分支数”达到最大。用大白话说这种矩阵能把单一字节的修改扩散到整列甚至整行让密码分析者很难追踪差分的传播路径。具体证明很复杂工程上你只需要知道这不是随便拍的系数。3.2 GF(2^8) 乘法的核心xtime 与 0x1B要在 C 语言里实现列混淆绕不开 GF(2^8) 乘法。GF(2^8) 可以理解成“二进制多项式”的运算空间一个字节 0x57 对应多项式 x^6 x^4 x^2 x 1。AES 在这个空间里选了一个不可约多项式 x^8 x^4 x^3 x 1十六进制就是 0x11B来做模运算。为什么乘法要“取模”因为两个 8 位多项式乘起来最高能到 x^14 次超过 8 位了必须模掉才能保证结果还落在一个字节内。取模用的多项式必须是不可约的类比整数域里的素数这样能保证每个非零元素都有逆元解密时才有逆运算可做。C 语言实现 GF(2^8) 乘法有好几种思路最直观的是“移位加异或”类似手算十进制乘法时的竖式。但真正高频使用的是 xtime 函数它专门算“乘 2”uint8_t xtime(uint8_t a) { uint16_t t (uint16_t)a 1; // 先提升到16位避免溢出丢失 if (t 0x100) { // 最高位溢出需要模不可约多项式 t ^ 0x1B; } return (uint8_t)t; }0x1B 是怎么来的不可约多项式 0x11B去掉最高位的 0x100剩下 0x1B。当左移一位后第 8 位0x100 位为 1说明次数已经到 8 次了这时候异或 0x1B 等价于“减去 x^8再对低 8 位做模约减”。有了 xtime 之后乘任意数都可以拆成 xtime 的组合。比如乘 0x03 乘 2 加乘 1也就是 xtime(a) ^ a乘 0x0b 乘 8 加乘 2 加乘 1连续调三次 xtime 再异或即可。我举个例子验证一下0x57 乘 0x13 等于多少0x57 × 0x01 0x570x57 × 0x02 xtime(0x57) 0xAE0x57 × 0x04 xtime(0xAE) 0x470x57 × 0x08 xtime(0x47) 0x8E0x57 × 0x10 xtime(0x8E) 0x07因为 0x13 0x10 ^ 0x02 ^ 0x01所以0x57 × 0x13 0x57 ^ 0xAE ^ 0x07 0xFE这个结果跟 AES 标准里的例子是一致的FIPS-197 中 0x57·0x130xFE。如果你自己写了一个 gmul 函数先用这个例子验一下通过了再继续往下。3.3 列混淆的 C 语言实现与验证算例通用 GF(2^8) 乘法写成 C 函数很简单uint8_t gmul(uint8_t a, uint8_t b) { uint8_t p 0; for (int i 0; i 8; i) { if (b 1) { p ^ a; } a xtime(a); b 1; } return p; }然后列混淆就能按矩阵乘法的定义直接写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] gmul(a0, 2) ^ gmul(a1, 3) ^ a2 ^ a3; s[1][c] a0 ^ gmul(a1, 2) ^ gmul(a2, 3) ^ a3; s[2][c] a0 ^ a1 ^ gmul(a2, 2) ^ gmul(a3, 3); s[3][c] gmul(a0, 3) ^ a1 ^ a2 ^ gmul(a3, 2); } }为什么要先把 a0~a3 存下来因为后面要对同一列的原始字节反复使用如果直接读 s[0][c]第一行赋值之后后面用到 s[0][c] 就已经是新值了。这个错很容易犯尤其在边写边改的时候。标准验证算例用它测一下就知道了某一列原始数据是 0xdb、0x13、0x53、0x45按照上面的 mix_columns 算完应该得到 0x8e、0x4d、0xa1、0xbc。这个例子在 FIPS-197 的标准附录里可以对照拿它当单元测试非常管用。3.4 逆向列混淆解密不能直接复用加密矩阵解密的时候列混淆也需要逆运算。加密矩阵的逆矩阵是| 14 11 13 9 | | 9 14 11 13 | | 13 9 14 11 | | 11 13 9 14 |所以解密时每一列的四个新字节这样算void 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); } }这里有个工程上常见的陷阱有人想偷懒说既然 MixColumns 是线性的解密时能不能把加密矩阵的逆矩阵展开成“先乘某个系数再对行移位”的组合理论可以但落地代码很容易错。我建议老老实实把四个逆系数写全哪怕多几次 gmul 调用。解密本来就不是性能瓶颈正确性优先。4. 完整 C 语言实现把行移位和列混淆串起来4.1 数据结构与字节序90% 的坑出在这里我前面强调过状态矩阵是列优先填充。我们用二维数组 uint8_t state[4][4]第 1 个维度是行第 2 个维度是列。如果你更习惯一维数组可以用宏来做映射比如#define STATE(r, c) state[(r) 4 * (c)]两种都行只要记住 state[r][c] 对应输入数据的第 r 4c 个字节而不是 r4 c。字节序问题也得提一句。如果你的平台是 little-endian从一份连续内存里读 16 字节时uint32_t 和 uint8_t 数组之间的转换顺序会让你崩溃。最稳妥的做法是输入输出全部用 uint8_t 指针禁止把 state 强转成 uint32_t 再按数值运算。AES 所有变换都是字节级的跑在什么字节序的 CPU 上结果都应该一致。4.2 可编译运行的 AES 核心函数把上面这些函数拼起来一个最小可验证的 AES 核心片段是这样的#include stdio.h #include stdint.h uint8_t xtime(uint8_t a) { uint16_t t (uint16_t)a 1; if (t 0x100) { t ^ 0x1B; } return (uint8_t)t; } uint8_t gmul(uint8_t a, uint8_t b) { uint8_t p 0; for (int i 0; i 8; i) { if (b 1) { p ^ a; } a xtime(a); b 1; } return p; } void shift_rows(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]; } for (int c 0; c 4; c) { s[r][c] tmp[(c r) % 4]; } } } 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] gmul(a0, 2) ^ gmul(a1, 3) ^ a2 ^ a3; s[1][c] a0 ^ gmul(a1, 2) ^ gmul(a2, 3) ^ a3; s[2][c] a0 ^ a1 ^ gmul(a2, 2) ^ gmul(a3, 3); s[3][c] gmul(a0, 3) ^ a1 ^ a2 ^ gmul(a3, 2); } } int main(void) { uint8_t s[4][4] {{0}}; s[0][0] 0xdb; s[1][0] 0x13; s[2][0] 0x53; s[3][0] 0x45; mix_columns(s); printf(0x%02x 0x%02x 0x%02x 0x%02x\n, s[0][0], s[1][0], s[2][0], s[3][0]); return 0; }这个程序编译运行后应该输出 0x8e 0x4d 0xa1 0xbc。如果你看到这个结果说明 xtime 和 gmul 的有限域乘法实现是正确的列混淆矩阵方向也写对了。这个测试比拿完整 AES 加密结果对比更直接因为完整实现里还有 S 盒和轮密钥扩展一旦结果不对你根本不知道错在哪一个环节。4.3 从核心函数到完整 AES-128还差什么行移位和列混淆只是轮函数的一部分。要跑通完整的 AES-128你还需要SubBytes用 256 字节的 S 盒表把每个字节替换掉解密时用逆 S 盒。AddRoundKey把 16 字节轮密钥按列优先填充成矩阵逐字节异或到状态上。Key Expansion从 16 字节主密钥生成 11 组轮密钥第 0 轮用主密钥之后每轮 16 字节。AES-128 是 10 轮但初始 AddRoundKey 也算一次所以需要 11 个轮密钥。轮函数编排前 9 轮做完整的 SubBytes、ShiftRows、MixColumns、AddRoundKey最后一轮省略 MixColumns。如果你要写完整实现我建议按这个顺序推进先实现并验证 S 盒再实现并验证密钥扩展最后把轮函数串起来。每完成一步都打印中间状态不要一口气写完再调试否则出了错很难定位。4.4 用标准向量自查别相信感觉完整实现完成后用 FIPS-197 附录里的标准向量做最终验证。最著名的一个是密钥000102030405060708090a0b0c0d0e0f明文00112233445566778899aabbccddeeff密文69c4e0d86a7b0430d8cdb78070b4c55a如果你的程序加密结果不是这一串说明某个环节还有错。此时不要急着猜把每一轮 SubBytes 之后、ShiftRows 之后、MixColumns 之后的状态打印出来和 FIPS-197 里提供的中间值逐个核对。这个习惯能把你排查问题的时间从一天缩短到半小时。5. 常见问题与排查技巧实录5.1 解密结果不对大概率是列混淆矩阵用错我在群里看到新手问得最多的问题就是“我的加密结果是正确的但解密出来是乱码。”这种情况十有八九是解密时没有用逆列混淆矩阵而是把加密矩阵的系数照抄了一遍。加密矩阵系数是 2、3、1、1解密矩阵系数是 14、11、13、9两者差别很大只靠“反着写一遍”是推不出来的必须查标准里的逆矩阵。排查步骤很简单先用一个已知密钥和明文跑加密确认密文和标准向量一致然后在解密函数里只处理一轮把解密第一轮结束后的状态和标准值对照。如果解密第一轮就错肯定是 inv_mix_columns 或 inv_shift_rows 的问题。如果第一轮对、后面错再去查逆 S 盒和轮密钥扩展。5.2 xtime 的溢出判断为什么不能写在左移之后有人写 xtime 时会这么写uint8_t wrong_xtime(uint8_t a) { a 1; if (a 0x100) { // 永远进不来 a ^ 0x1B; } return a; }这段代码看着逻辑没问题实际上 a 是 uint8_t左移一位后的第 8 位早就被截断了a 0x100 永远是 0。正确的做法是先用 uint16_t 暂存左移结果或者用原来的最高位做判断uint8_t xtime(uint8_t a) { return (uint8_t)((a 1) ^ ((a 0x80) ? 0x1B : 0x00)); }这个写法利用整数提升a 会先提升成 int 再左移所以不会截断但判断的是原始最高位。两种写法都对看代码习惯。关键是搞清楚溢出的判断依据是“原始字节的最高位是否为 1”不是左移后的结果。5.3 想提速用预计算表替代逐次乘法通用 gmul 每调用一次要做 8 次循环MixColumns 里每个输出字节要调 4 次 gmul一列输出要 16 次整个状态 4 列就是 64 次。加密 10 轮就是 640 次。虽然一次 gmul 才几微秒但在嵌入式平台上这就是负担。常见的优化方式是把乘 2、乘 3、乘 9、乘 11、乘 13、乘 14 的表提前算好查询时直接按下标取static uint8_t gm2[256]; static uint8_t gm3[256]; static uint8_t gm9[256]; static uint8_t gm11[256]; static uint8_t gm13[256]; static uint8_t gm14[256]; void init_gmul_tables(void) { for (int i 0; i 256; i) { gm2[i] gmul(i, 2); gm3[i] gmul(i, 3); gm9[i] gmul(i, 9); gm11[i] gmul(i, 11); gm13[i] gmul(i, 13); gm14[i] gmul(i, 14); } }加密时调用 gm2[a] ^ gm3[a1] ^ a2 ^ a3解密时查 gm14/gm11/gm13/gm9。速度能提升一个数量级代码可读性也不会差太多。更先进的做法是 OpenSSL 里那种 4 张 T 表把 MixColumns 和 AddRoundKey 融合在一起那就属于协议栈级别的优化了业务代码一般用不上。5.4 工程化提醒固定宽度类型、字节序与可移植性写 AES 这类算法C 语言里必须用标准固定宽度类型也就是 stdint.h 里的 uint8_t、uint32_t不要用 char、int。原因很简单char 的符号性由平台决定int 最短 16 位这些都会影响移位和异或的结果。uint8_t 保证 8 位无符号所有位运算行为可预测。字节序问题前面也说过这里再强调一次AES 标准是按字节流定义的和 CPU 是大端还是小端无关。如果你在 x86 上调通了把代码原样挪到 ARM 上也应该调通前提是你没有用指针强转把字节流当成 uint32_t 数组来读。用 uint8_t 数组作为唯一的外部接口可以规避绝大多数可移植性问题。另一个容易被忽略的是内存对齐。虽然 uint8_t 数组没有对齐要求但如果你在嵌入式平台开了优化并且把 state 定义成局部二维数组有些编译器会做栈上重排。如果你把所有状态都限制在固定数组里并且只通过函数参数传递地址这类优化问题基本不会碰到。5.5 关于“每次加密结果都不一样”的常见困惑网络热词里有个提问是“AES 什么模式每次加密结果都不一样”这里顺手解释一下。AES 本身是分组密码同样的明文、同样的密钥、同样的模式在 ECB 模式下每次加密结果必然是相同的。但如果你用 CBC 模式每次加密会生成一个随机 IV初始化向量跟第一块明文异或之后再加密所以每次结果都不同。CTR 模式类似每次会选不同的 nonce 和计数器初始值。所以“每次结果不同”不是 AES 算法的特性而是模式里的随机向量在起作用。自己写代码做测试时如果要复现标准向量一定要用 ECB 模式或者把 CBC 的 IV 固定成全零。否则你拿着随机 IV 去对标准向量永远对不上。5.6 调试小技巧逐轮打印中间状态写 AES 这类算法最忌讳“写完一把梭”。我习惯在开发阶段加一个调试开关在 SubBytes、ShiftRows、MixColumns、AddRoundKey 每个变换后都打印状态矩阵。标准里给出了每个中间状态的参考值你只要打印出来一行一行比马上知道是 S 盒表错、行移位方向错还是列混淆系数错。打印格式建议统一用十六进制、两个字符补零、每 4 个字节一组例如round 1 after ShiftRows: 82 c9 7d ca ...这样跟 FIPS-197 的表格可以直接对比。调试全部通过之后再把打印关掉或加宏控制不要留着 printf 进生产代码。嵌入式的串口输出很慢调试信息全开的话加密一次可能要多花几十毫秒。6. 最后动手调试时我的习惯写到这里我想分享一个自己调试 AES 实现最受益的习惯永远先验证最小单元再集成。很多人拿到 AES 就急着把 S 盒、密钥扩展、轮函数全部写完然后跑一遍发现不对开始怀疑人生。我的做法是先写 xtime用 0x57×0x130xFE 验证再写 gmul用随机组合对比标准值再写 mix_columns用 0xdb/0x13/0x53/0x45 那组数据验证最后才拼完整轮函数。每做一步都有确定性的答案兜底出错了也只用怀疑最近改动的那几行。如果你只是想在项目里用 AES完全没必要自己实现优先选 mbedTLS、OpenSSL 这类经过审计的库。但如果你想搞懂内部机制或者在资源受限的平台上按需裁剪优化把行移位和列混淆亲手写一遍是最值得投入的时间。至少我做完这件事之后再看任何 AES 的 C 语言实现脑子里都能直接映射到状态矩阵上不用再对着框图发呆。
深入理解AES行移位与列混淆：从原理到C语言实现
先交代一下背景我在做一个嵌入式通信项目的时候需要在资源很受限的 MCU 上自己实现 AES 加密不能直接搬 OpenSSL。于是把 AES 的每个环节都啃了一遍。过程中发现S 盒和密钥扩展很多人能照着抄真正卡住进度的往往是行移位和列混淆——尤其是列混淆里那个有限域乘法概念一绕代码就崩。这篇文章就把这两个环节彻底讲清楚告诉你为什么要这么设计、C 语言怎么写、调试时容易踩哪些坑。我默认你已经有 AES 的基本概念知道它是分组密码、密钥长度可以是 128/192/256 位。如果你连 AES 一轮有几个步骤都还没记清建议先把状态矩阵和轮函数的关系理顺我会从这块开始。看完这篇你至少能手写出行移位和列混淆的正确实现并且能对照标准向量验证自己的结果。1. 先把 AES 的底子铺好状态矩阵与整体流程1.1 为什么 AES 非要用 4×4 字节矩阵AES 处理的最小单位是字节16 个字节组成一个分组。这 16 个字节在内部被摆放成一个 4×4 的矩阵行索引 r 从 0 到 3列索引 c 从 0 到 3。网上的示意图一堆但你如果直接写 C 代码最容易搞错的是“这 16 个字节到底怎么填进去”。标准里规定的是列优先填充输入明文第 0 字节放在 state[0][0]第 1 字节放在 state[1][0]第 2 字节放在 state[2][0]第 3 字节放在 state[3][0]第 4 字节换到下一列放在 state[0][1]以此类推。也就是说state[r][c] input[r 4 * c];如果你按行优先填充比如直接把 input 的前 4 个字节填到第 0 行后面所有变换全乱套。这个坑我见过太多次很多人 S 盒实现没问题但最后结果不对查了半天发现是字节序填反了。理解这个列优先规则行移位和列混淆才能谈得上。1.2 一轮加密的四个操作顺序怎么记AES 的轮函数顺序是固定的SubBytes字节代换→ ShiftRows行移位→ MixColumns列混淆→ AddRoundKey轮密钥加。这个顺序不是随便定的。SubBytes 处理的是“每个字节内部”的非线性替换它解决的是混淆问题ShiftRows 和 MixColumns 处理的是“字节与字节之间”的位置扩散和线性混合解决的是扩散问题AddRoundKey 用轮密钥把结果混淆一次。逻辑上可以这么记先替身再移位再混合最后加密钥。还有一个经常搞混的点AES-128 一共 10 轮前 9 轮执行完整的四个步骤最后一轮省略 MixColumns。为什么最后一轮不做列混淆因为 MixColumns 是线性变换如果最后一轮还做攻击者可以通过逆运算把最后一轮剥离掉安全性没什么提升反而多一次计算。这是 AES 设计时做过的权衡。你写完整实现的时候循环里要把最后一轮单独处理别图省事统一走一遍。2. 行移位ShiftRows原理、反操作与 C 语言实现2.1 行移位到底在移动什么行移位的规则一句话就能说清楚第 0 行不动第 1 行循环左移 1 个字节第 2 行循环左移 2 个字节第 3 行循环左移 3 个字节。举个例子假设某个中间状态是这样的第0行: 63 7c 77 7b 第1行: ca 82 c9 7d 第2行: b7 fd 93 26 第3行: 04 27 5a 1e行移位之后变成第0行: 63 7c 77 7b 不动 第1行: 82 c9 7d ca 左移1字节 第2行: 93 26 b7 fd 左移2字节 第3行: 1e 04 27 5a 左移3字节它做的事情本质上是打乱列与列之间的字节关系原来同一列的数据经过行移位后会散布到不同的列里。如果没有这一步每一列就只在自己列内部做列混淆字节的位置扩散范围太小。行移位和列混淆配合起来才能把一个字节的变化快速扩散到整个状态矩阵。很多教材喜欢从“扩散”的角度解释我换个生活化的类比你有一排四张桌子每张桌子上有四个杯子。行移位就是把第二排的杯子整体往左推一格、第三排推两格、第四排推三格推到边缘的杯子绕回到右边。这样原本“竖着对齐”的杯子全错开了后面要混合的时候杯子就不会只在同一列里打转。2.2 解密时的逆向行移位行移位是循环位移操作所以逆向操作就是反方向移动第 0 行不动第 1 行循环右移 1 字节第 2 行右移 2 字节第 3 行右移 3 字节。由于第 3 行左移 3 字节等价于右移 1 字节实际实现时有些人会写“第 1 行左移 1、第 2 行左移 2、第 3 行右移 1”这样也能得到正确结果但逻辑上不如“统一右移”清晰。我建议解密函数里单独写一个 inv_shift_rows不要图省事把加密位移反过来硬套否则过两周回来看代码又要重新推导一遍。2.3 三种 C 语言写法里我推荐哪种行移位的 C 实现有很多种我见过三种比较典型的第一种是逐字节交换。代码最啰嗦第 2 行要交换两次、第 3 行要写三个临时变量非常容易手滑写错。第二种是临时数组。先把整行拷出来再按偏移写回去。逻辑最直观不容易错缺点是每次多占一个 uint8_t[4]对嵌入式开发来说可忽略。第三种是宏展开或查表索引。用索引表直接算目标位置效率高但第一次读代码的人基本看不懂。我推荐第二种临时数组版本理由就一条可读性决定可维护性。AES 本身就是靠几个标准向量就能验证的算法正确性比那十几条指令的性能重要得多。下面是推荐写法void shift_rows(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]; } for (int c 0; c 4; c) { s[r][c] tmp[(c r) % 4]; // 左移 r 个字节 } } }对应解密void inv_shift_rows(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]; } for (int c 0; c 4; c) { s[r][c] tmp[(c - r 4) % 4]; // 右移 r 个字节 } } }这里有个小细节模 4 运算在编译器眼里会转换成除法性能不算最优。你如果对性能敏感可以改成“先存 tmp 再按固定下标回填”比如第 1 行直接写 s[1][0] tmp[1], s[1][1] tmp[2]这样省掉取模。但绝大多数场景下取模的开销可以忽略先保证代码没错再说。3. 列混淆MixColumns有限域乘法才是真正的分水岭3.1 列混淆的矩阵乘法系数 2、3、1、1 从哪来行移位处理的是“行方向”的位置扩散列混淆处理的是“列方向”的字节混合。列混淆作用于每一列把列里的 4 个字节通过线性变换重新组合。标准变换是把某一列的 4 个字节看成一个列向量左乘一个 4×4 的矩阵| s0 | | 2 3 1 1 | | s0 | | s1 | | 1 2 3 1 | × | s1 | | s2 | | 1 1 2 3 | | s2 | | s3 | | 3 1 1 2 | | s3 |这里面的“乘”和“加”都不是普通的整数运算。加法是异或乘法是 GF(2^8) 有限域乘法。这一点必须刻在脑子里否则你会发现算出来的结果跟标准答案差得离谱。为什么偏偏选 2、3、1、1 这几个系数因为 AES 设计者希望这个矩阵是 MDS最大距离可分矩阵。MDS 矩阵有个性质输入任意两列不同经过变换后输出的任意两列也一定不同且差分扩散的“分支数”达到最大。用大白话说这种矩阵能把单一字节的修改扩散到整列甚至整行让密码分析者很难追踪差分的传播路径。具体证明很复杂工程上你只需要知道这不是随便拍的系数。3.2 GF(2^8) 乘法的核心xtime 与 0x1B要在 C 语言里实现列混淆绕不开 GF(2^8) 乘法。GF(2^8) 可以理解成“二进制多项式”的运算空间一个字节 0x57 对应多项式 x^6 x^4 x^2 x 1。AES 在这个空间里选了一个不可约多项式 x^8 x^4 x^3 x 1十六进制就是 0x11B来做模运算。为什么乘法要“取模”因为两个 8 位多项式乘起来最高能到 x^14 次超过 8 位了必须模掉才能保证结果还落在一个字节内。取模用的多项式必须是不可约的类比整数域里的素数这样能保证每个非零元素都有逆元解密时才有逆运算可做。C 语言实现 GF(2^8) 乘法有好几种思路最直观的是“移位加异或”类似手算十进制乘法时的竖式。但真正高频使用的是 xtime 函数它专门算“乘 2”uint8_t xtime(uint8_t a) { uint16_t t (uint16_t)a 1; // 先提升到16位避免溢出丢失 if (t 0x100) { // 最高位溢出需要模不可约多项式 t ^ 0x1B; } return (uint8_t)t; }0x1B 是怎么来的不可约多项式 0x11B去掉最高位的 0x100剩下 0x1B。当左移一位后第 8 位0x100 位为 1说明次数已经到 8 次了这时候异或 0x1B 等价于“减去 x^8再对低 8 位做模约减”。有了 xtime 之后乘任意数都可以拆成 xtime 的组合。比如乘 0x03 乘 2 加乘 1也就是 xtime(a) ^ a乘 0x0b 乘 8 加乘 2 加乘 1连续调三次 xtime 再异或即可。我举个例子验证一下0x57 乘 0x13 等于多少0x57 × 0x01 0x570x57 × 0x02 xtime(0x57) 0xAE0x57 × 0x04 xtime(0xAE) 0x470x57 × 0x08 xtime(0x47) 0x8E0x57 × 0x10 xtime(0x8E) 0x07因为 0x13 0x10 ^ 0x02 ^ 0x01所以0x57 × 0x13 0x57 ^ 0xAE ^ 0x07 0xFE这个结果跟 AES 标准里的例子是一致的FIPS-197 中 0x57·0x130xFE。如果你自己写了一个 gmul 函数先用这个例子验一下通过了再继续往下。3.3 列混淆的 C 语言实现与验证算例通用 GF(2^8) 乘法写成 C 函数很简单uint8_t gmul(uint8_t a, uint8_t b) { uint8_t p 0; for (int i 0; i 8; i) { if (b 1) { p ^ a; } a xtime(a); b 1; } return p; }然后列混淆就能按矩阵乘法的定义直接写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] gmul(a0, 2) ^ gmul(a1, 3) ^ a2 ^ a3; s[1][c] a0 ^ gmul(a1, 2) ^ gmul(a2, 3) ^ a3; s[2][c] a0 ^ a1 ^ gmul(a2, 2) ^ gmul(a3, 3); s[3][c] gmul(a0, 3) ^ a1 ^ a2 ^ gmul(a3, 2); } }为什么要先把 a0~a3 存下来因为后面要对同一列的原始字节反复使用如果直接读 s[0][c]第一行赋值之后后面用到 s[0][c] 就已经是新值了。这个错很容易犯尤其在边写边改的时候。标准验证算例用它测一下就知道了某一列原始数据是 0xdb、0x13、0x53、0x45按照上面的 mix_columns 算完应该得到 0x8e、0x4d、0xa1、0xbc。这个例子在 FIPS-197 的标准附录里可以对照拿它当单元测试非常管用。3.4 逆向列混淆解密不能直接复用加密矩阵解密的时候列混淆也需要逆运算。加密矩阵的逆矩阵是| 14 11 13 9 | | 9 14 11 13 | | 13 9 14 11 | | 11 13 9 14 |所以解密时每一列的四个新字节这样算void 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); } }这里有个工程上常见的陷阱有人想偷懒说既然 MixColumns 是线性的解密时能不能把加密矩阵的逆矩阵展开成“先乘某个系数再对行移位”的组合理论可以但落地代码很容易错。我建议老老实实把四个逆系数写全哪怕多几次 gmul 调用。解密本来就不是性能瓶颈正确性优先。4. 完整 C 语言实现把行移位和列混淆串起来4.1 数据结构与字节序90% 的坑出在这里我前面强调过状态矩阵是列优先填充。我们用二维数组 uint8_t state[4][4]第 1 个维度是行第 2 个维度是列。如果你更习惯一维数组可以用宏来做映射比如#define STATE(r, c) state[(r) 4 * (c)]两种都行只要记住 state[r][c] 对应输入数据的第 r 4c 个字节而不是 r4 c。字节序问题也得提一句。如果你的平台是 little-endian从一份连续内存里读 16 字节时uint32_t 和 uint8_t 数组之间的转换顺序会让你崩溃。最稳妥的做法是输入输出全部用 uint8_t 指针禁止把 state 强转成 uint32_t 再按数值运算。AES 所有变换都是字节级的跑在什么字节序的 CPU 上结果都应该一致。4.2 可编译运行的 AES 核心函数把上面这些函数拼起来一个最小可验证的 AES 核心片段是这样的#include stdio.h #include stdint.h uint8_t xtime(uint8_t a) { uint16_t t (uint16_t)a 1; if (t 0x100) { t ^ 0x1B; } return (uint8_t)t; } uint8_t gmul(uint8_t a, uint8_t b) { uint8_t p 0; for (int i 0; i 8; i) { if (b 1) { p ^ a; } a xtime(a); b 1; } return p; } void shift_rows(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]; } for (int c 0; c 4; c) { s[r][c] tmp[(c r) % 4]; } } } 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] gmul(a0, 2) ^ gmul(a1, 3) ^ a2 ^ a3; s[1][c] a0 ^ gmul(a1, 2) ^ gmul(a2, 3) ^ a3; s[2][c] a0 ^ a1 ^ gmul(a2, 2) ^ gmul(a3, 3); s[3][c] gmul(a0, 3) ^ a1 ^ a2 ^ gmul(a3, 2); } } int main(void) { uint8_t s[4][4] {{0}}; s[0][0] 0xdb; s[1][0] 0x13; s[2][0] 0x53; s[3][0] 0x45; mix_columns(s); printf(0x%02x 0x%02x 0x%02x 0x%02x\n, s[0][0], s[1][0], s[2][0], s[3][0]); return 0; }这个程序编译运行后应该输出 0x8e 0x4d 0xa1 0xbc。如果你看到这个结果说明 xtime 和 gmul 的有限域乘法实现是正确的列混淆矩阵方向也写对了。这个测试比拿完整 AES 加密结果对比更直接因为完整实现里还有 S 盒和轮密钥扩展一旦结果不对你根本不知道错在哪一个环节。4.3 从核心函数到完整 AES-128还差什么行移位和列混淆只是轮函数的一部分。要跑通完整的 AES-128你还需要SubBytes用 256 字节的 S 盒表把每个字节替换掉解密时用逆 S 盒。AddRoundKey把 16 字节轮密钥按列优先填充成矩阵逐字节异或到状态上。Key Expansion从 16 字节主密钥生成 11 组轮密钥第 0 轮用主密钥之后每轮 16 字节。AES-128 是 10 轮但初始 AddRoundKey 也算一次所以需要 11 个轮密钥。轮函数编排前 9 轮做完整的 SubBytes、ShiftRows、MixColumns、AddRoundKey最后一轮省略 MixColumns。如果你要写完整实现我建议按这个顺序推进先实现并验证 S 盒再实现并验证密钥扩展最后把轮函数串起来。每完成一步都打印中间状态不要一口气写完再调试否则出了错很难定位。4.4 用标准向量自查别相信感觉完整实现完成后用 FIPS-197 附录里的标准向量做最终验证。最著名的一个是密钥000102030405060708090a0b0c0d0e0f明文00112233445566778899aabbccddeeff密文69c4e0d86a7b0430d8cdb78070b4c55a如果你的程序加密结果不是这一串说明某个环节还有错。此时不要急着猜把每一轮 SubBytes 之后、ShiftRows 之后、MixColumns 之后的状态打印出来和 FIPS-197 里提供的中间值逐个核对。这个习惯能把你排查问题的时间从一天缩短到半小时。5. 常见问题与排查技巧实录5.1 解密结果不对大概率是列混淆矩阵用错我在群里看到新手问得最多的问题就是“我的加密结果是正确的但解密出来是乱码。”这种情况十有八九是解密时没有用逆列混淆矩阵而是把加密矩阵的系数照抄了一遍。加密矩阵系数是 2、3、1、1解密矩阵系数是 14、11、13、9两者差别很大只靠“反着写一遍”是推不出来的必须查标准里的逆矩阵。排查步骤很简单先用一个已知密钥和明文跑加密确认密文和标准向量一致然后在解密函数里只处理一轮把解密第一轮结束后的状态和标准值对照。如果解密第一轮就错肯定是 inv_mix_columns 或 inv_shift_rows 的问题。如果第一轮对、后面错再去查逆 S 盒和轮密钥扩展。5.2 xtime 的溢出判断为什么不能写在左移之后有人写 xtime 时会这么写uint8_t wrong_xtime(uint8_t a) { a 1; if (a 0x100) { // 永远进不来 a ^ 0x1B; } return a; }这段代码看着逻辑没问题实际上 a 是 uint8_t左移一位后的第 8 位早就被截断了a 0x100 永远是 0。正确的做法是先用 uint16_t 暂存左移结果或者用原来的最高位做判断uint8_t xtime(uint8_t a) { return (uint8_t)((a 1) ^ ((a 0x80) ? 0x1B : 0x00)); }这个写法利用整数提升a 会先提升成 int 再左移所以不会截断但判断的是原始最高位。两种写法都对看代码习惯。关键是搞清楚溢出的判断依据是“原始字节的最高位是否为 1”不是左移后的结果。5.3 想提速用预计算表替代逐次乘法通用 gmul 每调用一次要做 8 次循环MixColumns 里每个输出字节要调 4 次 gmul一列输出要 16 次整个状态 4 列就是 64 次。加密 10 轮就是 640 次。虽然一次 gmul 才几微秒但在嵌入式平台上这就是负担。常见的优化方式是把乘 2、乘 3、乘 9、乘 11、乘 13、乘 14 的表提前算好查询时直接按下标取static uint8_t gm2[256]; static uint8_t gm3[256]; static uint8_t gm9[256]; static uint8_t gm11[256]; static uint8_t gm13[256]; static uint8_t gm14[256]; void init_gmul_tables(void) { for (int i 0; i 256; i) { gm2[i] gmul(i, 2); gm3[i] gmul(i, 3); gm9[i] gmul(i, 9); gm11[i] gmul(i, 11); gm13[i] gmul(i, 13); gm14[i] gmul(i, 14); } }加密时调用 gm2[a] ^ gm3[a1] ^ a2 ^ a3解密时查 gm14/gm11/gm13/gm9。速度能提升一个数量级代码可读性也不会差太多。更先进的做法是 OpenSSL 里那种 4 张 T 表把 MixColumns 和 AddRoundKey 融合在一起那就属于协议栈级别的优化了业务代码一般用不上。5.4 工程化提醒固定宽度类型、字节序与可移植性写 AES 这类算法C 语言里必须用标准固定宽度类型也就是 stdint.h 里的 uint8_t、uint32_t不要用 char、int。原因很简单char 的符号性由平台决定int 最短 16 位这些都会影响移位和异或的结果。uint8_t 保证 8 位无符号所有位运算行为可预测。字节序问题前面也说过这里再强调一次AES 标准是按字节流定义的和 CPU 是大端还是小端无关。如果你在 x86 上调通了把代码原样挪到 ARM 上也应该调通前提是你没有用指针强转把字节流当成 uint32_t 数组来读。用 uint8_t 数组作为唯一的外部接口可以规避绝大多数可移植性问题。另一个容易被忽略的是内存对齐。虽然 uint8_t 数组没有对齐要求但如果你在嵌入式平台开了优化并且把 state 定义成局部二维数组有些编译器会做栈上重排。如果你把所有状态都限制在固定数组里并且只通过函数参数传递地址这类优化问题基本不会碰到。5.5 关于“每次加密结果都不一样”的常见困惑网络热词里有个提问是“AES 什么模式每次加密结果都不一样”这里顺手解释一下。AES 本身是分组密码同样的明文、同样的密钥、同样的模式在 ECB 模式下每次加密结果必然是相同的。但如果你用 CBC 模式每次加密会生成一个随机 IV初始化向量跟第一块明文异或之后再加密所以每次结果都不同。CTR 模式类似每次会选不同的 nonce 和计数器初始值。所以“每次结果不同”不是 AES 算法的特性而是模式里的随机向量在起作用。自己写代码做测试时如果要复现标准向量一定要用 ECB 模式或者把 CBC 的 IV 固定成全零。否则你拿着随机 IV 去对标准向量永远对不上。5.6 调试小技巧逐轮打印中间状态写 AES 这类算法最忌讳“写完一把梭”。我习惯在开发阶段加一个调试开关在 SubBytes、ShiftRows、MixColumns、AddRoundKey 每个变换后都打印状态矩阵。标准里给出了每个中间状态的参考值你只要打印出来一行一行比马上知道是 S 盒表错、行移位方向错还是列混淆系数错。打印格式建议统一用十六进制、两个字符补零、每 4 个字节一组例如round 1 after ShiftRows: 82 c9 7d ca ...这样跟 FIPS-197 的表格可以直接对比。调试全部通过之后再把打印关掉或加宏控制不要留着 printf 进生产代码。嵌入式的串口输出很慢调试信息全开的话加密一次可能要多花几十毫秒。6. 最后动手调试时我的习惯写到这里我想分享一个自己调试 AES 实现最受益的习惯永远先验证最小单元再集成。很多人拿到 AES 就急着把 S 盒、密钥扩展、轮函数全部写完然后跑一遍发现不对开始怀疑人生。我的做法是先写 xtime用 0x57×0x130xFE 验证再写 gmul用随机组合对比标准值再写 mix_columns用 0xdb/0x13/0x53/0x45 那组数据验证最后才拼完整轮函数。每做一步都有确定性的答案兜底出错了也只用怀疑最近改动的那几行。如果你只是想在项目里用 AES完全没必要自己实现优先选 mbedTLS、OpenSSL 这类经过审计的库。但如果你想搞懂内部机制或者在资源受限的平台上按需裁剪优化把行移位和列混淆亲手写一遍是最值得投入的时间。至少我做完这件事之后再看任何 AES 的 C 语言实现脑子里都能直接映射到状态矩阵上不用再对着框图发呆。
