Curve4Q
draft-ladd-cfrg-4q-01

Document Type Active Internet-Draft (individual)
Last updated 2017-03-27
Stream (None)
Intended RFC status (None)
Formats plain text xml 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)
Network Working Group                                            W. Ladd
Internet-Draft                                               UC Berkeley
Intended status: Standards Track                                P. Longa
Expires: September 28, 2017                           Microsoft Research
                                                               R. Barnes
                                                                 Mozilla
                                                          March 27, 2017

                                Curve4Q
                         draft-ladd-cfrg-4q-01

Abstract

   This document specifies Curve4Q, a twisted Edwards curve proposed in
   [Curve4Q] that takes advantage of arithmetic over the field
   GF(2^127-1) and two endomorphisms to achieve the speediest Diffie-
   Hellman key agreements over a group of order approximately 2^246,
   which provides around 128 bits of security.  Curve4Q implementations
   are more than two times faster than those of Curve25519 and, when not
   using endomorphisms, are between 1.2 and 1.6 times faster.

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 http://datatracker.ietf.org/drafts/current/.

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

   This Internet-Draft will expire on September 28, 2017.

Copyright Notice

   Copyright (c) 2017 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

Ladd, et al.           Expires September 28, 2017               [Page 1]
Internet-Draft                   Curve4Q                      March 2017

   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  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Mathematical Prerequisites  . . . . . . . . . . . . . . . . .   3
   3.  Representation of Curve Points  . . . . . . . . . . . . . . .   4
   4.  Scalar multiplication . . . . . . . . . . . . . . . . . . . .   6
     4.1.  Alternative Point Representations and Addition Laws . . .   6
     4.2.  Multiplication without Endomorphisms  . . . . . . . . . .   8
     4.3.  Multiplication with Endomorphisms . . . . . . . . . . . .   9
       4.3.1.  Endomorphisms . . . . . . . . . . . . . . . . . . . .   9
       4.3.2.  Scalar Decomposition and Recoding . . . . . . . . . .  11
       4.3.3.  Final Computation . . . . . . . . . . . . . . . . . .  12
   5.  Diffie-Hellman Key Agreement  . . . . . . . . . . . . . . . .  13
   6.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  14
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .  14
   8.  Informative References  . . . . . . . . . . . . . . . . . . .  15
   Appendix A.  Constants  . . . . . . . . . . . . . . . . . . . . .  16
   Appendix B.  Point Decompression  . . . . . . . . . . . . . . . .  18
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  20

1.  Introduction

   Public key cryptography continues to be computationally expensive,
   particularly on less powerful devices.  While recent advances in
   efficient formulas for addition and doubling have substantially
   reduced the cost of elliptic curve operations in terms of field
   operations, the number of group operations involved in scalar
   multiplication has not been reduced in the curves considered for IETF
   use.  Using curves with efficiently computable endomorphisms can
   reduce the number of group operations by turning one long scalar
   multiplication into the sum of several multiplications by smaller
   scalars, which can be evaluated more efficiently.

   For curves over quadratic extension fieldss, there are more
   endomorphism families to choose from, and the field operations are
   often more efficient compared to prime fields of the same size.  The
Show full document text