1948 年，Claude Shannon 发表了划时代的论文《A Mathematical Theory of Communication》，奠定了信息论（Information Theory）这一全新学科。仅仅一年后，他又发表了《Communication Theory of Secrecy Systems》，将信息论的数学工具系统地应用于密码学分析。这两篇论文不仅建立了现代通信理论的数学基础，更从根本上改变了人类对”保密”这一概念的理解方式——从此，密码学从一门依赖直觉和经验的艺术，转变为一门建立在严格数学证明之上的科学。

本文将从 Shannon 熵的定义出发，逐步推导出完美保密的条件，理解一次一密为何是唯一的完美保密系统，认识完美保密在实际中的不可行性，进而理解从信息论安全到计算安全的范式转换——这一转换正是现代密码学得以存在的根本原因。我们还将介绍 Min-Entropy、Leftover Hash Lemma 等现代信息论工具在密码学中的关键应用。

笔者认为，信息论是密码学中最容易被低估的「被遗忘的基础」。在今天的密码学工程实践中，大多数从业者直接跳入对称加密、公钥密码和协议设计，而对信息论只有浅尝辄止的了解——他们知道 Shannon 的名字，知道一次一密，但很少真正理解熵的深层含义以及它如何从根本上约束了所有密码学原语的设计空间。然而，一旦你深入理解了熵和信息论，你看待每一个密码学组件的方式都会发生改变：你会开始问「这个方案的安全性最终依赖于多少比特的真正随机性？」「密文是否比明文包含了更少的可利用结构？」「密钥派生过程中是否存在熵损失？」这些问题的答案往往比选择哪个具体算法更为根本。

先用一张图把本文的核心关系串起来。

graph TD
    A[概率分布] --> B[Shannon 熵]
    B --> C[条件熵]
    C --> D[互信息]
    D --> E[完美保密]

在 Shannon 之前，“信息”是一个模糊的、定性的概念。我们凭直觉知道，一件罕见事件的发生比一件常见事件的发生”包含更多信息”——“太阳从东方升起”几乎不传递任何信息，而”明天有小行星撞击地球”则包含巨大的信息量。Shannon 的天才之处在于将这种直觉精确地数学化了。

自信息：单个事件的信息量

对于一个发生概率为 P(x) 的事件 x，Shannon 定义其自信息（Self-information）为：

I(x) = -log₂ P(x)

这个定义具有美妙的性质。首先，确定事件（P(x) = 1）的自信息为零——如果一件事必然发生，它不传递任何信息。其次，不可能事件（P(x) → 0）的自信息趋向无穷大——越不可能发生的事情，一旦发生就越”令人惊讶”。第三，两个独立事件同时发生的信息量等于它们各自信息量之和：I(x, y) = I(x) + I(y)。使用对数恰好保证了这种可加性。

选择以 2 为底的对数意味着信息的基本单位是比特（bit）。一个公平硬币的抛掷结果包含 I(正面) = -log₂(1/2) = 1 比特的信息。直觉上完全合理：我们需要恰好 1 个二进制数字来编码这个结果。

Shannon 熵：不确定性的度量

自信息度量的是单个事件的信息量。当我们需要度量一个随机变量（或概率分布）整体的不确定性时，自然的做法是计算自信息的期望值。这就是 Shannon 熵（Shannon Entropy）：

H(X) = -Σ P(x) log₂ P(x)

其中求和遍历随机变量 X 的所有可能取值。Shannon 熵 H(X) 衡量的是：在观察到 X 的实际取值之前，我们对结果的平均不确定程度。也可以理解为：为了无损地编码 X 的取值，平均每个符号至少需要 H(X) 比特——这正是 Shannon 信源编码定理（Source Coding Theorem）的核心内容。

Shannon 熵具有以下关键性质：

非负性：H(X) ≥ 0，等号成立当且仅当 X 是确定性的（某个值的概率为 1）。不确定性不可能是负的。

最大值在均匀分布时取得：如果 X 有 n 个可能取值，则 H(X) ≤ log₂ n，等号成立当且仅当 X 服从均匀分布。这意味着均匀分布是”最不确定”的分布——所有结果同等可能时，我们最难预测。这一性质对密码学至关重要：好的密钥应当具有最大熵，即服从均匀分布。

让我们通过具体例子建立直觉。

公平硬币：P(正) = P(反) = 1/2，H(X) = -2 × (1/2) × log₂(1/2) = 1 比特。这是最大熵的情况。

偏心硬币：若 P(正) = 0.9，P(反) = 0.1，则 H(X) = -(0.9 × log₂ 0.9 + 0.1 × log₂ 0.1) ≈ 0.469 比特。偏心越严重，熵越低——因为结果更可预测。

公平六面骰子：H(X) = log₂ 6 ≈ 2.585 比特。

英文文本：如果把每个字母看作独立的随机变量（忽略上下文），英文字母表的熵约为 4.2 比特/字符。但考虑到字母之间的统计依赖性（如 “q” 后面几乎总是跟 “u”）以及单词和语法的约束，Shannon 估计英文文本的真正熵大约在 1.0 到 1.5 比特/字符之间。这意味着英文中存在大量的冗余（redundancy），这正是密码分析得以成功的根本原因——冗余使得密文中残留了可被统计利用的结构。

