【密码学百科】分组密码原理：Feistel 网络与 SPN 结构

在对称密码学的版图中，分组密码（Block Cipher）占据着无可争议的中心地位。从上世纪七十年代 DES 被确立为联邦标准，到二十一世纪 AES 在全球数十亿设备上守护数据安全，分组密码始终是密码工程师手中最基本、最常用的构件。它不仅本身提供加密功能，还是消息认证码（MAC）、哈希函数、密钥派生函数（KDF）乃至伪随机数生成器的底层构造基元。

本文将从形式化定义出发，逐层拆解分组密码的两大设计范式——Feistel 网络和 SPN 结构。我们将以 DES 为经典案例剖析 Feistel 网络的运作细节，用 Shannon 的混淆与扩散理论解释设计动机，进而讨论雪崩效应这一衡量扩散质量的关键指标。最后，我们将深入差分密码分析和线性密码分析——两种对分组密码最具杀伤力的攻击手段——理解它们如何利用算法内部的统计偏差来恢复密钥。

一、分组密码的形式化定义

从置换到伪随机置换

分组密码的数学本质是一族由密钥索引的置换。形式化地，一个分组密码是一个函数 E: K x X -> X，其中 K 是密钥空间，X = {0, 1}^n 是 n 比特的明文/密文空间。对于每个固定的密钥 k，函数 E(k, ·) 都是 X 上的一个双射（即一一对应的置换），其逆函数 D(k, ·) 用于解密。

这里 n 称为分组长度（Block Size）。DES 的分组长度为 64 比特，AES 的分组长度为 128 比特。分组长度的选择直接影响安全性——过短的分组长度会导致生日攻击（Birthday Attack）在相对少量的密文块之后便能找到碰撞，这也是 DES 的 64 比特分组长度在现代被视为不足的原因之一。

伪随机置换（PRP）

一个安全的分组密码应当”看起来像”一个从所有可能置换中均匀随机选取的置换。这一直觉通过伪随机置换（Pseudo-Random Permutation，PRP）的概念被形式化。具体而言，若任何计算上有界的区分器（Distinguisher）都无法以不可忽略的优势区分 E(k, ·)（k 随机选取）与一个真正的随机置换 pi（从 X 上所有 n! 个置换中均匀选取），则称 E 为一个安全的 PRP。

PRP 的概念与伪随机函数（Pseudo-Random Function，PRF）密切相关。PRF 是更宽泛的概念——它不要求可逆性，只要求与随机函数不可区分。一个重要的定理（即 PRP/PRF 切换引理）表明，当分组长度 n 足够大时，一个安全的 PRP 同时也是一个安全的 PRF，两者的区分优势之差不超过 q^2 / 2^n，其中 q 是查询次数。对于 128 比特的 AES，这意味着在查询次数远小于 2^64 的场景下，PRP 和 PRF 本质上不可区分。

密钥编排

密钥编排（Key Schedule）是分组密码的重要组成部分，它将主密钥（Master Key）扩展为一系列子密钥（Round Key），每一轮加密使用一个不同的子密钥。密钥编排的设计对安全性有深远影响——糟糕的密钥编排可能导致相关密钥攻击（Related-Key Attack），即攻击者通过分析多个相关密钥下的加密行为来恢复密钥信息。

理想的密钥编排应当使得子密钥之间的统计关系尽可能不可预测。然而在实践中，密钥编排的设计往往需要在安全性和效率之间权衡——过于复杂的密钥编排会增加实现成本和延迟，尤其是在需要频繁更换密钥的场景下。AES 的密钥编排相对简单且高效，但也因此在相关密钥模型下曾被发现存在一定的弱点。

二、Feistel 网络

结构概述

Feistel 网络以 IBM 密码学家 Horst Feistel 的名字命名，是分组密码设计中最经典的框架之一。其核心思想极为优雅：将一个不可逆的轮函数（Round Function）嵌入到一个可逆的整体结构中，从而无需轮函数本身具有可逆性便可实现加密与解密。

标准 Feistel 网络的运作方式如下。将 2n 比特的输入分成左右两半 L_0 和 R_0，每半各 n 比特。第 i 轮的变换为：

L_i = R_{i-1}
R_i = L_{i-1} XOR F(k_i, R_{i-1})

其中 F 是轮函数，k_i 是第 i 轮的子密钥。经过 r 轮变换后，将最终的 L_r 和 R_r 拼接即得密文。

解密过程完全对称——只需将子密钥的使用顺序反转即可。这一性质意味着加密和解密可以共用同一套硬件或代码逻辑，只需改变密钥的输入顺序，这在硬件实现上是一个极大的优势。

轮函数的设计自由度

Feistel 网络的一个显著优势在于，它对轮函数 F 几乎没有限制——F 甚至不需要是可逆的。这赋予了设计者极大的自由度：轮函数可以是任意复杂的非线性映射，包含 S 盒（S-box）、位置换、模加法、查表操作等各种运算。

这种设计自由度也带来了风险——一个精心设计的 Feistel 网络可以非常安全，但一个草率设计的轮函数也可能使得整个密码形同虚设。轮函数的质量直接决定了密码的安全性。

