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

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

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

Intended status: Informational March 23, 2019 | Intended status: Informational April 19, 2019 | |||

Expires: September 24, 2019 | Expires: October 21, 2019 | |||

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

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

Abstract | Abstract | |||

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

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

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

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

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

Requirements Language | Requirements Language | |||

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

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

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

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

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

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

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

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

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

This Internet-Draft will expire on September 24, 2019. | This Internet-Draft will expire on October 21, 2019. | |||

Copyright Notice | Copyright Notice | |||

Copyright (c) 2019 IETF Trust and the persons identified as the | Copyright (c) 2019 IETF Trust and the persons identified as the | |||

document authors. All rights reserved. | document authors. All rights reserved. | |||

This document is subject to BCP 78 and the IETF Trust's Legal | This document is subject to BCP 78 and the IETF Trust's Legal | |||

Provisions Relating to IETF Documents | Provisions Relating to IETF Documents | |||

(https://trustee.ietf.org/license-info) in effect on the date of | (https://trustee.ietf.org/license-info) in effect on the date of | |||

publication of this document. Please review these documents | publication of this document. Please review these documents | |||

skipping to change at page 2, line 23 ¶ | skipping to change at page 2, line 23 ¶ | |||

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

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

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

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

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

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

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

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

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

6. Security Considerations . . . . . . . . . . . . . . . . . . . 8 | 6. Security Considerations . . . . . . . . . . . . . . . . . . . 9 | |||

7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 9 | 7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 9 | |||

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

8.1. COSE Elliptic Curves Registration . . . . . . . . . . . . 9 | 8.1. COSE Elliptic Curves Registration . . . . . . . . . . . . 10 | |||

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

8.3. COSE Algorithms Registration (2/2) . . . . . . . . . . . 10 | 8.3. COSE Algorithms Registration (2/2) . . . . . . . . . . . 11 | |||

9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11 | 8.4. JOSE Elliptic Curves Registration . . . . . . . . . . . . 11 | |||

10. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 | 8.5. JOSE Algorithms Registration (1/2) . . . . . . . . . . . 11 | |||

10.1. Normative References . . . . . . . . . . . . . . . . . . 11 | 8.6. JOSE Algorithms Registration (2/2) . . . . . . . . . . . 12 | |||

10.2. Informative References . . . . . . . . . . . . . . . . . 12 | 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 12 | |||

Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 13 | 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 12 | |||

A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 13 | 10.1. Normative References . . . . . . . . . . . . . . . . . . 12 | |||

A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 13 | 10.2. Informative References . . . . . . . . . . . . . . . . . 13 | |||

A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 13 | Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 15 | |||

Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 14 | A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 15 | |||

B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 14 | A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 15 | |||

B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 15 | A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 15 | |||

Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 16 | Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 16 | |||

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

C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 17 | B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 17 | |||

C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 18 | Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 18 | |||

Appendix D. Relationship Between Curve Models . . . . . . . . . 19 | C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 18 | |||

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

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

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

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

Curves . . . . . . . . . . . . . . . . . . . . . . . . . 19 | ||||

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

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

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

Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 21 | D.2. Mapping between Montgomery Curves and Weierstrass Curves 22 | |||

E.1. Curve Definition and Alternative Representations . . . . 21 | D.3. Mapping between Twisted Edwards Curves and Weierstrass | |||

E.2. Switching between Alternative Representations . . . . . . 21 | Curves . . . . . . . . . . . . . . . . . . . . . . . . . 23 | |||

E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 23 | Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 23 | |||

Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 25 | E.1. Curve Definition and Alternative Representations . . . . 23 | |||

F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 25 | E.2. Switching between Alternative Representations . . . . . . 23 | |||

F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 26 | E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 25 | |||

F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 26 | Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 27 | |||

F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 27 | F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 27 | |||

Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 29 | F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 28 | |||

G.1. Further Alternative Representations . . . . . . . . . . . 29 | F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 28 | |||

G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 29 | F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 29 | |||

G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 30 | Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 31 | |||

Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 31 | G.1. Further Alternative Representations . . . . . . . . . . . 31 | |||

H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 31 | G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 31 | |||

H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 31 | G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 32 | |||

H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 34 | Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 33 | |||

H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 37 | H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 33 | |||

H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 38 | H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 33 | |||

H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 38 | H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 36 | |||

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

H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 43 | H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 40 | |||

Appendix I. Point Compression . . . . . . . . . . . . . . . . . 44 | H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 40 | |||

I.1. Point Compression for Weierstrass Curves . . . . . . . . 44 | H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 42 | |||

I.2. Point Compression for Montgomery Curves . . . . . . . . . 45 | H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 45 | |||

I.3. Point Compression for Twisted Edwards Curves . . . . . . 46 | Appendix I. Point Compression . . . . . . . . . . . . . . . . . 46 | |||

Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 46 | I.1. Point Compression for Weierstrass Curves . . . . . . . . 46 | |||

J.1. Conversion between Bit Strings and Integers . . . . . . . 47 | I.2. Point Compression for Montgomery Curves . . . . . . . . . 47 | |||

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

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

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

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

I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 47 | I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 49 | |||

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

OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 48 | OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 50 | |||

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

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

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

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

J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 49 | J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 51 | |||

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

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

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

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

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

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

Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 58 | Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 60 | |||

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

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

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

L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 58 | ||||

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

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

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

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

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

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

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

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

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

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

skipping to change at page 4, line 50 ¶ | skipping to change at page 5, line 4 ¶ | |||

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

respectively; see Appendix G. (Here, p is the characteristic of the | respectively; see Appendix G. (Here, p is the characteristic of the | |||

field over which these curves are defined.) | field over which these curves are defined.) | |||

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

The curves Curve25519, Edwards25519, and Wei25519, as specified in | The curves Curve25519, Edwards25519, and Wei25519, as specified in | |||

Appendix E.3, are all isomorphic, with the transformations of | Appendix E.3, are all isomorphic, with the transformations of | |||

Appendix E.2. These transformations map the specified base point of | Appendix E.2. These transformations map the specified base point of | |||

each of these curves to the specified base point of each of the other | each of these curves to the specified base point of each of the other | |||

curves. Consequently, a public-key pair (k,R:=k*G) for any one of | curves. Consequently, a public-private key pair (k,R:=k*G) for any | |||

these curves corresponds, via these isomorphic mappings, to the | one of these curves corresponds, via these isomorphic mappings, to | |||

public-key pair (k, R':=k*G') for each of these other curves (where G | the public-private key pair (k, R':=k*G') for each of these other | |||

and G' are the corresponding base points of these curves). This | curves (where G and G' are the corresponding base points of these | |||

observation extends to the case where one also considers curve | curves). This observation extends to the case where one also | |||

Wei25519.2 (which has hardcoded domain parameter a=2), as specified | considers curve Wei25519.2 (which has hardcoded domain parameter | |||

in Appendix G.3, since it is isomorphic to Wei25519, with the | a=2), as specified in Appendix G.3, since it is isomorphic to | |||

transformation of Appendix G.2, and, thereby, also isomorphic to | Wei25519, with the transformation of Appendix G.2, and, thereby, also | |||

Curve25519 and Edwards25519. | isomorphic to Curve25519 and Edwards25519. | |||

The curve Wei25519.-3 (which has hardcoded domain parameter a=-3 (mod | 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 | p)) is not isomorphic to the curve Wei25519, but is related in a | |||

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

Wei25519.-3, where the mapping of Appendix G.2 is an isogeny of | 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 | 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 | specified base point G' of Wei25519.-3 and where the so-called dual | |||

isogeny (which maps Wei25519.-3 to Wei25519) has the same degree | 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 | 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) | this multiple is l=47. Consequently, a public-private key pair | |||

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

