第七章数字签名和密码协议 主讲教师：董庆宽 研究方向：密码学与信息安全

Presentation on theme: "第七章数字签名和密码协议 主讲教师：董庆宽 研究方向：密码学与信息安全"— Presentation transcript:

1 第七章数字签名和密码协议 主讲教师：董庆宽 研究方向：密码学与信息安全 Email ：qkdong@mail.xidian.edu.cn
本科生必修课：现代密码学 第七章数字签名和密码协议 主讲教师：董庆宽 研究方向：密码学与信息安全 个人主页：

2 本章提要 7.1 数字签字的基本概念 7.2 数字签字标准 7.3 其它签字方案 7.4 认证协议 7.5 身份证明技术
7.6 其它密码协议

3 7.1 数字签字的基本概念 数字签名由公钥密码发展而来，它在网络安全方面具有重要的应用，包括 本章重点学习 身份认证 数据完整性 不可否认性
匿名性等 本章重点学习 数字签名的基本概念和一些常用的数字签名算法 身份认证协议、身份证明技术

4 7.1.1 数字签字应满足的要求 普通的基于对称密钥的消息认证方法存在重要缺陷 通信双方之间可能有多种形式的欺骗
数字签字应满足的要求 普通的基于对称密钥的消息认证方法存在重要缺陷 消息认证虽然可以保护通信双方以防第三方的攻击，然而却不能保护通信双方中的一方防止另一方的欺骗或伪造 通信双方之间可能有多种形式的欺骗 例如通信双方A和B（设A为发方，B为收方）使用消息认证码的基本方式通信，则可能发生以下欺骗： ① B伪造一个消息并使用与A共享的密钥产生该消息的认证码，然后声称该消息来自于A。 ② 由于B有可能伪造A发来的消息，所以A就可以对自己发过的消息予以否认。数字签名可提供消息的不可否认性

5 7.1.1 数字签字应满足的要求 这两种欺骗在实际的网络安全应用中都有可能发生
数字签字应满足的要求 这两种欺骗在实际的网络安全应用中都有可能发生 例如在电子资金传输中，收方增加收到的资金数，并声称这一数目来自发方。 又如用户通过电子邮件向其证券经纪人发送对某笔业务的指令，以后这笔业务赔钱了，用户就可否认曾发送过相应的指令。 在收发双方未建立起完全的信任关系且存在利害冲突的情况下，单纯的消息认证就显得不够。 数字签名技术则可有效解决这一问题。

6 类似于手书签名，数字签名应具有以下性质：
① 能够验证签名产生者的身份，以及产生签名的日期和时间 ② 能用于证实被签消息的内容 ③ 数字签名可由第三方验证，从而能够解决通信双方的争议 由此可见，数字签名具有认证功能

7 为实现上述3条性质，数字签名应满足以下要求：
① 签名的产生必须使用发方独有的一些信息以防伪造和否认 ② 签名的产生应较为容易 ③ 签名的识别和验证应较为容易 ④ 对已知的数字签名构造一新的消息或对已知的消息构造一假冒的数字签名在计算上都是不可行的

8 7.1.2 数字签名的产生方式 数字签名的产生可用加密算法或特定的签名算法 1. 由加密算法产生数字签名 (1) 单钥加密
数字签名的产生方式 数字签名的产生可用加密算法或特定的签名算法 1. 由加密算法产生数字签名 是指将消息或消息的摘要加密后的密文作为对该消息的数字签名 其用法又根据是单钥加密还是公钥加密而有所不同 (1) 单钥加密 如图：基于共享密钥加解密，密文即为签名 如果加密的是消息摘要或有消息冗余，则可提供消息源认证和完整性认证 严格来说，不能称为签名，不具备签名的要求①

9 (2) 公钥加密 如图1(b)所示，发送方A使用自己的秘密钥SKA对消息M加密后的密文作为对M的数字签名，
B使用A的公开钥PKA对消息解密，由于只有A才拥有加密密钥SKA，因此可使B相信自己收到的消息的确来自A。 然而由于任何人都可使用A的公开钥解密密文，所以这种方案不提供保密性 加密的消息应该是消息摘要或有消息冗余 为提供保密性，A可用B的公开钥再一次加密，如图1(c)所示。

10 下面以RSA签名体制为例说明数字签名的产生过程 ① 体制参数
选两个保密的大素数p和q，计算n=p×q，(n)=(p-1)(q-1) 选一整数e，满足1<e<φ(n)，且gcd(φ(n),e)=1 计算d，满足d·e≡1 mod φ(n) 以{e,n}为公开钥,{d,p,q}为秘密钥 ② 签名过程 设消息为M，对其签名为：S≡M d mod n ③ 验证过程 接收方在收到消息M和签名S后，验证M≡Se mod n是否成立，若成立，则发送方的签名有效 实际应用时，数字签名是对消息摘要加密产生，而不是直接对消息加密产生，如图6.3(a)~图6.3(d)所示

11 由加密算法产生数字签名又分为外部保密方式和内部保密方式
外部保密方式是指数字签名是直接对需要签名的消息生成而不是对已加密的消息生成，否则称为内部保密方式。外部保密也可说是先签名再加密，而后者是先加密再签名 外部保密方式便于解决争议，因为第3方在处理争议时，需得到明文消息及其签名 如果采用内部保密方式，第3方必须得到消息的解密密钥后才能得到明文消息。如果采用外部保密方式，接收方就可将明文消息及其数字签名存储下来以备以后万一出现争议时使用

12 2. 由签名算法产生数字签名 签名算法的输入是明文消息M和密钥x， 输出是对M的数字签名，表示为S=Sigx(M)
相应于签名算法，有一验证算法，表示为Ver(S,M)，其取值为 Ver(S,M)＝ 算法的安全性在于从M和S难以推出密钥x或伪造一个消息M，使M和S可被验证为真。

