SEC 2: Recommended Elliptic Curve Domain …

1 STANDARDS FOREFFICIENTCRYPTOGRAPHYSEC 2: Recommended Elliptic Curve Domain ParametersCerticom 20, 2000Ve r s i o n 1 . 0c 2000 Certicom to copy this document is granted providedit is identified as Standards for Efficient Cryptography (SEC) ,in all material mentioning or referencing 2 - ContentsPage Overview .. Compliance .. DocumentEvolution .. Elliptic Curve Domain parameters of Elliptic Curve Domain parameters 112-bit Elliptic Curve Domain parameters parameters secp112r1 .. parameters secp112r2 .. 128-bit Elliptic Curve Domain parameters parameters secp128r1 .. parameters secp128r2 .. 160-bit Elliptic Curve Domain parameters parameters secp160k1 .. parameters secp160r1 .. parameters secp160r2 .. 192-bit Elliptic Curve Domain parameters parameters secp192k1 .. parameters secp192r1 .. 224-bit Elliptic Curve Domain parameters parameters secp224k1 .. parameters secp224r1.

2 256-bit Elliptic Curve Domain parameters parameters secp256k1 .. parameters secp256r1 .. 384-bit Elliptic Curve Domain parameters parameters secp384r1 .. 16 Page iiSEC 2: Recommended Elliptic Curve Domain parameters Ver. 521-bit Elliptic Curve Domain parameters parameters secp521r1 .. 183 Recommended Elliptic Curve Domain parameters of Elliptic Curve Domain parameters 113-bit Elliptic Curve Domain parameters parameters sect113r1 .. parameters sect113r2 .. 131-bit Elliptic Curve Domain parameters parameters sect131r1 .. parameters sect131r2 .. 163-bit Elliptic Curve Domain parameters parameters sect163k1 .. parameters sect163r1 .. parameters sect163r2 .. 193-bit Elliptic Curve Domain parameters parameters sect193r1 .. parameters sect193r2 .. 233-bit Elliptic Curve Domain parameters parameters sect233k1.

3 parameters sect233r1 .. 239-bit Elliptic Curve Domain parameters parameters sect239k1 .. 283-bit Elliptic Curve Domain parameters parameters sect283k1 .. parameters sect283r1 .. 409-bit Elliptic Curve Domain parameters parameters sect409k1 .. parameters sect409r1 .. Recommended 571-bit Elliptic Curve Domain parameters Recommended parameters sect571k1 .. 37 SEC 2 - ContentsPage Recommended parameters sect571r1 .. 38A Syntax for Elliptic Curve Domain parameters .. Object Identifiers for Recommended parameters .. OIDs for Recommended parameters OIDs for Recommended parameters 43B References45 Page ivSEC 2: Recommended Elliptic Curve Domain parameters Ver. of Tables1 Properties of Recommended Elliptic Curve Domain parameters of Recommended Elliptic Curve Domain parameters 214 Properties of Recommended Elliptic Curve Domain parameters 225 Status of Recommended Elliptic Curve Domain parameters 23 SEC 2 - 1 IntroductionPage OverviewThis document lists example Elliptic Curve Domain parameters at commonly required security levels foruse by implementers of SEC 1 [12] and other ECC standards like ANSI [1], ANSI [3], andIEEE P1363 [8].

4 It is strongly Recommended that implementers select parameters from among the example parameterslisted in this document when they deploy ECC-based products in order to encourage the deployment ofinteroperable ECC-based ComplianceImplementations may claim compliance with the Recommended parameters specified in this documentprovided some subset of the Recommended parameters are used by the cryptographic schemes based onelliptic Curve cryptography included in the is envisioned that implementations choosing to comply with this document will typically choose alsoto comply with its companion document, SEC 1 [12].It is intended to make a validation system available so that implementors can check compliance with thisdocument - see the SECG website, , for further Document EvolutionThis document will be reviewed every five years to ensure it remains up to date with cryptographicadvances. The next scheduled review will therefore take place in September intermittent reviews may also be performed from time-to-time as deemed necessary by theStandards for Efficient Cryptography Intellectual PropertyThe reader s attention is called to the possibility that compliance with this document may require use ofan invention covered by patent rights.

5 By publication of this document, no position is taken with respectto the validity of this claim or of any patent rights in connection therewith. The patent holder(s) mayhave filed with the SECG a statement of willingness to grant a license under these rights on reasonableand nondiscriminatory terms and conditions to applicants desiring to obtain such a license. Additionaldetails may be obtained from the patent holder and from the SECG website, 2 SEC 2: Recommended Elliptic Curve Domain parameters Ver. OrganizationThis document is organized as main body of the document focuses on the specification of Recommended Elliptic Curve domainparameters. Section 2 describes Recommended Elliptic Curve Domain parameters overFp, and Section 3describes Recommended Elliptic Curve Domain parameters appendices to the document provide additional relevant material. Appendix A provides syntax for implementations to use to identify the parameters .