Wei25519.-3 (via the l-isogeny), whereas the public-key pair (k, | (k, R':= k*G') for Wei25519.-3 (via the l-isogeny), whereas the | |||

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

Wei25519 (via the dual isogeny). (Note the extra scalar l=47 here.) | private 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 | Alternative curve representations can, therefore, be used in any | |||

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

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

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

convert the results back to the original curve (where, in case this | 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). | involves an l-isogeny, one has to take into account the factor l). | |||

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

agreement and key transport schemes. | agreement and key transport schemes. | |||

skipping to change at page 8, line 28 ¶ | skipping to change at page 8, line 32 ¶ | |||

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

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

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

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

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

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

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

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

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

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

field as Curve25519 that is isomorphic to a Weierstrass curve | field as Curve25519 that is isomorphic to a Weierstrass curve | |||

with hardcoded a=-3 parameter is the Montgomery curve M_{A,B} | with hardcoded a=-3 parameter is the Montgomery curve M_{A,B} | |||

with B=1 and A=-1410290 (or, if one wants the base point to still | with B=1 and A=-1410290 (or, if one wants the base point to still | |||

have u-coordinate u=9, with B=1 and A=-3960846). In either case, | have u-coordinate u=9, with B=1 and A=-3960846). In either case, | |||

the resulting curve has the same cryptographic properties as | the resulting curve has the same cryptographic properties as | |||

