《对称密码体制》PPT课件.ppt

《《对称密码体制》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《对称密码体制》PPT课件.ppt（86页珍藏版）》请在三一办公上搜索。

1、第2章 对称密码体制,主讲内容 1.分组密码的一般设计原理 2.DES数据加密标准 3.AES加密算法,QUIZE TIME,1.古典密码的两个基本操作：、。维吉尼亚密码是采用什么操作？斯巴达的金腰带的密钥是什么？2.密码体制分为、3.公钥密码体制的两个密钥是否相同？4.对称密钥密码体制的密钥是否相同？,对称密钥算法,对称算法就是加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加/解密密钥是相同的。这些算法也叫秘密密钥算法或单密钥算法，它要求发送者和接收者在安全通信之前，商定一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都能对消息进行加/解密。,对称算法序列密

2、码,序列密码的主要原理是，通过伪随机序列发生器产生性能优良的伪随机序列，使用该序列加密信息流，（逐比特加密）得到密文序列，所以，序列密码算法的安全强度完全决定于伪随机序列的好坏。序列密码算法将明文逐位转换成密文。密钥流发生器输出一系列比特流：K1，K2，K3，Ki。密钥流跟明文比特流P1，P2，P3，Pi，进行异或运算产生密文比特流。Ci=PiKi 在解密端，密文流与完全相同的密钥流异或运算恢复出明文流。Pi=CiKi,序列密码,基于移位寄存器的序列密码应用十分广泛。一个反馈移位寄存器由两部分组成：移位寄存器和反馈函数。移位寄存器的长度用位表示，如果是n位长，称为n位移位寄存器。移位寄存器每次

3、向右移动一位，新的最左边的位根据反馈函数计算得到，移位寄存器输出的位是最低位。最简单的反馈移位寄存器是线形反馈移位寄存器，反馈函数是寄存器中某些位简单异或。,对称算法序列密码,序列密码的主要原理是，通过伪随机序列发生器产生性能优良的伪随机序列，使用该序列加密信息流，（逐比特加密）得到密文序列，所以，序列密码算法的安全强度完全决定于伪随机序列的好坏。序列密码算法将明文逐位转换成密文。密钥流发生器输出一系列比特流：K1，K2，K3，Ki。密钥流跟明文比特流P1，P2，P3，Pi，进行异或运算产生密文比特流。Ci=PiKi 在解密端，密文流与完全相同的密钥流异或运算恢复出明文流。Pi=CiKi,对称

4、算法分组密码要求,（1）分组长度应足够大。使得不同明文分组的个数足够大，以防让明文被穷学法攻击。新的算法标推般要求M128。(2)密钥空间应足够大，尽可能消除弱密钥，从而使所有密钥同等概率，以防灾学密钥攻击。同时，密钥不能太长，以利于密钥管理。DES采用56比特有效密钥，现在看来显然不够长。今后一段时间内，128比特密钥应该是足够安全的。,对称算法分组密码要求,(3)由密钥确定的算法要足够复杂，充分实现明文与密钥的扩散和混淆，没有简单关系可循，要能抵抗各种已知的攻击，如差分攻击和线性攻击等；另外，还要求有较高的非线性阶数。(4)软件实现的要求：尽量使用适合编程的子块和简单的运算。密码运算在于块

5、上进行，要求子块的长度能适应软件编程，如8、16、32比特等。应尽量避免按比特置换。,怎么样满足 分组密码要求,Shannon在1949的论文中介绍了一个新思想：通过“乘积”来组合密码体制。所谓乘积密码就是采用m个函数（密码）f1,f2,fm的复合，其中每个fi可能是一个代换或置换。Shannon建议交替使用代换和置换两种方法，即他称之为混乱（confusion）和扩散（diffusion）的过程，破坏对密码系统进行的各种统计分析。这种思想在现代密码体制的设计中十分重要，深刻影响着数据加密标准DES、高级数据加密标准AES的设计。,Shannon的新思想：“乘积”,扩散，就是将明文的统计特性迅

6、速散布到密文中去，实现方式是使得明文的每一位影响密文中多位的值，即密文中每一位受明文中多位影响；将密钥的每位数字尽可能扩散到更多个密文数字中去，以防止对密钥进行逐段破译。根据扩散原则，分组密码应设计成明文的每个比特与密钥的每个比特对密文的每个比特都产生影响。,Shannon的新思想：“乘积”,混乱的目的在于使明文和密文之间的统计关系变得尽可能复杂。使用复杂的非线形代换算法可得预期的混淆效果。常见的乘积密码是迭代密码。典型的迭代密码定义了一个轮函数和一个密钥编排方案，对明文的加密将经过多轮迭代。设K是一个定长的主密钥，密码编排方案用K生成Nr轮个轮密钥（子密钥）Ki。轮函数g以轮密钥Ki和当前状

