 1/draftietflwigcurverepresentations08.txt 20200309 17:14:15.296374789 0700
+++ 2/draftietflwigcurverepresentations09.txt 20200309 17:14:15.488379654 0700
@@ 1,210 +1,241 @@
lwig R. Struik
InternetDraft Struik Security Consultancy
Intended status: Informational July 24, 2019
Expires: January 25, 2020
+Intended status: Informational March 9, 2020
+Expires: September 10, 2020
Alternative Elliptic Curve Representations
 draftietflwigcurverepresentations08
+ draftietflwigcurverepresentations09
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.
+ using NIST prime curves. We also provide extensive background
+ material that may be useful for implementers of elliptic curve
+ cryptography.
Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
 "OPTIONAL" in this document are to be interpreted as described in RFC
 2119 [RFC2119].
+ "OPTIONAL" in this document are to be interpreted as described in BCP
+ 14 [RFC2119] [RFC8174] when, and only when, they appear in all
+ capitals, as shown here.
Status of This Memo
This InternetDraft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
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 January 25, 2020.
+ This InternetDraft will expire on September 10, 2020.
Copyright Notice
 Copyright (c) 2019 IETF Trust and the persons identified as the
+ Copyright (c) 2020 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/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 . . . . . . . . 4
 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 4
+ 1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 5
+ 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 5
3. Use of Representation Switches . . . . . . . . . . . . . . . 5
4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 6
 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 6
+ 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 7
4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 7
 4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 7
 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
 6. Implementation Considerations . . . . . . . . . . . . . . . . 9
 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 10
 8. Security Considerations . . . . . . . . . . . . . . . . . . . 11
 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 12
 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12
 10.1. COSE Elliptic Curves Registration . . . . . . . . . . . 12
 10.2. COSE Algorithms Registration (1/2) . . . . . . . . . . . 12
 10.3. COSE Algorithms Registration (2/2) . . . . . . . . . . . 13
 10.4. JOSE Elliptic Curves Registration . . . . . . . . . . . 13
 10.5. JOSE Algorithms Registration (1/2) . . . . . . . . . . . 13
 10.6. JOSE Algorithms Registration (2/2) . . . . . . . . . . . 14
 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14
 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 14
 12.1. Normative References . . . . . . . . . . . . . . . . . . 14
 12.2. Informative References . . . . . . . . . . . . . . . . . 16
 Appendix A. Some (nonBinary) Elliptic Curves . . . . . . . . . 17
 A.1. Curves in shortWeierstrass Form . . . . . . . . . . . . 17
 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 18
 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 18
 Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 18
 B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 18
 B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 20
 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 21
 C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 21
 C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 22
 C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 22
 Appendix D. Relationship Between Curve Models . . . . . . . . . 23
 D.1. Mapping between Twisted Edwards Curves and Montgomery
 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 24
+ 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 8
+ 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
+ 5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 9
+ 5.2. Representation Conventions . . . . . . . . . . . . . . . 9
+ 5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 9
+ 6. Implementation Considerations . . . . . . . . . . . . . . . . 10
+ 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 11
+ 8. Security Considerations . . . . . . . . . . . . . . . . . . . 12
+ 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 13
+ 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13
+ 10.1. IANA Considerations for Wei25519 . . . . . . . . . . . . 13
+ 10.1.1. COSE Elliptic Curves Registration . . . . . . . . . 14
+ 10.1.2. COSE Algorithms Registration (1/2) . . . . . . . . . 14
+ 10.1.3. COSE Algorithms Registration (2/2) . . . . . . . . . 14
+ 10.1.4. JOSE Elliptic Curves Registration . . . . . . . . . 15
+ 10.1.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 15
+ 10.1.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 16
+ 10.2. IANA Considerations for Wei448 . . . . . . . . . . . . . 16
+ 10.2.1. COSE Elliptic Curves Registration . . . . . . . . . 16
+ 10.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 17
+ 10.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 17
+ 10.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 17
+ 10.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 18
+ 10.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 18
 D.2. Mapping between Montgomery Curves and Weierstrass Curves 24
