| < 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/ | ||||