Luby-Rackoff 定理

1988 年，Michael Luby 和 Charles Rackoff 证明了一个具有里程碑意义的定理：如果轮函数 F 是一个安全的伪随机函数（PRF），那么三轮 Feistel 网络构成一个安全的伪随机置换（PRP），四轮 Feistel 网络构成一个强伪随机置换（Strong PRP，即在选择密文攻击下也安全）。

这一定理的意义是深远的。它给出了从 PRF 到 PRP 的一个通用构造方法，证明了 Feistel 网络不仅仅是一种工程上的巧妙设计，而且具有可证明的安全性保证。当然，Luby-Rackoff 定理的前提是轮函数是理想的 PRF，而实际密码中的轮函数只是对 PRF 的近似。因此，实际的 Feistel 密码（如 DES）需要远多于三或四轮——DES 使用了 16 轮——来弥补轮函数偏离理想 PRF 的差距。

需要注意的是，Luby-Rackoff 定理中的三轮和四轮分别使用独立的随机函数作为轮函数。如果所有轮次共用同一个函数，则安全性分析会有所不同。

Feistel 网络的变体

经典 Feistel 网络有许多变体。非平衡 Feistel 网络（Unbalanced Feistel Network）中左右两半的长度不等；广义 Feistel 网络（Generalized Feistel Network）将输入分成多于两个子块；Type-1、Type-2、Type-3 Feistel 网络分别采用不同的子块交互模式。这些变体在不同的应用场景下各有优势——例如，广义 Feistel 网络常用于设计宽分组密码（Wide Block Cipher），以处理大于标准分组长度的数据块。

三、DES 详解

历史背景

数据加密标准（Data Encryption Standard，DES）于 1977 年被美国国家标准局（NBS，即后来的 NIST）确立为联邦信息处理标准（FIPS 46）。它的前身是 IBM 的 Lucifer 密码，由 Horst Feistel 等人设计。在标准化过程中，美国国家安全局（NSA）参与了 DES 的评审，并对设计进行了两项关键修改：一是将密钥长度从 Lucifer 的 128 比特缩减至 56 比特，二是修改了 S 盒的设计。

密钥长度的缩减在当时便引发了密码学界的激烈批评。Whitfield Diffie 和 Martin Hellman 在 1977 年公开质疑 56 比特密钥不足以抵御政府级别的暴力破解。历史证明了他们的远见——1998 年，电子前哨基金会（EFF）用一台造价约 25 万美元的专用硬件”DES Cracker”在不到三天内破解了 DES。

整体结构

DES 是一个典型的 16 轮 Feistel 网络，分组长度为 64 比特，密钥长度为 56 比特（输入 64 比特，其中 8 比特用作奇偶校验）。

加密流程如下：首先，64 比特明文经过一个固定的初始置换（Initial Permutation，IP）；然后进入 16 轮 Feistel 迭代；最后经过初始置换的逆置换（IP^{-1}）得到密文。初始置换和末尾置换本身不提供任何密码学安全性，它们是 IBM 为硬件实现方便而引入的——在当时的芯片工艺下，这种比特重排有助于简化布线。

轮函数

DES 的轮函数 F 是整个算法的核心，它接收 32 比特的右半部分和 48 比特的子密钥作为输入，输出 32 比特。具体步骤如下：

第一步，扩展置换（Expansion Permutation，E）：将 32 比特输入扩展为 48 比特。扩展的方式是将 32 比特分为 8 组，每组 4 比特，然后每组的两端各借用相邻组的一个比特，使每组从 4 比特变为 6 比特。这一步骤引入了相邻组之间的关联，有助于扩散。

第二步，密钥混合：将 48 比特的扩展结果与 48 比特的子密钥进行异或（XOR）运算。

第三步，S 盒替换：将 48 比特分为 8 组，每组 6 比特。每组输入到对应的 S 盒（S-box，Substitution Box）中，输出 4 比特。8 个 S 盒各不相同，每个 S 盒本质上是一个 6 比特到 4 比特的非线性映射表。S 盒是 DES 安全性的关键来源——它们提供了唯一的非线性变换，没有 S 盒，DES 将退化为一个纯线性变换，可以用简单的线性代数破解。

第四步，P 置换：将 S 盒输出的 32 比特进行一个固定的比特置换。这一步骤使得每个 S 盒的输出比特在下一轮中被分散到不同的 S 盒的输入中，实现跨 S 盒的扩散。

S 盒的设计准则

NSA 对 S 盒设计准则的保密长期引发猜疑——许多人怀疑 NSA 在 S 盒中植入了后门。直到 1994 年，当差分密码分析被公开发明后，这些设计准则才被解密公布。事实证明，NSA 早在七十年代便独立发现了差分密码分析，并刻意设计 S 盒使 DES 能够抵抗这种攻击。具体而言，DES 的 S 盒满足以下关键性质：

每个 S 盒都是一个 4 到 1 的映射（6 比特输入，4 比特输出）；输入中任何单比特的改变都会导致输出中至少两个比特的改变；S 盒的输出不是其输入的线性函数或仿射函数；对于任何非零输入差分，对应的输出差分分布尽可能均匀——这正是抵抗差分密码分析的关键设计准则。

