Feistel 网络：现代密码的构建模块

20 世纪 70 年代初，IBM 研究院的霍斯特·费斯特尔正在研究卢西弗密码。当时他提出了一个根本性的洞见：即使轮函数不可逆，也可以构建出可逆密码。

这一发现具有革命性意义，因为设计既安全又可逆的函数非常困难。费斯特尔结构完全避开了这一要求，使人们能够使用任意复杂的单向轮函数。

在费斯特尔密码中，输入分组被分成两个大小相等的部分：L（左半部）和 R（右半部）。每一轮都对 R 应用轮函数 F，将结果与 L 执行 XOR，然后交换两半。

经过 n 轮后，重新组合两半以生成密文。交换操作确保两半在交替的轮次中都得到处理，并使它们充分混合。

费斯特尔网络中的轮函数 F 将右半部和轮子密钥作为输入，产生一个与左半部执行 XOR 的输出。关键在于，F 不需要是可逆的。

F 可以任意复杂：可以组合使用替换、置换、XOR 和模运算。F 越复杂、非线性越强，密码就越安全，因为解密过程始终不需要对 F 求逆。

费斯特尔密码的解密使用与加密完全相同的结构，但以相反顺序应用各轮子密钥。这是因为 XOR 是自身的逆运算：如果 A XOR B = C，那么 C XOR B = A。

由于解密过程从不调用 F^-1（F 的逆函数），轮函数可以是不可逆散列函数、查找表或任意复杂操作，而不会影响密码的可逆性。

费斯特尔网络的数学优雅之处在于，无论 F 执行什么操作，其 XOR 结构都能保证整体可逆。即使 F 是像 SHA-256 这样的一向函数，整个费斯特尔密码仍然可逆。

这使费斯特尔密码极其灵活。密码学家可以完全专注于让 F 尽可能实现混淆和扩散，同时知道可逆性由网络结构本身负责。

数据加密标准（DES）于 1977 年发布，是一种 16 轮费斯特尔密码，处理 64 位分组并使用 56 位密钥。每一轮都使用一个不同的 48 位子密钥，这些子密钥由主密钥派生而来。

DES 的轮函数包括扩展置换、与子密钥执行 XOR、提供非线性的八个 S 盒，以及一个 P 盒置换。这种组合同时提供了香农密码设计原则所要求的混淆和扩散。

河豚密码由布鲁斯·施奈尔于 1993 年设计，是一种密钥长度可变（32 至 448 位）的 16 轮费斯特尔密码。它使用依赖于密钥的 S 盒，使预计算攻击变得不切实际。

双鱼密码是高级加密标准竞选的入围方案，它将河豚密码的思想扩展到 128 位分组和 16 轮。两者至今都未被破解，并被用于密码散列等应用，其中一种密码散列方案使用了改进版河豚密码。

平衡费斯特尔密码将分组分成两个大小相等的部分。非平衡费斯特尔密码使用大小不等的部分，例如按 3/4 和 1/4 的比例分割。

非平衡费斯特尔网络在某些场景中可以提供安全优势，也被用于一些专用密码。CAST 系列密码使用平衡的 64 位费斯特尔结构。

1988 年，迈克尔·卢比和查尔斯·拉科夫证明：使用伪随机轮函数的 3 轮费斯特尔网络是安全的伪随机置换（PRP），而 4 轮版本是强伪随机置换。

这一理论成果为费斯特尔网络提供了坚实的可证明安全基础，而不仅是经验上的信心。它证实，除了轮函数之外，费斯特尔结构本身也能提升安全性。

高级加密标准所采用的替换–置换网络（SPN）会同时对整个分组应用替换和置换，而不是每轮只处理分组的一半。这可以实现更快的扩散。

高级加密标准只需 4 轮即可实现完全扩散，而 DES 的费斯特尔结构需要更多轮次才能达到相当的扩散效果。高级加密标准的 SPN 也更适合配备 SIMD 指令的现代处理器架构。

卢比–拉科夫定理将轮函数 F 视为真正的随机函数。在实际中，F 是伪随机函数（由密钥控制的密码或散列函数），而不是真正的随机预言机。

理论证明与实际实现之间的差距，是密码学中反复出现的主题。证明能够提供信心，但建立在理想化模型之上。现实世界的安全性还取决于不存在侧信道漏洞的安全实现。

请检验您对费斯特尔网络设计的理解。

费斯特尔网络是分组密码结构，使用不需要可逆的轮函数。解密时，只需将同一结构反向运行，并以相反顺序使用子密钥。

DES、河豚密码和双鱼密码都是费斯特尔密码。卢比–拉科夫定理提供了理论上的安全保证。高级加密标准则采用 SPN 结构，从而在每轮中实现更好的扩散。