第4章 现代对称分组密码

现代对称分组密码张原电子信息学院[e-mail]回顾上一讲的内容古典密码代替密码单字母密码多字母密码置换密码对称密码的两个基本运算代替和置换(Substitution&permutation)对称密码分析的两个基本方法系统分析法（统计分析法）、穷举法多轮加密数据安全基于算法的保密内容提要乘积密码DES的产生与应用分组密码的设计原理与方法简化的DESFeistel密码结构对DES的描述对DES的讨论分组密码的工作模式DES密码的应用乘积密码(ProductCiphers)因为语言的特征，用代替和置换规则构造的密码是不安全的因此，可以考虑连续使用两个或两个以上的基本密码的方式来增强密码强度:两次代替可以构造一个更难于分析的代替两次置换可以构造一个更难于分析的置换代替之后在进行一次置换，可以构造一个强度更高的新密码这是古典密码通往现代密码的桥梁乘积密码(ProductCiphers)乘积密码就是以某种方式连续执行两个或多个密码以使得到的最后结果从密码编码的角度比其任何一个组成密码都强.两个加密按它们加密的顺序连接进行合成时，要求第一个方法的密文空间与第二个方法的明文空间一致。挫败基于统计分析的密码破译加密合成两类方法的合成比单个方法更具有抗非法解密的能力?这不一定都对，第二个方法可以部分或全部抵消第一个方法的作用。如果合成的方法不满足交换性，而且其中之一与另一个还独立，则这一合成是有效的。比如换位，执行一次“扩散”，多字母代替，执行一次“混乱”，不是一个群，因此可以被重复而且其组合复杂度进一步增加。等于是扩大了密钥空间。转子机（RotorMachines）在现代密码之前，转子机是最普遍的乘积密码在第二次世界大战中得到广泛应用–GermanEnigma,AlliedHagelin,JapanesePurple实现了一个非常复杂的可变的代替密码使用一系列的转子，每一个状态给定一种代替表，每加密一个字母，转子转一格，代替表就变一个3个转子可以产生263=17576代替表转子机Rotormachine置换密码换位密码把明文按行写入,按列读出密钥包含3方面信息:行宽,列高,读出顺序key:4312567plaintext:attackpostponeduntiltwoamxyzciphertext:TTNAAPTMTSUOAODWCOIXPETZ完全保留字符的统计信息使用多轮加密可提高安全性多次置多次置换，减少结构性排列，不易于重构。置换密码分析内容提要乘积密码DES的产生与应用分组密码的设计原理与方法简化的DESFeistel密码结构对DES的描述对DES的讨论分组密码的工作模式DES密码的应用DES的产生背景美国国家标准局（NBS）1973年公开征求计算机加密算法标准，要求如下：①该算法必须提供较高的安全性；②该算法必须完全确定并且易于理解；③该算法的安全性不应依赖于算法本身，而是应该依赖于密钥；④该算法必须对所有的用户有效；⑤该算法必须适用于各种应用；⑥该算法必须能够通过价格合理的电子器件得以实现；⑦该算法必须能够有效使用；⑧该算法必须能够得以验证；⑨该算法必须能够得以出口。数据加密标准（DES）HISTORY1974年8月27日,NBS开始第二次征集IBM提交了算法LucifercipherbyteamledbyFeistelused64-bitdatablockswith128-bitkey1977年正式颁布为数据加密标准（DES-DataEncryptionStandard）。1979年，美国银行协会批准使用DES。1980年，DES成为美国标准化协会(ANSI)标准。1984年，ISO开始在DES基础上制定数据加密的国际标准，称之为DEA-1。美国国家安全局NSA每五年对该算法进行评估，1994年，决定1998年12月之后不再使用DES。现已由采用Rijndael算法的高级加密标准AES取代。内容提要乘积密码DES的产生与应用分组密码的设计原理与方法简化的DESFeistel密码结构对DES的描述对DES的讨论分组密码的工作模式DES密码的应用分组密码与流密码流密码加密过程是将信息流分为基本的信息单位，然后与相应的密钥流作运算从而掩盖明文信息。分组密码与之不同的是将明文编码表示后的数字序列，划分成等长的组，在密钥的作用下变换成等长的输出序列。解密时，将加密后的分组与相同的密钥相互作用而得到明文信息。分组密码的特点分组密码与流密码的不同之处在于，分组密码输出的每一位数字不是只与相应时刻输入的明文数字有关，而是还与一组长为m的明文数字有关。在密钥相同下，分组密码对长为m的输入明文所实施的变换是等同的，所以只需研究对任一组明文数字的变换规则。分组密码易于标准化和易于实现；不善于隐藏明文的数据模式，可以离线操作，对于重放、插入、删除等攻击方式的抵御能力不强。(时间无关)mn分组密码的长度明文为分组长度为m的序列，密文为分组长度为n的序列：nm，称其为有数据扩展的分组密码；nm，称其为有数据压缩的分组密码；n=m，称其为无数据扩展与压缩的分组密码。我们一般所说的分组密码为无数据扩展与压缩的分组密码。分组密码的一般设计原理-i分组密码是将明文信息编码表示后的数字序列划分成长为m的组，各组（长为m的矢量）分别在密钥控制下变换成等长的输出数字序列（长度为n的矢量），其加密函数为，是n维矢量空间，为密钥空间。,...,...,,21ixxx),...,,(110mxxxx),...,,(110lkkkk),...,,(110nyyyynnVKVE:nVK加密算法明文),...,,(110mxxxx密钥),...,,(110lkkkk密文),...,,(110nyyyy解密算法密钥),...,,(110lkkkk密钥),...,,(110mxxxx分组密码与简单代替密码名文分组同密文分组一一映射；分组密码算法可以理解为明文分组到密文分组的代替；分组的长度n决定了代替方式的数量n=2时，有12总代替方式：(2n)！分组密码的密钥：表示采用哪种代替方式明文分组密文分组变换规则分组密码的一般设计原理-iiN=4时，共有16！=(24)!个映射方法密钥长度：表达16！需要45位分组必须足够长以抵抗穷举攻击分组密码的一般设计原理-iii一般地，对于n位的一般代替分组密码，密钥的个数为(2n)！（明文－密文的映射方法），为表示任一特定代替所需的二元数字位数为：lb(2n!)≈(n-1.44)2n=O(n2n)(bit)即密钥长度达n2n位。n=4,4×24=64n=64,64×264=270≈1021位分组长度n要足够大，防止明文穷举攻击。分组密码的一般设计原理-ivDES的密钥长度仅为56位，AES的密钥长度为128/196/256分组密码的设计问题在于找到一种算法，能在密钥的控制之下，从一个足够大而且足够好的代替子集中，简单而迅速地选取出一个代替。分组密码的一般设计原理-v分组长度足够大密钥量足够大，能抵抗密钥穷举攻击，但又不能过长，以利于密钥管理由密钥确定代替的算法要足够复杂，能抵抗各种已知攻击分组密码设计原则Shannon指出：理想的密码中，密文的统计特性独立于密钥。1949年Shannon提出了保证实际密码安全的两个基本原则：混乱（Confusion）和扩散（Diffusion）原则。混乱原则：为了避免密码分析者利用明文和密文之间的依赖关系进行破译，密码的设计应保证这种依赖关系足够复杂。需要非线性代换算法。扩散原则：为避免密码分析者对密钥逐段破译，密码的设计应保证密钥的每位数字能够影响密文中的多位数字。同时，为了避免密码分析者利用明文的统计特性，密码的设计应该保证明文的每位数字能够影响密文中的多位数字，从而隐藏明文的统计特性。ShannonandSubstitution-PermutationCiphers1949Shannon提出了代替置换网络的思想substitution-permutation(S-P)networks–modernsubstitution-transpositionproductcipher这是构成现代分组密码的基础S-P网络基于密码学的两个基本操作：–substitution(S-box)–permutation(P-box)提供了消息的扩散与混乱实现方法的设计原则软件实现的要求：使用子模块：密码运算在子模块上进行，要求子块的长度能自然地适应软件编程，如8、16、32比特等。使用简单的运算。在子块上所进行的密码运算尽量采用易于软件实现的运算。最好是用标准处理器所具有的一些基本指令，如加法、乘法、移位等。硬件实现的要求：能够采用同样的器件来实现加密和解密，以节省费用和体积。尽量采用标准的组件结构，以便能适应于在超大规模集成电路中实现。内容提要乘积密码DES的产生与应用分组密码的设计原理与方法简化的DESFeistel密码结构对DES的描述对DES的讨论分组密码的工作模式DES密码的应用简化的DESSimplifiedDES方案，简称S-DES方案。分组长度8位，密钥长度10位加密算法涉及五个函数：(1)初始置换IP(initialpermutation)(2)复合函数fk1，它是由密钥K确定的，具有置换和代替的运算。(3)转换函数SW(4)复合函数fk2(5)初始置换IP的逆置换IP-1加密算法的数学表示IP-1◦fk2◦SW◦fk1◦IP也可写为密文=IP-1fk2(SW(fk1(IP(明文)))))其中K1=P8(移位(P10(密钥K)))K2=P8(移位(移位(P10(密钥K))))解密算法的数学表示：明文=IP-1（fk1(SW(fk2(IP(密文)))))S-DES的密钥生成exampleS-DES加密操作内容提要乘积密码DES的产生与应用分组密码的设计原理与方法简化的DESFeistel密码结构对DES的描述对DES的讨论分组密码的工作模式DES密码的应用Feistel分组加密算法结构之动机分组加密算法，一一映射（加密是可逆的）当n较小时，等价于代替变换当n较大时，比如n=64，无法表达这样的任意变换。Feistel结构很好地解决了二者之间的矛盾Feistel分组加密算法结构之思想基本思想：用简单算法的乘积来近似表达大尺寸的替换变换乘积密码就是以某种方式连续执行两个或多个密码，以使得所得到的最后结果或乘积从密码编码的角度比其任意一个组成密码都更强。交替使用代替和置换(permutation)混乱(confusion)和扩散(diffusion)概念的应用Feistel密码结构Feistel结构定义加密:Li=Ri-1;Ri=Li-1⊕F(Ri-1,Ki)解密:Ri-1=LiLi-1=Ri⊕F(Ri-1,Ki)=Ri⊕F(Li,Ki)Feistel加密与解密基于Feistel结构的密码算法设计分组大小。越大安全性越高，但速度下降，64比特较合理密钥位数。越大安全性越高，但速度下降，64比特广泛使用，但现在已经不够用—〉128循环次数。越多越安全，典型16次子钥产生算法。算法越复杂，就增加密码分析的难度round轮函数。函数越复杂，就增加密码分析的难度快速软件实现，包括加密和解密算法易于分析。便于掌握算法的保密强度以及扩展办法。内容提要乘积密码DES的产生与应用分组密码的设计原理与方法简化的DESFeistel密码结构对DES的描述对DES的讨论分组密码的工作模式DES密码的应用DES的描述DES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文DES加解密过程DES示意图输