崔永泉第三讲身份认证协议与机制课件

崔永泉第三讲身份认证协议与机制41.1网络安全模型与任务1.2信息安全支撑框架1.3密码协议的概念1.4协议的分类1密码协议51.1网络安全模型61.1网络安全的基本任务①设计一个算法，执行安全相关的转换②生成该算法的秘密信息③研制秘密信息的分布与共享的方法④设定两个责任者使用的协议，利用算法和秘密信息取得安全服务。71.1网络安全模型与任务1.2信息安全支撑框架1.3密码协议的概念1.4协议的分类1密码协议81.2信息安全保障的技术支柱91.2安全技术的层次*密码算法–encryptionalgorithms,digitalsignatures,etc.*安全协议–keyagreementprotocols,authenticationprotocols,etc.*安全的结构Securityarchitecture–designofasecuritysystem*安全的基础设施Securityinfrastructure–Servesbackboneofvarioussystemsandprovidessecurityservicestothesesystems101.1网络安全模型与任务1.2信息安全支撑框架1.3密码协议的概念1.4协议的分类1密码协议111.3协议的概念协议指的是双方或多方通过一系列规定的步骤来完成某项任务。协议的含义：–

第一，协议自开始至终是有序的过程，每一步骤必须依次执行。–

第二，协议至少需要两个参与者–

第三，通过执行协议必须完成某项任务。121.3协议的其它特点协议的每一方必须事先知道此协议及要执行的步骤协议涉及的每一方必须同意遵守协议协议必须是非模糊的协议必须是完整的每一步的操作要么是由一方或多方进行计算，要么是在各方之间进行消息传递131.3算法、协议和密码协议算法、协议、密码协议*算法(Algorithm)：一系列步骤，完成一项任务。*协议(Protocol)：一系列步骤，它包括两方或多方，设计它的目的是要完成一项任务。–

协议中的每个人都必须了解协议，并且预先知道所要完成的步骤；–

协议中的每个人都必须同意并遵循它；–

协议必须是清楚的，每一步必须明确定义，并且不会引起误解；–

协议必须是完整的，对每种可能的情况必须规定具体的动作；*密码协议(CryptographicProtocol)：是使用密码学的协议–

参与该协议的伙伴可能是朋友和完全信任的人，或者也可能是敌人和互相完全不信任的人。–

包含某种密码算法，但通常协议的目的不仅仅是为了简单的秘密性；–

参与协议的各方可能为了计算一个数值想共享他们的秘密部分、共同产生随机系列，确定互相的身份或者同时签署合同。–

使用密码的目的是防止或发现窃听者和欺骗。141.1网络安全模型与任务1.2信息安全支撑框架1.3密码协议的概念1.4协议的分类1密码协议151.4协议类型*仲裁协议*裁决协议*自动执行协议161.4仲裁协议仲裁者是在完成协议的过程中，值得信任的公正的第三方–

“公正”意味着仲裁者在协议中没有既得利益，与参与协议的任何人也没有特别的利害关系。–

“值得信任”表示协议中的所有人都接受这一事实，即仲裁者所说的都是真实的，所做的都是正确的。仲裁者能帮助互不信任的双方完成协议；律师、银行、公正人171.4仲裁协议例子Alice要卖车给不认识的Bob，Bob想用支票付帐，但Alice不知道支票的真假。同样，Bob也不相信Alice，在没有获得所有权前，不愿意将支票交与Alice.Alice将车的所有权交给律师

Bob将支票交给AliceAlice在银行兑现支票在支票兑现无误后，律师将车的所有权交给Bob，若在规定的时间内支票不能兑现，Alice将出示证据给律师，律师将车的所有权和钥匙交还给Alice181.4裁决协议裁决协议协议包括两个低级的子协议：一个是非仲裁子协议，执行协议的各方每次想要完成的，另一个是裁决子协议，仅在例外的情况下，即有争议的时候才执行，这种特殊的仲裁者叫裁决人。法官191.4裁决协议例子非仲裁子协议①A和B谈判合同的条款②A签署合同③B签署合同裁决子协议（仅在有争议时执行）：①A和B出现在法官面前②A提出她的证据③B也提出她的证据④法官根据证据裁决201.4自动执行协议协议本身就保证了公平性，不需要仲裁者来完成协议，也不需要裁决者来解决争端。211.4对协议的攻击攻击目标–

攻击协议使用的密码算法和密码技术–

攻击协议本身攻击方式–

