[硕士论文精品]基于身份环签名的研究

山东大学博士学位论文摘要随着计算机和网络技术的快速发展，人类生活方式发生了巨大的变化，得到更多的便利，但是，相应的信息安全问题也随之而来。现代密码学己成为信息安全技术的核心，而数字签名是现代密码学的基础和重要保证，在保护网络通信安全方面起着重要的作用。数字签名是对传统手写签名的模拟，在身份识别、数据完整性、抗抵赖性等方面具有广泛的应用，特别是在电子商务、电子政务等应用领域，数字签名是其关键技术之一。随着数字签名研究的不断深入，近年来在理论和应用研究上相继出现了许多具有特殊性质或特殊功能的数字签名，如盲签名、门限签名、群签名、环签名、多重签名和代理签名等。环签名的概念是2001年由RIVEST，SHAMIR和TAUMAN三人提出的，环签名可以实现签名者的无条件匿名性，即任何人都无法追踪到签名人的身份，在环签名生成过程中，真正的签名者任意选取一组成员包含它自身作为可能的签名者，用自己的私有密钥和其它成员的公开密钥对文件进行签名。签名者选取的这组成员称作环，生成的签名称作环签名。签名接收者能证明签名者是来自环中的某一个成员但却无法确定签名者的真实身份。代理签名是一种特殊的签名形式，它是由MAMBO，USUDU和OKAMOTO于1996年首次提出的。在代理签名中，原始签名人可以自己的签名权利委托给可靠的代理人，让代理人代表原始签名者行使签名权利。代理环签名是代理签名与环签名的结合，在代理签名方案里，有关代理签名者的隐私保护问题在许多应用场合都非常重要。考虑如下场景一个原始签名者将自己的签名权委托给一个可靠代理人的集合，集合中的任何人都可以代表原始签名人进行签名。比如董事长将签名权委托给董事会，董事会成员代表董事长进行匿名签名。为了解决这种需求，ZHANG等结合代理签名与环签名，提出代理环签名的概念，并给出第一个基于身份的代理环签名方案，随后UNIT等提出另一个基于身份代理环签名方案。代理环签名允许一个原始签名者将他的签名权力授权给一组代理签名者，之后这组代理签名者中任何一个成员可以代表原始签名者对VII非主流HTTP/WWWFEIZHULIUMOBI山东大学博士学位论文消息进行签名，并且保证自己身份的匿名性，代理环签名很好的解决了代理签名者隐私保护问题。指定验证者签名的概念在1996年由JAKOBSSON，SAKO和IMPAGLIAZZO首次提出。在一个指定验证者签名方案中，只有指定的签名者可以验证签名并确认该签名来自某个环成员，由于指定验证者的公钥和签名者的公钥都包含在签名验证过程中，所以指定验证者可以模拟生成有效签名，该签名与实际签名者生成的签名无法区分，所有人都可以验证该模拟签名，但是除了指定验证者，没有人可以确定该签名来自环成员还是指定验证者，但是任何人都可以确定只有两个潜在的签名者，一旦签名在指定验证者接收前被第三方在线劫获，就可以确定该签名由原始签名者生成。为了避免这种风险，SAEEDNIA，KRAMER和MARKOVITCH在2003年具体提出了强指定验证者的概念，即任何人都能生成一个具有相同分布的副本，使之与原始签名不能区分。签名者利用指定验证者的公钥对签名进行加密，或者将指定验证者的公钥包含在签名生成算法中，这样只有指定验证者可以使用自身私钥对签名进行验证。本文主要针对当前环签名相关方案和应用进行分析、设计和研究，取得的主要工作成果归纳如下对环签名的研究热点及研究进展进行了总结，对具有不同性质的环签名FI限环签名、关联环签名、可否认环签名、可撤销匿名性环签名等和各种基于环签名的数字签名形式代理环签名、盲环签名、环签密等的性质和研究现状进行了简单介绍。将代理签名与环签名相结合，以双线性对为基础，提出一个高效的基于身份代理环签名方案。与ZHANG方案和AMIT方案相比较，新方案将计算消耗最大的双线性对运算次数从ON降到了O1，大大降低了运算量，具有更高的计算效率。我们证明本方案满足签名者匿名性、可验证性、不可否认性和可区分性。并在随机预言模型下基于CDHP难解问题，利用环签名分叉引理证明了新方案的签名不可伪造性。给出一个强指定验证者环签名方案的基本模型，提出一个高效的基于身份的强指定验证者环签名方案。在随机预言模型下证明了该方案满足签名不可伪造性、对指定验证者的签名匿名性和对第三方的签名匿名性，同时分析了该方案的VIII山东大学博士学位论文计算效率，与同类方案相比较，新方案在保证安全性的前提下，效率更高。对一个基于身份的环签名方案和一个基于身份的环签密方案进行安全性分析，提出有效的攻击算法，即通过寻找签名算法中的陷门信息，并结合环成员公钥进行环成员穷举等式验证的方式，来确定实际签名者的身份，证明两个方案都不满足签名者无条件匿名性，指出一个安全的环签名算法必须按照ADAMBENDER定义来实现签名者的无条件匿名性。基于一个基于身份的环签名方案、盲签名和多重验证技术，并结合RSA密码系统，提出了一个完备的匿名电子投票方案，可以实现合法签名者身份的无条件匿名性，并能防止选票信息中途泄露，较好的避免了选票碰撞、投票人欺诈、投票机构欺骗或联合欺骗等非法行为。下一步的研究工作包括设计具有更高可证安全性的环签名方案，改进安全性证明方法。不仅仅在随机预言模型中证明其安全性，还要在标准模型中对方案安全性进行证明。分析和改进现有环签名方案。很多方案存在安全性缺陷漏洞，对其安全性进行分析和证明，并进行优化。研究环签名在移动自组网络ADHOC中的应用。针对目前电子商务和网络安全中的需要，提出适用于实际的，安全性和效率更高的特殊环签名方案。关键词环签名；双线性对；代理环签名；强指定验证者环签名；电子投票IX非主流HTTP/WWWFEIZHULIUMOBI山东大学博士学位论文ABSTRACTWITHTHERAPIDDEVELOPMENTOFCOMPMERANDNETWORKTECHNOLOGIES，PEOPLESLIFEOBTAINSHUGECHANGESANDMORECONVENIENCEGOINGWITHTHEADVANTAGES，THEINFORMATIONSECURITYPROBLEMSAPPEARTOOMODEMCRYPTOGRAPHYHASBECOMETHEKERNELTECHNIQUEOFINFORMATIONTECHNOLOGY，ANDDIGITALSIGNATURETECHNOLOGYISTHEFOUNDATIONANDGUARANTEEOFTHEMODEMCRYPTOGRAPHYANDPLAYSAKEYROLEINPROTECTINGTHESECURITYOFNETWORKCOMMUNICATIONDIGITALSIGNATUREISASIMULATIONOFTRADITIONALHANDWRITINGSIGNATURE，ITCANBEAPPLIEDINTHEFIELDOFIDENTIFICATION，DATAINTEGRITY，NONREPUDIATIONANDSOONESPECIALLYINTHEFIELDOFELECTRONICCOLNINERCE，ELECTRONICGOVERNMENTETC，DIGITALSIGNATUREISONEOFTHECRUCIALTECHNOLOGIESWITHTHEDEVELOPMENTOFTHEDIGITALSIGNATURE，INRECENTRESEARCH，ALARGENUMBEROFDIGITALSIGNATURESWITHADDITIONALPROPERTIESANDDIFFERENTEFFECTHAVEAPPEAREDEGBLINDSIGNATURE，THRESHOLDSIGNATURE，GROUPSIGNATURE，RINGSIGNATURE，MULTISIGNATUREANDPROXYSIGNATURE，ETCTHECONCEPTOFRINGSIGNATUREISINTRODUCEDBYRIVEST，SHAMIRANDTAUMANIN2001RINGSIGNATUREHASTHEPROPERTYOFUNCONDITIONALANONYMITY,NOBODYCANTRACETHEIDENTITYOFTHESIGNERINTHEPROCESSOFTHEGENERATIONOFRINGSIGNATURE，THEREALSIGNERRANDOMLYCHOOSEASETOFMEMBERSINCLUDINGHIMSELFTOBETHEPOTENTIALSIGNERTHESIGNERUSEHISPRIVATEKEYANDOTHERMEMBERSPUBLICKEYTOGENERATETHESIGNATURETHESETOFCHOSENMEMBERSISCALLEDARING，THESIGNATUREGENERATEDISCALLEDRINGSIGNATURETHERECEIVEROFTHERINGSIGNATURECANVERIFYTHATTHESIGNATUREISFROMONEMEMBEROFTHERINGBUTCALLTPOINTOUTTHEREALSIGNERPROXYSIGNATUREISASPECIALFORMOFDIGITALSIGNATUREITISFIRSTINTRODUCEDBYMAMBO，USUDUANDOKAMOTOIN1996INAPROXYSIGNATURE，PEOPLEALWAYSNEEDTOCONSIGNTHESIGNINGCAPABILITYTOATRUSTEDPROXYWHOCALLSIGNONAMESSAGEINSTEADOFTHEORIGINALSIGNERXPROXYRINGSIGNATUREISTHECOMBINATIONOFPROXYSIGNATUREANDRINGSIGNATUREIN山东大学博士学位论文APROXYSIGNATURESCHEME，THEPROBLEMOFTHEPROXYSIGNERSPRIVACYPROTECTINGISVERYIMPORTANTTHINKABOUTSUCHANAPPLICATIONSCENARIOANORIGINALSIGNERDELEGATEHISSIGNINGCAPABILITYTOMANYPROXIES，CALLEDPROXYSIGNERSSETSUCHASAPUBLICKNOWNDIRECTORATETHESEPROXYSIGNERSCANSIGNMESSAGESONBEHALFOFTHEORIGINALSIGNERWHILEPROVIDINGANONYMITYTOSOLVETHISPROBLEM，ZHANGETALINTRODUCEDTHECONCEPTOFAPROXYRINGSIGNATUREANDPROPOSEDTHEFIRSTIDBASEDPROXYRINGSIGNATURESCHEMELATERAMITETALPROPOSEDANOTHERSCHEMEUSINGPROXYRINGSIGNATURE，ALLORIGINALSIGNERDELEGATEHISSIGNINGCAPABILITYTOASETOFPROXYSIGNERS，THENEVERYMEMBEROFTHESETCANSIGNTHEMESSAGEONBEHALFOFTHEORIGINALSIGNERANDENSUREHISIDENTITYANONYMITYSOPROXYRINGSIGNATURESOLVESTHEPROBLEMOFTHEPROXYSIGNERSPRIVACYPROTECTINGWELLTHECONCEPTOFTHEDESIGNATEDVERIFIERSIGNATURESCHEMEWASFIRSTINTRODUCEDBYJAKOBSSON，SAKOANDIMPAGLIAZZOIN1996ITMAKESUREONLYTHEDESIGNATEDVERIFIERCANCONVINCETHATTHESIGNATUREISMADEBYTHESIGNERBECAMETHESIGNERSPUBLICKEYANDTHEDESIGNATEDVERIFIERSPUBLICKEYAREBOTHINCLUDEDINTHEVERIFICATIONSTEP，THEDESIGNATEDVERIFIERCANEFFICIENTLYSIMULATESIGNATURESTHATAREINDISTINGUISHABLEFROMTHESIGNERSSIGNATUREANYONECANVERIFYTHESIGNATURE，BUTNOONECANBECONVINCEDTHATWHOMTHEREALSIGNERIS，THEORIGINALSIGNERORTHEDESIGNATEDVERIFIER，EXCEPTFORTHEDESIGNATEDVERIFIERHIMSELADESIGNATEDVERIFIERSIGNATUREISSUITABLETOBEUSEDINSOMECIRCUMSTANCESTHATTHESIGNERSHOULDSPECIFYWHOMAYBECONVINCEDBYTHESIGNERSSIGNATUREBUTINSOMESITUATIONS，FOREXAMPLE，THESIGNATUREMAYBECAPTUREDONLINEBYTHETLLIRDPARTYBEFORETHEDESIGNATEDVERIFIERRECEIVESIT，THENTHEMIRDPARTYCANCONFIRMTHATTHEORIGINALSIGNERISTHEREALSIGNERTOAVOIDTHIS，THECONCEPTOFTHESTRONGDESIGNATEDVERIFIERSIGNATURESCHEMEWASINTRODUCEDBYSAEEDNIA,KRAMERANDMARKOVITCHIN2003EVERYONECANSIMULATESIGNATURESTHATAREINDISTINGUISHABLEFROMTHESIGNERSSIGNATURETHESIGNERENCRYPTTHESIGNATURE、析THTHEDESIGNATEDVERIFIERSPUBLICKEYORINVOLVEITINTHESIGNATURE，SOONLYTHEDESIGNATEDVERIFIERCANVERIFYTHESIGNATUREGENERATEDBYTHESIGNER、析NLHISPRIVATEKEYTHEMAINWORKINTHISTHESISISANALYSIS，DESIGNANDRESEARCHONRINGSIGNATUREANDRELEVANTSCHEMES0URMAINRESULTSAREASFOLLOWSXI非主流HTTP/WWWFEIZHULIUMOBI山东大学博士学位论文SUMMARIZETHERESEARCHHOTSPOTSANDRESEARCHPROGRESSONRINGSIGNATUREINTRODUCETHEPROPERTIESANDDEVELOPMENTOFSOMEKINDSOFRINGSIGNATURETHRESHOLDRINGSIGNATURE，LINKABLERINGSIGNATURE，DENIABLERINGSIGNATURE，ANONYMITYREVOCABLERINGSIGNATURE，PROXYRINGSIGNATURE，BLINDRINGSIGNATURE，RINGSIGNCRYPTION，ETCPROPOSEANIDBASEDPROXYRINGSIGNATURESCHEMEFROMBILINEARPAIRINGSWHICHCOMBINESTHEADVANTAGESOFPROXYSIGNATUREANDRINGSIGNATURECOMPAREDWITHZHANGSSCHEMEANDAMITSSCHEME，THENEWSCHEMEHASABETTERCOMPUTATIONALEFFICIENCYBECAUSETHECOMPUTATIONALCOSTOFBILINEARPAIRINGSREQUIREDISREDUCEDFROM0NTOD1ITISPROVEDTHAT0111“SCHEMEISSIGNERANONYMOUS，VERIFIABLE，NONDENIABLEANDDISTINGUISHABLEUSINGRINGSIGNATUREFORKINGLEMMA，WEALSOPROVEITISUI】南略EABLEINRANDOMORACLEMODELABASICMODELOFASTRONGDESIGNATEDVERIFIERRINGSIGNATUREISGIVENANEFFICIENTIDBASEDSTRONGDESIGNATEDVERIFIERRINGSIGNATURESDVRSSCHEMEISPROPOSEDINRANDOMORACLEMODEL，ITISPROVEDTHATTHENEWSCHEMESATISFYTHESECURITYPROPERTIESOFSDVRSSIGNERANONYMITYFORTHEDESIGNATEDVERIFIERSIGNERANONYMITYFORTHETHIRDPARTY，ANDUNFORGEABILITYTHECOMPUTATIONALEFFICIENCYISANALYSEDCOMPAREDWIMSIMILARSCHEMESTHENEWSCHEMEISMOREEFFICIENTTHESECURITYOFANIDBASEDRINGSIGNATURESCHEMEANDANIDBASEDRINGSIGNCRYPTIONSCHEMEAREANALYSEDEFFICIENTATTACKALGORITHMSAREINTRODUCED，WEFINDTHETRAPDOORINFORMATIONINTHESIGNATURESCHEME，USETHEPUBLICKEYSOFTHERINGMEMBERANDVERIFYTHEEQUATIONTOCONFIRMTHEIDENTITYOFTHEREALSIGNERITISPROVEDTHATTHETWOSCHEMESDONTSATISFYTHESECURITYPROPERTYOFSIGNERANONYMITY，SOASECURERINGSIGNATURESCHEMEMUSTREALIZETHESIGNERANONYMITYACCORDINGTOTHEDEFTNITIONOFADAMBENDERBASEONALLIDBASEDRINGSIGNATURESCHEME，BLINDSIGNATUREANDMULTIVERIFICATIONTECHNOLOGY，COMBINEDWITHRSACRYPTOSYSTEM，APERFECTANONYMOUSEVOTINGSYSTEMISDESIGNEDTHESYSTEMCANREALIZETHELEGALVOTERSUNCONDITIONALANONYMITY，ANDAVOIDILLEGALBEHAVIORSSUCHASBALLOTCOLLISION，VOTERDECEIVING，VOTEORGANIZATIONDECEIVING，UNITEDORGANIZATIONDECEIVING，ETCXII山东大学博士学位论文NEXTWORKSARDASFOLLOWSPROPOSERINGSIGNATURESCHEMESWITHSTRONGERSECURITYPROPERTIES，IMPROVETHEPROVEMETHODSOFSECURITYPROVETHESECURITYPROPERTIESNOTONLYINRANDOMORACLEMODELBUTALSOINSTANDARDMODELANALYSETHEEXISTENTRINGSIGNATURESCHEMEALOTOFSCHEMESHASSECURI哆LEAKAGES，PROVETHEMANDOPTIMIZETHEMRESEARCHTHEAPPLICATIONOFFINGSIGNATUREINADHOCNETWORK一FORTHEREQUIREMENTSOFEBUSINESSANDNETWORKSECURITY，PROPOSEMOREUSEFULRINGSIGNATURESCHEMESWITHBETTERSECURITYANDEFFICIENCYKEYWORDSRINGSIGNATURE；BILINEARPAIRING；PROXYRINGSIGNATURE；STRONGDESIGNATEDVERIFIERRINGSIGNATURE，EVOTE非主流HTTP/WWWFEIZHULIUMOBI山东大学博士学位论文XIVROMPPTIDBASEDDLPCDHPDDHP符号说明和缩写词素数P，G模为G的有限域阶为素数G的有限群比特串A和B的联结无碰撞的HASH函数密钥生成中心事件S发生的概率随机预言模型概率多项式时间基于身份离散对数问题DI伍EHELLMAN计算问题DIFFIEHELLMAN判决问题G0C妇川乙Q郴肌麟啡山东大学博士学位论文原创性声明本人郑重声明所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。论文作者签名羔盈ET期旌12兰篁关于学位论文使用授权的声明本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。保密论文在解密后应遵守此规定论文作者签名羔磊导师签名日期孕型一非主流HTTP/WWWFEIZHULIUMOBI山东大学博士学位论文第一章绪论11引言政治、军事、外交、商业的文件、契约和命令等，传统上采用手写签字或印章，以便在法律上能认证、核准、生效。现代信息化社会中，网络通信技术的快速发展，使得人们需要通过电子设备和技术实现快速、实时、远距离的认证和交易，电子商务与政务应运而生，与传统模式相比，电子商务提高了交易效率、降低了交易成本，在现代商务活动中的作用日益重要，但是电子商务自身的安全问题成为制约其进一步发展的瓶颈。电子商务安全主要包括计算机网络安全和商务交易信息安全两个方面，其中计算机网络安全是指作为电子商务交易平台的计算机网络自身的安全，包括计算机网络设备安全、计算机网络系统安全、数据库安全等方面；商务交易信息安全则包括防止信息窃听、篡改、伪装，确保电子商务数据的完整性、可用性、交易双方身份的确定性、交易行为的不可抵赖性等。数字签名是实现认证的重要工具，作为一种信息安全的保障手段正越来越受到人们的关注。随着电子商务的飞速发展，网上交易活动正日益成为大众所接受的社会活动方式，但由于互联网的匿名性和开放性，电子商务的安全防范较传统商务活动具备更大的复杂性。安全电子商务必须考虑可能遭受的多方面的恶意攻击与欺诈，不仅是外部的不参加交易的第三方，而且涉及内部交易过程中数据的真实性检验，用户认证等等，存在严重的安全隐患。对于交易双方，必须在交易发生前建立种安全互信机制，以保证各自的经济利益、隐私信息等不受到窃取和侵犯。绝大多数电子商品，如电子支票、电子和同等的合法性基础都在于数字签名，因此大部分的应用，都将焦点放在数字签名的公平交换上。数字签名主要的功能是保证信息传输的完整性、发送者的身份认证、防止交易中的抵赖发生。简单来说，数字签名技术的应用就是为了在网络虚拟环境下实现“亲笔签名”的效果。因此本文对于环签名技术以及其在电子商务中实现公平交换的研究，对电子商务安全机制的完善具有一定的现实意义。山东大学博士学位论文2000年10月美国国会通过全球和国内商业法中的电子签名法案，确保了数字签名的法律效力，而联邦数字签名标准DSS更是于早先时候被提出。我国在2005年4月1日开始执行电子签名法，其中明确规定可靠的电子签名与手写签名或者盖章具有同等的法律效力。电子签名法必将有力的促进我国数字签名技术的发展和应用。12数字签名的基本定义、分类及特点121数字签名的基本定义数字签名大都是在公开密钥系统和单向哈希函数基础上建立起来的。一般的数字签名方案包括3个过程系统的初始化、签名和验证。系统初始化过程中产生数字签名方案用到的参数；签名生成过程中，用户利用给定的算法对消息生成签名；签名验证过程中，验证者利用公开的验证方法对给定消息的签名进行验证，判断签名的有效性。数字签名体制一个数字签名体制由以下部分组成1一个明文消息空间M某字母表中串的集合；2一个签名空间Q可能的签名集合；3一个签名密钥空间K用于生成签名的可能密钥集合；和一个认证密钥空间K。用于验证签名的可能密钥集合；4一个有效的密钥生成算法GENNKK，其中K和K为3中定义，为安全参数空间5一个有效的签名算法SIGNMKQ；6一个有效的验证算法VERFVMKK。专TRUE，此垃DR1，0。对任意的SKK和任意的MM，我们用仃卜SIGN呔聊表示签名变换，读作“仃是用密钥始生成的M的签名。对于任意的私钥SKK，用础表示与曲相匹配的公钥。对于MM和盯Q，必有2非主流HTTP/WWWFEIZHULIUMOBI山东大学博士学位论文蚴加，竺僦概率黧嚣，其中，概率空间包括Q，M，K，X，如果签名验证算法是概率算法，那么也许还包括一个随机的输入空间。密钥生成算法GEN的输入整数规定了输出签名、签名密钥、验证密钥的规模长度的大小。因为密钥生成算法是有效的，其运行时间为输入长度规模的多项式时间，输入的整数值是一元编码的。这个整数是签名体制的安全参数，定义了签名空间的大小。目前的研究主要集中于基于公钥密码体制的数字签名，公钥密码体制一般都是建立在难解的数学问题基础之上，目前被世界上广泛认可和使用的三类数学难题是1大合数分解问题；2有限域乘法群上的离散对数问题；3椭圆曲线离散对数问题。122数字签名的分类自从数字签名的概念出现以后，人们提出了许多不同的数字签名体制。比较著名的数字签名体制包括RSA列、EIGAMAL副、SCHNORR、DSS射、OKAMOTO引、FIATSHAMIRNL、NYBERGRUEPPEL随3等。随着数字签名在数字信息化发展中的应用，一些满足某些特殊需要的数字签名被提出，主要有以下几类1盲签名。1982年，CHAUM口1首次提出了盲签名的概念。所谓盲签名，是相对于一般的数字签名的概念，指签名者虽然对用户提供的某个消息签了名，但事后却并不知道他所签消息的内容，即对签名人而言，消息被盲化处理过。2多重数字签名。在很多情况下，一个文件需要多个人进行签名。1983年，BOYDCN们提出了第一个多重数字签名方案，此后，不同的数字签名方案相继被提出。通常的多重数字签名有两种形式按序多重数字签名和广播多重数字签名。在按序多重数字签名中，签名人按照一定的顺序对消息进行签名；在广播多重数字签名中，发送人将消息广播给所有签名人，签名人独自对消息签名，然后将结果转给签名收集人，由他来形成多重签名。3代理签名。代理签名的概念是MAMBO等N妇于1996年提出的，在这种数字签名山东大学博士学位论文中，一个被称为原始签名人的用户，可以将其数字签名权力委托给另外一个被称为代理签名人的用户，使得在需要的时候该代理签名人可以代替原始签名人产生有效的数字签名。LEE等N21对代理签名的一些性质给出了更强的定义。4门限签名。门限签名是将D，甩门限方案，立ISHAMIR密钥共享方案N3|，与数字签名体制相融合的产物，其基本思想是使用D，疗门限方案将数字签名的签名密钥分为N个子密钥并分配给N个参与者保管，当需要对某个文件进行签名时，至少D个参与者合作才能有效地对文件进行签名。5群签名。群签名的概念是由DCHAUM和VANHEYSTN41于1991年首先提出的，这种签名允许群中成员代表群组对信息进行匿名签名，产生的签名可以利用群组的公开密钥验证。在发生纠纷时，只有指定的群主管可以打开签名，确定签名成员的身份。6环签名。环签名的概念是RIVEST等N朝在2001年亚洲密码学会议上提出的，可以视为简化了的群签名，参与者只有用户没有群主管，环中每个用户都能以环的名义对消息进行签名，但是除了签名人本人以外，其他任何人都不能确定签名用户的身份。除了以上几种签名外，还有根据实际应用，将上述两种或多种签名相结合的签名，如代理盲签名N6L、门限代理签名17,18、门限群签名N92引、群盲签名砼、门限环签名口2。3，绷、代理环签名汹263及盲环签名砼73等。123数字签名的主要特点数字签名具备以下主要特点1不可伪造性。在不知道签名者私钥的情况下通常敌手很难有效地伪造一个合法的数字签名。只有掌握签名私钥的签名者才能有效地生成数字签名。2保证消息的完整性。通常，签名者可对消息的HASH函数值进行签名。由于HASH函数具备抗碰撞的特点对于一个安全的HASH函数，通常很难找到两个不同的消息使得它们具有相同HASH值，签名便与原消息绑定在一起而形成一个完整的整体。任何对消息的修改都将会导致消息，签名对无法通过验证。因此，签名具备保证消息完整性的特点，即其可防止篡改消息。3不可否认性。对于普通的数字签名，任何人都可利用签名者的公钥对签名进行验证，并通过公钥证书确定签名者的身份。这样，签名者便无法否认自己对消4非主流HTTP/WWWFEIZHULIUMOBI山东大学博士学位论文息的签名，即签名具有不可否认性。不可否认性使得签名的接收者可以确认消息及相应签名的原始来源，并可用来进行身份认证。13数字签名的攻击方式考虑到数字签名方案的安全强度问题，POINTCHEVA和STEM瞄1将对数字签名方案的攻击方法分为两大类唯密钥攻击KEYONLYATTACK和已知消息攻击MESSAGEATTACK。131唯密钥攻击在这种攻击下，敌手只知道签名者的公钥。敌手试图通过利用公钥直接求出与其相应的签名密钥，从而达到能够对消息进行签名的目的。通常，这种攻击是很难成功的，这是由于通常的签名密钥的安全性基于单向函数的安全性。并且，由公钥直接求出与其相应的签名密钥就相当于解决了一个数学困难问题的实例。因此，这种攻击是很难成功的。132已知消息攻击假定敌手选定签名者彳的签名方案作为攻击对象对于这种攻击，敌手在攻击目标签名方案之前已经掌握了一些已知的或自己选择消息以及与其相对应的签名。这种攻击又可分为以下四类1简明己知消息攻击KNOWNMESSAGEATTACK在攻击彳的签名方案之前，敌手已掌握了一些消息聊，聊，的签名，但这些消息并非敌手自己选择的。2一般选择消息攻击GENERICCHOSENMESSAGEATTACK在攻击彳的签名方案之前，敌手可选择一系列消息，并可从彳处得到与这些消息相对应的签名，但需要注意的是这些消息是固定的并且独立于彳的公钥。这种攻击是非适应性的，即敌手在得到签名之前整个消息列表聊，已经确定。之所以称这种攻击为“一般“是因为它独立于彳的公钥，并且总是对其他被攻击者采取同样的攻击。3定向选择消息攻击DIRECTEDCHOSENMESSAGEATTACK这种攻击类似上述的一般消息攻击，不同的是敌手可在看到彳的公钥后选择消息列表肌，所，但聊，朋，的选择需在看到任何签名之前完成。因此，这种攻击仍然是“非适应性”的，并且是“定向地”应用于被攻击者彳。5山东大学博士学位论文4适应性选择消息攻击ADAPTIVECHOSENMESSAGEATTACK在这种攻击下，敌手可将签名者么视为一个“预言机“ORACLE，敌手可向彳索取一系列依赖于彳公钥的消息的数字签名，并且敌手所选择的这些消息可适应性的依赖于敌手已获得的数字签名。那么，什么样的结果才算意味着攻破了一个数字签名方案GOLDWASSER在其文29中给出四种结果1完全攻破TOTALBREAK计算出签名者的签名密钥或陷门信息。2普遍伪造UNIVERSALFORGERY找到了一个有效的签名生成算法，其性能等价于签名者的签名生成算法3选择性伪造SELECTIVEFORGERY敌手能够根据某个消息已知的签名伪造关于该消息的一个新的签名。4存在性伪造EXISTENTIALFORGERY敌手至少能够伪造一个消息的签名。在这种攻击下，敌手不能控制与伪造的签名相对应的消息。因此，在这种攻击下，敌手能够伪造签名的“消息“为一个随机数，从而该“消息”很可能是无实际意义的。因此，这种伪造攻击对签名者的影响几乎可以忽略。显然，上面所给出的四种结果的强度依次降低。目前普遍认为，若一个签名方案在适应性选择消息攻击下是安全的，则该签名方案是安全的。我们对数字签名的研究主要考虑适应性选择消息攻击和存在性伪造。14数字签名的安全性定义及证明方法定义11称一个数字签名方案是安全的，如果其在适应性选择消息攻击下能够抵抗存在性伪造攻击。更准确地说，对于任意概率多项式时间算法F，输入安全参数L。，签名者的公钥Y以及敌手适应性选择的、多项式个消息M，聊，的签名占，墨，F输出一个新的有效消息签名对优，S使得聊，S朋，墨的概率是可忽略的，即对所有的上述算法F，任意的正整数C和充分大的后，F输出的新的M，J为有效消息一签名对的概率小于尼。以上给出了关于普通数字签名方案的攻击模型和安全定义。对于普通数字签名方案的安全性证明方法，有三种较为经典的证明思路第一种为随机预言机模6非主流HTTP/WWWFEIZHULIUMOBI山东大学博士学位论文型下利用分叉引理FORKINGLEMMA证明数字签名的安全性慨删；第二种为随机预言机模型下非分叉引理证明口妇第三种为非随机预言机模型证明口羽。需要注意的是，对于不同类型的签名方案，又有着不同的攻击模型和安全性定义如基于身份的签名方案攻击模型及安全定义33，34。数字签名的可证明安全性可以在两种模型下进行证明1标准模型。利用计算复杂性理论，将数字签名的安全性转化为一些己知的难题，如大整数分解问题，离散对数问题或者一般NP完全问题。2随机预言机模型。在这个模型中，任何具体的对象例如HASH函数等，都被当作随机对象。它允许人们规约参数到相应的计算，HASH函数被作为一个预言返回值，对每一个新的查询，将得到一个随机的应答。将伪造者对签名的伪造规约为对一个困难问题的求解。7山东大学博士学位论文第二章数学基础及预备知识本章简要介绍后续章节将要使用到的一些数学基础和密码学预备知识，包括代数学、数论以及概率论、信息论的相关基础知识。21密码学基础211计算复杂性模型公钥密码学的安全性是以数学上的某些困难问题的难解性为前提的。必须在复杂性模型中对解决这些问题的“难“和“易”进行量度。因此，公钥密码学的安全性是建立在计算复杂性模型基础上的。本节对计算复杂性理论中与密码学相关的一些概念进行回顾与讨论口5L。2111多项式时间定义21图灵机为了精确定义算法这一概念，引入一个计算模型。图灵机由有限状态控制单元、七1条纸带TAPE以及同等数量的读写头TAPEHEAD组成。有限控制单元控制磁头读写纸带的操作，每个读写头访问一条纸带。每一条纸带分为无限个单元CELL图灵机求解一个问题时，读写头扫描一个有限个字符的串。该串从纸带的最左边的单元开始按顺序存放在纸带上，每个字符占用一个单元，右边剩下的是空白单元BLANKCELL，该串称为问题的一个输入。扫描从含有输入的纸带的左端开始，同时图灵机赋一个初始状态INITIALSTATE。任何时刻图灵机只有一个读写头访问它的纸带一个读写头对应一个纸带。读写头对它的纸带的一个访问称为一个合法的移动MOVE。如果图灵机从初始状态起，一步接一步的合法移动，完成对输入串的扫描，最终满足了终止条件而停下来，则称图灵机识别了该输入。否则图灵机在某一点没有合法移动，他会没有完成识别输入而停下来。图灵机识别的一个输入成为一种可识别语言1ANGUAGE的一个实例定义22确定性图灵机确定性图灵机的输出结果完全取决于输入和初始状态。也就是说，对同样的8非主流HTTP/WWWFEIZHULIUMOBI山东大学博士学位论文输入和初始状态运行一个确定性图灵机两次，这两次输出的结果是相同的。定义23确定性多项式时间可识别的语言语言三是确定性多项式时问内可识别的，如果存在一个确定性图灵机M和一个多项式P，使得1对于一个输入的二进制字符串X，M最多执行PI叫步，其中H表示X的比特长度；2M1当且仅当X上。定义中之所以可以把X看作一个比特字符串，是因为任何输入都可以编码为比特字符串。识别P语言的图灵机都是确定的DETERMINISTIC。定义2。4P类语言P类语言是由确定性多项式时间可识别的语言组成的语言类。下面给出非确定性多项式可识别的语言的定义，该定义有两种形式，这两种形式是等价的。定义25非确定性图灵机图灵机在进行某些操作步骤时会产生随机移动，有些移动可以产生正确的结果，而其他的移动则产生错误的结果，这种图灵机成为非确定性图灵机。定义26非确定性多项式可识别的语言1语言L是非确定性多项式时间内可识别的，如果存在一个非确定性图灵机M和一个多项式P，使得1对于一个输入的二进制字符串Z，M最多执行PI叫步，其中I纠表示X的比特长度；2MOL当且仅当XL。定义27非确定性多项式可识别的语言2语言L是非确定性多项式时间内可识别的，如果存在一个能被多项式时间内被识别的布尔关系也O，1XO，1和一个多项式P，使得XL当且仅当存在Y，以至于HR工且X，J，RL。Y被称为XL的证据。定义28咿类语言NP类语言是由非确定性多项式时间可识别的语言组成的语言类。9山东大学博士学位论文不用证据而采用确定性图灵机求解NP类中的任意一个问题的确切复杂度能否达到多项式时间，即尸NP21是否成立，是计算理论中的一个公开难题。但是普遍认为PNP，这也是公钥密码学存在的必要条件。定义29可多项式归约一种语言三可多项式归约到另一种语言，如果存在一个多项式时间界定的图灵机M，使得XL当且仅当MX。下面定义NP完全NPC的定义。定义210NP完全一种语言L是NP完全的，如果任意语言胛都可以可多项式归约到L。定义211有界差错概率多项式时间图灵机回答判定性问题时，非确定性图灵机出错概率的界是一个常数，这种情况下的图灵机成为有界差错概率多项式时间图灵机。定义212有界差错概率多项式可识别的语言语言L是能被有界差错概率多项式时间图灵机可识别的，如果1对于任意XL，关系式PRMXL】23，2对于任意XCL，关系式PRMX0】23。定义213BPP类语言BPP类语言是有界差错概率多项式时间可识别的语言组成的语言类。定义214可忽略的称函数厂可忽略的，如果对于任意多项式P，存在一个自然数，使得对于所有玎N，FN。密钥生成KEYGEN每个身份为IDO，1的环成员可以通过计算如HIDG。生成公钥Q，D。为了得到对应私钥，环成员向KGC提交个人身份，KGC壬T算对应公钥S，DXQID，并将公钥安全发送给该成员。在该方案中，身份为囝的环成员的秘27山东大学博士学位论文密签名密钥为S，D，公开验证密钥为Q，D。签名生成SIGN，Z个环成员身份集合皿，119，蛾，实际签名者对应序号为S，其公钥为，Q_以2日慨GL，指定验证者身份为11，签名者以对于消息所的签名算法步骤如下1选择U，RGL，计算忽NOMLLIIU，VI1，ZP，2选择乏，计算玑O她一肿妙，H,QID,，3计算暇ERQLD,S皿，W，4计算吃H。MLU，0耽，YHS蠢S以，5输出对消息所的签名仃，仃U妙，Y，形，L，现在三包含M，。签名验证VERIFY指定验证者收到环成员身份集合三，消息M以及环签名仃，通过如下等式检查环签名的合法性1IT算H,H。MLU川P形，S蛾，VIEL，沙，2检查等式P厶。，；U，曩Q以EP，Y是否成立，如果等式成立，该签名得到合法正确性验证，如果等式不成立，该签名非法。412对该环签名方案的攻击在该方案中，作者声称只有指定验证者者才能验证该签名，但是如果指定验证者公布其私钥，则该签名对于签名者和指定验证者是不可区分的，即没有入可以确定该签名到底是由实际签名者生成还是由指定验证者生成，对于这个问题，我们在下一章我们提出的新方案中详细说明。该方案的真正缺陷是不能保证环签名最基本的安全性要求一无条件匿名性。也就是说，任意得到该环签名17“、环成员身份集合三以及消息M的人都可以确定具体签名者的身份。我们可以通过以下步骤来确定签名者的身份1计算U。箸U一渺，28非主流HTTP/WWWFEIZHULIUMOBI山东大学博士学位论文。当NOMLLUF,A,O,，JUJ，2对所有的FL，刀，检查，NOMLLLLU，是否成立。如果等式成立，那么身份为崛的环成员就是实际签名者。下面我们给出攻击正确性证明如果ID，是实际签名者的身份，那么U配一形枷冀UU，一一US蠢一胁鼽红，故U阈，O以巧一。缸，匆一蠢Q，DL硝，篡U，巧Q_峨一，U。一瑚，冀魂Q吗一一Q，D，一阁，冀红，GNOMLLIIU,A,O,故，U一同J冀忽叠H。MLLILU，一瑚，O。MIIZLLU，THOMIILLLU，HOMULIIU。QTO,所以使得等式成立的S就是实际签名者的身份标识，也就是说，实际签名者的身份是ID，。由上述的攻击算法得知该环签名算法不满足签名者的无条件匿名性，是不安伞的。42对一个基于身份环签密方案的分析421基于身份环签密方案的一般模型基于身份环签密方案的一般模型包括以下四个部分山东大学博士学位论文SETUP给定一个安全参数七，KGC幂IJ用SETUP生成系统公共参数，其中包括KGC的公开密钥圪。SP，J为系统主密钥，对外是保密的。EXTRACTKGC通过该算法为环成员生成私有密钥。环成员的身份标识为皿，KGC计算该成员的私有密钥SM并通过安全信道传给该成员。SIGNCRYPT为了将消息聊发送给接收者BOB身份标识为DB，A1ICE选择一些用户并包含她自己构成一个环U，并代表环U对消息M生成一个环签密仃，记作仃SIGNCTYPTM，U，IDA。UNSIGNCRYPT接收者BOB通过UNSIGNCRYPT算法解密出环签密仃中的明文肌，并验证环签密仃的合法性。输出明文脚以及反映环签名是否合法的逻辑值，M2UNSIGNCTYPTA，U，S现。422LI等删提出的基于身份环签密方案LI等在80中提出一个高效的基于身份环签密方案，作者证明该方案在运算效率方面有较大提高，因为在SIG