网络信息安全第三章-1

•密钥必须秘密地分配•如果密钥被损害了，攻击者就能解密所有消息，并可以假装是其中一方。•密钥分配和管理传统密钥管理两两分别用一对密钥时，则当用户量增大时密钥空间急剧增大如:n=100时C(100,2)=4,995n=5000时C(5000,2)=12,497,500公钥密码体制的基本原理对称密码体制的缺点数字签名•用户选择一对密钥Ke和Kd，分别为公钥和私钥，并构造加密算法Ee和解密算法Ed。公钥密码算法•C=E(M,Ke)M=D(C,Kd)=D(E(M,Ke),Kd)•用户公开Ke和Ee密钥都是成对生成的，由一个公钥和一个私钥组成。注意：公钥密码的基本思想加密算法E解密算法D加密密钥Ke解密密钥Kd明文m明文m公开，其他用户可以像查找电话号码一样查到若用户A想向用户B传送一条消息M用户A用户BM用户A用户BCKeKd对称密钥加密方法公开密钥加密方法1用户A用户BCKeBKdBA查到B的公开加密钥KeB,用它加密M后得到C,将C发给B，B收到C以后，用自己保密的解密钥KdB解密C,得到明文M查找找到KeB方法1缺点•任何人都能够冒充用户A给B发消息，B无法察觉用户A用户BCKeBKdB查找找到KeB用户C此消息对用户A可能不利结论方法1无法保证信息的真实性公开密钥加密方法2用户A用户BCKdAKeA查找找到KeAA用自己保密的密钥KdA加密M,得到密文C，将C发给B，B收到C以后，查A的公开加密钥KeA,用KeA解密C后得到明文M。方法2缺点用户A用户BCKdAKeA查找找到KeA用户C截获密文用户C获取了明文结论方法2无法保证信息的秘密性公开密钥加密方法3用户A用户BCKeBKdB查找找到KeBKdAKeA查找找到KeAA用自己保密的密钥KdA加密M,得到中间密文S查到B的公开加密钥KeBA用KeB加密S得到CA发C给BS=D(M,KdA)C=E(S,KeB)用户AB用自己保密的密钥KdB解密C,得到中间密文SB接收C用KeA解密S得到M查到A的公开加密钥KeA用户BD(C,KdB)=SE(S,KeA)=M保证了数据的秘密性和真实性结论公钥密码应当满足的条件•加密算法和解密算法互逆，即对所有明文都有D(E(M,Ke),Kd)=M•计算上不能由Ke求出Kd•算法E和D都是高效的•E(D(M,Kd),Ke)=M单项函数单向函数是满足下列条件的函数f–(1)给定x，计算y=f(x)是容易的–(2)给定y,计算x使y=f(x)是困难的(所谓计算x=f-1(Y)困难是指计算上相当复杂已无实际意义)用于构造公钥密码常用的单向函数１多项式求根有限域GF(p)y=f(x)=(xn+an-1xn-1+…+a1x+a0)modp２离散对数如果p是一足够大的素数，a是{0,1,2,…,p-1}中与p互素的数。则已知p,a,x,计算y=f(x)=axmodp并不困难;若已知p,a,y,计算x=logbymodp，就很困难了。３大整数分解(FactorrizationProblme)若已知两个大素数p,q，求n=p×q仅需一次乘法，但已知n求p,q则是几千年来数论专家的一道难题。４菲-赫尔曼(Diffie-Hellman给定素数p，可构造一乘群Z*p，令α为Z*p的生成元，若已知αa,αb，求αab问题为菲-赫尔曼问题。５给定一个奇合数n和整数a，决定是否a为modn平方剩余问题。几个典型的公开钥密码系统•菲-赫尔曼（Diffie-Hellman）密码系统•RSA系统•背包系统•椭圆曲线密码体制RSA算法•RSA公钥算法是由Rivest,ShamirAdleman在1978年提出来的。•该算法的数学基础是初等数论中的Euler(欧拉)定理,并建立在大整数因子的困难性之上。•RSA算法起源欧拉定理aφ(m)≡1modm其中,φ(m)是比m小，且与m互素的正整数个数。若整数a和m互素，则素数一个大于1的整数，如果它的正因数只有1和它本身，就叫做质数（素数），否则就叫做合数。素因子分解•数n的因子分解是把它写成其它数的乘积n=a×b×c•素因子分解是把一个数写成素数的乘积形式eg.91=7×13•相对于把因子相乘得到一个数，进行一个数的因子分解是困难的。欧几里（Euclid）算法00000111111223332112221111nnnnnnnnnnnrrqrrrrrqrrrrrqrrrrrqrbbrrbqa用于求两个数的最大公约数?),gcd(banrba),gcd(例：利用Euclid算法求gcd(1694，917)77719171694140177791777514077763177140141637774146302714得gcd(1694，917)=7RSA算法描述•选择两个素数p,q,对外界保密•计算n=p*q•计算Ø(n)=(p-1)(q-1)•选择e,使它成为是Ø(n)的一个互质数•确定d,使得d*e=1modØ(n),并且dØ(n)数字n应该为200位或者是一个更大的数字。这样，p和q都至少在100位。实际使用中，密钥至少要1024位。对于敏感信息，可以考虑2048位或者以上1.生成RSA密钥d为私钥，e为公钥，p、q不再需要，丢弃。(1)把m分成等长数据块m1、m2、…、mi，块长s，其中2s≤n，s要尽可能的大。(2)对应的密文是RSA算法描述3.解密ci≡meimodn2.加密nCmdiimod例3.2p=43,q=59,n=pq=43×59=2537φ(n)=42×58=2436,e=13解：利用Euclid算法求d，解方程d×e≡1mod2436。对明文publickeyencryptions，用RSA算法求密文。（假定s=2）5187132436325132135112302121231)35(352352)2513(55213)187132436(52132436513937左右同时模2436，即937×13≡1mod2436即取e=13,d=937利用加密得：pu=0095,bl=1648,ic=1410,ke=1299,ye=1365,nc=1379,ry=2333,pt=2332,io=1751,ns=1289。明文publickeyencryptions，先将明文按两个一组进行分块，再将明文数字化，如按英文字母表的顺序得：pu=1520,bl=0111,ic=0802,ke=1004,ye=2404,nc=1302,ry=1724,pt=1519,io=0814,ns=1418。ci≡meimodn加密设张小姐需要发送机密信息（明文）m=85给李先生，她已经从公开媒体得到了李先生的公开密钥（n，e）=（143，7），计算密文为：c=memodn=857mod143=123并发送给李先生。李先生在收到密文c=123后，利用只有他自己知道的秘密密钥(d=103),计算：m=cdmodn=123103mod143=85，所以，李先生可以得到张小姐发给他的真正的信息m=85。例题：例题：•选择p=7,q=17•N=pq=119,Ø(n)=(p-1)(q-1)=6*16=96•选择随机整数e=5，与96互素•找出d,使得d*e=1mod96,选择d=77•算法C=MemodnM=Cdmodn•选择明文19，C=195mod119=66•密文66，M=6677mod119=19RSA算法的安全性•对RSA算法的攻击实际上等效于对n的乘积分解。–由于M=Cdmodn,n公开,则需要求出d–由于de=1modØ(n),e已知–需要求出Ø(n)–由于Ø(n)=(p-1)(q-1)，所以必须求出p,q–n=pq,所以必须对n进行分解最新纪录2007年，瑞士洛桑理工学院的ArjenLenstra宣称，他们的分布式计算工程在经过11个月的努力后破解了一个307位的RSA密钥，并且已经有能力在不久后破解700位，因此他警告说，在五六年后，随着各种计算、破解技术的不断强大，也许1024位的RSA加密都不能完全保险，人们必须寻求更安全的加密技术。大素数分解记录若n|（2n-2），则n为素数。若p为素数，则Mp=2p-1为素数Fermat推测Fn=22n+1为素数,n为正整数RSA问题1.如何选取大的素数?×素数在数轴上的分布情况是如x=10,π(x)=4,该式所含的素数为2、3、5、7。xxxln)(问题2.有多少素数?答案是有无穷多个。素数位数所含素数个数64bit2.05×1017128bit1.9×1036256bit3.25×1074①概率测试素数法问题3.如何产生一个素数?方法：对于一个给定的大正整数N，每进行一次检验，给出yes：N为素数的概率为1/2，或者no：N不是素数，若N通过r次检验，则N不是素数的概率为ε=2-r，则N为素数的概率为1-ε，若r足够大(如r=100)，则几乎认为N是素数。②确定性验证素数法定理令pi+1=hipi+1，若满足下述条件，则pi+1必为素数。(1)pi是奇素数;(2)hi4(pi+1),hi为偶数;(3)(4);mod121iphpii1mod12ihpi幂剩余函数的特性周期性即反复运算C=Memodn若干次后，将还原为最初始的M。例如,p=17,q=11,n=pq=187,e=7,m=123。m1=123,1237≡183mod187m2=183,183+7≡72mod187m3=72,72+7≡30mod187m4=30,30+7≡123mod187所谓安全素数p，应满足：(1)p是一个位数足够大的随机素数;(2)p-1含有一个大的素数因子r;(3)p+1含有一个大的素数因子;(4)r-1含有一个大的素数因子t安全素数(1)选择两个指定长度的奇数a,b(2)在a附近产生随机素数s，在b附近产生随机素数t(3)由t产生素数r①r=1+2t;②若r非素数，则r=r+2直到r(4)由r,s生成p:①p=(sr-1-rs-1)mod(rs);②若p为偶数,则p=p+rs;③p=p+2rs直到p为素数。如何获得安全素数？高次幂的求模算法步骤如下：将e用二进制表示,e=kt,kt-1,…,k0,ki∈{0,1},0≤i≤tc=1Fori=t~0C=C2modp若ki=1，则C=C(Mmodp)modpC=Memodp，已知M、e、p，C？例，求117mod17RSA的实用性B加密A解密A的私钥密文A的公钥明文明文(a)A加密B解密A的公钥密文A的私钥明文明文(b)B加密A解密A的私钥密文A的公钥明文明文(a)A加密B解密A的公钥密文A的私钥明文明文(b)加密解密模型认证模型RSA算法和DES算法加密体制。处理效率。密钥管理。安全性。应用。设在一个有限域GF(P)上讨论，P为素数，令g∈GF(q)，g为非零元素，明文为m，密文为c。菲-赫尔曼（Diffie-Hellman）密码系统(1)密钥的生成(用户A)私钥：α,0αP公钥：β≡gα(2)加密BAmc①B在区间［1,P-1］内选取一个随机数k,计算y=gkc=mβk=m(gα)k②找A的公钥,计算(3)解密A收到B的密文c后，计算mgmggmycmkkkk思考1.在RSA算法中，如果一个用户的私钥发生泄露，是他不重新需选择模数，而是保持n，重新选择e、k。这样做是否安全？2.在使用RSA系统的公钥系统中，你窃听到发给密钥为e=5、n=35的用户的密文C=10，对应的明文M应该是什么？设计假定用户A要把一个秘密信息发送给其他5个用户，设用户A和其他每个用户都有一对公钥，一对私钥，若要求A不是单独给每个用户发秘密信息，而是给所有的用户只发送同一个仅含有该文件的一个加密结果的消息。试问A如何完成这一方案？