13 7.1.3 数字签名的执行方式 数字签名的执行方式有两类： 直接方式和具有仲裁的方式 1. 直接方式(缺少监督的方式)
数字签名的执行方式 数字签名的执行方式有两类： 直接方式和具有仲裁的方式 1. 直接方式(缺少监督的方式) 直接方式是指数字签名的执行过程只有通信双方参与，并假定双方有共享的秘密钥或接收一方知道发方的公开钥 直接方式的数字签名有一公共弱点，即方案的有效性取决于发方秘密钥的安全性

14 如果发方想对已发出的消息予以否认，就可声称自己的秘密钥已丢失或被窃，因此自己的签名是他人伪造的
可采取某些行政手段，虽然不能完全避免但可在某种程度上减弱这种威胁 例如，要求每一被签名的消息都包含有一个时戳（日期和时间）并要求密钥丢失后立即向管理机构报告 这种方式的数字签名还存在发方的秘密钥真的被偷的危险 例如敌手在时刻T偷得发方的秘密钥，然后可伪造一消息，用偷得的秘密钥为其签名并加上T以前的时刻作为时戳

15 2. 具有仲裁方式的数字签名 可解决直接方式的缺陷 具有仲裁方式的数字签名也有很多实现方案，这些方案都按以下方式运行：
①发方X对发往收方Y的消息签名后，将消息及其签名先发给仲裁者A ②A对消息及其签名验证完后，再连同一个表示已通过验证的指令一起发往收方Y 此时由于A的存在，X无法对自己发出的消息予以否认。在这种方式中，仲裁者起着重要的作用，并应取得所有用户的信任

16 以下是具有仲裁方式数字签名的几个实例 【例7－1】 签名过程如下： 其中X表示发方，Y表示收方，A是仲裁者，M是消息
X→Y： M表示X给Y发送一消息M 【例7－1】 签名过程如下： ① X→A：M‖EKXA[IDX‖H(M)] ② A→Y：EKAY[IDX‖M‖EKXA[IDX‖H(M)]‖T] 其中E是单钥加密算法 KXA和KAY分别是X与A共享的密钥和A与Y共享的密钥 H(M)是M的杂凑值，T是时戳，IDX是X的身份 在①中，X以EKXA[IDX‖H(M)]作为自己对M的签名，将M及签名发往A 在②中A将从X收到的内容和IDX、T一起加密后发往Y，其中的T用于向Y表示所发的消息不是旧消息的重放。Y对收到的内容解密后,将解密结果存储起来以备出现争议时使用

17 由于Y不知KXA，因此不能直接检查X的签名，但Y认为消息来自于A因而是可信的。所以在整个过程中，A必须取得X和Y的高度信任：
在【例7－1】中如果出现争议，Y可声称自己收到的M的确来自X，并将EKAY[IDX‖M‖EKXA[IDX‖H(M)]]发给A，由A仲裁，A由KAY解密后，再用KXA对EKXA[IDX‖H(M)]解密，并对H(M)加以验证，从而验证了X的签名 由于Y不知KXA，因此不能直接检查X的签名，但Y认为消息来自于A因而是可信的。所以在整个过程中，A必须取得X和Y的高度信任： ①X相信A不会泄露KXA，并且不会伪造X的签名; ②Y相信A只有在对EKAY[IDX‖M‖EKXA[IDX‖H(M)]‖T]中的杂凑值及X的签名验证无误后才将之发给Y; ③X，Y都相信A可公正地解决争议

18 如果A已取得各方的信任，则X就能相信没有人能伪造自己的签名，Y就可相信X不能对自己的签名予以否认
严格的说，例7－1不是签字协议，仅仅是具有仲裁能力的认证协议 例7－1中消息M是以明文形式发送的，因此未提供保密性，下面两个例子可提供保密性 【例7－2】 签名过程如下： ① X→A: IDX‖EKXY[M]‖EKXA[IDX‖H(EKXY[M])] ② A→Y: EKAY[IDX‖EKXY[M]‖EKXA[IDX‖H(EKXY[M])]‖T] 其中KXY是X，Y共享的密钥，其他符号与例1相同

19 X以EKXA[IDX‖H(EKXY[M])]作为对M的签名，与由KXY加密的消息M一起发给A。
A对EKXA[IDX‖H(EKXY[M])]解密后通过验证杂凑值以验证X的签名，但始终未能读取明文M。 A验证完X的签名后，对X发来的消息加一时戳，再用KAY加密后发往Y。解决争议的方法与例1一样。 本例虽然提供了保密性，但还存在与上例相同的一个问题 即仲裁者可和发方共谋以否认发方曾发过的消息，也可和收方共谋以伪造发方的签名 这一问题可通过下例所示的采用公钥加密技术的方法得以解决

20 【例7－3】 签名过程如下： ① X→A：IDX‖ESKX[IDX‖EPKY[ESKX[M]]]
② A→Y：ESKA[IDX‖EPKY[ESKX[M]]‖T] 其中SKA和SKX分别是A和X的秘密钥，PKY是Y的公开钥，其他符号与前两例相同。 第①步中，X用自己的秘密钥SKX和Y的公开钥PKY对消息加密后作为对M的签名，以这种方式使得任何第3方（包括A）都不能得到M的明文消息 A收到X的内容后，用X的公开钥可对ESKX[IDX‖EPKY[ESKX[M]]]解密，并将解密得到的IDX与收到的IDX加以比较，从而可确信这一消息是来自于X的（因只有X有SKX） 第②步，A将X的身份IDX和X对M的签名加上一时戳后，再用自己的秘密钥加密发往Y

21 与前两种方案相比，第3种方案有很多优点。 首先，在协议执行以前，各方都不必有共享的信息，从而可防止共谋。
第二，只要仲裁者的秘密钥不被泄露，任何人包括发方就不能发送重放的消息。 最后，对任何第三方（包括A）来说，X发往Y的消息都是保密的

22 7.2 数字签名标准 数字签名标准DSS(Digital Signature Standard)是由美国NIST公布的联邦信息处理标准FIPS PUB 186 其中采用了上一章介绍的SHA和一新的签名技术，称为DSA(Digital Signature Algorithm) DSS最初于1991年公布，在考虑了公众对其安全性的反馈意见后，于1993年公布了其修改版 DSA 是算法, DSS 是标准

