计算机安全与保密4

1、4 对称密钥算法4.1 概述概述4.2 数据加密标准算法数据加密标准算法DES4.3 高级数据加密标准高级数据加密标准AES4.4 联合分组密码联合分组密码4.1 概述n分组密码：向量分组密码：向量x到向量到向量y上的一个映射上的一个映射 ：xy=xy= (x)x=(x0,x1,xN-1), y=(y0,y1,yN-1)n乘积密码：乘积密码：t个函数（密码）个函数（密码）F1,Ft的复合，其中的复合，其中每个每个Fi是一个换位或代替。如转轮机。是一个换位或代替。如转轮机。nLucifer密码的代替密码的代替-移位变换移位变换n乘积密码：代替和简单线性变换来实现混合变换。乘积密码：代替和简单线性

2、变换来实现混合变换。n例：例：ADFGVX乘积密码先造一个乘积密码先造一个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 Z 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

3、 DG XV DG XF FG VG GA AG XGn移位变换：构造一个移位矩阵移位变换：构造一个移位矩阵 约定一个密钥约定一个密钥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第二次加密（移位法）：按密钥字母在字母表中的顺序一列一列写出。第二次加密（移位法）：按密钥字

4、母在字母表中的顺序一列一列写出。n密文：密文：DXGX FFDG GXGG VVVG VGFG GDFA AAXA 4.2 数据加密标准算法DESn背景背景n算法描述算法描述n算法概述：算法概述：Li=Ri-1Ri=Li-1 f(Ri-1, Ki)明文IPR0L0fL1 R0R1 L0 f(R0，K1)Li Ri-1Ri Li-1 f(Ri-1，Ki)L15 R14R15 L14 f(R14，K15)L16 R15R16 L15 f(R15，K16)IP-1密文fffK1K2KiK16nF函数：函数：nE变换变换n按位异或按位异或nS盒代替盒代替nP变换变换Li-1Ri-1E变换S盒代替P变换

5、LiRi密钥移位移位压缩变换密钥密钥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盒代替：对

6、盒代替：对48位中间结果做代替操作。位中间结果做代替操作。n8个小个小S盒，每个有盒，每个有6位输入和位输入和4位输出位输出n设输入设输入为为b1b2b3b4b5b6，则，则b1b6为行号，为行号，b2b3b4b5为列号为列号n例：例：S6的输入的输入110011，行，行11（3），列），列1001（9）处为）处为14，输出为，输出为1110nP变换：换位操作，变换：换位操作，P变换的结果与上一圈的左半变换的结果与上一圈的左半部分异或，称为新的右半部分，开始下一圈部分异或，称为新的右半部分，开始下一圈n逆初始变换逆初始变换IP-1（移位）（移位）举例：设M = 0 x0123456789abc

7、def, K = 0 xfedcba9876543210, 求L1和R1。K: 1111111011011100101110101001100001110110010101000011001000010000 64位PC-1(K): 00001111001100110101010111110101010100110011000011111111 表4.2 56位循环左移: 00011110011001101010101111101010101001100110000111111110 56位K1(PC-2): 111101001111110110011000011001001011011001

8、011010 表4.4 48位M: 0000000100100011010001010110011110001001101010111100110111101111IP(M): 1100110000000000110011001111111111110000101010101111000010101010E(R0) 011110100001010101010101011110100001010101010101E(R0) K1 100011101110100011001101000111101010001100001111S盒代替: 110000011010000011001000100001

9、00P: 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种不同的子密钥，每种

10、出现种不同的子密钥，每种出现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

11、 000010S1:0行行0列：列：141110S2:0行行8列：列：91001S3:0行行2列：列：91001S4:1行行0列：列：131101S5:0行行0列：列：20010S6:0行行8列：列：00000S7:0行行2列：列：20010S8:0行行1列：列：200102.接上边DES算法的第一圈，求L2，R2。K: 00011110011001101010101111101010101001100110000111111110 56位循环左移: 00111100110011010101011111000101010011001100001111111101 56位K2(PC-2): 10

12、0101100101100110100110110110101001010111011001 表4.4 48位M: 1111000010101010111100001010101011011101100001000000110111011010E(R1) 011011111011110000001000000001011011111011110101E(R1) K2 111110011110010110101110110111110010101100101100S盒代替: 00001010011111011001000001111110P变换: 111011110001101100010100

13、01100100R2: 00011111101100011110010011001110L2:4.3 高级数据加密标准AESn背景背景nAES的数学基础的数学基础nAES加密算法描述加密算法描述nAES解密算法解密算法n算法评价算法评价n结论结论背景n现代计算机速度的迅速提高，使得只有现代计算机速度的迅速提高，使得只有56bit密钥的密钥的DES算法的安全性面临着极大的挑战。算法的安全性面临着极大的挑战。n1997年，年，NIST公开征求公开征求AES（Advanced Encryption Standard）作为）作为2001年以后的数据加密标准。年以后的数据加密标准。n1998年年8月，月

14、，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有限域有限域G

15、F(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

16、)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+

17、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 = b

18、7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 xn求乘法逆元求乘法逆元a(x) ：因为：因为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 (

19、x7+ x6 +1)(x+1)+ (x6+ x4 +x3) x7+ x6 +1= (x6+ x4 +x3)(x+1)+(x5+ x3 +1)x6+ x4 +x3 = (x5+ x3 +1) x+(x3+ x)x5+ x3 +1 = (x3+ x) x2 +1扩展的扩展的Euclid算法：算法： 1= (x5+ x3 +1) (x3+ x) x2 (x5+ x3 +1) (x6+ x4 +x3 )+ (x5+ x3+1) x ) x2 = (x5+ x3 +1) (1+ x3)+ (x6+ x4 +x3 ) x2 = (x7+ x6 +1)+ (x6+ x4 +x3)(x+1) (1+ x3)

