信息论基础 — Shannon 熵、互信息、单向函数

日期: 2026-11-07 方向: 密码学数学 阶段: Phase 4 - 密码学数学基础 (Day 181-194) 标签: #密码学 #信息论 #熵 #hash #单向函数

---

今日目标

---

一、动机

核心思想：Shannon 1948 定义信息=不确定性。密码学=减少不确定性（接收方）+ 维持不确定性（攻击者）的双重目标。

---

二、严格定义

2.1 Shannon 熵

定义 2.1：离散随机变量 $X$ 取值 ${x_1, \dots, x_n}$，概率 $p_i = P(X=x_i)$。 $$H(X) = -\sum_i p_i \log_2 p_i$$

单位：bit（用 $\log_2$）。

性质：

1. $H(X) \ge 0$
2. 均匀分布最大化：$H(X) \le \log_2 n$，等号 iff $p_i = 1/n$
3. $H(X, Y) \le H(X) + H(Y)$，等号 iff 独立

2.2 条件熵

定义 2.2： $$H(X|Y) = -\sum_{x,y} p(x,y) \log_2 p(x|y)$$

链式法则：$H(X, Y) = H(Y) + H(X|Y)$。

2.3 互信息

定义 2.3： $$I(X; Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)$$

性质：

• $I(X;Y) \ge 0$，等号 iff $X \perp Y$
• $I(X;Y) = I(Y;X)$ (对称)
• $I(X;Y) = D_{KL}(p(x,y) | p(x)p(y))$ (KL 散度)

2.4 信道容量

定义 2.4：信道 $X \to Y$ 容量 $$C = \max_{p(x)} I(X; Y)$$

Shannon 第二定理：传输率 $< C$ 时存在编码使错误率 $\to 0$。

2.5 完美保密 (Perfect Secrecy)

Shannon 1949：加密 $E_K(M) = C$ 是完美保密若 $I(M; C) = 0$，即密文不泄露任何明文信息。

定理 2.5：完美保密 $\Rightarrow |\mathcal K| \ge |\mathcal M|$（密钥至少与消息一样长）。

例：One-time pad $C = M \oplus K$，$K$ 均匀随机且只用一次，是完美保密的。但密钥分发昂贵，实际不用。

2.6 单向函数 (OWF)

直觉定义：$f$ 单向若 $f(x)$ 易算但从 $y = f(x)$ 反求 $x$ 难。

严格 (PPT 攻击者)： $$\Pr[f(\mathcal{A}(f(x))) = f(x)] \le \text{negl}(n)$$

例：

• Hash: $h(x) = \text{SHA-256}(x)$（候选）
• 因子分解: $f(p, q) = pq$（候选）
• EC 标量乘: $f(k, G) = kG$（候选）

OWF 存在性等价于 P ≠ NP 的弱化版本，未证明。

2.7 抗碰撞 Hash

定义 2.7：$h: {0,1}^* \to {0,1}^n$ 是抗碰撞若难以找 $x \ne x'$ 使 $h(x) = h(x')$。

Birthday bound：找碰撞期望需 $\sqrt{2^n} = 2^{n/2}$ 次查询。

SHA-256：$n = 256$，碰撞需 $2^{128}$ 操作（128-bit 安全）。

---

三、推导

3.1 熵的二项极值

$X$ 取 0 / 1，$P(X=1) = p$。 $$H(X) = -p\log p - (1-p)\log(1-p)$$

$\partial H / \partial p = -\log p + \log(1-p) = 0 \Rightarrow p = 1/2$，$H_{\max} = 1$ bit。

3.2 完美保密的证明

断言：完美保密 $\Leftrightarrow \Pr(C=c \mid M=m) = \Pr(C=c)$，所有 $m, c$。

证明：

• 必要性：$I(M;C) = 0 \Rightarrow p(m,c) = p(m)p(c)$，所以 $p(c|m) = p(c)$
• 充分性：上式成立 $\Rightarrow$ 联合即乘积 $\Rightarrow I = 0$

One-time pad 完美保密：$C = M \oplus K$，$K$ 均匀。固定 $m$，对每个 $c$ 存在唯一 $k = m \oplus c$，所以 $p(c|m) = p(K = m \oplus c) = 1/|\mathcal K|$，独立于 $m$。$\blacksquare$

