山东大学信息安全课件第5章数字签名

1、第5章 数字签名5.1数字签名l政治、军事、外交、商业以及日常事物经常出现需要签名的场合。签名的作用是核准后认可并且生效。随着信息时代的到来，人们希望能通过网络信息传输对文件、契约、合同、信件、帐单等进行数字签名(DigitalSignature)，从而代替面对面的手写签名。实际上数字签名是一种证明签名者身份和所签署内容真实性的一段信息。手写签名与数字签名的区别：手写签名与数字签名的区别：1）手写签名是所签的文件的物理组成部分。数字签名必须与所签文件捆绑在一起2验证手写签名通过与标准签名比较或检查笔迹来实现，伪造签名比较容易。数字签名通过公开的验证(Verification)算法。好的数字签名(Signing)算法应该使得伪造(Forgery)签名十分困难3）手写签名不易复制。数字签名是一个二进制信息，复制十分容易，所以必须防止数字签名重复使用一般，数字签名算法必须满足：l签名者事后不能否认自己的签名l任何他人不能伪造签名l当双方为签名真伪发生争执时，可以由第三方解决争端数字签名算法必须满足的条件数字签名算法必须满足的条件l按目的可以把数字签名分成普通数字签名和特殊目的的数字签名（如不

2、可否认签名、盲签、群签等）。前者由签名算法(DigitalSignatureGenerationAlgorithm)和验证算法(DigitalSignatureVerificationAlgorithm)组成。而后者还需要有附加的部件。l按验证方法可分成：在验证时需要输入被签信息和在验证中自动恢复被签信息两类l按是否使用随机数可分成：确定的和随机的两种签名算法签名算法的分类签名算法的分类1）在在把把被被签签的的数数据据格格式式化化(FormattingData)成成可可签签的的消消息息之之后后，签签名名者者使使用用签签名名算算法法生生成成数数字字签签名名。接接收收者者接接到到数数字字签签名名使使用用验验证证算算法法验验证证签签名名的的真真实实性。最后从消息恢复成为数据性。最后从消息恢复成为数据(RecoveringData).2）在在信信息息安安全全中中，数数字字签签名名有有许许多多应应用用如如认认证证、数数据据完完整整性性和和不不可可否否认认性性。主主要要的的应应用用之之一一是是大大型型网网络络中中的的“公公钥钥证证书书”。所所谓谓证证书书是是由由一一个个可可信信第第三三方方(Tru

3、stedThirdParty,简简称称TTP)把把用用户户身身份份标标识识与与用用户户公公钥钥绑绑在在一一起起的的一一种种手手段段。其其他他用用户户不不需需要要TTP帮助，自己就可以认证一个公钥。帮助，自己就可以认证一个公钥。数字签名的应用数字签名的应用5.2 RSA数字签名数字签名 5.2.1RSA数字签名算法数字签名算法密钥生成密钥生成p,q是两个不同的大素数，n=pq，任取b满足gcd(b,(n)=1。求b模的(n)逆a，即ab=1mod(n)n,b是签名者的RSA公钥,p,q,a是签名者的RSA私钥,数字签名算法数字签名算法:Sigk(x)=xamodn验证签名算法验证签名算法:Verk(x,y)=truex=ykmodn数字签名数字签名验证签名算法验证签名算法 信息发送者除了签名表示对此信息负责外还要求保密传送该信息，可以将消息x和签名用对方公钥加密后传送。过程如下图所示发送者接收者公钥nAbA,公钥nBbB,私钥pAqAaA，私钥pBqBaB计算z=(xaAmodnA)bBmodnB用私钥解密x和z，求出A的签名 和x并验证1）由于RSA签名能自动恢复被加密的消息。上面不必

4、计算和传送。2）这里的顺序是十分重要的。如果先加密再签名，则可能受到伪装攻击。假设发送者发送z=(xbBmodnB)aAmodnA。敌手C截获z，利用A的公钥和自己的私钥在不知道明文的情况下计算自己对密文的签名发给接收者B。B将会认为消息是C发送过来的。注意：l任何人都可以伪造某签名者对于随机信息x的签名y,。其方法是先选y，用某签名者的公钥n,b计算x=ybmodn,y就是某签名者对信息x的签名l若敌手掌握某签名者对信息x1,x2的签名分别是y1,y2，则可以伪造x1x2的签名y1y2l对长的信息签名要分成若干长为log2n的组分别进行签名，运算量极大。（可通过使用哈希函数解决）RSARSA签名算法的弱点签名算法的弱点5.2.2 RSA的重新分组问题的重新分组问题前面讲过，通常会把RSA签名经加密后传给对方。对方使用自己的私钥和发送方的公钥可以直接恢复信息。这里需要认真对待模数大小的问题。令A的公钥nA,bA，B的公钥nB,bB且 nAnB 。A加密一个信息传送给B，有可能B不能恢复出原来的消息。例如：A计算(55465219),发送给BB计算出现不能恢复明文的概率为(1)选一个 位

5、的随机素数p;(2)选另一个素数满足,使得解决这个问题的方法有两个。第一个方法是为每个实体生成两组公私钥对，分别用于加密和签名。公钥中的两个模数，加密模数有t+1位，签名模数为t位。显然这个方法要付出空间代价。第二个方法是规定模数的形式，,使出现上述问题的概率减小.具体做法是:,例如k=3,n是12位二进制数取是6位二进制数取q=59.假设 具有上述形式， 是A对x的签名，y 。这时并不能保证B正确解密，只是把不能正确解密的概率降到足够小。这里有两种可能:1）y的最左一位为0，则y的形式必为显然y小于具有这种形式的其它模数。2）y的最左一位为1，因ynA，所以1后面的位全为0。这样的有可能大于对方的模数。但这样的y在整体中只占2-k。当k比较大时（如k=100），这个概率可以忽略不计。5.3改进的改进的Rabin签名算法签名算法 公钥生成公钥生成1）选随机素数p=3mod8，q=7mod8，令n=pq，称n是Williams数。2）n是公钥，私钥d=(n-p-q-5)/8签名算法签名算法1）计算2）计算Jacobi数J=3）当J=1时，对的签名是modn当J=-1时，对的签名是modn

6、验证算法1）得到签名者的公钥n2）计算3)4)验证是否以0110结尾。如果不是，则拒绝。否则s是对明文m的Rabin签名。注：1）这里有 。从 知当时且，故当是，有故。2）使用改进的Rabin签名算法，我们从来不会对Jacobi数为-1的信息v签名。否则，。而v2是模n的二次剩余，。又，所以不成立。由此可推断或q，即导致分解n。例如：要签名的信息m=12，对信息m的Rabin签名。下面验证签名。计算，因，它的二进制形式为：11000110，明文为S是对明文m的Rabin签名。5.4EIGamal数字签名数字签名1)密钥生成密钥生成是的本原元素，A选择，.是公钥，是私钥2)签名算法签名算法A选择秘密随机数，其中3)验证算法验证算法对于EIGamal数字签名算法有下面两种伪造攻击1)欺骗者O同时选择计算。不难证明（）是A对消息x的合法签名。2）O已知()是A对消息x的合法签名，利用它再伪造一批A的签名。选择整数。计算()不难证明是A对消息的合法签名可以通过事先对消息进行散列来抵抗上述攻击在使用ElGamal签名时特别要注意1）不能泄露随机数k。如果泄露随机数k，可由求出密钥。2）不能使用相

