2010-5-14 1
第八章 数字签字和密码协议
2010-5-14 2
? 数字签字的基本概念
? 数字签字标准
? 其他签字方案
? 认证协议
? 身份证明技术
? 其他密码协议
2010-5-14 3
身份证明技术
2010-5-14 4
身份证明技术
传统的身份证明：
一般是通过检验, 物, 的有效性来确认
持该物的的身份 。 徽章, 工作证, 信用
卡, 驾驶执照, 身份证, 护照等, 卡上
含有个人照片 (易于换成指纹, 视网膜图
样, 牙齿的 X适用的射像等 )。
信息系统常用方式：
用户名和口令
2010-5-14 5
交互式证明
两方参与
示证者 P(Prover)，知道某一秘密，使 V相信
自己掌握这一秘密；
验证者 V(Verifier)，验证 P掌握秘密；每轮 V
向 P发出一询问,P向 V做应答。 V检查 P是否
每一轮都能正确应答。
2010-5-14 6
交互证明与数学证明的区别
? 数学证明的证明者可自己独立的完成证
明
? 交互证明由 P产生证明,V验证证明的有
效性来实现，双方之间要有通信
? 交互系统应满足
? 完备性：如果 P知道某一秘密,V将接收 P的
证明
? 正确性：如果 P能以一定的概率使 V相信 P的
证明，则 P知道相应的秘密
2010-5-14 7
Fiat-Shamir身份识别方案
参数：
选定一个随机模 m=p× q。 产生随机数 v，
且使 s2=v,即 v为模 m的平方剩余 。 m和
v是公开的, s作为 P的秘密
2010-5-14 8
Fiat-Shamir身份识别方案
(1) P取随机数 r(<m),计算 x= r 2 mod m,送给 V；
(2) V将一随机 bit b送给 P；
(3) 若 b=0,则 P将 r送给 V；若 b=1,则 P将 y=rs送给 V；
(4) 若 b=0,则 V证实 x=r 2 mod m,从而证明 P知道, 若
b=1,则 B证实 xv=y2 mod m,从而证明 A知道 。
这是一次证明, A和 B可将此协议重复 t次, 直到 B相
信 A知道 s为止 。
2010-5-14 9
Fiat-Shamir身份识别方案
? 完备性
? 如果 P和 V遵守协议，且 P知道 s，则应答 rs是应是模 m下 xv的平
方根,V接收 P的证明，所以协议是完备的。
? 正确性
? P不知道 s，他也可取 r，送 x=r2 mod m给 V,V送 b给 P。 P可将
r送出，当 b=0时则 V可通过检验而受骗，当 b=1时，则 V可发
现 P不知 s,B受骗概率为 1/2，但连续 t次受骗的概率将仅为 2-t
? V无法知道 P的秘密，因为 V没有机会产生 (0,1）以外的信息,P
送给 V的消息中仅为 P知道 v的平方根这一事实。
2010-5-14 10
零知识证明
最小泄露证明和零知识证明,
以一种有效的数学方法, 使 V可以检验每
一步成立, 最终确信 P知道其秘密, 而又
能保证不泄露 P所知道的信息 。
2010-5-14 11
零知识证明的基本协议
例 [Quisquater等 1989]。
设 P知道咒语,可
打开 C和 D之间的秘
密门，不知道者
都将走向死胡同中。
A
B
C D
2010-5-14 12
零知识证明的基本协议
(1) V站在 A点；
(2) P进入洞中任一点 C或 D；
(3) 当 P进洞之后, V走到 B点；
(4) V叫 P,(a)从左边出来, 或 (b)从右边出来；
(5) P按要求实现 (以咒语, 即解数学难题帮助 )；
(6) P和 V重复执行 (1)～ (5)共 n次 。
若 A不知咒语，则在 B点，只有 50 %的机会猜中 B的
要求，协议执行 n次，则只有 2-n的机会完全猜中，若
n=16，则若每次均通过 B的检验,B受骗机会仅为 1/65
536
2010-5-14 13
零知识证明的基本协议
哈米尔顿回路
图论中有一个著名问题, 对有 n个顶点的全连
通图 G,若有一条通路可通过且仅通过各顶点
一次, 则称其为哈米尔顿回路 。 Blum[1986] 最
早将其用于零知识证明 。 当 n大时, 要想找到
一条 Hamilton回路, 用计算机做也要好多年,
它是一种单向函数问题 。 若 A知道一条回路,
如何使 B相信他知道, 且不告诉他具体回路？
2010-5-14 14
(1) A将 G进行随机置换, 对其顶点进行移动, 并改变
其标号得到一个新的有限图 H。 因, 故 G上的
Hamilton回路与 H上的 Hamilton回路一一对应 。 已知
G上的 Hamilton回路易于找出 H上的相应回路；
(2)A将 H的复本给 B；
(3) B向 A提出下述问题之一,(a) 出示证明 G和 H同构,
(b) 出示 H上的 Hamilton回路；
(4) A执行下述任务之一,(a) 证明 G和 H同构, 但不出
示 H上的 Hamilton回路, (b) 出示 H上的 Hamilton回
路但不证明 G和 H同构；
(5) A和 B重复执行 (1)～ (4)共 n次 。
HG?
2010-5-14 15
其他密码协议
2010-5-14 16
智力扑克
? A和 B通过网络进行智力扑克比赛，不用第三方做裁
判，发牌者由任一方担任，要求发牌过程满足
1,任一副牌是等可能的
2,发给 A,B的牌没有重复
3,每人知道自己手中的牌，不知道别人的牌
4,比赛结束后，每一方都能发现对方的欺骗行为
? 为满足要求,A,B方需要加密一些信息，比赛结束前，
这些机密算法都是保密的。
2010-5-14 17
智力扑克
? A和 B的加密解密算法记为 EA,EB,DA，
DB，满足 EA(EB(m))= EB( EA(m))
? A,B协商好用以表示 52张牌的 w1,…,w52
2.随机选 5个
EB(wi)
3.另选 5个
EB(wi)，以 EA加
密
以 DA解密
1.洗牌，用 EB对
52个 wi加密
解密，作为发给
自己的牌
以 DB解密
52个 EB（ wi）
5个随机的 EB（ wi）
5个的 EA(EB(wi))
5个的 EA(wi)
完后公开所有加密变换A B
2010-5-14 18
掷硬币协议
? 某些密码协议中要求通信双方在无第三
方协助情况下，产生一个随机序列，因
为 A,B之间不存在信任关系，因此不能
由一方产生在通过网络或电话告诉另一
方
2010-5-14 19
掷硬币协议
? 利用单向函数掷硬币
? A,B都知道某一单向函数 f(x)，但都不知道逆函
数
1,B选择一个随机数 x，求 y＝ f(x)并发给 A
2,A猜测 x的奇偶性，并将结果告诉 B
3,B告诉 A猜测正确不正确，并将 x发给 A
? 安全性
? A不知道 f(x)的逆函数，无法由 y求 x，只能猜
? B若在 A猜测后改变 x,A可以通过 y=f(x)?检查出
来
2010-5-14 20
不经意传输
? 设 A有一个秘密，想以 1/2的概率传递给 B，
即 B有 50％概率收到该秘密
? 协议执行完后,A不知道 B是否收到这个
秘密
2010-5-14 21
基于大数分解的不经意传输协
议
? A想通过不经意传输协议传给 B大数 n的因子
分子
? 如果已知某数在模 n下的两个不同的平方根，
就可以分解 n
1,B随机选一数 x，将发给 A
2,A（掌握 n的分解）计算 x2mod n 的四个平方根
± x,± y,将其中之一发给 B
3,B检查收到的数是否与 ± x 在模 n下同余，如果是，
B没有得到任何新的信息，否则 B掌握了 x2mod n
的两个不同的平方根，从而可以分解 n，而 A确不
知道究竟是哪种情况
第八章 数字签字和密码协议
2010-5-14 2
? 数字签字的基本概念
? 数字签字标准
? 其他签字方案
? 认证协议
? 身份证明技术
? 其他密码协议
2010-5-14 3
身份证明技术
2010-5-14 4
身份证明技术
传统的身份证明：
一般是通过检验, 物, 的有效性来确认
持该物的的身份 。 徽章, 工作证, 信用
卡, 驾驶执照, 身份证, 护照等, 卡上
含有个人照片 (易于换成指纹, 视网膜图
样, 牙齿的 X适用的射像等 )。
信息系统常用方式：
用户名和口令
2010-5-14 5
交互式证明
两方参与
示证者 P(Prover)，知道某一秘密，使 V相信
自己掌握这一秘密；
验证者 V(Verifier)，验证 P掌握秘密；每轮 V
向 P发出一询问,P向 V做应答。 V检查 P是否
每一轮都能正确应答。
2010-5-14 6
交互证明与数学证明的区别
? 数学证明的证明者可自己独立的完成证
明
? 交互证明由 P产生证明,V验证证明的有
效性来实现，双方之间要有通信
? 交互系统应满足
? 完备性：如果 P知道某一秘密,V将接收 P的
证明
? 正确性：如果 P能以一定的概率使 V相信 P的
证明，则 P知道相应的秘密
2010-5-14 7
Fiat-Shamir身份识别方案
参数：
选定一个随机模 m=p× q。 产生随机数 v，
且使 s2=v,即 v为模 m的平方剩余 。 m和
v是公开的, s作为 P的秘密
2010-5-14 8
Fiat-Shamir身份识别方案
(1) P取随机数 r(<m),计算 x= r 2 mod m,送给 V；
(2) V将一随机 bit b送给 P；
(3) 若 b=0,则 P将 r送给 V；若 b=1,则 P将 y=rs送给 V；
(4) 若 b=0,则 V证实 x=r 2 mod m,从而证明 P知道, 若
b=1,则 B证实 xv=y2 mod m,从而证明 A知道 。
这是一次证明, A和 B可将此协议重复 t次, 直到 B相
信 A知道 s为止 。
2010-5-14 9
Fiat-Shamir身份识别方案
? 完备性
? 如果 P和 V遵守协议，且 P知道 s，则应答 rs是应是模 m下 xv的平
方根,V接收 P的证明，所以协议是完备的。
? 正确性
? P不知道 s，他也可取 r，送 x=r2 mod m给 V,V送 b给 P。 P可将
r送出，当 b=0时则 V可通过检验而受骗，当 b=1时，则 V可发
现 P不知 s,B受骗概率为 1/2，但连续 t次受骗的概率将仅为 2-t
? V无法知道 P的秘密，因为 V没有机会产生 (0,1）以外的信息,P
送给 V的消息中仅为 P知道 v的平方根这一事实。
2010-5-14 10
零知识证明
最小泄露证明和零知识证明,
以一种有效的数学方法, 使 V可以检验每
一步成立, 最终确信 P知道其秘密, 而又
能保证不泄露 P所知道的信息 。
2010-5-14 11
零知识证明的基本协议
例 [Quisquater等 1989]。
设 P知道咒语,可
打开 C和 D之间的秘
密门，不知道者
都将走向死胡同中。
A
B
C D
2010-5-14 12
零知识证明的基本协议
(1) V站在 A点；
(2) P进入洞中任一点 C或 D；
(3) 当 P进洞之后, V走到 B点；
(4) V叫 P,(a)从左边出来, 或 (b)从右边出来；
(5) P按要求实现 (以咒语, 即解数学难题帮助 )；
(6) P和 V重复执行 (1)～ (5)共 n次 。
若 A不知咒语，则在 B点，只有 50 %的机会猜中 B的
要求，协议执行 n次，则只有 2-n的机会完全猜中，若
n=16，则若每次均通过 B的检验,B受骗机会仅为 1/65
536
2010-5-14 13
零知识证明的基本协议
哈米尔顿回路
图论中有一个著名问题, 对有 n个顶点的全连
通图 G,若有一条通路可通过且仅通过各顶点
一次, 则称其为哈米尔顿回路 。 Blum[1986] 最
早将其用于零知识证明 。 当 n大时, 要想找到
一条 Hamilton回路, 用计算机做也要好多年,
它是一种单向函数问题 。 若 A知道一条回路,
如何使 B相信他知道, 且不告诉他具体回路？
2010-5-14 14
(1) A将 G进行随机置换, 对其顶点进行移动, 并改变
其标号得到一个新的有限图 H。 因, 故 G上的
Hamilton回路与 H上的 Hamilton回路一一对应 。 已知
G上的 Hamilton回路易于找出 H上的相应回路；
(2)A将 H的复本给 B；
(3) B向 A提出下述问题之一,(a) 出示证明 G和 H同构,
(b) 出示 H上的 Hamilton回路；
(4) A执行下述任务之一,(a) 证明 G和 H同构, 但不出
示 H上的 Hamilton回路, (b) 出示 H上的 Hamilton回
路但不证明 G和 H同构；
(5) A和 B重复执行 (1)～ (4)共 n次 。
HG?
2010-5-14 15
其他密码协议
2010-5-14 16
智力扑克
? A和 B通过网络进行智力扑克比赛，不用第三方做裁
判，发牌者由任一方担任，要求发牌过程满足
1,任一副牌是等可能的
2,发给 A,B的牌没有重复
3,每人知道自己手中的牌，不知道别人的牌
4,比赛结束后，每一方都能发现对方的欺骗行为
? 为满足要求,A,B方需要加密一些信息，比赛结束前，
这些机密算法都是保密的。
2010-5-14 17
智力扑克
? A和 B的加密解密算法记为 EA,EB,DA，
DB，满足 EA(EB(m))= EB( EA(m))
? A,B协商好用以表示 52张牌的 w1,…,w52
2.随机选 5个
EB(wi)
3.另选 5个
EB(wi)，以 EA加
密
以 DA解密
1.洗牌，用 EB对
52个 wi加密
解密，作为发给
自己的牌
以 DB解密
52个 EB（ wi）
5个随机的 EB（ wi）
5个的 EA(EB(wi))
5个的 EA(wi)
完后公开所有加密变换A B
2010-5-14 18
掷硬币协议
? 某些密码协议中要求通信双方在无第三
方协助情况下，产生一个随机序列，因
为 A,B之间不存在信任关系，因此不能
由一方产生在通过网络或电话告诉另一
方
2010-5-14 19
掷硬币协议
? 利用单向函数掷硬币
? A,B都知道某一单向函数 f(x)，但都不知道逆函
数
1,B选择一个随机数 x，求 y＝ f(x)并发给 A
2,A猜测 x的奇偶性，并将结果告诉 B
3,B告诉 A猜测正确不正确，并将 x发给 A
? 安全性
? A不知道 f(x)的逆函数，无法由 y求 x，只能猜
? B若在 A猜测后改变 x,A可以通过 y=f(x)?检查出
来
2010-5-14 20
不经意传输
? 设 A有一个秘密，想以 1/2的概率传递给 B，
即 B有 50％概率收到该秘密
? 协议执行完后,A不知道 B是否收到这个
秘密
2010-5-14 21
基于大数分解的不经意传输协
议
? A想通过不经意传输协议传给 B大数 n的因子
分子
? 如果已知某数在模 n下的两个不同的平方根，
就可以分解 n
1,B随机选一数 x，将发给 A
2,A（掌握 n的分解）计算 x2mod n 的四个平方根
± x,± y,将其中之一发给 B
3,B检查收到的数是否与 ± x 在模 n下同余，如果是，
B没有得到任何新的信息，否则 B掌握了 x2mod n
的两个不同的平方根，从而可以分解 n，而 A确不
知道究竟是哪种情况