23 7.2.1 DSS的基本方式 首先将DSS与RSA的签名方式做一比较 RSA算法既能用于加密和签名，又能用于密钥交换

24 RSA签名中，将消息输入到一个杂凑函数以产生一个固定长度的安全杂凑值，再用发方的秘密钥加密杂凑值就形成了对消息的签名
消息及其签名被一起发给收方 收方得到消息后再产生出消息的杂凑值 且使用发方的公开钥对收到的签名解密 这样收方就得了两个杂凑值，如果两个杂凑值是一样的，则认为收到的签名是有效的

25 DSS签名也利用一杂凑函数产生消息的一个杂凑值，杂凑值连同一随机数k一起作为签名函数的输入
签名函数还需使用发送方的秘密钥SKA和供所有用户使用的一族参数，称这一族参数为全局公开钥PKG 签名函数的两个输出s和r就构成了消息的签名(s,r)。 接收方收到消息后再产生出消息的杂凑值，将杂凑值与收到的签名一起输入验证函数，验证函数还需输入全局公开钥PKG和发送方的公开钥PKA。验证函数的输出如果与收到的签名成分r相等，则验证了签名是有效的

26 数字签名算法DSA DSA是在ElGamal和Schnorr两个签名方案的基础上设计的，其安全性基于求离散对数的困难性。生成签名长度 320 bit，算法描述如下： (1) 全局公开钥 p：满足2L-1<p<2L 的大素数，其中512≤L≤1024且L是64的倍数 q：p-1的素因子，满足2159<q<2160 ，即q长为160比特。 g：g=h(p-1)/q mod p，h是满足1<h<p-1且使得h(p-1)/q mod p >1的任一整数 (2) 用户秘密钥x x是满足0<x<q的随机数或伪随机数 (3) 用户的公开钥y y≡gx mod p。

27 (4) 用户为待签消息选取的秘密数k (5) 签名过程 (6) 验证过程 k是满足0<k<q的随机数或伪随机数。
用户对消息M的签名为(r, s)，其中r≡(gk mod p) mod q s≡[k-1(H(M)+xr)] mod q，H(M)是由SHA求出的杂凑值 (6) 验证过程 设接收方收到的消息为M，签名为(r,s)。计算 w≡(s)-1 mod q,u1≡[H(M)w] mod q u2≡rw mod q, v≡[(gu1yu2) mod p] mod q 检查v=r 是否成立，若相等，则认为签名有效 这是因为若(M,r,s)=(M,r,s)，则 v≡[gH(M)wgxrw mod p] mod q ≡[g(H(M)+xr)s־¹ mod p] mod q ≡[gk mod p] mod q≡r

28 算法的框图如图7-3所示，其中的4个函数分别为
s=f1[H(M),k,x,r,q]≡[k-1(H(M)+xr)] mod q r=f2(k,p,q,g)≡(gk mod p) mod q w=f3(s,q)≡(s)-1 mod q v=f4(y,q,g,H(M),w,r)≡[(g(H(M)w) mod q y rw mod q) mod p] mod q 由于离散对数的困难性，敌手从r恢复k或从s恢复x都是不可行的

29 DSA的安全性基于离散对数，最初建议使用一个共同的模数p ；现在建议不同的工作组使用不同的 (p,q,g)
r和k-1可预计算 即签名产生过程中的运算主要是求r的模指数运算r=(gk mod p) mod q，而这一运算与待签的消息无关，因此能被预先计算 事实上，用户可以预先计算出很多r和k-1以备以后的签名使用，从而可大大加快产生签名的速度 DSA的安全性基于离散对数，最初建议使用一个共同的模数p ；现在建议不同的工作组使用不同的 (p,q,g) 注意验证者及任何其它人均不知道x和k 同一个用户所产生的两个签名不能使用相同的k，否则会泄漏x Gus Simmons 发现存在潜信道，能够泄露私钥

30 7.3. 其他签名方案 7.3.1 基于离散对数问题的数字签名体制
基于离散对数问题的数字签名体制是数字签名体制中最为常用的一类，其中包括ElGamal签名体制、DSA签名体制、Okamoto签名体制等 1. 离散对数签名体制 ElGamal、DSA、Okamoto等签名体制都可归结为离散对数签名体制的特例 (1) 体制参数 p：大素数；q：p-1或p-1的大素因子 g：gRZp*，且gq≡1(mod p)，其中gRZp*表示g是从Zp*中随机选取的，其中Zp*=Zp-{0} x：用户A的秘密钥，1<x<q y：用户A的公开钥，y≡gx(mod p)

31 (2) 签名的产生过程 对于待签名的消息m，A执行以下步骤： ① 计算m的杂凑值H(m)。
② 选择随机数k：1<k<q，计算 r≡gk(mod p)。 ③ 从签名方程ak≡b+cx(mod q)中解出s。 方程的系数a、b、c有许多种不同的选择方法，表7-1给出了这些可能选择中的一小部分，以(r, s)作为产生的数字签名。 表7-1 参数a、b、c可能的置换取值表 a b c ±r ±s H(m) ±rH(m) 1 ±H(m)s ±H(m)r ±rs

32 (3) 签名的验证过程 2.ElGamal签名体制 (1) 体制参数 接收方在收到消息m和签名(r, s)后，可以按照以下验证方程检验：
Ver(y, (r, s), m)=Ture  ra≡gbyc (mod p) 2.ElGamal签名体制 (1) 体制参数 p：大素数； g：Zp*的一个生成元； x：用户A的秘密钥，xRZp* ； y：用户A的公开钥，y≡gx(mod p)。

