密码学Digital Signature.ppt
DigitalSignature曹天杰Tianjie Cao College of Computer Science andTechnology,China University of Mining and Technology,Xuzhou,China中国矿业大学计算机科学与技术学院2003.6.61DefinitionsDefinitionsDigitalSignature-adatastringwhichassociatesamessagewithsomeoriginatingentityDigitalSignatureGenerationAlgorithmamethodforproducingadigitalsignatureDigitalsignatureverificationalgorithm-amethodforverifyingthatadigitalsignatureisauthentic(i.e.,wasindeedcreatedbythespecifiedentity).DigitalSignatureScheme-consistsofasignaturegenerationalgorithmandanassociatedverificationalgorithm2ApplicationsDigitalSignaturescanprovideAuthenticationDataIntegrityNon-RepudiationOneApplicationCertificationofpublickeysinlargenetworks3ClassificationDigitalsignatureschemeswithappendixrequiretheoriginalmessageasinputtotheverificationalgorithm.Digitalsignatureschemeswithmessagerecoverydonotrequiretheoriginalmessageasinputtotheverificationalgorithm.Inthiscase,theoriginalmessageisrecoveredfromthesignatureitself.4Classification(cont)Taxonomyofdigitalsignaturessignature schemesmessage recoveryappendixdeterministicrandomizedrandomizeddeterministic5TypesofSignaturesDirect digital signatureinvolvesonlythecommunicatingpartiesAssumedthatreceiverknowspublickeyofsender.Signaturemaybeformedby(1)encryptingentiremessagewithsendersprivatekeyor(2)encryptinghashcodeofmessagewithsendersprivatekey.Furtherencryptionofentiremessage+signaturewithreceiverspublickeyorsharedprivatekeyensuresconfidentiality.6TypesofSignaturesProblemswithdirectsignatures:Validityofschemedependsonthesecurityofthesendersprivatekeysendermaylaterdenysendingacertainmessage.PrivatekeymayactuallybestolenfromXattimeT,sotimestampmaynothelp.7TypesofSignaturesArbitrated digital signatureinvolvesatrustedthirdpartyorarbiter1.Everysignedmessagefromsender,X,toreceiver,Y,goestoanarbiter,A,first.2.Asubjectsmessage+signaturetonumberofteststocheckorigin&content3.AdatesthemessageandsendsittoYwithindicationthatithasbeenverifiedtoitssatisfaction8ArbitratedDigitalSignaturesRequiresanunconditionallyTTPaspartofthesignaturegenerationandsignatureverification.EachentitysharesasymmetrickeywiththeTTPSymmetrickeycryptographyresultsinaveryfastalgorithmHowever,thisspeedupisovershadowedbytheTTPaswellascommunicationoverhead9ArbitratedDigitalSignaturesSignatureGeneration(byA)ATTPIA,u=EkA(h(m)s=EkT(h(m)|IA)10ArbitratedDigitalSignaturesSignatureVerification(byB)BTTPIB,v=EkB(s)EkB(h(m)|IA)11DigitalSignatureStandardsRSADigitalSignature-ISO9796-ANSIX9.31-CCITTX.509ElGamalNISTFIPS186DigitalSignatureStandard(DSS)12PublicKeyCryptographySignatureschemesLet P be the set of all messagesA be the set of signaturesK be the set of all keys13BasicMechanismofSignatureSchemesK:Akeygenerationalgorithmtorandomlyselectapublickeypair.SigK:Asignaturealgorithmthattakesmessage+privatekeyasinputandgeneratesasignatureforthemessageasoutputVerK:Asignatureverificationalgorithmthattakessignature+publickeyasinputandgeneratesinformationbitaccordingtowhethersignatureisconsistentasoutput.14AttackmodelsTotal Breaking Attack-Theattackerknowsthepublickey.Hetriestorecoverthecorrespondingsecretkey.Forgery Attack-Theattackerknowsthepublickey.Hetriestofindthesignatureforagivenmessage.Existential Forgery Attack-Theattackerknowsthepublickey.Hetriestofindapairofamessageanditssignature.Chosen Message Attack(CMA)-Theattackerisabletosignmessagesbutdoesnotknowthekeyused.Hetriestoperformthe(existential)forgeryortoobtainthesecretkey.15ForgeryAttackTheattackertriestofindthesignaturesfromagivenmessagemandthepublickey.Forgeryattackermessagempublickeysignaturesofm(d:secretkey)16ExistentialForgeryAttackExistentialForgeryAttackerpublickey(m,s):pairofmessageandsignature.Theattackertriestofindapairofamessageanditssignaturefromthepublickey.Themessageofthepairmayhavenomeanings.(d:secretkey)17ChosenMessageAttackTheattackertriestofindapair(m,s)fromseveralpairsofsignature(mi,si)andthepublickey.ChosenMessageAttackerpublickey(m,s):pairofmessageandsignature.(d:secretkey)SigningOraclemessagesmSd(m):signaturesIftheattackercanchoosenewmessagesdependenttoobtainedsignatures,itiscalledtheadaptivechosenmessageattack.18TheRSAdigitalsignatureLetn=pq,where pand qareprimes.LetP=A=Zn,anddefine K=(n,p,q,e,d):ed=1modf(n).Foreachkey K=(n,p,q,e,d),definesigK(m)=mdmodnandverK(m,y)=true y e=mmodn,where(m,y)Zn.Publickey=(n,e),Privatekey(n,d).19ExistentialForgeryofRSALet(S1,S2)bethesignaturesofthemessages(M1,M2),namelyS1=M1dmodn,S2=M2dmodn.ThenS=S1*S2modnisthesignatureofM=M1*M2modn,becauseS=S1*S2=M1dM2d=(M1*M2)dmodn.ThemessageMmustberandomizedbeforesigning.ThemessageMisusuallysignedbyS=h(M)dmodn,wherehisthehashfunctionh:0,1*-Z/nZ.(h(M)=h(M1)*h(M2)modndoesnothold)20TheElGamalsignatureschemeLetpbeaprimeandg Zpaprimitiveelement.LetP=Zp*,A=Zp*xZp-1andK=(p,g,x,y):y=gxmodp.Thevalues p,g,yarethepublickey.xistheprivatekey.21TheElGamalsignatureschemeSigningLetmZp*beamessage.ForK=(p,g,x,y):y=gxmodp,andsecretrandomnumberk Zp-1*,define:sigK(m,k)=(s,t),wheres=gkmodpt=(m-xs)k-1 modp-1(kt+xs=m modp-1)VerificationverK(m,(s,t)=true stys=gmmodp.stys=gkt gxs=gmmodp kt+xs=m modp-122ToyexampleLetp=467,g=2,x=127.Theny=2127mod467=132.Letmessagem=100,Choosek=213.Thenk-1mod466=431.Thesignatureis:s=2213mod467=29t=(m-xs)k-1mod(p-1)=(100-127x29)431mod466=51Verification:2100?132292951mod46723ThesecurityoftheElGamalsignatureIftheDiscreteLogarithmproblemcanbesolvedthenElGamalsignaturescanbeforged.Theconversemaynotbetrue.Theexponentkmustbeprivatecannotbeusedtwicebest:chosenatrandom.24DSAAvariantoftheElGamalandSchnorrSignatureSchemesPublickeycryptographicsystemusedforgeneratingandverifyingdigitalsignaturesCannotbeusedfordataencryptionorkeyexchangeBasedonfamiliarnumbertheoryconceptsMakesuseoftheSecureHashAlgorithm(SHA-1)25KeyGenerationAlgorithmGeneratingpublicandprivatekeys:1)Selectaprimenumberq2159q2160|q|=160bits2)Selectaprimenumberp2511p21024|p|=Lbits512L1024L0mod64p10modq26KeyGenerationAlgorithmGeneratingpublicandprivatekeys:3)Calculateaqthrootof1,=g(p1)/qmodp1g1Zp*4)Selectarandom“personal”privatekeyx1x(q1)5)Calculate“personal”publickeyyy=xmodp27KeyGenerationAlgorithmGlobalPublicKeyComponentsq,p,UsersPrivateKeyxUsersPublicKeyyUserspublickeyiscalculatedfromhis/herprivatekey28SignatureGenerationAlgorithmSigningamessagem:1)Selectarandomsecretintegerk0kqshouldbeuniqueforeachmessagesigned2)Calculatess=(kmodp)modq0sq3)Calculatett=(SHA-1(m)+(x s)k-1modq0tq4)Thesignatureofmproducesthepair(s,t)tobeusedintheverificationprocess29SignatureGenerationAlgorithmMessagemSHA-1MessageDigestSigns=(kmodp)modqt=(SHA-1(m)+(x s)k-1modqPrivateKeyxDigitalSignature(s,t)30VerificationAlgorithmVerifyingasignature(s,t):1)Verify0sqand0tq2)Calculatee1u1=SHA-1(m)t-1modq3)Calculatee2u2=st-1modq4)Calculatevv=(u1y u2)modpmodq5)Acceptthesignatureiff:v=s31VerificationAlgorithmMessagemSHA-1MessageDigestVerifyu1=SHA-1(m)t-1modqu2=st-1modqv=(u1y u2)modpmodqPublicKeysq,p,yDigitalSignature(s,t)v=sv sSignatureVerificationSucceededSignatureVerificationFailed32ProofLetw=t-1modqu1=(SHA-1(m)w)modqu2=(s w)modqFromsignaturegenerationwehave:t=(k-1(SHA-1(m)+x s)modqSo,w=t-1modq=(k-1(SHA-1(m)+x s)-1)modq=(k(SHA-1(m)+x s)-1)modqRearranging:(SHA-1(m)+x s)wmodq=kmodq33Proof(continued)Fromkeygeneration,wehave:y=xmodpSo,v=(u1y u2)modp)modq=(SHA-1(m)wy s w)modp)modq=(SHA-1(m)w x s w)modp)modq=(SHA-1(m)+x s)w)modp)modq=(k)modp)modq (q=1modp)=s34ExampleKeyGenerationp=124540019q=17389(p1)/q=7162g=110217528=g(p1)/qmodp=10083255x=12496y=xmodp=11994626535Example(continued)KeyGenerationPublicKey:p=124540019q=17389=10083255“Personal”PrivateKey:x=12496“Personal”PublicKey:y=11994626536Example(continued)SignatureGenerationk=9557s=(kmodp)modq=34 t=(SHA-1(m)+(x s)k-1modq=13049k-1modq=7631SHA-1(m)=5246(contrivedforexample)Signatureformis(s=34,t=13049)37Example(continued)SignatureVerificationu1=SHA-1(m)t-1=12716u2=st-1modq=8999v=(e1y e2)modpmodq=34Sincev=s=34,theverificationissuccessfulandthesignatureisvalidated38SecurityofDSAAdversaryDoesnotknowprivatekeyofsignerCannotgeneratevalidsignatureGiventheuserspublickey,itiscomputationallyinfeasibletodeterminetheusersprivatekeyDiscretelogarithmproblem39Criticism:RSAvs.DSARSA:usedforbothencryptionanddigitalsignaturessignatureverificationfasterthansignaturegenerationDSA:onlyfordigitalsignaturessignaturegenerationfasterthansignatureverification40CriticismfromRSADSAlackedRSAsflexibilityDSAtoonewandnotanalyzedenoughDSAsignatureverificationwastooslowComputerandhardwarevendorsalreadystandardizedontheRSAalgorithmProcessNISTusedtochooseDSAwastoosecretiveandarbitrarytoomuchinfluencefromNSA41CriticismoftheKeypwasinitiallyfixedat512bitsNotsecureenoughAllowedupto1024bitsOctober2001:NISTrecommendedthatpbe1024bits“neitherastandardnoraguideline”Presentlyconsideredsecurewith1024bits42TheEllipticCurveDigitalSignatureAlgorithm(ECDSA)isbeingproposedasanANSIX9.62standardLikeDSAbasedonElGamalsignatureschemeBetterthanDSAWithmuchsmallerkeylengthitprovidessamelevelofsecurityasthoseofRSAandDSASpeedcanbeoptimizedECDSA43ECDSA(contd)Publickeys:(E,P,n,Q)Privatekeys:dwhereE isanEllipticCurveP isapointonthecurvewhoseorderisnd isanintegerrandomlyselectedintheinterval1,n-1Q isanotherpointonthecurvesuchthat44ECDSA(contd)Signature:whereh(m)isSecureHashofthemessagem(SHA-1)k isarandomintegerintheinterval1,n-1(s,t)issignatureiscomponentsofanECpoint(integers)45ECDSA(contd)Verification:wherew=t-1 (modn)46Amechanismwhichcanbeusedtosign,atmost,onemessage;otherwise,signaturescanbeforgedAnewpublickeyisrequiredforeachmessagePublicinformation(validation parameters)isnecessaryforverificationSignaturegenerationandverificationareveryefficientUsefulinapplicationssuchassmartcards,wherelowcomputationalcomplexityisrequiredOne-timesignatureschemes47One-timeprivatekey:,eachofbitlengthlOne-timepublickey:,eachofbitlengthlsuchthatwhereE isasymmetric-keyencryptionscheme(e.g.DES),isthebinaryrepresentationofi.TheRabinone-timesignaturescheme48Signature:wherem ismessageissignatureh ishashfunctionE isasymmetric-keyencryptionscheme(e.g.DES)TheRabinscheme(contd)49Verification:Selectn distinctrandomnumberssuchthat1,2nRequesttheprivatekeysVerifytheauthenticityofkeybycheckingwhereVerifythatUnlikeotherdigitalsignatureschemes,verificationcanbedoneonlyonce.TheRabinscheme(contd)50TheRabinscheme(contd)keysize:n=80,l=64,Resolutionofdisputes:signerA,verifierBandTTPBprovidemandsignatureTTPgetprivatekeyk1,.k2nfromATTPverifyauthenticityoftheprivatekeyTTPcomputeui=Eki(h(m),1i2n.Ifui=siforatmostnvaluesofi,itisforgerybyB.Ifn+1ormorevaluesmatch,itisvalidsignatureRationalefordisputeresolutionprotocolAcandisavowwithPr=1/C2nn51TheRabinscheme(contd)RationalefordisputeresolutionprotocolIfB hasattemptedtoforgeAssignatureonanewmessagem0,B eitherneedstodetermineatleastonemorekeyk0 sothatatleastn+1 valuesofi giveui=si,ordeterminem0 suchthath(m)=h(m0).IfA attemptstocreateasignaturewhichitcanlaterdisavow,A mustensurethatui=siforpreciselyn valuesofi andhopethatB choosesthesen values,theprobabilityofwhichisonlywithPr=1/C2nn52BlindsignatureschemeDefinition:AsendsapieceofinformationtoB.BsignsandreturnsthesignaturetoA.Fromthissignature,AcancomputeBssignatureonapriorimessagemofAschoice.Atthecompletionoftheprotocol,Bknowsneitherm,northesignatureassociatedwithit.Application:e-cash53Blindsignaturescheme(cont)ChaumSenderA;SignerBBsRSApublicandprivatekeyareasusual.kisarandomsecretintegerchosenbyA,satisfying0knProtocolactions(blinding)A:compm*=mkemodn,toBNote:(mke)d=mdk(signing)Bcomps*=(m*)dmodn,toA(unblinding)A:computess=k-1s*modn54Blindsignaturescheme(cont)cut-and-choosetechnique(1)BOBpreparesndocuments,eachusingadifferentcovername,givinghimselfdiplomaticimmunity.(2)BOBblindseachofthesedocumentswithadifferentblindingfactor.(3)BOBsendsthenblindeddocumentstoALICE.(4)ALICEchoosesn1documentsatrandomandasksBOBfortheblindingfactorsforeachofthosedocuments.(5)BOBsendsALICEtheappropriateblindingfactors.(6)ALICEopens(i.e.,sheremovestheblindingfactor)n1documentsandmakessuretheyarecorrectandnotpensionauthorizations.(7)ALICEsignstheremainingdocumentandsendsittoBOB.(8)Agentremovestheblindingfactorandreadshisnewcovername:“TheCrimsonStreak.”Thesigneddocumentgiveshimdiplomaticimmunityunderthatname.55ReferencesFIPS PUB 186-256
