一种结构如何解决了一个古老的加密难题——并成为 DES、俄罗斯 Magma 以及几十种其他算法的基础
要解密一个分组密码，就必须设法撤销加密时的那些打乱操作。想出一个好的打乱函数已经够难了。再想出一个干净的数学逆函数，并把两者都实现出来，工作量就翻了一倍——出错的可能性也翻了一倍。
1970 年代初，霍斯特·费斯妥在 IBM 提出了一个结构上的妙招：把数据块切成两半 L 和 R，让其中一半与轮密钥一起经过一个可以任意复杂、任意不可逆的函数 F，把结果加到另一半上，然后交换两半。重复若干次。
把它分解成步骤，整个结构就显得出奇地简单：
数据块被切成左半部分 L 和右半部分 R。在 DES 中，是把 64 位分组分成 32 位和 32 位；在 Ludus Lab 的游戏中，是把一个字节分成 4 位和 4 位。
右半部分 R 与本轮的子密钥组合，再经过函数 F——在 DES 和 Magma 中，F 是一组 S 盒（代换表），它们赋予密码非线性。
F 的结果与左半部分 L 做异或，得到新的右半部分。然后交换两半。
整个过程一遍遍重复，每次使用新的子密钥：DES 重复 16 次，Magma 重复 32 次。轮数越多，就越难在明文和密文之间找到任何规律。
最后一轮之后，两半再交换一次——正是这一点赋予费斯妥网络最主要的性质：要解密，鲍勃只需运行完全相同的算法，只是把子密钥倒序输入。
F 可以任意复杂、任意不可逆——可逆的是“切分、混合、交换”这个结构本身。
费斯妥的想法没有停留在理论上——20 世纪对称密码学的很大一部分都建立在它之上：
第一个基于费斯妥结构的密码，由霍斯特·费斯妥和他在 IBM 的团队创造。
DES 的直接前身
改进后的 Lucifer 成为美国标准长达四分之一个世纪——64 位分组，56 位密钥，16 轮。
密钥：56 位——如今已不够
基于同一思想的独立苏联设计：64 位分组，但有 256 位密钥和 32 轮。
如今：GOST R 34.12-2015
费斯妥方案如此成功，以至于又成为后来好几代密码的基础：
在 Ludus Lab 的交互式演示中，你可以：
这两种算法都是费斯妥网络，但规模大不相同，命运也截然不同：
| 参数 | DES | Magma（GOST 28147-89） |
|---|---|---|
| 起源国家 | 美国 | 苏联 / 俄罗斯 |
| 采用年份 | 1977 | 1989（现为 GOST R 34.12-2015） |
| 结构 | 费斯妥网络 | 费斯妥网络 |
| 分组大小 | 64 位 | 64 位 |
| 密钥长度 | 56 位 | 256 位 |
| 轮数 | 16 | 32 |
| S 盒 | 自 1977 年起由标准固定 | 最初是各部门的秘密；直到 2015 年才有了统一固定的一套 |
| 监管机构 | NIST（美国） | 俄罗斯联邦安全局（FSB） |
1990 年，密码学家埃利·比哈姆（Eli Biham）和阿迪·沙米尔（Adi Shamir）发表了差分密码分析——一种针对分组密码的强大攻击。学界大吃一惊：DES 的 S 盒竟然早已对这种攻击具有非凡的抵抗力。
解释是后来才出现的：据 IBM 工程师唐·科珀史密斯说，IBM 团队从 1970 年代初就知道差分密码分析，并有意把 DES 的 S 盒设计成能抵御它——但应 NSA 的要求，这一点保密了将近二十年。
56 位的 DES 密钥大约有 7×1016 种可能的取值——在 1977 年这已足够多。到 1998 年，电子前哨基金会（EFF）造出了一台造价约 25 万美元的专用机器“Deep Crack”，用暴力搜索在大约 56 小时内找到了密钥。
这公开证明了 56 位已经不够了。权宜之计是 3DES（把 DES 连用三次），随后在 2001 年，通过公开的国际竞赛选出了 AES。
公开、无专利的 DES 替代品，由布鲁斯·施奈尔在 1990 年代设计
日本公司联合开发，国际 ISO/IEC 标准，用于 TLS
3G/UMTS 保密算法核心中的一个费斯妥网络
现在你明白了为什么函数 F 不必可逆，以及这一个想法如何发展成 DES、Magma 和几十种其他密码
在演示中，你将带着一个字节从明文一路走到密文再回来——亲眼看看这个结构为什么有效