 1/draftietflwigcurverepresentations00.txt 20181106 17:13:09.738638919 0800
+++ 2/draftietflwigcurverepresentations01.txt 20181106 17:13:09.806640569 0800
@@ 1,26 +1,26 @@
lwig R. Struik
InternetDraft Struik Security Consultancy
Intended status: Informational October 18, 2018
Expires: April 21, 2019
+Intended status: Informational November 06, 2018
+Expires: May 10, 2019
Alternative Elliptic Curve Representations
 draftietflwigcurverepresentations00
+ draftietflwigcurverepresentations01
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 implement elliptic curve
 computations using existing implementations that already implement,
 e.g., ECDSA and ECDH using NIST prime curves.
+ 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
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in RFC
2119 [RFC2119].
Status of This Memo
@@ 30,191 +30,356 @@
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 April 21, 2019.
+ This InternetDraft will expire on May 10, 2019.
Copyright Notice
Copyright (c) 2018 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
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 3
2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 3
 3. Example Uses . . . . . . . . . . . . . . . . . . . . . . . . 3
 3.1. ECDSASHA25625519 . . . . . . . . . . . . . . . . . . . 4
 3.2. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 4
 4. Security Considerations . . . . . . . . . . . . . . . . . . . 4
 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 5
 6. Normative References . . . . . . . . . . . . . . . . . . . . 5
 Appendix A. Some (nonBinary) Elliptic Curves . . . . . . . . . 6
 A.1. Curves in shortWeierstrass Form . . . . . . . . . . . . 6
 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 6
 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 6
 Appendix B. Elliptic Curve Group Operations . . . . . . . . . . 7
 B.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 7
 B.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 7
 B.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 8
 Appendix C. Relationship Between Curve Models . . . . . . . . . 8
 C.1. Mapping between twisted Edwards Curves and Montgomery
 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 8
 C.2. Mapping between Montgomery Curves and Weierstrass Curves 9
 C.3. Mapping between twisted Edwards Curves and Weierstrass
 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 10
 Appendix D. Curve25519 and Cousins . . . . . . . . . . . . . . . 10
 D.1. Curve Definition and Alternative Representations . . . . 10
 D.2. Switching between Alternative Representations . . . . . . 10
 D.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 12
 Appendix E. Further Mappings . . . . . . . . . . . . . . . . . . 14
 E.1. Isomorphic Mapping between Weierstrass Curves . . . . . . 14
 E.2. Isogeneous Mapping between Weierstrass Curves . . . . . . 15
 Appendix F. Further Cousins of Curve25519 . . . . . . . . . . . 16
 F.1. Further Alternative Representations . . . . . . . . . . . 16
 F.2. Further Switching . . . . . . . . . . . . . . . . . . . . 16
 F.3. Further Domain Parameters . . . . . . . . . . . . . . . . 17
 Appendix G. Isogeny Details . . . . . . . . . . . . . . . . . . 19
 G.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 19
 G.1.1. Coefficients of u(x): . . . . . . . . . . . . . . . . 19
 G.1.2. Coefficients of v(x): . . . . . . . . . . . . . . . . 21
 G.1.3. Coefficients of w(x): . . . . . . . . . . . . . . . . 24
+ 3. Use of Representation Switches . . . . . . . . . . . . . . . 4
+ 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 5
+ 4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 5
+ 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 5
+ 4.3. Specification of ECDSASHA256Wei25519 . . . . . . . . . 5
+ 4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 6
+ 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
+ 6. Security Considerations . . . . . . . . . . . . . . . . . . . 7
+ 7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 8
+ 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8
+ 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 8
+ 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 8
+ 10.1. Normative References . . . . . . . . . . . . . . . . . . 8
+ 10.2. Informative References . . . . . . . . . . . . . . . . . 9
+ Appendix A. Some (nonBinary) Elliptic Curves . . . . . . . . . 10
+ A.1. Curves in shortWeierstrass Form . . . . . . . . . . . . 10
+ A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 10
+ A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 10
+ Appendix B. Elliptic Curve Nomenclature . . . . . . . . . . . . 11
+ Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 11
+ C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 11
+ C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 12
+ C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 13
+ Appendix D. Relationship Between Curve Models . . . . . . . . . 14
+ D.1. Mapping between twisted Edwards Curves and Montgomery
+ Curves . . . . . . . . . . . . . . . . . . . . . . . . . 14
+ D.2. Mapping between Montgomery Curves and Weierstrass Curves 14
+ D.3. Mapping between twisted Edwards Curves and Weierstrass
+ Curves . . . . . . . . . . . . . . . . . . . . . . . . . 15
+ Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 15
+ E.1. Curve Definition and Alternative Representations . . . . 15
+ E.2. Switching between Alternative Representations . . . . . . 16
+ E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 17
+ Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 19
+ F.1. Isomorphic Mapping between Weierstrass Curves . . . . . . 19
+ F.2. Isogenous Mapping between Weierstrass Curves . . . . . . 20
 G.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 25
 G.2.1. Coefficients of u'(x): . . . . . . . . . . . . . . . 25
 G.2.2. Coefficients of v'(x): . . . . . . . . . . . . . . . 27
 G.2.3. Coefficients of w'(x): . . . . . . . . . . . . . . . 30
 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 31
+ Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 21
+ G.1. Further Alternative Representations . . . . . . . . . . . 21
+ G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 22
+ G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 23
+ Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 24
+ H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 24
+ H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 24
+ H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 26
+ H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 29
+ H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 30
+ H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 30
+ H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 32
+ H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 35
+ Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 36
1. Fostering Code Reuse with New Elliptic Curves
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 draft specifies an
+ 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
Edwards curve, which are both specified in [RFC7748], as points of a
 specific socalled "short" Weierstrass curve, called Wei25519. The
 draft also defines how to efficiently switch between these different
+ specific socalled "short" Weierstrass curve, called Wei25519. We
+ also define how to efficiently switch between these different
representations.
 Use of Wei25519 allows easy definition of signature schemes and key
 agreement schemes already specified for traditional NIST prime
+ Use of Wei25519 allows easy definition of new signature schemes and
+ key agreement schemes already specified for traditional NIST prime
curves, thereby allowing easy integration with existing
specifications, such as NIST SP 80056a [SP80056a], FIPS Pub 1864
 [FIPS1864], and ANSI X9.622005 [ANSIX9.62] and fostering code
+ [FIPS1864], and ANSI X9.622005 [ANSIX9.62], and fostering code
reuse on platforms that already implement some of these schemes using
elliptic curve arithmetic for curves in "short" Weierstrass form (see
 Appendix B.1).
+ Appendix C.1).
2. Specification of Wei25519
For the specification of Wei25519 and its relationship to Curve25519
 and Edwards25519, see Appendix D. For further details and background
+ and Edwards25519, see Appendix E. For further details and background
information on elliptic curves, we refer to the other appendices.
The use of Wei25519 allows reuse of existing generic code that
implements shortWeierstrass curves, such as the NIST curve P256, to
 also implement the CFRG curves Curve25519 and Ed25519. The draft
 also caters to reuse of existing code where some domain parameters
 may have been hardcoded, thereby widening the scope of applicability;
 see Appendix F.
