现代密码学和应用-数字签名课件

1、现代密码学与应用 数字签名主讲人：余艳玮E-mail: 2022/8/71参考书籍Handbook of Applied Cryptography: Chapter 11Applied Cryptography: Protocols, algorithms, and source code in C：Section 2.6，5.3，23.4；Chapter 202022/8/72大纲一、数字签名的基本概念二、RSA和相关签名方案三、Fiat-Shamir签名方案四、DSA和相关签名方案五、其他签名方案2022/8/73一、数字签名的基本概念2022/8/74数字签名实质上是一个数值它依赖于只有

2、签名者知道的某个秘密数以及待签消息的内容它将一条数字形式的消息与某发起实体相关联包含：数字签名的签名过程数字签名的验证过程：不需要签名者的秘密知识 （任何人都可验证真伪）2022/8/75数字签名的特点签名是可信(真实)的:任何人都可以方便的验证签名的有效性.签名是不可伪造的:除了合法的签名者外,任何其它人伪造签名是困难的，这种困难性指计算上是不可行的。签名是不可抵赖的：签名者不能否认自己的签名。签名是不可复制的：如果签名是从别的地方复制的，任何人都可发现消息与签名的不一致，从而拒绝签名。签名的消息是不可修改的2022/8/76数字签名的应用认证数据完整性不可抵赖性大型网络的公钥证书中2022

3、/8/771994年美国政府正式颁发了美国数字签名标准DSS(Digital Signature Standard)1995年我国也制定了自己的数字签名标准(GB15851-1995)2004年我国颁发中华人民共和国电子签名法2022/8/78相关术语消息M：签名者可将数字签名缀于该集合中的元素之后待签空间Ms：将签名变换应用于该集合中的元素签名空间S：与消息m关联的元素的集合，被用来将签名者绑定到消息R：签名变换2022/8/79数字签名方案的分类带附录的数字签名方案：要求初始消息M作为验证算法的输入DSA、ElGamal和Schnorr签名方案消息可以是任意长度带消息恢复的数字签名方案：消

4、息可从签名自身恢复，不要求初始消息M作为验证算法的输入RSA、Rabin等公钥签名方案通常消息的长度固定2022/8/710带附录的数字签名方案M:消息空间=mMh：消息摘要空间= S：消息签名空间=s*h: Hash函数SA,k: 签名变换(1-1映射)VA:验证变换2022/8/711带消息恢复的数字签名方案M:消息空间=mMR：消息的冗余值空间= MS：待签空间S：消息的签名空间=s*R: 冗余函数（可逆） (1-1映射)SA,k: 签名变换(1-1映射)M:消息空间=mMR：消息的冗余值空间= MS：待签空间S：消息的签名空间=s*R: 冗余函数（可逆） (1-1映射)SA,k: 签名

5、变换(1-1映射)2022/8/712从带消息恢复的签名产生带附录的签名先杂凑消息m；再对该杂凑值h(m)签名2022/8/713签名方案的攻击类型敌手的目标是：伪造签名完全攻克：敌手能计算出私钥选择性伪造：敌手能对一个特殊的消息或者预先选定的一类消息构造出正确的签名存在性伪造：敌手能伪造至少一个消息的签名，但敌手对被伪造签名所对应的消息几乎没有控制能力2022/8/714二、RSA和相关签名方案2022/8/715RSA签名方案有关RSA签名的可能攻击实际中的RSA签名ISO/IEC 9796规范PKCS #1规范2022/8/716RSA是以它的三个发明者Ron Rivest，Adi Sh

6、amir和Leoard Adleman的名字命名。RSA算法既可以用于加密，也可以用于数字签名。RSA的安全性基于大数分解的困难性，该算法已经经受住了多年深入的密码分析，密码分析者既不能证明也不能否认RSA的安全性，这恰恰说明该算法有一定的可信度。2022/8/7172.1 RSA签名方案密钥生成签名生成签名验证2022/8/718RSA签名方案的密钥生成实体A执行如下操作：独立地选取两大素数p和q(各100200位十进制数字)计算 n=pq，其欧拉函数值(n)=(p1)(q1)随机选一整数e，1e(n)，满足gcd(n), e)=1利用扩展的欧几里德算法，计算e的乘法逆元d=e -1 mod

7、 (n) 公钥为(n，e) ；私钥为d。(p, q不再需要，可以销毁。)2022/8/719RSA签名方案的签名生成和验证(1)实体A执行如下操作：计算整数计算A对m的签名为s为验证A的签名s及恢复消息m，实体B：获得A的可信公钥(n，e)计算验证恢复2022/8/720RSA签名方案的签名生成和验证(2)实体A执行如下操作：计算消息的散列值H(m)计算A对m的签名为(m, s)为验证A的签名，实体B：获得A的可信公钥(n，e)计算比较H(m)与v1，当且仅当H(m)=v1时，接受签名2022/8/7212.2 有关RSA签名的可能攻击整数因子分解 (公钥为(n，e) )d=e -1 mod

