信息安全基础4

1、4 对称密钥算法 4.1 概述概述 4.2 数据加密标准算法数据加密标准算法DES 4.3 高级数据加密标准高级数据加密标准AES 4.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乘积密码：代替和简单线性变换来实现混合变

2、换。乘积密码：代替和简单线性变换来实现混合变换。 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 S n变换（代替）：（变换（代替）：（行标，列标）行标，列标） 明文明文 P FG （把原来明文的一个字母用（把原来明文的一个字母用 R AG 两个字母行、列来代替）两个字母行、列来代替） n第一次加密密文：第一次

3、加密密文：FG AG VD VF XA DG XV DG XF FG VG GA AG XG 2. 移位变换：构造一个移位矩阵移位变换：构造一个移位矩阵, 约定一个密钥约定一个密钥 n密钥：密钥：DEUTSCH n把第一次加密的密文按行写入把第一次加密的密文按行写入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 G n第二次加密（移位法）：按密钥字母在字母

4、表中的顺序一列一列写出。第二次加密（移位法）：按密钥字母在字母表中的顺序一列一列写出。 n密文：密文：DXGX FFDG GXGG VVVG VGFG GDFA AAXA 4.2 数据加密标准算法DES n背景背景 n算法描述算法描述 n算法概述：算法概述： Li=Ri-1 Ri=Li-1 f(Ri-1, Ki) 明 文 IP变换 L0R0 +f L1=R0R1=L0 f(R0, K1) L15=R14 f + K1 R16=L15 f(R15, K16) R15=L14 f(R14, K15) L16=R15 K16 IP-1变换 密 文 + + + f+K2 Li=Ri-1 Ri=Li-1

5、 f(Ri-1, Ki) + f+Ki+1 nF函数：函数： nE变换变换 n按位异或按位异或 nS盒代替盒代替 nP变换变换 Li-1Ri-1 E变换 S盒代替 P变换 LiRi 密钥 移位移位 压缩变换 密钥 密钥 PC-1 C0D0 循环左移循环左移 C1D1 PC-2 循环左移循环左移 C2D2 PC-2 PC-2 循环左移循环左移 C16D16 K1 K2 K16 密钥变换： n初始变换初始变换IP：在第一圈之前（对明文移位）：在第一圈之前（对明文移位） n密钥变换：密钥变换： nPC-1：64位密钥去掉位密钥去掉8的倍数位的倍数位 n循环左移：循环左移：56位分成各位分成各28位的

6、两部分，分别循环左移位的两部分，分别循环左移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，输出为，输出为1110 nP变换：换位操作

7、，变换：换位操作，P变换的结果与上一圈的左半变换的结果与上一圈的左半 部分异或，成为新的右半部分，开始下一圈部分异或，成为新的右半部分，开始下一圈 n逆初始变换逆初始变换IP-1（移位）（移位） 举例：设M = 0 x0123456789abcdef, K = 0 xfedcba9876543210, 求L1 和R1。 K: 11111110 11011100 10111010 10011000 01110110 01010100 00110010 00010000 64位 PC-1(K): 00001111 00110011 01010101 11110101 01010011 001100

8、00 11111111 表4.2 56位 循环左移: 00011110 01100110 10101011 11101010 10100110 01100001 11111110 56位 K1(PC-2): 111101 001111 110110 011000 011001 001011 011001 011010 表4.4 48位 M: 00000001 00100011 01000101 01100111 10001001 10101011 11001101 11101111 IP(M): 11001100 00000000 11001100 11111111 11110000 1010

9、1010 11110000 10101010 E(R0) 011110 100001 010101 010101 011110 100001 010101 010101 E(R0) K1 100011 101110 100011 001101 000111 101010 001100 001111 S盒代替: 11000001 10100000 11001000 10000100 P变换: 00010001 10000100 11000001 00100101 R1: 11011101 10000100 00001101 11011010 L1: n加密过程：加密过程： L0R0IP() FO

10、R i=1 TO 16 Li Ri-1 Ri Li-1 f(Ri-1,Ki) IP-1(R16L16) n解密过程：解密过程： R16L16 IP() FOR i=16 TO 1 Ri-1 Li Li-1 Ri f(Li,Ki) IP-1(L0R0) nDES的安全性的安全性 n弱密钥弱密钥 n弱密钥：每一圈的子密钥都相同。共弱密钥：每一圈的子密钥都相同。共4个。个。 n半弱密钥：只产生半弱密钥：只产生2种不同的子密钥，每种出现种不同的子密钥，每种出现8次。共次。共12个。个。 n可能弱密钥：只产生可能弱密钥：只产生4种不同的子密钥，每种出现种不同的子密钥，每种出现4次。共次。共48 个。个。

