draft-ietf-lwig-curve-representations-01.txt   draft-ietf-lwig-curve-representations-02.txt 
lwig R. Struik lwig R. Struik
Internet-Draft Struik Security Consultancy Internet-Draft Struik Security Consultancy
Intended status: Informational November 06, 2018 Intended status: Informational March 11, 2019
Expires: May 10, 2019 Expires: September 12, 2019
Alternative Elliptic Curve Representations Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-01 draft-ietf-lwig-curve-representations-02
Abstract Abstract
This document specifies how to represent Montgomery curves and This document specifies how to represent Montgomery curves and
(twisted) Edwards curves as curves in short-Weierstrass form and (twisted) Edwards curves as curves in short-Weierstrass form and
illustrates how this can be used to carry out elliptic curve illustrates how this can be used to carry out elliptic curve
computations using existing implementations of, e.g., ECDSA and ECDH computations using existing implementations of, e.g., ECDSA and ECDH
using NIST prime curves. using NIST prime curves.
Requirements Language Requirements Language
skipping to change at page 1, line 41 skipping to change at page 1, line 41
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on May 10, 2019. This Internet-Draft will expire on September 12, 2019.
Copyright Notice Copyright Notice
Copyright (c) 2018 IETF Trust and the persons identified as the Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
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 . . . . . . . . . . . . . . . . . . 4
3. Use of Representation Switches . . . . . . . . . . . . . . . 4 3. Use of Representation Switches . . . . . . . . . . . . . . . 4
4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 5 4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 5
4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 5 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 6
4.3. Specification of ECDSA-SHA256-Wei25519 . . . . . . . . . 5 4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 6
4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 6 4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 6
5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6. Security Considerations . . . . . . . . . . . . . . . . . . . 7 6. Security Considerations . . . . . . . . . . . . . . . . . . . 8
7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 8 7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 8
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 8 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 9
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 9
10.1. Normative References . . . . . . . . . . . . . . . . . . 8 10.1. Normative References . . . . . . . . . . . . . . . . . . 9
10.2. Informative References . . . . . . . . . . . . . . . . . 9 10.2. Informative References . . . . . . . . . . . . . . . . . 10
Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 10 Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 10
A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 10 A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 10
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 10 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 11
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 10 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 11
Appendix B. Elliptic Curve Nomenclature . . . . . . . . . . . . 11 Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 11
Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 11 B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 11
C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 11 B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 13
C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 12 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 14
C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 13 C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 14
Appendix D. Relationship Between Curve Models . . . . . . . . . 14 C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 15
D.1. Mapping between twisted Edwards Curves and Montgomery C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 15
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 14 Appendix D. Relationship Between Curve Models . . . . . . . . . 16
D.2. Mapping between Montgomery Curves and Weierstrass Curves 14 D.1. Mapping between Twisted Edwards Curves and Montgomery
D.3. Mapping between twisted Edwards Curves and Weierstrass Curves . . . . . . . . . . . . . . . . . . . . . . . . . 16
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 15 D.2. Mapping between Montgomery Curves and Weierstrass Curves 17
Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 15 D.3. Mapping between Twisted Edwards Curves and Weierstrass
E.1. Curve Definition and Alternative Representations . . . . 15 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 18
E.2. Switching between Alternative Representations . . . . . . 16 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 18
E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 17 E.1. Curve Definition and Alternative Representations . . . . 18
Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 19 E.2. Switching between Alternative Representations . . . . . . 19
F.1. Isomorphic Mapping between Weierstrass Curves . . . . . . 19 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 20
F.2. Isogenous Mapping between Weierstrass Curves . . . . . . 20 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 22
F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 22
Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 21 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 23
G.1. Further Alternative Representations . . . . . . . . . . . 21 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 24
G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 22 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 25
G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 23 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 26
Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 24 G.1. Further Alternative Representations . . . . . . . . . . . 26
H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 24 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 26
H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 24 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 27
H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 26 Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 29
H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 29 H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 29
H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 30 H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 29
H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 30 H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 31
H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 32 H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 34
H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 35 H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 35
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 36 H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 35
H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 37
H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 40
Appendix I. Point Compression . . . . . . . . . . . . . . . . . 41
I.1. Point Compression for Weierstrass Curves . . . . . . . . 42
I.2. Point Compression for Montgomery Curves . . . . . . . . . 42
I.3. Point Compression for Twisted Edwards Curves . . . . . . 43
Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 43
J.1. Conversion between Bit Strings and Integers . . . . . . . 43
J.2. Conversion between Octet Strings and Integers (OS2I,
I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 44
J.3. Conversion between Octet Strings and Bit Strings (BS2OS,
OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 44
J.4. Conversion between Field Elements and Octet Strings
(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 44
J.5. Ordering Conventions . . . . . . . . . . . . . . . . . . 45
Appendix K. Representations for Curve25519 Family Members . . . 46
K.1. Wei25519 . . . . . . . . . . . . . . . . . . . . . . . . 46
Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 46
L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 46
L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 47
L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 47
L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 47
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 47
1. Fostering Code Reuse with New Elliptic Curves 1. Fostering Code Reuse with New Elliptic Curves
It is well-known that elliptic curves can be represented using It is well-known that elliptic curves can be represented using
different curve models. Recently, IETF standardized elliptic curves different curve models. Recently, IETF standardized elliptic curves
that are claimed to have better performance and improved robustness that are claimed to have better performance and improved robustness
against "real world" attacks than curves represented in the against "real world" attacks than curves represented in the
traditional "short" Weierstrass model. This document specifies an traditional "short" Weierstrass model. This document specifies an
alternative representation of points of Curve25519, a so-called alternative representation of points of Curve25519, a so-called
Montgomery curve, and of points of Edwards25519, a so-called twisted Montgomery curve, and of points of Edwards25519, a so-called twisted
skipping to change at page 3, line 50 skipping to change at page 4, line 25
elliptic curve arithmetic for curves in "short" Weierstrass form (see elliptic curve arithmetic for curves in "short" Weierstrass form (see
Appendix C.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 E. 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 P-256, to
also implement the CFRG curves Curve25519 and Edwards25519. We also also implement the CFRG curves Curve25519 and Edwards25519. We also
cater to reusing of existing code where some domain parameters may cater to reusing of existing code where some domain parameters may
have been hardcoded, thereby widening the scope of applicability. To have been hardcoded, thereby widening the scope of applicability. To
this end, we specify the short-Weierstrass curves Wei25519.2 and this end, we specify the short-Weierstrass curves Wei25519.2 and
Wei25519.-3, with hardcoded domain parameter a=2 and a=-3 (mod p), Wei25519.-3, with hardcoded domain parameter a=2 and a=-3 (mod p),
respectively; see Appendix G. respectively; see Appendix G. (Here, p is the characteristic of the
field over which these curves are defined.)
3. Use of Representation Switches 3. Use of Representation Switches
The curves Curve25519, Edwards25519, and Wei25519, as specified in The curves Curve25519, Edwards25519, and Wei25519, as specified in
Appendix E.3, are all isomorphic, with the transformations of Appendix E.3, are all isomorphic, with the transformations of
Appendix E.2. These transformations map the specified base point of Appendix E.2. These transformations map the specified base point of
each of these curves to the specified base point of each of the other each of these curves to the specified base point of each of the other
curves. Consequently, a public-key pair (k,R:=k*G) for any one of curves. Consequently, a public-key pair (k,R:=k*G) for any one of
these curves corresponds, via these isomorphic mappings, to the these curves corresponds, via these isomorphic mappings, to the
public-key pair (k, R':=k*G') for each of these other curves (where G public-key pair (k, R':=k*G') for each of these other curves (where G
skipping to change at page 5, line 41 skipping to change at page 6, line 16
RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature
scheme, with instantiation by the twisted Edwards curve Edwards25519. scheme, with instantiation by the twisted Edwards curve Edwards25519.
One can implement the computation of the ephemeral key pair for One can implement the computation of the ephemeral key pair for
Ed25519 using an existing Montgomery curve implementation by (1) Ed25519 using an existing Montgomery curve implementation by (1)
generating a public-private key pair (k, R':=k*G') for Curve25519; 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 (2) representing this public-private key as the pair (k, R:=k*G) for
Ed25519. As before, the representation change can be implemented via Ed25519. As before, the representation change can be implemented via
a simple wrapper. Note that the Montgomery ladder specified in a simple wrapper. Note that the Montgomery ladder specified in
Section 5 of RFC7748 [RFC7748] does not provide sufficient Section 5 of RFC7748 [RFC7748] does not provide sufficient
information to reconstruct R' (since it does not compute the information to reconstruct R':=(u, v) (since it does not compute the
y-coordinate of R'). However, this deficiency can be remedied by v-coordinate of R'). However, this deficiency can be remedied by
using a slightly modified version of the Montgomery ladder that using a slightly modified version of the Montgomery ladder that
includes reconstruction of the y-coordinate of R':=k*G' at the end of includes reconstruction of the v-coordinate of R':=k*G' at the end of
hereof (which uses the v-coordinate Gv of the base point of hereof (which uses the v-coordinate of the base point of Curve25519
Curve25519 as well). For details, see Appendix D.2. as well). For details, see Appendix C.1.
4.3. Specification of ECDSA-SHA256-Wei25519 4.3. Specification of ECDSA25519
FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and 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 can be instantiated not just with the NIST prime curves, but also
with other Weierstrass curves (that satisfy additional cryptographic with other Weierstrass curves (that satisfy additional cryptographic
criteria). In particular, one can instantiate this scheme with the criteria). In particular, one can instantiate this scheme with the
Weierstrass curve Wei25519 and the hash function SHA-256, where an Weierstrass curve Wei25519 and the hash function SHA-256, where an
implementation may generate a public-private key pair for Wei25519 by implementation may generate a public-private key pair for Wei25519 by
(1) internally carrying out these computations on the Montgomery (1) internally carrying out these computations on the Montgomery
curve Curve25519, the twisted Edwards curve Edwards25519, or even the curve Curve25519, the twisted Edwards curve Edwards25519, or even the
Weierstrass curve Wei25519.-3 (with hardcoded a=-3 domain parameter); Weierstrass curve Wei25519.-3 (with hardcoded a=-3 domain parameter);
(2) representing the result as a key pair for the curve Wei25519. (2) representing the result as a key pair for the curve Wei25519.
Note that, in either case, one can implement these schemes with the Note that, in either case, one can implement these schemes with the
same representation conventions as used with existing NIST same representation conventions as used with existing NIST
specifications, including bit/byte-ordering, compression functions, specifications, including bit/byte-ordering, compression functions,
and the-like. This allows implementations of ECDSA with the hash and the-like. This allows generic implementations of ECDSA with the
function SHA-256 and with the NIST curve P-256 or with the curve 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 Wei25519 specified in this draft to use the same implementation
(instantiated with, respectively, the NIST P-256 elliptic curve (instantiated with, respectively, the NIST P-256 elliptic curve
domain parameters or with the domain parameters of curve Wei25519 domain parameters or with the domain parameters of curve Wei25519
specified in Appendix E). specified in Appendix E).
4.4. Other Uses 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,
skipping to change at page 6, line 40 skipping to change at page 7, line 15
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.
5. Caveats 5. Caveats
The examples above illustrate how specifying the Weierstrass curve The examples above illustrate how specifying the Weierstrass curve
Wei25519 may facilitate reuse of existing code and may simplify Wei25519 (or any curve in short-Weierstrass format, for that matter)
standards development. However, the following caveats apply: may facilitate reuse of existing code and may simplify standards
development. However, the following caveats apply:
1. Unfriendly wire formats. The transformations between alternative 1. Wire format. The transformations between alternative curve
curve representations can be implemented at negligible relative representations can be implemented at negligible relative
incremental cost if the curve points are represented as affine incremental cost if the curve points are represented as affine
points. If a point is represented in compressed format, points. If a point is represented in compressed format,
conversion usually requires a costly point decompression step. conversion usually requires a costly point decompression step.
This is the case in [RFC7748], where the inputs to the co-factor This is the case in [RFC7748], where the inputs to the co-factor
Diffie-Hellman scheme X25519, as well as its output, are Diffie-Hellman scheme X25519, as well as its output, are
represented in x-coordinate-only format; represented in u-coordinate-only format. This is also the case
in [RFC8032], where the EdDSA signature includes the ephemeral
signing key represented in compressed format (see Appendix I for
details);
2. Unfriendly representation conventions. While elliptic curve 2. Representation conventions. While elliptic curve computations
computations are carried-out in a field GF(q) and, thereby, are carried-out in a field GF(q) and, thereby, involve large
involve large integer arithmetic, these integers are represented integer arithmetic, these integers are represented as bit- and
as bit- and byte-strings. Here, [RFC8032] uses least- byte-strings. Here, [RFC8032] uses least-significant-byte
significant-byte (LSB)/least-significant-bit (lsb) conventions, (LSB)/least-significant-bit (lsb) conventions, whereas [RFC7748]
whereas [RFC7748] uses LSB/most-significant-bit (msb) uses LSB/most-significant-bit (msb) conventions, and where most
conventions, and where most other cryptographic specifications, other cryptographic specifications, including NIST SP800-56a
including NIST SP800-56a [SP-800-56a], FIPS Pub 186-4 [SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005
[FIPS-186-4], and ANSI X9.62-2005 [ANSI-X9.62] use MSB/msb [ANSI-X9.62] use MSB/msb conventions. Since each pair of
conventions. Since each pair of conventions is different, this conventions is different (see Appendix J for details), this does
does necessitate bit/byte representation conversions; necessitate bit/byte representation conversions;
3. Unfriendly domain parameters. All traditional NIST curves are 3. Domain parameters. All traditional NIST curves are Weierstrass
Weierstrass curve with domain parameter a=-3, while all Brainpool curves with domain parameter a=-3, while all Brainpool curves
curves [RFC5639] are isomorphic to a Weierstrass curve of this [RFC5639] are isomorphic to a Weierstrass curve of this form.
form. Thus, one can expect there to be existing Weierstrass Thus, one can expect there to be existing Weierstrass
implementations with a hardcoded a=-3 domain parameter implementations with a hardcoded a=-3 domain parameter
("Jacobian-friendly"). For those implementations, including the ("Jacobian-friendly"). For those implementations, including the
curve Wei25519 as a potential vehicle for offering support for curve Wei25519 as a potential vehicle for offering support for
the CFRG curves Curve25519 and Edwards25519 is not possible, the CFRG curves Curve25519 and Edwards25519 is not possible,
since not of the required form. Instead, one has to implement since not of the required form. Instead, one has to implement
Curve25519.-3 and include code that implements the isogeny and Wei25519.-3 and include code that implements the isogeny and dual
dual isogeny from and to Wei25519. This isogeny has degree l=47 isogeny from and to Wei25519. This isogeny has degree l=47 and
and requires roughly 9kB of storage for isogeny and dual-isogeny requires roughly 9kB of storage for isogeny and dual-isogeny
computations (see the tables in Appendix H). Note that storage computations (see the tables in Appendix H). Note that storage
would have reduced to a single 32-bye table if the curve would would have reduced to a single 64-byte table if only the curve
have been generated so as to be isomorphic to a Weierstrass curve would have been generated so as to be isomorphic to a Weierstrass
with hardcoded a=-3 parameter (this corresponds to l=1). Note: curve with hardcoded a=-3 parameter (this corresponds to l=1).
an example of such a curve is the Montgomery curve M_{A,B} over Note: an example of such a curve is the Montgomery curve M_{A,B}
GF(p) with p=2^255-19, A=-1410290, and B=1 or (if one wants the over GF(p) with p=2^255-19, B=1, and A=-1410290 or (if one wants
base point to still have u-coordinate u=9) A=-3960846. In either the base point to still have u-coordinate u=9) A=-3960846. In
case, the resulting curve has the same cryptographic properties either case, the resulting curve has the same cryptographic
as Curve25519, while being more "Jacobian-friendly". properties as Curve25519 and the same performance (since A is a
3-byte integer as is the case with the domain parameter A=486662
used with Curve25519), while being "Jacobian-friendly" by design.
6. Security Considerations 6. Security Considerations
The different representations of elliptic curve points discussed in The different representations of elliptic curve points discussed in
this document are all obtained using a publicly known transformation, this document are all obtained using a publicly known transformation,
which is either an isomorphism or a low-degree isogeny. It is well- which is either an isomorphism or a low-degree isogeny. It is well-
known that an isomorphism maps elliptic curve points to equivalent known that an isomorphism maps elliptic curve points to equivalent
mathematical objects and that the complexity of cryptographic mathematical objects and that the complexity of cryptographic
problems (such as the discrete logarithm problem) of curves related problems (such as the discrete logarithm problem) of curves related
via a low-degree isogeny are tightly related. Thus, the use of these via a low-degree isogeny are tightly related. Thus, the use of these
skipping to change at page 8, line 19 skipping to change at page 8, line 48
for over 15 years. for over 15 years.
7. Privacy Considerations 7. Privacy Considerations
The transformations between different curve models described in this The transformations between different curve models described in this
document are publicly known and, therefore, do not affect privacy document are publicly known and, therefore, do not affect privacy
provisions. provisions.
8. IANA Considerations 8. IANA Considerations
There is *currently* no IANA action required for this document. New An object identifier is requested for Wei25519 and ECDSA25519, using
object identifiers would be required in case one wishes to specify the representation conventions in this document.
one or more of the "offspring" protocols exemplified in Section 4.
9. Acknowledgements 9. Acknowledgements
Thanks to Nikolas Rosener for discussions surrounding implementation Thanks to Nikolas Rosener for discussions surrounding implementation
details of the techniques described in this document and to Phillip details of the techniques described in this document and to Phillip
Hallam-Baker for triggering inclusion of verbiage on the use of Hallam-Baker for triggering inclusion of verbiage on the use of
Montgomery ladders with recovery of the y-coordinate. Montgomery ladders with recovery of the y-coordinate. Thanks to
Stanislav Smyshlyaev for his careful review.
10. References 10. References
10.1. Normative References 10.1. Normative References
[ANSI-X9.62] [ANSI-X9.62]
ANSI X9.62-2005, "Public Key Cryptography for the ANSI X9.62-2005, "Public Key Cryptography for the
Financial Services Industry: The Elliptic Curve Digital Financial Services Industry: The Elliptic Curve Digital
Signature Algorithm (ECDSA)", American National Standard Signature Algorithm (ECDSA)", American National Standard
for Financial Services, Accredited Standards Committee X9, for Financial Services, Accredited Standards Committee X9,
skipping to change at page 10, line 5 skipping to change at page 10, line 31
2003. 2003.
[GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to [GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to
Elliptic Curve Cryptography", New York: Springer-Verlag, Elliptic Curve Cryptography", New York: Springer-Verlag,
2004. 2004.
[HW-ECC] W.P. Liu, "How to Use the Kinets LTC ECC HW to Accelerate [HW-ECC] W.P. Liu, "How to Use the Kinets LTC ECC HW to Accelerate
Curve25519 (version 7)", NXP, Curve25519 (version 7)", NXP,
https://community.nxp.com/docs/DOC-330199, April 2017. https://community.nxp.com/docs/DOC-330199, April 2017.
[Ladder] P.L. Montgomery, "Speeding the Pollard and Elliptic Curve
Methods of Factorization", Mathematics of
Computation, Vol. 48, 1987.
[tEd-Formulas]
H. Hisil, K.K.H. Wong, G. Carter, E. Dawson, "Twisted
Edwards Curves Revisited", ASIACRYPT 2008, Lecture Notes
in Computer Science, Vol. 5350, New York: Springer-Verlag,
2008.
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 "secant-and-tangent" rule, where under addition, via the so-called "secant-and-tangent" rule, where
the point at infinity serves as the identity element. See the point at infinity serves as the identity element. See
Appendix C.1 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} and where A is unequal to (+/-)2 and where B is nonzero. The points
are the ordered pairs (u, v) whose coordinates are elements of GF(q) of M_{A,B} are the ordered pairs (u, v) whose coordinates are
and that satisfy the defining equation (the so-called affine points), elements of GF(q) and that satisfy the defining equation (the so-
together with the special point O (the so-called "point at called affine points), together with the special point O (the so-
infinity").This set forms a group under addition, via the so-called called "point at infinity"). This set forms a group under addition,
"secant-and-tangent" rule, where the point at infinity serves as the via the so-called "secant-and-tangent" rule, where the point at
identity element. See Appendix C.2 for details of the group infinity serves as the identity element. See Appendix C.2 for
operation. details of the group 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 O:=(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 C.3 for details of the group operation. equation.) See Appendix C.3 for details of the group operation.
An Edwards curve is a twisted Edwards curve with a=1. An Edwards curve is a twisted Edwards curve with a=1.
Appendix B. Elliptic Curve Nomenclature Appendix B. Elliptic Curve Nomenclature and Finite Fields
B.1. Elliptic Curve Nomenclature
Each curve defined in Appendix A forms a commutative group under Each curve defined in Appendix A forms a commutative group under
addition. In Appendix C we specify the group laws, which depend on addition (denoted by '+'). In Appendix C we specify the group laws,
the curve model in question. For completeness, we here include some which depend on the curve model in question. For completeness, we
common elliptic curve nomenclature and basic properties (primarily so here include some common elliptic curve nomenclature and basic
as to keep this document self-contained). These notions are mainly properties (primarily so as to keep this document self-contained).
used in Appendix E and Appendix G and not essential for our These notions are mainly used in Appendix E and Appendix G and not
exposition. This section can be skipped at first reading. 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 Any point P of a curve E is a generator of the cyclic subgroup
(P):={k*P | k = 0, 1, 2,...} of the curve. If (P) has cardinality l, (P):={k*P | k = 0, 1, 2,...} of the curve. (Here, k*P denotes the
then l is called the order of P. The order of a curve is the sum of k copies of P, where 0*P is the identity element O of the
cardinality of the set of its points. A curve is cyclic if it is curve.) If (P) has cardinality l, then l is called the order of P.
generated by some point of this curve. All curves of prime order are The order of curve E is the cardinality of the set of its points,
cyclic, while all curves of order |E| = h*n, where n is a large prime commonly denoted by |E|. A curve is cyclic if it is generated by some
number and where h is a small number (the so-called co-factor), have point of this curve. All curves of prime order are cyclic, while all
a large cyclic subgroup of prime order n. In this case, a generator curves of order h*n, where n is a large prime number and where h is a
of order n is called a base point, commonly denoted by G. A point of small number (the so-called co-factor), have a large cyclic subgroup
order dividing h is said to be in the small subgroup. For curves of of prime order n. In this case, a generator of order n is called a
prime order, this small subgroup is the singleton set, consisting of base point, commonly denoted by G. A point of order dividing h is
only the identity element. 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 O. If a point is not in the small subgroup, it has order at
least n.
If R is a point on a curve E that is also contained in (P), there is If R is a point of the curve that is also contained in (P), there is
a unique integer k in the interval [0, l-1] so that R=kP, where l is a unique integer k in the interval [0, l-1] so that R=k*P, where l is
the order of P. This number is called the discrete logarithm of R to the order of P. This number is called the discrete logarithm of R to
the base P. The discrete logarithm problem is the problem of finding the base P. The discrete logarithm problem is the problem of finding
the discrete logarithm of R to the base P for any two points P and R the discrete logarithm of R to the base P for any two points P and R
of the curve, if such a number exists. of the curve, if such a number exists.
A public-private key pair is an ordered pair (k, R:=kG), where G is a If P is a fixed base point G of the curve, the pair (k, R:=k*G) is
fixed base point of the curve. Here, k (the private key) is an called a public-private key pair, the integer k the private key, and
integer in the interval [0,n-1], where G has order n. the point R the corresponding public key. The private key k can be
represented as 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 In this document, a quadratic twist of a curve E defined over a field
E' related to E, with cardinality |E|+|E'|=2*(q+1). If E is a curve GF(q) is a curve E' related to E, with cardinality |E'|,
in one of the curve models specified in this document, a quadratic where |E|+|E'|=2*(q+1). If E is a curve in one of the curve models
twist of this curve can be expressed using the same curve model, specified in this document, a quadratic twist of this curve can be
although (naturally) with different curve parameters. expressed using the same curve model, although (naturally) with its
own curve parameters. Two curves E and E' defined over a field GF(q)
are said to be isogenous if these have the same order and are said to
be isomorphic if these have the same group structure. Note that
isomorphic curves have necessarily the same order and are, thus, a
special type of isogenous curves. Further details are out of scope.
Weierstrass curves can have prime order, whereas Montgomery curves
and twisted Edwards curves always have an order that is a multiple of
four (and, thereby, a small subgroup of cardinality four).
An ordered pair (x, y) whose coordinates are elements of GF(q) can be
associated with any ordered triple of the form [x*z: y*z: z], where z
is a nonzero element of GF(q), and can be uniquely recovered from
such a representation. The latter representation is commonly called
a representation in projective coordinates.
The group laws in Appendix C are mostly expressed in terms of affine
points, but can also be expressed in terms of the representation of
these points in projective coordinates, thereby allowing clearing of
denominators. The group laws may also involve non-affine points
(such as the point at infinity O of a Weierstrass curve or of a
Montgomery curve). Those can also be represented in projective
coordinates. Further details are out of scope.
B.2. Finite Fields
The field GF(q), where q is an odd prime power, is defined as
follows.
If p is a prime number, the field GF(p) consists of the integers in
the interval [0,p-1] and two binary operations on this set: addition
and multiplication modulo p.
If q=p^m and m>0, the field GF(q) is defined in terms of an
irreducible polynomial f(z) in z of degree m with coefficients in
GF(p) (i.e., f(z) cannot be written as the product of two polynomials
in z of lower degree with coefficients in GF(p)): in this case, GF(q)
consists of the polynomials in z of degree smaller than m with
coefficients in GF(p) and two binary operations on this set:
polynomial addition and polynomial multiplication modulo the
irreducible polynomial f(z). By definition, each element x of GF(q)
is a polynomial in z of degree smaller than m and can, therefore, be
uniquely represented as a vector (x_{m-1}, x_{m-2}, ..., x_1, x_0) of
length m with coefficients in GF(p), where x_i is the coefficient of
z^i of polynomial x. Note that this representation depends on the
irreducible polynomial f(z) of the field GF(p^m) in question (which
is often fixed in practice). Note that GF(q) contains the prime
field GF(p) as a subset. If m=1, we always pick f(z):=z, so that the
definions of GF(p) and GF(p^1) above coincide. If m>1, then GF(q) is
called a (nontrivial) extension field over GF(p). The number p is
called the characteristic of GF(q).
A field element y is called a square in GF(q) if it can be expressed
as y:=x^2 for some x in GF(q); it is called a non-square in GF(q)
otherwise. If y is a square in GF(q), we denote by sqrt(y) one of
its square roots (the other one being -sqrt(y)). For methods for
computing square roots and inverses in GF(q) - if these exist - see
Appendix L.1 and Appendix L.2, respectively.
NOTE: The curves in Appendix E and Appendix G are all defined over a
prime field GF(p), thereby reducing all operations to simple modular
integer arithmetic. Strictly speaking we could, therefore, have
refrained from introducing extension fields. Nevertheless, we
included the more general exposition, so as to accommodate potential
introduction of new curves that are defined over a (nontrivial)
extension field at some point in the future. This includes curves
proposed for post-quantum isogeny-based schemes, which are defined
over a quadratic extension field (i.e., where q:=p^2), and elliptic
curves used with pairing-based cryptography. The exposition in
either case is almost the same and now automatically yields, e.g.,
data conversion routines for any finite field object (see
Appendix J). Readers not interested in this, could simply view all
fields as prime fields.
Appendix C. Elliptic Curve Group Operations Appendix C. Elliptic Curve Group Operations
C.1. Group Law for Weierstrass Curves 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
= (y2 - y1)/(x2 - x1).
Let P:= (x1, y1) be an affine point of the Weierstrass curve W_{a,b} lambda:= (Y2 - Y1)/(X2 - X1).
and let Q:=2*P, where Q is not the identity element. Then Q:= (x,
y), where
x + 2*x1 = lambda^2 and y + y1 = lambda*(x1 - x), where Let P:=(X1, Y1) be an affine point of the Weierstrass curve W_{a,b}
lambda=(3*x1^2 + a)/(2*y1). and let Q:=2*P, where Q is not the identity element. Then Q:=(X, Y),
where
From the group law above it follows that if P=(x, y), P1=k*P=(x1, X + 2*X1 = lambda^2 and Y + Y1 = lambda*(X1 - X), where
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). lambda:=(3*X1^2 + a)/(2*Y1).
This property allows recovery of the y-coordinate of a point P1=k*P From the group laws above it follows that if P=(X, Y), P1=k*P=(X1,
Y1), and P2=(k+1)*P=(X2, Y2) are distinct 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 that is computed via the so-called Montgomery ladder, where P is an
affine point with nonzero y-coordinate. Further details are out of affine point with nonzero Y-coordinate (i.e., it does not have order
scope. two). Further details are out of scope.
C.2. Group Law for Montgomery Curves 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:=(u, v) 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 (u, -v) and one has P + (-P) = O.
Let P1:=(x1, y1) and P2:=(x2, y2) be distinct affine points of the Let P1:=(u1, v1) and P2:=(u2, v2) 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:=(u, v), where
x + x1 + x2 = B*lambda^2 - A and y + y1 = lambda*(x1 - x), where u + u1 + u2 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), where
lambda=(y2 - y1)/(x2 - x1).
Let P:= (x1, y1) be an affine point of the Montgomery curve M_{A,B} lambda:=(v2 - v1)/(u2 - u1).
and let Q:=2*P, where Q is not the identity element. Then Q:= (x,
y), where
x + 2*x1 = B*lambda^2 - A and y + y1 = lambda*(x1 - x), where
lambda=(3*x1^2 + 2*A*x1+1)/(2*B*y1).
From the group law above it follows that if P=(x, y), P1=k*P=(x1, Let P:=(u1, v1) be an affine point of the Montgomery curve M_{A,B}
y1), and P2=(k+1)*P=(x2, y2) are affine points of the Montgomery and let Q:=2*P, where Q is not the identity element. Then Q:=(u, v),
curve M_{A,B} and if y is nonzero, then the y-coordinate of P1 can be where
expressed in terms of the x-coordinates of P, P1, and P2, and the
y-coordinate of P, as
y1=((x*x1+1)*(x+x1+2*A)-2*A-x2*(x-x1)^2)/(2*B*y). u + 2*u1 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), where
This property allows recovery of the y-coordinate of a point P1=k*P lambda:=(3*u1^2 + 2*A*u1+1)/(2*B*v1).
From the group laws above it follows that if P=(u, v), P1=k*P=(u1,
v1), and P2=(k+1)*P=(u2, v2) are distinct affine points of the
Montgomery curve M_{A,B} and if v is nonzero, then the v-coordinate
of P1 can be expressed in terms of the u-coordinates of P, P1, and
P2, and the v-coordinate of P, as
v1=((u*u1+1)*(u+u1+2*A)-2*A-u2*(u-u1)^2)/(2*B*v).
This property allows recovery of the v-coordinate of a point P1=k*P
that is computed via the so-called Montgomery ladder, where P is an that is computed via the so-called Montgomery ladder, where P is an
affine point with nonzero y-coordinate. Further details are out of affine point with nonzero v-coordinate (i.e., it does not have order
scope. one or two). Further details are out of scope.
C.3. Group Law for Twisted Edwards Curves 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
a*x1*x2)/(1 - d*x1*x2*y1*y2).
y = (y1*y2 - a*x1*x2)/(1 - d*x1*x2*y1*y2).
Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and
let Q:=2*P. 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
d*x1^2*y1^2).
Note that one can use the formulae for point addition for y = (y1^2 - a*x1^2)/(1 - d*x1^2*y1^2).
implementing point doubling, taking inverses and adding the identity
element as well (i.e., the point addition formulae are uniform and Note that one can use the formulae for point addition for point
complete (subject to our Note above)). doubling, taking inverses, and adding the identity element as well
(i.e., the point addition formulae are uniform and complete (subject
to our Note above)).
From the group laws above (subject to our Note 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 twisted Edwards curve E_{a,d} and if x is nonzero, then
the x-coordinate of P1 can be expressed in terms of the y-coordinates
of P, P1, and P2, and the x-coordinate of P, as
x1=(y*y1-y2)/(x*(a-d*y*y1*y2)).
This property allows recovery of the x-coordinate of a point P1=k*P
that is computed via the so-called Montgomery ladder, where P is an
affine point with nonzero x-coordinate (i.e., it does not have order
one or two). Further details are out of scope.
Appendix D. 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.
D.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.
For the Montgomery curves and twisted Edwards curves we consider, the For the Montgomery curves and twisted Edwards curves we consider, the
mapping from M_{A,B} to E_{a,d} is defined by mapping the point at mapping from M_{A,B} to E_{a,d} is defined by mapping the point at
infinity O and the point (0, 0) of order two of M_{A,B} to, infinity O and the point (0, 0) of order two of M_{A,B} to,
respectively, the point (0, 1) and the point (0, -1) of order two of respectively, the point (0, 1) and the point (0, -1) of order two of
E_{a,d}, while mapping each other point (u, v) of M_{A,B} to the E_{a,d}, while mapping each other point (u, v) of M_{A,B} to the
point (x, y):=(u/v, (u-1)/(u+1)) of E_{a,d}. The inverse mapping from point (x,y):=(u/v,(u-1)/(u+1)) of E_{a,d}. The inverse mapping from
E_{a,d} to M_{A,B} is defined by mapping the point (0, 1) and the E_{a,d} to M_{A,B} is defined by mapping the point (0, 1) and the
point (0, -1) of order two of E_{a,d} to, respectively, the point at point (0, -1) of order two of E_{a,d} to, respectively, the point at
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
v):=((1+y)/(1-y), (1+y)/((1-y)*x)) of M_{A,B}. (u,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.
D.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
mapping each other point (u, v) of M_{A,B} to the point (x, y):=(u/ mapping each other point (u,v) of M_{A,B} to the point
B+A/(3*B), v/B) of W_{a,b}. Note that not all Weierstrass curves can (X,Y):=(u/B+A/(3*B),v/B) of W_{a,b}. Note that not all Weierstrass
be injectively mapped to Montgomery curves, since the latter have a curves can be injectively mapped to Montgomery curves, since the
point of order two and the former may not. In particular, if a latter have a point of order two and the former may not. In
Weierstrass curve has prime order, such as is the case with the so- particular, if a Weierstrass curve has prime order, such as is the
called "NIST curves", this inverse mapping is not defined. case with the so-called "NIST curves", this inverse mapping is not
defined.
If the Weierstrass curve W_{a,b} has a point (alpha,0) of order two
and c:=a+3*(alpha)^2 is a square in GF(q), one can map points of this
curve to points of the Montgomery curve M_{A,B}, where A:=3*alpha/
gamma and B:=1/gamma and where gamma is any square root of c. In
this case, the mapping from W_{a,b} to M_{A,B} is defined by mapping
the point at infinity O of W_{a,b} to the point at infinity O of
M_{A,B}, while mapping each other point (X,Y) of W_{a,b} to the point
(u,v):=((X-alpha)/gamma,Y/gamma) of M_{A,B}. As before, this defines
a one-to-one correspondence, which - in fact - is an isomorphism
between W_{a,b} and M_{A,B}. It is easy to see that the mapping from
W_{a,b} to M_{A,B} and that from M_{A,B} to W_{a,b} (if defined) are
each other's inverse.
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. original curve, thereby potentially allowing code reuse.
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 (which value is
known to allow more efficient implementations) cannot always be used known to allow more efficient implementations) cannot always be used
this way, since the curve W_{a,b} resulting from an isomorphic this way, since the curve W_{a,b} resulting from an isomorphic
mapping cannot always be expressed as a Weierstrass curve with a=-3 mapping cannot always be expressed as a Weierstrass curve with a=-3
via a coordinate transformation. For more details, see Appendix F. via a coordinate transformation. For more details, see Appendix F.
D.3. Mapping between twisted Edwards Curves and Weierstrass Curves 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 D.1 and the one between Montgomery and Montgomery curves of Appendix D.1 and the one between Montgomery and
Weierstrass curves of Appendix D.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 - if these exist) to
inverse of this mapping. realize the inverse of this mapping.
Appendix E. Curve25519 and Cousins Appendix E. Curve25519 and Cousins
E.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 E.3. the point (Gx, Gy), where parameters are as specified in
This curve is denoted as Edwards25519. For this curve, the parameter Appendix E.3. This curve is denoted as Edwards25519. For this
a is a square in GF(p), whereas d is not, so the group laws of curve, the parameter a is a square in GF(p), whereas d is not, so the
Appendix C.3 apply. group laws of 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 E.3. This (GX, GY), where parameters are as specified in Appendix E.3. This
curve is denoted as Wei25519. curve is denoted as Wei25519.
E.2. Switching between Alternative Representations E.2. Switching between Alternative Representations
Each affine point (u,v) of Curve25519 corresponds to the point Each affine point (u, v) of Curve25519 corresponds to the point (X,
(x,y):=(u + A/3,y) of Wei25519, while the point at infinity of Y):=(u + A/3, v) of Wei25519, while the point at infinity of
Curve25519 corresponds to the point at infinity of Wei25519. (Here, Curve25519 corresponds to the point at infinity of Wei25519. (Here,
we used the mapping of Appendix D.2.) Under this mapping, the base we used the mappings of Appendix D.2.) Under this mapping, the base
point (Gu,Gv) of Curve25519 corresponds to the base point (Gx',Gy') 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
at infinity of Wei25519 to the point at infinity of Curve25519. Note point at infinity of Wei25519 to the point at infinity of Curve25519.
that this mapping involves a simple shift of the first coordinate and Note that this mapping involves a simple shift of the first
can be implemented via integer-only arithmetic as a shift of (p+A)/3 coordinate and can be implemented via integer-only arithmetic as a
for the isomorphic mapping and a shift of -(p+A)/3 for its inverse, shift of (p+A)/3 for the isomorphic mapping and a shift of -(p+A)/3
where delta=(p+A)/3 is the element of GF(p) defined by for its inverse, where delta=(p+A)/3 is the element of GF(p) defined
by
delta 19298681539552699237261830834781317975544997444273427339909597 delta 19298681539552699237261830834781317975544997444273427339909597
334652188435537 334652188435537
(=0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaad2 (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa
451) aaaaaaaa aaad2451).
(Note that, depending on the implementation details of the field
arithmetic, one may have to shift the result by +p or -p if this
integer is not in the interval [0,p-1].)
The curve Edwards25519 is isomorphic to the curve Curve25519, where The curve Edwards25519 is isomorphic to the curve Curve25519, where
the base point (Gu,Gv) of Curve25519 corresponds to the base point the base point (Gu, Gv) of Curve25519 corresponds to the base point
(Gx,Gy) of Edwards25519 and where the point at infinity and the point (Gx,Gy) of Edwards25519 and where the point at infinity and the point
(0,0) of order two of Curve25519 correspond to, respectively, the (0,0) of order two of Curve25519 correspond to, respectively, the
point (0, 1) and the point (0, -1) of order two of Edwards25519 and point (0, 1) and the point (0, -1) of order two of Edwards25519 and
where each other point (u, v) of Curve25519 corresponds to the point where each other point (u, v) of Curve25519 corresponds to the point
(c*u/v, (u-1)/(u+1)) of Edwards25519, where c is the element of GF(p) (c*u/v, (u-1)/(u+1)) of Edwards25519, where c is the element of GF(p)
defined by defined by
c sqrt(-(A+2)) c sqrt(-(A+2)/B)
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 D.1.) The inverse mapping (Here, we used the mapping of Appendix D.1 and normalized this using
from Edwards25519 to Curve25519 is defined by mapping the point (0, the mapping of Appendix F.1 (where the element s of that appendix is
1) and the point (0, -1) of order two of Edwards25519 to, set to c above).) The inverse mapping from Edwards25519 to
respectively, the point at infinity and the point (0,0) of order two Curve25519 is defined by mapping the point (0, 1) and the point (0,
of Curve25519 and having each other point (x, y) of Edwards25519 -1) of order two of Edwards25519 to, respectively, the point at
correspond to the point ((1 + y)/(1 - y), c*(1 + y)/((1-y)*x)). infinity and the point (0,0) of order two of Curve25519 and having
each other point (x, y) of Edwards25519 correspond to the point ((1 +
y)/(1 - y), c*(1 + y)/((1-y)*x)) of Curve25519.
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
the base point (Gx',Gy') of Wei25519 and where the identity element to the base point (GX,GY) of Wei25519 and where the identity element
(0,1) and the point (0,-1) of order two of Edwards25519 correspond (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 D.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)) of
Edwards25519.
Note that these mappings can be easily realized in projective Note that these mappings can be easily realized if points are
coordinates, using a few field multiplications only, thus allowing represented in projective coordinates, using a few field
switching between alternative representations with negligible multiplications only, thus allowing switching between alternative
relative incremental cost. curve representations with negligible relative incremental cost.
E.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 [RFC7748]; the domain parameters of
Wei25519 are "new". Wei25519 are "new".
General parameters (for all curve models): General parameters (for all curve models):
p 2^{255}-19 p 2^{255}-19
(=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff (=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff
ffffffff ffffffed) ffffffff ffffffed)
h 8 h 8
skipping to change at page 18, line 30 skipping to change at page 21, line 37
Gv 14781619447589544791020593568409986887264606134616475288964881837 Gv 14781619447589544791020593568409986887264606134616475288964881837
755586237401 755586237401
(=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2 (=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2
29e9c5a2 7eced3d9) 29e9c5a2 7eced3d9)
Twisted Edwards curve-specific parameters (for Edwards25519): Twisted Edwards curve-specific parameters (for Edwards25519):
a -1 (-0x01) a -1 (-0x01)
d -121665/121666 d -121665/121666 = - (A-2)/(A+2)
(=370957059346694393431380835087545651895421138798432190163887855 (=370957059346694393431380835087545651895421138798432190163887855
33085940283555) 33085940283555)
(=0x52036cee 2b6ffe73 8cc74079 7779e898 00700a4d 4141d8ab (=0x52036cee 2b6ffe73 8cc74079 7779e898 00700a4d 4141d8ab
75eb4dca 135978a3) 75eb4dca 135978a3)
Gx 15112221349535400772501151409588531511454012693041857206046113283 Gx 15112221349535400772501151409588531511454012693041857206046113283
949847762202 949847762202
skipping to change at page 19, line 17 skipping to change at page 22, line 24
(=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa
aaaaaa98 4914a144) aaaaaa98 4914a144)
b 55751746669818908907645289078257140818241103727901012315294400837 b 55751746669818908907645289078257140818241103727901012315294400837
956729358436 956729358436
(=0x7b425ed0 97b425ed 097b425e d097b425 ed097b42 5ed097b4 (=0x7b425ed0 97b425ed 097b425e d097b425 ed097b42 5ed097b4
260b5e9c 7710c864) 260b5e9c 7710c864)
Gx' 19298681539552699237261830834781317975544997444273427339909597334 GX 19298681539552699237261830834781317975544997444273427339909597334
652188435546 652188435546
(=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 F. 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. In Appendix D we
model, further mappings exist that induce a mapping between elliptic already described relationships between these various curve models.
curves within each curve model. This can be exploited to force some Further mappings exist between elliptic curves within the same curve
of the domain parameters to a value that allows a more efficient model. These can be exploited to force some of the domain parameters
implementation of the addition formulae. to specific values that allow for a more efficient implementation of
the addition formulae.
F.1. Isomorphic Mapping between Weierstrass Curves F.1. Isomorphic Mapping between Twisted Edwards Curves
One can map points of the twisted Edwards curve E_{a,d} to points of
the twisted Edwards curve E_{a',d'}, where a:=a'*s^2 and d:=d'*s^2
for some nonzero element s of GF(q). This defines a one-to-one
correspondence, which - in fact - is an isomorphism between E_{a,d}
and E_{a',d'}.
The mapping from E_{a,d} to E_{a',d'} is defined by mapping the point
(x,y) of E_{a,d} to the point (x', y'):=(s*x, y) of E_{a',d'}. The
inverse mapping from E_{a',d'} to E_{a,d} is defined by mapping the
point (x', y') of E_{a',d'} to the point (x, y):=(x'/s, y') of
E_{a,d}.
Implementations may take advantage of this mapping to carry out
elliptic curve group operations originally defined for a twisted
Edwards curve with generic domain parameters a and d on a
corresponding isomorphic twisted Edwards curve with domain parameters
a' and d' that have a more special form, which are known to allow for
more efficient implementations of addition laws. In particular, it
is known that such efficiency improvements exist if a':=-1 (see
[tEd-Formulas]).
F.2. Isomorphic Mapping between Montgomery Curves
One can map points of the Montgomery curve M_{A,B} to points of the
Montgomery curve M_{A',B'}, where A:=A' and B:=B'*s^2 for some
nonzero element s of GF(q). This defines a one-to-one
correspondence, which - in fact - is an isomorphism between M_{A,B}
and M_{A',B'}.
The mapping from M_{A,B} to M_{A',B'} is defined by mapping the point
at infinity O of M_{A,B} to the point at infinity O of M_{A',B'},
while mapping each other point (u,v) of M_{A,B} to the point (u',
v'):=(u, s*v) of M_{A',B'}. The inverse mapping from M_{A',B'} to
M_{A,B} is defined by mapping the point at infinity O of M_{A',B'} to
the point at infinity O of M_{A,B}, while mapping each other point
(u',v') of M_{A',B'} to the point (u,v):=(u',v'/s) of M_{A,B}.
One can also map points of the Montgomery curve M_{A,B} to points of
the Montgomery curve M_{A',B'}, where A':=-A and B':=-B. This
defines a one-to-one correspondence, which - in fact - is an
isomorphism between M_{A,B} and M_{A',B'}.
In this case, the mapping from M_{A,B} to M_{A',B'} is defined by
mapping the point at infinity O of M_{A,B} to the point at infinity O
of M_{A',B'}, while mapping each other point (u,v) of M_{A,B} to the
point (u',v'):=(-u,v) of M_{A',B'}. The inverse mapping from
M_{A',B'} to M_{A,B} is defined by mapping the point at infinity O of
M_{A',B'} to the point at infinity O of M_{A,B}, while mapping each
other point (u',v') of M_{A',B'} to the point (u,v):=(-u',v') of
M_{A,B}.
Implementations may take advantage of this mapping to carry out
elliptic curve groups operations originally defined for a Montgomery
curve with generic domain parameters A and B on a corresponding
isomorphic Montgomery curve with domain parameters A' and B' that
have a more special form, which is known to allow for more efficient
implementations of addition laws. In particular, it is known that
such efficiency improvements exist if B' assumes a small absolute
value, such as B':=(+/-)1. (see [Ladder]).
F.3. 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 s of the finite field GF(q). This defines a one-to-one nonzero element s of 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'}.
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
y'):=(x*s^2, y*s^3) of W_{a',b'}. The inverse mapping from W_{a',b'} (X',Y'):=(X*s^2, Y*s^3) of W_{a',b'}. The inverse mapping from
to W_{a,b} is defined by mapping the point at infinity O of W_{a',b'} W_{a',b'} to W_{a,b} is defined by mapping the point at infinity O of
to the point at infinity O of W_{a,b}, while mapping each other point W_{a',b'} to the point at infinity O of W_{a,b}, while mapping each
(x', y') of W_{a',b'} to the point (x, y):=(x/s^2, y/s^3) of W_{a,b}. other point (X', Y') of W_{a',b'} to the point (X,Y):=(X'/s^2,Y'/s^3)
of W_{a,b}.
Implementations may take advantage of this mapping to carry out 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 generic domain parameters a and b on a corresponding
Weierstrass curve with domain parameter a' that has a special form, isomorphic Weierstrass curve with domain parameter a' and b' that
which is known to allow for more efficient implementations of have a more special form, which is known to allow for more efficient
addition laws, and translating the result back to the original curve. implementations of addition laws, and translating the result back to
In particular, it is known that such efficiency improvements exist if the original curve. In particular, it is known that such efficiency
a'=-3 (mod p) and one uses so-called Jacobian coordinates with a improvements exist if a'=-3 (mod p), where p is the characteristic of
particular projective version of the addition laws of Appendix C.1. GF(q), and one uses so-called Jacobian coordinates with a particular
While not all Weierstrass curves can be put into this form, all projective version of the addition laws of Appendix C.1. While not
traditional NIST curves have domain parameter a=-3, while all all Weierstrass curves can be put into this form, all traditional
Brainpool curves [RFC5639] are isomorphic to a Weierstrass curve of NIST curves have domain parameter a=-3, while all Brainpool curves
this form. [RFC5639] are isomorphic to a Weierstrass curve of 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 cannot always be form that hard-code the domain parameter a to a= -3 cannot always be
used this way, since the curve W_{a,b} cannot always be expressed in used this way, since the curve W_{a,b} cannot always be expressed in
terms of a Weierstrass curve with a'=-3 via a coordinate 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)
(see Section 3.1.5 of [GECC]). However, even in this case, one can (see Section 3.1.5 of [GECC]). However, even in this case, one can
still express the curve W_{a,b} as a Weierstrass curve with a small still express the curve W_{a,b} as a Weierstrass curve with a small
domain parameter value a', thereby still allowing a more efficient domain parameter value a', thereby still allowing a more efficient
implementation than with a general domain parameter value a. implementation than with a general domain parameter value a.
F.2. Isogenous Mapping between Weierstrass Curves F.4. 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) and where p
a'/a is not a fourth power in GF(q). In that case, this mappping is the characteristic of GF(q), even if a'/a is not a fourth power in
cannot be an isomorphism (see Appendix F.1). Instead, the mapping is GF(q). In that case, this mappping cannot be an isomorphism (see
a so-called isogeny (or homomorphism). Since most elliptic curve Appendix F.3). Instead, the mapping is a so-called isogeny (or
operations process points of prime order or use so-called "co-factor homomorphism). Since most elliptic curve operations process points
multiplication", in practice the resulting mapping has similar of prime order or use so-called "co-factor multiplication", in
properties as an isomorphism. In particular, one can still take practice the resulting mapping has similar properties as an
advantage of this mapping to carry out elliptic curve group isomorphism. In particular, one can still take advantage of this
operations originally defined for a Weierstrass curve with domain mapping to carry out elliptic curve group operations originally
parameter a unequal to -3 (mod p) on a corresponding isogenous defined for a Weierstrass curve with domain parameter a unequal to -3
Weierstrass curve with domain parameter a'=-3 (mod p) and translating (mod p) on a corresponding isogenous Weierstrass curve with domain
the result back to the original curve. parameter a'=-3 (mod p) and translating the result back to the
original curve.
In this case, the mapping from W_{a,b} to W_{a',b'} is defined by 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),
u(x), v(x), and w(x) are polynomials that depend on the isogeny in v(X), and w(X) are polynomials in X 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
y'*v'(x')/w'(x')^3) of W_{a,b}, where -- again -- u'(x'), v'(x'), and (X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of W_{a,b}, where --
w'(x') are polynomials that depend on the isogeny in question. These again -- u'(X'), v'(X'), and w'(X') are polynomials in X' that depend
mappings have the property that their composition is not the identity on the isogeny in question. These mappings have the property that
mapping (as is the case with the isomorphic mappings discussed in their composition is not the identity mapping (as was the case with
Appendix F.1), but rather a fixed multiple hereof: if this multiple the isomorphic mappings discussed in Appendix F.3), but rather a
is l then the isogeny is called an isogeny of degree l (or l-isogeny) fixed multiple hereof: if this multiple is l then the isogeny is
and u, v, and w (and, similarly, u', v', and w') are polynomials of called an isogeny of degree l (or l-isogeny) and u, v, and w (and,
degrees l, 3(l-1)/2, and (l-1)/2, respectively. Note that an similarly, u', v', and w') are polynomials of degrees l, 3*(l-1)/2,
isomorphism is simply an isogeny of degree l=1. Details of how to and (l-1)/2, respectively. Note that an isomorphism is simply an
determine isogenies are outside scope of this document (for this, isogeny of degree l=1. Details of how to determine isogenies are
contact the author of this document). outside scope of this document (for this, 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 isogenous curve with a generic domain parameter a on a corresponding isogenous
Weierstrass curve with domain parameter a'=-3 (mod p), where one can Weierstrass curve with domain parameter a'=-3 (mod p), where one can
use so-called Jacobian coordinates with a particular projective use so-called Jacobian coordinates with a particular projective
version of the addition laws of Appendix C.1. Since all traditional version of the addition laws of Appendix C.1. Since all traditional
NIST curves have domain parameter a=-3, while all Brainpool curves NIST curves have domain parameter a=-3, while all Brainpool curves
[RFC5639] are isomorphic to a Weierstrass curve of this form, this [RFC5639] are isomorphic to a Weierstrass curve of this form, this
allows taking advantage of existing implementations for these curves allows taking advantage of existing implementations for these curves
that may have a hardcoded a=-3 (mod p) domain parameter, provided one that may have a hardcoded a=-3 (mod p) domain parameter, provided one
switches back and forth to this curve form using the isogenous switches back and forth to this curve form using the isogenous
mapping in question. mapping in question.
Note that isogenous mappings can be easily realized in projective Note that isogenous mappings can be easily realized using
coordinates and involves roughly 3*l finite field multiplications, representations in projective coordinates and involves roughly 3*l
thus allowing switching between alternative representations at finite field multiplications, thus allowing switching between
relative low incremental cost compared to that of elliptic curve alternative representations at relatively low incremental cost
scalar multiplications (provided the isogeny has low degree l). compared to that of elliptic curve scalar multiplications (provided
Note, however, that this does require storage of the polynomial the isogeny has low degree l). Note, however, that this does require
coefficients of the isogeny and dual isogeny involved. This storage of the polynomial coefficients of the isogeny and dual
illustrates that low-degree isogenies are to be preferred, since an isogeny involved. This illustrates that low-degree isogenies are to
l-isogeny (usually) requires storing roughly 6*l elements of GF(q). be preferred, since an l-isogeny (usually) requires storing roughly
While there are many isogenies, we therefore only consider those with 6*l elements of GF(q). While there are many isogenies, we therefore
the desired property with lowest possible degree. only consider those with the desired property with lowest possible
degree.
Appendix G. Further Cousins of Curve25519 Appendix G. Further Cousins of Curve25519
G.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 Wei25519.2 defined over GF(p), with as base point the pair (G2X,G2Y),
(G1x',G1y'), and isogenous to the Weierstrass curve Wei25519.-3 and isogenous to the Weierstrass curve Wei25519.-3 defined over
defined over GF(p), with as base point the pair (G2x', G2y'), where GF(p), with as base point the pair (G3X, G3Y), where parameters are
parameters are as specified in Appendix G.3 and where the related as specified in Appendix G.3 and where the related mappings are as
mappings are as specified in Appendix G.2. specified in Appendix G.2.
G.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',
(x',y'):=(x*s^2,y*s^3) of Wei25519.2, where s is the element of GF(p) 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 F.1.) infinity of Wei25519.2. (Here, we used the mapping of Appendix F.3.)
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 (G2X,G2Y) of Wei25519.2. The inverse mapping maps
maps the affine point (x',y') of Wei25519.2 to (x,y):=(x'/s^2,y'/s^3) the affine point (X', Y') of Wei25519.2 to (X,Y):=(X'/s^2,Y'/s^3) of
of Wei25519, while mapping the point at infinity of Wei25519.2 to the Wei25519, while mapping the point at infinity O of Wei25519.2 to the
point at infinity of Wei25519. Note that this mapping (and its point at infinity O 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 H.1 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 35728133398289175649586938605660542688691615699169662967154525084
435568115620 644181596229
(=0x3982c126 59ad1749 ab8bc495 bb1a9d64 c9deffc5 e7b8e601 (=0x4efd6829 88ff8526 e189f712 5999550c e9ef729b ed1a7015
a5651992 07d48fa4), 73b1bab8 8bfcd845),
while the point at infinity of Wei25519 corresponds to the point at while the point at infinity of Wei25519 corresponds to the point at
infinity of Wei25519.-3. (Here, we used the isogenous mapping of infinity of Wei25519.-3. (Here, we used the isogenous mapping of
Appendix F.2.) Under this isogenous mapping, the base point Appendix F.4.) Under this isogenous mapping, the base point (GX,GY)
(Gx',Gy') of Wei25519 corresponds to the base point (G2x',G2y') of of Wei25519 corresponds to the base point (G3X,G3Y) of Wei25519.-3.
Wei25519.-3. The dual isogeny maps the affine point (x',y') of The dual isogeny maps the affine point (X',Y') of Wei25519.-3 to the
Wei25519.-3 to to (x,y):=(u'(x1)/w'(x1)^2,y1*v'(x1)/w'(x1)^3) of affine point (X,Y):=(u'(X1)/w'(X1)^2,Y1*v'(x1)/w'(X1)^3) of Wei25519,
Wei25519, where (x1,y1)=(x'*t^2,y'*t^3) and where u', v', and w' are where (X1,Y1)=(X'/t^2,Y'/t^3) and where u', v', and w' are the
the polynomials with coefficients in GF(p) as defined in polynomials with coefficients in GF(p) as defined in Appendix H.2,
Appendix H.2, while mapping the point at infinity of Wei25519.-3 to while mapping the point at infinity O of Wei25519.-3 to the point at
the point at infinity of Wei25519. Under this dual isogenous infinity O of Wei25519. Under this dual isogenous mapping, the base
mapping, the base point (G2x',G2y') of Wei25519.-3 corresponds to a point (G3X, G3Y) of Wei25519.-3 corresponds to a multiple of the base
multiple of the base point (Gx',Gy') of Wei25519, where this multiple point (GX, GY) of Wei25519, where this multiple is l=47 (the degree
is l=47 (the degree of the isogeny; see the description in of the isogeny; see the description in Appendix F.3). Note that this
Appendix F.1). Note that this isogenous map (and its dual) primarily isogenous map (and its dual) primarily involves the evaluation of
involves the evaluation of three fixed polynomials involving the three fixed polynomials involving the x-coordinate, which takes
x-coordinate, which takes roughly 140 modular multiplications (or roughly 140 modular multiplications (or less than 5-10% relative
less than 5-10% relative incremental cost compared to the cost of an incremental cost compared to the cost of an elliptic curve scalar
elliptic curve scalar multiplication). multiplication).
G.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 isogenous 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) General parameters: same as for Wei25519 (see Appendix E.3)
skipping to change at page 23, line 35 skipping to change at page 28, line 15
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)
G1x' 107705531383684005184170201967961611367923681983263378231495026 G2X 10770553138368400518417020196796161136792368198326337823149502681
81097436401658 097436401658
(=0x17cfeac3 78aed661 318e8634 582275b6 d9ad4def 072ea193 (=0x17cfeac3 78aed661 318e8634 582275b6 d9ad4def 072ea193
5ee3c4e8 7a940ffa) 5ee3c4e8 7a940ffa)
G1y' 544305758615084056530986689844575286168071033325025775211614397 G2Y 54430575861508405653098668984457528616807103332502577521161439773
7388639873869 88639873869
(=0x0c08a952 c55dfad6 2c4f13f1 a8f68dca dc5c331d 297a37b6 (=0x0c08a952 c55dfad6 2c4f13f1 a8f68dca dc5c331d 297a37b6
f0d7fdcc 51e16b4d) f0d7fdcc 51e16b4d)
Weierstrass curve-specific parameters (for Wei25519.-3, i.e., with Weierstrass curve-specific parameters (for Wei25519.-3, i.e., with
a=-3): a=-3):
a -3 a -3
(=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff (=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff
ffffffff ffffffea) ffffffff ffffffea)
b 29689592517550930188872794512874050362622433571298029721775200646 b 29689592517550930188872794512874050362622433571298029721775200646
451501277098 451501277098
(=0x41a3b6bf c668778e be2954a4 b1df36d1 485ecef1 ea614295 (=0x41a3b6bf c668778e be2954a4 b1df36d1 485ecef1 ea614295
796e1022 40891faa) 796e1022 40891faa)
G2x' 538371792299408724349427232574807773704511272123391981336972078 G3X 53837179229940872434942723257480777370451127212339198133697207846
46219400243292 219400243292
(=0x7706c37b 5a84128a 3884a5d7 1811f1b5 5da3230f fb17a8ab (=0x7706c37b 5a84128a 3884a5d7 1811f1b5 5da3230f fb17a8ab
0b32e48d 31a6685c) 0b32e48d 31a6685c)
G2y' 695480730911001844144020555292799703925148674228551417730708041 G3Y 69548073091100184414402055529279970392514867422855141773070804184
8460388229929 60388229929
(=0x0f60480c 7a5c0e11 40340adc 79d6a2bf 0cb57ad0 49d025dc (=0x0f60480c 7a5c0e11 40340adc 79d6a2bf 0cb57ad0 49d025dc
38d80c77 985f0329) 38d80c77 985f0329)
Appendix H. 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
skipping to change at page 36, line 44 skipping to change at page 41, line 22
19 0x6868305b4f40654460aad63af3cb9151ab67c775eaac5e5df90d3aea58dee141 19 0x6868305b4f40654460aad63af3cb9151ab67c775eaac5e5df90d3aea58dee141
20 0x16bc90219a36063a22889db810730a8b719c267d538cd28fa7c0d04f124c8580 20 0x16bc90219a36063a22889db810730a8b719c267d538cd28fa7c0d04f124c8580
21 0x3628f9cf1fbe3eb559854e3b1c06a4cd6a26906b4e2d2e70616a493bba2dc574 21 0x3628f9cf1fbe3eb559854e3b1c06a4cd6a26906b4e2d2e70616a493bba2dc574
22 0x64abcc6759f1ce1ab57d41e17c2633f717064e35a7233a6682f8cf8e9538afec 22 0x64abcc6759f1ce1ab57d41e17c2633f717064e35a7233a6682f8cf8e9538afec
23 0x1 23 0x1
Appendix I. Point Compression
Point compression allows a shorter representation of affine points of
an elliptic curve by exploiting algebraic relationships between the
coordinate values based on the defining equation of the curve in
question. Point decompression refers to the reverse process, where
one tries and recover the affine point from its compressed
representation and information on the domain parameters of the curve.
Consequently, point compression followed by point decompression is
the identity map.
The description below makes use of an auxiliary function (the parity
function), which we first define for prime fields GF(p) and then
extend to all fields GF(q), where q is an odd prime power. We assume
each finite field to be unambiguously defined.
Let y be a nonzero element of GF(q). If q:=p is an odd prime number,
y and p-y can be uniquely represented as integers in the interval
[1,p-1] and have odd sum p. Consequently, one can distinguish y from
-y via the parity of this representation, i.e., via par(y):=y (mod
2). If q:=p^m, where p is an odd prime number and where m>0, both y
and -y can be uniquely represented as vectors of length m, with
coefficients in GF(p) (see Appendix B.2). In this case, the leftmost
nonzero coordinate values of y and -y are in the same position and
have representations in [1,p-1] with different parity. As a result,
one can distinguish y from -y via the parity of the representation of
this coordinate value. This extends the definition of the parity
function to any odd-size field GF(q), where one defines par(0):=0.
I.1. Point Compression for Weierstrass Curves
If P:=(X, Y) is an affine point of the Weierstrass curve W_{a,b}
defined over the field GF(q), then so is -P:=(X, -Y). Since the
defining equation Y^2=X^2+a*X+b has at most two solutions with fixed
X-value, one can represent P by its X-coordinate and one bit of
information that allows one to distinguish P from -P, i.e., one can
represent P as the ordered pair compr(P):=(X, par(Y)). If P is a
point of order two, one can uniquely represent P by its X-coordinate
alone, since Y=0 and has fixed parity. Conversely, given the ordered
pair (X, t), where X is an element of GF(q) and where t=0 or t=1, and
the domain parameters of the curve, one can use the defining equation
of the curve to try and determine candidate values for the
Y-coordinate given X, by solving the quadratic equation Y^2:=alpha,
where alpha:=X^3+a*X+b. If alpha is not a square in GF(q), this
equation does not have a solution in GF(q) and the ordered pair (X,
t) does not correspond to a point of this curve. Otherwise, there
are two solutions, viz. Y=sqrt(alpha) and -Y. If alpha is a nonzero
element of GF(q), one can uniquely recover the Y-coordinate for which
par(Y):=t and, thereby, the point P:=(X, Y). This is also the case
if alpha=0 and t=0, in which case Y=0 and the point P has order two.
However, if alpha=0 and t=1, the ordered pair (X, t) does not
correspond to the outcome of the point compression function.
I.2. Point Compression for Montgomery Curves
If P:=(u, v) is an affine point of the Montgomery curve M_{A,B}
defined over the field GF(q), then so is -P:=(u, -v). Since the
defining equation B*v^2=u^3+A*u^2+u has at most two solutions with
fixed u-value, one can represent P by its u-coordinate and one bit of
information that allows one to distinguish P from -P, i.e., one can
represent P as the ordered pair compr(P):=(u, par(v)). If P is a
point of order two, one can uniquely represent P by its u-coordinate
alone, since v=0 and has fixed parity. Conversely, given the ordered
pair (u, t), where u is an element of GF(q) and where t=0 or t=1, and
the domain parameters of the curve, one can use the defining equation
of the curve to try and determine candidate values for the
v-coordinate given u, by solving the quadratic equation v^2:=alpha,
where alpha:=(u^3+A*u^2+u)/B. If alpha is not a square in GF(q),
this equation does not have a solution in GF(q) and the ordered pair
(u, t) does not correspond to a point of this curve. Otherwise,
there are two solutions, viz. v=sqrt(alpha) and -v. If alpha is a
nonzero element of GF(q), one can uniquely recover the v-coordinate
for which par(v):=t and, thereby, the affine point P:=(u, v). This
is also the case if alpha=0 and t=0, in which case v=0 and the point
P has order two. However, if alpha=0 and t=1, the ordered pair (u,
t) does not correspond to the outcome of the point compression
function.
I.3. Point Compression for Twisted Edwards Curves
If P:=(x, y) is an affine point of the twisted Edwards curve E_{a,d}
defined over the field GF(q), then so is -P:=(-x, y). Since the
defining equation a*x^2+y^2=1+d*x^2*y^2 has at most two solutions
with fixed y-value, one can represent P by its y-coordinate and one
bit of information that allows one to distinguish P from -P, i.e.,
one can represent P as the ordered pair compr(P):=(par(x), y). If P
is a point of order one or two, one can uniquely represent P by its
y-coordinate alone, since x=0 and has fixed parity. Conversely,
given the ordered pair (t, y), where y is an element of GF(q) and
where t=0 or t=1, and the domain parameters of the curve, one can use
the defining equation of the curve to try and determine candidate
values for the x-coordinate given y, by solving the quadratic
equation x^2:=alpha, where alpha:=(1-y^2)/(a-d*y^2). If alpha is not
a square in GF(q), this equation does not have a solution in GF(q)
and the ordered pair (t, y) does not correspond to a point of this
curve. Otherwise, there are two solutions, viz. x=sqrt(alpha) and
-x. If alpha is a nonzero element of GF(q), one can uniquely recover
the x-coordinate for which par(x):=t and, thereby, the affine point
P:=(x, y). This is also the case if alpha=0 and t=0, in which case
x=0 and the point P has order one or two. However, if alpha=0 and
t=1, the ordered pair (t, y) does not correspond to the outcome of
the point compression function.
Appendix J. Data Conversions
The string over some alphabet S consisting of the symbols x_{l-1},
x_{l-2}, ..., x_1, x_0 (each in S), in this order, is denoted by
str(x_{l-1}, x_{l-2}, ..., x_1, x_0). The length of this string
(over S) is the number of symbols it contains (here: l). The empty
string is the (unique) string of length l=0.
An octet is an integer in the interval [0,256). An octet string is a
string, where the alphabet is the set of all octets. A binary string
(or bit string, for short) is a string, where the alphabet is the set
{0,1}. Note that the length of a string is defined in terms of the
underlying alphabet.
J.1. Conversion between Bit Strings and Integers
There is a 1-1 correspondence between bit strings of length l and the
integers in the interval [0, 2^l), where the bit string
X:=str(x_{l-1}, x_{l-2}, ..., x_1, x_0) corresponds to the integer
x:=x_{l-1}*2^{l-1} + x_{l-2}*2^{l-2} + ... + x_1*2 + x_0*1. (If l=0,
the empty bit string corresponds to the integer zero.) Note that
while the mapping from bit strings to integers is uniquely defined,
the inverse mapping from integers to bit strings is not, since any
non-negative integer smaller than 2^t can be represented as a bit
string of length at least t (due to leading zero coefficients in base
2 representation). The latter representation is called tight if the
bit string representation has minimal length.
J.2. Conversion between Octet Strings and Integers (OS2I, I2OS)
There is a 1-1 correspondence between octet strings of length l and
the integers in the interval [0, 256^l), where the octet string
X:=str(X_{l-1}, X_{l-2}, ..., X_1, X_0) corresponds to the integer
x:=X_{l-1}*256^{l-1} + X^{l-2}*256^{l-2} + ... + X_1*256 + X_0*1.
(If l=0, the empty string corresponds to the integer zero.) Note
that while the mapping from octet strings to integers is uniquely
defined, the inverse mapping from integers to octet strings is not,
since any non-negative integer smaller than 256^t can be represented
as an octet string of length at least t (due to leading zero
coefficients in base 256 representation). The latter representation
is called tight if the octet string representation has minimal
length. This defines the mapping OS2I from octet strings to integers
and the mapping I2OS(x,l) from non-negative integers smaller than
256^l to octet strings of length l.
J.3. Conversion between Octet Strings and Bit Strings (BS2OS, OS2BS)
There is a 1-1 correspondence between octet strings of length l and
and bit strings of length 8*l, where the octet string X:=str(X_{l-1},
X_{l-2}, ..., X_1, X_0) corresponds to the right-concatenation of the
8-bit strings x_{l-1}, x_{l-2}, ..., x_1, x_0, where each octet X_i
corresponds to the 8-bit string x_i according to the mapping of
Appendix J.1 above. Note that the mapping from octet strings to bit
strings is uniquely defined and so is the inverse mapping from bit
strings to octet strings, if one prepends each bit string with the
smallest number of 0 bits so as to result in a bit string of length
divisible by eight (i.e., one uses pre-padding). This defines the
mapping OS2BS from octet strings to bit strings and the corresponding
mapping BS2OS from bit strings to octet strings.
J.4. Conversion between Field Elements and Octet Strings (FE2OS, OS2FE)
There is a 1-1 correspondence between elements of a fixed finite
field GF(q), where q=p^m and m>0, and vectors of length m, with
coefficients in GF(p), where each element x of GF(q) is a vector
(x_{m-1}, x_{m-2}, ..., x_1, x_0) according to the conventions of
Appendix B.2. In this case, this field element can be uniquely
represented by the right-concatenation of the octet strings X_{m-1},
X_{m-2}, ..., X_1, X_0, where each octet string X_i corresponds to
the integer x_i in the interval [0,p-1] according to the mapping of
Appendix J.2 above. Note that both the mapping from field elements
to octet strings and the inverse mapping are only uniquely defined if
each octet string X_i has the same fixed size (e.g., the smallest
integer l so that 256^l >= p) and if all integers are reduced modulo
p. If so, the latter representation is called tight if l is minimal
so that 256^l >= p. This defines the mapping FE2OS(x,l) from field
elements to octet strings and the mapping OS2FE(X,l) from octet
strings to field elements, where the underlying field is implicit and
assumed to be known from context. In this case, the octet string has
length l*m.
J.5. Ordering Conventions
One can consider various representation functions, depending on bit-
ordering and octet-ordering conventions.
The description below makes use of an auxiliary function (the
reversion function), which we define both for bit strings and octet
strings. For a bit string [octet string] X:=str(x_{l-1}, x_{l-2},
..., x_1, x_0), its reverse is the bit string [octet string]
X':=rev(X):=str(x_0, x_1, ..., x_{l-2}, x_{l-1}).
We now describe representations in most-significant-bit first (msb)
or least-significant-bit first (lsb) order and those in most-
significant-byte first (MSB) or least-significant-byte first (LSB)
order.
One distinguishes the following octet-string representations of
integers and field elements:
1. MSB, msb: represent field elements and integers as above,
yielding the octet string str(X_{l-1}, X_{l-2}, ..., X_1, X_0).
2. MSB, lsb: reverse the bit-order of each octet, viewed as 8-bit
string, yielding the octet string str((rev(X_{l-1}),
rev(X_{l-2}), ..., rev(X_1), rev(X_0)).
3. LSB, lsb: reverse the octet string and bit-order of each octet,
yielding the octet string str(rev(X_{0}), rev(X_{1}), ...,
rev(X_{l-2}), rev(X_{l-1})).
4. LSB, msb: reverse the octet string, yielding the octet string
str(X_{0}, X_{1}, ..., X_{l-2}, X_{l-1}).
Thus, the 2-octet string "07e3" represents the integer 2019 (=0x07e3)
in MSB/msb order, the integer 57,543 (0xe0c7) in MSB/lsb order, the
integer 51,168 (0xc7e0) in LSB/lsb order, and the integer 58,119
(=0xe307) in LSB/msb order.
Note that, with the above data conversions, there is still some
ambiguity as to how to represent an integer or a field element as a
bit string or octet string (due to leading zeros). However, tight
representations (as defined above) are non-ambiguous.
Appendix K. Representations for Curve25519 Family Members
K.1. Wei25519
The representation of integers, field elements, affine points, and
compressed points for the curve Wei25519 are as indicated below.
Representations are relative to the prime field GF(p), where
p=2^255-19 is one of the general domain parameters of Appendix E.3.
Each field element z of GF(p) is represented as the octet string
FE2OS(z), where one uses one the MSB/msb conventions and tight
representation, as specified in Appendix J. In particular, each
element of GF(p) is represented as a 32-byte octet string, which -
when viewed as a bit string - has the leftmost bit position set to 0.
Each affine point (X, Y) of Wei25519 is represented as the
rightconcatenation of the 32-byte octet representations for the x-
and y-coordinate of this point according to the conventions above,
i.e., it is represented as the 64-byte octet string str(FE2OS(X),
FE2OS(Y)).
For each compressed point (X, t) of Wei25519, the parity bit t (which
is an element of the field GF(2)), is represented as a 1-bit bit
string, whereas the x-coordinate X (which is an element of GF(p)), is
represented as a 32-byte octet string FE2OS(X). The result is
"squeezed", by superimposing the 1-bit representation of t on the
leftmost (unused) bit-position of the 32-byte octet representation of
X.
Each integer in the interval [0,n-1] is viewed as an element of the
prime field GF(n) and represented using MSB/msb conventions and a
tight representation. In particular, each element of GF(n) is
represented as a 32-byte octet string, which - when viewed as a bit
string - has the lefmost three bit positions set to 0.
Appendix L. Auxiliary Functions
L.1. Square Roots in GF(q)
Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see
Appendix L.1.1) or if q = 5 (mod 8) (see Appendix L.1.2). Details on
how to compute square roots for other values of q are out of scope.
If square roots are easy to compute in GF(q), then so are these in
GF(q^2).
L.1.1. Square Roots in GF(q), where q = 3 (mod 4)
If y is a nonzero element of GF(q) and z:= y^{(q-3)/4}, then y is a
square in GF(q) only if y*z^2=1. If y*z^2=1, z is a square root of
1/y and y*z is a square root of y in GF(q).
L.1.2. Square Roots in GF(q), where q = 5 (mod 8)
If y is a nonzero element of GF(q) and z:=y^{z-5)/8}, then y is a
square in GF(q) only if y^2*z^4=1.
a. If y*z^2=+1, z is a square root of 1/y and y*z is a square root
of y in GF(q);
b. If y*z^2=-1, i*z is a square root of 1/y and i*y*z is a square
root of y.
Here, i is an element of GF(q) for which i^2=-1 (e.g.,
i:=2^{(q-1)/4}). This field element can be precomputed.
L.2. Inversion
If y is an integer and gcd(y,n)=1, one can efficiently compute 1/y
(mod n) via the extended Euclidean Algorithm (see Section 2.2.5 of
[GECC]). One can use this algorithm as well to compute the inverse
of a nonzero element y of a prime field GF(p), since gcd(y,p)=1.
The inverse of a nonzero element y of GF(q) can be computed as
1/y:=y^{q-2} (since y^{q-1}=1).
Further details are out of scope. If inverses are easy to compute in
GF(q), then so are these in GF(q^2).
The inverses of two nonzero elements y1 and y2 of GF(q) can be
computed by first computing the inverse z of y1*y2 and by
subsequently computing y2*z=:1/y1 and y1*z=:1/y2.
Author's Address Author's Address
Rene Struik Rene Struik
Struik Security Consultancy Struik Security Consultancy
Email: rstruik.ext@gmail.com Email: rstruik.ext@gmail.com
 End of changes. 107 change blocks. 
347 lines changed or deleted 887 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/