密码学6-非对称密码体制优秀PPT.ppt

《密码学6-非对称密码体制优秀PPT.ppt》由会员分享，可在线阅读，更多相关《密码学6-非对称密码体制优秀PPT.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章 非对称密码体制非对称密码体制信息平安技术信息平安技术 6.1 概述概述6.1.1 对称密码体制的缺陷对称密码体制的缺陷密钥的平安传递比较困难密钥的平安传递比较困难n个用户多点通信所需密钥数为个用户多点通信所需密钥数为n(n-1)/2个个难以供应对主动攻击的抗击难以供应对主动攻击的抗击6.1.2 公钥（非对称）密码体制的基本思想公钥（非对称）密码体制的基本思想 Whitfield Diffie和和Martin Hellman在在1976年首先提出：用公开的密钥（公钥）年首先提出：用公开的密钥（公钥）加密，用与之对应的不公开的密钥（私钥）加密，用与之对应的不公开的密钥（私钥）解密。解

2、密。公钥密码体制提出的标记性文献公钥密码体制提出的标记性文献密码学的新方向：密码学的新方向：W.Diffie and M.E.Hellman,New Directions in Cryptography,IEEE Transaction on Information Theory,V.IT-22.No.6,Nov 1976,PP.644-654例：程嘉要传送密信给雷蕾，用雷蕾的公钥对明文例：程嘉要传送密信给雷蕾，用雷蕾的公钥对明文进行加密，然后通过公共信道将密文传送给雷蕾，进行加密，然后通过公共信道将密文传送给雷蕾，雷蕾用的与自己的公钥对应的私钥（只有雷蕾自雷蕾用的与自己的公钥对应的私钥（只有

3、雷蕾自己知道）解密得到明文。康威企图知道密信内容，己知道）解密得到明文。康威企图知道密信内容，截获到密文，虽然他也知道加密所用的公钥，但截获到密文，虽然他也知道加密所用的公钥，但他无法通过公钥倒推出相应的私钥，当然就不行他无法通过公钥倒推出相应的私钥，当然就不行能解密出明文。能解密出明文。6.1.2 对公钥密码体制的要求对公钥密码体制的要求（1）参与方）参与方B简洁通过计算产生一对密钥（公开简洁通过计算产生一对密钥（公开密钥密钥KUb和私有密钥和私有密钥KRb）。）。（2）在知道公钥和待加密报文）在知道公钥和待加密报文M的状况下，对于的状况下，对于发送方发送方A，很简洁通过计算产生对应的密文：

