 1/draftietflwigcurverepresentations03.txt 20190419 08:13:15.044323657 0700
+++ 2/draftietflwigcurverepresentations04.txt 20190419 08:13:15.160326684 0700
@@ 1,18 +1,18 @@
lwig R. Struik
InternetDraft Struik Security Consultancy
Intended status: Informational March 23, 2019
Expires: September 24, 2019
+Intended status: Informational April 19, 2019
+Expires: October 21, 2019
Alternative Elliptic Curve Representations
 draftietflwigcurverepresentations03
+ draftietflwigcurverepresentations04
Abstract
This document specifies how to represent Montgomery curves and
(twisted) Edwards curves as curves in shortWeierstrass form and
illustrates how this can be used to carry out elliptic curve
computations using existing implementations of, e.g., ECDSA and ECDH
using NIST prime curves.
Requirements Language
@@ 30,21 +30,21 @@
InternetDrafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as InternetDrafts. The list of current Internet
Drafts is at https://datatracker.ietf.org/drafts/current/.
InternetDrafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use InternetDrafts as reference
material or to cite them other than as "work in progress."
 This InternetDraft will expire on September 24, 2019.
+ This InternetDraft will expire on October 21, 2019.
Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/licenseinfo) in effect on the date of
publication of this document. Please review these documents
@@ 58,96 +58,100 @@
1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 4
2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 4
3. Use of Representation Switches . . . . . . . . . . . . . . . 4
4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 5
4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 6
4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 6
4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 7
5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
 6. Security Considerations . . . . . . . . . . . . . . . . . . . 8
+ 6. Security Considerations . . . . . . . . . . . . . . . . . . . 9
7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 9
 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9
 8.1. COSE Elliptic Curves Registration . . . . . . . . . . . . 9
+ 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10
+ 8.1. COSE Elliptic Curves Registration . . . . . . . . . . . . 10
8.2. COSE Algorithms Registration (1/2) . . . . . . . . . . . 10
 8.3. COSE Algorithms Registration (2/2) . . . . . . . . . . . 10
 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11
 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 11
 10.1. Normative References . . . . . . . . . . . . . . . . . . 11
 10.2. Informative References . . . . . . . . . . . . . . . . . 12
 Appendix A. Some (nonBinary) Elliptic Curves . . . . . . . . . 13
 A.1. Curves in shortWeierstrass Form . . . . . . . . . . . . 13
 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 13
 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 13
 Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 14
 B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 14
 B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 15
 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 16
 C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 16
 C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 17
 C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 18
 Appendix D. Relationship Between Curve Models . . . . . . . . . 19
+ 8.3. COSE Algorithms Registration (2/2) . . . . . . . . . . . 11
+ 8.4. JOSE Elliptic Curves Registration . . . . . . . . . . . . 11
+ 8.5. JOSE Algorithms Registration (1/2) . . . . . . . . . . . 11
+ 8.6. JOSE Algorithms Registration (2/2) . . . . . . . . . . . 12
+ 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 12
+ 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 12
+ 10.1. Normative References . . . . . . . . . . . . . . . . . . 12
+ 10.2. Informative References . . . . . . . . . . . . . . . . . 13
+ Appendix A. Some (nonBinary) Elliptic Curves . . . . . . . . . 15
+ A.1. Curves in shortWeierstrass Form . . . . . . . . . . . . 15
+ A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 15
+ A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 15
+ Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 16
+ B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 16
+ B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 17
+ Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 18
+ 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
 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 19
 D.2. Mapping between Montgomery Curves and Weierstrass Curves 20
 D.3. Mapping between Twisted Edwards Curves and Weierstrass
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 21
 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 21
 E.1. Curve Definition and Alternative Representations . . . . 21
 E.2. Switching between Alternative Representations . . . . . . 21
 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 23
 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 25
 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 25
 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 26
 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 26
 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 27
 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 29
 G.1. Further Alternative Representations . . . . . . . . . . . 29
 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 29
 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 30
 Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 31
 H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 31
 H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 31
 H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 34
 H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 37
 H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 38
 H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 38
 H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 40
 H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 43
 Appendix I. Point Compression . . . . . . . . . . . . . . . . . 44
 I.1. Point Compression for Weierstrass Curves . . . . . . . . 44
 I.2. Point Compression for Montgomery Curves . . . . . . . . . 45
 I.3. Point Compression for Twisted Edwards Curves . . . . . . 46
 Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 46
 J.1. Conversion between Bit Strings and Integers . . . . . . . 47
