现代密码学第9章：身份认证

1身份认证《现代密码学》第9章2本章主要内容1、身份认证概述2、相互认证3、单向认证4、身份的零知识证明技术5、其他的身份认证密码协议6、典型的认证应用31．身份认证概述为了保护网络资源及落实安全政策。需要提供可追究责任的机制，这里涉及到三个概念：认证、授权及审计。（1）认证Authentication：在做任何动作之前必须要有方法来识别动作执行者的真实身份。认证又称为鉴别、确认。身份认证主要是通过标识和鉴别用户的身份，防止攻击者假冒合法用户获取访问权限。（2）授权Authorization：授权是指当用户身份被确认合法后，赋予该用户进行文件和数据等操作的权限。这种权限包括读、写、执行及从属权等。（3）审计Auditing：每一个人都应该为自己所做的操作负责，所以在做完事情之后都要留下记录，以便核查责任。4用户对资源的访问过程5身份认证概述

在现实生活中，我们个人的身份主要是通过各种证件来确认的，比如：身份证、户口本等。计算机网络信息系统中，各种计算资源（如：文件、数据库、应用系统）也需要认证机制的保护，确保这些资源被应该使用的人使用。在大多数情况下，认证机制与授权和记账也紧密结合在一起。身份认证是对网络中的主体进行验证的过程，用户必须提供他是谁的证明。身份认证往往是许多应用系统中安全保护的第一道设防，它的失败可能导致整个系统的失败。6身份认证系统包含下列三项主要组成元件：（1）认证服务器(AuthenticationServer)负责进行使用者身份认证的工作，服务器上存放使用者的私有密钥、认证方式及其他使用者认证的相关资讯。（2）认证系统用户端软体(AuthenticationClientSoftware)认证系统用户端通常都是需要进行登陆(login)的设备或系统，在这些设备及系统中必须具备可以与认证服务器协同运作的认证协议。也有些情况下认证服务器与认证系统用户端软体是集成在一起的。（3）认证设备(Authenticator)认证设备是使用者用来产生或计算密码的软硬件设备。身份认证概述7

从用户角度来看，非法用户常采用以下手段对身份认证过程中攻击：数据流窃听(Sniffer)：由于认证信息要通过网络传递，并且很多认证系统的口令是未经加密的明文，攻击者通过窃听网络数据，就很容易分辨出某种特定系统的认证数据，并提取出用户名和口令。拷贝/重传：非法用户截获信息，然后再传送给接收者。修改或伪造：非法用户截获信息，替换或修改信息后再传送给接收者，或者非法用户冒充合法用户发送信息。身份认证概述8

适合于各种不同场合的认证交换机制有多种选择与组合。例如：当对等实体以及通信手段都可信任时，一个对等实体的身份可以通过口令来证实。该口令能防止出错，但不能防止恶意行为(特别不能防止重演)。相互鉴别可在每个方向上使用不同的口令来完成；当每个实体信任它的对等实体但不信任通信手段时，抗主动攻击的保护能够由口令与加密联合提供，或由密码手段提供。防止重演攻击的需要双方握手(用保护参数)，或时间标记(用可信任时钟)。带有重演保护的相互鉴别，使用三方握手就能达到。身份认证概述9

当实体不信任(或感到它们将来可能不信任)它们的对等实体或通信手段时可以使用抗抵赖服务。使用数字鉴名机制和公证机制就能实现抗抵赖服务。这些机制可与上面b中所述的机制一起使用。在计算机网络中，通常采用三种方法验证主体身份。一是只有该主体了解的秘密，如口令、密钥；二是主体携带的物品，如智能卡；三是只有该主体具有的独一无二的特征或能力，如指纹、声音、视网膜血管分布图或签字等。身份认证概述10

以前介绍过消息认证的基本概念，事实上安全可靠的通信除需进行消息的认证外，还需建立一些规范的协议对数据来源的可靠性、通信实体的真实性加以认证，以防止欺骗、伪装等攻击。本节以网络通信的一个基本问题的解决引出认证协议的基本意义，这一基本问题陈述如下：2.相互认证11A和B是网络的两个用户，他们想通过网络先建立安全的共享密钥再进行保密通信。那么A(B)如何确信自己正在和B(A)通信而不是和C通信呢？这种通信方式为双向通信，因此，此时的认证称为相互认证。类似地，对于单向通信来说，认证称为单向认证。2.相互认证12

A、B两个用户在建立共享密钥时需要考虑的核心问题是保密性和实时性。为了防止会话密钥的伪造或泄露，会话密钥在通信双方之间交换时应为密文形式，所以通信双方事先就应有密钥或公开钥。第2个问题实时性则对防止消息的重放攻击极为重要，实现实时性的一种方法是对交换的每一条消息都加上一个序列号，一个新消息仅当它有正确的序列号时才被接收。但这种方法的困难性是要求每个用户分别记录与其他每一用户交换的消息的序列号，从而增加了用户的负担，所以序列号方法一般不用于认证和密钥交换。2.1相互认证的实现13保证消息的实时性常用以下两种方法：

时戳 如果A收到的消息包括一时戳，且在A看来这一时戳充分接近自己的当前时刻，A才认为收到的消息是新的并接受之。这种方案要求所有各方的时钟是同步的。询问-应答 用户A向B发出一个一次性随机数作为询问，如果收到B发来的消息（应答）也包含一正确的一次性随机数，A就认为B发来的消息是新的并接受之。保证消息的实时性14

其中时戳法不能用于面向连接的应用过程，这是由于时戳法在实现时固有的困难性。首先是需要在不同的处理器时钟之间保持同步，那么所用的协议必须是容错的以处理网络错误，并且是安全的以对付恶意攻击。第二，如果协议中任一方的时钟出现错误而暂时地失去了同步，则将使敌手攻击成功的可能性增加。保证消息的实时性15

最后还由于网络本身存在着延迟，因此不能期望协议的各方能保持精确的同步。所以任何基于时戳的处理过程、协议等都必须允许同步有一个误差范围。考虑到网络本身的延迟，误差范围应足够大；考虑到可能存在的攻击，误差范围又应足够小。保证消息的实时性16

