 1/draftietflwigcurverepresentations12.txt 20201102 16:17:49.898608168 0800
+++ 2/draftietflwigcurverepresentations13.txt 20201102 16:17:50.030609973 0800
@@ 1,18 +1,18 @@
lwig R. Struik
InternetDraft Struik Security Consultancy
Intended status: Informational August 24, 2020
Expires: February 25, 2021
+Intended status: Informational November 2, 2020
+Expires: May 6, 2021
Alternative Elliptic Curve Representations
 draftietflwigcurverepresentations12
+ draftietflwigcurverepresentations13
Abstract
This document specifies how to represent Montgomery curves and
(twisted) Edwards curves as curves in shortWeierstrass form and
illustrates how this can be used to carry out elliptic curve
computations using existing implementations of, e.g., ECDSA and ECDH
using NIST prime curves. We also provide extensive background
material that may be useful for implementers of elliptic curve
cryptography.
@@ 33,21 +33,21 @@
InternetDrafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as InternetDrafts. The list of current Internet
Drafts is at https://datatracker.ietf.org/drafts/current/.
InternetDrafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use InternetDrafts as reference
material or to cite them other than as "work in progress."
 This InternetDraft will expire on February 25, 2021.
+ This InternetDraft will expire on May 6, 2021.
Copyright Notice
Copyright (c) 2020 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/licenseinfo) in effect on the date of
publication of this document. Please review these documents
@@ 60,187 +60,195 @@
Table of Contents
1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 5
2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 6
3. Use of Representation Switches . . . . . . . . . . . . . . . 6
4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 7
4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 8
4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 8
4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 9
 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
+ 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 10
5.2. Representation Conventions . . . . . . . . . . . . . . . 10
5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 10
6. Implementation Considerations . . . . . . . . . . . . . . . . 11
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 12
8. Security Considerations . . . . . . . . . . . . . . . . . . . 13
9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 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 . . . 15
10.1.1. Encoding of ShortWeierstrass Curves with COSE . . . 15
10.1.2. Encoding of ShortWeierstrass Curves with JOSE . . . 16
 10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 16
+ 10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 17
10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 17
10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 18
10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 19
10.3.1. Encoding of cofactor ECDH with COSE . . . . . . . . 20
10.3.2. Encoding of cofactor ECDH with JOSE . . . . . . . . 20
 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20
 11.1. IANA Considerations for Wei25519 . . . . . . . . . . . . 21
 11.1.1. COSE Elliptic Curves Registration . . . . . . . . . 21
 11.1.2. COSE Algorithms Registration (1/2) . . . . . . . . . 21
 11.1.3. COSE Algorithms Registration (2/2) . . . . . . . . . 21
 11.1.4. JOSE Elliptic Curves Registration . . . . . . . . . 22
 11.1.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 22
 11.1.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 23
 11.2. IANA Considerations for Wei448 . . . . . . . . . . . . . 23
 11.2.1. COSE Elliptic Curves Registration . . . . . . . . . 23
 11.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 24
 11.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 24
 11.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 24
 11.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 25
 11.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 25
 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 26
 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 26
 13.1. Normative References . . . . . . . . . . . . . . . . . . 26
 13.2. Informative References . . . . . . . . . . . . . . . . . 28
 Appendix A. Some (NonBinary) Elliptic Curves . . . . . . . . . 30
 A.1. Curves in ShortWeierstrass Form . . . . . . . . . . . . 30
 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 30
 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 30
 Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 31
 B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 31
 B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 33
 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 34
 C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 34
 C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 35
 C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 36
 Appendix D. Relationships Between Curve Models . . . . . . . . . 37
+ 11. Using Wei25519 and Wei448 with PKIX and CMS . . . . . . . . . 21
+ 11.1. Encoding of ShortWeierstrass Curves with PKIX . . . . . 21
+ 11.2. Encoding of ECDSA Instantiations with PKIX . . . . . . . 21
+ 11.3. Encoding of cofactor ECDH and Other Algorithms with
+ PKIX . . . . . . . . . . . . . . . . . . . . . . . . . . 21
+
+ 11.4. Encoding of EllipticCurveBased Algorithms with CMS . . 22
+ 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22
+ 12.1. OIDs for Use with PKIX and CMS . . . . . . . . . . . . . 22
+ 12.2. COSE/JOSE IANA Considerations for Wei25519 . . . . . . . 23
+ 12.2.1. COSE Elliptic Curves Registration . . . . . . . . . 23
+ 12.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 23
+ 12.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 23
+ 12.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 24
+ 12.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 24
+ 12.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 25
+ 12.3. COSE/JOSE IANA Considerations for Wei448 . . . . . . . . 25
+ 12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 25
+ 12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 26
+ 12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 26
+ 12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 26
+ 12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 27
+ 12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 27
+ 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 28
+ 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 28
+ 14.1. Normative References . . . . . . . . . . . . . . . . . . 28
+ 14.2. Informative References . . . . . . . . . . . . . . . . . 31
+ Appendix A. Some (NonBinary) Elliptic Curves . . . . . . . . . 32
+ A.1. Curves in ShortWeierstrass Form . . . . . . . . . . . . 33
+ A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 33
+ A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 33
+ Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 33
+ B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 34
+ B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 35
+ Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 36
+ C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 37
+ C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 37
+ C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 38
+ Appendix D. Relationships Between Curve Models . . . . . . . . . 39
D.1. Mapping between Twisted Edwards Curves and Montgomery
 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 37
 D.2. Mapping between Montgomery Curves and Weierstrass Curves 37
+ Curves . . . . . . . . . . . . . . . . . . . . . . . . . 40
+ D.2. Mapping between Montgomery Curves and Weierstrass Curves 40
D.3. Mapping between Twisted Edwards Curves and Weierstrass
 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 38
 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 39
 E.1. Curve Definition and Alternative Representations . . . . 39
 E.2. Switching between Alternative Representations . . . . . . 39
 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 41
 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 43
 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 43
 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 43
 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 44
 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 45
 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 47
 G.1. Further Alternative Representations . . . . . . . . . . . 47
 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 47
 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 48
 G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 49
 G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 49
 G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 56
 Appendix H. Point Compression . . . . . . . . . . . . . . . . . 62
 H.1. Point Compression for Weierstrass Curves . . . . . . . . 62
 H.2. Point Compression for Montgomery Curves . . . . . . . . . 63
 H.3. Point Compression for Twisted Edwards Curves . . . . . . 64
 Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 65
 I.1. Strings and String Operations . . . . . . . . . . . . . . 65
 I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 65