4、，很简洁通过计算产生对应的密文：C=EKUb(M)（3）接收方）接收方B运用私钥简洁通过计算解密所收到运用私钥简洁通过计算解密所收到的密文的密文C以便复原原来的明文：以便复原原来的明文：M=DKRb(C)=DKRb(EKUb(M)（4）攻击者即使知道公钥）攻击者即使知道公钥KUb，要确定其对应的，要确定其对应的私钥私钥KRb在计算上是不行行的。在计算上是不行行的。（5）攻击者即使知道公钥）攻击者即使知道公钥KUb和密文和密文C，要想复，要想复原原来的明文原原来的明文M在计算上也是不行行的。在计算上也是不行行的。（6）加密和解密函数可以以两个次序中的任何一）加密和解密函数可以以两个次序中的任何一

5、个来运用个来运用:M=DKRb(EKUb(M)（机密性）（机密性）或或M=EKUb(DKRb(M)（数字签名）（数字签名）6.1.3 单向陷门函数单向陷门函数公钥密码体制必需设计一个满足下列条件的函数公钥密码体制必需设计一个满足下列条件的函数f：正向易算性正向易算性由消息由消息x和密钥和密钥pk 简洁计算简洁计算y=fpk(x)反向不行算性反向不行算性在不知道密钥在不知道密钥sk的状况下，由随的状况下，由随意的意的y倒过来计算倒过来计算x=f-1sk(y)都是不行行的都是不行行的陷门依靠性陷门依靠性假如给定另一密钥假如给定另一密钥sk，则，则f-1(y)是可是可以计算的，以计算的，sk 与与p

6、k配对，相当于陷门。配对，相当于陷门。满足满足1、2的函数称为单向函数的函数称为单向函数 满足满足1、2、3的函数被称为带陷门的单向函数的函数被称为带陷门的单向函数 6.1.4 公钥密码体制的特点公钥密码体制的特点无需密钥的平安传递无需密钥的平安传递n个用户仅需个用户仅需n个个“公钥公钥-私钥私钥”对对支持对主动攻击的抗击支持对主动攻击的抗击平安性基于带陷门的单向函数平安性基于带陷门的单向函数加密、解密速度比加密、解密速度比DES、AES等分组密码体等分组密码体制慢制慢可用于对称密钥的交换可用于对称密钥的交换6.2 数论背景数论背景欧拉函数与欧拉定理欧拉函数与欧拉定理欧拉数欧拉数设正整数设正整

7、数n，则欧拉数，则欧拉数(n)定义为小于定义为小于n且与且与n互互素的正整数的个数（特殊地，素的正整数的个数（特殊地，(1)=1）。）。例如：例如：(6)=2(小于小于6且与且与6互素的是互素的是1和和5);(7)=6(1,2,3,4,5,6);(11)=10(110)素数的欧拉数素数的欧拉数对于素数对于素数p，其欧拉数，其欧拉数(p)=p-1(1p-1)欧拉数的初等性质欧拉数的初等性质 当当p、q都是素数时，都是素数时，(pq)=(p)(q)=(p-1)(q-1)例：例：(15)=(3)(5)=2*4=8(1,2,4,7,8,11,13,14)4.当当e与与m互素，则存在正整数互素，则存在正

8、整数d，使得使得 ed=1 (mod m)称称d是是e关于模关于模m的乘法逆元（简称的乘法逆元（简称“模模乘逆元乘逆元”或或“模逆元模逆元”），记作），记作e-1 例如：设例如：设m=13，则则5*8=40=3*13+1=1(mod 13)故故 5-1=85.欧拉定理欧拉定理 假设假设m、n互素，则互素，则m(n)=1 (mod n)例如：设例如：设m=13，n=7，则则136=4826809=689544*7+1=1(mod 7)6.费马小定理费马小定理欧拉定理的推论欧拉定理的推论 设设p与与m互素，且互素，且p是素数，则是素数，则 m p-1=1 (mod p)（因为（因为(p)=p-1）

9、7.基础定理基础定理RSA的理论基础的理论基础 设设n是两个不同的素数是两个不同的素数p、q之积，之积，x是小于是小于n的非负整数，的非负整数，k是非负整数，是非负整数，则有：则有：x k(n)+1=x (mod n)证明：若证明：若x不是素数不是素数p的倍数，则的倍数，则p与与x互素，由费马小互素，由费马小定理可得：定理可得：x p-1=1 (mod p)，于是由前述各式可得：，于是由前述各式可得：x k(n)=x k(pq)=x k(p)(q)=x k(p-1)(q-1)=(xp-1)k(q-1)=1(mod p)，故，故x k(n)+1=x (mod p)若若x是是p的倍数，则的倍数，则

10、 x=0 (mod p)，于是也有：，于是也有：x k(n)+1=0=x (mod p)故存在非负整数故存在非负整数i，使得，使得x k(n)+1=ip+x (mod p)，同理存在非负整数同理存在非负整数j，使得，使得x k(n)+1=jq+x (mod q)，从而可得从而可得ip=jq又由于又由于p、q互素，故互素，故q i，设整商为，设整商为t，即，即i=tq，于是：，于是：x k(n)+1=ip+x=tqp+x=tn+x=x(mod n)即最终证得：即最终证得：x k(n)+1=x (mod n)6.3 RSA算法算法6.3.1 概述概述独创人独创人RSA(Ron Rivest,Adi

11、Shamir 和和 Leonard Adleman)1977年在麻省理工学院开发年在麻省理工学院开发1978年发表年发表是最典型的公钥密码体制是最典型的公钥密码体制算法基于单向陷门函数的原理算法基于单向陷门函数的原理以模幂运算为基本运算以模幂运算为基本运算平安性基于大数因子分解的困难性（将一个充平安性基于大数因子分解的困难性（将一个充分大的正整数分解成两个素数之积几乎是不分大的正整数分解成两个素数之积几乎是不行能的）行能的）数学基础是著名的欧拉数学基础是著名的欧拉(Euler)数论数论6.3.2 RSA密码体制的创建密码体制的创建1)选择两个充分大的不同的素数选择两个充分大的不同的素数p和和q

12、2)计算积计算积n=pq及其欧拉数及其欧拉数(n)=(p-1)(q-1)3)选择一个介于选择一个介于1到到(n)之间且与之间且与(n)互素的正整互素的正整数数e 即即1e(n)且且GCD(e,(n)=14)求出求出d=e-1 (mod(n)即即e d=1 (mod(n)5)对明文空间对明文空间0n-1中的数中的数x，例：例：P115【例例6-2】以以为公钥加密：为公钥加密：y=E(x)=xe (mod n)以以 为私钥解密：为私钥解密：x=D(y)=yd (mod n)解密还原性的证明：解密还原性的证明：由于由于ed=1(mod(n)，故存在非负整数故存在非负整数k，使得：使得：ed=k(n)

13、+1，于是由基础定理可得：于是由基础定理可得：D(E(x)=(xe)d=xed=x k(n)+1=x (mod n)注注1：p,q从理论上讲也是私钥的组成部从理论上讲也是私钥的组成部分，但因在解密过程中不用，故在确定分，但因在解密过程中不用，故在确定e,d之后应予以销毁之后应予以销毁注注2:加密前明文加密前明文M需表示为若干需表示为若干0n-1的代码的代码Mi实例：对英文字母从实例：对英文字母从126编码，空格为编码，空格为0，对明文，对明文双字母编码，如双字母编码，如“its all greek to me”编码为：编码为：0920、1900、0112、1200、0718、0505、1100

14、、2015、0013、0500设设p=47、q=59，则则n=2773，(2773)=46*58=2668因因17*157=2669=1 (mod 2668)，故取公钥为故取公钥为，私钥为，私钥为对明文组对明文组M=0920加密，加密，C=92017=0948(mod 2773)，190017=2342(mod 2773)，其余各组的密文为：，其余各组的密文为：1084、1444、2663、2390、0778、0774、0219、1655对密文组对密文组C=948解密，解密，M=948157=920(mod 2773)详见：详见：RSA加密解密实例加密解密实例.doc6.3.4 计算方法及其程

15、序实现计算方法及其程序实现 如何计算模逆元如何计算模逆元要在已知要在已知e、m的状况下，求的状况下，求d，使得，使得 e*d=1(mod m)也即找整数也即找整数k，使得，使得e*d+mk=1这相当于求解这相当于求解d、k都是未知数的二元一次都是未知数的二元一次不定方程不定方程 e*d+mk=1的最小整数解的最小整数解2.扩展扩展Euclid算法算法3.输入：正整数输入：正整数a、b4.输出：输出：GCD(a,b)及满足及满足ax+by=GCD(a,b)的的整数整数x、y5.例如：设例如：设a=21、b=15，则，则GCD(a,b)=3，x=-2、y=36.算法步骤描述：算法步骤描述：7.置置

16、x1=1，x2=0，y1=0，y2=18.计算计算q=a/b，r=a%b9.若若r=0，则，则GCD(a,b)=b，x=x2，y=y2，算，算法结束；否则做下步法结束；否则做下步10.依次令依次令a=b，b=r，t=x2，x2=x1-qx2，x1=t，11.t=y2，y2=y1-qy2，y1=t，然后转，然后转2)附：附：扩展扩展Euclid算法算法.CPP3.乘法逆元的计算乘法逆元的计算4.输入：正整数输入：正整数e、m5.输出：输出：GCD(e,m)及满足及满足ed=GCD(e,m)(mod m)的整数的整数d6.当当GCD(e,m)=1（即（即e、m互素），互素），7.则则d=e-1(m

17、od m)8.例如：设例如：设e=7、m=17，则，则GCD(7,17)=1，d=5=7-1；因为；因为7*5=35=17*2+1=1(mod 17)9.算法：在扩展算法：在扩展Euclid算法中令算法中令a=e、b=m，则，则ex+my=GCD(e,m)(mod m)，10.即即 ex=GCD(e,m)(mod m)；11.若结果若结果GCD(e,m)=1，则，则d=e-1=x；否则；否则e没有逆元没有逆元附：附：求乘法逆元求乘法逆元.CPP4.解密指数解密指数最小正逆元的计算最小正逆元的计算附：附：求求最小正逆元最小正逆元.CPP设设d是是e的逆元，即的逆元，即ed=1(mod m)，由于

18、，由于e(d+km)=ed+ekm=ed=1(mod m)，故，故d+km也是也是e的的逆元，可见乘法逆元不惟一。逆元，可见乘法逆元不惟一。在上述乘法逆元算法中得到的逆元最接近零，但有在上述乘法逆元算法中得到的逆元最接近零，但有可能为负。可能为负。例如：设例如：设e=3、m=40，则，则GCD(3,40)=1，但，但d=13，明显不能用作，明显不能用作RSA算法的解密指数。因此必需将算法的解密指数。因此必需将这种负逆元调整为正逆元，才能得到解密指数。这种负逆元调整为正逆元，才能得到解密指数。改进后的算法如下：改进后的算法如下：输入：正整数输入：正整数e、m输出：输出：GCD(e,m)及满足及满

19、足ed=GCD(a,m)(mod m)的的最小正整数最小正整数d;当当CD(e,m)=1，则，则d=e-1(mod m)就是就是所求解密指数所求解密指数5.模幂的快速算法模幂的快速算法6.输入：整数输入：整数n、正整数、正整数m、e7.输出：输出：C=ne (mod m)8.算法：算法：9.将将e表示为二进制形式表示为二进制形式(bkbk-1 b1b0)10.C=111.对于从对于从k到到0的的i做做C=C*C(mod m)，假，假如如bi=1则再做则再做C=C*n (mod m)12.返回返回C附：附：快速求模幂快速求模幂.CPP6.素性检测算法之一素性检测算法之一Miller-Rabin算

20、法算法对于充分大的正奇数对于充分大的正奇数n，设设n-1=2km（其中其中k是非负整数、是非负整数、m是正奇数），是正奇数），若若bm=1(mod n)或或b2jm=1（其中其中 0j i-1），则称则称n通过以通过以b为基的为基的Miller-Rabin素性检测素性检测也即也即n以以(1-1/4b)的概率是素数的概率是素数输入：大奇数输入：大奇数n、检测次数、检测次数t输出：确定输出：确定n是合数或者以是合数或者以(1-1/4t)的概率是素的概率是素数。如：数。如：t=5，则判定，则判定n是素数的正确性约为：是素数的正确性约为：(1-1/45)=0.9990234375 算法：算法：将将n-

21、1表示为二进制形式表示为二进制形式(bkbk-1 b1b0)随机选取从随机选取从1到到n-1的整数的整数ax=1对于从对于从k到到0的的i依次做依次做:x0=x、x=x2(mod n)，假，假如如x=1&x01&x0n-1则返回则返回“是是”，算法，算法结束；假如结束；假如bi=1则再做则再做x=x*a (mod n)假如假如x 1则返回则返回“是是”，算法结束，算法结束转转2)直至算法结束或完成直至算法结束或完成t回测试，若完成回测试，若完成t回测回测试则返回试则返回“不是不是”，即，即n是伪素数是伪素数附：附：用用M-R检测素数检测素数.CPP 求求65535以下的素数以下的素数.CPP形

22、如形如2p1（其中（其中P为素数）的素数称为梅森素数为素数）的素数称为梅森素数（Mersenne prime），它是以），它是以17世纪法国数学家、法世纪法国数学家、法兰西科学院奠基人马林兰西科学院奠基人马林梅森的姓命名的。梅森的姓命名的。2008年年8月，美国加州高校洛杉矶分校月，美国加州高校洛杉矶分校(UCLA)的计的计算机专家史密斯算机专家史密斯(E.Smith)通过参与了一个名为通过参与了一个名为“因特网梅森素数大搜寻因特网梅森素数大搜寻”(GIMPS)的国际合作项目，的国际合作项目，发觉了第发觉了第46个也是目前最大的梅森素数个也是目前最大的梅森素数243112609-1。它有它有1

23、2,978,189（近（近1300万）位数，假如用一般字万）位数，假如用一般字号将这个巨数连续写下来，它的长度可超过号将这个巨数连续写下来，它的长度可超过50公里公里!这一成就被美国的时代杂志评为这一成就被美国的时代杂志评为“2008年度年度50项最佳独创项最佳独创”之一，排名在第之一，排名在第29位。位。由于这种素数珍奇而迷人，因此被人们誉为由于这种素数珍奇而迷人，因此被人们誉为“数学数学海洋中的绚烂明珠海洋中的绚烂明珠”。梅森素数始终是数论探讨的。梅森素数始终是数论探讨的一项重要内容，也是当今科学探究的热点和难点。一项重要内容，也是当今科学探究的热点和难点。6.3.5 梅森素数梅森素数6.

24、3.6 RSA方案的设计流程方案的设计流程1)用素性检测法选两个充分大的素数用素性检测法选两个充分大的素数p、q2)计算计算n=pq及及(n)=(p-1)(q-1)3)选择一个介于选择一个介于1到到(n)之间的正整数之间的正整数e4)用扩展用扩展Euclid算法计算算法计算GCD(e,(n)，若为若为1则则转下步，否则转转下步，否则转3)5)选出选出e的最小正逆元的最小正逆元d=e-1 (mod(n)6)销毁销毁p、q，选选e、d中的较小的一个与中的较小的一个与n组成公钥组成公钥并予以公布，另一个作为私钥予以严格保密并予以公布，另一个作为私钥予以严格保密7)设计加密方案：以某种规则将明文消息表