33 (2) 签名的产生过程 (3) 签名验证过程 对于待签名的消息m，A执行以下步骤： ① 计算m的杂凑值H(m)
② 选择随机数k：kZp*，gcd(k,p-1)=1，计算r≡gk(mod p) ③ 计算s≡k-1(H(m)-xr) (mod p-1) 以(r,s)作为产生的数字签名 注意在公开参数一样的情况下，任何两次签名的会话密钥k应不等 (3) 签名验证过程 接收方收到m和数字签名(r, s)后，先计算H(m)，并按下式验证： Ver(y, (r, s), H(m))=Ture  gH(m)≡rsyr (mod p) 正确性可由下式证明： rsyr≡grxgks≡grx+H(m)-rx≡gH(m) (mod p)

34 3. Schnorr签名体制 (1) 体制参数 (2) 签名的产生过程 p：大素数，p≥2512；
q：大素数，q|(p-1)，q≥2160； g：gRZp*,且gq≡1(mod p)； x：用户A的秘密钥，1<x<q； y：用户A的公开钥，y≡gx(mod p)。 (2) 签名的产生过程 对于待签名的消息m，A执行以下步骤： ① 选择随机数k：1<k<q，计算 r≡gk(mod p)。 ② 计算e=H(r, m)。 ③ 计算s≡xe+k(mod q)。 以(e, s)作为产生的数字签名。

35 (3) 签名验证过程 接收方在收到消息m和数字签名(e, s)后， 先计算r≡gsy-e(mod p)，
然后计算H(r,m)，并按下式验证 Ver(y, (e, s), m)=Ture  H(r,m) =e 其正确性可由下式证明：r≡gsy-e≡gxe+k-xe≡r (mod p)

36 基于大数分解问题的数字签名体制 设n是一个大合数，找出n的所有素因子是一个困难问题，称之为大数分解问题。下面介绍的两个数字签名体制都基于这个问题的困难性。 1. Fiat-Shamir签名体制 (1) 体制参数 n：n=pq，其中p和q是两个保密的大素数； k：固定的正整数； y1,y2,…,yk：用户A的公开钥，对任何i(1≤i≤k)，yi都是模n的平方剩余； x1,x2,…,xk：用户A的秘密钥，对任何i(1≤i≤k)，xi≡ mod n。

37 (2) 签名的产生过程 对于待签名的消息m，A执行以下步骤： ① 随机选取一个正整数t。
② 随机选取t个介于1和n之间的数r1,r2,…,rt，并对任何j(1≤j≤t)，计算Rj≡rj2(mod n)。 ③ 计算杂凑值H(m,R1,R2,…,Rt)，并依次取出H(m,R1,R2,…,Rt)的前kt个比特值b11,…,b1t, b21,…,b2t,…, bk1,…,bkt。 ④ 对任何j(1≤j≤t)，计算sj≡rj (mod n)。 以((b11,…,b1t, b21,…,b2t,…, bk1,…,bkt),(s1,…,st))作为对m的数字签名。

38 (3) 签名的验证过程 正确性可以由以下算式证明：
收方在收到消息m和签名((b11,…,b1t, b21,…,b2t,…, bk1,…,bkt),( s1,…,st))后，用以下步骤来验证： ① 对任何j(1≤j≤t)，计算Rj≡sj2· (mod n)。 ② 计算H(m,R1,R2,…,Rt)。 ③ 验证b11,…,b1t, b21,…,b2t,…, bk1,…,bkt是否依次是H(m,R1,R2,…,Rt)的前kt个比特。如果是，则以上数字签名是有效的。 正确性可以由以下算式证明： Rj≡sj2· (mod n)≡(rj )2· ≡rj2· ≡rj2≡Rj mod n

39 2. Guillou-Quisquater签名体制(GQ签名体制) (1) 体制参数
n：n=pq，p和q是两个保密的大素数； v：gcd(v,(p-1)(q-1))=1； x：用户A的秘密钥，xRZn*； y：用户A的公开钥，yR Zn*，且xvy≡1 mod n (2) 签名的产生过程 对于待签消息m，A进行以下步骤： ① 随机选择一个数kZn*，计算 T≡kv(mod n)。 ② 计算杂凑值： e=H(m,T)，且使1≤e<v；否则，返回步骤①。 ③ 计算s≡kxe mod n。 以(e, s)作为对m的签名。

40 (3) 签名的验证过程 正确性可由以下算式证明： 接收方在收到消息m和数字签名(e, s)后，用以下步骤来验证：
① 计算出T≡svye(mod n)。 ② 计算出e=H(m,T)。 ③ 验证：Ver(y, (e, s), m)=Ture  e=e 正确性可由以下算式证明： T≡svye(mod n)≡(kxe)vye(mod n) ≡kv(xvy)e(mod n)≡kv(mod n)≡T

41 7.3.3 基于身份的数字签字体制 1. ElGamal签字体制 (1)体制参数 体制参数与4.8.3节相同。
设q是大素数，G1,G2分别是阶为q的加法群和乘法群 e:G1×G1→G2是一个双线性映射 H1：{0,1}*→G1*和H2：G2→ {0,1}n是两个杂凑函数 sZq*是系统的主密钥，P是G1的一个生成元。 用户ID的公开钥和秘密钥分别是QID＝H1(ID) G1*和dID＝s QID

42 (2)签字的产生过程 (3)签字的验证过程 正确性可由下式证明： 对于待签字的消息m，A执行以下步骤： ①选择随机数kZq*
②计算R＝kP＝(xR,yR) ③计算S＝(H2(m)P+xRdID)k-1 以(R,S)作为产生的数字签字 (3)签字的验证过程 接收方在收到消息m和数字签字(R,S)后，先计算H2(m)，并按下式验证： Ver(QID,(R,S),H2(m))=Turee(P,P)H2(m) e(Ppub,QID)xR 正确性可由下式证明： e(R,S)=e(kP,(H2(m)P+xRdID)k-1)=e(P,P)H2(m) e(P,QID)xRs =e(P,P)H2(m) e(Ppub,QID)xR

