搞懂差分密码分析，这篇文章就够了！！

关注我！我会不定期发一些学习信安的心得体会

一、概述

差分密码分析研究首先被Eli Biham和Adi Shamir在1990年发表。其更早是由IBM在1974年提出，不过IBM将差分密码分析设为机密。差分分析方法是一种选择明文攻击，其基本思想时通过分析特定明文差分对结果密文差分的影响来获得可能性最大的密钥。它主要使用于攻击迭代密码体制。

二、流密码的线性特性

差分密码分析的基本思想是：根据比较明文与密文之间的差异，从而基于这些差异，对密钥进行合理的猜测。下面先学习一个简单的流密码加密过程，其加密运算如下：

Ci = Pi xor K

例如：

<center>密钥：0010010</center>

<center>明文：0110100</center>

<center>密文：0100110</center>

假设现在存在两个明文分组为P1，P2，使用同一个密钥K加密后的密文分组为C1，C2，则存在如下关系表达式：

C1 xor C2 = P1 xor K xor P2 xor K

化简可得到结果：

C1 xor C2 = P1 xor P2

我们通过举一个实例来理解上述关系表达式，例如我们有：

<center>明文P1：0110100 明文P2：1110011

<center> 密钥K ：0010010 密钥K ：0010010

<center>密文C1：0100110 密文C2：1100001</center>

则根据XOR运算表达关系式有：

<center>C1 XOR C2 = 1000111

<center>P1 XOR P2 = 1000111

显然，两者产生相同的结果。那么根据表达式，我们很容易得出这样的结论：如果已知两个密文流和其中一个明文流，那么就可以确定另一个明文流。例如，已知C1，C2，P1的情况下，那么，

P2 = C1 xor C2 xor P1

在实例中我们详细介绍了流密码的线性特性，即明文对与密文对的差异是相同的，使用密钥进行加密，并不会改变这个特性。但是分组密码却不是线性的，因为分组密码中的S盒是进行非线性变换，该操作可以使得明文对的差异（差分）与密文对的差异变得不同。如图一所示，这是差分分析一个有趣的性质：差分不会被异或运算所影响，但是S盒会改变差分。

三、差分分析

分组密码的非线性特性是由S盒的结构导致的，因此差分分析法就从考查S盒的特性入手。图二描述了玩具密码的过程：明文先与K0异或，然后输入到S盒中，其输出值与K1异或，然后输出密文。密码分析者如果单纯地使用穷举的方式去破解密钥，显然需要花费很多的时间（如果密钥是8bits，则需要尝试2^8次）。然而，如果猜测一个合理的输入S盒的值和输出S盒的值，那么破解K0,K1所花费的时间将大大减少。

幸运的是，S盒并不是那么完美。通过统计分析的方式可以建立输入差分与输出差分的关系。根据所找出的关系，我们可以建立差分分布表（difference distribution table, DDT）。如图三所示,
$$
横坐标是X\Delta（输入差分），纵坐标是Y\Delta（输出差分）,单元格里的值代表出现的次数。
$$
当输入差分为4，输出差分为7时，单元格的值是6，代表（4，7）出现了6次（总共为16次）。差分分布表可以帮助我们更快地破解密钥K。

例如，根据图四所示，密码分析者使用选择明文攻击的方式，选择明文对（1，5），其差分是4，由于异或不改变差分，所以S盒的输入差分也是4。密文对（0，7）的差分是7，由于异或不改变差分，所以S盒的输出差分也为7。输入差分为4，根据差分分布表，我们可以得到输入S盒的明文对存在以下几种可能：（0，4）、（1，5）、（4，0）、（5，1）、（9，13）、（13，9）。同理，我们可以得到输出S盒的密文对存在以下几种可能：（3，4）、（14，9）、（4，3）、（9，14）、（11，12）、（12、11）。根据差分分布表，运用统计的规律，针对S盒的输入输出进行合理的猜测，就可以破解密钥K。

四、toy cipher-差分密码分析视频讲解

Source Code

快速帮你搞懂差分密码分析！

五、参考

• The amazing King
• 《经典密码学与现代密码学》

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课