确认，使用户U和V确信他们彼此得到了相同的会话密钥K。
使用时间戳T和有效期L的目的是为了防止主动的对手的
Kerboros 密钥 分配协议的缺点是网络中所有用户的时 钟必须同步，因为当前时刻用于确定一个给定的会话密钥
是否有效。实际应用中，严格保持时钟同步是困难的，因
此允许一定的时钟误差存在。
10/37
如图
32/37
零知识洞穴
知道咒语的人才能打开门
33/37
P 向V 证明自己知道咒语的协议 ① V 停留在位置A; ② P 从位置A 走到位置B, 然后随机选择从左通道走到位 置C 或从右通道走到位置D; ③ P 消失后, V 走到位置B; ④ V 命令P 从位置C 经左通道或从位置D 经右通道返回位 置B; ⑤ P 服从V 的命令, 必要时P 可以利用咒语打开位置C 和 位置D 之间的门; ⑥ P 和V 重复执行第1 步至第5 步n 次.
26/37
Guillou-Quisquater协议
27/37
28/37
29/37
30/37
安全性：
任何知道u的人都可成功冒充A。但只 有A知道并且没有在协议执行过程中泄露，而 从 v=(u-1)b mod n 求解u相当于破译RSA公钥 密码体制。因此 Guillou - Quisquater身份识别 方案的安全性是基于RSA公钥密码体制的安 全性。
11/37
Di±e-Hellman 密钥交换协议是一个典型的密钥协商协议 ，描 述如下：
设p 是一个大素数, α ∈Zp 是一个本原元. p 和α 公开
① 用户U 随机选取aU，1 ≤ aU≤p − 2 ② 用户U 计算 并将结果传送给用户V
③ 用户V 随机选取aV，1≤aV≤p − 2 ④用户V 计算 ⑤用户U 计算 用户V 计算 并将结果传送给用户U
12/37
13/37
14/37
15/37
16/37
17/37
9. 2 秘密分享
Shamir 的(t， w) 门限方案
主要内容
18/37
9. 2. 1 Shamir 的(t，w) 门限方案
share ， 然后秘
(t,n) 密钥分享方案。
A . Shamir于1976年给出。是一种特殊的
定义9.1 设t 和w 为正整数，t ≤ w。一个(t;w) 门限方案是一 种在w 个参与者中分享一个密钥k 的方法, 使得任意t 个参 与者在给出他们的秘密份额后可以恢复密钥k, 而任意t -1 个参与者在给出他们的秘密份额后不能恢复密钥k。
9. 1. 2 密钥协商
Diffie-Hellman密钥交换协议是Whitfield Diffie和 Martin Hellman在1976年提出的一个典型的密钥协商协议。 通信双方可以在一个公开的信道上通过相互传送一些消息来 共同建立一个共享的秘密密钥。
Diffie-Hellman 密钥交换协议容易受到主动的对手的中间入侵 攻击假设W 是一个主动的对手，其中间入侵攻击如上图所示
9. 2. 2 (t，w) 门限方案中的密钥重建
可以写成矩阵的形式为
21/37
设系数矩阵为A。显然, A 是一个Vandermonde 矩阵，系数 矩阵A 的行列式为
因为
互不相同, 所以
线性方程组有唯一解，这说明任意t 个参与者能够重建密钥k。
而任t - 1 个参与者得不到密钥k的任何信息
22/37
第9章 密码协议
主讲： 刘小跃
1/37
主要内容
密钥分配与密钥协商
秘密分享. 身份识别 零知识证明
2/37
基本概念
协议(protocol): 两个或两个以上的参与者为完成某项任务所采取 1 协议的每个参与者都必须了解协议，事先知道所要完成的所 有步骤； 2 3 协议必须是清楚的，即每一步骤必须明确定义，不会引起误 4 协议必须是完整的，对每种可能的情况都要规定具体的操作 。 (cryptographic protocol) 应用密码技术构造的协议。其目的是在完成某项任务的同时， 不仅能够发现或防止协议参与者彼此之间的欺骗行为，还能避免 敏感信息被窃听者窃取或篡改。
Kerboros 密钥分配协议中消息的传送
6/37
Kerboros密钥分配协议描述
1 用户U向TA 请求一个会话密钥用于与用户V进行
2
TA随机选取一个会话密钥K，并产生一个时戳T
以及有效期L。时戳T表示TA接到请求的时间，有效
期L表示密钥K
3 TA计算 m1=EKU( k, ID(V),T,L) m2=EKV( k, ID(U),T,L)
用于证明和识别用户的合法身份。至少满足两个要 1)A能向B证明自己的确是A; 2)当A 向B证明了自己的身份后，B得不到任何用 于模仿A的有用的信息。B无法向第三者声称自己是 A。 3)Guillou-Quisquater 4) 此方案需要一个可信当局(trusted authority)，简 称TA。TA首先选取两个大素数 p,q并计算，p,q保密 ，而n公开。再选取一个大素数b作为安全参数。用 户A需要TA颁发一个证书，包含A的身份信息，是
3
1 2 个有效的共享密钥
5/37
9. 1. 1 密钥分配
(trusted authority):在利用密钥分配协议来建 立用户之间的共享密钥时，需要一个可信当局，简称TA。 TA的作用负责验证用户的身份并协助要进行保密的双方建 立一个会话密钥，譬如为用户选取并传送密钥等。
Kerboros 密钥分配协议是一种在线式密钥分配协议 (on-line key distributionprotocol)。所谓在线(on-line) 指的 是, 当两个用户U 和V 想要进行保密通信时, 就根据协议产 生一个新的密钥, 而不是事先确定一个密钥。
31/37
9. 4 零知识证明
零知识证明（zero-kno己掌握 这些秘密信息。V是检验者，V验证P是否真的掌握 这些秘密信息。P设法使V相信自己掌握这些秘密 信息的同时又不向V J.J.Quisquater和L.C.Guillou
23/37
24/37
9. 2. 3 利用Lagrange 插值公式重建(t， w) 门限方案中的密钥
过点 可以唯一地确定一个次 数至多为t-1 的多项式。 根据Lagrange 插值公式
容易验证 因为密钥k = a(0), 所以
令
则
25/37
9. 3
identification scheme
34/37
35/37
36/37
4 V验证在置换ρ 下，图 Gi 是否能变为图H。 5 P和V重复第1步至第4步n次。如果每次图 Gi都 能在置换ρ下变为图H，则V相信P能证明 G1和 G2 是同构的。
37/37
38/37
7/37
TA将 m1和 m2传送给用户。
4
用户U利用解密函数DKU对 进行解密获得K,T,L )，
以及ID(V)。然后用户U计算m3= Ek(ID(U),T
用户U将m2 和 m3传送给用户V。
5 用户V利用解密函数 Dkv对 进行解密获得 K,T,L以及ID(U)。然后用户V利用解密函数 Dk对m3 进行解密获得T和ID(U)。用户V分别检验从 m2和 m3 解密得到的T的两个值和ID(U)的两个值是否一样。
V计算m4= Ek(T+1)，用户V将 m4
传送给用户U。
8/37
6)用户U利用解密函数Dk对m4 T+1。 在 Kerboros 密钥分配协议中，用户U和V以及TA之 间在信道上传送的消息可以图示说明。
9/37
在Ke rboros密钥分配协议中传送的各种消息的功能 不同，m1和m2提供了会话密钥K的保密性；m3和m4用于密钥
19/37
设p 是一个素数, p > w + 1。 Shamir 的(t，w) 门限方案描述如下： ① D 从Zp 中选取w 个不同的非零元 D 将 分配给参与者 可以公开。 ② 如果D 要让参与者 分享一个密钥 , 则D 秘密地随机选取t -1 个元素 ③对 D 计算 其中
④D将
秘密地分配给
20/37
3/37
9. 1 密钥分配与密钥协商
密钥分配
密钥协商
(key distribution):
(key agreement): 以在一个公开的信道上通过相互传送一些消息来共同建立一个共享的 秘密密钥。
4/37
攻击
由于密钥分配和密钥协商都是在一个公开信道上进行，所
1 2 窃取通信双方在信道上传送的消息,然后在以后的