被动攻击：与协议无关的人能窃听协议的一部分或全部。–

主动攻击：改变协议以便对自己有利。假冒、删除、代替、重放研究目标：假设密码算法和密码技术都是安全的，只关注协议本身的攻击221.4密码协议使用密码的具有安全性功能的协议称为安全协议或密码协议.根据协议的功能:①密钥建立协议(keyestablishmentprotocol):建立共享秘密②鉴别协议(authenticationprotocol):向一个实体提供对他想要进行通信的另一个实体的身份的某种程度的确认.③鉴别的密钥建立协议(authenticatedkeyestablishmentprotocol):与另一个身份已被或可被证实的实体之间建立共享秘密.④……231密码协议2身份认证协议3基于非密码的认证4基于密码算法的认证5零知识证明协议第3讲身份认证协议与机制242.1身份认证概念2.2身份认证的目标2.3身份认证的分类2.4身份认证的途径2身份认证协议252.1安全的信息交换应满足的性质*保密性（Confidentiality）*完整性（Integrity）数据完整性，未被未授权篡改或者损坏––

系统完整性，系统未被非授权操纵，按既定的功能运行*可用性（Availability）**鉴别鉴别（（AuthenticityAuthenticity））–

实体身份的鉴别，适用于用户、进程、系统、信息等*不可否认性（Non-repudiation）–

防止源点或终点的抵赖262.1身份认证概述

为了保护网络资源及落实安全政策。需要提供可追究责任的机制，这里涉及到三个概念：认证、授权及审计。用户对资源的访问过程

访问控制用户身份认证资源授权数据库审计数据库272.1身份认证概述（续）认证与以下环境有关：某一成员（声称者）提交一个主体的身份并声称他是那个主体，认证能使别的成员（验证者）获得对声称者所声称的事实的信任。身份认证的作用对抗假冒攻击确保身份，明确责任

鉴别是最重要的安全服务之一。鉴别服务提供了关于某个实体身份的保证。（所有其它的安全服务都依赖于该服务）282.1实体鉴别的例子*263的邮件登录*sina的邮件登录*Client与Proxy-Server之间的鉴别*Telnet远程登录*POP3邮件登录*Ftp服务292.1身份认证概述对身份认证过程中攻击：数据流窃听(Sniffer)：由于认证信息要通过网络传递，并且很多认证系统的口令是未经加密的明文，攻击者通过窃听网络数据，就很容易分辨出某种特定系统的认证数据，并提取出用户名和口令。拷贝/重传：非法用户截获信息，然后再传送给接收者。修改或伪造：非法用户截获信息，替换或修改信息后再传送给接收者，或者非法用户冒充合法用户发送信息。302.1身份认证概念2.2身份认证的目标2.3身份认证的分类2.4身份认证的途径2身份认证协议312.2实体鉴别的需求和目的某一成员（声称者）提交一个主体的身份并声称它是那个主体。*实体鉴别目的：使别的成员（验证者）获得对声称者所声称的事实的信任。322.2实体鉴别的目的和过程*实体鉴别（身份鉴别）：某一实体确信与之打交道的实体正是所需要的实体。只是简单地鉴别实体本身的身份，不会和实体想要进行何种活动相联系。*在实体鉴别中，身份由参与某次通信连接或会话的远程参与者提交。这种服务在连接建立或在数据传送阶段的某些时刻提供，使用这种服务可以确信(仅仅在使用时间内):一个实体此时没有试图冒充别的实体，或没有试图将先前的连接作非授权地重放。332.2实体鉴别与消息鉴别的差别*实体鉴别一般都是实时的，消息鉴别一般不提供时间性。*实体鉴别只证实实体的身份，消息鉴别除了消息的合法和完整外，还需要知道消息的含义。*数字签名主要用于证实消息的真实来源。但在身份鉴别中消息的语义是基本固定的，一般不是“终生”的，签名是长期有效的。342.2实体鉴别实现安全目标的方式①作为访问控制服务的一种必要支持，访问控制服务的执行依赖于确知的身份（访问控制服务直接对达到机密性、完整性、可用性及合法使用目标提供支持）；②作为提供数据起源认证的一种可能方法（当它与数据完整性机制结合起来使用时）；③作为对责任原则的一种直接支持，例如，在审计追踪过程中做记录时，提供与某一活动相联系的确知身份。352.1身份认证概念2.2身份认证的目标2.3身份认证的分类2.4身份认证的途径2身份认证协议362.3实体鉴别分类-i*实体鉴别可以分为本地和远程两类。*本地多用户鉴别：实体在本地环境的初始化鉴别（就是说，作为实体个人，和设备物理接触，不和网络中的其他设备通信）。–