25、示为设计加密方案：以某种规则将明文消息表示为若干个小于若干个小于n的非负整数的非负整数6.3.7 RSA算法的平安性算法的平安性对对RSA的攻击等效于对模数的攻击等效于对模数n的因数分的因数分解，属于解，属于NP-类计算问题（不确定性类计算问题（不确定性多项式时间可解）多项式时间可解）附：将输入的充分大正整数分解为两个附：将输入的充分大正整数分解为两个素数之积（可能的话）的算法素数之积（可能的话）的算法整整数分解为素数之积数分解为素数之积.CPPp、q应尽量取符合下列要求的强素数：应尽量取符合下列要求的强素数：p-1有大的素因子有大的素因子rp+1有大的素因子有大的素因子r-1有大的素因子有大

26、的素因子知道知道(n)则可求得则可求得p、q，故应予以保密，故应予以保密或销毁或销毁泄漏解密指数泄漏解密指数d将有利于对将有利于对n的分解，的分解，因此不能光换因此不能光换d而必需选择新的而必需选择新的p、q7不同用户不行共享不同用户不行共享n 和和p、q7在一对加密、解密指数中，尽可能在一对加密、解密指数中，尽可能让让ed7目前目前p、q在在1024位位(1.810308)2048位位(3.210616)之内是平之内是平安的安的7平安的平安的RSA方案速度较方案速度较DES、AES慢，一般用于对称加密体制中的密慢，一般用于对称加密体制中的密钥传递和交换钥传递和交换6.3.9 平安平安RSA算

