| lwig | R. Struik |
| Internet-Draft | Struik Security Consultancy |
| Intended status: Informational | March 9, 2020 |
| Expires: September 10, 2020 |
Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-09
This document specifies how to represent Montgomery curves and (twisted) Edwards curves as curves in short-Weierstrass form and illustrates how this can be used to carry out elliptic curve computations using existing implementations of, e.g., ECDSA and ECDH using NIST prime curves. We also provide extensive background material that may be useful for implementers of elliptic curve cryptography.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."
This Internet-Draft will expire on September 10, 2020.
Copyright (c) 2020 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
Elliptic curves can be represented using different curve models. Recently, IETF standardized elliptic curves that are claimed to have better performance and improved robustness against "real world" attacks than curves represented in the traditional "short" Weierstrass model. This document specifies an alternative representation of points of Curve25519, a so-called Montgomery curve, and of points of Edwards25519, a so-called twisted Edwards curve, which are both specified in [RFC7748], as points of a specific so-called "short" Weierstrass curve, called Wei25519. We also define how to efficiently switch between these different representations.
Use of Wei25519 allows easy definition of new instantiations of signature schemes and key agreement schemes already specified for traditional NIST prime curves, thereby allowing easy integration with existing specifications, such as NIST SP 800-56a, FIPS Pub 186-4, and ANSI X9.62-2005, and fostering code reuse on platforms that already implement some of these schemes using elliptic curve arithmetic for curves in "short" Weierstrass form (see Appendix C.1).
For the specification of Wei25519 and its relationship to Curve25519 and Edwards25519, see Appendix E. For further details and background information on elliptic curves, we refer to the other appendices.
The use of Wei25519 allows reuse of existing generic code that implements short-Weierstrass curves, such as the NIST curve P-256, to also implement the CFRG curves Curve25519 and Edwards25519. (Here, generic code refers to an implementation that does not depend on hardcoded domain parameters (see also Section 6).) We also cater to reusing of existing code where some domain parameters may have been hardcoded, thereby widening the scope of applicability. To this end, we specify the short-Weierstrass curves Wei25519.2 and Wei25519.-3, with hardcoded domain parameter a=2 and a=-3 (mod p), respectively; see Appendix G. (Here, p is the characteristic of the field over which these curves are defined.)
The curves Curve25519, Edwards25519, and Wei25519, as specified in Appendix E.3, are all isomorphic, with the transformations of Appendix E.2. These transformations map the specified base point of each of these curves to the specified base point of each of the other curves. Consequently, a public-private key pair (k,R:=k*G) for any one of these curves corresponds, via these isomorphic mappings, to the public-private key pair (k, R':=k*G') for each of these other curves (where G and G' are the corresponding base points of these curves). This observation extends to the case where one also considers curve Wei25519.2 (which has hardcoded domain parameter a=2), as specified in Appendix G.3, since it is isomorphic to Wei25519, with the transformation of Appendix G.2, and, thereby, also isomorphic to Curve25519 and Edwards25519.
The curve Wei25519.-3 (which has hardcoded domain parameter a=-3 (mod p)) is not isomorphic to the curve Wei25519, but is related in a slightly weaker sense: the curve Wei25519 is isogenous to the curve Wei25519.-3, where the mapping of Appendix G.2 is an isogeny of degree l=47 that maps the specified base point G of Wei25519 to the specified base point G' of Wei25519.-3 and where the so-called dual isogeny (which maps Wei25519.-3 to Wei25519) has the same degree l=47, but does not map G' to G, but to a fixed multiple hereof, where this multiple is l=47. Consequently, a public-private key pair (k,R:=k*G) for Wei25519 corresponds to the public-private key pair (k, R':= k*G') for Wei25519.-3 (via the l-isogeny), whereas the public-private key pair (k, R':=k*G') corresponds to the public-private key pair (l*k, l*R=l*k*G) of Wei25519 (via the dual isogeny). (Note the extra scalar l=47 here.)
Alternative curve representations can, therefore, be used in any cryptographic scheme that involves computations on public-private key pairs, where implementations may carry out computations on the corresponding object for the isomorphic or isogenous curve and convert the results back to the original curve (where, in case this involves an l-isogeny, one has to take into account the factor l). This includes use with elliptic-curve based signature schemes and key agreement and key transport schemes.
For some examples of curve computations on each of the curves specified in Appendix E.3 and Appendix G.3, see Appendix J.
RFC 7748 [RFC7748] specifies the use of X25519, a co-factor Diffie-Hellman key agreement scheme, with instantiation by the Montgomery curve Curve25519. This key agreement scheme was already specified in Section 6.1.2.2 of NIST SP 800-56a for elliptic curves in short Weierstrass form. Hence, one can implement X25519 using existing NIST routines by (1) representing a point of the Montgomery curve Curve25519 as a point of the Weierstrass curve Wei25519; (2) instantiating the co-factor Diffie-Hellman key agreement scheme of the NIST specification with the resulting point and Wei25519 domain parameters; (3) representing the key resulting from this scheme (which is a point of the curve Wei25519 in Weierstrass form) as a point of the Montgomery curve Curve25519. The representation change can be implemented via a simple wrapper and involves a single modular addition (see Appendix E.2). Using this method has the additional advantage that one can reuse the public-private key pair routines, domain parameter validation, and other checks that are already part of the NIST specifications. A NIST-compliant version of co-factor Diffie-Hellman key agreement (denoted by ECDH25519) results if one keeps inputs (key contributions) and outputs (shared key) in the short-Weierstrass format (and, hence, does not perform Step (3) above).
NOTE: At this point, it is unclear whether this implies that a FIPS-accredited module implementing co-factor Diffie-Hellman for, e.g., P-256 would also extend this accreditation to X25519.
RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature scheme, with instantiation by the twisted Edwards curve Edwards25519. One can implement the computation of the ephemeral key pair for Ed25519 using an existing Montgomery curve implementation by (1) generating a public-private key pair (k, R':=k*G') for Curve25519; (2) representing this public-private key as the pair (k, R:=k*G) for Ed25519. As before, the representation change can be implemented via a simple wrapper. Note that the Montgomery ladder specified in Section 5 of RFC7748 [RFC7748] does not provide sufficient information to reconstruct R':=(u, v) (since it does not compute the v-coordinate of R'). However, this deficiency can be remedied by using a slightly modified version of the Montgomery ladder that includes reconstruction of the v-coordinate of R':=k*G' at the end of the Montgomery ladder (which uses the v-coordinate of the base point of Curve25519 as well). For details, see Appendix C.1.
FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and can be instantiated not just with the NIST prime curves, but also with other Weierstrass curves (that satisfy additional cryptographic criteria). In particular, one can instantiate this scheme with the Weierstrass curve Wei25519 and the hash function SHA-256 [FIPS-180-4], where an implementation may generate an ephemeral public-private key pair for Wei25519 by (1) internally carrying out these computations on the Montgomery curve Curve25519, the twisted Edwards curve Edwards25519, or even the Weierstrass curve Wei25519.-3 (with hardcoded a=-3 domain parameter); (2) representing the result as a key pair for the curve Wei25519. Note that, in either case, one can implement these schemes with the same representation conventions as used with existing NIST specifications, including bit/byte-ordering, compression functions, and the-like. This allows generic implementations of ECDSA with the hash function SHA-256 and with the NIST curve P-256 or with the curve Wei25519 specified in this specification to reuse the same implementation (instantiated with, respectively, the NIST P-256 elliptic curve domain parameters or with the domain parameters of curve Wei25519 specified in Appendix E). We denote by ECDSA25519 the instantiation of ECDSA with SHA-256 and with curve Wei25519, where the signature (r,s) is represented as the right-concatenation of the integers r and s, each represented as fixed-size strings with tight MSB/msb ordering (see Appendix I).
Any existing specification of cryptographic schemes using elliptic curves in Weierstrass form and that allows introduction of a new elliptic curve (here: Wei25519) is amenable to similar constructs, thus spawning "offspring" protocols, simply by instantiating these using the new curve in "short" Weierstrass form, thereby allowing code and/or specifications reuse and, for implementations that so desire, carrying out curve computations "under the hood" on Montgomery curve and twisted Edwards curve cousins hereof (where these exist). This would simply require definition of a new object identifier for any such envisioned "offspring" protocol. This could significantly simplify standardization of schemes and help keeping the resource and maintenance cost of implementations supporting algorithm agility [RFC7696] at bay.
We illustrate the construction of such offspring protocols for Curve448, another Montgomery curve recently standardized by IETF (see [RFC7748]). Similar to the case with Curve25519, one can represent points of this curve via different curve models, viz. as points of an Edwards curve (Ed448) or as points of a short-Weierstrass curve (Wei448). For the specification of Wei448 and its relationship to Curve448 and Ed448, see Appendix M. As with ECDH25519, one can now easily define a NIST-compliant version of co-factor Diffie-Hellman key agreement (denoted by ECDH448), by simply reusing the example of Section 4.1, but now using the short-Weierstrass curve Wei448, rather than Wei25519. Similarly, one can easily specify ECDSA with Wei448 and a suitable hash function, by simply reusing the example of Section 4.3, but now using the short-Weierstrass curve Wei448, rather than Wei25519, and picking as hash function SHAKE256 [FIPS-202] with output size of d=446 bits. We denote by ECDSA448 the resulting signature scheme (with the same bit/byte-ordering conventions).
The examples above illustrate how specifying the Weierstrass curve Wei25519 (or any curve in short-Weierstrass format, for that matter) may facilitate reuse of existing code and may simplify standards development. However, the following caveats apply:
The transformations between alternative curve representations can be implemented at negligible relative incremental cost if the curve points are represented as affine points. If a point is represented in compressed format, conversion usually requires a costly point decompression step. This is the case in [RFC7748], where the inputs to the co-factor Diffie-Hellman scheme X25519, as well as its output, are represented in 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 H for details). Note that in the latter case compression is lossless, whereas it is lossy in the former case;
While elliptic curve computations are carried-out in a field GF(q) and, thereby, involve large integer arithmetic, these integers are represented as bit- and byte-strings. Here, [RFC8032] uses least-significant-byte (LSB)/least-significant-bit (lsb) conventions, whereas [RFC7748] uses LSB/most-significant-bit (msb) conventions, and where most other cryptographic specifications, including NIST SP800-56a [SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005 [ANSI-X9.62] use MSB/msb conventions. Since each pair of conventions is different (see Appendix I for details and Appendix J for examples), this does necessitate bit/byte representation conversions;
All traditional NIST curves are Weierstrass curves with domain parameter a=-3, while all Brainpool curves [RFC5639] are isomorphic to a Weierstrass curve of this form. Thus, one can expect there to be existing Weierstrass implementations with a hardcoded a=-3 domain parameter ("Jacobian-friendly"). For those implementations, including the curve Wei25519 as a potential vehicle for offering support for the CFRG curves Curve25519 and Edwards25519 is not possible, since not of the required form. Instead, one has to implement Wei25519.-3 and include code that implements the isogeny and dual isogeny from and to Wei25519. The lowest odd-degree isogeny has degree l=47 and requires roughly 9kB of storage for isogeny and dual-isogeny computations (see the tables in Appendix G.4). Note that storage would have reduced to a single 64-byte table if only the curve would have been generated so as to be isomorphic to a Weierstrass curve with hardcoded a=-3 parameter (this corresponds to l=1).
NOTE 1: An example of a Montgomery curve defined over the same field as Curve25519 that is isomorphic to a Weierstrass curve with hardcoded a=-3 parameter is the Montgomery curve M_{A,B} with B=1 and A=-1410290 (or, if one wants the base point to still have u-coordinate u=9, with B=1 and A=-3960846). In either case, the resulting curve has the same cryptographic properties as Curve25519 and the same performance (which relies on A being a 3-byte integer, as is the case with the domain parameter A=486662 of Curve25519, and using the same special prime p=2^255-19), while at the same time being "Jacobian-friendly" by design.
NOTE 2: While an implementation of Curve25519 via an isogenous Weierstrass curve with domain parameter a=-3 requires a relatively large table (of size roughly 9kB), for the quadratic twist of Curve25519 (i.e., the Montgomery curve M_{A,B'} with A=486662 and B'=2) this implementation approach only requires a table of size less than 0.5kB (over 20x smaller), solely due to the fact that it is l-isogenous to a Weierstrass curve with a=-3 parameter with relatively small parameter l=2 (compared to l=47, as is the case with Curve25519 itself).
The efficiency of elliptic curve arithmetic is primarily determined by the efficiency of its group operations (see Appendix C). Numerous optimized formulae exist, such as the use of so-called Montgomery ladders with Montgomery curves [Mont-Ladder] or with Weierstrass curves [Wei-Ladder], the use of hardcoded a=-3 domain parameter for Weierstrass curves [ECC-Isogeny], and the use of hardcoded a=-1 domain parameters for twisted Edwards curves [tEd-Formulas]. These all target reduction of the number of finite field operations (primarily, finite field multiplications and squarings). Other optimizations target more efficient modular reductions underlying these finite field operations, by specifying curves defined over a field GF(q), where the field size q has a special form or a specific bit-size (typically, close to a multiple of a machine word). Depending on the implementation strategy, the bit-size of q may also facilitate reduced so-called "carry-effects" of integer arithmetic.
Most curves use a combination of these design philosophies. All NIST curves [FIPS-186-4] and Brainpool curves [RFC5639] are Weierstrass curves with a=-3 domain parameter, thus facilitating more efficient elliptic curve group operations (via so-called Jacobian coordinates). The NIST curves and the Montgomery curve Curve25519 are defined over prime fields, where the prime number has a special form, whereas the Brainpool curves - by design - use a generic prime number. None of the NIST prime curves, nor the Brainpool curves, can be expressed as Montgomery or twisted Edwards curves, whereas - conversely - Montgomery curves and twisted curves can be expressed as Weierstrass curves.
While use of Wei25519 allows reuse of existing generic code that implements short Weierstrass curves, such as the NIST curve P-256, to also implement the CFRG curves Curve25519 or Edwards25519, this obviously does not result in an implementation of these CFRG curves that exploits the specific structure of the underlying field or other specific domain parameters (since generic). Reuse of generic code, therefore, may result in a less computationally efficient curve implementation than would have been possible if the implementation had specifically targeted Curve25519 or Edwards25519 alone (with the overall cost differential estimated to be somewhere in the interval [1.00-1.25]). If existing generic code offers hardware support, however, the overall speed may still be larger, since less efficient formulae for curve arithmetic using Wei25519 curves compared to a direct implementation of Curve25519 or Edwards25519 arithmetic may be more than compensated for by faster implementations of the finite field arithmetic itself.
Overall, one should consider not just code reuse and computational efficiency, but also development and maintenance cost, and, e.g, the cost of providing effective implementation attack countermeasures (see also Section 8).
[Note to the RFC Editor] Please remove this entire section before publication, as well as the reference to [RFC7942].
This section records the status of known implementations of the protocol defined by this specification at the time of posting of this Internet-Draft, and is based on a proposal described in [RFC7942]. The description of implementations in this section is intended to assist the IETF in its decision processes in progressing drafts to RFCs. Please note that the listing of any individual implementation here does not imply endorsement by the IETF. Furthermore, no effort has been spent to verify the information presented here that was supplied by IETF contributors. This is not intended as, and must not be construed to be, a catalog of available implementations or their features. Readers are advised to note that other implementations may exist.
According to [RFC7942], "this will allow reviewers and working groups to assign due consideration to documents that have the benefit of running code, which may serve as evidence of valuable experimentation and feedback that have made the implemented protocols more mature. It is up to the individual working groups to use this information as they see fit.
Nikolas Rosener evaluated the performance of switching between different curve models in his Master's thesis [Rosener]. For an implementation of Wei25519, see <https://github.com/ncme/c25519>. For support of this curve in tinydtls, see <https://github.com/ncme/tinydtls>.
According to <https://community.nxp.com/docs/DOC-330199>, an implementation of Wei25519 on the Kinets LTC ECC HW platform improves the performance by over a factor ten compared to a stand-alone implementation of Curve25519 without hardware support.
The signature scheme ECDSA25519 (see Section 4.3) is supported in <https://datatracker.ietf.org/doc/draft-ietf-6lo-ap-nd/>.
The different representations of elliptic curve points discussed in this document are all obtained using a publicly known transformation, which is either an isomorphism or a low-degree isogeny. It is well-known that an isomorphism maps elliptic curve points to equivalent mathematical objects and that the complexity of cryptographic problems (such as the discrete logarithm problem) of curves related via a low-degree isogeny are tightly related. Thus, the use of these techniques does not negatively impact cryptographic security of elliptic curve operations.
As to implementation security, reusing existing high-quality code or generic implementations that have been carefully designed to withstand implementation attacks for one curve model may allow a more economical way of development and maintenance than providing this same functionality for each curve model separately (if multiple curve models need to be supported) and, otherwise, may allow a more gradual migration path, where one may initially use existing and accredited chipsets that cater to the pre-dominant curve model used in practice for over 15 years.
Elliptic curves are generally used as objects in a broader cryptographic scheme that may include processing steps that depend on the representation conventions used (such as with, e.g., key derivation following key establishment). These schemes should (obviously) unambiguously specify fixed representations of each input and output (e.g., representing each elliptic curve point always in short-Weierstrass form and in uncompressed tight MSB/msb format).
To prevent cross-protocol attacks, private keys SHOULD only be used with one cryptographic scheme. Private keys MUST NOT be reused between Ed25519 (as specified in [RFC8032]) and ECDSA25519 (as specified in Section 4.3).
To prevent intra-protocol cross-instantiation attacks, ephemeral private keys MUST NOT be reused between instantiations of ECDSA25519.
The transformations between different curve models described in this document are publicly known and, therefore, do not affect privacy provisions.
Use of a public key in any protocol for which successful execution evidences knowledge of the corresponding private key implicitly indicates the entity holding this private key. Reuse of this public key with more than one protocol or more than one protocol instantiation may, therefore, allow traceability of this entity. It may also allow correlation of meta-data communicated with this common data element (e.g., different addressing information), even if an observer cannot technically verify the binding of this meta-data.
The randomized representation described in Appendix K.5 allows random curve points to be represented as random pairs of field elements, thereby assisting in obfuscating the presence of these curve points in some applications.
Code points are requested for curve Wei25519 and Wei448 and its use with ECDSA and co-factor ECDH, using the representation conventions of this document.
New code points would be required in case one wishes to specify one or more other "offspring" protocols beyond those exemplified in Section 4.4. Specification hereof is, however, outside scope of the current document.
This section registers the following value in the IANA "COSE Elliptic Curves" registry [IANA.COSE.Curves].
(Note that The "kty" value for Wei25519 may be "OKP" or "EC2".)
This section registers the following value in the IANA "COSE Algorithms" registry [IANA.COSE.Algorithms].
This section registers the following value in the IANA "COSE Algorithms" registry [IANA.COSE.Algorithms].
This section registers the following value in the IANA "JSON Web Key Elliptic Curve" registry [IANA.JOSE.Curves].
This section registers the following value in the IANA "JSON Web Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
This section registers the following value in the IANA "JSON Web Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
This section registers the following value in the IANA "COSE Elliptic Curves" registry [IANA.COSE.Curves].
(Note that The "kty" value for Wei448 may be "OKP" or "EC2".)
This section registers the following value in the IANA "COSE Algorithms" registry [IANA.COSE.Algorithms].
This section registers the following value in the IANA "COSE Algorithms" registry [IANA.COSE.Algorithms].
This section registers the following value in the IANA "JSON Web Key Elliptic Curve" registry [IANA.JOSE.Curves].
This section registers the following value in the IANA "JSON Web Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
This section registers the following value in the IANA "JSON Web Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Thanks to Nikolas Rosener for discussions surrounding implementation details of the techniques described in this document and to Phillip Hallam-Baker for triggering inclusion of verbiage on the use of Montgomery ladders with recovery of the y-coordinate. Thanks to Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews.
| [ANSI-X9.62] | ANSI X9.62-2005, "Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)", American National Standard for Financial Services, Accredited Standards Committee X9, Inc, Anapolis, MD, 2005. |
| [FIPS-180-4] | FIPS 180-4, "Secure Hash Standard (SHS), Federal Information Processing Standards Publication 180-4", US Department of Commerce/National Institute of Standards and Technology, Gaithersburg, MD, August 2015. |
| [FIPS-186-4] | FIPS 186-4, "Digital Signature Standard (DSS), Federal Information Processing Standards Publication 186-4", US Department of Commerce/National Institute of Standards and Technology, Gaithersburg, MD, July 2013. |
| [FIPS-202] | FIPS 202, "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, Federal Information Processing Standards Publication 202", US Department of Commerce/National Institute of Standards and Technology, Gaithersburg, MD, August 2015. |
| [RFC2119] | Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997. |
| [RFC5639] | Lochter, M. and J. Merkle, "Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation", RFC 5639, DOI 10.17487/RFC5639, March 2010. |
| [RFC7696] | Housley, R., "Guidelines for Cryptographic Algorithm Agility and Selecting Mandatory-to-Implement Algorithms", BCP 201, RFC 7696, DOI 10.17487/RFC7696, November 2015. |
| [RFC7748] | Langley, A., Hamburg, M. and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10.17487/RFC7748, January 2016. |
| [RFC7942] | Sheffer, Y. and A. Farrel, "Improving Awareness of Running Code: The Implementation Status Section", BCP 205, RFC 7942, DOI 10.17487/RFC7942, July 2016. |
| [RFC8032] | Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital Signature Algorithm (EdDSA)", RFC 8032, DOI 10.17487/RFC8032, January 2017. |
| [RFC8152] | Schaad, J., "CBOR Object Signing and Encryption (COSE)", RFC 8152, DOI 10.17487/RFC8152, July 2017. |
| [RFC8174] | Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017. |
| [SEC1] | SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0", Standards for Efficient Cryptography, , June 2009. |
| [SEC2] | SEC2, "SEC 2: Elliptic Curve Cryptography, Version 2.0", Standards for Efficient Cryptography, , January 2010. |
| [SP-800-56a] | NIST SP 800-56a, "Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Log Cryptography, Revision 3", US Department of Commerce/National Institute of Standards and Technology, Gaithersburg, MD, April 2018. |
| [SP-800-56c] | NIST SP 800-56c, "Recommendation for Key-Derivation Methods in Key-Establishment Schemes, Revision 1", US Department of Commerce/National Institute of Standards and Technology, Gaithersburg, MD, April 2018. |
| [ECC] | I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in Cryptography", Cambridge University Press, Lecture Notes Series 265, July 1999. |
| [ECC-Isogeny] | E. Brier, M. Joye, "Fast Point Multiplication on Elliptic Curves through Isogenies", AAECC, Lecture Notes in Computer Science, Vol. 2643, New York: Springer-Verlag, 2003. |
| [GECC] | D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to Elliptic Curve Cryptography", New York: Springer-Verlag, 2004. |
| [IANA.COSE.Algorithms] | IANA, "COSE Algorithms", IANA, https://www.iana.org/assignments/cose/cose.xhtml#algorithms |
| [IANA.COSE.Curves] | IANA, "COSE Elliptic Curves", IANA, https://www.iana.org/assignments/cose/cose.xhtml#elliptic-curves |
| [IANA.JOSE.Algorithms] | IANA, "JSON Web Signature and Encryption Algorithms", IANA, https://www.iana.org/assignments/jose/jose.xhtml#web-signature-encryption-algorithms |
| [IANA.JOSE.Curves] | IANA, "JSON Web Key Elliptic Curve", IANA, https://www.iana.org/assignments/jose/jose.xhtml#web-key-elliptic-curve |
| [Mont-Ladder] | P.L. Montgomery, "Speeding the Pollard and Elliptic Curve Methods of Factorization", Mathematics of Computation, Vol. 48, 1987. |
| [Rosener] | N. Rosener, "Evaluating the Performance of Transformations Between Curve Representations in Elliptic Curve Cryptography for Constrained Device Security", M.Sc. Universitat Bremen, August 2018. |
| [SWUmap] | E. Brier, J-S. Coron, Th. Icart, D. Madore, H. Randriam, M. Tibouchi, "Efficient Indifferentiable Hashing into Ordinary Elliptic Curves", CRYPTO 2010, Lecture Notes in Computer Science, Vol. 6223, New York: Springer-Verlag, 2010. |
| [tEd] | D.J. Bernstein, P. Birkner, M. Joye, T. Lange, C. Peters, "Twisted Edwards Curves", Africacrypt 2008, Lecture Notes in Computer Science, Vol. 5023, New York: Springer-Verlag, 2008. |
| [tEd-Formulas] | 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. |
| [Tibouchi] | M. Tibouchi, "Elligator Squared -- Uniform Points on Elliptic Curves of Prime Order as Uniform Random Strings", Financial Cryptography 2014, Lecture Notes in Computer Science, Vol. 8437, New York: Springer-Verlag, 2014. |
| [Wei-Ladder] | T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve Multiplication Resistant Against Side Channel Attacks", Centre for Applied Cryptographic Research, Corr 2002-03, 2002. |
This section defines the three different curve models we consider, viz. short-Weierstrass curves, Montgomery curves, and twisted Edwards curves.
Let GF(q) denote the finite field with q elements, where q is an odd prime power and where q is not divisible by three. Let W_{a,b} be the Weierstrass curve with defining equation Y^2 = X^3 + a*X + b, where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is nonzero. The points of W_{a,b} are the ordered pairs (X, Y) whose coordinates are elements of GF(q) and that satisfy the defining equation (the so-called affine points), together with the special point O (the so-called "point at infinity"). This set forms a group under addition, via the so-called "chord-and-tangent" rule, where the point at infinity serves as the identity element. See Appendix C.1 for details of the group operation.
Let GF(q) denote the finite field with q elements, where q is an odd prime power. Let M_{A,B} be the Montgomery curve with defining equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q) and where A is unequal to (+/-)2 and where B is nonzero. The points of M_{A,B} are the ordered pairs (u, v) whose coordinates are elements of GF(q) and that satisfy the defining equation (the so-called affine points), together with the special point O (the so-called "point at infinity"). This set forms a group under addition, via the so-called "chord-and-tangent" rule, where the point at infinity serves as the identity element. See Appendix C.2 for details of the group operation.
Let GF(q) denote the finite field with q elements, where q is an odd prime power. Let E_{a,d} be the twisted Edwards curve with defining equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct nonzero elements of GF(q). The points of E_{a,d} are the ordered pairs (x, y) whose coordinates are elements of GF(q) and that satisfy the defining equation (the so-called affine points). It can be shown that this set forms a group under addition if a is a square in GF(q), whereas d is not, where the point O:=(0, 1) serves as the identity element. (Note that the identity element satisfies the defining equation.) See Appendix C.3 for details of the group operation.
An Edwards curve is a twisted Edwards curve with a=1.
This section provides brief background information on elliptic curves and finite fields that should be sufficient to understand constructions and examples in this document.
Each curve defined in Appendix A forms a commutative group under addition (denoted by '+'). In Appendix C we specify the group laws, which depend on the curve model in question. For completeness, we here include some common elliptic curve nomenclature and basic properties (primarily so as to keep this document self-contained). These notions are mainly used in Appendix E and Appendix G and not essential for our exposition. This section can be skipped at first reading.
Any point P of a curve E is a generator of the cyclic subgroup (P):={k*P | k = 0, 1, 2,...} of the curve. (Here, k*P denotes the sum of k copies of P, where 0*P is the identity element O of the curve; k*P is commonly referred to as scalar multiplication of P by k.) If (P) has cardinality l, then l is called the order of P. The order of curve E is the cardinality of the set of its points, commonly denoted by |E|. A curve is cyclic if it is generated by some point of this curve. All curves of prime order are cyclic, while all curves of order h*n, where n is a large prime number and where h is a small number (the so-called co-factor), have a large cyclic subgroup of prime order n. In this case, a generator of order n is called a base point, commonly denoted by G. A point of order dividing h is said to be in the small subgroup. For curves of prime order, this small subgroup is the singleton set, consisting of only the identity element O. A point that is not in the small subgroup is said to be a high-order point (since it has order at least n).
If R is a point of the curve that is also contained in (P), there is a unique integer k in the interval [0, 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 base P. The discrete logarithm problem is the problem of finding the discrete logarithm of R to the base P for any two points P and R of the curve, if such a number exists.
If P is a fixed base point G of the curve, the pair (k, R:=k*G) is commonly called a public-private key pair, the integer k the private key, and the point R the corresponding public key. The private key k can be represented as an integer in the interval [0,n-1], where G has order n. If this representation is nonzero, R has order n; otherwise, it has order one and is the identity element O of the curve.
In this document, a quadratic twist of a curve E defined over a field GF(q) is a curve E' related to E, with cardinality |E'|, where |E|+|E'|=2*(q+1). If E is a curve in one of the curve models specified in this document, a quadratic twist of this curve can be expressed using the same curve model, although (naturally) with its own curve parameters. Two curves E and E' defined over a field GF(q) are said to be isogenous if these have the same order and are said to be isomorphic if these have the same group structure. Note that isomorphic curves have necessarily the same order and are, thus, a special type of isogenous curves. Further details are out of scope.
Weierstrass curves can have prime order, whereas Montgomery curves and twisted Edwards curves always have an order that is a multiple of four (and, thereby, a small subgroup of cardinality four).
An ordered pair (x, y) whose coordinates are elements of GF(q) can be associated with any ordered triple of the form [x*z: y*z: z], where z is a nonzero element of GF(q), and can be uniquely recovered from such a representation. The latter representation is commonly called a representation in projective coordinates. Sometimes, yet other representations are useful (e.g., representation in Jacobian coordinates). Further details are out of scope.
The group laws in Appendix C are mostly expressed in terms of affine points, but can also be expressed in terms of the representation of these points in projective coordinates, thereby allowing clearing of denominators. The group laws may also involve 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.
The field GF(q), where q is a prime power, is defined as follows.
If q:=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. This field is commonly called a prime field.
If q:=p^m, where p is a prime number and where 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, the definitions of GF(p) and GF(p^1) above coincide, since each nonzero element of GF(p) can be viewed as a polynomial in z of degree zero. If m>1, then GF(q) is called a (nontrivial) extension field of 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 K.1 and Appendix K.2, respectively. For methods for mapping a nonzero field element that is not a square in GF(q) to a point of a curve, see Appendix K.3.
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 I). Readers not interested in this, could simply view all fields as prime fields.
This section specifies group operations for elliptic curves in short-Weierstrass form, for Montgomery curves, and for twisted Edwards curves.
For each point P of the Weierstrass curve W_{a,b}, the point at infinity O serves as identity element, i.e., P + O = O + P = P.
For each affine point P:=(X, Y) of the Weierstrass curve W_{a,b}, the point -P is the point (X, -Y) and one has P + (-P) = O (i.e., -P is the inverse of P). For the point at infinity O, one has -O:=O.
Let P1:=(X1, Y1) and P2:=(X2, Y2) be distinct affine points of the Weierstrass curve W_{a,b} and let Q:=P1 + P2, where Q is not the identity element. Then Q:=(X, Y), where
Let P:=(X1, Y1) be an affine point of the Weierstrass curve W_{a,b} and let Q:=2*P, where Q is not the identity element. Then Q:=(X, Y), where
From the group laws above it follows that if P=(X, Y), P1=(X1, Y1), and P2=(X2, Y2) are distinct affine points of the Weierstrass curve W_{a,b} with P2:=P+P1 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, since
This property allows recovery of the Y-coordinate of a point P1=k*P that is computed via the so-called Montgomery ladder, where P is an affine point with nonzero Y-coordinate (i.e., it does not have order two). For future reference, note that the expression above uniquely determines the X-coordinate of P2 in terms of the X-coordinates of P and P1 and the product of their Y-coordinates. Further details are out of scope.
For each point P of the Montgomery curve M_{A,B}, the point at infinity O serves as identity element, i.e., P + O = O + P = P.
For each affine point P:=(u, v) of the Montgomery curve M_{A,B}, the point -P is the point (u, -v) and one has P + (-P) = O (i.e., -P is the inverse of P). For the point at infinity O, one has -O:=O.
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 identity element. Then Q:=(u, v), where
Let P:=(u1, v1) be an affine point of the Montgomery curve M_{A,B} and let Q:=2*P, where Q is not the identity element. Then Q:=(u, v), where
From the group laws above it follows that if P=(u, v), P1=(u1, v1), and P2=(u2, v2) are distinct affine points of the Montgomery curve M_{A,B} with P2:=P+P1 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, since
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 affine point with nonzero v-coordinate (i.e., it does not have order two). For future reference, note that the expression above uniquely determines the u-coordinate of P2 in terms of the u-coordinates of P and P1 and the product of their v-coordinates. Further details are out of scope.
Note: The group laws below hold for twisted Edwards curves E_{a,d} where a is a square in GF(q), whereas d is not. In this case, the addition formulae below are defined for each pair of points, without exceptions. Generalizations of this group law to other twisted Edwards curves are out of scope.
For each point P of the twisted Edwards curve E_{a,d}, the point O:=(0,1) serves as identity element, i.e., P + O = O + P = P.
For each point P:=(x, y) of the twisted Edwards curve E_{a,d}, the point -P is the point (-x, y) and one has P + (-P) = O (i.e., -P is the inverse of P).
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
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
Note that one can use the formulae for point addition for point doubling, taking inverses, and adding the identity element as well (i.e., the point addition formulae are uniform and complete (subject to our Note above)).
From the group laws above (subject to our Note above) it follows that if P=(x, y), P1=(x1, y1), and P2=P=(x2, y2) are points of the twisted Edwards curve E_{a,d} with P2:=P+P1 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, since
(Here, observe that a-d*y*y1*y2 is nonzero per our Note above.) 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). For future reference, note that the group law (subject to our Note above) uniquely determines the y-coordinate of P2 in terms of the y-coordinates of P and P1 and the product of their x-coordinates. Further details are out of scope.
The non-binary curves specified in Appendix A are expressed in different curve models, viz. as curves in short-Weierstrass form, as Montgomery curves, or as twisted Edwards curves. These curve models are related, as follows.
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, 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 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-to-one correspondence, which - in fact - is an isomorphism between M_{A,B} and E_{a,d}, thereby showing that, e.g., the discrete logarithm problem in either curve model is equally hard.
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 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 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 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 infinity O and the point (0, 0) of order two of M_{A,B}, while each other point (x, y) of E_{a,d} is mapped to the point (u,v):=((1+y)/(1-y),(1+y)/((1-y)*x)) of M_{A,B}.
Implementations may take advantage of this mapping to carry out elliptic curve group operations originally defined for a twisted Edwards curve on the corresponding Montgomery curve, or vice-versa, and translating the result back to the original curve, thereby potentially allowing code reuse.
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 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}, thereby showing that, e.g., the discrete logarithm problem in either curve model is equally hard.
The mapping from M_{A,B} to W_{a,b} is defined by mapping the point at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while mapping each other point (u,v) of M_{A,B} to the point (X,Y):=((u+A/3)/B,v/B) of W_{a,b}.
Note that not all Weierstrass curves can be injectively mapped to Montgomery curves, since the latter have a point of order two and the former may not. In particular, if a Weierstrass curve has prime order, such as is the case with the so-called "NIST prime 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 originally defined for a twisted Edwards curve or for a Montgomery curve using group operations for the corresponding elliptic curve in short-Weierstrass form and translating the result back to the original curve, thereby potentially allowing code reuse.
Note that implementations for elliptic curves with short-Weierstrass form that hard-code the domain parameter a to a= -3 (which value is known to allow more efficient implementations) cannot always be used this way, since the curve W_{a,b} resulting from an isomorphic mapping cannot always be expressed as a Weierstrass curve with a=-3 via a coordinate transformation. For more details, see Appendix F.
One can map points of the twisted Edwards curve E_{a,d} to points of the Weierstrass curve W_{a,b}, via function composition, where one uses the isomorphic mapping between twisted Edwards curves and Montgomery curves of Appendix D.1 and the one between Montgomery and Weierstrass curves of Appendix D.2. Obviously, one can use function composition (now using the respective inverses - if these exist) to realize the inverse of this mapping.
This section introduces curves related to Curve25519 and explains their relationships.
The elliptic curve Curve25519 is the Montgomery curve M_{A,B} defined over the prime field GF(p), with p:=2^{255}-19, where A:=486662 and B:=1. This curve has order h*n, where h=8 and where n is a prime number. For this curve, A^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 and where n1 is a prime number. For this curve, the base point is the point (Gu, Gv), where Gu=9 and where Gv is an odd integer in the interval [0, p-1].
This curve has the same group structure as (is "isomorphic" to) the twisted Edwards curve E_{a,d} defined over GF(p), with as base point the point (Gx, Gy), where parameters are as specified in Appendix E.3. This curve is denoted as Edwards25519. For this curve, the parameter a is a square in GF(p), whereas d is not, so the group laws of Appendix C.3 apply.
The curve is also isomorphic to the elliptic curve W_{a,b} in short-Weierstrass form defined over GF(p), with as base point the point (GX, GY), where parameters are as specified in Appendix E.3. This curve is denoted as Wei25519.
Each affine point (u, v) of Curve25519 corresponds to the point (X, Y):=(u + A/3, v) of Wei25519, while the point at infinity of Curve25519 corresponds to the point at infinity of Wei25519. (Here, we used the mappings of Appendix D.2 and that B=1.) Under this mapping, the base point (Gu, Gv) of Curve25519 corresponds to the base point (GX, GY) of Wei25519. The inverse mapping maps the affine point (X, Y) of Wei25519 to (u, v):=(X - A/3, Y) of Curve25519, while mapping the point at infinity of Wei25519 to the point at infinity of Curve25519. Note that this mapping involves a simple shift of the first coordinate and can be implemented via integer-only arithmetic as a shift of (p+A)/3 for the isomorphic mapping and a shift of -(p+A)/3 for its inverse, where delta=(p+A)/3 is the element of GF(p) defined by
(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 base point (Gu, Gv) of Curve25519 corresponds to the base 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 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 (c*u/v, (u-1)/(u+1)) of Edwards25519, where c is the element of GF(p) defined by Appendix D.1 and normalized this using the mapping of Appendix F.1 (where the element s of that appendix is set to c above).) The inverse mapping from Edwards25519 to Curve25519 is defined by mapping the point (0, 1) and the point (0, -1) of order two of Edwards25519 to, respectively, the point at infinity and the point (0,0) of order two of Curve25519 and having each other point (x, y) of Edwards25519 correspond to the point ((1 + y)/(1 - y), c*(1 + y)/((1-y)*x)) of Curve25519.
(Here, we used the mapping of
The curve Edwards25519 is isomorphic to the Weierstrass curve Wei25519, where the base point (Gx, Gy) of Edwards25519 corresponds to the base point (GX,GY) of Wei25519 and where the identity element (0,1) and the point (0,-1) of order two of Edwards25519 correspond to, respectively, the point at infinity O and the point (A/3, 0) of order two of Wei25519 and where each other point (x, y) of Edwards25519 corresponds to the point (X, Y):=((1+y)/(1-y)+A/3, 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 Wei25519 to Edwards25519 is defined by mapping the point at infinity O and the point (A/3, 0) of order two of Wei25519 to, respectively, the identity element (0,1) and the point (0,-1) of order two of Edwards25519 and having each other point (X, Y) of Wei25519 correspond to the point (c*(X-A/3)/Y, (X-A/3-1)/(X-A/3+1)) of Edwards25519.
Note that these mappings can be easily realized if points are represented in projective coordinates, using a few field multiplications only, thus allowing switching between alternative curve representations with negligible relative incremental cost.
The parameters of the Montgomery curve and the corresponding isomorphic curves in twisted Edwards curve and short-Weierstrass form are as indicated below. Here, the domain parameters of the Montgomery curve Curve25519 and of the twisted Edwards curve Edwards25519 are as specified in [RFC7748]; the domain parameters of Wei25519 are "new".
General parameters (for all curve models):
Montgomery curve-specific parameters (for Curve25519):
Twisted Edwards curve-specific parameters (for Edwards25519):
Weierstrass curve-specific parameters (for Wei25519):
The non-binary curves specified in Appendix A are expressed in different curve models, viz. as curves in short-Weierstrass form, as Montgomery curves, or as twisted Edwards curves. In Appendix D we already described relationships between these various curve models. Further mappings exist between elliptic curves within the same curve model. These can be exploited to force some of the domain parameters to specific values that allow for a more efficient implementation of the addition formulae.
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 and that are known to allow for more efficient implementations of addition laws and translating the result back to the original curve. In particular, it is known that such efficiency improvements exist if a':=(+/-)1 (see [tEd-Formulas]).
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 these mappings 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 and that are known to allow for more efficient implementations of addition laws and translating the result back to the original curve. In particular, it is known that such efficiency improvements exist if B' assumes a small absolute value, such as B':=(+/-)1. (see [Mont-Ladder]).
One can map points of the Weierstrass curve W_{a,b} to points of the Weierstrass curve W_{a',b'}, where a':=a*s^4 and b':=b*s^6 for some nonzero element s of GF(q). This defines a one-to-one correspondence, which - in fact - is an isomorphism between W_{a,b} and W_{a',b'}.
The mapping from W_{a,b} to W_{a',b'} is defined by mapping the point at infinity O of W_{a,b} to the point at infinity O of W_{a',b'}, while mapping each other point (X,Y) of W_{a,b} to the point (X',Y'):=(X*s^2, Y*s^3) of W_{a',b'}. The inverse mapping from W_{a',b'} to W_{a,b} is defined by mapping the point at infinity O of W_{a',b'} to the point at infinity O of W_{a,b}, while mapping each other point (X', Y') of W_{a',b'} to the point (X,Y):=(X'/s^2,Y'/s^3) of W_{a,b}.
Implementations may take advantage of this mapping to carry out elliptic curve group operations originally defined for a Weierstrass curve with generic domain parameters a and b on a corresponding isomorphic Weierstrass curve with domain parameter a' and b' that have a more special form and that are known to allow for more efficient implementations of addition laws and translating the result back to the original curve. In particular, it is known that such efficiency improvements exist if a'=-3 (mod p), where p is the characteristic of GF(q), and one uses so-called Jacobian coordinates with a particular projective version of the addition laws of Appendix C.1. While not all Weierstrass curves can be put into this form, all traditional NIST curves have domain parameter a=-3, while all Brainpool curves [RFC5639] are isomorphic to a Weierstrass curve of this form via the above mapping.
Note that implementations for elliptic curves with short-Weierstrass 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 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) (see Section 3.1.5 of [GECC]). However, even in this case, one can still express the curve W_{a,b} as a Weierstrass curve with a small domain parameter value a', thereby still allowing a more efficient implementation than with a general domain parameter value a.
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) and where p is the characteristic of GF(q), even if a'/a is not a fourth power in GF(q). In that case, this mappping cannot be an isomorphism (see Appendix F.3). Instead, the mapping is a so-called isogeny (or homomorphism). Since most elliptic curve operations process points of prime order or use so-called "co-factor multiplication", in practice the resulting mapping has similar properties as an isomorphism. In particular, one can still take advantage of this mapping to carry out elliptic curve group operations originally defined for a Weierstrass curve with domain parameter a unequal to -3 (mod p) on a corresponding isogenous Weierstrass curve with domain parameter a'=-3 (mod p) and translating the result back to the original curve.
In this case, the mapping from W_{a,b} to W_{a',b'} is defined by mapping the point at infinity O of W_{a,b} to the point at infinity O of W_{a',b'}, while mapping each other point (X,Y) of W_{a,b} to the point (X',Y'):=(u(X)/w(X)^2,Y*v(X)/w(X)^3) of W_{a',b'}. Here, u(X), v(X), and w(X) are polynomials in X that depend on the isogeny in question, as do domain parameters a' and b'. The inverse mapping from W_{a',b'} to W_{a,b} is again an isogeny (called the dual isogeny) and defined by mapping the point at infinity O of W_{a',b'} to the point at infinity O of W_{a,b}, while mapping each other point (X', Y') of W_{a',b'} to the point (X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of W_{a,b}, where -- again -- u'(X'), v'(X'), and w'(X') are polynomials in X' that depend on the isogeny in question. These mappings have the property that their composition is not the identity mapping (as was the case with the isomorphic mappings discussed in Appendix F.3), but rather a fixed multiple hereof: if this multiple is l then the isogeny is called an isogeny of degree l (or l-isogeny) and u, v, and w (and, similarly, u', v', and w') are polynomials of degrees l, 3*(l-1)/2, and (l-1)/2, respectively. Note that an isomorphism is simply an isogeny of degree l=1. Details of how to determine isogenies are out of scope of this document. The above formulas assume that the isogeny has odd degree (i.e., l is odd); detailed formulas for even-degree isogenies are similar, but out of scope.
Implementations may take advantage of this mapping to carry out elliptic curve group operations originally defined for a Weierstrass curve with a generic domain parameter a on a corresponding isogenous Weierstrass curve with domain parameter a'=-3 (mod p), where one can use so-called Jacobian coordinates with a particular projective version of the addition laws of Appendix C.1. Since all traditional NIST curves have domain parameter a=-3, while all Brainpool curves [RFC5639] are isomorphic to a Weierstrass curve of this form, this allows taking advantage of existing implementations for these curves that may have a hardcoded a=-3 (mod p) domain parameter, provided one switches back and forth to this curve form using the isogenous mapping in question.
Note that isogenous mappings can be easily realized using representations in projective coordinates and involves roughly 3*l finite field multiplications, thus allowing switching between alternative representations at relatively low incremental cost compared to that of elliptic curve scalar multiplications (provided the isogeny has low degree l). Note, however, that this does require storage of the polynomial coefficients of the isogeny and dual isogeny involved. This illustrates that low-degree isogenies are to be preferred, since an l-isogeny (usually) requires storing roughly 6*l elements of GF(q). While there are many isogenies, we therefore only consider those with the desired property with lowest possible degree.
This section introduces some further curves related to Curve25519 and explains their relationships.
The Weierstrass curve Wei25519 is isomorphic to the Weierstrass curve Wei25519.2 defined over GF(p), with as base point the pair (G2X,G2Y), and isogenous to the Weierstrass curve Wei25519.-3 defined over GF(p), with as base point the pair (G3X, G3Y), where parameters are as specified in Appendix G.3 and where the related mappings are as specified in Appendix G.2.
Each affine point (X, Y) of Wei25519 corresponds to the point (X', Y'):=(X*s^2,Y*s^3) of Wei25519.2, where s is the element of GF(p) defined by Appendix F.3.) Under this mapping, the base point (GX, GY) of Wei25519 corresponds to the base point (G2X,G2Y) of Wei25519.2. The inverse mapping maps the affine point (X', Y') of Wei25519.2 to (X,Y):=(X'/s^2,Y'/s^3) of Wei25519, while mapping the point at infinity O of Wei25519.2 to the point at infinity O of Wei25519. Note that this mapping (and its inverse) involves a modular multiplication of both coordinates with fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which can be precomputed.
while the point at infinity of Wei25519 corresponds to the point at infinity of Wei25519.2. (Here, we used the mapping of
Each affine point (X,Y) of Wei25519 corresponds to the point (X',Y'):=(X1*t^2,Y1*t^3) of Wei25519.-3, where (X1,Y1)=(u(X)/w(X)^2,Y*v(X)/w(X)^3), where u, v, and w are the polynomials with coefficients in GF(p) as defined in Appendix G.4.1 and where t is the element of GF(p) defined by Appendix F.4.) Under this isogenous mapping, the base point (GX,GY) of Wei25519 corresponds to the base point (G3X,G3Y) of Wei25519.-3. The dual isogeny maps the affine point (X',Y') of Wei25519.-3 to the affine point (X,Y):=(u'(X1)/w'(X1)^2,Y1*v'(X1)/w'(X1)^3) of Wei25519, where (X1,Y1)=(X'/t^2,Y'/t^3) and where u', v', and w' are the polynomials with coefficients in GF(p) as defined in Appendix G.4.2, while mapping the point at infinity O of Wei25519.-3 to the point at infinity O of Wei25519. Under this dual isogenous mapping, the base point (G3X, G3Y) of Wei25519.-3 corresponds to a multiple of the base point (GX, GY) of Wei25519, where this multiple is l=47 (the degree of the isogeny; see the description in Appendix F.4). Note that this isogenous map (and its dual) primarily involves the evaluation of three fixed polynomials involving the x-coordinate, which takes roughly 140 modular multiplications (or less than 5-10% relative incremental cost compared to the cost of an elliptic curve scalar multiplication).
while the point at infinity of Wei25519 corresponds to the point at infinity of Wei25519.-3. (Here, we used the isogenous mapping of
The parameters of the Weierstrass curve with a=2 that is isomorphic with Wei25519 and the parameters of the Weierstrass curve with a=-3 that is isogenous with Wei25519 are as indicated below. Both domain parameter sets can be exploited directly to derive more efficient point addition formulae, should an implementation facilitate this.
General parameters: same as for Wei25519 (see Appendix E.3)
Weierstrass curve-specific parameters (for Wei25519.2, i.e., with a=2):
Weierstrass curve-specific parameters (for Wei25519.-3, i.e., with a=-3):
The isogeny and dual isogeny are both isogenies with degree l=47. Both are specified by a triple of polynomials u, v, and w (resp. u', v', and w') of degree 47, 69, and 23, respectively, with coefficients in GF(p). The coeffients of each of these polynomials are specified in Appendix G.4.1 (for the isogeny) and in Appendix G.4.2 (for the dual isogeny). For each polynomial in variable x, the coefficients are tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in hexadecimal format.
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 an 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), with p odd, and then extend to all fields GF(q), where q is an odd prime power. We assume each finite field to be unambiguously defined and known from context.
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.
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 W_{a,b}, 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.
We extend the definition of the point compression function to all points of the curve W_{a,b}, by associating the (non-affine) point at infinity O with any ordered pair compr(O):=(X,0), where X is any element of GF(q) for which alpha:=X^3+a*X+b is not a square in GF(q), and recover this point accordingly. In this case, the point at infinity O can be represented by any ordered pair (X,0) of elements of GF(q) for which X^3+a*X+b is not a square in GF(q). Note that this ordered pair does not satisfy the defining equation of the curve in question. An application may fix a specific suitable value of X or choose multiple such values and use this to encode additonal information. Further details are out of scope.
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 M_{A,B}, 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.
We extend the definition of the point compression function to all points of the curve M_{A,B}, by associating the (non-affine) point at infinity O with the ordered pair compr(O):=(0,1) and recover this point accordingly. (Note that this corresponds to the case alpha=0 and t=1 above.) The point at infinity O can be represented by the ordered pair (0, 1) of elements of GF(q). Note that this ordered pair does not satisfy the defining equation of the curve in question.
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 E_{a,d}, 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). (Here, observe that the denominator is nonzero for any point of E_{a,d}.) 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.
Note that the point compression function is defined for all points of the twisted Edwards curve E_{a,d}. Here, the identity element O:=(0,1) is associated with the compressed point compr(O):=(0,1). (Note that this corresponds to the case alpha=0 and t=0 above.)
We extend the definition of the compression function further, to also include a special marker element 'btm', by associating this marker element with the ordered pair compr(btm):=(1,1) and recover this marker element accordingly. (Note that this corresponds to the case alpha=0 and t=1 above.) The marker element 'btm' can be represented by the ordered pair (1,1) of elements of GF(q). Note that this ordered pair does not satisfy the defining equation of the curve in question.
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.
The right-concatenation of two strings X and Y (defined over the same alphabet) is the string Z consisting of the symbols of X (in the same order) followed by the symbols of Y (in the same order). The length of the resulting string Z is the sum of the lengths of X and Y. This string operation is denoted by Z:=X||Y. The string X is called a prefix of Z; the string Y a postfix. The t-prefix of a string Z of length l is its unique prefix X of length t; the t-postfix its unique postfix Y of length t (where in both cases t is an integer in the interval [0,l]). One can define these notions as well if t is outside the interval [0,l] by stipulating that a t-prefix or t-postfix is the empty string if t is negative and that it is the entire string Z if t is larger than l. Sometimes, a t-prefix of a string Z is denoted by trunc-left(Z,t); a t-postfix by trunc-right(Z,t). A string X is called a substring of Z if it is a prefix of some postfix of Z. The string resulting from prepending the string Y with X is the string X||Y.
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, as are the operations in the previous paragraph.
There is a 1-1 correspondence between bit strings of length l and 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. This defines the mapping BS2I from bit strings to integers and the mapping I2BS(x,l) from non-negative integers smaller than 2^l to bit strings of length l.
There is a 1-1 correspondence between octet strings of length l and 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.
There is a 1-1 correspondence between octet strings of length l 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 I.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.
There is a 1-1 correspondence between elements of the fixed finite field GF(q), where q:=p^m, where p is a prime number and where 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 I.2 above. Note that both the mapping from field elements to octet strings and the inverse mapping from octet strings to field elements 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. (Observe that with tight representations, the parameter l is uniquely defined by the characteristic p of the field GF(q) in question.)
There is a 1-1 correspondence between elements of the set Z_n of integers modulo n and integers in the interval [0,n), where each element x of Z_n is uniquely represented by the integer x mod n. In this case, x mod n can be uniquely represented by the octet string X according to the mapping of Appendix I.2 above. Note that both the mapping from elements of Z_n to octet strings and the inverse mapping from octet strings to elements of Z_n are only uniquely defined if the octet string has a fixed size (e.g., the smallest integer l so that 256^l >= n) and if all integers are first reduced modulo n. If so, the latter representation is called tight if l is minimal so that 256^l >= n. This defines the mapping ZnE2OS(x,l) from elements of Z_n to octet strings and the mapping OS2ZnE(X,l) from octet strings to elements of Z_n, where the underlying modulus n is implicit and assumed to be known from context. In this case, the octet string has length l. (Observe that with tight representations, the parameter l is uniquely defined by the parameter n in question.)
Note that if n is a prime number p, the conversions ZnE2OS and FE2OS are consistent, as are OS2ZnE and OS2FE. This is, however, no longer the case if n is a strict prime power.
The conversion rules for composite n values may be useful, e.g., when encoding RSA parameters (or elements of any other non-prime size set Z_n, for that matter).
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:
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. (Note, in particular, that tightness implies that elements of GF(q) are always uniquely represented.)
Note that elements of a prime field GF(p), where p is a 255-bit prime number, have a tight representation as a 32-byte string, where a fixed bit position is always set to zero. (This is the leftmost bit position of this octet string if one follows the MSB/msb representation conventions.) This allows the parity bit of a compressed point (see Appendix H) to be encoded in this bit position and, thereby, allows a compressed point and a field element of GF(p) to be represented by an octet string of the same length. This is called the squeezed point representation. Obviously, other representations (e.g., those of elements of Z_n) may also have fixed bit values in certain positions, which can be used to squeeze-in additional information. Further details are out of scope.
We present some examples of computations using the curves introduced in this document. In each case, we indicate the values of P, k*P, and (k+1)*P, where P is a fixed multiple (here: 2019) of the base point of the curve in question and where the private key k is the integer
Pm=(u, v), k*Pm=(u1, v1), and (k+1)*Pm=(u2, v2) with Curve25519:
As suggested in Appendix C.2, the v-coordinate of k*Pm can be indirectly computed from the u-coordinates of Pm, k*Pm, and (k+1)*Pm, and the v-coordinate of Pm, which allows computation of the entire point k*Pm (and not just its u-coordinate) if k*Pm is computed using the Montgomery ladder (as, e.g., [RFC7748] recommends), since that algorithm computes both u1 and u2 and the v-coordinate of the point Pm may be available from context.
The representation of k and the compressed representations of Pm and k*Pm in tight LSB/msb-order are given by Appendix H.2 and Appendix I for further detail on (squeezed) point compression.
where the leftmost bit of the rightmost octet indicates the parity of the v-coordinate of the point of Curve25519 in question (which, in this case, are both zero, since v and v1 are even). See
The scalar representation and (squeezed) point representation illustrated above are consistent with the representations specified in [RFC7748], except that in [RFC7748] only an affine point's u-coordinate is represented (i.e., the v-coordinate of any point is always implicitly assumed to have an even value) and that the representation of the point at infinity is not specified. Another difference is that [RFC7748] allows non-unique representations of some elements of GF(p), whereas our representation conventions do not (since tight).
A randomized representation (t1, t2) of the point k*Pm in tight LSB/msb order is given by Appendix K.5 and uses the mapping of Appendix K.3.2 with the default square root function.
where this representation is defined in
Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Edwards25519:
The representation of k and the compressed representations of Pe and k*Pe in tight LSB/lsb-order are given by Appendix H.3 and Appendix I for further detail on (squeezed) point compression.
where the rightmost bit of the rightmost octet indicates the parity of the x-coordinate of the point of Edwards25519 in question (which, in this case, are zero and one, respectively, since x is even and x1 is odd). See
The scalar representation and (squeezed) point representation illustrated above are fully consistent with the representations specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032] requires unique representations of all elements of GF(p).
A randomized representation (t1, t2) of the point k*Pe in tight LSB/lsb order is given by Appendix K.5 and uses the mapping of Appendix K.3.3 with the default square root function and underlying isomorphic mapping between Edwards25519 and Curve25519 of Appendix E.2.
where this representation is defined in
Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519:
The representation of k and the compressed representations of Pw and k*Pw in tight MSB/msb-order are given by Appendix H.1 and Appendix I for further detail on (squeezed) point compression.
where the leftmost bit of the leftmost octet indicates the parity of the Y-coordinate of the point of Wei25519 in question (which, in this case, are both zero, since Y and Y1 are even). See
The scalar representation is consistent with the representations specified in [SEC1]; the (squeezed) point representation illustrated above is "new". For completeness, we include a SEC1-consistent representation of the point Pw in affine format and in compressed format below.
The SEC1-compliant affine representation of the point Pw in tight MSB/msb-order is given by
whereas the SEC1-compliant compressed representation of the point Pw in tight MSB/msb-order is given by
The SEC1-compliant uncompressed format aff(Pw) of an affine point Pw corresponds to the right-concatenation of its X- and Y-coordinates, each in tight MSB/msb-order, prepended by the string 0x04, where the reverse procedure is uniquely defined, since elements of GF(p) have a unique fixed-size representation. The (squeezed) compressed format repr(Pw) corresponds to the SEC1-compliant compressed format by extracting the parity bit t from the leftmost bit of the leftmost octet of repr(Pw), replacing the bit position by the value zero, and prepending the octet string with 0x02 or 0x03, depending on whether t=0 or t=1, respectively, where the reverse procedure is uniquely defined, since GF(p) is a 255-bit prime field. For further details, see [SEC1]. Note that, due to the bit-size of the prime p, the squeezed compressed format repr(Pw) is one octet shorter than the SEC1-compliant compressed format compr(Pw).
A randomized representation (t1, t2) of the point k*Pw in tight MSB/msb order is given by Appendix K.5 and uses the mapping of Appendix K.3.1 with the default square root function.
where this representation is defined in
Pw2=(X, Y), k*Pw2=(X1, Y1), and (k+1)*Pw2=(X2, Y2) with Wei25519.2:
The representation of k and the compressed representations of Pw2 and k*Pw2 in tight MSB/msb-order are given by Appendix H.1 and Appendix I for further detail on (squeezed) point compression.
where the leftmost bit of the leftmost octet indicates the parity of the Y-coordinate of the point of Wei25519.2 in question (which, in this case, are both zero, since Y and Y1 are even). See Appendix
A randomized representation (t1, t2) of the point k*Pw2 in tight MSB/msb order is given by Appendix K.5 and uses the mapping of Appendix K.3.1 with the default square root function.
where this representation is defined in
Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei25519.-3:
The representation of k and the compressed representations of Pw3 and k*Pw3 in tight MSB/msb-order are given by Appendix H.1 and Appendix I for further detail on (squeezed) point compression.
where the leftmost bit of the leftmost octet indicates the parity of the Y-coordinate of the point of Wei25519.-3 in question (which, in this case, are one and zero, respectively, since Y is odd and Y1 is even). See
A randomized representation (t1, t2) of the point k*Pw3 in tight MSB/msb order is given by Appendix K.5 and uses the mapping of Appendix K.3.1 with the default square root function.
where this representation is defined in
This section illustrates how one could implement common routines, such as taking square roots and inverses in finite fields, and how to map field elements to curve points and to curve points that avoid some outliers.
Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see Appendix K.1.1) or if q = 5 (mod 8) (see Appendix K.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).
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).
If y is a nonzero element of GF(q) and z:=y^{(q-5)/8}, then y is a square in GF(q) only if y^2*z^4=1.
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.
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
If inverses are easy to compute in GF(q), then so are these in GF(q^2). Further details are out of scope.
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.
One can map elements of GF(q) that are not a square in GF(q) to points of a Weierstrass curve (see Appendix K.3.1), to points of a Montgomery curve (see Appendix K.3.2), or to points of a twisted Edwards curve (see Appendix K.3.3), under some mild conditions on the domain parameters. Full details on mappings that apply if these conditions are not satisfied are out of scope.
The description below assumes that the domain parameters a and b of the Weierstrass curve W_{a,b} are nonzero. For ease of exposition, we define f(z):=z^3+a*z+b. (Note that for an affine point (X,Y) of W_{a,b} one has Y^2=f(X).)
If t is an element of GF(q) that is not a square in GF(q) and that is unequal to -1, then the element X:=(-b/a)*(1+1/(t+t^2)) is the unique solution of the equation f(t*X)=t^3*f(X) and is nonzero. Consequently, either X or X':=t*X is the x-coordinate of an affine point of W{a,b}, depending on whether f(X) is a square in GF(q). Appendix H) satisfies this condition (henceforth called the default square root function).
Formally, this mapping is not properly defined, since a nonzero square y:=x^2 in GF(q) has two solutions, viz. x and -x; it is properly defined, however, if one designates for each element in GF(q) that is a square in GF(q) precisely one square root as "the" square root of this element. Note that always picking the square root with zero parity (see
If -1 is not a square in GF(q), this element is mapped to the point at infinity O of W_{a,b}.
The set of points of W_{a,b} that arises this way has size roughly 3/8 of the order of the curve and each such point arises as image of one or two t values. Further details are out of scope.
NOTE 1: If -1 is not a square in GF(q), the mapping above yields the point at infinity for t=-1. One can modify this mapping to always yield an affine point, by mapping the element -1 to, e.g., the base point G of W_{a,b} and leaving the remainder of the mapping the same. Suitability of such a modification is application-specific. Details are out of scope.
NOTE 2: The description above assumes that the domain parameters a and b of the Weierstrass curve are nonzero. If this is not the case, one can often find an isogenous curve W_{a',b'} for which the domain parameters a' and b' are nonzero. If so, one can map elements of GF(q) that are not a square in GF(q) to points of W_{a,b} via function composition, where one uses the mapping above to arrive at a point of W_{a',b'} and where one subsequently uses the dual isogeny from W_{a',b'} to W_{a,b} to arrive at a point of W_{a,b}. As an example, one can show that if a is zero and if -4*b is a cube in GF(q) (such as is the case with, e.g., the "BitCoin" curve secp256k1 [SEC2]), this curve is 3-isogenous to a curve with this property and the strategy above applies (for an example with secp256k1, see Appendix L). Further details are out of scope.
The description below assumes that the domain parameter A of the Montgomery curve M_{A,B} is nonzero. For ease of exposition, we define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of M_{A,B} one has B*v^2=f(u).)
If t is an element of GF(q) that is not a square in GF(q) and that is unequal to -1, then the element u:=-(1+1/t)/A is the unique nonzero solution of the equation f(t*u)=t^3*f(u). Consequently, either u or u':=t*u is the u-coordinate of an affine point of M{A,B}, depending on whether f(u)/B is a square in GF(q). Appendix H) satisfies this condition (henceforth called the default square root function).
As before, formally, this mapping is not properly defined, since a nonzero square y:=x^2 in GF(q) has two solutions, viz. x and -x; it is properly defined, however, if one designates for each element in GF(q) that is a square in GF(q) precisely one square root as "the" square root of this element. Note that always picking the square root with zero parity (see
If -1 is not a square in GF(q), this element is mapped to the point at infinity O of M_{A,B}.
The set of points of M_{A,B} that arises this way has size roughly 1/2 of the order of the curve and each such point arises as image of precisely one t value. Further details are out of scope.
NOTE 1: If -1 is not a square in GF(q), the mapping above yields the point at infinity for t=-1. One can modify this mapping to always yield an affine point, by mapping the element -1 to, e.g., the base point G of M_{A,B} and leaving the remainder of the mapping the same. Suitability of such a modification is application-specific. Details are out of scope.
NOTE 2: The description above assumes that the domain parameter A of the Montgomery curve is nonzero. If this is not the case, the curve is a Weierstrass curve for which the domain parameter b is zero and Note 2 of Appendix K.3.1 applies. If q = 3 (mod 4), an even simpler approach is possible, where one modifies the construction above and simply takes u:=t and u':=-t (which works, since -1 is not a square in GF(q) and f(-t)=-f(t)). In this case, this construction can be extended to all elements t of GF(q) and, if so, yields a 1-1 mapping between GF(q) and all affine curve points.
One can map elements of GF(q) that are not a square in GF(q) to points of the twisted Edwards curve E_{a,d} via function composition, where one uses the mapping of Appendix K.3.1 to arrive at a point of the Weierstrass curve W_{a,b} and where one subsequently uses the isomorphic mapping between twisted Edwards curves and Weierstrass curves of Appendix D.3 to arrive at a point of E_{a,d}. Another mapping is obtained by function composition, where one instead uses the mapping of Appendix K.3.2 to arrive at a point of the Montgomery curve M_{A,B} and where one subsequently uses the isomorphic mapping between twisted Edwards curves and Montgomery curves of Appendix D.1 to arrive at a point of E_{a,d}. Obviously, one can use function composition (now using the respective pre-images - if these exist) to realize the pre-images of either mapping.
Appendix K.3 described how one can map elements of GF(q) that are not a square in GF(q) to points of a Weierstrass curve, to points of a Montgomery curve, or to points of a twisted Edwards curve, under some mild conditions on the domain parameters. Below, we use the mappings of that appendix and the parity function par(.) specified in Appendix H to construct mappings to high-order curve points only (i.e., mappings that avoid points in the small subgroup, see Appendix B.1). We consider mappings to high-order points of a Weierstrass curve (see Appendix K.4.1), to high-order points of a Montgomery curve (see Appendix K.4.2), and to high-order points of a twisted Edwards curve (see Appendix K.4.3). As before, full details on mappings that apply if the mild conditions on the domain parameters are not satisfied are out of scope.
The description below assumes that the domain parameters a and b of the Weierstrass curve W_{a,b} are nonzero. For ease of exposition, we define f(z):=z^3+a*z+b. (Note that for an affine point (X,Y) of W_{a,b} one has Y^2=f(X).)
If t is an element of GF(q) that is not a square in GF(q) and that is unequal to -1, the mapping of Appendix K.3.1 yields an affine point P(t):=(X, Y) of W_{a,b}. Let P0:=(X0, Y0) be a fixed affine point of W_{a,b} for which neither P0, P0 + P(t), nor P0 - P(t) is in the small subgroup of W_{a,b}. (Note that this implies that P0 and P(t) are distinct affine points of the curve and that these are not each other's inverse.) For binary digit s, the point Q(t,s) is now defined as follows: Table 1).
Note that this mapping is properly defined as long as the fixed point P0 (the so-called "curve offset") alluded to above indeed exists. In cases of practical interest that we are aware of, this is indeed the case (see, e.g.,
If -1 is not a square in GF(q), the pair (-1,s) is mapped to the affine point P0 of W_{a,b} (irrespective of the value of s).
The set of points of W_{a,b} that arises this way has size roughly 3/8 of the order of the curve and each such point arises as image of up to four values of the pair (t,s). Further details are out of scope.
From the group law for Weierstrass curves (see Appendix C.1) it follows that one can express the coordinates of Q(t,s), with t<>-1, in terms of the X-coordinates of P0 and P(t) and the product of their Y-coordinates. (Here, observe that Y0*Y is a square root of f(X0)*f(X).) Thus, Q(t,s) can be computed without the need to fully compute P(t).
The description below assumes that the domain parameters A and B of the Montgomery curve M_{A,B} are nonzero. For ease of exposition, we define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of M_{A,B} one has B*v^2=f(u).)
If t is an element of GF(q) that is not a square in GF(q) and that is unequal to -1, the mapping of Appendix K.3.2 yields an affine point P(t):=(u, v) of M_{A,B}. Let P0:=(u0, v0) be a fixed affine point of M_{A,B} for which neither P0, P0 + P(t), nor P0 - P(t) is in the small subgroup of M_{A,B}. (Note that this implies that P0 and P(t) are distinct affine points of the curve and that these are not each other's inverse.) For binary digit s, the point Q(t,s) is now defined as follows: Table 1).
Note that this mapping is properly defined as long as the fixed point P0 (the so-called "curve offset") alluded to above indeed exists. In cases of practical interest that we are aware of, this is indeed the case (see, e.g.,
If -1 is not a square in GF(q), the pair (-1,s) is mapped to the affine point P0 of M_{A,B} (irrespective of the value of s).
The set of points of M_{A,B} that arises this way has size roughly 1/2 of the order of the curve and each such point arises as image of up to two values of the pair (t,s). Further details are out of scope.
From the group law for Montgomery curves (see Appendix C.2) it follows that one can express the coordinates of Q(t,s), with t<>-1, in terms of the u-coordinates of P0 and P(t) and the product of their v-coordinates. (Here, observe that B*v0*v is a square root of f(u0)*f(u).) Thus, Q(t,s) can be computed without the need to fully compute P(t).
| Curve | Fixed curve offset P0 |
|---|---|
| NIST P-224 [FIPS-186-4] | Base point (Gx,Gy) |
| NIST P-256 [FIPS-186-4] | P0:=(0,y) with y even |
| NIST P-384 [FIPS-186-4] | P0:=(0,y) with y even |
| NIST P-521 [FIPS-186-4] | P0:=(0,y) with y even |
| Brainpool224r1 [RFC5639] | Base point (Gx, Gy) |
| Brainpool256r1 [RFC5639] | Base point (Gx, Gy) |
| Brainpool320r1 [RFC5639] | Base point (Gx, Gy) |
| Brainpool384r1 [RFC5639] | Base point (Gx, Gy) |
| Brainpool512r1 [RFC5639] | P0:=(3,y), y even |
| Curve25519 [RFC7748] | P0:=(90,v), v even |
| Curve448 [RFC7748] | P0:=(50,v), v even |
| Wei25519 [Appendix E.3] | P0:=(3,y), y even |
| Wei25519.2 [Appendix G.3] | P0:=(244,y), y even |
| Wei25519.-3 [Appendix G.3] | P0:=(41,y), y even |
| secp256k1.m [Appendix L.3] | P0:=(0,y), y even |
One can map elements of GF(q) that are not a square in GF(q) to points of the twisted Edwards curve E_{a,d} via function composition, where one uses the mapping of Appendix K.4.1 to arrive at a point of the Weierstrass curve W_{a,b} that does not have low order and where one subsequently uses the isomorphic mapping between twisted Edwards curves and Weierstrass curves of Appendix D.3 to arrive at a point of E_{a,d} with this property. Another mapping is obtained by function composition, where one instead uses the mapping of Appendix K.4.2 to arrive at a point of the Montgomery curve M_{A,B} that does not have low order and where one subsequently uses the isomorphic mapping between twisted Edwards curves and Montgomery curves of Appendix D.1 to arrive at a point of E_{a,d} with this property. Obviously, one can use function composition (now using the respective pre-images - if these exist) to realize the pre-images of either mapping.
The mappings of Appendix K.3 allow one to represent a curve point Q as a specific element t of GF(q), provided this point arises as a point in the range of the mapping at hand. For Montgomery curves and twisted Edwards curves, this covers roughly half of the curve points; for Weierstrass curves, roughly 3/8 of the curve points. One can extend the mappings above, by mapping a pair (t1, t2) of inputs to the point Q:=P2(t1, t2):=P(t1) + P(t2). In this case, each curve point has roughly q/4 representations as an ordered pair (t1, t2) on average. In fact, one can show that if the input pairs are generated uniformly at random, then the corresponding curve points follow a distribution that is also (statistically indistinguishable from) a uniform distribution, and vice-versa. Here, each pair (t1, t2) deterministically yields a curve point, whereas for each curve point Q, a randomized algorithm yields an ordered pair (t1, t2) of pre-images of Q, where the expected number of randomized pre-images one has to try is small (four if one uses the mapping of Appendix K.3.1; two if one uses the mapping of Appendix K.3.2). For further details, see Algorithm 1 of [Tibouchi].
Similar properties hold if one uses the mappings of Appendix K.4 (rather than those of Appendix K.3): in this case, the mapping allows one to represent a curve point Q as a specific element (t,s) of GF(q)x{0,1}, provided this point arises as a point in the range of the mapping at hand. For Montgomery curves and twisted Edwards curves, this covers roughly half of the curve points; for Weierstrass curves, roughly 3/8 of the curve points. One can extend the mappings above, by mapping a pair ((t1,s1), (t2,s2)) of inputs to the point Q:=Q2((t1,s1), (t2,s2)):=Q(t1,s1) - Q(t2,s2). In this case, each curve point has roughly q representations as an ordered pair ((t1,s1), (t2,s2)) on average. In fact, one can show that if the input pairs are generated uniformly at random, then the corresponding curve points follow a distribution that is also (statistically indistinguishable from) a uniform distribution, and vice-versa. Here, each pair ((t1,s1), (t2,s2)) deterministically yields a curve point, whereas for each curve point Q, a randomized algorithm yields an ordered pair ((t1,s1), (t2,s2)) of pre-images of Q, where the expected number of randomized pre-images one has to try is small (four if one uses the mapping of Appendix K.4.1; two if one uses the mapping of Appendix K.4.2). Further details are out of scope.
NOTE 1: The main difference between the two constructions above is that that the first construction uses the mappings to curve points described in Appendix K.3, while the second construction uses the mappings to high-order curve points described in Appendix K.4. Note that Q2((t1,s1), (t2,s2)) assumes all values (+/-) P(t1) (+/-) P(t2) if one considers all possible values for the binary digits s1 and s2. (This, thereby, includes the value P2(t1, t2).)
NOTE 2: The second mapping above operates on input pairs (t,s), where t is an element of GF(q) that is not a square in GF(q) and where s is a binary digit from the set {0,1}. One can use these mappings to produce a mapping from the nonzero elements of GF(q) to points of a curve via function composition, where one first maps any nonzero element u of GF(q) to the pair (t,s):=(delta*u^2, par(u)), where delta is a fixed element of GF(q) that is not a square in GF(q), and where one subsequently applies any of the mappings above to yield a point of the curve in question. The resulting mapping from the nonzero elements of GF(q) to high-order curve points can be extended further to one that operates on all elements of GF(q) by mapping 0 to any fixed high-order point of the curve in question (e.g., to the fixed "curve offset" P0 of this curve [henceforth called the default completed mapping]). Depending on application-specific criteria, yet other function compositions may be preferred. For the first mapping above, one can use a similar function composition, where one simply drops the binary digit s and maps 0 to the point at infinity or any other suitable curve point. Further details are out of scope.
This section illustrates how isogenies can be used to yield curves with specific properties (here, for illustrated for the "BitCoin" curve secp256k1).
The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined over the prime field GF(p), with p:=2^256-2^32-2^9-2^8-2^7-2^6-2^4-1, where a:=0 and b:=7. This curve has order h*n, where h=1 and where n is a prime number. For this curve, domain parameter a is zero, whereas b is not. The quadratic twist of this curve has order h1*n1, where h1 is a 37-bit integer and where n1 is a prime number. For this curve, the base point is the point (GX, GY).
The curve secp256k1 is 3-isogenous to the Weierstrass curve secp256k1.m defined over GF(p), which has nonzero domain parameters a and b and has as base point the pair (GmX,GmY), where parameters are as specified in Appendix L.3 and where the related mappings are as specified in Appendix L.2.
Each affine point (X,Y) of secp256k1 corresponds to the point (X',Y'):=(u(X)/w(X)^2,Y*v(X)/w(X)^3) of secp256k1.m, where u, v, and w are the polynomials with coefficients in GF(p) as defined in Appendix L.4.1, while the point at infinity of secp256k1 corresponds to the point at infinity of secp256k1.m. Under this isogenous mapping, the base point (GX,GY) of secp256k1 corresponds to the base point (GmX,GmY) of secp256k1.m. The dual isogeny maps the affine point (X',Y') of secp256k1.m to the affine point (X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of secp256k1, where u', v', and w' are the polynomials with coefficients in GF(p) as defined in Appendix L.4.2, while mapping the point at infinity O of secp256k1.m to the point at infinity O of secp256k1. Under this dual isogenous mapping, the base point (GmX, GmY) of secp256k1.m corresponds to a multiple of the base point (GX, GY) of secp256k1, where this multiple is l=3 (the degree of the isogeny; see the description in Appendix F.4). Note that this isogenous map (and its dual) primarily involves the evaluation of three fixed polynomials involving the x-coordinate, which takes roughly 10 modular multiplications (or less than 1% relative incremental cost compared to the cost of an elliptic curve scalar multiplication).
The parameters of the curve sec256k1 and the corresponding 3-isogenous curve sec256k1.m are as indicated below. Here, the domain parameters of the curve secp256k1 are as specified in [SEC2]; the domain parameters of secp256k1.m are "new".
General parameters (for all curves):
Weierstrass curve-specific parameters (for secp256k1):
Weierstrass curve-specific parameters (for secp256k1.m):
The isogeny and dual isogeny are both isogenies with degree l=3. Both are specified by a triple of polynomials u, v, and w (resp. u', v', and w') of degree 3, 3, and 1, respectively, with coefficients in GF(p). The coeffients of each of these polynomials are specified in Appendix L.4.1 (for the isogeny) and in Appendix L.4.2 (for the dual isogeny). For each polynomial in variable x, the coefficients are tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in hexadecimal format.
This section introduces curves related to Curve448 and explains their relationships.
The elliptic curve Curve448 is the Montgomery curve M_{A,B} defined over the prime field GF(p), with p:=2^{448}-2^{224}-1, where A:=156326 and B:=1. This curve has order h*n, where h=4 and where n is a prime 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 and where n1 is a prime number. For this curve, the base point is the point (Gu, Gv), where Gu=5 and where Gv is an even integer in the interval [0, p-1].
This curve has the same group structure as (is "isomorphic" to) the twisted Edwards curve E_{a,d} defined over GF(p), with as base point the point (Gx, Gy), where parameters are as specified in Appendix M.3. This curve is denoted as Ed448. For this curve, the parameter a is a square in GF(p), whereas d is not, so the group laws of Appendix C.3 apply.
The curve is also isomorphic to the elliptic curve W_{a,b} in short-Weierstrass form defined over GF(p), with as base point the point (GX, GY), where parameters are as specified in Appendix M.3. This curve is denoted as Wei448.
Each affine point (u, v) of Curve448 corresponds to the point (X, Y):=(u + A/3, v) of Wei448, while the point at infinity of Curve448 corresponds to the point at infinity of Wei448. (Here, we used the mappings of Appendix D.2 and that B=1.) Under this mapping, the base point (Gu, Gv) of Curve448 corresponds to the base point (GX, GY) of Wei448. The inverse mapping maps the affine point (X, Y) of Wei448 to (u, v):=(X - A/3, Y) of Curve448, while mapping the point at infinity of Wei448 to the point at infinity of Curve448. Note that this mapping involves a simple shift of the first coordinate and can be implemented via integer-only arithmetic as a shift of -(p-A)/3 for the isomorphic mapping and a shift of (p-A)/3 for its inverse, where delta=(p-A)/3 is the element of GF(p) defined by
(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 Ed448 is isomorphic to the curve Curve448, where the base point (Gu, Gv) of Curve448 corresponds to the base point (Gx,Gy) of Ed448 and where the point at infinity and the point (0,0) of order two of Curve448 correspond to, respectively, the point (0, 1) and the point (0, -1) of order two of Ed448 and where each other point (u, v) of Curve448 corresponds to the point (c*u/v, (u+1)/(u-1)) of Ed448, where c is the element of GF(p) defined by Appendix D.1 and normalized this using the mapping of Appendix F.1 (where the element s of that appendix is set to c above).) The inverse mapping from Ed448 to Curve448 is defined by mapping the point (0, 1) and the point (0, -1) of order two of Ed448 to, respectively, the point at infinity and the point (0,0) of order two of Curve448 and having each other point (x, y) of Ed448 correspond to the point ((y + 1)/(y - 1), c*(y + 1)/((y-1)*x)) of Curve448.
(Here, we used the mapping of
The curve Ed448 is isomorphic to the Weierstrass curve Wei448, where the base point (Gx, Gy) of Ed448 corresponds to the base point (GX,GY) of Wei448 and where the identity element (0,1) and the point (0,-1) of order two of Ed448 correspond to, respectively, the point at infinity O and the point (A/3, 0) of order two of Wei448 and where each other point (x, y) of Ed448 corresponds to the point (X, Y):=((y+1)/(y-1)+A/3, c*(y+1)/((y-1)*x)) of Wei448, where c was defined before. (Here, we used the mapping of Appendix D.3.) The inverse mapping from Wei448 to Ed448 is defined by mapping the point at infinity O and the point (A/3, 0) of order two of Wei448 to, respectively, the identity element (0,1) and the point (0,-1) of order two of Ed448 and having each other point (X, Y) of Wei448 correspond to the point (c*(X-A/3)/Y, (X-A/3+1)/(X-A/3-1)) of Ed448.
Note that these mappings can be easily realized if points are represented in projective coordinates, using a few field multiplications only, thus allowing switching between alternative curve representations with negligible relative incremental cost.
The parameters of the Montgomery curve and the corresponding isomorphic curves in twisted Edwards curve and short-Weierstrass form are as indicated below. Here, the domain parameters of the Montgomery curve Curve448 and of the twisted Edwards curve Ed448 are as specified in [RFC7748]; the domain parameters of Wei448 are "new".
IMPORTANT NOTE: the supposed base point of Ed448 specified in [RFC7748] is incorrect, since it has order 2*n, and - in the notation below - that point is the point (Gx,-Gy)=-(Gx, Gy)+(0,-1). The birational map in that document is also incorrect.
General parameters (for all curve models):
Montgomery curve-specific parameters (for Curve448):
Edwards curve-specific parameters (for Ed448):
Weierstrass curve-specific parameters (for Wei448):
This section introduces some further curves related to Curve448 and explains their relationships.
The Weierstrass curve Wei448 is isomorphic to the Weierstrass curve Wei448.1 defined over GF(p), with as base point the pair (G1X,G1Y), and isogenous to the Weierstrass curve Wei448.-3 defined over GF(p), with as base point the pair (G3X, G3Y), where parameters are as specified in Appendix N.3 and where the related mappings are as specified in Appendix N.2. The Edwards curve Ed448 is isogenous to the Edwards curve Edwards448 defined over GF(p), with as base point the pair (G1x,G1y), where parameters are as specified in Appendix N.3 and where the related mappings are as specified in Appendix N.2.
Each affine point (X, Y) of Wei448 corresponds to the point (X', Y'):=(X*s^2,Y*s^3) of Wei448.1, where s is the element of GF(p) defined by Appendix F.3.) Under this mapping, the base point (GX, GY) of Wei448 corresponds to the base point (G1X,G1Y) of Wei448.1. The inverse mapping maps the affine point (X', Y') of Wei448.1 to (X,Y):=(X'/s^2,Y'/s^3) of Wei448, while mapping the point at infinity O of Wei448.1 to the point at infinity O of Wei448. Note that this mapping (and its inverse) involves a modular multiplication of both coordinates with fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which can be precomputed.
while the point at infinity of Wei448 corresponds to the point at infinity of Wei448.1. (Here, we used the mapping of
Each affine point (X,Y) of Wei448 for which the Y-coordinate is nonzero (i.e., each point with order larger than two) corresponds to the point (X',Y'):=(X1*t^2,Y1*t^3) of Wei448.-3, where (X1,Y1)=(u(X)/w(X),Y*v(X)/w(X)^2), where u, v, and w are the polynomials with coefficients in GF(p) as defined in Appendix N.4.1 and where t is the element of GF(p) defined by Appendix F.4.) Under this isogenous mapping, the base point (GX,GY) of Wei448 corresponds to the base point (G3X,G3Y) of Wei448.-3. The dual isogeny maps the affine point (X',Y') of Wei448.-3 to the affine point (X,Y):=(u'(X1)/w'(X1),Y1*v'(X1)/w'(X1)^2) of Wei448, where (X1,Y1)=(X'/t^2,Y'/t^3) and where u', v', and w' are the polynomials with coefficients in GF(p) as defined in Appendix N.4.2, while mapping the point at infinity O of Wei448.-3 to the point at infinity O of Wei448. Under this dual isogenous mapping, the base point (G3X, G3Y) of Wei448.-3 corresponds to a multiple of the base point (GX, GY) of Wei448, where this multiple is l=2 (the degree of the isogeny; see the description in Appendix F.4). Note that this isogenous map (and its dual) primarily involves the evaluation of three fixed polynomials involving the x-coordinate, which takes only a few modular multiplications (less than 0.5% relative incremental cost compared to the cost of an elliptic curve scalar multiplication).
while the point at infinity and the point (A/3,0) of order two of Wei448 corresponds to the point at infinity of Wei448.-3. (Here, we used the isogenous mapping of
Each point (x1,y1) of Edwards448 corresponds to the point (x,y) of Ed448, where Appendix F.4. Under this isogenous mapping, the base point (G1x, G1y) of Edwards448 corresponds to the base point (Gx,Gy) of Ed448. The dual isogeny maps each point (x,y) of Ed448 to the point (x1,y1) of Edwards448, where Appendix F.4). Note that this isogenous map (and its dual) primarily involves the evaluation of three fixed polynomials, which takes only a few multiplications (less than 0.5% relative incremental cost compared to the cost of an elliptic curve scalar multiplication).
(Here, we used the 4-isogenous mapping of
Under this dual isogenous mapping, the base point (Gx, Gy) of Ed448 corresponds to a multiple of the base point (G1x, G1y) of Edwards448, where this multiple is l=4 (the degree of the isogeny; see the description in
The point (0,1) and the point (0,-1) of order two of Edwards448 correspond to, respectively, the point at infinity and the point (0,0) of order two of Curve448, while each other point (x1,y1) of Edwards448 corresponds to the point (u,v) of Curve448, where
Under this isogenous mapping, the base point (G1x, G1y) of Edwards448 corresponds to the base point (Gu,Gv) of Curve448. The dual isogeny maps both the point at infinity and the point (0,0) of order two of Curve448 to the point (0,1) of Edwards448, while each other point (u,v) of Curve448 corresponds to the point (x1,y1) of Edwards448, where
Under this dual isogenous mapping, the base point (Gu, Gv) of Curve448 corresponds to a multiple of the base point (G1x, G1y) of Edwards448, where this multiple is l=4 (the degree of the isogeny; see above).
The parameters of the Weierstrass curve with a=1 that is isomorphic with Wei448 and the parameters of the Weierstrass curve with a=-3 that is isogenous with Wei448 are as indicated below. Both domain parameter sets can be exploited directly to derive more efficient point addition formulae, should an implementation facilitate this. The domain parameters of the twisted Edwards curve Edwards448 are as specified in [RFC7748].
General parameters: same as for Wei448 (see Appendix M.3)
Weierstrass curve-specific parameters (for Wei448.1, i.e., with a=1):
Weierstrass curve-specific parameters (for Wei448.-3, i.e., with a=-3):
Edwards curve-specific parameters (for Edwards448):
The isogeny and dual isogeny are both isogenies with degree l=2. Both are specified by a triple of polynomials u, v, and w (resp. u', v', and w') of degree 2, 2, and 1, respectively, with coefficients in GF(p). The coeffients of each of these polynomials are specified in Appendix N.4.1 (for the isogeny) and in Appendix N.4.2 (for the dual isogeny). For each polynomial in variable x, the coefficients are tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in hexadecimal format.
We present some examples of computations using the curves introduced in this document. In each case, we indicate the values of P, k*P, and (k+1)*P, where P is a fixed multiple (here: 2019) of the base point of the curve in question and where the private key k is the integer
Pm=(u, v), k*Pm=(u1, v1), and (k+1)*Pm=(u2, v2) with Curve448:
As suggested in Appendix C.2, the v-coordinate of k*Pm can be indirectly computed from the u-coordinates of Pm, k*Pm, and (k+1)*Pm, and the v-coordinate of Pm, which allows computation of the entire point k*Pm (and not just its u-coordinate) if k*Pm is computed using the Montgomery ladder (as, e.g., [RFC7748] recommends), since that algorithm computes both u1 and u2 and the v-coordinate of the point Pm may be available from context.
The representation of k and the compressed representations of Pm and k*Pm in tight LSB/msb-order are given by Appendix H.2 and Appendix I for further detail on (squeezed) point compression.
where the leftmost bit of the rightmost octet indicates the parity of the v-coordinate of the point of Curve448 in question (which, in this case, are both one, since v and v1 are odd). See
The scalar representation and (squeezed) point representation illustrated above are consistent with the representations specified in [RFC7748], except that in [RFC7748] only an affine point's u-coordinate is represented (i.e., the v-coordinate of any point is always implicitly assumed to have an even value) and that the representation of the point at infinity is not specified. (Note that due to the bit-size of the prime p, the lossless representation requires an additional octet compared to the lossy representation without v-coordinate.) Another difference is that [RFC7748] allows non-unique representations of some elements of GF(p), whereas our representation conventions do not (since tight).
A randomized representation (t1, t2) of the point k*Pm in tight LSB/msb order is given by Appendix K.5 and uses the mapping of Appendix K.3.2 with the default square root function.
where this representation is defined in
Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Ed448:
The representation of k and the compressed representations of Pe and k*Pe in tight LSB/lsb-order are given by Appendix H.3 and Appendix I for further detail on (squeezed) point compression.
where the rightmost bit of the rightmost octet indicates the parity of the x-coordinate of the point of Ed448 in question (which, in this case, are both one, since x and x1 are odd). See
The scalar representation and (squeezed) point representation illustrated above are fully consistent with the representations specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032] requires unique representations of all elements of GF(p).
A randomized representation (t1, t2) of the point k*Pe in tight LSB/lsb order is given by Appendix K.5 and uses the mapping of Appendix K.3.3 with the default square root function and underlying isomorphic mapping between Ed448 and Curve448 of Appendix M.2.
where this representation is defined in
Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei448:
The representation of k and the compressed representations of Pw and k*Pw in tight MSB/msb-order are given by Appendix H.1 and Appendix I for further detail on (squeezed) point compression.
where the leftmost bit of the leftmost octet indicates the parity of the Y-coordinate of the point of Wei448 in question (which, in this case, are both one, since Y and Y1 are odd). See
The scalar representation is consistent with the representations specified in [SEC1]; the (squeezed) point representation illustrated above is "new". For completeness, we include a SEC1-consistent representation of the point Pw in affine format and in compressed format below.
The SEC1-compliant affine representation of the point Pw in tight MSB/msb-order is given by
whereas the SEC1-compliant compressed representation of the point Pw in tight MSB/msb-order is given by
The SEC1-compliant uncompressed format aff(Pw) of an affine point Pw corresponds to the right-concatenation of its X- and Y-coordinates, each in tight MSB/msb-order, prepended by the string 0x04, where the reverse procedure is uniquely defined, since elements of GF(p) have a unique fixed-size representation. The (squeezed) compressed format repr(Pw) corresponds to the SEC1-compliant compressed format by extracting the parity bit t from the leftmost bit of the leftmost octet of repr(Pw), and replacing this leftmost octet with 0x02 or 0x03, depending on whether t=0 or t=1, respectively, where the reverse procedure is uniquely defined. For further details, see [SEC1]. Note that, due to the bit-size of the prime p, the squeezed compressed format repr(Pw) and the SEC1-compliant compressed format compr(Pw) have the same size.
A randomized representation (t1, t2) of the point k*Pw in tight MSB/msb order is given by Appendix K.5 and uses the mapping of Appendix K.3.1 with the default square root function.
where this representation is defined in
Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei448.-3:
The representation of k and the compressed representations of Pw3 and k*Pw3 in tight MSB/msb-order are given by Appendix H.1 and Appendix I for further detail on (squeezed) point compression.
where the leftmost bit of the leftmost octet indicates the parity of the Y-coordinate of the point of Wei448.-3 in question (which, in this case, are one and zero, respectively, since Y is odd and Y1 is even). See
A randomized representation (t1, t2) of the point k*Pw3 in tight MSB/msb order is given by Appendix K.5 and uses the mapping of Appendix K.3.1 with the default square root function.
where this representation is defined in
Pe1=(x, y), k*Pe1=(x1, y1), and (k+1)*Pe1=(x2, y2) with Edwards448:
The representation of k and the compressed representations of Pe1 and k*Pe1 in tight LSB/lsb-order are given by Appendix H.3 and Appendix I for further detail on (squeezed) point compression.
where the rightmost bit of the rightmost octet indicates the parity of the x-coordinate of the point of Edwards448 in question (which, in this case, are both one, since x and x1 are odd). See
The scalar representation and (squeezed) point representation illustrated above are fully consistent with the representations specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032] requires unique representations of all elements of GF(p).
A randomized representation (t1, t2) of the point k*Pe1 in tight LSB/lsb order is given by Appendix K.5 and uses the mapping of Appendix K.3.3 with the default square root function and underlying 4-isogenous mapping between Edwards448 and Curve448 of Appendix N.2.
where this representation is defined in