密码学的核心目标是在计算受限的对手面前保护信息。然而”计算受限”并不意味着对手只能做暴力穷举——当对手善于运用概率推理时，密码系统中哪怕极其微小的统计偏差都可能被放大为致命弱点。从 20 世纪 90 年代 Biham-Shamir 的差分密码分析（Differential Cryptanalysis）到 Matsui 的线性密码分析（Linear Cryptanalysis），概率论一直是密码分析领域最锋利的数学武器。本文将从概率论的基本概念出发，逐步深入到碰撞攻击、差分分析与线性分析的核心原理，最终揭示这些分析方法如何深刻地改变了现代密码的设计哲学。

一、概率论基础回顾

密码分析中所涉及的概率论并不需要测度论层面的深度，但对离散概率（Discrete Probability）的精确理解是不可或缺的。

样本空间与事件。 设有限样本空间 \(\Omega\)，每个基本事件 \(\omega \in \Omega\) 对应一个非负概率 \(\Pr[\omega]\)，且 \(\sum_{\omega \in \Omega} \Pr[\omega] = 1\)。在密码分析的语境下，\(\Omega\) 通常是所有可能的密钥空间、明文空间或随机带的取值集合。事件 \(A \subseteq \Omega\) 的概率为 \(\Pr[A] = \sum_{\omega \in A} \Pr[\omega]\)。

条件概率与贝叶斯定理（Bayes’ Theorem）。 给定事件 \(B\)（\(\Pr[B] > 0\)），事件 \(A\) 在 \(B\) 发生条件下的概率为：

\[\Pr[A \mid B] = \frac{\Pr[A \cap B]}{\Pr[B]}\]

贝叶斯定理将其反转：\(\Pr[A \mid B] = \Pr[B \mid A] \cdot \Pr[A] / \Pr[B]\)。在密码分析中，攻击者往往先观测到密文（事件 \(B\)），再推断密钥（事件 \(A\)）。贝叶斯推理框架恰好描述了这种”从观测到推断”的过程。

联合界（Union Bound）。 对于任意事件序列 \(A_1, A_2, \ldots, A_m\)，有：

\[\Pr\left[\bigcup_{i=1}^{m} A_i\right] \leq \sum_{i=1}^{m} \Pr[A_i]\]

联合界虽然简单，却在密码安全性证明中无处不在。例如，当我们想论证”在 \(q\) 次查询中，没有任何一次查询导致坏事件发生”时，只需将每次查询导致坏事件的概率上界累加即可。

独立性与期望。 两个事件 \(A\), \(B\) 独立当且仅当 \(\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]\)。随机变量 \(X\) 的期望为 \(\mathbb{E}[X] = \sum_x x \cdot \Pr[X = x]\)。切比雪夫不等式（Chebyshev’s Inequality）给出了随机变量偏离期望的概率上界：\(\Pr[|X - \mathbb{E}[X]| \geq t] \leq \operatorname{Var}(X) / t^2\)。在密码分析中，当攻击者需要收集足够多的样本来确认某个统计偏差时，期望与方差的计算直接决定了攻击所需的数据复杂度。

二、生日悖论与碰撞攻击

生日悖论（Birthday Paradox）也许是概率论在密码学中最著名的应用。它的表述极为直观：在一个有 23 人的房间里，至少两人生日相同的概率已经超过 50%。推广到密码学场景后，它构成了碰撞攻击（Collision Attack）的理论基石。

经典分析。 将 \(q\) 个元素均匀随机地映射到大小为 \(N\) 的值域。前 \(i\) 个元素互不碰撞的概率为：

\[\prod_{i=0}^{q-1} \left(1 - \frac{i}{N}\right) \approx \exp\left(-\frac{q(q-1)}{2N}\right)\]

当 \(q \approx 1.177 \sqrt{N}\) 时，碰撞概率超过 \(1/2\)。这就是著名的 \(O(\sqrt{N})\) 界：要在大小为 \(N\) 的空间中找到碰撞，期望只需约 \(\sqrt{N}\) 次采样，而非 \(N\) 次。

对哈希函数的影响。 一个输出长度为 \(n\) 比特的哈希函数，其值域大小为 \(N = 2^n\)。暴力寻找碰撞只需约 \(2^{n/2}\) 次哈希计算。这正是为什么 SHA-256 被认为提供 128 比特的碰撞安全性，而非 256 比特——生日界将安全强度直接减半。

多重碰撞（Multi-collision）。 2004 年，Joux 证明了一个令人吃惊的结果：对于迭代型哈希函数（Merkle-Damgard 结构），找到 \(2^t\) 路碰撞（即 \(2^t\) 条不同的消息映射到同一个哈希值）只需约 \(t \cdot 2^{n/2}\) 次计算，而非直觉上认为的 \(2^{(2^t - 1) \cdot n / 2^t}\) 次。这一结果深刻揭示了级联哈希（concatenation of hash functions）并不像人们直觉认为的那样能简单地累加安全性。