43 7.4 认证协议 安全可靠的通信除需进行消息的认证外，还需建立一些规范的协议对数据来源的可靠性、通信实体的真实性加以认证，以防止欺骗、伪装等攻击，一般分为三个层次： 数据完整性认证：防止篡改，重排，重放等等 数据源认证：使得通信业务与具体实体捆绑认证，数据由哪个实体而来 实体认证：发起通信或访问的实体是否具有合法身份和相应权限 这些认证常常一起进行，也有时单独进行 通信之前首先进行实体认证(身份认证)，身份认证之后会协商出会话密钥用于对每个传输数据的数据源认证和完整性认证 实体认证(身份认证)包括身份证实和身份识别：

44 身份证实 身份识别 你是否是你宣称的你 验证方首先知道要验证的身份是谁，进一步证实来访或与之通信的人是否具有该身份
一般用于A和B确定通信时所用，通常的网络认证协议都是身份证实 具体技术：输入个人信息，经公式或算法运算所得结果与卡中或数据库中存储信息经公式运算所得结果比较 身份识别 我是否知道你是谁 验证方不知道来访人是否为合法身份，没有比较确定的目标，只要满足某个条件就可判定身份的特点。验证者一般为权威机构 一般在实体认证中需要， 比如判断来访者是否是在逃犯，是否为密码开启者，是否为本公司员工。通常用指纹、虹膜技术 具体技术：输入个人信息，经过处理提取模版信息，试着在存储数据库中找出一个与之匹配的模版而后得出结论

45 认证协议的典型用途是：身份认证与会话密钥协商
身份认证和密钥协商往往同时进行 如Kerberos认证系统(NS协议)、X.509、SSL、TLS、IPSec/IKE 本节以网络通信的一个基本问题的解决引出认证协议的基本意义，这一基本问题陈述如下： A和B是网络的两个用户，他们想通过网络先建立安全的共享密钥再进行保密通信。A(B)如何确信自己正在和B(A)通信而不是和C通信呢？即双方的身份认证 这种通信方式为双向通信，此时的认证称为相互认证 类似地，对于单向通信来说，认证称为单向认证 这里的认证主要是身份证实

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

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

48 时戳法不能用于面向连接的应用过程 这是由于时戳法在实现时固有的困难性
首先是需要在不同的处理器时钟之间保持同步，那么所用的协议必须是容错的以处理网络错误，并且是安全的以对付恶意攻击 第二，如果协议中任一方的时钟出现错误而暂时地失去了同步，则将使敌手攻击成功的可能性增加 最后还由于网络本身存在着延迟，因此不能期望协议的各方能保持精确的同步。所以任何基于时戳的处理过程、协议等都必须允许同步有一个误差范围。考虑到网络本身的延迟，误差范围应足够大；考虑到可能存在的攻击，误差范围又应足够小

49 询问-应答方式则不适合于无连接的应用过程
这是因为在无连接传输以前需经询问-应答这一额外的握手过程，这与无连接应用过程的本质特性不符。 对无连接的应用程序来说，利用某种安全的时间服务器保持各方时钟同步是防止重放攻击最好的方法

50 通信双方建立共享密钥时可采用单钥加密体制和公钥加密体制
1. 单钥加密体制 需要有一个可信的密钥分配中心KDC，网络中每一用户都与KDC有一共享的密钥，称为主密钥 KDC为通信双方建立一个短期内使用的密钥，称为会话密钥，并用主密钥加密会话密钥后分配给两个用户 这种分配密钥的方式在实际应用中较为普遍采用，如Kerberos系统采用的就是这种方式

51 (1) Needham-Schroeder协议
以下是1978年出现的著名的Needham-Schroeder认证协议。即为5.1节中图5-1所示的采用KDC的密钥分配过程 这里需建立一个称为鉴别服务器的可信权威机构（密钥分发中心KDC），拥有每个用户的秘密密钥 若用户A欲与用户B通信，则用户A向鉴别服务器申请会话密钥。在会话密钥的分配过程中，双方身份得以鉴别

52 协议的目的是由KDC为A、B安全地分配会话密钥KS
① 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)] 协议的目的是由KDC为A、B安全地分配会话密钥KS A在第②步安全地获得了KS 第③步的消息仅能被B解读，因此B在第③步安全地获得了KS 第④步中B向A示意自己已掌握KS，N2用于向A询问自己在第③步收到的KS是否为一新会话密钥， 第⑤步A对B的询问作出应答，一方面表示自己已掌握KS，另一方面由f(N2)回答了KS的新鲜性。 第④、⑤两步用于防止对第③步的重放攻击

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

54 (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)] 其中T是时戳，用以向A、B双方保证KS的新鲜性。A和B可通过下式检查T的实时性： |Clock-T|<Δt1+Δt2 Clock为用户（A或B）本地的时钟 Δt1是用户本地时钟和KDC时钟误差的估计值 Δt2是网络的延迟时间。

55 以上改进还存在以下问题： T是经主密钥加密的，所以敌手即使知道旧会话密钥，并在协议的过去执行期间截获第③步的结果，也无法成功地重放给B
方案主要依赖网络中各方时钟的同步，这种同步可能会由于系统故障或计时误差而被破坏 等待重放攻击：如果发送方的时钟超前于接收方的时钟，敌手就可截获发送方发出的消息，等待消息中时戳接近于接收方的时钟时，再重发这个消息 这种重放至少可以影响Ks的有效期，也可造成重复接收等问题

56 (3) Needham-Schroeder协议的改进方案之二
抗等待重放攻击 方法一：要求网络中各方以KDC的时钟为基准定期检查并调整自己的时钟 方法二：使用一次性随机数的握手协议 这就是NS协议的另一种改进方法 (3) 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] TB是B建议的证书(会话密钥)截止时间，用于截止时间前再次发起会话时KS是否可用的判别时间

57 协议的具体含义如下： ① A将新的一次性随机数NA与自己的身份IDA一起以明文形式发往B，NA以后将与会话密钥KS一起以加密形式返回给A，以保证A收到的会话密钥的新鲜性。 ② B向KDC发出与A建立会话密钥的请求，表示请求的消息包括B的身份、一次性随机数NB以及由B与KDC共享的主密钥加密的数据项。其中NB以后将与会话密钥一起以加密形式返回给B以向B保证会话密钥的新鲜性 请求中由主密钥加密的数据项用于指示KDC向A发出一个证书，其中的数据项有证书接收者A的身份、B建议的证书截止时间TB、B从A收到的一次性随机数。