需要用户进行明确的操作*远程用户鉴别：连接远程设备、实体和环境的实体鉴别。–

通常将本地鉴别结果传送到远程。（1）安全（2）易用372.3实体鉴别分类-ii实体鉴别分类-ii实体鉴别可以是单向的也可以是双向的。–

单向鉴别是指通信双方中只有一方向另一方进行鉴别。双向鉴别是指通信双方相互进行鉴别。–382.1身份认证概念2.2身份认证的目标2.3身份认证的分类2.4身份认证的途径2身份认证协议392.4实体鉴别系统的组成*一方是出示证件的人，称作示证者P(Prover)，又称声称者(Claimant)。*另一方为验证者V（Verifier),检验声称者提出的证件的正确性和合法性，决定是否满足要求。*第三方是可信赖者TP（Trustedthirdparty)，参与调解纠纷。*第四方是攻击者，可以窃听或伪装声称者骗取验证者的信任。402.4实体鉴别系统的鉴别模型412.4对身份鉴别系统的要求（1）验证者正确识别合法申请者的概率极大化。（2）不具有可传递性（Transferability)（3）攻击者伪装成申请者欺骗验证者成功的概率要小到可以忽略的程度（4）计算有效性（5）通信有效性（6）秘密参数能安全存储（7）交互识别（8）第三方的实时参与（9）第三方的可信赖性（10）可证明的安全性422.4实现身份鉴别的途径*三种途径之一或他们的组合（1）所知（Knowledge）:密码、口令（2）所有（Possesses):身份证、护照、信用卡、钥匙（3）个人特征：指纹、笔迹、声纹、手型、血型、视网膜、虹膜、DNA以及个人动作方面的一些特征设计依据：安全水平、系统通过率、用户可接受性、成本等431密码协议2身份认证协议3基于非密码的认证4基于密钥的认证5零知识证明协议第3讲身份认证协议与机制443.1基于口令的机制3.2一次性口令3.3询问-应答机制3.4基于地址的认证3.5基于个人特征的认证机制3.6个人鉴别令牌3非密码的身份认证机制453.1.1常见口令机制3.1.2基于口令机制的攻击3.1.3口令机制的改进方案3.1基于口令的认证机制463.1.1常见口令机制口令或通行字机制是最广泛研究和使用的身份鉴别法。通常为长度为5~8的字符串。选择原则：易记、难猜、抗分析能力强。口令系统有许多脆弱点：

外部泄露

口令猜测

线路窃听

危及验证者

重放473.1.1对付外部泄露的措施教育、培训；严格组织管理办法和执行手续；口令定期改变；每个口令只与一个人有关；输入的口令不再现在终端上；使用易记的口令，不要写在纸上。483.1.1对付口令猜测的措施教育、培训；严格限制非法登录的次数；口令验证中插入实时延迟；限制最小长度，至少6~8字节以上防止用户特征相关口令，口令定期改变；及时更改预设口令；使用机器产生的口令。493.1.1对付线路窃听的措施使用保护口令机制：如单向函数。

qfididq比较是或不是pid声称者验证者消息50服务端的口令安全问题固定口令1）存储的口令文件以明文形式将用户口令存储在系统口令文件中口令文件需读保护和写保护2）“加密的”口令文件存储口令的单向函数值口令文件需写保护IDA,PWAB检查口令和身份窃听？存储安全？513.1.2主要缺陷及对策攻击者很容易构造一张q与p对应的表，表中的p尽最大可能包含所期望的值。随机串（Salt）是使这种攻击变得困难的一种办法。在口令后使用随机数。只能保护在多台计算机上使用相同口令或在同一计算机上使用同一口令的不同用户。–

防止口令文件中出现相同口令–

无须用户额外记住两个字符，就能增加口令长度–