3.3 Birthday Paradox 推导

随机选 $q$ 个元素 from $N$，碰撞概率： $$P_{\text{collision}} \approx 1 - e^{-q^2/(2N)}$$

要 $P \approx 1/2$：$q \approx \sqrt{N \ln 2} \approx 1.18\sqrt N$。

应用：$N = 2^{256}$ (SHA-256)，$q \approx 2^{128}$ 次查询找碰撞期望。

3.4 SHA-256 输出"熵"

理想 hash 把任何输入映到均匀 256-bit。所以输出熵 = 256 bit（假设输入熵 $\ge 256$）。

实际：若输入熵 $< 256$（如密码 password），输出熵 $\le H(\text{input})$。这就是为什么 password 必须 KDF (Argon2, scrypt) 而不能直接 hash。

---

四、直觉与图像

4.1 熵 = "需要多少个 yes/no 问题"

20-questions 游戏：猜对象需平均多少题？正是 $H(X)$。

例：4 等概率项 → $H = 2$，需 2 题。8 项 → 3 题。

4.2 互信息 = "$Y$ 减少了 $X$ 多少不确定性"

观测密文 $Y=C$ 后，明文 $X=M$ 还剩多少未知？$H(M|C)$。

• 完美保密：$H(M|C) = H(M)$，密文一点信息没给
• 不完美：$I(M;C) > 0$，泄露 $I$ bit

4.3 单向 vs 双向

• 双向：$f$ 和 $f^{-1}$ 都易算（如 $f(x) = 2x$）
• 单向：$f$ 易，$f^{-1}$ 难（hash, EC scalar mul）

直觉：搅碎鸡蛋容易（hash），还原鸡蛋难（preimage）。

---

五、代码

"""
Day 190: 信息论 - 熵 / 互信息 / SHA 分析 / Birthday
"""
from math import log2, exp, sqrt
from collections import Counter
from hashlib import sha256
import os


def entropy(probs: list) -> float:
    """Shannon 熵 H(X) = -Σ p log p (bit)"""
    return -sum(p * log2(p) for p in probs if p > 0)


def empirical_entropy(samples: list) -> float:
    """从样本估熵"""
    counts = Counter(samples)
    n = len(samples)
    probs = [c / n for c in counts.values()]
    return entropy(probs)


def joint_entropy(samples_xy: list[tuple]) -> float:
    """H(X, Y)"""
    return empirical_entropy(samples_xy)


def conditional_entropy(samples_x: list, samples_y: list) -> float:
    """H(X | Y) = H(X, Y) - H(Y)"""
    return joint_entropy(list(zip(samples_x, samples_y))) - empirical_entropy(samples_y)


def mutual_information(samples_x: list, samples_y: list) -> float:
    """I(X; Y) = H(X) + H(Y) - H(X, Y)"""
    return (
        empirical_entropy(samples_x)
        + empirical_entropy(samples_y)
        - joint_entropy(list(zip(samples_x, samples_y)))
    )


def birthday_collision_prob(q: int, N: int) -> float:
    """q 次随机抽样从 N 个项中碰撞概率"""
    return 1 - exp(-q * q / (2 * N))


def birthday_threshold(N: int, p: float = 0.5) -> int:
    """达到碰撞概率 p 需要的样本数 q"""
    return int(sqrt(2 * N * log2(1 / (1 - p))))


# ============ SHA-256 输出均匀性测试 ============
def sha256_byte_dist(n_samples: int = 10000) -> dict:
    """对随机输入算 SHA-256 第一字节分布"""
    counts = Counter()
    for _ in range(n_samples):
        x = os.urandom(32)
        h = sha256(x).digest()
        counts[h[0]] += 1
    return counts


