《分组加密算法》PPT课件

第7讲分组密码,它将明文划分成固定的n比特的数据组，然后以组为单位，在密钥的控制下进行一系列的线性或非线性的变化而得到密文。这就是分组密码。分组密码一次变换一组数据。分组密码算法的一个重要特点就是：当给定一个密钥后，若明文分组相同，那么所变换出密文分组也相同。分组密码的一个重要优点是不需要同步,分组密码体制,输入,输出,加密算法,密钥,明文,输入,输出,解密算法,密钥,明文,nbit,nbit,nbit,nbit,密文,密文,分组密码的一般设计原理,分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列。,加密算法,解密算法,明文,密文,原来的明文,（x0，,xn-1）,（x0，,xn-1）,（y0，,yn-1）,分组密码的一般设计原理,设计目标在密钥控制下，从一个足够大、足够好的置换子集中简单迅速地选出一个置换，对当前输入的明文数字组进行加密变换；要求：1分组长度足够大，防止穷举攻击；2密钥空间足够大，但不能太长，以便于密钥的管理；3算法要足够复杂，充分实现明文和密钥的扩散；没有简单的关系可寻,DES对称加密技术,DES(DataEncryptionStandard)算法是一种用56位密钥来加密64位数据的方法。发明人：IBM公司W.Tuchman和C.Meyer.基础：1967年美国HorstFeistel提出的理论；产生：美国国家标准局1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准，于1973年5月15日和1974年8月27日先后两次向公众发出了征求加密算法的公告，最终选定DES。,DES,采用分组密码体制；用56bit密钥来加密64bit数据的方法；DES要达到的目标有：提供高质量的数据保护，防止数据未经授权的泄露和未被察觉的修改；具有复杂性，使得破译的开销超过可能获得的利益；DES的安全性不依赖于算法的保密，安全性仅以加密密钥的保密为基础；在实现上可行、经济；,DES算法的原理,DES算法的入口参数有三个：Key、Data、Mode。其中：Key为8个字节共64位，是DES算法的工作密钥；Data也为8个字节64位，是要被加密或被解密的数据；Mode为DES的工作方式有两种：加密或解密。,DES算法原理,DES算法的工作原理：如Mode为加密，则用Key去把数据Data进行加密，生成Data的密码形式（64位）作为DES的输出结果；如Mode为解密，则用Key去把密码形式的数据Data解密，还原为Data的明码形式（64位）作为DES的输出结果。,DES算法的实现步骤,第一步：变换明文。对给定的64位比特的明文x，首先通过一个置换IP表来重新排列x，从而构造出64位比特的x0，x0=IP(x)=L0R0，其中L0表示x0的前32比特，R0表示x0的后32位。第二步：按照规则迭代。规则为Li=Ri-1Ri=Li-1f(Ri-1,Ki)（i=1,2,316）经过第一步变换已经得到L0和R0的值，其中符号表示的数学运算是异或，f表示一种置换，由S盒置换构成，Ki是一些由密钥编排函数产生的比特块。f和Ki将在后面介绍。第三步：对L16R16进行交换得到R16L16对R16L16利用IP-1作逆置换，就得到了密文y。,DES加密过程,输入64位比特明文,DES算法的实现步骤,可以看出，DES加密需要四个关键点：(1)IP置换表和IP-1逆置换表;(2)函数f;(3)子密钥Ki。(4)S盒的工作原理。,（1）IP置换表和IP-1逆置换表,58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157,40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725,IP与IP-1互逆,M=(m1,m2,.),12345678,910111213141516,1718192021222324,2526272829303132,3334353637383940,4142434445464748,4950515253545556,12345678,910111213141516,1718192021222324,2526272829303132,3334353637383940,4142434445464748,4950515253545556,IP(M)=(m58,m50)=(m11,m12,.),585042342618102,605244362820124,625446383022146,645648403224168,57494133251791,615845372921135,635547393123157,408481656246432,397471555236331,386461454226230,375451353216129,364441252206028,342421050185826,33141949175725,IP,IP-1,DES的一轮迭代,Li-1（32bit）,Ri-1（32bit）,选择扩展运算E盒,48bit寄存器,48bit寄存器,选择压缩运算S盒,32bit寄存器,置换运算P,Ri=Li-1f(Ri-1,ki)（32bit）,（32bit）,Li=Ri-1,轮开始：64bit分成左右两半,子密钥Ki（48bit）,扩展置换E盒(ExpandBox),将输入的32bit块扩展到48bit的输出块；48bit的输出块再分成8个6bit块；,01020304,05060708,09101112,13141516,17181920,21222324,25262728,29303132,01020304,05060708,09101112,13141516,17181920,21222324,25262728,29303132,32,04,08,12,16,20,24,28,05,09,13,17,21,25,29,01,扩展置换函数E,扩展位,扩展位,固定位,压缩替代S盒(SubstitutionBox),48bit块通过S盒压缩成32bit块,48bit寄存器,32bit寄存器,6bit,4bit,共8个S盒,S盒,作用：将6个输入位映射为4个输出位；方法：若定义a1a2a3a4a5a6，将a1a6组成2位二进制数，对应S盒表中的行号；将a2a3a4a5组成一个4位的2进制数，对应S盒表中的列号；映射到交叉点的数据就是该S盒的输出。输入为101011的输出是？,S盒,S盒,S盒,DES中其它算法都是线性的，而S盒运算则是非线性的，S盒不易于分析，它提供了更好的安全性；所以S盒是算法的关键所在；提供了密码算法所必需的混乱作用；改变S盒的一个输入位至少要引起两位的输出改变；,置换函数P（Permutaion）,P置换的目的是：提供雪崩效应；明文或密钥的一点小的变动都引起密文的较大变化；,DES中子密钥的生成,64bit密钥,C0（28bit）,D0（28bit）,循环左移,循环左移,C（28bit）,C（28bit）,循环左移,循环左移,置换选择2,Ci（28bit）,Di（28bit）,(56bit),(56bit),Ki,K1,(48bit),(48bit),(56bit),置换选择-1置换选择-2,5749413325179,1585042342618,1025951432527,1911360524436,63554739312315,7625446383022,1466153453729,211352820124,1417112415,3281562110,2319124268,1672720132,415231374755,304051453348,444939563453,464250362932,置换选择1,置换选择2,多重DES双重DES,双重DES加密逻辑,双重DES解密逻辑,多重DES三重DES,加密,解密,K1,P,C,三重DES加密逻辑,三重DES解密逻辑,K2,解密,K1,B,A,解密,加密,K1,C,P,K2,解密,K1,B,A,DES算法的安全性,DES算法具有比较高安全性，到目前为止，除了用穷举搜索法对DES算法进行攻击外，还没有发现更有效的办法。而56位长的密钥的穷举空间为256，如果一台计算机的速度是每一秒种检测一百万个密钥，则它搜索完全部密钥就需要将近228.5年的时间。f函数（S盒）的设计原理未知；,DES算法的程序实现,根据DES算法的原理，可以方便的利用C语言实现其加密和解密算法。在VC+6.0中新建基于控制台的Win32应用程序，算法如程序DES1.cpp所示。,数据加密标准DES,数据加密标准DES属于常规密钥密码体制，是一种分组密码。在加密前，先对整个明文进行分组。每一个组长为64bit。然后对每一个64bit二进制数据进行加密处理，产生一组64bit密文数据。最后将各组密文串接起来，即得出整个的密文。使用的密钥为64bit（实际密钥长度为56bit，有8bit用于奇偶校验)。,DES加密标准,L0,R0,L1=R0,IP,L2=R1,L15=R14,R1=L0f(R0,K1),R2=L1f(R1,K2),R15=L14f(R14,K15),L16=R15,R16=L15f(R15,K16),IP1,f,f,f,输出,密文Y(64bit),明文X(64bit),输入,K16(48bit),K2(48bit),K1(48bit),X0的左半边(32bit),X0(64bit),X0的右半边(32bit),R16L16(64bit),DES的明显缺点,DES实际上就是一种单字符替代，而这种字符的长度是64bit。也就是说，对于DES算法，相同的明文就产生相同的密文。这对DES的安全性来说是不利的。为了提高DES的安全性，可采用加密分组链接的方法。,加密分组的链接,X0,Y0,X1,Y1,X2,Y2,X3,Y3,X0,Y0,X1,Y1,X2,Y2,X3,Y3,初始向量,初始向量,密钥,密钥,明文,明文,密文,密文,加密,解密,E,E,E,E,D,D,D,D,DES的保密性,DES的保密性仅取决于对密钥的保密，而算法是公开的。尽管人们在破译DES方面取得了许多进展，但至今仍未能找到比穷举搜索密钥更有效的方法。DES是世界上第一个公认的实用密码算法标准，它曾对密码学的发展做出了重大贡献。目前较为严重的问题是DES的密钥的长度。现在已经设计出来搜索DES密钥的专用芯片。,三重DES(TripleDES),三重DES使用两个密钥，执行三次DES算法。下图中的方框E和D分别表示执行加密和解密算法。因此加密时是E-D-E，解密时是D-E-D。,E,D,E,K1,K2,K1,明文,密文,D,E,D,K1,K2,K1,密文,明文,加密,解密,高级加密标准(AES),高级加密标准AES,高级加密标准(AES),AES的起源AES的设计原则AES算法描述,1.AES的起源,1997年9月，NIST征集AES方案，以替代DES。1999年8月，以下5个方案成为最终候选方案：MARS,RC6,Rijndael,Serpent,Twofish。2000年10月，由比利时的JoanDaemen和VincentRijmen提出的算法最终胜出。（Rijndael读成RainDoll。）http:/www.esat.kuleuven.ac.be/rijmen/rijndael/,2.AES的设计原则,能抵抗所有已知的攻击；在各种平台上易于实现，速度快；设计简单。,Rijndael是一个分组密码算法，其分组长度和密钥长度相互独立，都可以改变。,表1.分组长度和密钥长度的不同取值,3.AES算法的一般描述,RijndaelRound的构成,ByteSubstitution,ByteRotation,MixColumn,+,RoundKey,一般的轮变换,ByteSubstitution,ByteRotation,+,RoundKey,最后一轮的轮变换,3.AES算法加密部分的实现,明文分组和密钥的组织排列方式,Fig1.以明文分组为128bits为例组成的阵列,Fig2.以明文分组（或密钥）为128bits、192bits、256bits为例组成的阵列,一些相关的的术语定义和表示,状态（State）：密码运算的中间结果称为状态。State的表示：状态用以字节为基本构成元素的矩阵阵列来表示，该阵列有4行，列数记为Nb。Nb=分组长度（bits）32Nb可以取的值为4，6，8，对应的分组长度为128，192，256bits。密码密钥（CipherKey）的表示：CipherKey类似地用一个4行的矩阵阵列来表示，列数记为Nk。Nk=密钥长度（bits）32Nk可以取的值为4，6，8，对应的密钥长度为128，192，256bits。,Fig3.当Nb=6时的状态和Nk=4时的密钥布局,Nb=6BlockLength=192bits,Nk=4KeyLength=128bits,Fig4.分组长度和密钥长度均为128bits时的Rijndael加密算法框图,Data/KeyAddition,Rnd0,Rnd1,Rnd8,FinalRnd,KeySchedule,CipherText,Key,PlainText,表2.轮数（Round）的不同取值,用伪代码表示的Rijndael轮变换,一般的轮变换Round(State,RoundKey)ByteSubstitution;ByteRotation;MixColumn;AddRounKey;,结尾轮变换FinalRound(State,RoundKey)ByteSubstituion;ByteRotation;AddRoundKey;,ByteSubstitution(字节替代),ByteSubstitution是一个非线性的字节替代，独立地在每个状态字节上进行运算。它包括两个变换。1.在有限域GF(28)上求乘法逆，00映射到它自身。2.在GF(2)上进行下面的仿射变换：,y011111000 x00y101111100 x11y200111110 x21y300011111x30y410001111x40y511000111x50y611100011x61y711110001x71,Fig6.ByteSubstitution该变换可以用一个256字节的表来实现,取逆仿射变换,ByteRotation(字节移位),在ByteRotation变换中，状态阵列的后3行循环移位不同的偏移量。第1行循环移位C1字节，第2行循环移位C2字节，第3行循环移位C3字节。偏移量C1、C2、C3与分组长度Nb有关，如下表所示：,Fig7.ByteRotation,循环左移1字节,循环左移2字节,循环左移3字节,MixColumn(列混合),将状态的列看作是有限域GF(28)上的多项式a(x)，与多项式c(x)=03x3+01x2+01x+02相乘(模x41)。令b(x)=c(x)a(x)，写成矩阵形式为：,b002030101a0b1=01020301a1b201010203a2b303010102a3,Fig8.MixColumn这一运算作用在每一列上,C(X),2.4AddRoundKey(轮密钥加),将轮密钥与状态按比特异或。轮密钥是通过KeySchedule过程从密码密钥中得到的，轮密钥长度等于分组长度。,A3,3K3,3B3,3(mod2),Fig7.Rijndael加密及解密的标准结构Block,KeyLength=128bits,Plaintext(128bits),ByteSubstitution,MixColumn,Ciphertext(128bits),K0,Ki,i=10,ByteRotation,fori=1to10,Ciphertext(128bits),K10,InvMixColumn,InvByteRotation,InvByteSubstitution,Ki,Plaintext(128bits),i=9,fori=9to0,加密,解密,用伪代码表示的Rijndael加密算法,Rijndael(State,CipherKey)KeyExpansion(CipherKey,ExpandedKey);AddRoundKey(State,ExpandedKey);For(i=1;iRnd;i+)Round(State,ExpandedKey+Nb*i);FinalRound(State,ExpandedKey+Nb*Rnd);,提前进行密钥扩展后的Rijndael加密算法描述,Rijndael(State,ExpandedKey)AddRoundKey(State,ExpandedKey);For(i=1;iRnd;i+)Round(State,ExpandedKey+Nb*i);FinalRound(State,ExpandedKey+Nb*Rnd);,AES的密钥调度密钥调度包括两个部分：密钥扩展和轮密钥选取。,密钥bit的总数分组长度（轮数Round1）例如当分组长度为128bits和轮数Round为10时，轮密钥长度为128(101)1408bits。将密码密钥扩展成一个扩展密钥。从扩展密钥中取出轮密钥：第一个轮密钥由扩展密钥的第一个Nb个4字节字，第二个圈密钥由接下来的Nb个4字节字组成，以此类推。,密钥扩展,+,+,+,ByteSubstitution,ByteRotate,+,Rcon,Wi-4,Wi-3,Wi-2,Wi-1,Wi,ByteSubstituion,ByteRotate,+,Rcons,+,Keyexpansion,4=i4(Rnd+1),imod4=0,imod4!=0,轮密钥选取,轮密钥0,轮密钥1,轮密钥2,AES的解密算法,解密算法与加密算法不同每个阶段均可逆，因此易证解密函授的确可以恢复明文见图5.7，P.121,AES算法的设计原理,GF(28)中乘法使用的多项式是8次不可约多项式列表中的第一个多项式。ByteSubstitution（称为S盒）在设计时考虑到抵抗差分密码