Curve25519 and the same performance (which relies on A being a | Curve25519 and the same performance (which relies on A being a | |||

3-byte integer, as is the case with the domain parameter A=486662 | 3-byte integer, as is the case with the domain parameter A=486662 | |||

of Curve25519, and using the same special prime p=2^255-19), | of Curve25519, and using the same special prime p=2^255-19), | |||

while at the same time being "Jacobian-friendly" by design. | while at the same time being "Jacobian-friendly" by design. | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

skipping to change at page 9, line 46 ¶ | skipping to change at page 10, line 14 ¶ | |||

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

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

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

this document. | this document. | |||

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

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

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

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

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

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

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

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

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

skipping to change at page 11, line 5 ¶ | skipping to change at page 11, line 22 ¶ | |||

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

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

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

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

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

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

8.4. JOSE Elliptic Curves Registration | ||||

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

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

Curve Name: Wei25519; | ||||

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

JOSE Implementation Requirements: optional; | ||||

Change Controller: IANA; | ||||

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

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

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

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

Algorithm Name: ECDSA25519; | ||||

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

Algorithm Usage Locations: alg; | ||||

JOSE Implementation Requirements: optional; | ||||

Change Controller: IANA; | ||||

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

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

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

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

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

Algorithm Name: ECDH25519; | ||||

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

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

Algorithm Usage Locations: alg; | ||||

Change Controller: IANA; | ||||

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

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

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

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

9. Acknowledgements | 9. Acknowledgements | |||

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

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

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

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

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

10. References | 10. References | |||

10.1. Normative 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. | |||

[IANA.COSE.Algorithms] | ||||

IANA, "COSE Algorithms", IANA, | ||||

https://www.iana.org/assignments/cose/ | ||||

cose.xhtml#algorithms. | ||||

[IANA.COSE.Curves] | ||||

IANA, "COSE Elliptic Curves", IANA, | ||||

https://www.iana.org/assignments/cose/cose.xhtml#elliptic- | ||||

curves. | ||||

