SEC 1: Elliptic Curve Cryptography

1 Standards for Efficient CryptographySEC 1: Elliptic Curve CryptographyCerticom ResearchContact: Daniel R. L. Brown 21, 2009 Version 2009 Certicom to copy this document is granted provided it is identified as Standards for EfficientCryptography 1 ( sec 1 ) , in all material mentioning or referencing 1 Ver. Overview .. Aim .. Compliance .. Document Evolution .. Intellectual Property .. Organization .. 22 Mathematical Finite Fields .. The Finite FieldFp.. The Finite FieldF2m.. Elliptic curves .. Elliptic curves overFp.. Elliptic curves overF2m.. Data Types and Conversions .. Bit-String-to-Octet-String Conversion.

2 Octet-String-to-Bit-String Conversion .. Elliptic - Curve -Point-to-Octet-String Conversion .. Octet-String-to- Elliptic - Curve -Point Conversion .. Field-Element-to-Octet-String Conversion .. Octet-String-to-Field-Element Conversion .. Integer-to-Octet-String Conversion .. Octet-String-to-Integer Conversion .. Field-Element-to-Integer Conversion .. 143 Cryptographic Elliptic Curve Domain Parameters .. Elliptic Curve Domain Parameters overFp.. Elliptic Curve Domain Parameters overF2m.. Verifiably Random curves and Base Point Generators .. Elliptic Curve Key Pairs .. 23 ContentsPage i of vSEC 1 Ver.

3 Elliptic Curve Key Pair Generation Primitive .. Validation of Elliptic Curve Public Keys .. Partial Validation of Elliptic Curve Public Keys .. Verifiable and Assisted Key Pair Generation and Validation .. Elliptic Curve Diffie-Hellman Primitives .. Elliptic Curve Diffie-Hellman Primitive .. Elliptic Curve Cofactor Diffie-Hellman Primitive .. Elliptic Curve MQV Primitive .. Hash Functions .. Key Derivation Functions .. ANS Key Derivation Function .. MAC schemes .. Scheme Setup .. Key Deployment .. Tagging Operation .. Tag Checking Operation .. Symmetric Encryption Schemes .. Scheme Setup.

4 Key Deployment .. Encryption Operation .. Decryption Operation .. Key Wrap Schemes .. Key Wrap Scheme Setup .. Key Wrap Schemes Key Generation .. Key Wrap Schemes Wrap Operation .. Key Wrap Schemes Unwrap Operation .. Random Number Generation .. Entropy .. Deterministic Generation of Pseudorandom Bit Strings .. Converting Random Bit Strings to Random Numbers .. Security Levels and Protection Lifetimes .. 424 Signature Schemes43 Page ii of vContentsSEC 1 Ver. Elliptic Curve Digital Signature Algorithm .. Scheme Setup .. Key Deployment .. Signing Operation .. Verifying Operation.

5 Alternative Verifying Operation .. Public Key Recovery Operation .. Self-Signing Operation .. 485 Encryption and Key Transport Elliptic Curve Integrated Encryption Scheme .. Scheme Setup .. Key Deployment .. Encryption Operation .. Decryption Operation .. Wrapped Key Transport Scheme .. 546 Key Agreement Elliptic Curve Diffie-Hellman Scheme .. Scheme Setup .. Key Deployment .. Key Agreement Operation .. Elliptic Curve MQV Scheme .. Scheme Setup .. Key Deployment .. Key Agreement Operation .. 60A Terms .. Acronyms, Initialisms and Other Abbreviations .. Notation.

6 68B Commentary on Section 2 Mathematical Foundations .. 70 ContentsPage iii of vSEC 1 Ver. Commentary on Section 3 Cryptographic Components .. Commentary on Elliptic Curve Domain Parameters .. Commentary on Elliptic Curve Key Pairs .. Commentary on Elliptic Curve Diffie-Hellman Primitives .. Commentary on the Elliptic Curve MQV Primitive .. Commentary on Hash Functions .. Commentary on Key Derivation Functions .. Commentary on MAC Schemes .. Commentary on Symmetric Encryption Schemes .. Commentary on Key Wrap Schemes .. Commentary on Random Number Generation .. Commentary on Security Levels and Protection Lifetimes.

7 Commentary on Section 4 Signature Schemes .. Commentary on the Elliptic Curve Digital Signature Algorithm .. Commentary on Section 5 Encryption Schemes .. Commentary on the Elliptic Curve Integrated Encryption Scheme .. Commentary on Wrapped Key Transport Scheme .. Commentary on Section 6 Key Agreement Schemes .. Commentary on the Elliptic Curve Diffie-Hellman Scheme .. Commentary on the Elliptic Curve MQV Scheme .. Alignment with Other Standards .. 96C for Elliptic Curve Syntax for Finite Fields .. Syntax for Elliptic Curve Domain Parameters .. Syntax for Elliptic Curve Public Keys .. Syntax for Elliptic Curve Private Keys.

8 Syntax for Signature and Key Establishment Schemes .. Syntax for Key Derivation Functions .. Protocol Data Unit Syntax .. Module .. 116D References138 Page iv of vContentsSEC 1 Ver. of Tables1 Representations ofF2m.. 52 Computing power required to solve ECDLP .. 713 Comparable key sizes .. 734 Alignment with other ECC standards .. 97 List of Figures1 Converting between Data Types .. 9 List of TablesPage v of vSEC 1 Ver. IntroductionThis section gives an overview of this standard, its use, its aims, and its OverviewThis document specifies public-key cryptographic schemes based on Elliptic Curve Cryptography (ECC).

9 In particular, it specifies: signature schemes; encryption and key transport schemes; and key agreement also describes cryptographic primitives which are used to construct the schemes, and for identifying the schemes are intended for general application within computer and communications AimThe aim of this document is threefold: Firstly, to facilitate deployment of ECC by completely specifying efficient, well-established,and well-understood public-key cryptographic schemes based on ECC. Secondly, to encourage deployment of interoperable implementations of ECC by profilingstandards such as ANS [ ], WAP WTLS [WTLS], ANS [ ] andIEEE 1363 [1363], and recommendation NIST SP 800-56 [800-56A], but restricting the op-tions allowed in these standards to increase the likelihood of interoperability and to ensureconformance with as many standards as possible.

10 Thirdly, to help ensure ongoing detailed analysis of ECC by cryptographers by clearly, com-pletely, and publicly specifying baseline ComplianceImplementations may claim compliance with the cryptographic schemes specified in this documentprovide the external interface (input and output) to the schemes is equivalent to the interfacespecified here. Internal computations may be performed as specified here, or may be performedvia an equivalent sequence of that this compliance definition implies that conformant implementations must perform allthe cryptographic checks included in the scheme specifications in this document. This is importantbecause the checks are essential for the prevention of subtle attacks.