而询问-应答方式则不适合于无连接的应用过程，这是因为在无连接传输以前需经询问\|应答这一额外的握手过程，这与无连接应用过程的本质特性不符。对无连接的应用程序来说，利用某种安全的时间服务器保持各方时钟同步是防止重放攻击最好的方法。通信双方建立共享密钥时可采用单钥加密体制和公钥加密体制。保证消息的实时性171.单钥加密体制采用单钥加密体制为通信双方建立共享的密钥时，需要有一个可信的密钥分配中心KDC，网络中每一用户都与KDC有一共享的密钥，称为主密钥。KDC为通信双方建立一个短期内使用的密钥，称为会话密钥，并用主密钥加密会话密钥后分配给两个用户。这种分配密钥的方式在实际应用中较为普遍采用，如Kerberos系统采用的就是这种方式。2.2单钥加密体制下共享密钥的的建立18(1)Needham-Schroeder协议以下是1978年出现的著名的Needham-Schroeder认证协议。这里需建立一个称为鉴别服务器的可信权威机构（密钥分发中心KDC），拥有每个用户的秘密密钥。若用户A欲与用户B通信，则用户A向鉴别服务器申请会话密钥。在会话密钥的分配过程中，双方身份得以鉴别。①A→KDC：IDA‖IDB‖N1②KDC→A：EKA[KS‖IDB‖N1‖EKB[KS‖IDA]]③A→B：EKB[KS‖IDA]④B→A：EKS[N2]⑤A→B：EKS[f(N2)]Needham-Schroeder协议19Needham-Schroeder认证过程

其中KDC是密钥分发中心，Ra、Rb是一次性随机数，保密密钥Ka和Kb分别是A和KDC、B和KDC之间共享的密钥，Ks是由KDC分发的A与B的会话密钥，EX表示使用密钥X加密。20

式中KA、KB分别是A、B与KDC共享的主密钥。协议的目的是由KDC为A、B安全地分配会话密钥KS，A在第②步安全地获得了KS，而第③步的消息仅能被B解读，因此B在第③步安全地获得了KS

，第④步中B向A示意自己已掌握KS，N2用于向A询问自己在第③步收到的KS是否为一新会话密钥，第⑤步A对B的询问作出应答，一方面表示自己已掌握KS，另一方面由f(N2)回答了KS的新鲜性。Needham-Schroeder协议21

可见第④、⑤两步用于防止一种类型的重放攻击，比如敌手在前一次执行协议时截获第③步的消息，然后在这次执行协议时重放，如果双方没有第④、⑤两步的握手过程的话，B就无法检查出自己得到的KS是重放的旧密钥。Needham-Schroeder协议22

然而以上协议却易遭受另一种重放攻击，假定敌手能获取旧会话密钥，则冒充A向B重放第③步的消息后，就可欺骗B使用旧会话密钥。敌手进一步截获第④步B发出的询问后，可假冒A作出第⑤步的应答。进而，敌手就可冒充A使用经认证过的会话密钥向B发送假消息。Needham-Schroeder协议23(2)

Needham-Schroeder协议的改进方案之一为克服以上弱点，可在第②步和第③步加上一时戳，改进后的协议如下：①A→KDC：IDA‖IDB②KDC→A：EKA[KS‖IDB‖T‖EKB[KS‖IDA‖T]]③A→B：EKB[KS‖IDA‖T]④B→A：EKS[N1]⑤A→B：EKS[f(N1)]Needham-Schroeder协议改进一24

其中T是时戳，用以向A、B双方保证KS的新鲜性。A和B可通过下式检查T的实时性：

|Clock-T|<Δt1+Δt2

其中Clock为用户（A或B）本地的时钟，Δt1是用户本地时钟和KDC时钟误差的估计值，Δt2是网络的延迟时间。以上协议中由于T是经主密钥加密的，所以敌手即使知道旧会话密钥，并在协议的过去执行期间截获第③步的结果，也无法成功地重放给B，因B对收到的消息可通过时戳检查其是否为新的。Needham-Schroeder协议改进一25

以上改进还存在以下问题：方案主要依赖网络中各方时钟的同步，这种同步可能会由于系统故障或计时误差而被破坏。如果发送方的时钟超前于接收方的时钟，敌手就可截获发送方发出的消息，等待消息中时戳接近于接收方的时钟时，再重发这个消息。这种攻击称为等待重放攻击。Needham-Schroeder协议改进一26

抗击等待重放攻击的一种方法是要求网络中各方以KDC的时钟为基准定期检查并调整自己的时钟，另一种方法是使用一次性随机数的握手协议，因为接收方向发送方发出询问的随机数是他人无法事先预测的，所以敌手即使实施等待重放攻击，也可被下面的握手协议检查出来。Needham-Schroeder协议改进一27(3)Needham-Schroeder协议的改进方案之二下面的协议可解决Needham-Schroeder协议以及改进方案一可能遭受的攻击：①A→B：IDA‖NA②B→KDC：IDB‖NB‖EKB[IDA‖NA‖TB]③KDC→A：EKA[IDB‖NA‖KS‖TB]‖EKB[IDA‖KS‖TB]‖NB④A→B：EKB[IDA‖KS‖TB]‖EKS[NB]Needham-Schroeder协议改进二28协议的具体含义如下：①A将新产生的一次性随机数NA与自己的身份IDA一起以明文形式发往B，NA以后将与会话密钥KS一起以加密形式返回给A，以保证A收到的会话密钥的新鲜性。Needham-Schroeder协议改进二29②B向KDC发出与A建立会话密钥的请求，表示请求的消息包括B的身份、一次性随机数NB以及由B与KDC共享的主密钥加密的数据项。其中NB以后将与会话密钥一起以加密形式返回给B以向B保证会话密钥的新鲜性，请求中由主密钥加密的数据项用于指示KDC向A发出一个证书，其中的数据项有证书接收者A的身份、B建议的证书截止时间TB、B从A收到的一次性随机数。Needham-Schroeder协议改进二30③KDC将B产生的NB连同由KDC与B共享的密钥KB加密的IDA‖KS‖TB一起发给A，其中KS是KDC分配的会话密钥，EKB[IDA‖KS‖TB]由A当作票据用于以后的认证。KDC向A发出的消息还包括由KDC与A共享的主密钥加密的IDB‖NA‖KS‖TB，A用这一消息可验证B已收到第①步发出的消息（通过IDB），A还能验证这一步收到的消息是新的（通过NA），这一消息中还包括KDC分配的会话密钥KS以及会话密钥的截止时间TB。Needham-Schroeder协议改进二31④A将票据EKB[IDA‖KS‖TB]连同由会话密钥加密的一次性随机数NB发往B，B由票据得到会话密钥KS，并由KS得NB。NB由会话密钥加密的目的是B认证了自己收到的消息不是一个重放,而的确是来自于A。Needham-Schroeder协议改进二32

