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

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

1、第六章第六章 非对称密码体制非对称密码体制信息安全技术信息安全技术 6.1 概述概述6.1.1 对称密码体制的缺陷对称密码体制的缺陷1.密钥的安全传递比较困难密钥的安全传递比较困难2.n个用户多点通信所需密钥数为个用户多点通信所需密钥数为n(n-1)/2个个3.难以提供对主动攻击的抗击难以提供对主动攻击的抗击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：1.正向易算性正向易算性由消息由消息x和密钥和密钥pk 容易计算容易计算y=fpk(x)2.反向不可算性反向不可算性在不知道密钥在不知道密钥sk的情况下，由任的情况下，由任意的意的y倒过来计算倒过来计算x=f-1sk(y)都是不可行的都是不可行的3.陷门依赖性陷门依赖性如果给定另一密钥如果给定另一密钥sk，则，则f-1(y)是是可以计算的，

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

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

8、3,14)4.当当e与与m互素，则存在正整数互素，则存在正整数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是素数，则是素数，则

9、m p-1=1 (mod p)（因为（因为(p)=p-1）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)+

10、1=x (mod p)若若x是是p的倍数，则的倍数，则 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 概述概述1

11、.发明人发明人RSA(Ron Rivest,AdiShamir 和和 Leonard Adleman)2.1977年在年在麻省理工学院开发麻省理工学院开发3.1978年发表年发表4.是最典型的公钥密码体制是最典型的公钥密码体制5.算法基于单向陷门函数的原理算法基于单向陷门函数的原理6.以模幂运算为基本运算以模幂运算为基本运算7.安全性基于大数因子分解的困难性安全性基于大数因子分解的困难性（将一个充分大的正整数分解成两个（将一个充分大的正整数分解成两个素数之积几乎是不可能的）素数之积几乎是不可能的）8.数学基础是著名的欧拉数学基础是著名的欧拉(Euler)数论数论6.3.2 RSA密码体制的创建

12、密码体制的创建1)选择两个充分大的不同的素数选择两个充分大的不同的素数p和和q2)计算积计算积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

13、=1(mod(n)，故存在非负整数故存在非负整数k，使得：使得：ed=k(n)+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”编码为

14、：编码为：0920、1900、0112、1200、0718、0505、1100、2015、0013、0500设设p=47、q=59，则则n=2773，(2773)=46*58=2668因因17*157=2669=1 (mod 2668)，故取公钥为故取公钥为，私钥为，私钥为对明文组对明文组M=0920加密，加密，C=92017=242322122805021463846350650290995200000000000000000=0948(mod 2773)，190017=54803868577848021859390000000000000000000000000000000000=2342

15、(mod 2773)，其余各组的密文为：，其余各组的密文为：1084、1444、2663、2390、0778、0774、0219、1655对密文组对密文组C=948解密，解密，M=948157=22851197405028860635677690234400325078676533928042956748370399668767991875431080811676258194650030904493506389581399490386260788943541096937266568769533212557718964278188604864941133928029184731979029505

16、2238061530036066382680768550813673301548951552880234295829603371076580111293376807996489026124001520858798504685685090226812534126526485193603752385784652819655258004954411544721976443792145433128756776848416542537051430937496263760556207832371853899712995186966528=920(mod 2773)详见：详见：RSA加密解密实例加密解密实例

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

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

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

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

21、最小正整数d;当当CD(e,m)=1，则则d=e-1(mod m)就是就是所求解密指数所求解密指数5.模幂的快速算法模幂的快速算法输入：整数输入：整数n、正整数正整数m、e输出：输出：C=ne (mod m)算法：算法：1)将将e表示为二进制形式表示为二进制形式(bkbk-1 b1b0)2)C=13)对于从对于从k到到0的的i做做C=C*C(mod m)，如果如果bi=1则再做则再做C=C*n (mod m)4)返回返回C附：附：快速求模幂快速求模幂.CPP6.素性检测算法之一素性检测算法之一Miller-Rabin算法算法对于充分大的正奇数对于充分大的正奇数n，设设n-1=2km（其中其中k

22、是非负整数、是非负整数、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 算法：算法：1)将将n-1表示为二进制形式表示为二进制形式(bkbk-1 b1b0)2)随机选取从随

23、机选取从1到到n-1的整数的整数a3)x=14)对于从对于从k到到0的的i依次做依次做:x0=x、x=x2(mod n)，如果如果x=1&x01&x0n-1则返回则返回“是是”，算法结束；如果算法结束；如果bi=1则再做则再做x=x*a (mod n)5)如果如果x 1则返回则返回“是是”，算法结束，算法结束6)转转2)直至算法结束或完成直至算法结束或完成t回测试，若完成回测试，若完成t回测试则返回回测试则返回“不是不是”，即，即n是伪素数是伪素数附：附：用用M-R检测素数检测素数.CPP 求求65535以下的素数以下的素数.CPP形如形如2p1（其中（其中P为素数）的素数称为梅森素数为素数）

24、的素数称为梅森素数（Mersenne prime），它是以），它是以17世纪法国数学家、世纪法国数学家、法兰西科学院奠基人马林法兰西科学院奠基人马林梅森的姓命名的。梅森的姓命名的。2008年年8月，美国加州大学洛杉矶分校月，美国加州大学洛杉矶分校(UCLA)的计的计算机专家史密斯算机专家史密斯(E.Smith)通过参加了一个名为通过参加了一个名为“因因特网梅森素数大搜索特网梅森素数大搜索”(GIMPS)的国际合作项目，的国际合作项目，发现了第发现了第46个也是目前最大的梅森素数个也是目前最大的梅森素数243112609-1。它有它有12,978,189（近（近1300万）位数，如果用普通字万）

