差分分析法

差分分析法解密DES算法苏常友差分分析法的基本思想是通过分析明文差分对相应密文差分影响来获得可能性最大的密钥（差分分析法的基本思想在这里听不懂不理解不要紧，后面会详细介绍）。其实目前的现状是利用差分分析法对破译16轮DES还不是很现实（主要原因是普通计算机的处理能力有限，而理论上是绝对没问题的），但用它破译轮数较低的DES是很成功的。现实中应用的DES算法为了保证足够的安全性所以比较复杂，比如经过多轮的循环以及密钥的非线性移位。我今天要讲的只是差分分析法的基本原理及主要过程，为了方便大家理解所以我选择先虚构一个简单的3轮类DES算法（主要是把信息位及密钥简化了，把循环轮数减为3轮，以及省去了IP置换，因为IP置换及其逆置换是公开的，查表就可以）。假设明文信息有12位并且表示为L0R0的形式（即平分为左右两部分，分别表前6位和后6位），密钥K由9位组成，第i个加密循环的密钥Ki是由密钥K中第i个位置起的8位而得来（即密钥每次只向右移1位）。第i个循环的输出定义如下：Li=Ri-1和Ri=Li-1⊕f（Ri-1，Ki）算法加密过程的主要部分就是函数f（Ri-1，Ki），它输入6位的Ri-1和8位的Ki，产生一个6位的输出。函数的第一个部分是扩展器，它输入6位而输出8位，如下图：12345612434356图1：函数的扩展过程比如011001扩展成为01010101。函数最主要的组件是S-盒，它是对用户公开的，我们使用两个：101010001110011100111000001100110010000111101011100000110101111001011010101011000111110010001100S1S2Si盒的输入有四位，第一位表示行：0代表第一行，1代表第二行。后三位表示列的二进制数：000表示第一列，001表示第二列，以此类推。例如，S1的输入为1010，意味着输出就是S1的第二行第三列，即110。密钥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位的数，进入下一轮的循环。我们可以把这个过程表示为下图：Ri-1E（Ri-1）4bits4bitsS1S2f（Ri-1，Ki）Ki⊕图：函数f过程的描述举例：Ri-1及Ki已知。100110101010100110010111001111000100E即假如输入是Li-1Ri-1=011100100110，并且Ki=01100101，Ri-1经过函数f后得到000100，我们将它再与Li-1异或，将得到Ri=011000，又由于Li=Ri-1，于是得到LiRi=100110011000，该结果作为下一轮循环的输入。熟悉前面讲的类DES算法后，现在开始讲解差分分析法的原理。面对一个三轮DES加密设备（S盒的内部工作过程已知），我们希望通过分析若干对明文的输入以及它们的输出而破译出密钥（明文攻击）。我们初始设置一个明文为L1R1（用L0R0也可以，我只是习惯从1开始），经过三轮循环加密后将得到输出L4R4。根据DES算法，有R2=L1⊕f（R1,K2）L3=R2=L1⊕f（R1,K2）R4=L3⊕f（R3,K4）=L1⊕f（R1,K2）⊕f（R3,K4）假设我们再选择一个明文L*1R*1（其中R*1=R1），我们将得到它的输出L*4R*4。对于每一个i，设一个新参数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。整理R’4得：R’4=R4⊕R*4=L’1⊕f（R*3,K4）⊕f（R*3,K4）为了使等式的一边全部为已知量，整理得：R’4⊕L’1=f（L4,K4）⊕f（L*4,K4）上等式中除了K4以外所有的参数都是已知量。现在来分析S盒的输入，以此来计算f（L4,K4）和f（L*4,K4）。先从L4开始，首先扩展然后和K4异或，得到E（L4）⊕K4，这是传送到S1和S2的位。同样的，由L*4可得出E（L*4）⊕K4。于是可以得到：R’4⊕L’1=f（L4,K4）⊕f（L*4,K4）（6位）=E（L4）⊕K4⊕E（L*4）⊕K4（8位）=E（L4）⊕E（L*4）上面的式子全部都是已知量，因此，可知：1.两个S盒输入的异或（即E（L4）⊕E（L*4）的前后四位）；2.两个输出的异或（即R’4⊕L’1的前三位和后三位）。现在来关注S1，对S2的分析类似。用给定的一对四位输入进行查S表运算，用计算机运算这些是非常快的，再寻找哪一些得出了理想的输出异或，把它们用表格记下来。举个例子比较好说明这个问题。例如，假设有输入的异或等于1011，正在寻找输出的异或等于100的值，我们可以运行输入对（每一对的互相异或都等于1011，总共有16对，其实算8对，因为交换位置本质上还是本身）（0000，1011），（0001，1010），（0010，1001）……并查找输出异或是否为100。经过一一试验（最好把这工作交给计算机）我们发现有两对输入（1010，0001），（0001，1010）对应的输出异或是100。我们可以验证一下，1010意味着S1的第二行第三列，它是110，0001意味着查找S1的第一行第二列，它是010，因此输出异或是110⊕010=100。我们已知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。如果重复这个过程，肯定可以利用取交集去掉前面两个K4左四位的其中一个。同理可以推出K4右四位。于是我们得到了9位密钥K的连续8位，未知的那位可以通过尝试两种可能性，并看哪一种与我们攻击的及其具有相同的加密结果，最终即可以确定9位密钥K，即达到目的。总结一下差分分析法，可以用下面几行字概括：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表的结果再异或，看是否等于L4R4⊕L*4R*4。把符合条件的输入对用表格保存下来。4.（E（L4）⊕K4，E（L*4）⊕K4）在上面的表格里面，由此可以推断K4的可能值。5.重复以上过程可完全确定K4，即确定了9位密钥K的连续8位。未知的那位只有0或1两种可能，随便假设一种情况即可判断到底是0还是1.于是9位密钥K全部破解了。举例：初始明文L1R1=000111011011，得到密文L4R4=000011100101再初始另一明文L*1R*1=101110011011，得到密文L*4R*4=100100011000很容易扩展L4和L*4得到E（L4）=00000011（8位）E（L*4）=10101000则可计算E（L4）⊕E（L*4）=10101011（此结果左右四位分别是S1，S2的输入异或）R’4⊕L’1=R4⊕R*4⊕L1⊕L*1=111101⊕101001=010100（分别是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产生输出异或等于100，即这两个成员有可能是E（L4）⊕K4=0011⊕K4右四位，所以K4的后四位只能是1111或0100。另外取两组明文重复以上过程，类似地分析显示k4的前四位和后四位又是二选一，例如K4前四位取值0011或1000，后四位取值0100或1011，结合上次的分析结果，我们取交集可判断K4=00110100。于是可推断K=00□001101。至于第三位，它只能取值0或1，我们先假设为0，让它加密上面的任一明文，看输出是否是对应的密文，是的话那密钥的第三位就是0，否则为1。由于自己知识及找资料的时间有限，我能讲的只能是这么多。还有就是这是我第一次做幻灯片，效果马马虎虎不是很理想，请大家见谅。谢谢大家！苏常友2008.10.27