这里有一个大多数教科书一笔带过、但值得深思的联系：压缩与加密本质上是同一枚硬币的两面。压缩的目标是消除冗余，将数据表示为尽可能接近其信息论下界（即熵）的形式；加密的目标是使密文在统计上不可区分于随机数据——而一个完美随机的字符串恰好是不可压缩的。从这个视角看，一个好的加密方案必须将明文中的所有统计结构（冗余）彻底打散，使得密文达到最大熵——这与无损压缩的效果在某种意义上是对称的。这也解释了一条实用经验法则：先压缩后加密通常优于先加密后压缩，因为加密后的数据已接近最大熵，几乎不可压缩；而先压缩能消除明文中攻击者可能利用的统计结构。不过，这条规则也有例外——CRIME 和 BREACH 攻击正是利用了「先压缩后加密」管道中压缩率与明文内容的关联性，通过观察密文长度变化来推断明文信息。这个精妙的攻击再次印证了信息论视角的重要性：压缩率本身就是在泄露关于明文的互信息。

联合熵、条件熵与互信息

当我们同时考虑两个随机变量 X 和 Y 时，需要更丰富的信息度量工具。以下四个概念紧密关联，构成信息论的核心工具集：

联合熵:    H(X, Y)  = -Σ Σ P(x, y) log₂ P(x, y)
条件熵:    H(X|Y)   = -Σ Σ P(x, y) log₂ P(x|y) = H(X, Y) - H(Y)
互信息:    I(X; Y)  = H(X) - H(X|Y) = H(Y) - H(Y|X) = H(X) + H(Y) - H(X, Y)
链式法则:  H(X₁, ..., Xₙ) = Σᵢ H(Xᵢ | X₁, ..., Xᵢ₋₁)

联合熵衡量两个随机变量的总不确定性。条件熵衡量在已知 Y 的情况下 X 的剩余不确定性，满足 H(X|Y) ≤ H(X)——知道额外信息永远不会增加不确定性（平均而言），等号成立当且仅当 X 和 Y 独立。互信息衡量知道 Y 能消除多少关于 X 的不确定性，它是对称的且非负，I(X; Y) = 0 当且仅当 X 和 Y 独立。互信息在密码学中的含义非常直观：如果 M 是明文、C 是密文，那么 I(M; C) 衡量的是密文泄露了多少关于明文的信息。完美保密恰好要求 I(M; C) = 0。最后，链式法则将以上概念优美地联系在一起——多个变量的联合不确定性可以分解为逐步条件化的不确定性之和。

以下 Python 代码演示了 Shannon 熵的计算：

import math

def shannon_entropy(probs):
    """计算给定概率分布的 Shannon 熵（单位：比特）"""
    return -sum(p * math.log2(p) for p in probs if p > 0)

# 几个典型分布的熵——与上文的直觉分析一一对应
print(f"公平硬币：{shannon_entropy([0.5, 0.5]):.4f} 比特")          # 1.0000
print(f"偏心硬币 (0.9/0.1)：{shannon_entropy([0.9, 0.1]):.4f} 比特")  # 0.4690
print(f"公平骰子：{shannon_entropy([1/6]*6):.4f} 比特")              # 2.5850
print(f"均匀 8-bit：{shannon_entropy([1/256]*256):.4f} 比特")        # 8.0000

二、完美保密的形式化定义

有了信息论的数学工具，Shannon 得以给出”完美保密”的精确定义——这是人类历史上第一次用数学语言严格表述”不可破解”的含义。

Shannon 的定义

一个加密方案 (Gen, Enc, Dec) 满足完美保密（Perfect Secrecy），当且仅当对所有明文 m ∈ M 和所有密文 c ∈ C（其中 P(C = c) > 0）：

P(M = m | C = c) = P(M = m)

这个等式的含义极其深刻：观察到密文 c 之后，攻击者对明文 m 的后验概率与先验概率完全相同。换言之，密文没有提供关于明文的任何信息——无论攻击者拥有多强的计算能力、使用多聪明的算法，密文对于破解都毫无用处。

等价表述

完美保密有几个重要的等价表述，从不同角度揭示了同一本质：

信息论表述：H(M | C) = H(M)。密文不减少明文的不确定性，或等价地，互信息 I(M; C) = 0。

分布独立性表述：对所有 m₀, m₁ ∈ M 和所有 c ∈ C：

P(Enc(K, m₀) = c) = P(Enc(K, m₁) = c)

即，无论加密哪条明文消息，产生任何特定密文的概率都是相同的。攻击者看到密文后，无法判断它是由哪条明文生成的，因为所有明文产生该密文的可能性完全一样。

不可区分性表述：对于任意两条等长消息 m₀ 和 m₁，加密 m₀ 得到的密文分布与加密 m₁ 得到的密文分布完全相同。这可以表述为一个”不可区分性实验”——给攻击者一个密文，让他猜测底层明文是 m₀ 还是 m₁，他的成功概率恰好是 1/2，与随机猜测无异。

为何这是最强的保密定义

完美保密之所以是最强的保密定义，原因在于它对攻击者没有施加任何计算限制。无论攻击者是一台笔记本电脑、一个超级计算机集群，还是一台（假想的）具有无限计算能力的机器，完美保密的方案对他们都同样安全。这种安全性完全来自信息论本身——密文中根本不包含关于明文的信息，无论你如何处理密文，都无法从中”榨取”出任何关于明文的知识。

