《分组加密算法》PPT课件.ppt

第7讲 分组密码,它将明文划分成固定的 n 比特的数据组，然后以组为单位，在密钥的控制下进行一系列的线性或非线性的变化而得到密文。这就是分组密码。分组密码一次变换一组数据。分组密码算法的一个重要特点就是：当给定一个密钥后，若明文分组相同，那么所变换出密文分组也相同。分组密码的一个重要优点是不需要同步,分组密码体制,输入,输出,加密算法,密钥,明文,输入,输出,解密算法,密钥,明文,n bit,n bit,n bit,n bit,密文,密文,分组密码的一般设计原理,分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列。,加密算法,解密算法,明文,密文,原来的明文,（x0，,xn-1）,（x0，,xn-1）,（y0，,yn-1）,分组密码的一般设计原理,设计目标在密钥控制下，从一个足够大、足够好的置换子集中简单迅速地选出一个置换，对当前输入的明文数字组进行加密变换；要求：1 分组长度足够大，防止穷举攻击；2 密钥空间足够大，但不能太长，以便于密钥的管理；3 算法要足够复杂，充分实现明文和密钥的扩散；没有简单的关系可寻,DES对称加密技术,DES(Data Encryption Standard)算法是一种用56位密钥来加密64位数据的方法。发明人：IBM公司 W.Tuchman和C.Meyer.基础：1967年美国Horst Feistel提出的理论；产生：美国国家标准局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逆置换表,58 50 42 34 26 18 10 260 52 44 36 28 20 12 462 54 46 38 30 22 14 664 56 48 40 32 24 16 857 49 41 33 25 17 9 159 51 43 35 27 19 11 361 53 45 37 29 21 13 563 55 47 39 31 23 15 7,40 8 48 16 56 24 64 3239 7 47 15 55 23 63 3138 6 46 14 54 22 62 3037 5 45 13 53 21 61 2936 4 44 12 52 20 60 2835 3 43 11 51 19 59 2734 2 42 10 50 18 58 2633 1 41 9 49 17 57 25,IP与IP-1互逆,M=(m1,m2,.),1 2 3 4 5 6 7 8,9 10 11 12 13 14 15 16,17 18 19 20 21 22 23 24,25 26 27 28 29 30 31 32,33 34 35 36 37 38 39 40,41 42 43 44 45 46 47 48,49 50 51 52 53 54 55 56,1 2 3 4 5 6 7 8,9 10 11 12 13 14 15 16,17 18 19 20 21 22 23 24,25 26 27 28 29 30 31 32,33 34 35 36 37 38 39 40,41 42 43 44 45 46 47 48,49 50 51 52 53 54 55 56,IP(M)=(m58,m50)=(m1 1,m1 2,.),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,61 58 45 37 29 21 13 5,63 55 47 39 31 23 15 7,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,34 2 42 10 50 18 58 26,33 1 41 9 49 17 57 25,IP,IP-1,DES的一轮迭代,Li-1（32 bit）,Ri-1（32 bit）,选择扩展运算 E盒,48bit寄存器,48bit寄存器,选择压缩运算 S盒,32bit寄存器,置换运算 P,Ri=Li-1f(Ri-1,ki)（32 bit）,（32 bit）,Li=Ri-1,轮开始：64bit分成左右两半,子密钥Ki（48 bit）,扩展置换 E盒(Expand Box),将输入的32bit块扩展到48bit的输出块；48bit的输出块再分成8个6bit块；,01 02 03 04,05 06 07 08,09 10 11 12,13 14 15 16,17 18 19 20,21 22 23 24,25 26 27 28,29 30 31 32,01 02 03 04,05 06 07 08,09 10 11 12,13 14 15 16,17 18 19 20,21 22 23 24,25 26 27 28,29 30 31 32,32,04,08,12,16,20,24,28,05,09,13,17,21,25,29,01,扩展置换函数E,扩展位,扩展位,固定位,压缩替代 S盒(Substitution Box),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,57 49 41 33 25 17 9,1 58 50 42 34 26 18,10 2 59 51 43 25 27,19 11 3 60 52 44 36,63 55 47 39 31 23 15,7 62 54 46 38 30 22,14 6 61 53 45 37 29,21 13 5 28 20 12 4,14 17 11 24 1 5,3 28 15 6 21 10,23 19 12 4 26 8,16 7 27 20 13 2,41 52 31 37 47 55,30 40 51 45 33 48,44 49 39 56 34 53,46 42 50 36 29 32,置换选择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 属于常规密钥密码体制，是一种分组密码。在加密前，先对整个明文进行分组。每一个组长为 64 bit。然后对每一个 64 bit 二进制数据进行加密处理，产生一组 64 bit 密文数据。最后将各组密文串接起来，即得出整个的密文。使用的密钥为 64 bit（实际密钥长度为 56 bit，有 8 bit 用于奇偶校验)。,DES 加密标准,L0,R0,L1=R0,IP,L2=R1,L15=R14,R1=L0 f(R0,K1),R2=L1 f(R1,K2),R15=L14 f(R14,K15),L16=R15,R16=L15 f(R15,K16),IP1,f,f,f,输出,密文 Y(64 bit),明文 X(64 bit),输入,K16(48 bit),K2(48 bit),K1(48 bit),X0 的左半边(32 bit),X0(64 bit),X0 的右半边(32 bit),R16L16(64 bit),DES 的明显缺点,DES 实际上就是一种单字符替代，而这种字符的长度是 64 bit。也就是说，对于 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(Triple DES),三重 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月，由比利时的Joan Daemen和Vincent Rijmen提出的算法最终胜出。（Rijndael 读成Rain Doll。）http:/www.esat.kuleuven.ac.be/rijmen/rijndael/,2.AES的设计原则,能抵抗所有已知的攻击；在各种平台上易于实现，速度快；设计简单。,Rijndael是一个分组密码算法，其分组长度和密钥长度相互独立，都可以改变。,表 1.分组长度和密钥长度的不同取值,3.AES 算法的一般描述,Rijndael Round的构成,ByteSubstitution,ByteRotation,MixColumn,+,RoundKey,一般的轮变换,ByteSubstitution,ByteRotation,+,RoundKey,最后一轮的轮变换,3.AES 算法加密部分的实现,明文分组和密钥的组织排列方式,Fig 1.以明文分组为128bits为例组成的阵列,Fig 2.以明文分组（或密钥）为128bits、192bits、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 bits,Nk=4Key Length=128 bits,Fig 4.分组长度和密钥长度均为128 bits时的Rijndael加密算法框图,Data/Key Addition,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)上进行下面的仿射变换：,y0 1 1 1 1 1 0 0 0 x0 0y1 0 1 1 1 1 1 0 0 x1 1y2 0 0 1 1 1 1 1 0 x2 1y3 0 0 0 1 1 1 1 1 x3 0y4 1 0 0 0 1 1 1 1 x4 0y5 1 1 0 0 0 1 1 1 x5 0y6 1 1 1 0 0 0 1 1 x6 1y7 1 1 1 1 0 0 0 1 x7 1,Fig 6.ByteSubstitution该变换可以用一个256字节的表来实现,取逆仿射变换,ByteRotation(字节移位),在ByteRotation变换中，状态阵列的后3行循环移位不同的偏移量。第1行循环移位C1字节，第2行循环移位C2字节，第3行循环移位C3字节。偏移量C1、C2、C3与分组长度Nb有关，如下表所示：,Fig 7.ByteRotation,循环左移1字节,循环左移2字节,循环左移3字节,MixColumn(列混合),将状态的列看作是有限域GF(28)上的多项式a(x)，与多项式c(x)=03 x3+01 x2+01 x+02相乘(模x41)。令b(x)=c(x)a(x)，写成矩阵形式为：,b0 02 03 01 01 a0 b1=01 02 03 01 a1 b2 01 01 02 03 a2 b3 03 01 01 02 a3,Fig 8.MixColumn这一运算作用在每一列上,C(X),2.4 AddRoundKey(轮密钥加),将轮密钥与状态按比特异或。轮密钥是通过Key Schedule过程从密码密钥中得到的，轮密钥长度等于分组长度。,A3,3 K3,3 B3,3(mod 2),Fig 7.Rijndael加密及解密的标准结构Block,Key Length=128 bits,Plaintext(128 bits),ByteSubstitution,MixColumn,Ciphertext(128 bits),K0,Ki,i=10,ByteRotation,for i=1 to 10,Ciphertext(128 bits),K10,InvMixColumn,InvByteRotation,InvByteSubstitution,Ki,Plaintext(128 bits),i=9,for i=9 to 0,加密,解密,用伪代码表示的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,+,Key expansion,4=i 4(Rnd+1),i mod 4=0,i mod 4!=0,轮密钥选取,轮密钥0,轮密钥1,轮密钥2,AES的解密算法,解密算法与加密算法不同每个阶段均可逆，因此易证解密函授的确可以恢复明文见图5.7，P.121,AES 算法的设计原理,GF(28)中乘法使用的多项式是8次不可约多项式列表中的第一个多项式。ByteSubstitution（称为S盒）在设计时考虑到抵抗差分密码分析、线性密码分析的要求，应满足以下条件：1.可逆性；2.输入比特的线性组合与输出比特的组合之间的最大非平凡相关性的极小化；3.异或差分表中最大非平凡值的极小化；4.GF(28)中代数表示的复杂性；5.描述的简单性。,满足前3条准则的S盒的构造方法已被给出，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倍数的任意分组长度。圈数和循环移位偏移量作为参数，要重新定义。,关于有限域G(28)的一些解释,G(28)可看为8位二进制比特串的集合直观上有限域的运算可为密码算法的实现带来方便只有满足一些规则后，G(28)才是有限域（参加第4章，p.95）,G(28)上的运算,加法按位异或乘法可通过对多个中间结果的移位运算和异或一个特定的比特串（比如00011011）实现。,Cryptanalysis,Some common symmetric-key cryptographic algorithms.,