draft-ietf-lwig-curve-representations-12.txt   draft-ietf-lwig-curve-representations-13.txt 
lwig R. Struik lwig R. Struik
Internet-Draft Struik Security Consultancy Internet-Draft Struik Security Consultancy
Intended status: Informational August 24, 2020 Intended status: Informational November 2, 2020
Expires: February 25, 2021 Expires: May 6, 2021
Alternative Elliptic Curve Representations Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-12 draft-ietf-lwig-curve-representations-13
Abstract Abstract
This document specifies how to represent Montgomery curves and This document specifies how to represent Montgomery curves and
(twisted) Edwards curves as curves in short-Weierstrass form and (twisted) Edwards curves as curves in short-Weierstrass form and
illustrates how this can be used to carry out elliptic curve illustrates how this can be used to carry out elliptic curve
computations using existing implementations of, e.g., ECDSA and ECDH computations using existing implementations of, e.g., ECDSA and ECDH
using NIST prime curves. We also provide extensive background using NIST prime curves. We also provide extensive background
material that may be useful for implementers of elliptic curve material that may be useful for implementers of elliptic curve
cryptography. cryptography.
skipping to change at page 1, line 44 skipping to change at page 1, line 44
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on February 25, 2021. This Internet-Draft will expire on May 6, 2021.
Copyright Notice Copyright Notice
Copyright (c) 2020 IETF Trust and the persons identified as the Copyright (c) 2020 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 30 skipping to change at page 2, line 30
Table of Contents Table of Contents
1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 5 1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 5
2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 6 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 6
3. Use of Representation Switches . . . . . . . . . . . . . . . 6 3. Use of Representation Switches . . . . . . . . . . . . . . . 6
4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 7 4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 7
4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 8 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 8
4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 8 4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 8
4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 9 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 9
5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 10 5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 10
5.2. Representation Conventions . . . . . . . . . . . . . . . 10 5.2. Representation Conventions . . . . . . . . . . . . . . . 10
5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 10 5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 10
6. Implementation Considerations . . . . . . . . . . . . . . . . 11 6. Implementation Considerations . . . . . . . . . . . . . . . . 11
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 12 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 12
8. Security Considerations . . . . . . . . . . . . . . . . . . . 13 8. Security Considerations . . . . . . . . . . . . . . . . . . . 13
9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 14 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 14
10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 14 10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 14
10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 14 10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 15
10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 15 10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 15
10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 16 10.1.2. Encoding of Short-Weierstrass 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.1. Encoding of ECDSA Instantiations with COSE . . . . . 17
10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 18 10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 18
10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 19 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 19
10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 20 10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 20
10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 20 10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 20
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 11. Using Wei25519 and Wei448 with PKIX and CMS . . . . . . . . . 21
11.1. IANA Considerations for Wei25519 . . . . . . . . . . . . 21 11.1. Encoding of Short-Weierstrass Curves with PKIX . . . . . 21
11.1.1. COSE Elliptic Curves Registration . . . . . . . . . 21 11.2. Encoding of ECDSA Instantiations with PKIX . . . . . . . 21
11.1.2. COSE Algorithms Registration (1/2) . . . . . . . . . 21 11.3. Encoding of co-factor ECDH and Other Algorithms with
11.1.3. COSE Algorithms Registration (2/2) . . . . . . . . . 21 PKIX . . . . . . . . . . . . . . . . . . . . . . . . . . 21
11.1.4. JOSE Elliptic Curves Registration . . . . . . . . . 22
11.1.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 22 11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS . . 22
11.1.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 23 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22
11.2. IANA Considerations for Wei448 . . . . . . . . . . . . . 23 12.1. OIDs for Use with PKIX and CMS . . . . . . . . . . . . . 22
11.2.1. COSE Elliptic Curves Registration . . . . . . . . . 23 12.2. COSE/JOSE IANA Considerations for Wei25519 . . . . . . . 23
11.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 24 12.2.1. COSE Elliptic Curves Registration . . . . . . . . . 23
11.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 24 12.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 23
11.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 24 12.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 23
11.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 25 12.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 24
11.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 25 12.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 24
12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 26 12.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 25
13. References . . . . . . . . . . . . . . . . . . . . . . . . . 26 12.3. COSE/JOSE IANA Considerations for Wei448 . . . . . . . . 25
13.1. Normative References . . . . . . . . . . . . . . . . . . 26 12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 25
13.2. Informative References . . . . . . . . . . . . . . . . . 28 12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 26
Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 30 12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 26
A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 30 12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 26
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 30 12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 27
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 30 12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 27
Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 31 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 28
B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 31 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 28
B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 33 14.1. Normative References . . . . . . . . . . . . . . . . . . 28
Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 34 14.2. Informative References . . . . . . . . . . . . . . . . . 31
C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 34 Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 32
C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 35 A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 33
C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 36 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 33
Appendix D. Relationships Between Curve Models . . . . . . . . . 37 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 D.1. Mapping between Twisted Edwards Curves and Montgomery
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 37 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 40
D.2. Mapping between Montgomery Curves and Weierstrass Curves 37 D.2. Mapping between Montgomery Curves and Weierstrass Curves 40
D.3. Mapping between Twisted Edwards Curves and Weierstrass D.3. Mapping between Twisted Edwards Curves and Weierstrass
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 38 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 41
Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 39 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 41
E.1. Curve Definition and Alternative Representations . . . . 39 E.1. Curve Definition and Alternative Representations . . . . 42
E.2. Switching between Alternative Representations . . . . . . 39 E.2. Switching between Alternative Representations . . . . . . 42
E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 41 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 44
Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 43 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 46
F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 43 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 46
F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 43 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 46
F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 44 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 47
F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 45 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 48
Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 47 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 50
G.1. Further Alternative Representations . . . . . . . . . . . 47 G.1. Further Alternative Representations . . . . . . . . . . . 50
G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 47 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 50
G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 48 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 51
G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 49 G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 52
G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 49 G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 52
G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 56 G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 59
Appendix H. Point Compression . . . . . . . . . . . . . . . . . 62 Appendix H. Point Compression . . . . . . . . . . . . . . . . . 65
H.1. Point Compression for Weierstrass Curves . . . . . . . . 62 H.1. Point Compression for Weierstrass Curves . . . . . . . . 65
H.2. Point Compression for Montgomery Curves . . . . . . . . . 63 H.2. Point Compression for Montgomery Curves . . . . . . . . . 66
H.3. Point Compression for Twisted Edwards Curves . . . . . . 64 H.3. Point Compression for Twisted Edwards Curves . . . . . . 67
Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 65 Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 68
I.1. Strings and String Operations . . . . . . . . . . . . . . 65 I.1. Strings and String Operations . . . . . . . . . . . . . . 68
I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 65 I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 69
I.3. Conversion between Octet Strings and Integers (OS2I, I.3. Conversion between Octet Strings and Integers (OS2I,
I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 66 I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 69
I.4. Conversion between Octet Strings and Bit Strings (OS2BS, I.4. Conversion between Octet Strings and Bit Strings (OS2BS,
BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 66 BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 69
I.5. Conversion between Field Elements and Octet Strings 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 I.6. Conversion between Elements of Z mod n and Octet Strings
(ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 67 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 70
I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 68 I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 71
I.8. Conversion Between Curve Points and Octet Strings . . . . 69 I.8. Conversion Between Curve Points and Octet Strings . . . . 72
Appendix J. Representation Examples Curve25519 Family Members . 71 Appendix J. Representation Examples Curve25519 Family Members . 74
J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 72 J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 75
J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 74 J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 77
J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 75 J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 79
J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 78 J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 82
J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 79 J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 84
Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 81 Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 86
K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 81 K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 86
K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 81 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) . . . . . 81 K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 86
K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 82 K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 87
K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 82 K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 87
K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 82 K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 87
K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 83 K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 89
K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 84 K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 90
K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 85 K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 90
K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 85 K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 90
K.4.2. Mapping to High-Order Points of Montgomery Curve . . 86 K.4.2. Mapping to High-Order Points of Montgomery Curve . . 91
K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 87 K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 93
K.5. Randomized Representation of Curve Points . . . . . . . . 88 K.5. Randomized Representation of Curve Points . . . . . . . . 94
K.6. Completing the Mappings to Curve Points . . . . . . . . . 89 K.6. Completing the Mappings to Curve Points . . . . . . . . . 95
Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 90 Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 96
L.1. Curve Definition and Alternative Representation . . . . . 90 L.1. Curve Definition and Alternative Representation . . . . . 96
L.2. Switching Between Representations . . . . . . . . . . . . 90 L.2. Switching Between Representations . . . . . . . . . . . . 97
L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 91 L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 97
L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 92 L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 99
L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 92 L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 99
L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 93 L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 99
Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 94 Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 100
M.1. Curve Definition and Alternative Representations . . . . 94 M.1. Curve Definition and Alternative Representations . . . . 100
M.2. Switching between Alternative Representations . . . . . . 94 M.2. Switching between Alternative Representations . . . . . . 101
M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 96 M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 102
Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 105
Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 98 N.1. Further Alternative Representations . . . . . . . . . . . 105
N.1. Further Alternative Representations . . . . . . . . . . . 98 N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 105
N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 99 N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 108
N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 101 N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 110
N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 103 N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 110
N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 103 N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 111
N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 104 Appendix O. Representation Examples Curve448 Family Members . . 111
Appendix O. Representation Examples Curve448 Family Members . . 105 O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 112
O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 105 O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 115
O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 108 O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 118
O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 110 O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 121
O.4. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 113 O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 123
O.5. Example with Edwards448 . . . . . . . . . . . . . . . . . 115 O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 126
Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 117 Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 129
P.1. Conversion to Integers in Z_n via Modular Reduction . . . 117 P.1. Conversion to Integers in Z_n via Modular Reduction . . . 129
P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 118 P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 130
P.3. Conversion to Integers in Z_n via the Discard Method . . 119 P.3. Conversion to Integers in Z_n via the Discard Method . . 130
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 119 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 131
1. Fostering Code Reuse with New Elliptic Curves 1. Fostering Code Reuse with New Elliptic Curves
Elliptic curves can be represented using different curve models. Elliptic curves can be represented using different curve models.
Recently, IETF standardized elliptic curves that are claimed to have Recently, IETF standardized elliptic curves that are claimed to have
better performance and improved robustness against "real world" better performance and improved robustness against "real world"
attacks than curves represented in the traditional "short" attacks than curves represented in the traditional short-Weierstrass
Weierstrass curve model. These so-called CFRG curves [RFC7748] use curve model. These so-called CFRG curves [RFC7748] use the
the Montgomery curve model and the model of twisted Edwards curves. Montgomery curve model and the model of twisted Edwards curves.
In this document, we specify these curves using the traditional In this document, we specify these curves using the traditional
"short" Weierstrass model and also define how to efficiently switch short-Weierstrass model and also define how to efficiently switch
between representations in these different curve models. In between representations in these different curve models. In
particular, we specify Wei25519, which allows an alternative particular, we specify Wei25519, which allows an alternative
representation of points of Curve25519 (a Montgomery curve) and of representation of points of Curve25519 (a Montgomery curve) and of
points of Edwards25519 (a twisted Edwards curve), as points of a points of Edwards25519 (a twisted Edwards curve), as points of a
corresponding "short" Weierstrass curve. Similarly, we specify corresponding short-Weierstrass curve. Similarly, we specify Wei448,
Wei448, which allows an alternative representation of points of which allows an alternative representation of points of Curve448 (a
Curve448 (a Montgomery curve) and of points of Ed448 (an Edwards Montgomery curve) and of points of Ed448 (an Edwards curve), as
curve), as points of a corresponding "short" Weierstrass curve. points of a corresponding short-Weierstrass curve.
Use of Wei25519 and Wei448 allows easy definition of new Use of Wei25519 and Wei448 allows easy definition of new
instantiations of signature schemes and key agreement schemes already instantiations of signature schemes and key agreement schemes already
specified for traditional NIST prime curves, thereby allowing easy specified for traditional NIST prime curves, thereby allowing easy
integration with existing specifications, such as NIST SP 800-56a integration with existing specifications, such as NIST SP 800-56a
[SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005 [SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005
[ANSI-X9.62], and fostering code reuse on platforms that already [ANSI-X9.62], and fostering code reuse on platforms that already
implement some of these schemes using elliptic curve arithmetic for implement some of these schemes using elliptic curve arithmetic for
curves in "short" Weierstrass form (see Appendix C.1). To illustrate curves in short-Weierstrass form (see Appendix C.1). To illustrate
this, we specify how to use Wei25519 and Wei448 with co-factor ECDH this, we specify how to use Wei25519 and Wei448 with co-factor ECDH
and with ECDSA, thereby giving rise to the key agreement schemes and with ECDSA, thereby giving rise to the key agreement schemes
ECDH25519 and ECDH448 and the signature schemes ECDSA25519 and ECDH25519 and ECDH448 and the signature schemes ECDSA25519 and
ECDSA448. In all these cases, implementors may use the curve ECDSA448. In all these cases, implementors may use the curve
arithmetic for the curve model of their choosing (where they can arithmetic for the curve model of their choosing (where they can
efficiently switch between representations in different curve models, efficiently switch between representations in different curve models,
if required). if required).
For ease of exposition, we consider Wei25519 first and introduce For ease of exposition, we consider Wei25519 first and introduce
Wei448 simply as an illustration of how to create other "offspring" Wei448 simply as an illustration of how to create other "offspring"
skipping to change at page 9, line 15 skipping to change at page 9, line 24
curve Wei25519, where the signature (r,s) is represented as the curve Wei25519, where the signature (r,s) is represented as the
right-concatenation of the integers r and s, each represented as right-concatenation of the integers r and s, each represented as
fixed-size strings with tight MSB/msb ordering (see Appendix I). fixed-size strings with tight MSB/msb ordering (see Appendix I).
4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others)
Any existing specification of cryptographic schemes using elliptic Any existing specification of cryptographic schemes using elliptic
curves in Weierstrass form and that allows introduction of a new curves in Weierstrass form and that allows introduction of a new
elliptic curve (here: Wei25519) is amenable to similar constructs, elliptic curve (here: Wei25519) is amenable to similar constructs,
thus spawning "offspring" protocols, simply by instantiating these thus spawning "offspring" protocols, simply by instantiating these
using the new curve in "short" Weierstrass form, thereby allowing using the new curve in short-Weierstrass form, thereby allowing code
code and/or specifications reuse and, for implementations that so and/or specifications reuse and, for implementations that so desire,
desire, carrying out curve computations "under the hood" on carrying out curve computations "under the hood" on Montgomery curve
Montgomery curve and twisted Edwards curve cousins hereof (where and twisted Edwards curve cousins hereof (where these exist). This
these exist). This would simply require definition of a new object would simply require definition of a new object identifier for any
identifier for any such envisioned "offspring" protocol. This could such envisioned "offspring" protocol. This could significantly
significantly simplify standardization of schemes and help keeping at simplify standardization of schemes and help keeping at bay the
bay the resource and maintenance cost of implementations supporting resource and maintenance cost of implementations supporting algorithm
algorithm agility [RFC7696]. agility [RFC7696].
We illustrate the construction of such offspring protocols for We illustrate the construction of such offspring protocols for
Curve448, another Montgomery curve recently standardized by IETF (see Curve448, another Montgomery curve recently standardized by IETF (see
[RFC7748]). Similar to the case with Curve25519, one can represent [RFC7748]). Similar to the case with Curve25519, one can represent
points of this curve via different curve models, viz. as points of an points of this curve via different curve models, viz. as points of an
Edwards curve (Ed448) or as points of a short-Weierstrass curve Edwards curve (Ed448) or as points of a short-Weierstrass curve
(Wei448). For the specification of Wei448 and its relationship to (Wei448). For the specification of Wei448 and its relationship to
Curve448 and Ed448, see Appendix M. As with ECDH25519, one can now Curve448 and Ed448, see Appendix M. As with ECDH25519, one can now
easily define a NIST-compliant version of co-factor Diffie-Hellman easily define a NIST-compliant version of co-factor Diffie-Hellman
key agreement (denoted by ECDH448), by simply reusing the example of key agreement (denoted by ECDH448), by simply reusing the example of
skipping to change at page 14, line 8 skipping to change at page 14, line 10
cryptographic scheme that may include processing steps that depend on cryptographic scheme that may include processing steps that depend on
the representation conventions used (such as with, e.g., key the representation conventions used (such as with, e.g., key
derivation following key establishment). These schemes should derivation following key establishment). These schemes should
(obviously) unambiguously specify fixed representations of each input (obviously) unambiguously specify fixed representations of each input
and output (e.g., representing each elliptic curve point always in and output (e.g., representing each elliptic curve point always in
short-Weierstrass form and in uncompressed tight MSB/msb format). short-Weierstrass form and in uncompressed tight MSB/msb format).
To prevent cross-protocol attacks, private keys SHOULD only be used To prevent cross-protocol attacks, private keys SHOULD only be used
with one cryptographic scheme. Private keys MUST NOT be reused with one cryptographic scheme. Private keys MUST NOT be reused
between Ed25519 (as specified in [RFC8032]) and ECDSA25519 (as 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 intra-protocol cross-instantiation attacks, ephemeral To prevent intra-protocol cross-instantiation attacks, ephemeral
private keys MUST NOT be reused between instantiations of ECDSA25519 private keys MUST NOT be reused between instantiations of ECDSA25519
or ECDSA448. or ECDSA448.
9. Privacy Considerations 9. Privacy Considerations
The transformations between different curve models described in this The transformations between different curve models described in this
document are publicly known and, therefore, do not affect privacy document are publicly known and, therefore, do not affect privacy
provisions. provisions.
skipping to change at page 20, line 39 skipping to change at page 21, line 5
name of the curve used with this particular instantiation of name of the curve used with this particular instantiation of
ECDH. ECDH.
When using a JOSE key for this algorithm, if the "alg" field is When using a JOSE key for this algorithm, if the "alg" field is
present, it MUST be set to the (unique) name of this particular present, it MUST be set to the (unique) name of this particular
instantiation of co-factor ECDH and the "crv" parameter MUST be set instantiation of co-factor ECDH and the "crv" parameter MUST be set
to the (unique) name of the corresponding curve; if the "key_ops" to the (unique) name of the corresponding curve; if the "key_ops"
field is present, it MUST include "derive shared secret" for the field is present, it MUST include "derive shared secret" for the
private key. 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 Short-Weierstrass 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 id-Wei448 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 SHA-256 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 id-wei25519 (see Section 11.1),
where ECDSA with SHA256 is identified by the object identifier id-
ecdsa-with-SHA256 (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 id-wei448 (see Section 11.1),
where ECDSA with SHAKE256 with output size of d=512 bits is
identified by the object identifier id-ecdsa-with-shake256 (see
[RFC8692]), and where all other aspects are specified in [RFC5480].
11.3. Encoding of co-factor 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. id-ecPublicKey, id-ecdh, 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 id-wei25519 and id-wei448,
respectively, and where all other aspects are specified in [RFC5480].
11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS
With [RFC5753], elliptic-curve 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 id-wei448, respectively, and where all other aspects are
specified in [RFC5753].
12. IANA Considerations
Code points are requested for curves Wei25519 and Wei448 and their Code points are requested for curves Wei25519 and Wei448 and their
use with ECDSA and co-factor ECDH, using the representation use with ECDSA and co-factor ECDH, using the representation
conventions of this document. conventions of this document.
New code points would be required in case one wishes to specify one New code points would be required in case one wishes to specify one
or more other "offspring" protocols beyond those exemplified in or more other "offspring" protocols beyond those exemplified in
Section 4.4. Specification hereof is, however, outside the scope of Section 4.4. Specification hereof is, however, outside the scope of
the current document. 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. id-Wei25519 OBJECT IDENTIFIER ::= TBD (Requested value: {iso(1)
identified-organization(3) thawte (101) 108 });
b. id-Wei448 OBJECT IDENTIFIER ::= TBD (Requested value: {iso(1)
identified-organization(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 This section registers the following value in the IANA "COSE Elliptic
Curves" registry [IANA.COSE.Curves]. Curves" registry [IANA.COSE.Curves].
Name: Wei25519; Name: Wei25519;
Value: TBD (Requested value: -1); Value: TBD (Requested value: -1);
Key Type: EC2 or OKP; Key Type: EC2 or OKP;
skipping to change at page 21, line 29 skipping to change at page 23, line 29
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Appendix E.3 of this specification; for Reference: specified in Appendix E.3 of this specification; for
encodings, see Section 10.1; encodings, see Section 10.1;
Recommended: Yes. Recommended: Yes.
(Note that The "kty" value for Wei25519 may be "EC2" or "OKP".) (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 This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms]. Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDSA25519; Name: ECDSA25519;
Value: TBD (Requested value: -1); Value: TBD (Requested value: -9);
Description: ECDSA with SHA-256 and curve Wei25519; Description: ECDSA with SHA-256 and curve Wei25519;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Section 4.3 of this specification; for Reference: specified in Section 4.3 of this specification; for
encodings, see Section 10.2; encodings, see Section 10.2;
Recommended: Yes. 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 This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms]. Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDH25519; Name: ECDH25519;
Value: TBD (Requested value: -2); Value: TBD (Requested value: -24);
Description: NIST-compliant co-factor Diffie-Hellman w/ curve Description: NIST-compliant co-factor Diffie-Hellman w/ curve
Wei25519 and key derivation function HKDF SHA256; Wei25519 and key derivation function HKDF SHA256;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Section 4.1 of this specification; for Reference: specified in Section 4.1 of this specification; for
encodings, see Section 10.3; encodings, see Section 10.3;
Recommended: Yes. Recommended: Yes.
11.1.4. JOSE Elliptic Curves Registration 12.2.4. JOSE Elliptic Curves Registration
This section registers the following value in the IANA "JSON Web Key This section registers the following value in the IANA "JSON Web Key
Elliptic Curve" registry [IANA.JOSE.Curves]. Elliptic Curve" registry [IANA.JOSE.Curves].
Curve Name: Wei25519; Curve Name: Wei25519;
Curve Description: short-Weierstrass curve Wei25519; Curve Description: short-Weierstrass curve Wei25519;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Appendix E.3 of this specification; for Reference: specified in Appendix E.3 of this specification; for
encodings, see Section 10.1. encodings, see Section 10.1.
(Note that The "kty" value for Wei25519 may be "EC" or "OKP".) (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 This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDSA25519; Algorithm Name: ECDSA25519;
Algorithm Description: ECDSA using SHA-256 and curve Wei25519; Algorithm Description: ECDSA using SHA-256 and curve Wei25519;
Algorithm Usage Locations: alg; Algorithm Usage Locations: alg;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Section 4.3 of this specification; for Reference: specified in Section 4.3 of this specification; for
encodings, see Section 10.2; encodings, see Section 10.2;
Algorithm Analysis Document(s): Section 4.3 of this specification. 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 This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDH25519; Algorithm Name: ECDH25519;
Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/ Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/
curve Wei25519 and key derivation function HKDF SHA256; curve Wei25519 and key derivation function HKDF SHA256;
Algorithm Usage Locations: alg; Algorithm Usage Locations: alg;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Section 4.1 of this specification; for Reference: specified in Section 4.1 of this specification; for
encodings, see Section 10.3; encodings, see Section 10.3;
Algorithm Analysis Document(s): Section 4.1 of this specification. Algorithm Analysis Document(s): Section 4.1 of this specification.
11.2. IANA Considerations for Wei448 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 This section registers the following value in the IANA "COSE Elliptic
Curves" registry [IANA.COSE.Curves]. Curves" registry [IANA.COSE.Curves].
Name: Wei448; Name: Wei448;
Value: TBD (Requested value: -2); Value: TBD (Requested value: -2);
Key Type: EC2 or OKP; Key Type: EC2 or OKP;
skipping to change at page 24, line 5 skipping to change at page 26, line 5
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Appendix M.3 of this specification; for Reference: specified in Appendix M.3 of this specification; for
encodings, see Section 10.1; encodings, see Section 10.1;
Recommended: Yes. Recommended: Yes.
(Note that The "kty" value for Wei448 may be "EC2" or "OKP".) (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 This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms]. Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDSA448; Name: ECDSA448;
Value: TBD (Requested value: -47); Value: TBD (Requested value: -48);
Description: ECDSA with SHAKE256 and curve Wei448; Description: ECDSA with SHAKE256 and curve Wei448;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Section 4.4 of this specification; for Reference: specified in Section 4.4 of this specification; for
encodings, see Section 10.1; encodings, see Section 10.1;
Recommended: Yes. 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 This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms]. Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDH448; Name: ECDH448;
Value: TBD (Requested value: -48); Value: TBD (Requested value: -49);
Description: NIST-compliant co-factor Diffie-Hellman w/ curve Wei448 Description: NIST-compliant co-factor Diffie-Hellman w/ curve Wei448
and key derivation function HKDF SHA512; and key derivation function HKDF SHA512;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Section 4.4 of this specification; for Reference: specified in Section 4.4 of this specification; for
encodings, see Section 10.1; for key derivation, see encodings, see Section 10.1; for key derivation, see
Section 11.1 of [RFC8152]; Section 11.1 of [RFC8152];
Recommended: Yes. 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 This section registers the following value in the IANA "JSON Web Key
Elliptic Curve" registry [IANA.JOSE.Curves]. Elliptic Curve" registry [IANA.JOSE.Curves].
Curve Name: Wei448; Curve Name: Wei448;
Curve Description: short-Weierstrass curve Wei448; Curve Description: short-Weierstrass curve Wei448;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Appendix M.3 of this specification; for Reference: specified in Appendix M.3 of this specification; for
encodings, see Section 10.1. encodings, see Section 10.1.
(Note that The "kty" value for Wei448 may be "EC" or "OKP".) (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 This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDSA448; Algorithm Name: ECDSA448;
Algorithm Description: ECDSA using SHAKE256 and curve Wei448; Algorithm Description: ECDSA using SHAKE256 and curve Wei448;
Algorithm Usage Locations: alg; Algorithm Usage Locations: alg;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Section 4.4 of this specification; for Reference: specified in Section 4.4 of this specification; for
encodings, see Section 10.2; encodings, see Section 10.2;
Algorithm Analysis Document(s): Section 4.4 of this specification. 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 This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDH448; Algorithm Name: ECDH448;
Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/ Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/
curve Wei448; curve Wei448;
Algorithm Usage Locations: alg; Algorithm Usage Locations: alg;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Section 4.4 of this specification; for Reference: specified in Section 4.4 of this specification; for
encodings, see Section 10.3; encodings, see Section 10.3;
Algorithm Analysis Document(s): Section 4.4 of this specification. Algorithm Analysis Document(s): Section 4.4 of this specification.
12. Acknowledgements 13. Acknowledgements
Thanks to Nikolas Rosener for discussions surrounding implementation Thanks to Nikolas Rosener for discussions surrounding implementation
details of the techniques described in this document and to Phillip details of the techniques described in this document and to Phillip
Hallam-Baker for triggering inclusion of verbiage on the use of Hallam-Baker for triggering inclusion of verbiage on the use of
Montgomery ladders with recovery of the y-coordinate. Thanks to Montgomery ladders with recovery of the y-coordinate. Thanks to
Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews. Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews.
13. References 14. References
13.1. Normative References 14.1. Normative References
[ANSI-X9.62] [ANSI-X9.62]
ANSI X9.62-2005, "Public Key Cryptography for the ANSI X9.62-2005, "Public Key Cryptography for the
Financial Services Industry: The Elliptic Curve Digital Financial Services Industry: The Elliptic Curve Digital
Signature Algorithm (ECDSA)", American National Standard Signature Algorithm (ECDSA)", American National Standard
for Financial Services, Accredited Standards Committee X9, for Financial Services, Accredited Standards Committee X9,
Inc, Anapolis, MD, 2005. Inc, Anapolis, MD, 2005.
[FIPS-180-4] [FIPS-180-4]
FIPS 180-4, "Secure Hash Standard (SHS), Federal FIPS 180-4, "Secure Hash Standard (SHS), Federal
skipping to change at page 26, line 45 skipping to change at page 28, line 45
[FIPS-202] [FIPS-202]
FIPS 202, "SHA-3 Standard: Permutation-Based Hash and FIPS 202, "SHA-3 Standard: Permutation-Based Hash and
Extendable-Output Functions, Federal Information Extendable-Output Functions, Federal Information
Processing Standards Publication 202", US Department of Processing Standards Publication 202", US Department of
Commerce/National Institute of Standards and Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, August 2015. Technology, Gaithersburg, MD, August 2015.
[I-D.ietf-cose-rfc8152bis-algs] [I-D.ietf-cose-rfc8152bis-algs]
Schaad, J., "CBOR Object Signing and Encryption (COSE): Schaad, J., "CBOR Object Signing and Encryption (COSE):
Initial Algorithms", draft-ietf-cose-rfc8152bis-algs-11 Initial Algorithms", draft-ietf-cose-rfc8152bis-algs-12
(work in progress), July 2020. (work in progress), September 2020.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data
Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006, Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006,
<https://www.rfc-editor.org/info/rfc4648>. <https://www.rfc-editor.org/info/rfc4648>.
[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,
<https://www.rfc-editor.org/info/rfc5280>.
[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,
<https://www.rfc-editor.org/info/rfc5480>.
[RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography [RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography
(ECC) Brainpool Standard Curves and Curve Generation", (ECC) Brainpool Standard Curves and Curve Generation",
RFC 5639, DOI 10.17487/RFC5639, March 2010, RFC 5639, DOI 10.17487/RFC5639, March 2010,
<https://www.rfc-editor.org/info/rfc5639>. <https://www.rfc-editor.org/info/rfc5639>.
[RFC5652] Housley, R., "Cryptographic Message Syntax (CMS)", STD 70,
RFC 5652, DOI 10.17487/RFC5652, September 2009,
<https://www.rfc-editor.org/info/rfc5652>.
[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, <https://www.rfc-editor.org/info/rfc5753>.
[RFC7049] Bormann, C. and P. Hoffman, "Concise Binary Object [RFC7049] Bormann, C. and P. Hoffman, "Concise Binary Object
Representation (CBOR)", RFC 7049, DOI 10.17487/RFC7049, Representation (CBOR)", RFC 7049, DOI 10.17487/RFC7049,
October 2013, <https://www.rfc-editor.org/info/rfc7049>. October 2013, <https://www.rfc-editor.org/info/rfc7049>.
[RFC7515] Jones, M., Bradley, J., and N. Sakimura, "JSON Web [RFC7515] Jones, M., Bradley, J., and N. Sakimura, "JSON Web
Signature (JWS)", RFC 7515, DOI 10.17487/RFC7515, May Signature (JWS)", RFC 7515, DOI 10.17487/RFC7515, May
2015, <https://www.rfc-editor.org/info/rfc7515>. 2015, <https://www.rfc-editor.org/info/rfc7515>.
[RFC7518] Jones, M., "JSON Web Algorithms (JWA)", RFC 7518, [RFC7518] Jones, M., "JSON Web Algorithms (JWA)", RFC 7518,
DOI 10.17487/RFC7518, May 2015, DOI 10.17487/RFC7518, May 2015,
skipping to change at page 28, line 9 skipping to change at page 30, line 32
<https://www.rfc-editor.org/info/rfc8037>. <https://www.rfc-editor.org/info/rfc8037>.
[RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)", [RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)",
RFC 8152, DOI 10.17487/RFC8152, July 2017, RFC 8152, DOI 10.17487/RFC8152, July 2017,
<https://www.rfc-editor.org/info/rfc8152>. <https://www.rfc-editor.org/info/rfc8152>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>. May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[RFC8692] Kampanakis, P. and Q. Dang, "Internet X.509 Public Key
Infrastructure: Additional Algorithm Identifiers for
RSASSA-PSS and ECDSA Using SHAKEs", RFC 8692,
DOI 10.17487/RFC8692, December 2019,
<https://www.rfc-editor.org/info/rfc8692>.
[SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0", [SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0",
Standards for Efficient Cryptography, , June 2009. Standards for Efficient Cryptography, , June 2009.
[SEC2] SEC2, "SEC 2: Elliptic Curve Cryptography, Version 2.0", [SEC2] SEC2, "SEC 2: Elliptic Curve Cryptography, Version 2.0",
Standards for Efficient Cryptography, , January 2010. Standards for Efficient Cryptography, , January 2010.
[SP-800-56a] [SP-800-56a]
NIST SP 800-56a, "Recommendation for Pair-Wise Key NIST SP 800-56a, "Recommendation for Pair-Wise Key
Establishment Schemes Using Discrete Log Cryptography, Establishment Schemes Using Discrete Log Cryptography,
Revision 3", US Department of Commerce/National Institute Revision 3", US Department of Commerce/National Institute
of Standards and Technology, Gaithersburg, MD, April 2018. of Standards and Technology, Gaithersburg, MD, April 2018.
[SP-800-56c] [SP-800-56c]
NIST SP 800-56c, "Recommendation for Key-Derivation NIST SP 800-56c, "Recommendation for Key-Derivation
Methods in Key-Establishment Schemes, Revision 1", US Methods in Key-Establishment Schemes, Revision 1", US
Department of Commerce/National Institute of Standards and Department of Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, April 2018. Technology, Gaithersburg, MD, April 2018.
13.2. Informative References 14.2. Informative References
[comm-FIPS-186-5] [comm-FIPS-186-5]
FIPS 186-5, "Public Comments Received on Draft FIPS Pub FIPS 186-5, "Public Comments Received on Draft FIPS Pub
186-5", US Department of Commerce/National Institute of 186-5", US Department of Commerce/National Institute of
Standards and Technology, Gaithersburg, MD, April 6, 2020. Standards and Technology, Gaithersburg, MD, April 6, 2020.
[ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in [ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in
Cryptography", Cambridge University Press, Lecture Notes Cryptography", Cambridge University Press, Lecture Notes
Series 265, July 1999. Series 265, July 1999.
skipping to change at page 31, line 41 skipping to change at page 34, line 29
curve; k*P is commonly referred to as scalar multiplication of P by curve; k*P is commonly referred to as scalar multiplication of P by
k.) If (P) has cardinality l, then l is called the order of P and l 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 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|. 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. 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, 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 where n is a large prime number and where h is a small number (the
so-called co-factor), have a large cyclic subgroup of prime order n. so-called co-factor), have a large cyclic subgroup of prime order n.
In this case, a generator of order n is called a base point, commonly 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 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 small subgroup (or said to be a low-order point). For curves of
the singleton set, consisting of only the identity element O. A prime order, this small subgroup is the singleton set, consisting of
point that is not in the small subgroup is said to be a high-order only the identity element O. A point that is not in the small
point (since it has order at least n). A point P of the curve is in subgroup is said to be a high-order point (since it has order at
the small subgroup if h*P=O (and is a high-order point otherwise); least n). A point P of the curve is in the small subgroup if h*P=O
this point has order n if n*P=O and if it is not the identity element (and is a high-order point otherwise); this point has order n if
O. (The latter order check is commonly called full public key n*P=O and if it is not the identity element O. (The latter order
validation.) check is commonly called full public key validation.)
If R is a point of the curve that is also contained in (P), there is If R is a point of the curve that is also contained in (P), there is
a unique integer k in the interval [0, l-1] so that R=k*P, where l is a unique integer k in the interval [0, l-1] so that R=k*P, where l is
the order of P. This number is called the discrete logarithm of R to the order of P. This number is called the discrete logarithm of R to
the base P. The discrete logarithm problem is the problem of finding the base P. The discrete logarithm problem is the problem of finding
the discrete logarithm of R to the base P for any two points P and R the discrete logarithm of R to the base P for any two points P and R
of the curve, if such a number exists. of the curve, if such a number exists.
If P is a fixed base point G of the curve, the pair (k, R:=k*G) is If P is a fixed base point G of the curve, the pair (k, R:=k*G) is
commonly called a public-private key pair, the integer k the private commonly called a public-private key pair, the integer k the private
skipping to change at page 63, line 17 skipping to change at page 66, line 17
where alpha:=X^3+a*X+b. If alpha is not a square in GF(q), this where alpha:=X^3+a*X+b. If alpha is not a square in GF(q), this
equation does not have a solution in GF(q) and the ordered pair (X, equation does not have a solution in GF(q) and the ordered pair (X,
t) does not correspond to a point of this curve. Otherwise, there t) does not correspond to a point of this curve. Otherwise, there
are two solutions, viz. Y=sqrt(alpha) and -Y. If alpha is a nonzero are two solutions, viz. Y=sqrt(alpha) and -Y. If alpha is a nonzero
element of GF(q), one can uniquely recover the Y-coordinate for which element of GF(q), one can uniquely recover the Y-coordinate for which
par(Y):=t and, thereby, the point P:=(X, Y). This is also the case par(Y):=t and, thereby, the point P:=(X, Y). This is also the case
if alpha=0 and t=0, in which case Y=0 and the point P has order two. if alpha=0 and t=0, in which case Y=0 and the point P has order two.
However, if alpha=0 and t=1, the ordered pair (X, t) does not However, if alpha=0 and t=1, the ordered pair (X, t) does not
correspond to the outcome of the point compression function. correspond to the outcome of the point compression function.
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 We extend the definition of the point compression function to all
points of the curve W_{a,b}, by associating the (non-affine) point at points of the curve W_{a,b}, by associating the (non-affine) point at
infinity O with any ordered pair compr(O):=(X,0), where X is any infinity O with any ordered pair compr(O):=(X,0), where X is any
element of GF(q) for which alpha:=X^3+a*X+b is not a square in GF(q), element of GF(q) for which alpha:=X^3+a*X+b is not a square in GF(q),
and recover this point accordingly. In this case, the point at and recover this point accordingly. In this case, the point at
infinity O can be represented by any ordered pair (X,0) of elements infinity O can be represented by any ordered pair (X,0) of elements
of GF(q) for which X^3+a*X+b is not a square in GF(q). Note that of GF(q) for which X^3+a*X+b is not a square in GF(q). Note that
this ordered pair does not satisfy the defining equation of the curve this ordered pair does not satisfy the defining equation of the curve
in question. An application may fix a specific suitable value of X in question. An application may fix a specific suitable value of X
or choose multiple such values and use this to encode additonal or choose multiple such values and use this to encode additonal
skipping to change at page 66, line 9 skipping to change at page 69, line 17
There is a 1-1 correspondence between bit strings of length l and There is a 1-1 correspondence between bit strings of length l and
integers in the interval [0, 2^l), where the bit string integers in the interval [0, 2^l), where the bit string
X:=str(x_{l-1}, x_{l-2}, ..., x_1, x_0) corresponds to the integer X:=str(x_{l-1}, x_{l-2}, ..., x_1, x_0) corresponds to the integer
x:=x_{l-1}*2^{l-1} + x_{l-2}*2^{l-2} + ... + x_1*2 + x_0*1. (If l=0, x:=x_{l-1}*2^{l-1} + x_{l-2}*2^{l-2} + ... + x_1*2 + x_0*1. (If l=0,
the empty bit string corresponds to the integer zero.) Note that the empty bit string corresponds to the integer zero.) Note that
while the mapping from bit strings to integers is uniquely defined, while the mapping from bit strings to integers is uniquely defined,
the inverse mapping from integers to bit strings is not, since any the inverse mapping from integers to bit strings is not, since any
non-negative integer smaller than 2^t can be represented as a bit non-negative integer smaller than 2^t can be represented as a bit
string of length at least t (due to leading zero coefficients in base string of length at least t (due to leading zero coefficients in base
2 representation). The latter representation is called tight if the 2 representation). The latter representation is called tight if the
bit string representation has minimal length. This defines the bit string representation has minimal length (the so-called bit-
mapping BS2I from bit strings to integers and the mapping I2BS(x,l) length of the integer in question). This defines the mapping BS2I
from non-negative integers smaller than 2^l to bit strings of length from bit strings to integers and the mapping I2BS(x,l) from non-
l. negative integers smaller than 2^l to bit strings of length l.
I.3. Conversion between Octet Strings and Integers (OS2I, I2OS) I.3. Conversion between Octet Strings and Integers (OS2I, I2OS)
There is a 1-1 correspondence between octet strings of length l and There is a 1-1 correspondence between octet strings of length l and
integers in the interval [0, 256^l), where the octet string integers in the interval [0, 256^l), where the octet string
X:=str(X_{l-1}, X_{l-2}, ..., X_1, X_0) corresponds to the integer X:=str(X_{l-1}, X_{l-2}, ..., X_1, X_0) corresponds to the integer
x:=X_{l-1}*256^{l-1} + X^{l-2}*256^{l-2} + ... + X_1*256 + X_0*1. x:=X_{l-1}*256^{l-1} + X^{l-2}*256^{l-2} + ... + X_1*256 + X_0*1.
(If l=0, the empty string corresponds to the integer zero.) Note (If l=0, the empty string corresponds to the integer zero.) Note
that while the mapping from octet strings to integers is uniquely that while the mapping from octet strings to integers is uniquely
defined, the inverse mapping from integers to octet strings is not, defined, the inverse mapping from integers to octet strings is not,
since any non-negative integer smaller than 256^t can be represented since any non-negative integer smaller than 256^t can be represented
as an octet string of length at least t (due to leading zero as an octet string of length at least t (due to leading zero
coefficients in base 256 representation). The latter representation coefficients in base 256 representation). The latter representation
is called tight if the octet string representation has minimal is called tight if the octet string representation has minimal length
length. This defines the mapping OS2I from octet strings to integers (the so-called byte-length of the integer in question). This defines
and the mapping I2OS(x,l) from non-negative integers smaller than the mapping OS2I from octet strings to integers and the mapping
256^l to octet strings of length l. I2OS(x,l) from non-negative integers smaller than 256^l to octet
strings of length l.
I.4. Conversion between Octet Strings and Bit Strings (OS2BS, BS2OS) I.4. Conversion between Octet Strings and Bit Strings (OS2BS, BS2OS)
There is a 1-1 correspondence between octet strings of length l and There is a 1-1 correspondence between octet strings of length l and
bit strings of length 8*l, where the octet string X:=str(X_{l-1}, bit strings of length 8*l, where the octet string X:=str(X_{l-1},
X_{l-2}, ..., X_1, X_0) corresponds to the right-concatenation of the X_{l-2}, ..., X_1, X_0) corresponds to the right-concatenation of the
8-bit strings x_{l-1}, x_{l-2}, ..., x_1, x_0, where each octet X_i 8-bit strings x_{l-1}, x_{l-2}, ..., x_1, x_0, where each octet X_i
corresponds to the 8-bit string x_i according to the mapping of corresponds to the 8-bit string x_i according to the mapping of
Appendix I.2 above. Note that the mapping from octet strings to bit 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 strings is uniquely defined and so is the inverse mapping from bit
skipping to change at page 69, line 43 skipping to change at page 72, line 46
question. The inverse mapping results by converting the first and question. The inverse mapping results by converting the first and
second coordinate of this pair (each an octet string of length l*m) second coordinate of this pair (each an octet string of length l*m)
to, respectively, the elements X and Y of GF(q) via the strict OS2FE to, respectively, the elements X and Y of GF(q) via the strict OS2FE
mapping of Appendix I.5. Note that if it is not a priori known mapping of Appendix I.5. Note that if it is not a priori known
whether the input to this inverse mapping actually represents an whether the input to this inverse mapping actually represents an
affine curve point, one should check that this is indeed an ordered affine curve point, one should check that this is indeed an ordered
pair of octet strings (each of length l*m) and that the output (X,Y) pair of octet strings (each of length l*m) and that the output (X,Y)
-- if defined -- is indeed an affine point of the curve in question, -- if defined -- is indeed an affine point of the curve in question,
where this mapping fails if either condition is not satisfied. where this mapping fails if either condition is not satisfied.
The compressed point (X,t) or (t, X) is represented by the ordered The compressed point (X, t) or (t, X) is represented by the ordered
pair whose coordinates are the octet string representations of the pair whose coordinates are the octet string representations of the
parity bit t in {0,1} and the element X of GF(q), respectively, using parity bit t in {0,1} and the element X of GF(q), respectively, using
the tight FE2OS mapping of Appendix I.5. Note that, since we use the tight FE2OS mapping of Appendix I.5. Note that, since we use
tight representations, this results in an ordered pair of octet tight representations, this results in an ordered pair of octet
strings (of length 1 and l*m, respectively), where the parameters l strings (of length 1 and l*m, respectively), where the parameters l
and m are uniquely defined by the field GF(q) in question. The and m are uniquely defined by the field GF(q) in question. The
inverse mapping results by converting the first and second coordinate inverse mapping results by converting the first and second coordinate
of this pair (each an octet string, of length 1 and l*m, of this pair (each an octet string, of length 1 and l*m,
respectively) to, respectively, the element t of {0,1} and the respectively) to, respectively, the element t of {0,1} and the
element X of GF(q) via the strict OS2FE mapping of Appendix I.5, and element X of GF(q) via the strict OS2FE mapping of Appendix I.5, and
skipping to change at page 70, line 39 skipping to change at page 73, line 42
affine points as above (as octet string), but prepends this with the affine points as above (as octet string), but prepends this with the
1-octet prefix 0x04, and represents the identity element of the curve 1-octet prefix 0x04, and represents the identity element of the curve
as the 1-octet string 0x00. This variable-size point representation as the 1-octet string 0x00. This variable-size point representation
has the property that its 1-octet prefix identifies whether it has the property that its 1-octet prefix identifies whether it
encodes an affine curve point, a compressed point (including parity encodes an affine curve point, a compressed point (including parity
bit), or the identity element, while the remainder of this bit), or the identity element, while the remainder of this
representation uniquely determines the curve point's value. While representation uniquely determines the curve point's value. While
the description in [SEC1] only applies to Weierstrass curves, the the description in [SEC1] only applies to Weierstrass curves, the
description above applies to each of the curve models we consider description above applies to each of the curve models we consider
(i.e., these apply to Montgomery curves and twisted Edwards curves as (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. representation.
Note that elements of a prime field GF(p), where p is a 255-bit prime Note that elements of a prime field GF(p), where p is a 255-bit prime
number, have a tight representation as a 32-octet string, where a number, have a tight representation as a 32-octet string, where a
fixed bit position is always set to zero. (This is the leftmost bit fixed bit position is always set to zero. (This is the leftmost bit
position of this octet string if one follows the MSB/msb position of this octet string if one follows the MSB/msb
representation conventions.) This allows the parity bit of a representation conventions.) This allows the parity bit of a
compressed point (see Appendix H) to be encoded in this bit position compressed point (see Appendix H) to be encoded in this bit position
and, thereby, allows a compressed point and an element of GF(p) to be and, thereby, allows a compressed point and an element of GF(p) to be
represented by an octet string of the same length. This is called represented by an octet string of the same length. This is called
skipping to change at page 73, line 46 skipping to change at page 77, line 4
msb order is given by msb order is given by
t1 409531317901122685707535715924445398426503483189854716584 t1 409531317901122685707535715924445398426503483189854716584
37762538294289253464 37762538294289253464
(=0x5844b232 8c4586dc 62f593c5 599c2a8c e61ba893 bb052de6 (=0x5844b232 8c4586dc 62f593c5 599c2a8c e61ba893 bb052de6
77510a42 b3a68a5a) 77510a42 b3a68a5a)
t2 451856098332889407421278004628150814449259902023388533929 t2 451856098332889407421278004628150814449259902023388533929
08848927625430980881 08848927625430980881
(=0x11598452 e65138dc ce948d7e d8f46a18 b640722c 8e170957 (=0x11598452 e65138dc ce948d7e d8f46a18 b640722c 8e170957
751b7729 1b26e663), 751b7729 1b26e663),
where this representation is defined in Appendix K.5 and uses the where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.2 with the default square root function. 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 J.2. Example with Edwards25519
Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Edwards25519: Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Edwards25519:
x 25301662348702136092602268236183361085863932475593120475382959053 x 25301662348702136092602268236183361085863932475593120475382959053
365387223252 365387223252
(=0x37f03bc0 1070ed12 d3218f8b ba1abb74 fd6b94eb 62033d09 (=0x37f03bc0 1070ed12 d3218f8b ba1abb74 fd6b94eb 62033d09
83851e21 d6a460d4). 83851e21 d6a460d4).
skipping to change at page 75, line 39 skipping to change at page 79, line 18
05479716220480287974 05479716220480287974
(=0x672e36c5 ae353073 cdfac343 e8297b05 1b010d0f 5b1016db (=0x672e36c5 ae353073 cdfac343 e8297b05 1b010d0f 5b1016db
dd4baf54 28068926), dd4baf54 28068926),
where this representation is defined in Appendix K.5 and uses the where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.3 with the default square root function and mapping of Appendix K.3.3 with the default square root function and
underlying isomorphic mapping between Edwards25519 and Curve25519 of underlying isomorphic mapping between Edwards25519 and Curve25519 of
Appendix E.2. 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 J.3. Example with Wei25519
Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519: Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519:
X 14428294459702615171094958724191825368445920488283965295163094662 X 14428294459702615171094958724191825368445920488283965295163094662
783879239338 783879239338
(=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7 (=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7
2a41cf12 629e56aa). 2a41cf12 629e56aa).
skipping to change at page 78, line 8 skipping to change at page 82, line 5
t2 213890166610228613105792710708385961712211281744756216061 t2 213890166610228613105792710708385961712211281744756216061
11930888059603107561 11930888059603107561
(=0x2f49c121 8fed7912 031157ee ae066507 a972320b 6180e267 (=0x2f49c121 8fed7912 031157ee ae066507 a972320b 6180e267
4025b006 2e67bee9), 4025b006 2e67bee9),
where this representation is defined in Appendix K.5 and uses the where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.1 with the default square root function. 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 J.4. Example with Wei25519.2
Pw2=(X, Y), k*Pw2=(X1, Y1), and (k+1)*Pw2=(X2, Y2) with Wei25519.2: Pw2=(X, Y), k*Pw2=(X1, Y1), and (k+1)*Pw2=(X2, Y2) with Wei25519.2:
X 17830493209951148331008014701079988862634531394137235438571836389 X 17830493209951148331008014701079988862634531394137235438571836389
227198459763 227198459763
(=0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c (=0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c
f21c8672 d1ecaf73). f21c8672 d1ecaf73).
skipping to change at page 79, line 35 skipping to change at page 84, line 5
t2 361115271162391608083096560179337391059615651279123199921 t2 361115271162391608083096560179337391059615651279123199921
18531180247832114098 18531180247832114098
(=0x4fd66668 e7174775 de44c852 92df8cfe b9832ef8 2570b3b8 (=0x4fd66668 e7174775 de44c852 92df8cfe b9832ef8 2570b3b8
fe5ec21a b2d4b3b2), fe5ec21a b2d4b3b2),
where this representation is defined in Appendix K.5 and uses the where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.1 with the default square root function. 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 J.5. Example with Wei25519.-3
Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei25519.-3: Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei25519.-3:
X 14780197759513083469009623947734627174363231692126610860256057394 X 14780197759513083469009623947734627174363231692126610860256057394
455099634096 455099634096
(=0x20ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00 (=0x20ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00
eb4c9272 03ca71b0). eb4c9272 03ca71b0).
skipping to change at page 81, line 14 skipping to change at page 86, line 5
t2 269945781324580189815142015663892935722419453863927287235 t2 269945781324580189815142015663892935722419453863927287235
57891665397640090729 57891665397640090729
(=0x3bae63c8 70f60de0 c2e35f94 d24220f1 bb6efd00 37625869 (=0x3bae63c8 70f60de0 c2e35f94 d24220f1 bb6efd00 37625869
f84923de ff4c5469), f84923de ff4c5469),
where this representation is defined in Appendix K.5 and uses the where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.1 with the default square root function. 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 Appendix K. Auxiliary Functions
This section illustrates how one could implement common routines, This section illustrates how one could implement common routines,
such as taking square roots and inverses in finite fields, and how to 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 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) K.1. Square Roots in GF(q)
Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see
Appendix K.1.1) or if q = 5 (mod 8) (see Appendix K.1.2). Details on Appendix K.1.1) or if q = 5 (mod 8) (see Appendix K.1.2). Details on
how to compute square roots for other values of q are out of scope. how to compute square roots for other values of q are out of scope.
If square roots are easy to compute in GF(q), then so are these in If square roots are easy to compute in GF(q), then so are these in
GF(q^2). GF(q^2).
K.1.1. Square Roots in GF(q), where q = 3 (mod 4) K.1.1. Square Roots in GF(q), where q = 3 (mod 4)
skipping to change at page 83, line 10 skipping to change at page 88, line 16
point of W_{a,b}, depending on whether f(X) is a square in GF(q). point of W_{a,b}, depending on whether f(X) is a square in GF(q).
a. If f(X) is a square in GF(q) and Y:=sqrt(f(X)), then t is mapped a. If f(X) is a square in GF(q) and Y:=sqrt(f(X)), then t is mapped
to the point P(t):=(X, Y); to the point P(t):=(X, Y);
b. If f(X) is not a square in GF(q) and Y':=sqrt(f(X')), then t is b. If f(X) is not a square in GF(q) and Y':=sqrt(f(X')), then t is
mapped to the point P(t):=(X', -Y'). mapped to the point P(t):=(X', -Y').
Formally, this mapping is not properly defined, since a nonzero Formally, this mapping is not properly defined, since a nonzero
square y:=x^2 in GF(q) has two solutions, viz. x and -x; it is square y:=x^2 in GF(q) has two solutions, viz. x and -x; it is
properly defined, however, if one designates for each element in properly defined, however, if one designates for each element of
GF(q) that is a square in GF(q) precisely one square root as "the" GF(q) that is a square in GF(q) precisely one square root as "the"
square root of this element. Note that always picking the square square root of this element. Note that always picking the square
root with zero parity (see Appendix H) satisfies this condition root with zero parity (see Appendix H) satisfies this condition
(henceforth called the default square root function). (henceforth called the default square root function).
If -1 is not a square in GF(q), this element is mapped to the point If -1 is not a square in GF(q), this element is mapped to the point
at infinity O of W_{a,b}. at infinity O of W_{a,b}.
The set of points of W_{a,b} that arises this way has size roughly The set of points of W_{a,b} that arises this way has size roughly
3/8 of the order of the curve and each such point arises as image of 3/8 of the order of the curve and each such point arises as image of
one or two t values. Further details are out of scope. one or two t values. Further details are out of scope.
NOTE 1: If -1 is not a square in GF(q), the mapping above yields the NOTE 1: If -1 is not a square in GF(q), the mapping above yields the
point at infinity for t=-1. One can modify this mapping, by mapping 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 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 point G or any other affine point) and leaving the remainder of the
mapping the same. Suitability of such a modification is application- mapping the same. Suitability of such a modification is application-
specific. Details are out of scope. specific. Details are out of scope.
NOTE 2: The description above assumes that the domain parameters a NOTE 2: The description above assumes that the domain parameters a
and b of the Weierstrass curve are nonzero. If this is not the case, and b of the Weierstrass curve W_{a,b} are nonzero. If this is not
one can often find an isogenous curve W_{a',b'} for which the domain the case, one can often find an isogenous curve W_{a',b'} for which
parameters a' and b' are nonzero. If so, one can map elements of the domain parameters a' and b' are nonzero. If so, one can map
GF(q) that are not a square in GF(q) to points of W_{a,b} via elements of GF(q) that are not a square in GF(q) to points of W_{a,b}
function composition, where one uses the mapping above to arrive at a via function composition, where one uses the mapping above to arrive
point of W_{a',b'} and where one subsequently uses the dual isogeny at a point of W_{a',b'} and where one subsequently uses the dual
from W_{a',b'} to W_{a,b} to arrive at a point of W_{a,b}. As an isogeny from W_{a',b'} to W_{a,b} to arrive at a point of W_{a,b}. As
example, one can show that if a is zero and if -4*b is a cube in 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 GF(q) (such as is the case with, e.g., the "BitCoin" curve secp256k1
[SEC2]), this curve is 3-isogenous to a curve with this property and [SEC2]), this curve is 3-isogenous to a curve with this property and
the strategy above applies (for an example with secp256k1, see the strategy above applies (for an example with secp256k1, see
Appendix L). Further details are out of scope. Appendix L). Further details are out of scope.
K.3.2. Mapping to Points of Montgomery Curve K.3.2. Mapping to Points of Montgomery Curve
The description below assumes that the domain parameter A of the The description below assumes that the domain parameter A of the
Montgomery curve M_{A,B} is nonzero. For ease of exposition, we Montgomery curve M_{A,B} is nonzero. For ease of exposition, we
define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of
skipping to change at page 84, line 16 skipping to change at page 89, line 26
on whether f(u)/B is a square in GF(q). on whether f(u)/B is a square in GF(q).
a. If f(u)/B is a square in GF(q) and v:=sqrt(f(u)/B), then t is a. If f(u)/B is a square in GF(q) and v:=sqrt(f(u)/B), then t is
mapped to the point P(t):=(u, v); mapped to the point P(t):=(u, v);
b. If f(u)/B is a not a square in GF(q) and v':=sqrt(f(u')/B), then b. If f(u)/B is a not a square in GF(q) and v':=sqrt(f(u')/B), then
t is mapped to the point P(t):=(u', -v'). t is mapped to the point P(t):=(u', -v').
As before, formally, this mapping is not properly defined, since a As before, formally, this mapping is not properly defined, since a
nonzero square y:=x^2 in GF(q) has two solutions, viz. x and -x; it nonzero square y:=x^2 in GF(q) has two solutions, viz. x and -x; it
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" GF(q) that is a square in GF(q) precisely one square root as "the"
square root of this element. Note that always picking the square square root of this element. Note that always picking the square
root with zero parity (see Appendix H) satisfies this condition root with zero parity (see Appendix H) satisfies this condition
(henceforth called the default square root function). (henceforth called the default square root function).
If -1 is not a square in GF(q), this element is mapped to the point If -1 is not a square in GF(q), this element is mapped to the point
at infinity O of M_{A,B}. at infinity O of M_{A,B}.
The set of points of M_{A,B} that arises this way has size roughly The set of points of M_{A,B} that arises this way has size roughly
1/2 of the order of the curve and each such point arises as image of 1/2 of the order of the curve and each such point arises as image of
precisely one t value. Further details are out of scope. precisely one t value. Further details are out of scope.
NOTE 1: If -1 is not a square in GF(q), the mapping above yields the NOTE 1: If -1 is not a square in GF(q), the mapping above yields the
point at infinity for t=-1. One can modify this mapping, by mapping 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 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 point G or any other affine point) and leaving the remainder of the
mapping the same. Suitability of such a modification is application- mapping the same. Suitability of such a modification is application-
specific. Details are out of scope. specific. Details are out of scope.
NOTE 2: The description above assumes that the domain parameter A of NOTE 2: The description above assumes that the domain parameter A of
the Montgomery curve is nonzero. If this is not the case, the curve the Montgomery curve M_{A,B} is nonzero. If this is not the case,
is a Weierstrass curve for which the domain parameter b is zero and the curve is a Weierstrass curve for which the domain parameter b is
Note 2 of Appendix K.3.1 applies. If q = 3 (mod 4), an even simpler zero and Note 2 of Appendix K.3.1 applies. If q = 3 (mod 4), an even
approach is possible, where one modifies the construction above and simpler approach is possible, where one modifies the construction
simply takes u:=t and u':=-t (which works, since -1 is not a square above and simply takes u:=t and u':=-t (which works, since -1 is not
in GF(q) and f(-t)=-f(t)). In this case, this construction can be a square in GF(q) and f(-t)=-f(t)). In this case, this construction
extended to all elements t of GF(q) and, if so, yields a 1-1 mapping can be extended to all elements t of GF(q) and, if so, yields a 1-1
between GF(q) and all affine curve points. mapping between GF(q) and all affine curve points.
K.3.3. Mapping to Points of Twisted Edwards Curve K.3.3. Mapping to Points of Twisted Edwards Curve
One can map elements of GF(q) that are not a square in GF(q) to One can map elements of GF(q) that are not a square in GF(q) to
points of the twisted Edwards curve E_{a,d} via function composition, points of the twisted Edwards curve E_{a,d} via function composition,
where one uses the mapping of Appendix K.3.1 to arrive at a point of where one uses the mapping of Appendix K.3.1 to arrive at a point of
the Weierstrass curve W_{a,b} and where one subsequently uses the the Weierstrass curve W_{a,b} and where one subsequently uses the
isomorphic mapping between twisted Edwards curves and Weierstrass isomorphic mapping between twisted Edwards curves and Weierstrass
curves of Appendix D.3 to arrive at a point of E_{a,d}. Another curves of Appendix D.3 to arrive at a point of E_{a,d}. Another
mapping is obtained by function composition, where one instead uses mapping is obtained by function composition, where one instead uses
skipping to change at page 87, line 20 skipping to change at page 93, line 5
up to two values of the pair (t,s). Further details are out of up to two values of the pair (t,s). Further details are out of
scope. scope.
From the group law for Montgomery curves (see Appendix C.2) it 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, follows that one can express the coordinates of Q(t,s), with t<>-1,
in terms of the u-coordinates of P0 and P(t) and the product of their in terms of the u-coordinates of P0 and P(t) and the product of their
v-coordinates. (Here, observe that B*v0*v is a square root of v-coordinates. (Here, observe that B*v0*v is a square root of
f(u0)*f(u).) Thus, Q(t,s) can be computed without the need to fully f(u0)*f(u).) Thus, Q(t,s) can be computed without the need to fully
compute P(t). compute P(t).
+----------------------------+------------------------+ +----------------------------+------------------------+-------------+
| Curve | Fixed curve offset P0 | | Curve | Fixed curve offset P0 | Non-Square |
+----------------------------+------------------------+ +----------------------------+------------------------+-------------+
| NIST P-224 [FIPS-186-4] | Base point (Gx,Gy) | | NIST P-224 [FIPS-186-4] | Base point (Gx,Gy) | 11 |
| NIST P-256 [FIPS-186-4] | P0:=(0,y) with y even | | NIST P-256 [FIPS-186-4] | P0:=(0,y), y even | -1 |
| NIST P-384 [FIPS-186-4] | P0:=(0,y) with y even | | NIST P-384 [FIPS-186-4] | P0:=(0,y), y even | -1 |
| NIST P-521 [FIPS-186-4] | P0:=(0,y) with y even | | NIST P-521 [FIPS-186-4] | P0:=(0,y), y even | -1 |
| Brainpool224r1 [RFC5639] | Base point (Gx, Gy) | | Brainpool224r1 [RFC5639] | Base point (Gx, Gy) | -1 |
| Brainpool256r1 [RFC5639] | Base point (Gx, Gy) | | Brainpool256r1 [RFC5639] | Base point (Gx, Gy) | -1 |
| Brainpool320r1 [RFC5639] | Base point (Gx, Gy) | | Brainpool320r1 [RFC5639] | Base point (Gx, Gy) | -1 |
| Brainpool384r1 [RFC5639] | Base point (Gx, Gy) | | Brainpool384r1 [RFC5639] | Base point (Gx, Gy) | -1 |
| Brainpool512r1 [RFC5639] | P0:=(3,y), y even | | Brainpool512r1 [RFC5639] | P0:=(3,y), y even | -1 |
| Curve25519 [RFC7748] | P0:=(90,v), v even | | Curve25519 [RFC7748] | P0:=(90,v), v even | 2 |
| Curve448 [RFC7748] | P0:=(50,v), v even | | Wei25519 [Appendix E.3] | P0:=(3,y), y even | 2 |
| Wei25519 [Appendix E.3] | P0:=(3,y), y even | | Wei25519.2 [Appendix G.3] | P0:=(244,y), y even | 2 |
| Wei25519.2 [Appendix G.3] | P0:=(244,y), y even | | Wei25519.-3 [Appendix G.3] | P0:=(41,y), y even | 2 |
| Wei25519.-3 [Appendix G.3] | P0:=(41,y), y even | | Curve448 [RFC7748] | P0:=(50,v), v even | -1 |
| secp256k1.m [Appendix L.3] | P0:=(0,y), y even | | 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 low-order points Table 1: Fixed curve offsets for mappings that avoid low-order
points, for some curves of practical interest, including listing of
fixed non-square elements of their underlying finite fields.
K.4.3. Mapping to High-Order Points of Twisted Edwards Curve K.4.3. Mapping to High-Order Points of Twisted Edwards Curve
One can map elements of GF(q) that are not a square in GF(q) to One can map elements of GF(q) that are not a square in GF(q) to
points of the twisted Edwards curve E_{a,d} via function composition, points of the twisted Edwards curve E_{a,d} via function composition,
where one uses the mapping of Appendix K.4.1 to arrive at a point of 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 the Weierstrass curve W_{a,b} that is not in the small subgroup and
one subsequently uses the isomorphic mapping between twisted Edwards where one subsequently uses the isomorphic mapping between twisted
curves and Weierstrass curves of Appendix D.3 to arrive at a point of Edwards curves and Weierstrass curves of Appendix D.3 to arrive at a
E_{a,d} with this property. Another mapping is obtained by function point of E_{a,d} with this property. Another mapping is obtained by
composition, where one instead uses the mapping of Appendix K.4.2 to function composition, where one instead uses the mapping of
arrive at a point of the Montgomery curve M_{A,B} that does not have Appendix K.4.2 to arrive at a point of the Montgomery curve M_{A,B}
low order and where one subsequently uses the isomorphic mapping that does not have low order and where one subsequently uses the
between twisted Edwards curves and Montgomery curves of Appendix D.1 isomorphic mapping between twisted Edwards curves and Montgomery
to arrive at a point of E_{a,d} with this property. Obviously, one curves of Appendix D.1 to arrive at a point of E_{a,d} with this
can use function composition (now using the respective pre-images - property. Obviously, one can use function composition (now using the
if these exist) to realize the pre-images of either mapping. respective pre-images - if these exist) to realize the pre-images of
either mapping.
K.5. Randomized Representation of Curve Points K.5. Randomized Representation of Curve Points
The mappings of Appendix K.3 allow one to represent a curve point Q 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 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 point in the range of the mapping at hand. For Montgomery curves and
twisted Edwards curves, this covers roughly half of the curve points; twisted Edwards curves, this covers roughly half of the curve points;
for Weierstrass curves, roughly 3/8 of the curve points. One can 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 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 the point Q:=P2(t1, t2):=P(t1) + P(t2). In this case, each curve
skipping to change at page 89, line 14 skipping to change at page 95, line 8
NOTE 1: The main difference between the two constructions above is NOTE 1: The main difference between the two constructions above is
that that the first construction uses the mappings to curve points that that the first construction uses the mappings to curve points
described in Appendix K.3, while the second construction uses the described in Appendix K.3, while the second construction uses the
mappings to high-order curve points described in Appendix K.4. Note mappings to high-order curve points described in Appendix K.4. Note
that Q2((t1,s1), (t2,s2)) assumes all values (+/-) P(t1) (+/-) P(t2) that Q2((t1,s1), (t2,s2)) assumes all values (+/-) P(t1) (+/-) P(t2)
if one considers all possible values for the binary digits s1 and s2. if one considers all possible values for the binary digits s1 and s2.
(This, thereby, includes the value P2(t1, t2).) (This, thereby, includes the value P2(t1, t2).)
NOTE 2: The results on the statistical distributions mentioned above NOTE 2: The results on the statistical distributions mentioned above
still hold if one makes a few localized changes to the constructions. still hold in practice if one makes a few localized changes to the
In particular, these are independent of the specific choices for the constructions. In particular, these are independent of the specific
point P0 (used with input -1 with the mappings of Appendix K.3, if choices for the point P0 (used with input -1 with the mappings of
applicable, respectively, used with the mappings of Appendix K.4) and Appendix K.3, if applicable, respectively, used with the mappings of
also still hold if one re-defines the mappings P2 or Q2 locally so as Appendix K.4) and also still hold if one re-defines the mappings P2
to avoid points in the small subgroup. or Q2 locally so as to avoid points in the small subgroup.
K.6. Completing the Mappings to Curve Points K.6. Completing the Mappings to Curve Points
The mappings of Appendix K.4 operate on input pairs (t, s), where t 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 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 binary digit from the set {0,1}. One can use these mappings to
produce a mapping from the nonzero elements of GF(q) to points of a produce mappings that operate on input pairs (u, s), where u is any
particular curve via function composition, where one first maps any nonzero element of GF(q), via function composition, where one first
nonzero element u of GF(q) to the pair (t,s):=(delta*u^2, par(u)), maps the pair (u,s) to the pair (t,s):=(delta*u^2,s), where delta is
where delta is a fixed element of GF(q) that is not a square in a fixed element of GF(q) that is not a square in GF(q), and where one
GF(q), and where one subsequently applies any of the mappings to subsequently applies any of forementioned mappings to the resulting
yield a point of the curve in question. The resulting mapping from pair to yield a point of the curve in question. The resulting
the nonzero elements of GF(q) to high-order curve points can be mapping to high-order curve points can be extended further to one
extended further to one that operates on all elements of GF(q) by that operates on all elements of GF(q)x{0,1} by mapping each input
mapping 0 to any fixed high-order point P1 of the curve in question. (u, s) with u=0 to any fixed high-order point P1 of the curve in
The resulting mapping is uniquely defined after fixing the curve question. The resulting mapping is uniquely defined after fixing the
offset P0 (used with the mappings of Appendix K.4), the high-order curve offset P0 (used with the mappings of Appendix K.4), the high-
point P1 (used for input 0 above), and the non-square element delta order point P1 (used for inputs with u=0 above), and the non-square
of GF(q) (used for nonzero inputs above). element delta of GF(q) (used for nonzero inputs u above).
For the mappings of Appendix K.3, one can use a similar function 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 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 the point at infinity or any other suitable curve point P1. As
before, the resulting mapping is uniquely defined after fixing the before, the resulting mapping is uniquely defined after fixing the
point P0 (for input -1 with the mappings of Appendix K.3, if 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- applicable), the point P1 (used for input u=0 above), and the non-
square element delta of GF(q) (used for nonzero inputs above). square element delta of GF(q) (used for nonzero inputs u above).
Further details are out of scope. Further details are out of scope.
Similarly, one can use the completed mappings above to map a pair 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 ((u1,s1), (u2,s2)) of elements of GF(q)x{0,1} to a point of a curve,
composition, where, in the first case, one first maps the pair (u1, via function composition, where, in the first case, one first maps
u2) to the pair ((t1,s1), (t2,s2)):=((delta*u1^2, par(u1)), the pair ((u1,s1),(u2,s2)) to the pair ((t1,s1),
(delta*u2^2, par(u2))) and subsequently computes Q2compl((t1,s1), (t2,s2)):=((delta*u1^2, s1), (delta*u2^2, s2)) and subsequently
(t2,s2)):=Qcompl(t1,s1) - Qcompl(t2,s2), where Qcompl(t,s):=Q(t,s) if computes Q2compl((t1,s1), (t2,s2)):=Qcompl(t1,s1) - Qcompl(t2,s2),
t is nonzero and where Qcompl(0,s):=P0 otherwise (irrespective of the where Qcompl(t,s):=Q(t,s) if t is nonzero and where Qcompl(0,s):=P0
value of s). In the second case, one first maps the pair (u1, u2) to otherwise (irrespective of the value of s). In the second case, one
the pair (t1, t2):=(delta*u1^2, delta*u2^2) and subsequently computes first maps the pair (u1, u2) to the pair (t1, t2):=(delta*u1^2,
P2compl(t1, t2):=Pcompl(t1) + Pcompl(t2), where Pcompl(t):=P(t) if t delta*u2^2) and subsequently computes P2compl(t1, t2):=Pcompl(t1) +
is nonzero and where Pcompl(0):=P1 otherwise. In either case, again, Pcompl(t2), where Pcompl(t):=P(t) if t is nonzero and where
the resulting mapping is uniquely defined after fixing the points P0 Pcompl(0):=P1 otherwise. In either case, again, the resulting
and P1 and the non-square element delta of GF(q). mapping is uniquely defined after fixing the points P0 and P1 and the
non-square 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 re-defined 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 m-1, where m is the bit-size of p, thereby allowing the pair
(u1, u2) -- a random (2*m-2)-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 Appendix L. Curve secp256k1 and Friend
This section illustrates how isogenies can be used to yield curves This section illustrates how isogenies can be used to yield curves
with specific properties (here, illustrated for the "BitCoin" curve with specific properties (here, illustrated for the "BitCoin" curve
secp256k1). secp256k1).
L.1. Curve Definition and Alternative Representation L.1. Curve Definition and Alternative Representation
The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined
skipping to change at page 99, line 34 skipping to change at page 106, line 7
infinity of Wei448.1. (Here, we used the mapping of Appendix F.3.) 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 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 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 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 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 point at infinity O of Wei448. Note that this mapping (and its
inverse) involves a modular multiplication of both coordinates with inverse) involves a modular multiplication of both coordinates with
fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which
can be precomputed. can be precomputed.
Each affine point (X,Y) of Wei448 for which the Y-coordinate is The point at infinity and the point (A/3,0) of order two of Wei448
nonzero (i.e., each point with order larger than two) corresponds to both correspond to the point at infinity of Wei448.-3, while each
the point (X',Y'):=(X1*t^2,Y1*t^3) of Wei448.-3, where 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 (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 polynomials with coefficients in GF(p) as defined in Appendix N.4.1
and where t is the element of GF(p) defined by and where t is the element of GF(p) defined by
t 23579450751475691430882365546539966269774125426758968522698856022 t 23579450751475691430882365546539966269774125426758968522698856022
13378944265540874438945283200254318223329383397068961863760712339 13378944265540874438945283200254318223329383397068961863760712339
07365 07365
(=0x530c9a1d7cf071d09646b83db246626b4e57ba5d6a791bef761972543209d (=0x530c9a1d 7cf071d0 9646b83d b246626b 4e57ba5d 6a791bef
c5c20d81498d5ab8d7a2fb22507ca68c040a6c82eb3b6c7aaa5), 76197254 3209dc5c 20d81498 d5ab8d7a 2fb22507 ca68c040 a6c82eb3
b6c7aaa5).
while the point at infinity and the point (A/3,0) of order two of (Here, we used the isogenous mapping of Appendix F.4.) Under this
Wei448 corresponds to the point at infinity of Wei448.-3. (Here, we isogenous mapping, the base point (GX,GY) of Wei448 corresponds to
used the isogenous mapping of Appendix F.4.) Under this isogenous the base point (G3X,G3Y) of Wei448.-3. The dual isogeny maps the
mapping, the base point (GX,GY) of Wei448 corresponds to the base point at infinity O and the point (tau,0) of order two of Wei448.-3,
point (G3X,G3Y) of Wei448.-3. The dual isogeny maps the affine point 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') of Wei448.-3 to the affine point
(X,Y):=(u'(X1)/w'(X1),Y1*v'(X1)/w'(X1)^2) of Wei448, where (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 (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 with coefficients in GF(p) as defined in Appendix N.4.2. Under this
mapping the point at infinity O of Wei448.-3 to the point at infinity dual isogenous mapping, the base point (G3X, G3Y) of Wei448.-3
O of Wei448. Under this dual isogenous mapping, the base point (G3X, corresponds to a multiple of the base point (GX, GY) of Wei448, where
G3Y) of Wei448.-3 corresponds to a multiple of the base point (GX, this multiple is l=2 (the degree of the isogeny; see the description
GY) of Wei448, where this multiple is l=2 (the degree of the isogeny; in Appendix F.4). Note that this isogenous map (and its dual)
see the description in Appendix F.4). Note that this isogenous map primarily involves the evaluation of three fixed polynomials
(and its dual) primarily involves the evaluation of three fixed involving the x-coordinate, which takes only a few modular
polynomials involving the x-coordinate, which takes only a few multiplications (less than 0.5% relative incremental cost compared to
modular multiplications (less than 0.5% relative incremental cost the cost of an elliptic curve scalar multiplication).
compared to the cost of an elliptic curve scalar multiplication).
Each point (x1,y1) of Edwards448 with nonzero coordinates corresponds Each point (x1,y1) of Edwards448 with nonzero coordinates corresponds
to the point (x,y) of Ed448, where to the point (x,y) of Ed448, where
x = c*x1*y1/(1-d1*x1^2*y1^2) = c*x1*y1/(2-x1^2-y1^2) and x = c*x1*y1/(1-d1*x1^2*y1^2) = c*x1*y1/(2-x1^2-y1^2) and
y =(1 + d1*x1^2*y1^2)/(y1^2-x1^2) = -(x1^2+y1^2)/(x1^2-y1^2), y =(1 + d1*x1^2*y1^2)/(y1^2-x1^2) = -(x1^2+y1^2)/(x1^2-y1^2),
while each other point (i.e., a point of order 1, 2, or 4) 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 corresponds to the identity element (0,1) of Ed448. (Here, we used
skipping to change at page 108, line 16 skipping to change at page 115, line 5
460881642951497067363381071471046477130052706607411985560 460881642951497067363381071471046477130052706607411985560
522861593611384288817 522861593611384288817
(=0x3176361c 580a7bcd d7880d84 aba10bc6 57010328 afb728cc (=0x3176361c 580a7bcd d7880d84 aba10bc6 57010328 afb728cc
2016461b 246bef46 0eb4bb04 8c1a3616 c3f74a56 3cc1790f 2016461b 246bef46 0eb4bb04 8c1a3616 c3f74a56 3cc1790f
6472256b ca3481c8), 6472256b ca3481c8),
where this representation is defined in Appendix K.5 and uses the where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.2 with the default square root function. 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 O.2. Example with Ed448
Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Ed448: Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Ed448:
x 12711234107145442394649604543297947887906244696692372551963816418 x 12711234107145442394649604543297947887906244696692372551963816418
93066253979844478364753304240794498368174540810674220788120782656 93066253979844478364753304240794498368174540810674220788120782656
62747 62747
(=0x2cc52fd1 6370554f 00c0f73f 64bda240 f5950177 d9033f6d (=0x2cc52fd1 6370554f 00c0f73f 64bda240 f5950177 d9033f6d
74acd12d 68c79a51 315f556f 240973f9 e5f71ed7 9314ee9d c87f0b1b 74acd12d 68c79a51 315f556f 240973f9 e5f71ed7 9314ee9d c87f0b1b
skipping to change at page 110, line 21 skipping to change at page 117, line 34
(=0x94ecb72a 069a5322 e62d9357 c49d5664 1c351611 d1f361a8 (=0x94ecb72a 069a5322 e62d9357 c49d5664 1c351611 d1f361a8
cbb8a12c f410e821 4fbe8e02 8d85d404 399b4c7c 5a6a72ce cbb8a12c f410e821 4fbe8e02 8d85d404 399b4c7c 5a6a72ce
deef7b08 96302d5f), deef7b08 96302d5f),
where this representation is defined in Appendix K.5 and uses the where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.3 with the default square root function and mapping of Appendix K.3.3 with the default square root function and
underlying isomorphic mapping between Ed448 and Curve448 of underlying isomorphic mapping between Ed448 and Curve448 of
Appendix M.2. 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 O.3. Example with Wei448
Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei448: Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei448:
X 29070637261778856087396075817199998758219070555984737667402173284 X 29070637261778856087396075817199998758219070555984737667402173284
55389871077654193754799253725773241315783295429899652880118118204 55389871077654193754799253725773241315783295429899652880118118204
91344 91344
(=0x6663c64e 5b9a1f6d cbee3f5f 839b7dd8 6f53cc3e 0a01dab3 (=0x6663c64e 5b9a1f6d cbee3f5f 839b7dd8 6f53cc3e 0a01dab3
e4a8314e 8d54be2a 4d63380b 692381bb ed7339fd dca7b0cd a80166fe e4a8314e 8d54be2a 4d63380b 692381bb ed7339fd dca7b0cd a80166fe
skipping to change at page 113, line 8 skipping to change at page 120, line 44
507910466738735762660894972854331591097934354210992993787 507910466738735762660894972854331591097934354210992993787
402433561014235472657 402433561014235472657
(=0x7e0ffcaf 7add27bc bb723629 95fdedd0 8769f676 78d953bc (=0x7e0ffcaf 7add27bc bb723629 95fdedd0 8769f676 78d953bc
0d38f4f6 d63a59dc 00f2d55a a4db7dab 16364503 591edcb1 0d38f4f6 d63a59dc 00f2d55a a4db7dab 16364503 591edcb1
e095a577 43dea311), e095a577 43dea311),
where this representation is defined in Appendix K.5 and uses the where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.1 with the default square root function. 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/msb-order 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 Y-coordinate 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: Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei448.-3:
X 54121793865726175505902038600562190720650456678500106168173285986 X 54121793865726175505902038600562190720650456678500106168173285986
99999531708218763586616425010404811083912084906688745035466757984 99999531708218763586616425010404811083912084906688745035466757984
48968 48968
(=0xbe9f5a23 51709e13 d5ad50c2 a27be8ee 1b051970 2580d5c3 (=0xbe9f5a23 51709e13 d5ad50c2 a27be8ee 1b051970 2580d5c3
c2de7f75 3010635e d89ef547 8b67dc54 16d63c5b 1cc1116f dd453515 c2de7f75 3010635e d89ef547 8b67dc54 16d63c5b 1cc1116f dd453515
71b39b48). 71b39b48).
Y 14962282101304548030627835311887275833718070818965306362006934455 Y 14962282101304548030627835311887275833718070818965306362006934455
59168773381983445709256615887526455657034051121085622763637035580 59168773381983445709256615887526455657034051121085622763637035580
12661 12661
(=0x34b2dcc4 92d6a940 e6249c14 122d0ba4 5dc040e9 3f060d8f (=0x34b2dcc4 92d6a940 e6249c14 122d0ba4 5dc040e9 3f060d8f
a65fa300 eb3cc969 25188b59 2d31039c f7a8e14a 48320a32 efe9b42b a65fa300 eb3cc969 25188b59 2d31039c f7a8e14a 48320a32 efe9b42b
skipping to change at page 115, line 8 skipping to change at page 125, line 44
363622725164496136165251928391223173879522521195772276587 363622725164496136165251928391223173879522521195772276587
373445978123589677750 373445978123589677750
(=0x7778c1f9 9d900633 d161d7ea a963ddad e9101d3f f4f04710 (=0x7778c1f9 9d900633 d161d7ea a963ddad e9101d3f f4f04710
623d2a51 6ca10133 3db9ccc3 86df9271 fbb72740 77f79dd1 623d2a51 6ca10133 3db9ccc3 86df9271 fbb72740 77f79dd1
9aed0bfb e3bc72b6), 9aed0bfb e3bc72b6),
where this representation is defined in Appendix K.5 and uses the where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.1 with the default square root function. 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: Pe1=(x, y), k*Pe1=(x1, y1), and (k+1)*Pe1=(x2, y2) with Edwards448:
x 70320395893028961673046639985409870226249442701760956079298956688 x 70320395893028961673046639985409870226249442701760956079298956688
26896600999421897751877804946848997852325361659665744287620719558 26896600999421897751877804946848997852325361659665744287620719558
67733 67733
(=0xf7acf3ca b79b29c2 aa44863d 9edaeca4 8c90ad84 e460df42 (=0xf7acf3ca b79b29c2 aa44863d 9edaeca4 8c90ad84 e460df42
7dd9ab59 1bd8a844 07cb3419 59309b33 1e22bfa1 a2d37e10 e2e42a1f 7dd9ab59 1bd8a844 07cb3419 59309b33 1e22bfa1 a2d37e10 e2e42a1f
170f0855). 170f0855).
skipping to change at page 116, line 40 skipping to change at page 128, line 4
this case, are both one, since x and x1 are odd). See Appendix H.3 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. and Appendix I for further detail on (squeezed) point compression.
The scalar representation and (squeezed) point representation The scalar representation and (squeezed) point representation
illustrated above are fully consistent with the representations illustrated above are fully consistent with the representations
specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032] specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032]
requires unique representations of all elements of GF(p). requires unique representations of all elements of GF(p).
A randomized representation (t1, t2) of the point k*Pe1 in tight LSB/ A randomized representation (t1, t2) of the point k*Pe1 in tight LSB/
lsb order is given by lsb order is given by
t1 125390048858887400104074787879402833851854739339836093733 t1 125390048858887400104074787879402833851854739339836093733
734638776755983021034212058415891288350265701101219981698 734638776755983021034212058415891288350265701101219981698
849086128138510420407 849086128138510420407
(=0xed921f3d 6ea4e452 dd06e783 782cbeb3 c5847a79 d9e6b993 (=0xed921f3d 6ea4e452 dd06e783 782cbeb3 c5847a79 d9e6b993
bd387cf5 feeddafe af8c038d f2732362 92724d37 273eedfc bd387cf5 feeddafe af8c038d f2732362 92724d37 273eedfc
f2ab2499 98a79434) f2ab2499 98a79434)
t2 365268494484253132875102676783560666625109899133767696106 t2 493324858478481242405018423865550638507715454654135514168
602723958322248430160651314075127005631031993354968950936 842560149827360763382889199963980056979895918545280883247
71875730862008188281 787003997982869314731
(=0x9ebc28c0 86176a1a c7f0cf71 ca5f2a8f 908bb27b e85c0bbd
1641c052 e542f7d3 88e18886 5afdca32 8df45408 8b6da28c (=0xd53a5125 193b6ab9 8db48161 20fb4865 02cf0546 3b48d8a6
0bc09d83 309ebb30), 514af28f 43c026cb 0f2ff3d5 e558bb03 4b833cd1 1ca710cc
9bf0c2a3 351083b5),
where this representation is defined in Appendix K.5 and uses the where this representation is defined in Appendix K.5 and uses the
mapping of Appendix K.3.3 with the default square root function and mapping of Appendix K.3.3 with the default square root function and
underlying 4-isogenous mapping between Edwards448 and Curve448 of underlying 4-isogenous mapping between Edwards448 and Curve448 of
Appendix N.2. Appendix N.2.
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 4-isogenous mapping between Edwards448 and
Curve448 of Appendix N.2.
Appendix P. Random Integers in Z_n Appendix P. Random Integers in Z_n
Any probability distribution on the interval [0,N-1] can be converted Any probability distribution on the interval [0,N-1] can be converted
to a probability distribution on [0,n-1], via a suitable function to a probability distribution on [0,n-1], via a suitable function
that maps inputs from the source distribution [0,N-1] to values in that maps inputs from the source distribution [0,N-1] to values in
the interval [0,n-1]. We consider three such functions, each with the interval [0,n-1]. We consider three such functions, each with
the property that if the source distribution on [0,N-1] is the property that if the source distribution on [0,N-1] is
statistically close to the uniform distribution, then so is the statistically close to the uniform distribution, then so is the
output distribution on [0,n-1]. In practical applications, one can output distribution on [0,n-1]. In practical applications, one can
use these functions to convert the output of a cryptographically use these functions to convert the output of a cryptographically
skipping to change at page 119, line 16 skipping to change at page 130, line 50
This function (defined for N at least n) is the identity map on the This function (defined for N at least n) is the identity map on the
interval [0,n-1] and fails for each integer y outside this interval. interval [0,n-1] and fails for each integer y outside this interval.
One can show that the statistical distance of the distribution on Z_n 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 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 the source distribution on Z_N (if the latter is relatively
negligible compared to n/N). Details are out of scope. 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- 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 length m, this conversion function fails with probability 1- n/N
1/2 and, if it succeeds, does not inflate the statistical distance by (which is at most 1/2) and, if it succeeds, does not inflate the
more than (roughly) a factor two. statistical distance by more than (roughly) a factor two.
Author's Address Author's Address
Rene Struik Rene Struik
Struik Security Consultancy Struik Security Consultancy
Email: rstruik.ext@gmail.com Email: rstruik.ext@gmail.com
 End of changes. 83 change blocks. 
300 lines changed or deleted 789 lines changed or added

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