非对称密码体制ppt课件

27.04.2020,Page:1,非对称密码体制,杨秋伟湖南大学计算机与通信学院,27.04.2020,Page:2,非对称密码体制组成,非对称密码体制的基本概念Diffie-Hellman密码体制背包密码体制RSA密码体制Elgamal密码体制椭圆曲线密码体制,27.04.2020,Page:3,非对称密码基本概念：对称密码面临的困难,密钥管理：若N个人相互保密通信，每人必须拥有(N-1)个私钥，N很大时，需要保存的私钥很多。如何解决？可信中心分发：共需要发N*(N-1)/2个私钥：例如N=1000时,999*1000/2=499500双方事先约定：用户之间自己秘密会面(第一次远距离通信如何办？),27.04.2020,Page:4,非对称密码基本概念：非对称密码的提出,对称密码的局限性密钥管理的困难性问题陌生人间的保密通信问题数字签名问题非对称密码(1976年由W.Diffie和M.Hellman提出)与对称密码的几点区别：双钥双钥密码、公钥密码基于数学函数，而非替换和换位解决了对称密码的诸多局限性,27.04.2020,Page:5,非对称密码基本概念：非对称密码体制,密钥(PK,SK)PK：俗称公钥(PublicKey)，通常公钥是公开的，可以被任何实体通过有效渠道获取；SK：俗称私钥(SecretKey)，通常私钥是保密的，不能被任何实体通过非法渠道获取；,27.04.2020,Page:6,非对称密码基本概念：设计要求,参与方B容易通过计算产生一对密钥；在知道公开密钥和待加密消息的情况下，发送方A容易产生密文；接受方B使用私有密钥容易通过计算解密所得密文，以便恢复原来的消息；敌手在知道公开密钥的情况下，确定私有密钥计算上不可行；敌手在知道公开密钥和密文的情况下，恢复消息计算上不可行；两个密钥中的任何一个可以用来加密，对应的另一个用来解密。,27.04.2020,Page:7,非对称密码基本概念：非对称密码的算法组成,密钥生成KG()根据输入的安全参数，输出公钥和私钥对(PK,SK)加密E()根据输入的公钥和消息，输出密文。解密D()根据输入的解密私钥和密文，算法输出消息或输出表示密文不合法的特殊符号“?”,27.04.2020,Page:8,非对称密码基本概念：非对称密码的原理,非对称密码体制：加密密钥与解密密钥不同非对称密码、认证系统的的安全性主要取决于构造非对称算法所依赖的数学问题。要求加密函数具有单向性，即求逆的困难性。因此，设计双钥体制的关键是先要寻求一个合适的单向函数。,27.04.2020,Page:9,非对称密码基本概念：单向函数,令函数f是集A到集B的映射，以f：AB表示。若对任意x1x2，x1,x2A，有f(x1)f(x2)，则称f为单射，或1-1映射，或可逆的函数。f为可逆的充要条件是：存在函数g:BA，使对任意xA有gf(x)=x。一个可逆函数f：AB，若它满足：对所有xA，易于计算f(x)；对“几乎所有xA”由f(x)求x“极为困难”，以至于实际上不可能做到，则称f为一单向(One-way)函数。定义中的“极为困难”是对现有的计算资源和算法而言。,27.04.2020,Page:10,非对称密码基本概念：单向函数,例一：令f是在有限域GF(p)中的指数函数，其中p是大素数，即y=f(x)=ax。式中，xGF(p)，x为满足0xp1的整数，其逆运算是GF(p)中定义的对数运算，即x=logay(0xp1)由x求y：即使当p很大，也不难实现。为方便计算令a=2。例如p=2100时，需作100乘法。利用高速计算机由x计算ax可在0.1毫秒内完成。从ax计算x：当p=2100时，以平均速度的计算机进行计算需时约1010.7秒(1年=107.5秒，故约为1600年！其中假定存储量的要求能够满足)。,27.04.2020,Page:11,非对称密码基本概念：单向陷门函数,满足下列条件的函数f称为单向陷门函数：给定x，计算y=f(x)是容易的；给定y，计算x使y=f(x)是困难的；存在z，已知z时,对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的。两个难题陷门函数其实就不是单向函数，因为单向函数是在任何条件下求逆都是困难的；陷门可能不止一个，通过试验,一个陷门就可容易地找到逆。如果陷门信息的保密性不强，求逆也就不难。,27.04.2020,Page:12,非对称密码体制组成,非对称密码体制的基本概念Diffie-Hellman密码体制背包密码体制RSA密码体制Elgamal密码体制椭圆曲线密码体制,27.04.2020,Page:13,非对称密码体制：Diffie-Hellman密码体制,Diffie和Hellman在密码学新方向一文中给出了非对称密码算法的思想它不是真正意义上的非对称密码实例，仅仅是一个单向函数；算法的目的是使得两个用户安全地交换一个会话密钥。密钥交换(秘密共享)发送方和接受方基于公钥密码体制交换会话密钥；会话密钥采用对称加密体制加密需要保密传输的消息。,27.04.2020,Page:14,Diffie-Hellman密码体制：密钥交换系统工作原理,发送者,接收者,接收者的公钥加密,接收者的私钥解密,加密,解密,会话密钥交换阶段,保密信息交换阶段,27.04.2020,Page:15,Diffie-Hellman密码体制：本原元和离散对数,本原元：对于一个素数q如果数值amodq,a2modq,aq-1modq是各不相同的整数；并且以某种排列方式组成了从1到q-1的所有整数；则称整数a是素数q的一个本原元。离散对数：对于一个整数b和素数q的一个本原元a，可以找到一个唯一的指数i，使得baimodq(0iq-1)成立，则指数i称为b的以a为基数的模q的离散对数。,27.04.2020,Page:16,Diffie-Hellman密码体制：算法,用户A和用户B之间安全交换会话密钥，已知一个素数q和一个整数a，其中整数a是素数q的一个本原元。用户A随机选择一个数xAq，计算yAaxAmodq；用户B随机选择一个数xBq，计算yBaxBmodq；用户A和用户B分别公开yA、yB；用户A计算k1(yB)xAmodq，用户B计算k2(yA)xBmodq，k即为共享的会话密钥。k1(yB)xAmodq(a)xAxBmodq(axA)xBmodq(yA)xBmodqk2,27.04.2020,Page:17,Diffie-Hellman密码体制：实例,例一：令p=43，3作为mod43的本原根。令Alice和Bob知道公共参数(p,a)=(43,3)，Alice和Bob试图协商一个会话密钥。Alice随机选取她的秘密指数8，计算3825mod43，并将结果发送给Bob；Bob随机选取她的秘密指数37，计算33720mod43，并将结果发送给Alice；Alice和Bob分别计算会话密钥92082537mod43。,27.04.2020,Page:18,Diffie-Hellman密码体制：算法安全性,Deffie-Hellman密钥交换算法安全性源于在有限域上计算离散对数，它比计算指数更为困难。攻击者只知道a、q、yA、yB，除非计算离散对数，恢复xA、xB，否则无济于事。a和q的选取(q-1)/2应该是一个素数，并且q应该足够大：系统的安全性取决于与q同样长度的数的因子分解的难度；可以选择任何模n的本原元a，通常选择最小的a(一般是一位数)。,27.04.2020,Page:19,Diffie-Hellman密码体制：中间人攻击,Alice,Bob,1,2,27.04.2020,Page:20,Diffie-Hellman密码体制：中间人攻击,用户Alice和用户Bob之间安全交换会话密钥，已知一个素数q和一个整数a，其中整数a是素数q的一个本原元。1Alice随机选择一个数xAq，计算yAaxAmodq，发送给Malice(Bob)；1Malice随机选择一个数mq，计算yMammodq，发送给Bob；2Bob随机选择一个数xBq，计算yBaxBmodq，发送给Malice(Alice)；2Malice将yMammodq发送给Alice。,DH密钥交换协议不支持认证功能，需要额外的身份认证机制来保证安全性。,27.04.2020,Page:21,非对称密码体制组成,非对称密码体制的基本概念Diffie-Hellman密码体制背包密码体制RSA密码体制Elgamal密码体制椭圆曲线密码体制,27.04.2020,Page:22,非对称密码体制：背包密码体制,RalphMerkle和MartinHellman开发了第一个非对称密码算法背包算法。(背包算法只能用于加密)背包问题的描述：给定一堆物品，每个重量不同，能否将这些物品中的几件放入一个背包中，使之等于一个给定的重量？给定一系列值m1,m2,mn和一个和s，计算bi使之满足s=b1m1+b2m2+bimi背包密码体制的安全性基于背包难题，它证明了如何将一个NP完全问题应用到非对称密码学，后来被证明是不安全的。,27.04.2020,Page:23,背包密码体制：背包算法的基本思想,背包算法的思想是将消息编码为背包问题的解明文分组长度等于堆中物品的个数，且明文位与bi的值相对应；密文是计算得到的和值。,27.04.2020,Page:24,背包密码体制：超递增背包序列,背包密码体制的奥秘：超递增背包序列超递增序列：它的每一项都大于它之前所有项之和；例一：1,3,6,13,27,52超递增背包问题的解计算其总重量并与序列中最大的数比较如果总重量小于这个数，则它不在背包中；反之，则它在背包中，背包重量减去这个数。考查数列下一个最大的数，重复直到结束如果总重量减为零，那么有一个解；反之无解。,27.04.2020,Page:25,背包密码体制：背包问题易与难之间的转化,问题的转化超递增背包问题的解很容易找到；非超递增背包问题是困难问题，没有快速解法。超递增背包问题向非超递增背包问题的转化取一个超递增序列，比如2,3,6,13,27,52；分别选取n和m，用n去乘所有的项，m作为模数进行模运。比如n=31,m=105,231mod105625231mod10537得到一个非超递增序列，比如62,93,81,88,102,37；超递增序列作为私人密钥，得到的非超递增序列作为公钥。,27.04.2020,Page:26,背包密码体制：加密,加密首先将明文分成长度等于背包序列中项数的多个分组；用1表示存在，用0表示该项不在其中，计算背包的总重量；所有分组重复第二步的操作。例一：明文“011000110101101110”，背包序列62,93,81,88,102,37明文分组=011000110101101110计算背包总重量，第一组011000对应93+81=174，其它类似密文=174，280，333,27.04.2020,Page:27,背包密码体制：解密,解密解密者知道私人密钥“超递增背包序列”首先计算出n-1以满足n-1nmodm1；用n-1模m乘密文值的每项；用私人背包对它进行划分可获得明文。例一：密文174，280，333，私人密钥2,3,6,13,27,52n=31，m=105，则n-1=61；所有密文值乘61模105，例17461mod10593+6对应011000；恢复出的明文为“011000110101101110”。,27.04.2020,Page:28,背包密码体制：实现及安全性,背包密码方案实现的限制超递增序列至少要包含250项，每一项的值应在200400位之间；模数一般在100200位之间。背包密码方案的安全性采用穷举法攻击：一台每秒运行百万次的计算机，要1046年，即使100万台计算机并行处理，太阳毁灭之前也解决不了这个问题；Shamir和Zippel发现了背包问题易与难之间转化的缺陷，可以从非超递增背包序列中重构出超递增背包序列。,27.04.2020,Page:29,非对称密码体制组成,非对称密码体制的基本概念Diffie-Hellman密码体制背包密码体制RSA密码体制Elgamal密码体制椭圆曲线密码体制,27.04.2020,Page:30,非对称密码体制：RSA密码体制,由Rivest、Shamir、Adleman三位密码学家1978年发明的RSA算法是一种用数论构造的，迄今为止最为成熟完善的一个可逆的公钥密码体制，问题难度基于大整数分解。RSA体制的几个组成部分密钥生成加密解密,27.04.2020,Page:31,RSA密码体制：密钥生成,首先选取两个大素数p和q，计算n=pq；随机选取加密密钥e，使e和(p-1)(q-1)互素；用扩展欧几里德算法计算解密密钥d，以满足：ed=1mod(p-1)(q-1)，即d=e-1mod(p-1)(q-1)；公开钥为(e,n)，秘密钥为(d,n)。,27.04.2020,Page:32,RSA密码体制：加/解密,加密过程加密的数学变换：C=Memodn解密过程解密的数学变换：M=Cdmodn正确性验证Cdmodn=(Me)dmodn=Medmodn=Mk(p-1)(q-1)+1modn=MMk(p-1)(q-1)modn(欧拉定理？),27.04.2020,Page:33,RSA密码体制：加/解密,M.Mk(p-1)(q-1)modn(欧拉定理？)M与n互素，则由欧拉定理Mk(p-1)(q-1)modn1modn得MMk(p-1)(q-1)modnMmodngcd(M,n)1，由于n=pq，且p和q都是素数，则M是p或q的倍数。设M=tp，其中t为一正整数，而gcd(M,q)=1(mn)。由欧拉定理Mq-1modq1modq得1)Mk(p-1)(q-1)modq1modqMk(p-1)(q-1)=1+rq(两边同时乘以M=tp)2)MMk(p-1)(q-1)=(1+rq)tp=tp+rtpq=M+rtn3)MMk(p-1)(q-1)modn(M+rtn)modnMmodn,27.04.2020,Page:34,RSA密码体制：举例,选p=7，q=17。求n=pq=119，。取e=5，满足1=1)if(m%2=0)*(link+*z)=0;else*(link+*z)=1;(*z)+;*(link+*z)=1;,快速幂计算intPowerCompute(inta,int*link,intz,intn)inty=1;for(;z0;z-)if(*(link+z)!=0)y=(y*a)%n)*(y*a)%n)%n;elsey=(y*y)%n;if(*link!=0)y=(y*a)%n;returny;,27.04.2020,Page:37,RSA密码体制：RSA密码的安全性,RSA的安全性完全依赖于分解大数的难度从数学上从未证明过需要分解n才能从c和e中计算出m；可通过猜测(p-1)(q-1)的值来攻击RSA，但这种攻击没有分解n容易；可尝试每一种可能的d，直到获得正确的一个，这种穷举攻击还没有试图分解n更有效；129位十进制数字的模数是能分解的临界数，n应该大于这个数。,27.04.2020,Page:38,RSA密码体制：对RSA的选择密文攻击,例一(对协议的攻击)：Eve在Alice的通信过程中进行窃听，设法成功选取了一个用她的公开密钥加密的密文c。Eve想读出信息m，m=cd。Eve选取一个随机数r，满足r小于n。她得到Alice的公钥e：xremodnyxcmodntr-1modnEve让Alice用她的私人密钥对y签名，以便解密y：uydmodnEve计算：tumodnr-1ydmodnr-1xdcdmodncdmodnm,27.04.2020,Page:39,RSA密码体制：对RSA的选择密文攻击,例二(对协议的攻击)：Trend是一个公开的计算机公证人，Mallory想让Trend对一个本来不愿意签名的消息签名，例如m1。Mallory计算(如果可能的话)：m1m2m3modnEve让Alice用她的私人密钥对m2和m3分别签名；Eve计算：m1d(m2dmodn)(m3dmodn),利用的缺陷：指数运算保持了输入的乘法结构(xm)dmodn=xdmdmodn,27.04.2020,Page:40,RSA密码体制：对RSA的公共模数攻击,不同的使用者采用相同模数n，即使e和d不同，假如两个公钥互素，则无需任何的解密技术就可以恢复明文。设m位明文，两个公钥为e1和e2，模数为n，两个密文为：c1me1modnc2me2modn由于e1和e2互素，根据扩展欧几里德算法找出r和s，满足：re1+se2=1假定r是负数(r或s中有一个必须是负数)，用欧几里德算法可计算c1-1：(c1-1)-rc2s=mmodn,27.04.2020,Page:41,RSA密码体制：对RSA的低加/解密指数攻击,对RSA的低加密指数攻击选取较低的e值可以加快计算速度；采用不同的RSA公钥及相同的e值，对e(e+1)/2个线形相关的消息加密，则存在一种能攻击该系统的方法阻止该攻击的方法是用独立随机值填充消息，使得m和n大小一样。对RSA的低解密指数攻击如果d达到n的1/4大小，且e比n小，那么存在一种攻击能够恢复d；假如e和d随机选择，该攻击很少发生；假如e的值很小，则d的值会比较大，该攻击不可能发生。,消息比较短，则md和ce都小于n,保证memodnme,27.04.2020,Page:42,RSA密码体制：实现RSA密码方案的限制,根据前面成功的攻击，JadithMoore列出了使用RSA的一些限制知道了对于一个给定模数的一个加/解密密钥指数对，攻击者就能分解这个模数；知道了对于一个给定模数的一个加/解密密钥指数对，攻击者无需分解n就可以计算出别的加/解密对；在通信网络中，利用RSA的协议不应该使用公共模数；消息应用随机数填充以避免对加密指数的攻击；解密指数应该大。,27.04.2020,Page:43,非对称密码体制组成,非对称密码体制的基本概念Diffie-Hellman密码体制背包密码体制RSA密码体制Elgamal密码体制椭圆曲线密码体制,27.04.2020,Page:44,非对称密码体制：ElGamal密码体制,Elgamal是一种可应用于加密和签名的密码算法安全性依赖于有限域上离散对数的难度,27.04.2020,Page:45,ElGamal密码体制：工作原理,选择一个素数p，两个随机数g和x(gp,xp)，计算ygxmodp。公开密钥是y、g和p，私钥是x。设待加密消息为m：加密首先选择随机数r，只要r与p-1互素；计算：agrmodp和byrmmodp，a和b作为密文对，密文的长度是明文的两倍；解密计算：mb/axmodp；验证：axgrxmodp，b/axyrm/axgxrm/gxrmmodp。,27.04.2020,Page:46,ElGamal密码体制：实例,密钥生成选取素数p=2357及Z*2357的生成元2，选取私钥x=1751并计算gxmodp21751mod23571185公钥是p=2357,g=2,gx=1185。加密为加密信息m=2053，选一个随机整数k=1520，并计算a21520mod23571430，b118515202053mod2357697。解密a-x1430-1751mod2357872，mb/axmodp6978722053,27.04.2020,Page:47,非对称密码体制组成,非对称密码体制的基本概念Diffie-Hellman密码体制背包密码体制RSA密码体制Elgamal密码体制椭圆曲线密码体制,27.04.2020,Page:48,非对称密码体制：椭圆曲线密码体制(ECC),NealKoblitz和VictorMiller在1985年分别提出了椭圆曲线密码体制(ECC)，它是迄今为止被实践证明安全有效的三类公钥密码体制之一。ECC的安全性基于椭圆曲线离散对数问题的难解性比整数分解问题和模p离散对数问题难解；密钥长度大大减少，256比特的ECC密钥达到128比特对称密钥的安全水平；对比RSA，用少得多的比特大小取得同等强度的安全性。1998年被ISO/IEC定为数字签名标准，2000年2月定为IEEE标准。,27.04.2020,Page:49,非对称密码体制：椭圆曲线密码体制(ECC),椭圆曲线公钥系统是代替RSA的强有力的竞争者有以下的优点安全性能更高：如160位ECC与1024位RSA、DSA有相同的安全强度；计算量小、处理速度快：在私钥的处理速度上(解密和签名)，ECC远比RSA、DSA快得多；存储空间占用小：ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多，所以占用的存储空间小得多；应用前景：带宽要求低使得ECC具有广泛得应用前景(比如研究者已把它作为下一代SET协议中缺省的公钥密码算法)。,27.04.2020,Page:50,椭圆曲线密码体制：椭圆曲线,实数域上的椭圆曲线对于固定的实数a,b，满足方程：y2=x3+ax+b的所有点的集合，外加一个零点和无穷远点O，其中x和y是实数域上取值。有限域GF(p)上的椭圆曲线对于固定的a,b，满足方程：y2x3+ax+b(modp)的所有点的集合，外加一个零点和无穷远点O，其中a,b,x,y是有限域GF(p)上取值，p是素数。有限域GF(2m)上的椭圆曲线对于固定的实数a,b，满足方程：y2+xy=x3+ax2+b的所有点的集合，外加一个零点和无穷远点O，其中a,b,x,y是有限域GF(2m)上取值。域GF(2m)上的元素是m位的串。,27.04.2020,Page:51,椭圆曲线密码体制：运算规则,只要非负整数a和b满足：4a3+27b2(modp)0，那么Ep(a,b)表示模p的椭圆群，这个群中的元素和一个称为无穷远点的O共同组成椭圆群Abel群(单位元、逆元、交换律、结合律)。两个互不为逆的点P(x1,y1)和Q(x2,y2)的加法规则P(x1,y1)+Q(x2,y2)=S(x3,y3)其中x3=2-x1-x2,y3=(x1-x3)-y1,=(y2-y1)/(x2-x1)对任意点P(x1,y1)的倍点规则P(x1,y1)+P(x1,y1)=2P(x1,y1)=Q(x3,y3)其中，x3=2-2x1,y3=(x1-x3)-y1,=(3x12+a)/2y1,27.04.2020,Page:52,椭圆曲线密码体制：关于运算的两个定义,定义一：mP=P+P+P(m个P)定义二：P是椭圆曲线E上的一个点，若存在最小的正整数n，使得nP=O，其中O是无穷远点，则称n是P的阶数。,27.04.2020,Page:53,椭圆曲线密码体制：系统初始化,系统的建立选取一个有限域GF(p)和定义在该域上的椭圆曲线E(a,b)和E(a,b)上的一个阶为n的点P(xp,yp)；GF(p)、a、b、P(xp,yp)和n都是公开信息。密钥的生成在区间1,n-1中随机选取一个整数d；计算Q=dP；实体的公开密钥是Q，私钥是证书d。,27.04.2020,Page:54,椭圆曲线密码体制：加密,Bob试图将消息M发送给Alice时，执行下列操作查找Alice的公钥Q；将消息M表示成一个域元素mGF(p)；在区间1,n-1中随机选取一个整数k；计算点(x1,y1)=kP；计算点(x2,y2)=kQ，如果x2=0，则返回到第三步；计算c=mx2；传送加密数据(x1,y1,c)给Alice。,数据类型的转换,27.04.202