差分分析法学习资料

1、差分分析法解密(ji m)DES算法 苏常友第一页，共15页。 差分分析法的基本思想是通过分析明文差分对相应密文差分影响来获得可能性最大的密钥 （差分分析法的基本思想在这里听不懂不理解不要紧，后面会详细介绍）。其实目前的现状是利用差分分析法对破译16轮DES还不是很现实（主要原因是普通计算机的处理能力有限，而理论上是绝对没问题的），但用它破译轮数较低的DES是很成功的。现实中应用的DES算法为了保证足够的安全性所以比较复杂，比如经过多轮的循环以及密钥的非线性移位。我今天要讲的只是差分分析法的基本原理及主要过程，为了方便大家理解所以我选择先虚构一个简单的3轮类DES算法（主要是把信息(xnx)位

2、及密钥简化了，把循环轮数减为3轮，以及省去了IP置换，因为IP置换及其逆置换是公开的，查表就可以）。 第二页，共15页。 假设明文信息有12位并且表示为L0R0的形式（即平分为左右两部分(b fen)，分别表前6位和后6位），密钥K由9位组成，第i个加密循环的密钥Ki是由密钥K中第i个位置起的8位而得来（即密钥每次只向右移1位）。 第i个循环的输出定义如下： Li=Ri-1 和 Ri=Li-1 f（Ri-1，Ki） 算法加密过程的主要部分(b fen)就是函数f（Ri-1，Ki），它输入6位的Ri-1 和8位的Ki，产生一个6位的输出。 函数的第一个部分(b fen)是扩展器，它输入6位而输出

3、8位，如下图：第三页，共15页。 1 2 3 4 5 61 2 4 3 4 3 5 6图图1：函数的扩展：函数的扩展(kuzhn)过程过程比如(br)011001扩展成为01010101。第四页，共15页。 函数最主要的组件是S-盒，它是对用户公开(gngki)的，我们使用两个： 010 001 110 011 100 111 000001 100 110 010 000 111 101 011100 000 110 101 111 001 011 010101 011 000 111 110 010 001 100 S1S2 Si盒的输入有四位，第一位表示行：0代表第一行，1代表第二行。后三

4、位表示列的二进制数：000表示第一列，001表示第二列，以此类推。例如，S1的输入为1010，意味着输出(shch)就是S1的第二行第三列，即110。第五页，共15页。 密钥K由9位组成，第i个加密循环的密钥Ki是由密钥K中第i个位置起的8位而得来。例如，K=010011001，那么K4=01100101（经过6位以后到达K的最末，最后两位从K的前面开始得到）。 概括一下函数f（Ri-1，Ki），就是输入Ri-1由6位组成，使用扩展函数将它扩展成8位，然后与Ki异或产生另一个8位的结果，这个结果的前四位发送给S1，后四位给S2，每一个S盒输出3位，连接它们形成6位的数，进入下一轮的循环。我们可

5、以把这个过程(guchng)表示为下图：第六页，共15页。Ri-1E（Ri-1）4bits4bitsS1S2f（Ri-1，Ki）Ki图：函数(hnsh)f过程的描述举例(j l)：Ri-1及Ki已知。10011010101010011001011100 1111000 100E即假如输入是Li-1Ri-1=011100100110，并且Ki=01100101，Ri-1经过函数f后得到000100，我们将它再与Li-1异或，将得到Ri=011000，又由于Li=Ri-1，于是得到LiRi=100110011000，该结果作为(zuwi)下一轮循环的输入。第七页，共15页。 熟悉前面讲的类DES算

6、法(sun f)后，现在开始讲解差分分析法的原理。 面对一个三轮DES加密设备（S盒的内部工作过程已知），我们希望通过分析若干对明文的输入以及它们的输出而破译出密钥（明文攻击）。 我们初始设置一个明文为L1R1（用L0R0也可以，我只是习惯从1开始），经过三轮循环加密后将得到输出L4R4。根据DES算法(sun f)，有 R2=L1 f（R1,K2） L3=R2=L1 f（R1,K2） R4=L3 f（R3,K4）=L1 f（R1,K2） f（R3,K4）第八页，共15页。 假设我们(w men)再选择一个明文L*1R*1（其中R*1=R1），我们将得到它的输出L*4R*4 。对于每一个i，设

7、一个新参数Ri=Ri Ri*，Li=Li Ri*。显然Li Ri=LiRi Li*Ri*。将上一页的公式用于L*1R*1，可产生对R*4的公式： R*4=L*3 f（R*3,K4）=L*1 f（R*1，K2） f（R*3,K4）因为已经假定R*1=R1，所以f（R1，K2） = f（R*1，K2） ，因此f（R1，K2） f（R*1，K2） =0。整理R4得： R4=R4 R*4=L1 f（R*3,K4） f（R*3,K4）为了使等式的一边全部为已知量，整理得： R4 L1= f（L4,K4） f（L*4,K4）第九页，共15页。 上等式中除了K4以外所有的参数都是已知量。 现在来分析S盒的输

