draft-ietf-lwig-curve-representations-00.txt | draft-ietf-lwig-curve-representations-01.txt | |||
---|---|---|---|---|

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

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

Intended status: Informational October 18, 2018 | Intended status: Informational November 06, 2018 | |||

Expires: April 21, 2019 | Expires: May 10, 2019 | |||

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

draft-ietf-lwig-curve-representations-00 | draft-ietf-lwig-curve-representations-01 | |||

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 implement elliptic curve | illustrates how this can be used to carry out elliptic curve | |||

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

e.g., ECDSA and ECDH using NIST prime curves. | using NIST prime curves. | |||

Requirements Language | Requirements Language | |||

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | |||

"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and | "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and | |||

"OPTIONAL" in this document are to be interpreted as described in RFC | "OPTIONAL" in this document are to be interpreted as described in RFC | |||

2119 [RFC2119]. | 2119 [RFC2119]. | |||

Status of This Memo | Status of This Memo | |||

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

Internet-Drafts are working documents of the Internet Engineering | Internet-Drafts are working documents of the Internet Engineering | |||

Task Force (IETF). Note that other groups may also distribute | Task Force (IETF). Note that other groups may also distribute | |||

working documents as Internet-Drafts. The list of current Internet- | working documents as Internet-Drafts. The list of current Internet- | |||

Drafts is at https://datatracker.ietf.org/drafts/current/. | Drafts is at https://datatracker.ietf.org/drafts/current/. | |||

Internet-Drafts are draft documents valid for a maximum of six months | Internet-Drafts are draft documents valid for a maximum of six months | |||

and may be updated, replaced, or obsoleted by other documents at any | and may be updated, replaced, or obsoleted by other documents at any | |||

time. It is inappropriate to use Internet-Drafts as reference | time. It is inappropriate to use Internet-Drafts as reference | |||

material or to cite them other than as "work in progress." | material or to cite them other than as "work in progress." | |||

This Internet-Draft will expire on April 21, 2019. | This Internet-Draft will expire on May 10, 2019. | |||

Copyright Notice | Copyright Notice | |||

Copyright (c) 2018 IETF Trust and the persons identified as the | Copyright (c) 2018 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 . . . . . . . . 3 | 1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 3 | |||

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

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

3.1. ECDSA-SHA256-25519 . . . . . . . . . . . . . . . . . . . 4 | 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 5 | |||

3.2. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 4 | 4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 5 | |||

4. Security Considerations . . . . . . . . . . . . . . . . . . . 4 | 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 5 | |||

5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 5 | 4.3. Specification of ECDSA-SHA256-Wei25519 . . . . . . . . . 5 | |||

6. Normative References . . . . . . . . . . . . . . . . . . . . 5 | 4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 6 | |||

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

A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 6 | 6. Security Considerations . . . . . . . . . . . . . . . . . . . 7 | |||

A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 6 | 7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 8 | |||

A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 6 | 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 | |||

Appendix B. Elliptic Curve Group Operations . . . . . . . . . . 7 | 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 8 | |||

B.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 7 | 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 | |||

B.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 7 | 10.1. Normative References . . . . . . . . . . . . . . . . . . 8 | |||

B.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 8 | 10.2. Informative References . . . . . . . . . . . . . . . . . 9 | |||

Appendix C. Relationship Between Curve Models . . . . . . . . . 8 | Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 10 | |||

C.1. Mapping between twisted Edwards Curves and Montgomery | A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 10 | |||

Curves . . . . . . . . . . . . . . . . . . . . . . . . . 8 | A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 10 | |||

C.2. Mapping between Montgomery Curves and Weierstrass Curves 9 | A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 10 | |||

C.3. Mapping between twisted Edwards Curves and Weierstrass | Appendix B. Elliptic Curve Nomenclature . . . . . . . . . . . . 11 | |||

Curves . . . . . . . . . . . . . . . . . . . . . . . . . 10 | Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 11 | |||

Appendix D. Curve25519 and Cousins . . . . . . . . . . . . . . . 10 | C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 11 | |||

D.1. Curve Definition and Alternative Representations . . . . 10 | C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 12 | |||

D.2. Switching between Alternative Representations . . . . . . 10 | C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 13 | |||

D.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 12 | Appendix D. Relationship Between Curve Models . . . . . . . . . 14 | |||

Appendix E. Further Mappings . . . . . . . . . . . . . . . . . . 14 | D.1. Mapping between twisted Edwards Curves and Montgomery | |||

E.1. Isomorphic Mapping between Weierstrass Curves . . . . . . 14 | Curves . . . . . . . . . . . . . . . . . . . . . . . . . 14 | |||

E.2. Isogeneous Mapping between Weierstrass Curves . . . . . . 15 | D.2. Mapping between Montgomery Curves and Weierstrass Curves 14 | |||

Appendix F. Further Cousins of Curve25519 . . . . . . . . . . . 16 | D.3. Mapping between twisted Edwards Curves and Weierstrass | |||

F.1. Further Alternative Representations . . . . . . . . . . . 16 | Curves . . . . . . . . . . . . . . . . . . . . . . . . . 15 | |||

F.2. Further Switching . . . . . . . . . . . . . . . . . . . . 16 | Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 15 | |||

F.3. Further Domain Parameters . . . . . . . . . . . . . . . . 17 | E.1. Curve Definition and Alternative Representations . . . . 15 | |||

Appendix G. Isogeny Details . . . . . . . . . . . . . . . . . . 19 | E.2. Switching between Alternative Representations . . . . . . 16 | |||

G.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 19 | E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 17 | |||

G.1.1. Coefficients of u(x): . . . . . . . . . . . . . . . . 19 | Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 19 | |||

G.1.2. Coefficients of v(x): . . . . . . . . . . . . . . . . 21 | F.1. Isomorphic Mapping between Weierstrass Curves . . . . . . 19 | |||

G.1.3. Coefficients of w(x): . . . . . . . . . . . . . . . . 24 | F.2. Isogenous Mapping between Weierstrass Curves . . . . . . 20 | |||

G.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 25 | Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 21 | |||

G.2.1. Coefficients of u'(x): . . . . . . . . . . . . . . . 25 | G.1. Further Alternative Representations . . . . . . . . . . . 21 | |||

G.2.2. Coefficients of v'(x): . . . . . . . . . . . . . . . 27 | G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 22 | |||

G.2.3. Coefficients of w'(x): . . . . . . . . . . . . . . . 30 | G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 23 | |||

Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 31 | Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 24 | |||

H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 24 | ||||

H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 24 | ||||

H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 26 | ||||

H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 29 | ||||

H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 30 | ||||

H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 30 | ||||

H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 32 | ||||

H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 35 | ||||

Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 36 | ||||

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

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

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

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

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

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

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

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

Edwards curve, which are both specified in [RFC7748], as points of a | Edwards curve, which are both specified in [RFC7748], as points of a | |||

specific so-called "short" Weierstrass curve, called Wei25519. The | specific so-called "short" Weierstrass curve, called Wei25519. We | |||

draft also defines how to efficiently switch between these different | also define how to efficiently switch between these different | |||

representations. | representations. | |||

Use of Wei25519 allows easy definition of signature schemes and key | Use of Wei25519 allows easy definition of new signature schemes and | |||

agreement schemes already specified for traditional NIST prime | key agreement schemes already specified for traditional NIST prime | |||

curves, thereby allowing easy integration with existing | curves, thereby allowing easy integration with existing | |||

