第9章数字签名

数字签名曹天杰中国矿业大学计算机学院数字签名的基本概念一个签名方案是一个满足下列条件的五元组(P,A,K,S,V)：1）P是所有可能的消息组成的有限集。2）A是所有可能的签名组成的有限集。3）K是所有可能的密钥组成的有限集。4）对每一个k∈K，有一个签名算法Sk∈S和一个相应的验证算法Vk∈V。对每一个消息x∈P和每一个签名y∈A，每一个签名算法Sk：PA和验证算法Vk：P×A{0,1}都满足：当y＝Sk(x)时，Vk(x,y)＝1，否则Vk(x,y)＝0。数字签名的基本概念数字签名具备以下主要特点：不可伪造性。不可否认性。保证消息的完整性。RSA签名签名者取两个随机大素数p和q（保密），计算公开的模数n=pq(公开)，计算秘密的欧拉函数(n)=（p-1）(q-1)（保密）。随机选取整数e，满足gcd(e,(n))=1(公开e，验证密钥)计算d，满足de≡1(mod(n))(签名密钥)签名:y=H(x)d(modn),把x||y发送给验证者验证:检查下式是否成立yd=H(x)(modn).yeH(x)d比较消息x消息xy消息xyHH(x)yeRSA签名标准PSSbcpadding2maskedDBMMpadding1mHashsaltsaltH’MGFM’=DB=EM=aHashHash对RSA数字签名的攻击（1）一般攻击（2）利用已有的签名进行攻击（3）利用签名进行攻击获得明文（4）对先加密后签名方案的攻击一般攻击由于RSA密码的加密运算和解密运算具有相同的形式，都是模幂运算。设e和n是用户A的公开密钥，所以任何人都可以获得并使用e和n。攻击者首先随意选择一个数据Y，并用A的公开密钥计算X＝Yemodn，于是便可以用Y伪造A的签名。因为X是A对Y的一个有效签名。这种攻击实际上的成功率是不高的。因为对于随意选择的Y，通过加密运算后得到的X具有正确语义的概率是很小的。可以通过认真设计数据格式或采用Hash函数与数字签名相结合的方法阻止这种攻击。利用已有的签名进行攻击假设攻击者想要伪造A对M3的签名，他很容易找到另外两个数据M1和M2，使得M3＝M1M2modn，他设法让A分别对M1和M2进行签名：S1＝(M1)dmodn，S2＝(M2)dmodn。于是攻击者就可以用S1和S2计算出A对M3的签名S3：(S1S2)modn＝((M1)d(M2)d)modn＝(M3)dmodn＝S3。对付这种攻击的方法是用户不要轻易地对其他人提供的随机数据进行签名。更有效的方法是不直接对数据签名，而是对数据的Hash值签名。利用签名进行攻击获得明文设攻击者截获了密文C，C＝Memodn，他想求出明文M。于是，他选择一个小的随机数r，并计算x＝remodn，y＝xCmodn，t＝r–1modn。因为x＝remodn，所以xd＝(re)dmodn，r＝xdmodn。然后攻击者设法让发送者对y签名，于是攻击者又获得S＝ydmodn攻击者计算tSmodn＝r−1ydmodn＝r−1xdCdmodn＝Cdmodn＝M，于是攻击者获得了明文M。对付这种攻击的方法也是用户不要轻易地对其他人提供的随机数据进行签名。最好是不直接对数据签名，而是对数据的Hash值签名。对先加密后签名方案的攻击假设用户A采用先加密后签名的方案把M发送给用户B，则他先用B的公开密钥eB对M加密，然后用自己的私钥dA签名。再设A的模为nA，B的模为nB。于是A发送如下的数据给B：((M)eBmodnB)dAmodnA，如果B是不诚实的，则他可以用M1抵赖M，而A无法争辩。因为nB是B的模，所以B知道nB的因子分解，于是他就能计算模nB的离散对数，即他就能找出满足(M1)x＝MmodnB的x，然后他公布他的新公开密钥为xeB。这时他就可以宣布他收到的是M1而不是M。A无法争辩的原因在于下式成立：((M1)xeBmodnB)dAmodnA＝((M)eBmodnB)dAmodnA。为了对付这种攻击，发送者应当在发送的数据中加入时间戳，从而可证明是用eB对M加密而不是用新公开密钥xeB对M1加密。另一种对付这种攻击的方法是经过Hash处理后再签名。数字签名标准DSSDSS签名利用一个单向Hash函数产生消息的一个Hash值，Hash值连同随机数k一起作为签名函数的输入，签名函数还需使用发方的秘密钥SKA和供所有用户使用的一组参数，称这组参数为全局公开钥PKG+。签名函数的两个输出s和r就构成了消息的签名(s,r)。接收方收到消息后再产生出消息的Hash值，将Hash值与收到的签名一起输入验证函数，此外，验证函数还需输入全局公开钥PKG+和发方的公开钥PKA。验证函数的输出如果与收到的签名成分r相等，则证明了签名是有效的。M||MHSigSrHVerPKG+SKGPKAPKG+k比较数字签名算法DSADSS的签名算法称为DSA，DSA使用以下参数：1）p为素数，要求2L–1＜p＜2L，其中512≤L≤1024且L为64的倍数，即L＝512＋64jj＝0,1,2,,82）q为素数，它是(p－1)的因子，2159＜q＜2160。3）g＝h(p−1)/qmodp，其中1＜h＜p—1，且满足使g＝h(p−1)/qmodp＞1。4）x为随机数，0＜x＜q。5）y＝gxmodp。6）k为随机数，0＜k＜g。这里参数p、q、g可以公开，且可为一组用户公用。x和y分别为一个用户的私钥和公钥。所有这些参数可在一定时间内固定。参数x和k用于产生签名，必须保密。参数k必须对每一签名都重新产生，且每一签名使用不同的k。对数据M的签名为数r和s，它们分别如下计算产生：r＝(gkmodp)modq，s＝(k−1(SHA(M))＋xr)modq。其中k−1为k的乘法逆元，即k−1k＝1modq，且0＜k−1＜q。SHA是安全的Hash函数，它从数据M抽出其摘要SHA(M)，SHA(M)为一个160位的二进制数字串。应该检验计算所得的r和s是否为零，若r＝0或s＝0，则重新产生k，并重新计算产生签名r和s。最后，把签名r和s是附在数据M后面发给接收者：(M||r||s)。为了验证签名，要使用参数p、q、g，用户的公开密钥y和其标识符。令MP，rP，sP分别为接收到的M，r和s。1）首先检验是否有0＜rP＜q，0＜sP＜q，若其中之一不成立，则签名为假。2）计算：w＝(sP1)modq，u1＝(SHA(MP)w)modq，u2＝((rP)w)modq，v＝(((g)u1(y)u2)modp)modq。3）若v＝rP，则签名为真，否则签名为假或数据被篡改。EIGamal签名方案公钥：p:素数，gp（p,g可由一组用户共享）y=gx(modp)私钥：xp签名：k:随机选取，与p-1互素，a（签名）=gkmodp，b（签名）满足M=(xa+kb)mod(p-1)(即有：b=(M-xa)k-1mod(p-1))验证：如果yaab(modp)=gM(modp)，则签名有效。Schnorr签名令待签消息为M，对给定的M做下述运算：任选一秘密随机数k∈Zq计算签名S=(e,s)r≡gkmodpsk-xemodq式中e=H(r||M)。验证签名S=(e,s)r’≡gsyemodp而后计算H(r’||M)。验证H(r’||M)=eECDSA签名算法签名的时候，自然有待签署的消息m，全局参数D＝(q,FR,a,b,G,n,h)，还有签名者的公钥私钥对(Q,d)。签名的算法步骤描述如下：1）选择一个随机数k，k∈[1,n－1]；2）计算kG＝(x1,y1)；3）计算r＝x1modn；如果r＝0，则回到步骤1）；4）计算k−1modn；5）计算e＝SHA1(m)；6）计算s＝k−1(e＋dr)modn，如果s＝0，则回到步骤1）；7）对消息的签名为(r,s)。最后签名者就可以把消息m和签名(r,s)发送给接收者。当接收者收到消息m和签名(r,s)之后，验证对消息签名的有效性，需要取得如下参数：全局参数D＝(q,FR,a,b,G,n,h)，发送者的公钥Q。我们建议接收者利用前面的合法性检验算法，也对参数D和Q的合法性进行检验。验证算法可以描述如下：1）检验r、s，要求r、s∈[1,n－1]；2）计算e＝SHA1(m)；3）计算w＝s−1modn；4）计算u1＝ewmodn；u2＝rwmodn；5）计算X＝u1G＋u2Q；6）如果X＝0，表示签名无效；否则，X＝(x1,y1)，计算v＝x1modn；7）如果v＝r，表示签名有效；否则表示签名无效。基于身份的签名方案Shamir的基于身份的数字签名方案Shamir的方案包括四个算法：1）初始化：KGC选择n、e和f，其中n为两个大素数p、q的乘积，e是一个与(n)互素的大素数，f是一个单向函数，则n,e,f为公开的安全参数。2）密钥提取：所有的用户都使用相同的n、e、f，唯一不同是公开的用户身份值i，与i值相对应的私钥为g，满足：ge＝i(modn)。由离散对数的困难性可知，其他人计算g是困难的。3）签名算法：用户对消息m进行签名，首先选择一个随机数r，计算t＝re(modn)，s＝grf(tm)，则将签名(s,t,r)发送给验证者。4）验证算法：验证者收到签名(s,t,r)之后，如果成立，则接受该签名为有效签名；否则，拒绝该签名。)(?mtfetisCha-Cheon的基于身份的数字签名方案Cha和Cheon的方案包括4个阶段：设置、析出、签名、验证。1）设置：给定安全参数k∈Z+，由输入的k值生成一个素数q，两个q阶群G1和G2，一个可接受的双线性映射ê:G1×G1→G2。随机选择生成元P∈G1。取随机数s∈Zq*为主密钥，令Ppub＝sP。选择2个密码学Hash函数H1:{0,1}*G1*和H2:{0,1}*×G1*Zq*。系统参数为params＝q,G1,G2,ê,P,Ppub,H1,H2，主密钥为s∈Zq*。2）析出：给定串ID∈{0,1}*，PKG计算QID＝H1(ID)，计算私钥dID＝sQID，这里s为主密钥。3）签名：给定私钥dID和消息m，选取随机数r∈Zq*，计算U＝rQID，h＝H2(m,U)和V＝(r＋h)dID，输出签名＝(U,V)。4）验证：对于给定的身份ID，消息m的签名＝(U,V)，验证ê(P,V)＝ê(Ppub,U＋hQID)是否成立，这里h＝H2(m,U)。Cha和Cheon在预言机模型下证明了其方案的安全性，他们的这个思路被普遍应用于基于身份的签名方案的安全性证明中。