+ also implement the CFRG curves Curve25519 and Edwards25519. We also
+ cater to reusing of existing code where some domain parameters may
+ have been hardcoded, thereby widening the scope of applicability. To
+ this end, we specify the shortWeierstrass curves Wei25519.2 and
+ Wei25519.3, with hardcoded domain parameter a=2 and a=3 (mod p),
+ respectively; see Appendix G.
3. Example Uses
3.1. ECDSASHA25625519
+3. Use of Representation Switches
 RFC 8032 [RFC8032] specifies the use of EdDSA, a "full" Schnorr
 signature scheme, with instantiation by Edwards25519 and Ed448, two
 socalled twisted Edwards curves. These curves can also be used with
 the widely implemented signature scheme ECDSA [FIPS1864], by
 instantiating ECDSA with the curve Wei25519 and hash function SHA
 256, where "under the hood" an implementation may carry out elliptic
 curve scalar multiplication routines using the corresponding
 representations of a point of the curve Wei25519 in Weierstrass form
 as a point of the Montgomery curve Curve25519 or of the twisted
 Edwards curve Edwards25519. (The corresponding ECDSASHA512448
 scheme arises if one were to specify a curve in shortWeierstrass
 form corresponding to Ed448 and use the hash function SHA512.) Note
 that, in either case, one can implement these schemes with the same
 representation conventions as used with existing NIST specifications,
 including bit/byteordering, compression functions, and thelike.
 This allows implementations of ECDSA with the hash function SHA256
 and with the NIST curve P256 or with the curve Wei25519 specified in
 this draft to use the same implementation (instantiated with,
 respectively, the NIST P256 elliptic curve domain parameters or with
 the domain parameters of curve Wei25519 specified in Appendix D).
+ 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.
3.2. Other Uses
+ The curve Wei25519.3 (which has hardcoded domain parameter a=3 (mod
+ p)) is not isomorphic to the curve Wei25519, but is related in a
+ slightly weaker sense: the curve Wei25519 is isogenous to the curve
+ Wei25519.3, where the mapping of Appendix G.2 is an isogeny of
+ degree l=47 that maps the specified base point G of Wei25519 to the
+ specified base point G' of Wei25519.3 and where the 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.)
+
+ 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.
+
+4. Examples
+
+4.1. Implementation of X25519
+
+ RFC 7748 [RFC7748] specifies the use of X25519, a cofactor Diffie
+ Hellman key agreement scheme, with instantiation by the Montgomery
+ curve Curve25519. This key agreement scheme was already specified in
+ Section 6.1.2.2 of NIST SP 80056a [SP80056a] for elliptic curves
+ in short Weierstrass form. Hence, one can implement X25519 using
+ existing NIST routines by (1) representing a point of the Montgomery
+ curve Curve25519 as a point of the Weierstrass curve Wei25519; (2)
+ instantiating the cofactor DiffieHellman key agreement scheme of
+ the NIST specification with the resulting point and Wei25519 domain
+ parameters; (3) representing the key resulting from this scheme
+ (which is a point of the curve Wei25519 in Weierstrass form) as a
+ point of the Montgomery curve Curve25519. The representation change
+ can be implemented via a simple wrapper and involves a single modular
+ addition (see Appendix D.2). Using this method has the additional
+ advantage that one can reuse the publicprivate key pair routines,
+ domain parameter validation, and other checks that are already part
+ of the NIST specifications. Note: at this point, it is unclear
+ whether this implies that a FIPSaccredited module implementing co
+ factor DiffieHellman for, e.g., P256 would also extend this
+ accreditation to X25519.
+
+4.2. Implementation of Ed25519
+
+ RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature
+ scheme, with instantiation by the twisted Edwards curve Edwards25519.
+ One can implement the computation of the ephemeral key pair for
+ Ed25519 using an existing Montgomery curve implementation by (1)
+ generating a publicprivate key pair (k, R':=k*G') for Curve25519;
+ (2) representing this publicprivate key as the pair (k, R:=k*G) for
+ Ed25519. As before, the representation change can be implemented via
+ a simple wrapper. Note that the Montgomery ladder specified in
+ Section 5 of RFC7748 [RFC7748] does not provide sufficient
+ information to reconstruct R' (since it does not compute the
+ ycoordinate of R'). However, this deficiency can be remedied by
+ using a slightly modified version of the Montgomery ladder that
+ includes reconstruction of the ycoordinate of R':=k*G' at the end of
+ hereof (which uses the vcoordinate Gv of the base point of
+ Curve25519 as well). For details, see Appendix D.2.
+
+4.3. Specification of ECDSASHA256Wei25519
+
+ FIPS Pub 1864 [FIPS1864] specifies the signature scheme ECDSA and
+ can be instantiated not just with the NIST prime curves, but also
+ with other Weierstrass curves (that satisfy additional cryptographic
+ criteria). In particular, one can instantiate this scheme with the
+ Weierstrass curve Wei25519 and the hash function SHA256, where an
+ implementation may generate a publicprivate key pair for Wei25519 by
+ (1) internally carrying out these computations on the Montgomery
+ curve Curve25519, the twisted Edwards curve Edwards25519, or even the
+ Weierstrass curve Wei25519.3 (with hardcoded a=3 domain parameter);
+ (2) representing the result as a key pair for the curve Wei25519.
+ Note that, in either case, one can implement these schemes with the
+ same representation conventions as used with existing NIST
+ specifications, including bit/byteordering, compression functions,
+ and thelike. This allows implementations of ECDSA with the hash
+ function SHA256 and with the NIST curve P256 or with the curve
+ Wei25519 specified in this draft to use the same implementation
+ (instantiated with, respectively, the NIST P256 elliptic curve
+ domain parameters or with the domain parameters of curve Wei25519
+ specified in Appendix E).
+
+4.4. Other Uses
Any existing specification of cryptographic schemes using elliptic
curves in Weierstrass form and that allows introduction of a new
elliptic curve (here: Wei25519) is amenable to similar constructs,
thus spawning "offspring" protocols, simply by instantiating these
using the new curve in "short" Weierstrass form, thereby allowing
code and/or specifications reuse and, for implementations that so
desire, carrying out curve computations "under the hood" on
Montgomery curve and twisted Edwards curve cousins hereof (where
these exist). This would simply require definition of a new object
identifier for any such envisioned "offspring" protocol. This could
significantly simplify standardization of schemes and help keeping
the resource and maintenance cost of implementations supporting
algorithm agility [RFC7696] at bay.
4. Security Considerations
+5. Caveats
+
+ The examples above illustrate how specifying the Weierstrass curve
+ Wei25519 may facilitate reuse of existing code and may simplify
+ standards development. However, the following caveats apply:
+
+ 1. Unfriendly wire formats. The transformations between alternative
+ curve representations can be implemented at negligible relative
+ incremental cost if the curve points are represented as affine
+ points. If a point is represented in compressed format,
+ conversion usually requires a costly point decompression step.
+ This is the case in [RFC7748], where the inputs to the cofactor
+ DiffieHellman scheme X25519, as well as its output, are
+ represented in xcoordinateonly format;
+
+ 2. Unfriendly representation conventions. While elliptic curve
+ computations are carriedout in a field GF(q) and, thereby,
+ involve large integer arithmetic, these integers are represented
+ as bit and bytestrings. Here, [RFC8032] uses least
+ significantbyte (LSB)/leastsignificantbit (lsb) conventions,
+ whereas [RFC7748] uses LSB/mostsignificantbit (msb)
+ conventions, and where most other cryptographic specifications,
+ including NIST SP80056a [SP80056a], FIPS Pub 1864
+ [FIPS1864], and ANSI X9.622005 [ANSIX9.62] use MSB/msb
+ conventions. Since each pair of conventions is different, this
+ does necessitate bit/byte representation conversions;
+
+ 3. Unfriendly domain parameters. All traditional NIST curves are
+ Weierstrass curve with domain parameter a=3, while all Brainpool
+ curves [RFC5639] are isomorphic to a Weierstrass curve of this
+ form. Thus, one can expect there to be existing Weierstrass
+ implementations with a hardcoded a=3 domain parameter
+ ("Jacobianfriendly"). For those implementations, including the
+ curve Wei25519 as a potential vehicle for offering support for
+ the CFRG curves Curve25519 and Edwards25519 is not possible,
+ since not of the required form. Instead, one has to implement
+ Curve25519.3 and include code that implements the isogeny and
+ dual isogeny from and to Wei25519. This isogeny has degree l=47
+ and requires roughly 9kB of storage for isogeny and dualisogeny
+ computations (see the tables in Appendix H). Note that storage
+ would have reduced to a single 32bye table if the curve would
+ have been generated so as to be isomorphic to a Weierstrass curve
+ with hardcoded a=3 parameter (this corresponds to l=1). Note:
+ an example of such a curve is the Montgomery curve M_{A,B} over
+ GF(p) with p=2^25519, A=1410290, and B=1 or (if one wants the
+ base point to still have ucoordinate u=9) A=3960846. In either
+ case, the resulting curve has the same cryptographic properties
+ as Curve25519, while being more "Jacobianfriendly".
+
+6. Security Considerations
The different representations of elliptic curve points discussed in
 this draft are all obtained using a publicly known transformation.
 Since this transformation is an isomorphism, this transformation maps
 elliptic curve points to equivalent mathematical objects.