8、入，以此来计算f（L4,K4）和f（L*4,K4）。先从L4开始，首先扩展然后和K4异或，得到E（L4） K4，这是传送到S1和S2的位。同样的，由L*4可得出E（L*4） K4。于是可以得到： R4 L1 = f（L4,K4） f（L*4,K4） （6位） = E（L4） K4 E（L*4） K4 （8位） = E（L4） E（L*4）上面的式子全部都是已知量，因此，可知(k zh)： 1.两个S盒输入的异或（即E（L4） E（L*4）的前后 四位 ）； 2.两个输出的异或（即R4 L1 的前三位和后三位）。第十页，共15页。 现在来关注S1，对S2的分析类似。用给定的一对四位输入进行查S表

9、运算，用计算机运算这些是非常快的，再寻找哪一些得出了理想的输出异或，把它们用表格记下来。举个例子比较好说明这个问题。 例如，假设有输入的异或等于1011，正在寻找输出的异或等于100的值，我们可以运行输入对（每一对的互相异或都等于1011，总共(znggng)有16对，其实算8对，因为交换位置本质上还是本身 ）（0000，1011），（0001，1010），（0010，1001）并查找输出异或是否为100。经过一一试验（最好把这工作交给计算机）我们发现有两对输入（1010，0001），（0001，1010）对应的输出异或是100。我们可以验证一下，1010意味着S1的第二行第三列，它是110，

10、0001意味着查找S1的第一行第二列，它是010，因此输出异或是110 010=100。第十一页，共15页。 我们已知L4和L*4，例如L4=101110和L*4=000010。因此E（L4）=10111110和E（L*4）=00000010，这样输入到S1是1011 K4左四位和0000 K4左四位，如果我们知道对S1的输出异或是100，那么：（ 1011 K4左四位， 0000 K4左四位）一定是刚才计算过的列表里的一对数，即（1010，0001），（0001 ，1010），这就意味着K4左四位=0001或1010。如果重复这个过程(guchng)，肯定可以利用取交集去掉前面两个K4左四位

11、的其中一个。同理可以推出K4右四位。于是我们得到了9位密钥K的连续8位，未知的那位可以通过尝试两种可能性，并看哪一种与我们攻击的及其具有相同的加密结果，最终即可以确定9位密钥K，即达到目的。第十二页，共15页。总结一下差分分析法，可以用下面几行字概括：1.人为地选择两组明文L1R1和L*1R*1（右半部分相同）， 经过加密设备后得到两组密文L4R4和L*4R*4。2.通过两组密文L4R4和L*4R*4（也就是S盒输出异或）可 以推断出S盒的输入异或为E（L4） E（L*4）。3.利用计算机把所有的异或组合对（相互的异或值为前面 的S盒输入异或E（L4） E（L*4）进行运算，对应查 S表的结果

12、再异或，看是否等于L4R4 L*4R*4。把符合 条件的输入对用表格保存下来。4. （E（L4） K4，E（L*4） K4）在上面的表格里面， 由此可以推断K4的可能值。5.重复以上过程可完全确定K4，即确定了9位密钥K的连续 8位。未知的那位只有0或1两种可能，随便假设一种情况 即可判断到底是0还是(hi shi)1.于是9位密钥K全部破解了。第十三页，共15页。举例：初始明文L1R1=000111 011011，得到密文L4R4=000011 100101 再初始另一明文L*1R*1=101110 011011，得到密文L*4R*4=100100 011000很容易扩展L4和L*4得到E（

13、L4）=0000 0011 （8位） E（L*4）=1010 1000则可计算E（L4） E（L*4）=1010 1011 （此结果左右四位分别是S1，S2的输入异或）R4 L1=R4 R*4 L1 L*1=111101 101001=010 100（分别是S1，S2的输出异或） 接下来的工作是计算机的事：先把所有异或值为1010（先考虑S1）的一对四位二进制数列出来，总共有16对，分别是（0000，1011），（0001，1010）然后对每一对数分别查S1表得出两个三位的二进制数，将它俩异或，判断异或值是否为010，是的话就将这对四位二进制数保存在表格里面。计算机判断完以后得到了两组数（1001，0011），（0011，1001）。 由于这组数的成员可能是E（L4） K4=0000 K4=K4的左四位，所以K4的前四位只有两种可能1001或0011。同理，对一组数（1100，0111），（0111，1100）S2产生(chnshng)输出异或等于100，即这两个成员有可能是E（L4） K4=0011 K4右四位，所以K4的后四位只能是1111或0100。 另外取两组明文重复以上过程，类似地分析显示k4的前四位和后四位又是二选一，例如K4前四位取值0011或1000，后四位取值0100或1011，结合上