差分密码分析

差分密码分析旨在破解基于轮的块密码和密码哈希函数。 为此，她研究了明文块的差异对加密生成的密文块的差异的影响。

该过程的核心是分析明文对的差异对所得密文对差异的影响。

使用 XOR 运算逐位形成差异。 如果 P 和 P ∗  是两个明文，那么它们的差就是 P ′ = P ⊕ P ∗ =P\oplus P^ { \分支 }} 。 通过各个加密步骤可以观察到这种差异。 仅包含 XOR 链接的步骤不会更改差异。 排列和扩展，因为它们出现在大多数 Feistel 密码中，也可以通过交换或复制排列和扩展提供的差异位来轻松计算。 只是不可能计算非线性替换框之间的差异。

为了更详细地检查替换框（S-box）中差异的行为，给出不同的输入值 S X I  和 S X I ∗ 具有相同的输入差异到 S-Box X ，即 S X I ′ = c o n s t 。 然后可以看出 S X O ′ 值 S X O 和 S X O ∗在输出端分布不均。 这意味着在输入差异恒定的情况下，一些输出差异会更频繁地出现，而另一些则不会出现或根本不会出现。 S-Box 的这个属性记录在一个差异分布表中：

值 x i , j 表示当用S-Box X 。 输入差异 S X I j ′ 然后导致输出差异 S X O i ′ 概率

p D = x i , j 2 l 通过检查的 S-Box X 与输入 l  位宽。

对于一轮 Feistel 密码，可以使用此知识排除某些密钥。 其余键是关键候选者。 右图以DES为例，使下面使用的标识有些清晰关于。

攻击者有两个用自选差异加密的明文。 他了解密文或至少了解它们之间的区别。 根据明文的知识，他可以计算出加密 S X E 在与轮密钥 K 进行异或运算之前的状态。 从密文差异，他可以计算出 S-Box X  的初始差异 S X O ′ 。 使用差异分布表，可见S-盒可能输入值的个数。 输入值对 S X I 和 S X I ∗  ，差值 S X I ′ ，这是输出差异 S X O ′ 必须由攻击者计算或从表中读取。 假设攻击者知道 S-box 的计算规则（Kerckhoffs 原理）。

这可以用不同的明文对重复。 正确的轮密钥总是在运行的关键候选者中。 因此，不包括在所有运行的关键候选者中的密钥作为轮密钥被消除。

每个特征 Ω 可以被分配一个概率 p Ω 具有给定差异 Ω P 的随机明文对恰好是那些这些特征假设在各个回合中存在差异。 n 轮特征 p Ω的概率是所有 1 轮特征 p i Ω 的概率的乘积n 轮特征 Ω。

p Ω = ∞ i = 1 n p i Ω

1轮特征的概率为 p D ，即该特征的输入差异导致该特征输出差异的概率。

一个特例是所谓的迭代特征，其中 Ω 1 = Ω 2 ，它总是可以附加到它们自身。 因此，明文差异的交换一半等于相同特征的密文差异。 因此，这些可以很容易地与任何大小的 n 轮特征相关联。 而在非迭代特征的情况下，概率随着 n 的增加而越来越快地下降，由于雪崩效应，构成迭代特征的部分特征的概率保持不变。 因此，在攻击中优选使用迭代特征。