迎接集团公司设备大检查自检情况汇报材料

密码学导论密码学导论第四章·分组密码第四章·分组密码本章要点本章•第一节分组密码原理–Feistel密码框架、原理•第二节数据加密标准DES结构原理–结构、原理•第三节DES的安全性–雪崩效应；计时攻击；能量攻击；差分密码分析；线性密码分析–DES设计准则•第四节有限域•第四节有限域–群、环和域；–模运算；欧几里得算法；扩展欧几里得算法；有限域多项式计算生成元表示的有限域中国科学技术大学·密码学导论–有限域GF(p),GF(2n)；多项式计算；生成元表示的有限域1本章要点本章•第五节高级加密标准AES–结构、实现方式•第六节分组密码工作模式ECBCBCCFBOFBCTR–ECB、CBC、CFB、OFB、CTR–密文误码的错误传播•第七节其它分组密码标准–3DES–中间相遇攻击–TDEA；Blowfish；IDEA；RC5；SMS4TDEA；Blowfish；IDEA；RC5；SMS4中国科学技术大学·密码学导论2第一节分组密码原理第节分组密码原理中国科学技术大学·密码学导论3一、分组的概念•流密码(StreamCipher)和分组密码(BlockCipher)(p)(p)–流密码：•加密以明文比特或字节为单位，以伪随机序列与明文序列模2加后，作为密文序列每次处理数据流中的一个比特或字节•密文不仅与昀初给定的算法和密钥有关，同时也与明文位置有关(是所处位置的函数)。•例如：一次一密系统、AutoKey等。–分组密码：•通常以大于等于64位的数据块为处理单位，加密得相同长度密文过加密所得到的密仅与给定的密算法密钥有关与被•经过加密所得到的密文仅与给定的密码算法和密钥有关，与被处理的明文数据在整个明文中的位置无关。•例如：DES等。中国科学技术大学·密码学导论4理想分组密码•n比特的明文分组，加密产生n比特的密文分组，2n个不同的明文分组，每一个都产生唯一的密文分组，这种变换称为可逆的或非奇异的或一一映射。例•例：中国科学技术大学·密码学导论5•分组加密器本质上就是一个巨大的替换器•对一个分组而言，希望提供的是完美安全位的分组就有2种输入–n位的分组就有2n种输入–每种输入需要n位密钥控制替换，共需n×2n位密钥•Feistel密码框架：一种近似理想体制–目前大多数分组密码基于Feistel密码结构采用了乘积加密器的思想交替使用代换和置换–采用了乘积加密器的思想，交替使用代换和置换•S-P网络（Substitution-PermutationNetwork）•代换S-box•置换P-box中国科学技术大学·密码学导论置换Pbox6二、Feistel密码框架•加密算法：–将输入等分为两段，–进行若干轮运算，每轮中•对左半段数据进行代换，依据对左半段数据进行代换，依据•轮函数F（右半段数据和子密钥）•然后置换：交换左右两段数据•解密算法：–与加密算法过程一致–子密钥使用次序相反中国科学技术大学·密码学导论7•参数：分组长度长度越大安全性越高处理速度也越低–分组长度：长度越大，安全性越高，处理速度也越低–密钥长度：长度越大，安全性越高，可能降低处理速度–迭代轮数：单轮不能提供足够的安全性；轮数越多，安全性越高处速度也成倍增加全性越高，处理速度也成倍增加–子密钥产生算法：算法越复杂，密码分析攻击越难，会降低处理速度数算法安全性高度降低–轮函数：算法越复杂，安全性越高，处理速度也降低•特点：特点–快速软件加/解密–分析简单：利于脆弱性的分析与测试•但DES并没有简便的分析方法中国科学技术大学·密码学导论8•Feistel加解密考虑第i轮–考虑第i轮–加密：ii1LERE–解密：ii1i1iRELEFRE,KLDREniiniiLDRERDLEn1iniii1LDRDLEREn1ininiiRDLDFRD,Kn1iniii1iiii1i1ii1iREFLE,KLEFRE,KFRE,KLE中国科学技术大学·密码学导论9i1LE讨论•对轮函数F的要求：–从可解密角度：没有–从安全角度：尽可能复杂–例如i1ii1iFREKREK例如i1ii1iFRE,KREKiK•扩散效应局限在两个对应比特上•轮函数F对扩散的效果有影响中国科学技术大学·密码学导论•同样，对子密钥的生成也应考虑到混淆的效果。10第二节数据加密标准DES第二节数据加密标准DES中国科学技术大学·密码学导论11历史的回顾•IBM设计出Lucifer密码(1971)()–由HorstFeistel带领的团队–用128比特密钥加密64比特数据分组•TuchmanMayer牵头开发商业密码•Tuchman-Mayer牵头开发商业密码–适合于单芯片实现–密钥长度56比特，抗密码分析能力更强美国国家安全介–美国国家安全局介入•1973年美国国家标准局征求国家密码标准方案，IBM将上述方案提交并被采用称为数据加密标IBM将上述方案提交，并被采用，称为数据加密标准（DES）中国科学技术大学·密码学导论12•民间研究显示DES安全性很强–广泛应用在金融、遗产等领域–虽然差分攻击和线性分析攻击在理论上有效，但实现起来计算量仍很大来计算量仍很大•是应用昀广泛的分组密码技术算机发速前经穷举法破解–计算机发展迅速，目前已经可以用穷举法破解DES–AES正取而代之•安全性曾争议颇多–用56比特密钥加密64比特数据设计标准列入机密中国科学技术大学·密码学导论–设计标准列入机密13DES的整体结构•64比特明文分组输入64比特明文64比特密钥•64比特密文分组输出64比特密钥IPK1第1轮PC1分组左移PC264485656•64比特密钥–实际只使用56位–其它用作奇偶校验等第轮第2轮分组左移分组左移PC264485656其它用作奇偶校验等•Feistel密码框架轮操作K16第16轮分组左移PC2486456–16轮操作–IP：初始置换–IP-1：逆初始置换32比特置换IP-164中国科学技术大学·密码学导论逆初始置换–PC1、PC2：压缩置换1464比特密文初始置换IP与逆初始置换IP-1•置换表中的每个元素表明了输入位在位表明了输入位在64位输出中的位置•两表互逆–IP表中第1个是58，表示输入的第1位被置换示输入的第1位被置换到第58位；–IP-1表中第58个是1，表示输入的第58位被表示输入的第58位被置换到第1位；•注意IP-1表很有规律中国科学技术大学·密码学导论•注意：IP1表很有规律15轮结构•64位数据分为L、R各32位Ri-1Li-13232•子密钥K为48位轮函数扩展置换E323248•轮函数：–将32位R通过E扩展为48位–与密钥K异或S盒置换KiF4848与密钥异或–由8个S盒子紧缩为32位–由置换P作用后输出S盒置换置换P32323232中国科学技术大学·密码学导论16RiLi扩展置换E•观察扩展置换E–将32位输入分为8组，每组4位–从相邻两组的邻近位置各取1位–扩展置换E扩展置换E12345678910111213141516171819202122232425262728293031323212345456789891011121312131415161716171819202120212223242524252627282928293031321•扩散作用–某一个比特，几轮操作后其影响会扩散到整个分组64位某个比特，几轮操作后其影响会扩散到整个分组位1234567891011121314151617181920212223242526272829303132中国科学技术大学·密码学导论17S盒子结构•S盒子为4行16列的矩阵，每行定义了一个可逆置换•输入6位，输出4位48SSSSSSSS66666666S1S2S3S4S5S6S7S84444444432中国科学技术大学·密码学导论18S盒子•输入6位，输出4位–输入的第1位和第6位组成一个2位二进制数，用来选择行–输入的第2位至第5位组成一个4位二进制数，用来选择列–将选中的数字以二进制数输出将选中的数字以二进制数输出•例：S1盒子输入011001–选择行1（01）；选择列12（1100）将选中的输出–将选中的9输出1001。•注意S盒子的行列从0开始计数中国科学技术大学·密码学导论•注意：S盒子的行、列从0开始计数19中国科学技术大学·密码学导论20密钥的产生产•输入64位密钥，保留56位–置换选择PC1将64位原始密钥置换输出56位钥置换输出56位–注意：若用大写英文字母作为密钥，常用它们的ASCII码作为二进制密钥。这是危险的因为它们的这是危险的，因为它们的ASCII码昀高位均为0，而DES舍弃的是昀低位！中国科学技术大学·密码学导论21–56位密钥分为两组，每轮迭代Ci-1Di-1分别循环左移1位或2位，作为下一轮的密钥输入–移位产生的值经置换选择2，输LS-1LS-12828移位产生的值经置换选择2，输出48位作为轮函数子密钥PC22828PC2Ki482828CiDi中国科学技术大学·密码学导论22CiDiDES解密解•解密是加密的逆过程•对Feistel框架密码，采用相同算法，但是子密钥使用的次序正好相反：IP变换抵消加密的昀后步IP1–IP变换抵消加密的昀后一步IP-1；–第一轮使用密钥K16；–第二轮使用密钥K15；15–……–第十六轮使用密钥K1；–IP-1变换抵消加密的第一步IP；IP变换抵消加密的第步IP；–获得解密明文。中国科学技术大学·密码学导论23第三节DES的安全性第三节DES的安全性中国科学技术大学·密码学导论24一、DES的安全性•密钥的长度问题–56-bit密钥有256=72,057,584,037,927,936≈7.2亿亿之多–蛮力搜索(bruteforcesearch)似乎很困难，20世纪70年代估计要1000－2000年估计要10002000年–技术进步使蛮力搜索成为可能•1997年网络合作破译耗时96天。•1998年在一台专用机上(EFF)只要三天时间即可•1998年在台专用机上(EFF)只要三天时间即可•1999年在超级计算机上只要22小时!–蛮力搜索需要明文可判决S-box问题其设计标准没有公开中国科学技术大学·密码学导论迄今没有发现S盒存在致命弱点25•至少有4个“弱密钥”：Ek(Ek(m))=m0101010101010101,1F1F1F1F0E0E0E0EE0E0E0E0F1F1F1F1,FEFEFEFEFEFEFEFE少有半密钥•至少有6对“半弱密钥”：EkEk'(m))=m01FE01FE01FE01FE↔FE01FE01FE01FE011FE01FE00EF10EF1↔E01FE01FF10EF10E01E001E001F101F1↔E001E001F101F1011FFE1FFE0EFE0EFE↔FE1FFE1FFE0EFE0E011F011F010E010E↔1F011F010E010E01E0FEE0FEF1FEF1FE↔FEE0FEE0FEF1FEF1•这里假设每字节的昀低位是奇偶校验位中国科学技术大学·密码学导论•这里假设每字节的昀低位是奇偶校验位26雪崩效应AvalancheEffect崩•雪崩效应：–明文或密钥的一比特的变化，引起密文许多比特的改变–加密算法的关键性能之一–希望明文或密钥的1比特变化，会使半数密文比特发生变希望明文或密钥的1比特变化，会使半数密文比特发生变化；否则，可能存在方法减小待搜索的明文和密钥空间DES密码有良好的雪崩效应•DES密码有良好的雪崩效应–如果用同样密钥加密只差一比特的两个明文：0000000000000000......000000001000000000000000......00000000•2轮迭代后密文有21个比特不同，16轮迭代后有34个比特不同–如果用只差一比特的两个密钥加密同样明文：中国科学技术大学·密码学导论如果用只差比特的两个密钥加密同样明文：•2轮迭代后密文有14