 1/draftietflwigcurverepresentations02.txt 20190323 19:13:13.113018743 0700
+++ 2/draftietflwigcurverepresentations03.txt 20190323 19:13:13.225021477 0700
@@ 1,18 +1,18 @@
lwig R. Struik
InternetDraft Struik Security Consultancy
Intended status: Informational March 11, 2019
Expires: September 12, 2019
+Intended status: Informational March 23, 2019
+Expires: September 24, 2019
Alternative Elliptic Curve Representations
 draftietflwigcurverepresentations02
+ draftietflwigcurverepresentations03
Abstract
This document specifies how to represent Montgomery curves and
(twisted) Edwards curves as curves in shortWeierstrass form and
illustrates how this can be used to carry out elliptic curve
computations using existing implementations of, e.g., ECDSA and ECDH
using NIST prime curves.
Requirements Language
@@ 30,115 +30,124 @@
InternetDrafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as InternetDrafts. The list of current Internet
Drafts is at https://datatracker.ietf.org/drafts/current/.
InternetDrafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use InternetDrafts as reference
material or to cite them other than as "work in progress."
 This InternetDraft will expire on September 12, 2019.
+ This InternetDraft will expire on September 24, 2019.
Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/licenseinfo) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
 1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 3
+ 1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 4
2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 4
3. Use of Representation Switches . . . . . . . . . . . . . . . 4
4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 5
4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 6
4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 6
 4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 6
+ 4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 7
5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6. Security Considerations . . . . . . . . . . . . . . . . . . . 8
 7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 8
 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8
 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 9
 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 9
 10.1. Normative References . . . . . . . . . . . . . . . . . . 9
 10.2. Informative References . . . . . . . . . . . . . . . . . 10
 Appendix A. Some (nonBinary) Elliptic Curves . . . . . . . . . 10
 A.1. Curves in shortWeierstrass Form . . . . . . . . . . . . 10
 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 11
 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 11
 Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 11
 B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 11
 B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 13
 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 14
 C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 14
 C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 15
 C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 15
 Appendix D. Relationship Between Curve Models . . . . . . . . . 16
+ 7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 9
+ 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9
+ 8.1. COSE Elliptic Curves Registration . . . . . . . . . . . . 9
+ 8.2. COSE Algorithms Registration (1/2) . . . . . . . . . . . 10
+ 8.3. COSE Algorithms Registration (2/2) . . . . . . . . . . . 10
+ 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11
+ 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 11
+ 10.1. Normative References . . . . . . . . . . . . . . . . . . 11
+ 10.2. Informative References . . . . . . . . . . . . . . . . . 12
+ Appendix A. Some (nonBinary) Elliptic Curves . . . . . . . . . 13
+ A.1. Curves in shortWeierstrass Form . . . . . . . . . . . . 13
+ A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 13
+ A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 13
+ Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 14
+ B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 14
+ B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 15
+ Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 16
+ C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 16
+ C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 17
+ C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 18
+ Appendix D. Relationship Between Curve Models . . . . . . . . . 19
D.1. Mapping between Twisted Edwards Curves and Montgomery
 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 16
 D.2. Mapping between Montgomery Curves and Weierstrass Curves 17
+ Curves . . . . . . . . . . . . . . . . . . . . . . . . . 19
+ D.2. Mapping between Montgomery Curves and Weierstrass Curves 20
D.3. Mapping between Twisted Edwards Curves and Weierstrass
 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 18
 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 18
 E.1. Curve Definition and Alternative Representations . . . . 18
 E.2. Switching between Alternative Representations . . . . . . 19
 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 20
 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 22
 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 22
 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 23
 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 24
 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 25
 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 26
 G.1. Further Alternative Representations . . . . . . . . . . . 26
 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 26
 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 27
 Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 29
 H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 29
 H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 29
 H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 31
 H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 34
 H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 35
 H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 35
 H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 37
 H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 40
 Appendix I. Point Compression . . . . . . . . . . . . . . . . . 41
 I.1. Point Compression for Weierstrass Curves . . . . . . . . 42
 I.2. Point Compression for Montgomery Curves . . . . . . . . . 42
 I.3. Point Compression for Twisted Edwards Curves . . . . . . 43
 Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 43
 J.1. Conversion between Bit Strings and Integers . . . . . . . 43
