3.2 分组密码内部：Feistel 网络与 AES 轮函数
3.2 分组密码内部：Feistel 网络与 AES 轮函数
本节摘要：分组密码把明文切成固定长度的块逐块加密，DES 与 AES 分别以 Feistel 网络与 SPN 网络实现香农的混淆与扩散。本节拆开两者的轮结构：DES 的 64 位分组、56 位密钥、16 轮 Feistel 与八个 S 盒；AES 的 128 位分组、128/192/256 位密钥与 10/12/14 轮 SPN；并复盘 56 位密钥如何在 1998 年被一台专用机穷举收割，理解 3DES 的过渡逻辑与 AES 的接棒必然性。
把香农公理铸成电路：Feistel 的妙手
1970 年代初，IBM 沃森实验室的霍斯特·费斯托接到了一道工程题：香农说混淆与扩散要反复叠加，可加密与解密必须各配一套电路，成本翻倍怎么办？Feistel 网络的答案堪称优雅：把 64 位分组劈成左右两半，每轮只对一半动手——右半与轮子密钥一起喂给轮函数 F，输出异或到左半，然后左右互换。这样一轮下来，F 想多复杂就多复杂（S 盒、置换随便堆），而解密电路与加密电路完全相同，只是子密钥的次序倒着用：算法本身是"自反"的。
IBM 把这套骨架配上 48 位子密钥、扩展置换与八个 S 盒，项目定名 Lucifer 应征 1973 年美国国家标准局的公开征集。评审过程有国家安全局的深度参与：密钥从候选的 128 位砍到 56 位（另加 8 位奇偶校验），S 盒的具体参数也经其修订——当年这被视为"暗箱操作"，多年后解密的评估显示 NSA 至少是按"抗差分分析"的方向在把关，只是顺手把密钥长度压到了它自己能穷举的范围。1977 年，DES 成为联邦信息处理标准 FIPS 46。
图：DES 的 Feistel 轮与 AES 的 SPN 轮结构对照
二、56 位密钥的死亡判决书
DES 的结构在其生命周期内顶住了密码分析的围攻：差分分析与线性分析这两件最强武器对 16 轮 DES 的实际效果都只是"略优于穷举"，真正执行处决的是算力。1998 年 7 月，电子前哨基金会（EFF）以约 25 万美元造价的专用机 Deep Crack 参加 DES 挑战：56 小时穷举出密钥，明文无歧义。1999 年 1 月，Deep Crack 与互联网上十万台志愿计算机联手，把时间压到 22 小时 15 分——每秒约 2450 万亿次候选密钥。从"联邦机密级标准"到"两天内可破"，56 位的欠账按香农的唯一解距离公式如期兑现。
过渡方案 3DES 的思路是简单粗暴的串联：加密三次（密钥 k1、k2、k3，简称 EDE），密钥总长 168 位。但由于中间相遇攻击（对 2DES 尤其致命：先对前半穷举建表、再对后半反向穷举撞表，时间乘空间复杂度从平方级降到近似单倍），双密钥 3DES 的实际强度只有约 112 位。它统治了金融行业二十年，2023 年 NIST 正式停止批准其加密用途——64 位分组导致的密文块重放风险（Sweet32 攻击）也推了一把。
用 Python 造一个玩具 Feistel（16 位迷你分组），亲手验证"加密解密同一电路"：
def F(right: int, subkey: int) -> int: """玩具轮函数：异或子密钥后做平方散开（生产中是 S 盒与置换）""" x = (right ^ subkey) & 0xFFFF return (x * x >> 7) & 0xFFFF def feistel(block: int, keys: list) -> int: L, R = block >> 16, block & 0xFFFF for k in keys: # 16 轮即传入 16 把子密钥 L, R = R, L ^ F(R, k) # 半块变换 + 左右互换 return (R << 16) | (L & 0xFFFF) # 收尾再换一次手 keys = [0x1F2E, 0x3D4C, 0x5B6A, 0x7988] ct = feistel(0xABCD1234, keys) # 加密 pt = feistel(ct, keys[::-1]) # 解密：同一函数、子密钥倒序 print(hex(ct), hex(pt)) # -> 0x… 0xabcd1234
三、AES：一场公开竞赛选出的继任者
吸取了 DES 参数暗改的教训，NIST 在 1997 年为继任者发起了完全公开的全球竞赛：十五个候选来自十二个国家，评审全程接受全世界密码分析者的公开攻击。2000 年 10 月，比利时学者 Daemen 与 Rijmen 设计的 Rijndael 胜出，2001 年定名 AES（FIPS 197）。它的内部不是 Feistel，而是代换-置换网络（SPN）：128 位状态排成 4×4 字节矩阵，每一轮依次经过 SubBytes（16 个 8 位 S 盒逐字节代换，提供混淆）、ShiftRows 与 MixColumns（行循环移位加列混合，把一个字节的扰动在一轮内撒满全块，提供扩散）、AddRoundKey（异或扩展子密钥）。密钥 128/192/256 位分别对应 10/12/14 轮——密钥越长轮数越多，安全边际同步放大。末轮省去 MixColumns，解密按逆序执行四步的逆变换。
SPN 与 Feistel 的工程差异值得一提：Feistel 每轮只改一半，N 轮至少要 N 轮才让全部比特"湿透"；SPN 每轮全改，扩散更快、轮数更省、且天然适合并行与硬件流水线——AES-NI 指令一条就是一整轮，这也是它至今稳坐 TLS 数据面主力位置的直接原因。
💡 关键直觉：DES 教会世界"密钥长度必须按未来算力规划"，AES 竞赛教会世界"算法要当众接受攻击"。这两条标准治理经验，比任何单个算法都长寿。
本节要点回顾
- Feistel 网络：每轮半改加互换，轮函数任意复杂而加解密电路同一，DES 以 16 轮、64 位分组、56 位密钥实现它；
- DES 之死：结构无恙，1998 年 Deep Crack 以 56 小时穷举兑现 56 位密钥的算力死刑；3DES 以约 112 位有效强度过渡至 2023 年退役；
- AES 参数：128 位分组，128/192/256 位密钥对应 10/12/14 轮 SPN，SubBytes 主混淆、ShiftRows 与 MixColumns 主扩散；
- 治理遗产：公开竞赛与公开分析成为此后标准制定（SHA-3、后量子）的固定范式。
分组的轮结构已拆完，但"切好的块怎么串起来"同样生死攸关。下一节看工作模式：ECB 如何让密文直接画出企鹅，GCM 又如何一石二鸟。