这与后来我们将讨论的计算安全形成了鲜明对比：计算安全的方案在数学上是可以被破解的，只是破解所需的计算量超出了任何实际攻击者的能力。

三、一次一密：唯一的完美保密系统

OTP 的构造

一次一密（One-Time Pad，OTP），也称为 Vernam 密码（Vernam Cipher），是密码学中最简单也最优美的加密方案。其构造如下：

• 密钥生成：均匀随机选择一个与明文等长的密钥 K ∈ {0, 1}ⁿ
• 加密：C = M ⊕ K（逐比特异或）
• 解密：M = C ⊕ K

这里的 ⊕ 表示异或（XOR）运算。整个方案的优美之处在于其极端的简洁性——加密和解密是完全相同的运算。

完美保密性的证明

定理：一次一密满足完美保密。

证明：对于任意明文 m 和任意密文 c，我们需要证明 P(C = c | M = m) 不依赖于 m 的选择。

当 M = m 时，C = m ⊕ K。要使 C = c，需要 K = m ⊕ c。由于 K 是均匀随机选取的 n 比特串，K 取任何特定值的概率为 2⁻ⁿ。因此：

P(C = c | M = m) = P(K = m ⊕ c) = 2⁻ⁿ

这个概率与 m 的选择无关。根据贝叶斯定理：

P(M = m | C = c) = P(C = c | M = m) × P(M = m) / P(C = c)

由于 P(C = c | M = m) = 2⁻ⁿ 对所有 m 成立，且 P(C = c) = Σₘ P(C = c | M = m) × P(M = m) = 2⁻ⁿ，我们得到：

P(M = m | C = c) = 2⁻ⁿ × P(M = m) / 2⁻ⁿ = P(M = m)

证毕。这个证明虽然简短，但揭示了 OTP 安全性的根本原因：对于每一个密文 c，明文空间中的每一条消息 m 都恰好对应唯一的一个密钥 k = m ⊕ c，而这些密钥的概率都相等。因此，密文 c 与所有明文都”同样兼容”，攻击者无法排除任何可能性。

实际困难

OTP 的完美安全性伴随着严苛的实际要求：

密钥必须与明文等长：加密 1 GB 的数据需要 1 GB 的密钥。密钥的传输和存储本身就构成了巨大的后勤挑战。如果你有安全的信道来传输密钥，那为什么不直接用这个信道传输明文呢？

密钥必须完全随机：密钥必须是真正的均匀随机比特串。伪随机数生成器（PRNG）生成的密钥不满足完美保密的条件——因为 PRNG 的输出由更短的种子确定，密钥空间实际上小于明文空间。

密钥绝对不能重复使用：这是最关键也最容易被违反的要求。如果同一个密钥 K 被用于加密两条消息 M₁ 和 M₂，攻击者可以计算 C₁ ⊕ C₂ = M₁ ⊕ M₂，直接得到两条明文的异或。在这个结果上应用频率分析等技术，往往可以恢复出两条明文的内容。

Venona 项目：密钥重用的惨痛教训

冷战期间，苏联情报机构使用一次一密系统保护其外交和间谍通信。在密码学层面，这本应是不可破解的。然而，由于战时物资短缺和后勤管理失误，苏联密码部门在 1942 年至 1948 年间复制了部分一次一密密钥本，导致相同的密钥被用于加密不同的消息。

美国国家安全局（NSA）的前身机构在 Venona 项目中发现了这一失误，并通过利用密钥重用漏洞，在 1946 年到 1980 年间逐步解密了约 3000 条苏联情报消息。这些解密的消息揭露了多名苏联间谍，包括在洛斯阿拉莫斯国家实验室从事原子弹研究的 Klaus Fuchs 和 Julius Rosenberg 夫妇。

Venona 项目是密码学史上最深刻的教训之一：一个理论上不可破解的系统，仅仅因为一条操作规范的违反——密钥的重复使用——就彻底崩溃了。这也说明了一个更广泛的道理：密码学系统的安全性不仅取决于数学算法本身，还取决于密钥管理等操作层面的严格执行。

以下代码演示了 OTP 加密以及密钥重用的危险性：

import os

def otp_encrypt(plaintext: bytes, key: bytes) -> bytes:
    assert len(key) >= len(plaintext), "密钥长度必须不小于明文长度"
    return bytes(p ^ k for p, k in zip(plaintext, key))

# 加密与解密运算完全相同：逐字节异或
msg = "HELLO WORLD".encode()
key = os.urandom(len(msg))
ct = otp_encrypt(msg, key)
print(f"明文：{msg}  密文：{ct.hex()}  解密：{otp_encrypt(ct, key)}")

# 完美保密性质：同一密文可被任意明文"合理解释"
fake_key = bytes(c ^ t for c, t in zip(ct, "ZZZZZZZZZZZ".encode()))
print(f"同一密文用不同密钥解密：{otp_encrypt(ct, fake_key)}")

# 密钥重用的危险：C1 ⊕ C2 = M1 ⊕ M2，直接泄露明文关系
key_reused = os.urandom(20)
c1 = otp_encrypt("ATTACK AT DAWN      ".encode()[:20], key_reused)
c2 = otp_encrypt("RETREAT TO BASE     ".encode()[:20], key_reused)
print(f"C1 ⊕ C2 = M1 ⊕ M2：{bytes(a ^ b for a, b in zip(c1, c2)).hex()}")

