Stream Cipher

2026-06-23

Uncategorized

15k words

流密码（Stream Ciphers）— 系统化课堂笔记

本笔记基于 Dan Boneh 密码学课程流密码章节的内容，按照逻辑递进关系重新组织： 基础定义 → 理想模型（OTP）→ 动机与思路（流密码诞生）→ PRG 理论（核心）→ 安全定义（语义安全）→ 实战案例。每节先给直觉，再给形式化定义，最后串联前后逻辑。

第一部分：基础概念

1.1 对称加密的定义

一个对称加密方案由以下要素构成：

三元组 (𝒦,ℳ,𝒞)：
- 𝒦：密钥空间（所有可能密钥的集合）
- ℳ：明文空间（所有可能明文的集合）
- 𝒞：密文空间（所有可能密文的集合）
二元组 (ℰ,𝒟)：
- ℰ：加密算法（通常是随机算法）
- 𝒟：解密算法（通常是确定算法）

形式化表达：

ℰ : 𝒦 × ℳ → 𝒞, 𝒟 : 𝒦 × 𝒞 → ℳ

且必须满足正确性要求——解密必须还原加密：

∀m ∈ ℳ, ∀k ∈ 𝒦: 𝒟(k, ℰ(k,m)) = m

💡 与一般密码的区别：对称加密比普通密码多一个密钥生成算法 𝒢，用于安全地生成密钥。

第二部分：理想模型 — 一次一密（One-Time Pad）

2.1 OTP 的构造

一次一密（OTP）是理论上最完美的加密方案，构造极其简单：

明文 m ∈ {0, 1}ⁿ（n 比特长的二进制串）
密钥 k ∈ {0, 1}ⁿ（与明文等长，真正均匀随机，仅使用一次）
密文 c = m ⊕ k（按位异或）

解密同样：m = c ⊕ k。

2.2 完美安全（Perfect Secrecy）的定义

直觉：攻击者拿到密文 c 后，因为密钥 k 是完全随机的，所有可能的明文 m′ 都同样可能。密文不提供任何关于明文的统计信息——它可以是任意一条消息加密后的结果。

香农（Shannon）的完美安全定义：

对于任意两条等长的明文 m₁, m₂，以及任意密文 c：

其中概率取自密钥 K 的随机分布。

等价表述：给定密文 c 后，明文的后验概率分布等于其先验概率分布——即密文不提供任何额外信息。

结论：OTP 是信息论意义上绝对安全的。即使攻击者拥有无限计算能力，也无法从密文中获取关于明文的任何信息（除了明文长度，这是所有加密方案都无法隐藏的）。

2.3 OTP 的致命局限

虽然理论完美，OTP 有四个严格约束，使其几乎无法在实际中大规模使用：

局限	说明
密钥长度 = 明文长度	加密任意长的消息需要预先共享同样长的密钥，带来巨大的密钥管理负担
密钥必须真正随机	不能使用伪随机数（如 C 语言 `rand()` 或任何 PRG），需要物理真随机源（抛硬币、量子随机数等）
密钥只能使用一次	重复使用密钥会彻底破坏安全性（见后文 Two-Time Pad 攻击）
需要安全的密钥分发渠道	密钥和明文一样长，分发密钥的代价等同于提前分发明文

💡 这些局限正是流密码诞生的动机——我们希望保留 OTP “异或随机密钥流” 的优雅结构，但用更短的密钥来实现。

2.4 常见误解澄清

“穷举密钥能破解 OTP”：❌ 错误。穷举确实能得到所有可能的明文，但攻击者无法判断哪个是正确的——所有明文等可能。安全 ≠ 无法枚举可能性，安全 = 无法获取额外信息。
“OTP 能防篡改”：❌ 错误。OTP 只提供保密性，不提供完整性或认证。攻击者可以翻转密文的某一位，导致解密后的明文对应位也翻转，且接收方无法察觉。实际系统必须结合 MAC（消息认证码）或使用认证加密。

第三部分：流密码 — 从理想走向实用

3.1 核心思想：用 PRG 模拟 OTP

流密码的诞生源于一个直接的想法：

OTP 的问题是密钥必须和消息一样长。 解决思路：用一个短的”种子”（如 128 比特），通过伪随机生成器（PRG） 扩展成长的”密钥流”，然后用这个密钥流像 OTP 一样做 XOR 加密。

flowchart LR
    subgraph OTP["OTP（理想模型）"]
        k1["真随机长密钥"] --> xor1["⊕"] --> c1["密文"]
        m1["明文"] --> xor1
    end
    subgraph SC["流密码（实用方案）"]
        seed["短种子"] --> prg["PRG"] --> ks["伪随机长密钥流"] --> xor2["⊕"] --> c2["密文"]
        m2["明文"] --> xor2
    end
    OTP -.->|"模拟"| SC

