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/