《对称密码算法》PPT课件.ppt
第四章 对称密码算法,三重DESIDEA加密先进对称分组密码的特点AES,双重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字节。,三重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可以抵抗中间相遇攻击.,对双密钥的三重DES的分析-ii,到目前为止,还没有人给出攻击三重DES的有效方法。对其密钥空间中密钥进行蛮干搜索,那么由于空间太大为2112=51033,这实际上是不可行的。若用差分攻击的方法,相对于单一DES来说复杂性以指数形式增长,要超过1052。虽然目前还没有针对两个密钥三重DES的实用攻击方法。但对两个密钥三重DES的攻击有一些设想,以这些设想为基础将来可能设计出更成功的攻击技术。,三密钥的三重DES(Triple DES with Three Keys),C=EK3(DK2(EK1(P)P=DK1(EK2(DK3(C),三密钥的三重DES分析,密钥的有效长度为168位。与DES的兼容性可以通过令K3=K2或K1=K2得到。许多基于Internet的应用里用到:PGP和S/MIME。,IDEA算法,1990年瑞士联邦技术学院的来学嘉和Massey提出,91年修订,92公布细节。设计目标从两个方面考虑加密强度易实现性强化了抗差分分析的能力。,64位分组,128位密钥运算:XOR,模216(65536)加,模(216+1)(65537)乘三种运算均不满足分配律与结合律有大量弱密钥难以直接扩展到128位块,IDEA算法特点,IDEA设计思想,得到confusion的途径按位异或以216(65536)为模的加法以216+1(65537)为模的乘法互不满足分配律、结合律得到diffusion的途径乘加(MA)结构实现上的考虑软件和硬件实现上的考虑,IDEA加密算法,IDEA每一轮,IDEA输出变换阶段,IDEA的子密钥,BLOWFISH算法,作者为Bruce SchneierBLOWFISH算法特点采用了Feistel结构,16轮快速:18时钟周期一个字节紧凑:消耗不到5k内存简单:结构简单,易于实现和判定算法强度安全性可变:通过选择不同的密钥长度选择不同的安全级别。从32位到32*14=448位不等子密钥产生过程复杂,一次性,BLOWFISH的加密和解密操作,BLOWFISH的加密伪代码,for i=1 to 16 doREi=LEi-1 XOR Pi;LEi=FREi XOR REi-1;LE17=RE16 XOR P18;RE17=LE16 XOR P17;,BLOWFISH算法单个循环的细节,BLOWFISH算法讨论,BLOWFISH算法可能是最难攻破的传统加密算法,因为S-BOX密钥相关。算法本身的特点由于子密钥和S-BOX产生需要执行521个BLOWFISH加密算法,所以不适合于密钥频繁变化的应用场合子密钥和S-BOX产生可以保存起来与Feistel分组密钥算法不同,每一步的两个部分都参与运算,不是简单的传递。密钥变长带来灵活性。速度快,在同类算法中相比较是最快的。,RC5加密算法,作者为Ron Rivest,1994设计、1995公开算法特点三个参数参数w:表示字长,RC5加密两字长分组,可用值为16、32、64参数r:表示轮数,可用值0,1,255参数b:表示密钥K的字节数,可用值0,1,255RC5版本:RC5-w/r/b算法作者建议标定版本为RC5-32/12/16,RC5,作者为Ron Rivest1.适用于软件或者硬件实现2.运算速度快3.能适应于不同字长的程序(一个字的bit数是RC5的一个参数;)4.加密的轮数可变(轮数是RC5的第二个参数)5.密钥长度是可变的(密钥长度是RC5的第三个参数)6.对内存要求低7.依赖于数据的循环移位(增强抗攻击能力),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,CAST-128加密算法,RFC 214497定义密钥48-128位,8位增量16轮Feistel分组结构64位分组特殊处:每一步两个子密钥每一步的F不同,CAST-128算法之讨论,S-Box是固定的,但设计时尽量保证了非线性。设计者认为,选择一个好的非线性S-BOX比随机的S-BOX更可取。子密钥的产生过程采用了与其他算法不同的产生法来加强其强度。目标是对抗已知明文攻击。Blowfish和RC5算法使用了不同的技术来保证这一点。F函数具有好的confusion、diffusion等特性。子密钥相关、轮数相关增加了强度。,RC2加密算法,设计者Ron Rivest分组长度64位,密钥长度8到1024位适合于在16位微处理器上实现RC2在S/MIME中用到的密钥为40、64、128位不等,RC4流加密算法,设计者Ron Rivest工作方式OFB算法特点:简单、快速随机序列的产生,用到8*8的S盒,AES介绍,1997年NIST宣布征集AES算法。要求:与三重DES比,要快且至少一样安全,分组128位,密钥128/192/256位。1998年确定第一轮15个候选者1999年确定第二轮五个候选者:MARS,RC6,Rijndael,Serpent,Twofish。2000年底Rijndael胜出。,Rijndael简介,加密、解密相似但不对称不属于Feistel结构支持128/32=Nb数据块大小支持128/192/256(/32=Nk)密钥长度有较好的数学理论作为基础结构简单、速度快,NIST对Rijndael的评估(2000),General Security Rijndael has no known security attacks.Rijndael uses S-boxes as nonlinear components.Rijndael appears to have an adequate security margin,but has received some criticism suggesting that its mathematical structure may lead to attacks.On the other hand,the simple structure may have facilitated its security analysis during the timeframe of the AES development process.,NIST对Rijndael的评估(2000),Software Implementations Rijndael performs encryption and decryption very well across a variety of platforms,including 8-bit and 64-bit platforms,and DSPs.However,there is a decrease in performance with the higher key sizes because of the increased number of rounds that are performed.Rijndaels high inherent parallelism facilitates the efficient use of processor resources,resulting in very good software performance even when implemented in a mode not capable of interleaving.Rijndaels key setup time is fast.,NIST对Rijndael的评估(2000),Restricted-Space Environments In general,Rijndael is very well suited for restricted-space environments where either encryption or decryption is implemented(but not both).It has very low RAM and ROM requirements.A drawback is that ROM requirements will increase if both encryption and decryption are implemented simultaneously,although it appears to remain suitable for these environments.The key schedule for decryption is separate from encryption.,NIST对Rijndael的评估(2000),Hardware Implementations Rijndael has the highest throughput of any of the finalists for feedback modes and second highest for non-feedback modes.For the 192 and 256-bit key sizes,throughput falls in standard and unrolled implementations because of the additional number of rounds.For fully pipelined implementations,the area requirement increases,but the throughput is unaffected.,Attacks on Implementations The operations used by Rijndael are among the easiest to defend against power and timing attacks.The use of masking techniques to provide Rijndael with some defense against these attacks does not cause significant performance degradation relative to the other finalists,and its RAM requirement remains reasonable.Rijndael appears to gain a major speed advantage over its competitors when such protections are considered.,NIST对Rijndael的评估(2000),Encryption vs.Decryption The encryption and decryption functions in Rijndael differ.One FPGA study reports that the implementation of both encryption and decryption takes about 60%more space than the implementation of encryption alone.Rijndaels speed does not vary significantly between encryption and decryption,although the key setup performance is slower for decryption than for encryption.,NIST对Rijndael的评估(2000),Key Agility Rijndael supports on-the-fly subkey computation for encryption.Rijndael requires a one-time execution of the key schedule to generate all subkeys prior to the first decryption with a specific key.This places a slight resource burden on the key agility of Rijndael.,NIST对Rijndael的评估(2000),Other Versatility and Flexibility Rijndael fully supports block sizes and key sizes of 128 bits,192 bits and 256 bits,in any combination.In principle,the Rijndael structure can accommodate any block sizes and key sizes that are multiples of 32,as well as changes in the number of rounds that are specified.Potential for Instruction-Level Parallelism Rijndael has an excellent potential for parallelism for a single block encryption.,NIST对Rijndael的评估(2000),AES参数,AES算法结构,AES算法的轮变换中没有Feistel结构,轮变换是由三个不同的可逆一致变换组成,称之为层。线性混合层:确保多轮之上的高度扩散。非线性层:具有最优最差-情形非线性性的S-盒的并行应用。密钥加层:轮密钥简单地异或到中间状态上。,AES算法结构,状态、密钥,状态/密钥的矩阵表示,字节代替(Substitute Bytes)变换,字节代替是一个非线性的字节代替,独立地在每个状态字节上进行运算。代替表(S-盒)是可逆的,是一个1616的矩阵。,字节代替(Substitute Bytes)变换,S盒,example,行移位(Shift Row)变换,简单的置换,example,列混合Mix Column变换,代替操作,将状态的列看作有限域GF(28)上的4维向量并被有限域GF(28)上的一个固定可逆方阵A乘,example,轮密钥加(Add Round Key),一个简单地按位异或的操作,AES的密钥调度,轮密钥是通过密钥调度算法从密钥中产生,包括两个组成部分:密钥扩展和轮密钥选取。基本原理如下:所有轮密钥比特的总数等于分组长度乘轮数加1。(如128比特的分组长度和10轮迭代,共需要1408比特的密钥)。将密码密钥扩展成一个扩展密钥。轮密钥按下述方式从扩展密钥中选取:第一个轮密钥由开始Nb个字组成,第二个轮密钥由接下来的Nb个字组成,如此继续下去。,AES的密钥扩展,Rijndael算法的抵抗攻击能力,消除了DES中出现的弱密钥的可能也消除了IDEA中发现的弱密钥能有效抵抗目前已知的攻击算法线性攻击差分攻击,先进对称分组加密算法的特点,可变的密钥长度:RC5混合的运算 IDEA数据相关的圈数 RC5密钥相关的圈数 CAST-128密钥相关的S盒:Blowfish冗长密钥调度算法:Blowfish可变的F:CAST-128可变长明文/密文块长度可变圈数每圈操作作用于全部数据,