Open Clock

密码分析的目标

密码分析的目标是：在不知道密钥的情况下，从密文（可能还有部分已知信息）中恢复明文或密钥。分析技术既用于攻击（破解密码），也用于评估算法安全性。

差分密码分析

由 Eli Biham 和 Adi Shamir 于 1990 年正式提出，是现代密码分析最重要的技术之一。

基本思想

研究输入差分如何影响输出差分：

1. 选择一对明文 P 和 P'，使得 ΔP = P ⊕ P' 满足特定模式
2. 分别加密得到 C = E(K, P) 和 C' = E(K, P')
3. 分析 ΔC = C ⊕ C' 与 ΔP 的统计关系
4. 如果某个 (ΔP, ΔC) 对出现的概率显著偏离随机期望，就可以利用这个偏差推断密钥信息

关键概念

• 差分特征（Differential Characteristic）：一轮中输入差分到输出差分的一条路径
• 差分概率：该特征出现的概率
• 差分（Differential）：多轮差分特征的组合，总概率为各轮概率的乘积

对 DES 的分析

有趣的是，DES 的 S 盒设计者似乎预先考虑到了差分分析（比公开提出早了约 15 年），S 盒的特别设计使得 DES 对差分分析有很强的抵抗能力。

线性密码分析

由 Mitsuru Matsui 于 1993 年提出。

基本思想

寻找明文比特、密文比特和密钥比特之间的线性近似关系：

P[a₁] ⊕ P[a₂] ⊕ ... ⊕ C[b₁] ⊕ C[b₂] ⊕ ... = K[c₁] ⊕ K[c₂] ⊕ ...

其中 P[a_i] 表示明文的第 a_i 比特，C[b_i] 表示密文的第 b_i 比特，K[c_i] 表示密钥的第 c_i 比特。

如果这个等式成立的概率 p 显著偏离 1/2，偏差 |p - 1/2| 越大，分析越有效。

所需数据量

约需要 |p - 1/2|^-2 个已知明文-密文对。偏差越大，所需数据越少。

对 DES 的应用

Matsui 用线性分析攻击完整 16 轮 DES 需要 2⁴³ 个已知明文对——虽然不实际，但比暴力搜索的 2⁵⁵ 更优。

积分密码分析

也称平方攻击（Square Attack），对基于字节的分组密码特别有效。

基本思想

1. 选择一组明文，其中某些字节取遍所有 256 个可能值（Active），其余字节固定（Passive）
2. 加密后追踪这些"Active"字节的和（XOR 和或模加和）
3. 在若干轮后，Active 字节的和通常为 0（平衡性质），称为积分区分器
4. 如果在某个中间状态知道一个字节的和为 0，就可以猜测最后一轮的密钥字节来验证

对 AES 的应用

积分攻击可以攻击到 4 轮或 5 轮的 AES 变体（完整 AES-128 有 10 轮）。这促使了 AES 密钥调度设计的改进。

侧信道攻击

不攻击算法的数学结构，而是利用物理实现的旁路信息：

时序攻击（Timing Attack）

测量加密操作的执行时间来推断密钥信息。如果算法中某些操作的时间依赖于密钥的值（如条件分支），攻击者可以通过统计分析恢复密钥。

防御：常数时间实现（Constant-time Implementation），消除所有与密钥相关的条件分支。

功耗分析

• 简单功耗分析（SPA）：直接观察功耗轨迹，识别出特定操作（如 RSA 中的平方和乘法）
• 差分功耗分析（DPA）：收集大量功耗轨迹，通过统计差分提取密钥比特。极其强大，已成功攻击多种智能卡。

电磁辐射攻击

测量芯片运行时的电磁辐射，原理类似功耗分析但无需物理接触。

故障攻击

故意引入硬件故障（如电压毛刺、激光照射）使加密运算出错，对比正确和错误输出来推断密钥。

总结

攻击方法	需要的信息	适用范围
差分分析	选择明文	几乎所有分组密码
线性分析	已知明文	几乎所有分组密码
积分分析	选择明文	基于字节的分组密码
侧信道攻击	物理访问	硬件实现