下面用 Python 模拟生日攻击，直观展示碰撞出现的速度：

import hashlib
import os
import math

def birthday_attack_simulation(hash_bits=32, max_attempts=2**20):
    """
    模拟生日攻击：在截断到 hash_bits 位的哈希空间中寻找碰撞。
    理论期望：约 2^(hash_bits/2) 次尝试后找到碰撞。
    """
    seen = {}
    mask = (1 << hash_bits) - 1

    for i in range(max_attempts):
        # 随机生成消息
        msg = os.urandom(16)
        # 计算截断哈希
        full_hash = hashlib.sha256(msg).digest()
        h = int.from_bytes(full_hash[:4], 'big') & mask

        if h in seen:
            prev_msg = seen[h]
            if prev_msg != msg:
                return {
                    'found': True,
                    'attempts': i + 1,
                    'theoretical': math.isqrt(2 ** hash_bits),
                    'msg1': prev_msg.hex(),
                    'msg2': msg.hex(),
                    'hash_value': hex(h),
                }
        seen[h] = msg

    return {'found': False, 'attempts': max_attempts}

if __name__ == '__main__':
    # 在 2^32 的哈希空间中寻找碰撞，期望约 2^16 = 65536 次
    result = birthday_attack_simulation(hash_bits=32)
    if result['found']:
        print(f"碰撞发现！尝试次数: {result['attempts']}")
        print(f"理论期望:         ~{result['theoretical']}")
        print(f"消息 1: {result['msg1']}")
        print(f"消息 2: {result['msg2']}")
        print(f"哈希值: {result['hash_value']}")
    else:
        print("未找到碰撞")

这段代码在 32 比特的截断哈希空间中搜索碰撞。理论上，约 \(2^{16} = 65536\) 次尝试即可找到碰撞，实际运行结果往往非常接近这个理论值。将 hash_bits 增大到 40、48 时，所需尝试次数也会按 \(2^{n/2}\) 规律增长，完美验证了生日界。

从工程实践来看，生日悖论也许是密码学中最危险的「简单」结果。它危险之处不在于难以理解——任何学过概率论的人都能在五分钟内掌握它——而在于它的数值后果极容易被低估。一个 128 位的哈希函数只有 64 位的碰撞安全性，这个 50% 的折扣看似显而易见，但笔者在工程审查中反复见到即使是经验丰富的工程师也会犯的错误：用 128 位随机 nonce 来「保证唯一性」时忘记了在 \(2^{64}\) 次使用后碰撞概率就变得不可忽略。GCM 模式的 96 位 nonce 意味着在同一密钥下仅约 \(2^{48}\) 次加密后就应当换密钥——这个数字对于高吞吐量系统来说可能在几小时内就会达到。生日界还暗示了一个更深层的教训：在密码学中，你的「安全余量」永远只有你以为的一半。

三、差分密码分析

先看一张图，把这一节的关键关系串起来。

flowchart LR
    A[输入差分或掩码] --> B[穿过轮函数]
    B --> C[形成统计偏差]
    C --> D[构造区分器]
    D --> E[恢复子密钥]

差分密码分析（Differential Cryptanalysis）由 Biham 和 Shamir 于 1990 年提出，是现代分组密码分析中最具影响力的技术之一。它利用明文对之间的差分（通常是异或差分）在加密过程中传播的统计规律来恢复密钥信息。

基本思想。 考虑一个分组密码 \(E_K\)，选择一对明文 \((P, P^*)\)，使其差分 \(\Delta P = P \oplus P^*\) 为预先确定的值。经过加密后得到密文对 \((C, C^*)\)，其差分为 \(\Delta C = C \oplus C^*\)。理想的随机置换中，\(\Delta C\) 在所有可能值上均匀分布。但在实际密码中，由于 S 盒（S-box）的非线性特性不够完美，某些输入差分 \(\Delta X\) 经过 S 盒后，某个输出差分 \(\Delta Y\) 出现的概率会显著高于 \(1/2^n\)（其中 \(n\) 为 S 盒输出宽度）。

差分分布表（Difference Distribution Table, DDT）。 对于一个 \(n\) 比特到 \(n\) 比特的 S 盒 \(S\)，其差分分布表的第 \((\alpha, \beta)\) 项定义为：

