密码编码学网络安全第03章对称密码体制(第四讲319)课件

1、密码编码学网络安全第03章对称密码体制(第四讲319)12022-3-7第三章第三章 对称密码体制对称密码体制密码编码学网络安全第03章对称密码体制(第四讲319)22022-3-7本章内容本章内容Feistel密码简化的数据加密标准S-DES数据加密标准DES差分分析和线性分析分组密码的设计原理密码编码学网络安全第03章对称密码体制(第四讲319)32022-3-71. Feistel密码当前使用的大部分对称加密算法都基于被称为Feistel分组密码的结构。 数据映射设计扩散和扰乱(混淆)加密算法结构解密算法密码编码学网络安全第03章对称密码体制(第四讲319)42022-3-71.0 流密

2、码与分组密码流密码流密码每次加密数据流的一位或一个字节。每次加密数据流的一位或一个字节。例子：古典密码中的例子：古典密码中的VigenreVigenre密码和密码和VernamVernam密码。密码。分组密码分组密码将一个明文组作为整体加密且通常得到的是与之等长将一个明文组作为整体加密且通常得到的是与之等长的密文组。的密文组。典型分组大小是典型分组大小是6464位或位或128128位。位。密码编码学网络安全第03章对称密码体制(第四讲319)52022-3-71.1 1.1 数据映射设计数据映射设计可逆映射 明文 密文 0011011010001101不可逆映射 明文 密文 001101101

3、0011101密码编码学网络安全第03章对称密码体制(第四讲319)62022-3-7 4 bit 输入 4 到 16 译码器 16 到 4 译码器 4 bit 输出 1 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 n=4n=4时的一个时的一个n n比特到比特到n n比特的分组密码比特的分组密码密码编码学网络安全第03章对称密码体制(第四讲319)72022-3-7示例：示例：4bit4bit明文明文一般替代一般替代线性映射线性映射y y1 1k k1111x x1 1k k1212x x2

4、 2k k1313x x3 3k k1414x x4 4y y2 2k k2121x x1 1k k2222x x2 2k k2323x x3 3k k2424x x4 4y y3 3k k3131x x1 1k k3232x x2 2k k3333x x3 3k k3434x x4 4y y4 4k k4141x x1 1k k4242x x2 2k k4343x x3 3k k4444x x4 4明文明文 密文密文 密文密文 明文明文 000011100000111000010100000100110010110100100100001100010011100001000010010000

5、0101011111010111000110101101101010011110000111111110000011100001111001101010011101101001101010100110111100101101101100010111001011110110011101001011100000111000001111011111110101替代密码的加密与解密表替代密码的加密与解密表密码编码学网络安全第03章对称密码体制(第四讲319)82022-3-7可逆映射和不可逆映射可逆映射和不可逆映射n bitn bit的可逆映射的不同变换个数为的可逆映射的不同变换个数为2 2n n！分

6、组长度较小时等同于古典的替代密码分组长度较小时等同于古典的替代密码n bitn bit的一般替代分组密码，密钥的大小是的一般替代分组密码，密钥的大小是 n n x 2 2n nn bitn bit线性映射的密钥的大小是线性映射的密钥的大小是n n2 2 密码编码学网络安全第03章对称密码体制(第四讲319)92022-3-71.2 1.2 扩散和混淆（扰乱）扩散和混淆（扰乱）现代分组密码设计的基础是为统计分析制造障碍现代分组密码设计的基础是为统计分析制造障碍扩散扩散 将明文的统计特征消散到密文中，让明文的每个数将明文的统计特征消散到密文中，让明文的每个数字影响许多密文数字的取值，亦即每个密文数

7、字被字影响许多密文数字的取值，亦即每个密文数字被许多明文数字影响。许多明文数字影响。混淆（扰乱）混淆（扰乱） 明文分组到密文分组的变换依赖于密钥，使得密文明文分组到密文分组的变换依赖于密钥，使得密文的统计特性与加密密钥的取值之间的关系尽量复杂的统计特性与加密密钥的取值之间的关系尽量复杂 ，使得即使攻击者掌握了密文的某些统计特性，由于使得即使攻击者掌握了密文的某些统计特性，由于密钥产生密文的方式是如此复杂以至于攻击者难于密钥产生密文的方式是如此复杂以至于攻击者难于从中推测出密钥从中推测出密钥 。密码编码学网络安全第03章对称密码体制(第四讲319)102022-3-7扩散扩散采用平均操作进行加密