四、Shannon 定理：完美保密的代价

OTP 的实际缺陷并非偶然。Shannon 证明了一个深刻的定理，表明完美保密系统的密钥长度必然不小于消息长度——这是一个无法绕开的信息论下界。

定理陈述

Shannon 定理（Shannon’s Theorem on Perfect Secrecy）：如果一个加密方案 (Gen, Enc, Dec) 满足完美保密，则密钥空间的大小必须满足 |K| ≥ |M|，即密钥空间至少与明文空间一样大。等价地，密钥的长度至少与明文的长度相同。

证明思路

假设 |K| < |M|，我们推出矛盾。考虑一个密文 c 使得 P(C = c) > 0。令 M(c) 为所有可能通过某个密钥解密 c 得到的明文集合：

M(c) = { Dec(k, c) : k ∈ K }

由于每个密钥最多产生一个解密结果，|M(c)| ≤ |K| < |M|。因此存在某个明文 m’ ∈ M 使得 m’ ∉ M(c)——没有任何密钥能将 c 解密为 m’。

这意味着 P(M = m’ | C = c) = 0。但如果 P(M = m’) > 0（即 m’ 是一条有正概率的合法明文），我们就有：

P(M = m' | C = c) = 0 ≠ P(M = m') > 0

这违反了完美保密的定义。因此 |K| ≥ |M| 是完美保密的必要条件。

深远影响

Shannon 定理的影响是深远的。它断言：如果我们坚持要求信息论意义上的完美保密，就必须使用与消息等长的密钥。这使得完美保密在大多数实际场景下不可行——想象一下，为了安全地发送一封 1 MB 的电子邮件，通信双方需要事先通过安全信道交换 1 MB 的密钥！如果他们有安全信道可以交换 1 MB 的密钥，为什么不直接通过这个信道发送邮件呢？

这个看似悲观的定理实际上催生了现代密码学最核心的思想转变：既然信息论安全在实践中不可行，那么我们能否退而求其次，接受一种”几乎安全”的定义——一种在计算上不可破解但在信息论上并非完美的安全性？

答案是肯定的，这正是计算安全（Computational Security）的出发点，也是现代密码学的基石。Shannon 定理不是密码学的终结，而是新密码学的起点——它精确地指出了信息论安全的边界，从而为计算安全的范式提供了理论动机。

从完美保密到现代密码学：范式演进全景

下表梳理了从完美保密到现代密码学体系的演进脉络——每一步都是对前一步局限性的回应：

演进逻辑：完美保密 →（Shannon 定理揭示代价不可接受）→ 计算安全 →（以计算不可区分性为核心形式化工具）→ 现代密码学完整体系

五、从信息论安全到计算安全

Shannon 定理告诉我们，追求绝对的保密需要付出不可接受的代价。现代密码学的核心洞见在于：放弃”绝对保密”的理想，转而追求”对任何现实可行的攻击者而言实际上不可破解”的安全性。这一范式转换是 20 世纪密码学最重要的思想突破。

信息论安全：抵御无限计算能力的攻击者

信息论安全（Information-Theoretic Security），也称为无条件安全（Unconditional Security），意味着即使攻击者拥有无限的计算资源和无限的时间，系统仍然是安全的。一次一密就是信息论安全的典范——密文中根本不包含明文的信息，无论攻击者如何计算都无济于事。

信息论安全的优势是显而易见的：安全性不依赖于任何未经证实的数学假设（如大整数分解的困难性），不受计算技术进步的威胁（量子计算机也无法破解），并且安全性可以在不做任何假设的情况下被严格证明。

然而，Shannon 定理告诉我们，这种安全性的代价过于高昂。除了密钥长度的限制外，信息论安全的方案在功能上也非常有限——例如，无法实现公钥加密等现代密码学的核心功能。

计算安全：利用攻击者的有限性

计算安全（Computational Security）的核心假设是：现实中的攻击者受到计算资源的限制。具体而言，我们假设攻击者是一个概率多项式时间（Probabilistic Polynomial Time，PPT）算法——它的运行时间是安全参数 n 的某个多项式 p(n)。

在计算安全的框架下，我们允许两种”退让”：

安全性可以有可忽略的失败概率：方案不需要在所有情况下都安全——允许以一个可忽略函数（Negligible Function）的概率失败。函数 ε(n) 是可忽略的，当对任意正多项式 p(·) 和所有足够大的 n，有 ε(n) < 1/p(n)。直觉上，可忽略函数比任何多项式的倒数都衰减得更快——例如 2⁻ⁿ、2⁻√ⁿ 等。当安全参数 n 取 128 或 256 时，2⁻ⁿ 小到了宇宙中所有原子加起来都无法利用的程度。

安全性只针对高效的攻击者：我们不要求方案对计算无限的攻击者安全——只要求对多项式时间的攻击者安全。指数时间的暴力搜索虽然理论上可以破解任何方案，但在实际中是不可行的。

这两个退让看似微小，实际上开启了一个全新的世界。在这个框架下，密钥可以远短于消息（例如 256 比特），因为安全性不再依赖于密钥空间覆盖整个明文空间，而是依赖于攻击者在有限时间内搜索密钥空间的不可行性。