27、法的实例算法的实例n=（1024位二进制、位二进制、256位十六进制）位十六进制）328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD15F90B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F017F9CCF1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD60438941D2ED173CCA50E114705D7E2BC511951公钥公

28、钥e=10001H6.3.8 RSA算法的演示算法的演示RSA-TOOL私钥私钥d=E760A3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D87A3106DD28C523C29954C5D86B36E943080E4919CA8CE08718C3B0930867A98F635EB9EA9200B25906D91B80A47B77324E66AFF2C4D70D8B1C69C50A9D8B4B7A3C9EE05FFF3A16AFC023731D80634763DA1DCABE9861A4789BD782A592D2B1965设明文

29、编码设明文编码M=则加密后的密文则加密后的密文C=Me(mod n)=17b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576bd45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed1d4cC4b293e26bc0a1dc67e247715caa6b3028f9461a3b1533ec0cb476441465f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91f1834580c3f6d90898 解密后还原成明文

30、解密后还原成明文M=Cd(mod n)=1.相对于对称密码体制，公钥密码体制有何优点相对于对称密码体制，公钥密码体制有何优点？2.请用生活中的例子简述用于机密性的公钥密码请用生活中的例子简述用于机密性的公钥密码体制的加密解密过程体制的加密解密过程3.最典型的公钥密码体制是哪一个？最典型的公钥密码体制是哪一个？4.RSA密码体制的数学基础是什么？密码体制的数学基础是什么？5.RSA密码体制的平安性依靠于什么？密码体制的平安性依靠于什么？6.请简述一个具体的请简述一个具体的RSA方案的设计过程方案的设计过程7.RSA密码体制的主要缺点是什么？密码体制的主要缺点是什么？8.p、q至少取十进制几位才能

