密码学课件 数字签名-作业

密码学导论IntroductiontoCryptology主讲教师：李卫海、胡红钢第10章数字签名数字签名数字签名的实现公钥密码的密钥管理数字签名算法与协议数字签名数字签名的实现公钥密码的密钥管理数字签名算法与协议签名的性质接收者可以凭借消息上所附加的某种东西，确认发信人的身份。这种东西，就是签名签名是独一无二的，是发信人所专有的签名一般应具有的性质：签名应当是可信的：签名者知道他所签名的内容反例：不知情签名。例如，夹在大量文件当中；垫复写纸签名应当是不可伪造的：确实是签名者所为反例：模仿他人的笔迹签名应当是不可重用的：不能被移做它用反例：扫描签名图像-复制-粘贴-打印签名的文件应当是不可改变的：不能篡改内容反例：文件中的空白区域；甚至空白签名签名应当是不可抵赖的：不能否认其行为反例：声称他人伪造自己的签名而抵赖数字签名的性质数字签名应当拥有的额外性质：接收方能够验证签名人、签名日期和时间可以由第三方仲裁，以解决争执认证被签名的消息内容，即认证完整性、真实性数字签名应满足以下条件：必须与消息相关必须使用发送者唯一拥有的信息——防止伪造和否认产生签名、识别和验证是容易的伪造在计算上是不可行的，无论是给定签名伪造消息，或是给定消息伪造签名可以存储、拷贝实现方式：私钥相关运算数字签名的基本形式对消息签名的两种方法对消息整体签名，消息整体经过密码变换得到签名，此时密文即签名对消息摘要签名，附在被签消息之后，或嵌在某一特定位置上作一段签名图样两个方法的签名验证方法不同两类数字签名确定性数字签名，明文与签名一一对应概率性数字签名，同一明文有多个合法签名数字签名的方法：直接数字签名仲裁数字签名仲裁者的安全性必须高度重视！直接数字签名直接数字签名仅涉及通信双方(信源、信宿)假定信宿知道信源的公开密钥，数字签名通过信源对整个报文，或对报文的摘要用私有密钥加密来实现签名与加密的顺序先签名后加密：消息内容和签名信息都被保护；验证前需解密先加密后签名：验证时只需提供密文；签名者未见到明文；签名可被替换签名

加密