密钥编排

DES 的密钥编排将 56 比特主密钥扩展为 16 个 48 比特子密钥。过程如下：首先通过置换选择 1（PC-1）从 64 比特输入中去除 8 个校验比特，得到 56 比特，分为两个 28 比特半密钥 C_0 和 D_0。在每一轮中，C 和 D 分别进行循环左移（第 1、2、9、16 轮移 1 位，其余轮移 2 位），然后通过置换选择 2（PC-2）从 56 比特中选取 48 比特作为子密钥。

DES 密钥编排的一个已知弱点是存在四个弱密钥（Weak Key）和六对半弱密钥（Semi-Weak Key）。弱密钥使得加密等于解密（即 E_k(E_k(x)) = x），半弱密钥则使得一个密钥的加密等于另一个密钥的解密。虽然在 2^56 的密钥空间中这些特殊密钥微乎其微，但在实现中仍应检测并避免使用。

密钥长度争议

56 比特密钥是 DES 最大的设计缺陷，也是密码学史上最著名的争议之一。2^56 约等于 7.2 x 10^16——在 1977 年，这对于商业攻击者而言确实遥不可及，但对于国家级攻击者则并非不可能。NSA 将密钥从 128 比特缩减至 56 比特的动机至今仍有争议，但普遍的猜测是 NSA 希望保留自己破解 DES 的能力，同时使 DES 对于商业间谍和外国政府足够安全。

为了延长 DES 的寿命，三重 DES（Triple DES，3DES）被引入——它使用两个或三个独立密钥对明文进行三次 DES 操作（加密-解密-加密），有效密钥长度为 112 或 168 比特。3DES 在 AES 标准化之前的过渡期间发挥了重要作用，但其三倍的计算开销和仅 64 比特的分组长度最终使其被 AES 取代。

四、SPN 结构

设计理念

替换-置换网络（Substitution-Permutation Network，SPN）是分组密码设计的另一大范式。与 Feistel 网络将输入分成两半、每轮只处理一半不同，SPN 在每一轮中对整个分组进行变换。SPN 的每一轮由三个层次组成：密钥混合层（Key Mixing Layer）、替换层（Substitution Layer）和置换层（Permutation Layer）。

SPN 的设计直接继承了 Shannon 在 1949 年提出的乘积密码（Product Cipher）思想——通过交替应用替换（Substitution）和转置（Transposition）来构建强密码。Shannon 指出，单独的替换或转置各自存在弱点，但将它们有机地组合在一起，便能产生远超各部分之和的安全性。

密钥混合层

每一轮的第一步（有些设计放在最后）是将子密钥与当前状态进行混合，通常使用异或（XOR）运算。密钥混合的目的是将密钥信息注入到加密过程中——如果没有密钥混合，SPN 将退化为一个不依赖密钥的固定置换，毫无安全性可言。

一些现代 SPN 设计使用模加法（Modular Addition）代替或补充异或运算来进行密钥混合。模加法引入了额外的非线性——异或是 GF(2) 上的加法，而模加法在二进制表示下由于进位的存在而具有复杂的非线性行为。

替换层（S 盒层）

替换层是 SPN 中唯一的非线性组件，它通过一组 S 盒对数据进行非线性变换。典型的做法是将 n 比特的状态分成若干组，每组通过同一个（或不同的）S 盒进行替换。

与 Feistel 网络中的 S 盒不同，SPN 中的 S 盒必须是双射（即输入和输出的比特数相同，映射是一一对应的），否则整个加密过程将不可逆。例如，AES 使用一个 8 比特到 8 比特的 S 盒——它在 GF(2^8) 上取乘法逆元，再进行一个仿射变换。这种代数结构使得 AES 的 S 盒具有良好的非线性度和差分均匀性。

S 盒的设计是 SPN 安全性的核心。一个好的 S 盒应当满足：高非线性度（与所有仿射函数的最大距离尽可能大）、低差分均匀性（任何输入差分对应的输出差分尽可能均匀分布）、没有固定点或对合点等代数弱点。

置换层

置换层的作用是将不同 S 盒的输出比特重新分配到下一轮各 S 盒的输入位置。在最简单的形式中，置换层只是一个比特置换（Bit Permutation）——将比特从一个位置移动到另一个位置。更复杂的设计使用线性变换（如 AES 中的 MixColumns 操作）来实现更高效的扩散。

置换层本身是线性的，不提供混淆。它的唯一目的是实现扩散——确保一个 S 盒的输出在下一轮中能够影响多个 S 盒的输入。好的置换层应当使得每个 S 盒的每个输出比特在下一轮中被分散到尽可能多的不同 S 盒中。

SPN 的加密与解密

与 Feistel 网络的优雅对称不同，SPN 的解密过程与加密过程是不同的。解密时，需要将每一层都替换为其逆操作：S 盒替换为逆 S 盒，置换层替换为逆置换，子密钥的使用顺序反转。这意味着 SPN 的加密器和解密器在硬件上通常不能完全复用，需要额外的面积来实现逆操作。

