您好,欢迎访问三七文档
当前位置:首页 > 电子/通信 > 数据通信与网络 > 第5章公钥密码体制edit
11第五讲公钥密码体制&密钥管理牛秋娜2Warmup•1.•2.23•解密是加密的逆运算:Dk()=Ek-1();•解密与加密使用同样的密钥,•掌握了加密方法与密钥的人,就能解密。•这样的密码系统被称为对称密钥体系(也叫单密钥制系统)。对称密钥系统(symmetriccipher)[温旧引新]4提纲公钥密码体制概述RSA密钥分配与管理123455.1公钥密码体制概述(asymmetriccipher)•参考文献:1.卢开澄:计算机密码学清华大学出版社(1998年7月第二版)2.章照之:现代密码学基础北京邮电大学出版社(2004年4月第1版)6外语关键词公钥密钥体系:asymmetriccipher计算复杂性:computationalcomplexity素数分解:factorizationofprimenumber离散对数:DiscreteLogarithms单向陷门函数:trap-doorone-wayfunction公钥与私钥:PublicKeyandPrivateKey720世纪末,电子商务与因特网迅速发展,一方面极大地方便了人们对信息的交换和共享,另一方面,也给安全通信提出了很多新的需求,传统的单钥制密码系统对此无能为力。如何更好地解决信息安全问题,已成为刻不容缓的任务。1、对称密码体制面对的形势5.1.1公钥密码体系产生的背景:82、传统密码体制已不适应形势的发展1).功能上的缺憾传统密码学不擅长认证功能。2).使用上的难题密钥交换是对称密钥体制的难题。3).管理上的困难密钥管理问题成了通信的瓶颈。9在这种情况下,一种新的密码体制出现了。它就是公开密钥系统,也称非对称密钥体系(也叫双密钥制系统)。从理论到实践上逐步解决了对称密钥存在的问题,并从根本上提升了密码学的理念,标志着密码学进入了崭新的发展阶段。3、非对称密钥体系开始出现105.1.2公钥密码体系的几种算法一种新理论新技术的产生,一方面是因为实际问题的需求,另一方面,也是科学发展的必然结果。创新成果的产生,源于对前人成果的不断积累与改进,也离不开发明者开创性的思维。我们将通过三个典型案例的介绍,向同学们展示公钥密码体系的产生过程。111.Merkle难题(Puzzle):起初人们并没有想到去发明一个公钥密码,只不过是为了解决在普通信道中完成密钥交换问题而进行了一系列探索和努力。1974年,Merkle为解决对称单钥制密钥体系的密钥交换问题,提出了一个设想。Merkle密钥交换协议如下:12xi是0~999999之间一个任意的但又各不相同的随机数;Yi也是0~999999之间任意但又各不相同的随机数,分别作为每条消息的密钥。Alice秘密保存所有yi与xi的密钥对照表后,就把这100万条消息分别用所宣布的yi加密,发给Bob。Eyi(这条信息是xi,它的密钥是yi)明文xj(1)Alice向Bob发送100万条消息;13(2)Bob收到100万条消息,从中任选一条,然后遍历100万个密钥进行尝试,总有一个yj可将其解密,从而得知xj的值。(3)Bob以明文形式将xj发给Alice(4)Alice收到xj,即知Bob所选的是哪个yj,从而二人都有了同样的密钥yj。14Merkle安全性探讨•非法窃听者Eve,即使收到了全部往来的明文和密文,为了找到xj对应的yj,他需要对约100万条消息一一作遍历100万个密钥的尝试。•若尝试1个密钥耗时1毫秒,尝试100万个密钥耗时1000秒≈17分钟,这才解译了一条消息,100万条消息约31年才能全部试完。•而合法用户乙最多只需要17分钟。此设计方案显然不现实,但其思想是很先进的。他用的是公开的算法,通过普通(不安全)信道完成了密钥交换,其保密机制是基于计算复杂性,安全理念是基于破译的时效性,其设计理念已经进入了公钥密码的大门。14152双钥制的提出1976年11月,美国斯坦福大学电气工程系研究生W.Diffie和副教授Helman在IEEE上发表了题为“密码学新方向“的学术论文,利用离散对数复杂性实际地解决了单钥制的密钥交换问题。16(1)离散对数问题设p一个为大素数,已知整数x和b,不难求出:modxybp例如,y=36mod7=729mod7=1;然而若已知y和b,用逆运算求x却十分困难:logmodbxyp为了求上例的逆运算:x=log31mod7=?需要算出全部指数数据,查表求反函数:x123456y32645117遍历法虽然是万能的方法,却是个笨方法。设想如果p是一个六位数,计算大约100万个x与y的对照表,再快也不会少于1毫秒吧,而如果p是一个一百零六位的数,按照同样的计算速度就需要10100毫秒=3.17×1089年。实际上,上面的估计还是太保守了。随着数位的增大,加减乘除都会变得更加繁杂,对于大数的乘方运算与求模运算,计算量已经远远增大,不能再沿用计算小数的速度来估计了。18(2)计算复杂性•所谓复杂性指计算所必须的基本运算步骤数量,它决定了计算所必须的机时和占用的计算机资源。•计算复杂性理论告诉我们,随着数位N的增大,计算量从小到大的次序是:常数→对数函数logN→线性函数aN→二次函数N2→三次函数N3→多项式函数Nd→亚指数函数2logN→指数函数2N或10N。•多项式以下的运算都认为是有效算法,属于可解问题(P类),而比多项式发散更快的算法都被认为是难解问题(NP类,NPC类)。•数学上已经证明离散对数是非正常(NP)类复杂问题,计算量随着N的增大而趋于无穷。19补充:P问题、NP问题和NPC问题1P问题P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间内判定或解出。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数,则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。2NP问题(Non-deterministicPolynomial)NP是一个判定问题类,这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解。也可以说这些问题可以在非确定性多项式时间内解决,它并不要求给出一个算法来求解问题本身,而只要求给出一个确定性算法在多项式时间内验证它的解。•显然所有P类问题都属于NP类问题,但是P是否等于NP?未解。。。203NPC问题•NPC,NP完全问题,是求NP中判定问题的一个子类,是最不可能被简化为P的决定性问题的集合。•每一个NPC问题都可以在多项式时间内转化为任何一个NP问题。补充:P问题、NP问题和NPC问题21用户I①选xi为私钥②求出yi=bximodp为公钥用户J①选xj为私钥②求出yj=bxjmodp为公钥发b,p,yi发yj=(bxj)xi=kij=(bxi)xj=(3)Diffie和Helman的方案:③收到yj后,由(yj)ximodp得到会话密钥③收到yi后,由(yi)xjmodp得到会话密钥22④尽管公布了yi,yj和p,基于离散对数的困难性,任何第三者难以求出xi和xj,因此无法获得kij。Diffie和Helman虽然讨论的仍然是单钥制的密钥交换问题,但他们的观念是很超前的。他们采用的算法是公开的,他们的保密机制是基于计算复杂性,并且他们首次提出了双密钥的观点。因此这篇论文被认为是现代密码学的开篇之作。22235.1.3RSA公开密钥体系•1978年美国麻省理工大学的Ron.Rivest、Adi.Shamir和Len.Adleman提出RSA公钥密码体系。•它是第一个具有实用价值的公钥密码算法.•它是应用最广泛的公钥密码算法。•它的原理是根据数论的欧拉定理。•它的安全性是基于大数分解因数的复杂性。240、介绍--模运算•模运算:简单的说,就是求余数。•设r是a除以b的余数,a与b的关系可表示为a=r(modb),这就是模运算。•例:23=11(mod12)29(mod26)=310(mod26)=3-1(mod26)=25模运算在数论和程序设计中都有着广泛的应用,从奇偶数的判别到素数的判别,从模幂运算到最大公约数的求法,从孙子问题到凯撒密码问题,无不充斥着模运算的身影。250、介绍--同余•一般地,两个整数a和b,除以一个大于1的自然数m所得的余数相同,就称a和b对于模m同余或a和b在模m下同余,记为a≡b(modm)读作a与b(模m)同余,“≡”读作“同余于”。•如,18≡11(mod7)•可用模将全体整数分类。•如用4来将整数分类,由于余数可为0、1、2、3共四种,因而可分为四类:0,4,8,12,16……1,5,9,13,17……2,6,10,14,18……3,7,11,15,19……260、介绍--模逆元•在公钥密码体制中,往往需要求解模逆元。•求模逆元,即寻找一个x,使得a*x=1(modn)或1=(a*x)modn其中a和n是正整数,x称为a的模n逆元。也写作:a-1=xmodn例:4-1mod7=?5-1mod14=?2-1mod14=?4*2(mod7)=123没有逆元!求解模逆元问题很困难,有时有结果,有时没有结果。270、介绍--分解•因子分解就是对合数的分解。•例:18=2*32,96=25*3,110=2*5*11•较好的因子分解方法:试除法、数域筛选法、椭圆曲线法等。•但对于很大的数(1024bit以上的数)进行因子分解,所需计算时间在目前条件下是一个天文数字。•所以,已知两个大素数p和q,求其积很容易;•反之,知道n求p和q就很困难。RSA公钥密码体制这样的分解是独一无二281、RSA算法原理设p和q为两个大素数,计算n=pq在小于n的n-1个正整数中:有p-1个正整数:q,2q,3q,……,(p-1)q含因子q;有q-1个正整数:p,2p,3p,……,(q-1)p含因子p;除此之外的数(同余类)都与n互素,其数目为:(n-1)-(p-1)-(q-1)=n-p-q+1=pq-p-q+1=(p-1)(q-1);令:φ(n)=(p-1)(q-1)叫做欧拉数,代表小于n且与n互素的数(同余类)的个数。注:严谨的表述应当是同余类-----凡除以n后余数相同的整数为一个同余类)。29•Euler(欧拉)定理:•若m与n为互素的正整数,则:m(n)≡1(modn)•若k是任意整数,则mk也与n互素,于是有:mk(n)≡1(modn)mk(n)+1m(modn)(对任意0mn)•只要选择e,d,满足ed1mod(n),(叫做在模(n)运算下d和e互为模逆元)即有:ed=k(n)+1,•于是上式变为:med=m(modn)得到d、e、n后,p、q、(n)都销毁2930设m为明文,由:med=mmodn出发可以设计出一种加、解密方案:如果用memodn作为加密计算结果,就可用(me)d=mmodn来解密;如果用mdmodn作为加密计算结果,就可用(md)e=mmodn来解密。一般取(n,e)为公钥,对明文m进行加密得到密文:c=memodnd为私钥,解密算法是:m=cdmodn当然也可以用私钥加密:c'=mdmodn用公钥解密:m=c'emodn31[例1]取两个小素数p=11,q=3来演示RSA的加、解密过程。解:先求出:n=pq=33,φ(n)=(p-1)(q-1)=20;在1eφ(n)中,取e=7为公钥(与20互素即可)不难看到:7×3mod20=1d=3(为私钥);设明文m=(010)2=2,则:密文c=27=128mod33mod33=29;解密:m=293mod33=24389mod33=2;32因为e和d是在模Φ(n)运算下的互为倒数,当e与d被确定后,应当把p、q和Φ(n)都销毁,仅留下n,e和d是无法互相推导的。除非能将n分解,求出p和q,而大数的分解因数是Np类难题。因此RSA的安全得到保证。2、RSA的安全性33提纲公钥密码体制介绍公钥密码体制特点密钥分配与管理12333345.2.1公钥密码体制的特点1.从形式上讲:由对称单钥制到非对称的双钥制•加密和解密所用的算法和密钥不同,而且二者不可互
本文标题:第5章公钥密码体制edit
链接地址:https://www.777doc.com/doc-2110359 .html