+ Curves . . . . . . . . . . . . . . . . . . . . . . . . . 41
+ Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 41
+ E.1. Curve Definition and Alternative Representations . . . . 42
+ E.2. Switching between Alternative Representations . . . . . . 42
+ E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 44
+ Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 46
+ F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 46
+ F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 46
+ F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 47
+ F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 48
+ Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 50
+ G.1. Further Alternative Representations . . . . . . . . . . . 50
+ G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 50
+ G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 51
+ G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 52
+ G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 52
+ G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 59
+ Appendix H. Point Compression . . . . . . . . . . . . . . . . . 65
+ H.1. Point Compression for Weierstrass Curves . . . . . . . . 65
+ H.2. Point Compression for Montgomery Curves . . . . . . . . . 66
+ H.3. Point Compression for Twisted Edwards Curves . . . . . . 67
+ Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 68
+ I.1. Strings and String Operations . . . . . . . . . . . . . . 68
+ I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 69
I.3. Conversion between Octet Strings and Integers (OS2I,
 I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 66
+ I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 69
I.4. Conversion between Octet Strings and Bit Strings (OS2BS,
 BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 66
+ BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 69
I.5. Conversion between Field Elements and Octet Strings
 (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 67
+ (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 70
I.6. Conversion between Elements of Z mod n and Octet Strings
 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 67
 I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 68
 I.8. Conversion Between Curve Points and Octet Strings . . . . 69
 Appendix J. Representation Examples Curve25519 Family Members . 71
 J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 72
 J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 74
 J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 75
 J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 78
 J.5. Example with Wei25519.3 . . . . . . . . . . . . . . . . 79
 Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 81
 K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 81
 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) . . . . . 81
 K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 82
 K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 82
 K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 82
 K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 83
 K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 84
 K.4. Mappings to HighOrder Curve Points . . . . . . . . . . . 85
 K.4.1. Mapping to HighOrder Points of Weierstrass Curve . . 85
 K.4.2. Mapping to HighOrder Points of Montgomery Curve . . 86
 K.4.3. Mapping to HighOrder Points of Twisted Edwards Curve 87
 K.5. Randomized Representation of Curve Points . . . . . . . . 88
 K.6. Completing the Mappings to Curve Points . . . . . . . . . 89
 Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 90
 L.1. Curve Definition and Alternative Representation . . . . . 90
 L.2. Switching Between Representations . . . . . . . . . . . . 90
 L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 91
 L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 92
 L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 92
 L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 93
 Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 94
 M.1. Curve Definition and Alternative Representations . . . . 94
 M.2. Switching between Alternative Representations . . . . . . 94
 M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 96

 Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 98
 N.1. Further Alternative Representations . . . . . . . . . . . 98
 N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 99
 N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 101
 N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 103
 N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 103
 N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 104
 Appendix O. Representation Examples Curve448 Family Members . . 105
 O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 105
 O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 108
 O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 110
 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
+ (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 70
+ I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 71
+ I.8. Conversion Between Curve Points and Octet Strings . . . . 72
+ Appendix J. Representation Examples Curve25519 Family Members . 74
+ J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 75
+ J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 77
+ J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 79
+ J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 82
+ J.5. Example with Wei25519.3 . . . . . . . . . . . . . . . . 84
+ Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 86
+ K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 86
+ K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 86
+ K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 86
+ K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 87
+ K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 87
+ K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 87
+ K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 89
+ K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 90
+ K.4. Mappings to HighOrder Curve Points . . . . . . . . . . . 90
+ K.4.1. Mapping to HighOrder Points of Weierstrass Curve . . 90
+ K.4.2. Mapping to HighOrder Points of Montgomery Curve . . 91
+ K.4.3. Mapping to HighOrder Points of Twisted Edwards Curve 93
+ K.5. Randomized Representation of Curve Points . . . . . . . . 94
+ K.6. Completing the Mappings to Curve Points . . . . . . . . . 95
+ Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 96
+ L.1. Curve Definition and Alternative Representation . . . . . 96
+ L.2. Switching Between Representations . . . . . . . . . . . . 97
+ L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 97
+ L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 99
+ L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 99
+ L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 99
+ Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 100
+ M.1. Curve Definition and Alternative Representations . . . . 100
+ M.2. Switching between Alternative Representations . . . . . . 101
+ M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 102
+ Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 105
+ N.1. Further Alternative Representations . . . . . . . . . . . 105
+ N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 105
+ N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 108
+ N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 110
+ N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 110
+ N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 111
+ Appendix O. Representation Examples Curve448 Family Members . . 111
+ O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 112
+ O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 115
+ O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 118
+ O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 121
+ O.5. Example with Wei448.3 . . . . . . . . . . . . . . . . . 123
+ O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 126
+ Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 129
+ P.1. Conversion to Integers in Z_n via Modular Reduction . . . 129
+ P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 130
+ P.3. Conversion to Integers in Z_n via the Discard Method . . 130
+ Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 131
1. Fostering Code Reuse with New Elliptic Curves
Elliptic curves can be represented using different curve models.
Recently, IETF standardized elliptic curves that are claimed to have
better performance and improved robustness against "real world"
 attacks than curves represented in the traditional "short"
 Weierstrass curve model. These socalled CFRG curves [RFC7748] use
 the Montgomery curve model and the model of twisted Edwards curves.
+ attacks than curves represented in the traditional shortWeierstrass
+ curve model. These socalled CFRG curves [RFC7748] use the
+ Montgomery curve model and the model of twisted Edwards curves.
In this document, we specify these curves using the traditional
 "short" Weierstrass model and also define how to efficiently switch
+ shortWeierstrass model and also define how to efficiently switch
between representations in these different curve models. In
particular, we specify Wei25519, which allows an alternative
representation of points of Curve25519 (a Montgomery curve) and of
points of Edwards25519 (a twisted Edwards curve), as points of a
 corresponding "short" Weierstrass curve. Similarly, we specify
 Wei448, which allows an alternative representation of points of
 Curve448 (a Montgomery curve) and of points of Ed448 (an Edwards
 curve), as points of a corresponding "short" Weierstrass curve.
+ corresponding shortWeierstrass curve. Similarly, we specify Wei448,
+ which allows an alternative representation of points of Curve448 (a
+ Montgomery curve) and of points of Ed448 (an Edwards curve), as
+ points of a corresponding shortWeierstrass curve.
Use of Wei25519 and Wei448 allows easy definition of new
instantiations of signature schemes and key agreement schemes already
specified for traditional NIST prime curves, thereby allowing easy
integration with existing specifications, such as NIST SP 80056a
[SP80056a], FIPS Pub 1864 [FIPS1864], and ANSI X9.622005
[ANSIX9.62], and fostering code reuse on platforms that already
implement some of these schemes using elliptic curve arithmetic for
 curves in "short" Weierstrass form (see Appendix C.1). To illustrate
+ curves in shortWeierstrass form (see Appendix C.1). To illustrate
this, we specify how to use Wei25519 and Wei448 with cofactor ECDH
and with ECDSA, thereby giving rise to the key agreement schemes
ECDH25519 and ECDH448 and the signature schemes ECDSA25519 and
ECDSA448. In all these cases, implementors may use the curve
arithmetic for the curve model of their choosing (where they can
efficiently switch between representations in different curve models,
if required).
For ease of exposition, we consider Wei25519 first and introduce
Wei448 simply as an illustration of how to create other "offspring"
@@ 383,29 +391,29 @@
curve Wei25519, where the signature (r,s) is represented as the
rightconcatenation of the integers r and s, each represented as
fixedsize strings with tight MSB/msb ordering (see Appendix I).
4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others)
Any existing specification of cryptographic schemes using elliptic
curves in Weierstrass form and that allows introduction of a new
elliptic curve (here: Wei25519) is amenable to similar constructs,
thus spawning "offspring" protocols, simply by instantiating these
 using the new curve in "short" Weierstrass form, thereby allowing
 code and/or specifications reuse and, for implementations that so
 desire, carrying out curve computations "under the hood" on
 Montgomery curve and twisted Edwards curve cousins hereof (where
 these exist). This would simply require definition of a new object
 identifier for any such envisioned "offspring" protocol. This could
 significantly simplify standardization of schemes and help keeping at
 bay the resource and maintenance cost of implementations supporting
 algorithm agility [RFC7696].
+ using the new curve in shortWeierstrass form, thereby allowing code
+ and/or specifications reuse and, for implementations that so desire,
+ carrying out curve computations "under the hood" on Montgomery curve
+ and twisted Edwards curve cousins hereof (where these exist). This
+ would simply require definition of a new object identifier for any
+ such envisioned "offspring" protocol. This could significantly
+ simplify standardization of schemes and help keeping at bay the
+ resource and maintenance cost of implementations supporting algorithm
+ agility [RFC7696].
We illustrate the construction of such offspring protocols for
Curve448, another Montgomery curve recently standardized by IETF (see
[RFC7748]). Similar to the case with Curve25519, one can represent
points of this curve via different curve models, viz. as points of an
Edwards curve (Ed448) or as points of a shortWeierstrass curve
(Wei448). For the specification of Wei448 and its relationship to
Curve448 and Ed448, see Appendix M. As with ECDH25519, one can now
easily define a NISTcompliant version of cofactor DiffieHellman
key agreement (denoted by ECDH448), by simply reusing the example of
@@ 610,21 +617,23 @@
cryptographic scheme that may include processing steps that depend on
the representation conventions used (such as with, e.g., key
derivation following key establishment). These schemes should
(obviously) unambiguously specify fixed representations of each input
and output (e.g., representing each elliptic curve point always in
shortWeierstrass form and in uncompressed tight MSB/msb format).
To prevent crossprotocol attacks, private keys SHOULD only be used
with one cryptographic scheme. Private keys MUST NOT be reused
between Ed25519 (as specified in [RFC8032]) and ECDSA25519 (as
 specified in Section 4.3).
+ specified in Section 4.3). Similarly, private keys MUST NOT be
+ reused between Ed448 (as specified in [RFC8032]) and ECDSA448 (as
+ specified in Section 4.4).
To prevent intraprotocol crossinstantiation attacks, ephemeral
private keys MUST NOT be reused between instantiations of ECDSA25519
or ECDSA448.
9. Privacy Considerations
The transformations between different curve models described in this
document are publicly known and, therefore, do not affect privacy
provisions.
@@ 931,34 +939,115 @@
name of the curve used with this particular instantiation of
ECDH.
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
instantiation of cofactor ECDH and the "crv" parameter MUST be set
to the (unique) name of the corresponding curve; if the "key_ops"
field is present, it MUST include "derive shared secret" for the
private key.
11. IANA Considerations
+11. Using Wei25519 and Wei448 with PKIX and CMS
+
+ This section illustrates how to use the curves Wei25519 and Wei448
+ with ECDH and ECDSA with PKIX certificates (see [RFC5280] and
+ [RFC5480]) and with CMS (see [RFC5652] and [RFC5753]).
+
+11.1. Encoding of ShortWeierstrass Curves with PKIX
+
+ The namedCurve field in the ECParameters field in the
+ SubjectPublicKeyInfo structure [RFC5280] indicates the elliptic curve
+ domain parameters for a specific curve, via a unique name of the
+ curve in question (where these are the unique object identifiers id
+ Wei25519 for the curve Wei25519 and idWei448 for the curve Wei448).
+
+ Affine and compressed curve points are encoded using the "SEC1"
+ representation (see Note 2 of Appendix I.8), using the tight MSB/msb
+ ordering conventions. This is consistent with the representation in
+ Section 2.2 of [RFC5480], after correcting for the error in [SEC1]
+ (for the correction, see Note in Appendix H.1).
+
+11.2. Encoding of ECDSA Instantiations with PKIX
+
+ ECDSA25519, as defined in Section 4.3, is the instantiation of ECDSA
+ with SHA256 and with curve Wei25519. With [RFC5480], ECDSA can be
+ instantiated with suitable elliptic curves and hash functions. This
+ allows support for ECDSA25519 by instantiating ECDSA with the curve
+ Wei25519 and the hash function SHA256, where curve Wei25519 is
+ identified by its object identifier idwei25519 (see Section 11.1),
+ where ECDSA with SHA256 is identified by the object identifier id
+ ecdsawithSHA256 (see [RFC5480]), and where all other aspects are
+ specified in [RFC5480].
+
+ ECDSA448, as defined in Section 4.4, is the instantiation of ECDSA
+ with SHAKE256 with output size d=512 bits and with curve Wei448.
+ With [RFC5480], ECDSA can be instantiated with suitable elliptic
+ curves and hash functions. This allows support for ECDSA448 by
+ instantiating ECDSA with the curve Wei448 and the hash function
+ SHAKE256 with output size of d=512 bits, where curve Wei448 is
+ identified by its object identifier idwei448 (see Section 11.1),
+ where ECDSA with SHAKE256 with output size of d=512 bits is
+ identified by the object identifier idecdsawithshake256 (see
+ [RFC8692]), and where all other aspects are specified in [RFC5480].
+
+11.3. Encoding of cofactor ECDH and Other Algorithms with PKIX
+
+ With [RFC5480], the algorithm field in the SubjectPublicKeyInfo
+ structure indicates the algorithm and the elliptic curve domain
+ parameters for a specific curve, where that specification defines
+ three algorithm identifiers (viz. idecPublicKey, idecdh, and id
+ ecmqv). Each of these algorithms can be instantiated with suitable
+ alliptic curves, thereby allowing support for their use with the
+ curves Wei25519 and Wei448, where these curves are identified by
+ their unique object identifiers idwei25519 and idwei448,
+ respectively, and where all other aspects are specified in [RFC5480].
+
+11.4. Encoding of EllipticCurveBased Algorithms with CMS
+
+ With [RFC5753], ellipticcurve based algorithms should use one of the
+ elliptic curve domain parameters specified in [RFC5480], where the
+ unique name of each such curve is identified by the object identifier
+ of this curve defined in that document. Each of these algorithms can
+ be instantiated with suitable elliptic curves, thereby allowing
+ support for their use with the curves Wei25519 and Wei448, where
+ these curves are identified by their unique object identifiers id
+ wei25519 and idwei448, respectively, and where all other aspects are
+ specified in [RFC5753].
+
+12. IANA Considerations
Code points are requested for curves Wei25519 and Wei448 and their
use with ECDSA and cofactor ECDH, using the representation
conventions of this document.
New code points would be required in case one wishes to specify one
or more other "offspring" protocols beyond those exemplified in
Section 4.4. Specification hereof is, however, outside the scope of
the current document.
11.1. IANA Considerations for Wei25519
+12.1. OIDs for Use with PKIX and CMS
11.1.1. COSE Elliptic Curves Registration
+ This section registers the following object identifiers for the
+ curves introduced in this document:
+
+ a. idWei25519 OBJECT IDENTIFIER ::= TBD (Requested value: {iso(1)
+ identifiedorganization(3) thawte (101) 108 });
+
+ b. idWei448 OBJECT IDENTIFIER ::= TBD (Requested value: {iso(1)
+ identifiedorganization(3) thawte (101) 109 }).
+
+ For a description of how these are used with PKIX certificates and
+ CMS, see Section 11.
+
+12.2. COSE/JOSE IANA Considerations for Wei25519
+
+12.2.1. COSE Elliptic Curves Registration
This section registers the following value in the IANA "COSE Elliptic
Curves" registry [IANA.COSE.Curves].
Name: Wei25519;
Value: TBD (Requested value: 1);
Key Type: EC2 or OKP;
@@ 966,118 +1055,118 @@
Change Controller: IESG;
Reference: specified in Appendix E.3 of this specification; for
encodings, see Section 10.1;
Recommended: Yes.
(Note that The "kty" value for Wei25519 may be "EC2" or "OKP".)
11.1.2. COSE Algorithms Registration (1/2)
+12.2.2. COSE Algorithms Registration (1/2)
This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDSA25519;
 Value: TBD (Requested value: 1);
+ Value: TBD (Requested value: 9);
Description: ECDSA with SHA256 and curve Wei25519;
Change Controller: IESG;
Reference: specified in Section 4.3 of this specification; for
encodings, see Section 10.2;
Recommended: Yes.
11.1.3. COSE Algorithms Registration (2/2)
+12.2.3. COSE Algorithms Registration (2/2)
This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDH25519;
 Value: TBD (Requested value: 2);
+ Value: TBD (Requested value: 24);
Description: NISTcompliant cofactor DiffieHellman w/ curve
Wei25519 and key derivation function HKDF SHA256;
Change Controller: IESG;
Reference: specified in Section 4.1 of this specification; for
encodings, see Section 10.3;
Recommended: Yes.
11.1.4. JOSE Elliptic Curves Registration
+12.2.4. JOSE Elliptic Curves Registration
This section registers the following value in the IANA "JSON Web Key
Elliptic Curve" registry [IANA.JOSE.Curves].
Curve Name: Wei25519;
Curve Description: shortWeierstrass curve Wei25519;
JOSE Implementation Requirements: Optional;
Change Controller: IESG;
Reference: specified in Appendix E.3 of this specification; for
encodings, see Section 10.1.
(Note that The "kty" value for Wei25519 may be "EC" or "OKP".)
11.1.5. JOSE Algorithms Registration (1/2)
+12.2.5. JOSE Algorithms Registration (1/2)
This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDSA25519;
Algorithm Description: ECDSA using SHA256 and curve Wei25519;
Algorithm Usage Locations: alg;
JOSE Implementation Requirements: Optional;
Change Controller: IESG;
Reference: specified in Section 4.3 of this specification; for
encodings, see Section 10.2;
Algorithm Analysis Document(s): Section 4.3 of this specification.
11.1.6. JOSE Algorithms Registration (2/2)
+12.2.6. JOSE Algorithms Registration (2/2)
This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDH25519;
Algorithm Description: NISTcompliant cofactor DiffieHellman w/
curve Wei25519 and key derivation function HKDF SHA256;
Algorithm Usage Locations: alg;
JOSE Implementation Requirements: Optional;
Change Controller: IESG;
Reference: specified in Section 4.1 of this specification; for
encodings, see Section 10.3;
Algorithm Analysis Document(s): Section 4.1 of this specification.
11.2. IANA Considerations for Wei448
+12.3. COSE/JOSE IANA Considerations for Wei448
11.2.1. COSE Elliptic Curves Registration
+12.3.1. COSE Elliptic Curves Registration
This section registers the following value in the IANA "COSE Elliptic
Curves" registry [IANA.COSE.Curves].
Name: Wei448;
Value: TBD (Requested value: 2);
Key Type: EC2 or OKP;
@@ 1085,127 +1174,127 @@
Change Controller: IESG;
Reference: specified in Appendix M.3 of this specification; for
encodings, see Section 10.1;
Recommended: Yes.
(Note that The "kty" value for Wei448 may be "EC2" or "OKP".)
11.2.2. COSE Algorithms Registration (1/2)
+12.3.2. COSE Algorithms Registration (1/2)
This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDSA448;
 Value: TBD (Requested value: 47);
+ Value: TBD (Requested value: 48);
Description: ECDSA with SHAKE256 and curve Wei448;
Change Controller: IESG;
Reference: specified in Section 4.4 of this specification; for
encodings, see Section 10.1;
Recommended: Yes.
11.2.3. COSE Algorithms Registration (2/2)
+12.3.3. COSE Algorithms Registration (2/2)
This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDH448;
 Value: TBD (Requested value: 48);
+ Value: TBD (Requested value: 49);
Description: NISTcompliant cofactor DiffieHellman w/ curve Wei448
and key derivation function HKDF SHA512;
Change Controller: IESG;
Reference: specified in Section 4.4 of this specification; for
encodings, see Section 10.1; for key derivation, see
Section 11.1 of [RFC8152];
Recommended: Yes.
11.2.4. JOSE Elliptic Curves Registration
+12.3.4. JOSE Elliptic Curves Registration
This section registers the following value in the IANA "JSON Web Key
Elliptic Curve" registry [IANA.JOSE.Curves].
Curve Name: Wei448;
Curve Description: shortWeierstrass curve Wei448;
JOSE Implementation Requirements: Optional;
Change Controller: IESG;
Reference: specified in Appendix M.3 of this specification; for
encodings, see Section 10.1.
(Note that The "kty" value for Wei448 may be "EC" or "OKP".)
11.2.5. JOSE Algorithms Registration (1/2)
+12.3.5. JOSE Algorithms Registration (1/2)
This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDSA448;
Algorithm Description: ECDSA using SHAKE256 and curve Wei448;
Algorithm Usage Locations: alg;
JOSE Implementation Requirements: Optional;
Change Controller: IESG;
Reference: specified in Section 4.4 of this specification; for
encodings, see Section 10.2;
Algorithm Analysis Document(s): Section 4.4 of this specification.
11.2.6. JOSE Algorithms Registration (2/2)
+12.3.6. JOSE Algorithms Registration (2/2)
This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDH448;
Algorithm Description: NISTcompliant cofactor DiffieHellman w/
curve Wei448;
Algorithm Usage Locations: alg;
JOSE Implementation Requirements: Optional;
Change Controller: IESG;
Reference: specified in Section 4.4 of this specification; for
encodings, see Section 10.3;
Algorithm Analysis Document(s): Section 4.4 of this specification.
12. Acknowledgements
+13. Acknowledgements
Thanks to Nikolas Rosener for discussions surrounding implementation
details of the techniques described in this document and to Phillip
HallamBaker for triggering inclusion of verbiage on the use of
Montgomery ladders with recovery of the ycoordinate. Thanks to
Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews.
13. References
+14. References
13.1. Normative References
+14.1. Normative References
[ANSIX9.62]
ANSI X9.622005, "Public Key Cryptography for the
Financial Services Industry: The Elliptic Curve Digital
Signature Algorithm (ECDSA)", American National Standard
for Financial Services, Accredited Standards Committee X9,
Inc, Anapolis, MD, 2005.
[FIPS1804]
FIPS 1804, "Secure Hash Standard (SHS), Federal
@@ 1221,37 +1310,57 @@
[FIPS202]
FIPS 202, "SHA3 Standard: PermutationBased Hash and
ExtendableOutput Functions, Federal Information
Processing Standards Publication 202", US Department of
Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, August 2015.
[ID.ietfcoserfc8152bisalgs]
Schaad, J., "CBOR Object Signing and Encryption (COSE):
 Initial Algorithms", draftietfcoserfc8152bisalgs11
 (work in progress), July 2020.
+ Initial Algorithms", draftietfcoserfc8152bisalgs12
+ (work in progress), September 2020.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
.
[RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data
Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006,
.
+ [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S.,
+ Housley, R., and W. Polk, "Internet X.509 Public Key
+ Infrastructure Certificate and Certificate Revocation List
+ (CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008,
+ .
+
+ [RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk,
+ "Elliptic Curve Cryptography Subject Public Key
+ Information", RFC 5480, DOI 10.17487/RFC5480, March 2009,
+ .
+
[RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography
(ECC) Brainpool Standard Curves and Curve Generation",
RFC 5639, DOI 10.17487/RFC5639, March 2010,
.
+ [RFC5652] Housley, R., "Cryptographic Message Syntax (CMS)", STD 70,
+ RFC 5652, DOI 10.17487/RFC5652, September 2009,
+ .
+
+ [RFC5753] Turner, S. and D. Brown, "Use of Elliptic Curve
+ Cryptography (ECC) Algorithms in Cryptographic Message
+ Syntax (CMS)", RFC 5753, DOI 10.17487/RFC5753, January
+ 2010, .
+
[RFC7049] Bormann, C. and P. Hoffman, "Concise Binary Object
Representation (CBOR)", RFC 7049, DOI 10.17487/RFC7049,
October 2013, .
[RFC7515] Jones, M., Bradley, J., and N. Sakimura, "JSON Web
Signature (JWS)", RFC 7515, DOI 10.17487/RFC7515, May
2015, .
[RFC7518] Jones, M., "JSON Web Algorithms (JWA)", RFC 7518,
DOI 10.17487/RFC7518, May 2015,
@@ 1282,39 +1391,45 @@
.
[RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)",
RFC 8152, DOI 10.17487/RFC8152, July 2017,
.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, .
+ [RFC8692] Kampanakis, P. and Q. Dang, "Internet X.509 Public Key
+ Infrastructure: Additional Algorithm Identifiers for
+ RSASSAPSS and ECDSA Using SHAKEs", RFC 8692,
+ DOI 10.17487/RFC8692, December 2019,
+ .
+
[SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0",
Standards for Efficient Cryptography, , June 2009.
[SEC2] SEC2, "SEC 2: Elliptic Curve Cryptography, Version 2.0",
Standards for Efficient Cryptography, , January 2010.
[SP80056a]
NIST SP 80056a, "Recommendation for PairWise Key
Establishment Schemes Using Discrete Log Cryptography,
Revision 3", US Department of Commerce/National Institute
of Standards and Technology, Gaithersburg, MD, April 2018.
[SP80056c]
NIST SP 80056c, "Recommendation for KeyDerivation
Methods in KeyEstablishment Schemes, Revision 1", US
Department of Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, April 2018.
13.2. Informative References
+14.2. Informative References
[commFIPS1865]
FIPS 1865, "Public Comments Received on Draft FIPS Pub
1865", 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
Cryptography", Cambridge University Press, Lecture Notes
Series 265, July 1999.
@@ 1460,28 +1575,28 @@
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 and l
is the smallest positive integer so that l*P=O. The order of curve E
is the cardinality of the set of its points, commonly denoted by E.
A curve is cyclic if it is generated by some point of this curve.
All curves of prime order are cyclic, while all curves of order h*n,
where n is a large prime number and where h is a small number (the
socalled cofactor), have a large cyclic subgroup of prime order n.
In this case, a generator of order n is called a base point, commonly
denoted by G, while a point of order dividing h is said to be in the
 small subgroup. For curves of prime order, this small subgroup is
 the singleton set, consisting of only the identity element O. A
 point that is not in the small subgroup is said to be a highorder
 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 highorder 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.)
+ small subgroup (or said to be a loworder point). For curves of
+ prime order, this small subgroup is the singleton set, consisting of
+ only the identity element O. A point that is not in the small
+ subgroup is said to be a highorder point (since it has order at
+ least n). A point P of the curve is in the small subgroup if h*P=O
+ (and is a highorder 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
a unique integer k in the interval [0, l1] so that R=k*P, where l is
the order of P. This number is called the discrete logarithm of R to
the base P. The discrete logarithm problem is the problem of finding
the discrete logarithm of R to the base P for any two points P and R
of the curve, if such a number exists.
If P is a fixed base point G of the curve, the pair (k, R:=k*G) is
commonly called a publicprivate key pair, the integer k the private
@@ 2949,20 +3065,26 @@
where alpha:=X^3+a*X+b. If alpha is not a square in GF(q), this
equation does not have a solution in GF(q) and the ordered pair (X,
t) does not correspond to a point of this curve. Otherwise, there
are two solutions, viz. Y=sqrt(alpha) and Y. If alpha is a nonzero
element of GF(q), one can uniquely recover the Ycoordinate for which
par(Y):=t and, thereby, the point P:=(X, Y). This is also the case
if alpha=0 and t=0, in which case Y=0 and the point P has order two.
However, if alpha=0 and t=1, the ordered pair (X, t) does not
correspond to the outcome of the point compression function.
+ NOTE: the procedure above corrects an error in the point
+ decompression procedure for Weierstrass curves defined over the prime
+ field GF(p) of [SEC1], which erroneously converts a purported
+ compressed point for which alpha=0 and t=1 (in the notation above),
+ to the ordered pair (0,p).
+
We extend the definition of the point compression function to all
points of the curve W_{a,b}, by associating the (nonaffine) point at
infinity O with any ordered pair compr(O):=(X,0), where X is any
element of GF(q) for which alpha:=X^3+a*X+b is not a square in GF(q),
and recover this point accordingly. In this case, the point at
infinity O can be represented by any ordered pair (X,0) of elements
of GF(q) for which X^3+a*X+b is not a square in GF(q). Note that
this ordered pair does not satisfy the defining equation of the curve
in question. An application may fix a specific suitable value of X
or choose multiple such values and use this to encode additonal
@@ 3084,41 +3205,42 @@
There is a 11 correspondence between bit strings of length l and
integers in the interval [0, 2^l), where the bit string
X:=str(x_{l1}, x_{l2}, ..., x_1, x_0) corresponds to the integer
x:=x_{l1}*2^{l1} + x_{l2}*2^{l2} + ... + x_1*2 + x_0*1. (If l=0,
the empty bit string corresponds to the integer zero.) Note that
while the mapping from bit strings to integers is uniquely defined,
the inverse mapping from integers to bit strings is not, since any
nonnegative integer smaller than 2^t can be represented as a bit
string of length at least t (due to leading zero coefficients in base
2 representation). The latter representation is called tight if the
 bit string representation has minimal length. This defines the
 mapping BS2I from bit strings to integers and the mapping I2BS(x,l)
 from nonnegative integers smaller than 2^l to bit strings of length
 l.
+ bit string representation has minimal length (the socalled bit
+ length of the integer in question). This defines the mapping BS2I
+ from bit strings to integers and the mapping I2BS(x,l) from non
+ negative integers smaller than 2^l to bit strings of length l.
I.3. Conversion between Octet Strings and Integers (OS2I, I2OS)
There is a 11 correspondence between octet strings of length l and
integers in the interval [0, 256^l), where the octet string
X:=str(X_{l1}, X_{l2}, ..., X_1, X_0) corresponds to the integer
x:=X_{l1}*256^{l1} + X^{l2}*256^{l2} + ... + X_1*256 + X_0*1.
(If l=0, the empty string corresponds to the integer zero.) Note
that while the mapping from octet strings to integers is uniquely
defined, the inverse mapping from integers to octet strings is not,
since any nonnegative integer smaller than 256^t can be represented
as an octet string of length at least t (due to leading zero
coefficients in base 256 representation). The latter representation
 is called tight if the octet string representation has minimal
 length. This defines the mapping OS2I from octet strings to integers
 and the mapping I2OS(x,l) from nonnegative integers smaller than
 256^l to octet strings of length l.
+ is called tight if the octet string representation has minimal length
+ (the socalled bytelength of the integer in question). This defines
+ the mapping OS2I from octet strings to integers and the mapping
+ I2OS(x,l) from nonnegative integers smaller than 256^l to octet
+ strings of length l.
I.4. Conversion between Octet Strings and Bit Strings (OS2BS, BS2OS)
There is a 11 correspondence between octet strings of length l and
bit strings of length 8*l, where the octet string X:=str(X_{l1},
X_{l2}, ..., X_1, X_0) corresponds to the rightconcatenation of the
8bit strings x_{l1}, x_{l2}, ..., x_1, x_0, where each octet X_i
corresponds to the 8bit string x_i according to the mapping of
Appendix I.2 above. Note that the mapping from octet strings to bit
strings is uniquely defined and so is the inverse mapping from bit
@@ 3302,21 +3424,22 @@
affine points as above (as octet string), but prepends this with the
1octet prefix 0x04, and represents the identity element of the curve
as the 1octet string 0x00. This variablesize point representation
has the property that its 1octet prefix identifies whether it
encodes an affine curve point, a compressed point (including parity
bit), or the identity element, while the remainder of this
representation uniquely determines the curve point's value. While
the description in [SEC1] only applies to Weierstrass curves, the
description above applies to each of the curve models we consider
(i.e., these apply to Montgomery curves and twisted Edwards curves as
 well). Collectively, we simply refer to this as the "SEC1" point
+ well) and also applies to curves defined over extension fields.
+ Collectively, we simply refer to this as the "SEC1" point
representation.
Note that elements of a prime field GF(p), where p is a 255bit prime
number, have a tight representation as a 32octet string, where a
fixed bit position is always set to zero. (This is the leftmost bit
position of this octet string if one follows the MSB/msb
representation conventions.) This allows the parity bit of a
compressed point (see Appendix H) to be encoded in this bit position
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
@@ 3453,27 +3576,45 @@
msb order is given by
t1 409531317901122685707535715924445398426503483189854716584
37762538294289253464
(=0x5844b232 8c4586dc 62f593c5 599c2a8c e61ba893 bb052de6
77510a42 b3a68a5a)
t2 451856098332889407421278004628150814449259902023388533929
08848927625430980881

(=0x11598452 e65138dc ce948d7e d8f46a18 b640722c 8e170957
751b7729 1b26e663),
where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.2 with the default square root function.
+ This representation can also be expressed in tight LSB/msb order as
+ the pair ((u1,s1),(u2,s2)), where (s1,s2):=(0,0) and where
+
+ u1 545187339829846945538068364048581821018455714632595988990
+ 2000416117254237099
+
+ (=0xabab17e4 f1dbafb1 ede0c4b3 bedb7734 9c85f2a7 917c5edf
+ ad4bd96a a7a60d0c)
+
+ u2 236263468848031270223854046645772980064576816578949344957
+ 7618817248044779847
+
+ (=0x47099c3e 9b5cc8fe eaac5db0 6fb413fa b3ef4516 7bfcdc4b
+ 8368f22e 2f343905),
+
+ where this uses the default completed mapping defined in Appendix K.6
+ and the mapping of Appendix K.4.2 (with the default square root
+ function).
+
J.2. Example with Edwards25519
Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Edwards25519:
x 25301662348702136092602268236183361085863932475593120475382959053
365387223252
(=0x37f03bc0 1070ed12 d3218f8b ba1abb74 fd6b94eb 62033d09
83851e21 d6a460d4).
@@ 3543,20 +3683,39 @@
05479716220480287974
(=0x672e36c5 ae353073 cdfac343 e8297b05 1b010d0f 5b1016db
dd4baf54 28068926),
where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.3 with the default square root function and
underlying isomorphic mapping between Edwards25519 and Curve25519 of
Appendix E.2.
+ This representation can also be expressed in tight LSB/lsb order as
+ the pair ((u1,s1),(u2,s2)), where (s1,s2):=(0,1) and where
+
+ u1 224462652213914013165861386626523724285418072774741333590
+ 46191305234585192644
+
+ (=0x2311ee45 c788a81b 7fcd7ae1 c6982d7b 537011fd d49e2eb4
+ 62b9c08c 5344058c)
+
+ u2 103951215490226901552766901992808623194604650181530822362
+ 9026508474142603215
+
+ (=0xf3ed475b fd95335c 3a0ceb7e 319f8d3c cc651d5b 17eb4439
+ e3b25693 0bea3240),
+
+ where this uses the default completed mapping defined in Appendix K.6
+ and the mapping of Appendix K.4.3 (with the default square root
+ function).
+
J.3. Example with Wei25519
Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519:
X 14428294459702615171094958724191825368445920488283965295163094662
783879239338
(=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7
2a41cf12 629e56aa).
@@ 3653,20 +3813,39 @@
t2 213890166610228613105792710708385961712211281744756216061
11930888059603107561
(=0x2f49c121 8fed7912 031157ee ae066507 a972320b 6180e267
4025b006 2e67bee9),
where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.1 with the default square root function.
+ This representation can also be expressed in tight MSB/msb order as
+ the pair ((u1,s1),(u2,s2)), where (s1,s2):=(1,0) and where
+
+ u1 520092833970966289810117689157951302936446424265230088162
+ 65117106436465991934
+
+ (=0x72fc3612 b18d2644 c2a85b3b dd66cd58 07ebf07b 2131b77d
+ 6d7579da 5efba0fe)
+
+ u2 134005949856425653115405838878115551263976839535650697250
+ 78991786686428785368
+
+ (=0x1da077cd 6fa87515 731029a8 bd88da6a 34e38b83 51191edf
+ 8a3b92d7 ba24aad8),
+
+ where this uses the default completed mapping defined in Appendix K.6
+ and the mapping of Appendix K.4.1 (with the default square root
+ function).
+
J.4. Example with Wei25519.2
Pw2=(X, Y), k*Pw2=(X1, Y1), and (k+1)*Pw2=(X2, Y2) with Wei25519.2:
X 17830493209951148331008014701079988862634531394137235438571836389
227198459763
(=0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c
f21c8672 d1ecaf73).
@@ 3729,20 +3908,39 @@
t2 361115271162391608083096560179337391059615651279123199921
18531180247832114098
(=0x4fd66668 e7174775 de44c852 92df8cfe b9832ef8 2570b3b8
fe5ec21a b2d4b3b2),
where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.1 with the default square root function.
+ This representation can also be expressed in tight MSB/msb order as
+ the pair ((u1,s1),(u2,s2)), where (s1,s2):=(1,0) and where
+
+ u1 138215499313862453472915174740765454800858627563772726738
+ 62176256261157017834
+
+ (=0x1e8eb854 2ce139f7 fdbf2059 ac257c89 d7e2e5fe 9c4b97e6
+ 7656d42c 590bd8ea)
+
+ u2 528750192685398685104289021251049791405104665681275304080
+ 7706116783659458600
+
+ (=0x0bb09eba b0470a84 0ce1ba90 0aeab208 7e8d4760 1309d7af
+ e3712e1f 2232a028),
+
+ where this uses the default completed mapping defined in Appendix K.6
+ and the mapping of Appendix K.4.1 (with the default square root
+ function).
+
J.5. Example with Wei25519.3
Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei25519.3:
X 14780197759513083469009623947734627174363231692126610860256057394
455099634096
(=0x20ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00
eb4c9272 03ca71b0).
@@ 3804,26 +4003,45 @@
t2 269945781324580189815142015663892935722419453863927287235
57891665397640090729
(=0x3bae63c8 70f60de0 c2e35f94 d24220f1 bb6efd00 37625869
f84923de ff4c5469),
where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.1 with the default square root function.
+ This representation can also be expressed in tight MSB/msb order as
+ the pair ((u1,s1),(u2,s2)), where (s1,s2):=(1,1) and where
+
+ u1 273592510979600674027837477146355037032732195078153389134
+ 81162438438522584713
+
+ (=0x3c7cc990 81eed784 9ca746d7 c479a902 ce9de65f 1150e7b9
+ c87d08d2 9785fe89)
+
+ u2 271488765024747755704729103260177059745349171282146823458
+ 00069381584030663589
+
+ (=0x3c05b835 1283fca7 705eba74 1e6b853e db3ed5dc d1891daa
+ c1643d8d d63a03a5),
+
+ where this uses the default completed mapping defined in Appendix K.6
+ and the mapping of Appendix K.4.1 (with the default square root
+ function).
+
Appendix K. Auxiliary Functions
This section illustrates how one could implement common routines,
such as taking square roots and inverses in finite fields, and how to
map field elements to curve points and to curve points that avoid
 some outliers.
+ outlier points in the small subgroup.
K.1. Square Roots in GF(q)
Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see
Appendix K.1.1) or if q = 5 (mod 8) (see Appendix K.1.2). Details on
how to compute square roots for other values of q are out of scope.
If square roots are easy to compute in GF(q), then so are these in
GF(q^2).
K.1.1. Square Roots in GF(q), where q = 3 (mod 4)
@@ 3893,49 +4111,49 @@
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
to the point P(t):=(X, Y);
b. If f(X) is not a square in GF(q) and Y':=sqrt(f(X')), then t is
mapped to the point P(t):=(X', Y').
Formally, this mapping is not properly defined, since a nonzero
square y:=x^2 in GF(q) has two solutions, viz. x and x; it is
 properly defined, however, if one designates for each element in
+ properly defined, however, if one designates for each element of
GF(q) that is a square in GF(q) precisely one square root as "the"
square root of this element. Note that always picking the square
root with zero parity (see Appendix H) satisfies this condition
(henceforth called the default square root function).
If 1 is not a square in GF(q), this element is mapped to the point
at infinity O of W_{a,b}.
The set of points of W_{a,b} that arises this way has size roughly
3/8 of the order of the curve and each such point arises as image of
one or two t values. Further details are out of scope.
NOTE 1: If 1 is not a square in GF(q), the mapping above yields the
point at infinity for t=1. One can modify this mapping, by mapping
the element 1 to any suitable point P0 of W_{a,b} (e.g., its base
point G or any other affine point) and leaving the remainder of the
mapping the same. Suitability of such a modification is application
specific. Details are out of scope.
NOTE 2: The description above assumes that the domain parameters a
 and b of the Weierstrass curve are nonzero. If this is not the case,
 one can often find an isogenous curve W_{a',b'} for which the domain
 parameters a' and b' are nonzero. If so, one can map elements of
 GF(q) that are not a square in GF(q) to points of W_{a,b} via
 function composition, where one uses the mapping above to arrive at a
 point of W_{a',b'} and where one subsequently uses the dual isogeny
 from W_{a',b'} to W_{a,b} to arrive at a point of W_{a,b}. As an
 example, one can show that if a is zero and if 4*b is a cube in
+ and b of the Weierstrass curve W_{a,b} are nonzero. If this is not
+ the case, one can often find an isogenous curve W_{a',b'} for which
+ the domain parameters a' and b' are nonzero. If so, one can map
+ elements of GF(q) that are not a square in GF(q) to points of W_{a,b}
+ via function composition, where one uses the mapping above to arrive
+ at a point of W_{a',b'} and where one subsequently uses the dual
+ isogeny from W_{a',b'} to W_{a,b} to arrive at a point of W_{a,b}. As
+ an example, one can show that if a is zero and if 4*b is a cube in
GF(q) (such as is the case with, e.g., the "BitCoin" curve secp256k1
[SEC2]), this curve is 3isogenous to a curve with this property and
the strategy above applies (for an example with secp256k1, see
Appendix L). Further details are out of scope.
K.3.2. Mapping to Points of Montgomery Curve
The description below assumes that the domain parameter A of the
Montgomery curve M_{A,B} is nonzero. For ease of exposition, we
define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of
@@ 3948,49 +4166,49 @@
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
mapped to the point P(t):=(u, v);
b. If f(u)/B is a not a square in GF(q) and v':=sqrt(f(u')/B), then
t is mapped to the point P(t):=(u', v').
As before, formally, this mapping is not properly defined, since a
nonzero square y:=x^2 in GF(q) has two solutions, viz. x and x; it
 is properly defined, however, if one designates for each element in
+ is properly defined, however, if one designates for each element of
GF(q) that is a square in GF(q) precisely one square root as "the"
square root of this element. Note that always picking the square
root with zero parity (see Appendix H) satisfies this condition
(henceforth called the default square root function).
If 1 is not a square in GF(q), this element is mapped to the point
at infinity O of M_{A,B}.
The set of points of M_{A,B} that arises this way has size roughly
1/2 of the order of the curve and each such point arises as image of
precisely one t value. Further details are out of scope.
NOTE 1: If 1 is not a square in GF(q), the mapping above yields the
point at infinity for t=1. One can modify this mapping, by mapping
the element 1 to any suitable point P0 of M_{a,b} (e.g., its base
point G or any other affine point) and leaving the remainder of the
mapping the same. Suitability of such a modification is application
specific. Details are out of scope.
NOTE 2: The description above assumes that the domain parameter A of
 the Montgomery curve is nonzero. If this is not the case, the curve
 is a Weierstrass curve for which the domain parameter b is zero and
 Note 2 of Appendix K.3.1 applies. If q = 3 (mod 4), an even simpler
 approach is possible, where one modifies the construction above and
 simply takes u:=t and u':=t (which works, since 1 is not a square
 in GF(q) and f(t)=f(t)). In this case, this construction can be
 extended to all elements t of GF(q) and, if so, yields a 11 mapping
 between GF(q) and all affine curve points.
+ the Montgomery curve M_{A,B} is nonzero. If this is not the case,
+ the curve is a Weierstrass curve for which the domain parameter b is
+ zero and Note 2 of Appendix K.3.1 applies. If q = 3 (mod 4), an even
+ simpler approach is possible, where one modifies the construction
+ above and simply takes u:=t and u':=t (which works, since 1 is not
+ a square in GF(q) and f(t)=f(t)). In this case, this construction
+ can be extended to all elements t of GF(q) and, if so, yields a 11
+ mapping between GF(q) and all affine curve points.
K.3.3. Mapping to Points of Twisted Edwards Curve
One can map elements of GF(q) that are not a square in GF(q) to
points of the twisted Edwards curve E_{a,d} via function composition,
where one uses the mapping of Appendix K.3.1 to arrive at a point of
the Weierstrass curve W_{a,b} and where one subsequently uses the
isomorphic mapping between twisted Edwards curves and Weierstrass
curves of Appendix D.3 to arrive at a point of E_{a,d}. Another
mapping is obtained by function composition, where one instead uses
@@ 4094,58 +4312,64 @@
up to two values of the pair (t,s). Further details are out of
scope.
From the group law for Montgomery curves (see Appendix C.2) it
follows that one can express the coordinates of Q(t,s), with t<>1,
in terms of the ucoordinates of P0 and P(t) and the product of their
vcoordinates. (Here, observe that B*v0*v is a square root of
f(u0)*f(u).) Thus, Q(t,s) can be computed without the need to fully
compute P(t).
 +++
  Curve  Fixed curve offset P0 
 +++
  NIST P224 [FIPS1864]  Base point (Gx,Gy) 
  NIST P256 [FIPS1864]  P0:=(0,y) with y even 
  NIST P384 [FIPS1864]  P0:=(0,y) with y even 
  NIST P521 [FIPS1864]  P0:=(0,y) with y even 
  Brainpool224r1 [RFC5639]  Base point (Gx, Gy) 
  Brainpool256r1 [RFC5639]  Base point (Gx, Gy) 
  Brainpool320r1 [RFC5639]  Base point (Gx, Gy) 
  Brainpool384r1 [RFC5639]  Base point (Gx, Gy) 
  Brainpool512r1 [RFC5639]  P0:=(3,y), y even 
  Curve25519 [RFC7748]  P0:=(90,v), v even 
  Curve448 [RFC7748]  P0:=(50,v), v even 
  Wei25519 [Appendix E.3]  P0:=(3,y), y even 
  Wei25519.2 [Appendix G.3]  P0:=(244,y), y even 
  Wei25519.3 [Appendix G.3]  P0:=(41,y), y even 
  secp256k1.m [Appendix L.3]  P0:=(0,y), y even 
 +++
