第八章 数字签名

1,上讲的主要内容,数字签名的简介基于RSA数字签名基于ElGamal数字签名Schnorr数字签名基于ECC数字签名,第八章数字签名续,主讲人：马秀文,Email：maxiuwen2001,3,数字签名的扩展,指定验证者（不可否认）签名盲签名多重签名群签名代理签名,4,前言,在数字签字的实际应用当中，一些特殊的场合往往有特殊的要求。因此需要在基本数字签名技术的基础上进行扩展，以满足这些要求。例如，为了保护信息拥有者的隐私，产生了盲签名；为了实现签名权的安全传递，产生了代理签名；为了实现多人对同一消息的签名，产生了多重签名等等。正是这些实际应用的特殊需求，使得各种各样的特殊数字签名的研究一直是数字签名研究领域非常活跃的部分并产生很多分支。,5,不可否认签名简介,普通数字签字，可以精确地对其进行复制，这对于如公开声明之类文件的散发是必须的，但对另一些文件如个人或公司信件、特别是有价值文件的签字，如果也可随意复制和散发，就会造成灾难。这时就需要不可否认签名。,6,不可否认签名简介,这类签名有一些特殊性质，其中最本质的是在无签字者合作条件下不可能验证签字，从而可以防止复制或散布他所签文件的可能性，这一性质使产权拥有者可以控制产品的散发，在电子出版系统知识产权保护中将有用场。特点：在得不到签名者配合的情况下其他人不能正确进行签名验证，即验证时，需由验证者与签名者合作才可证明其正确性。这样的签名是不允许使用者任意复制的。,7,不可否认签名的组成,不可否认签名方案由三部分组成：数字签名算法、验证协议、否认协议。否认协议(DisavowalProtocol)：在签字者合作下才能验证签字，这会给签字者一种机会，在不利于他时他“拒绝”合作以达到否认他曾签署的文件。为了防止此类事件而引入。构成签字算法的第三个组成部分，签字者可利用否认协议向法庭或公众证明一个伪造的签字确是假的；如果签字者拒绝参与执行否认协议，就表明签字事实上是真的由他签署的。,8,不可否认签名的算法（初始化）,S为签名者；V为签名的验证者；p和q是满足安全的大素数，q是p-1的大因子，g是域GF(p)的本原元；S拥有公私钥对(x,y)，其中y=gxmodp；m为待签名的文件；h是安全的哈希函数；,9,不可否认签名的算法（签名）,签名者S进行如下计算：1.2.消息m的不可否认签名是3.签名者的验证：,10,不可否认签名的算法（验证）,验证者V签名者S,11,如果不成立，这个签名是有效的（签名者没有配合），否则，这个签名是无效的。,不可否认签名的算法（不可否认）,如果上面验证没通过，验证者V做如下运算：,12,盲签名,盲数字签名是一种特殊的数字签名，当用户A发送消息m给签名者B时，一方面要求B对消息签名，另一方面又不让B知道消息的内容，也就是签名者B所签的消息是经过盲化处理的。,13,盲签名,盲签名除具有一般数字签名的特点外，还有下面两个特征：(1)签名者无法知道所签消息的具体内容，虽然他为这个消息签了名。（匿名性）(2)即使后来签名者见到这个签名时，也不能将之与盲消息对应起来。（不可跟踪性）,14,盲签名的实现过程,注：将盲变换看作是信封，盲化文件是对文件加个信封，而去掉盲因子过程是打开信封。文件在信封中时无人可读它，而在盲文件上签字相当于在复写纸信封上签字，从而得到了对真文件(信封内)的签字。,15,盲签字协议,(a)A取一文件并以一随机值乘之，称此随机值为盲因子（盲化处理）。(b)A将此盲文件送给B。(c)B对盲文件签字。(d)A以盲因子除之，得到B对原文件的签字。若签字函数和乘法函数是可换的，则上述作法成立。否则要采用其它方法(而不是乘法)修改原文件。,16,盲签字协议-安全性讨论,B可以欺诈吗？是否可以获取有关文件的信息？若盲因子完全随机，则可保证B不能由(b)中所看到的盲文件得出原文件的信息。即使B将(c)中所签盲文件复制，他也不能(对任何人)证明在此协议中所签的真正文件，而只是知道其签字成立，并可证实其签字。即使他签了100万个文件，也无从得到所签文件的信息。,17,盲签名存在问题（举例）,反间谍组织的成员的身份必须保密，甚至连反间谍机构也不知道他是谁。反间机构的头头要给每个成员一个签字的文件，文件上注明：持此签署文件人(将成员的掩蔽名字写于此)有充分外交豁免权。每个成员都有他自己的掩蔽名单。成员们不想将他们的掩蔽名单送给反间谍机构，敌人也可能会破坏反间谍机构的计算机。另一方面，反间机构也不会对成员给他的任何文件都进行盲签字，例如，一个聪明的成员可能用“成员(名字)已退休，并每年发给100万退休金”进行消息代换后，请总统先生签字。此情况下，盲签字可能有用。,18,盲签名实现的方法（举例）,假定每个成员可有10个可能的掩护名字，他们可以自行选用，别人不知道。假定成员们并不关心在那个掩护名字下他们得到了外交豁免，并假定机构的计算机为AgencysIntelligentComputingEngine，简记为ALICE。则可利用下述协议实现：(a)每个成员准备10份文件，各用不同的掩护名字，以得到外交豁免权。(b)成员以不同的盲因子盲化每个文件。(c)成员将10个盲文件送给ALICE。(d)ALICE随机选择9个，并询问成员每个文件的盲因子。(e)成员将适当的盲因子送给ALICE。(f)ALICE从9个文件中移去盲因子，确信其正确性。(g)ALICE将所签署10个文件送给成员。(f)成员移去盲因子，并读出他的新掩护名字：“TheCrimsonStreak”，在该名字下这份签署的文件给了他外交豁免权。,19,盲签名的安全性分析,这一协议在抗反间成员欺诈上是安全的，他必须知道哪个文件不被检验才可进行欺诈，其机会只有10%。(当然他可以送更多的文件)ALICE对所签第10个文件比较有信心，虽然未曾检验。这具有盲签性，保存了所有匿名性。反间成员可以按下述方法进行欺诈，他生成两个不同的文件，ALICE只愿签其中之一，B找两个不同的盲因子将每个文件变成同样的盲文件。这样若ALICE要求检验文件，B将原文件的盲因子给他；若ALICE不要求看文件并签字，则可用盲因子转换成另一蓄意制造的文件。以特殊的数学算法可以将两个盲文件做得几乎一样，显然，这仅在理论上是可能的。,20,盲签名的分类及过程,由于具有匿名性和不可追踪性的特点，盲签名能满足实际应用的许多需求，并已成为当前研究的热点。目前根据“盲”程度不同，盲签名方案通常分为强盲签名、弱盲签名两类。其中强盲签名方案应用最广，大部分场合都趋向于强盲签名的实现，弱盲签名主要立足于特殊应用需求，是强盲签名的重要补充，下面将对这两类方案进行简单的介绍。其中符号含义为：R(m)：为了文件m的内容不被泄漏而进行盲化过程得到的盲文件。Sign(R(m)：盲文件R(m)的签名。Sign(m)：去盲后得到的真实文件m的签名。,21,强盲签名,强盲签名又称为完全盲签名，它的原始定义是指签名者在文件上签名是有效的，但不能把签署文件的行为与签署了的文件相关联，即无法建立Sign(R(m)到Sign(m)的联系。正是这些特点实现了不可追踪性(untraceable)和匿名性（anonymous），也是盲签名的重要特色。它主要应用于电子商务中，诸如电子现金的使用和电子投票等有匿名性要求的领域。完全盲签名的研究已经比较成熟，如盲RSA签名和盲Schnorr签名方案是主要的实现方案。下面以最早的RSA盲签名实现方案为例，介绍强盲签名方案。,22,强盲签名(RSA),设签名人S有公钥(e,n)，私钥d，要对用户U的文件m进行完全盲签名。(1)U选取随机整数k1,n，盲化m为：t=mkemodn，并将t发给S。(2)S签名t：。(3)U对t去盲：。s是文件m最终的签名，易证，所以。s的效果相当于签名人S直接对m签名，但S不知道m的内容。这个协议中，由于S不知道k，不能从td得到s，从而得不到m。,23,强盲签名(DSA),设U签名的接受者，S为签名者，其拥有公私钥对(x,y)，其中y=gxmodp，m为待签名的文件，U和S的签名过程如下：US签名请求r,24,强盲签名(DSA)（正确性）,25,弱盲签名,所谓弱盲签名方案是指签名者S仅知道Sign(R(m)而不知道Sign(m)，但一旦公开Sign(m),S可以建立两者间的联系，即S能把盲签名Sign(R(m)的行为与文件m的内容关联起来。如果把文件m看作是一个电子现金，则用户U使用这个电子现金支付给商家，再由商家到银行兑付时，银行就可以从签名Sign(m)中了解是U消费的，从而可以追踪U的行为，这显然不满足不可跟踪性。但是从另一角度看，这种方案可以用于遗嘱、合同等电子公证，在一段时间内保护信息秘密，在合适的场合公布有关内容及用户身份。,26,弱盲签名(举例),设U签名的接受者，S为签名者，其拥有公私钥对(x,y)，其中y=gxmodp，m为待签名的文件，U和S的签名过程如下：US签名请求r,27,弱盲签名(举例)（正确性）,28,盲签名在电子投票中的应用,29,群(组)签名,1991年，Chaum和Heyst首次提出群签名方案（GroupSignature）。群签名方案允许组中合法用户以用户组的名义签名，具有签名者匿名、只有权威者才能辨认签名者等多种特点，在实际中有广泛的应用。,30,群(组)签名特点,只有组中成员才能代表组为消息签名，签名为群签名。消息接收者可以验证群签名的有效性，但不能辨别签名者。一旦发生争论，从消息的群签名权威（组长）可以辨别签名者。,31,群签名方案(初始化),组中每一用户Ui随机选择xi1,q-1,i=1,2,t，并计算yi=gximodp,那么用户Ui的私钥为xi和公钥为yi，同样，GC（组长）随机选择xT1,q-1,并计算yT=gxTmodp，GC的私钥为xT和公钥为yT。对于组中每一用户Ui，GC随机选择ki1,q-1,计算：,32,群签名方案,GC将(ri,si)发送到组中用户Ui，Ui收到(ri,si)，验证等式：,如果等式成立，(ri,si)是GC对用户Ui身份的有效签名。,对于组中每一用户Ui，GC存储(ri,si，ai，yi),其中：,33,群签名方案(签名),为了对消息m进行签名，用户Ui随机选择t1,q-1,计算:,那么,用户Ui生成的群签名值为(r,s),(ri,si),34,群签名方案(验证),接受方在收到消息m和群签名值(r,s),(ri,si)后，验证以下方程是否成立：如果等式成立，接受签名，否则签名无效。,35,群签名方案(正确性),36,群签名方案(揭示签名者),(1)GC使用消息m和群签名值(r,s),(ri,si)验证这个群签名是否有效，若有效进入下一步。(2)GC根据签名值中的(ri，si),在GC初始化过程中保存的(ri，si，ai，yi)中查找匹配项，若存在，根据yi能确定用户身份。(3)若成立，证明yi的用户身份。,37,多重数字签名的简介,在数字签名应用中，有时需要多个用户对同一文件进行签名和认证，比如，一个公司发表的声明涉及到财务部、开发部、销售部、售后服务部等部门，需要这些部门签名认可，那么，需要这些部门对这个声明文件进行签名。能够实现多个用户对同一文件进行签名的数字签名方案称为多重数字签名（DigitalMulti-signature）方案。,38,多重数字签名的简介,根据不同的签名过程，多重数字签名方案可分两类：有序多重数字签名（SequentialMultisignature）和广播多重数字签名（BroadcastingMultisignature）。无论是有序多重签名方案，还是广播多重签名方案，都包括文件发送者（Issuer）、文件签名者（Signers）和文件验证者（Verifier）。在广播多重签名方案中还包括签名收集者（Collector）。,39,有序多重签名方案的简介,文件发送者规定文件签名顺序，然后将文件发送到第一个签名者，除了第一个签名者外，每一位签名者收到签名文件后，首先验证上一签名的有效性，如果签名有效，继续签名，然后将签名文件发送到下一个签名者；如果签名无效，拒绝对文件签名，终止整个签名过程。当签名验证者收到签名文件后，验证签名的有效性，如果有效，多重数字签名有效；否则，多重数字签名无效。下图描述了有序多重数字签名方案。,40,Elgamal有序多重签名方案(初始化),设UI为消息发送者，UV为签名验证者，U1,U2,Ut为消息的签名者。p和q是满足安全的大素数，q是p-1的大因子，g是域GF(p)的本原元，每一个签名者Ui都拥有公私钥对(xi,yi)，其中yi=gximodp。消息发送者UI预先设计一种签名顺序(U1,U2,Ut)并将这种签名顺序发送给每一位签名者。,41,Elgamal有序多重签名方案(签名),UI将消息m发送给第一个签名者U1。设s0=0，那么每一位签名者Ui收(i2)到上一个签名者Ui-1的签名值(m,si-1)后，做如下操作：(1)验证等式是否成立，如果成立，Ui认为U1,U2,Ui-1对消息m的签名有效，否则认为签名无效，拒绝继续对消息签名。(2)Ui随机选择ki1,q,计算ri=gkimodp和si=si-1+h(m)xi-rikimodq。(3)将(m,si)发送到下一个签名者Ui+1，ri将分别发送到Ui以后的签名者。,42,Elgamal有序多重签名方案(验证),消息m的有序多重签名值(m,st,r1,r2,rt)。签名验证者UV验证式：是否成立，如果成立，UV认为U1,U2,Ut对消息m进行的多重签名有效，否则认为签名无效。,43,Elgamal有序多重签名方案(正确性),因此，Elgamal有序多重数字签名方案是正确的。,44,广播多重签名方案的简介,在广播多重数字签名方案中，文件发送者同时将文件发送给每一位签名者进行签名，然后签名者将签名文件发送到签名收集者，由收集者对签名文件进行整理并发送给签名验证者，签名验证者验证多重签名的有效性。下图描述了广播多重数字签名方案。,45,Elgamal广播多重签名方案(初始化),设UI为消息发送者，UV为签名验证者，U1,U2,Ut为消息的签名者，UC为消息收集者。p和q是满足安全的大素数，q是p-1的大因子，g是域GF(p)的本原元，每一个签名者Ui都拥有公私钥对(xi,yi)，其中yi=gximodp。UI将消息m同时发送到Ui(i=1,2,t)进行签名，Ui将签名信息发送给签名收集者UC，UC收到签名信息后验证其签名的有效性，然后对签名进行整理并产生多重签名，然后将这个多重签名发送到UV进行验证。,46,Elgamal广播多重签名方案(签名),UI将消息m发送给每一个签名者Ui(i=1,2,t)，Ui和UC收到消息后做如下操作：(1)Ui随机选择ki1,q,计算ri=gkimodp，将ri发送到签名接收者UC。(2)UC收到ri(i=1,2,t)后，计算，然后UC将R发送到其余每一个签名者Ui(i=1,2,t)。(3)对于消息m，Ui(i=1,2,t)计算si=h(m,R)xi-rikimodq,然后将签名消息(m,si,ri)发送到UC。(4)当UC收到(m,si,ri)后，其中i=1,2,t，计算，然后将(m,S,R)发送给UV。,47,Elgamal广播多重签名方案(验证),当签名验证者UV收到多重签名值(m，S，R)后，UV进行如下验证：是否成立，如果成立，UV认为U1,U2,Ut对消息m进行的多重签名有效，否则认为签名无效。,48,Elgamal广播多重签名方案(正确性),因此，Elgamal广播多重数字签名方案是正确的。,49,代理签名的简介,代理签名是指原始签名者把他的签名权授给代理者，代理者代表原始签名者行使他的签名权。当验证者验证代理签名时，验证者既能验证这个签名的有效性，也能确信这个签名是原始签名者认可的签名。,50,代理签名的发展过程,代理签名的思想最早出现于1991年1996年第一次系统地阐述了代理签名概念全代理授权部分代理授权授权书代理授权门限代理签名、代理盲签名、指定验证者的代理签名、一次代理签名、匿名代理者的代理签名、代理多重签名等分布式计算、电子投票、电子付费、网格计算、移动代理等,51,代理签名的定义,设A、B分别是某个代理数字签名体制的两个用户，他们的公私钥对分别是(xA,yA)和(xB,yB)。如果以下条件成立：A利用他的私钥xA计算出一个数，并将秘密地交给B。任何人（包括B）在试图求出xA时，不会对它有任何帮助。利用（可能包括xB）生成一个新的签名密钥，即代理私钥xP。,52,代理签名的定义（续）,存在一个公开的通用签名算法Sign，对被签名的文件m，有s=Sign(xP,m)，其中s是代理签名。存在一个与签名算法Sign相对应的验证算法Ver，验证等式Ver(yP,s,m)=True是否成立。任何人在试图求出xA、xB、或xP时，任何数字签名值s都不会对它产生帮助；那么就称用户A将他的（部分）数字签名权利委托给了用户B，并且称A为B的原始签名者，称B为A的代理签名者，称为委托代理密钥，xP称为代理签名密钥，称以xP作为签名密钥对消息m生成的数字签名s为A的代理签名。,53,代理签名的性质,可验证性可区分性不可伪造性可识别性不可否认性可控性,54,代理签名的组成,代理密钥对生成算法：它的输入值是A和B，分别由原始签名者A和代理签名者B生成的，其输出是代理密钥对(xP,yP)，它的实现是由原始签名者A和代理签名者B经过交互来完成的。代理签名算法：代理签名者B使用代理私钥xP对文件m签名，其输入值为xP和m，输出值是代理签名值sP.代理签名验证算法：验证者V对代理签名进行验证，其输入值为代理签名(sP,m,yP)，输出是一个布尔值，要么是真，要么是假.,55,代理签名的分类,完全授权型（Fulldelegation）部分授权型（Partialdelegation）非保护代理者的代理签名（proxy-unprotectedproxysignature）保护代理者的代理签名（proxy-protectedproxysignature）带授权书型（Delegationwithwarrant）,56,非保护代理者的代理签名(PH的方案),原始签名者A,代理签名者B,代理授权阶段,57,PH的方案(续),代理签名算法利用通用的签名生成算法Sign，B使用代理私钥xP代表原始签名者A对文件m进行签名s=Sign(xP,m)，有效的代理签名值为(m,s,r,yA,IDB)，其中IDB表示代理签名者的标识。代理验证算法为了验证代理签名s，验证者首先利用代理签名值(m,s,r,yA,IDB)计算代理公钥，然后利用与Sign相对应的通用签名验证算法Ver，验证者使用yp验证代理签名的有效性，即Ver(yP,s,m)=True，如果等式成立，说明这个代理签名是原始签名者认可的且是有效的。,，,58,保护代理者的代理签名(MUO的方案),原始签名者A,代理签名者B,代理授权阶段,59,MUO的方案(续),代理签名算法利用通用的签名生成算法Sign，B使用代理私钥xP代表原始签名者A对文件m进行签名s=Sign(xP,m)，有效的代理签名值为(m,s,r,yA,yB)。代理验证算法为了验证代理签名s，验证者首先利用代理签名值(m,s,r,yA,yB)计算代理公钥，然后利用与Sign相对应的通用签名验证算法Ver，验证者使用yp验证代理签名的有效性，即Ver(yP,s,m)=True，如果等式成立，说明这个代理签名是原始签名者认可的且是有效的。,，,60,带授权书的代理签名(KPW的方案),通过在代理签名中添加授权书，Kim等人提出一种新形式部分授权的代理签名方案，其主要思想是代理签名者利用自己