现代密码技术ppt课件

现代密码技术,DES、RSA,计算机网络安全,Chapter3,1,3.1数据加密标准DES,19世纪70年代，DES(theDataEncryptionStandard)最初由IBM公司提出。DES是一种分组密码，它采用56比特长的密钥将64比特的数据加密成64比特的密文。DES完全公开了加密、解密算法。因而是一个最引人注目的分组密码系统。它一直是国际上商用保密通信和计算机通信的最常用加密算法。特别是应用于保护金融数据的安全（例如：ATM取款机）。,2,3.1数据加密标准DES,DES的发展1977年正式颁布为数据加密标准（DES-DataEncryptionStandard）。1979年，美国银行协会批准使用DES。1980年，DES成为美国标准化协会(ANSI)标准。1984年，ISO开始在DES基础上制定数据加密的国际标准。美国国家安全局NSA每隔年对该算法进行评估，1994年，决定1998年12月之后不再使用DES。现已经确定了选用Rijndael算法作为高级加密算法AES。,3,3.1数据加密标准DES,分组密码就是一个明文分组被当作一个整体来产生一个等长（通常）的密文分组的密码，通常使用的是64或者128位分组大小。分组密码的实质是，设计一种算法，能在密钥控制下，把n比特明文简单而又迅速地置换成唯一n比特密文，并且这种变换是可逆的（解密）。现在使用的大多数对称分组加密算法都是基于Feistel分组密码结构的。,4,3.1数据加密标准DES,设计原则分组长度分组越长则安全性越高，但加/解密速度越低，分组长度为64位是一个合理的折衷。密钥长度密钥越长越安全，但加/解密速度越低，64位长的密钥已被证明是不安全的，128位是常用的长度迭代次数迭代越多越安全，通常为16次迭代子密钥产生算法越复杂则密码分析越困难轮函数越复杂则抗密码分析的能力越强,5,分组密码的两个基本设计方法。（如何挫败基于统计方法的密码分析？Shannon建议了两种对付统计分析的方法：扩散和混淆)（1）扩散(diffusion)：扩散指使明文的统计特征消散在密文中，可以让每个明文数字尽可能地影响多个密文数字获得，等价于说每个密文数字被许多明文数字影响。一个扩散的例子就是当前明文字母开始的若干明文字母之和(mod26)作为对应的密文字母。在二进制分组密码中，对明文进行置换后再用某个函数作用，重复多次就可获得较好的扩散效果。因为原始明文中的不同位对密文某一位都会产生影响。,3.1数据加密标准DES,6,3.1数据加密标准DES,（2）混淆(confusion)其目的在于使作用于明文的密钥和密文之间的关系复杂化，是明文和密文之间、密文和密钥之间的统计相关特性极小化，从而使统计分析攻击不能奏效。,7,3.1数据加密标准DES,乘积密码（ProductCipher）就是以某种方式连续执行两个或多个简单密码（如替代、置换），以使得所得到的最后结果或乘积比其任意一个组成密码都更强的分组密码。Shannon提出交替使用混淆和扩散进行乘积密码。基于Shannon理论，Feistel建议交替地使用代换和置换。,8,Feistel密码结构,方法将输入分组分成左右两部分。以右半部数据和子密钥作为参数，对左半部数据实施代换操作。将两部分进行互换，完成置换操作。优点能够产生雪崩效应快速软件加解密易于分析可自行设计的内容：分组长度密钥长度轮数子密钥生成算法轮函数,9,LEi=REi-1REi=LEi-1F(REi-1,Ki),Feistel每一轮的加密(替换+置换),3.1数据加密标准DES,10,3.1数据加密标准DES,DES加密操作DES在加解密过程中，将明文和密文分成64比特的分组进行操作。其一大特点是解密过程与加密过程是相似的。首先对64比特的明文分组进行IP置换。IP置换将输入分组的第58比特作为输出的第1比特，输入的第50比特作为输出的第2比特，依次类推。然后用密钥k对得到的结果进行迭代操作。最后再对迭代操作的结果进行IP-1置换产生输出分组。下面是DES算法的略图。,11,12,48bitsubkey,13,14,5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725,3.1数据加密标准DES,（1）初始置换与逆置换,IP：,IP-1：,例如：IP(675a69675e5a6b5a)=(ffb2194d004df6fb),15,加密：Li=Ri-1Ri=Li-1f(Ri-1,ki),（2）Feistel每一轮的加密过程,3.1数据加密标准DES,解密：Ri1=LiLi1=Rif(Ri1,Ki)Rif(Li,Ki),16,1)其中函数f的定义如下图所示：,17,E是一种输入为32比特，输出为48比特的置换，具体的置换方法如下，其置换方法和IP类似。32123454567898910111213E：12131415161716171819202120212223242524252627282928293031321,2)E扩展(32-48),18,称s1,s2,s8为s盒，实现明文消息在密文消息空间中的随机非线性分布，可以抵抗差分分析攻击DC。s盒的运算规则为，输入的6比特数据的第一和第六比特为s和的行数，其余比特决定s盒的列数，例如，当s1的输入为011011时，其输出为0101。s11441312151183106125907015741421311061211953841148136211151297310501512824917511314100613,3)S盒子的设计(压缩置换),DES的核心部分,19,8个S盒,20,P为一个输入和输出都为32比特的置换，具体形式如下：1672021291228171152326P：518311028241432273919133062211425,4)P置换,第16比特第1比特第07比特第2比特第25比特第32比特,21,DES算法的密钥k由一个56位的密钥以及附加的8位奇偶校验位组成，经过密码扩展算法可以把它扩展为16个子密钥。其中迭代次数与左移的比特数关系如下：迭代次数12345678910111213141516左移位数1122222212222221,3.1数据加密标准DES,5）轮密钥的产生,22,56位,28位,28位,56位,28位,28位,56位,56位,23,574941332517915850423426181025951433527PC-1：19113605244366355473931231576254463830221466153453729211352820124141711241532815621102319124268PC-2：1672720132415231374755304051453348444939563453464250362932,两个置换选择,（舍弃了奇偶校验位，即第8，16，64位）,（舍弃了第9,18,22,25,35,38,43,54比特位）,24,总结：DES一轮迭代的过程,25,DES解密操作,由迭代操作的定义，显然可以得到Ri-1=LiLi-1=Rif(Li,ki)若记加密算法每一轮的操作为Ti，我们可以方便的得出解密算法：DES-1=IP-1T1T2T15T16IP,26,3.1数据加密标准DES,DES的雪崩效应,27,雪崩效应AvalancheEffect,明文或密钥的一比特的变化，引起密文许多比特的改变。如果变化太小，就可能找到一种方法减小有待搜索的明文和密文空间的大小。如果用同样密钥加密只差一比特的两个明文：0000000000000000.000000001000000000000000.000000003次循环以后密文有21个比特不同，16次循环后有34个比特不同如果用只差一比特的两个密钥加密同样明文：3次循环以后密文有14个比特不同，16次循环后有35个比特不同,28,56位密钥长度问题56-bit密钥有256=72,057,584,037,927,9367.2亿亿之多强力搜索(bruteforcesearch)似乎很困难，20世纪70年代估计要10002000年技术进步使穷举搜索成为可能1997年1月29日，RSA公司发起破译RC4、RC5、MD2、MD5，以及DES的活动，破译DES奖励10000美金。结果仅搜索了24.6%的密钥空间便得到结果，耗时96天。1998年在一台专用机上(EFF)只要三天时间即可1999年在超级计算机上只要22小时!,3.1数据加密标准DES,DES的强度,29,S-box问题其设计标准没有公开，但是迄今没有发现S盒存在致命弱点计时攻击计时攻击利用的事实是加密或解密算法对于不同的输入所花的时间有细微的差别DES能够很好地抵抗计时攻击弱密钥(注意避免)弱密钥：8个弱密钥半弱密钥：2个半弱密钥,3.1数据加密标准DES,DES的强度,30,DESCrackerTheElectronicFrontierFoundationbuilttheso-calledDESCrackersupercomputerin1998tocrack56-bitDESencryption.ItlaterwonRSALaboratorysDESChallengeIIcontestinabout56hours.DESCrackerhad26(andlater27)systemboards,eachwith32or64customAWT-4500DeepCrackchips,foratotalofabout1,500to1,800chips.,31,3.2非对称密码-RSA,对称算法的缺陷为事先协商密钥，需另外的安全信道或KDC不能满足签名的需求密钥数量多,32,3.2非对称密码-RSA,NewDirectionsinCryptographyWhitfieldDiffie，Hellman1976提出了公钥密码算法的概念和思路提出了鉴别和签名问题提出了D-H密钥协商协议国际上已提出了许多公钥密码体制，主要有：基于大整数因子分解问题的RSA；另一类是基于离散对数问题的ElGamal公钥密码和椭圆曲线公钥密码。,33,3.2非对称密码-RSA,对称密码和非对称密码各有利弊。非对称密码体制在几方面易受攻击（例如伪装），且加/解密很慢。但它有突出的优点，可以与对称密码体制一起创建完美和有效的密码机制，可以提供高级别的安全性。因此，公钥密码一般用于密钥分发、数据完整性、消息认证等方面。,34,3.2非对称密码-RSA,单向函数函数值计算很容易：已知x，很容易计算y=f(x)逆计算是不可行的：已知y，很困难计算x=f-1(y)举例：打碎/拼接、平方/开方、乘法/分解单向陷门函数如果知道某个陷门(秘诀)，即能容易恢复x（陷门即为私钥）举例：魔方的置乱/恢复如果有那个口诀，就能很快恢复单向散列函数抗冲突性质,35,背包问题,背包问题描述已知一长度为b的背包及长度分别为a1,a2,an的n个物品假定这些物品的直径与背包相同若从这些物品中选出若干个正好装满这个背包那么究竟是那些物品?即求解其中ai和b都是正整数背包问题是著名的np完备类困难问题至今没有好的求解方法,而对2n中可能进行搜索实际上是不可能的,36,37,3.2非对称密码-RSA,公钥算法参数建立每个用户生成密钥对(Ke、Kd)Ke或Kd是一个或几个数(大数)而不是随机比特（对称算法）Ke需要公开Kd得自己秘密保留(公钥publickey私钥privatekey密钥secretkey)公钥的发布从Ke推导Kd的困难性使Ke不怕被公开公开的目录服务公钥Ke要在专门机构（CA）登记,38,3.2非对称密码-RSA,公钥算法加密加密（如果有人要给该用户发送消息P）先获得该用户的公开钥Ke加密C=E（P，Ke）传输解密D（C，Kd）P除非拥有Kd，否则不能解开*一般用于传输会话密钥（和签名及鉴别）,39,3.2非对称密码-RSA,公钥密码算法的实现对称算法替换混乱基于某些数学特性:从公钥推导私钥理论可能，但计算困难(从私钥到公钥容易);大整数的分解离散对数问题,40,公钥算法用来加密图示,41,消息来源鉴别和数字签名,使用加密/解密操作对称的算法，如RSA对消息H签名：S=Sig（H，Kd）验证Ver（C，Ke）？H消息H必然是Kd的持有人签署的,42,公钥算法用来鉴别图示,43,RSA算法,在Diffle和Hellman提出公钥的设想后两年，MIT的Rivest、Shamir和Adleman联合提出了被人们称之为RSA的公钥密码系统，其基础是数论的欧拉定理，其安全性依赖于大整数因数分解的困难性。基本参数分组密码算法基于整数乘法明/密文分组以及公/私钥被看作小于n的整数加/解密是模乘运算,44,45,46,RSA参数建立,找素数选取两个512bit的随机素数p,q计算模n和Euler函数(n)npq(n)=(p-1)(q-1)找ed1mod(n)【ed+r(n)=1】选取数e，用扩展Euclid算法求数d发布发布(e,n)，这是公钥ked保密，(d,n)是私钥kd,47,扩展的辗转除法,48,扩展Euclid算法举例,221mod31311229-1229即30229mod312229422-2(-122)4即3224mod319241-122-2(322)1即24221mod31281mod757522819-22819即732819mod7528119928-1(-228)9即3289mod7519291(-228)-2(338)1即67281mod752691mod349349126980-126980即-126926938029269-3(-1269)29即42698022922(-1269)-2(4269)22即-9269291227(4269)-1(-9269)7即1326922371(-9269)-3(13269)1即-48269得301,49,Euler欧拉函数,欧拉函数(n)定义为小于n而互素的正整数的个数也即模n的简化剩余集(互素)的元素个数举例（若p、q都是素数）(p)p-1(pq)=(p)(q)(p-1)(q-1)pq-p-q+1比如n1535pq则(n)(3-1)(5-1)8即8：1、2、4、7、8、11、13、14,50,欧拉定理,如果a、n互素，则a(n)1modn，或即a(n)1amodn比如n1535，(n)81、2、4、5、7、8、11、13、1481mod15而3、6、9、10、128!1mod15,51,RSA加密解密,加密明文分组m做为整数须小于nc=memodn解密m=cdmodnRSA的安全性是基于加密函数ek(x)=xe(modn)是一个单向函数所以对的人来说求逆计算不可行而Bob能解密的陷门是分解n=pq知(n)=(p-1)(q-1)从而用欧氏算法解出解密私钥d.,52,RSA的正确性,证明依据Euler定理，在modn的含义下cd(me)dmedmodnmk(n)+1modnmmodn（据Euler定理）,53,关于mk(n)+1,如果npq，则mk(n)+1mmodn如果m和n互素，直接使用欧拉定理即得如果m和n不互素，则公因子必是p(或者q)事实上，此时mk(n)+1mmodp（因为m是p的倍数）mk(n)+1mmodq（根据Fermat小定理）mk(n)+1mmodpq（由以上两式）,54,Fermat小定理,若p是素数，gcd(a,p)=1，则ap-11modp，或即apamodp举例25-11mod5411-11mod11证明见备注,55,RSA实例,选p7，q17则npq119且(n)(p-1)(q-1)61696取e5则d77(57738549611mod96)公钥（5，119），私钥（77，119）加密m19则cmemodn=195mod119=66mod119解密c66mcdmodn=6677mod11919mod119,56,RSA考虑,素数必须够大，否则对手可能很快分解n判定，试除法不可行判定，采用Miller-Rabin概率测试方法强素数(p-1)/2和(q-1)/2应是素数选取较小的e（较大的d）e：3、65537快速计算XY%Z,57,RSA中基本计算的复杂度,大数的加、减计算复杂度O(k),O(k)字加法K是大数的字宽度大数的乘、除(逆元)计算复杂度O(k2),O(k2logk)字乘法大数指数运算xcmodnO(k2logc)字乘法注：都是在modn下,58,模幂乘举例,97221%2003（都在模2003意义下）9722197128+64+16+8+4+19712897649716978974971依次计算971、972、974、978、971697128一直平方下去即可，并保持模2003如果某次方在1式出现，则累乘累积开始是1*乘法次数O(log2Y),59,模幂乘算法实现,计算W=XYmodZW=1ForeachbitofY=Y1Y2YkW=W*W%ZifYi=1thenW=W*X%ZEndfor,60,分解里程碑,十/二进制日期MIPS年方法69/1983二次筛法106/1989100/332April19917quadraticsieve110/365April199275quadraticsieve120/398June1993830quadraticsieve129/428April19945000quadraticsieve130/431April19