[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 12, line 32 ¶ | skipping to change at page 13, line 42 ¶ | |||

[SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0", | [SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0", | |||

Standards for Efficient Cryptography, , June 2009. | Standards for Efficient Cryptography, , June 2009. | |||

[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 3", US Department of Commerce/National Institute | Revision 3", US Department of Commerce/National Institute | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2003. | 2003. | |||

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

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

2004. | 2004. | |||

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

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

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

[IANA.COSE.Algorithms] | ||||

IANA, "COSE Algorithms", IANA, | ||||

https://www.iana.org/assignments/cose/ | ||||

cose.xhtml#algorithms. | ||||

[IANA.COSE.Curves] | ||||

IANA, "COSE Elliptic Curves", IANA, | ||||

https://www.iana.org/assignments/cose/cose.xhtml#elliptic- | ||||

curves. | ||||

[IANA.JOSE.Algorithms] | ||||

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

IANA, | ||||

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

signature-encryption-algorithms. | ||||

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

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

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

elliptic-curve. | ||||

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

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

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

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

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

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

2008. | ||||

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

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

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

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

2008. | 2008. | |||

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

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

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

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

2002. | ||||

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

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

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

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

skipping to change at page 14, line 48 ¶ | skipping to change at page 16, line 50 ¶ | |||

least n. | least n. | |||

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

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

the order of P. This number is called the discrete logarithm of R to | 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 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 | the discrete logarithm of R to the base P for any two points P and R | |||

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

If P is a fixed base point G of the curve, the pair (k, R:=k*G) is | If P is a fixed base point G of the curve, the pair (k, R:=k*G) is | |||

called a public-private key pair, the integer k the private key, and | commonly called a public-private key pair, the integer k the private | |||

the point R the corresponding public key. The private key k can be | key, and the point R the corresponding public key. The private key k | |||

represented as an integer in the interval [0,n-1], where G has order | can be represented as an integer in the interval [0,n-1], where G has | |||

n. | order n. | |||

In this document, a quadratic twist of a curve E defined over a field | In this document, a quadratic twist of a curve E defined over a field | |||

GF(q) is a curve E' related to E, with cardinality |E'|, | GF(q) is a curve E' related to E, with cardinality |E'|, | |||

where |E|+|E'|=2*(q+1). If E is a curve in one of the curve models | where |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 | specified in this document, a quadratic twist of this curve can be | |||

expressed using the same curve model, although (naturally) with its | expressed using the same curve model, although (naturally) with its | |||

own curve parameters. Two curves E and E' defined over a field GF(q) | own curve parameters. Two curves E and E' defined over a field GF(q) | |||

are said to be isogenous if these have the same order and are said to | are said to be isogenous if these have the same order and are said to | |||

be isomorphic if these have the same group structure. Note that | be isomorphic if these have the same group structure. Note that | |||

isomorphic curves have necessarily the same order and are, thus, a | isomorphic curves have necessarily the same order and are, thus, a | |||

special type of isogenous curves. Further details are out of scope. | special type of isogenous curves. Further details are out of scope. | |||

Weierstrass curves can have prime order, whereas Montgomery curves | Weierstrass curves can have prime order, whereas Montgomery curves | |||

and twisted Edwards curves always have an order that is a multiple of | and twisted Edwards curves always have an order that is a multiple of | |||

four (and, thereby, a small subgroup of cardinality four). | four (and, thereby, a small subgroup of cardinality four). | |||

An ordered pair (x, y) whose coordinates are elements of GF(q) can be | An ordered pair (x, y) whose coordinates are elements of GF(q) can be | |||

associated with any ordered triple of the form [x*z: y*z: z], where z | associated with any ordered triple of the form [x*z: y*z: z], where z | |||

is a nonzero element of GF(q), and can be uniquely recovered from | is a nonzero element of GF(q), and can be uniquely recovered from | |||

such a representation. The latter representation is commonly called | such a representation. The latter representation is commonly called | |||

a representation in projective coordinates. | a representation in projective coordinates. Sometimes, yet other | |||

representations are useful (e.g., representation in Jacobian | ||||

coordinates). Further details are out of scope. | ||||

The group laws in Appendix C are mostly expressed in terms of affine | The group laws in Appendix C are mostly expressed in terms of affine | |||

points, but can also be expressed in terms of the representation of | points, but can also be expressed in terms of the representation of | |||

these points in projective coordinates, thereby allowing clearing of | these points in projective coordinates, thereby allowing clearing of | |||

denominators. The group laws may also involve non-affine points | denominators. The group laws may also involve non-affine points | |||

(such as the point at infinity O of a Weierstrass curve or of a | (such as the point at infinity O of a Weierstrass curve or of a | |||

Montgomery curve). Those can also be represented in projective | Montgomery curve). Those can also be represented in projective | |||

coordinates. Further details are out of scope. | coordinates. Further details are out of scope. | |||

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

skipping to change at page 21, line 45 ¶ | skipping to change at page 23, line 47 ¶ | |||

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 E.3. This | (GX, GY), where parameters are as specified in Appendix E.3. This | |||

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

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

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

Y):=(u + A/3, v) of Wei25519, while the point at infinity of | Y):=(u + A/3, v) 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 mappings of Appendix D.2.) Under this mapping, the base | we used the mappings of Appendix D.2 and that B=1.) Under this | |||

point (Gu, Gv) of Curve25519 corresponds to the base point (GX, GY) | mapping, the base point (Gu, Gv) of Curve25519 corresponds to the | |||

