第13讲分组密码的整体结构ppt课件.pptx

密码学 第13讲,一口吃地球2014年4月8日,2023/1/10,密码学课件,1,分组密码的整体结构,迭代分组密码结构结构广义结构结构结构更多细化的结构分组密码工作模式,2023/1/10,密码学课件,2,分组密码的整体结构,迭代分组密码结构结构广义结构结构结构更多细化的结构分组密码工作模式,2023/1/10,密码学课件,3,迭代分组密码,如果分组密码是基于一个简单函数迭代若干次而形成，就称其为迭代密码。,2023/1/10,密码学课件,4,混乱,密钥,。,扩散,混乱,扩散,混乱,扩散,明文,密文,迭代分组密码,目前流行的分组密码均是迭代型密码,2023/1/10,密码学课件,5,密钥扩展算法,0=,(2),(1),=,(1),迭代分组密码,每次迭代称作一轮，相应的函数称作轮函数。每一轮输入都是前一轮输出的函数。=1,其中()是第轮子密钥，由秘密密钥通过密钥扩展算法产生。密钥扩展算法是将短的种子密钥扩展成若干子密钥，再将这些子密钥融合入每一轮的运算中。,2023/1/10,密码学课件,6,迭代分组密码,迭代次数（或者轮数）是迭代分组密码的一个主要参数。影响分组密码轮数选择的因素很多，主要包括以下几个因素：算法采用的整体结构。轮函数的性能。应用环境设计者对算法的安全性评估。,2023/1/10,密码学课件,7,迭代分组密码,在加密算法中，通常有前期白化和后期白化，原因是分组密码的安全性分析通常都是先猜测部分密钥比特，然后剥去密码的第一轮或最后一轮，再将攻击施加于剩下的中间轮上。一般要对密码的第一轮或者最后一轮特殊对待，给第一轮加一个密钥控制的前期变换，给最后一轮加一个密钥控制的后期变换。与种子密钥进行一次异或运算。,2023/1/10,密码学课件,8,分组密码的整体结构,迭代分组密码结构结构广义结构结构结构更多细化的结构分组密码工作模式,2023/1/10,密码学课件,9,结构,整体结构是每个分组密码的重要特征，所用整体结构对于分组密码的轮数选择、软硬件性能都有非常大的影响。整体结构的研究多采用可证明安全理论的方法，研究它们对差分、线性等分析方法的抵抗力，研究它们在一定假设下的伪随机性和超伪随机性。,2023/1/10,密码学课件,10,结构,结构可以把任何函数（通常称为轮函数）转化为一个置换。,2023/1/10,密码学课件,11,结构,对长度为2比特的输入 0|0，0 和 0 都是 比特。1=0 1=0(0,0),2023/1/10,密码学课件,12,结构,“加解密相似”是结构的实现优点，设计轮函数时可以不考虑解密的情况。对于任何的轮函数，结构都是可逆的。,2023/1/10,密码学课件,13,2023/1/10,密码学课件,14,结构,对于2轮情况证明 1=1 和 1=1 0=0 和 0=0 1=2=2=1 1=2 2,1=2 2,1=1 2,1 2,1=1 0=1=1=0 0=1 1,0=1 1,0=0 1,0 1,0=0,2023/1/10,密码学课件,15,结构,对多轮的情况假设轮,2023/1/10,密码学课件,16,2023/1/10,密码学课件,17,0,0,(0,0),0,(,),+1,+1,结构,对于轮情况，需要证明=和=1,0=+1=+1=+1+1,+1=+1+1,+1=+1,+1+1,+1=联立上述两式对做数学归纳法，=1,0。,2023/1/10,密码学课件,18,伪随机置换和超伪随机置换,分组密码是 0,1 0,1 上的一个置换，完全由密钥决定，所以分组密码一共有|种可能。如果密钥是个比特，那么就是 2 种可能。这个集合记做()而 0,1 0,1 上的所有置换共有 2!种可能。这个集合记做 2,2023/1/10,密码学课件,19,伪随机置换和超伪随机置换,2023/1/10,密码学课件,20,(),2,WORD 0,WORD 1,0?1,伪随机置换,伪随机置换和超伪随机置换,2023/1/10,密码学课件,21,(),2,WORD 0,WORD 1,0?1,超伪随机置换,结构,对于结构，有这样的结论：如果轮函数是伪随机函数，则3轮结构是伪随机的。3轮结构不是超伪随机的。4轮结构是超伪随机的。,2023/1/10,密码学课件,22,结构,假设3轮的轮函数分别是 0,1,2 在某个WORD里，我们做如下动作：3|3(0 2)0,1/0 3|3(|0)|1(3|3)=3 3,then return 0 else return 1.,2023/1/10,密码学课件,23,2023/1/10,密码学课件,24,0,0,(0,0),1,1,0,(1,1),2,2,1,(2,2),3,3,2,0=0,0 1=1,1 2=2,2,3轮结构,3|3=1 0 0|2 1 0(0)3=2(1(0),2023/1/10,密码学课件,25,3轮结构,=3 1 1=3 1 3 2 3=1 0 0 1 2 1 0 0 2 1 0 0=1 0 0 2 1 0=3 3,2023/1/10,密码学课件,26,2023/1/10,密码学课件,27,0,0,(0,0),1,1,0,(1,1),2,2,1,(2,2),3,3,2,0=0,0 1=1,1 2=2,2,分组密码的整体结构,迭代分组密码结构结构广义结构结构结构更多细化的结构分组密码工作模式,2023/1/10,密码学课件,28,结构,型密码的一轮由密钥“加”、混乱层和扩散层三部分组成。通常，混乱层由一些盒并置而成，盒为双射，轮子密钥和轮输入做异或运算。需要考虑解密函数。,2023/1/10,密码学课件,29,2023/1/10,密码学课件,30,结构,直观的看，先经过混乱层，再经过扩散层，就很接近所提出的混乱原则和扩散原则。经过多次迭代以后，会增强密码的混乱性和扩散性，使得密码的输出与输入之间的依赖关系更加复杂。和结构相比，结构可以得到更快速的扩散，更适宜高速的硬件实现。的轮数更少。,2023/1/10,密码学课件,31,分组密码的整体结构,迭代分组密码结构结构广义结构结构结构更多细化的结构分组密码工作模式,2023/1/10,密码学课件,32,广义结构,结构是左右平衡的。可以推广到非平衡的结构。通俗的讲，就是左边和右边长度不一样的结构。按输入的分组，还可以选用多个子块轮函数。,2023/1/10,密码学课件,33,2023/1/10,密码学课件,34,2,3,1,4,一型结构,2,3,1,4,二型结构,2023/1/10,密码学课件,35,2,3,1,4,三型结构,2,3,1,4,四型结构,2,1,广义结构,广义结构继承了结构“加解密相似”、轮函数不用求逆的优点。轮函数的设计规模更加灵活。7轮一型结构是伪随机的。5轮二、三型结构是伪随机的，6轮二、三型结构是超伪随机的。7轮四型结构是伪随机的，10轮四型结构是超伪随机的。,2023/1/10,密码学课件,36,分组密码的整体结构,迭代分组密码结构结构广义结构结构结构更多细化的结构分组密码工作模式,2023/1/10,密码学课件,37,结构,对长度为2的输入 1|1，1 是 1 比特，1 是 2 比特，1+2=2。=1=1 1(1)1 2 1 1|0 1 2,2023/1/10,密码学课件,38,结构,结构是借鉴结构的研究结果推广的一种整体结构。结构的优点是，当左右长度不一样时，合理选取轮函数可以使得结构达到比结构更高的安全界。缺点是轮函数的设计需要考虑解密操作。,2023/1/10,密码学课件,39,分组密码的整体结构,迭代分组密码Feistel结构SP结构广义Feistel结构MISTY结构Lai-Massey结构更多细化的结构分组密码工作模式,2023/1/10,密码学课件,40,结构,2023/1/10,密码学课件,41,结构,对长度为2的输入，|都是比特=+1=+1=,2023/1/10,密码学课件,42,结构,对长度是4比特的输入,1|,2|,3|,4，,都是比特。|=(,1,2)|(,3,4)+1,1=,1+1,2=,2+1,3=,3+1,4=,4,2023/1/10,密码学课件,43,作业,求结构的解密函数表达式,2023/1/10,密码学课件,44,结构,容易看出：=+1+1,1,2=+1,1+1,2,3,4=+1,3+1,4 所以任意轮的结构都不具备伪随机性。可以通过对，,1，,3 做一个简单的变换，使得3轮结构具备伪随机性。,2023/1/10,密码学课件,45,分组密码的整体结构,迭代分组密码Feistel结构SP结构广义Feistel结构MISTY结构Lai-Massey结构更多细化的结构分组密码工作模式,2023/1/10,密码学课件,46,更多细化的结构,结构：整体结构是结构，轮函数采用结构。结构：整体结构是结构，其中的混乱层采用型结构设计。结构：整体结构是广义结构，轮函数采用结构。结构：整体结构是结构，轮函数采用2轮结构，由于第2层变化对安全性贡献不大，所以通常将其丢掉，也就是所谓的1.5轮结构。,2023/1/10,密码学课件,47,更多的细化结构,结构：整体结构是结构，其中的层采用结构。结构：整体结构是结构，轮函数采用结构。结构：整体结构是结构，轮函数采用结构。结构：整体结构是结构，轮函数也采用结构。,2023/1/10,密码学课件,48,更多的细化结构,事实上，对前面提到的各种整体结构进行组合可以得到许多细化的分组密码整体结构。在算法设计时采用哪种结构，依赖于：对算法性能的要求；满足各种密码性能子模块的构造；对整体结构的安全性研究成果。,2023/1/10,密码学课件,49,更多的细化结构,对整体结构的安全性研究主要包括：对现有攻击方法的抵抗力。特别是对差分密码分析和线性密码分析。可证明安全。在假定关键基础模块（比如盒）是理想的（随机函数或者置换）的情况下，证明各种整体结构需要迭代多少轮数能达到伪随机或者超伪随机。将分组密码的安全问题归为小模块的安全，可以探讨各个模块对安全的权重。,2023/1/10,密码学课件,50,分组密码的整体结构,迭代分组密码Feistel结构SP结构广义Feistel结构MISTY结构Lai-Massey结构更多细化的结构分组密码工作模式,2023/1/10,密码学课件,51,分组密码工作模式,根据不同的应用环境，需要对分组密码的加密方式做一些变动，以增强密码的安全性和适应性。常见的工作模式包括分组模式()：电码本模式()：密码分组连接模式序列模式()：输出反馈模式()：密码反馈模式()：计数器模式,2023/1/10,密码学课件,52,模式,最简单，最直接的分组密码工作模式。对给定的密钥，集合(,)|=,0,1 中共有 2 个明密文对，相当于一个译码本。,2023/1/10,密码学课件,53,模式,的优点：可以独立地操作每个明(密)文组，不必按序列号=1,2,依次加密或解密，这对必须随机独立存取的数据块来说是很方便的。如对数据库，以ECB模式可以做到独立地加密或解密任意一个记录，同样，也可以单独地增加或删除任意记录。,2023/1/10,密码学课件,54,模式的缺点,若=+，必有=+，因此在密文中暴露了明文数据的数据格式和特征。明文数据一般具有固定格式、或大量的重复和较长的零串,重要的数据常常在同一位置上出现；明文数据开头通常是格式化的报头,内含发送者、接收者、通信地址、作业号、发报时间等信息。所有这些数据格式和统计特征均会在ECB模式的密文中暴露出来。,2023/1/10,密码学课件,55,模式的缺点,2023/1/10,密码学课件,56,模式的缺点,密码分析者在未知密钥的情况下利用大量积累的明密文对(,)，自行编译码本，以便对今后截取的密文直接解密；利用已知的明密文对进行替换、嵌入或删除等，从而进行一系列的主动攻击。,2023/1/10,密码学课件,57,模式的缺点,2023/1/10,密码学课件,58,M1=Pay to J.Jones M2=$1000 M3=Pay to S.Smith M4=$10000000,K,C1,K,C4,模式的替换攻击示意图,K,C1,K,C4,M1=Pay to J.Jones M4=$10000000,谢谢,2023/1/10,密码学课件,59,