阻止了用硬件实现DES52服务端的口令安全问题服务器端的字典攻击：在这种攻击中，Eve只对找到口令有兴趣，并不关心用户的ID。例如，如果口令是六位数，Eve可以创建一个六位数(000000~999999)的列表，然后对每一个数使用散列函数，结果就是一个一百万个散列的列表。她就可以得到口令档案并搜索条目中的第二列，找出一个与之相匹配的。这可以被编程并且在Eve的个人计算机上脱机运行。找到匹配以后，伊夫就可以再上线，用口令来访问系统。533.1.3UNIX系统中的口令存储(1)Unix系统使用一个单向函数crypt()来加密用户的口令。Crypt()是基于DES的加密算法，它将用户输入的口令作为密钥，加密一个64bit的0/1串，加密的结果又使用用户的口令再次加密；重复该过程，一共进行25次。最后的输出为一个13byte的字符串，存放在/etc/passwd的PASSWORD域。单向函数crypt()从数学原理上保证了从加密的密文得到加密前的明文是不可能的或是非常困难的。当用户登录时，系统并不是去解密已加密的口令，而是将输入的口令明文字符串传给加密函数，将加密函数的输出与/etc/passwd文件中该用户条目的PASSWORD域进行比较，若匹配成功，则允许用户登录系统。54UNIX系统中的口令存储(2)UNIX系统使用crypt()保证系统密码的完整性。

这一函数完成被称作单向加密的功能，它可以加密一些明码，但不能够将密码转换为原来的明码。553.1.3添加一个新用户56服务端的口令安全问题：unix的crypt（）加密过程口令加盐(SaltingPasswords)第一环节：口令字段字符串的生成：s=Agen(Dsalt,Dpw)①给口令Dpw撒盐：Dpw=Asalt(Dsalt，Dpw)；②用撒盐结果做密钥：K=Dpw；③用一个64位的全0位串构造一个数据块Dp；④设循环次数：i=0；⑤对数据块加密：Dc=Acrypt(K,Dp)；⑥Dp=Dc，i=i+1；⑦如果i<25，则回到第⑤步；⑧把数据块变换成字符串：s=Atrans(Dc)；⑨返回s。57服务端的口令安全问题：unix的crypt（）加密过程第二环节：口令字段信息维护：①接收用户提供的口令Dpw；②生成一个盐值：Dsalt=Arandom()；③生成口令信息：s=Agen(Dsalt,Dpw)；④把口令信息s和Dsalt存入数据库的口令字段中。583.1.3验证用户59服务端的口令安全问题：unix的crypt（）验证过程第三环节：身份认证过程：①接收用户提供的帐户名Dname和口令Dpw；②在帐户信息数据库中检查Dname的合法性，如果合法，则找出其对应的s和Dsalt；③生成临时口令信息：sr=Agen(Dsalt,Dpw)；④如果sr与s相等，则认证成功，否则，认证失败。60服务端的口令安全问题：改进分析盐处理使字典攻击更为困难。如果原口令是六位数，盐是四位数，那么散列处理的结果就超过十位数。这就意味着伊夫现在要制作一个有10，000，000个条目的列表，并为每一个条目创建一个散列。这个散列列表也有10，000，000个条目，比较这些条目要花费很长时间。如果盐是一个很长的随机数字，盐处理是非常有效的。UNIX操作系统运用的就是这种方法的变种。61对付窃听的改进方案

qid

qid比较f是或不是声称者验证者pid消息salt62基本的对付危及验证者的措施使用单向函数

pididq比较是或不是声称者验证者pid消息fqsalt63对付窃听及危及验证者的措施

声称者fqidgidr比较是或不是pidr验证者消息saltsalt64对付重放攻击的措施抵抗对通信线路的主动攻击——重放攻击。

ridtgfidqg比较是或不是p声称者验证者消息qidtsalt653.1基于口令的机制3.2一次性口令3.3询问-应答机制3.4基于地址的认证3.5基于个人特征的认证机制3.6个人鉴别令牌3非密码的身份认证机制663.2一次性口令机制一次性口令机制确保在每次认证中所使用的口令不同，以对付重放攻击。确定口令的方法：

（1）两端共同使用一个随机序列生成器，在该序列生成器的初态保持同步；

