draft-ietf-lwig-curve-representations-11.txt | draft-ietf-lwig-curve-representations-12.txt | |||
---|---|---|---|---|

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

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

Intended status: Informational July 13, 2020 | Intended status: Informational August 24, 2020 | |||

Expires: January 14, 2021 | Expires: February 25, 2021 | |||

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

draft-ietf-lwig-curve-representations-11 | draft-ietf-lwig-curve-representations-12 | |||

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. We also provide extensive background | using NIST prime curves. We also provide extensive background | |||

material that may be useful for implementers of elliptic curve | material that may be useful for implementers of elliptic curve | |||

cryptography. | cryptography. | |||

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

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 January 14, 2021. | This Internet-Draft will expire on February 25, 2021. | |||

Copyright Notice | Copyright Notice | |||

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

carefully, as they describe your rights and restrictions with respect | carefully, as they describe your rights and restrictions with respect | |||

to this document. Code Components extracted from this document must | to this document. Code Components extracted from this document must | |||

include Simplified BSD License text as described in Section 4.e of | include Simplified BSD License text as described in Section 4.e of | |||

the Trust Legal Provisions and are provided without warranty as | the Trust Legal Provisions and are provided without warranty as | |||

described in the Simplified BSD License. | described in the Simplified BSD License. | |||

Table of Contents | Table of Contents | |||

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

2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 5 | 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 6 | |||

3. Use of Representation Switches . . . . . . . . . . . . . . . 6 | 3. Use of Representation Switches . . . . . . . . . . . . . . . 6 | |||

4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7 | 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7 | |||

4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 7 | 4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 7 | |||

4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 7 | 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 8 | |||

4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 8 | 4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 8 | |||

4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 8 | 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 9 | |||

5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 | 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 | |||

5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 9 | 5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 10 | |||

5.2. Representation Conventions . . . . . . . . . . . . . . . 9 | 5.2. Representation Conventions . . . . . . . . . . . . . . . 10 | |||

5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 10 | 5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 10 | |||

6. Implementation Considerations . . . . . . . . . . . . . . . . 11 | 6. Implementation Considerations . . . . . . . . . . . . . . . . 11 | |||

7. Implementation Status . . . . . . . . . . . . . . . . . . . . 12 | 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 12 | |||

8. Security Considerations . . . . . . . . . . . . . . . . . . . 13 | 8. Security Considerations . . . . . . . . . . . . . . . . . . . 13 | |||

9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 13 | 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 14 | |||

10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 14 | 10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 14 | |||

10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 14 | 10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 14 | |||

10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 14 | 10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 15 | |||

10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 15 | 10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 16 | |||

10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 16 | 10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 16 | |||

10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 17 | 10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 17 | |||

10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 18 | 10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 18 | |||

10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 18 | 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 19 | |||

10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 19 | 10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 20 | |||

10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 20 | 10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 20 | |||

11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 | 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 | |||

11.1. IANA Considerations for Wei25519 . . . . . . . . . . . . 20 | 11.1. IANA Considerations for Wei25519 . . . . . . . . . . . . 21 | |||

11.1.1. COSE Elliptic Curves Registration . . . . . . . . . 20 | 11.1.1. COSE Elliptic Curves Registration . . . . . . . . . 21 | |||

11.1.2. COSE Algorithms Registration (1/2) . . . . . . . . . 21 | 11.1.2. COSE Algorithms Registration (1/2) . . . . . . . . . 21 | |||

11.1.3. COSE Algorithms Registration (2/2) . . . . . . . . . 21 | 11.1.3. COSE Algorithms Registration (2/2) . . . . . . . . . 21 | |||

11.1.4. JOSE Elliptic Curves Registration . . . . . . . . . 22 | 11.1.4. JOSE Elliptic Curves Registration . . . . . . . . . 22 | |||

11.1.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 22 | 11.1.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 22 | |||

11.1.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 22 | 11.1.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 23 | |||

11.2. IANA Considerations for Wei448 . . . . . . . . . . . . . 23 | 11.2. IANA Considerations for Wei448 . . . . . . . . . . . . . 23 | |||

11.2.1. COSE Elliptic Curves Registration . . . . . . . . . 23 | 11.2.1. COSE Elliptic Curves Registration . . . . . . . . . 23 | |||

11.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 23 | 11.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 24 | |||

11.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 24 | 11.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 24 | |||

11.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 24 | 11.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 24 | |||

11.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 24 | 11.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 25 | |||

11.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 25 | 11.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 25 | |||

12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 25 | 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 26 | |||

13. References . . . . . . . . . . . . . . . . . . . . . . . . . 26 | 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 26 | |||

13.1. Normative References . . . . . . . . . . . . . . . . . . 26 | 13.1. Normative References . . . . . . . . . . . . . . . . . . 26 | |||

13.2. Informative References . . . . . . . . . . . . . . . . . 28 | 13.2. Informative References . . . . . . . . . . . . . . . . . 28 | |||

Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 30 | Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 30 | |||

A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 30 | A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 30 | |||

