draft-ietf-lwig-curve-representations-08.txt   draft-ietf-lwig-curve-representations-09.txt 
lwig R. Struik lwig R. Struik
Internet-Draft Struik Security Consultancy Internet-Draft Struik Security Consultancy
Intended status: Informational July 24, 2019 Intended status: Informational March 9, 2020
Expires: January 25, 2020 Expires: September 10, 2020
Alternative Elliptic Curve Representations Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-08 draft-ietf-lwig-curve-representations-09
Abstract Abstract
This document specifies how to represent Montgomery curves and This document specifies how to represent Montgomery curves and
(twisted) Edwards curves as curves in short-Weierstrass form and (twisted) Edwards curves as curves in short-Weierstrass form and
illustrates how this can be used to carry out elliptic curve illustrates how this can be used to carry out elliptic curve
computations using existing implementations of, e.g., ECDSA and ECDH computations using existing implementations of, e.g., ECDSA and ECDH
using NIST prime curves. using NIST prime curves. We also provide extensive background
material that may be useful for implementers of elliptic curve
cryptography.
Requirements Language Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in RFC "OPTIONAL" in this document are to be interpreted as described in BCP
2119 [RFC2119]. 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on January 25, 2020. This Internet-Draft will expire on September 10, 2020.
Copyright Notice 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. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 4 1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 5
2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 4 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 5
3. Use of Representation Switches . . . . . . . . . . . . . . . 5 3. Use of Representation Switches . . . . . . . . . . . . . . . 5
4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 6 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 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.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 7
4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 7 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 8
5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
6. Implementation Considerations . . . . . . . . . . . . . . . . 9 5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 9
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 10 5.2. Representation Conventions . . . . . . . . . . . . . . . 9
8. Security Considerations . . . . . . . . . . . . . . . . . . . 11 5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 9
9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 12 6. Implementation Considerations . . . . . . . . . . . . . . . . 10
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 11
10.1. COSE Elliptic Curves Registration . . . . . . . . . . . 12 8. Security Considerations . . . . . . . . . . . . . . . . . . . 12
10.2. COSE Algorithms Registration (1/2) . . . . . . . . . . . 12 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 13
10.3. COSE Algorithms Registration (2/2) . . . . . . . . . . . 13 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13
10.4. JOSE Elliptic Curves Registration . . . . . . . . . . . 13 10.1. IANA Considerations for Wei25519 . . . . . . . . . . . . 13
10.5. JOSE Algorithms Registration (1/2) . . . . . . . . . . . 13 10.1.1. COSE Elliptic Curves Registration . . . . . . . . . 14
10.6. JOSE Algorithms Registration (2/2) . . . . . . . . . . . 14 10.1.2. COSE Algorithms Registration (1/2) . . . . . . . . . 14
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14 10.1.3. COSE Algorithms Registration (2/2) . . . . . . . . . 14
12. References . . . . . . . . . . . . . . . . . . . . . . . . . 14 10.1.4. JOSE Elliptic Curves Registration . . . . . . . . . 15
12.1. Normative References . . . . . . . . . . . . . . . . . . 14 10.1.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 15
12.2. Informative References . . . . . . . . . . . . . . . . . 16 10.1.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 16
Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 17 10.2. IANA Considerations for Wei448 . . . . . . . . . . . . . 16
A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 17 10.2.1. COSE Elliptic Curves Registration . . . . . . . . . 16
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 18 10.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 17
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 18 10.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 17
Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 18 10.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 17
B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 18 10.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 18
B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 20 10.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 18
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
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 (Non-Binary) Elliptic Curves . . . . . . . . . 22
A.1. Curves in Short-Weierstrass 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 D.3. Mapping between Twisted Edwards Curves and Weierstrass
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 25 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 31
Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 25 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 31
E.1. Curve Definition and Alternative Representations . . . . 25 E.1. Curve Definition and Alternative Representations . . . . 31
E.2. Switching between Alternative Representations . . . . . . 26 E.2. Switching between Alternative Representations . . . . . . 31
E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 27 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 33
Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 29 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 35
F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 30 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 35
F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 30 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 36
F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 31 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 36
F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 32 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 37
Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 33 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 39
G.1. Further Alternative Representations . . . . . . . . . . . 33 G.1. Further Alternative Representations . . . . . . . . . . . 39
G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 33 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 39
G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 34 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 40
Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 36 G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 41
H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 36 G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 42
H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 36 G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 48
H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 38 Appendix H. Point Compression . . . . . . . . . . . . . . . . . 54
H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 41 H.1. Point Compression for Weierstrass Curves . . . . . . . . 54
H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 42 H.2. Point Compression for Montgomery Curves . . . . . . . . . 55
H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 42 H.3. Point Compression for Twisted Edwards Curves . . . . . . 56
H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 44 Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 57
H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 47 I.1. Conversion between Bit Strings and Integers (BS2I, I2BS) 57
Appendix I. Point Compression . . . . . . . . . . . . . . . . . 48 I.2. Conversion between Octet Strings and Integers (OS2I,
I.1. Point Compression for Weierstrass Curves . . . . . . . . 49 I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 58
I.2. Point Compression for Montgomery Curves . . . . . . . . . 49 I.3. Conversion between Octet Strings and Bit Strings (OS2BS,
I.3. Point Compression for Twisted Edwards Curves . . . . . . 50 BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 58
Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 51 I.4. Conversion between Field Elements and Octet Strings
J.1. Conversion between Bit Strings and Integers . . . . . . . 52 (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 58
J.2. Conversion between Octet Strings and Integers (OS2I, I.5. Conversion between Elements of Z mod n and Octet Strings
I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 52 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 59
J.3. Conversion between Octet Strings and Bit Strings (BS2OS, I.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 59
OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 52 Appendix J. Representation Examples Curve25519 Family Members . 61
J.4. Conversion between Field Elements and Octet Strings J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 61
(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 53 J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 63
J.5. Conversion between Elements of Z mod n and Octet Strings J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 65
(ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 53 J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 67
J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 54 J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 68
Appendix K. Representation Examples Curve25519 Family Members . 55 Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 70
K.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 55 K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 70
K.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 57 K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 70
K.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 59 K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 70
K.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 61 K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 71
K.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 63 K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 71
Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 64 K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 71
L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 64 K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 72
L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 64 K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 74
L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 64 K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 74
L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 65 K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 74
L.3. Mapping to Curve Points . . . . . . . . . . . . . . . . . 65 K.4.2. Mapping to High-Order Points of Montgomery Curve . . 75
L.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 65 K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 76
L.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 66 K.5. Randomized Representation of Curve Points . . . . . . . . 77
L.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 68 Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 78
L.4. Randomized Representation of Curve Points . . . . . . . . 68 L.1. Curve Definition and Alternative Representation . . . . . 78
Appendix M. Curve secp256k1 and Friend . . . . . . . . . . . . . 68 L.2. Switching Between Representations . . . . . . . . . . . . 79
M.1. Curve Definition and Alternative Representation . . . . . 68 L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 79
M.2. Switching Between Representations . . . . . . . . . . . . 69 L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 81
M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 69 L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 81
M.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 71 L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 81
M.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 71 Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 82
M.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 72 M.1. Curve Definition and Alternative Representations . . . . 82
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 72 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 1. Fostering Code Reuse with New Elliptic Curves
It is well-known that elliptic curves can be represented using Elliptic curves can be represented using different curve models.
different curve models. Recently, IETF standardized elliptic curves Recently, IETF standardized elliptic curves that are claimed to have
that are claimed to have better performance and improved robustness better performance and improved robustness against "real world"
against "real world" attacks than curves represented in the attacks than curves represented in the traditional "short"
traditional "short" Weierstrass model. This document specifies an Weierstrass model. This document specifies an alternative
alternative representation of points of Curve25519, a so-called representation of points of Curve25519, a so-called Montgomery curve,
Montgomery curve, and of points of Edwards25519, a so-called twisted and of points of Edwards25519, a so-called twisted Edwards curve,
Edwards curve, which are both specified in [RFC7748], as points of a which are both specified in [RFC7748], as points of a specific so-
specific so-called "short" Weierstrass curve, called Wei25519. We called "short" Weierstrass curve, called Wei25519. We also define
also define how to efficiently switch between these different how to efficiently switch between these different representations.
representations.
Use of Wei25519 allows easy definition of new signature schemes and Use of Wei25519 allows easy definition of new instantiations of
key agreement schemes already specified for traditional NIST prime signature schemes and key agreement schemes already specified for
curves, thereby allowing easy integration with existing traditional NIST prime curves, thereby allowing easy integration with
specifications, such as NIST SP 800-56a [SP-800-56a], FIPS Pub 186-4 existing specifications, such as NIST SP 800-56a [SP-800-56a], FIPS
[FIPS-186-4], and ANSI X9.62-2005 [ANSI-X9.62], and fostering code Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005 [ANSI-X9.62], and
reuse on platforms that already implement some of these schemes using fostering code reuse on platforms that already implement some of
elliptic curve arithmetic for curves in "short" Weierstrass form (see these schemes using elliptic curve arithmetic for curves in "short"
Appendix C.1). Weierstrass form (see Appendix C.1).
2. Specification of Wei25519 2. Specification of Wei25519
For the specification of Wei25519 and its relationship to Curve25519 For the specification of Wei25519 and its relationship to Curve25519
and Edwards25519, see Appendix E. For further details and background and Edwards25519, see Appendix E. For further details and background
information on elliptic curves, we refer to the other appendices. information on elliptic curves, we refer to the other appendices.
The use of Wei25519 allows reuse of existing generic code that The use of Wei25519 allows reuse of existing generic code that
implements short-Weierstrass curves, such as the NIST curve P-256, to implements short-Weierstrass curves, such as the NIST curve P-256, to
also implement the CFRG curves Curve25519 and Edwards25519. We also also implement the CFRG curves Curve25519 and Edwards25519. (Here,
cater to reusing of existing code where some domain parameters may generic code refers to an implementation that does not depend on
have been hardcoded, thereby widening the scope of applicability. To hardcoded domain parameters (see also Section 6).) We also cater to
this end, we specify the short-Weierstrass curves Wei25519.2 and reusing of existing code where some domain parameters may have been
Wei25519.-3, with hardcoded domain parameter a=2 and a=-3 (mod p), hardcoded, thereby widening the scope of applicability. To this end,
respectively; see Appendix G. (Here, p is the characteristic of the we specify the short-Weierstrass curves Wei25519.2 and Wei25519.-3,
field over which these curves are defined.) 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 3. Use of Representation Switches
The curves Curve25519, Edwards25519, and Wei25519, as specified in The curves Curve25519, Edwards25519, and Wei25519, as specified in
Appendix E.3, are all isomorphic, with the transformations of Appendix E.3, are all isomorphic, with the transformations of
Appendix E.2. These transformations map the specified base point of Appendix E.2. These transformations map the specified base point of
each of these curves to the specified base point of each of the other each of these curves to the specified base point of each of the other
curves. Consequently, a public-private key pair (k,R:=k*G) for any curves. Consequently, a public-private key pair (k,R:=k*G) for any
one of these curves corresponds, via these isomorphic mappings, to one of these curves corresponds, via these isomorphic mappings, to
the public-private key pair (k, R':=k*G') for each of these other the public-private key pair (k, R':=k*G') for each of these other
skipping to change at page 6, line 6 skipping to change at page 6, line 39
Alternative curve representations can, therefore, be used in any Alternative curve representations can, therefore, be used in any
cryptographic scheme that involves computations on public-private key cryptographic scheme that involves computations on public-private key
pairs, where implementations may carry out computations on the pairs, where implementations may carry out computations on the
corresponding object for the isomorphic or isogenous curve and corresponding object for the isomorphic or isogenous curve and
convert the results back to the original curve (where, in case this convert the results back to the original curve (where, in case this
involves an l-isogeny, one has to take into account the factor l). involves an l-isogeny, one has to take into account the factor l).
This includes use with elliptic-curve based signature schemes and key This includes use with elliptic-curve based signature schemes and key
agreement and key transport schemes. agreement and key transport schemes.
For some examples of curve computations on each of the curves 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. Examples
4.1. Implementation of X25519 4.1. Implementation of X25519
RFC 7748 [RFC7748] specifies the use of X25519, a co-factor Diffie- RFC 7748 [RFC7748] specifies the use of X25519, a co-factor Diffie-
Hellman key agreement scheme, with instantiation by the Montgomery Hellman key agreement scheme, with instantiation by the Montgomery
curve Curve25519. This key agreement scheme was already specified in curve Curve25519. This key agreement scheme was already specified in
Section 6.1.2.2 of NIST SP 800-56a [SP-800-56a] for elliptic curves Section 6.1.2.2 of NIST SP 800-56a [SP-800-56a] for elliptic curves
in short Weierstrass form. Hence, one can implement X25519 using in short Weierstrass form. Hence, one can implement X25519 using
existing NIST routines by (1) representing a point of the Montgomery existing NIST routines by (1) representing a point of the Montgomery
curve Curve25519 as a point of the Weierstrass curve Wei25519; (2) curve Curve25519 as a point of the Weierstrass curve Wei25519; (2)
instantiating the co-factor Diffie-Hellman key agreement scheme of instantiating the co-factor Diffie-Hellman key agreement scheme of
the NIST specification with the resulting point and Wei25519 domain the NIST specification with the resulting point and Wei25519 domain
parameters; (3) representing the key resulting from this scheme parameters; (3) representing the key resulting from this scheme
(which is a point of the curve Wei25519 in Weierstrass form) as a (which is a point of the curve Wei25519 in Weierstrass form) as a
point of the Montgomery curve Curve25519. The representation change point of the Montgomery curve Curve25519. The representation change
can be implemented via a simple wrapper and involves a single modular can be implemented via a simple wrapper and involves a single modular
addition (see Appendix D.2). Using this method has the additional addition (see Appendix E.2). Using this method has the additional
advantage that one can reuse the public-private key pair routines, advantage that one can reuse the public-private key pair routines,
domain parameter validation, and other checks that are already part domain parameter validation, and other checks that are already part
of the NIST specifications. A NIST-compliant version of co-factor of the NIST specifications. A NIST-compliant version of co-factor
Diffie-Hellman key agreement (denoted by ECDH25519) results if one Diffie-Hellman key agreement (denoted by ECDH25519) results if one
keeps inputs (key contributions) and outputs (shared key) in the keeps inputs (key contributions) and outputs (shared key) in the
short-Weierstrass format (and, hence, does not perform Step (3) short-Weierstrass format (and, hence, does not perform Step (3)
above). above).
NOTE: At this point, it is unclear whether this implies that a FIPS- NOTE: At this point, it is unclear whether this implies that a FIPS-
accredited module implementing co-factor Diffie-Hellman for, e.g., accredited module implementing co-factor Diffie-Hellman for, e.g.,
skipping to change at page 7, line 4 skipping to change at page 7, line 38
Ed25519 using an existing Montgomery curve implementation by (1) Ed25519 using an existing Montgomery curve implementation by (1)
generating a public-private key pair (k, R':=k*G') for Curve25519; generating a public-private key pair (k, R':=k*G') for Curve25519;
(2) representing this public-private key as the pair (k, R:=k*G) for (2) representing this public-private key as the pair (k, R:=k*G) for
Ed25519. As before, the representation change can be implemented via Ed25519. As before, the representation change can be implemented via
a simple wrapper. Note that the Montgomery ladder specified in a simple wrapper. Note that the Montgomery ladder specified in
Section 5 of RFC7748 [RFC7748] does not provide sufficient Section 5 of RFC7748 [RFC7748] does not provide sufficient
information to reconstruct R':=(u, v) (since it does not compute the information to reconstruct R':=(u, v) (since it does not compute the
v-coordinate of R'). However, this deficiency can be remedied by v-coordinate of R'). However, this deficiency can be remedied by
using a slightly modified version of the Montgomery ladder that using a slightly modified version of the Montgomery ladder that
includes reconstruction of the v-coordinate of R':=k*G' at the end of includes reconstruction of the v-coordinate of R':=k*G' at the end of
hereof (which uses the v-coordinate of the base point of Curve25519 the Montgomery ladder (which uses the v-coordinate of the base point
as well). For details, see Appendix C.1. of Curve25519 as well). For details, see Appendix C.1.
4.3. Specification of ECDSA25519 4.3. Specification of ECDSA25519
FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and
can be instantiated not just with the NIST prime curves, but also can be instantiated not just with the NIST prime curves, but also
with other Weierstrass curves (that satisfy additional cryptographic with other Weierstrass curves (that satisfy additional cryptographic
criteria). In particular, one can instantiate this scheme with the criteria). In particular, one can instantiate this scheme with the
Weierstrass curve Wei25519 and the hash function SHA-256, where an Weierstrass curve Wei25519 and the hash function SHA-256
implementation may generate an ephemeral public-private key pair for [FIPS-180-4], where an implementation may generate an ephemeral
Wei25519 by (1) internally carrying out these computations on the public-private key pair for Wei25519 by (1) internally carrying out
Montgomery curve Curve25519, the twisted Edwards curve Edwards25519, these computations on the Montgomery curve Curve25519, the twisted
or even the Weierstrass curve Wei25519.-3 (with hardcoded a=-3 domain Edwards curve Edwards25519, or even the Weierstrass curve Wei25519.-3
parameter); (2) representing the result as a key pair for the curve (with hardcoded a=-3 domain parameter); (2) representing the result
Wei25519. Note that, in either case, one can implement these schemes as a key pair for the curve Wei25519. Note that, in either case, one
with the same representation conventions as used with existing NIST can implement these schemes with the same representation conventions
specifications, including bit/byte-ordering, compression functions, as used with existing NIST specifications, including bit/byte-
and the-like. This allows generic implementations of ECDSA with the ordering, compression functions, and the-like. This allows generic
hash function SHA-256 and with the NIST curve P-256 or with the curve implementations of ECDSA with the hash function SHA-256 and with the
Wei25519 specified in this specification to reuse the same NIST curve P-256 or with the curve Wei25519 specified in this
implementation (instantiated with, respectively, the NIST P-256 specification to reuse the same implementation (instantiated with,
elliptic curve domain parameters or with the domain parameters of respectively, the NIST P-256 elliptic curve domain parameters or with
curve Wei25519 specified in Appendix E). the domain parameters of curve Wei25519 specified in Appendix E). We
denote by ECDSA25519 the instantiation of ECDSA with SHA-256 and with
curve Wei25519, where the signature (r,s) is represented as the
right-concatenation of the integers r and s, each represented as
fixed-size strings with tight MSB/msb ordering (see Appendix I).
4.4. Other Uses 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others)
Any existing specification of cryptographic schemes using elliptic Any existing specification of cryptographic schemes using elliptic
curves in Weierstrass form and that allows introduction of a new curves in Weierstrass form and that allows introduction of a new
elliptic curve (here: Wei25519) is amenable to similar constructs, elliptic curve (here: Wei25519) is amenable to similar constructs,
thus spawning "offspring" protocols, simply by instantiating these thus spawning "offspring" protocols, simply by instantiating these
using the new curve in "short" Weierstrass form, thereby allowing using the new curve in "short" Weierstrass form, thereby allowing
code and/or specifications reuse and, for implementations that so code and/or specifications reuse and, for implementations that so
desire, carrying out curve computations "under the hood" on desire, carrying out curve computations "under the hood" on
Montgomery curve and twisted Edwards curve cousins hereof (where Montgomery curve and twisted Edwards curve cousins hereof (where
these exist). This would simply require definition of a new object these exist). This would simply require definition of a new object
identifier for any such envisioned "offspring" protocol. This could identifier for any such envisioned "offspring" protocol. This could
significantly simplify standardization of schemes and help keeping significantly simplify standardization of schemes and help keeping
the resource and maintenance cost of implementations supporting the resource and maintenance cost of implementations supporting
algorithm agility [RFC7696] at bay. algorithm agility [RFC7696] at bay.
We illustrate the construction of such offspring protocols for
Curve448, another Montgomery curve recently standardized by IETF (see
[RFC7748]). Similar to the case with Curve25519, one can represent
points of this curve via different curve models, viz. as points of an
Edwards curve (Ed448) or as points of a short-Weierstrass curve
(Wei448). For the specification of Wei448 and its relationship to
Curve448 and Ed448, see Appendix M. As with ECDH25519, one can now
easily define a NIST-compliant version of co-factor Diffie-Hellman
key agreement (denoted by ECDH448), by simply reusing the example of
Section 4.1, but now using the short-Weierstrass curve Wei448, rather
than Wei25519. Similarly, one can easily specify ECDSA with Wei448
and a suitable hash function, by simply reusing the example of
Section 4.3, but now using the short-Weierstrass curve Wei448, rather
than Wei25519, and picking as hash function SHAKE256 [FIPS-202] with
output size of d=446 bits. We denote by ECDSA448 the resulting
signature scheme (with the same bit/byte-ordering conventions).
5. Caveats 5. Caveats
The examples above illustrate how specifying the Weierstrass curve The examples above illustrate how specifying the Weierstrass curve
Wei25519 (or any curve in short-Weierstrass format, for that matter) Wei25519 (or any curve in short-Weierstrass format, for that matter)
may facilitate reuse of existing code and may simplify standards may facilitate reuse of existing code and may simplify standards
development. However, the following caveats apply: development. However, the following caveats apply:
1. Wire format. The transformations between alternative curve 5.1. Wire Format
representations can be implemented at negligible relative
incremental cost if the curve points are represented as affine
points. If a point is represented in compressed format,
conversion usually requires a costly point decompression step.
This is the case in [RFC7748], where the inputs to the co-factor
Diffie-Hellman scheme X25519, as well as its output, are
represented in u-coordinate-only format. This is also the case
in [RFC8032], where the EdDSA signature includes the ephemeral
signing key represented in compressed format (see Appendix I for
details);
2. Representation conventions. While elliptic curve computations The transformations between alternative curve representations can be
are carried-out in a field GF(q) and, thereby, involve large implemented at negligible relative incremental cost if the curve
integer arithmetic, these integers are represented as bit- and points are represented as affine points. If a point is represented
byte-strings. Here, [RFC8032] uses least-significant-byte in compressed format, conversion usually requires a costly point
(LSB)/least-significant-bit (lsb) conventions, whereas [RFC7748] decompression step. This is the case in [RFC7748], where the inputs
uses LSB/most-significant-bit (msb) conventions, and where most to the co-factor Diffie-Hellman scheme X25519, as well as its output,
other cryptographic specifications, including NIST SP800-56a are represented in u-coordinate-only format. This is also the case
[SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005 in [RFC8032], where the EdDSA signature includes the ephemeral
[ANSI-X9.62] use MSB/msb conventions. Since each pair of signing key represented in compressed format (see Appendix H for
conventions is different (see Appendix J for details and details). Note that in the latter case compression is lossless,
Appendix K for examples), this does necessitate bit/byte whereas it is lossy in the former case;
representation conversions;
3. Domain parameters. All traditional NIST curves are Weierstrass 5.2. Representation Conventions
curves with domain parameter a=-3, while all Brainpool curves
[RFC5639] are isomorphic to a Weierstrass curve of this form.
Thus, one can expect there to be existing Weierstrass
implementations with a hardcoded a=-3 domain parameter
("Jacobian-friendly"). For those implementations, including the
curve Wei25519 as a potential vehicle for offering support for
the CFRG curves Curve25519 and Edwards25519 is not possible,
since not of the required form. Instead, one has to implement
Wei25519.-3 and include code that implements the isogeny and dual
isogeny from and to Wei25519. This isogeny has degree l=47 and
requires roughly 9kB of storage for isogeny and dual-isogeny
computations (see the tables in Appendix H). Note that storage
would have reduced to a single 64-byte table if only the curve
would have 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 While elliptic curve computations are carried-out in a field GF(q)
field as Curve25519 that is isomorphic to a Weierstrass curve and, thereby, involve large integer arithmetic, these integers are
with hardcoded a=-3 parameter is the Montgomery curve M_{A,B} represented as bit- and byte-strings. Here, [RFC8032] uses least-
with B=1 and A=-1410290 (or, if one wants the base point to still significant-byte (LSB)/least-significant-bit (lsb) conventions,
have u-coordinate u=9, with B=1 and A=-3960846). In either case, whereas [RFC7748] uses LSB/most-significant-bit (msb) conventions,
the resulting curve has the same cryptographic properties as and where most other cryptographic specifications, including NIST
Curve25519 and the same performance (which relies on A being a SP800-56a [SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI
3-byte integer, as is the case with the domain parameter A=486662 X9.62-2005 [ANSI-X9.62] use MSB/msb conventions. Since each pair of
of Curve25519, and using the same special prime p=2^255-19), conventions is different (see Appendix I for details and Appendix J
while at the same time being "Jacobian-friendly" by design. for examples), this does necessitate bit/byte representation
conversions;
NOTE 2: While an implementation of Curve25519 via an isogenous 5.3. Domain Parameters
Weierstrass curve with domain parameter a=-3 requires a
relatively large table (of size roughly 9kB), for the quadratic All traditional NIST curves are Weierstrass curves with domain
twist of Curve25519 (i.e., the Montgomery curve M_{A,B'} with parameter a=-3, while all Brainpool curves [RFC5639] are isomorphic
A=486662 and B'=2) this implementation approach only requires a to a Weierstrass curve of this form. Thus, one can expect there to
table of size less than 0.5kB (over 20x smaller), solely due to be existing Weierstrass implementations with a hardcoded a=-3 domain
the fact that it is l-isogenous to a Weierstrass curve with a=-3 parameter ("Jacobian-friendly"). For those implementations,
parameter with relatively small parameter l=2 (compared to l=47, including the curve Wei25519 as a potential vehicle for offering
as is the case with Curve25519 itself). support for the CFRG curves Curve25519 and Edwards25519 is not
possible, since not of the required form. Instead, one has to
implement Wei25519.-3 and include code that implements the isogeny
and dual isogeny from and to Wei25519. The lowest odd-degree isogeny
has degree l=47 and requires roughly 9kB of storage for isogeny and
dual-isogeny computations (see the tables in Appendix G.4). Note
that storage would have reduced to a single 64-byte table if only the
curve would have been generated so as to be isomorphic to a
Weierstrass curve with hardcoded a=-3 parameter (this corresponds to
l=1).
NOTE 1: An example of a Montgomery curve defined over the same field
as Curve25519 that is isomorphic to a Weierstrass curve with
hardcoded a=-3 parameter is the Montgomery curve M_{A,B} with B=1 and
A=-1410290 (or, if one wants the base point to still have
u-coordinate u=9, with B=1 and A=-3960846). In either case, the
resulting curve has the same cryptographic properties as Curve25519
and the same performance (which relies on A being a 3-byte integer,
as is the case with the domain parameter A=486662 of Curve25519, and
using the same special prime p=2^255-19), while at the same time
being "Jacobian-friendly" by design.
NOTE 2: While an implementation of Curve25519 via an isogenous
Weierstrass curve with domain parameter a=-3 requires a relatively
large table (of size roughly 9kB), for the quadratic twist of
Curve25519 (i.e., the Montgomery curve M_{A,B'} with A=486662 and
B'=2) this implementation approach only requires a table of size less
than 0.5kB (over 20x smaller), solely due to the fact that it is
l-isogenous to a Weierstrass curve with a=-3 parameter with
relatively small parameter l=2 (compared to l=47, as is the case with
Curve25519 itself).
6. Implementation Considerations 6. Implementation Considerations
The efficiency of elliptic curve arithmetic is primarily determined The efficiency of elliptic curve arithmetic is primarily determined
by the efficiency of its group operations (see Appendix C). Numerous by the efficiency of its group operations (see Appendix C). Numerous
optimized formulae exist, such as the use of so-called Montgomery optimized formulae exist, such as the use of so-called Montgomery
ladders with Montgomery curves [Mont-Ladder] or with Weierstrass ladders with Montgomery curves [Mont-Ladder] or with Weierstrass
curves [Wei-Ladder], the use of hardcoded a=-3 domain parameter for curves [Wei-Ladder], the use of hardcoded a=-3 domain parameter for
Weierstrass curves [ECC-Isogeny], and the use of hardcoded a=-1 Weierstrass curves [ECC-Isogeny], and the use of hardcoded a=-1
domain parameters for twisted Edwards curves [tEd-Formulas]. These domain parameters for twisted Edwards curves [tEd-Formulas]. These
skipping to change at page 9, line 44 skipping to change at page 11, line 8
Depending on the implementation strategy, the bit-size of q may also Depending on the implementation strategy, the bit-size of q may also
facilitate reduced so-called "carry-effects" of integer arithmetic. facilitate reduced so-called "carry-effects" of integer arithmetic.
Most curves use a combination of these design philosophies. All NIST Most curves use a combination of these design philosophies. All NIST
curves [FIPS-186-4] and Brainpool curves [RFC5639] are Weierstrass curves [FIPS-186-4] and Brainpool curves [RFC5639] are Weierstrass
curves with a=-3 domain parameter, thus facilitating more efficient curves with a=-3 domain parameter, thus facilitating more efficient
elliptic curve group operations (via so-called Jacobian coordinates). elliptic curve group operations (via so-called Jacobian coordinates).
The NIST curves and the Montgomery curve Curve25519 are defined over The NIST curves and the Montgomery curve Curve25519 are defined over
prime fields, where the prime number has a special form, whereas the prime fields, where the prime number has a special form, whereas the
Brainpool curves - by design - use a generic prime number. None of 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 or twisted Edwards curves, whereas - conversely -
Montgomery curves and twisted curves can be expressed as Weierstrass Montgomery curves and twisted curves can be expressed as Weierstrass
curves. curves.
While use of Wei25519 allows reuse of existing generic code that While use of Wei25519 allows reuse of existing generic code that
implements short Weierstrass curves, such as the NIST curve P-256, to implements short Weierstrass curves, such as the NIST curve P-256, to
also implement the CFRG curves Curve25519 or Edwards25519, this also implement the CFRG curves Curve25519 or Edwards25519, this
obviously does not result in an implementation of these CFRG curves obviously does not result in an implementation of these CFRG curves
that exploits the specific structure of the underlying field or other that exploits the specific structure of the underlying field or other
specific domain parameters (since generic). Reuse of generic code, specific domain parameters (since generic). Reuse of generic code,
skipping to change at page 12, line 11 skipping to change at page 13, line 21
To prevent intra-protocol cross-instantiation attacks, ephemeral To prevent intra-protocol cross-instantiation attacks, ephemeral
private keys MUST NOT be reused between instantiations of ECDSA25519. private keys MUST NOT be reused between instantiations of ECDSA25519.
9. Privacy Considerations 9. Privacy Considerations
The transformations between different curve models described in this The transformations between different curve models described in this
document are publicly known and, therefore, do not affect privacy document are publicly known and, therefore, do not affect privacy
provisions. provisions.
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 meta-data communicated with this common
data element (e.g., different addressing information), even if an
observer cannot technically verify the binding of this meta-data.
The randomized representation described in Appendix K.5 allows random
curve points to be represented as random pairs of field elements, curve points to be represented as random pairs of field elements,
thereby assisting in obfuscating the presence of these curve points thereby assisting in obfuscating the presence of these curve points
in some applications. in some applications.
10. IANA Considerations 10. IANA Considerations
An object identifier is requested for curve Wei25519 and its use with Code points are requested for curve Wei25519 and Wei448 and its use
ECDSA and co-factor ECDH, using the representation conventions of with ECDSA and co-factor ECDH, using the representation conventions
this document. of this document.
There is *currently* no further IANA action required for this New code points would be required in case one wishes to specify one
document. New object identifiers would be required in case one or more other "offspring" protocols beyond those exemplified in
wishes to specify one or more of the "offspring" protocols Section 4.4. Specification hereof is, however, outside scope of the
exemplified in Section 4.4. 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 This section registers the following value in the IANA "COSE Elliptic
Curves" registry [IANA.COSE.Curves]. Curves" registry [IANA.COSE.Curves].
Name: Wei25519; Name: Wei25519;
Value: TBD (Requested value: -1); Value: TBD (Requested value: -1);
Key Type: EC2 or OKP (where OKP uses the squeezed MSB/msb Key Type: EC2 or OKP (where OKP uses the squeezed MSB/msb
representation of this specification); representation of this specification);
Description: short-Weierstrass curve Wei25519; Description: short-Weierstrass curve Wei25519;
Change Controller: IESG;
Reference: Appendix E.3 of this specification; Reference: Appendix E.3 of this specification;
Recommended: Yes. Recommended: Yes.
(Note that The "kty" value for Wei25519 may be "OKP" or "EC2".) (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 This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms]. Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDSA25519; Name: ECDSA25519;
Value: TBD (Requested value: -1); Value: TBD (Requested value: -1);
Description: ECDSA w/ SHA-256 and curve Wei25519; Description: ECDSA with SHA-256 and curve Wei25519;
Change Controller: IESG;
Reference: Section 4.3 of this specification; Reference: Section 4.3 of this specification;
Recommended: Yes. 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 This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms]. Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDH25519; Name: ECDH25519;
Value: TBD (Requested value: -2); Value: TBD (Requested value: -2);
Description: NIST-compliant co-factor Diffie-Hellman w/ curve Description: NIST-compliant co-factor Diffie-Hellman w/ curve
Wei25519 and key derivation function HKDF SHA256; Wei25519 and key derivation function HKDF SHA256;
Change Controller: IESG;
Reference: Section 4.1 of this specification (for key derivation, Reference: Section 4.1 of this specification (for key derivation,
see Section 11.1 of [RFC8152]); see Section 11.1 of [RFC8152]);
Recommended: Yes. 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 This section registers the following value in the IANA "JSON Web Key
Elliptic Curve" registry [IANA.JOSE.Curves]. Elliptic Curve" registry [IANA.JOSE.Curves].
Curve Name: Wei25519; Curve Name: Wei25519;
Curve Description: short-Weierstrass curve Wei25519; Curve Description: short-Weierstrass curve Wei25519;
JOSE Implementation Requirements: optional; JOSE Implementation Requirements: Optional;
Change Controller: IANA; Change Controller: IESG;
Reference: Appendix E.3 of this specification. 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 This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDSA25519; Algorithm Name: ECDSA25519;
Algorithm Description: ECDSA w/ SHA-256 and curve Wei25519; Algorithm Description: ECDSA using SHA-256 and curve Wei25519;
Algorithm Usage Locations: alg; 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; 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 This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDH25519; Algorithm Name: ECDH25519;
Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/ Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/
curve Wei25519 and key derivation function HKDF SHA256; curve Wei25519 and key derivation function HKDF SHA256;
Algorithm Usage Locations: alg; Algorithm Usage Locations: alg;
Change Controller: IANA; JOSE Implementation Requirements: Optional;
Change Controller: IESG;
Reference: Section 4.1 of this specification (for key derivation, Reference: Section 4.1 of this specification (for key derivation,
see Section 5 of [SP-800-56c]); see Section 5 of [SP-800-56c]);
Algorithm Analysis Documents: Section 4.1 of this specification (for Algorithm Analysis Document(s): Section 4.1 of this specification
key derivation, see Section 5 of [SP-800-56c]). (for key derivation, see Section 5 of [SP-800-56c]).
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: short-Weierstrass 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: NIST-compliant co-factor Diffie-Hellman 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: short-Weierstrass 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: NIST-compliant co-factor Diffie-Hellman 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 [SP-800-56c]);
Algorithm Analysis Document(s): Section 4.4 of this specification
(for key derivation, see Section 5 of [SP-800-56c]).
11. Acknowledgements 11. Acknowledgements
Thanks to Nikolas Rosener for discussions surrounding implementation Thanks to Nikolas Rosener for discussions surrounding implementation
details of the techniques described in this document and to Phillip details of the techniques described in this document and to Phillip
Hallam-Baker for triggering inclusion of verbiage on the use of Hallam-Baker for triggering inclusion of verbiage on the use of
Montgomery ladders with recovery of the y-coordinate. Thanks to Montgomery ladders with recovery of the y-coordinate. Thanks to
Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews. Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews.
12. References 12. References
12.1. Normative References 12.1. Normative References
[ANSI-X9.62] [ANSI-X9.62]
ANSI X9.62-2005, "Public Key Cryptography for the ANSI X9.62-2005, "Public Key Cryptography for the
Financial Services Industry: The Elliptic Curve Digital Financial Services Industry: The Elliptic Curve Digital
Signature Algorithm (ECDSA)", American National Standard Signature Algorithm (ECDSA)", American National Standard
for Financial Services, Accredited Standards Committee X9, for Financial Services, Accredited Standards Committee X9,
Inc, Anapolis, MD, 2005. Inc, Anapolis, MD, 2005.
[FIPS-180-4]
FIPS 180-4, "Secure Hash Standard (SHS), Federal
Information Processing Standards Publication 180-4", US
Department of Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, August 2015.
[FIPS-186-4] [FIPS-186-4]
FIPS 186-4, "Digital Signature Standard (DSS), Federal FIPS 186-4, "Digital Signature Standard (DSS), Federal
Information Processing Standards Publication 186-4", US Information Processing Standards Publication 186-4", US
Department of Commerce/National Institute of Standards and Department of Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, July 2013. Technology, Gaithersburg, MD, July 2013.
[FIPS-202]
FIPS 202, "SHA-3 Standard: Permutation-Based Hash and
Extendable-Output Functions, Federal Information
Processing Standards Publication 202", US Department of
Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, August 2015.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography [RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography
(ECC) Brainpool Standard Curves and Curve Generation", (ECC) Brainpool Standard Curves and Curve Generation",
RFC 5639, DOI 10.17487/RFC5639, March 2010, RFC 5639, DOI 10.17487/RFC5639, March 2010,
<https://www.rfc-editor.org/info/rfc5639>. <https://www.rfc-editor.org/info/rfc5639>.
skipping to change at page 15, line 44 skipping to change at page 20, line 23
[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
Signature Algorithm (EdDSA)", RFC 8032, Signature Algorithm (EdDSA)", RFC 8032,
DOI 10.17487/RFC8032, January 2017, DOI 10.17487/RFC8032, January 2017,
<https://www.rfc-editor.org/info/rfc8032>. <https://www.rfc-editor.org/info/rfc8032>.
[RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)", [RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)",
RFC 8152, DOI 10.17487/RFC8152, July 2017, RFC 8152, DOI 10.17487/RFC8152, July 2017,
<https://www.rfc-editor.org/info/rfc8152>. <https://www.rfc-editor.org/info/rfc8152>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0", [SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0",
Standards for Efficient Cryptography, , June 2009. Standards for Efficient Cryptography, , June 2009.
[SEC2] SEC2, "SEC 2: Elliptic Curve Cryptography, Version 2.0", [SEC2] SEC2, "SEC 2: Elliptic Curve Cryptography, Version 2.0",
Standards for Efficient Cryptography, , January 2010. Standards for Efficient Cryptography, , January 2010.
[SP-800-56a] [SP-800-56a]
NIST SP 800-56a, "Recommendation for Pair-Wise Key NIST SP 800-56a, "Recommendation for Pair-Wise Key
Establishment Schemes Using Discrete Log Cryptography, Establishment Schemes Using Discrete Log Cryptography,
Revision 3", US Department of Commerce/National Institute Revision 3", US Department of Commerce/National Institute
skipping to change at page 17, line 44 skipping to change at page 22, line 28
Elliptic Curves of Prime Order as Uniform Random Strings", Elliptic Curves of Prime Order as Uniform Random Strings",
Financial Cryptography 2014, Lecture Notes in Computer Financial Cryptography 2014, Lecture Notes in Computer
Science, Vol. 8437, New York: Springer-Verlag, 2014. Science, Vol. 8437, New York: Springer-Verlag, 2014.
[Wei-Ladder] [Wei-Ladder]
T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve
Multiplication Resistant Against Side Channel Attacks", Multiplication Resistant Against Side Channel Attacks",
Centre for Applied Cryptographic Research, Corr 2002-03, Centre for Applied Cryptographic Research, Corr 2002-03,
2002. 2002.
Appendix A. Some (non-Binary) Elliptic Curves Appendix A. Some (Non-Binary) Elliptic Curves
A.1. Curves in short-Weierstrass Form This section defines the three different curve models we consider,
viz. short-Weierstrass curves, Montgomery curves, and twisted Edwards
curves.
A.1. Curves in Short-Weierstrass Form
Let GF(q) denote the finite field with q elements, where q is an odd Let GF(q) denote the finite field with q elements, where q is an odd
prime power and where q is not divisible by three. Let W_{a,b} be prime power and where q is not divisible by three. Let W_{a,b} be
the Weierstrass curve with defining equation Y^2 = X^3 + a*X + b, the Weierstrass curve with defining equation Y^2 = X^3 + a*X + b,
where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is
nonzero. The points of W_{a,b} are the ordered pairs (X, Y) whose nonzero. The points of W_{a,b} are the ordered pairs (X, Y) whose
coordinates are elements of GF(q) and that satisfy the defining coordinates are elements of GF(q) and that satisfy the defining
equation (the so-called affine points), together with the special equation (the so-called affine points), together with the special
point O (the so-called "point at infinity"). This set forms a group point O (the so-called "point at infinity"). This set forms a group
under addition, via the so-called "secant-and-tangent" rule, where under addition, via the so-called "chord-and-tangent" rule, where the
the point at infinity serves as the identity element. See point at infinity serves as the identity element. See Appendix C.1
Appendix C.1 for details of the group operation. for details of the group operation.
A.2. Montgomery Curves A.2. Montgomery Curves
Let GF(q) denote the finite field with q elements, where q is an odd Let GF(q) denote the finite field with q elements, where q is an odd
prime power. Let M_{A,B} be the Montgomery curve with defining prime power. Let M_{A,B} be the Montgomery curve with defining
equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q) equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q)
and where A is unequal to (+/-)2 and where B is nonzero. The points 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 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- elements of GF(q) and that satisfy the defining equation (the so-
called affine points), together with the special point O (the so- called affine points), together with the special point O (the so-
called "point at infinity"). This set forms a group under addition, called "point at infinity"). This set forms a group under addition,
via the so-called "secant-and-tangent" rule, where the point at via the so-called "chord-and-tangent" rule, where the point at
infinity serves as the identity element. See Appendix C.2 for infinity serves as the identity element. See Appendix C.2 for
details of the group operation. details of the group operation.
A.3. Twisted Edwards Curves A.3. Twisted Edwards Curves
Let GF(q) denote the finite field with q elements, where q is an odd Let GF(q) denote the finite field with q elements, where q is an odd
prime power. Let E_{a,d} be the twisted Edwards curve with defining prime power. Let E_{a,d} be the twisted Edwards curve with defining
equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct
nonzero elements of GF(q). The points of E_{a,d} are the ordered nonzero elements of GF(q). The points of E_{a,d} are the ordered
pairs (x, y) whose coordinates are elements of GF(q) and that satisfy pairs (x, y) whose coordinates are elements of GF(q) and that satisfy
the defining equation (the so-called affine points). It can be shown the defining equation (the so-called affine points). It can be shown
that this set forms a group under addition if a is a square in GF(q), that this set forms a group under addition if a is a square in GF(q),
whereas d is not, where the point O:=(0, 1) serves as the identity whereas d is not, where the point O:=(0, 1) serves as the identity
element. (Note that the identity element satisfies the defining element. (Note that the identity element satisfies the defining
equation.) See Appendix C.3 for details of the group operation. equation.) See Appendix C.3 for details of the group operation.
An Edwards curve is a twisted Edwards curve with a=1. An Edwards curve is a twisted Edwards curve with a=1.
Appendix B. Elliptic Curve Nomenclature and Finite Fields 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 B.1. Elliptic Curve Nomenclature
Each curve defined in Appendix A forms a commutative group under Each curve defined in Appendix A forms a commutative group under
addition (denoted by '+'). In Appendix C we specify the group laws, addition (denoted by '+'). In Appendix C we specify the group laws,
which depend on the curve model in question. For completeness, we which depend on the curve model in question. For completeness, we
here include some common elliptic curve nomenclature and basic here include some common elliptic curve nomenclature and basic
properties (primarily so as to keep this document self-contained). properties (primarily so as to keep this document self-contained).
These notions are mainly used in Appendix E and Appendix G and not These notions are mainly used in Appendix E and Appendix G and not
essential for our exposition. This section can be skipped at first essential for our exposition. This section can be skipped at first
reading. reading.
Any point P of a curve E is a generator of the cyclic subgroup Any point P of a curve E is a generator of the cyclic subgroup
(P):={k*P | k = 0, 1, 2,...} of the curve. (Here, k*P denotes the (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 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. curve; k*P is commonly referred to as scalar multiplication of P by
The order of curve E is the cardinality of the set of its points, 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 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 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 curves of order h*n, where n is a large prime number and where h is a
small number (the so-called co-factor), have a large cyclic subgroup small number (the so-called co-factor), have a large cyclic subgroup
of prime order n. In this case, a generator of order n is called a 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 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 said to be in the small subgroup. For curves of prime order, this
small subgroup is the singleton set, consisting of only the identity 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 element O. A point that is not in the small subgroup is said to be a
least n. high-order point (since it has order at least n).
If R is a point of the curve that is also contained in (P), there is If R is a point of the curve that is also contained in (P), there is
a unique integer k in the interval [0, l-1] so that R=k*P, where l is a unique integer k in the interval [0, l-1] so that R=k*P, where l is
the order of P. This number is called the discrete logarithm of R to the order of P. This number is called the discrete logarithm of R to
the base P. The discrete logarithm problem is the problem of finding the base P. The discrete logarithm problem is the problem of finding
the discrete logarithm of R to the base P for any two points P and R the discrete logarithm of R to the base P for any two points P and R
of the curve, if such a number exists. of the curve, if such a number exists.
If P is a fixed base point G of the curve, the pair (k, R:=k*G) is If P is a fixed base point G of the curve, the pair (k, R:=k*G) is
commonly called a public-private key pair, the integer k the private commonly called a public-private key pair, the integer k the private
key, and the point R the corresponding public key. The private key k key, and the point R the corresponding public key. The private key k
can be represented as an integer in the interval [0,n-1], where G has can be represented as an integer in the interval [0,n-1], 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 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'|, 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 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 specified in this document, a quadratic twist of this curve can be
expressed using the same curve model, although (naturally) with its expressed using the same curve model, although (naturally) with its
own curve parameters. Two curves E and E' defined over a field GF(q) 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 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 be isomorphic if these have the same group structure. Note that
isomorphic curves have necessarily the same order and are, thus, a isomorphic curves have necessarily the same order and are, thus, a
skipping to change at page 20, line 18 skipping to change at page 25, line 15
The group laws in Appendix C are mostly expressed in terms of affine 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 points, but can also be expressed in terms of the representation of
these points in projective coordinates, thereby allowing clearing of these points in projective coordinates, thereby allowing clearing of
denominators. The group laws may also involve non-affine points denominators. The group laws may also involve non-affine points
(such as the point at infinity O of a Weierstrass curve or of a (such as the point at infinity O of a Weierstrass curve or of a
Montgomery curve). Those can also be represented in projective Montgomery curve). Those can also be represented in projective
coordinates. Further details are out of scope. coordinates. Further details are out of scope.
B.2. Finite Fields B.2. Finite Fields
The field GF(q), where q is an odd prime power, is defined as The field GF(q), where q is a prime power, is defined as follows.
follows.
If p is a prime number, the field GF(p) consists of the integers in If q:=p is a prime number, the field GF(p) consists of the integers
the interval [0,p-1] and two binary operations on this set: addition in the interval [0,p-1] and two binary operations on this set:
and multiplication modulo p. 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 If q:=p^m, where p is a prime number and where m>0, the field GF(q)
irreducible polynomial f(z) in z of degree m with coefficients in is defined in terms of an irreducible polynomial f(z) in z of degree
GF(p) (i.e., f(z) cannot be written as the product of two polynomials m with coefficients in GF(p) (i.e., f(z) cannot be written as the
in z of lower degree with coefficients in GF(p)): in this case, GF(q) product of two polynomials in z of lower degree with coefficients in
consists of the polynomials in z of degree smaller than m with GF(p)): in this case, GF(q) consists of the polynomials in z of
coefficients in GF(p) and two binary operations on this set: degree smaller than m with coefficients in GF(p) and two binary
polynomial addition and polynomial multiplication modulo the operations on this set: polynomial addition and polynomial
irreducible polynomial f(z). By definition, each element x of GF(q) multiplication modulo the irreducible polynomial f(z). By
is a polynomial in z of degree smaller than m and can, therefore, be definition, each element x of GF(q) is a polynomial in z of degree
uniquely represented as a vector (x_{m-1}, x_{m-2}, ..., x_1, x_0) of smaller than m and can, therefore, be uniquely represented as a
length m with coefficients in GF(p), where x_i is the coefficient of vector (x_{m-1}, x_{m-2}, ..., x_1, x_0) of length m with
z^i of polynomial x. Note that this representation depends on the 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 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 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 field GF(p) as a subset. If m=1, the definitions of GF(p) and
definitions of GF(p) and GF(p^1) above coincide. If m>1, then GF(q) GF(p^1) above coincide, since each nonzero element of GF(p) can be
is called a (nontrivial) extension field over GF(p). The number p is 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). called the characteristic of GF(q).
A field element y is called a square in GF(q) if it can be expressed A field element y is called a square in GF(q) if it can be expressed
as y:=x^2 for some x in GF(q); it is called a non-square in GF(q) as y:=x^2 for some x in GF(q); it is called a non-square in GF(q)
otherwise. If y is a square in GF(q), we denote by sqrt(y) one of 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 its square roots (the other one being -sqrt(y)). For methods for
computing square roots and inverses in GF(q) - if these exist - see 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 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 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 prime field GF(p), thereby reducing all operations to simple modular
integer arithmetic. Strictly speaking we could, therefore, have integer arithmetic. Strictly speaking we could, therefore, have
refrained from introducing extension fields. Nevertheless, we refrained from introducing extension fields. Nevertheless, we
included the more general exposition, so as to accommodate potential included the more general exposition, so as to accommodate potential
introduction of new curves that are defined over a (nontrivial) introduction of new curves that are defined over a (nontrivial)
extension field at some point in the future. This includes curves extension field at some point in the future. This includes curves
proposed for post-quantum isogeny-based schemes, which are defined proposed for post-quantum isogeny-based schemes, which are defined
over a quadratic extension field (i.e., where q:=p^2), and elliptic over a quadratic extension field (i.e., where q:=p^2), and elliptic
curves used with pairing-based cryptography. The exposition in curves used with pairing-based cryptography. The exposition in
either case is almost the same and now automatically yields, e.g., either case is almost the same and now automatically yields, e.g.,
data conversion routines for any finite field object (see 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. fields as prime fields.
Appendix C. Elliptic Curve Group Operations 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 For each point P of the Weierstrass curve W_{a,b}, the point at
infinity O serves as identity element, i.e., P + O = O + P = P. infinity O serves as identity element, i.e., P + O = O + P = P.
For each affine point P:=(X, Y) of the Weierstrass curve W_{a,b}, the For each affine point P:=(X, Y) of the Weierstrass curve W_{a,b}, the
point -P is the point (X, -Y) and one has P + (-P) = O. point -P is the point (X, -Y) and one has P + (-P) = O (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 Let P1:=(X1, Y1) and P2:=(X2, Y2) be distinct affine points of the
Weierstrass curve W_{a,b} and let Q:=P1 + P2, where Q is not the Weierstrass curve W_{a,b} and let Q:=P1 + P2, where Q is not the
identity element. Then Q:=(x, y), where identity element. Then Q:=(X, Y), where
X + X1 + X2 = lambda^2 and Y + Y1 = lambda*(X1 - X), where X + X1 + X2 = lambda^2 and Y + Y1 = lambda*(X1 - X), where
lambda:= (Y2 - Y1)/(X2 - X1). lambda:= (Y2 - Y1)/(X2 - X1).
Let P:=(X1, Y1) be an affine point of the Weierstrass curve W_{a,b} 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), and let Q:=2*P, where Q is not the identity element. Then Q:=(X, Y),
where where
X + 2*X1 = lambda^2 and Y + Y1 = lambda*(X1 - X), where X + 2*X1 = lambda^2 and Y + Y1 = lambda*(X1 - X), where
lambda:=(3*X1^2 + a)/(2*Y1). lambda:=(3*X1^2 + a)/(2*Y1).
From the group laws above it follows that if P=(X, Y), P1=k*P=(X1, From the group laws above it follows that if P=(X, Y), P1=(X1, Y1),
Y1), and P2=(k+1)*P=(X2, Y2) are distinct affine points of the and P2=(X2, Y2) are distinct affine points of the Weierstrass curve
Weierstrass curve W_{a,b} and if Y is nonzero, then the Y-coordinate W_{a,b} with P2:=P+P1 and if Y is nonzero, then the Y-coordinate of
of P1 can be expressed in terms of the X-coordinates of P, P1, and P1 can be expressed in terms of the X-coordinates of P, P1, and P2,
P2, and the Y-coordinate of P, as and the Y-coordinate of P, since
Y1=((X*X1+a)*(X+X1)+2*b-X2*(X-X1)^2)/(2*Y). 2*Y*Y1=(X*X1+a)*(X+X1)+2*b-X2*(X-X1)^2.
This property allows recovery of the Y-coordinate of a point P1=k*P This property allows recovery of the Y-coordinate of a point P1=k*P
that is computed via the so-called Montgomery ladder, where P is an that is computed via the so-called Montgomery ladder, where P is an
affine point with nonzero Y-coordinate (i.e., it does not have order affine point with nonzero Y-coordinate (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 X-coordinate of P2 in terms of the X-coordinates of P
and P1 and the product of their Y-coordinates. Further details are
out of scope.
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 For each point P of the Montgomery curve M_{A,B}, the point at
infinity O serves as identity element, i.e., P + O = O + P = P. infinity O serves as identity element, i.e., P + O = O + P = P.
For each affine point P:=(u, v) of the Montgomery curve M_{A,B}, the For each affine point P:=(u, v) of the Montgomery curve M_{A,B}, the
point -P is the point (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 Let P1:=(u1, v1) and P2:=(u2, v2) be distinct affine points of the
Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the
identity element. Then Q:=(u, v), where identity element. Then Q:=(u, v), where
u + u1 + u2 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), where u + u1 + u2 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), where
lambda:=(v2 - v1)/(u2 - u1). lambda:=(v2 - v1)/(u2 - u1).
Let P:=(u1, v1) be an affine point of the Montgomery curve M_{A,B} 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), and let Q:=2*P, where Q is not the identity element. Then Q:=(u, v),
where where
u + 2*u1 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), 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). 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, From the group laws above it follows that if P=(u, v), P1=(u1, v1),
v1), and P2=(k+1)*P=(u2, v2) are distinct affine points of the and P2=(u2, v2) are distinct affine points of the Montgomery curve
Montgomery curve M_{A,B} and if v is nonzero, then the v-coordinate M_{A,B} with P2:=P+P1 and if v is nonzero, then the v-coordinate of
of P1 can be expressed in terms of the u-coordinates of P, P1, and P1 can be expressed in terms of the u-coordinates of P, P1, and P2,
P2, and the v-coordinate of P, as and the v-coordinate of P, since
v1=((u*u1+1)*(u+u1+2*A)-2*A-u2*(u-u1)^2)/(2*B*v). 2*B*v*v1=(u*u1+1)*(u+u1+2*A)-2*A-u2*(u-u1)^2.
This property allows recovery of the v-coordinate of a point P1=k*P This property allows recovery of the v-coordinate of a point P1=k*P
that is computed via the so-called Montgomery ladder, where P is an that is computed via the so-called Montgomery ladder, where P is an
affine point with nonzero v-coordinate (i.e., it does not have order affine point with nonzero v-coordinate (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 u-coordinate of P2 in terms of the u-coordinates of P
and P1 and the product of their v-coordinates. Further details are
out of scope.
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} Note: The group laws below hold for twisted Edwards curves E_{a,d}
where a is a square in GF(q), whereas d is not. In this case, the where a is a square in GF(q), whereas d is not. In this case, the
addition formulae below are defined for each pair of points, without addition formulae below are defined for each pair of points, without
exceptions. Generalizations of this group law to other twisted exceptions. Generalizations of this group law to other twisted
Edwards curves are out of scope. Edwards curves are out of scope.
For each point P of the twisted Edwards curve E_{a,d}, the point For each point P of the twisted Edwards curve E_{a,d}, the point
O:=(0,1) serves as identity element, i.e., P + O = O + P = P. O:=(0,1) serves as identity element, i.e., P + O = O + P = P.
For each point P:=(x, y) of the twisted Edwards curve E_{a,d}, the For each point P:=(x, y) of the twisted Edwards curve E_{a,d}, the
point -P is the point (-x, y) and one has P + (-P) = O. point -P is the point (-x, y) and one has P + (-P) = O (i.e., -P is
the inverse of P).
Let P1:=(x1, y1) and P2:=(x2, y2) be points of the twisted Edwards Let P1:=(x1, y1) and P2:=(x2, y2) be points of the twisted Edwards
curve E_{a,d} and let Q:=P1 + P2. Then Q:=(x, y), where curve E_{a,d} and let Q:=P1 + P2. Then Q:=(x, y), where
x = (x1*y2 + x2*y1)/(1 + d*x1*x2*y1*y2) and x = (x1*y2 + x2*y1)/(1 + d*x1*x2*y1*y2) and
y = (y1*y2 - a*x1*x2)/(1 - d*x1*x2*y1*y2). y = (y1*y2 - a*x1*x2)/(1 - d*x1*x2*y1*y2).
Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and
let Q:=2*P. Then Q:=(x, y), where let Q:=2*P. Then Q:=(x, y), where
skipping to change at page 23, line 33 skipping to change at page 28, line 48
x = (2*x1*y1)/(1 + d*x1^2*y1^2) and x = (2*x1*y1)/(1 + d*x1^2*y1^2) and
y = (y1^2 - a*x1^2)/(1 - d*x1^2*y1^2). y = (y1^2 - a*x1^2)/(1 - d*x1^2*y1^2).
Note that one can use the formulae for point addition for point Note that one can use the formulae for point addition for point
doubling, taking inverses, and adding the identity element as well doubling, taking inverses, and adding the identity element as well
(i.e., the point addition formulae are uniform and complete (subject (i.e., the point addition formulae are uniform and complete (subject
to our Note above)). to our Note above)).
From the group laws above (subject to our Note above) it follows that 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 if P=(x, y), P1=(x1, y1), and P2=P=(x2, y2) are points of the twisted
points of the twisted Edwards curve E_{a,d} and if x is nonzero, then Edwards curve E_{a,d} with P2:=P+P1 and if x is nonzero, then the
the x-coordinate of P1 can be expressed in terms of the y-coordinates x-coordinate of P1 can be expressed in terms of the y-coordinates of
of P, P1, and P2, and the x-coordinate of P, as P, P1, and P2, and the x-coordinate of P, since
x*x1*(a-d*y*y1*y2)=y*y1-y2.
x1=(y*y1-y2)/(x*(a-d*y*y1*y2)).
This property allows recovery of the x-coordinate of a point P1=k*P (Here, observe that a-d*y*y1*y2 is nonzero per our Note above.) This
that is computed via the so-called Montgomery ladder, where P is an property allows recovery of the x-coordinate of a point P1=k*P that
affine point with nonzero x-coordinate (i.e., it does not have order is computed via the so-called Montgomery ladder, where P is an affine
one or two). Further details are out of scope. point with nonzero x-coordinate (i.e., it does not have order one or
two). For future reference, note that the group law (subject to our
Note above) uniquely determines the y-coordinate of P2 in terms of
the y-coordinates of P and P1 and the product of their x-coordinates.
Further details are out of scope.
Appendix D. Relationship Between Curve Models Appendix D. Relationship Between Curve Models
The non-binary curves specified in Appendix A are expressed in The non-binary curves specified in Appendix A are expressed in
different curve models, viz. as curves in short-Weierstrass form, as different curve models, viz. as curves in short-Weierstrass form, as
Montgomery curves, or as twisted Edwards curves. These curve models Montgomery curves, or as twisted Edwards curves. These curve models
are related, as follows. are related, as follows.
D.1. Mapping between Twisted Edwards Curves and Montgomery Curves D.1. Mapping between Twisted Edwards Curves and Montgomery Curves
One can map points of the Montgomery curve M_{A,B} to points of the One can map points of the Montgomery curve M_{A,B} to points of the
twisted Edwards curve E_{a,d}, where a:=(A+2)/B and d:=(A-2)/B and, twisted Edwards curve E_{a,d}, where a:=(A+2)/B and d:=(A-2)/B and,
conversely, map points of the twisted Edwards curve E_{a,d} to points conversely, map points of the twisted Edwards curve E_{a,d} to points
of the Montgomery curve M_{A,B}, where A:=2(a+d)/(a-d) and where of the Montgomery curve M_{A,B}, where A:=2*(a+d)/(a-d) and where
B:=4/(a-d). For twisted Edwards curves we consider (i.e., those B:=4/(a-d). For twisted Edwards curves we consider (i.e., those
where a is a square in GF(q), whereas d is not), this defines a one- where a is a square in GF(q), whereas d is not), this defines a one-
to-one correspondence, which - in fact - is an isomorphism between to-one correspondence, which - in fact - is an isomorphism between
M_{A,B} and E_{a,d}, thereby showing that, e.g., the discrete M_{A,B} and E_{a,d}, thereby showing that, e.g., the discrete
logarithm problem in either curve model is equally hard. logarithm problem in either curve model is equally hard.
For the Montgomery curves and twisted Edwards curves we consider, the For the Montgomery curves and twisted Edwards curves we consider, the
mapping from M_{A,B} to E_{a,d} is defined by mapping the point at mapping from M_{A,B} to E_{a,d} is defined by mapping the point at
infinity O and the point (0, 0) of order two of M_{A,B} to, infinity O and the point (0, 0) of order two of M_{A,B} to,
respectively, the point (0, 1) and the point (0, -1) of order two of respectively, the point (0, 1) and the point (0, -1) of order two of
skipping to change at page 24, line 47 skipping to change at page 30, line 17
One can map points of the Montgomery curve M_{A,B} to points of the One can map points of the Montgomery curve M_{A,B} to points of the
Weierstrass curve W_{a,b}, where a:=(3-A^2)/(3*B^2) and Weierstrass curve W_{a,b}, where a:=(3-A^2)/(3*B^2) and
b:=(2*A^3-9*A)/(27*B^3). This defines a one-to-one correspondence, b:=(2*A^3-9*A)/(27*B^3). This defines a one-to-one correspondence,
which - in fact - is an isomorphism between M_{A,B} and W_{a,b}, which - in fact - is an isomorphism between M_{A,B} and W_{a,b},
thereby showing that, e.g., the discrete logarithm problem in either thereby showing that, e.g., the discrete logarithm problem in either
curve model is equally hard. curve model is equally hard.
The mapping from M_{A,B} to W_{a,b} is defined by mapping the point The mapping from M_{A,B} to W_{a,b} is defined by mapping the point
at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while
mapping each other point (u,v) of M_{A,B} to the point 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 (X,Y):=((u+A/3)/B,v/B) of W_{a,b}.
curves can be injectively mapped to Montgomery curves, since the
latter have a point of order two and the former may not. In Note that not all Weierstrass curves can be injectively mapped to
particular, if a Weierstrass curve has prime order, such as is the Montgomery curves, since the latter have a point of order two and the
case with the so-called "NIST curves", this inverse mapping is not former may not. In particular, if a Weierstrass curve has prime
defined. order, such as is the case with the so-called "NIST prime curves",
this inverse mapping is not defined.
If the Weierstrass curve W_{a,b} has a point (alpha,0) of order two 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 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/ 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 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 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 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 M_{A,B}, while mapping each other point (X,Y) of W_{a,b} to the point
(u,v):=((X-alpha)/gamma,Y/gamma) of M_{A,B}. As before, this defines (u,v):=((X-alpha)/gamma,Y/gamma) of M_{A,B}. As before, this defines
a one-to-one correspondence, which - in fact - is an isomorphism a one-to-one correspondence, which - in fact - is an isomorphism
between W_{a,b} and M_{A,B}. It is easy to see that the mapping from 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 W_{a,b} to M_{A,B} and that from M_{A,B} to W_{a,b} (if defined) are
each other's inverse. each other's inverse.
This mapping can be used to implement elliptic curve group operations This mapping can be used to implement elliptic curve group operations
originally defined for a twisted Edwards curve or for a Montgomery originally defined for a twisted Edwards curve or for a Montgomery
curve using group operations on the corresponding elliptic curve in curve using group operations for the corresponding elliptic curve in
short-Weierstrass form and translating the result back to the short-Weierstrass form and translating the result back to the
original curve, thereby potentially allowing code reuse. original curve, thereby potentially allowing code reuse.
Note that implementations for elliptic curves with short-Weierstrass Note that implementations for elliptic curves with short-Weierstrass
form that hard-code the domain parameter a to a= -3 (which value is form that hard-code the domain parameter a to a= -3 (which value is
known to allow more efficient implementations) cannot always be used known to allow more efficient implementations) cannot always be used
this way, since the curve W_{a,b} resulting from an isomorphic this way, since the curve W_{a,b} resulting from an isomorphic
mapping cannot always be expressed as a Weierstrass curve with a=-3 mapping cannot always be expressed as a Weierstrass curve with a=-3
via a coordinate transformation. For more details, see Appendix F. via a coordinate transformation. For more details, see Appendix F.
skipping to change at page 25, line 43 skipping to change at page 31, line 17
One can map points of the twisted Edwards curve E_{a,d} to points of One can map points of the twisted Edwards curve E_{a,d} to points of
the Weierstrass curve W_{a,b}, via function composition, where one the Weierstrass curve W_{a,b}, via function composition, where one
uses the isomorphic mapping between twisted Edwards curves and uses the isomorphic mapping between twisted Edwards curves and
Montgomery curves of Appendix D.1 and the one between Montgomery and Montgomery curves of Appendix D.1 and the one between Montgomery and
Weierstrass curves of Appendix D.2. Obviously, one can use function Weierstrass curves of Appendix D.2. Obviously, one can use function
composition (now using the respective inverses - if these exist) to composition (now using the respective inverses - if these exist) to
realize the inverse of this mapping. realize the inverse of this mapping.
Appendix E. Curve25519 and Cousins Appendix E. Curve25519 and Cousins
This section introduces curves related to Curve25519 and explains
their relationships.
E.1. Curve Definition and Alternative Representations E.1. Curve Definition and Alternative Representations
The elliptic curve Curve25519 is the Montgomery curve M_{A,B} defined The elliptic curve Curve25519 is the Montgomery curve M_{A,B} defined
over the prime field GF(p), with p:=2^{255}-19, where A:=486662 and over the prime field GF(p), with p:=2^{255}-19, where A:=486662 and
B:=1. This curve has order h*n, where h=8 and where n is a prime B:=1. This curve has order h*n, where h=8 and where n is a prime
number. For this curve, A^2-4 is not a square in GF(p), whereas A+2 number. For this curve, A^2-4 is not a square in GF(p), whereas A+2
is. The quadratic twist of this curve has order h1*n1, where h1=4 is. The quadratic twist of this curve has order h1*n1, where h1=4
and where n1 is a prime number. For this curve, the base point is and where n1 is a prime number. For this curve, the base point is
the point (Gu, Gv), where Gu=9 and where Gv is an odd integer in the the point (Gu, Gv), where Gu=9 and where Gv is an odd integer in the
interval [0, p-1]. interval [0, p-1].
skipping to change at page 27, line 32 skipping to change at page 33, line 11
(0,1) and the point (0,-1) of order two of Edwards25519 correspond (0,1) and the point (0,-1) of order two of Edwards25519 correspond
to, respectively, the point at infinity O and the point (A/3, 0) of to, respectively, the point at infinity O and the point (A/3, 0) of
order two of Wei25519 and where each other point (x, y) of order two of Wei25519 and where each other point (x, y) of
Edwards25519 corresponds to the point (X, Y):=((1+y)/(1-y)+A/3, Edwards25519 corresponds to the point (X, Y):=((1+y)/(1-y)+A/3,
c*(1+y)/((1-y)*x)) of Wei25519, where c was defined before. (Here, c*(1+y)/((1-y)*x)) of Wei25519, where c was defined before. (Here,
we used the mapping of Appendix D.3.) The inverse mapping from we used the mapping of Appendix D.3.) The inverse mapping from
Wei25519 to Edwards25519 is defined by mapping the point at infinity Wei25519 to Edwards25519 is defined by mapping the point at infinity
O and the point (A/3, 0) of order two of Wei25519 to, respectively, O and the point (A/3, 0) of order two of Wei25519 to, respectively,
the identity element (0,1) and the point (0,-1) of order two of the identity element (0,1) and the point (0,-1) of order two of
Edwards25519 and having each other point (X, Y) of Wei25519 Edwards25519 and having each other point (X, Y) of Wei25519
correspond to the point (c*(3*X-A)/(3*Y), (3*X-A-3)/(3*X-A+3)) of correspond to the point (c*(X-A/3)/Y, (X-A/3-1)/(X-A/3+1)) of
Edwards25519. Edwards25519.
Note that these mappings can be easily realized if points are Note that these mappings can be easily realized if points are
represented in projective coordinates, using a few field represented in projective coordinates, using a few field
multiplications only, thus allowing switching between alternative multiplications only, thus allowing switching between alternative
curve representations with negligible relative incremental cost. curve representations with negligible relative incremental cost.
E.3. Domain Parameters E.3. Domain Parameters
The parameters of the Montgomery curve and the corresponding The parameters of the Montgomery curve and the corresponding
skipping to change at page 30, line 23 skipping to change at page 35, line 48
The mapping from E_{a,d} to E_{a',d'} is defined by mapping the point 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 (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 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 point (x', y') of E_{a',d'} to the point (x, y):=(x'/s, y') of
E_{a,d}. E_{a,d}.
Implementations may take advantage of this mapping to carry out Implementations may take advantage of this mapping to carry out
elliptic curve group operations originally defined for a twisted elliptic curve group operations originally defined for a twisted
Edwards curve with generic domain parameters a and d on a Edwards curve with generic domain parameters a and d on a
corresponding isomorphic twisted Edwards curve with domain parameters corresponding isomorphic twisted Edwards curve with domain parameters
a' and d' that have a more special form, which are known to allow for a' and d' that have a more special form and that are known to allow
more efficient implementations of addition laws. In particular, it for more efficient implementations of addition laws and translating
is known that such efficiency improvements exist if a':=-1 (see the result back to the original curve. In particular, it is known
that such efficiency improvements exist if a':=(+/-)1 (see
[tEd-Formulas]). [tEd-Formulas]).
F.2. Isomorphic Mapping between Montgomery Curves F.2. Isomorphic Mapping between Montgomery Curves
One can map points of the Montgomery curve M_{A,B} to points of the One can map points of the Montgomery curve M_{A,B} to points of the
Montgomery curve M_{A',B'}, where A:=A' and B:=B'*s^2 for some Montgomery curve M_{A',B'}, where A:=A' and B:=B'*s^2 for some
nonzero element s of GF(q). This defines a one-to-one nonzero element s of GF(q). This defines a one-to-one
correspondence, which - in fact - is an isomorphism between M_{A,B} correspondence, which - in fact - is an isomorphism between M_{A,B}
and M_{A',B'}. and M_{A',B'}.
skipping to change at page 31, line 9 skipping to change at page 36, line 37
In this case, the mapping from M_{A,B} to M_{A',B'} is defined by 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 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 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 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 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 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 other point (u',v') of M_{A',B'} to the point (u,v):=(-u',v') of
M_{A,B}. 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 elliptic curve groups operations originally defined for a Montgomery
curve with generic domain parameters A and B on a corresponding curve with generic domain parameters A and B on a corresponding
isomorphic Montgomery curve with domain parameters A' and B' that isomorphic Montgomery curve with domain parameters A' and B' that
have a more special form, which is known to allow for more efficient have a more special form and that are known to allow for more
implementations of addition laws. In particular, it is known that efficient implementations of addition laws and translating the result
such efficiency improvements exist if B' assumes a small absolute back to the original curve. In particular, it is known that such
value, such as B':=(+/-)1. (see [Mont-Ladder]). efficiency improvements exist if B' assumes a small absolute value,
such as B':=(+/-)1. (see [Mont-Ladder]).
F.3. Isomorphic Mapping between Weierstrass Curves F.3. Isomorphic Mapping between Weierstrass Curves
One can map points of the Weierstrass curve W_{a,b} to points of the One can map points of the Weierstrass curve W_{a,b} to points of the
Weierstrass curve W_{a',b'}, where a':=a*s^4 and b':=b*s^6 for some Weierstrass curve W_{a',b'}, where a':=a*s^4 and b':=b*s^6 for some
nonzero element s of GF(q). This defines a one-to-one nonzero element s of GF(q). This defines a one-to-one
correspondence, which - in fact - is an isomorphism between W_{a,b} correspondence, which - in fact - is an isomorphism between W_{a,b}
and W_{a',b'}. and W_{a',b'}.
The mapping from W_{a,b} to W_{a',b'} is defined by mapping the point The mapping from W_{a,b} to W_{a',b'} is defined by mapping the point
skipping to change at page 31, line 39 skipping to change at page 37, line 20
(X',Y'):=(X*s^2, Y*s^3) of W_{a',b'}. The inverse mapping from (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 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 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) other point (X', Y') of W_{a',b'} to the point (X,Y):=(X'/s^2,Y'/s^3)
of W_{a,b}. of W_{a,b}.
Implementations may take advantage of this mapping to carry out Implementations may take advantage of this mapping to carry out
elliptic curve group operations originally defined for a Weierstrass elliptic curve group operations originally defined for a Weierstrass
curve with generic domain parameters a and b on a corresponding curve with generic domain parameters a and b on a corresponding
isomorphic Weierstrass curve with domain parameter a' and b' that isomorphic Weierstrass curve with domain parameter a' and b' that
have a more special form, which is known to allow for more efficient have a more special form and that are known to allow for more
implementations of addition laws, and translating the result back to efficient implementations of addition laws and translating the result
the original curve. In particular, it is known that such efficiency back to the original curve. In particular, it is known that such
improvements exist if a'=-3 (mod p), where p is the characteristic of efficiency improvements exist if a'=-3 (mod p), where p is the
GF(q), and one uses so-called Jacobian coordinates with a particular characteristic of GF(q), and one uses so-called Jacobian coordinates
projective version of the addition laws of Appendix C.1. While not with a particular projective version of the addition laws of
all Weierstrass curves can be put into this form, all traditional Appendix C.1. While not all Weierstrass curves can be put into this
NIST curves have domain parameter a=-3, while all Brainpool curves form, all traditional NIST curves have domain parameter a=-3, while
[RFC5639] are isomorphic to a Weierstrass curve of this form. all Brainpool curves [RFC5639] are isomorphic to a Weierstrass curve
of this form via the above mapping.
Note that implementations for elliptic curves with short-Weierstrass Note that implementations for elliptic curves with short-Weierstrass
form that hard-code the domain parameter a to a= -3 cannot always be form that hard-code the domain parameter a to a= -3 cannot always be
used this way, since the curve W_{a,b} cannot always be expressed in used this way, since the curve W_{a,b} cannot always be expressed in
terms of a Weierstrass curve with a'=-3 via a coordinate terms of a Weierstrass curve with a'=-3 via a coordinate
transformation: this only holds if a'/a is a fourth power in GF(q) transformation: this only holds if a'/a is a fourth power in GF(q)
(see Section 3.1.5 of [GECC]). However, even in this case, one can (see Section 3.1.5 of [GECC]). However, even in this case, one can
still express the curve W_{a,b} as a Weierstrass curve with a small still express the curve W_{a,b} as a Weierstrass curve with a small
domain parameter value a', thereby still allowing a more efficient domain parameter value a', thereby still allowing a more efficient
implementation than with a general domain parameter value a. implementation than with a general domain parameter value a.
skipping to change at page 32, line 33 skipping to change at page 38, line 15
defined for a Weierstrass curve with domain parameter a unequal to -3 defined for a Weierstrass curve with domain parameter a unequal to -3
(mod p) on a corresponding isogenous Weierstrass curve with domain (mod p) on a corresponding isogenous Weierstrass curve with domain
parameter a'=-3 (mod p) and translating the result back to the parameter a'=-3 (mod p) and translating the result back to the
original curve. original curve.
In this case, the mapping from W_{a,b} to W_{a',b'} is defined by In this case, the mapping from W_{a,b} to W_{a',b'} is defined by
mapping the point at infinity O of W_{a,b} to the point at infinity O mapping the point at infinity O of W_{a,b} to the point at infinity O
of W_{a',b'}, while mapping each other point (X,Y) of W_{a,b} to the of W_{a',b'}, while mapping each other point (X,Y) of W_{a,b} to the
point (X',Y'):=(u(X)/w(X)^2,Y*v(X)/w(X)^3) of W_{a',b'}. Here, u(X), 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 v(X), and w(X) are polynomials in X that depend on the isogeny in
question. The inverse mapping from W_{a',b'} to W_{a,b} is again an question, as do domain parameters a' and b'. The inverse mapping
isogeny and defined by mapping the point at infinity O of W_{a',b'} 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 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') 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 -- (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 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 on the isogeny in question. These mappings have the property that
their composition is not the identity mapping (as was the case with their composition is not the identity mapping (as was the case with
the isomorphic mappings discussed in Appendix F.3), but rather a the isomorphic mappings discussed in Appendix F.3), but rather a
fixed multiple hereof: if this multiple is l then the isogeny is fixed multiple hereof: if this multiple is l then the isogeny is
called an isogeny of degree l (or l-isogeny) and u, v, and w (and, called an isogeny of degree l (or l-isogeny) and u, v, and w (and,
similarly, u', v', and w') are polynomials of degrees l, 3*(l-1)/2, similarly, u', v', and w') are polynomials of degrees l, 3*(l-1)/2,
and (l-1)/2, respectively. Note that an isomorphism is simply an and (l-1)/2, respectively. Note that an isomorphism is simply an
isogeny of degree l=1. Details of how to determine isogenies are out 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 Implementations may take advantage of this mapping to carry out
elliptic curve group operations originally defined for a Weierstrass elliptic curve group operations originally defined for a Weierstrass
curve with a generic domain parameter a on a corresponding isogenous curve with a generic domain parameter a on a corresponding isogenous
Weierstrass curve with domain parameter a'=-3 (mod p), where one can Weierstrass curve with domain parameter a'=-3 (mod p), where one can
use so-called Jacobian coordinates with a particular projective use so-called Jacobian coordinates with a particular projective
version of the addition laws of Appendix C.1. Since all traditional version of the addition laws of Appendix C.1. Since all traditional
NIST curves have domain parameter a=-3, while all Brainpool curves NIST curves have domain parameter a=-3, while all Brainpool curves
[RFC5639] are isomorphic to a Weierstrass curve of this form, this [RFC5639] are isomorphic to a Weierstrass curve of this form, this
allows taking advantage of existing implementations for these curves allows taking advantage of existing implementations for these curves
skipping to change at page 33, line 29 skipping to change at page 39, line 14
the isogeny has low degree l). Note, however, that this does require the isogeny has low degree l). Note, however, that this does require
storage of the polynomial coefficients of the isogeny and dual storage of the polynomial coefficients of the isogeny and dual
isogeny involved. This illustrates that low-degree isogenies are to isogeny involved. This illustrates that low-degree isogenies are to
be preferred, since an l-isogeny (usually) requires storing roughly be preferred, since an l-isogeny (usually) requires storing roughly
6*l elements of GF(q). While there are many isogenies, we therefore 6*l elements of GF(q). While there are many isogenies, we therefore
only consider those with the desired property with lowest possible only consider those with the desired property with lowest possible
degree. degree.
Appendix G. Further Cousins of Curve25519 Appendix G. Further Cousins of Curve25519
This section introduces some further curves related to Curve25519 and
explains their relationships.
G.1. Further Alternative Representations G.1. Further Alternative Representations
The Weierstrass curve Wei25519 is isomorphic to the Weierstrass curve The Weierstrass curve Wei25519 is isomorphic to the Weierstrass curve
Wei25519.2 defined over GF(p), with as base point the pair (G2X,G2Y), Wei25519.2 defined over GF(p), with as base point the pair (G2X,G2Y),
and isogenous to the Weierstrass curve Wei25519.-3 defined over and isogenous to the Weierstrass curve Wei25519.-3 defined over
GF(p), with as base point the pair (G3X, G3Y), where parameters are 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 as specified in Appendix G.3 and where the related mappings are as
specified in Appendix G.2. specified in Appendix G.2.
G.2. Further Switching G.2. Further Switching
skipping to change at page 34, line 16 skipping to change at page 40, line 4
the affine point (X', Y') of Wei25519.2 to (X,Y):=(X'/s^2,Y'/s^3) of 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 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 point at infinity O of Wei25519. Note that this mapping (and its
inverse) involves a modular multiplication of both coordinates with inverse) involves a modular multiplication of both coordinates with
fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which
can be precomputed. can be precomputed.
Each affine point (X,Y) of Wei25519 corresponds to the point Each affine point (X,Y) of Wei25519 corresponds to the point
(X',Y'):=(X1*t^2,Y1*t^3) of Wei25519.-3, where (X',Y'):=(X1*t^2,Y1*t^3) of Wei25519.-3, where
(X1,Y1)=(u(X)/w(X)^2,Y*v(X)/w(X)^3), where u, v, and w are the (X1,Y1)=(u(X)/w(X)^2,Y*v(X)/w(X)^3), where u, v, and w are the
polynomials with coefficients in GF(p) as defined in Appendix H.1 and polynomials with coefficients in GF(p) as defined in Appendix G.4.1
where t is the element of GF(p) defined by and where t is the element of GF(p) defined by
t 35728133398289175649586938605660542688691615699169662967154525084 t 35728133398289175649586938605660542688691615699169662967154525084
644181596229 644181596229
(=0x4efd6829 88ff8526 e189f712 5999550c e9ef729b ed1a7015 (=0x4efd6829 88ff8526 e189f712 5999550c e9ef729b ed1a7015
73b1bab8 8bfcd845), 73b1bab8 8bfcd845),
while the point at infinity of Wei25519 corresponds to the point at while the point at infinity of Wei25519 corresponds to the point at
infinity of Wei25519.-3. (Here, we used the isogenous mapping of infinity of Wei25519.-3. (Here, we used the isogenous mapping of
Appendix F.4.) Under this isogenous mapping, the base point (GX,GY) Appendix F.4.) Under this isogenous mapping, the base point (GX,GY)
of Wei25519 corresponds to the base point (G3X,G3Y) of Wei25519.-3. 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 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, 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 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 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 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 (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 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 of the isogeny; see the description in Appendix F.4). Note that this
isogenous map (and its dual) primarily involves the evaluation of isogenous map (and its dual) primarily involves the evaluation of
three fixed polynomials involving the x-coordinate, which takes three fixed polynomials involving the x-coordinate, which takes
roughly 140 modular multiplications (or less than 5-10% relative roughly 140 modular multiplications (or less than 5-10% relative
incremental cost compared to the cost of an elliptic curve scalar incremental cost compared to the cost of an elliptic curve scalar
multiplication). multiplication).
skipping to change at page 36, line 4 skipping to change at page 41, line 39
796e1022 40891faa) 796e1022 40891faa)
G3X 53837179229940872434942723257480777370451127212339198133697207846 G3X 53837179229940872434942723257480777370451127212339198133697207846
219400243292 219400243292
(=0x7706c37b 5a84128a 3884a5d7 1811f1b5 5da3230f fb17a8ab (=0x7706c37b 5a84128a 3884a5d7 1811f1b5 5da3230f fb17a8ab
0b32e48d 31a6685c) 0b32e48d 31a6685c)
G3Y 69548073091100184414402055529279970392514867422855141773070804184 G3Y 69548073091100184414402055529279970392514867422855141773070804184
60388229929 60388229929
(=0x0f60480c 7a5c0e11 40340adc 79d6a2bf 0cb57ad0 49d025dc (=0x0f60480c 7a5c0e11 40340adc 79d6a2bf 0cb57ad0 49d025dc
38d80c77 985f0329) 38d80c77 985f0329)
Appendix H. Isogeny Details G.4. Isogeny Details
The isogeny and dual isogeny are both isogenies with degree l=47. The isogeny and dual isogeny are both isogenies with degree l=47.
Both are specified by a triple of polynomials u, v, and w (resp. u', Both are specified by a triple of polynomials u, v, and w (resp. u',
v', and w') of degree 47, 69, and 23, respectively, with coefficients v', and w') of degree 47, 69, and 23, respectively, with coefficients
in GF(p). The coeffients of each of these polynomials are specified in GF(p). The coeffients of each of these polynomials are specified
in Appendix H.1 (for the isogeny) and in Appendix H.2 (for the dual in Appendix G.4.1 (for the isogeny) and in Appendix G.4.2 (for the
isogeny). For each polynomial in variable x, the coefficients are dual isogeny). For each polynomial in variable x, the coefficients
tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in are tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in
hexadecimal format. 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 0 0x670ed14828b6f1791ceb3a9cc0edfe127dee8729c5a72ddf77bb1abaebbba1e8
1 0x1135ca8bd5383cb3545402c8bce2ced14b45c29b241e4751b035f27524a9f932 1 0x1135ca8bd5383cb3545402c8bce2ced14b45c29b241e4751b035f27524a9f932
2 0x3223806ff5f669c430efd74df8389f058d180e2fcffa5cdef3eacecdd2c34771 2 0x3223806ff5f669c430efd74df8389f058d180e2fcffa5cdef3eacecdd2c34771
3 0x31b8fecf3f17a819c228517f6cd9814466c8c8bea2efccc47a29bfc14c364266 3 0x31b8fecf3f17a819c228517f6cd9814466c8c8bea2efccc47a29bfc14c364266
4 0x2541305c958c5a326f44efad2bec284e7abee840fadb08f2d994cd382fd8ce42 4 0x2541305c958c5a326f44efad2bec284e7abee840fadb08f2d994cd382fd8ce42
skipping to change at page 38, line 17 skipping to change at page 44, line 4
41 0x5a74d1296aaaa245ffb848f434531fa3ba9e5cb9098a7091d36c2777d4cf5a13 41 0x5a74d1296aaaa245ffb848f434531fa3ba9e5cb9098a7091d36c2777d4cf5a13
42 0x4bd3b700606397083f8038177bdaa1ac6edbba0447537582723cae0fd29341a9 42 0x4bd3b700606397083f8038177bdaa1ac6edbba0447537582723cae0fd29341a9
43 0x573453fb2b093016f3368356c786519d54ed05f5372c01723b4da520597ec217 43 0x573453fb2b093016f3368356c786519d54ed05f5372c01723b4da520597ec217
44 0x77f5c605bdb3a30d7d9c8840fce38650910d4418eed707a212c8927f41c2c812 44 0x77f5c605bdb3a30d7d9c8840fce38650910d4418eed707a212c8927f41c2c812
45 0x16d6b9f7ff57ca32350057de1204cc6d69d4ef1b255dfef8080118e2fef6ace3 45 0x16d6b9f7ff57ca32350057de1204cc6d69d4ef1b255dfef8080118e2fef6ace3
46 0x34e8595832a4021f8b5744014c6b4f7da7df0d0329e8b6b4d44c8fadad6513b7 46 0x34e8595832a4021f8b5744014c6b4f7da7df0d0329e8b6b4d44c8fadad6513b7
47 0x01 47 0x01
H.1.2. Coefficients of v(x) G.4.1.2. Coefficients of v(x)
0 0x0f9f5eb7134e6f8dafa30c45afa58d7bfc6d4e3ccbb5de87b562fd77403972b2 0 0x0f9f5eb7134e6f8dafa30c45afa58d7bfc6d4e3ccbb5de87b562fd77403972b2
1 0x36c2dcd9e88f0d2d517a15fc453a098bbbb5a05eb6e8da906fae418a4e1a13f7 1 0x36c2dcd9e88f0d2d517a15fc453a098bbbb5a05eb6e8da906fae418a4e1a13f7
2 0x0b40078302c24fa394a834880d5bf46732ca1b4894172fb7f775821276f558b3 2 0x0b40078302c24fa394a834880d5bf46732ca1b4894172fb7f775821276f558b3
3 0x53dd8e2234573f7f3f7df11e90a7bdd7b75d807f9712f521d4fb18af59aa5f26 3 0x53dd8e2234573f7f3f7df11e90a7bdd7b75d807f9712f521d4fb18af59aa5f26
4 0x6d4d7bb08de9061988a8cf6ff3beb10e933d4d2fbb8872d256a38c74c8c2ceda 4 0x6d4d7bb08de9061988a8cf6ff3beb10e933d4d2fbb8872d256a38c74c8c2ceda
skipping to change at page 41, line 17 skipping to change at page 47, line 4
64 0x0dab71e2ae94e6530a501ed8cf3df26731dd1d41cd81578341e12dca3cb71aa3 64 0x0dab71e2ae94e6530a501ed8cf3df26731dd1d41cd81578341e12dca3cb71aa3
65 0x537f58d52d18ce5b1d5a6bd3a420e796e64173491ad43dd4d1083a7dcc7dd201 65 0x537f58d52d18ce5b1d5a6bd3a420e796e64173491ad43dd4d1083a7dcc7dd201
66 0x49c2f6afa93fdcc4e0f8128a8b06da4c75049be14edf3e103821ab604c60f8ae 66 0x49c2f6afa93fdcc4e0f8128a8b06da4c75049be14edf3e103821ab604c60f8ae
67 0x10a333eabd6135aeaa3f5f5f7e73d102e4fd7e4bf0902fc55b00da235fa1ad08 67 0x10a333eabd6135aeaa3f5f5f7e73d102e4fd7e4bf0902fc55b00da235fa1ad08
68 0x0f5c86044bf6032f5102e601f2a0f73c7bce9384bedd120f3e72d78484179d9c 68 0x0f5c86044bf6032f5102e601f2a0f73c7bce9384bedd120f3e72d78484179d9c
69 0x01 69 0x01
H.1.3. Coefficients of w(x) G.4.1.3. Coefficients of w(x)
0 0x3da24d42421264f30939ff00203880f2b017eb3fecf8933ae61e18df8c8ba116 0 0x3da24d42421264f30939ff00203880f2b017eb3fecf8933ae61e18df8c8ba116
1 0x0457f20bc393cdc9a66848ce174e2fa41d77e6dbae05a317a1fb6e3ae78760f8 1 0x0457f20bc393cdc9a66848ce174e2fa41d77e6dbae05a317a1fb6e3ae78760f8
2 0x7f608a2285c480d5c9592c435431fae94695beef79d770bb6d029c1d10a53295 2 0x7f608a2285c480d5c9592c435431fae94695beef79d770bb6d029c1d10a53295
3 0x3832accc520a485100a0a1695792465142a5572bed1b2e50e1f8f662ac7289bb 3 0x3832accc520a485100a0a1695792465142a5572bed1b2e50e1f8f662ac7289bb
4 0x2df1b0559e31b328eb34beedd5e537c3f4d7b9befb0749f75d6d0d866d26fbaa 4 0x2df1b0559e31b328eb34beedd5e537c3f4d7b9befb0749f75d6d0d866d26fbaa
skipping to change at page 42, line 17 skipping to change at page 48, line 4
17 0x781d69243b6c86f59416f91f7decaca93eab9cdc36a184191810c56ed85e0fdc 17 0x781d69243b6c86f59416f91f7decaca93eab9cdc36a184191810c56ed85e0fdc
18 0x5f20526f4177357da40a18da054731d442ad2a5a4727322ba8ed10d32eca24fb 18 0x5f20526f4177357da40a18da054731d442ad2a5a4727322ba8ed10d32eca24fb
19 0x33e4cab64ed8a00d8012104fe8f928e6173c428eff95bbbe569ea46126a4f3cd 19 0x33e4cab64ed8a00d8012104fe8f928e6173c428eff95bbbe569ea46126a4f3cd
20 0x050555b6f07e308d33776922b6566829d122e19b25b7bbacbb0a4b1a7dc40192 20 0x050555b6f07e308d33776922b6566829d122e19b25b7bbacbb0a4b1a7dc40192
21 0x533fa4bf1e2a2aae2f979065fdbb5b667ede2f85543fddbba146aa3a4ef2d281 21 0x533fa4bf1e2a2aae2f979065fdbb5b667ede2f85543fddbba146aa3a4ef2d281
22 0x5a742cac1952010fc5aba200a635a7bed3ef868194f45b5a6a2647d6d6b289d2 22 0x5a742cac1952010fc5aba200a635a7bed3ef868194f45b5a6a2647d6d6b289d2
23 0x01 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 0 0x0f0eddb584a20aaac8f1419efdd02a5cca77b21e4cfae78c49b5127d98bc5882
1 0x7115e60d44a58630417df33dd45b8a546fa00b79fea3b2bdc449694bade87c0a 1 0x7115e60d44a58630417df33dd45b8a546fa00b79fea3b2bdc449694bade87c0a
2 0x0b3f3a6f3c445c7dc1f91121275414e88c32ff3f367ba0edad4d75b7e7b94b65 2 0x0b3f3a6f3c445c7dc1f91121275414e88c32ff3f367ba0edad4d75b7e7b94b65
3 0x1eb31bb333d7048b87f2b3d4ec76d69035927b41c30274368649c87c52e1ab30 3 0x1eb31bb333d7048b87f2b3d4ec76d69035927b41c30274368649c87c52e1ab30
4 0x552c886c2044153e280832264066cce2a7da1127dc9720e2a380e9d37049ac64 4 0x552c886c2044153e280832264066cce2a7da1127dc9720e2a380e9d37049ac64
skipping to change at page 44, line 17 skipping to change at page 50, line 4
39 0x53de362e2f8ff220f8921620a71e8faa1aa57f8886fcbb6808fa3a5560570543 39 0x53de362e2f8ff220f8921620a71e8faa1aa57f8886fcbb6808fa3a5560570543
40 0x0dc29a73b97f08aa8774911474e651130ed364e8d8cffd4a80dee633aacecc47 40 0x0dc29a73b97f08aa8774911474e651130ed364e8d8cffd4a80dee633aacecc47
41 0x4e7eb8584ae4de525389d1e9300fc4480b3d9c8a5a45ecfbe33311029d8f6b99 41 0x4e7eb8584ae4de525389d1e9300fc4480b3d9c8a5a45ecfbe33311029d8f6b99
42 0x6c3cba4aa9229550fa82e1cfaee4b02f2c0cb86f79e0d412b8e32b00b7959d80 42 0x6c3cba4aa9229550fa82e1cfaee4b02f2c0cb86f79e0d412b8e32b00b7959d80
43 0x5a9d104ae585b94af68eeb16b1349776b601f97b7ce716701645b1a75b68dcf3 43 0x5a9d104ae585b94af68eeb16b1349776b601f97b7ce716701645b1a75b68dcf3
44 0x754e014b5e87af035b3d5fe6fb49f4631e32549f6341c6693c5172a6388e273e 44 0x754e014b5e87af035b3d5fe6fb49f4631e32549f6341c6693c5172a6388e273e
45 0x6710d8265118e22eaceba09566c86f642ab42da58c435083a353eaa12d866c39 45 0x6710d8265118e22eaceba09566c86f642ab42da58c435083a353eaa12d866c39
46 0x6e88ac659ce146c369f8b24c3a49f8dca547827250cf7963a455851cfc4f8d22 46 0x6e88ac659ce146c369f8b24c3a49f8dca547827250cf7963a455851cfc4f8d22
47 0x0971eb5f253356cd1fde9fb21f4a4902aa5b8d804a2b57ba775dc130181ae2e8 47 0x0971eb5f253356cd1fde9fb21f4a4902aa5b8d804a2b57ba775dc130181ae2e8
H.2.2. Coefficients of v'(x) G.4.2.2. Coefficients of v'(x)
0 0x043c9b67cc5b16e167b55f190db61e44d48d813a7112910f10e3fd8da85d61d3 0 0x043c9b67cc5b16e167b55f190db61e44d48d813a7112910f10e3fd8da85d61d3
1 0x72046db07e0e7882ff3f0f38b54b45ca84153be47a7fd1dd8f6402e17c47966f 1 0x72046db07e0e7882ff3f0f38b54b45ca84153be47a7fd1dd8f6402e17c47966f
2 0x1593d97b65a070b6b3f879fe3dc4d1ef03c0e781c997111d5c1748f956f1ffc0 2 0x1593d97b65a070b6b3f879fe3dc4d1ef03c0e781c997111d5c1748f956f1ffc0
3 0x54e5fec076b8779338432bdc5a449e36823a0a7c905fd37f232330b026a143a0 3 0x54e5fec076b8779338432bdc5a449e36823a0a7c905fd37f232330b026a143a0
4 0x46328dd9bc336e0873abd453db472468393333fbf2010c6ac283933216e98038 4 0x46328dd9bc336e0873abd453db472468393333fbf2010c6ac283933216e98038
skipping to change at page 47, line 17 skipping to change at page 53, line 4
62 0x0a90f0059da81a012e9d0a756809fab2ce61cb45965d4d1513a06227783ee4ea 62 0x0a90f0059da81a012e9d0a756809fab2ce61cb45965d4d1513a06227783ee4ea
63 0x39fa55971c9e833f61139c39e243d40869fd7e8a1417ee4e7719dd2dd242766f 63 0x39fa55971c9e833f61139c39e243d40869fd7e8a1417ee4e7719dd2dd242766f
64 0x22677c1e659caa324f0c74a013921facf62d0d78f273563145cc1ddccfcc4421 64 0x22677c1e659caa324f0c74a013921facf62d0d78f273563145cc1ddccfcc4421
65 0x3468cf6df7e93f7ff1fe1dd7e180a89dec3ed4f72843b4ea8a8d780011a245b2 65 0x3468cf6df7e93f7ff1fe1dd7e180a89dec3ed4f72843b4ea8a8d780011a245b2
66 0x68f75a0e2210f52a90704ed5f511918d1f6bcfcd26b462cc4975252369db6e9d 66 0x68f75a0e2210f52a90704ed5f511918d1f6bcfcd26b462cc4975252369db6e9d
67 0x6220c0699696e9bcab0fe3a80d437519bd2bdf3caef665e106b2dd47585ddd9f 67 0x6220c0699696e9bcab0fe3a80d437519bd2bdf3caef665e106b2dd47585ddd9f
68 0x553ad47b129fb347992b576479b0a89f8d71f1196f83e5eaab5f533a1dd6f6d7 68 0x553ad47b129fb347992b576479b0a89f8d71f1196f83e5eaab5f533a1dd6f6d7
69 0x239aef387e116ec8730fa15af053485ca707650d9f8917a75f22acf6213197df 69 0x239aef387e116ec8730fa15af053485ca707650d9f8917a75f22acf6213197df
H.2.3. Coefficients of w'(x) G.4.2.3. Coefficients of w'(x)
0 0x6bd7f1fc5dd51b7d832848c180f019bcbdb101d4b3435230a79cc4f95c35e15e 0 0x6bd7f1fc5dd51b7d832848c180f019bcbdb101d4b3435230a79cc4f95c35e15e
1 0x17413bb3ee505184a504e14419b8d7c8517a0d268f65b0d7f5b0ba68d6166dd0 1 0x17413bb3ee505184a504e14419b8d7c8517a0d268f65b0d7f5b0ba68d6166dd0
2 0x47f4471beed06e5e2b6d5569c20e30346bdba2921d9676603c58e55431572f90 2 0x47f4471beed06e5e2b6d5569c20e30346bdba2921d9676603c58e55431572f90
3 0x2af7eaafd04f6910a5b01cdb0c27dca09487f1cd1116b38db34563e7b0b414eb 3 0x2af7eaafd04f6910a5b01cdb0c27dca09487f1cd1116b38db34563e7b0b414eb
4 0x57f0a593459732eef11d2e2f7085bf9adf534879ba56f7afd17c4a40d3d3477b 4 0x57f0a593459732eef11d2e2f7085bf9adf534879ba56f7afd17c4a40d3d3477b
skipping to change at page 48, line 17 skipping to change at page 54, line 4
15 0x55d8a5ceef588ab52a07fa6047d6045550a5c52c91cc8b6b82eeb033c8ca557d 15 0x55d8a5ceef588ab52a07fa6047d6045550a5c52c91cc8b6b82eeb033c8ca557d
16 0x620b5a4974cc3395f96b2a0fa9e6454202ef2c00d82b0e6c534b3b1d20f9a572 16 0x620b5a4974cc3395f96b2a0fa9e6454202ef2c00d82b0e6c534b3b1d20f9a572
17 0x4991b763929b00241a1a9a68e00e90c5df087f90b3352c0f4d8094a51429524e 17 0x4991b763929b00241a1a9a68e00e90c5df087f90b3352c0f4d8094a51429524e
18 0x18b6b49c5650fb82e36e25fd4eb6decfdd40b46c37425e6597c7444a1b6afb4e 18 0x18b6b49c5650fb82e36e25fd4eb6decfdd40b46c37425e6597c7444a1b6afb4e
19 0x6868305b4f40654460aad63af3cb9151ab67c775eaac5e5df90d3aea58dee141 19 0x6868305b4f40654460aad63af3cb9151ab67c775eaac5e5df90d3aea58dee141
20 0x16bc90219a36063a22889db810730a8b719c267d538cd28fa7c0d04f124c8580 20 0x16bc90219a36063a22889db810730a8b719c267d538cd28fa7c0d04f124c8580
21 0x3628f9cf1fbe3eb559854e3b1c06a4cd6a26906b4e2d2e70616a493bba2dc574 21 0x3628f9cf1fbe3eb559854e3b1c06a4cd6a26906b4e2d2e70616a493bba2dc574
22 0x64abcc6759f1ce1ab57d41e17c2633f717064e35a7233a6682f8cf8e9538afec 22 0x64abcc6759f1ce1ab57d41e17c2633f717064e35a7233a6682f8cf8e9538afec
23 0x01 23 0x01
Appendix I. Point Compression Appendix H. Point Compression
Point compression allows a shorter representation of affine points of Point compression allows a shorter representation of affine points of
an elliptic curve by exploiting algebraic relationships between the an elliptic curve by exploiting algebraic relationships between the
coordinate values based on the defining equation of the curve in coordinate values based on the defining equation of the curve in
question. Point decompression refers to the reverse process, where 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. representation and information on the domain parameters of the curve.
Consequently, point compression followed by point decompression is Consequently, point compression followed by point decompression is
the identity map. the identity map.
The description below makes use of an auxiliary function (the parity The description below makes use of an auxiliary function (the parity
function), which we first define for prime fields GF(p) and then function), which we first define for prime fields GF(p), with p odd,
extend to all fields GF(q), where q is an odd prime power. We assume and then extend to all fields GF(q), where q is an odd prime power.
each finite field to be unambiguously defined. 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, Let y be a nonzero element of GF(q). If q:=p is an odd prime number,
y and p-y can be uniquely represented as integers in the interval y and p-y can be uniquely represented as integers in the interval
[1,p-1] and have odd sum p. Consequently, one can distinguish y from [1,p-1] and have odd sum p. Consequently, one can distinguish y from
-y via the parity of this representation, i.e., via par(y):=y (mod -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 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 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 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 nonzero coordinate values of y and -y are in the same position and
have representations in [1,p-1] with different parity. As a result, have representations in [1,p-1] with different parity. As a result,
one can distinguish y from -y via the parity of the representation of one can distinguish y from -y via the parity of the representation of
this coordinate value. This extends the definition of the parity this coordinate value. This extends the definition of the parity
function to any odd-size field GF(q), where one defines par(0):=0. function to any odd-size 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} 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 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 defining equation Y^2=X^2+a*X+b has at most two solutions with fixed
X-value, one can represent P by its X-coordinate and one bit of X-value, one can represent P by its X-coordinate and one bit of
information that allows one to distinguish P from -P, i.e., one can 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 represent P as the ordered pair compr(P):=(X, par(Y)). If P is a
point of order two, one can uniquely represent P by its X-coordinate point of order two, one can uniquely represent P by its X-coordinate
alone, since Y=0 and has fixed parity. Conversely, given the ordered 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 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 the domain parameters of the curve W_{a,b}, one can use the defining
of the curve to try and determine candidate values for the equation of the curve to try and determine candidate values for the
Y-coordinate given X, by solving the quadratic equation Y^2:=alpha, Y-coordinate given X, by solving the quadratic equation Y^2:=alpha,
where alpha:=X^3+a*X+b. If alpha is not a square in GF(q), this where alpha:=X^3+a*X+b. If alpha is not a square in GF(q), this
equation does not have a solution in GF(q) and the ordered pair (X, equation does not have a solution in GF(q) and the ordered pair (X,
t) does not correspond to a point of this curve. Otherwise, there t) does not correspond to a point of this curve. Otherwise, there
are two solutions, viz. Y=sqrt(alpha) and -Y. If alpha is a nonzero are two solutions, viz. Y=sqrt(alpha) and -Y. If alpha is a nonzero
element of GF(q), one can uniquely recover the Y-coordinate for which element of GF(q), one can uniquely recover the Y-coordinate for which
par(Y):=t and, thereby, the point P:=(X, Y). This is also the case par(Y):=t and, thereby, the point P:=(X, Y). This is also the case
if alpha=0 and t=0, in which case Y=0 and the point P has order two. if alpha=0 and t=0, in which case Y=0 and the point P has order two.
However, if alpha=0 and t=1, the ordered pair (X, t) does not However, if alpha=0 and t=1, the ordered pair (X, t) does not
correspond to the outcome of the point compression function. correspond to the outcome of the point compression function.
skipping to change at page 49, line 43 skipping to change at page 55, line 30
infinity O with any ordered pair compr(O):=(X,0), where X is any 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), 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 and recover this point accordingly. In this case, the point at
infinity O can be represented by any ordered pair (X,0) of elements 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 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 this ordered pair does not satisfy the defining equation of the curve
in question. An application may fix a specific suitable value of X in question. An application may fix a specific suitable value of X
or choose multiple such values and use this to encode additonal or choose multiple such values and use this to encode additonal
information. Further details are out of scope. 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} If P:=(u, v) is an affine point of the Montgomery curve M_{A,B}
defined over the field GF(q), then so is -P:=(u, -v). Since the defined over the field GF(q), then so is -P:=(u, -v). Since the
defining equation B*v^2=u^3+A*u^2+u has at most two solutions with defining equation B*v^2=u^3+A*u^2+u has at most two solutions with
fixed u-value, one can represent P by its u-coordinate and one bit of fixed u-value, one can represent P by its u-coordinate and one bit of
information that allows one to distinguish P from -P, i.e., one can information that allows one to distinguish P from -P, i.e., one can
represent P as the ordered pair compr(P):=(u, par(v)). If P is a represent P as the ordered pair compr(P):=(u, par(v)). If P is a
point of order two, one can uniquely represent P by its u-coordinate point of order two, one can uniquely represent P by its u-coordinate
alone, since v=0 and has fixed parity. Conversely, given the ordered alone, since v=0 and has fixed parity. Conversely, given the ordered
pair (u, t), where u is an element of GF(q) and where t=0 or t=1, and 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 the domain parameters of the curve M_{A,B}, one can use the defining
of the curve to try and determine candidate values for the equation of the curve to try and determine candidate values for the
v-coordinate given u, by solving the quadratic equation v^2:=alpha, v-coordinate given u, by solving the quadratic equation v^2:=alpha,
where alpha:=(u^3+A*u^2+u)/B. If alpha is not a square in GF(q), 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 this equation does not have a solution in GF(q) and the ordered pair
(u, t) does not correspond to a point of this curve. Otherwise, (u, t) does not correspond to a point of this curve. Otherwise,
there are two solutions, viz. v=sqrt(alpha) and -v. If alpha is a there are two solutions, viz. v=sqrt(alpha) and -v. If alpha is a
nonzero element of GF(q), one can uniquely recover the v-coordinate nonzero element of GF(q), one can uniquely recover the v-coordinate
for which par(v):=t and, thereby, the affine point P:=(u, v). This for which par(v):=t and, thereby, the affine point P:=(u, v). This
is also the case if alpha=0 and t=0, in which case v=0 and the point is also the case if alpha=0 and t=0, in which case v=0 and the point
P has order two. However, if alpha=0 and t=1, the ordered pair (u, P has order two. However, if alpha=0 and t=1, the ordered pair (u,
t) does not correspond to the outcome of the point compression t) does not correspond to the outcome of the point compression
function. function.
We extend the definition of the point compression function to all We extend the definition of the point compression function to all
points of the curve M_{A,B}, by associating the (non-affine) point at points of the curve M_{A,B}, by associating the (non-affine) point at
infinity O with the ordered pair compr(O):=(0,1) and recover this infinity O with the ordered pair compr(O):=(0,1) and recover this
point accordingly. (Note that this corresponds to the case alpha=0 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 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 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. 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} If P:=(x, y) is an affine point of the twisted Edwards curve E_{a,d}
defined over the field GF(q), then so is -P:=(-x, y). Since the defined over the field GF(q), then so is -P:=(-x, y). Since the
defining equation a*x^2+y^2=1+d*x^2*y^2 has at most two solutions defining equation a*x^2+y^2=1+d*x^2*y^2 has at most two solutions
with fixed y-value, one can represent P by its y-coordinate and one with fixed y-value, one can represent P by its y-coordinate and one
bit of information that allows one to distinguish P from -P, i.e., bit of information that allows one to distinguish P from -P, i.e.,
one can represent P as the ordered pair compr(P):=(par(x), y). If P one can represent P as the ordered pair compr(P):=(par(x), y). If P
is a point of order one or two, one can uniquely represent P by its is a point of order one or two, one can uniquely represent P by its
y-coordinate alone, since x=0 and has fixed parity. Conversely, y-coordinate alone, since x=0 and has fixed parity. Conversely,
given the ordered pair (t, y), where y is an element of GF(q) and 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 where t=0 or t=1, and the domain parameters of the curve E_{a,d}, one
the defining equation of the curve to try and determine candidate can use the defining equation of the curve to try and determine
values for the x-coordinate given y, by solving the quadratic candidate values for the x-coordinate given y, by solving the
equation x^2:=alpha, where alpha:=(1-y^2)/(a-d*y^2). If alpha is not quadratic equation x^2:=alpha, where alpha:=(1-y^2)/(a-d*y^2).
a square in GF(q), this equation does not have a solution in GF(q) (Here, observe that the denominator is nonzero for any point of
and the ordered pair (t, y) does not correspond to a point of this E_{a,d}.) If alpha is not a square in GF(q), this equation does not
curve. Otherwise, there are two solutions, viz. x=sqrt(alpha) and have a solution in GF(q) and the ordered pair (t, y) does not
-x. If alpha is a nonzero element of GF(q), one can uniquely recover correspond to a point of this curve. Otherwise, there are two
the x-coordinate for which par(x):=t and, thereby, the affine point solutions, viz. x=sqrt(alpha) and -x. If alpha is a nonzero element
P:=(x, y). This is also the case if alpha=0 and t=0, in which case of GF(q), one can uniquely recover the x-coordinate for which
x=0 and the point P has order one or two. However, if alpha=0 and par(x):=t and, thereby, the affine point P:=(x, y). This is also the
t=1, the ordered pair (t, y) does not correspond to the outcome of case if alpha=0 and t=0, in which case x=0 and the point P has order
the point compression function. 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 Note that the point compression function is defined for all points of
the twisted Edwards curve E_{a,d} (subject to the Note in the twisted Edwards curve E_{a,d}. Here, the identity element
Appendix C.3). Here, the identity element O:=(0,1) is associated O:=(0,1) is associated with the compressed point compr(O):=(0,1).
with the compressed point compr(O):=(0,1). (Note that this (Note that this corresponds to the case alpha=0 and t=0 above.)
corresponds to the case alpha=0 and t=0 above.)
We extend the definition of the compression function further, to also We extend the definition of the compression function further, to also
include a special marker element 'btm', by associating this marker include a special marker element 'btm', by associating this marker
element with the ordered pair compr(btm):=(1,1) and recover this element with the ordered pair compr(btm):=(1,1) and recover this
marker element accordingly. (Note that this corresponds to the case marker element accordingly. (Note that this corresponds to the case
alpha=0 and t=1 above.) The marker element 'btm' can be represented 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 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 ordered pair does not satisfy the defining equation of the curve in
question. question.
Appendix J. Data Conversions Appendix I. Data Conversions
The string over some alphabet S consisting of the symbols x_{l-1}, The string over some alphabet S consisting of the symbols x_{l-1},
x_{l-2}, ..., x_1, x_0 (each in S), in this order, is denoted by x_{l-2}, ..., x_1, x_0 (each in S), in this order, is denoted by
str(x_{l-1}, x_{l-2}, ..., x_1, x_0). The length of this string str(x_{l-1}, x_{l-2}, ..., x_1, x_0). The length of this string
(over S) is the number of symbols it contains (here: l). The empty (over S) is the number of symbols it contains (here: l). The empty
string is the (unique) string of length l=0. string is the (unique) string of length l=0.
The right-concatenation of two strings X and Y (defined over the same The right-concatenation of two strings X and Y (defined over the same
alphabet) is the string Z consisting of the symbols of X (in the same 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 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 of the resulting string Z is the sum of the lengths of X and Y. This
string operation is denoted by Z:=X||Y. The string X is called a string operation is denoted by Z:=X||Y. The string X is called a
prefix of Z; the string Y a postfix. The t-prefix of a string Z of prefix of Z; the string Y a postfix. The t-prefix of a string Z of
length l is its unique prefix X of length t; the t-postfix its unique length l is its unique prefix X of length t; the t-postfix its unique
postfix Y of length t (where we define these notions as well if t is postfix Y of length t (where in both cases t is an integer in the
outside the interval [0,l]: a t-prefix or t-postfix is the empty interval [0,l]). One can define these notions as well if t is
string if t is negative and is the entire string Z if t is larger outside the interval [0,l] by stipulating that a t-prefix or
than l). Sometimes, a t-prefix of a string Z is denoted by trunc- t-postfix is the empty string if t is negative and that it is the
left(Z,t); a t-postfix by trunc-right(Z,t). A string X is called a entire string Z if t is larger than l. Sometimes, a t-prefix of a
substring of Z if it is a prefix of some postfix of Z. The string string Z is denoted by trunc-left(Z,t); a t-postfix by trunc-
resulting from prepending the string Y with X is the string X||Y. right(Z,t). A string X is called a substring of Z if it is a prefix
of some postfix of Z. The string resulting from prepending the
string Y with X is the string X||Y.
An octet is an integer in the interval [0,256). An octet string is a An octet is an integer in the interval [0,256). An octet string is a
string, where the alphabet is the set of all octets. A binary string string, where the alphabet is the set of all octets. A binary string
(or bit string, for short) is a string, where the alphabet is the set (or bit string, for short) is a string, where the alphabet is the set
{0,1}. Note that the length of a string is defined in terms of the {0,1}. Note that the length of a string is defined in terms of the
underlying alphabet, as are the operations in the previous paragraph. 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 1-1 correspondence between bit strings of length l and the There is a 1-1 correspondence between bit strings of length l and
integers in the interval [0, 2^l), where the bit string integers in the interval [0, 2^l), where the bit string
X:=str(x_{l-1}, x_{l-2}, ..., x_1, x_0) corresponds to the integer X:=str(x_{l-1}, x_{l-2}, ..., x_1, x_0) corresponds to the integer
x:=x_{l-1}*2^{l-1} + x_{l-2}*2^{l-2} + ... + x_1*2 + x_0*1. (If l=0, x:=x_{l-1}*2^{l-1} + x_{l-2}*2^{l-2} + ... + x_1*2 + x_0*1. (If l=0,
the empty bit string corresponds to the integer zero.) Note that the empty bit string corresponds to the integer zero.) Note that
while the mapping from bit strings to integers is uniquely defined, while the mapping from bit strings to integers is uniquely defined,
the inverse mapping from integers to bit strings is not, since any the inverse mapping from integers to bit strings is not, since any
non-negative integer smaller than 2^t can be represented as a bit non-negative integer smaller than 2^t can be represented as a bit
string of length at least t (due to leading zero coefficients in base string of length at least t (due to leading zero coefficients in base
2 representation). The latter representation is called tight if the 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 non-negative 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 1-1 correspondence between octet strings of length l and There is a 1-1 correspondence between octet strings of length l and
the integers in the interval [0, 256^l), where the octet string integers in the interval [0, 256^l), where the octet string
X:=str(X_{l-1}, X_{l-2}, ..., X_1, X_0) corresponds to the integer X:=str(X_{l-1}, X_{l-2}, ..., X_1, X_0) corresponds to the integer
x:=X_{l-1}*256^{l-1} + X^{l-2}*256^{l-2} + ... + X_1*256 + X_0*1. x:=X_{l-1}*256^{l-1} + X^{l-2}*256^{l-2} + ... + X_1*256 + X_0*1.
(If l=0, the empty string corresponds to the integer zero.) Note (If l=0, the empty string corresponds to the integer zero.) Note
that while the mapping from octet strings to integers is uniquely that while the mapping from octet strings to integers is uniquely
defined, the inverse mapping from integers to octet strings is not, defined, the inverse mapping from integers to octet strings is not,
since any non-negative integer smaller than 256^t can be represented since any non-negative integer smaller than 256^t can be represented
as an octet string of length at least t (due to leading zero as an octet string of length at least t (due to leading zero
coefficients in base 256 representation). The latter representation coefficients in base 256 representation). The latter representation
is called tight if the octet string representation has minimal is called tight if the octet string representation has minimal
length. This defines the mapping OS2I from octet strings to integers length. This defines the mapping OS2I from octet strings to integers
and the mapping I2OS(x,l) from non-negative integers smaller than and the mapping I2OS(x,l) from non-negative integers smaller than
256^l to octet strings of length l. 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 1-1 correspondence between octet strings of length l and There is a 1-1 correspondence between octet strings of length l and
and bit strings of length 8*l, where the octet string X:=str(X_{l-1}, bit strings of length 8*l, where the octet string X:=str(X_{l-1},
X_{l-2}, ..., X_1, X_0) corresponds to the right-concatenation of the X_{l-2}, ..., X_1, X_0) corresponds to the right-concatenation of the
8-bit strings x_{l-1}, x_{l-2}, ..., x_1, x_0, where each octet X_i 8-bit strings x_{l-1}, x_{l-2}, ..., x_1, x_0, where each octet X_i
corresponds to the 8-bit string x_i according to the mapping of corresponds to the 8-bit string x_i according to the mapping of
Appendix J.1 above. Note that the mapping from octet strings to bit 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 is uniquely defined and so is the inverse mapping from bit
strings to octet strings, if one prepends each bit string with the 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 smallest number of 0 bits so as to result in a bit string of length
divisible by eight (i.e., one uses pre-padding). This defines the divisible by eight (i.e., one uses pre-padding). This defines the
mapping OS2BS from octet strings to bit strings and the corresponding mapping OS2BS from octet strings to bit strings and the corresponding
mapping BS2OS from bit strings to octet strings. 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 1-1 correspondence between elements of a fixed finite There is a 1-1 correspondence between elements of the fixed finite
field GF(q), where q=p^m and m>0, and vectors of length m, with field GF(q), where q:=p^m, where p is a prime number and where m>0,
coefficients in GF(p), where each element x of GF(q) is a vector and vectors of length m, with coefficients in GF(p), where each
(x_{m-1}, x_{m-2}, ..., x_1, x_0) according to the conventions of element x of GF(q) is a vector (x_{m-1}, x_{m-2}, ..., x_1, x_0)
Appendix B.2. In this case, this field element can be uniquely according to the conventions of Appendix B.2. In this case, this
represented by the right-concatenation of the octet strings X_{m-1}, field element can be uniquely represented by the right-concatenation
X_{m-2}, ..., X_1, X_0, where each octet string X_i corresponds to of the octet strings X_{m-1}, X_{m-2}, ..., X_1, X_0, where each
the integer x_i in the interval [0,p-1] according to the mapping of octet string X_i corresponds to the integer x_i in the interval
Appendix J.2 above. Note that both the mapping from field elements [0,p-1] according to the mapping of Appendix I.2 above. Note that
to octet strings and the inverse mapping are only uniquely defined if both the mapping from field elements to octet strings and the inverse
each octet string X_i has the same fixed size (e.g., the smallest mapping from octet strings to field elements are only uniquely
integer l so that 256^l >= p) and if all integers are reduced modulo defined if each octet string X_i has the same fixed size (e.g., the
p. If so, the latter representation is called tight if l is minimal smallest integer l so that 256^l >= p) and if all integers are
so that 256^l >= p. This defines the mapping FE2OS(x,l) from field reduced modulo p. If so, the latter representation is called tight
elements to octet strings and the mapping OS2FE(X,l) from octet if l is minimal so that 256^l >= p. This defines the mapping
strings to field elements, where the underlying field is implicit and FE2OS(x,l) from field elements to octet strings and the mapping
assumed to be known from context. In this case, the octet string has OS2FE(X,l) from octet strings to field elements, where the underlying
length l*m. 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) OS2ZnE)
There is a 1-1 correspondence between elements of a fixed set Z(n) of There is a 1-1 correspondence between elements of the set Z_n of
integers modulo n and integers in the interval [0,n), where each integers modulo n and integers in the interval [0,n), where each
element x can be uniquely represented by the octet string element x of Z_n is uniquely represented by the integer x mod n. In
corresponding to the integer x modulo n according to the mapping of this case, x mod n can be uniquely represented by the octet string X
Appendix J.2 above. Note that both the mapping from elements of Z(n) according to the mapping of Appendix I.2 above. Note that both the
to octet strings and the inverse mapping are only uniquely defined if 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 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, that 256^l >= n) and if all integers are first reduced modulo n. If
the latter representation is called tight if l is minimal so that 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 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 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 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 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 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 are consistent, as are OS2ZnE and OS2FE. This is, however, no longer
the case if n is a strict prime power. the case if n is a strict prime power.
The conversion rules for composite n values are useful, e.g., when The conversion rules for composite n values may be useful, e.g., when
encoding the modulus n of RSA (or elements of any other non-prime set encoding RSA parameters (or elements of any other non-prime size set
Z(n), for that matter). Z_n, for that matter).
J.6. Ordering Conventions I.6. Ordering Conventions
One can consider various representation functions, depending on bit- One can consider various representation functions, depending on bit-
ordering and octet-ordering conventions. ordering and octet-ordering conventions.
The description below makes use of an auxiliary function (the The description below makes use of an auxiliary function (the
reversion function), which we define both for bit strings and octet reversion function), which we define both for bit strings and octet
strings. For a bit string [octet string] X:=str(x_{l-1}, x_{l-2}, strings. For a bit string [octet string] X:=str(x_{l-1}, x_{l-2},
..., x_1, x_0), its reverse is the bit string [octet string] ..., x_1, x_0), its reverse is the bit string [octet string]
X':=rev(X):=str(x_0, x_1, ..., x_{l-2}, x_{l-1}). X':=rev(X):=str(x_0, x_1, ..., x_{l-2}, x_{l-1}).
skipping to change at page 55, line 6 skipping to change at page 60, line 46
bit string or octet string (due to leading zeros). However, tight bit string or octet string (due to leading zeros). However, tight
representations (as defined above) are non-ambiguous. (Note, in representations (as defined above) are non-ambiguous. (Note, in
particular, that tightness implies that elements of GF(q) are always particular, that tightness implies that elements of GF(q) are always
uniquely represented.) uniquely represented.)
Note that elements of a prime field GF(p), where p is a 255-bit prime Note that elements of a prime field GF(p), where p is a 255-bit prime
number, have a tight representation as a 32-byte string, where a number, have a tight representation as a 32-byte string, where a
fixed bit position is always set to zero. (This is the leftmost bit fixed bit position is always set to zero. (This is the leftmost bit
position of this octet string if one follows the MSB/msb position of this octet string if one follows the MSB/msb
representation conventions.) This allows the parity bit of a 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) 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 to be represented by an octet string of the same length. This is
called the squeezed point representation. Obviously, other called the squeezed point representation. Obviously, other
representations (e.g., those of elements of Z(n)) may also have fixed representations (e.g., those of elements of Z_n) may also have fixed
bit values on certain positions, which can be used to squeeze-in bit values in certain positions, which can be used to squeeze-in
additional information. Further details are out of scope. 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 We present some examples of computations using the curves introduced
in this document. In each case, we indicate the values of P, k*P, 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 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 point of the curve in question and where the private key k is the
integer integer
k 45467544759954639344191351164156560595299236761702065033670739677 k 45467544759954639344191351164156560595299236761702065033670739677
691372543056 691372543056
(=0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3 (=0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3
c08d5abd 15e29c50). 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: Pm=(u, v), k*Pm=(u1, v1), and (k+1)*Pm=(u2, v2) with Curve25519:
u 53025657538808013645618620393754461319535915376830819974982289332 u 53025657538808013645618620393754461319535915376830819974982289332
088255623750 088255623750
(=0x753b7566 df35d574 4734142c 9abf931c ea290160 aa75853c (=0x753b7566 df35d574 4734142c 9abf931c ea290160 aa75853c
7f972467 b7f13246). 7f972467 b7f13246).
v 53327798092436462013048370302019946300826511459161905709144645521 v 53327798092436462013048370302019946300826511459161905709144645521
skipping to change at page 56, line 41 skipping to change at page 62, line 35
c2e583cd e6b78564 c2e583cd e6b78564
repr(Pm) 0x4632f1b7 6724977f 3c8575aa 600129ea 1c93bf9a 2c143447 repr(Pm) 0x4632f1b7 6724977f 3c8575aa 600129ea 1c93bf9a 2c143447
74d535df 66753b75; 74d535df 66753b75;
repr(k*Pm) 0xd89cbb88 6864bb23 0a98f767 b0f425ec 0a74168f 8ae158be repr(k*Pm) 0xd89cbb88 6864bb23 0a98f767 b0f425ec 0a74168f 8ae158be
d6d6bdf0 be94f15c, d6d6bdf0 be94f15c,
where the leftmost bit of the rightmost octet indicates the parity of where the leftmost bit of the rightmost octet indicates the parity of
the v-coordinate of the point of Curve25519 in question (which, in the v-coordinate of the point of Curve25519 in question (which, in
this case, are both zero, since v and v1 are even). See Appendix I.2 this case, are both zero, since v and v1 are even). See Appendix H.2
and Appendix J for further detail on (squeezed) point compression. and Appendix I for further detail on (squeezed) point compression.
The scalar representation and (squeezed) point representation The scalar representation and (squeezed) point representation
illustrated above are consistent with the representations specified illustrated above are consistent with the representations specified
in [RFC7748], except that in [RFC7748] only an affine point's in [RFC7748], except that in [RFC7748] only an affine point's
u-coordinate is represented (i.e., the v-coordinate of any point is u-coordinate is represented (i.e., the v-coordinate of any point is
always implicitly assumed to have an even value) and that the always implicitly assumed to have an even value) and that the
representation of the point at infinity is not specified. Another representation of the point at infinity is not specified. Another
difference is that [RFC7748] allows non-unique representations of difference is that [RFC7748] allows non-unique representations of
some elements of GF(p), whereas our representation conventions do not some elements of GF(p), whereas our representation conventions do not
(since tight). (since tight).
skipping to change at page 57, line 22 skipping to change at page 63, line 16
(=0x5844b232 8c4586dc 62f593c5 599c2a8c e61ba893 bb052de6 (=0x5844b232 8c4586dc 62f593c5 599c2a8c e61ba893 bb052de6
77510a42 b3a68a5a) 77510a42 b3a68a5a)
t2 451856098332889407421278004628150814449259902023388533929 t2 451856098332889407421278004628150814449259902023388533929
08848927625430980881 08848927625430980881
(=0x11598452 e65138dc ce948d7e d8f46a18 b640722c 8e170957 (=0x11598452 e65138dc ce948d7e d8f46a18 b640722c 8e170957
751b7729 1b26e663), 751b7729 1b26e663),
where this representation is defined in Appendix L.4 and uses the where this representation is defined in Appendix K.5 and uses the
mapping of Appendix L.3.2 with the default square root function. 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: Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Edwards25519:
x 25301662348702136092602268236183361085863932475593120475382959053 x 25301662348702136092602268236183361085863932475593120475382959053
365387223252 365387223252
(=0x37f03bc0 1070ed12 d3218f8b ba1abb74 fd6b94eb 62033d09 (=0x37f03bc0 1070ed12 d3218f8b ba1abb74 fd6b94eb 62033d09
83851e21 d6a460d4). 83851e21 d6a460d4).
y 54434749145175762798550436656748568411099702168121592090608501578 y 54434749145175762798550436656748568411099702168121592090608501578
skipping to change at page 58, line 32 skipping to change at page 64, line 26
repr(Pe) =0x0bf0c5cd a3a0e069 183c8559 40dc816a e3fa8e6c 4b286bc4 repr(Pe) =0x0bf0c5cd a3a0e069 183c8559 40dc816a e3fa8e6c 4b286bc4
71b72ee6 e79f1a1e; 71b72ee6 e79f1a1e;
repr(k*Pe) =0x3a293d01 e4110a06 b9c2d02a bff7abac 40a918df 69bbfa3d repr(k*Pe) =0x3a293d01 e4110a06 b9c2d02a bff7abac 40a918df 69bbfa3d
f5b5da19 923d6da7, f5b5da19 923d6da7,
where the rightmost bit of the rightmost octet indicates the parity where the rightmost bit of the rightmost octet indicates the parity
of the x-coordinate of the point of Edwards25519 in question (which, of the x-coordinate of the point of Edwards25519 in question (which,
in this case, are zero and one, respectively, since x is even and x1 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. (squeezed) point compression.
The scalar representation and (squeezed) point representation The scalar representation and (squeezed) point representation
illustrated above are fully consistent with the representations illustrated above are fully consistent with the representations
specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032] specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032]
requires unique representations of all elements of GF(p). requires unique representations of all elements of GF(p).
A randomized representation (t1, t2) of the point k*Pe in tight LSB/ A randomized representation (t1, t2) of the point k*Pe in tight LSB/
lsb order is given by lsb order is given by
skipping to change at page 59, line 4 skipping to change at page 64, line 45
lsb order is given by lsb order is given by
t1 577913017083163641949634219017190182170288776648725395935 t1 577913017083163641949634219017190182170288776648725395935
97750427519399254040 97750427519399254040
(=0x181a32c5 10e06dbc ea321882 f3519055 535e289e 8faac654 (=0x181a32c5 10e06dbc ea321882 f3519055 535e289e 8faac654
82e26f61 aded23fe) 82e26f61 aded23fe)
t2 454881407940919718426608573125377401686255068210624245884 t2 454881407940919718426608573125377401686255068210624245884
05479716220480287974 05479716220480287974
(=0x672e36c5 ae353073 cdfac343 e8297b05 1b010d0f 5b1016db (=0x672e36c5 ae353073 cdfac343 e8297b05 1b010d0f 5b1016db
dd4baf54 28068926), dd4baf54 28068926),
where this representation is defined in Appendix L.4 and uses the where this representation is defined in Appendix K.5 and uses the
mapping of Appendix L.3.3 with the default square root function and mapping of Appendix K.3.3 with the default square root function and
underlying isomorphic mapping between Edwards25519 and Curve25519 of underlying isomorphic mapping between Edwards25519 and Curve25519 of
Appendix E.2. 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: Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519:
X 14428294459702615171094958724191825368445920488283965295163094662 X 14428294459702615171094958724191825368445920488283965295163094662
783879239338 783879239338
(=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7 (=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7
2a41cf12 629e56aa). 2a41cf12 629e56aa).
Y 53327798092436462013048370302019946300826511459161905709144645521 Y 53327798092436462013048370302019946300826511459161905709144645521
skipping to change at page 60, line 19 skipping to change at page 66, line 10
c08d5abd 15e29c50; c08d5abd 15e29c50;
repr(Pw) =0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7 repr(Pw) =0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7
2a41cf12 629e56aa; 2a41cf12 629e56aa;
repr(k*Pw) =0x079c3f69 9b688181 69038c35 39c11eb5 96d09f5b 12a242b4 repr(k*Pw) =0x079c3f69 9b688181 69038c35 39c11eb5 96d09f5b 12a242b4
ce660f13 3368c13c, ce660f13 3368c13c,
where the leftmost bit of the leftmost octet indicates the parity of where the leftmost bit of the leftmost octet indicates the parity of
the Y-coordinate of the point of Wei25519 in question (which, in this the Y-coordinate of the point of Wei25519 in question (which, in this
case, are both zero, since Y and Y1 are even). See Appendix I.1 and case, are both zero, since Y and Y1 are even). See Appendix H.1 and
Appendix J for further detail on (squeezed) point compression. Appendix I for further detail on (squeezed) point compression.
The scalar representation is consistent with the representations The scalar representation is consistent with the representations
specified in [SEC1]; the (squeezed) point representation illustrated specified in [SEC1]; the (squeezed) point representation illustrated
above is "new". For completeness, we include a SEC1-consistent above is "new". For completeness, we include a SEC1-consistent
representation of the point Pw in affine format and in compressed representation of the point Pw in affine format and in compressed
format below. format below.
The SEC1-compliant affine representation of the point Pw in tight The SEC1-compliant affine representation of the point Pw in tight
MSB/msb-order is given by MSB/msb-order is given by
skipping to change at page 61, line 5 skipping to change at page 66, line 45
corresponds to the right-concatenation of its X- and Y-coordinates, corresponds to the right-concatenation of its X- and Y-coordinates,
each in tight MSB/msb-order, prepended by the string 0x04, where the each in tight MSB/msb-order, prepended by the string 0x04, where the
reverse procedure is uniquely defined, since elements of GF(p) have a reverse procedure is uniquely defined, since elements of GF(p) have a
unique fixed-size representation. The (squeezed) compressed format unique fixed-size representation. The (squeezed) compressed format
repr(Pw) corresponds to the SEC1-compliant compressed format by repr(Pw) corresponds to the SEC1-compliant compressed format by
extracting the parity bit t from the leftmost bit of the leftmost 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 octet of repr(Pw), replacing the bit position by the value zero, and
prepending the octet string with 0x02 or 0x03, depending on whether prepending the octet string with 0x02 or 0x03, depending on whether
t=0 or t=1, respectively, where the reverse procedure is uniquely t=0 or t=1, respectively, where the reverse procedure is uniquely
defined, since GF(p) is a 255-bit prime field. For further details, defined, since GF(p) is a 255-bit prime field. For further details,
see [SEC1]. see [SEC1]. Note that, due to the bit-size of the prime p, the
squeezed compressed format repr(Pw) is one octet shorter than the
SEC1-compliant compressed format compr(Pw).
A randomized representation (t1, t2) of the point k*Pw in tight MSB/ A randomized representation (t1, t2) of the point k*Pw in tight MSB/
msb order is given by msb order is given by
t1 446363445988889734093446280484122107283059206243307955388 t1 446363445988889734093446280484122107283059206243307955388
84223152228795899590 84223152228795899590
(=0x62af4697 4dd469ac 96c64809 c16c8517 b6a0cee5 40ba0e2e (=0x62af4697 4dd469ac 96c64809 c16c8517 b6a0cee5 40ba0e2e
6dd2b36a fcc75ec6) 6dd2b36a fcc75ec6)
t2 213890166610228613105792710708385961712211281744756216061 t2 213890166610228613105792710708385961712211281744756216061
11930888059603107561 11930888059603107561
(=0x2f49c121 8fed7912 031157ee ae066507 a972320b 6180e267 (=0x2f49c121 8fed7912 031157ee ae066507 a972320b 6180e267
skipping to change at page 61, line 22 skipping to change at page 67, line 16
(=0x62af4697 4dd469ac 96c64809 c16c8517 b6a0cee5 40ba0e2e (=0x62af4697 4dd469ac 96c64809 c16c8517 b6a0cee5 40ba0e2e
6dd2b36a fcc75ec6) 6dd2b36a fcc75ec6)
t2 213890166610228613105792710708385961712211281744756216061 t2 213890166610228613105792710708385961712211281744756216061
11930888059603107561 11930888059603107561
(=0x2f49c121 8fed7912 031157ee ae066507 a972320b 6180e267 (=0x2f49c121 8fed7912 031157ee ae066507 a972320b 6180e267
4025b006 2e67bee9), 4025b006 2e67bee9),
where this representation is defined in Appendix L.4 and uses the where this representation is defined in Appendix K.5 and uses the
mapping of Appendix L.3.1 with the default square root function. 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: Pw2=(X, Y), k*Pw2=(X1, Y1), and (k+1)*Pw2=(X2, Y2) with Wei25519.2:
X 17830493209951148331008014701079988862634531394137235438571836389 X 17830493209951148331008014701079988862634531394137235438571836389
227198459763 227198459763
(=0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c (=0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c
f21c8672 d1ecaf73). f21c8672 d1ecaf73).
Y 21064492012933896105338241940477778461866060481408222122979836206 Y 21064492012933896105338241940477778461866060481408222122979836206
skipping to change at page 62, line 32 skipping to change at page 68, line 26
repr(Pw2) =0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c repr(Pw2) =0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c
f21c8672 d1ecaf73; f21c8672 d1ecaf73;
repr(k*Pw2) =0x0e7986d2 e94354ab 8abd8806 3154536a 4dcf8e6e 65557183 repr(k*Pw2) =0x0e7986d2 e94354ab 8abd8806 3154536a 4dcf8e6e 65557183
e242192d 3b87f4e8, e242192d 3b87f4e8,
where the leftmost bit of the leftmost octet indicates the parity of where the leftmost bit of the leftmost octet indicates the parity of
the Y-coordinate of the point of Wei25519.2 in question (which, in the Y-coordinate of the point of Wei25519.2 in question (which, in
this case, are both zero, since Y and Y1 are even). See 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. point compression.
A randomized representation (t1, t2) of the point k*Pw2 in tight MSB/ A randomized representation (t1, t2) of the point k*Pw2 in tight MSB/
msb order is given by msb order is given by
t1 416669672354928148679758598803660112405431159793278161879 t1 416669672354928148679758598803660112405431159793278161879
36189858804289581274 36189858804289581274
(=0x5c1eaaef 80f9d4af 33c119fc c99acd58 f81e7d69 999c7048 (=0x5c1eaaef 80f9d4af 33c119fc c99acd58 f81e7d69 999c7048
e4043a77 87a930da) e4043a77 87a930da)
t2 361115271162391608083096560179337391059615651279123199921 t2 361115271162391608083096560179337391059615651279123199921
18531180247832114098 18531180247832114098
(=0x4fd66668 e7174775 de44c852 92df8cfe b9832ef8 2570b3b8 (=0x4fd66668 e7174775 de44c852 92df8cfe b9832ef8 2570b3b8
fe5ec21a b2d4b3b2), fe5ec21a b2d4b3b2),
where this representation is defined in Appendix L.4 and uses the where this representation is defined in Appendix K.5 and uses the
mapping of Appendix L.3.1 with the default square root function. 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: Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei25519.-3:
X 14780197759513083469009623947734627174363231692126610860256057394 X 14780197759513083469009623947734627174363231692126610860256057394
455099634096 455099634096
(=0x20ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00 (=0x20ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00
eb4c9272 03ca71b0). eb4c9272 03ca71b0).
Y 45596733430378470319805536538617129933663237960146030424392249401 Y 45596733430378470319805536538617129933663237960146030424392249401
952949482817 952949482817
(=0x64ced628 e982648e 4bfcf30c 71c4d267 ba48b0ce fee20062 (=0x64ced628 e982648e 4bfcf30c 71c4d267 ba48b0ce fee20062
b43ef4c9 73f7b541). b43ef4c9 73f7b541).
X1 47362979975244556396292400751828272600887612546997532158738958926 X1 47362979975244556396292400751828272600887612546997532158738958926
skipping to change at page 63, line 30 skipping to change at page 69, line 22
X1 47362979975244556396292400751828272600887612546997532158738958926 X1 47362979975244556396292400751828272600887612546997532158738958926
60745725532 60745725532
(=0x0a78a650 a39995ef dcf4de88 940d4ce9 5b2ca35c c5d70e06 (=0x0a78a650 a39995ef dcf4de88 940d4ce9 5b2ca35c c5d70e06
63b8455e 2e04e65c). 63b8455e 2e04e65c).
Y1 30318112837157047703426636957515037640997356617656007157255559136 Y1 30318112837157047703426636957515037640997356617656007157255559136
153389790354 153389790354
(=0x64ced628 e982648e 4bfcf30c 71c4d267 ba48b0ce fee20062 (=0x4307719a 20d08741 58d5889e 8c8ec27e 246b0342 55f8fd62
b43ef4c9 73f7b541). dbc9ca09 e79c7492).
X2 23778942085873786433506063022059853212880296499622328201295446580 X2 23778942085873786433506063022059853212880296499622328201295446580
293591664363 293591664363
(=0x3492677e 6ae9d1c3 e08f908b 61033f3d 4e8322c9 fba6da81 (=0x3492677e 6ae9d1c3 e08f908b 61033f3d 4e8322c9 fba6da81
2c95b067 9b1486eb). 2c95b067 9b1486eb).
Y2 44846366394651736248316749170687053272682847823018287439056537991 Y2 44846366394651736248316749170687053272682847823018287439056537991
969511150494 969511150494
skipping to change at page 64, line 11 skipping to change at page 70, line 4
repr(Pw3) =0xa0ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00 repr(Pw3) =0xa0ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00
eb4c9272 03ca71b0; eb4c9272 03ca71b0;
repr(k*Pw3) =0x0a78a650 a39995ef dcf4de88 940d4ce9 5b2ca35c c5d70e06 repr(k*Pw3) =0x0a78a650 a39995ef dcf4de88 940d4ce9 5b2ca35c c5d70e06
63b8455e 2e04e65c, 63b8455e 2e04e65c,
where the leftmost bit of the leftmost octet indicates the parity of where the leftmost bit of the leftmost octet indicates the parity of
the Y-coordinate of the point of Wei25519.-3 in question (which, in the Y-coordinate of the point of Wei25519.-3 in question (which, in
this case, are one and zero, respectively, since Y is odd and Y1 is 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. (squeezed) point compression.
A randomized representation (t1, t2) of the point k*Pw3 in tight MSB/ A randomized representation (t1, t2) of the point k*Pw3 in tight MSB/
msb order is given by msb order is given by
t1 573714937613596601525680684642155667097217474964816246889 t1 573714937613596601525680684642155667097217474964816246889
88981227297409008259 88981227297409008259
(=0x7ed71d5f 566d2259 99bdb404 bfb9d6cf d2e86ccb 1894d4a6 (=0x7ed71d5f 566d2259 99bdb404 bfb9d6cf d2e86ccb 1894d4a6
c75e3c69 e5eb0283) c75e3c69 e5eb0283)
t2 269945781324580189815142015663892935722419453863927287235 t2 269945781324580189815142015663892935722419453863927287235
57891665397640090729 57891665397640090729
(=0x3bae63c8 70f60de0 c2e35f94 d24220f1 bb6efd00 37625869 (=0x3bae63c8 70f60de0 c2e35f94 d24220f1 bb6efd00 37625869
f84923de ff4c5469), f84923de ff4c5469),
where this representation is defined in Appendix L.4 and uses the where this representation is defined in Appendix K.5 and uses the
mapping of Appendix L.3.1 with the default square root function. 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 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. how to compute square roots for other values of q are out of scope.
If square roots are easy to compute in GF(q), then so are these in If square roots are easy to compute in GF(q), then so are these in
GF(q^2). GF(q^2).
L.1.1. Square Roots in GF(q), where q = 3 (mod 4) 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^{(q-3)/4}, then y is a If y is a nonzero element of GF(q) and z:=y^{(q-3)/4}, then y is a
square in GF(q) only if y*z^2=1. If y*z^2=1, z is a square root of square in GF(q) only if y*z^2=1. If y*z^2=1, z is a square root of
1/y and y*z is a square root of y in GF(q). 1/y and y*z is a square root of y in GF(q).
L.1.2. Square Roots in GF(q), where q = 5 (mod 8) 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^{z-5)/8}, then y is a If y is a nonzero element of GF(q) and z:=y^{(q-5)/8}, then y is a
square in GF(q) only if y^2*z^4=1. 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 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); 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 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., Here, i is an element of GF(q) for which i^2=-1 (e.g.,
i:=2^{(q-1)/4}). This field element can be precomputed. i:=2^{(q-1)/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 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 (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 [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. 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 The inverse of a nonzero element y of GF(q) can be computed as
1/y:=y^{q-2} (since y^{q-1}=1). 1/y:=y^{q-2} (since y^{q-1}=1).
Further details are out of scope. If inverses are easy to compute in If inverses are easy to compute in GF(q), then so are these in
GF(q), then so are these in GF(q^2). GF(q^2). Further details are out of scope.
The inverses of two nonzero elements y1 and y2 of GF(q) can be 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 computed by first computing the inverse z of y1*y2 and by
subsequently computing y2*z=:1/y1 and y1*z=:1/y2. 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 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 points of a Weierstrass curve (see Appendix K.3.1), to points of a
Montgomery curve (see Appendix L.3.2), or to points of a twisted Montgomery curve (see Appendix K.3.2), or to points of a twisted
Edwards curve (see Appendix L.3.3), under some mild conditions on the Edwards curve (see Appendix K.3.3), under some mild conditions on the
domain parameters. Full details on mappings that apply if these domain parameters. Full details on mappings that apply if these
conditions are not satisfied are out of scope. 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 description below assumes that the domain parameters a and b of
the Weierstrass curve W_{a,b} are nonzero. For ease of exposition, 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 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).) 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 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 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. solution of the equation f(t*X)=t^3*f(X) and is nonzero.
Consequently, either X or X':=t*X is the x-coordinate of an affine Consequently, either X or X':=t*X is the x-coordinate of an affine
skipping to change at page 66, line 16 skipping to change at page 72, line 16
to the point P(t):=(X, Y); 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 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'). mapped to the point P(t):=(X', -Y').
Formally, this mapping is not properly defined, since a nonzero 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 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 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" 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 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). (henceforth called the default square root function).
If -1 is not a square in GF(q), this element is mapped to the point If -1 is not a square in GF(q), this element is mapped to the point
at infinity O of W_{a,b}. at infinity O of W_{a,b}.
The set of points of W_{a,b} that arises this way has size roughly 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 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. 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 NOTE 1: If -1 is not a square in GF(q), the mapping above yields the
skipping to change at page 66, line 41 skipping to change at page 72, line 41
are out of scope. are out of scope.
NOTE 2: The description above assumes that the domain parameters a 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, 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 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 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 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 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 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 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) example, one can show that if a is zero and if -4*b is a cube in
(such as is the case with, e.g., the "BitCoin" curve secp256k1 GF(q) (such as is the case with, e.g., the "BitCoin" curve secp256k1
[SEC2]), this curve is 3-isogenous to a curve with this property and [SEC2]), this curve is 3-isogenous to a curve with this property and
the strategy above applies (for an example with secp256k1, see 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 The description below assumes that the domain parameter A of the
Montgomery curve M_{A,B} is nonzero. For ease of exposition, we 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 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).) 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 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 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 solution of the equation f(t*u)=t^3*f(u). Consequently, either u or
u':=t*u is the u-coordinate of an affine point of M{A,B}, depending u':=t*u is the u-coordinate of an affine point of M{A,B}, depending
on whether f(u)/B is a square in GF(q). on whether f(u)/B is a square in GF(q).
skipping to change at page 67, line 21 skipping to change at page 73, line 21
mapped to the point P(t):=(u, v); 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 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'). t is mapped to the point P(t):=(u', -v').
As before, formally, this mapping is not properly defined, since a 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 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 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" 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 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). (henceforth called the default square root function).
If -1 is not a square in GF(q), this element is mapped to the point If -1 is not a square in GF(q), this element is mapped to the point
at infinity O of M_{A,B}. at infinity O of M_{A,B}.
The set of points of M_{A,B} that arises this way has size roughly 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 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. 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 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 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 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. point G of M_{A,B} and leaving the remainder of the mapping the same.
Suitability of such a modification is application-specific. Details Suitability of such a modification is application-specific. Details
are out of scope. are out of scope.
NOTE 2: The description above assumes that the domain parameter A of 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 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 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 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 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 in GF(q) and f(-t)=-f(t)). In this case, this construction can be
extended to all elements t of GF(q) and, if so, yields a 1-1 mapping extended to all elements t of GF(q) and, if so, yields a 1-1 mapping
between GF(q) and all affine curve points. 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 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, 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 the Weierstrass curve W_{a,b} and where one subsequently uses the
isomorphic mapping between twisted Edwards curves and Weierstrass isomorphic mapping between twisted Edwards curves and Weierstrass
curves of Appendix D.3 to arrive at a point of E_{a,d}. Another 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 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 curve M_{A,B} and where one subsequently uses the isomorphic mapping
between twisted Edwards curves and Montgomery curves of Appendix D.1 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 to arrive at a point of E_{a,d}. Obviously, one can use function
composition (now using the respective pre-images - if these exist) to composition (now using the respective pre-images - if these exist) to
realize the pre-images of either mapping. realize the pre-images of either mapping.
L.4. Randomized Representation of Curve Points K.4. Mappings to High-Order Curve Points
The mappings of Appendix L.3.1, Appendix L.3.2, and Appendix L.3.3 Appendix K.3 described how one can map elements of GF(q) that are not
allow one to represent a curve point Q as a specific element of a square in GF(q) to points of a Weierstrass curve, to points of a
GF(q), provided this point arises as a point in the range of the Montgomery curve, or to points of a twisted Edwards curve, under some
mapping at hand. For Montgomery curves and twisted Edwards curves, mild conditions on the domain parameters. Below, we use the mappings
this covers roughly half of the curve points; for Weierstrass curves, of that appendix and the parity function par(.) specified in
roughly 3/8 of the curve points. One can extend the mappings above, Appendix H to construct mappings to high-order curve points only
by mapping a pair (t1, t2) of inputs to the point Q:=P2(t1, (i.e., mappings that avoid points in the small subgroup, see
t2):=P(t1) + P(t2). In this case, each curve point has roughly q/4 Appendix B.1). We consider mappings to high-order points of a
representations as an ordered pair (t1, t2) on average. In fact, one Weierstrass curve (see Appendix K.4.1), to high-order points of a
can show that if the input pairs are generated uniformly at random, Montgomery curve (see Appendix K.4.2), and to high-order points of a
then the corresponding curve points follow a distribution that is twisted Edwards curve (see Appendix K.4.3). As before, full details
also (statistically indistinguishable from) a uniform distribution, on mappings that apply if the mild conditions on the domain
and vice-versa. Here, each pair (t1, t2) deterministically yields a parameters are not satisfied are out of scope.
curve point, whereas for each curve point Q, a randomized algorithm
yields an ordered pair (t1, t2) of pre-images of Q, where the K.4.1. Mapping to High-Order 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 so-called "curve offset") alluded to above indeed exists. In
cases of practical interest that we are aware of, this is indeed the
case (see, e.g., 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 X-coordinates of P0 and P(t) and the product of their
Y-coordinates. (Here, observe that Y0*Y is a square root of
f(X0)*f(X).) Thus, Q(t,s) can be computed without the need to fully
compute P(t).
K.4.2. Mapping to High-Order 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 so-called "curve offset") alluded to above indeed exists. In
cases of practical interest that we are aware of, this is indeed the
case (see, e.g., 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 u-coordinates of P0 and P(t) and the product of their
v-coordinates. (Here, observe that B*v0*v is a square root of
f(u0)*f(u).) Thus, Q(t,s) can be computed without the need to fully
compute P(t).
+----------------------------+------------------------+
| Curve | Fixed curve offset P0 |
+----------------------------+------------------------+
| NIST P-224 [FIPS-186-4] | Base point (Gx,Gy) |
| NIST P-256 [FIPS-186-4] | P0:=(0,y) with y even |
| NIST P-384 [FIPS-186-4] | P0:=(0,y) with y even |
| NIST P-521 [FIPS-186-4] | P0:=(0,y) with y even |
| Brainpool224r1 [RFC5639] | Base point (Gx, Gy) |
| Brainpool256r1 [RFC5639] | Base point (Gx, Gy) |
| Brainpool320r1 [RFC5639] | Base point (Gx, Gy) |
| Brainpool384r1 [RFC5639] | Base point (Gx, Gy) |
| Brainpool512r1 [RFC5639] | P0:=(3,y), y even |
| Curve25519 [RFC7748] | P0:=(90,v), v even |
| Curve448 [RFC7748] | P0:=(50,v), v even |
| Wei25519 [Appendix E.3] | P0:=(3,y), y even |
| Wei25519.2 [Appendix G.3] | P0:=(244,y), y even |
| Wei25519.-3 [Appendix G.3] | P0:=(41,y), y even |
| secp256k1.m [Appendix L.3] | P0:=(0,y), y even |
+----------------------------+------------------------+
Table 1: Curve offsets P0 for mappings that avoid low-order points
K.4.3. Mapping to High-Order 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 pre-images -
if these exist) to realize the pre-images 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 vice-versa. Here, each pair (t1, t2)
deterministically yields a curve point, whereas for each curve point
Q, a randomized algorithm yields an ordered pair (t1, t2) of pre-
images of Q, where the expected number of randomized pre-images one
has to try is small (four if one uses the mapping of Appendix K.3.1;
two if one uses the mapping of Appendix K.3.2). For further details,
see Algorithm 1 of [Tibouchi].
Similar properties hold if one uses the mappings of Appendix K.4
(rather than those of Appendix K.3): in this case, the mapping allows
one to represent a curve point Q as a specific element (t,s) of
GF(q)x{0,1}, provided this point arises as a point in the range of
the mapping at hand. For Montgomery curves and twisted Edwards
curves, this covers roughly half of the curve points; for Weierstrass
curves, roughly 3/8 of the curve points. One can extend the mappings
above, by mapping a pair ((t1,s1), (t2,s2)) of inputs to the point
Q:=Q2((t1,s1), (t2,s2)):=Q(t1,s1) - Q(t2,s2). In this case, each
curve point has roughly q representations as an ordered pair
((t1,s1), (t2,s2)) on average. In fact, one can show that if the
input pairs are generated uniformly at random, then the corresponding
curve points follow a distribution that is also (statistically
indistinguishable from) a uniform distribution, and vice-versa.
Here, each pair ((t1,s1), (t2,s2)) deterministically yields a curve
point, whereas for each curve point Q, a randomized algorithm yields
an ordered pair ((t1,s1), (t2,s2)) of pre-images of Q, where the
expected number of randomized pre-images one has to try is small expected number of randomized pre-images one has to try is small
(four if one uses the mapping of Appendix L.3.1; two if one uses the (four if one uses the mapping of Appendix K.4.1; two if one uses the
mapping of Appendix L.3.2). For further details, see Algorithm 1 of mapping of Appendix K.4.2). Further details are out of scope.
[Tibouchi].
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 high-order curve points described in Appendix K.4. Note
that Q2((t1,s1), (t2,s2)) assumes all values (+/-) P(t1) (+/-) P(t2)
if one considers all possible values for the binary digits s1 and s2.
(This, thereby, includes the value P2(t1, t2).)
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 high-order curve points can be extended
further to one that operates on all elements of GF(q) by mapping 0 to
any fixed high-order point of the curve in question (e.g., to the
fixed "curve offset" P0 of this curve [henceforth called the default
completed mapping]). Depending on application-specific criteria, yet
other function compositions may be preferred. For the first mapping
above, one can use a similar function composition, where one simply
drops the binary digit s and maps 0 to the point at infinity or any
other suitable curve point. Further details are out of scope.
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 The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined
over the prime field GF(p), with p:=2^256-2^32-2^9-2^8-2^7-2^6-2^4-1, over the prime field GF(p), with p:=2^256-2^32-2^9-2^8-2^7-2^6-2^4-1,
where a:=0 and b:=7. This curve has order h*n, where h=1 and where n 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, 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, whereas b is not. The quadratic twist of this curve has order h1*n1,
where h1 is a 37-bit integer and where n1 is a prime number. For where h1 is a 37-bit integer and where n1 is a prime number. For
this curve, the base point is the point (GX, GY). this curve, the base point is the point (GX, GY).
The curve secp256k1 is 3-isogenous to the Weierstrass curve The curve secp256k1 is 3-isogenous to the Weierstrass curve
secp256k1.m defined over GF(p), which has nonzero domain parameters a 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 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 as specified in Appendix L.3 and where the related mappings are as
specified in Appendix M.2. 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 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 (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 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 to the point at infinity of secp256k1.m. Under this isogenous
mapping, the base point (GX,GY) of secp256k1 corresponds to the base 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 (GmX,GmY) of secp256k1.m. The dual isogeny maps the affine
point (X',Y') of secp256k1.m to the affine point 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', (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 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 secp256k1.m to the point at infinity O of secp256k1. Under this dual
isogenous mapping, the base point (GmX, GmY) of secp256k1.m isogenous mapping, the base point (GmX, GmY) of secp256k1.m
corresponds to a multiple of the base point (GX, GY) of secp256k1, 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 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 description in Appendix F.4). Note that this isogenous map (and its
dual) primarily involves the evaluation of three fixed polynomials dual) primarily involves the evaluation of three fixed polynomials
involving the x-coordinate, which takes roughly 10 modular involving the x-coordinate, which takes roughly 10 modular
multiplications (or less than 1% relative incremental cost compared multiplications (or less than 1% relative incremental cost compared
to the cost of an elliptic curve scalar multiplication). 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 The parameters of the curve sec256k1 and the corresponding
3-isogenous curve sec256k1.m are as indicated below. Here, the 3-isogenous curve sec256k1.m are as indicated below. Here, the
domain parameters of the curve secp256k1 are as specified in [SEC2]; domain parameters of the curve secp256k1 are as specified in [SEC2];
the domain parameters of secp256k1.m are "new". the domain parameters of secp256k1.m are "new".
General parameters (for all curves): General parameters (for all curves):
p 2^256-2^32-2^9-2^8-2^7-2^6-2^4-1 p 2^256-2^32-2^9-2^8-2^7-2^6-2^4-1
skipping to change at page 71, line 7 skipping to change at page 81, line 4
b 1771 (=0x06eb) b 1771 (=0x06eb)
GmX 26591621185618668069038227574782692264471832498547635565821216767 GmX 26591621185618668069038227574782692264471832498547635565821216767
730887659845 730887659845
(=0x3aca5300 959fa1d0 baf78dcf f77a616f 395e586d 67aced0a (=0x3aca5300 959fa1d0 baf78dcf f77a616f 395e586d 67aced0a
88798129 0c279145) 88798129 0c279145)
GmY 67622516283223102233819216063319565850973524550533340939716651159 GmY 67622516283223102233819216063319565850973524550533340939716651159
860372686848 860372686848
(=0x9580fce5 3a170f4f b744579f f3d62086 12cd6a23 3e2de237 (=0x9580fce5 3a170f4f b744579f f3d62086 12cd6a23 3e2de237
f976c6a7 8611c800) f976c6a7 8611c800)
M.4. Isogeny Details L.4. Isogeny Details
The isogeny and dual isogeny are both isogenies with degree l=3. 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', 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 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 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 isogeny). For each polynomial in variable x, the coefficients are
tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in
hexadecimal format. 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 0 0x54
1 0xa4d89db3ed06c81e6143ec2eca9f761d8d17260dc229e1da1f73f714506872a9 1 0xa4d89db3ed06c81e6143ec2eca9f761d8d17260dc229e1da1f73f714506872a9
2 0xcc58ffccbd9febb4a66222c7d1311d988d88c0624bcd68ec4c758a8e67dfd99b 2 0xcc58ffccbd9febb4a66222c7d1311d988d88c0624bcd68ec4c758a8e67dfd99b
3 0x01 3 0x01
M.4.1.2. Coefficients of v(x) L.4.1.2. Coefficients of v(x)
0 0x1c 0 0x1c
1 0x94c7bc69befd17f2fae2e3ebf24df1f355d181fa1a8056103ba9baad4b40f029 1 0x94c7bc69befd17f2fae2e3ebf24df1f355d181fa1a8056103ba9baad4b40f029
2 0xb2857fb31c6fe18ef993342bb9c9ac64d44d209371b41d6272b04fd61bcfc851 2 0xb2857fb31c6fe18ef993342bb9c9ac64d44d209371b41d6272b04fd61bcfc851
3 0x01 3 0x01
M.4.1.3. Coefficients of w(x) L.4.1.3. Coefficients of w(x)
0 0xe62c7fe65ecff5da53311163e8988ecc46c4603125e6b476263ac546b3efeae5 0 0xe62c7fe65ecff5da53311163e8988ecc46c4603125e6b476263ac546b3efeae5
1 0x01 1 0x01
M.4.2. Dual Isogeny Parameters L.4.2. Dual Isogeny Parameters
L.4.2.1. Coefficients of u'(x)
M.4.2.1. Coefficients of u'(x)
0 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa8c7 0 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa8c7
1 0x44cd5cd7ce55a801725891578fbe7356bd936355fd0e2f538797cecff7a37244 1 0x44cd5cd7ce55a801725891578fbe7356bd936355fd0e2f538797cecff7a37244
2 0x668d0011162006c3c889f4680f9a4b77d0d26a89e6bb87b13bd8d1cfdd600a41 2 0x668d0011162006c3c889f4680f9a4b77d0d26a89e6bb87b13bd8d1cfdd600a41
3 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c 3 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c
M.4.2.2. Coefficients of v'(x) L.4.2.2. Coefficients of v'(x)
0 0x4bda12f684bda12f684bda12f684bda12f684bda12f684bda12f684b8e38e23c 0 0x4bda12f684bda12f684bda12f684bda12f684bda12f684bda12f684b8e38e23c
1 0x519ba9c1f48f68054def6a410f0fa6e8b71c6c3b4a8958324681f6508c01fada 1 0x519ba9c1f48f68054def6a410f0fa6e8b71c6c3b4a8958324681f6508c01fada
2 0xb34680088b100361e444fa3407cd25bbe8693544f35dc3d89dec68e76eb00338 2 0xb34680088b100361e444fa3407cd25bbe8693544f35dc3d89dec68e76eb00338
3 0x2f684bda12f684bda12f684bda12f684bda12f684bda12f684bda12f38e38d84 3 0x2f684bda12f684bda12f684bda12f684bda12f684bda12f684bda12f38e38d84
M.4.2.3. Coefficients of w'(x) L.4.2.3. Coefficients of w'(x)
0 0x4d7a804ce3901e71066ccbd44636539b2bb2df6c8e4be29d8d4fb028e43033de 0 0x4d7a804ce3901e71066ccbd44636539b2bb2df6c8e4be29d8d4fb028e43033de
1 0x01 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^2-4 is not a square in GF(p),
whereas A-2 is. The quadratic twist of this curve has order h1*n1,
where h1=4 and where n1 is a prime number. For this curve, the base
point is the point (Gu, Gv), where Gu=5 and where Gv is an even
integer in the interval [0, p-1].
This curve has the same group structure as (is "isomorphic" to) the
twisted Edwards curve E_{a,d} defined over GF(p), with as base point
the point (Gx, Gy), where parameters are as specified in
Appendix M.3. This curve is denoted as Ed448. For this curve, the
parameter a is a square in GF(p), whereas d is not, so the group laws
of Appendix C.3 apply.
The curve is also isomorphic to the elliptic curve W_{a,b} in short-
Weierstrass form defined over GF(p), with as base point the point
(GX, GY), where parameters are as specified in Appendix M.3. This
curve is denoted as Wei448.
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 integer-only arithmetic as a shift of -(p-A)/3 for
the isomorphic mapping and a shift of (p-A)/3 for its inverse, where
delta=(p-A)/3 is the element of GF(p) defined by
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,p-1].)
The curve Ed448 is isomorphic to the curve Curve448, where the base
point (Gu, Gv) of Curve448 corresponds to the base point (Gx,Gy) of
Ed448 and where the point at infinity and the point (0,0) of order
two of Curve448 correspond to, respectively, the point (0, 1) and the
point (0, -1) of order two of Ed448 and where each other point (u, v)
of Curve448 corresponds to the point (c*u/v, (u+1)/(u-1)) of Ed448,
where c is the element of GF(p) defined by
c sqrt((A-2)/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)/((y-1)*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)/(y-1)+A/3, c*(y+1)/((y-1)*x)) of Wei448, where c was
defined before. (Here, we used the mapping of Appendix D.3.) The
inverse mapping from Wei448 to Ed448 is defined by mapping the point
at infinity O and the point (A/3, 0) of order two of Wei448 to,
respectively, the identity element (0,1) and the point (0,-1) of
order two of Ed448 and having each other point (X, Y) of Wei448
correspond to the point (c*(X-A/3)/Y, (X-A/3+1)/(X-A/3-1)) of Ed448.
Note that these mappings can be easily realized if points are
represented in projective coordinates, using a few field
multiplications only, thus allowing switching between alternative
curve representations with negligible relative incremental cost.
M.3. Domain Parameters
The parameters of the Montgomery curve and the corresponding
isomorphic curves in twisted Edwards curve and short-Weierstrass form
are as indicated below. Here, the domain parameters of the
Montgomery curve Curve448 and of the twisted Edwards curve Ed448 are
as specified in [RFC7748]; the domain parameters of Wei448 are "new".
IMPORTANT NOTE: the supposed base point of Ed448 specified in
[RFC7748] is incorrect, since it has order 2*n, and - in the notation
below - that point is the point (Gx,-Gy)=-(Gx, Gy)+(0,-1). The
birational map in that document is also incorrect.
General parameters (for all curve models):
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 curve-specific 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 curve-specific parameters (for Ed448):
a 1 (0x01)
d 39082/39081 = (A+2)/(A-2)
(=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 curve-specific 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 Y-coordinate is
nonzero (i.e., each point with order larger than two) corresponds to
the point (X',Y'):=(X1*t^2,Y1*t^3) of Wei448.-3, where
(X1,Y1)=(u(X)/w(X),Y*v(X)/w(X)^2), where u, v, and w are the
polynomials with coefficients in GF(p) as defined in Appendix N.4.1
and where t is the element of GF(p) defined by
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 x-coordinate, which takes only a few
modular multiplications (less than 0.5% relative incremental cost
compared to the cost of an elliptic curve scalar multiplication).
Each point (x1,y1) of Edwards448 corresponds to the point (x,y) of
Ed448, where
x = c*x1*y1/(1-d1*x1^2*y1^2) = c*x1*y1/(2-x1^2-y1^2) and
y =(1 + d1*x1^2*y1^2)/(y1^2-x1^2) = -(x1^2+y1^2)/(x1^2-y1^2).
(Here, we used the 4-isogenous 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^2-x^2) and
y1 = (1 - d*x^2*y^2)/(1 + d*x^2*y^2) = (2-x^2-y^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*(2-x1^2-y1^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^2-1)*v/((u^2-1)^2+4*v^2) and
y1 = u*((u^2-1)^2-4*v^2)/(2*(u^2+1)*v^2-u*(u^2-1)^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 curve-specific 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 curve-specific 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 curve-specific parameters (for Edwards448):
a 1 (0x01)
d1 -39081 = -(A-2)/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 v-coordinate of k*Pm can be
indirectly computed from the u-coordinates of Pm, k*Pm, and (k+1)*Pm,
and the v-coordinate of Pm, which allows computation of the entire
point k*Pm (and not just its u-coordinate) if k*Pm is computed using
the Montgomery ladder (as, e.g., [RFC7748] recommends), since that
algorithm computes both u1 and u2 and the v-coordinate of the point
Pm may be available from context.
The representation of k and the compressed representations of Pm and
k*Pm in tight LSB/msb-order are given by
repr(k) 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 v-coordinate 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
u-coordinate is represented (i.e., the v-coordinate of any point is
always implicitly assumed to have an even value) and that the
representation of the point at infinity is not specified. (Note that
due to the bit-size of the prime p, the lossless representation
requires an additional octet compared to the lossy representation
without v-coordinate.) Another difference is that [RFC7748] allows
non-unique representations of some elements of GF(p), whereas our
representation conventions do not (since tight).
A randomized representation (t1, t2) of the point k*Pm in tight LSB/
msb order is given by
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/lsb-order 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 x-coordinate 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/msb-order 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 Y-coordinate 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 SEC1-consistent
representation of the point Pw in affine format and in compressed
format below.
The SEC1-compliant affine representation of the point Pw in tight
MSB/msb-order is given by
aff(Pw) =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 SEC1-compliant compressed representation of the point Pw
in tight MSB/msb-order is given by
compr(Pw) =0x03 6663c64e 5b9a1f6d cbee3f5f 839b7dd8 6f53cc3e
0a01dab3 e4a8314e 8d54be2a 4d63380b 692381bb ed7339fd
dca7b0cd a80166fe 18c15250.
The SEC1-compliant uncompressed format aff(Pw) of an affine point Pw
corresponds to the right-concatenation of its X- and Y-coordinates,
each in tight MSB/msb-order, prepended by the string 0x04, where the
reverse procedure is uniquely defined, since elements of GF(p) have a
unique fixed-size representation. The (squeezed) compressed format
repr(Pw) corresponds to the SEC1-compliant compressed format by
extracting the parity bit t from the leftmost bit of the leftmost
octet of repr(Pw), and replacing this leftmost octet with 0x02 or
0x03, depending on whether t=0 or t=1, respectively, where the
reverse procedure is uniquely defined. For further details, see
[SEC1]. Note that, due to the bit-size of the prime p, the squeezed
compressed format repr(Pw) and the SEC1-compliant compressed format
compr(Pw) have the same size.
A randomized representation (t1, t2) of the point k*Pw in tight MSB/
msb order is given by
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/msb-order 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 Y-coordinate of the point of Wei448.-3 in question (which, in
this case, are one and zero, respectively, since Y is odd and Y1 is
even). See 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/lsb-order 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 x-coordinate 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 4-isogenous mapping between Edwards448 and Curve448 of
Appendix N.2.
Author's Address Author's Address
Rene Struik Rene Struik
Struik Security Consultancy Struik Security Consultancy
Email: rstruik.ext@gmail.com Email: rstruik.ext@gmail.com
 End of changes. 208 change blocks. 
525 lines changed or deleted 2041 lines changed or added

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