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

Document Type Active Internet-Draft (individual)
Last updated 2019-04-04
Stream (None)
Intended RFC status (None)
Formats plain text pdf htmlized 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-10-06                                         2019-04-04
          Elliptic curve 2y^2=x^3+x over field size 8^91+5


  This document recommends using a special elliptic curve alongside
  dissimilar curves, such as NIST P-256, Curve25519, sect283k1,
  Brainpool, and random curves, as a cryptographic defense against an
  unlikely, undisclosed attack against mainstream curves.  Features of
  this curve 2y^2=x^3+x/GF(8^91+5) are: isomorphism to Miller curves
  from 1985; Montgomery form mappable to Edwards; simple field
  powering for inversion, Legendre symbol, and square roots; efficient
  endomorphism to speed up Diffie--Hellman with Bernstein's 2-D
  ladder; 34-byte keys; similarity to Bitcoin curve; hashing-to-point;
  low Kolmogorov complexity (low risk of backdoor).  

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

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

  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 2]
Internet-Draft                                             2019-04-04

Table of Contents
    1.  Introduction
    1.1.  Background
    1.1.1. Notation
    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 public key MAY, SHOULD or MUST be validated
    4.1.1.  Precautionary mandatory validation
    4.1.2.  Simplified validation
    4.1.3.  Relatively safe cases of non-validation
    4.1.4.  Minimal validation
    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.  IANA Considerations
    7.  Security considerations
    7.1.  Field choice
    7.2.  Curve choice
    7.3.  Encoding choices
    7.4.  General subversion concerns
    7.5.  Concerns about 'aegis'
    8.  References
    8.1.  Normative References
    8.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
    D.  Primality proofs and certificates
    D.1.  Pratt certificate for the field size 8^91+5
    D.2.  Pratt certificate for subgroup order

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

1.  Introduction
  This document relates to elliptic curve cryptography (ECC).  It
  specifies methods for using the elliptic curve 2y^2=x^3+x over the
  field of size 8^91+5.  It recommends using this curve in combination
  with a diverse set of curves, as a strongest-link multi-layer
  defense-in-depth against undisclosed attacks against some subset of

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

1.1.1. Notation

  The symbol '^', as used in '2y^2=x^3+x' and '8^91+5' means
  exponentiation, also known as powering.  For example, y^3=yyy, or
  y*y*y, if * is used for multiplication, and 8^91 = 8*8*...*8, with
Show full document text