58 ③ 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。 ④ A将票据EKB[IDA‖KS‖TB]连同由会话密钥加密的一次性随机数NB发往B，B由票据得到会话密钥KS，并由KS得NB。NB由会话密钥加密的目的是B认证了自己收到的消息不是一个重放,而的确是来自于A。

59 如果A保留由协议得到的票据EKB[IDA‖KS‖TB] ，就可在有效时间范围内不再求助于认证服务器而由以下方式实现双方的新认证：
① A→B：EKB[IDA‖KS‖TB]，NA ② B→A：NB ，EKS[NA] ③ A→B：EKS[NB] B在第①步收到票据后，可通过TB检验票据是否过时，而新产生的一次性随机数NA  ，NB则向双方保证了没有重放攻击 以上协议中时间期限TB是B根据自己的时钟定的，因此不要求各方之间的同步

60 2. 公钥加密体制 B的证书可省去 时戳T用以防止重放攻击，所以需要各方时钟同步
曾介绍过使用公钥加密体制分配会话密钥的方法(前提是收发双方已经互相知道对方公钥)，以下协议也用于此目的(但事先不知道彼此公钥) ① 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] 其中SKAS、SKA 分别是AS和A的秘密钥，PKA、PKB分别是A和B的公开钥，E为公钥加密算法，AS是认证服务器 时戳T用以防止重放攻击，所以需要各方时钟同步 B的证书可省去

61 第①步，A将自己的身份及欲通信的对方的身份发送给AS
第②步，AS发给A的两个链接的数据项都是由自己的秘密钥加密（即由AS签字），分别作为发放给通信双方的公钥证书 第③步，A选取会话密钥并经自己的秘密钥和B的公开钥加密后连同两个公钥证书一起发往B。因会话密钥是由A选取，并以密文形式发送给B，因此包括AS在内的任何第3者都无法得到会话密钥 时戳T用以防止重放攻击，所以需要各方时钟同步

62 下一协议使用一次性随机数，因此不需要时钟的同步：
① 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] 其中SKAU和PKAU分别是KDC的秘密钥和公开钥

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

64 第⑤步，KDC向B发出A的公钥证书以及由自己的秘密钥和B的公开钥加密的三元组{NA,KS,IDB}。三元组由KDC的秘密钥加密可使B验证三元组的确是由KDC发来的，由B的公开钥加密是防止他人得到三元组后假冒B建立与A的连接。 第⑥步，B新产生一个一次性随机数NB,连同上一步收到的由KDC的秘密钥加密的三元组一起经A的公开钥加密后发往A。 第⑦步，A取出会话密钥，再由会话密钥加密NB后发往B，以使B知道A已掌握会话密钥。 以上协议可进一步做如下改进： 在第⑤、⑥两步出现NA的地方加上IDA，以说明NA的确是由A产生的而不是其他人产生的，这时{IDA，NA}就可惟一地识别A发出的连接请求

65 以上协议稍微扩展就是著名的Kerberos协议 解决的问题：
它是工作在应用层的认证协议 解决的问题： 在一个公开的分布式环境中，工作站上的用户希望访问分布在网络中的服务器(可能是多个)上的服务 服务器希望能够限制授权用户的访问，并能对服务请求进行鉴别 Kerberos的主要功能：认证、授权、记账与审计 Kerberos系统在一个分布式的Client/Server体系机构中采用一个或多个Kerberos服务器提供一个认证服务。 Kerberos系统基于对称密钥构建，提供一个基于可信第三方的认证服务

66 Kerberos不是为每一个服务器构造一个身份认证协议，而是提供一个中心认证服务器，提供用户到服务器和服务器到用户的认证服务
该中心认证服务器执行密钥管理和控制的功能，维护一个保存所有客户密钥的数据库。 该中心认证服务器即为可信第三方 每当两个用户要进行安全通信及认证请求时，Kerberos认证服务器就产生会话密钥 Kerberos系统使用56位DES加密算法加密网络连接，并且提供用户身份的认证

67 Kerberos认证协议的体系结构图 ①和②每次登陆执行一次 ③和④每种服务执行一次 ⑤和⑥每个服务的每次会话执行一次

68

69 把西电网络看成一个提供网页、邮件、FTP、数据库等多个服务的网络
这个过程可以通过如下的例子来理解 把西电网络看成一个提供网页、邮件、FTP、数据库等多个服务的网络 那么有一个认证中心在网络中心，还有一个票据服务器用于对每一种服务的接入授权 每一个西电用户都在认证中心注册了自己的账号 现在用户Alice想要访问西电的FTP服务器，则采用如下步骤 （1）如果Alice还未登陆系统，则首先向认证中心认证，并请求访问票据许可服务器，认证中心在检验了用户身份后发给Alice一个访问票据许可服务器的票据，如果已经登陆则不需此步骤 （2）如果Alice要访问一个服务，如FTP，但还没有被授权访问，则将认证中心的票据及要访问的服务提交给票据许可服务器，认证后票据许可服务器发给Alice一个服务许可票据，用于访问FTP服务器，如果已经有有效票据则不需此步骤。 （3）用户Alice要访问FTP服务，在每次会话建立前，将服务许可票据提交给FTP服务器，验证后即可访问资源

70 7.4.2 单向认证 电子邮件等网络应用不要求收发双方同时在线 与双向认证一样，在此仍分为单钥加密和公钥加密两种情况来考虑
单向认证 电子邮件等网络应用不要求收发双方同时在线 邮件消息的报头必须是明文形式以使SMTP或X.400等存储-转发协议能够处理 SMTP（simple mail transfer protocol-简单邮件传输协议） 通常都不希望邮件处理协议要求邮件的消息本身是明文形式，否则就要求用户对邮件处理机制的信任 所以用户在进行保密通信时，需对邮件消息进行加密以使包括邮件处理系统在内的任何第3者都不能读取邮件的内容。再者邮件接收者还希望对邮件的来源即发方的身份进行认证，以防他人的假冒。 与双向认证一样，在此仍分为单钥加密和公钥加密两种情况来考虑

