draft-ietf-lwig-curve-representations-17.txt   draft-ietf-lwig-curve-representations-18.txt 
lwig R. Struik lwig R. Struik
Internet-Draft Struik Security Consultancy Internet-Draft Struik Security Consultancy
Intended status: Standards Track December 11, 2020 Intended status: Standards Track December 15, 2020
Expires: June 14, 2021 Expires: June 18, 2021
Alternative Elliptic Curve Representations Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-17 draft-ietf-lwig-curve-representations-18
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 14, 2021. This Internet-Draft will expire on June 18, 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 27 skipping to change at page 2, line 27
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 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, Specification of ECDH25519 . . 7 4.1. Implementation of X25519, Specification of ECDH25519 . . 7
4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 9 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 8
4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 9 4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 8
4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 10 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 9
5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 11 5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 10
5.2. Representation Conventions . . . . . . . . . . . . . . . 11 5.2. Representation Conventions . . . . . . . . . . . . . . . 10
5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 11 5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 11
6. Implementation Considerations . . . . . . . . . . . . . . . . 12 6. Implementation Considerations . . . . . . . . . . . . . . . . 11
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 13 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 13
8. Security Considerations . . . . . . . . . . . . . . . . . . . 14 8. Security Considerations . . . . . . . . . . . . . . . . . . . 13
9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 15 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 14
10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 16 10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 15
10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 16 10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 15
10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 16 10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 15
10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 17 10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 16
10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 18 10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 17
10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 19 10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 18
10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 20 10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 19
10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 21 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 20
10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 22 10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 21
10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 22 10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 21
11. Using Wei25519 and Wei448 with PKIX and CMS . . . . . . . . . 22 11. Using Wei25519 and Wei448 with PKIX and CMS . . . . . . . . . 21
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 . . . . . . . 23 11.2. Encoding of ECDSA Instantiations with PKIX . . . . . . . 22
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 . . . . . . . . . . . . . . . . . . . . . . . . . . 22
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 . . . . . . . . . . . . . . . . . . . . . 24 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23
12.1. OIDs for Use with PKIX and CMS . . . . . . . . . . . . . 24 12.1. OIDs for Use with PKIX and CMS . . . . . . . . . . . . . 23
12.2. COSE/JOSE IANA Considerations for Wei25519 . . . . . . . 24 12.2. COSE/JOSE IANA Considerations for Wei25519 . . . . . . . 23
12.2.1. COSE Elliptic Curves Registration . . . . . . . . . 24 12.2.1. COSE Elliptic Curves Registration . . . . . . . . . 23
12.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 25 12.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 24
12.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 25 12.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 24
12.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 26 12.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 25
12.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 26 12.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 25
12.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 26 12.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 25
12.3. COSE/JOSE IANA Considerations for Wei448 . . . . . . . . 27 12.3. COSE/JOSE IANA Considerations for Wei448 . . . . . . . . 26
12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 27 12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 26
12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 27 12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 26
12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 28 12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 27
12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 28 12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 27
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) . . . . . . . . . 28
13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 29 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 28
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 30 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 29
14.1. Normative References . . . . . . . . . . . . . . . . . . 30 14.1. Normative References . . . . . . . . . . . . . . . . . . 29
14.2. Informative References . . . . . . . . . . . . . . . . . 33 14.2. Informative References . . . . . . . . . . . . . . . . . 32
Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 35 Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 34
A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 35 A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 34
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 35 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 34
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 35 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 34
Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 36 Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 35
B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 36 B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 35
B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 38 B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 37
Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 39 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 38
C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 39 C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 38
C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 40 C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 39
C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 41 C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 40
Appendix D. Relationships Between Curve Models . . . . . . . . . 42 Appendix D. Relationships Between Curve Models . . . . . . . . . 41
D.1. Mapping between Twisted Edwards Curves and Montgomery D.1. Mapping between Twisted Edwards Curves and Montgomery
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 42 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 41
D.2. Mapping between Montgomery Curves and Weierstrass Curves 43 D.2. Mapping between Montgomery Curves and Weierstrass Curves 42
D.3. Mapping between Twisted Edwards Curves and Weierstrass D.3. Mapping between Twisted Edwards Curves and Weierstrass
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 44 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 43
Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 44 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 43
E.1. Curve Definition and Alternative Representations . . . . 44 E.1. Curve Definition and Alternative Representations . . . . 43
E.2. Switching between Alternative Representations . . . . . . 45 E.2. Switching between Alternative Representations . . . . . . 44
E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 46 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 45
Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 48 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 47
F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 48 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 47
F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 49 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 48
F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 50 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 49
F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 51 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 50
Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 52 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 51
G.1. Further Alternative Representations . . . . . . . . . . . 52 G.1. Further Alternative Representations . . . . . . . . . . . 51
G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 52 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 51
G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 53 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 52
G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 55 G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 54
G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 55 G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 54
G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 61 G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 60
Appendix H. Point Compression . . . . . . . . . . . . . . . . . 67 Appendix H. Point Compression . . . . . . . . . . . . . . . . . 66
H.1. Point Compression for Weierstrass Curves . . . . . . . . 68 H.1. Point Compression for Weierstrass Curves . . . . . . . . 67
H.2. Point Compression for Montgomery Curves . . . . . . . . . 68 H.2. Point Compression for Montgomery Curves . . . . . . . . . 67
H.3. Point Compression for Twisted Edwards Curves . . . . . . 69 H.3. Point Compression for Twisted Edwards Curves . . . . . . 68
Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 70 Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 69
I.1. Strings and String Operations . . . . . . . . . . . . . . 70 I.1. Strings and String Operations . . . . . . . . . . . . . . 69
I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 71 I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 70
I.3. Conversion between Octet Strings and Integers (OS2I, I.3. Conversion between Octet Strings and Integers (OS2I,
I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 71 I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 70
I.4. Conversion between Octet Strings and Bit Strings (OS2BS, I.4. Conversion between Octet Strings and Bit Strings (OS2BS,
BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 72 BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 71
I.5. Conversion between Field Elements and Octet Strings I.5. Conversion between Field Elements and Octet Strings
(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 72 (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 71
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) . . . . . . . . . . . . . . . . . . . . 73 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 72
I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 73 I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 72
I.8. Conversion Between Curve Points and Octet Strings . . . . 74 I.8. Conversion Between Curve Points and Octet Strings . . . . 73
Appendix J. Representation Examples Curve25519 Family Members . 76 Appendix J. Representation Examples Curve25519 Family Members . 75
J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 77 J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 76
J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 79 J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 78
J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 82 J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 81
J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 84 J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 83
J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 86 J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 85
Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 88 Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 87
K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 88 K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 87
K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 89 K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 88
K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 89 K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 88
K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 89 K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 88
K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 90 K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 89
K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 90 K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 89
K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 91 K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 90
K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 92 K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 91
K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 92 K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 91
K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 93 K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 92
K.4.2. Mapping to High-Order Points of Montgomery Curve . . 94 K.4.2. Mapping to High-Order Points of Montgomery Curve . . 93
K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 95 K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 94
K.5. Randomized Representation of Curve Points . . . . . . . . 96 K.5. Randomized Representation of Curve Points . . . . . . . . 95
K.6. Completing the Mappings to Curve Points . . . . . . . . . 97 K.6. Completing the Mappings to Curve Points . . . . . . . . . 96
Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 100 Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 99
L.1. Curve Definition and Alternative Representation . . . . . 101 L.1. Curve Definition and Alternative Representation . . . . . 100
L.2. Switching Between Representations . . . . . . . . . . . . 101 L.2. Switching Between Representations . . . . . . . . . . . . 100
L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 101 L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 100
L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 103 L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 102
L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 103 L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 102
L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 104 L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 103
Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 104 Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 103
M.1. Curve Definition and Alternative Representations . . . . 104 M.1. Curve Definition and Alternative Representations . . . . 103
M.2. Switching between Alternative Representations . . . . . . 105 M.2. Switching between Alternative Representations . . . . . . 104
M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 106 M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 105
Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 109 Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 108
N.1. Further Alternative Representations . . . . . . . . . . . 109 N.1. Further Alternative Representations . . . . . . . . . . . 108
N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 109 N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 108
N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 112 N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 111
N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 114 N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 113
N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 114 N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 113
N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 115 N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 114
Appendix O. Representation Examples Curve448 Family Members . . 115 Appendix O. Representation Examples Curve448 Family Members . . 114
O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 116 O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 115
O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 119 O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 118
O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 122 O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 121
O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 125 O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 124
O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 128 O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 127
O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 130 O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 129
Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 133 Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 132
P.1. Conversion to Integers in Z_n via Modular Reduction . . . 134 P.1. Conversion to Integers in Z_n via Modular Reduction . . . 133
P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 135 P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 134
P.3. Conversion to Integers in Z_n via the Discard Method . . 136 P.3. Conversion to Integers in Z_n via the Discard Method . . 135
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 136 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 135
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 24 skipping to change at page 8, line 24
A NIST-compliant version of the co-factor Diffie-Hellman key A NIST-compliant version of the co-factor Diffie-Hellman key
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: At this point, it is unclear whether this implies that a FIPS-
agreement scheme (denoted by X25519+) results by incorporating Steps accredited module implementing co-factor Diffie-Hellman for, e.g.,
(1), (2), and (3) above, i.e., where one keeps inputs (key P-256 would also extend this accreditation to X25519.
contributions) and pre-output (shared key K) in the Montgomery curve
format, as points of Curve25519, where one represents each affine
point by only its x-coordinate, represented as a fixed-size octet
string in tight LSB/msb-order using the FE2OS mapping and its
reverse, the strict OS2FE mapping, of Appendix I.5, and where the
actual output (shared secret Z) is the representation of the shared
key K as defined above (if this is an affine point of the curve), and
where the output is an error indicator otherwise (i.e., if K is the
point at infinity O of the curve). The scheme X25519, as specified
in [RFC7748], is a more lenient version of this X25519+ scheme,
whereby one does not mandate rejection of shared keys in the small
subgroup (which are instead represented as if these were the point
(0,0) of order two), one does not check whether a received key
contribution is a point of Curve25519, rather than a point of a
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
implementing the co-factor Diffie-Hellman scheme with, e.g., P-256
would also extend this accreditation to the Montgomery versions
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.
One can implement the computation of the ephemeral key pair for One can implement the computation of the ephemeral key pair for
Ed25519 using an existing Montgomery curve implementation by (1) Ed25519 using an existing Montgomery curve implementation by (1)
generating a public-private key pair (k, R':=k*G') for Curve25519; generating a public-private key pair (k, R':=k*G') for Curve25519;
(2) representing this public-private key as the pair (k, R:=k*G) for (2) representing this public-private key as the pair (k, R:=k*G) for
Ed25519. As before, the representation change can be implemented via Ed25519. As before, the representation change can be implemented via
skipping to change at page 10, line 40 skipping to change at page 10, line 13
Section 4.1, but now using the short-Weierstrass curve Wei448, rather Section 4.1, but now using the short-Weierstrass curve Wei448, rather
than Wei25519 (with the same representation and bit/byte-ordering than Wei25519 (with the same representation and bit/byte-ordering
conventions). Similarly, one can easily specify ECDSA with Wei448 conventions). Similarly, one can easily specify ECDSA with Wei448
and a suitable hash function, by simply reusing the example of and a suitable hash function, by simply reusing the example of
Section 4.3, but now using the short-Weierstrass curve Wei448, rather Section 4.3, but now using the short-Weierstrass curve Wei448, rather
than Wei25519, and picking as hash function SHAKE256 [FIPS-202] with than Wei25519, and picking as hash function SHAKE256 [FIPS-202] with
output size of d=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
agreement scheme (denoted by X448+) results by reusing the
description of X25519+ in Section 4.1, but now using the Montgomery
curve Curve448, rather than Curve25519 (with the same checks and
representation and bit/byte-ordering conventions). The scheme X448,
as specified in [RFC7748], is a more lenient version of this X448+
scheme, whereby one does not mandate rejection of shared keys in the
small subgroup (which are instead represented as if these were the
point (0,0) of order two), nor checks whether a received key
contribution is a point of Curve448, rather than a point of a
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
The transformations between alternative curve representations can be The transformations between alternative curve representations can be
skipping to change at page 21, line 7 skipping to change at page 20, line 15
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 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; if the it MUST include "verify" when verifying an ECDSA signature; if the
JWK _use_ field is present, its value MUST be "sig". JWK _use_ field is present, its value MUST be "sig".
10.3. Using ECDH25519 and ECDH448 with COSE and JOSE 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE
NIST SP 800-56a [SP-800-56a] specifies the co-factor elliptic-curve Section 6.1.2.2 of NIST SP 800-56a [SP-800-56a] specifies the co-
Diffie-Hellman key agreement scheme (co-factor ECDH) and can be factor elliptic-curve Diffie-Hellman key agreement scheme (co-factor
instantiated with a suitable elliptic curve in short-Weierstrass form ECDH) and can be instantiated with a suitable elliptic curve in
(that satisfies particular cryptographic criteria). While this short-Weierstrass form (that satisfies particular cryptographic
completely specifies the internal workings of the key agreement criteria). While this completely specifies the internal workings of
scheme in question, this does not uniquely specify the input/output the key agreement scheme in question, this does not uniquely specify
formats: the input/output formats:
a. The co-factor ECDH scheme is a two-party key agreement scheme a. The co-factor Diffie-Hellman primitive (Section 5.7.1.2 of
that takes as inputs a private key d in the interval [1,n-1] from [SP-800-56a]) takes as inputs a private key d in the interval
one of the parties and a point Q' obtained from the other party [1,n-1] from one of the parties and a point Q' obtained from the
and produces a shared key K:=h*(d*Q'), where h and n are, other party and produces the shared key K:=h*(d*Q'), where h and
respectively, the co-factor and the order of the base point of n are, respectively, the co-factor and the order of the base
the curve in question and where Q' is a point of this curve. If point of the curve in question and where Q' is a point of this
this shared key K is the point at infinity O of the curve, the curve. If this shared key K is the point at infinity O of the
output is an error indicator; curve, the output is an error indicator;
b. If the shared key K is an affine point of the curve, the output b. If the shared key K is an affine point of the curve, the output
is the (raw) shared secret Z, which is the fixed-size octet is the (raw) shared secret Z, which is the fixed-size octet
representation of the x-coordinate of K, using the FE2OS mapping representation of the x-coordinate of K, using the FE2OS mapping
of Appendix I.5, represented in tight-MSB/msb-order (see of Appendix I.5, represented in tight-MSB/msb-order (see
Appendix I.7). Appendix I.7).
(NOTE: A subsequent key derivation function (kdf) takes as inputs (NOTE: A subsequent key derivation function (kdf) takes as inputs
the shared secret Z and side information OtherInfo and produces the shared secret Z and side information OtherInfo and produces
as output an octet string of DerivedKeyingMaterial, where details as output an octet string of DerivedKeyingMaterial, where details
 End of changes. 20 change blocks. 
202 lines changed or deleted 158 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/