密码学第11章-密码协议课件

第,11,章 密码协议,概述,密钥分配与密钥协商,秘密共享,身份识别,零知识证明,不经意传输,习题,第11章 密码协议 概述,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,防止重,放攻击,密钥确证,防止重密钥确证,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,这里,TA,不同于在线密钥分配中的,TA,，他只负责初始化时发放证书，以及必要时的纠纷处理，一般情况下的密钥协商过程不需要,TA,参与。,每个用户的证书,C(U),实际上是此用户的一个可信的（经可信第三方“盖章”的）验证签名算法。,注：总假设证书发放时,TA,会验明身份，不存在冒充,这里TA不同于在线密钥分配中的TA，他只负责初始化时发放证书,密码学第11章-密码协议课件,密码学第11章-密码协议课件,W,无法伪造,U,和,V,的签名，因此不能成功实施中间人攻击,W无法伪造U和V的签名，因此不能成功实施中间人攻击,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,实际上求密钥只需要将前面三,式中的常数项相加即可,实际上求密钥只需要将前面三,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,u,相当于是代表自己身份的密钥，不可泄露出去,仍假设发放证书时不存在假冒。即保证证书中的,v,一定是,A,提供给,TA,的,这个证书说明：,TA,能保证,(,只有,),真正的,A,有,v,的离散对数,u,识别思路？,A,向,B,证明他知道,u,的值,u相当于是代表自己身份的密钥，不可泄露出去仍假设发放证书时不,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,零知识洞穴,Quisquater,和,Guillou,给出了一个非常形象的例子来解释零知识证明。,在洞穴深处的位置,C,和位置,D,之间有一道门，只有知道秘密咒语的人才能打开它。假设,P,知道打开门的咒语，,P,想向,V,证明自己知道咒语，但又不想向,V,泄露咒语。,P,可以利用下列协议来达到这个目的：,零知识洞穴在洞穴深处的位置C和位置D之间有一道门，只有知道秘,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,密码学第11章-密码协议课件,协议如下：,B,选择,p,、,q,，,计算,n,=,pq,；,再选取满足,的随,机数,a,，,将,n,和,a,发送给,A。, A,猜测,a,是模,n,的平方剩余或非平方剩余，并将结,果告诉,B。, B,告诉,A,猜测正确或不正确，并将,p,、,q,发送给,A, A,检查,p,、,q,都是素数且,n,=,pq,。,显然，,A,猜中的概率是1/2。协议执行完后，,A,根据,p,、,q,可求出,a,mod,n,的4个平方根（如果,a,是模,n,的平方剩余），以检查,B,是否在,A,猜测完后将结果做了修改。,协议如下：,设,A,有一个秘密，想以1/2的概率传递给,B，,即,B,有50%的机会收到这个秘密，另外50%的机会什么也没有收到，协议执行完后，,B,知道自己是否收到了这个秘密，但,A,却不知,B,是否收到了这个秘密。这种协议就称为不经意传输协议。,不经意传输,设A有一个秘密，想以1/2的概率传递给B，即B有50,1. 基于大数分解问题的不经意传输协议,设,A,想通过不经意传输协议传递给,B,的秘密是整数,n,（,为两个大素数之积）的因数分解。这个问题具有普遍意义，因为任何秘密都可通过,RSA,加密，得到,n,的因数分解就可得到这个秘密。,协议基于如下事实： 已知某数在模,n,下两个不同的平方根，就可分解,n,。,1. 基于大数分解问题的不经意传输协议,协议如下：,B,随机选一数,x,，,将,x,2,mod,n,发送给,A。, A（,掌握,n,=,pq,的分解）计算,x,2,mod,n,的4个平方,根,x,和,y,，,并将其中之一发送给,B。,由于,A,只,知道,x,2,mod,n,，,并不知道4个平方根中哪一个是,B,选的,x,。, B,检查第步收到的数是否与,x,在模,n,下同余，,如果是，则,B,没有得到任何新信息；否则,B,就掌,握了,x,2,mod,n,的两个不同的平方根，从而能够分,解,n,。,而,A,却不知究竟是哪种情况。,显然，,B,得到,n,的分解的概率是1/2。,协议如下：,2. 基于离散对数问题的不经意传输协议,下一个不经意传输协议是非交互的，其中,B,不向,A,发送任何消息。,设系统中所有用户都知道一个大素数,p,、GF(,p,)-0,的生成元,g,和另一大素数,c,，,但无人知道,c,的离散对数。,假定计算离散对数是不可行的，因此从,g,x,mod,p,和,g,y,mod,p,无法计算,g,xy,mod,p,。,协议中所有运算都在,GF(,p,),中进行。,2. 基于离散对数问题的不经意传输协议,B,按如下方式产生公开的加密密钥和秘密的解密密钥：,随机选取一个比特,i,和一个数,x,(0,x,p,-2)，,计算,y,i,=g,x,y,1-,i,=c,(,g,x,),-1,，,以(,y,0,y,1,),作为公开的加密密钥，以(,i,x,),作为秘密解密密钥。,由于,B,不知道,c,的离散对数，所以他知道,y,0,和,y,1,两者其中一个的离散对数，而,A,无法知道,y,0,和,y,1,中哪个离散对数是,B,已知的。,A,可通过方程,y,0,y,1,=,c,来检查,B,的公开加密密钥是否正确。,B按如下方式产生公开的加密密钥和秘密的解密密钥：,协议中设,A,的两个秘密,s,0,和,s,1,是二进制数，是异或运算，若进行异或运算的两个数不等长，可在较短数前面补0。,协议如下：,A,在0到,p,-2,之间随机取两个整数,k,0,、,k,1,，,对,j,=0,1,计算,将,c,0,c,1,m,0,m,1,发送给,B。, B,用自己的秘密解密密钥计算,。,由于,B,不知道,y,1-,i,的离散对数，所以无法得到,d,1-,i,和,s,1-,i,。,注：本协议相当于“二传一”不经意传输。若其中一个为有效秘密一个为空，则成为前一种不经意传输。,协议中设A的两个秘密s0和s1是二进制数，是异或运,3. “多传一”的不经意传输协议,设,A,有多个秘密，想将其中一个传递给,B，,使得只有,B,知道,A,传递的是哪个秘密。设,A,的秘密是,s,1,s,2,s,k,，,每一秘密是一比特序列。协议如下：,A,告诉,B,一个单向函数,f,，,但对,f,-1,保密。, 设,B,想得到秘密,s,i,，,他在,f,的定义域内随机选取,k,个值,x,1,x,2,x,k,，,将,k,元组(,y,1,y,2,y,k,),发送给,A，,其中,3. “多传一”的不经意传输协议,A,计算,z,j,=,f,-1,(,y,j,)(,j,=1,2,k,)，,并将,z,j,s,j,(,j,=1,2,k,),发送给,B。,由于,z,i,=,f,-1,(,y,i,)=,f,-1,(,f,(,x,i,)=,x,i,，,所以,B,知道,z,i,，,因此可从,z,i,s,i,获得,s,i,。,由于,A,不知,k,元组(,y,1,y,2,y,k,),中哪个是,f,(,x,i,)，,因此无法确定,B,得到的是哪个秘密。,然而如果,B,不遵守协议，他用,f,对多个,x,j,求得,f,(,x,j,)，,就可获得多个秘密。因此总假定这种“多传一”协议中所有用户都遵守协议。, A计算zj=f -1(yj)(j=1,2,k)，并将,4. 基于大数分解问题的“多传一”不经意传输协议,设,A,有多个秘密，并对自己的每个秘密都使用一个不同的,RSA,体制加密，,A,要想向,B,传递其中的一个秘密，就可告诉,B,加密该秘密的,RSA,体制模数的分解。协议如下：,A,构造,k,个,RSA,加密体制，使得在每个体制中的两个素数,p,j,和,q,j,满足,p,j,q,j,3 mod 4（,这样可保证同一数,a,在模,n,j,=p,j,q,j,下的两个平方根有相反的,Jacobi,符号），将加密密钥(,e,j, n,j,),及加密后的秘密,发送给,B，,其中,j,=1,2,k,。,4. 基于大数分解问题的“多传一”不经意传输协议,B,选,k,个数,x,1,x,2,x,k,，,分别计算,Jacobi,符号,和,x,2,j,mod,n,j,（,j,=1,2,k,）。B,如果想获得秘密,s,i,，,则将,x,2,i,mod,n,i,和 发送给,A，,而对所有,j,i,，,将,x,2,j,mod,n,j,和,发送给,A。,对每一,j,，A,计算,x,2,j,mod,n,j,的平方根和平方根的,Jacobi,符号，比较每一平方根的,Jacobi,符号是否与第步收到的,Jacobi,符号相同，将,Jacobi,符号相同的那一平方根发送给,B。, B,现在获得,x,2,i,mod,n,i,的两个不同的平方根，因此能够分解,n,i,，,求出解密密钥,d,i,，,进一步求出,s,i,；,而对,ji,，B,在第步收到的平方根是自己已知的，因此无法求出,n,j,和,s,j,。, B选k个数x1,x2,xk，分别计算Jacobi符号,因为,A,不知道,B,选择的是哪个,i,，,因此不知道,B,获得的是哪个秘密。协议中仍假定,A、B,都遵守协议，否则,B,在第步进行欺骗的话，,A,仍无法识别。,因为A不知道B选择的是哪个i，因此不知道B获得的是哪个秘密。,例7.7 在上述协议中，设,A,用于加密某个秘密,s,的,RSA,体制的模数,n,=2773=4759，,满足47593,mod 4。B,在第步选择的相应,x,=2001，,计算,x,2,mod,n,=2001,2,mod 2773=2562,及,如果,B,想获得,s,，,则将(2562,1)发送给,A,例7.7 在上述协议中，设A用于加密某个秘密s的RSA体制的,第步，,A,如下计算2562,mod 2773,的平方根：,求2562,mod 47=24, 2562 mod 59=25，,求出24在,mod 47,时的平方根为27，25在,mod 59,时的平方根为5,，,由中国剩余定理求出平方根为2759454754，即349，772，2001，2424。,因 ，,A,将349或,2424发送给,B。,第步，A如下计算2562 mod 2773的平方根：,第步，,B,由,gcd2773, 349+2001=47,或,gcd2773, 2424-2001=47,得,n,的一个因子，从而得到,n,的分解式4759。若,B,不想获得,s,，,则将(2562,-1)发送给,A，A,将772或2001发送给,B，,因7722001,mod 2773，,所以,B,未收到任何新信息。,第步，B由 gcd2773, 349+2001=47,