数字签名(新)

1、第第7章章 数字签名数字签名RSA签名体制二三Rabin签名体制一 数字签名的基本概念一ElGamal签名体制四五Schnorr签名体制六DSS签名体制七ESIGN签名体制八十十一Okamoto签名体制离散对数签名体制其它签名体制简介一 消息认证码的基本用途十二一 杂凑算法/加密/签名结合应用方案十三第第7章章 数字签名数字签名九OSS签名体制一、数字签名的基本概念一、数字签名的基本概念 收方能够确认或证实发方的签名，但不能伪造，简记为R1-条件。 发方发出签名的消息给收方后，就不能再否认他所签发的消息，简记为S-条件。 收方对已收到的签名消息不能否认，即有收报认证，简记为R2-条件。 第三者

2、可以确认收发双方之间的消息传送，但不能伪造这一过程，简记为T-条件。1. 数字签名与消息认证的区别数字签名与消息认证的区别 当收发者之间没有利害冲突时，这对于防止第三者的破坏已经足够了。 收方能够验证消息发送者身份是否被篡改； 收方能够验证所发消息内容是否被篡改。 当收发双方存在利害冲突时，单纯用消息认证技术就无法解决他们之间的纠纷。必须采用数字签名技术。 数字签名能确定消息来源的真实性 数字签名能保证实体身份的真实性 数字签名是不可否认的。2. 数字签名与公钥加密的区别数字签名与公钥加密的区别 公钥加密A采用B的公开密钥对信息加密，A将密文发给B；B用自己的私钥对收到的密文解密，恢复出明文。

3、 数字签名A采用自己的私钥采用自己的私钥对消息m签名，A将m和签名发给B；B收到A的签名后，采用采用A的公钥的公钥来验证签名的有效性；一个签名的消息很可能在多年之后才验证其真实性；数字签名可能需要多次验证；对数字签名的安全性和防伪造要求很高；要求签名速度比验证速度更快。3. 数字签名的分类数字签名的分类 按照消息是否被压缩分类 对整体消息进行签名； 对压缩的消息进行签名。 按照消息/签名的对应关系划分 确定性（确定性（deterministic）数字签名：）数字签名：消息与签名一一对应，对同一消息的签名永不变化，如RSA和Rabin算法； 随机化（随机化（randomized）或概率式数字签名

4、）或概率式数字签名：对同一消息的签名是变化的。因此，此类签名取决于算法中的随机参数的取值，如ElGamal算法。4. 签名体制的构成签名体制的构成m 由两部分构成m 签名算法（signature algorithm）m 验 证 算 法 （ v e r i f i c a t i o n algorithm）m 安全性约定m 签名算法或签名密钥是秘密的，只有签名人掌握；m 验证算法应当公开，以便于他人进行验证。Digital SignatureReferencemCSC1720 Introduction to InternetmAll copyrights reserved by C.C. Ch

5、eung 2003.105. 签名体制的数学表示签名体制的数学表示m 一个签名体制可由量(M, S, K, V)来表示 m M是明文空间m S是签名的集合m K是密钥空间m V是验证函数的值域，由真、伪组成。m 对于每一个kK，m Mm签名算法：s = Sigk(m) Sm验证算法：Verk(s, m) 真，伪 m 签名体制的安全性在于：m从m和s难于推出签名者的私钥k；m很难伪造另外一个消息m，使Verk(s, m) 真 。二、二、RSA数字签名体制数字签名体制m 令 , p1和p2是大素数；m 令m, sZn（整数域）m 选e，并计算出d，使m 将n, e公开（公钥）, 将p1、p2和d保

