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.

3 Theseadvantagesareespeciallyimportantin environmentswhereprocessingpower, storagespace, bandwidth,orpowerconsumptionis DigitalSignatureAlgorithm (ECDSA) is theellipticcurve analogueof 1992by ScottVanstone[108]in responsetoNIST s (NationalInstituteofStandardsandTechnolo gy)requestforpubliccom-mentsontheirfirst proposalforDSS. 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.

4 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. Disputesmay arisewhena signertriestorepudiatea signatureit didcreate, orwhenaforgermakesa concernedwithasymmetric digitalsignaturesschemeswithappendix. Asymmetric meansthateachentityselectsa key pairconsistingofa privatekeyanda relatedpublickey. Theentitymaintainsthesecrecyoftheprivate key whichitusesforsigningmessages, andmakesauthenticcopiesof itspublickey available tootherentitieswhichuseit to verifysignatures.

5 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).Digitalsig natureschemesarecommonlyusedasprimitives incryptographicprotocolsthatprovideother ser-vicesincludingentityauthentication( ,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]).

6 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) .TheDSAcanbeviewedasa variantoftheElGamalsignaturescheme[23].I tssecurityis basedontheintractabilityof thediscretelogarithmproblemin prime-ordersubgroupsof.

7 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 ) +-, . IfO< IKthengoto s signatureforthemessageAis1HS2TO" SIGNATUREVERIFICATIONTo verify s signature1HV2 TOV6onA,Wobtainsauthen-ticcopiesof s domainparameters1 324 52( -6andpublickey= theintervalXY "24 9 : SHA-11A; [ O!]

8 +-, . \ 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. Theseconddiscretelogarithmproblemworksto thebase in thesubgroupof order in : given , , , and=, find7suchthat= > @?1) +5, 6. Forlarge ( ,1024-bits),thebestalgorithmknownforthis problemis Pollard s rhomethod[83],andtakesabout "~1~ 6steps.]

9 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. Forfurtherdiscussionof thisissue, seeGordon[34].FIPS186alsospecifiestwo methods, basedonDES andSHA-1,forpseudorandomlygeneratingpriv atekeys7andper-messagesecretsB.

10 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 '.