第 10章 数字签名
? 数字签名特点,
?签名不可伪造;
?签名是可靠的;
?签名不可重用;
?签名不可改变;
?签名不可抵赖。
? 定义 10.0.1:一个签名方案是一个 5元组( M,A,K,S,V),
满足如下的条件,
( 1) M是一个可能消息的有限集;
( 2) A是一个可能签名的有限集;
( 3)密钥空间 K是一个可能密钥的有限集;
( 4)对每一个 k=( k1,k2) K,都对应一个签名算法 Sig
S和验证算法 Ver V。每一个 Sig,M- >A和 Ver,M- >
A{TRUE,FALSE}是一个对每一个消息 x M和每一个签名 y
A满足下列方程的函数,
Ver(x,y)=
( 5)对每一个 k,函数 Sig和 Ver都是多项式时间可计算的
函数。 Ver是一个公开函数,k1称作公钥;而 Sig是一个秘
密函数,k2称作私钥,由用户秘密地保存。
2K
? ?
1K
?
? ?
?
?? ?
?
)(y
)(
2
2
xS igF A L S E
xS igyT R U E
K
K


10.1基于 RSA和离散对数的签名体制
10.1.1RSA签名方案
? 系统参数:设 n=pq,且 p和 q是两个大素数, 则
M=A=Zn,定义 К={( n,d,p,q,e) }这里 e和 d 满足 ed
≡ 1(modΦ(n))( Φ是欧拉函数 )
公开密钥 n,e,
私有密钥 p,q,d,
签名算法, Sigk2 (x)= y = xd mod n
验证算法,Ver(x,y)=TRUE
ye = x (mod n),(x,y) ∈ Zn× Zn,
? 带加密的签名
?先签名再加密
?先加密再签名
10.1.2 EIGAMAL签名方案及其一般化的模型
系统参数:设 p是一大素数, g是 Z的一个生成元,定义 К={( p,g,y,x),y= gx mod p}其中 x
∈ Z。
公开密钥 y,p,g
私有密钥 x
签名算法:对于 К=( p,g,y,x), 随机数 k∈ Z和待
签消息 m,定义 Sig(x,k)=(r,s),这里的 r=gkmod p;
s=(m-xr)k-1 mod (p-1),
( r,s) 即为生成的签名 。
验证算法,Ver(m,r,s)=TRUE
yrrs=gmmod p
? EIGAMAL签名方案的安全性分析
( 1)本方案是基于离散对数问题的。
( 2)对于随机数 k应注意两方面的情况,首先,k不能泄露,
其次,随机数不能重复使用。
( 3)伪造签名攻击。
? 一般 ELGAMAL签名方案
( 1)系统初始化
( 2)签名方程
Ax=Bk+Cmod(p-1)
( 3)验证方程
yA=rBgC mod p
10.1.3 DSS
系统参数:设 p是一 512位到 1024位的大素数, 它满足 Zp中的离散对数问题是难解决的, q是 160位长的素数, 且 q|p-1,
g∈ Zp是 Zp域中的 q次单位根 。 定义 К={( p,q,g,y,x), y=gx
mod p}
公开密钥,p,q,g,y
私有密钥,x
签名算法:对于随机数 k∈ Z和待签消息 m∈ Z,计算 r= (gk
mod p) mod q
s=(h(m)+xr)k-1mod q,消息对 ( r,s) 即为生成的签名 。
验证算法,Ver(m,r,s)=TRUE
(ye2 ge1 mod p)modq=r
其中 e1=h(m)s-1modq,e2=r s-1 modq
10.1.4Lamport签名方案
系统参数:设 k是一个正整数, P={0,1}k,假设f:Y
→ Z是一单向 Hash函数, A=Yk,随机选择
yij∈ Y这里 1≦ i ≦ k,j=0,1且 zij=f(yij),1 ≦ i ≦ k,j=0,1,
私有密钥, yij,1≦ i ≦ k,j=0,1
公开密钥, zij,1 ≦ i ≦ k,j=0,1
签名算法,Sig (x1,…,xk)=(y1x1,…,ykxk)
验证算法,
Ver( x1,…,xk,a1,…,ak)=TRUE
f(ai)=zixi,1 ≦ i ≦ k
10.1.5不可否认签名方案
系统参数:设 p=2q+1是一个素数, 这里的 q是素数且 Zp中的离散对数问题是难解决的, α是 Z域中的 q次单位根, 1 ≦ a ≦ q-1,设 G表示阶
为 q的 Z的乘法
子群,M=A=G,且定义
К={( p,α,β,a), β = αa mod p }
私有密钥 a,
公开密钥 p,α,β 。
签名算法:设待签消息为 x∈ G,y=Sig(x)=xamodp,这里 y ∈ G。
验证协议:1,A随机选取 e1, e2 ∈ Z。
2,A计算 c=ye1 β e2 mod p且把它传给 B,
3,B计算 d=c modp,并将其传给 A,
4,A接受 y,并将它作为一有效签名当且仅当
d=xe1 α e1mod p
qa mod1?
? 否认协议如下,
1,A随机选取 e1, e2∈ Z,
2,A计算 c=ye1 βe2 mod p且把它传给 B
3,B计算 d=c modp,并将其传给 A,
4,A证实 d≠xe1αe2modp,
5,A随机选取 f1,f2 ∈ Z,
6,A计算 c’= yf1 βf2 modp且把它传给 B
7,B计算 d’=c’ modp,并将其传给 A
8,A验证 d’≠xf1αf2modp,
9,A推出 y是伪造的当且仅当
(d α-e2)f1=( d’ α-f2 )e1mod p
qa mod1?
qa mod1?
? 不可否认签名方案的安全性分析
? 定理 10.1.1:当 y≠xamod p时,则 A接受 y
作为 x的真正签名的概率为 1/q。
? 定理 10.1.2:若 y≠xamod p 且 A和 B都遵守
否认协议,则 (dα-e2)f1=(d’α-f2 )e1mod p
? 定理 10.1.3,若 y=xamod p且 A遵守否认协
议,又 d≠xe1αe2mod p,d’≠xf1αf2modp
则 (dα-e2)f1=(d’α-f2 )e1mod p成立的概率为 1-
1/q 。
10.1.6故障停止式签名方案
? 系统参数
? 签名算法,对于 k={( γ1,γ2,a1,a2,b1,b2) }和待
签消息 x ∈ Z,定义 Sig(x)=(y1,y2),
y1=a1+xb1 modq y2=a2+xb2 modq 消息对
(y1,y2)即为生成的签名。
? 验证算法,对 y=(y1,y2) ∈ Z× Z,我们有
Ver( x,y)=TRUE
γ1γ2x=αy1βy2modp
? 伪造证明算法
10.1.7 Schnorr数字签名方案
? 系统参数
? 签名算法 对于待签消息 m∈ Z,选择随机数
k(1<k<q),计算 r=gkmodp,e=h(r,m),从签名方程
s=k-xe modq中解出 s,消息对( e,s)即为生成的
签名。
? 验证算法 收方在收到消息 m和数字签名 (e,s)后
计算 r’=gsyemodp则
Ver(m,(e,s))=TRUE
h(r’,m)=e
? Schnorr数字签名方案的安全性分析
( 1) EIGAMAL系统中 g为 Zp中的本原元,而于 Schnorr系统
中则不是。从安全的角度来看,EIGAMAL安全性较高,这
是因为本原元的阶为 p-1,而 Schnorr系统中 g的的阶为
q(>2160),在此阶下,基于离散对数问题的体制是否安全
有待进一步研究。
( 2) Schnorr系统的签名文较短,e的长度由函数 h决定。 s
的长度小于 |q|。若 h的输出长度为 128位,|q|为 160位,则
其签名长度为 288位,比 EIGAMAL系统的 1024位小,
( 3) Schnorr首先提出 r= gkmod p可以事先计算,由于 k是
与 m无关的随机数,故 Schnorr系统在签名中只需一次乘
法及减法 (模运算 ),比 EIGAMAL系统快很多。因此,
Schnorr数字签名方案特别适合于智能卡的应用。
10.2 群签名
? 一般说来,群签名方案由组、组成员(签名者)、
签名接受者(签名验证者)和权威 (Authority)或
GC(Group Center)组成,具有如下特点,
(1)只有组中的合法用户才能对消息签名,并产生群
签名;
( 2)签名的接收者能验证群签名的有效性;
( 3)签名的接收者不能辨认是谁的签名;
(4)一旦发生争论,群签名的权威或组中所有成员的
联合可以辨别出签名者。
K-P-W可变群签名方案
系统参数; 选择 n=pq=(2fp’+1)( 2fq’+1),这里的 p,q,f,p’和 q’为相
异的大素数, g的阶为 f,γ 和 d为整数, 且 γd=1modφ(n),gcd(γ,
φ(n))=1,h为安全的 hash函数, IDG为 GC的身份消息 。
签名组的公钥,(n,γ,g,f,h,IDG),
签名组的私钥,(d,p’,q’)。
设 IDA为组成员 A的身份消息, A随机选取 sA∈ (0,f)并将消息 (IDA,gsA
mod n)发送给 GC。 GC计算 xA=(IDG’)-dmod n,并将 xA秘密地传送给
成员 A。 则 A的私有密钥,(xA,sA)。
签名算法:对于待签消息 m:组中成员 A随机选择整数 (r1,r2),计算
V= gr1r2γ mod n,e=h(V,m) 则群签名为 ( e,z1,z2),
其中 z1=r1+sAe(mod f),z2=r2xAe mod n
签名验证算法,e=h(V’,m),这里的 V’= (IDG)egz1z2γ(mod n),
身份验证算法,gz1=(Vr2-γ)(gsA)e mod n, 其中 r2=z2xA-e(mod n)
? K-P-W可变群签名方案的安全性分析
( 1)当 p’和 q’具有相同的比特位时,攻击者可以采用对参数
n进行因子分解的方法。分解 n=pq=(2fp’+1)( 2fq’+1)只需
要 2 次整数乘法,这里的 │x│为 x的比特位数。
( 2)在组中成员诚实的情况下,虽说权威能辨别出签名者
签名。可是当组中的成员伪造或共谋伪造时,仍能生成有
效的签名。设组中成员 A随机选取整数 a和 b,计算 sA=ab
mod f 和 sA’= sA+ b mod f,将 (sA,sA’)作为 A的私钥,公钥
为 yA= gsAmod n,,yA’= gsA’ mod n,从 GC处秘密地收到私
钥 xA和 xA’,则有 gbd=xA(xA’)-1 mod n,IDG-d= xA( gbd)a
mod n,于是可以得到 gd=( gbd)b-1mod n。对于任意的 sA,
由于 A知道 IDG-d 和 gd,故可算出私钥( xA,sA),对任意的
消息,都可以产生有效的群签名,而权威无法辨认签名用
户。如果组中两成员共谋,利用上述方法同样可产生有效
的群签名,而权威无法辨认签名用户。
2' )( fp?
10.3 多重数字签名方案
? 广播多重数字签名方案 ( Broadcasting
Multisignature)





U
U
U





签名
验证

? 有序多重数字签名方案 (Sequential
Multisignature)
? EIGAMAL有序多重数字签名方案
( 1)系统初始化
( 2)签名算法
签名者 Ui (i=2,…,n) 收到上一签名者发送的待签消息( m,
( si-1,ri-1))( s=0)后做如下的工作:首先随机选取 ki∈
[1,p-1],计算 ri=gkimodp,si=si-1+m’xi-rikimodφ(p) 这里的
m’=h(m),最后将签名消息 (m,(si,ri))发给下一个签名者
Ui+1,并将 ri发给 Ui以后的签名者和签名验证者。
( 3)验证算法
验证包括两方面的要求:签名者 Ui (i=2,…,n) 要对
U1,U2,…Ui -1的签名的有效性进行验证;验证者 Uv要对所
有签名者 U1,U2,…Un 的签名进行验证,
对于 Ui (i=2,…,n) 通过验证等式 g = modp是否成
立,来判断 U1,U2,…Ui -1的签名是否有效。若等式成立则
有效,反之无效。
对于验证者 Uv通过验证等式是否成立来判断 U1,U2,…Un
的签名是否有效。若等式成立则有效,反之无效。
???11ij rj jr ??
?
1
1
'i
j
mjy
? HARN广播多重数字签名方案
( 1)系统初始化
( 2)单用户签名的产生
( 3)单用户签名的验证
( 4)多重签名的产生
( 5)多重签名的验证
10.4代理数字签名体制
? 定义 10.4.1:设 A,B是某个数字签名体制( M,A,K,S,V)的
两个用户,他们的私钥和公钥对分别是( x,y),( x,y),如
果满足下列条件,
? ( 1) A利用它的秘密密钥 x计算出一个数,并将秘密交给
B;
? ( 2)任何人(包括 B)在试图求出 x时,不会对他有任何
帮助;
? ( 3) B可以用和 x生成一新的签名密钥;
? ( 4)存在一个公开的验证算法 Ver,使得对任何 s和 mM
都有 Ver(y,s,m)=TRUEs=Sig(,m);
? ( 5)任何人在试图求出 x,x,或时,任何数字签名 Sig(,m)
都不会对他产生帮助。
? 代理签名体制具有下面的特定的安全特性,
? 可区别性。任何人都可区别代理签名和正常的签名。
? 不可伪造性。只有原始签名者和指定的代理签名者能够产
生有效的代理签名。
? 代理签名者的不符合性。代理签名者必须创建一个能检测
到是代理签名的有效代理签名。
? 可验证性。从代理签名中,验证者能够相信原始的签名者
认同了这份签名消息。
? 可识别性。原始签名者能够从代理签名中识别代理签名者
的身份。
? 不可抵赖性。代理签名者不能否认他创立的且被认可的代
理签名。
? 可注销性。如果原始签名者希望代理签名人只能在一定时
间内拥有生成代理签名的能力,那么必须能让代理签名人
的代理签名密钥在指定时间内失去作用。
系统参数:( M,A,K,S,V)是一基于离散对数问题的签名体制,
其参数 p,q,g满足
p是一大素数,它满足 Z中的离散对数问题是难解决的。
q是大素数, 且 q,
g Z是 Z域中的 q次单位根 。
用户 A和 B的私钥和公钥对分别是( x,y),( x,y),这里的
y=gmodp,y=gmodp。
委托过程,A随机选择一整数 k Z,计算 K= gmodp,=
x+kKmodq,将(,K)秘密传给 B.B收到消息后验证等式
g=yKmodp是否成立。
代理签名的生成算法:对于待签消息 m,B生成普通的数
字签名 s=Sig(,m),将( s,K)作为他代表 A对消息 m的数
字签名,即代理签名。
代理签名的验证算法:当代理签名的接收者收到了
消息 m和代理签名( s,K)后,计算 v=yKmodp;
验证 Ver(y,( s,K),m) =TRUE Ver(v,s,m)= TRUE,
? 安全性分析
? ( 1)基本的不可伪造性,在这个代理签名体制中,B难以根据所得到的(,K)
计算出 x,从而不能伪造 A的普通数字签名。由此说明任何其他的攻击者都难
以伪造 A的普通数字签名,
? ( 2)代理签名的不可伪造性。由于 A和 B都知道(,K),所以,A和 B都能
生成代理签名。但是除了 A和 B以外,其他任何人都难以伪造一个有效的代理
签名。
? ( 3)代理签名的可区分性。代理签名( s,K)有两部分组成,一部分是普通
数字签名 s,另一部分是某个数 K.由于代理签名比普通签名多出一部分,所以,
容易将代理签名与普通的数字签名区分开。假如除了 B以外,还有另外一个代
理签名人 C,A在委托过程中发送给 C的消息是(,K),这里的 K=gmodp,k,于是
C生成的代理签名体制的形式一定为( s,K),可以看出,由于 k,所以 K,从而将
B和 C生成的代理签名区分开。
? ( 4)不可抵赖性。由于任何人都不能伪造 A的普通数字签名,所以 A不能否
认他的一个有效的普通签名。由于除了 A和 B外,任何人都不能伪造 B的代理
签名,所以 A和 B都不能否认一个有效的代理签名( s,K)是由他们中的某个
人生成的。但是,A和 B可以互相对有效的代理签名进行抵赖,声称它是由对
方而不是由自己生成的。
? ( 5)身份证实性。在这个代理签名体制中,如果 A向 B发送了(,K)的时候,
将 K和 B的身份保存在一起,那么当 A看到一个有效的代理签名( s,K)的时
候,就可以通过 K确认 B的身份。
? ( 6)密钥依赖性。在这个代理签名体制中,代理签名密钥是 A的秘密密钥 x
的函数值,即它依赖于 x。
? ( 7)可注销性。 A如果想注销 B拥有的代理签名密钥,那么就可以向大家
“广播”一条消息(这个消息应该由 A签名),宣布 K不再有效,从而 B生成
的所有代理签名随之失效。
10.5基于纠错码的数字签名体制
系统参数, 用户选择一个可纠 t个错误的 GF(2)上的 [n,k,d ]既约 Goppa 码 C,这里的 d2t+1,或者有大码类的其它码 。 码 C的生成矩阵和校验矩阵分别为 kn 阶的G和 (n-k)n 阶的 H。
用户的公开密钥,
J=,=,=,H,,
用户的私有密钥, S,G,P
G和满足关系式 G=I,这里的 I是 kk阶单位矩阵,P和 S分别是 GF(2)上的 nn阶和 kk
阶满秩的随机矩阵, 和分别是它们的右逆阵,
签名算法,若待签的消息 MF,用户 1随机选取 EF且 w(E)t,则签名如下,
Sig(M)=(E+MSG)P= C
验证算 法,由 于信 道中可 能存 在干 扰,因 此用 户 2 收到的 消息为
C=C+E=(E+MSG)P+E,(EF)计算
D(C)= CT=[(E+MSG)P+E]PH= EH,
这里的 E=E+ EP,运用已知的译码算法如 Berlekamp-Massy算法译码 。
当译码器发现 w(E)>t,则要求用户重发签名, 当 E=0时, 正确译码得到 C
和 E,
Ver(M,C)=TRUE M =CJ+EW
? 安全性分析与改进
? Harn攻击
? Alabhadi-Wieker攻击
10.6 批验证协议
? 安全的批验证协议需满足如下的条件,
? 签名者在签名过程中一次产生多个消息的签名;
? 多个签名的有效性由签名验证者一次验证完成;
? 多个有效的签名一定满足批验证协议中的批验证
原则;
? 在批验证协议中有效的多个签名一定是有效的签
名。
? HARN非交互式批验证协议
? 系统参数:设 p是一 512位到 1024位的大素数,它
满足 Z中的离散对数问题是难解决的,q是 160位
长的素数,且 q,g Z是 Z域中的 q次单位根。定义
? К={( p,q,g,y,x),y=gmodp},
? 公开密钥 p,q,g,y,私有密钥 x。
? 签名算法:对于待签的消息 m(i=1,2,…,t),签名者
i随机选取 kZ,计算 r=gmodp,s= rk- h(m)x
modq,{r,s}(i=1,2,…,t) 即为生成的签名。
? 批验证算法:验证者收到消息的签名
{r,s},{r,s},…,{r,s} 后,验证
? Ver(m,s,r)=TRUE=gymodp modq
? N-M-R-V交互式批验证协议
? 系统参数:设 p是一 512位到 1024位的大素数,它满足 Z中
的离散对数问题是难解决的,q是 160位长的素数,且 q,
g Z是 Z域中的 q次单位根。定义
? К={( p,q,g,y,x),y=gmodp}
? 公开密钥 p,q,g,y,私有密钥 x。
? 签名算法:对于消息 m(i=1,2,…,t),签名者 i随机选取 kZ,
计算 r=gmodp,并将 r发送到验证者;验证者随机选取一
个 e比特位的随机数 b,并将 b发送到签名者 i;
? 签名者计算 s=k(h(m,b)+rx)mod q,( s,r,b)即为 i对消息
m的签名。
? 批验证算法:验证者收到签名( s,r,b)后,验证
? Ver(m,s,r,b)=TRUE=gymod p