（2）使用时戳，两端维持同步的时钟。67一次口令一次口令的共享列表用户和系统都同意一个口令列表。一次使用一个。如果用户不按次序使用口令，系统就要执行一个长的搜索才能找到匹配。这个方案就使窃听和口令的重复使用毫无用处了。存储保护不善，会导致所有口令泄露。顺序更新一次口令初始口令P1，这个口令仅在第一次访问时有效。访问的过程中，用户用P1作为密钥对这个口令加密产生新口令P2，作为第二次访问口令。Pi用来创建Pi+1。如果Eve能够猜测出第一个口令(P1)，她就可以找出所有这一系列的口令。683.2SKEY验证程序Alice输入随机数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用完了列表上面的数后，需要重新初始化。693.2双因素动态口令卡*基于密钥/时间双因素的身份鉴别机制；*用户登录口令随时间变化，口令一次性使用，无法预测，可以有效抵御密码窃取和重放攻击行为*RSA等多家安全公司703.2双因素动态口令卡相关产品*美国RSASecurID公司推出的RSASecurID系统是当前世界领的双因素身份鉴别系统。形成了硬件令牌、虚拟令牌（软件令牌）、与智能卡相结合的令牌等系列产品。鉴别服务器可运行于Windows/95/98/2000、Windows/NT、UNIX等环境。*美国另一家公司Axend(现被Symantec公司兼并)是较早推出双因素身份认证系统的公司。Axend的产品不仅可运行于Windows/95/98/2000、Windows/NT、UNIX等环境，还能运行于Netwarex系统，适应我国证券行业的需要。*我国一些信息技术公司也相继推出了动态口令认证系统。如网泰金安信息技术公司、北京亿青创新信息技术有限公司等。713.2双因素动态口令卡例子723.2双因素动态口令卡原理分析733.2安全性分析（1）没有器件而知道口令p，不能导致一个简单的攻击；（2）拥有器件而不知道口令p，不能导致一个简单的攻击；（3）除非攻击者也能进行时间同步，否则重放不是一个简单的攻击；（4）知道q（例如通过浏览验证者系统文件）而不知道设备安全值dsv，不能导致一个简单的攻击。743.3询问—应答机制

询问—应答原理可以扩张基于口令的方案，能大大地提高抵抗重放攻击的能力，但通常通信代价很高。*前面所示的对付重放攻击的机制存在两个重要的问题。一个是为了两端都知道nrv值需要维持同步。另一个是验证者要知道nrv值是否被重复使用过是比较困难的。*询问—应答方法克服了这些问题。753.3询问—应答机制763.4基于地址的机制基于地址的机制假定声称者的可鉴别性是以呼叫的源地址为基础的。在大多数的数据网络中，呼叫地址的辨别都是可行的。在不能可靠地辨别地址时，可以用一个呼叫—回应设备来获得呼叫的源地址。一个验证者对每一个主体都保持一份合法呼叫地址的文件。这种机制最大的困难是在一个临时的环境里维持一个连续的主机和网络地址的联系。地址的转换频繁、呼叫—转发或重定向引起了一些主要问题。基于地址的机制自身不能被作为鉴别机制，但可作为其它机制的有用补充。773.5基于个人特征的机制生物特征识别技术主要有：

1）指纹识别；

2）声音识别；

3）手迹识别；

4）视网膜扫描；

5）手形。

这些技术的使用对网络安全协议不会有重要的影响。783.6个人鉴别令牌物理特性用于支持认证“某人拥有某东西”，但通常要与一个口令或PIN结合使用。这种器件应具有存储功能，通常有键盘、显示器等界面部件，更复杂的能支持一次性口令，甚至可嵌入处理器和自己的网络通信设备（如智能卡）。这种器件通常还利用其它密码鉴别方法。791身份认证概述2身份认证协议与结构3基于非密码的认证4基于密码算法的认证5零知识证明协议第3讲身份认证协议与机制804基于密码算法的强鉴别协议*强鉴别（strongauthentication):通过密码学的询问-应答(challenge-response)协议实现的身份鉴别，询问-应答协议的思想是一个实体向另一个实体证明他知道有关的秘密知识，但不向验证者提供秘密本身。这通过对一个时变的询问提供应答来实现，应答通常依赖于实体的秘密和询问。询问通常是一个实体选择的一个数（随机和秘密地）。814基于密码算法的强鉴别协议821身份认证概述2身份认证协议与结构3基于非密码的认证4基于密码算法的认证5零知识证明协议第3讲身份认证协议与机制835零知识证明协议*下面是一个故事：*Alice:“我知道联邦储备系统计算的口令”*Bob:“不，你不知道”*Alice：我知道*Bob：你不知道*Alice：我确实知道*Bob：请你的证实这一点*Alice：好吧，我告诉你。（她悄悄说出了口令）*Bob：太有趣了！现在我也知道了。我要告诉《华盛顿邮报》*Alice：啊呀！845零知识证明协议*P为示证者(Prover),V为验证者，P试图向V证明自己知道某信息。–P告诉V这一信息使得V相信，这样V也知道了这一信息，这是基于知识的证明；–