以上协议为A、B双方建立共享的会话密钥提供了一个安全有效的手段。再者，如果A保留由协议得到的票据，就可在有效时间范围内不再求助于认证服务器而由以下方式实现双方的新认证：①A→B：EKB[IDA‖KS‖TB],N′A②B→A：N′B，EKS[N′A]③A→B：EKS[N′B]Needham-Schroeder协议改进二332.公钥加密体制曾介绍过使用公钥加密体制分配会话密钥的方法，下面的协议也用于这个目的。①A→AS：IDA‖IDB②AS→A：ESKAS[IDA‖PKA‖T]‖ESKAS[IDB‖PKB‖T]③A→B：ESKAS[IDA‖PKA‖T]‖ESKAS[IDB‖PKB‖T‖EPKB[ESKA[KS‖T]]2.3公钥加密体制下共享密钥的建立34

其中SKAS、SKA

分别是AS和A的秘密钥，PKA、PKB分别是A和B的公开钥，E为公钥加密算法，AS是认证服务器（authenticationserver）。第①步，A将自己的身份及欲通信的对方的身份发送给AS。第②步，AS发给A的两个链接的数据项都是由自己的秘密钥加密（即由AS签字），分别作为发放给通信双方的公钥证书。公钥加密体制下共享密钥的建立35

第③步，A选取会话密钥并经自己的秘密钥和B的公开钥加密后连同两个公钥证书一起发往B。因会话密钥是由A选取，并以密文形式发送给B，因此包括AS在内的任何第3者都无法得到会话密钥。时戳T用以防止重放攻击，所以需要各方的时钟是同步的。公钥加密体制下共享密钥的建立36

下一协议使用一次性随机数，因此不需要时钟的同步：①A→KDC：IDA‖IDB②KDC→A：ESKAU[IDB‖PKB]③A→B：EPKB[NA‖IDA]④B→KDC：IDB‖IDA‖EPKAU[NA]⑤KDC→B：ESKAU[IDA‖PKA]‖EPKB[ESKAU[NA‖KS‖IDB]]⑥B→A：EPKA[ESKAU[NA‖KS‖IDB]‖NB]⑦A→B：EKS[NB]公钥加密体制下共享密钥的建立37

其中SKAU和PKAU分别是KDC的秘密钥和公开钥。第①步，A通知KDC他想和B建立安全连接。第②步，KDC将B的公钥证书发给A，公钥证书包括经KDC签字的B的身份和公钥。第③步，A告诉B想与他通信，并将自己选择的一次性随机数NA发给B。第④步，B向KDC发出得到A的公钥证书和会话密钥的请求，请求中由KDC的公开钥加密的NA用于让KDC将建立的会话密钥与NA联系起来，以保证会话密钥的新鲜性。公钥加密体制下共享密钥的建立38

第⑤步，KDC向B发出A的公钥证书以及由自己的秘密钥和B的公开钥加密的三元组{NA,KS,IDB}。三元组由KDC的秘密钥加密可使B验证三元组的确是由KDC发来的，由B的公开钥加密是防止他人得到三元组后假冒B建立与A的连接。第⑥步，B新产生一个一次性随机数NB,连同上一步收到的由KDC的秘密钥加密的三元组一起经A的公开钥加密后发往A。第⑦步，A取出会话密钥，再由会话密钥加密NB后发往B，以使B知道A已掌握会话密钥。公钥加密体制下共享密钥的建立39

以上协议可进一步做如下改进：在第⑤、⑥两步出现NA的地方加上IDA，以说明NA的确是由A产生的而不是其他人产生的，这时{IDA，NA}就可惟一地识别A发出的连接请求。公钥加密体制下共享密钥的建立40Diffie-Hellman算法发明于1976年，是第一个公开密钥算法。Diffie-Hellman算法不能用于加密与解密，但可用于密钥分配。密钥交换协议(keyexchangeprotocol)是指两人或多人之间通过一个协议取得密钥并用于通信加密。在实际的密码应用中密钥交换是很重要的一个环节。比如说利用对称加密算法进行秘密通信，双方首先需要建立一个共享密钥。如果双方没有约定好密钥，就必须进行密钥交换。如何使得密钥到达接收者和发送者手里是件很复杂的事情，最早利用公钥密码思想提出一种允许陌生人建立共享秘密密钥的协议叫Diffle-Hellman密钥交换。Diffie-Hellman共享密钥的建立41Diffie-Hellman密钥交换算法是基于有限域中计算离散对数的困难性问题之上的。离散对数问题是指对任意正整数x，计算gxmodP是容易的；但是一般的已知g、Y和P求x使Y=gxmodP是计算上几乎不可能的。当Alice和Bob要进行秘密通信时，他们可以按如下步骤建立共享密钥：（1）Alice选取大的随机数x，并计算X=gx(modP)，Alice将g、P、X传送给Bob。（2）Bob选取大的随机数y，并计算Y=gy(modP)，Bob将Y传送给Alice。（3）Alice计算K=Yx(modP)；Bob计算K’＝Xy(modP)，易见，K=K’=gxy(modP)。Alice和Bob获得了相同的秘密值K。双方以K作为加解密钥以对称密钥算法进行保密通信。Diffie-Hellman共享密钥的建立42监听者可以获得g、P、X、Y，但由于算不出x、y，所以得不到共享密钥K。虽然Diffie-Hellman密钥交换算法十分巧妙，但由于没有认证功能，存在中间人攻击。当Alice和Bob交换数据时，Trudy拦截通信信息，并冒充Alice欺骗Bob，冒充Bob欺骗Alice。其过程如下：Diffie-Hellman共享密钥的建立43

中间人攻击44（1）Alice选取大的随机数x，并计算X=gx(modP)，Alice将g、P、X传送给Bob，但被Trudy拦截。（2）Trudy冒充Alice选取大的随机数z，并计算

Z=gz(modP)，Trudy将Z传送给Bob。（3）Trudy冒充Bob选取大的随机数z，并计算

Z=gz(modP)，Trudy将Z传送给Alice。（4）Bob选取大的随机数y，并计算

Y=gy(modP)，Bob将Y传送给Alice，但被Trudy拦截。由（1）、（3）Alice与Trudy共享了一个秘密密钥gxz，由（2）、（4）Trudy与Bob共享了一个秘密密钥gyz。Diffie-Hellman共享密钥的建立45站间协议（station-to-stationprotocol）是一个密钥协商协议，它能够挫败这种中间人攻击，其方法是让A、B分别对消息签名。（1）A→B：gx（2）B→A：gy||Ek(Sb(gy||gx))（3）A→B：Ek(Sa(gx||gy))Diffie-Hellman共享密钥的建立46

其中建立的会话密钥是k=gxy。站间协议的一个改进版本没有使用加密，建立的会话密钥仍然是k=gxy。（1）A→B：gx（2）B→A：gy||Sb(gy||gx)（3）A→B：Sa(gx||gy)

站间协议具有前向保密性（Forwardsecret）。前向保密性是指长期密钥被攻破后，利用长期密钥建立的会话密钥仍具有保密性。站间协议中A、B的私钥泄露不影响会话密钥的安全。Diffie-Hellman共享密钥的建立47首先假定双方已经知道对方的公开密钥，如交换证书。ISO认证的基本步骤如下：（1）A→B：Ra（2）B→A：Certb||Rb||Sb(Ra||Rb||B)其中Ra、Rb是大的随机数，Certb是B的证书，Sb()表示使用B的私有密钥进行数字签名。如果需要双向认证，需要第三步：（3）A→B：Certa||Sa(Ra||Rb||A)这里Sa()表示使用A的的私有密钥进行数字签名。2.4公钥加密体制下的认证过程48现在我们假定双方不知道对方的公开密钥。这时需要一个可信的第三方T保存公开密钥库。Denning-Sacco认证协议如下：（1）A→T：A||B（2）T→A：ST（B||KB）||ST（A||KA）T把用T的私钥T签名的B的公钥KB发给A。T也把用T的私钥T签名的A自己的公钥KA发给A。（3）A→B：EB（SA（K||TA））||ST（B，KB）||ST（A，KA）公钥加密体制下的DS认证协议49A向B传送随机会话密钥K、时间标记TA（都用A自己私钥签名并用B的公钥加密）和两个签了名的公开密钥。B用私钥解密A的消息，然后用A的公钥验证签名。以确信时间标记仍有效。在这里A和B两人都有密钥K，他们能够安全地通信。公钥加密体制下的DS认证协议50但该协议是有缺陷的。在和A一起完成协议后，B能够伪装是A。其步骤是：（1）B→T：B||C（2）T→B：ST（C||KC）||ST（B||KB）（3）B(A)→C：EC（SA（K||TA））||ST（C||KC）||ST（A||KA）B将以前从A那里接收的会话密钥和时间标记的签名用C的公钥加密，并和A和C的证书一起发给C。C用私钥解密A的消息，然后用A的公钥验证签名。检查并确信时间标记仍有效。C现在认为正在与A交谈，B成功地欺骗了C。在时间标记截止前，B可以欺骗任何人。公钥加密体制下的DS认证协议51这个问题容易解决。在第（3）步的加密消息内加上名字：

EB（SA（A||B||K||TA））||ST（A||KA）||ST（B||KB）因为这一步清楚地表明是A和B在通信，所以现在B就不可能对C重放旧消息。公钥加密体制下的DS认证协议52

电子邮件等网络应用有一个最大的优点就是不要求收发双方同时在线，发送方将邮件发往接收方的信箱，邮件在信箱中存着，直到接收方阅读时才打开。邮件消息的报头必须是明文形式以使SMTP（simplemailtransferprotocol-简单邮件传输协议）或X.400等存储-转发协议能够处理。然而通常都不希望邮件处理协议要求邮件的消息本身是明文形式，否则就要求用户对邮件处理机制的信任。3.单向认证53

所以用户在进行保密通信时，需对邮件消息进行加密以使包括邮件处理系统在内的任何第3者都不能读取邮件的内容。再者邮件接收者还希望对邮件的来源即发方的身份进行认证，以防他人的假冒。单向认证54

通过用户ID和口令进行认证是操作系统或应用程序通常采用的。如果非法用户获得合法用户身份的口令，他就可以自由访问未授权的系统资源，所以需要防止口令泄露。易猜的口令或缺省口令也是一个很严重的问题，但一个更严重的问题是有的帐号根本没有口令。实际上，所有使用弱口令，缺省口令和没有口令的帐号都应从系统中清除。另外，很多系统有内置的或缺省的帐号，这些帐号在软件的安装过程中通常口令是不变的。攻击者通常查找这些帐号。因此，所有内置的或缺省的帐号都应从系统中移出。3.1单向认证中的口令认证55

目前各类计算资源主要靠固定口令的方式来保护。这种以固定口令为基础的认证方式存在很多问题，对口令的攻击包括以下几种：（1）网络数据流窃听(Sniffer)：攻击者通过窃听网络数据，如果口令使用明文传输，则可被非法截获。大量的通讯协议比如Telnet、Ftp、基本HTTP都使用明文口令，这意味着它们在网络上是以未加密格式传输于服务器端和客户端，而入侵者只需使用协议分析器就能查看到这些信息，从而进一步分析出口令。口令认证的攻击类型56口令认证的攻击类型--窃听57（2）认证信息截取/重放(Record/Replay)：有的系统会将认证信息进行简单加密后进行传输，如果攻击者无法用第一种方式推算出密码，可以使用截取/重放方式，需要的是重新编写客户端软件以使用加密口令实现系统登录。口令认证的攻击类型—截取/重放58截取/重放59（3）字典攻击：根据调查结果可知，大部份的人为了方便记忆选用的密码都与自己周遭的事物有关，例如：身份证字号、生日、车牌号码、在办公桌上可以马上看到的标记或事物、其他有意义的单词或数字，某些攻击者会使用字典中的单词来尝试用户的密码。所以大多数系统都建议用户在口令中加入特殊字符，以增加口令的安全性。（4）穷举攻击(BruteForce)：也称蛮力破解。这是一种特殊的字典攻击，它使用字符串的全集作为字典。如果用户的密码较短，很容易被穷举出来，因而很多系统都建议用户使用长口令。口令认证的攻击类型60（5）窥探：攻击者利用与被攻击系统接近的机会，安装监视器或亲自窥探合法用户输入口令的过程，以得到口令。（6）社交工程：社会工程就是指采用非隐蔽方法盗用口令等，比如冒充是处长或局长骗取管理员信任得到口令等等。冒充合法用户发送邮件或打电话给管理人员，以骗取用户口令等。比如，在终端上可能发现如下信息：Pleaseenteryourusernametologon:Yourpassword:这很可能是一个模仿登录信息的特洛伊木马程序，他会记录口令，然后传给入侵者。口令认证的攻击类型61（7）垃圾搜索：攻击者通过搜索被攻击者的废弃物，得到与攻击系统有关的信息，如果用户将口令写在纸上又随便丢弃，则很容易成为垃圾搜索的攻击对象。口令认证的攻击类型62在口令的设置过程中，有许多个人因素在起作用，攻击者可以利用这些因素来解密。由于口令安全性的考虑，人们会被禁止把口令写在纸上，因此很多人都设法使自己的口令容易记忆，而这就给攻击者提供了可乘之机。为防止攻击猜中口令。安全口令具有以下特点：（1）位数>6位。（2）大小写字母混合。如果用一个大写字母，既不要放在开头，也不要放在结尾。（3）可以把数字无序的加在字母中。（4）系统用户一定用8位口令，而且包括～!@＃＄％^＆＊<>?:"{}等特殊符号。安全口令的特点63不安全的口令则有如下几种情况：（1）使用用户名（帐号）作为口令。这种方法便于记忆，可是在安全上几乎是不堪一击。几乎所有以破解口令为手段的黑客软件，都首先会将用户名作为口令的突破口。（2）用用户名（帐号）的变换形式作为口令。将用户名颠倒或者加前后缀作为口令，比如说著名的黑客软件John，如果用户名是fool，那么它在尝试使用fool作为口令之后，还会试着使用诸如fool123、fool1、loof、loof123、lofo等作为口令。不安全口令的类型64（3）使用自己或者亲友的生日作为口令。这种口令有着很大的欺骗性，因为这样往往可以得到一个6位或者8位的口令，但实际上可能的表达方式只有100×12×31=37200种，即使再考虑到年月日三者共有六种排列顺序，一共也只有37200×6=223200种。（4）使用常用的英文单词作为口令。这种方法比前几种方法要安全一些。如果选用的单词是十分偏僻的，那么黑客软件就可能无能为力了。不安全口令的类型65应采取两个步骤以消除口令漏洞。第一步，所有弱口令应被加强。但是当用户被要求改变或加强他们的弱口令时，他们经常又选择一个容易猜测的。这就导致了第二步，用户的口令在被修改后，应加以确认。可以用程序来拒绝任何不符合安全策略的口令。可以采取以下措施来加强口令的安全性：（1）在创建口令时执行检查功能。如检查口令的长度。（2）强制使口令周期性过期。也就是定期更换口令。（3）保持口令历史记录，使用户不能循环使用旧口令。加强口令安全性的措施66可以使用以下几种方式进行基于口令的认证：（1）基于单向函数计算机存储口令的单向函数值而不是存储口令。Alice将口令传送给计算机，计算机使用单向函数计算，然后把单向函数的运算结果和它以前存储的单向函数值进行比较。由于计算机不再存储口令表，所以敌手侵入计算机偷取口令的威胁就减少了。（2）掺杂口令如果敌手获得了存储口令的单向函数值的文件，采用字典攻击是有效的。敌手计算猜测的口令的单向函数值，然后搜索文件，观察是否有匹配的。

Salt是使这种攻击更困难的一种方法。Salt是一随机字符串，它与口令连接在一起，再用单向函数对其运算。然后将Salt值和单向函数运算的结果存入主机中。Salt只防止对整个口令文件采用的的字典攻击，不能防止对单个口令的字典攻击。加强口令安全性的措施67

（3）SKEYAlice输入随机数R，计算机计算x1=f（R）、x2=f（x1）、…、xn+1=f（xn）。Alice保管x1，x2，x3，。。。，xn这些数的列表，计算机在登录数据库中Alice的名字后面存储xn+1的值。当Alice第一次登录时，输入名字和xn，计算机计算f（xn），并把它和xn+1比较，如果匹配，就证明Alice身份是真的。然后，计算机用xn代替xn+1。Alice将从自己的列表中取消xn。Alice每次登录时，都输入她的列表中未取消的最后的数xI，计算机计算f（xI），并和存储在它的数据库中的xI+1比较。当Alice用完了列表上面的数后，需要重新初始化。加强口令安全性的措施68为了增强基于口令认证的安全，可以采用以下改进方案。（1）认证过程有一定的时延，增大穷举尝试的难度。（2）不可预测的口令。修改口令登记程序以便促使用户使用更加生僻的口令。这样就进一步削弱了字典攻击。（3）对无效用户名的回答应该与对有效用户名的回答相同。加强口令安全性的措施69

成功地注册进入系统，必须首先打入一个有效的用户名，然后再打入一个对该用户名是正确的口令。如果当用户名有效时，要延迟1.5秒后才回答，而对无效用户名是立即回答。这样破坏者就能查明某个特定的用户名是否有效。（4）一次性口令固定密码有被监听及猜中的问题，如果使用者使用的密码可以不断改变就可以防止固定密码的问题，因此这种不断改变使用者密码的技术便被称作动态口令(DynamicPassword)或者一次性口令OTP(One-timePassword)。其主要思路是在登录过程中加入不确定因素，使每次登录过程中传送的信息都不相同，以提高登录过程安全性。系统接收到登录口令后做一个验算即可验证用户的合法性。如挑战/响应。用户登录时，系统产生一个随机数(nonce)发送给用户。用户将自己的口令和随机数用某种单向算法混合起来发送给系统，系统用同样的方法做验算即可验证用户身份。加强口令安全性的措施70

与双向认证一样，在此仍分为单钥加密和公钥加密两种情况来考虑。单向认证的加密方案711.单钥加密对诸如电子邮件等单向通信来说，无中心的密钥分配情况不适用。因为该方案要求发送方给接收方发送一请求，并等到接收方发回一个包含会话密钥的应答后，才向接收方发送消息，所以本方案与接收方和发送方不必同时在线的要求不符。3.2单向认证的单钥加密72

在图5.1所示的情况中去掉第④步和第⑤步就可满足单向通信的两个要求。协议如下：①A→KDC：IDA‖IDB‖N1②KDC→A：EKA[KS‖IDB‖N1‖EKB[KS‖IDA]]③A→B：EKB[KS‖IDA]‖EKS[M]单向认证的单钥加密73

本协议不要求B同时在线，但保证了只有B能解读消息，同时还提供了对消息的发方A的认证。然而本协议不能防止重放攻击，为此需在消息中加上时戳，但由于电子邮件处理中的延迟，时戳的作用极为有限。单向认证的单钥加密742.公钥加密公钥加密算法可对发送的消息提供保密性、认证性或既提供保密性又提供认证性，为此要求发送方知道接收方的公开钥（保密性），或要求接收方知道发送方的公开钥（认证性），或要求每一方都知道另一方的公开钥。3.3单向认证的公钥加密75

如果主要关心保密性，则可使用以下方式：A→B：EPKB[KS]‖EKS[M]

其中A用B的公开钥加密一次性会话密钥，用一次性会话密钥加密消息。只有B能够使用相应的秘密钥得到一次性会话密钥，再用一次性会话密钥得到消息。这种方案比简单地用B的公开钥加密整个消息要有效得多。76

如果主要关心认证性，则可使用以下方式：

A→B：M‖ESKA[H(M)]

这种方式可实现对A的认证，但不提供对M的保密性。如果既要提供保密性又要提供认证性，可使用以下方式：

A→B：EPKB[M‖ESKA[H(M)]]单向认证的公钥加密77

后两种情况要求B知道A的公开钥并确信公开钥的真实性。为此A还需同时向B发送自己的公钥证书，表示为A→B：M‖ESKA[H(M)]‖ESKAS[T‖IDA‖PKA]或A→B：EPKB[M‖ESKA[H(M)]‖ESKAS[T‖IDA‖PKA]]

其中ESKAS[T‖IDA‖PKA]是认证服务器AS为A签署的公钥证书。单向认证的公钥加密78

在很多情况下，用户都需证明自己的身份，如登录计算机系统、存取电子银行中的账目数据库、从自动出纳机ATM(automatictellermachine)取款等。传统的方法是使用通行字或个人身份识别号PIN(personalidentificationnumber)来证明自己的身份，这些方法的缺点是检验用户通行字或PIN的人或系统可使用用户的通行字或PIN冒充用户。4.身份的零知识证明技术79

本节介绍的身份的零知识证明技术，可使用户在不泄露自己的通行字或PIN的情况下向他人证实自己的身份。身份的零知识证明技术80

交互证明系统由两方参与，分别称为证明者（prover，简记为P）和验证者（verifier，简记为V），其中P知道某一秘密（如公钥密码体制的秘密钥或一平方剩余x的平方根），P希望使V相信自己的确掌握这一秘密。交互证明由若干轮组成，在每一轮，P和V可能需根据从对方收到的消息和自己计算的某个结果向对方发送消息。比较典型的方式是在每轮V都向P发出一询问，P向V做出一应答。所有轮执行完后，V根据P是否在每一轮对自己发出的询问都能正确应答，以决定是否接受P的证明。交互证明系统81

交互证明和数学证明的区别是：数学证明的证明者可自己独立地完成证明，而交互证明是由P产生证明、V验证证明的有效性来实现，因此双方之间通过某种信道的通信是必需的。交互证明系统须满足以下要求：①完备性如果P知道某一秘密，V将接受P的证明。②正确性如果P能以一定的概率使V相信P的证明，则P知道相应的秘密。交互证明系统82

零知识证明起源于最小泄露证明。在交互证明系统中，设P知道某一秘密，并向V证明自己掌握这一秘密，但又不向V泄露这一秘密，这就是最小泄露证明。进一步，如果V除了知道P能证明某一事实外，不能得到其他任何信息，则称P实现了零知识证明，相应的协议称为零知识证明协议。身份的零知识证明技术834.1零知识证明零知识证明（zero-knowledgeproof）的思想是：证明者Peggy拥有某些知识（如某些长期没有解决的难问题的解决方法），零知识证明就是在不将该知识的内容泄露给验证者Victor的前提下，Peggy向Victor证明自己拥有该知识。首先，我们看下面Peggy和Victor之间的一段对话：84Peggy：“我可以对密文为C的消息进行解密。”Victor：“我不相信。请证明。”Peggy（糟糕的回答）：“密钥是K，您可以看到消息解密成了M。”Victor：“哈哈！现在我也知道了密钥和消息。”这里，Peggy虽然证明了自己拥有某些知识（密钥K及明文M），却向Victor泄露了这些知识。一个更好的对话是：Peggy：“我可以对加密为C的消息进行解密。”Victor：“我不相信。请证明。”Peggy（好的回答）：“让我们使用一个零知识协议，我将以任意高的概率证明我的知识（但是不会将关于消息的任何情况泄露给您）。”Victor：“好”。Peggy和Victor通过该协议……零知识证明经典实例85零知识证明经典实例

可以使用洞穴例子来解释零知识，C和D之间存在一个密门，并且只有知道咒语的人才能打开。Peggy知道咒语并想对Victor证明，但证明过程中不想泄露咒语。86零知识证明经典实例步骤如下：（1）Victor站在A点；（2）Peggy一直走进洞穴，到达C点或者D点；（3）在Peggy消失在洞穴中之后，Victor走到B点；（4）Victor随机选择左通道或者右通道，要求Peggy从该通道出来；（5）Peggy从Victor要求的通道出来，如果有必要就用咒语打开密门；（6）Peggy和Victor重复步骤（1）至（5）n次。87零知识证明协议示例88零知识洞穴分析

如果Peggy不知道这个咒语，那么只能从进去的路出来，如果在协议的每一轮中Peggy都能按Victor要求的通道出来，那么Peggy所有n次都猜中的概率是1/2n。经过16轮后，Peggy只有65536分之一的机会猜中。于是Victor可以假定，如果所有16次Peggy的证明都是有效的，那么她一定知道开启C点和D点间的密门的咒语。89图的同构

我们来再看一个零知识证明的例子。图是否同构是NP完全问题，对于一个非常大的图，判断两个图是否同构是非常困难的。对于图G1和G2，如果存在一个一一对应的函数F：F的定义域是G1的顶点集。F的值域是G2的顶点集。当且仅当[g1,g2]是G1中的一条边，[F(g1),F(g2)]才是G2中的一条边，称G1和G2同构的。假设Peggy知道图G1和G2之间同构，Peggy使用下面的协议将使Victor相信G1和G2同构：90（1）Peggy随机置换G1产生另一个图H，并且H和G1同构。因为Peggy知道G1和H同构，也就知道了H和G2同构。（2）Peggy把H送给Victor。（3）对如下两个问题Victor选择其中的一个，要求Peggy证明。但是，Victor不要求两者都证明。证明G1和H同构，或者证明G2和H同构。（4）Peggy按Victor的要求证明。（5）Peggy和Victor重复步骤（1）至（4）n次。图的同构91如果Peggy不知道G1和G2之间的同构性，Peggy就只能创造一个图或者与G1同构或者与G2同构。每一轮中Peggy只有50%的机会猜中Victor的选择。又因为Peggy在协议的每一轮都产生一个新图H，故不管经过多少轮协议Victor也得不到任何信息，他不能从Peggy的答案中了解G1和G2的同构性。图同构的零知识证明只具有理论意义，从实现来看，是不实用的。图的同构92例1哈密尔顿（Hamilton）回路

图中的回路是指始点和终点相重合的路径，若回路通过图的每个顶点一次且仅一次，则称为哈密尔顿回路，构造图的哈密尔顿回路是NPC问题。现在假定P知道图G的哈密尔顿回路，并希望向V证明这一事实，可采用如下协议：①P随机地构造一个与图G同构的图，并将交给V。②V随机地要求P做下述两件工作之一：证明图G和图同构；指出图的一条哈密尔顿回路。哈密尔顿（Hamilton）回路93③P根据要求做下述两件工作之一：证明图G和图同构，但不指出图G或图的哈密尔顿回路；指出图的哈密尔顿回路，但不证明图G和图同构。④P和V重复以上过程n次。哈密尔顿（Hamilton）回路94

协议执行完后，V无法获得任何信息使自己可以构造图G的哈密尔顿回路，因此该协议是零知识证明协议。事实上，如果P向V证明图G和图同构，这个结论对V并没有意义，因为构造图的哈密尔顿回路和构造图G的哈密尔顿回路同样困难。如果P向V指出图的一条哈密尔顿回路，这一事实也无法向V提供任何帮助，因为求两个图之间的同构并不比求一个图的哈密尔顿回路容易。哈密尔顿（Hamilton）回路95

在协议的每一轮中，P都随机地构造一个与图G同构的新图，因此不论协议执行多少轮，V都得不到任何有关构造图G的哈密尔顿回路的信息。注：两个图G1和G2是同构的是指从G1的顶点集合到G2的顶点集合之间存在一个一一映射π，当且仅当若x、y是G1上的相邻点，π(x)和π(y)是G2上的相邻点。哈密尔顿（Hamilton）回路96这里我们介绍著名的Feige-Fiat-shamir零知识身份认证协议的一个简化方案。可信赖仲裁选定一个随机模数n，n为两个大素数乘积，实际中至少为为512位或长达1024位。仲裁方产生随机数v，使x2=vmodn，即v为模n的平方剩余，且有v-1modn存在。以v作为Peggy的公钥，而后计算最小的整数s：s=sqrt(v-1)modn作为Peggy的私钥。实施身份证明的协议如下：Fiat-Shamir零知识身份认证协议简化方案97（1）用户Peggy取随机数r，这里r＜m，计算x=r2modm，把x送给Victor；（2）Victor把一个随机位b送给Peggy；（3）若b=0，则Peggy将r送给Victor；若b=1，则Peggy将y=rs

送给Victor；（4）若b=0，则Victor验证x=r2modm，从而证实Peggy知道sqrt(x)；若b=1，则Victor验证x=y2.vmodm，从而证实Peggy知道s。这是一轮鉴定，Peggy和Victor可将此协议重复t次，直到Victor相信Peggy知道s为止。4.2Fiat-Shamir零知识身份认证协议简化方案981.协议及原理在简化的Fiat-Shamir身份识别方案中，验证者V接受假冒的证明者证明的概率是1/2，为减小这个概率，将证明者的秘密改为由随机选择的t个平方根构成的一个向量y=(y1,y2,…,yt)，模数n和向量x=(y21,y22,…,y2t)是公开的，其中n仍是两个不相同的大素数的乘积。Fiat-Shamir身份识别方案99协议如下：①P随机选r(0<r<n)，计算a≡r2modn，将a发送给V。②V随机选e=(e1,e2,…,et)，其中ei∈{0,1}(i=1,2,…,t)，将e发送给P。③P计算，将b发送给V。④若，V拒绝P的证明，协议停止。⑤P和V重复以上过程k次。Fiat-Shamir身份识别协议原理1001.协议及原理设n=pq，其中p和q是两个不同的大素数，x是模n的平方剩余，y是x的平方根。又设n和x是公开的，而p、q和y是保密的。证明者P以y作为自己的秘密。已证明，求解方程x2≡amodn与分解n是等价的。因此他人不知n的两个素因子p、q而计算y是困难的。P和验证者V通过交互证明协议，P向V证明自己掌握秘密y，从而证明了自己的身份。简化的Fiat-Shamir身份识别方案101协议如下：①P随机选r(0<r<n)，计算a≡r2modn，将a发送给V。②V随机选e∈{0,1}，将e发送给P。③P计算b≡ryemodn，即e=0时，b=r；e=1时，b=rymodn。将b发送给V。④若b2≡axemodn，V接受P的证明。简化的Fiat-Shamir身份识别方案102

在协议的前3步，P和V之间共交换了3个消息，这3个消息的作用分别是：第1个消息是P用来声称自己知道a的平方根；第2个消息e是V的询问，如果e=0，P必须展示a的平方根，即r，如果e=1，P必须展示被加密的秘密，即rymodn；第3个消息b是P对V询问的应答。简化的Fiat-Shamir身份识别方案1032.协议的完备性、正确性和安全性(1)完备性如果P和V遵守协议，且P知道y，则应答b≡ryemodn应是模n下axe的平方根，在协议的第④步V接受P的证明，所以协议是完备的。Fiat-Shamir身份识别协议分析104(2)正确性假冒的证明者E可按以下方式以1/2的概率骗得V接受自己的证明：①E随机选r(0<r<n)和，计算a≡r2x-modn，将a发送给V。②V随机选e∈{0,1}，将e发送给E。③E将r发送给V。Fiat-Shamir身份识别协议分析105(2)正确性如果假冒者E欺骗V成功的概率大于2-kt，意味着E知道一个向量A=(a1,a2,…,ak)，其中aj是第j次执行协议时产生的，对这个A，E能正确地回答V的两个不同的询问E=(e1,e2,…,ek)、F=(f1,f2,…,fk)（每一元素是一向量），E≠F。由E≠F可设ej≠fj，ej和fj是第j次执行协议时V的两个不同的询问（为向量），简记为e=ej和f=fj，这一轮对应的aj简记为a。Fiat-Shamir身份识别协议分析106

所以E能计算两个不同的值，即，所以E可由求得的平方根，矛盾。Fiat-Shamir身份识别协议分析107(3)安全性协议的安全性可分别从证明者P和验证者V的角度来考虑。根据上面的讨论，假冒的证明者E欺骗V成功的概率是1/2，对V来说，这个概率太大了。为减小这个概率，可将协议重复执行多次，设执行t次，则欺骗者欺骗成功的概率将减小到2-t。Fiat-Shamir身份识别协议分析108

下面考虑P的安全性。因为V的询问是在很小的集合{0,1}中选取的，V没有机会产生其他信息，而P发送给V的信息仅为P知道x的平方根这一事实，因此V无法得知x的平方根。Fiat-Shamir身份识别协议分析109(3)安全性

Fiat-Shamir身份识别方案是对简化的Fiat

Shamir身份识别方案的推广，首先将V的询问由一个比特推广到由t个比特构成的向量，再者基本协议被执行k次。假冒的证明者只有能正确猜测V的每次询问，才可使V相信自己的证明，成功的概率是2-kt。Fiat-Shamir身份识别协议分析110

根据协议的第④步，V的验证方程是

，当时，验证方程成立，V接受E的证明，即E欺骗成功。因的概率是1/2，所以E欺骗成功的概率是1/2。Fiat-Shamir身份识别协议分析111另一方面，1/2是E能成功欺骗的最好概率，否则假设E以大于1/2的概率使V相信自己的证明，那么E知道一个a，对这个a他可正确地应答V的两个询问e=0和e=1，意味着E能计算b21≡amodn和b22≡axmodn，即，因此E由即可求得x

的平方根y，矛盾。Fiat-Shamir身份识别协议分析1126.1智力扑克协议假设两个人A和B通过计算机网络进行智力扑克比赛，比赛中不用第三方做裁判。发牌者可由任一方担任，发牌过程应满足以下要求：5.其他密码协议113①任一副牌（即发给参赛人员手中的牌）是等可能的。②发给A、B手中的牌没有重复的。③每人都知道自己手中的牌，但却不知对方手中的牌。④比赛结束后，每一方都能发现对方的欺骗行为（如果有的话）。5.1智力扑克协议114

为满足这些要求，A、B之间必须以加密形式交换一些信息。在下面的协议中，加密体制可以是单钥密码也可以是公钥密码，设EA和EB、DA和DB分别表示A和B的加密变换和解密变换，在比赛结束之前，这些变换都是保密的，比赛结束后予以公布用以证明比赛的公正性。要求加密变换满足交换律，即对任意消息M有：EA(EB(M))=EB(EA(M))5.1智力扑克协议115

比赛开始前A、B协商好用以表示52张牌的消息w1,w2,…,w52，协议中设A为发牌人，并设给每人发5张牌。协议如下：①B先洗牌，然后用EB对52个消息分别加密，将加密结果EB(wi)发送给A。②A从收到的52个加密的消息中随机选5个EB(wi)，并发送给B，B用自己的解密变换DB对这5个值解密，解密后的值作为发给自己的一副牌。因为B的加密变换EB和解密变换DB都是保密的，所以A无法知道B手中的牌。智力扑克协议116③A另选5个EB(wi)，用EA加密后发送给B。④B用DB对收到的值解密后再发送给A，A用DA对收到的值解密后作为发给自己的一副牌，这是因为B发送给A的值是DB(EA(EB(wi)))=DB(EB(EA(wi)))=EA(wi)其中用到加密变换的交换律。5.1智力扑克协议117

下面考虑该协议是否满足发牌过程的4个要求。对第②个要求，B可在协议的第③步检查A发来的5个值是否和第②步发来的5个值有重复。为满足第4个要求，可在比赛结束后公开所有的加密变换和解密变换，双方都可检查对方的牌看是否有欺诈。对第①个和第③个要求来说，关键在于加密变换EB的强度，由EB(wi)可能得不出wi，但有可能得出wi的部分信息。例如，wi是一个比特串，则有可能从EB(wi)得出wi的最后一个比特，因此A可将52个值EB(w1),EB(w2),…,EB(w52)分成两个子集，A在发牌时可将发给B的牌集中在某一子集中，因此使得第①个和第③个要求无法满足。5.1智力扑克协议118

在某些密码协议中要求通信双方在无第三方协助的情况下，产生一个随机序列，因为A、B之间可能存在不信任关系，因此随机序列不能由一方产生再通过电话或网络告诉另一方。这一问题可通过掷硬币协议来实现，掷硬币协议有多种实现方式，下面介绍其中的3种。5.2掷硬币协议1191.采用平方根掷硬币协议如下：①A选择两个大素数p、q，将乘积n=pq发送给B。②B在1和n/2之间，随机选择一个整数u，计算z≡u2modn，并将z发送给A。③A计算模n下z的4个平方根±x和±y（因A知道n的分解，所以可做到），设x′是xmodn和-xmodn中较小者，y′是ymodn和-ymodn中较小者，则由于1<u<n/2，所以u为x′和y′之一。平方根掷硬币协议120④A猜测u=x′或u=y′，或者A找出最小的i使得x′的第i个比特与y′的第i个比特不同，A猜测u的第i个比特是0还是1。A将猜测发送给B。⑤B告诉A猜测正确或不正确，并将u的值发送给A。平方根掷硬币协议121⑥A公开n的因子。因u是B随机选取的，A不知道u，所以要猜测u只能是计算模n下z的4个平方根，猜中的概率是12。再考虑B如何能欺骗A，如果B在A猜测完后能够改变u的值，则A的猜测必不正确，A可通过

检查出B是否改变了u的值，所以B要想改变u的值就只能在x′和y′之间进行。而B若掌握x′和y′，就可通过gcd{x′-y′,n}或gcd{x′+y′,n}求出p和q，说明B的欺骗与分解n是等价的。平方根掷硬币协议122

例2本例是采用平方根掷硬币的一个具体实现过程：①A取p=3,q=7，将n=21发送给B。②B在1和21/2之间，随机选择一个整数u=2，计算z≡22modn≡4并将z=4发送给A。③A计算模21下z=4的4个平方根x=2,-x=19,y=5,-y=16，取x′=2，y′=5。平方根掷硬币协议123④A猜测u=5并将猜测发送给B\.⑤B告诉A猜测不正确，并将u=2发送给A，A检验u=2在1和21/2之间且满足4≡22mod21，A知道自己输了。⑥A公开n=21的因子p=3,q=7，B检验n=pq，知道自己赢了。平方根掷硬币协议1242.利用单向函数掷硬币设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可通过

检查出来。单向函数掷硬币协议1253.利用二次剩余掷硬币设n是两个大素数p、q的乘积，即n=pq。整数a满足0<a<n和gcd(a,n)=1，则有一半的a，其Jacobi符号，而在满足

的所有a中，只有一半是模n的平方剩余，而判断a是否为模n的平方剩余与分解n是等价的。二次剩余掷硬币协议126协议如下：①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可求出amodn的4个平方根（如果a是模n的平方剩余），以检查B是否在A猜测