\[\text{DDT}(\alpha, \beta) = \#\{x \in \{0,1\}^n : S(x) \oplus S(x \oplus \alpha) = \beta\}\]

该值除以 \(2^n\) 即为差分概率 \(\text{DP}(\alpha \to \beta) = \text{DDT}(\alpha, \beta) / 2^n\)。如果所有非零项的差分概率都接近 \(1/2^n\)，则该 S 盒对差分分析有良好的抵抗力。

差分特征（Differential Characteristic）。 攻击者不仅关注单轮 S 盒的差分传播，还需要将差分穿越多轮。一条 \(r\) 轮的差分特征是一系列中间差分值 \(\Delta_0, \Delta_1, \ldots, \Delta_r\)，每相邻两轮之间的转移概率为 \(p_i = \text{DP}(\Delta_{i-1} \to \Delta_i)\)。在独立轮密钥假设下，整条特征的概率近似为：

\[p = \prod_{i=1}^{r} p_i\]

当 \(p\) 显著大于 \(2^{-n}\)（\(n\) 为分组长度）时，攻击者就能利用该特征区分密码与随机置换。

对 DES 的攻击。 Biham 和 Shamir 展示了对缩减轮数 DES（Reduced-round DES）的差分攻击。完整 16 轮 DES 的最优差分特征概率约为 \(2^{-62}\)，使得攻击所需的选择明文数量接近整个密文空间 \(2^{64}\)，因此对完整 DES 的差分攻击在实际中并不比穷举搜索更优。但值得注意的是，据后来解密的文件显示，IBM 和 NSA 在设计 DES 时已经了解差分分析的原理，并特意优化了 S 盒以抵御这种攻击——这比 Biham-Shamir 的公开发表早了近 20 年。

笔者认为，差分密码分析的提出永久性地改变了密码设计的范式。在 Biham-Shamir 之前，密码设计者依赖直觉和临时性测试来判断一个密码是否「足够好」——DES 的 S 盒虽然在 NSA 的秘密指导下针对差分分析进行了优化，但这种知识并未公开，整个学术界对系统化的密码分析方法一无所知。差分分析的公开发表彻底终结了这种「安全靠模糊」的时代。此后，任何严肃的分组密码设计都必须附带对差分攻击抵抗力的严格证明——AES 的宽轨迹策略正是这一范式转变的直接产物，它不是简单地「设计出一个好密码」，而是提供了一个数学框架来证明密码对差分攻击和线性攻击的安全下界。从某种意义上说，Biham-Shamir 的贡献不在于他们攻破了什么，而在于他们定义了密码设计者此后必须回答的问题。

下面是一段 Python 代码，用于构建简化 S 盒的差分分布表并搜索差分特征：

def build_ddt(sbox):
    """
    为给定的 S 盒构建差分分布表 (DDT)。
    sbox: 长度为 2^n 的列表，表示 n 比特到 n 比特的置换或函数。
    返回: 二维列表 ddt[input_diff][output_diff] = count
    """
    n = len(sbox)
    ddt = [[0] * n for _ in range(n)]

    for x in range(n):
        for dx in range(n):
            x_prime = x ^ dx
            dy = sbox[x] ^ sbox[x_prime]
            ddt[dx][dy] += 1

    return ddt

def find_best_differentials(ddt, top_k=5):
    """
    从 DDT 中找到概率最高的非平凡差分转移。
    排除输入差分为 0 的平凡情况。
    """
    n = len(ddt)
    results = []

    for dx in range(1, n):
        for dy in range(n):
            if ddt[dx][dy] > 0:
                prob = ddt[dx][dy] / n
                results.append((dx, dy, prob, ddt[dx][dy]))

    results.sort(key=lambda t: t[2], reverse=True)
    return results[:top_k]

def search_differential_characteristic(sbox, num_rounds, threshold=0.0):
    """
    使用贪心策略搜索多轮差分特征（简化的 Feistel 结构示例）。
    每一轮选择当前概率最高的差分转移。
    这是教学演示，实际攻击需要更精细的搜索算法。
    """
    n = len(sbox)
    ddt = build_ddt(sbox)

    best_chars = []
    for start_dx in range(1, n):
        path = [start_dx]
        total_prob = 1.0
        current_dx = start_dx

        for r in range(num_rounds):
            best_dy = -1
            best_p = 0.0
            for dy in range(n):
                p = ddt[current_dx][dy] / n
                if p > best_p and (dy != 0 or r == num_rounds - 1):
                    best_p = p
                    best_dy = dy
            if best_dy == -1 or best_p == 0:
                break
            total_prob *= best_p
            path.append(best_dy)
            current_dx = best_dy

        if len(path) == num_rounds + 1 and total_prob > threshold:
            best_chars.append((path, total_prob))

    best_chars.sort(key=lambda t: t[1], reverse=True)
    return best_chars

if __name__ == '__main__':
    # DES 第一个 S 盒的简化 4-bit 版本（教学用）
    sbox_example = [14, 4, 13, 1, 2, 15, 11, 8,
                     3, 10, 6, 12, 5, 9, 0, 7]

    print("=== 差分分布表 (DDT) ===")
    ddt = build_ddt(sbox_example)
    print("     ", "  ".join(f"{i:2X}" for i in range(16)))
    for dx in range(16):
        row = "  ".join(f"{ddt[dx][dy]:2d}" for dy in range(16))
        print(f"  {dx:2X}: {row}")

    print("\n=== 最优差分转移 ===")
    top_diffs = find_best_differentials(ddt, top_k=8)
    for dx, dy, prob, count in top_diffs:
        print(f"  Δin=0x{dx:X} → Δout=0x{dy:X}  "
              f"概率={prob:.4f} ({count}/16)")

    print("\n=== 3 轮差分特征搜索 ===")
    chars = search_differential_characteristic(sbox_example, 3)
    for path, prob in chars[:5]:
        path_str = " → ".join(f"0x{d:X}" for d in path)
        print(f"  {path_str}  总概率={prob:.6f}")

运行该代码，可以直观看到：即使是精心设计的 S 盒，某些差分转移的概率仍显著偏离均匀分布。攻击者正是利用这些偏差来构造高概率的差分特征。

3.1 完整的 4 轮差分路径 Worked Example

为了让读者对差分分析建立具体直觉，下面以一个简化的 4 轮 SPN（Substitution-Permutation Network）为例，完整演示差分路径的构造与概率计算。

Toy SPN 规格。 分组长度 16 比特，分为 4 个 4-bit 半字节。每轮由三个操作组成：S 层（4 个并行的 4-bit S 盒）、P 层（比特置换）、轮密钥异或。S 盒采用上文的教学示例：S = [14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7]（即 DES S1 的简化版本）。

目标。 构造一条穿越 4 轮的差分特征，使整条路径的概率显著高于随机（\(> 2^{-16}\)）。

步骤 1：选择输入差分。 从 DDT 中我们知道，差分 \(\Delta_{\text{in}} = \texttt{0xB} \to \Delta_{\text{out}} = \texttt{0x8}\) 的概率为 \(8/16 = 1/2\)（DDT 值为 8），这是该 S 盒中概率最高的非平凡差分之一。我们选择只激活第一个 S 盒，令 16 比特输入差分为 \(\Delta_0 = \texttt{0xB000}\)。

步骤 2：第 1 轮传播。

• S 层：只有 S 盒 0 被激活，输入差分 \(\texttt{0xB}\)，输出差分 \(\texttt{0x8}\)，概率 \(p_1 = 1/2\)。其余三个 S 盒输入差分为 \(\texttt{0x0}\)，输出差分必然为 \(\texttt{0x0}\)，概率 \(1\)。
• S 层输出差分：\(\texttt{0x8000}\)，即二进制 \(\texttt{1000 0000 0000 0000}\)。
• P 层（假设简单的比特移位置换）：第 15 位被映射到第 12 位，输出差分变为 \(\texttt{0x1000}\)，即 \(\texttt{0001 0000 0000 0000}\)。

步骤 3：第 2 轮传播。

• S 层输入差分 \(\texttt{0x1000}\)：只有 S 盒 0 被激活，输入差分 \(\texttt{0x1}\)。
• 查 DDT：\(\texttt{0x1} \to \texttt{0x4}\) 的概率为 \(4/16 = 1/4\)（DDT 值为 4）。概率 \(p_2 = 1/4\)。
• S 层输出差分：\(\texttt{0x4000}\)，即 \(\texttt{0100 0000 0000 0000}\)。
• P 层：第 14 位映射到第 8 位，输出差分 \(\texttt{0x0100}\)。

步骤 4：第 3 轮传播。

• S 层输入差分 \(\texttt{0x0100}\)：只有 S 盒 1 被激活，输入差分 \(\texttt{0x1}\)。
• 同上，选择 \(\texttt{0x1} \to \texttt{0x4}\)，概率 \(p_3 = 1/4\)。
• S 层输出差分：\(\texttt{0x0400}\)。
• P 层：映射后输出差分 \(\texttt{0x0020}\)。

步骤 5：第 4 轮（最后一轮，仅经过 S 层和密钥异或，不再经过 P 层）。

• S 层输入差分 \(\texttt{0x0020}\)：只有 S 盒 2 被激活，输入差分 \(\texttt{0x2}\)。
• 查 DDT：\(\texttt{0x2} \to \texttt{0xD}\) 的概率为 \(4/16 = 1/4\)。概率 \(p_4 = 1/4\)。
• 输出差分：\(\texttt{0x00D0}\)。

概率汇总。 整条 4 轮差分特征的概率为：

\[p = p_1 \times p_2 \times p_3 \times p_4 = \frac{1}{2} \times \frac{1}{4} \times \frac{1}{4} \times \frac{1}{4} = \frac{1}{128} = 2^{-7}\]

这远高于随机情形下的 \(2^{-16}\)（16 比特分组的均匀随机概率），意味着攻击者只需约 \(128\) 个选择明文对即可以高概率观测到该差分特征。一旦特征被确认，攻击者便可对最后一轮密钥进行部分穷举，通过统计计数恢复密钥比特。

关键观察。 整条路径的设计策略是每轮只激活一个 S 盒（「单活跃 S 盒」路径），从而将概率损失控制在最小。这也是差分密码分析中常用的搜索策略：优先寻找「稀疏」的差分路径。

个人思考。 差分密码分析的提出从根本上改变了分组密码的设计范式。在 Biham-Shamir 之前，密码设计更多依赖直觉和经验——设计者会说「这个 S 盒看起来足够非线性」，但没有量化评估的框架。差分分析迫使设计者回答一个精确的问题：「穿越所有轮的最优差分特征，其概率上界是多少？」AES 的 Wide Trail 策略正是对这一问题的系统化回答——它通过保证每条活跃路径必须穿过足够多的 S 盒，从数学上证明了最优差分概率低于穷举攻击的阈值。从「希望它是安全的」到「证明最优差分的概率足够低」，这一转变是密码学走向成熟科学的关键一步。

四、线性密码分析

如果说差分分析利用的是密码输入输出之间的”差分偏差”，那么线性密码分析（Linear Cryptanalysis）利用的则是”线性偏差”。该方法由 Matsui 于 1993 年提出，与差分分析并列为分组密码分析的两大支柱。

线性近似。 对于 S 盒 \(S: \{0,1\}^n \to \{0,1\}^n\)，一条线性近似是指选择输入掩码 \(\alpha\) 和输出掩码 \(\beta\)，使得：

\[\alpha \cdot x \oplus \beta \cdot S(x) = 0\]

在所有 \(x\) 上成立的概率偏离 \(1/2\)。这里 \(\alpha \cdot x\) 表示 \(\alpha\) 与 \(x\) 的内积（即各比特按位与后异或求和）。定义偏差（bias）为：

\[\epsilon(\alpha, \beta) = \Pr[\alpha \cdot x \oplus \beta \cdot S(x) = 0] - \frac{1}{2}\]

线性近似表（Linear Approximation Table, LAT）。 类似于 DDT，LAT 的第 \((\alpha, \beta)\) 项记录了满足上述等式的 \(x\) 的个数减去 \(2^{n-1}\)。LAT 中绝对值越小的项越好，意味着 S 盒的输出与输入之间没有明显的线性关系。

堆积引理（Piling-up Lemma）。 线性分析的力量在于可以将多轮的偏差叠加。Matsui 的堆积引理指出：若有 \(m\) 个独立的线性近似，各自的偏差为 \(\epsilon_1, \epsilon_2, \ldots, \epsilon_m\)，则它们的异或组合的偏差为：

\[\epsilon_{1,2,\ldots,m} = 2^{m-1} \prod_{i=1}^{m} \epsilon_i\]

这一结果意味着只要每一轮的偏差不为零，多轮线性近似的总偏差虽然会指数级衰减，但只要总偏差 \(|\epsilon|\) 仍然可以被检测到（即 \(|\epsilon| \gg 2^{-n/2}\)），攻击就是可行的。

对 DES 的攻击。 Matsui 利用线性分析对完整 16 轮 DES 发起了实际攻击。他找到了一条 14 轮的线性近似，其偏差约为 \(2^{-21}\)。根据数据复杂度与偏差的关系（约需 \(O(1/\epsilon^2)\) 个已知明文），攻击需要约 \(2^{43}\) 个已知明文-密文对，远少于 \(2^{55}\) 的暴力搜索复杂度。1994 年，Matsui 在实验中成功恢复了完整 DES 密钥，这是线性密码分析最经典的实际应用。

与差分分析的对偶关系。 差分分析和线性分析之间存在深刻的数学对偶性。差分分析在”值域”中工作——研究函数值之间的差分关系；线性分析在”频域”中工作——研究 Walsh-Hadamard 变换下的频谱性质。一个 S 盒如果对差分分析安全（DDT 中的最大值小），那么它对线性分析通常也有一定的安全性，反之亦然。这种对偶关系并非巧合，而是由离散 Fourier 分析的基本定理所保证的。

一个值得深思的现象是，线性密码分析相对于差分分析在公众认知中被严重低估。差分分析因其「选择明文」的戏剧性设定而广为人知——攻击者精心构造输入对，观察输出差分，这在直觉上很容易理解。但线性分析的实际威胁性在许多场景下更大，原因在于它只需要已知明文（known plaintext），而非选择明文（chosen plaintext）。在真实世界中，攻击者往往能观察到大量的明文-密文对（例如已知格式的协议头部），但很少有机会让目标系统加密自己精心选择的数据。Matsui 对完整 16 轮 DES 的线性攻击只需 \(2^{43}\) 个已知明文即可成功，而差分攻击需要的选择明文数量接近整个密文空间——这使得线性攻击在实践中对 DES 的威胁远大于差分攻击。从这个意义上说，线性密码分析提醒我们：评估一种攻击的实际危险性，不仅要看其计算复杂度，更要看其数据获取模型是否在现实场景中可行。

五、不可能差分与截断差分

经典差分分析寻找的是高概率差分特征。然而，密码分析者后来发现，概率为零的差分（即”不可能差分”）同样具有强大的攻击能力。

不可能差分分析（Impossible Differential Cryptanalysis）。 其基本策略是：找到一条中间轮的差分转移，其概率恰好为零（即不可能发生），然后利用这一事实排除候选密钥。具体做法是从加密方向和解密方向分别推导差分，如果在中间某一轮产生矛盾（即正向推导出的差分与反向推导出的差分在同一位置不一致），则可以确信这条路径上的密钥猜测是错误的。通过逐步排除不可能的密钥，攻击者最终锁定正确密钥。这种”从中间会合”（miss-in-the-middle）策略的威力在于，它不需要找到高概率的差分路径——事实上，对于安全性较好的密码，高概率路径可能根本不存在，但不可能差分却往往能覆盖相当数量的中间轮。Biham、Biryukov 和 Shamir 于 1999 年将不可能差分分析系统化，并成功地将其应用于 Skipjack、IDEA 和 Khufu 等密码的缩减版本。在 AES 的分析中，不可能差分可以覆盖 4 轮 AES 的内部结构，从而对 6 轮甚至 7 轮 AES 构成有效攻击。

截断差分（Truncated Differential）。 由 Knudsen 于 1994 年提出。与经典差分分析精确追踪每一比特的差分不同，截断差分只关注差分的部分信息——例如，只追踪某些字节是否为零或非零，而不关心具体的非零值是什么。这种”粗粒度”的差分追踪可以将许多不同的精确差分特征合并为一类，从而获得更高的总概率。截断差分分析对以字节为单位操作的密码（如 AES）尤其有效。

积分密码分析（Integral Cryptanalysis）。 积分攻击（也称为 Square 攻击或饱和攻击）可以看作截断差分的进一步推广。攻击者选择一组明文，使得某些字节位置遍历所有可能值（“活跃”字节），而其余字节固定（“常数”字节）。然后追踪经过若干轮加密后，各字节位置上的值集合的代数性质——是否仍然遍历所有值（“全活跃”）、是否异或和为零（“平衡”）、或者已经退化为常数。积分分析最早被用于分析 Square 密码（AES 的前身），后来成为分析 AES 类结构的标准工具之一。

六、S-Box 设计准则

差分分析和线性分析的出现直接催生了一套严格的 S 盒设计准则。一个好的 S 盒必须同时满足多项密码学性质。

差分均匀性（Differential Uniformity）。 S 盒 \(S\) 的差分均匀度定义为 DDT 中非零输入差分行的最大值：

\[\delta(S) = \max_{\alpha \neq 0, \beta} \text{DDT}(\alpha, \beta)\]

\(\delta(S)\) 越小越好。当 \(\delta(S) = 2\) 时（这是偶数幂 \(n\) 下可能达到的理论最小值），\(S\) 被称为几乎完美非线性函数（Almost Perfect Nonlinear, APN）。APN 函数提供了对差分分析的最优抵抗力。

非线性度（Nonlinearity）。 S 盒的非线性度衡量它与所有仿射函数之间的最小汉明距离。在 LAT 的语言下，非线性度与 LAT 中绝对值的最大值成反比关系。非线性度越高，S 盒对线性分析的抵抗力越强。对于 \(n\) 比特布尔函数，非线性度的上界为 \(2^{n-1} - 2^{n/2 - 1}\)（Covering Radius Bound），达到此上界的函数称为 Bent 函数。但 Bent 函数不是置换，因此不能直接用作 S 盒。实际密码中通常追求非线性度尽可能接近 Bent 函数上界的置换。

代数次数（Algebraic Degree）。 将 S 盒的每个输出比特视为输入比特的 \(\text{GF}(2)\) 多项式，其最高次项的次数称为代数次数。代数次数越高，S 盒越难以被代数攻击所突破。对于 \(n\) 比特 S 盒，代数次数的上界为 \(n - 1\)（对于置换）。AES 的 S 盒基于 \(\text{GF}(2^8)\) 上的求逆运算，其代数次数为 7（即 \(8 - 1\)），同时具有极低的差分均匀度（\(\delta = 4\)）和很高的非线性度。

其他准则。 除上述三大核心准则外，S 盒设计还需考虑：雪崩效应（Avalanche Effect）——输入的单比特变化应导致输出约一半比特翻转；比特独立性（Bit Independence Criterion）——输出比特之间应尽可能独立；以及实现效率——S 盒不能过大以至于无法高效实现。

七、Wide Trail 策略

差分分析和线性分析不仅影响了 S 盒的设计，更深刻地改变了分组密码整体结构的设计理念。Rijndael（即 AES）的设计者 Daemen 和 Rijmen 提出的宽轨迹策略（Wide Trail Strategy）是这一变革的典范。

设计哲学。 宽轨迹策略的核心思想是：通过精心设计线性扩散层（Linear Diffusion Layer），确保任何差分特征或线性近似在穿越多轮后，必须激活足够多的 S 盒。由于每个活跃 S 盒都会引入一定的概率衰减（差分分析中为 \(\delta / 2^n\)，线性分析中为对应的偏差），激活的 S 盒越多，总概率衰减得越快，攻击就越困难。

分支数（Branch Number）。 衡量线性扩散层扩散能力的关键参数是分支数。对于线性变换 \(\theta: \{0,1\}^{mn} \to \{0,1\}^{mn}\)（将输入视为 \(m\) 个 \(n\) 比特字），其微分分支数（Differential Branch Number）定义为：

\[\mathcal{B}_d(\theta) = \min_{a \neq 0} \left( w(a) + w(\theta(a)) \right)\]

其中 \(w(a)\) 表示向量 \(a\)（视为 \(m\) 个 \(n\) 比特字的序列）中非零字的个数。类似地可以定义线性分支数。分支数越大，扩散越充分。

MDS 矩阵。 最大距离可分码（Maximum Distance Separable, MDS）矩阵是实现最优分支数的工具。一个 \(m \times m\) 的矩阵（元素在 \(\text{GF}(2^n)\) 上）如果它的所有子方阵都是非奇异的，则称为 MDS 矩阵。MDS 矩阵的分支数达到理论最大值 \(m + 1\)。AES 中的 MixColumns 操作使用的就是一个 \(4 \times 4\) 的 MDS 矩阵，其分支数为 5，意味着任何跨越两轮的差分特征至少会激活 5 个 S 盒。

可证明安全界。 宽轨迹策略最大的优势在于它能提供可证明的安全下界。对于 AES，可以证明任何 4 轮差分特征至少激活 25 个 S 盒。由于 AES S 盒的最大差分概率为 \(2^{-6}\)，4 轮差分特征的概率至多为 \((2^{-6})^{25} = 2^{-150}\)，远低于 \(2^{-128}\) 的分组大小。这保证了完整 10 轮（128 比特密钥）AES 对差分分析有充足的安全余量。

八、代数攻击与其他分析方法

差分分析和线性分析虽然是最经典的两种分析技术，但密码分析的工具箱远不止于此。

代数攻击（Algebraic Attacks）。 代数攻击将密码系统表示为 \(\text{GF}(2)\) 上的多项式方程组，然后尝试用 Grobner 基、XL 算法或 SAT 求解器等工具直接求解密钥。对于代数次数较低的密码组件，代数攻击可能非常高效。这也是为什么现代 S 盒设计要求较高的代数次数和较复杂的代数结构。更具体地说，代数攻击的流程是：首先将密码的每一轮运算（包括 S 盒的非线性变换、线性扩散层和密钥混合步骤）表示为关于明文比特、密钥比特和中间状态比特的多元多项式方程；然后将所有轮的方程联立，形成一个大规模的超定或恰定方程组；最后利用代数求解算法尝试从中提取密钥。对于 AES，其 S 盒基于 \(\text{GF}(2^8)\) 上的求逆运算，可以用仅 23 个二次方程来精确描述一个 S 盒的输入输出关系，整个 AES-128 可以表示为一个包含约 8000 个方程和 1600 个变量的二次方程组。尽管目前已知的代数求解算法在这一规模上尚不足以威胁完整 AES 的安全性，但代数攻击对轮数较少的简化版本或代数结构较弱的密码仍然构成实际威胁。

插值攻击（Interpolation Attacks）。 由 Jakobsen 和 Knudsen 于 1997 年提出。如果密码可以被表示为 \(\text{GF}(2^n)\) 上次数较低的多项式，则攻击者可以通过收集足够的明文-密文对来插值该多项式，从而完全恢复加密函数。插值攻击对使用简单代数结构（如幂映射）作为 S 盒的密码特别有效。

滑动攻击（Slide Attacks）。 由 Biryukov 和 Wagner 于 1999 年提出。传统密码分析的复杂度通常随轮数增加而增长，但滑动攻击是一个例外——它利用密码轮函数的自相似性（即每轮结构相同且轮密钥周期性重复），将多轮密码的分析归约为对单轮的分析。滑动攻击的复杂度仅取决于轮函数本身的强度，与总轮数无关。这一发现迫使密码设计者引入轮常数（Round Constants）和非周期性的密钥编排（Key Schedule），以打破轮之间的自相似结构。

相关密钥攻击（Related-key Attacks）。 攻击者不仅能选择明文，还能请求在多个存在已知关系（如异或差分）的密钥下加密。Biham 于 1993 年提出了相关密钥差分攻击的概念。2009 年，Biryukov、Khovratovich 和 Nikolic 利用相关密钥差分攻击对 AES-256 的完整 14 轮发起了理论攻击（虽然攻击复杂度为 \(2^{99.5}\)，低于暴力搜索的 \(2^{256}\)，但在实际中仍不可行）。这一结果揭示了 AES 密钥编排的相对薄弱性，引发了关于密钥编排设计准则的广泛讨论。

Boomerang 攻击。 由 Wagner 于 1999 年提出，它巧妙地将两条短的差分特征拼接起来，即使每条特征各自覆盖的轮数不多、概率不高，拼接后也能攻击更多轮。Boomerang 攻击及其改进版本（如矩形攻击）已成为现代密码分析的标准工具。

九、密码分析的实际影响

密码分析技术不仅仅是纯学术研究——它们深刻影响了实际密码标准的选择与演进。

AES 竞赛。 1997 年 NIST 发起的 AES 竞赛明确要求候选密码必须对差分分析和线性分析提供可证明的安全边界。这一要求直接受到了 DES 被差分和线性分析削弱的教训。最终胜出的 Rijndael 正是因为其宽轨迹策略提供了清晰的安全性证明而脱颖而出。其他候选者如 Serpent 也提供了类似的安全边界，但在性能上稍逊。AES 竞赛确立了一个范式：现代分组密码的设计必须伴随着对主要密码分析方法的安全性论证。

SHA-3 竞赛。 2007 年启动的 SHA-3 竞赛同样深受密码分析发展的推动。SHA-1 的碰撞攻击（Wang 等人于 2005 年将复杂度从 \(2^{80}\) 降至 \(2^{63}\)）直接促成了这次竞赛。最终选定的 Keccak（即 SHA-3）采用了全新的海绵结构（Sponge Construction），其设计哲学之一就是以足够宽的状态和简单的轮函数来抵御差分和线性分析。Keccak 的设计者提供了详尽的差分界和线性界分析，展示了其内部置换对已知攻击方法的安全余量。

实际密码的攻破。 密码分析在实践中的影响不容忽视。FEAL-4 密码在差分分析下只需 8 个选择明文即可完全攻破；CSS（Content Scramble System，用于 DVD 加密）的密钥恢复只需几秒钟；RC4 流密码的统计偏差导致了 WEP 协议的全面瓦解。这些案例反复证明了一条铁律：任何未经严格密码分析审查的密码方案，在部署到真实世界后被攻破只是时间问题。

从分析到设计的闭环。 现代密码学已经形成了一个健康的”分析-设计”闭环：新的密码分析技术被发现后，密码设计者立即将其纳入设计准则，确保下一代密码能够抵抗该技术。差分分析催生了差分均匀性准则和宽轨迹策略；线性分析催生了非线性度准则和分支数优化；代数攻击催生了对代数次数和代数结构的审查；相关密钥攻击催生了更强的密钥编排设计。这种对抗与进化的动态平衡，正是密码学作为一门科学持续进步的核心驱动力。

概率论作为贯穿所有这些分析方法的数学主线，其重要性怎么强调都不过分。生日界决定了哈希函数输出长度的最低要求；差分概率决定了 S 盒和整体结构的设计参数；线性偏差约束了分组密码至少需要多少轮才能安全。理解这些概率论工具，不仅是密码分析者的必修课，更是每一位密码设计者的基本功。唯有深入理解攻击，才能设计出真正安全的密码。

密码学百科系列 · 第 38 篇

← 上一篇：格密码数学基础 | 系列目录 | 下一篇：计算复杂性与归约 →