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/ |