通过某种有效的数学方法，使得V相信P掌握这一信息，却不泄漏任何有用的信息，这种方法称为零知识证明问题。*最小泄漏证明（MinimumDisclosureProof)*零知识证明(ZeroKnowledgeProof)855零知识证明协议*P几乎不可能欺骗V：如果P知道证明，他可以使V以极大的概率相信他知道证明；如果P不知道证明，则他使得V相信他知道证明的概率几乎为零。*V几乎不可能知道证明的知识，特别是他不可能向别人重复证明过程。*V无法从P那里得到任何有关证明的知识。（零知识证明满足全部三个条件）865零知识证明协议（1）V站在A点；（2）P进入山洞，走到C点或D点；（3）当P消失后，V进入到B点；（4）V指定P从左边或右边出来；（5）P按照要求出洞（如果需要通过门，则使用咒语）（6）P和V重复步骤（1）至（5）n次。87挑战-应答身份鉴别协议若P不知咒语，则在B点，只有50%的机会猜中V的要求，协议执行n次，则只有2-n的机会完全猜中，若n=16，则若每次均通过Bob的检验，V受骗机会仅为1/65536。如果V用摄像机记录下他所看到的一切，他把录像给Carol看，Carol会相信这是真的吗？Carol是不会相信这是真的。这说明了两件事情：其一，V不可能使第三方相信这个证明；其二，它证明了这个协议是零知识的。V在不知道咒语的情况下，显然不能从录像中获悉任何信息。88挑战-应答身份鉴别协议零知识(Zero-knowledge)(ZK)证明:是一种交互式证明系统声称者（证明者）和验证者交换多个信息，这些信息的生成依赖于保密的随机数证明者P(Prover)：知道某一秘密s，使V相信自己掌握这一秘密；验证者V(Verifier)：验证P掌握秘密s每轮V向P发出一询问，P向V作应答（需要有s的知识才能正确应答）。V检查P是否每一轮都能正确应答。89挑战-应答身份鉴别协议交互证明与数学证明的区别数学证明：证明者可自己独立完成证明(绝对)交互证明：由P产生证明(响应)，V验证证明(响应）的有效性（概率上）来实现，双方之间要有通信交互系统应满足完备性：如果P知道某一秘密，V将接收P的证明正确性：如果P能以一定的概率使V相信P的证明，则P知道相应的秘密（冒充者伪造成功的概率可忽略不计）90挑战-应答身份鉴别协议Needham-Schroeder协议：是基于对称密钥加密的挑战-响应计算模n平方根的困难性Fiat-Shamir身份识别协议Fiege-Fiat-Shamir身份识别协议离散对数的困难性：Schnorr协议91挑战-应答身份鉴别协议参数的选择：可信中心T选择两个素数p和q(保密，最好用完丢弃)，计算类似RSA的模数m=p×q、并公开m。证明者选择与m互素的私钥s(1≦s<m)，计算v=s2modm证明者在可信中心T中注册公钥v2Fiat-Shamir身份识别协议92挑战-应答身份鉴别协议协议执行：迭代t轮(连续地、独立地)(1)Alice取随机数r(<m)，计算x=r2modm，并发送给Bob；(2)Bob将一随机比特e=0或1作为挑战发给Alice；(3)Alice计算响应值y并发给Bob若e=0，则Alice将y=r送给Bob；若e=1，则Alice将y=r×smodm送给Bob；(4)若y=0，则Bob拒绝证明；反之，验证y2≡x×vemodm？若e=0，则Bob证实y2=x

modm若e=1，则Bob证实y2=x×vmodm

若t轮都成功，则Bob就接收Alice的身份Fiat-Shamir身份识别协议93挑战-应答身份鉴别协议完备性如果Alice和Bob遵守协议，且Alice知道s，则响应值y2=(r×se)2modm≡x×vemodm，Bob接收Alice的证明，所以协议是完备的。正确性Alice不知道s，他也可取r，送y2

=r2modm给Bob；Bob送e给Alice；Alice将r作为响应值；当b=0时则Alice可通过检验使得Bob受骗，当b=1时，则Bob可发现Alice不知s。Bob受骗概率为1/2，但连续t轮受骗的概率将仅为2-tBob无法知道Alice的秘密(s)，因为s没有被传送过，且Bob只能随机选取一个比特位作为挑战。94挑战-应答身份