第四讲-数据加密标准(DES)

第四讲数据加密标准(DES)1974年，IBM向国家标准局(NBS)提交了一个名为LUCIFER的加密算法。NBS将其转给了国家安全局(NSA)进行审定，之后就得到了一个名为数据加密标准DES的算法。1977年，NBS正式将其用于无限制级的政府通讯。其间NBS和NSA可能存在某些误会。NSA原本打算DES仅用于硬件执行，但是NBS却公布了过多的技术细节以致于人们可以根据其写出DES加密软件。如果NSA预料到后续的情况发展，他们或许不会同意公布DES。从1975年起，围绕DES的争论就没有停止。许多学者担心NSA无形的手对算法产生的干预。如：(1)NSA可能修改算法以安装陷门。(2)NSA将原先的128位密钥缩短到56位。(3)算法内部的运行机理始终没有得到明确解释。例如，差分分析。许多NSA设计算法的原理在90年代逐渐清晰起来，但在70年代这些的确另人迷惑。DES已经使用了三十多年，因此，2000年，国家标准与技术研究所(NIST)决定使用新的系统代替DES。但是DES仍然值得研究，它代表了一类曾经非常流行的对称加密算法。DES是分组密码，每个分组为64比特数据。64比特明文通过加密最后成为64比特密文。DES的核心是一个被称为Feistel系统的部件。本讲提要简化DES型算法差分分析DESDES不是一个群破译DES口令安全修改发现码(MDC)1简化DES型算法LiRiRi-1(6比特)Li-1(6比特)Ki(8比特)f一轮Feistel系统一轮Feistel系统(续)。。最后交换次序得到继续下去就能得到。，，，输出，则给出步输入使用相反的次序。第一但是密钥使用加密相同的过程，。解密过程。并产生密文次数这一操作会做某个固定。，，，异或表示这里，，和加密过程000011111111]][[])()(][[])(][[21XOR)(RLLRLRKLfKRfLRKLfRLLRKLRRLRLniKRfLRRLnnnnnnnnnnnnnninnnnnniiiiii一轮Feistel系统(续)函数f(Ri1，Ki)Ri1EE(Ri1)Ki4bitsS14bitsS2f(Ri1，Ki)一轮Feistel系统(续)扩张函数13243546132456S-盒10000101011011100001110101001100111110111000010001110111100001011010000100011110001111000101010121SS一轮Feistel系统(续)011000100110100110011000000100011100)(000100)(10011110001100110011110110010110101010(100110)10011001100101100111001001111121111。我们得到，。并且，接着。，因此，。得到输出送给。比特得到输出送给比特。和。也就是和假定输入是iiiiiiiiiiiiiiiRLRLKRfLRKRfSSKERKRL例子12差分分析思路：通过适当选择明文得到密文比较它们的差异以推导出使用的密钥。我们从前面的操作可以看出密钥与E(Ri1)进行异或得到结果，因此，我们可以通过再次异或移除由密钥引入的部分随机性。2.1针对三轮的差分分析参数。以外的除密钥通过输入输出知道所有在最后这个式子中我们。，，我们得到，，由于。重新安排一下得到。因此，。，定义。且假定另一条消息。，，，，我们有。应该得到相应不同的输入消息为起点进行分析。使用而不是我们先以44*44414*4*3434*343144*3431*444***11*1*14321143343211244110011)()(),(),(),(),()()()()(KKLfKLfLRLRLRKRfKRfLRKRfKRfLRRRLLLRRRRRRLKRfKRfLKRfLRLKRfLRRLRLRLRLiiiiii2.1针对三轮的差分分析(续)。比特比特和后的前也就是盒输出的异或两个输出是两个异或；为这是因，比特比特和后的前就是扩张函数也盒的输入两个操作可以延伸入异或知道的分析，我们，和，通过对函数)33(XOR-SXOR(2))()()()()44)((-SXOR(1))()(144*44*4444*444LRLELLELELELEKLfKLf2.1针对三轮的差分分析(续)。下一个密钥重复以上过程直到只剩。推导可能的密钥是否在列表上。，对。和输出列表查看输入列表总结攻击过程如下：444*444144(4)(3)))()(((2)XOR)(XOR(1)KKKLEKLELRLE2.1针对三轮的差分分析(续)。密钥就是。的可以产生正确仅有。中。因此，，在比特的密钥后中，，在比特的密钥前。我们发现和现在重复中。，在比特的密钥以推出后使用同样的方法我们可中。，在比特的密钥前因此，。输出等于异或，，和，。对于对的输出是，的输出是这意味着。和此，。因可以得到我们选择如果。我们得到比特开始。并从其的第特比轮加密只使用其中的在第密钥。假定我们不知道密钥。和密钥我们开始于001001101001001101001101?001011}{41000}{4111011100110110101110110}{11114}{10014010XOR1001)(00110011)(100100101001010010101011)()()(00100100011011101110011001000011100180010011011100011101104444*1*111442114*444*4*4*1*14411KRLKKKKRLRLKKSSLRLELELERLRLRLiiKKKRLi0100001101000011例子22.2针对四轮的差分分析四轮差分分析是建立在三轮基础之上的，但是要扩展到四轮还需要使用一些统计方面的知识。这里我们关注S-盒的一些弱点。2.2针对四轮的差分分析(续)。也就是，。这样满足和。现在我们假定选择的概率为输出等于们可以得到盒的输出相互独立，我两个。如果我们假定这通过扩展函数得到。满足和假定我们开始随机选择。输出等于个的异或的对中，存在等于或个输入的异盒中。在。类似的缺陷也存在于等于输出都个异或的对，我们发现等于异或个输入的我们关注盒存在一个缺陷。如果在0000000110100110103/816)(12/16)(8/011010XOR-S00111100)001100(001100010XOR81100XOR16011XOR120011XOR16*1101*000*00*000*0021RRLRLLLLLERRRRRSS事实12.2针对四轮的差分分析(续)高出很多。密钥次数将比其它不正确的在密钥的列表中出现的钥出现，因此，正确的密可能不正确的密钥频繁。由于没有出可能的密钥使用三轮差分分析推导接着。。假定，察输出观。等于随机选择输入对的异或分析策略：000011000000000110100011XOR4411*4*444KKRLRLRL2.2针对四轮的差分分析(续)。我们就能得出正确密钥加密消息。使用两种可能的密钥因此，密钥频率位后频率位后频率位前频率位前下表。的密钥频率列于。我们可以将每种可能和百个随机输入对假定我们已经实验了几110000?10171111110111391111601116111080110281110401102311011001013211013010181100270100401001810111000113510111500118101035101080010161001600014010017000181000140000331000120000444400011010001100*0*000KRLRLRL591100420010例子32.3关于差分分析(1)我们注意到前面的例子表明差分攻击至少和强力攻击有相同的速度。然而，对于更优异的系统如DES，在一定的轮数下，差分攻击的效率将明显快于搜索全部密钥空间的强力攻击。(2)MitsuruMatsui发明了另一种名为线性攻击的分析方法。这一攻击使用线性估计来描述分组密码的行为。线性分析可以看作是一种效率改进的新型差分分析(理论上需要大约243明-密文对)。但是并没有证据显示其可以有效的在实际中攻击DES。3DESDES的密钥通常写为64比特，但每8比特有一位奇偶效验位，可以忽略，因此，实际只有56比特。算法只使用不超过64位的标准算术操作和逻辑操作，所以在70年代仅使用硬件就可以容易地实现算法。算法的重复特性非常适合专用芯片执行。起初采用软件执行的DES显得笨拙，但目前的软件执行效果也相当不错。3.1DES算法描述DES)3()((3)48)(161(2)3232)((1)DES161611616111000000特串的次序。调换前后比算法一样在解密过程中步意味着无需像简化相反的次序。第的过程，除了密钥使用加密过程使用完全相同。初始计算的逆得到密文接着使用，调换前后次序得到要定义的函数。是一个在后面将比特的串，产生的一个是从密钥这里，，进行如下操作：，对于比特。是后比特是前，这里写为，初始计算得到的比特串通过一个固定消息组成：算法的加密由三个阶段LRIPcLRfKKKRfLRRLiRLRLmmIPmmiiiiiii3.1DES算法描述(续)明文IPL0R0fK1L1R1L16R16密文IP13.2初始计算入芯片而提出的。为了使算法更有效的载年代意义，它可能只是在初始计算没有任何密码初始计算70715233139475563513212937455361311192735435159191725334149578162432404856646142230384654624122028364452602101826344250583.3函数f(Ri1，Ki)Ri1扩张E(Ri1)KiB1B2B3B4B5B6B7B8S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8计算f(Ri-1,Ki)3.3函数f(Ri1，Ki)(续)。，，，比特输出到每个盒的决定。通过这种方法得列由由盒的行的输入。盒做为为写比特。为，这里每个并将其写成计算扩展计算。比特使用如下表扩展为比特按如下描述运行：函数82154326162182111114--.(3)6)()2(1323130292829282726252425242322212021201918171617161514131213121110989876545432132)(48)()(32(1)),CCCbbbbbbSSSBbbbBBBBBKRERERKf(Rjjjjiiiiii3.3函数f(Ri1，Ki)(续)91450127611241531108131523961285113410117140511961010121482157413310501213279431161481152-S13601014311571942812150510379121511261381414835911126101132144715070951261038111521134141-S-S盒盒盒14271211549813110601534825143115137111209610914101122743015651181315412115821109603141374-S122511314154789601310171410512211103158946131151112145821064390713824117121315153614901