specifications, such as NIST SP 800-56a [SP-800-56a], FIPS Pub 186-4 | 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 | [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 | reuse on platforms that already implement some of these schemes using | |||

elliptic curve arithmetic for curves in "short" Weierstrass form (see | elliptic curve arithmetic for curves in "short" Weierstrass form (see | |||

Appendix B.1). | Appendix C.1). | |||

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 D. 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 P256, to | implements short-Weierstrass curves, such as the NIST curve P256, to | |||

also implement the CFRG curves Curve25519 and Ed25519. The draft | also implement the CFRG curves Curve25519 and Edwards25519. We also | |||

also caters to reuse of existing code where some domain parameters | cater to reusing of existing code where some domain parameters may | |||

may have been hardcoded, thereby widening the scope of applicability; | have been hardcoded, thereby widening the scope of applicability. To | |||

see Appendix F. | this end, we specify the short-Weierstrass curves Wei25519.2 and | |||

Wei25519.-3, with hardcoded domain parameter a=2 and a=-3 (mod p), | ||||

respectively; see Appendix G. | ||||

3. Example Uses | 3. Use of Representation Switches | |||

3.1. ECDSA-SHA256-25519 | ||||

RFC 8032 [RFC8032] specifies the use of EdDSA, a "full" Schnorr | The curves Curve25519, Edwards25519, and Wei25519, as specified in | |||

signature scheme, with instantiation by Edwards25519 and Ed448, two | Appendix E.3, are all isomorphic, with the transformations of | |||

so-called twisted Edwards curves. These curves can also be used with | Appendix E.2. These transformations map the specified base point of | |||

the widely implemented signature scheme ECDSA [FIPS-186-4], by | each of these curves to the specified base point of each of the other | |||

instantiating ECDSA with the curve Wei25519 and hash function SHA- | curves. Consequently, a public-key pair (k,R:=k*G) for any one of | |||

256, where "under the hood" an implementation may carry out elliptic | these curves corresponds, via these isomorphic mappings, to the | |||

curve scalar multiplication routines using the corresponding | public-key pair (k, R':=k*G') for each of these other curves (where G | |||

representations of a point of the curve Wei25519 in Weierstrass form | and G' are the corresponding base points of these curves). This | |||

as a point of the Montgomery curve Curve25519 or of the twisted | observation extends to the case where one also considers curve | |||

Edwards curve Edwards25519. (The corresponding ECDSA-SHA512-448 | Wei25519.2 (which has hardcoded domain parameter a=2), as specified | |||

scheme arises if one were to specify a curve in short-Weierstrass | in Appendix G.3, since it is isomorphic to Wei25519, with the | |||

form corresponding to Ed448 and use the hash function SHA512.) Note | transformation of Appendix G.2, and, thereby, also isomorphic to | |||

that, in either case, one can implement these schemes with the same | Curve25519 and Edwards25519. | |||

representation conventions as used with existing NIST specifications, | ||||

including bit/byte-ordering, compression functions, and the-like. | ||||

This allows implementations of ECDSA with the hash function SHA-256 | ||||

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

this draft to use the same implementation (instantiated with, | ||||

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

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

3.2. Other Uses | The curve Wei25519.-3 (which has hardcoded domain parameter a=-3 (mod | |||

p)) is not isomorphic to the curve Wei25519, but is related in a | ||||

slightly weaker sense: the curve Wei25519 is isogenous to the curve | ||||

Wei25519.-3, where the mapping of Appendix G.2 is an isogeny of | ||||

degree l=47 that maps the specified base point G of Wei25519 to the | ||||

specified base point G' of Wei25519.-3 and where the so-called dual | ||||

isogeny (which maps Wei25519.-3 to Wei25519) has the same degree | ||||

l=47, but does not map G' to G, but to a fixed multiple hereof, where | ||||

this multiple is l=47. Consequently, a public-key pair (k,R:=k*G) | ||||

for Wei25519 corresponds to the public-key pair (k, R':= k*G') for | ||||

Wei25519.-3 (via the l-isogeny), whereas the public-key pair (k, | ||||

R':=k*G') corresponds to the public-key pair (l*k, l*R=l*k*G) of | ||||

Wei25519 (via the dual isogeny). (Note the extra scalar l=47 here.) | ||||

Alternative curve representations can, therefore, be used in any | ||||

cryptographic scheme that involves computations on public-private key | ||||

pairs, where implementations may carry out computations on the | ||||

corresponding object for the isomorphic or isogenous curve and | ||||

convert the results back to the original curve (where, in case this | ||||

involves an l-isogeny, one has to take into account the factor l). | ||||

This includes use with elliptic-curve based signature schemes and key | ||||

agreement and key transport schemes. | ||||

4. Examples | ||||

4.1. Implementation of X25519 | ||||

RFC 7748 [RFC7748] specifies the use of X25519, a co-factor Diffie- | ||||

Hellman key agreement scheme, with instantiation by the Montgomery | ||||

curve Curve25519. This key agreement scheme was already specified in | ||||

Section 6.1.2.2 of NIST SP 800-56a [SP-800-56a] for elliptic curves | ||||

in short Weierstrass form. Hence, one can implement X25519 using | ||||

existing NIST routines by (1) representing a point of the Montgomery | ||||

curve Curve25519 as a point of the Weierstrass curve Wei25519; (2) | ||||

instantiating the co-factor Diffie-Hellman key agreement scheme of | ||||

the NIST specification with the resulting point and Wei25519 domain | ||||

parameters; (3) representing the key resulting from this scheme | ||||

(which is a point of the curve Wei25519 in Weierstrass form) as a | ||||

point of the Montgomery curve Curve25519. The representation change | ||||

can be implemented via a simple wrapper and involves a single modular | ||||

addition (see Appendix D.2). Using this method has the additional | ||||

advantage that one can reuse the public-private key pair routines, | ||||

domain parameter validation, and other checks that are already part | ||||

of the NIST specifications. Note: at this point, it is unclear | ||||

whether this implies that a FIPS-accredited module implementing co- | ||||

factor Diffie-Hellman for, e.g., P-256 would also extend this | ||||

accreditation to X25519. | ||||

4.2. Implementation of Ed25519 | ||||

RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature | ||||

scheme, with instantiation by the twisted Edwards curve Edwards25519. | ||||

One can implement the computation of the ephemeral key pair for | ||||

Ed25519 using an existing Montgomery curve implementation by (1) | ||||

generating a public-private key pair (k, R':=k*G') for Curve25519; | ||||

(2) representing this public-private key as the pair (k, R:=k*G) for | ||||

Ed25519. As before, the representation change can be implemented via | ||||

a simple wrapper. Note that the Montgomery ladder specified in | ||||

Section 5 of RFC7748 [RFC7748] does not provide sufficient | ||||

information to reconstruct R' (since it does not compute the | ||||

y-coordinate of R'). However, this deficiency can be remedied by | ||||

using a slightly modified version of the Montgomery ladder that | ||||

includes reconstruction of the y-coordinate of R':=k*G' at the end of | ||||

hereof (which uses the v-coordinate Gv of the base point of | ||||

Curve25519 as well). For details, see Appendix D.2. | ||||

4.3. Specification of ECDSA-SHA256-Wei25519 | ||||

FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and | ||||

can be instantiated not just with the NIST prime curves, but also | ||||

with other Weierstrass curves (that satisfy additional cryptographic | ||||

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

Weierstrass curve Wei25519 and the hash function SHA-256, where an | ||||

implementation may generate a public-private key pair for Wei25519 by | ||||

(1) internally carrying out these computations on the Montgomery | ||||

curve Curve25519, the twisted Edwards curve Edwards25519, or even the | ||||

Weierstrass curve Wei25519.-3 (with hardcoded a=-3 domain parameter); | ||||

(2) representing the result as a key pair for the curve Wei25519. | ||||

Note that, in either case, one can implement these schemes with the | ||||

same representation conventions as used with existing NIST | ||||

specifications, including bit/byte-ordering, compression functions, | ||||

and the-like. This allows implementations of ECDSA with the hash | ||||

function SHA-256 and with the NIST curve P-256 or with the curve | ||||

Wei25519 specified in this draft to use the same implementation | ||||

(instantiated with, respectively, the NIST P-256 elliptic curve | ||||

domain parameters or with the domain parameters of curve Wei25519 | ||||

specified in Appendix E). | ||||

4.4. Other Uses | ||||

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

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

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

4. Security Considerations | 5. Caveats | |||

The examples above illustrate how specifying the Weierstrass curve | ||||

Wei25519 may facilitate reuse of existing code and may simplify | ||||

standards development. However, the following caveats apply: | ||||

1. Unfriendly wire formats. The transformations between alternative | ||||

curve representations can be implemented at negligible relative | ||||

incremental cost if the curve points are represented as affine | ||||

points. If a point is represented in compressed format, | ||||

conversion usually requires a costly point decompression step. | ||||

This is the case in [RFC7748], where the inputs to the co-factor | ||||

Diffie-Hellman scheme X25519, as well as its output, are | ||||

represented in x-coordinate-only format; | ||||

2. Unfriendly representation conventions. While elliptic curve | ||||

computations are carried-out in a field GF(q) and, thereby, | ||||

involve large integer arithmetic, these integers are represented | ||||

as bit- and byte-strings. Here, [RFC8032] uses least- | ||||

significant-byte (LSB)/least-significant-bit (lsb) conventions, | ||||

whereas [RFC7748] uses LSB/most-significant-bit (msb) | ||||

conventions, and where most other cryptographic specifications, | ||||

including NIST SP800-56a [SP-800-56a], FIPS Pub 186-4 | ||||

[FIPS-186-4], and ANSI X9.62-2005 [ANSI-X9.62] use MSB/msb | ||||

conventions. Since each pair of conventions is different, this | ||||

does necessitate bit/byte representation conversions; | ||||

3. Unfriendly domain parameters. All traditional NIST curves are | ||||

Weierstrass curve with domain parameter a=-3, while all Brainpool | ||||

curves [RFC5639] are isomorphic to a Weierstrass curve of this | ||||

form. Thus, one can expect there to be existing Weierstrass | ||||

implementations with a hardcoded a=-3 domain parameter | ||||

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

curve Wei25519 as a potential vehicle for offering support for | ||||

the CFRG curves Curve25519 and Edwards25519 is not possible, | ||||

since not of the required form. Instead, one has to implement | ||||

Curve25519.-3 and include code that implements the isogeny and | ||||

dual isogeny from and to Wei25519. This isogeny has degree l=47 | ||||

and requires roughly 9kB of storage for isogeny and dual-isogeny | ||||

computations (see the tables in Appendix H). Note that storage | ||||

would have reduced to a single 32-bye table if the curve would | ||||

have been generated so as to be isomorphic to a Weierstrass curve | ||||

with hardcoded a=-3 parameter (this corresponds to l=1). Note: | ||||

an example of such a curve is the Montgomery curve M_{A,B} over | ||||

GF(p) with p=2^255-19, A=-1410290, and B=1 or (if one wants the | ||||

base point to still have u-coordinate u=9) A=-3960846. In either | ||||

case, the resulting curve has the same cryptographic properties | ||||

as Curve25519, while being more "Jacobian-friendly". | ||||

6. Security Considerations | ||||

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

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

Since this transformation is an isomorphism, this transformation maps | which is either an isomorphism or a low-degree isogeny. It is well- | |||

elliptic curve points to equivalent mathematical objects. | known that an isomorphism maps elliptic curve points to equivalent | |||

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

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

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

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

5. IANA Considerations | As to implementation security, reusing existing high-quality code or | |||

generic implementations that have been carefully designed to | ||||

withstand implementation attacks for one curve model may allow a more | ||||

economical way of development and maintenance than providing this | ||||

same functionality for each curve model separately (if multiple curve | ||||

models need to be supported) and, otherwise, may allow a more gradual | ||||

migration path, where one may initially use existing and accredited | ||||

chipsets that cater to the pre-dominant curve model used in practice | ||||

for over 15 years. | ||||

7. Privacy Considerations | ||||

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

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

provisions. | ||||

8. IANA Considerations | ||||

There is *currently* no IANA action required for this document. New | There is *currently* no IANA action required for this document. New | |||

object identifiers would be required in case one wishes to specify | object identifiers would be required in case one wishes to specify | |||

one or more of the "offspring" protocols exemplified in Section 3. | one or more of the "offspring" protocols exemplified in Section 4. | |||

6. Normative References | 9. Acknowledgements | |||

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

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

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

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

10. References | ||||

10.1. Normative References | ||||

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

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

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

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

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

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

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

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

Information Processing Standards Publication 186-4", US | Information Processing Standards Publication 186-4", US | |||

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

Technology Gaithersburg, MD, July 2013. | Technology, Gaithersburg, MD, July 2013. | |||

[GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to | ||||

Elliptic Curve Cryptography", New York: Springer-Verlag, | ||||

2004. | ||||

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | |||

Requirement Levels", BCP 14, RFC 2119, | Requirement Levels", BCP 14, RFC 2119, | |||

DOI 10.17487/RFC2119, March 1997, | DOI 10.17487/RFC2119, March 1997, | |||

<https://www.rfc-editor.org/info/rfc2119>. | <https://www.rfc-editor.org/info/rfc2119>. | |||

[RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography | [RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography | |||

(ECC) Brainpool Standard Curves and Curve Generation", | (ECC) Brainpool Standard Curves and Curve Generation", | |||

RFC 5639, DOI 10.17487/RFC5639, March 2010, | RFC 5639, DOI 10.17487/RFC5639, March 2010, | |||

<https://www.rfc-editor.org/info/rfc5639>. | <https://www.rfc-editor.org/info/rfc5639>. | |||

skipping to change at page 6, line 9 ¶ | skipping to change at page 9, line 28 ¶ | |||

[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital | [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital | |||

Signature Algorithm (EdDSA)", RFC 8032, | Signature Algorithm (EdDSA)", RFC 8032, | |||

DOI 10.17487/RFC8032, January 2017, | DOI 10.17487/RFC8032, January 2017, | |||

<https://www.rfc-editor.org/info/rfc8032>. | <https://www.rfc-editor.org/info/rfc8032>. | |||

[SP-800-56a] | [SP-800-56a] | |||

NIST SP 800-56a, "Recommendation for Pair-Wise Key | NIST SP 800-56a, "Recommendation for Pair-Wise Key | |||

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

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

of Standards and Technology Gaithersburg, MD, June 2013. | of Standards and Technology, Gaithersburg, MD, June 2013. | |||

10.2. Informative References | ||||

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

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

Series 265, July 1999. | ||||

[ECC-Isogeny] | ||||

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

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

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

2003. | ||||

[GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to | ||||

Elliptic Curve Cryptography", New York: Springer-Verlag, | ||||

2004. | ||||

[HW-ECC] W.P. Liu, "How to Use the Kinets LTC ECC HW to Accelerate | ||||

Curve25519 (version 7)", NXP, | ||||

https://community.nxp.com/docs/DOC-330199, April 2017. | ||||

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

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

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

prime power and where q is not divisible by three. Let W_{a,b} be | prime power and where q is not divisible by three. Let W_{a,b} be | |||

the Weierstrass curve with defining equation y^2 = x^3 + a*x + b, | the Weierstrass curve with defining equation y^2 = x^3 + a*x + b, | |||

where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is | where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is | |||

nonzero. The points of W_{a,b} are the ordered pairs (x, y) whose | nonzero. The points of W_{a,b} are the ordered pairs (x, y) whose | |||

coordinates are elements of GF(q) and that satisfy the defining | coordinates are elements of GF(q) and that satisfy the defining | |||

equation (the so-called affine points), together with the special | equation (the so-called affine points), together with the special | |||

point O (the so-called "point at infinity").This set forms a group | point O (the so-called "point at infinity").This set forms a group | |||

under addition, via the so-called "chord-and-tangent" rule, where the | under addition, via the so-called "secant-and-tangent" rule, where | |||

point at infinity serves as the identity element. See Appendix B.1 | the point at infinity serves as the identity element. See | |||

for details of the group operation. | Appendix C.1 for details of the group operation. | |||

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

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

prime power. Let M_{A,B} be the Montgomery curve with defining | prime power. Let M_{A,B} be the Montgomery curve with defining | |||

equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q) | equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q) | |||

with A unequal to (+/-)2 and with B nonzero. The points of M_{A,B} | with A unequal to (+/-)2 and with B nonzero. The points of M_{A,B} | |||

are the ordered pairs (u, v) whose coordinates are elements of GF(q) | are the ordered pairs (u, v) whose coordinates are elements of GF(q) | |||

and that satisfy the defining equation (the so-called affine points), | and that satisfy the defining equation (the so-called affine points), | |||

together with the special point O (the so-called "point at | together with the special point O (the so-called "point at | |||

infinity").This set forms a group under addition, via the so-called | infinity").This set forms a group under addition, via the so-called | |||

"chord-and-tangent" rule, where the point at infinity serves as the | "secant-and-tangent" rule, where the point at infinity serves as the | |||

identity element. See Appendix B.2 for details of the group | identity element. See Appendix C.2 for details of the group | |||

operation. | operation. | |||

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

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

prime power. Let E_{a,d} be the twisted Edwards curve with defining | prime power. Let E_{a,d} be the twisted Edwards curve with defining | |||

equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct | equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct | |||

nonzero elements of GF(q). The points of E_{a,d} are the ordered | nonzero elements of GF(q). The points of E_{a,d} are the ordered | |||

pairs (x, y) whose coordinates are elements of GF(q) and that satisfy | pairs (x, y) whose coordinates are elements of GF(q) and that satisfy | |||

the defining equation (the so-called affine points). It can be shown | the defining equation (the so-called affine points). It can be shown | |||

that this set forms a group under addition if a is a square in GF(q), | that this set forms a group under addition if a is a square in GF(q), | |||

whereas d is not, where the point (0, 1) serves as the identity | whereas d is not, where the point (0, 1) serves as the identity | |||

element. (Note that the identity element satisfies the defining | element. (Note that the identity element satisfies the defining | |||

equation.) See Appendix B.3 for details of the group operation. An | equation.) See Appendix C.3 for details of the group operation. | |||

Edwards curve is a twisted Edwards curve with a=1. | ||||

Appendix B. Elliptic Curve Group Operations | An Edwards curve is a twisted Edwards curve with a=1. | |||

B.1. Group Law for Weierstrass Curves | Appendix B. Elliptic Curve Nomenclature | |||

Each curve defined in Appendix A forms a commutative group under | ||||

addition. In Appendix C we specify the group laws, which depend on | ||||

the curve model in question. For completeness, we here include some | ||||

common elliptic curve nomenclature and basic properties (primarily so | ||||

as to keep this document self-contained). These notions are mainly | ||||

used in Appendix E and Appendix G and not essential for our | ||||

exposition. This section can be skipped at first reading. | ||||

Any point P of a curve is a generator of the cyclic subgroup | ||||

(P):={k*P | k = 0, 1, 2,...} of the curve. If (P) has cardinality l, | ||||

then l is called the order of P. The order of a curve is the | ||||

cardinality of the set of its points. A curve is cyclic if it is | ||||

generated by some point of this curve. All curves of prime order are | ||||

cyclic, while all curves of order |E| = h*n, where n is a large prime | ||||

number and where h is a small number (the so-called co-factor), have | ||||

a large cyclic subgroup of prime order n. In this case, a generator | ||||

of order n is called a base point, commonly denoted by G. A point of | ||||

order dividing h is said to be in the small subgroup. For curves of | ||||

prime order, this small subgroup is the singleton set, consisting of | ||||

only the identity element. | ||||

If R is a point on a curve E that is also contained in (P), there is | ||||

a unique integer k in the interval [0, l-1] so that R=kP, where l is | ||||

the order of P. This number is called the discrete logarithm of R to | ||||

the base P. The discrete logarithm problem is the problem of finding | ||||

the discrete logarithm of R to the base P for any two points P and R | ||||

of the curve, if such a number exists. | ||||

A public-private key pair is an ordered pair (k, R:=kG), where G is a | ||||

fixed base point of the curve. Here, k (the private key) is an | ||||

integer in the interval [0,n-1], where G has order n. | ||||

A quadratic twist of a curve E defined over a field GF(q) is a curve | ||||

E' related to E, with cardinality |E|+|E'|=2*(q+1). If E is a curve | ||||

in one of the curve models specified in this document, a quadratic | ||||

twist of this curve can be expressed using the same curve model, | ||||

although (naturally) with different curve parameters. | ||||

Appendix C. Elliptic Curve Group Operations | ||||

C.1. Group Law for Weierstrass Curves | ||||

For each point P of the Weierstrass curve W_{a,b}, the point at | For each point P of the Weierstrass curve W_{a,b}, the point at | |||

infinity O serves as identity element, i.e., P + O = O + P = P. | infinity O serves as identity element, i.e., P + O = O + P = P. | |||

For each affine point P:=(x, y) of the Weierstrass curve W_{a,b}, the | For each affine point P:=(x, y) of the Weierstrass curve W_{a,b}, the | |||

point -P is the point (x, -y) and one has P + (-P) = O. | point -P is the point (x, -y) and one has P + (-P) = O. | |||

Let P1:=(x1, y1) and P2:=(x2, y2) be distinct affine points of the | Let P1:=(x1, y1) and P2:=(x2, y2) be distinct affine points of the | |||

Weierstrass curve W_{a,b} and let Q:=P1 + P2, where Q is not the | Weierstrass curve W_{a,b} and let Q:=P1 + P2, where Q is not the | |||

identity element. Then Q:=(x, y), where | identity element. Then Q:=(x, y), where | |||

x + x1 + x2 = lambda^2 and y + y1 = lambda*(x1 - x), where lambda | x + x1 + x2 = lambda^2 and y + y1 = lambda*(x1 - x), where lambda | |||

= (y2 - y1)/(x2 - x1). | = (y2 - y1)/(x2 - x1). | |||

Let P:= (x1, y1) be an affine point of the Weierstrass curve W_{a,b} | Let P:= (x1, y1) be an affine point of the Weierstrass curve W_{a,b} | |||

and let Q:=2P, where Q is not the identity element. Then Q:= (x, y), | and let Q:=2*P, where Q is not the identity element. Then Q:= (x, | |||

where | y), where | |||

x + 2*x1 = lambda^2 and y + y1 = lambda*(x1 - x), where | x + 2*x1 = lambda^2 and y + y1 = lambda*(x1 - x), where | |||

lambda=(3*x1^2 + a)/(2*y1). | lambda=(3*x1^2 + a)/(2*y1). | |||

B.2. Group Law for Montgomery Curves | From the group law above it follows that if P=(x, y), P1=k*P=(x1, | |||

y1), and P2=(k+1)*P=(x2, y2) are affine points of the Weierstrass | ||||

curve W_{a,b} and if y is nonzero, then the y-coordinate of P1 can be | ||||

expressed in terms of the x-coordinates of P, P1, and P2, and the | ||||

y-coordinate of P, as | ||||

y1=((x*x1+a)*(x+x1)+2*b-x2*(x-x1)^2)/(2*y). | ||||

This property allows recovery of the y-coordinate of a point P1=k*P | ||||

that is computed via the so-called Montgomery ladder, where P is an | ||||

affine point with nonzero y-coordinate. Further details are out of | ||||

scope. | ||||

C.2. Group Law for Montgomery Curves | ||||

For each point P of the Montgomery curve M_{A,B}, the point at | For each point P of the Montgomery curve M_{A,B}, the point at | |||

infinity O serves as identity element, i.e., P + O = O + P = P. | infinity O serves as identity element, i.e., P + O = O + P = P. | |||

For each affine point P:=(x, y) of the Montgomery curve M_{A,B}, the | For each affine point P:=(x, y) of the Montgomery curve M_{A,B}, the | |||

point -P is the point (x, -y) and one has P + (-P) = O. | point -P is the point (x, -y) and one has P + (-P) = O. | |||

Let P1:=(x1, y1) and P2:=(x2, y2) be distinct affine points of the | Let P1:=(x1, y1) and P2:=(x2, y2) be distinct affine points of the | |||

Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the | Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the | |||

identity element. Then Q:=(x, y), where | identity element. Then Q:=(x, y), where | |||

x + x1 + x2 = B*lambda^2 - A and y + y1 = lambda*(x1 - x), where | x + x1 + x2 = B*lambda^2 - A and y + y1 = lambda*(x1 - x), where | |||

lambda=(y2 - y1)/(x2 - x1). | lambda=(y2 - y1)/(x2 - x1). | |||

Let P:= (x1, y1) be an affine point of the Montgomery curve M_{A,B} | Let P:= (x1, y1) be an affine point of the Montgomery curve M_{A,B} | |||

and let Q:=2P, where Q is not the identity element. Then Q:= (x, y), | and let Q:=2*P, where Q is not the identity element. Then Q:= (x, | |||

where | y), where | |||

x + 2*x1 = B*lambda^2 - A and y + y1 = lambda*(x1 - x), where | x + 2*x1 = B*lambda^2 - A and y + y1 = lambda*(x1 - x), where | |||

lambda=(3*x1^2 + 2*A*x1+1)/(2*y1). | lambda=(3*x1^2 + 2*A*x1+1)/(2*B*y1). | |||

Alternative and more efficient group laws exist, e.g., when using the | From the group law above it follows that if P=(x, y), P1=k*P=(x1, | |||

so-called Montgomery ladder. Details are out of scope. | y1), and P2=(k+1)*P=(x2, y2) are affine points of the Montgomery | |||

curve M_{A,B} and if y is nonzero, then the y-coordinate of P1 can be | ||||

expressed in terms of the x-coordinates of P, P1, and P2, and the | ||||

y-coordinate of P, as | ||||

B.3. Group Law for Twisted Edwards Curves | y1=((x*x1+1)*(x+x1+2*A)-2*A-x2*(x-x1)^2)/(2*B*y). | |||

This property allows recovery of the y-coordinate of a point P1=k*P | ||||

that is computed via the so-called Montgomery ladder, where P is an | ||||

affine point with nonzero y-coordinate. Further details are out of | ||||

scope. | ||||

C.3. Group Law for Twisted Edwards Curves | ||||

Note: The group laws below hold for twisted Edwards curves E_{a,d} | Note: The group laws below hold for twisted Edwards curves E_{a,d} | |||

where a is a square in GF(q), whereas d is not. In this case, the | where a is a square in GF(q), whereas d is not. In this case, the | |||

addition formulae below are defined for each pair of points, without | addition formulae below are defined for each pair of points, without | |||

exceptions. Generalizations of this group law to other twisted | exceptions. Generalizations of this group law to other twisted | |||

Edwards curves are out of scope. | Edwards curves are out of scope. | |||

For each point P of the twisted Edwards curve E_{a,d}, the point | For each point P of the twisted Edwards curve E_{a,d}, the point | |||

O=(0,1) serves as identity element, i.e., P + O = O + P = P. | O=(0,1) serves as identity element, i.e., P + O = O + P = P. | |||

For each point P:=(x, y) of the twisted Edwards curve E_{a,d}, the | For each point P:=(x, y) of the twisted Edwards curve E_{a,d}, the | |||

point -P is the point (-x, y) and one has P + (-P) = O. | point -P is the point (-x, y) and one has P + (-P) = O. | |||

Let P1:=(x1, y1) and P2:=(x2, y2) be points of the twisted Edwards | Let P1:=(x1, y1) and P2:=(x2, y2) be points of the twisted Edwards | |||

curve E_{a,d} and let Q:=P1 + P2. Then Q:=(x, y), where | curve E_{a,d} and let Q:=P1 + P2. Then Q:=(x, y), where | |||

x = (x1*y2 + x2*y1)/(1 + d*x1*x2*y1*y2) and y = (y1*y2 - | x = (x1*y2 + x2*y1)/(1 + d*x1*x2*y1*y2) and y = (y1*y2 - | |||

a*x1*x2)/(1 - d*x1*x2*y1*y2). | a*x1*x2)/(1 - d*x1*x2*y1*y2). | |||

Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and | Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and | |||

let Q:=2P. Then Q:=(x, y), where | let Q:=2*P. Then Q:=(x, y), where | |||

x = (2*x1*y1)/(1 + d*x1^2*y1^2) and y = (y1^2 - a*x1^2)/(1 - | x = (2*x1*y1)/(1 + d*x1^2*y1^2) and y = (y1^2 - a*x1^2)/(1 - | |||

d*x1^2*y1^2). | d*x1^2*y1^2). | |||

Note that one can use the formulae for point addition to implement | Note that one can use the formulae for point addition for | |||

point doubling, taking inverses and adding the identity element as | implementing point doubling, taking inverses and adding the identity | |||

well (i.e., the point addition formulae are uniform and complete | element as well (i.e., the point addition formulae are uniform and | |||

(subject to our Note above)). | complete (subject to our Note above)). | |||

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

The non-binary curves specified in Appendix A are expressed in | The non-binary curves specified in Appendix A are expressed in | |||

different curve models, viz. as curves in short-Weierstrass form, as | different curve models, viz. as curves in short-Weierstrass form, as | |||

Montgomery curves, or as twisted Edwards curves. These curve models | Montgomery curves, or as twisted Edwards curves. These curve models | |||

are related, as follows. | are related, as follows. | |||

C.1. Mapping between twisted Edwards Curves and Montgomery Curves | D.1. Mapping between twisted Edwards Curves and Montgomery Curves | |||

One can map points of the Montgomery curve M_{A,B} to points of the | One can map points of the Montgomery curve M_{A,B} to points of the | |||

twisted Edwards curve E_{a,d}, where a:=(A+2)/B and d:=(A-2)/B and, | twisted Edwards curve E_{a,d}, where a:=(A+2)/B and d:=(A-2)/B and, | |||

conversely, map points of the twisted Edwards curve E_{a,d} to points | conversely, map points of the twisted Edwards curve E_{a,d} to points | |||

of the Montgomery curve M_{A,B}, where A:=2(a+d)/(a-d) and where | of the Montgomery curve M_{A,B}, where A:=2(a+d)/(a-d) and where | |||

B:=4/(a-d). For twisted Edwards curves we consider (i.e., those | B:=4/(a-d). For twisted Edwards curves we consider (i.e., those | |||

where a is a square in GF(q), whereas d is not), this defines a one- | where a is a square in GF(q), whereas d is not), this defines a one- | |||

to-one correspondence, which - in fact - is an isomorphism between | to-one correspondence, which - in fact - is an isomorphism between | |||

M_{A,B} and E_{a,d}, thereby showing that, e.g., the discrete | M_{A,B} and E_{a,d}, thereby showing that, e.g., the discrete | |||

logarithm problem in either curve model is equally hard. | logarithm problem in either curve model is equally hard. | |||

skipping to change at page 9, line 27 ¶ | skipping to change at page 14, line 42 ¶ | |||

infinity O and the point (0, 0) of order two of M_{A,B}, while each | infinity O and the point (0, 0) of order two of M_{A,B}, while each | |||

other point (x, y) of E_{a,d} is mapped to the point (u, | other point (x, y) of E_{a,d} is mapped to the point (u, | |||

v):=((1+y)/(1-y), (1+y)/((1-y)*x)) of M_{A,B}. | v):=((1+y)/(1-y), (1+y)/((1-y)*x)) of M_{A,B}. | |||

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

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

Edwards curve on the corresponding Montgomery curve, or vice-versa, | Edwards curve on the corresponding Montgomery curve, or vice-versa, | |||

and translating the result back to the original curve, thereby | and translating the result back to the original curve, thereby | |||

potentially allowing code reuse. | potentially allowing code reuse. | |||

C.2. Mapping between Montgomery Curves and Weierstrass Curves | D.2. Mapping between Montgomery Curves and Weierstrass Curves | |||

One can map points of the Montgomery curve M_{A,B} to points of the | One can map points of the Montgomery curve M_{A,B} to points of the | |||

Weierstrass curve W_{a,b}, where a:=(3-A^2)/(3*B^2) and | Weierstrass curve W_{a,b}, where a:=(3-A^2)/(3*B^2) and | |||

b:=(2*A^3-9*A)/(27*B^3). This defines a one-to-one correspondence, | b:=(2*A^3-9*A)/(27*B^3). This defines a one-to-one correspondence, | |||

which - in fact - is an isomorphism between M_{A,B} and W_{a,b}, | which - in fact - is an isomorphism between M_{A,B} and W_{a,b}, | |||

thereby showing that, e.g., the discrete logarithm problem in either | thereby showing that, e.g., the discrete logarithm problem in either | |||

curve model is equally hard. | curve model is equally hard. | |||

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

at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while | at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while | |||

skipping to change at page 9, line 49 ¶ | skipping to change at page 15, line 15 ¶ | |||

B+A/(3*B), v/B) of W_{a,b}. Note that not all Weierstrass curves can | B+A/(3*B), v/B) of W_{a,b}. Note that not all Weierstrass curves can | |||

be injectively mapped to Montgomery curves, since the latter have a | be injectively mapped to Montgomery curves, since the latter have a | |||

point of order two and the former may not. In particular, if a | point of order two and the former may not. In particular, if a | |||

Weierstrass curve has prime order, such as is the case with the so- | Weierstrass curve has prime order, such as is the case with the so- | |||

called "NIST curves", this inverse mapping is not defined. | called "NIST curves", this inverse mapping is not defined. | |||

This mapping can be used to implement elliptic curve group operations | This mapping can be used to implement elliptic curve group operations | |||

originally defined for a twisted Edwards curve or for a Montgomery | originally defined for a twisted Edwards curve or for a Montgomery | |||

curve using group operations on the corresponding elliptic curve in | curve using group operations on the corresponding elliptic curve in | |||

short-Weierstrass form and translating the result back to the | short-Weierstrass form and translating the result back to the | |||

original curve, thereby potentially allowing code reuse. Note that | original curve, thereby potentially allowing code reuse. | |||

implementations for elliptic curves with short-Weierstrass form that | ||||

hard-code the domain parameter a to a= -3 (which value is known to | ||||

allow more efficient implementations) cannot always be used this way, | ||||

since the curve W_{a,b} may not always be expressed in terms of a | ||||

Weierstrass curve with a=-3 via a coordinate transformation. | ||||

C.3. Mapping between twisted Edwards Curves and Weierstrass Curves | Note that implementations for elliptic curves with short-Weierstrass | |||

form that hard-code the domain parameter a to a= -3 (which value is | ||||

known to allow more efficient implementations) cannot always be used | ||||

this way, since the curve W_{a,b} resulting from an isomorphic | ||||

mapping cannot always be expressed as a Weierstrass curve with a=-3 | ||||

via a coordinate transformation. For more details, see Appendix F. | ||||

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

One can map points of the twisted Edwards curve E_{a,d} to points of | One can map points of the twisted Edwards curve E_{a,d} to points of | |||

the Weierstrass curve W_{a,b}, via function composition, where one | the Weierstrass curve W_{a,b}, via function composition, where one | |||

uses the isomorphic mapping between twisted Edwards curve and | uses the isomorphic mapping between twisted Edwards curve and | |||

Montgomery curves of Appendix C.1 and the one between Montgomery and | Montgomery curves of Appendix D.1 and the one between Montgomery and | |||

Weierstrass curves of Appendix C.2. Obviously, one can use function | Weierstrass curves of Appendix D.2. Obviously, one can use function | |||

composition (now using the respective inverses) to realize the | composition (now using the respective inverses) to realize the | |||

inverse of this mapping. | inverse of this mapping. | |||

Appendix D. Curve25519 and Cousins | Appendix E. Curve25519 and Cousins | |||

D.1. Curve Definition and Alternative Representations | E.1. Curve Definition and Alternative Representations | |||

The elliptic curve Curve25519 is the Montgomery curve M_{A,B} defined | The elliptic curve Curve25519 is the Montgomery curve M_{A,B} defined | |||

over the prime field GF(p), with p:=2^{255}-19, where A:=486662 and | over the prime field GF(p), with p:=2^{255}-19, where A:=486662 and | |||

B:=1. This curve has order h*n, where h=8 and where n is a prime | B:=1. This curve has order h*n, where h=8 and where n is a prime | |||

number. For this curve, A^2-4 is not a square in GF(p), whereas A+2 | number. For this curve, A^2-4 is not a square in GF(p), whereas A+2 | |||

is. The quadratic twist of this curve has order h1*n1, where h1=4 | is. The quadratic twist of this curve has order h1*n1, where h1=4 | |||

and where n1 is a prime number. For this curve, the base point is | and where n1 is a prime number. For this curve, the base point is | |||

the point (Gu,Gv), where Gu=9 and where Gv is an odd integer in the | the point (Gu,Gv), where Gu=9 and where Gv is an odd integer in the | |||

interval [0, p-1]. | interval [0, p-1]. | |||

This curve has the same group structure as (is "isomorphic" to) the | This curve has the same group structure as (is "isomorphic" to) the | |||

twisted Edwards curve E_{a,d} defined over GF(p), with as base point | twisted Edwards curve E_{a,d} defined over GF(p), with as base point | |||

the point (Gx,Gy), where parameters are as specified in Appendix D.3. | the point (Gx,Gy), where parameters are as specified in Appendix E.3. | |||

This curve is denoted as Edwards25519. For this curve, the parameter | This curve is denoted as Edwards25519. For this curve, the parameter | |||

a is a square in GF(p), whereas d is not, so the group laws of | a is a square in GF(p), whereas d is not, so the group laws of | |||

Appendix B.3 apply. | Appendix C.3 apply. | |||

The curve is also isomorphic to the elliptic curve W_{a,b} in short- | The curve is also isomorphic to the elliptic curve W_{a,b} in short- | |||

Weierstrass form defined over GF(p), with as base point the point | Weierstrass form defined over GF(p), with as base point the point | |||

(Gx',Gy'), where parameters are as specified in Appendix D.3. This | (Gx',Gy'), where parameters are as specified in Appendix E.3. This | |||

curve is denoted as Wei25519. | curve is denoted as Wei25519. | |||

D.2. Switching between Alternative Representations | E.2. Switching between Alternative Representations | |||

Each affine point (u,v) of Curve25519 corresponds to the point | Each affine point (u,v) of Curve25519 corresponds to the point | |||

(x,y):=(u + A/3,y) of Wei25519, while the point at infinity of | (x,y):=(u + A/3,y) of Wei25519, while the point at infinity of | |||

Curve25519 corresponds to the point at infinity of Wei25519. (Here, | Curve25519 corresponds to the point at infinity of Wei25519. (Here, | |||

we used the mapping of Appendix C.2.) Under this mapping, the base | we used the mapping of Appendix D.2.) Under this mapping, the base | |||

point (Gu,Gv) of Curve25519 corresponds to the base point (Gx',Gy') | point (Gu,Gv) of Curve25519 corresponds to the base point (Gx',Gy') | |||

of Wei25519. The inverse mapping maps the affine point (x,y) of | of Wei25519. The inverse mapping maps the affine point (x,y) of | |||

Wei25519 to (u,v):=(x - A/3,y) of Curve25519, while mapping the point | Wei25519 to (u,v):=(x - A/3,y) of Curve25519, while mapping the point | |||

at infinity of Wei25519 to the point at infinity of Curve25519. Note | at infinity of Wei25519 to the point at infinity of Curve25519. Note | |||

that this mapping involves a simple shift of the first coordinate and | that this mapping involves a simple shift of the first coordinate and | |||

can be implemented via integer-only arithmetic as a shift of (p+A)/3 | can be implemented via integer-only arithmetic as a shift of (p+A)/3 | |||

for the isomorphic mapping and a shift of -(p+A)/3 for its inverse, | for the isomorphic mapping and a shift of -(p+A)/3 for its inverse, | |||

where delta=(p+A)/3 is the element of GF(p) defined by | where delta=(p+A)/3 is the element of GF(p) defined by | |||

delta 19298681539552699237261830834781317975544997444273427339909597 | delta 19298681539552699237261830834781317975544997444273427339909597 | |||

skipping to change at page 11, line 33 ¶ | skipping to change at page 16, line 50 ¶ | |||

defined by | defined by | |||

c sqrt(-(A+2)) | c sqrt(-(A+2)) | |||

51042569399160536130206135233146329284152202253034631822681833788 | 51042569399160536130206135233146329284152202253034631822681833788 | |||

666877215207 | 666877215207 | |||

(=0x70d9120b 9f5ff944 2d84f723 fc03b081 3a5e2c2e b482e57d | (=0x70d9120b 9f5ff944 2d84f723 fc03b081 3a5e2c2e b482e57d | |||

3391fb55 00ba81e7) | 3391fb55 00ba81e7) | |||

(Here, we used the mapping of Appendix C.1.) The inverse mapping | (Here, we used the mapping of Appendix D.1.) The inverse mapping | |||

from Edwards25519 to Curve25519 is defined by mapping the point (0, | from Edwards25519 to Curve25519 is defined by mapping the point (0, | |||

1) and the point (0, -1) of order two of Edwards25519 to, | 1) and the point (0, -1) of order two of Edwards25519 to, | |||

respectively, the point at infinity and the point (0,0) of order two | respectively, the point at infinity and the point (0,0) of order two | |||

of Curve25519 and having each other point (x, y) of Edwards25519 | of Curve25519 and having each other point (x, y) of Edwards25519 | |||

correspond to the point ((1 + y)/(1 - y), c*(1 + y)/((1-y)*x)). | correspond to the point ((1 + y)/(1 - y), c*(1 + y)/((1-y)*x)). | |||

The curve Edwards25519 is isomorphic to the Weierstrass curve | The curve Edwards25519 is isomorphic to the Weierstrass curve | |||

Wei25519, where the base point (Gx,Gy) of Edwards25519 corresponds to | Wei25519, where the base point (Gx,Gy) of Edwards25519 corresponds to | |||

the base point (Gx',Gy') of Wei25519 and where the identity element | the base point (Gx',Gy') of Wei25519 and where the identity element | |||

(0,1) and the point (0,-1) of order two of Edwards25519 correspond | (0,1) and the point (0,-1) of order two of Edwards25519 correspond | |||

to, respectively, the point at infinity O and the point (A/3, 0) of | to, respectively, the point at infinity O and the point (A/3, 0) of | |||

order two of Wei25519 and where each other point (x, y) of | order two of Wei25519 and where each other point (x, y) of | |||

Edwards25519 corresponds to the point (x', y'):=((1+y)/(1-y)+A/3, | Edwards25519 corresponds to the point (x', y'):=((1+y)/(1-y)+A/3, | |||

c*(1+y)/((1-y)*x)) of Wei25519, where c was defined before. (Here, | c*(1+y)/((1-y)*x)) of Wei25519, where c was defined before. (Here, | |||

we used the mapping of Appendix C.3.) The inverse mapping from | we used the mapping of Appendix D.3.) The inverse mapping from | |||

Wei25519 to Edwards25519 is defined by mapping the point at infinity | Wei25519 to Edwards25519 is defined by mapping the point at infinity | |||

O and the point (A/3, 0) of order two of Wei25519 to, respectively, | O and the point (A/3, 0) of order two of Wei25519 to, respectively, | |||

the identity element (0,1) and the point (0,-1) of order two of | the identity element (0,1) and the point (0,-1) of order two of | |||

Edwards25519 and having each other point (x, y) of Wei25519 | Edwards25519 and having each other point (x, y) of Wei25519 | |||

correspond to the point (c*(3*x-A)/(3*y), (3*x-A-3)/(3*x-A+3)). | correspond to the point (c*(3*x-A)/(3*y), (3*x-A-3)/(3*x-A+3)). | |||

Note that these mappings can be easily realized in projective | Note that these mappings can be easily realized in projective | |||

coordinates, using a few field multiplications only, thus allowing | coordinates, using a few field multiplications only, thus allowing | |||

switching between alternative representations with negligible | switching between alternative representations with negligible | |||

relative incremental cost. | relative incremental cost. | |||

D.3. Domain Parameters | E.3. Domain Parameters | |||

The parameters of the Montgomery curve and the corresponding | The parameters of the Montgomery curve and the corresponding | |||

isomorphic curves in twisted Edwards curve and short-Weierstrass form | isomorphic curves in twisted Edwards curve and short-Weierstrass form | |||

are as indicated below. Here, the domain parameters of the | are as indicated below. Here, the domain parameters of the | |||

Montgomery curve Curve25519 and of the twisted Edwards curve | Montgomery curve Curve25519 and of the twisted Edwards curve | |||

Edwards25519 are as specified in RFC 7748; the domain parameters of | Edwards25519 are as specified in RFC 7748; the domain parameters of | |||

Wei25519 are "new". | Wei25519 are "new". | |||

General parameters (for all curve models): | General parameters (for all curve models): | |||

skipping to change at page 14, line 11 ¶ | skipping to change at page 19, line 29 ¶ | |||

(=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa | (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa | |||

aaaaaaaa aaad245a) | aaaaaaaa aaad245a) | |||

Gy' 14781619447589544791020593568409986887264606134616475288964881837 | Gy' 14781619447589544791020593568409986887264606134616475288964881837 | |||

755586237401 | 755586237401 | |||

(=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2 | (=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2 | |||

29e9c5a2 7eced3d9) | 29e9c5a2 7eced3d9) | |||

Appendix E. Further Mappings | Appendix F. Further Mappings | |||

The non-binary curves specified in Appendix A are expressed in | The non-binary curves specified in Appendix A are expressed in | |||

different curve models, viz. as curves in short-Weierstrass form, as | different curve models, viz. as curves in short-Weierstrass form, as | |||

Montgomery curves, or as twisted Edwards curves. Within each curve | Montgomery curves, or as twisted Edwards curves. Within each curve | |||

model, further mappings exist that induce a mapping between elliptic | model, further mappings exist that induce a mapping between elliptic | |||

curves within each curve model. This can be exploited to force some | curves within each curve model. This can be exploited to force some | |||

of the domain parameter to a value that allows a more efficient | of the domain parameters to a value that allows a more efficient | |||

implementation of the addition formulae. | implementation of the addition formulae. | |||

E.1. Isomorphic Mapping between Weierstrass Curves | F.1. Isomorphic Mapping between Weierstrass Curves | |||

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

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

nonzero value u of the finite field GF(q). This defines a one-to-one | nonzero value s of the finite field GF(q). This defines a one-to-one | |||

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

and W_{a',b'}, thereby showing that, e.g., the discrete logarithm | and W_{a',b'}, thereby showing that, e.g., the discrete logarithm | |||

problem in either curve model is equally hard. | problem in either curve model is equally hard. | |||

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

at infinity O of W_{a,b} to the point at infinity O of W_{a',b'}, | at infinity O of W_{a,b} to the point at infinity O of W_{a',b'}, | |||

while mapping each other point (x, y) of W_{a,b} to the point (x', | while mapping each other point (x, y) of W_{a,b} to the point (x', | |||

y'):=(x*s^2, y*s^3) of W_{a',b'}. The inverse mapping from W_{a',b'} | y'):=(x*s^2, y*s^3) of W_{a',b'}. The inverse mapping from W_{a',b'} | |||

to W_{a,b} is defined by mapping the point at infinity O of W_{a',b'} | to W_{a,b} is defined by mapping the point at infinity O of W_{a',b'} | |||

to the point at infinity O of W_{a,b}, while mapping each other point | to the point at infinity O of W_{a,b}, while mapping each other point | |||

(x', y') of W_{a',b'} to the point (x, y):=(x/s^2, y/s^3) of W_{a,b}. | (x', y') of W_{a',b'} to the point (x, y):=(x/s^2, y/s^3) of W_{a,b}. | |||

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 isomorphic | curve with a generic domain parameter a on a corresponding isomorphic | |||

Weierstrass curve with domain parameter a' that has a special form, | Weierstrass curve with domain parameter a' that has a special form, | |||

which is known to allow for more efficient implementations of | which is known to allow for more efficient implementations of | |||

addition laws, and translating the result back to the original curve. | addition laws, and translating the result back to the original curve. | |||

In particular, it is known that such efficiency improvements exist if | In particular, it is known that such efficiency improvements exist if | |||

a'=-3 (mod p) and one uses so-called Jacobian coordinates with a | a'=-3 (mod p) and one uses so-called Jacobian coordinates with a | |||

particular projective version of the addition laws of Appendix B.1. | particular projective version of the addition laws of Appendix C.1. | |||

While not all Weierstrass curves can be put into this form, all | While not all Weierstrass curves can be put into this form, all | |||

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

Brainpool curves [RFC5639] are isomorphic to a Weierstrass curve of | Brainpool curves [RFC5639] are isomorphic to a Weierstrass curve of | |||

this form. For details, we refer to Section 3.1.5 of [GECC]. | this form. | |||

Note that implementations for elliptic curves with short-Weierstrass | Note that implementations for elliptic curves with short-Weierstrass | |||

form that hard-code the domain parameter a to a= -3 (which value is | form that hard-code the domain parameter a to a= -3 cannot always be | |||

known to allow more efficient implementations) cannot always be used | used this way, since the curve W_{a,b} cannot always be expressed in | |||

this way, since the curve W_{a,b} may not always be expressed in | ||||

terms of a Weierstrass curve with a'=-3 via a coordinate | terms of a Weierstrass curve with a'=-3 via a coordinate | |||

transformation: this only holds if a'/a is a fourth power in GF(q). | transformation: this only holds if a'/a is a fourth power in GF(q) | |||

However, even in this case, one can still express the curve W_{a,b} | (see Section 3.1.5 of [GECC]). However, even in this case, one can | |||

in terms of a Weierstrass curve with a small a' domain parameter, | still express the curve W_{a,b} as a Weierstrass curve with a small | |||

thereby still allowing a more efficient implementation than with a | domain parameter value a', thereby still allowing a more efficient | |||

general a value. | implementation than with a general domain parameter value a. | |||

E.2. Isogeneous Mapping between Weierstrass Curves | F.2. Isogenous Mapping between Weierstrass Curves | |||

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

of the Weierstrass curve W_{a',b'}, where a':=-3 (mod p), even if | of the Weierstrass curve W_{a',b'}, where a':=-3 (mod p), even if | |||

a'/a is not a fourth power in GF(q). In that case, this mappping | a'/a is not a fourth power in GF(q). In that case, this mappping | |||

cannot be an isomorphism (see Appendix E.1) and, thereby, does not | cannot be an isomorphism (see Appendix F.1). Instead, the mapping is | |||

define a one-to-one correspondence. Instead, the mapping is a so- | a so-called isogeny (or homomorphism). Since most elliptic curve | |||

called isogeny (or homomorphism). Since most elliptic curve | ||||

operations process points of prime order or use so-called "co-factor | operations process points of prime order or use so-called "co-factor | |||

multiplication", in practice the resulting mapping has similar | multiplication", in practice the resulting mapping has similar | |||

properties. In particular, one can still take advantage of this | properties as an isomorphism. In particular, one can still take | |||

mapping to carry out elliptic curve group operations originally | advantage of this mapping to carry out elliptic curve group | |||

defined for a Weierstrass curve with domain parameter a unequal to -3 | operations originally defined for a Weierstrass curve with domain | |||

(mod p) on a corresponding isogenous Weierstrass curve with domain | parameter a unequal to -3 (mod p) on a corresponding isogenous | |||

parameter a'=-3 (mod p) and translating the result back to the | Weierstrass curve with domain parameter a'=-3 (mod p) and translating | |||

original curve. | the result back to the original curve. | |||

In this case, the mapping from W_{a,b} to W_{a',b'} is defined by | In this case, the mapping from W_{a,b} to W_{a',b'} is defined by | |||

mapping the point at infinity O of W_{a,b} to the point at infinity O | mapping the point at infinity O of W_{a,b} to the point at infinity O | |||

of W_{a',b'}, while mapping each other point (x, y) of W_{a,b} to the | of W_{a',b'}, while mapping each other point (x, y) of W_{a,b} to the | |||

point (x', y'):=(u(x)/w(x)^2, y*v(x)/w(x)^3) of W_{a',b'}. Here, | point (x', y'):=(u(x)/w(x)^2, y*v(x)/w(x)^3) of W_{a',b'}. Here, | |||

u(x), v(x), and w(x) are polynomials that depend on the isogeny in | u(x), v(x), and w(x) are polynomials that depend on the isogeny in | |||

question. The inverse mapping from W_{a',b'} to W_{a,b} is again an | question. The inverse mapping from W_{a',b'} to W_{a,b} is again an | |||

isogeny and defined by mapping the point at infinity O of W_{a',b'} | isogeny and defined by mapping the point at infinity O of W_{a',b'} | |||

to the point at infinity O of W_{a,b}, while mapping each other point | to the point at infinity O of W_{a,b}, while mapping each other point | |||

(x', y') of W_{a',b'} to the point (x, y):=(u'(x')/w'(x')^2, | (x', y') of W_{a',b'} to the point (x, y):=(u'(x')/w'(x')^2, | |||

y'*v'(x')/w'(x')^3) of W_{a,b}, where -- again -- u'(x'), v'(x'), and | y'*v'(x')/w'(x')^3) of W_{a,b}, where -- again -- u'(x'), v'(x'), and | |||

w'(x') are polynomials that depend on the isogeny in question. These | w'(x') are polynomials that depend on the isogeny in question. These | |||

mappings have the property that their composition is not the identity | mappings have the property that their composition is not the identity | |||

mapping (as is the case with the isomorphic mappings discussed in | mapping (as is the case with the isomorphic mappings discussed in | |||

Appendix E.1), but rather a fixed multiple hereof: if this multiple | Appendix F.1), but rather a fixed multiple hereof: if this multiple | |||

is l then the isogeny is called an isogeny of degree l (or l-isogeny) | is l then the isogeny is called an isogeny of degree l (or l-isogeny) | |||

and u, v, and w (and, similarly, u', v', and w') are polynomials of | and u, v, and w (and, similarly, u', v', and w') are polynomials of | |||

degrees l, 3(l-1)/2, and (l-1)/2, respectively. Note that an | degrees l, 3(l-1)/2, and (l-1)/2, respectively. Note that an | |||

isomorphism is simply an isogeny of degree l=1. Details of how to | isomorphism is simply an isogeny of degree l=1. Details of how to | |||

compute this mapping are outside scope of this document (for this, | determine isogenies are outside scope of this document (for this, | |||

contact the author of this document). | contact the author of this document). | |||

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 isogeneous | 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 B.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 | |||

[RFC5639] are isomorphic to a Weierstrass curve of this form, this | [RFC5639] are isomorphic to a Weierstrass curve of this form, this | |||

allows taking advantage of existing generic implementations for these | allows taking advantage of existing implementations for these curves | |||

curves, provided one switches back and forth to this curve form using | that may have a hardcoded a=-3 (mod p) domain parameter, provided one | |||

the isogeneous mapping in question. | switches back and forth to this curve form using the isogenous | |||

mapping in question. | ||||

Note that isogeneous mappings can be easily realized in projective | Note that isogenous mappings can be easily realized in projective | |||

coordinates and involves roughly 3*l finite field multiplications, | coordinates and involves roughly 3*l finite field multiplications, | |||

thus allowing switching between alternative representations at | thus allowing switching between alternative representations at | |||

relative low incremental cost compared to that of elliptic curve | relative low incremental cost compared to that of elliptic curve | |||

scalar multiplications (provided the isogeny has low degree l). | scalar multiplications (provided the isogeny has low degree l). | |||

Note, however, that this does require storage of the polynomial | Note, however, that this does require storage of the polynomial | |||

coefficients of the isogeny and dual isogeny involved. This | coefficients of the isogeny and dual isogeny involved. This | |||

illustrates that low-degree isogenies are to be preferred, since an | illustrates that low-degree isogenies are to be preferred, since an | |||

l-isogeny (usually) requires storing roughly 6*l elements of GF(q). | l-isogeny (usually) requires storing roughly 6*l elements of GF(q). | |||

While there are many isogenies, we therefore only consider those with | While there are many isogenies, we therefore only consider those with | |||

the desired property with lowest possible degree. | the desired property with lowest possible degree. | |||

Appendix F. Further Cousins of Curve25519 | Appendix G. Further Cousins of Curve25519 | |||

F.1. Further Alternative Representations | G.1. Further Alternative Representations | |||

The Weierstrass curve Wei25519 is isomorphic to the Weierstrass curve | The Weierstrass curve Wei25519 is isomorphic to the Weierstrass curve | |||

Wei25519.2 defined over GF(p), with as base point the pair (G1x,G1y), | Wei25519.2 defined over GF(p), with as base point the pair | |||

and isogeneous to the Weierstrass curve Wei25519.-3 defined over | (G1x',G1y'), and isogenous to the Weierstrass curve Wei25519.-3 | |||

GF(p), with as base point the pair (G2x, G2y), where parameters are | defined over GF(p), with as base point the pair (G2x', G2y'), where | |||

as specified in Appendix F.3 and where the related mappings are as | parameters are as specified in Appendix G.3 and where the related | |||

specified in Appendix F.2. | mappings are as specified in Appendix G.2. | |||

F.2. Further Switching | G.2. Further Switching | |||

Each affine point (x,y) of Wei25519 corresponds to the point | Each affine point (x,y) of Wei25519 corresponds to the point | |||

(x',y'):=(x*s^2,y*s^3) of Wei25519.2, where s is the element of GF(p) | (x',y'):=(x*s^2,y*s^3) of Wei25519.2, where s is the element of GF(p) | |||

defined by | defined by | |||

s 20343593038935618591794247374137143598394058341193943326473831977 | s 20343593038935618591794247374137143598394058341193943326473831977 | |||

39407761440 | 39407761440 | |||

(=0x047f6814 6d568b44 7e4552ea a5ed633d 02d62964 a2b0a120 | (=0x047f6814 6d568b44 7e4552ea a5ed633d 02d62964 a2b0a120 | |||

5e7941e9 375de020), | 5e7941e9 375de020), | |||

while the point at infinity of Wei25519 corresponds to the point at | while the point at infinity of Wei25519 corresponds to the point at | |||

infinity of Wei25519.2. (Here, we used the mapping of Appendix E.1.) | infinity of Wei25519.2. (Here, we used the mapping of Appendix F.1.) | |||

Under this mapping, the base point (Gx',Gy') of Wei25519 corresponds | Under this mapping, the base point (Gx',Gy') of Wei25519 corresponds | |||

to the base point (G1x',G1y') of Wei25519.2. The inverse mapping | to the base point (G1x',G1y') of Wei25519.2. The inverse mapping | |||

maps the affine point (x',y') of Wei25519.2 to (x,y):=(x'/s^2,y'/s^3) | maps the affine point (x',y') of Wei25519.2 to (x,y):=(x'/s^2,y'/s^3) | |||

of Wei25519, while mapping the point at infinity of Wei25519.2 to the | of Wei25519, while mapping the point at infinity of Wei25519.2 to the | |||

point at infinity of Wei25519. Note that this mapping (and its | point at infinity of Wei25519. Note that this mapping (and its | |||

inverse) involves a modular multiplication of both coordinates with | inverse) involves a modular multiplication of both coordinates with | |||

fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which | fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which | |||

can be precomputed. | can be precomputed. | |||

Each affine point (x,y) of Wei25519 corresponds to the point | Each affine point (x,y) of Wei25519 corresponds to the point | |||

(x',y'):=(x1/t^2,y1/t^3) of Wei25519.-3, where | (x',y'):=(x1/t^2,y1/t^3) of Wei25519.-3, where | |||

(x1,y1)=(u(x)/w(x)^2,y*v(x)/w(x)^3), where u, v, and w are the | (x1,y1)=(u(x)/w(x)^2,y*v(x)/w(x)^3), where u, v, and w are the | |||

polynomials with coefficients in GF(p) as defined in Appendix G and | polynomials with coefficients in GF(p) as defined in Appendix H.1 and | |||

where t is the element of GF(p) defined by | where t is the element of GF(p) defined by | |||

t 26012855558634277483276064234565597076862996895623795164528458073 | t 26012855558634277483276064234565597076862996895623795164528458073 | |||

435568115620 | 435568115620 | |||

(=0x3982c126 59ad1749 ab8bc495 bb1a9d64 c9deffc5 e7b8e601 | (=0x3982c126 59ad1749 ab8bc495 bb1a9d64 c9deffc5 e7b8e601 | |||

a5651992 07d48fa4), | a5651992 07d48fa4), | |||

while the point at infinity of Wei25519 corresponds to the point at | while the point at infinity of Wei25519 corresponds to the point at | |||

infinity of Wei25519.-3. (Here, we used the isogeneous mapping of | infinity of Wei25519.-3. (Here, we used the isogenous mapping of | |||

Appendix E.2.) Under this isogeneous mapping, the base point | Appendix F.2.) Under this isogenous mapping, the base point | |||

(Gx',Gy') of Wei25519 corresponds to the base point (G2x',G2y') of | (Gx',Gy') of Wei25519 corresponds to the base point (G2x',G2y') of | |||

Wei25519.-3. The dual isogeny maps the affine point (x',y') of | Wei25519.-3. The dual isogeny maps the affine point (x',y') of | |||

Wei25519.-3 to to (x,y):=(u'(x1)/w'(x1)^2,y1*v'(x1)/w'(x1)^3) of | Wei25519.-3 to to (x,y):=(u'(x1)/w'(x1)^2,y1*v'(x1)/w'(x1)^3) of | |||

Wei25519, where (x1,y1)=(x'*t^2,y'*t^3) and where u', v', and w' are | Wei25519, where (x1,y1)=(x'*t^2,y'*t^3) and where u', v', and w' are | |||

the polynomials with coefficients in GF(p) as defined in Appendix G, | the polynomials with coefficients in GF(p) as defined in | |||

while mapping the point at infinity of Wei25519.-3 to the point at | Appendix H.2, while mapping the point at infinity of Wei25519.-3 to | |||

infinity of Wei25519. Under this dual isogeneous mapping, the base | the point at infinity of Wei25519. Under this dual isogenous | |||

point (G2x',G2y') of Wei25519.-3 corresponds to a multiple of the | mapping, the base point (G2x',G2y') of Wei25519.-3 corresponds to a | |||

base point (Gx',Gy') of Wei25519, where this multiple is l=47 (the | multiple of the base point (Gx',Gy') of Wei25519, where this multiple | |||

degree of the isogeny; see the description in Appendix E.1). Note | is l=47 (the degree of the isogeny; see the description in | |||

that this isogenous map (and its dual) primarily involves the | Appendix F.1). Note that this isogenous map (and its dual) primarily | |||

evaluation of three fixed polynomials involving the x-coordinate, | involves the evaluation of three fixed polynomials involving the | |||

which takes roughly 140 modular multiplications (or less than 5% | x-coordinate, which takes roughly 140 modular multiplications (or | |||

relative incremental cost compared to the cost of an elliptic curve | less than 5-10% relative incremental cost compared to the cost of an | |||

scalar multiplication). | elliptic curve scalar multiplication). | |||

F.3. Further Domain Parameters | G.3. Further Domain Parameters | |||

The parameters of the Weierstrass curve with a=2 that is isomorphic | The parameters of the Weierstrass curve with a=2 that is isomorphic | |||

with Wei25519 and the parameters of the Weierstrass curve with a=-3 | with Wei25519 and the parameters of the Weierstrass curve with a=-3 | |||

that is isogeneous with Wei25519 are as indicated below. Both domain | that is isogenous with Wei25519 are as indicated below. Both domain | |||

parameter sets can be exploited directly to derive more efficient | parameter sets can be exploited directly to derive more efficient | |||

point addition formulae, should an implementation facilitate this. | point addition formulae, should an implementation facilitate this. | |||

General parameters: same as for Wei25519 (see Appendix E.3) | ||||

Weierstrass curve-specific parameters (for Wei25519.2, i.e., with | Weierstrass curve-specific parameters (for Wei25519.2, i.e., with | |||

a=2): | a=2): | |||

a 2 (=0x02) | a 2 (=0x02) | |||

b 12102640281269758552371076649779977768474709596484288167752775713 | b 12102640281269758552371076649779977768474709596484288167752775713 | |||

178787220689 | 178787220689 | |||

(=0x1ac1da05 b55bc146 33bd39e4 7f94302e f19843dc f669916f | (=0x1ac1da05 b55bc146 33bd39e4 7f94302e f19843dc f669916f | |||

6a5dfd01 65538cd1) | 6a5dfd01 65538cd1) | |||

skipping to change at page 19, line 4 ¶ | skipping to change at page 24, line 21 ¶ | |||

796e1022 40891faa) | 796e1022 40891faa) | |||

