第4章 现代对称分组密码

1、现代对称分组密码,张原电子信息学院,回顾上一讲的内容,古典密码代替密码单字母密码多字母密码置换密码对称密码的两个基本运算代替和置换(SubstitutionRi=Li-1F(Ri-1,Ki)解密:Ri-1=LiLi-1=RiF(Ri-1,Ki)=RiF(Li,Ki),Feistel加密与解密,基于Feistel结构的密码算法设计,分组大小。越大安全性越高，但速度下降，64比特较合理密钥位数。越大安全性越高，但速度下降，64比特广泛使用，但现在已经不够用128循环次数。越多越安全，典型16次子钥产生算法。算法越复杂，就增加密码分析的难度round轮函数。函数越复杂，就增加密码分析的难度快速软件实

2、现，包括加密和解密算法易于分析。便于掌握算法的保密强度以及扩展办法。,内容提要,乘积密码DES的产生与应用分组密码的设计原理与方法简化的DESFeistel密码结构对DES的描述对DES的讨论分组密码的工作模式DES密码的应用,DES的描述,DES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文,DES加解密过程,DES示意图,输入的明文首先经过一个初始置换IP，将明文分为左半部分和右半部分，各长32位。然后进行16轮完全相同的运算，即图中的f函数。在这些函数中，数据与密钥结合起来从而隐藏了密文，最后左、右半部分合在一起经过一个末置换IP-1（初始置换的逆置换），就完

3、成了密文的生成。,初始置换IP和IP-1,同S-DES（简化的DES）相同，DES在算法的开始和结束部分增加了两个置换操作。目的增加算法的抗分析能力。,输入（64位）,58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157,输出（64位）,初始变换IP,L0（32位）,R0（32位）,置换码组输入（64位）,40848165624643239747155523633138646145422623037545135

4、321612936444125220602835343115119592734242105018582633141949175725,输出（64位）,逆初始变换IP-1,初始置换IP和IP-1(互逆),M20M14,M14M20,一轮DES,左32位,右32位,Li-1,Ri-1,48位(明文),64位密钥,作第i次迭代的计算机子密钥Ki,密钥程序表,48位(密钥),8组6位码,模2加,选择函数输入：6位输出：4位,+,32位,置换,32位,32位,Li,Ri,左32位,右32位,Ri-1,Li-1,模2加,+.+,乘积变换中的一次迭代,DES:FunctionF,扩展置换的作用,它产生了与密

5、钥同长度的数据进行异或运算它产生了更长的结果，使得在代替运算时能进行压缩(增加复杂性)输入的一位将影响两个替换（例如第一位输入，存在于第一个和第8个子分组中，每个子分组分别进行S盒替换），所以输出对输入的依赖性将传播得更快，明文或密钥的一点小的变动应该使密文发生一个大的变化.这叫雪崩效应。（avalancheeffect）,S-Box,对每个盒，6比特输入中的第1和第6比特组成的二进制数确定的行，中间4位二进制数用来确定16列中的相应列，行、列交叉处的十进制数转换为二进制数后，4位二进制数表示作为输出。,S-盒的构造（S6）,P-盒置换,1607202129122817011523260518

6、311002082414322703091913300622110425,5749413325179158504234261810259514335271911360524436,6355473931331576254463830221466153453729211352820124,置换选择1,密钥（64位）,C0(28位),D0(28位),DES的解密过程,采用与加密相同的算法。以逆序（即）使用密钥。第一圈用第16个子密钥K16，第二圈用K15，其余类推。,不同微处理器上的DES软件实现速度,采样专业硬件速度可达千万分组/S,内容提要,乘积密码DES的产生与应用分组密码的设计原理与方法简化

7、的DESFeistel密码结构对DES的描述对DES的讨论分组密码的工作模式DES密码的应用,对DES的讨论,弱密钥与半弱密钥互补密钥DES的破译密钥长度的争论DES的轮数函数FS-盒的疑问,弱密钥,初始密钥被分成两部分，每部分都单独做移位。如果每一部分的每一位都是0或都是1，则每一圈的子密钥都相同。这样的密钥被称为弱密钥。弱密钥的定义：若k使得加密函数与解密函数一致，则称k为弱密钥。EK(EK(p)=pDES存在4个弱密钥,半弱密钥,有些成对的密钥会将明文加密成相同的密文，即一对密钥中的一个能用来解密由另一个密钥加密的消息，这种密钥称作半弱密钥。这些密钥不是产生16个不同的子密钥，而是产生两

8、种不同的子密钥。半弱密钥：对于密钥k，存在一个不同的密钥，满足。至少有12个半弱密钥。,对DES的讨论,弱密钥与半弱密钥互补密钥DES的破译密钥长度的争论DES的轮数函数FS-盒的疑问,互补密钥,将密钥的0换成1，1换成0，就得到该密钥的补密钥。如果用原密钥加密一组明文，则用补密钥可以将明文的补码加密成密文的补码。DES算法具有互补性，即：若、是的补、是的补，则。,证明-i,对于一位的A和B有下的真值表，因此，对于任何等长的A和B，有(AB)=AB,AB=AB,证明-ii,如果明文和密钥取补(A、B、K)，相当于第一个XOR的输入也取补，这样输出和没有取补时一样F(B,K)，进一步我们看到对于

9、第二个XOR的输入只有一个取补了，因此输出AF(B,K)（AF(B,K)(AB)=AB,AB=AB,互补密钥对穷举式攻击的影响,在一个选择明文攻击中，如果选择明文X,攻击者可以得到Y1=EKX和Y2=EKX,那么穷举式攻击只需要进行255次加密，而不是256次.注意到(Y2)=EKX，现在选取一个测试密钥T,计算ETX.如果结果是Y1,T是正确的密钥.如果结果是(Y2),T是正确的密钥.如果都不是，我们就通过一次加密否定了两个基本密钥。,对DES的讨论,弱密钥与半弱密钥互补密钥DES的破译密钥长度的争论DES的轮数函数FS-盒的疑问,DES的破译：分组密码的分析方法,根据攻击者所掌握的信息，可

10、将分组密码的攻击分为以下几类：唯密文攻击已知明文攻击选择明文攻击攻击的复杂度数据复杂度:实施该攻击所需输入的数据量处理复杂度:处理这些数据所需要的计算量,分组密码的典型攻击方法,最可靠的攻击办法：强力攻击差分密码分析：通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特。选择明文攻击，需要247个选择明文线性密码分析：本质上是一种已知明文攻击方法，通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统，需要247个已知明文插值攻击方法密钥相关攻击,强力攻击,穷尽密钥搜索攻击:唯密文：用2k个密钥对密文解密，看明文是否有意义已知(选择)明文：用2k个密钥对明文加密,看明密文是否相同字

11、典攻击：明密文对编成字典,得到密文后在字典中查找对应的明文，需2n个明文-密文对。查表攻击：是选择明文攻击,给定明文,用所有的2k个密钥,预计算密文,构成密文密钥表，得到密文后在表中查找对应的密钥。（某些协议中会出现固定的短语）,DES的破译,1990年，以色列密码学家EliBiham和AdiShamir提出了差分密码分析法，可对DES进行选择明文攻击。IBM声称1974年就知道该方法，因此在S盒和P盒的设计中做了考虑，差分方法对8轮DES需214个选择明文，对其他分组密码算法更有效。线性密码分析比差分密码分析更有效强力攻击：平均255次尝试差分密码分析法：使用247对明密文的选择明文攻击线性

12、密码分析法：使用247对明密文的已知明文攻击,对DES的讨论,弱密钥与半弱密钥互补密钥DES的破译密钥长度的争论DES的轮数函数FS-盒的疑问,密钥长度,关于DES算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有2561017个早在1977年，Diffie和Hellman已建议制造一个每微秒能测试100万个密钥的VLSI芯片。每微秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元。Hellman提出通过空间和时间的折衷，可以加速密钥的寻找过程。他建议计算并存储256种用每种可能密钥加密一段固定明

13、文的结果。估计机器造价500万美元。,密钥长度,1997年1月28日，美国的RSA数据安全公司在RSA安全年会上公布了一项“秘密密钥挑战”竞赛，其中包括悬赏1万美元破译密钥长度为56比特的DES。美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的1万美元。1998年7月电子前沿基金会（ElectronicFrontierFoundation）使用一台25万美元的电脑在56小时内破译了56比特密钥的DES。1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了

14、一个DES的密钥。,对DES的讨论,弱密钥与半弱密钥互补密钥DES的破译密钥长度的争论DES的轮数函数FS-盒的疑问,DES的轮数,Feistel密码的编码强度来自于：迭代轮数、函数F和密钥使用的算法。一般来说，循环次数越多进行密码分析的难度就越大。一般来说，循环次数的选择准则是要使已知的密码分析的工作量大于简单的穷举式密钥搜索的工作量。对于16个循环的DES来说，差分密码分析的运算次数为255.1，而穷举式搜索要求255，前者比后者效率稍低，如果DES有15次循环，那么差分密码分析比穷举式搜索的工作量要小。,对DES的讨论,弱密钥与半弱密钥互补密钥DES的破译密钥长度的争论DES的轮数函数F

15、S-盒的疑问,函数F,Feistel密码的核心是函数F，函数F依赖于S盒的使用。函数F作用：给Feistel密码注入了混淆的成分。F是非线性的，是DES中唯一的非线性成分。函数F设计的雪崩准则（输入的一位变化引起输出的很多位变化严格雪崩准则SAC（Strictavalanchecriterion)：对于任何的i,j，当任何一个输入比特i变化时，一个S盒子的任何输出比特j变化的概率为1/2。比特独立准则BIC(bitindependencecriterion)：对于任意的i,j,k，当任意一个输入比特i变化时，输出j和k应当独立地变化。,DES的雪崩效应-i,DES的雪崩效应-ii,对DES的讨

16、论,弱密钥与半弱密钥互补密钥DES的破译密钥长度的争论DES的轮数函数FS-盒的疑问,S-盒的构造要求,S-盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度提供了密码算法所必须的混乱作用如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题非线性度、差分均匀性、严格雪崩准则、没有陷门,S-Box问题-i,S-Box的设计细节，NSA和IBM都未公开过。70年代中Lexar公司和Bell公司都对S-Box进行了大量研究，她们都发现了S-Box有一些不能解释的特征，但并没有找到弱点。Lexar结论：“已发现的DES的结构毫无疑问增强了系统抗击一

17、定攻击的能力，同时也正是这些结构似乎削弱了系统抗攻击的能力。”（S-Box不是随机选取的）Bell结论：S-Box可能隐藏了陷门。,S-Box问题-ii,1976年美国NSA提出了下列几条S盒的设计准则：没有一个S盒是它输入变量的线性函数S盒的每一行是整数0，15的一个置换改变S盒的一个输入位至少要引起两位的输出改变对任何一个S盒和任何一个输入X，S（X）和S(X001100）至少有两个比特不同（这里X是长度为6的比特串）对任何一个S盒，对任何一个输入对e,f属于0,1,S(X)S(X11ef00)对任何一个S盒，如果固定一个输入比特，来看一个固定输出比特的值，使这个输出比特为0的输入数目将接

18、近于使这个输出比特为1的输入数目。,S-Box问题-iii,在差分分析公开后，1992年IBM公布了S-盒和P-盒设计准则。没有一个S盒是它输入变量的线性函数S盒的每一行是整数0，15的一个置换改变S盒的一个输入位至少要引起两位的输出改变对任何一个S盒和任何一个输入X，S（X）和S(X001100）至少有两个比特不同（这里X是长度为6的比特串）对任何一个S盒，对任何一个输入对e,f属于0,1,S(X)S(X11ef00)对于任何输入之间的非零的6位差值，具有这种差值的输入中32对中有不超过8对的输出相同。,S盒子的设计,从本质上说，希望S盒子输入向量的任何变动在输出方都产生看似随机的变动。这两

19、种变动之间的关系是非线性的并难于用线性函数近似。S盒的设计方法：随机产生：s盒较小时不太理想带测试的随机产生人工产生：利用简单的数学原理，配合手工方法，DES就是利用这种方法设计。用数学方法：安全性高,内容提要,乘积密码DES的产生与应用分组密码的设计原理与方法简化的DESFeistel密码结构对DES的描述对DES的讨论分组密码的工作模式DES密码的应用,分组密码的工作模式,电子密码本ECB(electroniccodebookmode)密码分组链接CBC(cipherblockchaining)密码反馈CFB(cipherfeedback)输出反馈OFB(outputfeedback)计数

20、器CTR(counter),电子密码本（ECB）,重要特点：在给定的密钥下，相同的明文总是对应相同的密文。名称的由来：对给定的密钥，任何64位的明文组只有唯一的密文与之对应，可以想像存在一个很厚的密码本，根据任意64位明文可以查到相应的密文。使用方法：若明文长度大于64位，可将其分为64位分组，必要时可对最后一个分组进行填充。,电子密码本（ECB）,ECB的特点,简单和有效可以并行实现不能隐藏明文的模式信息相同明文相同密文同样信息多次出现造成泄漏对明文的主动攻击是可能的（提款）信息块可被替换、重排、删除、重放误差传递：密文块损坏仅对应明文块损坏适合于传输短信息：加密密钥,分组密码的工作模式,电

21、子密码本ECB(electroniccodebookmode)密码分组链接CBC(cipherblockchaining)密码反馈CFB(cipherfeedback)输出反馈OFB(outputfeedback)计数器CTR(counter),密码分组链接（CBC）,目点：消除电子密码本ECB模式的缺点。相同的明文加密成不同的密文。密码算法的输入是当前的明文组和上一个密文组的异或。相当于每个明文异或一个初始化向量的ECB,密码分组链接（CBC）,CBC特点,没有已知的并行实现算法能隐藏明文的模式信息：相同明文不同密文需要共同的初始化向量IVIV需要保密：初始化向量IV可以用来改变第一块对明文

22、的主动攻击是不容易的信息块不容易被替换、重排、删除、重放误差传递：密文块损坏两明文块损坏安全性好于ECB适合于传输长度大于64位的报文，是大多系统的标准如SSL、IPSec,分组密码的工作模式,电子密码本ECB(electroniccodebookmode)密码分组链接CBC(cipherblockchaining)密码反馈CFB(cipherfeedback)输出反馈OFB(outputfeedback)计数器CTR(counter),密码反馈CFB,在密码分组链接CBC模式下，整个数据分组在接受完成之后才能进行加密。例如：某些安全的网络环境中，可能需要当从终端输入时，必须把每个字符实时加密

23、传给主机，这种方式CBC无法满足。CFB:分组密码流密码,CFB加密示意图,CFB解密示意图,CFB特点,相当于自同步序列密码分组密码流密码隐藏了明文模式需要共同的移位寄存器初始值IV对于不同的消息，IV必须唯一：如果第三方知道了先前的EK(IV)，则可恢复P1误差传递：明文的一个错误会影响后面所有密文。密文的1位错误会引起对应明文的1位错误，同时密文进入移位寄存器后，会引起其后多个明文单元的错误。,流密码的分类,依据状态转移函数与输入明文有无关系分类，也即系统状态与明文信息的关系来划分：同步流密码：与明文信息无关，即密码流独立于明文。自同步流密码：与明文信息有关，不仅与当前输入有关，而且与以

24、前的输入历史有关。,分组密码的工作模式,电子密码本ECB(electroniccodebookmode)密码分组链接CBC(cipherblockchaining)密码反馈CFB(cipherfeedback)输出反馈OFB(outputfeedback)计数器CTR(counter),输出反馈OFB,同CFB模式非常相似OFB:分组密码流密码,OFB加密示意图,OFB解密示意图,OFB特点,相当于同步序列密码OFB:分组密码流密码隐藏了明文模式对于不同的消息，IV必须唯一误差传递：传输过程中一个密文单元的错误只影响对应明文单元对明文的主动攻击是可能的密文的某位取反，恢复的明文相应位也取反信息

25、块可被替换、重放安全性较CFB差在明文存在之前可以进行离线工作,分组密码的工作模式,电子密码本ECB(electroniccodebookmode)密码分组链接CBC(cipherblockchaining)密码反馈CFB(cipherfeedback)输出反馈OFB(outputfeedback)计数器CTR(counter),计数器模式Counter(CTR),很早之前就提出，但在ATM网络安全和IPSec中的广泛应用才引起注意CTR:分组密码流密码与OFB类似，但使用加密计数器值，而不是反馈值必须对每一个明文使用一个不同的计数器值加解密方式：Ci=PiXOROi（取Oi与Pi长度相同的位

26、数）Oi=DESK(i)应用于高速网络加密,计数器模式Counter(CTR),CTR特点,CTR:分组密码流密码有效性：可以并行实现可以预处理适用于高速网络可以随机访问加密的数据分组隐藏了明文模式，与CBC模式一样安全可以处理任意长度的消息误差传递：一个单元损坏只影响对应单元对明文的主动攻击是可能的信息块可被替换、重放,内容提要,乘积密码DES的产生与应用分组密码的设计原理与方法简化的DESFeistel密码结构对DES的描述对DES的讨论分组密码的工作模式DES密码的应用,DES密码的应用,由于DES在穷举攻击下相对比较脆弱，因此一般不能简单使用DES进行加密处理，需要某种算法进行替代，这

27、里通常有两种方案：一种是利用全新的算法。另一种是为保护对使用DES的已有软件和硬件的投资，采用多个密钥的多个多次DES加密。应用最广泛的是：三重DES加密,双重DES(DoubleDES),双重DES的讨论,中间相遇攻击,对双重DES有：,攻击过程：给定明文密文对(P,C)1、首先用K1的所有256个密钥加密P，对结果按X的值排序保存在表T中。2、用K2的所有256个密钥解密C，每解密一次，就将解密结果与T中的值比较，如果有相等的，就用刚测试的两个密钥对P加密，若结果为C，则这两个密钥可能是正确的密钥。,对双重DES的中间相遇攻击的分析,二重DES所用密钥的长度应是112bits，所以密钥空间为2112，也就是选择密钥有2112个可能性。即一个明文P有2112种方式映