第六章第六章 非对称密码体制非对称密码体制信息安全技术信息安全技术 非对称密码体制6.1 概述概述6.1.1 对称密码体制的缺陷对称密码体制的缺陷1.密钥的安全传递比较困难密钥的安全传递比较困难2.n个用户多点通信所需密钥数为个用户多点通信所需密钥数为n(n-1)/2个个3.难以提供对抗抵赖功能的支持难以提供对抗抵赖功能的支持6.1.2 公钥（非对称）密码体制的基本思想公钥（非对称）密码体制的基本思想 Whitfield Diffie和和Martin Hellman在在1976年年n首先提出：用公开的密钥（公钥）加密，用与之首先提出：用公开的密钥（公钥）加密，用与之对应的不公开的密钥（私钥）解密。对应的不公开的密钥（私钥）解密。 公钥密码体制提出的标志性文献公钥密码体制提出的标志性文献密码学密码学的新方向：的新方向： 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非对称密码体制例：卢毅要传送密信给胡旦，用胡旦的公钥对明文例：卢毅要传送密信给胡旦，用胡旦的公钥对明文进行加密，然后通过公共信道将密文传送给胡旦，进行加密，然后通过公共信道将密文传送给胡旦，胡旦用的与自己的公钥对应的私钥（只有胡旦自胡旦用的与自己的公钥对应的私钥（只有胡旦自己知道）解密得到明文。俞敏祺企图知道密信内己知道）解密得到明文。俞敏祺企图知道密信内容，截获到密文，虽然他也知道加密所用的公钥，容，截获到密文，虽然他也知道加密所用的公钥，但他无法通过公钥倒推出相应的私钥，当然就不但他无法通过公钥倒推出相应的私钥，当然就不可能解密出明文。可能解密出明文。非对称密码体制6.1.2 对公钥密码体制的要求对公钥密码体制的要求（1）参与方）参与方B容易通过计算产生一对密钥（公开密钥容易通过计算产生一对密钥（公开密钥KUb和私有密钥和私有密钥KRb）。）。（2）在知道公钥和待加密报文）在知道公钥和待加密报文M的情况下，对于发的情况下，对于发送方送方A，很容易通过计算产生对应的密文：，很容易通过计算产生对应的密文：C=EKUb(M)（3）接收方）接收方B使用私钥容易通过计算解密所收到的密使用私钥容易通过计算解密所收到的密文文C以便恢复原来的明文：以便恢复原来的明文： M=DKRb(C)=DKRb (EKUb(M)（4）攻击者即使知道公钥）攻击者即使知道公钥KUb，要确定其对应的私，要确定其对应的私钥钥KRb在计算上是不可行的。在计算上是不可行的。（5）攻击者即使知道公钥）攻击者即使知道公钥KUb和密文和密文C，要想恢复原，要想恢复原来的明文来的明文M在计算上也是不可行的。在计算上也是不可行的。（6）加密和解密函数可以以两个次序中的任何一个）加密和解密函数可以以两个次序中的任何一个来使用来使用: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)是是可以计算的，可以计算的， sk 与与pk配对，相当于陷门。配对，相当于陷门。 满足满足1、2的函数称为单向函数的函数称为单向函数 满足满足1、2、3的函数被称为带陷门的单向函数的函数被称为带陷门的单向函数非对称密码体制非对称密码体制 6.1.4 公钥密码体制的特点公钥密码体制的特点1.无需密钥的安全传递无需密钥的安全传递2.n个用户仅需个用户仅需n个个“公钥公钥-私钥私钥”对对3.支持数字签名机制支持数字签名机制4.安全性基于带陷门的单向函数安全性基于带陷门的单向函数5.加密、解密速度比加密、解密速度比DES、AES等等分组密码体制慢分组密码体制慢6.可用于对称密钥的交换可用于对称密钥的交换非对称密码体制6.2 数论背景数论背景欧拉函数与欧拉定理欧拉函数与欧拉定理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,13,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是素数，则是素数，则 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) +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.发明人发明人RSA(Ron Rivest, AdiShamir 和和 Leonard Adleman) 2.1977年在年在麻省理工学院开发麻省理工学院开发3.1978年发表年发表4.是最典型的公钥密码体制是最典型的公钥密码体制5.算法基于单向陷门函数的原理算法基于单向陷门函数的原理6.以模幂运算为基本运算以模幂运算为基本运算7.安全性基于大数因子分解的困难性安全性基于大数因子分解的困难性（将一个充分大的正整数分解成两个（将一个充分大的正整数分解成两个素数之积几乎是不可能的）素数之积几乎是不可能的）8.数学基础是著名的欧拉数学基础是著名的欧拉(Euler)数论数论非对称密码体制6.3.2 RSA密码体制的创建密码体制的创建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=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 ”编码为：编码为：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=242322122835000000=0948 (mod 2773)，190017=548000000000=2342 (mod 2773)，其余各组的密文为：，其余各组的密文为： 1084、1444、2663、2390、0778、0774、0219、1655非对称密码体制对密文组对密文组C=948解密，解密，M=948157 =228511974677697867653392891167625819465894354557761979682685829611129337681242652648519366528196552584721976443792677684841654253762637671853899712995186966528=920 (mod 2773) 详见：详见：RSA加密解密实例加密解密实例.doc非对称密码体制6.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算法步骤描述：算法步骤描述：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算法算法.CPP非对称密码体制3.乘法逆元的计算乘法逆元的计算输入：正整数输入：正整数e、m输出：输出：GCD(e,m)及满足及满足ed=GCD(e,m) (mod m)的整数的整数d当当GCD(e,m)=1 （即（即e、m互素）互素），则则d=e-1 (mod m)例如：设例如：设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没有没有逆元逆元附：附：求乘法逆元求乘法逆元.CPP非对称密码体制4.解密指数解密指数最小正逆元的计算最小正逆元的计算附：附：求求最小正逆元最小正逆元.CPP设设d是是e的逆元，即的逆元，即ed=1 (mod m)，由于由于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)及满足及满足ed=GCD(a,m) (mod m)的的最小正整数最小正整数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附：附：快速求模幂快速求模幂.CPP非对称密码体制6.素性检测算法之一素性检测算法之一Miller-Rabin算法算法对于充分大的正奇数对于充分大的正奇数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 算法：算法：1)将将n-1表示为二进制形式表示为二进制形式(bkbk-1 b1b0)2)随机选取从随机选取从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为素数）的素数称为梅森素数为素数）的素数称为梅森素数;它是以它是以17世纪法国数学家、法兰西科学院奠基人世纪法国数学家、法兰西科学院奠基人马林马林梅森的姓命名的。梅森的姓命名的。最近美国国家海洋和大气局最近美国国家海洋和大气局(NOAA)信息技术顾问、信息技术顾问、数学爱好者乔希数学爱好者乔希芬德利使用一台装有芬德利使用一台装有2.4GHz奔奔腾处理器的个人计算机，发现了目前世界上已知腾处理器的个人计算机，发现了目前世界上已知的最大素数。的最大素数。该梅森素数为该梅森素数为21，它有它有7235733位数，位数，如果用普通字号将这个数字连续写下来，它的长如果用普通字号将这个数字连续写下来，它的长度可达度可达30公里！公里！6.3.5 梅森素数梅森素数非对称密码体制6.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)设计加密方案：以某种规则将明文消息表示为设计加密方案：以某种规则将明文消息表示为若干个小于若干个小于n的非负整数的非负整数非对称密码体制6.3.7 RSA算法的安全性算法的安全性7对对RSA的攻击等效于对模数的攻击等效于对模数n的因数分解，的因数分解，属于属于NP-类计算问题（不确定性多项式时间类计算问题（不确定性多项式时间可解）可解）附：将输入的充分大正整数分解为两个素数之附：将输入的充分大正整数分解为两个素数之积（可能的话）的算法积（可能的话）的算法整数分解为素数整数分解为素数之积之积.CPP7p、q应尽量取符合下列要求的强素数：应尽量取符合下列要求的强素数：p-1有大的素因子有大的素因子rp+1有大的素因子有大的素因子r-1有大的素因子有大的素因子7知道知道(n)则可求得则可求得p、q，故应予以保密或销故应予以保密或销毁毁7泄漏解密指数泄漏解密指数d将有利于对将有利于对n的分解，因此的分解，因此不能光换不能光换d而必须选择新的而必须选择新的p、q非对称密码体制7不同用户不可共享不同用户不可共享n 和和p、q7在一对加密、解密指数中，尽可能在一对加密、解密指数中，尽可能让让ed7目前目前p、q在在1024位位(1.810308) 2048位位(3.210616)之内是安全的之内是安全的7安全的安全的RSA方案速度较方案速度较DES、AES慢，一般用于对称加密体制中的密慢，一般用于对称加密体制中的密钥传递和交换钥传递和交换非对称密码体制6.3.9 安全安全RSA算法的实例算法的实例n=（1024位二进制、位二进制、256位十六进制）位十六进制）328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD15F90B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F017F9CCF1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD60438941D2ED173CCA50E114705D7E2BC511951公钥公钥e=10001H6.3.8 RSA算法的演示算法的演示RSA-TOOL非对称密码体制私钥私钥d=E760A3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D87A3106DD28C523C29954C5D86B36E943080E4919CA8CE08718C3B0930867A98F635EB9EA9200B25906D91B80A47B77324E66AFF2C4D70D8B1C69C50A9D8B4B7A3C9EE05FFF3A16AFC023731D80634763DA1DCABE9861A4789BD782A592D2B1965设明文编码设明文编码M= =11111111111122222222222233333333333 非对称密码体制则加密后的密文则加密后的密文C=Me (mod n)=17b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576bd45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed1d4cC4b293e26bc0a1dc67e247715caa6b3028f9461a3b1533ec0cb476441465f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91f1834580c3f6d90898 解密后还原成明文解密后还原成明文M= =Cd (mod n)=11111111111122222222222233333333333非对称密码体制1.相对于对称密码体制，公钥密码体制有何优点相对于对称密码体制，公钥密码体制有何优点？2.请用生活中的例子简述用于机密性的公钥密码请用生活中的例子简述用于机密性的公钥密码体制的加密解密过程体制的加密解密过程3.最典型的公钥密码体制是哪一个？最典型的公钥密码体制是哪一个？4.RSA密码体制的数学基础是什么？密码体制的数学基础是什么？5.RSA密码体制的安全性依赖于什么？密码体制的安全性依赖于什么？6.请简述一个具体的请简述一个具体的RSA方案的设计过程方案的设计过程7.RSA密码体制的主要缺点是什么？密码体制的主要缺点是什么？8.p、q至少取十进制几位才能使至少取十进制几位才能使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 (mod 11)，故故log59 (mod 11)=4非对称密码体制2.本原元和循环群本原元和循环群定义：设定义：设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)个本个本原元原元非对称密码体制例如：例如： Z19=0,1,2,3,18，(18)= 6(1,5,7,11,13,17),故故Z19*=1,2,3,18共有共有6个本个本原元：原元：2,3,10,13,14,15； 验证验证15是是Z19*的本原元：的本原元：151=15， 152=16， 153=12，154=9， 155=2， 156=11，157=13， 158=5， 159=18，1510=4， 1511=3， 1512=7，1513=10， 1514=17， 1515=8，1516=6， 1517=14， 1518=1附：附：求本原元求本原元.CPP非对称密码体制6.4.2 密码体系设计步骤密码体系设计步骤1.选择合适的大素数选择合适的大素数p，建立循环群建立循环群Zp =0,1,2,3,p-1，使得在，使得在Zp中求离散对数是困中求离散对数是困难的难的2.选择选择Zp *的本原元的本原元 3.针对某用户任选针对某用户任选aZp ，计算计算=a (mod p)，以形成公钥以形成公钥(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 (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属于每次加密过程，由发送方选取，需保属于每次加密过程，由发送方选取，需保密，但在解密时不用，故可在加密后销毁密，但在解密时不用，故可在加密后销毁非对称密码体制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选择一个保密的随机数选择一个保密的随机数XBq，计算：，计算： YB=aXB (mod q) ，并予以公开，并予以公开A计算：计算：K=YBXA (mod q)，从而得到所，从而得到所要交换的密钥要交换的密钥K B计算：计算：K=YAXB (mod q)，从而得到所，从而得到所要交换的密钥要交换的密钥K注：注：C虽然知道虽然知道YA和和YB，但由于不知道，但由于不知道XA或或XB ，故无法得到，故无法得到K=YBXA=YAXB非对称密码体制3.通信示意图通信示意图非对称密码体制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.例子例子对于素数对于素数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)还原出明文。还原出明文。 非对称密码体制