The Elliptic Curve Digital Signature Algorithm (ECDSA)

1 TheEllipticCurveDigitalSignatureAlgorith m (ECDSA) DonJohnson andAlfredMenezes andScottVanstone CerticomResearch,Canada Combinatorics& Optimization,Universityof Waterloo, CanadaEmails: djohnson,amenezes, svanstone DigitalSignatureAlgorithm (ECDSA) is theellipticcurveanalogueof theDigitalSignatureAlgorithm(DSA).It wasacceptedin 1999asanANSI standard,andwasacceptedin 2000asIEEEandNIST standards. It wasalsoacceptedin 1998asanISOstandard,andis underconsiderationforinclusionin someotherISOstandards. Unlike theordinary discretelogarithmproblemandtheintegerfac torizationproblem,nosubexponential-timea lgorithmis knownfortheellipticcurve ,thestrength-per-key-bitis substantiallygreaterin analgorithmthatusesellipticcurves. ,anddiscussesrelatedsecurity, implementation, (DSA)wasspecifiedin a GovernmentFederalInformationProcessingSt andard(FIPS)calledtheDigitalSignatureSta ndard(DSS[70]).

2 Itssecurityis basedonthecomputationalintractabilityof thediscretelogarithmproblem(DLP)in prime-ordersubgroupsof .Ellipticcurve cryptosystems(ECC)wereinventedby NealKoblitz[49]andVictorMiller[67] canbeviewedasellipticcurve analoguesoftheolderdiscretelogarithm(DL) cryptosystemsinwhichthesubgroupof is replacedbythegroupofpointsonanellipticcu rve overa cryptosystemsis thecomputationalintractabilityoftheellip ticcurve discretelogarithmproblem(ECDLP).Sincethe ECDLP appearstobesignificantlyharderthantheDLP , thestrength-per-key-bitis substantiallygreaterin ellipticcurve systemsthanin conventionaldiscretelogarithmsystems. Thus, smallerparameterscanbeusedin ECCthanwithDLsys-temsbutwithequivalentle velsofsecurity. Theadvantagesthatcanbegainedfromsmallerp arametersincludespeed(fastercomputations )andsmallerkeysandcertifi-cates. Theseadvantagesareespeciallyimportantin environmentswhereprocessingpower, storagespace, bandwidth,orpowerconsumptionis DigitalSignatureAlgorithm (ECDSA) is theellipticcurve analogueof 1992by ScottVanstone[108]in responsetoNIST s (NationalInstituteofStandardsandTechnolo gy)requestforpubliccom-mentsontheirfirst proposalforDSS.

3 It wasacceptedin1998asanISO(Inter-nationalS tandardsOrganization)standard(ISO14888-3 ),acceptedin 1999asanANSI(AmericanNationalStandardsIn stitute)standard( ),andacceptedin 2000asanIEEE(Instituteof ElectricalandElectronicsEngineers)standa rd(IEEE1363-2000)anda FIPS standard(FIPS186-2).It is alsounderconsiderationforin-clusioninsom eotherISOstandards. Inthispaper, we ,presentrationaleforsomeof thedesigndecisions, anddiscussrelatedse-curity, implementation, In 2,we brieftutorialonfinitefieldsandellipticcu rvesisprovidedin 3 and 4, respectively. In 5, methodsfordomainparametergenerationandva lidationareconsidered,while 6 discussesmethodsforkey pairgenerationandpublickey studiedin , someimplementationandinteroperabilityiss uesareconsideredin 9 and 10. tohand-writtensignatures(andmore).A digitalsignatureis a numberdependentonsomesecretknownonlytoth esigner(thesigner s privatekey),and,additionally, if a disputearisesasto whetheranentitysigneda document,anunbiasedthirdparty shouldbeable toresolve thematterequitably, withoutrequiringaccesstothesigner s privatekey.

