2010-5-14 1
第八章 数字签字和密码协议
2010-5-14 2
? 数字签字的基本概念
? 数字签字标准
? 其他签字方案
? 认证协议
? 身份证明技术
? 其他密码协议
2010-5-14 3
数字签字的基本概念
2010-5-14 4
数字签字的执行方式
? 直接方式
数字签字的执行过程只有通信的双方参
与，并假定双方有共享的秘密密钥或者
接收一方知道发送方的公开钥。
? 缺点：方案的有效性取决于发方密钥的
安全性。
? 发方可声称秘密钥丢失或被窃
2010-5-14 5
数字签字的执行方式
? 具有仲裁方式的数字签字
1,发方 X对发往收方 Y的消息签字
2,将消息和签字先发往仲裁者 A
3,A对消息和签字验证完后，再连同一个表示
已通过验证的指令一起发给 Y.
2010-5-14 6
数字签字的执行方式－具有仲
裁方式的数字签字
? 例 1：
1,X?A:M||
2,A?Y:
)](||[ MHIDE XK XA
]||)(||[||||[ TMHIDEMIDE XKXK XAAY
E：单钥加密算法
KXA,KAY:A与 X和 Y的共享密钥
M：消息
T：时戳
IDX,X的身份
H(M),M的杂凑值
A必须获得 X和 Y的高度信任
X相信 A不会泄漏 KXA，并且不会 X的签字
Y相信 A只有对
中的杂凑值及 X签字验证无误后才将其发给 Y
X,Y都相信 A可公正的解决争议
]||)(||[||||[ TMHIDEMIDE XKXK XAAY
2010-5-14 7
数字签字的执行方式－具有仲
裁方式的数字签字
? 例 2
1,X?A:IDX||
2,A?Y,]||) ) ]((||[||][||[ TMEHIDEMEIDE XYXAXYAY KXKKXK
) ) ]((||[||][ MEHIDEME XYXAXY KXKK
X对 M的签字
X和 Y的共享密钥
此方案提供了对 M的保密性
和前一方案相同，仲裁者可和发方共谋否认发方曾发过
的消息，也可和收方共谋产生发方的签字
2010-5-14 8
数字签字的执行方式－具有仲
裁方式的数字签字
? 例 3
]||]][[||[:.2
] ] ][[||[||:.1
TMEEIDEYA
MEEIDEIDAX
XYA
XYX
SKPKXSK
SKPKXSKX
?
?
X的私钥 Y的公钥
2010-5-14 9
数字签名标准
Digital Signature Standard (DSS)
2010-5-14 10
概况
? 由 NIST1991年公布
? 1993年公布修改版
? 美国联邦信息处理标准 FIPS PUB 186
? 签名长度 320bit
? 只能用于数字签字，不能用于加密
2010-5-14 11
DSS的基本方式
M ||
H E
SKA
M
)]([ MHE ASK
H
D
PKA 比较
M ||
H
SKA
M
s
H
PKG
比较
Ver
PKG
K
随机数
r
PKA
Sig
RSA签字
DSS签字
全局公开钥
2010-5-14 12
数字签字算法 DSA
? 在 Elgamal和 Schnorr两个方案基础上设计的
? 算法描述,
(a) 全局公钥 ( p,q,g )
p：是 2L-1 < p < 2L中的大素数,512 ? L ? 1024，按
64 bits递增；
q,(p－ 1)的素因子，且 2159 < q < 2160，即字长 160
bits；
g,= hp-1 mod p，且 1< h < (p－ 1)，使 h(p-1)/q mod
p >1。
(b) 用户秘密钥 x,x为在 0<x<q内的随机数。
(c) 用户公钥 y,=g x mod p。
(d) 用户每个消息用的秘密随机数 k：在 0<k<q内的
2010-5-14 13
数字签字算法 DSA
(e) 签字过程：对消息 M?M=Zp*，其签字为 S=Sigk(M,k)=(r,
s),S?S=Zq× Zq,
r?(gk mod p) mod q
s?[k-1 (h(M)＋ xr)] mod q
(f) 验证过程：计算
w=s -1 mod q ; u1 =[H(M)w] mod q ;
u2=rw mod q ; v=[(gu1yu2) mod p] mod q。
Ver(M,r,s)=真 ? v=r
rqpg
qpg
qpggv
k
sxrMH
x r wwMH
??
?
?
??
m o d)m o d(
m o d]m o d[
m o d]m o d)[(
1])([
)(
2010-5-14 14
其他签字方案
2010-5-14 15
离散对数签字体制
? 体制参数
p：大素数
q,(p－ 1)或 p-1的大素因子
g,g∈ RZp*,gq=1 mod p。
x：用户秘密钥,x为在 1<x<q内的随机数。
y：用户公钥 g x= mod p。
2010-5-14 16
离散对数签字体制
? 签字产生过程
1,计算 m的杂凑值
2,选择随机数 k:1<k<q，计算 r＝ gk mod p
3,从签字方程 ak=b+cx mod q中解出 s.（ r,s)为数
字签字 。a b c
± r
± rH(m)
± rH(m)
± H(m)r
± H(m)s
± s
± s
± H(m)s
± rs
± rs
H(m)
1
1
1
1
2010-5-14 17
离散对数签字体制
? 签字验证过程
)( m o d)),,(,( pygrT u r emsryV e r cba ???
2010-5-14 18
Elgamal签字体制
? 离散对数签字体制的特例
? 体制参数
p：一个大素数；
g：是 Zp中乘群 Zp*的一个生成元或本原元素；
M：消息空间，为 Zp*；
S：签字空间，为 Zp*× Zp－ 1；
x：用户秘密钥 x?Zp*；
y,用户公钥, y?gx mod p
p,g,y为公钥,x为秘密钥。
2010-5-14 19
Elgamal签字体制
? 签字过程：给定消息 M，进行下述工作。
(a) 选择秘密随机数 k?Zp*；
(b) 计算 H(M)；
(c) 计算
r=gk mod p
s=(H(M)－ xr)k--1 mod (p－ 1)
(r,s)作为签字,
2010-5-14 20
Elgamal签字体制
? 验证过程：
收信人收到 M,(r,s)，先计算 H(M)，并按下
式验证
Verk(H(M),r,s)=真 ? yrrs?gH(M) mod p
因为 yrrs?grxgsk?g(rx+sk) mod p，
(rx+sk)?H(M) mod(p－ 1)
故有 y rr s?gH(M) mod p
第八章 数字签字和密码协议
2010-5-14 2
? 数字签字的基本概念
? 数字签字标准
? 其他签字方案
? 认证协议
? 身份证明技术
? 其他密码协议
2010-5-14 3
数字签字的基本概念
2010-5-14 4
数字签字的执行方式
? 直接方式
数字签字的执行过程只有通信的双方参
与，并假定双方有共享的秘密密钥或者
接收一方知道发送方的公开钥。
? 缺点：方案的有效性取决于发方密钥的
安全性。
? 发方可声称秘密钥丢失或被窃
2010-5-14 5
数字签字的执行方式
? 具有仲裁方式的数字签字
1,发方 X对发往收方 Y的消息签字
2,将消息和签字先发往仲裁者 A
3,A对消息和签字验证完后，再连同一个表示
已通过验证的指令一起发给 Y.
2010-5-14 6
数字签字的执行方式－具有仲
裁方式的数字签字
? 例 1：
1,X?A:M||
2,A?Y:
)](||[ MHIDE XK XA
]||)(||[||||[ TMHIDEMIDE XKXK XAAY
E：单钥加密算法
KXA,KAY:A与 X和 Y的共享密钥
M：消息
T：时戳
IDX,X的身份
H(M),M的杂凑值
A必须获得 X和 Y的高度信任
X相信 A不会泄漏 KXA，并且不会 X的签字
Y相信 A只有对
中的杂凑值及 X签字验证无误后才将其发给 Y
X,Y都相信 A可公正的解决争议
]||)(||[||||[ TMHIDEMIDE XKXK XAAY
2010-5-14 7
数字签字的执行方式－具有仲
裁方式的数字签字
? 例 2
1,X?A:IDX||
2,A?Y,]||) ) ]((||[||][||[ TMEHIDEMEIDE XYXAXYAY KXKKXK
) ) ]((||[||][ MEHIDEME XYXAXY KXKK
X对 M的签字
X和 Y的共享密钥
此方案提供了对 M的保密性
和前一方案相同，仲裁者可和发方共谋否认发方曾发过
的消息，也可和收方共谋产生发方的签字
2010-5-14 8
数字签字的执行方式－具有仲
裁方式的数字签字
? 例 3
]||]][[||[:.2
] ] ][[||[||:.1
TMEEIDEYA
MEEIDEIDAX
XYA
XYX
SKPKXSK
SKPKXSKX
?
?
X的私钥 Y的公钥
2010-5-14 9
数字签名标准
Digital Signature Standard (DSS)
2010-5-14 10
概况
? 由 NIST1991年公布
? 1993年公布修改版
? 美国联邦信息处理标准 FIPS PUB 186
? 签名长度 320bit
? 只能用于数字签字，不能用于加密
2010-5-14 11
DSS的基本方式
M ||
H E
SKA
M
)]([ MHE ASK
H
D
PKA 比较
M ||
H
SKA
M
s
H
PKG
比较
Ver
PKG
K
随机数
r
PKA
Sig
RSA签字
DSS签字
全局公开钥
2010-5-14 12
数字签字算法 DSA
? 在 Elgamal和 Schnorr两个方案基础上设计的
? 算法描述,
(a) 全局公钥 ( p,q,g )
p：是 2L-1 < p < 2L中的大素数,512 ? L ? 1024，按
64 bits递增；
q,(p－ 1)的素因子，且 2159 < q < 2160，即字长 160
bits；
g,= hp-1 mod p，且 1< h < (p－ 1)，使 h(p-1)/q mod
p >1。
(b) 用户秘密钥 x,x为在 0<x<q内的随机数。
(c) 用户公钥 y,=g x mod p。
(d) 用户每个消息用的秘密随机数 k：在 0<k<q内的
2010-5-14 13
数字签字算法 DSA
(e) 签字过程：对消息 M?M=Zp*，其签字为 S=Sigk(M,k)=(r,
s),S?S=Zq× Zq,
r?(gk mod p) mod q
s?[k-1 (h(M)＋ xr)] mod q
(f) 验证过程：计算
w=s -1 mod q ; u1 =[H(M)w] mod q ;
u2=rw mod q ; v=[(gu1yu2) mod p] mod q。
Ver(M,r,s)=真 ? v=r
rqpg
qpg
qpggv
k
sxrMH
x r wwMH
??
?
?
??
m o d)m o d(
m o d]m o d[
m o d]m o d)[(
1])([
)(
2010-5-14 14
其他签字方案
2010-5-14 15
离散对数签字体制
? 体制参数
p：大素数
q,(p－ 1)或 p-1的大素因子
g,g∈ RZp*,gq=1 mod p。
x：用户秘密钥,x为在 1<x<q内的随机数。
y：用户公钥 g x= mod p。
2010-5-14 16
离散对数签字体制
? 签字产生过程
1,计算 m的杂凑值
2,选择随机数 k:1<k<q，计算 r＝ gk mod p
3,从签字方程 ak=b+cx mod q中解出 s.（ r,s)为数
字签字 。a b c
± r
± rH(m)
± rH(m)
± H(m)r
± H(m)s
± s
± s
± H(m)s
± rs
± rs
H(m)
1
1
1
1
2010-5-14 17
离散对数签字体制
? 签字验证过程
)( m o d)),,(,( pygrT u r emsryV e r cba ???
2010-5-14 18
Elgamal签字体制
? 离散对数签字体制的特例
? 体制参数
p：一个大素数；
g：是 Zp中乘群 Zp*的一个生成元或本原元素；
M：消息空间，为 Zp*；
S：签字空间，为 Zp*× Zp－ 1；
x：用户秘密钥 x?Zp*；
y,用户公钥, y?gx mod p
p,g,y为公钥,x为秘密钥。
2010-5-14 19
Elgamal签字体制
? 签字过程：给定消息 M，进行下述工作。
(a) 选择秘密随机数 k?Zp*；
(b) 计算 H(M)；
(c) 计算
r=gk mod p
s=(H(M)－ xr)k--1 mod (p－ 1)
(r,s)作为签字,
2010-5-14 20
Elgamal签字体制
? 验证过程：
收信人收到 M,(r,s)，先计算 H(M)，并按下
式验证
Verk(H(M),r,s)=真 ? yrrs?gH(M) mod p
因为 yrrs?grxgsk?g(rx+sk) mod p，
(rx+sk)?H(M) mod(p－ 1)
故有 y rr s?gH(M) mod p
