1. 敌手能力
评估一个密码体制的安全性，首先要界定敌手拥有的资源及获取信息的方式。根据敌手对密码系统的介入程度，攻击能力由弱到强通常分为以下几类：
唯密文攻击 (COA - Ciphertext-Only Attack)
- 定义：敌手仅能获取若干段密文 \(C_1, C_2, \dots, C_n\)，且已知这些密文是用同一密钥 \(K\) 加密的。
- 目标：推导出明文 \(M\) 或密钥 \(K\)。
- 分析：这是敌手能力的最低门槛。如果一个连 COA 都无法抵御的算法（如简单凯撒密码），被视为完全不安全。现代密码设计时，通常假设敌手至少拥有 COA 能力。
已知明文攻击 (KPA - Known-Plaintext Attack)
- 定义：敌手除拥有密文外，还掌握了部分与这些密文对应的明文对 \((M_1, C_1), (M_2, C_2), \dots\)
- 来源：明文可能具有标准格式（如邮件头 "To:"），或者是通过其他渠道泄露的旧数据。
- 分析：敌手利用已知的明密对，分析密钥 \(K\) 与密文 \(C\) 之间的映射关系。许多历史算法在 KPA 下表现不佳，如线性分析法针对 DES。
选择明文攻击 (CPA - Chosen-Plaintext Attack)
- 定义：敌手可以临时访问加密机（Oracle），能够任意选择明文 \(M\) 并获得对应的密文 \(C = Enc(K, M)\)。
- 场景：这是公钥密码体制的标准威胁模型，因为加密密钥是公开的，任何人都可以加密。在对称密码中，这模拟了敌手作为系统内部用户或发送者的情况。
- 核心要求：安全的对称加密必须具备 CPA 安全性，密文必须是不可区分的。
选择密文攻击 (CCA - Chosen-Ciphertext Attack)
- 定义：敌手能力最强，不仅能选择明文加密（CPA），还能选择密文进行解密（访问解密 Oracle），获得对应的明文 \(M = Dec(K, C)\)。唯一的限制通常是不能直接提交挑战密文进行解密。
- 场景：模拟了敌手诱导接收者解密任意密文，如通过协议漏洞、中间人攻击的情况。
- 分析：CCA 是许多互联网安全协议，如 TLS、SSL，要求的安全级别。能够抵抗 CCA 的体制通常具备非延展性。
1.5 选择文本攻击 (CTA - Chosen-Text Attack)
- 定义：泛指敌手既能选择明文又能选择密文的能力
- 注：在加密体制讨论中，通常被 CCA 所涵盖；在签名体制中，指敌手请求对特定消息的签名。
2. 安全性定义
无条件安全
- 定义：无论敌手拥有多少计算资源（时间、空间、算力），都无法破译密码体制。
- 理论基础：信息论。
- 典型案例：一次一密(One-Time Pad)。
- 香农证明，若要达到无条件安全，密钥长度必须大于等于明文长度，且密钥只能使用一次。这使其在大多数大规模应用中不切实际。
计算安全
- 定义：在有限的计算资源下，敌手破译密码体制的概率是可忽略的。
- 核心逻辑：基于计算复杂性理论。攻击算法的时间复杂度必须是超多项式的（如 \(2^{128}\) 或 \(2^{256}\)）。
- 实际应用：现代所有商用密码的安全性均属于计算安全。这意味着理论上可以通过穷举破译，但现有计算力条件下不具备可行性。
3. 攻击方法
通用攻击：给出算法上界
在讨论攻击效率时，我们关注攻击算法的时间复杂度和空间复杂度。最基础的上界由穷举搜索给出。
穷举搜索
- 原理：遍历密钥空间 \(\mathcal{K}\) 中的每一个可能的密钥 \(K_i\)，尝试解密密文，直到解密结果符合明文的语言特征（如具有可读性、校验和正确）。
- 复杂度上界：
- 时间复杂度：\(O(|\mathcal{K}|)\)，即密钥空间的大小。对于 \(k\) 位密钥，需要 \(2^k\) 次运算。
- 空间复杂度：\(O(1)\)（仅需存储当前尝试的密钥和中间结果）。
- 结论：如果一个密码体制的最佳攻击算法复杂度接近穷举搜索，我们通常认为该算法的设计是成功的，其安全性仅依赖于密钥长度。
穷举攻击示例
分组长度64bit，密钥长度80bit
\(P\{E_k(m)=c\}=\frac{1}{2^{64}}\)
穷举全部密钥，得到\(2^{16}\)个候选密钥
需要再获取一个明密文对才能成功破解
其他
查表攻击
字典攻击
时间-存储折中攻击
基于设计细节的攻击
差分分析、线性分析、积分分析等
侧信道攻击
收集泄漏的物理信息推测密钥
4. 序列密码攻击思想
针对序列密码的攻击主要聚焦于密钥流生成器（KSG）的弱点。
区分
这是现代流密码分析中最核心的概念，通常对应于判决攻击。
- 基本思想：
将密钥流生成器视为一个伪随机数生成器 (PRNG)。- 假设 H0：输出序列 \(S\) 是由真随机生成器产生的（均匀分布）
- 假设 H1：输出序列 \(S\) 是由特定密钥流生成器产生的。
- 攻击方式：
敌手寻找输出序列中的统计偏差或线性相关性。如果能找到一个算法 \(D\)，使得 \(D(S)\) 判决为“生成器输出”的概率显著高于 1/2，则称该生成器被区分。 - 后果：
一旦敌手能区分密钥流和随机流，通常意味着可以利用这种偏差进一步恢复内部状态或密钥。线性攻击就是典型的区分攻击。
分割
亦称分治法
- 基本思想：
密钥流生成器的内部状态通常由多个部分组成（例如 LFSR 的抽头、非线性函数的输入）。直接穷举整个内部状态空间太大。 - 攻击方式：
- 将内部状态猜测问题分解为若干个子问题（例如先猜测 LFSR1 的状态，再猜测 LFSR2）。
- 利用非线性函数输出（密钥流）对各个子部分的状态进行局部验证或筛选。
- 排除掉错误的子状态猜测，显著减少需要进行最终验证的状态组合数量。
- 核心逻辑：
利用代数结构，将指数级复杂度 \(O(2^{(n_1+n_2)})\) 降低为亚指数级或低阶多项式级 \(O(2^{n_1} + 2^{n_2})\)。这是针对基于 LFSR 的流密码（如 Geffe 发生器）最有效的攻击手段之一。