[硕士论文精品]前向安全环签名研究

西南交通大学硕士研究生学位论文第1页摘要2001年，RIVEST，SHAMIR，TAUMAN提出了环签名的概念。环签名是一类以完全匿名方式对消息进行签名的特殊数字签名，验证者确信签名来自于环中的某个成员，却无法判断签名人的真实身份。环签名适用于匿名投票系统，可转移电子现金系统等，成为实现匿名交易安全的核心技术。作为环签名基础的公钥加密体制，存在着密钥泄露的问题，对于环签名的安全性来说是致命的。从密钥泄露问题出现以来，探索有效地解决方法一直没有停止过，直到1997年，ANDERSON提出了前向安全数字签名思想。前向安全数字签名与普通数字签名不同的是增加了一个私钥更新算法，具体过程是将数字签名的有效时间被分成若干个周期，在每一个周期内使用不同的私钥，而验证签名的公钥在整个有效时间内保持不变。每个周期结束时，利用该周期的私钥；由系统内设置好的更新算法产生下一个周期的私钥。这样若某个周期内的私钥泄露，不会影响在该周期之前产生的签名。前向安全的签名体制也可以引入到环签名方案中，保护签名人的私钥，防止签名被伪造攻击，进一步提高了环签名的安全性。本文主要对前向安全环签名进行了研究，主要工作如下首先，分析了一种基于环Z。上的圆锥曲线的前向安全环签名方案，指出了该签名方案中私钥更新算法的不足之处，给出了一个可能存在的伪造攻击。改进后的方案在原有的困难问题上又增加了因子分解困难问题，安全性有了很大的提高。其次，对AUMANHO等提出的基于身份的环签名进行了伪造攻击，结合已有的两种改进方案，提出了更加安全的改进方案。新方案在效率上也有了一定地提高。最后，给出了两个基于身份的前向安全环签名方案，分别在随机预言模型与标准模型下详细地进行了安全性证明。在前向安全性方面，第一个方案是基于因子分解困难问题，第二个方案是基于离散对数问题。关键词环签名；前向安全；数字签名；密钥泄漏；，随机预言模型标准化模型经典语录HTTP/WWWYULUME西南交通大学硕士研究生学位论文第1I页ABSTRACTIN2001，RIVEST，SHAMIRANDTAUMANADDRESSEDNOTIONOFFINGSIGNATUREIUNGSIGNATURE，WHICHSIGNSAMESSAGEINALLUNCONDITIONALLYANONYMOUSWAY,ISASPECIALDIGITALSIGNATUREAVERIFIERCONVINCESTHESIGNATUREWHICHISSIGNEDBYONEOFINDEPENDENTRINGSIGNERSWITHOUTALLOWINGTHEVERIFIERTOIDENTIFYWHICHSIGNERITISRINGSIGNATUREADAPTSANONYMOUSELECTRONICVOTINGSYSTEM，TRANSMISSIBLEELECTRONICCASHSYSTEMETC，ANDITHASBEENACORETECHNOLOGYFORAPPLYINGEXCHANGEANONYMOUSSECURITYITISACRUXFORSECURITYOFRINGSIGNATURETHATEXPOSUREOFSECRETKEYSCALLBEADEVASTATINGATTACKONCRYPTOSYSTEMWHICHRINGSIGNATUREBASEONTHELEGITIMATEMETHODFOREXPOSUREOFSECRETKEYSHADBEENEXPLOREDUNTILANDERSONPROPOSEDFORWARDSECUREDIGITALSIGNATUREIN1997THEDIFFERENTBETWEENFORWARDSECUREDIGITALSIGNATUREANDORDINARYDIGITALSIGNATUREISADDINGKEYUPDATEALGORITHMTOFORWARDSECUREDIGITALSIGNATURETHESPECIFICCOURSEISTHATTHETIMEDURINGWHICHTHEPUBLICKEYISDESIREDTOBEVALIDISDIVIDEDINTOPERIODS；THESECRETKEYEVOLVESINEACHPERIODTHESECRETKEYOFNEXTPERIODISDERIVEDFROMTHECURRENTSECRETKEYVIAKEYUPDATEALGORITHMWHICHISARRANGEDINSYSTEMAFTERAPERIODENDTHEPREVIOUSSIGNATUREWOULDNOTBEBROKENBYALLATTACKEREVENIFKEYISEXPOSEDANDTHEATTACKERSUCCESSFULLYATTAINSITFORWARDSECURESIGNATUREADVANCEDINRINGSIGNATURETOPROTECTTHESECRETKEYOFSIGNERANDGUARDAGAINSTFORGINGSIGNATUREASRESULT，THESECURITYOFRINGSIGNATUREISIMPROVEDGREATLYTHISTHESISMAINLYFOCUSESOILTHERESEARCHOFFORWARDSECURERINGSIGNATURETHEMAINWORKISASFOLLOWSFIRSTLY,WEANALYSIZEAFORWARDSECURERINGSIGNATUREBASEDONTHECONICCURVEOVERRINGZFLTHENWEPOINTOUTADISADVANGTAGEOFKEYUPDATEALGORITHMOFTHESIGNATUREANDGIVEAILEXSITENTIALFORGINGATTACKTHEIMPROVEDSIGNATUREADVANCESINSECURITYBECAUSEITUSESTWOHARDNESSPROBLEMSATTHESAMETIMETHEHARDNESSOFFACTOFIZATIONISADDEDTOIMPROVEDSIGNATURELATERSECONDLY,WEGIVEAFORGINGATTACKTOIDENTITYBASEDRINGSIGNATUREPROPOSEDAUMANHOETA1WITHTWOIMPROVEDSIGNATURESPROPOSEDRESPECTIVELY,WEGIVEADEWSIGNATUREITISMORESECURETHANPREVIOUSSIGNATURESANDTHEEFFICIENCYISADVANCEDMORETHANORIGINALSIGNATURETHIRDLY,WEGIVETWOIDENTITYBASEDFORWARDSECURERINGSIGNATURESINSECURITY,ONEISPROVEDINRANDOMORACLEMODELTHEOTHERISPROVEDINSTANDARDMODELINFORWARDSECURE西南交通大学硕士研究生学位论文第TIL页PROPERTY,THEFORMERSIGNATUREBASE011HARDPROBLEMOFFACTORIZATION，THELATTERSIGNATUREBASEOILDISCRETELOGARITHMHARDPROBLEMKEYWORDSRINGSIGNATURE；FORWARDSECURITY；DIGITALSIGNATURE；KEYEXPOSURE；RANDOMORACLEMODEL；STANDARDMODEL经典语录HTTP/WWWYULUME西南交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位论文。本学位论文属于1保密口，在年解密后适用本授权书；2不保密彤使用本授权书。请在以上方框内打“”学位论文作者签名、F匐级日期00IOR09引气跚日期JD汐J岁F西南交通大学硕士学位论文主要工作贡献声明本人在学位论文中所做的主要工作或贡献如下首先，分析了基于环Z。上的圆锥曲线的前向安全环签名方案，指出了私钥更新方案的不足之处，给出了一个可能存在的伪造攻击。改进后的方案在原有的困难问题上又增加了因子分解困难问题，安全性有了很大的提高。其次，对AUMANHO等提出的基于身份的环签名进行了伪造攻击，结合已有的两种改进方案，提出了更加安全的改进方案。最后，给出了两个基于身份的前向安全环签名方案，分别在随机预言模型与标准模型下详细地进行了安全性证明，在前向安全性方面，第一个方案是基于因子分解困难问题，第二个方案基于离散对数问题。本人郑重声明所呈交的学位论文，是在导师指导下独立进行研究工作所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确说明。本人完全了解违反上述声明所引起的一切法律责任将由本人承担。学位论文作者签名哟之日强0OF1DR。38经典语录HTTP/WWWYULUME西南交通大学硕士研究生学位论文第1页第1章绪论本章介绍了课题研究的背景，发展现状，本文的主要研究内容和基本框架结构。11课题研究背景与意义随着信息时代的飞速发展，电子商务、电子政务及日常生活的信息化，使得与公钥密码体制相伴的数字签名技术具有了广泛的应用前景。在电子商务和电子政务中，数字签名扮演着与手写签名一样重要的角色。自从WDI伍E和MHELLMAN1976首先提出了“数字签名”的概念以后，相继出现了以RSA，EIGAMAL和DSS为代表的数字签名方案。在具体的应用领域，一般的数字签名方案无法满足相应的需求，因此，构造满足特殊需求的数字签名方案成为关注的问题。在普通的数字签名基础上附加一些特殊性质后，出现了群签名、环签名、盲签名、代理数字签名和可传递签名等许多特殊数字签名，研究特殊数字签名对构建安全、实用、高效的电子信息系统具有重要意义。在电子拍卖、电子投票和电子现金等具体应用中，为了防止用户的个人信息被非法窃取和使用，需要进行匿名签名，验证者仅能验证签名者是否属于某个特殊群体而不知道具体签名者的身份。1991年CHAUM和VANHEYEILJ提出了群签名的概念，这是一种重要的匿名签名技术，群签名允许群成员代表群匿名签名，群管理员享有揭露签名者的真实身份的特权，在某些实际应用中，签名者希望对群管理员的这种特权予以必要的约束，以防止其滥用职权。文献【2，3，4】提出了一些相应的解决方案，因为构造较为复杂，不利于实现。2001年，RIVEST，SHAMIR和TAUMANT5J提出了的环签名概念，与群签名相比，环签名无群管理员，签名人自己指定群，无密钥分配过程，不需要其他群成员的参与达到匿名效果，签名人的真实身份是无条件匿名的。在实际应用中，环签名方案面临的最大安全威胁并不是签名方案被攻破，而是由于该方案所依赖的底层系统或者存放私钥对于采用对称加密体制的数字签名，签名者和验证者持有的密钥就称为密钥，因为签名者和验证者的密钥是致的；采用公钥加密体制的数字签名，签名者持有的密钥就称为私钥，验证者持有的密钥成为公钥，因为签名者与验证者持有的密钥是非一致的。由于数字签名一般采用公钥加密体制，因此数字签名方案中的密钥泄漏问题一般是私钥泄漏问题的机器的安全性遭到破坏，所导致的私钥泄漏。对于一个利用通用签名算法的环签名方案而言，利用现有的运算速度攻破签名方案是相当困难的；然而当签名的私钥泄漏后，不仅之后该方案的安全性遭到破坏，甚至在私钥泄漏之前所进行的签名也会受到影响。为了缓解私钥泄漏对西南交通大学硕士研究生学位论文第2页签名安全造成的威胁，各国的学者进行了大量的研究，在实用性和成本方面做了充分而细致的工作，最终将前向安全作为数字签名缓解私钥泄漏问题的最佳方案。作为特殊数字签名的环签名，当面对私钥泄漏问题时，提出具有前向安全的环签名方案是缓解私钥泄漏对环签名造成威胁的理想方案。12研究现状近几年，环签名的研究取得了丰硕的成果，其结构体系也在不断地壮大、完善，在这个体系的建设过程中，到目前为止主要经历了三个阶段第一阶段，是把不同的加密体制应用到RIVEST等人提出的环签名方案中。MASAYUKIABE等【6J类型的公钥构造1OUTOFN签名。FANGGUOZHANG等17J应用双线性对构造基于身份的环签名方案。EMMANUELBRESSON等瞵J提出了门限环签名的概念，适用于ADHOC网络。鉴于隐私保护的要求，MONINAORI9L提出了可否认的环认证方案。第二阶段，DUNCANSWONG等ILUJ提出一种新的构造环签名的方法，即REEDSOLOMONCODE方法。JAVIERHERRANZ等【LJJ提出适合环签名安全性的分叉引理。基于NYBERGRUEPPEL签名方案，CHONGZHIGA0112J提出一个新的环签名方案。WILLYSULILO等【L3J在可否认的环认证方案基础上提出的非交互式的可否认环认证方案。JIQIANGLV等114J将认证加密与环签名相结合，提出了环认证加密方案，TIANJIECAO”J提出了它的改进方案，使其具有签名人的可验证性和接受者的可验证性。YEVGENIYDODIS16J提出的利用单向累加器的环签名方案解决了ADHOC群体的匿名认证问题。GANZHITL7】提出了可验证环签名方案，此方案的方法是在阀下信道嵌入认证消息。此外，文献【18提出高效的基于身份的环签名与代理环签名，文献19，20，21对门限环签名，有了进一步的研究。第三阶段，环签名的研究重点放在了效率、安全性、实用性方面。在效率方面NGUYEN22J利用双线性对累加器构造的基于身份的签名方案，避免因成员过多影响签名效率。QIANHONGWU【23】构造了高效的盲环签名方案。在实用方面，PATRICKETSANG等【241在关于签名人身份的关联问题的基础上，提出了简短的关联环签名，并将其应用于电子投票、电子现金系统上。对于环签名的安全性问题，下面将做详细重点论述。一般数字签名的安全性主要概括为两个方面，一方面是签名的安全性，另一方面是签名密钥的安全性，即私钥的安全性。作为特殊数字签名的环签名也不例外。在签名安全性方面，SHERMANSMCHOW等12纠首次提出了在标准模型中的环签名方案，这个环签名是基于门QDSJSDH的假设下是可证安全的。ADAMBENDER等【26】提出了更加可靠的安全性定义，并给出了两个安全的环签名方案。AUMANHO271提出了安全性较好的新的简短关联环签名方案。在私钥的安全性方面，JOSEPHKLIU等【28】结合数字签名的密钥泄漏问题，首次提出了前向安全的环签名方案与密钥封装的环签名方案，在随经典语录HTTP/WWWYULUME西南交通大学硕士研究生学位论文第3页机预言模型下是可证安全的。JOSEPHKLIU等指出环签名的密钥泄漏造成的后果比一般的数字签名要严重，这是因为对一般的数字签名而言，攻击者不但可以伪造任意时期任意消息的签名，还可以把其他签名的密钥撤销，放入泄漏的密钥伪造新的签名；至于环签名，存在上述危险的同时，还存在攻击者可代表所在的群体进行任意的签名伪造，或者自发的形成一个群体进行有效签名伪造的危险。在实际应用中，环签名与数字签名一样，面临的最大安全威胁并不是签名方案被攻破，而是由于该方案所依赖的底层系统或者存放密钥的机器的安全性遭到破坏，所导致的密钥泄漏。，为了解决密钥泄漏问题，密码学发展史上有许多方案被提出来，如秘密分享，门限加密体制，前摄加密体制。其中考虑得最多的一种方法是将私钥通过秘密共享的方式分布在不同的计算机上，以此来减小密钥被泄漏的风险。该方法的具体体现就是门限签名【291。该方法有以下缺陷将密钥分布在多个机器上代价太大，对于普通用户来说不实际，只有大公司或者认证机构才有能力使用该方法；另外，由于几乎所有的机器对于相同的攻击抵抗力并没有明显的区别，如果一台机器被攻破，则其它机器也不能幸免，因此该方法并不能从根本上解决问题。一些其他的方法，如硬件保护或者智能卡等，代价太大，不可能在实际中得到广泛应用。后来提出的前向安全和密钥封装技术被广泛研究和应用。密钥封装技术与前向安全的思想基本一致，只是在私钥更新过程中需要一个安全的设备作为辅助，效率上稍显逊色。GTINTHER等PUJ在一文中首次提出“前向安全”的概念。在这篇文章中前向安全被用于会话密钥交换协议中。前向安全的基本思想是系统的使用时间被划分为若干个较短的周期，系统的私钥仅在一个周期内使用，不同的周期使用不同的私钥，当某个周期内使用的私钥泄漏后，不会影响在该周期前的所有周期内进行的签名操作。与其他方法相比，前向安全不需要密钥分布或者保护设备，同时也不增加密钥管理的开销，因此具有显著优势。随后，DIFFIE31J在AUTHENTICATIONANDAUTHENTICATEDKEYEXCHANGES中用到前向安全。ROSSANDERSONL32J在ACMCCS会议中首次提出前向安全数字签名思想。前向安全数字签名与普通的数字签名类似，前者包含了私钥更新算法，具体做法是系统的运行时间被分成若干个周期，每个签名密钥仅使用一个周期，第F个周期所使用的密钥可以由第F1个周期的私钥通过私钥更新算法得到，但是反过来很难由第F个周期的密钥得到第F一1个周期的密钥。因此若第F个周期内密钥丢失，不会影响到该周期之前所有周期的签名。ROSSANDERSON在会议中提出了一个开放性问题，即如何寻找满足前向安全的数字签名方案。1999年，BELLAIRE和MINER33】在美国密码学会中的AFORWARDSECUREDIGITALSIGNATURESCHEME中解决了ANDERSON提出的问题并给出了更多的结论。到目前为止，前向安全环签名的研究时间较短，国内外文献数量较少，研究处于起步阶段。随着环签名的不断发展，安全性要求地不断提高，前向安全环签名的研究西南交通大学硕士研究生学位论文第4页会逐渐引起各国学者的关注。本文对前向安全环签名的研究做了一些工作，改进了已有前向安全环签名方案存在的不足；在已有的基于身份的环签名方案的基础上，结合基于身份的前向安全数字签名，提出了基于身份的前向安全环签名方案，并在安全性方面进行了详细的分析。13主要研究内容本文的研究重点是环签名的安全性方面，主要工作贡献有一、分析王玲玲等人提出的基于环Z。上的圆锥曲线的前向安全环签名方案存在的不可抵抗伪造攻击的安全问题，指出签名方案不具有前向安全性。改进后的签名方案安全性有了很大提高，抗伪造攻击能力增强。二、分析AUMANHO等人提出的基于身份的环签名存在的已知签名伪造攻击，结合张跃宇等人和刘振华等人提出的两种改进方案，提出了可以完全抵抗已知签名伪造攻击的改进方案，改进后的基于身份的环签名方案在效率与安全性方面都有了一定地提高。三、先给出一个一般的基于身份的前向安全环签名方案，在随机预言模型下详细论证了其安全性。然后同时从签名安全与私钥安全两个角度出发，给出了安全性比较完善的标准模型下基于身份的前向安全环签名方案，在基于CDH难解问题上证明了不可伪造性，前向安全性是基于离散对数难解问题。14论文结构第一章绪论，简要介绍了课题的研究意义和发展现状，本文的主要研究内容和基本框架结构。第二章基础知识，主要介绍了理论基础知识及相关概念。为下面展开的讨论与分析做好了充分地铺垫。第三章前向安全环签名，描述了前向安全环签名的形式化定义，安全模型，着重分析了在随机预言模型下提出的基于环Z。上的圆锥曲线的前向安全环签名方案，分析方案存在的漏洞，提出改进方案，并对改进后的方案进行安全性分析。第四章基于身份的前向安全环签名方案，首先介绍了基于身份的加密体制，对AUMANHO等提出的基于身份的环签名进行了伪造攻击，分析张跃宇等和刘振华等提出的两种改进方案，这两种改进方案提高了效率，并在一定程度上可以抵抗伪造攻击，但是并不彻底。在这两种改进方案的基础上，提出了可以彻底抵抗伪造攻击的改进方案，并吸取了前两种改进方案效率方面的优点。经典语录HTTP/WWWYULUME西南交通大学硕士研究生学位论文第5页第五章基于身份的前向安全环签名，首先介绍了基于身份的前向安全环签名的形式定义和安全模型，然后在随机预言模型与标准模型下，提出了两个基于身份的前向安全环签名方案，并详细的分析它们的安全性。结论，总结本文的主要工作，提出以后继续研究的方向。西南交通大学硕士研究生学位论文第6页第2章基础知识本章主要介绍了理论基础知识，包括必须了解的数学基本知识和相关概念，为前向安全环签名的研究做好理论和技术支持。21数学基础知识本节主要介绍本文所需的数字理论及密码学知识。211因子分解定义211给定一个正整数N，找出该正整数的所有因子，并根据算术基本定理将整数N表示成如下形式，7所P；2露21其中，只是互不相同的素数，E，1，翻04FA暮FBMODM，其中FX为任意个整系数多项式。定理213若CTC兰BCMODM，且M，CD，则口毫BMODMD。定理214若口善BMODM,，FL，2，玎，则口兰BMODML，垓】。经典语录HTTP/WWWYULUME西南交通大学硕士研究生学位论文第页213欧拉函数定义213欧拉函数缈是一个定义在整数集上的函数，P刀的值等于序列0，1，2，刀一1与互素的数的个数。定理215设M1，口，M1，则扩州暮LMODM。214杂凑函数杂凑函数，也就是通常所说的HASH函数，它是以一段消息M作为输入，产生一个输出，输出值被称为杂凑值或杂凑代码。杂凑函数可以将任意长的比特串映射为疗长的比特串HO，1专0，1”，7HHM22根据上面的描述，杂凑函数可以由无限个元素映射到有限个元素，因此，杂凑函数肯定不是双射，每个函数值都有无数个原像与之对应，这样就会有很多碰撞。碰撞是指存在一对M，M，满足办MHM1的情况。这时我们可以说M，M是杂凑函数H的一个碰撞。在没有碰撞的情况下，杂凑值可以作为消息的压缩形式有时被称为数字指纹或数字摘要，在密码学中的应用相当于数字签名方案。杂凑函数可以用来控制消息的完整性。如果安全地存放消息M的杂凑值，通过计算M的现在杂凑值与原来的比较，就可以检测出M是否被篡改，在这个意义上，杂凑函数被称为篡改检验码。如果在数字签名中结合使用杂凑函数，消息应首先经过杂凑，接着被签字的是消息的杂凑值而不是原消息。假设某一签名者签署了7，Z的杂凑值HM，必须保证攻击者不能找到另一个消息RH满足白MHM。否则，攻击者可以伪装成签名者对消息M而不是对消息聊进行签字。因此，杂凑函数必须具有不可逆的性质，即己知函数值办聊，找不到一个朋满足HMHM，这个性质被称作抗第二原像的性质。而对于在数字签名中使用的杂凑函数H，我们要求更强的性质。一个使用杂凑函数的数字签名方案中的合法用户应该不可能找到对不同的消息M，M。满足HMHM。若是找到了这样的消息，那么用户可以对所签得的消息M进行否认，因而不能满足数字签名的三条基本性质之一消息的不可否认性，因此，选择杂凑函数时，应满足找到对碰撞消息的计算是不可行的要求，满足这种要求的一类杂凑函数是抗碰撞的。抗碰撞的杂凑函数一定是抗第二原像的。西南交通大学硕士研究生学位论文第8页215随机数借用不可区分性的概念来定义随机序列如果没有有效的算法能将一个序列和一个同样长度的均匀分布序列区别开，则称其为伪随机序列。即伪随机数要满足通过概率多项式算法无法区分其与真正意义上的随机数。一个随机数生成器PRG是一个生成伪随机数的有效算法。下面给出随机数生成器的定义。定义214一个随机数生成器PRG是一个确定的多项式算法G，并且满足以下两个属性1可扩展性存在函数，N专N，对所有满足LN刀的RT，ZN，以及每个SO，1，有IGSI，|S1，函数LG,为函数彳的扩展因子。2伪随机性集合G乩是伪随机的。其中巩是定义在长度为，2的集合上的均匀分布的随机变量。伪随机生成器的关键思想是降低了人工生成伪随机序列所耗费的成本，它的理论研究具有重要意义。22难解问题很多密码系统的安全性都是基于数论上的某个困难性问题。所谓一个问题是困难的，指的是任何一个算法都不能通过合理数量的资源如时间、内存等来解决这个问题。事实上，人们并没有办法证明这样的算法是不存在，但人们不得不假设没有这样的算法存在，因为人们找不到这样的算法。攻击者想要对密码系统实施攻击成功，也必须解决这样的难题下面给出在公钥密码密码体制中经常使用到的一些园难性问题。221因子分解难题定义213中给出了一个整数的标准分解形式，为密码学的因子分解问题提供了理论依据。密码学中的因子分解问题是一类比较特殊的因子分解，要求给定一个正整数刀，刀可以分解成两个大素数的乘积，两个大素数分别是P，QP，Q2768，求其中的一个因子。严格的定义为给定聆PQ，其中P，Q是位数相同的大素数，即FPJIQI，则对于任意的概率多项式时间算法彳，任意的正多项式P和充分大的，都有1PR【彳珂SXSP，9】G2，两个哈希函数为EO，1寸Z，H2O，1IIG2_G1。系统公钥为厶。YNLP，系统的私钥为YNL。公开的系统参数GL，G2，P，P，名6，HI，皿，T，刀，X。EXTRACT用户的私钥分配与其身份标识有关，假设用户的身份标识为尬，那么该用户的公钥QE哆，相对应的初始的私钥为S。旷“Q。UPDATE系统进入第歹时期，当歹TI时，SI，是空串，当1歹T，S，表示签名者崛第J1周期的私钥，由S冷，_，一L可以得到时期的私钥S，。SIGN系统进入第歹时段，用户群为LID,，皿，ID，消息为M。1令任选A只G1，计算气。EA，尸“，如果EA，P1，重新选择彳。2任选正G1，I1，2，K一1，K1，”，组成相应的集合TZ，集合R中没有两个相同的元素，如果出现相同的元素，应重新选择，直到集合中没有两个重复的元素为止。同时还有集合C，表示如下CC刚LE1E名6，皿搬LLQQ2互，尸，IL，2，K一1，KL，船，C1CN“513计算瓦1X顶彳一马所ILLIQS，并将互放入集合R中；计算唧。P巳。，H2聊II三II气QP瓦，尸，并将Q放入集合C中；4输出签名为Q，五，E。VERIFY1对于江1，2，胛一1，计算E卅P，垦MII三JLQQPZ，P。2验证等式QP乇。，必册LI三ILC。QE乙，尸是否正确，如果正确，签名有效；否则，签名无效。523安全性分析1正确性从上述的签名方案得知，C中的元素满足Q。P尸M，142MLJ三I|EQPZ，尸52那么，下面的过程应该是正确的C2P只柚，致掰IILLC1Q弦互，P巳P乞岫，心所II上|CQP乏，尸吼E尸朋。，皿MIL三|IC一，G一。弦瓦一。，尸西南交通大学硕士研究生学位论文第30页CKLE厶6，致朋I|三|CKGETK，尸EA，尸一；53CNP名6，H2聊II三LHQP瓦，PC。其中，CEEPUB，H2MII三LCKOKETK，PPF。，H2MII0CKQE1X彳一H2MI|三ILCTSK，PPC。6，凰MII三|QQE1X7A一1X哎聊LI三|CKX墨O，PP厶。，必圳I圳CTQ81X彳一皿ILLIICKSKO，N54EP，H2MIL三|ICKSKOE1X。AH2MIL上IIQSO，PEP，皿，押|L三I|CKSO1X7AH2聊L|三QSOEP，1X。彳EA，尸17。所以，签名结果是正确无误的。2无条件匿名性分析签名Q，互，乙的构造，互，L中除了瓦之外，其余的都是随机选取的，耳1X么一哎班LL三LLCKSK,J中的A是随机选择的，尽管1X，鸩聊IL三IL唧对于验证者并不陌生，但是在五，乙中仍然是无法区分的。另外，通过分析Q，C2，CN得到签名人的身份也是非常困难的，因为这些结果也是毫无规律的。对这咒个成员来说，攻击者猜测出真实签名人的概率为1，Z，当RL25，概率趋近于零，因此签名方案满足无条件匿名性。3签名方案具有前向安全性利用因子分解问题的困难性，证明方案是前向安全的。如果存在攻击者么能以不可忽略的概率攻破上述具有前向安全性的环签名方案，则存在挑战者C能以不可忽略的概率解决RSA问题即给定X，E，栉，C能以不可忽略的概率输出BGL，使得XBE；其中刀PQ，P，Q为两个素数，妒刀P一1G一1，XY三1ROODON、。挑战者C拥有一个可以模拟真实攻击环境的模拟器，把一组数工，E，“，T输入S，希望能够得到满足XBE的B。随机选取一个用户群三，设用户四为签名人，周期为F，1FT，E是第F个周期的私钥，公开系统参数X，1I，T，XTITE，E，H1，H2。S允许攻击者A查询三种形式预言机签名预言机查询，哈希预言机查询和“BREAKIN”查询。S拥有两张查询表，签名查询表和哈希查询表，分别用来保存签名和哈希预言机查询结果。不失一般性，A不会查询到多次相同结果；但是么可能对相同的消息进行多次签名查询。签名预言机查询由于S控制着签名预言机，它能随机的回答么的签名查询。么的第S次签名查询，希望查询第，。周期对消息M的签名，随机选择两个数仃，口，OG，经典语录HTTP/WWWYULUME西南交通大学硕士研究生学位论文第31页口乏，计算TXTLTS仃一口X1,E，并计算巳LEXN卜仃，尸，查询是否在签名查询表中，若在，将疋，仃替换为疋，CR，并将放入签名查询表，F。，疋，仃发给攻击者4。哈希预言机查询哈希预言机查询也能同时作随机应答。A的第H次哈希预言机查询，希望查询第周期的预言值，查询聊IL三LLC。的哈希值，计算巳。EXTLTE，H2聊II三IIC。QP疋，E，并在签名查询表中查询含有C州的签名是否存在，若在，返回一个口给A，否则，随机选择口的值，将乃，厶所，L，CX小口保存在哈希查询表中，并将口作为查询结果返回给A。“BREAKIN”查询么要求获得第，周期私钥。当A在第，个周期进行“BREAKIN查询，若，12得到B，使得XBE。证明如果存在，YE，那么X7DIEIXL，即XTIDIL。孝表示GCDX，F1的概率，当X为素数时，F与X互素的概率孝12。这样GCDX,F1，存在两个整数LA，DZ。，有XOI1。所以，1AX7OILLAX，OIL1AX，U戈卜1DXTI1AXLOD，综上所述，就是西南交通大学硕士研究生学位论文第32页要求的B。下面分析一下攻击成功的概率S模拟失败的概率最大值为G。G黼12。，因为哈希值被看作是均匀分布的，哈希值的选择冲突的概率应该不超过G心112。若攻击者攻破方案的概率为占，模拟机失败的概率最大值为G。PG胁12。，所以，当模拟机返回完成所有的询问后，攻击者能伪造出有效签名的概率至少为万占一G。G黼12。令点表示彳在第F2FT1周期进行“BREAKIN”预言机查询条件下，伪造有效R1签名的概率。显然万点。选择做某一周期私钥的概率为1T。T2令PH，表示彳在获得第F个周期的私钥，根据第H次哈希查询的结果，伪造有效签G耐1名的概率。万P幻。S表示长度为珀勺足够长的字符串，它是彳在进行第办次哈希HL查询之前的哈希查询应答。令仇，表示A获得第I个周期私钥的概率，根据第H次哈希Y苣NNNS，伪造有效签名的概率为2TPH。，PH，。SE0，1两次模拟过程是独立的，对于固定的哈希值，在获得第I周期的私钥后，攻击者伪造有效签名的概率为菇刚，得到两次不同签名的概率为PH，PH，12，这样就可以计算出在得到第I周期的私钥后，两次第H次的哈希查询返回结果不同，令，为成功伪造签名的概率，则纵，垦D堕攀2一，矗。一2一T仇。掣一2一办，露厂2一T见，56成功伪造签名的总概率为吼，著PJ丢2“鲵一G黼07HL12“巧57打L打皇1QD幽T上当E值不固定为某一周期私钥时，解决RSA问题的概率为占事篓C羔。殒一寿P8，攻击者么选择的用户群一般有刀个成员，每个成员被选作签名人的概率为1N，当攻击者彳成功伪造有效签名后，攻击者彳攻破方案的概率为占占N。经典语录HTTP/WWWYULUME西南交通大学硕士研究生学位论文第33页53标准模型下基于身份的前向安全环签名近年来，数字签名方案的安全性大多都依赖于随机预言模型，但是CANETTI、GOLDREIEH和HALEVI等人【4S】证明签名和加密方案，在ROM下是可证明安全的，但在实际中不会有任何安全的实现。这是因为这些方案在ROM下证明安全时，都是假设签名或加密的明文是均匀随机的。但是，在真实世界中，不存在均匀随机的明文或签名，所以在任何实际中的实现都显然是不安全的。而在标准模型下证明方案的安全性时则不需要均匀随机这个假设，因此，标准模型下的签名方案在现实生活中更有实用价值。王玲玲等【49】提出一种基于双线性对的前向安全环签名方案。该方案全面考虑了攻击者的实际攻击能力，结合前向安全的性质，新方案的安全性与一般环签名方案相比，有了明显的增强。标准模型下的签名方案是基于一类新的安全假设，文献49】中的新安全假设为研，ZDSJSDH问题。新方案还结合了双线性对计算快速，存储量小的特点，使得新的环签名方案在效率上优于一般的环签名方案。针对密钥泄露问题，结合第4章AUMANHO环签名和44节的改进方案，本节提出了一个新的基于身份的前向安全环签名，而且新方案在标准模型下是可证安全的。531安全性模型如果标准模型下基于身份的前向安全环签名是安全的，那么它应该满足不可伪造性、无条件匿名性、前向安全性。假设签名方案在有效期内被划分了丁个时期，攻击者为4。当证明标准模型下基于身份的前向安全环签名方案是不可伪造时，郎证明第，1，R时期的签名是否可以伪造。假设攻击者通过某种方式已经获得第，时期的私钥，然后再伪造第，周期的签名。如果伪造成功，说明4对这个签名方案的伪造攻击是成功的。如果成功伪造一个有效签名与某种难解问题有关，说明攻击成功的概率是可以忽略的，那么签名方案是安全的。假设4得知第，时期私钥时，因为基于某种困难问题，却不能以不可忽略的概率得到之前某周期的密钥，那么签名方案是具有前向安全性质的。当证明具有前向安全性的签名方案的不可伪造性时，可以假设该方案是不具有前向安全性的，这样一来，就可以利用标准模型下基于身份的环签名的不可伪造攻击模型，如果在此模型下证明了签名方案是不可伪造的，那么原签名方案也是不可伪造的。下面重点介绍一下标准模型下基于身份的环签名的不可伪造攻击模型。对于一个标准模型下基于身份的环签名而言，伪造攻击者通过选取消息与用户集，西南交通大学硕士研究生学位论文第34页便能任意伪造一个有效的签名，如果这种情况是不可能的，那么签名方案是安全的。评价一个方案是否安全，主要从以下两个方面入手1适应选择消息的攻击；2适应选择身份的攻击。选择消息攻击是允许攻击者在伪造攻击中要求并获得相应的消息签名对；而选择身份的攻击允许攻击者自己选择用户成员来伪造签名。假设攻击者是利用如下两种预言访问模型来进行选择消息与身份的攻击。私钥生成预言输入某用户的标识ID，可以得到该用户的公钥PK，。输入签名所在的时间段，则返回私钥D，预言指定返回的值是唯一的，即ID，ID，必有D，Z签名预言攻击者先选择，Z个用户，其身份标识分别是尬，江1，2，刀，然后选择消息M，询问签名预言后，返回一个有效的签名。在询问签名预言中，可以同时询问私钥生成预言。一个拥有私钥生成预言与签名预言的攻击者，在输入一系列用户身份标识的数据后，对于预言未曾询问的用户身份和消息，能够成功地伪造一个有效的签名，那么攻击者的伪造攻击是成功的。假设4是攻击者，下面以概率的形式表示攻击者伪造成功的公式ADV_PRASUCCEEDS】59定义531如果攻击者4最多用时间T，至少以概率占，对私钥生成预言和签名预言分别进行了次数不多于吼与吼的询问，那么就称这个攻击者A是一个S，F，吼，吼伪造攻击者。对于一个签名方案，占，F，吼，吼伪造攻击者是不存在的，那么这个签名方案不存在S，F，Q。，Q，伪造攻击。5。3。2标准模型下基于身份的前向安全环签名方案新方案如F令LO，1一O，1，风O，1专0，1是两个抗碰撞的哈希函数，其中玩，ZP，这两个哈希函数用于将任意长度的身份信息与消息转化成指定长度的二进制值。SETUP选择一个双线性对EG1G1专G2，G1的阶是P。令G为G1的生成元，任意选择口冗ZP，92贾GL，并计算GLG“。再选择如下随机值甜RG1五，月G1其中I1，2，玩，同时令U五，签名的有效期分为R个时期，公开参数是经典语录HTTP/WWWYULUME西南交通大学硕士研究生学位论文第35页P，GI，G2，G，G。，G，ZF，痧，主密钥是醪。EXTRACT对具有身份标识111的用户歹来说，我们有甜，玩哆，令甜，I1为“，的第I比特，定义集合MC1，2，玩是甜，I11的指数集合。随机选择乞，只乙，构造初始私钥DJO，如下“N矧五，D。爵彤，G510为便于书写，我们可以把私钥的两部分简单记为叫13，彰碧，其中D裟彰U，“，巧IGK。令三玛，织作为所有用户身份标识的集合。UPDATE假设系统进入F时段，1FT，用户第F一1时段的私钥为T卜。巧上，一DJ2一。，歹1，2，胛，这一时段随机选取，I_F，眨，。，尺ZP，放入集合月；计算GB，G，G。，放入集合G，然后再计算M。HMG钆，G吃”，G。M。刀作为M的二进制中第I比特，如果M。司1，那么就把I放入集合M中，集合MC1，T，叫1旦“，巧2。G，曼“511F一1时段的私钥会马上被系统删除。SIGN选取消息M，用户群上，选取皿为真实签名人，相应的密钥为以，碳；，瑚。将集合G中的元素取出，得到M以聊LF五|LGRLG弦F，GK再计算U“。兀剧。五，歹1，2，刀，将集合R，G的元素应用到签名中，则盯碟叼兀飞G气F，矿”，碟矿”，GK，矿512J暑L签名完成后立刻删除集合R，G。以上的签名可以简单表示为仃，R，R，B，。VERIFY验证者持有用户身份列表，即身份标识集合L玛，蛾和签名者签署的消息M。首先计算“，鼠哆，Q“兀剧五，J1，2，”，并检验P形，GP92，G，NEVJ，RJ，513JL是否成立。若成立，签名有效；否则签名无效。西南交通大学硕士研究生学位论文第36页533安全性分析的。1正确性只要证明PK，GEG，G。兀PU，R川成立，那么签名过程就是正确JLEE，GP碟W兀Q，GJ1P92，GEU1气。，GP虬K一”，GP以“K“一，GPUKF，GPD璺一，一E1M1“，GPFLU,B，GPURZTM，GE虬。，GPU”，G丌C，PD璺，GPU。“M，GP弘T，GPU。乞F”，GEU州KU，GPU”，GPD鬟L虬EHMB，GE虬，TIMI钆，GEU11，GP皈白，M，GP磁虬“M，GE虬”M，亿，GP皈K，”，GE己厂川K1”，GPU。名”，GPD璺；2,GPUERML“，GP，EVMLB，GPU1一，GPU，M，GEU，K，GPU。”，GPD，GP”M，GPU。“M，GP”M，G丌，P虬“M，GEU1气，GP虬白。”，GPU。1珞“”，GPU名一，GK，M圭N。PDJ，GPU亿，GPU。QLTEAGQ。，GP虬。岛“”，GPU，GP以。K1，GPUK，G。，M圭兀。PG；UK，GPUK，GPU”“坞，GPU。K1”，GPUH，G。O，M圭兀_。PG；，GPU气，GPU”“怕，GEU。“”，GP虬K。，G气，名，M圭IL。E92，G“口U，G气P虬，G”“5帕PUL，GP乩K。，GE92，G“PU，G_，叩U，D2，GK一”PU1，GKL，叩乩，GE92，91PU1，RT，PU，R列EUL，疋L，EU。，R。，5】4经典语录HTTP/WWWYULUME西南交通大学硕士研究生学位论文第37页综上所述，T时期签名过程是正确的。2无条件匿名性F时期的签名结果为仃，R，R2，R州，R，F1，HIY“KM名，NQ在每个时期签名者由选择不同的随机序列产生的，而R。，G”“啪与其它随机MF兀，产生的元素E，没有任何区别。另外，GUKU。”1嘶U，UK，也没有实际签名者的任何信息，在这样的情况下，攻击者是无法猜测到真实签名人，那么这个方案满足无条件匿名性。3不可伪造性该方案的不可伪造性是基于CDH问题计算的困难性，那么何为CDH问题计算的困难性简要介绍一下CDH问题的定义。定义452给定一个阶为大素数P的群G，生成元为G，随机选择口，BZ，94，96G，那么在群G中的CDH问题为计算G神。如果没有算法可以在时间T内，以最小的概率占解决在群G中CDH问题，我们称之为在群G中的，R一CDH假设。下面详细地证明了方案的签名是具有不可伪造性的。定理451假如在G1中存在S，F一CDH假设，其中占。二一5】52”3G。G。”NO1”Q，船。1TFD9。力。G，”RT。PG。NQ，R516在G1中，P和F分别指乘法运算时间和指数运算时间，那么对新的基于身份的前向安全环签名方案是不能进行S，F，吼，吼伪造攻击的。证明类似于文献271。当前周期为F。假设存在一个S，T，Q。，Q，攻击者A，获得了第F周期的密钥之后，4能成功地伪造之前某一周期的签名，并且消息与用户身份从未被访问，这样就可以构造一个概率多项式时间算法召，它可以利用，T，Q。，Q，攻击者4，在不超过时间F内，至少以占的概率情况下，就可以解决删问题，这里的S是指在这一时期攻破签名的最小概率。召仿真了一个挑战者与两个预言私钥生成预言和签名预言，F，吼，吼攻击者么伪造一个签名。将群G1，生成元G以及94，96G1作为已知条件赋予舀，利用攻击者么伪造的签名，舀可以计算出G曲，从而可以解决一个CDH问题。吼，纵，为已知的定值，令乙2Q。玑，乙2Q。，有乞仇1PRTNA,ANB,NANBPRN4NANN局NB】这里的事件N彳，NA与N局NB是相互独立的。I111一方面，PR】2P州0MODPNF材0MOD专志”另一方面，所以，533534PR【NQL4A】1一PRUQL互IA】L一QPR【互IA】53511TL，；1QIQLQLPRNA,NA。PR【彳PRTN4I彳】PRA11EPRA,I彳】536I1TLI1这里的互表示，也0ROOD,，I1，2，G，。因为事件五与A是相互独立的，因此PR互I爿】三；骅帮PR【