11、 n互补密钥互补密钥 n代数结构代数结构 n密钥长度密钥长度 n圈数圈数 nS盒的设计盒的设计 练习 n1.已知已知DES算法中算法中S盒的输入为盒的输入为0 x010101010102，求经过，求经过 S盒代替后的输出结果。盒代替后的输出结果。 n答案：答案：1110 1001 1001 1101 0010 0000 0010 0010 n输入输入: 000000 010000 000100 000001 000000 010000 000100 000010 S1:0行行0列：列：141110 S2:0行行8列：列：91001 S3:0行行2列：列：91001 S4:1行行0列：列：131

12、101 S5:0行行0列：列：20010 S6:0行行8列：列：00000 S7:0行行2列：列：20010 S8:0行行1列：列：20010 4.3 高级数据加密标准AES n背景背景 nAES的数学基础的数学基础 nAES加密算法描述加密算法描述 nAES解密算法解密算法 n算法评价算法评价 n结论结论 背景 n现代计算机速度的迅速提高，使得只有现代计算机速度的迅速提高，使得只有56bit密钥的密钥的DES 算法的安全性面临着极大的挑战。算法的安全性面临着极大的挑战。 n1997年，年，NIST公开征求公开征求AES（Advanced Encryption Standard）作为）作为20

13、01年以后的数据加密标准。年以后的数据加密标准。 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），将