+ ++++
+  Curve  Fixed curve offset P0  NonSquare 
+ ++++
+  NIST P224 [FIPS1864]  Base point (Gx,Gy)  11 
+  NIST P256 [FIPS1864]  P0:=(0,y), y even  1 
+  NIST P384 [FIPS1864]  P0:=(0,y), y even  1 
+  NIST P521 [FIPS1864]  P0:=(0,y), y even  1 
+  Brainpool224r1 [RFC5639]  Base point (Gx, Gy)  1 
+  Brainpool256r1 [RFC5639]  Base point (Gx, Gy)  1 
+  Brainpool320r1 [RFC5639]  Base point (Gx, Gy)  1 
+  Brainpool384r1 [RFC5639]  Base point (Gx, Gy)  1 
+  Brainpool512r1 [RFC5639]  P0:=(3,y), y even  1 
+  Curve25519 [RFC7748]  P0:=(90,v), v even  2 
+  Wei25519 [Appendix E.3]  P0:=(3,y), y even  2 
+  Wei25519.2 [Appendix G.3]  P0:=(244,y), y even  2 
+  Wei25519.3 [Appendix G.3]  P0:=(41,y), y even  2 
+  Curve448 [RFC7748]  P0:=(50,v), v even  1 
+  Wei448 [Appendix M.3]  P0:=(18,y), y even  1 
+  Wei448.1 [Appendix N.3]  P0:=(10,y), y even  1 
+  Wei448.3 [Appendix N.3]  P0:=(8,y), y even  1 
+  secp256k1.m [Appendix L.3]  P0:=(0,y), y even  1 
+ ++++
 Table 1: Curve offsets P0 for mappings that avoid loworder points
