PKIX Working Group L. Bassham (NIST) Internet Draft D. Johnson (Certicom) expires in six months W. Polk (NIST) November 21, 1997 Internet X.509 Public Key Infrastructure Representation of Elliptic Curve Digital Signature Algorithm (ECDSA) Keys and Signatures in Internet X.509 Public Key Infrastructure Certificates < Status of this Memo This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." To learn the current status of any Internet-Draft, please check the "1id-abstracts.txt" listing contained in the Internet- Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au Pacific Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). Abstract This is the first draft of a profile for specification of Elliptic Curve Digital Signature Algorithm (ECDSA) keys in Internet Public Key Infrastructure X.509 certificates. Please send comments on this document to the ietf-pkix@tandem.com mail list. 1 Executive Summary This specification contains guidance on the use of the Internet Public Key Infrastructure certificates to convey Elliptic Curve Digital Signature Algorithm (ECDSA) keys. This specification is an addendum to RFC xxxx, "Internet Public Key Infrastructure: Bassham, Johnson & Polk [Page 1] INTERNET DRAFT November 21 1997 Certificate and CRL Profile". Implementations of this specification must also conform to RFC xxxx. Implementations of this specification are not required to conform to other parts from that series. The Elliptic Curve Digital Signature Algorithm (ECDSA) is the elliptic curve analog of the Digital Signature Algorithm (DSA). This specification profiles the format and semantics of fields in X.509 V3 certificates containing ECDSA keys. The specification addresses the subjectPublicKeyInfo field and the keyUsage extension. 2 Requirements and Assumptions The goal is to augment the X.509 certificate profile presented in Part 1 to facilitate the use and management of ECDSA keys for those communities which use this algorithm. 2.1 Communication and Topology This profile, as presented in Part 1 and augmented by this specification, supports users without high bandwidth, real-time IP connectivity, or high connection availability. In addition, the profile allows for the presence of firewall or other filtered communication. This profile does not assume the deployment of an X.500 Directory system. The profile does not prohibit the use of an X.500 Directory, but other means of distributing certificates and certificate revocation lists (CRLs) are supported. 2.2 Acceptability Criteria The goal of the Internet Public Key Infrastructure (PKI) is to meet the needs of deterministic, automated identification, authentication, access control, and authorization functions. Support for these services determines the attributes contained in the certificate as well as the ancillary control information in the certificate such as policy data and certification path constraints. The goal of this document is to profile ECDSA certificates, specifying the contents and semantics of attributes which were not fully specified by Part 1. If not specifically addressed by this document, the contents and semantics of the fields and extensions must be as described in Part 1. 2.3 User Expectations Users of the Internet PKI are people and processes who use client software and are the subjects named in certificates. These uses Bassham, Johnson & Polk [Page 2] INTERNET DRAFT November 21 1997 include readers and writers of electronic mail, the clients for WWW browsers, WWW servers, and the key manager for IPSEC within a router. This profile recognizes the limitations of the platforms these users employ and the sophistication/attentiveness of the users themselves. This manifests itself in minimal user configuration responsibility (e.g., root keys, rules), explicit platform usage constraints within the certificate, certification path constraints which shield the user from many malicious actions, and applications which sensibly automate validation functions. 2.4 Administrator Expectations As with users, the Internet PKI profile is structured to support the individuals who generally operate Certification Authorities (CAs). Providing administrators with unbounded choices increases the chances that a subtle CA administrator mistake will result in broad compromise or unnecessarily limit interoperability. This profile defines the object identifiers and data formats that must be supported to interpret ECDSA public keys. 3 ECDSA Algorithm Support This section describes object identifiers and data formats which may be used with PKIX certificate profile to describe X.509 certificates containing a ECDSA public key or signed with ECDSA. Conforming CAs are required to use the object identifiers and data formats when issuing ECDSA certificates. Conforming applications shall recognize the object identifiers and process the data formats when processing such certificates. The Elliptic Curve Digital Signature Algorithm (ECDSA) is defined in the draft ANSI X9.62 standard [X9.62]. The ASN.1 object identifiers used to identify the ECDSA algorithm are defined in the following arc: ansi-X9-62 OBJECT IDENTIFIER ::= { iso(1) member-body(2) us(840) 10045 } 3.1 Subject Public Key Info The certificate identifies the ECDSA algorithm, conveys optional parameters, and specifies the ECDSA public key in the subjectPublicKeyInfo field. The subjectPublicKeyInfo field is a SEQUENCE of an algorithm identifier and the subjectPublicKey field. The certificate indicates the algorithm through an algorithm identifier. This algorithm identifier consists of an object identifier (OID) and optional associated parameters. Section 3.1.1 Bassham, Johnson & Polk [Page 3] INTERNET DRAFT November 21 1997 identifies the preferred OID and parameters for the ECDSA algorithm. Conforming CAs shall use the identified OID when issuing certificates containing public keys for the ECDSA algorithm. Conforming applications supporting the ECDSA algorithm shall, at a minimum, recognize the OID identified in section 3.1.1. The certificate conveys the ECDSA public key through the subjectPublicKey field. This subjectPublicKey field is a BIT STRING. Section 3.1.2 specifies the method for encoding a ECDSA public key as a BIT STRING. Conforming CAs shall encode the ECDSA public key as described in Section 3.1.2 when issuing certificates containing public keys for the ECDSA algorithm. Conforming applications supporting the ECDSA algorithm shall decode the subjectPublicKey as described in section 3.1.2 when the algorithm identifier is the one presented in 3.1.1. 3.1.1 Algorithm Identifier and Parameters When certificates contain an ECDSA public key, the id-ecPublicKey algorithm identifier shall be used. The id-ecPublicKey algorithm identifier is defined as follows: id-public-key-type OBJECT IDENTIFIER ::= { ansi-X9.62 2 } id-ecPublicKey OBJECT IDENTIFIER ::= { id-publicKeyType 1 } ECDSA requires use of certain parameters with the public key. The parameters may be included in the certificate using the following ASN.1 structure: ECParameters ::= SEQUENCE { version INTEGER { ecpVer1(1) } (ecpVer1), -- version is always 1 fieldID FieldID { {FieldTypes} }, -- identifies the finite field over -- which the curve is defined curve Curve, -- coefficients a and b of the -- elliptic curve base ECPoint, -- specifies the base point P -- on the elliptic curve order INTEGER, -- the order n of the base point cofactor INTEGER, ... } FieldElement ::= OCTET STRING Bassham, Johnson & Polk [Page 4] INTERNET DRAFT November 21 1997 The value of FieldElement shall be the octet string representation of a field element following the conversion routine in [X9.62, Section 4.3.1] Curve ::= SEQUENCE { a FieldElement, b FieldElement, seed BIT STRING OPTIONAL } ECPoint ::= OCTET STRING The value of ECPoint shall be the octet string representation of an elliptic curve point following the conversion routine in [X9.62, Section 4.4.3.b] The components of type ECParameters have the following meanings: * version specifies the version number of the elliptic curve parameters. It shall have the value 1 for this version of the Standard. The notation above creates an INTEGER named ecpVer1 and gives it a value of one. It is used to constrain version to a single value. * fieldID identifies the finite field over which the elliptic curve is defined. Finite fields are represented by values of the parameterized type FieldID, constrained to the values of the objects defined in the information object set FieldTypes. Additional detail regarding fieldID is provided below. * curve specifies the coefficients a and b of the elliptic curve E. Each coefficient shall be represented as a value of type FieldElement, an OCTET STRING. seed is an optional parameter used to derive the coefficients of a randomly generated elliptic curve. * base specifies the base point P on the elliptic curve. The base point shall be represented as a value of type ECPoint, an OCTET STRING. * order specifies the order n of the base point. * cofactor is the integer h = #E(Fq)/n. Note: This parameter is not used in ECDSA, except in parameter validation. It is included for compatibility with Elliptic Curve Key Agreement public key parameters. The AlgorithmIdentifier within subjectPublicKeyInfo is the only place within a certificate where the parameters may be used. If the ECDSA Bassham, Johnson & Polk [Page 5] INTERNET DRAFT November 21 1997 algorithm parameters are absent from the subjectPublicKeyInfo AlgorithmIdentifier and the CA signed the subject certificate using ECDSA, then the certificate issuer's ECDSA parameters apply to the subject's ECDSA key. If the ECDSA algorithm parameters are absent from the subjectPublicKeyInfo AlgorithmIdentifier and the CA signed the certificate using a signature algorithm other than ECDSA, then clients shall not validate the certificate. FieldID { FIELD-ID:IOSet } ::= SEQUENCE { fieldType FIELD-ID.&id({IOSet}), parameters FIELD-ID.&Type({IOSet}{@fieldType}) OPTIONAL } FieldTypes FIELD-ID ::= { { Prime-p IDENTIFIED BY prime-field } | { Characteristic-two IDENTIFIED BY characteristic-two-field }, ... } FIELD-ID ::= TYPE-IDENTIFIER FieldID is a parameterized type composed of two components, fieldType and parameters. These components are specified by the fields &id and &Type, which form a template for defining sets of information objects, instances of the class FIELD-ID. This class is based on the useful information object class TYPE-IDENTIFIER, described in X.681 Annex A. In an instance of FieldID, "fieldType" will contain an object identifier value that uniquely identifies the type contained in "parameters". The effect of referencing "fieldType" in both components of the fieldID sequence is to tightly bind the object identifier and its type. The information object set FieldTypes is used as the single parameter in a reference to type FieldID. FieldTypes contains two objects followed by the extension marker ("..."). Each object, which represents a finite field, contains a unique object identifier and its associated type. The values of these objects define all of the valid values that may appear in an instance of fieldID. The extension marker allows backward compatibility with future versions of this standard which may define objects to represent additional kinds of finite fields. The object identifier id-fieldType represents the root of a tree containing the object identifiers of each field type. It has the following value: id-fieldType OBJECT IDENTIFIER ::= { ansi-X9-62 fieldType(1) } The object identifiers prime-field and characteristic-two-field name Bassham, Johnson & Polk [Page 6] INTERNET DRAFT November 21 1997 the two kinds of fields defined in this Standard. They have the following values: prime-field OBJECT IDENTIFIER ::= { id-fieldType 1 } characteristic-two-field OBJECT IDENTIFIER ::= { id-fieldType 2 } Prime-p ::= INTEGER -- Field size p (p in bits) Characteristic-two ::= SEQUENCE { m INTEGER, -- Field size 2^m (m in bits) basis CHARACTERISTIC-TWO.&id({BasisTypes}), parameters CHARACTERISTIC-TWO.&Type({BasisTypes}{@basis}) } BasisTypes CHARACTERISTIC-TWO::= { { NULL IDENTIFIED BY onBasis } | { Trinomial IDENTIFIED BY tpBasis } | { Pentanomial IDENTIFIED BY ppBasis }, ... } Trinomial ::= INTEGER Pentanomial ::= SEQUENCE { k1 INTEGER, k2 INTEGER, k3 INTEGER } CHARACTERISTIC-TWO ::= TYPE-IDENTIFIER The object identifier id-characteristic-two-basis represents the root of a tree containing the object identifiers for each type of basis for the characteristic-two finite fields. It has the following value: id-characteristic-two-basis OBJECT IDENTIFIER ::= { characteristic-two-field basisType(1) } The object identifiers onBasis, tpBasis and ppBasis name the three kinds of basis for characteristic-two finite fields defined by [X9.62]. They have the following values: onBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 1 } tpBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 2 } ppBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 3 } Bassham, Johnson & Polk [Page 7] INTERNET DRAFT November 21 1997 3.1.2 Encoding of ECDSA Public Keys The elliptic curve public key (an ECPoint which is an OCTET STRING) is mapped to a subjectPublicKey (a BIT STRING) as follows: the most significant bit of the OCTET STRING becomes the most significant bit of the BIT STRING, etc.; the least significant bit of the OCTET STRING becomes the least significant bit of the BIT STRING. 3.1.3 Key Usage Extension in ECDSA certificates The key usage extension may optionally appear in certificates which convey an ECDSA public key. If a certificate containing an ECDSA public key includes the keyUsage extension, only the following values may be asserted: digitalSignature; nonRepudiation; keyCertSign; and cRLSign. The keyCertSign and cRLSign values may only be asserted if the basicConstraints extension is present and cA is TRUE. 3.2 Representation of ECDSA Signatures When used to sign certificates, CRLs, or PKI messages, the ECDSA shall be used with the SHA-1 hash algorithm. The ASN.1 object identifier used to identify the ECDSA algorithm with SHA-1 shall be: ecdsa-with-SHA1 OBJECT IDENTIFIER ::= { ansi-X9-62 1 } When the ecdsa-with-SHA1 algorithm identifier is used in the SIGNED parameterized TYPE (e.g., in the signature on a certificate or CRL) it shall have NULL parameters. The ECDSA parameters in the certificate of the issuer shall apply to the verification of the signature. When signing, the ECDSA algorithm generates two values. These values are commonly referred to as r and s. To easily transfer these two values as one signature, they shall be ASN.1 encoded using the following ASN.1 structure: Ecdsa-Sig-Value ::= SEQUENCE { r INTEGER, s INTEGER } References Bassham, Johnson & Polk [Page 8] INTERNET DRAFT November 21 1997 [X9.62] X9.62-199x, "Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)" November 17, 1997. [P1363] IEEE P1363, "Standard for Public-Key Cryptography", draft standard, 1997. [RFC xxxx] R. Housley, W. Ford, W. Polk and D. Solo "Internet X.509 Public Key Infrastructure: Certificate and CRL Profile", October 28, 1997. Patent Statements To be added. Security Considerations This entire memo is about security mechanisms. Author Addresses: Larry Bassham NIST Building 820, Room 426 Gaithersburg, MD 20899 USA lbassham@nist.gov Don Johnson Certicom 7684 Knightshayes Drive Manassas, VA 20111 djohnson@certicom.com Tim Polk NIST Building 820, Room 426 Gaithersburg, MD 20899 USA wpolk@nist.gov Bassham, Johnson & Polk [Page 9]