第6章-公钥密码学课件

1/第六章第六章 公钥密码学公钥密码学 2公钥密码学提出的背景公钥密码学提出的背景1密密钥管理的困管理的困难性性问题 传统密密钥管理两两分管理两两分别用一用一对密密钥时则n个用个用户需需要要n(n-1)/2个密个密钥，当用，当用户量增大量增大时密密钥空空间急急剧增大。增大。2系系统的开放性的开放性问题 对称密称密码体制的密体制的密钥分分发方法要求密方法要求密钥共享各方共享各方互相信任，因此它不能解决陌生人互相信任，因此它不能解决陌生人间的密的密钥传递问题 3数字数字签名名问题 对称加密算法称加密算法难以以实现抗抵抗抵赖的安全需求。的安全需求。3密钥分发密钥分发DES提供了高效的密提供了高效的密码系系统，保障商家通，保障商家通讯不不受到商受到商务对手的攻手的攻击。用民用。用民用计算机来破解算机来破解DES加密的密文几乎是不可能的，因加密的密文几乎是不可能的，因为可能的可能的密密钥数目是十分大的。不幸的是，尽管数目是十分大的。不幸的是，尽管DES强大，尽管大，尽管DES提供了加密提供了加密标准，商家准，商家们还要解要解决另一个密决另一个密码通通讯中存在的中存在的问题，这个个问题称称作作“密密钥分分发”。很久以来很久以来“密密钥分分发”的的问题一直困一直困扰着密着密码专家。比如，二家。比如，二战时，德国高，德国高级指指挥部每个月部每个月都需要分都需要分发每日密每日密钥月刊月刊给所有的所有的“思格思格玛”机操作机操作员。而且，即使。而且，即使u型潜艇大多数型潜艇大多数时间都都远离基地，它也不得不想离基地，它也不得不想办法法获得最新的密得最新的密钥。美国政府的密美国政府的密钥是是COMSEC(通通讯安全局的安全局的缩写写)掌管和分掌管和分发的的1970年代，年代，COMSEC每天每天分分发的密的密钥数以吨数以吨计。当装。当装载着着COMSEC密密钥的船靠港的船靠港时，密，密码分分发员会到甲板上收集各会到甲板上收集各种卡片、种卡片、纸带以及以及软盘和其他一切和其他一切贮存密存密钥的的介介质。然后，把它。然后，把它们分分发给客客户。4公钥密码学的思想公钥密码学的思想公公钥密密码也称也称为非非对称密称密码。使用公。使用公钥密密码的每一个用的每一个用户都分都分别拥有两个密有两个密钥：加密密加密密钥与解密密与解密密钥，它，它们两者并不相同，并且两者并不相同，并且由由加密密加密密钥得到解密密得到解密密钥在在计算上是不可行的算上是不可行的。每一个用每一个用户的加密密的加密密钥都是公开的。都是公开的。不不对称密称密码可以可以这样来理解：任何人只需按来理解：任何人只需按一下就可以把一下就可以把锁关上，但只有有关上，但只有有钥匙的人才匙的人才能把能把锁打开。关打开。关锁(加密加密)是容易的，人人都是容易的，人人都可以做到，但开可以做到，但开锁(解密解密)只能由有只能由有钥匙的人匙的人来做了。知道关来做了。知道关锁的知的知识毫无助于开毫无助于开锁。5公钥密码算法公钥密码算法公公钥密密码算法的最大特点是采用两个相关密算法的最大特点是采用两个相关密钥将加密和解密能力分开，其中一个密将加密和解密能力分开，其中一个密钥是公开是公开的，称的，称为公开密公开密钥（简称公称公钥）用于加密；另）用于加密；另一个密一个密钥是是为用用户专用，因而是保密的，称用，因而是保密的，称为秘密密秘密密钥（简称私称私钥），用于解密。因此，公），用于解密。因此，公钥密密码体制也称体制也称为双双钥密密码体制。体制。为了把不了把不对称密称密码这个概念个概念变成可成可实行的密行的密码系系统必必须有人找到一个合适的数学函数。有人找到一个合适的数学函数。这就是陷就是陷门单向函数。向函数。单向陷向陷门函数函数单向陷向陷门函数可以被定函数可以被定义为如下函数如下函数f：（1）给出出f的定的定义域中的任意元素域中的任意元素x,f(x)的的计算是容易的；算是容易的；（2）给出出y=f(x)中的中的y要要计算算x时，若知道，若知道设计函数函数f时结合合进去的某种信息（去的某种信息（该信息称信息称为陷陷门），），则容易容易计算；若不知道算；若不知道该信息，信息，则难以以计算。算。6公钥密码学的应用公钥密码学的应用（1）机密性的机密性的实现 发送方用接收方的公送方用接收方的公钥加密消息，接收方用加密消息，接收方用自己的私自己的私钥来解密。来解密。（2）数字数字签名名 发送方用自己的私送方用自己的私钥来来签名消息，接收方通名消息，接收方通过发送方送方对应的公的公钥来来鉴别消息，并且消息，并且发送送方不能方不能对自己的自己的签名名进行否行否认。（3）密密钥分分发和和协商商 发送方和接收方基于公送方和接收方基于公钥密密码系系统容易容易实现在公开信道上的大在公开信道上的大规模的密模的密钥分分发和和协商。商。7公钥密码体制认证框图公钥密码体制认证框图 公钥密码体制认证框图公钥密码体制认证框图8公钥密码体制基于的困难问题公钥密码体制基于的困难问题已已经出出现的并且仍然具有的并且仍然具有较高安全性的公开密高安全性的公开密钥密密码体制所基于的困体制所基于的困难问题有：有：1、大整数分解、大整数分解问题；RSA公钥密码体制公钥密码体制2、ZP上的离散上的离散对数数问题；ElGamal公钥密码体制公钥密码体制3、椭圆曲曲线上的离散上的离散对数数问题；4、线性性编码的解的解码问题；5、构造非、构造非线性弱可逆有限自性弱可逆有限自动机的弱逆机的弱逆问题（基（基于有限自于有限自动机的公开密机的公开密钥密密码体制，它是我国学者体制，它是我国学者陶仁陶仁骥等提出的一种公开密等提出的一种公开密钥密密码体制）体制）9数学背景数学背景欧拉函数欧拉函数(m)：为小于或等于小于或等于m且与且与m互素的正整互素的正整数个数数个数定理定理若若p为素数，素数，则(p)(p1)。如。如p和和q为两个两个素数，素数，则(pq)(p1)(q-1)欧拉定理欧拉定理(Euler定理定理):设m2,且且(a,m)=1,则:a(m)1(modm).例例1求求132001被被15除所得的余数。除所得的余数。解：因解：因为(13,15)1，所以，所以13(15)1(mod15)。因。因为(15)(35)8，而，而200125081，所，所以以1381(mod15)，132001(138)2501313(mod15)，即被，即被15除所得的余数除所得的余数为13。10RSARSA密码算法密码算法RSA公公钥算法算法是由是由MIT的的Rivest,Shamir和和Adleman在在I978年提出来的。年提出来的。RSA方案是方案是被最广泛接受并被最广泛接受并实现的通用公开密的通用公开密钥密密码算法，算法，目前已成目前已成为公公钥密密码的国的国际标准。准。该算法的数算法的数学基学基础是初等数是初等数论中的欧拉定理，其安全性建中的欧拉定理，其安全性建立在大整数因子分解的困立在大整数因子分解的困难性之上。性之上。Rivest和和Shamir是是计算机学家，算机学家，Adleman是一位非常有能力的数学家，他是一位非常有能力的数学家，他负责挑出挑出Rivest和和Shamir的的错误，以使他，以使他们在在错误的的道路上少浪道路上少浪费时间。据英国政府声称，他据英国政府声称，他们在切在切尔特特汉姆的政府通姆的政府通讯总部很早就部很早就发明了公开密明了公开密钥密密码术。1969年年年年初初英英国国军方方请求求詹詹姆姆斯斯埃埃利利斯斯，一一位位前前英英国国政政府府的的密密码专家家，找找到到一一种种能能应付付密密钥分分发问题的的方方法法。埃埃利利斯斯的的个个性性有有点点古古怪怪。他他很很骄傲傲地地吹吹嘘嘘他他在在出出生生前前就就绕着着地地球球转了了半半圈圈他他是是在在英英国国受受孕孕的的，却却是是在在澳澳大大利利亚出出生的。生的。11RSARSA密码算法密码算法埃利斯的想法与埃利斯的想法与Shamir、Rivest和和Adleman的很相似，只是比他的很相似，只是比他们提前了好几年。然而，提前了好几年。然而，没有人知道埃利斯的工作因没有人知道埃利斯的工作因为他是英国政府他是英国政府的雇的雇员，而且要，而且要发誓保密。到誓保密。到1969年末，埃年末，埃利斯看来已利斯看来已经陷入了僵局，他已陷入了僵局，他已证明公开密明公开密钥是可能的，他也是可能的，他也发明了公开密明了公开密钥和私人密和私人密钥的的概念。概念。接下来的三年中，政府通接下来的三年中，政府通讯总部的最部的最聪明的明的头脑努力努力寻找一个能找一个能满足埃利斯要求的足埃利斯要求的单向函数，向函数，但毫无但毫无结果。果。1973年年9月，一个年月，一个年轻的数学家加入了的数学家加入了这个小个小组，克利福德克利福德科克斯。科克斯。刚刚毕业于于剑桥大学，大学，是一个是一个纯粹的数学家。粹的数学家。六个星期后，佩特森告六个星期后，佩特森告诉科克斯，之所以告科克斯，之所以告诉科克斯科克斯这个想法，是因个想法，是因为这是密是密码学中最学中最让人人兴奋的想法，而不是指望他能的想法，而不是指望他能够解决解决这个个问题。科克斯回科克斯回忆到：到：“从开始到从开始到结束，我束，我总共没花共没花半个小半个小时的的时间，我，我对自己很自己很满意，我想意，我想哦，哦，这很好，很好，别人人给我提了一个我提了一个问题，而我解决了。，而我解决了。”12RSARSA算法描述算法描述（1）密）密钥的生成的生成1.选择两个大素数两个大素数p，q，（，（p，q为互异素数，需互异素数，需要保密），要保密），2.计算算n=pq，(n)=(p1)(q1)3.选择整数整数e使使(n)，e)=1,1e(n)4.计算算d，使使d=e1mod(n),得到：公得到：公钥为e,n；私私钥为d（2）加密加密(用用e，n)：明文：明文：Mn，密文密文C=Me(modn)（3）解密解密(用用d，n)：密文密文C，明文明文M=Cd(modn)13举例举例例：例：设p=3,q=5,则n=p*q=3*5=15,(n)=(p-1)(q-1)=2*4=8取取d=3,则e=3,因因为ed1mod(n)1mod8加密：加密：1.假假设明文明文m=7,则密文密文c=me=7313(mod15)解密：解密：已知密文已知密文c=13,则可如下恢复明文：可如下恢复明文：m=cd=1337(mod15)2.假假设明文明文m=9(注意注意(9,15)不互素不互素),则密文密文c=me=939(mod15)解密：解密：已知密文已知密文c=9,则可如下恢复明文：可如下恢复明文：m=cd=939(mod15)14RSARSA的证明的证明证明：由加密明：由加密过程知程知cmemodn，所以：所以：cdmodnmedmodnm1mod(n)modnmk(n)+1modn下面分两种情况加以介下面分两种情况加以介绍。1）m与与n互素，互素，则由由Euler定理得：定理得：m(n)1modn,mk(n)1modn,mk(n)+1mmodn,则cdmodnm。2)gcd(m,n)1，m是是p的的倍倍数数或或q的的倍倍数数，设m=cp，其其中中c为一一正正整整数。此数。此时必有必有gcd(m,q)=1，否否则m也是也是q的倍数，与的倍数，与mn=pq矛盾。矛盾。由由gcd(m,q)=1及及Euler定理得定理得m(q)1modq,，所以：所以：mk(q)1modq,(mk(q)(p)1modq,mk(n)1modq因此存在一整数因此存在一整数r，使得：使得：mk(n)1+rq两两边同乘以同乘以m=cp得：得：mk(n)+1m+rcpq=rcn+m即即mk(n)+1mmodn。所以，所以，cdmodnm。15对素数的认识对素数的认识1、如果每个人都需要一个不同的素数，、如果每个人都需要一个不同的素数，难道道素数不会被用光素数不会被用光吗？当然不会，事？当然不会，事实上，上，小于小于n的素数的的素数的总数数为n/(lnn)，这个个结论称称为素素数个数定理。数个数定理。例：小于例：小于10100的素数个数的素数个数x=10100/ln10100ln10100log210100=100*log21010100/4002、是否会有两个人偶然地、是否会有两个人偶然地选择了同了同样的素数的素数的情况呢？的情况呢？这种情况不会种情况不会发生。生。从从M个素数中个素数中选出出q个素数，至少有两个素数个素数，至少有两个素数相同的概率至少相同的概率至少为1/2，此，此时q=1.17M1/23、如果有人建立了所有素数的数据如果有人建立了所有素数的数据库，难道道他不能用他不能用这个数据个数据库来破来破译公开密公开密钥算法？算法？4、产生素数困生素数困难吗？16素数的产生素数的产生现在在还没有没有产生任意的大素数的有用技生任意的大素数的有用技术，因，因此解决此解决这个个问题需要其他方法。通常在使用需要其他方法。通常在使用过程中随机程中随机选取一个需要的数量取一个需要的数量级的奇数并的奇数并检验这个数是否是素数。如果不是，个数是否是素数。如果不是，则选取后取后继的的随机数直到找到了通随机数直到找到了通过检验的素数的素数为止。止。检验素数性方面已素数性方面已经出出现了了许多方法。几乎所多方法。几乎所有的有的检验方法都是概率性的，即方法都是概率性的，即这个个检验只是只是确定一个确定一个给定的整数可能是素数。定的整数可能是素数。虽然缺乏完然缺乏完全的确定性，但是全的确定性，但是这些些检验在运行在运行时可以按照可以按照需要做到使得概率尽可能地接近需要做到使得概率尽可能地接近1。一般的，一般的，选取一个素数的取一个素数的过程如下：程如下：1 1）随机选一个奇数）随机选一个奇数n(n(例如使用伪随机数产生器例如使用伪随机数产生器)；2 2）用某种概率性算法（如）用某种概率性算法（如Miller-RabinMiller-Rabin算法）对算法）对n n进行一次素性检验，如果进行一次素性检验，如果n n没有通过检验，转到步没有通过检验，转到步骤骤1 1；3 3）重复步骤）重复步骤2 2足够多次，如果足够多次，如果n n都通过了检测，则认都通过了检测，则认为为n n为素数。为素数。17RSARSA的实现的实现大数运算大数运算.如何快速的如何快速的计算算am(modn)求求am可如下可如下进行，其中行，其中a,m是正整数：是正整数：将将m表示表示为二二进制形式制形式bkbk-1b0，即：即：m=bk2k+bk-12k-1+b12+b0因此，因此，例例如如：19=124+023+022+121+120，所以：所以：a19=(a1)2a0)2a0)2a1)2a1注意一点，即所有的乘法或乘方运算之后都注意一点，即所有的乘法或乘方运算之后都有一个模运算。有一个模运算。18如：如：56mod21=?6=(110)2d=1,i=2d=1*1=1;b2=1;d=1*5=5i=1d=5*54mod21;b1=1;d=4*5=20i=0d=4001mod21;b0=0;结束结束算法：算法：d=1;fori=kdownto0d(dd)modn;ifbi=1thend(da)modnreturndRSARSA的实现的实现19RSARSA的安全性的安全性RSA的安全性的安全性-为什么要保密什么要保密p,q,dd是私是私钥，当然要保密。，当然要保密。为什么要保密什么要保密p,q？也就是也就是说为什么什么RSA是基于大数分解是基于大数分解难题的？的？因因为知道了知道了p,q.也就是也就是说知道了知道了n的因子的因子分解，就可以算出分解，就可以算出Euler函数函数(n)=(p-1)(q-1)，也就可以利用也就可以利用辗转相除法，根据相除法，根据ed1mod(n),由由e求出求出d.因因为基于大整数分解的公开密基于大整数分解的公开密钥体制的安全体制的安全性依性依赖于于大整数（大合数分解）大整数（大合数分解）问题，所以，所以RSA的安全性完全依的安全性完全依赖于大数分解于大数分解问题。但但这只是一个推只是一个推测，目前，目前，还未能从数学未能从数学上上证明由明由c和和e计算出算出m一定需要分解一定需要分解n。然而然而，如果新方法能使密，如果新方法能使密码分析者推算出分析者推算出d，它也它也就成就成为大数分解的一个新方法。而且大数分解的一个新方法。而且这种方种方法并不比分解法并不比分解n容易。容易。20RSARSA的安全性的安全性形如形如p=2p1+1,p1也是素数的素数也是素数的素数p，通常称通常称为安安全素数，全素数，也即也即:在在RSA中，中，(p-1)/2和和(q-1)/2都都应该是素数。是素数。也即也即:*p-1和和q-1的最大公因子的最大公因子应该较小，小，*p-1和和q-1都都应有大的素因子。有大的素因子。如如23,47,83等是等是满足此特征的小素数。足此特征的小素数。安全素数是安全素数是RSA算法中算法中p,q选择必必须满足的条件。足的条件。安全素数的个数是否有限未能得到安全素数的个数是否有限未能得到证明。明。21RSARSA安全性安全性|qp|要大要大设q-p=k,则：(q+p)2-(q-p)2=4pq=4n(q+p)2=(q-p)2+4n=k2+4n如果如果k的的值小，小，则可以容易找到可以容易找到这样的的k,使得使得k2+4n是一个完全平方数，从得出是一个完全平方数，从得出q+p和和q-p的的值，联立求解可得到立求解可得到q、p。例：例：q=313,p=311,则n=97343,(q+p)2=3893764n=389372,则(q+p)2-4n4，很很简单就得到了就得到了k的的值。所以，所以，q,p的差必的差必须很大，最好差几个比很大，最好差几个比特位。特位。22RSARSA的安全性的安全性不同用不同用户不可共享模不可共享模n（共模攻共模攻击）假定用假定用户B1与与B2共享模数共享模数为n，它它们的加密密的加密密钥分分别是是e1和和e2，且（且（e1,e2）=1，某用某用户对同一同一消息消息m分分别以以e1和和e2加密得到密文加密得到密文c1与与c2。攻攻击者截者截获密文密文c1与与c2后，由于后，由于(e1,e2)=1，攻攻击者能者能够（使用（使用扩展欧几里德算法）展欧几里德算法）计算得到算得到r与与s满足足re1+se2=1，然后，攻然后，攻击者将者将进行如下行如下计算。算。23RSARSA的安全性的安全性公开公开钥e：实际中加密指数中加密指数e一般取一般取3或者或者216+1=65537，这两个数的二两个数的二进制表示中制表示中只有两个只有两个1。e=3时，加密只需要一次模乘法，加密只需要一次模乘法和一次模平方，和一次模平方，e=65537时加密只需要加密只需要16次次模平方和一次模乘法，模平方和一次模乘法，这使得加密运算非常使得加密运算非常快。快。216+1优于于3之之处在于它能在于它能够抵抗抵抗对RSA公公钥密密码的低指数攻的低指数攻击，因，因为同同样的消的消息不可能息不可能发给(216+1)个接收者。个接收者。e和和d也有些要求，如也有些要求，如e不可太小，否不可太小，否则不安全。不安全。比如比如D欲向欲向A、B、C三人送去信息三人送去信息m，A、B、C三人的三人的eA=eBeC=3，nA,nB,nC无公因数无公因数(因因为若若nA,nB有公因数，有公因数，则求求nA,nB的公因数的公因数便可将便可将nA和和nB因数分解因数分解)。则对密文：密文：c1m3modnA,c2m3modnB,c3m3modnC利用中国剩余定理可求得解：利用中国剩余定理可求得解：m3mod(nAnBnC)因因为m3(nA*nB*nC),所以只要所以只要对m3开立方开立方即可求得即可求得m。24RSARSA的安全性的安全性不同用不同用户选用的素数不能相同用的素数不能相同若若 用用 户 B1与与 B2选 用用 了了 同同 一一 个个 素素 数数 p，设n1=pq1与与n2=pq2分分别是是他他们的的模模数数，那那么么任任何何人人都都可可以以用用欧欧几几里里德德算算法法求求得得(n1,n2)=p，从从而而得得到到n1与与n2的的分分解解式式。当当然然，就就是是有有用用户选用用了了相相同同的的素素数数，遭遭到到攻攻击的的可可能能性性也也是微乎其微，但我是微乎其微，但我们应该尽量避免。尽量避免。密密钥泄漏泄漏 如果私如果私钥d被泄露，被泄露，则在模在模n的情况下重新的情况下重新计算算一一对密密钥是不是不够的，而是必的，而是必须选择一个新的公一个新的公钥n.从已知的算法可知，在私从已知的算法可知，在私钥d泄露的情况泄露的情况下，可以成功分解下，可以成功分解n的成功概率至少的成功概率至少为1/2.说明：我明：我们知道知道ed1mod(n),也即也即ed=k(n)+1.但是知道但是知道e,d并不能一下子就并不能一下子就求得求得(n)，因因为k的取的取值范范围也很大，然而利也很大，然而利用已知的算法是可以分解用已知的算法是可以分解n的，的，请看例子。看例子。25密钥泄露密钥泄露例：例：设p=9103,q=9871,则n=pq=89855713取取e=34986517,则d=82330933ed=2880472587030361ed-1=2880472587030360(n)=9870*9102=89836740(ed1)/(n)=32063414由此例可以看出，知道由此例可以看出，知道d的的值并不是可以很快就能并不是可以很快就能求出求出(n)的的值，也就不能很快分解，也就不能很快分解n,但有算法已但有算法已经证明知道明知道d是可以分解是可以分解n的，成功的概率的，成功的概率为1/2。所。所以，一旦以，一旦d泄露，就要更泄露，就要更换n.26RSARSA的安全性问题的安全性问题按照攻按照攻击者占有者占有资源的不同，攻源的不同，攻击者分者分为选择明文攻明文攻击者者CPA选择密文攻密文攻击者者CCA1适适应性性选择密文攻密文攻击者者CCA2注意到注意到RSA算法算法满足如下的性足如下的性质：(m1*m2)emodn=(m1e*m2e)modn现在在设想一个适想一个适应性密文攻性密文攻击者者获得了消息得了消息m的密的密文文c，其可以其可以选择密文密文m，并并询问密文密文(m)e*c所所对应的明文，按照上的明文，按照上边的关系，我的关系，我们知道其明文是知道其明文是(m*m)，则c对应的明文易得。的明文易得。最佳非最佳非对称填充（称填充（OAEP)27本原根本原根设n为正整数，正整数，对于于am1modn,如果如果(a,n)=1,则至少有一个整数至少有一个整数m满足足这一方程，称一方程，称满足方程的最足方程的最小正整数小正整数m为模模n下下a的的阶如果如果a的的阶m(n)，则称称a为n的的本原根本原根（本原（本原元）元）,例如模素数例如模素数7的一个本原根是的一个本原根是3整数整数a是模是模n的一个本原根，如果的一个本原根，如果对于每个与于每个与n互素互素的的x都存在一个整数都存在一个整数l，使得，使得alxmodn并非所有整数都有本原元，只有以下形式的整数才并非所有整数都有本原元，只有以下形式的整数才有本原元：有本原元：2，4，pa,2pa(a1,p为奇素数）奇素数）28ElgamalElgamal公钥密码体制公钥密码体制ElGamal密密码体制是体制是T.ElGamal于于1985年提出，是年提出，是最有名的公最有名的公钥密密码体制之一，它的安全性是基于离体制之一，它的安全性是基于离散散对数数问题.设p至少是至少是150位的十位的十进制素数，制素数，p-1有大素因子。有大素因子。Zp为有限域，若有限域，若g为Zp中的本原元，有中的本原元，有Zp*若取若取 Zp*=Zp0，如何算得唯一得整数如何算得唯一得整数a，(要求，要求，0ap-2)，满足足ga=(modp)称称为离散离散对数数问题，将，将a记为a=logg一般来一般来说，求解，求解a在在计算上是算上是难处理的。理的。29算法描述算法描述1密密钥的生成的生成选取大素数取大素数p，g Zp*是一个本原元（生成元）是一个本原元（生成元）。p、g作作为系系统参数所有用参数所有用户共享。系共享。系统中中每个用每个用户U都随机挑都随机挑选整数整数x，2xp2，并并计算：算：y=g x(modp)，(p,g,y)作作为用用户U的公开密的公开密钥，而，而x作作为用用户U的秘密密的秘密密钥2.加密：加密：(1)用用户A先把明文先把明文M编码为一个在一个在0到到(p1)之之间的整数的整数m；(2)用用户A挑挑选一个一个秘密随机数秘密随机数r(2rp2)，并并计算：算：c1g r(modp)；c2 m yr(modp)，其中其中y是用是用户B的公开密的公开密钥；用；用户A把二元把二元组(c1,c2)作作为其密文其密文传送送给用用户B。30算法描述算法描述3.解密解密用用户B接收到密文二元接收到密文二元组(c1,c2)后，做解密后，做解密计算：算：算法的正确性容易算法的正确性容易验证，略。，略。ElGamal算法特点算法特点：(1)“非确定性的非确定性的”。由于密文依。由于密文依赖于于执行加密行加密过程的用程的用户A所所选择的的随机数随机数r，所以，所以，加加密相同的明文可能会密相同的明文可能会产生不同的密文。生不同的密文。(2)密文空密文空间大于明文空大于明文空间。明文空。明文空间为Zp*，而密文空而密文空间为Zp*Zp*对于每个明文，于每个明文，其密文由其密文由2个个Zp*上的元素上的元素组成。成。31ElgamalElgamal算法的安全性算法的安全性同同RSA的的处理一理一样，假，假设适适应性性选择密文的密文的攻攻击者者获得了消息得了消息m的密文的密文(c1,c2),攻攻击者者随机随机选择r和消息和消息m，并并计算：算：c1=(c1*g r)modpc2=(c2*yr*m)modp攻攻击者将构造的新密文者将构造的新密文(c1,c2)送解密机，送解密机，则返回明文返回明文(m*m)modp从而容易得到密文从而容易得到密文c的明文的明文m两个基本算法两个基本算法(basicRSA或或basicElgamal)不安全，因不安全，因为存在存在这种同种同态的性的性质。32EllipticCurveCryptography由由HealKablitz和和VictorMiller在在1985年分年分别提出提出并在近年开始得到重并在近年开始得到重视。ECC的安全性基于的安全性基于椭圆曲曲线离散离散对数数问题的的难解性。同基于有限域上的离散解性。同基于有限域上的离散对数数问题的公的公钥密密码体制相比，体制相比，椭圆曲曲线密密码体制主要有体制主要有以下两个方面的以下两个方面的优点。点。1)密密钥长度小度小到目前到目前为止，止，ECC没有没有亚指数攻指数攻击，所以，在，所以，在实现相相同的安全同的安全级别的条件下，的条件下，ECC所需要的密所需要的密钥长度度远小小于基于有限域上的离散于基于有限域上的离散对数数问题的公的公钥密密码体制的密体制的密钥长度度2)算法性能好算法性能好由于密由于密钥长度小很多，因此减少了度小很多，因此减少了处理开理开销，具有存，具有存储效率、效率、计算效率和通信算效率和通信带宽的的节约等方面的等方面的优势33作业作业P2019.2（e）、）、9.8P2039.16