+ Table 1: Fixed curve offsets for mappings that avoid loworder
+ points, for some curves of practical interest, including listing of
+ fixed nonsquare elements of their underlying finite fields.
K.4.3. Mapping to HighOrder Points of Twisted Edwards Curve
One can map elements of GF(q) that are not a square in GF(q) to
points of the twisted Edwards curve E_{a,d} via function composition,
where one uses the mapping of Appendix K.4.1 to arrive at a point of
 the Weierstrass curve W_{a,b} that does not have low order and where
 one subsequently uses the isomorphic mapping between twisted Edwards
 curves and Weierstrass curves of Appendix D.3 to arrive at a point of
 E_{a,d} with this property. Another mapping is obtained by function
 composition, where one instead uses the mapping of Appendix K.4.2 to
 arrive at a point of the Montgomery curve M_{A,B} that does not have
 low order and where one subsequently uses the isomorphic mapping
 between twisted Edwards curves and Montgomery curves of Appendix D.1
 to arrive at a point of E_{a,d} with this property. Obviously, one
 can use function composition (now using the respective preimages 
 if these exist) to realize the preimages of either mapping.
+ the Weierstrass curve W_{a,b} that is not in the small subgroup and
+ where one subsequently uses the isomorphic mapping between twisted
+ Edwards curves and Weierstrass curves of Appendix D.3 to arrive at a
+ point of E_{a,d} with this property. Another mapping is obtained by
+ function composition, where one instead uses the mapping of
+ Appendix K.4.2 to arrive at a point of the Montgomery curve M_{A,B}
+ that does not have low order and where one subsequently uses the
+ isomorphic mapping between twisted Edwards curves and Montgomery
+ curves of Appendix D.1 to arrive at a point of E_{a,d} with this
+ property. Obviously, one can use function composition (now using the
+ respective preimages  if these exist) to realize the preimages of
+ either mapping.
K.5. Randomized Representation of Curve Points
The mappings of Appendix K.3 allow one to represent a curve point Q
as a specific element t of GF(q), provided this point arises as a
point in the range of the mapping at hand. For Montgomery curves and
twisted Edwards curves, this covers roughly half of the curve points;
for Weierstrass curves, roughly 3/8 of the curve points. One can
extend the mappings above, by mapping a pair (t1, t2) of inputs to
the point Q:=P2(t1, t2):=P(t1) + P(t2). In this case, each curve
@@ 4184,68 +4408,93 @@
NOTE 1: The main difference between the two constructions above is
that that the first construction uses the mappings to curve points
described in Appendix K.3, while the second construction uses the
mappings to highorder curve points described in Appendix K.4. Note
that Q2((t1,s1), (t2,s2)) assumes all values (+/) P(t1) (+/) P(t2)
if one considers all possible values for the binary digits s1 and s2.
(This, thereby, includes the value P2(t1, t2).)
NOTE 2: The results on the statistical distributions mentioned above
 still hold if one makes a few localized changes to the constructions.
 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 redefines the mappings P2 or Q2 locally so as
 to avoid points in the small subgroup.