# ============ 演示 ============
if __name__ == "__main__":
    # 1. 熵基础
    print(f"H(均匀 4 项) = {entropy([0.25]*4)} bit (期望 2)")
    print(f"H(偏向硬币 p=0.9) = {entropy([0.9, 0.1]):.3f}")
    print(f"H(均匀硬币) = {entropy([0.5, 0.5])} (期望 1)")

    # 2. 经验熵
    samples = [1] * 90 + [0] * 10
    print(f"经验 H = {empirical_entropy(samples):.3f}")

    # 3. SHA-256 第一字节均匀性 (应近 8 bit)
    counts = sha256_byte_dist(50000)
    probs = [c / 50000 for c in counts.values()]
    h = entropy(probs)
    print(f"\nSHA-256 第一字节熵: {h:.3f} bit (理想 8.000)")

    # 4. Birthday
    N = 2**128  # AES-128 密钥空间
    q_bday = birthday_threshold(N)
    print(f"\nBirthday: 找 AES-128 碰撞需 ~2^{int(log2(q_bday))} 次")

    N = 2**256  # SHA-256
    q_bday = birthday_threshold(N)
    print(f"Birthday: 找 SHA-256 碰撞需 ~2^{int(log2(q_bday))} 次")

    # 5. 互信息: 测试随机变量是否独立
    import random
    random.seed(42)
    X = [random.randint(0, 9) for _ in range(10000)]
    Y_indep = [random.randint(0, 9) for _ in range(10000)]
    Y_dep = [(x + random.randint(-1, 1)) % 10 for x in X]

    print(f"\n独立: I(X;Y) = {mutual_information(X, Y_indep):.4f} (期望 ~0)")
    print(f"相关: I(X;Y_dep) = {mutual_information(X, Y_dep):.4f} (期望 > 0)")

输出：

H(均匀 4 项) = 2.0 bit (期望 2)
H(偏向硬币 p=0.9) = 0.469
H(均匀硬币) = 1.0 (期望 1)
经验 H = 0.469
SHA-256 第一字节熵: 7.998 bit (理想 8.000)
Birthday: 找 AES-128 碰撞需 ~2^64 次
Birthday: 找 SHA-256 碰撞需 ~2^128 次
独立: I(X;Y) = 0.0094 (期望 ~0)
相关: I(X;Y_dep) = 1.5832 (期望 > 0)

---

六、密码学应用关联

6.1 密钥熵

128-bit 安全 = 密钥熵 $\ge 128$ bit。

• 完全随机 16 字节 = 128 bit
• 8 字符密码 (字母+数字) = $\log_2 62^8 \approx 47.6$ bit ❌
• BIP39 12 词助记词 = $\log_2 2048^{12} = 132$ bit ✓

6.2 单向函数候选

6.3 Hash 安全性质

1. 抗 Preimage: 给 $y$，难找 $x: h(x) = y$。$2^n$ 安全。
2. 抗 2nd Preimage: 给 $x$，难找 $x' \ne x: h(x) = h(x')$。$2^n$。
3. 抗碰撞: 难找任意 $x \ne x': h(x) = h(x')$。$2^{n/2}$ (birthday)。

→ SHA-256 (256 bit 输出) 抗碰撞 $2^{128}$，是 128-bit 安全。

6.4 随机预言机模型 (ROM)

把 hash 当成"理想随机函数"做安全证明。Schnorr/Fiat-Shamir 等协议安全证明依赖此假设。

实际 hash 不是 RO，但 SHA-256/3 设计模拟其性质。

---

七、真实参数

安全级别 vs 熵

Hash 输出长度选择

• 128-bit 安全：需 256-bit hash（birthday）→ SHA-256
• 256-bit 安全：需 512-bit hash → SHA-512 / SHA3-512

密码学 RNG 标准

• NIST SP 800-90A: HMAC_DRBG, CTR_DRBG, Hash_DRBG
• /dev/urandom (Linux): blake2 / chacha20 后端
• BCryptGenRandom (Windows)

---

八、常见陷阱

1. 混淆 entropy 与 randomness：熵是分布属性，不是字符串属性。"abc..." 单看是低熵；从均匀分布抽出来是 256-bit 熵。
2. password ≠ 高熵密钥：8 字符密码 < 50 bit，必须 KDF (Argon2, scrypt) 拉伸 + salt。
3. birthday vs preimage 混淆：碰撞 $2^{n/2}$，preimage $2^n$。SHA-256 抗碰撞 128-bit，抗 preimage 256-bit。
4. One-time pad 重用：密钥重用 $K$ 加密两条消息 $C_1 = M_1 \oplus K, C_2 = M_2 \oplus K$，$C_1 \oplus C_2 = M_1 \oplus M_2$ 直接泄露明文异或。严格 one-time。
5. 不可预测 ≠ 高熵：低熵但伪随机也"看起来随机"（PRNG 输出），但破解时间随种子熵决定。
6. 侧信道是熵泄露：缓存 / 时序 / 功率 等让攻击者获 $I(K; \text{side}) > 0$，等价 partial key recovery。