7、同的k去签两个不同信息。假如使用相同的k对消息x1,x2的签名分别是 ,。由签名算法得知,又得出，令，由得到d个k的后选值。通过验证确定唯一的k值。再由求出。5.5数据签名标准数据签名标准DSS许多被签名的是合同、遗嘱等法律文件要在签署许多被签名的是合同、遗嘱等法律文件要在签署后许多年之后验证。考虑到技术的发展，对数字签名后许多年之后验证。考虑到技术的发展，对数字签名算法更强调安全性。算法更强调安全性。DSS（DigitalSignatureStandard）是）是EIGamal数字签名算法的一个变形。数字签名算法的一个变形。1991年年8月月30日第一次提出。它的修改版于日第一次提出。它的修改版于1994年年5月月19日公布，并于同年日公布，并于同年12月月1日采纳为美国的数字签名标日采纳为美国的数字签名标准。当选择准。当选择p是是512位的素数时，位的素数时，ElGamal签名算法的签名算法的大小是大小是1024位。位。DSS中通过又引入一个中通过又引入一个160位的素数将位的素数将签名的大小减少为签名的大小减少为320位，从而减少存储空间和传输带位，从而减少存储空间和传输带宽。宽

8、。令p是512位的素数，以使 中的离散对数是困难问题，q是160位的素数且任选，计算，如果，则 是q阶元。取秘密指数a，计算是公钥，是私钥。签名算法签名算法：选取随机数 k， 计算若：，（概率只为：），则重新选择k是对消息x的签名验证算法验证算法：计算若，则接受是对消息x的签名。否则拒绝。具体实施中的细节： 1） 可以事先选好一批 计算出相应的 和2)对x的签名可以改为对哈希函数H(x)的签名3)密钥生成中参数，p是长度在5121024之间而且长度是64倍数的素数且。生成p,q的方法如下：令，H(x)是哈希函数，输入长度，输出长度160位。（1）用随机序列生成器长度为g（大于160）的序列S， 计算（2）计算 , 将其最高位置“1”称为q。检测q是否是素数，如果不是转回（1）。（3）令i=1,j=2.（4）如果 ，则转回（1）。（5）计算令其中，令，从而（6）如果 ，则转到（8）。 （7）i=i+1,j=j+n+1;转到（4）。（8）对p进行素数测试。如果是素数，则返回(p,q)。否则转到(7). 在RSA中验证算法比签名算法快，而DSS中签名算法比验证算法快。由于smart卡计算能力

