密码学分组密码

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 分组密码体制,分组密码概述,数据加密标准,差分密码分析与线性密码分析,分组密码的运行模式,其他分组密码体制,1,分组密码概述,分组密码因其实现速度较快，在,许多密码系统,中是一个重要的组成部分。分组密码与流密码在区别在于分组密码将明文的消息编码后划分成长度为n的组，在,一个密钥,的控制下变换成等长（m）的输出序列。一般情况下，nm。若mn，为由数据扩充的分组密码；若mn，为由数据压缩的分组密码。,2,为了保证一个分组密码算法的有效性安全、易于实施。分组密码算法应满足以下要求：,分组,n,足够大，使得明文空间足够大，防止明文穷举攻击法奏效。,密钥量足够大，尽可能消除弱密钥，使得所有密钥都一样好，防止对密钥的穷举攻击成功。,由密钥确定的算法要足够的复杂，充分实现明文与密钥的扩散和混乱，使得算法能抵抗各种攻击。,加密和解密运算简单，易于软件和硬件的高速实现。,数据扩展。一般无数据扩展，在采用同态置换和随机化加密技术时可引进数据扩展。,差错传播尽可能小。,3,设计分组密码常用的一些方法介绍,1. 代换,将n长的明文分组变换为唯一n长密文分组，这样的变换是可逆的，称明文分组到密文分组的可逆变换为代换。,若分组长度为n，则明文空间M有 个向量，代换的就是给出在该空间上的一个可逆变换 。,例如：取n4，,4,2. 扩散和混淆,扩散和混淆是Shannon提出的设计密码系统的两个基本的方法，目的是抵抗敌手对密码系统的统计分析。,扩散,：就是将明文的统计特性散布到密文中，实现的方法是使明文的每一位影响密文的多位，等价于说密文的每一位均受明文中的多位影响。目的是使明文和密文的统计关系变得尽可能的复杂，使敌手无法得到明文（密文）。,方法,：对数据重复执行某个置换，再对该置换作用一函数，可获得扩散。,混淆,：是使密文的统计特性和密钥取值的关系变得尽可能的复杂，使敌手无法获得密钥。,方法,：使用复杂的代换算法，可获得好的混淆结果，而使用简单的线性代换得到的混淆效果不太理想。,5,Feistel密码结构,很多分组密码的结构本质上都是基于一个Feistel密码结构。 Feistel密码结构的思想是利用,乘积密码实现扩散和混淆,。乘积密码是,顺序,的执行两个或多个密码系统，使得最后结构的密码强度高于每个基本密码系统产生的结果。,6,加密,:,L,i,= R,i-1,;,R,i,= L,i-1,F(R,i-1,K,i,),解密:,R,i-1,= L,i,L,i-1,= R,i,F(R,i-1,K,i,),=,R,i,F(L,i,K,i,),Feistel,结构定义,7,Feistel结构图,8,数据加密标准,DES描述,二重DES,两个密钥的三重DES,三个密钥的三重DES,9,64比特明文,DES算法加密,64比特密文,64比特的密钥,（内含8比特校验位）,10,DES示意图,11,DES,的描述,DES,利用56比特长度的密钥K来加密长度为64位的明文，得到长度为64位的密文,输入64比特明文数据,初始置换IP,在密钥控制下,16轮迭代,初始逆置换IP,-1,输出64比特密文数据,DES算法框图,交换左右32比特,12,DES,加解密过程,令,i,表示迭代次数，,表示逐位模,2,求和，,f,为加密函数。,DES,的加密和解密过程表示如下。,加密过程：,解密过程：,13,DES 加密过程：,IP,m,R0,L,0,IP -1,DES ( m ) = m,R1 = L0, ( R0, K1 ),L1 = R0,K,1,T,1,R16 = L15, ( R15, K16 ),L16 = R15,K,16,T,16,R15 = L14, ( R14, K15 ),L15 = R14,14,IP,m,L,16,R,16,IP -1,DES ( m ) = m,K,16,L,15,= R,16, ( L,16, K,16,),R,15,=L,16,T,16,L,0,= R,1, ( L,1, K,1,),R,0,= L,1,K,1,T,1,L,1,= R,2, ( L,2, K,1,),R,1,=L,2,DES 解密过程,15,初始置换IP和初始逆置换IP,1,注：数字表示比特位,16,逆初始置换 (IP,-1,) 是简单的比特,移位,。,置 换 码 组,1 2 3 64位 63 64,逆初始置换,密 文,1 2 3 64位 63 64,逆,初始置换,8,7,6,5,4,3,2,1,40,39,38,37,36,35,34,33,48,47,46,45,44,43,42,41,16,15,14,13,12,11,10,9,56,55,54,53,52,51,50,49,24,23,22,21,20,19,18,17,64,63,62,61,60,59,58,57,32,31,30,29,28,27,26,25,IP,-1,17,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,IP IP,-1,= IP,-1, IP = I,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,-1,:,IP:,18,L,i-1,(32比特),R,i-1,(32比特),第 i 次迭代,R,i-1,(32比特),选择扩展运算E,48比特寄存器,+,K,i,48比特寄存器,选择压缩运算S,32比特寄存器,置换运算P,+,L,i,19,R,i-1,1 48比特 48,( R,i-1,K,i,),的功能：,选择扩展运算,E,1 32比特 32,置换P,1 32比特 32,( R,i-1,K,i,),1 32比特 32,+,S,1,S,2,S,3,S,4,S,5,S,6,S,7,S,8,K,i,(,48比特,),选择压缩函数 S,i,20,3212345,456789,8910111213,121314151617,161718192021,202122232425,242526272829,28293031321,E:,E的作用：,将,32,比特的输入膨胀为,48,比特。,则输出为：B = t,32,t,1,t,2, t,32,t,1,选择扩展运算,的功能,：,设输入为：T = t,1,t,2,t,3, t,32,21,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,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,23,24,25 26 27 28,25,28,29 30 31 32,1,E的作用：,将,32,比特的输入膨胀为,48,比特。,选择扩展运算,：,22,Si,设 Si 盒的 6 个输入端为 b1 b2 b3 b4 b5 b6，在 Si 表中找出 b1 b6 行，b2 b3 b4 b5 列的元素：,Si (,b1,b6, b2 b3 b4,b5,),便是 Si 盒的输出。,S,i,选择压缩函数,Si,的功能,：,E 输出的,48 比特与子密钥异或后，,顺序分成 8 组，每组 6 比特，分别通过 S1，S2，,S8 盒后又缩为,32 比特,，即每盒输入为 6比特，输出为 4 比特。,b1 b6,b2 b3 b4 b5,二进制输出,23,选择压缩函数,Si,的功能,：,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,0,1,2,3,14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7,0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8,4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0,15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13,输入到选择函数S1,1 0 1 1 0 0,b1 b6,1 0,0 0 1 0,选择函数S1的输出,6,24,S-Box-i,25,S-Box-ii,26,子密钥的产生,27,置换选择1和置换选择2,28,DES解密,和Feistel密码一样，DES的解密和加密使用同一算法，只是子密钥的使用顺序相反。,子密钥是独立产生的，可以独立存储。,29,DES中的M、K、C,明文 m 和密钥 K 的变化,对密文的影响,：,DES的加密结果，每一比特都是明文m和密钥K的每一比特的复杂函数，即明文m和密钥k每改变一个比特都将对密文产生剧烈影响。（明文m和密钥k任意改变一比特，其结果大致有将近一半的位产生了变化。）,30,关于DES的若干问题：,1. DES的坏密钥问题：,(1)弱密钥：,定义：当密钥,K,所产生的子密钥满足,：,K,1,= K,2,= = K,16,则有：,DES,k,( m ) =,DES,k,-1,( m ),，,或：,DES,k,(,DES,k,( m ) ) = m,这样的密钥,K,称为弱密钥。,产生条件：当密钥,K,满足以下条件时产生弱密钥,，,k,57,= k,49,= k,41,= = k,9,= k,1,=0,或,1,k,63,= k,55,= k,47,= = k,15,= k,7,=0,或,1,举例：共有,4,种，如：,10101,。,31,(2) 半弱密钥：,定义：当存在子密钥,K,和,K,，,使得,：,DES,k,( m ) =,DES,k,-1,( m ),或,DES,k,(,DES,k,( m ) ) = m,则,K,和,K,成对构成半弱密钥。,产生条件,：,C,0,=101010,D,0,=000,或,111,或,101010,或,010101,C,0,=010101,D,0,=000,或,111,或,101010,或,010101,32,2. DES的安全性：,即DES的抗攻击强度如何，或者说密钥长度是否足够了（密钥实际上只有56比特）。,(1) 理论攻击法：,差分分析法和线性逼近法,(1990,年提出,),：前提条件太强：需要已知,2,43,= 4,39810,12,对明文,密文对。,可制造专用装置，用硬件来实现对所有密钥的遍历搜索。,33,早在1977年，Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元。,在CRYPTO93上，Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以16次加密能同时完成。此芯片每秒能测试5000万个密钥，用5760个芯片组成的系统需要花费10万美元，它平均用1.5天左右就可找到DES密钥。,34,(2) 有实效的攻击法：,1997,年,1,月,28,日，美国的,RSA,数据安全公司在,RSA,安全年会上公布了一项,“,秘密密钥挑战,”,竞赛，其中包括悬赏,1,万美元破译密钥长度为,56,比特的,DES,。美国克罗拉多洲的程序员,Verser,从,1997,年2月,18,日起，用了,96,天时间，在,Internet,上数万名志愿者的协同工作下，成功地找到了,DES,的密钥，赢得了悬赏的,1,万美元。,1998年7月电子前沿基金会（EFF）使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES。,1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥。,35,(3) 结论：,对DES的成功攻击，说明随着计算机技术的发展，现在完全可以用能够接受的代价破译DES密码，DES已不再安全，数据加密标准面临更新与提高。,36,双重DES (Double DES),C = EK2,(,EK1(P),P = DK1,(D,K2(C),37,双重DES的讨论,假设对于,DES,和所有,56,比特密钥，给定任意两个密钥,K1,和,K2,，,都能找到一个密钥,K3,使得,EK2,(,EK1(P)=EK3 (P),。,如果这个假设是事实，则,DES,的两重加密或者多重加密都将等价于用一个,56,比特密钥的一次加密。,从直观上看，上面的假设不可能为真。因为,DES,的加密事实上就是做一个从,64,比特分组到一个,64,分组的置换， 而,64,比特分组共有,2,64,可能的状态，因而可能的置换个数为,另一方面，,DES,的每个密钥确定了一个置换，因而总的置换个数为 。,直到,1992,年才有人证明了这个结果。,38,中间相遇攻击,C = E,K2,(,E,K1,(P),X = E,K1,(P) =,D,K2,(,C),给定明文密文对(,P,C),对所有2,56,个密钥,加密,P,对结果排序,对所有2,56,个密钥,解密,C,对结果排序,逐个比较,找出,K1,K2,使得,E,K1,(P) = D,K2,(,C),39,三重DES,三重DES四种模型：,DES-EEE3,：,三个不同密钥，顺序使用三次加密算法,DES-EDE3,：,三个不同密钥，依次使用加密,-,解密,-,加密算法,DES-EEE2,：,K1=K3,，,同上,DES-EDE2,：,K1=K3,，,同上,40,三重DES,C=E,K3,(,D,K2,(,E,K1,(P),P=D,K3,(,E,K2,(,D,K1,(C),E,和,D,互换,K1=K3,E,D,41,差分密码分析与线性密码分析,差分密码分析,差分密码分析方法是迄今已知的攻击迭代密码最有效的方法之一，其基本思想是：通过分析明文对的差值对密文对的差值的影响来恢复某些密钥的比特。 本质是一种选择明文攻击。,对明文分组为n的r轮迭代密码，两个n比特串 和 的差分定义为,为在n比特串集上定义的一个群运算,由加密对可得差分序列,42,定义： 轮特征 是一个差分序列：,其中 是明文对 和 的差分， 是第 轮 输出 和 的差分。轮特征 的概率是指在明文 和子密钥 独立、均匀随机时，明文对 和 的差分为 的条件下，第 轮输出的差分为 的概率。,43,对r轮迭代密码的差分密码分析过程可综述为如下的步骤：,（1）找出一个（r-1)-轮特征 使得它的概率达到最大或几乎最大。,（2）均匀随机地选择明文 并计算 ，使得它们的差分为 ，找出 和 在实际密钥加密下所得的密文 和 。若最后一轮的子密钥 有 个可能取值 ，设置相应的 个计数器，用每个 解密密文得到 和 ，如果 和 的差分是 ，则给相应的计数器加1,44,（3）重复步骤(2)，直到一个或几个计算器的值明显高于其他计数器的值，则输出它们对应的子密钥（或部分比特）。,攻击的复杂度：数据复杂度和计算（处理）复杂度,。,45,线性密码分析,线性密码分析是迭代密码的一种已知明文攻击，它利用的是密码算法中的“不平衡的线性逼近”。,设明文分组和密文分组的长度皆为n比特，记明文和密文分组分别为,。,记,线性密码分析的目标就是找出以下形式的有效线性方程：,其中,46,如果方程成立的概率 ，则称该方程是有效的线性逼近。如果 是最大，则称该方程是最有效的线性逼近。,设N表示明文的个数，T表示是方程左边为0的明文数。如果 ，则令,如果 ，则令,从而可得关于密钥比特的一个线性方程。对不同的明文密文对重复以上过程，可得关于一组线性方程，从而确定出密钥比特。,0和1互换,47,分组密码的操作模式,电子密码本ECB (electronic codebook mode),密码分组链接CBC (cipher block chaining),密码反馈CFB (cipher feedback),输出反馈OFB (output feedback),美国NSB在FIPS PUB 74和81中规定,ANSI 在ANSI X3.106中规定,ISO和ISO/IEC在ISO 9732 ISO/IEC 10116中规定,48,电子密码本（ECB）,C,i,= E,K,(P,i,),P,i,=,D,K,(C,i,),49,ECB特点,简单和有效,可以并行实现,不能隐藏明文的模式信息,相同明文,相同密文,同样信息多次出现造成泄漏,对明文的主动攻击是可能的,信息块可被替换、重排、删除、重放,误差传递：密文块损坏,仅,对应明文块损坏,适合于传输短信息,50,密码分组链接CBC,C,i,=E,K,(C,i-1,P,i,),P,i,=,E,K,(C,i,),C,i-1,51,CBC特点,没有已知的并行实现算法,能隐藏明文的模式信息,需要共同的初始化向量,IV,相同明文,不同密文,初始化向量,IV,可以用来改变第一块,对明文的主动攻击是不容易的,信息块不容易被替换、重排、删除、重放,误差传递：,密文块损坏,两,明文,块,损坏,安全性好于,ECB,适合于传输长度大于,64,位的报文，还可以进行用户鉴别,是大多系统的标准如,SSL,、,IPSec,52,密码反馈CFB,CFB:分组密码,流密码,S,i,为移位寄存器,j,为流单元宽度,加密:,C,i,=,P,i,(,E,K,(S,i,),的高j位),S,i+1,=(,S,i,j)|C,i,解密,: P,i,=,C,i,(,E,K,(S,i,),的高j位),S,i+1,=(,S,i,j)|C,i,53,CFB加密示意图,C,i,=P,i,(,E,K,(S,i,),的高j位) ; S,i+1,=(S,i,j)|C,i,54,CFB解密示意图,P,i,=C,i,(,E,K,(S,i,),的高j位); S,i+1,=(S,i,j)|C,i,55,CFB特点,分组密码,流密码,没有已知的并行实现算法,隐藏了明文模式,需要共同的移位寄存器初始值,IV,对于不同的消息，,IV,必须唯一,误差传递：一个单元损坏影响多个单元,56,输出反馈OFB,O,FB:分组密码,流密码,S,i,为移位寄存器,j,为流单元宽度,加密:,C,i,=,P,i,(,E,K,(S,i,),的高j位),S,i+1,=(,S,i,j)|,(,E,K,(S,i,),的高j位),解密,: P,i,=,C,i,(,E,K,(S,i,),的高j位),S,i+1,=(,S,i,j)|,(,E,K,(S,i,),的高j位),57,OFB加密示意图,C,i,=P,i,(,E,K,(S,i,),的高j位);S,i+1,=(S,i,j)|,(,E,K,(S,i,),的高j位),58,OFB解密示意图,P,i,=C,i,(,E,K,(S,i,),的高j位); S,i+1,=(S,i,j)|,(,E,K,(S,i,),的高j位),59,OFB特点,O,FB:分组密码,流密码,没有已知的并行实现算法,隐藏了明文模式,需要共同的移位寄存器初始值IV,误差传递：一个单元损坏只影响对应单元,对明文的主动攻击是可能的,信息块可被替换、重排、删除、重放,安全性较CFB差,60,其他分组密码体制,IDEA,设计原理,加密过程,61,国际数据加密IDEA,（International Data Encryption Algorithm),算法,1990年瑞士联邦技术学院的来学嘉和Massey提出，PES，91年修订，92公布细节,设计目标从两个方面考虑,加密强度,易实现性,强化了抗差分分析的能力，,PGP,62,高级加密标准,AES算法Rijndael,数学基础和设计思想,算法描述,63,AES背景-i,1997年4月15日，（美国）国家标准技术研究所（NIST）发起征集高级加密标准（Advanced Encryption Standard）AES的活动，活动目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，作为新的数据加密标准。,1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。作为进入AES候选过程的一个条件，开发者承诺放弃被选中算法的知识产权。,对AES的基本要求是：比三重DES快、至少与三重DES一样安全、数据分组长度为128比特、密钥长度为128/192/256比特。,64,AES背景-ii,1998年8月12日，在首届AES会议上指定了15个候选算法。,1999年3月22日第二次AES会议上，将候选名单减少为5个，这5个算法是RC6，Rijndael，SERPENT，Twofish和MARS。,2000年4月13日，第三次AES会议上，对这5个候选算法的各种分析结果进行了讨论。,2000年10月2日，NIST宣布了获胜者Rijndael算法，2001,年11月出版了最终标准FIPS PUB197,。,65,Rijndael简介,不属于Feistel结构,加密、解密相似但不对称,支持128/32=Nb数据块大小,支持128/192/256(/32=Nk)密钥长度,有较好的数学理论作为基础,结构简单、速度快,66,AES参数,67,SP网络结构,在这种密码的每一轮中，轮输入首先被一个由子密钥控制的可逆函数,S,作用，然后再对所得结果用置换（或可逆线性变换）,P,作用。,S,和,P,分别被称为混乱层和扩散层，主要起混乱和扩散作用。,68,AES算法结构-i,AES,算法的轮变换中没有,Feistel,结构，轮变换是由三个不同的可逆一致变换组成，称之为层，,线性混合层：确保多轮之上的高度扩散。,非线性层：具有最优最差,-,情形非线性性的,S-,盒的并行应用。,密钥加层：轮密钥简单地异或到中间状态上。,69,AES算法结构-ii,70,AES-128加解密过程,71,AES算法描述,假设：State表示数据，以及每一轮的中间结果RoundKey表示每一轮对应的子密钥,算法如下：,第一轮之前执行AddRoundKey(State,RoundKey),Round(State,RoundKey) ,ByteSub(State);,ShiftRow(State);,MixColumn(State);,AddRoundKey(State,RoundKey); ,FinalRound(State,RoundKey) ,ByteSub(State);,ShiftRow(State);,AddRoundKey(State,RoundKey); ,72,状态、密钥,状态,/,密钥的矩阵表示,S,00,S,01,S,02,S,03,S,04,S,05,S,06,S,07,S,08,S,09,S,10,S,11,S,12,S,13,S,14,S,15,k,00,k,01,k,02,k,03,k,10,k,11,k,12,k,13,k,20,k,21,k,22,k,23,k,30,k,31,k,32,k,33,73,字节代替(Substitute Bytes )变换,字节代替是一个非线性的字节代替，独立地在每个状态字节上进行运算。代替表（S-盒）是可逆的，是一个16,16的矩阵。,74,75,example,76,行移位(Shift Row)变换,简单的置换,77,example,78,列混合Mix Column变换,代替操作，将状态的列看作有限域GF（2,8,）上的4维向量并被有限域GF（2,8,）上的一个固定可逆方阵A乘,79,80,example,81,轮密钥加（Add Round Key),一个简单地按位异或的操作,82,AES的密钥调度,轮密钥是通过密钥调度算法从密钥中产生，包括两个组成部分：密钥扩展和轮密钥选取。基本原理如下：,所有轮密钥比特的总数等于分组长度乘轮数加,1,。（如,128,比特的分组长度和,10,轮迭代，共需要,1408,比特的密钥）。,将种子密钥扩展成一个扩展密钥。,轮密钥按下述方式从扩展密钥中选取：第一个轮密钥由开始,Nb,个字组成，第二个轮密钥由接下来的,Nb,个字组成，如此继续下去。,83,AES的密钥扩展,84,85,G变换,Rotword执行一字节循环左移,b,0,b,1,b,2,b,3, b,1,b,2,b,3,b,0,Subword执行使用S-盒实行字节替换,前两步的结果XOR轮常数Rconj,86,example,87,Rijndael安全性,没有发现弱密钥或补密钥,能有效抵抗目前已知的攻击算法,线性攻击,差分攻击,88,先进对称分组加密算法的特点,可变的密钥长度,: RC5,混合的运算,IDEA,数据相关的轮数,RC5,密钥相关的轮数,CAST-128,密钥相关的,S,盒,: Blowfish,冗长密钥调度算法：,Blowfish,可变的,F,：,CAST-128,可变长明文,/,密文块长度,可变轮数,每轮操作作用于全部数据,89,习题,P73:1,2,3,4,90,实验安排：,第十三、十四、十五周停课安排实验。,第十三周：周一下午1：305：30；,地点：信北503,环境：Windows操作系统，C语言编译环境。,2人/组,第十五周：周一下午5-6节，信西503，硬件实验。,91,