4 Disputesmay arisewhena signertriestorepudiatea signatureit didcreate, orwhenaforgermakesa concernedwithasymmetric digitalsignaturesschemeswithappendix. Asymmetric meansthateachentityselectsa key pairconsistingofa privatekeyanda relatedpublickey. Theentitymaintainsthesecrecyoftheprivate key whichitusesforsigningmessages, andmakesauthenticcopiesof itspublickey available tootherentitieswhichuseit to verifysignatures. Appendix meansthata cryptographichashfunctionis usedtocreatea messagedigestofthemessage, andthesigningtransformationis appliedto themessagedigestratherthanto Ideally, a digitalsignatureschemeshouldbeexistentia llyunforgeable un-derchosen-messageattack. Thisnotionofsecuritywasintroducedby Goldwasser,MicaliandRivest[33].Informall y, it asserts thatanadversary whois able toobtainentity s signaturesforany messagesofitschoiceis unable tosuccessfullyforge s signatureona Digitalsignatureschemescanbeusedtoprovid ethefollowingba-siccryptographicservices :dataintegrity(theassurancethatdatahasno tbeenal-teredby unauthorizedorunknownmeans),dataoriginau thentication(theassur-ancethatthesourceo f datais asclaimed),andnon-repudiation(theassuran cethatanentitycannotdeny previousactionsorcommitments).

5 Digitalsignatureschemesarecommonlyusedas primitivesincryptographicprotocolsthatpr ovideotherser-vicesincludingentityauthen tication( ,FIPS196[72],ISO/IEC9798-3[40],andBlake- WilsonandMenezes[10]),authenticatedkey transport ( ,Blake-WilsonandMenezes[10], [4],andISO/IEC11770-3[41]),andauthentica tedkey agreement( ,ISO/IEC11770-3[41],Diffie, vanOorschotandWiener[21],andBellare, CanettiandKrawczyk[8]).CLASSIFICATION. Thedigitalsignatureschemesinusetoday canbeclassifiedac-cordingtothehardunderl yingmathematicalproblemwhichprovidestheb asisfortheirsecurity: (IF)schemes, whichbasetheirsecurityontheintractabilit yof theseincludetheRSA[85]andRabin[84] (DL)schemes, whichbasetheirsecurityontheintractabilit yofthe(ordinary)discretelogarithmproblem ina [23],Schnorr[90],DSA[70],andNyberg-Ruepp el[78,79] (EC)schemes, whichbasetheirsecurityontheintractabilit yof theellipticcurve (DSA)TheDSAwasproposedin August1991by NationalInstituteofStandardsandTechnolog y(NIST)andwasspecifiedin a GovernmentFederal InformationProcessingStandard(FIPS186[70 ])calledtheDigitalSignatureStandard(DSS) .

6 TheDSAcanbeviewedasa variantoftheElGamalsignaturescheme[23].I tssecurityis basedontheintractabilityof thediscretelogarithmproblemin prime-ordersubgroupsof .DSA DOMAINPARAMETERGENERATION. Domainparametersaregeneratedfor eachentityin a particularsecuritydomain.(Seealsothenote below onsecuregenerationof parameters.) 160-bitprime anda 1024-bitprime withtheproperty that .2.(Selecta generator of theuniquecyclicgroupoforder in .)Selectanelement andcompute "! $#&%('*) +-, . (Repeatuntil /. 0 .) , and .DSA KEYPAIRGENERATION. Eachentity in thedomainwithdomainparameters1 324 52( -6 randomorpseudorandominteger7suchthat 98:7;8: < : . > @?) +5, .3. s publickey is=; s privatekey SIGNATUREGENERATION. To signa messageA, randomorpseudorandomintegerB, C8>BD8: < : . > 5G) +-, andH9 IE) +-, . IfHJ IKthengoto ! L) +5, . SHA-11A; B! M*PQ7RH5 ) +.

