信息安全基础4课件.pptx

4 对称密钥算法4.1 概述概述4.2 数据加密标准算法数据加密标准算法DES4.3 高级数据加密标准高级数据加密标准AES4.4 联合分组密码联合分组密码4.1 概述n分组密码：向量分组密码：向量x到向量到向量y上的一个映射上的一个映射：x xy y=(x)x=(x0,x1,xN-1),y=(y0,y1,yN-1)n乘积密码：乘积密码：t个函数（密码）个函数（密码）F1,Ft的复合，其的复合，其中每个中每个Fi是一个换位或代替。如转轮机。是一个换位或代替。如转轮机。nLucifer密码的代替密码的代替-移位变换移位变换n乘积密码：代替和简单线性变换来实现混合变换。乘积密码：代替和简单线性变换来实现混合变换。n例：例：ADFGVX乘积密码乘积密码1.先造一个先造一个6*6方阵方阵 A D F G V X A K 2 W R 1 F D 9 B 6 C L 5 F Q 7 J P G X G E V Y 3 A N V 8 O D H 0 2 X U 4 I S T M n明文：明文：P R O D U C T C I P H E R Sn变换（代替）：（变换（代替）：（行标，列标）行标，列标）明文明文 P FG （把原来明文的一个字母用（把原来明文的一个字母用 R AG 两个字母行、列来代替）两个字母行、列来代替）n第一次加密密文：第一次加密密文：FG AG VD VF XA DG XV DG XF FG VG GA AG XG2.移位变换：构造一个移位矩阵移位变换：构造一个移位矩阵,约定一个密钥约定一个密钥n密钥：密钥：DEUTSCHn把第一次加密的密文按行写入把第一次加密的密文按行写入4*7矩阵，前边加上密钥，密钥字母按其在字矩阵，前边加上密钥，密钥字母按其在字母表中出现的次序编号。母表中出现的次序编号。D E U T S C H 2 3 7 6 5 1 4 F G A G V D V F X A D G X V D G X F F G V G G A A G X Gn第二次加密（移位法）：按密钥字母在字母表中的顺序一列一列写出。第二次加密（移位法）：按密钥字母在字母表中的顺序一列一列写出。n密文：密文：DXGX FFDG GXGG VVVG VGFG GDFA AAXA 4.2 数据加密标准算法DESn背景背景n算法描述算法描述n算法概述：算法概述：Li=Ri-1Ri=Li-1 f(Ri-1,Ki)nF函数：函数：nE变换变换n按位异或按位异或nS盒代替盒代替nP变换变换密钥PC-1C0D0循环左移循环左移C1D1PC-2循环左移循环左移C2D2PC-2PC-2循环左移循环左移C16D16K1K2K16密钥变换：n初始变换初始变换IP：在第一圈之前（对明文移位）：在第一圈之前（对明文移位）n密钥变换：密钥变换：nPC-1：64位密钥去掉位密钥去掉8的倍数位的倍数位n循环左移：循环左移：56位分成各位分成各28位的两部分，分别循环左移位的两部分，分别循环左移1或或2位位nPC-2：从：从56位中选出位中选出48位，为本圈子密钥位，为本圈子密钥n扩展变换扩展变换E：将右半部分从：将右半部分从32位扩展到位扩展到48位位nS盒代替：对盒代替：对48位中间结果做代替操作。位中间结果做代替操作。n8个小个小S盒，每个有盒，每个有6位输入和位输入和4位输出位输出n设输入为设输入为b1b2b3b4b5b6，则，则b1b6为行号，为行号，b2b3b4b5为列号为列号n例：例：S6的输入的输入110011，行，行11（3），列），列1001（9）处为）处为14，输出为，输出为1110nP变换：换位操作，变换：换位操作，P变换的结果与上一圈的左半变换的结果与上一圈的左半部分异或，成为新的右半部分，开始下一圈部分异或，成为新的右半部分，开始下一圈n逆初始变换逆初始变换IP-1（移位）（移位）举例：设M=0 x0123456789abcdef,K=0 xfedcba9876543210,求L1和R1。K:1111111011011100101110101001100001110110010101000011001000010000 64位PC-1(K):00001111001100110101010111110101010100110011000011111111 表4.2 56位循环左移:00011110011001101010101111101010101001100110000111111110 56位K1(PC-2):111101001111110110011000011001001011011001011010 表4.4 48位M:0000000100100011010001010110011110001001101010111100110111101111IP(M):1100110000000000110011001111111111110000101010101111000010101010E(R0)011110100001010101010101011110100001010101010101E(R0)K1 100011101110100011001101000111101010001100001111S盒代替:11000001101000001100100010000100P变换:00010001100001001100000100100101R1:11011101100001000000110111011010L1:n加密过程：加密过程：L0R0IP()FOR i=1 TO 16Li Ri-1Ri Li-1 f(Ri-1,Ki)IP-1(R16L16)n解密过程：解密过程：R16L16 IP()FOR i=16 TO 1Ri-1 LiLi-1 Ri f(Li,Ki)IP-1(L0R0)nDES的安全性的安全性n弱密钥弱密钥n弱密钥：每一圈的子密钥都相同。共弱密钥：每一圈的子密钥都相同。共4个。个。n半弱密钥：只产生半弱密钥：只产生2种不同的子密钥，每种出现种不同的子密钥，每种出现8次。共次。共12个。个。n可能弱密钥：只产生可能弱密钥：只产生4种不同的子密钥，每种出现种不同的子密钥，每种出现4次。共次。共48个。个。n互补密钥互补密钥n代数结构代数结构n密钥长度密钥长度n圈数圈数nS盒的设计盒的设计练习n1.已知已知DES算法中算法中S盒的输入为盒的输入为0 x010101010102，求经过，求经过S盒代替后的输出结果。盒代替后的输出结果。n答案：答案：1110 1001 1001 1101 0010 0000 0010 0010n输入输入:000000 010000 000100 000001 000000 010000 000100 000010S1:0行行0列：列：141110S2:0行行8列：列：91001S3:0行行2列：列：91001S4:1行行0列：列：131101S5:0行行0列：列：20010S6:0行行8列：列：00000S7:0行行2列：列：20010S8:0行行1列：列：200104.3 高级数据加密标准AESn背景背景nAES的数学基础的数学基础nAES加密算法描述加密算法描述nAES解密算法解密算法n算法评价算法评价n结论结论背景n现代计算机速度的迅速提高，使得只有现代计算机速度的迅速提高，使得只有56bit密钥的密钥的DES算法的安全性面临着极大的挑战。算法的安全性面临着极大的挑战。n1997年，年，NIST公开征求公开征求AES（Advanced Encryption Standard）作为）作为2001年以后的数据加密标准。年以后的数据加密标准。n1998年年8月，月，AES召开第一次候选会，确定召开第一次候选会，确定15个算法入围。个算法入围。n1999年年3月，月，AES召开第二次候选会，有召开第二次候选会，有5个算法入围个算法入围（MARS,RC6,Rijndael,Serpent和和Twofish）。）。n2000年年10月，月，NIST选出由比利时的选出由比利时的Joan Daemen和和Vincent Rijmen提交的提交的Rijndael算法作为算法作为AES。n2001年夏天，年夏天，NIST颁布新的信息处理标准（颁布新的信息处理标准（FIPS），将），将Rijndael算法作为算法作为AES。AES的数学基础(1)n有限域有限域GF(28)上定义了上定义了4种运算：种运算：“+”、“”、“X”和带系数的多项式乘运算和带系数的多项式乘运算“”。n对字节对字节b，用多项式表示为：，用多项式表示为：b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0n“+”运算：两个字节相加，相当于字节的每一位简单异运算：两个字节相加，相当于字节的每一位简单异或。或。n例：例：5783d4(57)16=(01010111)2x6+x4+x2+x+1(83)16=(10000011)2 x7+x+15783(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2(11010100)2(d4)16AES的数学基础(2)n“”运算：选择一个不可约多项式：运算：选择一个不可约多项式：m(x)=x8+x4+x3+x+1，“”运算为两多项式相乘后进行模运算为两多项式相乘后进行模m(x)的运算。的运算。n例：例：57 83c1(57)16=(01010111)2x6+x4+x2+x+1(83)16=(10000011)2 x7+x+157 83(x6+x4+x2+x+1)(x7+x+1)mod(x8+x4+x3+x+1)=x13+x11+x9+x8+x7+x7+x5+x3+x2+x+x6+x4+x2+x+1)mod(x8+x4+x3+x+1)=(x13+x11+x9+x8+x6+x5+x4+x3+1)mod(x8+x4+x3+x+1)x7+x6+1(11000001)2(c1)16(x13+x11+x9+x8+x6+x5+x4+x3+1)mod(x8+x4+x3+x+1):x5+x3x8+x4+x3+x+1x13+x11+x9+x8+x6+x5+x4+x3+1x13 +x9+x8+x6+x5x7+x6+1x11+x4+x3+1x11+x7+x6+x4+x3AES的数学基础(3)n“X”运算：运算：b X=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 xn求乘法逆元：因为求乘法逆元：因为m(x)是是GF(28)上的不可约多项式，所上的不可约多项式，所以对于任意以对于任意b(x)，都可以用扩展的，都可以用扩展的Euclid算法求算法求a(x)，使，使得得 a(x)b(x)+c(x)m(x)=1 因而因而 a(x)b(x)mod m(x)=1 即即 b1(x)mod m(x)=a(x),m(x)=x8+x4+x3+x+1例：求(x7+x6+1)关于模m(x)x8+x4+x3+x+1的乘法逆元。辗转相除：辗转相除：x8+x4+x3+x+1(x 7+x 6+1)(x+1)+(x 6+x 4+x 3)x 7+x 6+1=(x 6+x 4+x 3)(x+1)+(x 5+x 3+1)x 6+x 4+x 3=(x 5+x 3+1)x+(x 3+x)x 5+x 3+1=(x 3+x)x 2+1扩展的扩展的Euclid算法：算法：1=(x 5+x 3+1)(x 3+x)x 2 (x 5+x 3+1)(x 6+x 4+x 3)+(x 5+x 3+1)x)x 2 =(x 5+x 3+1)(1+x 3)+(x 6+x 4+x 3)x 2 =(x 7+x 6+1)+(x 6+x 4+x 3)(x+1)(1+x 3)+(x 6+x 4+x 3)x 2 =(x 7+x 6+1)(1+x 3)+(x 6+x 4+x 3)(x 4+x 3+x 2+x+1)=(x 7+x 6+1)(1+x 3)+(x 8+x 4+x 3+x+1)+(x 7+x 6+1)(x+1)(x 4+x 3+x 2+x+1)=(x 7+x 6+1)(x 5+x 3)+(x 8+x 4+x 3+x+1)(x 4+x 3+x 2+x+1)因此，因此，(x 7+x 6+1)1 mod(x 8+x 4+x 3+x+1)x 5+x 3 AES的数学基础(4)n带系数的多项式乘运算带系数的多项式乘运算“”：令令a(x)=a3x3+a2x2+a1x+a0,b(x)=b3x3+b2x2+b1x+b0,其乘积其乘积 c(x)=a(x)b(x)=c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0其中，其中，c0=a0 b0 c1=a1 b0 a0 b1 c2=a2 b0 a1 b1 a0 b2 c3=a3 b0 a2 b1 a1 b2 a0 b3 c4=a3 b1 a2 b2 a1 b3 c5=a3 b2 a2 b3 c6=a3 b3对（对（x4+1）取模得）取模得d(x):d(x)=a(x)b(x)=d3x3+d2x2+d1x+d0其中，其中，d0=a0 b0 a3 b1 a2 b2 a1 b3 d1=a1 b0 a0 b1 a3 b2 a2 b3 d2=a2 b0 a1 b1 a0 b2 a3 b3 d3=a3 b0 a2 b1 a1 b2 a0 b3注意：注意：xi mod(x4+1)=xi mod 4AES加密算法描述n加密算法概述加密算法概述n一圈变换一圈变换n密钥扩展密钥扩展n加密算法描述加密算法描述加密算法概述（1）nAES算法与以往的基于算法与以往的基于Feistel网的密码（如网的密码（如DES）不同，）不同，算法的每一步都是可逆的。算法的每一步都是可逆的。n算法的明文块长可以为算法的明文块长可以为128bit，192bit或或256bit，密钥也，密钥也可以分别为可以分别为128bit，192bit或或256bit。n算法有多圈相同的运算，每一圈包括算法有多圈相同的运算，每一圈包括4个步骤：个步骤：n非线性代替（非线性代替（S-盒）盒）n行循环左移（行循环左移（ShiftRow）n列混合变换（列混合变换（MixColum）n与扩展密钥相异或与扩展密钥相异或n每一圈的子密钥从扩展密钥中取出每一圈的子密钥从扩展密钥中取出n密钥扩展过程同时应用了非线性变换和循环左移密钥扩展过程同时应用了非线性变换和循环左移n算法定义的所有运算都是在有限域算法定义的所有运算都是在有限域GF(28)上进行的上进行的加密算法概述（2）n算法中进行运算的单位包括：算法中进行运算的单位包括：n1个字节个字节n1列列n1行行n用字节数组表示的整个加密块用字节数组表示的整个加密块n加密块数组中，加密块数组中，n可以是可以是3，5，7，所代表的加密块分别表示，所代表的加密块分别表示128bit，192bit和和256bit。ai,ja0,ja1,ja2,ja3,jai,0ai,1ai,3a0,2a0,3a1,2a1,3a2,2a2,3a0,0a0,1a1,0a1,1a2,0a2,1a3,0a3,1a3,2a3,3a0,na1,na2,na3,n加密算法概述（3）n令令Nr代表算法的圈数，代表算法的圈数，Nk代表密钥长度代表密钥长度/32，Nb代表块长度代表块长度/32，则算，则算法的圈数法的圈数Nr的取值与的取值与Nk和和Nb的关系为：的关系为：n除最后一圈不做列混合除最后一圈不做列混合变换外，每一圈都经过变换外，每一圈都经过4步相同的操作：步相同的操作：NrNb4Nb6Nb8Nk4101214Nk6121214Nk8141414Round(State,RoundKey)ByteSub(State);/S-盒 ShiftRow(State);/行循环左移 MixColumn(State);/列混合变换 AddRoundKey(State,RoundKey);/与扩展密钥相异或一圈变换（1）n非线性代替（非线性代替（S-盒）：包括盒）：包括2步步n在在GF(28)上求每个字节关于模上求每个字节关于模m(x)的乘法逆元素，的乘法逆元素，00的逆的逆元定义为元定义为00；(000110001163,01011111007c)n应用应用GF(2)上的一个仿射变换：上的一个仿射变换：一圈变换（2）n每个字节每个字节aij经过以上经过以上2步变换后，记为步变换后，记为bij。n可以将每个可能的可以将每个可能的aij值对应的值对应的bij值制成表格，通过查表值制成表格，通过查表的方式来实现的方式来实现S-盒代替，见下表。其中盒代替，见下表。其中xy代表代表1个个字节的字节的16进制表示。进制表示。一圈变换（3）n行循环左移（行循环左移（ShiftRow）：每一）：每一行以字节为单位循环左移，左移行以字节为单位循环左移，左移的字节数见右表。因此，第的字节数见右表。因此，第1行行不移位，第不移位，第2行左移行左移1个字节个字节n列混合变换（列混合变换（Mixcolumn）：对）：对每一列中每个字节每一列中每个字节a(x)，令，令b(x)=c(x)a(x)，其中，其中c(x)为：为：c(x)=03x3+01x2+01x+02n与扩展密钥相异或：与扩展密钥相异或：aij kijbijNbC0C1C2C3401236012380134一圈变换（4）n一圈结构图：一圈结构图：Step1.ByteSub(State)Step2.ShiftRow(State)Step3.MixColumn(State)Step4.AddRoundKey(State,RoundKey)StateS-盒行循环左移c(x)AARoundKeyRound(State,RoundKey)密钥扩展（1）n扩展密钥是一个以扩展密钥是一个以4字节大小为单位字节大小为单位(用用Word表示表示)的线的线性数组。当性数组。当Nk大于大于6的时候有一点不同。开始的时候有一点不同。开始Nk个个Word是加密用的密钥，以后每个是加密用的密钥，以后每个Word通过对通过对K实行变换得到。实行变换得到。n当当Nk6时，时，若若Nk mod i 0，则，则Wordi=Wordi-1 Wordi-Nk;（i不能被不能被Nk整除）整除）若若Nk mod i0，则先循环左移，然后查非线性变换表（，则先循环左移，然后查非线性变换表（S-盒），盒），之后再与常量之后再与常量Rconi/Nk异或，其中：异或，其中：Rconi=(RCi,00,00,00)，RC1=1，RCi=x(RCi-1)=x(i-1)。最后，与。最后，与Wordi-Nk异或。异或。n当当Nk8时，若时，若i mod Nk=4，则先查非线性变换表，再，则先查非线性变换表，再与与Wordi-Nk异或。异或。密钥扩展的伪代码：KeyExpansion(byte key4*Nk,word wNb*(Nr+1),Nk)for(i=0;i Nk;i+)wi=wordkey4*i,key4*i+1,key4*i+2,key4*i+3;for(i=Nk;i Nb*(Nr+1);i+)word temp=wi-1;if(i%Nk=0)temp=SubWord(RotWord(temp)Rconi/Nk;else if(Nk=8 and i%Nk=4)temp=SubWord(temp);S盒盒wi=wi-Nk temp;异或异或密钥扩展（2）n可以从扩展密钥中选择可以从扩展密钥中选择Round key，例如：当，例如：当Nb6,Nk4时，扩展密钥和各圈子密钥的选择如下：时，扩展密钥和各圈子密钥的选择如下：加密算法描述n整个算法可以用整个算法可以用 下面的代码表示：下面的代码表示：Rijndael(State,CipherKey)KeyExpansion(CipherKey,ExpandedKey);/扩展密钥扩展密钥AddRoundKey(State,ExpandedKey);/与扩展密钥异或与扩展密钥异或for(i=1;iNr;i+)Round(State,ExpandedKey+Nb*i);每一圈每一圈FinalRound(State,ExpandedKey+Nb*Nr);/最后一圈不做列混合变最后一圈不做列混合变换换AES解密算法（1）n由于由于Rijndael算法的每一步都是可逆的算法的每一步都是可逆的，因此一，因此一圈的逆过程如下：圈的逆过程如下：InvRound(State,RoundKey)AddRoundKey(State,RoundKey);InvMixColumn(State);InvShiftRow(State);InvByteSub(State);AES解密算法（2）n列混合变换的逆变换列混合变换的逆变换InvMixColumn：s(x)=c-1(x)s(x)对于对于0cNb，有，有n循环左移的逆变换为循环右移相应的字节数循环左移的逆变换为循环右移相应的字节数AES解密算法（3）n逆逆S-盒：盒：先做逆仿射变换，然后求先做逆仿射变换，然后求GF(28)上模上模m(x)的乘法逆元，也可以做成的乘法逆元，也可以做成一个查找表（逆一个查找表（逆S-盒）。盒）。算法评价(1)n所有的运算定义在有限域所有的运算定义在有限域GF(28)上，算法执行时除了一上，算法执行时除了一个查表操作外，其它的运算都是简单的异或和移位，运个查表操作外，其它的运算都是简单的异或和移位，运行速度很快。在每一圈运算和密钥扩展中都应用了非线行速度很快。在每一圈运算和密钥扩展中都应用了非线性操作，大大增强了抗差分和线性密码分析能力。性操作，大大增强了抗差分和线性密码分析能力。n轮运算：轮运算：（1）所有操作都是可逆的；）所有操作都是可逆的；（2）每一步对一定攻击都有很强的抵抗能力，）每一步对一定攻击都有很强的抵抗能力，S-盒能抵盒能抵抗差分和线性密码分析，行循环左移能抵抗截断差分抗差分和线性密码分析，行循环左移能抵抗截断差分密码分析及密码分析及Square攻击，列混合达到了扩散的目的；攻击，列混合达到了扩散的目的；（3）能在广泛的硬件平台上高效快速地执行；）能在广泛的硬件平台上高效快速地执行；（4）每一步操作都易于描述。）每一步操作都易于描述。算法评价(2)n密钥扩展：密钥扩展：（1）非线性操作防止了仅仅由密钥的差分而导致每一圈子）非线性操作防止了仅仅由密钥的差分而导致每一圈子密钥的差分；密钥的差分；（2）密钥扩展产生的效果使每一圈子密钥都不同；）密钥扩展产生的效果使每一圈子密钥都不同；（3）有效地抵抗密钥相关分析及已知部分密钥的分析；）有效地抵抗密钥相关分析及已知部分密钥的分析；（4）消除了每圈中以及圈与圈之间的对称性；）消除了每圈中以及圈与圈之间的对称性；（5）运行速度快，易于描述。）运行速度快，易于描述。n抵抗常见攻击：研究表明，抵抗常见攻击：研究表明，AES算法能够抵抗差分和线算法能够抵抗差分和线性密码分析、截断差分分析、性密码分析、截断差分分析、Square攻击和相关密钥分攻击和相关密钥分析等攻击方法；没有弱密钥，因此对密钥的选择没有限析等攻击方法；没有弱密钥，因此对密钥的选择没有限制；最有效的攻击方法是密钥穷举攻击，而这对于二十制；最有效的攻击方法是密钥穷举攻击，而这对于二十年内的计算能力是不可能的。年内的计算能力是不可能的。结论nRijndael 算法集高安全性、高性能、高效率、易实现及伸缩性强于算法集高安全性、高性能、高效率、易实现及伸缩性强于一身，能应用于广泛的计算环境，密钥建立高效且灵活。一身，能应用于广泛的计算环境，密钥建立高效且灵活。n很低的存储要求，使之在有空间限制的环境中执行。很低的存储要求，使之在有空间限制的环境中执行。n能抵抗各种常用的攻击方法。能抵抗各种常用的攻击方法。n密钥和块长都设计得很灵活，在圈数选择方面能提供一定的灵活性。密钥和块长都设计得很灵活，在圈数选择方面能提供一定的灵活性。n圈运算对指令级并行很具潜力。圈运算对指令级并行很具潜力。n加密的逆运算有一些限制。加密的逆运算有一些限制。n在智能卡上解密过程相对加密过程难于执行，需要更多的代码和循在智能卡上解密过程相对加密过程难于执行，需要更多的代码和循环。环。n对于软件，加密和解密需要不同的代码和查找表。对于软件，加密和解密需要不同的代码和查找表。n对于用硬件来实施加密和解密，解密只能部分地重用加密过程用到对于用硬件来实施加密和解密，解密只能部分地重用加密过程用到的电路。的电路。4.4 联合分组密码n多重加密：使用一个算法、多个密钥将相同的明多重加密：使用一个算法、多个密钥将相同的明文加密多次文加密多次n串联：使用不同的算法、多个密钥将相同的明文串联：使用不同的算法、多个密钥将相同的明文加密多次加密多次1、有时候读书是一种巧妙地避开思考的方法。3月-233月-23Wednesday,March 29,20232、阅读一切好书如同和过去最杰出的人谈话。19:34:5119:34:5119:343/29/2023 7:34:51 PM3、越是没有本领的就越加自命不凡。3月-2319:34:5119:34Mar-2329-Mar-234、越是无能的人，越喜欢挑剔别人的错儿。19:34:5119:34:5119:34Wednesday,March 29,20235、知人者智，自知者明。胜人者有力，自胜者强。3月-233月-2319:34:5119:34:51March 29,20236、意志坚强的人能把世界放在手中像泥块一样任意揉捏。29 三月 20237:34:51 下午19:34:513月-237、最具挑战性的挑战莫过于提升自我。三月 237:34 下午3月-2319:34March 29,20238、业余生活要有意义，不要越轨。2023/3/29 19:34:5119:34:5129 March 20239、一个人即使已登上顶峰，也仍要自强不息。7:34:51 下午7:34 下午19:34:513月-2310、你要做多大的事情，就该承受多大的压力。3/29/2023 7:34:51 PM19:34:5129-3月-2311、自己要先看得起自己，别人才会看得起你。3/29/2023 7:34 PM3/29/2023 7:34 PM3月-233月-2312、这一秒不放弃，下一秒就会有希望。29-Mar-2329 March 20233月-2313、无论才能知识多么卓著，如果缺乏热情，则无异纸上画饼充饥，无补于事。Wednesday,March 29,202329-Mar-233月-2314、我只是自己不放过自己而已，现在我不会再逼自己眷恋了。3月-2319:34:5129 March 202319:34谢谢大家谢谢大家