+ still hold in practice if one makes a few localized changes to the
+ constructions. 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 redefines 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
 particular curve via function composition, where one first maps any
 nonzero element u of GF(q) to the pair (t,s):=(delta*u^2, par(u)),
 where delta is a fixed element of GF(q) that is not a square in
 GF(q), and where one subsequently applies any of the mappings to
 yield a point of the curve in question. The resulting mapping from
 the nonzero elements of GF(q) to highorder curve points can be
 extended further to one that operates on all elements of GF(q) by
 mapping 0 to any fixed highorder point P1 of the curve in question.
 The resulting mapping is uniquely defined after fixing the curve
 offset P0 (used with the mappings of Appendix K.4), the highorder
 point P1 (used for input 0 above), and the nonsquare element delta
 of GF(q) (used for nonzero inputs above).
+ produce mappings that operate on input pairs (u, s), where u is any
+ nonzero element of GF(q), via function composition, where one first
+ maps the pair (u,s) to the pair (t,s):=(delta*u^2,s), where delta is
+ a fixed element of GF(q) that is not a square in GF(q), and where one
+ subsequently applies any of forementioned mappings to the resulting
+ pair to yield a point of the curve in question. The resulting
+ mapping to highorder curve points can be extended further to one
+ that operates on all elements of GF(q)x{0,1} by mapping each input
+ (u, s) with u=0 to any fixed highorder point P1 of the curve in
+ question. The resulting mapping is uniquely defined after fixing the
+ curve offset P0 (used with the mappings of Appendix K.4), the high
+ order point P1 (used for inputs with u=0 above), and the nonsquare
+ element delta of GF(q) (used for nonzero inputs u above).
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).
+ applicable), the point P1 (used for input u=0 above), and the non
+ square element delta of GF(q) (used for nonzero inputs u 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 nonsquare element delta of GF(q).
+ ((u1,s1), (u2,s2)) of elements of GF(q)x{0,1} to a point of a curve,
+ via function composition, where, in the first case, one first maps
+ the pair ((u1,s1),(u2,s2)) to the pair ((t1,s1),
+ (t2,s2)):=((delta*u1^2, s1), (delta*u2^2, s2)) 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
+ nonsquare element delta of GF(q).
+
+ NOTE 1: Each of the above mappings is fully and unambiguously defined
+ by the triple (P0,P1,delta). One can locally change this mapping so
+ as to avoid points in the small subgroup, should these otherwise
+ occur, e.g., by setting any such redefined image to any fixed high
+ order point P2 of the curve in question. In this case, the
+ corresponding mapping is uniquely defined by the quadruple
+ (P0,P1,P2,delta) and  in practice  has the same statistical
+ distribution properties as the original mapping (see NOTE 2 of
+ Appendix K.5). For each curve in Table 1, these completed mappings
+ are uniquely defined by the mentioned fixed curve offset P0 and non
+ square element delta of GF(q), if one defines P2:=P1:=P0 (henceforth
+ called the default completed mappings).
+
+ NOTE 2: For elliptic curves defined over prime fields (i.e., q:=p)
+ one can relax the completed mappings above and show that the
+ statistical properties for randomized representations still hold if
+ u1 is a random element of a sufficiently large interval in GF(p) and
+ if u2 is a random element of a sufficiently large subset of GF(p).
+ This allows generating u1 and u2, e.g., each as random bit strings of
+ length m1, where m is the bitsize of p, thereby allowing the pair
+ (u1, u2)  a random (2*m2)bit string  to be used unaltered in
+ this construction, without the need to carry out a reduction modulo p
+ first. Further details are out of scope of this document.
Appendix L. Curve secp256k1 and Friend
This section illustrates how isogenies can be used to yield curves
with specific properties (here, illustrated for the "BitCoin" curve
secp256k1).
L.1. Curve Definition and Alternative Representation
The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined
@@ 4680,52 +4929,63 @@
infinity of Wei448.1. (Here, we used the mapping of Appendix F.3.)
Under this mapping, the base point (GX, GY) of Wei448 corresponds to
the base point (G1X,G1Y) of Wei448.1. The inverse mapping maps the
affine point (X', Y') of Wei448.1 to (X,Y):=(X'/s^2,Y'/s^3) of
Wei448, while mapping the point at infinity O of Wei448.1 to the
point at infinity O of Wei448. Note that this mapping (and its
inverse) involves a modular multiplication of both coordinates with
fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which
can be precomputed.
 Each affine point (X,Y) of Wei448 for which the Ycoordinate is
 nonzero (i.e., each point with order larger than two) corresponds to
 the point (X',Y'):=(X1*t^2,Y1*t^3) of Wei448.3, where
+ The point at infinity and the point (A/3,0) of order two of Wei448
+ both correspond to the point at infinity of Wei448.3, while each
+ other point (X,Y) of Wei448 corresponds to the point
+ (X',Y'):=(X1*t^2,Y1*t^3) of Wei448.3, where
(X1,Y1)=(u(X)/w(X),Y*v(X)/w(X)^2), where u, v, and w are the
polynomials with coefficients in GF(p) as defined in Appendix N.4.1
and where t is the element of GF(p) defined by
t 23579450751475691430882365546539966269774125426758968522698856022
13378944265540874438945283200254318223329383397068961863760712339
07365
 (=0x530c9a1d7cf071d09646b83db246626b4e57ba5d6a791bef761972543209d
 c5c20d81498d5ab8d7a2fb22507ca68c040a6c82eb3b6c7aaa5),
+ (=0x530c9a1d 7cf071d0 9646b83d b246626b 4e57ba5d 6a791bef
+ 76197254 3209dc5c 20d81498 d5ab8d7a 2fb22507 ca68c040 a6c82eb3
+ b6c7aaa5).
 while the point at infinity and the point (A/3,0) of order two of
 Wei448 corresponds to the point at infinity of Wei448.3. (Here, we
 used the isogenous mapping of Appendix F.4.) Under this isogenous
 mapping, the base point (GX,GY) of Wei448 corresponds to the base
 point (G3X,G3Y) of Wei448.3. The dual isogeny maps the affine point
+ (Here, we used the isogenous mapping of Appendix F.4.) Under this
+ isogenous mapping, the base point (GX,GY) of Wei448 corresponds to
+ the base point (G3X,G3Y) of Wei448.3. The dual isogeny maps the
+ point at infinity O and the point (tau,0) of order two of Wei448.3,
+ where tau is the element of GF(p) defined by
+
+ tau 42178595713080601145580616893463205889346047807394283240821661315
+ 01870168726890624132409486822657385666418069563147259152341712826
+ 86207
+
+ (=0x948eabcf 057e0d55 9c372c98 075ddacf 6f3d19bc 514e5d23
+ 248d685b 75f97a10 36696aaf 61c02d8e 3da778c3 8d9fda05 54c9258b
+ 3c0e80ff),
+
+ to the point at infinity O of Wei448, while mapping each other point
(X',Y') of Wei448.3 to the affine point
(X,Y):=(u'(X1)/w'(X1),Y1*v'(X1)/w'(X1)^2) of Wei448, where
(X1,Y1)=(X'/t^2,Y'/t^3) and where u', v', and w' are the polynomials
 with coefficients in GF(p) as defined in Appendix N.4.2, while
 mapping the point at infinity O of Wei448.3 to the point at infinity
 O of Wei448. Under this dual isogenous mapping, the base point (G3X,
 G3Y) of Wei448.3 corresponds to a multiple of the base point (GX,
 GY) of Wei448, where this multiple is l=2 (the degree of the isogeny;
 see the description in Appendix F.4). Note that this isogenous map
 (and its dual) primarily involves the evaluation of three fixed
 polynomials involving the xcoordinate, which takes only a few
 modular multiplications (less than 0.5% relative incremental cost
 compared to the cost of an elliptic curve scalar multiplication).
+ with coefficients in GF(p) as defined in Appendix N.4.2. Under this
+ dual isogenous mapping, the base point (G3X, G3Y) of Wei448.3
+ corresponds to a multiple of the base point (GX, GY) of Wei448, where
+ this multiple is l=2 (the degree of the isogeny; see the description
+ in Appendix F.4). Note that this isogenous map (and its dual)
+ primarily involves the evaluation of three fixed polynomials
+ involving the xcoordinate, which takes only a few modular
+ multiplications (less than 0.5% relative incremental cost compared to
+ the cost of an elliptic curve scalar multiplication).
Each point (x1,y1) of Edwards448 with nonzero coordinates corresponds
to the point (x,y) of Ed448, where
x = c*x1*y1/(1d1*x1^2*y1^2) = c*x1*y1/(2x1^2y1^2) and
y =(1 + d1*x1^2*y1^2)/(y1^2x1^2) = (x1^2+y1^2)/(x1^2y1^2),
while each other point (i.e., a point of order 1, 2, or 4)
corresponds to the identity element (0,1) of Ed448. (Here, we used
@@ 5086,20 +5346,43 @@
460881642951497067363381071471046477130052706607411985560
522861593611384288817
(=0x3176361c 580a7bcd d7880d84 aba10bc6 57010328 afb728cc
2016461b 246bef46 0eb4bb04 8c1a3616 c3f74a56 3cc1790f
6472256b ca3481c8),
where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.2 with the default square root function.
+ This representation can also be expressed in tight LSB/msb order as
+ the pair ((u1,s1),(u2,s2)), where (s1,s2):=(0,1) and where
+
+ u1 136243399181827781288243566840664309780937553734476297986
+ 555794212826774821697384612603539068963961668560923975117
+ 429548012444908081181
+
+ (=0x1d50f12f 9d4a9f5b c49d8a59 0403a454 e9ab4208 ccde0595
+ 11d72af1 f44cefe4 0c743579 6502c443 730c55e9 2981fce1
+ f172d988 fa7efc2f)
+
+ u2 316511454563659405723248762668968632925539726790750815582
+ 281632434431599609191814743278306058750675581434472930261
+ 478756904493088717708
+
+ (=0x8c3b4bf7 5ff5eaf5 4df2119b a413785d 73059f0b aa677e16
+ e6eb7cf6 1e066961 e54e4b52 6ae528b1 d3c8cf8e aa3a7df0
+ 3b7a9a0d bb827a6f),
+
+ where this uses the default completed mapping defined in Appendix K.6
+ and the mapping of Appendix K.4.2 (with the default square root
+ function).
+
O.2. Example with Ed448
Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Ed448:
x 12711234107145442394649604543297947887906244696692372551963816418
93066253979844478364753304240794498368174540810674220788120782656
62747
(=0x2cc52fd1 6370554f 00c0f73f 64bda240 f5950177 d9033f6d
74acd12d 68c79a51 315f556f 240973f9 e5f71ed7 9314ee9d c87f0b1b
@@ 5186,20 +5469,43 @@
(=0x94ecb72a 069a5322 e62d9357 c49d5664 1c351611 d1f361a8
cbb8a12c f410e821 4fbe8e02 8d85d404 399b4c7c 5a6a72ce
deef7b08 96302d5f),
where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.3 with the default square root function and
underlying isomorphic mapping between Ed448 and Curve448 of
Appendix M.2.
+ This representation can also be expressed in tight LSB/lsb order as
+ the pair ((u1,s1),(u2,s2)), where (s1,s2):=(1,1) and where
+
+ u1 799430080555285542466583392114886786202374259081179178887
+ 990338902005327496428208435321295787094454554911799066625
+ 85567756287085693163
+
+ (=0xd713005d bece883b de9e7077 e0084c74 e3f8ccf3 dcdf9af2
+ 2db99b77 5a9c3de7 c8d14433 634cee63 531d3d85 0637c24d
+ a28691a3 ac041438)
+
+ u2 273728972604711260959662149917071768586371733548553856048
+ 628325847723030459670661529224890730701519431099205367639
+ 437006368499972842925
+
+ (=0xb5a46d1d be03f21b a4070e3c 51e42a50 1de9a4e6 3155b58c
+ 41dbdaed d5089539 cf69bbc8 78f3809d 5630ab65 c250e49b
+ 3a91a31d 067f1606),
+
+ where this uses the default completed mapping defined in Appendix K.6
+ and the mapping of Appendix K.4.3 (with the default square root
+ function).
+
O.3. Example with Wei448
Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei448:
X 29070637261778856087396075817199998758219070555984737667402173284
55389871077654193754799253725773241315783295429899652880118118204
91344
(=0x6663c64e 5b9a1f6d cbee3f5f 839b7dd8 6f53cc3e 0a01dab3
e4a8314e 8d54be2a 4d63380b 692381bb ed7339fd dca7b0cd a80166fe
@@ 5316,28 +5623,164 @@
507910466738735762660894972854331591097934354210992993787
402433561014235472657
(=0x7e0ffcaf 7add27bc bb723629 95fdedd0 8769f676 78d953bc
0d38f4f6 d63a59dc 00f2d55a a4db7dab 16364503 591edcb1
e095a577 43dea311),
where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.1 with the default square root function.
O.4. Example with Wei448.3
+ This representation can also be expressed in tight MSB/msb order as
+ the pair ((u1,s1),(u2,s2)), where (s1,s2):=(0,0) and where
+
+ u1 276116573473684049599673971142041943002546018725744504858
+ 999210132924481156665376801365226215725437541502686055399
+ 974543995300346621026
+ (=0x6140460c 1860a8cb 7c8ab942 b9509a84 95b4093c 95be5c8b
+ df46e24c 069fe28a a23e4bfc 5bc29543 ee9ff503 febb80c8
+ eb207253 8d7c6c62)
+
+ u2 128692595060487759871442054704123965938223087241863768179
+ 405512569340496286539849938457727539660932642464491037369
+ 291713756051590336193
+
+ (=0x2d53abf2 370638a2 c2d38efe 718d0189 18d15d15 f132741b
+ 34405174 97fc0884 0c6be3a5 d9c201b9 cb0c3637 2674078e
+ 59ac8cd7 4f9fcec1),
+
+ where this uses the default completed mapping defined in Appendix K.6
+ and the mapping of Appendix K.4.1 (with the default square root
+ function).
+
+O.4. Example with Wei448.1
+
+ Pw1=(X, Y), k*Pw1=(X1, Y1), and (k+1)*Pw1=(X2, Y2) with Wei448.1:
+
+ X 41414505267302962826496323862800346730148184600706317030200831678
+ 13123337737005257876668389910719145841028692415431602235556184165
+ 13314
+
+ (=0x91ddb90a 3c19f561 21de39ad a8c6bb00 579a6d2d 9ff6b810
+ b109bf41 6e4e6227 0fc34010 be9ec68e 5ca11111 bc99e998 cff0f6db
+ f4225122).
+
+ Y 21678703524693091005728527221124083240889481089231739678311939020
+ 43874709051080711177237887514058399787606848450432099149433728340
+ 08081
+
+ (=0x4c5ac727 121de1f1 be917280 829a6d4c 9f615e3a 879a7dfd
+ 50f8bdcc 75d5856b 1d01ffaa 44e5ba0a ed0e341d 9383e15a 6cd48db8
+ c1e26c11).
+
+ X1 21211734920525001827254082557112140340208109740004519264558098189
+ 40985376833176210029490012696175276046779431389727351279961384020
+ 21113
+
+ (=0x4ab5bb5f ca80119b 6280f5d1 aec51745 23ab57ab 4d617195
+ 38f453dd 2e8d9b66 a5417d1b ed0cee3d 4d6c84ca abda1d41 b7a805dc
+ cbaefef9).
+
+ Y1 14152482531219571027190110620355502977165146571026919001455348108
+ 06142769037926777863731011790633441497896003632149582109867558046
+ 16181
+ (=0x31d8b337 09272016_25d2f9d6 cb0e2396 b7088c79 ffc8571f
+ 6dc9bfe9 9e0783d4 1f684439 c02981f1 83f6696d 9c0377c9 431b8186
+ f503d5f5).
+
+ X2 30394319241133688143587947164786865078477223372122681434460686381
+ 23744153597949961703624604448300529949032402198106459850911229168
+ 46262
+
+ (=0x6b0d487d cba3633b_034f65a5 bbd1c8eb 1b6dcb1f 8d787db1
+ a581c08d ad23cbcd 6faa39d5 36731645 fd2fd6c0 03367bff 9093d29d
+ 550d6ab6).
+
+ Y2 18866191129065867707969757296934620738822864945913956797432892866
+ 18725386530370846638505587040510045280940919798896557156654042590
+ 85719
+
+ (=0x4272da7b 7ad66918 144ae679 3811eb6b 2124b02f 42fd51f2
+ 34e6f3ea 6285d40e 43cf726f 585b7e74 c4448acb b0c3ab89 d5a55678
+ c4622d97).
+
+ The representation of k and the compressed representations of Pw1 and
+ k*Pw1 in tight MSB/msborder are given by
+
+ repr(k) =0xdcb3bbb9 e42d7aca fe62052d 902123c7 0872b984 4c1e199f
+ 7c5d37bd 1171102b c20a6352 d9c91886 29b685de 51441e84
+ 3afe2665 5251aa80;
+
+ repr(Pw1) =0x80 0x91ddb90a 3c19f561 21de39ad a8c6bb00 579a6d2d
+ 9ff6b810 b109bf41 6e4e6227 0fc34010 be9ec68e 5ca11111
+ bc99e998 cff0f6db f4225122;
+
+ repr(k*Pw1) =0x80 0x4ab5bb5f ca80119b 6280f5d1 aec51745 23ab57ab
+ 4d617195 38f453dd 2e8d9b66 a5417d1b ed0cee3d 4d6c84ca
+ abda1d41 b7a805dc cbaefef9,
+
+ where the leftmost bit of the leftmost octet indicates the parity of
+ the Ycoordinate of the point of Wei448.1 in question (which, in this
+ case, are both one, since Y and Y1 are odd). See Appendix H.1 and
+ Appendix I for further detail on (squeezed) point compression.
+
+ A randomized representation (t1, t2) of the point k*Pw1 in tight MSB/
+ msb order is given by
+
+ t1 303494474566270819668963081208440311422386279248346372989
+ 800906749888679443057479207554461646083343330145746687567
+ 323228377891922156528
+ (=0x6ae4d2fc 57e63e5e bfdc44e6 5148d1bd b30b7c7b 2ca2a66a
+ 8a2bea6c 69113c79 7a4d6d0f 3c89b06a 3883ab2c e7d73f42
+ 24c82419 391e9bf0)
+
+ t2 637873534161581517938168102871523640780662020357386089328
+ 144426836947858617075256828298188817117945599296940030103
+ 858866119361786506090
+
+ (=0xe0aa61c1 213a19b4 a9fddbb3 4c1377d0 4cd1fb84 017a1719
+ e57b243b 31b13406 d5d77138 23c5a1b8 4fe271a5 2e53c98f
+ 900f2900 d1e76b6a),
+
+ where this representation is defined in Appendix K.5 and uses the
+ mapping of Appendix K.3.1 with the default square root function.
+
+ This representation can also be expressed in tight MSB/msb order as
+ the pair ((u1,s1),(u2,s2)), where (s1,s2):=(1,0) and where
+
+ u1 258036413119309433113527846878476684681744445436114935036
+ 372455666259396397921645423893888406553811930237985641251
+ 551672383206550397837
+
+ (=0x5ae20fb6 5cafa07a 40421568 72419f49 dc31cbe9 766806f6
+ 8b1dbd7f 628c8ecf 10577848 e2e87ac2 fead0f09 6726ee34
+ c2ed465f 5b7be38d)
+
+ u2 193962140052429320576140519455776109491178991023347646634
+ 723564200925012444187815484406230413980100291233975929881
+ 580671116555136082409
+
+ (=0x4450c0ba ba9ee42a 4723b3b4 dbe7613f a78a2feb ee01752f
+ 9f8f51d6 41476eb8 041c9d87 d1b6df7b 9c6b48ad 2cdf4c20
+ 02d22f0c fbf521e9),
+
+ where this uses the default completed mapping defined in Appendix K.6
+ and the mapping of Appendix K.4.1 (with the default square root
+ function).
+
+O.5. Example with Wei448.3
Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei448.3:
X 54121793865726175505902038600562190720650456678500106168173285986
99999531708218763586616425010404811083912084906688745035466757984
48968

(=0xbe9f5a23 51709e13 d5ad50c2 a27be8ee 1b051970 2580d5c3
c2de7f75 3010635e d89ef547 8b67dc54 16d63c5b 1cc1116f dd453515
71b39b48).
Y 14962282101304548030627835311887275833718070818965306362006934455
59168773381983445709256615887526455657034051121085622763637035580
12661
(=0x34b2dcc4 92d6a940 e6249c14 122d0ba4 5dc040e9 3f060d8f
a65fa300 eb3cc969 25188b59 2d31039c f7a8e14a 48320a32 efe9b42b
@@ 5411,21 +5853,43 @@
363622725164496136165251928391223173879522521195772276587
373445978123589677750
(=0x7778c1f9 9d900633 d161d7ea a963ddad e9101d3f f4f04710
623d2a51 6ca10133 3db9ccc3 86df9271 fbb72740 77f79dd1
9aed0bfb e3bc72b6),
where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.1 with the default square root function.
O.5. Example with Edwards448
+ This representation can also be expressed in tight MSB/msb order as
+ the pair ((u1,s1),(u2,s2)), where (s1,s2):=(0,1) and where
+
+ u1 589255274721777493669102139212346422449226408440608788354
+ 266603544786997157375671957901717836941301424106139118763
+ 92799989153446639329
+ (=0x14c11156 85eab1a5 f6c00d37 a3f6bd73 fe403dd1 31e337e7
+ 15927c25 0264a8f8 d2cd661e b5138468 92a3b91d 09284398
+ 17c2e361 96fa36e1)
+
+ u2 213991023129828413030692573508989139610229330687681826719
+ 574082317313789459478773972345123463766002343322541837566
+ 496527438452046182709
+
+ (=0x4b5eac5a 3632b273 012a1050 7762eba4 8df1ccad 16dd9e6f
+ d68e57a9 89de5a0c 1eda0951 e4f3de0e 39f5c37b 2f8f04d5
+ 52c093d8 fb983935),
+
+ where this uses the default completed mapping defined in Appendix K.6
+ and the mapping of Appendix K.4.1 (with the default square root
+ function).
+
+O.6. Example with Edwards448
Pe1=(x, y), k*Pe1=(x1, y1), and (k+1)*Pe1=(x2, y2) with Edwards448:
x 70320395893028961673046639985409870226249442701760956079298956688
26896600999421897751877804946848997852325361659665744287620719558
67733
(=0xf7acf3ca b79b29c2 aa44863d 9edaeca4 8c90ad84 e460df42
7dd9ab59 1bd8a844 07cb3419 59309b33 1e22bfa1 a2d37e10 e2e42a1f
170f0855).
@@ 5490,41 +5953,65 @@
this case, are both one, since x and x1 are odd). See Appendix H.3
and Appendix I for further detail on (squeezed) point compression.
The scalar representation and (squeezed) point representation
illustrated above are fully consistent with the representations
specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032]
requires unique representations of all elements of GF(p).
A randomized representation (t1, t2) of the point k*Pe1 in tight LSB/
lsb order is given by

t1 125390048858887400104074787879402833851854739339836093733
734638776755983021034212058415891288350265701101219981698
849086128138510420407
(=0xed921f3d 6ea4e452 dd06e783 782cbeb3 c5847a79 d9e6b993
bd387cf5 feeddafe af8c038d f2732362 92724d37 273eedfc
f2ab2499 98a79434)
 t2 365268494484253132875102676783560666625109899133767696106
 602723958322248430160651314075127005631031993354968950936
 71875730862008188281
 (=0x9ebc28c0 86176a1a c7f0cf71 ca5f2a8f 908bb27b e85c0bbd
 1641c052 e542f7d3 88e18886 5afdca32 8df45408 8b6da28c
 0bc09d83 309ebb30),
+ t2 493324858478481242405018423865550638507715454654135514168
+ 842560149827360763382889199963980056979895918545280883247
+ 787003997982869314731
+
+ (=0xd53a5125 193b6ab9 8db48161 20fb4865 02cf0546 3b48d8a6
+ 514af28f 43c026cb 0f2ff3d5 e558bb03 4b833cd1 1ca710cc
+ 9bf0c2a3 351083b5),
where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.3 with the default square root function and
underlying 4isogenous mapping between Edwards448 and Curve448 of
Appendix N.2.
+ This representation can also be expressed in tight LSB/lsb order as
+ the pair ((u1,s1),(u2,s2)), where (s1,s2):=(0,0) and where
+
+ u1 135993582308059710871118067705651831584215992415511174727
+ 255533641033816319052989477276487981998957706382391254504
+ 484510842833065141388
+
+ (=0x31276f5f d399d1cd 5d18c46a eba5388f 93effaf7 9574b23b
+ ce34ba45 5050c160 477ae803 9c3112be 596281a7 b7ae4da6
+ e9dd7688 191fa7f4)
+
+ u2 300725936379847215929002275525633229576034707671620463143
+ 626393832660436027759737097637786753095880885199368686863
+ 187789449179730426477
+
+ (=0xb65c5ee8 597b5b55 a87e266f b9c1f5cb 5d224ec3 8fb22f32
+ b0378e70 47ecc389 9585b06e 7fb4f70b 38a3b453 ab5c03d8
+ 37b5093b 9a4cd796),
+
+ where this uses the default completed mapping defined in Appendix K.6
+ and the mapping of Appendix K.4.3 (with the default square root
+ function) and underlying 4isogenous mapping between Edwards448 and
+ Curve448 of Appendix N.2.
+
Appendix P. Random Integers in Z_n
Any probability distribution on the interval [0,N1] can be converted
to a probability distribution on [0,n1], via a suitable function
that maps inputs from the source distribution [0,N1] to values in
the interval [0,n1]. We consider three such functions, each with
the property that if the source distribution on [0,N1] is
statistically close to the uniform distribution, then so is the
output distribution on [0,n1]. In practical applications, one can
use these functions to convert the output of a cryptographically
@@ 5605,20 +6092,20 @@
This function (defined for N at least n) is the identity map on the
interval [0,n1] 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.
+ length m, this conversion function fails with probability 1 n/N
+ (which is at most 1/2) and, if it succeeds, does not inflate the
+ statistical distance by more than (roughly) a factor two.
Author's Address
Rene Struik
Struik Security Consultancy
Email: rstruik.ext@gmail.com