draft-ietf-lwig-curve-representations-16.txt   draft-ietf-lwig-curve-representations-17.txt 
lwig R. Struik lwig R. Struik
Internet-Draft Struik Security Consultancy Internet-Draft Struik Security Consultancy
Intended status: Standards Track December 9, 2020 Intended status: Standards Track December 11, 2020
Expires: June 12, 2021 Expires: June 14, 2021
Alternative Elliptic Curve Representations Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-16 draft-ietf-lwig-curve-representations-17
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 June 12, 2021. This Internet-Draft will expire on June 14, 2021.
Copyright Notice Copyright Notice
Copyright (c) 2020 IETF Trust and the persons identified as the Copyright (c) 2020 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 38 skipping to change at page 2, line 38
4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 9 4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 9
4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 10 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 10
5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 11 5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 11
5.2. Representation Conventions . . . . . . . . . . . . . . . 11 5.2. Representation Conventions . . . . . . . . . . . . . . . 11
5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 11 5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 11
6. Implementation Considerations . . . . . . . . . . . . . . . . 12 6. Implementation Considerations . . . . . . . . . . . . . . . . 12
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 13 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 13
8. Security Considerations . . . . . . . . . . . . . . . . . . . 14 8. Security Considerations . . . . . . . . . . . . . . . . . . . 14
9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 15 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 15
10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 15 10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 16
10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 16 10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 16
10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 16 10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 16
10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 17 10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 17
10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 18 10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 18
10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 18 10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 19
10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 19 10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 20
10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 20 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 21
10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 21 10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 22
10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 22 10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 22
11. Using Wei25519 and Wei448 with PKIX and CMS . . . . . . . . . 22 11. Using Wei25519 and Wei448 with PKIX and CMS . . . . . . . . . 22
11.1. Encoding of Short-Weierstrass Curves with PKIX . . . . . 22 11.1. Encoding of Short-Weierstrass Curves with PKIX . . . . . 22
11.2. Encoding of ECDSA Instantiations with PKIX . . . . . . . 22 11.2. Encoding of ECDSA Instantiations with PKIX . . . . . . . 23
11.3. Encoding of co-factor ECDH and Other Algorithms with 11.3. Encoding of co-factor ECDH and Other Algorithms with
PKIX . . . . . . . . . . . . . . . . . . . . . . . . . . 23 PKIX . . . . . . . . . . . . . . . . . . . . . . . . . . 23
11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS . . 23 11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS . . 23
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24
12.1. OIDs for Use with PKIX and CMS . . . . . . . . . . . . . 24 12.1. OIDs for Use with PKIX and CMS . . . . . . . . . . . . . 24
12.2. COSE/JOSE IANA Considerations for Wei25519 . . . . . . . 24 12.2. COSE/JOSE IANA Considerations for Wei25519 . . . . . . . 24
12.2.1. COSE Elliptic Curves Registration . . . . . . . . . 24 12.2.1. COSE Elliptic Curves Registration . . . . . . . . . 24
12.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 24 12.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 25
12.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 25 12.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 25
12.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 25 12.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 26
12.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 26 12.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 26
12.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 26 12.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 26
12.3. COSE/JOSE IANA Considerations for Wei448 . . . . . . . . 26 12.3. COSE/JOSE IANA Considerations for Wei448 . . . . . . . . 27
12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 26 12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 27
12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 27 12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 27
12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 27 12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 28
12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 28 12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 28
12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 28 12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 28
12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 29 12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 29
13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 29 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 29
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 29 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 30
14.1. Normative References . . . . . . . . . . . . . . . . . . 29 14.1. Normative References . . . . . . . . . . . . . . . . . . 30
14.2. Informative References . . . . . . . . . . . . . . . . . 32 14.2. Informative References . . . . . . . . . . . . . . . . . 33
Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 34 Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 35
A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 34 A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 35
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 35 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 35
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 35 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 35
Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 35 Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 36
B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 35 B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 36
B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 37 B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 38
Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 38 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 39
C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 38 C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 39
C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 39 C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 40
C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 40 C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 41
Appendix D. Relationships Between Curve Models . . . . . . . . . 41 Appendix D. Relationships Between Curve Models . . . . . . . . . 42
D.1. Mapping between Twisted Edwards Curves and Montgomery D.1. Mapping between Twisted Edwards Curves and Montgomery
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 41 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 42
D.2. Mapping between Montgomery Curves and Weierstrass Curves 42 D.2. Mapping between Montgomery Curves and Weierstrass Curves 43
D.3. Mapping between Twisted Edwards Curves and Weierstrass D.3. Mapping between Twisted Edwards Curves and Weierstrass
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 43 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 44
Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 43 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 44
E.1. Curve Definition and Alternative Representations . . . . 43 E.1. Curve Definition and Alternative Representations . . . . 44
E.2. Switching between Alternative Representations . . . . . . 44 E.2. Switching between Alternative Representations . . . . . . 45
E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 45 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 46
Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 47 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 48
F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 47 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 48
F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 48 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 49
F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 49 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 50
F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 50 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 51
Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 51 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 52
G.1. Further Alternative Representations . . . . . . . . . . . 51 G.1. Further Alternative Representations . . . . . . . . . . . 52
G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 51 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 52
G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 52 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 53
G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 54 G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 55
G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 54 G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 55
G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 60 G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 61
Appendix H. Point Compression . . . . . . . . . . . . . . . . . 66 Appendix H. Point Compression . . . . . . . . . . . . . . . . . 67
H.1. Point Compression for Weierstrass Curves . . . . . . . . 67 H.1. Point Compression for Weierstrass Curves . . . . . . . . 68
H.2. Point Compression for Montgomery Curves . . . . . . . . . 68 H.2. Point Compression for Montgomery Curves . . . . . . . . . 68
H.3. Point Compression for Twisted Edwards Curves . . . . . . 68 H.3. Point Compression for Twisted Edwards Curves . . . . . . 69
Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 69 Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 70
I.1. Strings and String Operations . . . . . . . . . . . . . . 69 I.1. Strings and String Operations . . . . . . . . . . . . . . 70
I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 70 I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 71
I.3. Conversion between Octet Strings and Integers (OS2I, I.3. Conversion between Octet Strings and Integers (OS2I,
I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 70 I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 71
I.4. Conversion between Octet Strings and Bit Strings (OS2BS, I.4. Conversion between Octet Strings and Bit Strings (OS2BS,
BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 71 BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 72
I.5. Conversion between Field Elements and Octet Strings I.5. Conversion between Field Elements and Octet Strings
(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 71 (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 72
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) . . . . . . . . . . . . . . . . . . . . 72 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 73
I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 72 I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 73
I.8. Conversion Between Curve Points and Octet Strings . . . . 73 I.8. Conversion Between Curve Points and Octet Strings . . . . 74
Appendix J. Representation Examples Curve25519 Family Members . 76 Appendix J. Representation Examples Curve25519 Family Members . 76
J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 76 J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 77
J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 79 J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 79
J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 81 J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 82
J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 83 J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 84
J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 85 J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 86
Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 87 Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 88
K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 88 K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 88
K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 88 K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 89
K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 88 K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 89
K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 88 K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 89
K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 89 K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 90
K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 89 K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 90
K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 90 K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 91
K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 91 K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 92
K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 92 K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 92
K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 92 K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 93
K.4.2. Mapping to High-Order Points of Montgomery Curve . . 93 K.4.2. Mapping to High-Order Points of Montgomery Curve . . 94
K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 94 K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 95
K.5. Randomized Representation of Curve Points . . . . . . . . 95 K.5. Randomized Representation of Curve Points . . . . . . . . 96
K.6. Completing the Mappings to Curve Points . . . . . . . . . 96 K.6. Completing the Mappings to Curve Points . . . . . . . . . 97
Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 99 Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 100
L.1. Curve Definition and Alternative Representation . . . . . 100 L.1. Curve Definition and Alternative Representation . . . . . 101
L.2. Switching Between Representations . . . . . . . . . . . . 100 L.2. Switching Between Representations . . . . . . . . . . . . 101
L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 100 L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 101
L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 102 L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 103
L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 102 L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 103
L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 103 L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 104
Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 103 Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 104
M.1. Curve Definition and Alternative Representations . . . . 103 M.1. Curve Definition and Alternative Representations . . . . 104
M.2. Switching between Alternative Representations . . . . . . 104 M.2. Switching between Alternative Representations . . . . . . 105
M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 105 M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 106
Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 108 Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 109
N.1. Further Alternative Representations . . . . . . . . . . . 108 N.1. Further Alternative Representations . . . . . . . . . . . 109
N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 108 N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 109
N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 111 N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 112
N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 113 N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 114
N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 113 N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 114
N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 114 N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 115
Appendix O. Representation Examples Curve448 Family Members . . 114 Appendix O. Representation Examples Curve448 Family Members . . 115
O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 115 O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 116
O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 118 O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 119
O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 121 O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 122
O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 124 O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 125
O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 127 O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 128
O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 129 O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 130
Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 132 Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 133
P.1. Conversion to Integers in Z_n via Modular Reduction . . . 133 P.1. Conversion to Integers in Z_n via Modular Reduction . . . 134
P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 134 P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 135
P.3. Conversion to Integers in Z_n via the Discard Method . . 135 P.3. Conversion to Integers in Z_n via the Discard Method . . 136
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 135 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 136
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-Weierstrass attacks than curves represented in the traditional short-Weierstrass
curve model. These so-called CFRG curves [RFC7748] use the curve model. These so-called CFRG curves [RFC7748] use the
Montgomery curve model and the model of twisted Edwards curves. Montgomery curve model and the model of twisted Edwards curves.
skipping to change at page 8, line 25 skipping to change at page 8, line 25
agreement scheme (denoted by ECDH25519) results if one keeps inputs agreement scheme (denoted by ECDH25519) results if one keeps inputs
(key contributions) and pre-output (shared key K) in the short- (key contributions) and pre-output (shared key K) in the short-
Weierstrass format (and, hence, does not perform Steps (1) and (3) Weierstrass format (and, hence, does not perform Steps (1) and (3)
above), where the actual output (shared secret Z) is the x-coordinate above), where the actual output (shared secret Z) is the x-coordinate
of K (if this is an affine point of the curve), represented as a of K (if this is an affine point of the curve), represented as a
fixed-size octet string in tight MSB/msb-order using the FE2OS fixed-size octet string in tight MSB/msb-order using the FE2OS
mapping of Appendix I.5, and where the output is an error indicator mapping of Appendix I.5, and where the output is an error indicator
otherwise (i.e., if K is the point at infinity O of the curve). otherwise (i.e., if K is the point at infinity O of the curve).
NOTE 1: A Montgomery version of the co-factor Diffie-Hellman key NOTE 1: A Montgomery version of the co-factor Diffie-Hellman key
agreement scheme (denoted by X25519+) results by incorporating Step agreement scheme (denoted by X25519+) results by incorporating Steps
(1), (2), and (3) above, i.e., where one keeps inputs (key (1), (2), and (3) above, i.e., where one keeps inputs (key
contributions) and pre-output (shared key K) in the Montgomery curve contributions) and pre-output (shared key K) in the Montgomery curve
format, as points of Curve25519, and where one represents all affine format, as points of Curve25519, where one represents each affine
points by their x-coordinate, represented as a fixed-size octet point by only its x-coordinate, represented as a fixed-size octet
string in tight LSB/msb-order using the FE2OS mapping of string in tight LSB/msb-order using the FE2OS mapping and its
Appendix I.5, where the actual output (shared secret Z) is the reverse, the strict OS2FE mapping, of Appendix I.5, and where the
representation of the shared key K as defined above (if this is an actual output (shared secret Z) is the representation of the shared
affine point of the curve), and where the output is an error key K as defined above (if this is an affine point of the curve), and
indicator otherwise (i.e., if K is the point at infinity O of the where the output is an error indicator otherwise (i.e., if K is the
curve). The scheme X25519, as specified in [RFC7748], is compatible point at infinity O of the curve). The scheme X25519, as specified
with a more lenient version of this X25519+ scheme, whereby it does in [RFC7748], is a more lenient version of this X25519+ scheme,
not mandate rejection of shared keys in the small subgroup (which are whereby one does not mandate rejection of shared keys in the small
instead represented as if these were the point (0,0) of order two) subgroup (which are instead represented as if these were the point
and where it also accepts a shared key if all points are points of (0,0) of order two), one does not check whether a received key
the quadratic twist of Curve25519, rather than of Curve25519 itself contribution is a point of Curve25519, rather than a point of a
(for definitions of these terms, see Appendix B.1). quadratic twist of this curve (for definitions of these terms, see
Appendix B.1), and where one uses the non-strict (rather than strict)
OS2FE mapping (which, in this case, is always applied after setting
the leftmost bit of the rightmost octet to zero). Moreover, with
X25519, private keys are derived from integers generated in the
interval [2^251,2^252-1], rather than generated in the interval
[1,n-1], where n is the order of the base point of the curve in
question.
NOTE 2: At this point, it is unclear whether a FIPS-accredited module NOTE 2: At this point, it is unclear whether a FIPS-accredited module
implementing the co-factor Diffie-Hellman scheme with, e.g., P-256 implementing the co-factor Diffie-Hellman scheme with, e.g., P-256
would also extend this accreditation to the Montgomery versions would also extend this accreditation to the Montgomery versions
X25519+ or X25519. X25519+ or X25519.
4.2. Implementation of Ed25519 4.2. Implementation of Ed25519
RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature
scheme, with instantiation by the twisted Edwards curve Edwards25519. scheme, with instantiation by the twisted Edwards curve Edwards25519.
skipping to change at page 10, line 45 skipping to change at page 10, line 45
than Wei25519, and picking as hash function SHAKE256 [FIPS-202] with than Wei25519, and picking as hash function SHAKE256 [FIPS-202] with
output size of d=512 bits. We denote by ECDSA448 the resulting output size of d=512 bits. We denote by ECDSA448 the resulting
signature scheme (with the same representation and bit/byte-ordering signature scheme (with the same representation and bit/byte-ordering
conventions). conventions).
NOTE: A Montgomery version of the co-factor Diffie-Hellman key NOTE: A Montgomery version of the co-factor Diffie-Hellman key
agreement scheme (denoted by X448+) results by reusing the agreement scheme (denoted by X448+) results by reusing the
description of X25519+ in Section 4.1, but now using the Montgomery description of X25519+ in Section 4.1, but now using the Montgomery
curve Curve448, rather than Curve25519 (with the same checks and curve Curve448, rather than Curve25519 (with the same checks and
representation and bit/byte-ordering conventions). The scheme X448, representation and bit/byte-ordering conventions). The scheme X448,
as specified in [RFC7748], is compatible with a more lenient version as specified in [RFC7748], is a more lenient version of this X448+
of this X448+ scheme, whereby it does not mandate rejection of shared scheme, whereby one does not mandate rejection of shared keys in the
keys in the small subgroup (which are instead again represented as if small subgroup (which are instead represented as if these were the
these were the point (0,0) of order two) and where it also accepts a point (0,0) of order two), nor checks whether a received key
shared key if all points are points of the quadratic twist of contribution is a point of Curve448, rather than a point of a
Curve448, rather than of Curve448 itself. quadratic twist of this curve, and where one uses the non-strict
(rather than the strict) OS2FE mapping for converting octet strings
to field elements. Moreover, with X448, private keys are derived
from integers generated in the interval [2^445,2^446-1], rather than
generated in the interval [1,n-1], where n is the order of the base
point of the curve in question.
5. Caveats 5. Caveats
The examples above illustrate how specifying the Weierstrass curve The examples above illustrate how specifying the Weierstrass curve
Wei25519 (or any curve in short-Weierstrass format, for that matter) Wei25519 (or any curve in short-Weierstrass format, for that matter)
may facilitate reuse of existing code and may simplify standards may facilitate reuse of existing code and may simplify standards
development. However, the following caveats apply: development. However, the following caveats apply:
5.1. Wire Format 5.1. Wire Format
skipping to change at page 12, line 23 skipping to change at page 12, line 27
A=-1410290 (or, if one wants the base point to still have A=-1410290 (or, if one wants the base point to still have
u-coordinate u=9, with B=1 and A=-3960846). In either case, the u-coordinate u=9, with B=1 and A=-3960846). In either case, the
resulting curve has the same cryptographic properties as Curve25519 resulting curve has the same cryptographic properties as Curve25519
and the same performance (which relies on A being a 3-byte integer, and the same performance (which relies on A being a 3-byte integer,
as is the case with the domain parameter A=486662 of Curve25519, and as is the case with the domain parameter A=486662 of Curve25519, and
using the same special prime p=2^255-19), while at the same time using the same special prime p=2^255-19), while at the same time
being "Jacobian-friendly" by design. being "Jacobian-friendly" by design.
NOTE 2: While an implementation of Curve25519 via an isogenous NOTE 2: While an implementation of Curve25519 via an isogenous
Weierstrass curve with domain parameter a=-3 requires a relatively Weierstrass curve with domain parameter a=-3 requires a relatively
large table (of size roughly 9kB), for the quadratic twist of large table (of size roughly 9kB), for a quadratic twist of
Curve25519 (i.e., the Montgomery curve M_{A,B'} with A=486662 and Curve25519 (e.g., the Montgomery curve M_{A,B'} with A=486662 and
B'=2) this implementation approach only requires a table of size less B'=2) this implementation approach only requires a table of size less
than 0.5kB (over 20x smaller), solely due to the fact that it is than 0.5kB (over 20x smaller), solely due to the fact that it is
l-isogenous to a Weierstrass curve with a=-3 parameter with l-isogenous to a Weierstrass curve with a=-3 parameter with
relatively small parameter l=2 (compared to l=47, as is the case with relatively small parameter l=2 (compared to l=47, as is the case with
Curve25519 itself). Curve25519 itself).
6. Implementation Considerations 6. Implementation Considerations
The efficiency of elliptic curve arithmetic is primarily determined The efficiency of elliptic curve arithmetic is primarily determined
by the efficiency of its group operations (see Appendix C). Numerous by the efficiency of its group operations (see Appendix C). Numerous
skipping to change at page 15, line 11 skipping to change at page 15, line 16
Elliptic curves are generally used as objects in a broader Elliptic curves are generally used as objects in a broader
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.
between Ed25519 (as specified in [RFC8032]) and ECDSA25519 (as
specified in Section 4.3). Similarly, private keys MUST NOT be Private keys MUST NOT be reused between Ed25519 (as specified in
reused between Ed448 (as specified in [RFC8032]) and ECDSA448 (as [RFC8032]) and ECDSA25519 (as specified in Section 4.3). Similarly,
specified in Section 4.4). 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 of ECDSA448.
With ECDSA25519 and ECDSA448, the same private signature key MUST NOT
be reused between application scenarios where message encoding and
decoding rules vary, since this may jeopardize message unforgeability
properties; see also the Note in Section 10.2.1. (In fact, this
holds for any signature scheme, not just ECDSA.)
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.
Use of a public key in any protocol for which successful execution Use of a public key in any protocol for which successful execution
evidences knowledge of the corresponding private key implicitly evidences knowledge of the corresponding private key implicitly
indicates the entity holding this private key. Reuse of this public indicates the entity holding this private key. Reuse of this public
skipping to change at page 19, line 37 skipping to change at page 19, line 50
instantiation of ECDSA and the "crv" parameter MUST be set to the instantiation of ECDSA and the "crv" parameter MUST be set to the
(unique) name of the corresponding curve; if the "key_ops" field is (unique) name of the corresponding curve; if the "key_ops" field is
present, it MUST include "sign" when creating an ECDSA signature and present, it MUST include "sign" when creating an ECDSA signature and
it MUST include "verify" when verifying an ECDSA signature. it MUST include "verify" when verifying an ECDSA signature.
NOTE: Care should be taken that signers and verifiers do have a NOTE: Care should be taken that signers and verifiers do have a
common understanding of message encoding rules, since otherwise common understanding of message encoding rules, since otherwise
signature verification may fail for messages with the same semantics. signature verification may fail for messages with the same semantics.
As an example, if there is ambiguity as to whether to represent the As an example, if there is ambiguity as to whether to represent the
binary digit 0 as the integer 0 or as the CBOR false value binary digit 0 as the integer 0 or as the CBOR false value
(represented as the CBOR bit string b000_00000 or b111_101000, (represented as the CBOR bit string b000_00000 or b111_10100,
respectively), signing and signature verification may depend on respectively), signing and signature verification may depend on
different ToBeSigned strings and, thereby, may fail unexpectedly. different ToBeSigned strings and, thereby, may fail unexpectedly.
This explains the (strong) requirement for deterministic encoding This explains the (strong) requirement for deterministic encoding
rules above and, thereby, the requirement for strong typing of any rules above and, thereby, the requirement for strong typing of any
CBOR encodings used with signed messages. Further care should be CBOR encodings used with signed messages. Further care should be
taken that message decoding rules are always unambiguous, since taken that message decoding rules are always unambiguous, since
otherwise the semantics of signed messages may not be clear or the otherwise the semantics of signed messages may not be clear or the
unforgeability property of signatures may be jeopardized. unforgeability property of signatures may be jeopardized.
10.2.2. Encoding of ECDSA Instantiations with JOSE 10.2.2. Encoding of ECDSA Instantiations with JOSE
skipping to change at page 34, line 37 skipping to change at page 35, line 9
[Wei-Ladder] [Wei-Ladder]
T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve
Multiplication Resistant Against Side Channel Attacks", Multiplication Resistant Against Side Channel Attacks",
Centre for Applied Cryptographic Research, Corr 2002-03, Centre for Applied Cryptographic Research, Corr 2002-03,
2002. 2002.
Appendix A. Some (Non-Binary) Elliptic Curves Appendix A. Some (Non-Binary) Elliptic Curves
This section defines the three different curve models we consider, This section defines the three different curve models we consider,
viz. short-Weierstrass curves, Montgomery curves, and twisted Edwards viz. short-Weierstrass curves, Montgomery curves, and twisted Edwards
curves. curves. For nomenclature, see Appendix B.
A.1. Curves in Short-Weierstrass Form A.1. Curves in Short-Weierstrass Form
Let GF(q) denote the finite field with q elements, where q is an odd Let GF(q) denote the finite field with q elements, where q is an odd
prime power and where q is not divisible by three. Let W_{a,b} be prime power and where q is not divisible by three. Let W_{a,b} be
the Weierstrass curve with defining equation Y^2 = X^3 + a*X + b, the Weierstrass curve with defining equation Y^2 = X^3 + a*X + b,
where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is
nonzero. The points of W_{a,b} are the ordered pairs (X, Y) whose nonzero. The points of W_{a,b} are the ordered pairs (X, Y) whose
coordinates are elements of GF(q) and that satisfy the defining coordinates are elements of GF(q) and that satisfy the defining
equation (the so-called affine points), together with the special equation (the so-called affine points), together with the special
point O (the so-called "point at infinity"). This set forms a group point O (the so-called "point at infinity"). This set forms a group
under addition, via the so-called "chord-and-tangent" rule, where the under addition, via the so-called "chord-and-tangent" rule, where the
point at infinity serves as the identity element. See Appendix C.1 point at infinity serves as the identity element. See Appendix C.1
for details of the group operation. for details of the group operation.
A quadratic twist of W_{a,b} is a curve W_{a',b'} for which a':=
a*gamma^2 and b':=b*gamma^3, where gamma is an element of GF(q) that
is not a square in GF(q).
A.2. Montgomery Curves A.2. Montgomery Curves
Let GF(q) denote the finite field with q elements, where q is an odd Let GF(q) denote the finite field with q elements, where q is an odd
prime power. Let M_{A,B} be the Montgomery curve with defining prime power. Let M_{A,B} be the Montgomery curve with defining
equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q) equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q)
and where A is unequal to (+/-)2 and where B is nonzero. The points and where A is unequal to (+/-)2 and where B is nonzero. The points
of M_{A,B} are the ordered pairs (u, v) whose coordinates are of M_{A,B} are the ordered pairs (u, v) whose coordinates are
elements of GF(q) and that satisfy the defining equation (the so- elements of GF(q) and that satisfy the defining equation (the so-
called affine points), together with the special point O (the so- called affine points), together with the special point O (the so-
called "point at infinity"). This set forms a group under addition, called "point at infinity"). This set forms a group under addition,
via the so-called "chord-and-tangent" rule, where the point at via the so-called "chord-and-tangent" rule, where the point at
infinity serves as the identity element. See Appendix C.2 for infinity serves as the identity element. See Appendix C.2 for
details of the group operation. details of the group operation.
A quadratic twist of M_{A,B} is a curve M_{A',B'} for which A':= A
and B':=B*gamma, where gamma is an element of GF(q) that is not a
square in GF(q).
A.3. Twisted Edwards Curves A.3. Twisted Edwards Curves
Let GF(q) denote the finite field with q elements, where q is an odd Let GF(q) denote the finite field with q elements, where q is an odd
prime power. Let E_{a,d} be the twisted Edwards curve with defining prime power. Let E_{a,d} be the twisted Edwards curve with defining
equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct
nonzero elements of GF(q). The points of E_{a,d} are the ordered nonzero elements of GF(q). The points of E_{a,d} are the ordered
pairs (x, y) whose coordinates are elements of GF(q) and that satisfy pairs (x, y) whose coordinates are elements of GF(q) and that satisfy
the defining equation (the so-called affine points). It can be shown the defining equation (the so-called affine points). It can be shown
that this set forms a group under addition if a is a square in GF(q), that this set forms a group under addition if a is a square in GF(q),
whereas d is not, where the point O:=(0, 1) serves as the identity whereas d is not, where the point O:=(0, 1) serves as the identity
element. (Note that the identity element satisfies the defining element. (Note that the identity element satisfies the defining
equation.) See Appendix C.3 for details of the group operation. equation.) See Appendix C.3 for details of the group operation.
(All curves E_{a,d} in this document are assumed to satisfy the
condition on domain parameters a and d above and, thereby, the Note
in that appendix.)
An Edwards curve is a twisted Edwards curve with a=1. An Edwards curve is a twisted Edwards curve with a=1.
A quadratic twist of E_{a,d} is a curve E_{a',d'} for which a':=
a*gamma and d':=d*gamma, where gamma is an element of GF(q) that is
not a square in GF(q).
Appendix B. Elliptic Curve Nomenclature and Finite Fields Appendix B. Elliptic Curve Nomenclature and Finite Fields
This section provides brief background information on elliptic curves This section provides brief background information on elliptic curves
and finite fields that should be sufficient to understand and finite fields that should be sufficient to understand
constructions and examples in this document. constructions and examples in this document.
B.1. Elliptic Curve Nomenclature B.1. Elliptic Curve Nomenclature
The set of points of each curve defined in Appendix A forms a The set of points of each curve defined in Appendix A forms a
commutative group under addition (denoted by '+'). In Appendix C we commutative group under addition (denoted by '+'). In Appendix C we
skipping to change at page 36, line 50 skipping to change at page 37, line 37
key, and the point R the corresponding public key. The private key k key, and the point R the corresponding public key. The private key k
can be represented as an integer in the interval [0,n-1], where G has can be represented as an integer in the interval [0,n-1], where G has
order n. If this representation is nonzero, R has order n; order n. If this representation is nonzero, R has order n;
otherwise, it has order one and is the identity element O of the otherwise, it has order one and is the identity element O of the
curve. curve.
In this document, a quadratic twist of a curve E defined over a field In this document, a quadratic twist of a curve E defined over a field
GF(q) is a specific curve E' related to E defined over the same GF(q) is a specific curve E' related to E defined over the same
field, with cardinality |E'|, where |E|+|E'|=2*(q+1). If E is a field, with cardinality |E'|, where |E|+|E'|=2*(q+1). If E is a
curve in one of the curve models specified in this document, a curve in one of the curve models specified in this document, a
quadratic twist of this curve can be expressed using the same curve quadratic twist E' of this curve can be expressed using the same
model, although (naturally) with its own curve parameters. Two curve model, although (naturally) with its own curve parameters (see
curves E and E' defined over a field GF(q) are said to be isogenous Appendix A). Points that are both points of E and E' have order one
if these have the same order and are said to be isomorphic if these or two. Two curves E and E' defined over a field GF(q) are said to
have the same group structure. Note that isomorphic curves have be isogenous if these have the same order and are said to be
necessarily the same order and are, thus, a special type of isogenous isomorphic if these have the same group structure. Note that
curves. Further details are out of scope. isomorphic curves have necessarily the same order and are, thus, a
special case of isogenous curves. Further details are out of scope.
Weierstrass curves can have prime order, whereas Montgomery curves Weierstrass curves can have prime order, whereas Montgomery curves
and twisted Edwards curves always have an order that is a multiple of and twisted Edwards curves always have an order that is a multiple of
four (and, thereby, a small subgroup of cardinality four). four (and, thereby, a small subgroup of cardinality four).
An ordered pair (x, y) whose coordinates are elements of GF(q) can be An ordered pair (x, y) whose coordinates are elements of GF(q) can be
associated with any ordered triple of the form [x*z: y*z: z], where z associated with any ordered triple of the form [x*z: y*z: z], where z
is a nonzero element of GF(q), and can be uniquely recovered from is a nonzero element of GF(q), and can be uniquely recovered from
such a representation. The latter representation is commonly called such a representation. The latter representation is commonly called
a representation in projective coordinates. Sometimes, yet other a representation in projective coordinates. Sometimes, yet other
 End of changes. 37 change blocks. 
145 lines changed or deleted 180 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/