【安全课件】第78讲--分组密码

第四章分组密码王滨2005年3月14日2明文处理方式•分组密码（blockcipher)将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。•流密码（streamcipher)又称序列密码。序列密码每次加密一位或一字节的明文。3§4.1分组密码的基本原理定义1分组密码就是将明文数据按固定长度进行分组，然后在同一密钥控制下逐组进行加密，从而将各个明文分组变换成一个等长的密文分组的密码。其中二进制明文分组的长度称为该分组密码的分组规模.m1m2m3mnc1c2c3cnkkkk4实现原则:(1)必须实现起来比较简单,知道密钥时加密和脱密都十分容易,适合硬件和(或)软件实现.(2)加脱密速度和所消耗的资源和成本较低,能满足具体应用范围的需要.例:对高速通信数据的加密----硬件实现;嵌入到系统软件的加密程序----软件实现;智能卡内数据的加密----低成本实现5安全性设计原则1.混乱原则(又称混淆原则)(Confusion)混乱原则就是将密文、明文、密钥三者之间的统计关系和代数关系变得尽可能复杂，使得敌手即使获得了密文和明文，也无法求出密钥的任何信息；即使获得了密文和明文的统计规律，也无法求出明文的新的信息。可进一步理解为：（1）明文不能由已知的明文，密文及少许密钥比特代数地或统计地表示出来。（2）密钥不能由已知的明文，密文及少许密钥比特代数地或统计地表示出来。62.扩散原则(Diffusion)扩散原则就是应将明文的统计规律和结构规律散射到相当长的一段统计中去(Shannon的原话)。也就是说让明文中的每一位影响密文中的尽可能多的位，或者说让密文中的每一位都受到明文中的尽可能多位的影响。如果当明文变化一个比特时,密文有某些比特不可能发生变化,则这个明文就与那些密文无关,因而在攻击这个明文比比特时就可不利用那些密文比特.7分组密码的设计方法采用乘积密码：即通过将一个弱的密码函数迭代若干次，产生一个强的密码函数，使明文和密钥得到必要的混乱和扩散。在设计迭代函数时，充分利用代替密码和移位密码各自的优点，抵消各自的缺点，从而通过多次迭代，形成一个强的分组密码算法。8§4.2DES分组密码算法(DateEncipherStandard)一、背景简介该算法是在美国NSA（国家安全局）资助下由IBM公司开发的密码算法，其初衷是为政府非机密的敏感信息提供较强的加密保护。它是美国政府担保的第一种加密算法，并在1977年被正式作为美国联邦信息处理标准。DES主要提供非军事性质的联邦政府机构和私营部门使用，并迅速成为名声最大，使用最广的商用密码算法。9背景发明人：美国IBM公司W.Tuchman和C.Meyer1971-1972年研制成功基础：1967年美国HorstFeistel提出的理论产生：美国国家标准局（NBS)1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（DataEncryptionStandard），于1977年7月15日生效10背景美国国家安全局（NSA,NationalSecurityAgency)参与了美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位1979年，美国银行协会批准使用DES1980年，DES成为美国标准化协会(ANSI)标准1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作11DES首次被批准使用五年，并规定每隔五年由美国国家保密局作出评估，并重新批准它是否继续作为联邦加密标准。最近的一次评估是在1994年1月，美国已决定1998年12月以后将不再使用DES。因为按照现有的技术水平，采用不到几十万美元的设备，就可破开DES密码体制。目前的新标准是AES，它是由比利时的密码学家JoanDaemen和VincentRijmen设计的分组密码—Rijndael（荣代尔）。12§1DES分组密码算法二、算法概述（一）基本参数分组加密算法：明文和密文为64位分组长度对称算法：加密和解密除密钥编排不同外，使用同一算法密钥长度：有效密钥56位，但每个第8位为奇偶校验位，可忽略密钥可为任意的56位数，但存在弱密钥，容易避开采用混乱和扩散的组合，每个组合先替代后置换，共16轮只使用了标准的算术和逻辑运算，易于实现13输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据DES加密过程14圈五十第15kf1415RL),(15141415kRfLR),(16151516kRfLRf16k1516RL圈六十第1k0L0R圈一第01RL),(1001kRfLRf文明IP1IP文密加密框图15置换•定义4.1：设S是一个有限集合，φ是从S到S的一个映射。如果对任意的u，v，当u≠v时，φ(u)≠φ(v),则称φ是S上的一个置换。16初始置换与逆初始置换输入和输出比特的序号从左向右编排为1,2,3,…,64含义:输出的第1比特是输入的第58比特,该表示方法实现方便.17IP和IP-12014'MM1420'''MMIPIP—118（二）加密算法的加密过程可描述为：则设明文DES),,(00RLm16,2,1),,(111iKRfLRRLiiiiiiLi（32位）Ri（32位）Li-1（32位）Ri-1（32位）fDES的第i圈加密结构图Ki19DES加密算的圈函数----属于Feistel模型:Li（32位）Ri（32位）Li-1（32位）Ri-1（32位）fDES的圈函数的结构),(yx设输入为圈加密的输出为：的则1DES))(,(yfxyk即它等价于两个对合变换:)),,((),(yykfxyx),(),(abba)),,((),(yykfxyx)),(,(ykfxyKi20注意•无论f函数如何选取，DES的圈函数是一个对合变换。)),,((),(yykfxyxF),()),,(()),((yxyykfxFyxFF21P1S2S3S4S5S6S7S8S4821kkk4821aaa3221aaaEDES的F函数12322①E盒扩展扩展变换的作用是将输入的32比特数据扩展为48比特数据扩展23①E盒扩展3212345456789891011121312131415161716171819202120212223242524252627282928293031321扩展方式:(1)将输入的32比特每4比特为一组分为8块;(2)分别将第m-1块的最右比特和第m+1块的最左比特添到第m块的左边和右边,形成输出的第k个6比特块.主要原因:硬件实现简单24P1S2S3S4S5S6S7S8S4821kkk4821aaa3221aaaEDES的F函数1225压缩替代S-盒－48位压缩到32位1S2S3S4S5S6S7S8S123456……………………………………………………4344454647481234……………………………………………………293031322600010203040506070809101112131415012314041301021511080310061205090007001507041402130110061211090503080401140813060211151209070310050015120802040901070511031410000613012315010814061103040907021312000510031304071502081412000110060911050014071110041301050812060903021513081001031504021106071200051409012310000914060315050113120711040208130700090304061002080514121115011306040908150300110102120510140701101300060908070415140311050212012307131403000609100102080511120415130811050615000304070212011014091006090012110713150103140502080403150006100113080904051112070214012302120401071011060805031513001409141102120407130105001510030908060402011110130708150912050603001411081207011402130615000910040503012312011015090206080013030414070511101504020712090506011314001103080914150502081203070004100113110604030212090515101114010706000813012304110214150008130312090705100601130011070409011014030512021508060104111312030714101506080005090206111308010410070905001514020312012313020804061511011009031405001207011513081003070412050611001409020711040109121402000610131503050802011407041008131512090003050611输出列行1S2S3S4S5S6S7S8S②S盒行和列的序号从0起算。271234561626234521133911001110019bbbbbbbbSbbbb行：-盒子行列列：值：14=1100②S-盒的构造28S-盒的构造要求•S-盒是算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度•提供了密码算法所必须的混乱作用•非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门29P1S2S3S4S5S6S7S8S4821kkk4821aaa3221aaaEDES的F函数12330③P盒置换P1672021291228171152326518311028241432273919133062211425将S-盒变换后的32比特数据再进行P盒置换，置换后得到的32比特即为f函数的输出。含义:P盒输出的第1个元是输入的第16个元。基本特点：（1）P盒的各输出块的4个比特都来自不同的输入块；（2）P盒的各输入块的4个比特都分配到不同的输出块之中；（3）P盒的第t输出块的4个比特都不来自第t输入块。31例:利用DES算法和全0密钥对输入1000000119600000进行1圈加密的结果。（1）输入的右半部分是19600000=00011001011000000000000000000000（2）经E盒扩展后变为000011110011101100000000000000000000000000（3）与全0子密钥模2加后变为000011110010101100000000000000000000000000（4）查S盒后的32比特输出为f8372c4d11111000001101110010110001001101（5）经P盒后得F函数的32比特输出:9cd89aa7=10011100110110001001101010100111（6）将F函数的输入放到左边,将F函数的输出与圈函数的左半输入模2加后放到右边,的圈