[硕士论文精品]同时签名和环签名的研究

摘要论文题目同时签名和环签名的研究学科专业应用数学研究生张馨文指导教师王尚平教授摘要签名醴墨。签名公平交换数字签名问题是密码学的一个基本问题，在电子商务中有着广泛的应用，同时签名是解决公平交换的一个新的工具。在一个同时签名方案中，两个实体共同生成两个没有绑定的签名，直到其中一方公开一个额外的信息称为“重要信息”。“重要信息”公开后，两个签名都将与它们真实的签名者同时绑定。同时签名是一种比较经济的公平交换数字签名的方法，它不需要仲裁者，这一点远远优于以往的方法，为公平交换提供了一种全新的思路，但代价是不能够达到完全的公平性。同时签名是比较经济实用的，可以在电子商务中广泛应用。而将两方同时签名方案推广到多方，被公认是同时签名研究中的一个难点和热点。现有的同时签名方案大多数是在环签名的基础上构造的，因为环签名可以被看作是简化了的群签名，它保护签名者的匿名性不被泄露，即环签名可以提供我们所需要的模糊性。因为环签名克服了群签名中群管理员权限过大的缺点，对签名者是无条件完全匿名的，所以在匿名电子选举、电子政务、电子现金系统、密钥管理中的密钥分配以及多方安全计算中都有着广泛的应用，成为当前研究的热点。本文重点研究了环签名和同时签名中的多方同时签名，并结合基于身份的签名，所作的主要工作包括1根据多方同时签名的特点，改进了DONGVUTONIEN等人提出的多方同时签名方案，将基于身份的签名结合进去，构造了一个新的基于身份的多方同时签名方案，从而使该方案将身份与公钥绑定，降低了管理成本；2通过对ZHANGKIM环签名方案的分析、改进，在1中所做的基于身份的多方同时签名方案的基础上，加以修改，重新构造了一个新的基于身份和双线性对的环签名方案，该方案比ZHANGKIM方案的效率更高。关键词数字签名；同时签名；环签名；基于身份的签名名字测试打分HTTP/WWWXINGMINGCESHIORGABSTRACTTITLERESEARCHONCONCURRENTSIGNATURESANDRINGSIGNATURESMAJOR,APPLIEDMATHEMATICSNAMEXINWENZHANGSUPERVISOR；PROFSHANGPINGWANGABSTRACTSIGNATURESIGNATURE才FAIREXCHANGEINDIGITALSIGNATURESISONEOFTHEFUNDAMENTALPROBLEMSINCRYPTOGRAPHYFAIREXCHANGEISANECESSARYFEATUREINMANYWIDESPREADAPPLICATIONSFORELECTRONICCOMMERCECONCURRENTSIGNATURESCONTRIBUTEANOVELAPPROACHFORTHETRADITIONALPROBLEMOFFAIREXCHANGEOFSIGNATURESINCONCURRENTSIGNATURESCHEMES，TWOENTITIESCALLPRODUCETWOSIGNATURESTHATARENOTBINDING，UNTILANEXTRAPIECEOFINFORMATIONNAMELYTHEKEYSTONEISRELEASEDBYONEOFTHEPARTIESUPONRELEASEOFTHEKEYSTONE，BOTHSIGNATURESBECOMEBINDINGTOTHEIRTRUESIGNERSCONCURRENTLYCONCURRENTSIGNATURESPROVIDEAMOREECONOMICALTOOLTOREALIZEPRACTICALEXCHANGETHANTHERELIANCEONATTPITSURPASSESTHEFORMERMETHODBYFARHOWEVERITSPRICEISCANNOTACHIEVETHECOMPLETEFAIMESSGENERALLYSPEAKING，COMPAREDWITHFORMERSCHEMES，CONCURRENTSIGNATURESAREVERYEFFICIENTWHICHDONOTREQUIREASPECIALTRUSTEDTHIRDPARTY,ANDDONOTRELYONACOMPUTATIONALBALANCEBETWEENTHEPARTIESSOCONCURRENTSIGNATURESAREECONOMICALANDHAVEBEENWIDELYUSEDINELECTRONICCOMMERCEHOWEVER，THEEXPANSIONFROMTWOPARTYCONCURRENTSIGNATURESTOMULTIPARTYCONCURRENTSIGNATURESISAHOTSPOTANDDIFFICULTYMOSTEXISTINGCONCURRENTSIGNATURESARECONSTRUCTEDFROMRINGSIGNATURES，FORRINGSIGNATURESCANPROVIDEANONYMITYANDTHUSCONCURRENTSIGNATURESCONSTRUCTEDFROMRINGSIGNATUREAREAMBIGUOUSRINGSIGNATURESCANBEVIEWEDASSIMPLIFIEDGROUPSIGNATURESRINGSIGNATURESCANPROVIDEFULLANONYMITYFORTHEREISNOGROUPMANAGERINARINGSIGNATURESCHEMESORINGSIGNATURESBECOMETHEHOTSPOTANDHAVEBEENWIDELYUSEDINANONYMOUSELECTIONSELECTION，EGOVERNMENT，ELECTRONICCASHSYSTEM，KEYDISTRIBUTIONINKEYMANAGEMENTANDMULTIPARTYSECURECOMPUTATIONTHISPAPERMAINLYSTUDYONRINGSIGNATURESANDMULTIPARTYCONCURRENTSIGNATURES，COMBININGWITHIDENTITYBASEDSIGNATURESTHEMAINWORKSAREASFOLLOWS1ACCORDINGTOTHECHARACTERISTICOFCONCURRENTSIGNATURES，PROPOSEDANEWIDENTITYBASEIIABSTRACTMULTIPARTYCONCURRENTSIGNATURESCHEMEBYIMPROVINGTHEMULTIPARTYCONCURRENTSIGNATURESCHEMEPROPOSEDBYDONGVUTONIENANDCOMBININGTHEIDENTITYBASEDSIGNATURESTHENEWSCHEMEWHICHBINDINGTHEIDENTITYANDPUBLICKEYSREDUCEDTHEMANAGEMENTCOST2BYMEANSOFANALYSISONTHERINGSIGNATURESCHEMEOFZHANGKIM，PROPOSEDANEWRINGSIGNATURESCHEMEONTHEBASISOFIDENTITYBASEMULTIPARTYCONCURRENTSIGNATURESCHEMEIN1KEYWORDSDIGITALSIGNATURE；CONCURRENTSIGNATURES；RINGSIGNATURE；IDENTITYBASEDSIGNATUREILL名字测试打分HTTP/WWWXINGMINGCESHIORG独创性声明秉承祖国优良道德传统和学校的严谨学风郑重申明I本人所呈交的学位论文是我令人在导师指导下进行的研究土作及取得的成果J尽我所知、，R除特别加以标注和致谢的地方外，论文中不包含其他人的研究成果毒与我同工作的同志对本文所论述的工作和成果的任何贡献均已在论文中作了明确的说明并已致谢D，本论文及其相关资料若有不实之处；由本人承担0切相关责任论文作者签名F邀。瑚年多一月2铲臼学位论文使用授权声明本人燃二在导师的指导下创作完成毕业论文Q本人已通过论文的答辩，并已经在西安理工大学申请博士硕士学位。本人作为学位论文著作权拥有者，同意授权西安理工大学拥有学位论文的部分使用权I，即I王R已获学位的研究生按学校规定提交印刷版和电予版学位论文；一学校可以采用影印土缩印或其他复制手段保存研究生上交的学位论文，J可以将学位论文的全部或部分内容编入有关数据库进行检索；，2R为教学和科研目的学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、资料室等场所或在校园网上供校内师生阅读、浏览。本人学位论文全部或部分内容的公布J0占丹D6【A避除，J0是可忽略的。242RSA问题定义24RSA问题令，G是一个RSA生成器，输A1，在K的多项式时间输出I个2忌比特的模NPQ，其中P,Q是两个不同的均匀分布的素数，长度均为K比特；IIEZ0州川，给定CZ；求整数聊，使得满足研。CMODN。换句话说，RSA问题中，要求一个整数在模合数下的E次方根。假设22RSA假设RSA算法是一个PPT算法A，记S0为SPROBM4AE,M8B。DJ26“1名字测试打分HTTP/WWWXINGMINGCESHIORG第二章相关的密码学基础知识令，G是一个RSA生成器，输入1，在K的多项式时间内输出I一个2KBIT的模NPQ，其中P,Q是两个不同的均匀分布的素数，长度均为K比特，IIPZ0一JXQ一胪我们说，G满足RSA假设，如果对于所有充分大的K，对于任何多项式时间PPT算法A，概率占0是可忽略的。显然，整数分解问题比RSA问题难解，即，如果整数分解问题可解，则RSA问题也是可解的，反之不然。243强RSA问题定义25给定两个整数N，C，分别满足以下条件是两个不同的奇素数的P，Q的乘积；CZV；求整数对M和E，使得M。CMODN。不难看出强RSA仁RSA问题仁整数分解问题。通常用PL仁P2表示存在一个多项式时间的将问题PL规约为问题P2的一个算法，即可以借助于求解问题P2的算法求解问题P1。即在多项式时间算法内解决强RSA问题不如解决RSA问题困难而后者又不如解决整数分解问题困难，即如果整数分解问题可解存在多项式时间算法，则RSA问题也是可解的也存在多项式时间的算法，进而强RSA问题也是可解的。反之不然。244离散对数问题DLP定义26离散对数问题DLP给定素数P及Z；的两个独立的元素口，Z，；求关于口的离散对数。也即，要在O，P一2中找出使下式惟一成立的整数X口。MODP。在现有的计算能力下，已知口，X计算口5MODP是容易的；但已知口，计算满足口。MODP的整数X，在计算上却是困难的，即不存在多项式算法解决它。245DIFFIEHEIIMAN问题定义27计算性DIFFIEHELLMAN问题CDH设P是素数，G是Z的生成元。已知G。，GYZ其中X,Y1,P一1】是未知的，计算G砂。假设23计算性DIFFIEHELLMAN假设CDA存在多项式时间算法K，以1为输入，输出KBIT长的大素数P,G,GX,GY，其中G是ZP的生成元，GX,GY钇；对任何多项式WTILL算法A，对任何充分大的参数K，其成功解决CDH的概率是可忽略的。即PROBLG矽卜ALC1L是可以忽略的。西安理工大学硕士学位论文定义28判定性DIFFIEHELLMAN问题DDH设P是素数，G是Z。的生成元。已知G。ZP，GYZP，92ZP其中X,Y,Z1，P一1】是未知的，判定G叫和92是否相等。假设24判定性DIFFIEHELLMAN假设DDA存在多项式时间算法易，以1为输入，输出KBIT长的大素数P，G,G。若Y髫2，其中G是Z；的生成元，旷，GY，92Z；对任何多项式时间算法A，对任何充分大的参数K，其成功解决DDH的概率是可忽略的。即ILPROBIG矽92卜ALO1I是可以忽略的。LJ不难看出DDH乍CDHDLP。即，在多项式时间算法内解决DDH问题不如解决CDH问题困难，而后者又不如解决DLP问题困难，求解DDH，CDH，DLP的难度是递增的。25本章小结本章介绍了密码学中的一些基本知识，包括数论、群论、哈希函数、椭圆曲线及双线性对的相关知识，以及相关的困难问题及假设。这些都是网络信息安全所必需的基础理论。密码学正是以数学为基础来完善密码理论与算法的，也正是这些数学知识保证了密码体制的安全性。12名字测试打分HTTP/WWWXINGMINGCESHIORG第三章同时签名3同时签名31数字签名的基本原理311密码体制保密是密码学的核心，而实现保密的实用工具就是加密。现代加密可以看成是一个数学变换，将明文消息空间M中的元素在加密密钥空间K中的一个元素的作用下映射到密文空间C，可以认为是将“有意义的消息“映射为“不可理解的消息”，这一过程称为加密，使用的映射称为加密算法E。为了恢复明文消息，要求加密映射是可逆的，逆映射称为解密算法D。即将密文空间C中的元素在解密密钥空间K的一个元素的作用下映射到明文消息空间M中。通常加密算法和解密算法再加上消息和密钥的形式描述就构成了一个密码体制。明文图31密码体制模型FI931CRYPTOSYSTEMMODEL如图31就是一个典型的密码体制模型，其中屯K，为加密密钥；KK7，为解密密钥。如果KEK，称为单钥密码体制或对称密码体制，否则称为双钥非对称密码体制或公钥密码体制。单钥密码体制中通信主体共享一个密钥，既可用于数据加密，也可用于消息认证。公钥密码体制能用于数据加密、数字签名和公开信道的密钥建立。其中，七。公开，通常用于消息加密和签名认证；而K保密，通常用于解密和签名。为了提供保密性，抗击密码攻击，一个好的密码体制需要满足以下性质1系统至少要达到计算上安全，即从截获的密文或已知的某些明文、密文对，要决定密钥或任意明文在计算上不可行2E和D不包括保密成分，即遵守KERCHOFF原则；3E和D适用于所有密钥空间中的元素；4系统便于实现和使用方便。西安理工大学硕士学位论文312数字签名原理简单地说，数字签名就是两个数学变换发送方对信息施以数学变换后发送，接受方进行逆变换得到原始信息。发送方的变换就是签名，通常是一种加密；对应的逆变换就是对签名的认证，通常是一种解密措施。数字签名体制一般包括两个部分一个是签名部分，对消息K做签名，可以记为SSIGNK，M，其中K是签名者的私钥，是秘密的；另一个是接收方的认证部分，记为VERS，M真，假。如下图所示较图32数字签名FIG32DIGITALSIGNATURE313数字签名的特点数字签名具有如下特性1签名是可信的任何人都可以方便的验证签名的有效性；2签名是不可伪造的除了合法的签名者外，任何其他人伪造签名是困难的，这种困难性指计算上是不可行的；3签名是不可复制的如果签名是从别的地方复制的，任何人都可发现消息与签名的不一致，从而拒绝签名；4签名的消息是不可改变的经过验证的签名不能被篡改；5签名是不可抵赖的签名者不能否认自己的签名。常用的数字签名算法有RSA、DSA、RABIN、EIGAMAL、SCHNORR等，现今普遍使用的数字签名算法，一般都是基于下面的三个数学难题之上的1整数的因子分解INTEGERFACTORIZIONIH题，比如RSA算法；2离散对数难题DISCRETELOGARITHIMPROBLOME，比如DSA；3椭圆曲线离散对数难题ELLIPTICCURVEDISCRETEPROBLOME，比如ECDSA。14名字测试打分HTTP/WWWXINGMINGCESHIORG第三章同时签名32同时签名基本原理321同时签名的提出及基本概念考虑这样的一个场景，ALICE想从BOB的商店中购买一台笔记本电脑。ALICE签署了一个支付指令给BOB以支付该电脑的价格，而BOB通过签署一个收条来表示同意并认证ALICE可以从他的商店取走笔记本电脑。我们需要实现这样的公平ALICE和BOB的签名将被同时绑定。也就是说，当ALICE从BOB的商店取走笔记本电脑时，ALICE的支付指令将被绑定，同时BOB的收条也将被绑定。这就是公平交易中同时签名应用的一个典型场景。对公平交易的早期研究，着重于逐步释放秘密来获得同时性和公平性，其主要思想是双方轮流释放一部分秘密，这样双方都不会比对方得到更多的优势11720|。这种方法的缺点是计算和交互的开销太大，并且要依赖于双方计算能力的平衡，而且实际执行也很困难比如说异常终止。一个替代方案是利用一个可信第三方TTP来实现公平性T21,221。一个可信第三方本质上是一个可解决参与者争端的仲裁者。仲裁者既可以是在线的，参与每次交易；也可以是离线的，只有在发生错误时比如，某个参与方企图欺骗或攻击，或者参与方之间交互的延迟太大令人无法忍受等等参与交易。离线的方式也被称为是优化的。这种方法的缺点是，协议中的TTP必须是完全可被信任的，他的功能甚至超过了CA，这点并不理想。同时，由于有第三方的参与，降低了效率。为了解决以上问题，2004年陈立群等首次提出了同时签名的概念1231。同时签名是指，双方各自对消息分别作不确定的模糊签名。因为两个签名者都可以独自生成这个签名，所以任何第三方不能把这两个模糊签名和签名者的身份对应起来，即第三方无法断定究竟是谁做了哪个签名，除非其中的某一方公布一个“重要信息“。该“重要信息“被公开后，这两个签名就同时和签名者的身份绑定起来了。在“重要信息”被公开以前，签名被称为模糊签名AMBIGUOUSSIGNATURE，此时签名和签名者的身份没有绑定，签名者与签名的关系是不确定的；一旦“重要信息“被公布，我们就称签名为同时签名，此时两个签名与其对应的签名者的身份被同时绑定。322同时签名的基本算法一个同时签名方案主要包括以下算法SETUP生成算法根据输入的安全参数，输出各个系统参数，哈希函数KGEN，及参与双方的公、私钥对；SIGN签名算法关于消息M生成模糊签名的概率算法；AVERIFY模糊验证算法验证模糊签名的有效性；VERIFY验证算法在重要信息公布后验证签名的有效性。基本的同时签名方案都包括以上的4种算法，其它的同时签名方案，如非对称同时签西安理工大学硕士学位论文名方案、多方同时签名方案等有时会根据需要将算法SIGN分为两个ISIGN和SSIGN算法在非对称同时签名中发起签名者和响应签名者的生成算法是不同的，将算法AVERIFY分为INSIDERVERIFY重要信息公布前环内签名者的验证算法、OUTSIDERVERIFY局外人的验证算法和BINDINGVERIFY重要信息公布后任何人用来验证签名的有效性及绑定性。323同时签名的基本运行模式同时签名的运做如下所示假设签名者A与B要分别交换关于消息M4和M口的签名彳BK重要信息的像厂F,模糊签名盯J2_A验证仃口的有效性彳公开重要信息K曰验证盯一的有效性厂哼模糊签名盯口发起签名者彳选择了一个随机数作为重要信息K，并对K做哈希得到重要信息的像厂，利用厂与自己的私钥和响应签名者曰的公钥执行签名算法，生成了关于消息M。的模糊签名盯。，然后将盯。发送给B；响应签名者召收到吼后，首先验证仃一的有效性。如果盯一有效，B利用厂与自己的私钥和发起签名者么的公钥执行签名算法，生成了关于消息M。的模糊签名盯。，然后将盯。发送给彳；彳收到盯口后，验证仃丑的有效性。如果仃口有效，彳公开重要信息K，将盯与盯口同时绑定；此时把签名对吼，K与仃口，K就称为同时签名。33几个具体的同时签名方案331第一个同时签名方案2004年，陈立群等首次提出了同时签名这个概念231，并且基于SCHNORR环签名方案的一个变形提出了第一个同时签名方案。这个方案可以说是同时签名的开山之作，为大家对于研究数字签名的公平交换提供了一个新的思路和工具。该方案包括以下4个算法SETUP生成算法这是一个概率性算法，生成了包括密钥在内的所有参数。该16名字测试打分HTTP/WWWXINGMINGCESHIORG第三章同时签名算法选择两个大素数P，Q其中QQPJ和一个阶为G的生成员GEZ。，同时生成了密码学哈希函数日，皿P，玎一ZQ，A1ICE和BOB是参与该协议的双方。在生成算法完成之后，ALICE获得了她的私钥_ZQ及相应的公钥Y爿G霸ROODP；BOB获得了他的私钥ZQ及相应的公钥Y口G柏ROODP。SIGN签名算法这是一个概率性算法。对于输入彳，YN，葺，F，其中I0，B，FH，尼，KD，11“是重要信息，输出个模糊签名Q。为了签署消息朋一，灿ICE选择了一个随机数，ZQ和重要信息七，并计算厂日，尼及办H。B7YBF。DPLIM一31H办一FROODG32_，一H一硝MODQ33该算法输出关于消息垅爿的模糊签名吼G爿，H一，F，并把它发送给BOB。AVE附1W模糊验证算法对于输入SB，Y，YJ，M，该算法输出“接受”或拒绝”。对于ALICE发送过来的模糊签名SP，Y一，Y口，M爿，B0B验证等式H_厂H。G“YBYBFM。DP0M月似。DQ34是否成立。如果成立，接受这个模糊签名，否则，拒绝。如果BOB接受了这个模糊签名，他使用一，Y丑，厂对消息肌口做模糊签名仃口G丑，H口，F，其中乃H。G，YSFM。DP0M口35H口JIL厂BODQ36J口，H口X口ROODQ37，7是Z。中的随机数。BOB将这个签名发送给A1ICE。接收到这个模糊签名盯口后，A1ICE首先检验厂是否与她以前使用过的相同。如果不是，终止协议，否则，ALICE验证等式H曰厂H。K“Y口BYAFM。DPILM曰M。DQ38是否成立。如果成立，发送K给BOB。卅E砒IIY验证算法该算法对于输入S，首先检验日，厂是否成立。如果不成立，终止协议，否则，运行“模糊验证算法”验证墨。西安理工大学硕士学位论文口。和仃。都提供签名者身份的模糊性，当重要信息K被其中一方公开后，模糊性解除，签名者的身份随之公开，两个签名也就同时绑定了，因而也就达到了公平地交换签名的目的。332完善同时签名方案同年，WILLYSUSILO等指出，陈立群提出的同时签名方案无法为签名者提供充分的模糊性和匿名性当签名双方都是诚实地执行协议时，并进一步提出了“完善同时签名”这个概念2们。WILLYSUSILO首先在文中分析了同时签名的模糊性。对于由签名者么，B生成并已经公开的两个模糊签名盯，仃，任意第三方都可以得到以下4个结论中的任意一个1两个模糊签名仃，仃，都是由签名者彳生成的；2两个模糊签名仃，仃，都是由签名者曰生成的；3仃，由签名者彳生成，盯，由签名者曰生成；4仃，由签名者B生成，盯，由签名者彳生成。一个同时签名方案要想具有充分的模糊性和匿名性，任何第三方判断谁是真正的签名者的概率都不应当大于14，也就是猜测的概率不应当大于14。在陈立群的方案中，如果签名双方都是诚实的，也就是两个签名者都诚实地遵守了协议，那么上述前两种情形由一个签名者生成两个签名的情况就不会出现。假设彳、曰诚实地遵守协议，分别生成了签名仃，G一，H爿，F、G占，H口，F，由前面的协议可知，任意第三方要验证盯，就必须使用Y占，要验证吒就必须使用Y，。因此，如果签名经验证有效，那么任意第三方就可以确定真实的签名者，也就是仃，由签名者A生成，吒由签名者B生成。为了使同时签名达到充分的模糊性和匿名性，WILLYSUSILO对陈立群的方案进行修改，构造了完善同时签名方案。要达到完善的匿名性，在任意第三方看来，两个签名之间应当没有任何明确的联系在陈立群的方案中，很显然，厂使用了两次，两个签名中都有厂。也就是说，两个模糊签名之间的联系只有签名者知道，任意第三方都无法区分这两个签名。WILLYSUSILO的完善同时签名方案包括以下4个算法一ETUP选择两个大素数P，QBLPJ和一个阶为Q的生成员GZ。，同时生成了密码学哈希函数H，D，盯一Z。，设MKZ。，在生成算法完成之后，A获得了她的私钥_ZQ及相应的公钥Y一G砀NODP；B获得了他的私钥乙及相应的公钥Y矗G钿MODP。ASIGN对于输入J，Y，XI，曼川J，其中YF，YJ为公钥且MY，XI是相对于YF的私钥，JF，M是要签名的消息，该算法如下运行名字测试打分HTTP/WWWXINGMINGCESHIORG第三章同时签名1选择一个随机数口Z。；2计算C日，B，98YJ。DP；3计算F一CK,NODG；4输出盯0，F，J。制EML对于输入B，YI，YJ，肌，其中盯C，歹，；，YL，乃是公钥且消息聊M，该算法验证下面的等式是否成立CH，B，G。Y，亨YJ。DP如果成立，输出“接受“否则输出“拒绝”。VEL吖对于输入仗，S，其中KK是重要信息，39SB，盯，YI，YJ，盯G，亨，；，该算法验证K的值是否有效。如果有效，甬TAVERIFYS，VERIFY的输出结果也就是AVERIFY的输出结果。根据以上算法，WILLYSUSILO提出了一个具体的同时签名协议。不失一般性地，假设彳是发起签名者，B是响应签名者。在运行协议之前，假设SETUP算法已经执行过了，并且已经将公钥儿和儿公开。协议如下1彳进行以下工作选择一个消息M。M；选择一个随机数KK，令已；运行吼七ASIGNY一，YB，_，已，M爿获得模糊签名O“A0，F，屯，并令S，F；选择一个随机数F乙并计算FY,4ROODP；公布B_，O“A，F，其中；G，S，屯并发送这个值给B。2在接收到彳的模糊签名后，B验证AVEMFY0“A，YA，YS，的输出结果是否等于“接受“。如果不是，终止协议，否则执行下面的工作选择一个消息M；计算，卜扣ROODP；令S，卜屯，似。DG；运行卜ASIGNY，脚口模糊签名C，占，J；19西安理工大学硕士学位论文令S2七_2；公布口，其中F，C，S。、】并发送这个值给彳。3在接收到B的签名M口，后，B执行下列操作验证AVE砒1WH，Y一，YS，L,N口“接受是否成立。如果不成立，终止协议，否则计算厂S，一S2如ODQ；验证等式，YS一西DDP是非成立。如果不成立，终止协议，否则进行知识证明FSPKEQJ，妒尹G妒人YAGRXK；公布重要信息KK，R，R，I，使两个签名同时绑定。WILLYSUSILO将陈立群等人的同时签名概念进行推广，提出了完善同时签名的概念，提高了签名者的模糊性和匿名性，是同时签名发展史上的一大贡献，以后的很多同时签名方案都受到了该方案的启发和影响。333非对称同时签名环签名可以提供同时签名所需的匿名性，因而过去的同时签名方案都是基于环签名的。2005年，KHANHNGUYEN黜了一种全新的同时签名方案非对称同时签名屹61。这种同时签名不是基于环签名的，它与以前基于环签名的同时签名最大区别在于，发起签名者的签名算法与响应签名者的签名算法是不同的，因此称之为非对称同时签名。在KHANHNGUYEN的方案中，他把以前的同时签名的签名算法ASIGN分为两个发起签名者的签名算法ISIGN和响应签名者的签名算法SSIGN；相应地，对模糊签名的验证算法AVERIFY也分为两个IVERIFY和SVERIFY。因此，非对称同时签名包括以下6个算法SETUP对于输入的安全参数，该算法输出公开参数P，Q其中QP1和一个阶为Q的生成员GZ，密钥空间KZ。，消息空间M矽，密钥的像空间FZ，参与双方的私钥墨与相对应的公钥X，G而；哈希函数恩强GG。，阳ENJKXJ，YZKTRANS,XJJ勺；一SIGN对于输入陇，XI，M，该算法产生一个随机数RZQ，返回签名的SCHILORR承诺QG，C，其中C日G7，M。，S97Q；名字测试打分HTTP/WWWXINGMINGCESHIORG第三章同时签名一SIGN对于输入SJ，鸭和S，该算法产生一个随机数，ZQ，返回签名的类似SCHILORR承诺G，KJ，C，其中JS，CP撇7SM，K，R一C_MODG；IVE砌LIY对于输入QG，C，如果CH缸，。，M。，该算法输出“接受”，否则输出“拒绝；SVE砒I吖对于输入G，尼，C，如果CT日K置S鸩，该算法输出接受”，否则输出“拒绝”；_VE砌1W对于输入后和QG，C或者是尼和W，G，尼，C，如果KGENKJ且IVERIFYH接受或者是的疆W，JJ|_SVERIFYW，接受，该算法输出“接受”。非对称同时签名方案的提出颠覆了以往的同时签名方案，它不是基于环签名的，这为构造同时签名提供了新的思路。不过，由于发起签名者和响应签名者的签名算法不相同，这可能会造成签名的公平性难以实现，尤其是对响应签名者而言。这也是有待改进的地方。334三方同时签名2007年，WILLYSUSILO和YIMU将同时签名的概念推广到了三方同时签名眩91。这是第一次突破了两方同时签名的局限，虽然他们提出的这个三方同时签名本身不能推广到多方场景，但还是为同时签名在多方场景下的应用带来了新思路，为后来多方同时签名方案的提出奠定了基础。3341三方同时签名算法一个三方同时签名包含以下算法SETUP输入安全参数，该算法输出签名者的集合【，所有参与者的公钥P相对应的私钥是S，消息空间M，重要信息空间K，重要信息的像的空间，以及其他系统公共参数PARAMS，和一个函数KGENKF；ASIGN输入B，厂，鼻，E，只，SI，其中FF，MM，名，弓和E是签名者的公钥而S，是与只相对应的私钥，该算法输出关于M的一个模糊签名S；AVE眦1W输入B，厂，盯，鼻，弓，最，其中FF，MM，只，弓和只是签名者的公钥，盯S，输出“接受”或“拒绝”；枷LEASE该算法接受厂F和关于消息B，M，M。的有效签名B，OJ，吼，输出在函数FKGENK中使用过的正确的值KK以及一些重要的信，皂,INFO以确定公开的签名PROOFVE砒FY输入重要信息KK，一个重要信息的像厂F，以及一些由RELEASE算法所产生的必需的信息INFO，该算法验证重要信息和INFO的J下确性。如果它2I西安理工大学硕士学位论文们正确，输出“接受”，否则，输出“拒绝”；VE砒1W输入厂，K，盯和由RELEASE算法所产生的必需的信息INFO，并执行PROOFVERIFYK，F，坳算法和AVEIULWK，厂，O“U，只，只，最算法，输出“接受”或“拒绝”；一DENY输入B，F，吼，0“2，只，E，最，S，其中MM，FF，只，鼻和只是签名者的公钥，S，是与层相对应的私钥，仃，盯S，该算法验证这两个签名是否有效，即是否通过了AVERIFY算法，并且确定其中一个是伪造的。如果发生了伪造，输出“接受”，否则，输出“拒绝”。3342三方同时签名方案我们描述的三方同时签名协议发生在三方彳、曰和C之间。其中一方需要生成一个重要信息并发送第一个模糊签名给其它两方，我们把这一方称为发起签名者；接着，另一方需要用相同的重要信息的像生成一个模糊签名以响应发起签名，我们把这一方称为第一响应签名者；最后，第三方将生成他自己的模糊签名以响应前两个签名，我们把他称为第二响应签名者。不失一般性地，我们假设彳是发起签名者，B是第一响应签名者，C是第二响应签名者。协议如下运行彳、B和C运行SETUP算法确定这个方案的公开参数。我们把签名者F的公、私钥分别记为只和J，其中FA，B，C。1A选择一个随机的重要信息KK并计算厂硒E七，然后4生成他关于消息M一的模糊签名ASIGNM彳，F，只，已，尼，S彳，并发送给曰和C；2在收到彳的模糊签名矿。后，B和C通过AVERIFY算法验证签名的有效性。如果无效，曰和C终止协议；否则，曰选择一个消息M。M，使用相同的重要信息生成他的模糊签名盯口ASIGNM口，F，只，兄，忍，并发送给4和C；3在收到B的模糊签名仃疗后，彳和C通过AVERIFY算法验证签名的有效性。如果无效，么和C终止协议；否则，C选择一个消息MRM，使用相同的重要信息厂F做出他的模糊签名盯CASIGNMC，只，B，芝，SC，并发送给彳和曰；4在收到C的模糊签名后，彳和B通过AVERIFY算法验证签名的有效性。如果无效，4和曰终止协议；否则，么执行VERIFY算法公开重要信息K及其他一些信息INFO给曰和C。这时，所有签名都被同时绑定了。3343一个具体的三方同时签名协议我们假设签名者为U，I彳，B，C，协议如下运行SETUP输入安全参数，该算法均匀分布的随机数组PARAMSP，GI，G0，E，P，其中Q是阶为Q的循环加法群，是阶为Q的循环乘法群，E为双线性映射EG1XG1专吒，P是Q的一个生成元。该算法同时选择私钥SZQ并计算厶。SP。名字测试打分HTTP/WWWXINGMINGCESHIORG第三章同时签名公开两个密码学哈希函数O，1一G1和H，O，L，寸ZQ。每个签名者以I0，B，C选择他们的私钥S，并公开公钥EP；ASIGN输入B，F，只，E，只，T，其中只J，尸，SI是的私钥，只，弓和圪是，U，和U。的公钥，MM，FF，该算法执行下面的操作选择一个随机数，乙；计算MBLI厂；计算Q，墨似一，心只和QRP；输出关于M的签名13R9，QAVERIFY输入B，F，仃，E，最，其中盯，Q，MM，FF，验证等式P包，只弘娩，EAP。II厂L尸是否成立。如果不成立，该算法输出拒绝”，否则，输出“接受”RELEASE输入后K和酝，QIAQ2一强B口，切口，Q2口池BC，OLC,QC一个有效的签名列，其中Q匕，Q。如果每一个B，匕，Q嘞都通过了AVE融IIY算法，则计算锡Q7和瓯墨02。，其中把“通过ASIGN算法生成的签名Q记为Q2“；产生下面的知识证明11ECSPKEQK岛心瓯诅虹310输出扩，岛QC，级，11，其中KK且日，驴K。注意的值只有发起签名者才知道，因此这个算法只有发起签名者才能执行。PROOFVERIFY在下面的描述中，我们把发起签名者记为阢。该算法验证知识证明IECSPKEQKQ【也级峨，珏是否成立。如果不成立，输出拒绝“，否则，验证下面的等式是否成立E匕，EL惦，P缸，只三E，P311PB，最魄，尸匕，E兰P，尸312如果不成立，输出“拒绝“，否则，验豇I,IEFKGENK。如果不成立，输出“拒绝，否西安理工大学硕士学位论文则，输出“接受”；VERIFY输入B，F，忽P，E，E，Q，虢，R，其中仃，Q，MM，FF，KK，该算法执行下面的操作验证H，厂K是否成立。如果不成立，输出“拒绝”；执行PROOFVERIFY算法。如果不成立，输出“拒绝”；执行AVE砒L吖K，F，O“U，名，只，最。VERIFY的输出结果就是AVERIFY的输出结果。DENY输入B，F，仃，Q，霉，只，最，S，该算法执行下面的操作验证AVE融IB，F，仃。，只，最，其中“P，2。如果不成立，就终止该算法并输出“拒绝“；计算4SIQ一MP，其中M乒SOMLS,对两个签名盯，盯，执行下面的验证E娩，只只，P二PP，P313如果上面的验证结果是仃，或盯，为真实的，则输出“接受“，否则输出“拒绝“。WILLYSUSILO等人提出的这个三方同时签名方案第一次突破了双方同时签名签名的局限，虽然这个方案本身并不能推广到多方同时签名中，但是也为后来多方同时签名方案的提出奠定了基础。34多方同时签名341多方同时签名的提出及基本运作方式同时签名在多方场景中的应用是密码学的一个新问题，也是一个难点，陈立群等曾质疑多方同时签名的存在。前不久，SUSILO等人成功地构造了一个三方同时签名方案1291但是他们的方案很难推广到多方场景。2006年，DONGVUTONIEN等人第一次提出了一个多方同时签名方案1301他们方案的核心是一个环签名。在其方案中，发起签名者选择了一个群重要信息，另外，所有的签名者都选择一个个人重要信息。这样，在所有签名者的重要信息都被公开后，签名得以绑定。简单地说，多方同时签名是这样运作的假设有G个签名者，我们把这玎个签名者称为内部成员，而把其他任何人称为外部成员以便区别。其中有一个成员【，作了第一个签名，我们把他称为发起签名者。发起签名者选择了一个群重要信息和一个个人重要信息，并把它们保持秘密。群重要信息由一个公开的哈希函数经过哈希生成群重要信息的像。使用该签名者的个人重要信息和群重要信息的像产生一个匿名的签名，然后发送这第一个模糊签名与群重要信息的像给所有成员。这个签名可以分别被外部成员与内部成员进行两个名字测试打分HTTP/WWWXINGMINGCESHIORG第三章同时签名不同层次的验证外部验证和内部验证。外部成员验证这个模糊签名是有效的却无法将这个签名与它真实的签名者联系起来。换句话说，外部成员可以确定这个签名的确是由刀个签名者中的某一个人生成的，但是却无法断定究竟是谁生成的。另一方面，内部成员可以在更深层次验证这个签名。利用自己的私钥，可以验证这个签名是由发起签名者U，签的。在所有内部成员都验证了U，的签名后，另一成员，如【，对U，做出响应。U，选择了第二个个人重要消息，并将它保持秘密。然后使用它与群重要信息的像生成了第二个模糊签名。同【，一样，U，将这个签名发送给所有成员进行两个不同层次的验证。最终，当所有用户都对他们的消息做了签名后，就进入到了重要信息公布阶段。在这个阶段，所有签名者都公开他们的个人重要信息，发起签名者也公开群重要信息。在所有重要信息都公开后，所有的签名就同时与他们的签名者绑定了。这时，任何外部成员都可以使用重要信息来验证这些签名。342多方同时签名的算法一个多方同时签名包括以下主要算法SETUP亿甩输入安全参数，和签名者的人数行，该算法输出刀个签名者的私钥SKSK，N，一个公钥豚，消息空间M，重要信息空间K重要信息的像的空间F，以及其他系统公共参数PARAMS，和一个函数KGENKF；SIGNM，PK，如，成输入一个消息M，公钥数组PK，重要信息的像的空间F，一个签名者的私钥曲，和他的个人重要消息腩，该算法输出关于M的一个匿名签名盯。这个算法是由内部成员用来生成一个匿名签名的；OUTSIDERVERIFYM，正户K，F外部验证算法输入一个消息M，一个签名盯，公钥数组雕，重要信息的像的空间，该算法输出“接受“或“拒绝“。这个算法是外部成员用来检验一个匿名签名的；一NSIDERVERIFYM，仃，胀，只ZSK内部验证算法输入一个消息M，一个签名盯，公钥数组雕，重要信息的像的空间尸，一个签名者的身份，和一个签名者的私钥曲，该算法输出“接受”或“拒绝。这个算法是一个内部成员其私钥为SK用来检验签名者，是否做了这个签名的；KEYSTONESRELEASE重要信息的公开在发起签名者公开了群重要信息贴和他的个人重要信息腩，后，并且其他签名者也公开了他们的个人重要信息访，后，该算法以下面的形式输出最终的绑定签名GK，F，IK，一，IK，M，OL，M，02，M。，ON，其中MF，Q是签名者F的签名；BINDINGVERIFY，亦，F，IK，一，IK。，M，盯，M2，吼，M。，仃。绑定验证输入公钥数组麒和一个同时签名舭，F，腩，一，IK。，M，O，M，盯，M。，仃。，该算法输出“接受”或“拒绝”。这个算法可以由任何人来验证以个签名的有效性及绑定。西安理工大学硕士学位论文343一个具体的多方同时签名方案本节我们给出DONGVUTONIEN所提出的一个具体的多方同时签名方案SETUPF，聆选择双线性对PG1G1专G2，其中G1和G2是阶为素数G的群，以及4个密码学哈希函数H，H。O，1专GL和也，H，O，1专乙；选择G1的一个生成元尸和随机数S饬，SKI，SK。ZQ，对任意的OIN，令PKF只SKIP；对任意的F【，Z】，签名者F的私钥是J屯；公钥数组是胀P，EO，E，；令K舻，JY，FGI，M乙；函数KGENK专F被定义为KGENHISIGNM，PK，F，SK，IK一个签名者使用私钥睹ST和个人重要信。IK叱对消息朋MJ进行签名，具体步骤如下对任意的IJ，N且FJ，计算和计算和HM川州FEO严G1忽皿K，IIP玉FLU,乙UJ也托湾一似哆只GI乃也M制F乙VSKIHJH4KKJFG1；这个签名是盯Y，U，以，VO。314315316317318名字测试打分HTTP/WWWXINGMINGCESHIORG第三章同时签名OUTSIDERVERIFYM，盯，PK，F对任意的FJ，刀，计算吃亿K胀护0VZ，；，升、如果等式PP，矿芒1F，P，啊PL成立，该算法输出“接受”。TLINSIDER、KRIFYM，盯，PK，Y,J,SK一个签名者F使用私钥妣S毛来检验签名者的关于消息聊M，的签名O，具体步骤如下如果H。M，F忙位，E产，那么输出“拒绝”，否则继续下面的步骤；对任意的汪J，刀，计算吃H，B，IILLP“TZQ；，N、如果等式P尸，YDF，心HIP,L成立，该算法输出“接受”。I1，BINDINGVERIFY湫，班，F，玻，一，IK。，乃，R2，M，仃，M，02，M。，如果下列等式有任何_个不成立，该算避就输出“拒绝”检验F三硒EB惫是否成立；对任意的IJ，疗，对于签名者的签名，检验啦矿三T喜眠W和P尸，矿三P忆，沁日，F尼，归320其中吩11,M,FLIPKOFII乙。35一个新的基于身份的多方同时签名方案本节根据多方同时签名的特点，改进了文献B中提出的多方同时签名方案，将基于身份的签名结合进去，构造了一个新的基于身份的多方同时签名方案，从而使该方案将身份与公钥绑定，降低了管理成本。在阐述新方案之前，我们先来简单介绍一下基于身份的签名的提出和特点。351身份密码学为了避开传统公钥加密机制中复杂的证书管理，1984年SHAMIR【311提出身份密码学27西安理工大学硕士学位论文IDENTITYBASEDCRYPTOSYSTEM简称IBC的思想，同时给出了一种建立在大整数因子分解问题基础上的身份签名机制IBS。这类方案能使网上的任何一对用户无需交换秘密密钥或公开密钥、无需保存密钥簿、无需使用第三方服务便可进行安全地通信和相互验证签名。在这类方案中，假定了存在个可信的密钥产生中心，该中心的主要作用是给每一个第一次入网的用户颁发一个个人化的SMART卡。嵌入在这个卡中的信息能使用户签名和加密他所发送的消息，并能使用户用一个完全独立的方式解密和验证他所收到的消息。SHAMIR基于身份的密码方案仍然是一类公钥密码方案，但它不是直接生成一对随机的公开密钥和秘密密钥，而是由用户选择他的名字和网络地址等来作为公开密钥。当用户入网时，密钥产生中心首先对用户进行识别。如果接纳用户，密钥产生中心就为该用户颁布一个秘密密钥。于是，当