31、使至少取十进制几位才能使RSA方案具有平方案具有平安意义？安意义？9.什么是单向函数？什么是单向函数？10.能否用私钥加密而用公钥解密？有何用途？能否用私钥加密而用公钥解密？有何用途？附：关于公钥密码体制与附：关于公钥密码体制与RSA的探讨的探讨6.4 ElGamal（Taher ElGamal提出）密码体制提出）密码体制6.4.1 数论背景数论背景1.离散对数离散对数在模意义下的对数在模意义下的对数设正整数设正整数、a和和p，若若 a=(mod p)，则称则称a是是的以的以为底在模为底在模p意义下的离散对数，意义下的离散对数，记作记作a=log(mod p)。例如：例如：因因54=625=9

32、(mod 11)，故故log59(mod 11)=42.本原元和循环群本原元和循环群定义：设定义：设p是素数，是素数，Zp=0,1,2,3,p-1，Zp*=1,2,3,p-1，若对任一，若对任一 Zp*，总存在正整数总存在正整数a，使得，使得a=(mod p)，也即：，也即：Zp中随意非中随意非0元素总存在离散对数元素总存在离散对数log(mod p)，则，则称为称为Zp*（或（或p）的本原元）的本原元（或生成元、基元、原根），也即（或生成元、基元、原根），也即Zp 对模对模p乘构成循环群乘构成循环群可以证明：可以证明：对于素数对于素数p，Zp*共有共有(p-1)个本原元个本原元对于素数对于素