签名直接数字签名：使用对称密码实现Alice和Bob间已共享密钥kAlice用k对消息进行加密，同时完成保密和签名密钥是Alice和Bob共享的，Bob可以确认文件来自Alice，即确认签名缺点：Alice可以假称密钥丢失，否认签名签名和加密绑定，能验证签名，就能阅读文件Bob不能聘请秘书来替他验证签名不适用于多人系统。Alice需要与N个人分别共享密钥，并分别加密N次直接数字签名：使用公钥密码实现签名者用私钥加密消息，任何人都可以用公钥解密获得明文，同时确认消息来自签名人优点：签名是不可伪造、签名是不可重用、签名的文件是不可改变通过加密算法，签名与密文捆绑在一起缺点：计算量大，速度慢不验证签名就无法获得消息明文，不适用于特殊场合例如，广播地震警报，并不需要所有人都去验证警报的来源需要将加密与签名分开。根据保密程度决定是否加密；验证签名时并不需要了解消息明文解决办法：专门的数字签名算法用对称密钥加密消息，用私钥加密较短的明文/密文消息摘要仲裁数字签名为解决直接数字签名中私钥安全带来的问题签名方伪称私钥丢失基本过程：签名方将签名的报文首先送给仲裁者A，仲裁者对报文和签名进行测试以检验出处和内容，然后注上日期和仲裁说明后发给接收方。仲裁者作用至关重要，通信各方必须对仲裁者适度的信任可以用对称密码或公钥密码实现仲裁者可以读取消息，也可以不读取仲裁数字签名：例Alice的签名由Trent进行验证，Bob不能直接读取Bob可保存收到的消息，需要时发给Trent来解决争执双方对Trent应高度信任Bob相信Trent只有验证签名正确后，才会向Bob发送消息Alice和Bob都相信Trent不会泄露密钥，不会伪造签名消息是公开的可以在第一步中，将M移至加密函数内，保护明文消息AliceBobTrent(1)M||E(KTA,IDA||H(M))(2)E(KTB,IDA||M||E(KTA,IDA||H(M))||T)(1)(2)仲裁数字签名：例Trent处理的是加密后的数据，不能读取明文消息如果仲裁者不公正怎么办？Trent和Alice共同否认一个已签名的消息Trent和Bob共同伪造发送者的签名(1)IDA||E(KAB,M)||E(KTA,IDA||H(E(KAB,M)))(2)E(KTB,IDA||E(KAB,M)||T)||E(KTA,IDA||H(E(KAB,M)))||T)AliceBobTrent(1)(2)仲裁数字签名：例通信前各方不共享任何信息，避免联合欺诈时间戳由Trent添加并签名，其他人不能伪造消息是保密的AliceBobTrent(1)(2)(1)IDA||E(PRA,IDA||E(PUB,E(PRA,M)))(2)E(PRT,IDA||E(PUB,E(PRA,M))||T)时间标记与抗抵赖私钥签名本身不能抗抵赖签名者可以声称私钥在较早时期丢失签名时，对消息摘要和时间戳共同进行签名需要专门机构记录并发布公钥有效情况但时间戳不能由签名者加入。为什么？窃取私钥的人，在签名时，可以附上一个较早的时间抵赖者可以声称发生了上述的事数字时间标记协议应有如下性质数据本身（无论何种介质）必须有时间标记改变文件的任何1个位都会引起文件的明显变化只能用当前日期和时间来标记文件仲裁建库提供时间标记由仲裁者Trent提供可信的时间标记服务存在的问题：文件M没有保密性，Trent的数据库的保密性也有潜在危险Trent的数据库是巨大的，所需的网络带宽也是巨大的依赖于Trent的可信性和安全性AliceTrent(1)M(2)M||T(2)保留副本仲裁签名提供时间标记利用散列函数和数字签名散列函数的使用保证了文件M的保密性散列函数的安全性很重要，需要抗弱碰撞或强碰撞。为什么？Trent不再保存文件副本，无需维护数据库散列值很短，对Trent带宽的要求低Trent的可信性和安全性仍存在问题Trent可以和Alice合谋制作假时间标记AliceTrent(1)H(M)(2)E(PRT,H(M)||T)链接协议提供时间标记将当前时间标记同过去产生的时间标记链接起来若有人对Alice的时间标记提问，则Alice可以和IDn-1和IDn+1联系出具证据若要Alice和Trent欲合谋，只能在Alice的文件前后创建一个虚拟的文件链，该链长度足以回答任何人对时间标记链的提问AliceTrent(1)Hn=H(M)(2)E(PRT,n||IDA||Hn||Tn||IDn-1||Hn-1||Tn-1||Ln)(3)IDn+1Ln=H(IDn-1,Hn-1,Tn-1,Ln-1)分布式链接协议提供时间标记若Alice无法找到IDn-1或IDn+1，则链接协议无法进行可以将前后10个人的标记都嵌入Alice的标记中，但显然代价增加很多分布式协议：Alice使用Hn作为输入，用密码学意义上安全的伪随机序列发生器CSPRNG产生一串随机数，视为k个人的标记ID1,ID2,ID3,…,IDkAlice将Hn发送给这k个人每个人都将时间附在Hn之后，签名并送回给AliceAlice收集所有签名作为时间标记CSPRNG可以保证Alice无法预测或指定她将选择哪些人进行签名分布式的链接协议，就是一个简单的区块链多重签名有时需要多方共同对一个文件进行签名，验证者可以选择验证其中一部分或全部各方分别进行签名，然后将所有的签名一起发布若是采用对摘要用私钥签名的方式，签名长度是单个签名的N倍签名各方顺序地、在前人的基础上进行签名操作。若是采用加密作为签名的方式，后一个人是对前一个人的密文再加密，最终长度不变若是采用对摘要用私钥签名的方式，后一个人需要将前一个人的签名也计算到摘要中，则最终长度是单个签名的N倍可以实现分级别的管理需要专门的算法才能保证验证者可以任意验证签名利用签名过程的攻击设想一个自动回复收据的系统AliceBob: E(PUB,D(PRA,M))Bob: M=E(PUA,D(PRB,E(PUB,E(PRA,M))))BobAlice: E(PUA,D(PRB,M))发送收据Alice: M=E(PUB,D(PRA,E(PUA,D(PRB,M))))确认Eve窃取消息——进行重放攻击：EveBob:E(PUB,D(PRA,M))。Bob用Eve的公钥验证签名，得乱码M'=E(PUE,D(PRA,M))Bob如自动回复，则会根据Eve的公钥进行加密BobEve:E(PUE,D(PRB,M’))Eve得到M'，进而算出M=E(PUA,D(PRE,M'))Eve也可以将Bob的收据在某个时刻发给Alice，并期待Alice的回复Eve可以窃取Bob的签名利用签名过程的攻击解决办法：不要随意回复乱码，明码也要看明白再回复永远不回复原文，而只回复原文的摘要值(hash)在消息中嵌入发送者ID，而非由地址默认AliceE(PUB,IDA||D(PRA,M))在消息中嵌入ID是一个好习惯，即使这个ID可以从其他地方推测得到。需要时甚至考虑将发送者和接收者ID都嵌入。嵌入时间戳（或随机数+数据库）也是个解决办法，但如何确定消息有效时限并不总是那么容易签名的应用实例对禁止核试验条约的监控美国和前苏联互相允许将地震测试仪放入对方的领土内，对核试验进行监控东道国需要确认测试仪发送的只是必要的监测数据监督国需要确认监测数据没有被篡改将监测数据签名后发送东道国只能读取，但不能篡改数字签名数字签名的实现公钥密码的密钥管理数字签名算法与协议RSA数字签名给定n=pq，p和q是大素数，edmodφ(n)=1，公开密钥为(n,e)，秘密密钥为(p,q,d)加密：c=memodn解密：m=cdmodn=medmodn=m签名：s=mdmodn验证：m=semodn=medmodn=m例：n=55=11×5，e=11，m=3答：

(n)=40，d=e-1mod

(n)=11签名：s=311mod55=47验证：m=4711mod55=3例：n=65=13×5，e=29，m=3答：

(n)=48，d=e-1mod

(n)=5签名：s=35mod65=48验证：m=4829mod65=3RSA数字签名：即加密也签名设用户A:nA,eA,dA；B:nB,eB,dB；A→B：m若nA<nB，则必须A：c=E(PUB,D(PRA,m))B：m=E(PUA,D(PRB,c))若nB<nA，则必须A：c=D(PRA,E(PUB,m))B：m=D(PRB,E(PUA,c))必须先用小模数对应密钥操作，

再用大模数对应的密钥操作例：用户Alice(nA,eA)=(15,3)，Bob(nB,eB)=(35,5)，A发送m=11给B，要求既保密又认证地传送。答：dA=3,dB=5nA<nB，因此先签名，后加密；先解密，后验证C=(113mod15)5mod35=16m=(165mod35)3mod15=11若先加密，后签名C=(115mod35)3mod15=163mod15=1m=(13mod15)5mod35=1出错ElGamal数字签名共享大素数p,本原元α;私钥x,公钥Y=αxmodp加密：0≤m≤p-1，随机选取k，1<k<p-1(c1,c2),c1=αkmodp,c2=mYBkmodp解密：K=c1xB

modp,m=c2K-1modp签名：随机选取k，1<k<p-1，且GCD(k,p-1)=1计算r=αkmodps满足：m=(xAr+ks)modp-1签名为(r,s)验证：检验αmmodp=YArrsmodp是否成立证明：αmmodp=α(xAr+ks)modp

=YArrs例：p=17,α=3,xA=2,xB=5,m=11,k=5签名：r=αkmodp=35mod17=5,11=(2×5+5s)mod165smod16=1,s=13.所以，签名为(5,13)。验证：αmmodp=311mod17=7YArrsmodp=(32)5×513mod17=7验证通过ElGamal数字签名r=αkmodpm=(xAr+ks)modp-1注意：k不能被泄露，否则私钥可以被解出k不能被重复使用（可以通过观察r发现），两次的方程联立可解出私钥若s为零，则应更换k重新计算。否则私钥可以被解出Schnorr数字签名方案基于离散对数难题，生成签名时所需的计算量最少（不计预处理）生成公钥/私钥对：选择素数p和q，使得q是p-1的一个素因子选择整数a，使得aq≡1(modp)，a、p和q构成全局公钥选择随机整数s，0<s<q，作为用户私钥计算v=a-smodp，作为用户公钥对消息M做签名运算：选择随机整数r，0<r<q，计算x=armodp计算e=H(M||x)计算y=(r+se)modq，签名为(e,y)验证签名：计算x'=ayve(modp)，验证e=H(M||x')证明：x'≡ayve≡aya-se≡ay-se≡ar≡x(modp)Schnorr数字签名方案预处理的安全性对比：Elgamal签名：随机选取k，1<k<p-1，且GCD(k,p-1)=1计算r=αkmodps满足：m=(xAr+ks)modp-1k的泄露会导致私钥xA泄露r作为签名一部分被公开，签名者和攻击者都可以准备k-r预运算表，攻击复杂度就是查表的复杂度Schnorr签名：选择随机整数r，0<r<q，计算x=armodp。计算e=H(M||x)计算y=(r+se)modqr的泄露会导致私钥s泄露x未直接公开，攻击者从e不能获知x，无法从r-x的预运算表得到关于r的信息ECC数字签名（ECDSA）共享GF(p)上的椭圆曲线E(a,b)，基点G及其阶n；私钥d；公钥Q=dG签名：任选k,1<k<n计算kG=(x1,y1),r=x1，若r=0则返回第一步重选k解方程ks=m+drmodn则m的签名为(r,s)验证：检查是否0<r,s<n计算w=s-1modn计算t1=mwmodn,t2=rwmodn计算t1G+t2Q=(x0,y0),v=x0modn若v=r，则签名被认可证明：t1G+t2Q=w(mG+rQ)=s-1(m+dr)G=[k-1(m+dr)]-1(m+dr)G=kGECC数字签名（ECDSA）若r=0则k只能是一个定值，可以由ks=m解出那么任何人都可以为消息m'伪造签名(0,m'k-1

modn)与ElGamal数字签名类似：k不能被泄露，否则私钥可以被解出k不能被重复使用（可以通过观察r发现），两次的方程联立可解出私钥若s为零，则应更换k重新计算。否则私钥可以被解出kG=(x1,y1),r=x1ks=m+drmodn基于SM2的数字签名共享GF(p)上的椭圆曲线E(a,b)，基点G及其阶n；私钥d；公钥P=dG签名：计算e=H(ZA||M)，其中ZA是用户A的标识、a、b、G、PA构成的串任选k，1<k<n计算kG=(x1,y1),r=x1+emodn，若r=0或r+k=n则返回第2步重选k计算s=(1+dA)-1(k-rdA)modn，若s=0则返回第2步重选k则m的签名为(r,s)验证：若r、s不属于[1,n-1]，则验证不通过计算e=H(ZA||M)计算t=r+smodn，若t=0则验证不通过计算sG+tPA=(x1,y1)计算v=e+x1，若v=r，则验证通过，否则验证不通过证明：

基于SM2的数字签名讨论：若r=0则s=(1+dA)-1kmodn若存在多个r=0的签名，则(1+dA)-1

是这些签名中s的最大公约数，可能导致私钥泄露若s=0k=rdA

modn，若存在多个s=0的签名，可能导致私钥泄露若r+k=n则s=(1+dA)-1(-r-rdA)=-r=n-rmodn，此时r+s=0modn此时s与dA无关，任何人可以伪造签名若k被泄露，则由s可以解出私钥kG=(x1,y1),r=x1+emodns=(1+dA)-1(k-rdA)modn数字签名标准DSS美国国家标准与技术协会(NIST)发布的FIPS186，被称为数字签名标准(DSS)1991年提出，1993年、1996年两次修改，2000年发布FIPS186-2，2007年发布FIPS

186-3DSS指标准,DSA指算法使用了安全散列算法SHA是ElGamal方案和Schnorr方案的改进典型签名长度320bits安全性依靠离散对数求解难题DSS签名与RSA签名的比较PUG为一组用户共有的参数，称为全局公钥k是随机数，每次签名都不一样DSA密钥产生全局公钥(p,q,g):选择大素数p，2L-1<p<2L

其中L在1024到2048之间，是64的倍数q是p-1的素因子，2159<q<2160令g=h(p-1)/q其中1<h<p-1，h(p-1)/q(modp)>1即g模p的阶是q用户密钥选择私钥x<q计算公钥y=gx(modp)DSA签名与验证签名：r=f2(k,p,q,g)=(gkmodp)modqs=f1(H(M),k,x,r,q)=k-1(H(M)+xr)modq验证：w=f3(s',q)=(s')-1modqv=f4(y,q,g,h(M'),w,r')=((g(H(M')w)modqyr'wmodq)modp)modqDSA证明r=f2(k,p,q,g)=(gkmodp)modqs=f1(H(M),k,x,r,q)=k-1(H(M)+xr)modqw=f3(s',q)=(s')-1modqv=f4(y,q,g,h(M'),w,r')=((g(H(M')w)modqyr'wmodq)modp)modq证明：s'=s,M'=M,r'=r w=(s)-1modq=(k-1(H(M)+xr))-1modq∴wk-1(H(M)+xr)=1modq w(H(M)+xr)=kmodq∴v=((g(H(M)w)modqyrwmodq)modp)modq =((g(H(M)w)modqgxrwmodq)modp)modq =((g(H(M)+xr)wmodq)modp)modq =(gkmodp)modq =rDSA签名r=f2(k,p,q,g)=(gkmodp)modqs=f1(H(M),k,x,r,q)=k-1(H(M)+xr)modq与ElGamal数字签名类似：k不能被泄露，否则私钥可以被解出k不能被重复使用（可以通过观察r发现），两次的方程联立可解出私钥若s为零，则应更换k重新计算，否则私钥可以被解出数字签名数字签名的实现公钥密码的密钥管理数字签名算法与协议密钥长度公开密钥算法的安全性基于计算困难问题大数因子分解算法的发展比数学家的预计还要快1983年，分解71位的数据需要0.1mips-year1994年，分解129位的数据需要5000mips-year预测大数分解能力是非常困难的当前，RSA公钥密码民用一般取1024～2048位，政府往往取2048位或4096位非数学的大数分解方法DNA技术：利用DNA链来求解NP困难问题图的哈密尔顿环问题：结点由一段DNA分子表示每条边也用一段DNA分子表示，分子两端可以与相应的结点分子相连制备大量分子，充分反应后，利用重力析解出特定的分子链量子技术可以解决某些NP问题威胁基于大数分解或离散对数的密码系统2008年，分解21相同安全强度下非对称密码与对称密码的密钥长度密码系统的安全性由最薄弱环节决定选择安全强度相当的密钥长度应注意，安全强度是随时间变化的密钥长度随着运算能力的增加而增加——对称密钥密钥长度随着算法的改进而增加——公开密钥对称密钥5680112128192256RSA密钥512102420483072768015360ECC密钥112161224256384512公钥密码系统的密钥分配公钥的管理/分配方法：公开发布公开可访问目录公钥授权公钥证书公钥的公开发布用户直接将公钥发送给另一方，或进行广播通知例如：将PGP密钥附在邮件上或发布给新闻组/邮件组主要弱点是可以被伪造假冒者可以冒充用户A，将公钥公开发布在用户A发现，并通知所有人之前，假冒者可以解读所有发往A的消息公钥的公开可访问目录在一个公开可访问目录下注册公钥提供更高的安全性该目录应由可信实体或组织负责，内容包括：包括条目｛姓名，公钥｝公钥的注册必须亲自进行，或通过安全认证的通信进行用户可以在任何时刻更新公钥该目录应定期更新该目录可以通过网络访问仍有被假冒的风险目录管理员的密钥泄漏管理目录的服务器被攻破公钥授权由公钥授权中心来分发公钥可以更严格的控制目录中的密钥分配每个用户拥有管理员的公钥管理员成为系统安全性的瓶颈获取Bob公钥获取Alice公钥双向身份认证公钥证书证书内容用认证中心CA（或其他可信第三方）的私钥进行签名证书将用户身份与公钥绑定在一起通常还包括：有效期、权限等信息公钥证书使得传输公钥时不需要与公钥授权中心的实时连接任何知道CA公钥的用户都可以对证书进行验证获取自己公钥证书获取自己公钥证书交换证书注意，这里没有认证对方身份公钥证书公钥证书满足如下条件：任何通信方可以读取证书，确定证书拥有者的姓名和公钥任何通信方可以验证证书出自证书管理员只有证书管理员可以产生并更新证书对于申请者A，管理员提供的证书为：CA=

E(PRauth,T||IDA||PUa)，T是时间戳其他人读取并验证：D(PUauth,CA)=T||IDA||PUaX.509认证服务ITU-T建议书中X.500系列中定义目录服务的部分定义了认证服务框架存储公钥证书的目录公钥证书由CA签发定义了认证协议是基于公钥密码体制和数字签名的服务X.509：证书证书制作证书格式版本号序列号证书签名算法发行商有效期用户名用户公钥信息发行商ID用户ID扩展域证书签名值X.509：证书链与证书的获取公钥证书可公开存放每个CA目录中包含两种证书前向证书：其他CA生成的X的证书后向证书：X生成的其他CA的证书利用证书链验证其它CA签名的证书例：A获取B的公钥证书X<<W>>

W<<V>>

V<<Y>>

Y<<Z>>

Z<<B>>X.509：泄漏密钥处理对称密码系统的密钥丢失，需要立即通知通信对方公钥密码中私钥丢失，麻烦大了通知所有人要尽可能确定泄漏发生的时间如何证明泄漏发生的时间，用于仲裁？最好在不同用途上使用不同的密码，减少损失X.509：证书的撤销未到有效期而撤销用户私钥被认为不安全用户不再信任该CACA证书被认为不安全证书撤销表CRL如何有效管理、查找撤销列表？X.509

v3基本特性多算法支持报文摘要：SHA256加密签名：RSA、DSA持钥者密钥对类型：RSA密钥、DSA签名密钥、D-H交换密钥、KEA密钥、ECDSA密钥多种命名机制E-mail地址、IPv4/v6地址、DNS、URL限制证书(公钥)的用途签名、无否认、密钥加密、密钥协商、数据加密、证书签发、CRL签发定义证书遵循的策略证书链的处理公钥基础设施RFC2822（互联网安全术语）定义：PKI系统(PublicKeyInfrastructure)是由硬件、软件、人、策略和相应处理构成的一整套体系。用来创建、管理、存储、分发和撤销数字证书提供网络信息安全服务，保证用户安全、便捷、高效地获取公钥互联网工程任务组(IETF)的PKIX工作组在

X.509基础上建立了一个基本模型，包括：端实体认证机构(CA)：生成、发放证书，

也承担部分管理任务注册机构(RA)：承担部分管理任务证书撤销列表(CRL)发布点证书存取库密钥备份、恢复、历史档案利用公钥密码分配对称密钥获得公钥后，可用于加密、认证等工作公钥密码算法计算量大、速度慢，不适用于大数据量的实时加密公钥密码通常用于管理会话密钥，即用公/私钥作为主密钥用对称密码加密数据，会话密钥一般使用对称密钥有多种协议用于协商会话密钥简单的密钥交换协议Merkle于1979年提出：A产生临时公私钥对，将公钥和她的ID发送给BB产生会话密钥K，并用A提供的公钥加密，并发给AA解密获得会话密钥，舍弃临时公私钥对中间人攻击E干扰密钥交换并窃取会话密钥后，不必再干扰AB的正常通信，可以任意窃听公钥证书有助于抵抗中间人攻击未确认对方身份AEBPUa||IDaPUe||IDeEPUe(K)EPUa(K)具有保密和认证的密钥分配这里假设Alice和Bob已获得对方公钥A发出请求A确认BB确认A传递会话密钥混合密钥分配使用KDCKDC与每个用户间共享一个秘密的主密钥使用主密钥来分配会话密钥公钥用于分发主密钥当用户分布比较分散时特别有效主要考虑：性能：需要频繁更换会话密钥时，公钥算法的计算量会影响系统性能。在混合系统中，KDC只偶尔更新主密钥兼容性：易于应用到传统KDC系统中Diffie-Hellman密钥协商协议Diffie和Hellman于1976提出的首次利用公钥算法实现密钥分配轶闻：Williamson(UKCESG)于1970年已在机密文件中提出了该算法，并用于开发商业产品D-H协议用于安全协商密钥不能用于交换确定消息可用于建立仅有通信双方知道的共享密钥实现基于有限域上的指数运算——容易安全性依赖于离散对数运算——困难DLP，CDH和DDH问题DLP难题：离散对数难题给定域G和生成元g，已知h=ga，寻找aCDH难题：计算D-H难题给定G和生成元g，已知ga与gb，寻找gabDDH难题：区分D-H难题给定G和生成元g，已知ga与gb，区分gab和gc

，a、b、c都是随机的若DLP可解，则CDH可解：DLP难度>=CDH难度若CDH可解，则DDH可解：CDH难度>=DDH难度Diffie-Hellman密钥协商协议双方设定公共参数：大素数或素多项式q、模q的本原根α双方（例如用户A）各自产生自己的公私钥选择私钥：XA<q计算公钥：YA=αXAmodq，并公开YA双方获得对方公钥，再分别计算会话密钥KABKAB=αXAXBmodq =YAXBmodq(B的运算) =YBXAmodq(A的运算)用户需要更新公私钥，以产生新的会话密钥安全性：攻击者必须解离散对数问题例：用户A和B交换密钥：公共参数q=353及

α=3选择随机私钥： A选择XA=97，B选择XB=233计算公钥： A：YA=397mod353=40 B：YB=3233mod353=248计算共享会话密钥： A：KAB=YBXAmod353

=24897

mod353=160 B：KAB=YAXBmod353

=40233

mod353=160Diffie-Hellman协议的中间人攻击E与A共享会话密钥：αXA·XE2E与B共享会话密钥：αXB·XE1在AB通信期间，E需要持续的截获、解密、重加密使用数字签名或公钥证书有助于抵抗中间人攻击AEBαXAαXE1αXE2αXBHughes对Diffie-Hellman协议的修改某些场合下，需要通信一方预先设定密钥Hughs：A可以事先生成密钥，而B可以通过接收到的数据计算出该密钥A:K=αXAmodPB:Y=αXB

modP

AA:X=YXA

modP=αXAXB

modP

BB:x'B=xB-1,K'=XX'BmodP=αXAmodP=KDiffie-Hellman协议的椭圆曲线实现D-H协议：素数p，本原根gECC实现：选定椭圆曲线Ep(a,b)，及基点G，n是G的阶A、B分别随机选取a<n、b<n并保密。A=gamodpB=gbmodp共享秘密S=Ab=Ba=gabmodpA=aGmodpB=bGmodp共享秘密Q=bA=aB=abGMTI密钥协商协议

加密密钥交换协议EKEStevesBellovin和Michael