draft-ietf-lwig-curve-representations-20.txt   draft-ietf-lwig-curve-representations-21.txt 
lwig R. Struik lwig R. Struik
Internet-Draft Struik Security Consultancy Internet-Draft Struik Security Consultancy
Intended status: Standards Track February 17, 2021 Intended status: Informational June 9, 2021
Expires: August 21, 2021 Expires: December 11, 2021
Alternative Elliptic Curve Representations Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-20 draft-ietf-lwig-curve-representations-21
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 August 21, 2021. This Internet-Draft will expire on December 11, 2021.
Copyright Notice Copyright Notice
Copyright (c) 2021 IETF Trust and the persons identified as the Copyright (c) 2021 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
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
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 . . . . . . . . . . . . . . . 7
4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.1. Implementation of X25519, Specification of ECDH25519 . . 7 4.1. Implementation of X25519, Specification of ECDH25519 . . 8
4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 9 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 9
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 . . . . . . . . . . . . . . . . . . . . 12
6. Implementation Considerations . . . . . . . . . . . . . . . . 12 6. Implementation Considerations . . . . . . . . . . . . . . . . 13
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 13 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 14
8. Security Considerations . . . . . . . . . . . . . . . . . . . 14 8. Security Considerations . . . . . . . . . . . . . . . . . . . 15
9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 15 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 16
10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 16 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 . . . 17
10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 17 10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 18
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 . . . . . 19 10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 19
10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 20 10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 20
10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 21 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 21
10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 22 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 . . . . . . . . . 23
11.1. Encoding of Short-Weierstrass Curves with PKIX . . . . . 22 11.1. Encoding of Short-Weierstrass Curves with PKIX . . . . . 23
11.2. Encoding of ECDSA Instantiations with PKIX . . . . . . . 23 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 . . . . . . . . . . . . . . . . . . . . . . . . . . 24
11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS . . 23 11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS . . 24
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 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. JOSE IANA Considerations for Wei25519 . . . . . . . . . 24 12.2. COSE/JOSE IANA Considerations for Wei25519 . . . . . . . 25
12.2.1. JOSE Elliptic Curves Registration . . . . . . . . . 24 12.2.1. COSE Elliptic Curves Registration . . . . . . . . . 25
12.2.2. JOSE Algorithms Registration (1/2) . . . . . . . . . 25 12.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 25
12.2.3. JOSE Algorithms Registration (2/2) . . . . . . . . . 25 12.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 26
12.3. JOSE IANA Considerations for Wei448 . . . . . . . . . . 26 12.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 26
12.3.1. JOSE Elliptic Curves Registration . . . . . . . . . 26 12.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 26
12.3.2. JOSE Algorithms Registration (1/2) . . . . . . . . . 26 12.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 27
12.3.3. JOSE Algorithms Registration (2/2) . . . . . . . . . 26 12.3. COSE/JOSE IANA Considerations for Wei448 . . . . . . . . 27
13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 27 12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 27
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 27 12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 28
14.1. Normative References . . . . . . . . . . . . . . . . . . 27 12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 28
14.2. Informative References . . . . . . . . . . . . . . . . . 30 12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 29
Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 33 12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 29
A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 33 12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 29
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 33 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 30
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 33 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 30
Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 34 14.1. Normative References . . . . . . . . . . . . . . . . . . 30
B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 34 14.2. Informative References . . . . . . . . . . . . . . . . . 33
B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 36 Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 35
Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 37 A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 35
C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 37 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 36
C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 38 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 36
C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 39 Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 37
Appendix D. Relationships Between Curve Models . . . . . . . . . 40 B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 37
B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 39
Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 40
C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 40
C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 41
C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 42
Appendix D. Relationships Between Curve Models . . . . . . . . . 43
D.1. Mapping between Twisted Edwards Curves and Montgomery D.1. Mapping between Twisted Edwards Curves and Montgomery
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 40 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 43
D.2. Mapping between Montgomery Curves and Weierstrass Curves 41 D.2. Mapping between Montgomery Curves and Weierstrass Curves 44
D.3. Mapping between Twisted Edwards Curves and Weierstrass D.3. Mapping between Twisted Edwards Curves and Weierstrass
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 42 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 45
Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 42 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 45
E.1. Curve Definition and Alternative Representations . . . . 42 E.1. Curve Definition and Alternative Representations . . . . 45
E.2. Switching between Alternative Representations . . . . . . 43 E.2. Switching between Alternative Representations . . . . . . 45
E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 44 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 47
Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 46 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 49
F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 46 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 49
F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 47 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 50
F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 48 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 50
F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 49 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 51
Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 50 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 53
G.1. Further Alternative Representations . . . . . . . . . . . 50 G.1. Further Alternative Representations . . . . . . . . . . . 53
G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 50 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 53
G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 51 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 54
G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 53 G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 55
G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 53 G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 56
G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 59 G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 62
Appendix H. Point Compression . . . . . . . . . . . . . . . . . 68
Appendix H. Point Compression . . . . . . . . . . . . . . . . . 65 H.1. Point Compression for Weierstrass Curves . . . . . . . . 68
H.1. Point Compression for Weierstrass Curves . . . . . . . . 66 H.2. Point Compression for Montgomery Curves . . . . . . . . . 69
H.2. Point Compression for Montgomery Curves . . . . . . . . . 66 H.3. Point Compression for Twisted Edwards Curves . . . . . . 70
H.3. Point Compression for Twisted Edwards Curves . . . . . . 67 Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 71
Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 68 I.1. Strings and String Operations . . . . . . . . . . . . . . 71
I.1. Strings and String Operations . . . . . . . . . . . . . . 68 I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 72
I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 69
I.3. Conversion between Octet Strings and Integers (OS2I, I.3. Conversion between Octet Strings and Integers (OS2I,
I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 69 I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 72
I.4. Conversion between Octet Strings and Bit Strings (OS2BS, I.4. Conversion between Octet Strings and Bit Strings (OS2BS,
BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 70 BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 72
I.5. Conversion between Field Elements and Octet Strings I.5. Conversion between Field Elements and Octet Strings
(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 70 (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 73
I.6. Conversion between Elements of Z_n and Octet Strings I.6. Conversion between Elements of Z_n and Octet Strings
(ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 71 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 73
I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 71 I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 74
I.8. Conversion Between Curve Points and Octet Strings . . . . 72 I.8. Conversion Between Curve Points and Octet Strings . . . . 75
Appendix J. Representation Examples Curve25519 Family Members . 75 Appendix J. Representation Examples Curve25519 Family Members . 77
J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 75 J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 78
J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 78 J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 80
J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 80 J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 82
J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 82 J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 85
J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 84 J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 87
Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 86 Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 89
K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 87 K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 89
K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 87 K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 90
K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 87 K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 90
K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 88 K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 90
K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 88 K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 91
K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 88 K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 91
K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 90 K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 92
K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 91 K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 93
K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 91 K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 94
K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 91 K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 94
K.4.2. Mapping to High-Order Points of Montgomery Curve . . 92 K.4.2. Mapping to High-Order Points of Montgomery Curve . . 95
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 96
K.5. Randomized Representation of Curve Points . . . . . . . . 95 K.5. Randomized Representation of Curve Points . . . . . . . . 97
K.6. Completing the Mappings to Curve Points . . . . . . . . . 96 K.6. Completing the Mappings to Curve Points . . . . . . . . . 98
Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 99 Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 101
L.1. Curve Definition and Alternative Representation . . . . . 100 L.1. Curve Definition and Alternative Representation . . . . . 102
L.2. Switching Between Representations . . . . . . . . . . . . 100 L.2. Switching Between Representations . . . . . . . . . . . . 102
L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 100 L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 102
L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 102 L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 104
L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 102 L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 104
L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 103 L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 105
Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 103 Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 105
M.1. Curve Definition and Alternative Representations . . . . 103 M.1. Curve Definition and Alternative Representations . . . . 105
M.2. Switching between Alternative Representations . . . . . . 104 M.2. Switching between Alternative Representations . . . . . . 106
M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 105 M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 107
Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 108 Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 110
N.1. Further Alternative Representations . . . . . . . . . . . 108 N.1. Further Alternative Representations . . . . . . . . . . . 110
N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 108 N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 110
N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 111 N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 113
N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 113 N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 115
N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 113 N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 115
N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 114 N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 116
Appendix O. Representation Examples Curve448 Family Members . . 114 Appendix O. Representation Examples Curve448 Family Members . . 116
O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 115 O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 117
O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 118 O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 120
O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 121 O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 123
O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 124 O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 126
O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 127 O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 129
O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 129 O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 131
Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 132 Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 134
P.1. Conversion to Integers in Z_n via Modular Reduction . . . 133 P.1. Conversion to Integers in Z_n via Modular Reduction . . . 135
P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 134 P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 136
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 . . 137
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 135 Appendix Q. ECDSA signatures . . . . . . . . . . . . . . . . . . 137
Q.1. ECDSA Signing Operation . . . . . . . . . . . . . . . . . 137
Q.2. ECDSA Verification Operation . . . . . . . . . . . . . . 138
Q.3. Representation Examples ECDSA . . . . . . . . . . . . . . 139
Q.3.1. Example of ECDSA with Wei25519 and SHA-256 . . . . . 140
Q.3.2. Example of ECDSA with Wei25519 and SHAKE128 . . . . . 142
Q.3.3. Example of ECDSA with Wei448 and SHAKE256 . . . . . . 144
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 146
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 9, line 49 skipping to change at page 10, line 15
implementations of ECDSA with the hash function SHA-256 and with the implementations of ECDSA with the hash function SHA-256 and with the
NIST curve P-256 or with the curve Wei25519 specified in this NIST curve P-256 or with the curve Wei25519 specified in this
specification to reuse the same implementation (instantiated with, specification to reuse the same implementation (instantiated with,
respectively, the NIST P-256 elliptic curve domain parameters or with respectively, the NIST P-256 elliptic curve domain parameters or with
the domain parameters of curve Wei25519 specified in Appendix E). We the domain parameters of curve Wei25519 specified in Appendix E). We
denote by ECDSA25519 the instantiation of ECDSA with SHA-256 and with denote by ECDSA25519 the instantiation of ECDSA with SHA-256 and with
curve Wei25519, where the signature (r,s) is represented as the curve Wei25519, where the signature (r,s) is represented as the
right-concatenation of the integers r and s in the interval [1,n-1], right-concatenation of the integers r and s in the interval [1,n-1],
where n is the order of the base point of the curve in question, each where n is the order of the base point of the curve in question, each
represented as fixed-size octet strings in tight MSB/msb-order using represented as fixed-size octet strings in tight MSB/msb-order using
the Zn2OS mapping of Appendix I.6. the ZnE2OS mapping of Appendix I.6.
4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others)
Any existing specification of cryptographic schemes using elliptic Any existing specification of cryptographic schemes using elliptic
curves in Weierstrass form and that allows introduction of a new curves in Weierstrass form and that allows introduction of a new
elliptic curve (here: Wei25519) is amenable to similar constructs, elliptic curve (here: Wei25519) is amenable to similar constructs,
thus spawning "offspring" protocols, simply by instantiating these thus spawning "offspring" protocols, simply by instantiating these
using the new curve in short-Weierstrass form, thereby allowing code using the new curve in short-Weierstrass form, thereby allowing code
and/or specifications reuse and, for implementations that so desire, and/or specifications reuse and, for implementations that so desire,
carrying out curve computations "under the hood" on Montgomery curve carrying out curve computations "under the hood" on Montgomery curve
skipping to change at page 16, line 49 skipping to change at page 17, line 24
a. With the "EC2" type, each affine point (X, Y) is encoded by a. With the "EC2" type, each affine point (X, Y) is encoded by
setting the parameters "x" and "y" to the octet string setting the parameters "x" and "y" to the octet string
representations of the elements X and Y, respectively, in tight representations of the elements X and Y, respectively, in tight
MSB/msb-order, and converting each to a CBOR byte string. Each MSB/msb-order, and converting each to a CBOR byte string. Each
compressed point (X, t) is encoded by setting the parameter "x" compressed point (X, t) is encoded by setting the parameter "x"
to the octet representation of the element X, in tight MSB/msb- to the octet representation of the element X, in tight MSB/msb-
order, converted to a CBOR byte string, and by setting the order, converted to a CBOR byte string, and by setting the
parameter "y" to the CBOR false or CBOR true value, depending on parameter "y" to the CBOR false or CBOR true value, depending on
whether, respectively, t=0 or t=1. For representation details whether, respectively, t=0 or t=1. For representation details
and for details on the reverse mappings, see Appendix I.8. (Note and for details on the reverse mappings, see Appendix I.8. (Note
that for affine points this representation is consistent with the that for affine points of a curve defined over a prime field this
"EC2" representation in Section 13.1.1 of [RFC8152].) representation is consistent with the "EC2" representation in
Section 13.1.1 of [RFC8152].)
b. With the "OKP" type, each point is encoded by setting the b. With the "OKP" type, each point is encoded by setting the
parameter "x" to the "squeezed" point representation of this parameter "x" to the "squeezed" point representation of this
point, in MSB/msb-order, and converting this to a CBOR byte point, in MSB/msb-order, and converting this to a CBOR byte
string. For representation details and for details on the string. For representation details and for details on the
reverse mappings, see Appendix I.8. (Note that for affine points reverse mappings, see Appendix I.8. (Note that for affine points
this representation is consistent with the "OKP" representation of a curve defined over a prime field this representation is
in Section 7.2 of [I-D.ietf-cose-rfc8152bis-algs], which affords consistent with the "OKP" representation in Section 7.2 of
a curve-specific octet string encoding.) [I-D.ietf-cose-rfc8152bis-algs], which affords a curve-specific
octet string encoding.)
In either case, if the point is a public key (i.e., the private key In either case, if the point is a public key (i.e., the private key
is well-defined), the parameter "d" encodes the corresponding private is well-defined), the parameter "d" encodes the corresponding private
key, using the octet string representation, in tight MSB/msb-order, key, using the octet string representation, in tight MSB/msb-order,
and converting this to a CBOR byte string (see Appendix I.6). and converting this to a CBOR byte string (see Appendix I.6).
For curve points, the "crv" parameter and the parameters referenced For curve points, the "crv" parameter and the parameters referenced
with the applicable key type-specific settings above MUST be present with the applicable key type-specific settings above MUST be present
in the structure, whereas the parameter "d" MUST NOT be present, in the structure, whereas the parameter "d" MUST NOT be present,
while for private keys, the parameters "crv" and "d" MUST be present while for private keys, the parameters "crv" and "d" MUST be present
skipping to change at page 17, line 41 skipping to change at page 18, line 20
parameter to the (unique) name of the curve in question and the "kty" parameter to the (unique) name of the curve in question and the "kty"
parameter to "EC" or "OKP", respectively, where key type-specific parameter to "EC" or "OKP", respectively, where key type-specific
settings are as follows: settings are as follows:
a. With the "EC" type, each affine curve point (X, Y) is encoded by a. With the "EC" type, each affine curve point (X, Y) is encoded by
setting the parameters "x" and "y" to the octet string setting the parameters "x" and "y" to the octet string
representations of the elements X and Y, respectively, in tight representations of the elements X and Y, respectively, in tight
MSB/msb-order, and converting each using the base64url encoding. MSB/msb-order, and converting each using the base64url encoding.
The point at infinity O is encoded as if this were an affine The point at infinity O is encoded as if this were an affine
point. For representation details and details on the reverse point. For representation details and details on the reverse
mappings, see Appendix I.8. (Note that for affine points this mappings, see Appendix I.8. (Note that for affine points of a
representation is consistent with the "EC" representation in curve defined over a prime field this representation is
Section 6.2 of [RFC7518]).) consistent with the "EC" representation in Section 6.2 of
[RFC7518]).)
b. With the "OKP" type, each curve point is encoded by setting the b. With the "OKP" type, each curve point is encoded by setting the
parameter "x" to the "squeezed" point representation of this parameter "x" to the "squeezed" point representation of this
point, in MSB/msb-order, and converting this using the base64url point, in MSB/msb-order, and converting this using the base64url
encoding. For representation details and for details on the encoding. For representation details and for details on the
reverse mappings, see Appendix I.8. (Note that for affine points reverse mappings, see Appendix I.8. (Note that for affine points
this representation is consistent with the "OKP" representation of a curve defined over a prime field this representation is
in Section 2 of [RFC8037], which affords a curve-specific octet consistent with the "OKP" representation in Section 2 of
string encoding.) [RFC8037], which affords a curve-specific octet string encoding.)
In either case, if the point is a public key (i.e., the private key In either case, if the point is a public key (i.e., the private key
is well-defined), the parameter "d" encodes the corresponding private is well-defined), the parameter "d" encodes the corresponding private
key, using the octet string representation, in tight MSB/msb-order, key, using the octet string representation, in tight MSB/msb-order,
and converting this using the base64url encoding (see Appendix I.6). and converting this using the base64url encoding (see Appendix I.6).
For curve points, the "crv" parameter and the parameters referenced For curve points, the "crv" parameter and the parameters referenced
with the applicable key type-specific settings above MUST be present with the applicable key type-specific settings above MUST be present
in the structure, whereas the parameter "d" MUST NOT be present, in the structure, whereas the parameter "d" MUST NOT be present,
while for private keys, the parameters "crv" and "d" MUST be present while for private keys, the parameters "crv" and "d" MUST be present
skipping to change at page 24, line 35 skipping to change at page 25, line 14
a. id-Wei25519 OBJECT IDENTIFIER ::= TBD (Requested value: {iso(1) a. id-Wei25519 OBJECT IDENTIFIER ::= TBD (Requested value: {iso(1)
identified-organization(3) thawte (101) 108 }); identified-organization(3) thawte (101) 108 });
b. id-Wei448 OBJECT IDENTIFIER ::= TBD (Requested value: {iso(1) b. id-Wei448 OBJECT IDENTIFIER ::= TBD (Requested value: {iso(1)
identified-organization(3) thawte (101) 109 }). identified-organization(3) thawte (101) 109 }).
For a description of how these are used with PKIX certificates and For a description of how these are used with PKIX certificates and
CMS, see Section 11. CMS, see Section 11.
12.2. JOSE IANA Considerations for Wei25519 12.2. COSE/JOSE IANA Considerations for Wei25519
NOTE: This draft does not request COSE IANA registrations. 12.2.1. COSE Elliptic Curves Registration
12.2.1. JOSE Elliptic Curves Registration This section registers the following value in the IANA "COSE Elliptic
Curves" registry [IANA.COSE.Curves].
Name: Wei25519;
Value: TBD (Requested value: -1);
Key Type: EC2 or OKP;
Description: short-Weierstrass curve Wei25519;
Change Controller: IESG;
Reference: specified in Appendix E.3 of this specification; for
encodings, see Section 10.1;
Recommended: Yes.
(Note that The "kty" value for Wei25519 may be "EC2" or "OKP".)
12.2.2. COSE Algorithms Registration (1/2)
This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDSA25519;
Value: TBD (Requested value: -9);
Description: ECDSA with SHA-256 and curve Wei25519;
Change Controller: IESG;
Reference: specified in Section 4.3 of this specification; for
encodings, see Section 10.2;
Recommended: Yes.
12.2.3. COSE Algorithms Registration (2/2)
This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDH25519;
Value: TBD (Requested value: -24);
Description: NIST-compliant co-factor Diffie-Hellman w/ curve
Wei25519 and key derivation function HKDF SHA256;
Change Controller: IESG;
Reference: specified in Section 4.1 of this specification; for
encodings, see Section 10.3;
Recommended: Yes.
12.2.4. JOSE Elliptic Curves Registration
This section registers the following value in the IANA "JSON Web Key This section registers the following value in the IANA "JSON Web Key
Elliptic Curve" registry [IANA.JOSE.Curves]. Elliptic Curve" registry [IANA.JOSE.Curves].
Curve Name: Wei25519; Curve Name: Wei25519;
Curve Description: short-Weierstrass curve Wei25519; Curve Description: short-Weierstrass curve Wei25519;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
skipping to change at page 25, line 4 skipping to change at page 26, line 38
This section registers the following value in the IANA "JSON Web Key This section registers the following value in the IANA "JSON Web Key
Elliptic Curve" registry [IANA.JOSE.Curves]. Elliptic Curve" registry [IANA.JOSE.Curves].
Curve Name: Wei25519; Curve Name: Wei25519;
Curve Description: short-Weierstrass curve Wei25519; Curve Description: short-Weierstrass curve Wei25519;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Appendix E.3 of this specification; for Reference: specified in Appendix E.3 of this specification; for
encodings, see Section 10.1. encodings, see Section 10.1.
(Note that The "kty" value for Wei25519 may be "EC" or "OKP".) (Note that The "kty" value for Wei25519 may be "EC" or "OKP".)
12.2.2. JOSE Algorithms Registration (1/2) 12.2.5. JOSE Algorithms Registration (1/2)
This section registers the following value in the IANA "JSON Web This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDSA25519; Algorithm Name: ECDSA25519;
Algorithm Description: ECDSA using SHA-256 and curve Wei25519; Algorithm Description: ECDSA using SHA-256 and curve Wei25519;
Algorithm Usage Locations: alg; Algorithm Usage Locations: alg;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Section 4.3 of this specification; for Reference: specified in Section 4.3 of this specification; for
encodings, see Section 10.2; encodings, see Section 10.2;
Algorithm Analysis Document(s): Section 4.3 of this specification. Algorithm Analysis Document(s): Section 4.3 of this specification.
skipping to change at page 25, line 29 skipping to change at page 27, line 15
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Section 4.3 of this specification; for Reference: specified in Section 4.3 of this specification; for
encodings, see Section 10.2; encodings, see Section 10.2;
Algorithm Analysis Document(s): Section 4.3 of this specification. Algorithm Analysis Document(s): Section 4.3 of this specification.
12.2.3. JOSE Algorithms Registration (2/2) 12.2.6. JOSE Algorithms Registration (2/2)
This section registers the following value in the IANA "JSON Web This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDH25519; Algorithm Name: ECDH25519;
Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/ Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/
curve Wei25519 and key derivation function HKDF SHA256; curve Wei25519 and key derivation function HKDF SHA256;
Algorithm Usage Locations: alg; Algorithm Usage Locations: alg;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Section 4.1 of this specification; for Reference: specified in Section 4.1 of this specification; for
encodings, see Section 10.3; encodings, see Section 10.3;
Algorithm Analysis Document(s): Section 4.1 of this specification. Algorithm Analysis Document(s): Section 4.1 of this specification.
12.3. JOSE IANA Considerations for Wei448 12.3. COSE/JOSE IANA Considerations for Wei448
NOTE: This draft does not request COSE IANA registrations. 12.3.1. COSE Elliptic Curves Registration
12.3.1. JOSE Elliptic Curves Registration This section registers the following value in the IANA "COSE Elliptic
Curves" registry [IANA.COSE.Curves].
Name: Wei448;
Value: TBD (Requested value: -2);
Key Type: EC2 or OKP;
Description: short-Weierstrass curve Wei448;
Change Controller: IESG;
Reference: specified in Appendix M.3 of this specification; for
encodings, see Section 10.1;
Recommended: Yes.
(Note that The "kty" value for Wei448 may be "EC2" or "OKP".)
12.3.2. COSE Algorithms Registration (1/2)
This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDSA448;
Value: TBD (Requested value: -48);
Description: ECDSA with SHAKE256 and curve Wei448;
Change Controller: IESG;
Reference: specified in Section 4.4 of this specification; for
encodings, see Section 10.2;
Recommended: Yes.
12.3.3. COSE Algorithms Registration (2/2)
This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDH448;
Value: TBD (Requested value: -49);
Description: NIST-compliant co-factor Diffie-Hellman w/ curve Wei448
and key derivation function HKDF SHA512;
Change Controller: IESG;
Reference: specified in Section 4.4 of this specification; for
encodings, see Section 10.1; for key derivation, see
Section 11.1 of [RFC8152];
Recommended: Yes.
12.3.4. JOSE Elliptic Curves Registration
This section registers the following value in the IANA "JSON Web Key This section registers the following value in the IANA "JSON Web Key
Elliptic Curve" registry [IANA.JOSE.Curves]. Elliptic Curve" registry [IANA.JOSE.Curves].
Curve Name: Wei448; Curve Name: Wei448;
Curve Description: short-Weierstrass curve Wei448; Curve Description: short-Weierstrass curve Wei448;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Appendix M.3 of this specification; for Reference: specified in Appendix M.3 of this specification; for
encodings, see Section 10.1. encodings, see Section 10.1.
(Note that The "kty" value for Wei448 may be "EC" or "OKP".) (Note that The "kty" value for Wei448 may be "EC" or "OKP".)
12.3.2. JOSE Algorithms Registration (1/2) 12.3.5. JOSE Algorithms Registration (1/2)
This section registers the following value in the IANA "JSON Web This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDSA448; Algorithm Name: ECDSA448;
Algorithm Description: ECDSA using SHAKE256 and curve Wei448; Algorithm Description: ECDSA using SHAKE256 and curve Wei448;
Algorithm Usage Locations: alg; Algorithm Usage Locations: alg;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Section 4.4 of this specification; for Reference: specified in Section 4.4 of this specification; for
encodings, see Section 10.2; encodings, see Section 10.2;
Algorithm Analysis Document(s): Section 4.4 of this specification. Algorithm Analysis Document(s): Section 4.4 of this specification.
12.3.3. JOSE Algorithms Registration (2/2) 12.3.6. JOSE Algorithms Registration (2/2)
This section registers the following value in the IANA "JSON Web This section registers the following value in the IANA "JSON Web
Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
Algorithm Name: ECDH448; Algorithm Name: ECDH448;
Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/ Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/
curve Wei448; curve Wei448;
Algorithm Usage Locations: alg; Algorithm Usage Locations: alg;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: specified in Section 4.4 of this specification; for Reference: specified in Section 4.4 of this specification; for
skipping to change at page 35, line 35 skipping to change at page 38, line 23
for generating k, see Appendix P. for generating k, see Appendix P.
If P is a fixed base point G of the curve, the pair (k, R:=k*G) is If P is a fixed base point G of the curve, the pair (k, R:=k*G) is
commonly called a public-private key pair, the integer k the private commonly called a public-private key pair, the integer k the private
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.
A curve E defined over the field GF(q) has order |E| relatively close
to q, where, in fact, |E|=q+1-t for some integer t (the so-called
trace) with absolute value at most 2*|sqrt(q)|. This is commonly
referred to as the Hasse bound.
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 E' of this curve can be expressed using the same quadratic twist E' of this curve can be expressed using the same
curve model, although (naturally) with its own curve parameters (see curve model, although (naturally) with its own curve parameters (see
Appendix A). Points that are both points of E and E' have order one 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 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 be isogenous if these have the same order and are said to be
isomorphic if these have the same group structure. Note that isomorphic if these have the same group structure. Note that
isomorphic curves have necessarily the same order and are, thus, a isomorphic curves have necessarily the same order and are, thus, a
special case of isogenous curves. Further details are out of scope. special case of isogenous curves. Further details are out of scope.
Weierstrass curves can have prime order, whereas Montgomery curves Curves in short-Weierstrass form can have prime order, whereas
and twisted Edwards curves always have an order that is a multiple of Montgomery curves and twisted Edwards curves always have an order
four (and, thereby, a small subgroup of cardinality four). 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 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
representations are useful (e.g., representation in Jacobian representations are useful (e.g., representation in Jacobian
coordinates). Further details are out of scope. coordinates). Further details are out of scope.
The group laws in Appendix C are mostly expressed in terms of affine The group laws in Appendix C are mostly expressed in terms of affine
skipping to change at page 135, line 20 skipping to change at page 137, line 20
One can show that the statistical distance of the distribution on Z_n One can show that the statistical distance of the distribution on Z_n
is at most roughly N/n times as large as the statistical distance of is at most roughly N/n times as large as the statistical distance of
the source distribution on Z_N (if the latter is relatively the source distribution on Z_N (if the latter is relatively
negligible compared to n/N). Details are out of scope. negligible compared to n/N). Details are out of scope.
Note that, under the above conditions, if N:=2^m and if n has bit- Note that, under the above conditions, if N:=2^m and if n has bit-
length m, this conversion function fails with probability 1- n/N length m, this conversion function fails with probability 1- n/N
(which is at most 1/2) and, if it succeeds, does not inflate the (which is at most 1/2) and, if it succeeds, does not inflate the
statistical distance by more than (roughly) a factor two. statistical distance by more than (roughly) a factor two.
Appendix Q. ECDSA signatures
The ECDSA signature scheme is specified in FIPS Pub 186-4
[FIPS-186-4], ANSI X9.2-2005 [ANSI-X9.62], SEC 1 [SEC1], and many
other standards and can be instantiated with suitable combinations of
short-Weierstrass curves and hash functions (that satisfy particular
cryptographic criteria). Despite of its wide-spread use, some
details seem less well-understood. We, therefore, provide a concise
specification of ECDSA (for short-Weierstrass curves defined over a
prime field GF(p)) and give some examples of ECDSA computations where
the underlying short-Weierstrass curve has co-factor h>1 and domain
parameter n that differs from the output size of the used hash
function, illustrated with the curves Wei25519 and Wei448 introduced
in this document. Our description is consistent with all
forementioned standards.
The signing operation takes as inputs a message m (represented as a
bit string) and a private key d in the interval [1,n-1] and produces
as output a signature, which is an ordered pair (r, s) of integers in
the interval [1,n-1], where n is the order of the base point G of the
curve in question. The signature verification operation takes as
inputs a message m, a public key Q, and a signature (r,s) and
produces as output the value "valid" or "invalid", depending upon
whether the message was purportedly signed by a holder of the private
key of the public-private key pair (d, Q) for the curve used with the
signature scheme. Full details are provided below.
Q.1. ECDSA Signing Operation
The signing operation involves the following steps:
a. Generate a random ephemeral public-private key pair (k, R:=k*G),
by generating a random integer k in the interval [1,n-1] and
computing R:=k*G (see, e.g., Appendix B.1);
b. Compute k1:=(1/k) (mod n) (see, e.g., NOTE 1 of Appendix K.2);
c. Set xR to the x-coordinate of the (affine) point R, convert this
element of the field GF(p) to the integer r0 in the interval
[0,p-1], and set r:= r0 (mod n), where xR is converted to r0 by
subesequently using the FE2OS and OS2I mappings of Appendix I.5
and Appendix I.3, respectively;
d. Compute the hash value E:=H(m) according to the applicable hash
function H, where E is a bit string of length hashlen;
e. Represent E as the integer e in the interval [0, 2^l-1], where e
is the integer representation of the l-prefix of E, using the
BS2I mapping of Appendix I.2, and where l is the bit-length of n.
For a definition of the l-prefix, see Appendix I.1;
f. Compute s:= k1*(e+ r*d) (mod n);
g. Return to the first step if r and s are not both integers in the
interval [1,n-1];
h. Output the ordered pair (r, s) as the signature.
Q.2. ECDSA Verification Operation
The verification operation involves the following steps:
a. Check that the purported signer's public key Q is a point of the
curve in question of order n (and output "reject" if this is not
the case);
b. Check that the coordinates of the purported signature (r, s) are
both integers in the interval [1,n-1] (and output "reject" if
this is not the case);
c. Compute the hash value E:=H(m) according to the applicable hash
function H, where E is a bit string of length hashlen;
d. Represent E as the integer e in the interval [0, 2^l-1], where e
is the integer representation of the l-prefix of E, using the
BS2I mapping of Appendix I.2, and where l is the bit-length of n.
(For a definition of the l-prefix, see Appendix I.1);
e. Compute s1:=(1/s) (mod n) (see, e.g., Appendix K.2); compute u:=
e*s1 (mod n) and v:= r*s1 (mod n);
f. Compute the point R':= u*G+v*Q. Check whether R' is the identity
element O of the curve (and output "reject" if this is the case);
g. Set xR' to the x-coordinate of the (affine) point R, convert this
element of the field GF(p) to the integer r0' in the interval
[0,p-1], and set r':= r0' (mod n), where xR' is converted to r0'
by subesequently using the FE2OS and OS2I mappings of
Appendix I.5 and Appendix I.3, respectively;
h. Output "accept" if r'=r; output "reject" otherwise.
NOTE 1: For prime-order curves, r generally uniquely represents the
x-coordinate of R (since, by the Hasse bound, |E|=n is relatively
close to p). For curves with co-factor h>1, this result holds only
if one would know r0 (mod n*h), rather than r:= r0 (mod n).
NOTE 2: If an ECDSA signature (r, s) is valid for a particular
message m and public key Q, then so is (r,-s) - the so-called
malleability. Note that this corresponds to changing the ephemeral
signing key pair (k, R) in the first step of the signing operation to
(-k, -R), where the y-coordinates of R:=(xR, yR) and -R=(xR, -yR)
have different parity (see Appendix H). Since any party (not just
the signer) can recompute the ephemeral signing key R' from a valid
signature, since R':=(1/s)(e*G+r*Q), this implies that any party can
retroactively put the ECDSA signature in a form where the
y-coordinate of the ephemeral signing key has a fixed parity. This
observation can be used to put ECDSA signatures in a form that
generally allows unique and efficient recovery of R from r for prime-
order curves (due to NOTE 1 above) and more efficient signature
verification methods. Further details are out of scope.
Q.3. Representation Examples ECDSA
We present some examples of ECDSA computations, when used with curve
Wei25519 and SHA256 (see Appendix Q.3.1), with Wei25519 and SHAKE128
with output size d=256 (see Appendix Q.3.2), and with Wei448 and
SHAKE256 with output size d=512 (see Appendix Q.3.3). In each case,
we indicate the signer's public key Q:=d*G, the ephemeral signing key
R:=k*G ,the message m that is signed, and some intermediate values in
the ECDSA signing operation resulting in signature (r,s). We write
R:=(xR, yR) and Q:=(xQ, yQ), and include the ascii representation of
message m. Note that the domain parameter n of curve Wei25519 has
bit-size l:=253, whereas the corresponding domain parameter for
Wei448 has bit-size l:=446.
Q.3.1. Example of ECDSA with Wei25519 and SHA-256
d 47941274660029138864396347947568908774951195017212284524777080461
79444885588
(=0x0a996146 d73d096f 6a606ad8 72e11b12 ce973033 524591c3
ebcc630d b6368854).
xQ 34422557393689369648095312405803933433606568476197477554293337733
87341283644
(=0x079c3f69 9b688181 69038c35 39c11eb5 96d09f5b 12a242b4
ce660f13 3368c13c).
yQ 76981661982917351630937517222412729130882368858134322156485762195
67913357634
(=0x110501f6 1dff511e d6c4e9b9 bfd5acbe 8bf043b8 c3e381dd
f5771306 479ad142).
k 17426547602876470587191777825317027698752636279275919375559360929
53735113209
(=0x03da4ec1 8dc83b53 5ab8857c bbd289ae 40e6d25b ba52923c
e6b217a0 348ca9f9).
xR 38236544880946097675798638032669186189501319930946799635186226253
710117141679
(=0x54891e12 88cf078e f3f1444c c1919e30 67eb5dd6 1c6f45d1
94b9c0e1 192d7caf).
yR 24120175139256121256267158437786975197587143475570212981221664791
614551611968
(=0x3553890b d265d561 032e2daa 10b9820c 4845dbf8 f6b4f432
08f5df99 c375da40).
r 20515169942847866059327052174542149852157381340472616051764715622
82845886734
(=0x04891e12 88cf078e f3f1444c c1919e2f ff907c7c ed9935a1
dc5dd15d 4860590e).
1/k 41122695303709273156068243481808769134600808188172269288861174824
34446546266
(=0x0917764a 5a76024b e9608472 bfec99be 0cffacbe 0a5a6805
0e4e75bc 36a0d55a).
m "example ECDSA w/ Wei25519 and SHA-256"
(=0x65 78616d70 6c652045 43445341 20772f20 57656932 35353139
20616e64 20534841 2d323536).
E 10340924651306471157182528854495725311608440786255119926874295925
4624066081637
(=0xe49f8f34 0ac7fd87 1ca6c035 1ac83b97 2ec4711e f4a79d37
214b6b94 c6f41365).
e 12926155814133088946478161068119656639510550982818899908592869906
828008260204
(=0x1c93f1e6 8158ffb0 e394d806 a3590772 e5d88e23 de94f3a6
e4296d72 98de826c).
s 18145968192643101430203980459406244543409512911444833316246990876
74236833451
(=0x04030680 d490837e 0b50800d 5052feb3 8181da43 f14fea65
d75fff8e 095d8eab).
The ECDSA signature (r,s) can be represented uniquely as the 64-octet
string
0x04891e12 88cf078e f3f1444c c1919e2f ff907c7c ed9935a1 dc5dd15d
4860590e
04030680 d490837e 0b50800d 5052feb3 8181da43 f14fea65 d75fff8e
095d8eab,
where this string is the right-concatenation of the integers r and s,
each represented as fixed-size octet string in tight MSB/msb-order
using the ZnE2OS mapping of Appendix I.6. Since an ECDSA signature
(r, s) if valid only if the ECDSA signature (r,-s) is, one can
alternatively use the representation
0x04891e12 88cf078e f3f1444c c1919e2f ff907c7c ed9935a1 dc5dd15d
4860590e
0bfcf97f 2b6f7c81 f4af7ff2 afad014c 935d1f9a b1a7b270 80b2638c
53984542,
with the same representation conventions.
Q.3.2. Example of ECDSA with Wei25519 and SHAKE128
d 50032130580855419870069268521079636534051105694026315073511374709
23129445444
(=0x0b0fb7de 7b857528 c16cc691 f91acb6a e6f83700 c2257210
d9ce4a66 540f5c44).
xQ 49674872575618115649605301860097524739691386255387989689284412105
715250815836
(=0x6dd2fb44 ebc47199 0558875c 338b32a0 01c04e5e 54b0239f
931ba404 43fee35c).
yQ 19668752079014976246249662506722644231308019872013845936101364656
882653051514
(=0x2b7c1e81 e0d7311a 7e73c581 ac8d7478 f5d8402e a25ecf03
2fcf49b3 ebe3ba7a).
k 67458228593538039868031175183537823353427877783158546151245140204
51058711301
(=0x0eea001c 69e39d65 a93a736f 51dab17d 3c89d712 67b95dba
28f43e6c 6d73fb05).
xR 22710793528316744414502819712682283876956423576126122262984645007
656889457787
(=0x3235da86 6c184868 db1060f4 c57414ba f9dd8bbf af94eb8e
65a26fa8 146d9c7b).
yR 48228386115947942380117850340406514077008333836380715701663219971
594920954196
(=0x6aa04c98 30a51d5a 226fc67b 6ec00aa4 66eae465 432825e3
c8da192d 330c8954).
r 99977679631995777258326002355330115438507449798639944497879219280
0526704820
(=0x0235da86 6c184868 db1060f4 c57414ba bb409e23 c6ae150b
5d6b4658 fd8c20b4).
1/k 16237902548817115200666748510759761693156732885271500846541777492
82633956147
(=0x03970860 022244d0 1cee5f2e 973372d7 2000b51d 2d75731c
0e27428a 7e723b33).
m "example ECDSA w/ Wei25519 and SHAKE128"
(=0x6578 616d706c 65204543 44534120 772f2057 65693235 35313920
616e6420 5348414b 45313238).
E 52885769330535495835899107243770360963478954388007874330946529931
479220563171
(=0x74ec48e0 d8b9c37c 7ad823b5 e1d9e837 45b4c7c5 d02f2938
1f99196f f2052ce3).
e 66107211663169369794873884054712951204348692985009842913683162414
34902570396
(=0x0e9d891c 1b17386f 8f5b0476 bc3b3d06 e8b698f8 ba05e527
03f3232d fe40a59c).
s 21018124433820277670749322033999530145769351947494095769585139740
41491232262
(=0x04a5956c 6d03d578 40764c7d 33e8159a 2c875830 0b5a4228
f585dc0f b8135606).
The ECDSA signature (r,s) can be represented uniquely as the 64-octet
string
0x0235da86 6c184868 db1060f4 c57414ba bb409e23 c6ae150b 5d6b4658
fd8c20b4
04a5956c 6d03d578 40764c7d 33e8159a 2c875830 0b5a4228 f585dc0f
b8135606,
where this string is the right-concatenation of the integers r and s,
each represented as fixed-size octet string in tight MSB/msb-order
using the ZnE2OS mapping of Appendix I.6. Since an ECDSA signature
(r, s) if valid only if the ECDSA signature (r,-s) is, one can
alternatively use the representation
0x0235da86 6c184868 db1060f4 c57414ba bb409e23 c6ae150b 5d6b4658
fd8c20b4
0b5a6a93 92fc2a87 bf89b382 cc17ea65 e857a1ae 979d5aad 628c870a
a4e27de7,
with the same representation conventions.
Q.3.3. Example of ECDSA with Wei448 and SHAKE256
d 83773921833883065724152755040779926324701042667680137762329241115
92597160376444120699241862910141955866217224630560765595890572227
9690
(=0x1d818b12 92af6ef4 3f0ed657 b55d2ab7 a0cd1e64 516414d1
d32ea610 dd6dddbe af65bc96 df648e6d fac1b907 6588b37e 984d5860
7390970a).
xQ 40351504322781497250899987383866753965468971276834772118588405333
77140867939355980788573436893357369201402928958042617224896092079
46142
(=0x8e1f426a 4a1af133 ff970fe2 76693c7a eaa78786 361b1cfe
4ccbd786 e020ba9a 0bf65a1d 5d9a128a f85c63a2 79a00139 7aca56db
15341b9e).
yQ 55735504615964066386264989698774850924544182484936624265048483231
35693859362627880184586282439234602798023594054611737412667543758
11547
(=0xc44e5e0f 2c254d23 1dc082db 77175e8c fd37793c 22ebe200
77905a5f 750b3c9f 4a95d4d5 4e1a1e54 d2d31689 4249252d 0c8b1c45
1c1481db).
k 56463034235306169014882307562036113095966844917631298686749571574
22895909756933115614724351575144190884397720504249121444938140865
3424
(=0x13e308f8 2f7eb169 78a86240 a2087c59 38ad954c 5a725311
00e2738b 93f87064 06846d1b 0348c213 5cd8f9db 21cbf970 6b70fa40
29364070).
xR 46421117529223435940590399200091023258880155395346929342228475577
87411917154572694868891187346300643187653728654052509827159201295
60118
(=0xa37ff9a3 9734a3dc 9ccf72b7 cb3b8e5e 20d4e1f1 655c973a
c72e4aa4 6f139529 84b1cd37 2524bf09 c4e38684 5c88cc79 e8e19242
42398e36).
yR 48450878695819342796480063527087959345962966106444727188216313803
37436540801561730584163096514114057681225129685101546366763700225
61560
(=0xaaa6202c df8711b2 6e5a8802 6c5d86b3 2f320d89 8f48a809
40818982 bb74e0cc 7b884f20 aad090fb 90c4c93f fd84ed56 c03451d8
84fc7718).
r 10079181314443091413124208805690796541198087360981026328153965618
84491837923780980544976081512453123921447854472219263731684084102
60560
(=0x237ff9a3 9734a3dc 9ccf72b7 cb3b8e5e 20d4e1f1 655c973a
c72e4aa5 757f4d55 fc1416a3 c77851e9 820a019f 40fdadcf a1f00d1c
eb890450).
1/k 13511362508598651506450197334516130806445911047753884276726477993
82054003440714897722657048821186399503939251111689038388764827779
24830
(=0x2f96a107 4a355722 1f20fd90 aed12db3 83b3c32f 593079f4
779e2942 3ad2b5e6 0ea15bdc a57e5827 04ed1f09 e42b8352 68428208
502444de).
m "example ECDSA w/ Wei448 and SHAKE256"
(=0x6578616d 706c6520 45434453 4120772f 20576569 34343820
616e6420 5348414b 45323536).
E 12090734314062687821830960462859241481351750980975210807010692417
87788290188009052883047169049228170145424614719943072950310100584
3039685804727137826504734
(=0xe6da473c 90ccc33d 35b6f458 dda7a718 6296d1fc f6ed5139
49978903 10c3eb0b 448726c3 470051e9 4562c319 070156c1 36b6818b
eb9b4c18 873fbc40 3b38001e).
e 16386000512814751750588212096686160936149469654286309627413103110
39082128948717862895885154262738521307509222558257976323832793566
29766
(=0x39b691cf 243330cf 4d6dbd16 3769e9c6 18a5b47f 3dbb544e
5265e240 c430fac2 d121c9b0 d1c0147a 5158b0c6 41c055b0 4dada062
fae6d306).
s 13548644118210160703789217445495123183108197273149701428544426319
69721549289474790694640600902913761876631795267154847305287335592
32284
(=0x2fb83e89 3ce77084 18cfff70 d02c01df d4c10a3f 90e0546e
993d82ba 823b5b5b d9b62b3d 521cdbf5 c6144ade c58d1084 401c1f21
45f3971c).
The ECDSA signature (r,s) can be represented uniquely as the
112-octet string
0x237ff9a3 9734a3dc 9ccf72b7 cb3b8e5e 20d4e1f1 655c973a c72e4aa5
757f4d55 fc1416a3 c77851e9 820a019f 40fdadcf a1f00d1c eb890450
2fb83e89 3ce77084 18cfff70 d02c01df d4c10a3f 90e0546e 993d82ba
823b5b5b d9b62b3d 521cdbf5 c6144ade c58d1084 401c1f21 45f3971c,
where this string is the right-concatenation of the integers r and s,
each represented as fixed-size octet string in tight MSB/msb-order
using the ZnE2OS mapping of Appendix I.6. Since an ECDSA signature
(r, s) if valid only if the ECDSA signature (r,-s) is, one can
alternatively use the representation
0x237ff9a3 9734a3dc 9ccf72b7 cb3b8e5e 20d4e1f1 655c973a c72e4aa5
757f4d55 fc1416a3 c77851e9 820a019f 40fdadcf a1f00d1c eb890450
1047c176 c3188f7b e730008f 2fd3fe20 2b3ef5c0 6f1fab91 66c27d44
fa8ec88d ea98b00c 5cb95a9a 5b587793 c8387ed0 e35ca371 6564add7,
with the same representation conventions.
Author's Address Author's Address
Rene Struik Rene Struik
Struik Security Consultancy Struik Security Consultancy
Email: rstruik.ext@gmail.com Email: rstruik.ext@gmail.com
 End of changes. 38 change blocks. 
151 lines changed or deleted 720 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/