draft-ietf-lwig-curve-representations-02.txt   draft-ietf-lwig-curve-representations-03.txt 
lwig R. Struik lwig R. Struik
Internet-Draft Struik Security Consultancy Internet-Draft Struik Security Consultancy
Intended status: Informational March 11, 2019 Intended status: Informational March 23, 2019
Expires: September 12, 2019 Expires: September 24, 2019
Alternative Elliptic Curve Representations Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-02 draft-ietf-lwig-curve-representations-03
Abstract Abstract
This document specifies how to represent Montgomery curves and This document specifies how to represent Montgomery curves and
(twisted) Edwards curves as curves in short-Weierstrass form and (twisted) Edwards curves as curves in short-Weierstrass form and
illustrates how this can be used to carry out elliptic curve illustrates how this can be used to carry out elliptic curve
computations using existing implementations of, e.g., ECDSA and ECDH computations using existing implementations of, e.g., ECDSA and ECDH
using NIST prime curves. using NIST prime curves.
Requirements Language Requirements Language
skipping to change at page 1, line 41 skipping to change at page 1, line 41
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on September 12, 2019. This Internet-Draft will expire on September 24, 2019.
Copyright Notice Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 3 1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 4
2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 4 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 4
3. Use of Representation Switches . . . . . . . . . . . . . . . 4 3. Use of Representation Switches . . . . . . . . . . . . . . . 4
4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 5 4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 5
4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 6 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 6
4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 6 4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 6
4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 6 4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 7
5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6. Security Considerations . . . . . . . . . . . . . . . . . . . 8 6. Security Considerations . . . . . . . . . . . . . . . . . . . 8
7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 8 7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 9
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 9 8.1. COSE Elliptic Curves Registration . . . . . . . . . . . . 9
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 8.2. COSE Algorithms Registration (1/2) . . . . . . . . . . . 10
10.1. Normative References . . . . . . . . . . . . . . . . . . 9 8.3. COSE Algorithms Registration (2/2) . . . . . . . . . . . 10
10.2. Informative References . . . . . . . . . . . . . . . . . 10 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11
Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 10 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 11
A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 10 10.1. Normative References . . . . . . . . . . . . . . . . . . 11
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 11 10.2. Informative References . . . . . . . . . . . . . . . . . 12
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 11 Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 13
Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 11 A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 13
B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 11 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 13
B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 13 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 13
Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 14 Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 14
C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 14 B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 14
C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 15 B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 15
C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 15 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 16
Appendix D. Relationship Between Curve Models . . . . . . . . . 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 D.1. Mapping between Twisted Edwards Curves and Montgomery
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 16 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 19
D.2. Mapping between Montgomery Curves and Weierstrass Curves 17 D.2. Mapping between Montgomery Curves and Weierstrass Curves 20
D.3. Mapping between Twisted Edwards Curves and Weierstrass D.3. Mapping between Twisted Edwards Curves and Weierstrass
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 18 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 21
Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 18 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 21
E.1. Curve Definition and Alternative Representations . . . . 18 E.1. Curve Definition and Alternative Representations . . . . 21
E.2. Switching between Alternative Representations . . . . . . 19 E.2. Switching between Alternative Representations . . . . . . 21
E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 20 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 23
Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 22 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 25
F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 22 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 25
F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 23 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 26
F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 24 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 26
F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 25 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 27
Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 26 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 29
G.1. Further Alternative Representations . . . . . . . . . . . 26 G.1. Further Alternative Representations . . . . . . . . . . . 29
G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 26 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 29
G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 27 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 30
Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 29 Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 31
H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 29 H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 31
H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 29 H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 31
H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 31 H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 34
H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 34 H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 37
H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 35 H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 38
H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 35 H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 38
H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 37 H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 40
H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 40 H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 43
Appendix I. Point Compression . . . . . . . . . . . . . . . . . 41 Appendix I. Point Compression . . . . . . . . . . . . . . . . . 44
I.1. Point Compression for Weierstrass Curves . . . . . . . . 42 I.1. Point Compression for Weierstrass Curves . . . . . . . . 44
I.2. Point Compression for Montgomery Curves . . . . . . . . . 42 I.2. Point Compression for Montgomery Curves . . . . . . . . . 45
I.3. Point Compression for Twisted Edwards Curves . . . . . . 43 I.3. Point Compression for Twisted Edwards Curves . . . . . . 46
Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 43 Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 46
J.1. Conversion between Bit Strings and Integers . . . . . . . 43 J.1. Conversion between Bit Strings and Integers . . . . . . . 47
J.2. Conversion between Octet Strings and Integers (OS2I, J.2. Conversion between Octet Strings and Integers (OS2I,
I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 44 I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 47
J.3. Conversion between Octet Strings and Bit Strings (BS2OS, J.3. Conversion between Octet Strings and Bit Strings (BS2OS,
OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 44 OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 48
J.4. Conversion between Field Elements and Octet Strings J.4. Conversion between Field Elements and Octet Strings
(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 44 (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 48
J.5. Ordering Conventions . . . . . . . . . . . . . . . . . . 45 J.5. Conversion between Elements of Z mod n and Octet Strings
Appendix K. Representations for Curve25519 Family Members . . . 46 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 48
K.1. Wei25519 . . . . . . . . . . . . . . . . . . . . . . . . 46 J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 49
Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 46 Appendix K. Representation Examples Curve25519 Family Members . 50
L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 46 K.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 50
L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 47 K.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 52
L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 47 K.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 53
L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 47 K.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 55
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 47 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 1. Fostering Code Reuse with New Elliptic Curves
It is well-known that elliptic curves can be represented using It is well-known that elliptic curves can be represented using
different curve models. Recently, IETF standardized elliptic curves different curve models. Recently, IETF standardized elliptic curves
that are claimed to have better performance and improved robustness that are claimed to have better performance and improved robustness
against "real world" attacks than curves represented in the against "real world" attacks than curves represented in the
traditional "short" Weierstrass model. This document specifies an traditional "short" Weierstrass model. This document specifies an
alternative representation of points of Curve25519, a so-called alternative representation of points of Curve25519, a so-called
Montgomery curve, and of points of Edwards25519, a so-called twisted Montgomery curve, and of points of Edwards25519, a so-called twisted
skipping to change at page 5, line 25 skipping to change at page 5, line 34
Alternative curve representations can, therefore, be used in any Alternative curve representations can, therefore, be used in any
cryptographic scheme that involves computations on public-private key cryptographic scheme that involves computations on public-private key
pairs, where implementations may carry out computations on the pairs, where implementations may carry out computations on the
corresponding object for the isomorphic or isogenous curve and corresponding object for the isomorphic or isogenous curve and
convert the results back to the original curve (where, in case this 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). involves an l-isogeny, one has to take into account the factor l).
This includes use with elliptic-curve based signature schemes and key This includes use with elliptic-curve based signature schemes and key
agreement and key transport schemes. 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. Examples
4.1. Implementation of X25519 4.1. Implementation of X25519
RFC 7748 [RFC7748] specifies the use of X25519, a co-factor Diffie- RFC 7748 [RFC7748] specifies the use of X25519, a co-factor Diffie-
Hellman key agreement scheme, with instantiation by the Montgomery Hellman key agreement scheme, with instantiation by the Montgomery
curve Curve25519. This key agreement scheme was already specified in curve Curve25519. This key agreement scheme was already specified in
Section 6.1.2.2 of NIST SP 800-56a [SP-800-56a] for elliptic curves Section 6.1.2.2 of NIST SP 800-56a [SP-800-56a] for elliptic curves
in short Weierstrass form. Hence, one can implement X25519 using in short Weierstrass form. Hence, one can implement X25519 using
existing NIST routines by (1) representing a point of the Montgomery existing NIST routines by (1) representing a point of the Montgomery
curve Curve25519 as a point of the Weierstrass curve Wei25519; (2) curve Curve25519 as a point of the Weierstrass curve Wei25519; (2)
instantiating the co-factor Diffie-Hellman key agreement scheme of instantiating the co-factor Diffie-Hellman key agreement scheme of
the NIST specification with the resulting point and Wei25519 domain the NIST specification with the resulting point and Wei25519 domain
parameters; (3) representing the key resulting from this scheme parameters; (3) representing the key resulting from this scheme
(which is a point of the curve Wei25519 in Weierstrass form) as a (which is a point of the curve Wei25519 in Weierstrass form) as a
point of the Montgomery curve Curve25519. The representation change point of the Montgomery curve Curve25519. The representation change
can be implemented via a simple wrapper and involves a single modular can be implemented via a simple wrapper and involves a single modular
addition (see Appendix D.2). Using this method has the additional addition (see Appendix D.2). Using this method has the additional
advantage that one can reuse the public-private key pair routines, advantage that one can reuse the public-private key pair routines,
domain parameter validation, and other checks that are already part domain parameter validation, and other checks that are already part
of the NIST specifications. Note: at this point, it is unclear of the NIST specifications. A NIST-compliant version of co-factor
whether this implies that a FIPS-accredited module implementing co- Diffie-Hellman key agreement (denoted by ECDH25519) results if one
factor Diffie-Hellman for, e.g., P-256 would also extend this keeps inputs (key contributions) and outputs (shared key) in the
accreditation to X25519. 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.
4.2. Implementation of Ed25519 4.2. Implementation of Ed25519
RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature
scheme, with instantiation by the twisted Edwards curve Edwards25519. scheme, with instantiation by the twisted Edwards curve Edwards25519.
One can implement the computation of the ephemeral key pair for One can implement the computation of the ephemeral key pair for
Ed25519 using an existing Montgomery curve implementation by (1) Ed25519 using an existing Montgomery curve implementation by (1)
generating a public-private key pair (k, R':=k*G') for Curve25519; generating a public-private key pair (k, R':=k*G') for Curve25519;
(2) representing this public-private key as the pair (k, R:=k*G) for (2) representing this public-private key as the pair (k, R:=k*G) for
Ed25519. As before, the representation change can be implemented via Ed25519. As before, the representation change can be implemented via
skipping to change at page 6, line 30 skipping to change at page 6, line 44
hereof (which uses the v-coordinate of the base point of Curve25519 hereof (which uses the v-coordinate of the base point of Curve25519
as well). For details, see Appendix C.1. as well). For details, see Appendix C.1.
4.3. Specification of ECDSA25519 4.3. Specification of ECDSA25519
FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and
can be instantiated not just with the NIST prime curves, but also can be instantiated not just with the NIST prime curves, but also
with other Weierstrass curves (that satisfy additional cryptographic with other Weierstrass curves (that satisfy additional cryptographic
criteria). In particular, one can instantiate this scheme with the criteria). In particular, one can instantiate this scheme with the
Weierstrass curve Wei25519 and the hash function SHA-256, where an Weierstrass curve Wei25519 and the hash function SHA-256, where an
implementation may generate a public-private key pair for Wei25519 by implementation may generate an ephemeral public-private key pair for
(1) internally carrying out these computations on the Montgomery Wei25519 by (1) internally carrying out these computations on the
curve Curve25519, the twisted Edwards curve Edwards25519, or even the Montgomery curve Curve25519, the twisted Edwards curve Edwards25519,
Weierstrass curve Wei25519.-3 (with hardcoded a=-3 domain parameter); or even the Weierstrass curve Wei25519.-3 (with hardcoded a=-3 domain
(2) representing the result as a key pair for the curve Wei25519. parameter); (2) representing the result as a key pair for the curve
Note that, in either case, one can implement these schemes with the Wei25519. Note that, in either case, one can implement these schemes
same representation conventions as used with existing NIST with the same representation conventions as used with existing NIST
specifications, including bit/byte-ordering, compression functions, specifications, including bit/byte-ordering, compression functions,
and the-like. This allows generic implementations of ECDSA with the 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 hash function SHA-256 and with the NIST curve P-256 or with the curve
Wei25519 specified in this draft to use the same implementation Wei25519 specified in this specification to reuse the same
(instantiated with, respectively, the NIST P-256 elliptic curve implementation (instantiated with, respectively, the NIST P-256
domain parameters or with the domain parameters of curve Wei25519 elliptic curve domain parameters or with the domain parameters of
specified in Appendix E). curve Wei25519 specified in Appendix E).
4.4. Other Uses 4.4. Other Uses
Any existing specification of cryptographic schemes using elliptic Any existing specification of cryptographic schemes using elliptic
curves in Weierstrass form and that allows introduction of a new curves in Weierstrass form and that allows introduction of a new
elliptic curve (here: Wei25519) is amenable to similar constructs, elliptic curve (here: Wei25519) is amenable to similar constructs,
thus spawning "offspring" protocols, simply by instantiating these thus spawning "offspring" protocols, simply by instantiating these
using the new curve in "short" Weierstrass form, thereby allowing using the new curve in "short" Weierstrass form, thereby allowing
code and/or specifications reuse and, for implementations that so code and/or specifications reuse and, for implementations that so
desire, carrying out curve computations "under the hood" on desire, carrying out curve computations "under the hood" on
skipping to change at page 7, line 40 skipping to change at page 8, line 7
2. Representation conventions. While elliptic curve computations 2. Representation conventions. While elliptic curve computations
are carried-out in a field GF(q) and, thereby, involve large are carried-out in a field GF(q) and, thereby, involve large
integer arithmetic, these integers are represented as bit- and integer arithmetic, these integers are represented as bit- and
byte-strings. Here, [RFC8032] uses least-significant-byte byte-strings. Here, [RFC8032] uses least-significant-byte
(LSB)/least-significant-bit (lsb) conventions, whereas [RFC7748] (LSB)/least-significant-bit (lsb) conventions, whereas [RFC7748]
uses LSB/most-significant-bit (msb) conventions, and where most uses LSB/most-significant-bit (msb) conventions, and where most
other cryptographic specifications, including NIST SP800-56a other cryptographic specifications, including NIST SP800-56a
[SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005 [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 [ANSI-X9.62] use MSB/msb conventions. Since each pair of
conventions is different (see Appendix J for details), this does conventions is different (see Appendix J for details and
necessitate bit/byte representation conversions; Appendix K for examples), this does necessitate bit/byte
representation conversions;
3. Domain parameters. All traditional NIST curves are Weierstrass 3. Domain parameters. All traditional NIST curves are Weierstrass
curves with domain parameter a=-3, while all Brainpool curves curves with domain parameter a=-3, while all Brainpool curves
[RFC5639] are isomorphic to a Weierstrass curve of this form. [RFC5639] are isomorphic to a Weierstrass curve of this form.
Thus, one can expect there to be existing Weierstrass Thus, one can expect there to be existing Weierstrass
implementations with a hardcoded a=-3 domain parameter implementations with a hardcoded a=-3 domain parameter
("Jacobian-friendly"). For those implementations, including the ("Jacobian-friendly"). For those implementations, including the
curve Wei25519 as a potential vehicle for offering support for curve Wei25519 as a potential vehicle for offering support for
the CFRG curves Curve25519 and Edwards25519 is not possible, the CFRG curves Curve25519 and Edwards25519 is not possible,
since not of the required form. Instead, one has to implement since not of the required form. Instead, one has to implement
Wei25519.-3 and include code that implements the isogeny and dual Wei25519.-3 and include code that implements the isogeny and dual
isogeny from and to Wei25519. This isogeny has degree l=47 and isogeny from and to Wei25519. This isogeny has degree l=47 and
requires roughly 9kB of storage for isogeny and dual-isogeny requires roughly 9kB of storage for isogeny and dual-isogeny
computations (see the tables in Appendix H). Note that storage computations (see the tables in Appendix H). Note that storage
would have reduced to a single 64-byte table if only the curve 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 would have been generated so as to be isomorphic to a Weierstrass
curve with hardcoded a=-3 parameter (this corresponds to l=1). curve with hardcoded a=-3 parameter (this corresponds to l=1).
Note: an example of such a curve is the Montgomery curve M_{A,B}
over GF(p) with p=2^255-19, B=1, and A=-1410290 or (if one wants NOTE: An example of a Montgomery curve defined over the same
the base point to still have u-coordinate u=9) A=-3960846. In field as Curve25519 that is isomorphic to a Weierstrass curve
either case, the resulting curve has the same cryptographic with hardcoded a=-3 parameter is the Montgomery curve M_{A,B}
properties as Curve25519 and the same performance (since A is a with B=1 and A=-1410290 (or, if one wants the base point to still
3-byte integer as is the case with the domain parameter A=486662 have u-coordinate u=9, with B=1 and A=-3960846). In either case,
used with Curve25519), while being "Jacobian-friendly" by design. 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.
6. Security Considerations 6. Security Considerations
The different representations of elliptic curve points discussed in The different representations of elliptic curve points discussed in
this document are all obtained using a publicly known transformation, this document are all obtained using a publicly known transformation,
which is either an isomorphism or a low-degree isogeny. It is well- which is either an isomorphism or a low-degree isogeny. It is well-
known that an isomorphism maps elliptic curve points to equivalent known that an isomorphism maps elliptic curve points to equivalent
mathematical objects and that the complexity of cryptographic mathematical objects and that the complexity of cryptographic
problems (such as the discrete logarithm problem) of curves related problems (such as the discrete logarithm problem) of curves related
via a low-degree isogeny are tightly related. Thus, the use of these via a low-degree isogeny are tightly related. Thus, the use of these
techniques does not negatively impact cryptographic security. techniques does not negatively impact cryptographic security of
elliptic curve operations.
As to implementation security, reusing existing high-quality code or As to implementation security, reusing existing high-quality code or
generic implementations that have been carefully designed to generic implementations that have been carefully designed to
withstand implementation attacks for one curve model may allow a more withstand implementation attacks for one curve model may allow a more
economical way of development and maintenance than providing this economical way of development and maintenance than providing this
same functionality for each curve model separately (if multiple curve same functionality for each curve model separately (if multiple curve
models need to be supported) and, otherwise, may allow a more gradual models need to be supported) and, otherwise, may allow a more gradual
migration path, where one may initially use existing and accredited migration path, where one may initially use existing and accredited
chipsets that cater to the pre-dominant curve model used in practice chipsets that cater to the pre-dominant curve model used in practice
for over 15 years. 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.
7. Privacy Considerations 7. Privacy Considerations
The transformations between different curve models described in this The transformations between different curve models described in this
document are publicly known and, therefore, do not affect privacy document are publicly known and, therefore, do not affect privacy
provisions. provisions.
8. IANA Considerations 8. IANA Considerations
An object identifier is requested for Wei25519 and ECDSA25519, using An object identifier is requested for curve Wei25519 and its use with
the representation conventions in this document. ECDSA and co-factor 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: short-Weierstrass 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/ SHA-256 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: NIST-compliant co-factor Diffie-Hellman 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 9. Acknowledgements
Thanks to Nikolas Rosener for discussions surrounding implementation Thanks to Nikolas Rosener for discussions surrounding implementation
details of the techniques described in this document and to Phillip details of the techniques described in this document and to Phillip
Hallam-Baker for triggering inclusion of verbiage on the use of Hallam-Baker for triggering inclusion of verbiage on the use of
Montgomery ladders with recovery of the y-coordinate. Thanks to Montgomery ladders with recovery of the y-coordinate. Thanks to
Stanislav Smyshlyaev for his careful review. Stanislav Smyshlyaev for his careful review.
10. References 10. References
skipping to change at page 9, line 30 skipping to change at page 11, line 30
Signature Algorithm (ECDSA)", American National Standard Signature Algorithm (ECDSA)", American National Standard
for Financial Services, Accredited Standards Committee X9, for Financial Services, Accredited Standards Committee X9,
Inc, Anapolis, MD, 2005. Inc, Anapolis, MD, 2005.
[FIPS-186-4] [FIPS-186-4]
FIPS 186-4, "Digital Signature Standard (DSS), Federal FIPS 186-4, "Digital Signature Standard (DSS), Federal
Information Processing Standards Publication 186-4", US Information Processing Standards Publication 186-4", US
Department of Commerce/National Institute of Standards and Department of Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, July 2013. Technology, Gaithersburg, MD, July 2013.
[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 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography [RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography
(ECC) Brainpool Standard Curves and Curve Generation", (ECC) Brainpool Standard Curves and Curve Generation",
RFC 5639, DOI 10.17487/RFC5639, March 2010, RFC 5639, DOI 10.17487/RFC5639, March 2010,
<https://www.rfc-editor.org/info/rfc5639>. <https://www.rfc-editor.org/info/rfc5639>.
skipping to change at page 10, line 5 skipping to change at page 12, line 19
[RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
for Security", RFC 7748, DOI 10.17487/RFC7748, January for Security", RFC 7748, DOI 10.17487/RFC7748, January
2016, <https://www.rfc-editor.org/info/rfc7748>. 2016, <https://www.rfc-editor.org/info/rfc7748>.
[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
Signature Algorithm (EdDSA)", RFC 8032, Signature Algorithm (EdDSA)", RFC 8032,
DOI 10.17487/RFC8032, January 2017, DOI 10.17487/RFC8032, January 2017,
<https://www.rfc-editor.org/info/rfc8032>. <https://www.rfc-editor.org/info/rfc8032>.
[RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)",
RFC 8152, DOI 10.17487/RFC8152, July 2017,
<https://www.rfc-editor.org/info/rfc8152>.
[SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0",
Standards for Efficient Cryptography, , June 2009.
[SP-800-56a] [SP-800-56a]
NIST SP 800-56a, "Recommendation for Pair-Wise Key NIST SP 800-56a, "Recommendation for Pair-Wise Key
Establishment Schemes Using Discrete Log Cryptography, Establishment Schemes Using Discrete Log Cryptography,
Revision 2", US Department of Commerce/National Institute Revision 3", US Department of Commerce/National Institute
of Standards and Technology, Gaithersburg, MD, June 2013. of Standards and Technology, Gaithersburg, MD, April 2018.
10.2. Informative References 10.2. Informative References
[ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in [ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in
Cryptography", Cambridge University Press, Lecture Notes Cryptography", Cambridge University Press, Lecture Notes
Series 265, July 1999. Series 265, July 1999.
[ECC-Isogeny] [ECC-Isogeny]
E. Brier, M. Joye, "Fast Point Multiplication on Elliptic E. Brier, M. Joye, "Fast Point Multiplication on Elliptic
Curves through Isogenies", AAECC, Lecture Notes in Curves through Isogenies", AAECC, Lecture Notes in
skipping to change at page 42, line 29 skipping to change at page 45, line 15
where alpha:=X^3+a*X+b. If alpha is not a square in GF(q), this 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, 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 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 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 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 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. 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 However, if alpha=0 and t=1, the ordered pair (X, t) does not
correspond to the outcome of the point compression function. 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 (non-affine) 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 I.2. Point Compression for Montgomery Curves
If P:=(u, v) is an affine point of the Montgomery curve M_{A,B} 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 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 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 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 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 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 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 alone, since v=0 and has fixed parity. Conversely, given the ordered
skipping to change at page 43, line 5 skipping to change at page 45, line 50
this equation does not have a solution in GF(q) and the ordered pair 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, (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 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 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 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 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, 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 t) does not correspond to the outcome of the point compression
function. 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.
I.3. Point Compression for Twisted Edwards Curves I.3. Point Compression for Twisted Edwards Curves
If P:=(x, y) is an affine point of the twisted Edwards curve E_{a,d} 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 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 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 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., 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 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 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, y-coordinate alone, since x=0 and has fixed parity. Conversely,
skipping to change at page 43, line 30 skipping to change at page 46, line 35
a square in GF(q), this equation does not have a solution in GF(q) 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 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 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 -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 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 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 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 t=1, the ordered pair (t, y) does not correspond to the outcome of
the point compression function. 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 Appendix J. Data Conversions
The string over some alphabet S consisting of the symbols x_{l-1}, 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 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 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 (over S) is the number of symbols it contains (here: l). The empty
string is the (unique) string of length l=0. 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 we define these notions as well if t is
outside the interval [0,l]: a t-prefix or t-postfix is the empty
string if t is negative and 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 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 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 (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 {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 J.1. Conversion between Bit Strings and Integers
There is a 1-1 correspondence between bit strings of length l and the There is a 1-1 correspondence between bit strings of length l and the
integers in the interval [0, 2^l), where the bit string 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:=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, 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 the empty bit string corresponds to the integer zero.) Note that
while the mapping from bit strings to integers is uniquely defined, while the mapping from bit strings to integers is uniquely defined,
the inverse mapping from integers to bit strings is not, since any the inverse mapping from integers to bit strings is not, since any
skipping to change at page 45, line 14 skipping to change at page 48, line 41
to octet strings and the inverse mapping are only uniquely defined if 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 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 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 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 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 elements to octet strings and the mapping OS2FE(X,l) from octet
strings to field elements, where the underlying field is implicit and strings to field elements, where the underlying field is implicit and
assumed to be known from context. In this case, the octet string has assumed to be known from context. In this case, the octet string has
length l*m. length l*m.
J.5. Ordering Conventions J.5. Conversion between Elements of Z mod n and Octet Strings (ZnE2OS,
OS2ZnE)
There is a 1-1 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 non-prime set
Z(n), for that matter).
J.6. Ordering Conventions
One can consider various representation functions, depending on bit- One can consider various representation functions, depending on bit-
ordering and octet-ordering conventions. ordering and octet-ordering conventions.
The description below makes use of an auxiliary function (the The description below makes use of an auxiliary function (the
reversion function), which we define both for bit strings and octet 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}, 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_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}). X':=rev(X):=str(x_0, x_1, ..., x_{l-2}, x_{l-1}).
skipping to change at page 46, line 8 skipping to change at page 50, line 13
str(X_{0}, X_{1}, ..., X_{l-2}, X_{l-1}). str(X_{0}, X_{1}, ..., X_{l-2}, X_{l-1}).
Thus, the 2-octet string "07e3" represents the integer 2019 (=0x07e3) 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 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 integer 51,168 (0xc7e0) in LSB/lsb order, and the integer 58,119
(=0xe307) in LSB/msb order. (=0xe307) in LSB/msb order.
Note that, with the above data conversions, there is still some 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 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 bit string or octet string (due to leading zeros). However, tight
representations (as defined above) are non-ambiguous. representations (as defined above) are non-ambiguous. (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 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 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 squeeze-in
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 We present some examples of computations using the curves introduced
compressed points for the curve Wei25519 are as indicated below. in this document. In each case, we indicate the values of P, k*P,
Representations are relative to the prime field GF(p), where and (k+1)*P, where P is a fixed multiple (here: 2019) of the base
p=2^255-19 is one of the general domain parameters of Appendix E.3. 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 k 45467544759954639344191351164156560595299236761702065033670739677
FE2OS(z), where one uses one the MSB/msb conventions and tight 691372543056
representation, as specified in Appendix J. In particular, each
element of GF(p) is represented as a 32-byte octet string, which -
when viewed as a bit string - has the leftmost bit position set to 0.
Each affine point (X, Y) of Wei25519 is represented as the (=0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3
rightconcatenation of the 32-byte octet representations for the x- c08d5abd 15e29c50).
and y-coordinate of this point according to the conventions above,
i.e., it is represented as the 64-byte octet string str(FE2OS(X),
FE2OS(Y)).
For each compressed point (X, t) of Wei25519, the parity bit t (which K.1. Example with Curve25519
is an element of the field GF(2)), is represented as a 1-bit bit
string, whereas the x-coordinate X (which is an element of GF(p)), is
represented as a 32-byte octet string FE2OS(X). The result is
"squeezed", by superimposing the 1-bit representation of t on the
leftmost (unused) bit-position of the 32-byte octet representation of
X.
Each integer in the interval [0,n-1] is viewed as an element of the Pm=(u, v), k*Pm=(u1, v1), and (k+1)*Pm=(u2, v2) with Curve25519:
prime field GF(n) and represented using MSB/msb conventions and a
tight representation. In particular, each element of GF(n) is u 53025657538808013645618620393754461319535915376830819974982289332
represented as a 32-byte octet string, which - when viewed as a bit 088255623750
string - has the lefmost three bit positions set to 0.
(=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 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
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 v-coordinate 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
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).
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/lsb-order 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 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 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/msb-order 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 Y-coordinate 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 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
aff(Pw) =0x04 1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b
55202fe7 2a41cf12 629e56aa
75e676ce deee3b3c 12942357 22f1d884 ac06de07 330fb07b
ae35ca26 df75417e,
whereas the SEC1-compliant compressed representation of the point Pw
in tight MSB/msb-order is given by
compr(Pw) =0x02 1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b
55202fe7 2a41cf12 629e56aa;
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].
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/msb-order 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 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 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/msb-order 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 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 Appendix I.1 and Appendix J for further detail on
(squeezed) point compression.
Appendix L. Auxiliary Functions Appendix L. Auxiliary Functions
L.1. Square Roots in GF(q) L.1. Square Roots in GF(q)
Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see 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 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. 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 If square roots are easy to compute in GF(q), then so are these in
GF(q^2). GF(q^2).
L.1.1. Square Roots in GF(q), where q = 3 (mod 4) L.1.1. Square Roots in GF(q), where q = 3 (mod 4)
If y is a nonzero element of GF(q) and z:= y^{(q-3)/4}, then y is a 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 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). 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) L.1.2. Square Roots in GF(q), where q = 5 (mod 8)
 End of changes. 38 change blocks. 
128 lines changed or deleted 642 lines changed or added

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