许多搞密码学的人第一次注意到“Rijndael”这个名字是在翻AES相关文档时看到一句“AES使用Rijndael算法”的描述。大多数人会把两者直接划等号我最早也是这样。直到后来我照着原始提案《The Design of Rijndael》写了一个支持任意分组长度的实现才发现这中间有不少细节和FIPS 197标准不一样。那段时间踩了不少坑也逼着我重新梳理了这个算法的设计逻辑。今天想把这些东西整理出来给准备深入AES、做对称加密实现或者做密码学作业的同学一些参考。这篇文章会覆盖Rijndael的竞标背景、状态阵列和四轮变换的数学原理、它和AES标准之间的微妙差别以及我在实际落地中遇到的几个高频问题。最后我会用一个最近总被问到的话题收尾SM3杂凑算法的P置换中1比特输入差分到底对应多少比特输出差分。这个问题看起来和Rijndael无关但本质上是在讨论扩散性和我们前文讲的MixColumns设计思路是同一件事。1. 为什么Rijndael能在AES竞标中胜出1.1 DES退役后的明牌需求上世纪九十年代末DES已经明显撑不住了。56位密钥的暴力破解在1997年就已经被分布式攻击验证电子前沿基金会造的Deep Crack机器能在几十小时内解出DES密钥。密码学界和工业界都需要一个新的分组密码标准要求也很明确分组长度128位密钥长度128、192、256位可选安全性至少和3DES同级而且要能在各种软硬件平台上高效运行。这个需求由NIST在1997年向社会公开征集前后收到了15个候选算法经过两轮筛选后1999年8月公布了五个决赛算法MARS、RC6、Rijndael、Serpent和Twofish。这五个算法代表了当时四种完全不同的设计流派。1.2 五个决赛达人的优缺点博弈我简单盘一下这五个算法的风格Serpent设计者想用非常高的安全冗余来彻底消除结构风险于是做了32轮迭代每轮只有简单的异或和S盒替换。它在抗差分分析和线性分析上的指标非常好但速度在当时的软件平台上相对偏慢。RC6依赖32位整数的循环移位和乘法运算充分利用Rivest家族在RC5上的经验。在32位处理器上速度极快但结构相对“简单”安全论证不如一些候选充分。MARSIBM设计混合了多种操作像Feistel网络和查找表的结合体。功能强但结构复杂难以给出简洁的安全推导。TwofishBruce Schneier带队使用16个S盒和复杂的密钥依赖置换理论上很漂亮但实现时需要预先计算大量S盒内容在资源受限设备上开销比较大。RijndaelJoan Daemen和Vincent Rijmen这对比利时学者提交的算法用简洁的方形状态阵列把一个字节的替换、一行一列的位移和矩阵乘法组合起来形成了高度规则的结构。最后一轮评选中Rijndael的分组长度和密钥长度都灵活可变风雪开销小软硬件实现曲线平滑同时安全分析结果也很扎实。所以在2000年10月NIST宣布Rijndael成为AES算法。1.3 Rijndael胜出的三个关键因素如果从今天回看Rijndael赢在三个层面第一安全上的充分冗余与可证明性之间的平衡。它没有像Serpent那样极端但通过宽轨迹策略给差分分析和线性分析提供了严格下界而且经过公开征集、多轮评估后没有发现有效攻击。第二软硬件表现全线能打。Rijndael的轮结构只需要查表、异或、移位三种基础运算8位MCU上可以逐字节处理32位处理器上可以用T表合并多步到现代x86 CPU上又催生了AES-NI指令集实现成本不断降低。第三设计的优雅和可调试性。它的S盒公式公开、有限域运算规则透明测试向量多到可以直接用来查错。这是一个对实现者非常友好的算法比那些内部耦合度高的结构容易理解得多。2. 把Rijndael拆开看状态阵列、密钥扩展与四轮变换2.1 状态State从128比特串到4×4矩阵Rijndael内部处理的数据单位是一个叫“状态”的二维字节数组。对于AES标准常见的128位分组来说状态就是4行4列共16个字节初始填入顺序是逐列从上到下填入。比如明文的前4个字节填第0列接下来4个字节填第1列以此类推。这种“列优先”的排布方式和大多数程序员习惯的“行优先”思维不太一样我在第一次写实现时就在这里排错过。如果看Rijndael原始提案状态的行数Nb会被固定为4但列数可以随分组长度变化分组128位时Nb4192位时Nb6256位时Nb8。密钥同样以列为单位排列列数Nk分别为4、6、8。NIST在标准化时把分组长度钉死在128位后面的章节我会再细说这里面的差异。2.2 轮变换一SubBytes与S盒的数学设计每一轮里数据经历四个变换SubBytes、ShiftRows、MixColumns、AddRoundKey。SubBytes是唯一的非线性操作。它的做法是把状态里的每个字节独立替换成S盒中的另一个字节。Rijndael的S盒不是拍脑袋生成的表而是两步数学运算的结果。第一步是在GF(2^8)有限域中求乘法逆元。GF(2^8)可以理解为由0x1B参与约简的256元素域Rijndael选择的多项式是m(x) x^8 x^4 x^3 x 1也就是十六进制的0x11B。一个字节A的逆元A^{-1}满足 A × A^{-1} ≡ 1 mod m(x)特殊地0的逆元在Rijndael中被规定为0。第二步是对逆元做仿射变换输出比特是输入比特与一个固定矩阵相乘后再异或常数0x63。这个仿射变换的主要目的不是增加线性强度而是打破S盒的代数简单性避免出现类似“输入为0时输出为0”这类容易被利用的性质。有人问我能不能不查表直接现场算逆元可以但每次调用都会经历求幂或扩展欧几里得算法性能极慢。实际工程中要么在初始化阶段把256字节S盒预先算好存进内存要么直接硬编码常量数组。S盒的查表实现很快因为一张表只有256字节在缓存里能完全命中。2.3 轮变换二ShiftRows和MixColumns如何完成扩散ShiftRows是一个行移位操作。状态矩阵的第0行不动第1行循环左移1个字节第2行循环左移2个字节第3行循环左移3个字节。这个操作的目的是让列之间的数据相互交缠为后续MixColumns产生跨列扩散创造条件。MixColumns是Rijndael中最能体现代数设计的地方。它把状态的每一列看作一个四字节向量然后与一个固定的4×4矩阵在GF(2^8)上做乘法。对于一列输入(a0, a1, a2, a3)输出(b0, b1, b2, b3)满足b0 2·a0 ⊕ 3·a1 ⊕ 1·a2 ⊕ 1·a3b1 1·a0 ⊕ 2·a1 ⊕ 3·a2 ⊕ 1·a3b2 1·a0 ⊕ 1·a1 ⊕ 2·a2 ⊕ 3·a3b3 3·a0 ⊕ 1·a1 ⊕ 1·a2 ⊕ 2·a3这里的2·x和3·x都是在GF(2^8)下定义的乘法。乘2可以写成旁段逻辑x左移一位如果最高位溢出就异或0x1B。乘3就是乘2再加自身。之所以选这个矩阵是因为它是一组MDS码的生成矩阵分支数达到5。分支数的含义是输入列差分和输出列差分的非零字节数之和至少为5。换句话说如果输入只有1个字节变化输出必然4个字节全部变化如果输入恰好有4个字节都变化输出列也至少有1个字节变化足以保证在经过两轮之后整个状态的活跃S盒数量有一个可靠的下界。这是Rijndael能抵抗差分密码分析的重要基础。2.4 轮变换三AddRoundKey与密钥扩展AddRoundKey最简单把状态与轮密钥逐字节异或。它在每一轮的开头或结尾各做一次保证密钥数据无法被绕过。密钥扩展的作用是把初始密钥扩展成(Nr1)个轮密钥。Rijndael的算法规则也很规整先按列填充初始密钥然后对于后续每一列如果列号是Nk的倍数先把前一列循环移位、逐字节S盒替换再异或上一个轮常数Rcon否则直接异或前一列。轮常数是一个从GF(2^8)生成的序列比如第一轮是0x01第二轮是0x02第三轮是0x04依次翻倍遇到0x80之后会异或0x1B回到域内换算。有一个容易搞混的点轮常数只在固定间隔被引入它的存在是为了破坏不同轮之间密钥调度的对称性。如果去掉这些常数攻击者可能会看到重复的轮密钥模式。我在实现时曾因为把轮常数索引写错导致加密能对上、解密却怎么都对不上最后用中间的已知轮密钥调试才定位到问题。2.5 用数学语言总结一轮变换如果用一个广义公式表达一轮操作可以写成Round(State, K_i) AddRoundKey(MixColumns(ShiftRows(SubBytes(State))), K_i)但要注意AES标准里的最后一轮不执行MixColumns。这是为了在解密时保持相同的结构让加解密流程更适合用反向轮函数实现。如果你自己写解密流程需要把InvMixColumns放在AddRoundKey前面具体顺序在下文实现部分会展开。3. 容易忽略的版本坑Rijndael与AES标准并不相同3.1 分组长度和密钥长度的任意组合Rijndael的设计非常灵活。它原始支持的分组长度以位为单位可以是128、192、256密钥长度也同样是128、192、256。也就是说从理论上讲你可以用128位密钥配256位分组也可以用256位密钥配192位分组。你只需要按照规则确定状态列数Nb和密钥列数Nk然后计算轮数Nr max(Nb, Nk) 6比如128位分组加128位密钥轮数就是max(4,4)610192位分组加192位密钥轮数是max(6,6)612256位分组加256位密钥轮数是max(8,8)614。注意常规AES中的密钥越长轮数越多但分组长度其实也会影响轮数。这个公式在原始Rijndael文档里写得很清楚。3.2 AES为什么只保留了128位分组NIST在制定FIPS 197时只采用了128位分组长度。给出的原因是128位分组已经足够应对当时所有应用场景同时可以简化标准降低实现方的测试成本和互操作难度。更长的分组确实在大数据量的密码学操作中能提供更大的生日界安全余量但代价是密钥调度和状态操作复杂度上升。标准机构天然倾向“够用且统一”。于是市场上绝大多数AES库只实现“分组128位密钥128/192/256位”的固定组合。这本身没有错但你如果翻阅老旧的Rijndael实现代码或者遇到某个支持192位分组的库就必须小心它生成的密文与标准AES完全不兼容除非你明确知道自己需要的是什么。3.3 库实现差异与我的踩坑记录说一下我经历过的真实案例。早年在做一个遗留系统互通时对方说他们的加密接口用的是Rijndael发送过来一个十六进制密文要求我们用相同算法解密。我们这边直接用OpenSSL的AES-128-CBC解结果前16字节乱码。后来翻对方SDK发现它内部调用的是一个老旧的Rijndael实现并且把分组长度设成了192位。也就是说他在用一个非标准的变量分组长度为192位、密钥长度为128位。这个组合在标准AES里根本不存在。解决方式最终是在Python里找到了一个第三方库python-rijndael它支持传入block_size参数。代码类似这样from rijndael import Rijndael cipher Rijndael(key, block_size24) # 分组长度按字节数传192位24字节 plaintext cipher.decrypt(ciphertext_block)这个经历让我养成一个习惯任何时候看到“Rijndael”而没有标明“AES”时都要额外确认分组长度和密钥长度。这两个参数一旦错位加出来的密文完全对不上。4. 实战落地高效实现与安全强化的十个关键点4.1 不要用纯循环计算S盒用查表听上去像废话但确实有同学在性能敏感代码中直接调用一个计算S盒的函数每次加密都现场算逆和仿射变换。这样做不仅慢而且代码可读性极差。正确做法是初始化256字节的S盒和逆S盒表加密解密共用。如果空间更宽裕还可以预生成4张用于MixColumns的T表把SubBytes、ShiftRows和MixColumns合并成一次查表加异或。4.2 T表合并轮变换但要注意数据结构T表加速的基本思路是把列混合矩阵乘法和SubBytes合并起来对状态列的一字节输入输出一个32位值。每列直接用4次查表结果异或就能得到结果。常见的T表有T0、T1、T2、T3四张每张256个32位整数总共4KB左右。这在现代CPU上很适合放入L1缓存但在内存极小的MCU上反而可能因空间不够造成负担。因此嵌入式环境下更推荐逐字节计算模式空间换时间的取舍要按实际平台决定。4.3 AES-NI指令集从软件优化到硬件加速如果你在x86或ARM上做AES追求性能时第一步不是调代码而是看硬件是否支持AES-NI或ARMv8 Crypto扩展。AES-NI提供四条核心指令AESENC、AESENCLAST、AESDEC、AESDECLAST以及密钥扩展辅助指令AESKEYGENASSIST一条指令就能完成一轮加解密的核心变换。T表方案在软件层已经很优秀但和硬件指令比差距仍然很大。实际压测中同样一台服务器上AES-NI可以做到数GB/s甚至更高。不过要提醒一句AES-NI和OpenSSL库之间的对接是透明的你不需要自己写汇编。但如果你在做自定义协议想手动调用这些指令需要查CPU ID标志位做检测同时在Intel或ARM的数据手册里确认指令编码。4.4 解密算法的轮密钥顺序和逆变换顺序如果自己实现Rijndael解密最容易栽跟头的地方是轮顺序。加密轮顺序是SubBytes、ShiftRows、MixColumns、AddRoundKey。解密时不能简单地把四个变换都取逆就完事因为AddRoundKey在中间轮密钥加必须保持特定相对位置。标准解密步骤是初始轮AddRoundKey(最后一个轮密钥)重复Nr-1轮InvShiftRows、InvSubBytes、AddRoundKey、InvMixColumns最终轮InvShiftRows、InvSubBytes、AddRoundKey注意在解密轮中AddRoundKey和InvMixColumns的顺序是反的因为密钥加和逆列混合实际上满足可交换性这里提一句AddRoundKey是在状态上异或密钥InvMixColumns是对每个列做线性变换由于线性变换满足加法分配律可以先加后逆也可以先逆后加但实现时一般在InvShiftRows和InvSubBytes之后再加密钥再逆列混合顺序不能乱。我调试时写了一个错误版本把InvMixColumns放到了AddRoundKey之前导致只有第一个块能解对后续块全错。后来我把中间状态打印出来和官方测试向量逐轮比对才发现顺序问题。建议所有自己实现Rijndael的朋友都去下载“AES Known Answer Test”向量用KAT来校验每一轮中间值。4.5 侧信道攻击与常数时间实现Rijndael本身抵抗的是黑盒密码分析但如果你把它跑在物理设备上还要面对侧信道威胁。最常见的是时序攻击和功耗分析。如果你的S盒查找索引来源于密钥或密文那么不同的索引会导致不同缓存命中延迟或不同功耗特征攻击者可以利用统计方法恢复密钥。现代常量时间实现思路是禁止把密钥相关数据作为内存查表的索引用位运算和固定循环次数替代条件分支。举例说在软件中避免使用类似if (bit) swap(a,b)这种依赖密钥比特的分支而是用掩码完成交换。硬件层面使用AES-NI能极大降低软件查表的缓存抖动风险因为内部逻辑是把轮函数固化在电路中。4.6 常见库的“Rijndael”接口怎么看不同库对Rijndael的支持程度差异很大。OpenSSL和多数密码库里的AES_*函数只支持128位分组。Python的Crypto.Cipher.AES也是标准AES不允许你传192位分组。rijndael纯Python库支持更灵活的块大小。Java的AES/ECB/PKCS5Padding同样固定128位分组。在C#的RijndaelManaged类中有一个BlockSize属性默认128位但可以改成192或256。很多老项目在这里一改就会产生与标准AES不兼容的密文。所以看到“RijndaelManaged”时别想当然先看它的BlockSize是不是128。如果是192或256那它和“AES”就不是一回事。5. 扩散性对比Rijndael的列混合与SM3的P置换5.1 从1比特差分看扩散性密码算法的扩散性指输入中某一个比特变化能多快、多广地影响到输出状态。扩散性越强攻击者越难建立输入差分和输出差分之间的联系。Rijndael的ShiftRows和MixColumns的组合就是为了在几轮之内就让状态中所有字节都被“搅和”成高度纠缠。在Rijndael的列混合中分支数为5。这意味着如果某一列的输入差分非零字节数为d输出差分非零字节数至少是5-d。当d1时输出至少4个字节变化。这是一个数学上的硬保证不随具体随机测试而改变。5.2 SM3的P置换1比特输入差分到底输出几比特SM3是我国国密标准中的密码杂凑算法分组处理和消息扩展中都有一个线性置换P。SM3中的P置换定义如下P(X) X ⊕ (X 9) ⊕ (X 17)其中X是一个32位字表示循环左移。在很多场合人们也会在64位或更宽的字上讨论类似的结构。问题问的是如果P置换的输入只有1比特差分输出差分有多少比特答案是3比特。因为P是线性置换输入差分Δ会直接映射为输出差分Δout Δ ⊕ (Δ 9) ⊕ (Δ 17)如果Δ只有1个比特例如只有第i位是1那么Δout在三个不同位置上会出现1原来的第i位、循环左移9位后的第(i9) mod 32位、循环左移17位后的第(i17) mod 32位。这三个位置两两不同因为9、17、26这里注意32位下17与9差8不会重叠不能模32后与0相同且9≠17 mod 32。所以输出差分的汉明重量刚好是3。用式子表示就是wt(Δout) wt(Δ) wt(Δ 9) wt(Δ 17) 1 1 1 3但要注意这里假设初始的只有一个1比特和两个移位后的1比特互不重叠。在SM3的P置换中循环左移9位和17位都不会让这两个1恰好出现在同一个位置所以不会发生异或抵消。因此答案是3比特。我在一次密码学分享课上现场推过这个例子有不少人第一反应是“1比特输入差分输出差分不一定只有1比特”确实在线性变换下输入差分和输出差分之间并不保持汉明重量不变。只通过“1比特变1比特”或“1比特变多比特”来判断是否线性或非线性其实是不准确的。5.3 与MixColumns分支数5的对比把SM3的P置换和Rijndael的MixColumns做对比会更有意思。两者都是扩散层但后者的“分支数”要求更强MixColumns一列四字节输入输出差分非零字节数之和至少5。SM3 P置换一字32比特输入输出差分非零比特数至少为3不这里没有定义分支数从1比特变3比特来看其比特级分支数很小。但杂凑函数不是靠这一个P实现全部扩散它还有消息扩展和多次迭代。重点在于Rijndael的列混合是以“字节”为最小单位的强扩散而SM3的P置换是以“位”为单位将信息复制到三个位置后续还需要通过扩展和压缩函数的多轮迭代积累扩散效果。两者设计目标不同但底层思想共通让差分快速传播。5.4 扩散性对整个算法安全性的意义无论分组密码还是杂凑函数扩散性都是安全基石。如果扩散不足攻击者可能利用截断差分从少量中间状态推测密钥。Rijndael用“宽轨迹策略”保证活跃S盒数量的下界SM3则用“消息扩展加P置换”让每一轮消息字都携带足够多的原始信息。判断一个算法设计得好不好不能只看S盒的代数性质还要看扩散层能否把S盒的非线性放大。Rijndael的MixColumns和ShiftRows正是承担这个任务。理解了这一点你再看AES竞标里的各种替代方案会发现大家归根结底都在处理同一个问题如何在保证非线性强度的前提下让局部变化快速蔓延到全状态。我自己在实际测试中也喜欢用差分分布图来观察一个自写密码算法的扩散效果。把输入翻转1比特统计输出比特中变化的比例如果一轮之后只有局部几个比特变化这个算法的传播速度就是不合格的。Rijndael在一轮之后由于MixColumns的存在至少一列的全部字节都受到影响两轮之后几乎全部16个字节都被搅动。这种良好的雪崩效应是它这么多年来依然稳坐标准位置的重要原因之一。如果让我给刚开始接触Rijndael的人一个建议那就是不要只背流程一定要亲手实现一遍并用测试向量校验。你可以先写一个支持128位分组的简化版把S盒打印出来把列混合的中间状态打印出来再和官方文档里的示例比对。这个“跟自己较劲”的过程比看十遍文档都能加深理解。等到你把这个流程走通再回头去看Rijndael原始提案里关于“宽轨迹策略”和“MDS矩阵”的论述那种感觉是完全不一样的。密码学有很多看似抽象的概念但落到代码里它们会变得清清楚楚。Rijndael正是这样一个适合作为所有密码学入门者“解剖课”的作品。