--- 1/draft-ietf-lwig-curve-representations-16.txt 2020-12-11 09:13:10.880971165 -0800
+++ 2/draft-ietf-lwig-curve-representations-17.txt 2020-12-11 09:13:11.016973009 -0800
@@ -1,18 +1,18 @@
lwig R. Struik
Internet-Draft Struik Security Consultancy
-Intended status: Standards Track December 9, 2020
-Expires: June 12, 2021
+Intended status: Standards Track December 11, 2020
+Expires: June 14, 2021
Alternative Elliptic Curve Representations
- draft-ietf-lwig-curve-representations-16
+ draft-ietf-lwig-curve-representations-17
Abstract
This document specifies how to represent Montgomery curves and
(twisted) Edwards curves as curves in short-Weierstrass form and
illustrates how this can be used to carry out elliptic curve
computations using existing implementations of, e.g., ECDSA and ECDH
using NIST prime curves. We also provide extensive background
material that may be useful for implementers of elliptic curve
cryptography.
@@ -33,21 +33,21 @@
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
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 (c) 2020 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
@@ -68,158 +68,158 @@
4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 9
4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 10
5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 11
5.2. Representation Conventions . . . . . . . . . . . . . . . 11
5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 11
6. Implementation Considerations . . . . . . . . . . . . . . . . 12
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 13
8. Security Considerations . . . . . . . . . . . . . . . . . . . 14
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.1. Encoding of Short-Weierstrass Curves with COSE . . . 16
10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 17
10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 18
- 10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 18
- 10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 19
- 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 20
- 10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 21
+ 10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 19
+ 10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 20
+ 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 21
+ 10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 22
10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 22
11. Using Wei25519 and Wei448 with PKIX and CMS . . . . . . . . . 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
PKIX . . . . . . . . . . . . . . . . . . . . . . . . . . 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.2. COSE/JOSE IANA Considerations for Wei25519 . . . . . . . 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.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.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 26
- 12.3. COSE/JOSE IANA Considerations for Wei448 . . . . . . . . 26
- 12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 26
+ 12.3. COSE/JOSE IANA Considerations for Wei448 . . . . . . . . 27
+ 12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 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.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 28
12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 29
13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 29
- 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 29
- 14.1. Normative References . . . . . . . . . . . . . . . . . . 29
- 14.2. Informative References . . . . . . . . . . . . . . . . . 32
- Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 34
- A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 34
+ 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 30
+ 14.1. Normative References . . . . . . . . . . . . . . . . . . 30
+ 14.2. Informative References . . . . . . . . . . . . . . . . . 33
+ Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 35
+ A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 35
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 35
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 35
- Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 35
- B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 35
- B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 37
- Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 38
- C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 38
- C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 39
- C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 40
- Appendix D. Relationships Between Curve Models . . . . . . . . . 41
+ Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 36
+ B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 36
+ B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 38
+ Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 39
+ C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 39
+ C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 40
+ C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 41
+ Appendix D. Relationships Between Curve Models . . . . . . . . . 42
D.1. Mapping between Twisted Edwards Curves and Montgomery
- Curves . . . . . . . . . . . . . . . . . . . . . . . . . 41
- D.2. Mapping between Montgomery Curves and Weierstrass Curves 42
+ Curves . . . . . . . . . . . . . . . . . . . . . . . . . 42
+ D.2. Mapping between Montgomery Curves and Weierstrass Curves 43
D.3. Mapping between Twisted Edwards Curves and Weierstrass
- Curves . . . . . . . . . . . . . . . . . . . . . . . . . 43
- Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 43
- E.1. Curve Definition and Alternative Representations . . . . 43
- E.2. Switching between Alternative Representations . . . . . . 44
- E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 45
- Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 47
- F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 47
- F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 48
- F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 49
- F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 50
- Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 51
- G.1. Further Alternative Representations . . . . . . . . . . . 51
- G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 51
- G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 52
- G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 54
- G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 54
- G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 60
- Appendix H. Point Compression . . . . . . . . . . . . . . . . . 66
- H.1. Point Compression for Weierstrass Curves . . . . . . . . 67
+ Curves . . . . . . . . . . . . . . . . . . . . . . . . . 44
+ Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 44
+ E.1. Curve Definition and Alternative Representations . . . . 44
+ E.2. Switching between Alternative Representations . . . . . . 45
+ E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 46
+ Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 48
+ F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 48
+ F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 49
+ F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 50
+ F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 51
+ Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 52
+ G.1. Further Alternative Representations . . . . . . . . . . . 52
+ G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 52
+ G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 53
+ G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 55
+ G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 55
+ G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 61
+ Appendix H. Point Compression . . . . . . . . . . . . . . . . . 67
+ H.1. Point Compression for Weierstrass Curves . . . . . . . . 68
H.2. Point Compression for Montgomery Curves . . . . . . . . . 68
- H.3. Point Compression for Twisted Edwards Curves . . . . . . 68
- Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 69
- I.1. Strings and String Operations . . . . . . . . . . . . . . 69
- I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 70
+ H.3. Point Compression for Twisted Edwards Curves . . . . . . 69
+ Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 70
+ I.1. Strings and String Operations . . . . . . . . . . . . . . 70
+ I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 71
I.3. Conversion between Octet Strings and Integers (OS2I,
- I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 70
+ I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 71
I.4. Conversion between Octet Strings and Bit Strings (OS2BS,
- BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 71
+ BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 72
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
- (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 72
- I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 72
- I.8. Conversion Between Curve Points and Octet Strings . . . . 73
+ (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 73
+ I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 73
+ I.8. Conversion Between Curve Points and Octet Strings . . . . 74
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.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 81
- J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 83
- J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 85
- Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 87
+ J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 82
+ J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 84
+ J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 86
+ Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 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.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 88
- K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 88
- K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 89
- K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 89
- K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 90
- K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 91
+ 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) . . . . . 89
+ K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 89
+ K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 90
+ K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 90
+ K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 91
+ K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 92
K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 92
- K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 92
- K.4.2. Mapping to High-Order Points of Montgomery Curve . . 93
- K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 94
- K.5. Randomized Representation of Curve Points . . . . . . . . 95
- K.6. Completing the Mappings to Curve Points . . . . . . . . . 96
- Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 99
- L.1. Curve Definition and Alternative Representation . . . . . 100
- L.2. Switching Between Representations . . . . . . . . . . . . 100
- L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 100
- L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 102
- L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 102
- L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 103
- Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 103
- M.1. Curve Definition and Alternative Representations . . . . 103
- M.2. Switching between Alternative Representations . . . . . . 104
- M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 105
- Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 108
- N.1. Further Alternative Representations . . . . . . . . . . . 108
- N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 108
- N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 111
- N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 113
- N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 113
- N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 114
- Appendix O. Representation Examples Curve448 Family Members . . 114
- O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 115
- O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 118
- O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 121
- O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 124
- O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 127
- O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 129
- Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 132
- P.1. Conversion to Integers in Z_n via Modular Reduction . . . 133
- P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 134
- P.3. Conversion to Integers in Z_n via the Discard Method . . 135
- Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 135
+ K.4.1. Mapping to High-Order Points of Weierstrass 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 95
+ K.5. Randomized Representation of Curve Points . . . . . . . . 96
+ K.6. Completing the Mappings to Curve Points . . . . . . . . . 97
+ Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 100
+ L.1. Curve Definition and Alternative Representation . . . . . 101
+ L.2. Switching Between Representations . . . . . . . . . . . . 101
+ L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 101
+ L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 103
+ L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 103
+ L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 104
+ Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 104
+ M.1. Curve Definition and Alternative Representations . . . . 104
+ M.2. Switching between Alternative Representations . . . . . . 105
+ M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 106
+ Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 109
+ N.1. Further Alternative Representations . . . . . . . . . . . 109
+ N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 109
+ N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 112
+ N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 114
+ N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 114
+ N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 115
+ Appendix O. Representation Examples Curve448 Family Members . . 115
+ O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 116
+ O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 119
+ O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 122
+ O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 125
+ O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 128
+ O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 130
+ Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 133
+ P.1. Conversion to Integers in Z_n via Modular Reduction . . . 134
+ P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 135
+ P.3. Conversion to Integers in Z_n via the Discard Method . . 136
+ Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 136
1. Fostering Code Reuse with New Elliptic Curves
Elliptic curves can be represented using different curve models.
Recently, IETF standardized elliptic curves that are claimed to have
better performance and improved robustness against "real world"
attacks than curves represented in the traditional short-Weierstrass
curve model. These so-called CFRG curves [RFC7748] use the
Montgomery curve model and the model of twisted Edwards curves.
@@ -344,37 +344,44 @@
agreement scheme (denoted by ECDH25519) results if one keeps inputs
(key contributions) and pre-output (shared key K) in the short-
Weierstrass format (and, hence, does not perform Steps (1) and (3)
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
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
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
- 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
contributions) and pre-output (shared key K) in the Montgomery curve
- format, as points of Curve25519, and where one represents all affine
- points by their x-coordinate, represented as a fixed-size octet
- string in tight LSB/msb-order using the FE2OS mapping of
- Appendix I.5, 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 compatible
- with a more lenient version of this X25519+ scheme, whereby it 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)
- and where it also accepts a shared key if all points are points of
- the quadratic twist of Curve25519, rather than of Curve25519 itself
- (for definitions of these terms, see Appendix B.1).
+ 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
RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature
scheme, with instantiation by the twisted Edwards curve Edwards25519.
@@ -453,26 +460,31 @@
than Wei25519, and picking as hash function SHAKE256 [FIPS-202] with
output size of d=512 bits. We denote by ECDSA448 the resulting
signature scheme (with the same representation and bit/byte-ordering
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 compatible with a more lenient version
- of this X448+ scheme, whereby it does not mandate rejection of shared
- keys in the small subgroup (which are instead again represented as if
- these were the point (0,0) of order two) and where it also accepts a
- shared key if all points are points of the quadratic twist of
- Curve448, rather than of Curve448 itself.
+ 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
The examples above illustrate how specifying the Weierstrass curve
Wei25519 (or any curve in short-Weierstrass format, for that matter)
may facilitate reuse of existing code and may simplify standards
development. However, the following caveats apply:
5.1. Wire Format
@@ -527,22 +539,22 @@
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
resulting curve has the same cryptographic properties as Curve25519
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
using the same special prime p=2^255-19), while at the same time
being "Jacobian-friendly" by design.
NOTE 2: While an implementation of Curve25519 via an isogenous
Weierstrass curve with domain parameter a=-3 requires a relatively
- large table (of size roughly 9kB), for the quadratic twist of
- Curve25519 (i.e., the Montgomery curve M_{A,B'} with A=486662 and
+ large table (of size roughly 9kB), for a quadratic twist of
+ 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
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
relatively small parameter l=2 (compared to l=47, as is the case with
Curve25519 itself).
6. Implementation Considerations
The efficiency of elliptic curve arithmetic is primarily determined
by the efficiency of its group operations (see Appendix C). Numerous
@@ -658,29 +670,36 @@
Elliptic curves are generally used as objects in a broader
cryptographic scheme that may include processing steps that depend on
the representation conventions used (such as with, e.g., key
derivation following key establishment). These schemes should
(obviously) unambiguously specify fixed representations of each input
and output (e.g., representing each elliptic curve point always in
short-Weierstrass form and in uncompressed tight MSB/msb format).
To prevent cross-protocol attacks, private keys SHOULD only be used
- with one cryptographic scheme. Private keys MUST NOT be reused
- between Ed25519 (as specified in [RFC8032]) and ECDSA25519 (as
- specified in Section 4.3). Similarly, private keys MUST NOT be
- reused between Ed448 (as specified in [RFC8032]) and ECDSA448 (as
- specified in Section 4.4).
+ with one cryptographic scheme.
+
+ Private keys MUST NOT be reused between Ed25519 (as specified in
+ [RFC8032]) and ECDSA25519 (as 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
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
The transformations between different curve models described in this
document are publicly known and, therefore, do not affect privacy
provisions.
Use of a public key in any protocol for which successful execution
evidences knowledge of the corresponding private key implicitly
indicates the entity holding this private key. Reuse of this public
@@ -876,21 +895,21 @@
instantiation of ECDSA and the "crv" parameter MUST be set to the
(unique) name of the corresponding curve; if the "key_ops" field is
present, it MUST include "sign" when creating an ECDSA signature and
it MUST include "verify" when verifying an ECDSA signature.
NOTE: Care should be taken that signers and verifiers do have a
common understanding of message encoding rules, since otherwise
signature verification may fail for messages with the same semantics.
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
- (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
different ToBeSigned strings and, thereby, may fail unexpectedly.
This explains the (strong) requirement for deterministic encoding
rules above and, thereby, the requirement for strong typing of any
CBOR encodings used with signed messages. Further care should be
taken that message decoding rules are always unambiguous, since
otherwise the semantics of signed messages may not be clear or the
unforgeability property of signatures may be jeopardized.
10.2.2. Encoding of ECDSA Instantiations with JOSE
@@ -1577,65 +1596,80 @@
[Wei-Ladder]
T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve
Multiplication Resistant Against Side Channel Attacks",
Centre for Applied Cryptographic Research, Corr 2002-03,
2002.
Appendix A. Some (Non-Binary) Elliptic Curves
This section defines the three different curve models we consider,
viz. short-Weierstrass curves, Montgomery curves, and twisted Edwards
- curves.
+ curves. For nomenclature, see Appendix B.
A.1. Curves in Short-Weierstrass Form
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
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
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
equation (the so-called affine points), together with the special
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
point at infinity serves as the identity element. See Appendix C.1
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
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
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
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-
called affine points), together with the special 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 point at
infinity serves as the identity element. See Appendix C.2 for
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
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
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
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
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
element. (Note that the identity element satisfies the defining
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.
+ 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
This section provides brief background information on elliptic curves
and finite fields that should be sufficient to understand
constructions and examples in this document.
B.1. Elliptic Curve Nomenclature
The set of points of each curve defined in Appendix A forms a
commutative group under addition (denoted by '+'). In Appendix C we
@@ -1687,27 +1721,28 @@
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
order n. If this representation is nonzero, R has order n;
otherwise, it has order one and is the identity element O of the
curve.
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
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
- quadratic twist of this curve can be expressed using the same curve
- model, although (naturally) with its own curve parameters. Two
- curves E and E' defined over a field GF(q) are said to be isogenous
- if these have the same order and are said to be isomorphic if these
- have the same group structure. Note that isomorphic curves have
- necessarily the same order and are, thus, a special type of isogenous
- curves. Further details are out of scope.
+ quadratic twist E' of this curve can be expressed using the same
+ curve model, although (naturally) with its own curve parameters (see
+ Appendix A). Points that are both points of E and E' have order one
+ or two. Two curves E and E' defined over a field GF(q) are said to
+ be isogenous if these have the same order and are said to be
+ isomorphic if these have the same group structure. Note that
+ 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
and twisted Edwards curves always have an order that is a multiple of
four (and, thereby, a small subgroup of cardinality four).
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
is a nonzero element of GF(q), and can be uniquely recovered from
such a representation. The latter representation is commonly called
a representation in projective coordinates. Sometimes, yet other