2010-5-14 1
第八章 数字签字和密码协议
2010-5-14 2
? 数字签字的基本概念
? 数字签字标准
? 其他签字方案
? 认证协议
? 身份证明技术
? 其他密码协议
2010-5-14 3
其他签字方案
2010-5-14 4
Schnorr签字体制
? 体制参数
p,q：大素数,q|p-1。 q是大于等于 160 bits的整数，
p是大于等于 512 bits的整数，保证 Zp中求解离散对
数困难；
g,Zp*中元素，且 gq?1 mod p；
x：用户密钥 1<x<q；
y：用户公钥 y?gx mod p。
消息空间 M=Zp*，签字空间 S=Zp*× Zq；密钥空间
K={(p,q,g,x,y),y?gx mod p}
2010-5-14 5
Schnorr签字体制
? 签字过程：令待签消息为 M，对给定的
M做下述运算：
(a) 发用户任选一秘密随机数 k?Zq
(b) 计算
r?gk mod p
s?k＋ xe mod p
式中 e=H(r||M)
(c) 签字 S=Sigk(M)=(e,s)
2010-5-14 6
Schnorr签字体制
验证过程, 收信人收到消息 M及签字 S=(e,s)
后
(a) 计算 r’?gsye mod p 而后计算 H(r’||M)。
(b) 验证 Ver(M,r,s) ? H(r’||M)=e
因为，若 (e||s)是 M的合法签字，则有
gsye?gk-xegxe?gk?r mod p。
2010-5-14 7
Schnorr签字体制
Schnorr签字与 ElGamal签字的不同点：
? 在 ElGamal体制中,g为 Z*p的本原元素；而
在 Schnorr体制中,g为 Zp*中子集 Zq*的本原元
素，它不是 Zp*的本原元素。显然 ElGamal的安
全性要高于 Schnorr。
? Schnorr的签字较短，由 |q|及 |H(M)|决定。
? 在 Schnorr签字中,r=gk mod p可以预先计
算,k与 M无关，因而签字只需一次 mod q乘法
及减法。所需计算量少，速度快。
2010-5-14 8
认证协议
Authentication Protocols
2010-5-14 9
相互认证
? A,B双方在建立共享密钥时需要考虑保
密性和实时性。
? 保密性：会话密钥应以密文传送，因此
双方应事先共享密钥或者使用公钥
? 实时性,防止重放
? 序列号方法
? 时戳
? 询问－应答
2010-5-14 10
序列号方法
? 对交换的每一条消息加上序列号，序列
号正确才被接收
? 要求每个用户分别记录与其他每一用户
交互的序列号，增加用户负担，因而很
少使用
2010-5-14 11
时戳法
? A收到消息中包含时戳，且 A看来这一时
戳充分接近自己的当前时刻,A才认为收
到的消息是新的并接收
? 要求各方时间同步
2010-5-14 12
询问－应答
? 用户 A向 B发出一个一次性随机数作为询
问，如果收到 B发来的应答消息也包含一
正确的一次性随机数,A就认为消息是新
的并接受之 。
2010-5-14 13
各种方法的比较
? 时戳法不适用于面向连接的应用过程
? 要求不同的处理器之间时间同步，所用的协
议必须是容错的以处理网络错误
? 协议中任何一方时钟出现错误失去同步，则
敌手攻击的可能性增加
? 网络中存在延迟，不能期待保持精确同步，
必须允许误差范围
2010-5-14 14
各种方法的比较
? 询问－应答不适合于无连接的应用过程
? 在传输前需要经过询问－应答这一额外的握
手过程，与无连接应用过程的本质特性不符。
? 无连接应用最好使用安全时间服务器提供同
步
2010-5-14 15
Needham－ Schroeder协议
2,
4,
)]||(||||||[ 1 AsKBsK IDKENIDKE BA
KDC
A B
1,IDA|| IDB ||N1
3,]||[
AsK IDKE B
][ 2NE SK
5,)]([
2NfE SK
如果敌手获得了旧会话
密钥，则可以冒充 A重
放 3，并且可回答 5，成
功的欺骗 B
2010-5-14 16
Needham－ Schroeder改进协
议（ 1）
2,
4,
)]||||(||||||[ TIDKETIDKE AsKBsK BA
KDC
A B
1,IDA|| IDB
3,]||||[ TIDKE
AsK B
][ 1NE SK
5,)]([
1NfE SK
以时戳替代随机数，
用以向 A,B保证 Ks
的新鲜性
|Clock－ T|<⊿ t1+⊿ t2
Clock:本地时钟
⊿ t1：本地时钟与 KDC
时钟误差估计值
⊿ t2,网络延迟时间
要求各方时钟同步
如果发方时钟超前 B方时钟，可能
导致等待重放攻击
2010-5-14 17
Needham－ Schroeder改进协
议（ 2）
KDC
A B
3,
1,AA NID ||
4,][||]||||[ BKBSAK NETKIDE
SB
2,]||||[||||
BAAKBB TNIDENID B
BBSAKBSABK NTKIDETKNIDE BA ||]||||[||]||||||[
会话密钥的
截止时间
2010-5-14 18
Needham－ Schroeder改进协
议（ 2）
A B
1.
'],||||[ ABSAK NTKIDE
B
2.
][,'' AKB NEN S
3.
][ 'BK NE S
有效期内可不通过 KDC直接认证
2010-5-14 19
公钥加密体制
AS
A B
1,IDA|| IDB
2,]||||[||]||||[ TPKIDETPKIDE
BBSKAASK ASAS
3,]]||[[||]||||[||]||||[ TKEETPKIDETPKIDE
SSKPKBBSKAASK ABASAS
时戳防止重放，要
求时钟同步
2010-5-14 20
公钥加密体制
AS
A B
2,]||[
BBSK PKIDE AS
1,IDA|| IDB
3,]||[
AAPK IDNE B
4,][|||| APKAB NEIDID
AS
6
]||]||||[[ BBSASKPK NIDKNEE ASA
7 ][
BK NE S
2010-5-14 21
单向认证
? 不需要双方同时在线（电子邮件）
? 邮件接收者希望认证邮件的来源以防假
冒
? 分为单钥加密方法和公钥加密方法
2010-5-14 22
单钥加密
2,)]||(||||||[
1 AsKBsK IDKENIDKE BA
KDC
A B
1,IDA|| IDB ||N1
3,][]||[ MEIDKE
SB KAsK
不要求 B同时在线，保
证只有 B能解读消息，
提供对 A的认证。不能
防止重放攻击。
2010-5-14 23
公钥加密
A B][||][ MEKE sB KsPK
对发送消息提供保密性
对发送消息提供认证性
A B
]||||[||)]([|| AASKSK PKIDTEMHEM ASA
对发送消息提供保密和认证性
A B
]||||[) ] ]([||[ AASKSKPK PKIDTEMHEME ASAB
A的证书
第八章 数字签字和密码协议
2010-5-14 2
? 数字签字的基本概念
? 数字签字标准
? 其他签字方案
? 认证协议
? 身份证明技术
? 其他密码协议
2010-5-14 3
其他签字方案
2010-5-14 4
Schnorr签字体制
? 体制参数
p,q：大素数,q|p-1。 q是大于等于 160 bits的整数，
p是大于等于 512 bits的整数，保证 Zp中求解离散对
数困难；
g,Zp*中元素，且 gq?1 mod p；
x：用户密钥 1<x<q；
y：用户公钥 y?gx mod p。
消息空间 M=Zp*，签字空间 S=Zp*× Zq；密钥空间
K={(p,q,g,x,y),y?gx mod p}
2010-5-14 5
Schnorr签字体制
? 签字过程：令待签消息为 M，对给定的
M做下述运算：
(a) 发用户任选一秘密随机数 k?Zq
(b) 计算
r?gk mod p
s?k＋ xe mod p
式中 e=H(r||M)
(c) 签字 S=Sigk(M)=(e,s)
2010-5-14 6
Schnorr签字体制
验证过程, 收信人收到消息 M及签字 S=(e,s)
后
(a) 计算 r’?gsye mod p 而后计算 H(r’||M)。
(b) 验证 Ver(M,r,s) ? H(r’||M)=e
因为，若 (e||s)是 M的合法签字，则有
gsye?gk-xegxe?gk?r mod p。
2010-5-14 7
Schnorr签字体制
Schnorr签字与 ElGamal签字的不同点：
? 在 ElGamal体制中,g为 Z*p的本原元素；而
在 Schnorr体制中,g为 Zp*中子集 Zq*的本原元
素，它不是 Zp*的本原元素。显然 ElGamal的安
全性要高于 Schnorr。
? Schnorr的签字较短，由 |q|及 |H(M)|决定。
? 在 Schnorr签字中,r=gk mod p可以预先计
算,k与 M无关，因而签字只需一次 mod q乘法
及减法。所需计算量少，速度快。
2010-5-14 8
认证协议
Authentication Protocols
2010-5-14 9
相互认证
? A,B双方在建立共享密钥时需要考虑保
密性和实时性。
? 保密性：会话密钥应以密文传送，因此
双方应事先共享密钥或者使用公钥
? 实时性,防止重放
? 序列号方法
? 时戳
? 询问－应答
2010-5-14 10
序列号方法
? 对交换的每一条消息加上序列号，序列
号正确才被接收
? 要求每个用户分别记录与其他每一用户
交互的序列号，增加用户负担，因而很
少使用
2010-5-14 11
时戳法
? A收到消息中包含时戳，且 A看来这一时
戳充分接近自己的当前时刻,A才认为收
到的消息是新的并接收
? 要求各方时间同步
2010-5-14 12
询问－应答
? 用户 A向 B发出一个一次性随机数作为询
问，如果收到 B发来的应答消息也包含一
正确的一次性随机数,A就认为消息是新
的并接受之 。
2010-5-14 13
各种方法的比较
? 时戳法不适用于面向连接的应用过程
? 要求不同的处理器之间时间同步，所用的协
议必须是容错的以处理网络错误
? 协议中任何一方时钟出现错误失去同步，则
敌手攻击的可能性增加
? 网络中存在延迟，不能期待保持精确同步，
必须允许误差范围
2010-5-14 14
各种方法的比较
? 询问－应答不适合于无连接的应用过程
? 在传输前需要经过询问－应答这一额外的握
手过程，与无连接应用过程的本质特性不符。
? 无连接应用最好使用安全时间服务器提供同
步
2010-5-14 15
Needham－ Schroeder协议
2,
4,
)]||(||||||[ 1 AsKBsK IDKENIDKE BA
KDC
A B
1,IDA|| IDB ||N1
3,]||[
AsK IDKE B
][ 2NE SK
5,)]([
2NfE SK
如果敌手获得了旧会话
密钥，则可以冒充 A重
放 3，并且可回答 5，成
功的欺骗 B
2010-5-14 16
Needham－ Schroeder改进协
议（ 1）
2,
4,
)]||||(||||||[ TIDKETIDKE AsKBsK BA
KDC
A B
1,IDA|| IDB
3,]||||[ TIDKE
AsK B
][ 1NE SK
5,)]([
1NfE SK
以时戳替代随机数，
用以向 A,B保证 Ks
的新鲜性
|Clock－ T|<⊿ t1+⊿ t2
Clock:本地时钟
⊿ t1：本地时钟与 KDC
时钟误差估计值
⊿ t2,网络延迟时间
要求各方时钟同步
如果发方时钟超前 B方时钟，可能
导致等待重放攻击
2010-5-14 17
Needham－ Schroeder改进协
议（ 2）
KDC
A B
3,
1,AA NID ||
4,][||]||||[ BKBSAK NETKIDE
SB
2,]||||[||||
BAAKBB TNIDENID B
BBSAKBSABK NTKIDETKNIDE BA ||]||||[||]||||||[
会话密钥的
截止时间
2010-5-14 18
Needham－ Schroeder改进协
议（ 2）
A B
1.
'],||||[ ABSAK NTKIDE
B
2.
][,'' AKB NEN S
3.
][ 'BK NE S
有效期内可不通过 KDC直接认证
2010-5-14 19
公钥加密体制
AS
A B
1,IDA|| IDB
2,]||||[||]||||[ TPKIDETPKIDE
BBSKAASK ASAS
3,]]||[[||]||||[||]||||[ TKEETPKIDETPKIDE
SSKPKBBSKAASK ABASAS
时戳防止重放，要
求时钟同步
2010-5-14 20
公钥加密体制
AS
A B
2,]||[
BBSK PKIDE AS
1,IDA|| IDB
3,]||[
AAPK IDNE B
4,][|||| APKAB NEIDID
AS
6
]||]||||[[ BBSASKPK NIDKNEE ASA
7 ][
BK NE S
2010-5-14 21
单向认证
? 不需要双方同时在线（电子邮件）
? 邮件接收者希望认证邮件的来源以防假
冒
? 分为单钥加密方法和公钥加密方法
2010-5-14 22
单钥加密
2,)]||(||||||[
1 AsKBsK IDKENIDKE BA
KDC
A B
1,IDA|| IDB ||N1
3,][]||[ MEIDKE
SB KAsK
不要求 B同时在线，保
证只有 B能解读消息，
提供对 A的认证。不能
防止重放攻击。
2010-5-14 23
公钥加密
A B][||][ MEKE sB KsPK
对发送消息提供保密性
对发送消息提供认证性
A B
]||||[||)]([|| AASKSK PKIDTEMHEM ASA
对发送消息提供保密和认证性
A B
]||||[) ] ]([||[ AASKSKPK PKIDTEMHEME ASAB
A的证书
