密码学基础(2).ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,密码学基础（2）,胡建斌,北京大学网络与信息安全研究室,E-mail:,hjbin,,infosec,.pku.,edu,.,cn,/,hjbin,目 录,数据加密标准,公开密钥算法,数据加密标准,（,Data Encryption Standard,DES),背景,发明人,：美国,IBM,公司,W.,Tuchman,和,C.Meyer,1971-1972,年研制成功,基础：1967年美国,Horst,Feistel,提出的理论,产生：美国国家标准局（,NBS)1973,年5月到1974年8月两次发布通告，,公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳,了,IBM,的,LUCIFER,方案,标准化：,DES,算法1975年3月公开发表，1977年1月15日由美国国家标,准局颁布为数据加密标准（,Data Encryption Standard），,于,1977年7月15日生效,背景,美国国家安全局（,NSA,National Security Agency),参与了美国国家标准局制定数据加密标准的过程。,NBS,接受了,NSA,的某些建议，对算法做了修改，并将密钥长度从,LUCIFER,方案中的128位压缩到56位,1979年，美国银行协会批准使用,DES,1980,年，,DES,成为美国标准化协会(,ANSI),标准,1984年2月，,ISO,成立的数据加密技术委员会(,SC20),在,DES,基础上制定数据加密的国际标准工作,DES,概述,分组加密算法：明文和密文为64位分组长度,对称算法：加密和解密除密钥编排不同外，使用同一算法,密钥长度：56位，但每个第8位为奇偶校验位，可忽略,密钥可为任意的56位数，但存在弱密钥，容易避开,采用混乱和扩散的组合，每个组合先替代后置换，共16轮,只使用了标准的算术和逻辑运算，易于实现,DES,加密算法的一般描述,输入64比特明文数据,初始置换,IP,在密钥控制下,16轮迭代,初始逆置换,IP,-1,输出64比特密文数据,交换左右32比特,DES,加密过程,DES,加密过程,令,i,表示迭代次数，,表示逐位模2求和，,f,为加密函数,DES,解密过程,令,i,表示迭代次数，,表示逐位模2求和，,f,为加密函数,DES,中的各种置换、扩展和替代,初始置换,IP,和初始逆置换,IP,1,IP,和,IP,1,IP,IP,1,L,i-,1,（32,比特）,R,i,-,1,（32,比特）,L,i,（32,比特）,48比特寄存器,选择扩展运算,E,48比特寄存器,子密钥,K,i,（48,比特）,32比特寄存器,选择压缩运算,S,置换运算,P,R,i,（32,比特）,L,i,=,R,i,-,1,DES,的,一轮迭代,扩展置换-盒,32位扩展到48位,扩展,压缩替代,S-,盒,48位压缩到32位,共8个,S,盒,S-,盒1,S-,盒2,S-,盒3,S-,盒4,S-,盒5,S-,盒6,S-,盒7,S-,盒8,S-,盒的构造,S-,盒的构造,DES,中其它算法都是线性的，而,S-,盒运算则是非线性的,S-,盒不易于分析，它提供了更好的安全性,所以,S-,盒是算法的关键所在,S-,盒的构造准则,S,盒的每一行是整数0，15的一个置换,没有一个,S,盒是它输入变量的线性函数,改变,S,盒的一个输入位至少要引起两位的输出改变,对任何一个,S,盒和任何一个输入,X，S（X）,和,S(X,001100）,至少有两个比特不同（这里,X,是长度为6的比特串）,对任何一个,S,盒，对任何一个输入对,e,f,属于0,1,S(X)S(X,11e,f00),对任何一个,S,盒，如果固定一个输入比特，来看一个固定输出比特的值，这个输出比特为0的输入数目将接近于这个输出比特为1的输入数目,S-,盒的构造要求,S-,盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度,提供了密码算法所必须的混乱作用,如何全面准确地度量,S-,盒的密码强度和设计有效的,S-,盒是分组密码设计和分析中的难题,非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门,置换,p-,盒的构造,p-,盒的构造准则,P,置换的目的是提供雪崩效应,明文或密钥的一点小的变动都引起密文的较大变化,DES,中的子密钥的生成,密钥置换算法的构造准则,设计目标：子密钥的统计独立性和灵活性,实现简单,速度,不存在简单关系：(给定两个有某种关系的种子密钥,能预测它们轮子密钥之间的关系),种子密钥的所有比特对每个子密钥比特的影响大致相同,从一些子密钥比特获得其他的子密钥比特在计算上是难的,没有弱密钥,L,i-,1,（32,比特）,R,i,-,1,（32,比特）,L,i,（32,比特）,48比特寄存器,选择扩展运算,E,48比特寄存器,子密钥,K,i,（48,比特）,32比特寄存器,选择压缩运算,S,置换运算,P,R,i,（32,比特）,L,i,=,R,i,-,1,DES,的,一轮迭代,DES,加密算法的一般描述,DES,的,工作模式,电子密码本,ECB(electronic codebook mode),密码分组链接,CBC(cipher block chaining),密码反馈,CFB(cipher feedback),输出反馈,OFB(output feedback),电子密码本,ECB,ECB,的特点,简单和有效,可以并行实现,不能隐藏明文的模式信息,相同明文,生成,相同密文，,同样信息多次出现造成泄漏,对明文的主动攻击是可能的,信息块可被替换、重排、删除、重放,误差传递：密文块损坏,仅,对应明文块损坏,适合于传输短信息,密码分组链接,CBC,CBC,的特点,没有已知的并行实现算法,能隐藏明文的模式信息,需要共同的初始化向量,IV,相同明文,生成,不同密文,初始化向量,IV,可以用来改变第一块,对明文的主动攻击是不容易的,信息块不容易被替换、重排、删除、重放,误差传递：密文块损坏,两,明文,块,损坏,安全性好于,ECB,适合于传输长度大于64位的报文，还可以进行用户鉴别,是大多系统的标准如,SSL、,IPSec,密码反馈,CFB,CFB:分组密码,流密码,假定：,Si,为移位寄存器,传输单位为,j,bit,加密:,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,密码反馈,CFB,加密,C,i,=P,i,(,E,K,(,S,i,),的高j位),;,S,i,+1,=(,S,i,j)|,C,i,密码反馈,CFB,解密,P,i,=,C,i,(,E,K,(,S,i,),的高j位),;,S,i,+1,=(,S,i,j)|,C,i,CFB,的特点,分组密码,流密码,没有已知的并行实现算法,隐藏了明文模式,需要共同的移位寄存器初始值,IV,对于不同的消息，,IV,必须唯一,误差传递：一个单元损坏影响多个单元,输出反馈,OFB,O,FB:分组密码,流密码,假定：,Si,为移位寄存器,传输单位为,j,bit,加密:,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位),输出反馈,OFB,加密,C,i,=P,i,(,E,K,(,S,i,),的高j位),;,S,i,+1,=(,S,i,j)|,(,E,K,(,S,i,),的高j位),输出反馈,OFB,解密,P,i,=,C,i,(,E,K,(,S,i,),的高j位),;,S,i,+1,=(,S,i,j)|,(,E,K,(,S,i,),的高j位),0,FB,的特点,分组密码,流密码,没有已知的并行实现算法,隐藏了明文模式,需要共同的移位寄存器初始值,IV,对于不同的消息，,IV,必须唯一,误差传递：一个单元损坏只影响对应单元,对明文的主动攻击是可能的,信息块可被替换、重排、删除、重放,安全性较,CFB,差,多重,DES,两重,DES,三重,DES,DES,的,安全性,F,函数(,S-Box),设计原理未知,密钥长度的争论,DES,的,破译,弱密钥与半弱密钥,DES,密钥长度,关于,DES,算法的另一个最有争议的问题就是担心实际,56,比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有 个,早在,1977,年，,Diffie,和,Hellman,已建议制造一个每秒能测试100万个密钥的,VLSI,芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要,2000万,美元,DES,密钥长度,在,CRYPTO93,上，,Session,和,Wiener,给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以,16,次加密能同时完成。花费,10万,美元，平均用,1.5,天左右就可找到,DES,密钥,美国克罗拉多洲的程序员,Verser,从,1997,年2月,18,日起，用了,96,天时间，在,Internet,上数万名志愿者的协同工作下，成功地找到了,DES,的密钥，赢得了悬赏的,1,万美元,DES,密钥长度,1998年7月电子前沿基金会（,EFF）,使用一台25万美圆的电脑在56小时内破译了56比特密钥的,DES,1999,年1月,RSA,数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个,DES,的密钥,破译,DES,1990年，以色列密码学家,Eli,Biham,和,Adi Shamir,提出了差分密码分析法，可对,DES,进行选择明文攻击,线性密码分析比差分密码分析更有效,弱,密钥与半弱密钥,弱密钥:,E,K,E,K,=I,，DES,存在4个弱密钥,即：,半弱密钥:,E,K1,=E,K2,，,至少有12个半弱密钥,即：,其它常规分组加密算法,Triple DES,IDEA,RC5,RC6,AES,其他一些较实用的算法，如,Blowfish，CAST，,以及,RC2,等,使用常规加密进行保密通信,易受,攻击的位置,电话公司,市话局,接线盒,链路加密和端到端加密,存储转发通信的加密覆盖范围,各种加密策略包含的内容,链路层加密,对于在两个网络节点间的某一次通信链路,链路加密能为网上传输的数据提供安全保证,所有消息在被传输之前进行加密,在每一个节点对接收到的消息进行解密,然后先使用下一个链路的密钥对消息进行加密,再进行传输,链路层加密的优点,由于在每一个中间传输节点消息均被解密后重新进行加密,因此,包括路由信息在内的链路上的所有数据均以密文形式出现。这样,链路加密就掩盖了被传输消息的源点与终点,由于填充技术的使用以及填充字符在不需要传输数据的情况下就可以进行加密,这使得消息的频率和长度特性得以掩盖,从而可以防止对通信业务进行分析,链路层加密的缺点,链路加密通常用在点对点的同步或异步线路上,它要求先对在链路两端的加密设备进行同步,然后使用一种链模式对链路上传输的数据进行加密。这就给网络的性能和可管理性带来了副作用,在一个网络节点,链路加密仅在通信链路上提供安全性,消息以明文形式存在,因此所有节点在物理上必须是安全的,否则就会泄漏明文内容,在传统的加密算法中,用于解密消息的密钥与用于加密的密钥是相同的,该密钥必须被秘密保存,并按一定规则进行变化。这样,密钥分配在链路加密系统中就成了一个问题,因为每一个节点必须存储与其相连接的所有链路的加密密钥,这就需要对密钥进行物理传送或者建立专用网络设施。而网络节点地理分布的广阔性使得这一过程变得复杂,同时增加了密钥连续分配时的费用,节点加密,节点在操作方式上与链路加密是类似的:两者均在通信链路上为传输的消息提供安全性;都在中间节点先对消息进行解密,然后进行加密。因为要对所有传输的数据进行加密,所以加密过程对用户是透明的,然而,与链路加密不同,节点加密不允许消息在网络节点以明文形式存在,它先把收到的消息进行解密,然后采用另一个不同的密钥进行加密,这一过程是在节点上的一个安全模块中进行,节点加密要求报头和路由信息以明文形式传输,以便中间节点能得到如何处理消息的信息。因此这种方法对于防止攻击者分析通信业务是脆弱的,端到端加密,端到端加密允许数据在从源点到终点的传输过程中始终以密文形式存在,采用端到端加密(又称脱线加密或包加密),消息在被传输时到达终点之前不进行解密,因为消息在整个传输过程中均受到保护,所以即使有节点被损坏也不会使消息泄露,端到端加密的优点,端到端加密系统的价格便宜些,与链路加密和节点加密相比更可靠,更容易设计、实现和维护,端到端加密避免了其它加密系统所固有的同步问题,因为每个报文包均是独立被加密的,所以一个报文包所发生的传输错误不会影响后续的报文包,从用户对安全需求的直觉上讲,端到端加密更自然些。单个用户可能会选用这种加密方法,以便不影响网络上的其他用户,此方法只需要源和目的节点是保密的即可,端到端加密的缺点,通常不允许对消息的目的地址进行加密,这是因为每一个消息所经过的节点都要用此地址来确定如何传输消息,由于这种加密方法不能掩盖被传输消息的源点与终点,因此它对于防止攻击者分析通信业务是脆弱的,目 录,数据加密标准,公开密钥算法,公开密钥算法,公开密钥算法是非对称算法，即密钥分为公钥和私钥，因此称双密钥体制,双钥体制的公钥可以公开，因此也称公钥算法,公钥算法的出现，给密码的发展开辟了新的方向。公钥算法虽然已经历了,20,多年的发展，但仍具有强劲的发展势头，在鉴别系统和密钥交换等安全技术领域起着关键的作用,公开密钥算法的提出,公钥密码学是1976年由,Diffie,和,Hellman,在其“密码学新方向”一文中提出的，见文献：,W.,Diffie,and M.E.,Hellman,New,Directrions,in Cryptography，,IEEE Transaction on Information Theory,V.IT-22.No.6,Nov 1976,PP.644-654,公开密钥算法的提出,RSA,公钥算法是由,Rivest,Shamir,和,Adleman,在1978年提出来的,参见,Communitions,of the ACM.Vol.21.No.2.Feb.1978,PP.120-126,该算法的数学基础是初等数论中的,Euler,（,欧拉)定理，并建立在大整数因子的困难性之上,加密与解密由不同的密钥完成,加密：,解密：,知道加密算法，从加密密钥得到解密密钥在计算上是不可行的,两个密钥中任何一个都可以作为加密而另一个用作解密（不是必须的）,公开密钥算法的基本要求,基于公开密钥的加密过程,用公钥密码实现保密,用户拥有自己的密钥对,(,K,U,K,R,),公钥,K,U,公开，私钥,K,R,保密,基于公开密钥的鉴别过程,用公钥密码实现鉴别,条件：两个密钥中任何一个都可以用作加密而另外一个用作解密,鉴别：,鉴别保密,公开密钥算法,公钥算法的种类很多，具有代表性的三种密码：,基于整数分解难题（,IFP,）,的算法体制,基于离散对数难题（,DLP,）,算法体制,基于椭圆曲线离散对数难题（,ECDLP,）,的算法体制,Diffie,-,Hellman,密钥交换算法,单向陷门函数函数,满足下列条件的函数,f：,(1),给定,x，,计算,y=f(x),是容易的,(2)给定,y,计算,x,使,y=f(x),是困难的,(3),存在,z，,已知,z,时,对给定的任何,y，,若相应的,x,存,在，则计算,x,使,y=f(x),是容易的,所谓计算,x=,f,-1,(Y),困难是指计算上相当复杂，已无实际意义,单向陷门函数说明,仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性，,z,称为陷门信息,当用陷门函数,f,作为加密函数时，可将,f,公开，这相当于公开加密密钥，此时加密密钥便称为公开钥，记为,Pk,f,函数的设计者将,z,保密，用作解密密钥，此时,z,称为秘密钥匙，记为,Sk,。,由于设计者拥有,Sk,，,他自然可以解出,x=f,-1,(y),单向陷门函数的第(2)条性质表明窃听者由截获的密文,y=f(x),推测,x,是不可行的,Diffie,-,Hellman,密钥交换算法,Diffie,和,Hellman,在其里程碑意义的文章中，虽然给出了密码的思想，但是没有给出真正意义上的公钥密码实例，也既没能找出一个真正带,陷门,的单向函数,然而，他们给出单向函数的实例，并且基于此提出,Diffie,-,Hellman,密钥交换算法,Diffie,-,Hellman,密钥交换算法的原理,基于有限域中计算离散对数的困难性问题之上：设,F,为有限域，,gF,是,F,的乘法群,F,*,=F0=，,并且对任意正整数,x，,计算,g,x,是容易的；但是已知,g,和,y,求,x,使,y=,g,x,，,是计算上几乎不可能的,这个问题称为有限域,F,上的离散对数问题。公钥密码学中使用最广泛的有限域为素域,F,P,Diffie,-,Hellman,密钥交换协议描述,Alice,和,Bob,协商好一个大素数,p,，,和大的整数,g,，1gp，g,最好是,F,P,中的本原元，即,F,P,*,p,和,g,无须保密，可为网络上的所有用户共享,Diffie,-,Hellman,密钥交换协议描述,当,Alice,和,Bob,要进行保密通信时，他们可以按如下步骤来做：,(1),Alice,选取大的随机数,x，,并计算,X,=,g,x,(mod P),(2)Bob,选取大的随机数,x,，,并计算,X,=,g,x,(mod P),(3)Alice,将,X,传送给,Bob；Bob,将,X,传送给,Alice,(4)Alice,计算,K,=(X,),X,(mod P);Bob,计算,K,=（X),X,(mod P),易见，,K=K,=g,xx,(mod P),由(4)知，,Alice,和,Bob,已获得了相同的秘密值,K,双方以,K,作为加解密钥以传统对称密钥算法进行保密通信,RSA,算法,Euler,函数,所有模,m,和,r,同余的整数组成剩余类,r,剩余类,r,中的每一个数和,m,互素的充要条件是,r,和,m,互素,和,m,互素的同余类数目用,(m),表示，称,m,的,Euler,函数,当,m,是素数时，小于,m,的所有整数均与,m,互素，因此,(m)=m-1,对,n=,pq,p,和,q,是素数，,(n)=(p)(q)=(p-1)(q-1),Euler,函数,举例,设,p=3,q=5,那么,（,15,）,=,（,3-1,）*（,5-1,）,=8,这8个模15的剩余类是,：,1,，,2,，,4,，,7,，,8,，,11,，,13,，,14,RSA,算法的实现,实现的步骤如下：,Bob,为实现者,(1),Bob,寻找出两个大素数,p,和,q,(2)Bob,计算出,n=,pq,和,(n)=(p-1)(q-1),(3)Bob,选择一个随机数,e(0e,(n)，,满足(,e,(n)=1,(4)Bob,使用辗转相除法计算,d=e,-1,(mod,(n),(5)Bob,在目录中公开,n,和,e,作为公钥,密码分析者攻击,RSA,体制的关键点在于如何分解,n。,若分,解成功使,n=,pq,，,则可以算出,(n)（p-1)(q-1)，,然后由公,开的,e，,解出秘密的,d,RSA,算法编制,参数,T=N；,私钥,SK=D,；,公钥,PK=E,；,设：明文,M,，,密文,C,，,那么：,用公钥作业：,M,E,mod N=C,用私钥作业：,M,D,mod N=M,RSA,算法举例,设,p=7,q=17,n=7*17=119;,参数,T=n=119;,(n)=(7-1)(17-1)=96;,选择,e=5,gcd,(5,96)=1;,公钥,pk,=5;,计算,d,(d*e)mod 96=1;d=77;,私钥,sk,=77;,设,:,明文,m=19,加密：（,19,）,5,mod 119=66,脱密：（,66,）,77,mod 119=19,RSA,算法的安全性分析,密码分析者攻击,RSA,体制的关键点在于如何分解,n,若分解成功使,n=,pq,，,则可以算出,(n)（p-1)(q-1)，,然后由公开的,e，,解出秘密的,d,若使,RSA,安全，,p,与,q,必为足够大的素数，使分析者没有办法在多项式时间内将,n,分解出来,RSA,算法的安全性分析,建议选择,p,和,q,大约是100位的十进制素数,模,n,的长度要求至少是512比特,EDI,攻击标准使用的,RSA,算法中规定,n,的长度为512至1024比特位之间，但必须是128的倍数,国际数字签名标准,ISO/IEC 9796,中规定,n,的长度位512比特位,RSA,算法的安全性分析,为了抵抗现有的整数分解算法，对,RSA,模,n,的素因子,p,和,q,还有如下要求：,(1)|,p-q|,很大，通常,p,和,q,的长度相同；,(2),p-1,和,q-1,分别含有大素因子,p1,和,q1,(3)P1-1,和,q1-1,分别含有大素因子,p2,和,q2,(4)p+1,和,q+1,分别含有大素因子,p3,和,q3,RSA,算法的安全性分析,为了提高加密速度，通常取,e,为特定的小整数,如,EDI,国际标准中规定,e2161,ISO/IEC9796,中甚至允许取,e3,这时加密速度一般比解密速度快10倍以上,