8、(n)分解n=pq再计算出(n)=(p1)(q1)由(n)和e，推导出私钥dRSA的乘性质s1=m1d mod ns2=m2d mod n(s1s2)=(m1m2)d mod n要求冗余函数R具有非乘性，即R(ab)R(a) R(b) (必要条件）2022/8/722使用RSA的建议(1)参数的选取：p,q,e,d。(2)不可使用公共模数。(3)明文的熵要尽可能的大。(4)尽量使用散列函数。(5)若RSA的模数n=2k bits，则：若消息的长度nB时，B有可能无法恢复消息2022/8/7242.4 ISO/IEC 9796规范是数字签名的第一个国际标准，1991公布。它规定了一套数字签名程序

9、，并采用一种带消息恢复的数字签名机制主要特点：基于公钥密码学未指定特定签名算法，但必须是k bits映射为k bits用于签署有限长度的消息提供消息恢复描述了必需的消息填充RSA、Rabin算法2022/8/725m (d bits)MP (8z bits)ME (8t bits)MR (16t bits)IR (k bits)s (k bits)2022/8/7262.5 PKCS #1规范公钥密码技术标准(PKCS)是包含RSA加密和签名的技术的一套规范PKCS #1规定了RSA签名采用带附录的签名机制使用Hash函数(MD2或MD5)2022/8/727MMDDEBmsED2022/8/

10、728三、 Fiege-Fiat-Shamir签名方案2022/8/729Fiege-Fiat-Shamir签名方案是由Fiege-Fiat-Shamir身份识别方案转变而来的安全性基于计算模n平方根的困难性签名生成的计算量远远小于RSA签名适合于需快速执行签名生成、且不限制密钥空间存储量的应用实体A对消息签名后，再由实体B来验证签名的有效性。具体包含：密钥生成签名生成和验证2022/8/730Fiege-Fiat-Shamir签名方案的密钥生成可信中心T选择两个素数p和q(保密，最好用完丢弃)，计算类似RSA的模数n=pq、并公开n。实体A选择k个与n互素、且互不相同的随机整数作为私钥s1,

11、 s2, ,sk(1sin)实体A计算vi=si-2 mod n (1ik)实体A的公钥(v1, v2 , vk; n)，私钥(s1, s2, ,sk)2022/8/731Fiege-Fiat-Shamir签名方案的签名生成和验证签名生成。实体A执行如下操作：随机选择正整数 r (n) ；计算u=r2 mod n计算e=(e1,ek)=h(m|u)，ei0,1 计算A对m的签名是(e，y)验证。实体B执行如下操作： （已知(e,y)和m)获得A的可信公钥(v1, v2 , vk; n)计算 计算e=h(m|w) 当且仅当e=e时接受签名2022/8/732签名验证的可行性证明实质上证明：w=u

12、2022/8/733方案的安全性所有实体都可使用相同的模数n需要一个可信第三方(TTP)产生素数p和q，以及每个实体的公钥和私钥安全性基于模n平方根的困难性2022/8/734基于身份的Fiege-Fiat-Shamir签名可对密钥生成过程作如下修改：TTP选择两个素数p和q(保密，最好用完丢弃)，计算模数n=pq、并公开n。TTP计算vj=f(IA|j), (1jk)IA含有A的身份信息的比特串f是Hash函数计算模n下vj-1的一个平方根sj, (1jk)公钥(v1, v2 , vk; n):只与身份信息IA相关私钥 (s1, s2, ,sk)2022/8/735四、DSA和相关签名方案2

13、022/8/736ElGamal签名方案Schnorr签名方案数字签名算法(DSA)带附录的签名方案带附录的签名方案1、安全性都基于Zp*上的离散对数计算的困难性2、都是随机化签名方案2022/8/7374.1 ElGamal签名方案密钥生成。实体A执行如下操作：随机产生一个大素数p，以及乘法群Zp* 的一个生成元g随机选择整数 (0 p-1)计算g mod pA的公钥(p,g,)，私钥2022/8/7384.1 ElGamal签名方案签名生成。实体A执行如下操作：随机一个秘密整数k (0 p-1) ，并满足gcd(k,p-1)=1计算r=gk mod p计算k-1 mod (p-1)计算s=

