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.

2 The Finite FieldF2m.. Elliptic curves .. Elliptic curves overFp.. Elliptic curves overF2m.. Data Types and Conversions .. Bit-String-to-Octet-String Conversion .. 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.

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

4 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 .. Key Deployment .. Encryption Operation.

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

6 Scheme Setup .. Key Deployment .. Signing Operation .. Verifying Operation .. 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.

7 Key Deployment .. Key Agreement Operation .. Elliptic Curve MQV Scheme .. Scheme Setup .. Key Deployment .. Key Agreement Operation .. 60A Terms .. Acronyms, Initialisms and Other Abbreviations .. Notation .. 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.

8 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 .. Commentary on Section 4 Signature Schemes .. Commentary on the Elliptic Curve Digital Signature Algorithm .. Commentary on Section 5 Encryption Schemes.

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

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