+ 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 18
+ 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 19
+ 12.1. Normative References . . . . . . . . . . . . . . . . . . 19
+ 12.2. Informative References . . . . . . . . . . . . . . . . . 20
+ Appendix A. Some (NonBinary) Elliptic Curves . . . . . . . . . 22
+ A.1. Curves in ShortWeierstrass Form . . . . . . . . . . . . 22
+ A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 22
+ A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 23
+ Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 23
+ B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 23
+ B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 25
+ Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 26
+ C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 26
+ C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 27
+ C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 28
+ Appendix D. Relationship Between Curve Models . . . . . . . . . 29
+ D.1. Mapping between Twisted Edwards Curves and Montgomery
+ Curves . . . . . . . . . . . . . . . . . . . . . . . . . 29
+ D.2. Mapping between Montgomery Curves and Weierstrass Curves 30
D.3. Mapping between Twisted Edwards Curves and Weierstrass
 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 25
 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 25
 E.1. Curve Definition and Alternative Representations . . . . 25
 E.2. Switching between Alternative Representations . . . . . . 26
 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 27
 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 29
 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 30
 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 30
 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 31
 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 32
 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 33
 G.1. Further Alternative Representations . . . . . . . . . . . 33
 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 33
 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 34
 Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 36
 H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 36
 H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 36
 H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 38
 H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 41
 H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 42
 H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 42
 H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 44
 H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 47
 Appendix I. Point Compression . . . . . . . . . . . . . . . . . 48
 I.1. Point Compression for Weierstrass Curves . . . . . . . . 49
 I.2. Point Compression for Montgomery Curves . . . . . . . . . 49
 I.3. Point Compression for Twisted Edwards Curves . . . . . . 50
 Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 51
 J.1. Conversion between Bit Strings and Integers . . . . . . . 52
 J.2. Conversion between Octet Strings and Integers (OS2I,
 I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 52
 J.3. Conversion between Octet Strings and Bit Strings (BS2OS,
 OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 52
 J.4. Conversion between Field Elements and Octet Strings
 (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 53
 J.5. Conversion between Elements of Z mod n and Octet Strings
 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 53
 J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 54
 Appendix K. Representation Examples Curve25519 Family Members . 55
 K.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 55
 K.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 57
 K.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 59
 K.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 61
 K.5. Example with Wei25519.3 . . . . . . . . . . . . . . . . 63
 Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 64
 L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 64
 L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 64
 L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 64
 L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 65
 L.3. Mapping to Curve Points . . . . . . . . . . . . . . . . . 65
 L.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 65
 L.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 66
 L.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 68
 L.4. Randomized Representation of Curve Points . . . . . . . . 68
 Appendix M. Curve secp256k1 and Friend . . . . . . . . . . . . . 68
 M.1. Curve Definition and Alternative Representation . . . . . 68
 M.2. Switching Between Representations . . . . . . . . . . . . 69
 M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 69
 M.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 71
 M.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 71
 M.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 72
 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 72
+ Curves . . . . . . . . . . . . . . . . . . . . . . . . . 31
+ Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 31
+ E.1. Curve Definition and Alternative Representations . . . . 31
+ E.2. Switching between Alternative Representations . . . . . . 31
+ E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 33
+ Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 35
+ F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 35
+ F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 36
+ F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 36
+ F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 37
+ Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 39
+ G.1. Further Alternative Representations . . . . . . . . . . . 39
+ G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 39
+ G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 40
+ G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 41
+ G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 42
+ G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 48
+ Appendix H. Point Compression . . . . . . . . . . . . . . . . . 54
+ H.1. Point Compression for Weierstrass Curves . . . . . . . . 54
+ H.2. Point Compression for Montgomery Curves . . . . . . . . . 55
+ H.3. Point Compression for Twisted Edwards Curves . . . . . . 56
+ Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 57
+ I.1. Conversion between Bit Strings and Integers (BS2I, I2BS) 57
+ I.2. Conversion between Octet Strings and Integers (OS2I,
+ I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 58
+ I.3. Conversion between Octet Strings and Bit Strings (OS2BS,
+ BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 58
+ I.4. Conversion between Field Elements and Octet Strings
+ (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 58
+ I.5. Conversion between Elements of Z mod n and Octet Strings
+ (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 59
+ I.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 59
+ Appendix J. Representation Examples Curve25519 Family Members . 61
+ J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 61
+ J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 63
+ J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 65
+ J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 67
+ J.5. Example with Wei25519.3 . . . . . . . . . . . . . . . . 68
+ Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 70
+ K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 70
+ K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 70
+ K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 70
+ K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 71
+ K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 71
+ K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 71
+ K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 72
+ K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 74
+ K.4. Mappings to HighOrder Curve Points . . . . . . . . . . . 74
+ K.4.1. Mapping to HighOrder Points of Weierstrass Curve . . 74
+ K.4.2. Mapping to HighOrder Points of Montgomery Curve . . 75
+ K.4.3. Mapping to HighOrder Points of Twisted Edwards Curve 76
+ K.5. Randomized Representation of Curve Points . . . . . . . . 77
+ Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 78
+ L.1. Curve Definition and Alternative Representation . . . . . 78
+ L.2. Switching Between Representations . . . . . . . . . . . . 79
+ L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 79
+ L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 81
+ L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 81
+ L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 81
+ Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 82
+ M.1. Curve Definition and Alternative Representations . . . . 82
+ M.2. Switching between Alternative Representations . . . . . . 83
+ M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 84
+ Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 87
+ N.1. Further Alternative Representations . . . . . . . . . . . 87
+ N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 87
+ N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 89
+ N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 91
+ N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 92
+ N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 92
+ Appendix O. Representation Examples Curve448 Family Members . . 93
+ O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 93
+ O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 96
+ O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 98
+ O.4. Example with Wei448.3 . . . . . . . . . . . . . . . . . 101
+ O.5. Example with Edwards448 . . . . . . . . . . . . . . . . . 103
+
+ Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 105
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
 Edwards curve, which are both specified in [RFC7748], as points of a
 specific socalled "short" Weierstrass curve, called Wei25519. We
 also define how to efficiently switch between these different
 representations.
+ 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 Edwards curve,
+ which are both specified in [RFC7748], as points of a specific so
+ called "short" Weierstrass curve, called Wei25519. We also define
+ how to efficiently switch between these different representations.
 Use of Wei25519 allows easy definition of new signature schemes and
 key agreement schemes already specified for traditional NIST prime
 curves, thereby allowing easy integration with existing
 specifications, such as NIST SP 80056a [SP80056a], FIPS Pub 1864
 [FIPS1864], and ANSI X9.622005 [ANSIX9.62], and fostering code
 reuse on platforms that already implement some of these schemes using
 elliptic curve arithmetic for curves in "short" Weierstrass form (see
 Appendix C.1).
+ Use of Wei25519 allows easy definition of new instantiations of
+ signature schemes and key agreement schemes already specified for
+ traditional NIST prime curves, thereby allowing easy integration with
+ existing specifications, such as NIST SP 80056a [SP80056a], FIPS
+ Pub 1864 [FIPS1864], and ANSI X9.622005 [ANSIX9.62], and
+ fostering code reuse on platforms that already implement some of
+ these schemes using elliptic curve arithmetic for curves in "short"
+ Weierstrass form (see Appendix C.1).
2. Specification of Wei25519
For the specification of Wei25519 and its relationship to Curve25519
and Edwards25519, see Appendix E. For further details and background
information on elliptic curves, we refer to the other appendices.
The use of Wei25519 allows reuse of existing generic code that
implements shortWeierstrass curves, such as the NIST curve P256, to
 also implement the CFRG curves Curve25519 and Edwards25519. We also
 cater to reusing of existing code where some domain parameters may
 have been hardcoded, thereby widening the scope of applicability. To
 this end, we specify the shortWeierstrass curves Wei25519.2 and
 Wei25519.3, with hardcoded domain parameter a=2 and a=3 (mod p),
 respectively; see Appendix G. (Here, p is the characteristic of the
 field over which these curves are defined.)
+ also implement the CFRG curves Curve25519 and Edwards25519. (Here,
+ generic code refers to an implementation that does not depend on
+ hardcoded domain parameters (see also Section 6).) We also cater to
+ reusing of existing code where some domain parameters may have been
+ hardcoded, thereby widening the scope of applicability. To this end,
+ we specify the shortWeierstrass curves Wei25519.2 and Wei25519.3,
+ with hardcoded domain parameter a=2 and a=3 (mod p), respectively;
+ see Appendix G. (Here, p is the characteristic of the field over
+ which these curves are defined.)
3. Use of Representation Switches
The curves Curve25519, Edwards25519, and Wei25519, as specified in
Appendix E.3, are all isomorphic, with the transformations of
Appendix E.2. These transformations map the specified base point of
each of these curves to the specified base point of each of the other
curves. Consequently, a publicprivate key pair (k,R:=k*G) for any
one of these curves corresponds, via these isomorphic mappings, to
the publicprivate key pair (k, R':=k*G') for each of these other
@@ 233,40 +264,40 @@
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.
+ specified in Appendix E.3 and Appendix G.3, see Appendix J.
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
+ addition (see Appendix E.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. 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.,
@@ 280,130 +311,156 @@
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
a simple wrapper. Note that the Montgomery ladder specified in
Section 5 of RFC7748 [RFC7748] does not provide sufficient
information to reconstruct R':=(u, v) (since it does not compute the
vcoordinate of R'). However, this deficiency can be remedied by
using a slightly modified version of the Montgomery ladder that
includes reconstruction of the vcoordinate of R':=k*G' at the end of
 hereof (which uses the vcoordinate of the base point of Curve25519
 as well). For details, see Appendix C.1.
+ the Montgomery ladder (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 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 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).
+ Weierstrass curve Wei25519 and the hash function SHA256
+ [FIPS1804], where an 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/byte
+ ordering, 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
+ 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). We
+ denote by ECDSA25519 the instantiation of ECDSA with SHA256 and with
+ curve Wei25519, where the signature (r,s) is represented as the
+ rightconcatenation of the integers r and s, each represented as
+ fixedsize strings with tight MSB/msb ordering (see Appendix I).
4.4. Other Uses
+4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others)
Any existing specification of cryptographic schemes using elliptic
curves in Weierstrass form and that allows introduction of a new
elliptic curve (here: Wei25519) is amenable to similar constructs,
thus spawning "offspring" protocols, simply by instantiating these
using the new curve in "short" Weierstrass form, thereby allowing
code and/or specifications reuse and, for implementations that so
desire, carrying out curve computations "under the hood" on
Montgomery curve and twisted Edwards curve cousins hereof (where
these exist). This would simply require definition of a new object
identifier for any such envisioned "offspring" protocol. This could
significantly simplify standardization of schemes and help keeping
the resource and maintenance cost of implementations supporting
algorithm agility [RFC7696] at bay.
+ We illustrate the construction of such offspring protocols for
+ Curve448, another Montgomery curve recently standardized by IETF (see
+ [RFC7748]). Similar to the case with Curve25519, one can represent
+ points of this curve via different curve models, viz. as points of an
+ Edwards curve (Ed448) or as points of a shortWeierstrass curve
+ (Wei448). For the specification of Wei448 and its relationship to
+ Curve448 and Ed448, see Appendix M. As with ECDH25519, one can now
+ easily define a NISTcompliant version of cofactor DiffieHellman
+ key agreement (denoted by ECDH448), by simply reusing the example of
+ Section 4.1, but now using the shortWeierstrass curve Wei448, rather
+ than Wei25519. Similarly, one can easily specify ECDSA with Wei448
+ and a suitable hash function, by simply reusing the example of
+ Section 4.3, but now using the shortWeierstrass curve Wei448, rather
+ than Wei25519, and picking as hash function SHAKE256 [FIPS202] with
+ output size of d=446 bits. We denote by ECDSA448 the resulting
+ signature scheme (with the same bit/byteordering conventions).
+
5. Caveats
The examples above illustrate how specifying the Weierstrass curve
Wei25519 (or any curve in shortWeierstrass format, for that matter)
may facilitate reuse of existing code and may simplify standards
development. However, the following caveats apply:
 1. Wire format. The transformations between alternative curve
 representations can be implemented at negligible relative
 incremental cost if the curve points are represented as affine
 points. If a point is represented in compressed format,
 conversion usually requires a costly point decompression step.
 This is the case in [RFC7748], where the inputs to the cofactor
 DiffieHellman scheme X25519, as well as its output, are
 represented in ucoordinateonly format. This is also the case
+5.1. Wire Format
+
+ The transformations between alternative curve representations can be
+ implemented at negligible relative incremental cost if the curve
+ points are represented as affine points. If a point is represented
+ in compressed format, conversion usually requires a costly point
+ decompression step. This is the case in [RFC7748], where the inputs
+ to the cofactor DiffieHellman scheme X25519, as well as its output,
+ are represented in ucoordinateonly format. This is also the case
in [RFC8032], where the EdDSA signature includes the ephemeral
 signing key represented in compressed format (see Appendix I for
 details);
+ signing key represented in compressed format (see Appendix H for
+ details). Note that in the latter case compression is lossless,
+ whereas it is lossy in the former case;
 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 and
 Appendix K for examples), this does necessitate bit/byte
 representation conversions;
+5.2. Representation Conventions
 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).
+ 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 least
+ significantbyte (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 I for details and Appendix J
+ for examples), this does necessitate bit/byte representation
+ conversions;
 NOTE 1: An example of a Montgomery curve defined over the same
 field as Curve25519 that is isomorphic to a Weierstrass curve
 with hardcoded a=3 parameter is the Montgomery curve M_{A,B}
 with B=1 and A=1410290 (or, if one wants the base point to still
 have 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.
+5.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. The lowest odddegree isogeny
+ has degree l=47 and requires roughly 9kB of storage for isogeny and
+ dualisogeny computations (see the tables in Appendix G.4). 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 1: An example of a Montgomery curve defined over the same field
+ as Curve25519 that is isomorphic to a Weierstrass curve with
+ hardcoded a=3 parameter is the Montgomery curve M_{A,B} with B=1 and
+ A=1410290 (or, if one wants the base point to still have
+ 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.
NOTE 2: While an implementation of Curve25519 via an isogenous
 Weierstrass curve with domain parameter a=3 requires a
 relatively large table (of size roughly 9kB), for the quadratic
 twist of Curve25519 (i.e., the Montgomery curve M_{A,B'} with
 A=486662 and B'=2) this implementation approach only requires a
 table of size less than 0.5kB (over 20x smaller), solely due to
 the fact that it is lisogenous to a Weierstrass curve with a=3
 parameter with relatively small parameter l=2 (compared to l=47,
 as is the case with Curve25519 itself).
+ Weierstrass curve with domain parameter a=3 requires a relatively
+ large table (of size roughly 9kB), for the quadratic twist of
+ Curve25519 (i.e., the Montgomery curve M_{A,B'} with A=486662 and
+ B'=2) this implementation approach only requires a table of size less
+ than 0.5kB (over 20x smaller), solely due to the fact that it is
+ lisogenous to a Weierstrass curve with a=3 parameter with
+ relatively small parameter l=2 (compared to l=47, as is the case with
+ Curve25519 itself).
6. Implementation Considerations
The efficiency of elliptic curve arithmetic is primarily determined
by the efficiency of its group operations (see Appendix C). Numerous
optimized formulae exist, such as the use of socalled Montgomery
ladders with Montgomery curves [MontLadder] or with Weierstrass
curves [WeiLadder], the use of hardcoded a=3 domain parameter for
Weierstrass curves [ECCIsogeny], and the use of hardcoded a=1
domain parameters for twisted Edwards curves [tEdFormulas]. These
@@ 416,21 +473,21 @@
Depending on the implementation strategy, the bitsize of q may also
facilitate reduced socalled "carryeffects" of integer arithmetic.
Most curves use a combination of these design philosophies. All NIST
curves [FIPS1864] and Brainpool curves [RFC5639] are Weierstrass
curves with a=3 domain parameter, thus facilitating more efficient
elliptic curve group operations (via socalled Jacobian coordinates).
The NIST curves and the Montgomery curve Curve25519 are defined over
prime fields, where the prime number has a special form, whereas the
Brainpool curves  by design  use a generic prime number. None of
 the NIST curves, nor the Brainpool curves, can be expressed as
+ the NIST prime curves, nor the Brainpool curves, can be expressed as
Montgomery or twisted Edwards curves, whereas  conversely 
Montgomery curves and twisted curves can be expressed as Weierstrass
curves.
While use of Wei25519 allows reuse of existing generic code that
implements short Weierstrass curves, such as the NIST curve P256, to
also implement the CFRG curves Curve25519 or Edwards25519, this
obviously does not result in an implementation of these CFRG curves
that exploits the specific structure of the underlying field or other
specific domain parameters (since generic). Reuse of generic code,
@@ 527,165 +583,312 @@
To prevent intraprotocol crossinstantiation attacks, ephemeral
private keys MUST NOT be reused between instantiations of ECDSA25519.
9. Privacy Considerations
The transformations between different curve models described in this
document are publicly known and, therefore, do not affect privacy
provisions.
 The randomized representation described in Appendix L.4 allows random
+ Use of a public key in any protocol for which successful execution
+ evidences knowledge of the corresponding private key implicitly
+ indicates the entity holding this private key. Reuse of this public
+ key with more than one protocol or more than one protocol
+ instantiation may, therefore, allow traceability of this entity. It
+ may also allow correlation of metadata communicated with this common
+ data element (e.g., different addressing information), even if an
+ observer cannot technically verify the binding of this metadata.
+
+ The randomized representation described in Appendix K.5 allows random
curve points to be represented as random pairs of field elements,
thereby assisting in obfuscating the presence of these curve points
in some applications.
10. IANA Considerations
 An object identifier is requested for curve Wei25519 and its use with
 ECDSA and cofactor ECDH, using the representation conventions of
 this document.
+ Code points are requested for curve Wei25519 and Wei448 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.4.
+ New code points would be required in case one wishes to specify one
+ or more other "offspring" protocols beyond those exemplified in
+ Section 4.4. Specification hereof is, however, outside scope of the
+ current document.
10.1. COSE Elliptic Curves Registration
+10.1. IANA Considerations for Wei25519
+10.1.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;
+ Change Controller: IESG;
+
Reference: Appendix E.3 of this specification;
Recommended: Yes.
(Note that The "kty" value for Wei25519 may be "OKP" or "EC2".)
10.2. COSE Algorithms Registration (1/2)
+10.1.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;
+ Description: ECDSA with SHA256 and curve Wei25519;
+
+ Change Controller: IESG;
Reference: Section 4.3 of this specification;
Recommended: Yes.
10.3. COSE Algorithms Registration (2/2)
+10.1.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;
+ Change Controller: IESG;
+
Reference: Section 4.1 of this specification (for key derivation,
see Section 11.1 of [RFC8152]);
Recommended: Yes.
10.4. JOSE Elliptic Curves Registration
+10.1.4. JOSE Elliptic Curves Registration
This section registers the following value in the IANA "JSON Web Key
Elliptic Curve" registry [IANA.JOSE.Curves].
Curve Name: Wei25519;
Curve Description: shortWeierstrass curve Wei25519;
 JOSE Implementation Requirements: optional;
+ JOSE Implementation Requirements: Optional;
 Change Controller: IANA;
+ Change Controller: IESG;
Reference: Appendix E.3 of this specification.
10.5. JOSE Algorithms Registration (1/2)
+10.1.5. JOSE Algorithms Registration (1/2)
This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDSA25519;
 Algorithm Description: ECDSA w/ SHA256 and curve Wei25519;
+ Algorithm Description: ECDSA using SHA256 and curve Wei25519;
+
Algorithm Usage Locations: alg;
 JOSE Implementation Requirements: optional;
+ JOSE Implementation Requirements: Optional;
 Change Controller: IANA;
+ Change Controller: IESG;
Reference: Section 4.3 of this specification;
 Algorithm Analysis Documents: Section 4.3 of this specification.
+ Algorithm Analysis Document(s): Section 4.3 of this specification.
10.6. JOSE Algorithms Registration (2/2)
+10.1.6. JOSE Algorithms Registration (2/2)
This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDH25519;
Algorithm Description: NISTcompliant cofactor DiffieHellman w/
curve Wei25519 and key derivation function HKDF SHA256;
Algorithm Usage Locations: alg;
 Change Controller: IANA;
+ JOSE Implementation Requirements: Optional;
+
+ Change Controller: IESG;
Reference: Section 4.1 of this specification (for key derivation,
see Section 5 of [SP80056c]);
 Algorithm Analysis Documents: Section 4.1 of this specification (for
 key derivation, see Section 5 of [SP80056c]).
+ Algorithm Analysis Document(s): Section 4.1 of this specification
+ (for key derivation, see Section 5 of [SP80056c]).
+
+10.2. IANA Considerations for Wei448
+
+10.2.1. COSE Elliptic Curves Registration
+
+ This section registers the following value in the IANA "COSE Elliptic
+ Curves" registry [IANA.COSE.Curves].
+
+ Name: Wei448;
+
+ Value: TBD (Requested value: 2);
+
+ Key Type: EC2 or OKP (where OKP uses the squeezed MSB/msb
+ representation of this specification);
+
+ Description: shortWeierstrass curve Wei448;
+
+ Change Controller: IESG;
+
+ Reference: Appendix M.3 of this specification;
+
+ Recommended: Yes.
+
+ (Note that The "kty" value for Wei448 may be "OKP" or "EC2".)
+
+10.2.2. COSE Algorithms Registration (1/2)
+
+ This section registers the following value in the IANA "COSE
+ Algorithms" registry [IANA.COSE.Algorithms].
+
+ Name: ECDSA448;
+
+ Value: TBD (Requested value: 21);
+
+ Description: ECDSA with SHAKE256 and curve Wei448;
+
+ Change Controller: IESG;
+
+ Reference: Section 4.4 of this specification;
+
+ Recommended: Yes.
+
+10.2.3. COSE Algorithms Registration (2/2)
+
+ This section registers the following value in the IANA "COSE
+ Algorithms" registry [IANA.COSE.Algorithms].
+
+ Name: ECDH448;
+
+ Value: TBD (Requested value: 22);
+
+ Description: NISTcompliant cofactor DiffieHellman w/ curve
+ Wei25519 and key derivation function HKDF SHA512;
+
+ Change Controller: IESG;
+
+ Reference: Section 4.4 of this specification (for key derivation,
+ see Section 11.1 of [RFC8152]);
+
+ Recommended: Yes.
+
+10.2.4. JOSE Elliptic Curves Registration
+
+ This section registers the following value in the IANA "JSON Web Key
+ Elliptic Curve" registry [IANA.JOSE.Curves].
+
+ Curve Name: Wei448;
+
+ Curve Description: shortWeierstrass curve Wei448;
+
+ JOSE Implementation Requirements: Optional;
+
+ Change Controller: IESG;
+ Reference: Appendix M.3 of this specification.
+
+10.2.5. JOSE Algorithms Registration (1/2)
+
+ This section registers the following value in the IANA "JSON Web
+ Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
+
+ Algorithm Name: ECDSA448;
+
+ Algorithm Description: ECDSA using SHAKE256 and curve Wei448;
+
+ Algorithm Usage Locations: alg;
+
+ JOSE Implementation Requirements: Optional;
+
+ Change Controller: IESG;
+
+ Reference: Section 4.4 of this specification;
+
+ Algorithm Analysis Document(s): Section 4.4 of this specification.
+
+10.2.6. JOSE Algorithms Registration (2/2)
+
+ This section registers the following value in the IANA "JSON Web
+ Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
+
+ Algorithm Name: ECDH448;
+
+ Algorithm Description: NISTcompliant cofactor DiffieHellman w/
+ curve Wei25519 and key derivation function HKDF SHA512;
+
+ Algorithm Usage Locations: alg;
+
+ JOSE Implementation Requirements: Optional;
+
+ Change Controller: IESG;
+
+ Reference: Section 4.4 of this specification (for key derivation,
+ see Section 5 of [SP80056c]);
+
+ Algorithm Analysis Document(s): Section 4.4 of this specification
+ (for key derivation, see Section 5 of [SP80056c]).
11. 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 and Vasily Nikolaev for their careful reviews.
12. References
12.1. Normative References
[ANSIX9.62]
ANSI X9.622005, "Public Key Cryptography for the
Financial Services Industry: The Elliptic Curve Digital
Signature Algorithm (ECDSA)", American National Standard
for Financial Services, Accredited Standards Committee X9,
Inc, Anapolis, MD, 2005.
+ [FIPS1804]
+ FIPS 1804, "Secure Hash Standard (SHS), Federal
+ Information Processing Standards Publication 1804", US
+ Department of Commerce/National Institute of Standards and
+ Technology, Gaithersburg, MD, August 2015.
+
[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.
+ [FIPS202]
+ FIPS 202, "SHA3 Standard: PermutationBased Hash and
+ ExtendableOutput Functions, Federal Information
+ Processing Standards Publication 202", US Department of
+ Commerce/National Institute of Standards and
+ Technology, Gaithersburg, MD, August 2015.
+
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
.
[RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography
(ECC) Brainpool Standard Curves and Curve Generation",
RFC 5639, DOI 10.17487/RFC5639, March 2010,
.
@@ 705,20 +908,24 @@
[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,
.
+ [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
+ 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
+ May 2017, .
+
[SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0",
Standards for Efficient Cryptography, , June 2009.
[SEC2] SEC2, "SEC 2: Elliptic Curve Cryptography, Version 2.0",
Standards for Efficient Cryptography, , January 2010.
[SP80056a]
NIST SP 80056a, "Recommendation for PairWise Key
Establishment Schemes Using Discrete Log Cryptography,
Revision 3", US Department of Commerce/National Institute
@@ 799,106 +1006,117 @@
Elliptic Curves of Prime Order as Uniform Random Strings",
Financial Cryptography 2014, Lecture Notes in Computer
Science, Vol. 8437, New York: SpringerVerlag, 2014.
[WeiLadder]
T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve
Multiplication Resistant Against Side Channel Attacks",
Centre for Applied Cryptographic Research, Corr 200203,
2002.
Appendix A. Some (nonBinary) Elliptic Curves
+Appendix A. Some (NonBinary) Elliptic Curves
A.1. Curves in shortWeierstrass Form
+ This section defines the three different curve models we consider,
+ viz. shortWeierstrass curves, Montgomery curves, and twisted Edwards
+ curves.
+
+A.1. Curves in ShortWeierstrass Form
Let GF(q) denote the finite field with q elements, where q is an odd
prime power and where q is not divisible by three. Let W_{a,b} be
the Weierstrass curve with defining equation Y^2 = X^3 + a*X + b,
where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is
nonzero. The points of W_{a,b} are the ordered pairs (X, Y) whose
coordinates are elements of GF(q) and that satisfy the defining
equation (the socalled affine points), together with the special
point O (the socalled "point at infinity"). This set forms a group
 under addition, via the socalled "secantandtangent" rule, where
 the point at infinity serves as the identity element. See
 Appendix C.1 for details of the group operation.
+ under addition, via the socalled "chordandtangent" rule, where the
+ point at infinity serves as the identity element. See Appendix C.1
+ for details of the group operation.
A.2. Montgomery Curves
Let GF(q) denote the finite field with q elements, where q is an odd
prime power. Let M_{A,B} be the Montgomery curve with defining
equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q)
and where A is unequal to (+/)2 and where B is nonzero. The points
of M_{A,B} are the ordered pairs (u, v) whose coordinates are
elements of GF(q) and that satisfy the defining equation (the so
called affine points), together with the special point O (the so
called "point at infinity"). This set forms a group under addition,
 via the socalled "secantandtangent" rule, where the point at
+ via the socalled "chordandtangent" rule, where the point at
infinity serves as the identity element. See Appendix C.2 for
details of the group operation.
A.3. Twisted Edwards Curves
Let GF(q) denote the finite field with q elements, where q is an odd
prime power. Let E_{a,d} be the twisted Edwards curve with defining
equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct
nonzero elements of GF(q). The points of E_{a,d} are the ordered
pairs (x, y) whose coordinates are elements of GF(q) and that satisfy
the defining equation (the socalled affine points). It can be shown
that this set forms a group under addition if a is a square in GF(q),
whereas d is not, where the point O:=(0, 1) serves as the identity
element. (Note that the identity element satisfies the defining
equation.) See Appendix C.3 for details of the group operation.
An Edwards curve is a twisted Edwards curve with a=1.
Appendix B. Elliptic Curve Nomenclature and Finite Fields
+ This section provides brief background information on elliptic curves
+ and finite fields that should be sufficient to understand
+ constructions and examples in this document.
+
B.1. Elliptic Curve Nomenclature
Each curve defined in Appendix A forms a commutative group under
addition (denoted by '+'). In Appendix C we specify the group laws,
which depend on the curve model in question. For completeness, we
here include some common elliptic curve nomenclature and basic
properties (primarily so as to keep this document selfcontained).
These notions are mainly used in Appendix E and Appendix G and not
essential for our exposition. This section can be skipped at first
reading.
Any point P of a curve E is a generator of the cyclic subgroup
(P):={k*P  k = 0, 1, 2,...} of the curve. (Here, k*P denotes the
sum of k copies of P, where 0*P is the identity element O of the
 curve.) If (P) has cardinality l, then l is called the order of P.
 The order of curve E is the cardinality of the set of its points,
+ curve; k*P is commonly referred to as scalar multiplication of P by
+ k.) If (P) has cardinality l, then l is called the order of P. The
+ order of curve E is the cardinality of the set of its points,
commonly denoted by E. A curve is cyclic if it is generated by some
point of this curve. All curves of prime order are cyclic, while all
curves of order h*n, where n is a large prime number and where h is a
small number (the socalled cofactor), have a large cyclic subgroup
of prime order n. In this case, a generator of order n is called a
base point, commonly denoted by G. A point of order dividing h is
said to be in the small subgroup. For curves of prime order, this
small subgroup is the singleton set, consisting of only the identity
 element O. If a point is not in the small subgroup, it has order at
 least n.
+ element O. A point that is not in the small subgroup is said to be a
+ highorder point (since it has order at least n).
If R is a point of the curve that is also contained in (P), there is
a unique integer k in the interval [0, l1] so that R=k*P, where l is
the order of P. This number is called the discrete logarithm of R to
the base P. The discrete logarithm problem is the problem of finding
the discrete logarithm of R to the base P for any two points P and R
of the curve, if such a number exists.
If P is a fixed base point G of the curve, the pair (k, R:=k*G) is
commonly called a publicprivate key pair, the integer k the private
key, and the point R the corresponding public key. The private key k
can be represented as an integer in the interval [0,n1], where G has
 order n.
+ order n. If this representation is nonzero, R has order n;
+ otherwise, it has order one and is the identity element O of the
+ curve.
In this document, a quadratic twist of a curve E defined over a field
GF(q) is a curve E' related to E, with cardinality E',
where E+E'=2*(q+1). If E is a curve in one of the curve models
specified in this document, a quadratic twist of this curve can be
expressed using the same curve model, although (naturally) with its
own curve parameters. Two curves E and E' defined over a field GF(q)
are said to be isogenous if these have the same order and are said to
be isomorphic if these have the same group structure. Note that
isomorphic curves have necessarily the same order and are, thus, a
@@ 919,159 +1137,174 @@
The group laws in Appendix C are mostly expressed in terms of affine
points, but can also be expressed in terms of the representation of
these points in projective coordinates, thereby allowing clearing of
denominators. The group laws may also involve nonaffine points
(such as the point at infinity O of a Weierstrass curve or of a
Montgomery curve). Those can also be represented in projective
coordinates. Further details are out of scope.
B.2. Finite Fields
 The field GF(q), where q is an odd prime power, is defined as
 follows.
+ The field GF(q), where q is a prime power, is defined as follows.
 If p is a prime number, the field GF(p) consists of the integers in
 the interval [0,p1] and two binary operations on this set: addition
 and multiplication modulo p.
+ If q:=p is a prime number, the field GF(p) consists of the integers
+ in the interval [0,p1] and two binary operations on this set:
+ addition and multiplication modulo p. This field is commonly called
+ a prime field.
 If q=p^m and m>0, the field GF(q) is defined in terms of an
 irreducible polynomial f(z) in z of degree m with coefficients in
 GF(p) (i.e., f(z) cannot be written as the product of two polynomials
 in z of lower degree with coefficients in GF(p)): in this case, GF(q)
 consists of the polynomials in z of degree smaller than m with
 coefficients in GF(p) and two binary operations on this set:
 polynomial addition and polynomial multiplication modulo the
 irreducible polynomial f(z). By definition, each element x of GF(q)
 is a polynomial in z of degree smaller than m and can, therefore, be
 uniquely represented as a vector (x_{m1}, x_{m2}, ..., x_1, x_0) of
 length m with coefficients in GF(p), where x_i is the coefficient of
 z^i of polynomial x. Note that this representation depends on the
+ If q:=p^m, where p is a prime number and where m>0, the field GF(q)
+ is defined in terms of an irreducible polynomial f(z) in z of degree
+ m with coefficients in GF(p) (i.e., f(z) cannot be written as the
+ product of two polynomials in z of lower degree with coefficients in
+ GF(p)): in this case, GF(q) consists of the polynomials in z of
+ degree smaller than m with coefficients in GF(p) and two binary
+ operations on this set: polynomial addition and polynomial
+ multiplication modulo the irreducible polynomial f(z). By
+ definition, each element x of GF(q) is a polynomial in z of degree
+ smaller than m and can, therefore, be uniquely represented as a
+ vector (x_{m1}, x_{m2}, ..., x_1, x_0) of length m with
+ coefficients in GF(p), where x_i is the coefficient of z^i of
+ polynomial x. Note that this representation depends on the
irreducible polynomial f(z) of the field GF(p^m) in question (which
is often fixed in practice). Note that GF(q) contains the prime
 field GF(p) as a subset. If m=1, we always pick f(z):=z, so that the
 definitions of GF(p) and GF(p^1) above coincide. If m>1, then GF(q)
 is called a (nontrivial) extension field over GF(p). The number p is
+ field GF(p) as a subset. If m=1, the definitions of GF(p) and
+ GF(p^1) above coincide, since each nonzero element of GF(p) can be
+ viewed as a polynomial in z of degree zero. If m>1, then GF(q) is
+ called a (nontrivial) extension field of GF(p). The number p is
called the characteristic of GF(q).
A field element y is called a square in GF(q) if it can be expressed
as y:=x^2 for some x in GF(q); it is called a nonsquare in GF(q)
otherwise. If y is a square in GF(q), we denote by sqrt(y) one of
its square roots (the other one being sqrt(y)). For methods for
computing square roots and inverses in GF(q)  if these exist  see
 Appendix L.1 and Appendix L.2, respectively. For methods for mapping
+ Appendix K.1 and Appendix K.2, respectively. For methods for mapping
a nonzero field element that is not a square in GF(q) to a point of a
 curve, see Appendix L.3.
+ curve, see Appendix K.3.
NOTE: The curves in Appendix E and Appendix G are all defined over a
prime field GF(p), thereby reducing all operations to simple modular
integer arithmetic. Strictly speaking we could, therefore, have
refrained from introducing extension fields. Nevertheless, we
included the more general exposition, so as to accommodate potential
introduction of new curves that are defined over a (nontrivial)
extension field at some point in the future. This includes curves
proposed for postquantum isogenybased schemes, which are defined
over a quadratic extension field (i.e., where q:=p^2), and elliptic
curves used with pairingbased cryptography. The exposition in
either case is almost the same and now automatically yields, e.g.,
data conversion routines for any finite field object (see
 Appendix J). Readers not interested in this, could simply view all
+ Appendix I). Readers not interested in this, could simply view all
fields as prime fields.
Appendix C. Elliptic Curve Group Operations
C.1. Group Law for Weierstrass Curves
+ This section specifies group operations for elliptic curves in short
+ Weierstrass form, for Montgomery curves, and for twisted Edwards
+ curves.
+
+C.1. Group Laws for Weierstrass Curves
For each point P of the Weierstrass curve W_{a,b}, the point at
infinity O serves as identity element, i.e., P + O = O + P = P.
For each affine point P:=(X, Y) of the Weierstrass curve W_{a,b}, the
 point P is the point (X, Y) and one has P + (P) = O.
+ point P is the point (X, Y) and one has P + (P) = O (i.e., P is
+ the inverse of P). For the point at infinity O, one has O:=O.
Let P1:=(X1, Y1) and P2:=(X2, Y2) be distinct affine points of the
Weierstrass curve W_{a,b} and let Q:=P1 + P2, where Q is not the
 identity element. Then Q:=(x, y), where
+ identity element. Then Q:=(X, Y), where
X + X1 + X2 = lambda^2 and Y + Y1 = lambda*(X1  X), where
lambda:= (Y2  Y1)/(X2  X1).
Let P:=(X1, Y1) be an affine point of the Weierstrass curve W_{a,b}
and let Q:=2*P, where Q is not the identity element. Then Q:=(X, Y),
where
X + 2*X1 = lambda^2 and Y + Y1 = lambda*(X1  X), where
lambda:=(3*X1^2 + a)/(2*Y1).
 From the group laws above it follows that if P=(X, Y), P1=k*P=(X1,
 Y1), and P2=(k+1)*P=(X2, Y2) are distinct affine points of the
 Weierstrass curve W_{a,b} and if Y is nonzero, then the Ycoordinate
 of P1 can be expressed in terms of the Xcoordinates of P, P1, and
 P2, and the Ycoordinate of P, as
+ From the group laws above it follows that if P=(X, Y), P1=(X1, Y1),
+ and P2=(X2, Y2) are distinct affine points of the Weierstrass curve
+ W_{a,b} with P2:=P+P1 and if Y is nonzero, then the Ycoordinate of
+ P1 can be expressed in terms of the Xcoordinates of P, P1, and P2,
+ and the Ycoordinate of P, since
 Y1=((X*X1+a)*(X+X1)+2*bX2*(XX1)^2)/(2*Y).
+ 2*Y*Y1=(X*X1+a)*(X+X1)+2*bX2*(XX1)^2.
This property allows recovery of the Ycoordinate of a point P1=k*P
that is computed via the socalled Montgomery ladder, where P is an
affine point with nonzero Ycoordinate (i.e., it does not have order
 two). Further details are out of scope.
+ two). For future reference, note that the expression above uniquely
+ determines the Xcoordinate of P2 in terms of the Xcoordinates of P
+ and P1 and the product of their Ycoordinates. Further details are
+ out of scope.
C.2. Group Law for Montgomery Curves
+C.2. Group Laws for Montgomery Curves
For each point P of the Montgomery curve M_{A,B}, the point at
infinity O serves as identity element, i.e., P + O = O + P = P.
For each affine point P:=(u, v) of the Montgomery curve M_{A,B}, the
 point P is the point (u, v) and one has P + (P) = O.
+ point P is the point (u, v) and one has P + (P) = O (i.e., P is
+ the inverse of P). For the point at infinity O, one has O:=O.
Let P1:=(u1, v1) and P2:=(u2, v2) be distinct affine points of the
Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the
identity element. Then Q:=(u, v), where
u + u1 + u2 = B*lambda^2  A and v + v1 = lambda*(u1  u), where
lambda:=(v2  v1)/(u2  u1).
Let P:=(u1, v1) be an affine point of the Montgomery curve M_{A,B}
and let Q:=2*P, where Q is not the identity element. Then Q:=(u, v),
where
u + 2*u1 = B*lambda^2  A and v + v1 = lambda*(u1  u), where
lambda:=(3*u1^2 + 2*A*u1+1)/(2*B*v1).
 From the group laws above it follows that if P=(u, v), P1=k*P=(u1,
 v1), and P2=(k+1)*P=(u2, v2) are distinct affine points of the
 Montgomery curve M_{A,B} and if v is nonzero, then the vcoordinate
 of P1 can be expressed in terms of the ucoordinates of P, P1, and
 P2, and the vcoordinate of P, as
+ From the group laws above it follows that if P=(u, v), P1=(u1, v1),
+ and P2=(u2, v2) are distinct affine points of the Montgomery curve
+ M_{A,B} with P2:=P+P1 and if v is nonzero, then the vcoordinate of
+ P1 can be expressed in terms of the ucoordinates of P, P1, and P2,
+ and the vcoordinate of P, since
 v1=((u*u1+1)*(u+u1+2*A)2*Au2*(uu1)^2)/(2*B*v).
+ 2*B*v*v1=(u*u1+1)*(u+u1+2*A)2*Au2*(uu1)^2.
This property allows recovery of the vcoordinate of a point P1=k*P
that is computed via the socalled Montgomery ladder, where P is an
affine point with nonzero vcoordinate (i.e., it does not have order
 one or two). Further details are out of scope.
+ two). For future reference, note that the expression above uniquely
+ determines the ucoordinate of P2 in terms of the ucoordinates of P
+ and P1 and the product of their vcoordinates. Further details are
+ out of scope.
C.3. Group Law for Twisted Edwards Curves
+C.3. Group Laws for Twisted Edwards Curves
Note: The group laws below hold for twisted Edwards curves E_{a,d}
where a is a square in GF(q), whereas d is not. In this case, the
addition formulae below are defined for each pair of points, without
exceptions. Generalizations of this group law to other twisted
Edwards curves are out of scope.
For each point P of the twisted Edwards curve E_{a,d}, the point
O:=(0,1) serves as identity element, i.e., P + O = O + P = P.
For each point P:=(x, y) of the twisted Edwards curve E_{a,d}, the
 point P is the point (x, y) and one has P + (P) = O.
+ point P is the point (x, y) and one has P + (P) = O (i.e., P is
+ the inverse of P).
Let P1:=(x1, y1) and P2:=(x2, y2) be points of the twisted Edwards
curve E_{a,d} and let Q:=P1 + P2. Then Q:=(x, y), where
x = (x1*y2 + x2*y1)/(1 + d*x1*x2*y1*y2) and
y = (y1*y2  a*x1*x2)/(1  d*x1*x2*y1*y2).
Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and
let Q:=2*P. Then Q:=(x, y), where
@@ 1079,45 +1312,48 @@
x = (2*x1*y1)/(1 + d*x1^2*y1^2) and
y = (y1^2  a*x1^2)/(1  d*x1^2*y1^2).
Note that one can use the formulae for point addition for point
doubling, taking inverses, and adding the identity element as well
(i.e., the point addition formulae are uniform and complete (subject
to our Note above)).
From the group laws above (subject to our Note above) it follows that
 if P=(x, y), P1=k*P=(x1, y1), and P2=(k+1)*P=(x2, y2) are affine
 points of the twisted Edwards curve E_{a,d} and if x is nonzero, then
 the xcoordinate of P1 can be expressed in terms of the ycoordinates
 of P, P1, and P2, and the xcoordinate of P, as

 x1=(y*y1y2)/(x*(ad*y*y1*y2)).
+ if P=(x, y), P1=(x1, y1), and P2=P=(x2, y2) are points of the twisted
+ Edwards curve E_{a,d} with P2:=P+P1 and if x is nonzero, then the
+ xcoordinate of P1 can be expressed in terms of the ycoordinates of
+ P, P1, and P2, and the xcoordinate of P, since
+ x*x1*(ad*y*y1*y2)=y*y1y2.
 This property allows recovery of the xcoordinate of a point P1=k*P
 that is computed via the socalled Montgomery ladder, where P is an
 affine point with nonzero xcoordinate (i.e., it does not have order
 one or two). Further details are out of scope.
+ (Here, observe that ad*y*y1*y2 is nonzero per our Note above.) This
+ property allows recovery of the xcoordinate of a point P1=k*P that
+ is computed via the socalled Montgomery ladder, where P is an affine
+ point with nonzero xcoordinate (i.e., it does not have order one or
+ two). For future reference, note that the group law (subject to our
+ Note above) uniquely determines the ycoordinate of P2 in terms of
+ the ycoordinates of P and P1 and the product of their xcoordinates.
+ Further details are out of scope.
Appendix D. Relationship Between Curve Models
The nonbinary curves specified in Appendix A are expressed in
different curve models, viz. as curves in shortWeierstrass form, as
Montgomery curves, or as twisted Edwards curves. These curve models
are related, as follows.
D.1. Mapping between Twisted Edwards Curves and Montgomery Curves
One can map points of the Montgomery curve M_{A,B} to points of the
twisted Edwards curve E_{a,d}, where a:=(A+2)/B and d:=(A2)/B and,
conversely, map points of the twisted Edwards curve E_{a,d} to points
 of the Montgomery curve M_{A,B}, where A:=2(a+d)/(ad) and where
+ of the Montgomery curve M_{A,B}, where A:=2*(a+d)/(ad) and where
B:=4/(ad). For twisted Edwards curves we consider (i.e., those
where a is a square in GF(q), whereas d is not), this defines a one
toone correspondence, which  in fact  is an isomorphism between
M_{A,B} and E_{a,d}, thereby showing that, e.g., the discrete
logarithm problem in either curve model is equally hard.
For the Montgomery curves and twisted Edwards curves we consider, the
mapping from M_{A,B} to E_{a,d} is defined by mapping the point at
infinity O and the point (0, 0) of order two of M_{A,B} to,
respectively, the point (0, 1) and the point (0, 1) of order two of
@@ 1140,43 +1376,44 @@
One can map points of the Montgomery curve M_{A,B} to points of the
Weierstrass curve W_{a,b}, where a:=(3A^2)/(3*B^2) and
b:=(2*A^39*A)/(27*B^3). This defines a onetoone correspondence,
which  in fact  is an isomorphism between M_{A,B} and W_{a,b},
thereby showing that, e.g., the discrete logarithm problem in either
curve model is equally hard.
The mapping from M_{A,B} to W_{a,b} is defined by mapping the point
at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while
mapping each other point (u,v) of M_{A,B} to the point
 (X,Y):=((u+A/3)/B,v/B) of W_{a,b}. Note that not all Weierstrass
 curves can be injectively mapped to Montgomery curves, since the
 latter have a point of order two and the former may not. In
 particular, if a Weierstrass curve has prime order, such as is the
 case with the socalled "NIST curves", this inverse mapping is not
 defined.
+ (X,Y):=((u+A/3)/B,v/B) of W_{a,b}.
+
+ Note that not all Weierstrass curves can be injectively mapped to
+ Montgomery curves, since the latter have a point of order two and the
+ former may not. In particular, if a Weierstrass curve has prime
+ order, such as is the case with the socalled "NIST prime curves",
+ this inverse mapping is not defined.
If the Weierstrass curve W_{a,b} has a point (alpha,0) of order two
and c:=a+3*(alpha)^2 is a square in GF(q), one can map points of this
curve to points of the Montgomery curve M_{A,B}, where A:=3*alpha/
gamma and B:=1/gamma and where gamma is any square root of c. In
this case, the mapping from W_{a,b} to M_{A,B} is defined by mapping
the point at infinity O of W_{a,b} to the point at infinity O of
M_{A,B}, while mapping each other point (X,Y) of W_{a,b} to the point
(u,v):=((Xalpha)/gamma,Y/gamma) of M_{A,B}. As before, this defines
a onetoone correspondence, which  in fact  is an isomorphism
between W_{a,b} and M_{A,B}. It is easy to see that the mapping from
W_{a,b} to M_{A,B} and that from M_{A,B} to W_{a,b} (if defined) are
each other's inverse.
This mapping can be used to implement elliptic curve group operations
originally defined for a twisted Edwards curve or for a Montgomery
 curve using group operations on the corresponding elliptic curve in
+ curve using group operations for the corresponding elliptic curve in
shortWeierstrass form and translating the result back to the
original curve, thereby potentially allowing code reuse.
Note that implementations for elliptic curves with shortWeierstrass
form that hardcode the domain parameter a to a= 3 (which value is
known to allow more efficient implementations) cannot always be used
this way, since the curve W_{a,b} resulting from an isomorphic
mapping cannot always be expressed as a Weierstrass curve with a=3
via a coordinate transformation. For more details, see Appendix F.
@@ 1185,20 +1422,23 @@
One can map points of the twisted Edwards curve E_{a,d} to points of
the Weierstrass curve W_{a,b}, via function composition, where one
uses the isomorphic mapping between twisted Edwards curves and
Montgomery curves of Appendix D.1 and the one between Montgomery and
Weierstrass curves of Appendix D.2. Obviously, one can use function
composition (now using the respective inverses  if these exist) to
realize the inverse of this mapping.
Appendix E. Curve25519 and Cousins
+ This section introduces curves related to Curve25519 and explains
+ their relationships.
+
E.1. Curve Definition and Alternative Representations
The elliptic curve Curve25519 is the Montgomery curve M_{A,B} defined
over the prime field GF(p), with p:=2^{255}19, where A:=486662 and
B:=1. This curve has order h*n, where h=8 and where n is a prime
number. For this curve, A^24 is not a square in GF(p), whereas A+2
is. The quadratic twist of this curve has order h1*n1, where h1=4
and where n1 is a prime number. For this curve, the base point is
the point (Gu, Gv), where Gu=9 and where Gv is an odd integer in the
interval [0, p1].
@@ 1272,21 +1513,21 @@
(0,1) and the point (0,1) of order two of Edwards25519 correspond
to, respectively, the point at infinity O and the point (A/3, 0) of
order two of Wei25519 and where each other point (x, y) of
Edwards25519 corresponds to the point (X, Y):=((1+y)/(1y)+A/3,
c*(1+y)/((1y)*x)) of Wei25519, where c was defined before. (Here,
we used the mapping of Appendix D.3.) The inverse mapping from
Wei25519 to Edwards25519 is defined by mapping the point at infinity
O and the point (A/3, 0) of order two of Wei25519 to, respectively,
the identity element (0,1) and the point (0,1) of order two of
Edwards25519 and having each other point (X, Y) of Wei25519
 correspond to the point (c*(3*XA)/(3*Y), (3*XA3)/(3*XA+3)) of
+ correspond to the point (c*(XA/3)/Y, (XA/31)/(XA/3+1)) of
Edwards25519.
Note that these mappings can be easily realized if points are
represented in projective coordinates, using a few field
multiplications only, thus allowing switching between alternative
curve representations with negligible relative incremental cost.
E.3. Domain Parameters
The parameters of the Montgomery curve and the corresponding
@@ 1404,23 +1644,24 @@
The mapping from E_{a,d} to E_{a',d'} is defined by mapping the point
(x,y) of E_{a,d} to the point (x', y'):=(s*x, y) of E_{a',d'}. The
inverse mapping from E_{a',d'} to E_{a,d} is defined by mapping the
point (x', y') of E_{a',d'} to the point (x, y):=(x'/s, y') of
E_{a,d}.
Implementations may take advantage of this mapping to carry out
elliptic curve group operations originally defined for a twisted
Edwards curve with generic domain parameters a and d on a
corresponding isomorphic twisted Edwards curve with domain parameters
 a' and d' that have a more special form, which are known to allow for
 more efficient implementations of addition laws. In particular, it
 is known that such efficiency improvements exist if a':=1 (see
+ a' and d' that have a more special form and that are known to allow
+ for more efficient implementations of addition laws and translating
+ the result back to the original curve. In particular, it is known
+ that such efficiency improvements exist if a':=(+/)1 (see
[tEdFormulas]).
F.2. Isomorphic Mapping between Montgomery Curves
One can map points of the Montgomery curve M_{A,B} to points of the
Montgomery curve M_{A',B'}, where A:=A' and B:=B'*s^2 for some
nonzero element s of GF(q). This defines a onetoone
correspondence, which  in fact  is an isomorphism between M_{A,B}
and M_{A',B'}.
@@ 1439,28 +1680,29 @@
In this case, the mapping from M_{A,B} to M_{A',B'} is defined by
mapping the point at infinity O of M_{A,B} to the point at infinity O
of M_{A',B'}, while mapping each other point (u,v) of M_{A,B} to the
point (u',v'):=(u,v) of M_{A',B'}. The inverse mapping from
M_{A',B'} to M_{A,B} is defined by mapping the point at infinity O of
M_{A',B'} to the point at infinity O of M_{A,B}, while mapping each
other point (u',v') of M_{A',B'} to the point (u,v):=(u',v') of
M_{A,B}.
 Implementations may take advantage of this mapping to carry out
+ Implementations may take advantage of these mappings to carry out
elliptic curve groups operations originally defined for a Montgomery
curve with generic domain parameters A and B on a corresponding
isomorphic Montgomery curve with domain parameters A' and B' that
 have a more special form, which is known to allow for more efficient
 implementations of addition laws. In particular, it is known that
 such efficiency improvements exist if B' assumes a small absolute
 value, such as B':=(+/)1. (see [MontLadder]).
+ have a more special form and that are known to allow for more
+ efficient implementations of addition laws and translating the result
+ back to the original curve. In particular, it is known that such
+ efficiency improvements exist if B' assumes a small absolute value,
+ such as B':=(+/)1. (see [MontLadder]).
F.3. Isomorphic Mapping between Weierstrass Curves
One can map points of the Weierstrass curve W_{a,b} to points of the
Weierstrass curve W_{a',b'}, where a':=a*s^4 and b':=b*s^6 for some
nonzero element s of GF(q). This defines a onetoone
correspondence, which  in fact  is an isomorphism between W_{a,b}
and W_{a',b'}.
The mapping from W_{a,b} to W_{a',b'} is defined by mapping the point
@@ 1469,29 +1711,30 @@
(X',Y'):=(X*s^2, Y*s^3) of W_{a',b'}. The inverse mapping from
W_{a',b'} to W_{a,b} is defined by mapping the point at infinity O of
W_{a',b'} to the point at infinity O of W_{a,b}, while mapping each
other point (X', Y') of W_{a',b'} to the point (X,Y):=(X'/s^2,Y'/s^3)
of W_{a,b}.
Implementations may take advantage of this mapping to carry out
elliptic curve group operations originally defined for a Weierstrass
curve with generic domain parameters a and b on a corresponding
isomorphic Weierstrass curve with domain parameter a' and b' that
 have a more special form, which is known to allow for more efficient
 implementations of addition laws, and translating the result back to
 the original curve. In particular, it is known that such efficiency
 improvements exist if a'=3 (mod p), where p is the characteristic of
 GF(q), and one uses socalled Jacobian coordinates with a particular
 projective version of the addition laws of Appendix C.1. While not
 all Weierstrass curves can be put into this form, all traditional
 NIST curves have domain parameter a=3, while all Brainpool curves
 [RFC5639] are isomorphic to a Weierstrass curve of this form.
+ have a more special form and that are known to allow for more
+ efficient implementations of addition laws and translating the result
+ back to the original curve. In particular, it is known that such
+ efficiency improvements exist if a'=3 (mod p), where p is the
+ characteristic of GF(q), and one uses socalled Jacobian coordinates
+ with a particular projective version of the addition laws of
+ Appendix C.1. While not all Weierstrass curves can be put into this
+ form, all traditional NIST curves have domain parameter a=3, while
+ all Brainpool curves [RFC5639] are isomorphic to a Weierstrass curve
+ of this form via the above mapping.
Note that implementations for elliptic curves with shortWeierstrass
form that hardcode the domain parameter a to a= 3 cannot always be
used this way, since the curve W_{a,b} cannot always be expressed in
terms of a Weierstrass curve with a'=3 via a coordinate
transformation: this only holds if a'/a is a fourth power in GF(q)
(see Section 3.1.5 of [GECC]). However, even in this case, one can
still express the curve W_{a,b} as a Weierstrass curve with a small
domain parameter value a', thereby still allowing a more efficient
implementation than with a general domain parameter value a.
@@ 1511,35 +1754,38 @@
defined for a Weierstrass curve with domain parameter a unequal to 3
(mod p) on a corresponding isogenous Weierstrass curve with domain
parameter a'=3 (mod p) and translating the result back to the
original curve.
In this case, the mapping from W_{a,b} to W_{a',b'} is defined by
mapping the point at infinity O of W_{a,b} to the point at infinity O
of W_{a',b'}, while mapping each other point (X,Y) of W_{a,b} to the
point (X',Y'):=(u(X)/w(X)^2,Y*v(X)/w(X)^3) of W_{a',b'}. Here, u(X),
v(X), and w(X) are polynomials in X that depend on the isogeny in
 question. The inverse mapping from W_{a',b'} to W_{a,b} is again an
 isogeny and defined by mapping the point at infinity O of W_{a',b'}
+ question, as do domain parameters a' and b'. The inverse mapping
+ from W_{a',b'} to W_{a,b} is again an isogeny (called the dual
+ isogeny) and defined by mapping the point at infinity O of W_{a',b'}
to the point at infinity O of W_{a,b}, while mapping each other point
(X', Y') of W_{a',b'} to the point
(X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of W_{a,b}, where 
again  u'(X'), v'(X'), and w'(X') are polynomials in X' that depend
on the isogeny in question. These mappings have the property that
their composition is not the identity mapping (as was the case with
the isomorphic mappings discussed in Appendix F.3), but rather a
fixed multiple hereof: if this multiple is l then the isogeny is
called an isogeny of degree l (or lisogeny) and u, v, and w (and,
similarly, u', v', and w') are polynomials of degrees l, 3*(l1)/2,
and (l1)/2, respectively. Note that an isomorphism is simply an
isogeny of degree l=1. Details of how to determine isogenies are out
 of scope of this document.
+ of scope of this document. The above formulas assume that the
+ isogeny has odd degree (i.e., l is odd); detailed formulas for even
+ degree isogenies are similar, but out of scope.
Implementations may take advantage of this mapping to carry out
elliptic curve group operations originally defined for a Weierstrass
curve with a generic domain parameter a on a corresponding isogenous
Weierstrass curve with domain parameter a'=3 (mod p), where one can
use socalled Jacobian coordinates with a particular projective
version of the addition laws of Appendix C.1. Since all traditional
NIST curves have domain parameter a=3, while all Brainpool curves
[RFC5639] are isomorphic to a Weierstrass curve of this form, this
allows taking advantage of existing implementations for these curves
@@ 1555,20 +1801,23 @@
the isogeny has low degree l). Note, however, that this does require
storage of the polynomial coefficients of the isogeny and dual
isogeny involved. This illustrates that lowdegree isogenies are to
be preferred, since an lisogeny (usually) requires storing roughly
6*l elements of GF(q). While there are many isogenies, we therefore
only consider those with the desired property with lowest possible
degree.
Appendix G. Further Cousins of Curve25519
+ This section introduces some further curves related to Curve25519 and
+ explains their relationships.
+
G.1. Further Alternative Representations
The Weierstrass curve Wei25519 is isomorphic to the Weierstrass curve
Wei25519.2 defined over GF(p), with as base point the pair (G2X,G2Y),
and isogenous to the Weierstrass curve Wei25519.3 defined over
GF(p), with as base point the pair (G3X, G3Y), where parameters are
as specified in Appendix G.3 and where the related mappings are as
specified in Appendix G.2.
G.2. Further Switching
@@ 1590,37 +1839,37 @@
the affine point (X', Y') of Wei25519.2 to (X,Y):=(X'/s^2,Y'/s^3) of
Wei25519, while mapping the point at infinity O of Wei25519.2 to the
point at infinity O of Wei25519. Note that this mapping (and its
inverse) involves a modular multiplication of both coordinates with
fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which
can be precomputed.
Each affine point (X,Y) of Wei25519 corresponds to the point
(X',Y'):=(X1*t^2,Y1*t^3) of Wei25519.3, where
(X1,Y1)=(u(X)/w(X)^2,Y*v(X)/w(X)^3), where u, v, and w are the
 polynomials with coefficients in GF(p) as defined in Appendix H.1 and
 where t is the element of GF(p) defined by
+ polynomials with coefficients in GF(p) as defined in Appendix G.4.1
+ and where t is the element of GF(p) defined by
t 35728133398289175649586938605660542688691615699169662967154525084
644181596229
(=0x4efd6829 88ff8526 e189f712 5999550c e9ef729b ed1a7015
73b1bab8 8bfcd845),
while the point at infinity of Wei25519 corresponds to the point at
infinity of Wei25519.3. (Here, we used the isogenous mapping of
Appendix F.4.) Under this isogenous mapping, the base point (GX,GY)
of Wei25519 corresponds to the base point (G3X,G3Y) of Wei25519.3.
The dual isogeny maps the affine point (X',Y') of Wei25519.3 to the
affine point (X,Y):=(u'(X1)/w'(X1)^2,Y1*v'(X1)/w'(X1)^3) of Wei25519,
where (X1,Y1)=(X'/t^2,Y'/t^3) and where u', v', and w' are the
 polynomials with coefficients in GF(p) as defined in Appendix H.2,
+ polynomials with coefficients in GF(p) as defined in Appendix G.4.2,
while mapping the point at infinity O of Wei25519.3 to the point at
infinity O of Wei25519. Under this dual isogenous mapping, the base
point (G3X, G3Y) of Wei25519.3 corresponds to a multiple of the base
point (GX, GY) of Wei25519, where this multiple is l=47 (the degree
of the isogeny; see the description in Appendix F.4). Note that this
isogenous map (and its dual) primarily involves the evaluation of
three fixed polynomials involving the xcoordinate, which takes
roughly 140 modular multiplications (or less than 510% relative
incremental cost compared to the cost of an elliptic curve scalar
multiplication).
@@ 1673,37 +1922,38 @@
796e1022 40891faa)
G3X 53837179229940872434942723257480777370451127212339198133697207846
219400243292
(=0x7706c37b 5a84128a 3884a5d7 1811f1b5 5da3230f fb17a8ab
0b32e48d 31a6685c)
G3Y 69548073091100184414402055529279970392514867422855141773070804184
60388229929
+
(=0x0f60480c 7a5c0e11 40340adc 79d6a2bf 0cb57ad0 49d025dc
38d80c77 985f0329)
Appendix H. Isogeny Details
+G.4. Isogeny Details
The isogeny and dual isogeny are both isogenies with degree l=47.
Both are specified by a triple of polynomials u, v, and w (resp. u',
v', and w') of degree 47, 69, and 23, respectively, with coefficients
in GF(p). The coeffients of each of these polynomials are specified
 in Appendix H.1 (for the isogeny) and in Appendix H.2 (for the dual
 isogeny). For each polynomial in variable x, the coefficients are
 tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in
+ in Appendix G.4.1 (for the isogeny) and in Appendix G.4.2 (for the
+ dual isogeny). For each polynomial in variable x, the coefficients
+ are tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in
hexadecimal format.
H.1. Isogeny Parameters
+G.4.1. Isogeny Parameters
H.1.1. Coefficients of u(x)
+G.4.1.1. Coefficients of u(x)
0 0x670ed14828b6f1791ceb3a9cc0edfe127dee8729c5a72ddf77bb1abaebbba1e8
1 0x1135ca8bd5383cb3545402c8bce2ced14b45c29b241e4751b035f27524a9f932
2 0x3223806ff5f669c430efd74df8389f058d180e2fcffa5cdef3eacecdd2c34771
3 0x31b8fecf3f17a819c228517f6cd9814466c8c8bea2efccc47a29bfc14c364266
4 0x2541305c958c5a326f44efad2bec284e7abee840fadb08f2d994cd382fd8ce42
@@ 1780,26 +2031,25 @@
41 0x5a74d1296aaaa245ffb848f434531fa3ba9e5cb9098a7091d36c2777d4cf5a13
42 0x4bd3b700606397083f8038177bdaa1ac6edbba0447537582723cae0fd29341a9
43 0x573453fb2b093016f3368356c786519d54ed05f5372c01723b4da520597ec217
44 0x77f5c605bdb3a30d7d9c8840fce38650910d4418eed707a212c8927f41c2c812
45 0x16d6b9f7ff57ca32350057de1204cc6d69d4ef1b255dfef8080118e2fef6ace3

46 0x34e8595832a4021f8b5744014c6b4f7da7df0d0329e8b6b4d44c8fadad6513b7
47 0x01
H.1.2. Coefficients of v(x)
+G.4.1.2. Coefficients of v(x)
0 0x0f9f5eb7134e6f8dafa30c45afa58d7bfc6d4e3ccbb5de87b562fd77403972b2
1 0x36c2dcd9e88f0d2d517a15fc453a098bbbb5a05eb6e8da906fae418a4e1a13f7
2 0x0b40078302c24fa394a834880d5bf46732ca1b4894172fb7f775821276f558b3
3 0x53dd8e2234573f7f3f7df11e90a7bdd7b75d807f9712f521d4fb18af59aa5f26
4 0x6d4d7bb08de9061988a8cf6ff3beb10e933d4d2fbb8872d256a38c74c8c2ceda
@@ 1921,24 +2172,23 @@
64 0x0dab71e2ae94e6530a501ed8cf3df26731dd1d41cd81578341e12dca3cb71aa3
65 0x537f58d52d18ce5b1d5a6bd3a420e796e64173491ad43dd4d1083a7dcc7dd201
66 0x49c2f6afa93fdcc4e0f8128a8b06da4c75049be14edf3e103821ab604c60f8ae
67 0x10a333eabd6135aeaa3f5f5f7e73d102e4fd7e4bf0902fc55b00da235fa1ad08
68 0x0f5c86044bf6032f5102e601f2a0f73c7bce9384bedd120f3e72d78484179d9c

69 0x01
H.1.3. Coefficients of w(x)
+G.4.1.3. Coefficients of w(x)
0 0x3da24d42421264f30939ff00203880f2b017eb3fecf8933ae61e18df8c8ba116
1 0x0457f20bc393cdc9a66848ce174e2fa41d77e6dbae05a317a1fb6e3ae78760f8
2 0x7f608a2285c480d5c9592c435431fae94695beef79d770bb6d029c1d10a53295
3 0x3832accc520a485100a0a1695792465142a5572bed1b2e50e1f8f662ac7289bb
4 0x2df1b0559e31b328eb34beedd5e537c3f4d7b9befb0749f75d6d0d866d26fbaa
@@ 1968,28 +2219,27 @@
17 0x781d69243b6c86f59416f91f7decaca93eab9cdc36a184191810c56ed85e0fdc
18 0x5f20526f4177357da40a18da054731d442ad2a5a4727322ba8ed10d32eca24fb
19 0x33e4cab64ed8a00d8012104fe8f928e6173c428eff95bbbe569ea46126a4f3cd
20 0x050555b6f07e308d33776922b6566829d122e19b25b7bbacbb0a4b1a7dc40192
21 0x533fa4bf1e2a2aae2f979065fdbb5b667ede2f85543fddbba146aa3a4ef2d281

22 0x5a742cac1952010fc5aba200a635a7bed3ef868194f45b5a6a2647d6d6b289d2
23 0x01
H.2. Dual Isogeny Parameters
+G.4.2. Dual Isogeny Parameters
H.2.1. Coefficients of u'(x)
+G.4.2.1. Coefficients of u'(x)
0 0x0f0eddb584a20aaac8f1419efdd02a5cca77b21e4cfae78c49b5127d98bc5882
1 0x7115e60d44a58630417df33dd45b8a546fa00b79fea3b2bdc449694bade87c0a
2 0x0b3f3a6f3c445c7dc1f91121275414e88c32ff3f367ba0edad4d75b7e7b94b65
3 0x1eb31bb333d7048b87f2b3d4ec76d69035927b41c30274368649c87c52e1ab30
4 0x552c886c2044153e280832264066cce2a7da1127dc9720e2a380e9d37049ac64
@@ 2062,30 +2313,29 @@
39 0x53de362e2f8ff220f8921620a71e8faa1aa57f8886fcbb6808fa3a5560570543
40 0x0dc29a73b97f08aa8774911474e651130ed364e8d8cffd4a80dee633aacecc47
41 0x4e7eb8584ae4de525389d1e9300fc4480b3d9c8a5a45ecfbe33311029d8f6b99
42 0x6c3cba4aa9229550fa82e1cfaee4b02f2c0cb86f79e0d412b8e32b00b7959d80
43 0x5a9d104ae585b94af68eeb16b1349776b601f97b7ce716701645b1a75b68dcf3

44 0x754e014b5e87af035b3d5fe6fb49f4631e32549f6341c6693c5172a6388e273e
45 0x6710d8265118e22eaceba09566c86f642ab42da58c435083a353eaa12d866c39
46 0x6e88ac659ce146c369f8b24c3a49f8dca547827250cf7963a455851cfc4f8d22
47 0x0971eb5f253356cd1fde9fb21f4a4902aa5b8d804a2b57ba775dc130181ae2e8
H.2.2. Coefficients of v'(x)
+G.4.2.2. Coefficients of v'(x)
0 0x043c9b67cc5b16e167b55f190db61e44d48d813a7112910f10e3fd8da85d61d3
1 0x72046db07e0e7882ff3f0f38b54b45ca84153be47a7fd1dd8f6402e17c47966f
2 0x1593d97b65a070b6b3f879fe3dc4d1ef03c0e781c997111d5c1748f956f1ffc0
3 0x54e5fec076b8779338432bdc5a449e36823a0a7c905fd37f232330b026a143a0
4 0x46328dd9bc336e0873abd453db472468393333fbf2010c6ac283933216e98038
@@ 2203,28 +2454,27 @@
62 0x0a90f0059da81a012e9d0a756809fab2ce61cb45965d4d1513a06227783ee4ea
63 0x39fa55971c9e833f61139c39e243d40869fd7e8a1417ee4e7719dd2dd242766f
64 0x22677c1e659caa324f0c74a013921facf62d0d78f273563145cc1ddccfcc4421
65 0x3468cf6df7e93f7ff1fe1dd7e180a89dec3ed4f72843b4ea8a8d780011a245b2
66 0x68f75a0e2210f52a90704ed5f511918d1f6bcfcd26b462cc4975252369db6e9d

67 0x6220c0699696e9bcab0fe3a80d437519bd2bdf3caef665e106b2dd47585ddd9f
68 0x553ad47b129fb347992b576479b0a89f8d71f1196f83e5eaab5f533a1dd6f6d7
69 0x239aef387e116ec8730fa15af053485ca707650d9f8917a75f22acf6213197df
H.2.3. Coefficients of w'(x)
+G.4.2.3. Coefficients of w'(x)
0 0x6bd7f1fc5dd51b7d832848c180f019bcbdb101d4b3435230a79cc4f95c35e15e
1 0x17413bb3ee505184a504e14419b8d7c8517a0d268f65b0d7f5b0ba68d6166dd0
2 0x47f4471beed06e5e2b6d5569c20e30346bdba2921d9676603c58e55431572f90
3 0x2af7eaafd04f6910a5b01cdb0c27dca09487f1cd1116b38db34563e7b0b414eb
4 0x57f0a593459732eef11d2e2f7085bf9adf534879ba56f7afd17c4a40d3d3477b
@@ 2250,71 +2501,71 @@
15 0x55d8a5ceef588ab52a07fa6047d6045550a5c52c91cc8b6b82eeb033c8ca557d
16 0x620b5a4974cc3395f96b2a0fa9e6454202ef2c00d82b0e6c534b3b1d20f9a572
17 0x4991b763929b00241a1a9a68e00e90c5df087f90b3352c0f4d8094a51429524e
18 0x18b6b49c5650fb82e36e25fd4eb6decfdd40b46c37425e6597c7444a1b6afb4e
19 0x6868305b4f40654460aad63af3cb9151ab67c775eaac5e5df90d3aea58dee141

20 0x16bc90219a36063a22889db810730a8b719c267d538cd28fa7c0d04f124c8580
21 0x3628f9cf1fbe3eb559854e3b1c06a4cd6a26906b4e2d2e70616a493bba2dc574
22 0x64abcc6759f1ce1ab57d41e17c2633f717064e35a7233a6682f8cf8e9538afec
23 0x01
Appendix I. Point Compression
+Appendix H. Point Compression
Point compression allows a shorter representation of affine points of
an elliptic curve by exploiting algebraic relationships between the
coordinate values based on the defining equation of the curve in
question. Point decompression refers to the reverse process, where
 one tries and recover the affine point from its compressed
+ one tries and recover an affine point from its compressed
representation and information on the domain parameters of the curve.
Consequently, point compression followed by point decompression is
the identity map.
The description below makes use of an auxiliary function (the parity
 function), which we first define for prime fields GF(p) and then
 extend to all fields GF(q), where q is an odd prime power. We assume
 each finite field to be unambiguously defined.
+ function), which we first define for prime fields GF(p), with p odd,
+ and then extend to all fields GF(q), where q is an odd prime power.
+ We assume each finite field to be unambiguously defined and known
+ from context.
Let y be a nonzero element of GF(q). If q:=p is an odd prime number,
y and py can be uniquely represented as integers in the interval
[1,p1] and have odd sum p. Consequently, one can distinguish y from
y via the parity of this representation, i.e., via par(y):=y (mod
2). If q:=p^m, where p is an odd prime number and where m>0, both y
and y can be uniquely represented as vectors of length m, with
coefficients in GF(p) (see Appendix B.2). In this case, the leftmost
nonzero coordinate values of y and y are in the same position and
have representations in [1,p1] with different parity. As a result,
one can distinguish y from y via the parity of the representation of
this coordinate value. This extends the definition of the parity
function to any oddsize field GF(q), where one defines par(0):=0.
I.1. Point Compression for Weierstrass Curves
+H.1. Point Compression for Weierstrass Curves
If P:=(X, Y) is an affine point of the Weierstrass curve W_{a,b}
defined over the field GF(q), then so is P:=(X, Y). Since the
defining equation Y^2=X^2+a*X+b has at most two solutions with fixed
Xvalue, one can represent P by its Xcoordinate and one bit of
information that allows one to distinguish P from P, i.e., one can
represent P as the ordered pair compr(P):=(X, par(Y)). If P is a
point of order two, one can uniquely represent P by its Xcoordinate
alone, since Y=0 and has fixed parity. Conversely, given the ordered
pair (X, t), where X is an element of GF(q) and where t=0 or t=1, and
 the domain parameters of the curve, one can use the defining equation
 of the curve to try and determine candidate values for the
+ the domain parameters of the curve W_{a,b}, one can use the defining
+ equation of the curve to try and determine candidate values for the
Ycoordinate given X, by solving the quadratic equation Y^2:=alpha,
where alpha:=X^3+a*X+b. If alpha is not a square in GF(q), this
equation does not have a solution in GF(q) and the ordered pair (X,
t) does not correspond to a point of this curve. Otherwise, there
are two solutions, viz. Y=sqrt(alpha) and Y. If alpha is a nonzero
element of GF(q), one can uniquely recover the 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.
@@ 2324,216 +2575,226 @@
infinity O with any ordered pair compr(O):=(X,0), where X is any
element of GF(q) for which alpha:=X^3+a*X+b is not a square in GF(q),
and recover this point accordingly. In this case, the point at
infinity O can be represented by any ordered pair (X,0) of elements
of GF(q) for which X^3+a*X+b is not a square in GF(q). Note that
this ordered pair does not satisfy the defining equation of the curve
in question. An application may fix a specific suitable value of X
or choose multiple such values and use this to encode additonal
information. Further details are out of scope.
I.2. Point Compression for Montgomery Curves
+H.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
pair (u, t), where u is an element of GF(q) and where t=0 or t=1, and
 the domain parameters of the curve, one can use the defining equation
 of the curve to try and determine candidate values for the
+ the domain parameters of the curve M_{A,B}, one can use the defining
+ equation of the curve to try and determine candidate values for the
vcoordinate given u, by solving the quadratic equation v^2:=alpha,
where alpha:=(u^3+A*u^2+u)/B. If alpha is not a square in GF(q),
this equation does not have a solution in GF(q) and the ordered pair
(u, t) does not correspond to a point of this curve. Otherwise,
there are two solutions, viz. v=sqrt(alpha) and v. If alpha is a
nonzero element of GF(q), one can uniquely recover the 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
+H.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,
given the ordered pair (t, y), where y is an element of GF(q) and
 where t=0 or t=1, and the domain parameters of the curve, one can use
 the defining equation of the curve to try and determine candidate
 values for the xcoordinate given y, by solving the quadratic
 equation x^2:=alpha, where alpha:=(1y^2)/(ad*y^2). If alpha is not
 a square in GF(q), this equation does not have a solution in GF(q)
 and the ordered pair (t, y) does not correspond to a point of this
 curve. Otherwise, there are two solutions, viz. x=sqrt(alpha) and
 x. If alpha is a nonzero element of GF(q), one can uniquely recover
 the 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.
+ where t=0 or t=1, and the domain parameters of the curve E_{a,d}, one
+ can use the defining equation of the curve to try and determine
+ candidate values for the xcoordinate given y, by solving the
+ quadratic equation x^2:=alpha, where alpha:=(1y^2)/(ad*y^2).
+ (Here, observe that the denominator is nonzero for any point of
+ E_{a,d}.) If alpha is not a square in GF(q), this equation does not
+ have a solution in GF(q) and the ordered pair (t, y) does not
+ correspond to a point of this curve. Otherwise, there are two
+ solutions, viz. x=sqrt(alpha) and x. If alpha is a nonzero element
+ of GF(q), one can uniquely recover the 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). (Note that this
 corresponds to the case alpha=0 and t=0 above.)
+ the twisted Edwards curve E_{a,d}. Here, the identity element
+ O:=(0,1) is associated with the compressed point compr(O):=(0,1).
+ (Note that this corresponds to the case alpha=0 and t=0 above.)
We extend the definition of the compression function further, to also
include a special marker element 'btm', by associating this marker
element with the ordered pair compr(btm):=(1,1) and recover this
marker element accordingly. (Note that this corresponds to the case
alpha=0 and t=1 above.) The marker element 'btm' can be represented
by the ordered pair (1,1) of elements of GF(q). Note that this
ordered pair does not satisfy the defining equation of the curve in
question.
Appendix J. Data Conversions
+Appendix I. 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.
+ postfix Y of length t (where in both cases t is an integer in the
+ interval [0,l]). One can define these notions as well if t is
+ outside the interval [0,l] by stipulating that a tprefix or
+ tpostfix is the empty string if t is negative and that it is the
+ entire string Z if t is larger than l. Sometimes, a tprefix of a
+ string Z is denoted by truncleft(Z,t); a tpostfix 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 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, as are the operations in the previous paragraph.
J.1. Conversion between Bit Strings and Integers
+I.1. Conversion between Bit Strings and Integers (BS2I, I2BS)
 There is a 11 correspondence between bit strings of length l and the
+ There is a 11 correspondence between bit strings of length l and
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
nonnegative integer smaller than 2^t can be represented as a bit
string of length at least t (due to leading zero coefficients in base
2 representation). The latter representation is called tight if the
 bit string representation has minimal length.
+ bit string representation has minimal length. This defines the
+ mapping BS2I from bit strings to integers and the mapping I2BS(x,l)
+ from nonnegative integers smaller than 2^l to bit strings of length
+ l.
J.2. Conversion between Octet Strings and Integers (OS2I, I2OS)
+I.2. Conversion between Octet Strings and Integers (OS2I, I2OS)
There is a 11 correspondence between octet strings of length l and
 the integers in the interval [0, 256^l), where the octet string
+ integers in the interval [0, 256^l), where the octet string
X:=str(X_{l1}, X_{l2}, ..., X_1, X_0) corresponds to the integer
x:=X_{l1}*256^{l1} + X^{l2}*256^{l2} + ... + X_1*256 + X_0*1.
(If l=0, the empty string corresponds to the integer zero.) Note
that while the mapping from octet strings to integers is uniquely
defined, the inverse mapping from integers to octet strings is not,
since any nonnegative integer smaller than 256^t can be represented
as an octet string of length at least t (due to leading zero
coefficients in base 256 representation). The latter representation
is called tight if the octet string representation has minimal
length. This defines the mapping OS2I from octet strings to integers
and the mapping I2OS(x,l) from nonnegative integers smaller than
256^l to octet strings of length l.
J.3. Conversion between Octet Strings and Bit Strings (BS2OS, OS2BS)
+I.3. Conversion between Octet Strings and Bit Strings (OS2BS, BS2OS)
There is a 11 correspondence between octet strings of length l and
 and bit strings of length 8*l, where the octet string X:=str(X_{l1},
+ bit strings of length 8*l, where the octet string X:=str(X_{l1},
X_{l2}, ..., X_1, X_0) corresponds to the rightconcatenation of the
8bit strings x_{l1}, x_{l2}, ..., x_1, x_0, where each octet X_i
corresponds to the 8bit string x_i according to the mapping of
 Appendix J.1 above. Note that the mapping from octet strings to bit
+ Appendix I.1 above. Note that the mapping from octet strings to bit
strings is uniquely defined and so is the inverse mapping from bit
strings to octet strings, if one prepends each bit string with the
smallest number of 0 bits so as to result in a bit string of length
divisible by eight (i.e., one uses prepadding). This defines the
mapping OS2BS from octet strings to bit strings and the corresponding
mapping BS2OS from bit strings to octet strings.
J.4. Conversion between Field Elements and Octet Strings (FE2OS, OS2FE)
+I.4. Conversion between Field Elements and Octet Strings (FE2OS, OS2FE)
 There is a 11 correspondence between elements of a fixed finite
 field GF(q), where q=p^m and m>0, and vectors of length m, with
 coefficients in GF(p), where each element x of GF(q) is a vector
 (x_{m1}, x_{m2}, ..., x_1, x_0) according to the conventions of
 Appendix B.2. In this case, this field element can be uniquely
 represented by the rightconcatenation of the octet strings X_{m1},
 X_{m2}, ..., X_1, X_0, where each octet string X_i corresponds to
 the integer x_i in the interval [0,p1] according to the mapping of
 Appendix J.2 above. Note that both the mapping from field elements
 to octet strings and the inverse mapping are only uniquely defined if
 each octet string X_i has the same fixed size (e.g., the smallest
 integer l so that 256^l >= p) and if all integers are reduced modulo
 p. If so, the latter representation is called tight if l is minimal
 so that 256^l >= p. This defines the mapping FE2OS(x,l) from field
 elements to octet strings and the mapping OS2FE(X,l) from octet
 strings to field elements, where the underlying field is implicit and
 assumed to be known from context. In this case, the octet string has
 length l*m.
+ There is a 11 correspondence between elements of the fixed finite
+ field GF(q), where q:=p^m, where p is a prime number and where m>0,
+ and vectors of length m, with coefficients in GF(p), where each
+ element x of GF(q) is a vector (x_{m1}, x_{m2}, ..., x_1, x_0)
+ according to the conventions of Appendix B.2. In this case, this
+ field element can be uniquely represented by the rightconcatenation
+ of the octet strings X_{m1}, X_{m2}, ..., X_1, X_0, where each
+ octet string X_i corresponds to the integer x_i in the interval
+ [0,p1] according to the mapping of Appendix I.2 above. Note that
+ both the mapping from field elements to octet strings and the inverse
+ mapping from octet strings to field elements are only uniquely
+ defined if each octet string X_i has the same fixed size (e.g., the
+ smallest integer l so that 256^l >= p) and if all integers are
+ reduced modulo p. If so, the latter representation is called tight
+ if l is minimal so that 256^l >= p. This defines the mapping
+ FE2OS(x,l) from field elements to octet strings and the mapping
+ OS2FE(X,l) from octet strings to field elements, where the underlying
+ field is implicit and assumed to be known from context. In this
+ case, the octet string has length l*m. (Observe that with tight
+ representations, the parameter l is uniquely defined by the
+ characteristic p of the field GF(q) in question.)
J.5. Conversion between Elements of Z mod n and Octet Strings (ZnE2OS,
+I.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
+ There is a 11 correspondence between elements of the 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
+ element x of Z_n is uniquely represented by the integer x mod n. In
+ this case, x mod n can be uniquely represented by the octet string X
+ according to the mapping of Appendix I.2 above. Note that both the
+ mapping from elements of Z_n to octet strings and the inverse mapping
+ from octet strings to elements of Z_n are only uniquely defined if
the octet string has a fixed size (e.g., the smallest integer l so
 that 256^l >= n) and if all integers are reduced modulo n. If so,
 the latter representation is called tight if l is minimal so that
+ that 256^l >= n) and if all integers are first reduced modulo n. If
+ so, the latter representation is called tight if l is minimal so that
256^l >= n. This defines the mapping ZnE2OS(x,l) from elements of
 Z(n) to octet strings and the mapping OS2ZnE(X,l) from octet strings
 to elements of Z(n), where the underlying modulus n is implicit and
+ 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.
+ length l. (Observe that with tight representations, the parameter l
+ is uniquely defined by the parameter n in question.)
Note that if n is a prime number p, the conversions ZnE2OS and FE2OS
are consistent, as are OS2ZnE and OS2FE. This is, however, no longer
the case if n is a strict prime power.
 The conversion rules for composite n values are useful, e.g., when
 encoding the modulus n of RSA (or elements of any other nonprime set
 Z(n), for that matter).
+ The conversion rules for composite n values may be useful, e.g., when
+ encoding RSA parameters (or elements of any other nonprime size set
+ Z_n, for that matter).
J.6. Ordering Conventions
+I.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}).
@@ 2569,43 +2830,43 @@
bit string or octet string (due to leading zeros). However, tight
representations (as defined above) are nonambiguous. (Note, in
particular, that tightness implies that elements of GF(q) are always
uniquely represented.)
Note that elements of a prime field GF(p), where p is a 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
+ compressed point (see Appendix H) to be encoded in this bit position
and, thereby, allows a compressed point and a field element of GF(p)
to be represented by an octet string of the same length. This is
called the squeezed point representation. Obviously, other
 representations (e.g., those of elements of Z(n)) may also have fixed
 bit values on certain positions, which can be used to squeezein
+ representations (e.g., those of elements of Z_n) may also have fixed
+ bit values in certain positions, which can be used to squeezein
additional information. Further details are out of scope.
Appendix K. Representation Examples Curve25519 Family Members
+Appendix J. Representation Examples Curve25519 Family Members
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
k 45467544759954639344191351164156560595299236761702065033670739677
691372543056
(=0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3
c08d5abd 15e29c50).
K.1. Example with Curve25519
+J.1. Example with Curve25519
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
@@ 2652,22 +2913,22 @@
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.
+ this case, are both zero, since v and v1 are even). See Appendix H.2
+ and Appendix I 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).
@@ 2680,24 +2940,24 @@
(=0x5844b232 8c4586dc 62f593c5 599c2a8c e61ba893 bb052de6
77510a42 b3a68a5a)
t2 451856098332889407421278004628150814449259902023388533929
08848927625430980881
(=0x11598452 e65138dc ce948d7e d8f46a18 b640722c 8e170957
751b7729 1b26e663),
 where this representation is defined in Appendix L.4 and uses the
 mapping of Appendix L.3.2 with the default square root function.
+ where this representation is defined in Appendix K.5 and uses the
+ mapping of Appendix K.3.2 with the default square root function.
K.2. Example with Edwards25519
+J.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
@@ 2738,21 +2998,21 @@
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
+ is odd). See Appendix H.3 and Appendix I 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 [RFC7748], [RFC8032]
requires unique representations of all elements of GF(p).
A randomized representation (t1, t2) of the point k*Pe in tight LSB/
lsb order is given by
@@ 2757,29 +3017,30 @@
lsb order is given by
t1 577913017083163641949634219017190182170288776648725395935
97750427519399254040
(=0x181a32c5 10e06dbc ea321882 f3519055 535e289e 8faac654
82e26f61 aded23fe)
t2 454881407940919718426608573125377401686255068210624245884
05479716220480287974
+
(=0x672e36c5 ae353073 cdfac343 e8297b05 1b010d0f 5b1016db
dd4baf54 28068926),
 where this representation is defined in Appendix L.4 and uses the
 mapping of Appendix L.3.3 with the default square root function and
