draft-ietf-lwig-curve-representations-16.txt | draft-ietf-lwig-curve-representations-17.txt | |||
---|---|---|---|---|

lwig R. Struik | lwig R. Struik | |||

Internet-Draft Struik Security Consultancy | Internet-Draft Struik Security Consultancy | |||

Intended status: Standards Track December 9, 2020 | Intended status: Standards Track December 11, 2020 | |||

Expires: June 12, 2021 | Expires: June 14, 2021 | |||

Alternative Elliptic Curve Representations | Alternative Elliptic Curve Representations | |||

draft-ietf-lwig-curve-representations-16 | draft-ietf-lwig-curve-representations-17 | |||

Abstract | Abstract | |||

This document specifies how to represent Montgomery curves and | This document specifies how to represent Montgomery curves and | |||

(twisted) Edwards curves as curves in short-Weierstrass form and | (twisted) Edwards curves as curves in short-Weierstrass form and | |||

illustrates how this can be used to carry out elliptic curve | illustrates how this can be used to carry out elliptic curve | |||

computations using existing implementations of, e.g., ECDSA and ECDH | computations using existing implementations of, e.g., ECDSA and ECDH | |||

using NIST prime curves. We also provide extensive background | using NIST prime curves. We also provide extensive background | |||

material that may be useful for implementers of elliptic curve | material that may be useful for implementers of elliptic curve | |||

cryptography. | cryptography. | |||

skipping to change at page 1, line 44 ¶ | skipping to change at page 1, line 44 ¶ | |||

Internet-Drafts are working documents of the Internet Engineering | Internet-Drafts are working documents of the Internet Engineering | |||

Task Force (IETF). Note that other groups may also distribute | Task Force (IETF). Note that other groups may also distribute | |||

working documents as Internet-Drafts. The list of current Internet- | working documents as Internet-Drafts. The list of current Internet- | |||

Drafts is at https://datatracker.ietf.org/drafts/current/. | Drafts is at https://datatracker.ietf.org/drafts/current/. | |||

Internet-Drafts are draft documents valid for a maximum of six months | Internet-Drafts are draft documents valid for a maximum of six months | |||

and may be updated, replaced, or obsoleted by other documents at any | and may be updated, replaced, or obsoleted by other documents at any | |||

time. It is inappropriate to use Internet-Drafts as reference | time. It is inappropriate to use Internet-Drafts as reference | |||

material or to cite them other than as "work in progress." | material or to cite them other than as "work in progress." | |||

This Internet-Draft will expire on June 12, 2021. | This Internet-Draft will expire on June 14, 2021. | |||

Copyright Notice | Copyright Notice | |||

Copyright (c) 2020 IETF Trust and the persons identified as the | Copyright (c) 2020 IETF Trust and the persons identified as the | |||

document authors. All rights reserved. | document authors. All rights reserved. | |||

This document is subject to BCP 78 and the IETF Trust's Legal | This document is subject to BCP 78 and the IETF Trust's Legal | |||

Provisions Relating to IETF Documents | Provisions Relating to IETF Documents | |||

