原文：(ItcomesfromCarltonR.Davis.IPSEC:SecuringVPNS.北京：清華大學(xué)出版社，2002)CryptanalysisandImprovementofDigitalMultisignatureSchemeBasedonRSASULi(粟栗)CUIGuohua(崔國(guó)華)CHENJing(陳晶)YUANJun(袁雋)SchoolofComputerScienceandTechnology,HuazhongUniversityofScienceandTechnology,Wuhan430074,ChinaAbstractZhangeta.lproposedasequentialmultisignatureschemebasedonRSA.Theschemehasadvantagesoflowcomputationandcommunicationcosts,andsoon.However,wefindaproblemintheirschemethattheverifiercannotdistinguishwhetherthemulti-signatureissignedbyallthesignersofthegrouporonlybythelastsigner.Thus,anysinglesignaturecreatedbythelastsignercanbeusedasamultisignaturecreatedbythewholegroupmembers.Thispaperproposesanimprovedschemethatcanovercomethedefect.Inthenewscheme,theidentitymessagesofallthesignersareaddedinthemultisignatureandusedinverificationphase,sothattheverifiercanknowthesignatureisgeneratedbywhichsigners.Performanceanalysisshowsthattheproposedschemecostslesscomputationthantheoriginalschemeinbothsignatureandverificationphases.Furthermore,eachpartialsignatureisbasedonthesigner’sidentitycertificate,whichmakestheschememoresecure.Keywords:Digitalmultisignature;Sequentialmultisignature;RSAcryptosystem;CryptanalysisIntroductionMultisignatureisajointsignaturegeneratedbyagroupofsigners.Thegrouphasasecuritypolicythatrequiresamultisignaturetobesignedbyallgroupmemberswiththeknowledgeofmultipleprivatekeys.Digitalmultisignaturesshouldhaveseveralbasicproperties[1]:(1)Multisignaturesaregeneratedbymultiplegroupmemberswiththeknowledgeofmultipleprivatekeys.(2)Multisignaturescanbeverifiedeasilybyusingthegrouppublickeywithoutknowingeachsignerspublickey.(3)Itiscomputationallyinfeasibletogeneratethegroupsignaturewithoutthecooperationofallgroupmembers.In2003,Zhangeta.l[2]proposedasequentialmultisignatureschemebasedonRSA,inwhichallthesignersuseacommonmodulus.Theschemehastheadvantagesoflowcomputationandcommunicationcosts,andcanresistforgeryandcoalitionattacks.Thedifficultyofbreakingthesystemisequivalenttothatoffactoringalargeintegerintoitstwolargeprimefactors.However,ourcryptanalysisofZhangeta.l’sschemefindsaseriousproblem;thatisaultisignatureisverifiedbyusingthelastsigner’spublickeyinsteadofthegrouppublickey.Asaresulttheverifiercannotdistinguishwhetherasignatureissignedbyagroupofsignersoronlybythelastsigner,whichviolatesthebasicpropertiesofsequentialmultisignature[1,3,4].Therefore,weproposeanimprovementschemetoovercomethisdefectinthispaper,sothattheverifierknowswhohavecreatedthemultisignature.Performanceandsecurityanalysesshowthatthenewschemenotonlykeepstheadvantagesoforiginalcheme,butalsosatisfiesthedefinitionofmltisignatureandismoresecure.1ReviewofZhangeta.lsSequentialMultisignatureScheme1.1SysteminitializationFirsttheTrustCenter(TC)selectstwolargeprimpandq,andcomputestheRSAmodulusn=pq.Then,TCselectsarandomnumberasthepublickeywhichmakesgcd(e,)=1,wheregcd(·)isthegreatestcommondivisorfunction,=(p-1)(q-1),and1<e<.Finally,TCcomputestheprivatekeydwhichmakesed≡1mod((n)).Inthemeanwhile,TCpublishesthepublickey(n,e)andkeeps(d,p,q)secretly.Define(i=1,2,…,k)tobethesignerwhohasaexclusivecertificate(i=1,2,…,k),whereispublic,andMthemessagetobesigned.TCcomputesandforeverysigner,andsendsthecertificatetoeachsignerthroughasafechannelwhereH(·)issecurehashfunction,whichgeneratesafixedlengthidentityinformationfromthecertificate,andistheprivatekeyofthesigner.Then,thecorrespondingsignerverifiesthevalidityofthecertificatethroughtheformula,andkeepsasasecretkeyiftheformulaholds.1.2GeneratingpartialsignatureofsequentialmultisignatureAsapreparationforgenerationofpartialsignatures,TCpublishestheorderofsignersthroughtheiridentity().Step1ThesignerU1selectsarandomnumberandcomputes,,,,WhereisthecommitmentofU1;m1bindsthecommitmentandplaintextbyhashfunction;(D1,f1)isthesignatureof.ThenthesignerU1sendsthepartialsignaturetothesigner.Step2Byanalogy,ifthe(i-1)thpartialsignatureisright,(2≤i<k)createstheithsignature.Heselectsarandomnumberandcomputes,,,.Thensendsthepartialsignaturetothesigner.computes=H(),,.verifiesthevalidityoftheithpartialsignaturebycomparingthevalueofwith.Thepartialsignatureisrightifequalsmi;otherwiseitiswrong.Step3createsthenextpartialsignature.Theaboveprocessisrepeateduntillthesignercreatesthesignatureandsendsittomultisignaturereceiver.Thereceivercomputes,,.verifiesthethesignaturevaliditybycomparingwith.Thefinalmultisignatureis.2CryptanalysisofZhangeta.l’sSequentialMultisignatureSchemeWhenthereceiverusesthesignature,heshouldconvincethethirdpartythatitwascorrectlysignedbytheksigners.Thethirdpartycomputesand,andverifiesthevalidityofthemultisignaturebyjudgingwhetherequation〕holdsornot.Thesignatureisverifiedbyusingonlythe’spublickeyinsteadofthepublickeyofksigners.Hence,thethirdpartycannotdistinguishwhetherthesignatureissignedbyksignersoronlybythekthsigner.Ifthesignerwantstoconvincethethirdparty,hemustuseallsigners’publickeytoverifythemultisignature.Althoughcanbecalculatedinpublictoshowthatthemultisignatureissignedbytheksigners,buttheverifierhastoknowallthekpartialsignatures,whichviolatesthedefinitionofsequentialmultisignature.Thecomputationamountofverificationincreaseslinearlywiththenumberofsigners.Therefore,weproposeanimprovedschemehereinaftertosolvethisproblembasedontheschemesinRefs.[2,5,6,7].3ImprovedSequentialMultisignatureSchemeBasedonRSA3.1InitializationphaseSignerselectsarandomnumber,computes,andsendstothe.Similarly,everysignerselectsarandomnumber,computesandsendstosigner.Atlast,computes,andsendstoreceiver.Then,computesm=H(M,)andpublishesm.3.2GeneratingpartialsignatureofsequentialmultisignatureStep1Signerusestherandomnumberandcomputes.Becausehassenttothesignerininitializationphase,heonlysendstonow.computesand,andverifies(,)bycomparingwithT1.Thepartialsignatureofisrightifequals.Otherwise,itiswrong,andrequirestoresignuntilthepartialsignaturesatisfiestheverificationequation.Step2Assumingthatthe(i-1)thsignatureisright(1<i<k),createstheithsignatureas.Thensendsthepartialsignaturetothesigner.computes,,and.verifiesthevalidityofbycomparingwith.Step3Signercreatesthenextpartialsignature.Theaboveprocessisrepeateduntilsignercreatesthelastpartialsignatureandsendsittothemultisignaturereceiver.computes,,and.verifiesthevalidityof(,)bycomparingwith.Thefinalmultisignaturesignedbyksignersis(,,m).3.3TestifyingvalidityAnyonecanverifythevalidityofthemultisignaturebycomputingandcomparingwith.Ifequals,themultisignaturesignedbytheksignersisright.ProofFromthesequentialsignatureprocess,itisknownthatWhenthereceiverorthethirdpartyverifiesthemultisignature,hecomputesBecause,wehave。ThenThemultisignatureisrightifandonlyifequals.4SecurityAnalysisZhangeta.l[2]analyzedthesecurityoftheiroriginalschemeindetailHere,weonlyanalyzethesecurityrelatedtothemodifiedpart.(1)Theverifierknowsthesignerofthemultisignature.Intheimprovedscheme,thecertificateofeachsignerhasbeenpublished,andtheverifiermustuse,,…,tocomputeforverification,sohecandistinguishwhetherthesignatureissignedbyksignersoronlybythekthsigner.(2)Thepublicationofininitializationphaseissecure.InZhangeta.l’soriginalscheme,istranslatedsequentiallybetweensigners.Here,iscomputedininitializationphase.Evenanattackerknowsandcancomputethevalueof,buthecannotgetfrom.(3)Themultisignaturecanresistforgeryattack.Iftheattackerwantstoforgethepartialsignatureof,hemustforgeavalidsatisfyingtheverificationformula.However,ispublishedininitializationphaseandcannotbeforged,sohemustmakeathatsatisfiestheformula.Thatisadifficultproblembasedonfactorizationofabiginteger.(4)Allsignersmustfollowthespecifiedorder.AnextsignerUi(i=2,…,k)verifiesthepartialsignaturethroughthevalueof,whichisgeneratedininitializationphase.AnysignaturedisorderofindividualsignerswillresultsintheprocessinterruptionofCreatingmultisignature.Forexample,ifthesignercreatedthepartialsignatureTibeforehereceivesthesignature,then≠willoccurtothesubsequentverificationphaseandtheprocessofcreatingthemultisignaturestops.5PerformanceAnalysisDefinesymbols,andasthetimecostsofmodularmultiplication,modularexponentiationandhashoperation,respectively.Inourscheme,theaveragecomputationtimeforverifyingthepreviouspartialsignatureis,butthecomputationoftillandtheirproductwhichcosts,canbedonebypre-calculation;thecomputationtimeforpartialsignatureis.ThecomputationcostsforbothsignatureandverificationarelessthanthoseinZhangeta.l’sscheme;thereforeourschemeismoreefficient.6ConclusionWepointedoutadefectofZhangeta.l’ssequentialmultisignatureschemebasedonRSA;thatis,averifiercannotdistinguishwhetherthesignatureissignedbyagroupofsignersoronlybythelastsignerofthegroup.Toovercomethedefectweproposedanimprovedscheme,inwhichtheverifiercanknowthesignatureisgeneratedbywhichsigners.Theproposedschemedoesnotincreasetheamountofcomputationandcommunication;itssecurityisbasedonthedifficultyoffactoringalargeinteger.Performanceanalysisandsecurityanalysisshowthattheproposedschemeismoresecureandefficientthantheoriginalscheme.ECCellipticcurvenumeralencryptionECCisbasedonthegaloisfieldin,ellipticcurvesetofpointsEconstatutesonthegroupdefinesseparatelogarithmsystemIngaloisfieldellipticcurvechoice,Shouldavoidusingtheultrastrangecurve,guaranteestheenoughsecurityTheellipticcurveoperationforassignsonellipticcurveEbasicpointGandTheinteger(11)nkappakappa,asksthenumbertoride,QalsoisonE,computation..(kappaGAddstogether)isrelativelyeasy;ButifassignsintheellipticcurvetwoGandQ,asksanintegerkappa,causes(mod)GQpkappa=,speciallywhenGiscomparesWhenGaoJiebasicpoint,thenisextremelydifficultThisistheellipticcurveseparatelogarithmquestion.Basedontheellipticcurveseparatelogarithmquestiondifficultsolution,tohaveformedtheECCsystem.1.ellipticcurvespasswordTheellipticcurvecryptographicsystemhasthemanykindsofforms,typicallikeEpigamicsystemDiffie-Hellmankeyswapagreement:SupposesEisanelementnumberfield()ontheellipticcurve,Gisinthecurvethepublicspot,itsstepisn.Asecretdesignationstochasticinteger,thecomputationselects,thetransmissionforB;Similarly,Bsecretdesignationstochasticinteger,thecomputationselects,thetransmissionforA.Themalekeyis,AwhilebythecomputationwhichreceivesfromBobtainsQwithownprivatekey;BwithownprivatekeyBdwhilebytheAdGcomputationwhichreceivesfromAobtainsQ.Theinterceptionmustresultindetermines,onlyknowsG,,with,butisunabletopromoteorTheEIGamalsystem:SupposedtheinformationsequencealreadytoinsertthroughthecodetotheellipticcurveEpsilonon,andA,BbothsidesalreadypassedTheDiffie-HellmanagreementhasmutuallyexchangedAdGandBdG.AmusttoBtransmissioninformationmEpsilon∈,AtransmissionforBseveralpairs:withitsprivatekeywhilebythefirstitem,usestheseconditemtosubtractitagain,solvesinformationm.2.severalkindstypicalbasedonECCdigitalsignatureplanBasedonthemalekeypassworddigitalsignaturesystembasicprincipleis:Whentheusersignswiththeprivatekey,signswithuseritselfrelatesintogether,alsoHasthelegalefficiency,thereceivingendconfirmswiththemalekeysigns.Generally,regardingthesamescaleparameter,theellipticcurvepasswordeachkeyintensitymustbebiggermuch,,173ellipticcurvepassworddepartmentTheseriesisequalto1,024EIGmalortheDSAsystemThereallegationspeedcomparedtoDSA,RSAandsoonothermalekeysystems,theefficiencyismorequicklyhigh.2.1basedonECCEIGamalsignatureplanThisplanistransplantsfromthetraditionalEIGamalsignaturesystemtotheellipticcurveinproduces1)initialization:Thestructureelementnumberfieldonthenon-ultrastrangeellipticcurveEpsilon,choosespublicbasicpoint,itsstepisn;InformationsequenceminsertsthroughthecodetoEpsilonon,namely2)keyproduction:TheuserAstochasticselection,willpublicizeselectstotakethemalekey3)signature:TheAstochasticchoice,thecomputation,calculates1again，thenlosesLeavessigns.4)confirms:AfterBreceivesthesignatureinformation,confirmsand,ifconfirmsforreallysigns;Otherwiseisthevacation.2.2ECDSAsignatureplanSupposestheelementnumberfieldonthenon-ultrastrangeellipticcurveEpsilon,choosespublicbasicpoint,itsstepisn;PassesinformationsequencemThecodeinsertstoEpsilonon,namely.SupposesAwithownprivatekeyAdtotheinformationmsignature,BusesAmalekeytotheabovebambooslipThenamecarriesontheconfirmation2.2.1signsAtohaveastochasticinteger,causes,,isanunidirectionalHashfunctionThen,AwillsigntheinformationandinformationmtransmissionforB.2.2.2confirmsBtoreceive,,,calculates.,and,if,pass,because2.3AbovebasedonECCsignatureplanalgorithmicanalysisIntheEIGamalplanonly(nisellipticcurveEpsilonstep)operatesthetraditionalmoldpoperationsubstitutionformoldnTheECDSAplancharacteristiciscalculatesinformationmthroughtheHashfunctionmixedtocollectthevalue,makesthenonlineartransformationtotheinformation,furtherenhancedthebambooslipFamoussecurityBut,directlyregardingthistheHashvaluecarriesonthesignature,becausetheHashvalue(MD5is128,SHAis160binarysequences)itValueverybig,makesthesignatureoperationtobemoretime-consumingInaddition,initsalgorithminformationdefiniteordersmbutdirectlyhasnottransmittedaftertheencryption,theinformationmsecuritycannotObtainsthesafeguardInviewofthis,thisarticleproposedonekindofproperattentiontobothsecurityandtheoperationefficiencyonekindhastheinformationretrievalthedigitalsignatureplan.3.OnekindbasedonECCsignatureimprovementprogramThisarticleproposedweightmakesthesignaturebynewsHashthevalueHamming,alsopassesthroughafterinformationmtheencryptionwithtosigntransmitstogether,causesthereceiveTheinformationhasmayrestore.3.1ParameterchoiceDesignatedHashfunctionMD5,easyhighspeedtorealizeMD5theinputnewslengthwith32bitsoftwarefree,theoutputcompressionvalueis128bit.IfdirectlyregardingthistheHashvaluecarriesonthesignature,becauseHashis128binarysequences,itsvalueverybig,calculatesthesignaturewithit,therunningtimeisverylongBecauseHashfunctionHammingweighttonewschangeverysensitive,ifthenewschange,theHammingweightchangestheprobabilityisabove90%,thisarticleconclusioncarriesonthemassiveexperimentalconfirmationregardingthiswithMATLAB,theresultisconsistentThereforethisarticleproposedweightmakesthesignaturebyHashthevalueHamming,doesnotsurpass128,regarding128binarysequencesitsvaluetobepossibletocausetheoperationgreatlyforthesimplification.Establishesaellipticcurveterritoryparameter,among,pexpressedagaloisfield,theelement,,thenon-ultrastrangeellipticcurveEpsilononspotsatisfiesequation,andEpsilononthebasicpointintegerfor#,iscalledellipticcurveEpsilonstepGexpressionellipticcurveEpsilononabasicpoint,nisselectsGthestepalsoforisbiggerthan1,602bigprimenumbers,itslengthhaddecidedtheECCkeylengthhisthesmallintegeriscalled-oddfactoralso.RelatedellipticcurvespotCanada,thesubtractionandthenumberwhileandsoontheoperationalrule,thestepcomputation,descriptionandsoonbasicpointselectionseealsotheliteratureispublic.Insertsinformationsequencemthroughthecodetotheelementnumberfield,namely.3.3ThisarticleplanalgorithmicanalysisFirstusedsecurehigherHashforinformationmfunctionMD5toentertherow,namelymadethenonlineartransformationaftermtodosignsAsaresultofHashThefunctionhasunidirectional,non-collisioncharacteristic,thereforecannotfindtwoseveral12,mm,causes,theaggressornottobeimpossibletocarryonthegenerationTradestheattack,hasthesamesecurityrankwithECDSA;TodispersesarowvaluetheHammingweighttocarryonsignsbutnon-todispersestherowvaluedirectsignature,comparesEnhancedtheoperationefficiencyAndalsopassesthroughafterinformationmtheencryptionwithtosigntransmitstogether,enablethereceivetheinformationtohavemayrestore.4.PerformanceanalysissignswhichbasedonECCBasedontheellipticcurvepassworddigitalsignature(ECDSA),itbreaksacodethedifficultytobeequaltotheellipticcurveseparatelogarithmquestiondifficultsolution,uptonowUptohadnotfoundtheeffectivemethodofattack,therelatedECDSAsecureanalysis,theliteraturehasamoredetailedanalysisThisarticlealgorithmintheECDSAfoundation,furtherenhancesthesecurityWhensignature,considerstheinformationdefiniteorderstheprotection,inordertoisextensivetothedefiniteordersDuplicate;HasnotusedittotheinformationdefiniteordersdirectsignaturetodispersearowvaluetheChinesebrightweighttomakethesignatureoperation.ThisarticleplanhasemphaticallyconsideredtheoperationefficiencyenhancementThealgorithminhadsomeplansinthefoundationtomakethefurtheroptimization,toHashletterThenumberHammingweightmakesthesignature,andtakesthemoldoperationbesidestheellipticcurveinnumberwhiletheoperation,otherarethealgebraicoperation,operationcomplexcomparesLow,greatlyenhancedtheoperatingspeed.Underspecificallyanalyzeseachperformance:(1)ThesignaturemayconfirmWhenBwithAmalekeyAQconfirmationnews,BmayconfirmistheAsignature;(2)BambooslipThenamecannotfabricateOnlysomeAknewitsprivatekeyAd,theothersareunabletoanalyzeobtainEvenifinellipticcurvebasicpointGandAA()QdG=ispublicButpromotesAdistheellipticcurveseparatelogarithmquestion,atpresentthesituationisunsolvable;(3)ThesignaturedidnotacknowledgeBorotherpeopleonlymustuseAMalekeyAQcanconfirmAthesignature,onceisconfirmed,Aafterwardsdidnotacknowledge;(4)SignscannotduplicateusesBecauseusedhasunidirectionaldispersedarrangesinorderHashThefunctionenterstherowtotheinformationoriginaltext,formsthehash,againsignsinthisabstractfoundationtoitsChinesebrightweightProducesoriginallyusingtheHashfunctionBeginninginformationhashtoprimaryinformationslightchangeextremelysensitive,theChinesebrightweightveryisalsosensitivetotheprimaryinformationchangeThesignatureistheinformationoriginaltextThefunction,differentinformationoriginaltextitdispersesarowvaluetobedifferent,signsalsodifferently;(5)TheinformationwhichsignsismayrestoreAmakesinformationmwithBQTheencryptionkey,carriedontheECCencryptiontotheinformationdefiniteorders,BhasmadetheinformationdecipherkeywithBdveryeasilytorestoretoit.Thisarticleplanmaygoastepfurtherthepracticalapplication,liketoinformationtheandsoonpictureortextdigitalsignatureistheworkwhichnextstepmustdoHowinvolvestoFirmlyinsertstheinformationoriginaltextintheellipticcurve,aswellasquestionandsoonrelatedellipticcurvefastalgorithmseparatearticlediscussion.5.AnellipticcurvedigitalsignatureschemeEllipticCurveCryptosystemisapublic-keycryptosystem,inadditiontodataencryption,itisanotherapplicationfordigitalsignatures.Withdistributedcomputertechnologytoenhanceandextensiveapplicationofcomputingpowerincreasedgreatly.Toachievegreatersecurity,RSAneedsofthekeybitlonger,tieuphugeresources,Thisaffectedmoreencryptionandsignaturespeed,inappropriateforsmartcardsandotherresourceslimitedhardwaredesign,EllipticCurveandhasthesamesecurityadvantagesofthesmalloverhead,EllipticCurveDigitalSignatureresearchandproductdesigngraduallybecomethehotspot.EllipticCurveDigitalSignatureandElGamaldigitalsignatureisverysimilar,onlyellipticcurvedigitalsignatureisbasedontheellipticcurvediscretelogarithmproblem(Eclipse),ElGamaldigitalsignatureandisbasedongenerallylimiteddomainofdiscretelogarithmproblem(DLP).Therefore,wecanusethissimilarity,rightabovethesixdifferenttypesofsignaturesequationappropriatetransform,thusbemoreconvenientEllipticCurvesignatureequation.Ourlastarticleisa(5)SignedanequationderivedEllipticCurveDigitalSignatureprogram.InEquationWeusedtoreplacem,thentheequationinto,Withbothsidesmultipliedbym,;Becausemisknownthenews,Itcanbehash,Signedwaslaunchedandtheacceptancesideknow,Wecanmake,canusesubstituteAsnewsmsignatures,Thus,theaboveequationcanbesignedintoasfollows:Signedinordertousethisequationtoconstructasignatureprogram,thestepsareasfollows:Selectingasecurityellipticcurve,ellipsecurveparametersandParaapartofthesame.(1)SignedAliceonEchoiceprivateKeyx,gforEBp,calculation,yasapublickeyissued,Aliceexplicitcalculationofm;(2)Alicechoiceintegerrandomk(ksecrets),(s,r,e)willbesenttotheverifierBob;Theseareoursignaturesderivedprogram,whichavoidstheinverseprocess,solvetheECDSAalgorithminadequate.TheprogramthanECDSAsimplealgorithm,theexperimentalresultsshowthatthealgorithmthanElGamal,Schnorrprogramabout28%faster.譯文1：密碼分析和基于RSA多重?cái)?shù)字簽名方案的改良(粟栗,崔國(guó)華,陳晶,袁雋)中國(guó)華中科技大學(xué),計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,武漢430074摘要張等人提出了基于RSA序貫多重簽名方案.該方案具有低運(yùn)算、低通信費(fèi)用優(yōu)點(diǎn)等等。然而，我們發(fā)現(xiàn)一個(gè)問(wèn)題,在他們的方案中核查不能區(qū)分多重簽名簽署是由簽名組中所有的簽名者所簽署還是由最后一位簽名者簽署.因此,由最后一位簽名者所做的單一簽署可以作為整組簽署成員所做的多重簽署。本文提出一個(gè)改良方案，可以克服這個(gè)缺陷。在新的方案中，所有簽名者的身份信息被添加在這個(gè)多重簽署中，并且會(huì)在核查階段顯示，以確保核查時(shí)能知道簽署是由哪些簽名者產(chǎn)生的。性能分析說(shuō)明，這個(gè)新的方案在簽署和核查階段需要的計(jì)算都比原來(lái)的方案少。此外，每一局部的簽名是基于簽名者的身份證書(shū)，這使得該方案更平安。引言多重簽名是由一組簽名者所產(chǎn)生的聯(lián)合簽名。該集團(tuán)的平安政策，需要多重要簽署的所有組成員的知識(shí)的多重私人鑰匙。數(shù)字多重簽署應(yīng)該有幾個(gè)根本屬性：〔1〕多重簽署是由多組成員用多個(gè)私鑰的知識(shí)產(chǎn)生的；〔2〕多重簽署在不知道每個(gè)簽署者的公鑰的情況下可以很容易的通過(guò)該組的公鑰進(jìn)行核查?！?〕在沒(méi)有所有組成員的合作下，計(jì)算產(chǎn)生該組簽署的可行性。2003年，張等人提出了一種基于RSA的序列多重簽名方案。其中所有的簽名使用一個(gè)共同的模量。該方案的優(yōu)點(diǎn)是低的計(jì)算和通信費(fèi)用，并能抵抗偽造和聯(lián)軍攻擊。攻破這個(gè)系統(tǒng)的困難性相當(dāng)于將一個(gè)大整數(shù)分解為兩個(gè)大素?cái)?shù)因子。然而，我們對(duì)張等人加密方案進(jìn)行分析，發(fā)現(xiàn)一個(gè)嚴(yán)重的問(wèn)題。這個(gè)問(wèn)題就是：一個(gè)多重簽署可以由最后的簽名者的公鑰來(lái)進(jìn)行核查，而不是多重簽署組的公鑰。結(jié)果使核查者不能區(qū)分簽署是由一組簽署者簽署還是僅由最后一個(gè)簽署者簽署，這就違背了連續(xù)多重簽署的根本屬性【1，3】。因此，在這章中，我們提出一種改良的方案來(lái)克服這個(gè)缺陷，以使核查者能夠確認(rèn)簽名是由誰(shuí)產(chǎn)生的。性能和平安性分析說(shuō)明，新的方案不僅保存了原來(lái)方案的優(yōu)點(diǎn)，同時(shí)也符合了多重的定義，并且更加平安。1.張等人的連續(xù)多重簽名方案的回憶1.1系統(tǒng)初始化首先，信托中心選擇兩個(gè)大素?cái)?shù)p和q，并且計(jì)算RSA算法的模n=pq。然后，信托中心選擇一個(gè)隨機(jī)數(shù)e作為公鑰，它滿足gcd(e,)=1,這兒的gcd(·)是最大公約數(shù)函數(shù)，=(p-1)(q-1)，and1<e<.最后信托中心根據(jù)ed≡1mod((n))計(jì)算出私鑰d。與此同時(shí)，信托中心發(fā)布公鑰(n,e)和秘密保存(dp,q)。定義(i=1,2,…,k)是簽名者，他有一個(gè)獨(dú)家證書(shū)(i=1,2,…,k),這兒的是公開(kāi)的，且將要被簽名的信息是M。對(duì)每個(gè)簽名者，信托中心計(jì)算和，并且通過(guò)一個(gè)平安渠道發(fā)送那個(gè)證書(shū)給每個(gè)簽名者，這兒的H(·)是保密散列函數(shù)，這會(huì)產(chǎn)生一個(gè)固定長(zhǎng)度的身份信息的憑證，是私鑰簽字。然后，相應(yīng)的簽字確認(rèn)證書(shū)的有效性，在持有公式的情況下，通過(guò)公式，并保持作為密鑰。1.2生成局部連續(xù)多重簽名作為新一代的準(zhǔn)備局部簽名，信托中心通過(guò)簽名者的身份信息()發(fā)布簽名的順序。步驟1：簽名者U1選擇一個(gè)隨機(jī)數(shù)并且計(jì)算,,,,這兒的是U1的委托事項(xiàng)；綁定那些委托事項(xiàng)，并且明文通過(guò)散列函數(shù)；(D1,f1)就是的簽名。然后，簽名者U1發(fā)送局部的簽名給簽名者.步驟2：通過(guò)類(lèi)推，如果(i-1)次局部簽字是正確的，(2≤i<k)就創(chuàng)立i次簽字。他選擇一個(gè)隨機(jī)數(shù)，并計(jì)算,,,.然后發(fā)送局部的簽名給簽名者.計(jì)算=H(),,.通過(guò)比擬和的值來(lái)驗(yàn)證第i局部簽名的有效性，如果等于，那么那局部簽名是正確的，否那么是錯(cuò)誤的。步驟3：創(chuàng)立下一局部簽名。以上過(guò)程重復(fù)執(zhí)行直到簽名者創(chuàng)立簽名并且將其發(fā)送給多重簽名接收者，這個(gè)接收者計(jì)算：,,.通過(guò)比擬和的值驗(yàn)證簽名的有效性，最終的多重簽名是.2.張等人的連續(xù)多重簽名方案的加密分析當(dāng)接收者在使用簽名時(shí)，他應(yīng)該說(shuō)服第三方，這是k個(gè)簽名者的正確簽署。第三方計(jì)算and,并且通過(guò)判斷等式〕是否存在來(lái)驗(yàn)證這個(gè)多重簽名的有效性。這個(gè)簽名只有用的公鑰而不是所有k個(gè)簽名者共有的公鑰來(lái)驗(yàn)證。因此，第三方不能區(qū)分這個(gè)簽名是由k個(gè)簽名者共同簽署還是由第k個(gè)簽名者一個(gè)人簽署。如果簽名者想說(shuō)服第三方，他必須用所有簽名者的公鑰來(lái)驗(yàn)證這個(gè)多重簽名。盡管能夠被公眾的計(jì)算以顯示這個(gè)多重簽名是由k個(gè)簽名者所簽署，但驗(yàn)證者必須知道所有k局部的簽名，這違反了連續(xù)多重簽名的定義。驗(yàn)證的計(jì)算量隨著簽名者的數(shù)目呈線性增加。因此，我們?cè)谶@兒提出一種改良的方案，后面解決這個(gè)問(wèn)題是基于參考文獻(xiàn)【2，5，6，7】中的方案。3基于RSA改良的連續(xù)多重簽名方案3.1初始化階段簽名者選擇一個(gè)隨機(jī)數(shù),計(jì)算,并且發(fā)送給.相似地,每個(gè)簽名者選擇一個(gè)隨機(jī)數(shù),計(jì)算且發(fā)送給簽名者.最后，計(jì)算,且發(fā)送給接收者.然后，計(jì)算m=H(M,)且公布m.3.2產(chǎn)生連續(xù)多重簽名的局部簽名步驟1：簽名者使用隨機(jī)數(shù)且計(jì)算.因?yàn)樵诔跏蓟A段已經(jīng)發(fā)送給簽名者了,所以現(xiàn)在他只需發(fā)送給。計(jì)算和,且通過(guò)比擬和T1驗(yàn)證(,).如果等于，那么那局部簽名是正確的.否那么,它是錯(cuò)誤的，且需要讓位直到那局部簽名滿足驗(yàn)證方程。步驟2：假定第(i-1)局部簽名是正確的(1<i<k)，創(chuàng)立第i局部簽名如.然后發(fā)送那局部簽名給簽名者.計(jì)算,,及.通過(guò)比擬和驗(yàn)證的有效性。步驟3：簽名者創(chuàng)立下一局部簽名。以上過(guò)程重復(fù)執(zhí)行直到簽名者創(chuàng)立最后局部的簽名并且將其發(fā)送給多重簽名接收者.計(jì)算,,及.通過(guò)比擬和來(lái)驗(yàn)證(,)的有效性，最終多重簽名是由k簽名者共同簽署的，即(,,m).3.3作證有效性任何人都可以通過(guò)計(jì)算且比擬和來(lái)驗(yàn)證多重簽名的有效性.多重簽名由k個(gè)簽名者簽署是正確的。證明：從連續(xù)多重簽名的過(guò)程中可以知道當(dāng)接收者或者第三方驗(yàn)證這個(gè)多重簽名時(shí)，他計(jì)算因?yàn)?我們得到。那么當(dāng)且僅當(dāng)?shù)扔跁r(shí)，簽名正確。4平安性分析張等人細(xì)節(jié)性的分析了他們的原始方案的平安性。在這兒，我們只分析了平安性相關(guān)的修改局部?！?〕驗(yàn)證者知道這個(gè)多重簽名的簽署者。在改良方案中，每個(gè)簽名者的憑證被公開(kāi)，并且驗(yàn)證者為了驗(yàn)證，必須用,,…,來(lái)計(jì)算，所以，他能夠區(qū)分開(kāi)那個(gè)簽名是由k個(gè)簽名者簽署還是由第k個(gè)簽名者簽署?！?〕在初始化階段，的發(fā)布是平安的。在張等人的原始方案中，在簽名者之間被連續(xù)傳遞。而在這兒，在初始化階段被計(jì)算出。即使一個(gè)破壞者知道且能夠計(jì)算出的值，但他也不能由得到?！?〕多重簽名能抵抗偽造攻擊。如果攻擊者想偽造局部的簽名，他必須要偽造一個(gè)有效的滿足那個(gè)驗(yàn)證公式。然而，是在初始化階段被公開(kāi)的，并且不能被偽造，所以，他必須取得一個(gè)使其滿足公式.這是一個(gè)基于大整數(shù)分解的難題?！?〕所有的簽名者必須按照特定的次序。一個(gè)接一個(gè)簽名者Ui(i=2,…,k)通過(guò)的值驗(yàn)證那局部簽名，這個(gè)過(guò)程是在初始化階段產(chǎn)生的。任何個(gè)體簽名者的障礙將導(dǎo)致創(chuàng)立多重簽名過(guò)程的終止。例如，如果簽名者在接到簽名局部之前創(chuàng)立局部簽名，那么≠將導(dǎo)致隨后的驗(yàn)證階段和創(chuàng)立多重簽名過(guò)程的終止5性能分析定義符號(hào),和作為建立多重簽名所消耗的時(shí)間，分別進(jìn)行模冪和散列運(yùn)算。在我們的方案中，來(lái)驗(yàn)證前面局部的簽名所消耗的平均時(shí)間是,但是，直到及它們的產(chǎn)生將消耗的時(shí)間是,這可以預(yù)先計(jì)算。局部簽名的計(jì)算時(shí)間是.簽名和驗(yàn)證的耗時(shí)都少于張等人的方案。因此，我們的方案是更加有效地。6結(jié)論我們指出張等人基于RSA的連續(xù)多重簽名方案的缺陷，那就是：驗(yàn)證者不能區(qū)分簽名是由一組簽名者共同簽署還是僅由這組簽名者中的最后一位單獨(dú)簽署。為了克服這個(gè)缺陷，我們提出一個(gè)改良方案，在這個(gè)方案中，驗(yàn)證者能夠知道簽名是由哪些人產(chǎn)生的。這個(gè)改良方案沒(méi)有增加計(jì)算量和通信費(fèi)用；它的平安性是基于一個(gè)大整數(shù)分解的困難性。性能分析和平安性分析顯示，提出的這個(gè)方案比原來(lái)的方案更加平安和有效。譯文2：基于橢圓曲線的一種改良的數(shù)字簽名方案侯?lèi)?ài)琴，張潔，高寶建，曹正文〔西北大學(xué)信息科學(xué)與技術(shù)學(xué)院，陜西西安710069〕ECC是基于有限域上，橢圓曲線點(diǎn)集所構(gòu)成的群上定義的離散對(duì)數(shù)系統(tǒng).有限域上橢圓曲線的選擇，應(yīng)防止使用超奇異曲線,以保證足夠的平安性.橢圓曲線的運(yùn)算為給定橢圓曲線上的一個(gè)基點(diǎn)和一個(gè)整數(shù)，求數(shù)乘，也是上的一點(diǎn)，計(jì)算(個(gè)相加)相對(duì)容易；但假設(shè)給定橢圓曲線上兩點(diǎn)和，求一整數(shù)，使，特別是當(dāng)G是較高階的基點(diǎn)時(shí)，那么非常困難。這就是橢圓曲線離散對(duì)數(shù)問(wèn)題?；跈E圓曲線離散對(duì)數(shù)問(wèn)題的難解性，形成了ECC體制。1.橢圓曲線密碼橢圓曲線密碼系統(tǒng)有多種形式，典型的如EIGamal系統(tǒng)。Diffie-Hellman密鑰交換協(xié)議：設(shè)E是一個(gè)素?cái)?shù)域上的橢圓曲線，是曲線上公開(kāi)的點(diǎn),其階為。A秘密的選定一個(gè)隨機(jī)整數(shù)，計(jì)算點(diǎn),發(fā)送給B；同樣，B秘密的選定一個(gè)隨機(jī)整數(shù)，計(jì)算點(diǎn)，發(fā)送給A。公鑰為，A用自己的私鑰乘以從B收到的計(jì)算得到；B用自己的私鑰乘以從A收到的計(jì)