不过，某些精心设计的 SPN 可以通过调整密钥编排来使加密和解密共用同一套数据通路。AES 的设计者便考虑了这一点——虽然 AES 的加密和解密在数学上不同，但通过等价解密（Equivalent Inverse Cipher）变换，可以将子密钥进行预处理，使得解密数据通路与加密数据通路的结构相同。

五、混淆与扩散

Shannon 的两大原则

1949 年，Claude Shannon 在其奠基性论文”Communication Theory of Secrecy Systems”中提出了密码系统应当具备的两个基本性质：混淆（Confusion）和扩散（Diffusion）。这两个概念虽然提出已逾七十年，但至今仍是评判分组密码设计质量的首要标准。

混淆是指使密文与密钥之间的关系尽可能复杂、不透明。如果密文的每一个比特都以复杂的非线性方式依赖于密钥的多个比特，攻击者便难以通过分析密文来推断密钥的信息。在实际的分组密码中，混淆主要通过 S 盒的非线性替换来实现。

扩散是指使明文的统计特征尽可能广泛地散布到密文中。理想的扩散意味着明文中任何一个比特的改变都会导致密文中约一半比特的改变——即著名的雪崩效应。在实际的分组密码中，扩散主要通过置换层、线性变换和 Feistel 网络的交叉结构来实现。

Feistel 网络中的混淆与扩散

在 Feistel 网络中，混淆由轮函数中的 S 盒提供，扩散则通过两种机制实现。第一种是轮函数内部的置换（如 DES 中的 P 置换），它使得一个 S 盒的输出在下一轮中影响多个 S 盒的输入。第二种是 Feistel 结构本身的左右交替——每一轮中，右半部分经过轮函数处理后与左半部分异或，然后左右交换，这意味着信息在左右两半之间不断交叉流动。

Feistel 网络的一个固有局限是，每一轮只有一半的数据（右半部分）经过轮函数处理，另一半（左半部分）只是简单地与轮函数输出异或。这意味着 Feistel 网络的扩散速度相对较慢——直觉上，需要大约两倍的轮数才能达到 SPN 同等程度的扩散。这也解释了为什么 DES 需要 16 轮，而 AES（SPN 结构）只需要 10 到 14 轮。

SPN 中的混淆与扩散

在 SPN 结构中，混淆同样由 S 盒提供。扩散则由置换层（或更一般的线性变换层）负责。由于 SPN 在每一轮中对整个分组进行变换，其扩散效率通常高于 Feistel 网络。

以 AES 为例，其扩散由两个操作共同完成：ShiftRows 在行级别上进行字节移位，MixColumns 在列级别上进行字节混合。这两个操作的组合使得仅经过两轮，输入的每一个字节便已影响到输出的所有 16 个字节。这种快速而完整的扩散是 AES 能够以较少轮数达到高安全性的关键原因之一。

两种结构的设计权衡

Feistel 网络和 SPN 各有优劣。Feistel 网络的优势在于：轮函数不需要可逆，加密和解密结构完全相同（只需反转密钥顺序），设计灵活度高。其劣势是扩散速度较慢，导致需要更多轮数。SPN 的优势在于扩散效率高、轮数较少，并且更容易进行安全性的数学分析（尤其是宽轨迹策略的应用）。其劣势是 S 盒必须可逆，加密和解密通路不同，硬件实现可能更复杂。

在现代密码设计中，SPN 结构逐渐成为主流。AES、Serpent、PRESENT、GIFT、Ascon 等重要密码均采用 SPN 或其变体。然而，Feistel 网络远未退出历史舞台——Camellia、SIMON、SPECK 等现代密码仍然基于 Feistel 结构，尤其在资源受限的环境中，Feistel 网络的实现优势仍然具有吸引力。

六、雪崩效应

定义与直觉

雪崩效应（Avalanche Effect）是衡量分组密码扩散质量的核心指标。直觉上，它要求输入的微小变化（如改变明文的一个比特）能够导致输出的剧烈变化。一个好的分组密码应当表现出强烈的雪崩效应——改变明文或密钥的一个比特，密文中应当约有一半的比特发生改变。

这一概念最早由 Horst Feistel 在 DES 的设计过程中提出，随后被 Webster 和 Tavares 于 1986 年形式化为严格雪崩准则（Strict Avalanche Criterion，SAC）。

严格雪崩准则（SAC）

SAC 要求：对于一个布尔函数 f，如果改变输入的任意一个比特，输出的每一个比特都以恰好 1/2 的概率发生改变，则称 f 满足严格雪崩准则。

将 SAC 推广到分组密码的语境中：对于一个 n 比特到 n 比特的分组密码，固定密钥后，改变明文的第 i 个比特（i 从 1 到 n），密文的第 j 个比特（j 从 1 到 n）应当以接近 1/2 的概率发生翻转。这可以用一个 n x n 的矩阵来量化——矩阵的第 (i, j) 个元素表示翻转输入第 i 位时输出第 j 位翻转的概率，理想情况下所有元素都应接近 0.5。

轮数与雪崩效应的关系

在典型的分组密码中，雪崩效应是逐轮累积的。以 DES 为例：经过一轮后，改变明文的一个比特只会影响密文中少数几个比特；经过五轮后，影响已扩展到密文的大部分比特；到第八轮左右，完整的雪崩效应基本形成——此后的轮次进一步巩固和细化扩散。