语义安全：完美保密的计算类比

语义安全（Semantic Security）是完美保密在计算安全框架下的对应概念。Goldwasser 和 Micali 在 1984 年的开创性工作中提出了这一定义。

非形式化地说，一个加密方案是语义安全的，当且仅当攻击者（限制为 PPT）观察密文后能够计算出的关于明文的任何信息，都可以在不观察密文的情况下同样高效地计算出来。换言之，密文对 PPT 攻击者而言”不泄露任何信息”——这与完美保密的精神完全一致，只是将”任何攻击者”弱化为”任何 PPT 攻击者”。

语义安全后来被证明等价于 IND-CPA（Indistinguishability under Chosen-Plaintext Attack，选择明文攻击下的不可区分性），后者因其更容易用于安全性证明而成为标准定义。

为何这一区分至关重要

信息论安全与计算安全的区别不仅是技术性的细节——它定义了整个现代密码学的可能性边界。如果我们坚持信息论安全，那么公钥加密、数字签名、零知识证明等现代密码学的核心构件都不可能存在。正是因为接受了计算安全的范式，密码学才从一个局限于对称加密的狭窄领域，发展成为支撑整个互联网安全基础设施的广阔学科。

这一范式转换也引入了一个根本性的风险：计算安全依赖于某些数学问题（如大整数分解、离散对数）的计算困难性假设。如果这些假设被证伪（例如，量子计算机可以高效地分解大整数），那么基于这些假设的所有密码学方案都将失效。这就是后量子密码学（Post-Quantum Cryptography）研究的动机——我们需要基于量子计算机也无法高效求解的数学问题来构建密码学方案。

在我看来，从信息论安全到计算安全的范式转换，是密码学史上最重要的单一思想跃迁——其重要性甚至超过了任何具体算法的发明。Shannon 定理本质上是一个”不可能性定理”：它告诉我们，在信息论的框架内，安全的加密通信需要预先共享与消息等量的秘密，这似乎宣判了实用密码学的死刑。但 Goldwasser、Micali、Yao 等人在 1980 年代的洞见是：如果我们将”安全”的定义从”信息论上不可能破解”放宽到”计算上不可行破解”，整个图景就发生了根本性的改变。这不仅仅是一个技术上的让步——它是一次认识论层面的革命：我们承认了”实践中的不可能”与”数学上的不可能”具有同等的实用价值。没有这一思想转变，就不会有 RSA，不会有 Diffie-Hellman，不会有 TLS——我们今天所依赖的整个数字安全基础设施都建立在这一哲学性的让步之上。

六、计算不可区分性

计算安全的核心技术概念是计算不可区分性（Computational Indistinguishability），它是形式化”两个东西在计算上看起来一样”的精确数学工具。

形式化定义

两个概率分布族 {Xₙ} 和 {Yₙ}（以安全参数 n 为索引）是计算不可区分的，当且仅当对任何 PPT 算法（区分器）D：

|Pr[D(Xₙ) = 1] - Pr[D(Yₙ) = 1]| ≤ negl(n)

其中 negl(n) 是某个可忽略函数。直觉上，这意味着没有任何高效算法能有效地区分从 Xₙ 中取出的样本和从 Yₙ 中取出的样本——两者”在计算上看起来一样”。

区分器 D 可以执行任何它想要的计算——统计分析、机器学习、量子模拟（如果我们考虑量子攻击者的话）——只要它在多项式时间内完成。计算不可区分性断言的是：所有这些尝试都只能获得可忽略的区分优势。

与语义安全的关系

加密方案的语义安全（等价于 IND-CPA）可以用计算不可区分性优雅地表述：对任意两条等长消息 m₀ 和 m₁，加密 m₀ 的密文分布与加密 m₁ 的密文分布是计算不可区分的。

{Enc(K, m₀)} ≈_c {Enc(K, m₁)}

其中 ≈_c 表示计算不可区分性。与完美保密要求两个分布完全相同不同，计算安全只要求它们在计算上不可区分——这正是计算安全比信息论安全宽松的地方。

计算假设的角色

计算不可区分性不是凭空获得的——它依赖于特定的计算困难性假设。例如，伪随机生成器（Pseudorandom Generator，PRG）将短的随机种子扩展为长的伪随机字符串，其安全性定义就是：PRG 的输出与同长度的真随机字符串是计算不可区分的。

{G(s) : s ← {0,1}ⁿ} ≈_c {r : r ← {0,1}ˡ⁽ⁿ⁾}

如果这个性质成立，那么我们可以用 PRG 将短密钥扩展为长密钥流，从而构建流密码——用短得多的密钥加密长消息，同时保持计算安全性。这正是 Shannon 定理所禁止的信息论安全版本的”近似替代品”。

统计距离与计算不可区分性

值得注意的是，两个分布之间的关系有一个强度层级：

完全相同 > 统计不可区分 > 计算不可区分

两个分布的统计距离（Statistical Distance）定义为：

Δ(X, Y) = (1/2) Σ |P(X = v) - P(Y = v)|

如果统计距离是可忽略的，则两个分布是统计不可区分的——即使拥有无限计算能力也几乎无法区分。统计不可区分性严格强于计算不可区分性。在某些密码学协议（如零知识证明）中，我们追求统计不可区分性而非仅仅是计算不可区分性，因为它提供了更强的安全保证。