OTP 是衡量流密码安全性的理想标准
如果 PRG 的输出在计算能力有限的敌手看来与真随机序列不可区分，那么流密码本质上就是”实用的 OTP”
代价：安全从”信息论完美安全”降级为“计算安全”（仅对多项式时间攻击者安全）

3.2 流密码的公式表示

设 PRG 为 𝒢，短种子（密钥）为 k，则：

ℰ(k,m) = m ⊕ 𝒢(k)

解密同理：𝒟(k,c) = c ⊕ 𝒢(k)。

关键问题随之而来：什么样的 PRG 才算”安全”？这需要一整套理论来回答。

第四部分：PRG 深度理论

4.1 PRG 的不可预测性（Unpredictability）

直觉：一个安全的 PRG 必须是”不可预测”的——即使攻击者知道输出序列的前 i 个比特，在计算上也无法以显著高于 50% 的概率猜出第 i + 1 个比特。

如果存在高效的预测算法 → PRG 不安全
不可预测性是安全 PRG 的必要条件

4.2 可忽略函数（Negligible Function）

在深入定义”安全”之前，需要先建立一个数学工具——“可忽略”。

直觉：在密码学中，“安全”不要求攻破概率精确为零，只要求它比任何实际操作中能测量的量都小。“可忽略”就是这种”实际上的零”的数学形式化。

形式化定义：

一个函数 ε(n) 称为可忽略的（negligible），如果对于任意多项式 p(n)，都存在一个数 N，使得对所有 n > N：

换句话说：ε(n) 最终比任何多项式函数的倒数都小。

不可忽略：存在某个多项式 p(n)，使得 ε(n) ≥ 1/p(n) 对无穷多个 n 成立。

💡 为什么用多项式来定义？ 密码学中”高效”通常意味着”多项式时间（Polynomial Time）“。因此”可忽略”定义了在多项式时间攻击下的”安全边界”——如果攻击者的优势是可忽略的，方案就是安全的。

4.3 统计测试（Statistical Test）与区分优势（Advantage）

4.3.1 统计测试的定义

一个统计测试 𝒜 是一个算法：

𝒜 : {0, 1}^l → {0, 1}

𝒜(x) = 1：测试判定 x “看起来像随机串”
𝒜(x) = 0：测试判定 x “看起来不像随机串”

4.3.2 课堂示例：三个具体测试

Dan Boneh 在课上给出了三个例子，说明单一统计测试只能捕捉一类特征：

0/1 均衡性测试：0 和 1 的数量应该大致相等（接近 l/2）
二元连续对（00）计数测试：字符串内连续 “00” 的总个数应接近 l/4；过多或过少都会被判定为非随机
0 的最长游程测试：最长连续 0 块的长度应 ≤ 10 × log₂(n)；全 1 字符串无连续 0，最长游程为 0，测试会判为”随机”（这是一个误判的例子）

⚠️ 重要：单一统计测试只能捕捉一类特征，存在误判可能，无法单独作为完整区分器。

4.3.3 区分优势（Advantage）的形式化定义

设： - ：输入 PRG 伪随机串时，测试判定”随机”的概率 - ：输入真随机串时，测试判定”随机”的概率

则测试 𝒜 针对 PRG G 的区分优势为：

优势的含义：

优势值	含义
Adv ≈ 1	𝒫₀ 与 𝒫₁ 差距极大，测试能清晰分开两类分布 → PRG 被破解
Adv ≈ 0	测试面对伪随机和真随机输入表现无差别 → 该测试对 G 无效
Adv 为常数（如 1/6）	属于可攻破，说明发生器存在明显偏置漏洞

💡 优势 = 两类输入下测试阳性概率的差值绝对值。优势越大，区分能力越强。优势可忽略 = 无法区分。

4.4 安全 PRG 的完整形式化定义

PRG G : 𝒦 → {0, 1}^l 是安全的 ⇔ 对所有 PPT 统计测试 𝒜, Adv_𝒜, G^prg(λ) 是关于 λ 的可忽略函数

其中 λ = N 是安全参数（密钥长度）。

两个关键约束

只限制 PPT（概率多项式时间）统计测试：算法运行步数是输入长度的多项式，即现实计算机可实现。若去掉”有效”限制，存在指数时间暴力算法遍历所有种子，完美还原种子、100% 区分，但加入 PPT 限制后定义才具备可满足性。
要求对所有有效测试优势均可忽略：安全不能只抵抗某一种统计测试，必须抵抗全部多项式时间区分算法。

4.5 PRG 存在性与复杂度理论

⚠️ 目前无法数学严格证明任意一个现实 PRG（AES-CTR、ChaCha20 等）是安全的。仅靠多年攻击实践，未找到高效区分器，工程上信任它们。

PRG 安全与 P ≠ NP 等价关联
若存在可严格证明安全的 PRG，则可推出 P ≠ NP
若日后证明 P = NP，则不存在任何安全 PRG，所有流密码、对称密码根基崩塌
实际中：基于数论 / 分组密码构造大量实用 PRG，在工程中广泛使用