这种逐轮积累的过程解释了为什么分组密码需要多轮迭代。如果轮数不足，雪崩效应尚未完全形成，密文中将残留明文的统计特征，为攻击者提供可利用的信息。密码设计者通常选择的轮数会远超完整雪崩效应形成所需的最低轮数，以提供额外的安全余量。

测量雪崩效应的方法

量化雪崩效应最直接的方法是实验统计。具体步骤为：随机生成大量明文-密钥对；对于每一对，逐一翻转明文（或密钥）的每一个比特，计算密文中发生变化的比特数；统计变化比特数的平均值和分布。理想情况下，变化比特数的平均值应为 n/2（n 为分组长度），分布应接近均值为 n/2 的二项分布。

以下 C 代码演示了一个简化的 Feistel 网络实现，并测量其雪崩效应：

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

/* 简化 Feistel 网络：32 比特分组，8 轮，用于演示雪崩效应 */

#define BLOCK_SIZE 32
#define HALF_SIZE  16
#define NUM_ROUNDS 8
#define NUM_TESTS  10000

/* 简单的非线性轮函数：混合移位、异或和加法 */
static uint16_t round_function(uint16_t data, uint16_t subkey)
{
    uint16_t x = data ^ subkey;
    /* S 盒效果：利用乘法引入非线性 */
    x = (uint16_t)(x * 0xA53F + 0x1B2D);
    /* 比特混合 */
    x = (uint16_t)((x << 7) | (x >> 9));
    x ^= (uint16_t)(x >> 5);
    return x;
}

/* Feistel 加密：32 比特输入，拆分为两个 16 比特半块 */
static uint32_t feistel_encrypt(uint32_t plaintext, const uint16_t subkeys[NUM_ROUNDS])
{
    uint16_t left  = (uint16_t)(plaintext >> 16);
    uint16_t right = (uint16_t)(plaintext & 0xFFFF);

    for (int i = 0; i < NUM_ROUNDS; i++) {
        uint16_t f_out = round_function(right, subkeys[i]);
        uint16_t new_right = left ^ f_out;
        left  = right;
        right = new_right;
    }
    return ((uint32_t)left << 16) | (uint32_t)right;
}

/* 简单密钥编排：从 32 比特主密钥派生 8 个 16 比特子密钥 */
static void key_schedule(uint32_t master_key, uint16_t subkeys[NUM_ROUNDS])
{
    uint32_t k = master_key;
    for (int i = 0; i < NUM_ROUNDS; i++) {
        k = k * 0x6C078965u + (uint32_t)i;
        subkeys[i] = (uint16_t)(k >> 16);
    }
}

/* 计算两个 32 比特值之间的汉明距离 */
static int hamming_distance(uint32_t a, uint32_t b)
{
    uint32_t diff = a ^ b;
    int count = 0;
    while (diff) {
        count += (int)(diff & 1u);
        diff >>= 1;
    }
    return count;
}

/* 雪崩效应测试：逐比特翻转明文，统计密文变化 */
static void avalanche_test(void)
{
    uint16_t subkeys[NUM_ROUNDS];
    uint32_t master_key = 0xDEADBEEFu;
    key_schedule(master_key, subkeys);

    long long total_flipped = 0;
    long long total_trials  = 0;

    for (int t = 0; t < NUM_TESTS; t++) {
        /* 伪随机明文 */
        uint32_t pt = (uint32_t)rand() ^ ((uint32_t)rand() << 16);
        uint32_t ct = feistel_encrypt(pt, subkeys);

        for (int bit = 0; bit < BLOCK_SIZE; bit++) {
            uint32_t pt_flipped = pt ^ (1u << bit);
            uint32_t ct_flipped = feistel_encrypt(pt_flipped, subkeys);
            total_flipped += hamming_distance(ct, ct_flipped);
            total_trials++;
        }
    }

    double avg_flipped = (double)total_flipped / (double)total_trials;
    printf("雪崩效应测试结果\n");
    printf("  分组长度:     %d 比特\n", BLOCK_SIZE);
    printf("  轮数:         %d\n", NUM_ROUNDS);
    printf("  测试样本数:   %d\n", NUM_TESTS);
    printf("  平均翻转比特: %.2f / %d (理想值: %.1f)\n",
           avg_flipped, BLOCK_SIZE, BLOCK_SIZE / 2.0);
    printf("  翻转比例:     %.2f%% (理想值: 50%%)\n",
           avg_flipped / BLOCK_SIZE * 100.0);
}