20、+ (x6+ x4 +x3 ) x2 = (x7+ x6 +1) (1+ x3)+ (x6+ x4 +x3 )(x4 +x3 +x2 +x+1 ) = (x7+ x6 +1) (1+ x3)+ (x8+x4+x3+x+1)+(x7+ x6 +1)(x+1) (x4+x3 +x2 +x+1 ) = (x7+ x6 +1)(x5+ x3 ) + (x8+x4+x3+x+1) (x4 +x3 +x2 +x+1 ) 因此，因此， (x7+ x6 +1)1 mod (x8+x4+x3+x+1) x5+ x3 AES的数学基础(4)n带系数的多项式乘运算带系数的多项式乘运算“ ”：令令a(x)= a3x3

21、+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

22、 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或或256b

23、it，密钥也，密钥也可以分别为可以分别为128bit，192bit或或256bit。n算法有多圈相同的运算，每一圈包括算法有多圈相同的运算，每一圈包括4个步骤：个步骤：n非线性代替（非线性代替（S-盒）盒）n行循环左移（行循环左移（ShiftRow）n列混合变换列混合变换（MixColum）n与扩展密钥相异或与扩展密钥相异或n每一圈的子密钥从扩展密钥中取出每一圈的子密钥从扩展密钥中取出n密钥扩展过程同时应用了非线性变换和循环左移密钥扩展过程同时应用了非线性变换和循环左移n算法定义的所有运算都是在有限域算法定义的所有运算都是在有限域GF(28)上进行的上进行的加密算法概述（2）n算法中进行运算的

24、单位包括：算法中进行运算的单位包括：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代表块长

25、度代表块长度/32，则算，则算法的圈数法的圈数Nr的取值与的取值与Nk和和Nb的关系为：的关系为：n除最后一圈不做列混合除最后一圈不做列混合变换外，每一圈都经过变换外，每一圈都经过4步相同的操作：步相同的操作：NrNb4Nb6Nb8Nk4101214Nk6121214Nk8141414Round(State, RoundKey) ByteSub(State);/S-盒 ShiftRow(State);/行循环左移 MixColumn(State);/列混合变换 AddRoundKey(State, RoundKey); /与扩展密钥相异或一圈变换（1）n非线性代替（非线性代替（S-盒）：包括盒

26、）：包括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行循环左移（行循环

27、左移（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.

28、 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 i，则，则Wordi

29、= Wordi-1 Wordi-Nk ;（i不能被不能被Nk整整除）除）若若Nk | i，则先循环左移，然后查非线性变换表（，则先循环左移，然后查非线性变换表（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 wN

30、b * (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 ke

31、y，例如：当，例如：当Nb6,Nk4时，扩展密钥和各圈子密钥的选择如下：时，扩展密钥和各圈子密钥的选择如下：w0=key0,1,2,3w0=key0,1,2,3w1=key4,5,6,7w1=key4,5,6,7w2=key8,9,10,11w2=key8,9,10,11w3=key12,13,14,15w3=key12,13,14,15w4=w0tempw4=w0tempw5=w1w4w5=w1w4w6=w2w5w6=w2w5w7=w3w6w7=w3w6w8=w4tempw8=w4tempw9=w5w8w9=w5w8加密算法描述n整个算法可以用整个算法可以用 下面的代码表示：下面的代码表示：

32、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算法的每一步都是可逆的算法的每一步都是可逆的 ，因此一，因此一圈的逆过程如下：

33、圈的逆过程如下：InvRound(State, RoundKey) AddRoundKey(State, RoundKey); InvMixColumn(State); InvShiftRow(State); InvByteSub(State);AES解密算法（2）n列混合变换的逆变换列混合变换的逆变换InvMixColumn： s(x)=c-1(x) s(x) 对于对于0jNb，有，有n循环左移的逆变换为循环右移相应的字节数循环左移的逆变换为循环右移相应的字节数AES解密算法（3）n逆逆S-盒：盒： 先做逆仿射变换，然后先做逆仿射变换，然后求求GF(28)上模上模m(x)的乘法逆元，也可以做

34、成的乘法逆元，也可以做成一个查找表（逆一个查找表（逆S-盒）。盒）。算法评价(1)n所有的运算定义在有限所有的运算定义在有限域域GF(28)上，算法执行时除了一上，算法执行时除了一个查表操作外，其它的运算都是简单的异或和移位，运个查表操作外，其它的运算都是简单的异或和移位，运行速度很快。在每一圈运算和密钥扩展中都应用了非线行速度很快。在每一圈运算和密钥扩展中都应用了非线性操作，大大增强了抗差分和线性密码分析能力。性操作，大大增强了抗差分和线性密码分析能力。n轮运算：轮运算：（1）所有操作都是可逆的；）所有操作都是可逆的；（2）每一步对一定攻击都有很强的抵抗能力，）每一步对一定攻击都有很强的抵抗能力，S-盒能抵盒能抵抗差分和线性密码分析，行循环左移能抵抗截断差分抗差分和线性密码分析，行循环左移能抵抗截断差分密码分析及密码分析及Square攻