+ 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.
5. IANA Considerations
+ As to implementation security, reusing existing highquality code or
+ generic implementations that have been carefully designed to
+ withstand implementation attacks for one curve model may allow a more
+ economical way of development and maintenance than providing this
+ same functionality for each curve model separately (if multiple curve
+ models need to be supported) and, otherwise, may allow a more gradual
+ migration path, where one may initially use existing and accredited
+ chipsets that cater to the predominant curve model used in practice
+ for over 15 years.
+
+7. Privacy Considerations
+
+ The transformations between different curve models described in this
+ document are publicly known and, therefore, do not affect privacy
+ provisions.
+
+8. IANA Considerations
There is *currently* no IANA action required for this document. New
object identifiers would be required in case one wishes to specify
 one or more of the "offspring" protocols exemplified in Section 3.
+ one or more of the "offspring" protocols exemplified in Section 4.
6. Normative References
+9. Acknowledgements
+
+ Thanks to Nikolas Rosener for discussions surrounding implementation
+ details of the techniques described in this document and to Phillip
+ HallamBaker for triggering inclusion of verbiage on the use of
+ Montgomery ladders with recovery of the ycoordinate.
+
+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.
+ 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.

 [GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to
 Elliptic Curve Cryptography", New York: SpringerVerlag,
 2004.
+ Technology, Gaithersburg, MD, July 2013.
[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,
.
@@ 230,154 +395,237 @@
[RFC8032] Josefsson, S. and I. Liusvaara, "EdwardsCurve Digital
Signature Algorithm (EdDSA)", RFC 8032,
DOI 10.17487/RFC8032, January 2017,
.
[SP80056a]
NIST SP 80056a, "Recommendation for PairWise Key
Establishment Schemes Using Discrete Log Cryptography,
Revision 2", US Department of Commerce/National Institute
 of Standards and Technology Gaithersburg, MD, June 2013.
+ of Standards and Technology, Gaithersburg, MD, June 2013.
+
+10.2. Informative References
+
+ [ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in
+ Cryptography", Cambridge University Press, Lecture Notes
+ Series 265, July 1999.
+
+ [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.
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
equation (the socalled affine points), together with the special
point O (the socalled "point at infinity").This set forms a group
 under addition, via the socalled "chordandtangent" rule, where the
 point at infinity serves as the identity element. See Appendix B.1
 for details of the group operation.
+ under addition, via the socalled "secantandtangent" rule, where
+ the point at infinity serves as the identity element. See
+ Appendix C.1 for details of the group operation.
A.2. Montgomery Curves
Let GF(q) denote the finite field with q elements, where q is an odd
prime power. Let M_{A,B} be the Montgomery curve with defining
equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q)
with A unequal to (+/)2 and with B nonzero. The points of M_{A,B}
are the ordered pairs (u, v) whose coordinates are elements of GF(q)
and that satisfy the defining equation (the socalled affine points),
together with the special point O (the socalled "point at
infinity").This set forms a group under addition, via the socalled
 "chordandtangent" rule, where the point at infinity serves as the
 identity element. See Appendix B.2 for details of the group
+ "secantandtangent" rule, where the point at infinity serves as the
+ identity element. See Appendix C.2 for details of the group
operation.
A.3. Twisted Edwards Curves
Let GF(q) denote the finite field with q elements, where q is an odd
prime power. Let E_{a,d} be the twisted Edwards curve with defining
equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct
nonzero elements of GF(q). The points of E_{a,d} are the ordered
pairs (x, y) whose coordinates are elements of GF(q) and that satisfy
the defining equation (the socalled affine points). It can be shown
that this set forms a group under addition if a is a square in GF(q),
whereas d is not, where the point (0, 1) serves as the identity
element. (Note that the identity element satisfies the defining
 equation.) See Appendix B.3 for details of the group operation. An
 Edwards curve is a twisted Edwards curve with a=1.
+ equation.) See Appendix C.3 for details of the group operation.
Appendix B. Elliptic Curve Group Operations
+ An Edwards curve is a twisted Edwards curve with a=1.
B.1. Group Law for Weierstrass Curves
+Appendix B. Elliptic Curve Nomenclature
+
+ Each curve defined in Appendix A forms a commutative group under
+ addition. In Appendix C we specify the group laws, which depend on
+ the curve model in question. For completeness, we here include some
+ common elliptic curve nomenclature and basic properties (primarily so
+ as to keep this document selfcontained). These notions are mainly
+ used in Appendix E and Appendix G and not essential for our
+ exposition. This section can be skipped at first reading.
+
+ Any point P of a curve is a generator of the cyclic subgroup
+ (P):={k*P  k = 0, 1, 2,...} of the curve. If (P) has cardinality l,
+ then l is called the order of P. The order of a curve is the
+ cardinality of the set of its points. A curve is cyclic if it is
+ generated by some point of this curve. All curves of prime order are
+ cyclic, while all curves of order E = h*n, where n is a large prime
+ number and where h is a small number (the socalled cofactor), have
+ a large cyclic subgroup of prime order n. In this case, a generator
+ of order n is called a base point, commonly denoted by G. A point of
+ order dividing h is said to be in the small subgroup. For curves of
+ prime order, this small subgroup is the singleton set, consisting of
+ only the identity element.
+
+ If R is a point on a curve E that is also contained in (P), there is
+ a unique integer k in the interval [0, l1] so that R=kP, where l is
+ the order of P. This number is called the discrete logarithm of R to
+ the base P. The discrete logarithm problem is the problem of finding
+ the discrete logarithm of R to the base P for any two points P and R
+ of the curve, if such a number exists.
+
+ A publicprivate key pair is an ordered pair (k, R:=kG), where G is a
+ fixed base point of the curve. Here, k (the private key) is an
+ integer in the interval [0,n1], where G has order n.
+
+ A quadratic twist of a curve E defined over a field GF(q) is a curve
+ E' related to E, with cardinality E+E'=2*(q+1). If E is a curve
+ in one of the curve models specified in this document, a quadratic
+ twist of this curve can be expressed using the same curve model,
+ although (naturally) with different curve parameters.
+
+Appendix C. Elliptic Curve Group Operations
+
+C.1. Group Law for Weierstrass Curves
For each point P of the Weierstrass curve W_{a,b}, the point at
infinity O serves as identity element, i.e., P + O = O + P = P.
For each affine point P:=(x, y) of the Weierstrass curve W_{a,b}, the
point P is the point (x, y) and one has P + (P) = O.
Let P1:=(x1, y1) and P2:=(x2, y2) be distinct affine points of the
Weierstrass curve W_{a,b} and let Q:=P1 + P2, where Q is not the
identity element. Then Q:=(x, y), where
x + x1 + x2 = lambda^2 and y + y1 = lambda*(x1  x), where lambda
= (y2  y1)/(x2  x1).
Let P:= (x1, y1) be an affine point of the Weierstrass curve W_{a,b}
 and let Q:=2P, where Q is not the identity element. Then Q:= (x, y),
 where
+ and let Q:=2*P, where Q is not the identity element. Then Q:= (x,
+ y), where
x + 2*x1 = lambda^2 and y + y1 = lambda*(x1  x), where
lambda=(3*x1^2 + a)/(2*y1).
B.2. Group Law for Montgomery Curves
+ From the group law above it follows that if P=(x, y), P1=k*P=(x1,
+ y1), and P2=(k+1)*P=(x2, y2) are affine points of the Weierstrass
+ curve W_{a,b} and if y is nonzero, then the ycoordinate of P1 can be
+ expressed in terms of the xcoordinates of P, P1, and P2, and the
+ ycoordinate of P, as
+
+ y1=((x*x1+a)*(x+x1)+2*bx2*(xx1)^2)/(2*y).
+
+ This property allows recovery of the ycoordinate of a point P1=k*P
+ that is computed via the socalled Montgomery ladder, where P is an
+ affine point with nonzero ycoordinate. Further details are out of
+ scope.
+
+C.2. Group Law for Montgomery Curves
For each point P of the Montgomery curve M_{A,B}, the point at
infinity O serves as identity element, i.e., P + O = O + P = P.
For each affine point P:=(x, y) of the Montgomery curve M_{A,B}, the
point P is the point (x, y) and one has P + (P) = O.
Let P1:=(x1, y1) and P2:=(x2, y2) be distinct affine points of the
Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the
identity element. Then Q:=(x, y), where
x + x1 + x2 = B*lambda^2  A and y + y1 = lambda*(x1  x), where
lambda=(y2  y1)/(x2  x1).
Let P:= (x1, y1) be an affine point of the Montgomery curve M_{A,B}
 and let Q:=2P, where Q is not the identity element. Then Q:= (x, y),
 where

+ and let Q:=2*P, where Q is not the identity element. Then Q:= (x,
+ y), where
x + 2*x1 = B*lambda^2  A and y + y1 = lambda*(x1  x), where
 lambda=(3*x1^2 + 2*A*x1+1)/(2*y1).
+ lambda=(3*x1^2 + 2*A*x1+1)/(2*B*y1).
 Alternative and more efficient group laws exist, e.g., when using the
 socalled Montgomery ladder. Details are out of scope.
+ From the group law above it follows that if P=(x, y), P1=k*P=(x1,
+ y1), and P2=(k+1)*P=(x2, y2) are affine points of the Montgomery
+ curve M_{A,B} and if y is nonzero, then the ycoordinate of P1 can be
+ expressed in terms of the xcoordinates of P, P1, and P2, and the
+ ycoordinate of P, as
B.3. Group Law for Twisted Edwards Curves
+ y1=((x*x1+1)*(x+x1+2*A)2*Ax2*(xx1)^2)/(2*B*y).
+
+ This property allows recovery of the ycoordinate of a point P1=k*P
+ that is computed via the socalled Montgomery ladder, where P is an
+ affine point with nonzero ycoordinate. Further details are out of
+ scope.
+
+C.3. Group Law for Twisted Edwards Curves
Note: The group laws below hold for twisted Edwards curves E_{a,d}
where a is a square in GF(q), whereas d is not. In this case, the
addition formulae below are defined for each pair of points, without
exceptions. Generalizations of this group law to other twisted
Edwards curves are out of scope.
For each point P of the twisted Edwards curve E_{a,d}, the point
O=(0,1) serves as identity element, i.e., P + O = O + P = P.
For each point P:=(x, y) of the twisted Edwards curve E_{a,d}, the
point P is the point (x, y) and one has P + (P) = O.
Let P1:=(x1, y1) and P2:=(x2, y2) be points of the twisted Edwards
curve E_{a,d} and let Q:=P1 + P2. Then Q:=(x, y), where
x = (x1*y2 + x2*y1)/(1 + d*x1*x2*y1*y2) and y = (y1*y2 
a*x1*x2)/(1  d*x1*x2*y1*y2).
Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and
 let Q:=2P. Then Q:=(x, y), where
+ let Q:=2*P. Then Q:=(x, y), where
x = (2*x1*y1)/(1 + d*x1^2*y1^2) and y = (y1^2  a*x1^2)/(1 
d*x1^2*y1^2).
 Note that one can use the formulae for point addition to implement
 point doubling, taking inverses and adding the identity element as
 well (i.e., the point addition formulae are uniform and complete
 (subject to our Note above)).
+ Note that one can use the formulae for point addition for
+ implementing point doubling, taking inverses and adding the identity
+ element as well (i.e., the point addition formulae are uniform and
+ complete (subject to our Note above)).
Appendix C. Relationship Between Curve Models
+Appendix D. Relationship Between Curve Models
The nonbinary curves specified in Appendix A are expressed in
different curve models, viz. as curves in shortWeierstrass form, as
Montgomery curves, or as twisted Edwards curves. These curve models
are related, as follows.
C.1. Mapping between twisted Edwards Curves and Montgomery Curves
+D.1. Mapping between twisted Edwards Curves and Montgomery Curves
One can map points of the Montgomery curve M_{A,B} to points of the
twisted Edwards curve E_{a,d}, where a:=(A+2)/B and d:=(A2)/B and,
conversely, map points of the twisted Edwards curve E_{a,d} to points
of the Montgomery curve M_{A,B}, where A:=2(a+d)/(ad) and where
B:=4/(ad). For twisted Edwards curves we consider (i.e., those
where a is a square in GF(q), whereas d is not), this defines a one
toone correspondence, which  in fact  is an isomorphism between
M_{A,B} and E_{a,d}, thereby showing that, e.g., the discrete
logarithm problem in either curve model is equally hard.
@@ 393,21 +641,21 @@
infinity O and the point (0, 0) of order two of M_{A,B}, while each
other point (x, y) of E_{a,d} is mapped to the point (u,
v):=((1+y)/(1y), (1+y)/((1y)*x)) of M_{A,B}.
Implementations may take advantage of this mapping to carry out
elliptic curve group operations originally defined for a twisted
Edwards curve on the corresponding Montgomery curve, or viceversa,
and translating the result back to the original curve, thereby
potentially allowing code reuse.
C.2. Mapping between Montgomery Curves and Weierstrass Curves
+D.2. Mapping between Montgomery Curves and Weierstrass Curves
One can map points of the Montgomery curve M_{A,B} to points of the
Weierstrass curve W_{a,b}, where a:=(3A^2)/(3*B^2) and
b:=(2*A^39*A)/(27*B^3). This defines a onetoone correspondence,
which  in fact  is an isomorphism between M_{A,B} and W_{a,b},
thereby showing that, e.g., the discrete logarithm problem in either
curve model is equally hard.
The mapping from M_{A,B} to W_{a,b} is defined by mapping the point
at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while
@@ 415,68 +663,70 @@
B+A/(3*B), v/B) of W_{a,b}. Note that not all Weierstrass curves can
be injectively mapped to Montgomery curves, since the latter have a
point of order two and the former may not. In particular, if a
Weierstrass curve has prime order, such as is the case with the so
called "NIST curves", this inverse mapping is not defined.
This mapping can be used to implement elliptic curve group operations
originally defined for a twisted Edwards curve or for a Montgomery
curve using group operations on the corresponding elliptic curve in
shortWeierstrass form and translating the result back to the
 original curve, thereby potentially allowing code reuse. Note that
 implementations for elliptic curves with shortWeierstrass form that
 hardcode the domain parameter a to a= 3 (which value is known to
 allow more efficient implementations) cannot always be used this way,
 since the curve W_{a,b} may not always be expressed in terms of a
 Weierstrass curve with a=3 via a coordinate transformation.
+ original curve, thereby potentially allowing code reuse.
C.3. Mapping between twisted Edwards Curves and Weierstrass Curves
+ Note that implementations for elliptic curves with shortWeierstrass
+ form that hardcode the domain parameter a to a= 3 (which value is
+ known to allow more efficient implementations) cannot always be used
+ this way, since the curve W_{a,b} resulting from an isomorphic
+ mapping cannot always be expressed as a Weierstrass curve with a=3
+ via a coordinate transformation. For more details, see Appendix F.
+
+D.3. Mapping between twisted Edwards Curves and Weierstrass Curves
One can map points of the twisted Edwards curve E_{a,d} to points of
the Weierstrass curve W_{a,b}, via function composition, where one
uses the isomorphic mapping between twisted Edwards curve and
 Montgomery curves of Appendix C.1 and the one between Montgomery and
 Weierstrass curves of Appendix C.2. Obviously, one can use function
+ Montgomery curves of Appendix D.1 and the one between Montgomery and
+ Weierstrass curves of Appendix D.2. Obviously, one can use function
composition (now using the respective inverses) to realize the
inverse of this mapping.
Appendix D. Curve25519 and Cousins
+Appendix E. Curve25519 and Cousins
D.1. Curve Definition and Alternative Representations
+E.1. Curve Definition and Alternative Representations
The elliptic curve Curve25519 is the Montgomery curve M_{A,B} defined
over the prime field GF(p), with p:=2^{255}19, where A:=486662 and
B:=1. This curve has order h*n, where h=8 and where n is a prime
number. For this curve, A^24 is not a square in GF(p), whereas A+2
is. The quadratic twist of this curve has order h1*n1, where h1=4
and where n1 is a prime number. For this curve, the base point is
the point (Gu,Gv), where Gu=9 and where Gv is an odd integer in the
interval [0, p1].
This curve has the same group structure as (is "isomorphic" to) the
twisted Edwards curve E_{a,d} defined over GF(p), with as base point
 the point (Gx,Gy), where parameters are as specified in Appendix D.3.
+ the point (Gx,Gy), where parameters are as specified in Appendix E.3.
This curve is denoted as Edwards25519. For this curve, the parameter
a is a square in GF(p), whereas d is not, so the group laws of
 Appendix B.3 apply.
+ Appendix C.3 apply.
The curve is also isomorphic to the elliptic curve W_{a,b} in short
Weierstrass form defined over GF(p), with as base point the point
 (Gx',Gy'), where parameters are as specified in Appendix D.3. This
+ (Gx',Gy'), where parameters are as specified in Appendix E.3. This
curve is denoted as Wei25519.
D.2. Switching between Alternative Representations
+E.2. Switching between Alternative Representations
Each affine point (u,v) of Curve25519 corresponds to the point
(x,y):=(u + A/3,y) of Wei25519, while the point at infinity of
Curve25519 corresponds to the point at infinity of Wei25519. (Here,
 we used the mapping of Appendix C.2.) Under this mapping, the base
+ we used the mapping of Appendix D.2.) Under this mapping, the base
point (Gu,Gv) of Curve25519 corresponds to the base point (Gx',Gy')
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
@@ 495,48 +745,48 @@
defined by
c sqrt((A+2))
51042569399160536130206135233146329284152202253034631822681833788
666877215207
(=0x70d9120b 9f5ff944 2d84f723 fc03b081 3a5e2c2e b482e57d
3391fb55 00ba81e7)
 (Here, we used the mapping of Appendix C.1.) The inverse mapping
+ (Here, we used the mapping of Appendix D.1.) The inverse mapping
from Edwards25519 to Curve25519 is defined by mapping the point (0,
1) and the point (0, 1) of order two of Edwards25519 to,
respectively, the point at infinity and the point (0,0) of order two
of Curve25519 and having each other point (x, y) of Edwards25519
correspond to the point ((1 + y)/(1  y), c*(1 + y)/((1y)*x)).
The curve Edwards25519 is isomorphic to the Weierstrass curve
Wei25519, where the base point (Gx,Gy) of Edwards25519 corresponds to
the base point (Gx',Gy') of Wei25519 and where the identity element
(0,1) and the point (0,1) of order two of Edwards25519 correspond
to, respectively, the point at infinity O and the point (A/3, 0) of
order two of Wei25519 and where each other point (x, y) of
Edwards25519 corresponds to the point (x', y'):=((1+y)/(1y)+A/3,
c*(1+y)/((1y)*x)) of Wei25519, where c was defined before. (Here,
 we used the mapping of Appendix C.3.) The inverse mapping from
+ we used the mapping of Appendix D.3.) The inverse mapping from
Wei25519 to Edwards25519 is defined by mapping the point at infinity
O and the point (A/3, 0) of order two of Wei25519 to, respectively,
the identity element (0,1) and the point (0,1) of order two of
Edwards25519 and having each other point (x, y) of Wei25519
correspond to the point (c*(3*xA)/(3*y), (3*xA3)/(3*xA+3)).
Note that these mappings can be easily realized in projective
coordinates, using a few field multiplications only, thus allowing
switching between alternative representations with negligible
relative incremental cost.
D.3. Domain Parameters
+E.3. Domain Parameters
The parameters of the Montgomery curve and the corresponding
isomorphic curves in twisted Edwards curve and shortWeierstrass form
are as indicated below. Here, the domain parameters of the
Montgomery curve Curve25519 and of the twisted Edwards curve
Edwards25519 are as specified in RFC 7748; the domain parameters of
Wei25519 are "new".
General parameters (for all curve models):
@@ 617,207 +868,208 @@
(=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa
aaaaaaaa aaad245a)
Gy' 14781619447589544791020593568409986887264606134616475288964881837
755586237401
(=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2
29e9c5a2 7eced3d9)
Appendix E. Further Mappings
+Appendix F. Further Mappings
The nonbinary curves specified in Appendix A are expressed in
different curve models, viz. as curves in shortWeierstrass form, as
Montgomery curves, or as twisted Edwards curves. Within each curve
model, further mappings exist that induce a mapping between elliptic
curves within each curve model. This can be exploited to force some
 of the domain parameter to a value that allows a more efficient