+ where this representation is defined in Appendix K.5 and uses the
+ mapping of Appendix K.3.3 with the default square root function and
underlying isomorphic mapping between Edwards25519 and Curve25519 of
Appendix E.2.
K.3. Example with Wei25519
+J.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
@@ 2819,22 +3080,22 @@
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.
+ case, are both zero, since Y and Y1 are even). See Appendix H.1 and
+ Appendix I 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
@@ 2854,25 +3115,26 @@
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].
+ see [SEC1]. Note that, due to the bitsize of the prime p, the
+ squeezed compressed format repr(Pw) is one octet shorter than the
+ SEC1compliant compressed format compr(Pw).
A randomized representation (t1, t2) of the point k*Pw in tight MSB/
msb order is given by

t1 446363445988889734093446280484122107283059206243307955388
84223152228795899590
(=0x62af4697 4dd469ac 96c64809 c16c8517 b6a0cee5 40ba0e2e
6dd2b36a fcc75ec6)
t2 213890166610228613105792710708385961712211281744756216061
11930888059603107561
(=0x2f49c121 8fed7912 031157ee ae066507 a972320b 6180e267
@@ 2871,24 +3133,24 @@
(=0x62af4697 4dd469ac 96c64809 c16c8517 b6a0cee5 40ba0e2e
6dd2b36a fcc75ec6)
t2 213890166610228613105792710708385961712211281744756216061
11930888059603107561
(=0x2f49c121 8fed7912 031157ee ae066507 a972320b 6180e267
4025b006 2e67bee9),
 where this representation is defined in Appendix L.4 and uses the
 mapping of Appendix L.3.1 with the default square root function.
+ where this representation is defined in Appendix K.5 and uses the
+ mapping of Appendix K.3.1 with the default square root function.
K.4. Example with Wei25519.2
+J.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
@@ 2929,48 +3191,47 @@
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)
+ Appendix Appendix H.1 and Appendix I for further detail on (squeezed)
point compression.
A randomized representation (t1, t2) of the point k*Pw2 in tight MSB/
msb order is given by
t1 416669672354928148679758598803660112405431159793278161879
36189858804289581274
(=0x5c1eaaef 80f9d4af 33c119fc c99acd58 f81e7d69 999c7048
e4043a77 87a930da)
t2 361115271162391608083096560179337391059615651279123199921
18531180247832114098
(=0x4fd66668 e7174775 de44c852 92df8cfe b9832ef8 2570b3b8
fe5ec21a b2d4b3b2),
 where this representation is defined in Appendix L.4 and uses the
 mapping of Appendix L.3.1 with the default square root function.
