Elliptic curve 2y^2=x^3+x over field size 8^91+5

Document Type Active Internet-Draft (individual)
Last updated 2018-10-04
Stream (None)
Intended RFC status (None)
Formats plain text pdf html bibtex
Stream Stream state (No stream defined)
Consensus Boilerplate Unknown
RFC Editor Note (None)
IESG IESG state I-D Exists
Telechat date
Responsible AD (None)
Send notices to (None)
Internet-Draft                                                D. Brown
Intended status: Experimental                               BlackBerry
Expires: 2019-04-07                                         2018-10-04
          Elliptic curve 2y^2=x^3+x over field size 8^91+5


  This document specifies a special elliptic curve with a compact
  description (see title) and an efficient endormorphism (complex
  multiplication by i).  This curve is only recommended for
  cryptographic use in a strongest-link combination with dissimilar
  elliptic curves (e.g. NIST P-256, Curve25519, extension-field
  curves, etc.).  Used in this manner, the curve special features
  serve as a defense in depth against an unlikely event: a new or
  secret attack against the other types of elliptic curves.

Status of This Memo
  This Internet-Draft is submitted in full conformance with the
  provisions of BCP 78 and BCP 79.  Internet-Drafts are working
  documents of the Internet Engineering Task Force (IETF).  Note that
  other groups may also distribute working documents as
  Internet-Drafts.  The list of current Internet-Drafts is at

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

Copyright Notice
  Copyright (c) 2018 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.

  This document may not be modified, and derivative works of it may
  not be created, except to format it for publication as an RFC or to
  translate it into languages other than English.

Brown                2y^2=x^3+x over 8^91+5                 [Page 1]
Internet-Draft                                             2018-10-04

Table of Contents
  1.  Introduction
  1.1.  Background
  1.2.  Motivation
  2.  Requirements Language (RFC 2119)
  3.  Encoding a point into 34 bytes
  3.1.  Encoding a point into bytes
  3.2.  Decoding bytes into a point
  4.  Point validation
  4.1.  When a point MUST be validated
  4.2.  How to validate a point (given only x)
  5.  OPTIONAL encodings
  5.1.  Encoding scalar multipliers as 34 bytes
  5.2.  Encoding 34 bytes into a point (sketch)
  6.  Cryptographic schemes
  6.1.  Diffie--Hellman key agreement
  6.2.  Signatures
  6.3  Menezes--Qu--Vanstone key agreement
  7.  IANA Considerations
  8.  Security considerations
  8.1.  Field choice
  8.2.  Curve choice
  8.3.  Encoding choices
  8.4.  General subversion concerns
  9.  References
  9.1.  Normative References 
  9.2.  Informative References
  Appendix A.  Test vectors
  Appendix B.  Motivation: minimizing the room for backdoors
  Appendix C.  Pseudocode
  C.1.  Byte encoding
  C.2.  Byte decoding
  C.3.  Fermat inversion
  C.4.  Branchless Legendre symbol computation
  C.5.  Field multiplication and squaring
  C.6.  Field element partial reduction
  C.7.  Field element final reduction
  C.8.  Scalar point multiplication
  C.9.  Diffie--Hellman pseudocode
  C.10.  Elligator i
  Appendix D.  Primality proofs and certificates
  D.1 Pratt certificate for the field size 8^91+5
  D.2 Pratt certificate for size of the large elliptic curve subgroup

Brown                2y^2=x^3+x over 8^91+5                 [Page 2]
Internet-Draft                                             2018-10-04

1.  Introduction
  This document specifies some conventions for using the elliptic
  curve 2y^2=x^3+x over the field of size 8^91+5 in cryptography.

  This draft focuses on applications to Diffie--Hellman exchange.

1.1.  Background
  This document presumes that its reader already has familiarity with
  elliptic curve cryptography.

  The symbol '^', as used in '2y^2=x^3+x' and '8^91+5' means
  exponentiation, also known as powering.  In particular, it does not
  mean bit-wise exclusive-or (as in the C programming language
  operator).  For example, y^3=yyy (or y*y*y, if * is used for

  In particular, p=8^91+5 is a (positive) prime number.  Its encoding
  into bytes, using little-endian ordering (least significant bytes
  first), requires 35 bytes, and has the form {5,0,0,...,2}, with the
  first byte equal to 5, the last 2, and the 33 intermediate bytes are
  each 0.  A byte encoding of p is not needed for this document, and
  is only shown here for illustrative purposes.  Its hexadecimal
  representation (i.e. big-endian, base 16), is 20...05, with 67 zeros
  between 2 and 5.
Show full document text