+ of the domain parameters to a value that allows a more efficient
implementation of the addition formulae.
E.1. Isomorphic Mapping between Weierstrass Curves
+F.1. Isomorphic Mapping between Weierstrass Curves
One can map points of the Weierstrass curve W_{a,b} to points of the
Weierstrass curve W_{a',b'}, where a:=a'*s^4 and b:=b'*s^6 for some
 nonzero value u of the finite field GF(q). This defines a onetoone
+ nonzero value s of the finite field GF(q). This defines a onetoone
correspondence, which  in fact  is an isomorphism between W_{a,b}
and W_{a',b'}, thereby showing that, e.g., the discrete logarithm
problem in either curve model is equally hard.
The mapping from W_{a,b} to W_{a',b'} is defined by mapping the point
at infinity O of W_{a,b} to the point at infinity O of W_{a',b'},
while mapping each other point (x, y) of W_{a,b} to the point (x',
y'):=(x*s^2, y*s^3) of W_{a',b'}. The inverse mapping from W_{a',b'}
to W_{a,b} is defined by mapping the point at infinity O of W_{a',b'}
to the point at infinity O of W_{a,b}, while mapping each other point
(x', y') of W_{a',b'} to the point (x, y):=(x/s^2, y/s^3) of W_{a,b}.
Implementations may take advantage of this mapping to carry out
elliptic curve group operations originally defined for a Weierstrass
curve with a generic domain parameter a on a corresponding isomorphic
Weierstrass curve with domain parameter a' that has a special form,
which is known to allow for more efficient implementations of
addition laws, and translating the result back to the original curve.
In particular, it is known that such efficiency improvements exist if
a'=3 (mod p) and one uses socalled Jacobian coordinates with a
 particular projective version of the addition laws of Appendix B.1.
+ particular projective version of the addition laws of Appendix C.1.
While not all Weierstrass curves can be put into this form, all
traditional NIST curves have domain parameter a=3, while all
Brainpool curves [RFC5639] are isomorphic to a Weierstrass curve of
 this form. For details, we refer to Section 3.1.5 of [GECC].
+ this form.
Note that implementations for elliptic curves with shortWeierstrass
 form that hardcode the domain parameter a to a= 3 (which value is
 known to allow more efficient implementations) cannot always be used
 this way, since the curve W_{a,b} may not always be expressed in
+ form that hardcode the domain parameter a to a= 3 cannot always be
+ used this way, since the curve W_{a,b} cannot always be expressed in
terms of a Weierstrass curve with a'=3 via a coordinate
 transformation: this only holds if a'/a is a fourth power in GF(q).
 However, even in this case, one can still express the curve W_{a,b}
 in terms of a Weierstrass curve with a small a' domain parameter,
 thereby still allowing a more efficient implementation than with a
 general a value.
+ transformation: this only holds if a'/a is a fourth power in GF(q)
+ (see Section 3.1.5 of [GECC]). However, even in this case, one can
+ still express the curve W_{a,b} as a Weierstrass curve with a small
+ domain parameter value a', thereby still allowing a more efficient
+ implementation than with a general domain parameter value a.
E.2. Isogeneous Mapping between Weierstrass Curves
+F.2. Isogenous Mapping between Weierstrass Curves
One can still map points of the Weierstrass curve W_{a,b} to points
of the Weierstrass curve W_{a',b'}, where a':=3 (mod p), even if
a'/a is not a fourth power in GF(q). In that case, this mappping
 cannot be an isomorphism (see Appendix E.1) and, thereby, does not
 define a onetoone correspondence. Instead, the mapping is a so
 called isogeny (or homomorphism). Since most elliptic curve
+ cannot be an isomorphism (see Appendix F.1). Instead, the mapping is
+ a socalled isogeny (or homomorphism). Since most elliptic curve
operations process points of prime order or use socalled "cofactor
multiplication", in practice the resulting mapping has similar
 properties. In particular, one can still take advantage of this
 mapping to carry out elliptic curve group operations originally
 defined for a Weierstrass curve with domain parameter a unequal to 3
 (mod p) on a corresponding isogenous Weierstrass curve with domain
 parameter a'=3 (mod p) and translating the result back to the
 original curve.
+ properties as an isomorphism. In particular, one can still take
+ advantage of this mapping to carry out elliptic curve group
+ operations originally defined for a Weierstrass curve with domain
+ parameter a unequal to 3 (mod p) on a corresponding isogenous
+ Weierstrass curve with domain parameter a'=3 (mod p) and translating
+ the result back to the original curve.
In this case, the mapping from W_{a,b} to W_{a',b'} is defined by
mapping the point at infinity O of W_{a,b} to the point at infinity O
of W_{a',b'}, while mapping each other point (x, y) of W_{a,b} to the
point (x', y'):=(u(x)/w(x)^2, y*v(x)/w(x)^3) of W_{a',b'}. Here,
u(x), v(x), and w(x) are polynomials that depend on the isogeny in
question. The inverse mapping from W_{a',b'} to W_{a,b} is again an
isogeny and defined by mapping the point at infinity O of W_{a',b'}
to the point at infinity O of W_{a,b}, while mapping each other point
(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 that depend on the isogeny in question. These
mappings have the property that their composition is not the identity
mapping (as is the case with the isomorphic mappings discussed in
 Appendix E.1), but rather a fixed multiple hereof: if this multiple
+ Appendix F.1), but rather a fixed multiple hereof: if this multiple
is l then the isogeny is called an isogeny of degree l (or 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
 compute this mapping are outside scope of this document (for this,
+ determine isogenies are outside scope of this document (for this,
contact the author of this document).
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 isogeneous
+ 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 B.1. Since all traditional
+ version of the addition laws of Appendix C.1. Since all traditional
NIST curves have domain parameter a=3, while all Brainpool curves
[RFC5639] are isomorphic to a Weierstrass curve of this form, this
 allows taking advantage of existing generic implementations for these
 curves, provided one switches back and forth to this curve form using
 the isogeneous mapping in question.
+ allows taking advantage of existing implementations for these curves
+ that may have a hardcoded a=3 (mod p) domain parameter, provided one
+ switches back and forth to this curve form using the isogenous
+ mapping in question.
 Note that isogeneous mappings can be easily realized in projective
+ Note that isogenous mappings can be easily realized in projective
coordinates and involves roughly 3*l finite field multiplications,
thus allowing switching between alternative representations at
relative low incremental cost compared to that of elliptic curve
scalar multiplications (provided the isogeny has low degree l).
Note, however, that this does require storage of the polynomial
coefficients of the isogeny and dual isogeny involved. This
illustrates that lowdegree isogenies are to be preferred, since an
lisogeny (usually) requires storing roughly 6*l elements of GF(q).
While there are many isogenies, we therefore only consider those with
the desired property with lowest possible degree.
Appendix F. Further Cousins of Curve25519
+Appendix G. Further Cousins of Curve25519
F.1. Further Alternative Representations
+G.1. Further Alternative Representations
The Weierstrass curve Wei25519 is isomorphic to the Weierstrass curve
 Wei25519.2 defined over GF(p), with as base point the pair (G1x,G1y),
 and isogeneous to the Weierstrass curve Wei25519.3 defined over
 GF(p), with as base point the pair (G2x, G2y), where parameters are
 as specified in Appendix F.3 and where the related mappings are as
 specified in Appendix F.2.
+ Wei25519.2 defined over GF(p), with as base point the pair
+ (G1x',G1y'), and isogenous to the Weierstrass curve Wei25519.3
+ defined over GF(p), with as base point the pair (G2x', G2y'), where
+ parameters are as specified in Appendix G.3 and where the related
+ mappings are as specified in Appendix G.2.
F.2. Further Switching
+G.2. Further Switching
Each affine point (x,y) of Wei25519 corresponds to the point
(x',y'):=(x*s^2,y*s^3) of Wei25519.2, where s is the element of GF(p)
defined by
s 20343593038935618591794247374137143598394058341193943326473831977
39407761440
(=0x047f6814 6d568b44 7e4552ea a5ed633d 02d62964 a2b0a120
5e7941e9 375de020),
while the point at infinity of Wei25519 corresponds to the point at
 infinity of Wei25519.2. (Here, we used the mapping of Appendix E.1.)
+ infinity of Wei25519.2. (Here, we used the mapping of Appendix F.1.)
Under this mapping, the base point (Gx',Gy') of Wei25519 corresponds
to the base point (G1x',G1y') of Wei25519.2. The inverse mapping
maps the affine point (x',y') of Wei25519.2 to (x,y):=(x'/s^2,y'/s^3)
of Wei25519, while mapping the point at infinity of Wei25519.2 to the
point at infinity of Wei25519. Note that this mapping (and its
inverse) involves a modular multiplication of both coordinates with
fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which
can be precomputed.
Each affine point (x,y) of Wei25519 corresponds to the point
(x',y'):=(x1/t^2,y1/t^3) of Wei25519.3, where
(x1,y1)=(u(x)/w(x)^2,y*v(x)/w(x)^3), where u, v, and w are the
 polynomials with coefficients in GF(p) as defined in Appendix G and
+ polynomials with coefficients in GF(p) as defined in Appendix H.1 and
where t is the element of GF(p) defined by
t 26012855558634277483276064234565597076862996895623795164528458073
435568115620
(=0x3982c126 59ad1749 ab8bc495 bb1a9d64 c9deffc5 e7b8e601
a5651992 07d48fa4),
while the point at infinity of Wei25519 corresponds to the point at
 infinity of Wei25519.3. (Here, we used the isogeneous mapping of
 Appendix E.2.) Under this isogeneous mapping, the base point
+ infinity of Wei25519.3. (Here, we used the isogenous mapping of
+ Appendix F.2.) Under this isogenous mapping, the base point
(Gx',Gy') of Wei25519 corresponds to the base point (G2x',G2y') of
Wei25519.3. The dual isogeny maps the affine point (x',y') of
Wei25519.3 to to (x,y):=(u'(x1)/w'(x1)^2,y1*v'(x1)/w'(x1)^3) of
Wei25519, where (x1,y1)=(x'*t^2,y'*t^3) and where u', v', and w' are
 the polynomials with coefficients in GF(p) as defined in Appendix G,
 while mapping the point at infinity of Wei25519.3 to the point at
 infinity of Wei25519. Under this dual isogeneous mapping, the base
 point (G2x',G2y') 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 E.1). 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 5%
 relative incremental cost compared to the cost of an elliptic curve
 scalar multiplication).
+ the polynomials with coefficients in GF(p) as defined in
+ Appendix H.2, while mapping the point at infinity of Wei25519.3 to
+ the point at infinity of Wei25519. Under this dual isogenous
+ mapping, the base point (G2x',G2y') 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.1). 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 incremental cost compared to the cost of an
+ elliptic curve scalar multiplication).
F.3. Further Domain Parameters
+G.3. Further Domain Parameters
The parameters of the Weierstrass curve with a=2 that is isomorphic
with Wei25519 and the parameters of the Weierstrass curve with a=3
 that is isogeneous with Wei25519 are as indicated below. Both domain