七、Min-Entropy 与 Rényi 熵

Shannon 熵是”平均”意义上的信息度量。但在密码学中，我们往往更关心”最坏情况”——攻击者最好的猜测能成功的概率是多少？这引出了 Min-Entropy 和更广泛的 Rényi 熵族。

Min-Entropy：最坏情况度量

Min-Entropy（最小熵）定义为：

H_∞(X) = -log₂ max_x P(X = x)

即取概率最大的那个值的自信息。Min-Entropy 衡量的是：攻击者以最优策略（总是猜概率最大的值）进行一次猜测时的成功概率。

为什么 Min-Entropy 在密码学中比 Shannon 熵更重要？考虑以下例子：一个 128 比特的随机变量 X，它以 1/2 的概率取值 0（全零），以等概率 1/(2¹²⁸ - 1) × 1/2 取其余 2¹²⁸ - 1 个值中的每一个。

Shannon 熵计算为 H(X) ≈ 64 比特——看起来还不错。但 Min-Entropy 为 H_∞(X) = -log₂(1/2) = 1 比特——这意味着攻击者只需猜测 X = 0，就有 50% 的概率猜对！如果我们用这个 X 作为密钥，系统的实际安全性将是灾难性的。

Shannon 熵因为求取平均，掩盖了分布中的”尖峰”。而 Min-Entropy 关注的恰好是攻击者会利用的那个最弱点——这正是密码学所需要的保守度量。

Rényi 熵族

Rényi 熵（Rényi Entropy）是 Shannon 熵和 Min-Entropy 的推广。阶为 α（α > 0 且 α ≠ 1）的 Rényi 熵定义为：

H_α(X) = (1 / (1 - α)) log₂ (Σ P(x)^α)

不同的 α 值给出不同的信息度量：

• α → 1：极限为 Shannon 熵 H(X)
• α = 2：碰撞熵（Collision Entropy）H₂(X) = -log₂ Σ P(x)²

碰撞熵 H₂(X) 度量的是两个独立取样的值相同的概率。它在密码学中的一个重要应用是生日攻击（Birthday Attack）的分析：从一个碰撞熵为 H₂ 的分布中取样，大约在 2^(H₂/2) 次取样后就会出现碰撞。这就是为什么 256 比特的哈希函数只提供 128 比特的碰撞抗性。

• α → ∞：极限为 Min-Entropy H_∞(X)

对于任意分布，Rényi 熵满足：

H_∞(X) ≤ H₂(X) ≤ H(X) ≤ H₀(X) = log₂ |support(X)|

这个不等式链告诉我们，Min-Entropy 是所有 Rényi 熵中最保守的度量。

Min-Entropy 在实践中的应用

在评估随机数源的质量时，Min-Entropy 是最合适的度量。例如，NIST SP 800-90B 标准要求对熵源进行 Min-Entropy 估计，而不是 Shannon 熵估计。原因很明确：我们需要知道最坏情况下攻击者能多好地预测随机数源的输出，而不是平均情况。

Linux 内核的 /dev/random 和 /dev/urandom 接口也使用基于 Min-Entropy 的评估来决定何时有足够的熵可供使用。硬件随机数生成器（TRNG）的安全认证同样要求 Min-Entropy 达到特定阈值。

在实际的密钥派生和随机数工程中，Min-Entropy 长期处于被低估的状态。我在审阅各类密码学实现时，反复观察到同一类错误：开发者使用 Shannon 熵来评估随机源的质量，得到一个看似”足够高”的数值后便放心使用。然而正如前文的例子所示，一个 Shannon 熵为 64 比特的分布可能只有 1 比特的 Min-Entropy。这种差异在实践中绝非学术性的吹毛求疵——它直接影响密钥的可猜测性。NIST 在 SP 800-90B 中明确要求使用 Min-Entropy 而非 Shannon 熵来评估熵源，正是对这一教训的制度化回应。作为一条经验法则：任何时候你需要评估一个随机源是否适合密码学用途，都应该问”Min-Entropy 是多少”，而不是”Shannon 熵是多少”。

八、Leftover Hash Lemma 与随机性提取

在现实世界中，我们获得的随机性来源往往是不完美的——物理噪声可能存在偏差和相关性，用户密码的分布远非均匀，Diffie-Hellman 密钥交换产生的共享秘密也不是均匀随机的。如何从这些”不完美”的随机源中提取出密码学可用的均匀随机比特？这就是随机性提取（Randomness Extraction）的问题，而 Leftover Hash Lemma（剩余哈希引理）是解决这个问题的核心工具。

问题的提出

假设我们有一个 n 比特的随机变量 X，它的 Min-Entropy 为 k 比特（k < n）。这意味着 X 中”包含” k 比特的随机性，但这 k 比特的随机性分布在 n 比特之中，并非均匀分布。我们的目标是提取出一个 m 比特的字符串 R（m ≤ k），使得 R 的分布在统计上接近均匀分布 U_m。

这个问题的难点在于：我们不知道 X 的具体分布形式，只知道它的 Min-Entropy 下界。提取器需要对满足 Min-Entropy 条件的所有分布都有效。

通用哈希函数

