draft-ietf-lwig-curve-representations-04.txt | draft-ietf-lwig-curve-representations-05.txt | |||
---|---|---|---|---|

lwig R. Struik | lwig R. Struik | |||

Internet-Draft Struik Security Consultancy | Internet-Draft Struik Security Consultancy | |||

Intended status: Informational April 19, 2019 | Intended status: Informational May 15, 2019 | |||

Expires: October 21, 2019 | Expires: November 16, 2019 | |||

Alternative Elliptic Curve Representations | Alternative Elliptic Curve Representations | |||

draft-ietf-lwig-curve-representations-04 | draft-ietf-lwig-curve-representations-05 | |||

Abstract | Abstract | |||

This document specifies how to represent Montgomery curves and | This document specifies how to represent Montgomery curves and | |||

(twisted) Edwards curves as curves in short-Weierstrass form and | (twisted) Edwards curves as curves in short-Weierstrass form and | |||

illustrates how this can be used to carry out elliptic curve | illustrates how this can be used to carry out elliptic curve | |||

computations using existing implementations of, e.g., ECDSA and ECDH | computations using existing implementations of, e.g., ECDSA and ECDH | |||

using NIST prime curves. | using NIST prime curves. | |||

Requirements Language | Requirements Language | |||

skipping to change at page 1, line 41 ¶ | skipping to change at page 1, line 41 ¶ | |||

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 https://datatracker.ietf.org/drafts/current/. | Drafts is at https://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 October 21, 2019. | This Internet-Draft will expire on November 16, 2019. | |||

Copyright Notice | Copyright Notice | |||

Copyright (c) 2019 IETF Trust and the persons identified as the | Copyright (c) 2019 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 | |||

