draft-ietf-lwig-curve-representations-18.txt | draft-ietf-lwig-curve-representations-19.txt | |||
---|---|---|---|---|

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

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

Intended status: Standards Track December 15, 2020 | Intended status: Standards Track December 17, 2020 | |||

Expires: June 18, 2021 | Expires: June 20, 2021 | |||

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

draft-ietf-lwig-curve-representations-18 | draft-ietf-lwig-curve-representations-19 | |||

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 18, 2021. | This Internet-Draft will expire on June 20, 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 27 ¶ | skipping to change at page 2, line 27 ¶ | |||

the Trust Legal Provisions and are provided without warranty as | the Trust Legal Provisions and are provided without warranty as | |||

described in the Simplified BSD License. | described in the Simplified BSD License. | |||

Table of Contents | Table of Contents | |||

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

2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 6 | 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 6 | |||

3. Use of Representation Switches . . . . . . . . . . . . . . . 6 | 3. Use of Representation Switches . . . . . . . . . . . . . . . 6 | |||

4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7 | 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7 | |||

4.1. Implementation of X25519, Specification of ECDH25519 . . 7 | 4.1. Implementation of X25519, Specification of ECDH25519 . . 7 | |||

4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 8 | 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 9 | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 18 | 10.2.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 . . . . . . . . 21 | 10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 22 | |||

11. Using Wei25519 and Wei448 with PKIX and CMS . . . . . . . . . 21 | 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 . . . . . 23 | |||

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 . . . . . . . . . . . . . . . . . . . . . . . . . . 22 | PKIX . . . . . . . . . . . . . . . . . . . . . . . . . . 23 | |||

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

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

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

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

12.2.1. COSE Elliptic Curves Registration . . . . . . . . . 23 | 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) . . . . . . . . . 24 | 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) . . . . . . . . . 25 | 12.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 26 | |||

12.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 25 | 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) . . . . . . . . . 26 | 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 . . . . . . . . . 27 | 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) . . . . . . . . . 29 | |||

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

13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 28 | 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 . . . . . . . . . . . . . . . . . . . . 34 | A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 35 | |||

A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 34 | A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 36 | |||

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

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

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

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

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

Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 43 | D.2. Mapping between Montgomery Curves and Weierstrass Curves 43 | |||

E.1. Curve Definition and Alternative Representations . . . . 43 | D.3. Mapping between Twisted Edwards Curves and Weierstrass | |||

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

E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 45 | Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 44 | |||

Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 47 | E.1. Curve Definition and Alternative Representations . . . . 45 | |||

F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 47 | E.2. Switching between Alternative Representations . . . . . . 45 | |||

F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 48 | E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 47 | |||

F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 49 | Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 49 | |||

F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 50 | F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 49 | |||

Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 51 | F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 49 | |||

G.1. Further Alternative Representations . . . . . . . . . . . 51 | F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 50 | |||

G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 51 | F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 51 | |||

G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 52 | Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 53 | |||

G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 54 | G.1. Further Alternative Representations . . . . . . . . . . . 53 | |||

G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 54 | G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 53 | |||

G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 60 | G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 54 | |||

Appendix H. Point Compression . . . . . . . . . . . . . . . . . 66 | G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 55 | |||

H.1. Point Compression for Weierstrass Curves . . . . . . . . 67 | G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 55 | |||

H.2. Point Compression for Montgomery Curves . . . . . . . . . 67 | G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 62 | |||

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

Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 69 | H.1. Point Compression for Weierstrass Curves . . . . . . . . 68 | |||

I.1. Strings and String Operations . . . . . . . . . . . . . . 69 | H.2. Point Compression for Montgomery Curves . . . . . . . . . 69 | |||

I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 70 | H.3. Point Compression for Twisted Edwards Curves . . . . . . 70 | |||

Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 71 | ||||

I.1. Strings and String Operations . . . . . . . . . . . . . . 71 | ||||

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

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

I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 70 | I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 72 | |||

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) . . . . . . . . . . . . . . . . . . . . . 73 | |||

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

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

I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 72 | I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 74 | |||

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

