SEC 1: Elliptic Curve Cryptography

1 STANDARDS FOREFFICIENTCRYPTOGRAPHYSEC 1: Elliptic Curve CryptographyCerticom 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 1 - ContentsPage Overview .. Aim .. Compliance .. DocumentEvolution .. Finite Finite curves curves DataTypesandConversions .. Conversion .. Conversion .. FieldElement-to-OctetStringConversion .. OctetString-to-FieldElementConversion .. 143 Cryptographic Curve Domain Parameters .. Curve Domain Parameters Curve Domain Parameters 19 Page iiSEC 1: Elliptic Curve Cryptography Ver. Curve Key Pairs .. Curve Key Pair Generation Primitive .. of Elliptic Curve Public Keys.

2 Validation of Elliptic Curve Public Keys .. Curve Diffie-Hellman Primitives .. Curve Diffie-Hellman Primitive .. Curve Cofactor Diffie-Hellman Primitive .. Curve MQV Primitive .. HashFunctions .. KeyDeployment .. TaggingOperation .. TagCheckingOperation .. SymmetricEncryptionSchemes .. KeyDeployment .. 344 Signature Curve Digital Signature KeyDeployment .. SigningOperation .. VerifyingOperation .. 385 Encryption Curve Integrated Encryption Scheme .. 41 sec 1 - ContentsPage KeyDeployment .. 436 Key Agreement Curve Diffie-Hellman Scheme .. KeyDeployment .. Agreement Operation .. Curve MQV KeyDeployment.

3 Agreement Operation .. 49A Terms .. 56B Commentary on Section 2 - Mathematical Foundations .. Commentary on Section 3 - Cryptographic Components .. on Elliptic Curve Domain Parameters .. on Elliptic Curve Key on Elliptic Curve Diffie-Hellman Primitives .. on the Elliptic Curve MQV Primitive .. CommentaryonSection4-SignatureSchemes .. on the Elliptic Curve Digital Signature Algorithm .. CommentaryonSection5-EncryptionSchemes .. on the Elliptic Curve Integrated Encryption Scheme .. Commentary on Section 6 - Key Agreement Schemes .. on the Elliptic Curve Diffie-Hellman Scheme .. 69 Page ivSEC 1: Elliptic Curve Cryptography Ver. on the Elliptic Curve MQV Scheme .. AlignmentwithOtherStandards .. 72C for Elliptic Curve Syntax for Elliptic Curve Domain Parameters.

4 Syntax for Elliptic Curve Public Keys .. Syntax for Elliptic Curve Private Keys .. 84D References85 SEC1-ListofFiguresPagevList of Tables1 Representations .. 603 Comparable key sizes .. 624 AlignmentwithothercoreECCstandards .. 73 List of Figures1 ConvertingbetweenDataTypes ..9 sec 1 - 1 IntroductionPage OverviewThis document specifies public-key cryptographic schemes based on Elliptic Curve Cryptography (ECC).In particular, it specifies: signature schemes; encryption schemes; and key agreement also describes cryptographic primitives which are used to construct the schemes, and syntax foridentifying the schemes are intended for general application within computer and communications AimThe aim of this document is to facilitate deployment of ECC by completely specifying efficient, well-established, and well-understood public-key cryptographic schemes based on to encourage deployment of interoperable implementations of ECC by profiling existing stan-dards like ANSI [3], IEEE P1363 [40], and WAP WTLS [87], and draft standards like [4] and IEEE P1363A [41]

5 , but restricting the options allowed in these standards to increase thelikelihood of interoperability and to ensure conformance with all standards to help ensure ongoing detailed analysis of ECC by cryptographers by clearly, completely, andpublicly specifying baseline ComplianceImplementations may claim compliance with the cryptographic schemes specified in this document pro-vided the external interface (input and output) to the schemes is identical to the interface specified computations may be performed as specified here, or may be performed via an equivalent se-quence of that this compliance definition implies that conformant implementations must perform all the cryp-tographic checks included in the scheme specifications in this document. This is important because thechecks are essential to the prevention of subtle is intended to make a validation system available so that implementors can check compliance with thisdocument - see the SECG website, , for further 2 sec 1 : Elliptic Curve Cryptography Ver.

6 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. 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.

7 Additionaldetails may be obtained from the patent holder and from the SECG website, OrganizationThis document is organized as main body of the document focuses on the specification of public-key cryptographic schemes basedon ECC. Section 2 describes the mathematical foundations fundamental to the operation of all theschemes. Section 3 provides the cryptographic components used to build the schemes. Sections 4, 5,and 6 respectively specify signature schemes, encryption schemes, and key agreement schemes based appendices to the document provide additional relevant material. Appendix A gives a glossary ofthe acronyms and notation used as well as an explanation of the terms used. Appendix B elaboratessome of the details of the main body discussing implementation guidelines, making security remarks,and attributing references.

8 Appendix C provides reference syntax for implementations to use toidentify the schemes, and Appendix D lists the references cited in the 1 - 2 Mathematical FoundationsPage 32 Mathematical FoundationsUse of each of the public-key cryptographic schemes described in this document involves arithmeticoperations on an Elliptic Curve over a finite field. This section introduces the mathematical conceptsnecessary to understand and implement these arithmetic discusses finite fields, Section discusses Elliptic curves over finite fields, and Section the data types involved and the conventions used to convert between data Appendix B for a commentary on the contents on this section, including implementation discussion,security discussion, and Finite FieldsAbstractly a finite field consists of a finite set of objects called field elements together with the descriptionof two operations - addition and multiplication - that can be performed on pairs of field elements.

9 Theseoperations must possess certain turns out that there is a finite field containingqfield elements if and only ifqisapowerofaprimenumber, and furthermore that in fact for each suchqthere is precisely one finite field. The finite fieldcontainingqelements is denoted only two types of finite fieldsFqare used finite fieldsFpwithq=p,pan odd prime which arecalled prime finite fields, and finite fieldsF2mwithq=2mfor somem 1 which are called characteristic2 finite is necessary to describe these fields concretely in order to precisely specify cryptographic schemesbased on ECC. Section describes prime finite fields and Section describes characteristic 2finite The Finite FieldFpThe finite fieldFpis the prime finite field containingpelements. Although there is only one prime finitefieldFpfor each odd primep, there are many different ways to represent the elements the elements ofFpshould be represented by the set of integers:f0;1;:::;p 1gwith addition and multiplication defined as follows: Addition: Ifa;b2Fp,thena+b=rinFp, wherer2[0;p 1]is the remainder when the integera+bis divided byp.

10 This is known as addition modulopand writtena+b r(modp). Multiplication: Ifa;b2Fp,thena:b=sinFp, wheres2[0;p 1]is the remainder when the integerabis divided byp. This is known as multiplication modulopand writtena:b s(modp).Page 4 sec 1 : Elliptic Curve Cryptography Ver. and multiplication inFpcan be calculated efficiently using standard algorithms for ordinaryinteger arithmetic. In this representation ofFp, the additive identity or zero element is the integer 0, andthe multiplicative identity is the integer is convenient to define subtraction and division of field elements just as it is convenient to definesubtraction and division of integers. To do so, the additive inverse (or negative) and multiplicative inverseof a field element must be described: Additive inverse: Ifa2Fp, then the additive inverse( a)ofainFpis the unique solution to theequationa+x 0(modp).