A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 30 | A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 30 | |||

A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 30 | A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 30 | |||

Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 31 | Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 31 | |||

B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 31 | B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 31 | |||

B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 33 | B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 33 | |||

skipping to change at page 5, line 30 ¶ | skipping to change at page 5, line 30 ¶ | |||

P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 118 | P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 118 | |||

P.3. Conversion to Integers in Z_n via the Discard Method . . 119 | P.3. Conversion to Integers in Z_n via the Discard Method . . 119 | |||

Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 119 | Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 119 | |||

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

Elliptic curves can be represented using different curve models. | Elliptic curves can be represented using different curve models. | |||

Recently, IETF standardized elliptic curves that are claimed to have | Recently, IETF standardized elliptic curves that are claimed to have | |||

better performance and improved robustness against "real world" | better performance and improved robustness against "real world" | |||

attacks than curves represented in the traditional "short" | attacks than curves represented in the traditional "short" | |||

Weierstrass model. This document specifies an alternative | Weierstrass curve model. These so-called CFRG curves [RFC7748] use | |||

representation of points of Curve25519, a so-called Montgomery curve, | the Montgomery curve model and the model of twisted Edwards curves. | |||

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

which are both specified in [RFC7748], as points of a specific so- | ||||

called "short" Weierstrass curve, called Wei25519. We also define | ||||

how to efficiently switch between these different representations. | ||||

Use of Wei25519 allows easy definition of new instantiations of | In this document, we specify these curves using the traditional | |||

signature schemes and key agreement schemes already specified for | "short" Weierstrass model and also define how to efficiently switch | |||

traditional NIST prime curves, thereby allowing easy integration with | between representations in these different curve models. In | |||

existing specifications, such as NIST SP 800-56a [SP-800-56a], FIPS | particular, we specify Wei25519, which allows an alternative | |||

Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005 [ANSI-X9.62], and | representation of points of Curve25519 (a Montgomery curve) and of | |||

fostering code reuse on platforms that already implement some of | points of Edwards25519 (a twisted Edwards curve), as points of a | |||

these schemes using elliptic curve arithmetic for curves in "short" | corresponding "short" Weierstrass curve. Similarly, we specify | |||

Weierstrass form (see Appendix C.1). | Wei448, which allows an alternative representation of points of | |||

Curve448 (a Montgomery curve) and of points of Ed448 (an Edwards | ||||

curve), as points of a corresponding "short" Weierstrass curve. | ||||

Use of Wei25519 and Wei448 allows easy definition of new | ||||

instantiations of signature schemes and key agreement schemes already | ||||

specified for traditional NIST prime curves, thereby allowing easy | ||||

integration with existing specifications, such as NIST SP 800-56a | ||||

[SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005 | ||||

[ANSI-X9.62], and fostering code reuse on platforms that already | ||||

implement some of these schemes using elliptic curve arithmetic for | ||||

curves in "short" Weierstrass form (see Appendix C.1). To illustrate | ||||

this, we specify how to use Wei25519 and Wei448 with co-factor ECDH | ||||

and with ECDSA, thereby giving rise to the key agreement schemes | ||||

ECDH25519 and ECDH448 and the signature schemes ECDSA25519 and | ||||

ECDSA448. In all these cases, implementors may use the curve | ||||

arithmetic for the curve model of their choosing (where they can | ||||

efficiently switch between representations in different curve models, | ||||

if required). | ||||

For ease of exposition, we consider Wei25519 first and introduce | ||||

Wei448 simply as an illustration of how to create other "offspring" | ||||

objects and protocols (see Section 4.4). We also provide extensive | ||||

background material that we hope may be useful for implementors of | ||||

elliptic curve cryptography or for cross-referencing with future | ||||

specification work. | ||||

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

For the specification of Wei25519 and its relationship to Curve25519 | For the specification of Wei25519 and its relationship to Curve25519 | |||

and Edwards25519, see Appendix E. For further details and background | and Edwards25519, see Appendix E. For further details and background | |||

information on elliptic curves, we refer to the other appendices. | information on elliptic curves, we refer to the other appendices. | |||

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

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

also implement the CFRG curves Curve25519 and Edwards25519. (Here, | also implement the CFRG curves Curve25519 and Edwards25519. (Here, | |||

skipping to change at page 8, line 26 ¶ | skipping to change at page 8, line 46 ¶ | |||

criteria). In particular, one can instantiate this scheme with the | criteria). In particular, one can instantiate this scheme with the | |||

Weierstrass curve Wei25519 and the hash function SHA-256 | Weierstrass curve Wei25519 and the hash function SHA-256 | |||

[FIPS-180-4], where an implementation may generate an ephemeral | [FIPS-180-4], where an implementation may generate an ephemeral | |||

public-private key pair for Wei25519 by (1) internally carrying out | public-private key pair for Wei25519 by (1) internally carrying out | |||

these computations on the Montgomery curve Curve25519, the twisted | these computations on the Montgomery curve Curve25519, the twisted | |||

Edwards curve Edwards25519, or even the Weierstrass curve Wei25519.-3 | Edwards curve Edwards25519, or even the Weierstrass curve Wei25519.-3 | |||

(with hardcoded a=-3 domain parameter); (2) representing the result | (with hardcoded a=-3 domain parameter); (2) representing the result | |||

as a key pair for the curve Wei25519. Note that, in either case, one | as a key pair for the curve Wei25519. Note that, in either case, one | |||

can implement these schemes with the same representation conventions | can implement these schemes with the same representation conventions | |||

as used with existing NIST specifications, including bit/byte- | as used with existing NIST specifications, including bit/byte- | |||

ordering, compression functions, and the-like. This allows generic | ordering, compression functions, and the like. This allows generic | |||

implementations of ECDSA with the hash function SHA-256 and with the | implementations of ECDSA with the hash function SHA-256 and with the | |||

NIST curve P-256 or with the curve Wei25519 specified in this | NIST curve P-256 or with the curve Wei25519 specified in this | |||

specification to reuse the same implementation (instantiated with, | specification to reuse the same implementation (instantiated with, | |||

respectively, the NIST P-256 elliptic curve domain parameters or with | respectively, the NIST P-256 elliptic curve domain parameters or with | |||

the domain parameters of curve Wei25519 specified in Appendix E). We | the domain parameters of curve Wei25519 specified in Appendix E). We | |||

denote by ECDSA25519 the instantiation of ECDSA with SHA-256 and with | denote by ECDSA25519 the instantiation of ECDSA with SHA-256 and with | |||

curve Wei25519, where the signature (r,s) is represented as the | curve Wei25519, where the signature (r,s) is represented as the | |||

right-concatenation of the integers r and s, each represented as | right-concatenation of the integers r and s, each represented as | |||

fixed-size strings with tight MSB/msb ordering (see Appendix I). | fixed-size strings with tight MSB/msb ordering (see Appendix I). | |||

skipping to change at page 8, line 49 ¶ | skipping to change at page 9, line 21 ¶ | |||

Any existing specification of cryptographic schemes using elliptic | Any existing specification of cryptographic schemes using elliptic | |||

curves in Weierstrass form and that allows introduction of a new | curves in Weierstrass form and that allows introduction of a new | |||

elliptic curve (here: Wei25519) is amenable to similar constructs, | elliptic curve (here: Wei25519) is amenable to similar constructs, | |||

thus spawning "offspring" protocols, simply by instantiating these | thus spawning "offspring" protocols, simply by instantiating these | |||

using the new curve in "short" Weierstrass form, thereby allowing | using the new curve in "short" Weierstrass form, thereby allowing | |||

code and/or specifications reuse and, for implementations that so | code and/or specifications reuse and, for implementations that so | |||

desire, carrying out curve computations "under the hood" on | desire, carrying out curve computations "under the hood" on | |||

Montgomery curve and twisted Edwards curve cousins hereof (where | Montgomery curve and twisted Edwards curve cousins hereof (where | |||

these exist). This would simply require definition of a new object | these exist). This would simply require definition of a new object | |||

identifier for any such envisioned "offspring" protocol. This could | identifier for any such envisioned "offspring" protocol. This could | |||

significantly simplify standardization of schemes and help keeping | significantly simplify standardization of schemes and help keeping at | |||

the resource and maintenance cost of implementations supporting | bay the resource and maintenance cost of implementations supporting | |||

algorithm agility [RFC7696] at bay. | algorithm agility [RFC7696]. | |||

We illustrate the construction of such offspring protocols for | We illustrate the construction of such offspring protocols for | |||

Curve448, another Montgomery curve recently standardized by IETF (see | Curve448, another Montgomery curve recently standardized by IETF (see | |||

[RFC7748]). Similar to the case with Curve25519, one can represent | [RFC7748]). Similar to the case with Curve25519, one can represent | |||

points of this curve via different curve models, viz. as points of an | points of this curve via different curve models, viz. as points of an | |||

Edwards curve (Ed448) or as points of a short-Weierstrass curve | Edwards curve (Ed448) or as points of a short-Weierstrass curve | |||

(Wei448). For the specification of Wei448 and its relationship to | (Wei448). For the specification of Wei448 and its relationship to | |||

Curve448 and Ed448, see Appendix M. As with ECDH25519, one can now | Curve448 and Ed448, see Appendix M. As with ECDH25519, one can now | |||

easily define a NIST-compliant version of co-factor Diffie-Hellman | easily define a NIST-compliant version of co-factor Diffie-Hellman | |||

key agreement (denoted by ECDH448), by simply reusing the example of | key agreement (denoted by ECDH448), by simply reusing the example of | |||

skipping to change at page 10, line 17 ¶ | skipping to change at page 10, line 42 ¶ | |||

5.3. Domain Parameters | 5.3. Domain Parameters | |||

All traditional NIST curves are Weierstrass curves with domain | All traditional NIST curves are Weierstrass curves with domain | |||

parameter a=-3, while all Brainpool curves [RFC5639] are isomorphic | parameter a=-3, while all Brainpool curves [RFC5639] are isomorphic | |||

to a Weierstrass curve of this form. Thus, one can expect there to | to a Weierstrass curve of this form. Thus, one can expect there to | |||

be existing Weierstrass implementations with a hardcoded a=-3 domain | be existing Weierstrass implementations with a hardcoded a=-3 domain | |||

parameter ("Jacobian-friendly"). For those implementations, | parameter ("Jacobian-friendly"). For those implementations, | |||

including the curve Wei25519 as a potential vehicle for offering | including the curve Wei25519 as a potential vehicle for offering | |||

support for the CFRG curves Curve25519 and Edwards25519 is not | support for the CFRG curves Curve25519 and Edwards25519 is not | |||

possible, since not of the required form. Instead, one has to | possible, since it is not of the required form. Instead, one has to | |||

implement Wei25519.-3 and include code that implements the isogeny | implement Wei25519.-3 and include code that implements the isogeny | |||

and dual isogeny from and to Wei25519. The lowest odd-degree isogeny | and dual isogeny from and to Wei25519. The lowest odd-degree isogeny | |||

has degree l=47 and requires roughly 9kB of storage for isogeny and | has degree l=47 and requires roughly 9kB of storage for isogeny and | |||

dual-isogeny computations (see the tables in Appendix G.4). Note | dual-isogeny computations (see the tables in Appendix G.4). Note | |||

that storage would have reduced to a single 64-byte table if only the | that storage would have reduced to a single 64-byte table if only the | |||

Curve25519 curve would have been generated so as to be isomorphic to | Curve25519 curve would have been generated so as to be isomorphic to | |||

a Weierstrass curve with hardcoded a=-3 parameter (this corresponds | a Weierstrass curve with hardcoded a=-3 parameter (this corresponds | |||

to l=1). | to l=1). | |||

NOTE 1: An example of a Montgomery curve defined over the same field | NOTE 1: An example of a Montgomery curve defined over the same field | |||

skipping to change at page 17, line 11 ¶ | skipping to change at page 17, line 28 ¶ | |||

All inputs and outputs are uniquely determined by specifying the | All inputs and outputs are uniquely determined by specifying the | |||

encodings of the message m, the private key d, the public key Q, the | encodings of the message m, the private key d, the public key Q, the | |||

signature, and the values "valid" and "invalid". | signature, and the values "valid" and "invalid". | |||

The encodings below specify the use of instantiations of ECDSA with | The encodings below specify the use of instantiations of ECDSA with | |||

COSE (see Section 10.2.1) and JOSE (see Section 10.2.2), where the | COSE (see Section 10.2.1) and JOSE (see Section 10.2.2), where the | |||

encoding for a specific ECDSA instantiation (i.e., with a specific | encoding for a specific ECDSA instantiation (i.e., with a specific | |||

short-Weierstrass curve and specific hash function) results by | short-Weierstrass curve and specific hash function) results by | |||

setting the "crv" parameter to the unique name of the underlying | setting the "crv" parameter to the unique name of the underlying | |||

curve in question and the "alg" parameter to the unique name of the | curve in question and the "alg" parameter to the unique name of the | |||

specific signature scheme scheme instantiation (e.g., "ECDSA25519" | specific signature scheme instantiation (e.g., "ECDSA25519" for the | |||

for the ECDSA scheme defined in Section 4.3 and "ECDSA448" for the | ECDSA scheme defined in Section 4.3 and "ECDSA448" for the scheme | |||

scheme defined in Section 4.4). Note that, in this case, the "alg" | defined in Section 4.4). Note that, in this case, the "alg" name | |||

name uniquely defines the curve (and, thereby, implicitly the | uniquely defines the curve (and, thereby, implicitly the underlying | |||

underlying "crv" parameter) and the underlying hash function. | "crv" parameter) and the underlying hash function. | |||

10.2.1. Encoding of ECDSA Instantiations with COSE | 10.2.1. Encoding of ECDSA Instantiations with COSE | |||

Instantiations of ECDSA used with COSE use the following encodings of | Instantiations of ECDSA used with COSE use the following encodings of | |||

inputs and outputs: | inputs and outputs: | |||

a. The message m is the COSE_Sign structure as specified in | a. The message m is the COSE_Sign structure as specified in | |||

Section 4.1 of [RFC8152], converted to a bit-string, using the | Section 4.1 of [RFC8152], converted to a bit-string, using the | |||

OS2BS mapping of Appendix I.4; | OS2BS mapping of Appendix I.4; | |||

skipping to change at page 20, line 32 ¶ | skipping to change at page 20, line 47 ¶ | |||

private key. | private key. | |||

11. IANA Considerations | 11. IANA Considerations | |||

Code points are requested for curves Wei25519 and Wei448 and their | Code points are requested for curves Wei25519 and Wei448 and their | |||

use with ECDSA and co-factor ECDH, using the representation | use with ECDSA and co-factor ECDH, using the representation | |||

conventions of this document. | conventions of this document. | |||

New code points would be required in case one wishes to specify one | New code points would be required in case one wishes to specify one | |||

or more other "offspring" protocols beyond those exemplified in | or more other "offspring" protocols beyond those exemplified in | |||

Section 4.4. Specification hereof is, however, outside scope of the | Section 4.4. Specification hereof is, however, outside the scope of | |||

current document. | the current document. | |||

11.1. IANA Considerations for Wei25519 | 11.1. IANA Considerations for Wei25519 | |||

11.1.1. COSE Elliptic Curves Registration | 11.1.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; | |||

skipping to change at page 33, line 31 ¶ | skipping to change at page 33, line 31 ¶ | |||

multiplication modulo the irreducible polynomial f(z). By | multiplication modulo the irreducible polynomial f(z). By | |||

definition, each element x of GF(q) is a polynomial in z of degree | definition, each element x of GF(q) is a polynomial in z of degree | |||

smaller than m and can, therefore, be uniquely represented as a | smaller than m and can, therefore, be uniquely represented as a | |||

vector (x_{m-1}, x_{m-2}, ..., x_1, x_0) of length m with | vector (x_{m-1}, x_{m-2}, ..., x_1, x_0) of length m with | |||

coefficients in GF(p), where x_i is the coefficient of z^i of | coefficients in GF(p), where x_i is the coefficient of z^i of | |||

polynomial x. Note that this representation depends on the | polynomial x. Note that this representation depends on the | |||

irreducible polynomial f(z) of the field GF(p^m) in question (which | irreducible polynomial f(z) of the field GF(p^m) in question (which | |||

is often fixed in practice). Note that GF(q) contains the prime | is often fixed in practice). Note that GF(q) contains the prime | |||

field GF(p) as a subset. If m=1, the definitions of GF(p) and | field GF(p) as a subset. If m=1, the definitions of GF(p) and | |||

GF(p^1) above coincide, since each nonzero element of GF(p) can be | GF(p^1) above coincide, since each nonzero element of GF(p) can be | |||

viewed as a polynomial in z of degree zero. If m>1, then GF(q) is | viewed as a polynomial in z of degree zero. If m>1 (i.e., if if q is | |||

called a (nontrivial) extension field of GF(p). The number p is | a strict prime power), then GF(q) is called a (nontrivial) extension | |||

called the characteristic of GF(q). | field of GF(p). The number p is called the characteristic of GF(q). | |||

A field element y is called a square in GF(q) if it can be expressed | A field element y is called a square in GF(q) if it can be expressed | |||

as y:=x^2 for some x in GF(q); it is called a non-square in GF(q) | as y:=x^2 for some x in GF(q); it is called a non-square in GF(q) | |||

otherwise. If y is a square in GF(q), we denote by sqrt(y) one of | otherwise. If y is a square in GF(q), we denote by sqrt(y) one of | |||

its square roots (the other one being -sqrt(y)). For methods for | its square roots (the other one being -sqrt(y)). For methods for | |||

computing square roots and inverses in GF(q) - if these exist - see | computing square roots and inverses in GF(q) - if these exist - see | |||

Appendix K.1 and Appendix K.2, respectively. For methods for mapping | Appendix K.1 and Appendix K.2, respectively. For methods for mapping | |||

a nonzero field element that is not a square in GF(q) to a point of a | a nonzero field element that is not a square in GF(q) to a point of a | |||

curve, see Appendix K.3 (or see Appendix K.4, if one wishes to always | curve, see Appendix K.3 (or see Appendix K.4, if one wishes to always | |||

obtain a high-order point of the curve in question). | obtain a high-order point of the curve in question). | |||

skipping to change at page 46, line 18 ¶ | skipping to change at page 46, line 18 ¶ | |||

(X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of W_{a,b}, where -- | (X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of W_{a,b}, where -- | |||

again -- u'(X'), v'(X'), and w'(X') are polynomials in X' that depend | again -- u'(X'), v'(X'), and w'(X') are polynomials in X' that depend | |||

on the isogeny in question. These mappings have the property that | on the isogeny in question. These mappings have the property that | |||

their composition is not the identity mapping (as was the case with | their composition is not the identity mapping (as was the case with | |||

the isomorphic mappings discussed in Appendix F.3), but rather a | the isomorphic mappings discussed in Appendix F.3), but rather a | |||

fixed multiple hereof: if this multiple is l then the isogeny is | fixed multiple hereof: if this multiple is l then the isogeny is | |||

called an isogeny of degree l (or l-isogeny) and u, v, and w (and, | called an isogeny of degree l (or l-isogeny) and u, v, and w (and, | |||

similarly, u', v', and w') are polynomials of degrees l, 3*(l-1)/2, | similarly, u', v', and w') are polynomials of degrees l, 3*(l-1)/2, | |||

and (l-1)/2, respectively. Note that an isomorphism is simply an | and (l-1)/2, respectively. Note that an isomorphism is simply an | |||

isogeny of degree l=1. Details of how to determine isogenies are out | isogeny of degree l=1. Details of how to determine isogenies are out | |||

of scope of this document. The above formulas assume that the | of the scope of this document. The above formulas assume that the | |||

isogeny has odd degree (i.e., l is odd); detailed formulas for even- | isogeny has odd degree (i.e., l is odd); detailed formulas for even- | |||

degree isogenies are similar, but out of scope. | degree isogenies are similar, but out of scope. | |||

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

elliptic curve group operations originally defined for a Weierstrass | elliptic curve group operations originally defined for a Weierstrass | |||

curve with a generic domain parameter a on a corresponding isogenous | curve with a generic domain parameter a on a corresponding isogenous | |||

Weierstrass curve with domain parameter a'=-3 (mod p), where one can | Weierstrass curve with domain parameter a'=-3 (mod p), where one can | |||

use so-called Jacobian coordinates with a particular projective | use so-called Jacobian coordinates with a particular projective | |||

version of the addition laws of Appendix C.1. Since all traditional | version of the addition laws of Appendix C.1. Since all traditional | |||

NIST curves have domain parameter a=-3, while all Brainpool curves | NIST curves have domain parameter a=-3, while all Brainpool curves | |||

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

38d80c77 985f0329) | 38d80c77 985f0329) | |||

G.4. Isogeny Details | G.4. Isogeny Details | |||

The isogeny and dual isogeny are both isogenies with degree l=47. | The isogeny and dual isogeny are both isogenies with degree l=47. | |||

Both are specified by a triple of polynomials u, v, and w (resp. u', | Both are specified by a triple of polynomials u, v, and w (resp. u', | |||

v', and w') of degree 47, 69, and 23, respectively, with coefficients | v', and w') of degree 47, 69, and 23, respectively, with coefficients | |||

in GF(p). The coeffients of each of these polynomials are specified | in GF(p). The coeffients of each of these polynomials are specified | |||

in Appendix G.4.1 (for the isogeny) and in Appendix G.4.2 (for the | in Appendix G.4.1 (for the isogeny) and in Appendix G.4.2 (for the | |||

dual isogeny). For each polynomial in variable x, the coefficients | dual isogeny). For each polynomial in variable x, the coefficients | |||

are tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in | are tabulated as the sequence of coefficients of x^0, x^1, x^2, ..., | |||

hexadecimal format. | in hexadecimal format. | |||

G.4.1. Isogeny Parameters | G.4.1. Isogeny Parameters | |||

G.4.1.1. Coefficients of u(x) | G.4.1.1. Coefficients of u(x) | |||

0 0x670ed14828b6f1791ceb3a9cc0edfe127dee8729c5a72ddf77bb1abaebbba1e8 | 0 0x670ed14828b6f1791ceb3a9cc0edfe127dee8729c5a72ddf77bb1abaebbba1e8 | |||

1 0x1135ca8bd5383cb3545402c8bce2ced14b45c29b241e4751b035f27524a9f932 | 1 0x1135ca8bd5383cb3545402c8bce2ced14b45c29b241e4751b035f27524a9f932 | |||

2 0x3223806ff5f669c430efd74df8389f058d180e2fcffa5cdef3eacecdd2c34771 | 2 0x3223806ff5f669c430efd74df8389f058d180e2fcffa5cdef3eacecdd2c34771 | |||

skipping to change at page 68, line 14 ¶ | skipping to change at page 68, line 14 ¶ | |||

mapping is called strict if it operates as the OS2ZnE(X,l) function, | mapping is called strict if it operates as the OS2ZnE(X,l) function, | |||

except that it fails whenever it would require at least one modular | except that it fails whenever it would require at least one modular | |||

reduction. Notice that the tight ZnE2OS mapping followed by the | reduction. Notice that the tight ZnE2OS mapping followed by the | |||

strict OS2ZnE mapping is the identity map (and, hence, ZnE2OS never | strict OS2ZnE mapping is the identity map (and, hence, ZnE2OS never | |||

fails in this case). | fails in this case). | |||

Note that if n is a prime number p, the conversions ZnE2OS and FE2OS | Note that if n is a prime number p, the conversions ZnE2OS and FE2OS | |||

are consistent, as are OS2ZnE and OS2FE. This is, however, no longer | are consistent, as are OS2ZnE and OS2FE. This is, however, no longer | |||

the case if n is a strict prime power. | the case if n is a strict prime power. | |||

The conversion rules for composite n values may be useful, e.g., when | The conversion rules for composite (i.e., non-prime) n values may be | |||

encoding RSA parameters (or elements of any other non-prime size set | useful, e.g., when encoding RSA parameters (or elements of any other | |||

Z_n, for that matter). | non-prime size set Z_n, for that matter). | |||

I.7. Ordering Conventions | I.7. Ordering Conventions | |||

One can consider various representation functions, depending on bit- | One can consider various representation functions, depending on bit- | |||

ordering and octet-ordering conventions. | ordering and octet-ordering conventions. | |||

The description below makes use of an auxiliary function (the | The description below makes use of an auxiliary function (the | |||

reversion function), where the reverse of the string X:=str(x_{l-1}, | reversion function), where the reverse of the string X:=str(x_{l-1}, | |||

x_{l-2}, ..., x_1, x_0) is defined to be the string | x_{l-2}, ..., x_1, x_0) is defined to be the string | |||

X':=rev(X):=str(x_0, x_1, ..., x_{l-2}, x_{l-1}). Below, we use this | X':=rev(X):=str(x_0, x_1, ..., x_{l-2}, x_{l-1}). Below, we use this | |||

skipping to change at page 70, line 28 ¶ | skipping to change at page 70, line 28 ¶ | |||

coordinates (in left-to-right order). Since each coordinate has | coordinates (in left-to-right order). Since each coordinate has | |||

known length, this operation is reversible. When appropriate, we | known length, this operation is reversible. When appropriate, we | |||

refer to the latter as the octet (rather than the pair) | refer to the latter as the octet (rather than the pair) | |||

representation of a point. | representation of a point. | |||

NOTE 2: The octet representation of compressed points above | NOTE 2: The octet representation of compressed points above | |||

identifies the parity bit t of the curve point in question via the | identifies the parity bit t of the curve point in question via the | |||

1-octet representations of the integers 0 and 1. Obviously, other | 1-octet representations of the integers 0 and 1. Obviously, other | |||

1-1 mappings are also possible. As an example, with [SEC1], the | 1-1 mappings are also possible. As an example, with [SEC1], the | |||

parity bit t is represented by 0x02 or 0x03 depending on whether t=0 | parity bit t is represented by 0x02 or 0x03 depending on whether t=0 | |||

or t=1, respectively The same [SEC1] specification represents affine | or t=1, respectively. The same [SEC1] specification represents | |||

points as above (as octet string), but prepends this with the 1-octet | affine points as above (as octet string), but prepends this with the | |||

prefix 0x04, and represents the identity element of the curve as the | 1-octet prefix 0x04, and represents the identity element of the curve | |||

1-octet string 0x00. This variable-size point representation has the | as the 1-octet string 0x00. This variable-size point representation | |||

property that its 1-octet prefix identifies whether it encodes an | has the property that its 1-octet prefix identifies whether it | |||

affine curve point, a compressed point (including parity bit), or the | encodes an affine curve point, a compressed point (including parity | |||

identity element, while the remainder of this representation uniquely | bit), or the identity element, while the remainder of this | |||

determines the curve point's value. While the description in [SEC1] | representation uniquely determines the curve point's value. While | |||

only applies to Weierstrass curves, the description above applies to | the description in [SEC1] only applies to Weierstrass curves, the | |||

each of the curve models we consider (i.e., these apply to Montgomery | description above applies to each of the curve models we consider | |||

curves and twisted Edwards curves as well). Collectively, we simply | (i.e., these apply to Montgomery curves and twisted Edwards curves as | |||

refer to this as the "SEC1" point representation. | well). Collectively, we simply refer to this as the "SEC1" point | |||

representation. | ||||

Note that elements of a prime field GF(p), where p is a 255-bit prime | Note that elements of a prime field GF(p), where p is a 255-bit prime | |||

number, have a tight representation as a 32-octet string, where a | number, have a tight representation as a 32-octet string, where a | |||

fixed bit position is always set to zero. (This is the leftmost bit | fixed bit position is always set to zero. (This is the leftmost bit | |||

position of this octet string if one follows the MSB/msb | position of this octet string if one follows the MSB/msb | |||

representation conventions.) This allows the parity bit of a | representation conventions.) This allows the parity bit of a | |||

compressed point (see Appendix H) to be encoded in this bit position | compressed point (see Appendix H) to be encoded in this bit position | |||

and, thereby, allows a compressed point and an element of GF(p) to be | and, thereby, allows a compressed point and an element of GF(p) to be | |||

represented by an octet string of the same length. This is called | represented by an octet string of the same length. This is called | |||

the "squeezed" point representation. (We will use this squeezed | the "squeezed" point representation. (We will use this squeezed | |||

skipping to change at page 90, line 17 ¶ | skipping to change at page 90, line 17 ¶ | |||

value of s). In the second case, one first maps the pair (u1, u2) to | value of s). In the second case, one first maps the pair (u1, u2) to | |||

the pair (t1, t2):=(delta*u1^2, delta*u2^2) and subsequently computes | the pair (t1, t2):=(delta*u1^2, delta*u2^2) and subsequently computes | |||

P2compl(t1, t2):=Pcompl(t1) + Pcompl(t2), where Pcompl(t):=P(t) if t | P2compl(t1, t2):=Pcompl(t1) + Pcompl(t2), where Pcompl(t):=P(t) if t | |||

is nonzero and where Pcompl(0):=P1 otherwise. In either case, again, | is nonzero and where Pcompl(0):=P1 otherwise. In either case, again, | |||

the resulting mapping is uniquely defined after fixing the points P0 | the resulting mapping is uniquely defined after fixing the points P0 | |||

and P1 and the non-square element delta of GF(q). | and P1 and the non-square element delta of GF(q). | |||

Appendix L. Curve secp256k1 and Friend | Appendix L. Curve secp256k1 and Friend | |||

This section illustrates how isogenies can be used to yield curves | This section illustrates how isogenies can be used to yield curves | |||

with specific properties (here, for illustrated for the "BitCoin" | with specific properties (here, illustrated for the "BitCoin" curve | |||

curve secp256k1). | secp256k1). | |||

L.1. Curve Definition and Alternative Representation | L.1. Curve Definition and Alternative Representation | |||

The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined | The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined | |||

over the prime field GF(p), with p:=2^256-2^32-2^9-2^8-2^7-2^6-2^4-1, | over the prime field GF(p), with p:=2^256-2^32-2^9-2^8-2^7-2^6-2^4-1, | |||

where a:=0 and b:=7. This curve has order h*n, where h=1 and where n | where a:=0 and b:=7. This curve has order h*n, where h=1 and where n | |||

is a prime number. For this curve, domain parameter a is zero, | is a prime number. For this curve, domain parameter a is zero, | |||

whereas b is not. The quadratic twist of this curve has order h1*n1, | whereas b is not. The quadratic twist of this curve has order h1*n1, | |||

where h1 is a 37-bit integer and where n1 is a prime number. For | where h1 is a 37-bit integer and where n1 is a prime number. For | |||

this curve, the base point is the point (GX, GY). | this curve, the base point is the point (GX, GY). | |||

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

f976c6a7 8611c800) | f976c6a7 8611c800) | |||

