密码学-块加密法

1、第八讲,块加密法,内容纲要,块加密法模式,乘积加密法,数据加密标准（,DES,）,Cipher Structures,.,Classical,Stream,RC4,Block,Transposition,Substitution,Column,polyalphabetic,monoalphabetic,Nihilist,Vigenere,Hill,MultiLiteral,Keyword,Affine,Shift,Block Cipher,?,块加密法是最常见的加密类型,定义计算机的位块表示几个字母,一次加密整个块,Block of Bits,KEY,Algorithm,Block of Bi

2、ts,Modes of Operation,?,块加密法的三种标准模式,:,电子编码薄,(ECB),加密,-,块,-,链,(CBC),输出反馈模式,(OFM),电子编码薄,?,电子编码薄,-,最简单的模式,明文的每个块加密成密文的一个块（使,用一个密钥）,M,1,M,2,M,m,Problem:,if M,i,= M,j,then,C,i,= C,j,Key,E,k,C,1,E,k,C,2,E,k,C,m,加密,-,块,-,链,?,?,?,来自上一块的密文与当前的明文块做,XOR,运算,密文跟明文不再是一一对应的关系，破解起来更困难，,而且克服了只要简单调换密文块可能达到目的的攻击,缺点是不能

3、实时加密，必须等到每,8,个字节都接受到之,后才能开始加密，否则就不能得到正确的结果。,M,1,M,2,M,m,Key,E,k,C,1,E,k,C,2,E,k,C,m,输出反馈模式,?,使用块加密法为流加密法生成一个随机位,流，密钥和块加密法的初始输入启动加密,过程,M,i,KEY,R,i,E,k,R,i+1,C,i,General Structure,?,1973,年, Feistel,提出一种乘积加密法，它成,为今天所用的对称块加密法的体系结构基础,处理过程包括多个阶段的替换以及换位,.,主密钥分成一个子密钥集，每个阶段使用一个子,密钥,.,每个阶段中，数据块分成了左右两部分，进行交,换，

4、其中一个部分与子密钥混合，用于该阶段,.,这种类型的加密法又称为替换,置换加密法,.,Feistel Cipher,?,其中一个阶段的操作,:,Plaintext,Left Side,Right Side,Permutation,Creates the,subkey,for each stage,S,New Left Side,New Right Side,F,Substitution,Key,块加密法评估,?,任何新的加密法必须安全，能防止被人破解。但随着加,密法变得越来越复杂，如何才能确信这些加密法能保护,我们那些有价值的数据呢？,真正答案是我们永远无法确保一个加密法是安全的,.,要想知道

5、一个新的加密法是否安全，最好办法是让,安全社区的人去测试它,.,?,如果要使一个加密法让用户可接受，那么它必须具有以,下特征：,首先，密钥必须足够大，使强力攻击法无效或至少,得不偿失,.,Algorithm Strength,?,?,?,雪崩条件：任何输入位或密钥位与输出位,之间不应有任何连续，即密文中不能有内,容含有关于密钥或明文的提示。,如果有人试用不同密钥，当尝试的密钥其,中的某些位接近于实际的密钥时，不能有,任何信息提示。,猜测的密钥与实际密钥即使只有一位之差，,也应产生迥乎不同的密文。,数据加密标准,?,20,世纪,70,年代中期，美国政府认为需要一个,功能强大的标准加密系统。,由美

6、国标准局提出要求，多家公司提交建议，,最后,IBM,的,Lucifer,加密系统入选。,1977,年,根据美国国家安全局的建议进行修改,后，,Lucifer,的方案成为数据加密标准（,DES,）,后来发展成为高级加密标准,(AES),Basic Structure,?,DES,用一个,64,位的密钥来加密每个块长度为,64,位的明文,.,DES,是一个包含了,16,个阶段,的替换,置换加密法,.,DES,的密钥为,56,位的,0-1,串,这样的,0-1,串共有,2,56,种,(,大于,10,16,),通常以,7,个字母的单词形式出现,?,?,DES,将,56,的,0-1,串扩展为,64,位,其

7、中,8, 16, 24, 32, 40, 48, 56,与,64,位是添加上去的，,每个,8,位的密钥包含了用户提供的,7,位和,DES,确定的,1,位，,添加的位使得每个,8,位的块都有奇数个奇偶校验位（,1,的个数为奇数）。,Key Generation,16,个阶段中的每个阶段使用一,个,48,位的密钥，该密钥是从最,初的,64,位派生而来。,该密钥要穿过,PC-1,块，,PC-,1,块负责取出由用户提供的,56,位。,56,位分成左右两半，每一半都,左移,1,或,2,位（视每个阶段情况,不同）。,新的,56,位用,PC-2,压缩，抛弃,8,位后，为某个阶段生成一个,48,位的密钥。,6

8、4 bit key,PC-1,28 bit C,0,28 bit D,0,Left Shift,Left Shift,28 bit C,1,28 bit D,1,PC-2,K,1,Left Shift,Left Shift,交换选择,?,PC-1,从密钥中选取,56,位，按照下列方式重排,57 49 41 33 25 17 9 1 58 50 42 34 26 18,10 2 59 51 43 35 27 19 11 3 60 52 44 36,63 55 47 39 31 23 15 7 62 54 46 38 30 22,14 6 61 53 45 37 29 21 13 5 28 20