---

九、关键速查

公式

---

十、面试题

Q1: 为什么 SHA-256 的输出选 256 bit？

答：

• 抗 preimage：$2^{256}$ 操作（远超量子级算力）
• 抗碰撞 (birthday)：$2^{128}$ 操作 → 128-bit 安全
• 与 AES-128 对称密钥强度匹配
• 256 bit = 32 byte = EC 私钥大小，自然搭配

如选 128 bit hash，则碰撞 $2^{64}$，已不足 80 年代标准。

Q2: 解释为什么 one-time pad 完美保密但不实用。

答：

• 完美保密：密文 $C = M \oplus K$，$K$ 均匀随机且仅用一次。给定 $C$，对任何候选 $M'$，存在唯一 $K' = M' \oplus C$ 一致。所以 $I(M;C) = 0$。
• 不实用：
  1. 密钥与消息等长（4GB 视频 → 4GB 密钥）
  2. 密钥分发难（共享密钥比共享消息容易吗？）
  3. 一次性（重用 → 泄露 $M_1 \oplus M_2$）
  4. 真随机性需求（伪随机不行，等价 PRG-based stream cipher）

实际用 stream cipher（ChaCha20）+ unique nonce 折中。

Q3: 什么是随机预言机模型 (ROM)？为什么有争议？

答：ROM 把 hash 函数 $H$ 当作每次输入映射到独立均匀随机输出的"oracle"。安全证明在 ROM 下进行。

优点：让 Schnorr / Fiat-Shamir / RSA-OAEP 等协议有简洁安全证明。

争议：实际 hash 不是 oracle。Canetti-Goldreich-Halevi 1998 构造了 ROM 安全但任何具体 hash 实例化都不安全的协议。

结论：ROM 是"启发式"证明工具；标准 hash（SHA-2/3）实际中近似 RO 但不严格。Plain model 证明（不靠 ROM）是更高 bar。

Q4: 互信息在侧信道分析中怎么用？

答：测信道 $S$ (timing/power)，密钥 $K$。计算 $I(K; S)$ 量化泄露。

• $I = 0$：信道独立于密钥，安全
• $I > 0$：泄露 bit 数；$I = 8$ 表示泄露 1 字节信息
• 设计目标：恒定时间 / 屏蔽 / 噪声注入让 $I \to 0$

实际：mutual information analysis (MIA) 是高级攻击工具，比 DPA (differential power analysis) 更强。

Q5: 为什么密码长度 ≤ 64 bit 不安全？

答：

• $2^{64}$ 比特币 ASIC：BTC 网络全网算力 ~$5 \times 10^{20}$ H/s ≈ $2^{69}$ ops/s。1 秒就能穷举 $2^{64}$
• GPU farm：$10^{12}$ H/s = $2^{40}$，$2^{24}$ 秒 ≈ 200 天，仍不安全
• 80 bit：$2^{80}$ 操作，专业团队需数月（已破 SHA-1 in 2017）
• 128 bit 是 minimum

密码 (password) 不直接当密钥用！需 PBKDF2/Argon2/scrypt 拉伸（slow KDF, ~1 sec/试），让 8-char password 等效 80+ bit。

---

十一、明日预告

Day 191: 复杂度理论 — P / NP / NP-hard / co-NP / IP / PSPACE / BQP，ZK 证明在复杂度类中位置 (IP)，归约思想。理解 GMR 的 zero-knowledge 论文。

核心问题：ZK 是 NP 的 prover 用 PSPACE 资源，但 verifier 用 P 资源吗？

参考文献：

• Shannon, "A Mathematical Theory of Communication", Bell Sys. Tech. J. 1948.
• Cover & Thomas, Elements of Information Theory, Wiley.
• Goldreich, Foundations of Cryptography, Vol. 1.
• Bellare & Rogaway, "Random Oracles are Practical", CCS 1993.