信息安全基础4

4对称密钥算法4.1概述4.2数据加密标准算法DES4.3高级数据加密标准AES4.4联合分组密码4.1概述分组密码：向量x到向量y上的一个映射：x→y=(x)x=(x0,x1,…,xN-1),y=(y0,y1,…,yN-1)乘积密码：t个函数（密码）F1,…,Ft的复合，其中每个Fi是一个换位或代替。如转轮机。Lucifer密码的代替-移位变换乘积密码：代替和简单线性变换来实现混合变换。例：ADFGVX乘积密码1.先造一个6*6方阵ADFGVXAK2WR1FD9B6CL5FQ7JPGXGEVY3ANV8ODH02XU4ISTM明文：PRODUCTCIPHERS变换（代替）：（行标，列标）明文PFG（把原来明文的一个字母用RAG两个字母行、列来代替）第一次加密密文：FGAGVDVFXADGXVDGXFFGVGGAAGXG2.移位变换：构造一个移位矩阵,约定一个密钥密钥：DEUTSCH把第一次加密的密文按行写入4*7矩阵，前边加上密钥，密钥字母按其在字母表中出现的次序编号。DEUTSCH2376514FGAGVDVFXADGXVDGXFFGVGGAAGXG第二次加密（移位法）：按密钥字母在字母表中的顺序一列一列写出。密文：DXGXFFDGGXGGVVVGVGFGGDFAAAXA4.2数据加密标准算法DES背景算法描述算法概述：Li=Ri-1Ri=Li-1⊕f(Ri-1,Ki)明文IP变换L0R0+fL1=R0R1=L0f(R0,K1)L15=R14f+K1R16=L15f(R15,K16)R15=L14f(R14,K15)L16=R15K16IP-1变换密文+++f+K2…………Li=Ri-1Ri=Li-1f(Ri-1,Ki)+f+Ki+1…………F函数：E变换按位异或S盒代替P变换Li-1Ri-1E变换S盒代替P变换LiRi密钥移位移位压缩变换密钥密钥PC-1C0D0循环左移循环左移C1D1PC-2循环左移循环左移C2D2PC-2PC-2循环左移循环左移C16D16……K1K2K16密钥变换：初始变换IP：在第一圈之前（对明文移位）密钥变换：PC-1：64位密钥去掉8的倍数位循环左移：56位分成各28位的两部分，分别循环左移1或2位PC-2：从56位中选出48位，为本圈子密钥扩展变换E：将右半部分从32位扩展到48位S盒代替：对48位中间结果做代替操作。8个小S盒，每个有6位输入和4位输出设输入为b1b2b3b4b5b6，则b1b6为行号，b2b3b4b5为列号例：S6的输入110011，行11（3），列1001（9）处为14，输出为1110P变换：换位操作，P变换的结果与上一圈的左半部分异或，成为新的右半部分，开始下一圈逆初始变换IP-1（移位）举例：设M=0x0123456789abcdef,K=0xfedcba9876543210,求L1和R1。K:111111101101110010111010100110000111011001010100001100100001000064位PC-1(K):00001111001100110101010111110101010100110011000011111111表4.256位循环左移:0001111001100110101010111110101010100110011000011111111056位K1(PC-2):111101001111110110011000011001001011011001011010表4.448位M:0000000100100011010001010110011110001001101010111100110111101111IP(M):1100110000000000110011001111111111110000101010101111000010101010E(R0)011110100001010101010101011110100001010101010101E(R0)⊕K1100011101110100011001101000111101010001100001111S盒代替:11000001101000001100100010000100P变换:00010001100001001100000100100101R1:11011101100001000000110111011010L1:加密过程：L0R0IP(64位明文)FORi=1TO16LiRi-1RiLi-1⊕f(Ri-1,Ki)64位密文IP-1(R16L16)解密过程：R16L16IP(64位密文)FORi=16TO1Ri-1LiLi-1Ri⊕f(Li,Ki)64位明文IP-1(L0R0)DES的安全性弱密钥弱密钥：每一圈的子密钥都相同。共4个。半弱密钥：只产生2种不同的子密钥，每种出现8次。共12个。可能弱密钥：只产生4种不同的子密钥，每种出现4次。共48个。互补密钥代数结构密钥长度圈数S盒的设计练习1.已知DES算法中S盒的输入为0x010101010102，求经过S盒代替后的输出结果。答案：11101001100111010010000000100010输入:000000010000000100000001000000010000000100000010S1:0行0列：14－－1110S2:0行8列：9－－1001S3:0行2列：9－－1001S4:1行0列：13－－1101S5:0行0列：2－－0010S6:0行8列：0－－0000S7:0行2列：2－－0010S8:0行1列：2－－00104.3高级数据加密标准AES背景AES的数学基础AES加密算法描述AES解密算法算法评价结论背景现代计算机速度的迅速提高，使得只有56bit密钥的DES算法的安全性面临着极大的挑战。1997年，NIST公开征求AES（AdvancedEncryptionStandard）作为2001年以后的数据加密标准。1998年8月，AES召开第一次候选会，确定15个算法入围。1999年3月，AES召开第二次候选会，有5个算法入围（MARS,RC6,Rijndael,Serpent和Twofish）。2000年10月，NIST选出由比利时的JoanDaemen和VincentRijmen提交的Rijndael算法作为AES。2001年夏天，NIST颁布新的信息处理标准（FIPS），将Rijndael算法作为AES。AES的数学基础(1)有限域GF(28)上定义了4种运算：“+”、“·”、“·X”和带系数的多项式乘运算“”。对字节b，用多项式表示为：b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0“+”运算：两个字节相加，相当于字节的每一位简单异或。例：’57’＋’83’＝‘d4’(57)16=(01010111)2→x6+x4+x2+x+1(83)16=(10000011)2→x7+x+1’57’＋’83’→(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2→(11010100)2＝(d4)16AES的数学基础(2)“·”运算：选择一个不可约多项式：m(x)=x8+x4+x3+x+1，“·”运算为两多项式相乘后进行模m(x)的运算。例：’57’·’83’＝‘c1’(57)16=(01010111)2→x6+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+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)“·X”运算：b·X=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x求乘法逆元：因为m(x)是GF(28)上的不可约多项式，所以对于任意b(x)，都可以用扩展的Euclid算法求a(x)，使得a(x)·b(x)+c(x)·m(x)=1因而a(x)·b(x)modm(x)=1即b－1(x)modm(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＝(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)+(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)－1mod(x8+x4+x3+x+1)＝x5+x3AES的数学基础(4)带系数的多项式乘运算“”：令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·b0c1=a1·b0a0·b1c2=a2·b0a1·b1a0·b2c3=a3·b0a2·b1a1·b2a0·b3c4=a3·b1a2·b2a1·b3c5=a3·b2a2·b3c6=a3·b3对（x4+1）取模得d(x):d(x)=a(x)b(x)=d3x3+d2x2+d1x+d0其中，d0=a0·b0a3·b1a2·b2a1·b3d1=a1·b0a0·b1a3·b2a2·b3d2=a2·b0a1·b1a0·b2a3·b3d3=a3·b0a2·b1a1·b2a0·b3注意：ximod(x4+1)=ximod4AES加密算法描述加密算法概述一圈变换密钥扩展加密算法描述加密算法概述（1）AES算法与以往的基于Feistel网的密码（如DES）不同，算法的每一步都是可逆的。算法的明文块长可以为128bit，192bit或256bit，密钥也可以分别为128bit，192bit或256bit。算法有多圈相同的运算，每一圈包括4个步骤：非线性代替（S-盒）行循环左移（ShiftRow）列混合变换（MixColum）与扩展密钥相异或每一圈的子密钥从扩展密钥中取出密钥扩展过程同时应用了非线性变换和循环左移算法定义的所有运算都是在有限域GF(28)上进行的加密算法概述（2）算法中进行运算的单位包括：1个字节1列1行用字节数组表示的整个加密块加密块数组中，n可以是3，5，7，所代表的加密块分别表示128bit，192bit和256bit。ai,ja0,ja1,ja2,ja3,jai,0ai,