9、有限，所以采DSS签名算法较为有利.5.6 一次性签名一次性签名一次性签名是至多能签一个消息的签名方案。如果签多个消息，敌手就可以伪造签名。这里每签一个消息就需要一个新的公私钥对。一次性签名方案的签名和验证都十分有效。签名方案签名方案密钥生成单向函数Lamport 在Y中随机选取为私钥计算，及单向函数为公钥。签名算法对明文的签名是验证算法若包含在公钥中， 则签名合法例如：素数p=7879,3是的本原元素。定义，令k=3.私钥公钥及对消息 x= 011 的签名为（4285，2467，735）。对方验证时计算 .它们都在公钥中，所以签名合法。 对手虽然不能从 求出 ，但是用这个方法对两个不同的消息签名时，对手就能伪造出另一个消息的签名。例如上例中对手知道011和101的签名分别是 和，显然和分别是111和001的签名。5.7 失败停止数字签名Fail-stopFail-Stop数字签名最早是1990年由B.Pfitzmann&M.Waidner提出的。它允许实体A证明“声称是A的签名”实际上是伪造的签名。其做法是展示“该签名机制所基于的假设已受到威胁”。Fail-Stop数字签名的好处在于

10、即使一个非常强的对手可能伪造一个签名，但可以察觉出是伪造的，与此同时不再使用该签名机制。所以称为“失败而后停止”更恰当一些。Fail-Stop数字签名应具有如下性质: (1) 如果签名者依据该机制签署一个消息，则验证者能验证签名并接受它. (2)伪造者没有指数运算能力就不可能构造“能通过验证算法的一批签名。(3)如果伪造者以高概率成功地构造出一个能通过验证算法的签名，那么真正的签名者可以给出“该签名是伪造的”的证明。(4)签名者不能自己构造出一些签名，而后又断言他们是伪造的。以次保证接收者的安全Fail-Stop数字签名由签名算法、验证算法、“伪造”证明算法组成。其中“伪造”证明算法是对伪造签名的一种证明。 1992年E.Heyst & T.P.Pedersen 提出的 Fail-Stop数字签名算法，它是一次性签名，即一个密钥只能用来签名一次。该数字签名的基本思想是：每个可能的公钥有许多私钥与之对应，然而签名者只知道其中之一，并用它作签名。窃听者搜集被签名的信息，试图从中发现签名者的私钥。由于私钥很多，所以成功的概率可以忽略不计。窃听者使用他自己生成的密钥伪造一个信息的签名，这个签名

《山东大学信息安全课件第5章数字签名》由会员东***分享，可在线阅读，更多相关《山东大学信息安全课件第5章数字签名》请在金锄头文库上搜索。