71 1. 单钥加密 单向通信时无中心的密钥分配情况不适用，因为需要握手
在图5-1所示的情况中去掉第④步和第⑤步就可满足单向通信的两个要求。协议如下： ① A→KDC：IDA‖IDB‖N1 ② KDC→A：EKA[KS‖IDB‖N1‖EKB[KS‖IDA]] ③ A→B：EKB[KS‖IDA]‖EKS[M] 本协议不要求B同时在线，但保证了只有B能解读消息，同时还提供了对消息的发方A的认证 然而本协议不能防止重放攻击，如第③步，为此需在消息中加上时戳，但由于电子邮件处理中的延迟，时戳的作用极为有限

72 2. 公钥加密 公钥加密算法可对发送的消息提供保密性、认证性或既提供保密性又提供认证性，为此 如果主要关心保密性，则可使用以下方式：
要求发送方知道接收方的公开钥（保密性）， 或要求接收方知道发送方的公开钥（认证性）， 或要求每一方都知道另一方的公开钥 如果主要关心保密性，则可使用以下方式： A→B：EPKB[KS]‖EKS[M] 其中A用B的公开钥加密一次性会话密钥，用一次性会话密钥加密消息。只有B能够使用相应的秘密钥得到一次性会话密钥，再用一次性会话密钥得到消息。这种方案比简单地用B的公开钥加密整个消息要有效得多。

73 如果既要提供保密性又要提供认证性，可使用以下方式：
如果主要关心认证性，则可使用以下方式： A→B：M‖ESKA[H(M)] 这种方式可实现对A的认证，但不提供对M的保密性。 如果既要提供保密性又要提供认证性，可使用以下方式： A→B：EPKB[M‖ESKA[H(M)]] 后两种情况要求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签署的公钥证书

74 7.5 身份证明技术 在很多情况下，用户都需证明自己的身份 传统的方法 身份的零知识证明技术 如登录计算机系统 存取电子银行中的账目数据库
从自动出纳机ATM(automatic teller machine)取款等 传统的方法 使用通行字(口令) 个人身份识别号PIN(personal identification number)来证明自己的身份 这些方法的缺点是检验用户通行字或PIN的人或系统可使用用户的通行字或PIN冒充用户 身份的零知识证明技术 可使用户在不泄露自己的通行字或PIN的情况下向他人证实自己的身份

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

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

77 7.5.2 简化的Fiat-Shamir身份识别方案
1. 协议及原理 设n=pq，其中p和q是两个不同的大素数 x是模n的平方剩余 y是x的平方根 n和x是公开的，而p、q和y是保密的 证明者P以y作为自己的秘密 已证明，求解方程y2≡x mod n与分解n是等价的。因此他人不知n的两个素因子p、q而计算y是困难的 P和V通过交互证明协议，P向V证明自己掌握秘密y，从而证明了自己的身份

78 在协议的前3步，P和V之间共交换了3个消息，这3个消息的作用分别是：
协议如下： ① P随机选r (0<r<n)，计算a≡r2 mod n，将a发送给V。 ② V随机选e{0,1}，将e发送给P。 ③ P计算b≡rye mod n，即e=0时，b=r；e=1时，b=ry mod n。将b发送给V。 ④ 若b2≡axe mod 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询问的应答。

79 2. 协议的完备性、正确性和安全性 (1) 完备性 (2) 正确性
如果P和V遵守协议，且P知道y，则应答b≡rye mod n应是模n下axe的平方根 在协议的第④步V接受P的证明，所以协议是完备的 (2) 正确性 假冒的证明者E可按以下方式以1/2的概率骗得V接受自己的证明： ① E随机选r(0<r<n)和e{0,1}，计算a≡r2x-e mod n，将a发送给V ② V随机选e{0,1}，将e发送给E ③ E将r发送给V 根据协议的第④步，V的验证方程是r2≡axe mod n≡r2x-exe mod n，当e=e 时，验证方程成立，V接受E的证明，即E欺骗成功

80 e=e的概率是1/2，所以E欺骗成功的概率是1/2 另一方面，1/2是E能成功欺骗的最好概率
否则假设E以大于1/2的概率使V相信自己的证明 那么E知道一个a，对这个a他可正确地应答V的两个询问e=0和e=1， 意味着E能计算b12≡a mod n和b22≡ax mod n，即b22/b12≡x mod n，因此E由b2/b1 mod n即可求得x的平方根y，矛盾。

81 (3) 安全性 协议的安全性可分别从证明者P和验证者V的角度来考虑。 V的安全性，要求验证方被骗概率可忽略 P的安全性，证明方消息无泄漏
根据上面的讨论，假冒的证明者E欺骗V成功的概率是1/2，对V来说，这个概率太大了。 为减小这个概率，可将协议重复执行多次，设执行t次，则欺骗者欺骗成功的概率将减小到2-t。 P的安全性，证明方消息无泄漏 因为V的询问是在很小的集合{0,1}中选取的，V没有机会产生其他信息，而P发送给V的信息仅为P知道x的平方根这一事实，因此V无法得知x的平方根。

82 7.5.3 零知识证明 零知识证明起源于最小泄露证明 在交互证明系统中，设P知道某一秘密，并向V证明自己掌握这一秘密，但又不向V泄露这一秘密，这就是最小泄露证明 进一步，如果V除了知道P能证明某一事实外，不能得到其他任何信息，则称P实现了零知识证明，相应的协议称为零知识证明协议

83 【例7-4】 图7-4表示一个简单的迷宫，C和D之间有一道门，需要知道秘密口令才能打开
P向V证明自己能打开这道门，但又不愿向V泄漏秘密口令