+ where this representation is defined in Appendix K.5 and uses the
+ mapping of Appendix K.3.1 with the default square root function.
K.5. Example with Wei25519.3
+J.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
@@ 2975,22 +3236,22 @@
X1 47362979975244556396292400751828272600887612546997532158738958926
60745725532
(=0x0a78a650 a39995ef dcf4de88 940d4ce9 5b2ca35c c5d70e06
63b8455e 2e04e65c).
Y1 30318112837157047703426636957515037640997356617656007157255559136
153389790354
 (=0x64ced628 e982648e 4bfcf30c 71c4d267 ba48b0ce fee20062
 b43ef4c9 73f7b541).
+ (=0x4307719a 20d08741 58d5889e 8c8ec27e 246b0342 55f8fd62
+ dbc9ca09 e79c7492).
X2 23778942085873786433506063022059853212880296499622328201295446580
293591664363
(=0x3492677e 6ae9d1c3 e08f908b 61033f3d 4e8322c9 fba6da81
2c95b067 9b1486eb).
Y2 44846366394651736248316749170687053272682847823018287439056537991
969511150494
@@ 3005,99 +3266,104 @@
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
+ even). See Appendix H.1 and Appendix I for further detail on
(squeezed) point compression.
A randomized representation (t1, t2) of the point k*Pw3 in tight MSB/
msb order is given by
t1 573714937613596601525680684642155667097217474964816246889
88981227297409008259
(=0x7ed71d5f 566d2259 99bdb404 bfb9d6cf d2e86ccb 1894d4a6
c75e3c69 e5eb0283)
t2 269945781324580189815142015663892935722419453863927287235
57891665397640090729
(=0x3bae63c8 70f60de0 c2e35f94 d24220f1 bb6efd00 37625869
f84923de ff4c5469),
 where this representation is defined in Appendix L.4 and uses the
 mapping of Appendix L.3.1 with the default square root function.