/* 演示单比特翻转的逐轮扩散过程 */
static void diffusion_demo(void)
{
    uint16_t subkeys[NUM_ROUNDS];
    uint32_t master_key = 0xCAFEBABEu;
    key_schedule(master_key, subkeys);

    uint32_t pt1 = 0x12345678u;
    uint32_t pt2 = pt1 ^ 1u;  /* 只翻转最低位 */

    printf("\n逐轮扩散演示\n");
    printf("  明文 1: 0x%08X\n", pt1);
    printf("  明文 2: 0x%08X (翻转最低位)\n", pt2);
    printf("  %-6s  %-12s  %-12s  %s\n", "轮次", "状态 1", "状态 2", "差异比特数");

    uint16_t l1 = (uint16_t)(pt1 >> 16), r1 = (uint16_t)(pt1 & 0xFFFF);
    uint16_t l2 = (uint16_t)(pt2 >> 16), r2 = (uint16_t)(pt2 & 0xFFFF);

    for (int i = 0; i < NUM_ROUNDS; i++) {
        uint16_t f1 = round_function(r1, subkeys[i]);
        uint16_t f2 = round_function(r2, subkeys[i]);
        uint16_t new_r1 = l1 ^ f1, new_r2 = l2 ^ f2;
        l1 = r1; r1 = new_r1;
        l2 = r2; r2 = new_r2;

        uint32_t s1 = ((uint32_t)l1 << 16) | r1;
        uint32_t s2 = ((uint32_t)l2 << 16) | r2;
        printf("  第 %d 轮  0x%08X  0x%08X  %d / %d\n",
               i + 1, s1, s2, hamming_distance(s1, s2), BLOCK_SIZE);
    }
}

int main(void)
{
    srand(42);
    avalanche_test();
    diffusion_demo();
    return 0;
}

这段代码展示了两个关键实验。第一个实验对大量随机明文逐比特翻转，统计密文中平均翻转的比特数——如果接近分组长度的一半（即 16），说明雪崩效应良好。第二个实验则直观地展示了扩散的逐轮累积过程：两个仅相差一个比特的明文，经过每一轮加密后差异比特数逐步增加，直至趋近于理想值。

七、差分密码分析

历史背景

差分密码分析（Differential Cryptanalysis）由以色列密码学家 Eli Biham 和 Adi Shamir 于 1990 年公开发表，是分组密码分析领域的一次革命性突破。然而，如前文所述，NSA 早在七十年代设计 DES 的 S 盒时便已知晓这一技术——这是密码学史上情报机构领先学术界十余年的著名案例。

差分密码分析的核心思想是：观察明文对的差分（通常定义为异或差）如何通过加密算法传播到密文对的差分。如果算法是理想的随机置换，输入差分与输出差分之间不应存在任何统计关联；但如果算法存在非随机的差分传播特性，攻击者便可以利用这些特性来恢复密钥。

差分特征与概率

一条差分特征（Differential Characteristic）描述了差分通过加密算法各轮传播的路径。形式化地，对于一个 r 轮密码，一条差分特征是一个序列 (delta_0, delta_1, …, delta_r)，其中 delta_0 是输入差分，delta_r 是输出差分，delta_i 是第 i 轮之后的中间差分。

差分特征的概率是指：在随机选取的明文对中，满足该差分特征所描述的传播路径的概率。这个概率取决于各轮中差分通过 S 盒时的概率。对于一个 S 盒，输入差分 alpha 映射到输出差分 beta 的概率可以通过穷举计算——统计所有满足 S(x) XOR S(x XOR alpha) = beta 的输入 x 的数量，除以输入空间的大小。

一条好的（即对攻击者有利的）差分特征应当具有尽可能高的概率。如果概率为 p，则攻击者大约需要 O(1/p) 个选择明文对来执行攻击。

对 DES 的差分攻击

Biham 和 Shamir 对 DES 的差分密码分析取得了以下结果：对完整的 16 轮 DES，他们找到的最佳差分特征的概率约为 2^{-47}，对应的攻击需要约 2^{47} 个选择明文。虽然这比暴力搜索（2^{55} 次加密）要快，但所需的选择明文数量之大使得这一攻击在实践中几乎不可行——这恰恰印证了 NSA 精心设计 S 盒以抵抗差分密码分析的事实。

对于轮数不足的 DES 变体，差分密码分析的威力则要强大得多。例如，对 8 轮 DES 只需约 2^{14} 个选择明文，对 12 轮 DES 需要约 2^{31} 个选择明文。这种轮数与攻击复杂度之间的关系为密码设计者选择合适的轮数提供了定量依据。

S 盒的差分均匀性

S 盒抵抗差分攻击的能力用差分均匀性（Differential Uniformity）来衡量。一个 S 盒 S 的差分均匀性定义为：对于所有非零输入差分 alpha 和所有输出差分 beta，满足 S(x) XOR S(x XOR alpha) = beta 的输入 x 的最大数量。差分均匀性越低，S 盒抵抗差分攻击的能力越强。

对于一个 n 比特到 n 比特的 S 盒，差分均匀性的理论最小值为 2（这样的 S 盒称为几乎完美非线性（Almost Perfect Nonlinear，APN）函数）。AES 的 S 盒基于 GF(2^8) 上的乘法逆元，其差分均匀性为 4，虽然不是最优的 APN，但已经非常优秀。

八、线性密码分析

基本原理

线性密码分析（Linear Cryptanalysis）由日本密码学家 Matsui Mitsuru 于 1993 年提出，是继差分密码分析之后对分组密码最重要的通用攻击方法。其核心思想是寻找明文比特、密文比特和密钥比特之间的近似线性关系。

