数字签名(新)

第7章数字签名RSA签名体制二三Rabin签名体制一数字签名的基本概念一ElGamal签名体制四五Schnorr签名体制六DSS签名体制七ESIGN签名体制八十十一Okamoto签名体制离散对数签名体制其它签名体制简介一消息认证码的基本用途十二一杂凑算法/加密/签名结合应用方案十三第7章数字签名九OSS签名体制一、数字签名的基本概念1.收方能够确认或证实发方的签名，但不能伪造，简记为R1-条件。2.发方发出签名的消息给收方后，就不能再否认他所签发的消息，简记为S-条件。3.收方对已收到的签名消息不能否认，即有收报认证，简记为R2-条件。4.第三者可以确认收发双方之间的消息传送，但不能伪造这一过程，简记为T-条件。类似于手书签名，数字签名也应满足以下要求：1.数字签名与消息认证的区别当收发者之间没有利害冲突时，这对于防止第三者的破坏已经足够了。收方能够验证消息发送者身份是否被篡改；收方能够验证所发消息内容是否被篡改。当收发双方存在利害冲突时，单纯用消息认证技术就无法解决他们之间的纠纷。必须采用数字签名技术。数字签名能确定消息来源的真实性数字签名能保证实体身份的真实性数字签名是不可否认的。消息认证数字签名2.数字签名与公钥加密的区别公钥加密A采用B的公开密钥对信息加密，A将密文发给B；B用自己的私钥对收到的密文解密，恢复出明文。数字签名A采用自己的私钥对消息m签名，A将m和签名发给B；B收到A的签名后，采用A的公钥来验证签名的有效性；一个签名的消息很可能在多年之后才验证其真实性；数字签名可能需要多次验证；对数字签名的安全性和防伪造要求很高；要求签名速度比验证速度更快。3.数字签名的分类按照消息是否被压缩分类对整体消息进行签名；对压缩的消息进行签名。按照消息/签名的对应关系划分确定性（deterministic）数字签名：消息与签名一一对应，对同一消息的签名永不变化，如RSA和Rabin算法；随机化（randomized）或概率式数字签名：对同一消息的签名是变化的。因此，此类签名取决于算法中的随机参数的取值，如ElGamal算法。4.签名体制的构成由两部分构成签名算法（signaturealgorithm）验证算法（verificationalgorithm）安全性约定签名算法或签名密钥是秘密的，只有签名人掌握；验证算法应当公开，以便于他人进行验证。DigitalSignatureReferenceCSC1720–IntroductiontoInternetAllcopyrightsreservedbyC.C.Cheung2003.105.签名体制的数学表示一个签名体制可由量(M,S,K,V)来表示M是明文空间S是签名的集合K是密钥空间V是验证函数的值域，由真、伪组成。对于每一个k∈K，m∈M签名算法：s=Sigk(m)∈S验证算法：Verk(s,m)∈{真，伪}签名体制的安全性在于：从m和s难于推出签名者的私钥k；很难伪造另外一个消息m’，使Verk(s,m’)∈{真}。二、RSA数字签名体制令,p1和p2是大素数；令m,s∈Zn（整数域）选e，并计算出d，使将n,e公开（公钥）,将p1、p2和d保密（私钥）。对m∈Zn，定义签名：s=Sigk(m)=mdmodn给定m,s，验证：m≡semodn?)(mod1ned21ppn体制参数签名过程验证过程13.13SigningandVerifying13.5.1ContinuedFigure13.7RSAdigitalsignaturescheme13.14RSASignatureontheMessageDigest13.5.1ContinuedFigure13.8TheRSAsignatureonthemessagedigestRSA签名体制的安全性显然，由于只有签名者知道私钥d，根据RSA体制知，其他人不可能伪造签名；易于证实{m,s}是否是合法的{消息m,签名s}对，只要计算m≡semodn即可。RSA体制的安全性依赖于n=p1×p2分解的困难性。讨论安全性四、ElGamal签名体制p：一个大素数，可使Zp中求解离散对数为困难问题；g：是群ZP*的一个生成元或本原元素；M：消息空间，为ZP*；S：签名空间，为ZP-1；x：用户秘密钥，x∈ZP*y≡gxmodpp,g,y为公钥，x为秘密钥。选择秘密随机数k∈ZP*，m∈M计算：H(m)计算：r=gkmodp计算：s=[H(m)-xr]k-1mod(p-1)签名为Sigk(m)=(r,s)，将m和(r,s)送给对方。体制参数签名过程ElGamal签名体制收信人收到m和(r,s)；计算：H(m)；验证：Verk(H(m),(r,s))=真yrrs≡gH(m)modp；左边：yrrs≡gxrgskmodp≡g(rx+sk)modp而(rx+sk)≡H(m)modp-1故：yrrs≡gH(m)modp选择p=467,g=2,x=127,则有y≡gx≡2127≡132mod467若待送消息m的杂凑值H(m)=100，选随机数k=213注意：(213,466)=1,且213-1mod466=431则：r=2213=29mod467,s=(100-127*29)431=51mod466。验证：(1)收信人计算H(m)=100，(2)验证：132292951=189mod4672100=189mod467验证过程例子ElGamal签名体制的安全性在不知{消息,签名}对时，伪造签名相当于求离散对数；如果攻击者掌握了同一随机数k下的两个消息m1,m2的合法签名（r1,s1）（r2,s2），就会构造如下的方程：m1=r1x+s1km2=r2x+s2k可见：攻击者解此方程可以求出x和k。要确保此签名体制的安全性，就必须保证每次签名时，选择不同的随机数k。讨论安全性五、Schnorr签名体制p,q：大素数,q|p-1,确保Zp中求解离散对数为困难问题；g：是Zp中乘群ZP*的一个元素，且gq≡1modp；M：消息空间，为ZP*；S：签名空间，为ZP*×ZP-1；x：用户秘密钥，1xqy：用户公钥，y≡gxmodpp,q,g,y为公钥，x为秘密钥。用户选择秘密随机数k∈Zq，m∈M计算：w=gkmodp计算：r=H(w||m)计算：s=k+xrmodp签名：Sigk(m)=(r,s)作为签名，将m和(r,s)送给对方。体制参数签名过程13.2013.5.3SchnorrDigitalSignatureSchemeFigure13.11GeneralideabehindtheSchnorrdigitalsignaturescheme收信人收到消息m和签名(r,s)计算：H(m)计算：w’=gsy-rmodp计算：H(w’||m)验证H(w’||m)=r？即Ver(y,(e,s),m)=真Schnorr签名验证：在ElGamal体制中，g为Zp的本原元素；在Schnorr体制中，g为Zp*中的子集Zq*的本原元，它不是Zp*的本原元。Schnorr的签名长度要比ElGamal短，由|q|及|H(m)|决定。w=gkmodp可以预先计算，签名只需1次乘法和1次加法，所以签名速度非常快，适用于智能卡应用。由于Schnorr签名较短，其安全性要比ElGamal签名差。Schnorr签名体制的安全性Schnorr与ElGamal的区别安全性六、DSS签名体制1991年8月由NIST公布1994年5月19日由NIST正式公布1994年12月1日正式成为美国联邦信息处理标准它是基于ElGamal和Schnorr签名体制设计的该签名体制有较好的兼容性和适用性，已经成为网络安全体系的基本构件之一。DSA是DSS签名标准中所采用的数字签名算法；此算法由D.W.Kravitz设计。DSS概况什么是DSADSS签名算法——DSAp：大素数,,512≦L≦1024；q：(p-1)的素因子，且2159q2160，即字长160bg：g≡h(p-1)/qmodp，且1h(p-1)，h(p-1)/qmodp1x：选择用户私钥，1xqy：计算用户公钥，y≡gxmodpp,q,g,y为公钥，x为私钥。用户选择秘密随机数k，0kq计算：H(m)计算：r=(gkmodp)modq计算：s=[k-1(H(m)+xr)]modq签名：Sigk(m)=(r,s)，将m和(r,s)送给对方。LLp212体制参数签名过程DSS签名算法——DSA收信人收到m和(r,s)；计算：H(m)；计算：w=s-1modq计算：u1=[H(m)w]modq计算：u2=rwmodq计算：v=[(gu1yu2)modp]modq验证：v≡r?证明：v=[(gu1yu2)modp]modq=[gH(m)wyrwmodp]modq=[gH(m)wgxrwmodp]modq=[g[H(M)+xr]wmodp]modq而：[H(m)+xr]w=[H(m)+xr]s-1=kmodq所以：v=gkmodq=r验证过程DSS签名框图f2mHf1pqgrsxkDSS签名验证框图f4Hf3yqgrvmsr比较DSS签名算法的公众反应RSA公司想以RSA算法为标准RSA指出：RSA可以加密，而DSA不能用于加密；DSA是由NSA开发的，可能设有陷门；DSA的签名验证速度比RSA慢，不适合联机在线验证；RSA是一个事实上的标准，而DSS与现行标准不相容；DSA未经公开选择，还没有足够的时间进行分析证明；DSA可能侵犯了其他专利，如Schnorr签名算法，Diffie-Hellman的密钥分配算法；DSS中模数为512b所限定的密钥量太小，现已经改为凡是512-1024b中可被64除尽的数，均可供使用。RSA公司反应强烈DSS签名算法的实现速度DSARSA密钥生成14sOffcard预计算14sN/A签名0.035s15s证实16s1.5s注：PC机80386/33M，模皆为512b七、ESIGN签名体制n=p2q：大合数,公开钥；p,q：两个大素数，作为秘密钥；M：消息空间S：签名空间k：安全参数（它的作用后面讨论）用户选择秘密随机数r，0rpq计算：H(M)计算：w=大于等于[(H(M)-rk)modn]/pq的最小整数计算：s=r+[(w/krk-1)modp]×pqSigk(M,k)=s作为签名，将M和s送给对方。体制参数签名过程收信人收到M和s；计算：H(M)；计算：srkmodn计算：a，它是大于等于2n/3的最小整数验证：Verk(H(M),s)=真H(M)≤sk且skmodn﹤H(M)+2a此算法可以采用预计算来提高签名速度(1)发方预计算：u=rkmodn;v=1/(krk-1)modp(2)计算w：w=大于等于[(H(M)-u)modn]/pq的最小整数计算s：s=r+(wvmodp)×pq通过预计算，可以使签名速度提高10倍。k=2,3时,被破解。作者建议k=8,16,32,64,128,256,1024ESIGN签名算法验证过程讨论ESIGN在美国、加拿大、英国、法国、德国和意大利申请了专利。分析表明，此算法要比RSA，ElGamal及DSA速度快。其安全性与RSA或Rabin体制同样安全。ESIGN签名算法讨论八、Okamoto签名体制p,q：大素数,p至少为512bit；q:(p-1)的素因子，且q长约140bitg1,g2:是全局公钥，与q同长的随机数;s1,s2:是秘密钥，与q同长的随机数;M：消息空间，M∈ZP*；S：签名空间，为ZP*×ZP-1；v：用户公钥，v≡g1-s1g2-s2modpp,q,g1,g2,v为公钥，s1,s2为秘密钥。用户选择两秘密随机数r1,r2，0r1,r2q计算：e=H(g1r1g2r2modp,M)计算：y1=(r1+es1)modq计算：y2=(r2+es2)modqSigk(M,k)=S=(e,y1,y2)为签名，将M和S送给对方。体制参数签名过程收信人收到M和S=(e,y1,y2)；验