L.4. Isogeny Details | L.4. Isogeny Details | |||

The isogeny and dual isogeny are both isogenies with degree l=3. | The isogeny and dual isogeny are both isogenies with degree l=3. | |||

Both are specified by a triple of polynomials u, v, and w (resp. u', | Both are specified by a triple of polynomials u, v, and w (resp. u', | |||

v', and w') of degree 3, 3, and 1, respectively, with coefficients in | v', and w') of degree 3, 3, and 1, respectively, with coefficients in | |||

GF(p). The coeffients of each of these polynomials are specified in | GF(p). The coeffients of each of these polynomials are specified in | |||

Appendix L.4.1 (for the isogeny) and in Appendix L.4.2 (for the dual | Appendix L.4.1 (for the isogeny) and in Appendix L.4.2 (for the dual | |||

isogeny). For each polynomial in variable x, the coefficients are | isogeny). For each polynomial in variable x, the coefficients are | |||

tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in | tabulated as the sequence of coefficients of x^0, x^1, x^2, ..., in | |||

hexadecimal format. | hexadecimal format. | |||

L.4.1. Isogeny Parameters | L.4.1. Isogeny Parameters | |||

L.4.1.1. Coefficients of u(x) | L.4.1.1. Coefficients of u(x) | |||

0 0x54 | 0 0x54 | |||