14、k-1h(m)- r mod (p-1)A对m的签名是(r,s)签名验证。B执行如下操作： （已知(r,s)和m)获得A的可信公钥(p,g,)验证0rp；否则拒绝接受该签名计算v1= rrs mod p计算h(m)和v2=gh(m) mod p当且仅当v1=v2时接受签名2022/8/739签名验证可行性的证明若签名(r, s)由A生成，则：2022/8/740ElGamal签名的安全性若敌手要伪造A的签名，则必须确定s=k-1h(m)- r mod (p-1) （k由敌手选取，但A的私钥是保密的)。伪造成功的概率为1/p对每个待签消息，须选择不同的k（保密）敌手已知(m1,s1,r,k,p)

15、，很容易就可以计算出敌手已知(m1,s1,r,k,p)，很容易就可以计算出若不同的消息，k相同，则r也相同2022/8/741必须采用杂凑函数h假设未采用杂凑函数，即h(m)=m选取任一整数对(u,v),gcd(v,p-1)=1，计算：则(r, s)也是对消息m1(=su mod (p-1)的一个有效签名。存在性伪造！2022/8/742ElGamal签名方案的变体签名方案为：u=av+kw mod (p-1)sh(m)rh(m)srrh(m)sh(m)rsrsh(m)srh(m)认证等式签名方程序号签名方程为：u=xv+kw mod (p-1)x是私钥2022/8/7434.2 Schnor

16、r签名方案密钥生成。实体A执行如下操作： (1)p 及 q 是两个大素数，且 q|(p-1); (3)随机选择数a (0aq)，计算y= a mod p (4)A的公钥是(p,q,y)，私钥是a2022/8/7444.2 Schnorr签名方案签名生成。实体A执行如下操作：随机选择一个秘密整数k (0kq)计算r= k mod p，e=h(m|r)和s=ae+k mod qA对m的签名为(s,e)签名验证。B执行如下操作： （已知(s,e)和m）获得A的可信公钥(p,q,y)计算v= sy-e mod p和e=h(m|v)当且仅当e=e时接受签名2022/8/745签名验证可行性的证明若(e,

17、s)是A对m的合法签字，则有v=sy-e=s(-a)e=k=r mod p故，h(m|v)=h(m|r)，即e=e2022/8/746Schnorr签名方案 vs. ElGamal签名方案Schnorr签名方案为Zp*中子集Zq*的生成元签名较短，由|q|及|H(M)|决定签名生成只需一次mod q乘法。所需计算量少，速度快。ElGamal签名方案g为Z*p的生成元，安全性较高签名长度由|p-1|及|H(M)|决定签名生成需要两次（在线）mod (p-1)的乘法运算2022/8/7474.3 DSA-概况由NIST1991年公布1993年公布修改版是美国联邦信息处理标准FIPS PUB 186

18、(即DSS)中使用的算法在Elgamal和Schnorr两个方案基础上设计的签名长度为320bit只能用于数字签字，不能用于加密2022/8/7484.3 DSA密钥生成。实体A执行如下操作： (1)选取素数q ，其中2159 q 2160 (2)选取t (t9)和素数p，2511+64t q 2512+64t且 q|(p-1); (4)随机选择数a (0aq)，计算y= a mod p (5)A的公钥是(p,q,y)，私钥是a2022/8/7494.3 DSA签名生成。实体A执行如下操作：随机选择一个秘密整数k (0kq)计算r= (k mod p) mod q计算k-1 mod qs= k

19、-1h(m)+ar mod qA对m的签名为(r,s)2022/8/7504.3 DSA签名验证。B执行如下操作： （已知(r,s)和m）获得A的可信公钥(p,q,y)验证0rq和0sq；否则拒绝该签名计算w=s-1 mod q 和 h(m)计算u1= wh(m) mod q 和u2=rw mod q计算v= (u1yu2 mod p) mod q当且仅当v=r时接受签名2022/8/751签名验证可行性的证明若(r,s)是A对m的合法签字，则有h(m)=-ar+ks (mod q)可推出：wh(m)+arw=k (mod q)即，u1+au2=k mod q(u1 (a)u2 mod p)

20、mod q = (k mod p) mod q即 v=r2022/8/752DSA的争议（1）DSA的选择过程不公开，并且提供的分析时间不充分。（2）DSA可能侵犯了其他专利。（3）DSA是由NSA研制的，可能存在馅门。（4）DSA不能用于加密或密钥分配。（5）DSA比RSA慢，二者产生签名的速度相同，但签名验证DSA比RSA慢40倍。（6）DSA的密钥长度太短。（7）RSA是一个事实上的标准。2022/8/753五、其他签名方案2022/8/754仲裁数字签名不可否认签名方案盲签名方案失败-停止签名方案代理签名团体签名门限签名2022/8/7555.1 仲裁数字签名2. 3. TTPAB1.

21、 IDA| 4. 消息的签名KA,KB分别为实体A和B的秘密密钥;KT是可信第三方(TTP)的秘密密钥;TTP拥有所有实体的秘密密钥2022/8/7565.2 不可否认签名方案验证协议要求签名者合作可以在一定程度上防止复制或散布产权所有者（签名者）所签字的文件的可能性，从而使产权所有者可以控制产品的散发。这在数字知识版权保护领域中有用一般的数字签名的复制品也可以来验证签名的有效性。如，公开宣传品的发布等2022/8/757应用在涉及私人隐私的问题上，如签名的私人信件、商业函件等，是不希望其他人验证的。由此1989年，Chaum和Antwerpen等引入了不可否认数字签名的概念。假定某公司A制作

22、了一个软件包。A将该软件包签名后卖给实体B。若B决定冒充A将该软件包复制后再卖给第三方C，但是没有A的合作时，B将无法向C验证该软件是否正版。2022/8/758密钥生成实体A执行如下操作：(1)选择素数p,q，且p=2q+1(2)选择Zp*的q阶子群的生成元 (q = 1 mod p)(3)随机选取整数a，并计算y = a mod p(4)A的公钥为(p,y)，私钥为a2022/8/759签名生成和验证签名生成。实体A执行如下操作：计算s = ma mod pA对消息m的签名是s验证：实体B执行如下操作：B获得A的可信公钥(p,y)B随机选取秘密整数x1,x21,2, , q-1B计算z=s

23、x1yx2 mod p，并将z发送给AA计算w=za-1 mod p，并将w发送给BB计算w=mx1x2 mod p当且仅当w=w时，接受签名2022/8/760 如果签字者拒绝合作就无法验证签名的有效性。但确实是签字者的数字签名，其又拒绝合作时，又如何处理？那么可以在法庭等第三方的监督下，启用拒绝协议（Disavowal Protocol），以证明签名的真假。如果对方拒绝参与否认协议，那么，就是他签名的；如果不是他签名的，否认协议可以确认他没有签名。2022/8/761拒绝协议接收者B选择随机数a、b， 接收者B计算： 将c发给签名者A。签名者A计算： , 将d发给接收者B； 接收者B验证：

24、 , 如果等式成立，说明签名有效，终止协议。 2022/8/762拒绝协议接收者再选择随机数i、j, 接收者计算： ，将C发送给签名者A ；签名者A计算： ，将D发送给接收者B ； 接收者B验证： 如果等式成立，B接收签名，并终止协议。2022/8/763拒绝协议如果下列等式： 成立，那么接收者B可以判定签名s是伪造的；否则签名有效，可说明A在企图拒绝签名s。 点评：上面的协议经过了两个回合，（1）-（4）和（5）-（8）都是认证过程的重复；最后通过（9）的一致性检验可以使接受方B能够确定出签名者A是否如实的执行了上述规定的协议。2022/8/7645.3 盲签名前面介绍的数字签名，签名者可以

25、查看所签信息的内容，这和日常生活的情形相符合：我们通常需要在知道文件内容之后才会签署。而在有些时候，要求签名者对所签署消息是不可见的，就需要盲签名。盲签名（blind signature)是由David Chanm于1983年提出的。盲签名在数字现金，电子投票等领域都有较大的应用价值，特别是目前的数字现金，大部分都是采用盲签名的原理实现。2022/8/765盲签名过程求签名者进行盲变换仲裁者进行签名求签名者进行解盲变换签名S(M)消息M2022/8/766完全盲签名协议 假定请求签名者为A，签字者（仲裁者）为B。盲签名就是要求A让B签署一个文件，而不让B知悉文件的内容，仅仅要求以后在需要时B可

26、以对他所签署的文件进行仲裁。那么可以通过下面称为完全盲签名的协议来完成； （1）A把文件用一个随机数乘之，该随机数常称为盲因子（Blinding Factor）。 （2）A将上面处理后的文件盲文件传送给B。2022/8/767 （3）B对盲文件签名。 （4）A取回B的签名结果，并用盲因子除之，得到B对原文件的签名。 显然，在上面的协议中，如果签名函数与乘法可交换，那么上述协议成立。否则盲变换不能用乘法，而采用其他变换方法。2022/8/768基于RSA的盲签名算法第一个盲签名算法的实现是D.Chaum于1985年提出的，该算法使用了RSA算法。下面设定签名者B的公钥参数为e，私钥参数为d，而模为n。 下面A让B进行盲签名，签署消息M： A盲变换：选用盲因子k,1kM ,计算： 将t传送给BB签名：B对t进行签名，计算 ，将签名S(t)传送给AA取得签名：A计算： 该签名算法显然成立，S其实就是B对消息M进行的RSA签名2022/8/769 那么上面协议中，B可以获得文件内容吗？如果盲因子是完全随机数，显然B不能获得所签署文件内容，即使他签署了A的上万份文件。但是这些文件确实是他签署的，并且可以在以