6 Appendix B lists the referencescited in the 2 - 2 Recommended Elliptic Curve Domain parameters overFpPage 32 Recommended Elliptic Curve Domain parameters overFpThis section specifies the Elliptic Curve Domain parameters overFprecommended in this section is organized as follows. First Section describes relevant properties of the recommendedparameters overFp. Then Section specifies Recommended 112-bit Elliptic Curve Domain parametersoverFp, Section specifies Recommended 128-bit Elliptic Curve Domain parameters overFp, Sec-tion specifies Recommended 160-bit Elliptic Curve Domain parameters overFp, Section specifiesrecommended 192-bit Elliptic Curve Domain parameters overFp, Section specifies Recommended 224-bit Elliptic Curve Domain parameters overFp, Section specifies Recommended 256-bit Elliptic curvedomain parameters overFp, Section specifies Recommended 384-bit Elliptic Curve Domain parametersoverFp, Section specifies Recommended 521-bit Elliptic Curve Domain parameters overFp, Properties of Elliptic Curve Domain parameters overFpFollowing SEC 1 [12], Elliptic Curve Domain parameters overFpare a sextuple:T=(p;a;b;G;n;h)consisting of an integerpspecifying the finite fieldFp, two elementsa.

7 B2 Fpspecifying an Elliptic curveE(Fp)defined by the equation:E:y2 x3+a:x+b(modp);a base pointG=(xG;yG)onE(Fp),aprimenwhich is the order ofG, and an integerhwhich is thecofactorh=#E(Fp)= Elliptic Curve Domain parameters are specified in this document, each component of this sextupleis represented as an octet string converted using the conventions specified in SEC 1 [12].Again following SEC 1 [12], Elliptic Curve Domain parameters overFpmust have:dlog2pe2f112;128;160;192;224;256;38 4;521g:This restriction is designed to encourage interoperability while allowing implementers to supply com-monly required security levels recall that Elliptic Curve Domain parameters overFpwithdlog2pe=2tsupply approximatelytbits of security meaning that solving the logarithm problem on the associatedelliptic Curve is believed to take approximately Recommended Elliptic Curve Domain parameters are supplied at each of the sizes allowed in SEC the Recommended Elliptic Curve Domain parameters overFpuse special form primes for their fieldorderp.

8 These special form primes facilitate especially efficient implementations like those described in[5]. Recommended Elliptic Curve Domain parameters overFpwhich use random primes for their fieldorderpmay be added later if commercial demand for such parameters Elliptic Curve Domain parameters overFpsupplied at each security level typically consist of examplesof two different types of parameters one type being parameters associated with a Koblitz Curve and thePage 4 SEC 2: Recommended Elliptic Curve Domain parameters Ver. type being parameters chosen verifiably at random although only verifiably random parametersare supplied at export strength and at extremely high associated with a Koblitz Curve admit especially efficient implementation. The name Koblitzcurve is best-known when used to describe binary anomalous curves overF2mwhich havea;b2f0;1g[9].Here it is generalized to refer also to curves overFpwhich possess an efficiently computable endomor-phism [7].

9 The Recommended parameters associated with a Koblitz Curve were chosen by repeatedlyselecting parameters admitting an efficiently computable endomorphism until a prime order Curve random parameters offer some additional conservative features. These parameters are chosenfrom a seed using SHA-1 as specified in ANSI [1]. This process ensures that the parameterscannot be predetermined. The parameters are therefore extremely unlikely to be susceptible to futurespecial-purpose attacks, and no trapdoors can have been placed in the parameters during their Elliptic Curve Domain parameters are chosen verifiably at random, the seedSused to generate theparameters may optionally be stored along with the parameters so that users can verify the parameterswere chosen verifiably at verifiably random parameters have been chosen either so that the associated Elliptic Curve has primeorder, or so that scalar multiplication of points on the associated Elliptic Curve can be accelerated usingMontgomery s method [10].

10 The Recommended verifiably random parameters were chosen by repeatedlyselecting a random seed and counting the number of points on the corresponding Curve until appropriateparameters were found. Typically the parameters were chosen so thata=p 3 because such parametersadmit efficient implementation. For a givenp, approximately half the isomorphism classes of ellipticcurves overFpcontain a Curve witha=p SEC 1 [12] for further guidance on the selection of Elliptic Curve Domain parameters Recommended Elliptic Curve Domain parameters overFphave been given nicknames to enable themto be easily identified. The nicknames were chosen as follows. Each name begins withsecto denote Standards for Efficient Cryptography , followed by apto denote parameters overFp, followed by anumber denoting the length in bits of the field sizep, followed by akto denote parameters associatedwith a Koblitz Curve or anrto denote verifiably random parameters , followed by a sequence 1 summarizes salient properties of the Recommended Elliptic Curve Domain parameters is represented in Table 1 as follows.