第10章 数字签名.ppt

第10章数字签名
数字签名特点:
签名不可伪造;
签名是可靠的;
签名不可重用;
签名不可改变;
签名不可抵赖。
:一个签名方案是一个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称作私钥,由用户秘密地保存。


系统参数:设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.
带加密的签名
先签名再加密
先加密再签名
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不能泄露,其次,随机数不能重复使用。
(3)伪造签名攻击。
一般ELGAMAL签名方案
(1)系统初始化
(2)签名方程
Ax=Bk+Cmod(p-1)
(3)验证方程
yA=rBgC mod p
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

系统参数:设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

系统参数:设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。
验证协议: ,e2 ∈ Z。
=ye1 β e2 mod p且把它传给B.
=c modp,并将其传给A.
,并将它作为一有效签名当且仅当
d=xe1 α e1mod p