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/