《公钥密码.ppt》由会员分享，可在线阅读，更多相关《公钥密码.ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、公钥密码公钥体制v一 什么是公钥体制?v 保密通信在进入了互联网时代后,用户的大量增加对于保密通信的需求就给传统密码带来的很大的麻烦.v 这是因为传统密码要求通信双方的密钥应通过秘密信道私下约定.若互联网上有n个用户,则需要n(n-1)/2个密钥.若n=1000,则这个数字就是大约500000个,这么庞大的密钥如何管理和定期更换?更有甚者,如果每一个用户与其他n-1个用户的保密通信,需保存n-1个密钥,记在本子或存在电脑上,这本身就不安全.公钥体制v 因此这些新课题就促使了保密体制一个新的变革的产生:美国人Diffie和Hellman于1976年在密码学新方向中提出了一个新的保密体制-公开密钥
2、体制.公钥体制v 它的基本思想是:每一个用户有一个加密密钥 ,和一个解密密钥 ,将 公开,而 保密;并且 的公开不妨碍 的安全.可以将各个用户 的集中成公钥文件,公开发给所有用户.公钥体制v 若B欲跟A保密通信,通过公钥文件查到A的公开密钥 ,用它得到加密密文 .将c传输给A,A用只有他自己掌握的解密密钥 解密恢复出明文 .v 在通信中任何第三者截获密文c,由于不掌握解密密钥 ,也无法得知明文m.公钥体制v注:1.因为 ,所以公钥密码也就被称为”非对称密码”,而以往的传统密码因为通信双方的密钥都一样,也被称为”对称密码”.v2.公钥体制的一个特点:对于每一个用户的每一对密钥 ,由 算 很简单,
3、而由 算 很困难.MH背包公钥v二背包公钥密码v(1)背包问题v 当公钥密码这个设想刚提出时,还没有一个实例.而为了解决组合数学中的背包问题,Merkle和Hellman提出了MH背包公钥.v 所谓背包问题:已知有n个物品,它的重量分别为 ,今有一个重量为b的背包,问它装有哪些物品?v用数学语言描述:若 =0或1,i=1,2,nv 满足v这个问题是著名的NP完备类问题,至今还没有好的解法.当n很大的时候,用穷举法是不现实的.MH背包公钥(2)超递增序列 并非所有的背包问题都没有有效算法,若序列 满足条件 ,i=2,3,n 成立时,有多项式解法.满足这样条件的序列称为超递增序列.例子:1,2,4
4、,8,是一个超递增序列.求因为4332,所以 ,带入得 1116,所以所以 MH背包公钥(2)MH背包公钥1由私人密钥产生公开密钥:先选取一个超递增序列 ,选取整数m,w:,且w,m互素.则存在t,使得 .作变换 ,k=1,2,n得到序列 ,且序列 不在具有超递增特性.公钥:私钥:,m,tMH背包公钥v2 加密(AB)vB的公钥是 ,私钥是 ,m,t.v明文P是二进制的字符串,设 ,=0或1v则密文为MH背包公钥v3解密vB收到密文c后,由 有v 由 是超递增序列,容易解出 而得到明文P.RSA公钥v三 RSA公钥体制v 在MH背包公钥系统提出得同时,Rivest ,Shamir和Adlema
5、n联合提出了RSA公钥系统.MH背包系统作为第一批公钥系统由于它的超递增序列的特性而容易被人攻击,而RSA公钥则是现今比较成熟的公钥系统.它的基础就是数论的欧拉定理,其安全性依赖于大数的因数分解的困难性.RSA公钥(1)RSA加解密算法 RSA的加密过程为:1 选取两个素数p和q(保密).2 计算n=pq(公开),(保密)3 随机选取整数e(公开),满足 (公开)4 计算d,满足 (保密)RSA公钥v 利用第一步之前需要将明文数字化,并取长度小于 的数字作为明文块.v其加密算法为:v解密算法:v公钥是(e,n),私钥d,其中p,q保密.RSA公钥(3)RSA的安全性讨论 若n=pq被因子分解,
6、则 马上被暴露,从而私钥d可以由 马上算出.因此RSA的安全性完全依赖于因子分解的复杂性.目前对大整数进行因子分解最快的方法是NSF,它的时间复杂度为exp(sqrt(ln(n)lnln(n)在实际应用中一般取p和q为100位的十进制数.最好是选用强素数.强素数就是满足以下条件的素数:素数p,p-1和p+1分别有大素数因子p1和p2,p1-1有大素数因子q.RSA公钥(4)RSA与数字签名vRSA的一个重要性质就是用于数字签名,其重要性不亚于公钥本身.RSA有两个参数e和d,v,若将e公开则d保密.v密码能保证信息m不被非法窃取,但不能防止发信方抵赖也不能防止收信方作假.vRSA则既可以用来加
7、密信息也可以用来进行数字签名v注:数字签名是指通过每个人的唯一数字信息来确认自己的身份以防止个人抵赖或其他人作假.RSA公钥v1 RSA仅用于数字签名vAB通信(信息m不保密),执行S1:v S2:A将(m,S)同时寄给B.v B收到后作 ,将m*和m比较,若一致则确定信息是由A寄来的.若发生纠纷,则B可以拿出(m,S)作为凭证.因为S是由A的私钥得到的,所以A不能抵赖.RSA公钥v2 RSA用于加密并数字签名vAB:A掌握的是 ,B掌握的是vA计算:S1-v S2-A将S用B的公钥加密得到密文v S3-A将C寄给BvB计算:S1-对C用B的密钥解密v S2-用A的公钥再解密v小结:v(1)公钥体制的由来v(2)MH背包公钥v(3)RSA公钥