8、采用平均操作进行加密 重复使用对数据的某种置换，并对置换结果再应用某重复使用对数据的某种置换，并对置换结果再应用某个函数。个函数。扰乱扰乱采用复杂的替代算法（非线性函数）。采用复杂的替代算法（非线性函数）。kiinnmc126mod密码编码学网络安全第03章对称密码体制(第四讲319)112022-3-71.3 1.3 Feistel加密算法结构明文分组被分为两个部分明文分组被分为两个部分L L0 0和和R R0 0，数据的，数据的这两个部分经过这两个部分经过n n轮的处理后组合起来产轮的处理后组合起来产生密文分组。生密文分组。每一轮每一轮i i以从前一轮得到的以从前一轮得到的L Li-1i-

9、1和和R Ri-1i-1为输为输入，另外的输入还有从总的密钥入，另外的输入还有从总的密钥K K生成的生成的子密钥子密钥K Ki i。子密钥子密钥K Ki i不同于不同于K K，它们彼此之间也不相，它们彼此之间也不相同。同。每一轮的结构都一样。对数据的左边一半每一轮的结构都一样。对数据的左边一半进行替代操作，替代的方法是对数据右边进行替代操作，替代的方法是对数据右边一半应用一半应用roundround函数函数F F，然后用这个函数的，然后用这个函数的输出和数据的左边一半做异或。输出和数据的左边一半做异或。 roundround函数在每一轮中有着相同的结构，函数在每一轮中有着相同的结构，但是以各轮

10、的子密钥但是以各轮的子密钥K Ki i为参数形成区分。为参数形成区分。在这个替代之后，算法做一个置换操作把在这个替代之后，算法做一个置换操作把数据的两个部分进行互换。数据的两个部分进行互换。 明文(2w 比特) w 比特 w 比特 第 1 轮 L0 R0 L1 K1 R1 Rn+1 F 第 i 轮 Li Ki Ri F 第 n 轮 Ln Kn Rn F Ln+1 密文(2w 比特) 密码编码学网络安全第03章对称密码体制(第四讲319)122022-3-7分组大小：分组越大意味着安全性越高（如果其他条件相分组大小：分组越大意味着安全性越高（如果其他条件相同），但加密同），但加密/ /解密速度也

11、越慢。解密速度也越慢。密钥大小：密钥长度越长则安全性越高，但加密密钥大小：密钥长度越长则安全性越高，但加密/ /解密速度解密速度也越慢。也越慢。循环次数：一个循环不能保证足够的安全性，而循环越多循环次数：一个循环不能保证足够的安全性，而循环越多 则安全性越高。则安全性越高。子密钥产生算法子密钥产生算法 ：算法越复杂则密码分析就应该越困难。：算法越复杂则密码分析就应该越困难。RoundRound函数：复杂性越高则抗击密码分析的能力就越强。函数：复杂性越高则抗击密码分析的能力就越强。FeistelFeistel具体实现依赖的参数和设计特点具体实现依赖的参数和设计特点 密码编码学网络安全第03章对称

12、密码体制(第四讲319)132022-3-7FeistelFeistel具体实现应考虑的其它因素具体实现应考虑的其它因素快速的软件加密快速的软件加密/ /解密：在很多情况下，加密过程被以某种解密：在很多情况下，加密过程被以某种方式嵌入在应用程序或工具函数中以至于没法用硬件实现，方式嵌入在应用程序或工具函数中以至于没法用硬件实现，因此，算法的执行速度就成为一个重要的考虑因素。因此，算法的执行速度就成为一个重要的考虑因素。便于分析：如果算法能够简洁地解释清楚，那么就很容易通便于分析：如果算法能够简洁地解释清楚，那么就很容易通过分析算法而找到密码分析上的弱点，也就能够对其牢固程过分析算法而找到密码分

13、析上的弱点，也就能够对其牢固程度有更大信心。度有更大信心。密码编码学网络安全第03章对称密码体制(第四讲319)142022-3-71.4 Feistel解密算法RD15=LE1 LD15=RE1 LD16=RE0 输出(明文) 输入(密文) RD16=LE0 RD14=LE2 F F K1 K2 LD14=RE2 RD0=LE16 RD1=LE15 RD14=LE14 F F K15 LD1=RE15 K16 LD2=RE14 LD0=RE16 LD16=RE0 RD16=LE0 输出(密文) RE16 LE16 LE1 输入(明文) LE0 F F K1 RE0 K2 RE1 RE2 LE

14、2 LE15 LE14 F F K15 RE14 K16 RE15 RE16 LE16 密码编码学网络安全第03章对称密码体制(第四讲319)152022-3-7FeistelFeistel密码的解密过程与其加密过程实质是相同的。密码的解密过程与其加密过程实质是相同的。以密文作为算法的输入，但是以相反的次序使用子密钥以密文作为算法的输入，但是以相反的次序使用子密钥K Ki i。这就是说在第一轮用。这就是说在第一轮用K Kn n，在第二轮用，在第二轮用k kn-1n-1，如此等等，如此等等，直到在最后一轮使用直到在最后一轮使用K K1 1。 密码编码学网络安全第03章对称密码体制(第四讲319)