33、数p，设，设 Zp*有一个本原元有一个本原元g，则，则Zp*的全部本原元由以下集合给出：的全部本原元由以下集合给出：gt|1tp-1,GCD(t,p-1)=1 对于素数对于素数p，推断，推断g是否是否Zp*的本原元，不须的本原元，不须要逐一计算要逐一计算g1，g2，gp-1，而仅须，而仅须要计算全部要计算全部gt(mod p），其中），其中t|p-1。只。只要不产生重复结果，要不产生重复结果，g就是素数就是素数p的本原的本原元元例如：例如：Z19=0,1,2,3,18，(18)=6(1,5,7,11,13,17),故故Z19*=1,2,3,18共有共有6个本个本原元：原元：2,3,10,13,

34、14,15；验证验证15是是Z19*的本原元：的本原元：满足满足t|18的的t有：有：1,2,3,6,9151=15，152=16，153=12，156=11，159=18附：附：求本原元求本原元.CPP6.4.2 密码体系设计步骤密码体系设计步骤1.选择合适的大素数选择合适的大素数p，建立循环群建立循环群Zp=0,1,2,3,p-1，使得在，使得在Zp中求离散对数是困中求离散对数是困难的难的2.选择选择Zp*的本原元的本原元 3.针对某用户任选针对某用户任选aZp，计算计算=a(mod p)，以形成公钥以形成公钥(p,)和私钥和私钥a4.加密：对于明文加密：对于明文xZp，随机选取正整数随机

35、选取正整数r Zp*，计算计算 y1=r(mod p)和和 y2=xr(mod p)，得到密文对得到密文对(y1,y2)5.解密：解密：x=y2(y1a)-1(mod p)6.4.3 解密还原性的证明解密还原性的证明留意：留意：(y1a)-1(mod p)=(y1a(mod p)-1(mod p)因为：因为：y1=r(mod p)、y2=xr(mod p)、=a(mod p)所以：所以：y2(y1a)-1(mod p)=xr(r)a)-1(mod p)=x(a)r(r)a)-1(mod p)=xar(ra)-1(mod p)=x(mod p)6.4.4 平安性及算法说明平安性及算法说明1.由由

