第三章 分组密码与数据加密标准

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,密码编码学与网络安全,福州大学软件学院 林宇峰,Lin_yfyahoo,第三章 分组密码和数据加密标准,分组密码原理,现在使用的大多数对称分组密码加密算法都是基于,Feistel,分组密码结构。,流密码和分组密码,流密码,：每次加密数据流的一位或一个字节,vigenere,密码和,vernam,密码（古典）,分组密码,：将一个明文组作为整体加密，并且通常得到的是与之等长的密文组。（典型的有,64,位和,128,位，应用更加广泛些，常规的加密通常应用到分组加密，这是本书讨论的内容）,注：第六章会提到两者的等效问题。,Feistel,设计的动机,可逆与不可逆,可逆的映射,明文,密文,00,11,01,10,10,00,11,01,不可逆的映射,明文,密文,00,11,01,10,10,01,11,01,加密的变换要可逆的，或者称为非奇异的。（不同变换总数为,2,n,！）,变换（映射）的总数：,2,n,！,N=4,的一个普通代换密码结构,矛与盾,较小的分组：,1.,密码系统等价于传统的代换密码,2.,利用统计分析法破解（轻而易举）,3.,脆弱性的来源：小，而非代换,4.,若,n,充分大，且有可逆变换，掩盖统计学特征,大规模分组,1.,密钥的确定,n=4,：,4*16=64,；,n=64,：,64*2,64,=2,70,密钥长度,：,n*2,n,，变换为,2,n,！,Feistel,设想,n,很大时，近似一个理想分组密码，使之能够用容易的部分组合起来。,思想：用,乘积密码,的方式近似简单的替代密码,乘积密码：以某种方式连续使用多个密码，使所得的结果比使用单一密码的强度更大。（,实质,）,扩散和混淆,扩散与混淆,理想密码：密文的所有统计特征多与所用的密钥 无关,扩散：明文的统计学特征在密文中消失。,1.,让每个明文数字尽可能多得去影响密文（等价）,2.,使得密文中的单、双字母的频率接近于平均,混淆：尽可能的是密文和密钥之间的关系变复杂，阻止攻击者发现密钥。,本质性,的体现。,Feistel(DES),加密框架,明文分组的长,n,2w,分左右两半,L,0,R,0,密钥,K,产生子钥：,Kk,1,，,k,2,，,，,k,r,r,是轮数，比如,16,轮,是异或函数,XOR,pxx=p,函数,F,是散列混乱函数,可以是手工精心构造的查表函数,Feistel,网络,Feistel,解密,Feistel for Loop,加密计算序列,L,0,左半,R,0,右半,L,1,R,0,R,1,L,0,F(k,1,R,0,),L,2,R,1,R,2,L,1,F(k,2,R,1,),L,3,R,2,R,3,L,2,F(k,3,R,2,),L,i,R,i-1,R,i,L,i-1,F(k,i,R,i-1,),L,n,R,n-1,R,n,L,n-1,F(k,n,R,n-1,),密文即（,L,n,，,R,n,）,解密计算,2,轮解密举例,假设,n,2,轮，,C,（,L2,，,R2,）,加密,明文半半,L0+R0,L1,R0 R1,L0F(k1,R0),L2,R1R2,L1F(k2,R1),解密,密文半半,L2,R2,R1,L2L1,R2F(k2,R1),R0,L1L0,R1F(k1,R0),明文,L0,R0,L1,R2F(k2,R1),L1F(k2,R1)F(k2,R1),L1,L0,R1F(k1,R0),L0F(k1,R0)F(k1,R0),L0,Feistel,参数特性,分组大小,密钥大小,循环次数,一般仅几轮是不够的，得十几轮才好，如,16,轮,子钥产生算法,越复杂越好,轮函数,Round,关键,其他考虑,速度（尤其是软件实现的速度）,便于分析（使用简洁的结构）,数据加密标准,DES,DES,是为美国政府研制的，并建议普通大众采用,它已经被美国和其他一些国家作为官方加密标准,很多软件和硬件加密系统都是根据,DES,进行设计,然而，人们开始对其充分性（即安全性）开始表示怀疑（在,1977,年，,Diffie,和,Hellman,提出，,56,位密钥过于短小。）,谈谈历史,20,世纪,70,年代,NBS,的意识,国防部和联邦政府的任务委派给,NBS,同时，几家主要的软硬件公司也在研制加密设备，有通过软硬件进行实现的。,问题：产生了加密技术商业增值的难度，这个难度在于“交换”,两个设备用户无法交换他们的加密信息。,很快人们明白了，加密应该被,号召的发起,NBS,在,1972,年发出号召，征集制定公开加密算法的意见，并提出了算法的标准：,1.,能提供高度的安全性，说明详细且易于理解,2.,可发布，这样安全性不依赖于算法的保密性,3.,可用于所有用户,4.,可适用于不同的应用,5.,用电子设备实现起来比较经济,6.,使用有效,7.,可验证，可输出等,NBS,原本的打算,，,IBM,的,Lucifer,算法,IBM,的,Lucifer,算法,20,世纪,60,年代后期，,IBM,成立了计算机密码学研究项目，并在,1971,年研制成功,Lucifer,算法,Lucifer,算法是分组长度为,64,位，密钥长度为,128,位，具有,Feistel,结构的分组密码。,Lucifer,修订版本：为了能够适合芯片的实现，同时抗击密码分析的能力更为强大，将密钥减少到,56,位，因而很适合在单片机环境下使用。,1973,年提交,Tuchman-Meyer,方案，,1977,年,NBS,将这个最好的方案采纳为,DES,未平息的激烈批评,128,56,，担心密钥太短，经受不起穷举攻击,DES,内部结构的问题：,S,盒子的设计标准被纳入官方标准。,差分分析方面的工作表明，,DES,内部结构是很完美的。,安全性,1977,年提出，,56,位密钥太小，当时机器没有办法对,2,的,56,次方进行测试。,2019,年，研究者用,3500,台计算机并行计算，在,4,个月内推出一个密钥。,2019,年，研究者制造出一台大约,100 000,美元的机器“,DES cracker”,能够在,4,天内找到一个,DES,的密钥,2019,年，,NBS,开始寻找,AES,（新，更有力）,DES,加密算法,密钥置换选择,-1,57 49 41 33 25 17 9 8,1 58 50 42 34 26 18 16,10 2 59 51 43 35 27 24,19 11 3 60 52 44 36 32,63 55 47 39 31 23 15 40,7 62 54 46 38 30 22 48,14 6 61 53 45 37 29 56,21 13 5 28 20 12 4 64,78,K,的,56,比特重新排列，成为,C,0,D,0,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,33 34 35 36 37 38 39 40,41 42 43 44 45 46 47 48,49 50 51 52 53 54 55 56,57 58 59 60 61 62 63 64,Key,i,(48bit),C0D0,C15D15,PC-2,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,86,未入选的：,9,、,18,、,22,等,每轮从,56,比特中选取,48,比特即为,Ki,，并同时左移,Bits rotated 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1,初始置换及逆置换,Initial Permutation,（,IP/IP,-1,）,58 50 42 34 26 18 10 2,60 52 44 36 28 20 12 4,62 54 46 38 30 22 14 6,64 56 48 40 32 24 16 8,57 49 41 33 25 17 9 1,59 51 43 35 27 19 11 3,61 53 45 37 29 21 13 5,63 55 47 39 31 23 15 7,40 8 48 16 56 24 64 32,39 7 47 15 55 23 63 31,38 6 46 14 54 22 62 30,37 5 45 13 53 21 61 29,36 4 44 12 52 20 60 28,35 3 43 11 51 19 59 27,34 2 42 10 50 18 58 26,33 1 41 9 49 17 57 25,初始明文按照,IP,重排；,16,轮后的密文按照,IP,-1,重排即为最后密文,odd,even,轮,One Round,扩展置换,Expansion Permutation,32 1 2 3 4 5,4 5 6 7 8 9,8 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,R,i,的,32bit 48bit,两边的是重复选中的,68,轮函数,Round Function,S,盒,S-Boxes,：,1/4,两边,2,比特选择行号,中间,4,比特选择列号,从,S,盒出来后重排：,Permutation Function,P 84,16 7 20 21 29 12 28 17,1 15 23 26 5 18 31 10,2 8 24 14 32 27 3 9,19 13 30 6 22 11 4 25,DES-Review,DES,安全强度,对,DES,的争议集中在,密钥空间太小,Key space,从,Lucifer,的,2128,降到,DES,的,256,DES Challenge III,22 hours 15 minutes,S,盒,S-Boxes,S,盒的设计准则？,陷门？,trapdoors by NSA (?),“Form surprise to suspicion”,从惊喜,(,甚至能够抵御很后来才发现的各种攻击,),到怀疑,(n,年前就如此厉害的,NSA,现在究竟有多厉害,),33,密钥大小,Key Size,256 71016,1Mkeys/Second means 1000 years,Special machine designed,Wiener,Cost/time table,Recent news,in 2019 on Internet in a few months(Rocke,96days),in 2019 on dedicated h/w in a few days,(DES II-2 EFF,56 hrs),in 2019 above combined in 22hrs 15 mins,“Deep Crack”by EFF,穷举,(,蛮力,),攻击,Cost/Time,表,Key search machine unitexpected search time,$100,00035 hours,$1,000,0003.5 hours,$10,000,00021 mins,wiener93efficient.pdf,A Brut