15、162022-3-7证明：证明：设：LEi和REi表示加密过程中各个阶段的数据 LDi和RDi表示解密过程中各个阶段的数据则：LE16RE15 RE16=LE15 F(RE15，K16) LD1=RD0=LE16=RE15 RD1=LD0 F(RD0，K16) =RE16 F(RE15，K16) LE15 F(RE15，K16) F(RE15，K16) 由于：A B C = A B C D D = 0 E 0 = E 故： RD1=LE15通式： 由于：LEi = REi-1 REi = LEi-1 F(REi-1，Ki) 因此：REi-1 = LEi LEi-1 = REi F(REi-1，

16、Ki) = REi F(LEi，Ki) RD15=LE1 LD15=RE1 LD16=RE0 输出(明文) 输入(密文) RD16=LE0 RD14=LE2 F F K1 K2 LD14=RE2 RD0=LE16 RD1=LE15 RD14=LE14 F F K15 LD1=RE15 K16 LD2=RE14 LD0=RE16 LD16=RE0 RD16=LE0 密码编码学网络安全第03章对称密码体制(第四讲319)172022-3-72. 2. 简化的数据加密标准简化的数据加密标准S-DESS-DESDES-Data Encryption Standard DES-Data Encrypti

17、on Standard (1977(1977年元月年元月1515日日- -美国联邦标准）美国联邦标准） 19981998年被破解。年被破解。Simplified DESSimplified DES方案，简称方案，简称S-DESS-DES方案。方案。1.1. 加密算法涉及五个函数：加密算法涉及五个函数： (1)(1)初始置换初始置换IP(initial permutation) IP(initial permutation) (2)(2)复杂函数复杂函数f fk1k1，它是依赖于密钥，它是依赖于密钥K K，具有置换和替换，具有置换和替换的运算。的运算。 (3)(3)置换函数置换函数SW SW (

18、4)(4)复杂函数复杂函数f fk2 k2 (5)(5)初始置换初始置换IPIP的逆置换的逆置换IPIP-1-1密码编码学网络安全第03章对称密码体制(第四讲319)182022-3-7 10 bit 密钥 加密 解密 8 bit 明文规定 8 bit 密文 K1 K1 8 bit 密文 8 bit 明文规定 K2 K2 P10 移位 P8 移位 P8 IP fK fK fK fK IP-1 SW SW IP IP-1 密码编码学网络安全第03章对称密码体制(第四讲319)192022-3-72.2.加密算法的数学表示：加密算法的数学表示： IPIP-1-1* *f fk2k2* *SWSW*

19、 *f fk1k1* *IPIP 也可写为也可写为 密文密文=IP=IP-1-1（f fk2k2(SW(f(SW(fk1k1(IP(IP(明文明文) ) 其中其中 K K1 1=P8(=P8(移位移位(P10(P10(密钥密钥K) K) K K2 2=P8(=P8(移位移位( (移位移位(P10(P10(密钥密钥K) K) 解密算法的数学表示：解密算法的数学表示： 明文明文=IP=IP-1-1（f fk1k1(SW(f(SW(fk2k2(IP(IP(密文密文)密码编码学网络安全第03章对称密码体制(第四讲319)202022-3-7（1 1） S-DESS-DES的密钥生成：的密钥生成： 10

20、 bit 密钥 K1 K2 5 5 8 10 P10 LS-1 P8 LS-2 LS-2 LS-1 P8 5 5 5 5 8 密码编码学网络安全第03章对称密码体制(第四讲319)212022-3-7（1 1） S-DESS-DES的密钥生成：的密钥生成： 设设10bit10bit的密钥为（的密钥为（k k1 1,k,k2 2,k,k3 3,k,k4 4,k,k5 5,k,k6 6,k,k7 7, k, k8 8,k,k9 9,k,k1010) ) 置换置换P10P10是这样定义的是这样定义的 P10(kP10(k1 1,k,k2 2,k,k1010)=(k)=(k3 3,k,k5 5,k,k

21、2 2,k,k7 7,k,k4 4,k,k1010,k,k1 1,k,k9 9,k,k8 8,k,k6 6) ) 相当于相当于 P10= P10= LS-1LS-1为循环左移，在这里实现左移为循环左移，在这里实现左移1 1位位; ; LS-2 LS-2为循环左移，在这里实现左移为循环左移，在这里实现左移2 2位位; ; P8= P8= 若若K K选为选为( (1010000010), ), 产生的两个子密钥分别为产生的两个子密钥分别为K K1 1=(=(1 0 1 0 0 1 0 0),K),K2 2=(=(0 1 0 0 0 0 1 1) )6891104725310987654321910

22、58473687654321密码编码学网络安全第03章对称密码体制(第四讲319)222022-3-7(2)S-DES(2)S-DES的加密运算的加密运算: :初始置换用初始置换用IPIP函数函数: :末端算法的置换为末端算法的置换为IPIP的逆置换的逆置换: :易见易见IPIP-1-1(IP(X)=X (IP(X)=X 3 5 7 4 2 1 8 6 IP 3 5 7 4 2 1 8 6 IP-1 密码编码学网络安全第03章对称密码体制(第四讲319)232022-3-7(3)S-DES(3)S-DES加密图加密图 8 bit 密密文 IP-1 SW 8 8 2 2 4 4 4 E/P S0

23、 S1 P4 fK K2 4 4 4 8 F 8 8 2 2 4 4 4 8 bit 明文明文 E/P IP S0 S1 P4 fK K1 8 4 4 4 F 密码编码学网络安全第03章对称密码体制(第四讲319)242022-3-7函数函数f fk k，是加密方案中的最重要部分，它可表示为：，是加密方案中的最重要部分，它可表示为： f fk k(L,R)=(L(L,R)=(L F(R,SK),R)F(R,SK),R)其中其中L L，R R为为8 8位输入位输入, , 左右各为左右各为4 4位位, F, F为从为从4 4位集到位集到4 4位集的位集的一个映射一个映射, , 并不要求是一一映射的

24、。并不要求是一一映射的。SKSK为子密钥。为子密钥。对映射对映射F F来说：来说：首先输入是一个首先输入是一个4 4位数（位数（n n1 1,n,n2 2,n,n3 3,n,n4 4），第一步运算是扩张），第一步运算是扩张/ /置换置换（E/PE/P）运算：）运算： 事实上，它的直观表现形式为：事实上，它的直观表现形式为： 2 3 2 4 3 1 4 1 E/P 13432124nnnnnnnn密码编码学网络安全第03章对称密码体制(第四讲319)252022-3-78-bit8-bit子密钥：子密钥：K1=(kK1=(k1111,k,k1212,k,k1313,k,k1414,k,k1515

25、,k,k1616,k,k1717,k,k1818),),然后与然后与E/PE/P的结果作异或运算得：的结果作异或运算得：把它们重记为把它们重记为8 8位：位：上述第一行输入进上述第一行输入进S S盒盒S0S0，产生，产生2-2-位的输出；第二行的位的输出；第二行的4 4位输位输入进入进S S盒盒S1S1，产生，产生2-2-位的输出。两个位的输出。两个S S盒按如下定义：盒按如下定义：181143174163132121152114knknknknknknknkn3 , 13 , 02, 11 , 12, 01 , 00, 10, 0pppppppp23133120012323010S30120

26、103310232101S密码编码学网络安全第03章对称密码体制(第四讲319)262022-3-7S S盒按下述规则运算：盒按下述规则运算：将第将第1 1和第和第4 4的输入比特做为的输入比特做为2bit2bit数，指示为数，指示为S S盒的一个行；盒的一个行；将第将第2 2和第和第3 3的输入比特做为的输入比特做为S S盒的一个列。如此确定为盒的一个列。如此确定为S S盒矩阵的（盒矩阵的（i,ji,j）数。）数。例如：（例如：（P P0,0, 0,0, P P0,30,3）=(00),=(00),并且并且(P(P0,10,1,P,P0,20,2)=(1 0)=(1 0)确定了确定了S0S0

27、中的第中的第0 0行行2 2列（列（0 0，2 2）的系数为）的系数为3 3，记为（，记为（1 11 1）输出。输出。由由S0, S1S0, S1输出输出4-bit4-bit经置换经置换它的输出就是它的输出就是F F函数的输出。函数的输出。 3 1 2 4 P4 密码编码学网络安全第03章对称密码体制(第四讲319)272022-3-7(4)S-DES(4)S-DES的安全性分析的安全性分析无法抗强力攻击无法抗强力攻击具有一定的抗密码分析能力具有一定的抗密码分析能力置换和加法操作都是线性映射置换和加法操作都是线性映射 非线性来自于非线性来自于S S盒子盒子 设：设： S S盒子盒子 输入为输入

28、为( (p p0,00,0，p p0,10,1，p p0,20,2，p p0,30,3) = () = (a a，b b，c c，d d) ) 和和( (p p1,01,0，p p1,11,1，p p1,21,2，p p1,31,3) = () = (w w，x x，y y，z z) ) S S盒子输出为盒子输出为( (q q，r r，s s，t t) ) 则：则：q q = = abcdabcd + + abab + + acac + + b b + + d d （模（模2 2加）加） r r = = abcdabcd + + abdabd + + abab + + acac + + ada

29、d + + a a + + c c +1 +1 （模（模2 2加）加）线性映射和非线性映射交替使用将产生复杂的密文比特多线性映射和非线性映射交替使用将产生复杂的密文比特多项式，其复杂性可用项式，其复杂性可用8 8个包含个包含1010个未知数的非线性方程表个未知数的非线性方程表示，每一个方程大约有示，每一个方程大约有2 29 9个项个项 （含有（含有1010个二进制未知数个二进制未知数的一个多项式方程可以有的一个多项式方程可以有2 21010个可能的项个可能的项 ）。）。密码编码学网络安全第03章对称密码体制(第四讲319)282022-3-7背景背景发明人：美国发明人：美国IBMIBM公司公司

30、 W. Tuchman W. Tuchman 和和 C. Meyer C. Meyer 1971-1972 1971-1972年研制成功年研制成功基础：基础：19671967年美国年美国Horst FeistelHorst Feistel提出的理论提出的理论产生：美国国家标准局（产生：美国国家标准局（NBS)1973NBS)1973年年5 5月到月到19741974年年8 8月两次发布月两次发布通告，通告， 公开征求用于电子计算机的加密算法。经评选从一大批公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了算法中采纳了IBMIBM的的LUCIFERLUCIFER方案方案标准化：标准化：

31、DESDES算法算法19751975年年3 3月公开发表，月公开发表，19771977年年1 1月月1515日由美国国日由美国国家标准局颁布为数据加密标准家标准局颁布为数据加密标准( Data Encryption Standard ),( Data Encryption Standard ),于于19771977年年7 7月月1515日生效日生效3. 3. 数据加密标准数据加密标准DESDES密码编码学网络安全第03章对称密码体制(第四讲319)292022-3-7背景背景美国国家安全局（美国国家安全局（NSA, National Security Agency)NSA, National

32、Security Agency)参与了美参与了美国国家标准局制定数据加密标准的过程。国国家标准局制定数据加密标准的过程。NBSNBS接受了接受了NSANSA的某些的某些建议，对算法做了修改，并将密钥长度从建议，对算法做了修改，并将密钥长度从LUCIFERLUCIFER方案中的方案中的128128位压缩到位压缩到5656位位19791979年，美国银行协会批准使用年，美国银行协会批准使用DESDES19801980年，年，DESDES成为美国标准化协会成为美国标准化协会(ANSI)(ANSI)标准标准19841984年年2 2月，月，ISOISO成立的数据加密技术委员会成立的数据加密技术委员会(

33、SC20)(SC20)在在DESDES基础基础上制定数据加密的国际标准工作上制定数据加密的国际标准工作密码编码学网络安全第03章对称密码体制(第四讲319)302022-3-7nDESDES利用利用5656比特串长度的密钥比特串长度的密钥K K来加密长度为来加密长度为6464位的明文，得到位的明文，得到长度为长度为6464位的密文位的密文n该算法分三个阶段实现：该算法分三个阶段实现：1. 1. 给定明文给定明文X X，通过一个固定的初始置换，通过一个固定的初始置换IPIP来排列来排列X X中的位，中的位，得到得到X X0 0。 X X0 0=IP=IP（X X）=L=L0 0R R0 0其中其

34、中L L0 0由由X X0 0前前3232位组成，位组成，R R0 0由由X X0 0的后的后3232位组成。位组成。2.2.计算函数计算函数F F的的1616次迭代次迭代, , 根据下述规则来计算根据下述规则来计算L Li iR Ri i(1=i=16(1=i=16） L Li i=R=Ri-1i-1, Ri=L, Ri=Li-1i-1 F(R F(Ri-1i-1, K, Ki i) )其中其中K Ki i是长为是长为4848位的子密钥。子密钥位的子密钥。子密钥K K1 1，K K2 2，K K1616是作为密是作为密钥钥K K（5656位）的函数而计算出的。位）的函数而计算出的。 3.3.

35、对比特串对比特串R R1616L L1616使用逆置换使用逆置换IPIP-1-1得到密文得到密文Y Y。 Y=IP Y=IP-1-1（R R1616L L1616）密码编码学网络安全第03章对称密码体制(第四讲319)312022-3-7DESDES加密加密流程图流程图 K2 K16 K1 循环左移 循环左移 循环左移 置换选择 1 置换选择 2 置换选择 2 第 16 轮 初始置换 第 1 轮 置换选择 2 第 2 轮 32 bit 对换 逆初始置换 64 bit 明文 56 bit 密钥 64 bit 密文 密码编码学网络安全第03章对称密码体制(第四讲319)322022-3-7初始置换

36、及逆初始置换初始置换及逆初始置换初始置换初始置换IP58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157逆初始置换逆初始置换IP-140848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725密码编码学网络安全第03章对称密码体制(第四

37、讲319)332022-3-7IPIP和和IPIP-1-12014MM1420MMIPIP1密码编码学网络安全第03章对称密码体制(第四讲319)342022-3-7DES的一轮迭代37密码编码学网络安全第03章对称密码体制(第四讲319)352022-3-7选择压缩运算选择压缩运算41密码编码学网络安全第03章对称密码体制(第四讲319)362022-3-7一轮加密通式 Li = Ri-1Ri = Li-1 F(Ri-1, Ki) 一轮加密扩展置换及P置换扩展置换扩展置换E32 123454567898910 11121312 13 14 15161716 17 18 19202120 21

38、 22 23242524 25 26 27282928 29 30 31321P置换置换16720 21 29 12 28 17115 23 26518 31 102824 14 32 273919 13 30622 11425密码编码学网络安全第03章对称密码体制(第四讲319)372022-3-7扩展置换-盒32位扩展到48位扩展39密码编码学网络安全第03章对称密码体制(第四讲319)382022-3-7nF(RF(R，K)K)的计算的计算n S S盒选取盒选取每一个每一个S S盒都接受盒都接受6 6个比特作为输入并产生个比特作为输入并产生4 4个比特作为输个比特作为输出。出。 输入的第

39、一和最后一个比特构成一个输入的第一和最后一个比特构成一个2 2位二进制数，用来位二进制数，用来选择由选择由S Si i表中的四行所定义的四种替代的一种，中间的表中的四行所定义的四种替代的一种，中间的4 4个比特则选出一列。个比特则选出一列。 P S1 48 bit 32 bit R(32 bit) S2 S3 S4 S5 S6 S7 S8 K(48 bit) E 密码编码学网络安全第03章对称密码体制(第四讲319)392022-3-7nS S盒定义盒定义S215181461134972131205103134715281412011069115014711104131581269321513

40、81013154211671205149S11441312151183106125907015741421311061211953841148136211151297310501512824917511314100613S47131430691012851112415138115615034721211014910690121171315131452843150610113894511127214S31009146315511312711428137093461028514121115113649815301112125101471101306987415143115212密码编码学网络安全第

41、03章对称密码体制(第四讲319)402022-3-7S S-盒的构造盒的构造1 2 3 4 5 61 6262 3 4 521133 911001110019bbbbbbbbSbbbb行 ：-盒 子 行列列 ：值 ： 14=1100密码编码学网络安全第03章对称密码体制(第四讲319)412022-3-7n密钥的产生置换选择置换选择157494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124置换选择置换选择2141711241532815621

42、1023191242681672720132415231374755304051453348444939563453464250362932左移调度左移调度循环序号12345678910111213141516转动比特数 1122222212222221密码编码学网络安全第03章对称密码体制(第四讲319)422022-3-7子密钥的产生子密钥的产生64 位 密 钥密钥表的计算逻辑循环左移：置换选择 112311291011122C 0 （ 2 8 位 ）循环左移D 0 （ 2 8 位 ）循环左移4567822222121314151622221C 1 （ 2 8 位 ）D 1 （ 2 8 位

43、 ）（ 56 位 ） 置 换 选 择 2k 1(48 位 )循环左移C i （ 2 8 位 ）循环左移D i （ 2 8 位 ）（ 56 位 ）置换选择 2k i（ 48 位 ）密码编码学网络安全第03章对称密码体制(第四讲319)432022-3-7nDESDES加密的示例加密的示例取取1616进制明文进制明文X X：0123456789ABCDEF0123456789ABCDEF密钥密钥K K为：为：133457799BBCDFF1133457799BBCDFF1去掉奇偶校验位以二进制形式表示的密钥是去掉奇偶校验位以二进制形式表示的密钥是111111111000111111111000应用

44、应用IPIP，我们得到：，我们得到：L L0 0=1111111111=1111111111L L1 1=R=R0 0=1111101010=1111101010然后进行然后进行1616轮加密。轮加密。最后对最后对L L1616, R, R1616使用使用IPIP-1-1得到密文：得到密文：85E813540F0AB40585E813540F0AB405密码编码学网络安全第03章对称密码体制(第四讲319)442022-3-7nDESDES的雪崩效应的雪崩效应 P P置换的目的是提供雪崩效应置换的目的是提供雪崩效应: : 明文或密钥的一点小的变动都引起密文的较大变化明文或密钥的一点小的变动都引

45、起密文的较大变化明文变化的影响明文变化的影响明文明文1 1：0 00000 00000 00000 00000 0000 00000 00000 00000 明文明文2 2：1 10000 00000 00000 00000 0000 00000 00000 00000 密钥：密钥：0000001 1001011 0100100 1100010 0011100 0011000 0011100 0000001 1001011 0100100 1100010 0011100 0011000 0011100 0110010 0110010 密钥变化的影响密钥变化的影响 明文明文:01101 0010

46、111 01111 01110110 11101 :01101 0010111 01111 01110110 11101 密钥密钥1 1：1 1110010 1111011 1101111 0011000 0011101 0000100 0110110010 1111011 1101111 0011000 0011101 0000100 0110 密钥密钥2 2：0 0110010 1111011 1101111 0011000 0011101 0000100 0110 110010 1111011 1101111 0011000 0011101 0000100 0110 密码编码学网络安全第

47、03章对称密码体制(第四讲319)452022-3-7DES的雪崩效应 明文的变化明文的变化 循环 不同比特的个数 01162213354395346327318299421044113212301330142615291634密钥的变化密钥的变化 循环 不同比特的个数 00122143284325306327358349401038113112331328142615341635密码编码学网络安全第03章对称密码体制(第四讲319)462022-3-7nDESDES的争论的争论密钥长度密钥长度最初最初IBMIBM设计设计LuciferLucifer时的钥长为时的钥长为128128位，当位，当

48、DESDES成为标准时有效成为标准时有效长度缩减为长度缩减为5656位，要求增加钥长的争论主要是针对蛮力攻击的位，要求增加钥长的争论主要是针对蛮力攻击的可能性。可能性。 nDESDES的争论的争论DESDES设计标准设计标准NSANSA告诫告诫DESDES的设计者，代替和换位变换等的设计标准是的设计者，代替和换位变换等的设计标准是“敏感敏感”的，并要求的，并要求IBMIBM公司不要公布这些信息和数据。公司不要公布这些信息和数据。nDESDES的争论的争论选代次数选代次数 在在8 8轮迭代之后，密文基本上就是每一明文位和密钥位的随机函数，为什么轮迭代之后，密文基本上就是每一明文位和密钥位的随机函

49、数，为什么算法不在算法不在8 8轮之后停止？轮之后停止？ nDESDES的争论的争论抗差分分析抗差分分析差分分析表明任何少于差分分析表明任何少于1616次迭代的次迭代的DESDES算法都可以用比穷举法更有效的方法算法都可以用比穷举法更有效的方法破译，而破译，而DESDES恰巧为恰巧为1616次迭代，这是偶然的巧合吗？差分分析方法是以色列次迭代，这是偶然的巧合吗？差分分析方法是以色列学者学者E. BihamE. Biham和和A. ShamirA. Shamir在在19901990年发明的，但据称年发明的，但据称IBMIBM在在19741974年就掌握了年就掌握了这种差分分析方法。这种差分分析方

50、法。密码编码学网络安全第03章对称密码体制(第四讲319)472022-3-7nDESDES的争论的争论SS盒盒DESDES的核心是的核心是S S盒，除此之外的计算是属线性的。盒，除此之外的计算是属线性的。S S盒作为该密码体制的非盒作为该密码体制的非线性组件对安全性至关重要。线性组件对安全性至关重要。19761976年美国年美国NSANSA提出了下列几条提出了下列几条S S盒的设计准则：盒的设计准则：1. S1. S盒的每一行是整数盒的每一行是整数0 0，1515的一个置换的一个置换2. 2. 没有一个没有一个S S盒是它输入变量的线性函数盒是它输入变量的线性函数3.3.改变改变S S盒的一

51、个输入位至少要引起两位的输出改变盒的一个输入位至少要引起两位的输出改变4.4.对任何一个对任何一个S S盒和任何一个输入盒和任何一个输入X X，S S（X X）和）和 S(XS(X 001100001100）至少有两个）至少有两个 比特不同（这里比特不同（这里X X是长度为是长度为6 6的比特串）的比特串）5.5.对任何一个对任何一个S S盒，对任何一个输入对盒，对任何一个输入对e,fe,f属于属于0,1,S(X) S(X0,1,S(X) S(X e ef00)f00)6.6.对任何一个对任何一个S S盒，如果固定一个输入比特，来看一个固定输出比特的值盒，如果固定一个输入比特，来看一个固定输出

52、比特的值, , 这个输出比特为这个输出比特为0 0的输入数目将接近于这个输出比特为的输入数目将接近于这个输出比特为1 1的输入数目。的输入数目。盒子的设计标准（其实也就是整个算法的设计标准）并未公开，人们怀疑盒子的设计标准（其实也就是整个算法的设计标准）并未公开，人们怀疑这些盒子的设计可能隐藏着一种可以使得了解这些盒子的设计可能隐藏着一种可以使得了解S S盒子弱点的敌对方成功盒子弱点的敌对方成功进行密码分析的隐患。这种可能性使人心神不安，而且这么多年以来的确进行密码分析的隐患。这种可能性使人心神不安，而且这么多年以来的确有不少有不少S S盒子的规律性以及未曾料到的行为被发现。尽管如此，至今还没

53、盒子的规律性以及未曾料到的行为被发现。尽管如此，至今还没有人成功地发现有人成功地发现S S盒子想象中的致命缺陷（至少没有人公开承认这样一个盒子想象中的致命缺陷（至少没有人公开承认这样一个发现）。发现）。 密码编码学网络安全第03章对称密码体制(第四讲319)482022-3-7DESDES的强度的强度n 5656位密钥位密钥长度问题（密钥容量），且各次迭代中使用长度问题（密钥容量），且各次迭代中使用的密钥的密钥K K（i i）是递推产生的。是递推产生的。n S S盒子盒子设计标准未公开（但有部分准则）设计标准未公开（但有部分准则）n 加密单位仅有加密单位仅有6464位二进制，这对于数据传输来说

54、太小，因位二进制，这对于数据传输来说太小，因为每个区组仅含为每个区组仅含8 8个字符，而且其中某些位还要用于奇偶个字符，而且其中某些位还要用于奇偶校验或其他通讯开销。校验或其他通讯开销。密码编码学网络安全第03章对称密码体制(第四讲319)492022-3-7强力攻击：强力攻击：2 25555次尝试次尝试差分密码分析法：差分密码分析法：2 24747次尝试次尝试线性密码分析法：线性密码分析法：2 24343次尝试次尝试n 其他加密标准（其他加密标准（3-3-DES IDEADES IDEA）n 新加密标准（新加密标准（Advanced Encryption StandardAdvanced E

55、ncryption Standard：AESAES）可随可随机产生机产生128128、192192或或256256位密钥为信息加密。位密钥为信息加密。n 如能如能1 1秒内破解秒内破解DESDES密码，那么用这种计算机来破解密码，那么用这种计算机来破解AESAES的的128128位算法的密码仍需要位算法的密码仍需要149149万亿年。万亿年。DESDES的强度的强度密码编码学网络安全第03章对称密码体制(第四讲319)502022-3-7DESDES密钥长度密钥长度关于关于DESDES算法的另一个最有争议的问题就是担心实际算法的另一个最有争议的问题就是担心实际5656比特的密钥长度不足以抵御穷

56、举式攻击，因为密钥量只比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有有 个个 早在早在19771977年，年，DiffieDiffie和和HellmanHellman已建议制造一个每秒能已建议制造一个每秒能测试测试100100万个密钥的万个密钥的VLSIVLSI芯片。每秒测试芯片。每秒测试100100万个密钥的万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要制造这样的机器大约需要20002000万美元万美元1756102密码编码学网络安全第03章对称密码体制(第四讲319)512022-3-7DESDES密钥长

57、度密钥长度在在CRYPTO93CRYPTO93上，上，SessionSession和和WienerWiener给出了一个非常详细的密给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以芯片，所以1616次加密能同时完成。花费次加密能同时完成。花费1010万美元，平均用万美元，平均用1.51.5天左右就可找到天左右就可找到DESDES密钥密钥美国克罗拉多洲的程序员美国克罗拉多洲的程序员VerserVerser从从19971997年年2 2月月1818日起，用了日起，用了9696天时间，在天时间，在Internet

58、Internet上数万名志愿者的协同工作下，成功地上数万名志愿者的协同工作下，成功地找到了找到了DESDES的密钥，赢得了悬赏的的密钥，赢得了悬赏的1 1万美元万美元密码编码学网络安全第03章对称密码体制(第四讲319)522022-3-7DESDES密钥长度密钥长度19981998年年7 7月电子前沿基金会（月电子前沿基金会（EFFEFF）使用一台使用一台2525万美圆的电万美圆的电脑在脑在5656小时内破译了小时内破译了5656比特密钥的比特密钥的DESDES19991999年年1 1月月RSARSA数据安全会议期间，电子前沿基金会用数据安全会议期间，电子前沿基金会用2222小小时时151

59、5分钟就宣告破解了一个分钟就宣告破解了一个DESDES的密钥的密钥密码编码学网络安全第03章对称密码体制(第四讲319)532022-3-74. 4. 差分分析和线性分析差分分析和线性分析n差分密码分析差分密码分析Differential CryptanalysisDifferential Cryptanalysis历史历史 19901990年，年，MurphyMurphy、BihamBiham和和ShamirShamir首次提出用差分密码分析攻击分组首次提出用差分密码分析攻击分组密码和散列函数，是第一种可以以少于密码和散列函数，是第一种可以以少于2 25555的复杂性对的复杂性对DESDES

60、进行破译的方进行破译的方法。法。 Differential Cryptanalysis compares two related pairs of Differential Cryptanalysis compares two related pairs of encryptions.encryptions.差分密码分析攻击方法差分密码分析攻击方法with a known difference in the input, searching for a known with a known difference in the input, searching for a known diffe