+ where this representation is defined in Appendix K.5 and uses the
+ mapping of Appendix K.3.1 with the default square root function.
Appendix L. Auxiliary Functions
+Appendix K. Auxiliary Functions
L.1. Square Roots in GF(q)
+ This section illustrates how one could implement common routines,
+ such as taking square roots and inverses in finite fields, and how to
+ map field elements to curve points and to curve points that avoid
+ some outliers.
+
+K.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
+ Appendix K.1.1) or if q = 5 (mod 8) (see Appendix K.1.2). Details on
how to compute square roots for other values of q are out of scope.
If square roots are easy to compute in GF(q), then so are these in
GF(q^2).
L.1.1. Square Roots in GF(q), where q = 3 (mod 4)
+K.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)
+K.1.2. Square Roots in GF(q), where q = 5 (mod 8)
 If y is a nonzero element of GF(q) and z:=y^{z5)/8}, then y is a
+ If y is a nonzero element of GF(q) and z:=y^{(q5)/8}, then y is a
square in GF(q) only if y^2*z^4=1.
a. If y*z^2=+1, z is a square root of 1/y and y*z is a square root
of y in GF(q);
b. If y*z^2=1, i*z is a square root of 1/y and i*y*z is a square
 root of y.
+ root of y in GF(q).
Here, i is an element of GF(q) for which i^2=1 (e.g.,
i:=2^{(q1)/4}). This field element can be precomputed.
L.2. Inversion
+K.2. Inversion
If y is an integer and gcd(y,n)=1, one can efficiently compute 1/y
(mod n) via the extended Euclidean Algorithm (see Section 2.2.5 of
[GECC]). One can use this algorithm as well to compute the inverse
of a nonzero element y of a prime field GF(p), since gcd(y,p)=1.
The inverse of a nonzero element y of GF(q) can be computed as
1/y:=y^{q2} (since y^{q1}=1).
 Further details are out of scope. If inverses are easy to compute in
 GF(q), then so are these in GF(q^2).
+ If inverses are easy to compute in GF(q), then so are these in
+ GF(q^2). Further details are out of scope.
The inverses of two nonzero elements y1 and y2 of GF(q) can be
computed by first computing the inverse z of y1*y2 and by
subsequently computing y2*z=:1/y1 and y1*z=:1/y2.
L.3. Mapping to Curve Points
+K.3. Mappings to Curve Points
One can map elements of GF(q) that are not a square in GF(q) to
 points of a Weierstrass curve (see Appendix L.3.1), to points of a
 Montgomery curve (see Appendix L.3.2), or to points of a twisted
 Edwards curve (see Appendix L.3.3), under some mild conditions on the
+ points of a Weierstrass curve (see Appendix K.3.1), to points of a
+ Montgomery curve (see Appendix K.3.2), or to points of a twisted
+ Edwards curve (see Appendix K.3.3), under some mild conditions on the
domain parameters. Full details on mappings that apply if these
conditions are not satisfied are out of scope.
L.3.1. Mapping to Points of Weierstrass Curve
+K.3.1. Mapping to Points of Weierstrass Curve
The description below assumes that the domain parameters a and b of
the Weierstrass curve W_{a,b} are nonzero. For ease of exposition,
we define f(z):=z^3+a*z+b. (Note that for an affine point (X,Y) of
W_{a,b} one has Y^2=f(X).)
If t is an element of GF(q) that is not a square in GF(q) and that is
unequal to 1, then the element X:=(b/a)*(1+1/(t+t^2)) is the unique
solution of the equation f(t*X)=t^3*f(X) and is nonzero.
Consequently, either X or X':=t*X is the xcoordinate of an affine
@@ 3107,21 +3373,21 @@
to the point P(t):=(X, Y);
b. If f(X) is not a square in GF(q) and Y':=sqrt(f(X')), then t is
mapped to the point P(t):=(X', Y').
Formally, this mapping is not properly defined, since a nonzero
square y:=x^2 in GF(q) has two solutions, viz. x and x; it is
properly defined, however, if one designates for each element in
GF(q) that is a square in GF(q) precisely one square root as "the"
square root of this element. Note that always picking the square
 root with zero parity (see Appendix I) satisfies this condition
+ root with zero parity (see Appendix H) satisfies this condition
(henceforth called the default square root function).
If 1 is not a square in GF(q), this element is mapped to the point
at infinity O of W_{a,b}.
The set of points of W_{a,b} that arises this way has size roughly
3/8 of the order of the curve and each such point arises as image of
one or two t values. Further details are out of scope.
NOTE 1: If 1 is not a square in GF(q), the mapping above yields the
@@ 3132,27 +3398,27 @@
are out of scope.
NOTE 2: The description above assumes that the domain parameters a
and b of the Weierstrass curve are nonzero. If this is not the case,
one can often find an isogenous curve W_{a',b'} for which the domain
parameters a' and b' are nonzero. If so, one can map elements of
GF(q) that are not a square in GF(q) to points of W_{a,b} via
function composition, where one uses the mapping above to arrive at a
point of W_{a',b'} and where one subsequently uses the dual isogeny
from W_{a',b'} to W_{a,b} to arrive at a point of W_{a,b}. As an
 example, one can show that if a is zero and 4*b is a cube in GF(q)
 (such as is the case with, e.g., the "BitCoin" curve secp256k1
+ example, one can show that if a is zero and if 4*b is a cube in
+ GF(q) (such as is the case with, e.g., the "BitCoin" curve secp256k1
[SEC2]), this curve is 3isogenous to a curve with this property and
the strategy above applies (for an example with secp256k1, see
 Appendix M). Further details are out of scope.
+ Appendix L). Further details are out of scope.
L.3.2. Mapping to Points of Montgomery Curve
+K.3.2. Mapping to Points of Montgomery Curve
The description below assumes that the domain parameter A of the
Montgomery curve M_{A,B} is nonzero. For ease of exposition, we
define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of
M_{A,B} one has B*v^2=f(u).)
If t is an element of GF(q) that is not a square in GF(q) and that is
unequal to 1, then the element u:=(1+1/t)/A is the unique nonzero
solution of the equation f(t*u)=t^3*f(u). Consequently, either u or
u':=t*u is the ucoordinate of an affine point of M{A,B}, depending
on whether f(u)/B is a square in GF(q).
@@ 3161,127 +3427,317 @@
mapped to the point P(t):=(u, v);
b. If f(u)/B is a not a square in GF(q) and v':=sqrt(f(u')/B), then
t is mapped to the point P(t):=(u', v').
As before, formally, this mapping is not properly defined, since a
nonzero square y:=x^2 in GF(q) has two solutions, viz. x and x; it
is properly defined, however, if one designates for each element in
GF(q) that is a square in GF(q) precisely one square root as "the"
square root of this element. Note that always picking the square
 root with zero parity (see Appendix I) satisfies this condition
+ root with zero parity (see Appendix H) satisfies this condition
(henceforth called the default square root function).
If 1 is not a square in GF(q), this element is mapped to the point
at infinity O of M_{A,B}.
The set of points of M_{A,B} that arises this way has size roughly
1/2 of the order of the curve and each such point arises as image of
precisely one t value. Further details are out of scope.
NOTE 1: If 1 is not a square in GF(q), the mapping above yields the
point at infinity for t=1. One can modify this mapping to always
yield an affine point, by mapping the element 1 to, e.g., the base
point G of M_{A,B} and leaving the remainder of the mapping the same.
Suitability of such a modification is applicationspecific. Details
are out of scope.
NOTE 2: The description above assumes that the domain parameter A of
the Montgomery curve is nonzero. If this is not the case, the curve
is a Weierstrass curve for which the domain parameter b is zero and
 Note 2 of Appendix L.3.1 applies. If q = 3 (mod 4), an even simpler
+ Note 2 of Appendix K.3.1 applies. If q = 3 (mod 4), an even simpler
approach is possible, where one modifies the construction above and
simply takes u:=t and u':=t (which works, since 1 is not a square
in GF(q) and f(t)=f(t)). In this case, this construction can be
extended to all elements t of GF(q) and, if so, yields a 11 mapping
between GF(q) and all affine curve points.
L.3.3. Mapping to Points of Twisted Edwards Curve
+K.3.3. Mapping to Points of Twisted Edwards Curve
One can map elements of GF(q) that are not a square in GF(q) to
points of the twisted Edwards curve E_{a,d} via function composition,
 where one uses the mapping of Appendix L.3.1 to arrive at a point of
+ where one uses the mapping of Appendix K.3.1 to arrive at a point of
the Weierstrass curve W_{a,b} and where one subsequently uses the
isomorphic mapping between twisted Edwards curves and Weierstrass
curves of Appendix D.3 to arrive at a point of E_{a,d}. Another
mapping is obtained by function composition, where one instead uses
 the mapping of Appendix L.3.2 to arrive at a point of the Montgomery
+ the mapping of Appendix K.3.2 to arrive at a point of the Montgomery
curve M_{A,B} and where one subsequently uses the isomorphic mapping
between twisted Edwards curves and Montgomery curves of Appendix D.1
to arrive at a point of E_{a,d}. Obviously, one can use function
composition (now using the respective preimages  if these exist) to
realize the preimages of either mapping.
L.4. Randomized Representation of Curve Points
+K.4. Mappings to HighOrder Curve Points
 The mappings of Appendix L.3.1, Appendix L.3.2, and Appendix L.3.3
 allow one to represent a curve point Q as a specific element of
 GF(q), provided this point arises as a point in the range of the
 mapping at hand. For Montgomery curves and twisted Edwards curves,
 this covers roughly half of the curve points; for Weierstrass curves,
 roughly 3/8 of the curve points. One can extend the mappings above,
 by mapping a pair (t1, t2) of inputs to the point Q:=P2(t1,
 t2):=P(t1) + P(t2). In this case, each curve point has roughly q/4
 representations as an ordered pair (t1, t2) on average. In fact, one
 can show that if the input pairs are generated uniformly at random,
 then the corresponding curve points follow a distribution that is
 also (statistically indistinguishable from) a uniform distribution,
 and viceversa. Here, each pair (t1, t2) deterministically yields a
 curve point, whereas for each curve point Q, a randomized algorithm
 yields an ordered pair (t1, t2) of preimages of Q, where the
