Rijndael算法深度解析：从核心变换到抗差分攻击设计

聊分组密码的时候Rijndael这个名字经常被一笔带过很多人只知道它是AES的前身入选之后就被当成了AES的代名词。但如果你真的把Rijndael的设计文档摊开来看会发现这个算法值得细品的地方太多了它在效率、安全性和可实现性之间做到了一个非常漂亮的平衡是那种“越看懂越佩服”的设计。我身边不少搞安全和写协议栈的朋友第一步都是先手推一轮Rijndael加密比直接背一堆AES API调用有用得多。这篇文章想跟你聊的是Rijndael背后真正核心的东西四大变换为什么这么设计、密钥扩展有什么讲究、它凭什么能扛住差分攻击顺手再把最近网上很火的一个问题“SM3密码杂凑算法的P置换中有1比特输入差分输出差分有多少比特”也一并讲透。不管你是刚接触密码学还是已经在工程里用了很久AES这篇应该都能给你一些新的视角。1. Rijndael是什么AES背后的迭代分组密码1.1 从两个比利时人说起Rijndael这个名字是两位比利时密码学家Joan Daemen和Vincent Rijmen姓氏的组合读起来大概类似“Rain-doll”。1997年美国国家标准与技术研究院NIST公开征集新一代高级加密标准算法接收了来自全球的15个候选方案。最终进入决赛的几个算法里Rijndael凭借安全、性能、实现灵活等综合表现胜出2001年被正式采纳为FIPS 197标准也就是我们今天常说的AES。这里有个细节很多人第一次接触时会搞混Rijndael本身并不是一个严格的“标准算法名”它只是提交时的原始算法名称。NIST在标准化时做了一处关键改动——Rijndael原本支持多种分组长度128位、192位、256位但AES标准只固定了分组长度为128位密钥长度保留了128位、192位、256位三种。所以严格说AES是Rijndael的一个子集。现在密码学教材里说的“Rijndael算法”默认讨论的是完整版本而工程里说的“AES”绝大多数时候指的就是分组128位、密钥长度可选的这个标准版本。1.2 设计理念安全、高效、简单Rijndael的设计目标说起来很朴素做起来却极难第一要能抵抗已知的所有攻击方法尤其是差分密码分析和线性密码分析第二要在各种平台上都有优秀的实现性能从8位单片机到带硬件指令的现代CPU都不能太慢第三要保持结构的简单和优雅方便分析和审计。为了达成这三个目标Daemen和Rijmen选择了迭代分组密码结构SPN代换-置换网络。每一轮加密对状态矩阵依次做四件事字节代换SubBytes、行移位ShiftRows、列混合MixColumns和轮密钥加AddRoundKey。前三者负责混淆和扩散最后一个负责把密钥信息掺入数据流。轮数由密钥长度决定128位密钥10轮192位密钥12轮256位密钥14轮。需要说明的是这里的“轮”指的是普通轮实际每一轮结束前都要额外做一次轮密钥加整体流程还包括最前面的初始轮密钥加和最后一轮省略列混合的处理。1.3 一次看懂状态矩阵Rijndael处理的最小单位是字节所有运算都在一个4行4列的字节矩阵上进行这个矩阵叫作“状态”state。一个128位的分组就是16个字节按列优先的顺序填入矩阵输入的前4个字节填第0列接下来4个字节填第1列以此类推。后面我们讲行移位、列混合的时候都是基于这个状态矩阵展开的所以列优先这个习惯要先记住否则看代码的时候很容易被绕晕。2. 把Rijndael拆开四大核心变换详解2.1 SubBytes非线性来自有限域SubBytes是Rijndael中唯一一个非线性变换也是整个算法抗差分攻击和线性攻击的第一道防线。它做的事很简单把状态矩阵里的每一个字节通过一张固定的S盒查表替换成另一个字节。问题在于这张S盒不是随便拍脑袋生成的它背后有严格的数学构造。S盒由两步组成。第一步把字节看成GF(2^8)有限域上的元素求它的乘法逆元。这里用的不可约多项式是x^8 x^4 x^3 x 1也就是十六进制的0x11B。全零字节的逆元定义为它自身在有限域中0没有逆元但设计中把它映射到0。第二步对逆元结果做一次仿射变换。仿射变换的作用是打破逆元运算中可能存在的代数简单性避免整个S盒被表示成过于简单的幂函数形式。打个比方乘法逆元就像把数字变成倒数但倒数的分布还是有一些规律可循仿射变换就像把这个规律再揉碎了一次让输入每一个比特的变化都尽可能影响输出多个比特。这样设计出的S盒最大差分概率和最大线性偏差都被控制在了非常低的水平为后面的宽轨迹策略打下了基础。造S盒的Python代码可以这样写我这里为了清晰直接用按位操作实现仿射变换def gf_mult(a, b): res 0 while b: if b 1: res ^ a a 1 if a 0x100: a ^ 0x11B b 1 return res 0xFF def affine_transform(b): res 0 for i in range(8): bit ((b i) 1) ^ \ ((b ((i4) % 8)) 1) ^ \ ((b ((i5) % 8)) 1) ^ \ ((b ((i6) % 8)) 1) ^ \ ((b ((i7) % 8)) 1) ^ \ ((0x63 i) 1) res | bit i return res def build_sbox(): inv [0] * 256 for x in range(256): for y in range(256): if gf_mult(x, y) 1: inv[x] y break return [affine_transform(b) for b in inv] SBOX build_sbox()这段代码的求逆部分用了最朴素的穷举效率很低只是为了说明原理实际工程里S盒都是预计算好的查找表。仿射变换里的0x63就是AES标准里的常数c。生成完可以验证一下SBOX[0x53]应该等于0xED网上所有AES S盒表都能对得上。2.2 ShiftRows行方向的扩散ShiftRows的作用是把状态矩阵里每一行的字节循环左移不同位数。第0行不动第1行左移1个字节第2行左移2个字节第3行左移3个字节。这样做的效果是原本只落在某一列里的信息经过一次行移位就散布到了不同的列。为什么需要这一步因为接下来要做的MixColumns是针对每一列独立操作的如果列之间没有交流那么某一列的差分或线性特征就不会扩散到其他列整个算法就退化成每4个字节独立加密安全性大打折扣。ShiftRows和MixColumns配合才真正形成了“列与列之间的交叉感染”。这里有一个很容易犯的错很多资料用行优先的矩阵图讲ShiftRows你自己写代码时状态却是列优先存储的移位方向和索引很容易搞反。我建议写代码时直接用通用公式new_state[(c r) % 4][r] state[c][r]这样按列遍历最不容易出错。2.3 MixColumnsMDS与列方向的雪崩MixColumns是Rijndael里最“数学”的一步。它把状态矩阵的每一列看成一个四维向量然后用一个固定的矩阵去乘这个向量。矩阵的第一行是[2, 3, 1, 1]第二行是[1, 2, 3, 1]第三行是[1, 1, 2, 3]第四行是[3, 1, 1, 2]所有乘法和加法都在GF(2^8)上完成。这背后的设计思想非常关键这个矩阵是一个MDS最大距离可分矩阵它的差分分支数达到了5。所谓差分分支数可以理解成一个非零字节经过列混合后输入和输出中非零字节总数的最小值。这里输入列有4个字节输出列也有4个字节MDS保证了输入列和输出列加起来至少会有5个字节非零。这意味着即使输入列只有1个字节发生变化输出列的4个字节也会全部发生变化即使输入列有2个字节变化输出列至少还有3个字节发生相应变化。这种扩散能力是抵抗差分密码分析的核心支柱。用代码实现MixColumns时有一个小技巧乘2和乘3都可以用xtime操作来加速。乘2就是左移一位溢出就异或0x11B乘3就是先乘2再异或原数。def mix_columns(state): new [[0]*4 for _ in range(4)] for c in range(4): a0, a1, a2, a3 state[c] new[c][0] gf_mult(a0, 2) ^ gf_mult(a1, 3) ^ a2 ^ a3 new[c][1] a0 ^ gf_mult(a1, 2) ^ gf_mult(a2, 3) ^ a3 new[c][2] a0 ^ a1 ^ gf_mult(a2, 2) ^ gf_mult(a3, 3) new[c][3] gf_mult(a0, 3) ^ a1 ^ a2 ^ gf_mult(a3, 2) return new这里需要注意列混合处理的是状态矩阵的每一列而不是每一行。不少初学者一上来就看矩阵乘法公式把行和列搞混结果整个加密流程的结果永远对不上标准测试向量。2.4 AddRoundKey密钥进入的入口AddRoundKey是整个加密流程里最简单的一步把状态矩阵的每一列与对应位置的轮密钥字节做异或。之所以把它放在SubBytes、ShiftRows、MixColumns之后是因为异或本身不提供任何混淆和扩散作用但它能把密钥的随机性注入到数据流中让整个变换依赖密钥。轮密钥不是直接用主密钥而是通过密钥扩展算法生成的。每一轮使用4个字每字4字节一个128位分组需要44个字的扩展密钥分别用于第0轮的初始白化、中间10轮每轮4个字和最后一轮再4个字。可以理解为把一把主密钥拉伸成一长串子密钥每轮用不同的一段即使某一轮的子密钥泄露也不至于直接推回主密钥。3. 从密钥到轮密钥密钥扩展算法3.1 三个辅助函数RotWord、SubWord、Rcon密钥扩展的核心逻辑简单说就是一边把上一轮的字复制过来一边进行各种搅和。以128位密钥为例初始的4个字直接取自主密钥之后每个新字都是前一个字和4个位置之前的字异或得到的。每遇到i能被4整除的位置就要对前一个字做一次特殊处理先循环左移一个字节RotWord再逐字节过S盒SubWord最后异或上一个轮常量Rcon。Rcon的生成规则是Rcon[1] 0x01Rcon[i] xtime(Rcon[i-1])。也就是说Rcon[i]是GF(2^8)中x^(i-1)的幂次表示。这个轮常量的作用是破坏密钥扩展的对称性防止不同轮的子密钥出现规律性的相似结构。代码可以这样写RC [0] * 11 RC[1] 0x01 for i in range(2, 11): RC[i] gf_mult(RC[i-1], 2) def key_expansion(key): # 仅支持128位密钥Nk4生成44个字 w [[key[4*i j] for j in range(4)] for i in range(4)] for i in range(4, 44): temp w[i-1][:] if i % 4 0: temp temp[1:] temp[:1] # RotWord temp [SBOX[x] for x in temp] # SubWord temp[0] ^ RC[i // 4] # Rcon w.append([w[i-4][j] ^ temp[j] for j in range(4)]) return w3.2 192位和256位密钥的边界条件完整版Rijndael密钥扩展不止这一种情况。当密钥长度为192位时初始有6个字每次生成一批也按6个字的节奏推进最终需要的字数是52个当密钥长度为256位时初始有8个字最终需要的字数是60个。关键区别是对于256位密钥每遇到i mod 8 4的位置要额外做一次SubWord操作。这个设计是有原因的。如果不同时做SubWord密钥扩展的非线性程度在某些密钥长度下会不够强可能让子密钥之间出现代数关联。很多只写过128位版本的教学代码一旦改成256位就直接跑挂多半就是漏了这个条件。工程实现里这个分支处理一定要写清楚。4. 安全性分析Rijndael凭什么防住差分攻击4.1 宽轨迹策略与活跃S盒差分密码分析的思路是通过构造特定输入差分观察它经过多轮加密后在输出端扩散成什么样子从而反推密钥。Rijndael抵御这种攻击的底气来自于所谓的“宽轨迹策略”Wide Trail Strategy。这个策略不追求在单轮内做到完全扩散而是通过精心设计线性层ShiftRows MixColumns和非线性层SubBytes交替堆叠让差分在穿透每一轮时经过的“活跃S盒”数量快速增加。活跃S盒就是输入差分非零的那些S盒。S盒是算法中唯一的非线性部件攻击者需要猜测的活跃S盒越多攻击的成本就越高。由于S盒的最大差分概率已经被压到2^-6左右MixColumns的MDS属性又保证了活跃S盒数量的下界会随着轮数增长迅速上升到了10轮以后想通过差分路径恢复密钥的计算量早就超出了穷举搜索的代价。这也是Rijndael设计上最令人叹服的地方它的安全边界不是靠“看起来复杂”堆出来的而是有清晰的数学证明链条。4.2 热词延伸SM3的P置换1比特差分输出多少比特最近网上有个很有意思的问题“SM3密码杂凑算法的P置换中有1比特输入差分输出差分有多少比特”这个问题初看很简单但很容易答错因为它涉及对线性置换差分传播的精确理解。SM3里有两种P置换压缩函数中的P0和消息扩展中的P1都是32位输入、32位输出P0(X) X ^ (X 9) ^ (X 17)P1(X) X ^ (X 15) ^ (X 23)这里的表示循环左移。如果输入差分ΔX只有1个比特为1比如第i位为1那么输出差分就是ΔY ΔX ^ (ΔX 9) ^ (ΔX 17)这个异或结果在三个位置会置1原来的第i位、左移9位后的第(i9) mod 32位、左移17位后的第(i17) mod 32位。关键问题是这三个位置会不会重合不会。因为9、17、26这三个差值都不是32的倍数任意两个位置都不可能重叠。所以P0的输出差分正好是3比特。P1的推导完全一样15、23、8这三个差值也都不是32的倍数因此答案同样是3比特。所以当你听到“SM3的P置换1比特输入差分输出多少比特”这个问题时标准答案就是3比特。当然如果问的是整个消息扩展把16个字变成68个字的整体置换那差分会在不同字之间传播情况就会复杂得多不能简单用“多少比特”来回答了。这个例子特别适合和Rijndael的MixColumns做对比。Rijndael的列混合是MDS矩阵1个字节差分经过列混合后输出列4个字节全部非零也就是说输入输出非零字节数之和达到了5这是线性层的扩散能力上限。而SM3的P0/P1作为一个轻量级的线性置换1比特差分扩散成3比特扩散比率大约是1:3明显弱于MDS。这不是说SM3设计有问题而是两者在算法中的角色不同SM3靠64轮迭代来积累扩散效果单轮不要求做到极限Rijndael轮数少每一轮都必须尽可能把差分打散。理解了这一点你会对“扩散度”和“轮数”之间的取舍有更深的体会。5. 用Python手写一个极简Rijndael5.1 准备工作有限域运算与查表法有了前面的基础我们可以写一个能跑的教学版Rijndael实现。目标不是做出生产级代码而是通过代码把每个变换的输入输出串起来让算法不再停留在纸面上。先解决底层的有限域乘法。前面已经给出了gf_mult函数这是所有GF(2^8)运算的基础。实际工程中为了速度一般会预计算三个查找表2倍表、3倍表、9倍表、11倍表、13倍表、14倍表用查表代替循环乘法。但在教学代码里循环乘法的可读性更好也能帮助理解数学本质。S盒和逆S盒可以直接用前面build_sbox函数生成不需要手工录入几百个数字。生成一次之后如果嫌慢可以把SBOX打印出来存成常量以后直接引用。5.2 核心代码轮变换与加密过程把前面各个变换拼在一起加密一个分组的完整逻辑是def shift_rows(state): new [[0]*4 for _ in range(4)] for r in range(4): for c in range(4): new[(c r) % 4][r] state[c][r] return new def add_round_key(state, round_keys, rnd): for c in range(4): for r in range(4): state[c][r] ^ round_keys[4*rnd c][r] def encrypt_block(plain, key): # 按列优先把16字节明文填入状态矩阵 state [[plain[4*i r] for r in range(4)] for i in range(4)] round_keys key_expansion(key) add_round_key(state, round_keys, 0) for rnd in range(1, 10): for c in range(4): for r in range(4): state[c][r] SBOX[state[c][r]] state shift_rows(state) state mix_columns(state) add_round_key(state, round_keys, rnd) # 最后一轮省略MixColumns for c in range(4): for r in range(4): state[c][r] SBOX[state[c][r]] state shift_rows(state) add_round_key(state, round_keys, 10) return bytes(state[c][r] for c in range(4) for r in range(4))这段代码只支持128位密钥和128位分组。你可以用NIST标准文档里的AES-128测试向量来验证正确性例如密钥为2b7e151628aed2a6abf7158809cf4f3c明文为6bc1bee22e409f96e93d7e117393172a时加密结果应为3ad77bb40d7a3660a89ecaf32466ef97。如果输出对不上优先检查三个地方状态的列填充方式、ShiftRows的索引公式、密钥扩展的i % 4分支。5.3 实操中容易踩的坑写这个教学实现时我踩过几个印象很深的坑。第一个是状态矩阵的行列顺序这个前面反复强调过列优先填充和列优先读取必须全程一致。第二个是ShiftRows的实现方向网上有些代码用行优先数组写直接搬过来很容易把“左移”写成“右移”密文完全对不上。第三个是最后一轮不要忘记省略MixColumns这是AES结构定义的一部分漏掉或误加都会导致结果错误。还要郑重提醒一下这种纯Python实现绝对不能用于生产环境。原因有很多性能只是其次更重要的是侧信道攻击——Python的字节数组索引和分支操作计时不稳定攻击者可以通过测量加密时间反推出密钥的一部分。真要在产品里用AES请使用OpenSSL、libsodium这些经过审计的密码库或者直接用CPU的AES-NI指令。手写实现的意义在于学习和验证不在于替换成熟库。6. 工程实践Rijndael在真实世界的落脚点6.1 你每天都在用AESAES可以说是现代互联网加密的地基。TLS/SSL协议里对称加密部分最常用的就是AESWiFi的WPA2/WPA3加密使用AES全盘加密工具比如BitLocker、FileVault底层同样是AES数据库加密、压缩包加密、密码管理器的主密码派生到处都能看到AES的影子。虽然协议层还在不断演进但AES短时间内的地位依然非常稳固。Rijndael作为AES的前身在这些场景里的实际使用方式和标准AES几乎一致只不过标准AES固定了128位分组。那些支持192位、256位分组完整版Rijndael的场景反而比较少见主要出现在一些特定密码协议和学术研究中。日常调API时你看到的大多数AES函数用的都是128位分组、CBC或GCM模式。6.2 性能优化路径AES之所以能在各种设备上全面铺开和它的硬件支持密不可分。现代x86和ARM处理器基本都内置了AES指令集比如x86的AES-NI一条指令就能完成一轮AES的核心操作吞吐量可以达到每秒几十GB。软件实现方面经典做法是预计算T表把SubBytes和MixColumns合并成4张1KB查找表用查表代替逐字节计算更进一步的位切片技术则把多个分组打包成位平面并行处理适合在无AES指令的老平台上追求速度。如果你自己实现了Rijndael做性能测试会发现纯Python版本跑一个分组都要几十微秒而OpenSSL的AES-NI实现跑同样大小数据可能快好几个数量级。这个对比不是没有意义它能直观告诉你硬件加速和软件算法优化之间的差距到底有多大。6.3 常见误区关于Rijndael/AES有几个误区在社区里反复出现。第一Rijndael不等于AESAES只是Rijndael的128位分组版本第二AES加密时必须配合工作模式使用千万别用ECB模式把每个分组独立加密分组之间完全独立会导致同样的明文块得到同样的密文块信息泄露非常严重第三密钥长度越长不代表实际场景越安全128位密钥的暴力破解在现代技术下已经非常困难很多时候真正需要关注的是密钥管理和协议设计。最后说点我自己的经验。每接触一个新的分组密码我都会先手动推导一轮加密的全部过程再落到代码里验证一次标准测试向量。这个过程听起来麻烦但比通读十篇综述都有用。Rijndael的巧妙之处你在纸上推演MixColumns和ShiftRows怎么配合时感受最深——那种“每一轮都在把数据彻底打散”的感觉是只看代码体会不到的。如果你也想深入理解现代密码算法Rijndael绝对是一个最好的起点。