对称密码学及其应用 第4章 典型分组密码算法.ppt

对称密码学及其应用对称密码学及其应用1第四章第四章 典型分组密码算法典型分组密码算法 nDES算法算法nIDEA算法算法 nRC5算法算法nAES算法算法 对称密码学及其应用对称密码学及其应用2DES 算法算法nDES的历史n1971 IBM，由Horst Feistel 领导的密码研究项目组研究出LUCIFER算法。并应用于商业领域。n1973美国标准局征求标准，IBM提交结果，n在1977年，被选为数据加密标准。nDES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文对称密码学及其应用对称密码学及其应用3DES的描述n该算法主要步骤：n将64位明文分组送入初始置换（IP，Initial Permutation）函数。n对明文进行初始置换。n初始置换产生转换块的两半，假设为左明文（LPT）和右明文（RPT）。n每个左明文与右明文用各自的密钥经过16轮加密过程。n将左明文与右明文重接起来，对组成的块进行最终置换（FP，Final Permutation）。n这个过程的结果得到64位密文。对称密码学及其应用对称密码学及其应用4DES主要步骤对称密码学及其应用对称密码学及其应用5IP-初始置换初始置换对称密码学及其应用对称密码学及其应用6最终转换（最终转换（FP）对称密码学及其应用对称密码学及其应用7DES的一轮的一轮对称密码学及其应用对称密码学及其应用8异或与交换异或与交换 对称密码学及其应用对称密码学及其应用9n n DES 轮函数F（）对称密码学及其应用对称密码学及其应用10 DES加密的一个例子n取16进制明文X：0123456789ABCDEF密钥K为：133457799BBCDFF1去掉奇偶校验位以二进制形式表示的密钥是00010010011010010101101111001001101101111011011111111000应用IP，我们得到：L0=11001100000000001100110011111111L1=R0=11110000101010101111000010101010然后进行16轮加密。最后对L16,R16使用IP-1得到密文：85E813540F0AB405对称密码学及其应用对称密码学及其应用11DES的设计思想和特点 nDES的核心是S盒，除此之外的计算是属线性的。S盒作为该密码体制的非线性组件对安全性至关重要。nS盒的设计准则：1.S盒不是它输入变量的线性函数2.改变S盒的一个输入位至少要引起两位的输出改变3.对任何一个S盒，如果固定一个输入比特，其它输入变化时，输出数字中0和1的总数近于相等。对称密码学及其应用对称密码学及其应用12DES的安全性的安全性 n对对DES的批评主要集中在以下几点：的批评主要集中在以下几点：nDES的密钥长度（的密钥长度（56位）可能太小。位）可能太小。nDES的迭代次数可能太少。的迭代次数可能太少。nS盒中可能有不安全因素。盒中可能有不安全因素。nDES的一些关键部分不应当保密。的一些关键部分不应当保密。对称密码学及其应用对称密码学及其应用133DES对称密码学及其应用对称密码学及其应用14IDEA简介瑞士的Xuejia Lai和James Massey于1990年公布了IDEA密码算法第一版，称为PES(Proposed Encryption Standard)。为抗击差分密码攻击，他们增强了算法的强度，称IPES（Improved PES)，并于1992年改名为IDEA（International Data Encryption Algorithm，国际数据加密算法。）对称密码学及其应用对称密码学及其应用15IDEA(Cont.)nIDEA是一个分组长度为64位的分组密码算法，密钥长度为128位（抗强力攻击能力比DES强），同一算法既可加密也可解密。nIDEA的“混淆”和“扩散”设计原则来自三种运算，它们易于软、硬件实现（加密速度快）：对称密码学及其应用对称密码学及其应用16IDEA简介(Cont.)nIDEA是PGP的一部分；nIDEA能抗差分分析和相关分析；nIDEA似乎没有DES意义下的弱密钥；nBruce Schneier 认为IDEA是DES的最好替代，但问题是IDEA太新，许多问题没解决。对称密码学及其应用对称密码学及其应用17IDEA简介(Cont.)n异或运算（）n整数模216加（+）n整数模216+1乘（）(IDEA的S盒）n扩散由称为MA结构的算法基本构件提供。Z6F2F1Z5G1G2对称密码学及其应用对称密码学及其应用18IDEA简介(Cont.)n实现上的考虑n使用子分组：16bit的子分组；n使用简单操作（易于加法、移位等操作实现）n加密解密过程类似；n规则的结构（便于VLSI实现）。对称密码学及其应用对称密码学及其应用19 IDEA加密的总体方案图加密的总体方案图循环循环2循环循环8循环循环1输出变换输出变换64位密文位密文64位明文位明文Z1Z6Z7Z12Z43Z48Z49Z52子密钥生成器子密钥生成器128位密钥位密钥Z1Z5216对称密码学及其应用对称密码学及其应用20 对称密码学及其应用对称密码学及其应用21IDEA的密钥生产56个16bit的子密钥从128bit的密钥中生成n前8个子密钥直接从密钥中取出；n对密钥进行25bit的循环左移，接下来的密钥就从中取出；n重复进行直到52个子密钥都产生出来。对称密码学及其应用对称密码学及其应用22IDEA的解密n加密解密实质相同，但使用不同的密钥；n解密密钥以如下方法从加密子密钥中导出：n解密循环I的头4个子密钥从加密循环10I的头4个子密钥中导出；解密密钥第1、4个子密钥对应于1、4加密子密钥的乘法逆元；2、3对应2、3的加法逆元；n对前8个循环来说，循环I的最后两个子密钥等于加密循环9I的最后两个子密钥；对称密码学及其应用对称密码学及其应用23RC5加密算法加密算法n作者为作者为Ron Rivestn算法特点算法特点n三个参数三个参数n参数参数w：表示字长，表示字长，RC5加密两字长分组，可用值加密两字长分组，可用值为为16、32、64n参数参数r：表示轮数，可用值表示轮数，可用值0,1,255n参数参数b：表示密钥表示密钥K的字节数，可用值的字节数，可用值0,1,255nRC5版本：版本：RC5-w/r/bn算法作者建议标定版本为算法作者建议标定版本为RC5-32/12/16对称密码学及其应用对称密码学及其应用24RC5加密算法加密算法n三个基本运算三个基本运算n字的加法，模字的加法，模2w +n按位异或按位异或 n左循环移位左循环移位 n算法：算法：nA=A+S0；nB=B+S1；nFor i=1 to r do A=(A B)B+S2*i B=(B A)A+S2*i+1对称密码学及其应用对称密码学及其应用25美国高级数据加密标准美国高级数据加密标准AESn背景nAES homepagenhttp:/www.nist.gov/aes/nhttp:/csrc.nist.gov/CryptoToolkit/aes/nFIPS 197nTimen1997年，要求算法公开、自由，密钥年，要求算法公开、自由，密钥128n1998/8/20，征集到，征集到15个候选算法个候选算法n1999/3,4，经分析开会讨论落实了，经分析开会讨论落实了5个算法个算法nMARS,RC6,Rijndael,Serpent,Twofishn2000/10/2，选定，选定Rijndael为为AESn2001/11，FIPS 197对称密码学及其应用对称密码学及其应用26n要求n该算法应比三重DES快，而且至少还要一样的安全；n具有128比特分组长度和256比特分组密钥长度（不过必须支持128和192比特的密钥）；n应该具有较大的灵活性。AES算法算法对称密码学及其应用对称密码学及其应用27 AES的评估准则 1）安全性；）安全性；2）代价，主要包括：许可要求，在各种平）代价，主要包括：许可要求，在各种平台上的计算效率（速度）和内存空间的台上的计算效率（速度）和内存空间的需求；需求；3）算法和实现特性，主要包括：灵活性、）算法和实现特性，主要包括：灵活性、硬件和软件适应性、算法的简单性等。硬件和软件适应性、算法的简单性等。AES算法算法对称密码学及其应用对称密码学及其应用281998年8月20日，NIST在第一阶段讨论（AES1）中宣布了由12个国家提出的15个候选算法，1999年3月开始的第二阶段讨论（AES2），1999年8月NIST选出5个算法候选:MARS、RC6、Rijndael、Serpent和Twofish。AES算法算法对称密码学及其应用对称密码学及其应用29高级加密标准算法高级加密标准算法AESRijndael n最大优点是可以给出算法的最佳差分特最大优点是可以给出算法的最佳差分特征的概率及最佳线性逼近的偏差的界，征的概率及最佳线性逼近的偏差的界，由此，可以分析算法抵抗差分密码分析由此，可以分析算法抵抗差分密码分析及线性密码分析的能力。及线性密码分析的能力。对称密码学及其应用对称密码学及其应用30AES算法算法n基本参数基本参数n分组分组128bit,数据块数据块48bit=1个字个字n轮数要么是轮数要么是10,12,要么是要么是14,依赖于种子依赖于种子密钥长度是密钥长度是128位、位、192 位还是位还是 256 位位 对称密码学及其应用对称密码学及其应用31AES的工作原理的工作原理 对称密码学及其应用对称密码学及其应用32操作操作1：替换操作：替换操作n操作操作1：Rijndael替换操作替换操作 对称密码学及其应用对称密码学及其应用33字节代换，计算字节代换，计算S盒元素盒元素n输入输入 Aa7a6a5a4a3a2a1a0 a(x)n求逆求逆 b(x)b7b6b5b4b3b2b1b0n输出字节输出字节b7b6b5b4b3b2b1b0B对称密码学及其应用对称密码学及其应用34AES S-Box x/yx/y 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 5 6 7 8 9 A B C D E Fn0 63 7C 77 7B F2 6B 6F C5 30 01 67 2B FE D7 AB 760 63 7C 77 7B F2 6B 6F C5 30 01 67 2B FE D7 AB 76n1 CA 82 C9 7D FA 59 47 F0 AD D4 A2 AF 9C A4 72 C01 CA 82 C9 7D FA 59 47 F0 AD D4 A2 AF 9C A4 72 C0n2 B7 FD 93 26 36 3F F7 CC 34 A5 E5 F1 71 D8 31 152 B7 FD 93 26 36 3F F7 CC 34 A5 E5 F1 71 D8 31 15n3 04 C7 23 C3 18 96 05 9A 07 12 80 E2 EB 27 B2 753 04 C7 23 C3 18 96 05 9A 07 12 80 E2 EB 27 B2 75n4 09 83 2C 1A 1B 6E 5A A0 52 3B D6 B3 29 E3 2F 844 09 83 2C 1A 1B 6E 5A A0 52 3B D6 B3 29 E3 2F 84n5 53 D1 00 ED 20 FC B1 5B 6A CB BE 39 4A 4C 58 CF5 53 D1 00 ED 20 FC B1 5B 6A CB BE 39 4A 4C 58 CFn6 D0 EF AA FB 43 4D 33 85 45 F9 02 7F 50 3C 9F A86 D0 EF AA FB 43 4D 33 85 45 F9 02 7F 50 3C 9F A8n7 51 A3 40 8F 92 9D 38 F5 BC B6 DA 21 10 FF F3 D27 51 A3 40 8F 92 9D 38 F5 BC B6 DA 21 10 FF F3 D2n8 CD 0C 13 EC 5F 97 44 17 C4 A7 7E 3D 64 5D 19 738 CD 0C 13 EC 5F 97 44 17 C4 A7 7E 3D 64 5D 19 73n9 60 81 4F DC 22 2A 90 88 46 EE B8 14 DE 5E 0B DB9 60 81 4F DC 22 2A 90 88 46 EE B8 14 DE 5E 0B DBnA E0 32 3A 0A 49 06 24 5C C2 D3 AC 62 91 95 E4 79A E0 32 3A 0A 49 06 24 5C C2 D3 AC 62 91 95 E4 79nB E7 C8 37 6D 8D D5 4E A9 6C 56 F4 EA 65 7A AE 08B E7 C8 37 6D 8D D5 4E A9 6C 56 F4 EA 65 7A AE 08nC BA 78 25 2E 1C A6 B4 C6 E8 DD 74 1F 4B BD 8B 8AC BA 78 25 2E 1C A6 B4 C6 E8 DD 74 1F 4B BD 8B 8AnD 70 3E B5 66 48 03 F6 0E 61 35 57 B9 86 C1 1D 9ED 70 3E B5 66 48 03 F6 0E 61 35 57 B9 86 C1 1D 9EnE E1 F8 98 11 69 D9 8E 94 9B 1E 87 E9 CE 55 28 DFE E1 F8 98 11 69 D9 8E 94 9B 1E 87 E9 CE 55 28 DFnF 8C A1 89 0D BF E6 42 68 41 99 2D 0F B0 54 BB 16F 8C A1 89 0D BF E6 42 68 41 99 2D 0F B0 54 BB 16对称密码学及其应用对称密码学及其应用35AES S-Box（逆）（逆）x/yx/y 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 5 6 7 8 9 A B C D E Fn0 52 09 6A D5 30 36 A5 38 BF 40 A3 9E 81 F3 D7 FB0 52 09 6A D5 30 36 A5 38 BF 40 A3 9E 81 F3 D7 FBn1 7C E3 39 82 9B 2F FF 87 34 8E 43 44 C4 DE E9 CB1 7C E3 39 82 9B 2F FF 87 34 8E 43 44 C4 DE E9 CBn2 54 7B 94 32 A6 C2 23 3D EE 4C 95 0B 42 FA C3 4E2 54 7B 94 32 A6 C2 23 3D EE 4C 95 0B 42 FA C3 4En3 08 2E A1 66 28 D9 24 B2 76 5B A2 49 6D 8B D1 253 08 2E A1 66 28 D9 24 B2 76 5B A2 49 6D 8B D1 25n4 72 F8 F6 64 86 68 98 16 D4 A4 5C CC 5D 65 B6 924 72 F8 F6 64 86 68 98 16 D4 A4 5C CC 5D 65 B6 92n5 6C 70 48 50 FD ED B9 DA 5E 15 46 57 A7 8D 9D 845 6C 70 48 50 FD ED B9 DA 5E 15 46 57 A7 8D 9D 84n6 90 D8 AB 00 8C BC D3 0A F7 E4 58 05 B8 B3 45 066 90 D8 AB 00 8C BC D3 0A F7 E4 58 05 B8 B3 45 06n7 D0 2C 1E 8F CA 3F 0F 02 C1 AF BD 03 01 13 8A 6B7 D0 2C 1E 8F CA 3F 0F 02 C1 AF BD 03 01 13 8A 6Bn8 3A 91 11 41 4F 67 DC EA 97 F2 CF CE F0 B4 E6 738 3A 91 11 41 4F 67 DC EA 97 F2 CF CE F0 B4 E6 73n9 96 AC 74 22 E7 AD 35 85 E2 F9 37 E8 1C 75 DF 6E9 96 AC 74 22 E7 AD 35 85 E2 F9 37 E8 1C 75 DF 6EnA 47 F1 1A 71 1D 29 C5 89 6F B7 62 0E AA 18 BE 1BA 47 F1 1A 71 1D 29 C5 89 6F B7 62 0E AA 18 BE 1BnB FC 56 3E 4B C6 D2 79 20 9A DB C0 FE 78 CD 5A F4B FC 56 3E 4B C6 D2 79 20 9A DB C0 FE 78 CD 5A F4nC 1F DD A8 33 88 07 C7 31 B1 12 10 59 27 80 EC 5FC 1F DD A8 33 88 07 C7 31 B1 12 10 59 27 80 EC 5FnD 60 51 7F A9 19 B5 4A 0D 2D E5 7A 9F 93 C9 9C EFD 60 51 7F A9 19 B5 4A 0D 2D E5 7A 9F 93 C9 9C EFnE A0 E0 3B 4D AE 2A F5 B0 C8 EB BB 3C 83 53 99 61E A0 E0 3B 4D AE 2A F5 B0 C8 EB BB 3C 83 53 99 61nF 17 2B 04 7E BA 77 D6 26 E1 69 14 63 55 21 0C 7DF 17 2B 04 7E BA 77 D6 26 E1 69 14 63 55 21 0C 7D对称密码学及其应用对称密码学及其应用36操作操作2：行移位操作：行移位操作n操作操作2：行移位操作：行移位操作 对称密码学及其应用对称密码学及其应用37操作操作3：列混合变换：列混合变换对称密码学及其应用对称密码学及其应用38子密钥生成子密钥生成n密钥扩展密钥扩展n轮密钥选择轮密钥选择n其基本规则：其基本规则：所有轮密钥的位数总和数据分组长度位数所有轮密钥的位数总和数据分组长度位数*（加密轮数（加密轮数1）初始密钥扩展为一个扩展密钥初始密钥扩展为一个扩展密钥轮密钥按下述方式从扩展密钥中抽取：第一轮轮密钥按下述方式从扩展密钥中抽取：第一轮密钥由扩展密钥的前密钥由扩展密钥的前Nb*4个字节组成，第二轮个字节组成，第二轮密钥由接下来的密钥由接下来的Nb*4个字节组成，如此继续下个字节组成，如此继续下去直到获得所有轮密钥。去直到获得所有轮密钥。Nb是阵列列数是阵列列数对称密码学及其应用对称密码学及其应用39子密钥生成子密钥生成n128bits isa 16bytes isa 4words扩展至扩展至 nsubkey in w043n初始初始AddRoundKey w0,1,2,3n9轮循环轮循环 w4,5,6,7w36,37,38,39n最后最后1轮轮 w40,41,42,43对称密码学及其应用对称密码学及其应用40AES Key Expansionn 对称密码学及其应用对称密码学及其应用41AES Key Expansion：g(.)n循环左移循环左移1字节字节n字节代换（字节代换（S盒）盒）nXOR 轮常量轮常量Rcon Rcon1（01，00，00，00）Rconj（(02)j-1,00,00,00）;j=2,3,4对称密码学及其应用对称密码学及其应用42Rcon表表对称密码学及其应用对称密码学及其应用43KeyExpansion()