第10章数字签名
第10章 数字签名
数字签名特点: 口签名不可伪造 口签名是可靠的; 口签名不可重用; 口签名不可改变; 口签名不可抵赖
◼ 数字签名特点： 签名不可伪造； 签名是可靠的； 签名不可重用； 签名不可改变； 签名不可抵赖
■定义1001:一个签名方案是一个5元组(M,A,K,S,v), 满足如下的条件: (1)M是一个可能消息的有限集; (2)A是一个可能签名的有限集; (3)密钥空间K是一个可能密钥的有限集; (4)对每一个K=(K1,k2K,都对应一个签名算法Sg∈ S和验证算法erx,∈V。每一个Sg:M一>A和Ver:M-> ATRUE, FALSE}是一个对每一个消息XM和每一个签名y∈ A满足下列方程的函数: Ver(xy)=UE当y=Sgk(x) FALSE当y≠Sgk,(x) (5)对每一个k,函数Sg和Ve都是多项式时间可计算的 函数。ver是一个公开函数,k1称作公钥;而Sg是一个秘 密函数,k2称作私钥,由用户秘密地保存
◼ 定义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称作私钥，由用户秘密地保存。 K2 K1 = y ( ) ( ) 2 2 FALSE Sig x TRUE y Sig x K K 当 当
101基于RSA和离散对数的签名体制 1011RSA签名方案 系统参数:设n=pq,且p和q是两个大素数,则 M=AZn定义K={(ndp,qe)}这里e和d满足ed ≡1(mod(n)Φ是欧拉函数) 公开密钥n,e 私有密钥p,q,d 签名算法:Sig2(x)y= xd mod n 验证算法:Ver(xy)=TRUE y=x(modn.(Xy)∈Zn×Zn
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 = x d mod n 验证算法： Ver(x,y)=TRUE y e ＝x (mod n). (x,y) ∈Zn×Zn
带加密的签名 口先签名再加密 口先加密再签名
◼ 带加密的签名 先签名再加密 先加密再签名
1012E| GAMAL签名方案及其一般化的模型 系统参数:设p是一大素数,g是Z的一个生成元, 定义K={(pyx)y= gx mod p}其中x∈Z。 公开密钥ypg 私有密钥x 签名算法:对于K=(p,gyx)、随机数k∈Z和待 签消息m,定义Sig(xk)=(r,s).这里的r= good p; S=(m-xr)k-mod(p-1) (r,s)即为生成的签名 验证算法:Ⅴer(mrs)=TRUE r mo p
10.1.2 EIGAMAL签名方案及其一般化的模型 系统参数：设p是一大素数，g是Z的一个生成元， 定义К={（p,g,y,x）:y= g x 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 y r r s=gmmod p
■ EIGAMAL签名方案的安全性分析 (1)本方案是基于离散对数问题的。 (2)对于随机数k应注意两方面的情况.首先,k不能泄露, 其次,随机数不能重复使用。 (3)伪造签名攻击 ■一般 ELGAMAL签名方案 1)系统初始化 (2)签名方程 AX=Bk+Cmod(p-1) (3)验证方程 y^=reg°modp
◼ EIGAMAL签名方案的安全性分析 （1）本方案是基于离散对数问题的。 （2）对于随机数k应注意两方面的情况.首先，k不能泄露， 其次，随机数不能重复使用。 （3）伪造签名攻击。 ◼ 一般ELGAMAL签名方案 （1）系统初始化 （2）签名方程 Ax=Bk+Cmod(p-1) （3）验证方程 y A=rBg C mod p
10.13DSS 系统参数:设p是-512位到1024位的大素数,它满足Zp中 的离散对数问题是难解决的,q是160位长的素数,且qp-1, g∈Zp是Zp域中的q次单位根。定义K={(p,qgyx):y=gx mod p 公开密钥:p,q2gy 私有密钥:x 签名算法:对于随机数k∈Z和待签消息m∈Z,计算r=( mod p)mod s=(h(m)+xr) kmod q,消息对(r,s)即为生成的签名。 验证算法:Ver(mr,s)=TRUE (yez gel mod p)modq=r 其中el-h(m) s-'modq,e2= rs 'modq
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 g e1 mod p)modq=r 其中 e1=h(m)s-1modq，e2=rs -1 modq
1014 Lamport签名方案 系统参数:设k是一个正整数,P={0,1,假设 fY→Z是一单向Hash函数,A=Y,随机选择 y∈Y这里1iskj=0,1且2=y),1 sisk,=0 私有密钥:y,1≡i≡kj=0,1 公开密钥:可j,1≤i≤kj=0, 签名算法:Sig(x12…,x)=(y1x12,yd) 验证算法: fa)=z1x1isk大RUE ver(x12…,xa12
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
1015不可否认签名方案 系统参数:设p=2q+1是一个素数,这里的q是素数且Zp中的离散对数 问题是难解决的,α是Z域中的q次单位根,1sa≤q-1,设G表示阶为q 的Z的乘法 子群M=A=G,且定义 K={(p,阝,a):β dp) 私有密钥a, 公开密钥p,a,β。 签名算法:设待签消息为x∈G,y=Sig(x)=x"modp,这里y∈G 验证协议:1.A随机选取el,e2∈Z 2A计算 c=yei pe2 nod p且把它传给B. 3B计算d= c modp,并将其传给A 4A接受y,并将它作为一有效签名当且仅当 d=xel a mod p
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 β e2mod p且把它传给B． ３.B计算d=c modp，并将其传给A． ４.A接受y，并将它作为一有效签名当且仅当 d=xe1 α e1mod p a mod q −1
