draft-ietf-lwig-curve-representations-10.txt   draft-ietf-lwig-curve-representations-11.txt 
lwig R. Struik lwig R. Struik
Internet-Draft Struik Security Consultancy Internet-Draft Struik Security Consultancy
Intended status: Informational April 23, 2020 Intended status: Informational July 13, 2020
Expires: October 25, 2020 Expires: January 14, 2021
Alternative Elliptic Curve Representations Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-10 draft-ietf-lwig-curve-representations-11
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. We also provide extensive background using NIST prime curves. We also provide extensive background
material that may be useful for implementers of elliptic curve material that may be useful for implementers of elliptic curve
cryptography. cryptography.
skipping to change at page 1, line 44 skipping to change at page 1, line 44
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 October 25, 2020. This Internet-Draft will expire on January 14, 2021.
Copyright Notice Copyright Notice
Copyright (c) 2020 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
skipping to change at page 2, line 34 skipping to change at page 2, line 34
3. Use of Representation Switches . . . . . . . . . . . . . . . 6 3. Use of Representation Switches . . . . . . . . . . . . . . . 6
4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 7 4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 7
4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 7 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 7
4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 8 4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 8
4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 8 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 8
5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 9 5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 9
5.2. Representation Conventions . . . . . . . . . . . . . . . 9 5.2. Representation Conventions . . . . . . . . . . . . . . . 9
5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 10 5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 10
6. Implementation Considerations . . . . . . . . . . . . . . . . 10 6. Implementation Considerations . . . . . . . . . . . . . . . . 11
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 12 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 12
8. Security Considerations . . . . . . . . . . . . . . . . . . . 12 8. Security Considerations . . . . . . . . . . . . . . . . . . . 13
9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 13 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 13
10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 14 10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 14
10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 14 10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 14
10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 14 10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 14
10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 15 10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 15
10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 16 10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 16
10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 17 10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 17
10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 17 10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 18
10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 18 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 18
10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 19 10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 19
10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 19 10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 20
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20
11.1. IANA Considerations for Wei25519 . . . . . . . . . . . . 20 11.1. IANA Considerations for Wei25519 . . . . . . . . . . . . 20
11.1.1. COSE Elliptic Curves Registration . . . . . . . . . 20 11.1.1. COSE Elliptic Curves Registration . . . . . . . . . 20
11.1.2. COSE Algorithms Registration (1/2) . . . . . . . . . 21 11.1.2. COSE Algorithms Registration (1/2) . . . . . . . . . 21
11.1.3. COSE Algorithms Registration (2/2) . . . . . . . . . 21 11.1.3. COSE Algorithms Registration (2/2) . . . . . . . . . 21
11.1.4. JOSE Elliptic Curves Registration . . . . . . . . . 21 11.1.4. JOSE Elliptic Curves Registration . . . . . . . . . 22
11.1.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 22 11.1.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 22
11.1.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 22 11.1.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 22
11.2. IANA Considerations for Wei448 . . . . . . . . . . . . . 23 11.2. IANA Considerations for Wei448 . . . . . . . . . . . . . 23
11.2.1. COSE Elliptic Curves Registration . . . . . . . . . 23 11.2.1. COSE Elliptic Curves Registration . . . . . . . . . 23
11.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 23 11.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 23
11.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 23 11.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 24
11.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 24 11.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 24
11.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 24 11.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 24
11.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 25 11.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 25
12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 25 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 25
13. References . . . . . . . . . . . . . . . . . . . . . . . . . 25 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 26
13.1. Normative References . . . . . . . . . . . . . . . . . . 25 13.1. Normative References . . . . . . . . . . . . . . . . . . 26
13.2. Informative References . . . . . . . . . . . . . . . . . 28 13.2. Informative References . . . . . . . . . . . . . . . . . 28
Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 29 Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 30
A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 29 A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 30
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 30 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 30
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 30 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 30
Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 30 Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 31
B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 30 B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 31
B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 32 B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 33
Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 33 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 34
C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 33 C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 34
C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 34 C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 35
C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 35 C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 36
Appendix D. Relationship Between Curve Models . . . . . . . . . 36 Appendix D. Relationships Between Curve Models . . . . . . . . . 37
D.1. Mapping between Twisted Edwards Curves and Montgomery D.1. Mapping between Twisted Edwards Curves and Montgomery
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 36 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 37
D.2. Mapping between Montgomery Curves and Weierstrass Curves 37 D.2. Mapping between Montgomery Curves and Weierstrass Curves 37
D.3. Mapping between Twisted Edwards Curves and Weierstrass D.3. Mapping between Twisted Edwards Curves and Weierstrass
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 38 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 38
Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 38 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 39
E.1. Curve Definition and Alternative Representations . . . . 38 E.1. Curve Definition and Alternative Representations . . . . 39
E.2. Switching between Alternative Representations . . . . . . 38 E.2. Switching between Alternative Representations . . . . . . 39
E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 40 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 41
Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 42 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 43
F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 42 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 43
F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 43 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 43
F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 43 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 44
F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 44 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 45
Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 46 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 47
G.1. Further Alternative Representations . . . . . . . . . . . 46 G.1. Further Alternative Representations . . . . . . . . . . . 47
G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 46 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 47
G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 47 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 48
G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 48 G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 49
G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 49 G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 49
G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 55 G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 56
Appendix H. Point Compression . . . . . . . . . . . . . . . . . 61 Appendix H. Point Compression . . . . . . . . . . . . . . . . . 62
H.1. Point Compression for Weierstrass Curves . . . . . . . . 61 H.1. Point Compression for Weierstrass Curves . . . . . . . . 62
H.2. Point Compression for Montgomery Curves . . . . . . . . . 62 H.2. Point Compression for Montgomery Curves . . . . . . . . . 63
H.3. Point Compression for Twisted Edwards Curves . . . . . . 63 H.3. Point Compression for Twisted Edwards Curves . . . . . . 64
Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 64 Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 65
I.1. Strings and String Operations . . . . . . . . . . . . . . 64 I.1. Strings and String Operations . . . . . . . . . . . . . . 65
I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 64 I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 65
I.3. Conversion between Octet Strings and Integers (OS2I, I.3. Conversion between Octet Strings and Integers (OS2I,
I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 65 I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 66
I.4. Conversion between Octet Strings and Bit Strings (OS2BS, I.4. Conversion between Octet Strings and Bit Strings (OS2BS,
BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 65 BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 66
I.5. Conversion between Field Elements and Octet Strings I.5. Conversion between Field Elements and Octet Strings
(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 66 (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 67
I.6. Conversion between Elements of Z mod n and Octet Strings I.6. Conversion between Elements of Z mod n and Octet Strings
(ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 66 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 67
I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 67 I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 68
I.8. Conversion Between Curve Points and Octet Strings . . . . 68 I.8. Conversion Between Curve Points and Octet Strings . . . . 69
Appendix J. Representation Examples Curve25519 Family Members . 70 Appendix J. Representation Examples Curve25519 Family Members . 71
J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 71 J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 72
J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 73 J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 74
J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 74 J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 75
J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 77 J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 78
J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 78 J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 79
Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 80 Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 81
K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 80 K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 81
K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 80 K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 81
K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 80 K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 81
K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 81 K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 82
K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 81 K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 82
K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 81 K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 82
K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 82 K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 83
K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 83 K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 84
K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 84 K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 85
K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 84 K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 85
K.4.2. Mapping to High-Order Points of Montgomery Curve . . 85 K.4.2. Mapping to High-Order Points of Montgomery Curve . . 86
K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 86 K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 87
K.5. Randomized Representation of Curve Points . . . . . . . . 87 K.5. Randomized Representation of Curve Points . . . . . . . . 88
Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 88 K.6. Completing the Mappings to Curve Points . . . . . . . . . 89
L.1. Curve Definition and Alternative Representation . . . . . 88 Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 90
L.2. Switching Between Representations . . . . . . . . . . . . 89 L.1. Curve Definition and Alternative Representation . . . . . 90
L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 89 L.2. Switching Between Representations . . . . . . . . . . . . 90
L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 91 L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 91
L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 91 L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 92
L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 91 L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 92
Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 92 L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 93
M.1. Curve Definition and Alternative Representations . . . . 92 Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 94
M.2. Switching between Alternative Representations . . . . . . 93 M.1. Curve Definition and Alternative Representations . . . . 94
M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 94 M.2. Switching between Alternative Representations . . . . . . 94
Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 97 M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 96
N.1. Further Alternative Representations . . . . . . . . . . . 97
N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 97 Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 98
N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 99 N.1. Further Alternative Representations . . . . . . . . . . . 98
N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 101 N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 99
N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 102 N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 101
N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 102 N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 103
Appendix O. Representation Examples Curve448 Family Members . . 103 N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 103
O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 104 N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 104
O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 106 Appendix O. Representation Examples Curve448 Family Members . . 105
O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 108 O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 105
O.4. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 111 O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 108
O.5. Example with Edwards448 . . . . . . . . . . . . . . . . . 113 O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 110
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 115 O.4. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 113
O.5. Example with Edwards448 . . . . . . . . . . . . . . . . . 115
Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 117
P.1. Conversion to Integers in Z_n via Modular Reduction . . . 117
P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 118
P.3. Conversion to Integers in Z_n via the Discard Method . . 119
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 119
1. Fostering Code Reuse with New Elliptic Curves 1. Fostering Code Reuse with New Elliptic Curves
Elliptic curves can be represented using different curve models. Elliptic curves can be represented using different curve models.
Recently, IETF standardized elliptic curves that are claimed to have Recently, IETF standardized elliptic curves that are claimed to have
better performance and improved robustness against "real world" better performance and improved robustness against "real world"
attacks than curves represented in the traditional "short" attacks than curves represented in the traditional "short"
Weierstrass model. This document specifies an alternative Weierstrass model. This document specifies an alternative
representation of points of Curve25519, a so-called Montgomery curve, representation of points of Curve25519, a so-called Montgomery curve,
and of points of Edwards25519, a so-called twisted Edwards curve, and of points of Edwards25519, a so-called twisted Edwards curve,
skipping to change at page 9, line 12 skipping to change at page 9, line 19
Edwards curve (Ed448) or as points of a short-Weierstrass curve Edwards curve (Ed448) or as points of a short-Weierstrass curve
(Wei448). For the specification of Wei448 and its relationship to (Wei448). For the specification of Wei448 and its relationship to
Curve448 and Ed448, see Appendix M. As with ECDH25519, one can now Curve448 and Ed448, see Appendix M. As with ECDH25519, one can now
easily define a NIST-compliant version of co-factor Diffie-Hellman easily define a NIST-compliant version of co-factor Diffie-Hellman
key agreement (denoted by ECDH448), by simply reusing the example of key agreement (denoted by ECDH448), by simply reusing the example of
Section 4.1, but now using the short-Weierstrass curve Wei448, rather Section 4.1, but now using the short-Weierstrass curve Wei448, rather
than Wei25519. Similarly, one can easily specify ECDSA with Wei448 than Wei25519. Similarly, one can easily specify ECDSA with Wei448
and a suitable hash function, by simply reusing the example of and a suitable hash function, by simply reusing the example of
Section 4.3, but now using the short-Weierstrass curve Wei448, rather Section 4.3, but now using the short-Weierstrass curve Wei448, rather
than Wei25519, and picking as hash function SHAKE256 [FIPS-202] with than Wei25519, and picking as hash function SHAKE256 [FIPS-202] with
output size of d=446 bits. We denote by ECDSA448 the resulting output size of d=512 bits. We denote by ECDSA448 the resulting
signature scheme (with the same bit/byte-ordering conventions). 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:
5.1. Wire Format 5.1. Wire Format
skipping to change at page 19, line 42 skipping to change at page 20, line 4
a. Curve points and private keys are encoded as specified in a. Curve points and private keys are encoded as specified in
Section 10.1.1, where the "crv" parameter is set to the unique Section 10.1.1, where the "crv" parameter is set to the unique
name of the curve used with this particular instantiation of name of the curve used with this particular instantiation of
ECDH. ECDH.
When using a COSE key for this algorithm, if the "alg" field is When using a COSE key for this algorithm, if the "alg" field is
present, it MUST be set to the (unique) name of this particular present, it MUST be set to the (unique) name of this particular
instantiation of co-factor ECDH and the "crv" parameter MUST be set instantiation of co-factor ECDH and the "crv" parameter MUST be set
to the (unique) name of the corresponding curve; if the "key_ops" to the (unique) name of the corresponding curve; if the "key_ops"
field is present, it MUST include "key agreement" when creating an field is present, it MUST include "derive shared secret" for the
ECDH shared secret. private key.
10.3.2. Encoding of co-factor ECDH with JOSE 10.3.2. Encoding of co-factor ECDH with JOSE
Instantiations of co-factor ECDH used with JOSE use the following Instantiations of co-factor ECDH used with JOSE use the following
encodings of inputs and outputs: encodings of inputs and outputs:
a. Curve points and private keys are encoded as specified in a. Curve points and private keys are encoded as specified in
Section 10.1.2, where the "crv" parameter is set to the unique Section 10.1.2, where the "crv" parameter is set to the unique
name of the curve used with this particular instantiation of name of the curve used with this particular instantiation of
ECDH. ECDH.
When using a JOSE key for this algorith, if the "alg" field is When using a JOSE key for this algorithm, if the "alg" field is
present, it MUST be set to the (unique) name of this particular present, it MUST be set to the (unique) name of this particular
instantiation of co-factor ECDH and the "crv" parameter MUST be set instantiation of co-factor ECDH and the "crv" parameter MUST be set
to the (unique) name of the corresponding curve; if the "key_ops" to the (unique) name of the corresponding curve; if the "key_ops"
field is present, it MUST include "key agreement" when creating an field is present, it MUST include "derive shared secret" for the
ECDH shared secret. private key.
11. IANA Considerations 11. IANA Considerations
Code points are requested for curves Wei25519 and Wei448 and their Code points are requested for curves Wei25519 and Wei448 and their
use with ECDSA and co-factor ECDH, using the representation use with ECDSA and co-factor ECDH, using the representation
conventions of this document. conventions of this document.
New code points would be required in case one wishes to specify one New code points would be required in case one wishes to specify one
or more other "offspring" protocols beyond those exemplified in or more other "offspring" protocols beyond those exemplified in
Section 4.4. Specification hereof is, however, outside scope of the Section 4.4. Specification hereof is, however, outside scope of the
skipping to change at page 21, line 37 skipping to change at page 21, line 43
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; Change Controller: IESG;
Reference: defined in Section 4.1 of this specification; for Reference: specified in Section 4.1 of this specification; for
encodings, see Section 10.3; encodings, see Section 10.3;
Recommended: Yes. Recommended: Yes.
11.1.4. JOSE Elliptic Curves Registration 11.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;
skipping to change at page 22, line 47 skipping to change at page 23, line 11
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;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: Section 4.1 of this specification; for encodings, see Reference: specified in Section 4.1 of this specification; for
Section 10.1; encodings, see Section 10.3;
Algorithm Analysis Document(s): Section 4.1 of this specification. Algorithm Analysis Document(s): Section 4.1 of this specification.
11.2. IANA Considerations for Wei448 11.2. IANA Considerations for Wei448
11.2.1. COSE Elliptic Curves Registration 11.2.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].
skipping to change at page 23, line 41 skipping to change at page 24, line 4
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: ECDSA448; Name: ECDSA448;
Value: TBD (Requested value: -47); Value: TBD (Requested value: -47);
Description: ECDSA with SHAKE256 and curve Wei448; Description: ECDSA with SHAKE256 and curve Wei448;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Section 4.4 of this specification; for
Reference: Section 4.4 of this specification; encodings, see Section 10.1;
Recommended: Yes. Recommended: Yes.
11.2.3. COSE Algorithms Registration (2/2) 11.2.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: ECDH448; Name: ECDH448;
Value: TBD (Requested value: -48); Value: TBD (Requested value: -48);
Description: NIST-compliant co-factor Diffie-Hellman w/ curve Wei448 Description: NIST-compliant co-factor Diffie-Hellman w/ curve Wei448
and key derivation function HKDF SHA512; and key derivation function HKDF SHA512;
Change Controller: IESG; Change Controller: IESG;
Reference: Section 4.4 of this specification (for key derivation, Reference: specified in Section 4.4 of this specification; for
see Section 11.1 of [RFC8152]); encodings, see Section 10.1; for key derivation, see
Section 11.1 of [RFC8152];
Recommended: Yes. Recommended: Yes.
11.2.4. JOSE Elliptic Curves Registration 11.2.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: Wei448; Curve Name: Wei448;
skipping to change at page 25, line 24 skipping to change at page 25, line 37
Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/ Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/
curve Wei448; curve Wei448;
Algorithm Usage Locations: alg; Algorithm Usage Locations: alg;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Section 4.4 of this specification; for Reference: specified in Section 4.4 of this specification; for
encodings, see Section 10.3 encodings, see Section 10.3;
Algorithm Analysis Document(s): Section 4.4 of this specification. Algorithm Analysis Document(s): Section 4.4 of this specification.
12. Acknowledgements 12. 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.
skipping to change at page 26, line 20 skipping to change at page 26, line 37
[FIPS-202] [FIPS-202]
FIPS 202, "SHA-3 Standard: Permutation-Based Hash and FIPS 202, "SHA-3 Standard: Permutation-Based Hash and
Extendable-Output Functions, Federal Information Extendable-Output Functions, Federal Information
Processing Standards Publication 202", US Department of Processing Standards Publication 202", US Department of
Commerce/National Institute of Standards and Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, August 2015. Technology, Gaithersburg, MD, August 2015.
[I-D.ietf-cose-rfc8152bis-algs] [I-D.ietf-cose-rfc8152bis-algs]
Schaad, J., "CBOR Object Signing and Encryption (COSE): Schaad, J., "CBOR Object Signing and Encryption (COSE):
Initial Algorithms", draft-ietf-cose-rfc8152bis-algs-07 Initial Algorithms", draft-ietf-cose-rfc8152bis-algs-11
(work in progress), March 2020. (work in progress), July 2020.
[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>.
[RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data
Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006, Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006,
<https://www.rfc-editor.org/info/rfc4648>. <https://www.rfc-editor.org/info/rfc4648>.
skipping to change at page 28, line 7 skipping to change at page 28, line 22
of Standards and Technology, Gaithersburg, MD, April 2018. of Standards and Technology, Gaithersburg, MD, April 2018.
[SP-800-56c] [SP-800-56c]
NIST SP 800-56c, "Recommendation for Key-Derivation NIST SP 800-56c, "Recommendation for Key-Derivation
Methods in Key-Establishment Schemes, Revision 1", US Methods in Key-Establishment Schemes, Revision 1", US
Department of Commerce/National Institute of Standards and Department of Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, April 2018. Technology, Gaithersburg, MD, April 2018.
13.2. Informative References 13.2. Informative References
[comm-FIPS-186-5]
FIPS 186-5, "Public Comments Received on Draft FIPS Pub
186-5", US Department of Commerce/National Institute of
Standards and Technology, Gaithersburg, MD, April 6, 2020.
[ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in [ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in
Cryptography", Cambridge University Press, Lecture Notes Cryptography", Cambridge University Press, Lecture Notes
Series 265, July 1999. Series 265, July 1999.
[ECC-Isogeny] [ECC-Isogeny]
E. Brier, M. Joye, "Fast Point Multiplication on Elliptic E. Brier, M. Joye, "Fast Point Multiplication on Elliptic
Curves through Isogenies", AAECC, Lecture Notes in Curves through Isogenies", AAECC, Lecture Notes in
Computer Science, Vol. 2643, New York: Springer-Verlag, Computer Science, Vol. 2643, New York: Springer-Verlag,
2003. 2003.
skipping to change at page 30, line 42 skipping to change at page 31, line 19
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 This section provides brief background information on elliptic curves
and finite fields that should be sufficient to understand and finite fields that should be sufficient to understand
constructions and examples in this document. 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 The set of points of each curve defined in Appendix A forms a
addition (denoted by '+'). In Appendix C we specify the group laws, commutative group under addition (denoted by '+'). In Appendix C we
which depend on the curve model in question. For completeness, we specify the group laws, which depend on the curve model in question.
here include some common elliptic curve nomenclature and basic For completeness, we here include some common elliptic curve
properties (primarily so as to keep this document self-contained). nomenclature and basic properties (primarily so as to keep this
These notions are mainly used in Appendix E and Appendix G and not document self-contained). These notions are mainly used in
essential for our exposition. This section can be skipped at first Appendix E and Appendix G and not essential for our exposition. This
reading. section can be skipped at first 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; k*P is commonly referred to as scalar multiplication of P by curve; k*P is commonly referred to as scalar multiplication of P by
k.) If (P) has cardinality l, then l is called the order of P. The k.) If (P) has cardinality l, then l is called the order of P and l
order of curve E is the cardinality of the set of its points, is the smallest positive integer so that l*P=O. The order of curve E
commonly denoted by |E|. A curve is cyclic if it is generated by some is the cardinality of the set of its points, commonly denoted by |E|.
point of this curve. All curves of prime order are cyclic, while all A curve is cyclic if it is generated by some point of this curve.
curves of order h*n, where n is a large prime number and where h is a All curves of prime order are cyclic, while all curves of order h*n,
small number (the so-called co-factor), have a large cyclic subgroup where n is a large prime number and where h is a small number (the
of prime order n. In this case, a generator of order n is called a so-called co-factor), have a large cyclic subgroup of prime order n.
base point, commonly denoted by G. A point of order dividing h is In this case, a generator of order n is called a base point, commonly
said to be in the small subgroup. For curves of prime order, this denoted by G, while a point of order dividing h is said to be in the
small subgroup is the singleton set, consisting of only the identity small subgroup. For curves of prime order, this small subgroup is
element O. A point that is not in the small subgroup is said to be a the singleton set, consisting of only the identity element O. A
high-order point (since it has order at least n). point that is not in the small subgroup is said to be a high-order
point (since it has order at least n). A point P of the curve is in
the small subgroup if h*P=O (and is a high-order point otherwise);
this point has order n if n*P=O and if it is not the identity element
O. (The latter order check is commonly called full public key
validation.)
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. If this representation is nonzero, R 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 otherwise, it has order one and is the identity element O of the
curve. 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 specific curve E' related to E defined over the same
where |E|+|E'|=2*(q+1). If E is a curve in one of the curve models field, with cardinality |E'|, where |E|+|E'|=2*(q+1). If E is a
specified in this document, a quadratic twist of this curve can be curve in one of the curve models specified in this document, a
expressed using the same curve model, although (naturally) with its quadratic twist of this curve can be expressed using the same curve
own curve parameters. Two curves E and E' defined over a field GF(q) model, although (naturally) with its own curve parameters. Two
are said to be isogenous if these have the same order and are said to curves E and E' defined over a field GF(q) are said to be isogenous
be isomorphic if these have the same group structure. Note that if these have the same order and are said to be isomorphic if these
isomorphic curves have necessarily the same order and are, thus, a have the same group structure. Note that isomorphic curves have
special type of isogenous curves. Further details are out of scope. necessarily the same order and are, thus, a special type of isogenous
curves. Further details are out of scope.
Weierstrass curves can have prime order, whereas Montgomery curves Weierstrass curves can have prime order, whereas Montgomery curves
and twisted Edwards curves always have an order that is a multiple of and twisted Edwards curves always have an order that is a multiple of
four (and, thereby, a small subgroup of cardinality four). four (and, thereby, a small subgroup of cardinality four).
An ordered pair (x, y) whose coordinates are elements of GF(q) can be An ordered pair (x, y) whose coordinates are elements of GF(q) can be
associated with any ordered triple of the form [x*z: y*z: z], where z associated with any ordered triple of the form [x*z: y*z: z], where z
is a nonzero element of GF(q), and can be uniquely recovered from is a nonzero element of GF(q), and can be uniquely recovered from
such a representation. The latter representation is commonly called such a representation. The latter representation is commonly called
a representation in projective coordinates. Sometimes, yet other a representation in projective coordinates. Sometimes, yet other
skipping to change at page 33, line 6 skipping to change at page 33, line 42
called a (nontrivial) extension field of GF(p). The number p 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 K.1 and Appendix K.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 K.3. curve, see Appendix K.3 (or see Appendix K.4, if one wishes to always
obtain a high-order point of the curve in question).
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
skipping to change at page 36, line 18 skipping to change at page 37, line 7
(Here, observe that a-d*y*y1*y2 is nonzero per our Note above.) This (Here, observe that a-d*y*y1*y2 is nonzero per our Note above.) This
property allows recovery of the x-coordinate of a point P1=k*P that property allows recovery of the x-coordinate of a point P1=k*P that
is computed via the so-called Montgomery ladder, where P is an affine is computed via the so-called Montgomery ladder, where P is an affine
point with nonzero x-coordinate (i.e., it does not have order one or 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 two). For future reference, note that the group law (subject to our
Note above) uniquely determines the y-coordinate of P2 in terms of 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. the y-coordinates of P and P1 and the product of their x-coordinates.
Further details are out of scope. Further details are out of scope.
Appendix D. Relationship Between Curve Models Appendix D. Relationships 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,
skipping to change at page 55, line 4 skipping to change at page 55, line 50
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
G.4.2. Dual Isogeny Parameters G.4.2. Dual Isogeny Parameters
G.4.2.1. Coefficients of u'(x) G.4.2.1. Coefficients of u'(x)
0 0x0f0eddb584a20aaac8f1419efdd02a5cca77b21e4cfae78c49b5127d98bc5882 0 0x0f0eddb584a20aaac8f1419efdd02a5cca77b21e4cfae78c49b5127d98bc5882
1 0x7115e60d44a58630417df33dd45b8a546fa00b79fea3b2bdc449694bade87c0a 1 0x7115e60d44a58630417df33dd45b8a546fa00b79fea3b2bdc449694bade87c0a
skipping to change at page 56, line 4 skipping to change at page 56, line 49
15 0x74676df60a9906901d1dc316c639ff6ae0fcdb02b5571d4b83fc2eedcd2936a8 15 0x74676df60a9906901d1dc316c639ff6ae0fcdb02b5571d4b83fc2eedcd2936a8
16 0x22f8212219aca01410f06eb234ed53bd5b8fbe7c08652b8002bcd1ea3cdae387 16 0x22f8212219aca01410f06eb234ed53bd5b8fbe7c08652b8002bcd1ea3cdae387
17 0x7edb04449565d7c566b934a87fadade5515f23bda1ce25daa19fff0c6a5ccc2f 17 0x7edb04449565d7c566b934a87fadade5515f23bda1ce25daa19fff0c6a5ccc2f
18 0x106ef71aa3aa34e8ecf4c07a67d03f0949d7d015ef2c1e32eb698dd3bec5a18c 18 0x106ef71aa3aa34e8ecf4c07a67d03f0949d7d015ef2c1e32eb698dd3bec5a18c
19 0x0017913eb705db126ac3172447bcd811a62744d505ad0eea94cfcfdde5ca7428 19 0x0017913eb705db126ac3172447bcd811a62744d505ad0eea94cfcfdde5ca7428
20 0x2cc793e6d3b592dcf5472057a991ff1a5ab43b4680bb34c0f5faffc5307827c1
20 0x2cc793e6d3b592dcf5472057a991ff1a5ab43b4680bb34c0f5faffc5307827c1
21 0x6dafcc0b16f98300cddb5e0a7d7ff04a0e73ca558c54461781d5a5ccb1ea0122 21 0x6dafcc0b16f98300cddb5e0a7d7ff04a0e73ca558c54461781d5a5ccb1ea0122
22 0x7e418891cf222c021b0ae5f5232b9c0dc8270d4925a13174a0f0ac5e7a4c8045 22 0x7e418891cf222c021b0ae5f5232b9c0dc8270d4925a13174a0f0ac5e7a4c8045
23 0x76553bd26fecb019ead31142684789fea7754c2dc9ab9197c623f45d60749058 23 0x76553bd26fecb019ead31142684789fea7754c2dc9ab9197c623f45d60749058
24 0x693efb3f81086043656d81840902b6f3a9a4b0e8f2a5a5edf5ce1c7f50a3898e 24 0x693efb3f81086043656d81840902b6f3a9a4b0e8f2a5a5edf5ce1c7f50a3898e
25 0x46c630eac2b86d36f18a061882b756917718a359f44752a5caf41be506788921 25 0x46c630eac2b86d36f18a061882b756917718a359f44752a5caf41be506788921
skipping to change at page 57, line 4 skipping to change at page 57, line 49
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
G.4.2.2. Coefficients of v'(x) G.4.2.2. Coefficients of v'(x)
0 0x043c9b67cc5b16e167b55f190db61e44d48d813a7112910f10e3fd8da85d61d3 0 0x043c9b67cc5b16e167b55f190db61e44d48d813a7112910f10e3fd8da85d61d3
skipping to change at page 58, line 4 skipping to change at page 58, line 49
14 0x0fde79514935d9b40f52e33429621a200acc092f6e5dec14b49e73f2f59c780d 14 0x0fde79514935d9b40f52e33429621a200acc092f6e5dec14b49e73f2f59c780d
15 0x37517ac5c04dc48145a9d6e14803b8ce9cb6a5d01c6f0ad1b04ff3353d02d815 15 0x37517ac5c04dc48145a9d6e14803b8ce9cb6a5d01c6f0ad1b04ff3353d02d815
16 0x58ae96b8eefe9e80f24d3b886932fe3c27aaea810fa189c702f93987c8c97854 16 0x58ae96b8eefe9e80f24d3b886932fe3c27aaea810fa189c702f93987c8c97854
17 0x6f6402c90fa379096d5f436035bebc9d29302126e9b117887abfa7d4b3c5709a 17 0x6f6402c90fa379096d5f436035bebc9d29302126e9b117887abfa7d4b3c5709a
18 0x01dbdf2b9ec09a8defeb485cc16ea98d0d45c5b9877ff16bd04c0110d2f64961 18 0x01dbdf2b9ec09a8defeb485cc16ea98d0d45c5b9877ff16bd04c0110d2f64961
19 0x53c51706af523ab5b32291de6c6b1ee7c5cbd0a5b317218f917b12ff38421452
19 0x53c51706af523ab5b32291de6c6b1ee7c5cbd0a5b317218f917b12ff38421452
20 0x1b1051c7aec7d37a349208e3950b679d14e39f979db4fcd7b50d7d27dc918650 20 0x1b1051c7aec7d37a349208e3950b679d14e39f979db4fcd7b50d7d27dc918650
21 0x1547e8d36262d5434cfb029cdd29385353124c3c35b1423c6cca1f87910b305b 21 0x1547e8d36262d5434cfb029cdd29385353124c3c35b1423c6cca1f87910b305b
22 0x198efe984efc817835e28f704d41e4583a1e2398f7ce14045c4575d0445c6ce7 22 0x198efe984efc817835e28f704d41e4583a1e2398f7ce14045c4575d0445c6ce7
23 0x492276dfe9588ee5cd9f553d990f377935d721822ecd0333ce2eb1d4324d539c 23 0x492276dfe9588ee5cd9f553d990f377935d721822ecd0333ce2eb1d4324d539c
24 0x77bad5319bacd5ed99e1905ce2ae89294efa7ee1f74314e4095c618a4e580c9b 24 0x77bad5319bacd5ed99e1905ce2ae89294efa7ee1f74314e4095c618a4e580c9b
skipping to change at page 59, line 4 skipping to change at page 59, line 49
38 0x36199723cc59867e2e309fe9941cd33722c807bb2d0a06eeb41de93f1b93f2f5 38 0x36199723cc59867e2e309fe9941cd33722c807bb2d0a06eeb41de93f1b93f2f5
39 0x5cdeb1f2ee1c7d694bdd884cb1c5c22de206684e1cafb8d3adb9a33cb85e19a2 39 0x5cdeb1f2ee1c7d694bdd884cb1c5c22de206684e1cafb8d3adb9a33cb85e19a2
40 0x0f6e6b3fc54c2d25871011b1499bb0ef015c6d0da802ae7eccf1d8c3fb73856c 40 0x0f6e6b3fc54c2d25871011b1499bb0ef015c6d0da802ae7eccf1d8c3fb73856c
41 0x0c1422c98b672414344a9c05492b926f473f05033b9f85b8788b4bb9a080053c 41 0x0c1422c98b672414344a9c05492b926f473f05033b9f85b8788b4bb9a080053c
42 0x19a8527de35d4faacb00184e0423962247319703a815eecf355f143c2c18f17f 42 0x19a8527de35d4faacb00184e0423962247319703a815eecf355f143c2c18f17f
43 0x7812dc3313e6cf093da4617f06062e8e8969d648dfe6b5c331bccd58eb428383
43 0x7812dc3313e6cf093da4617f06062e8e8969d648dfe6b5c331bccd58eb428383
44 0x61e537180c84c79e1fd2d4f9d386e1c4f0442247605b8d8904d122ee7ef9f7be 44 0x61e537180c84c79e1fd2d4f9d386e1c4f0442247605b8d8904d122ee7ef9f7be
45 0x544d8621d05540576cfc9b58a3dab19145332b88eb0b86f4c15567c37205adf9 45 0x544d8621d05540576cfc9b58a3dab19145332b88eb0b86f4c15567c37205adf9
46 0x11be3ef96e6e07556356b51e2479436d9966b7b083892b390caec22a117aa48e 46 0x11be3ef96e6e07556356b51e2479436d9966b7b083892b390caec22a117aa48e
47 0x205cda31289cf75ab0759c14c43cb30f7287969ea3dc0d5286a3853a4d403187 47 0x205cda31289cf75ab0759c14c43cb30f7287969ea3dc0d5286a3853a4d403187
48 0x048d8fc6934f4f0a99f0f2cc59010389e2a0b20d6909bfcf8d7d0249f360acdc 48 0x048d8fc6934f4f0a99f0f2cc59010389e2a0b20d6909bfcf8d7d0249f360acdc
skipping to change at page 60, line 4 skipping to change at page 60, line 49
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
G.4.2.3. Coefficients of w'(x) G.4.2.3. Coefficients of w'(x)
0 0x6bd7f1fc5dd51b7d832848c180f019bcbdb101d4b3435230a79cc4f95c35e15e 0 0x6bd7f1fc5dd51b7d832848c180f019bcbdb101d4b3435230a79cc4f95c35e15e
1 0x17413bb3ee505184a504e14419b8d7c8517a0d268f65b0d7f5b0ba68d6166dd0 1 0x17413bb3ee505184a504e14419b8d7c8517a0d268f65b0d7f5b0ba68d6166dd0
skipping to change at page 61, line 4 skipping to change at page 61, line 49
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 H. 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
skipping to change at page 61, line 47 skipping to change at page 62, line 45
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.
The value of the parity function is commonly called the parity bit. The value of the parity function is commonly called the parity bit.
H.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^3+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 W_{a,b}, one can use the defining the domain parameters of the curve W_{a,b}, one can use the defining
equation of the curve to try and determine candidate values for the 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
skipping to change at page 69, line 42 skipping to change at page 70, line 42
property that its 1-octet prefix identifies whether it encodes an property that its 1-octet prefix identifies whether it encodes an
affine curve point, a compressed point (including parity bit), or the affine curve point, a compressed point (including parity bit), or the
identity element, while the remainder of this representation uniquely identity element, while the remainder of this representation uniquely
determines the curve point's value. While the description in [SEC1] determines the curve point's value. While the description in [SEC1]
only applies to Weierstrass curves, the description above applies to only applies to Weierstrass curves, the description above applies to
each of the curve models we consider (i.e., these apply to Montgomery each of the curve models we consider (i.e., these apply to Montgomery
curves and twisted Edwards curves as well). Collectively, we simply curves and twisted Edwards curves as well). Collectively, we simply
refer to this as the "SEC1" point representation. refer to this as the "SEC1" point representation.
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-octet 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 H) 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 an element of GF(p) to be and, thereby, allows a compressed point and an element of GF(p) to be
represented by an octet string of the same length. This is called represented by an octet string of the same length. This is called
the "squeezed" point representation. (We will use this squeezed the "squeezed" point representation. (We will use this squeezed
representation in Appendix J.) Obviously, other representations representation in Appendix J.) Obviously, other representations
(e.g., those of elements of Z_n) may also have fixed bit values in (e.g., those of elements of Z_n) may also have fixed bit values in
certain positions, which can be used to squeeze-in additional certain positions, which can be used to squeeze-in additional
information. Further details are out of scope. Notice that elements information. Further details are out of scope.
of a prime field GF(p), where p is a prime number with bit-size m
divisible by eight, have a tight representation as an (m/8)-byte Notice that elements of a prime field GF(p), where p is a prime
string, but do not have a bit position that is always set to zero. number with bit-size m divisible by eight, have a tight
Thus, in this case, one cannot represent a compressed point as an representation as an (m/8)-octet string, but do not have a bit
octet string of the same length as an element of GF(p). However, one position that is always set to zero. Thus, in this case, one cannot
can still encode this as an octet string of length (m/8)+1 (see Note represent a compressed point as an octet string of the same length as
1 above). If one uses right-concatenation as in Note 1, but (for an element of GF(p). However, one can still encode this as an octet
historial reasons) represents the parity bit t of the compressed string of length (m/8)+1 (see Note 1 above). If one uses right-
point in question by 0x00 or 0x80 depending on whether t=0 or t=1, concatenation as in Note 1, but (for historial reasons) represents
respectively, this is again called the "squeezed' representation the parity bit t of the compressed point in question by 0x00 or 0x80
(despite this being somewhat a misnomer, since each point is now depending on whether t=0 or t=1, respectively, this is again called
represented as an octet string that is one octet longer than the the "squeezed' representation (despite this being somewhat a
tight representation of elements of GF(p)). Notice that this misnomer, since each point is now represented as an octet string that
representation corresponds to the compressed point representation of is one octet longer than the tight representation of elements of
Appendix I.8 as octet string, but with the bit-ordering in the GF(p)). Notice that this representation corresponds to the
1-octet representation of t reversed. (Note that this puts the compressed point representation of Appendix I.8 as octet string, but
parity bit t in the leftmost bit position of the octet string if one with the bit-ordering in the 1-octet representation of t reversed.
follows the MSB/msb representation conventions.) We will use this (Note that this puts the parity bit t in the leftmost bit position of
squeezed represenation in Appendix O. the octet string if one follows the MSB/msb representation
conventions.) We will use this squeezed represenation in Appendix O.
Appendix J. 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 Appendix E and Appendix G of this document. In each case, we in Appendix E and Appendix G of this document. In each case, we
indicate the values of P, k*P, and (k+1)*P, where P is a fixed 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 multiple (here: 2019) of the base point of the curve in question and
where the private key k is the integer where the private key k is the integer
k 45467544759954639344191351164156560595299236761702065033670739677 k 45467544759954639344191351164156560595299236761702065033670739677
skipping to change at page 81, line 23 skipping to change at page 82, line 23
1/y:=y^{q-2} (since y^{q-1}=1). 1/y:=y^{q-2} (since y^{q-1}=1).
If inverses are easy to compute in GF(q), then so are these in If inverses are easy to compute in GF(q), then so are these in
GF(q^2). Further details are out of scope. 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.
NOTE: This method can also be used to compute the inverse and a
square root, respectively, of two nonzero elements x and y of GF(q)
by first computing a square root z of 1/(y*x^2) (see Appendix K.1)
and by subsequently computing a square root of y as x*y*z and the
inverse of x as x*y*z^2.
K.3. Mappings 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 K.3.1), to points of a points of a Weierstrass curve (see Appendix K.3.1), to points of a
Montgomery curve (see Appendix K.3.2), or to points of a twisted Montgomery curve (see Appendix K.3.2), or to points of a twisted
Edwards curve (see Appendix K.3.3), under some mild conditions on the 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.
K.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
point of W{a,b}, depending on whether f(X) is a square in GF(q). point of W_{a,b}, depending on whether f(X) is a square in GF(q).
a. If f(X) is a square in GF(q) and Y:=sqrt(f(X)), then t is mapped a. If f(X) is a square in GF(q) and Y:=sqrt(f(X)), then t is mapped
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
skipping to change at page 82, line 18 skipping to change at page 83, line 24
(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
point at infinity for t=-1. One can modify this mapping to always point at infinity for t=-1. One can modify this mapping, by mapping
yield an affine point, by mapping the element -1 to, e.g., the base the element -1 to any suitable point P0 of W_{a,b} (e.g., its base
point G of W_{a,b} and leaving the remainder of the mapping the same. point G or any other affine point) and leaving the remainder of the
Suitability of such a modification is application-specific. Details mapping the same. Suitability of such a modification is application-
are out of scope. specific. Details 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 if -4*b is a cube in example, one can show that if a is zero and if -4*b is a cube in
skipping to change at page 82, line 48 skipping to change at page 84, line 5
K.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).
a. If f(u)/B is a square in GF(q) and v:=sqrt(f(u)/B), then t is a. If f(u)/B is a square in GF(q) and v:=sqrt(f(u)/B), then t is
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
skipping to change at page 83, line 27 skipping to change at page 84, line 30
(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, by mapping
yield an affine point, by mapping the element -1 to, e.g., the base the element -1 to any suitable point P0 of M_{a,b} (e.g., its base
point G of M_{A,B} and leaving the remainder of the mapping the same. point G or any other affine point) and leaving the remainder of the
Suitability of such a modification is application-specific. Details mapping the same. Suitability of such a modification is application-
are out of scope. specific. Details 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 K.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.
skipping to change at page 88, line 7 skipping to change at page 89, line 13
mapping of Appendix K.4.2). Further details are out of scope. mapping of Appendix K.4.2). Further details are out of scope.
NOTE 1: The main difference between the two constructions above is NOTE 1: The main difference between the two constructions above is
that that the first construction uses the mappings to curve points that that the first construction uses the mappings to curve points
described in Appendix K.3, while the second construction uses the described in Appendix K.3, while the second construction uses the
mappings to high-order curve points described in Appendix K.4. Note 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) 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. if one considers all possible values for the binary digits s1 and s2.
(This, thereby, includes the value P2(t1, t2).) (This, thereby, includes the value P2(t1, t2).)
NOTE 2: The second mapping above operates on input pairs (t,s), where NOTE 2: The results on the statistical distributions mentioned above
t is an element of GF(q) that is not a square in GF(q) and where s is still hold if one makes a few localized changes to the constructions.
a binary digit from the set {0,1}. One can use these mappings to In particular, these are independent of the specific choices for the
point P0 (used with input -1 with the mappings of Appendix K.3, if
applicable, respectively, used with the mappings of Appendix K.4) and
also still hold if one re-defines the mappings P2 or Q2 locally so as
to avoid points in the small subgroup.
K.6. Completing the Mappings to Curve Points
The mappings of Appendix K.4 operate 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 produce a mapping from the nonzero elements of GF(q) to points of a
curve via function composition, where one first maps any nonzero particular curve via function composition, where one first maps any
element u of GF(q) to the pair (t,s):=(delta*u^2, par(u)), where nonzero element u of GF(q) to the pair (t,s):=(delta*u^2, par(u)),
delta is a fixed element of GF(q) that is not a square in GF(q), and where delta is a fixed element of GF(q) that is not a square in
where one subsequently applies any of the mappings above to yield a GF(q), and where one subsequently applies any of the mappings to
point of the curve in question. The resulting mapping from the yield a point of the curve in question. The resulting mapping from
nonzero elements of GF(q) to high-order curve points can be extended the nonzero elements of GF(q) to high-order curve points can be
further to one that operates on all elements of GF(q) by mapping 0 to extended further to one that operates on all elements of GF(q) by
any fixed high-order point of the curve in question (e.g., to the mapping 0 to any fixed high-order point P1 of the curve in question.
fixed "curve offset" P0 of this curve [henceforth called the default The resulting mapping is uniquely defined after fixing the curve
completed mapping]). Depending on application-specific criteria, yet offset P0 (used with the mappings of Appendix K.4), the high-order
other function compositions may be preferred. For the first mapping point P1 (used for input 0 above), and the non-square element delta
above, one can use a similar function composition, where one simply of GF(q) (used for nonzero inputs above).
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. For the mappings of Appendix K.3, 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 P1. As
before, the resulting mapping is uniquely defined after fixing the
point P0 (for input -1 with the mappings of Appendix K.3, if
applicable), the point P1 (used for input 0 above), and the non-
square element delta of GF(q) (used for nonzero inputs above).
Further details are out of scope.
Similarly, one can use the completed mappings above to map a pair
(u1, u2) of elements of GF(q) to a point of a curve, via function
composition, where, in the first case, one first maps the pair (u1,
u2) to the pair ((t1,s1), (t2,s2)):=((delta*u1^2, par(u1)),
(delta*u2^2, par(u2))) and subsequently computes Q2compl((t1,s1),
(t2,s2)):=Qcompl(t1,s1) - Qcompl(t2,s2), where Qcompl(t,s):=Q(t,s) if
t is nonzero and where Qcompl(0,s):=P0 otherwise (irrespective of the
value of s). In the second case, one first maps the pair (u1, u2) to
the pair (t1, t2):=(delta*u1^2, delta*u2^2) and subsequently computes
P2compl(t1, t2):=Pcompl(t1) + Pcompl(t2), where Pcompl(t):=P(t) if t
is nonzero and where Pcompl(0):=P1 otherwise. In either case, again,
the resulting mapping is uniquely defined after fixing the points P0
and P1 and the non-square element delta of GF(q).
Appendix L. Curve secp256k1 and Friend Appendix L. Curve secp256k1 and Friend
This section illustrates how isogenies can be used to yield curves This section illustrates how isogenies can be used to yield curves
with specific properties (here, for illustrated for the "BitCoin" with specific properties (here, for illustrated for the "BitCoin"
curve secp256k1). curve secp256k1).
L.1. Curve Definition and Alternative Representation 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
skipping to change at page 97, line 20 skipping to change at page 98, line 49
This section introduces some further curves related to Curve448 and This section introduces some further curves related to Curve448 and
explains their relationships. explains their relationships.
N.1. Further Alternative Representations N.1. Further Alternative Representations
The Weierstrass curve Wei448 is isomorphic to the Weierstrass curve The Weierstrass curve Wei448 is isomorphic to the Weierstrass curve
Wei448.1 defined over GF(p), with as base point the pair (G1X,G1Y), 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), and isogenous to the Weierstrass curve Wei448.-3 defined over GF(p),
with as base point the pair (G3X, G3Y), where parameters are as 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.3 and where the related mappings are as
specified in Appendix N.2. The Edwards curve Ed448 is isogenous to specified in Appendix N.2.
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 The Edwards curve Ed448 is isogenous to the Edwards curve Edwards448
and where the related mappings are as specified in Appendix N.2. 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. For this curve, the
domain parameter a is a square in GF(p), whereas d1 is not, so the
group laws of Appendix C.3 apply.
N.2. Further Switching N.2. Further Switching
Each affine point (X, Y) of Wei448 corresponds to the point (X', 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) Y'):=(X*s^2,Y*s^3) of Wei448.1, where s is the element of GF(p)
defined by defined by
s 52322274343677442779379520589771028818568404587729117919590511061 s 52322274343677442779379520589771028818568404587729117919590511061
93509510238347880134473888687471465216641846232724641298954890800 93509510238347880134473888687471465216641846232724641298954890800
00881 00881
skipping to change at page 98, line 35 skipping to change at page 100, line 19
mapping the point at infinity O of Wei448.-3 to the point at infinity 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, 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, 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; 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 see the description in Appendix F.4). Note that this isogenous map
(and its dual) primarily involves the evaluation of three fixed (and its dual) primarily involves the evaluation of three fixed
polynomials involving the x-coordinate, which takes only a few polynomials involving the x-coordinate, which takes only a few
modular multiplications (less than 0.5% relative incremental cost modular multiplications (less than 0.5% relative incremental cost
compared to the cost of an elliptic curve scalar multiplication). compared to the cost of an elliptic curve scalar multiplication).
Each point (x1,y1) of Edwards448 corresponds to the point (x,y) of Each point (x1,y1) of Edwards448 with nonzero coordinates corresponds
Ed448, where 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 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). 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 while each other point (i.e., a point of order 1, 2, or 4)
isogenous mapping, the base point (G1x, G1y) of Edwards448 corresponds to the identity element (0,1) of Ed448. (Here, we used
corresponds to the base point (Gx,Gy) of Ed448. The dual isogeny the 4-isogenous mapping of Appendix F.4). Under this isogenous
maps each point (x,y) of Ed448 to the point (x1,y1) of Edwards448, mapping, the base point (G1x, G1y) of Edwards448 corresponds to the
where 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 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). 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 Under this dual isogenous mapping, the base point (Gx, Gy) of Ed448
corresponds to a multiple of the base point (G1x, G1y) of Edwards448, 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 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 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,
which takes only a few multiplications (less than 0.5% relative which takes only a few multiplications (less than 0.5% 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).
The point (0,1) and the point (0,-1) of order two of Edwards448 Each point (x1,y1) of Edwards448 with nonzero coordinates corresponds
correspond to, respectively, the point at infinity and the point to the point (u,v) of Curve448, where
(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. 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 while each other point (i.e., a point of order 1, 2, or 4)
corresponds to the point at infinity of Curve448. Under this
isogenous mapping, the base point (G1x, G1y) of Edwards448
corresponds to the base point (Gu,Gv) of Curve448. The dual isogeny 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 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 Curve448 to the identity element (0,1) of Edwards448, while each
(u,v) of Curve448 corresponds to the point (x1,y1) of Edwards448, other point (u,v) of Curve448 corresponds to the point (x1,y1) of
where Edwards448, where
x1 = 4*(u^2-1)*v/((u^2-1)^2+4*v^2) and 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). 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 Under this dual isogenous mapping, the base point (Gu, Gv) of
Curve448 corresponds to a multiple of the base point (G1x, G1y) 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; Edwards448, where this multiple is l=4 (the degree of the isogeny;
see above). see above).
N.3. Further Domain Parameters N.3. Further Domain Parameters
The parameters of the Weierstrass curve with a=1 that is isomorphic The parameters of the Weierstrass curve with a=1 that is isomorphic
with Wei448 and the parameters of the Weierstrass curve with a=-3 with Wei448 and the parameters of the Weierstrass curve with a=-3
that is isogenous with Wei448 are as indicated below. Both domain that is isogenous with Wei448 are as indicated below. Both domain
parameter sets can be exploited directly to derive more efficient parameter sets can be exploited directly to derive more efficient
point addition formulae, should an implementation facilitate this. point addition formulae, should an implementation facilitate this.
The domain parameters of the twisted Edwards curve Edwards448 are as The domain parameters of the Edwards curve Edwards448 are as
specified in [RFC7748]. specified in [RFC7748].
General parameters: same as for Wei448 (see Appendix M.3) General parameters: same as for Wei448 (see Appendix M.3)
Weierstrass curve-specific parameters (for Wei448.1, i.e., with a=1): Weierstrass curve-specific parameters (for Wei448.1, i.e., with a=1):
a 1 (=0x01) a 1 (=0x01)
b 65961281701807170531944804985907990287225248056560036392380945951 b 65961281701807170531944804985907990287225248056560036392380945951
38183088507635437786021044927715119224497407914895790669345268896 38183088507635437786021044927715119224497407914895790669345268896
52743 52743
(=0xe8528596 bfbcbac9 7ebdbe4e 9683e25c 73a5ff37 6c4cd400 (=0xe8528596 bfbcbac9 7ebdbe4e 9683e25c 73a5ff37 6c4cd400
5a75c425 8e3eb05a 9f6f8c24 24cb5aa9 0dcf9fa4 cab6691d 5530347c 5a75c425 8e3eb05a 9f6f8c24 24cb5aa9 0dcf9fa4 cab6691d 5530347c
28437207) 28437207)
G1X 19236211982508211644805033459306273038523230481309141518540414163 G1X 19236211982508211644805033459306273038523230481309141518540414163
72091186292458482231912460243257247478684005448999746809691007995 72091186292458482231912460243257247478684005448999746809691007995
skipping to change at page 115, line 19 skipping to change at page 117, line 4
734638776755983021034212058415891288350265701101219981698 734638776755983021034212058415891288350265701101219981698
849086128138510420407 849086128138510420407
(=0xed921f3d 6ea4e452 dd06e783 782cbeb3 c5847a79 d9e6b993 (=0xed921f3d 6ea4e452 dd06e783 782cbeb3 c5847a79 d9e6b993
bd387cf5 feeddafe af8c038d f2732362 92724d37 273eedfc bd387cf5 feeddafe af8c038d f2732362 92724d37 273eedfc
f2ab2499 98a79434) f2ab2499 98a79434)
t2 365268494484253132875102676783560666625109899133767696106 t2 365268494484253132875102676783560666625109899133767696106
602723958322248430160651314075127005631031993354968950936 602723958322248430160651314075127005631031993354968950936
71875730862008188281 71875730862008188281
(=0x9ebc28c0 86176a1a c7f0cf71 ca5f2a8f 908bb27b e85c0bbd (=0x9ebc28c0 86176a1a c7f0cf71 ca5f2a8f 908bb27b e85c0bbd
1641c052 e542f7d3 88e18886 5afdca32 8df45408 8b6da28c 1641c052 e542f7d3 88e18886 5afdca32 8df45408 8b6da28c
0bc09d83 309ebb30), 0bc09d83 309ebb30),
where this representation is defined in Appendix K.5 and uses the 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 mapping of Appendix K.3.3 with the default square root function and
underlying 4-isogenous mapping between Edwards448 and Curve448 of underlying 4-isogenous mapping between Edwards448 and Curve448 of
Appendix N.2. Appendix N.2.
Appendix P. Random Integers in Z_n
Any probability distribution on the interval [0,N-1] can be converted
to a probability distribution on [0,n-1], via a suitable function
that maps inputs from the source distribution [0,N-1] to values in
the interval [0,n-1]. We consider three such functions, each with
the property that if the source distribution on [0,N-1] is
statistically close to the uniform distribution, then so is the
output distribution on [0,n-1]. In practical applications, one can
use these functions to convert the output of a cryptographically
strong random bit generator (where N is a power of two and after
conversion of the random bit string to an integer via the BS2I
mapping of Appendix I.2) to a pseudo-random integer in the interval
[0,n-1], where the bias is small if N is suitably picked.
We consider mappings that convert an output of the source
distribution to an integer in the interval [0,n-1] via modular
reduction (Appendix P.1), via scaling (Appendix P.2), or via a
membership test (Appendix P.3). For suitably picked N values and not
too poor source distributions, the first two mappings never fail and
any bias introduced by the conversion process can be made negligible
in practice, while the third mapping (if it does not fail) inflates
the bias by a small factor only in practice. (For details, see the
remarks following each of the mappings below.)
NOTE: Each of the mappings below may yield a zero output value. One
can modify each such mapping to always yield nonzero outputs, by
setting output x to 1 if the original mapping would yield x=0 for a
specific input y and leaving the mapping the same otherwise
(henceforth called the modified conversion function). This
modification has negligible impact on the bias and does yield a
conversion function to integers in the interval [1,n-1].
P.1. Conversion to Integers in Z_n via Modular Reduction
This function maps each integer y in the interval [0,N-1] to its
remainder modulo n, i.e., y is mapped to x:= y (mod n).
One can show that the bias introduced by this conversion function is
at most epsilon:=2*rho*(1-rho)/(N/n), where r:=N (mod n) and where
rho:=r/n. Details are out of scope.
Note that if n does not divide N, this invariably introduces some
bias, no matter the quality of the source distribution. In
particular, the statistical distance of the distribution on Z_n can
be much larger than the statistical distance of the source
distribution on Z_N, since the bias introduced by the modular
reduction step may be significantly larger than the bias of the
source distribution on Z_N if the value rho above is not close to
zero or one and if n/N is not sufficiently small. The maximum bias
is, however, easy to determine from n and N. In particular, if the
bit-length of N is sufficiently larger than that of n, the bias
introduced by the modular reduction operation is negligible in
practice. The same holds if N is close to a multiple of n (e.g., if
n is close to a power of two and the input distribution is generated
by a high-quality random bit generator with outputs of fixed bit-
length).
Note: In practice, one does not determine the maximum bias epsilon
from n and N, but rather specifies a required upper bound (usually
set to a value at most 2^{-64}) for epsilon and subsequently
determines the minimal value of N for which this upper bound indeed
applies, as a function of n.
P.2. Conversion to Integers in Z_n via Scaling
This function maps each integer y in the interval [0,N-1] to the
integer x:=floor(n*y/N), where the floor function rounds real numbers
downwards to an integer (i.e., floor(z) is the unique integer i for
which z is an element of the interval [i,i+1) of real numbers).
One can show that the bias introduced by this conversion function is
at most epsilon:=2*rho*(1-rho)/(N/n), where r:=N (mod n) and where
rho:=r/n. Details are out of scope.
The same remarks as in Appendix P.1 apply.
Note: this mapping corresponds to interpolation on the line with
endpoints (0,0) and (N,n), where values are truncated to integers.
The division operation in this conversion function reduces to a
binary string truncation operation if N is a power of two (which is
often the case in practice). See also [comm-FIPS-186-5], pp. 80-82.
P.3. Conversion to Integers in Z_n via the Discard Method
This function (defined for N at least n) is the identity map on the
interval [0,n-1] and fails for each integer y outside this interval.
One can show that the statistical distance of the distribution on Z_n
is at most roughly N/n times as large as the statistical distance of
the source distribution on Z_N (if the latter is relatively
negligible compared to n/N). Details are out of scope.
Note that, under the above conditions, if N:=2^m and if n has bit-
length m, this conversion function fails with probability less than
1/2 and, if it succeeds, does not inflate the statistical distance by
more than (roughly) a factor two.
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. 73 change blocks. 
223 lines changed or deleted 384 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/