Fundamental Elliptic Curve Cryptography Algorithms
RFC 6090

Internet Engineering Task Force (IETF)                         D. McGrew
Request for Comments: 6090                                 Cisco Systems
Category: Informational                                          K. Igoe
ISSN: 2070-1721                                                M. Salter
                                                National Security Agency
                                                           February 2011

           Fundamental Elliptic Curve Cryptography Algorithms

Abstract

   This note describes the fundamental algorithms of Elliptic Curve
   Cryptography (ECC) as they were defined in some seminal references
   from 1994 and earlier.  These descriptions may be useful for
   implementing the fundamental algorithms without using any of the
   specialized methods that were developed in following years.  Only
   elliptic curves defined over fields of characteristic greater than
   three are in scope; these curves are those used in Suite B.

Status of This Memo

   This document is not an Internet Standards Track specification; it is
   published for informational purposes.

   This document is a product of the Internet Engineering Task Force
   (IETF).  It represents the consensus of the IETF community.  It has
   received public review and has been approved for publication by the
   Internet Engineering Steering Group (IESG).  Not all documents
   approved by the IESG are a candidate for any level of Internet
   Standard; see Section 2 of RFC 5741.

   Information about the current status of this document, any errata,
   and how to provide feedback on it may be obtained at
   http://www.rfc-editor.org/info/rfc6090.

McGrew, et al.                Informational                     [Page 1]
RFC 6090                     Fundamental ECC               February 2011

Copyright Notice

   Copyright (c) 2011 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
     1.1.  Conventions Used in This Document  . . . . . . . . . . . .  4
   2.  Mathematical Background  . . . . . . . . . . . . . . . . . . .  4
     2.1.  Modular Arithmetic . . . . . . . . . . . . . . . . . . . .  4
     2.2.  Group Operations . . . . . . . . . . . . . . . . . . . . .  5
     2.3.  The Finite Field Fp  . . . . . . . . . . . . . . . . . . .  6
   3.  Elliptic Curve Groups  . . . . . . . . . . . . . . . . . . . .  7
     3.1.  Homogeneous Coordinates  . . . . . . . . . . . . . . . . .  8
     3.2.  Other Coordinates  . . . . . . . . . . . . . . . . . . . .  9
     3.3.  ECC Parameters . . . . . . . . . . . . . . . . . . . . . .  9
       3.3.1.  Discriminant . . . . . . . . . . . . . . . . . . . . . 10
       3.3.2.  Security . . . . . . . . . . . . . . . . . . . . . . . 10
   4.  Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 10
     4.1.  Data Types . . . . . . . . . . . . . . . . . . . . . . . . 11
     4.2.  Compact Representation . . . . . . . . . . . . . . . . . . 11
   5.  Elliptic Curve ElGamal Signatures  . . . . . . . . . . . . . . 11
     5.1.  Background . . . . . . . . . . . . . . . . . . . . . . . . 11
     5.2.  Hash Functions . . . . . . . . . . . . . . . . . . . . . . 12
     5.3.  KT-IV Signatures . . . . . . . . . . . . . . . . . . . . . 12
       5.3.1.  Keypair Generation . . . . . . . . . . . . . . . . . . 12
       5.3.2.  Signature Creation . . . . . . . . . . . . . . . . . . 13
       5.3.3.  Signature Verification . . . . . . . . . . . . . . . . 13
     5.4.  KT-I Signatures  . . . . . . . . . . . . . . . . . . . . . 14
       5.4.1.  Keypair Generation . . . . . . . . . . . . . . . . . . 14
       5.4.2.  Signature Creation . . . . . . . . . . . . . . . . . . 14
       5.4.3.  Signature Verification . . . . . . . . . . . . . . . . 14
     5.5.  Converting KT-IV Signatures to KT-I Signatures . . . . . . 15
     5.6.  Rationale  . . . . . . . . . . . . . . . . . . . . . . . . 15
   6.  Converting between Integers and Octet Strings  . . . . . . . . 16
     6.1.  Octet-String-to-Integer Conversion . . . . . . . . . . . . 17
     6.2.  Integer-to-Octet-String Conversion . . . . . . . . . . . . 17

McGrew, et al.                Informational                     [Page 2]