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

第三章 对称密码体制,对称加密技术,基本概念标准算法的介绍DES算法AES算法分组密码的分析方法分组密码的工作模式,基本概念,密码学中常见的有两种体制:对称密码体制(单钥密码体制)如果一个加密系统的加密密钥和解密密钥相同，或者虽然不相同，但是由其中的任意一个可以很容易地推导出另一个，即密钥是双方共享的,则该系统所采用的就是对称密码体制。非对称密码体制(公钥密码体制)分组密码是指将处理的明文按照固定长度进行分组，加解密的处理在固定长度密钥的控制下，以一个分组为单位独立进行，得出一个固定长度的对应于明文分组的结果。属于对称密码体制的范畴。,基本概念（续）,在分组密码的设计中用代替、置换手段实现扩散和混淆功能。混淆 指加密算法的密文与明文及密钥关系十分复杂，无法从数学上描述，或从统计上去分析。扩散 指明文中的任一位以及密钥中的任一位，对全体密文位有影响。经由此种扩散作用，可以隐藏许多明文在统计上的特性，增加密码的安全,对称加密技术,基本概念标准算法的介绍DES算法国际数据加密算法（IDEA）AES算法分组密码的分析方法分组密码的工作模式,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日生效。,DES加密算法的背景,美国国家安全局（NSA,National Security Agency)参与了美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位。1979年，美国银行协会批准使用DES。1980年，DES成为美国标准化协会(ANSI)标准。1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作。,DES算法描述,为二进制编码数据设计的，可以对计算机数据进行密码保护的数学运算。DES使用56位密钥对64位的数据块进行加密，并对64位的数据块进行16轮编码。在每轮编码时，一个48位的“每轮”密钥值由56位的“种子”密钥得出来。DES算法的入口参数有三个：Key、Data和Mode。Key为8个字节共64位，是DES算法的工作密钥；Data也为8个字节64位，是要被加密或被解密的数据；Mode为DES的工作方式，有两种：加密或解密64位明文变换到64位密文，密钥64位，实际可用密钥长度为56位。,DES算法描述（续）,初始换位的功能是把输入的64位数据块按位重新组合，并把输出分为L0、R0两部分，每部分各长32位，其置换规则见下表：58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7例：设置换前的输入值为D1D2D3.D64，则经过初始置换后的结果为：L0=D58D50.D8；R0=D57D49.D7。,DES算法描述（续）,逆置换正好是初始置的逆运算。【例】第1位经过初始置换后，处于第40位，而通过逆置 换，又将第40位换回到第1位，其逆置换规则如下表所示：40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25,DES算法的一次迭代过程图,DES算法描述（续）,扩展置换为:32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1P-盒置换为：16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25,在变换中用到的S1,S2.S8为选择函数，俗称为S-盒，是DES算法的核心。其功能是把6bit数据变为4bit数据。S1:14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 015 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 在S1中，共有4行数据，命名为0，1、2、3行；每行有16列，命名为0、1、2、3，.，14、15列。现设输入为：DD1D2D3D4D5D6 令：列D2D3D4D5 行D1D6然后在S1表中查得对应的数，以4位二进制表示，此即为选择函数S1的输出。,密钥Ki(48bit)的生成算法,DES的破解,DES的实际密钥长度为56-bit，就目前计算机的计算机能力而言，DES不能抵抗对密钥的穷举搜索攻击。1997年1月28日，RSA数据安全公司在RSA安全年会上悬赏10000美金破解DES，克罗拉多州的程序员Verser在Inrernet上数万名志愿者的协作下用96天的时间找到了密钥长度为40-bit和48-bit的DES密钥。1998年7月电子边境基金会（EFF）使用一台价值25万美元的计算机在56小时之内破译了56-bit的DES。1999年1月电子边境基金会（EFF）通过互联网上的10万台计算机合作，仅用22小时15分就破解了56-bit的ES。不过这些破译的前提是，破译者能识别出破译的结果确实是明文，也即破译的结果必须容易辩认。如果明文加密之前经过压缩等处理，辩认工作就比较困难。,DES算法的公开性与脆弱性,DES的两个主要弱点：密钥容量：56位不太可能提供足够的安全性S盒：可能隐含有陷井（Hidden trapdoors）DES的半公开性：S盒的设计原理至今未公布,对称加密技术,基本概念标准算法的介绍DES算法AES算法分组密码的工作模式分组密码的分析方法,分组密码的操作模式,电子密码本ECB(electronic codebook mode)密码分组链接CBC(cipher block chaining)密码反馈CFB(cipher feedback)输出反馈OFB(output feedback),电子密码本（ECB）,Ci=EK(Pi)Pi=DK(Ci),ECB特点,简单和有效可以并行实现不能隐藏明文的模式信息相同明文相同密文同样信息多次出现造成泄漏对明文的主动攻击是可能的信息块可被替换、重排、删除、重放误差传递：密文块损坏仅对应明文块损坏适合于传输短信息,密码分组链接CBC,Ci=EK(Ci-1Pi)Pi=EK(Ci)Ci-1,CBC特点,没有已知的并行实现算法能隐藏明文的模式信息需要共同的初始化向量IV相同明文不同密文初始化向量IV可以用来改变第一块对明文的主动攻击是不容易的信息块不容易被替换、重排、删除、重放误差传递：密文块损坏两明文块损坏安全性好于ECB适合于传输长度大于64位的报文，还可以进行用户鉴别,是大多系统的标准如 SSL、IPSec,密码反馈CFB,CFB:分组密码流密码 Si 为移位寄存器,j为流单元宽度 加密:Ci=Pi(EK(Si)的高j位)Si+1=(Sij)|Ci 解密:Pi=Ci(EK(Si)的高j位)Si+1=(Sij)|Ci,CFB加密示意图,Ci=Pi(EK(Si)的高j位);Si+1=(Sij)|Ci,CFB解密示意图,Pi=Ci(EK(Si)的高j位);Si+1=(Sij)|Ci,CFB特点,分组密码流密码没有已知的并行实现算法隐藏了明文模式需要共同的移位寄存器初始值IV对于不同的消息，IV必须唯一误差传递：一个单元损坏影响多个单元,输出反馈OFB,OFB:分组密码流密码 Si 为移位寄存器,j为流单元宽度 加密:Ci=Pi(EK(Si)的高j位)Si+1=(Sij)|(EK(Si)的高j位)解密:Pi=Ci(EK(Si)的高j位)Si+1=(Sij)|(EK(Si)的高j位),OFB加密示意图,Ci=Pi(EK(Si)的高j位);Si+1=(Sij)|(EK(Si)的高j位),OFB解密示意图,Pi=Ci(EK(Si)的高j位);Si+1=(Sij)|(EK(Si)的高j位),OFB特点,OFB:分组密码流密码没有已知的并行实现算法隐藏了明文模式需要共同的移位寄存器初始值IV误差传递：一个单元损坏只影响对应单元对明文的主动攻击是可能的信息块可被替换、重排、删除、重放安全性较CFB差,对称加密技术,基本概念标准算法的介绍DES算法AES算法分组密码的工作模式分组密码的分析方法,分组密码的分析方法,根据攻击者所掌握的信息,可将分组密码的攻击分为以下几类:唯密文攻击已知明文攻击选择明文攻击攻击的复杂度数据复杂度:实施该攻击所需输入的数据量处理复杂度:处理这些数据所需要的计算量,分组密码的典型攻击方法,最可靠的攻击办法:强力攻击最有效的攻击:差分密码分析,通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特.线性密码分析:本质上是一种已知明文攻击方法,通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统插值攻击方法密钥相关攻击,强力攻击,穷尽密钥搜索攻击:唯密文,2k已知(选择)明文,2k,k-密钥长度字典攻击:明密文对编成字典,2n,n-分组长度查表攻击:选择明文攻击,给定明文,用所有的2k个密钥,预计算密文,k-密钥长度时间存储权衡攻击:选择明文攻击,由穷尽密钥搜索和查表攻击混合而成,它在选择明文攻击中以时间换取空间,现代常规分组加密算法,一种是对DES进行复合，强化它的抗攻击能力；另一种是开辟新的方法，即象DES那样加解密速度快，又具有抗差分攻击和其他方式攻击的能力。,现代常规分组加密算法,1.Triple DES2.IDEA3.RC54.RC65.AES其他一些较实用的算法，如Blowfish，CAST，以及RC2。,1.TRIPLE DES,由于已经证明DES不能成为群，见 Proof that DES is not a group In Advances in CryptologyCrpto92.Springer-Verlag,New York,1993.于是多重DES，尤其是三重DES还在普遍使用。,双重DES(Double DES),C=EK2(EK1(P)P=DK1(DK2(C),双重DES的讨论,假设对于 DES和所有56比特密钥，给定任意两个密钥K1和K2，都能找到一个密钥K3使得EK2(EK1(P)=EK3(P)。如果这个假设是事实，则DES的两重加密或者多重加密都将等价于用一个56比特密钥的一次加密。从直观上看，上面的假设不可能为真。因为DES的加密事实上就是做一个从64比特分组到一个64分组的置换，而64比特分组共有264可能的状态，因而可能的置换个数为另一方面，DES的每个密钥确定了一个置换，因而总的置换个数为。直到1992年才有人证明了这个结果。,中间相遇(meet-in-the-middle)攻击,C=EK2(EK1(P)X=EK1(P)=DK2(C)给定明文密文对(P,C)对所有256个密钥,加密P,对结果排序 对所有256个密钥,解密C,对结果排序 逐个比较,找出K1,K2使得EK1(P)=DK2(C),对双重DES的中间相遇攻击的分析,已知，给定一个明文P，经二重DES加密有264个可能的密文。而二重DES所用密钥的长度应是112 bits，所以选择密钥有2112个可能性。于是对给定一个明文P加密成密文有2112/264=248种可能。给定两个明密文对,虚警率降为248-64=2-16。换句话说，对已知2个明文-密文对的中间相遇攻击成功的概率为1-2-16。攻击用的代价加密或解密所用运算次数 2 256 需要大量的存储器:256 64=1017字节,Triple-DES的四种模型,DES-EEE3：三个不同密钥，顺序使用三次加密算法DES-EDE3：三个不同密钥，依次使用加密-解密-加密算法DES-EEE2：K1=K3，同上DES-EDE2：K1=K3，同上,双密钥的三重DES（Triple DES with Two Keys),C=EK1(DK2(EK1(P)P=DK1(EK2(DK1(C),对双密钥的三重DES的分析-i,该模式由IBM设计,可与常规加密算法兼容这种替代DES的加密较为流行并且已被采纳用于密钥管理标准（The Key Manager Standards ANSX9.17和ISO8732).交替使用K1和K2可以抵抗中间相遇攻击.如果C=EK2(EK1(EK1(P),只需要256+2次加密到目前为止，还没有人给出攻击三重DES的有效方法。对其密钥空间中密钥进行蛮干搜索，那么由于空间太大为2112=51033，这实际上是不可行的。若用差分攻击的方法，相对于单一DES来说复杂性以指数形式增长，要超过1052。,对双密钥的三重DES的分析-ii,目前还没有针对两个密钥三重DES的实用攻击方法。但对两个密钥三重DES的攻击有一些设想，以这些设想为基础将来可能设计出更成功的攻击技术。Merkle R.and Hellman,M.“On the security of multiple encryption”.Communication of the ACM,July 1981Oorschot,P and Wiener,M.“A Known-plaintext attack on two-key triple encryption”Proceedings,EUROCrypt90,1990:published by Springer-Verlag,三密钥的三重DES（Triple DES with Three Keys),C=EK3(DK2(EK1(P)P=DK3(EK2(DK1(C),三密钥的三重DES分析,密钥的有效长度为168位与DES的兼容性可以通过令K3=K2或K1=K2得到许多基于Internet的应用里用到：PGP和S/MIME,现代常规分组加密算法,1.Triple DES2.IDEA3.RC54.RC65.AES,国际数据加密IDEA（International Data Encryption Algorithm)算法,1990年瑞士联邦技术学院的来学嘉和Massey提出，PES，91年修订，92公布细节设计目标从两个方面考虑加密强度易实现性强化了抗差分分析的能力，PGP,IDEA算法特点,64位分组,128位密钥运算:XOR,模216（65536）加,模(216+1)（65537）乘三种运算均不满足分配律与结合律有大量弱密钥难以直接扩展到128位块,IDEA设计思想,得到confusion的途径按位异或以216(65536)为模的加法以216+1(65537)为模的乘法互不满足分配律、结合律得到diffusion的途径乘加(MA)结构实现上的考虑软件和硬件实现上的考虑,IDEA加密算法,IDEA每一轮,IDEA输出变换阶段,IDEA的子密钥,现代常规分组加密算法,1.Triple DES2.IDEA3.RC54.RC65.AES,RC5,作者为Ron Rivest 1994设计、1995公开1.适用于软件或者硬件实现2.运算速度快3.能适应于不同字长的程序（一个字的bit数是RC5的一个参数；）加密的轮数可变（轮数是RC5的第二个参数）密钥长度是可变的（密钥长度是RC5的第三个参数）6.对内存要求低7.依赖于数据的循环移位（增强抗攻击能力）,RC5参数,三个参数参数w：表示字长，RC5加密两字长分组，可用值为16、32、64参数r：表示轮数，可用值0,1,255参数b：表示密钥K的字节数，可用值0,1,255RC5版本：RC5-w/r/b算法作者建议标定版本为RC5-32/12/16,RC5基本运算,整个加密使用了下述3个基本运算和它们的逆运算：模2w加法运算，表示为“+”；逐比特异或运算，表示为“”；字的循环左移运算：字x循环左移y比特，表示为xy如（a0,a1,a2,an-1)3=(a3,a4,an-1,a0,a1,a2),密钥扩展,总计产生 t=2r+2 个子密钥，每个密钥的长度为一个字长（w bits)。,密钥的初始化,对于给定的参数r和w，开始初始化运算 Pw=Odd(e-2)2w)Qw=Odd(-1)2w)这里 自然对数的底）（黄金分割比率）并且Oddx表示最接近x且可左可右的奇整数。例：Odde=3,Odd=1用上述两个常数，按下述方式得到初始化的阵列S:S0=Pw For i=1 to t-1 do Si=Si-1+Qw其中的加法是模2w的加法运算。,密钥扩展,1*.为了增强复杂性，可对阵列S,L做多次处理：i=j=x=y=0 do 3max(t,c)times:Si=(Si+X+Y)3；X=Si；i=(i+1)(mod t);Lj=(Lj+X+Y)(X+Y)；Y=Lj；j=(j+1)(mod c);2*.Rivest 声称，这个扩张函数具有单向性。,加解密运算图,加密算法,加密：将明文分组为左右A,B；用变量Lei，Rei参与运算程序为：LE0=A+S0 RE0=B+S1 for i=1 to r do LEi=(LEi-1REi-1)REi-1)+S2i;REi=(REi-1 LEi)LEi)+S2i+1;,解密算法,对两个1-字变量LDr和RDr。用变量LDi和RDi从r到1做：for i=r down to 1 do RDi-1=(RDi-S2*i+1LDi)LDi);LDi-1=(LDi-S2*iRDi-1)RDi-1);B=RD0-S1;A=LD0-S0.RC5操作模式RFC2040 Baldwin,R.,and Rivest,R.The RC5,RC5-CBC,RC5-CBC-Pad,and RC5-CTS algorithms.Oct.1996P9696,现代常规分组加密算法,1.Triple DES2.IDEA3.RC54.RC65.AES,AES背景-i,1997年4月15日，（美国）国家标准技术研究所（NIST）发起征集高级加密标准（Advanced Encryption Standard）AES的活动，活动目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，作为新的数据加密标准。1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。作为进入AES候选过程的一个条件，开发者承诺放弃被选中算法的知识产权。对AES的基本要求是：比三重DES快、至少与三重DES一样安全、数据分组长度为128比特、密钥长度为128/192/256比特。,AES背景-ii,1998年8月12日，在首届AES会议上指定了15个候选算法。1999年3月22日第二次AES会议上，将候选名单减少为5个，这5个算法是RC6，Rijndael，SERPENT，Twofish和MARS。2000年4月13日，第三次AES会议上，对这5个候选算法的各种分析结果进行了讨论。2000年10月2日，NIST宣布了获胜者Rijndael算法，2001年11月出版了最终标准FIPS PUB197。,Rijndael简介,不属于Feistel结构加密、解密相似但不对称支持128/32=Nb数据块大小支持128/192/256(/32=Nk)密钥长度有较好的数学理论作为基础结构简单、速度快,AES参数,SP网络结构,在这种密码的每一轮中，轮输入首先被一个由子密钥控制的可逆函数S作用，然后再对所得结果用置换（或可逆线性变换）P作用。S和P分别被称为混乱层和扩散层，主要起混乱和扩散作用。,AES算法结构-i,AES算法的轮变换中没有Feistel结构，轮变换是由三个不同的可逆一致变换组成，称之为层，线性混合层：确保多轮之上的高度扩散。非线性层：具有最优最差-情形非线性性的S-盒的并行应用。密钥加层：轮密钥简单地异或到中间状态上。,AES算法结构-ii,AES-128加解密过程,AES算法描述,假设：State表示数据，以及每一轮的中间结果RoundKey表示每一轮对应的子密钥算法如下：第一轮之前执行AddRoundKey(State,RoundKey)Round(State,RoundKey)ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey);FinalRound(State,RoundKey)ByteSub(State);ShiftRow(State);AddRoundKey(State,RoundKey);,状态、密钥,状态/密钥的矩阵表示,字节代替(Substitute Bytes)变换,字节代替是一个非线性的字节代替，独立地在每个状态字节上进行运算。代替表（S-盒）是可逆的，是一个1616的矩阵。,example,行移位(Shift Row)变换,简单的置换,example,列混合Mix Column变换,代替操作，将状态的列看作有限域GF（28）上的4维向量并被有限域GF（28）上的一个固定可逆方阵A乘,example,轮密钥加（Add Round Key),一个简单地按位异或的操作,AES的密钥调度,轮密钥是通过密钥调度算法从密钥中产生，包括两个组成部分：密钥扩展和轮密钥选取。基本原理如下：所有轮密钥比特的总数等于分组长度乘轮数加1。（如128比特的分组长度和10轮迭代，共需要1408比特的密钥）。将密码密钥扩展成一个扩展密钥。轮密钥按下述方式从扩展密钥中选取：第一个轮密钥由开始Nb个字组成，第二个轮密钥由接下来的Nb个字组成，如此继续下去。,AES的密钥扩展,密钥扩展的伪代码,伪代码之二,G变换,Rotword执行一字节循环左移 b0,b1,b2,b3 b1,b2,b3,b0Subword执行使用S-盒实行字节替换前两步的结果XOR与轮常数Rconj,example,Rijndael安全性,没有发现弱密钥或补密钥能有效抵抗目前已知的攻击算法线性攻击差分攻击,先进对称分组加密算法的特点,可变的密钥长度:RC5混合的运算 IDEA数据相关的圈数 RC5密钥相关的圈数 CAST-128密钥相关的S盒:Blowfish冗长密钥调度算法：Blowfish可变的F：CAST-128可变长明文/密文块长度可变圈数每圈操作作用于全部数据,分组密码的一般设计原理,针对安全性的一般原则:混乱扩散重要的设计原理:必须能抵抗现有的攻击方法针对实现的原则软件硬件,分组密码的整体结构,Feistel 网络SP网络,作业,分组加密的概念和分析方法介绍用DES加密，明文是m=computer，密钥是programmM=01100011 01101111 01101101 01110000 01110101 01110100 01100101 01110010K=01110000 01110010 01101111 01100111 01110010 01100001 01101101 01101101,