(https://trustee.ietf.org/license-info) in effect on the date of | (https://trustee.ietf.org/license-info) in effect on the date of | |||

publication of this document. Please review these documents | publication of this document. Please review these documents | |||

skipping to change at page 2, line 38 ¶ | skipping to change at page 2, line 38 ¶ | |||

4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 9 | 4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 9 | |||

4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 10 | 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 10 | |||

5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 | 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 | |||

5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 11 | 5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 11 | |||

5.2. Representation Conventions . . . . . . . . . . . . . . . 11 | 5.2. Representation Conventions . . . . . . . . . . . . . . . 11 | |||

5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 11 | 5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 11 | |||

6. Implementation Considerations . . . . . . . . . . . . . . . . 12 | 6. Implementation Considerations . . . . . . . . . . . . . . . . 12 | |||

7. Implementation Status . . . . . . . . . . . . . . . . . . . . 13 | 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 13 | |||

8. Security Considerations . . . . . . . . . . . . . . . . . . . 14 | 8. Security Considerations . . . . . . . . . . . . . . . . . . . 14 | |||

9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 15 | 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 15 | |||

10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 15 | 10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 16 | |||

10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 16 | 10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 16 | |||

10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 16 | 10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 16 | |||

10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 17 | 10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 17 | |||

10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 18 | 10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 18 | |||

10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 18 | 10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 19 | |||

10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 19 | 10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 20 | |||

10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 20 | 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 21 | |||

10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 21 | 10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 22 | |||

10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 22 | 10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 22 | |||

11. Using Wei25519 and Wei448 with PKIX and CMS . . . . . . . . . 22 | 11. Using Wei25519 and Wei448 with PKIX and CMS . . . . . . . . . 22 | |||

11.1. Encoding of Short-Weierstrass Curves with PKIX . . . . . 22 | 11.1. Encoding of Short-Weierstrass Curves with PKIX . . . . . 22 | |||

11.2. Encoding of ECDSA Instantiations with PKIX . . . . . . . 22 | 11.2. Encoding of ECDSA Instantiations with PKIX . . . . . . . 23 | |||

11.3. Encoding of co-factor ECDH and Other Algorithms with | 11.3. Encoding of co-factor ECDH and Other Algorithms with | |||

PKIX . . . . . . . . . . . . . . . . . . . . . . . . . . 23 | PKIX . . . . . . . . . . . . . . . . . . . . . . . . . . 23 | |||

11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS . . 23 | 11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS . . 23 | |||

12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 | 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 | |||

12.1. OIDs for Use with PKIX and CMS . . . . . . . . . . . . . 24 | 12.1. OIDs for Use with PKIX and CMS . . . . . . . . . . . . . 24 | |||

12.2. COSE/JOSE IANA Considerations for Wei25519 . . . . . . . 24 | 12.2. COSE/JOSE IANA Considerations for Wei25519 . . . . . . . 24 | |||

12.2.1. COSE Elliptic Curves Registration . . . . . . . . . 24 | 12.2.1. COSE Elliptic Curves Registration . . . . . . . . . 24 | |||

12.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 24 | 12.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 25 | |||

12.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 25 | 12.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 25 | |||

12.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 25 | 12.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 26 | |||

12.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 26 | 12.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 26 | |||

12.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 26 | 12.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 26 | |||

12.3. COSE/JOSE IANA Considerations for Wei448 . . . . . . . . 26 | 12.3. COSE/JOSE IANA Considerations for Wei448 . . . . . . . . 27 | |||

12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 26 | 12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 27 | |||

12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 27 | 12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 27 | |||

12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 27 | 12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 28 | |||

12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 28 | 12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 28 | |||

12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 28 | 12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 28 | |||

12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 29 | 12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 29 | |||

13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 29 | 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 29 | |||

14. References . . . . . . . . . . . . . . . . . . . . . . . . . 29 | 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 30 | |||

14.1. Normative References . . . . . . . . . . . . . . . . . . 29 | 14.1. Normative References . . . . . . . . . . . . . . . . . . 30 | |||

14.2. Informative References . . . . . . . . . . . . . . . . . 32 | 14.2. Informative References . . . . . . . . . . . . . . . . . 33 | |||

Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 34 | Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 35 | |||

A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 34 | A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 35 | |||

A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 35 | A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 35 | |||

A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 35 | A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 35 | |||

Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 35 | Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 36 | |||

B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 35 | B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 36 | |||

B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 37 | B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 38 | |||

Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 38 | Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 39 | |||

C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 38 | C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 39 | |||

C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 39 | C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 40 | |||

C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 40 | C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 41 | |||

Appendix D. Relationships Between Curve Models . . . . . . . . . 41 | Appendix D. Relationships Between Curve Models . . . . . . . . . 42 | |||

D.1. Mapping between Twisted Edwards Curves and Montgomery | D.1. Mapping between Twisted Edwards Curves and Montgomery | |||

Curves . . . . . . . . . . . . . . . . . . . . . . . . . 41 | Curves . . . . . . . . . . . . . . . . . . . . . . . . . 42 | |||

D.2. Mapping between Montgomery Curves and Weierstrass Curves 42 | D.2. Mapping between Montgomery Curves and Weierstrass Curves 43 | |||

D.3. Mapping between Twisted Edwards Curves and Weierstrass | D.3. Mapping between Twisted Edwards Curves and Weierstrass | |||

Curves . . . . . . . . . . . . . . . . . . . . . . . . . 43 | Curves . . . . . . . . . . . . . . . . . . . . . . . . . 44 | |||

Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 43 | Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 44 | |||

E.1. Curve Definition and Alternative Representations . . . . 43 | E.1. Curve Definition and Alternative Representations . . . . 44 | |||

E.2. Switching between Alternative Representations . . . . . . 44 | E.2. Switching between Alternative Representations . . . . . . 45 | |||

E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 45 | E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 46 | |||

Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 47 | Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 48 | |||

F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 47 | F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 48 | |||

F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 48 | F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 49 | |||

F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 49 | F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 50 | |||

F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 50 | F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 51 | |||

Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 51 | Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 52 | |||

G.1. Further Alternative Representations . . . . . . . . . . . 51 | G.1. Further Alternative Representations . . . . . . . . . . . 52 | |||

G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 51 | G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 52 | |||

G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 52 | G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 53 | |||

G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 54 | G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 55 | |||

G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 54 | G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 55 | |||

G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 60 | G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 61 | |||

Appendix H. Point Compression . . . . . . . . . . . . . . . . . 66 | Appendix H. Point Compression . . . . . . . . . . . . . . . . . 67 | |||

H.1. Point Compression for Weierstrass Curves . . . . . . . . 67 | H.1. Point Compression for Weierstrass Curves . . . . . . . . 68 | |||

H.2. Point Compression for Montgomery Curves . . . . . . . . . 68 | H.2. Point Compression for Montgomery Curves . . . . . . . . . 68 | |||

H.3. Point Compression for Twisted Edwards Curves . . . . . . 68 | H.3. Point Compression for Twisted Edwards Curves . . . . . . 69 | |||

Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 69 | Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 70 | |||

I.1. Strings and String Operations . . . . . . . . . . . . . . 69 | I.1. Strings and String Operations . . . . . . . . . . . . . . 70 | |||

I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 70 | I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 71 | |||

I.3. Conversion between Octet Strings and Integers (OS2I, | I.3. Conversion between Octet Strings and Integers (OS2I, | |||

I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 70 | I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 71 | |||

I.4. Conversion between Octet Strings and Bit Strings (OS2BS, | I.4. Conversion between Octet Strings and Bit Strings (OS2BS, | |||

BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 71 | BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 72 | |||

I.5. Conversion between Field Elements and Octet Strings | I.5. Conversion between Field Elements and Octet Strings | |||

(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 71 | (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 72 | |||

I.6. Conversion between Elements of Z mod n and Octet Strings | I.6. Conversion between Elements of Z mod n and Octet Strings | |||

(ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 72 | (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 73 | |||

I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 72 | I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 73 | |||

I.8. Conversion Between Curve Points and Octet Strings . . . . 73 | I.8. Conversion Between Curve Points and Octet Strings . . . . 74 | |||

Appendix J. Representation Examples Curve25519 Family Members . 76 | Appendix J. Representation Examples Curve25519 Family Members . 76 | |||

J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 76 | J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 77 | |||

J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 79 | J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 79 | |||

J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 81 | J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 82 | |||

J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 83 | J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 84 | |||

J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 85 | J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 86 | |||

Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 87 | Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 88 | |||

K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 88 | K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 88 | |||

K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 88 | K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 89 | |||

K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 88 | K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 89 | |||

K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 88 | K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 89 | |||

K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 89 | K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 90 | |||

K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 89 | K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 90 | |||

K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 90 | K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 91 | |||

K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 91 | K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 92 | |||

K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 92 | K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 92 | |||

K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 92 | K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 93 | |||

K.4.2. Mapping to High-Order Points of Montgomery Curve . . 93 | K.4.2. Mapping to High-Order Points of Montgomery Curve . . 94 | |||

K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 94 | K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 95 | |||

K.5. Randomized Representation of Curve Points . . . . . . . . 95 | K.5. Randomized Representation of Curve Points . . . . . . . . 96 | |||

K.6. Completing the Mappings to Curve Points . . . . . . . . . 96 | K.6. Completing the Mappings to Curve Points . . . . . . . . . 97 | |||

Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 99 | Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 100 | |||

L.1. Curve Definition and Alternative Representation . . . . . 100 | L.1. Curve Definition and Alternative Representation . . . . . 101 | |||

L.2. Switching Between Representations . . . . . . . . . . . . 100 | L.2. Switching Between Representations . . . . . . . . . . . . 101 | |||

L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 100 | L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 101 | |||

L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 102 | L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 103 | |||

L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 102 | L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 103 | |||

L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 103 | L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 104 | |||

Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 103 | Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 104 | |||

M.1. Curve Definition and Alternative Representations . . . . 103 | M.1. Curve Definition and Alternative Representations . . . . 104 | |||

M.2. Switching between Alternative Representations . . . . . . 104 | M.2. Switching between Alternative Representations . . . . . . 105 | |||

M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 105 | M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 106 | |||

Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 108 | Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 109 | |||

N.1. Further Alternative Representations . . . . . . . . . . . 108 | N.1. Further Alternative Representations . . . . . . . . . . . 109 | |||

N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 108 | N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 109 | |||

N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 111 | N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 112 | |||

N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 113 | N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 114 | |||

N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 113 | N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 114 | |||

N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 114 | N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 115 | |||

Appendix O. Representation Examples Curve448 Family Members . . 114 | Appendix O. Representation Examples Curve448 Family Members . . 115 | |||

O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 115 | O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 116 | |||

O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 118 | O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 119 | |||

O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 121 | O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 122 | |||

O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 124 | O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 125 | |||

O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 127 | O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 128 | |||

O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 129 | O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 130 | |||

Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 132 | Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 133 | |||

P.1. Conversion to Integers in Z_n via Modular Reduction . . . 133 | P.1. Conversion to Integers in Z_n via Modular Reduction . . . 134 | |||

P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 134 | P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 135 | |||

P.3. Conversion to Integers in Z_n via the Discard Method . . 135 | P.3. Conversion to Integers in Z_n via the Discard Method . . 136 | |||

Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 135 | Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 136 | |||

1. Fostering Code Reuse with New Elliptic Curves | 1. Fostering Code Reuse with New Elliptic Curves | |||

Elliptic curves can be represented using different curve models. | Elliptic curves can be represented using different curve models. | |||

Recently, IETF standardized elliptic curves that are claimed to have | Recently, IETF standardized elliptic curves that are claimed to have | |||

better performance and improved robustness against "real world" | better performance and improved robustness against "real world" | |||

attacks than curves represented in the traditional short-Weierstrass | attacks than curves represented in the traditional short-Weierstrass | |||

curve model. These so-called CFRG curves [RFC7748] use the | curve model. These so-called CFRG curves [RFC7748] use the | |||

Montgomery curve model and the model of twisted Edwards curves. | Montgomery curve model and the model of twisted Edwards curves. | |||

skipping to change at page 8, line 25 ¶ | skipping to change at page 8, line 25 ¶ | |||

agreement scheme (denoted by ECDH25519) results if one keeps inputs | agreement scheme (denoted by ECDH25519) results if one keeps inputs | |||

(key contributions) and pre-output (shared key K) in the short- | (key contributions) and pre-output (shared key K) in the short- | |||

Weierstrass format (and, hence, does not perform Steps (1) and (3) | Weierstrass format (and, hence, does not perform Steps (1) and (3) | |||

above), where the actual output (shared secret Z) is the x-coordinate | above), where the actual output (shared secret Z) is the x-coordinate | |||

of K (if this is an affine point of the curve), represented as a | of K (if this is an affine point of the curve), represented as a | |||

fixed-size octet string in tight MSB/msb-order using the FE2OS | fixed-size octet string in tight MSB/msb-order using the FE2OS | |||

mapping of Appendix I.5, and where the output is an error indicator | mapping of Appendix I.5, and where the output is an error indicator | |||

otherwise (i.e., if K is the point at infinity O of the curve). | otherwise (i.e., if K is the point at infinity O of the curve). | |||

NOTE 1: A Montgomery version of the co-factor Diffie-Hellman key | NOTE 1: A Montgomery version of the co-factor Diffie-Hellman key | |||

agreement scheme (denoted by X25519+) results by incorporating Step | agreement scheme (denoted by X25519+) results by incorporating Steps | |||

(1), (2), and (3) above, i.e., where one keeps inputs (key | (1), (2), and (3) above, i.e., where one keeps inputs (key | |||

contributions) and pre-output (shared key K) in the Montgomery curve | contributions) and pre-output (shared key K) in the Montgomery curve | |||

format, as points of Curve25519, and where one represents all affine | format, as points of Curve25519, where one represents each affine | |||

points by their x-coordinate, represented as a fixed-size octet | point by only its x-coordinate, represented as a fixed-size octet | |||

string in tight LSB/msb-order using the FE2OS mapping of | string in tight LSB/msb-order using the FE2OS mapping and its | |||

Appendix I.5, where the actual output (shared secret Z) is the | reverse, the strict OS2FE mapping, of Appendix I.5, and where the | |||

representation of the shared key K as defined above (if this is an | actual output (shared secret Z) is the representation of the shared | |||

affine point of the curve), and where the output is an error | key K as defined above (if this is an affine point of the curve), and | |||

indicator otherwise (i.e., if K is the point at infinity O of the | where the output is an error indicator otherwise (i.e., if K is the | |||

curve). The scheme X25519, as specified in [RFC7748], is compatible | point at infinity O of the curve). The scheme X25519, as specified | |||

with a more lenient version of this X25519+ scheme, whereby it does | in [RFC7748], is a more lenient version of this X25519+ scheme, | |||

not mandate rejection of shared keys in the small subgroup (which are | whereby one does not mandate rejection of shared keys in the small | |||

instead represented as if these were the point (0,0) of order two) | subgroup (which are instead represented as if these were the point | |||

and where it also accepts a shared key if all points are points of | (0,0) of order two), one does not check whether a received key | |||

the quadratic twist of Curve25519, rather than of Curve25519 itself | contribution is a point of Curve25519, rather than a point of a | |||

(for definitions of these terms, see Appendix B.1). | quadratic twist of this curve (for definitions of these terms, see | |||

Appendix B.1), and where one uses the non-strict (rather than strict) | ||||

OS2FE mapping (which, in this case, is always applied after setting | ||||

the leftmost bit of the rightmost octet to zero). Moreover, with | ||||

X25519, private keys are derived from integers generated in the | ||||

interval [2^251,2^252-1], rather than generated in the interval | ||||

[1,n-1], where n is the order of the base point of the curve in | ||||

question. | ||||

NOTE 2: At this point, it is unclear whether a FIPS-accredited module | NOTE 2: At this point, it is unclear whether a FIPS-accredited module | |||

implementing the co-factor Diffie-Hellman scheme with, e.g., P-256 | implementing the co-factor Diffie-Hellman scheme with, e.g., P-256 | |||

would also extend this accreditation to the Montgomery versions | would also extend this accreditation to the Montgomery versions | |||

X25519+ or X25519. | X25519+ or X25519. | |||

4.2. Implementation of Ed25519 | 4.2. Implementation of Ed25519 | |||

RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature | RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature | |||

scheme, with instantiation by the twisted Edwards curve Edwards25519. | scheme, with instantiation by the twisted Edwards curve Edwards25519. | |||

skipping to change at page 10, line 45 ¶ | skipping to change at page 10, line 45 ¶ | |||

than Wei25519, and picking as hash function SHAKE256 [FIPS-202] with | than Wei25519, and picking as hash function SHAKE256 [FIPS-202] with | |||

output size of d=512 bits. We denote by ECDSA448 the resulting | output size of d=512 bits. We denote by ECDSA448 the resulting | |||

signature scheme (with the same representation and bit/byte-ordering | signature scheme (with the same representation and bit/byte-ordering | |||

conventions). | conventions). | |||

NOTE: A Montgomery version of the co-factor Diffie-Hellman key | NOTE: A Montgomery version of the co-factor Diffie-Hellman key | |||

agreement scheme (denoted by X448+) results by reusing the | agreement scheme (denoted by X448+) results by reusing the | |||

description of X25519+ in Section 4.1, but now using the Montgomery | description of X25519+ in Section 4.1, but now using the Montgomery | |||

curve Curve448, rather than Curve25519 (with the same checks and | curve Curve448, rather than Curve25519 (with the same checks and | |||

representation and bit/byte-ordering conventions). The scheme X448, | representation and bit/byte-ordering conventions). The scheme X448, | |||

as specified in [RFC7748], is compatible with a more lenient version | as specified in [RFC7748], is a more lenient version of this X448+ | |||

of this X448+ scheme, whereby it does not mandate rejection of shared | scheme, whereby one does not mandate rejection of shared keys in the | |||

keys in the small subgroup (which are instead again represented as if | small subgroup (which are instead represented as if these were the | |||

these were the point (0,0) of order two) and where it also accepts a | point (0,0) of order two), nor checks whether a received key | |||

shared key if all points are points of the quadratic twist of | contribution is a point of Curve448, rather than a point of a | |||

Curve448, rather than of Curve448 itself. | quadratic twist of this curve, and where one uses the non-strict | |||

(rather than the strict) OS2FE mapping for converting octet strings | ||||

to field elements. Moreover, with X448, private keys are derived | ||||

from integers generated in the interval [2^445,2^446-1], rather than | ||||

generated in the interval [1,n-1], where n is the order of the base | ||||

point of the curve in question. | ||||

5. Caveats | 5. Caveats | |||

The examples above illustrate how specifying the Weierstrass curve | The examples above illustrate how specifying the Weierstrass curve | |||

Wei25519 (or any curve in short-Weierstrass format, for that matter) | Wei25519 (or any curve in short-Weierstrass format, for that matter) | |||

may facilitate reuse of existing code and may simplify standards | may facilitate reuse of existing code and may simplify standards | |||

development. However, the following caveats apply: | development. However, the following caveats apply: | |||

5.1. Wire Format | 5.1. Wire Format | |||

skipping to change at page 12, line 23 ¶ | skipping to change at page 12, line 27 ¶ | |||

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

being "Jacobian-friendly" by design. | being "Jacobian-friendly" by design. | |||

NOTE 2: While an implementation of Curve25519 via an isogenous | NOTE 2: While an implementation of Curve25519 via an isogenous | |||

Weierstrass curve with domain parameter a=-3 requires a relatively | Weierstrass curve with domain parameter a=-3 requires a relatively | |||

large table (of size roughly 9kB), for the quadratic twist of | large table (of size roughly 9kB), for a quadratic twist of | |||

Curve25519 (i.e., the Montgomery curve M_{A,B'} with A=486662 and | Curve25519 (e.g., the Montgomery curve M_{A,B'} with A=486662 and | |||

B'=2) this implementation approach only requires a table of size less | B'=2) this implementation approach only requires a table of size less | |||

than 0.5kB (over 20x smaller), solely due to the fact that it is | than 0.5kB (over 20x smaller), solely due to the fact that it is | |||

l-isogenous to a Weierstrass curve with a=-3 parameter with | l-isogenous to a Weierstrass curve with a=-3 parameter with | |||

relatively small parameter l=2 (compared to l=47, as is the case with | relatively small parameter l=2 (compared to l=47, as is the case with | |||

Curve25519 itself). | Curve25519 itself). | |||

6. Implementation Considerations | 6. Implementation Considerations | |||

The efficiency of elliptic curve arithmetic is primarily determined | The efficiency of elliptic curve arithmetic is primarily determined | |||

by the efficiency of its group operations (see Appendix C). Numerous | by the efficiency of its group operations (see Appendix C). Numerous | |||

skipping to change at page 15, line 11 ¶ | skipping to change at page 15, line 16 ¶ | |||

Elliptic curves are generally used as objects in a broader | Elliptic curves are generally used as objects in a broader | |||

cryptographic scheme that may include processing steps that depend on | cryptographic scheme that may include processing steps that depend on | |||

the representation conventions used (such as with, e.g., key | the representation conventions used (such as with, e.g., key | |||

derivation following key establishment). These schemes should | derivation following key establishment). These schemes should | |||

(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. | |||

between Ed25519 (as specified in [RFC8032]) and ECDSA25519 (as | ||||

specified in Section 4.3). Similarly, private keys MUST NOT be | Private keys MUST NOT be reused between Ed25519 (as specified in | |||

reused between Ed448 (as specified in [RFC8032]) and ECDSA448 (as | [RFC8032]) and ECDSA25519 (as specified in Section 4.3). Similarly, | |||

specified in Section 4.4). | private keys MUST NOT be reused between Ed448 (as specified in | |||

[RFC8032]) and ECDSA448 (as specified in Section 4.4). | ||||

To prevent intra-protocol cross-instantiation attacks, ephemeral | 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. | or of ECDSA448. | |||

With ECDSA25519 and ECDSA448, the same private signature key MUST NOT | ||||

be reused between application scenarios where message encoding and | ||||

decoding rules vary, since this may jeopardize message unforgeability | ||||

properties; see also the Note in Section 10.2.1. (In fact, this | ||||

holds for any signature scheme, not just ECDSA.) | ||||

9. Privacy Considerations | 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 19, line 37 ¶ | skipping to change at page 19, line 50 ¶ | |||

instantiation of ECDSA and the "crv" parameter MUST be set to the | instantiation of ECDSA and the "crv" parameter MUST be set to the | |||

(unique) name of the corresponding curve; if the "key_ops" field is | (unique) name of the corresponding curve; if the "key_ops" field is | |||

present, it MUST include "sign" when creating an ECDSA signature and | present, it MUST include "sign" when creating an ECDSA signature and | |||

it MUST include "verify" when verifying an ECDSA signature. | it MUST include "verify" when verifying an ECDSA signature. | |||

NOTE: Care should be taken that signers and verifiers do have a | NOTE: Care should be taken that signers and verifiers do have a | |||

common understanding of message encoding rules, since otherwise | common understanding of message encoding rules, since otherwise | |||

signature verification may fail for messages with the same semantics. | signature verification may fail for messages with the same semantics. | |||

As an example, if there is ambiguity as to whether to represent the | As an example, if there is ambiguity as to whether to represent the | |||

binary digit 0 as the integer 0 or as the CBOR false value | binary digit 0 as the integer 0 or as the CBOR false value | |||

(represented as the CBOR bit string b000_00000 or b111_101000, | (represented as the CBOR bit string b000_00000 or b111_10100, | |||

respectively), signing and signature verification may depend on | respectively), signing and signature verification may depend on | |||

different ToBeSigned strings and, thereby, may fail unexpectedly. | different ToBeSigned strings and, thereby, may fail unexpectedly. | |||

This explains the (strong) requirement for deterministic encoding | This explains the (strong) requirement for deterministic encoding | |||

rules above and, thereby, the requirement for strong typing of any | rules above and, thereby, the requirement for strong typing of any | |||

CBOR encodings used with signed messages. Further care should be | CBOR encodings used with signed messages. Further care should be | |||

taken that message decoding rules are always unambiguous, since | taken that message decoding rules are always unambiguous, since | |||

otherwise the semantics of signed messages may not be clear or the | otherwise the semantics of signed messages may not be clear or the | |||

unforgeability property of signatures may be jeopardized. | unforgeability property of signatures may be jeopardized. | |||

10.2.2. Encoding of ECDSA Instantiations with JOSE | 10.2.2. Encoding of ECDSA Instantiations with JOSE | |||

skipping to change at page 34, line 37 ¶ | skipping to change at page 35, line 9 ¶ | |||

[Wei-Ladder] | [Wei-Ladder] | |||

T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve | T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve | |||

Multiplication Resistant Against Side Channel Attacks", | Multiplication Resistant Against Side Channel Attacks", | |||

Centre for Applied Cryptographic Research, Corr 2002-03, | Centre for Applied Cryptographic Research, Corr 2002-03, | |||

2002. | 2002. | |||

Appendix A. Some (Non-Binary) Elliptic Curves | Appendix A. Some (Non-Binary) Elliptic Curves | |||

This section defines the three different curve models we consider, | This section defines the three different curve models we consider, | |||

viz. short-Weierstrass curves, Montgomery curves, and twisted Edwards | viz. short-Weierstrass curves, Montgomery curves, and twisted Edwards | |||

curves. | curves. For nomenclature, see Appendix B. | |||

A.1. Curves in Short-Weierstrass Form | A.1. Curves in Short-Weierstrass Form | |||

Let GF(q) denote the finite field with q elements, where q is an odd | Let GF(q) denote the finite field with q elements, where q is an odd | |||

prime power and where q is not divisible by three. Let W_{a,b} be | prime power and where q is not divisible by three. Let W_{a,b} be | |||

the Weierstrass curve with defining equation Y^2 = X^3 + a*X + b, | the Weierstrass curve with defining equation Y^2 = X^3 + a*X + b, | |||

where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is | where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is | |||

nonzero. The points of W_{a,b} are the ordered pairs (X, Y) whose | nonzero. The points of W_{a,b} are the ordered pairs (X, Y) whose | |||

coordinates are elements of GF(q) and that satisfy the defining | coordinates are elements of GF(q) and that satisfy the defining | |||

equation (the so-called affine points), together with the special | equation (the so-called affine points), together with the special | |||

point O (the so-called "point at infinity"). This set forms a group | point O (the so-called "point at infinity"). This set forms a group | |||

under addition, via the so-called "chord-and-tangent" rule, where the | under addition, via the so-called "chord-and-tangent" rule, where the | |||

point at infinity serves as the identity element. See Appendix C.1 | point at infinity serves as the identity element. See Appendix C.1 | |||

for details of the group operation. | for details of the group operation. | |||

A quadratic twist of W_{a,b} is a curve W_{a',b'} for which a':= | ||||

a*gamma^2 and b':=b*gamma^3, where gamma is an element of GF(q) that | ||||

is not a square in GF(q). | ||||

A.2. Montgomery Curves | A.2. Montgomery Curves | |||

Let GF(q) denote the finite field with q elements, where q is an odd | Let GF(q) denote the finite field with q elements, where q is an odd | |||

prime power. Let M_{A,B} be the Montgomery curve with defining | prime power. Let M_{A,B} be the Montgomery curve with defining | |||

equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q) | equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q) | |||

and where A is unequal to (+/-)2 and where B is nonzero. The points | and where A is unequal to (+/-)2 and where B is nonzero. The points | |||

of M_{A,B} are the ordered pairs (u, v) whose coordinates are | of M_{A,B} are the ordered pairs (u, v) whose coordinates are | |||

elements of GF(q) and that satisfy the defining equation (the so- | elements of GF(q) and that satisfy the defining equation (the so- | |||

called affine points), together with the special point O (the so- | called affine points), together with the special point O (the so- | |||

called "point at infinity"). This set forms a group under addition, | called "point at infinity"). This set forms a group under addition, | |||

via the so-called "chord-and-tangent" rule, where the point at | via the so-called "chord-and-tangent" rule, where the point at | |||

infinity serves as the identity element. See Appendix C.2 for | infinity serves as the identity element. See Appendix C.2 for | |||

details of the group operation. | details of the group operation. | |||

A quadratic twist of M_{A,B} is a curve M_{A',B'} for which A':= A | ||||

and B':=B*gamma, where gamma is an element of GF(q) that is not a | ||||

square in GF(q). | ||||

A.3. Twisted Edwards Curves | A.3. Twisted Edwards Curves | |||

Let GF(q) denote the finite field with q elements, where q is an odd | Let GF(q) denote the finite field with q elements, where q is an odd | |||

prime power. Let E_{a,d} be the twisted Edwards curve with defining | prime power. Let E_{a,d} be the twisted Edwards curve with defining | |||

equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct | equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct | |||

nonzero elements of GF(q). The points of E_{a,d} are the ordered | nonzero elements of GF(q). The points of E_{a,d} are the ordered | |||

pairs (x, y) whose coordinates are elements of GF(q) and that satisfy | pairs (x, y) whose coordinates are elements of GF(q) and that satisfy | |||

the defining equation (the so-called affine points). It can be shown | the defining equation (the so-called affine points). It can be shown | |||

that this set forms a group under addition if a is a square in GF(q), | that this set forms a group under addition if a is a square in GF(q), | |||

whereas d is not, where the point O:=(0, 1) serves as the identity | whereas d is not, where the point O:=(0, 1) serves as the identity | |||

element. (Note that the identity element satisfies the defining | element. (Note that the identity element satisfies the defining | |||

equation.) See Appendix C.3 for details of the group operation. | equation.) See Appendix C.3 for details of the group operation. | |||

(All curves E_{a,d} in this document are assumed to satisfy the | ||||

condition on domain parameters a and d above and, thereby, the Note | ||||

in that appendix.) | ||||

An Edwards curve is a twisted Edwards curve with a=1. | An Edwards curve is a twisted Edwards curve with a=1. | |||

A quadratic twist of E_{a,d} is a curve E_{a',d'} for which a':= | ||||

a*gamma and d':=d*gamma, where gamma is an element of GF(q) that is | ||||

not a square in GF(q). | ||||

Appendix B. Elliptic Curve Nomenclature and Finite Fields | Appendix B. Elliptic Curve Nomenclature and Finite Fields | |||

This section provides brief background information on elliptic curves | This section provides brief background information on elliptic curves | |||

and finite fields that should be sufficient to understand | and finite fields that should be sufficient to understand | |||

constructions and examples in this document. | constructions and examples in this document. | |||

B.1. Elliptic Curve Nomenclature | B.1. Elliptic Curve Nomenclature | |||

The set of points of each curve defined in Appendix A forms a | The set of points of each curve defined in Appendix A forms a | |||

commutative group under addition (denoted by '+'). In Appendix C we | commutative group under addition (denoted by '+'). In Appendix C we | |||

skipping to change at page 36, line 50 ¶ | skipping to change at page 37, line 37 ¶ | |||

key, and the point R the corresponding public key. The private key k | key, and the point R the corresponding public key. The private key k | |||

can be represented as an integer in the interval [0,n-1], where G has | can be represented as an integer in the interval [0,n-1], where G has | |||

order n. If this representation is nonzero, R has order n; | order n. If this representation is nonzero, R has order n; | |||

otherwise, it has order one and is the identity element O of the | otherwise, it has order one and is the identity element O of the | |||

curve. | curve. | |||

In this document, a quadratic twist of a curve E defined over a field | In this document, a quadratic twist of a curve E defined over a field | |||

GF(q) is a specific curve E' related to E defined over the same | GF(q) is a specific curve E' related to E defined over the same | |||

field, with cardinality |E'|, where |E|+|E'|=2*(q+1). If E is a | field, with cardinality |E'|, where |E|+|E'|=2*(q+1). If E is a | |||

curve in one of the curve models specified in this document, a | curve in one of the curve models specified in this document, a | |||

quadratic twist of this curve can be expressed using the same curve | quadratic twist E' of this curve can be expressed using the same | |||

model, although (naturally) with its own curve parameters. Two | curve model, although (naturally) with its own curve parameters (see | |||

curves E and E' defined over a field GF(q) are said to be isogenous | Appendix A). Points that are both points of E and E' have order one | |||

if these have the same order and are said to be isomorphic if these | or two. Two curves E and E' defined over a field GF(q) are said to | |||

have the same group structure. Note that isomorphic curves have | be isogenous if these have the same order and are said to be | |||

necessarily the same order and are, thus, a special type of isogenous | isomorphic if these have the same group structure. Note that | |||

curves. Further details are out of scope. | isomorphic curves have necessarily the same order and are, thus, a | |||

special case of isogenous curves. Further details are out of scope. | ||||

Weierstrass curves can have prime order, whereas Montgomery curves | Weierstrass curves can have prime order, whereas Montgomery curves | |||

and twisted Edwards curves always have an order that is a multiple of | and twisted Edwards curves always have an order that is a multiple of | |||

four (and, thereby, a small subgroup of cardinality four). | four (and, thereby, a small subgroup of cardinality four). | |||

An ordered pair (x, y) whose coordinates are elements of GF(q) can be | An ordered pair (x, y) whose coordinates are elements of GF(q) can be | |||

associated with any ordered triple of the form [x*z: y*z: z], where z | associated with any ordered triple of the form [x*z: y*z: z], where z | |||

is a nonzero element of GF(q), and can be uniquely recovered from | is a nonzero element of GF(q), and can be uniquely recovered from | |||

such a representation. The latter representation is commonly called | such a representation. The latter representation is commonly called | |||

a representation in projective coordinates. Sometimes, yet other | a representation in projective coordinates. Sometimes, yet other | |||

End of changes. 37 change blocks. | ||||

145 lines changed or deleted | | 180 lines changed or added | ||

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