+ Appendix K.3 described how one can map elements of GF(q) that are not
+ a square in GF(q) to points of a Weierstrass curve, to points of a
+ Montgomery curve, or to points of a twisted Edwards curve, under some
+ mild conditions on the domain parameters. Below, we use the mappings
+ of that appendix and the parity function par(.) specified in
+ Appendix H to construct mappings to highorder curve points only
+ (i.e., mappings that avoid points in the small subgroup, see
+ Appendix B.1). We consider mappings to highorder points of a
+ Weierstrass curve (see Appendix K.4.1), to highorder points of a
+ Montgomery curve (see Appendix K.4.2), and to highorder points of a
+ twisted Edwards curve (see Appendix K.4.3). As before, full details
+ on mappings that apply if the mild conditions on the domain
+ parameters are not satisfied are out of scope.
+
+K.4.1. Mapping to HighOrder Points of Weierstrass Curve
+
+ The description below assumes that the domain parameters a and b of
+ the Weierstrass curve W_{a,b} are nonzero. For ease of exposition,
+ we define f(z):=z^3+a*z+b. (Note that for an affine point (X,Y) of
+ W_{a,b} one has Y^2=f(X).)
+
+ If t is an element of GF(q) that is not a square in GF(q) and that is
+ unequal to 1, the mapping of Appendix K.3.1 yields an affine point
+ P(t):=(X, Y) of W_{a,b}. Let P0:=(X0, Y0) be a fixed affine point of
+ W_{a,b} for which neither P0, P0 + P(t), nor P0  P(t) is in the
+ small subgroup of W_{a,b}. (Note that this implies that P0 and P(t)
+ are distinct affine points of the curve and that these are not each
+ other's inverse.) For binary digit s, the point Q(t,s) is now
+ defined as follows:
+
+ a. If par(Y0*Y)=s, then the pair (t,s) is mapped to the point
+ Q(t,s):=P0 + P(t);
+
+ b. If par(Y0*Y)<>s, then the pair (t,s) is mapped to the point
+ Q(t,s):=P0  P(t).
+
+ Note that this mapping is properly defined as long as the fixed point
+ P0 (the socalled "curve offset") alluded to above indeed exists. In
+ cases of practical interest that we are aware of, this is indeed the
+ case (see, e.g., Table 1).
+
+ If 1 is not a square in GF(q), the pair (1,s) is mapped to the
+ affine point P0 of W_{a,b} (irrespective of the value of s).
+
+ The set of points of W_{a,b} that arises this way has size roughly
+ 3/8 of the order of the curve and each such point arises as image of
+ up to four values of the pair (t,s). Further details are out of
+ scope.
+
+ From the group law for Weierstrass curves (see Appendix C.1) it
+ follows that one can express the coordinates of Q(t,s), with t<>1,
+ in terms of the Xcoordinates of P0 and P(t) and the product of their
+ Ycoordinates. (Here, observe that Y0*Y is a square root of
+ f(X0)*f(X).) Thus, Q(t,s) can be computed without the need to fully
+ compute P(t).
+
+K.4.2. Mapping to HighOrder Points of Montgomery Curve
+
+ The description below assumes that the domain parameters A and B of
+ the Montgomery curve M_{A,B} are nonzero. For ease of exposition, we
+ define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of
+ M_{A,B} one has B*v^2=f(u).)
+
+ If t is an element of GF(q) that is not a square in GF(q) and that is
+ unequal to 1, the mapping of Appendix K.3.2 yields an affine point
+ P(t):=(u, v) of M_{A,B}. Let P0:=(u0, v0) be a fixed affine point of
+ M_{A,B} for which neither P0, P0 + P(t), nor P0  P(t) is in the
+ small subgroup of M_{A,B}. (Note that this implies that P0 and P(t)
+ are distinct affine points of the curve and that these are not each
+ other's inverse.) For binary digit s, the point Q(t,s) is now
+ defined as follows:
+
+ a. If par(B*v0*v)=s, then the pair (t,s) is mapped to the point
+ Q(t,s):=P0 + P(t);
+
+ b. If par(B*v0*v)<>s, then the pair (t,s) is mapped to the point
+ Q(t,s):=P0  P(t).
+
+ Note that this mapping is properly defined as long as the fixed point
+ P0 (the socalled "curve offset") alluded to above indeed exists. In
+ cases of practical interest that we are aware of, this is indeed the
+ case (see, e.g., Table 1).
+
+ If 1 is not a square in GF(q), the pair (1,s) is mapped to the
+ affine point P0 of M_{A,B} (irrespective of the value of s).
+
+ The set of points of M_{A,B} that arises this way has size roughly
+ 1/2 of the order of the curve and each such point arises as image of
+ up to two values of the pair (t,s). Further details are out of
+ scope.
+
+ From the group law for Montgomery curves (see Appendix C.2) it
+ follows that one can express the coordinates of Q(t,s), with t<>1,
+ in terms of the ucoordinates of P0 and P(t) and the product of their
+ vcoordinates. (Here, observe that B*v0*v is a square root of
+ f(u0)*f(u).) Thus, Q(t,s) can be computed without the need to fully
+ compute P(t).
+
+ +++
+  Curve  Fixed curve offset P0 
+ +++
+  NIST P224 [FIPS1864]  Base point (Gx,Gy) 
+  NIST P256 [FIPS1864]  P0:=(0,y) with y even 
+  NIST P384 [FIPS1864]  P0:=(0,y) with y even 
+  NIST P521 [FIPS1864]  P0:=(0,y) with y even 
+  Brainpool224r1 [RFC5639]  Base point (Gx, Gy) 
+  Brainpool256r1 [RFC5639]  Base point (Gx, Gy) 
+  Brainpool320r1 [RFC5639]  Base point (Gx, Gy) 
+  Brainpool384r1 [RFC5639]  Base point (Gx, Gy) 
+  Brainpool512r1 [RFC5639]  P0:=(3,y), y even 
+  Curve25519 [RFC7748]  P0:=(90,v), v even 
+  Curve448 [RFC7748]  P0:=(50,v), v even 
+  Wei25519 [Appendix E.3]  P0:=(3,y), y even 
+  Wei25519.2 [Appendix G.3]  P0:=(244,y), y even 
+  Wei25519.3 [Appendix G.3]  P0:=(41,y), y even 
+  secp256k1.m [Appendix L.3]  P0:=(0,y), y even 
+ +++
+
+ Table 1: Curve offsets P0 for mappings that avoid loworder points
+
+K.4.3. Mapping to HighOrder Points of Twisted Edwards Curve
+
+ One can map elements of GF(q) that are not a square in GF(q) to
+ points of the twisted Edwards curve E_{a,d} via function composition,
+ where one uses the mapping of Appendix K.4.1 to arrive at a point of
+ the Weierstrass curve W_{a,b} that does not have low order and where
+ one subsequently uses the isomorphic mapping between twisted Edwards
+ curves and Weierstrass curves of Appendix D.3 to arrive at a point of
+ E_{a,d} with this property. Another mapping is obtained by function
+ composition, where one instead uses the mapping of Appendix K.4.2 to
+ arrive at a point of the Montgomery curve M_{A,B} that does not have
+ low order and where one subsequently uses the isomorphic mapping
+ between twisted Edwards curves and Montgomery curves of Appendix D.1
+ to arrive at a point of E_{a,d} with this property. Obviously, one
+ can use function composition (now using the respective preimages 
+ if these exist) to realize the preimages of either mapping.
+
+K.5. Randomized Representation of Curve Points
+
+ The mappings of Appendix K.3 allow one to represent a curve point Q
+ as a specific element t of GF(q), provided this point arises as a
+ point in the range of the mapping at hand. For Montgomery curves and
+ twisted Edwards curves, this covers roughly half of the curve points;
+ for Weierstrass curves, roughly 3/8 of the curve points. One can
+ extend the mappings above, by mapping a pair (t1, t2) of inputs to
+ the point Q:=P2(t1, t2):=P(t1) + P(t2). In this case, each curve
+ point has roughly q/4 representations as an ordered pair (t1, t2) on
+ average. In fact, one can show that if the input pairs are generated
+ uniformly at random, then the corresponding curve points follow a
+ distribution that is also (statistically indistinguishable from) a
+ uniform distribution, and viceversa. Here, each pair (t1, t2)
+ deterministically yields a curve point, whereas for each curve point
+ Q, a randomized algorithm yields an ordered pair (t1, t2) of pre
+ images of Q, where the expected number of randomized preimages one
+ has to try is small (four if one uses the mapping of Appendix K.3.1;
+ two if one uses the mapping of Appendix K.3.2). For further details,
+ see Algorithm 1 of [Tibouchi].
+
+ Similar properties hold if one uses the mappings of Appendix K.4
+ (rather than those of Appendix K.3): in this case, the mapping allows
+ one to represent a curve point Q as a specific element (t,s) of
+ GF(q)x{0,1}, provided this point arises as a point in the range of
+ the mapping at hand. For Montgomery curves and twisted Edwards
+ curves, this covers roughly half of the curve points; for Weierstrass
+ curves, roughly 3/8 of the curve points. One can extend the mappings
+ above, by mapping a pair ((t1,s1), (t2,s2)) of inputs to the point
+ Q:=Q2((t1,s1), (t2,s2)):=Q(t1,s1)  Q(t2,s2). In this case, each
+ curve point has roughly q representations as an ordered pair
+ ((t1,s1), (t2,s2)) on average. In fact, one can show that if the
+ input pairs are generated uniformly at random, then the corresponding
+ curve points follow a distribution that is also (statistically
+ indistinguishable from) a uniform distribution, and viceversa.
+ Here, each pair ((t1,s1), (t2,s2)) deterministically yields a curve
+ point, whereas for each curve point Q, a randomized algorithm yields
+ an ordered pair ((t1,s1), (t2,s2)) of preimages of Q, where the
expected number of randomized preimages one has to try is small
 (four if one uses the mapping of Appendix L.3.1; two if one uses the
 mapping of Appendix L.3.2). For further details, see Algorithm 1 of
 [Tibouchi].
+ (four if one uses the mapping of Appendix K.4.1; two if one uses the
+ mapping of Appendix K.4.2). Further details are out of scope.
Appendix M. Curve secp256k1 and Friend
+ NOTE 1: The main difference between the two constructions above is
+ that that the first construction uses the mappings to curve points
+ described in Appendix K.3, while the second construction uses the
+ mappings to highorder curve points described in Appendix K.4. Note
+ that Q2((t1,s1), (t2,s2)) assumes all values (+/) P(t1) (+/) P(t2)
+ if one considers all possible values for the binary digits s1 and s2.
+ (This, thereby, includes the value P2(t1, t2).)
M.1. Curve Definition and Alternative Representation
+ NOTE 2: The second mapping above operates on input pairs (t,s), where
+ t is an element of GF(q) that is not a square in GF(q) and where s is
+ a binary digit from the set {0,1}. One can use these mappings to
+ produce a mapping from the nonzero elements of GF(q) to points of a
+ curve via function composition, where one first maps any nonzero
+ element u of GF(q) to the pair (t,s):=(delta*u^2, par(u)), where
+ delta is a fixed element of GF(q) that is not a square in GF(q), and
+ where one subsequently applies any of the mappings above to yield a
+ point of the curve in question. The resulting mapping from the
+ nonzero elements of GF(q) to highorder curve points can be extended
+ further to one that operates on all elements of GF(q) by mapping 0 to
+ any fixed highorder point of the curve in question (e.g., to the
+ fixed "curve offset" P0 of this curve [henceforth called the default
+ completed mapping]). Depending on applicationspecific criteria, yet
+ other function compositions may be preferred. For the first mapping
+ above, one can use a similar function composition, where one simply
+ drops the binary digit s and maps 0 to the point at infinity or any
+ other suitable curve point. Further details are out of scope.
+
+Appendix L. Curve secp256k1 and Friend
+
+ This section illustrates how isogenies can be used to yield curves
+ with specific properties (here, for illustrated for the "BitCoin"
+ curve secp256k1).
+
+L.1. Curve Definition and Alternative Representation
The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined
over the prime field GF(p), with p:=2^2562^322^92^82^72^62^41,
where a:=0 and b:=7. This curve has order h*n, where h=1 and where n
is a prime number. For this curve, domain parameter a is zero,
whereas b is not. The quadratic twist of this curve has order h1*n1,
where h1 is a 37bit integer and where n1 is a prime number. For
this curve, the base point is the point (GX, GY).
The curve secp256k1 is 3isogenous to the Weierstrass curve
secp256k1.m defined over GF(p), which has nonzero domain parameters a
and b and has as base point the pair (GmX,GmY), where parameters are
 as specified in Appendix M.3 and where the related mappings are as
 specified in Appendix M.2.
+ as specified in Appendix L.3 and where the related mappings are as
+ specified in Appendix L.2.
M.2. Switching Between Representations
+L.2. Switching Between Representations
Each affine point (X,Y) of secp256k1 corresponds to the point
(X',Y'):=(u(X)/w(X)^2,Y*v(X)/w(X)^3) of secp256k1.m, where u, v, and
w are the polynomials with coefficients in GF(p) as defined in
 Appendix M.4.1, while the point at infinity of secp256k1 corresponds
+ Appendix L.4.1, while the point at infinity of secp256k1 corresponds
to the point at infinity of secp256k1.m. Under this isogenous
mapping, the base point (GX,GY) of secp256k1 corresponds to the base
point (GmX,GmY) of secp256k1.m. The dual isogeny maps the affine
point (X',Y') of secp256k1.m to the affine point
(X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of secp256k1, where u',
v', and w' are the polynomials with coefficients in GF(p) as defined
 in Appendix M.4.2, while mapping the point at infinity O of
+ in Appendix L.4.2, while mapping the point at infinity O of
secp256k1.m to the point at infinity O of secp256k1. Under this dual
isogenous mapping, the base point (GmX, GmY) of secp256k1.m
corresponds to a multiple of the base point (GX, GY) of secp256k1,
where this multiple is l=3 (the degree of the isogeny; see the
description in Appendix F.4). Note that this isogenous map (and its
dual) primarily involves the evaluation of three fixed polynomials
involving the xcoordinate, which takes roughly 10 modular
multiplications (or less than 1% relative incremental cost compared
to the cost of an elliptic curve scalar multiplication).
M.3. Domain Parameters
+L.3. Domain Parameters
The parameters of the curve sec256k1 and the corresponding
3isogenous curve sec256k1.m are as indicated below. Here, the
domain parameters of the curve secp256k1 are as specified in [SEC2];
the domain parameters of secp256k1.m are "new".
General parameters (for all curves):
p 2^2562^322^92^82^72^62^41
@@ 3332,87 +3788,1151 @@
b 1771 (=0x06eb)
GmX 26591621185618668069038227574782692264471832498547635565821216767
730887659845
(=0x3aca5300 959fa1d0 baf78dcf f77a616f 395e586d 67aced0a
88798129 0c279145)
GmY 67622516283223102233819216063319565850973524550533340939716651159
860372686848

(=0x9580fce5 3a170f4f b744579f f3d62086 12cd6a23 3e2de237
f976c6a7 8611c800)
M.4. Isogeny Details
+L.4. Isogeny Details
The isogeny and dual isogeny are both isogenies with degree l=3.
Both are specified by a triple of polynomials u, v, and w (resp. u',
v', and w') of degree 3, 3, and 1, respectively, with coefficients in
GF(p). The coeffients of each of these polynomials are specified in
 Appendix M.4.1 (for the isogeny) and in Appendix M.4.2 (for the dual
+ Appendix L.4.1 (for the isogeny) and in Appendix L.4.2 (for the dual
isogeny). For each polynomial in variable x, the coefficients are
tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in
hexadecimal format.
M.4.1. Isogeny Parameters
+L.4.1. Isogeny Parameters
M.4.1.1. Coefficients of u(x)
+L.4.1.1. Coefficients of u(x)
0 0x54
1 0xa4d89db3ed06c81e6143ec2eca9f761d8d17260dc229e1da1f73f714506872a9
2 0xcc58ffccbd9febb4a66222c7d1311d988d88c0624bcd68ec4c758a8e67dfd99b
3 0x01
M.4.1.2. Coefficients of v(x)
+L.4.1.2. Coefficients of v(x)
0 0x1c
1 0x94c7bc69befd17f2fae2e3ebf24df1f355d181fa1a8056103ba9baad4b40f029
2 0xb2857fb31c6fe18ef993342bb9c9ac64d44d209371b41d6272b04fd61bcfc851
3 0x01
M.4.1.3. Coefficients of w(x)
+L.4.1.3. Coefficients of w(x)
0 0xe62c7fe65ecff5da53311163e8988ecc46c4603125e6b476263ac546b3efeae5
1 0x01
M.4.2. Dual Isogeny Parameters

M.4.2.1. Coefficients of u'(x)
+L.4.2. Dual Isogeny Parameters
+L.4.2.1. Coefficients of u'(x)
0 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa8c7
1 0x44cd5cd7ce55a801725891578fbe7356bd936355fd0e2f538797cecff7a37244
2 0x668d0011162006c3c889f4680f9a4b77d0d26a89e6bb87b13bd8d1cfdd600a41
3 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c
M.4.2.2. Coefficients of v'(x)
+L.4.2.2. Coefficients of v'(x)
0 0x4bda12f684bda12f684bda12f684bda12f684bda12f684bda12f684b8e38e23c
1 0x519ba9c1f48f68054def6a410f0fa6e8b71c6c3b4a8958324681f6508c01fada
2 0xb34680088b100361e444fa3407cd25bbe8693544f35dc3d89dec68e76eb00338
3 0x2f684bda12f684bda12f684bda12f684bda12f684bda12f684bda12f38e38d84
M.4.2.3. Coefficients of w'(x)
+L.4.2.3. Coefficients of w'(x)
0 0x4d7a804ce3901e71066ccbd44636539b2bb2df6c8e4be29d8d4fb028e43033de
1 0x01
+Appendix M. Curve448 and Cousins
+
+ This section introduces curves related to Curve448 and explains their
+ relationships.
+
+M.1. Curve Definition and Alternative Representations
+
+ The elliptic curve Curve448 is the Montgomery curve M_{A,B} defined
+ over the prime field GF(p), with p:=2^{448}2^{224}1, where
+ A:=156326 and B:=1. This curve has order h*n, where h=4 and where n
+ is a prime number. For this curve, A^24 is not a square in GF(p),
+ whereas A2 is. The quadratic twist of this curve has order h1*n1,
+ where h1=4 and where n1 is a prime number. For this curve, the base
+ point is the point (Gu, Gv), where Gu=5 and where Gv is an even
+ integer in the interval [0, p1].
+
+ This curve has the same group structure as (is "isomorphic" to) the
+ twisted Edwards curve E_{a,d} defined over GF(p), with as base point
+ the point (Gx, Gy), where parameters are as specified in
+ Appendix M.3. This curve is denoted as Ed448. For this curve, the
+ parameter a is a square in GF(p), whereas d is not, so the group laws
+ of Appendix C.3 apply.
+
+ The curve is also isomorphic to the elliptic curve W_{a,b} in short
+ Weierstrass form defined over GF(p), with as base point the point
+ (GX, GY), where parameters are as specified in Appendix M.3. This
+ curve is denoted as Wei448.
+
+M.2. Switching between Alternative Representations
+
+ Each affine point (u, v) of Curve448 corresponds to the point (X,
+ Y):=(u + A/3, v) of Wei448, while the point at infinity of Curve448
+ corresponds to the point at infinity of Wei448. (Here, we used the
+ mappings of Appendix D.2 and that B=1.) Under this mapping, the base
+ point (Gu, Gv) of Curve448 corresponds to the base point (GX, GY) of
+ Wei448. The inverse mapping maps the affine point (X, Y) of Wei448
+ to (u, v):=(X  A/3, Y) of Curve448, while mapping the point at
+ infinity of Wei448 to the point at infinity of Curve448. Note that
+ this mapping involves a simple shift of the first coordinate and can
+ be implemented via integeronly arithmetic as a shift of (pA)/3 for
+ the isomorphic mapping and a shift of (pA)/3 for its inverse, where
+ delta=(pA)/3 is the element of GF(p) defined by
+
+ delta 24227957476520229684977460262933484478454712022910602009383006
+ 63935374427222435908954654612328921819766962948206145457870178326
+ 72736371
+
+ (=0x55555555 55555555 55555555 55555555 55555555 55555555
+ 55555554 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
+ ffff3473).
+
+ (Note that, depending on the implementation details of the field
+ arithmetic, one may have to shift the result by +p or p if this
+ integer is not in the interval [0,p1].)
+
+ The curve Ed448 is isomorphic to the curve Curve448, where the base
+ point (Gu, Gv) of Curve448 corresponds to the base point (Gx,Gy) of
+ Ed448 and where the point at infinity and the point (0,0) of order
+ two of Curve448 correspond to, respectively, the point (0, 1) and the
+ point (0, 1) of order two of Ed448 and where each other point (u, v)
+ of Curve448 corresponds to the point (c*u/v, (u+1)/(u1)) of Ed448,
+ where c is the element of GF(p) defined by
+
+ c sqrt((A2)/B)
+
+ 19788846729546443953835400975385803825683515259105980214819977919
+ 60874042320025157136042631277930307478554244641856917664538448351
+ 92428
+ (=0x45b2c5f7 d649eed0 77ed1ae4 5f44d541 43e34f71 4b71aa96
+ c945af01 2d182975 0734cde9 faddbda4 c066f7ed 54419ca5 2c85de1e
+ 8aae4e6c).
+
+ (Here, we used the mapping of Appendix D.1 and normalized this using
+ the mapping of Appendix F.1 (where the element s of that appendix is
+ set to c above).) The inverse mapping from Ed448 to Curve448 is
+ defined by mapping the point (0, 1) and the point (0, 1) of order
+ two of Ed448 to, respectively, the point at infinity and the point
+ (0,0) of order two of Curve448 and having each other point (x, y) of
+ Ed448 correspond to the point ((y + 1)/(y  1), c*(y + 1)/((y1)*x))
+ of Curve448.
+
+ The curve Ed448 is isomorphic to the Weierstrass curve Wei448, where
+ the base point (Gx, Gy) of Ed448 corresponds to the base point
+ (GX,GY) of Wei448 and where the identity element (0,1) and the point
+ (0,1) of order two of Ed448 correspond to, respectively, the point
+ at infinity O and the point (A/3, 0) of order two of Wei448 and where
+ each other point (x, y) of Ed448 corresponds to the point (X,
+ Y):=((y+1)/(y1)+A/3, c*(y+1)/((y1)*x)) of Wei448, where c was
+ defined before. (Here, we used the mapping of Appendix D.3.) The
+ inverse mapping from Wei448 to Ed448 is defined by mapping the point
+ at infinity O and the point (A/3, 0) of order two of Wei448 to,
+ respectively, the identity element (0,1) and the point (0,1) of
+ order two of Ed448 and having each other point (X, Y) of Wei448
+ correspond to the point (c*(XA/3)/Y, (XA/3+1)/(XA/31)) of Ed448.
+
+ Note that these mappings can be easily realized if points are
+ represented in projective coordinates, using a few field
+ multiplications only, thus allowing switching between alternative
+ curve representations with negligible relative incremental cost.
+
+M.3. Domain Parameters
+
+ The parameters of the Montgomery curve and the corresponding
+ isomorphic curves in twisted Edwards curve and shortWeierstrass form
+ are as indicated below. Here, the domain parameters of the
+ Montgomery curve Curve448 and of the twisted Edwards curve Ed448 are
+ as specified in [RFC7748]; the domain parameters of Wei448 are "new".
+
+ IMPORTANT NOTE: the supposed base point of Ed448 specified in
+ [RFC7748] is incorrect, since it has order 2*n, and  in the notation
+ below  that point is the point (Gx,Gy)=(Gx, Gy)+(0,1). The
+ birational map in that document is also incorrect.
+
+ General parameters (for all curve models):
+
+ p 2^{448}2^{224}1
+ (=0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
+ fffffffe ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
+ ffffffff)
+
+ h 4
+
+ n 18170968107390172263733095197200113358841034017182951507037254979
+ 51460039615395857161957552916923759633102937090916623047737558596
+ 49779
+
+ (=2^{446}  0x8335dc16 3bb124b6 5129c96f de933d8d 723a70aa
+ dc873d6d 54a7bb0d)
+
+ h1 4
+
+ n1 18170968107390172263733095197200113358841034017182951507037254979
+ 51601601218258006270024365576458970017341485218301563757529931495
+ 32941
+
+ (=2^{446} + 0x0335dc16 3bb124b6 5129c96f de933d8d 723a70aa
+ dc873d6d 54a7bb0d)
+
+ Montgomery curvespecific parameters (for Curve448):
+
+ A 156326 (=0x0262a6)
+
+ B 1 (=0x01)
+
+ Gu 5 (=0x05)
+
+ Gv 35529392678556817526412750206378333480897639938771427183188089843
+ 51690887869674100029326737658645509101427741472681058389855952906
+ 06362
+
+ (=0x7d235d12 95f5b1f6 6c98ab6e 58326fce cbae5d34 f55545d0
+ 60f75dc2 8df3f6ed b8027e23 46430d21 1312c4b1 50677af7 6fd7223d
+ 457b5b1a)
+
+ Edwards curvespecific parameters (for Ed448):
+
+ a 1 (0x01)
+
+ d 39082/39081 = (A+2)/(A2)
+
+ (=611975850744529176160423220965553317543219696871016626328968936
+ 41508786004263647489178559928366602041476867897998937814706546281
+ 5545017)
+ (=0xd78b4bdc 7f0daf19 f24f38c2 9373a2cc ad461572 42a50f37
+ 809b1da3 412a12e7 9ccc9c81 264cfe9a d0809970 58fb61c4 243cc32d
+ baa156b9)
+
+ Gx 34539749303972951637400860415053741026665526007518329021640697028
+ 16456950736723444304817877593406332217083915834240417889241245677
+ 00732
+
+ (=0x79a70b2b 70400553 ae7c9df4 16c792c6 1128751a c9296924
+ 0c25a07d 728bdc93 e21f7787 ed697224 9de732f3 8496cd11 69871309
+ 3e9c04fc)
+
+ Gy 3/2
+
+ 36341936214780344527466190394400226717682068034365903014074509959
+ 03061640833653863431981918493382729650444422309218186805267490091
+ 82721
+
+ (=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff
+ ffffffff 80000000 00000000 00000000 00000000 00000000 00000000
+ 00000001)
+
+ Weierstrass curvespecific parameters (for Wei448):
+
+ a 48455914953040459369954920525866968956909424045821204018766013278
+ 70748854444871817909309224657843639533925896412290915740356571996
+ 37535
+
+ (=0xaaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa
+ aaaaaaa9 ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe
+ 1a76d41f)
+
+ b 26919952751689144094419400292148316087171902247678446677092229599
+ 28193808024928787727394013698802021963292164673494953191916856645
+ 13904
+
+ (=0x5ed097b4 25ed097b 425ed097 b425ed09 7b425ed0 97b425ed
+ 097b425e 71c71c71 c71c71c7 1c71c71c 71c71c71 c71c71c7 1c72c87b
+ 7cc69f70)
+
+ GX 48455914953040459369954920525866968956909424045821204018766013278
+ 70748854444871817909309224657843639533925896412290915740356653456
+ 29073
+
+ (=0xaaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa
+ aaaaaaaa 00000000 00000000 00000000 00000000 00000000 00000000
+ 0000cb91)
+
+ GY 35529392678556817526412750206378333480897639938771427183188089843
+ 51690887869674100029326737658645509101427741472681058389855952906
+ 06362
+
+ (=0x7d235d12 95f5b1f6 6c98ab6e 58326fce cbae5d34 f55545d0
+ 60f75dc2 8df3f6ed b8027e23 46430d21 1312c4b1 50677af7 6fd7223d
+ 457b5b1a)
+
+Appendix N. Further Cousins of Curve448
+
+ This section introduces some further curves related to Curve448 and
+ explains their relationships.
+
+N.1. Further Alternative Representations
+
+ The Weierstrass curve Wei448 is isomorphic to the Weierstrass curve
+ Wei448.1 defined over GF(p), with as base point the pair (G1X,G1Y),
+ and isogenous to the Weierstrass curve Wei448.3 defined over GF(p),
+ with as base point the pair (G3X, G3Y), where parameters are as
+ specified in Appendix N.3 and where the related mappings are as
+ specified in Appendix N.2. The Edwards curve Ed448 is isogenous to
+ the Edwards curve Edwards448 defined over GF(p), with as base point
+ the pair (G1x,G1y), where parameters are as specified in Appendix N.3
+ and where the related mappings are as specified in Appendix N.2.
+
+N.2. Further Switching
+
+ Each affine point (X, Y) of Wei448 corresponds to the point (X',
+ Y'):=(X*s^2,Y*s^3) of Wei448.1, where s is the element of GF(p)
+ defined by
+
+ s 52322274343677442779379520589771028818568404587729117919590511061
+ 93509510238347880134473888687471465216641846232724641298954890800
+ 00881
+
+ (=0xb848cd01 981d2f83 f2829b42 eb86914e 88f44c9d 05dcbdff
+ dbdd1e56 c4674bc8 d6d90d91 862a38f5 ca797ca7 f21c05cf a7ac32bf
+ d2ca0171),
+
+ while the point at infinity of Wei448 corresponds to the point at
+ infinity of Wei448.1. (Here, we used the mapping of Appendix F.3.)
+ Under this mapping, the base point (GX, GY) of Wei448 corresponds to
+ the base point (G1X,G1Y) of Wei448.1. The inverse mapping maps the
+ affine point (X', Y') of Wei448.1 to (X,Y):=(X'/s^2,Y'/s^3) of
+ Wei448, while mapping the point at infinity O of Wei448.1 to the
+ point at infinity O of Wei448. Note that this mapping (and its
+ inverse) involves a modular multiplication of both coordinates with
+ fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which
+ can be precomputed.
+
+ Each affine point (X,Y) of Wei448 for which the Ycoordinate is
+ nonzero (i.e., each point with order larger than two) corresponds to
+ the point (X',Y'):=(X1*t^2,Y1*t^3) of Wei448.3, where
+ (X1,Y1)=(u(X)/w(X),Y*v(X)/w(X)^2), where u, v, and w are the
+ polynomials with coefficients in GF(p) as defined in Appendix N.4.1
+ and where t is the element of GF(p) defined by
+
+ t 23579450751475691430882365546539966269774125426758968522698856022
+ 13378944265540874438945283200254318223329383397068961863760712339
+ 07365
+
+ (=0x530c9a1d7cf071d09646b83db246626b4e57ba5d6a791bef761972543209d
+ c5c20d81498d5ab8d7a2fb22507ca68c040a6c82eb3b6c7aaa5),
+
+ while the point at infinity and the point (A/3,0) of order two of
+ Wei448 corresponds to the point at infinity of Wei448.3. (Here, we
+ used the isogenous mapping of Appendix F.4.) Under this isogenous
+ mapping, the base point (GX,GY) of Wei448 corresponds to the base
+ point (G3X,G3Y) of Wei448.3. The dual isogeny maps the affine point
+ (X',Y') of Wei448.3 to the affine point
+ (X,Y):=(u'(X1)/w'(X1),Y1*v'(X1)/w'(X1)^2) of Wei448, where
+ (X1,Y1)=(X'/t^2,Y'/t^3) and where u', v', and w' are the polynomials
+ with coefficients in GF(p) as defined in Appendix N.4.2, while
+ mapping the point at infinity O of Wei448.3 to the point at infinity
+ O of Wei448. Under this dual isogenous mapping, the base point (G3X,
+ G3Y) of Wei448.3 corresponds to a multiple of the base point (GX,
+ GY) of Wei448, where this multiple is l=2 (the degree of the isogeny;
+ see the description in Appendix F.4). Note that this isogenous map
+ (and its dual) primarily involves the evaluation of three fixed
+ polynomials involving the xcoordinate, which takes only a few
+ modular multiplications (less than 0.5% relative incremental cost
+ compared to the cost of an elliptic curve scalar multiplication).
+
+ Each point (x1,y1) of Edwards448 corresponds to the point (x,y) of
+ Ed448, where
+
+ x = c*x1*y1/(1d1*x1^2*y1^2) = c*x1*y1/(2x1^2y1^2) and
+
+ y =(1 + d1*x1^2*y1^2)/(y1^2x1^2) = (x1^2+y1^2)/(x1^2y1^2).
+
+ (Here, we used the 4isogenous mapping of Appendix F.4. Under this
+ isogenous mapping, the base point (G1x, G1y) of Edwards448
+ corresponds to the base point (Gx,Gy) of Ed448. The dual isogeny
+ maps each point (x,y) of Ed448 to the point (x1,y1) of Edwards448,
+ where
+ x1 = (4*x*y/c)/(y^2x^2) and
+
+ y1 = (1  d*x^2*y^2)/(1 + d*x^2*y^2) = (2x^2y^2)/(x^2+y^2).
+
+ Under this dual isogenous mapping, the base point (Gx, Gy) of Ed448
+ corresponds to a multiple of the base point (G1x, G1y) of Edwards448,
+ where this multiple is l=4 (the degree of the isogeny; see the
+ description in Appendix F.4). Note that this isogenous map (and its
+ dual) primarily involves the evaluation of three fixed polynomials,
+ which takes only a few multiplications (less than 0.5% relative
+ incremental cost compared to the cost of an elliptic curve scalar
+ multiplication).
+
+ The point (0,1) and the point (0,1) of order two of Edwards448
+ correspond to, respectively, the point at infinity and the point
+ (0,0) of order two of Curve448, while each other point (x1,y1) of
+ Edwards448 corresponds to the point (u,v) of Curve448, where
+
+ u = y1^2/x1^2 and v = y1*(2x1^2y1^2)/x1^3.
+
+ Under this isogenous mapping, the base point (G1x, G1y) of Edwards448
+ corresponds to the base point (Gu,Gv) of Curve448. The dual isogeny
+ maps both the point at infinity and the point (0,0) of order two of
+ Curve448 to the point (0,1) of Edwards448, while each other point
+ (u,v) of Curve448 corresponds to the point (x1,y1) of Edwards448,
+ where
+
+ x1 = 4*(u^21)*v/((u^21)^2+4*v^2) and
+
+ y1 = u*((u^21)^24*v^2)/(2*(u^2+1)*v^2u*(u^21)^2).
+
+ Under this dual isogenous mapping, the base point (Gu, Gv) of
+ Curve448 corresponds to a multiple of the base point (G1x, G1y) of
+ Edwards448, where this multiple is l=4 (the degree of the isogeny;
+ see above).
+
+N.3. Further Domain Parameters
+
+ The parameters of the Weierstrass curve with a=1 that is isomorphic
+ with Wei448 and the parameters of the Weierstrass curve with a=3
+ that is isogenous with Wei448 are as indicated below. Both domain
+ parameter sets can be exploited directly to derive more efficient
+ point addition formulae, should an implementation facilitate this.
+ The domain parameters of the twisted Edwards curve Edwards448 are as
+ specified in [RFC7748].
+
+ General parameters: same as for Wei448 (see Appendix M.3)
+ Weierstrass curvespecific parameters (for Wei448.1, i.e., with a=1):
+
+ a 1 (=0x01)
+
+ b 65961281701807170531944804985907990287225248056560036392380945951
+ 38183088507635437786021044927715119224497407914895790669345268896
+ 52743
+
+ (=0xe8528596 bfbcbac9 7ebdbe4e 9683e25c 73a5ff37 6c4cd400
+ 5a75c425 8e3eb05a 9f6f8c24 24cb5aa9 0dcf9fa4 cab6691d 5530347c
+ 28437207)
+
+ G1X 19236211982508211644805033459306273038523230481309141518540414163
+ 72091186292458482231912460243257247478684005448999746809691007995
+ 9723
+
+ (=0x06c672d5 b5bae33b 010fa210 9de7937a 95db8ffc 043c507f
+ 5e0d07a1 25382eaf 13f5fc3b 75db2614 6e6d002f d8364ed6 c9bc8fbf
+ bbda22ab)
+
+ G1Y 30319443056877169804488072384563064288675576234196773667920807567
+ 79177927858755621958756222206632465988308466319556948821775845861
+ 64158
+
+ (=0x6ac9c53c 767cd3ae cbf904a1 2923502f 115355d1 6ae8911c
+ 5c92f612 aa854455 d1e6d29f 4db4ddea 519a174f c0dd2505 ec3328ba
+ 250a07be)
+
+ Weierstrass curvespecific parameters (for Wei448.3, i.e., with a=
+ 3):
+
+ a 3
+
+ (=0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
+ fffffffe ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
+ fffffffc)
+
+ b 69993768681000150084833669961900533067383335592494498709534693464
+ 91314250731583068774689950893229681024927315747794587331422088592
+ 54465
+
+ (=0xf686723d 80e29d06 2d00a9f1 3305b698 85790019 cca78035
+ 9dac226b efb1ae21 125397dd 16f255b0 cc5d18e5 43582a1c af90dfe2
+ c0aeaec1)
+
+ G3X 40677474994869876470916133424311516856662407970799424837841348421
+ 87696274665113140719001227030116551378877280368526334985627104680
+ 88795
+ (=0x8f452c6b dc3265dd 580b2638 59a02b20 198cc020 1dd7fba1
+ 8b431694 4a936052 fb4e4a41 93d01fa5 5fb5c732 7393208b 8170f3f2
+ be78d3db)
+
+ G3Y 54594210970205994927260789585006437115117066846498189378285031510
+ 90310290468347714929366106635470978666795512446629051235704504868
+ 06147
+
+ (=0xc0494f90 461db11c 35fb7646 8349399a ae230351 11330cce
+ b7473244 ab63c955 cf6ec02f 2656b439 44b19f4b 52eef12e 73026bbc
+ 84444683)
+
+ Edwards curvespecific parameters (for Edwards448):
+
+ a 1 (0x01)
+
+ d1 39081 = (A2)/4
+
+ (=726838724295606890549323807888004534353641360687318060281490199
+ 18061232816673077268639638369867654593008888446184363736105349801
+ 8326358)
+
+ (=0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
+ fffffffe ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
+ ffff6756)
+
+ G1x 22458004029592430018760433409989603624678964163256413424612546168
+ 69504154674060329090291928693579532825780320751464461736746026352
+ 47710
+
+ (=0x4f1970c6 6bed0ded 221d15a6 22bf36da 9e146570 470f1767
+ ea6de324 a3d3a464 12ae1af7 2ab66511 433b80e1 8b00938e 2626a82b
+ c70cc05e)
+
+ G1y 29881921007848149267601793044393067343754404015408024209592824137
+ 23315061898358760035368786554187847339823032335034625005315450628
+ 32660
+
+ (=0x693f4671 6eb6bc24 88762037 56c9c762 4bea7373 6ca39840
+ 87789c1e 05a0c2d7 3ad3ff1c e67c39c4 fdbd132c 4ed7c8ad 9808795b
+ f230fa14)
+
+N.4. Isogeny Details
+
+ The isogeny and dual isogeny are both isogenies with degree l=2.
+ Both are specified by a triple of polynomials u, v, and w (resp. u',
+ v', and w') of degree 2, 2, and 1, respectively, with coefficients in
+ GF(p). The coeffients of each of these polynomials are specified in
+ Appendix N.4.1 (for the isogeny) and in Appendix N.4.2 (for the dual
+ isogeny). For each polynomial in variable x, the coefficients are
+ tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in
+ hexadecimal format.
+
+N.4.1. Isogeny Parameters
+
+N.4.1.1. Coefficients of u(x)
+
+ 0 0x01
+
+ 1 0x55555555555555555555555555555555555555555555555555555554ffffffff
+ ffffffffffffffffffffffffffffffffffffffffffff3473
+
+ 2 0x01
+
+N.4.1.2. Coefficients of v(x)
+
+ 0 0x1c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c55555555
+ 5555555555555555555555555555555555555555f72db94a
+
+ 1 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa9ffffffff
+ fffffffffffffffffffffffffffffffffffffffffffe68e6
+
+ 2 0x01
+
+N.4.1.3. Coefficients of w(x)
+
+ 0 0x55555555555555555555555555555555555555555555555555555554ffffffff
+ ffffffffffffffffffffffffffffffffffffffffffff3473
+
+ 1 0x01
+
+N.4.2. Dual Isogeny Parameters
+
+N.4.2.1. Coefficients of u'(x)
+
+ 0 0x016c26e0e8
+
+ 1 0x5555555555555555555555555555555555555555555555555555555500000000
+ 0000000000000000000000000000000000000000000065c6
+
+ 2 0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffc0000000
+ 000000000000000000000000000000000000000000000000
+
+N.4.2.2. Coefficients of v'(x)
+
+ 0 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaaaaa
+ aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa45836c31
+
+ 1 0x5555555555555555555555555555555555555555555555555555555500000000
+ 0000000000000000000000000000000000000000000065c6
+
+ 2 0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffe0000000
+ 000000000000000000000000000000000000000000000000
+
+N.4.2.3. Coefficients of w'(x)
+
+ 0 0x5555555555555555555555555555555555555555555555555555555500000000
+ 000000000000000000000000000000000000000000019719
+
+ 1 0x01
+
+Appendix O. Representation Examples Curve448 Family Members
+
+ 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
+
+ k 62662039304523906689788124833289384446202946474440057655160773695
+ 63756342505410402166230018620066482794080866641616932013327623579
+ 01952
+
+ (=0xdcb3bbb9 e42d7aca fe62052d 902123c7 0872b984 4c1e199f
+ 7c5d37bd 1171102b c20a6352 d9c91886 29b685de 51441e84 3afe2665
+ 5251aa80).
+
+O.1. Example with Curve448
+
+ Pm=(u, v), k*Pm=(u1, v1), and (k+1)*Pm=(u2, v2) with Curve448:
+
+ u 53298594738299085772373536080133483236673782578895339676785179923
+ 90764298300090102709453866054695061082746243636045110750296444932
+ 27715
+
+ (=0xbbb91ba3 b0ef74c3 214394b4 d8f0d32d c4a92193 5f573009
+ 39fd86a3 8d54be2a 4d63380b 692381bb ed7339fd dca7b0cd a80166fe
+ 18c086c3).
+
+ v 30578727850066757341435137807347775064915058999485530015946871157
+ 86794631407274936870618580714107931661730999350222644894729285604
+ 97149
+
+ (=0x6bb38e82 8d52337f 6f0395ef dc16c776 52162f5e 309112ae
+ fc7401bf 0cfb0499 eb1ed555 bf507ebc c33b4753 2d6dc6c5 d68dea1c
+ c1e4c1fd).
+
+ u1 64579461799301726935877447646800238443923683299745374127971411973
+ 12515295161791889743228049222279188968365877164188075095074418806
+ 82513
+
+ (=0xe37497bf 9f704689 54ec6537 cbbe91d0 3ffcdcdb 8b707253
+ a2212cdb e020ba9a 0bf65a1d 5d9a128a f85c63a2 79a00139 7aca56db
+ 15335011).
+
+ v1 55735504615964066386264989698774850924544182484936624265048483231
+ 35693859362627880184586282439234602798023594054611737412667543758
+ 11547
+
+ (=0xc44e5e0f 2c254d23 1dc082db 77175e8c fd37793c 22ebe200
+ 77905a5f 750b3c9f 4a95d4d5 4e1a1e54 d2d31689 4249252d 0c8b1c45
+ 1c1481db).
+
+ u2 32685564331119553171673802371596819258307818641496728161547328225
+ 07595618587323619256769558535630624960575212644680149034661008254
+ 8876
+
+ (=0x0b831eca 9c6215b0 5d830361 4013732f 7a9dd07f ebb9441e
+ 49129264 eb724f44 dc53671c ffabb9ee 0c02aa74 b083cd82 a821a4cf
+ 6f6d8c8c).
+
+ v2 57682103223585233918507344950062950306770296215271320612937204938
+ 77499282103483092990510136901415757273082719665657484294344333591
+ 20741
+
+ (=0xcb2988a4 6e37f9a9 a7a1255b 2fd2eea9 82308e7c eb8e18b8
+ 2252175f fd416a10 5984c6b8 36470e48 31879293 8f6139c6 f96164cb
+ 14010965).
+
+ 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) 0x80aa5152 6526fe3a 841e4451 de85b629 8618c9d9 52630ac2
+ 2b107111 bd375d7c 9f191e4c 84b97208 c7232190 2d0562fe
+ ca7a2de4 b9bbb3dc;
+
+ repr(Pm) 0xc386c018 fe6601a8 cdb0a7dc fd3973ed bb812369 0b38634d
+ 2abe548d a386fd39 0930575f 9321a9c4 2dd3f0d8 b4944321
+ c374efb0 a31bb9bb 80;
+
+ repr(k*Pm) 0x11503315 db56ca7a 3901a079 a2635cf8 8a129a5d 1d5af60b
+ 9aba20e0 db2c21a2 5372708b dbdcfc3f d091becb 3765ec54
+ 8946709f bf9774e3 80,
+
+ where the leftmost bit of the rightmost octet indicates the parity of
+ the vcoordinate of the point of Curve448 in question (which, in this
+ case, are both one, since v and v1 are odd). See Appendix H.2 and
+ Appendix I 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. (Note that
+ due to the bitsize of the prime p, the lossless representation
+ requires an additional octet compared to the lossy representation
+ without vcoordinate.) Another difference is that [RFC7748] allows
+ nonunique representations of some elements of GF(p), whereas our
+ representation conventions do not (since tight).
+
+ A randomized representation (t1, t2) of the point k*Pm in tight LSB/
+ msb order is given by
+
+ t1 642695971489808425948939115432957219707501931105169269237
+ 122551860533279049805112466411050091592893048844749561382
+ 909707113070546618079
+
+ (=0xdf86cb83 ae1ca6e6 da6afbaf afbb2fc0 606a136f 80eea078
+ c868a5d7 7e638d09 99518385 65250cf1 9c034f96 1fa28f54
+ f3016600 68335de2)
+
+ t2 569275737967591640709387827593956375775147481657775744720
+ 460881642951497067363381071471046477130052706607411985560
+ 522861593611384288817
+ (=0x3176361c 580a7bcd d7880d84 aba10bc6 57010328 afb728cc
+ 2016461b 246bef46 0eb4bb04 8c1a3616 c3f74a56 3cc1790f
+ 6472256b ca3481c8),
+
+ where this representation is defined in Appendix K.5 and uses the
+ mapping of Appendix K.3.2 with the default square root function.
+
+O.2. Example with Ed448
+
+ Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Ed448:
+
+ x 12711234107145442394649604543297947887906244696692372551963816418
+ 93066253979844478364753304240794498368174540810674220788120782656
+ 62747
+
+ (=0x2cc52fd1 6370554f 00c0f73f 64bda240 f5950177 d9033f6d
+ 74acd12d 68c79a51 315f556f 240973f9 e5f71ed7 9314ee9d c87f0b1b
+ bcc0fd1b).
+
+ y 69251010954633529003803699627438795111055087299023774963200632446
+ 22677618700964599963790149315020469517869703738619380660774687159
+ 85238
+
+ (=0xf3e8bb95 c9675fd0 0c388fc5 e96cfbc7 3c19d945 76849979
+ 34c4ab60 73c4a763 c2a89bac d3879838 f4de11a3 3a4710c2 396dea1d
+ cc012956).
+
+ x1 69268794439088733926883958090256942256857349796922332363888137509
+ 71700910417786272464007666020220956482611896297610096130434552586
+ 39205
+
+ (=0xf3f8c472 ca2e730b 05cc9092 f9d40956 029113e3 e92c2d55
+ 76406db2 c2903721 62f43371 1c0ec80c f8d7222d 1d701467 9da18531
+ 0fb5bb65).
+
+ y1 50516707418203531159001223293623288296803299598968490915066154362
+ 78541820739332329525138363312119838075438487384161435963107103409
+ 09734
+
+ (=0xb1eccbfc 5f5f92e8 d9129d14 b721c524 96fc1b1f a4c17c5f
+ e4979b0c 763f34ba 91299376 d2499220 19b05f56 c3bb6b5d ac988271
+ 287d7aa6).
+
+ x2 67287262124444231243108222498849910362455590990935326363062127166
+ 04126947894055981270997819628982374416022607672923451356182938105
+ 87868
+ (=0xecfe1a4f a4cd7e2f 19afcf16 1ce2198f 0a850beb 41afa209
+ 94741609 5b1a858a 8e9548f5 011d188e d50484d3 119103f6 8bcd5ba2
+ a6e3e8dc).
+
+ y2 13744276256057290540518554008940700979716578667786691114397525367
+ 92684542875757407063179870154307882588988293167000249160114881659
+ 30341
+
+ (=0x3068a338 4016ebfd a229ac73 b5c30bba ff67e183 71d1185f
+ 19dfbbee 28478baf 9034ebad 51407f01 35162743 c2c234bc 2d484c13
+ 552ea565).
+
+ The representation of k and the compressed representations of Pe and
+ k*Pe in tight LSB/lsborder are given by
+
+ repr(k) =0x01558a4a a6647f5c 2178228a 7ba16d94 6118939b 4ac65043
+ d4088e88 bdecba3e f9987832 219d4e10 e3c48409 b4a0467f
+ 535eb427 9dddcd3b;
+
+ repr(Pe) =0x6a948033 b857b69c 4308e25c c5887b2f 1c19e1cb 35d91543
+ c6e523ce 06d5232c 9e99216e a29b983c e3df3697 a3f11c30
+ 0bfae693 a9dd17cf 01;
+
+ repr(k*Pe) =0x655ebe14 8e411935 bad6ddc3 6afa0d98 0449924b 6ec99489
+ 5d2cfc6e 30d9e927 fa3e8325 f8d83f69 24a384ed 28b9489b
+ 1749fafa 3fd3378d 01,
+
+ where the rightmost bit of the rightmost octet indicates the parity
+ of the xcoordinate of the point of Ed448 in question (which, in this
+ case, are both one, since x and x1 are odd). See Appendix H.3 and
+ Appendix I 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 [RFC7748], [RFC8032]
+ requires unique representations of all elements of GF(p).
+
+ A randomized representation (t1, t2) of the point k*Pe in tight LSB/
+ lsb order is given by
+
+ t1 397357047759003459380102071532091085834125520561197668989
+ 747600577137881485970346806080038194336473483709104865191
+ 806326006691504231547
+
+ (=0xde295d0e 5efceb9b f43967ca be45a54b a1f75bdd a4b1b1b3
+ b24a8d1d f2056329 e506867e c968aa8b 866017e4 f0cbc343
+ 2cf8e7fa 0b202fd1)
+
+ t2 711800301530600330791068062467600183663589340593884950808
+ 136091389056251997893995894309660827763434071897306280320
+ 151044063120296064809
+
+ (=0x94ecb72a 069a5322 e62d9357 c49d5664 1c351611 d1f361a8
+ cbb8a12c f410e821 4fbe8e02 8d85d404 399b4c7c 5a6a72ce
+ deef7b08 96302d5f),
+
+ where this representation is defined in Appendix K.5 and uses the
+ mapping of Appendix K.3.3 with the default square root function and
+ underlying isomorphic mapping between Ed448 and Curve448 of
+ Appendix M.2.
+
+O.3. Example with Wei448
+
+ Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei448:
+
+ X 29070637261778856087396075817199998758219070555984737667402173284
+ 55389871077654193754799253725773241315783295429899652880118118204
+ 91344
+
+ (=0x6663c64e 5b9a1f6d cbee3f5f 839b7dd8 6f53cc3e 0a01dab3
+ e4a8314e 8d54be2a 4d63380b 692381bb ed7339fd dca7b0cd a80166fe
+ 18c15250).
+
+ Y 30578727850066757341435137807347775064915058999485530015946871157
+ 86794631407274936870618580714107931661730999350222644894729285604
+ 97149
+
+ (=0x6bb38e82 8d52337f 6f0395ef dc16c776 52162f5e 309112ae
+ fc7401bf 0cfb0499 eb1ed555 bf507ebc c33b4753 2d6dc6c5 d68dea1c
+ c1e4c1fd).
+
+ X1 40351504322781497250899987383866753965468971276834772118588405333
+ 77140867939355980788573436893357369201402928958042617224896092079
+ 46142
+
+ (=0x8e1f426a 4a1af133 ff970fe2 76693c7a eaa78786 361b1cfe
+ 4ccbd786 e020ba9a 0bf65a1d 5d9a128a f85c63a2 79a00139 7aca56db
+ 15341b9e).
+
+ Y1 55735504615964066386264989698774850924544182484936624265048483231
+ 35693859362627880184586282439234602798023594054611737412667543758
+ 11547
+
+ (=0xc44e5e0f 2c254d23 1dc082db 77175e8c fd37793c 22ebe200
+ 77905a5f 750b3c9f 4a95d4d5 4e1a1e54 d2d31689 4249252d 0c8b1c45
+ 1c1481db).
+
+ X2 51724471386152414687122300763026650882740205909970876834920746101
+ 21508416303604179834986180511406702029983417676758930643822754281
+ 77944
+
+ (=0xb62dc975 470cc05b 082dae0b eabe1dda 25487b2a 9663eec8
+ f3bd3d0e eb724f44 dc53671c ffabb9ee 0c02aa74 b083cd82 a821a4cf
+ 6f6e5818).
+
+ Y2 57682103223585233918507344950062950306770296215271320612937204938
+ 77499282103483092990510136901415757273082719665657484294344333591
+ 20741
+
+ (=0xcb2988a4 6e37f9a9 a7a1255b 2fd2eea9 82308e7c eb8e18b8
+ 2252175f fd416a10 5984c6b8 36470e48 31879293 8f6139c6 f96164cb
+ 14010965).
+
+ The representation of k and the compressed representations of Pw and
+ k*Pw in tight MSB/msborder are given by
+
+ repr(k) =0xdcb3bbb9 e42d7aca fe62052d 902123c7 0872b984 4c1e199f
+ 7c5d37bd 1171102b c20a6352 d9c91886 29b685de 51441e84
+ 3afe2665 5251aa80;
+
+ repr(Pw) =0x80 6663c64e 5b9a1f6d cbee3f5f 839b7dd8 6f53cc3e
+ 0a01dab3 e4a8314e 8d54be2a 4d63380b 692381bb ed7339fd
+ dca7b0cd a80166fe 18c15250;
+
+ repr(k*Pw) =0x80 8e1f426a 4a1af133 ff970fe2 76693c7a eaa78786
+ 361b1cfe 4ccbd786 e020ba9a 0bf65a1d 5d9a128a f85c63a2
+ 79a00139 7aca56db 15341b9e,
+
+ where the leftmost bit of the leftmost octet indicates the parity of
+ the Ycoordinate of the point of Wei448 in question (which, in this
+ case, are both one, since Y and Y1 are odd). See Appendix H.1 and
+ Appendix I 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) =0x6663c64e 5b9a1f6d cbee3f5f 839b7dd8 6f53cc3e 0a01dab3
+ e4a8314e 8d54be2a 4d63380b 692381bb ed7339fd dca7b0cd
+ a80166fe 18c15250
+ 6bb38e82 8d52337f 6f0395ef dc16c776 52162f5e 309112ae
+ fc7401bf 0cfb0499 eb1ed555 bf507ebc c33b4753 2d6dc6c5
+ d68dea1c c1e4c1fd,
+
+ whereas the SEC1compliant compressed representation of the point Pw
+ in tight MSB/msborder is given by
+
+ compr(Pw) =0x03 6663c64e 5b9a1f6d cbee3f5f 839b7dd8 6f53cc3e
+ 0a01dab3 e4a8314e 8d54be2a 4d63380b 692381bb ed7339fd
+ dca7b0cd a80166fe 18c15250.
+
+ 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), and replacing this leftmost octet with 0x02 or
+ 0x03, depending on whether t=0 or t=1, respectively, where the
+ reverse procedure is uniquely defined. For further details, see
+ [SEC1]. Note that, due to the bitsize of the prime p, the squeezed
+ compressed format repr(Pw) and the SEC1compliant compressed format
+ compr(Pw) have the same size.
+
+ A randomized representation (t1, t2) of the point k*Pw in tight MSB/
+ msb order is given by
+
+ t1 655783099225353926682910498535559663266263823350679216116
+ 172951494291735730803127024621397533084891460609898061397
+ 896825551162064841608
+
+ (=0xe6f93655 2765628b accfe61c 7dc6a594 e06fb243 70195ded
+ 74d88a53 fdedc2e8 077e0eff 62fa6a80 fa26b499 1f8796f5
+ 21f2f03b f7e92b88)
+
+ t2 357918241879339174086992006475988394618511927120788596330
+ 507910466738735762660894972854331591097934354210992993787
+ 402433561014235472657
+
+ (=0x7e0ffcaf 7add27bc bb723629 95fdedd0 8769f676 78d953bc
+ 0d38f4f6 d63a59dc 00f2d55a a4db7dab 16364503 591edcb1
+ e095a577 43dea311),
+
+ where this representation is defined in Appendix K.5 and uses the
+ mapping of Appendix K.3.1 with the default square root function.
+
+O.4. Example with Wei448.3
+
+ Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei448.3:
+
+ X 54121793865726175505902038600562190720650456678500106168173285986
+ 99999531708218763586616425010404811083912084906688745035466757984
+ 48968
+
+ (=0xbe9f5a23 51709e13 d5ad50c2 a27be8ee 1b051970 2580d5c3
+ c2de7f75 3010635e d89ef547 8b67dc54 16d63c5b 1cc1116f dd453515
+ 71b39b48).
+
+ Y 14962282101304548030627835311887275833718070818965306362006934455
+ 59168773381983445709256615887526455657034051121085622763637035580
+ 12661
+
+ (=0x34b2dcc4 92d6a940 e6249c14 122d0ba4 5dc040e9 3f060d8f
+ a65fa300 eb3cc969 25188b59 2d31039c f7a8e14a 48320a32 efe9b42b
+ 986afef5).
+
+ X1 18808295916646645825216065847266150404062470629833854840155953858
+ 63091795696773741607659794828181692381790403935750135247605982648
+ 6547
+
+ (=0x069fdd7c 2ec1ecbf d3cd0e27 1e8110c6 d2e478f2 aa393928
+ 64a5511e da0b8dc7 3834fd57 b5ef8527 361a8176 c6da44ee 63701c0c
+ f49d7d13).
+
+ Y1 12212945244064471634326466576257313927639904273911210953487761656
+ 77684161144865373513143868308041748047828401098060667767703779846
+ 85920
+
+ (=0x2b03e68e b61581c4 9f977443 3e1ddc63 976f8f1d cdb185ee
+ 9c53328d b425973d 359bbc09 468645c4 0996a2c7 fda561be acb4d0b5
+ 745ab760).
+
+ X2 58672976485086436102048679093716482249296622848351051568512020319
+ 97872083950108489407370832733527154843728068195507632886574086695
+ 12670
+
+ (=0xcea6f66e e741e7b3 ee50acd4 bd6eacbf 821fab72 bf5fe85b
+ 8f614af9 04aff677 15e820b9 e4bcc159 f67a97f3 2c176d2c d9b7cdeb
+ f753f3de).
+
+ Y2 63661899992109030051219177516378471383513217472497460517936503629
+ 79522840238080543318627428149249774773108009447466292682661818280
+ 41265
+ (=0xe0394408 ed2b4efb b6b6ac7e bc815516 fdf31a6e d32db3f9
+ 54cd8ac1 c7ddf0cc e7507688 a70f219a 57eef863 49003560 66747ca3
+ 00105a31).
+
+ The representation of k and the compressed representations of Pw3 and
+ k*Pw3 in tight MSB/msborder are given by
+
+ repr(k) =0xdcb3bbb9 e42d7aca fe62052d 902123c7 0872b984 4c1e199f
+ 7c5d37bd 1171102b c20a6352 d9c91886 29b685de 51441e84
+ 3afe2665 5251aa80;
+
+ repr(Pw3) =0x80 be9f5a23 51709e13 d5ad50c2 a27be8ee 1b051970
+ 2580d5c3 c2de7f75 3010635e d89ef547 8b67dc54 16d63c5b
+ 1cc1116f dd453515 71b39b48;
+
+ repr(k*Pw3) =0x00 069fdd7c 2ec1ecbf d3cd0e27 1e8110c6 d2e478f2
+ aa393928 64a5511e da0b8dc7 3834fd57 b5ef8527 361a8176
+ c6da44ee 63701c0c f49d7d13,
+
+ where the leftmost bit of the leftmost octet indicates the parity of
+ the Ycoordinate of the point of Wei448.3 in question (which, in
+ this case, are one and zero, respectively, since Y is odd and Y1 is
+ even). See Appendix H.1 and Appendix I for further detail on
+ (squeezed) point compression.
+
+ A randomized representation (t1, t2) of the point k*Pw3 in tight MSB/
+ msb order is given by
+
+ t1 450833060883286904091316612794941178576639837300736625958
+ 696097131313213727115363096930063001237631586932727905179
+ 306828042642854311987
+
+ (=0x9ec9ba07 3fb2bb5e 9dbee995 067ce094 63601ecd 325f0930
+ aea79cb8 745fa71d 4caa37ee f04fab67 ab2de747 4ac0a025
+ 830f4828 429cf833)
+
+ t2 339205723274519707955026734148022275762579914421865223818
+ 363622725164496136165251928391223173879522521195772276587
+ 373445978123589677750
+
+ (=0x7778c1f9 9d900633 d161d7ea a963ddad e9101d3f f4f04710
+ 623d2a51 6ca10133 3db9ccc3 86df9271 fbb72740 77f79dd1
+ 9aed0bfb e3bc72b6),
+
+ where this representation is defined in Appendix K.5 and uses the
+ mapping of Appendix K.3.1 with the default square root function.
+
+O.5. Example with Edwards448
+
+ Pe1=(x, y), k*Pe1=(x1, y1), and (k+1)*Pe1=(x2, y2) with Edwards448:
+
+ x 70320395893028961673046639985409870226249442701760956079298956688
+ 26896600999421897751877804946848997852325361659665744287620719558
+ 67733
+
+ (=0xf7acf3ca b79b29c2 aa44863d 9edaeca4 8c90ad84 e460df42
+ 7dd9ab59 1bd8a844 07cb3419 59309b33 1e22bfa1 a2d37e10 e2e42a1f
+ 170f0855).
+
+ y 70628706854857281648863291487942166052137991441320055237644304464
+ 58787938273165391464653528929699350754224243613996187734424074211
+ 98773
+
+ (=0xf8c2f181 3bceee8e 085ecd70 d1b6aa4c ea9b95bd 8f36ab44
+ c79e9124 1ea625b7 f9f5ec57 89cc5af2 a2eb255a b252b874 509dc0d9
+ 685841b5).
+
+ x1 38125875041649701211705790554244713713134918749445854542272999596
+ 74058986304488795258334978838809456257721496105769894880185657328
+ 40277
+
+ (=0x864880b9 e1900c68 ba4a545a 6fe2b161 62dcc3b9 fa218e4b
+ feba9828 5cee5193 f2c989f6 c3b94eb6 2914dce7 b4818e4d 8fc8d51f
+ 05a13355).
+
+ y1 11060653846610182753991162627427631707898421166839907726978369444
+ 53337541552746428662176632660036639406375548888849623833963458813
+ 1154
+
+ (=0x03e54af3 7f4cf5e6 5f1e2acd 5c4a4554 76adc652 b198ab2a
+ 719e5aa9 ee749871 0193da82 ab6d000b f55836b1 0615653f 69514297
+ f4459f52).
+
+ x2 15620503788413497044804517304021524439062374489822547728508337937
+ 50606335270276724725939683726318058744384611584731365019896485812
+ 8760
+
+ (=0x05806f71 95e85352 ef3960ac 1ff9cf6c 3c99e0ee 2e75edfc
+ a133cafc 4a4b5fbf e4339859 c5fa123b 70ad2faf 7584ab9d 264540e7
+ 7d560978).
+
+ y2 40019917514121727463122190125689377890703570698337158159153510836
+ 68442386516751945577468473801561261386285902585868517988506010293
+ 44096
+ (=0x8cf44811 3cec6e07 d1bbe9f5 4062075c 6fec0ac5 31272dce
+ 1f446aeb d895373d e312c18d 6a345755 2861e014 0cc23158 a46ace4c
+ 9ca21b60).
+
+ The representation of k and the compressed representations of Pe1 and
+ k*Pe1 in tight LSB/lsborder are given by
+
+ repr(k) =0x01558a4a a6647f5c 2178228a 7ba16d94 6118939b 4ac65043
+ d4088e88 bdecba3e f9987832 219d4e10 e3c48409 b4a0467f
+ 535eb427 9dddcd3b;
+
+ repr(Pe1) =0xad821a16 9b03b90a 2e1d4a4d 5aa4d745 4f5a3391 ea37af9f
+ eda46578 248979e3 22d56cf1 bda9d957 32556d8b 0eb37a10
+ 717773dc 818f431f 01;
+
+ repr(k*Pe1) =0x4af9a22f e9428a96 fca6a860 8d6c1aaf d000b6d5 415bc980
+ 8e192e77 955a798e 54d5198d 4a63b56e 2aa2523a b35478fa
+ 67af32fe cf52a7c0 01,
+
+ where the rightmost bit of the rightmost octet indicates the parity
+ of the xcoordinate of the point of Edwards448 in question (which, in
+ this case, are both one, since x and x1 are odd). See Appendix H.3
+ and Appendix I 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 [RFC7748], [RFC8032]
+ requires unique representations of all elements of GF(p).
+
+ A randomized representation (t1, t2) of the point k*Pe1 in tight LSB/
+ lsb order is given by
+
+ t1 125390048858887400104074787879402833851854739339836093733
+ 734638776755983021034212058415891288350265701101219981698
+ 849086128138510420407
+
+ (=0xed921f3d 6ea4e452 dd06e783 782cbeb3 c5847a79 d9e6b993
+ bd387cf5 feeddafe af8c038d f2732362 92724d37 273eedfc
+ f2ab2499 98a79434)
+
+ t2 365268494484253132875102676783560666625109899133767696106
+ 602723958322248430160651314075127005631031993354968950936
+ 71875730862008188281
+
+ (=0x9ebc28c0 86176a1a c7f0cf71 ca5f2a8f 908bb27b e85c0bbd
+ 1641c052 e542f7d3 88e18886 5afdca32 8df45408 8b6da28c
+ 0bc09d83 309ebb30),
+
+ where this representation is defined in Appendix K.5 and uses the
+ mapping of Appendix K.3.3 with the default square root function and
+ underlying 4isogenous mapping between Edwards448 and Curve448 of
+ Appendix N.2.
+
Author's Address
Rene Struik
Struik Security Consultancy
Email: rstruik.ext@gmail.com