+ that is isogenous with Wei25519 are as indicated below. Both domain
parameter sets can be exploited directly to derive more efficient
point addition formulae, should an implementation facilitate this.
+ General parameters: same as for Wei25519 (see Appendix E.3)
+
Weierstrass curvespecific parameters (for Wei25519.2, i.e., with
a=2):
a 2 (=0x02)
b 12102640281269758552371076649779977768474709596484288167752775713
178787220689
(=0x1ac1da05 b55bc146 33bd39e4 7f94302e f19843dc f669916f
6a5dfd01 65538cd1)
@@ 849,37 +1100,38 @@
796e1022 40891faa)
G2x' 538371792299408724349427232574807773704511272123391981336972078
46219400243292
(=0x7706c37b 5a84128a 3884a5d7 1811f1b5 5da3230f fb17a8ab
0b32e48d 31a6685c)
G2y' 695480730911001844144020555292799703925148674228551417730708041
8460388229929
+
(=0x0f60480c 7a5c0e11 40340adc 79d6a2bf 0cb57ad0 49d025dc
38d80c77 985f0329)
Appendix G. Isogeny Details
+Appendix H. Isogeny Details
The isogeny and dual isogeny are both isogenies with degree l=47.
Both are specified by a triple of polynomials u, v, and w (resp. u',
v', and w') of degree 47, 69, and 23, respectively, with coefficients
in GF(p). The coeffients of each of these polynomials are specified
 in Appendix G.1 (for the isogeny) and in Appendix G.2 (for the dual
+ in Appendix H.1 (for the isogeny) and in Appendix H.2 (for the dual
isogeny). For each polynomial in variable x, the coefficients are
tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in
hexadecimal format.
G.1. Isogeny Parameters
+H.1. Isogeny Parameters
G.1.1. Coefficients of u(x):
+H.1.1. Coefficients of u(x)
0 0x670ed14828b6f1791ceb3a9cc0edfe127dee8729c5a72ddf77bb1abaebbba1e8
1 0x1135ca8bd5383cb3545402c8bce2ced14b45c29b241e4751b035f27524a9f932
2 0x3223806ff5f669c430efd74df8389f058d180e2fcffa5cdef3eacecdd2c34771
3 0x31b8fecf3f17a819c228517f6cd9814466c8c8bea2efccc47a29bfc14c364266
4 0x2541305c958c5a326f44efad2bec284e7abee840fadb08f2d994cd382fd8ce42
@@ 961,21 +1213,21 @@
43 0x573453fb2b093016f3368356c786519d54ed05f5372c01723b4da520597ec217
44 0x77f5c605bdb3a30d7d9c8840fce38650910d4418eed707a212c8927f41c2c812
45 0x16d6b9f7ff57ca32350057de1204cc6d69d4ef1b255dfef8080118e2fef6ace3
46 0x34e8595832a4021f8b5744014c6b4f7da7df0d0329e8b6b4d44c8fadad6513b7
47 0x1
G.1.2. Coefficients of v(x):
+H.1.2. Coefficients of v(x)
0 0xf9f5eb7134e6f8dafa30c45afa58d7bfc6d4e3ccbb5de87b562fd77403972b2
1 0x36c2dcd9e88f0d2d517a15fc453a098bbbb5a05eb6e8da906fae418a4e1a13f7
2 0xb40078302c24fa394a834880d5bf46732ca1b4894172fb7f775821276f558b3
3 0x53dd8e2234573f7f3f7df11e90a7bdd7b75d807f9712f521d4fb18af59aa5f26
4 0x6d4d7bb08de9061988a8cf6ff3beb10e933d4d2fbb8872d256a38c74c8c2ceda
@@ 1100,21 +1352,21 @@
65 0x537f58d52d18ce5b1d5a6bd3a420e796e64173491ad43dd4d1083a7dcc7dd201
66 0x49c2f6afa93fdcc4e0f8128a8b06da4c75049be14edf3e103821ab604c60f8ae
67 0x10a333eabd6135aeaa3f5f5f7e73d102e4fd7e4bf0902fc55b00da235fa1ad08
68 0xf5c86044bf6032f5102e601f2a0f73c7bce9384bedd120f3e72d78484179d9c
69 0x1
G.1.3. Coefficients of w(x):
+H.1.3. Coefficients of w(x)
0 0x3da24d42421264f30939ff00203880f2b017eb3fecf8933ae61e18df8c8ba116
1 0x457f20bc393cdc9a66848ce174e2fa41d77e6dbae05a317a1fb6e3ae78760f8
2 0x7f608a2285c480d5c9592c435431fae94695beef79d770bb6d029c1d10a53295
3 0x3832accc520a485100a0a1695792465142a5572bed1b2e50e1f8f662ac7289bb
4 0x2df1b0559e31b328eb34beedd5e537c3f4d7b9befb0749f75d6d0d866d26fbaa
@@ 1149,32 +1401,31 @@
19 0x33e4cab64ed8a00d8012104fe8f928e6173c428eff95bbbe569ea46126a4f3cd
20 0x50555b6f07e308d33776922b6566829d122e19b25b7bbacbb0a4b1a7dc40192
21 0x533fa4bf1e2a2aae2f979065fdbb5b667ede2f85543fddbba146aa3a4ef2d281
22 0x5a742cac1952010fc5aba200a635a7bed3ef868194f45b5a6a2647d6d6b289d2
23 0x1
G.2. Dual Isogeny Parameters
+H.2. Dual Isogeny Parameters
G.2.1. Coefficients of u'(x):
+H.2.1. Coefficients of u'(x)
0 0xf0eddb584a20aaac8f1419efdd02a5cca77b21e4cfae78c49b5127d98bc5882
1 0x7115e60d44a58630417df33dd45b8a546fa00b79fea3b2bdc449694bade87c0a
2 0xb3f3a6f3c445c7dc1f91121275414e88c32ff3f367ba0edad4d75b7e7b94b65
3 0x1eb31bb333d7048b87f2b3d4ec76d69035927b41c30274368649c87c52e1ab30

4 0x552c886c2044153e280832264066cce2a7da1127dc9720e2a380e9d37049ac64
5 0x4504f27908db2e1f5840b74ae42445298755d9493141f5417c02f04d47797dda
6 0x82c242cce1eb19698a4fa30b5affe64e5051c04ae8b52cb68d89ee85222e628
7 0x480473406add76cf1d77661b3ff506c038d9cdd5ad6e1ea41969430bb876d223
8 0x25f47bb506fba80c79d1763365fa9076d4c4cb6644f73ed37918074397e88588
@@ 1247,28 +1499,27 @@
43 0x5a9d104ae585b94af68eeb16b1349776b601f97b7ce716701645b1a75b68dcf3
44 0x754e014b5e87af035b3d5fe6fb49f4631e32549f6341c6693c5172a6388e273e
45 0x6710d8265118e22eaceba09566c86f642ab42da58c435083a353eaa12d866c39
46 0x6e88ac659ce146c369f8b24c3a49f8dca547827250cf7963a455851cfc4f8d22
47 0x971eb5f253356cd1fde9fb21f4a4902aa5b8d804a2b57ba775dc130181ae2e8
G.2.2. Coefficients of v'(x):
+H.2.2. Coefficients of v'(x)
0 0x43c9b67cc5b16e167b55f190db61e44d48d813a7112910f10e3fd8da85d61d3
1 0x72046db07e0e7882ff3f0f38b54b45ca84153be47a7fd1dd8f6402e17c47966f
2 0x1593d97b65a070b6b3f879fe3dc4d1ef03c0e781c997111d5c1748f956f1ffc0

3 0x54e5fec076b8779338432bdc5a449e36823a0a7c905fd37f232330b026a143a0
4 0x46328dd9bc336e0873abd453db472468393333fbf2010c6ac283933216e98038
5 0x25d0c64de1dfe1c6d5f5f2d98ab637d8b39bcf0d886a23dabac18c80d7eb03ce
6 0x3a175c46b2cd8e2b313dde2d5f3097b78114a6295f283cf58a33844b0c8d8b34
7 0x5cf4e6f745bdd61181a7d1b4db31dc4c30c84957f63cdf163bee5e466a7a8d38
@@ 1386,30 +1638,29 @@
65 0x3468cf6df7e93f7ff1fe1dd7e180a89dec3ed4f72843b4ea8a8d780011a245b2
66 0x68f75a0e2210f52a90704ed5f511918d1f6bcfcd26b462cc4975252369db6e9d
67 0x6220c0699696e9bcab0fe3a80d437519bd2bdf3caef665e106b2dd47585ddd9f
68 0x553ad47b129fb347992b576479b0a89f8d71f1196f83e5eaab5f533a1dd6f6d7
69 0x239aef387e116ec8730fa15af053485ca707650d9f8917a75f22acf6213197df
G.2.3. Coefficients of w'(x):
+H.2.3. Coefficients of w'(x)
0 0x6bd7f1fc5dd51b7d832848c180f019bcbdb101d4b3435230a79cc4f95c35e15e
1 0x17413bb3ee505184a504e14419b8d7c8517a0d268f65b0d7f5b0ba68d6166dd0
2 0x47f4471beed06e5e2b6d5569c20e30346bdba2921d9676603c58e55431572f90
3 0x2af7eaafd04f6910a5b01cdb0c27dca09487f1cd1116b38db34563e7b0b414eb

4 0x57f0a593459732eef11d2e2f7085bf9adf534879ba56f7afd17c4a40d3d3477b
5 0x4da04e912f145c8d1e5957e0a9e44cca83e74345b38583b70840bdfdbd0288ed
6 0x7cc9c3a51a3767d9d37c6652c349adc09bfe477d99f249a2a7bc803c1c5f39ed
7 0x425d7e58b8adf87eebf445b424ba308ee7880228921651995a7eab548180ad49
8 0x48156db5c99248234c09f43fedf509005943d3d5f5d7422621617467b06d314f