84 协议中，如果P不知道秘密口令，就只能从来路返回B，而不能走另外一条路。
①V在协议开始时停留在位置A； ②P一直走到迷宫的深处，随机选择位置C或位置D； ③P消失在迷宫中后，V走到位置B，然后命令P从某个出口返回位置B； ④P服从V的命令，必要时利用秘密口令打开C与D之间的门； ⑤P和V重复以上过程n次。 协议中，如果P不知道秘密口令，就只能从来路返回B，而不能走另外一条路。 P每次猜对V要求走哪一条路的概率是1/2，因此每一轮中P能够欺骗V的概率是1/2。 假定n取16，则执行16轮后，P成功欺骗V的概率是1/216＝1/65536。于是，如果P16次都能按V的要求返回，V即能证明P确实知道秘密口令。 还可以看出，V无法从上述证明过程中获取丝毫关于P的秘密口令的信息，所以这是一个零知识证明协议。

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

86 协议执行完后，V无法获得任何信息使自己可以构造图G的哈密尔顿回路，因此该协议是零知识证明协议。
事实上，如果P向V证明图G和图 同构，这个结论对V并没有意义，因为构造图 的哈密尔顿回路和构造图G的哈密尔顿回路同样困难。如果P向V指出图的一条哈密尔顿回路，这一事实也无法向V提供任何帮助，因为求两个图之间的同构并不比求一个图的哈密尔顿回路容易。在协议的每一轮中，P都随机地构造一个与图G同构的新图，因此不论协议执行多少轮，V都得不到任何有关构造图G的哈密尔顿回路的信息。 注：两个图G1和G2是同构的是指从G1的顶点集合到G2的顶点集合之间存在一个一一映射π，当且仅当若x、y是G1上的相邻点，π(x)和π(y)是G2上的相邻点。

87 7.5.4 Fiat-Shamir身份识别方案 1. 协议及原理 协议如下：
在简化的Fiat-Shamir身份识别方案中，验证者V接受假冒的证明者证明的概率是1/2，为减小这个概率，将证明者的秘密改为由随机选择的t个平方根构成的一个向量y=(y1,y2,…,yt)，模数n和向量x=(y12,y22,…,yt2)是公开的，其中n仍是两个不相同的大素数的乘积。 协议如下： ① P随机选r(0<r<n)，计算a≡r2 mod n，将a发送给V。 ② V随机选e=(e1,e2,…,et)，其中ei{0,1}(i=1,2,…,t)，将e发送给P。 ③ P计算b≡r mod n，将b发送给V。 ④ 若b2≠a mod n，V拒绝P的证明，协议停止。 ⑤ P和V重复以上过程k次。

88 2. 协议的完备性、正确性和安全性 (1) 完备性 (2) 正确性 若P和V遵守协议，则V接受P的证明。
如果假冒者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。所以E能计算两个不同的值 b12≡a mod n，b22≡a mod n，即b22/b12≡ mod n，所以E可由b2/b1 mod n求得 mod n的平方根，矛盾。

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

90 7.6 其他密码协议 安全协议：基于认证、加密算法和密钥以获得用户所需的安全服务 7.6.1 智力扑克协议 A加密52张牌
智力扑克协议 A加密52张牌 B选5张发给A，A解密得到自己的牌 B再选5张由A加密的牌用B的密钥加密后发给A，A用自己的密钥进行一轮脱密后发给B，B再用自己的密钥解密得到发给自己的牌 利用加密的交换性(主要是公钥密码算法)

91 7.6.2 掷硬币协议 利用单向函数掷硬币 设A,B都知道某一单向函数f(x),但都不知道该函数的逆函数，协议如下：
掷硬币协议 利用单向函数掷硬币 设A,B都知道某一单向函数f(x),但都不知道该函数的逆函数，协议如下： 1. B选一个随机数x，求y=f(x)并发送给A 2. A对x的奇偶性进行猜测，并将结果告诉B 3. B告诉A猜测正确或不正确，并将x发送给A，以供检验 这样如果A猜对了表示0，错了表示1，且由于单向函数的不可逆性，以及双方对过程的可验证性，能够公平的完成抛币

92 不经意传输协议 设A有一个秘密，想以1/2的概率传递给B，即B有50%的机会收到这个秘密，另外50%的机会什么也没有收到，协议执行完后，B知道自己是否收到了这个秘密，但A却不知B是否收到了这个秘密。这种协议就称为不经意传输协议。 例如A是机密的出售者，A列举了很多问题，意欲出售各个问题的答案，B想买其中一个问题的答案，但又不想让A知道自己买的是哪个问题的答案。

93 基于大数分解的不经意传输协议 设A想通过不经意传输协议传给B的秘密是整数n(为两个大素数之积)的因数分解。这个问题具有普遍意义，因为任何秘密都可以通过RSA加密，得到n的因数分解就可得到这个秘密 协议基于如下事实：已知某数在模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 的2个不同的平方根，从而能够分解n。而A却不知道究竟是那种情况。 显然，B得到n的分解的概率是1/2。

94 “多传一”的不经意传输协议 设A有多个秘密，想将其中一个传递给B，使得只有B知道A传递的是哪个秘密。设A的秘密是s1,s2,…,sk，每一秘密是一比特序列。协议如下： ①A告诉B一个单向函数f，但对f-1保密。 ②设B想要的到秘密si，他在f的定义域内随机选取k个值x1,x2,…,xk，将k元组(y1,y2,…,yk)发送给A，其中ji时yj=xj，j=i时yj=f(xj) ③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，因此可以解出si。 由于B没有zj(ji)的信息，无法得到其它秘密，而A不知道k元组(y1,y2,…,yk)中哪个是f(xi)，因此无法确定B得到的是哪个秘密 然而如果B不遵守协议，用f对多个xj求得f(xj)，就可获得多个秘密。因协议无法抗主动欺骗。

95 此外还有： 多方安全计算，(计算完成后不泄露各方的秘密) 小额电子支付协议SET …… …… 作业：p216：1，2