7 IfO< IKthengoto s signatureforthemessageAis1HS2TO" SIGNATUREVERIFICATIONTo verify s signature1HV2 TOV6onA,Wobtainsauthen-ticcopiesof s domainparameters1 324 52( -6andpublickey= theintervalXY "24 9 : SHA-11A; [ O! ) +-, . \ M][) +-, and\ ^H"[) +-, . > @_a` =@_Sb) +-, andc ^E) +-, . andonlyifc ^ SinceHandOareeachintegerslessthan , DSAsignaturesare320bitsin size. Thesecurityof theDSAreliesontwo distinctbut relateddiscretelogarithmproblems. Oneis thediscretelogarithmproblemin wherethenumberfieldsieve Algorithm (seeGordon[35]andSchirokauer[89 ])applies;thisalgorithmhasa subexponentialrunningtime. Moreprecisely, theexpectedrunningtimeof thealgorithmisdfehgji-kle1nmPpo1 q6 61nrts u6 $%(v1nrtswrts 6 4%(vhxux21 q6wheremzy "{}|a~a , andr&s* isa 1024-bitprime, thentheexpression(1)representsaninfeasib leamountofcomputation;thustheDSAusinga 1024-bitprime is currentlynotvulnerable tothisattack.]]

8 Theseconddiscretelogarithmproblemworksto thebase in thesubgroupof order in : given , , , and=, find7suchthat= > @?1) +5, 6. Forlarge ( ,1024-bits),thebestalgorithmknownforthis problemis Pollard s rhomethod[83],andtakesabout "~1~ 6steps. If y~ , thentheexpression(2)representsaninfeasib le amountof compu-tation;thustheDSAis notvulnerable to thisattack. However, notethattherearetwoprimary securityparametersforDSA,thesize of andthesize of . Increasingonewithouta correspondingincreasein theotherwillnotresultin aneffective increasein security. Furthermore, anadvancein algorithmsforeitheroneofthetwo Inresponsetosomecriticismsreceivedonthef irstdraft(seeRueppeletal.[86]andSmidandB ranstad[99]),FIPS186specifieda methodforgeneratingprimes and verifiably atrandom .Thisfea-turepreventsanentity( ,a central authoritygeneratingdomainparametersto besharedby a network ofentities)fromintentionallyconstructing weak primes and forwhichthediscretelogarithmproblemis relativelyeasy.

9 Forfurtherdiscussionof thisissue, seeGordon[34].FIPS186alsospecifiestwo methods, basedonDES andSHA-1,forpseudorandomlygeneratingpriv atekeys7andper-messagesecretsB. FIPS186mandatestheuseofthesealgorithms, orany providea briefintroductionto finitefields. Forfurtherinformation,seeChapter3of Koblitz[52],orthebooksby McEliece[61]andLidlandNiederreitter[59]. Afinitefieldconsistsof a finitesetof elements togetherwithtwo binary operationson , calledadditionandmultiplication,thatsati sfycertainarithmeticproperties. Theorderof a finitefieldis thenumberof elementsin finitefieldoforder if andonlyif is a primepower. If is a primepower, thenthereis essentiallyonlyonefinitefieldoforder ; thisfieldis denotedby '. Thereare, however, manywaysofrepresentingtheelementsof '. Somerepresentationsmay leadtomoreefficientimplementationsofthef ieldarithmeticin hardwareorin C R where is a primeandAis a positive integer, then is calledthecharacter-isticof 'andAis calledtheextensiondegreeof '.

10 Moststandardswhichspecifytheellipticcurv e cryptographictechniquesrestricttheordero ftheunderlyingfinitefieldto beanoddprime( C ) ora powerof 2 ( C ~ 6. In ,we describetheel-ementsandtheoperationsof thefinitefield . In ,elementsandtheoperationsofthefinitefiel d aredescribed,togetherwithtwo Let bea primenumber. Thefinitefield , calledaprimefield, is comprisedofthesetof integers K-2] "2T~52h{h{h{ 2n : V withthefollowingarithmeticoperations: 3 If 2T D Q , then PI H, whereHis theremainderwhen P^ isdividedby andK 8 H 8/ . Thisis knownasadditionmodulo . p ] R If 2T C , then S O, whereOis theremainderwhen V is dividedby andK 8 O 8/ . Thisis knownasmultiplicationmodulo . T h n 3 If is a non-zeroelementin , theinverseof modulo , denoted ! , is theuniqueintegerm D forwhich J m 0 .Example1.(Thefinitefield v) Theelementsof vare K-2] "2T~52h{h{h{ 2T~a~@.)}}}}}}