of Wei25519. The inverse mapping maps the affine point (X, Y) of | base point (GX, GY) of Wei25519. The inverse mapping maps the affine | |||

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

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

Note that this mapping involves a simple shift of the first | Curve25519. Note that this mapping involves a simple shift of the | |||

coordinate and can be implemented via integer-only arithmetic as a | first coordinate and can be implemented via integer-only arithmetic | |||

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

for its inverse, where delta=(p+A)/3 is the element of GF(p) defined | -(p+A)/3 for its inverse, where delta=(p+A)/3 is the element of GF(p) | |||

by | defined by | |||

delta 19298681539552699237261830834781317975544997444273427339909597 | delta 19298681539552699237261830834781317975544997444273427339909597 | |||

334652188435537 | 334652188435537 | |||

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

aaaaaaaa aaad2451). | aaaaaaaa aaad2451). | |||

(Note that, depending on the implementation details of the field | (Note that, depending on the implementation details of the field | |||

arithmetic, one may have to shift the result by +p or -p if this | arithmetic, one may have to shift the result by +p or -p if this | |||

integer is not in the interval [0,p-1].) | integer is not in the interval [0,p-1].) | |||

skipping to change at page 28, line 25 ¶ | skipping to change at page 30, line 25 ¶ | |||

(X', Y') of W_{a',b'} to the 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}, where -- | (X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of W_{a,b}, where -- | |||

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

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

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

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

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

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

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

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

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

outside scope of this document (for this, contact the author of this | of scope of this document. | |||

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

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

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

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

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

[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 implementations for these curves | allows taking advantage of existing implementations for these curves | |||

skipping to change at page 30, line 10 ¶ | skipping to change at page 32, line 10 ¶ | |||

644181596229 | 644181596229 | |||

(=0x4efd6829 88ff8526 e189f712 5999550c e9ef729b ed1a7015 | (=0x4efd6829 88ff8526 e189f712 5999550c e9ef729b ed1a7015 | |||

73b1bab8 8bfcd845), | 73b1bab8 8bfcd845), | |||

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 isogenous mapping of | infinity of Wei25519.-3. (Here, we used the isogenous mapping of | |||

Appendix F.4.) Under this isogenous mapping, the base point (GX,GY) | Appendix F.4.) Under this isogenous mapping, the base point (GX,GY) | |||

of Wei25519 corresponds to the base point (G3X,G3Y) of Wei25519.-3. | of Wei25519 corresponds to the base point (G3X,G3Y) of Wei25519.-3. | |||

The dual isogeny maps the affine point (X',Y') of Wei25519.-3 to the | The dual isogeny maps the affine point (X',Y') of Wei25519.-3 to the | |||

affine point (X,Y):=(u'(X1)/w'(X1)^2,Y1*v'(x1)/w'(X1)^3) of Wei25519, | affine point (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 the | 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 H.2, | polynomials with coefficients in GF(p) as defined in Appendix H.2, | |||

while mapping the point at infinity O of Wei25519.-3 to the point at | while mapping the point at infinity O of Wei25519.-3 to the point at | |||

infinity O of Wei25519. Under this dual isogenous mapping, the base | infinity O of Wei25519. Under this dual isogenous mapping, the base | |||

point (G3X, G3Y) of Wei25519.-3 corresponds to a multiple of the base | point (G3X, G3Y) of Wei25519.-3 corresponds to a multiple of the base | |||

point (GX, GY) of Wei25519, where this multiple is l=47 (the degree | point (GX, GY) of Wei25519, where this multiple is l=47 (the degree | |||

of the isogeny; see the description in Appendix F.3). Note that this | of the isogeny; see the description in Appendix F.3). Note that this | |||

isogenous map (and its dual) primarily involves the evaluation of | isogenous map (and its dual) primarily involves the evaluation of | |||

three fixed polynomials involving the x-coordinate, which takes | three fixed polynomials involving the x-coordinate, which takes | |||

roughly 140 modular multiplications (or less than 5-10% relative | roughly 140 modular multiplications (or less than 5-10% relative | |||

End of changes. 29 change blocks. | ||||

118 lines changed or deleted | | 215 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/ |