draft-ietf-lwig-curve-representations-09.txt   draft-ietf-lwig-curve-representations-10.txt 
lwig R. Struik lwig R. Struik
Internet-Draft Struik Security Consultancy Internet-Draft Struik Security Consultancy
Intended status: Informational March 9, 2020 Intended status: Informational April 23, 2020
Expires: September 10, 2020 Expires: October 25, 2020
Alternative Elliptic Curve Representations Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-09 draft-ietf-lwig-curve-representations-10
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 September 10, 2020. This Internet-Draft will expire on October 25, 2020.
Copyright Notice Copyright Notice
Copyright (c) 2020 IETF Trust and the persons identified as the Copyright (c) 2020 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
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 . . . . . . . . . . . . . . . . . . 5 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 5
3. Use of Representation Switches . . . . . . . . . . . . . . . 5 3. Use of Representation Switches . . . . . . . . . . . . . . . 6
4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 6 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 6 4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 7
4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 7 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 7
4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 7 4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 8
4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 8 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 8
5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 9 5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 9
5.2. Representation Conventions . . . . . . . . . . . . . . . 9 5.2. Representation Conventions . . . . . . . . . . . . . . . 9
5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 9 5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 10
6. Implementation Considerations . . . . . . . . . . . . . . . . 10 6. Implementation Considerations . . . . . . . . . . . . . . . . 10
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 11 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 12
8. Security Considerations . . . . . . . . . . . . . . . . . . . 12 8. Security Considerations . . . . . . . . . . . . . . . . . . . 12
9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 13 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 13
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 14
10.1. IANA Considerations for Wei25519 . . . . . . . . . . . . 13 10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 14
10.1.1. COSE Elliptic Curves Registration . . . . . . . . . 14 10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 14
10.1.2. COSE Algorithms Registration (1/2) . . . . . . . . . 14 10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 15
10.1.3. COSE Algorithms Registration (2/2) . . . . . . . . . 14 10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 16
10.1.4. JOSE Elliptic Curves Registration . . . . . . . . . 15 10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 17
10.1.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 15 10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 17
10.1.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 16 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 18
10.2. IANA Considerations for Wei448 . . . . . . . . . . . . . 16 10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 19
10.2.1. COSE Elliptic Curves Registration . . . . . . . . . 16 10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 19
10.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 17 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20
10.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 17 11.1. IANA Considerations for Wei25519 . . . . . . . . . . . . 20
10.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 17 11.1.1. COSE Elliptic Curves Registration . . . . . . . . . 20
10.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 18 11.1.2. COSE Algorithms Registration (1/2) . . . . . . . . . 21
10.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 18 11.1.3. COSE Algorithms Registration (2/2) . . . . . . . . . 21
11.1.4. JOSE Elliptic Curves Registration . . . . . . . . . 21
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 18 11.1.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 22
12. References . . . . . . . . . . . . . . . . . . . . . . . . . 19 11.1.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 22
12.1. Normative References . . . . . . . . . . . . . . . . . . 19 11.2. IANA Considerations for Wei448 . . . . . . . . . . . . . 23
12.2. Informative References . . . . . . . . . . . . . . . . . 20 11.2.1. COSE Elliptic Curves Registration . . . . . . . . . 23
Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 22 11.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 23
A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 22 11.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 23
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 22 11.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 24
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 23 11.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 24
Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 23 11.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 25
B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 23 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 25
B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 25 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 25
Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 26 13.1. Normative References . . . . . . . . . . . . . . . . . . 25
C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 26 13.2. Informative References . . . . . . . . . . . . . . . . . 28
C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 27 Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 29
C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 28 A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 29
Appendix D. Relationship Between Curve Models . . . . . . . . . 29 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 30
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 30
Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 30
B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 30
B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 32
Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 33
C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 33
C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 34
C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 35
Appendix D. Relationship Between Curve Models . . . . . . . . . 36
D.1. Mapping between Twisted Edwards Curves and Montgomery D.1. Mapping between Twisted Edwards Curves and Montgomery
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 29 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 36
D.2. Mapping between Montgomery Curves and Weierstrass Curves 30 D.2. Mapping between Montgomery Curves and Weierstrass Curves 37
D.3. Mapping between Twisted Edwards Curves and Weierstrass D.3. Mapping between Twisted Edwards Curves and Weierstrass
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 31 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 38
Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 31 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 38
E.1. Curve Definition and Alternative Representations . . . . 31 E.1. Curve Definition and Alternative Representations . . . . 38
E.2. Switching between Alternative Representations . . . . . . 31 E.2. Switching between Alternative Representations . . . . . . 38
E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 33 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 40
Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 35 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 42
F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 35 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 42
F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 36 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 43
F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 36 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 43
F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 37 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 44
Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 39 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 46
G.1. Further Alternative Representations . . . . . . . . . . . 39 G.1. Further Alternative Representations . . . . . . . . . . . 46
G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 39 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 46
G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 40 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 47
G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 41 G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 48
G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 42 G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 49
G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 48 G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 55
Appendix H. Point Compression . . . . . . . . . . . . . . . . . 54 Appendix H. Point Compression . . . . . . . . . . . . . . . . . 61
H.1. Point Compression for Weierstrass Curves . . . . . . . . 54 H.1. Point Compression for Weierstrass Curves . . . . . . . . 61
H.2. Point Compression for Montgomery Curves . . . . . . . . . 55 H.2. Point Compression for Montgomery Curves . . . . . . . . . 62
H.3. Point Compression for Twisted Edwards Curves . . . . . . 56 H.3. Point Compression for Twisted Edwards Curves . . . . . . 63
Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 57 Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 64
I.1. Conversion between Bit Strings and Integers (BS2I, I2BS) 57 I.1. Strings and String Operations . . . . . . . . . . . . . . 64
I.2. Conversion between Octet Strings and Integers (OS2I, I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 64
I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 58 I.3. Conversion between Octet Strings and Integers (OS2I,
I.3. Conversion between Octet Strings and Bit Strings (OS2BS, I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 65
BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 58 I.4. Conversion between Octet Strings and Bit Strings (OS2BS,
I.4. Conversion between Field Elements and Octet Strings BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 65
(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 58 I.5. Conversion between Field Elements and Octet Strings
I.5. Conversion between Elements of Z mod n and Octet Strings (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 66
(ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 59 I.6. Conversion between Elements of Z mod n and Octet Strings
I.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 59 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 66
Appendix J. Representation Examples Curve25519 Family Members . 61 I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 67
J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 61 I.8. Conversion Between Curve Points and Octet Strings . . . . 68
J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 63 Appendix J. Representation Examples Curve25519 Family Members . 70
J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 65 J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 71
J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 67 J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 73
J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 68 J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 74
Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 70 J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 77
K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 70 J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 78
K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 70 Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 80
K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 70 K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 80
K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 71 K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 80
K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 71 K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 80
K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 71 K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 81
K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 72 K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 81
K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 74 K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 81
K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 74 K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 82
K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 74 K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 83
K.4.2. Mapping to High-Order Points of Montgomery Curve . . 75 K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 84
K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 76 K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 84
K.5. Randomized Representation of Curve Points . . . . . . . . 77 K.4.2. Mapping to High-Order Points of Montgomery Curve . . 85
Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 78 K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 86
L.1. Curve Definition and Alternative Representation . . . . . 78 K.5. Randomized Representation of Curve Points . . . . . . . . 87
L.2. Switching Between Representations . . . . . . . . . . . . 79 Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 88
L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 79 L.1. Curve Definition and Alternative Representation . . . . . 88
L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 81 L.2. Switching Between Representations . . . . . . . . . . . . 89
L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 81 L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 89
L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 81 L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 91
Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 82 L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 91
M.1. Curve Definition and Alternative Representations . . . . 82 L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 91
M.2. Switching between Alternative Representations . . . . . . 83 Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 92
M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 84 M.1. Curve Definition and Alternative Representations . . . . 92
Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 87 M.2. Switching between Alternative Representations . . . . . . 93
N.1. Further Alternative Representations . . . . . . . . . . . 87 M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 94
N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 87 Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 97
N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 89 N.1. Further Alternative Representations . . . . . . . . . . . 97
N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 91 N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 97
N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 92 N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 99
N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 92 N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 101
Appendix O. Representation Examples Curve448 Family Members . . 93 N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 102
O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 93 N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 102
O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 96 Appendix O. Representation Examples Curve448 Family Members . . 103
O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 98 O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 104
O.4. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 101 O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 106
O.5. Example with Edwards448 . . . . . . . . . . . . . . . . . 103 O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 108
O.4. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 111
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 105 O.5. Example with Edwards448 . . . . . . . . . . . . . . . . . 113
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 115
1. Fostering Code Reuse with New Elliptic Curves 1. Fostering Code Reuse with New Elliptic Curves
Elliptic curves can be represented using different curve models. Elliptic curves can be represented using different curve models.
Recently, IETF standardized elliptic curves that are claimed to have Recently, IETF standardized elliptic curves that are claimed to have
better performance and improved robustness against "real world" better performance and improved robustness against "real world"
attacks than curves represented in the traditional "short" attacks than curves represented in the traditional "short"
Weierstrass model. This document specifies an alternative Weierstrass model. This document specifies an alternative
representation of points of Curve25519, a so-called Montgomery curve, representation of points of Curve25519, a so-called Montgomery curve,
and of points of Edwards25519, a so-called twisted Edwards curve, and of points of Edwards25519, a so-called twisted Edwards curve,
skipping to change at page 7, line 16 skipping to change at page 7, line 28
parameters; (3) representing the key resulting from this scheme parameters; (3) representing the key resulting from this scheme
(which is a point of the curve Wei25519 in Weierstrass form) as a (which is a point of the curve Wei25519 in Weierstrass form) as a
point of the Montgomery curve Curve25519. The representation change point of the Montgomery curve Curve25519. The representation change
can be implemented via a simple wrapper and involves a single modular can be implemented via a simple wrapper and involves a single modular
addition (see Appendix E.2). Using this method has the additional addition (see Appendix E.2). Using this method has the additional
advantage that one can reuse the public-private key pair routines, advantage that one can reuse the public-private key pair routines,
domain parameter validation, and other checks that are already part domain parameter validation, and other checks that are already part
of the NIST specifications. A NIST-compliant version of co-factor of the NIST specifications. A NIST-compliant version of co-factor
Diffie-Hellman key agreement (denoted by ECDH25519) results if one Diffie-Hellman key agreement (denoted by ECDH25519) results if one
keeps inputs (key contributions) and outputs (shared key) in the keeps inputs (key contributions) and outputs (shared key) in the
short-Weierstrass format (and, hence, does not perform Step (3) short-Weierstrass format (and, hence, does not perform Steps (1) and
above). (3) above).
NOTE: At this point, it is unclear whether this implies that a FIPS- NOTE: At this point, it is unclear whether this implies that a FIPS-
accredited module implementing co-factor Diffie-Hellman for, e.g., accredited module implementing co-factor Diffie-Hellman for, e.g.,
P-256 would also extend this accreditation to X25519. P-256 would also extend this accreditation to X25519.
4.2. Implementation of Ed25519 4.2. Implementation of Ed25519
RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature
scheme, with instantiation by the twisted Edwards curve Edwards25519. scheme, with instantiation by the twisted Edwards curve Edwards25519.
One can implement the computation of the ephemeral key pair for One can implement the computation of the ephemeral key pair for
skipping to change at page 9, line 24 skipping to change at page 9, line 34
The transformations between alternative curve representations can be The transformations between alternative curve representations can be
implemented at negligible relative incremental cost if the curve implemented at negligible relative incremental cost if the curve
points are represented as affine points. If a point is represented points are represented as affine points. If a point is represented
in compressed format, conversion usually requires a costly point in compressed format, conversion usually requires a costly point
decompression step. This is the case in [RFC7748], where the inputs decompression step. This is the case in [RFC7748], where the inputs
to the co-factor Diffie-Hellman scheme X25519, as well as its output, to the co-factor Diffie-Hellman scheme X25519, as well as its output,
are represented in u-coordinate-only format. This is also the case are represented in u-coordinate-only format. This is also the case
in [RFC8032], where the EdDSA signature includes the ephemeral in [RFC8032], where the EdDSA signature includes the ephemeral
signing key represented in compressed format (see Appendix H for signing key represented in compressed format (see Appendix H for
details). Note that in the latter case compression is lossless, details). Note that in the latter case compression is lossless,
whereas it is lossy in the former case; whereas it is lossy in the former case.
5.2. Representation Conventions 5.2. Representation Conventions
While elliptic curve computations are carried-out in a field GF(q) While elliptic curve computations are carried-out in a field GF(q)
and, thereby, involve large integer arithmetic, these integers are and, thereby, involve large integer arithmetic, these integers are
represented as bit- and byte-strings. Here, [RFC8032] uses least- represented as bit- and byte-strings. Here, [RFC8032] uses least-
significant-byte (LSB)/least-significant-bit (lsb) conventions, significant-byte (LSB)/least-significant-bit (lsb) conventions,
whereas [RFC7748] uses LSB/most-significant-bit (msb) conventions, whereas [RFC7748] uses LSB/most-significant-bit (msb) conventions,
and where most other cryptographic specifications, including NIST and where most other cryptographic specifications, including NIST
SP800-56a [SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI SP800-56a [SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI
X9.62-2005 [ANSI-X9.62] use MSB/msb conventions. Since each pair of X9.62-2005 [ANSI-X9.62] use most-significant-byte (MSB)/msb
conventions is different (see Appendix I for details and Appendix J conventions. Since each pair of conventions is different (see
for examples), this does necessitate bit/byte representation Appendix I for details and Appendix J for examples), this does
conversions; necessitate bit/byte representation conversions.
5.3. Domain Parameters 5.3. Domain Parameters
All traditional NIST curves are Weierstrass curves with domain All traditional NIST curves are Weierstrass curves with domain
parameter a=-3, while all Brainpool curves [RFC5639] are isomorphic parameter a=-3, while all Brainpool curves [RFC5639] are isomorphic
to a Weierstrass curve of this form. Thus, one can expect there to to a Weierstrass curve of this form. Thus, one can expect there to
be existing Weierstrass implementations with a hardcoded a=-3 domain be existing Weierstrass implementations with a hardcoded a=-3 domain
parameter ("Jacobian-friendly"). For those implementations, parameter ("Jacobian-friendly"). For those implementations,
including the curve Wei25519 as a potential vehicle for offering including the curve Wei25519 as a potential vehicle for offering
support for the CFRG curves Curve25519 and Edwards25519 is not support for the CFRG curves Curve25519 and Edwards25519 is not
possible, since not of the required form. Instead, one has to possible, since not of the required form. Instead, one has to
implement Wei25519.-3 and include code that implements the isogeny implement Wei25519.-3 and include code that implements the isogeny
and dual isogeny from and to Wei25519. The lowest odd-degree isogeny and dual isogeny from and to Wei25519. The lowest odd-degree isogeny
has degree l=47 and requires roughly 9kB of storage for isogeny and has degree l=47 and requires roughly 9kB of storage for isogeny and
dual-isogeny computations (see the tables in Appendix G.4). Note dual-isogeny computations (see the tables in Appendix G.4). Note
that storage would have reduced to a single 64-byte table if only the that storage would have reduced to a single 64-byte table if only the
curve would have been generated so as to be isomorphic to a Curve25519 curve would have been generated so as to be isomorphic to
Weierstrass curve with hardcoded a=-3 parameter (this corresponds to a Weierstrass curve with hardcoded a=-3 parameter (this corresponds
l=1). to l=1).
NOTE 1: An example of a Montgomery curve defined over the same field NOTE 1: An example of a Montgomery curve defined over the same field
as Curve25519 that is isomorphic to a Weierstrass curve with as Curve25519 that is isomorphic to a Weierstrass curve with
hardcoded a=-3 parameter is the Montgomery curve M_{A,B} with B=1 and hardcoded a=-3 parameter is the Montgomery curve M_{A,B} with B=1 and
A=-1410290 (or, if one wants the base point to still have A=-1410290 (or, if one wants the base point to still have
u-coordinate u=9, with B=1 and A=-3960846). In either case, the u-coordinate u=9, with B=1 and A=-3960846). In either case, the
resulting curve has the same cryptographic properties as Curve25519 resulting curve has the same cryptographic properties as Curve25519
and the same performance (which relies on A being a 3-byte integer, and the same performance (which relies on A being a 3-byte integer,
as is the case with the domain parameter A=486662 of Curve25519, and as is the case with the domain parameter A=486662 of Curve25519, and
using the same special prime p=2^255-19), while at the same time using the same special prime p=2^255-19), while at the same time
skipping to change at page 13, line 13 skipping to change at page 13, line 31
(obviously) unambiguously specify fixed representations of each input (obviously) unambiguously specify fixed representations of each input
and output (e.g., representing each elliptic curve point always in and output (e.g., representing each elliptic curve point always in
short-Weierstrass form and in uncompressed tight MSB/msb format). short-Weierstrass form and in uncompressed tight MSB/msb format).
To prevent cross-protocol attacks, private keys SHOULD only be used To prevent cross-protocol attacks, private keys SHOULD only be used
with one cryptographic scheme. Private keys MUST NOT be reused with one cryptographic scheme. Private keys MUST NOT be reused
between Ed25519 (as specified in [RFC8032]) and ECDSA25519 (as between Ed25519 (as specified in [RFC8032]) and ECDSA25519 (as
specified in Section 4.3). specified in Section 4.3).
To prevent intra-protocol cross-instantiation attacks, ephemeral To prevent intra-protocol cross-instantiation attacks, ephemeral
private keys MUST NOT be reused between instantiations of ECDSA25519. private keys MUST NOT be reused between instantiations of ECDSA25519
or ECDSA448.
9. Privacy Considerations 9. Privacy Considerations
The transformations between different curve models described in this The transformations between different curve models described in this
document are publicly known and, therefore, do not affect privacy document are publicly known and, therefore, do not affect privacy
provisions. provisions.
Use of a public key in any protocol for which successful execution Use of a public key in any protocol for which successful execution
evidences knowledge of the corresponding private key implicitly evidences knowledge of the corresponding private key implicitly
indicates the entity holding this private key. Reuse of this public indicates the entity holding this private key. Reuse of this public
skipping to change at page 13, line 35 skipping to change at page 14, line 7
instantiation may, therefore, allow traceability of this entity. It instantiation may, therefore, allow traceability of this entity. It
may also allow correlation of meta-data communicated with this common may also allow correlation of meta-data communicated with this common
data element (e.g., different addressing information), even if an data element (e.g., different addressing information), even if an
observer cannot technically verify the binding of this meta-data. observer cannot technically verify the binding of this meta-data.
The randomized representation described in Appendix K.5 allows random The randomized representation described in Appendix K.5 allows random
curve points to be represented as random pairs of field elements, curve points to be represented as random pairs of field elements,
thereby assisting in obfuscating the presence of these curve points thereby assisting in obfuscating the presence of these curve points
in some applications. in some applications.
10. IANA Considerations 10. Using Wei25519 and Wei448 with COSE and JOSE
Code points are requested for curve Wei25519 and Wei448 and its use This section defines algorithm encodings and representations enabling
with ECDSA and co-factor ECDH, using the representation conventions the use of the curves Wei25519 and Wei448 and their use with ECDH and
of this document. ECDSA with JOSE [RFC7518] and COSE [RFC8152] messages.
All octet string encodings below use the MSB/msb-ordering conventions
as defined in Appendix I.7. For CBOR representation details, we
refer to [RFC7049]; for base64url encodings, we refer to [RFC4648].
10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE
For Weierstrass curves, the representation of the point at infinity O
is curve-specific (see Appendix H.1). For the short-Weierstrass
curve Wei25519, we define O:=(-1,0), whereas for Wei448, we define
O:=(1,0).
The encodings below specify the use of short-Weierstrass curves with
COSE (see Section 10.1.1) and JOSE (see Section 10.1.2), where the
encoding for a specific curve results by setting the "crv" parameter
to the unique name of the curve in question (e.g., "Wei25519" for the
curve Wei25519 and "Wei448" for the curve Wei448).
10.1.1. Encoding of Short-Weierstrass Curves with COSE
With COSE, points of short-Weierstrass curves are encoded using the
"EC2" key type (Section 13.1.1 of [RFC8152]) or the "OKP" key type
(Section 7.2 of [I-D.ietf-cose-rfc8152bis-algs]), which are
instantiated by setting the "crv" parameter to the (unique) name of
the curve in question and the "kty" parameter to "EC2" or "OKP",
respectively, where key type-specific settings are as follows:
a. With the "EC2" type, each affine point (X, Y) is encoded by
setting the parameters "x" and "y" to the octet string
representations of the elements X and Y, respectively, in tight
MSB/msb-order, and converting each to a CBOR byte string. Each
compressed point (X, t) is encoded by setting the parameter "x"
to the octet representation of the element X, in tight MSB/msb-
order, converted to a CBOR byte string, and by setting the
parameter "y" to the CBOR False or CBOR True value, depending on
whether, respectively, t=0 or t=1. For representation details
and for details on the reverse mappings, see Appendix I.8. (Note
that for affine points this 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
parameter "x" to the "squeezed" point representation of this
point, in MSB/msb-order, and converting this to a CBOR byte
string. For representation details and for details on the
reverse mappings, see Appendix I.8. (Note that for affine points
this representation is consistent with the "OKP" representation
in Section 7.2 of [I-D.ietf-cose-rfc8152bis-algs], which affords
a curve-specific octet string encoding.)
In either case, if the point is a public key, the parameter "d"
encodes the corresponding private key, using the octet string
representation, in tight MSB/msb-order, and converting this to a CBOR
byte string (see Appendix I.6).
For curve points, the "crv" parameter and the parameters referenced
with the applicable key type-specific settings above MUST 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
and the applicable key type-specific parameters of the corresponding
public-key are RECOMMENDED to be present.
10.1.2. Encoding of Short-Weierstrass Curves with JOSE
With JOSE, points of short-Weierstrass curves are encoded using the
"EC" key type (Section 6.2 of [RFC7518]) or the "OKP" key type
(Section 2 of [RFC8037]), which are instantiated by setting the "crv"
parameter to the (unique) name of the curve in question and the "kty"
parameter to "EC" or "OKP", respectively, where key type-specific
settings are as follows:
a. With the "EC" type, each affine curve point (X, Y) is encoded by
setting the parameters "x" and "y" to the octet string
representations of the elements X and Y, respectively, in tight
MSB/msb-order, and converting each using the base64url encoding.
The point at infinity O is encoded as if this were an affine
point. For representation details and details on the reverse
mappings, see Appendix I.8. (Note that for affine points this
representation is consistent with the "EC" representation in
Section 6.2 of [RFC7518]).)
b. With the "OKP" type, each curve point is encoded by setting the
parameter "x" to the "squeezed" point representation of this
point, in MSB/msb-order, and converting this using the base64url
encoding. For representation details and for details on the
reverse mappings, see Appendix I.8. (Note that for affine points
this representation is consistent with the "OKP" representation
in Section 2 of [RFC8037], which affords a curve-specific octet
string encoding.)
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
key, using the octet string representation, in tight MSB/msb-order,
and converting this using the base64url encoding (see Appendix I.6).
For curve points, the "crv" parameter and the parameters referenced
with the applicable key type-specific settings above MUST 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
and the applicable key type-specific parameters of the corresponding
public-key are RECOMMENDED to be present.
10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE
FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and
can be instantiated with suitable combinations of elliptic curves in
short-Weierstrass form and hash functions (that satisfy particular
cryptographic criteria). While this completely specifies the
internal workings of the signing and signature verification
operations, this does not uniquely specify the input/output formats:
a. 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 of the curve in question;
b. 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 in question.
All inputs and outputs are uniquely determined by specifying the
encodings of the message m, the private key d, the public key Q, the
signature, and the values "valid" and "invalid".
The encodings below specify the use of instantiations of ECDSA with
COSE (see Section 10.2.1) and JOSE (see Section 10.2.2), where the
encoding for a specific ECDSA instantiation (i.e., with a specific
short-Weierstrass curve and specific hash function) results by
setting the "crv" parameter to the unique name of the underlying
curve in question and the "alg" parameter to the unique name of the
specific signature scheme scheme instantiation (e.g., "ECDSA25519"
for the ECDSA scheme defined in Section 4.3 and "ECDSA448" for the
scheme defined in Section 4.4). Note that, in this case, the "alg"
name uniquely defines the curve (and, thereby, implicitly the
underlying "crv" parameter) and the underlying hash function.
10.2.1. Encoding of ECDSA Instantiations with COSE
Instantiations of ECDSA used with COSE use the following encodings of
inputs and outputs:
a. The message m is the COSE_Sign structure as specified in
Section 4.1 of [RFC8152], converted to a bit-string, using the
OS2BS mapping of Appendix I.4;
b. The public key Q and the private key d are encoded as specified
in Section 10.1.1, where the "crv" parameter is set to the unique
name of the curve used with this particular instantiation of
ECDSA;
c. The Cose signature is encoded as the right-concatenation of the
octet string representations of the coordinates of the signature
pair (r, s), in left-to-right order, where r and s are each
represented as octet strings in tight MSB/msb-order using the
ZnE2OS mapping of Appendix I.6, converted to a CBOR byte string.
Note that, since we use a tight representation, this right-
concatenated octet string has fixed size 2*l, where the parameter
l is uniquely defined by the set Z_n in question. The inverse
mapping results by checking that the purported encoded signature
(after CBOR decoding) has indeed size 2*l, and by converting the
left-side and right-side halves of this octet string (each of
length l) to, respectively, the integers r and s in Z_n, via the
strict OS2ZnE mapping of Appendix I.6.
When using a COSE key for this algorithm, if the "alg" field is
present, it MUST be set to the (unique) name of this particular
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.
10.2.2. Encoding of ECDSA Instantiations with JOSE
Instantiations of ECDSA used with JOSE use the following encodings of
inputs and outputs:
a. The message m is the JWS Signing Input as specified in [RFC7515],
converted to a bit-string, using the OS2BS mapping of
Appendix I.4;
b. The public key and the private key are encoded as specified in
Section 10.1.2, where the "crv" parameter is set to the unique
name of the curve used with this particular instantiation of
ECDSA;
c. The JWS signature is encoded as the right-concatenation of the
octet string representations of the coordinates of the signature
pair (r, s), in left-to-right order, where r and s are each
represented in tight MSB/msb-order (see Appendix I.7), converted
using the base64url encoding. Note that, since we use a tight
representation, this right-concatenated octet string has fixed
size 2*l, where the parameter l is uniquely defined by the set
Z_n in question. The inverse mapping results by checking that
the purported encoded signature (after base64url decoding) has
indeed size 2*l, and by converting the left-side and right-side
halves of this octet string (each of length l) to, respectively,
the integers r and s in Z_n, via the strict OS2ZnE mapping of
Appendix I.6.
When using a JOSE key for this algorithm, if the "alg" field is
present, it MUST be set to the (unique) name of this particular
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; if the
JWK _use_ field is present, its value MUST be "sig".
10.3. Using ECDH25519 and ECDH448 with COSE and JOSE
NIST SP 800-56a [SP-800-56a] specifies the co-factor elliptic-curve
Diffie-Hellman key agreement scheme (co-factor ECDH) and can be
instantiated with a suitable elliptic curve in short-Weierstrass form
(that satisfies particular cryptographic criteria). While this
completely specifies the internal workings of the key agreement
scheme in question, this does not uniquely specify the input/output
formats:
a. The co-factor ECDH scheme is a two-party key agreement scheme
that takes as inputs a private key d from one of the parties and
a point Q' obtained from the other party and produces a shared
key K:=h*(d*Q'), where h and n are, respectively, the co-factor
and the order of the base point of the curve in question and
where Q' is a point of this curve. If this shared key K is the
point at infinity O of the curve, the output is an error message;
b. If the shared key K is an affine point of the curve, the output
is the (raw) shared secret Z, which is the octet representation
of the x-coordinate of K, using the FE2OS mapping of
Appendix I.5, represented in tight-MSB/msb-order (see
Appendix I.7).
(NOTE: A subsequent key derivation function (kdf) takes as inputs
the shared secret Z and side information OtherInfo and produces
as output an octet string of DerivedKeyingMaterial, where details
depend on the used kdf in question. This step is out of scope.)
The inputs and outputs are uniquely determined by specifying the
encodings of private keys, curve points, and the error message for
this key agreement scheme.
The encodings below specify the use of instantiations of ECDH with
COSE (see Section 10.3.1) and JOSE (see Section 10.3.2), where the
encoding for a specific co-factor ECDH instantiation (i.e., with a
specific short-Weierstrass curve) results by setting the "crv"
parameter to the unique name of the underlying curve in question and
the "alg" parameter to the unique name of the specific key agreement
scheme instantiation (e.g., "ECDH25519" for the co-factor ECDH scheme
defined in Section 4.1 and "ECDH448" for the scheme defined in
Section 4.4). Note that, in this case, the "alg" name uniquely
defines the curve (and, thereby, implicitly the underlying "crv"
parameter).
10.3.1. Encoding of co-factor ECDH with COSE
Instantiations of co-factor ECDH used with COSE use the following
encodings of inputs and outputs:
a. Curve points and private keys are encoded as specified in
Section 10.1.1, where the "crv" parameter is set to the unique
name of the curve used with this particular instantiation of
ECDH.
When using a COSE key for this algorithm, if the "alg" field is
present, it MUST be set to the (unique) name of this particular
instantiation of co-factor ECDH 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 "key agreement" when creating an
ECDH shared secret.
10.3.2. Encoding of co-factor ECDH with JOSE
Instantiations of co-factor ECDH used with JOSE use the following
encodings of inputs and outputs:
a. Curve points and private keys are encoded as specified in
Section 10.1.2, where the "crv" parameter is set to the unique
name of the curve used with this particular instantiation of
ECDH.
When using a JOSE key for this algorith, if the "alg" field is
present, it MUST be set to the (unique) name of this particular
instantiation of co-factor ECDH 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 "key agreement" when creating an
ECDH shared secret.
11. IANA Considerations
Code points are requested for curves Wei25519 and Wei448 and their
use with ECDSA and co-factor ECDH, using the representation
conventions of this document.
New code points would be required in case one wishes to specify one New code points would be required in case one wishes to specify one
or more other "offspring" protocols beyond those exemplified in or more other "offspring" protocols beyond those exemplified in
Section 4.4. Specification hereof is, however, outside scope of the Section 4.4. Specification hereof is, however, outside scope of the
current document. current document.
10.1. IANA Considerations for Wei25519 11.1. IANA Considerations for Wei25519
10.1.1. COSE Elliptic Curves Registration
11.1.1. COSE Elliptic Curves Registration
This section registers the following value in the IANA "COSE Elliptic This section registers the following value in the IANA "COSE Elliptic
Curves" registry [IANA.COSE.Curves]. Curves" registry [IANA.COSE.Curves].
Name: Wei25519; Name: Wei25519;
Value: TBD (Requested value: -1); Value: TBD (Requested value: -1);
Key Type: EC2 or OKP (where OKP uses the squeezed MSB/msb Key Type: EC2 or OKP;
representation of this specification);
Description: short-Weierstrass curve Wei25519; Description: short-Weierstrass curve Wei25519;
Change Controller: IESG; Change Controller: IESG;
Reference: Appendix E.3 of this specification; Reference: specified in Appendix E.3 of this specification; for
encodings, see Section 10.1;
Recommended: Yes. Recommended: Yes.
(Note that The "kty" value for Wei25519 may be "OKP" or "EC2".) (Note that The "kty" value for Wei25519 may be "EC2" or "OKP".)
10.1.2. COSE Algorithms Registration (1/2) 11.1.2. COSE Algorithms Registration (1/2)
This section registers the following value in the IANA "COSE This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms]. Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDSA25519; Name: ECDSA25519;
Value: TBD (Requested value: -1); Value: TBD (Requested value: -1);
Description: ECDSA with SHA-256 and curve Wei25519; Description: ECDSA with SHA-256 and curve Wei25519;
Change Controller: IESG; Change Controller: IESG;
Reference: Section 4.3 of this specification; Reference: specified in Section 4.3 of this specification; for
encodings, see Section 10.2;
Recommended: Yes. Recommended: Yes.
10.1.3. COSE Algorithms Registration (2/2) 11.1.3. COSE Algorithms Registration (2/2)
This section registers the following value in the IANA "COSE This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms]. Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDH25519; Name: ECDH25519;
Value: TBD (Requested value: -2); Value: TBD (Requested value: -2);
Description: NIST-compliant co-factor Diffie-Hellman w/ curve Description: NIST-compliant co-factor Diffie-Hellman w/ curve
Wei25519 and key derivation function HKDF SHA256; Wei25519 and key derivation function HKDF SHA256;
Change Controller: IESG; Change Controller: IESG;
Reference: Section 4.1 of this specification (for key derivation, Reference: defined in Section 4.1 of this specification; for
see Section 11.1 of [RFC8152]); encodings, see Section 10.3;
Recommended: Yes. Recommended: Yes.
10.1.4. JOSE Elliptic Curves Registration 11.1.4. JOSE Elliptic Curves Registration
This section registers the following value in the IANA "JSON Web Key This section registers the following value in the IANA "JSON Web Key
Elliptic Curve" registry [IANA.JOSE.Curves]. Elliptic Curve" registry [IANA.JOSE.Curves].
Curve Name: Wei25519; Curve Name: Wei25519;
Curve Description: short-Weierstrass curve Wei25519; Curve Description: short-Weierstrass curve Wei25519;
JOSE Implementation Requirements: Optional; JOSE Implementation Requirements: Optional;
Change Controller: IESG; Change Controller: IESG;
Reference: Appendix E.3 of this specification. Reference: specified in Appendix E.3 of this specification; for
encodings, see Section 10.1.
10.1.5. JOSE Algorithms Registration (1/2) (Note that The "kty" value for Wei25519 may be "EC" or "OKP".)
11.1.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: Section 4.3 of this specification; Reference: specified in Section 4.3 of this specification; for
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.
10.1.6. JOSE Algorithms Registration (2/2) 11.1.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: Section 4.1 of this specification (for key derivation, Reference: Section 4.1 of this specification; for encodings, see
see Section 5 of [SP-800-56c]); Section 10.1;
Algorithm Analysis Document(s): Section 4.1 of this specification Algorithm Analysis Document(s): Section 4.1 of this specification.
(for key derivation, see Section 5 of [SP-800-56c]).
10.2. IANA Considerations for Wei448 11.2. IANA Considerations for Wei448
10.2.1. COSE Elliptic Curves Registration 11.2.1. COSE Elliptic Curves Registration
This section registers the following value in the IANA "COSE Elliptic This section registers the following value in the IANA "COSE Elliptic
Curves" registry [IANA.COSE.Curves]. Curves" registry [IANA.COSE.Curves].
Name: Wei448; Name: Wei448;
Value: TBD (Requested value: -2); Value: TBD (Requested value: -2);
Key Type: EC2 or OKP (where OKP uses the squeezed MSB/msb Key Type: EC2 or OKP;
representation of this specification);
Description: short-Weierstrass curve Wei448; Description: short-Weierstrass curve Wei448;
Change Controller: IESG; Change Controller: IESG;
Reference: Appendix M.3 of this specification; Reference: specified in Appendix M.3 of this specification; for
encodings, see Section 10.1;
Recommended: Yes. Recommended: Yes.
(Note that The "kty" value for Wei448 may be "OKP" or "EC2".) (Note that The "kty" value for Wei448 may be "EC2" or "OKP".)
10.2.2. COSE Algorithms Registration (1/2) 11.2.2. COSE Algorithms Registration (1/2)
This section registers the following value in the IANA "COSE This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms]. Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDSA448; Name: ECDSA448;
Value: TBD (Requested value: -21); Value: TBD (Requested value: -47);
Description: ECDSA with SHAKE256 and curve Wei448; Description: ECDSA with SHAKE256 and curve Wei448;
Change Controller: IESG; Change Controller: IESG;
Reference: Section 4.4 of this specification; Reference: Section 4.4 of this specification;
Recommended: Yes. Recommended: Yes.
10.2.3. COSE Algorithms Registration (2/2) 11.2.3. COSE Algorithms Registration (2/2)
This section registers the following value in the IANA "COSE This section registers the following value in the IANA "COSE
Algorithms" registry [IANA.COSE.Algorithms]. Algorithms" registry [IANA.COSE.Algorithms].
Name: ECDH448; Name: ECDH448;
Value: TBD (Requested value: -48);
Value: TBD (Requested value: -22); Description: NIST-compliant co-factor Diffie-Hellman w/ curve Wei448
and key derivation function HKDF SHA512;
Description: NIST-compliant co-factor Diffie-Hellman w/ curve
Wei25519 and key derivation function HKDF SHA512;
Change Controller: IESG; Change Controller: IESG;
Reference: Section 4.4 of this specification (for key derivation, Reference: Section 4.4 of this specification (for key derivation,
see Section 11.1 of [RFC8152]); see Section 11.1 of [RFC8152]);
Recommended: Yes. Recommended: Yes.
10.2.4. JOSE Elliptic Curves Registration 11.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: 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: Appendix M.3 of this specification.
10.2.5. JOSE Algorithms Registration (1/2) Reference: specified in Appendix M.3 of this specification; for
encodings, see Section 10.1.
(Note that The "kty" value for Wei448 may be "EC" or "OKP".)
11.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: 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: Section 4.4 of this specification; Reference: specified in Section 4.4 of this specification; for
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.
10.2.6. JOSE Algorithms Registration (2/2) 11.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: ECDH448; Algorithm Name: ECDH448;
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 SHA512; 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: Section 4.4 of this specification (for key derivation, Reference: specified in Section 4.4 of this specification; for
see Section 5 of [SP-800-56c]); encodings, see Section 10.3
Algorithm Analysis Document(s): Section 4.4 of this specification Algorithm Analysis Document(s): Section 4.4 of this specification.
(for key derivation, see Section 5 of [SP-800-56c]).
11. Acknowledgements 12. Acknowledgements
Thanks to Nikolas Rosener for discussions surrounding implementation Thanks to Nikolas Rosener for discussions surrounding implementation
details of the techniques described in this document and to Phillip details of the techniques described in this document and to Phillip
Hallam-Baker for triggering inclusion of verbiage on the use of Hallam-Baker for triggering inclusion of verbiage on the use of
Montgomery ladders with recovery of the y-coordinate. Thanks to Montgomery ladders with recovery of the y-coordinate. Thanks to
Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews. Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews.
12. References 13. References
12.1. Normative References 13.1. Normative References
[ANSI-X9.62] [ANSI-X9.62]
ANSI X9.62-2005, "Public Key Cryptography for the ANSI X9.62-2005, "Public Key Cryptography for the
Financial Services Industry: The Elliptic Curve Digital Financial Services Industry: The Elliptic Curve Digital
Signature Algorithm (ECDSA)", American National Standard Signature Algorithm (ECDSA)", American National Standard
for Financial Services, Accredited Standards Committee X9, for Financial Services, Accredited Standards Committee X9,
Inc, Anapolis, MD, 2005. Inc, Anapolis, MD, 2005.
[FIPS-180-4] [FIPS-180-4]
FIPS 180-4, "Secure Hash Standard (SHS), Federal FIPS 180-4, "Secure Hash Standard (SHS), Federal
skipping to change at page 19, line 37 skipping to change at page 26, line 18
Department of Commerce/National Institute of Standards and Department of Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, July 2013. Technology, Gaithersburg, MD, July 2013.
[FIPS-202] [FIPS-202]
FIPS 202, "SHA-3 Standard: Permutation-Based Hash and FIPS 202, "SHA-3 Standard: Permutation-Based Hash and
Extendable-Output Functions, Federal Information Extendable-Output Functions, Federal Information
Processing Standards Publication 202", US Department of Processing Standards Publication 202", US Department of
Commerce/National Institute of Standards and Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, August 2015. Technology, Gaithersburg, MD, August 2015.
[I-D.ietf-cose-rfc8152bis-algs]
Schaad, J., "CBOR Object Signing and Encryption (COSE):
Initial Algorithms", draft-ietf-cose-rfc8152bis-algs-07
(work in progress), March 2020.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data
Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006,
<https://www.rfc-editor.org/info/rfc4648>.
[RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography [RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography
(ECC) Brainpool Standard Curves and Curve Generation", (ECC) Brainpool Standard Curves and Curve Generation",
RFC 5639, DOI 10.17487/RFC5639, March 2010, RFC 5639, DOI 10.17487/RFC5639, March 2010,
<https://www.rfc-editor.org/info/rfc5639>. <https://www.rfc-editor.org/info/rfc5639>.
[RFC7049] Bormann, C. and P. Hoffman, "Concise Binary Object
Representation (CBOR)", RFC 7049, DOI 10.17487/RFC7049,
October 2013, <https://www.rfc-editor.org/info/rfc7049>.
[RFC7515] Jones, M., Bradley, J., and N. Sakimura, "JSON Web
Signature (JWS)", RFC 7515, DOI 10.17487/RFC7515, May
2015, <https://www.rfc-editor.org/info/rfc7515>.
[RFC7518] Jones, M., "JSON Web Algorithms (JWA)", RFC 7518,
DOI 10.17487/RFC7518, May 2015,
<https://www.rfc-editor.org/info/rfc7518>.
[RFC7696] Housley, R., "Guidelines for Cryptographic Algorithm [RFC7696] Housley, R., "Guidelines for Cryptographic Algorithm
Agility and Selecting Mandatory-to-Implement Algorithms", Agility and Selecting Mandatory-to-Implement Algorithms",
BCP 201, RFC 7696, DOI 10.17487/RFC7696, November 2015, BCP 201, RFC 7696, DOI 10.17487/RFC7696, November 2015,
<https://www.rfc-editor.org/info/rfc7696>. <https://www.rfc-editor.org/info/rfc7696>.
[RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
for Security", RFC 7748, DOI 10.17487/RFC7748, January for Security", RFC 7748, DOI 10.17487/RFC7748, January
2016, <https://www.rfc-editor.org/info/rfc7748>. 2016, <https://www.rfc-editor.org/info/rfc7748>.
[RFC7942] Sheffer, Y. and A. Farrel, "Improving Awareness of Running [RFC7942] Sheffer, Y. and A. Farrel, "Improving Awareness of Running
Code: The Implementation Status Section", BCP 205, Code: The Implementation Status Section", BCP 205,
RFC 7942, DOI 10.17487/RFC7942, July 2016, RFC 7942, DOI 10.17487/RFC7942, July 2016,
<https://www.rfc-editor.org/info/rfc7942>. <https://www.rfc-editor.org/info/rfc7942>.
[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
Signature Algorithm (EdDSA)", RFC 8032, Signature Algorithm (EdDSA)", RFC 8032,
DOI 10.17487/RFC8032, January 2017, DOI 10.17487/RFC8032, January 2017,
<https://www.rfc-editor.org/info/rfc8032>. <https://www.rfc-editor.org/info/rfc8032>.
[RFC8037] Liusvaara, I., "CFRG Elliptic Curve Diffie-Hellman (ECDH)
and Signatures in JSON Object Signing and Encryption
(JOSE)", RFC 8037, DOI 10.17487/RFC8037, January 2017,
<https://www.rfc-editor.org/info/rfc8037>.
[RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)", [RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)",
RFC 8152, DOI 10.17487/RFC8152, July 2017, RFC 8152, DOI 10.17487/RFC8152, July 2017,
<https://www.rfc-editor.org/info/rfc8152>. <https://www.rfc-editor.org/info/rfc8152>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>. May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0", [SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0",
Standards for Efficient Cryptography, , June 2009. Standards for Efficient Cryptography, , June 2009.
skipping to change at page 20, line 45 skipping to change at page 28, line 5
Establishment Schemes Using Discrete Log Cryptography, Establishment Schemes Using Discrete Log Cryptography,
Revision 3", US Department of Commerce/National Institute Revision 3", US Department of Commerce/National Institute
of Standards and Technology, Gaithersburg, MD, April 2018. of Standards and Technology, Gaithersburg, MD, April 2018.
[SP-800-56c] [SP-800-56c]
NIST SP 800-56c, "Recommendation for Key-Derivation NIST SP 800-56c, "Recommendation for Key-Derivation
Methods in Key-Establishment Schemes, Revision 1", US Methods in Key-Establishment Schemes, Revision 1", US
Department of Commerce/National Institute of Standards and Department of Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, April 2018. Technology, Gaithersburg, MD, April 2018.
12.2. Informative References 13.2. Informative References
[ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in [ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in
Cryptography", Cambridge University Press, Lecture Notes Cryptography", Cambridge University Press, Lecture Notes
Series 265, July 1999. Series 265, July 1999.
[ECC-Isogeny] [ECC-Isogeny]
E. Brier, M. Joye, "Fast Point Multiplication on Elliptic E. Brier, M. Joye, "Fast Point Multiplication on Elliptic
Curves through Isogenies", AAECC, Lecture Notes in Curves through Isogenies", AAECC, Lecture Notes in
Computer Science, Vol. 2643, New York: Springer-Verlag, Computer Science, Vol. 2643, New York: Springer-Verlag,
2003. 2003.
skipping to change at page 31, line 41 skipping to change at page 38, line 41
This curve has the same group structure as (is "isomorphic" to) the This curve has the same group structure as (is "isomorphic" to) the
twisted Edwards curve E_{a,d} defined over GF(p), with as base point twisted Edwards curve E_{a,d} defined over GF(p), with as base point
the point (Gx, Gy), where parameters are as specified in the point (Gx, Gy), where parameters are as specified in
Appendix E.3. This curve is denoted as Edwards25519. For this Appendix E.3. This curve is denoted as Edwards25519. For this
curve, the parameter a is a square in GF(p), whereas d is not, so the curve, the parameter a is a square in GF(p), whereas d is not, so the
group laws of Appendix C.3 apply. group laws of Appendix C.3 apply.
The curve is also isomorphic to the elliptic curve W_{a,b} in short- The curve is also isomorphic to the elliptic curve W_{a,b} in short-
Weierstrass form defined over GF(p), with as base point the point Weierstrass form defined over GF(p), with as base point the point
(GX, GY), where parameters are as specified in Appendix E.3. This (GX, GY), where parameters are as specified in Appendix E.3. This
curve is denoted as Wei25519. curve is denoted as Wei25519. For this curve, the parameter b is a
square in GF(p). (For future reference, we note that this curve has
no affine points with x-coordinate -1.)
E.2. Switching between Alternative Representations E.2. Switching between Alternative Representations
Each affine point (u, v) of Curve25519 corresponds to the point (X, Each affine point (u, v) of Curve25519 corresponds to the point (X,
Y):=(u + A/3, v) of Wei25519, while the point at infinity of Y):=(u + A/3, v) of Wei25519, while the point at infinity of
Curve25519 corresponds to the point at infinity of Wei25519. (Here, Curve25519 corresponds to the point at infinity of Wei25519. (Here,
we used the mappings of Appendix D.2 and that B=1.) Under this we used the mappings of Appendix D.2 and that B=1.) Under this
mapping, the base point (Gu, Gv) of Curve25519 corresponds to the mapping, the base point (Gu, Gv) of Curve25519 corresponds to the
base point (GX, GY) of Wei25519. The inverse mapping maps the affine base point (GX, GY) of Wei25519. The inverse mapping maps the affine
point (X, Y) of Wei25519 to (u, v):=(X - A/3, Y) of Curve25519, while point (X, Y) of Wei25519 to (u, v):=(X - A/3, Y) of Curve25519, while
skipping to change at page 54, line 41 skipping to change at page 61, line 41
[1,p-1] and have odd sum p. Consequently, one can distinguish y from [1,p-1] and have odd sum p. Consequently, one can distinguish y from
-y via the parity of this representation, i.e., via par(y):=y (mod -y via the parity of this representation, i.e., via par(y):=y (mod
2). If q:=p^m, where p is an odd prime number and where m>0, both y 2). If q:=p^m, where p is an odd prime number and where m>0, both y
and -y can be uniquely represented as vectors of length m, with and -y can be uniquely represented as vectors of length m, with
coefficients in GF(p) (see Appendix B.2). In this case, the leftmost coefficients in GF(p) (see Appendix B.2). In this case, the leftmost
nonzero coordinate values of y and -y are in the same position and nonzero coordinate values of y and -y are in the same position and
have representations in [1,p-1] with different parity. As a result, have representations in [1,p-1] with different parity. As a result,
one can distinguish y from -y via the parity of the representation of one can distinguish y from -y via the parity of the representation of
this coordinate value. This extends the definition of the parity this coordinate value. This extends the definition of the parity
function to any odd-size field GF(q), where one defines par(0):=0. function to any odd-size field GF(q), where one defines par(0):=0.
The value of the parity function is commonly called the parity bit.
H.1. Point Compression for Weierstrass Curves H.1. Point Compression for Weierstrass Curves
If P:=(X, Y) is an affine point of the Weierstrass curve W_{a,b} If P:=(X, Y) is an affine point of the Weierstrass curve W_{a,b}
defined over the field GF(q), then so is -P:=(X, -Y). Since the defined over the field GF(q), then so is -P:=(X, -Y). Since the
defining equation Y^2=X^2+a*X+b has at most two solutions with fixed defining equation Y^2=X^2+a*X+b has at most two solutions with fixed
X-value, one can represent P by its X-coordinate and one bit of X-value, one can represent P by its X-coordinate and one bit of
information that allows one to distinguish P from -P, i.e., one can information that allows one to distinguish P from -P, i.e., one can
represent P as the ordered pair compr(P):=(X, par(Y)). If P is a represent P as the ordered pair compr(P):=(X, par(Y)). If P is a
point of order two, one can uniquely represent P by its X-coordinate point of order two, one can uniquely represent P by its X-coordinate
skipping to change at page 57, line 9 skipping to change at page 64, line 10
include a special marker element 'btm', by associating this marker include a special marker element 'btm', by associating this marker
element with the ordered pair compr(btm):=(1,1) and recover this element with the ordered pair compr(btm):=(1,1) and recover this
marker element accordingly. (Note that this corresponds to the case marker element accordingly. (Note that this corresponds to the case
alpha=0 and t=1 above.) The marker element 'btm' can be represented alpha=0 and t=1 above.) The marker element 'btm' can be represented
by the ordered pair (1,1) of elements of GF(q). Note that this by the ordered pair (1,1) of elements of GF(q). Note that this
ordered pair does not satisfy the defining equation of the curve in ordered pair does not satisfy the defining equation of the curve in
question. question.
Appendix I. Data Conversions Appendix I. Data Conversions
This section introduces various data conversion routines that are
useful when representing integers, finite field elements, and curve
points as binary or octet strings.
I.1. Strings and String Operations
The string over some alphabet S consisting of the symbols x_{l-1}, The string over some alphabet S consisting of the symbols x_{l-1},
x_{l-2}, ..., x_1, x_0 (each in S), in this order, is denoted by x_{l-2}, ..., x_1, x_0 (each in S), in this order, is denoted by
str(x_{l-1}, x_{l-2}, ..., x_1, x_0). The length of this string str(x_{l-1}, x_{l-2}, ..., x_1, x_0). The length of this string
(over S) is the number of symbols it contains (here: l). The empty (over S) is the number of symbols it contains (here: l). The empty
string is the (unique) string of length l=0. string is the (unique) string of length l=0.
The right-concatenation of two strings X and Y (defined over the same The right-concatenation of two strings X and Y (defined over the same
alphabet) is the string Z consisting of the symbols of X (in the same alphabet) is the string Z consisting of the symbols of X (in the same
order) followed by the symbols of Y (in the same order). The length order) followed by the symbols of Y (in the same order). The length
of the resulting string Z is the sum of the lengths of X and Y. This of the resulting string Z is the sum of the lengths of X and Y. This
skipping to change at page 57, line 32 skipping to change at page 64, line 39
postfix Y of length t (where in both cases t is an integer in the postfix Y of length t (where in both cases t is an integer in the
interval [0,l]). One can define these notions as well if t is interval [0,l]). One can define these notions as well if t is
outside the interval [0,l] by stipulating that a t-prefix or outside the interval [0,l] by stipulating that a t-prefix or
t-postfix is the empty string if t is negative and that it is the t-postfix is the empty string if t is negative and that it is the
entire string Z if t is larger than l. Sometimes, a t-prefix of a entire string Z if t is larger than l. Sometimes, a t-prefix of a
string Z is denoted by trunc-left(Z,t); a t-postfix by trunc- string Z is denoted by trunc-left(Z,t); a t-postfix by trunc-
right(Z,t). A string X is called a substring of Z if it is a prefix right(Z,t). A string X is called a substring of Z if it is a prefix
of some postfix of Z. The string resulting from prepending the of some postfix of Z. The string resulting from prepending the
string Y with X is the string X||Y. string Y with X is the string X||Y.
An octet is an integer in the interval [0,256). An octet string is a An octet (or byte) is an integer in the interval [0,256). An octet
string, where the alphabet is the set of all octets. A binary string string is a string, where the alphabet is the set of all octets. A
(or bit string, for short) is a string, where the alphabet is the set binary string (or bit string, for short) is a string, where the
{0,1}. Note that the length of a string is defined in terms of the alphabet is the set {0,1} of binary digits. Note that the length of
underlying alphabet, as are the operations in the previous paragraph. a string is defined in terms of the underlying alphabet, as are the
operations in the previous paragraph.
I.1. Conversion between Bit Strings and Integers (BS2I, I2BS) I.2. Conversion between Bit Strings and Integers (BS2I, I2BS)
There is a 1-1 correspondence between bit strings of length l and There is a 1-1 correspondence between bit strings of length l and
integers in the interval [0, 2^l), where the bit string integers in the interval [0, 2^l), where the bit string
X:=str(x_{l-1}, x_{l-2}, ..., x_1, x_0) corresponds to the integer X:=str(x_{l-1}, x_{l-2}, ..., x_1, x_0) corresponds to the integer
x:=x_{l-1}*2^{l-1} + x_{l-2}*2^{l-2} + ... + x_1*2 + x_0*1. (If l=0, x:=x_{l-1}*2^{l-1} + x_{l-2}*2^{l-2} + ... + x_1*2 + x_0*1. (If l=0,
the empty bit string corresponds to the integer zero.) Note that the empty bit string corresponds to the integer zero.) Note that
while the mapping from bit strings to integers is uniquely defined, while the mapping from bit strings to integers is uniquely defined,
the inverse mapping from integers to bit strings is not, since any the inverse mapping from integers to bit strings is not, since any
non-negative integer smaller than 2^t can be represented as a bit non-negative integer smaller than 2^t can be represented as a bit
string of length at least t (due to leading zero coefficients in base string of length at least t (due to leading zero coefficients in base
2 representation). The latter representation is called tight if the 2 representation). The latter representation is called tight if the
bit string representation has minimal length. This defines the bit string representation has minimal length. This defines the
mapping BS2I from bit strings to integers and the mapping I2BS(x,l) mapping BS2I from bit strings to integers and the mapping I2BS(x,l)
from non-negative integers smaller than 2^l to bit strings of length from non-negative integers smaller than 2^l to bit strings of length
l. l.
I.2. Conversion between Octet Strings and Integers (OS2I, I2OS) I.3. Conversion between Octet Strings and Integers (OS2I, I2OS)
There is a 1-1 correspondence between octet strings of length l and There is a 1-1 correspondence between octet strings of length l and
integers in the interval [0, 256^l), where the octet string integers in the interval [0, 256^l), where the octet string
X:=str(X_{l-1}, X_{l-2}, ..., X_1, X_0) corresponds to the integer X:=str(X_{l-1}, X_{l-2}, ..., X_1, X_0) corresponds to the integer
x:=X_{l-1}*256^{l-1} + X^{l-2}*256^{l-2} + ... + X_1*256 + X_0*1. x:=X_{l-1}*256^{l-1} + X^{l-2}*256^{l-2} + ... + X_1*256 + X_0*1.
(If l=0, the empty string corresponds to the integer zero.) Note (If l=0, the empty string corresponds to the integer zero.) Note
that while the mapping from octet strings to integers is uniquely that while the mapping from octet strings to integers is uniquely
defined, the inverse mapping from integers to octet strings is not, defined, the inverse mapping from integers to octet strings is not,
since any non-negative integer smaller than 256^t can be represented since any non-negative integer smaller than 256^t can be represented
as an octet string of length at least t (due to leading zero as an octet string of length at least t (due to leading zero
coefficients in base 256 representation). The latter representation coefficients in base 256 representation). The latter representation
is called tight if the octet string representation has minimal is called tight if the octet string representation has minimal
length. This defines the mapping OS2I from octet strings to integers length. This defines the mapping OS2I from octet strings to integers
and the mapping I2OS(x,l) from non-negative integers smaller than and the mapping I2OS(x,l) from non-negative integers smaller than
256^l to octet strings of length l. 256^l to octet strings of length l.
I.3. Conversion between Octet Strings and Bit Strings (OS2BS, BS2OS) I.4. Conversion between Octet Strings and Bit Strings (OS2BS, BS2OS)
There is a 1-1 correspondence between octet strings of length l and There is a 1-1 correspondence between octet strings of length l and
bit strings of length 8*l, where the octet string X:=str(X_{l-1}, bit strings of length 8*l, where the octet string X:=str(X_{l-1},
X_{l-2}, ..., X_1, X_0) corresponds to the right-concatenation of the X_{l-2}, ..., X_1, X_0) corresponds to the right-concatenation of the
8-bit strings x_{l-1}, x_{l-2}, ..., x_1, x_0, where each octet X_i 8-bit strings x_{l-1}, x_{l-2}, ..., x_1, x_0, where each octet X_i
corresponds to the 8-bit string x_i according to the mapping of corresponds to the 8-bit string x_i according to the mapping of
Appendix I.1 above. Note that the mapping from octet strings to bit Appendix I.2 above. Note that the mapping from octet strings to bit
strings is uniquely defined and so is the inverse mapping from bit strings is uniquely defined and so is the inverse mapping from bit
strings to octet strings, if one prepends each bit string with the strings to octet strings, if one prepends each bit string with the
smallest number of 0 bits so as to result in a bit string of length smallest number of 0 bits so as to result in a bit string of length
divisible by eight (i.e., one uses pre-padding). This defines the divisible by eight (i.e., one uses pre-padding). This defines the
mapping OS2BS from octet strings to bit strings and the corresponding mapping OS2BS from octet strings to bit strings and the corresponding
mapping BS2OS from bit strings to octet strings. mapping BS2OS from bit strings to octet strings. When we refer to a
specific bit position in an octet string, this indicates the
corresponding position, when this octet string is viewed as a bit
string using the OS2BS mapping above.
I.4. Conversion between Field Elements and Octet Strings (FE2OS, OS2FE) I.5. Conversion between Field Elements and Octet Strings (FE2OS, OS2FE)
There is a 1-1 correspondence between elements of the fixed finite There is a 1-1 correspondence between elements of the fixed finite
field GF(q), where q:=p^m, where p is a prime number and where m>0, field GF(q), where q:=p^m, where p is a prime number and where m>0,
and vectors of length m, with coefficients in GF(p), where each and vectors of length m, with coefficients in GF(p), where each
element x of GF(q) is a vector (x_{m-1}, x_{m-2}, ..., x_1, x_0) element x of GF(q) is a vector (x_{m-1}, x_{m-2}, ..., x_1, x_0)
according to the conventions of Appendix B.2. In this case, this according to the conventions of Appendix B.2. In this case, this
field element can be uniquely represented by the right-concatenation field element can be uniquely represented by the right-concatenation
of the octet strings X_{m-1}, X_{m-2}, ..., X_1, X_0, where each of the octet strings X_{m-1}, X_{m-2}, ..., X_1, X_0, where each
octet string X_i corresponds to the integer x_i in the interval octet string X_i corresponds to the integer x_i in the interval
[0,p-1] according to the mapping of Appendix I.2 above. Note that [0,p-1] according to the mapping of Appendix I.3 above. Note that
both the mapping from field elements to octet strings and the inverse both the mapping from field elements to octet strings and the inverse
mapping from octet strings to field elements are only uniquely mapping from octet strings to field elements are only uniquely
defined if each octet string X_i has the same fixed size (e.g., the defined if each octet string X_i has the same fixed size (e.g., the
smallest integer l so that 256^l >= p) and if all integers are smallest integer l so that 256^l >= p) and if all integers are
reduced modulo p. If so, the latter representation is called tight reduced modulo p. If so, the latter representation is called tight
if l is minimal so that 256^l >= p. This defines the mapping if l is minimal so that 256^l >= p. This defines the mapping
FE2OS(x,l) from field elements to octet strings and the mapping FE2OS(x,l) from field elements to octet strings and the mapping
OS2FE(X,l) from octet strings to field elements, where the underlying OS2FE(X,l) from octet strings to field elements, where the underlying
field is implicit and assumed to be known from context. In this field is implicit and assumed to be known from context. In this
case, the octet string has length l*m. (Observe that with tight case, the octet string has length l*m. (Observe that with tight
representations, the parameter l is uniquely defined by the representations, the parameter l is uniquely defined by the
characteristic p of the field GF(q) in question.) characteristic p of the field GF(q) in question.) The OS2FE(X,l)
mapping is called strict if it operates as the OS2FE(X,l) function,
except that it fails whenever it would require at least one modular
reduction. Notice that the tight FE2OS mapping followed by the
strict OS2FE mapping is the identity map (and, hence, OS2FE never
fails in this case).
I.5. Conversion between Elements of Z mod n and Octet Strings (ZnE2OS, I.6. Conversion between Elements of Z mod n and Octet Strings (ZnE2OS,
OS2ZnE) OS2ZnE)
There is a 1-1 correspondence between elements of the set Z_n of There is a 1-1 correspondence between elements of the set Z_n of
integers modulo n and integers in the interval [0,n), where each integers modulo n and integers in the interval [0,n), where each
element x of Z_n is uniquely represented by the integer x mod n. In element x of Z_n is uniquely represented by the integer x mod n. In
this case, x mod n can be uniquely represented by the octet string X this case, x mod n can be uniquely represented by the octet string X
according to the mapping of Appendix I.2 above. Note that both the according to the mapping of Appendix I.3 above. Note that both the
mapping from elements of Z_n to octet strings and the inverse mapping mapping from elements of Z_n to octet strings and the inverse mapping
from octet strings to elements of Z_n are only uniquely defined if from octet strings to elements of Z_n are only uniquely defined if
the octet string has a fixed size (e.g., the smallest integer l so the octet string has a fixed size (e.g., the smallest integer l so
that 256^l >= n) and if all integers are first reduced modulo n. If that 256^l >= n) and if all integers are first reduced modulo n. If
so, the latter representation is called tight if l is minimal so that so, the latter representation is called tight if l is minimal so that
256^l >= n. This defines the mapping ZnE2OS(x,l) from elements of 256^l >= n. This defines the mapping ZnE2OS(x,l) from elements of
Z_n to octet strings and the mapping OS2ZnE(X,l) from octet strings Z_n to octet strings and the mapping OS2ZnE(X,l) from octet strings
to elements of Z_n, where the underlying modulus n is implicit and to elements of Z_n, where the underlying modulus n is implicit and
assumed to be known from context. In this case, the octet string has assumed to be known from context. In this case, the octet string has
length l. (Observe that with tight representations, the parameter l length l. (Observe that with tight representations, the parameter l
is uniquely defined by the parameter n in question.) is uniquely defined by the parameter n in question.) The OS2ZnE(X,l)
mapping is called strict if it operates as the OS2ZnE(X,l) function,
except that it fails whenever it would require at least one modular
reduction. Notice that the tight ZnE2OS mapping followed by the
strict OS2ZnE mapping is the identity map (and, hence, ZnE2OS never
fails in this case).
Note that if n is a prime number p, the conversions ZnE2OS and FE2OS Note that if n is a prime number p, the conversions ZnE2OS and FE2OS
are consistent, as are OS2ZnE and OS2FE. This is, however, no longer are consistent, as are OS2ZnE and OS2FE. This is, however, no longer
the case if n is a strict prime power. the case if n is a strict prime power.
The conversion rules for composite n values may be useful, e.g., when The conversion rules for composite n values may be useful, e.g., when
encoding RSA parameters (or elements of any other non-prime size set encoding RSA parameters (or elements of any other non-prime size set
Z_n, for that matter). Z_n, for that matter).
I.6. Ordering Conventions I.7. Ordering Conventions
One can consider various representation functions, depending on bit- One can consider various representation functions, depending on bit-
ordering and octet-ordering conventions. ordering and octet-ordering conventions.
The description below makes use of an auxiliary function (the The description below makes use of an auxiliary function (the
reversion function), which we define both for bit strings and octet reversion function), where the reverse of the string X:=str(x_{l-1},
strings. For a bit string [octet string] X:=str(x_{l-1}, x_{l-2}, x_{l-2}, ..., x_1, x_0) is defined to be the string
..., x_1, x_0), its reverse is the bit string [octet string] X':=rev(X):=str(x_0, x_1, ..., x_{l-2}, x_{l-1}). Below, we use this
X':=rev(X):=str(x_0, x_1, ..., x_{l-2}, x_{l-1}). reversion function with binary and octet strings.
We now describe representations in most-significant-bit first (msb) We now describe representations in most-significant-bit first (msb)
or least-significant-bit first (lsb) order and those in most- or least-significant-bit first (lsb) order and those in most-
significant-byte first (MSB) or least-significant-byte first (LSB) significant-byte first (MSB) or least-significant-byte first (LSB)
order. order.
One distinguishes the following octet-string representations of One distinguishes the following octet-string representations of
integers and field elements: integers and field elements:
1. MSB, msb: represent field elements and integers as above, 1. MSB, msb: represent field elements and integers as above,
skipping to change at page 60, line 41 skipping to change at page 68, line 17
integer 51,168 (0xc7e0) in LSB/lsb order, and the integer 58,119 integer 51,168 (0xc7e0) in LSB/lsb order, and the integer 58,119
(=0xe307) in LSB/msb order. (=0xe307) in LSB/msb order.
Note that, with the above data conversions, there is still some Note that, with the above data conversions, there is still some
ambiguity as to how to represent an integer or a field element as a ambiguity as to how to represent an integer or a field element as a
bit string or octet string (due to leading zeros). However, tight bit string or octet string (due to leading zeros). However, tight
representations (as defined above) are non-ambiguous. (Note, in representations (as defined above) are non-ambiguous. (Note, in
particular, that tightness implies that elements of GF(q) are always particular, that tightness implies that elements of GF(q) are always
uniquely represented.) uniquely represented.)
I.8. Conversion Between Curve Points and Octet Strings
For each of the curve models we consider, each affine point is an
ordered pair (X, Y) whose coordinates are elements of a finite field
GF(q) and that satisfy the defining equation for the curve in
question. Each compressed point is an ordered pair (X,t) (for
Weierstrass curves and Montgomery curves) or (t, X) (for twisted
Edwards curves) where X is an element of GF(q) and where t is an
element of {0,1} (see Appendix H).
The affine point (X, Y) is represented by the ordered pair whose
coordinates are the octet string representations of the elements X
and Y of GF(q), respectively, using the tight FE2OS mapping of
Appendix I.5. Note that, since we use a tight representation, this
results in a pair of octet strings (each of length l*m), where the
parameters l and m are uniquely defined by the field GF(q) in
question. The inverse mapping results by converting the first and
second coordinate of this pair (each an octet string of length l*m)
to, respectively, the elements X and Y of GF(q) via the strict OS2FE
mapping of Appendix I.5. Note that if it is not a priori known
whether the input to this inverse mapping actually represents an
affine curve point, one should check that this is indeed an ordered
pair of octet strings (each of length l*m) and that the output (X,Y)
-- if defined -- is indeed an affine point of the curve in question,
where this mapping fails if either condition is not satisfied.
The compressed point (X,t) or (t, X) is represented by the ordered
pair whose coordinates are the octet string representations of the
parity bit t in {0,1} and the element X of GF(q), respectively, using
the tight FE2OS mapping of Appendix I.5. Note that, since we use
tight representations, this results in an ordered pair of octet
strings (of length 1 and l*m, respectively), where the parameters l
and m are uniquely defined by the field GF(q) in question. The
inverse mapping results by converting the first and second coordinate
of this pair (each an octet string, of length 1 and l*m,
respectively) to, respectively, the element t of {0,1} and the
element X of GF(q) via the strict OS2FE mapping of Appendix I.5, and
representing this as the compressed point (X, t) or (t, X) according
to the curve model in question. Note that if it is not a priori
known whether the input to this inverse mapping actually represents a
compressed curve point, one should check that this is indeed an
ordered pair of octet strings (of length 1 and l*m, respectively) and
that the output (X, t) or (t, X) -- if defined -- is indeed a
compressed point of the curve in question, using the point
decompression process for this curve (see Appendix H), where this
mapping fails if either condition is not satisfied.
NOTE 1: The representations of affine and compressed points above are
as ordered pairs of octet strings. In practice, one often represents
these as octet strings instead, via right-concatenation of its
coordinates (in left-to-right order). Since each coordinate has
known length, this operation is reversible. When appropriate, we
refer to the latter as the octet (rather than the pair)
representation of a point.
NOTE 2: The octet representation of compressed points above
identifies the parity bit t of the curve point in question via the
1-octet representations of the integers 0 and 1. Obviously, other
1-1 mappings are also possible. As an example, with [SEC1], the
parity bit t is represented by 0x02 or 0x03 depending on whether t=0
or t=1, respectively The same [SEC1] specification represents affine
points as above (as octet string), but prepends this with the 1-octet
prefix 0x04, and represents the identity element of the curve as the
1-octet string 0x00. This variable-size point representation has the
property that its 1-octet prefix identifies whether it encodes an
affine curve point, a compressed point (including parity bit), or the
identity element, while the remainder of this representation uniquely
determines the curve point's value. While the description in [SEC1]
only applies to Weierstrass curves, the description above applies to
each of the curve models we consider (i.e., these apply to Montgomery
curves and twisted Edwards curves as well). Collectively, we simply
refer to this as the "SEC1" point representation.
Note that elements of a prime field GF(p), where p is a 255-bit prime Note that elements of a prime field GF(p), where p is a 255-bit prime
number, have a tight representation as a 32-byte string, where a number, have a tight representation as a 32-byte string, where a
fixed bit position is always set to zero. (This is the leftmost bit fixed bit position is always set to zero. (This is the leftmost bit
position of this octet string if one follows the MSB/msb position of this octet string if one follows the MSB/msb
representation conventions.) This allows the parity bit of a representation conventions.) This allows the parity bit of a
compressed point (see Appendix H) to be encoded in this bit position compressed point (see Appendix H) to be encoded in this bit position
and, thereby, allows a compressed point and a field element of GF(p) and, thereby, allows a compressed point and an element of GF(p) to be
to be represented by an octet string of the same length. This is represented by an octet string of the same length. This is called
called the squeezed point representation. Obviously, other the "squeezed" point representation. (We will use this squeezed
representations (e.g., those of elements of Z_n) may also have fixed representation in Appendix J.) Obviously, other representations
bit values in certain positions, which can be used to squeeze-in (e.g., those of elements of Z_n) may also have fixed bit values in
additional information. Further details are out of scope. certain positions, which can be used to squeeze-in additional
information. Further details are out of scope. Notice that elements
of a prime field GF(p), where p is a prime number with bit-size m
divisible by eight, have a tight representation as an (m/8)-byte
string, but do not have a bit position that is always set to zero.
Thus, in this case, one cannot represent a compressed point as an
octet string of the same length as an element of GF(p). However, one
can still encode this as an octet string of length (m/8)+1 (see Note
1 above). If one uses right-concatenation as in Note 1, but (for
historial reasons) represents the parity bit t of the compressed
point in question by 0x00 or 0x80 depending on whether t=0 or t=1,
respectively, this is again called the "squeezed' representation
(despite this being somewhat a misnomer, since each point is now
represented as an octet string that is one octet longer than the
tight representation of elements of GF(p)). Notice that this
representation corresponds to the compressed point representation of
Appendix I.8 as octet string, but with the bit-ordering in the
1-octet representation of t reversed. (Note that this puts the
parity bit t in the leftmost bit position of the octet string if one
follows the MSB/msb representation conventions.) We will use this
squeezed represenation in Appendix O.
Appendix J. Representation Examples Curve25519 Family Members Appendix J. Representation Examples Curve25519 Family Members
We present some examples of computations using the curves introduced We present some examples of computations using the curves introduced
in this document. In each case, we indicate the values of P, k*P, in Appendix E and Appendix G of this document. In each case, we
and (k+1)*P, where P is a fixed multiple (here: 2019) of the base indicate the values of P, k*P, and (k+1)*P, where P is a fixed
point of the curve in question and where the private key k is the multiple (here: 2019) of the base point of the curve in question and
integer where the private key k is the integer
k 45467544759954639344191351164156560595299236761702065033670739677 k 45467544759954639344191351164156560595299236761702065033670739677
691372543056 691372543056
(=0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3 (=0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3
c08d5abd 15e29c50). c08d5abd 15e29c50).
In the examples below, each curve point is represented using the
"squeezed" point representation (see Appendix I.8), whereby each
point is represented as a 32-octet string, where the ordering
convention (see Appendix I.7) depends on the underlying curve model
in question. Here, points of a Weierstrass curve are represented in
tight MSB/msb-order, points of a Montgomery curve in tight LSB/msb-
order, and points of a twisted Edwards curve in tight LSB/lsb-order.
For points that are a public key, the corresponding private keys are
represented as 32-octet strings, using the same (tight) ordering
conventions as with the public keys. For affine points, we also give
the tight representation of each of its coordinates, using the same
ordering conventions as used with the squeezed point representation.
For further details, see the examples themselves.
J.1. Example with Curve25519 J.1. Example with Curve25519
Pm=(u, v), k*Pm=(u1, v1), and (k+1)*Pm=(u2, v2) with Curve25519: Pm=(u, v), k*Pm=(u1, v1), and (k+1)*Pm=(u2, v2) with Curve25519:
u 53025657538808013645618620393754461319535915376830819974982289332 u 53025657538808013645618620393754461319535915376830819974982289332
088255623750 088255623750
(=0x753b7566 df35d574 4734142c 9abf931c ea290160 aa75853c (=0x753b7566 df35d574 4734142c 9abf931c ea290160 aa75853c
7f972467 b7f13246). 7f972467 b7f13246).
skipping to change at page 93, line 26 skipping to change at page 103, line 18
N.4.2.3. Coefficients of w'(x) N.4.2.3. Coefficients of w'(x)
0 0x5555555555555555555555555555555555555555555555555555555500000000 0 0x5555555555555555555555555555555555555555555555555555555500000000
000000000000000000000000000000000000000000019719 000000000000000000000000000000000000000000019719
1 0x01 1 0x01
Appendix O. Representation Examples Curve448 Family Members Appendix O. Representation Examples Curve448 Family Members
We present some examples of computations using the curves introduced We present some examples of computations using the curves introduced
in this document. In each case, we indicate the values of P, k*P, in Appendix M and Appendix N of this document. In each case, we
and (k+1)*P, where P is a fixed multiple (here: 2019) of the base indicate the values of P, k*P, and (k+1)*P, where P is a fixed
point of the curve in question and where the private key k is the multiple (here: 2019) of the base point of the curve in question and
integer where the private key k is the integer
k 62662039304523906689788124833289384446202946474440057655160773695 k 62662039304523906689788124833289384446202946474440057655160773695
63756342505410402166230018620066482794080866641616932013327623579 63756342505410402166230018620066482794080866641616932013327623579
01952 01952
(=0xdcb3bbb9 e42d7aca fe62052d 902123c7 0872b984 4c1e199f (=0xdcb3bbb9 e42d7aca fe62052d 902123c7 0872b984 4c1e199f
7c5d37bd 1171102b c20a6352 d9c91886 29b685de 51441e84 3afe2665 7c5d37bd 1171102b c20a6352 d9c91886 29b685de 51441e84 3afe2665
5251aa80). 5251aa80).
In the examples below, each curve point is represented using the
compressed point representation (see Appendix I.8), but where (for
historical reasons) the parity bit t of the compressed curve point in
question is represented by 0x00 or 0x80 depending on whether t=0 or
t=1, respectively. Notice that this representation corresponds to
the compressed point representation of Appendix I.8, but with the
bit-ordering in the 1-octet representation of t reversed. (Note that
this puts the parity bit t in the leftmost bit position of the octet
string if one follows the MSB/msb representation conventions.) For
simplicity, this representation is again called the "squeezed"
representation, although each point is now represented as a 57-octet
string and, thereby, one octet longer than the tight representation
of elements of GF(p). As before, the ordering convention (see
Appendix I.7) depends on the underlying curve model in question.
Here, points of a Weierstrass curve are represented in tight MSB/msb-
order, points of a Montgomery curve in tight LSB/msb-order, and
points of a twisted Edwards curve in tight LSB/lsb-order. For points
that are a public key, the corresponding private keys are represented
as 56-octet strings, using the same ordering conventions as with the
public keys. For affine points, we also give the tight
representation of each of its coordinates (as 56-octet strings),
using the same ordering conventions as used with the squeezed point
representation. For further details, see the examples themselves.
O.1. Example with Curve448 O.1. Example with Curve448
Pm=(u, v), k*Pm=(u1, v1), and (k+1)*Pm=(u2, v2) with Curve448: Pm=(u, v), k*Pm=(u1, v1), and (k+1)*Pm=(u2, v2) with Curve448:
u 53298594738299085772373536080133483236673782578895339676785179923 u 53298594738299085772373536080133483236673782578895339676785179923
90764298300090102709453866054695061082746243636045110750296444932 90764298300090102709453866054695061082746243636045110750296444932
27715 27715
(=0xbbb91ba3 b0ef74c3 214394b4 d8f0d32d c4a92193 5f573009 (=0xbbb91ba3 b0ef74c3 214394b4 d8f0d32d c4a92193 5f573009
39fd86a3 8d54be2a 4d63380b 692381bb ed7339fd dca7b0cd a80166fe 39fd86a3 8d54be2a 4d63380b 692381bb ed7339fd dca7b0cd a80166fe
 End of changes. 83 change blocks. 
221 lines changed or deleted 714 lines changed or added

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