25、位数，如果用普通字号将这个巨数连续写下来，它的长度可超过号将这个巨数连续写下来，它的长度可超过50公里公里!这一成就被美国的这一成就被美国的时代时代杂志评为杂志评为“2008年度年度50项最佳发明项最佳发明”之一，排名在第之一，排名在第29位。位。由于这种素数珍奇而迷人，因此被人们誉为由于这种素数珍奇而迷人，因此被人们誉为“数学数学海洋中的璀璨明珠海洋中的璀璨明珠”。梅森素数一直是数论研究的。梅森素数一直是数论研究的一项重要内容，也是当今科学探索的热点和难点。一项重要内容，也是当今科学探索的热点和难点。6.3.5 梅森素数梅森素数6.3.6 RSA方案的设计流程方案的设计流程1)用素性检测法选

26、两个充分大的素数用素性检测法选两个充分大的素数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)设计加密方案：以某种规则将明文消息表示为设计加密方案：以某种规则将明文消息表示为若干个小于若干个

27、小于n的非负整数的非负整数6.3.7 RSA算法的安全性算法的安全性7对对RSA的攻击等效于对模数的攻击等效于对模数n的因数分解，的因数分解，属于属于NP-类计算问题（不确定性多项式时间类计算问题（不确定性多项式时间可解）可解）附：将输入的充分大正整数分解为两个素数之附：将输入的充分大正整数分解为两个素数之积（可能的话）的算法积（可能的话）的算法整数分解为素数整数分解为素数之积之积.CPP7p、q应尽量取符合下列要求的强素数：应尽量取符合下列要求的强素数：p-1有大的素因子有大的素因子rp+1有大的素因子有大的素因子r-1有大的素因子有大的素因子7知道知道(n)则可求得则可求得p、q，故应予以

28、保密或销故应予以保密或销毁毁7泄漏解密指数泄漏解密指数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算法的实例算法的实例n=（1024位二进制、位二进制、2

29、56位十六进制）位十六进制）328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD15F90B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F017F9CCF1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD60438941D2ED173CCA50E114705D7E2BC511951公钥公钥e=10001H6.3.8 RSA算法的演示算法的演

30、示RSA-TOOL私钥私钥d=E760A3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D87A3106DD28C523C29954C5D86B36E943080E4919CA8CE08718C3B0930867A98F635EB9EA9200B25906D91B80A47B77324E66AFF2C4D70D8B1C69C50A9D8B4B7A3C9EE05FFF3A16AFC023731D80634763DA1DCABE9861A4789BD782A592D2B1965设明文编码设明文编码M=111111111111222222

31、22222233333333333 则加密后的密文则加密后的密文C=Me(mod n)=17b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576bd45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed1d4cC4b293e26bc0a1dc67e247715caa6b3028f9461a3b1533ec0cb476441465f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91f1834580c3f6d90898

32、 解密后还原成明文解密后还原成明文M=Cd(mod n)=111111111111222222222222333333333331.相对于对称密码体制，公钥密码体制有何优点相对于对称密码体制，公钥密码体制有何优点？2.请用生活中的例子简述用于机密性的公钥密码请用生活中的例子简述用于机密性的公钥密码体制的加密解密过程体制的加密解密过程3.最典型的公钥密码体制是哪一个？最典型的公钥密码体制是哪一个？4.RSA密码体制的数学基础是什么？密码体制的数学基础是什么？5.RSA密码体制的安全性依赖于什么？密码体制的安全性依赖于什么？6.请简述一个具体的请简述一个具体的RSA方案的设计过程方案的设计过程7.

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

34、数，意义下的离散对数，记作记作a=log(mod p)。例如：例如：因因54=625=9(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乘构乘构成循环群成循环群可以证明：

35、可以证明：1.对于素数对于素数p，Zp*共有共有(p-1)个本原元个本原元2.对于素数对于素数p，设设 Zp*有一个有一个本原元本原元g，则，则Zp*的所有本原元由以下集合给出：的所有本原元由以下集合给出：gt|1tp-1,GCD(t,p-1)=1 3.对于素数对于素数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,

36、13,17),故故Z19*=1,2,3,18共有共有6个本个本原元：原元：2,3,10,13,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)，以形成

37、公钥以形成公钥(p,)和私钥和私钥a4.加密：对于明文加密：对于明文xZp，随机选取正整数随机选取正整数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(

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

39、但在解密时不用，故可在加密后销毁6.5 Diffie-Hellman密钥交换算法密钥交换算法1.概述概述7简称简称D-H密钥交换算法密钥交换算法7用于通信双方交换密钥用于通信双方交换密钥7所要交换的密钥用于加密明文，一般是所要交换的密钥用于加密明文，一般是对称密钥对称密钥7安全性依赖于计算离散对数的困难性安全性依赖于计算离散对数的困难性2.算法步骤算法步骤A、B方预先确定两个公开的整数：方预先确定两个公开的整数：q和和a，其中，其中q是素数，是素数，a是是q的本原元的本原元A选择一个保密的随机数选择一个保密的随机数XAq，计算：，计算：YA=aXA (mod q)，并予以公开，并予以公开B选择

40、一个保密的随机数选择一个保密的随机数XBq，计算：，计算：YB=aXB (mod q)，并予以公开，并予以公开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 (mo

41、d q)=(aXA(mod q)XB (mod q)=YAXB (mod q)5.例子例子对于素数对于素数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)还原出明文。还原出明文。