+ Curves . . . . . . . . . . . . . . . . . . . . . . . . . 21
+ Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 21
+ E.1. Curve Definition and Alternative Representations . . . . 21
+ E.2. Switching between Alternative Representations . . . . . . 21
+ E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 23
+ Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 25
+ F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 25
+ F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 26
+ F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 26
+ F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 27
+ Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 29
+ G.1. Further Alternative Representations . . . . . . . . . . . 29
+ G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 29
+ G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 30
+ Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 31
+ H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 31
+ H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 31
+ H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 34
+ H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 37
+ H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 38
+ H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 38
+ H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 40
+ H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 43
+ Appendix I. Point Compression . . . . . . . . . . . . . . . . . 44
+ I.1. Point Compression for Weierstrass Curves . . . . . . . . 44
+ I.2. Point Compression for Montgomery Curves . . . . . . . . . 45
+ I.3. Point Compression for Twisted Edwards Curves . . . . . . 46
+ Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 46
+ J.1. Conversion between Bit Strings and Integers . . . . . . . 47
J.2. Conversion between Octet Strings and Integers (OS2I,
 I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 44
+ I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 47
J.3. Conversion between Octet Strings and Bit Strings (BS2OS,
 OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 44
+ OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 48
J.4. Conversion between Field Elements and Octet Strings
 (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 44
 J.5. Ordering Conventions . . . . . . . . . . . . . . . . . . 45
 Appendix K. Representations for Curve25519 Family Members . . . 46
 K.1. Wei25519 . . . . . . . . . . . . . . . . . . . . . . . . 46
 Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 46
 L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 46
 L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 47
 L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 47
 L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 47
 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 47
+ (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 48
+ J.5. Conversion between Elements of Z mod n and Octet Strings
+ (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 48
+ J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 49
+ Appendix K. Representation Examples Curve25519 Family Members . 50
+ K.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 50
+ K.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 52
+ K.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 53
+ K.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 55
+ K.5. Example with Wei25519.3 . . . . . . . . . . . . . . . . 56
+ Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 58
+ L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 58
+ L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 58
+ L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 58
+ L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 58
+ Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 59
1. Fostering Code Reuse with New Elliptic Curves
It is wellknown that elliptic curves can be represented using
different curve models. Recently, IETF standardized elliptic curves
that are claimed to have better performance and improved robustness
against "real world" attacks than curves represented in the
traditional "short" Weierstrass model. This document specifies an
alternative representation of points of Curve25519, a socalled
Montgomery curve, and of points of Edwards25519, a socalled twisted
@@ 204,44 +213,52 @@
Alternative curve representations can, therefore, be used in any
cryptographic scheme that involves computations on publicprivate key
pairs, where implementations may carry out computations on the
corresponding object for the isomorphic or isogenous curve and
convert the results back to the original curve (where, in case this
involves an lisogeny, one has to take into account the factor l).
This includes use with ellipticcurve based signature schemes and key
agreement and key transport schemes.
+ For some examples of curve computations on each of the curves
+ specified in Appendix E.3 and Appendix G.3, see Appendix K.
+
4. Examples
4.1. Implementation of X25519
RFC 7748 [RFC7748] specifies the use of X25519, a cofactor Diffie
Hellman key agreement scheme, with instantiation by the Montgomery
curve Curve25519. This key agreement scheme was already specified in
Section 6.1.2.2 of NIST SP 80056a [SP80056a] for elliptic curves
in short Weierstrass form. Hence, one can implement X25519 using
existing NIST routines by (1) representing a point of the Montgomery
curve Curve25519 as a point of the Weierstrass curve Wei25519; (2)
instantiating the cofactor DiffieHellman key agreement scheme of
the NIST specification with the resulting point and Wei25519 domain
parameters; (3) representing the key resulting from this scheme
(which is a point of the curve Wei25519 in Weierstrass form) as a
point of the Montgomery curve Curve25519. The representation change
can be implemented via a simple wrapper and involves a single modular
addition (see Appendix D.2). Using this method has the additional
advantage that one can reuse the publicprivate key pair routines,
domain parameter validation, and other checks that are already part
 of the NIST specifications. Note: at this point, it is unclear
 whether this implies that a FIPSaccredited module implementing co
 factor DiffieHellman for, e.g., P256 would also extend this
 accreditation to X25519.
+ of the NIST specifications. A NISTcompliant version of cofactor
+ DiffieHellman key agreement (denoted by ECDH25519) results if one
+ keeps inputs (key contributions) and outputs (shared key) in the
+ shortWeierstrass 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 cofactor DiffieHellman for, e.g.,
+ P256 would also extend this accreditation to X25519.
4.2. Implementation of Ed25519
RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature
scheme, with instantiation by the twisted Edwards curve Edwards25519.
One can implement the computation of the ephemeral key pair for
Ed25519 using an existing Montgomery curve implementation by (1)
generating a publicprivate key pair (k, R':=k*G') for Curve25519;
(2) representing this publicprivate key as the pair (k, R:=k*G) for
Ed25519. As before, the representation change can be implemented via
@@ 254,34 +271,34 @@
hereof (which uses the vcoordinate of the base point of Curve25519
as well). For details, see Appendix C.1.
4.3. Specification of ECDSA25519
FIPS Pub 1864 [FIPS1864] specifies the signature scheme ECDSA and
can be instantiated not just with the NIST prime curves, but also
with other Weierstrass curves (that satisfy additional cryptographic
criteria). In particular, one can instantiate this scheme with the
Weierstrass curve Wei25519 and the hash function SHA256, where an
 implementation may generate a publicprivate key pair for Wei25519 by
 (1) internally carrying out these computations on the Montgomery
 curve Curve25519, the twisted Edwards curve Edwards25519, or even the
 Weierstrass curve Wei25519.3 (with hardcoded a=3 domain parameter);
 (2) representing the result as a key pair for the curve Wei25519.
 Note that, in either case, one can implement these schemes with the
 same representation conventions as used with existing NIST
+ implementation may generate an ephemeral publicprivate key pair for
+ Wei25519 by (1) internally carrying out these computations on the
+ Montgomery curve Curve25519, the twisted Edwards curve Edwards25519,
+ or even the Weierstrass curve Wei25519.3 (with hardcoded a=3 domain
+ parameter); (2) representing the result as a key pair for the curve
+ Wei25519. Note that, in either case, one can implement these schemes
+ with the same representation conventions as used with existing NIST
specifications, including bit/byteordering, compression functions,
and thelike. This allows generic implementations of ECDSA with the
hash function SHA256 and with the NIST curve P256 or with the curve
 Wei25519 specified in this draft to use the same implementation
 (instantiated with, respectively, the NIST P256 elliptic curve
 domain parameters or with the domain parameters of curve Wei25519
 specified in Appendix E).
+ Wei25519 specified in this specification to reuse the same
+ implementation (instantiated with, respectively, the NIST P256
+ elliptic curve domain parameters or with the domain parameters of
+ curve Wei25519 specified in Appendix E).
4.4. Other Uses
Any existing specification of cryptographic schemes using elliptic
curves in Weierstrass form and that allows introduction of a new
elliptic curve (here: Wei25519) is amenable to similar constructs,
thus spawning "offspring" protocols, simply by instantiating these
using the new curve in "short" Weierstrass form, thereby allowing
code and/or specifications reuse and, for implementations that so
desire, carrying out curve computations "under the hood" on
@@ 313,78 +330,158 @@
2. Representation conventions. While elliptic curve computations
are carriedout in a field GF(q) and, thereby, involve large
integer arithmetic, these integers are represented as bit and
bytestrings. Here, [RFC8032] uses leastsignificantbyte
(LSB)/leastsignificantbit (lsb) conventions, whereas [RFC7748]
uses LSB/mostsignificantbit (msb) conventions, and where most
other cryptographic specifications, including NIST SP80056a
[SP80056a], FIPS Pub 1864 [FIPS1864], and ANSI X9.622005
[ANSIX9.62] use MSB/msb conventions. Since each pair of
 conventions is different (see Appendix J for details), this does
 necessitate bit/byte representation conversions;
+ conventions is different (see Appendix J for details and
+ Appendix K for examples), this does necessitate bit/byte
+ representation conversions;
3. Domain parameters. 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
("Jacobianfriendly"). For those implementations, including the
curve Wei25519 as a potential vehicle for offering support for
the CFRG curves Curve25519 and Edwards25519 is not possible,
since not of the required form. Instead, one has to implement
Wei25519.3 and include code that implements the isogeny and dual
isogeny from and to Wei25519. This isogeny has degree l=47 and
requires roughly 9kB of storage for isogeny and dualisogeny
computations (see the tables in Appendix H). Note that storage
would have reduced to a single 64byte table if only the curve
would have been generated so as to be isomorphic to a Weierstrass
curve with hardcoded a=3 parameter (this corresponds to l=1).
 Note: an example of such a curve is the Montgomery curve M_{A,B}
 over GF(p) with p=2^25519, B=1, and A=1410290 or (if one wants
 the base point to still have ucoordinate u=9) A=3960846. In
 either case, the resulting curve has the same cryptographic
 properties as Curve25519 and the same performance (since A is a
 3byte integer as is the case with the domain parameter A=486662
 used with Curve25519), while being "Jacobianfriendly" by design.
+
+ NOTE: An example of a Montgomery curve defined over the same
+ field as Curve25519 that is isomorphic to a Weierstrass curve
+ with hardcoded a=3 parameter is the Montgomery curve M_{A,B}
+ with B=1 and A=1410290 (or, if one wants the base point to still
+ have ucoordinate u=9, with B=1 and A=3960846). In either case,
+ the resulting curve has the same cryptographic properties as
+ Curve25519 and the same performance (which relies on A being a
+ 3byte integer, as is the case with the domain parameter A=486662
+ of Curve25519, and using the same special prime p=2^25519),
+ while at the same time being "Jacobianfriendly" by design.
6. Security Considerations
The different representations of elliptic curve points discussed in
this document are all obtained using a publicly known transformation,
which is either an isomorphism or a lowdegree isogeny. It is well
known that an isomorphism maps elliptic curve points to equivalent
mathematical objects and that the complexity of cryptographic
problems (such as the discrete logarithm problem) of curves related
via a lowdegree isogeny are tightly related. Thus, the use of these
 techniques does not negatively impact cryptographic security.
+ techniques does not negatively impact cryptographic security of
+ elliptic curve operations.
As to implementation security, reusing existing highquality code or
generic implementations that have been carefully designed to
withstand implementation attacks for one curve model may allow a more
economical way of development and maintenance than providing this
same functionality for each curve model separately (if multiple curve
models need to be supported) and, otherwise, may allow a more gradual
migration path, where one may initially use existing and accredited
chipsets that cater to the predominant curve model used in practice
for over 15 years.
+ 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
+ shortWeierstrass form and in uncompressed tight MSB/msb format).
+
+ To prevent crossprotocol 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 intraprotocol crossinstantiation attacks, ephemeral
+ private keys MUST NOT be reused between instantiations of ECDSA25519.
+
7. Privacy Considerations
The transformations between different curve models described in this
document are publicly known and, therefore, do not affect privacy
provisions.
8. IANA Considerations
 An object identifier is requested for Wei25519 and ECDSA25519, using
 the representation conventions in this document.
+ An object identifier is requested for curve Wei25519 and its use with
+ ECDSA and cofactor ECDH, using the representation conventions of
+ this document.
+
+ There is *currently* no further IANA action required for this
+ document. New object identifiers would be required in case one
+ wishes to specify one or more of the "offspring" protocols
+ exemplified in Section 4.
+
+8.1. COSE Elliptic Curves Registration
+
+ This section registers the following value in the IANA "COSE Elliptic
+ Curves" registry [IANA.COSE.Curves].
+
+ Name: Wei25519;
+
+ Value: TBD (Requested value: 1);
+
+ Key Type: EC2 or OKP (where OKP uses the squeezed MSB/msb
+ representation of this specification);
+
+ Description: shortWeierstrass curve Wei25519;
+
+ Reference: Appendix E.3 of this specification;
+
+ Recommended: Yes.
+
+ (Note that The "kty" value for Wei25519 may be "OKP" or "EC2".)
+
+8.2. COSE Algorithms Registration (1/2)
+
+ This section registers the following value in the IANA "COSE
+ Algorithms" registry [IANA.COSE.Algorithms].
+
+ Name: ECDSA25519;
+
+ Value: TBD (Requested value: 1);
+
+ Description: ECDSA w/ SHA256 and curve Wei25519;
+
+ Reference: Section 4.3 of this specification;
+
+ Recommended: Yes.
+
+8.3. COSE Algorithms Registration (2/2)
+
+ This section registers the following value in the IANA "COSE
+ Algorithms" registry [IANA.COSE.Algorithms].
+
+ Name: ECDH25519;
+
+ Value: TBD (Requested value: 2);
+
+ Description: NISTcompliant cofactor DiffieHellman w/ curve
+ Wei25519 and key derivation function HKDF SHA256;
+
+ Reference: Section 4.1 of this specification (for key derivation,
+ see Section 11.1 of [RFC8152]);
+
+ Recommended: Yes.
9. Acknowledgements
Thanks to Nikolas Rosener for discussions surrounding implementation
details of the techniques described in this document and to Phillip
HallamBaker for triggering inclusion of verbiage on the use of
Montgomery ladders with recovery of the ycoordinate. Thanks to
Stanislav Smyshlyaev for his careful review.
10. References
@@ 397,20 +494,30 @@
Signature Algorithm (ECDSA)", American National Standard
for Financial Services, Accredited Standards Committee X9,
Inc, Anapolis, MD, 2005.
[FIPS1864]
FIPS 1864, "Digital Signature Standard (DSS), Federal
Information Processing Standards Publication 1864", US
Department of Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, July 2013.
+ [IANA.COSE.Algorithms]
+ IANA, "COSE Algorithms", IANA,
+ https://www.iana.org/assignments/cose/
+ cose.xhtml#algorithms.
+
+ [IANA.COSE.Curves]
+ IANA, "COSE Elliptic Curves", IANA,
+ https://www.iana.org/assignments/cose/cose.xhtml#elliptic
+ curves.
+
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
.
[RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography
(ECC) Brainpool Standard Curves and Curve Generation",
RFC 5639, DOI 10.17487/RFC5639, March 2010,
.
@@ 421,25 +528,32 @@
[RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
for Security", RFC 7748, DOI 10.17487/RFC7748, January
2016, .
[RFC8032] Josefsson, S. and I. Liusvaara, "EdwardsCurve 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,
+ .
+
+ [SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0",
+ Standards for Efficient Cryptography, , June 2009.
+
[SP80056a]
NIST SP 80056a, "Recommendation for PairWise Key
Establishment Schemes Using Discrete Log Cryptography,
 Revision 2", US Department of Commerce/National Institute
 of Standards and Technology, Gaithersburg, MD, June 2013.
+ Revision 3", US Department of Commerce/National Institute
+ of Standards and Technology, Gaithersburg, MD, April 2018.
10.2. Informative References
[ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in
Cryptography", Cambridge University Press, Lecture Notes
Series 265, July 1999.
[ECCIsogeny]
E. Brier, M. Joye, "Fast Point Multiplication on Elliptic
Curves through Isogenies", AAECC, Lecture Notes in
@@ 1967,20 +2082,30 @@
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 Ycoordinate 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.
+ If the Weierstrass curve W_{a,b} has a point of order two, we extend
+ the definition of the point compression function to all points of the
+ curve, by associating the (nonaffine) point at infinity O with the
+ ordered pair compr(O):=(X,1), where (X,0) is any point of order two,
+ and recover this point accordingly. (Note that this corresponds to
+ the case alpha=0 and t=1 above.) In this case, the point at infinity
+ O can be represented by any ordered pair (X, 1) of elements of GF(q),
+ where (X,0) is any point of order two. Note that this ordered pair
+ does not satisfy the defining equation of the curve in question.
+
I.2. Point Compression for Montgomery Curves
If P:=(u, v) is an affine point of the Montgomery curve M_{A,B}
defined over the field GF(q), then so is P:=(u, v). Since the
defining equation B*v^2=u^3+A*u^2+u has at most two solutions with
fixed uvalue, one can represent P by its ucoordinate 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 ucoordinate
alone, since v=0 and has fixed parity. Conversely, given the ordered
@@ 1992,20 +2117,28 @@
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 vcoordinate
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 (nonaffine) 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.
+
I.3. Point Compression for Twisted Edwards Curves
If P:=(x, y) is an affine point of the twisted Edwards curve E_{a,d}
defined over the field GF(q), then so is P:=(x, y). Since the
defining equation a*x^2+y^2=1+d*x^2*y^2 has at most two solutions
with fixed yvalue, one can represent P by its ycoordinate 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
ycoordinate alone, since x=0 and has fixed parity. Conversely,
@@ 2017,33 +2150,53 @@
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 xcoordinate 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} (subject to the Note in
+ Appendix C.3). Here, the identity element O:=(0,1) is associated
+ with the compressed point compr(O):=(0,1).
+
Appendix J. Data Conversions
The string over some alphabet S consisting of the symbols x_{l1},
x_{l2}, ..., x_1, x_0 (each in S), in this order, is denoted by
str(x_{l1}, x_{l2}, ..., 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 rightconcatenation 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:=XY. The string X is called a
+ prefix of Z; the string Y a postfix. The tprefix of a string Z of
+ length l is its unique prefix X of length t; the tpostfix its unique
+ postfix Y of length t (where we define these notions as well if t is
+ outside the interval [0,l]: a tprefix or tpostfix is the empty
+ string if t is negative and is the entire string Z if t is larger
+ than l). Sometimes, a tprefix of a string Z is denoted by trunc
+ left(Z,t); a tpostfix by truncright(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 XY.
+
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.
+ underlying alphabet, as are the operations in the previous paragraph.
J.1. Conversion between Bit Strings and Integers
There is a 11 correspondence between bit strings of length l and the
integers in the interval [0, 2^l), where the bit string
X:=str(x_{l1}, x_{l2}, ..., x_1, x_0) corresponds to the integer
x:=x_{l1}*2^{l1} + x_{l2}*2^{l2} + ... + 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
@@ 2098,21 +2251,47 @@
to octet strings and the inverse mapping are only uniquely defined if
each octet string X_i has the same fixed size (e.g., the smallest
integer l so that 256^l >= p) and if all integers are reduced modulo
p. If so, the latter representation is called tight if l is minimal
so that 256^l >= p. This defines the mapping FE2OS(x,l) from field
elements to octet strings and the mapping OS2FE(X,l) from octet
strings to field elements, where the underlying field is implicit and
assumed to be known from context. In this case, the octet string has
length l*m.
J.5. Ordering Conventions
+J.5. Conversion between Elements of Z mod n and Octet Strings (ZnE2OS,
+ OS2ZnE)
+
+ There is a 11 correspondence between elements of a fixed set Z(n) of
+ integers modulo n and integers in the interval [0,n), where each
+ element x can be uniquely represented by the octet string
+ corresponding to the integer x modulo n according to the mapping of
+ Appendix J.2 above. Note that both the mapping from elements of Z(n)
+ to octet strings and the inverse mapping 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 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.
+
+ 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 are useful, e.g., when
+ encoding the modulus n of RSA (or elements of any other nonprime set
+ Z(n), for that matter).
+
+J.6. Ordering Conventions
One can consider various representation functions, depending on bit
ordering and octetordering 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_{l1}, x_{l2},
..., x_1, x_0), its reverse is the bit string [octet string]
X':=rev(X):=str(x_0, x_1, ..., x_{l2}, x_{l1}).
@@ 2139,65 +2318,401 @@
str(X_{0}, X_{1}, ..., X_{l2}, X_{l1}).
Thus, the 2octet 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 nonambiguous.
+ representations (as defined above) are nonambiguous. (Note, in
+ particular, that tightness implies that elements of GF(q) are always
+ uniquely represented.)
Appendix K. Representations for Curve25519 Family Members
+ Note that elements of a prime field GF(p), where p is a 255bit prime
+ number, have a tight representation as a 32byte 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 I) 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 on certain positions, which can be used to squeezein
+ additional information. Further details are out of scope.
K.1. Wei25519
+Appendix K. Representation Examples Curve25519 Family Members
 The representation of integers, field elements, affine points, and
 compressed points for the curve Wei25519 are as indicated below.
 Representations are relative to the prime field GF(p), where
 p=2^25519 is one of the general domain parameters of Appendix E.3.
+ 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
 Each field element z of GF(p) is represented as the octet string
 FE2OS(z), where one uses one the MSB/msb conventions and tight
 representation, as specified in Appendix J. In particular, each
 element of GF(p) is represented as a 32byte octet string, which 
 when viewed as a bit string  has the leftmost bit position set to 0.
+ k 45467544759954639344191351164156560595299236761702065033670739677
+ 691372543056
 Each affine point (X, Y) of Wei25519 is represented as the
 rightconcatenation of the 32byte octet representations for the x
 and ycoordinate of this point according to the conventions above,
 i.e., it is represented as the 64byte octet string str(FE2OS(X),
 FE2OS(Y)).
+ (=0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3
+ c08d5abd 15e29c50).
 For each compressed point (X, t) of Wei25519, the parity bit t (which
 is an element of the field GF(2)), is represented as a 1bit bit
 string, whereas the xcoordinate X (which is an element of GF(p)), is
 represented as a 32byte octet string FE2OS(X). The result is
 "squeezed", by superimposing the 1bit representation of t on the
 leftmost (unused) bitposition of the 32byte octet representation of
 X.
+K.1. Example with Curve25519
 Each integer in the interval [0,n1] is viewed as an element of the
 prime field GF(n) and represented using MSB/msb conventions and a
 tight representation. In particular, each element of GF(n) is
 represented as a 32byte octet string, which  when viewed as a bit
 string  has the lefmost three bit positions set to 0.
+ Pm=(u, v), k*Pm=(u1, v1), and (k+1)*Pm=(u2, v2) with Curve25519:
+
+ u 53025657538808013645618620393754461319535915376830819974982289332
+ 088255623750
+
+ (=0x753b7566 df35d574 4734142c 9abf931c ea290160 aa75853c
+ 7f972467 b7f13246).
+
+ v 53327798092436462013048370302019946300826511459161905709144645521
+ 233690313086
+
+ (=0x75e676ce deee3b3c 12942357 22f1d884 ac06de07 330fb07b
+ ae35ca26 df75417e).
+
+ u1 42039618818474335439333192910143029294450651736166602435248528442
+ 691717668056
+
+ (=0x5cf194be f0bdd6d6 be58e18a 8f16740a ec25f4b0 67f7980a
+ 23bb6468 88bb9cd8).
+
+ v1 76981661982917351630937517222412729130882368858134322156485762195
+ 67913357634
+
+ (=0x110501f6 1dff511e d6c4e9b9 bfd5acbe 8bf043b8 c3e381dd
+ f5771306 479ad142).
+
+ u2 34175116482377882355440137752573651838273760818624557524643126101
+ 82464621878
+
+ (=0x078e3e38 41c3e0d0 373e5454 ecffae33 2798b10a 55c72117
+ 62629f97 f1394d36).
+
+ v2 43046985853631671610553834968785204191967171967937842531656254539
+ 962663994648
+
+ (=0x5f2bbb06 f7ec5953 2c2a1a62 21124585 1d2682e0 cc37307e
+ fbc17f7f 7fda8518).
+
+ As suggested in Appendix C.2, the vcoordinate of k*Pm can be
+ indirectly computed from the ucoordinates of Pm, k*Pm, and (k+1)*Pm,
+ and the vcoordinate of Pm, which allows computation of the entire
+ point k*Pm (and not just its ucoordinate) if k*Pm is computed using
+ the Montgomery ladder (as, e.g., [RFC7748] recommends), since that
+ algorithm computes both u1 and u2 and the vcoordinate 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/msborder are given by
+
+ repr(k) 0x509ce215 bd5a8dc0 c3328c77 5dc6f59c 4d4915f9 e4bf5d0d
+ c2e583cd e6b78564
+
+ repr(Pm) 0x4632f1b7 6724977f 3c8575aa 600129ea 1c93bf9a 2c143447
+ 74d535df 66753b75;
+
+ repr(k*Pm) 0xd89cbb88 6864bb23 0a98f767 b0f425ec 0a74168f 8ae158be
+ d6d6bdf0 be94f15c,
+
+ where the leftmost bit of the rightmost octet indicates the parity of
+ the vcoordinate of the point of Curve25519 in question (which, in
+ this case, are both zero, since v and v1 are even). See Appendix I.2
+ and Appendix J for further detail on (squeezed) point compression.
+
+ 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
+ ucoordinate is represented (i.e., the vcoordinate 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 nonunique representations of
+ some elements of GF(p), whereas our representation conventions do not
+ (since tight).
+
+K.2. Example with Edwards25519
+
+ Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Edwards25519:
+
+ x 25301662348702136092602268236183361085863932475593120475382959053
+ 365387223252
+
+ (=0x37f03bc0 1070ed12 d3218f8b ba1abb74 fd6b94eb 62033d09
+ 83851e21 d6a460d4).
+
+ y 54434749145175762798550436656748568411099702168121592090608501578
+ 942019473360
+
+ (=0x7858f9e7 6774ed8e 23d614d2 36715fc7 56813b02 9aa13c18
+ 960705c5 b3a30fd0).
+
+ x1 42966967796585460733861724865699548279978730460766025087444502812
+ 416557284873
+
+ (=0x5efe7124 465b5bdb b364bb3e e4f106e2 18d59b36 48f4fe83
+ c11afc91 785d7e09).
+
+ y1 46006463385134057167371782068441558951541960707376246310705917936
+ 352255317084
+
+ (=0x65b6bc49 985badaf bc5fdd96 fb189502 35d5effd 540b439d
+ 60508827 80bc945c).
+
+ x2 42629294840915692510487991904657367226900127896202625319538173473
+ 104931719808
+ (=0x5e3f536a 3be2364a 1fa775a3 5f8f65ae 93f4a89d 81a04a2e
+ 87783748 00120a80).
+
+ y2 29739282897206659585364020239089516293417836047563355347155817358
+ 737209129078
+
+ (=0x41bfd66e 64bdd801 c581a720 f48172a8 187445fa 350924a2
+ c92c791e 38d57876).
+
+ The representation of k and the compressed representations of Pe and
+ k*Pe in tight LSB/lsborder are given by
+
+ repr(k) =0x0a3947a8 bd5ab103 c34c31ee ba63af39 b292a89f 27fdbab0
+ 43a7c1b3 67eda126;
+
+ repr(Pe) =0x0bf0c5cd a3a0e069 183c8559 40dc816a e3fa8e6c 4b286bc4
+ 71b72ee6 e79f1a1e;
+
+ repr(k*Pe) =0x3a293d01 e4110a06 b9c2d02a bff7abac 40a918df 69bbfa3d
+ f5b5da19 923d6da7,
+
+ where the rightmost bit of the rightmost octet indicates the parity
+ of the xcoordinate 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 Appendix I.3 and Appendix J for further detail on
+ (squeezed) point compression.
+
+ The scalar representation and (squeezed) point representation
+ illustrated above are fully consistent with the representations
+ specified in [RFC8032]. Note that, contrary to [RFC8032], [RFC8032]
+ requires unique representations of all elements of GF(p).
+
+K.3. Example with Wei25519
+
+ Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519:
+
+ X 14428294459702615171094958724191825368445920488283965295163094662
+ 783879239338
+
+ (=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7
+ 2a41cf12 629e56aa).
+
+ Y 53327798092436462013048370302019946300826511459161905709144645521
+ 233690313086
+
+ (=0x75e676ce deee3b3c 12942357 22f1d884 ac06de07 330fb07b
+ ae35ca26 df75417e).
+
+ X1 34422557393689369648095312405803933433606568476197477554293337733
+ 87341283644
+
+ (=0x079c3f69 9b688181 69038c35 39c11eb5 96d09f5b 12a242b4
+ ce660f13 3368c13c).
+
+ Y1 76981661982917351630937517222412729130882368858134322156485762195
+ 67913357634
+
+ (=0x110501f6 1dff511e d6c4e9b9 bfd5acbe 8bf043b8 c3e381dd
+ f5771306 479ad142).
+
+ X2 22716193187790487472805844610038683159372373526135883092373909944
+ 834653057415
+
+ (=0x3238e8e2 ec6e8b7a e1e8feff 97aa58dd d2435bb5 0071cbc2
+ 0d0d4a42 9be67187).
+
+ Y2 43046985853631671610553834968785204191967171967937842531656254539
+ 962663994648
+
+ (=0x5f2bbb06 f7ec5953 2c2a1a62 21124585 1d2682e0 cc37307e
+ fbc17f7f 7fda8518).
+
+ The representation of k and the compressed representations of Pw and
+ k*Pw in tight MSB/msborder are given by
+
+ repr(k) =0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3
+ c08d5abd 15e29c50;
+
+ repr(Pw) =0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7
+ 2a41cf12 629e56aa;
+
+ repr(k*Pw) =0x079c3f69 9b688181 69038c35 39c11eb5 96d09f5b 12a242b4
+ ce660f13 3368c13c,
+
+ where the leftmost bit of the leftmost octet indicates the parity of
+ the Ycoordinate of the point of Wei25519 in question (which, in this
+ case, are both zero, since Y and Y1 are even). See Appendix I.1 and
+ Appendix J for further detail on (squeezed) point compression.
+
+ The scalar representation is consistent with the representations
+ specified in [SEC1]; the (squeezed) point representation illustrated
+ above is "new". For completeness, we include a SEC1consistent
+ representation of the point Pw in affine format and in compressed
+ format below.
+
+ The SEC1compliant affine representation of the point Pw in tight
+ MSB/msborder is given by
+
+ aff(Pw) =0x04 1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b
+ 55202fe7 2a41cf12 629e56aa
+
+ 75e676ce deee3b3c 12942357 22f1d884 ac06de07 330fb07b
+ ae35ca26 df75417e,
+
+ whereas the SEC1compliant compressed representation of the point Pw
+ in tight MSB/msborder is given by
+
+ compr(Pw) =0x02 1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b
+ 55202fe7 2a41cf12 629e56aa;
+
+ The SEC1compliant uncompressed format aff(Pw) of an affine point Pw
+ corresponds to the rightconcatenation of its X and Ycoordinates,
+ each in tight MSB/msborder, prepended by the string 0x04, where the
+ reverse procedure is uniquely defined, since elements of GF(p) have a
+ unique fixedsize representation. The (squeezed) compressed format
+ repr(Pw) corresponds to the SEC1compliant 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 255bit prime field. For further details,
+ see [SEC1].
+
+K.4. Example with Wei25519.2
+
+ Pw2=(X, Y), k*Pw2=(X1, Y1), and (k+1)*Pw2=(X2, Y2) with Wei25519.2:
+
+ X 17830493209951148331008014701079988862634531394137235438571836389
+ 227198459763
+
+ (=0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c
+ f21c8672 d1ecaf73).
+
+ Y 21064492012933896105338241940477778461866060481408222122979836206
+ 137075789640
+
+ (=0x2e921479 5ad47af7 784831de 572ed8e9 7e20e137 cc67378c
+ 184ca19f f9136f48).
+
+ X1 65470988951686461979789632362377759464688342154017353834939203791
+ 39281908968
+ (=0x0e7986d2 e94354ab 8abd8806 3154536a 4dcf8e6e 65557183
+ e242192d 3b87f4e8).
+
+ Y1 51489590494292183562535790579480033229043271539297275888817125227
+ 35262330110
+
+ (=0x0b623521 c1ff84bc 1522ff26 3376796d be77fcad 1fcabc28
+ 98f1be85 d7576cfe).
+
+ X2 83741788501517200942826153677682120998854086551751663061374935388
+ 3494226693
+
+ (=0x01d9f633 b2ac2606 9e6e93f7 6917446c 2b27c16f 729121d7
+ 709c0a58 00ef9b05).
+
+ Y2 42567334190622848157611574766896093933050043101247319937794684825
+ 168161540336
+
+ (=0x5e1c41e1 fb74e41b 3a19ce50 e1b2caf7 7cabcbb3 0c1c1474
+ a4fd13e6 6c4c08f0).
+
+ The representation of k and the compressed representations of Pw2 and
+ k*Pw2 in tight MSB/msborder are given by
+
+ repr(k) =0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3
+ c08d5abd 15e29c50;
+
+ repr(Pw2) =0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c
+ f21c8672 d1ecaf73;
+
+ repr(k*Pw2) =0x0e7986d2 e94354ab 8abd8806 3154536a 4dcf8e6e 65557183
+ e242192d 3b87f4e8,
+
+ where the leftmost bit of the leftmost octet indicates the parity of
+ the Ycoordinate of the point of Wei25519.2 in question (which, in
+ this case, are both zero, since Y and Y1 are even). See
+ Appendix Appendix I.1 and Appendix J for further detail on (squeezed)
+ point compression.
+
+K.5. Example with Wei25519.3
+
+ Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei25519.3:
+
+ X 14780197759513083469009623947734627174363231692126610860256057394
+ 455099634096
+
+ (=0x20ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00
+ eb4c9272 03ca71b0).
+
+ Y 45596733430378470319805536538617129933663237960146030424392249401
+ 952949482817
+
+ (=0x64ced628 e982648e 4bfcf30c 71c4d267 ba48b0ce fee20062
+ b43ef4c9 73f7b541).
+
+ X1 47362979975244556396292400751828272600887612546997532158738958926
+ 60745725532
+
+ (=0x0a78a650 a39995ef dcf4de88 940d4ce9 5b2ca35c c5d70e06
+ 63b8455e 2e04e65c).
+
+ Y1 30318112837157047703426636957515037640997356617656007157255559136
+ 153389790354
+
+ (=0x64ced628 e982648e 4bfcf30c 71c4d267 ba48b0ce fee20062
+ b43ef4c9 73f7b541).
+
+ X2 23778942085873786433506063022059853212880296499622328201295446580
+ 293591664363
+
+ (=0x3492677e 6ae9d1c3 e08f908b 61033f3d 4e8322c9 fba6da81
+ 2c95b067 9b1486eb).
+
+ Y2 44846366394651736248316749170687053272682847823018287439056537991
+ 969511150494
+
+ (=0x632624d4 ab94c83a 796511c0 5f5412a3 876e56d2 ed18eca3
+ 21b95bef 7bf9939e).
+
+ The representation of k and the compressed representations of Pw3 and
+ k*Pw3 in tight MSB/msborder are given by
+
+ repr(k) =0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3
+ c08d5abd 15e29c50;
+
+ repr(Pw3) =0xa0ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00
+ eb4c9272 03ca71b0;
+
+ repr(k*Pw3) =0x0a78a650 a39995ef dcf4de88 940d4ce9 5b2ca35c c5d70e06
+ 63b8455e 2e04e65c,
+
+ where the leftmost bit of the leftmost octet indicates the parity of
+ the Ycoordinate 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 Appendix I.1 and Appendix J for further detail on
+ (squeezed) point compression.
Appendix L. Auxiliary Functions
L.1. Square Roots in GF(q)
Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see
Appendix L.1.1) or if q = 5 (mod 8) (see Appendix L.1.2). Details on
how to compute square roots for other values of q are out of scope.

If square roots are easy to compute in GF(q), then so are these in
GF(q^2).
L.1.1. Square Roots in GF(q), where q = 3 (mod 4)
If y is a nonzero element of GF(q) and z:= y^{(q3)/4}, then y is a
square in GF(q) only if y*z^2=1. If y*z^2=1, z is a square root of
1/y and y*z is a square root of y in GF(q).
L.1.2. Square Roots in GF(q), where q = 5 (mod 8)