(https://trustee.ietf.org/license-info) in effect on the date of | (https://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 23 ¶ | skipping to change at page 2, line 23 ¶ | |||

1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 4 | 1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 4 | |||

2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 4 | 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 4 | |||

3. Use of Representation Switches . . . . . . . . . . . . . . . 4 | 3. Use of Representation Switches . . . . . . . . . . . . . . . 4 | |||

4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 5 | 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 5 | |||

4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 5 | 4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 5 | |||

4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 6 | 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 6 | |||

4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 6 | 4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 6 | |||

4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 7 | 4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 7 | |||

5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 | 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 | |||

6. Security Considerations . . . . . . . . . . . . . . . . . . . 9 | 6. Implementation Considerations . . . . . . . . . . . . . . . . 9 | |||

7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 9 | 7. Security Considerations . . . . . . . . . . . . . . . . . . . 10 | |||

8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 | 8. Privacy Considerations . . . . . . . . . . . . . . . . . . . 10 | |||

8.1. COSE Elliptic Curves Registration . . . . . . . . . . . . 10 | 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 | |||

8.2. COSE Algorithms Registration (1/2) . . . . . . . . . . . 10 | 9.1. COSE Elliptic Curves Registration . . . . . . . . . . . . 11 | |||

8.3. COSE Algorithms Registration (2/2) . . . . . . . . . . . 11 | 9.2. COSE Algorithms Registration (1/2) . . . . . . . . . . . 11 | |||

8.4. JOSE Elliptic Curves Registration . . . . . . . . . . . . 11 | 9.3. COSE Algorithms Registration (2/2) . . . . . . . . . . . 12 | |||

8.5. JOSE Algorithms Registration (1/2) . . . . . . . . . . . 11 | 9.4. JOSE Elliptic Curves Registration . . . . . . . . . . . . 12 | |||

8.6. JOSE Algorithms Registration (2/2) . . . . . . . . . . . 12 | 9.5. JOSE Algorithms Registration (1/2) . . . . . . . . . . . 12 | |||

9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 12 | 9.6. JOSE Algorithms Registration (2/2) . . . . . . . . . . . 13 | |||

10. References . . . . . . . . . . . . . . . . . . . . . . . . . 12 | 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 13 | |||

10.1. Normative References . . . . . . . . . . . . . . . . . . 12 | 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 13 | |||

10.2. Informative References . . . . . . . . . . . . . . . . . 13 | 11.1. Normative References . . . . . . . . . . . . . . . . . . 13 | |||

Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 15 | 11.2. Informative References . . . . . . . . . . . . . . . . . 14 | |||

A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 15 | Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 16 | |||

A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 15 | A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 16 | |||

A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 15 | A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 16 | |||

Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 16 | A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 16 | |||

B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 16 | Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 17 | |||

B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 17 | B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 17 | |||

Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 18 | B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 18 | |||

C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 18 | Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 19 | |||

C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 19 | C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 19 | |||

C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 20 | C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 20 | |||

Appendix D. Relationship Between Curve Models . . . . . . . . . 21 | C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 21 | |||

Appendix D. Relationship Between Curve Models . . . . . . . . . 22 | ||||

D.1. Mapping between Twisted Edwards Curves and Montgomery | D.1. Mapping between Twisted Edwards Curves and Montgomery | |||

Curves . . . . . . . . . . . . . . . . . . . . . . . . . 21 | Curves . . . . . . . . . . . . . . . . . . . . . . . . . 22 | |||

D.2. Mapping between Montgomery Curves and Weierstrass Curves 22 | D.2. Mapping between Montgomery Curves and Weierstrass Curves 23 | |||

D.3. Mapping between Twisted Edwards Curves and Weierstrass | D.3. Mapping between Twisted Edwards Curves and Weierstrass | |||

Curves . . . . . . . . . . . . . . . . . . . . . . . . . 23 | Curves . . . . . . . . . . . . . . . . . . . . . . . . . 24 | |||

Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 23 | Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 24 | |||

E.1. Curve Definition and Alternative Representations . . . . 23 | E.1. Curve Definition and Alternative Representations . . . . 24 | |||

E.2. Switching between Alternative Representations . . . . . . 23 | E.2. Switching between Alternative Representations . . . . . . 24 | |||

E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 25 | E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 26 | |||

Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 27 | Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 28 | |||

F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 27 | F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 28 | |||

F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 28 | F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 29 | |||

F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 28 | F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 29 | |||

F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 29 | F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 30 | |||

Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 31 | Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 32 | |||

G.1. Further Alternative Representations . . . . . . . . . . . 31 | G.1. Further Alternative Representations . . . . . . . . . . . 32 | |||

G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 31 | G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 32 | |||

G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 32 | G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 33 | |||

Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 33 | Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 34 | |||

H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 33 | H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 34 | |||

H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 33 | H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 34 | |||

H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 36 | H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 37 | |||

H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 39 | H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 40 | |||

H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 40 | H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 41 | |||

H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 40 | H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 41 | |||

H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 42 | H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 43 | |||

H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 45 | H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 46 | |||

Appendix I. Point Compression . . . . . . . . . . . . . . . . . 46 | Appendix I. Point Compression . . . . . . . . . . . . . . . . . 47 | |||

I.1. Point Compression for Weierstrass Curves . . . . . . . . 46 | I.1. Point Compression for Weierstrass Curves . . . . . . . . 47 | |||

I.2. Point Compression for Montgomery Curves . . . . . . . . . 47 | I.2. Point Compression for Montgomery Curves . . . . . . . . . 48 | |||

I.3. Point Compression for Twisted Edwards Curves . . . . . . 48 | I.3. Point Compression for Twisted Edwards Curves . . . . . . 49 | |||

Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 48 | Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 49 | |||

J.1. Conversion between Bit Strings and Integers . . . . . . . 49 | J.1. Conversion between Bit Strings and Integers . . . . . . . 50 | |||

J.2. Conversion between Octet Strings and Integers (OS2I, | J.2. Conversion between Octet Strings and Integers (OS2I, | |||

I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 49 | I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 50 | |||

J.3. Conversion between Octet Strings and Bit Strings (BS2OS, | J.3. Conversion between Octet Strings and Bit Strings (BS2OS, | |||

OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 50 | OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 51 | |||

J.4. Conversion between Field Elements and Octet Strings | J.4. Conversion between Field Elements and Octet Strings | |||

(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 50 | (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 51 | |||

J.5. Conversion between Elements of Z mod n and Octet Strings | J.5. Conversion between Elements of Z mod n and Octet Strings | |||

(ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 50 | (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 51 | |||

J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 51 | J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 52 | |||

Appendix K. Representation Examples Curve25519 Family Members . 52 | Appendix K. Representation Examples Curve25519 Family Members . 53 | |||

K.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 52 | K.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 53 | |||

K.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 54 | K.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 55 | |||

K.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 55 | K.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 56 | |||

K.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 57 | K.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 58 | |||

K.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 58 | K.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 59 | |||

Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 60 | Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 61 | |||

L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 60 | L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 61 | |||

L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 60 | L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 61 | |||

L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 60 | L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 61 | |||

L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 61 | ||||

L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 60 | Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 62 | |||

Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 61 | ||||

1. Fostering Code Reuse with New Elliptic Curves | 1. Fostering Code Reuse with New Elliptic Curves | |||

It is well-known that elliptic curves can be represented using | It is well-known that elliptic curves can be represented using | |||

different curve models. Recently, IETF standardized elliptic curves | different curve models. Recently, IETF standardized elliptic curves | |||

that are claimed to have better performance and improved robustness | that are claimed to have better performance and improved robustness | |||

against "real world" attacks than curves represented in the | against "real world" attacks than curves represented in the | |||

traditional "short" Weierstrass model. This document specifies an | traditional "short" Weierstrass model. This document specifies an | |||

alternative representation of points of Curve25519, a so-called | alternative representation of points of Curve25519, a so-called | |||

Montgomery curve, and of points of Edwards25519, a so-called twisted | Montgomery curve, and of points of Edwards25519, a so-called twisted | |||

skipping to change at page 9, line 5 ¶ | skipping to change at page 9, line 7 ¶ | |||

NOTE 2: While an implementation of Curve25519 via an isogenous | NOTE 2: While an implementation of Curve25519 via an isogenous | |||

Weierstrass curve with domain parameter a=-3 requires a | Weierstrass curve with domain parameter a=-3 requires a | |||

relatively large table (of size roughly 9kB), for the quadratic | relatively large table (of size roughly 9kB), for the quadratic | |||

twist of Curve25519 (i.e., the Montgomery curve M_{A,B'} with | twist of Curve25519 (i.e., the Montgomery curve M_{A,B'} with | |||

A=486662 and B'=2) this implementation approach only requires a | A=486662 and B'=2) this implementation approach only requires a | |||

table of size less than 0.5kB (over 20x smaller), solely due to | table of size less than 0.5kB (over 20x smaller), solely due to | |||

the fact that it is l-isogenous to a Weierstrass curve with a=-3 | the fact that it is l-isogenous to a Weierstrass curve with a=-3 | |||

parameter with relatively small parameter l=2 (compared to l=47, | parameter with relatively small parameter l=2 (compared to l=47, | |||

as is the case with Curve25519 itself). | as is the case with Curve25519 itself). | |||

6. Security Considerations | 6. Implementation Considerations | |||

The efficiency of elliptic curve arithmetic is primarily determined | ||||

by the efficiency of its group operations (see Appendix C). Numerous | ||||

optimized formulae exist, such as the use of so-called Montgomery | ||||

ladders with Montgomery curves [Mont-Ladder] or with Weierstrass | ||||

curves [Wei-Ladder], the use of hardcoded a=-3 domain parameter for | ||||

Weierstrass curves [ECC-Isogeny], and the use of hardcoded a=-1 | ||||

domain parameters for twisted Edwards curves [tEd-Formulas]. These | ||||

all target reduction of the number of finite field operations | ||||

(primarily, finite field multiplications and squarings). Other | ||||

optimizations target more efficient modular reductions underlying | ||||

these finite field operations, by specifying curves defined over a | ||||

field GF(q), where the field size q has a special form or a specific | ||||

bit-size (typically, close to a multiple of a machine word). | ||||

Depending on the implementation strategy, the bit-size of q may also | ||||

facilitate reduced so-called "carry-effects" of integer arithmetic. | ||||

Most curves use a combination of these design philosophies. All NIST | ||||

curves [FIPS-186-4] and Brainpool curves [RFC5639] are Weierstrass | ||||

curves with a=-3 domain parameter, thus facilitating more efficient | ||||

elliptic curve group operations (via so-called Jacobian coordinates). | ||||

The NIST curves and the Montgomery curve Curve25519 are defined over | ||||

prime fields, where the prime number has a special form, whereas the | ||||

Brainpool curves - by design - use a generic prime number. None of | ||||

the NIST curves, nor the Brainpool curves, can be expressed as | ||||

Montgomery or twisted Edwards curves, whereas - conversely - | ||||

Montgomery curves and twisted curves can be expressed as Weierstrass | ||||

curves. | ||||

While use of Wei25519 allows reuse of existing generic code that | ||||

implements short Weierstrass curves, such as the NIST curve P-256, to | ||||

also implement the CFRG curves Curve25519 or Edwards25519, this | ||||

obviously does not result in an implementation of these CFRG curves | ||||

that exploits the special structure of the underlying field or other | ||||

specific domain parameters (since generic). Reuse of code, | ||||

therefore, may result in a less computationally efficient curve | ||||

implementation than would have been possible if the implementation | ||||

had specially targeted Curve25519 or Edwards25519 alone. Overall, | ||||

one should consider not just code reuse and computational efficiency, | ||||

but also development and maintenance cost, and, e.g, the cost of | ||||

providing effective implementation attack countermeasures (see also | ||||

Section 7). | ||||

7. Security Considerations | ||||

The different representations of elliptic curve points discussed in | The different representations of elliptic curve points discussed in | |||

this document are all obtained using a publicly known transformation, | this document are all obtained using a publicly known transformation, | |||

which is either an isomorphism or a low-degree isogeny. It is well- | which is either an isomorphism or a low-degree isogeny. It is well- | |||

known that an isomorphism maps elliptic curve points to equivalent | known that an isomorphism maps elliptic curve points to equivalent | |||

mathematical objects and that the complexity of cryptographic | mathematical objects and that the complexity of cryptographic | |||

problems (such as the discrete logarithm problem) of curves related | problems (such as the discrete logarithm problem) of curves related | |||

via a low-degree isogeny are tightly related. Thus, the use of these | via a low-degree isogeny are tightly related. Thus, the use of these | |||

techniques does not negatively impact cryptographic security of | techniques does not negatively impact cryptographic security of | |||

elliptic curve operations. | elliptic curve operations. | |||

skipping to change at page 9, line 43 ¶ | skipping to change at page 10, line 43 ¶ | |||

short-Weierstrass form and in uncompressed tight MSB/msb format). | short-Weierstrass form and in uncompressed tight MSB/msb format). | |||

To prevent cross-protocol attacks, private keys SHOULD only be used | To prevent cross-protocol attacks, private keys SHOULD only be used | |||

with one cryptographic scheme. Private keys MUST NOT be reused | with one cryptographic scheme. Private keys MUST NOT be reused | |||

between Ed25519 (as specified in [RFC8032]) and ECDSA25519 (as | between Ed25519 (as specified in [RFC8032]) and ECDSA25519 (as | |||

specified in Section 4.3). | specified in Section 4.3). | |||

To prevent intra-protocol cross-instantiation attacks, ephemeral | To prevent intra-protocol cross-instantiation attacks, ephemeral | |||

private keys MUST NOT be reused between instantiations of ECDSA25519. | private keys MUST NOT be reused between instantiations of ECDSA25519. | |||

7. Privacy Considerations | 8. Privacy Considerations | |||

The transformations between different curve models described in this | The transformations between different curve models described in this | |||

document are publicly known and, therefore, do not affect privacy | document are publicly known and, therefore, do not affect privacy | |||

provisions. | provisions. | |||

8. IANA Considerations | 9. IANA Considerations | |||

An object identifier is requested for curve Wei25519 and its use with | An object identifier is requested for curve Wei25519 and its use with | |||

ECDSA and co-factor ECDH, using the representation conventions of | ECDSA and co-factor ECDH, using the representation conventions of | |||

this document. | this document. | |||

There is *currently* no further IANA action required for this | There is *currently* no further IANA action required for this | |||

document. New object identifiers would be required in case one | document. New object identifiers would be required in case one | |||

wishes to specify one or more of the "offspring" protocols | wishes to specify one or more of the "offspring" protocols | |||

exemplified in Section 4.4. | exemplified in Section 4.4. | |||

8.1. COSE Elliptic Curves Registration | 9.1. COSE Elliptic Curves Registration | |||

This section registers the following value in the IANA "COSE Elliptic | This section registers the following value in the IANA "COSE Elliptic | |||

Curves" registry [IANA.COSE.Curves]. | Curves" registry [IANA.COSE.Curves]. | |||

Name: Wei25519; | Name: Wei25519; | |||

Value: TBD (Requested value: -1); | Value: TBD (Requested value: -1); | |||

Key Type: EC2 or OKP (where OKP uses the squeezed MSB/msb | Key Type: EC2 or OKP (where OKP uses the squeezed MSB/msb | |||

representation of this specification); | representation of this specification); | |||

Description: short-Weierstrass curve Wei25519; | Description: short-Weierstrass curve Wei25519; | |||

Reference: Appendix E.3 of this specification; | Reference: Appendix E.3 of this specification; | |||

Recommended: Yes. | Recommended: Yes. | |||

(Note that The "kty" value for Wei25519 may be "OKP" or "EC2".) | (Note that The "kty" value for Wei25519 may be "OKP" or "EC2".) | |||

8.2. COSE Algorithms Registration (1/2) | 9.2. COSE Algorithms Registration (1/2) | |||

This section registers the following value in the IANA "COSE | This section registers the following value in the IANA "COSE | |||

Algorithms" registry [IANA.COSE.Algorithms]. | Algorithms" registry [IANA.COSE.Algorithms]. | |||

Name: ECDSA25519; | Name: ECDSA25519; | |||

Value: TBD (Requested value: -1); | Value: TBD (Requested value: -1); | |||

Description: ECDSA w/ SHA-256 and curve Wei25519; | Description: ECDSA w/ SHA-256 and curve Wei25519; | |||

Reference: Section 4.3 of this specification; | Reference: Section 4.3 of this specification; | |||

Recommended: Yes. | Recommended: Yes. | |||

8.3. COSE Algorithms Registration (2/2) | 9.3. COSE Algorithms Registration (2/2) | |||

This section registers the following value in the IANA "COSE | This section registers the following value in the IANA "COSE | |||

Algorithms" registry [IANA.COSE.Algorithms]. | Algorithms" registry [IANA.COSE.Algorithms]. | |||

Name: ECDH25519; | Name: ECDH25519; | |||

Value: TBD (Requested value: -2); | Value: TBD (Requested value: -2); | |||

Description: NIST-compliant co-factor Diffie-Hellman w/ curve | Description: NIST-compliant co-factor Diffie-Hellman w/ curve | |||

Wei25519 and key derivation function HKDF SHA256; | Wei25519 and key derivation function HKDF SHA256; | |||

Reference: Section 4.1 of this specification (for key derivation, | Reference: Section 4.1 of this specification (for key derivation, | |||

see Section 11.1 of [RFC8152]); | see Section 11.1 of [RFC8152]); | |||

Recommended: Yes. | Recommended: Yes. | |||

8.4. JOSE Elliptic Curves Registration | 9.4. JOSE Elliptic Curves Registration | |||

This section registers the following value in the IANA "JSON Web Key | This section registers the following value in the IANA "JSON Web Key | |||

Elliptic Curve" registry [IANA.JOSE.Curves]. | Elliptic Curve" registry [IANA.JOSE.Curves]. | |||

Curve Name: Wei25519; | Curve Name: Wei25519; | |||

Curve Description: short-Weierstrass curve Wei25519; | Curve Description: short-Weierstrass curve Wei25519; | |||

JOSE Implementation Requirements: optional; | JOSE Implementation Requirements: optional; | |||

Change Controller: IANA; | Change Controller: IANA; | |||

Reference: Appendix E.3 of this specification. | Reference: Appendix E.3 of this specification. | |||

8.5. JOSE Algorithms Registration (1/2) | 9.5. JOSE Algorithms Registration (1/2) | |||

This section registers the following value in the IANA "JSON Web | This section registers the following value in the IANA "JSON Web | |||

Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. | Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. | |||

Algorithm Name: ECDSA25519; | Algorithm Name: ECDSA25519; | |||

Algorithm Description: ECDSA w/ SHA-256 and curve Wei25519; | Algorithm Description: ECDSA w/ SHA-256 and curve Wei25519; | |||

Algorithm Usage Locations: alg; | Algorithm Usage Locations: alg; | |||

JOSE Implementation Requirements: optional; | JOSE Implementation Requirements: optional; | |||

Change Controller: IANA; | Change Controller: IANA; | |||

Reference: Section 4.3 of this specification; | Reference: Section 4.3 of this specification; | |||

Algorithm Analysis Documents: Section 4.3 of this specification. | Algorithm Analysis Documents: Section 4.3 of this specification. | |||

8.6. JOSE Algorithms Registration (2/2) | 9.6. JOSE Algorithms Registration (2/2) | |||

This section registers the following value in the IANA "JSON Web | This section registers the following value in the IANA "JSON Web | |||

Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. | Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. | |||

Algorithm Name: ECDH25519; | Algorithm Name: ECDH25519; | |||

Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/ | Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/ | |||

curve Wei25519 and key derivation function HKDF SHA256; | curve Wei25519 and key derivation function HKDF SHA256; | |||

Algorithm Usage Locations: alg; | Algorithm Usage Locations: alg; | |||

Change Controller: IANA; | Change Controller: IANA; | |||

Reference: Section 4.1 of this specification (for key derivation, | Reference: Section 4.1 of this specification (for key derivation, | |||

see Section 5 of [SP-800-56c]); | see Section 5 of [SP-800-56c]); | |||

Algorithm Analysis Documents: Section 4.1 of this specification (for | Algorithm Analysis Documents: Section 4.1 of this specification (for | |||

key derivation, see Section 5 of [SP-800-56c]). | key derivation, see Section 5 of [SP-800-56c]). | |||

9. Acknowledgements | 10. Acknowledgements | |||

Thanks to Nikolas Rosener for discussions surrounding implementation | Thanks to Nikolas Rosener for discussions surrounding implementation | |||

details of the techniques described in this document and to Phillip | details of the techniques described in this document and to Phillip | |||

Hallam-Baker for triggering inclusion of verbiage on the use of | Hallam-Baker for triggering inclusion of verbiage on the use of | |||

Montgomery ladders with recovery of the y-coordinate. Thanks to | Montgomery ladders with recovery of the y-coordinate. Thanks to | |||

Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews. | Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews. | |||

10. References | 11. References | |||

10.1. Normative References | 11.1. Normative References | |||

[ANSI-X9.62] | [ANSI-X9.62] | |||

ANSI X9.62-2005, "Public Key Cryptography for the | ANSI X9.62-2005, "Public Key Cryptography for the | |||

Financial Services Industry: The Elliptic Curve Digital | Financial Services Industry: The Elliptic Curve Digital | |||

Signature Algorithm (ECDSA)", American National Standard | Signature Algorithm (ECDSA)", American National Standard | |||

for Financial Services, Accredited Standards Committee X9, | for Financial Services, Accredited Standards Committee X9, | |||

Inc, Anapolis, MD, 2005. | Inc, Anapolis, MD, 2005. | |||

[FIPS-186-4] | [FIPS-186-4] | |||

FIPS 186-4, "Digital Signature Standard (DSS), Federal | FIPS 186-4, "Digital Signature Standard (DSS), Federal | |||

skipping to change at page 13, line 48 ¶ | skipping to change at page 14, line 48 ¶ | |||

Establishment Schemes Using Discrete Log Cryptography, | Establishment Schemes Using Discrete Log Cryptography, | |||

Revision 3", US Department of Commerce/National Institute | Revision 3", US Department of Commerce/National Institute | |||

of Standards and Technology, Gaithersburg, MD, April 2018. | of Standards and Technology, Gaithersburg, MD, April 2018. | |||

[SP-800-56c] | [SP-800-56c] | |||

NIST SP 800-56c, "Recommendation for Key-Derivation | NIST SP 800-56c, "Recommendation for Key-Derivation | |||

Methods in Key-Establishment Schemes, Revision 1", US | Methods in Key-Establishment Schemes, Revision 1", US | |||

Department of Commerce/National Institute of Standards and | Department of Commerce/National Institute of Standards and | |||

Technology, Gaithersburg, MD, April 2018. | Technology, Gaithersburg, MD, April 2018. | |||

10.2. Informative References | 11.2. Informative References | |||

[ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in | [ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in | |||

Cryptography", Cambridge University Press, Lecture Notes | Cryptography", Cambridge University Press, Lecture Notes | |||

Series 265, July 1999. | Series 265, July 1999. | |||

[ECC-Isogeny] | [ECC-Isogeny] | |||

E. Brier, M. Joye, "Fast Point Multiplication on Elliptic | E. Brier, M. Joye, "Fast Point Multiplication on Elliptic | |||

Curves through Isogenies", AAECC, Lecture Notes in | Curves through Isogenies", AAECC, Lecture Notes in | |||

Computer Science, Vol. 2643, New York: Springer-Verlag, | Computer Science, Vol. 2643, New York: Springer-Verlag, | |||

2003. | 2003. | |||

skipping to change at page 14, line 40 ¶ | skipping to change at page 15, line 40 ¶ | |||

IANA, "JSON Web Signature and Encryption Algorithms", | IANA, "JSON Web Signature and Encryption Algorithms", | |||

IANA, | IANA, | |||

https://www.iana.org/assignments/jose/jose.xhtml#web- | https://www.iana.org/assignments/jose/jose.xhtml#web- | |||

signature-encryption-algorithms. | signature-encryption-algorithms. | |||

[IANA.JOSE.Curves] | [IANA.JOSE.Curves] | |||

IANA, "JSON Web Key Elliptic Curve", IANA, | IANA, "JSON Web Key Elliptic Curve", IANA, | |||

https://www.iana.org/assignments/jose/jose.xhtml#web-key- | https://www.iana.org/assignments/jose/jose.xhtml#web-key- | |||

elliptic-curve. | elliptic-curve. | |||

[Ladder] P.L. Montgomery, "Speeding the Pollard and Elliptic Curve | [Mont-Ladder] | |||

P.L. Montgomery, "Speeding the Pollard and Elliptic Curve | ||||

Methods of Factorization", Mathematics of | Methods of Factorization", Mathematics of | |||

Computation, Vol. 48, 1987. | Computation, Vol. 48, 1987. | |||

[tEd] D.J. Bernstein, P. Birkner, M. Joye, T. Lange, C. Peters, | [tEd] D.J. Bernstein, P. Birkner, M. Joye, T. Lange, C. Peters, | |||

"Twisted Edwards Curves", Africacrypt 2008, Lecture Notes | "Twisted Edwards Curves", Africacrypt 2008, Lecture Notes | |||

in Computer Science, Vol. 5023, New York: Springer-Verlag, | in Computer Science, Vol. 5023, New York: Springer-Verlag, | |||

2008. | 2008. | |||

[tEd-Formulas] | [tEd-Formulas] | |||

H. Hisil, K.K.H. Wong, G. Carter, E. Dawson, "Twisted | H. Hisil, K.K.H. Wong, G. Carter, E. Dawson, "Twisted | |||

Edwards Curves Revisited", ASIACRYPT 2008, Lecture Notes | Edwards Curves Revisited", ASIACRYPT 2008, Lecture Notes | |||

in Computer Science, Vol. 5350, New York: Springer-Verlag, | in Computer Science, Vol. 5350, New York: Springer-Verlag, | |||

2008. | 2008. | |||

[Wei-y-recovery] | [Wei-Ladder] | |||

T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve | T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve | |||

Multiplication Resistant Against Side Channel Attacks", | Multiplication Resistant Against Side Channel Attacks", | |||

Centre for Applied Cryptographic Research, Corr 2002-03, | Centre for Applied Cryptographic Research, Corr 2002-03, | |||

2002. | 2002. | |||

Appendix A. Some (non-Binary) Elliptic Curves | Appendix A. Some (non-Binary) Elliptic Curves | |||

A.1. Curves in short-Weierstrass Form | A.1. Curves in short-Weierstrass Form | |||

Let GF(q) denote the finite field with q elements, where q is an odd | Let GF(q) denote the finite field with q elements, where q is an odd | |||

skipping to change at page 28, line 42 ¶ | skipping to change at page 29, line 42 ¶ | |||

other point (u',v') of M_{A',B'} to the point (u,v):=(-u',v') of | other point (u',v') of M_{A',B'} to the point (u,v):=(-u',v') of | |||

M_{A,B}. | M_{A,B}. | |||

Implementations may take advantage of this mapping to carry out | Implementations may take advantage of this mapping to carry out | |||

elliptic curve groups operations originally defined for a Montgomery | elliptic curve groups operations originally defined for a Montgomery | |||

curve with generic domain parameters A and B on a corresponding | curve with generic domain parameters A and B on a corresponding | |||

isomorphic Montgomery curve with domain parameters A' and B' that | isomorphic Montgomery curve with domain parameters A' and B' that | |||

have a more special form, which is known to allow for more efficient | have a more special form, which is known to allow for more efficient | |||

implementations of addition laws. In particular, it is known that | implementations of addition laws. In particular, it is known that | |||

such efficiency improvements exist if B' assumes a small absolute | such efficiency improvements exist if B' assumes a small absolute | |||

value, such as B':=(+/-)1. (see [Ladder]). | value, such as B':=(+/-)1. (see [Mont-Ladder]). | |||

F.3. Isomorphic Mapping between Weierstrass Curves | F.3. Isomorphic Mapping between Weierstrass Curves | |||

One can map points of the Weierstrass curve W_{a,b} to points of the | One can map points of the Weierstrass curve W_{a,b} to points of the | |||

Weierstrass curve W_{a',b'}, where a':=a*s^4 and b':=b*s^6 for some | Weierstrass curve W_{a',b'}, where a':=a*s^4 and b':=b*s^6 for some | |||

nonzero element s of GF(q). This defines a one-to-one | nonzero element s of GF(q). This defines a one-to-one | |||

correspondence, which - in fact - is an isomorphism between W_{a,b} | correspondence, which - in fact - is an isomorphism between W_{a,b} | |||

and W_{a',b'}. | and W_{a',b'}. | |||

The mapping from W_{a,b} to W_{a',b'} is defined by mapping the point | The mapping from W_{a,b} to W_{a',b'} is defined by mapping the point | |||

End of changes. 26 change blocks. | ||||

94 lines changed or deleted | | 139 lines changed or added | ||

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