《认证理论与技术-数字签名.ppt》由会员分享,可在线阅读,更多相关《认证理论与技术-数字签名.ppt(58页珍藏版)》请在三一办公上搜索。
1、西安电子科技大学出版社,二00九年十二月,应 用 密 码 学,张仕斌 万武南 张金全 孙宣东编著,第7章 认证理论与技术数字签名,知识点:,数字签名的原理及分类 RSA及ElGamal数字签名算法 数字签名标准DSS 其他数字专用签名方案 盲签名方案及其应用,7.1.概述,由于计算机和网络的快速发展,电子商务日渐兴起,通过在文档上签字盖章的方式进行商务活动,显得效率很低。例如,一个在中国的公司和一个在美国的公司进行合作,双方达成协议后,要签订一个合同,则需要一方签名盖章后,邮寄或派人到另一方去签名盖章。于是人们就想,能不能对已经协商好的电子文档进行和手写签名一样的电子签名呢?并且这个电子签名和
2、要求手写签名具有相同的法律效力,同时也是安全的,也即不能被伪造。这样,一方签名后,可以通过电子邮件发送给另一方,效率高而且花费小。,数字签名的概念由Diffie和Hellman于1976年提出,目的是通过签名者对电子文件进行电子签名,使签名者无法否认自己的签名,同时别人也不能伪造,实现与手写签名相同的功能,具有与手写签名相同的法律效力。由于数字签名技术在现在和未来社会里对政府、企事业、一般团体和个人的重要影响,世界各国都加强了对它的研究。,1994年美国政府正式颁发了美国数字签名标准DSS(Digital Signature Standard)1995年我国也制定了自己的数字签名标准(GB15
3、851-1995)2004年我国颁发中华人民共和国电子签名法,数字签名与手工签名的区别数字签名数字的,因消息而异手工签名模拟的,因人而异,数字签名与消息认证的区别数字签名第三者可以确认收发双方的消息传送消息认证只有收发双方才能确认消息的传送,认证数据完整性不可抵赖性大型网络的公钥证书中,数字签名的应用,7.2 数字签名的原理及分类,在RSA加密算法中,假如用户Bob的参数选取简单写为n=pq,de1mod(n),则e,n为公开密钥,d,n为秘密密钥。对于一个秘密密钥d,n,在满足de1mod(n)的条件下,只有唯一的e,n与之对应。如同在介绍RSA加密算法时所提及的那样,一个用户的公钥会在较长
4、时间内保持不变,故我们可以说,在一定时间内,e,n表示了秘密密钥d,n的持有者的身份。如果秘密密钥d,n的持有者Bob声明某个信息m并放于公共媒介如网络之上,那么其他人如何确定这个消息就是他发布的原信息而没有被其他人更改过呢?也就是如何确定消息的完整性呢?我们可以通过下面这种方式达到目的。,让消息发布者Bob先计算smd mod n,然后把s附于消息m之后,一起放到公共媒介上。因为大家都知道e,n唯一代表了消息发布者Bob的身份,故可以通过计算mse mod n成立与否,来判定消息是不是Bob所发,以及消息是否被篡改。因为Bob是秘密密钥d,n的唯一持有者,只有他才能通过smd mod n计算
5、出s的值来。其他人如果想算出s的值,他必须要能破解大数分解问题才行。,7.2.2 数字签名的分类,当前,数字签名应具有的性质(1)收方能确认或证实发方的签字,但不能伪造;(2)发方发出签名后的消息,就不能否认所签消息;(3)收方对已收到的消息不能否认;(4)第三者可以确认收发双方之间的消息传送,但不能伪造这一过程;(5)必须能够验证签名者及其签名的日期时间;(6)必须能够认证被签名消息的内容;(7)签名必须能够由第三方验证,以解决争议。,注:数字签名功能包含了认证的功能。,按数字签名的所依赖的理论基础分,主要可以分为:(1)基于大数分解难题的数字签名,如7.3节及7.6节介绍的例子;(2)基于
6、离散对数的数字签名,如7.4节介绍的DSA;(3)基于椭圆曲线离散对数的数字签名,这类签名往往由基于离散对数的数字签名改进而来。近年来,随着密码理论的发展,人们也提出了基于双线性对的数字签名等。,从数字签名的用途分,可以把数字签名分为普通的数字签名和特殊用途的数字签名。普通的数字签名往往可以和身份认证相互转换 特殊用途的数字签名,如盲签名、代理签名、群签名、门限签名等,多是在某些特殊的场合下使用。盲签名通常用于需要匿名的小额电子现金的支付,代理签名可以用于委托别人在自己无法签名的时候(如外出旅游)代替签名等。这部分内容请参考7.5节。,7.3 数字签名算法,在本节中,我们介绍比较经典的数字签名
7、算法:一个是RSA签名算法 一个是ElGamal签名算法 RSA签名算法提出的时间比较早,并且一直到现在,以其为基础的应用都还在使用。而ElGamal签名算法的变型算法之一,就是后来的数字签名算法(DSA)。,7.3.1 RSA数字签名,(1)参数选择 选择两个满足需要的大素数p和q,计算n=pq,(n)=(p-1)(q-1),其中(n)是n的欧拉函数值。选一个整数e,满足1e(n),且gcd(n),e)=1。通过de1mod(n),计算出d。以e,n为公开密钥,d,n为秘密密钥。,1RSA数字签名描述,(2)签名过程 假设签名者为Bob,则只有Bob知道秘密密钥d,n。设需要签名的消息为m,
8、则签名者Bob通过如下计算对m签名:smd mod n(m,s)为对消息m的签名。Bob在公共媒体上宣称他发布了消息m,同时把对m的签名s置于消息后用于公众验证签名。,(3)验证过程。公众在看到消息m和对其签名s后,利用Bob的公开验证密钥e,n对消息进行验证。公众计算:mse mod n是否成立,若成立,则Bob的签名有效。公众认为消息m的确是Bob所发布,且消息内容没有被篡改。也就是说,公众可以容易鉴别发布人发布的消息的完整性。,2对上述RSA签名算法的一个攻击,前面所描述的RSA签名算法是有缺陷的。假设攻击者Eve在得到Bob的两次对消息的签名后,很容易实现伪造。若已知:(1)Bob对消
9、息M1的签名为S1,即S1M1d mod n;(2)Bob对消息M2的签名为S2,即S2M2d mod n;则攻击者Eve可以构造消息M3=M1*M2的签名S3,S3=M3d=(M1*M2)dmodnS2*S1 虽然说在已知M1、M2的情况下,M3往往只是一个数值,一般来说是没有意义的,但不排除有意义的可能性,故导致了算法的不安全。,3对上述RSA签名算法的改进,假设公开的安全哈希函数为H(),参数选择如前,其签名过程和验证过程如下:(1)签名过程 设需要签名的消息为m,签名者Bob通过如下计算对其签名:sH(m)d mod n(m,s)为对消息m的签名。(2)验证过程 在收到消息m和签名s后
10、,验证H(m)se mod n 是否成立,若成立,则发送方的签名有效。,数字签名的步骤(数字签名与验证过程),第一步:将消息按散列算法计算得到一个固定 位数的消息摘要值。,在数学上保证:只要改动消息的任何一位,重新计算出的消息摘要就会与原先值不符。这样就保证了消息的不可更改。,第二步:对消息摘要值用发送者的私有密钥加密,所产生的密文即称数字签名。然后该数字签名同原消息一起发送给接收者。第三步:接收方收到消息和数字签名后,用同样的散列算法对消息计算摘要值,然后与用发送者的公开密钥对数字签名进行解密,将解密后的结果与计算的摘要值相比较。如相等则说明报文确实来自发送者。,数字签名与验证过程图示,当M
11、3=M1*M2时,H(M3)=H(M1)*H(M2)一般不成立,有效的防止了这类攻击方法。可以看到,通过使用哈希函数,有效防止了对签名的伪造,增强了签名算法的安全性,这也是在很多签名算法中使用哈希函数的原因之一。,7.3.2 ElGamal数字签名,ElGamal签名算法也是基于离散对数难题的,于1985年提出,其变型之一成为美国国家标准技术研究所(National Institute of Standards and Technology,简称NIST)提出的DSA(digital signature Algorithm)算法的基础。,2对于ElGamal签名算法的理解,需注意:,(1)这个
12、方案还是存在一定的不足。比如,对于消息没有用哈希函数进行处理,签名容易被伪造。(2)签名时所使用的随机值k不能泄露,否则攻击者可以计算出签名的私钥。通过变换(m-x)k-1mod(p-1),可知x(m-k)-1 mod(p-1)。,(3)对于两个不同的消息签名时,不要使用相同的k,否则容易求得k的值,从而知道签名者的私钥。通过对上面两个算法的学习,我们可以看到,数字签名的一个重要作用,就是保证了被签名文档的完整性。一旦被签名的文档内容发生了改变,则通不过验证,从而防止了文档被篡改和伪造;而且,签名是与文档内容紧密联系的,这样,对一个文档的签名,如果复制到另外一个文档上,就通不过验证,使得签名对
13、该文档无效。,7.4 数字签名标准(DSS),1991年8月,NIST提出将数字签名算法(DSA,Digital Signature Algorithm)用于数字签名标准(DSS,Digital Signature Standard)中。由于RSA算法及签名的广泛使用等各种原因,使得DSS的出现引起了很多的争议。1994年,在考虑了公众的建议后,该标准最终颁布。,7.4.1 DSA的描述,1算法的参数,p是L比特长的素数,L的长度为512到1024且是64的倍数。q是160比特长且为p-1的素因子。gh(p-1)/q mod p,其中h,g是整数,1hp-1,且要求g大于1。x是签名者的私钥,
14、由签名者选取的随机数,要求是小于q的正整数;ygx mod p为签名者的公钥。选择安全散列算法H(),标准中指定为SHA。签名者公开(p,q,g,y)及安全散列算法H(),保密x。,DSA的安全性是基于求解离散对数困难性的基础之上的,并使用了安全散列算法。它也是Schnorr和ElGamal签名算法的变型。,对于DSA算法,人们有一些批评意见,比如认为验证比签名快,q的长度160比特太短,不能用于加密和分配密钥等。另外,由于DSA算法是ElGamal签名算法的变型,故所有对ElGamal签名算法的攻击,也可以用于对DSA算法的攻击。不过就已有的攻击来看,DSA算法还是安全的。与RSA数字签名算
15、法比较,DSA在管理上有一个优点:对于RSA数字签名算法,每个用户都要有不同的公钥,故针对每个用户,都要去产生大的素数p和q,去计算d;而对于DSA算法,管理机构只需要计算一次p,g,q(通常又叫全局公开钥),每个用户只需要选择私钥x,然后计算公钥y(通常又叫用户公钥)。为什么?,7.4.2 DSA举例,对于DSA签名算法的举例,如果在例子中采用了对消息进行消息摘要值的计算H(m),大数的运算容易让初学者望而生畏,我们在这里采用小的整数代替H(m)。如果读者关心在算法中使用了消息摘要的例子,可以参看DSA的标准fips-186.标准中提到了用Miller Rabin素性检测算法产生素数,用AN
16、SI X9.17产生随机数,以及其他参数的选取等。,假设q=101,p=78*101+1=7879,h=19,则g=1978 mod 7879367 取x=69,则ygx mod p=36769 mod 78791292。假设想签名的消息为m=3456,且选择的随机值为k=27,可以计算k-115mod101。故可以算出签名为r(gk mod p)mod q=(36727 mod 7879)mod 1016797 mod 10130 s(k-1(m+xr)mod q=(15(3456+6930)mod1 0170 可以得到对m的签名为(30,70)。,验证签名:ws-1 mod q=70-1
17、mod 10113 u1mw mod q=345613 mod 10184 u2rw mod q=3013 mod 10187 v(gu1yu2mod p)mod q=(36784129287 mod 7879)mod 101(24561687 mod7879)mod 1016797 mod 10130 v=r,因此签名是有效的注:可以看到,签名和验证过程中的运算量是很大的,其中最主要的运算集中在模幂运算上,而且上面的举例中,素数的取值也是比较小的,这些运算可以通过简单编程实现。如果是按标准中的取值,模幂运算及大数的处理对初学者来说还是有挑战性的。,7.5 其他专用数字签名方案,针对实际应用中
18、大量特殊场合的签名需要,数字签名领域也转向了针对特殊签名的广泛研究阶段。(1)盲签名 用户需要让签名者对明文消息文件进行数字签名,而又不希望签名者知晓明文消息文件的具体内容,这就需要盲数字签名,简称盲签名(Blind Signature)。盲签名是一种特殊的数字签名方法,相对于一般的数字签名而言还应当具有下列2个特性:盲性:所签消息的内容对签名人是盲的,即签名人签名时不能看见消息的具体内容;不可追踪性:即使在盲签名公开后,签名者仍然不能跟踪消息-签名对,即不能把签名和其在签名时的看到的信息联系起来。盲签名主要用于基于Internet的匿名金融交易,如匿名电子现金支付系统、匿名电子拍卖系统等应用
19、中。,(2)门限签名:在有n个成员的群体中,至少有t个成员才能代表群体对文件进行有效的数字签名。门限签名通过共享密钥方法实现,它将密钥分为n份,只有当将超过t份的子密钥组合在一起时才能重构出密钥。门限签名在密钥托管技术中得到了很好的应用,某人的私钥由政府的n个部门托管,当其中超过t个部门决定对其实行监听时,便可重构密钥,实现监听。(3)代理签名 1996 年,Mambo、Usuda 和Okamoto提出了代理签名的概念。代理签名允许密钥持有者授权给第三方,获得授权的第三方能够代表签名持有者进行数字签名。代理签名相当于一个人把自己的印章托付给自己信赖的人,让他代替自己行使权力。由于代理签名在实际
20、应用中起着重要作用,所以代理签名一提出便受到关注,被广泛研究。,(4)群签名 允许一个群体中的成员以整个群体的名义进行数字签名,并且验证者能够确认签名者的身份。一个好的群签名方案应满足以下的安全性要求:匿名性,给定一个群签名后,对除了唯一的群管理人之外的任何人来说,确定签名人的身份在计算上是不可行的;不关联性,在不打开签名的情况下,确定两个不同的签名是否为同一个群成员所做在计算上是困难的;防伪造性,只有群成员才能产生有效的群签名;可跟踪性,群管理人在必要时可以打开一个签名以确定出签名人的身份,而且签名人不能阻止一个合法签名的打开;,防陷害攻击,包括群管理人在内的任何人都不能以其他群成员的名义产
21、生合法的群签名;抗联合攻击,即使一些群成员串通在一起也不能产生一个合法的不能被跟踪的群签名。在D.Chaum和E.van Heyst提出群数字签名的定义,并给出了四个实现方案后,由于群签名的实用性,人们对群签名加以了更加广泛的研究。提出了分级多群签名、群盲签名、多群签名、满足门限性质的群签名、前向安全的群签名等。,(5)前向安全的数字签名方案 普通数字签名具有如下局限性:若签名者的密钥被泄漏,那么这个签名者所有的签名(过去的和将来的)都有可能泄漏,前向安全的数字签名方案主要思想是当前密钥的泄露并不影响以前时间段签名的安全性。在提出以上这些签名之后,研究者们根据不同的需要,又给出了一些综合以上性
22、质的签名,如前向安全的群签名、盲代理签名、代理门限签名、代理多重签名、公平盲签名等。,7.6 盲签名方案,1983年,Chaum提出了盲签名概念,在此基础上提出了一个盲签名方案,并指出盲签名应该满足如下两个性质:(1)盲性,所签消息的内容对签名人是盲的,即签名人签名时不能看见消息的具体内容;(2)不可追踪性,即使在盲签名公开后,签名者仍然不能跟踪消息-签名对,即不能把签名和其在签名时的看到的信息联系起来。一般来说,盲签名的协议有如下几个步骤:初始化过程,盲化过程,签名过程,脱盲过程,验证过程。,7.6.1 基于整数分解难题的盲签名,1RSA盲数字签名描述,(1)参数选择 选择两个满足需要的大素
23、数p和q,计算n=pq,(n)=(p-1)(q-1),其中(n)是n的欧拉函数值。选一个整数e,满足1e(n),且gcd(n),e)=1。通过de1mod(n),计算出d。以e,n为公开密钥,d,n为秘密密钥。选择安全的单向hash函数h()。仍然把Bob作为签名者,则Bob知道秘密密钥d,n;所有人都知道公开密钥e,n和算法中选择的hash函数h().,(2)盲化过程 设需要签名的消息为m,请求签名者Alice随机选择一个整数r作为盲化因子,然后进行如下计算:reh(m)mod n,然后发送给签名者Bob。(3)签名过程 Bob在收到后,计算 tdmod n,然后把t发送给Alice。(4)
24、脱盲过程 Alice接收到t后,计算str-1mod n.就得到了消息m 的签名(m,s)。(5)验证过程 通过如下计算,任何人都可以验证签名的有效性:seh(m)mod n是否成立,若成立,则发送方的签名有效。,下面来体会一下这个签名方案为什么叫做盲签名方案。签名者看到的信息是,根据,e,n,签名者显然不能计算出h(m)来,因为还有一个变量r(盲化因子),即所签消息的内容对签名人是盲的,即签名人Bob签名时不能看见消息的具体内容;在Alice得到Bob的签名后,Bob即使看到了自己的签名(m,s),仍然不能把它与签名时的联系起来,即盲签名的第二个性质,不可追踪性。,7.6.2 基于离散对数难
25、题的盲签名,基于离散对数难题的盲签名出现的时间相对比较晚。1994年,J.Camenisch在DSA和Nyberg-Rueppel方案的基础上,各提出了一个盲签名方案。后来,随着研究进展,出现了强盲签名和弱盲签名的分化,再后来出现了跟其他签名结合的签名方案,如盲代理签名,盲群签名等。下面选择Schnorr盲签名算法来学习基于离散对数难题的盲签名。,可以看到,在该算法中,同样满足盲签名的两个特征,即签名者在签名时不知道所签消息的内容,事后即使看到了签名(m,c,s),也不能把它与签名时收到的消息v联系起来,从而实现了盲签名。,7.6.3 盲签名的应用,著名密码学家David Chaum 1982
26、 年首次提出了利用盲签字实现电子现金的方法,DigiCash 是Divid Chaum 发起的提供电子支付系统的专业公司,eCashTM是DigiCash开发的用软件实现的第一个完全匿名的在线电子现金系统,它的基本算法是RSA 盲签名算法。1995 年Mark Twain 银行就开始发行Internet 网上电子现金。一个电子现金支付系统通常包括三个参与方:银行,电子现金支付者,电子现金接收者。在电子货币支付时,电子现金支付者从银行取出他的电子货币,然后将电子货币支付给接收者,接收者将收到的电子货币存入银行。其关系可以用下页图表示,其中箭头方向表示了电子货币的流向。,1eCashTM系统相关的
27、参数,设银行的签名公钥为e,支付公钥PK bank,秘密钥为d,模为n,采用安全单向函数为h(.).h(.)的使用使伪造电子现金的变得不可行 银行的公开信息是e,n,h(.),支付公钥PK bank;秘密信息是d,p,q,n=p*q,p,q 是安全素数,使得分解大整数n是困难的。系统假设用户Alice已经在银行里存了一笔钱在账户NA上以备提取。,2电子现金提取协议 这里使用的是一个单位面值的电子现金,即对给定消息m,约定h(m)的e次根,即d次幂值为一个单位面值。用户提取电子现金的协议如下:(1)Alice选取随机数r,serial#,计算b re*h(serial#)modn,发送b,账号N
28、A和身份IDA给银行。其中serial#表示选取的电子现金的面值,这里仅指一个单位面值;(2)银行验证身份IDA的合法性,若合法,计算Bbdmodn,在用户账户上减掉一个单位面值的电子现金,发送B给Alice;(3)Alice计算SB/r mod n。于是用户Alice获得了银行发行一个的单位面值的电子现金Coin=serial#,S。在这里使用了盲签名技术,实现了用户Alice的电子现金的不可追踪性。,3支付协议,任何人如果知道某个没有花费的Coin,就可使用。用户支付Coin时,不能让接收者看到Coin.eCashTM 为了保证这点,银行使用了一个用来完成支付的公钥PK bank,用户支付
29、时用PK bank对Coin加密,保证了只有电子现金拥有者在申请后和银行在电子现金拥有者完成支付时才能看到它。假定电子现金支付者和接收者商定了支付银行bankID、支付金额amount、币种currency、电子现金个数nCoins、时戳timestamp、接收者身份merchant_Ids与其银行帐户对应、交易描述description以备将来解决支付者和接收者的可能争议,支付者的秘密随机数payer_code也用来解决支付者和接收者的可能争议。,Payment_inf=bank ID,amount,currency,nCoins,timestamp,merchant-Ids,h(descr
30、iption),h(payer_code)在支付过程中,银行不能知道description的信息,只能知道description的hash值。具体支付协议如下:(1)电子现金支付者计算 payment=payment_inf,nCoins,merchant_IdsPKbank 发送payment到电子现金接收者。其中nCoins,merchant_IdsPKbank表示用PKbank加密nCoins,merchant_Ids。(2)电子现金接收者验证payment_inf,发送payment给银行;(3)银行验证nCoins,merchant_Ids PKbank确信Coins没有重复花费,把
31、nCoins列入已花费的coins,给merchant_Ids账户上加上一定金额,否则支付失败。,不可否认签名方案,1989年Chaum和Antwerpen提出了不可否认签名方案。其实质是在没有签名者合作时不可能验证签名,从而可防止复制或散布签名消息。显然,这一签名方案的目的是阻止签名文件的随便复制、任意散布。这在电子出版物的知识产权保护方面具有相当的应用前景。,补充:,(1)不可否认签名的基本原理,下面先举一个例子,比如向别人借钱,必须在借条上签字。也许有一天,提前向你索要钱款,或者与对方发生了矛盾,为此防止你的借条到处散布,并验证给人们看,确实证明你向别人借了钱,使你受到了巨大的伤害或损失
32、。这不是你希望发生的。所以希望借条必须有其他人的合作才能验证。如果是没有签名的借条(就不能验证),等于一张废纸,因而没有人会相信展示的借条,你的设想确实达到了他的目的;但是也会担心任何时候对方都不合作,即使在法官面前也不合作,从而就没有办法验证借条的真实性,这样就不能讨回借款了。,这样一队矛盾怎样才能解决呢?不可否认签名就借用了法律的原理来实现这一目标。如果从法律的角度来分析问题:(1)如果拒绝合作,则认为提供的是事实;(2)如果用虚假方法验证,算法可以实现的行为,也判定提供的是事实;(3)如果提供的借条是伪造的,则也可以发现并证明,从而否认提供的借条。由此可知,不可否认签名主要由三个部分组成
33、:签名算法、验证算法和不可否认算法。下面给出Chaum-Antwerpen不可否认签名算法。,(2)不可否认签名算法 算法描述,2023/9/28,53,验证原理及不可否认原理,所以,一致性检验不但可以检查签名者的非法验证行为,还可以证明其验证行为的真实性,因而它可以检查出伪造的签名。,防失败签名方案,防失败签名是一种强化安全性的数字签名,即使攻击者分析到用户的密钥,也难以伪造该用户的签名,而签名方对自己的签名也是难以抵赖的。下面介绍由Van Heyst和Pederson提出的防失败签名方案。,思考题,1数字签名的原理是什么?2数字签名有哪些分类?3简述RSA数字签名算法与RSA公钥加密体制有什么差别与联系?4以小的整数实现DSA签名算法的参数选取,数字签名和签名过程,以理解DSA签名算法。5程序实现RSA签名算法和DSA签名算法。,