7、态wi-1作为输入。初始状态w0=x，明文x，密文y，经过所有Nr轮后的状态wNr。加密过程是：w0=x wi=g（wi-1,Ki）i=1,2,Nr 解密过程是：wNr=y wi-1=g-1（wi,Ki）i=Nr,Nr-1,1,Feistel网络的结构,Feistel提出利用乘积密码可获得简单的代换密码，乘积密码指顺序地执行多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果。取一个长度为n的分组（n为偶数），然后把它分为长度为n/2的两部分：L和R。定义一个迭代的分组密码算法，其第i轮的输出取决于前一轮的输出，Feistel网络的结构如下图：,Feistel网络结构图,SP

8、网络结构,奥利奥 汉堡在哪里,数据加密标准（Data Encryption Standard,DES),背景,发明人：美国IBM公司 W.Tuchman 和 C.Meyer 1971-1972年研制成功基础：1967年美国Horst Feistel提出的理论产生：美国国家标准局（NBS)1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（Data Encryption Standard），于1977年7月15日生效,背景

9、,美国国家安全局（NSA,National Security Agency)参与了美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位1979年，美国银行协会批准使用DES1980年，DES成为美国标准化协会(ANSI)标准1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作,DES概述,分组加密算法：明文和密文为64位分组长度对称算法：加密和解密除密钥编排不同外，使用同一算法密钥长度：56位，但每个第8位为奇偶校验位，可忽略密钥可为任意的56位数，但存在弱密钥

10、，容易避开采用混乱和扩散的组合，每个组合先替代后置换，共16轮只使用了标准的算术和逻辑运算，易于实现,DES加密算法的一般描述,DES加密过程,DES加解密过程,Ek（m）=IP-1T16T15T1IP（m）。其中IP为初始置换，IP-1是IP的逆，Ti，i=1，2，16是一系列的变换。解密算法为m=Ek-1 Ek（m）=IP-1T1T2T16IPEk（m）。,DES中的各种置换、扩展和替代,初始置换IP和初始逆置换IP1,IP和IP1,IP,IP1,DES的一轮迭代,扩展置换-盒32位扩展到48位,扩展,压缩替代S-盒48位压缩到32位,共8个S盒,S-盒1,S-盒2,S-盒3,S-盒4,S

