draft-ietf-lwig-curve-representations-00.txt   draft-ietf-lwig-curve-representations-01.txt 
lwig R. Struik lwig R. Struik
Internet-Draft Struik Security Consultancy Internet-Draft Struik Security Consultancy
Intended status: Informational October 18, 2018 Intended status: Informational November 06, 2018
Expires: April 21, 2019 Expires: May 10, 2019
Alternative Elliptic Curve Representations Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-00 draft-ietf-lwig-curve-representations-01
Abstract Abstract
This document specifies how to represent Montgomery curves and This document specifies how to represent Montgomery curves and
(twisted) Edwards curves as curves in short-Weierstrass form and (twisted) Edwards curves as curves in short-Weierstrass form and
illustrates how this can be used to implement elliptic curve illustrates how this can be used to carry out elliptic curve
computations using existing implementations that already implement, computations using existing implementations of, e.g., ECDSA and ECDH
e.g., ECDSA and ECDH using NIST prime curves. using NIST prime curves.
Requirements Language Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in RFC "OPTIONAL" in this document are to be interpreted as described in RFC
2119 [RFC2119]. 2119 [RFC2119].
Status of This Memo Status of This Memo
skipping to change at page 1, line 41 skipping to change at page 1, line 41
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 21, 2019. This Internet-Draft will expire on May 10, 2019.
Copyright Notice Copyright Notice
Copyright (c) 2018 IETF Trust and the persons identified as the Copyright (c) 2018 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 3 1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 3
2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 3 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 3
3. Example Uses . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Use of Representation Switches . . . . . . . . . . . . . . . 4
3.1. ECDSA-SHA256-25519 . . . . . . . . . . . . . . . . . . . 4 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 4 4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 5
4. Security Considerations . . . . . . . . . . . . . . . . . . . 4 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 5
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 5 4.3. Specification of ECDSA-SHA256-Wei25519 . . . . . . . . . 5
6. Normative References . . . . . . . . . . . . . . . . . . . . 5 4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 6
Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 6 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 6 6. Security Considerations . . . . . . . . . . . . . . . . . . . 7
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 6 7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 8
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 6 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8
Appendix B. Elliptic Curve Group Operations . . . . . . . . . . 7 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 8
B.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 7 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 8
B.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 7 10.1. Normative References . . . . . . . . . . . . . . . . . . 8
B.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 8 10.2. Informative References . . . . . . . . . . . . . . . . . 9
Appendix C. Relationship Between Curve Models . . . . . . . . . 8 Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 10
C.1. Mapping between twisted Edwards Curves and Montgomery A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 10
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 8 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 10
C.2. Mapping between Montgomery Curves and Weierstrass Curves 9 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 10
C.3. Mapping between twisted Edwards Curves and Weierstrass Appendix B. Elliptic Curve Nomenclature . . . . . . . . . . . . 11
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 10 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 11
Appendix D. Curve25519 and Cousins . . . . . . . . . . . . . . . 10 C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 11
D.1. Curve Definition and Alternative Representations . . . . 10 C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 12
D.2. Switching between Alternative Representations . . . . . . 10 C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 13
D.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 12 Appendix D. Relationship Between Curve Models . . . . . . . . . 14
Appendix E. Further Mappings . . . . . . . . . . . . . . . . . . 14 D.1. Mapping between twisted Edwards Curves and Montgomery
E.1. Isomorphic Mapping between Weierstrass Curves . . . . . . 14 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 14
E.2. Isogeneous Mapping between Weierstrass Curves . . . . . . 15 D.2. Mapping between Montgomery Curves and Weierstrass Curves 14
Appendix F. Further Cousins of Curve25519 . . . . . . . . . . . 16 D.3. Mapping between twisted Edwards Curves and Weierstrass
F.1. Further Alternative Representations . . . . . . . . . . . 16 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 15
F.2. Further Switching . . . . . . . . . . . . . . . . . . . . 16 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 15
F.3. Further Domain Parameters . . . . . . . . . . . . . . . . 17 E.1. Curve Definition and Alternative Representations . . . . 15
Appendix G. Isogeny Details . . . . . . . . . . . . . . . . . . 19 E.2. Switching between Alternative Representations . . . . . . 16
G.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 19 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 17
G.1.1. Coefficients of u(x): . . . . . . . . . . . . . . . . 19 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 19
G.1.2. Coefficients of v(x): . . . . . . . . . . . . . . . . 21 F.1. Isomorphic Mapping between Weierstrass Curves . . . . . . 19
G.1.3. Coefficients of w(x): . . . . . . . . . . . . . . . . 24 F.2. Isogenous Mapping between Weierstrass Curves . . . . . . 20
G.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 25 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 21
G.2.1. Coefficients of u'(x): . . . . . . . . . . . . . . . 25 G.1. Further Alternative Representations . . . . . . . . . . . 21
G.2.2. Coefficients of v'(x): . . . . . . . . . . . . . . . 27 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 22
G.2.3. Coefficients of w'(x): . . . . . . . . . . . . . . . 30 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 23
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 31 Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 24
H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 24
H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 24
H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 26
H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 29
H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 30
H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 30
H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 32
H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 35
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 36
1. Fostering Code Reuse with New Elliptic Curves 1. Fostering Code Reuse with New Elliptic Curves
It is well-known that elliptic curves can be represented using It is well-known that elliptic curves can be represented using
different curve models. Recently, IETF standardized elliptic curves different curve models. Recently, IETF standardized elliptic curves
that are claimed to have better performance and improved robustness that are claimed to have better performance and improved robustness
against "real world" attacks than curves represented in the against "real world" attacks than curves represented in the
traditional "short" Weierstrass model. This draft specifies an traditional "short" Weierstrass model. This document specifies an
alternative representation of points of Curve25519, a so-called alternative representation of points of Curve25519, a so-called
Montgomery curve, and of points of Edwards25519, a so-called twisted Montgomery curve, and of points of Edwards25519, a so-called twisted
Edwards curve, which are both specified in [RFC7748], as points of a Edwards curve, which are both specified in [RFC7748], as points of a
specific so-called "short" Weierstrass curve, called Wei25519. The specific so-called "short" Weierstrass curve, called Wei25519. We
draft also defines how to efficiently switch between these different also define how to efficiently switch between these different
representations. representations.
Use of Wei25519 allows easy definition of signature schemes and key Use of Wei25519 allows easy definition of new signature schemes and
agreement schemes already specified for traditional NIST prime key agreement schemes already specified for traditional NIST prime
curves, thereby allowing easy integration with existing curves, thereby allowing easy integration with existing
specifications, such as NIST SP 800-56a [SP-800-56a], FIPS Pub 186-4 specifications, such as NIST SP 800-56a [SP-800-56a], FIPS Pub 186-4
[FIPS-186-4], and ANSI X9.62-2005 [ANSI-X9.62] and fostering code [FIPS-186-4], and ANSI X9.62-2005 [ANSI-X9.62], and fostering code
reuse on platforms that already implement some of these schemes using reuse on platforms that already implement some of these schemes using
elliptic curve arithmetic for curves in "short" Weierstrass form (see elliptic curve arithmetic for curves in "short" Weierstrass form (see
Appendix B.1). Appendix C.1).
2. Specification of Wei25519 2. Specification of Wei25519
For the specification of Wei25519 and its relationship to Curve25519 For the specification of Wei25519 and its relationship to Curve25519
and Edwards25519, see Appendix D. For further details and background and Edwards25519, see Appendix E. For further details and background
information on elliptic curves, we refer to the other appendices. information on elliptic curves, we refer to the other appendices.
The use of Wei25519 allows reuse of existing generic code that The use of Wei25519 allows reuse of existing generic code that
implements short-Weierstrass curves, such as the NIST curve P256, to implements short-Weierstrass curves, such as the NIST curve P256, to
also implement the CFRG curves Curve25519 and Ed25519. The draft also implement the CFRG curves Curve25519 and Edwards25519. We also
also caters to reuse of existing code where some domain parameters cater to reusing of existing code where some domain parameters may
may have been hardcoded, thereby widening the scope of applicability; have been hardcoded, thereby widening the scope of applicability. To
see Appendix F. this end, we specify the short-Weierstrass curves Wei25519.2 and
Wei25519.-3, with hardcoded domain parameter a=2 and a=-3 (mod p),
respectively; see Appendix G.
3. Example Uses 3. Use of Representation Switches
3.1. ECDSA-SHA256-25519
RFC 8032 [RFC8032] specifies the use of EdDSA, a "full" Schnorr The curves Curve25519, Edwards25519, and Wei25519, as specified in
signature scheme, with instantiation by Edwards25519 and Ed448, two Appendix E.3, are all isomorphic, with the transformations of
so-called twisted Edwards curves. These curves can also be used with Appendix E.2. These transformations map the specified base point of
the widely implemented signature scheme ECDSA [FIPS-186-4], by each of these curves to the specified base point of each of the other
instantiating ECDSA with the curve Wei25519 and hash function SHA- curves. Consequently, a public-key pair (k,R:=k*G) for any one of
256, where "under the hood" an implementation may carry out elliptic these curves corresponds, via these isomorphic mappings, to the
curve scalar multiplication routines using the corresponding public-key pair (k, R':=k*G') for each of these other curves (where G
representations of a point of the curve Wei25519 in Weierstrass form and G' are the corresponding base points of these curves). This
as a point of the Montgomery curve Curve25519 or of the twisted observation extends to the case where one also considers curve
Edwards curve Edwards25519. (The corresponding ECDSA-SHA512-448 Wei25519.2 (which has hardcoded domain parameter a=2), as specified
scheme arises if one were to specify a curve in short-Weierstrass in Appendix G.3, since it is isomorphic to Wei25519, with the
form corresponding to Ed448 and use the hash function SHA512.) Note transformation of Appendix G.2, and, thereby, also isomorphic to
that, in either case, one can implement these schemes with the same Curve25519 and Edwards25519.
representation conventions as used with existing NIST specifications,
including bit/byte-ordering, compression functions, and the-like.
This allows implementations of ECDSA with the hash function SHA-256
and with the NIST curve P-256 or with the curve Wei25519 specified in
this draft to use the same implementation (instantiated with,
respectively, the NIST P-256 elliptic curve domain parameters or with
the domain parameters of curve Wei25519 specified in Appendix D).
3.2. Other Uses The curve Wei25519.-3 (which has hardcoded domain parameter a=-3 (mod
p)) is not isomorphic to the curve Wei25519, but is related in a
slightly weaker sense: the curve Wei25519 is isogenous to the curve
Wei25519.-3, where the mapping of Appendix G.2 is an isogeny of
degree l=47 that maps the specified base point G of Wei25519 to the
specified base point G' of Wei25519.-3 and where the so-called dual
isogeny (which maps Wei25519.-3 to Wei25519) has the same degree
l=47, but does not map G' to G, but to a fixed multiple hereof, where
this multiple is l=47. Consequently, a public-key pair (k,R:=k*G)
for Wei25519 corresponds to the public-key pair (k, R':= k*G') for
Wei25519.-3 (via the l-isogeny), whereas the public-key pair (k,
R':=k*G') corresponds to the public-key pair (l*k, l*R=l*k*G) of
Wei25519 (via the dual isogeny). (Note the extra scalar l=47 here.)
Alternative curve representations can, therefore, be used in any
cryptographic scheme that involves computations on public-private key
pairs, where implementations may carry out computations on the
corresponding object for the isomorphic or isogenous curve and
convert the results back to the original curve (where, in case this
involves an l-isogeny, one has to take into account the factor l).
This includes use with elliptic-curve based signature schemes and key
agreement and key transport schemes.
4. Examples
4.1. Implementation of X25519
RFC 7748 [RFC7748] specifies the use of X25519, a co-factor Diffie-
Hellman key agreement scheme, with instantiation by the Montgomery
curve Curve25519. This key agreement scheme was already specified in
Section 6.1.2.2 of NIST SP 800-56a [SP-800-56a] for elliptic curves
in short Weierstrass form. Hence, one can implement X25519 using
existing NIST routines by (1) representing a point of the Montgomery
curve Curve25519 as a point of the Weierstrass curve Wei25519; (2)
instantiating the co-factor Diffie-Hellman key agreement scheme of
the NIST specification with the resulting point and Wei25519 domain
parameters; (3) representing the key resulting from this scheme
(which is a point of the curve Wei25519 in Weierstrass form) as a
point of the Montgomery curve Curve25519. The representation change
can be implemented via a simple wrapper and involves a single modular
addition (see Appendix D.2). Using this method has the additional
advantage that one can reuse the public-private key pair routines,
domain parameter validation, and other checks that are already part
of the NIST specifications. Note: at this point, it is unclear
whether this implies that a FIPS-accredited module implementing co-
factor Diffie-Hellman for, e.g., P-256 would also extend this
accreditation to X25519.
4.2. Implementation of Ed25519
RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature
scheme, with instantiation by the twisted Edwards curve Edwards25519.
One can implement the computation of the ephemeral key pair for
Ed25519 using an existing Montgomery curve implementation by (1)
generating a public-private key pair (k, R':=k*G') for Curve25519;
(2) representing this public-private key as the pair (k, R:=k*G) for
Ed25519. As before, the representation change can be implemented via
a simple wrapper. Note that the Montgomery ladder specified in
Section 5 of RFC7748 [RFC7748] does not provide sufficient
information to reconstruct R' (since it does not compute the
y-coordinate of R'). However, this deficiency can be remedied by
using a slightly modified version of the Montgomery ladder that
includes reconstruction of the y-coordinate of R':=k*G' at the end of
hereof (which uses the v-coordinate Gv of the base point of
Curve25519 as well). For details, see Appendix D.2.
4.3. Specification of ECDSA-SHA256-Wei25519
FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and
can be instantiated not just with the NIST prime curves, but also
with other Weierstrass curves (that satisfy additional cryptographic
criteria). In particular, one can instantiate this scheme with the
Weierstrass curve Wei25519 and the hash function SHA-256, where an
implementation may generate a public-private key pair for Wei25519 by
(1) internally carrying out these computations on the Montgomery
curve Curve25519, the twisted Edwards curve Edwards25519, or even the
Weierstrass curve Wei25519.-3 (with hardcoded a=-3 domain parameter);
(2) representing the result as a key pair for the curve Wei25519.
Note that, in either case, one can implement these schemes with the
same representation conventions as used with existing NIST
specifications, including bit/byte-ordering, compression functions,
and the-like. This allows implementations of ECDSA with the hash
function SHA-256 and with the NIST curve P-256 or with the curve
Wei25519 specified in this draft to use the same implementation
(instantiated with, respectively, the NIST P-256 elliptic curve
domain parameters or with the domain parameters of curve Wei25519
specified in Appendix E).
4.4. Other Uses
Any existing specification of cryptographic schemes using elliptic Any existing specification of cryptographic schemes using elliptic
curves in Weierstrass form and that allows introduction of a new curves in Weierstrass form and that allows introduction of a new
elliptic curve (here: Wei25519) is amenable to similar constructs, elliptic curve (here: Wei25519) is amenable to similar constructs,
thus spawning "offspring" protocols, simply by instantiating these thus spawning "offspring" protocols, simply by instantiating these
using the new curve in "short" Weierstrass form, thereby allowing using the new curve in "short" Weierstrass form, thereby allowing
code and/or specifications reuse and, for implementations that so code and/or specifications reuse and, for implementations that so
desire, carrying out curve computations "under the hood" on desire, carrying out curve computations "under the hood" on
Montgomery curve and twisted Edwards curve cousins hereof (where Montgomery curve and twisted Edwards curve cousins hereof (where
these exist). This would simply require definition of a new object these exist). This would simply require definition of a new object
identifier for any such envisioned "offspring" protocol. This could identifier for any such envisioned "offspring" protocol. This could
significantly simplify standardization of schemes and help keeping significantly simplify standardization of schemes and help keeping
the resource and maintenance cost of implementations supporting the resource and maintenance cost of implementations supporting
algorithm agility [RFC7696] at bay. algorithm agility [RFC7696] at bay.
4. Security Considerations 5. Caveats
The examples above illustrate how specifying the Weierstrass curve
Wei25519 may facilitate reuse of existing code and may simplify
standards development. However, the following caveats apply:
1. Unfriendly wire formats. The transformations between alternative
curve representations can be implemented at negligible relative
incremental cost if the curve points are represented as affine
points. If a point is represented in compressed format,
conversion usually requires a costly point decompression step.
This is the case in [RFC7748], where the inputs to the co-factor
Diffie-Hellman scheme X25519, as well as its output, are
represented in x-coordinate-only format;
2. Unfriendly representation conventions. While elliptic curve
computations are carried-out in a field GF(q) and, thereby,
involve large integer arithmetic, these integers are represented
as bit- and byte-strings. Here, [RFC8032] uses least-
significant-byte (LSB)/least-significant-bit (lsb) conventions,
whereas [RFC7748] uses LSB/most-significant-bit (msb)
conventions, and where most other cryptographic specifications,
including NIST SP800-56a [SP-800-56a], FIPS Pub 186-4
[FIPS-186-4], and ANSI X9.62-2005 [ANSI-X9.62] use MSB/msb
conventions. Since each pair of conventions is different, this
does necessitate bit/byte representation conversions;
3. Unfriendly domain parameters. All traditional NIST curves are
Weierstrass curve with domain parameter a=-3, while all Brainpool
curves [RFC5639] are isomorphic to a Weierstrass curve of this
form. Thus, one can expect there to be existing Weierstrass
implementations with a hardcoded a=-3 domain parameter
("Jacobian-friendly"). For those implementations, including the
curve Wei25519 as a potential vehicle for offering support for
the CFRG curves Curve25519 and Edwards25519 is not possible,
since not of the required form. Instead, one has to implement
Curve25519.-3 and include code that implements the isogeny and
dual isogeny from and to Wei25519. This isogeny has degree l=47
and requires roughly 9kB of storage for isogeny and dual-isogeny
computations (see the tables in Appendix H). Note that storage
would have reduced to a single 32-bye table if the curve would
have been generated so as to be isomorphic to a Weierstrass curve
with hardcoded a=-3 parameter (this corresponds to l=1). Note:
an example of such a curve is the Montgomery curve M_{A,B} over
GF(p) with p=2^255-19, A=-1410290, and B=1 or (if one wants the
base point to still have u-coordinate u=9) A=-3960846. In either
case, the resulting curve has the same cryptographic properties
as Curve25519, while being more "Jacobian-friendly".
6. Security Considerations
The different representations of elliptic curve points discussed in The different representations of elliptic curve points discussed in
this draft are all obtained using a publicly known transformation. this document are all obtained using a publicly known transformation,
Since this transformation is an isomorphism, this transformation maps which is either an isomorphism or a low-degree isogeny. It is well-
elliptic curve points to equivalent mathematical objects. known that an isomorphism maps elliptic curve points to equivalent
mathematical objects and that the complexity of cryptographic
problems (such as the discrete logarithm problem) of curves related
via a low-degree isogeny are tightly related. Thus, the use of these
techniques does not negatively impact cryptographic security.
5. IANA Considerations As to implementation security, reusing existing high-quality code or
generic implementations that have been carefully designed to
withstand implementation attacks for one curve model may allow a more
economical way of development and maintenance than providing this
same functionality for each curve model separately (if multiple curve
models need to be supported) and, otherwise, may allow a more gradual
migration path, where one may initially use existing and accredited
chipsets that cater to the pre-dominant curve model used in practice
for over 15 years.
7. Privacy Considerations
The transformations between different curve models described in this
document are publicly known and, therefore, do not affect privacy
provisions.
8. IANA Considerations
There is *currently* no IANA action required for this document. New There is *currently* no IANA action required for this document. New
object identifiers would be required in case one wishes to specify object identifiers would be required in case one wishes to specify
one or more of the "offspring" protocols exemplified in Section 3. one or more of the "offspring" protocols exemplified in Section 4.
6. Normative References 9. Acknowledgements
Thanks to Nikolas Rosener for discussions surrounding implementation
details of the techniques described in this document and to Phillip
Hallam-Baker for triggering inclusion of verbiage on the use of
Montgomery ladders with recovery of the y-coordinate.
10. References
10.1. Normative References
[ANSI-X9.62] [ANSI-X9.62]
ANSI X9.62-2005, "Public Key Cryptography for the ANSI X9.62-2005, "Public Key Cryptography for the
Financial Services Industry: The Elliptic Curve Digital Financial Services Industry: The Elliptic Curve Digital
Signature Algorithm (ECDSA)", American National Standard Signature Algorithm (ECDSA)", American National Standard
for Financial Services, Accredited Standards Committee X9, for Financial Services, Accredited Standards Committee X9,
Inc Anapolis, MD, 2005. Inc, Anapolis, MD, 2005.
[FIPS-186-4] [FIPS-186-4]
FIPS 186-4, "Digital Signature Standard (DSS), Federal FIPS 186-4, "Digital Signature Standard (DSS), Federal
Information Processing Standards Publication 186-4", US Information Processing Standards Publication 186-4", US
Department of Commerce/National Institute of Standards and Department of Commerce/National Institute of Standards and
Technology Gaithersburg, MD, July 2013. Technology, Gaithersburg, MD, July 2013.
[GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to
Elliptic Curve Cryptography", New York: Springer-Verlag,
2004.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography [RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography
(ECC) Brainpool Standard Curves and Curve Generation", (ECC) Brainpool Standard Curves and Curve Generation",
RFC 5639, DOI 10.17487/RFC5639, March 2010, RFC 5639, DOI 10.17487/RFC5639, March 2010,
<https://www.rfc-editor.org/info/rfc5639>. <https://www.rfc-editor.org/info/rfc5639>.
skipping to change at page 6, line 9 skipping to change at page 9, line 28
[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
Signature Algorithm (EdDSA)", RFC 8032, Signature Algorithm (EdDSA)", RFC 8032,
DOI 10.17487/RFC8032, January 2017, DOI 10.17487/RFC8032, January 2017,
<https://www.rfc-editor.org/info/rfc8032>. <https://www.rfc-editor.org/info/rfc8032>.
[SP-800-56a] [SP-800-56a]
NIST SP 800-56a, "Recommendation for Pair-Wise Key NIST SP 800-56a, "Recommendation for Pair-Wise Key
Establishment Schemes Using Discrete Log Cryptography, Establishment Schemes Using Discrete Log Cryptography,
Revision 2", US Department of Commerce/National Institute Revision 2", US Department of Commerce/National Institute
of Standards and Technology Gaithersburg, MD, June 2013. of Standards and Technology, Gaithersburg, MD, June 2013.
10.2. Informative References
[ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in
Cryptography", Cambridge University Press, Lecture Notes
Series 265, July 1999.
[ECC-Isogeny]
E. Brier, M. Joye, "Fast Point Multiplication on Elliptic
Curves through Isogenies", AAECC, Lecture Notes in
Computer Science, Vol. 2643, New York: Springer-Verlag,
2003.
[GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to
Elliptic Curve Cryptography", New York: Springer-Verlag,
2004.
[HW-ECC] W.P. Liu, "How to Use the Kinets LTC ECC HW to Accelerate
Curve25519 (version 7)", NXP,
https://community.nxp.com/docs/DOC-330199, April 2017.
Appendix A. Some (non-Binary) Elliptic Curves Appendix A. Some (non-Binary) Elliptic Curves
A.1. Curves in short-Weierstrass Form A.1. Curves in short-Weierstrass Form
Let GF(q) denote the finite field with q elements, where q is an odd Let GF(q) denote the finite field with q elements, where q is an odd
prime power and where q is not divisible by three. Let W_{a,b} be prime power and where q is not divisible by three. Let W_{a,b} be
the Weierstrass curve with defining equation y^2 = x^3 + a*x + b, the Weierstrass curve with defining equation y^2 = x^3 + a*x + b,
where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is
nonzero. The points of W_{a,b} are the ordered pairs (x, y) whose nonzero. The points of W_{a,b} are the ordered pairs (x, y) whose
coordinates are elements of GF(q) and that satisfy the defining coordinates are elements of GF(q) and that satisfy the defining
equation (the so-called affine points), together with the special equation (the so-called affine points), together with the special
point O (the so-called "point at infinity").This set forms a group point O (the so-called "point at infinity").This set forms a group
under addition, via the so-called "chord-and-tangent" rule, where the under addition, via the so-called "secant-and-tangent" rule, where
point at infinity serves as the identity element. See Appendix B.1 the point at infinity serves as the identity element. See
for details of the group operation. Appendix C.1 for details of the group operation.
A.2. Montgomery Curves A.2. Montgomery Curves
Let GF(q) denote the finite field with q elements, where q is an odd Let GF(q) denote the finite field with q elements, where q is an odd
prime power. Let M_{A,B} be the Montgomery curve with defining prime power. Let M_{A,B} be the Montgomery curve with defining
equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q) equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q)
with A unequal to (+/-)2 and with B nonzero. The points of M_{A,B} with A unequal to (+/-)2 and with B nonzero. The points of M_{A,B}
are the ordered pairs (u, v) whose coordinates are elements of GF(q) are the ordered pairs (u, v) whose coordinates are elements of GF(q)
and that satisfy the defining equation (the so-called affine points), and that satisfy the defining equation (the so-called affine points),
together with the special point O (the so-called "point at together with the special point O (the so-called "point at
infinity").This set forms a group under addition, via the so-called infinity").This set forms a group under addition, via the so-called
"chord-and-tangent" rule, where the point at infinity serves as the "secant-and-tangent" rule, where the point at infinity serves as the
identity element. See Appendix B.2 for details of the group identity element. See Appendix C.2 for details of the group
operation. operation.
A.3. Twisted Edwards Curves A.3. Twisted Edwards Curves
Let GF(q) denote the finite field with q elements, where q is an odd Let GF(q) denote the finite field with q elements, where q is an odd
prime power. Let E_{a,d} be the twisted Edwards curve with defining prime power. Let E_{a,d} be the twisted Edwards curve with defining
equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct
nonzero elements of GF(q). The points of E_{a,d} are the ordered nonzero elements of GF(q). The points of E_{a,d} are the ordered
pairs (x, y) whose coordinates are elements of GF(q) and that satisfy pairs (x, y) whose coordinates are elements of GF(q) and that satisfy
the defining equation (the so-called affine points). It can be shown the defining equation (the so-called affine points). It can be shown
that this set forms a group under addition if a is a square in GF(q), that this set forms a group under addition if a is a square in GF(q),
whereas d is not, where the point (0, 1) serves as the identity whereas d is not, where the point (0, 1) serves as the identity
element. (Note that the identity element satisfies the defining element. (Note that the identity element satisfies the defining
equation.) See Appendix B.3 for details of the group operation. An equation.) See Appendix C.3 for details of the group operation.
Edwards curve is a twisted Edwards curve with a=1.
Appendix B. Elliptic Curve Group Operations An Edwards curve is a twisted Edwards curve with a=1.
B.1. Group Law for Weierstrass Curves Appendix B. Elliptic Curve Nomenclature
Each curve defined in Appendix A forms a commutative group under
addition. In Appendix C we specify the group laws, which depend on
the curve model in question. For completeness, we here include some
common elliptic curve nomenclature and basic properties (primarily so
as to keep this document self-contained). These notions are mainly
used in Appendix E and Appendix G and not essential for our
exposition. This section can be skipped at first reading.
Any point P of a curve is a generator of the cyclic subgroup
(P):={k*P | k = 0, 1, 2,...} of the curve. If (P) has cardinality l,
then l is called the order of P. The order of a curve is the
cardinality of the set of its points. A curve is cyclic if it is
generated by some point of this curve. All curves of prime order are
cyclic, while all curves of order |E| = h*n, where n is a large prime
number and where h is a small number (the so-called co-factor), have
a large cyclic subgroup of prime order n. In this case, a generator
of order n is called a base point, commonly denoted by G. A point of
order dividing h is said to be in the small subgroup. For curves of
prime order, this small subgroup is the singleton set, consisting of
only the identity element.
If R is a point on a curve E that is also contained in (P), there is
a unique integer k in the interval [0, l-1] so that R=kP, where l is
the order of P. This number is called the discrete logarithm of R to
the base P. The discrete logarithm problem is the problem of finding
the discrete logarithm of R to the base P for any two points P and R
of the curve, if such a number exists.
A public-private key pair is an ordered pair (k, R:=kG), where G is a
fixed base point of the curve. Here, k (the private key) is an
integer in the interval [0,n-1], where G has order n.
A quadratic twist of a curve E defined over a field GF(q) is a curve
E' related to E, with cardinality |E|+|E'|=2*(q+1). If E is a curve
in one of the curve models specified in this document, a quadratic
twist of this curve can be expressed using the same curve model,
although (naturally) with different curve parameters.
Appendix C. Elliptic Curve Group Operations
C.1. Group Law for Weierstrass Curves
For each point P of the Weierstrass curve W_{a,b}, the point at For each point P of the Weierstrass curve W_{a,b}, the point at
infinity O serves as identity element, i.e., P + O = O + P = P. infinity O serves as identity element, i.e., P + O = O + P = P.
For each affine point P:=(x, y) of the Weierstrass curve W_{a,b}, the For each affine point P:=(x, y) of the Weierstrass curve W_{a,b}, the
point -P is the point (x, -y) and one has P + (-P) = O. point -P is the point (x, -y) and one has P + (-P) = O.
Let P1:=(x1, y1) and P2:=(x2, y2) be distinct affine points of the Let P1:=(x1, y1) and P2:=(x2, y2) be distinct affine points of the
Weierstrass curve W_{a,b} and let Q:=P1 + P2, where Q is not the Weierstrass curve W_{a,b} and let Q:=P1 + P2, where Q is not the
identity element. Then Q:=(x, y), where identity element. Then Q:=(x, y), where
x + x1 + x2 = lambda^2 and y + y1 = lambda*(x1 - x), where lambda x + x1 + x2 = lambda^2 and y + y1 = lambda*(x1 - x), where lambda
= (y2 - y1)/(x2 - x1). = (y2 - y1)/(x2 - x1).
Let P:= (x1, y1) be an affine point of the Weierstrass curve W_{a,b} Let P:= (x1, y1) be an affine point of the Weierstrass curve W_{a,b}
and let Q:=2P, where Q is not the identity element. Then Q:= (x, y), and let Q:=2*P, where Q is not the identity element. Then Q:= (x,
where y), where
x + 2*x1 = lambda^2 and y + y1 = lambda*(x1 - x), where x + 2*x1 = lambda^2 and y + y1 = lambda*(x1 - x), where
lambda=(3*x1^2 + a)/(2*y1). lambda=(3*x1^2 + a)/(2*y1).
B.2. Group Law for Montgomery Curves From the group law above it follows that if P=(x, y), P1=k*P=(x1,
y1), and P2=(k+1)*P=(x2, y2) are affine points of the Weierstrass
curve W_{a,b} and if y is nonzero, then the y-coordinate of P1 can be
expressed in terms of the x-coordinates of P, P1, and P2, and the
y-coordinate of P, as
y1=((x*x1+a)*(x+x1)+2*b-x2*(x-x1)^2)/(2*y).
This property allows recovery of the y-coordinate of a point P1=k*P
that is computed via the so-called Montgomery ladder, where P is an
affine point with nonzero y-coordinate. Further details are out of
scope.
C.2. Group Law for Montgomery Curves
For each point P of the Montgomery curve M_{A,B}, the point at For each point P of the Montgomery curve M_{A,B}, the point at
infinity O serves as identity element, i.e., P + O = O + P = P. infinity O serves as identity element, i.e., P + O = O + P = P.
For each affine point P:=(x, y) of the Montgomery curve M_{A,B}, the For each affine point P:=(x, y) of the Montgomery curve M_{A,B}, the
point -P is the point (x, -y) and one has P + (-P) = O. point -P is the point (x, -y) and one has P + (-P) = O.
Let P1:=(x1, y1) and P2:=(x2, y2) be distinct affine points of the Let P1:=(x1, y1) and P2:=(x2, y2) be distinct affine points of the
Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the
identity element. Then Q:=(x, y), where identity element. Then Q:=(x, y), where
x + x1 + x2 = B*lambda^2 - A and y + y1 = lambda*(x1 - x), where x + x1 + x2 = B*lambda^2 - A and y + y1 = lambda*(x1 - x), where
lambda=(y2 - y1)/(x2 - x1). lambda=(y2 - y1)/(x2 - x1).
Let P:= (x1, y1) be an affine point of the Montgomery curve M_{A,B} Let P:= (x1, y1) be an affine point of the Montgomery curve M_{A,B}
and let Q:=2P, where Q is not the identity element. Then Q:= (x, y), and let Q:=2*P, where Q is not the identity element. Then Q:= (x,
where y), where
x + 2*x1 = B*lambda^2 - A and y + y1 = lambda*(x1 - x), where x + 2*x1 = B*lambda^2 - A and y + y1 = lambda*(x1 - x), where
lambda=(3*x1^2 + 2*A*x1+1)/(2*y1). lambda=(3*x1^2 + 2*A*x1+1)/(2*B*y1).
Alternative and more efficient group laws exist, e.g., when using the From the group law above it follows that if P=(x, y), P1=k*P=(x1,
so-called Montgomery ladder. Details are out of scope. y1), and P2=(k+1)*P=(x2, y2) are affine points of the Montgomery
curve M_{A,B} and if y is nonzero, then the y-coordinate of P1 can be
expressed in terms of the x-coordinates of P, P1, and P2, and the
y-coordinate of P, as
B.3. Group Law for Twisted Edwards Curves y1=((x*x1+1)*(x+x1+2*A)-2*A-x2*(x-x1)^2)/(2*B*y).
This property allows recovery of the y-coordinate of a point P1=k*P
that is computed via the so-called Montgomery ladder, where P is an
affine point with nonzero y-coordinate. Further details are out of
scope.
C.3. Group Law for Twisted Edwards Curves
Note: The group laws below hold for twisted Edwards curves E_{a,d} Note: The group laws below hold for twisted Edwards curves E_{a,d}
where a is a square in GF(q), whereas d is not. In this case, the where a is a square in GF(q), whereas d is not. In this case, the
addition formulae below are defined for each pair of points, without addition formulae below are defined for each pair of points, without
exceptions. Generalizations of this group law to other twisted exceptions. Generalizations of this group law to other twisted
Edwards curves are out of scope. Edwards curves are out of scope.
For each point P of the twisted Edwards curve E_{a,d}, the point For each point P of the twisted Edwards curve E_{a,d}, the point
O=(0,1) serves as identity element, i.e., P + O = O + P = P. O=(0,1) serves as identity element, i.e., P + O = O + P = P.
For each point P:=(x, y) of the twisted Edwards curve E_{a,d}, the For each point P:=(x, y) of the twisted Edwards curve E_{a,d}, the
point -P is the point (-x, y) and one has P + (-P) = O. point -P is the point (-x, y) and one has P + (-P) = O.
Let P1:=(x1, y1) and P2:=(x2, y2) be points of the twisted Edwards Let P1:=(x1, y1) and P2:=(x2, y2) be points of the twisted Edwards
curve E_{a,d} and let Q:=P1 + P2. Then Q:=(x, y), where curve E_{a,d} and let Q:=P1 + P2. Then Q:=(x, y), where
x = (x1*y2 + x2*y1)/(1 + d*x1*x2*y1*y2) and y = (y1*y2 - x = (x1*y2 + x2*y1)/(1 + d*x1*x2*y1*y2) and y = (y1*y2 -
a*x1*x2)/(1 - d*x1*x2*y1*y2). a*x1*x2)/(1 - d*x1*x2*y1*y2).
Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and
let Q:=2P. Then Q:=(x, y), where let Q:=2*P. Then Q:=(x, y), where
x = (2*x1*y1)/(1 + d*x1^2*y1^2) and y = (y1^2 - a*x1^2)/(1 - x = (2*x1*y1)/(1 + d*x1^2*y1^2) and y = (y1^2 - a*x1^2)/(1 -
d*x1^2*y1^2). d*x1^2*y1^2).
Note that one can use the formulae for point addition to implement Note that one can use the formulae for point addition for
point doubling, taking inverses and adding the identity element as implementing point doubling, taking inverses and adding the identity
well (i.e., the point addition formulae are uniform and complete element as well (i.e., the point addition formulae are uniform and
(subject to our Note above)). complete (subject to our Note above)).
Appendix C. Relationship Between Curve Models Appendix D. Relationship Between Curve Models
The non-binary curves specified in Appendix A are expressed in The non-binary curves specified in Appendix A are expressed in
different curve models, viz. as curves in short-Weierstrass form, as different curve models, viz. as curves in short-Weierstrass form, as
Montgomery curves, or as twisted Edwards curves. These curve models Montgomery curves, or as twisted Edwards curves. These curve models
are related, as follows. are related, as follows.
C.1. Mapping between twisted Edwards Curves and Montgomery Curves D.1. Mapping between twisted Edwards Curves and Montgomery Curves
One can map points of the Montgomery curve M_{A,B} to points of the One can map points of the Montgomery curve M_{A,B} to points of the
twisted Edwards curve E_{a,d}, where a:=(A+2)/B and d:=(A-2)/B and, twisted Edwards curve E_{a,d}, where a:=(A+2)/B and d:=(A-2)/B and,
conversely, map points of the twisted Edwards curve E_{a,d} to points conversely, map points of the twisted Edwards curve E_{a,d} to points
of the Montgomery curve M_{A,B}, where A:=2(a+d)/(a-d) and where of the Montgomery curve M_{A,B}, where A:=2(a+d)/(a-d) and where
B:=4/(a-d). For twisted Edwards curves we consider (i.e., those B:=4/(a-d). For twisted Edwards curves we consider (i.e., those
where a is a square in GF(q), whereas d is not), this defines a one- where a is a square in GF(q), whereas d is not), this defines a one-
to-one correspondence, which - in fact - is an isomorphism between to-one correspondence, which - in fact - is an isomorphism between
M_{A,B} and E_{a,d}, thereby showing that, e.g., the discrete M_{A,B} and E_{a,d}, thereby showing that, e.g., the discrete
logarithm problem in either curve model is equally hard. logarithm problem in either curve model is equally hard.
skipping to change at page 9, line 27 skipping to change at page 14, line 42
infinity O and the point (0, 0) of order two of M_{A,B}, while each infinity O and the point (0, 0) of order two of M_{A,B}, while each
other point (x, y) of E_{a,d} is mapped to the point (u, other point (x, y) of E_{a,d} is mapped to the point (u,
v):=((1+y)/(1-y), (1+y)/((1-y)*x)) of M_{A,B}. v):=((1+y)/(1-y), (1+y)/((1-y)*x)) of M_{A,B}.
Implementations may take advantage of this mapping to carry out Implementations may take advantage of this mapping to carry out
elliptic curve group operations originally defined for a twisted elliptic curve group operations originally defined for a twisted
Edwards curve on the corresponding Montgomery curve, or vice-versa, Edwards curve on the corresponding Montgomery curve, or vice-versa,
and translating the result back to the original curve, thereby and translating the result back to the original curve, thereby
potentially allowing code reuse. potentially allowing code reuse.
C.2. Mapping between Montgomery Curves and Weierstrass Curves D.2. Mapping between Montgomery Curves and Weierstrass Curves
One can map points of the Montgomery curve M_{A,B} to points of the One can map points of the Montgomery curve M_{A,B} to points of the
Weierstrass curve W_{a,b}, where a:=(3-A^2)/(3*B^2) and Weierstrass curve W_{a,b}, where a:=(3-A^2)/(3*B^2) and
b:=(2*A^3-9*A)/(27*B^3). This defines a one-to-one correspondence, b:=(2*A^3-9*A)/(27*B^3). This defines a one-to-one correspondence,
which - in fact - is an isomorphism between M_{A,B} and W_{a,b}, which - in fact - is an isomorphism between M_{A,B} and W_{a,b},
thereby showing that, e.g., the discrete logarithm problem in either thereby showing that, e.g., the discrete logarithm problem in either
curve model is equally hard. curve model is equally hard.
The mapping from M_{A,B} to W_{a,b} is defined by mapping the point The mapping from M_{A,B} to W_{a,b} is defined by mapping the point
at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while
skipping to change at page 9, line 49 skipping to change at page 15, line 15
B+A/(3*B), v/B) of W_{a,b}. Note that not all Weierstrass curves can B+A/(3*B), v/B) of W_{a,b}. Note that not all Weierstrass curves can
be injectively mapped to Montgomery curves, since the latter have a be injectively mapped to Montgomery curves, since the latter have a
point of order two and the former may not. In particular, if a point of order two and the former may not. In particular, if a
Weierstrass curve has prime order, such as is the case with the so- Weierstrass curve has prime order, such as is the case with the so-
called "NIST curves", this inverse mapping is not defined. called "NIST curves", this inverse mapping is not defined.
This mapping can be used to implement elliptic curve group operations This mapping can be used to implement elliptic curve group operations
originally defined for a twisted Edwards curve or for a Montgomery originally defined for a twisted Edwards curve or for a Montgomery
curve using group operations on the corresponding elliptic curve in curve using group operations on the corresponding elliptic curve in
short-Weierstrass form and translating the result back to the short-Weierstrass form and translating the result back to the
original curve, thereby potentially allowing code reuse. Note that original curve, thereby potentially allowing code reuse.
implementations for elliptic curves with short-Weierstrass form that
hard-code the domain parameter a to a= -3 (which value is known to
allow more efficient implementations) cannot always be used this way,
since the curve W_{a,b} may not always be expressed in terms of a
Weierstrass curve with a=-3 via a coordinate transformation.
C.3. Mapping between twisted Edwards Curves and Weierstrass Curves Note that implementations for elliptic curves with short-Weierstrass
form that hard-code the domain parameter a to a= -3 (which value is
known to allow more efficient implementations) cannot always be used
this way, since the curve W_{a,b} resulting from an isomorphic
mapping cannot always be expressed as a Weierstrass curve with a=-3
via a coordinate transformation. For more details, see Appendix F.
D.3. Mapping between twisted Edwards Curves and Weierstrass Curves
One can map points of the twisted Edwards curve E_{a,d} to points of One can map points of the twisted Edwards curve E_{a,d} to points of
the Weierstrass curve W_{a,b}, via function composition, where one the Weierstrass curve W_{a,b}, via function composition, where one
uses the isomorphic mapping between twisted Edwards curve and uses the isomorphic mapping between twisted Edwards curve and
Montgomery curves of Appendix C.1 and the one between Montgomery and Montgomery curves of Appendix D.1 and the one between Montgomery and
Weierstrass curves of Appendix C.2. Obviously, one can use function Weierstrass curves of Appendix D.2. Obviously, one can use function
composition (now using the respective inverses) to realize the composition (now using the respective inverses) to realize the
inverse of this mapping. inverse of this mapping.
Appendix D. Curve25519 and Cousins Appendix E. Curve25519 and Cousins
D.1. Curve Definition and Alternative Representations E.1. Curve Definition and Alternative Representations
The elliptic curve Curve25519 is the Montgomery curve M_{A,B} defined The elliptic curve Curve25519 is the Montgomery curve M_{A,B} defined
over the prime field GF(p), with p:=2^{255}-19, where A:=486662 and over the prime field GF(p), with p:=2^{255}-19, where A:=486662 and
B:=1. This curve has order h*n, where h=8 and where n is a prime B:=1. This curve has order h*n, where h=8 and where n is a prime
number. For this curve, A^2-4 is not a square in GF(p), whereas A+2 number. For this curve, A^2-4 is not a square in GF(p), whereas A+2
is. The quadratic twist of this curve has order h1*n1, where h1=4 is. The quadratic twist of this curve has order h1*n1, where h1=4
and where n1 is a prime number. For this curve, the base point is and where n1 is a prime number. For this curve, the base point is
the point (Gu,Gv), where Gu=9 and where Gv is an odd integer in the the point (Gu,Gv), where Gu=9 and where Gv is an odd integer in the
interval [0, p-1]. interval [0, p-1].
This curve has the same group structure as (is "isomorphic" to) the This curve has the same group structure as (is "isomorphic" to) the
twisted Edwards curve E_{a,d} defined over GF(p), with as base point twisted Edwards curve E_{a,d} defined over GF(p), with as base point
the point (Gx,Gy), where parameters are as specified in Appendix D.3. the point (Gx,Gy), where parameters are as specified in Appendix E.3.
This curve is denoted as Edwards25519. For this curve, the parameter This curve is denoted as Edwards25519. For this curve, the parameter
a is a square in GF(p), whereas d is not, so the group laws of a is a square in GF(p), whereas d is not, so the group laws of
Appendix B.3 apply. Appendix C.3 apply.
The curve is also isomorphic to the elliptic curve W_{a,b} in short- The curve is also isomorphic to the elliptic curve W_{a,b} in short-
Weierstrass form defined over GF(p), with as base point the point Weierstrass form defined over GF(p), with as base point the point
(Gx',Gy'), where parameters are as specified in Appendix D.3. This (Gx',Gy'), where parameters are as specified in Appendix E.3. This
curve is denoted as Wei25519. curve is denoted as Wei25519.
D.2. Switching between Alternative Representations E.2. Switching between Alternative Representations
Each affine point (u,v) of Curve25519 corresponds to the point Each affine point (u,v) of Curve25519 corresponds to the point
(x,y):=(u + A/3,y) of Wei25519, while the point at infinity of (x,y):=(u + A/3,y) of Wei25519, while the point at infinity of
Curve25519 corresponds to the point at infinity of Wei25519. (Here, Curve25519 corresponds to the point at infinity of Wei25519. (Here,
we used the mapping of Appendix C.2.) Under this mapping, the base we used the mapping of Appendix D.2.) Under this mapping, the base
point (Gu,Gv) of Curve25519 corresponds to the base point (Gx',Gy') point (Gu,Gv) of Curve25519 corresponds to the base point (Gx',Gy')
of Wei25519. The inverse mapping maps the affine point (x,y) of of Wei25519. The inverse mapping maps the affine point (x,y) of
Wei25519 to (u,v):=(x - A/3,y) of Curve25519, while mapping the point Wei25519 to (u,v):=(x - A/3,y) of Curve25519, while mapping the point
at infinity of Wei25519 to the point at infinity of Curve25519. Note at infinity of Wei25519 to the point at infinity of Curve25519. Note
that this mapping involves a simple shift of the first coordinate and that this mapping involves a simple shift of the first coordinate and
can be implemented via integer-only arithmetic as a shift of (p+A)/3 can be implemented via integer-only arithmetic as a shift of (p+A)/3
for the isomorphic mapping and a shift of -(p+A)/3 for its inverse, for the isomorphic mapping and a shift of -(p+A)/3 for its inverse,
where delta=(p+A)/3 is the element of GF(p) defined by where delta=(p+A)/3 is the element of GF(p) defined by
delta 19298681539552699237261830834781317975544997444273427339909597 delta 19298681539552699237261830834781317975544997444273427339909597
skipping to change at page 11, line 33 skipping to change at page 16, line 50
defined by defined by
c sqrt(-(A+2)) c sqrt(-(A+2))
51042569399160536130206135233146329284152202253034631822681833788 51042569399160536130206135233146329284152202253034631822681833788
666877215207 666877215207
(=0x70d9120b 9f5ff944 2d84f723 fc03b081 3a5e2c2e b482e57d (=0x70d9120b 9f5ff944 2d84f723 fc03b081 3a5e2c2e b482e57d
3391fb55 00ba81e7) 3391fb55 00ba81e7)
(Here, we used the mapping of Appendix C.1.) The inverse mapping (Here, we used the mapping of Appendix D.1.) The inverse mapping
from Edwards25519 to Curve25519 is defined by mapping the point (0, from Edwards25519 to Curve25519 is defined by mapping the point (0,
1) and the point (0, -1) of order two of Edwards25519 to, 1) and the point (0, -1) of order two of Edwards25519 to,
respectively, the point at infinity and the point (0,0) of order two respectively, the point at infinity and the point (0,0) of order two
of Curve25519 and having each other point (x, y) of Edwards25519 of Curve25519 and having each other point (x, y) of Edwards25519
correspond to the point ((1 + y)/(1 - y), c*(1 + y)/((1-y)*x)). correspond to the point ((1 + y)/(1 - y), c*(1 + y)/((1-y)*x)).
The curve Edwards25519 is isomorphic to the Weierstrass curve The curve Edwards25519 is isomorphic to the Weierstrass curve
Wei25519, where the base point (Gx,Gy) of Edwards25519 corresponds to Wei25519, where the base point (Gx,Gy) of Edwards25519 corresponds to
the base point (Gx',Gy') of Wei25519 and where the identity element the base point (Gx',Gy') of Wei25519 and where the identity element
(0,1) and the point (0,-1) of order two of Edwards25519 correspond (0,1) and the point (0,-1) of order two of Edwards25519 correspond
to, respectively, the point at infinity O and the point (A/3, 0) of to, respectively, the point at infinity O and the point (A/3, 0) of
order two of Wei25519 and where each other point (x, y) of order two of Wei25519 and where each other point (x, y) of
Edwards25519 corresponds to the point (x', y'):=((1+y)/(1-y)+A/3, Edwards25519 corresponds to the point (x', y'):=((1+y)/(1-y)+A/3,
c*(1+y)/((1-y)*x)) of Wei25519, where c was defined before. (Here, c*(1+y)/((1-y)*x)) of Wei25519, where c was defined before. (Here,
we used the mapping of Appendix C.3.) The inverse mapping from we used the mapping of Appendix D.3.) The inverse mapping from
Wei25519 to Edwards25519 is defined by mapping the point at infinity Wei25519 to Edwards25519 is defined by mapping the point at infinity
O and the point (A/3, 0) of order two of Wei25519 to, respectively, O and the point (A/3, 0) of order two of Wei25519 to, respectively,
the identity element (0,1) and the point (0,-1) of order two of the identity element (0,1) and the point (0,-1) of order two of
Edwards25519 and having each other point (x, y) of Wei25519 Edwards25519 and having each other point (x, y) of Wei25519
correspond to the point (c*(3*x-A)/(3*y), (3*x-A-3)/(3*x-A+3)). correspond to the point (c*(3*x-A)/(3*y), (3*x-A-3)/(3*x-A+3)).
Note that these mappings can be easily realized in projective Note that these mappings can be easily realized in projective
coordinates, using a few field multiplications only, thus allowing coordinates, using a few field multiplications only, thus allowing
switching between alternative representations with negligible switching between alternative representations with negligible
relative incremental cost. relative incremental cost.
D.3. Domain Parameters E.3. Domain Parameters
The parameters of the Montgomery curve and the corresponding The parameters of the Montgomery curve and the corresponding
isomorphic curves in twisted Edwards curve and short-Weierstrass form isomorphic curves in twisted Edwards curve and short-Weierstrass form
are as indicated below. Here, the domain parameters of the are as indicated below. Here, the domain parameters of the
Montgomery curve Curve25519 and of the twisted Edwards curve Montgomery curve Curve25519 and of the twisted Edwards curve
Edwards25519 are as specified in RFC 7748; the domain parameters of Edwards25519 are as specified in RFC 7748; the domain parameters of
Wei25519 are "new". Wei25519 are "new".
General parameters (for all curve models): General parameters (for all curve models):
skipping to change at page 14, line 11 skipping to change at page 19, line 29
(=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa
aaaaaaaa aaad245a) aaaaaaaa aaad245a)
Gy' 14781619447589544791020593568409986887264606134616475288964881837 Gy' 14781619447589544791020593568409986887264606134616475288964881837
755586237401 755586237401
(=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2 (=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2
29e9c5a2 7eced3d9) 29e9c5a2 7eced3d9)
Appendix E. Further Mappings Appendix F. Further Mappings
The non-binary curves specified in Appendix A are expressed in The non-binary curves specified in Appendix A are expressed in
different curve models, viz. as curves in short-Weierstrass form, as different curve models, viz. as curves in short-Weierstrass form, as
Montgomery curves, or as twisted Edwards curves. Within each curve Montgomery curves, or as twisted Edwards curves. Within each curve
model, further mappings exist that induce a mapping between elliptic model, further mappings exist that induce a mapping between elliptic
curves within each curve model. This can be exploited to force some curves within each curve model. This can be exploited to force some
of the domain parameter to a value that allows a more efficient of the domain parameters to a value that allows a more efficient
implementation of the addition formulae. implementation of the addition formulae.
E.1. Isomorphic Mapping between Weierstrass Curves F.1. Isomorphic Mapping between Weierstrass Curves
One can map points of the Weierstrass curve W_{a,b} to points of the One can map points of the Weierstrass curve W_{a,b} to points of the
Weierstrass curve W_{a',b'}, where a:=a'*s^4 and b:=b'*s^6 for some Weierstrass curve W_{a',b'}, where a:=a'*s^4 and b:=b'*s^6 for some
nonzero value u of the finite field GF(q). This defines a one-to-one nonzero value s of the finite field GF(q). This defines a one-to-one
correspondence, which - in fact - is an isomorphism between W_{a,b} correspondence, which - in fact - is an isomorphism between W_{a,b}
and W_{a',b'}, thereby showing that, e.g., the discrete logarithm and W_{a',b'}, thereby showing that, e.g., the discrete logarithm
problem in either curve model is equally hard. problem in either curve model is equally hard.
The mapping from W_{a,b} to W_{a',b'} is defined by mapping the point The mapping from W_{a,b} to W_{a',b'} is defined by mapping the point
at infinity O of W_{a,b} to the point at infinity O of W_{a',b'}, at infinity O of W_{a,b} to the point at infinity O of W_{a',b'},
while mapping each other point (x, y) of W_{a,b} to the point (x', while mapping each other point (x, y) of W_{a,b} to the point (x',
y'):=(x*s^2, y*s^3) of W_{a',b'}. The inverse mapping from W_{a',b'} y'):=(x*s^2, y*s^3) of W_{a',b'}. The inverse mapping from W_{a',b'}
to W_{a,b} is defined by mapping the point at infinity O of W_{a',b'} to W_{a,b} is defined by mapping the point at infinity O of W_{a',b'}
to the point at infinity O of W_{a,b}, while mapping each other point to the point at infinity O of W_{a,b}, while mapping each other point
(x', y') of W_{a',b'} to the point (x, y):=(x/s^2, y/s^3) of W_{a,b}. (x', y') of W_{a',b'} to the point (x, y):=(x/s^2, y/s^3) of W_{a,b}.
Implementations may take advantage of this mapping to carry out Implementations may take advantage of this mapping to carry out
elliptic curve group operations originally defined for a Weierstrass elliptic curve group operations originally defined for a Weierstrass
curve with a generic domain parameter a on a corresponding isomorphic curve with a generic domain parameter a on a corresponding isomorphic
Weierstrass curve with domain parameter a' that has a special form, Weierstrass curve with domain parameter a' that has a special form,
which is known to allow for more efficient implementations of which is known to allow for more efficient implementations of
addition laws, and translating the result back to the original curve. addition laws, and translating the result back to the original curve.
In particular, it is known that such efficiency improvements exist if In particular, it is known that such efficiency improvements exist if
a'=-3 (mod p) and one uses so-called Jacobian coordinates with a a'=-3 (mod p) and one uses so-called Jacobian coordinates with a
particular projective version of the addition laws of Appendix B.1. particular projective version of the addition laws of Appendix C.1.
While not all Weierstrass curves can be put into this form, all While not all Weierstrass curves can be put into this form, all
traditional NIST curves have domain parameter a=-3, while all traditional NIST curves have domain parameter a=-3, while all
Brainpool curves [RFC5639] are isomorphic to a Weierstrass curve of Brainpool curves [RFC5639] are isomorphic to a Weierstrass curve of
this form. For details, we refer to Section 3.1.5 of [GECC]. this form.
Note that implementations for elliptic curves with short-Weierstrass Note that implementations for elliptic curves with short-Weierstrass
form that hard-code the domain parameter a to a= -3 (which value is form that hard-code the domain parameter a to a= -3 cannot always be
known to allow more efficient implementations) cannot always be used used this way, since the curve W_{a,b} cannot always be expressed in
this way, since the curve W_{a,b} may not always be expressed in
terms of a Weierstrass curve with a'=-3 via a coordinate terms of a Weierstrass curve with a'=-3 via a coordinate
transformation: this only holds if a'/a is a fourth power in GF(q). transformation: this only holds if a'/a is a fourth power in GF(q)
However, even in this case, one can still express the curve W_{a,b} (see Section 3.1.5 of [GECC]). However, even in this case, one can
in terms of a Weierstrass curve with a small a' domain parameter, still express the curve W_{a,b} as a Weierstrass curve with a small
thereby still allowing a more efficient implementation than with a domain parameter value a', thereby still allowing a more efficient
general a value. implementation than with a general domain parameter value a.
E.2. Isogeneous Mapping between Weierstrass Curves F.2. Isogenous Mapping between Weierstrass Curves
One can still map points of the Weierstrass curve W_{a,b} to points One can still map points of the Weierstrass curve W_{a,b} to points
of the Weierstrass curve W_{a',b'}, where a':=-3 (mod p), even if of the Weierstrass curve W_{a',b'}, where a':=-3 (mod p), even if
a'/a is not a fourth power in GF(q). In that case, this mappping a'/a is not a fourth power in GF(q). In that case, this mappping
cannot be an isomorphism (see Appendix E.1) and, thereby, does not cannot be an isomorphism (see Appendix F.1). Instead, the mapping is
define a one-to-one correspondence. Instead, the mapping is a so- a so-called isogeny (or homomorphism). Since most elliptic curve
called isogeny (or homomorphism). Since most elliptic curve
operations process points of prime order or use so-called "co-factor operations process points of prime order or use so-called "co-factor
multiplication", in practice the resulting mapping has similar multiplication", in practice the resulting mapping has similar
properties. In particular, one can still take advantage of this properties as an isomorphism. In particular, one can still take
mapping to carry out elliptic curve group operations originally advantage of this mapping to carry out elliptic curve group
defined for a Weierstrass curve with domain parameter a unequal to -3 operations originally defined for a Weierstrass curve with domain
(mod p) on a corresponding isogenous Weierstrass curve with domain parameter a unequal to -3 (mod p) on a corresponding isogenous
parameter a'=-3 (mod p) and translating the result back to the Weierstrass curve with domain parameter a'=-3 (mod p) and translating
original curve. the result back to the original curve.
In this case, the mapping from W_{a,b} to W_{a',b'} is defined by In this case, the mapping from W_{a,b} to W_{a',b'} is defined by
mapping the point at infinity O of W_{a,b} to the point at infinity O mapping the point at infinity O of W_{a,b} to the point at infinity O
of W_{a',b'}, while mapping each other point (x, y) of W_{a,b} to the of W_{a',b'}, while mapping each other point (x, y) of W_{a,b} to the
point (x', y'):=(u(x)/w(x)^2, y*v(x)/w(x)^3) of W_{a',b'}. Here, point (x', y'):=(u(x)/w(x)^2, y*v(x)/w(x)^3) of W_{a',b'}. Here,
u(x), v(x), and w(x) are polynomials that depend on the isogeny in u(x), v(x), and w(x) are polynomials that depend on the isogeny in
question. The inverse mapping from W_{a',b'} to W_{a,b} is again an question. The inverse mapping from W_{a',b'} to W_{a,b} is again an
isogeny and defined by mapping the point at infinity O of W_{a',b'} isogeny and defined by mapping the point at infinity O of W_{a',b'}
to the point at infinity O of W_{a,b}, while mapping each other point to the point at infinity O of W_{a,b}, while mapping each other point
(x', y') of W_{a',b'} to the point (x, y):=(u'(x')/w'(x')^2, (x', y') of W_{a',b'} to the point (x, y):=(u'(x')/w'(x')^2,
y'*v'(x')/w'(x')^3) of W_{a,b}, where -- again -- u'(x'), v'(x'), and y'*v'(x')/w'(x')^3) of W_{a,b}, where -- again -- u'(x'), v'(x'), and
w'(x') are polynomials that depend on the isogeny in question. These w'(x') are polynomials that depend on the isogeny in question. These
mappings have the property that their composition is not the identity mappings have the property that their composition is not the identity
mapping (as is the case with the isomorphic mappings discussed in mapping (as is the case with the isomorphic mappings discussed in
Appendix E.1), but rather a fixed multiple hereof: if this multiple Appendix F.1), but rather a fixed multiple hereof: if this multiple
is l then the isogeny is called an isogeny of degree l (or l-isogeny) is l then the isogeny is called an isogeny of degree l (or l-isogeny)
and u, v, and w (and, similarly, u', v', and w') are polynomials of and u, v, and w (and, similarly, u', v', and w') are polynomials of
degrees l, 3(l-1)/2, and (l-1)/2, respectively. Note that an degrees l, 3(l-1)/2, and (l-1)/2, respectively. Note that an
isomorphism is simply an isogeny of degree l=1. Details of how to isomorphism is simply an isogeny of degree l=1. Details of how to
compute this mapping are outside scope of this document (for this, determine isogenies are outside scope of this document (for this,
contact the author of this document). contact the author of this document).
Implementations may take advantage of this mapping to carry out Implementations may take advantage of this mapping to carry out
elliptic curve group operations originally defined for a Weierstrass elliptic curve group operations originally defined for a Weierstrass
curve with a generic domain parameter a on a corresponding isogeneous curve with a generic domain parameter a on a corresponding isogenous
Weierstrass curve with domain parameter a'=-3 (mod p), where one can Weierstrass curve with domain parameter a'=-3 (mod p), where one can
use so-called Jacobian coordinates with a particular projective use so-called Jacobian coordinates with a particular projective
version of the addition laws of Appendix B.1. Since all traditional version of the addition laws of Appendix C.1. Since all traditional
NIST curves have domain parameter a=-3, while all Brainpool curves NIST curves have domain parameter a=-3, while all Brainpool curves
[RFC5639] are isomorphic to a Weierstrass curve of this form, this [RFC5639] are isomorphic to a Weierstrass curve of this form, this
allows taking advantage of existing generic implementations for these allows taking advantage of existing implementations for these curves
curves, provided one switches back and forth to this curve form using that may have a hardcoded a=-3 (mod p) domain parameter, provided one
the isogeneous mapping in question. switches back and forth to this curve form using the isogenous
mapping in question.
Note that isogeneous mappings can be easily realized in projective Note that isogenous mappings can be easily realized in projective
coordinates and involves roughly 3*l finite field multiplications, coordinates and involves roughly 3*l finite field multiplications,
thus allowing switching between alternative representations at thus allowing switching between alternative representations at
relative low incremental cost compared to that of elliptic curve relative low incremental cost compared to that of elliptic curve
scalar multiplications (provided the isogeny has low degree l). scalar multiplications (provided the isogeny has low degree l).
Note, however, that this does require storage of the polynomial Note, however, that this does require storage of the polynomial
coefficients of the isogeny and dual isogeny involved. This coefficients of the isogeny and dual isogeny involved. This
illustrates that low-degree isogenies are to be preferred, since an illustrates that low-degree isogenies are to be preferred, since an
l-isogeny (usually) requires storing roughly 6*l elements of GF(q). l-isogeny (usually) requires storing roughly 6*l elements of GF(q).
While there are many isogenies, we therefore only consider those with While there are many isogenies, we therefore only consider those with
the desired property with lowest possible degree. the desired property with lowest possible degree.
Appendix F. Further Cousins of Curve25519 Appendix G. Further Cousins of Curve25519
F.1. Further Alternative Representations G.1. Further Alternative Representations
The Weierstrass curve Wei25519 is isomorphic to the Weierstrass curve The Weierstrass curve Wei25519 is isomorphic to the Weierstrass curve
Wei25519.2 defined over GF(p), with as base point the pair (G1x,G1y), Wei25519.2 defined over GF(p), with as base point the pair
and isogeneous to the Weierstrass curve Wei25519.-3 defined over (G1x',G1y'), and isogenous to the Weierstrass curve Wei25519.-3
GF(p), with as base point the pair (G2x, G2y), where parameters are defined over GF(p), with as base point the pair (G2x', G2y'), where
as specified in Appendix F.3 and where the related mappings are as parameters are as specified in Appendix G.3 and where the related
specified in Appendix F.2. mappings are as specified in Appendix G.2.
F.2. Further Switching G.2. Further Switching
Each affine point (x,y) of Wei25519 corresponds to the point Each affine point (x,y) of Wei25519 corresponds to the point
(x',y'):=(x*s^2,y*s^3) of Wei25519.2, where s is the element of GF(p) (x',y'):=(x*s^2,y*s^3) of Wei25519.2, where s is the element of GF(p)
defined by defined by
s 20343593038935618591794247374137143598394058341193943326473831977 s 20343593038935618591794247374137143598394058341193943326473831977
39407761440 39407761440
(=0x047f6814 6d568b44 7e4552ea a5ed633d 02d62964 a2b0a120 (=0x047f6814 6d568b44 7e4552ea a5ed633d 02d62964 a2b0a120
5e7941e9 375de020), 5e7941e9 375de020),
while the point at infinity of Wei25519 corresponds to the point at while the point at infinity of Wei25519 corresponds to the point at
infinity of Wei25519.2. (Here, we used the mapping of Appendix E.1.) infinity of Wei25519.2. (Here, we used the mapping of Appendix F.1.)
Under this mapping, the base point (Gx',Gy') of Wei25519 corresponds Under this mapping, the base point (Gx',Gy') of Wei25519 corresponds
to the base point (G1x',G1y') of Wei25519.2. The inverse mapping to the base point (G1x',G1y') of Wei25519.2. The inverse mapping
maps the affine point (x',y') of Wei25519.2 to (x,y):=(x'/s^2,y'/s^3) maps the affine point (x',y') of Wei25519.2 to (x,y):=(x'/s^2,y'/s^3)
of Wei25519, while mapping the point at infinity of Wei25519.2 to the of Wei25519, while mapping the point at infinity of Wei25519.2 to the
point at infinity of Wei25519. Note that this mapping (and its point at infinity of Wei25519. Note that this mapping (and its
inverse) involves a modular multiplication of both coordinates with inverse) involves a modular multiplication of both coordinates with
fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which
can be precomputed. can be precomputed.
Each affine point (x,y) of Wei25519 corresponds to the point Each affine point (x,y) of Wei25519 corresponds to the point
(x',y'):=(x1/t^2,y1/t^3) of Wei25519.-3, where (x',y'):=(x1/t^2,y1/t^3) of Wei25519.-3, where
(x1,y1)=(u(x)/w(x)^2,y*v(x)/w(x)^3), where u, v, and w are the (x1,y1)=(u(x)/w(x)^2,y*v(x)/w(x)^3), where u, v, and w are the
polynomials with coefficients in GF(p) as defined in Appendix G and polynomials with coefficients in GF(p) as defined in Appendix H.1 and
where t is the element of GF(p) defined by where t is the element of GF(p) defined by
t 26012855558634277483276064234565597076862996895623795164528458073 t 26012855558634277483276064234565597076862996895623795164528458073
435568115620 435568115620
(=0x3982c126 59ad1749 ab8bc495 bb1a9d64 c9deffc5 e7b8e601 (=0x3982c126 59ad1749 ab8bc495 bb1a9d64 c9deffc5 e7b8e601
a5651992 07d48fa4), a5651992 07d48fa4),
while the point at infinity of Wei25519 corresponds to the point at while the point at infinity of Wei25519 corresponds to the point at
infinity of Wei25519.-3. (Here, we used the isogeneous mapping of infinity of Wei25519.-3. (Here, we used the isogenous mapping of
Appendix E.2.) Under this isogeneous mapping, the base point Appendix F.2.) Under this isogenous mapping, the base point
(Gx',Gy') of Wei25519 corresponds to the base point (G2x',G2y') of (Gx',Gy') of Wei25519 corresponds to the base point (G2x',G2y') of
Wei25519.-3. The dual isogeny maps the affine point (x',y') of Wei25519.-3. The dual isogeny maps the affine point (x',y') of
Wei25519.-3 to to (x,y):=(u'(x1)/w'(x1)^2,y1*v'(x1)/w'(x1)^3) of Wei25519.-3 to to (x,y):=(u'(x1)/w'(x1)^2,y1*v'(x1)/w'(x1)^3) of
Wei25519, where (x1,y1)=(x'*t^2,y'*t^3) and where u', v', and w' are Wei25519, where (x1,y1)=(x'*t^2,y'*t^3) and where u', v', and w' are
the polynomials with coefficients in GF(p) as defined in Appendix G, the polynomials with coefficients in GF(p) as defined in
while mapping the point at infinity of Wei25519.-3 to the point at Appendix H.2, while mapping the point at infinity of Wei25519.-3 to
infinity of Wei25519. Under this dual isogeneous mapping, the base the point at infinity of Wei25519. Under this dual isogenous
point (G2x',G2y') of Wei25519.-3 corresponds to a multiple of the mapping, the base point (G2x',G2y') of Wei25519.-3 corresponds to a
base point (Gx',Gy') of Wei25519, where this multiple is l=47 (the multiple of the base point (Gx',Gy') of Wei25519, where this multiple
degree of the isogeny; see the description in Appendix E.1). Note is l=47 (the degree of the isogeny; see the description in
that this isogenous map (and its dual) primarily involves the Appendix F.1). Note that this isogenous map (and its dual) primarily
evaluation of three fixed polynomials involving the x-coordinate, involves the evaluation of three fixed polynomials involving the
which takes roughly 140 modular multiplications (or less than 5% x-coordinate, which takes roughly 140 modular multiplications (or
relative incremental cost compared to the cost of an elliptic curve less than 5-10% relative incremental cost compared to the cost of an
scalar multiplication). elliptic curve scalar multiplication).
F.3. Further Domain Parameters G.3. Further Domain Parameters
The parameters of the Weierstrass curve with a=2 that is isomorphic The parameters of the Weierstrass curve with a=2 that is isomorphic
with Wei25519 and the parameters of the Weierstrass curve with a=-3 with Wei25519 and the parameters of the Weierstrass curve with a=-3
that is isogeneous with Wei25519 are as indicated below. Both domain that is isogenous with Wei25519 are as indicated below. Both domain
parameter sets can be exploited directly to derive more efficient parameter sets can be exploited directly to derive more efficient
point addition formulae, should an implementation facilitate this. point addition formulae, should an implementation facilitate this.
General parameters: same as for Wei25519 (see Appendix E.3)
Weierstrass curve-specific parameters (for Wei25519.2, i.e., with Weierstrass curve-specific parameters (for Wei25519.2, i.e., with
a=2): a=2):
a 2 (=0x02) a 2 (=0x02)
b 12102640281269758552371076649779977768474709596484288167752775713 b 12102640281269758552371076649779977768474709596484288167752775713
178787220689 178787220689
(=0x1ac1da05 b55bc146 33bd39e4 7f94302e f19843dc f669916f (=0x1ac1da05 b55bc146 33bd39e4 7f94302e f19843dc f669916f
6a5dfd01 65538cd1) 6a5dfd01 65538cd1)
skipping to change at page 19, line 4 skipping to change at page 24, line 21
796e1022 40891faa) 796e1022 40891faa)
G2x' 538371792299408724349427232574807773704511272123391981336972078 G2x' 538371792299408724349427232574807773704511272123391981336972078
46219400243292 46219400243292
(=0x7706c37b 5a84128a 3884a5d7 1811f1b5 5da3230f fb17a8ab (=0x7706c37b 5a84128a 3884a5d7 1811f1b5 5da3230f fb17a8ab
0b32e48d 31a6685c) 0b32e48d 31a6685c)
G2y' 695480730911001844144020555292799703925148674228551417730708041 G2y' 695480730911001844144020555292799703925148674228551417730708041
8460388229929 8460388229929
(=0x0f60480c 7a5c0e11 40340adc 79d6a2bf 0cb57ad0 49d025dc (=0x0f60480c 7a5c0e11 40340adc 79d6a2bf 0cb57ad0 49d025dc
38d80c77 985f0329) 38d80c77 985f0329)
Appendix G. Isogeny Details Appendix H. Isogeny Details
The isogeny and dual isogeny are both isogenies with degree l=47. The isogeny and dual isogeny are both isogenies with degree l=47.
Both are specified by a triple of polynomials u, v, and w (resp. u', Both are specified by a triple of polynomials u, v, and w (resp. u',
v', and w') of degree 47, 69, and 23, respectively, with coefficients v', and w') of degree 47, 69, and 23, respectively, with coefficients
in GF(p). The coeffients of each of these polynomials are specified in GF(p). The coeffients of each of these polynomials are specified
in Appendix G.1 (for the isogeny) and in Appendix G.2 (for the dual in Appendix H.1 (for the isogeny) and in Appendix H.2 (for the dual
isogeny). For each polynomial in variable x, the coefficients are isogeny). For each polynomial in variable x, the coefficients are
tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in
hexadecimal format. hexadecimal format.
G.1. Isogeny Parameters H.1. Isogeny Parameters
G.1.1. Coefficients of u(x): H.1.1. Coefficients of u(x)
0 0x670ed14828b6f1791ceb3a9cc0edfe127dee8729c5a72ddf77bb1abaebbba1e8 0 0x670ed14828b6f1791ceb3a9cc0edfe127dee8729c5a72ddf77bb1abaebbba1e8
1 0x1135ca8bd5383cb3545402c8bce2ced14b45c29b241e4751b035f27524a9f932 1 0x1135ca8bd5383cb3545402c8bce2ced14b45c29b241e4751b035f27524a9f932
2 0x3223806ff5f669c430efd74df8389f058d180e2fcffa5cdef3eacecdd2c34771 2 0x3223806ff5f669c430efd74df8389f058d180e2fcffa5cdef3eacecdd2c34771
3 0x31b8fecf3f17a819c228517f6cd9814466c8c8bea2efccc47a29bfc14c364266 3 0x31b8fecf3f17a819c228517f6cd9814466c8c8bea2efccc47a29bfc14c364266
4 0x2541305c958c5a326f44efad2bec284e7abee840fadb08f2d994cd382fd8ce42 4 0x2541305c958c5a326f44efad2bec284e7abee840fadb08f2d994cd382fd8ce42
skipping to change at page 21, line 22 skipping to change at page 26, line 40
43 0x573453fb2b093016f3368356c786519d54ed05f5372c01723b4da520597ec217 43 0x573453fb2b093016f3368356c786519d54ed05f5372c01723b4da520597ec217
44 0x77f5c605bdb3a30d7d9c8840fce38650910d4418eed707a212c8927f41c2c812 44 0x77f5c605bdb3a30d7d9c8840fce38650910d4418eed707a212c8927f41c2c812
45 0x16d6b9f7ff57ca32350057de1204cc6d69d4ef1b255dfef8080118e2fef6ace3 45 0x16d6b9f7ff57ca32350057de1204cc6d69d4ef1b255dfef8080118e2fef6ace3
46 0x34e8595832a4021f8b5744014c6b4f7da7df0d0329e8b6b4d44c8fadad6513b7 46 0x34e8595832a4021f8b5744014c6b4f7da7df0d0329e8b6b4d44c8fadad6513b7
47 0x1 47 0x1
G.1.2. Coefficients of v(x): H.1.2. Coefficients of v(x)
0 0xf9f5eb7134e6f8dafa30c45afa58d7bfc6d4e3ccbb5de87b562fd77403972b2 0 0xf9f5eb7134e6f8dafa30c45afa58d7bfc6d4e3ccbb5de87b562fd77403972b2
1 0x36c2dcd9e88f0d2d517a15fc453a098bbbb5a05eb6e8da906fae418a4e1a13f7 1 0x36c2dcd9e88f0d2d517a15fc453a098bbbb5a05eb6e8da906fae418a4e1a13f7
2 0xb40078302c24fa394a834880d5bf46732ca1b4894172fb7f775821276f558b3 2 0xb40078302c24fa394a834880d5bf46732ca1b4894172fb7f775821276f558b3
3 0x53dd8e2234573f7f3f7df11e90a7bdd7b75d807f9712f521d4fb18af59aa5f26 3 0x53dd8e2234573f7f3f7df11e90a7bdd7b75d807f9712f521d4fb18af59aa5f26
4 0x6d4d7bb08de9061988a8cf6ff3beb10e933d4d2fbb8872d256a38c74c8c2ceda 4 0x6d4d7bb08de9061988a8cf6ff3beb10e933d4d2fbb8872d256a38c74c8c2ceda
skipping to change at page 24, line 20 skipping to change at page 29, line 38
65 0x537f58d52d18ce5b1d5a6bd3a420e796e64173491ad43dd4d1083a7dcc7dd201 65 0x537f58d52d18ce5b1d5a6bd3a420e796e64173491ad43dd4d1083a7dcc7dd201
66 0x49c2f6afa93fdcc4e0f8128a8b06da4c75049be14edf3e103821ab604c60f8ae 66 0x49c2f6afa93fdcc4e0f8128a8b06da4c75049be14edf3e103821ab604c60f8ae
67 0x10a333eabd6135aeaa3f5f5f7e73d102e4fd7e4bf0902fc55b00da235fa1ad08 67 0x10a333eabd6135aeaa3f5f5f7e73d102e4fd7e4bf0902fc55b00da235fa1ad08
68 0xf5c86044bf6032f5102e601f2a0f73c7bce9384bedd120f3e72d78484179d9c 68 0xf5c86044bf6032f5102e601f2a0f73c7bce9384bedd120f3e72d78484179d9c
69 0x1 69 0x1
G.1.3. Coefficients of w(x): H.1.3. Coefficients of w(x)
0 0x3da24d42421264f30939ff00203880f2b017eb3fecf8933ae61e18df8c8ba116 0 0x3da24d42421264f30939ff00203880f2b017eb3fecf8933ae61e18df8c8ba116
1 0x457f20bc393cdc9a66848ce174e2fa41d77e6dbae05a317a1fb6e3ae78760f8 1 0x457f20bc393cdc9a66848ce174e2fa41d77e6dbae05a317a1fb6e3ae78760f8
2 0x7f608a2285c480d5c9592c435431fae94695beef79d770bb6d029c1d10a53295 2 0x7f608a2285c480d5c9592c435431fae94695beef79d770bb6d029c1d10a53295
3 0x3832accc520a485100a0a1695792465142a5572bed1b2e50e1f8f662ac7289bb 3 0x3832accc520a485100a0a1695792465142a5572bed1b2e50e1f8f662ac7289bb
4 0x2df1b0559e31b328eb34beedd5e537c3f4d7b9befb0749f75d6d0d866d26fbaa 4 0x2df1b0559e31b328eb34beedd5e537c3f4d7b9befb0749f75d6d0d866d26fbaa
skipping to change at page 25, line 22 skipping to change at page 30, line 40
19 0x33e4cab64ed8a00d8012104fe8f928e6173c428eff95bbbe569ea46126a4f3cd 19 0x33e4cab64ed8a00d8012104fe8f928e6173c428eff95bbbe569ea46126a4f3cd
20 0x50555b6f07e308d33776922b6566829d122e19b25b7bbacbb0a4b1a7dc40192 20 0x50555b6f07e308d33776922b6566829d122e19b25b7bbacbb0a4b1a7dc40192
21 0x533fa4bf1e2a2aae2f979065fdbb5b667ede2f85543fddbba146aa3a4ef2d281 21 0x533fa4bf1e2a2aae2f979065fdbb5b667ede2f85543fddbba146aa3a4ef2d281
22 0x5a742cac1952010fc5aba200a635a7bed3ef868194f45b5a6a2647d6d6b289d2 22 0x5a742cac1952010fc5aba200a635a7bed3ef868194f45b5a6a2647d6d6b289d2
23 0x1 23 0x1
G.2. Dual Isogeny Parameters H.2. Dual Isogeny Parameters
G.2.1. Coefficients of u'(x): H.2.1. Coefficients of u'(x)
0 0xf0eddb584a20aaac8f1419efdd02a5cca77b21e4cfae78c49b5127d98bc5882 0 0xf0eddb584a20aaac8f1419efdd02a5cca77b21e4cfae78c49b5127d98bc5882
1 0x7115e60d44a58630417df33dd45b8a546fa00b79fea3b2bdc449694bade87c0a 1 0x7115e60d44a58630417df33dd45b8a546fa00b79fea3b2bdc449694bade87c0a
2 0xb3f3a6f3c445c7dc1f91121275414e88c32ff3f367ba0edad4d75b7e7b94b65 2 0xb3f3a6f3c445c7dc1f91121275414e88c32ff3f367ba0edad4d75b7e7b94b65
3 0x1eb31bb333d7048b87f2b3d4ec76d69035927b41c30274368649c87c52e1ab30 3 0x1eb31bb333d7048b87f2b3d4ec76d69035927b41c30274368649c87c52e1ab30
4 0x552c886c2044153e280832264066cce2a7da1127dc9720e2a380e9d37049ac64 4 0x552c886c2044153e280832264066cce2a7da1127dc9720e2a380e9d37049ac64
5 0x4504f27908db2e1f5840b74ae42445298755d9493141f5417c02f04d47797dda 5 0x4504f27908db2e1f5840b74ae42445298755d9493141f5417c02f04d47797dda
6 0x82c242cce1eb19698a4fa30b5affe64e5051c04ae8b52cb68d89ee85222e628 6 0x82c242cce1eb19698a4fa30b5affe64e5051c04ae8b52cb68d89ee85222e628
7 0x480473406add76cf1d77661b3ff506c038d9cdd5ad6e1ea41969430bb876d223 7 0x480473406add76cf1d77661b3ff506c038d9cdd5ad6e1ea41969430bb876d223
8 0x25f47bb506fba80c79d1763365fa9076d4c4cb6644f73ed37918074397e88588 8 0x25f47bb506fba80c79d1763365fa9076d4c4cb6644f73ed37918074397e88588
skipping to change at page 27, line 26 skipping to change at page 32, line 44
43 0x5a9d104ae585b94af68eeb16b1349776b601f97b7ce716701645b1a75b68dcf3 43 0x5a9d104ae585b94af68eeb16b1349776b601f97b7ce716701645b1a75b68dcf3
44 0x754e014b5e87af035b3d5fe6fb49f4631e32549f6341c6693c5172a6388e273e 44 0x754e014b5e87af035b3d5fe6fb49f4631e32549f6341c6693c5172a6388e273e
45 0x6710d8265118e22eaceba09566c86f642ab42da58c435083a353eaa12d866c39 45 0x6710d8265118e22eaceba09566c86f642ab42da58c435083a353eaa12d866c39
46 0x6e88ac659ce146c369f8b24c3a49f8dca547827250cf7963a455851cfc4f8d22 46 0x6e88ac659ce146c369f8b24c3a49f8dca547827250cf7963a455851cfc4f8d22
47 0x971eb5f253356cd1fde9fb21f4a4902aa5b8d804a2b57ba775dc130181ae2e8 47 0x971eb5f253356cd1fde9fb21f4a4902aa5b8d804a2b57ba775dc130181ae2e8
G.2.2. Coefficients of v'(x): H.2.2. Coefficients of v'(x)
0 0x43c9b67cc5b16e167b55f190db61e44d48d813a7112910f10e3fd8da85d61d3 0 0x43c9b67cc5b16e167b55f190db61e44d48d813a7112910f10e3fd8da85d61d3
1 0x72046db07e0e7882ff3f0f38b54b45ca84153be47a7fd1dd8f6402e17c47966f 1 0x72046db07e0e7882ff3f0f38b54b45ca84153be47a7fd1dd8f6402e17c47966f
2 0x1593d97b65a070b6b3f879fe3dc4d1ef03c0e781c997111d5c1748f956f1ffc0 2 0x1593d97b65a070b6b3f879fe3dc4d1ef03c0e781c997111d5c1748f956f1ffc0
3 0x54e5fec076b8779338432bdc5a449e36823a0a7c905fd37f232330b026a143a0 3 0x54e5fec076b8779338432bdc5a449e36823a0a7c905fd37f232330b026a143a0
4 0x46328dd9bc336e0873abd453db472468393333fbf2010c6ac283933216e98038 4 0x46328dd9bc336e0873abd453db472468393333fbf2010c6ac283933216e98038
5 0x25d0c64de1dfe1c6d5f5f2d98ab637d8b39bcf0d886a23dabac18c80d7eb03ce 5 0x25d0c64de1dfe1c6d5f5f2d98ab637d8b39bcf0d886a23dabac18c80d7eb03ce
6 0x3a175c46b2cd8e2b313dde2d5f3097b78114a6295f283cf58a33844b0c8d8b34 6 0x3a175c46b2cd8e2b313dde2d5f3097b78114a6295f283cf58a33844b0c8d8b34
7 0x5cf4e6f745bdd61181a7d1b4db31dc4c30c84957f63cdf163bee5e466a7a8d38 7 0x5cf4e6f745bdd61181a7d1b4db31dc4c30c84957f63cdf163bee5e466a7a8d38
skipping to change at page 30, line 24 skipping to change at page 35, line 42
65 0x3468cf6df7e93f7ff1fe1dd7e180a89dec3ed4f72843b4ea8a8d780011a245b2 65 0x3468cf6df7e93f7ff1fe1dd7e180a89dec3ed4f72843b4ea8a8d780011a245b2
66 0x68f75a0e2210f52a90704ed5f511918d1f6bcfcd26b462cc4975252369db6e9d 66 0x68f75a0e2210f52a90704ed5f511918d1f6bcfcd26b462cc4975252369db6e9d
67 0x6220c0699696e9bcab0fe3a80d437519bd2bdf3caef665e106b2dd47585ddd9f 67 0x6220c0699696e9bcab0fe3a80d437519bd2bdf3caef665e106b2dd47585ddd9f
68 0x553ad47b129fb347992b576479b0a89f8d71f1196f83e5eaab5f533a1dd6f6d7 68 0x553ad47b129fb347992b576479b0a89f8d71f1196f83e5eaab5f533a1dd6f6d7
69 0x239aef387e116ec8730fa15af053485ca707650d9f8917a75f22acf6213197df 69 0x239aef387e116ec8730fa15af053485ca707650d9f8917a75f22acf6213197df
G.2.3. Coefficients of w'(x): H.2.3. Coefficients of w'(x)
0 0x6bd7f1fc5dd51b7d832848c180f019bcbdb101d4b3435230a79cc4f95c35e15e 0 0x6bd7f1fc5dd51b7d832848c180f019bcbdb101d4b3435230a79cc4f95c35e15e
1 0x17413bb3ee505184a504e14419b8d7c8517a0d268f65b0d7f5b0ba68d6166dd0 1 0x17413bb3ee505184a504e14419b8d7c8517a0d268f65b0d7f5b0ba68d6166dd0
2 0x47f4471beed06e5e2b6d5569c20e30346bdba2921d9676603c58e55431572f90 2 0x47f4471beed06e5e2b6d5569c20e30346bdba2921d9676603c58e55431572f90
3 0x2af7eaafd04f6910a5b01cdb0c27dca09487f1cd1116b38db34563e7b0b414eb 3 0x2af7eaafd04f6910a5b01cdb0c27dca09487f1cd1116b38db34563e7b0b414eb
4 0x57f0a593459732eef11d2e2f7085bf9adf534879ba56f7afd17c4a40d3d3477b 4 0x57f0a593459732eef11d2e2f7085bf9adf534879ba56f7afd17c4a40d3d3477b
5 0x4da04e912f145c8d1e5957e0a9e44cca83e74345b38583b70840bdfdbd0288ed 5 0x4da04e912f145c8d1e5957e0a9e44cca83e74345b38583b70840bdfdbd0288ed
6 0x7cc9c3a51a3767d9d37c6652c349adc09bfe477d99f249a2a7bc803c1c5f39ed 6 0x7cc9c3a51a3767d9d37c6652c349adc09bfe477d99f249a2a7bc803c1c5f39ed
7 0x425d7e58b8adf87eebf445b424ba308ee7880228921651995a7eab548180ad49 7 0x425d7e58b8adf87eebf445b424ba308ee7880228921651995a7eab548180ad49
8 0x48156db5c99248234c09f43fedf509005943d3d5f5d7422621617467b06d314f 8 0x48156db5c99248234c09f43fedf509005943d3d5f5d7422621617467b06d314f
 End of changes. 95 change blocks. 
213 lines changed or deleted 462 lines changed or added

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