4.6 姚期智定理（Yao’s Theorem, 1982）

这是本章最重要的定理，是整个流密码安全理论的核心桥梁。

定理陈述

$是安全满足下一位不可预测$

正向（⇒）：安全 → 不可预测（若可预测，则能构造区分器，与安全定义矛盾）——此方向较直观。

反向（⇐）：不可预测 → 安全（如果不存在任何 PPT 算法能预测任意位置的下一位，那么不存在任何 PPT 统计测试可以区分 PRG 输出与真随机串）——此方向是姚期智的核心贡献。

反向证明思路：混合论证（Hybrid Argument）

直觉：如果你连下一个比特都猜不出来，那整个序列对你来说和真随机就是不可区分的。

假设存在区分器 D 能区分 PRG 输出 G(k) 和真随机串。构造一系列中间串 H₀, H₁, …, H_n：

$真随机串（个真随机比特）这就是真随机比特真随机比特真随机比特这就是$

关键观察：H_i 和 H_i + 1 的唯一区别是第 i + 1 比特的来源——前者来自真随机，后者来自 PRG。如果 D 能区分 H₀ 和 H_n，就一定能在某对相邻的 H_i 和 H_i + 1 之间表现出差别，而这恰好可以改造成一个下一位预测器——与”不可预测”矛盾。

结论：不可预测 ⇒ 安全。QED。

定理意义

把”抵抗所有复杂统计测试”这个极难验证的强条件，简化成”下一位不可预测”这一单一条件，极大降低 PRG 安全性证明的难度。

课堂例题

问题：已知某 PRG 存在漏洞——只要给出输出最后一位，就能高效算出第一位。是否说明该发生器可预测？

答：是。存在可利用的结构漏洞 ⇒ G 不安全 ⇒（由姚定理）一定存在某个位置 i，给定前 i 位可以高效预测第 i + 1 位。姚定理建立了”不可预测性”与”PRG 安全”的等价关系——只要发现任意结构性区分漏洞，就能直接判定存在下一位预测器。

4.7 计算不可区分（Computational Indistinguishability）

将 PRG 安全的思路推广到任意两个分布：

形式化定义：称两个分布 𝒫₁≈_c𝒫₂（计算上不可区分），当且仅当对所有 PPT 统计测试 𝒜：

是关于安全参数 λ 的可忽略函数。

💡 计算不可区分是密码学的通用底层概念。记号代表多项式时间内无法分辨两个分布。

4.8 脆弱的 PRG 示例

线性同余生成器（Linear Congruential Generator, LCG）

一些统计学库（如 glibc）中曾使用。公式如下：

r[i] ← (a⋅r[i−1]+b) mod p

在简单统计测试（如 0/1 个数统计）中可能表现良好
致命弱点：输出是内部状态的线性函数，只需收集少量连续输出，攻击者就能求解出参数和内部状态，预测后续所有输出

C 标准库 `rand()` / `random()`

⚠️ 永远不要使用 C 标准库中的 rand() 或 random() 等函数来生成密钥或用于任何密码学目的。

这些函数设计的初衷是统计学上的随机性，而非抗预测性。它们的输出往往具有固定的模式或周期，对精心设计的攻击是不安全的。

第五部分：流密码的安全性

5.1 攻击模型：什么算”被攻破”？

攻击者拿到密文后，即使无法做到以下两件事，系统仍然可能不安全：

✗ 无法完整还原整个共享密钥
✗ 无法完整还原全部明文

只要发生以下任一情况，系统就算被攻破： - 能恢复部分明文（哪怕只有一个比特） - 能判断明文是 0 开头还是 1 开头 - 能区分两段不同明文对应的密文

5.2 从完美安全到语义安全的逻辑演进

完美安全（OTP 基准）

对称加密方案 (K,E,D) 满足完美安全，当且仅当对任意两条等长明文 M₀, M₁，密钥均匀随机选取时：

$和$

严格同分布——不管加密 M₀ 还是 M₁，密文每种取值的概率完全一致。攻击者只看密文，完全无法判断它来自哪条明文。

但完美安全要求太高了： - 密钥长度 ≥ 明文长度，且密钥只能使用一次 - 流密码用短种子通过 PRG 生成密钥流，种子空间远小于全部可能密钥流，无法让两条明文的密文严格同分布 - 只有 OTP 达到完美安全

两步弱化——得到语义安全

第一层弱化：不要求两个密文分布完全相同，仅要求计算上不可区分（PPT 攻击者分不出）
第二层弱化：不对世界上所有明文成立，仅对攻击者主动给出的两条明文 M₀, M₁ 成立

这就是语义安全（Semantic Security）——流密码和分组密码的标准安全定义。

5.3 语义安全的双实验模型

实验流程

参与方：PPT 攻击者 𝒜、挑战者（持有随机密钥 k）：