Appendix J. Representation Examples Curve25519 Family Members . 75 | Appendix J. Representation Examples Curve25519 Family Members . 77 | |||

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

J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 78 | J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 80 | |||

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

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

Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 87 | Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 89 | |||

K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 87 | K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 89 | |||

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

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

K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 88 | K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 90 | |||

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

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

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

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

K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 91 | K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 93 | |||

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

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

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

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

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

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

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

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

L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 100 | L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 102 | |||

L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 102 | L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 104 | |||

L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 102 | L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 104 | |||

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

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

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

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

M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 105 | M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 107 | |||

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

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

N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 108 | N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 110 | |||

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

N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 113 | N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 115 | |||

N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 113 | N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 115 | |||

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

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

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

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

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

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

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

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

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

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

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

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

Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 135 | Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 137 | |||

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 24 ¶ | skipping to change at page 8, line 24 ¶ | |||

A NIST-compliant version of the co-factor Diffie-Hellman key | A NIST-compliant version of the co-factor Diffie-Hellman key | |||

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: At this point, it is unclear whether this implies that a FIPS- | NOTE 1: A Montgomery version of the co-factor Diffie-Hellman key | |||

accredited module implementing co-factor Diffie-Hellman for, e.g., | agreement scheme (denoted by X25519+) results by incorporating Steps | |||