6、密（私钥）。m 对mZn，定义签名：s = Sigk(m) =md mod n 给定m, s，验证： m se mod n ?)(mod1ned21ppn体制参数签名过程验证过程13.13mSigning and Verifyingm13.5.1 ContinuedmFigure 13.7 RSA digital signature scheme13.14mRSA Signature on the Message Digestm13.5.1 ContinuedmFigure 13.8 The RSA signature on the message digestRSA签名体制的安全性签名体制的

7、安全性m 显然，由于只有签名者知道私钥d，根据RSA体制知，其他人不可能伪造签名；m 易于证实m, s是否是合法的消息m, 签名s对，只要计算 m se mod n 即可。 RSA体制的安全性依赖于n=p1p2分解的困难性。讨论安全性四、四、ElGamal签名体制签名体制m p：一个大素数，可使Zp中求解离散对数为困难问题；m g：是群ZP*的一个生成元或本原元素；m M：消息空间，为ZP*；m S：签名空间，为ZP-1；m x：用户秘密钥，xZP*m ygx mod pm p, g, y为公钥，x为秘密钥。m 选择秘密随机数k ZP*，m Mm 计算：H(m)m 计算：r=gk mod pm

8、 计算：s=H(m)-xrk-1 mod (p-1) 签名为Sigk(m)=(r, s)，将m和(r, s)送给对方。体制参数签名过程ElGamal签名体制签名体制m 收信人收到m和(r, s) ；m 计算：H(m)；m 验证：Verk(H(m), (r, s)=真 yrrs gH(m) mod p； 左边： yrrs gxrgsk mod p g(rx+sk) mod p 而(rx+sk) H(m) mod p-1 故： yrrs gH(m) mod pm 选择p=467, g=2, x=127, 则有y gx 2127 132 mod 467m 若待送消息m的杂凑值H(m)=100，选随机

9、数k=213 注意：(213, 466)=1, 且213-1 mod 466=431m 则：r=2213=29 mod 467, s=(100-127*29)431=51 mod 466。m 验证：(1)收信人计算H(m)=100， (2)验证：132292951=189 mod 467 2100=189 mod 467验证过程例子ElGamal签名体制的安全性签名体制的安全性m在不知消息,签名对时，伪造签名相当于求离散对数；m如果攻击者掌握了同一随机数k下的两个消息m1, m2的合法签名（r1, s1）（r2, s2），就会构造如下的方程： m1=r1x+s1k m2=r2x+s2k 可见：

10、攻击者解此方程可以求出x和k。要确保此签名体制的安全性，就必须保证每次签名时，选择不同的随机数k。讨论安全性五、五、Schnorr签名体制签名体制m p, q：大素数, q|p-1, 确保Zp中求解离散对数为困难问题；m g：是Zp中乘群ZP*的一个元素，且gq1 mod p；m M：消息空间，为ZP*；m S：签名空间，为ZP* ZP-1；m x：用户秘密钥，1xqm y：用户公钥，ygx mod pm p, q, g, y为公钥，x为秘密钥。m 用户选择秘密随机数kZq， m Mm 计算：w=gk mod p m 计算：r=H(w|m)m 计算：s=k+xr mod p 签名：Sigk(m

11、)=(r, s)作为签名，将m和(r, s)送给对方。体制参数签名过程13.20m13.5.3 Schnorr Digital Signature SchememFigure 13.11 General idea behind the Schnorr digital signature schemem收信人收到消息m和签名(r, s)m计算：H(m)m 计算：w=gsy-r mod pm 计算：H(w|m)m 验证H(w|m)=r ？即 Ver(y, (e, s), m)=真Schnorr签名验证：m在ElGamal体制中，g为Zp的本原元素；在Schnorr体制中，g为Zp*中的子集Zq*的

12、本原元，它不是Zp* 的本原元。m Schnorr的签名长度要比ElGamal短，由|q|及|H(m)|决定。m w=gk mod p可以预先计算，签名只需1次乘法和1次加法，所以签名速度非常快，适用于智能卡应用。 由于Schnorr签名较短，其安全性要比ElGamal签名差 。Schnorr签名体制的安全性签名体制的安全性Schnorr与ElGamal的区别安全性六、六、DSS签名体制签名体制m 1991年8月由NIST公布m 1994年5月19日由NIST正式公布m 1994年12月1日正式成为美国联邦信息处理标准m 它是基于ElGamal和Schnorr签名体制设计的m 该签名体制有较好

13、的兼容性和适用性，已经成为网络安全体系的基本构件之一。m DSA是DSS签名标准中所采用的数字签名算法； 此算法由D. W. Kravitz设计。 DSS概况什么是DSADSS签名算法签名算法DSAm p：大素数, , 512L1024；m q：(p-1)的素因子，且2159q2160，即字长160bm g：gh(p-1)/q mod p，且1h1m x：选择用户私钥，1xqm y：计算用户公钥，ygx mod pm p, q, g, y为公钥，x为私钥。m 用户选择秘密随机数k，0kqm 计算：H(m)m 计算：r=(gk modp)mod qm 计算：s=k-1(H(m)+xr) mod

14、qm 签名：Sigk(m)=(r, s)，将m和(r, s)送给对方。LLp212体制参数签名过程DSS签名算法签名算法DSAm 收信人收到m和(r, s) ；m 计算：H(m)；m 计算：w=s-1 mod qm 计算：u1=H(m)w mod qm 计算：u2=rw mod q m 计算：v=(gu1yu2) mod p mod qm 验证：v r ? 证明： v=(gu1yu2) mod p mod q =g H(m)wyrw mod p mod q =g H(m)wgxrw mod p mod q =gH(M)+xrw mod p mod q 而： H(m)+xrw = H(m)+xr

15、s-1=k mod q 所以：v=gk mod q= r 验证过程DSS签名框图签名框图p q g rsxkDSS签名验证框图签名验证框图y q g rvDSS签名算法的公众反应签名算法的公众反应m RSA公司想以RSA算法为标准m RSA指出：RSA可以加密，而DSA不能用于加密；m DSA是由NSA开发的，可能设有陷门；m DSA的签名验证速度比RSA慢，不适合联机在线验证；m RSA是一个事实上的标准，而DSS与现行标准不相容；m DSA未经公开选择，还没有足够的时间进行分析证明；m DSA可能侵犯了其他专利，如Schnorr签名算法，Diffie-Hellman的密钥分配算法；m DS

16、S中模数为512b所限定的密钥量太小，现已经改为凡是512-1024b中可被64除尽的数，均可供使用。RSA公司反应强烈DSS签名算法的实现速度签名算法的实现速度14sOff card14sN/A0.035s15s16s1.5s注：注：PC机80386/33M，模皆为512b七、七、ESIGN签名体制签名体制m n=p2q：大合数, 公开钥；m p, q：两个大素数，作为秘密钥；m M：消息空间m S：签名空间m k：安全参数（它的作用后面讨论） m 用户选择秘密随机数r，0rpqm 计算：H(M)m 计算：w=大于等于(H(M)-rk) mod n/pq的最小整数m 计算：s= r + (w

17、/krk-1) mod p pq Sigk(M, k)=s 作为签名，将M和s送给对方。体制参数签名过程m 收信人收到M和s；m 计算：H(M)；m 计算：srk mod nm 计算：a，它是大于等于2n/3的最小整数m 验证：Verk(H(M), s)=真 H(M) sk 且sk mod n H(M)+2am 此算法可以采用预计算来提高签名速度 (1) 发方预计算：u=rk mod n; v=1/(krk-1) mod p (2) 计算w：w=大于等于(H(M)-u) mod n/pq的最小整数 计算s：s = r + (wv mod p) pq m 通过预计算，可以使签名速度提高10倍。

18、k=2,3时, 被破解。作者建议k=8,16,32,64,128,256,1024 ESIGN签名算法签名算法验证过程讨论mESIGN在美国、加拿大、英国、法国、德国和意大利申请了专利。m 分析表明，此算法要比RSA，ElGamal及DSA速度快。m 其安全性与RSA或Rabin体制同样安全。ESIGN签名算法签名算法讨论八、八、Okamoto签名体制签名体制m p, q：大素数, p至少为512bit；m q: (p-1)的素因子，且q长约140 bitm g1, g2: 是全局公钥，与q同长的随机数; m s1, s2: 是秘密钥，与q同长的随机数;m M：消息空间，MZP*；m S：签名

19、空间，为ZP* ZP-1；m v：用户公钥，vg1-s1 g2-s2 mod pm p, q, g1, g2, v为公钥， s1, s2为秘密钥。 m 用户选择两秘密随机数r1, r2，0r1, r2qm 计算：e=H(g1r1 g2r2 mod p, M)m 计算：y1=(r1 + es1) mod qm 计算：y2=(r2 + es2) mod q Sigk(M, k)=S=(e, y1, y2) 为签名，将M和S 送给对方。体制参数签名过程m 收信人收到M和S=(e, y1, y2) ；m 验证：Verk(M, e, y1, y2)=真 H(g1y1 g2y2 vemod p，M) =

20、e g1y1 g2y2 vemod p= g1 (r1 + es1) g2 (r2 + es2) (g1-s1 g2-s2)e mod p = g1 r1 g2 r2 mod p 所以： H(g1y1 g2y2 vemod p，M) = H(g1r1 g2r2 mod p, M) = eOkamoto签名算法签名算法验证过程讨论九、九、OSS签名体制签名体制m n：大整数（不必知道其分解）；m k： 随机数，满足(k, n)=1m h：满足h= -k-2 mod nm M：消息空间，MZP*；m S：签名空间，为ZP* ZP*；m h, n为公钥，k为秘密钥。 m 用户选择随机数r，满足 (r

21、, n)=1 m 计算：s1=(M/r+r)/2 mod n，m 计算：s2=k(M/r-r)/2 mod nSigk(M, k)=S=(s1, s2)作为M的签名，将M和(s1, s2)送给对方。体制参数签名过程m 收信人收到M和=(s1, s2) ；m 计算：M= s12+hs22 mod n；m 验证：Verk(H(M), r, s)=真 M M ； 因为： M=(M/r+r)/2 )2 +h (k(M/r-r)/2)2 mod n =M2/r2+2M+r2-M2/r2+2M-r2/4 mod n =4M/4 mod n =M mod n OSS签名算法签名算法Ong-Schnorr-S

22、hamir验证过程OSS签名算法签名算法m 对于以上由二次或三次多项式构造的签名，已被证明是不安全的；m 四次多项式方案也已被攻破。m Okamoto曾提出一种补救措施。 ESIGN是由Okamoto和Sharaishi在OSS的基础上提出的数字签名方案。 讨论十、离散对数签名体制十、离散对数签名体制m p：大素数m q: (p-1)的大素因子m g：g ZP*，且满足gq=1 mod pm M：消息空间，MZP*；m S：签名空间；m x：用户秘密钥，1xqm y：用户公钥，ygx mod pm p, q, g, y为公钥，x为秘密钥。m 用户选择一次性秘密随机数k，0kqm 计算：H(m)

23、m 计算：r=gk mod pm 签字方程：ak = b + cx mod q Sigk(m)=(r, s)作为签名，将m和(r, s)送给对方。体制参数签名过程所有以上的签名体制均可看成其一个特例！所有以上的签名体制均可看成其一个特例！签名的验证过程签名的验证过程 收端收到消息m和签名(r, s)后，可以按照以下验证方程检验： Ver(M, r, s)=真 ragbyc mod q签名算法中签名算法中a, b, c的取值的取值rs H(m)rk=s+H(m)x mod qrH(m)srk=H(m)+sx mod qsr H(m)sk=r+H(m)x mod q sH(m)rsk=H(m)+r

24、x mod qH(m)srH(m)k=s+rx mod qH(m)rsH(m)k=r+sx mod q签名方程签名方程ak=b+cx对应的签名算法对应的签名算法rk=s+H(m)x mod qrr=gsyH(m) mod pYen, Laihrk=H(m)+sx mod qrr=gH(m)ys mod pAgnew, Yenrk=r+H(m)x mod qrr=gH(m)ys mod psk=H(m)+rx mod qrs=gH(m)yr mod pElGamal, DSAH(m)k=s+rx mod qrH(m)=gsyr mod pSchnorr, NybergH(m)k=r+sx mod

25、 qrH(M)=grys mod p十一、其他签名体制十一、其他签名体制不可否认签名不可否认签名为什么需要不可否认签名？普通签名可以精确地被复制，适合公开声明之类文件的散发；但是对于个人或公司信件，特别是有价值文件的签名，如果也可以随意复制和散发，就可能造成灾难。这类签名要求在签名者合作下，才能验证签名。无签名者合作，不可能验证签名，从而可以防止复制和散布他所签的文件。这一性质可以可以用于知识产权的保护等，在电子出版物的知识产权保护中将大显身手。产权拥有者可以控制产品的发布。1989年Chaum和Antwerpen提出不可否认签名的概念其他签名体制其他签名体制防失败签名防失败签名（Fail-S

26、top Signature）这是一种强化安全性的数字签名，可防范有充足计算资源的攻击者。当A的签名受到攻击，甚至在分析出A的私钥的情况下，攻击者也难以伪造A的签名。同时，A也难以对自己的签名进行抵赖。它是一种一次性签名方案，即给定密钥只能签署一个消息。1991年由Pfitzmann和Waidner提出其他签名体制其他签名体制盲签名盲签名（Blind Signature）对于一般的数字签名来说，签名者总是要先知道文件内容后才签名，这是正常的应用情形。但是有时需要某人对一个文件签名，但又不想让他知道所签署的文件内容。在选举投票和数字货币协议中，会用到此签名体制。盲签名在电子商务系统中，有重要的应用

27、。1983年由Chuam最先提出其他签名体制其他签名体制群签名群签名（Group Signature）只有群中的成员才能代表群体签名。接收到签名的人可以用公钥验证群签名，但不可能知道由群体中的那个成员所签。发生争议时，由群体中的成员或可信赖机构识别群签名的签名者。这类签名可以用于项目投标。例如：所有参有投标的公司组成一个群体，且每个公司都匿名地采用群签名对自己的标书签名。当选中了一个满意的标书后，招标方就可以识别出签名的公司，而其他标书仍保持匿名。中标方若想反悔已无济于事，因为在没有他参与的情况下，仍可以正确地识别出签名人是谁。1991年由Chaum和van Heyst最先提出其他签名体制其他签名体制代理签名代理签名（Proxy Signature）代理签名就是某人授权其代理进行的签名，在委托签名时，签名密钥不交给代理人。代理签名有如下几个特性： l不可区分性：代理签名与委托人的签名不可区分；l不可伪造性：只有委托人和代理人可以建立合法的签名；l代理签名的差异