形式化地，一个线性近似（Linear Approximation）是一个形如 P_{i1} XOR P_{i2} XOR … XOR C_{j1} XOR C_{j2} XOR … = K_{l1} XOR K_{l2} XOR … 的等式，其中 P_i 是明文比特，C_j 是密文比特，K_l 是密钥比特。如果这个等式成立的概率不是恰好 1/2，而是 1/2 + epsilon（其中 epsilon 称为偏差或偏斜），攻击者便可以利用这一偏差来推断密钥比特的信息。

堆积引理

线性密码分析的关键工具是堆积引理（Piling-Up Lemma）。该引理指出，如果将多个独立的线性近似串联起来，总偏差等于各个偏差的乘积（的 2^{r-1} 倍，其中 r 是串联的近似数量）。

具体而言，设 r 个独立的线性近似各自的偏差为 epsilon_1, epsilon_2, …, epsilon_r，则串联后的总偏差为 epsilon = 2^{r-1} * epsilon_1 * epsilon_2 * … * epsilon_r。

堆积引理使得攻击者可以将每一轮中 S 盒的局部线性近似组合成贯穿整个密码的全局线性近似。组合后的偏差虽然随轮数指数级衰减，但只要总偏差仍然可检测，攻击就有效。

对 DES 的线性攻击

Matsui 对完整 16 轮 DES 的线性密码分析是一个里程碑式的成果。他找到了一条贯穿 14 轮（从第 2 轮到第 15 轮）的线性近似，偏差约为 2^{-21}。利用这条近似，结合对第一轮和最后一轮的分析，他能够以约 2^{43} 个已知明文恢复部分密钥比特。

值得注意的是，线性密码分析只需要已知明文（Known Plaintext），而差分密码分析需要选择明文（Chosen Plaintext）。在实际攻击场景中，已知明文通常比选择明文更容易获取，这使得线性密码分析在某些场景下更具实战价值。1994 年，Matsui 在一台工作站上用 50 天时间实际执行了对 DES 的线性攻击，这是首次公开成功的全轮 DES 实际密钥恢复。

非线性度与线性逼近表

S 盒抵抗线性攻击的能力用非线性度（Nonlinearity）和线性逼近表（Linear Approximation Table，LAT）来衡量。对于一个 S 盒，其 LAT 记录了所有可能的输入掩码和输出掩码组合下的偏差。LAT 中所有非零项的绝对值的最大值越小，S 盒抵抗线性攻击的能力越强。

一个 n 比特到 n 比特的 S 盒的非线性度上界是 2^{n-1} - 2^{n/2-1}（即所谓的 Bent 函数界）。AES 的 S 盒达到了这一上界，这意味着它在非线性度方面是最优的。

差分分析与线性分析的对偶性

差分密码分析和线性密码分析之间存在深刻的数学对偶关系。差分分析利用 S 盒差分分布表（DDT）中的高概率项，线性分析利用线性逼近表（LAT）中的高偏差项。Chabaud 和 Vaudenay 于 1995 年证明了一个优雅的定理：对于一些特定类型的 S 盒，DDT 和 LAT 之间存在精确的对应关系。

这种对偶性意味着，抵抗差分攻击的设计准则和抵抗线性攻击的设计准则往往是一致的——一个好的 S 盒通常在两方面都表现优秀。这也是为什么现代 S 盒设计同时优化差分均匀性和非线性度。

九、现代分组密码设计趋势

从 DES 到 AES 的设计演化

在进入具体的设计方法论之前，有必要先从宏观视角审视分组密码三十余年的设计演化脉络。下表浓缩了从 DES 到未来轻量级密码的关键设计决策及其背后的工程取舍。

一个值得深思的现象是，从 DES 到 AES 的演化不仅仅是参数的升级（更长的密钥、更大的分组），更是设计范式的根本转变——从 Feistel 网络到 SPN 结构。这一转变与软件工程中更广泛的趋势有着耐人寻味的平行关系。Feistel 网络的哲学是「分而治之」：将数据分成两半，每轮只变换一半，通过左右交替来逐步扩散。这类似于早期系统设计中偏爱的模块化分治策略——每个模块职责单一，通过接口交互。而 SPN 的哲学是「全局统一变换」：每一轮中，SubBytes 对所有字节施加非线性变换，ShiftRows 和 MixColumns 在全局范围内扩散，每一步都直接作用于整个状态。这更像现代数据管线中端到端的统一处理——不再将数据切割成独立的半块，而是让每一层变换都「看见」全部状态。笔者认为，SPN 之所以在 AES 竞赛中胜出，根本原因在于它能用更少的轮数实现同等的扩散质量——Rijndael 仅需 10 轮（128-bit 密钥）即可达到 DES 16 轮 Feistel 难以企及的全扩散效果。这种效率优势在硬件实现和侧信道防护中被进一步放大，最终使 SPN 成为二十一世纪分组密码设计的默认选择。

宽轨迹策略

AES 的设计者 Joan Daemen 和 Vincent Rijmen 提出的宽轨迹策略（Wide Trail Strategy）是现代 SPN 设计的核心方法论。其基本思想是：通过精心设计线性扩散层，使得任何非平凡的差分特征或线性近似都必须经过大量的活跃 S 盒（Active S-box），从而保证差分特征的概率和线性近似的偏差都足够小。

