2012-3-19 1
第七章 密码协议
一,基本密码协议
二,中、高级密码协议
2012-3-19 2
一,基本密码协议
2012-3-19 3
身份认证协议
? 身 份 认 证 协 议 （ Identy Authentication
Protocols ）
Alice
Bob
Eve
Alice?
or Eve? Bob?
or Eve?
2012-3-19 4
身份认证协议
? 用户的身份认证是许多应用系统的第一道防
线，其目的在于识别用户的合法性，从而阻
止非法用户访问系统。身份识别（认证）对
确保系统和数据的安全保密是极其重要的。
2012-3-19 5
身份认证协议
? 安全的身份认证协议应该满足如下条件,
1,证明者 A能向验证者 B证明他确实是 B；
2,在证明者 A向验证者 B证明他的身份后, 验证者 B不能
获得任何有用的信息, B也不能模仿 A向其他第三方证
明他就是 A。
2012-3-19 6
身份认证协议
分析和评价身份认证协议应考虑如下几个方面,
（ 1） 是单方还是双方的身份认证；
（ 2）计算的有效性；
（ 3）通信的有效性；
（ 4）是否需要第三方的实时参与；
（ 5）对第三方的可信度的要求；
（ 6）安全保证（可证明安全、零知识证明）；
（ 7）用来存储共享秘密数据的地方和方法。
2012-3-19 7
身份认证协议
? 身份认证的类型,
弱认证：使用口令、口令段、口令驱动的密钥；
使用时间戳； 序列号方法等 。
强认证：通过向验证者展示与证明者实体有关的
信息来证明自己的身份。
2012-3-19 8
身份认证协议
? A,B 双方在建立共享密钥时需要考虑保密性
和实时性。
? 保密性：会话密钥应以密文传送，因此双方
应事先共享密钥或者使用公钥。
? 实时性,防止重放
– 询问－应答
– 时戳
– 序列号方法
2012-3-19 9
身份认证协议
传统的身份证明,
一般是通过检验, 物, 的有效性来确
认持该物的的身份 。 徽章, 工作证, 信
用卡, 驾驶执照, 身份证, 护照等, 卡
上含有个人照片 (易于换成指纹, 视网
膜图样, 牙齿的 X适用的射像等 )。
信息系统常用方式,
用户名和口令
2012-3-19 10
身份认证协议
? 交互式证明
两方参与
示证者 P(Prover)，知道某一秘密，使 V相信自
己掌握这一秘密；
验证者 V(Verifier)，验证 P 掌握秘密；每轮
V向 P 发出一询问,P 向 V 做应答。 V 检查 P
是否每一轮都能正确应答 。
2012-3-19 11
并将 y 发送给 B；
身份认证协议
)( xEy k?
? 询问－应答协议（ Challenge-response)
证明者 A 向验证者 B 认证自己,A 和 B共享一个
共同的秘密密钥 k,k 确定了一个加密算法 。
（ 1） B 随机选择一个口令 x（ x 是一个 64比特长的
随机串），并将 x 发送给 A；
（ 2） A 计算
（ 3） B 计算
kE
)( xEy k??
并验证是否有 。yy ??
2012-3-19 12
身份认证协议
Challenge-response
B A 口令 x
yy
??
)( xEy k?
)( xEy k??
口令协议的安全性是建立在 A 和 B 相互信任的
基础上的。属于弱认证协议。
2012-3-19 13
身份认证协议
时戳法
? A 收到消息中包含时戳，且 A 看来这一时戳
充分接近自己的当前时刻,A 才认为收到的
消息是新的并接收。
? 要求各方时间同步。
2012-3-19 14
身份认证协议
序列号方法
? 对交换的每一条消息加上序列号，序列号正
确才被接收。
? 要求每个用户分别记录与其他每一用户交互
的序列号，增加用户负担，因而很少使用。
2012-3-19 15
身份认证协议
各种方法的比较
? 询问－应答不适合于无连接的应用过程
– 在传输前需要经过询问－应答这一额外的握手过
程，与无连接应用过程的本质特性不符。
– 无连接应用最好使用安全时间服务器提供同步
2012-3-19 16
身份认证协议
各种方法的比较
? 时戳法不适用于面向连接的应用过程
– 要求不同的处理器之间时间同步，所用的协议必
须是容错的以处理网络错误
– 协议中任何一方时钟出现错误失去同步，则敌手
攻击的可能性增加
– 网络中存在延迟，不能期待保持精确同步，必须
允许误差范围
2012-3-19 17
身份认证协议
通信双方建立共享密钥时可采用单钥加密体制
和公钥加密体制
? 单钥加密体制
? 公钥加密体制
2012-3-19 18
身份认证协议
? Needham－ Schroeder协议
A B KDC
1,IDA|| IDB ||N1
)]||(||||||[2 1 AsKBsK IDKENIDKE BA、
]||[3 AsK IDKE B、
][4 2NE SK、
)]([5 2NfE SK、
2012-3-19 19
身份认证协议
然而 Needham－ Schroeder 协议易受到重放
攻击,
假定敌手能获得旧会话密钥，则冒充 A向 B重放第 3步
的消息后，就可以欺骗 B使用旧的会话密钥。敌手进
一步截获第 4步 B发出的询问后，可假冒 A作出第 5步
的应答。进而，敌手就可冒充 A使用经认证过的会话
密钥向 B发送假消息 。
2012-3-19 20
身份认证协议
? Needham－ Schroeder 改进协议（ 1）
KDC A B
BA IDID ||1、
)]||||(||||||[2 TIDKETIDKE AsKBsK BA、
]||||[3 TIDKE AsK B、
][4 1NE SK、
)]([5 1NfE SK、
sK
其中 T 为时间戳，用以向 A,B双方保证 的实时性。
2012-3-19 21
身份认证协议
要求各方时钟同步
如果发方时钟超前 B方时钟，可能导致等待重放攻击。
|Clock－ T|<⊿ t
1+⊿ t2
Clock:本地时钟
⊿ t1：本地时钟与 KDC时钟误差估计值
⊿ t2,网络延迟时间
2012-3-19 22
身份认证协议
? Needham－ Schroeder改进协议（ 2）
KDC A B
AA NID ||1、
]||||[||||2 BAAKBB TNIDENID B、
BBsAKBsABK NTKIDETKNIDE BA ||]||||[||]||||||[3,
][||]||||[4 AKBsAK NETKIDE sB、
该协议为 A,B 双方建立共享的会话密钥提供了一个安全有效的手段。
2012-3-19 23
身份认证协议
? 如果 A 保留由协议得到的票据，就可以在有效期内
可不通过 KDC直接认证
A B
'],||||[1 ABSAK NTKIDE
B、
][,2 '' AKB NEN S、
][3 'BK NE S、
B在第一步收到票据后，可以通过
BT
检验票据是否过时，而
新产生的一次随机数 则向双方保证了没有重放攻击 。
BA NN ??,
2012-3-19 24
身份认证协议
? Shnorr 身份认证协议
Shnorr 身份认证协议融合了 ELGamal协议、
Fiat-Shamir协议、和 Chaum-Evertse-Van de
Graff交互协议等协议的思想，是一种计算量
、通信量均少，特别适合智能卡上用户身份
识别的方案。
其安全性建立在计算离散对数问题的困难性
上的。
2012-3-19 25
身份认证协议
? Shnorr 身份认证协议需要一个可信中心 TA。
TA为协议选择下列参数,
（ 1） p 及 q 是两个大素数，且 q|(p-1);
的生成元。）
为，阶元（如可取为 pqpp ggqZ Z)2( /)1(* ??? ??
（ 3） h 是一个输出为 t为的单向函数,t为一个
安全参数 ;
（ 4）公开密钥 v和秘密密钥 s,可用作签名。
p,q,h 及其公开钥都公开，每个用户自己选定个人秘
密密钥 s,其计算公开密钥 v。 其中 。pvqs s m o d],1,1[ ???? ?
2012-3-19 26
身份认证协议
? 每位用户必须到 TA 注册其公开密钥。 TA
验明用户身份后，对每位用户指定一识别名 I
。 I中包括用户的姓名、性别、生日、职业、
电话号码、指纹信息等识别信息。 TA 再对
h(I,v)签名，以便将来验证只用。
? 在身份认证过程中，不需要 TA 介入。
2012-3-19 27
身份认证协议
? 证明者 A向验证者 B证明他身份（ Schnorr 认证
协议）
AvI,1、
A B
用 TA 的数字签名来
验证 A 的公开密钥 pZr *?任选
pX r m o d2 ??、
]2,1[ te ?任选整数3,e
qsery m o d4 ??、
。pvX ey m o d??
、验证 5
2012-3-19 28
身份认证协议
? Schnorr 协议的安全的基础是离散对数计算困
难性。从 v 求 s 就是求离散对数，在计算上
是不可行的。 r 和 s 都是用户的秘密，假冒者
Eve 是无法从 y 中得到用户的秘密，当然也
就无法假冒证明者 A。
2012-3-19 29
身份认证协议
? Okamoto 身份认证协议
Okamoto 身份认证协议是 Schnorr协议的一种
改进，是一个可证明安全的协议。 Okamoto
协议同样需要一个可信的 TA。
TA 选择两个大素数 p,q,q|(p-1)。
的元素，中两个阶为是 qZ p*21,??
。保密 21l o g ???cTA
TA 选择一个签名方案和一个 Hash函数
2012-3-19 30
身份认证协议
? TA 向 A 颁布一个证书，协议如下,
（ 1） TA 建立 A 的身份并颁布一个识别串 ID(A)。
（ 2） A 秘密地选择两个随机数,,
21 mm
,1,0 21 ??? qmm 并计算,m o d21 21 pv mm ??? ??
将 v 发给 TA。
（ 3） TA 对（ ID,v） 签名,。),( vIDs i gs
TA?
TA 将证书 C(A)=( ID(A),v,s ) 发送给 A。
2012-3-19 31
身份认证协议
? Okamoto 身份认证协议如下,
A B
随机选取,,
21 rr
1,0 21 ??? qrr
pX rr m o d21 21 ??? XsvAIDAC ),,),(()( ?
T u r esvIDV e r TA?),,( ?
,e随机选取 te 20 ??e
21,yy
pvX eyy m o d21 21? ???
验证
qemry m o d)( 111 ??
qemry m o d)( 222 ??
计算
2012-3-19 32
身份认证协议
? Guillou-Quisquater 身份认证协议
Guillou-Quisquater 身份认证协议的安全性
是基于 RSA 体制安全的。
TA 选择一个大素数 b（ 用作一个安全参数）
和一个公开的 RSA 加密指数。同时 TA 选择
一个签名方案和 Hash 函数。
TA 选择两个大素数 p 和 q,形成 n＝ pq。
保密 p 和 q,公开 n。
2012-3-19 33
身份认证协议
? TA 向证明者 A颁发一个证书,
（ 1） TA 建立 A 的身份并颁布一个识别串 ID(A)。
（ 2） A 秘密地选择一个随机整数 m,
,10 ??? nm 并计算,m o d)( 1 nmv b??
并将 v 发送给 TA。
（ 3） TA 对（ ID,v） 签名,。),( vIDs i gs
TA?
TA 将证书 C(A)=( ID(A),v,s ) 发送给 A。
2012-3-19 34
身份认证协议
? Guillou-Quisquater 身份认证协议
A B
随机选取 r
10 ??? nr
nrX b m o d? XsvAIDAC ),,),(()( ? T u r esvIDV e r
TA
),,( ?
,e随机选取 10 ??? bee
y
nyvX be m o d??
验证
nrmy e m o d?
计算
2012-3-19 35
身份认证协议
? 基于身份的身份认证协议
Shamir的基于身份的基于身份的密码方案的思想
Shamir在 1984年提出了一类新型的密码方案，这类方
案能使网上的任何一对用户无需交换秘密密钥或公开
密钥、无需保存密钥薄、无需使用第三方服务可进行
安全的通信和相互签名。
他不直接生成一对随机的公开密钥和秘密密钥，而是由
用户选择他的名字和网址来作为公开密钥。
2012-3-19 36
身份认证协议
? 几种密码体制的差别
加密 解密 消息 m
k
随机种子 k
（ a） 私钥密码体制
k
信使
消息 m 信道
加密 解密 消息 m
随机种子 k
（ b） 公钥密码体制
公钥号码薄
消息 m
ek dk
信道
2012-3-19 37
身份认证协议
加密 解密 消息 m
密钥的产生
（ c） 基于身份的密码体制
消息 m 信道
ek接收者的身份 dk
随机种子 k
2012-3-19 38
身份认证协议
? Guillou-Quisquater 的基于身份的认证协议
TA 为 A 颁发一个值 u 的过程如下,
（ 1)TA 建立 A 的身份并颁布一个识别串 ID(A)；
（ 2） TA 计算,m o d))((( 1 nAIDHu a?? 并将 u 发给 A。
其中 H 是一个公开的 Hash 函数。参数选择和
Guillou-Quisquater协议中一样，且
)(m o d1 nab ??
2012-3-19 39
身份认证协议
? Guillou-Quisquater 的基于身份的认
证协议
A B
r
10 ??? nr
nrX b m o d? XAID ),(
,e随机选取 10 ??? bee
y
nyvX be m o d??
nruy e m o d?
计算
))(( AIDHv ?
计算
2012-3-19 40
密钥交换协议
哈哈 ！ …
我也知道你
们的秘密了
攻击者
窃听者
明文
m 公开信道
明文 m
Alice Bob
明文
m
明文在公开信道中传输
2012-3-19 41
密钥交换协议
信息传输模型
加 密 明文 m 公开信道
明文
m
加密
密钥
Alice
解 密 密文 c
解密
密钥
Bob
攻击者
我晕 ！ … 他
们的秘密是什
么呢？？？
2012-3-19 42
密钥交换协议
传统的密钥分配方式
信使
会话密钥 K 会话密钥 K
Alice Bob
2012-3-19 43
密钥交换协议
? 密钥交换协议 (key exchange protocol)是指两人
或多人之间通过一个协议取得会话密钥并用于
进一步的加密算法或会话中的方法 。 在实际的
密码世界中密钥交换其实是很重要的一个环节
。
? 密钥交换协议往往会和身份认证协议结合, 这
样才能得到更安全的密钥交换协议 。
2012-3-19 44
密钥交换协议
? 对称密码学的密钥交换
协议中 Alice和 Bob各与密钥分配中心 KDC共享
一个秘密密钥
KDC
Alice Bob
。BA kk,
1、请求
2、产生一个
随机会话密钥
ABk
)(),(2 ABkABk kEkE BA、
ABABkkA kkED A ?)]([3,
)(4 ABk kE B、
ABABkkB kkED B ?)]([5,
(1)该协议要求
KDC绝对可信；
(2)KDC可能会成
为瓶颈。
2012-3-19 45
密钥交换协议
? 公钥秘密学的密钥交换
Alice和 Bob使用公开密钥密码协商会话密钥，并用协
商的会话密钥加密数据。
Alice的私钥和公钥分别为
AA pksk,
Bob的私钥和公钥分别为
BB pksk,
产生会话
密钥 k
KDC
Alice Bob
Bpk
)( kE Bpk
kkED BB pksk ?)]([
在实用中，公钥
可以从数据库中
获得，使得密钥
交换协议更容易
。但 Bob不知道和
他通信的人就一
定是 Alice。
2012-3-19 46
密钥交换协议
? 具有保密性和认证性的密钥交换
Alice Bob
]||[ 1 Ap k B IDNE①
]||[ 21 NNE p k A②
][ 2NE pkB③
④ )]([ ss k Ap k B kEE
由于协议中使用了随机数 N1和 N2和采用了公
钥加密，通信双方能确信对方的身份 。
2012-3-19 47
密钥交换协议
? Diffie－ Hellman密钥交换协议
算法的安全性基于求离散对数的困难性
Alice Bob
xA xB pgX
Ax m o d?
pgY Bx m o d?pg
pYk
BA
A
xx
x
m o d
m o d
?
?
pg
pXk
BA
B
xx
x
m o d
m o d
?
?
系统参数,p是一个大素数,g是 Z*p的一个生成元。
该协议
容易受
到中间
人攻击
Diffie－ Hellman 两方密钥交换协议
2012-3-19 48
密钥交换协议
? 如果 被动攻击者 能窃听 Alice和 Bob的通信,
并截获,
BA xx gYgX ??,
性，他无法得到 xA,xB。
由离散对数的困难
，BA xx gg,窃听者由 无法计算出会话密钥
pgk BA xx m o d?
2012-3-19 49
密钥交换协议
? 例,取 p＝ 23,g＝ 5
Alice 选择 xA＝ 7,Bob 选择 xB＝ 15。
1723m o d5 7 ??? AxgX
Bob 计算
1923m o d5 15 ??? BxgY
交换 X,Y 后
Alice 计算
Bob 计算
1523m o d19 7 ??? AxYk
1523m o d17 15 ??? BxXk
Alice 计算
2012-3-19 50
密钥交换协议
? 对 Diffie－ Hellman密钥交换协议的 中间人攻
击
Alice Bob
xA xB
pgX Ax m o d?
pgY Bx m o d?
Diffie－ Hellman 两方密钥交换协议的中间人攻击
Adversary
pgZ A d vx m o d?
pgZ A d vx m o d?
pg
pZk
BA d v
B
xx
x
m o d
m o d2
?
?
pg
pZk
AA d v
A
xx
x
m o d
m o d1
?
?
2012-3-19 51
密钥交换协议
? Diffie－ Hellman 三方密钥交换协议
A
C
B Ax Bx
Cx
pgX Ax m o d?①
pgY Bx m o d?②
pgZ Zx m o d?③
pZZ Ax m o d??④
pXX Bx m o d??⑤ pYY
Cx m o d??⑥
⑦ pYk A
x m o d??
⑧ pZk
Bx m o d??
⑨
pXk Cx m o d??
pgk CBA xxx m o d?
会话密钥 系统参数,p是一个大素数,g是 Z*p的一
个生成元。
2012-3-19 52
密钥交换协议
? 密钥交换四方协议,
A
D
C
B
1rg①
2211,,rrrr ggg
②
213213231,,,rrrrrrrrr gggg
③
432 rrrg
④
431 rrrg⑤
421 rrrg⑥
会话密钥为
pgk rrrr m o d4321?
系统参数,p是一个大素数,g是 Z*p的
一个生成元。以上运算均为模运算。
缺陷：第四
方权限过大
2012-3-19 53
密钥交换协议
Shamir 协议
在 Shamir 协议下, 任意秘密通信的双方都不必建立
公钥或私钥, 只需要通过该协议便可获得保密通信
的会话密钥 。
Shamir 协议可形象看作是 A先将保密的会话密钥 k装
入保险箱, 锁上只有他自己才能打开的锁, 然后寄
给 B。 B 收到后, 他不能打开这个箱子, 只能加上只
有 B才能打开的另一把锁, 再退还给 A。 此时箱子上
有两把锁, A 开启他锁上的锁, 再寄给 B,B 再打开
他自己加上的锁, 然后取出保密的会话密钥 。
2012-3-19 54
密钥交换协议
Shamir 协议中加密密钥 EA,解密密钥 DA 均由 A
自己秘密保管, EB,DB 也是一样 。 协议具体如下,
A B
随机产生一
个会话密钥 k
)(kE A
)]([ kEE AB
)(
)]]([[
kE
kEED
B
ABA
? )(kE B
kkED BB ?)]([
Shamir协议要求加密算法是可交换的，即 )]([)]([ kEEkEE
ijji ?
一次一密密码系统是可交换的,RSA 密码体制也是可交换的。
2012-3-19 55
密钥交换协议
? 如果加密、解密算法是按位 ⊕ 运算，则可以恢
复出会话密钥的。从这种攻击来说,Shamir
协议是不安全的。
? 如果 Shamir 协议采用 RSA密码体制进行加密、
解密，则是安全的 。
? Shamir 协议没有身份认证，只存在保密。在
保密通信前缺少对发信方的身份验证，这也容
易受到中间人攻击。
2012-3-19 56
密钥交换协议
? 以上协议基本上没有身份认证。 Alice和 Bob
通过密钥交换协议得到了会话密钥，但他们
无法确认和自己通信的人就是 Alice或 Bob，
这也是以上协议的一个安全隐患。把密钥交
换协议和身份认证协议结合，就可以得到更
安全的密钥交换协议－ 可认证的密钥交换协
议。
2012-3-19 57
密钥交换协议
? Yahalom协议
这个协议中 Alice和 Bob两人各与 KDC共享一个秘密密钥
EA,EB。
Alice KDC BOb
(A,RA)
EB(A,RA,RB)
EA(B,k,RA,RB),EB(A,k)
解密得 k和 RA并
确认 RA的有效性
EB(A,k),Ek(RB)
解密得 k,再解密得 RB,
确认 RA的有效性
A,B分
别为
Alice,
Bob的名
字。 RA,
RB为随
机数
通过该协议,Alice,Bob互相确信是
正在同对方谈话，而不是跟第三方。
2012-3-19 58
密钥交换协议
? Kerberos协议
这个协议中 Alice和 Bob两人各与 KDC共享一个秘密密钥
EA,EB。 Alice想产生一会话密钥用于与 Bob通信。
协议如下,
KDC Alice Bob
A,B
EA(T,L,K,B),EB(T,L,K,A)
EK(A,T),EB(T,L,K,A)
EK(T+1)
A,B分
别为
Alice,
Bob的名
字。 RA,
RB为随
机数
2012-3-19 59
密钥交换协议
? Kerberos协议是可行的，但它假设每个人的
时钟都与 KDC的时钟同步。实际上，这个结果
是通过把时钟同步到一个安全的定时服务器
的几分钟之内，并在这个时间间隔内检测重
放而获得的。
2012-3-19 60
密钥交换协议
? 分布式鉴别安全协议－ DASS 协议
Alice和 Bob每人有一个私人密钥,KDC有他们公开密
钥签名的副本。
（ 1） Alice送一个消息给 KDC,这个消息由 Bob的名字
组成,B。
（ 2） KDC把 Bob的公开密钥 KB发给 Alice,并用自己的
私人密钥 T 签名。签名消息包括 Bob的名字,ST(B,KB)
（ 3） Alice验证 KDC 签名以确认她接收的密钥确实是
Bob的公开密钥。她产生一随机会话密钥 K和一公开密
钥 /私人密钥对 KP,她用 K加密时间标记 TA,然后用她
的私人密钥 KA对会话密钥的寿命周期 L,她的名字和
KP签名。
2012-3-19 61
密钥交换协议
。))((),,,(),( KESKALSTE BPA KKPKAK
Alice给 Bob发送消息,
（ 4） Bob发送一个消息给 KDC,它由 Alice的名字组成,A
（ 5） KDC把 Alice的公开密钥 KA 发给 Bob,并用自己的私
人密钥 T签名,ST(A,KA)。
（ 6） Bob验证 KDC的签名以确认他接收的密钥确实是
Alice的公开密钥。然后他验证 Alice的签名并恢复出 KP。 他
验证签名并用他的私人密钥恢复 K。 然后解密 TA以确信这
是当前的消息。
（ 7）如果需要相互鉴别,Bob用 K加密一个新的时间标记
，并把它发送给 Alice,EK(TB),
（ 8） Alice用 K解密 TB 以确认消息是当前的 。
2012-3-19 62
二、高级协议
2012-3-19 63
比特承诺协议
? 问题,
股票经纪人 Alice想说服投资商 Bob她的选取赢利股票的方法
很不错 。
Bob说：, 给我选 5支股票, 如果都赢利, 我将把生意给你 。
”
Alice说：, 如果我为你选了 5支股票, 你可以自己对他们投
资, 而不用给我付款 。 我为什么不向你出示我上个月选的
股票呢？,
Bob说：, 我怎样知道你在了解上月股票的收益后没有改变
你上月选择的股票呢？ 如果你现在告诉我你选的股票, 我
就可以知道你不能改变他们 。 在我买你的方法以前我不在
这些股票中投资 。 相信我 。,
2012-3-19 64
比特承诺协议
Alice说：, 我宁愿告诉你我上月选择的股票 。 我不会
变, 相信我 。,
Alice想对 Bob承诺一个预测（即 1位或位序列），但直
到某个时间以后才揭示她的预测。而另一方面,Bob
想确信 Alice承诺了她的预测后，她没有改变她的想
法。
2012-3-19 65
比特承诺协议
? 一般地，一个比特承诺方案就是一个函数
YXf ??}1,0{:
这里 X 和 Y 是两个有限集。 }1,0{?b 的一个
加密是 Xxxbf ?)},({ 中的一个值。
比特承诺协议满足以下两个特性,
（ 1）隐蔽性（ Concealing）。 对 }1,0{?b
不能从 f(b,x) 确定 b 的值。
接收者
（ 2）约束性（ Binding）。 发送者能打开 f(b,x)
,即发送者能通过揭露用于加密的 b 的 x 的值使
接收者相信 b 的确是被加密的值。
2012-3-19 66
比特承诺协议
? 使用对称密码学的比特 （ 位 ） 承诺协议
（ 1） Bob产生一个随机比特串 R,并把它发送给 Alice,R。
（ 2） Alice产生一个由她想承诺的位 b组成的消息 （ b实际上
可能是几位 ）, 已经 Bob的随机串 。 她用某个随机密钥 K
对它加密, 并将结果送回给 Bob,EK(R,b)。
这是一个协议的承诺部分, Bob不能解密消息, 因而不知
道位为何 。 当到了 Alice揭示她的位的时候, 协议继续,
（ 3） Alice发送密钥给 Bob；
2012-3-19 67
比特承诺协议
（ 4） Bob解密消息以揭示位。他检测他的随机串以证
实位的有效性。
如果消息不包括 Bob的随机串,Alice能够秘密地用一
系列密钥解密她交给 Bob的消息，直到找到她的位，
而不是她的承诺位。由于位只有两种可能的值，她
只需试几次肯定可以找到一个。 Bob的随机串避免了
这种攻击，她必须能找到一个新的消息，这个消息
不仅使她的位反转，而且使 Bob的随机串准确地重新
产生。如果加密算法好，她发现这种消息的机会是
极小的。 Alice不能在她承诺后改变她的 位。
2012-3-19 68
比特承诺协议
? 使用单向函数的比特（位）承诺协议
该协议利用单向函数来实现位承诺。协议如下,
（ 1） Alice产生两个随机位串,R1,R2。
（ 2） Alice产生消息，该消息由她的随机串和她的希望
承诺的位（实际上可能是几位）组成,(R1,R2,b)。
（ 3） Alice计算消息的单向函数值，将结果以及其中一
个随机串发送给 Bob,H(R1,R2,b),R1。
这个来自 Alice的传送就是承诺证据。 Alice在第（ 3）
步使用单向函数阻止 Bob对函数求逆并确定这个位 。
2012-3-19 69
比特承诺协议
（ 4） Alice将原消息发给 Bob,（ R1,R2,b）。
（ 5） Bob计算消息的单向函数值，并将该值及 R1与原
先受到的值及随机串比较。如匹配，则位有效。
这个协议的优点在于 Bob不必发送任何消息。只要
Alice发送给 Bob一个对位承诺的消息，已经另一揭示
该位的消息。
这里步需要 Bob的随机串，因为 Alice承诺的结果是对消
息进行单向函数变换得到的。 Alice不可能欺骗，并
找到另一个消息 （ R1’,R2’,b’）,以满足 H(R1,R2,b)＝
H(R1’,R2’,b’)。
2012-3-19 70
比特承诺协议
? 使用伪随机序列发生器的比特（位）承诺
（ 1） Bob产生随机位串，并发送给 Alice,RB。
（ 2） Alice位伪随机位发生器产生一个随机种子。然后，对
Bob随机位串中的每一位（比特），她回送 Bob下面两个
中的一个,
（ a） 如果 Bob的位为 0，则为发生器的输出。
（ b)如果 Bob的位位 1，则为发生器输出与她的位的异或
。
2012-3-19 71
比特承诺协议
（ 3） Alice将随机种子送给 Bob。
（ 4） Bob确认 Alice的行动是合理的。
如果 Bob的随机位串足够长，伪随机位发生器不可预
测，这时 Alice就无有效的 方法进行欺诈。
2012-3-19 72
比特承诺协议
? 抛币协议
某些密码协议中要求通信双方在无第三方协
助情况下，产生一个随机序列，因为 A,B之
间不存在信任关系，因此不能由一方产生在
通过网络或电话告诉另一方
2012-3-19 73
比特承诺协议
? 使用单向函数的抛币协议
Alice,Bob都知道某一单向函数 f(x)，但都不知道
逆函数
(1)Alice选择一个随机数 x，求 y＝ f (x) 并发给 Bob
(2)Bob猜测 x 的奇偶性，并将结果告诉 Alice
(3)Alice告诉 Bob猜测正确不正确，并将 x 发给 Bob
(4)Bob确信 y＝ f (x)
? 安全性
– Bob不知道 f (x)的逆函数，无法由 y 求 x，只能猜
– Alice若在 Bob猜测后改变 x,Bob可以通过 y=f (x)?
检查 出来
2012-3-19 74
零知识证明协议
背景,
Alice,我知道联邦储备系统计算机的口令，汉堡包秘密调味
汁的成分以及 Knuth第 4卷的内容。
Bob,不，你不知道。
Alice,我知道。
Bob,你不知道。
Alice,我确实知道！
Bob,请你证实这一点！
Alice,好吧，我告诉你！（她悄悄地说出了口令）
Bob,太有趣了！现在我页知道了。我要告诉《华盛顿邮报,
Alice,啊呀！
2012-3-19 75
零知识证明协议
? 不幸的是,Alice用常用的方法给 Bob证明她知道的
秘密。这样一来,Bob也知道了这些秘密了，现在
Bob要告诉其他人,Alice对此毫无办法。
? 问题,有没有一种有效的办法，让 Alice给 Bob证
明她知道这些秘密，使得 Bob可以确信 Alice的确知
道这些，但 Bob根本不能获得这些秘密的任何消息呢
？
2012-3-19 76
零知识证明协议
? 零知识证明的思想,
零知识证明采用交互式协议的形式。
Alice要向 Bob证明她知道某些秘密，可如下进行,
Bob问 Alice一系列问题，如果 Alice知道那个秘密，她
就能正确回答所有问题。如果她不知道，她仍有 50
％的机会回答每一个问题，但要猜对每个问题的机
会实在太小了（几乎不可能）。大约 10个问题之后
，将使 Bob确信 Alice是否知道那个秘密。然而所有回
答都没有给 Bob提供 Alice所知道的 秘密的任何信息。
2012-3-19 77
零知识证明协议
? 零知识基本协议 Quisquater－ Guillou 协议
设 Alice知道咒语,
可打开 C和 D之间的
秘密门，不知道者
都将走向死胡同 中 。
A
B
C D
2012-3-19 78
零知识证明协议
? 零知识证明的基本协议
(1) Bob站在 A 点；
(2) Alice进入洞中任一点 C 或 D；
(3) 当 Alice进洞之后, Bob走到 B 点；
(4) Bob叫 Alice,(a)从左边出来, 或 (b)从右边出来；
(5) Alice按要求实现 (以咒语, 即解数学难题帮助 )；
(6) Alice和 Bob重复执行 (1)～ (5)共 n 次 。
2012-3-19 79
零知识证明协议
? 若 Alice 不知咒语，则在 B 点，只有 50 %的机会猜中
Bob的要求，协议执行 n 次，则只有 2-n 的机会完全猜中
，若 n=16，则若每次均通过 Bob 的检验,B受骗机会仅
为 1/65536。
? 如果 Bob用摄像机记录下他所看到的一切，他把录像给
Carol看,Carol会相信这是真的吗？ Carol是不会相信
这是真的。
? 这说明了两件事情：其一,Bob不可能使第三方相信这
个证明；其二，它证明了这个协议是零知识的。 Bob在
不知道咒语的情况下，显然不能从录像中获悉任何信息
。
2012-3-19 80
零知识证明协议
? 基本零知识协议由下面几轮组成,模型
如下,
（ 1） Alice用她的信息和一个随机数将这个难题转变为
另一个难题，新的难题和原来的难题同构。然后她
用她的信息和这个随机数解这个新的难题。
（ 2） Alice利用位承诺方案提交这个新的难题的解法。
（ 3） Alice向 Bob透露这个新的难题。 Bob不能利用这
个新的难题得到关于原难题 或其解法的任何信息。
2012-3-19 81
零知识证明协议
（ 4） Bob要求 Alice,
（ a） 向他证明新、旧难题是同构的（即两个相关问
题的两种不同解法）或者
（ b） 公开她在第（ 2）步中提交的解法并证明新难题
的解法。
（ 5） Alice同意。
（ 6） Alice和 Bob重复第（ 1）至（ 5）步 n 次
2012-3-19 82
零知识证明协议
哈米尔顿回路
图论中有一个著名问题，对有 n个顶点的全连通
图 G，若有一条通路可通过且仅通过各顶点一次，
则称其为哈米尔顿回路。 Blum[1986] 最早将其
用于零知识证明。当 n大时，要想找到一条
Hamilton回路，用计算机做也要好多年，它是一
种单向函数问题。若 A知道一条回路，如何使
Bob相信他知道，且不告诉他具体回路？
2012-3-19 83
零知识证明协议
回路与 H 上的 Hamilton 回路一一对应。已知 G 上的
Hamilton 回路易于找出 H 上的相应回路；
(2) Alice将 H的复本给 Bob；
(3) Bob 向 Alice提出下述问题之一,(a) 出示证明 G 和
H 同构,(b) 出示 H 上的 Hamilton 回路；
(4) Alice执行下述任务之一,(a) 证明 G 和 H 同构，但
不出示 H上的 Hamilton 回路,(b) 出示 H 上的 Hamilton
回路但不证明 G和 H 同构；
(5) Alice和 Bob重复执行 (1)～ (4)共 n 次。
HG ?
(1) Alice将 G 进行随机臵换，对其顶点进行移动，并改变其
标号得到一个新的有限图 H。因, 故 G上的 Hamilton
2012-3-19 84
零知识证明协议
? Fiat-Shamir身份识别方案
(1) Alice 取随机数 r(<m),计算 x= r2 mod m,送给 Bob；
(2) Bob 将一随机 bit b 送给 Alice；
(3) 若 b=0,则 Alice 将 r 送给 Bob； 若 b=1,则 Alice将 y=rs送
给 Bob；
(4) 若 b=0,则 Bob 证实 x=r2modm,从而证明 Alice 知道,
若 b=1,则 Bob 证实 xv=y2modm,从而证明 Alice 知道 。
这是一次证明, Alice 和 Bob 可将此协议重复 t 次, 直到
Bob 相信 Alice 知道 s 为止 。
2012-3-19 85
零知识证明协议
? 完备性
– 如果 Alice和 Bob遵守协议，且 Alice知道 s，则应答 rs
是应是模 m下 xv的平方根,Bob接收 Alice的证明，所
以协议是完备的。
? 正确性
– Alice不知道 s，他也可取 r，送 x=r2 mod m给 Bob，
Bob送 b 给 Alice。 Alice可将 r送出，当 b=0时则 Bob可
通过检验而受骗，当 b=1时，则 Bob可发现 Alice不知 s
,B受骗概率为 1/2，但连续 t 次受骗的概率将仅为 2-t
– Bob无法知道 Alice的秘密，因为 Bob没有机会产生
(0,1)以外的信息,Bob送给 Alice的消息中仅为 Alice知
道 v的平方根这一事实。
2012-3-19 86
零知识证明协议
最小泄露证明和零知识证明,
以一种有效的数学方法, 使 V可以检验每
一步成立, 最终确信 P知道其秘密, 而又能
保证不泄露 P所知道的信息 。
2012-3-19 87
不经意传输和安全多方计算
? 不经意传输 （ Oblivious Transfer）
设 A有一个秘密, 想以 1/2的概率传递给 B,即 B有 50%的
机会收到这个秘密, 另外 50%的机会什么也得不到, 协
议执行完后, B知道自己是否收到了这个秘密, 但 A却步
知道 B是否收到了这个秘密 。 这种协议称为不经意传输
协议 。
例如,A是机密的出售者, A列举了很多问题, 意欲出
售各个问题的答案, B想买其中一个问题的答案, 但又
不想让 A知道自己买的是哪个问题的答案 。
2012-3-19 88
不经意传输和安全多方计算
? 基于大数分解的不经意传输协议
A 想通过不经意传输协议传给 B 大数 n 的因子分子
如果已知某数在模 n下的两个不同的平方根，就可以分解 n。
1,B 随机选一数 x，将 x2modn 发给 A。
2,A（掌握 n＝ pq 的分解）计算 x2mod n 的 4个平方根
± x,± y,将其中之一发给 B。 A只知道 x2modn, 并不知
道 4个平方根中的哪一个被 B 选中。
3,B 检查收到的数是否与 ± x 在模 n 下同余，如果是，
B没有得到任何新的信息，否则 B 掌握了 x2mod n 的两个
不同的平方根，从而可以分解 n，而 A 确不知道究竟是
哪种情况。
2012-3-19 89
不经意传输和安全多方计算
此协议是非交互的, 其中 B不向 A发送任何消息 。
设系统中所有用户都知道一个大素数 p,Z*p的生成元 g
和另一个素数 c,但无人知道 c的离散对数 。 假定计算
离散对数是不可行的, 因此 gxmodp和 gymodp无法计算
gxymodp。
B的加密, 解密密钥：随机选取一个比特 i 和一个数 x
? 基于离散对数问题的不经意传输协议
)20( ??? px
，计算 yi=gx,y1-i=cg-x,以 (y0,yi)作为加密公钥,
以 (i,x)作为解密密钥。
2012-3-19 90
不经意传输和安全多方计算
由于 B不知道 c的离散对数，所以他知道 y0 或 y1的离散对
数，而 A无法知道 y0或 yi中的哪个离散对数是 B已知的。
A可通过方城 y0 y1=c 来检查 B的公钥是否正确。
设 A的两个秘密 s0和 s1是二进制数,⊕ 是异或运算，若进
行异或运算的两个数不等长，可在较短数前面补 0。
（ 1） A在 0到 p－ 2之间随机取两个整数 k0,k1,对 j=0,1计算
,,,jjjkjjkj dsmydgc jj ???? 将 1010,,,mmcc 发送给 B。
（ 2） B用自己的解密密钥计算 。iiiikixkxi dmsdygc ii ?????,
由于 B不知道 y1-i 的离散对数，所以无法得到 d1-i和 s1-i。
2012-3-19 91
不经意传输和安全多方计算
?, 多传一, 的不经意传输协议
设 A有多个秘密，想将其中一个传递给 B,使得只有 B知
道 A传递的是哪个秘密。设 A的秘密是 s1,s2,…,sk,每一
秘密是一比特串。协议如下,
（ 1） A告诉 B一个单向函数 f,但对 f--1保密。
（ 2）设 B想得到秘密 si,他在 f 的定义域内随机选取 k 个
值 x1,x2,…,xk,将 k 元组 (y1,y2,…,yk)发给 A,其中
?
?
?
?
?
?
ijxf
ijx
y
i
j
j )(
2012-3-19 92
不经意传输和安全多方计算
（ 3） A计算 ),,2,1()(1 kjyfz
jj ??? ?
,并将 ),,2,1( kjsz
jj ???
发送给 B。
（ 4）由于,))(()(
11 iiij xxffyfz ??? ??
所以 B知道 zi,因此可从
ii sz ?
获得 si。
由于 B没有 )( ijz
j ?
的信息，因此无法得到 )( ijs j ?, 而 A
不知道 k元组 (y1,y2,…,yk)中哪个是 f(xi),因此无法确定 B
得到的是哪个秘密。
2012-3-19 93
不经意传输和安全多方计算
? 不经意签名
不经意签名有两种类型,
（ 1） Alice有 n份不同的消息。 Bob可以选择其
中之一给 Alice签名,Alice没有办法知道她
签的哪一份消息。
（ 2） Alice有一份消息,Bob可以选择 n个密钥
中的一个给 Alice签署消息用,Alice无法知
道她用的哪一个密钥。
2012-3-19 94
不经意传输和安全多方计算
? 同时签约：面对面
Alice和 Bob想订立一个合约。他们同意了其中的措词，
但每个人都想等对方签名后再签名。为了保证公平他们
可以采用下面协议进行同时签约。
（ 1） Alice签上她的名字的第一个字母，并把合约递给 Bob。
（ 2） Bob签上他的名字的第一个字母，并把合约递给 Alice。
（ 3） Alice签上她的名字的第二个字母，并把合约递给 Bob。
（ 4） Bob签名签上他的名字的第二个字母，并把合约递给 Alice。
（ 5） 这样继续下去，直到 Alice和 Bob都签上他们的名。
2012-3-19 95
不经意传输和安全多方计算
这个协议有个明显的问题，如果有一个人的名字较
长，则协议就可能变得对名字较短的人不公平。如
果名字较长的人在另一个人签完名后，拒绝签名，
在这份合约对他就没有什么约束力。
解决办法：可以采用 Hash函数，把签名人的姓名变成等
长的哈希函数值（二进制串），然后再进行上面协
议。
2012-3-19 96
不经意传输和安全多方计算
? 同时签约：非面对面
这个协议,Alice和 Bob交换一系列签名消息：我同意我以概
率 p 接受这个合约约束。
（ 1） Alice和 Bob就签约应当完成的日期达成一致意见。
（ 2） Alice和 Bob确定一个双方都愿意用的概率差。设 Alice
的概率差为 a,Bob的概率差为 b。
（ 3） Alice发给 Bob一份 p＝ a 的已签署的消息。
（ 4） Bob发给 Alice一份 p＝ a＋ b 已签署的消息。
（ 5）令 p为 Alice在前一步中从 Bob那里收到的消息的概率。
Alice发给 Bob一份 p’＝ p＋ a 或 1中较小的已签署的消息。
2012-3-19 97
不经意传输和安全多方计算
（ 6）令 p为 Bob在前一步中从 Alice那里收到的消息概率。
Bob发给 Alice一份 p’＝ p＋ b 或 1中较小的已签署的消息
。
（ 7） Alice和 Bob继续交通执行第（ 5）和第（ 6）步，直
到双方都收到 p＝ 1的消息，或者已到了在第（ 1）中达
成一致的日期。
2012-3-19 98
不经意传输和安全多方计算
? 同时签约：使用密码术
(1) Alice和 Bob二者随机选择 2n个 DES密钥，分成一对对的
。
(2） Alice和 Bob都产生 n对消息。如 Li,Ri：,这是我的第 i
个签名的左半部分”,,这是我的第 i 个签名的右半部分
” 。
(3) Alice和 Bob都二者用每个 DES密钥对加密他们的消息，
左半消息用密钥对中的左密钥，右半消息用密钥对中的
右密钥。
（ 4） Alice和 Bob相互发送给对方 2n份加密消息，弄清哪份
消息是哪对消息的哪一半 。
2012-3-19 99
不经意传输和安全多方计算
(5)Alice和 Bob利用每一对的不经意传输协议相互送给对
方，即 Alice送给 Bob或用于独立加密 n对消息中的每
一对左半消息的密钥；或用于加密右半消息的密钥
。 Bob也这样做。
(6)Alice和 Bob用收到的密钥解密他们能解密的那一半消
息。他们确信解密消息是有效的。
(7)Alice和 Bob都把 2n个 DES密钥的第一个发送给对方。
(8)Alice和 Bob对所有的 2n个 DES密钥的第二个位、第三
个位，重复第（ 7）步，如此继续下去，直到所有
DES密钥的所有位都被传送出去。
2012-3-19 100
不经意传输和安全多方计算
(9)Alice和 Bob解密剩余一半消息对，合约被签署。
(10)Alice和 Bob交换在第（ 5）步的步经意传输中使用的
私人密钥，并验证对方没有欺骗。
2012-3-19 101
不经意传输和安全多方计算
? 安全多方计算
安全多方计算在缺少信任的情况下，参与各
方秘密输入一个函数值，用一种特殊的方法
计算含有多个变量的函数。其中每个人都知
道函数的值，但除了函数的输出外，没有人
知道关于任何其他成员输入的任何信息。
安全多方计算在分布式密码系统中有非常重
要的应用。
2012-3-19 102
不经意传输和安全多方计算
? A.C.Yao.于 1982 年在,Protocols for secure comput
－ ations,首先提出安全多方计算问题－姚百万富翁
问题。
姚百万富翁问题的一般模型,
Alice知道一个整数 i,Bob知道一个整数 j,Alice和 Bob
ji ?
想知道是 i > j,还是, 但 Alice和 Bob都不希望泄露
他们各自知道的整数。
2012-3-19 103
不经意传输和安全多方计算
假定 i和 j 的取值范围是从 1到 100,Bob有一
个公开密钥和一个私人密钥。
（ 1） Alice选择一个大随机数 x,并用 Bob的公开密钥加
密,c=EB(x)。
（ 2） Alice计算 c-i,并将结果发送给 Bob。
（ 3） Bob计算下面的 100个数,
yu=DB(c-i+u),。1001 ?? u
DB是使用 Bob的私人密钥的解密算法
。
2012-3-19 104
不经意传输和安全多方计算
Bob选择一个大的随机数 p（ p 的大小应比 x 稍小一点
,Bob不知道 x,但 Alice能容易地告诉他 x 的大小），
然后计算下面 100个数,
1001),m o d( ??? upyz uu
然后他对所有 验证 vu ?
2|| ?? vu zz
并对所有的 u 验证
10 ??? pz u
如果不成立,Bob就选择另一个素数并重复试验。
2012-3-19 105
不经意传输和安全多方计算
（ 4） Bob将以下数列发送给 Alice,
z1,z2,…,zj,zj+1+1,zj+2+1,…,z100+1,p
（ 5） Alice检查这个数列中第 i 个数是否同余 x 模 p。
如果同余，她得出结论是 。ji ?
如果不同余，她得出结论是 i >j。
（ 6） Alice把这个结论告诉 Bob。
2012-3-19 106
不经意传输和安全多方计算
Bob在第（ 3）步中所作的验证完全是为了保证第（ 4）
步产生的数列中没有任何一个数出现两次，否则，如
果 za=zb,Alice就将知道 。bja ??
该协议的一个 缺点 是,Alice在 Bob之前就获悉了计算
结果。没有什么能阻止她完成该协议直到第（ 5）步，
然后在第（ 6）步拒绝告诉 Bob结果，甚至在第（ 6）
步有可能对 Bob撒谎。
第七章 密码协议
一,基本密码协议
二,中、高级密码协议
2012-3-19 2
一,基本密码协议
2012-3-19 3
身份认证协议
? 身 份 认 证 协 议 （ Identy Authentication
Protocols ）
Alice
Bob
Eve
Alice?
or Eve? Bob?
or Eve?
2012-3-19 4
身份认证协议
? 用户的身份认证是许多应用系统的第一道防
线，其目的在于识别用户的合法性，从而阻
止非法用户访问系统。身份识别（认证）对
确保系统和数据的安全保密是极其重要的。
2012-3-19 5
身份认证协议
? 安全的身份认证协议应该满足如下条件,
1,证明者 A能向验证者 B证明他确实是 B；
2,在证明者 A向验证者 B证明他的身份后, 验证者 B不能
获得任何有用的信息, B也不能模仿 A向其他第三方证
明他就是 A。
2012-3-19 6
身份认证协议
分析和评价身份认证协议应考虑如下几个方面,
（ 1） 是单方还是双方的身份认证；
（ 2）计算的有效性；
（ 3）通信的有效性；
（ 4）是否需要第三方的实时参与；
（ 5）对第三方的可信度的要求；
（ 6）安全保证（可证明安全、零知识证明）；
（ 7）用来存储共享秘密数据的地方和方法。
2012-3-19 7
身份认证协议
? 身份认证的类型,
弱认证：使用口令、口令段、口令驱动的密钥；
使用时间戳； 序列号方法等 。
强认证：通过向验证者展示与证明者实体有关的
信息来证明自己的身份。
2012-3-19 8
身份认证协议
? A,B 双方在建立共享密钥时需要考虑保密性
和实时性。
? 保密性：会话密钥应以密文传送，因此双方
应事先共享密钥或者使用公钥。
? 实时性,防止重放
– 询问－应答
– 时戳
– 序列号方法
2012-3-19 9
身份认证协议
传统的身份证明,
一般是通过检验, 物, 的有效性来确
认持该物的的身份 。 徽章, 工作证, 信
用卡, 驾驶执照, 身份证, 护照等, 卡
上含有个人照片 (易于换成指纹, 视网
膜图样, 牙齿的 X适用的射像等 )。
信息系统常用方式,
用户名和口令
2012-3-19 10
身份认证协议
? 交互式证明
两方参与
示证者 P(Prover)，知道某一秘密，使 V相信自
己掌握这一秘密；
验证者 V(Verifier)，验证 P 掌握秘密；每轮
V向 P 发出一询问,P 向 V 做应答。 V 检查 P
是否每一轮都能正确应答 。
2012-3-19 11
并将 y 发送给 B；
身份认证协议
)( xEy k?
? 询问－应答协议（ Challenge-response)
证明者 A 向验证者 B 认证自己,A 和 B共享一个
共同的秘密密钥 k,k 确定了一个加密算法 。
（ 1） B 随机选择一个口令 x（ x 是一个 64比特长的
随机串），并将 x 发送给 A；
（ 2） A 计算
（ 3） B 计算
kE
)( xEy k??
并验证是否有 。yy ??
2012-3-19 12
身份认证协议
Challenge-response
B A 口令 x
yy
??
)( xEy k?
)( xEy k??
口令协议的安全性是建立在 A 和 B 相互信任的
基础上的。属于弱认证协议。
2012-3-19 13
身份认证协议
时戳法
? A 收到消息中包含时戳，且 A 看来这一时戳
充分接近自己的当前时刻,A 才认为收到的
消息是新的并接收。
? 要求各方时间同步。
2012-3-19 14
身份认证协议
序列号方法
? 对交换的每一条消息加上序列号，序列号正
确才被接收。
? 要求每个用户分别记录与其他每一用户交互
的序列号，增加用户负担，因而很少使用。
2012-3-19 15
身份认证协议
各种方法的比较
? 询问－应答不适合于无连接的应用过程
– 在传输前需要经过询问－应答这一额外的握手过
程，与无连接应用过程的本质特性不符。
– 无连接应用最好使用安全时间服务器提供同步
2012-3-19 16
身份认证协议
各种方法的比较
? 时戳法不适用于面向连接的应用过程
– 要求不同的处理器之间时间同步，所用的协议必
须是容错的以处理网络错误
– 协议中任何一方时钟出现错误失去同步，则敌手
攻击的可能性增加
– 网络中存在延迟，不能期待保持精确同步，必须
允许误差范围
2012-3-19 17
身份认证协议
通信双方建立共享密钥时可采用单钥加密体制
和公钥加密体制
? 单钥加密体制
? 公钥加密体制
2012-3-19 18
身份认证协议
? Needham－ Schroeder协议
A B KDC
1,IDA|| IDB ||N1
)]||(||||||[2 1 AsKBsK IDKENIDKE BA、
]||[3 AsK IDKE B、
][4 2NE SK、
)]([5 2NfE SK、
2012-3-19 19
身份认证协议
然而 Needham－ Schroeder 协议易受到重放
攻击,
假定敌手能获得旧会话密钥，则冒充 A向 B重放第 3步
的消息后，就可以欺骗 B使用旧的会话密钥。敌手进
一步截获第 4步 B发出的询问后，可假冒 A作出第 5步
的应答。进而，敌手就可冒充 A使用经认证过的会话
密钥向 B发送假消息 。
2012-3-19 20
身份认证协议
? Needham－ Schroeder 改进协议（ 1）
KDC A B
BA IDID ||1、
)]||||(||||||[2 TIDKETIDKE AsKBsK BA、
]||||[3 TIDKE AsK B、
][4 1NE SK、
)]([5 1NfE SK、
sK
其中 T 为时间戳，用以向 A,B双方保证 的实时性。
2012-3-19 21
身份认证协议
要求各方时钟同步
如果发方时钟超前 B方时钟，可能导致等待重放攻击。
|Clock－ T|<⊿ t
1+⊿ t2
Clock:本地时钟
⊿ t1：本地时钟与 KDC时钟误差估计值
⊿ t2,网络延迟时间
2012-3-19 22
身份认证协议
? Needham－ Schroeder改进协议（ 2）
KDC A B
AA NID ||1、
]||||[||||2 BAAKBB TNIDENID B、
BBsAKBsABK NTKIDETKNIDE BA ||]||||[||]||||||[3,
][||]||||[4 AKBsAK NETKIDE sB、
该协议为 A,B 双方建立共享的会话密钥提供了一个安全有效的手段。
2012-3-19 23
身份认证协议
? 如果 A 保留由协议得到的票据，就可以在有效期内
可不通过 KDC直接认证
A B
'],||||[1 ABSAK NTKIDE
B、
][,2 '' AKB NEN S、
][3 'BK NE S、
B在第一步收到票据后，可以通过
BT
检验票据是否过时，而
新产生的一次随机数 则向双方保证了没有重放攻击 。
BA NN ??,
2012-3-19 24
身份认证协议
? Shnorr 身份认证协议
Shnorr 身份认证协议融合了 ELGamal协议、
Fiat-Shamir协议、和 Chaum-Evertse-Van de
Graff交互协议等协议的思想，是一种计算量
、通信量均少，特别适合智能卡上用户身份
识别的方案。
其安全性建立在计算离散对数问题的困难性
上的。
2012-3-19 25
身份认证协议
? Shnorr 身份认证协议需要一个可信中心 TA。
TA为协议选择下列参数,
（ 1） p 及 q 是两个大素数，且 q|(p-1);
的生成元。）
为，阶元（如可取为 pqpp ggqZ Z)2( /)1(* ??? ??
（ 3） h 是一个输出为 t为的单向函数,t为一个
安全参数 ;
（ 4）公开密钥 v和秘密密钥 s,可用作签名。
p,q,h 及其公开钥都公开，每个用户自己选定个人秘
密密钥 s,其计算公开密钥 v。 其中 。pvqs s m o d],1,1[ ???? ?
2012-3-19 26
身份认证协议
? 每位用户必须到 TA 注册其公开密钥。 TA
验明用户身份后，对每位用户指定一识别名 I
。 I中包括用户的姓名、性别、生日、职业、
电话号码、指纹信息等识别信息。 TA 再对
h(I,v)签名，以便将来验证只用。
? 在身份认证过程中，不需要 TA 介入。
2012-3-19 27
身份认证协议
? 证明者 A向验证者 B证明他身份（ Schnorr 认证
协议）
AvI,1、
A B
用 TA 的数字签名来
验证 A 的公开密钥 pZr *?任选
pX r m o d2 ??、
]2,1[ te ?任选整数3,e
qsery m o d4 ??、
。pvX ey m o d??
、验证 5
2012-3-19 28
身份认证协议
? Schnorr 协议的安全的基础是离散对数计算困
难性。从 v 求 s 就是求离散对数，在计算上
是不可行的。 r 和 s 都是用户的秘密，假冒者
Eve 是无法从 y 中得到用户的秘密，当然也
就无法假冒证明者 A。
2012-3-19 29
身份认证协议
? Okamoto 身份认证协议
Okamoto 身份认证协议是 Schnorr协议的一种
改进，是一个可证明安全的协议。 Okamoto
协议同样需要一个可信的 TA。
TA 选择两个大素数 p,q,q|(p-1)。
的元素，中两个阶为是 qZ p*21,??
。保密 21l o g ???cTA
TA 选择一个签名方案和一个 Hash函数
2012-3-19 30
身份认证协议
? TA 向 A 颁布一个证书，协议如下,
（ 1） TA 建立 A 的身份并颁布一个识别串 ID(A)。
（ 2） A 秘密地选择两个随机数,,
21 mm
,1,0 21 ??? qmm 并计算,m o d21 21 pv mm ??? ??
将 v 发给 TA。
（ 3） TA 对（ ID,v） 签名,。),( vIDs i gs
TA?
TA 将证书 C(A)=( ID(A),v,s ) 发送给 A。
2012-3-19 31
身份认证协议
? Okamoto 身份认证协议如下,
A B
随机选取,,
21 rr
1,0 21 ??? qrr
pX rr m o d21 21 ??? XsvAIDAC ),,),(()( ?
T u r esvIDV e r TA?),,( ?
,e随机选取 te 20 ??e
21,yy
pvX eyy m o d21 21? ???
验证
qemry m o d)( 111 ??
qemry m o d)( 222 ??
计算
2012-3-19 32
身份认证协议
? Guillou-Quisquater 身份认证协议
Guillou-Quisquater 身份认证协议的安全性
是基于 RSA 体制安全的。
TA 选择一个大素数 b（ 用作一个安全参数）
和一个公开的 RSA 加密指数。同时 TA 选择
一个签名方案和 Hash 函数。
TA 选择两个大素数 p 和 q,形成 n＝ pq。
保密 p 和 q,公开 n。
2012-3-19 33
身份认证协议
? TA 向证明者 A颁发一个证书,
（ 1） TA 建立 A 的身份并颁布一个识别串 ID(A)。
（ 2） A 秘密地选择一个随机整数 m,
,10 ??? nm 并计算,m o d)( 1 nmv b??
并将 v 发送给 TA。
（ 3） TA 对（ ID,v） 签名,。),( vIDs i gs
TA?
TA 将证书 C(A)=( ID(A),v,s ) 发送给 A。
2012-3-19 34
身份认证协议
? Guillou-Quisquater 身份认证协议
A B
随机选取 r
10 ??? nr
nrX b m o d? XsvAIDAC ),,),(()( ? T u r esvIDV e r
TA
),,( ?
,e随机选取 10 ??? bee
y
nyvX be m o d??
验证
nrmy e m o d?
计算
2012-3-19 35
身份认证协议
? 基于身份的身份认证协议
Shamir的基于身份的基于身份的密码方案的思想
Shamir在 1984年提出了一类新型的密码方案，这类方
案能使网上的任何一对用户无需交换秘密密钥或公开
密钥、无需保存密钥薄、无需使用第三方服务可进行
安全的通信和相互签名。
他不直接生成一对随机的公开密钥和秘密密钥，而是由
用户选择他的名字和网址来作为公开密钥。
2012-3-19 36
身份认证协议
? 几种密码体制的差别
加密 解密 消息 m
k
随机种子 k
（ a） 私钥密码体制
k
信使
消息 m 信道
加密 解密 消息 m
随机种子 k
（ b） 公钥密码体制
公钥号码薄
消息 m
ek dk
信道
2012-3-19 37
身份认证协议
加密 解密 消息 m
密钥的产生
（ c） 基于身份的密码体制
消息 m 信道
ek接收者的身份 dk
随机种子 k
2012-3-19 38
身份认证协议
? Guillou-Quisquater 的基于身份的认证协议
TA 为 A 颁发一个值 u 的过程如下,
（ 1)TA 建立 A 的身份并颁布一个识别串 ID(A)；
（ 2） TA 计算,m o d))((( 1 nAIDHu a?? 并将 u 发给 A。
其中 H 是一个公开的 Hash 函数。参数选择和
Guillou-Quisquater协议中一样，且
)(m o d1 nab ??
2012-3-19 39
身份认证协议
? Guillou-Quisquater 的基于身份的认
证协议
A B
r
10 ??? nr
nrX b m o d? XAID ),(
,e随机选取 10 ??? bee
y
nyvX be m o d??
nruy e m o d?
计算
))(( AIDHv ?
计算
2012-3-19 40
密钥交换协议
哈哈 ！ …
我也知道你
们的秘密了
攻击者
窃听者
明文
m 公开信道
明文 m
Alice Bob
明文
m
明文在公开信道中传输
2012-3-19 41
密钥交换协议
信息传输模型
加 密 明文 m 公开信道
明文
m
加密
密钥
Alice
解 密 密文 c
解密
密钥
Bob
攻击者
我晕 ！ … 他
们的秘密是什
么呢？？？
2012-3-19 42
密钥交换协议
传统的密钥分配方式
信使
会话密钥 K 会话密钥 K
Alice Bob
2012-3-19 43
密钥交换协议
? 密钥交换协议 (key exchange protocol)是指两人
或多人之间通过一个协议取得会话密钥并用于
进一步的加密算法或会话中的方法 。 在实际的
密码世界中密钥交换其实是很重要的一个环节
。
? 密钥交换协议往往会和身份认证协议结合, 这
样才能得到更安全的密钥交换协议 。
2012-3-19 44
密钥交换协议
? 对称密码学的密钥交换
协议中 Alice和 Bob各与密钥分配中心 KDC共享
一个秘密密钥
KDC
Alice Bob
。BA kk,
1、请求
2、产生一个
随机会话密钥
ABk
)(),(2 ABkABk kEkE BA、
ABABkkA kkED A ?)]([3,
)(4 ABk kE B、
ABABkkB kkED B ?)]([5,
(1)该协议要求
KDC绝对可信；
(2)KDC可能会成
为瓶颈。
2012-3-19 45
密钥交换协议
? 公钥秘密学的密钥交换
Alice和 Bob使用公开密钥密码协商会话密钥，并用协
商的会话密钥加密数据。
Alice的私钥和公钥分别为
AA pksk,
Bob的私钥和公钥分别为
BB pksk,
产生会话
密钥 k
KDC
Alice Bob
Bpk
)( kE Bpk
kkED BB pksk ?)]([
在实用中，公钥
可以从数据库中
获得，使得密钥
交换协议更容易
。但 Bob不知道和
他通信的人就一
定是 Alice。
2012-3-19 46
密钥交换协议
? 具有保密性和认证性的密钥交换
Alice Bob
]||[ 1 Ap k B IDNE①
]||[ 21 NNE p k A②
][ 2NE pkB③
④ )]([ ss k Ap k B kEE
由于协议中使用了随机数 N1和 N2和采用了公
钥加密，通信双方能确信对方的身份 。
2012-3-19 47
密钥交换协议
? Diffie－ Hellman密钥交换协议
算法的安全性基于求离散对数的困难性
Alice Bob
xA xB pgX
Ax m o d?
pgY Bx m o d?pg
pYk
BA
A
xx
x
m o d
m o d
?
?
pg
pXk
BA
B
xx
x
m o d
m o d
?
?
系统参数,p是一个大素数,g是 Z*p的一个生成元。
该协议
容易受
到中间
人攻击
Diffie－ Hellman 两方密钥交换协议
2012-3-19 48
密钥交换协议
? 如果 被动攻击者 能窃听 Alice和 Bob的通信,
并截获,
BA xx gYgX ??,
性，他无法得到 xA,xB。
由离散对数的困难
，BA xx gg,窃听者由 无法计算出会话密钥
pgk BA xx m o d?
2012-3-19 49
密钥交换协议
? 例,取 p＝ 23,g＝ 5
Alice 选择 xA＝ 7,Bob 选择 xB＝ 15。
1723m o d5 7 ??? AxgX
Bob 计算
1923m o d5 15 ??? BxgY
交换 X,Y 后
Alice 计算
Bob 计算
1523m o d19 7 ??? AxYk
1523m o d17 15 ??? BxXk
Alice 计算
2012-3-19 50
密钥交换协议
? 对 Diffie－ Hellman密钥交换协议的 中间人攻
击
Alice Bob
xA xB
pgX Ax m o d?
pgY Bx m o d?
Diffie－ Hellman 两方密钥交换协议的中间人攻击
Adversary
pgZ A d vx m o d?
pgZ A d vx m o d?
pg
pZk
BA d v
B
xx
x
m o d
m o d2
?
?
pg
pZk
AA d v
A
xx
x
m o d
m o d1
?
?
2012-3-19 51
密钥交换协议
? Diffie－ Hellman 三方密钥交换协议
A
C
B Ax Bx
Cx
pgX Ax m o d?①
pgY Bx m o d?②
pgZ Zx m o d?③
pZZ Ax m o d??④
pXX Bx m o d??⑤ pYY
Cx m o d??⑥
⑦ pYk A
x m o d??
⑧ pZk
Bx m o d??
⑨
pXk Cx m o d??
pgk CBA xxx m o d?
会话密钥 系统参数,p是一个大素数,g是 Z*p的一
个生成元。
2012-3-19 52
密钥交换协议
? 密钥交换四方协议,
A
D
C
B
1rg①
2211,,rrrr ggg
②
213213231,,,rrrrrrrrr gggg
③
432 rrrg
④
431 rrrg⑤
421 rrrg⑥
会话密钥为
pgk rrrr m o d4321?
系统参数,p是一个大素数,g是 Z*p的
一个生成元。以上运算均为模运算。
缺陷：第四
方权限过大
2012-3-19 53
密钥交换协议
Shamir 协议
在 Shamir 协议下, 任意秘密通信的双方都不必建立
公钥或私钥, 只需要通过该协议便可获得保密通信
的会话密钥 。
Shamir 协议可形象看作是 A先将保密的会话密钥 k装
入保险箱, 锁上只有他自己才能打开的锁, 然后寄
给 B。 B 收到后, 他不能打开这个箱子, 只能加上只
有 B才能打开的另一把锁, 再退还给 A。 此时箱子上
有两把锁, A 开启他锁上的锁, 再寄给 B,B 再打开
他自己加上的锁, 然后取出保密的会话密钥 。
2012-3-19 54
密钥交换协议
Shamir 协议中加密密钥 EA,解密密钥 DA 均由 A
自己秘密保管, EB,DB 也是一样 。 协议具体如下,
A B
随机产生一
个会话密钥 k
)(kE A
)]([ kEE AB
)(
)]]([[
kE
kEED
B
ABA
? )(kE B
kkED BB ?)]([
Shamir协议要求加密算法是可交换的，即 )]([)]([ kEEkEE
ijji ?
一次一密密码系统是可交换的,RSA 密码体制也是可交换的。
2012-3-19 55
密钥交换协议
? 如果加密、解密算法是按位 ⊕ 运算，则可以恢
复出会话密钥的。从这种攻击来说,Shamir
协议是不安全的。
? 如果 Shamir 协议采用 RSA密码体制进行加密、
解密，则是安全的 。
? Shamir 协议没有身份认证，只存在保密。在
保密通信前缺少对发信方的身份验证，这也容
易受到中间人攻击。
2012-3-19 56
密钥交换协议
? 以上协议基本上没有身份认证。 Alice和 Bob
通过密钥交换协议得到了会话密钥，但他们
无法确认和自己通信的人就是 Alice或 Bob，
这也是以上协议的一个安全隐患。把密钥交
换协议和身份认证协议结合，就可以得到更
安全的密钥交换协议－ 可认证的密钥交换协
议。
2012-3-19 57
密钥交换协议
? Yahalom协议
这个协议中 Alice和 Bob两人各与 KDC共享一个秘密密钥
EA,EB。
Alice KDC BOb
(A,RA)
EB(A,RA,RB)
EA(B,k,RA,RB),EB(A,k)
解密得 k和 RA并
确认 RA的有效性
EB(A,k),Ek(RB)
解密得 k,再解密得 RB,
确认 RA的有效性
A,B分
别为
Alice,
Bob的名
字。 RA,
RB为随
机数
通过该协议,Alice,Bob互相确信是
正在同对方谈话，而不是跟第三方。
2012-3-19 58
密钥交换协议
? Kerberos协议
这个协议中 Alice和 Bob两人各与 KDC共享一个秘密密钥
EA,EB。 Alice想产生一会话密钥用于与 Bob通信。
协议如下,
KDC Alice Bob
A,B
EA(T,L,K,B),EB(T,L,K,A)
EK(A,T),EB(T,L,K,A)
EK(T+1)
A,B分
别为
Alice,
Bob的名
字。 RA,
RB为随
机数
2012-3-19 59
密钥交换协议
? Kerberos协议是可行的，但它假设每个人的
时钟都与 KDC的时钟同步。实际上，这个结果
是通过把时钟同步到一个安全的定时服务器
的几分钟之内，并在这个时间间隔内检测重
放而获得的。
2012-3-19 60
密钥交换协议
? 分布式鉴别安全协议－ DASS 协议
Alice和 Bob每人有一个私人密钥,KDC有他们公开密
钥签名的副本。
（ 1） Alice送一个消息给 KDC,这个消息由 Bob的名字
组成,B。
（ 2） KDC把 Bob的公开密钥 KB发给 Alice,并用自己的
私人密钥 T 签名。签名消息包括 Bob的名字,ST(B,KB)
（ 3） Alice验证 KDC 签名以确认她接收的密钥确实是
Bob的公开密钥。她产生一随机会话密钥 K和一公开密
钥 /私人密钥对 KP,她用 K加密时间标记 TA,然后用她
的私人密钥 KA对会话密钥的寿命周期 L,她的名字和
KP签名。
2012-3-19 61
密钥交换协议
。))((),,,(),( KESKALSTE BPA KKPKAK
Alice给 Bob发送消息,
（ 4） Bob发送一个消息给 KDC,它由 Alice的名字组成,A
（ 5） KDC把 Alice的公开密钥 KA 发给 Bob,并用自己的私
人密钥 T签名,ST(A,KA)。
（ 6） Bob验证 KDC的签名以确认他接收的密钥确实是
Alice的公开密钥。然后他验证 Alice的签名并恢复出 KP。 他
验证签名并用他的私人密钥恢复 K。 然后解密 TA以确信这
是当前的消息。
（ 7）如果需要相互鉴别,Bob用 K加密一个新的时间标记
，并把它发送给 Alice,EK(TB),
（ 8） Alice用 K解密 TB 以确认消息是当前的 。
2012-3-19 62
二、高级协议
2012-3-19 63
比特承诺协议
? 问题,
股票经纪人 Alice想说服投资商 Bob她的选取赢利股票的方法
很不错 。
Bob说：, 给我选 5支股票, 如果都赢利, 我将把生意给你 。
”
Alice说：, 如果我为你选了 5支股票, 你可以自己对他们投
资, 而不用给我付款 。 我为什么不向你出示我上个月选的
股票呢？,
Bob说：, 我怎样知道你在了解上月股票的收益后没有改变
你上月选择的股票呢？ 如果你现在告诉我你选的股票, 我
就可以知道你不能改变他们 。 在我买你的方法以前我不在
这些股票中投资 。 相信我 。,
2012-3-19 64
比特承诺协议
Alice说：, 我宁愿告诉你我上月选择的股票 。 我不会
变, 相信我 。,
Alice想对 Bob承诺一个预测（即 1位或位序列），但直
到某个时间以后才揭示她的预测。而另一方面,Bob
想确信 Alice承诺了她的预测后，她没有改变她的想
法。
2012-3-19 65
比特承诺协议
? 一般地，一个比特承诺方案就是一个函数
YXf ??}1,0{:
这里 X 和 Y 是两个有限集。 }1,0{?b 的一个
加密是 Xxxbf ?)},({ 中的一个值。
比特承诺协议满足以下两个特性,
（ 1）隐蔽性（ Concealing）。 对 }1,0{?b
不能从 f(b,x) 确定 b 的值。
接收者
（ 2）约束性（ Binding）。 发送者能打开 f(b,x)
,即发送者能通过揭露用于加密的 b 的 x 的值使
接收者相信 b 的确是被加密的值。
2012-3-19 66
比特承诺协议
? 使用对称密码学的比特 （ 位 ） 承诺协议
（ 1） Bob产生一个随机比特串 R,并把它发送给 Alice,R。
（ 2） Alice产生一个由她想承诺的位 b组成的消息 （ b实际上
可能是几位 ）, 已经 Bob的随机串 。 她用某个随机密钥 K
对它加密, 并将结果送回给 Bob,EK(R,b)。
这是一个协议的承诺部分, Bob不能解密消息, 因而不知
道位为何 。 当到了 Alice揭示她的位的时候, 协议继续,
（ 3） Alice发送密钥给 Bob；
2012-3-19 67
比特承诺协议
（ 4） Bob解密消息以揭示位。他检测他的随机串以证
实位的有效性。
如果消息不包括 Bob的随机串,Alice能够秘密地用一
系列密钥解密她交给 Bob的消息，直到找到她的位，
而不是她的承诺位。由于位只有两种可能的值，她
只需试几次肯定可以找到一个。 Bob的随机串避免了
这种攻击，她必须能找到一个新的消息，这个消息
不仅使她的位反转，而且使 Bob的随机串准确地重新
产生。如果加密算法好，她发现这种消息的机会是
极小的。 Alice不能在她承诺后改变她的 位。
2012-3-19 68
比特承诺协议
? 使用单向函数的比特（位）承诺协议
该协议利用单向函数来实现位承诺。协议如下,
（ 1） Alice产生两个随机位串,R1,R2。
（ 2） Alice产生消息，该消息由她的随机串和她的希望
承诺的位（实际上可能是几位）组成,(R1,R2,b)。
（ 3） Alice计算消息的单向函数值，将结果以及其中一
个随机串发送给 Bob,H(R1,R2,b),R1。
这个来自 Alice的传送就是承诺证据。 Alice在第（ 3）
步使用单向函数阻止 Bob对函数求逆并确定这个位 。
2012-3-19 69
比特承诺协议
（ 4） Alice将原消息发给 Bob,（ R1,R2,b）。
（ 5） Bob计算消息的单向函数值，并将该值及 R1与原
先受到的值及随机串比较。如匹配，则位有效。
这个协议的优点在于 Bob不必发送任何消息。只要
Alice发送给 Bob一个对位承诺的消息，已经另一揭示
该位的消息。
这里步需要 Bob的随机串，因为 Alice承诺的结果是对消
息进行单向函数变换得到的。 Alice不可能欺骗，并
找到另一个消息 （ R1’,R2’,b’）,以满足 H(R1,R2,b)＝
H(R1’,R2’,b’)。
2012-3-19 70
比特承诺协议
? 使用伪随机序列发生器的比特（位）承诺
（ 1） Bob产生随机位串，并发送给 Alice,RB。
（ 2） Alice位伪随机位发生器产生一个随机种子。然后，对
Bob随机位串中的每一位（比特），她回送 Bob下面两个
中的一个,
（ a） 如果 Bob的位为 0，则为发生器的输出。
（ b)如果 Bob的位位 1，则为发生器输出与她的位的异或
。
2012-3-19 71
比特承诺协议
（ 3） Alice将随机种子送给 Bob。
（ 4） Bob确认 Alice的行动是合理的。
如果 Bob的随机位串足够长，伪随机位发生器不可预
测，这时 Alice就无有效的 方法进行欺诈。
2012-3-19 72
比特承诺协议
? 抛币协议
某些密码协议中要求通信双方在无第三方协
助情况下，产生一个随机序列，因为 A,B之
间不存在信任关系，因此不能由一方产生在
通过网络或电话告诉另一方
2012-3-19 73
比特承诺协议
? 使用单向函数的抛币协议
Alice,Bob都知道某一单向函数 f(x)，但都不知道
逆函数
(1)Alice选择一个随机数 x，求 y＝ f (x) 并发给 Bob
(2)Bob猜测 x 的奇偶性，并将结果告诉 Alice
(3)Alice告诉 Bob猜测正确不正确，并将 x 发给 Bob
(4)Bob确信 y＝ f (x)
? 安全性
– Bob不知道 f (x)的逆函数，无法由 y 求 x，只能猜
– Alice若在 Bob猜测后改变 x,Bob可以通过 y=f (x)?
检查 出来
2012-3-19 74
零知识证明协议
背景,
Alice,我知道联邦储备系统计算机的口令，汉堡包秘密调味
汁的成分以及 Knuth第 4卷的内容。
Bob,不，你不知道。
Alice,我知道。
Bob,你不知道。
Alice,我确实知道！
Bob,请你证实这一点！
Alice,好吧，我告诉你！（她悄悄地说出了口令）
Bob,太有趣了！现在我页知道了。我要告诉《华盛顿邮报,
Alice,啊呀！
2012-3-19 75
零知识证明协议
? 不幸的是,Alice用常用的方法给 Bob证明她知道的
秘密。这样一来,Bob也知道了这些秘密了，现在
Bob要告诉其他人,Alice对此毫无办法。
? 问题,有没有一种有效的办法，让 Alice给 Bob证
明她知道这些秘密，使得 Bob可以确信 Alice的确知
道这些，但 Bob根本不能获得这些秘密的任何消息呢
？
2012-3-19 76
零知识证明协议
? 零知识证明的思想,
零知识证明采用交互式协议的形式。
Alice要向 Bob证明她知道某些秘密，可如下进行,
Bob问 Alice一系列问题，如果 Alice知道那个秘密，她
就能正确回答所有问题。如果她不知道，她仍有 50
％的机会回答每一个问题，但要猜对每个问题的机
会实在太小了（几乎不可能）。大约 10个问题之后
，将使 Bob确信 Alice是否知道那个秘密。然而所有回
答都没有给 Bob提供 Alice所知道的 秘密的任何信息。
2012-3-19 77
零知识证明协议
? 零知识基本协议 Quisquater－ Guillou 协议
设 Alice知道咒语,
可打开 C和 D之间的
秘密门，不知道者
都将走向死胡同 中 。
A
B
C D
2012-3-19 78
零知识证明协议
? 零知识证明的基本协议
(1) Bob站在 A 点；
(2) Alice进入洞中任一点 C 或 D；
(3) 当 Alice进洞之后, Bob走到 B 点；
(4) Bob叫 Alice,(a)从左边出来, 或 (b)从右边出来；
(5) Alice按要求实现 (以咒语, 即解数学难题帮助 )；
(6) Alice和 Bob重复执行 (1)～ (5)共 n 次 。
2012-3-19 79
零知识证明协议
? 若 Alice 不知咒语，则在 B 点，只有 50 %的机会猜中
Bob的要求，协议执行 n 次，则只有 2-n 的机会完全猜中
，若 n=16，则若每次均通过 Bob 的检验,B受骗机会仅
为 1/65536。
? 如果 Bob用摄像机记录下他所看到的一切，他把录像给
Carol看,Carol会相信这是真的吗？ Carol是不会相信
这是真的。
? 这说明了两件事情：其一,Bob不可能使第三方相信这
个证明；其二，它证明了这个协议是零知识的。 Bob在
不知道咒语的情况下，显然不能从录像中获悉任何信息
。
2012-3-19 80
零知识证明协议
? 基本零知识协议由下面几轮组成,模型
如下,
（ 1） Alice用她的信息和一个随机数将这个难题转变为
另一个难题，新的难题和原来的难题同构。然后她
用她的信息和这个随机数解这个新的难题。
（ 2） Alice利用位承诺方案提交这个新的难题的解法。
（ 3） Alice向 Bob透露这个新的难题。 Bob不能利用这
个新的难题得到关于原难题 或其解法的任何信息。
2012-3-19 81
零知识证明协议
（ 4） Bob要求 Alice,
（ a） 向他证明新、旧难题是同构的（即两个相关问
题的两种不同解法）或者
（ b） 公开她在第（ 2）步中提交的解法并证明新难题
的解法。
（ 5） Alice同意。
（ 6） Alice和 Bob重复第（ 1）至（ 5）步 n 次
2012-3-19 82
零知识证明协议
哈米尔顿回路
图论中有一个著名问题，对有 n个顶点的全连通
图 G，若有一条通路可通过且仅通过各顶点一次，
则称其为哈米尔顿回路。 Blum[1986] 最早将其
用于零知识证明。当 n大时，要想找到一条
Hamilton回路，用计算机做也要好多年，它是一
种单向函数问题。若 A知道一条回路，如何使
Bob相信他知道，且不告诉他具体回路？
2012-3-19 83
零知识证明协议
回路与 H 上的 Hamilton 回路一一对应。已知 G 上的
Hamilton 回路易于找出 H 上的相应回路；
(2) Alice将 H的复本给 Bob；
(3) Bob 向 Alice提出下述问题之一,(a) 出示证明 G 和
H 同构,(b) 出示 H 上的 Hamilton 回路；
(4) Alice执行下述任务之一,(a) 证明 G 和 H 同构，但
不出示 H上的 Hamilton 回路,(b) 出示 H 上的 Hamilton
回路但不证明 G和 H 同构；
(5) Alice和 Bob重复执行 (1)～ (4)共 n 次。
HG ?
(1) Alice将 G 进行随机臵换，对其顶点进行移动，并改变其
标号得到一个新的有限图 H。因, 故 G上的 Hamilton
2012-3-19 84
零知识证明协议
? Fiat-Shamir身份识别方案
(1) Alice 取随机数 r(<m),计算 x= r2 mod m,送给 Bob；
(2) Bob 将一随机 bit b 送给 Alice；
(3) 若 b=0,则 Alice 将 r 送给 Bob； 若 b=1,则 Alice将 y=rs送
给 Bob；
(4) 若 b=0,则 Bob 证实 x=r2modm,从而证明 Alice 知道,
若 b=1,则 Bob 证实 xv=y2modm,从而证明 Alice 知道 。
这是一次证明, Alice 和 Bob 可将此协议重复 t 次, 直到
Bob 相信 Alice 知道 s 为止 。
2012-3-19 85
零知识证明协议
? 完备性
– 如果 Alice和 Bob遵守协议，且 Alice知道 s，则应答 rs
是应是模 m下 xv的平方根,Bob接收 Alice的证明，所
以协议是完备的。
? 正确性
– Alice不知道 s，他也可取 r，送 x=r2 mod m给 Bob，
Bob送 b 给 Alice。 Alice可将 r送出，当 b=0时则 Bob可
通过检验而受骗，当 b=1时，则 Bob可发现 Alice不知 s
,B受骗概率为 1/2，但连续 t 次受骗的概率将仅为 2-t
– Bob无法知道 Alice的秘密，因为 Bob没有机会产生
(0,1)以外的信息,Bob送给 Alice的消息中仅为 Alice知
道 v的平方根这一事实。
2012-3-19 86
零知识证明协议
最小泄露证明和零知识证明,
以一种有效的数学方法, 使 V可以检验每
一步成立, 最终确信 P知道其秘密, 而又能
保证不泄露 P所知道的信息 。
2012-3-19 87
不经意传输和安全多方计算
? 不经意传输 （ Oblivious Transfer）
设 A有一个秘密, 想以 1/2的概率传递给 B,即 B有 50%的
机会收到这个秘密, 另外 50%的机会什么也得不到, 协
议执行完后, B知道自己是否收到了这个秘密, 但 A却步
知道 B是否收到了这个秘密 。 这种协议称为不经意传输
协议 。
例如,A是机密的出售者, A列举了很多问题, 意欲出
售各个问题的答案, B想买其中一个问题的答案, 但又
不想让 A知道自己买的是哪个问题的答案 。
2012-3-19 88
不经意传输和安全多方计算
? 基于大数分解的不经意传输协议
A 想通过不经意传输协议传给 B 大数 n 的因子分子
如果已知某数在模 n下的两个不同的平方根，就可以分解 n。
1,B 随机选一数 x，将 x2modn 发给 A。
2,A（掌握 n＝ pq 的分解）计算 x2mod n 的 4个平方根
± x,± y,将其中之一发给 B。 A只知道 x2modn, 并不知
道 4个平方根中的哪一个被 B 选中。
3,B 检查收到的数是否与 ± x 在模 n 下同余，如果是，
B没有得到任何新的信息，否则 B 掌握了 x2mod n 的两个
不同的平方根，从而可以分解 n，而 A 确不知道究竟是
哪种情况。
2012-3-19 89
不经意传输和安全多方计算
此协议是非交互的, 其中 B不向 A发送任何消息 。
设系统中所有用户都知道一个大素数 p,Z*p的生成元 g
和另一个素数 c,但无人知道 c的离散对数 。 假定计算
离散对数是不可行的, 因此 gxmodp和 gymodp无法计算
gxymodp。
B的加密, 解密密钥：随机选取一个比特 i 和一个数 x
? 基于离散对数问题的不经意传输协议
)20( ??? px
，计算 yi=gx,y1-i=cg-x,以 (y0,yi)作为加密公钥,
以 (i,x)作为解密密钥。
2012-3-19 90
不经意传输和安全多方计算
由于 B不知道 c的离散对数，所以他知道 y0 或 y1的离散对
数，而 A无法知道 y0或 yi中的哪个离散对数是 B已知的。
A可通过方城 y0 y1=c 来检查 B的公钥是否正确。
设 A的两个秘密 s0和 s1是二进制数,⊕ 是异或运算，若进
行异或运算的两个数不等长，可在较短数前面补 0。
（ 1） A在 0到 p－ 2之间随机取两个整数 k0,k1,对 j=0,1计算
,,,jjjkjjkj dsmydgc jj ???? 将 1010,,,mmcc 发送给 B。
（ 2） B用自己的解密密钥计算 。iiiikixkxi dmsdygc ii ?????,
由于 B不知道 y1-i 的离散对数，所以无法得到 d1-i和 s1-i。
2012-3-19 91
不经意传输和安全多方计算
?, 多传一, 的不经意传输协议
设 A有多个秘密，想将其中一个传递给 B,使得只有 B知
道 A传递的是哪个秘密。设 A的秘密是 s1,s2,…,sk,每一
秘密是一比特串。协议如下,
（ 1） A告诉 B一个单向函数 f,但对 f--1保密。
（ 2）设 B想得到秘密 si,他在 f 的定义域内随机选取 k 个
值 x1,x2,…,xk,将 k 元组 (y1,y2,…,yk)发给 A,其中
?
?
?
?
?
?
ijxf
ijx
y
i
j
j )(
2012-3-19 92
不经意传输和安全多方计算
（ 3） A计算 ),,2,1()(1 kjyfz
jj ??? ?
,并将 ),,2,1( kjsz
jj ???
发送给 B。
（ 4）由于,))(()(
11 iiij xxffyfz ??? ??
所以 B知道 zi,因此可从
ii sz ?
获得 si。
由于 B没有 )( ijz
j ?
的信息，因此无法得到 )( ijs j ?, 而 A
不知道 k元组 (y1,y2,…,yk)中哪个是 f(xi),因此无法确定 B
得到的是哪个秘密。
2012-3-19 93
不经意传输和安全多方计算
? 不经意签名
不经意签名有两种类型,
（ 1） Alice有 n份不同的消息。 Bob可以选择其
中之一给 Alice签名,Alice没有办法知道她
签的哪一份消息。
（ 2） Alice有一份消息,Bob可以选择 n个密钥
中的一个给 Alice签署消息用,Alice无法知
道她用的哪一个密钥。
2012-3-19 94
不经意传输和安全多方计算
? 同时签约：面对面
Alice和 Bob想订立一个合约。他们同意了其中的措词，
但每个人都想等对方签名后再签名。为了保证公平他们
可以采用下面协议进行同时签约。
（ 1） Alice签上她的名字的第一个字母，并把合约递给 Bob。
（ 2） Bob签上他的名字的第一个字母，并把合约递给 Alice。
（ 3） Alice签上她的名字的第二个字母，并把合约递给 Bob。
（ 4） Bob签名签上他的名字的第二个字母，并把合约递给 Alice。
（ 5） 这样继续下去，直到 Alice和 Bob都签上他们的名。
2012-3-19 95
不经意传输和安全多方计算
这个协议有个明显的问题，如果有一个人的名字较
长，则协议就可能变得对名字较短的人不公平。如
果名字较长的人在另一个人签完名后，拒绝签名，
在这份合约对他就没有什么约束力。
解决办法：可以采用 Hash函数，把签名人的姓名变成等
长的哈希函数值（二进制串），然后再进行上面协
议。
2012-3-19 96
不经意传输和安全多方计算
? 同时签约：非面对面
这个协议,Alice和 Bob交换一系列签名消息：我同意我以概
率 p 接受这个合约约束。
（ 1） Alice和 Bob就签约应当完成的日期达成一致意见。
（ 2） Alice和 Bob确定一个双方都愿意用的概率差。设 Alice
的概率差为 a,Bob的概率差为 b。
（ 3） Alice发给 Bob一份 p＝ a 的已签署的消息。
（ 4） Bob发给 Alice一份 p＝ a＋ b 已签署的消息。
（ 5）令 p为 Alice在前一步中从 Bob那里收到的消息的概率。
Alice发给 Bob一份 p’＝ p＋ a 或 1中较小的已签署的消息。
2012-3-19 97
不经意传输和安全多方计算
（ 6）令 p为 Bob在前一步中从 Alice那里收到的消息概率。
Bob发给 Alice一份 p’＝ p＋ b 或 1中较小的已签署的消息
。
（ 7） Alice和 Bob继续交通执行第（ 5）和第（ 6）步，直
到双方都收到 p＝ 1的消息，或者已到了在第（ 1）中达
成一致的日期。
2012-3-19 98
不经意传输和安全多方计算
? 同时签约：使用密码术
(1) Alice和 Bob二者随机选择 2n个 DES密钥，分成一对对的
。
(2） Alice和 Bob都产生 n对消息。如 Li,Ri：,这是我的第 i
个签名的左半部分”,,这是我的第 i 个签名的右半部分
” 。
(3) Alice和 Bob都二者用每个 DES密钥对加密他们的消息，
左半消息用密钥对中的左密钥，右半消息用密钥对中的
右密钥。
（ 4） Alice和 Bob相互发送给对方 2n份加密消息，弄清哪份
消息是哪对消息的哪一半 。
2012-3-19 99
不经意传输和安全多方计算
(5)Alice和 Bob利用每一对的不经意传输协议相互送给对
方，即 Alice送给 Bob或用于独立加密 n对消息中的每
一对左半消息的密钥；或用于加密右半消息的密钥
。 Bob也这样做。
(6)Alice和 Bob用收到的密钥解密他们能解密的那一半消
息。他们确信解密消息是有效的。
(7)Alice和 Bob都把 2n个 DES密钥的第一个发送给对方。
(8)Alice和 Bob对所有的 2n个 DES密钥的第二个位、第三
个位，重复第（ 7）步，如此继续下去，直到所有
DES密钥的所有位都被传送出去。
2012-3-19 100
不经意传输和安全多方计算
(9)Alice和 Bob解密剩余一半消息对，合约被签署。
(10)Alice和 Bob交换在第（ 5）步的步经意传输中使用的
私人密钥，并验证对方没有欺骗。
2012-3-19 101
不经意传输和安全多方计算
? 安全多方计算
安全多方计算在缺少信任的情况下，参与各
方秘密输入一个函数值，用一种特殊的方法
计算含有多个变量的函数。其中每个人都知
道函数的值，但除了函数的输出外，没有人
知道关于任何其他成员输入的任何信息。
安全多方计算在分布式密码系统中有非常重
要的应用。
2012-3-19 102
不经意传输和安全多方计算
? A.C.Yao.于 1982 年在,Protocols for secure comput
－ ations,首先提出安全多方计算问题－姚百万富翁
问题。
姚百万富翁问题的一般模型,
Alice知道一个整数 i,Bob知道一个整数 j,Alice和 Bob
ji ?
想知道是 i > j,还是, 但 Alice和 Bob都不希望泄露
他们各自知道的整数。
2012-3-19 103
不经意传输和安全多方计算
假定 i和 j 的取值范围是从 1到 100,Bob有一
个公开密钥和一个私人密钥。
（ 1） Alice选择一个大随机数 x,并用 Bob的公开密钥加
密,c=EB(x)。
（ 2） Alice计算 c-i,并将结果发送给 Bob。
（ 3） Bob计算下面的 100个数,
yu=DB(c-i+u),。1001 ?? u
DB是使用 Bob的私人密钥的解密算法
。
2012-3-19 104
不经意传输和安全多方计算
Bob选择一个大的随机数 p（ p 的大小应比 x 稍小一点
,Bob不知道 x,但 Alice能容易地告诉他 x 的大小），
然后计算下面 100个数,
1001),m o d( ??? upyz uu
然后他对所有 验证 vu ?
2|| ?? vu zz
并对所有的 u 验证
10 ??? pz u
如果不成立,Bob就选择另一个素数并重复试验。
2012-3-19 105
不经意传输和安全多方计算
（ 4） Bob将以下数列发送给 Alice,
z1,z2,…,zj,zj+1+1,zj+2+1,…,z100+1,p
（ 5） Alice检查这个数列中第 i 个数是否同余 x 模 p。
如果同余，她得出结论是 。ji ?
如果不同余，她得出结论是 i >j。
（ 6） Alice把这个结论告诉 Bob。
2012-3-19 106
不经意传输和安全多方计算
Bob在第（ 3）步中所作的验证完全是为了保证第（ 4）
步产生的数列中没有任何一个数出现两次，否则，如
果 za=zb,Alice就将知道 。bja ??
该协议的一个 缺点 是,Alice在 Bob之前就获悉了计算
结果。没有什么能阻止她完成该协议直到第（ 5）步，
然后在第（ 6）步拒绝告诉 Bob结果，甚至在第（ 6）
步有可能对 Bob撒谎。
