< draft-irtf-cfrg-curves-10.txt   draft-irtf-cfrg-curves-11.txt >
CFRG A. Langley CFRG A. Langley
Internet-Draft Google Internet-Draft Google
Intended status: Informational M. Hamburg Intended status: Informational M. Hamburg
Expires: April 5, 2016 Rambus Cryptography Research Expires: April 11, 2016 Rambus Cryptography Research
S. Turner S. Turner
IECA, Inc. IECA, Inc.
October 3, 2015 October 9, 2015
Elliptic Curves for Security Elliptic Curves for Security
draft-irtf-cfrg-curves-10 draft-irtf-cfrg-curves-11
Abstract Abstract
This memo specifies two elliptic curves over prime fields that offer This memo specifies two elliptic curves over prime fields that offer
high practical security in cryptographic applications, including high practical security in cryptographic applications, including
Transport Layer Security (TLS). These curves are intended to operate Transport Layer Security (TLS). These curves are intended to operate
at the ~128-bit and ~224-bit security level, respectively, and are at the ~128-bit and ~224-bit security level, respectively, and are
generated deterministically based on a list of required properties. generated deterministically based on a list of required properties.
Status of This Memo Status of This Memo
skipping to change at page 1, line 37 skipping to change at page 1, line 37
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 5, 2016. This Internet-Draft will expire on April 11, 2016.
Copyright Notice Copyright Notice
Copyright (c) 2015 IETF Trust and the persons identified as the Copyright (c) 2015 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 49 skipping to change at page 2, line 49
examples are algorithms protected against certain side-channel examples are algorithms protected against certain side-channel
attacks, various 'special' prime shapes that allow faster modular attacks, various 'special' prime shapes that allow faster modular
arithmetic, and a larger set of curve models from which to choose. arithmetic, and a larger set of curve models from which to choose.
There is also concern in the community regarding the generation and There is also concern in the community regarding the generation and
potential weaknesses of the curves defined by NIST [NIST]. potential weaknesses of the curves defined by NIST [NIST].
This memo specifies two elliptic curves ("curve25519" and "curve448") This memo specifies two elliptic curves ("curve25519" and "curve448")
that lend themselves to constant-time implementation and an that lend themselves to constant-time implementation and an
exception-free scalar multiplication that is resistant to a wide exception-free scalar multiplication that is resistant to a wide
range of side-channel attacks, including timing and cache attacks. range of side-channel attacks, including timing and cache attacks.
They are Montgomery curves (where y^2 = x^3 + Ax^2 + x) and thus have They are Montgomery curves (where y^2 = x^3 + A*x^2 + x) and thus
birationally equivalent Edwards versions. Edwards curves support the have birationally equivalent Edwards versions. Edwards curves
fastest (currently known) complete formulas for the elliptic-curve support the fastest (currently known) complete formulas for the
group operations, specifically the Edwards curve x^2 + y^2 = 1 + elliptic-curve group operations, specifically the Edwards curve x^2 +
dx^2y^2 for primes p when p = 3 mod 4, and the twisted Edwards curve y^2 = 1 + d*x^2*y^2 for primes p when p = 3 mod 4, and the twisted
-x^2 + y^2 = 1 + dx^2y^2 when p = 1 mod 4. The maps to/from the Edwards curve -x^2 + y^2 = 1 + d*x^2*y^2 when p = 1 mod 4. The maps
Montgomery curves to their (twisted) Edwards equivalents are also to/from the Montgomery curves to their (twisted) Edwards equivalents
given. are also given.
This memo also specifies how these curves can be used with the This memo also specifies how these curves can be used with the
Diffie-Hellman protocol for key agreement. Diffie-Hellman protocol for key agreement.
2. Requirements Language 2. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119]. document are to be interpreted as described in RFC 2119 [RFC2119].
skipping to change at page 7, line 34 skipping to change at page 7, line 34
u = u % p u = u % p
return ''.join([chr((u >> 8*i) & 0xff) return ''.join([chr((u >> 8*i) & 0xff)
for i in range((bits+7)/8)]) for i in range((bits+7)/8)])
<CODE ENDS> <CODE ENDS>
Scalars are assumed to be randomly generated bytes. For X25519, in Scalars are assumed to be randomly generated bytes. For X25519, in
order to decode 32 random bytes as an integer scalar, set the three order to decode 32 random bytes as an integer scalar, set the three
least significant bits of the first byte and the most significant bit least significant bits of the first byte and the most significant bit
of the last to zero, set the second most significant bit of the last of the last to zero, set the second most significant bit of the last
byte to 1 and, finally, decode as little-endian. This means that byte to 1 and, finally, decode as little-endian. This means that
resulting integer is of the form 2^254 + 8 * {0, 1, ..., 2^(251) - resulting integer is of the form 2^254 plus eight times a value
1}. Likewise, for X448, set the two least significant bits of the between 0 and (2^251)-1 (inclusive). Likewise, for X448, set the two
first byte to 0, and the most significant bit of the last byte to 1. least significant bits of the first byte to 0, and the most
This means that the resulting integer is of the form 2^447 + 4 * {0, significant bit of the last byte to 1. This means that the resulting
1, ..., 2^(445) - 1}. integer is of the form 2^447 plus four times a value between 0 and
(2^445)-1 (inclusive).
<CODE BEGINS> <CODE BEGINS>
def decodeScalar25519(k): def decodeScalar25519(k):
k_list = [ord(b) for b in k] k_list = [ord(b) for b in k]
k_list[0] &= 248 k_list[0] &= 248
k_list[31] &= 127 k_list[31] &= 127
k_list[31] |= 64 k_list[31] |= 64
return decodeLittleEndian(k_list, 255) return decodeLittleEndian(k_list, 255)
def decodeScalar448(k): def decodeScalar448(k):
skipping to change at page 17, line 13 skipping to change at page 17, line 13
elliptic curves", 1998. elliptic curves", 1998.
[smart] Smart, N., "The discrete logarithm problem on elliptic [smart] Smart, N., "The discrete logarithm problem on elliptic
curves of trace one", 1999, curves of trace one", 1999,
<http://www.hpl.hp.com/techreports/97/HPL-97-128.pdf>. <http://www.hpl.hp.com/techreports/97/HPL-97-128.pdf>.
Appendix A. Deterministic Generation Appendix A. Deterministic Generation
This section specifies the procedure that was used to generate the This section specifies the procedure that was used to generate the
above curves; specifically it defines how to generate the parameter A above curves; specifically it defines how to generate the parameter A
of the Montgomery curve y^2 = x^3 + Ax^2 + x. This procedure is of the Montgomery curve y^2 = x^3 + A*x^2 + x. This procedure is
intended to be as objective as can reasonably be achieved so that intended to be as objective as can reasonably be achieved so that
it's clear that no untoward considerations influenced the choice of it's clear that no untoward considerations influenced the choice of
curve. The input to this process is p, the prime that defines the curve. The input to this process is p, the prime that defines the
underlying field. The size of p determines the amount of work needed underlying field. The size of p determines the amount of work needed
to compute a discrete logarithm in the elliptic curve group and to compute a discrete logarithm in the elliptic curve group and
choosing a precise p depends on many implementation concerns. The choosing a precise p depends on many implementation concerns. The
performance of the curve will be dominated by operations in GF(p) so performance of the curve will be dominated by operations in GF(p) so
carefully choosing a value that allows for easy reductions on the carefully choosing a value that allows for easy reductions on the
intended architecture is critical. This document does not attempt to intended architecture is critical. This document does not attempt to
articulate all these considerations. articulate all these considerations.
 End of changes. 7 change blocks. 
18 lines changed or deleted 19 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/