具体而言，宽轨迹策略将扩散层设计为具有高分支数（Branch Number）的线性变换。分支数定义为：对于一个线性映射 L，其分支数 B = min{w(x) + w(L(x)) : x != 0}，其中 w 表示以 S 盒为单位的重量（即非零 S 盒输入/输出的数量）。分支数越高，任何差分路径中活跃 S 盒的总数越多，攻击所需的数据量越大。

AES 中 MixColumns 操作的分支数为 5（这是 4 个 S 盒列的理论最大值），结合 ShiftRows 的跨列扩散，保证了连续四轮中至少有 25 个活跃 S 盒。这一下界使得对 AES 的差分和线性攻击都需要远超实际可行的数据量。

轻量级密码

物联网（IoT）和嵌入式系统的普及催生了轻量级密码（Lightweight Cipher）的研究热潮。这些环境中，芯片面积、功耗和延迟都受到严格约束，传统的 AES 可能过于”昂贵”。轻量级密码的设计目标是在大幅降低实现成本的同时维持足够的安全性。

PRESENT 是轻量级密码的开创性作品，由 Bogdanov 等人于 2007 年提出。它采用 SPN 结构，64 比特分组，80 或 128 比特密钥，31 轮。PRESENT 的 S 盒只有 4 比特，置换层是一个简单的比特置换——整个算法可以用不到 1600 个门电路实现，这使得它适合在 RFID 标签等极端资源受限的环境中使用。

GIFT 是 PRESENT 的改进版本，由 Banik 等人于 2017 年提出。它在保持轻量化的同时改进了扩散速度和安全性余量。GIFT 有两个版本：GIFT-64（64 比特分组）和 GIFT-128（128 比特分组），后者成为了 NIST 轻量级密码竞赛获胜方案 Ascon 的组件之一。

Ascon 是 2023 年 NIST 轻量级密码标准化竞赛的最终获胜者。严格来说，Ascon 是一个认证加密和哈希方案家族，其核心是一个基于 SPN 的置换。Ascon 的设计哲学是”少即是多”——使用一个统一的、经过充分分析的置换来构建加密、认证和哈希等多种功能，而非为每种功能单独设计算法。

可证明安全性界

现代分组密码设计越来越重视可证明的安全性界（Provable Security Bounds）。这并不意味着证明一个密码”绝对安全”（这在复杂性理论的当前水平下几乎不可能），而是证明在某些明确的假设下，攻击者的优势被某个可计算的函数所限制。

例如，对于一个使用宽轨迹策略设计的 SPN，可以证明：任何 r 轮差分特征的概率不超过 p_max^{N_min}，其中 p_max 是单个 S 盒的最大差分概率，N_min 是 r 轮中活跃 S 盒的最小数量。类似的界也适用于线性近似。这些界为选择轮数和 S 盒参数提供了严格的数学依据。

可证明安全性的另一个方向是理想化模型中的证明。例如，Even-Mansour 构造证明了：即使使用一个公开的随机置换 pi，通过简单的密钥白化（即 C = k2 XOR pi(k1 XOR P)）也能获得可证明的 CPA 安全性——攻击者需要至少 2^{n/2} 次查询才能以常数优势区分该构造与随机置换。这一结果为密钥白化（Key Whitening）技术提供了理论基础。

面向未来的设计考量

后量子安全是现代密码设计必须考虑的维度。好消息是，与公钥密码不同，分组密码在量子计算面前相对稳健。Grover 算法可以将暴力搜索的复杂度从 2^n 降低到 2^{n/2}，这意味着 128 比特密钥在量子世界中仅提供 64 比特安全性。因此，NIST 建议在后量子时代使用 256 比特密钥（即 AES-256）以确保 128 比特的量子安全性。

侧信道抵抗（Side-Channel Resistance）也日益成为分组密码设计的重要考量。掩码（Masking）和阈值实现（Threshold Implementation）等技术要求密码的代数结构具有特定的性质——例如 S 盒的代数次数不宜过高。这为密码设计引入了新的约束维度，有时会与传统的安全性指标产生权衡。

形式化验证（Formal Verification）工具的发展使得自动化地搜索差分和线性特征成为可能。MILP（混合整数线性规划）和 SAT/SMT 求解器被广泛用于搜索最优差分特征和线性近似，为安全性分析提供了强大的自动化手段。

从 Feistel 和 Shannon 奠基至今，分组密码的设计已经从一门经验驱动的技艺演变为一门有着丰富数学工具支撑的工程科学。然而，密码设计的本质挑战从未改变——如何在安全性、效率和简洁性之间找到最佳的平衡点。下一篇文章将聚焦于这门科学最杰出的成果——AES，逐步拆解它的每一个设计决策，理解为什么它能在全球密码学社区的公开竞争中脱颖而出，成为二十一世纪最重要的对称密码标准。

密码学百科系列 · 第 06 篇

← 上一篇：信息论入门 | 系列目录 | 下一篇：AES 逐步拆解 →