11、-盒5,S-盒6,S-盒7,S-盒8,S-盒的构造,S-盒的构造,DES中其它算法都是线性的，而S-盒运算则是非线性的S-盒不易于分析，它提供了更好的安全性所以S-盒是算法的关键所在,S-盒的构造准则,S盒的每一行是整数0，15的一个置换没有一个S盒是它输入变量的线性函数改变S盒的一个输入位至少要引起两位的输出改变对任何一个S盒和任何一个输入X，S（X）和 S(X001100）至少有两个比特不同（这里X是长度为6的比特串）对任何一个S盒，对任何一个输入对e,f属于0,1,S(X)S(X11ef00)对任何一个S盒，如果固定一个输入比特，来看一个固定输出比特的值，这个输出比特为0的输入数目将接近

12、于这个输出比特为1的输入数目,S-盒的构造要求,S-盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度提供了密码算法所必须的混乱作用如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门,置换p-盒的构造,p-盒的构造准则,P置换的目的是提供雪崩效应明文或密钥的一点小的变动都引起密文的较大变化,DES中的子密钥的生成,密钥置换算法的构造准则,设计目标：子密钥的统计独立性和灵活性实现简单速度不存在简单关系：(给定两个有某种关系的种子密钥,能预测它们轮子密钥之间的关系)种子密钥的所有比特对每个子

13、密钥比特的影响大致相同从一些子密钥比特获得其他的子密钥比特在计算上是难的没有弱密钥,DES的一轮迭代,DES加密算法的一般描述,多重DES,两重DES,三重DES,Quize time 5 minutes,1.DES是对称密钥加密算法还是公钥加密算法？是分组密码还是序列密码？2.DES有效密钥长度位，分组长度位，3DES有效密钥长度位？3.DES用于加密消息还是传递密钥？相对于公钥，加密速度快还是慢？4.序列密码比分组密码安全高还是低？5.DES是否有弱密钥？6.DES是在古典密码基本操作基础上，通过乘积实现的，对吗？,DES的安全性,F函数(S-Box)设计原理未知 密钥长度的争论 DES的

14、破译 弱密钥与半弱密钥,破译DES,1990年，以色列密码学家Eli Biham和Adi Shamir提出了差分密码分析法，可对DES进行选择明文攻击,差分密码分析(Differential cryptanalysis),DES经历了近20年全世界性的分析和攻击，提出了各种方法，但破译难度大都停留在255量级上。1991年Biham和Shamir公开发表了差分密码分析法才使对DES一类分组密码的分析工作向前推进了一大步。目前这一方法是攻击迭代密码体制的最佳方法，它对多种分组密码和Hash 函数都相当有效，相继攻破了FEAL、LOKI、LUCIFER等密码。此法对分组密码的研究设计也起到巨大推动

15、作用。,差分密码分析(Differential cryptanalysis),差分密码分析是一种攻击迭代分组密码的选择明文统计分析破译法。它不是直接分析密文或密钥的统计相关性，而是分析明文差分和密文差分之间的统计相关性。给定一个r轮迭代密码，对已知n长明文对X和X，定义其差分为 X=X(X)-1 其中，表示n-bits组X的集合中定义的群运算，(X)-1为X在群中的逆元。,易受攻击的位置,电话公司市话局,接线盒,DES用软件进行解码需要用很长时间，而用硬件解码速度非常快，但幸运的是当时大多数黑客并没有足够的设备制造出这种硬件设备。在1977年，人们估计要耗资两千万美元才能建成一个专门计算机用于

16、DES的解密，而且需要12个小时的破解才能得到结果。所以，当时DES被认为是一种十分强壮的加密方法。,1997年开始，RSA公司发起了一个称作“向DES挑战”的竞技赛。1997年1月，用了96天时间，成功地破解了用DES加密的一段信息；一年之后，在第二届赛事上，这一记录41天；1998年7月，“第2-2届DES挑战赛（DES Challenge II-2）”把破解DES的时间缩短到了只需56个小时；“第三届DES挑战赛（DES Challenge III）”把破解DES的时间缩短到了只需22.5小时。,三重DES 解决其密钥长度问题的方法，即采用三重DES。这种方法用两个密钥对明文进行三次加密

17、，假设两个密钥是K1和K2，其算法的步骤：1.用密钥K1进行DES加密。2.用K2对步骤1的结果进行DES解密。3.用步骤2的结果使用密钥K1进行DES加密缺点：花费原来三倍时间优点：112位密钥长度，很“强壮”的加密方式,第2节 AES的起源,1997年9月，NIST征集AES方案，以替代DES。1999年8月，以下5个方案成为最终候选方案：MARS,RC6,Rijndael,Serpent,Twofish。2000年10月，由比利时的Joan Daemen和Vincent Rijmen提出的算法最终胜出。（Rijndael 读成Rain Doll。）http:/www.esat.kuleu

18、ven.ac.be/rijmen/rijndael/,2.AES的设计原则,能抵抗所有已知的攻击；在各种平台上易于实现，速度快；设计简单。,Rijndael是一个分组密码算法，其分组长度和密钥长度相互独立，都可以改变。,表 1.分组长度和密钥长度的不同取值,3.AES 算法的一般描述,Rijndael Round的构成,字节代替,行移位,列混合,+,轮密钥,一般的轮变换,字节代替,行移位,+,轮密钥,最后一轮的轮变换,3.AES 算法加密部分的实现,明文分组和密钥的组织排列方式,Fig 1.以明文分组为128bits为例组成的阵列,Fig 2.以明文分组（或密钥）为128bits、192bit

19、s、256bits为例组成的阵列,状态（State）：密码运算的中间结果称为状态。State的表示：状态用以字节为基本构成元素的矩阵阵列来表示，该阵列有4行，列数记为Nb。Nb=分组长度（bits）32 Nb可以取的值为4，6，8，对应的分组长度为128，192，256 bits。密码密钥（Cipher Key）的表示：Cipher Key类似地用一个4行的矩阵阵列来表示，列数记为Nk。Nk=密钥长度（bits）32 Nk可以取的值为4，6，8，对应的密钥长度为128，192，256 bits。,Fig 3.当Nb=6时的状态和Nk=4时的密钥布局,Nb=6Block Length=192 b

20、its,Nk=4Key Length=128 bits,Fig 4.分组长度和密钥长度均为128 bits时的Rijndael加密算法框图,Data/Key Addition,Rnd0,Rnd1,Rnd8,FinalRnd,KeySchedule,CipherText,Key,PlainText,表 2.轮数（Round）的不同取值,Rijndael 之所为能当选AES,主要是因为:(1)运算速度快，软硬件实现都表现出非常好的性能；(2)对内存的需求非常低,很适合于受限制的环境下；(3)算法可靠，使用非线性结构S盒,有足够的安全性；(4)该 算法能有效抵抗差分分析和线性分析攻击；(5)Rijn

21、dael 是一个分组迭代密码,被设计成128/192/256 比特三种密钥长度,可用于加密长度为128/192/256 比特的分组,相应的轮数为10/12/14,分组长度和密钥长度设计灵活。(6)密钥安装的时间很好,具有很高的灵活性。,这个矩阵称为状态（state）,以后所有的变换都是基于这个矩阵进行的，到此，准备工作已经完成。现在按照前面的顺序进行加密变换，首先开始第一次循环的第一个变换：字节代换(SubByte()。,字节代换(SubByte(),查表,根据其S1,1的值用两位十六进制数表示，第一位为行号X，第二位作为列号Y，对S盒进行查表作为对应的输出。,字节代换-S盒变换(查表),S1

22、2=53,则X=5,Y=3,out9=ed,ShiftRows()(行移位)变换,行变换示意图,S,S,（列混合）变换：AXS=S形式。,MixColumns()（列混合）变换,S0c(02 S0c)(03 S1c)S2cS3c，但这个结果可能会超出一个字节的存储范围，所以实际上还要对结果进行处理。,轮密钥的添加,AddRoundKey(),轮密钥的添加,AES 的密钥调度 密钥调度包括两个部分：密钥扩展和轮密钥选取。,密钥bit的总数分组长度（轮数Round1）例如当分组长度为128bits和轮数Round为10时，轮密钥长度为128(101)1408bits。将密码密钥扩展成一个扩展密钥。

23、从扩展密钥中取出轮密钥：第一个轮密钥由扩展密钥的第一个Nb个4字节字，第二个圈密钥由接下来的Nb个4字节字组成，以此类推。,将初始密钥表示成4X4的矩阵的形式，按列优先排列，每一个格子相当于一个字节，共4X4X8=128bit，其中w0、w1、w2、w3表示初始密钥，w4、w5、w6、w7表示第二轮扩展后的密钥，最后一轮是w40、w41、w42、w43。,密钥扩展,+,+,+,ByteSubstitution,ByteRotate,+,Rcon,Wi-4,Wi-3,Wi-2,Wi-1,Wi,ByteSubstituion,ByteRotate,+,Rcons,+,Key expansion,4

24、=i 4(Rnd+1),i mod 4=0,i mod 4!=0,轮密钥选取,轮密钥0,轮密钥1,轮密钥2,AES的解密算法,解密算法与加密算法不同每个阶段均可逆，因此易证解密函授的确可以恢复明文,AES 算法的设计原理,GF(28)中乘法使用的多项式是8次不可约多项式列表中的第一个多项式。ByteSubstitution（称为S盒）在设计时考虑到抵抗差分密码分析、线性密码分析的要求，应满足以下条件：1.可逆性；2.输入比特的线性组合与输出比特的组合之间的最大非平凡相关性的极小化；3.异或差分表中最大非平凡值的极小化；4.GF(28)中代数表示的复杂性；5.描述的简单性。,满足前3条准则的S盒

25、的构造方法已被给出，AES的作者从众多候选构造中选择将x映射到它的逆的S盒。该映射过于简单，为了抵抗插入攻击，加入仿射变换：b(x)=(x7+x6+x2+x)+a(x)(x7+x6+x5+x4+1)mod x8+1模数多项式x8+1选择为可能是最简单的模数多项式。可以找到其它的S盒满足以上准则。,MixColumn变换符合以下准则：1.可逆性；2.GF(2)中的线性性；3.适当的扩散性能；4.8位处理器上实现速度快；5.对称性；6.描述的简单性。选择模数多项式x41可满足准则2、5、6。准则1、3、4要求系数的值要小，故选00、01、02、03。ByteRotation符合以下准则：1.4个位移量互不相同且C00；2.能抵抗差分截断攻击；3.能抗Square攻击；4.简单。从满足准则2和准则3出发，AES的作者选取了最简单的组合。,与一些其它算法的比较：,与DES相比：1.无DES中的弱密钥和半弱密钥；2.紧凑的设计使得没有足够的空间来隐藏陷门。与IDEA相比：无IDEA中的弱密钥。具有扩展性：密钥长度可以扩展到为32bits倍数的任意密钥长度，分组长度可以扩展到为64bits倍数的任意分组长度。圈数和循环移位偏移量作为参数，要重新定义。,