G2x' 538371792299408724349427232574807773704511272123391981336972078 | G2x' 538371792299408724349427232574807773704511272123391981336972078 | |||

46219400243292 | 46219400243292 | |||

(=0x7706c37b 5a84128a 3884a5d7 1811f1b5 5da3230f fb17a8ab | (=0x7706c37b 5a84128a 3884a5d7 1811f1b5 5da3230f fb17a8ab | |||

0b32e48d 31a6685c) | 0b32e48d 31a6685c) | |||

G2y' 695480730911001844144020555292799703925148674228551417730708041 | G2y' 695480730911001844144020555292799703925148674228551417730708041 | |||

8460388229929 | 8460388229929 | |||

(=0x0f60480c 7a5c0e11 40340adc 79d6a2bf 0cb57ad0 49d025dc | (=0x0f60480c 7a5c0e11 40340adc 79d6a2bf 0cb57ad0 49d025dc | |||

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

Appendix G. Isogeny Details | Appendix H. 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.1 (for the isogeny) and in Appendix G.2 (for the dual | in Appendix H.1 (for the isogeny) and in Appendix H.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 sequence of coefficients of x^0, x^1, x^2, ..., in | |||

hexadecimal format. | hexadecimal format. | |||

G.1. Isogeny Parameters | H.1. Isogeny Parameters | |||

G.1.1. Coefficients of u(x): | H.1.1. Coefficients of u(x) | |||

0 0x670ed14828b6f1791ceb3a9cc0edfe127dee8729c5a72ddf77bb1abaebbba1e8 | 0 0x670ed14828b6f1791ceb3a9cc0edfe127dee8729c5a72ddf77bb1abaebbba1e8 | |||

1 0x1135ca8bd5383cb3545402c8bce2ced14b45c29b241e4751b035f27524a9f932 | 1 0x1135ca8bd5383cb3545402c8bce2ced14b45c29b241e4751b035f27524a9f932 | |||

2 0x3223806ff5f669c430efd74df8389f058d180e2fcffa5cdef3eacecdd2c34771 | 2 0x3223806ff5f669c430efd74df8389f058d180e2fcffa5cdef3eacecdd2c34771 | |||

3 0x31b8fecf3f17a819c228517f6cd9814466c8c8bea2efccc47a29bfc14c364266 | 3 0x31b8fecf3f17a819c228517f6cd9814466c8c8bea2efccc47a29bfc14c364266 | |||

4 0x2541305c958c5a326f44efad2bec284e7abee840fadb08f2d994cd382fd8ce42 | 4 0x2541305c958c5a326f44efad2bec284e7abee840fadb08f2d994cd382fd8ce42 | |||

skipping to change at page 21, line 22 ¶ | skipping to change at page 26, line 40 ¶ | |||

43 0x573453fb2b093016f3368356c786519d54ed05f5372c01723b4da520597ec217 | 43 0x573453fb2b093016f3368356c786519d54ed05f5372c01723b4da520597ec217 | |||

44 0x77f5c605bdb3a30d7d9c8840fce38650910d4418eed707a212c8927f41c2c812 | 44 0x77f5c605bdb3a30d7d9c8840fce38650910d4418eed707a212c8927f41c2c812 | |||

45 0x16d6b9f7ff57ca32350057de1204cc6d69d4ef1b255dfef8080118e2fef6ace3 | 45 0x16d6b9f7ff57ca32350057de1204cc6d69d4ef1b255dfef8080118e2fef6ace3 | |||

46 0x34e8595832a4021f8b5744014c6b4f7da7df0d0329e8b6b4d44c8fadad6513b7 | 46 0x34e8595832a4021f8b5744014c6b4f7da7df0d0329e8b6b4d44c8fadad6513b7 | |||

47 0x1 | 47 0x1 | |||

G.1.2. Coefficients of v(x): | H.1.2. Coefficients of v(x) | |||

0 0xf9f5eb7134e6f8dafa30c45afa58d7bfc6d4e3ccbb5de87b562fd77403972b2 | 0 0xf9f5eb7134e6f8dafa30c45afa58d7bfc6d4e3ccbb5de87b562fd77403972b2 | |||

1 0x36c2dcd9e88f0d2d517a15fc453a098bbbb5a05eb6e8da906fae418a4e1a13f7 | 1 0x36c2dcd9e88f0d2d517a15fc453a098bbbb5a05eb6e8da906fae418a4e1a13f7 | |||

2 0xb40078302c24fa394a834880d5bf46732ca1b4894172fb7f775821276f558b3 | 2 0xb40078302c24fa394a834880d5bf46732ca1b4894172fb7f775821276f558b3 | |||

3 0x53dd8e2234573f7f3f7df11e90a7bdd7b75d807f9712f521d4fb18af59aa5f26 | 3 0x53dd8e2234573f7f3f7df11e90a7bdd7b75d807f9712f521d4fb18af59aa5f26 | |||

4 0x6d4d7bb08de9061988a8cf6ff3beb10e933d4d2fbb8872d256a38c74c8c2ceda | 4 0x6d4d7bb08de9061988a8cf6ff3beb10e933d4d2fbb8872d256a38c74c8c2ceda | |||

skipping to change at page 24, line 20 ¶ | skipping to change at page 29, line 38 ¶ | |||

65 0x537f58d52d18ce5b1d5a6bd3a420e796e64173491ad43dd4d1083a7dcc7dd201 | 65 0x537f58d52d18ce5b1d5a6bd3a420e796e64173491ad43dd4d1083a7dcc7dd201 | |||

66 0x49c2f6afa93fdcc4e0f8128a8b06da4c75049be14edf3e103821ab604c60f8ae | 66 0x49c2f6afa93fdcc4e0f8128a8b06da4c75049be14edf3e103821ab604c60f8ae | |||

67 0x10a333eabd6135aeaa3f5f5f7e73d102e4fd7e4bf0902fc55b00da235fa1ad08 | 67 0x10a333eabd6135aeaa3f5f5f7e73d102e4fd7e4bf0902fc55b00da235fa1ad08 | |||

68 0xf5c86044bf6032f5102e601f2a0f73c7bce9384bedd120f3e72d78484179d9c | 68 0xf5c86044bf6032f5102e601f2a0f73c7bce9384bedd120f3e72d78484179d9c | |||

69 0x1 | 69 0x1 | |||

G.1.3. Coefficients of w(x): | H.1.3. Coefficients of w(x) | |||

0 0x3da24d42421264f30939ff00203880f2b017eb3fecf8933ae61e18df8c8ba116 | 0 0x3da24d42421264f30939ff00203880f2b017eb3fecf8933ae61e18df8c8ba116 | |||

1 0x457f20bc393cdc9a66848ce174e2fa41d77e6dbae05a317a1fb6e3ae78760f8 | 1 0x457f20bc393cdc9a66848ce174e2fa41d77e6dbae05a317a1fb6e3ae78760f8 | |||

2 0x7f608a2285c480d5c9592c435431fae94695beef79d770bb6d029c1d10a53295 | 2 0x7f608a2285c480d5c9592c435431fae94695beef79d770bb6d029c1d10a53295 | |||

3 0x3832accc520a485100a0a1695792465142a5572bed1b2e50e1f8f662ac7289bb | 3 0x3832accc520a485100a0a1695792465142a5572bed1b2e50e1f8f662ac7289bb | |||

4 0x2df1b0559e31b328eb34beedd5e537c3f4d7b9befb0749f75d6d0d866d26fbaa | 4 0x2df1b0559e31b328eb34beedd5e537c3f4d7b9befb0749f75d6d0d866d26fbaa | |||

skipping to change at page 25, line 22 ¶ | skipping to change at page 30, line 40 ¶ | |||

19 0x33e4cab64ed8a00d8012104fe8f928e6173c428eff95bbbe569ea46126a4f3cd | 19 0x33e4cab64ed8a00d8012104fe8f928e6173c428eff95bbbe569ea46126a4f3cd | |||

20 0x50555b6f07e308d33776922b6566829d122e19b25b7bbacbb0a4b1a7dc40192 | 20 0x50555b6f07e308d33776922b6566829d122e19b25b7bbacbb0a4b1a7dc40192 | |||

21 0x533fa4bf1e2a2aae2f979065fdbb5b667ede2f85543fddbba146aa3a4ef2d281 | 21 0x533fa4bf1e2a2aae2f979065fdbb5b667ede2f85543fddbba146aa3a4ef2d281 | |||

22 0x5a742cac1952010fc5aba200a635a7bed3ef868194f45b5a6a2647d6d6b289d2 | 22 0x5a742cac1952010fc5aba200a635a7bed3ef868194f45b5a6a2647d6d6b289d2 | |||

23 0x1 | 23 0x1 | |||

G.2. Dual Isogeny Parameters | H.2. Dual Isogeny Parameters | |||

G.2.1. Coefficients of u'(x): | H.2.1. Coefficients of u'(x) | |||

0 0xf0eddb584a20aaac8f1419efdd02a5cca77b21e4cfae78c49b5127d98bc5882 | 0 0xf0eddb584a20aaac8f1419efdd02a5cca77b21e4cfae78c49b5127d98bc5882 | |||

1 0x7115e60d44a58630417df33dd45b8a546fa00b79fea3b2bdc449694bade87c0a | 1 0x7115e60d44a58630417df33dd45b8a546fa00b79fea3b2bdc449694bade87c0a | |||

2 0xb3f3a6f3c445c7dc1f91121275414e88c32ff3f367ba0edad4d75b7e7b94b65 | 2 0xb3f3a6f3c445c7dc1f91121275414e88c32ff3f367ba0edad4d75b7e7b94b65 | |||

3 0x1eb31bb333d7048b87f2b3d4ec76d69035927b41c30274368649c87c52e1ab30 | 3 0x1eb31bb333d7048b87f2b3d4ec76d69035927b41c30274368649c87c52e1ab30 | |||

4 0x552c886c2044153e280832264066cce2a7da1127dc9720e2a380e9d37049ac64 | 4 0x552c886c2044153e280832264066cce2a7da1127dc9720e2a380e9d37049ac64 | |||

5 0x4504f27908db2e1f5840b74ae42445298755d9493141f5417c02f04d47797dda | 5 0x4504f27908db2e1f5840b74ae42445298755d9493141f5417c02f04d47797dda | |||

6 0x82c242cce1eb19698a4fa30b5affe64e5051c04ae8b52cb68d89ee85222e628 | 6 0x82c242cce1eb19698a4fa30b5affe64e5051c04ae8b52cb68d89ee85222e628 | |||

7 0x480473406add76cf1d77661b3ff506c038d9cdd5ad6e1ea41969430bb876d223 | 7 0x480473406add76cf1d77661b3ff506c038d9cdd5ad6e1ea41969430bb876d223 | |||

8 0x25f47bb506fba80c79d1763365fa9076d4c4cb6644f73ed37918074397e88588 | 8 0x25f47bb506fba80c79d1763365fa9076d4c4cb6644f73ed37918074397e88588 | |||

skipping to change at page 27, line 26 ¶ | skipping to change at page 32, line 44 ¶ | |||

43 0x5a9d104ae585b94af68eeb16b1349776b601f97b7ce716701645b1a75b68dcf3 | 43 0x5a9d104ae585b94af68eeb16b1349776b601f97b7ce716701645b1a75b68dcf3 | |||

44 0x754e014b5e87af035b3d5fe6fb49f4631e32549f6341c6693c5172a6388e273e | 44 0x754e014b5e87af035b3d5fe6fb49f4631e32549f6341c6693c5172a6388e273e | |||

45 0x6710d8265118e22eaceba09566c86f642ab42da58c435083a353eaa12d866c39 | 45 0x6710d8265118e22eaceba09566c86f642ab42da58c435083a353eaa12d866c39 | |||

46 0x6e88ac659ce146c369f8b24c3a49f8dca547827250cf7963a455851cfc4f8d22 | 46 0x6e88ac659ce146c369f8b24c3a49f8dca547827250cf7963a455851cfc4f8d22 | |||

47 0x971eb5f253356cd1fde9fb21f4a4902aa5b8d804a2b57ba775dc130181ae2e8 | 47 0x971eb5f253356cd1fde9fb21f4a4902aa5b8d804a2b57ba775dc130181ae2e8 | |||

G.2.2. Coefficients of v'(x): | H.2.2. Coefficients of v'(x) | |||

0 0x43c9b67cc5b16e167b55f190db61e44d48d813a7112910f10e3fd8da85d61d3 | 0 0x43c9b67cc5b16e167b55f190db61e44d48d813a7112910f10e3fd8da85d61d3 | |||

1 0x72046db07e0e7882ff3f0f38b54b45ca84153be47a7fd1dd8f6402e17c47966f | 1 0x72046db07e0e7882ff3f0f38b54b45ca84153be47a7fd1dd8f6402e17c47966f | |||

2 0x1593d97b65a070b6b3f879fe3dc4d1ef03c0e781c997111d5c1748f956f1ffc0 | 2 0x1593d97b65a070b6b3f879fe3dc4d1ef03c0e781c997111d5c1748f956f1ffc0 | |||

3 0x54e5fec076b8779338432bdc5a449e36823a0a7c905fd37f232330b026a143a0 | 3 0x54e5fec076b8779338432bdc5a449e36823a0a7c905fd37f232330b026a143a0 | |||

4 0x46328dd9bc336e0873abd453db472468393333fbf2010c6ac283933216e98038 | 4 0x46328dd9bc336e0873abd453db472468393333fbf2010c6ac283933216e98038 | |||

5 0x25d0c64de1dfe1c6d5f5f2d98ab637d8b39bcf0d886a23dabac18c80d7eb03ce | 5 0x25d0c64de1dfe1c6d5f5f2d98ab637d8b39bcf0d886a23dabac18c80d7eb03ce | |||

6 0x3a175c46b2cd8e2b313dde2d5f3097b78114a6295f283cf58a33844b0c8d8b34 | 6 0x3a175c46b2cd8e2b313dde2d5f3097b78114a6295f283cf58a33844b0c8d8b34 | |||

7 0x5cf4e6f745bdd61181a7d1b4db31dc4c30c84957f63cdf163bee5e466a7a8d38 | 7 0x5cf4e6f745bdd61181a7d1b4db31dc4c30c84957f63cdf163bee5e466a7a8d38 | |||

skipping to change at page 30, line 24 ¶ | skipping to change at page 35, line 42 ¶ | |||

65 0x3468cf6df7e93f7ff1fe1dd7e180a89dec3ed4f72843b4ea8a8d780011a245b2 | 65 0x3468cf6df7e93f7ff1fe1dd7e180a89dec3ed4f72843b4ea8a8d780011a245b2 | |||

66 0x68f75a0e2210f52a90704ed5f511918d1f6bcfcd26b462cc4975252369db6e9d | 66 0x68f75a0e2210f52a90704ed5f511918d1f6bcfcd26b462cc4975252369db6e9d | |||

67 0x6220c0699696e9bcab0fe3a80d437519bd2bdf3caef665e106b2dd47585ddd9f | 67 0x6220c0699696e9bcab0fe3a80d437519bd2bdf3caef665e106b2dd47585ddd9f | |||

68 0x553ad47b129fb347992b576479b0a89f8d71f1196f83e5eaab5f533a1dd6f6d7 | 68 0x553ad47b129fb347992b576479b0a89f8d71f1196f83e5eaab5f533a1dd6f6d7 | |||

69 0x239aef387e116ec8730fa15af053485ca707650d9f8917a75f22acf6213197df | 69 0x239aef387e116ec8730fa15af053485ca707650d9f8917a75f22acf6213197df | |||

G.2.3. Coefficients of w'(x): | H.2.3. Coefficients of w'(x) | |||

0 0x6bd7f1fc5dd51b7d832848c180f019bcbdb101d4b3435230a79cc4f95c35e15e | 0 0x6bd7f1fc5dd51b7d832848c180f019bcbdb101d4b3435230a79cc4f95c35e15e | |||

1 0x17413bb3ee505184a504e14419b8d7c8517a0d268f65b0d7f5b0ba68d6166dd0 | 1 0x17413bb3ee505184a504e14419b8d7c8517a0d268f65b0d7f5b0ba68d6166dd0 | |||

2 0x47f4471beed06e5e2b6d5569c20e30346bdba2921d9676603c58e55431572f90 | 2 0x47f4471beed06e5e2b6d5569c20e30346bdba2921d9676603c58e55431572f90 | |||

3 0x2af7eaafd04f6910a5b01cdb0c27dca09487f1cd1116b38db34563e7b0b414eb | 3 0x2af7eaafd04f6910a5b01cdb0c27dca09487f1cd1116b38db34563e7b0b414eb | |||

4 0x57f0a593459732eef11d2e2f7085bf9adf534879ba56f7afd17c4a40d3d3477b | 4 0x57f0a593459732eef11d2e2f7085bf9adf534879ba56f7afd17c4a40d3d3477b | |||

5 0x4da04e912f145c8d1e5957e0a9e44cca83e74345b38583b70840bdfdbd0288ed | 5 0x4da04e912f145c8d1e5957e0a9e44cca83e74345b38583b70840bdfdbd0288ed | |||

6 0x7cc9c3a51a3767d9d37c6652c349adc09bfe477d99f249a2a7bc803c1c5f39ed | 6 0x7cc9c3a51a3767d9d37c6652c349adc09bfe477d99f249a2a7bc803c1c5f39ed | |||

7 0x425d7e58b8adf87eebf445b424ba308ee7880228921651995a7eab548180ad49 | 7 0x425d7e58b8adf87eebf445b424ba308ee7880228921651995a7eab548180ad49 | |||

8 0x48156db5c99248234c09f43fedf509005943d3d5f5d7422621617467b06d314f | 8 0x48156db5c99248234c09f43fedf509005943d3d5f5d7422621617467b06d314f | |||

End of changes. 95 change blocks. | ||||

213 lines changed or deleted | | 462 lines changed or added | ||

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