挑战者均匀随机生成密钥
攻击者 𝒜 输出两条等长明文 M₀, M₁（由攻击者自主选择）
分支实验：
- 实验 0：挑战者返回 C₀ = E_k(M₀)
- 实验 1：挑战者返回 C₁ = E_k(M₁)
攻击者拿到密文后，输出猜测比特 b′ ∈ {0, 1}

事件与优势定义

记： - W₀：实验 0 中攻击者输出 1 的事件，Pr [W₀] 为其概率 - W₁：实验 1 中攻击者输出 1 的事件，Pr [W₁] 为其概率

攻击者 𝒜 针对加密方案 E 的语义安全优势：

优势的含义：

优势值	含义
Adv ≈ 0（可忽略）	攻击者在两个实验中行为几乎一样，无法区分加密 M₀ 和 M₁ 的密文 → 安全
Adv 为不可忽略常数	攻击者能稳定分辨两条明文 → 被攻破

语义安全的完整定义

对称加密方案 E 满足语义安全，当且仅当：

对所有 PPT 攻击者 𝒜，语义安全优势 Adv_𝒜, E^sem 是关于安全参数的可忽略函数。

即不存在任何多项式时间算法能区分攻击者选定的任意两条明文对应的密文。

课堂例题：能恢复明文最低位 → 不满足语义安全

场景：加密系统存在漏洞，攻击者拿到密文就能算出明文最后 1 比特。证明该系统不满足语义安全。

构造区分攻击者 ℬ：

主动提交两条明文 M₀, M₁，二者最低位不同（如 M₀ 末位为 0，M₁ 末位为 1）
拿到密文后调用漏洞算法算出明文末位
若末位为 0 则输出 0，末位为 1 则输出 1

计算概率： - 实验 0（加密 M₀）：末位恒为 0，攻击者永远输出 0 → Pr [W₀] = 0 - 实验 1（加密 M₁）：末位恒为 1，攻击者永远输出 1 → Pr [W₁] = 1

优势：Adv = |0−1| = 1（极大、不可忽略），系统完全被破解。

🔑 关键推论：只要攻击者能学习到明文任意单个比特、任意局部信息，加密方案一定不满足语义安全。这也是流密码安全的底线——不能泄露明文任何比特特征。

课堂例题：OTP 满足语义安全

OTP 加密规则：C = M ⊕ k，密钥 k 与明文等长、均匀随机、仅使用一次。

任取等长明文 M₀, M₁： - C₀ = M₀ ⊕ k，k 均匀随机 → C₀ 在所有等长比特串上均匀分布 - C₁ = M₁ ⊕ k，k 均匀随机 → C₁ 同样均匀分布

两个实验给攻击者的输入密文服从完全相同的均匀分布。无论攻击者是什么 PPT 算法，面对同分布输入，输出 1 的概率必然相等：

Pr [W₀] = Pr [W₁]

优势 Adv = 0，对任意攻击者优势恒为 0。因此 OTP 同时满足完美安全 + 语义安全。

完美安全 vs 语义安全对比

维度	香农完美安全	语义安全（流密码使用）
分布要求	密文分布严格相等	密文分布计算不可区分
敌手算力限制	无限制（含指数时间敌手）	仅限制 PPT 多项式时间敌手
明文范围	全体任意等长明文	仅攻击者主动选出的明文对
密钥要求	密钥长度 ≥ 明文长度，一次性	短固定密钥，可通过 PRG 扩展
适用方案	仅 OTP	安全 PRG 构造的流密码、分组密码
优势	所有敌手优势严格 = 0	PPT 敌手优势可忽略

5.4 核心定理：安全 PRG → 语义安全的流密码

定理陈述

若 G 是安全 PRG，则基于 G 的流密码 E 满足语义安全。

证明方法：归约法（逆否命题 + 反证法）

