知识库 / Feistel 网络：分组密码的结构基石

Feistel 网络：分组密码的结构基石

密码学概念 · 2026-11-04

概述

Feistel 网络（Feistel Network）是现代分组密码最基础的结构设计之一。1973 年，Horst Feistel 在 IBM 工作时提出了这一结构，随后被应用于 DES（Data Encryption Standard）的设计中。半个多世纪后，Feistel 网络依然是分组密码设计的核心范式——SM4 采用的就是其非平衡变体。

核心洞察：Feistel 网络的最大优势在于加解密结构完全对称——只需将轮密钥倒序使用，即可实现解密，无需设计独立的解密函数。这一性质在工程实现中具有极高价值，特别是在资源受限的硬件环境（如智能卡、HSM）中。

数学结构：从信息论到构造原则

原始 Feistel 结构

设明文分组长为 $2n$ 位，分为左半部分 $L_0$ 和右半部分 $R_0$。每轮变换定义为：

$$L_i = R_{i-1}$$ $$R_i = L_{i-1} \oplus F(R_{i-1}, K_i)$$

其中：

  • $F$ 是轮函数（Round Function），将 $n$ 位输入映射为 $n$ 位输出
  • $K_i$ 是第 $i$ 轮的子密钥
  • $\oplus$ 表示按位异或

为什么解密只需逆转密钥顺序？

这是 Feistel 结构最精妙之处。经过一轮变换后：

$$R_{i-1} = L_i \quad \text{（直接可得）}$$ $$L_{i-1} = R_i \oplus F(L_i, K_i) \quad \text{（因为 } F(R_{i-1}, K_i) = F(L_i, K_i) \text{）}$$

可见，只要已知 $L_i$、$R_i$ 和 $K_i$，就能无条件恢复 $L_{i-1}$、$R_{i-1}$。整个过程不依赖 $F$ 的可逆性，只要 $F$ 是普通函数即可。

与 SPN 的本质区别：SPN（Substitution-Permutation Network，如 AES）要求每一轮都可逆，因此加解密需要独立的逆变换电路。Feistel 则天然实现了加解密共享结构。

安全性分析：扩散与混淆

单轮的安全性边界

单轮 Feistel 网络不具备密码学安全性。攻击者只需观察一个明文-密文对，就能通过查询 $F$ 函数的输入输出关系，推断出 $F$ 的内部结构。

多轮的安全保证

Feistel 网络的安全性依赖于轮数。Luby 和 Rackoff 证明了：

  • 3 轮 Feistel：在理想cipher模型下，达到大约 $2^{n/2}$ 的安全强度（Birthday bound）
  • 4 轮及以上：可实现 IND-CPA（选择明文攻击下的不可区分性）
实际设计中通常采用 16-32 轮，以确保足够的安全裕度。

差分与线性特性传播

Feistel 网络的扩散特性较弱——每轮仅改变状态的一半。这意味着：

  • 积分密码分析（Integral Cryptanalysis） 对 Feistel 结构特别有效
  • 宽轨迹策略（Wide Trail Strategy） 在设计时需额外考虑
这解释了为何 SM4 采用了非平衡 Feistel 变体来增强扩散速度。

平衡 vs 非平衡 Feistel

平衡 Feistel（经典 DES）

  • 状态分为等长的左右两半（各 64 位）
  • 每轮只变换一半状态
  • 优点：结构对称，易于硬件实现
  • 缺点：扩散慢，需要更多轮数

非平衡 Feistel（SM4）

SM4 将 128 位状态分为 4 个 32 位字 $(X_0, X_1, X_2, X_3)$，每轮更新一个字：

$$X_i = X_{i-4} \oplus T(X_{i-3} \oplus X_{i-2} \oplus X_{i-1} \oplus K_i)$$

其中 $T$ 是复合变换（S盒 + 线性变换）。

优势：

  • 每轮参与更多字，扩散更快
  • 4 轮即可完成完整的状态混合（vs 平衡结构的 8 轮+）
  • 保持了解密的对称性

广义 Feistel 网络（GFN）

现代设计中还出现多种变体：

  • GFSbox：每轮使用多个 S 盒
  • Even-Mansour 结构：结合外密钥的 Feistel 变体
  • ARX 结构：用加法、旋转、异或替代 S 盒

与国密 SM4 的设计关联

SM4 的结构特点

SM4 是典型的中国国家标准分组密码，采用非平衡 Feistel 结构：

参数值
分组长度128 位
密钥长度128 位
轮数32 轮
轮密钥32 个子密钥 $K_0 \sim K_{31}$
结构类型非平衡 Feistel（4 字迭代）

为什么 SM4 不采用经典平衡 Feistel？

  • 扩散需求：物联网场景需要更快的扩散速度
  • 硬件效率：32 位字对齐，便于 ARM/MIPS 架构
  • 侧信道防护：非平衡结构更易于实现掩码防护

SM4 的 S 盒设计

SM4 的 S 盒是基于有限域 $GF(2^8)$ 上的逆函数构造的，与 AES 的 S 盒设计思路相同：

$$S(x) = A + M \cdot x^{-1}$$

其中 $x^{-1}$ 是在 $GF(2^8)$ 上的乘法逆元，$A$ 是常数，$M$ 是线性变换矩阵。这种设计保证了良好的差分均匀性和线性偏差。

现代密码学中的 Feistel 遗产

仍在使用的 Feistel 密码

算法结构状态
DES平衡 Feistel，16 轮已退役
3DES平衡 Feistel，48 轮（等效）逐渐淘汰
SM4非平衡 Feistel，32 轮现行标准
Blowfish平衡 Feistel，16 轮活跃
Twofish平衡 Feistel，16 轮活跃
CAST-128平衡 Feistel，16 轮活跃

Feistel 的局限与演进

尽管 Feistel 结构有诸多优势，但在以下场景存在局限：

  • 认证加密：AEAD 模式（如 GCM）需要不同的结构范式
  • 哈希函数： sponge 结构（SHA-3/Keccak）更适合哈希
  • 后量子密码：格密码多采用 LWE 结构，与 Feistel 无关
现代密码学呈现出结构多样化的趋势，Feistel 只是其中一种经过时间检验的经典范式。

总结

Feistel 网络的核心价值在于加解密对称性——这一性质在资源受限环境中具有不可替代的工程优势。SM4 等非平衡变体进一步证明了该结构在现代密码设计中的生命力。

理解 Feistel 网络，是理解现代分组密码设计思想的关键一步。无论是分析旧算法的安全强度，还是设计新的密码原语，Feistel 的基本原理都是不可或缺的分析工具。

相关实践

参考

  • Horst Feistel, "Cryptography and Data Security", Plenum Press, 1973
  • GB/T 32907-2016《信息安全技术 SM4 分组密码算法》
  • NIST FIPS 46-3, "Data Encryption Standard" (archived)
  • Daemen and Vincent Rijmen, "The Design of Rijndael", Springer, 2002
← 返回知识库