《第11章 密码协议》由会员分享，可在线阅读，更多相关《第11章 密码协议（81页珍藏版）》请在金锄头文库上搜索。
1、第11章 密码协议 概述 密钥分配与密钥协商 秘密共享 身份识别 零知识证明 不经意传输习题防止重 放攻击密钥确 证这里TA不同于在线密 钥分配中的TA，他只 负责初始化时发放证 书，以及必要时的纠 纷处理，一般情况下 的密钥协商过程不需 要TA参与。每个用户的证书C(U) 实际上是此用户的一 个可信的（经可信第 三方“盖章”的）验证 签名算法。注：总假 设证书发放时TA会验 明身份，不存在冒充W无法伪造U和V的签 名，因此不能成功实 施中间人攻击实际上求密钥只需要将前面三 式中的常数项相加即可u相当于是代表自 己身份的密钥， 不可泄露出去仍假设发放证书时不 存在假冒。即保证证 书中的v一定是
2、A提 供给TA的这个证书说明：TA 能保证(只有)真正的 A有v的离散对数u识别思路？ A向B证明他知道u的值零知识洞穴 Quisquater和Guillou给出了一个非常形象的例子来解释零知 识证明。在洞穴深处的位置C和位置D之间有一道门，只有知道秘密咒 语的人才能打开它。假设P知道打开门的咒语，P想向V证明自 己知道咒语，但又不想向V泄露咒语。P可以利用下列协议来 达到这个目的：协议如下： B选择p、q，计算n=pq；再选取满足 的随机数a，将n和a发送给A。 A猜测a是模n的平方剩余或非平方剩余，并将 结果告诉B。 B告诉A猜测正确或不正确，并将p、q发送给 A A检查p、q都是素数且n
3、=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是否收到了这个秘密。这种协议就称为不经意传输协议。不经意传输1. 基于大数分解问题的不经意传输协议设A想通过不经意传输协议传递给B的秘密是 整数n（为两个大素数之积）的因数分解。这个问 题具有普遍意义，因为任何秘密都可通过RSA加密 ，得到n的因数分解就可得到这个秘密。
4、协议基于如下事实： 已知某数在模n下两个不 同的平方根，就可分解n。协议如下： B随机选一数x，将x2 mod n发送给A。 A（掌握n=pq的分解）计算x2 mod n的4个平 方根x和y，并将其中之一发送给B。由于A只知道x2 mod n，并不知道4个平方根中哪一个是 B 选的x。 B检查第步收到的数是否与x在模n下同余 ，如果是，则B没有得到任何新信息；否则B就 掌握了x2 mod n的两个不同的平方根，从而能够 分解n。而A却不知究竟是哪种情况。显然，B得到n的分解的概率是1/2。2. 基于离散对数问题的不经意传输协议下一个不经意传输协议是非交互的，其中B不 向A发送任何消息。设系统中
5、所有用户都知道一个大素数p、GF(p) -0的生成元g和另一大素数c，但无人知道c的离散 对数。假定计算离散对数是不可行的，因此从gx mod p和gy mod p无法计算gxy mod p。协议中所有运算都在GF(p)中进行。B按如下方式产生公开的加密密钥和秘密的解 密密钥： 随机选取一个比特i和一个数x(0xp-2)，计算yi=gx, y1-i=c(gx)-1，以(y0, y1)作为公开的加密密钥，以(i, x)作为秘密解密密钥。由于B不知道c的离散对数，所以他知道y0和y1 两者其中一个的离散对数，而A无法知道y0和y1中 哪个离散对数是B已知的。A可通过方程y0y1=c来检查B的公开加
6、密密钥是否正确。协议中设A的两个秘密s0和s1是二进制数， 是 异或运算，若进行异或运算的两个数不等长，可在 较短数前面补0。协议如下： A在0到p-2之间随机取两个整数k0、k1，对 j=0,1计算 将c0, c1, m0, m1 发送给B。 B用自己的秘密解密密钥计算 。由于B不知道y1-i的离散对数，所以 无法得到d1-i和s1-i。注：本协议相当于“二传一”不经意传输。若其中一个为 有效秘密一个为空，则成为前一种不经意传输。3. “多传一”的不经意传输协议设A有多个秘密，想将其中一个传递给B，使 得只有B知道A传递的是哪个秘密。设A的秘密是 s1,s2,sk，每一秘密是一比特序列。协议
7、如下： A告诉B一个单向函数f，但对f -1保密。 设B想得到秘密si，他在f的定义域内随机选取 k个值x1,x2,xk，将k元组(y1,y2,yk)发送给A，其 中 A计算zj=f -1(yj)(j=1,2,k)，并将 zj sj(j=1,2,k)发送给B。 由于zi=f -1(yi)=f -1(f(xi)=xi，所以B知道zi，因 此可从zisi获得si。由于A不知k元组(y1,y2,yk)中哪个是f(xi)，因 此无法确定B得到的是哪个秘密。然而如果B不遵守协议，他用f对多个xj求得 f(xj)，就可获得多个秘密。因此总假定这种“多传 一”协议中所有用户都遵守协议。4. 基于大数分解问题
8、的“多传一”不经意传输协议设A有多个秘密，并对自己的每个秘密都使用 一个不同的RSA体制加密，A要想向B传递其中的 一个秘密，就可告诉B加密该秘密的RSA体制模数的分解。协议如下： A构造k个RSA加密体制，使得在每个体制中 的两个素数pj和qj满足pjqj3 mod 4（这样可保证 同一数a在模nj=pjqj下的两个平方根有相反的Jacobi 符号），将加密密钥(ej , nj)及加密后的秘密发送给B，其中j=1,2,k。 B选k个数x1,x2,xk，分别计算Jacobi符号 和x2j mod nj （j=1,2,k）。B如果想获得秘密si，则将x2i mod ni和 发送给A，而对所有ji
9、，将x2j mod nj和 发送给A。 对每一j，A计算x2j mod nj的平方根和平方根 的Jacobi符号，比较每一平方根的Jacobi符号是否 与第步收到的Jacobi符号相同，将Jacobi符号相 同的那一平方根发送给B。 B现在获得x2i mod ni的两个不同的平方根，因 此能够分解ni，求出解密密钥di，进一步求出si；而 对ji，B在第步收到的平方根是自己已知的，因 此无法求出nj和sj。因为A不知道B选择的是哪个i，因此不知道B获 得的是哪个秘密。协议中仍假定A、B都遵守协议 ，否则B在第步进行欺骗的话，A仍无法识别。例7.7 在上述协议中，设A用于加密某个秘密s的RSA体
10、制的模数n=2773=4759，满足47593 mod 4。B在第步选择的相应x=2001，计算x2 mod n=20012 mod 2773=2562及如果B想获得s，则将(2562,1)发送给A第步，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。第步，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未收到任何新信息。
