计算机安全保密第四讲

计算机安全保密第四讲对称密钥算法唐明武汉大学计算机学院本次课的内容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是一个换位或代替。如转轮机。Feistel设计的Lucifer密码的代替-移位变换P53图4.1Feistel加密过程输入：长为2w比特的明文分组密钥k输出：长为2w比特的密文分组4.1.1Feistel网络的特点明文分组分为：L0，R0，数据的这两部分通过n次循环处理后，再结合起来生成密文分组第i轮循环都以上一轮循环产生的Li-1和Ri-1和K产生的子密钥Ki作为输入。一般说来，子密钥Ki与K不同，相互之间也不同，它是用子密钥生成算法从密钥生成的4.1.1Feistel网络的特点所有循环的结构都相同，置换在数据的左半部分进行，其方法是先对数据的右半部分应用循环函数F，然后对函数输出结果和数据的左半部分取异或(XOR)循环函数对每次循环都有相同的通用结构，但由循环子密钥Ki来区分在置换之后，执行由数据两部分互换构成的交换4.1.1Feistel网络的特点解密过程与加密过程基本相同。规则如下：–用密文作为算法的输入–但以相反顺序使用子密钥Ki意味着加密和解密不需要用两种不同的方法。Involution:对合运算4.1.2Feistel结构定义•加密:Li=Ri-1;Ri=Li-1F(Ri-1,Ki)•解密:Ri-1=LiLi-1=RiF(Ri-1,Ki)=RiF(Li,Ki)Li-1Ri-14.1.3Feistel网络的设计特点分组大小：较大的分组意味着较强的安全性，但会降低加密解密速度。64位的分组大小是合理的折中，几乎所有的分组设计中都使用它密钥大小：较大的密钥意味着较强的安全性，但会降低加密解密速度。现代算法中最常用的是128位密钥循环次数：本质是单一循环的不足，多重循环能够加强安全性。典型的循环次数为16子密钥生成算法：较大的复杂性会增大密钥分析的难度循环函数：较大的复杂性意味着给密码分析带来更大的难度4.2数据加密标准算法DES背景–DES是20年来全世界通用的标准算法。–20世纪70年代初期，非军事性的密码处于一种无序状态。–1972年，美国国家标准局NBS开始一项保护计算机和通信数据的项目，其中一部分是要开发一个单独的标准保密算法。–1973年5月15日，NBS公开征集标准加密算法，并公布了设计要求(P54)，未果。–1974年8月，NBS第二次征集算法，收到一份可选方案：基于IBM在20世纪70年代初开发的LUCIFER算法的算法。–1976年，NBS指派两个工作组来评价该标准。–DES在1976年11月23日被宣布为联邦标准，允许在非保密的政府通信中使用。标准的官方描述在1977年1月15日颁布，6个月后生效。–1984年9美国总统签署145号国家安全决策令(NSDD),命令NSA着手发展新的加密标准,用于政府系统非机密数据和私人企事业单位.•NSA宣布每隔5年重新审议DES是否继续作为联邦标准,1988年(FIPS46-1),1993年(FIPS46-2),1998年不再重新批准DES为联邦标准.4.2.1数据加密标准算法DES算法描述–算法概述：–每轮：Li=Ri-1Ri=Li-1⊕f(Ri-1,Ki)f将数据和密钥结合起来。DES加密算法明文IPL0R0fffIP-1K1密文L=R10R=Lf(R,K)1001L=R21R=L21f(R,K)12L=R1514R=L1514f(R,K)1415K2K16R=L1615f(R,K)1516L=R1615InitialPermutationP55P55初始变换IP：在第一圈之前逆初始变换IP-1：最后一圈之后置换表中的每个元素表明了某个输入位在64位输出中的位置。DES算法一轮迭代的过程F函数：–E变换–按位异或–S盒代替–P变换Li-1Ri-1E变换S盒代替P变换LiRi密钥移位移位压缩变换密钥2828484832325628284832323232ki4.2.2扩展变换E：将右半部分从32位扩展到48位4.2.3S盒代替：对48位中间结果做代替操作。–8个小S盒，每个有6位输入和4位输出–设输入为b1b2b3b4b5b6，则b1b6为行号，b2b3b4b5为列号–例：S6的输入110011，行11（3），列1001（9）处为14，输出为1110P变换：换位操作P变换的结果与上一圈的左半部分异或，称为新的右半部分，开始下一圈密钥PC-1C0D0循环左移循环左移C1D1PC-2循环左移循环左移C2D2PC-2PC-2循环左移循环左移C16D16……K1K2K16密钥变换C:Compress6456282828282828564828282828484856562828282828284.2.4密钥变换–PC-1：64位密钥去掉8的倍数位，通过置换选择得到56位。循环左移：56位分成各28位的两部分，分别循环左移1或2位计算:各轮移位次数之和为多少?PC-2：从56位中选出48位，为本圈子密钥举例：K=0xfedcba9876543210,求K1K:1111111011011100101110101001100001110110010101000011001000010000循环左移:00011110111001101010101111101010101001100110000111111110K1:1111010011111101100110000110010010110110010110100000111100110011PC-1(K):0101010111110101010100110011111100001111PC-2举例例：m=computer,k=program,试用DES求密文。（1）把m和k转换为2进制数，m:163H896FH16176DH242570H3201100011,01101111,01101101,011100003375H404174H484965H565772H6401110101,01110100,01100101,01110010k:01110000,01110010,01101111,0110011101110010,01100001,01101101IP(m):L0=?11111111,10111000,01110110,01010111R0=?00000000,11111111,00000110,10000011Insertchecksumintok:01110001,00111001,10011010,1110110101110111,10010011,10000100,11011011PC-1(k):C0=?11101100,10011001,00011011,1011D0=?10110100,01011000,10001110,0111K1=PC-2(K)=?00111101,10001111,11001101,00110111,00111111,01001000E(R0)=?10000000,00010111,1111111010000000,11010100,00000110D=E(R0)K1=?10111101,10011000,00110011,10110111,11101011,01001110D为S盒的输入：101111-011001-100000-110011-101101-111110-101101-001110s-box(D)=?输入：101111-011001-100000-110011-101101-111110-101101-001110输出：0111-0110,1101-0100,0010-0110,1010-0001P变换=？01000100,00100001,10011111,10011111R1=L0f(R0,K1)=？10111011,10011000,11101000,11001000L1=R0=？00000000,11111111,00000110,100000114.2.5DES的加解密加密过程：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的安全性–弱密钥P60•弱密钥：每一圈的子密钥都相同。共4个。•半弱密钥：只产生2种不同的子密钥，每种出现8次。共12个。•半半弱密钥（可能弱密钥）：只产生4种不同的子密钥，每种出现4次。共48个。–互补密钥•将密钥的0换成1，1换成0，就得到该密钥的补密钥。如果用原密钥加密一组明文，则用补密钥可以将明文的补码加密成密文的补码。–代数结构–密钥长度–圈数–S盒的设计准则P654.3高级数据加密标准AES背景AES的数学基础AES加密算法描述AES解密算法算法评价结论4.3.1背景现代计算机速度的迅速提高，使得只有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。4.3.2AES的数学基础(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)164.3.3AES的数学基础(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+x34.3.4AES的数学基础(3)“·X”运算：b·X=b7x8+b