P-256 would also extend this accreditation to X25519. | (1), (2), and (3) above, i.e., where one keeps inputs (key | |||

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

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

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

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

reverse, the strict OS2FE mapping, of Appendix I.5, and where the | ||||

actual output (shared secret Z) is the representation of the shared | ||||

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

where the output is an error indicator otherwise (i.e., if K is the | ||||

point at infinity O of the curve). The scheme X25519, as specified | ||||

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

whereby one does not mandate rejection of shared keys in the small | ||||

subgroup (which are instead represented as if these were the point | ||||

(0,0) of order two), where one does not check whether a received key | ||||

contribution is a point of Curve25519 rather than a point of a | ||||

quadratic twist of this curve (for definitions of these terms, see | ||||

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

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

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

X25519, private keys are generated in the interval [2^251,2^252-1] | ||||

rather than in the interval [1,n-1] (the so-called "clamping") and | ||||

one uses as base point G':=h*G, where G, n, and h are, respectively, | ||||

the fixed base point, the order of the base point, and the co-factor | ||||

of the curve in question. | ||||

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

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

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

X25519+ or X25519. (For cryptographic module validation program | ||||

guidance, see, e.g., [FIPS-140-2].) | ||||

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

Ed25519 using an existing Montgomery curve implementation by (1) | Ed25519 using an existing Montgomery curve implementation by (1) | |||

generating a public-private key pair (k, R':=k*G') for Curve25519; | generating a public-private key pair (k, R':=k*G') for Curve25519; | |||

(2) representing this public-private key as the pair (k, R:=k*G) for | (2) representing this public-private key as the pair (k, R:=k*G) for | |||

Ed25519. As before, the representation change can be implemented via | Ed25519. As before, the representation change can be implemented via | |||

a simple wrapper. Note that the Montgomery ladder specified in | a simple wrapper. Note that the Montgomery ladder specified in | |||

Section 5 of RFC7748 [RFC7748] does not provide sufficient | Section 5 of RFC7748 [RFC7748] does not provide sufficient | |||

information to reconstruct R':=(u, v) (since it does not compute the | information to reconstruct R':=(u, v) (since it does not compute the | |||

v-coordinate of R'). However, this deficiency can be remedied by | v-coordinate of R'). However, this deficiency can be remedied by | |||

using a slightly modified version of the Montgomery ladder that | using a slightly modified version of the Montgomery ladder that | |||

includes reconstruction of the v-coordinate of R':=k*G' at the end of | includes reconstruction of the v-coordinate of R':=k*G' at the end of | |||

the Montgomery ladder (which uses the v-coordinate of the base point | the Montgomery ladder (which uses the v-coordinate of the base point | |||

of Curve25519 as well). For details, see Appendix C.2. | G' of Curve25519 as well). For details, see Appendix C.2. | |||

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

FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and | FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and | |||

can be instantiated not just with the NIST prime curves, but also | can be instantiated not just with the NIST prime curves, but also | |||

with other Weierstrass curves (that satisfy additional cryptographic | with other Weierstrass curves (that satisfy additional cryptographic | |||

criteria). In particular, one can instantiate this scheme with the | criteria). In particular, one can instantiate this scheme with the | |||

Weierstrass curve Wei25519 and the hash function SHA-256 | Weierstrass curve Wei25519 and the hash function SHA-256 | |||

[FIPS-180-4], where an implementation may generate an ephemeral | [FIPS-180-4], where an implementation may generate an ephemeral | |||

public-private key pair for Wei25519 by (1) internally carrying out | public-private key pair for Wei25519 by (1) internally carrying out | |||

skipping to change at page 10, line 13 ¶ | skipping to change at page 10, line 43 ¶ | |||

Section 4.1, but now using the short-Weierstrass curve Wei448, rather | Section 4.1, but now using the short-Weierstrass curve Wei448, rather | |||

than Wei25519 (with the same representation and bit/byte-ordering | than Wei25519 (with the same representation and bit/byte-ordering | |||

conventions). Similarly, one can easily specify ECDSA with Wei448 | conventions). Similarly, one can easily specify ECDSA with Wei448 | |||

and a suitable hash function, by simply reusing the example of | and a suitable hash function, by simply reusing the example of | |||

Section 4.3, but now using the short-Weierstrass curve Wei448, rather | Section 4.3, but now using the short-Weierstrass curve Wei448, rather | |||

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

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

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

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

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

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

scheme, whereby one does not mandate rejection of shared keys in the | ||||

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

point (0,0) of order two), nor checks whether a received key | ||||

contribution is a point of Curve448 rather than a point of a | ||||

quadratic twist of this curve, and where one uses the non-strict | ||||

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

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

in the interval [2^445,2^446-1] rather than in the interval [1,n-1] | ||||

(the so-called "clamping") and one uses as base point G':=h*G, where | ||||

G, n, and h are, respectively, the fixed base point, the order of the | ||||

base point, and the co-factor 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 | |||

The transformations between alternative curve representations can be | The transformations between alternative curve representations can be | |||

skipping to change at page 32, line 12 ¶ | skipping to change at page 33, line 12 ¶ | |||

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

14.2. Informative References | 14.2. Informative References | |||

[comm-FIPS-186-5] | [comm-FIPS-186-5] | |||

FIPS 186-5, "Public Comments Received on Draft FIPS Pub | FIPS 186-5, "Public Comments Received on Draft FIPS Pub | |||

186-5", US Department of Commerce/National Institute of | 186-5", US Department of Commerce/National Institute of | |||

Standards and Technology, Gaithersburg, MD, April 6, 2020. | Standards and Technology, Gaithersburg, MD, April 6, 2020. | |||

[draft-FIPS-186-5] | ||||

FIPS 186-5, "Digital Signature Standard (DSS) (Draft)", US | ||||

Department of Commerce/National Institute of Standards and | ||||

Technology, Gaithersburg, MD, October 31, 2019. | ||||

[draft-NIST-800-186] | ||||

NIST SP 800-186, "Recommendations for Discrete Logarithm- | ||||

Based Cryptography, Elliptic Curve Domain Parameters | ||||

(Draft)", US Department of Commerce/National Institute of | ||||

Standards and Technology, Gaithersburg, MD, October 31, | ||||

2019. | ||||

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

[FIPS-140-2] | ||||

FIPS 140-2, "Implementation Guidance for FIPS 140-2 and | ||||

the Cryptographic Module Validation Program", US | ||||

Department of Commerce/National Institute of Standards and | ||||

Technology, Gaithersburg, MD, August 28, 2020. | ||||

[GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to | [GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to | |||

Elliptic Curve Cryptography", New York: Springer-Verlag, | Elliptic Curve Cryptography", New York: Springer-Verlag, | |||

2004. | 2004. | |||

[Handbook] | ||||

A.J. Menezes, P. van Oorschot, S.A. Vanstone,, "Handbook | ||||

of Applied Cryptography", Boca Raton: CRC Press, 1995. | ||||

[IANA.COSE.Algorithms] | [IANA.COSE.Algorithms] | |||

IANA, "COSE Algorithms", IANA, | IANA, "COSE Algorithms", IANA, | |||

https://www.iana.org/assignments/cose/ | https://www.iana.org/assignments/cose/ | |||

cose.xhtml#algorithms. | cose.xhtml#algorithms. | |||

[IANA.COSE.Curves] | [IANA.COSE.Curves] | |||

IANA, "COSE Elliptic Curves", IANA, | IANA, "COSE Elliptic Curves", IANA, | |||

https://www.iana.org/assignments/cose/cose.xhtml#elliptic- | https://www.iana.org/assignments/cose/cose.xhtml#elliptic- | |||

curves. | curves. | |||

skipping to change at page 34, line 25 ¶ | skipping to change at page 35, line 42 ¶ | |||

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 quadratic twist of W_{a,b} is a curve W_{a',b'} defined over the | |||

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

is not a square in GF(q). | 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 | A quadratic twist of M_{A,B} is a curve M_{A',B'} defined over the | |||

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

square in GF(q). | 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 | (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 | condition on domain parameters a and d above and, thereby, satisfy | |||

in that appendix.) | 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 quadratic twist of E_{a,d} is a curve E_{a',d'} defined over the | |||

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

not a square in GF(q). | 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 | |||

skipping to change at page 72, line 5 ¶ | skipping to change at page 73, line 38 ¶ | |||

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.) The OS2FE(X,l) | 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, | 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 | except that it fails whenever it would require at least one modular | |||

reduction. Notice that the tight FE2OS mapping followed by the | reduction. Notice that the tight FE2OS mapping followed by the | |||

strict OS2FE mapping is the identity map (and, hence, OS2FE never | strict OS2FE mapping is the identity map (and, hence, OS2FE never | |||

fails in this case). | fails in this case). | |||

I.6. Conversion between Elements of Z mod n and Octet Strings (ZnE2OS, | I.6. Conversion between Elements of Z_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.3 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 | |||

skipping to change at page 74, line 6 ¶ | skipping to change at page 75, line 41 ¶ | |||

coordinates are the octet string representations of the elements X | coordinates are the octet string representations of the elements X | |||

and Y of GF(q), respectively, using the tight FE2OS mapping of | and Y of GF(q), respectively, using the tight FE2OS mapping of | |||

Appendix I.5. Note that, since we use a tight representation, this | 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 | 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 | parameters l and m are uniquely defined by the field GF(q) in | |||

question. The inverse mapping results by converting the first and | question. The inverse mapping results by converting the first and | |||

second coordinate of this pair (each an octet string of length l*m) | 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 | 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 | mapping of Appendix I.5. Note that if it is not a priori known | |||

whether the input to this inverse mapping actually represents an | whether the input to this inverse mapping actually represents an | |||

affine curve point, one should check that this is indeed an ordered | affine curve point, one should check that the output (X,Y) -- if | |||

pair of octet strings (each of length l*m) and that the output (X,Y) | defined -- is indeed an affine point of the curve in question, where | |||

-- if defined -- is indeed an affine point of the curve in question, | this operation fails if this is not the case. (This check involves | |||

where this mapping fails if either condition is not satisfied. | simply checking whether the ordered pair (X,Y) satisfies the defining | |||

equation for this curve.) | ||||

The compressed point (X, t) or (t, X) is represented by the ordered | The compressed point (X, t) or (t, X) is represented by the ordered | |||

pair whose coordinates are the octet string representations of the | 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 | 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 | the tight FE2OS mapping of Appendix I.5. Note that, since we use | |||

tight representations, this results in an ordered pair of octet | tight representations, this results in an ordered pair of octet | |||

strings (of length 1 and l*m, respectively), where the parameters l | 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 | and m are uniquely defined by the field GF(q) in question. The | |||

inverse mapping results by converting the first and second coordinate | inverse mapping results by converting the first and second coordinate | |||

of this pair (each an octet string, of length 1 and l*m, | of this pair (each an octet string, of length 1 and l*m, | |||

respectively) to, respectively, the element t of {0,1} and the | 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 | 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 | 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 | 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 | known whether the input to this inverse mapping actually represents a | |||

compressed curve point, one should check that this is indeed an | compressed curve point, one should check that the output (X, t) or | |||

ordered pair of octet strings (of length 1 and l*m, respectively) and | (t, X) -- if defined -- is indeed a compressed point of the curve in | |||

that the output (X, t) or (t, X) -- if defined -- is indeed a | question, using the point decompression process for this curve (see | |||

compressed point of the curve in question, using the point | Appendix H), where this operation fails if this is not the case. | |||

decompression process for this curve (see Appendix H), where this | (This check does include checking whether an element is a square in | |||

mapping fails if either condition is not satisfied. | GF(q), but does not require actually computing square roots (see also | |||

the Note in Appendix K.1).) | ||||

NOTE 1: The representations of affine and compressed points above are | NOTE 1: The representations of affine and compressed points above are | |||

as ordered pairs of octet strings. In practice, one often represents | as ordered pairs of octet strings. In practice, one often represents | |||

these as octet strings instead, via right-concatenation of its | these as octet strings instead, via right-concatenation of its | |||

coordinates (in left-to-right order). Since each coordinate has | coordinates (in left-to-right order). Since each coordinate has | |||

known length, this operation is reversible. When appropriate, we | known length, this operation is reversible. When appropriate, we | |||

refer to the latter as the octet (rather than the pair) | refer to the latter as the octet (rather than the pair) | |||

representation of a point. | representation of a point. | |||

NOTE 2: The octet representation of compressed points above | NOTE 2: The octet representation of compressed points above | |||

skipping to change at page 88, line 5 ¶ | skipping to change at page 89, line 42 ¶ | |||

outlier points in the small subgroup. | outlier points in the small subgroup. | |||

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

Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see | Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see | |||

Appendix K.1.1) or if q = 5 (mod 8) (see Appendix K.1.2). Details on | Appendix K.1.1) or if q = 5 (mod 8) (see Appendix K.1.2). Details on | |||

how to compute square roots for other values of q are out of scope. | how to compute square roots for other values of q are out of scope. | |||

If square roots are easy to compute in GF(q), then so are these in | If square roots are easy to compute in GF(q), then so are these in | |||

GF(q^2). | GF(q^2). | |||

NOTE: If one wishes to check whether an element is a square in GF(q), | ||||

rather than actually compute square roots, more efficient methods can | ||||

be used. As an example, if GF(q) is a prime field (i.e., q:=p), one | ||||

can efficiently check whether an element y is a square in GF(p) by | ||||

computing its Legendre symbol (y/p) (see Section 2.4.5 of | ||||

[Handbook]). Details on how to efficiently check whether an element | ||||

is a square in GF(q) for other values of q are out of scope. If | ||||

checking whether an element is a square is easy in GF(q), then so it | ||||

is in GF(q^2). | ||||

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

If y is a nonzero element of GF(q) and z:=y^{(q-3)/4}, then y is a | If y is a nonzero element of GF(q) and z:=y^{(q-3)/4}, then y is a | |||

square in GF(q) only if y*z^2=1. If y*z^2=1, z is a square root of | square in GF(q) only if y*z^2=1. If y*z^2=1, z is a square root of | |||

1/y and y*z is a square root of y in GF(q). | 1/y and y*z is a square root of y in GF(q). | |||

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

If y is a nonzero element of GF(q) and z:=y^{(q-5)/8}, then y is a | If y is a nonzero element of GF(q) and z:=y^{(q-5)/8}, then y is a | |||

square in GF(q) only if y^2*z^4=1. | square in GF(q) only if y^2*z^4=1. | |||

End of changes. 25 change blocks. | ||||

172 lines changed or deleted | | 253 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/ |