第7章数字签字和密码协议zhp.doc

第7章数字签字和密码协议zhp 数字签名由公钥密码发展而来，它在网络安全，包括身份认证、数据完整性、不可否认性等方面有着重要的应用。 数字签名的目的是提供一种手段，使得一个实体把他的身份与某个信息捆绑在一起。 一个消息的数字签名实际上是一个数，它仅仅依赖于签名者知道的某个秘密，也依赖于被签名信息的本身。 与消息加密不同点消息加密和解密可能是一次性的，它要求在解密之前是安全的；而一个签名的消息可能作为一个法律上的文件，如合同等，很可能在对象签署多年之后才验证其签字，且可能需要多次验证此签名。 第第7章数字签字和密码协议7.1数字签字的基本概念7.2数字签字标准7.3其他签字方案7.4认证协议7.5身份证明技术7.6其他密码协议习题消息认证保护通信双方遭受第三方的攻击，但不能保护通信双方中的一方防止另一方的欺骗或伪造。 通信双方之间也可能有多种形式的欺骗.7.1数字签字的基本概念7.1.1数字签字应满足的要求数字签名的安全要求签名是可以被验证的。 能够验证签字产生者的身份，以及产生签字的日期和时间。 能用于证实被签消息的内容。 签名是不可抵赖的的签名者事后不能抵赖对消息的签名，出现争议时，数字签字可由第三方验证，从而能够解决通信双方的争议。 数学签名算法应满足的要求签字的产生必须使用发方独有的一些信息以防伪造和否认。 同时，要求保证独有的一些信息的安全性。 签字的产生应较为容易。 签字的识别和验证应较为容易。 对已知的数字签字构造一新的消息或对已知的消息构造一假冒的数字签字在计算上都是不可行的。 数字签字的产生可用加密算法或特定的签字算法。 1.由加密算法产生数字签字利用加密算法产生数字签字是指将消息或消息的摘要加密后的密文作为对该消息的数字签字.7.1.2数字签字的产生方式 (1)单钥加密发送方A根据单钥加密算法以与接收方B共享的密钥钥K对消息M加密后的密文作为对M的数字签字发往B。 (2)公钥加密发送方A使用自己的秘密钥SK A对消息M加密后的密文作为对M的数字签字，B使用A的公开钥PK A对消息解密，由于只有A才拥有加密密钥SK A，因此可使B相信自己收到的消息的确A。 由加密算法产生数字签字又分为外部保密方式和内部保密方式，外部保密方式是指数字签字是直接对需要签字的消息生成而不是对已加密的消息生成，否则称为内部保密方式。 外部保密方式便于解决争议，因为第33方在处理争议时，需得到明文消息及其签字。 但如果采用内部保密方式，第33方必须得到消息的解密密钥后才能得到明文消息。 如果采用外部保密方式，接收方就可将明文消息及其数字签字存储下来以备以后万一出现争议时使用。 2.由签字算法产生数字签字签字算法的输入是明文消息M和密钥x，输出是对M的的数字签字，表示为S=Sig x(M)。 相应于签字算法，有一验证算法，表示为Ver x(S,M)，其取值为算法的安全性在于从M和S难以推出密钥x或伪造一个消息M使M和S可被验证为真。 ?,xxxTrue S Sig MVerS MFalseSSigM?1.直接数字签名直接方式是指数字签字的执行过程只有通信双方参与，并假定双方有共享的秘密钥或接收一方知道发方的公开钥。 弱点签名的有效性依赖于发送方秘钥的安全性7.1.3数字签字的执行方式2.具有仲裁方式的数字签字引入一个可信的第三方作为数字签名系统的仲裁者来解决直接数字签名的问题。 发方X对发往收方Y的消息签字后，将消息及其签字先发给仲裁者A，A对消息及其签字验证完后，再连同一个表示已通过验证的指令一起发往收方Y。 此时由于A的存在，X无法对自己发出的消息予以否认。 可仲裁数字签名的实现方案X表示发方，Y表示收方，A是仲裁者，M是消息，XYM表示X给Y发送一消息M。 对称密钥加密，不提供保密性XA ME KXAID XH(M)。 AY E KAYID XME KXAID XH(M)T。 其中E是单钥加密算法，K XA和和K AY分别是X与A共享的密钥和和A与Y共享的密钥，H(M)是M的杂凑值，T是时戳，ID X是是X的身份。 由于Y不能直接检查X的签字，但Y认为消息于A因而是可信的。 这种方案A必须取得X和Y的高度信任?X相信A不会泄露K XA，并且不会伪造X的签字;?Y相信A只有在对E KAYID XME KXAID XH(M)中的杂凑值及X的签字验证无误后才将之发给Y;?X，Y都相信A可公正地解决争议。 如果A已取得各方的信任，则X就能相信没有人能伪造自己的签字，Y就可相信X不能对自己的签字予以否认。 对称密钥加密，提供保密性XA:ID XE KXYME KXAID XH(E KXYM)。 AY:E KAYID XE KXYME KXAID XH(EKXYM)T。 问题仲裁者可和发方共谋以否认发方曾发过的消息，也可和收方共谋以伪造发方的签字。 公钥加密，提供保密性XA ID XE SKXID XE PKYE SKXM。 AY E SKAIDXE PKYESKXMT。 优点?通信之前各方无须共享任何信息，可防止共谋。 ?只要仲裁者的秘密钥没有被泄露，任何人包括发送方都不能伪造时戳T，不能发送重放消息。 ?消息对任何第三方（包括A）都是保密的。 数字签字标准DSS(Digital SignatureStandard)是由美国国NIST公布的联邦信息处理标准FIPS PUB186，其中采用了上一章介绍的SHA和一新的签字技术，称为DSA(Digital SignatureAlgorithm)。 DSS最初于1991年公布，在考虑了公众对其安全性的反馈意见后，于1993年公布了其修改版。 7.2数字签字标准首先将DSS与RSA的签字方式做一比较。 RSA算法既能用于加密和签字，又能用于密钥交换。 与此不同，DSS使用的算法只能提供数字签字功能。 7.2.1DSS的基本方式基于离散对数问题的数字签字体制是数字签字体制中最为常用的一类，其中包括ElGamal签字体制、DSA签字体制、Okamoto签字体制等。 数字签名方案基于离散对数问题的数字签字体制DSA是在ElGamal和Schnorr两个签字方案(见下一节)的基础上设计的，其安全性基于求离散对数的困难性。 （ （1）体制参数?全局公开钥p满足2L-1 q p-1的素因子，满足2159 g gh(p-1)/q mod p，其中h是满足11的任一整数。 ?用户秘密钥x:x是满足0 ?用户的公开钥y:yg x mod p。 签名者的公钥为(p,q,g,y),私钥为x1数字签字算法DSA (2)签字过程?为待签消息m,选取秘密数k k是满足0 (3)验证过程设接收方收到的消息为M，签字为(r,s)。 计算w(s)-1mod q,u1H(M)wmod qu2rw mod q,v(g u1y u2)mod pmod q检查，若相等，则认为签字有效。 这是因为若(M,r,s)=(M,r,s)，则则V(g(H(M)w)mod qy rw mod q)mod pmod qg(H(M)+xr)w)mod qg(H(M)+xr)k(H(M)+xr)-1)mod qr sf1H(M),k,x,r,qk-1(H(M)+xr)mod qr=f2(k,p,q,g)(g kmod p)mod qw=f3(s,q)(s)-1mod qv=f4(y,q,g,H(M),w,r)(g(H(M)w)mod qy rw mod q)mod pmod q由于离散对数的困难性，敌手从r恢复k或从s恢复x都是不可行的。 还有一个问题值得注意，即签字产生过程中的运算主要是求求r的模指数运算r=(g kmod p)modq，而这一运算与待签的消息无关，因此能被预先计算。 事实上，用户可以预先计算出很多r和k-1以备以后的签字使用，从而可大大加快产生签字的速度。 2.ElGamal签字体制 (1)体制参数p大素数；g Z*p的一个生成元；x用户A的秘密钥，xR Z*p；y用户A的公开钥，yg x(mod p)。 (2)签字的产生过程:对于待签字的消息m，A执行以下步骤计算m的杂凑值H(m)。 选择随机数k kZ*p，计算rg k(mod p)。 计算s(H(m)-xr)k-1(mod p-1)。 以以(r,s)作为产生的数字签字。 (3)签字验证过程接收方在收到消息m和数字签字(r,s)后，先计算H(m)，并按下式验证正确性证明()(,(,),()(mod)r s H mVer y r sHm Truey r g p?()()(mod)rs rx ksrx Hm rxH myrg g g g p?3.Schnorr签字体制 (1)体制参数p大素数，p2512；q大素数，q|(p-1)，q2160；g gR Z*p,且g q1(mod p)；x用户A的秘密钥，1 (2)签字的产生过程对于待签字的消息m，A执行以下步骤选择随机数k1 计算e=H(r,m)。 计算sxe+k(modq)。 以以(e,s)作为产生的数字签字。 (3)签字验证过程接收方在收到消息m和数字签字(e,s)后，先计算rg s y-e mod p)，然后计算H(r,m)，并按下式验证其正确性可由下式证明(,(,),)(,)Ver y e sm TrueH rm e?(mod)s exe k xe krg ygg r p?离散对数签字体制ElGamal、DSA、Okamoto等签字体制都可归结为离散对数签字体制的特例。 (1)体制参数p大素数；q p-1或p-1的大素因子；ggR Z*p，且且g q1(mod p)，其中gR Z*p表示g是从Z*p中随机选取的，其中Z*p=Z p-0；x用户A的秘密钥，1 (2)签字的产生过程对于待签字的消息m，A执行以下步骤计算m的杂凑值H(m)。 选择随机数k1 从签字方程akb+cx(modq)中解出s。 方程的系数a、b、c有许多种不同的选择方法，表7.1给出了这些可能选择中的一小部分，以(r,s)作为产生的数字签字。 (3)签字的验证过程接收方在收到消息m和签字(r,s)后，可以按照以下验证方程检验)(mod),(,(p ygrTrue msry Vercb a?1.RSA签字体制体制参数。 选两个保密的大素数p和q，计算n=pq，(n)=(p-1)(q-1)；选一整数e，满足1 签字过程。 设消息为M，对其签字为SM dmod n验证过程。 接收方在收到消息M和签字S后，验证是否成立，若成立，则发送方的签字有效。 实际应用时，数字签字是对消息摘要加密产生，而不是直接对消息加密产生。 ?modeM Sn?基于大数分解问题的数字签字体制2.Guillou-Quisquater签字体制 (1)体制参数n n=pq，p和q是两个保密的大素数；v gcd(v,(p-1)(q-1)=1；x用户A的秘密钥，xR Z*n；y用户A的公开钥，yZ*n，且且x vy1(mod n)。 (2)签字的产生过程对于待签消息m，A进行以下步骤随机选择一个数kZ*n，计算Tk v(mod n)。 计算杂凑值e=H(m,T)，且使1e 计算skx emod n。 以以(e,s)作为对m的签字。 (3)签字的验证过程接收方在收到消息m和数字签字(e,s)后，用以下步骤来验证计算出Ts vye(mod n)。 计算出e=H(m,T)。 验证正确性可由以下算式证明(,(,),)Verye sm True e e?(mod)()(mod)()(mod)(mod)v e e ve vv evTsy n kxy nkxy nkn T?安全可靠的通信除需进行消息的认证外，还需建立一些规范的协议对数据的可靠性、通信实体的真实性加以认证，以防止欺骗、伪装等攻击。 A和B是网络的两个用户，他们想通过网络先建立安全的共享密钥再进行保密通信。 那么A(B)如何确信自己正在和和B(A)通信而不是和C通信呢？这种通信方式为双向通信，因此，此时的认证称为相互认证。 类似地，对于单向通信来说，认证称为单向认证。 7.4认证协议A、B两个用户在建立共享密钥时需要考虑的核心问题是保密性和实时性。 保密性为了防止会话密钥的伪造或泄露，会话密钥在通信双方之间交换时应为密文形式，所以通信双方事先就应有密钥或公开钥。 实时性对防止消息的重放攻击极为重要，实现实时性的一种方法是对交换的每一条消息都加上一个序列号，但增加用户的负担，所以序列号方法一般不用于认证和密钥交换。 7.4.1相互认证保证消息的实时性常用以下两种方法?时戳如果A收到的消息包括一时戳，且在A看来这一时戳充分接近自己的当前时刻，A才认为收到的消息是新的并接受之。 这种方案要求所有各方的时钟是同步的。 ?询问-应答用户A向B发出一个一次性随机数作为询问，如果收到B发来的消息（应答）也包含一正确的一次性随机数，A就认为B发来的消息是新的并接受之。 1.单钥加密体制采用单钥加密体制为通信双方建立共享密钥时，需要有一个可信的密钥分配中心，网络中每一用户都与KDC有一共享的密钥，称为主密钥，KDC为通信双方建议一个短期内使用的密钥，称为会话密钥。 并用主密钥加密会话密钥分配给两个用户。 (1)Needham-Schroeder协议5.1节中图5.1所示的采用KDC的密钥分配过程，可用以下协议（称为Needham-Schroeder协议）来描述AKDC ID AID BN1KDCAE KAK SID BN1E KBK SID AAB E KBK SID A-弱点BA E KSN2AB E KSf(N2)其中N2用于向A询问K S是否为一新会话密钥，第步A对对B的询问作出应答，一方面表示自己已掌握K S，另一方面由f(N2)回答了K S的新鲜性。 (2)Needham-Schroeder协议的改进方案之一AKDC ID AID BKDCA EKAK SID BTE KBK SID ATAB E KBK SID ATBA E KSN1AB E KSf(N1)T是时戳，用以向A、B双方保证K S的新鲜性。 A和B可通过下式检查T的实时性|Clock-T| 以上协议中由于T是经主密钥加密的，所以敌手即使知道旧会话密钥，并在协议的过去执行期间截获第步的结果，也无法成功地重放给B，因因B对收到的消息可通过时戳检查其是否为新的。 存在问题方案主要依赖网络中各方时钟的同步，这种同步可能会由于系统故障或计时误差而被破坏。 如果发送方的时钟超前于接收方的时钟，敌手就可截获发送方发出的消息，等待消息中时戳接近于接收方的时钟时，再重发这个消息。 这种攻击称为等待重放攻击。 抗击等待重放攻击的方法?一种方法是要求网络中各方以KDC的时钟为基准定期检查并调整自己的时钟，?使用一次性随机数的握手协议，因为接收方向发送方发出询问的随机数是他人无法事先预测的，所以敌手即使实施等待重放攻击，也可被下面的握手协议检查出来。 (3)Needham-Schroeder协议的改进方案之二下面的协议可解决Needham-Schroeder协议以及改进方案一可能遭受的攻击AB ID AN ABKDC ID BN BE KBID AN AT BKDCA EKAID BN AK ST BE KBID AK ST BN BAB EKBID AK ST BEKSN BN A的作用是在进行密钥分发时返回给A，以保证A收到的会话密钥K S的新鲜性。 N B以后将与会话密钥一起以加密形式返回给B以向B保保证会话密钥的新鲜性作用是请求KDC向A发出一个可信证书（票据），指定了证书接收者A的的身份、B建议的证书截止时间T B、B从从A收到的一次性随机数。 由由A当作票据用于以后的认证A用这一消息可验证B已收到第步发出的消息（通过ID B），A还能验证这一步收到的消息是新的（通过N A），这一消息中还包括KDC分配的会话密钥KS以及会话密钥的截止时间T B。 N B由会话密钥加密的目的是B认认证了自己收到的消息不是一个重放放,而的确是于A。 以上协议为A、B双方建立共享的会话密钥提供了一个安全有效的手段。 A、B再次建立新的会话时，如果A保留由协议得到的票据EKBID AK ST B，就可在密钥的有效期内不再求助于认证服务器而由以下方式实现双方的新认证AB EKBID AK ST B,NABA NB，EKSNAAB EKSNBB在第步收到票据后，可通过T B检验票据是否过时，而新产生的一次性随机数NA、NB则向双方保证了没有重放攻击。 以上协议中时间期限T B是是B根据自己的时钟定的，因此不要求各方之间的同步。 2.公钥加密体制AASID AID BASA E SKASID APK ATE SKASID BPK BTAB E SKASID APK ATE SKASID BPK BTE PKBE SKAK ST会话密钥是由A选取，并以密文形式发送给B，因此包括AS在内的任何第3者都无法得到会话密钥。 时戳T用以防止重放攻击，所以需要各方的时钟是同步的。 B B的公钥证书A A的公钥证书下一协议使用一次性随机数，因此不需要时钟的同步AKDC ID AID BKDCA ESK AUID BPK BAB E PKBN AID ABKDC ID BID AE PKAUN AKDCB E SKAUID APK AEPKBE SKAUN AK SID BBA EPKAE SKAUN AK SID BN BAB EKSN BB B的公钥证书A通过B的公钥告之之B与之通信B向KDC申请A的公钥及会话密钥目的 （1）三元组的确是是KDC发送的（ （2）防止他人假冒B建建立与A的连接电子邮件等网络应用有一个最大的优点就是不要求收发双方同时在线，邮件的接收者希望对发送方的身份进行认证，以防他人假冒。 7.4.2单向认证与双向认证一样，在此仍分为单钥加密和公钥加密两种情况来考虑。 1.单钥加密Needham-Schroeder协议中去掉第步和第步就可满足单向通信的两个要求。 协议如下AKDC ID AID BN1KDCA EKAK SID BN1EKBK SID AAB EKBK SID AEKSM本协议不要求B同时在线，但保证了只有B能解读消息，同时还提供了对消息的发方A的认证。 然而本协议不能防止重放攻击，为此需在消息中加上时戳，但由于电子邮件处理中的延迟，时戳的作用极为有限。 2.公钥加密公钥加密算法可对发送的消息提供保密性、认证性为此要求发送方知道接收方的公开钥（保密性），或要求接收方知道发送方的公开钥（认证性），或要求通信双方都知道对方的公开钥。 ?提供保密性AB EPKBK SEKSM?认证性AB ME SKAH(M)?提供保密性和认证性AB EPKBMESKAH(M)后两种情况要求B知道A的公开钥并确信公开钥的真实性。 为此A还需同时向B发送自己的公钥证书，表示为ABMESKAH(M)E SKASTIDAPK A或:AB EPKBMESKAH(M)E SKASTIDAPK A其中E SKASTIDAPK A是认证服务器AS为A签署的公钥证书。 在很多情况下，用户都需证明自己的身份，如登录计算机系统、存取电子银行中的账目数据库、从自动出纳机ATM(automatic tellermachine)取款等。 传统的方法是使用通行字或个人身份识别号PIN(personal identificationnumber)来证明自己的身份，这些方法的缺点是检验用户通行字或PIN的人或系统可使用用户的通行字或PIN冒充用户。 本节介绍的身份的零知识证明技术，可使用户在不泄露自己的通行字或PIN的情况下向他人证实自己的身份。 7.5身份证明技术交互证明系统由两方参与，分别称为证明者（prover，简记为P）和验证者（verifier，简记为V），其中P知道某一秘密，P希望使V相信自己的确掌握这一秘密。 交互证明由若干轮组成，在每一轮，P和V可能需根据从对方收到的消息和自己计算的某个结果向对方发送消息。 比较典型的方式是在每轮V都向P发出一询问，P向V做出一应答。 所有轮执行完后，V根据P是否在每一轮对自己发出的询问都能正确应答，以决定是否接受P的证明。 7.5.1交互证明系统交互证明和数学证明的区别是数学证明的证明者可自己独立地完成证明，而交互证明是由P产生证明、V验证证明的有效性来实现，因此双方之间通过某种信道的通信是必需的。 交互证明系统须满足以下要求完备性:如果P知道某一秘密，V将接受P的证明。 正确性:如果P能以一定的概率使V相信P的证明，则P知知道相应的秘密。 1.协议及原理n=pq，（p、q是两不同的大素数）y2x mod n其中其中n和x是公开的，而p、q和y是保密的。 P以y作为自己的秘密。 ?已证明，求解方程y2x mod n与分解n是等价的。 因此他人不知n的两个素因子p、q而计算y是困难的。 ?P和V通过交互证明协议，P向V证明自己掌握秘密y，从而证明了自己的身份。 7.5.2简化的Fiat-Shamir身份识别方案协议如下P随机选r(0 V随机选e0,1，将将e发送给P。 P计算bry emod n，即即e=0时，b=r；e=1时，b=ry mod n。 将将b发送给V。 若b2ax emod n，V接受P的证明。 在协议的前3步，P和V之间共交换了3个个消息，这3个个消息的作用分别是第第1个消息是P用来声称自己知道a的平方根；第第2个消息e是V的询问，如果e=0，P必须展示a的平方根，即即r，如果e=1，P必须展示被加密的秘密，即ry mod n；第第3个消息b是P对V询问的应答。 2.协议的完备性、正确性和安全性 (1)完备性如果P和V遵守协议，且P知道y，则应答bry emod n应应是模n下ax e的平方根，在协议的第步V接受P的证明，所以协议是完备的。 (2)正确性假冒的证明者E可按以下方式以1/2的概率骗得V接受自己的证明E随机选r(0 V随机选e0,1，将将e发送给E。 E将r发送给V。 ?0,1e?n xr aemod2?根据协议的第步，V的验证方程是是，当当时，验证方程成立，V接受E的证明，即E欺骗成功。 因的概率是是1/2，所以E欺骗成功的概率是1/2。 另一方面，1/2是E能能成功欺骗的最好概率，否则假设E以大于1/2的概率使V相信自己的证明，那么E知道一个a，对这个a他可正确地应答V的两个询问e=0和e=1，意味着E能计算b21a mod n和b22ax mod n，即即，因此E由即可求得x的平方根y，矛盾。 22mod modee erax nr xx n?ee?ee?2221modbx nb?21modbnb (3)安全性协议的安全性可分别从P和V的角度来考虑。 假冒的证明者E欺骗V成功的概率是1/2，对V来说，这个概率太大了。 为减小这个概率，可将协议重复执行多次，设执行t次，则欺骗者欺骗成功的概率将减小到2-t。 下面考虑P的安全性。 因为V的询问是在很小的集合0,1中选取的，V没有机会产生其他信息，而P发送给V的的信息仅为P知道x的平方根这一事实，因此V无法得知x的平方根。 零知识证明实际上是一种密码协议，零知识证明起源于最小泄露证明。 在交互证明系统中，设P知道某一秘密，并向向V证明自己掌握这一秘密，但又不向V泄露这一秘密，这就是最小泄露证明。 进一步，如果V除了知道P能证明某一事实外，不能得到其他任何信息，则称P实现了零知识证明，相应的协议称为零知识证明协议。 7.5.3零知识证明例例7.4图7.4表示一个简单的迷宫，C与D之间有一道门，需要知道秘密口令才能将其打开。 P向V证明自己能打开这道门，但又不愿向V泄露秘密口令。 可采用如下协议V在协议开始时停留在位置A。 P一直走到迷宫深处，随机选择位置C或位置D。 P消失后，V走到位置B，然后命令P从某个出口返回位置置B。 P服从V的命令，必要时利用秘密口令打开C与D之间的门。 P和V重复以上过程n次。 P每次猜对V要求走哪一条路的概率是1/2，因此每一轮中P能够欺骗V的概率是1/2。 假定n取16，则执行16轮后，P成功欺骗V的概率是1/216=1/65536。 于是，如果P16次都能按按V的要求返回，V即能证明P确实知道秘密口令。 还可以看出，V无法从上述证明过程中获取丝毫关于P的秘密口令的信息，所以这是一个零知识证明协议。 1.协议及原理在简化的Fiat-Shamir身份识别方案中，验证者V接受假冒的证明者证明的概率是1/2，为减小这个概率，将证明者的秘密改为由随机选择的t个平方根构成的一个向量y=(y1,y2,y t)，模数n和向量x=(y21,y22,y2t)是公开的，其中中n仍是两个不相同的大素数的乘积。 7.5.4Fiat-Shamir身份识别方案协议如下P随机选r(0 V随机选e=(e1,e2,e t)，其中e i0,1(i=1,2,t)，将将e发发送给P。 P计算，将将b发送给V。 若V拒绝P的证明，协议停止。 P和V重复以上过程k次。 1moditeiib ryn?21moditeiib ax n?假设两个人A和B通过计算机网络进行智力扑克比赛，比赛中不用第三方做裁判。 发牌者可由任一方担任，发牌过程应满足以下要求任一副牌（即发给参赛人员手中的牌）是等可能的。 发给A、B手中的牌没有重复的。 每人都知道自己手中的牌，但却不知对方手中的牌。 比赛结束后，每一方都能发现对方的欺骗行为（如果有的话）。 7.6其他密码协议7.6.1智力扑克为满足这些要求，A、B之间必须以加密形式交换一些信息。 在下面的协议中，加密体制可以是单钥密码也可以是公钥密码，设E A和和E B、DA和和D B分别表示A和B的加密变换和解密变换，在比赛结束之前，这些变换都是保密的，比赛结束后予以公布用以证明比赛的公正性。 要求加密变换满足交换律，即对任意消息M有E A(E B(M)=E B(E A(M)比赛开始前A、B协商好用以表示52张牌的消息w1,w2,w52，协议中设A为发牌人，并设给每人发5张牌。 协议如下B先洗牌，然后用E B对对52个消息分别加密，将加密结果E B(w i)发送给A。 A从收到的52个加密的消息中随机选5个E B(w i)，并发送给给B，B用自己的解密变换D B对这5个值解密，解密后的值作为发给自己的一副牌。 因为B的加密变换EB和解密变换D B都是保密的，所以A无法知道B手中的牌。 A另选5个E B(w i)，用用E A加密后发送给B。 B用D B对收到的值解密后再发送给A，A用DA对收到的值解密后作为发给自己的一副牌，这是因为B发送给A的值是DB(E A(E B(w i)=DB(E B(E A(w i)=E A(w i)其中用到加密变换的交换律。 下面考虑该协议是否满足发牌过程的4个要求。 对第个要求，B可在协议的第步检查A发来的5个值是否和第步发来的5个值有重复。 为满足第4个要求，可在比赛结束后公开所有的加密变换和解密变换，双方都可检查对方的牌看是否有欺诈。 对第个和第个要求来说，关键在于加密变换EB的强度，由E B(w i)可能得不出w i，但有可能得出w i的部分信息。 例如，w i是一个比特串，则有可能从E B(w i)得出w i的最后一个比特，因此A可将52个值E B(w1),E B(w2),E B(w52)分成两个子集，A在发牌时可将发给B的牌集中在某一子集中，因此使得第个和第个要求无法满足。 在计算机网络中，实现真正的掷硬币是不可能的，但执行一个掷硬币协议是可能的。 一般来说，一个投硬币协议需要满足以下三个条件（ （1）A和B各有50%的机会获胜（ （2）规定双方中任何一方欺骗则认为其失败（ （3）协议结束后，A，B双方都知识结果。 7.6.2掷硬币协议1.采用平方根掷硬币协议如下A选择两个大素数p、q，将乘积n=pq发送给B。 B在1和n/2之间，随机选择一个整数u，计算zu2modn，并将z发送给A。 A计算模n下z的4个平方根x和y（因因A知道n的分解，所以可做到），设x是x modn和-xmodn中较小者，y是y modn和-y modn中较小者，则由于1 A猜测u=x或u=y，或者A找出最小的i使得x的第i个比特与y的第i个比特不同，A猜测u的第i个比特是0还是1。 A将猜测发送给B。 B告诉A猜测正确或不正确，并将u的值发送给A。 A公开n的因子。 分析因因u是B随机选取的，A不知道u，所以要猜测u只能是计算模n下z的4个平方根，猜中的概率是1/2。 考虑B如何能欺骗A，如果B在A猜测完后能够改变u的值，则则A的猜测必不正确，A可通过检查出B是否改变了了u的值，所以B要想改变u的值就只能在x和y之间进行。 而而B若掌握x和y，就可通过gcdx-y,n或gcdx+y,n求出出p和q，说明B的欺骗与分解n是等价的。 )(mod2n uz?例例7.6本例是采用平方根掷硬币的一个具体实现过程A取p=3,q=7，将将n=21发送给B。 B在1和21/2之间，随机选择一个整数u=2，计算z22modn4并将z=4发送给A。 A计算模21下z=4的4个平方根x=2,-x=19,y=5,-y=16，取x=2，y=5。 A猜测u=5并将猜测发送给B.B告诉A猜测不正确，并将u=2发送给A，A检验u=2在1和和21/2之间且满足422mod21，A知道自己输了。 A公开n=21的因子p=3,q=7，B检验n=pq，知道自己赢了。 2.利用单向函数掷硬币设设A、B都知道某一单向函数f(x)，但都不知道该函数的逆函数，协议如下B选择一个随机数x，求求y=f(x)并发送给A。 A对x的奇偶性进行猜测，并将结果告诉B。 B告诉A猜测正确或不正确，并将x发送给A。 由于A不知道f(x)的逆函数，因此无法通过B发过来的y得出x，即只能猜测x的奇偶性。 而B若在A做出猜测以后改变x，A可通过检查出来。 ?y fx?3.利用二次剩余掷硬币设设n是两个大素数p、q的乘积，即n=pq。 整数a满足0 1an?1an?协议如下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 modn的4个平方根（如果a是模n的平方剩余），以检查B是否在A猜测完后将结果做了修改。 1an?设设A有一个秘密，想以1/2的概率传递给B，即即B有50%的机会收到这个秘密，另外50%的机会什么也没有收到，协议执行完后，B知道自己是否收到了这个秘密，但A却不知知B是否收到了这个秘密。 这种协议就称为不经意传输协议。 例如A是机密的出售者，A列举了很多问题，意欲出售各个问题的答案，B想买其中一个问题的答案，但又不想让A知道自己买的是哪个问题的答案。 7.6.3不经意传输1.基于大数分解问题的不经意传输协议设设A想通过不经意传输协议传递给B的秘密是整数n（为两个大素数之积）的因数分解。 这个问题具有普遍意义，因为任何秘密都可通过RSA加密，得到n的因数分解就可得到这个秘密。 协议基于如下事实已知某数在模n下两个不同的平方根，就可分解n。 协议如下B随机选一数x，将将x2modn发送给A。 A（掌握n=pq的分解）计算x2modn的4个平方根x和和y，并将其中之一发送给B。 由于A只知道x2modn，并不知道4个平方根中哪一个是B选的x。 B检查第步收到的数是否与x在模n下同余，如果是，则则B没有得到任何新信息；否则B就掌握了x2modn的两个不同的平方根，从而能够分解n。 而而A却不知究竟是哪种情况。 显然，B得到n的分解的概率是1/2。 2.基于离散对数问题的不经意传输协议下一个不经意传输协议是非交互的，其中B不向A发送任何消息。 设系统中所有用户都知道一个大素数p、GF(p)-0的生成元g和另一大素数c，但无人知道c的离散对数。 假定计算离散对数是不可行的，因此从g xmodp和g ymodp无无法计算g xymodp。 协议中所有运算都在GF(p)中进行。 B按如下方式产生公开的加密密钥和秘密的解密密钥随随机选取一个比特i和一个数x(0xp-2)，计算y i=g x,y1-i=c(g x)-1，以以(y0,y1)作为公开的加密密钥，以(i,x)作为秘密解密密钥。 由于B不知道c的离散对数，所以他知道y0或或y1的离散对数，而而A无法知道y0和和y1中哪个离散对数是B已知的。 A可通过方程程y0y1=c来检查B的公开加密密钥是否正确。 协议中设A的两个秘密s0和和s1若进行异或运算的两个数不等长，可在较短数前面补0。 协议如下A在0到p-2之间随机取两个整数k 0、k1，对对j=0,1计算将c0,c1,m0,m1发送给B。 B用自己的秘密解密密钥计算。 由于B不知道y1-i的离散对数，所以无法得到d1-i和和s1-i。 ,jkjc g?,jkj jdy?j jjm sd?i ixkk xi i icg yd?iiis md?3.“多传一”的不经意传输协议设设A有多个秘密，想将其中一个传递给B，使得只有B