9、12 4,14 17 11 24 1 5 3 28 15 6 21 10,23 19 12 4 26 8 16 7 27 20 13 2,41 52 31 37 47 55 30 40 51 45 33 48,44 49 39 56 34 53 46 42 50 36 29 32,?,PC-2,从,56,位中选取,48,位，按照下列方式重排,DES Stages,?,DES,的每个阶段使用的是不同的子密钥,和上一阶段的输出，但执行的操作相同,.,这些操作定义在三种盒中：,扩充盒（,expansion box,，,E,盒,),替换盒（,substitution box,，,S,盒,),置换盒（,

10、the permutation box,，,P,盒,).,Example Stage,Right 32 bits,Key,Left 32 bits,E-Box,将,64,位的右边,32,位的输入扩充为,48,位；,E-Box,的输出结果与,48,位的子密钥进行,XOR,逻,辑运算，输出新的,48,位，作为,S-Box,的输入；,S-Box,有,8,种不同的盒，每个,S,盒接收一个,6,位的,输入，输出一个,4,位的输出；,P-Box,是一个简单的置换；,初始左半边的,32,位与,P,盒输出的,32,位进行,XOR,逻辑运算，结果作为下一轮的右半边,32,位；,E Box,48 bits,XOR

11、,56 bits,48 bits,Key Box,48 bits,S Boxes,32 bits,P Box,32 bits,XOR,32 bits,32 bits,E-Box,?,The EBox expands its 32-bit input into 48-,bits by duplicating some of the input bits.,Right 32 bits,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,EBox,32,1,4,8,5,2,6,3

12、,7,4,8,5,9,9,10,11,12,13,12,13,14,15,16,17,16,17,18,19,20,21,20,21,22,23,24,25,24,25,26,27,28,29,28,29,30,31,32,1,Note the duplication,S-Boxes,?,S-Boxes,真正体现了,DES,的强大：,S-Boxes,一共有,8,种,每个,S,盒接收一个,6,位的输入，输出一个,4,位的,输出,.,每个,S-box,有,16,列，,4,行,，它的每个元素是,一个,4,位的块，通常用十进制表示,Column,0 1 2 3 4 5 6 7 8 9 10 11 12

13、 13 14 15,0,14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,1,0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,Row,2,4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,3,15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13,Working with the,S-Boxes,?,一个,S-Box,的,6,位输入包含了行与列的索引,.,行索引由,1,6,位给出，列索引由,2-5,位给出,.,S-Box,的输出需要查找行,-,列索引对应的数值，将该,十进制数表示成二进制输出,I

14、nput: 0 1 1 1 1 0,Column 15,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,0,15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10,1,3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5,2,0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,5,3,13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9,Row 0,Output: 1 0 1 0,S2,P-Box,?,经过,S-Box,操作之后剩下,32,位，按照下,面的,P-Box,进行置换操作,:

15、,SBox Outputs,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,PBox,16,7,20,21,29,12,28,17,1,15,23,26,5,18,31,10,2,8,24,14,9,32,27,3,19,13,30,6,22,11,4,25,Final Step,?,?,?,最后的操作是将初始右半边的,32,位作为左半,边，而初始左半边的,32,位与,P,盒的,32,位进行,XOR,逻辑运算，并将结果作为右半边的,32,位。,该过程进行,16,轮，每轮

16、使用不用的子密钥,将,DES,一个阶段的输入和输出做一个对比，,两个位串有约多于一半的位发生了变化。,11001100 11001100 11001100 11001100 01010101 01010101 01010101 01010101,01010101 01010101 01010101 01010101 10100001 00101110 10111101 01110001,?,?,Using CAP,?,CAP provides an implementation of DES,Run,Avalanche,tests,CAP also provides a simple vers

17、ion of,DES,S-DES,?,S-DES (Simplified-DES) was,developed by Dr. Edward Schaefer at,Santa Clara University in 1996.,It is simple enough so that you can,explore the operation of DES and some,of its weaknesses.,It operates on 8-bit data blocks (in other,words, single characters) using a 10-bit,key (only

18、 2,10,= 1024 possibilities) and,two stages,Plaintext block,?,In spite,of the,simplifi,cations,S-DES,looks,much,like our,basic,DES.,10 bit key,8 bits,PC-1,IP,1 2 3 4 5 6 7 8,2 6 3 1 4 8 5 7,C,0,D,0,Left Shift 1 bit,Left Shift 1 bit,L,0,R,0,K,C,1,D,1,1,PC-2,XOR,F,Left Shift 2 bits,Left Shift 2 bits,C,

19、2,D,2,L,1,R,1,K,2,PC-2,XOR,F,L,2,R,2,IP,-1,1 2 3 4 5 6 7 8,4 1 3 5 7 2 8 6,8 bits,Ciphertext block,S-DES S-Boxes,The function F on the prior slide contains,an EBox, PBox and 2 SBoxes (much like,DES),?,The two S-Boxes are given by:,The input is a 4 bit value,?,The first and last bits,define the row,T

20、he middle bits define,the column,The output is a 2 bit value,S-DES Key Generation,?,?,?,?,The key generation mechanism begins,with a 10-bit key which is permuted by PC-,1 into the order 3 5 2 7 4 10 1 9 8 6.,It is separated into 2 five bit segments and,each segment is left shift by one bit.,PC-2 selects and rearranges 8