36、、a 求求=a(mod p)是简洁的是简洁的2.当当p充分大，由充分大，由、求离散对数求离散对数a=log(mod p)是极其困难的是极其困难的3.为抗击已知的攻击，为抗击已知的攻击，p至少是至少是150位十位十进制数，并且进制数，并且p-1有大的素因子有大的素因子4.p、可为全部用户共享可为全部用户共享5.a、属于某一个接收方，其中属于某一个接收方，其中是公是公钥，钥，a 是私钥是私钥6.r属于每次加密过程，由发送方选取，属于每次加密过程，由发送方选取，需保密，但在解密时不用，故可在加需保密，但在解密时不用，故可在加密后销毁密后销毁6.5 Diffie-Hellman密钥交换算法密钥交换算法

37、概述概述简称简称D-H密钥交换算法密钥交换算法用于通信双方交换密钥用于通信双方交换密钥所要交换的密钥用于加密明文，一般是对所要交换的密钥用于加密明文，一般是对称密钥称密钥平安性依靠于计算离散对数的困难性平安性依靠于计算离散对数的困难性2.算法步骤算法步骤A、B方预先确定两个公开的整数：方预先确定两个公开的整数：q和和a，其中，其中q是素数，是素数，a是是q的本原元的本原元A选择一个保密的随机数选择一个保密的随机数XAq，计算：，计算：YA=aXA (mod q)，并予以公开，并予以公开B选择一个保密的随机数选择一个保密的随机数XBq，计算：，计算：YB=aXB (mod q)，并予以公开，并予

38、以公开A计算：计算：K=YBXA (mod q)，从而得到所，从而得到所要交换的密钥要交换的密钥K B计算：计算：K=YAXB (mod q)，从而得到所，从而得到所要交换的密钥要交换的密钥K注：注：C虽然知道虽然知道YA和和YB，但由于不知道，但由于不知道XA或或XB，故无法得到，故无法得到K=YBXA=YAXB3.通信示意图通信示意图4.密钥相同的证明密钥相同的证明YBXA (mod q)=(aXB(mod q)XA (mod q)=(aXB)XA (mod q)=(aXA)XB (mod q)=(aXA(mod q)XB (mod q)=YAXB (mod q)5.例子例子对于素数对于素

39、数q=97，选择它的一个本原元，选择它的一个本原元a=5A和和B分别选择随机数分别选择随机数XA=36和和XB=58A计算公开密钥：计算公开密钥：YA=536=50(mod 97)B计算公开密钥：计算公开密钥：YB=558=44(mod 97)A计算所要交换的密钥：计算所要交换的密钥：K=4436=75(mod 97)B计算所要交换的密钥：计算所要交换的密钥：K=5058=75(mod 97)作业作业P146页：页：1、2、3、4、5、6、7、9、10（改为（改为“给出加密、解密结果给出加密、解密结果”）、）、11、补充题：在补充题：在ELGamal密码体制下，设素数密码体制下，设素数p=19，验证，验证=13是是 Z19*的本原元，针对私钥的本原元，针对私钥a=10，计算公钥，计算公钥(p,)；对于消息明文；对于消息明文x=15，随，随机选取正整数机选取正整数r=11，请计算密文对，请计算密文对(y1,y2)，并由并由(y1,y2)还原出明文。还原出明文。