第 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次单位根, １ ≦ a ≦ q-1,设 G表示阶
为 q的 Z的乘法
子群,M=A=G,且定义
К={（ p,α,β,a）, β ＝ αa mod p }
私有密钥 a,
公开密钥 p,α,β 。
签名算法：设待签消息为 x∈ G,y=Sig(x)=xamodp,这里 y ∈ G。
验证协议：１,A随机选取 e1, e2 ∈ Z。
２,A计算 c=ye1 β e2 mod p且把它传给 B,
３,B计算 d=c modp,并将其传给 A,
４,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
? 数字签名特点,
?签名不可伪造；
?签名是可靠的；
?签名不可重用；
?签名不可改变；
?签名不可抵赖。
? 定义 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次单位根, １ ≦ a ≦ q-1,设 G表示阶
为 q的 Z的乘法
子群,M=A=G,且定义
К={（ p,α,β,a）, β ＝ αa mod p }
私有密钥 a,
公开密钥 p,α,β 。
签名算法：设待签消息为 x∈ G,y=Sig(x)=xamodp,这里 y ∈ G。
验证协议：１,A随机选取 e1, e2 ∈ Z。
２,A计算 c=ye1 β e2 mod p且把它传给 B,
３,B计算 d=c modp,并将其传给 A,
４,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