flowchart TD
    A["前提：G 是安全 PRG
（所有 PPT 区分器优势可忽略）"] --> B["要证：基于 G 的流密码是语义安全的"]
    B --> C["证明策略（反证法）"]
    C --> D["① 假设存在 PPT 攻击者 A 能攻破流密码"]
    D --> E["② 利用 A 构造出一个 PPT PRG 区分器 B"]
    E --> F["③ 证明 B 对 PRG G 拥有不可忽略的区分优势"]
    F --> G["④ 这与「G 是安全 PRG」矛盾！"]
    G --> H["⑤ 故假设不成立，流密码是语义安全的 ✓"]

证明核心技巧：两套平行游戏

引入两套完全平行的挑战者，唯一区别是密钥流来源：

	伪随机游戏（流密码世界）	真随机游戏（OTP 世界）
密钥流来源	（PRG 输出）	（纯均匀随机）
A 输出 1 的概率（实验 0）	W₀	R₀
A 输出 1 的概率（实验 1）	W₁	R₁
区分优势	Adv_𝒜, E^sem = \|W₀ − W₁\|	\|R₀ − R₁\|

5.4.1 证明的核心三角不等式推导（课堂主线逻辑）

证明目标：证明 |Pr[W₀]−Pr[W₁]| 是可忽略函数。

核心技巧：引入 OTP 真随机游戏的概率 Pr [R₀] 和 Pr [R₁] 作为”桥梁”，利用三角不等式拆分绝对值：

论断 1：真随机游戏（密钥流 = 真随机 r）等同于 OTP，由 OTP 的完美安全性：

Pr [R₀] = Pr [R₁]

因此中间项 |Pr[R₀]−Pr[R₁]| = 0，直接消失。不等式简化为：

此时的证明关键转变为：只要证明对 b = 0, 1，|Pr[W_b]−Pr[R_b]| 都等于某个 PRG 区分器的优势（而安全 PRG 保证所有区分器优势均可忽略），则两项可忽略函数相加仍可忽略 → 流密码语义安全优势也可忽略。

这就是论断 2。

5.4.2 论断 2 完整证明：构造 PRG 区分器 ℬ

第一步：区分器 ℬ 的功能定位

ℬ 是 PRG 的标准统计测试：

输入：一条长度为 l 的比特串 T（挑战者给的样本，来源未知——要么是伪随机 G(k)，要么是真随机 r）
输出：一个比特 {0, 1}
目标：区分两类样本（伪随机 vs 真随机）

第二步：ℬ 的执行步骤（归约的核心构造）

ℬ 的攻击流程如下：

flowchart TD
    T["输入：未知比特串 T
（要么是 G(k)，要么是 r）"] --> B1["① 启动流密码攻击者 A"]
    B1 --> B2["② A 输出一对等长明文 M₀, M₁"]
    B2 --> B3["③ B 拿输入串 T 当作密钥流
计算密文 C = M₀ ⊕ T"]
    B3 --> B4["④ 将密文 C 发给攻击者 A"]
    B4 --> B5["⑤ 等待 A 输出猜测比特 b'"]
    B5 --> B6["⑥ B 直接输出 b'
（即 A 的猜测结果）作为测试输出"]
    B6 --> O["输出 0 或 1"]

🔑 关键洞察：ℬ 内部嵌入 𝒜 作为子程序。ℬ 自己不知道 T 是真是假，但它观察 𝒜 的行为——如果 𝒜 能”识破”流密码，ℬ 就能利用这种能力区分 T 的来源。

第三步：计算 ℬ 的 PRG 区分优势

回顾 PRG 区分优势的定义：

下面分两种情况计算：

情况一：输入 T = G(k)（伪随机串）

此时 ℬ 内部运行的恰好是伪随机游戏（流密码）的实验 0： - 密钥流 = G(k)（PRG 输出） - 密文 = M₀ ⊕ G(k) - 𝒜 收到的是流密码加密的密文

因此 ℬ 输出 1 的概率恰好等于实验 0 中攻击者 𝒜 输出 1 的概率：

情况二：输入 T = r（真随机串）

此时 ℬ 内部运行的恰好是真随机游戏（OTP）的实验 0： - 密钥流 = r（真随机） - 密文 = M₀ ⊕ r（就是 OTP！） - 𝒜 收到的是 OTP 加密的密文

因此 ℬ 输出 1 的概率恰好等于实验 0 中攻击者 𝒜 输出 1 的概率：

代入优势定义：

第四步：构造另一个区分器 ℬ′（处理 M₁）

完全对称地，只需要把第三步中加密的明文从 M₀ 换成 M₁：

flowchart TD
    T["输入：未知比特串 T
（要么是 G(k)，要么是 r）"] --> B1["① 启动流密码攻击者 A"]
    B1 --> B2["② A 输出一对等长明文 M₀, M₁"]
    B2 --> B3["③ B' 拿输入串 T 当作密钥流
计算密文 C = M₁ ⊕ T  🔸唯一变化"]
    B3 --> B4["④ 将密文 C 发给攻击者 A"]
    B4 --> B5["⑤ 等待 A 输出猜测比特 b'"]
    B5 --> B6["⑥ B' 直接输出 b'
（即 A 的猜测结果）作为测试输出"]
    B6 --> O["输出 0 或 1"]

完全相同的推导可得：

论断 2 的结论

对 b = 0, 1，|Pr[W_b]−Pr[R_b]| 分别等于某个 PPT 区分器（ℬ 或 ℬ′）针对 G 的 PRG 优势。

因为 G 是安全 PRG，所有 PPT 区分器的优势都是可忽略函数：

|Pr[W₀]−Pr[R₀]| = negl(λ), |Pr[W₁]−Pr[R₁]| = negl(λ)

5.4.3 合并不等式，完成定理证明

将论断 2 的结果代入之前推导的三角不等式：

$（论断：中间项）（论断：每项优势）（两个可忽略函数之和仍可忽略）$

最终结论：任意 PPT 攻击者 𝒜 对流密码的语义安全优势 Adv_𝒜, E^sem 是可忽略函数。由语义安全定义，该流密码满足语义安全。证毕。 ∎

5.4.4 证明全流程可视化总结

flowchart TD
    A["流密码语义安全优势
Adv = |Pr[W₀] - Pr[W₁]|"] --> B["三角不等式拆分
≤ |W₀-R₀| + |R₀-R₁| + |W₁-R₁|"]
    B --> C{"论断 1：|R₀ - R₁| = ?"}
    C -->|"= 0（OTP 完美安全）"| D["简化：≤ |W₀-R₀| + |W₁-R₁|"]
    D --> E{"论断 2：|W₀-R₀| = ?
|W₁-R₁| = ?"}
    E -->|"= Adv_B（区分器 B 的 PRG 优势）"| F1["|W₀-R₀| = negl"]
    E -->|"= Adv_B'（区分器 B' 的 PRG 优势）"| F2["|W₁-R₁| = negl"]
    F1 --> G["安全 PRG 保证所有区分器优势可忽略"]
    F2 --> G
    G --> H["Adv_sem ≤ negl + negl = negl（可忽略）"]
    H --> I["流密码满足语义安全 ✓"]

💡 归约法的直觉：如果能攻破流密码 → 就能区分 PRG → 与 “PRG 安全” 矛盾 → 所以流密码攻不破。类比：如果能造出永动机 → 就能违反能量守恒 → 能量守恒是铁律 → 永动机不存在。

第六部分：流密码的实践陷阱

6.1 致命错误一：重复使用密钥流（Two-Time Pad）

这是最常见也最致命的错误。如果对不同消息使用相同的密钥流：

c₁ ⊕ c₂ = (m₁⊕G(k)) ⊕ (m₂⊕G(k)) = m₁ ⊕ m₂

密钥流被消掉，攻击者直接得到两条明文异或的结果。由于自然语言（如英语）或文件格式（如 PDF、ZIP）存在大量冗余信息，攻击者很容易从中分析出原始明文。

📜 历史案例：著名的”维诺那计划”（Venona Project，1941-1946）正是利用了 Two-Time Pad 这一弱点，破解了苏联的间谍通信。

正确的做法：引入 Nonce

为了解决同一长期密钥加密海量数据的问题，必须引入一个公开的、永不重复的 Nonce（Number used once）或 IV（Initialization Vector）：

ℰ(k,m;r) = m ⊕ PRG(k;r)

其中 r 是 Nonce，确保有序对 (k,r) 永不重复。底线：可以重复使用密钥，因为 Nonce 确保了唯一性。

6.2 致命错误二：IV / Nonce 太短

802.11b WEP 的经典失败案例：

WEP 协议使用 24 位 IV
在繁忙的网络中，2²⁴ ≈ 1677 万个可能值很快就会被耗尽
IV 重复 → Two-Time Pad 攻击
更糟：某些实现中 IV 在设备重启后重置为 0，极大加速密钥流重用
加上 RC4 本身的统计偏差 → 几分钟内即可破解

6.3 致命错误三：流密码的延展性（Malleability）

流密码（包括 OTP）和大多数仅提供保密性的加密方案一样，不提供完整性保护。

延展性：攻击者可以在不知道密钥和明文的情况下，通过有目的地修改密文，来精确”控制”解密后的明文内容。

攻击步骤

发起攻击：攻击者拦截密文 c，选择任意值 p，计算新密文 c′ = c ⊕ p，发送给接收方。

接收方解密：

结果：接收方最终看到的是被篡改后的明文 m′ = m ⊕ p。整个过程攻击者不需要知道密钥 k，但解密出的结果精确按照攻击者设定的模式 p 发生改变。

⚠️ 教训：流密码必须结合 MAC（消息认证码）或直接使用认证加密（AEAD），如 ChaCha20-Poly1305。

第七部分：实战案例研究

7.1 RC4 — 从辉煌到废弃

RC4 由 Ron Rivest 在 1987 年为 RSA Security 设计，以极简、极快著称，完全基于字节操作，没有复杂的数学运算。它将可变长度密钥（通常 40~256 位）扩展成密钥流，与明文逐字节异或。

RC4 的两个阶段

阶段一：密钥调度算法（KSA）——用密钥初始化 256 字节的状态数组 S：

$密钥长度为字节初始状态数组$

阶段二：伪随机生成算法（PRGA）——从状态数组 S 不断产生密钥流字节：

$状态数组密钥流字节$

RC4 的系统性弱点

KSA 的根本缺陷

弱密钥（Weak Keys）：某些密钥模式导致初始 S 数组在 KSA 后仍存在可预测结构。当密钥长度是 2 的幂时，某些密钥使 S 中很多位置的数值与索引之间存在线性关系。
关键字节的统计相关性：KSA 不是完美的打乱过程，S[1] 与密钥的第一个字节之间存在强相关性，会传递到 PRGA 的前几个输出字节。

输出字节的统计偏差（最致命弱点）

RC4 输出的概率分布不是均匀的：

偏差	发现者	详情
Z₂ = 0 双倍概率	Mantin & Shamir (2001)	第二个输出字节 Z₂ = 0 的概率 ≈ 2/256 = 1/128（真随机为 1/256），偏差 2 倍且不会消失
Z₁ 正弦分布	Mironov (2002)	第一个输出字节 Z₁ = 0 的概率低于 1/256，所有 256 个可能值呈正弦波形
更多字节偏向零	后续研究	Z₃ 到 Z₂₅₅ 及更多字节都存在不同程度的偏向 0 的偏差，且周期性重现

区分攻击与实战攻击

区分攻击：收集 RC4 前 256 字节，统计其中 0 的个数。若显著高于理想值 → 判定为 RC4。仅需几千字节即可区分，完美密码本应需要天文数字。

FMS 攻击（2001）— 攻破 WEP： - WEP 将 24 位 IV 与固定密钥拼接为 RC4 密钥：Key = IV || 固定密钥 - 攻击者构造许多”相关密钥”，利用 KSA 弱密钥 + 第一个字节的偏差 - 从统计中恢复固定密钥（40 位或 104 位） - 仅需约 400 万~600 万个数据包，几秒内即可破解

TLS 攻击（2013）：在 TLS 会话中使用 RC4 时，攻击者注入大量会话使 cookie 多次重复加密，利用输出字节偏差直接恢复加密的 cookie。这导致浏览器厂商和 IETF 正式弃用 RC4。

7.2 CSS（Content Scrambling System）— DVD 加密的失败

核心教训：一个仅基于线性反馈移位寄存器（LFSR）且密钥长度受限的密码极其脆弱。

CSS 的设计

两个 LFSR：一个 17 位（R1），一个 25 位（R2）
共同构成 40 位密钥空间
两个 LFSR 的初始状态由 40 位盘密钥（Disk Key）设定
每次两个 LFSR 生成 9 位数据（8 位有效位 + 进位），合成 1 字节密钥流
最后一步引入带进位加法（非线性元素）试图混淆

CSS 的系统性弱点

40 位短密钥：受美国当年密码出口管制所限，理论上可暴力破解
线性 + 可分离（真正的杀手锏）：LFSR 是线性组件，攻击者可利用 Berlekamp-Massey 算法，通过一小段已知密钥流重构整个 LFSR 的线性递归关系。两个 LFSR 的组合方式使其可被逐一攻破。

攻击方法（逐层剥离）

获取初始密钥流：DVD 使用 MPEG 格式，文件头有固定已知明文（如 ‘MPEG’ 等）。密文 XOR 已知明文 → 恢复最初 20 字节的 CSS 密钥流
暴力破解 R1：遍历所有 2¹⁷ ≈ 13 万种可能的 R1 初始状态，模拟 R1 生成前 20 字节输出
验证并获取 R2：将真实密钥流减去 R1 的猜测输出。若猜测正确，得到的就是 R2 的前 20 字节输出
高效验证：检验”推测的 R2 输出”是否可能由一个 25 位 LFSR 生成（使用 Berlekamp-Massey 算法）
一举两得：一旦验证成功，R1 和 R2 同时被确定 → 攻击者可生成任意后续密钥流，解密整部电影

7.3 eStream 项目与现代流密码

eStream 是欧洲密码学卓越网络（ECRYPT）在 2004—2008 年间发起的大型项目，旨在征集、评估并推荐新一代安全高效的流密码算法。它类似于流密码领域的”AES 选拔赛”，但目标更偏向探索与推荐。

两个评选方向

Profile	目标	应用场景
Profile 1（面向软件）	在通用 CPU 上达到最高加密吞吐量	服务器、桌面、移动设备
Profile 2（面向硬件）	以最低门电路数、功耗和内存实现	智能卡、嵌入式系统、IoT

⚠️ eStream 并非制定唯一强制标准。委员会明确指出这些算法在当时仍较新，可能存在未知风险。

Salsa20 — 代表性算法

Salsa20 是一个同时面向硬件和软件设计的流密码。输入 128 位或 256 位密钥，64 位随机数（Nonce），产生任意长度的输出：

Salsa20 : {0, 1}^{128 or
256} × {0, 1}⁶⁴ → {0, 1}ⁿ

核心构造：利用函数 H，输入密钥 k、随机数 r 和递增的计数器（1, 2, 3, …），通过反复调用 H 获得足够长的密钥流：

Salsa20(k;r) := H(k,(r,0)) ∥ H(k,(r,1)) ∥ H(k,(r,2)) ∥ …

函数 H 的工作过程：将状态扩充至 64 字节：

偏移	0-3	4-19	20-23	24-31	32-39	40-43	44-59	60-63
内容	Tau0	密钥 k	Tau1	随机数 r	计数器 i	Tau2	密钥 k	Tau3
字节数	4	16	4	8	8	4	16	4

其中 Tau0~Tau3 是 Salsa20 规范中给定的四个常数。

eStream 算法性能对比

类别	算法	速度 (MB/sec)
传统	RC4	126
eStream	Salsa20/12	643
eStream	Sosemanuk	727

附录：全章关键公式速查

概念	公式
对称加密定义	ℰ : 𝒦 × ℳ → 𝒞, 𝒟 : 𝒦 × 𝒞 → ℳ
OTP 加密	c = m ⊕ k（k 真随机，等长，仅用一次）
完美安全	Pr [ℰ_k(m)=c] = 1/2ⁿ，所有明文等可能
流密码加密	ℰ(k,m;r) = m ⊕ PRG(k;r)
可忽略函数	∀p(n), ∃N : ∀n > N, ε(n) < 1/p(n)
PRG 区分优势	Adv_𝒜, G^prg = \|Pr [𝒜(G(k))=1] − Pr [𝒜(r)=1]\|
姚期智定理	安全 PRG ⇔ 下一位不可预测
计算不可区分	𝒫₁≈_c𝒫₂：所有 PPT 测试优势可忽略
语义安全优势	Adv_𝒜, E^sem = \|Pr [W₀] − Pr [W₁]\|
Two-Time Pad	c₁ ⊕ c₂ = m₁ ⊕ m₂
延展性攻击	c′ = c ⊕ p ⟹ 𝒟(c′,k) = m ⊕ p

📚 复习建议：按本文顺序阅读即可——从 OTP 出发，理解为什么需要 PRG，掌握 PRG 的安全定义（不可预测 = 安全），理解语义安全实验，最后通过实战案例验证所有概念。

Categories

Tags

Archives

Recent Posts

流密码（Stream Ciphers）— 系统化课堂笔记

第一部分：基础概念

1.1 对称加密的定义

第二部分：理想模型 — 一次一密（One-Time Pad）

2.1 OTP 的构造

2.2 完美安全（Perfect Secrecy）的定义

2.3 OTP 的致命局限

2.4 常见误解澄清

第三部分：流密码 — 从理想走向实用

3.1 核心思想：用 PRG 模拟 OTP

3.2 流密码的公式表示

第四部分：PRG 深度理论

4.1 PRG 的不可预测性（Unpredictability）

4.2 可忽略函数（Negligible Function）

4.3 统计测试（Statistical Test）与区分优势（Advantage）

4.3.1 统计测试的定义

4.3.2 课堂示例：三个具体测试

4.3.3 区分优势（Advantage）的形式化定义

4.4 安全 PRG 的完整形式化定义

两个关键约束

4.5 PRG 存在性与复杂度理论

4.6 姚期智定理（Yao’s Theorem, 1982）

定理陈述

反向证明思路：混合论证（Hybrid Argument）

定理意义

课堂例题

4.7 计算不可区分（Computational Indistinguishability）

4.8 脆弱的 PRG 示例

线性同余生成器（Linear Congruential Generator, LCG）

C 标准库 rand() / random()

第五部分：流密码的安全性

5.1 攻击模型：什么算”被攻破”？

5.2 从完美安全到语义安全的逻辑演进

完美安全（OTP 基准）

两步弱化——得到语义安全

5.3 语义安全的双实验模型

实验流程

事件与优势定义

语义安全的完整定义

课堂例题：能恢复明文最低位 → 不满足语义安全

课堂例题：OTP 满足语义安全

完美安全 vs 语义安全对比

5.4 核心定理：安全 PRG → 语义安全的流密码

定理陈述

证明方法：归约法（逆否命题 + 反证法）

证明核心技巧：两套平行游戏

5.4.1 证明的核心三角不等式推导（课堂主线逻辑）

5.4.2 论断 2 完整证明：构造 PRG 区分器 ℬ

第一步：区分器 ℬ 的功能定位

第二步：ℬ 的执行步骤（归约的核心构造）

第三步：计算 ℬ 的 PRG 区分优势

第四步：构造另一个区分器 ℬ′（处理 M1）

论断 2 的结论

5.4.3 合并不等式，完成定理证明

5.4.4 证明全流程可视化总结

第六部分：流密码的实践陷阱

6.1 致命错误一：重复使用密钥流（Two-Time Pad）

正确的做法：引入 Nonce

6.2 致命错误二：IV / Nonce 太短

6.3 致命错误三：流密码的延展性（Malleability）

攻击步骤

第七部分：实战案例研究

7.1 RC4 — 从辉煌到废弃

RC4 的两个阶段

RC4 的系统性弱点

KSA 的根本缺陷

输出字节的统计偏差（最致命弱点）

区分攻击与实战攻击

7.2 CSS（Content Scrambling System）— DVD 加密的失败

CSS 的设计

CSS 的系统性弱点

攻击方法（逐层剥离）

7.3 eStream 项目与现代流密码

两个评选方向

Salsa20 — 代表性算法

eStream 算法性能对比

C 标准库 `rand()` / `random()`

第四步：构造另一个区分器 ℬ′（处理 M₁）