第6章 数字签名技术1.ppt

第6章数字签名,人们通过网络支付费用、买卖股票，为了保证网上商务活动的安全，需要信息安全中一个很重要的安全机制数字签名。举个例子说：用户A通过网络发送一条消息，告诉银行从用户A的账户上给用户B支付5000元。1、银行如何知道这条消息是由用户A发送的？2、如果事后用户A否认他曾经发送过这条消息，或声称他的支付请求是1000元，而不是5000元，银行如何向公证机关证明用户A确实发送过这条消息？解决办法之一：用户A对他的请求“让银行从用户A的账户上给用户B支付5000元”进行签名。,第6章数字签名技术,6.1数字签名概述数字签名的特性1.数字签名的目的和要求数字签名的目的是保证信息的完整性和真实性，即消息内容没有被篡改，而且签名也没有被篡改，消息只能始发于所声称的发方。一个完善的签名方案应满足以下三个条件：签名者事后不能否认或抵赖自己的签名。其他任何人均不能伪造签名，也不能对接收或发送的信息进行篡改、伪造和冒充。若当事双方对签名真伪发生争执时，能够在公正的仲裁者面前通过验证签名来确定其真伪。,第6章数字签名技术,sig：MKS，ssigk(m),数字签名方案的描述,数字签名方案的定义是：设M是消息的有限集合，S是签名的有限集合，K是密钥的有限集合，则数字签名算法是一个映射：,验证算法也是一个映射：,为了实现数字签名要求，当事双方应首先达成有关协议，数字签名协议中包括签名的产生、验证及纠纷的解决方法等内容。一般来说，数字签名方案还应满足以下要求：签名是不可伪造的。签名是不可抵赖的。签名是可信的。签名是不可复制的。签名的消息是不可篡改的。,一个数字签名方案由两部分组成：带有陷门的数字签名算法（SignatureAlgorithm）和验证算法（VerificationAlgorithm）。,第6章数字签名技术,归纳起来，一个数字签名方案的应用一般包括三个过程：（1）系统初始化过程：产生数字签名方案中用到的所有系统和用户参数，有公开的，也有秘密的。（2）签名产生过程：在此过程用户利用给定的签名算法和参数对消息产生签名，这种签名过程可以公开也可以不公开，但一定包含仅签名者才拥有的秘密信息（签名密钥）。（3）签名验证过程：验证者利用公开的验证方法和参数对给定消息的签名进行验证，得出签名的有效性。,五元组M，S，K，sig，ver就称为一个签名算法。,数字签名的执行方式,数字签名的执行方式有两类：直接数字签名方式和具有仲裁的数字签名方。,1.直接方式,直接方式是指数字签名的执行过程只有通信双方参与，并假定双方有共享的秘密密钥，或者接收一方知道发方的公开密钥。,直接方式,(1)AB:EKRaM提供了认证与签名：只有A具有KRa进行加密;传输中无法被篡改；需要某些格式信息/冗余度；任何第三方可以用KUa验证签名,(1)AB:EKUbEKRa(M)提供了保密(KUb)、认证与签名(KRa)：,直接方式,(2)AB:M|EKRaH(M)提供认证及数字签名-H(M)受到密码算法的保护；-只有A能够生成EKRaH(M),(2)AB:EKM|EKRaH(M)提供保密性、认证和数字签名。,直接数字签名有一些共同的缺点：方案的有效性依赖于发送方秘密密钥的安全性。,仲裁数字签名,引入仲裁者。通常的做法是所有从发送方X到接收方Y的签名消息首先送到仲裁者A，A将消息及其签名进行一系列测试，以检查其来源和内容，然后将消息加上日期并与已被仲裁者验证通过的指示一起发给Y。仲裁者在这一类签名模式中扮演敏感和关键的角色。所有的参与者必须极大地相信这一仲裁机制工作正常。（trustedsystem）,第6章数字签名技术,方案一对称加密，仲裁者可以看到消息内容,该方案的前提是每个用户都有与仲裁者共享的秘密密钥。数字签名过程如下：(1)SA：M|EKSAIDS|H(M)(2)AR：EKARIDS|M|EKSAIDS|H(M)|T其中E是对称密钥加密算法，KSA和KAR分别是仲裁者A与发送方S、接收方R的共享密钥，H(M)是M的散列值，T是时间戳，IDS是S的身份标识。,从上面过程中可以看出，A的存在可以解决直接数字签名可能产生的问题。这时仲裁者起着关键的作用，这必须要求：(1)发送者S必须确信仲裁者A不会泄露KSA，也不会产生虚假的数字签名；(2)接收方R必须确信仲裁者A只有在散列码正确且发送方S的数字签名被证实的情况下才发送；(3)通信双方必须确信仲裁者A能公平的解决争端。,注：该方案中消息以明文方式发送，未提供机密性保护。,第6章数字签名技术,方案二：对称加密，仲裁者不能看到消息内容,该方案的前提是每个用户都有与仲裁者共享的秘密密钥，而且两两用户间也有共享密钥。数字签名过程如下：(1)SA：IDS|EKSRM|EKSAIDS|H(EKSRM)(2)AR：EKARIDS|EKSRM|EKSAIDS|H(EKSRM)|T其中KSR是S，R的共享密钥。,本方案虽然对消息M提供了保密性，但是仍存在与方案一相同的问题：(1)仲裁者和发送方可以合谋来否认曾经发送过的消息；(2)仲裁者和接收方可以合谋来伪造发送方发的签名。,方案三：公钥加密，仲裁者不能看到消息内容该方案的前提是每个用户都能安全获取仲裁者和其它用户的公开密钥。数字签名过程如下：(1)SA：IDS|EKRSIDS|EKUREKRSM(2)AR：EKRAIDS|EKUREKRSM|T其中KRS和KRA分别是发送方S和仲裁者A的私钥，KUR是接收方R的公钥在第（1）步中，S用自己的私钥对消息M加密，来实现对消息M的签名，用R的公钥对消息M加密，来实现对M的机密性保护。采用这种方式，任何第三方（包括仲裁者A）都不知道消息M的内容。仲裁者A收到S发来的内容后，用S的公钥进行解密，并将得到的IDs与收到的IDs进行比较，从而可以判断消息是否来自发送方S。与前两种方案相比，方案三有许多优点：(1)在方案执行以前，各方都不必有共享的信息，从而可以防止合谋；(2)只要仲裁者的私钥不被泄露，任何人包括发送方就不能重放消息；(3)对任何第三方（包括A），S发往R的消息都是保密的。,第6章数字签名技术,6.2基于公钥密码体制的典型数字签名方案,RSA数字签名方案,基于RSA公钥密码体制的数字签名方案通常称为RSA数字签名方案。,RSA数字签名体制的基本算法可以表述如下：,(2)签名产生过程用户A对消息MZn进行签名，计算SA=Sig(M)=Mdmodn；其中d为签名方A的私钥。并将SA附在消息M后作为用户对消息M的签名。,(1)系统初始化过程产生两个大素数p，q；计算n=pq；随机选取一个与(n)互素的整数e作为公钥，私钥d满足ed=1mod(n)；用户A将公开公钥e与n，而私钥d，以及p，q则严格保密。,第6章数字签名技术,(3)签名验证过程假设用户B要验证用户A对消息M的签名，用户计算M=SAemodn；其中e为签名方A的公钥。并判断M与M是否相等。如果相等则相信签名确实为A所产生，否则拒绝确认该签名消息。,RSA数字签名算法如图6.1所示。,第6章数字签名技术,对于RSA数字签名方案的应用及安全性需要注意以下的几个问题：,(1)上述RSA数字签名算法采用了对整个消息进行签名的方法，由于公开密钥密码体制一般速度都比较慢，这样当消息比较长时，整个签名与验证过程都会相当的慢。,(2)RSA数字签名算法的安全性取决于RSA公开密钥密码算法的安全性（基于大整数分解的困难性）。,(3)如果消息M1、M2的签名分别是S1和S2，则任何知道M1，S1，M2，S2的人都可以伪造对消息M1M2的签名S1S2，这是因为在RSA的数字签名方案中，Sig(M1M2)=Sig(M1)Sig(M2)。,ElGamal数字签名方案,EIGamal数字签名方案是T.EIGamal在1985年发表关于EIGamal公开密钥密码时给出的两个方案之一(另外一个用于加密)。,第6章数字签名技术,1.ElGamal数字签名算法描述,(1)系统初始化过程ElGamal系统初始化过程用来设置系统公共参数和用户的密钥。系统公共参数a.选择大素数p，使得Zp中的离散对数问题为困难问题；b.选择乘法群Zp*上的一本原元。用户选择密钥每个用户选择一随机数x，且1xp1，计算,用户将x作为自己的私钥（用于签名），将y作为自己的公钥（用于签名验证）。,整个系统公开的参数有大素数p、本原元以及每个用户的公钥；而每个用户的私钥则严格保密。,(2)签名过程给定消息M，签名者A将进行如下计算：选择随机数kZp*，且k与（p1)互素；,第6章数字签名技术,(3)验证签名过程接收方B在收到消息M与数字签名(r，s)后：计算消息M的散列码H(M)；计算yrrsmodp和H(M)modp；其中y为签名方A的公钥。若两式相等，即yrrsH(M)modp则确认(r，s)为有效签名，否则则认为签名是伪造的。,用户A将（r，s）作为对消息M的数字签名，与消息M一起发送给接收方。,签名方对消息M进行散列压缩得到消息散列码H(M)，并计算:r=kmodp；s=(H(M)xr)k1mod(p1)；其中x为签名方A的私钥。,把EIGamal数字签名方案总结如图6.2所示。(见下页),2.ElGamal数字签名算法安全性,(1)EIGamal数字签名算法是一个非确定性的数字签名算法，对同一个消息M所产生的签名依赖于随机数k。(2)由于用户的签名密钥x是保密的，攻击者要从公开的验证密钥y得到签名密钥x必须求解有限域上的离散对数问题（x=log，py）。因此ElGamal数字签名算法的安全性是基于有限域上计算离散对数的困难性。,第6章数字签名技术,在签名时用的随机数r不能被泄露。(4)随机数k不能被重复使用。,例：设素数p=11，=2是Z11*上的本原元，用户A选择x=8作为自己的私钥，消息M的哈希值H(M)=5，用户A选择的签名随机数k=9，计算A用EIGamal数字签名算法对消息M的签名以及用户B对签名的验证。,数字签名标准DSS1DSA数字签名算法描述DSA的参数p是一个素数，要求2L-11。随机选择整数x作为用户的私钥，要求0xq。计算用户的公钥y=gxmodp。显然，给定x计算y是容易的，但是给定y求x是离散对数问题。在上述参数中，p、q以及g是公开的系统参数，x和y分别是用户的私钥和公钥。,第6章数字签名技术,其中H(M)是使用SHA-1生成的消息M的散列码，（r，s）就是消息M的数字签名，k-1是k模q的乘法逆元，为了安全起见，每次签名应当随机选取不同的k。若r=0或s=0则返回重新计算。,；其中x为签名方A的私钥。,(2)签名过程假设用户A要对消息M进行数字签名，然后发送给用户B.发送方A秘密选取随机整数k，0kq；发送方计算r(gkmodp)modq；,第6章数字签名技术,如果v=r则确定签名合法，可以认为收到的消息是可信的，否则消息可能被篡改。,(3)签名验证过程如果接收者收到消息M，r，s后，首先验证0rq，0sq，如果通过则计算：w=s-1modq；u1=H(M)wmodq；u2=rwmodq;,；其中y为签名方A的公钥。,定理6.2设p和q是素数且满足q|(p1)，h是小于p的正整数，g=h(p-1)/qmodp，则gpmodp=1，并且假如mnmodq，则gmgnmodp定理6.3：如果(r，s)是合法用户A采用DSA数字签名算法对消息M的签名，则一定有v=r成立。,第6章数字签名技术,DSA算法也是非确定性的数字签名算法，对消息M它的签名依赖于随机数r，这样相同的消息就可能产生不同的签名。,DSA的安全性也是基于计算有限域离散对数的困难性，鉴于有限域上计算离散对数问题的进展，一般认为512位的DSA算法无法提供较长期的安全性，而1024位的安全性值得信赖。例：假设素数q=23，p=47,并取h=17，用户A选择了x=10作为自己签名的私钥和签名随机数k=19来对消息M进行签名，消息M的哈希值H(M)=15，计算消息M的签名以及签名验证。,2DSA数字签名算法的安全性分析,第6章数字签名技术,6.3特殊数字签名方案,不可否认签名,在现实生活中，有时需要在签名者参加的情况下才能进行签名的验证，而签名者又不能否认签名。满足这个要求的数字签名称为不可否认签名方案（Undeniablesignaturescheme）。这一方案的主要目的是阻止签名文件的随便复制和任意散布。例如：某软件公司A开发的一个软件产品，公司A将软件产品和对产品的不可否认数字签名卖给用户B。B在A的参与配合下才能验证A的签名，确认产品的真实性，并得到公司A的售后技术支持。但如果用户B想把该软件产品复制后私自卖给第三方，由于没有公司A的参与，不能验证软件的真实性，从而保护了公司A的利益。,不可否认签名的概念由D.Chaum和VanAntwerpen在1989年提出。不可否认性包含两层含义：签名的证实和否定必须与签名者合作才能完成；签名者不能否认他曾经签过的签名。在不可否认签名方案中，若没有签名者的配合，签名就不能得到验证，从而防止未经签名者的授权，签名文件被复制和分发的可能；而在签名者的配合下，验证者可对数字签名进行验证。如果签名是伪造的，在签名者和验证者的配合下能证明该签名事实上是伪造的。而当一个签名通过验证，签名者不能否认签名。如果签名者拒绝参与签名验证，在法律上就认定签名者签名的事实。如果在验证过程中，签名者用虚假的方法或数据，验证算法可以发现签名者的造假行为，也可认定签名者的签名事实。如果验证者提供的签名是伪造的，则签名者也可以发现并证明，从而否认这个签名。,第6章数字签名技术,（2）签名的验证协议签名者和验证者执行交互式协议，验证协议必须具备完备性和合理性：只要签名者和验证者都是诚实的，则签名者签署的签名总是能够通过验证协议，从而被验证者接受；同时，若一个不是由签名者签署的签名，无论签名者如何狡辩，要使得签名通过验证协议，并使得验证者接受的概率是可以忽略的。