+ D.2. Mapping between Montgomery Curves and Weierstrass Curves 22
+ D.3. Mapping between Twisted Edwards Curves and Weierstrass
+ Curves . . . . . . . . . . . . . . . . . . . . . . . . . 23
+ Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 23
+ E.1. Curve Definition and Alternative Representations . . . . 23
+ E.2. Switching between Alternative Representations . . . . . . 23
+ E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 25
+ Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 27
+ F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 27
+ F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 28
+ F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 28
+ F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 29
+ Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 31
+ G.1. Further Alternative Representations . . . . . . . . . . . 31
+ G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 31
+ G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 32
+ Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 33
+ H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 33
+ H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 33
+ H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 36
+ H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 39
+ H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 40
+ H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 40
+ H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 42
+ H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 45
+ Appendix I. Point Compression . . . . . . . . . . . . . . . . . 46
+ I.1. Point Compression for Weierstrass Curves . . . . . . . . 46
+ 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,
 I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 47
+ I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 49
J.3. Conversion between Octet Strings and Bit Strings (BS2OS,
 OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 48
+ OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 50
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
 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 48
 J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 49
 Appendix K. Representation Examples Curve25519 Family Members . 50
 K.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 50
 K.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 52
 K.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 53
 K.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 55
 K.5. Example with Wei25519.3 . . . . . . . . . . . . . . . . 56
 Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 58
 L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 58
 L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 58
 L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 58
 L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 58
 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 59
+ (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 50
+ J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 51
+ Appendix K. Representation Examples Curve25519 Family Members . 52
+ K.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 52
+ K.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 54
+ K.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 55
+ K.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 57
+ K.5. Example with Wei25519.3 . . . . . . . . . . . . . . . . 58
+ Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 60
+ L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 60
+ 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) . . . . . 60
+
+ L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 60
+ Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 61
1. Fostering Code Reuse with New Elliptic Curves
It is wellknown that elliptic curves can be represented using
different curve models. Recently, IETF standardized elliptic curves
that are claimed to have better performance and improved robustness
against "real world" attacks than curves represented in the
traditional "short" Weierstrass model. This document specifies an
alternative representation of points of Curve25519, a socalled
Montgomery curve, and of points of Edwards25519, a socalled twisted
@@ 180,43 +184,44 @@
Wei25519.3, with hardcoded domain parameter a=2 and a=3 (mod p),
respectively; see Appendix G. (Here, p is the characteristic of the
field over which these curves are defined.)
3. Use of Representation Switches
The curves Curve25519, Edwards25519, and Wei25519, as specified in
Appendix E.3, are all isomorphic, with the transformations 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
 curves. Consequently, a publickey pair (k,R:=k*G) for any one of
 these curves corresponds, via these isomorphic mappings, to the
 publickey pair (k, R':=k*G') for each of these other curves (where G
 and G' are the corresponding base points of these curves). This
 observation extends to the case where one also considers curve
 Wei25519.2 (which has hardcoded domain parameter a=2), as specified
 in Appendix G.3, since it is isomorphic to Wei25519, with the
 transformation of Appendix G.2, and, thereby, also isomorphic to
 Curve25519 and Edwards25519.
+ curves. Consequently, a publicprivate key pair (k,R:=k*G) for any
+ one of these curves corresponds, via these isomorphic mappings, to
+ the publicprivate key pair (k, R':=k*G') for each of these other
+ curves (where G and G' are the corresponding base points of these
+ curves). This observation extends to the case where one also
+ considers curve Wei25519.2 (which has hardcoded domain parameter
+ a=2), as specified in Appendix G.3, since it is isomorphic to
+ Wei25519, with the transformation of Appendix G.2, and, thereby, also
+ isomorphic to Curve25519 and Edwards25519.
The curve Wei25519.3 (which has hardcoded domain parameter a=3 (mod
p)) is not isomorphic to the curve Wei25519, but is related in a
slightly weaker sense: the curve Wei25519 is isogenous to the curve
Wei25519.3, where the mapping of Appendix G.2 is an isogeny of
degree l=47 that maps the specified base point G of Wei25519 to the
specified base point G' of Wei25519.3 and where the socalled dual
isogeny (which maps Wei25519.3 to Wei25519) has the same degree
l=47, but does not map G' to G, but to a fixed multiple hereof, where
 this multiple is l=47. Consequently, a publickey pair (k,R:=k*G)
 for Wei25519 corresponds to the publickey pair (k, R':= k*G') for
 Wei25519.3 (via the lisogeny), whereas the publickey pair (k,
 R':=k*G') corresponds to the publickey pair (l*k, l*R=l*k*G) of
 Wei25519 (via the dual isogeny). (Note the extra scalar l=47 here.)
+ this multiple is l=47. Consequently, a publicprivate key pair
+ (k,R:=k*G) for Wei25519 corresponds to the publicprivate key pair
+ (k, R':= k*G') for Wei25519.3 (via the lisogeny), whereas the
+ publicprivate key pair (k, R':=k*G') corresponds to the public
+ 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
cryptographic scheme that involves computations on publicprivate key
pairs, where implementations may carry out computations on the
corresponding object for the isomorphic or isogenous curve and
convert the results back to the original curve (where, in case this
involves an lisogeny, one has to take into account the factor l).
This includes use with ellipticcurve based signature schemes and key
agreement and key transport schemes.
@@ 351,31 +356,41 @@
the CFRG curves Curve25519 and Edwards25519 is not possible,
since not of the required form. Instead, one has to implement
Wei25519.3 and include code that implements the isogeny and dual
isogeny from and to Wei25519. This isogeny has degree l=47 and
requires roughly 9kB of storage for isogeny and dualisogeny
computations (see the tables in Appendix H). Note that storage
would have reduced to a single 64byte table if only the curve
would have been generated so as to be isomorphic to a Weierstrass
curve with hardcoded a=3 parameter (this corresponds to l=1).
 NOTE: An example of 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
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
have ucoordinate u=9, with B=1 and A=3960846). In either case,
the resulting curve has the same cryptographic properties as
Curve25519 and the same performance (which relies on A being a
3byte integer, as is the case with the domain parameter A=486662
of Curve25519, and using the same special prime p=2^25519),
while at the same time being "Jacobianfriendly" 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 lisogenous 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
The different representations of elliptic curve points discussed in
this document are all obtained using a publicly known transformation,
which is either an isomorphism or a lowdegree isogeny. It is well
known that an isomorphism maps elliptic curve points to equivalent
mathematical objects and that the complexity of cryptographic
problems (such as the discrete logarithm problem) of curves related
via a lowdegree isogeny are tightly related. Thus, the use of these
techniques does not negatively impact cryptographic security of
@@ 415,21 +430,21 @@
8. IANA Considerations
An object identifier is requested for curve Wei25519 and its use with
ECDSA and cofactor ECDH, using the representation conventions of
this document.
There is *currently* no further IANA action required for this
document. New object identifiers would be required in case one
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
This section registers the following value in the IANA "COSE Elliptic
Curves" registry [IANA.COSE.Curves].
Name: Wei25519;
Value: TBD (Requested value: 1);
@@ 469,55 +484,98 @@
Value: TBD (Requested value: 2);
Description: NISTcompliant cofactor DiffieHellman w/ curve
Wei25519 and key derivation function HKDF SHA256;
Reference: Section 4.1 of this specification (for key derivation,
see Section 11.1 of [RFC8152]);
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: shortWeierstrass 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/ SHA256 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: NISTcompliant cofactor DiffieHellman 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 [SP80056c]);
+
+ Algorithm Analysis Documents: Section 4.1 of this specification (for
+ key derivation, see Section 5 of [SP80056c]).
+
9. Acknowledgements
Thanks to Nikolas Rosener for discussions surrounding implementation
details of the techniques described in this document and to Phillip
HallamBaker for triggering inclusion of verbiage on the use of
Montgomery ladders with recovery of the ycoordinate. Thanks to
 Stanislav Smyshlyaev for his careful review.
+ Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews.
10. References
10.1. Normative References
[ANSIX9.62]
ANSI X9.622005, "Public Key Cryptography for the
Financial Services Industry: The Elliptic Curve Digital
Signature Algorithm (ECDSA)", American National Standard
for Financial Services, Accredited Standards Committee X9,
Inc, Anapolis, MD, 2005.
[FIPS1864]
FIPS 1864, "Digital Signature Standard (DSS), Federal
Information Processing Standards Publication 1864", US
Department of Commerce/National Institute of Standards and
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
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
.
[RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography
(ECC) Brainpool Standard Curves and Curve Generation",
RFC 5639, DOI 10.17487/RFC5639, March 2010,
.
@@ 541,50 +599,88 @@
[SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0",
Standards for Efficient Cryptography, , June 2009.
[SP80056a]
NIST SP 80056a, "Recommendation for PairWise Key
Establishment Schemes Using Discrete Log Cryptography,
Revision 3", US Department of Commerce/National Institute
of Standards and Technology, Gaithersburg, MD, April 2018.
+ [SP80056c]
+ NIST SP 80056c, "Recommendation for KeyDerivation
+ Methods in KeyEstablishment Schemes, Revision 1", US
+ Department of Commerce/National Institute of Standards and
+ Technology, Gaithersburg, MD, April 2018.
+
10.2. Informative References
[ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in
Cryptography", Cambridge University Press, Lecture Notes
Series 265, July 1999.
[ECCIsogeny]
E. Brier, M. Joye, "Fast Point Multiplication on Elliptic
Curves through Isogenies", AAECC, Lecture Notes in
Computer Science, Vol. 2643, New York: SpringerVerlag,
2003.
[GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to
Elliptic Curve Cryptography", New York: SpringerVerlag,
2004.
[HWECC] W.P. Liu, "How to Use the Kinets LTC ECC HW to Accelerate
Curve25519 (version 7)", NXP,
https://community.nxp.com/docs/DOC330199, 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
+ signatureencryptionalgorithms.
+
+ [IANA.JOSE.Curves]
+ IANA, "JSON Web Key Elliptic Curve", IANA,
+ https://www.iana.org/assignments/jose/jose.xhtml#webkey
+ ellipticcurve.
+
[Ladder] P.L. Montgomery, "Speeding the Pollard and Elliptic Curve
Methods of Factorization", Mathematics of
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: SpringerVerlag,
+ 2008.
+
[tEdFormulas]
H. Hisil, K.K.H. Wong, G. Carter, E. Dawson, "Twisted
Edwards Curves Revisited", ASIACRYPT 2008, Lecture Notes
in Computer Science, Vol. 5350, New York: SpringerVerlag,
2008.
+ [Weiyrecovery]
+ T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve
+ Multiplication Resistant Against Side Channel Attacks",
+ Centre for Applied Cryptographic Research, Corr 200203,
+ 2002.
+
Appendix A. Some (nonBinary) Elliptic Curves
A.1. Curves in shortWeierstrass Form
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
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
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
@@ 653,45 +749,47 @@
least n.
If R is a point of the curve that is also contained in (P), there is
a unique integer k in the interval [0, l1] so that R=k*P, where l is
the order of P. This number is called the discrete logarithm of R to
the base P. The discrete logarithm problem is the problem of finding
the discrete logarithm of R to the base P for any two points P and R
of the curve, if such a number exists.
If P is a fixed base point G of the curve, the pair (k, R:=k*G) is
 called a publicprivate key pair, the integer k the private key, and
 the point R the corresponding public key. The private key k can be
 represented as an integer in the interval [0,n1], where G has order
 n.
+ commonly called a publicprivate key pair, the integer k the private
+ key, and the point R the corresponding public key. The private key k
+ can be represented as an integer in the interval [0,n1], where G has
+ order n.
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',
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
expressed using the same curve model, although (naturally) with its
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
be isomorphic if these have the same group structure. Note that
isomorphic curves have necessarily the same order and are, thus, a
special type of isogenous curves. Further details are out of scope.
Weierstrass curves can have prime order, whereas Montgomery curves
and twisted Edwards curves always have an order that is a multiple of
four (and, thereby, a small subgroup of cardinality four).
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
is a nonzero element of GF(q), and can be uniquely recovered from
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
points, but can also be expressed in terms of the representation of
these points in projective coordinates, thereby allowing clearing of
denominators. The group laws may also involve nonaffine points
(such as the point at infinity O of a Weierstrass curve or of a
Montgomery curve). Those can also be represented in projective
coordinates. Further details are out of scope.
B.2. Finite Fields
@@ 980,30 +1078,30 @@
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
(GX, GY), where parameters are as specified in Appendix E.3. This
curve is denoted as Wei25519.
E.2. Switching between Alternative Representations
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
Curve25519 corresponds to the point at infinity of Wei25519. (Here,
 we used the mappings of Appendix D.2.) Under this mapping, the base
 point (Gu, Gv) of Curve25519 corresponds to the base point (GX, GY)
 of Wei25519. The inverse mapping maps the affine point (X, Y) of
 Wei25519 to (u, v):=(X  A/3, Y) of Curve25519, while mapping the
 point at infinity of Wei25519 to the point at infinity of Curve25519.
 Note that this mapping involves a simple shift of the first
 coordinate and can be implemented via integeronly arithmetic as a
 shift of (p+A)/3 for the isomorphic mapping and a shift of (p+A)/3
 for its inverse, where delta=(p+A)/3 is the element of GF(p) defined
 by
+ we used the mappings of Appendix D.2 and that B=1.) Under this
+ mapping, the base point (Gu, Gv) of Curve25519 corresponds to the
+ base point (GX, GY) of Wei25519. The inverse mapping maps the affine
+ point (X, Y) of Wei25519 to (u, v):=(X  A/3, Y) of Curve25519, while
+ mapping the point at infinity of Wei25519 to the point at infinity of
+ Curve25519. Note that this mapping involves a simple shift of the
+ first coordinate and can be implemented via integeronly arithmetic
+ as a shift of (p+A)/3 for the isomorphic mapping and a shift of
+ (p+A)/3 for its inverse, where delta=(p+A)/3 is the element of GF(p)
+ defined by
delta 19298681539552699237261830834781317975544997444273427339909597
334652188435537
(=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa
aaaaaaaa aaad2451).
(Note that, depending on the implementation details of the field
arithmetic, one may have to shift the result by +p or p if this
integer is not in the interval [0,p1].)
@@ 1292,23 +1389,22 @@
(X', Y') of W_{a',b'} to the point
(X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of W_{a,b}, where 
again  u'(X'), v'(X'), and w'(X') are polynomials in X' that depend
on the isogeny in question. These mappings have the property that
their composition is not the identity mapping (as was the case with
the isomorphic mappings discussed in Appendix F.3), but rather a
fixed multiple hereof: if this multiple is l then the isogeny is
called an isogeny of degree l (or lisogeny) and u, v, and w (and,
similarly, u', v', and w') are polynomials of degrees l, 3*(l1)/2,
and (l1)/2, respectively. Note that an isomorphism is simply an
 isogeny of degree l=1. Details of how to determine isogenies are
 outside scope of this document (for this, contact the author of this
 document).
+ isogeny of degree l=1. Details of how to determine isogenies are out
+ of scope of this document.
Implementations may take advantage of this mapping to carry out
elliptic curve group operations originally defined for a Weierstrass
curve with a generic domain parameter a on a corresponding isogenous
Weierstrass curve with domain parameter a'=3 (mod p), where one can
use socalled Jacobian coordinates with a particular projective
version of the addition laws of Appendix C.1. Since all traditional
NIST curves have domain parameter a=3, while all Brainpool curves
[RFC5639] are isomorphic to a Weierstrass curve of this form, this
allows taking advantage of existing implementations for these curves
@@ 1373,21 +1469,21 @@
644181596229
(=0x4efd6829 88ff8526 e189f712 5999550c e9ef729b ed1a7015
73b1bab8 8bfcd845),
while the point at infinity of Wei25519 corresponds to the point at
infinity of Wei25519.3. (Here, we used the isogenous mapping of
Appendix F.4.) Under this isogenous mapping, the base point (GX,GY)
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
 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
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
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 (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
isogenous map (and its dual) primarily involves the evaluation of
three fixed polynomials involving the xcoordinate, which takes
roughly 140 modular multiplications (or less than 510% relative