搜索
密码学第13讲一口吃地球2014年4月8日2020/11/29密码学课件1分组密码的整体结构迭代分组密码𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝑆𝑃结构广义𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝑀𝐼𝑆𝑇𝑌结构𝐿𝑎𝑖−𝑀𝑎𝑠𝑠𝑒𝑦结构更多细化的结构分组密码工作模式2020/11/29密码学课件2分组密码的整体结构迭代分组密码𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝑆𝑃结构广义𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝑀𝐼𝑆𝑇𝑌结构𝐿𝑎𝑖−𝑀𝑎𝑠𝑠𝑒𝑦结构更多细化的结构分组密码工作模式2020/11/29密码学课件3迭代分组密码如果分组密码𝐸是基于一个简单函数𝐹迭代若干次而形成，就称其为迭代密码。2020/11/29密码学课件4混乱密钥。。。扩散混乱扩散混乱扩散明文密文迭代分组密码目前流行的分组密码均是迭代型密码2020/11/29密码学课件5密钥扩展算法𝐹𝐹𝐹𝐹𝑌0=𝑋𝑌(𝑟−2)𝑌(𝑟−1)𝑌𝑟=𝑌𝐾(𝑟−1)𝐾迭代分组密码每次迭代称作一轮，相应的函数𝐹称作轮函数。每一轮输入都是前一轮输出的函数。𝑌𝑖=𝐹𝑌𝑖−1,𝐾𝑖其中𝐾(𝑖)是第𝑖轮子密钥，由秘密密钥𝐾通过密钥扩展算法产生。密钥扩展算法是将短的种子密钥扩展成若干子密钥，再将这些子密钥融合入每一轮的运算中。2020/11/29密码学课件6迭代分组密码迭代次数（或者轮数）是迭代分组密码的一个主要参数。影响分组密码轮数选择的因素很多，主要包括以下几个因素：算法采用的整体结构。轮函数的性能。应用环境设计者对算法的安全性评估。2020/11/29密码学课件7迭代分组密码在加密算法中，通常有前期白化和后期白化，原因是分组密码的安全性分析通常都是先猜测部分密钥比特，然后剥去密码的第一轮或最后一轮，再将攻击施加于剩下的中间轮上。一般要对密码的第一轮或者最后一轮特殊对待，给第一轮加一个密钥控制的前期变换，给最后一轮加一个密钥控制的后期变换。与种子密钥进行一次异或运算。2020/11/29密码学课件8分组密码的整体结构迭代分组密码𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝑆𝑃结构广义𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝑀𝐼𝑆𝑇𝑌结构𝐿𝑎𝑖−𝑀𝑎𝑠𝑠𝑒𝑦结构更多细化的结构分组密码工作模式2020/11/29密码学课件9𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构整体结构是每个分组密码的重要特征，所用整体结构对于分组密码的轮数选择、软硬件性能都有非常大的影响。整体结构的研究多采用可证明安全理论的方法，研究它们对差分、线性等分析方法的抵抗力，研究它们在一定假设下的伪随机性和超伪随机性。2020/11/29密码学课件10𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构可以把任何函数（通常称为轮函数𝐹）转化为一个置换。2020/11/29密码学课件11𝐿0𝑅0𝐹(𝑅0,𝐾0)𝐿1𝑅1𝐾0𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构对长度为2𝑛比特的输入𝐿0||𝑅0，𝐿0和𝑅0都是𝑛比特。𝐿1=𝑅0𝑅1=𝐿0⊕𝐹(𝑅0,𝐾0)2020/11/29密码学课件12𝐿0𝑅0𝐹(𝑅0,𝐾0)𝐿1𝑅1𝐾0𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构“加解密相似”是𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构的实现优点，设计轮函数时可以不考虑解密的情况。对于任何的轮函数𝐹，𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构都是可逆的。2020/11/29密码学课件132020/11/29密码学课件14𝐿0𝑅0𝐹(𝑅0,𝐾0)𝐿1𝑅1𝐾0𝐹(𝑅1,𝐾1)𝐿2𝑅2𝐾1𝑅2𝐿2𝑟2𝑙2𝐹(𝑙2,𝐾1)𝑟1𝑙1𝐾1𝐹(𝑙1,𝐾0)𝑟0𝑙0𝐾0𝑙0𝑟0𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构对于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=𝐿02020/11/29密码学课件15𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构对多轮的情况假设𝑁轮2020/11/29密码学课件162020/11/29密码学课件17𝐿0𝑅0𝐹(𝑅0,𝐾0)𝐿𝑖𝑅𝑖𝐾0𝐹(𝑅𝑖,𝐾𝑖)𝐿𝑖+1𝑅𝑖+1𝐾𝑖𝑅𝑁𝐿𝑁𝑟𝑁𝑙𝑁𝐹(𝑙2,𝐾1)𝑟𝑁−𝑖𝑙𝑁−𝑖𝐾𝑁−1𝐹(𝑙𝑁−𝑖,𝐾𝑁−𝑖)𝑟𝑁−𝑖−1𝑙𝑁−𝑖−1𝐾𝑁−𝑖𝑙0𝑟0𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构对于𝑁轮情况，需要证明𝑟𝑖=𝑅𝑖和𝑙𝑖=𝐿𝑖𝑖=𝑁−1,……,0𝑟𝑖=𝑙𝑖+1=𝐿𝑖+1=𝑅𝑖𝑙𝑖=𝑟𝑖+1⊕𝐹𝑙𝑖+1,𝐾𝑖+1=𝑅𝑖+1⊕𝐹𝐿𝑖+1,𝐾𝑖+1=𝐿𝑖⊕𝐹𝐿𝑖+1,𝐾𝑖+1⊕𝐹𝐿𝑖+1,𝐾𝑖+1=𝐿𝑖联立上述两式对𝑖做数学归纳法，𝑖=𝑁−1,……,0。2020/11/29密码学课件18伪随机置换和超伪随机置换分组密码是0,1𝑛→0,1𝑛上的一个置换，完全由密钥𝐾决定，所以分组密码一共有|𝐾|种可能。如果密钥𝐾是𝑙个比特，那么就是2𝑙种可能。这个集合记做𝐸(𝐾)而0,1𝑛→0,1𝑛上的所有置换共有2𝑛!种可能。这个集合记做𝑆2𝑛2020/11/29密码学课件19伪随机置换和超伪随机置换2020/11/29密码学课件20𝑃←𝑅𝐸(𝑘)𝑃←𝑅𝑆2𝑛WORD0WORD10?1伪随机置换和超伪随机置换2020/11/29密码学课件21𝑃←𝑅𝐸(𝑘)𝑃←𝑅𝑆2𝑛WORD0WORD10?1𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构对于𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构，有这样的结论：如果轮函数𝐹是伪随机函数，则3轮𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构是伪随机的。3轮𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构不是超伪随机的。4轮𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构是超伪随机的。2020/11/29密码学课件22𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构假设3轮𝐹𝑒𝑖𝑠𝑡𝑒𝑙的轮函数分别是𝑓0,𝑓1,𝑓2在某个WORD里，我们做如下动作：𝐿3||𝑅3←𝑃(02𝑛)𝑋←𝑅0,1𝑛/{0𝑛}𝐿3∗||𝑅3∗←𝑃(𝑋||0𝑛)𝑋𝐿||𝑋𝑅←𝑃−1(𝐿3||𝑅3⊕𝑋)𝑖𝑓𝑋𝑅=𝐿3⊕𝐿3∗,thenreturn0elsereturn1.2020/11/29密码学课件232020/11/29密码学课件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,𝐾23轮𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝐿3|𝑅3=𝑓1𝑓00𝑛|𝑓2𝑓1𝑓0(0𝑛)𝐿3∗=𝑓2(𝑋⊕𝑓1(0𝑛))2020/11/29密码学课件253轮𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝑋𝑅=𝐿3⊕𝑓1𝑅1=𝐿3⊕𝑓1𝑅3⊕𝑋⊕𝑓2𝐿3=𝑓1𝑓00𝑛⊕𝑓1𝑓2𝑓1𝑓00𝑛⊕𝑋⊕𝑓2𝑓1𝑓00𝑛=𝑓1𝑓00𝑛⊕𝑓2𝑓10𝑛⊕𝑋=𝐿3⊕𝐿3∗2020/11/29密码学课件262020/11/29密码学课件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分组密码的整体结构迭代分组密码𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝑆𝑃结构广义𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝑀𝐼𝑆𝑇𝑌结构𝐿𝑎𝑖−𝑀𝑎𝑠𝑠𝑒𝑦结构更多细化的结构分组密码工作模式2020/11/29密码学课件28𝑆𝑃结构𝑆𝑃型密码的一轮由密钥“加”、混乱层和扩散层三部分组成。通常，混乱层由一些𝑆盒并置而成，𝑆盒为双射，轮子密钥和轮输入做异或运算。需要考虑解密函数。2020/11/29密码学课件292020/11/29密码学课件30𝑆1𝑆2𝑆3……𝑆𝑛扩散层𝐾𝑖𝑆1𝑆2𝑆3……𝑆𝑛扩散层𝐾𝑖𝑆𝑃结构直观的看，先经过混乱层，再经过扩散层，就很接近𝑆ℎ𝑎𝑛𝑛𝑜𝑛所提出的混乱原则和扩散原则。经过多次迭代以后，会增强密码的混乱性和扩散性，使得密码的输出与输入之间的依赖关系更加复杂。和𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构相比，𝑆𝑃结构可以得到更快速的扩散，更适宜高速的硬件实现。𝑆𝑃的轮数更少。2020/11/29密码学课件31分组密码的整体结构迭代分组密码𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝑆𝑃结构广义𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝑀𝐼𝑆𝑇𝑌结构𝐿𝑎𝑖−𝑀𝑎𝑠𝑠𝑒𝑦结构更多细化的结构分组密码工作模式2020/11/29密码学课件32广义𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构是左右平衡的。可以推广到非平衡的𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构。通俗的讲，就是左边和右边长度不一样的𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构。按输入的分组，还可以选用多个子块轮函数𝐹。2020/11/29密码学课件332020/11/29密码学课件34𝐿𝑖,2𝐿𝑖,3𝐿𝑖,1𝐿𝑖,4𝐹𝑖一型结构𝐿𝑖,2𝐿𝑖,3𝐿𝑖,1𝐿𝑖,4𝐹𝑖二型结构2020/11/29密码学课件35𝐿𝑖,2𝐿𝑖,3𝐿𝑖,1𝐿𝑖,4三型结构𝐿𝑖,2𝐿𝑖,3𝐿𝑖,1𝐿𝑖,4四型结构𝐹𝑖,2𝐹𝑖,1𝐹𝑖广义𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构广义𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构继承了𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构“加解密相似”、轮函数不用求逆的优点。轮函数的设计规模更加灵活。7轮一型结构是伪随机的。5轮二、三型结构是伪随机的，6轮二、三型结构是超伪随机的。7轮四型结构是伪随机的，10轮四型结构是超伪随机的。2020/11/29密码学课件36分组密码的整体结构迭代分组密码𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝑆𝑃结构广义𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构𝑀𝐼𝑆𝑇𝑌结构𝐿𝑎𝑖−𝑀𝑎𝑠𝑠𝑒𝑦结构更多细化的结构分组密码工作模式2020/11/29密码学课件37𝑀𝐼𝑆𝑇𝑌结构对长度为2𝑛的输入𝐿𝑖−1||𝑅𝑖−1，𝐿𝑖−1是𝑛1比特，𝑅𝑖−1是𝑛2比特，𝑛1+𝑛2=2𝑛。𝐿𝑖=𝑅𝑖−1𝑅𝑖={𝐹𝑖𝐿𝑖−1⊕𝑀𝑆𝐵𝑛1(𝑅𝑖−1)𝑛1≤𝑛2𝐹𝑖𝐿𝑖−1⊕𝑅𝑖−1||0∗𝑛1𝑛22020/11/29密码学课件38𝐿𝑖𝑅𝑖𝐹𝑖𝑀𝐼𝑆𝑇𝑌结构𝑀𝐼𝑆𝑇𝑌结构是借鉴𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构的研究结果推广的一种整体结构。𝑀𝐼𝑆𝑇𝑌结构的优点是，当左右长度不一样时，合理选取轮函数可以使得𝑀𝐼𝑆𝑇𝑌结构达到比𝐹𝑒𝑖𝑠𝑡𝑒𝑙结构更高的安全界。缺点是轮函数的设计需要