1 0xa4d89db3ed06c81e6143ec2eca9f761d8d17260dc229e1da1f73f714506872a9 | 1 0xa4d89db3ed06c81e6143ec2eca9f761d8d17260dc229e1da1f73f714506872a9 | |||

skipping to change at page 103, line 38 ¶ | skipping to change at page 103, line 38 ¶ | |||

f230fa14) | f230fa14) | |||

N.4. Isogeny Details | N.4. Isogeny Details | |||

The isogeny and dual isogeny are both isogenies with degree l=2. | The isogeny and dual isogeny are both isogenies with degree l=2. | |||

Both are specified by a triple of polynomials u, v, and w (resp. u', | Both are specified by a triple of polynomials u, v, and w (resp. u', | |||

v', and w') of degree 2, 2, and 1, respectively, with coefficients in | v', and w') of degree 2, 2, and 1, respectively, with coefficients in | |||

GF(p). The coeffients of each of these polynomials are specified in | GF(p). The coeffients of each of these polynomials are specified in | |||

Appendix N.4.1 (for the isogeny) and in Appendix N.4.2 (for the dual | Appendix N.4.1 (for the isogeny) and in Appendix N.4.2 (for the dual | |||

isogeny). For each polynomial in variable x, the coefficients are | isogeny). For each polynomial in variable x, the coefficients are | |||

tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in | tabulated as the sequence of coefficients of x^0, x^1, x^2, ..., in | |||

hexadecimal format. | hexadecimal format. | |||

N.4.1. Isogeny Parameters | N.4.1. Isogeny Parameters | |||

N.4.1.1. Coefficients of u(x) | N.4.1.1. Coefficients of u(x) | |||

0 0x01 | 0 0x01 | |||

1 0x55555555555555555555555555555555555555555555555555555554ffffffff | 1 0x55555555555555555555555555555555555555555555555555555554ffffffff | |||

ffffffffffffffffffffffffffffffffffffffffffff3473 | ffffffffffffffffffffffffffffffffffffffffffff3473 | |||

End of changes. 30 change blocks. | ||||

71 lines changed or deleted | | 93 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/ |