通用哈希函数族（Universal Hash Functions）由 Carter 和 Wegman 在 1979 年提出。一族函数 H = {h : {0,1}ⁿ → {0,1}ᵐ} 是通用的（2-universal），如果对任意 x ≠ x’：

Pr[h(x) = h(x')] ≤ 1/2ᵐ

其中概率取自从 H 中均匀随机选取 h。直觉上，通用哈希函数以”最低碰撞率”将输入映射到输出——不同的输入碰撞的概率不超过完全随机映射的碰撞概率。

一个经典的构造是基于有限域运算的：选择一个大素数 p，令 h_{a,b}(x) = ((ax + b) mod p) mod 2ᵐ，其中 a, b 从 Z_p 中均匀随机选取。

Leftover Hash Lemma 的陈述与直觉

Leftover Hash Lemma（LHL）的陈述如下：令 X 是一个 Min-Entropy 至少为 k 的随机变量，H 是一族从 X 的取值域到 {0,1}ᵐ 的通用哈希函数，其中 m ≤ k - 2 log(1/ε)。那么：

Δ((H, H(X)), (H, U_m)) ≤ ε

其中 H 从函数族中均匀选取，U_m 是 m 比特的均匀分布，Δ 表示统计距离。

这个引理的含义非常深刻：只要我们愿意”损失”一些比特（大约 2 log(1/ε) 比特用于保证与均匀分布的接近程度），就可以从任何具有足够 Min-Entropy 的弱随机源中提取出近乎均匀的随机比特。提取器的构造极其简单——只需要随机选取一个通用哈希函数并应用它即可。

选取哈希函数所用的随机性（称为种子）需要是独立的均匀随机比特。种子不需要保密——它可以公开传输，因为即使攻击者知道了哈希函数的选取，他仍然无法从 H(X) 中获得关于 X 的有用信息（只要 X 的 Min-Entropy 足够高）。

随机性提取器的类型

确定性提取器（Deterministic Extractor）不需要额外的随机种子，但只能对特定结构的弱随机源工作（例如，位固定源）。对于一般的弱随机源，已经证明不可能存在确定性提取器。

种子提取器（Seeded Extractor）使用一个短的均匀随机种子来辅助提取。Leftover Hash Lemma 就是种子提取器的一个具体构造。种子的长度通常为 O(log n)，远短于输出，因此是高效的。

多源提取器（Multi-Source Extractor）从多个独立但各自不完美的弱随机源中提取均匀随机性，不需要额外的种子。

密码学中的应用

密钥派生：Diffie-Hellman 密钥交换产生的共享秘密 g^{ab} 不是均匀分布的——它是某个群中的一个元素，具有特定的代数结构。为了将其用作对称加密的密钥，需要通过随机性提取将其转化为均匀分布的比特串。HKDF（HMAC-based Key Derivation Function）就是这一思想的实际实现——它的”提取”阶段本质上是一个基于 HMAC 的随机性提取器。

量子密钥分发中的隐私放大：在量子密钥分发（QKD）协议中，Alice 和 Bob 通过量子信道建立的原始密钥可能部分泄露给了窃听者 Eve。隐私放大（Privacy Amplification）使用通用哈希函数将原始密钥压缩为更短但对 Eve 几乎均匀分布的最终密钥。Leftover Hash Lemma 是证明隐私放大安全性的关键数学工具。

从不完美随机源构建密码学原语：在嵌入式设备和物联网场景中，可用的随机源通常质量不佳。随机性提取器使得我们可以从这些不完美的随机源中安全地提取密码学可用的密钥。

以下代码展示了一个简化的通用哈希函数和随机性提取过程：

import os, hashlib

def universal_hash(data: bytes, seed: bytes, output_bits: int) -> int:
    """基于 BLAKE2 的通用哈希函数（简化实现）"""
    h = hashlib.blake2b(data, key=seed, digest_size=(output_bits + 7) // 8)
    return int.from_bytes(h.digest(), 'big') & ((1 << output_bits) - 1)

# 将 32 比特弱随机源（高 8 位固定为 0）压缩为 16 比特近均匀输出
seed = os.urandom(32)
weak = [int.from_bytes(os.urandom(4), 'big') & 0x00FFFFFF for _ in range(10000)]
extracted = [universal_hash(s.to_bytes(4, 'big'), seed, 16) for s in weak]
# 提取后分布的均匀性显著改善——通用哈希有效消除了弱随机源的偏差

Leftover Hash Lemma 是我个人认为密码学中最优美的定理之一——不是因为它的证明技巧有多高超（实际上证明相当直接），而是因为它在理论与实践之间搭建了一座几乎完美的桥梁。在理论层面，它给出了从弱随机性中提取均匀随机性的精确条件和最优界；在实践层面，它的构造极其简单——选一个通用哈希函数，应用它，就完成了。这种”深刻的简洁性”在数学中并不常见。更令人赞叹的是它的普适性：无论弱随机源的内部结构多么复杂和病态，只要 Min-Entropy 足够高，LHL 就保证提取的输出在统计上接近均匀。从 Diffie-Hellman 密钥交换后的密钥派生，到量子密钥分发中的隐私放大，再到区块链中的随机信标设计，LHL 的身影无处不在。它提醒我们：好的理论不仅解释世界，还能直接用于构建世界。

九、信息论在密码学中的现代应用

信息论不仅为密码学提供了理论基础，在现代密码学研究的前沿领域中，信息论工具仍然扮演着不可替代的角色。

窃听信道模型

Wyner 在 1975 年提出的窃听信道模型（Wiretap Channel Model）是物理层安全的理论基础。在这个模型中，发送者 Alice 通过一个噪声信道向接收者 Bob 发送消息，窃听者 Eve 通过一个更差的信道（退化信道）观察传输。Wyner 证明了一个惊人的结果：如果 Eve 的信道比 Bob 的信道质量更差，那么 Alice 和 Bob 可以在不使用任何密钥的情况下实现保密通信，并且安全性是信息论意义上的。

保密容量（Secrecy Capacity）定义为：

Cₛ = max [I(X; Y) - I(X; Z)]

其中 Y 是 Bob 的观察，Z 是 Eve 的观察。当 Cₛ > 0 时，信息论安全的通信成为可能。这一理论近年来在无线通信安全领域获得了广泛关注——无线信道的多径衰落特性天然地使得不同位置的接收者看到不同质量的信号，为物理层安全提供了实际基础。

从关联随机性中提取密钥

密钥协商（Secret Key Agreement）研究的是 Alice 和 Bob 在共享某种关联随机性（Correlated Randomness）的情况下，如何通过公开信道协商出一个共享密钥。Maurer、Ahlswede 和 Csiszár 等人的研究表明，只要 Alice 和 Bob 的随机变量之间的互信息大于 Eve 与他们任何一方之间的互信息，密钥协商就是可能的。

这个结果的深刻之处在于：即使 Eve 也观察到了与 Alice 和 Bob 相关的随机变量，只要她的观察质量较差，Alice 和 Bob 仍然可以提取出 Eve 完全不知道的密钥。量子密钥分发（QKD）的安全性证明正是基于这一信息论框架。

信息论安全的多方计算

在信息论安全的多方计算（Information-Theoretic MPC）中，多个参与方联合计算一个函数，而不泄露各自的输入。与基于计算假设的 MPC 不同，信息论安全的 MPC 即使对计算无限的攻击者也是安全的。

Ben-Or、Goldwasser 和 Wigderson 在 1988 年证明了一个里程碑式的结果：在诚实多数的假设下（即腐败参与方不超过总数的一半），任何函数都可以被信息论安全地计算。Shamir 秘密共享方案是信息论安全 MPC 的核心构件——它使得一个秘密可以被分割为 n 份，任意 t 份可以重构秘密，而少于 t 份在信息论意义上不泄露任何信息。

有界存储模型与噪声存储模型

有界存储模型（Bounded Storage Model）由 Maurer 在 1992 年提出。该模型假设攻击者的存储空间是有限的（但计算能力可以是无限的）。在这个模型下，如果公开广播的随机比特串足够长，超过了攻击者的存储容量，那么即使攻击者可以自由选择存储这些比特中的哪一部分，Alice 和 Bob 仍然可以使用这些公开随机比特来提取共享密钥。

噪声存储模型（Noisy Storage Model）进一步放宽了假设——不要求攻击者的存储容量有固定上界，只要求存储过程引入噪声（例如，量子存储不可避免地引入退相干噪声）。这个模型在量子密码学中特别有意义。

与可证明安全的联系

信息论工具在现代密码学的可证明安全（Provable Security）理论中继续发挥关键作用。许多安全性归约的分析需要用到条件熵、互信息、统计距离等信息论概念。例如：

• 模拟范式（Simulation Paradigm）中，证明一个协议安全的标准方法是构造一个”模拟器”，使得模拟器的输出与真实协议的执行在统计上（或计算上）不可区分。统计距离正是度量这种不可区分性的工具。

• 随机预言模型（Random Oracle Model）中，哈希函数被建模为一个完全随机的函数。这个模型的分析大量使用了 Shannon 熵和 Min-Entropy 的工具。

• 差分隐私（Differential Privacy）的定义和分析也借鉴了信息论的框架——它要求个体的参与对输出分布的影响不超过一个小的乘性因子，这与统计距离和互信息的概念密切相关。

在本系列后续关于可证明安全（第七部分）的文章中，我们将更深入地讨论这些信息论工具在安全性证明中的具体应用。从对称加密的 IND-CPA/IND-CCA 安全性证明，到公钥加密的归约安全性论证，信息论的语言贯穿始终。

总结

信息论是密码学的数学灵魂。Shannon 熵给了我们度量不确定性的精确工具；完美保密的定义告诉我们”绝对安全”意味着什么；Shannon 定理揭示了绝对安全的不可承受之代价；而从信息论安全到计算安全的范式转换，则开启了现代密码学的大门。Min-Entropy 和 Leftover Hash Lemma 等工具将信息论的力量延伸到了实际的密码学工程中——从密钥派生到随机性提取，从量子密码学到物理层安全。

理解信息论，就是理解密码学的根基——为什么某些事情是不可能的（Shannon 定理），为什么某些事情在合理假设下是可能的（计算安全），以及如何精确地衡量”安全”的程度（熵、统计距离、计算不可区分性）。这些概念将在后续的每一篇文章中反复出现，成为我们分析和理解各种密码学原语与协议的共同语言。

密码学百科系列 · 第 05 篇

← 上一篇：随机性 | 系列目录 | 下一篇：分组密码原理 →