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

Document Type Active Internet-Draft (individual)
Last updated 2019-10-03
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: 2020-04-05                                         2019-10-03
          Elliptic curve 2y^2=x^3+x over field size 8^91+5


  In elliptic curve cryptography, 2y^2=x^3+x/GF(8^91+5) hedges a
  remote risk of potential weakness in other curves, if used in
  multi-curve Diffie--Hellman, for example.  This curve features:
  isomorphism to Miller curves from 1985; low Kolmogorov complexity
  (little room for secretly embedded trapdoors of Gordon, Young--Yung,
  or Teske); likeness to a Bitcoin curve; 34-byte keys; prime field;
  5*64-bit field arithmetic; easy reduction, inversion, Legendre
  symbol, and square root; Montgomery ladder or Edwards unified curve
  arithmetic (Hisil--Carter--Dawson--Wong); multiplication by i
  (Gallant--Lambert--Vanstone); and string-as-point encoding.

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.

  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                                             2019-10-03

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

Table of Contents
1.  Introduction
1.1.  Background
1.1.1.  Notation
1.1.2.  Basic features
1.1.3.  Multi-curve ECC
1.2.  Speculative security motivation
2.  Requirements Language (RFC 2119)
3.  Encoding points
3.1.  Point encoding process
3.1.1.  Summary
3.1.2.  Details
3.2.  Point decoding process
3.2.1.  Summary
3.2.2.  Detail
4.  Point validation
4.1.  When to validate
4.1.1.  Mandatory validation
4.1.2.  Simplified validation
4.1.4.  Minimal validation
4.2.  Point validation process
5.  OPTIONAL encodings
5.1.  Encoding scalars
5.2.  Encoding strings as points
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.  Minimizing trapdoors and backdoors
Appendix C.  Pseudocode
C.1.  Scalar multiplication of 34-byte strings
C.1.1.  Field arithmetic for GF(8^91+5)
C.1.2.  Montgomery ladder scalar multiplication
C.1.3.  Bernstein's 2-dimensional Montgomery ladder
C.1.4.  GLV in Edwards coordinates (Hisil--Carter--Dawson--Wong)
C.2  Pseudocode for test vectors
C.3. Pseudocode for a command-line demo of Diffie--Hellman
C.4  Pseudocode for public-key validation and twist insecurity
C.5.  Elligator i
D. Primality proofs and certificates
D.1.  Pratt certificate for the field size 8^91+5

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

D.2.  Pratt certificate for subgroup order


1.  Introduction
  This document specifies a type of elliptic curve cryptography (ECC)
  using the curve

    2y^2=x^3+x / GF(8^91+5).

  This curve is useful as part of a multi-curve ECC system that
  combines a diverse set of curves for extra security.

  The extra security in using multiple curves is a strongest-link,
  multi-layer, fail-safe, defense-in-depth against potential (but not
  yet known) attacks against one or more of the curves.

    Note: Using multiple curves adds a nonzero cost to an ECC system.
    On a current personal computer, this extra cost includes up to 1
    millisecond of runtime and sending an extra 34 bytes, per ECC
    transaction.  In low-end devices, the time may be higher due to
    slower processors, making the cost might be unaffordable.  Even in
Show full document text