OpenPGP Working Group Ted Rallis INTERNET-DRAFT Certicom Corporation Expires February 20, 1999 August 20, 1998 ECC Update to OpenPGP 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 view the entire list of current Internet-Drafts, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). Abstract This document updates the OpenPGP message format to support an Elliptic Curve Cryptosystem (ECC). The document assumes that the reader is familiar with OpenPGP. The document defines OpenPGP message formats for the Elliptic Curve Encryption Scheme [ECES] and the Elliptic Curve Digital Signature Algorithm [ECDSA]. Rallis, Ted. Informational [Page 1] INTERNET-DRAFT ECC Extentions to OpenPGP August 20, 1998 Table of Contents Status of this Memo 1 Abstract 1 Table of Contents 2 1. Terms 2 2. Additions to Public-Key Encrypted Session Key Packets 2 3. Additions to Version 4 Signature Packet Format 2 4. Additions to Public Key Packet Formats 3 4.1. ECC Domain 3 4.1.1. ECC Domain Tag Format 3 4.1.2. ECC Parameter Block 4 4.1.3. Basis Type Block 4 4.1.4. Curve Seed Block 5 5. Additions to Secret Key Packet Formats 5 6. Updates to Public Key Algorithm Constants 5 7. Pre-defined Curves 5 8. References 5 1. Terms EC Elliptic Curve. An elliptic curve over a finite field is a set of points which satisfy a certain equation specified by 2 field elements a and b. See [X9.62] 4.2. ECES Elliptic Curve Encryption Scheme. An encryption algorithm using elliptic curves. See [X9.63] 5.8.1. ECDSA EC Digital Signature Algorithm. A signature scheme using elliptic curves. See [X9.62]. 2. Additions to Public-Key Encrypted Session Key Packets Add the following to section 5.1: Public-Key Encrypted Session Key Packets. Algorithm Specific Fields for ECC Encryption: - MPI of ECES value QE | m + EncKey. [X9.63] 5.8.1. The value 'm' is as in the OpenPGP message format section 5.1. 3. Additions to Version 4 Signature Packet Format Add the following to Section 5.2.3: Version 4 Signature Packet Format. Rallis, Ted. Informational [Page 2] INTERNET-DRAFT ECC Extentions to OpenPGP August 20, 1998 Algorithm Specific Fields for ECDSA Signatures: - MPI of ECDSA value r as defined in [X9.62] 5.3.4. - MPI of ECDSA value s as defined in [X9.62] 5.3.4. 4. Additions to Public Key Packet Formats Add the following to Section 5.5.2: Public Key Packet Formats. Algorithm Specific Fields for ECC Public Keys: - One byte defining the ECC domain [below: 4.1.1]. - MPI of Public Key Q as encoded in [P1363] E.2.3. - ECC Parameter Block (possibly empty) [below: 4.1.2]. The first byte of this field gives information about the algorithm domain. It can reference a predefined curve or specify a curve type which the next bytes will define. Use of predefined curves is recommended. This key format is applicable to any ECC algorithm. 4.1. ECC Domain 4.1.1. ECC Domain Tag Format The following defines a byte that specifies the curve domain. If the byte is 0x20 or greater the curve is predefined. Predefined domains are specified below. If the byte is 0x1F or less it defines the type of curve and signals that an ECC Parameter Block follows. Domain Tag: - 0x00 Custom Elliptic Curve over a prime field p. - 0x01 Custom Elliptic Curve over a field with a normal basis. - 0x02 Custom Elliptic Curve over a field with trinomial basis defined by k [below: 4.1.3]. - 0x03 Custom Elliptic Curve over a field with pentanomial basis defined by k1,k2,k3 [below: 4.1.3]. - 0x04 to 0x0F Reserved for future curve types. - 0x10 to 0x1F As 0x10 to 0x1F but expect a seed value [below: 4.1.4]. - 0x20 Curve 1 [below: 7] - 0x21 Curve 2 [below: 7] Rallis, Ted. Informational [Page 3] INTERNET-DRAFT ECC Extentions to OpenPGP August 20, 1998 - 0x22 Curve 3 [below: 7] - 0x24 to 0xF0 Available for future curves. - 0xF1 to 0xFF Used for experimental curves. Curves may be added via an addendum. 4.1.2. ECC Parameter Block If the domain tag specified a predefined curve (any tag after 0x1F) this block is empty. - MPI of field size p if p is a prime field, or exponent m if field is characteristic two. - MPI of Elliptic Curve parameter a. - MPI of Elliptic Curve parameter b. - MPI of Curve Generating Point G as defined in [P1363] E.2.3. - MPI of the order r of G. - MPI of cofactor #E/r. (order of curve E divided by r). - Basis type block (possibly empty) [below: 4.1.3]. - Curve seed block (possibly empty) [below: 4.1.4]. 4.1.3. Basis Type Block Prime - Empty Optimal Normal Basis - Empty Trinomial Basis - MPI of value k. Pentanomial Basis - MPI of value k1. - MPI of value k2. Rallis, Ted. Informational [Page 4] INTERNET-DRAFT ECC Extentions to OpenPGP August 20, 1998 - MPI of value k3. 4.1.4. Curve Seed Block If the domain tag is not in the range 0x10 to 0x1F this is empty. If it is in this range this block contains the following: - MPI of SEED. Seeds are used to verify that a custom curve was generated randomly. 5. Additions to Secret Key Packet Formats Add the following to Section 5.5.3: Public Key Packet Formats. Algorithm Specific Fields for ECC secret keys: - MPI of elliptic curve private key d. As above, this is applicable to any ECC algorithm. 6. Updates to Public Key Algorithm Constants Change algorithm constants 18 and 19 from the following: 18 Elliptic Curve (reserved for) 19 ECDSA (reserved for) To the following: 18 Elliptic Curve (ECES) 19 ECDSA 7. Pre-defined Curves [Pre-defined Curves are to be determined.] 8. Encoding If a curve is over a prime field then the field elements are large integers and easily encoded as MPIs. If it is not then field elements should be encoded as defined in [P1363] 5.5. Rallis, Ted. Informational [Page 5] INTERNET-DRAFT ECC Extentions to OpenPGP August 20, 1998 9. References [X9.62] ANSI X9.62 Working Draft, June 18, 1998. [P1363] IEEE P1363 Working Draft, July, 1998. [X9.63] ANSI X9.63 Working Draft, July 5, 1998. Author Ted Rallis Certicom Corporation trallis(_at_)certicom(_dot_)com Other contributors Tim Dierks Certicom Corporation tdierks(_at_)certicom(_dot_)com David Lucey Exodus Communications dlucey(_at_)exodus(_dot_)com Rallis, Ted. Informational [Page 6]