14、），将 Rijndael算法作为算法作为AES。 AES的数学基础(1) n有限域有限域GF(28)上定义了上定义了4种运算：种运算：“+”、 “”、 “ X”和和 带系数的多项式乘运算带系数的多项式乘运算“ ”。 n对字节对字节b，用多项式表示为：，用多项式表示为： b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0 n“+”运算：两个字节相加，相当于字节的每一位简单异或。运算：两个字节相加，相当于字节的每一位简单异或。 n例：例：5783d4 (57)16=(01010111)2x6+x4+x2+x+1 (83)16=(10000011)2 x7+x+1 5783 (

15、x6+x4+x2+x+1)+(x7+x+1)= x7 +x6+x4+x2 (11010100)2 (d4)16 AES的数学基础(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+1 57 83 (x6+x4+x2+x+1) (x7+x+1) mod (x8+x4+x3+x+1) = x13 + x11 + x9 + x8

16、 + 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 + x3 x8+x4+x3+x+1 x13 + x11 + x9 + x8 + x6 + x5+x4+x3+1 x13 + x9 + x8 + x6 + x5 x7+ x6

17、 +1 x11 + x4+x3+1 x11 + x7+ x6+ x4+x3 AES的数学基础(3) n“ X”运算：运算： b X = b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x n求乘法逆元：因为求乘法逆元：因为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 即即 b 1(x) mod m(x) = a(x) , m(x) = x8+x

18、4+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

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

20、 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 其中，

21、其中， 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 b

22、3 注意：注意： xi mod (x4+1) = xi mod 4 AES加密算法描述 n加密算法概述加密算法概述 n一圈变换一圈变换 n密钥扩展密钥扩展 n加密算法描述加密算法描述 加密算法概述（1） nAES算法与以往的基于算法与以往的基于Feistel网的密码（如网的密码（如DES）不同，）不同， 算法的每一步都是可逆的。算法的每一步都是可逆的。 n算法的明文块长可以为算法的明文块长可以为128bit，192bit或或256bit，密钥也，密钥也 可以分别为可以分别为128bit，192bit或或256bit。 n算法有多圈相同的运算，每一圈包括算法有多圈相同的运算，每一圈包括4个步骤：

23、个步骤： n非线性代替（非线性代替（S-盒）盒） n行循环左移（行循环左移（ShiftRow） n列混合变换（列混合变换（MixColum） n与扩展密钥相异或与扩展密钥相异或 n每一圈的子密钥从扩展密钥中取出每一圈的子密钥从扩展密钥中取出 n密钥扩展过程同时应用了非线性变换和循环左移密钥扩展过程同时应用了非线性变换和循环左移 n算法定义的所有运算都是在有限域算法定义的所有运算都是在有限域GF(28)上进行的上进行的 加密算法概述（2） n算法中进行运算的单位包括：算法中进行运算的单位包括： n1个字节个字节 n1列列 n1行行 n用字节数组表示的整个加密块用字节数组表示的整个加密块 n加密块

24、数组中，加密块数组中，n可以是可以是3，5，7，所代表的加密块分别表示，所代表的加密块分别表示 128bit，192bit和和256bit。 ai,j a0,j a1,j a2,j a3,j ai,0ai,1ai,3 a0,2a0,3 a1,2a1,3 a2,2a2,3 a0,0a0,1 a1,0a1,1 a2,0a2,1 a3,0a3,1a3,2a3,3 a0,n a1,n a2,n a3,n 加密算法概述（3） n令令Nr代表算法的圈数，代表算法的圈数， Nk代表密钥长度代表密钥长度/32， Nb代表块长度代表块长度/32，则算，则算 法的圈数法的圈数Nr的取值与的取值与Nk 和和Nb的关

25、系为：的关系为： n除最后一圈不做列混合除最后一圈不做列混合 变换外，每一圈都经过变换外，每一圈都经过4 步相同的操作：步相同的操作： NrNb4Nb6Nb8 Nk4101214 Nk6121214 Nk8141414 Round(State, RoundKey) ByteSub(State);/S-盒 ShiftRow(State);/行循环左移 MixColumn(State);/列混合变换 AddRoundKey(State, RoundKey); /与扩展密钥相异或 一圈变换（1） n非线性代替（非线性代替（S-盒）：包括盒）：包括2步步 n在在GF(28)上求每个字节关于模上求每个字

26、节关于模m(x)的乘法逆元素，的乘法逆元素，00的逆元的逆元 定义为定义为00；(000110001163, 01011111007c) n应用应用GF(2)上的一个仿射变换：上的一个仿射变换： 一圈变换（2） n每个字节每个字节aij经过以上经过以上2步变换后，记为步变换后，记为bij。 n可以将每个可能的可以将每个可能的aij值对应的值对应的bij值制成表格，通过查值制成表格，通过查 表的方式来实现表的方式来实现S-盒代替，见下表。其中盒代替，见下表。其中xy代表代表1 个字节的个字节的16进制表示。进制表示。 一圈变换（3） n行循环左移（行循环左移（ShiftRow）：每一）：每一 行

27、以字节为单位循环左移，左移行以字节为单位循环左移，左移 的字节数见右表。因此，第的字节数见右表。因此，第1行行 不移位，第不移位，第2行左移行左移1个字节个字节 n列混合变换（列混合变换（Mixcolumn）：对）：对 每一列中每个字节每一列中每个字节a(x)，令，令 b(x)=c(x) a(x)，其中，其中c(x)为：为： c(x)=03x3+01x2+01x+02 n与扩展密钥相异或：与扩展密钥相异或： aij kijbij NbC0C1C2C3 40123 60123 80134 一圈变换（4） n一圈结构图：一圈结构图： Step1. ByteSub(State) Step2. Shi

28、ftRow(State) Step3. MixColumn(State) Step4. AddRoundKey(State, RoundKey) State S-盒 行循环左移 c(x)A A RoundKey Round(State, RoundKey) 密钥扩展（1） n扩展密钥是一个以扩展密钥是一个以4字节大小为单位字节大小为单位(用用Word表示表示)的线性的线性 数组。当数组。当Nk大于大于6的时候有一点不同。开始的时候有一点不同。开始Nk个个Word是是 加密用的密钥，以后每个加密用的密钥，以后每个Word通过对通过对K实行变换得到。实行变换得到。 n当当Nk6时，时， 若若Nk

29、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异或。异或。 密钥扩展的伪代码： KeyExpa

30、nsion(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; 异或

31、异或 密钥扩展（2） n可以从扩展密钥中选择可以从扩展密钥中选择Round key，例如：当，例如：当Nb6,Nk 4时，扩展密钥和各圈子密钥的选择如下：时，扩展密钥和各圈子密钥的选择如下： 加密算法描述 n整个算法可以用整个算法可以用 下面的代码表示：下面的代码表示： Rijndael(State, CipherKey) KeyExpansion(CipherKey, ExpandedKey); /扩展密钥扩展密钥 AddRoundKey(State, ExpandedKey); /与扩展密钥异或与扩展密钥异或 for ( i=1; iNr; i+) Round(State, Expande

32、dKey+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列混合变换的逆变换列混合变换的逆变换

33、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）能在广泛的硬件平台上高效