draft-ietf-lwig-curve-representations-12.txt | draft-ietf-lwig-curve-representations-13.txt | |||
---|---|---|---|---|

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

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

Intended status: Informational August 24, 2020 | Intended status: Informational November 2, 2020 | |||

Expires: February 25, 2021 | Expires: May 6, 2021 | |||

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

draft-ietf-lwig-curve-representations-12 | draft-ietf-lwig-curve-representations-13 | |||

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 February 25, 2021. | This Internet-Draft will expire on May 6, 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 30 ¶ | skipping to change at page 2, line 30 ¶ | |||

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 . . . . . . . . . . . . . . . . 7 | 4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 7 | |||

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

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

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

5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 | 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 | |||

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

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

5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 10 | 5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 10 | |||

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

7. Implementation Status . . . . . . . . . . . . . . . . . . . . 12 | 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 12 | |||

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

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

10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 14 | 10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 14 | |||

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

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

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

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

10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 17 | 10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 17 | |||

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

10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 19 | 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 19 | |||

10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 20 | 10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 20 | |||

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

11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 | 11. Using Wei25519 and Wei448 with PKIX and CMS . . . . . . . . . 21 | |||

11.1. IANA Considerations for Wei25519 . . . . . . . . . . . . 21 | 11.1. Encoding of Short-Weierstrass Curves with PKIX . . . . . 21 | |||

11.1.1. COSE Elliptic Curves Registration . . . . . . . . . 21 | 11.2. Encoding of ECDSA Instantiations with PKIX . . . . . . . 21 | |||

11.1.2. COSE Algorithms Registration (1/2) . . . . . . . . . 21 | 11.3. Encoding of co-factor ECDH and Other Algorithms with | |||

11.1.3. COSE Algorithms Registration (2/2) . . . . . . . . . 21 | PKIX . . . . . . . . . . . . . . . . . . . . . . . . . . 21 | |||

11.1.4. JOSE Elliptic Curves Registration . . . . . . . . . 22 | ||||

11.1.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 22 | 11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS . . 22 | |||

11.1.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 23 | 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 | |||

11.2. IANA Considerations for Wei448 . . . . . . . . . . . . . 23 | 12.1. OIDs for Use with PKIX and CMS . . . . . . . . . . . . . 22 | |||

11.2.1. COSE Elliptic Curves Registration . . . . . . . . . 23 | 12.2. COSE/JOSE IANA Considerations for Wei25519 . . . . . . . 23 | |||

11.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 24 | 12.2.1. COSE Elliptic Curves Registration . . . . . . . . . 23 | |||

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

11.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 24 | 12.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 23 | |||

11.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 25 | 12.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 24 | |||

11.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 25 | 12.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 24 | |||

12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 26 | 12.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 25 | |||

13. References . . . . . . . . . . . . . . . . . . . . . . . . . 26 | 12.3. COSE/JOSE IANA Considerations for Wei448 . . . . . . . . 25 | |||

13.1. Normative References . . . . . . . . . . . . . . . . . . 26 | 12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 25 | |||

13.2. Informative References . . . . . . . . . . . . . . . . . 28 | 12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 26 | |||

Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 30 | 12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 26 | |||

A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 30 | 12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 26 | |||

A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 30 | 12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 27 | |||

A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 30 | 12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 27 | |||

Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 31 | 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 28 | |||

B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 31 | 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 28 | |||

B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 33 | 14.1. Normative References . . . . . . . . . . . . . . . . . . 28 | |||

Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 34 | 14.2. Informative References . . . . . . . . . . . . . . . . . 31 | |||

C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 34 | Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 32 | |||

C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 35 | A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 33 | |||

C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 36 | A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 33 | |||

Appendix D. Relationships Between Curve Models . . . . . . . . . 37 | A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 33 | |||

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

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

B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 35 | ||||

Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 36 | ||||

C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 37 | ||||

C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 37 | ||||

C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 38 | ||||

Appendix D. Relationships Between Curve Models . . . . . . . . . 39 | ||||

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

Curves . . . . . . . . . . . . . . . . . . . . . . . . . 37 | Curves . . . . . . . . . . . . . . . . . . . . . . . . . 40 | |||

D.2. Mapping between Montgomery Curves and Weierstrass Curves 37 | D.2. Mapping between Montgomery Curves and Weierstrass Curves 40 | |||

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

Curves . . . . . . . . . . . . . . . . . . . . . . . . . 38 | Curves . . . . . . . . . . . . . . . . . . . . . . . . . 41 | |||

Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 39 | Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 41 | |||

E.1. Curve Definition and Alternative Representations . . . . 39 | E.1. Curve Definition and Alternative Representations . . . . 42 | |||

E.2. Switching between Alternative Representations . . . . . . 39 | E.2. Switching between Alternative Representations . . . . . . 42 | |||

E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 41 | E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 44 | |||

Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 43 | Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 46 | |||

F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 43 | F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 46 | |||

F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 43 | F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 46 | |||

F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 44 | F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 47 | |||

F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 45 | F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 48 | |||

Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 47 | Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 50 | |||

G.1. Further Alternative Representations . . . . . . . . . . . 47 | G.1. Further Alternative Representations . . . . . . . . . . . 50 | |||

G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 47 | G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 50 | |||

G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 48 | G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 51 | |||

G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 49 | G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 52 | |||

G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 49 | G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 52 | |||

G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 56 | G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 59 | |||

Appendix H. Point Compression . . . . . . . . . . . . . . . . . 62 | Appendix H. Point Compression . . . . . . . . . . . . . . . . . 65 | |||

H.1. Point Compression for Weierstrass Curves . . . . . . . . 62 | H.1. Point Compression for Weierstrass Curves . . . . . . . . 65 | |||

H.2. Point Compression for Montgomery Curves . . . . . . . . . 63 | H.2. Point Compression for Montgomery Curves . . . . . . . . . 66 | |||

H.3. Point Compression for Twisted Edwards Curves . . . . . . 64 | H.3. Point Compression for Twisted Edwards Curves . . . . . . 67 | |||

Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 65 | Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 68 | |||

I.1. Strings and String Operations . . . . . . . . . . . . . . 65 | I.1. Strings and String Operations . . . . . . . . . . . . . . 68 | |||

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

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

I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 66 | I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 69 | |||

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

BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 66 | BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 69 | |||

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

(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 67 | (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 70 | |||

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) . . . . . . . . . . . . . . . . . . . . 67 | (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 70 | |||

I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 68 | I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 71 | |||

I.8. Conversion Between Curve Points and Octet Strings . . . . 69 | I.8. Conversion Between Curve Points and Octet Strings . . . . 72 | |||

Appendix J. Representation Examples Curve25519 Family Members . 71 | Appendix J. Representation Examples Curve25519 Family Members . 74 | |||

J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 72 | J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 75 | |||

J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 74 | J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 77 | |||

J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 75 | J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 79 | |||

J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 78 | J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 82 | |||

J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 79 | J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 84 | |||

Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 81 | Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 86 | |||

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

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

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

K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 82 | K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 87 | |||

K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 82 | K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 87 | |||

K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 82 | K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 87 | |||

K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 83 | K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 89 | |||

K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 84 | K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 90 | |||

K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 85 | K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 90 | |||

K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 85 | K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 90 | |||

K.4.2. Mapping to High-Order Points of Montgomery Curve . . 86 | K.4.2. Mapping to High-Order Points of Montgomery Curve . . 91 | |||

K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 87 | K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 93 | |||

K.5. Randomized Representation of Curve Points . . . . . . . . 88 | K.5. Randomized Representation of Curve Points . . . . . . . . 94 | |||

K.6. Completing the Mappings to Curve Points . . . . . . . . . 89 | K.6. Completing the Mappings to Curve Points . . . . . . . . . 95 | |||

Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 90 | Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 96 | |||

L.1. Curve Definition and Alternative Representation . . . . . 90 | L.1. Curve Definition and Alternative Representation . . . . . 96 | |||

L.2. Switching Between Representations . . . . . . . . . . . . 90 | L.2. Switching Between Representations . . . . . . . . . . . . 97 | |||

L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 91 | L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 97 | |||

L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 92 | L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 99 | |||

L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 92 | L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 99 | |||

L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 93 | L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 99 | |||

Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 94 | Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 100 | |||

M.1. Curve Definition and Alternative Representations . . . . 94 | M.1. Curve Definition and Alternative Representations . . . . 100 | |||

M.2. Switching between Alternative Representations . . . . . . 94 | M.2. Switching between Alternative Representations . . . . . . 101 | |||

M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 96 | M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 102 | |||

Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 105 | ||||

Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 98 | N.1. Further Alternative Representations . . . . . . . . . . . 105 | |||

N.1. Further Alternative Representations . . . . . . . . . . . 98 | N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 105 | |||

N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 99 | N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 108 | |||

N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 101 | N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 110 | |||

N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 103 | N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 110 | |||

N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 103 | N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 111 | |||

N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 104 | Appendix O. Representation Examples Curve448 Family Members . . 111 | |||

Appendix O. Representation Examples Curve448 Family Members . . 105 | O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 112 | |||

O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 105 | O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 115 | |||

O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 108 | O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 118 | |||

O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 110 | O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 121 | |||

O.4. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 113 | O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 123 | |||

O.5. Example with Edwards448 . . . . . . . . . . . . . . . . . 115 | O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 126 | |||

Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 117 | Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 129 | |||

P.1. Conversion to Integers in Z_n via Modular Reduction . . . 117 | P.1. Conversion to Integers in Z_n via Modular Reduction . . . 129 | |||

P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 118 | P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 130 | |||

P.3. Conversion to Integers in Z_n via the Discard Method . . 119 | P.3. Conversion to Integers in Z_n via the Discard Method . . 130 | |||

Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 119 | Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 131 | |||

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

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

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

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

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

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

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

In this document, we specify these curves using the traditional | In this document, we specify these curves using the traditional | |||

"short" Weierstrass model and also define how to efficiently switch | short-Weierstrass model and also define how to efficiently switch | |||

between representations in these different curve models. In | between representations in these different curve models. In | |||

particular, we specify Wei25519, which allows an alternative | particular, we specify Wei25519, which allows an alternative | |||

representation of points of Curve25519 (a Montgomery curve) and of | representation of points of Curve25519 (a Montgomery curve) and of | |||

points of Edwards25519 (a twisted Edwards curve), as points of a | points of Edwards25519 (a twisted Edwards curve), as points of a | |||

corresponding "short" Weierstrass curve. Similarly, we specify | corresponding short-Weierstrass curve. Similarly, we specify Wei448, | |||

Wei448, which allows an alternative representation of points of | which allows an alternative representation of points of Curve448 (a | |||

Curve448 (a Montgomery curve) and of points of Ed448 (an Edwards | Montgomery curve) and of points of Ed448 (an Edwards curve), as | |||

curve), as points of a corresponding "short" Weierstrass curve. | points of a corresponding short-Weierstrass curve. | |||

Use of Wei25519 and Wei448 allows easy definition of new | Use of Wei25519 and Wei448 allows easy definition of new | |||

instantiations of signature schemes and key agreement schemes already | instantiations of signature schemes and key agreement schemes already | |||

specified for traditional NIST prime curves, thereby allowing easy | specified for traditional NIST prime curves, thereby allowing easy | |||

integration with existing specifications, such as NIST SP 800-56a | integration with existing specifications, such as NIST SP 800-56a | |||

[SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005 | [SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005 | |||

[ANSI-X9.62], and fostering code reuse on platforms that already | [ANSI-X9.62], and fostering code reuse on platforms that already | |||

implement some of these schemes using elliptic curve arithmetic for | implement some of these schemes using elliptic curve arithmetic for | |||

curves in "short" Weierstrass form (see Appendix C.1). To illustrate | curves in short-Weierstrass form (see Appendix C.1). To illustrate | |||

this, we specify how to use Wei25519 and Wei448 with co-factor ECDH | this, we specify how to use Wei25519 and Wei448 with co-factor ECDH | |||

and with ECDSA, thereby giving rise to the key agreement schemes | and with ECDSA, thereby giving rise to the key agreement schemes | |||

ECDH25519 and ECDH448 and the signature schemes ECDSA25519 and | ECDH25519 and ECDH448 and the signature schemes ECDSA25519 and | |||

ECDSA448. In all these cases, implementors may use the curve | ECDSA448. In all these cases, implementors may use the curve | |||

arithmetic for the curve model of their choosing (where they can | arithmetic for the curve model of their choosing (where they can | |||

efficiently switch between representations in different curve models, | efficiently switch between representations in different curve models, | |||

if required). | if required). | |||

For ease of exposition, we consider Wei25519 first and introduce | For ease of exposition, we consider Wei25519 first and introduce | |||

Wei448 simply as an illustration of how to create other "offspring" | Wei448 simply as an illustration of how to create other "offspring" | |||

skipping to change at page 9, line 15 ¶ | skipping to change at page 9, line 24 ¶ | |||

curve Wei25519, where the signature (r,s) is represented as the | curve Wei25519, where the signature (r,s) is represented as the | |||

right-concatenation of the integers r and s, each represented as | right-concatenation of the integers r and s, each represented as | |||

fixed-size strings with tight MSB/msb ordering (see Appendix I). | fixed-size strings with tight MSB/msb ordering (see Appendix I). | |||

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

Any existing specification of cryptographic schemes using elliptic | Any existing specification of cryptographic schemes using elliptic | |||

curves in Weierstrass form and that allows introduction of a new | curves in Weierstrass form and that allows introduction of a new | |||

elliptic curve (here: Wei25519) is amenable to similar constructs, | elliptic curve (here: Wei25519) is amenable to similar constructs, | |||

thus spawning "offspring" protocols, simply by instantiating these | thus spawning "offspring" protocols, simply by instantiating these | |||

using the new curve in "short" Weierstrass form, thereby allowing | using the new curve in short-Weierstrass form, thereby allowing code | |||

code and/or specifications reuse and, for implementations that so | and/or specifications reuse and, for implementations that so desire, | |||

desire, carrying out curve computations "under the hood" on | carrying out curve computations "under the hood" on Montgomery curve | |||

Montgomery curve and twisted Edwards curve cousins hereof (where | and twisted Edwards curve cousins hereof (where these exist). This | |||

these exist). This would simply require definition of a new object | would simply require definition of a new object identifier for any | |||

identifier for any such envisioned "offspring" protocol. This could | such envisioned "offspring" protocol. This could significantly | |||

significantly simplify standardization of schemes and help keeping at | simplify standardization of schemes and help keeping at bay the | |||

bay the resource and maintenance cost of implementations supporting | resource and maintenance cost of implementations supporting algorithm | |||

algorithm agility [RFC7696]. | agility [RFC7696]. | |||

We illustrate the construction of such offspring protocols for | We illustrate the construction of such offspring protocols for | |||

Curve448, another Montgomery curve recently standardized by IETF (see | Curve448, another Montgomery curve recently standardized by IETF (see | |||

[RFC7748]). Similar to the case with Curve25519, one can represent | [RFC7748]). Similar to the case with Curve25519, one can represent | |||

points of this curve via different curve models, viz. as points of an | points of this curve via different curve models, viz. as points of an | |||

Edwards curve (Ed448) or as points of a short-Weierstrass curve | Edwards curve (Ed448) or as points of a short-Weierstrass curve | |||

(Wei448). For the specification of Wei448 and its relationship to | (Wei448). For the specification of Wei448 and its relationship to | |||

Curve448 and Ed448, see Appendix M. As with ECDH25519, one can now | Curve448 and Ed448, see Appendix M. As with ECDH25519, one can now | |||

easily define a NIST-compliant version of co-factor Diffie-Hellman | easily define a NIST-compliant version of co-factor Diffie-Hellman | |||

key agreement (denoted by ECDH448), by simply reusing the example of | key agreement (denoted by ECDH448), by simply reusing the example of | |||

skipping to change at page 14, line 8 ¶ | skipping to change at page 14, line 10 ¶ | |||

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. Private keys MUST NOT be reused | |||

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

specified in Section 4.3). | specified in Section 4.3). Similarly, 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 ECDSA448. | |||

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

The transformations between different curve models described in this | The transformations between different curve models described in this | |||

document are publicly known and, therefore, do not affect privacy | document are publicly known and, therefore, do not affect privacy | |||

provisions. | provisions. | |||

skipping to change at page 20, line 39 ¶ | skipping to change at page 21, line 5 ¶ | |||

name of the curve used with this particular instantiation of | name of the curve used with this particular instantiation of | |||

ECDH. | ECDH. | |||

When using a JOSE key for this algorithm, if the "alg" field is | When using a JOSE key for this algorithm, if the "alg" field is | |||

present, it MUST be set to the (unique) name of this particular | present, it MUST be set to the (unique) name of this particular | |||

instantiation of co-factor ECDH and the "crv" parameter MUST be set | instantiation of co-factor ECDH and the "crv" parameter MUST be set | |||

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

field is present, it MUST include "derive shared secret" for the | field is present, it MUST include "derive shared secret" for the | |||

private key. | private key. | |||

11. IANA Considerations | 11. Using Wei25519 and Wei448 with PKIX and CMS | |||

This section illustrates how to use the curves Wei25519 and Wei448 | ||||

with ECDH and ECDSA with PKIX certificates (see [RFC5280] and | ||||

[RFC5480]) and with CMS (see [RFC5652] and [RFC5753]). | ||||

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

The namedCurve field in the ECParameters field in the | ||||

SubjectPublicKeyInfo structure [RFC5280] indicates the elliptic curve | ||||

domain parameters for a specific curve, via a unique name of the | ||||

curve in question (where these are the unique object identifiers id- | ||||

Wei25519 for the curve Wei25519 and id-Wei448 for the curve Wei448). | ||||

Affine and compressed curve points are encoded using the "SEC1"- | ||||

representation (see Note 2 of Appendix I.8), using the tight MSB/msb- | ||||

ordering conventions. This is consistent with the representation in | ||||

Section 2.2 of [RFC5480], after correcting for the error in [SEC1] | ||||

(for the correction, see Note in Appendix H.1). | ||||

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

ECDSA25519, as defined in Section 4.3, is the instantiation of ECDSA | ||||

with SHA-256 and with curve Wei25519. With [RFC5480], ECDSA can be | ||||

instantiated with suitable elliptic curves and hash functions. This | ||||

allows support for ECDSA25519 by instantiating ECDSA with the curve | ||||

Wei25519 and the hash function SHA256, where curve Wei25519 is | ||||

identified by its object identifier id-wei25519 (see Section 11.1), | ||||

where ECDSA with SHA256 is identified by the object identifier id- | ||||

ecdsa-with-SHA256 (see [RFC5480]), and where all other aspects are | ||||

specified in [RFC5480]. | ||||

ECDSA448, as defined in Section 4.4, is the instantiation of ECDSA | ||||

with SHAKE256 with output size d=512 bits and with curve Wei448. | ||||

With [RFC5480], ECDSA can be instantiated with suitable elliptic | ||||

curves and hash functions. This allows support for ECDSA448 by | ||||

instantiating ECDSA with the curve Wei448 and the hash function | ||||

SHAKE256 with output size of d=512 bits, where curve Wei448 is | ||||

identified by its object identifier id-wei448 (see Section 11.1), | ||||

where ECDSA with SHAKE256 with output size of d=512 bits is | ||||

identified by the object identifier id-ecdsa-with-shake256 (see | ||||

[RFC8692]), and where all other aspects are specified in [RFC5480]. | ||||

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

With [RFC5480], the algorithm field in the SubjectPublicKeyInfo | ||||

structure indicates the algorithm and the elliptic curve domain | ||||

parameters for a specific curve, where that specification defines | ||||

three algorithm identifiers (viz. id-ecPublicKey, id-ecdh, and id- | ||||

ecmqv). Each of these algorithms can be instantiated with suitable | ||||

alliptic curves, thereby allowing support for their use with the | ||||

curves Wei25519 and Wei448, where these curves are identified by | ||||

their unique object identifiers id-wei25519 and id-wei448, | ||||

respectively, and where all other aspects are specified in [RFC5480]. | ||||

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

With [RFC5753], elliptic-curve based algorithms should use one of the | ||||

elliptic curve domain parameters specified in [RFC5480], where the | ||||

unique name of each such curve is identified by the object identifier | ||||

of this curve defined in that document. Each of these algorithms can | ||||

be instantiated with suitable elliptic curves, thereby allowing | ||||

support for their use with the curves Wei25519 and Wei448, where | ||||

these curves are identified by their unique object identifiers id- | ||||

wei25519 and id-wei448, respectively, and where all other aspects are | ||||

specified in [RFC5753]. | ||||

12. IANA Considerations | ||||

Code points are requested for curves Wei25519 and Wei448 and their | Code points are requested for curves Wei25519 and Wei448 and their | |||

use with ECDSA and co-factor ECDH, using the representation | use with ECDSA and co-factor ECDH, using the representation | |||

conventions of this document. | conventions of this document. | |||

New code points would be required in case one wishes to specify one | New code points would be required in case one wishes to specify one | |||

or more other "offspring" protocols beyond those exemplified in | or more other "offspring" protocols beyond those exemplified in | |||

Section 4.4. Specification hereof is, however, outside the scope of | Section 4.4. Specification hereof is, however, outside the scope of | |||

the current document. | the current document. | |||

11.1. IANA Considerations for Wei25519 | 12.1. OIDs for Use with PKIX and CMS | |||

11.1.1. COSE Elliptic Curves Registration | This section registers the following object identifiers for the | |||

curves introduced in this document: | ||||

a. id-Wei25519 OBJECT IDENTIFIER ::= TBD (Requested value: {iso(1) | ||||

identified-organization(3) thawte (101) 108 }); | ||||

b. id-Wei448 OBJECT IDENTIFIER ::= TBD (Requested value: {iso(1) | ||||

identified-organization(3) thawte (101) 109 }). | ||||

For a description of how these are used with PKIX certificates and | ||||

CMS, see Section 11. | ||||

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

12.2.1. COSE Elliptic Curves Registration | ||||

This section registers the following value in the IANA "COSE Elliptic | This section registers the following value in the IANA "COSE Elliptic | |||

Curves" registry [IANA.COSE.Curves]. | Curves" registry [IANA.COSE.Curves]. | |||

Name: Wei25519; | Name: Wei25519; | |||

Value: TBD (Requested value: -1); | Value: TBD (Requested value: -1); | |||

Key Type: EC2 or OKP; | Key Type: EC2 or OKP; | |||

skipping to change at page 21, line 29 ¶ | skipping to change at page 23, line 29 ¶ | |||

Change Controller: IESG; | Change Controller: IESG; | |||

Reference: specified in Appendix E.3 of this specification; for | Reference: specified in Appendix E.3 of this specification; for | |||

encodings, see Section 10.1; | encodings, see Section 10.1; | |||

Recommended: Yes. | Recommended: Yes. | |||

(Note that The "kty" value for Wei25519 may be "EC2" or "OKP".) | (Note that The "kty" value for Wei25519 may be "EC2" or "OKP".) | |||

11.1.2. COSE Algorithms Registration (1/2) | 12.2.2. COSE Algorithms Registration (1/2) | |||

This section registers the following value in the IANA "COSE | This section registers the following value in the IANA "COSE | |||

Algorithms" registry [IANA.COSE.Algorithms]. | Algorithms" registry [IANA.COSE.Algorithms]. | |||

Name: ECDSA25519; | Name: ECDSA25519; | |||

Value: TBD (Requested value: -1); | Value: TBD (Requested value: -9); | |||

Description: ECDSA with SHA-256 and curve Wei25519; | Description: ECDSA with SHA-256 and curve Wei25519; | |||

Change Controller: IESG; | Change Controller: IESG; | |||

Reference: specified in Section 4.3 of this specification; for | Reference: specified in Section 4.3 of this specification; for | |||

encodings, see Section 10.2; | encodings, see Section 10.2; | |||

Recommended: Yes. | Recommended: Yes. | |||

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

This section registers the following value in the IANA "COSE | This section registers the following value in the IANA "COSE | |||

Algorithms" registry [IANA.COSE.Algorithms]. | Algorithms" registry [IANA.COSE.Algorithms]. | |||

Name: ECDH25519; | Name: ECDH25519; | |||

Value: TBD (Requested value: -2); | Value: TBD (Requested value: -24); | |||

Description: NIST-compliant co-factor Diffie-Hellman w/ curve | Description: NIST-compliant co-factor Diffie-Hellman w/ curve | |||

Wei25519 and key derivation function HKDF SHA256; | Wei25519 and key derivation function HKDF SHA256; | |||

Change Controller: IESG; | Change Controller: IESG; | |||

Reference: specified in Section 4.1 of this specification; for | Reference: specified in Section 4.1 of this specification; for | |||

encodings, see Section 10.3; | encodings, see Section 10.3; | |||

Recommended: Yes. | Recommended: Yes. | |||

11.1.4. JOSE Elliptic Curves Registration | 12.2.4. JOSE Elliptic Curves Registration | |||

This section registers the following value in the IANA "JSON Web Key | This section registers the following value in the IANA "JSON Web Key | |||

Elliptic Curve" registry [IANA.JOSE.Curves]. | Elliptic Curve" registry [IANA.JOSE.Curves]. | |||

Curve Name: Wei25519; | Curve Name: Wei25519; | |||

Curve Description: short-Weierstrass curve Wei25519; | Curve Description: short-Weierstrass curve Wei25519; | |||

JOSE Implementation Requirements: Optional; | JOSE Implementation Requirements: Optional; | |||

Change Controller: IESG; | Change Controller: IESG; | |||

Reference: specified in Appendix E.3 of this specification; for | Reference: specified in Appendix E.3 of this specification; for | |||

encodings, see Section 10.1. | encodings, see Section 10.1. | |||

(Note that The "kty" value for Wei25519 may be "EC" or "OKP".) | (Note that The "kty" value for Wei25519 may be "EC" or "OKP".) | |||

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

This section registers the following value in the IANA "JSON Web | This section registers the following value in the IANA "JSON Web | |||

Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. | Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. | |||

Algorithm Name: ECDSA25519; | Algorithm Name: ECDSA25519; | |||

Algorithm Description: ECDSA using SHA-256 and curve Wei25519; | Algorithm Description: ECDSA using SHA-256 and curve Wei25519; | |||

Algorithm Usage Locations: alg; | Algorithm Usage Locations: alg; | |||

JOSE Implementation Requirements: Optional; | JOSE Implementation Requirements: Optional; | |||

Change Controller: IESG; | Change Controller: IESG; | |||

Reference: specified in Section 4.3 of this specification; for | Reference: specified in Section 4.3 of this specification; for | |||

encodings, see Section 10.2; | encodings, see Section 10.2; | |||

Algorithm Analysis Document(s): Section 4.3 of this specification. | Algorithm Analysis Document(s): Section 4.3 of this specification. | |||

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

This section registers the following value in the IANA "JSON Web | This section registers the following value in the IANA "JSON Web | |||

Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. | Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. | |||

Algorithm Name: ECDH25519; | Algorithm Name: ECDH25519; | |||

Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/ | Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/ | |||

curve Wei25519 and key derivation function HKDF SHA256; | curve Wei25519 and key derivation function HKDF SHA256; | |||

Algorithm Usage Locations: alg; | Algorithm Usage Locations: alg; | |||

JOSE Implementation Requirements: Optional; | JOSE Implementation Requirements: Optional; | |||

Change Controller: IESG; | Change Controller: IESG; | |||

Reference: specified in Section 4.1 of this specification; for | Reference: specified in Section 4.1 of this specification; for | |||

encodings, see Section 10.3; | encodings, see Section 10.3; | |||

Algorithm Analysis Document(s): Section 4.1 of this specification. | Algorithm Analysis Document(s): Section 4.1 of this specification. | |||

11.2. IANA Considerations for Wei448 | 12.3. COSE/JOSE IANA Considerations for Wei448 | |||

11.2.1. COSE Elliptic Curves Registration | 12.3.1. COSE Elliptic Curves Registration | |||

This section registers the following value in the IANA "COSE Elliptic | This section registers the following value in the IANA "COSE Elliptic | |||

Curves" registry [IANA.COSE.Curves]. | Curves" registry [IANA.COSE.Curves]. | |||

Name: Wei448; | Name: Wei448; | |||

Value: TBD (Requested value: -2); | Value: TBD (Requested value: -2); | |||

Key Type: EC2 or OKP; | Key Type: EC2 or OKP; | |||

skipping to change at page 24, line 5 ¶ | skipping to change at page 26, line 5 ¶ | |||

Change Controller: IESG; | Change Controller: IESG; | |||

Reference: specified in Appendix M.3 of this specification; for | Reference: specified in Appendix M.3 of this specification; for | |||

encodings, see Section 10.1; | encodings, see Section 10.1; | |||

Recommended: Yes. | Recommended: Yes. | |||

(Note that The "kty" value for Wei448 may be "EC2" or "OKP".) | (Note that The "kty" value for Wei448 may be "EC2" or "OKP".) | |||

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

This section registers the following value in the IANA "COSE | This section registers the following value in the IANA "COSE | |||

Algorithms" registry [IANA.COSE.Algorithms]. | Algorithms" registry [IANA.COSE.Algorithms]. | |||

Name: ECDSA448; | Name: ECDSA448; | |||

Value: TBD (Requested value: -47); | Value: TBD (Requested value: -48); | |||

Description: ECDSA with SHAKE256 and curve Wei448; | Description: ECDSA with SHAKE256 and curve Wei448; | |||

Change Controller: IESG; | Change Controller: IESG; | |||

Reference: specified in Section 4.4 of this specification; for | Reference: specified in Section 4.4 of this specification; for | |||

encodings, see Section 10.1; | encodings, see Section 10.1; | |||

Recommended: Yes. | Recommended: Yes. | |||

11.2.3. COSE Algorithms Registration (2/2) | 12.3.3. COSE Algorithms Registration (2/2) | |||

This section registers the following value in the IANA "COSE | This section registers the following value in the IANA "COSE | |||

Algorithms" registry [IANA.COSE.Algorithms]. | Algorithms" registry [IANA.COSE.Algorithms]. | |||

Name: ECDH448; | Name: ECDH448; | |||

Value: TBD (Requested value: -48); | Value: TBD (Requested value: -49); | |||

Description: NIST-compliant co-factor Diffie-Hellman w/ curve Wei448 | Description: NIST-compliant co-factor Diffie-Hellman w/ curve Wei448 | |||

and key derivation function HKDF SHA512; | and key derivation function HKDF SHA512; | |||

Change Controller: IESG; | Change Controller: IESG; | |||

Reference: specified in Section 4.4 of this specification; for | Reference: specified in Section 4.4 of this specification; for | |||

encodings, see Section 10.1; for key derivation, see | encodings, see Section 10.1; for key derivation, see | |||

Section 11.1 of [RFC8152]; | Section 11.1 of [RFC8152]; | |||

Recommended: Yes. | Recommended: Yes. | |||

11.2.4. JOSE Elliptic Curves Registration | 12.3.4. JOSE Elliptic Curves Registration | |||

This section registers the following value in the IANA "JSON Web Key | This section registers the following value in the IANA "JSON Web Key | |||

Elliptic Curve" registry [IANA.JOSE.Curves]. | Elliptic Curve" registry [IANA.JOSE.Curves]. | |||

Curve Name: Wei448; | Curve Name: Wei448; | |||

Curve Description: short-Weierstrass curve Wei448; | Curve Description: short-Weierstrass curve Wei448; | |||

JOSE Implementation Requirements: Optional; | JOSE Implementation Requirements: Optional; | |||

Change Controller: IESG; | Change Controller: IESG; | |||

Reference: specified in Appendix M.3 of this specification; for | Reference: specified in Appendix M.3 of this specification; for | |||

encodings, see Section 10.1. | encodings, see Section 10.1. | |||

(Note that The "kty" value for Wei448 may be "EC" or "OKP".) | (Note that The "kty" value for Wei448 may be "EC" or "OKP".) | |||

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

This section registers the following value in the IANA "JSON Web | This section registers the following value in the IANA "JSON Web | |||

Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. | Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. | |||

Algorithm Name: ECDSA448; | Algorithm Name: ECDSA448; | |||

Algorithm Description: ECDSA using SHAKE256 and curve Wei448; | Algorithm Description: ECDSA using SHAKE256 and curve Wei448; | |||

Algorithm Usage Locations: alg; | Algorithm Usage Locations: alg; | |||

JOSE Implementation Requirements: Optional; | JOSE Implementation Requirements: Optional; | |||

Change Controller: IESG; | Change Controller: IESG; | |||

Reference: specified in Section 4.4 of this specification; for | Reference: specified in Section 4.4 of this specification; for | |||

encodings, see Section 10.2; | encodings, see Section 10.2; | |||

Algorithm Analysis Document(s): Section 4.4 of this specification. | Algorithm Analysis Document(s): Section 4.4 of this specification. | |||

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

This section registers the following value in the IANA "JSON Web | This section registers the following value in the IANA "JSON Web | |||

Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. | Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. | |||

Algorithm Name: ECDH448; | Algorithm Name: ECDH448; | |||

Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/ | Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/ | |||

curve Wei448; | curve Wei448; | |||

Algorithm Usage Locations: alg; | Algorithm Usage Locations: alg; | |||

JOSE Implementation Requirements: Optional; | JOSE Implementation Requirements: Optional; | |||

Change Controller: IESG; | Change Controller: IESG; | |||

Reference: specified in Section 4.4 of this specification; for | Reference: specified in Section 4.4 of this specification; for | |||

encodings, see Section 10.3; | encodings, see Section 10.3; | |||

Algorithm Analysis Document(s): Section 4.4 of this specification. | Algorithm Analysis Document(s): Section 4.4 of this specification. | |||

12. Acknowledgements | 13. Acknowledgements | |||

Thanks to Nikolas Rosener for discussions surrounding implementation | Thanks to Nikolas Rosener for discussions surrounding implementation | |||

details of the techniques described in this document and to Phillip | details of the techniques described in this document and to Phillip | |||

Hallam-Baker for triggering inclusion of verbiage on the use of | Hallam-Baker for triggering inclusion of verbiage on the use of | |||

Montgomery ladders with recovery of the y-coordinate. Thanks to | Montgomery ladders with recovery of the y-coordinate. Thanks to | |||

Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews. | Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews. | |||

13. References | 14. References | |||

13.1. Normative References | 14.1. Normative References | |||

[ANSI-X9.62] | [ANSI-X9.62] | |||

ANSI X9.62-2005, "Public Key Cryptography for the | ANSI X9.62-2005, "Public Key Cryptography for the | |||

Financial Services Industry: The Elliptic Curve Digital | Financial Services Industry: The Elliptic Curve Digital | |||

Signature Algorithm (ECDSA)", American National Standard | Signature Algorithm (ECDSA)", American National Standard | |||

for Financial Services, Accredited Standards Committee X9, | for Financial Services, Accredited Standards Committee X9, | |||

Inc, Anapolis, MD, 2005. | Inc, Anapolis, MD, 2005. | |||

[FIPS-180-4] | [FIPS-180-4] | |||

FIPS 180-4, "Secure Hash Standard (SHS), Federal | FIPS 180-4, "Secure Hash Standard (SHS), Federal | |||

skipping to change at page 26, line 45 ¶ | skipping to change at page 28, line 45 ¶ | |||

[FIPS-202] | [FIPS-202] | |||

FIPS 202, "SHA-3 Standard: Permutation-Based Hash and | FIPS 202, "SHA-3 Standard: Permutation-Based Hash and | |||

Extendable-Output Functions, Federal Information | Extendable-Output Functions, Federal Information | |||

Processing Standards Publication 202", US Department of | Processing Standards Publication 202", US Department of | |||

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

Technology, Gaithersburg, MD, August 2015. | Technology, Gaithersburg, MD, August 2015. | |||

[I-D.ietf-cose-rfc8152bis-algs] | [I-D.ietf-cose-rfc8152bis-algs] | |||

Schaad, J., "CBOR Object Signing and Encryption (COSE): | Schaad, J., "CBOR Object Signing and Encryption (COSE): | |||

Initial Algorithms", draft-ietf-cose-rfc8152bis-algs-11 | Initial Algorithms", draft-ietf-cose-rfc8152bis-algs-12 | |||

(work in progress), July 2020. | (work in progress), September 2020. | |||

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | |||

Requirement Levels", BCP 14, RFC 2119, | Requirement Levels", BCP 14, RFC 2119, | |||

DOI 10.17487/RFC2119, March 1997, | DOI 10.17487/RFC2119, March 1997, | |||

<https://www.rfc-editor.org/info/rfc2119>. | <https://www.rfc-editor.org/info/rfc2119>. | |||

[RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data | [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data | |||

Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006, | Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006, | |||

<https://www.rfc-editor.org/info/rfc4648>. | <https://www.rfc-editor.org/info/rfc4648>. | |||

[RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., | ||||

Housley, R., and W. Polk, "Internet X.509 Public Key | ||||

Infrastructure Certificate and Certificate Revocation List | ||||

(CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008, | ||||

<https://www.rfc-editor.org/info/rfc5280>. | ||||

[RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk, | ||||

"Elliptic Curve Cryptography Subject Public Key | ||||

Information", RFC 5480, DOI 10.17487/RFC5480, March 2009, | ||||

<https://www.rfc-editor.org/info/rfc5480>. | ||||

[RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography | [RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography | |||

(ECC) Brainpool Standard Curves and Curve Generation", | (ECC) Brainpool Standard Curves and Curve Generation", | |||

RFC 5639, DOI 10.17487/RFC5639, March 2010, | RFC 5639, DOI 10.17487/RFC5639, March 2010, | |||

<https://www.rfc-editor.org/info/rfc5639>. | <https://www.rfc-editor.org/info/rfc5639>. | |||

[RFC5652] Housley, R., "Cryptographic Message Syntax (CMS)", STD 70, | ||||

RFC 5652, DOI 10.17487/RFC5652, September 2009, | ||||

<https://www.rfc-editor.org/info/rfc5652>. | ||||

[RFC5753] Turner, S. and D. Brown, "Use of Elliptic Curve | ||||

Cryptography (ECC) Algorithms in Cryptographic Message | ||||

Syntax (CMS)", RFC 5753, DOI 10.17487/RFC5753, January | ||||

2010, <https://www.rfc-editor.org/info/rfc5753>. | ||||

[RFC7049] Bormann, C. and P. Hoffman, "Concise Binary Object | [RFC7049] Bormann, C. and P. Hoffman, "Concise Binary Object | |||

Representation (CBOR)", RFC 7049, DOI 10.17487/RFC7049, | Representation (CBOR)", RFC 7049, DOI 10.17487/RFC7049, | |||

October 2013, <https://www.rfc-editor.org/info/rfc7049>. | October 2013, <https://www.rfc-editor.org/info/rfc7049>. | |||

[RFC7515] Jones, M., Bradley, J., and N. Sakimura, "JSON Web | [RFC7515] Jones, M., Bradley, J., and N. Sakimura, "JSON Web | |||

Signature (JWS)", RFC 7515, DOI 10.17487/RFC7515, May | Signature (JWS)", RFC 7515, DOI 10.17487/RFC7515, May | |||

2015, <https://www.rfc-editor.org/info/rfc7515>. | 2015, <https://www.rfc-editor.org/info/rfc7515>. | |||

[RFC7518] Jones, M., "JSON Web Algorithms (JWA)", RFC 7518, | [RFC7518] Jones, M., "JSON Web Algorithms (JWA)", RFC 7518, | |||

DOI 10.17487/RFC7518, May 2015, | DOI 10.17487/RFC7518, May 2015, | |||

skipping to change at page 28, line 9 ¶ | skipping to change at page 30, line 32 ¶ | |||

<https://www.rfc-editor.org/info/rfc8037>. | <https://www.rfc-editor.org/info/rfc8037>. | |||

[RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)", | [RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)", | |||

RFC 8152, DOI 10.17487/RFC8152, July 2017, | RFC 8152, DOI 10.17487/RFC8152, July 2017, | |||

<https://www.rfc-editor.org/info/rfc8152>. | <https://www.rfc-editor.org/info/rfc8152>. | |||

[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC | [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC | |||

2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, | 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, | |||

May 2017, <https://www.rfc-editor.org/info/rfc8174>. | May 2017, <https://www.rfc-editor.org/info/rfc8174>. | |||

[RFC8692] Kampanakis, P. and Q. Dang, "Internet X.509 Public Key | ||||

Infrastructure: Additional Algorithm Identifiers for | ||||

RSASSA-PSS and ECDSA Using SHAKEs", RFC 8692, | ||||

DOI 10.17487/RFC8692, December 2019, | ||||

<https://www.rfc-editor.org/info/rfc8692>. | ||||

[SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0", | [SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0", | |||

Standards for Efficient Cryptography, , June 2009. | Standards for Efficient Cryptography, , June 2009. | |||

[SEC2] SEC2, "SEC 2: Elliptic Curve Cryptography, Version 2.0", | [SEC2] SEC2, "SEC 2: Elliptic Curve Cryptography, Version 2.0", | |||

Standards for Efficient Cryptography, , January 2010. | Standards for Efficient Cryptography, , January 2010. | |||

[SP-800-56a] | [SP-800-56a] | |||

NIST SP 800-56a, "Recommendation for Pair-Wise Key | NIST SP 800-56a, "Recommendation for Pair-Wise Key | |||

Establishment Schemes Using Discrete Log Cryptography, | Establishment Schemes Using Discrete Log Cryptography, | |||

Revision 3", US Department of Commerce/National Institute | Revision 3", US Department of Commerce/National Institute | |||

of Standards and Technology, Gaithersburg, MD, April 2018. | of Standards and Technology, Gaithersburg, MD, April 2018. | |||

[SP-800-56c] | [SP-800-56c] | |||

NIST SP 800-56c, "Recommendation for Key-Derivation | NIST SP 800-56c, "Recommendation for Key-Derivation | |||

Methods in Key-Establishment Schemes, Revision 1", US | Methods in Key-Establishment Schemes, Revision 1", US | |||

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

Technology, Gaithersburg, MD, April 2018. | Technology, Gaithersburg, MD, April 2018. | |||

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

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

skipping to change at page 31, line 41 ¶ | skipping to change at page 34, line 29 ¶ | |||

curve; k*P is commonly referred to as scalar multiplication of P by | curve; k*P is commonly referred to as scalar multiplication of P by | |||

k.) If (P) has cardinality l, then l is called the order of P and l | k.) If (P) has cardinality l, then l is called the order of P and l | |||

is the smallest positive integer so that l*P=O. The order of curve E | is the smallest positive integer so that l*P=O. The order of curve E | |||

is the cardinality of the set of its points, commonly denoted by |E|. | is the cardinality of the set of its points, commonly denoted by |E|. | |||

A curve is cyclic if it is generated by some point of this curve. | A curve is cyclic if it is generated by some point of this curve. | |||

All curves of prime order are cyclic, while all curves of order h*n, | All curves of prime order are cyclic, while all curves of order h*n, | |||

where n is a large prime number and where h is a small number (the | where n is a large prime number and where h is a small number (the | |||

so-called co-factor), have a large cyclic subgroup of prime order n. | so-called co-factor), have a large cyclic subgroup of prime order n. | |||

In this case, a generator of order n is called a base point, commonly | In this case, a generator of order n is called a base point, commonly | |||

denoted by G, while a point of order dividing h is said to be in the | denoted by G, while a point of order dividing h is said to be in the | |||

small subgroup. For curves of prime order, this small subgroup is | small subgroup (or said to be a low-order point). For curves of | |||

the singleton set, consisting of only the identity element O. A | prime order, this small subgroup is the singleton set, consisting of | |||

point that is not in the small subgroup is said to be a high-order | only the identity element O. A point that is not in the small | |||

point (since it has order at least n). A point P of the curve is in | subgroup is said to be a high-order point (since it has order at | |||

the small subgroup if h*P=O (and is a high-order point otherwise); | least n). A point P of the curve is in the small subgroup if h*P=O | |||

this point has order n if n*P=O and if it is not the identity element | (and is a high-order point otherwise); this point has order n if | |||

O. (The latter order check is commonly called full public key | n*P=O and if it is not the identity element O. (The latter order | |||

validation.) | check is commonly called full public key validation.) | |||

If R is a point of the curve that is also contained in (P), there is | If R is a point of the curve that is also contained in (P), there is | |||

a unique integer k in the interval [0, l-1] so that R=k*P, where l is | a unique integer k in the interval [0, l-1] so that R=k*P, where l is | |||

the order of P. This number is called the discrete logarithm of R to | the order of P. This number is called the discrete logarithm of R to | |||

the base P. The discrete logarithm problem is the problem of finding | the base P. The discrete logarithm problem is the problem of finding | |||

the discrete logarithm of R to the base P for any two points P and R | the discrete logarithm of R to the base P for any two points P and R | |||

of the curve, if such a number exists. | of the curve, if such a number exists. | |||

If P is a fixed base point G of the curve, the pair (k, R:=k*G) is | If P is a fixed base point G of the curve, the pair (k, R:=k*G) is | |||

commonly called a public-private key pair, the integer k the private | commonly called a public-private key pair, the integer k the private | |||

skipping to change at page 63, line 17 ¶ | skipping to change at page 66, line 17 ¶ | |||

where alpha:=X^3+a*X+b. If alpha is not a square in GF(q), this | where alpha:=X^3+a*X+b. If alpha is not a square in GF(q), this | |||

equation does not have a solution in GF(q) and the ordered pair (X, | equation does not have a solution in GF(q) and the ordered pair (X, | |||

t) does not correspond to a point of this curve. Otherwise, there | t) does not correspond to a point of this curve. Otherwise, there | |||

are two solutions, viz. Y=sqrt(alpha) and -Y. If alpha is a nonzero | are two solutions, viz. Y=sqrt(alpha) and -Y. If alpha is a nonzero | |||

element of GF(q), one can uniquely recover the Y-coordinate for which | element of GF(q), one can uniquely recover the Y-coordinate for which | |||

par(Y):=t and, thereby, the point P:=(X, Y). This is also the case | par(Y):=t and, thereby, the point P:=(X, Y). This is also the case | |||

if alpha=0 and t=0, in which case Y=0 and the point P has order two. | if alpha=0 and t=0, in which case Y=0 and the point P has order two. | |||

However, if alpha=0 and t=1, the ordered pair (X, t) does not | However, if alpha=0 and t=1, the ordered pair (X, t) does not | |||

correspond to the outcome of the point compression function. | correspond to the outcome of the point compression function. | |||

NOTE: the procedure above corrects an error in the point | ||||

decompression procedure for Weierstrass curves defined over the prime | ||||

field GF(p) of [SEC1], which erroneously converts a purported | ||||

compressed point for which alpha=0 and t=1 (in the notation above), | ||||

to the ordered pair (0,p). | ||||

We extend the definition of the point compression function to all | We extend the definition of the point compression function to all | |||

points of the curve W_{a,b}, by associating the (non-affine) point at | points of the curve W_{a,b}, by associating the (non-affine) point at | |||

infinity O with any ordered pair compr(O):=(X,0), where X is any | infinity O with any ordered pair compr(O):=(X,0), where X is any | |||

element of GF(q) for which alpha:=X^3+a*X+b is not a square in GF(q), | element of GF(q) for which alpha:=X^3+a*X+b is not a square in GF(q), | |||

and recover this point accordingly. In this case, the point at | and recover this point accordingly. In this case, the point at | |||

infinity O can be represented by any ordered pair (X,0) of elements | infinity O can be represented by any ordered pair (X,0) of elements | |||

of GF(q) for which X^3+a*X+b is not a square in GF(q). Note that | of GF(q) for which X^3+a*X+b is not a square in GF(q). Note that | |||

this ordered pair does not satisfy the defining equation of the curve | this ordered pair does not satisfy the defining equation of the curve | |||

in question. An application may fix a specific suitable value of X | in question. An application may fix a specific suitable value of X | |||

or choose multiple such values and use this to encode additonal | or choose multiple such values and use this to encode additonal | |||

skipping to change at page 66, line 9 ¶ | skipping to change at page 69, line 17 ¶ | |||

There is a 1-1 correspondence between bit strings of length l and | There is a 1-1 correspondence between bit strings of length l and | |||

integers in the interval [0, 2^l), where the bit string | integers in the interval [0, 2^l), where the bit string | |||

X:=str(x_{l-1}, x_{l-2}, ..., x_1, x_0) corresponds to the integer | X:=str(x_{l-1}, x_{l-2}, ..., x_1, x_0) corresponds to the integer | |||

x:=x_{l-1}*2^{l-1} + x_{l-2}*2^{l-2} + ... + x_1*2 + x_0*1. (If l=0, | x:=x_{l-1}*2^{l-1} + x_{l-2}*2^{l-2} + ... + x_1*2 + x_0*1. (If l=0, | |||

the empty bit string corresponds to the integer zero.) Note that | the empty bit string corresponds to the integer zero.) Note that | |||

while the mapping from bit strings to integers is uniquely defined, | while the mapping from bit strings to integers is uniquely defined, | |||

the inverse mapping from integers to bit strings is not, since any | the inverse mapping from integers to bit strings is not, since any | |||

non-negative integer smaller than 2^t can be represented as a bit | non-negative integer smaller than 2^t can be represented as a bit | |||

string of length at least t (due to leading zero coefficients in base | string of length at least t (due to leading zero coefficients in base | |||

2 representation). The latter representation is called tight if the | 2 representation). The latter representation is called tight if the | |||

bit string representation has minimal length. This defines the | bit string representation has minimal length (the so-called bit- | |||

mapping BS2I from bit strings to integers and the mapping I2BS(x,l) | length of the integer in question). This defines the mapping BS2I | |||

from non-negative integers smaller than 2^l to bit strings of length | from bit strings to integers and the mapping I2BS(x,l) from non- | |||

l. | negative integers smaller than 2^l to bit strings of length l. | |||

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

There is a 1-1 correspondence between octet strings of length l and | There is a 1-1 correspondence between octet strings of length l and | |||

integers in the interval [0, 256^l), where the octet string | integers in the interval [0, 256^l), where the octet string | |||

X:=str(X_{l-1}, X_{l-2}, ..., X_1, X_0) corresponds to the integer | X:=str(X_{l-1}, X_{l-2}, ..., X_1, X_0) corresponds to the integer | |||

x:=X_{l-1}*256^{l-1} + X^{l-2}*256^{l-2} + ... + X_1*256 + X_0*1. | x:=X_{l-1}*256^{l-1} + X^{l-2}*256^{l-2} + ... + X_1*256 + X_0*1. | |||

(If l=0, the empty string corresponds to the integer zero.) Note | (If l=0, the empty string corresponds to the integer zero.) Note | |||

that while the mapping from octet strings to integers is uniquely | that while the mapping from octet strings to integers is uniquely | |||

defined, the inverse mapping from integers to octet strings is not, | defined, the inverse mapping from integers to octet strings is not, | |||

since any non-negative integer smaller than 256^t can be represented | since any non-negative integer smaller than 256^t can be represented | |||

as an octet string of length at least t (due to leading zero | as an octet string of length at least t (due to leading zero | |||

coefficients in base 256 representation). The latter representation | coefficients in base 256 representation). The latter representation | |||

is called tight if the octet string representation has minimal | is called tight if the octet string representation has minimal length | |||

length. This defines the mapping OS2I from octet strings to integers | (the so-called byte-length of the integer in question). This defines | |||

and the mapping I2OS(x,l) from non-negative integers smaller than | the mapping OS2I from octet strings to integers and the mapping | |||

256^l to octet strings of length l. | I2OS(x,l) from non-negative integers smaller than 256^l to octet | |||

strings of length l. | ||||

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

There is a 1-1 correspondence between octet strings of length l and | There is a 1-1 correspondence between octet strings of length l and | |||

bit strings of length 8*l, where the octet string X:=str(X_{l-1}, | bit strings of length 8*l, where the octet string X:=str(X_{l-1}, | |||

X_{l-2}, ..., X_1, X_0) corresponds to the right-concatenation of the | X_{l-2}, ..., X_1, X_0) corresponds to the right-concatenation of the | |||

8-bit strings x_{l-1}, x_{l-2}, ..., x_1, x_0, where each octet X_i | 8-bit strings x_{l-1}, x_{l-2}, ..., x_1, x_0, where each octet X_i | |||

corresponds to the 8-bit string x_i according to the mapping of | corresponds to the 8-bit string x_i according to the mapping of | |||

Appendix I.2 above. Note that the mapping from octet strings to bit | Appendix I.2 above. Note that the mapping from octet strings to bit | |||

strings is uniquely defined and so is the inverse mapping from bit | strings is uniquely defined and so is the inverse mapping from bit | |||

skipping to change at page 69, line 43 ¶ | skipping to change at page 72, line 46 ¶ | |||

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 this is indeed an ordered | |||

pair of octet strings (each of length l*m) and that the output (X,Y) | pair of octet strings (each of length l*m) and that the output (X,Y) | |||

-- if defined -- is indeed an affine point of the curve in question, | -- if defined -- is indeed an affine point of the curve in question, | |||

where this mapping fails if either condition is not satisfied. | where this mapping fails if either condition is not satisfied. | |||

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

skipping to change at page 70, line 39 ¶ | skipping to change at page 73, line 42 ¶ | |||

affine points as above (as octet string), but prepends this with the | affine points as above (as octet string), but prepends this with the | |||

1-octet prefix 0x04, and represents the identity element of the curve | 1-octet prefix 0x04, and represents the identity element of the curve | |||

as the 1-octet string 0x00. This variable-size point representation | as the 1-octet string 0x00. This variable-size point representation | |||

has the property that its 1-octet prefix identifies whether it | has the property that its 1-octet prefix identifies whether it | |||

encodes an affine curve point, a compressed point (including parity | encodes an affine curve point, a compressed point (including parity | |||

bit), or the identity element, while the remainder of this | bit), or the identity element, while the remainder of this | |||

representation uniquely determines the curve point's value. While | representation uniquely determines the curve point's value. While | |||

the description in [SEC1] only applies to Weierstrass curves, the | the description in [SEC1] only applies to Weierstrass curves, the | |||

description above applies to each of the curve models we consider | description above applies to each of the curve models we consider | |||

(i.e., these apply to Montgomery curves and twisted Edwards curves as | (i.e., these apply to Montgomery curves and twisted Edwards curves as | |||

well). Collectively, we simply refer to this as the "SEC1" point | well) and also applies to curves defined over extension fields. | |||

Collectively, we simply refer to this as the "SEC1" point | ||||

representation. | representation. | |||

Note that elements of a prime field GF(p), where p is a 255-bit prime | Note that elements of a prime field GF(p), where p is a 255-bit prime | |||

number, have a tight representation as a 32-octet string, where a | number, have a tight representation as a 32-octet string, where a | |||

fixed bit position is always set to zero. (This is the leftmost bit | fixed bit position is always set to zero. (This is the leftmost bit | |||

position of this octet string if one follows the MSB/msb | position of this octet string if one follows the MSB/msb | |||

representation conventions.) This allows the parity bit of a | representation conventions.) This allows the parity bit of a | |||

compressed point (see Appendix H) to be encoded in this bit position | compressed point (see Appendix H) to be encoded in this bit position | |||

and, thereby, allows a compressed point and an element of GF(p) to be | and, thereby, allows a compressed point and an element of GF(p) to be | |||

represented by an octet string of the same length. This is called | represented by an octet string of the same length. This is called | |||

skipping to change at page 73, line 46 ¶ | skipping to change at page 77, line 4 ¶ | |||

msb order is given by | msb order is given by | |||

t1 409531317901122685707535715924445398426503483189854716584 | t1 409531317901122685707535715924445398426503483189854716584 | |||

37762538294289253464 | 37762538294289253464 | |||

(=0x5844b232 8c4586dc 62f593c5 599c2a8c e61ba893 bb052de6 | (=0x5844b232 8c4586dc 62f593c5 599c2a8c e61ba893 bb052de6 | |||

77510a42 b3a68a5a) | 77510a42 b3a68a5a) | |||

t2 451856098332889407421278004628150814449259902023388533929 | t2 451856098332889407421278004628150814449259902023388533929 | |||

08848927625430980881 | 08848927625430980881 | |||

(=0x11598452 e65138dc ce948d7e d8f46a18 b640722c 8e170957 | (=0x11598452 e65138dc ce948d7e d8f46a18 b640722c 8e170957 | |||

751b7729 1b26e663), | 751b7729 1b26e663), | |||

where this representation is defined in Appendix K.5 and uses the | where this representation is defined in Appendix K.5 and uses the | |||

mapping of Appendix K.3.2 with the default square root function. | mapping of Appendix K.3.2 with the default square root function. | |||

This representation can also be expressed in tight LSB/msb order as | ||||

the pair ((u1,s1),(u2,s2)), where (s1,s2):=(0,0) and where | ||||

u1 545187339829846945538068364048581821018455714632595988990 | ||||

2000416117254237099 | ||||

(=0xabab17e4 f1dbafb1 ede0c4b3 bedb7734 9c85f2a7 917c5edf | ||||

ad4bd96a a7a60d0c) | ||||

u2 236263468848031270223854046645772980064576816578949344957 | ||||

7618817248044779847 | ||||

(=0x47099c3e 9b5cc8fe eaac5db0 6fb413fa b3ef4516 7bfcdc4b | ||||

8368f22e 2f343905), | ||||

where this uses the default completed mapping defined in Appendix K.6 | ||||

and the mapping of Appendix K.4.2 (with the default square root | ||||

function). | ||||

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

Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Edwards25519: | Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Edwards25519: | |||

x 25301662348702136092602268236183361085863932475593120475382959053 | x 25301662348702136092602268236183361085863932475593120475382959053 | |||

365387223252 | 365387223252 | |||

(=0x37f03bc0 1070ed12 d3218f8b ba1abb74 fd6b94eb 62033d09 | (=0x37f03bc0 1070ed12 d3218f8b ba1abb74 fd6b94eb 62033d09 | |||

83851e21 d6a460d4). | 83851e21 d6a460d4). | |||

skipping to change at page 75, line 39 ¶ | skipping to change at page 79, line 18 ¶ | |||

05479716220480287974 | 05479716220480287974 | |||

(=0x672e36c5 ae353073 cdfac343 e8297b05 1b010d0f 5b1016db | (=0x672e36c5 ae353073 cdfac343 e8297b05 1b010d0f 5b1016db | |||

dd4baf54 28068926), | dd4baf54 28068926), | |||

where this representation is defined in Appendix K.5 and uses the | where this representation is defined in Appendix K.5 and uses the | |||

mapping of Appendix K.3.3 with the default square root function and | mapping of Appendix K.3.3 with the default square root function and | |||

underlying isomorphic mapping between Edwards25519 and Curve25519 of | underlying isomorphic mapping between Edwards25519 and Curve25519 of | |||

Appendix E.2. | Appendix E.2. | |||

This representation can also be expressed in tight LSB/lsb order as | ||||

the pair ((u1,s1),(u2,s2)), where (s1,s2):=(0,1) and where | ||||

u1 224462652213914013165861386626523724285418072774741333590 | ||||

46191305234585192644 | ||||

(=0x2311ee45 c788a81b 7fcd7ae1 c6982d7b 537011fd d49e2eb4 | ||||

62b9c08c 5344058c) | ||||

u2 103951215490226901552766901992808623194604650181530822362 | ||||

9026508474142603215 | ||||

(=0xf3ed475b fd95335c 3a0ceb7e 319f8d3c cc651d5b 17eb4439 | ||||

e3b25693 0bea3240), | ||||

where this uses the default completed mapping defined in Appendix K.6 | ||||

and the mapping of Appendix K.4.3 (with the default square root | ||||

function). | ||||

J.3. Example with Wei25519 | J.3. Example with Wei25519 | |||

Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519: | Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519: | |||

X 14428294459702615171094958724191825368445920488283965295163094662 | X 14428294459702615171094958724191825368445920488283965295163094662 | |||

783879239338 | 783879239338 | |||

(=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7 | (=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7 | |||

2a41cf12 629e56aa). | 2a41cf12 629e56aa). | |||

skipping to change at page 78, line 8 ¶ | skipping to change at page 82, line 5 ¶ | |||

t2 213890166610228613105792710708385961712211281744756216061 | t2 213890166610228613105792710708385961712211281744756216061 | |||

11930888059603107561 | 11930888059603107561 | |||

(=0x2f49c121 8fed7912 031157ee ae066507 a972320b 6180e267 | (=0x2f49c121 8fed7912 031157ee ae066507 a972320b 6180e267 | |||

4025b006 2e67bee9), | 4025b006 2e67bee9), | |||

where this representation is defined in Appendix K.5 and uses the | where this representation is defined in Appendix K.5 and uses the | |||

mapping of Appendix K.3.1 with the default square root function. | mapping of Appendix K.3.1 with the default square root function. | |||

This representation can also be expressed in tight MSB/msb order as | ||||

the pair ((u1,s1),(u2,s2)), where (s1,s2):=(1,0) and where | ||||

u1 520092833970966289810117689157951302936446424265230088162 | ||||

65117106436465991934 | ||||

(=0x72fc3612 b18d2644 c2a85b3b dd66cd58 07ebf07b 2131b77d | ||||

6d7579da 5efba0fe) | ||||

u2 134005949856425653115405838878115551263976839535650697250 | ||||

78991786686428785368 | ||||

(=0x1da077cd 6fa87515 731029a8 bd88da6a 34e38b83 51191edf | ||||

8a3b92d7 ba24aad8), | ||||

where this uses the default completed mapping defined in Appendix K.6 | ||||

and the mapping of Appendix K.4.1 (with the default square root | ||||

function). | ||||

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

Pw2=(X, Y), k*Pw2=(X1, Y1), and (k+1)*Pw2=(X2, Y2) with Wei25519.2: | Pw2=(X, Y), k*Pw2=(X1, Y1), and (k+1)*Pw2=(X2, Y2) with Wei25519.2: | |||

X 17830493209951148331008014701079988862634531394137235438571836389 | X 17830493209951148331008014701079988862634531394137235438571836389 | |||

227198459763 | 227198459763 | |||

(=0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c | (=0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c | |||

f21c8672 d1ecaf73). | f21c8672 d1ecaf73). | |||

skipping to change at page 79, line 35 ¶ | skipping to change at page 84, line 5 ¶ | |||

t2 361115271162391608083096560179337391059615651279123199921 | t2 361115271162391608083096560179337391059615651279123199921 | |||

18531180247832114098 | 18531180247832114098 | |||

(=0x4fd66668 e7174775 de44c852 92df8cfe b9832ef8 2570b3b8 | (=0x4fd66668 e7174775 de44c852 92df8cfe b9832ef8 2570b3b8 | |||

fe5ec21a b2d4b3b2), | fe5ec21a b2d4b3b2), | |||

where this representation is defined in Appendix K.5 and uses the | where this representation is defined in Appendix K.5 and uses the | |||

mapping of Appendix K.3.1 with the default square root function. | mapping of Appendix K.3.1 with the default square root function. | |||

This representation can also be expressed in tight MSB/msb order as | ||||

the pair ((u1,s1),(u2,s2)), where (s1,s2):=(1,0) and where | ||||

u1 138215499313862453472915174740765454800858627563772726738 | ||||

62176256261157017834 | ||||

(=0x1e8eb854 2ce139f7 fdbf2059 ac257c89 d7e2e5fe 9c4b97e6 | ||||

7656d42c 590bd8ea) | ||||

u2 528750192685398685104289021251049791405104665681275304080 | ||||

7706116783659458600 | ||||

(=0x0bb09eba b0470a84 0ce1ba90 0aeab208 7e8d4760 1309d7af | ||||

e3712e1f 2232a028), | ||||

where this uses the default completed mapping defined in Appendix K.6 | ||||

and the mapping of Appendix K.4.1 (with the default square root | ||||

function). | ||||

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

Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei25519.-3: | Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei25519.-3: | |||

X 14780197759513083469009623947734627174363231692126610860256057394 | X 14780197759513083469009623947734627174363231692126610860256057394 | |||

455099634096 | 455099634096 | |||

(=0x20ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00 | (=0x20ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00 | |||

eb4c9272 03ca71b0). | eb4c9272 03ca71b0). | |||

skipping to change at page 81, line 14 ¶ | skipping to change at page 86, line 5 ¶ | |||

t2 269945781324580189815142015663892935722419453863927287235 | t2 269945781324580189815142015663892935722419453863927287235 | |||

57891665397640090729 | 57891665397640090729 | |||

(=0x3bae63c8 70f60de0 c2e35f94 d24220f1 bb6efd00 37625869 | (=0x3bae63c8 70f60de0 c2e35f94 d24220f1 bb6efd00 37625869 | |||

f84923de ff4c5469), | f84923de ff4c5469), | |||

where this representation is defined in Appendix K.5 and uses the | where this representation is defined in Appendix K.5 and uses the | |||

mapping of Appendix K.3.1 with the default square root function. | mapping of Appendix K.3.1 with the default square root function. | |||

This representation can also be expressed in tight MSB/msb order as | ||||

the pair ((u1,s1),(u2,s2)), where (s1,s2):=(1,1) and where | ||||

u1 273592510979600674027837477146355037032732195078153389134 | ||||

81162438438522584713 | ||||

(=0x3c7cc990 81eed784 9ca746d7 c479a902 ce9de65f 1150e7b9 | ||||

c87d08d2 9785fe89) | ||||

u2 271488765024747755704729103260177059745349171282146823458 | ||||

00069381584030663589 | ||||

(=0x3c05b835 1283fca7 705eba74 1e6b853e db3ed5dc d1891daa | ||||

c1643d8d d63a03a5), | ||||

where this uses the default completed mapping defined in Appendix K.6 | ||||

and the mapping of Appendix K.4.1 (with the default square root | ||||

function). | ||||

Appendix K. Auxiliary Functions | Appendix K. Auxiliary Functions | |||

This section illustrates how one could implement common routines, | This section illustrates how one could implement common routines, | |||

such as taking square roots and inverses in finite fields, and how to | such as taking square roots and inverses in finite fields, and how to | |||

map field elements to curve points and to curve points that avoid | map field elements to curve points and to curve points that avoid | |||

some outliers. | 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). | |||

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

skipping to change at page 83, line 10 ¶ | skipping to change at page 88, line 16 ¶ | |||

point of W_{a,b}, depending on whether f(X) is a square in GF(q). | point of W_{a,b}, depending on whether f(X) is a square in GF(q). | |||

a. If f(X) is a square in GF(q) and Y:=sqrt(f(X)), then t is mapped | a. If f(X) is a square in GF(q) and Y:=sqrt(f(X)), then t is mapped | |||

to the point P(t):=(X, Y); | to the point P(t):=(X, Y); | |||

b. If f(X) is not a square in GF(q) and Y':=sqrt(f(X')), then t is | b. If f(X) is not a square in GF(q) and Y':=sqrt(f(X')), then t is | |||

mapped to the point P(t):=(X', -Y'). | mapped to the point P(t):=(X', -Y'). | |||

Formally, this mapping is not properly defined, since a nonzero | Formally, this mapping is not properly defined, since a nonzero | |||

square y:=x^2 in GF(q) has two solutions, viz. x and -x; it is | square y:=x^2 in GF(q) has two solutions, viz. x and -x; it is | |||

properly defined, however, if one designates for each element in | properly defined, however, if one designates for each element of | |||

GF(q) that is a square in GF(q) precisely one square root as "the" | GF(q) that is a square in GF(q) precisely one square root as "the" | |||

square root of this element. Note that always picking the square | square root of this element. Note that always picking the square | |||

root with zero parity (see Appendix H) satisfies this condition | root with zero parity (see Appendix H) satisfies this condition | |||

(henceforth called the default square root function). | (henceforth called the default square root function). | |||

If -1 is not a square in GF(q), this element is mapped to the point | If -1 is not a square in GF(q), this element is mapped to the point | |||

at infinity O of W_{a,b}. | at infinity O of W_{a,b}. | |||

The set of points of W_{a,b} that arises this way has size roughly | The set of points of W_{a,b} that arises this way has size roughly | |||

3/8 of the order of the curve and each such point arises as image of | 3/8 of the order of the curve and each such point arises as image of | |||

one or two t values. Further details are out of scope. | one or two t values. Further details are out of scope. | |||

NOTE 1: If -1 is not a square in GF(q), the mapping above yields the | NOTE 1: If -1 is not a square in GF(q), the mapping above yields the | |||

point at infinity for t=-1. One can modify this mapping, by mapping | point at infinity for t=-1. One can modify this mapping, by mapping | |||

the element -1 to any suitable point P0 of W_{a,b} (e.g., its base | the element -1 to any suitable point P0 of W_{a,b} (e.g., its base | |||

point G or any other affine point) and leaving the remainder of the | point G or any other affine point) and leaving the remainder of the | |||

mapping the same. Suitability of such a modification is application- | mapping the same. Suitability of such a modification is application- | |||

specific. Details are out of scope. | specific. Details are out of scope. | |||

NOTE 2: The description above assumes that the domain parameters a | NOTE 2: The description above assumes that the domain parameters a | |||

and b of the Weierstrass curve are nonzero. If this is not the case, | and b of the Weierstrass curve W_{a,b} are nonzero. If this is not | |||

one can often find an isogenous curve W_{a',b'} for which the domain | the case, one can often find an isogenous curve W_{a',b'} for which | |||

parameters a' and b' are nonzero. If so, one can map elements of | the domain parameters a' and b' are nonzero. If so, one can map | |||

GF(q) that are not a square in GF(q) to points of W_{a,b} via | elements of GF(q) that are not a square in GF(q) to points of W_{a,b} | |||

function composition, where one uses the mapping above to arrive at a | via function composition, where one uses the mapping above to arrive | |||

point of W_{a',b'} and where one subsequently uses the dual isogeny | at a point of W_{a',b'} and where one subsequently uses the dual | |||

from W_{a',b'} to W_{a,b} to arrive at a point of W_{a,b}. As an | isogeny from W_{a',b'} to W_{a,b} to arrive at a point of W_{a,b}. As | |||

example, one can show that if a is zero and if -4*b is a cube in | an example, one can show that if a is zero and if -4*b is a cube in | |||

GF(q) (such as is the case with, e.g., the "BitCoin" curve secp256k1 | GF(q) (such as is the case with, e.g., the "BitCoin" curve secp256k1 | |||

[SEC2]), this curve is 3-isogenous to a curve with this property and | [SEC2]), this curve is 3-isogenous to a curve with this property and | |||

the strategy above applies (for an example with secp256k1, see | the strategy above applies (for an example with secp256k1, see | |||

Appendix L). Further details are out of scope. | Appendix L). Further details are out of scope. | |||

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

The description below assumes that the domain parameter A of the | The description below assumes that the domain parameter A of the | |||

Montgomery curve M_{A,B} is nonzero. For ease of exposition, we | Montgomery curve M_{A,B} is nonzero. For ease of exposition, we | |||

define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of | define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of | |||

skipping to change at page 84, line 16 ¶ | skipping to change at page 89, line 26 ¶ | |||

on whether f(u)/B is a square in GF(q). | on whether f(u)/B is a square in GF(q). | |||

a. If f(u)/B is a square in GF(q) and v:=sqrt(f(u)/B), then t is | a. If f(u)/B is a square in GF(q) and v:=sqrt(f(u)/B), then t is | |||

mapped to the point P(t):=(u, v); | mapped to the point P(t):=(u, v); | |||

b. If f(u)/B is a not a square in GF(q) and v':=sqrt(f(u')/B), then | b. If f(u)/B is a not a square in GF(q) and v':=sqrt(f(u')/B), then | |||

t is mapped to the point P(t):=(u', -v'). | t is mapped to the point P(t):=(u', -v'). | |||

As before, formally, this mapping is not properly defined, since a | As before, formally, this mapping is not properly defined, since a | |||

nonzero square y:=x^2 in GF(q) has two solutions, viz. x and -x; it | nonzero square y:=x^2 in GF(q) has two solutions, viz. x and -x; it | |||

is properly defined, however, if one designates for each element in | is properly defined, however, if one designates for each element of | |||

GF(q) that is a square in GF(q) precisely one square root as "the" | GF(q) that is a square in GF(q) precisely one square root as "the" | |||

square root of this element. Note that always picking the square | square root of this element. Note that always picking the square | |||

root with zero parity (see Appendix H) satisfies this condition | root with zero parity (see Appendix H) satisfies this condition | |||

(henceforth called the default square root function). | (henceforth called the default square root function). | |||

If -1 is not a square in GF(q), this element is mapped to the point | If -1 is not a square in GF(q), this element is mapped to the point | |||

at infinity O of M_{A,B}. | at infinity O of M_{A,B}. | |||

The set of points of M_{A,B} that arises this way has size roughly | The set of points of M_{A,B} that arises this way has size roughly | |||

1/2 of the order of the curve and each such point arises as image of | 1/2 of the order of the curve and each such point arises as image of | |||

precisely one t value. Further details are out of scope. | precisely one t value. Further details are out of scope. | |||

NOTE 1: If -1 is not a square in GF(q), the mapping above yields the | NOTE 1: If -1 is not a square in GF(q), the mapping above yields the | |||

point at infinity for t=-1. One can modify this mapping, by mapping | point at infinity for t=-1. One can modify this mapping, by mapping | |||

the element -1 to any suitable point P0 of M_{a,b} (e.g., its base | the element -1 to any suitable point P0 of M_{a,b} (e.g., its base | |||

point G or any other affine point) and leaving the remainder of the | point G or any other affine point) and leaving the remainder of the | |||

mapping the same. Suitability of such a modification is application- | mapping the same. Suitability of such a modification is application- | |||

specific. Details are out of scope. | specific. Details are out of scope. | |||

NOTE 2: The description above assumes that the domain parameter A of | NOTE 2: The description above assumes that the domain parameter A of | |||

the Montgomery curve is nonzero. If this is not the case, the curve | the Montgomery curve M_{A,B} is nonzero. If this is not the case, | |||

is a Weierstrass curve for which the domain parameter b is zero and | the curve is a Weierstrass curve for which the domain parameter b is | |||

Note 2 of Appendix K.3.1 applies. If q = 3 (mod 4), an even simpler | zero and Note 2 of Appendix K.3.1 applies. If q = 3 (mod 4), an even | |||

approach is possible, where one modifies the construction above and | simpler approach is possible, where one modifies the construction | |||

simply takes u:=t and u':=-t (which works, since -1 is not a square | above and simply takes u:=t and u':=-t (which works, since -1 is not | |||

in GF(q) and f(-t)=-f(t)). In this case, this construction can be | a square in GF(q) and f(-t)=-f(t)). In this case, this construction | |||

extended to all elements t of GF(q) and, if so, yields a 1-1 mapping | can be extended to all elements t of GF(q) and, if so, yields a 1-1 | |||

between GF(q) and all affine curve points. | mapping between GF(q) and all affine curve points. | |||

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

One can map elements of GF(q) that are not a square in GF(q) to | One can map elements of GF(q) that are not a square in GF(q) to | |||

points of the twisted Edwards curve E_{a,d} via function composition, | points of the twisted Edwards curve E_{a,d} via function composition, | |||

where one uses the mapping of Appendix K.3.1 to arrive at a point of | where one uses the mapping of Appendix K.3.1 to arrive at a point of | |||

the Weierstrass curve W_{a,b} and where one subsequently uses the | the Weierstrass curve W_{a,b} and where one subsequently uses the | |||

isomorphic mapping between twisted Edwards curves and Weierstrass | isomorphic mapping between twisted Edwards curves and Weierstrass | |||

curves of Appendix D.3 to arrive at a point of E_{a,d}. Another | curves of Appendix D.3 to arrive at a point of E_{a,d}. Another | |||

mapping is obtained by function composition, where one instead uses | mapping is obtained by function composition, where one instead uses | |||

skipping to change at page 87, line 20 ¶ | skipping to change at page 93, line 5 ¶ | |||

up to two values of the pair (t,s). Further details are out of | up to two values of the pair (t,s). Further details are out of | |||

scope. | scope. | |||

From the group law for Montgomery curves (see Appendix C.2) it | From the group law for Montgomery curves (see Appendix C.2) it | |||

follows that one can express the coordinates of Q(t,s), with t<>-1, | follows that one can express the coordinates of Q(t,s), with t<>-1, | |||

in terms of the u-coordinates of P0 and P(t) and the product of their | in terms of the u-coordinates of P0 and P(t) and the product of their | |||

v-coordinates. (Here, observe that B*v0*v is a square root of | v-coordinates. (Here, observe that B*v0*v is a square root of | |||

f(u0)*f(u).) Thus, Q(t,s) can be computed without the need to fully | f(u0)*f(u).) Thus, Q(t,s) can be computed without the need to fully | |||

compute P(t). | compute P(t). | |||

+----------------------------+------------------------+ | +----------------------------+------------------------+-------------+ | |||

| Curve | Fixed curve offset P0 | | | Curve | Fixed curve offset P0 | Non-Square | | |||

+----------------------------+------------------------+ | +----------------------------+------------------------+-------------+ | |||

| NIST P-224 [FIPS-186-4] | Base point (Gx,Gy) | | | NIST P-224 [FIPS-186-4] | Base point (Gx,Gy) | 11 | | |||

| NIST P-256 [FIPS-186-4] | P0:=(0,y) with y even | | | NIST P-256 [FIPS-186-4] | P0:=(0,y), y even | -1 | | |||

| NIST P-384 [FIPS-186-4] | P0:=(0,y) with y even | | | NIST P-384 [FIPS-186-4] | P0:=(0,y), y even | -1 | | |||

| NIST P-521 [FIPS-186-4] | P0:=(0,y) with y even | | | NIST P-521 [FIPS-186-4] | P0:=(0,y), y even | -1 | | |||

| Brainpool224r1 [RFC5639] | Base point (Gx, Gy) | | | Brainpool224r1 [RFC5639] | Base point (Gx, Gy) | -1 | | |||

| Brainpool256r1 [RFC5639] | Base point (Gx, Gy) | | | Brainpool256r1 [RFC5639] | Base point (Gx, Gy) | -1 | | |||

| Brainpool320r1 [RFC5639] | Base point (Gx, Gy) | | | Brainpool320r1 [RFC5639] | Base point (Gx, Gy) | -1 | | |||

| Brainpool384r1 [RFC5639] | Base point (Gx, Gy) | | | Brainpool384r1 [RFC5639] | Base point (Gx, Gy) | -1 | | |||

| Brainpool512r1 [RFC5639] | P0:=(3,y), y even | | | Brainpool512r1 [RFC5639] | P0:=(3,y), y even | -1 | | |||

| Curve25519 [RFC7748] | P0:=(90,v), v even | | | Curve25519 [RFC7748] | P0:=(90,v), v even | 2 | | |||

| Curve448 [RFC7748] | P0:=(50,v), v even | | | Wei25519 [Appendix E.3] | P0:=(3,y), y even | 2 | | |||

| Wei25519 [Appendix E.3] | P0:=(3,y), y even | | | Wei25519.2 [Appendix G.3] | P0:=(244,y), y even | 2 | | |||

| Wei25519.2 [Appendix G.3] | P0:=(244,y), y even | | | Wei25519.-3 [Appendix G.3] | P0:=(41,y), y even | 2 | | |||

| Wei25519.-3 [Appendix G.3] | P0:=(41,y), y even | | | Curve448 [RFC7748] | P0:=(50,v), v even | -1 | | |||

| secp256k1.m [Appendix L.3] | P0:=(0,y), y even | | | Wei448 [Appendix M.3] | P0:=(18,y), y even | -1 | | |||

+----------------------------+------------------------+ | | Wei448.1 [Appendix N.3] | P0:=(10,y), y even | -1 | | |||

| Wei448.-3 [Appendix N.3] | P0:=(8,y), y even | -1 | | ||||

| secp256k1.m [Appendix L.3] | P0:=(0,y), y even | -1 | | ||||

+----------------------------+------------------------+-------------+ | ||||

Table 1: Curve offsets P0 for mappings that avoid low-order points | Table 1: Fixed curve offsets for mappings that avoid low-order | |||

points, for some curves of practical interest, including listing of | ||||

fixed non-square elements of their underlying finite fields. | ||||

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

One can map elements of GF(q) that are not a square in GF(q) to | One can map elements of GF(q) that are not a square in GF(q) to | |||

points of the twisted Edwards curve E_{a,d} via function composition, | points of the twisted Edwards curve E_{a,d} via function composition, | |||

where one uses the mapping of Appendix K.4.1 to arrive at a point of | where one uses the mapping of Appendix K.4.1 to arrive at a point of | |||

the Weierstrass curve W_{a,b} that does not have low order and where | the Weierstrass curve W_{a,b} that is not in the small subgroup and | |||

one subsequently uses the isomorphic mapping between twisted Edwards | where one subsequently uses the isomorphic mapping between twisted | |||

curves and Weierstrass curves of Appendix D.3 to arrive at a point of | Edwards curves and Weierstrass curves of Appendix D.3 to arrive at a | |||

E_{a,d} with this property. Another mapping is obtained by function | point of E_{a,d} with this property. Another mapping is obtained by | |||

composition, where one instead uses the mapping of Appendix K.4.2 to | function composition, where one instead uses the mapping of | |||

arrive at a point of the Montgomery curve M_{A,B} that does not have | Appendix K.4.2 to arrive at a point of the Montgomery curve M_{A,B} | |||

low order and where one subsequently uses the isomorphic mapping | that does not have low order and where one subsequently uses the | |||

between twisted Edwards curves and Montgomery curves of Appendix D.1 | isomorphic mapping between twisted Edwards curves and Montgomery | |||

to arrive at a point of E_{a,d} with this property. Obviously, one | curves of Appendix D.1 to arrive at a point of E_{a,d} with this | |||

can use function composition (now using the respective pre-images - | property. Obviously, one can use function composition (now using the | |||

if these exist) to realize the pre-images of either mapping. | respective pre-images - if these exist) to realize the pre-images of | |||

either mapping. | ||||

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

The mappings of Appendix K.3 allow one to represent a curve point Q | The mappings of Appendix K.3 allow one to represent a curve point Q | |||

as a specific element t of GF(q), provided this point arises as a | as a specific element t of GF(q), provided this point arises as a | |||

point in the range of the mapping at hand. For Montgomery curves and | point in the range of the mapping at hand. For Montgomery curves and | |||

twisted Edwards curves, this covers roughly half of the curve points; | twisted Edwards curves, this covers roughly half of the curve points; | |||

for Weierstrass curves, roughly 3/8 of the curve points. One can | for Weierstrass curves, roughly 3/8 of the curve points. One can | |||

extend the mappings above, by mapping a pair (t1, t2) of inputs to | extend the mappings above, by mapping a pair (t1, t2) of inputs to | |||

the point Q:=P2(t1, t2):=P(t1) + P(t2). In this case, each curve | the point Q:=P2(t1, t2):=P(t1) + P(t2). In this case, each curve | |||

skipping to change at page 89, line 14 ¶ | skipping to change at page 95, line 8 ¶ | |||

NOTE 1: The main difference between the two constructions above is | NOTE 1: The main difference between the two constructions above is | |||

that that the first construction uses the mappings to curve points | that that the first construction uses the mappings to curve points | |||

described in Appendix K.3, while the second construction uses the | described in Appendix K.3, while the second construction uses the | |||

mappings to high-order curve points described in Appendix K.4. Note | mappings to high-order curve points described in Appendix K.4. Note | |||

that Q2((t1,s1), (t2,s2)) assumes all values (+/-) P(t1) (+/-) P(t2) | that Q2((t1,s1), (t2,s2)) assumes all values (+/-) P(t1) (+/-) P(t2) | |||

if one considers all possible values for the binary digits s1 and s2. | if one considers all possible values for the binary digits s1 and s2. | |||

(This, thereby, includes the value P2(t1, t2).) | (This, thereby, includes the value P2(t1, t2).) | |||

NOTE 2: The results on the statistical distributions mentioned above | NOTE 2: The results on the statistical distributions mentioned above | |||

still hold if one makes a few localized changes to the constructions. | still hold in practice if one makes a few localized changes to the | |||

In particular, these are independent of the specific choices for the | constructions. In particular, these are independent of the specific | |||

point P0 (used with input -1 with the mappings of Appendix K.3, if | choices for the point P0 (used with input -1 with the mappings of | |||

applicable, respectively, used with the mappings of Appendix K.4) and | Appendix K.3, if applicable, respectively, used with the mappings of | |||

also still hold if one re-defines the mappings P2 or Q2 locally so as | Appendix K.4) and also still hold if one re-defines the mappings P2 | |||

to avoid points in the small subgroup. | or Q2 locally so as to avoid points in the small subgroup. | |||

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

The mappings of Appendix K.4 operate on input pairs (t, s), where t | The mappings of Appendix K.4 operate on input pairs (t, s), where t | |||

is an element of GF(q) that is not a square in GF(q) and where s is a | is an element of GF(q) that is not a square in GF(q) and where s is a | |||

binary digit from the set {0,1}. One can use these mappings to | binary digit from the set {0,1}. One can use these mappings to | |||

produce a mapping from the nonzero elements of GF(q) to points of a | produce mappings that operate on input pairs (u, s), where u is any | |||

particular curve via function composition, where one first maps any | nonzero element of GF(q), via function composition, where one first | |||

nonzero element u of GF(q) to the pair (t,s):=(delta*u^2, par(u)), | maps the pair (u,s) to the pair (t,s):=(delta*u^2,s), where delta is | |||

where delta is a fixed element of GF(q) that is not a square in | a fixed element of GF(q) that is not a square in GF(q), and where one | |||

GF(q), and where one subsequently applies any of the mappings to | subsequently applies any of forementioned mappings to the resulting | |||

yield a point of the curve in question. The resulting mapping from | pair to yield a point of the curve in question. The resulting | |||

the nonzero elements of GF(q) to high-order curve points can be | mapping to high-order curve points can be extended further to one | |||

extended further to one that operates on all elements of GF(q) by | that operates on all elements of GF(q)x{0,1} by mapping each input | |||

mapping 0 to any fixed high-order point P1 of the curve in question. | (u, s) with u=0 to any fixed high-order point P1 of the curve in | |||

The resulting mapping is uniquely defined after fixing the curve | question. The resulting mapping is uniquely defined after fixing the | |||

offset P0 (used with the mappings of Appendix K.4), the high-order | curve offset P0 (used with the mappings of Appendix K.4), the high- | |||

point P1 (used for input 0 above), and the non-square element delta | order point P1 (used for inputs with u=0 above), and the non-square | |||

of GF(q) (used for nonzero inputs above). | element delta of GF(q) (used for nonzero inputs u above). | |||

For the mappings of Appendix K.3, one can use a similar function | For the mappings of Appendix K.3, one can use a similar function | |||

composition, where one simply drops the binary digit s and maps 0 to | composition, where one simply drops the binary digit s and maps 0 to | |||

the point at infinity or any other suitable curve point P1. As | the point at infinity or any other suitable curve point P1. As | |||

before, the resulting mapping is uniquely defined after fixing the | before, the resulting mapping is uniquely defined after fixing the | |||

point P0 (for input -1 with the mappings of Appendix K.3, if | point P0 (for input -1 with the mappings of Appendix K.3, if | |||

applicable), the point P1 (used for input 0 above), and the non- | applicable), the point P1 (used for input u=0 above), and the non- | |||

square element delta of GF(q) (used for nonzero inputs above). | square element delta of GF(q) (used for nonzero inputs u above). | |||

Further details are out of scope. | Further details are out of scope. | |||

Similarly, one can use the completed mappings above to map a pair | Similarly, one can use the completed mappings above to map a pair | |||

(u1, u2) of elements of GF(q) to a point of a curve, via function | ((u1,s1), (u2,s2)) of elements of GF(q)x{0,1} to a point of a curve, | |||

composition, where, in the first case, one first maps the pair (u1, | via function composition, where, in the first case, one first maps | |||

u2) to the pair ((t1,s1), (t2,s2)):=((delta*u1^2, par(u1)), | the pair ((u1,s1),(u2,s2)) to the pair ((t1,s1), | |||

(delta*u2^2, par(u2))) and subsequently computes Q2compl((t1,s1), | (t2,s2)):=((delta*u1^2, s1), (delta*u2^2, s2)) and subsequently | |||

(t2,s2)):=Qcompl(t1,s1) - Qcompl(t2,s2), where Qcompl(t,s):=Q(t,s) if | computes Q2compl((t1,s1), (t2,s2)):=Qcompl(t1,s1) - Qcompl(t2,s2), | |||

t is nonzero and where Qcompl(0,s):=P0 otherwise (irrespective of the | where Qcompl(t,s):=Q(t,s) if t is nonzero and where Qcompl(0,s):=P0 | |||

value of s). In the second case, one first maps the pair (u1, u2) to | otherwise (irrespective of the value of s). In the second case, one | |||

the pair (t1, t2):=(delta*u1^2, delta*u2^2) and subsequently computes | first maps the pair (u1, u2) to the pair (t1, t2):=(delta*u1^2, | |||

P2compl(t1, t2):=Pcompl(t1) + Pcompl(t2), where Pcompl(t):=P(t) if t | delta*u2^2) and subsequently computes P2compl(t1, t2):=Pcompl(t1) + | |||

is nonzero and where Pcompl(0):=P1 otherwise. In either case, again, | Pcompl(t2), where Pcompl(t):=P(t) if t is nonzero and where | |||

the resulting mapping is uniquely defined after fixing the points P0 | Pcompl(0):=P1 otherwise. In either case, again, the resulting | |||

and P1 and the non-square element delta of GF(q). | mapping is uniquely defined after fixing the points P0 and P1 and the | |||

non-square element delta of GF(q). | ||||

NOTE 1: Each of the above mappings is fully and unambiguously defined | ||||

by the triple (P0,P1,delta). One can locally change this mapping so | ||||

as to avoid points in the small subgroup, should these otherwise | ||||

occur, e.g., by setting any such re-defined image to any fixed high- | ||||

order point P2 of the curve in question. In this case, the | ||||

corresponding mapping is uniquely defined by the quadruple | ||||

(P0,P1,P2,delta) and -- in practice -- has the same statistical | ||||

distribution properties as the original mapping (see NOTE 2 of | ||||

Appendix K.5). For each curve in Table 1, these completed mappings | ||||

are uniquely defined by the mentioned fixed curve offset P0 and non- | ||||

square element delta of GF(q), if one defines P2:=P1:=P0 (henceforth | ||||

called the default completed mappings). | ||||

NOTE 2: For elliptic curves defined over prime fields (i.e., q:=p) | ||||

one can relax the completed mappings above and show that the | ||||

statistical properties for randomized representations still hold if | ||||

u1 is a random element of a sufficiently large interval in GF(p) and | ||||

if u2 is a random element of a sufficiently large subset of GF(p). | ||||

This allows generating u1 and u2, e.g., each as random bit strings of | ||||

length m-1, where m is the bit-size of p, thereby allowing the pair | ||||

(u1, u2) -- a random (2*m-2)-bit string -- to be used unaltered in | ||||

this construction, without the need to carry out a reduction modulo p | ||||

first. Further details are out of scope of this document. | ||||

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

This section illustrates how isogenies can be used to yield curves | This section illustrates how isogenies can be used to yield curves | |||

with specific properties (here, illustrated for the "BitCoin" curve | with specific properties (here, illustrated for the "BitCoin" curve | |||

secp256k1). | secp256k1). | |||

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

The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined | The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined | |||

skipping to change at page 99, line 34 ¶ | skipping to change at page 106, line 7 ¶ | |||

infinity of Wei448.1. (Here, we used the mapping of Appendix F.3.) | infinity of Wei448.1. (Here, we used the mapping of Appendix F.3.) | |||

Under this mapping, the base point (GX, GY) of Wei448 corresponds to | Under this mapping, the base point (GX, GY) of Wei448 corresponds to | |||

the base point (G1X,G1Y) of Wei448.1. The inverse mapping maps the | the base point (G1X,G1Y) of Wei448.1. The inverse mapping maps the | |||

affine point (X', Y') of Wei448.1 to (X,Y):=(X'/s^2,Y'/s^3) of | affine point (X', Y') of Wei448.1 to (X,Y):=(X'/s^2,Y'/s^3) of | |||

Wei448, while mapping the point at infinity O of Wei448.1 to the | Wei448, while mapping the point at infinity O of Wei448.1 to the | |||

point at infinity O of Wei448. Note that this mapping (and its | point at infinity O of Wei448. Note that this mapping (and its | |||

inverse) involves a modular multiplication of both coordinates with | inverse) involves a modular multiplication of both coordinates with | |||

fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which | fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which | |||

can be precomputed. | can be precomputed. | |||

Each affine point (X,Y) of Wei448 for which the Y-coordinate is | The point at infinity and the point (A/3,0) of order two of Wei448 | |||

nonzero (i.e., each point with order larger than two) corresponds to | both correspond to the point at infinity of Wei448.-3, while each | |||

the point (X',Y'):=(X1*t^2,Y1*t^3) of Wei448.-3, where | other point (X,Y) of Wei448 corresponds to the point | |||

(X',Y'):=(X1*t^2,Y1*t^3) of Wei448.-3, where | ||||

(X1,Y1)=(u(X)/w(X),Y*v(X)/w(X)^2), where u, v, and w are the | (X1,Y1)=(u(X)/w(X),Y*v(X)/w(X)^2), where u, v, and w are the | |||

polynomials with coefficients in GF(p) as defined in Appendix N.4.1 | polynomials with coefficients in GF(p) as defined in Appendix N.4.1 | |||

and where t is the element of GF(p) defined by | and where t is the element of GF(p) defined by | |||

t 23579450751475691430882365546539966269774125426758968522698856022 | t 23579450751475691430882365546539966269774125426758968522698856022 | |||

13378944265540874438945283200254318223329383397068961863760712339 | 13378944265540874438945283200254318223329383397068961863760712339 | |||

07365 | 07365 | |||

(=0x530c9a1d7cf071d09646b83db246626b4e57ba5d6a791bef761972543209d | (=0x530c9a1d 7cf071d0 9646b83d b246626b 4e57ba5d 6a791bef | |||

c5c20d81498d5ab8d7a2fb22507ca68c040a6c82eb3b6c7aaa5), | 76197254 3209dc5c 20d81498 d5ab8d7a 2fb22507 ca68c040 a6c82eb3 | |||

b6c7aaa5). | ||||

while the point at infinity and the point (A/3,0) of order two of | (Here, we used the isogenous mapping of Appendix F.4.) Under this | |||

Wei448 corresponds to the point at infinity of Wei448.-3. (Here, we | isogenous mapping, the base point (GX,GY) of Wei448 corresponds to | |||

used the isogenous mapping of Appendix F.4.) Under this isogenous | the base point (G3X,G3Y) of Wei448.-3. The dual isogeny maps the | |||

mapping, the base point (GX,GY) of Wei448 corresponds to the base | point at infinity O and the point (tau,0) of order two of Wei448.-3, | |||

point (G3X,G3Y) of Wei448.-3. The dual isogeny maps the affine point | where tau is the element of GF(p) defined by | |||

tau 42178595713080601145580616893463205889346047807394283240821661315 | ||||

01870168726890624132409486822657385666418069563147259152341712826 | ||||

86207 | ||||

(=0x948eabcf 057e0d55 9c372c98 075ddacf 6f3d19bc 514e5d23 | ||||

248d685b 75f97a10 36696aaf 61c02d8e 3da778c3 8d9fda05 54c9258b | ||||

3c0e80ff), | ||||

to the point at infinity O of Wei448, while mapping each other point | ||||

(X',Y') of Wei448.-3 to the affine point | (X',Y') of Wei448.-3 to the affine point | |||

(X,Y):=(u'(X1)/w'(X1),Y1*v'(X1)/w'(X1)^2) of Wei448, where | (X,Y):=(u'(X1)/w'(X1),Y1*v'(X1)/w'(X1)^2) of Wei448, where | |||

(X1,Y1)=(X'/t^2,Y'/t^3) and where u', v', and w' are the polynomials | (X1,Y1)=(X'/t^2,Y'/t^3) and where u', v', and w' are the polynomials | |||

with coefficients in GF(p) as defined in Appendix N.4.2, while | with coefficients in GF(p) as defined in Appendix N.4.2. Under this | |||

mapping the point at infinity O of Wei448.-3 to the point at infinity | dual isogenous mapping, the base point (G3X, G3Y) of Wei448.-3 | |||

O of Wei448. Under this dual isogenous mapping, the base point (G3X, | corresponds to a multiple of the base point (GX, GY) of Wei448, where | |||

G3Y) of Wei448.-3 corresponds to a multiple of the base point (GX, | this multiple is l=2 (the degree of the isogeny; see the description | |||

GY) of Wei448, where this multiple is l=2 (the degree of the isogeny; | in Appendix F.4). Note that this isogenous map (and its dual) | |||

see the description in Appendix F.4). Note that this isogenous map | primarily involves the evaluation of three fixed polynomials | |||

(and its dual) primarily involves the evaluation of three fixed | involving the x-coordinate, which takes only a few modular | |||

polynomials involving the x-coordinate, which takes only a few | multiplications (less than 0.5% relative incremental cost compared to | |||

modular multiplications (less than 0.5% relative incremental cost | the cost of an elliptic curve scalar multiplication). | |||

compared to the cost of an elliptic curve scalar multiplication). | ||||

Each point (x1,y1) of Edwards448 with nonzero coordinates corresponds | Each point (x1,y1) of Edwards448 with nonzero coordinates corresponds | |||

to the point (x,y) of Ed448, where | to the point (x,y) of Ed448, where | |||

x = c*x1*y1/(1-d1*x1^2*y1^2) = c*x1*y1/(2-x1^2-y1^2) and | x = c*x1*y1/(1-d1*x1^2*y1^2) = c*x1*y1/(2-x1^2-y1^2) and | |||

y =(1 + d1*x1^2*y1^2)/(y1^2-x1^2) = -(x1^2+y1^2)/(x1^2-y1^2), | y =(1 + d1*x1^2*y1^2)/(y1^2-x1^2) = -(x1^2+y1^2)/(x1^2-y1^2), | |||

while each other point (i.e., a point of order 1, 2, or 4) | while each other point (i.e., a point of order 1, 2, or 4) | |||

corresponds to the identity element (0,1) of Ed448. (Here, we used | corresponds to the identity element (0,1) of Ed448. (Here, we used | |||

skipping to change at page 108, line 16 ¶ | skipping to change at page 115, line 5 ¶ | |||

460881642951497067363381071471046477130052706607411985560 | 460881642951497067363381071471046477130052706607411985560 | |||

522861593611384288817 | 522861593611384288817 | |||

(=0x3176361c 580a7bcd d7880d84 aba10bc6 57010328 afb728cc | (=0x3176361c 580a7bcd d7880d84 aba10bc6 57010328 afb728cc | |||

2016461b 246bef46 0eb4bb04 8c1a3616 c3f74a56 3cc1790f | 2016461b 246bef46 0eb4bb04 8c1a3616 c3f74a56 3cc1790f | |||

6472256b ca3481c8), | 6472256b ca3481c8), | |||

where this representation is defined in Appendix K.5 and uses the | where this representation is defined in Appendix K.5 and uses the | |||

mapping of Appendix K.3.2 with the default square root function. | mapping of Appendix K.3.2 with the default square root function. | |||

This representation can also be expressed in tight LSB/msb order as | ||||

the pair ((u1,s1),(u2,s2)), where (s1,s2):=(0,1) and where | ||||

u1 136243399181827781288243566840664309780937553734476297986 | ||||

555794212826774821697384612603539068963961668560923975117 | ||||

429548012444908081181 | ||||

(=0x1d50f12f 9d4a9f5b c49d8a59 0403a454 e9ab4208 ccde0595 | ||||

11d72af1 f44cefe4 0c743579 6502c443 730c55e9 2981fce1 | ||||

f172d988 fa7efc2f) | ||||

u2 316511454563659405723248762668968632925539726790750815582 | ||||

281632434431599609191814743278306058750675581434472930261 | ||||

478756904493088717708 | ||||

(=0x8c3b4bf7 5ff5eaf5 4df2119b a413785d 73059f0b aa677e16 | ||||

e6eb7cf6 1e066961 e54e4b52 6ae528b1 d3c8cf8e aa3a7df0 | ||||

3b7a9a0d bb827a6f), | ||||

where this uses the default completed mapping defined in Appendix K.6 | ||||

and the mapping of Appendix K.4.2 (with the default square root | ||||

function). | ||||

O.2. Example with Ed448 | O.2. Example with Ed448 | |||

Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Ed448: | Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Ed448: | |||

x 12711234107145442394649604543297947887906244696692372551963816418 | x 12711234107145442394649604543297947887906244696692372551963816418 | |||

93066253979844478364753304240794498368174540810674220788120782656 | 93066253979844478364753304240794498368174540810674220788120782656 | |||

62747 | 62747 | |||

(=0x2cc52fd1 6370554f 00c0f73f 64bda240 f5950177 d9033f6d | (=0x2cc52fd1 6370554f 00c0f73f 64bda240 f5950177 d9033f6d | |||

74acd12d 68c79a51 315f556f 240973f9 e5f71ed7 9314ee9d c87f0b1b | 74acd12d 68c79a51 315f556f 240973f9 e5f71ed7 9314ee9d c87f0b1b | |||

skipping to change at page 110, line 21 ¶ | skipping to change at page 117, line 34 ¶ | |||

(=0x94ecb72a 069a5322 e62d9357 c49d5664 1c351611 d1f361a8 | (=0x94ecb72a 069a5322 e62d9357 c49d5664 1c351611 d1f361a8 | |||

cbb8a12c f410e821 4fbe8e02 8d85d404 399b4c7c 5a6a72ce | cbb8a12c f410e821 4fbe8e02 8d85d404 399b4c7c 5a6a72ce | |||

deef7b08 96302d5f), | deef7b08 96302d5f), | |||

where this representation is defined in Appendix K.5 and uses the | where this representation is defined in Appendix K.5 and uses the | |||

mapping of Appendix K.3.3 with the default square root function and | mapping of Appendix K.3.3 with the default square root function and | |||

underlying isomorphic mapping between Ed448 and Curve448 of | underlying isomorphic mapping between Ed448 and Curve448 of | |||

Appendix M.2. | Appendix M.2. | |||

This representation can also be expressed in tight LSB/lsb order as | ||||

the pair ((u1,s1),(u2,s2)), where (s1,s2):=(1,1) and where | ||||

u1 799430080555285542466583392114886786202374259081179178887 | ||||

990338902005327496428208435321295787094454554911799066625 | ||||

85567756287085693163 | ||||

(=0xd713005d bece883b de9e7077 e0084c74 e3f8ccf3 dcdf9af2 | ||||

2db99b77 5a9c3de7 c8d14433 634cee63 531d3d85 0637c24d | ||||

a28691a3 ac041438) | ||||

u2 273728972604711260959662149917071768586371733548553856048 | ||||

628325847723030459670661529224890730701519431099205367639 | ||||

437006368499972842925 | ||||

(=0xb5a46d1d be03f21b a4070e3c 51e42a50 1de9a4e6 3155b58c | ||||

41dbdaed d5089539 cf69bbc8 78f3809d 5630ab65 c250e49b | ||||

3a91a31d 067f1606), | ||||

where this uses the default completed mapping defined in Appendix K.6 | ||||

and the mapping of Appendix K.4.3 (with the default square root | ||||

function). | ||||

O.3. Example with Wei448 | O.3. Example with Wei448 | |||

Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei448: | Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei448: | |||

X 29070637261778856087396075817199998758219070555984737667402173284 | X 29070637261778856087396075817199998758219070555984737667402173284 | |||

55389871077654193754799253725773241315783295429899652880118118204 | 55389871077654193754799253725773241315783295429899652880118118204 | |||

91344 | 91344 | |||

(=0x6663c64e 5b9a1f6d cbee3f5f 839b7dd8 6f53cc3e 0a01dab3 | (=0x6663c64e 5b9a1f6d cbee3f5f 839b7dd8 6f53cc3e 0a01dab3 | |||

e4a8314e 8d54be2a 4d63380b 692381bb ed7339fd dca7b0cd a80166fe | e4a8314e 8d54be2a 4d63380b 692381bb ed7339fd dca7b0cd a80166fe | |||

skipping to change at page 113, line 8 ¶ | skipping to change at page 120, line 44 ¶ | |||

507910466738735762660894972854331591097934354210992993787 | 507910466738735762660894972854331591097934354210992993787 | |||

402433561014235472657 | 402433561014235472657 | |||

(=0x7e0ffcaf 7add27bc bb723629 95fdedd0 8769f676 78d953bc | (=0x7e0ffcaf 7add27bc bb723629 95fdedd0 8769f676 78d953bc | |||

0d38f4f6 d63a59dc 00f2d55a a4db7dab 16364503 591edcb1 | 0d38f4f6 d63a59dc 00f2d55a a4db7dab 16364503 591edcb1 | |||

e095a577 43dea311), | e095a577 43dea311), | |||

where this representation is defined in Appendix K.5 and uses the | where this representation is defined in Appendix K.5 and uses the | |||

mapping of Appendix K.3.1 with the default square root function. | mapping of Appendix K.3.1 with the default square root function. | |||

O.4. Example with Wei448.-3 | This representation can also be expressed in tight MSB/msb order as | |||

the pair ((u1,s1),(u2,s2)), where (s1,s2):=(0,0) and where | ||||

u1 276116573473684049599673971142041943002546018725744504858 | ||||

999210132924481156665376801365226215725437541502686055399 | ||||

974543995300346621026 | ||||

(=0x6140460c 1860a8cb 7c8ab942 b9509a84 95b4093c 95be5c8b | ||||

df46e24c 069fe28a a23e4bfc 5bc29543 ee9ff503 febb80c8 | ||||

eb207253 8d7c6c62) | ||||

u2 128692595060487759871442054704123965938223087241863768179 | ||||

405512569340496286539849938457727539660932642464491037369 | ||||

291713756051590336193 | ||||

(=0x2d53abf2 370638a2 c2d38efe 718d0189 18d15d15 f132741b | ||||

34405174 97fc0884 0c6be3a5 d9c201b9 cb0c3637 2674078e | ||||

59ac8cd7 4f9fcec1), | ||||

where this uses the default completed mapping defined in Appendix K.6 | ||||

and the mapping of Appendix K.4.1 (with the default square root | ||||

function). | ||||

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

Pw1=(X, Y), k*Pw1=(X1, Y1), and (k+1)*Pw1=(X2, Y2) with Wei448.1: | ||||

X 41414505267302962826496323862800346730148184600706317030200831678 | ||||

13123337737005257876668389910719145841028692415431602235556184165 | ||||

13314 | ||||

(=0x91ddb90a 3c19f561 21de39ad a8c6bb00 579a6d2d 9ff6b810 | ||||

b109bf41 6e4e6227 0fc34010 be9ec68e 5ca11111 bc99e998 cff0f6db | ||||

f4225122). | ||||

Y 21678703524693091005728527221124083240889481089231739678311939020 | ||||

43874709051080711177237887514058399787606848450432099149433728340 | ||||

08081 | ||||

(=0x4c5ac727 121de1f1 be917280 829a6d4c 9f615e3a 879a7dfd | ||||

50f8bdcc 75d5856b 1d01ffaa 44e5ba0a ed0e341d 9383e15a 6cd48db8 | ||||

c1e26c11). | ||||

X1 21211734920525001827254082557112140340208109740004519264558098189 | ||||

40985376833176210029490012696175276046779431389727351279961384020 | ||||

21113 | ||||

(=0x4ab5bb5f ca80119b 6280f5d1 aec51745 23ab57ab 4d617195 | ||||

38f453dd 2e8d9b66 a5417d1b ed0cee3d 4d6c84ca abda1d41 b7a805dc | ||||

cbaefef9). | ||||

Y1 14152482531219571027190110620355502977165146571026919001455348108 | ||||

06142769037926777863731011790633441497896003632149582109867558046 | ||||

16181 | ||||

(=0x31d8b337 09272016_25d2f9d6 cb0e2396 b7088c79 ffc8571f | ||||

6dc9bfe9 9e0783d4 1f684439 c02981f1 83f6696d 9c0377c9 431b8186 | ||||

f503d5f5). | ||||

X2 30394319241133688143587947164786865078477223372122681434460686381 | ||||

23744153597949961703624604448300529949032402198106459850911229168 | ||||

46262 | ||||

(=0x6b0d487d cba3633b_034f65a5 bbd1c8eb 1b6dcb1f 8d787db1 | ||||

a581c08d ad23cbcd 6faa39d5 36731645 fd2fd6c0 03367bff 9093d29d | ||||

550d6ab6). | ||||

Y2 18866191129065867707969757296934620738822864945913956797432892866 | ||||

18725386530370846638505587040510045280940919798896557156654042590 | ||||

85719 | ||||

(=0x4272da7b 7ad66918 144ae679 3811eb6b 2124b02f 42fd51f2 | ||||

34e6f3ea 6285d40e 43cf726f 585b7e74 c4448acb b0c3ab89 d5a55678 | ||||

c4622d97). | ||||

The representation of k and the compressed representations of Pw1 and | ||||

k*Pw1 in tight MSB/msb-order are given by | ||||

repr(k) =0xdcb3bbb9 e42d7aca fe62052d 902123c7 0872b984 4c1e199f | ||||

7c5d37bd 1171102b c20a6352 d9c91886 29b685de 51441e84 | ||||

3afe2665 5251aa80; | ||||

repr(Pw1) =0x80 0x91ddb90a 3c19f561 21de39ad a8c6bb00 579a6d2d | ||||

9ff6b810 b109bf41 6e4e6227 0fc34010 be9ec68e 5ca11111 | ||||

bc99e998 cff0f6db f4225122; | ||||

repr(k*Pw1) =0x80 0x4ab5bb5f ca80119b 6280f5d1 aec51745 23ab57ab | ||||

4d617195 38f453dd 2e8d9b66 a5417d1b ed0cee3d 4d6c84ca | ||||

abda1d41 b7a805dc cbaefef9, | ||||

where the leftmost bit of the leftmost octet indicates the parity of | ||||

the Y-coordinate of the point of Wei448.1 in question (which, in this | ||||

case, are both one, since Y and Y1 are odd). See Appendix H.1 and | ||||

Appendix I for further detail on (squeezed) point compression. | ||||

A randomized representation (t1, t2) of the point k*Pw1 in tight MSB/ | ||||

msb order is given by | ||||

t1 303494474566270819668963081208440311422386279248346372989 | ||||

800906749888679443057479207554461646083343330145746687567 | ||||

323228377891922156528 | ||||

(=0x6ae4d2fc 57e63e5e bfdc44e6 5148d1bd b30b7c7b 2ca2a66a | ||||

8a2bea6c 69113c79 7a4d6d0f 3c89b06a 3883ab2c e7d73f42 | ||||

24c82419 391e9bf0) | ||||

t2 637873534161581517938168102871523640780662020357386089328 | ||||

144426836947858617075256828298188817117945599296940030103 | ||||

858866119361786506090 | ||||

(=0xe0aa61c1 213a19b4 a9fddbb3 4c1377d0 4cd1fb84 017a1719 | ||||

e57b243b 31b13406 d5d77138 23c5a1b8 4fe271a5 2e53c98f | ||||

900f2900 d1e76b6a), | ||||

where this representation is defined in Appendix K.5 and uses the | ||||

mapping of Appendix K.3.1 with the default square root function. | ||||

This representation can also be expressed in tight MSB/msb order as | ||||

the pair ((u1,s1),(u2,s2)), where (s1,s2):=(1,0) and where | ||||

u1 258036413119309433113527846878476684681744445436114935036 | ||||

372455666259396397921645423893888406553811930237985641251 | ||||

551672383206550397837 | ||||

(=0x5ae20fb6 5cafa07a 40421568 72419f49 dc31cbe9 766806f6 | ||||

8b1dbd7f 628c8ecf 10577848 e2e87ac2 fead0f09 6726ee34 | ||||

c2ed465f 5b7be38d) | ||||

u2 193962140052429320576140519455776109491178991023347646634 | ||||

723564200925012444187815484406230413980100291233975929881 | ||||

580671116555136082409 | ||||

(=0x4450c0ba ba9ee42a 4723b3b4 dbe7613f a78a2feb ee01752f | ||||

9f8f51d6 41476eb8 041c9d87 d1b6df7b 9c6b48ad 2cdf4c20 | ||||

02d22f0c fbf521e9), | ||||

where this uses the default completed mapping defined in Appendix K.6 | ||||

and the mapping of Appendix K.4.1 (with the default square root | ||||

function). | ||||

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

Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei448.-3: | Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei448.-3: | |||

X 54121793865726175505902038600562190720650456678500106168173285986 | X 54121793865726175505902038600562190720650456678500106168173285986 | |||

99999531708218763586616425010404811083912084906688745035466757984 | 99999531708218763586616425010404811083912084906688745035466757984 | |||

48968 | 48968 | |||

(=0xbe9f5a23 51709e13 d5ad50c2 a27be8ee 1b051970 2580d5c3 | (=0xbe9f5a23 51709e13 d5ad50c2 a27be8ee 1b051970 2580d5c3 | |||

c2de7f75 3010635e d89ef547 8b67dc54 16d63c5b 1cc1116f dd453515 | c2de7f75 3010635e d89ef547 8b67dc54 16d63c5b 1cc1116f dd453515 | |||

71b39b48). | 71b39b48). | |||

Y 14962282101304548030627835311887275833718070818965306362006934455 | Y 14962282101304548030627835311887275833718070818965306362006934455 | |||

59168773381983445709256615887526455657034051121085622763637035580 | 59168773381983445709256615887526455657034051121085622763637035580 | |||

12661 | 12661 | |||

(=0x34b2dcc4 92d6a940 e6249c14 122d0ba4 5dc040e9 3f060d8f | (=0x34b2dcc4 92d6a940 e6249c14 122d0ba4 5dc040e9 3f060d8f | |||

a65fa300 eb3cc969 25188b59 2d31039c f7a8e14a 48320a32 efe9b42b | a65fa300 eb3cc969 25188b59 2d31039c f7a8e14a 48320a32 efe9b42b | |||

skipping to change at page 115, line 8 ¶ | skipping to change at page 125, line 44 ¶ | |||

363622725164496136165251928391223173879522521195772276587 | 363622725164496136165251928391223173879522521195772276587 | |||

373445978123589677750 | 373445978123589677750 | |||

(=0x7778c1f9 9d900633 d161d7ea a963ddad e9101d3f f4f04710 | (=0x7778c1f9 9d900633 d161d7ea a963ddad e9101d3f f4f04710 | |||

623d2a51 6ca10133 3db9ccc3 86df9271 fbb72740 77f79dd1 | 623d2a51 6ca10133 3db9ccc3 86df9271 fbb72740 77f79dd1 | |||

9aed0bfb e3bc72b6), | 9aed0bfb e3bc72b6), | |||

where this representation is defined in Appendix K.5 and uses the | where this representation is defined in Appendix K.5 and uses the | |||

mapping of Appendix K.3.1 with the default square root function. | mapping of Appendix K.3.1 with the default square root function. | |||

O.5. Example with Edwards448 | This representation can also be expressed in tight MSB/msb order as | |||

the pair ((u1,s1),(u2,s2)), where (s1,s2):=(0,1) and where | ||||

u1 589255274721777493669102139212346422449226408440608788354 | ||||

266603544786997157375671957901717836941301424106139118763 | ||||

92799989153446639329 | ||||

(=0x14c11156 85eab1a5 f6c00d37 a3f6bd73 fe403dd1 31e337e7 | ||||

15927c25 0264a8f8 d2cd661e b5138468 92a3b91d 09284398 | ||||

17c2e361 96fa36e1) | ||||

u2 213991023129828413030692573508989139610229330687681826719 | ||||

574082317313789459478773972345123463766002343322541837566 | ||||

496527438452046182709 | ||||

(=0x4b5eac5a 3632b273 012a1050 7762eba4 8df1ccad 16dd9e6f | ||||

d68e57a9 89de5a0c 1eda0951 e4f3de0e 39f5c37b 2f8f04d5 | ||||

52c093d8 fb983935), | ||||

where this uses the default completed mapping defined in Appendix K.6 | ||||

and the mapping of Appendix K.4.1 (with the default square root | ||||

function). | ||||

O.6. Example with Edwards448 | ||||

Pe1=(x, y), k*Pe1=(x1, y1), and (k+1)*Pe1=(x2, y2) with Edwards448: | Pe1=(x, y), k*Pe1=(x1, y1), and (k+1)*Pe1=(x2, y2) with Edwards448: | |||

x 70320395893028961673046639985409870226249442701760956079298956688 | x 70320395893028961673046639985409870226249442701760956079298956688 | |||

26896600999421897751877804946848997852325361659665744287620719558 | 26896600999421897751877804946848997852325361659665744287620719558 | |||

67733 | 67733 | |||

(=0xf7acf3ca b79b29c2 aa44863d 9edaeca4 8c90ad84 e460df42 | (=0xf7acf3ca b79b29c2 aa44863d 9edaeca4 8c90ad84 e460df42 | |||

7dd9ab59 1bd8a844 07cb3419 59309b33 1e22bfa1 a2d37e10 e2e42a1f | 7dd9ab59 1bd8a844 07cb3419 59309b33 1e22bfa1 a2d37e10 e2e42a1f | |||

170f0855). | 170f0855). | |||

skipping to change at page 116, line 40 ¶ | skipping to change at page 128, line 4 ¶ | |||

this case, are both one, since x and x1 are odd). See Appendix H.3 | this case, are both one, since x and x1 are odd). See Appendix H.3 | |||

and Appendix I for further detail on (squeezed) point compression. | and Appendix I for further detail on (squeezed) point compression. | |||

The scalar representation and (squeezed) point representation | The scalar representation and (squeezed) point representation | |||

illustrated above are fully consistent with the representations | illustrated above are fully consistent with the representations | |||

specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032] | specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032] | |||

requires unique representations of all elements of GF(p). | requires unique representations of all elements of GF(p). | |||

A randomized representation (t1, t2) of the point k*Pe1 in tight LSB/ | A randomized representation (t1, t2) of the point k*Pe1 in tight LSB/ | |||

lsb order is given by | lsb order is given by | |||

t1 125390048858887400104074787879402833851854739339836093733 | t1 125390048858887400104074787879402833851854739339836093733 | |||

734638776755983021034212058415891288350265701101219981698 | 734638776755983021034212058415891288350265701101219981698 | |||

849086128138510420407 | 849086128138510420407 | |||

(=0xed921f3d 6ea4e452 dd06e783 782cbeb3 c5847a79 d9e6b993 | (=0xed921f3d 6ea4e452 dd06e783 782cbeb3 c5847a79 d9e6b993 | |||

bd387cf5 feeddafe af8c038d f2732362 92724d37 273eedfc | bd387cf5 feeddafe af8c038d f2732362 92724d37 273eedfc | |||

f2ab2499 98a79434) | f2ab2499 98a79434) | |||

t2 365268494484253132875102676783560666625109899133767696106 | t2 493324858478481242405018423865550638507715454654135514168 | |||

602723958322248430160651314075127005631031993354968950936 | 842560149827360763382889199963980056979895918545280883247 | |||

71875730862008188281 | 787003997982869314731 | |||

(=0x9ebc28c0 86176a1a c7f0cf71 ca5f2a8f 908bb27b e85c0bbd | ||||

1641c052 e542f7d3 88e18886 5afdca32 8df45408 8b6da28c | (=0xd53a5125 193b6ab9 8db48161 20fb4865 02cf0546 3b48d8a6 | |||

0bc09d83 309ebb30), | 514af28f 43c026cb 0f2ff3d5 e558bb03 4b833cd1 1ca710cc | |||

9bf0c2a3 351083b5), | ||||

where this representation is defined in Appendix K.5 and uses the | where this representation is defined in Appendix K.5 and uses the | |||

mapping of Appendix K.3.3 with the default square root function and | mapping of Appendix K.3.3 with the default square root function and | |||

underlying 4-isogenous mapping between Edwards448 and Curve448 of | underlying 4-isogenous mapping between Edwards448 and Curve448 of | |||

Appendix N.2. | Appendix N.2. | |||

This representation can also be expressed in tight LSB/lsb order as | ||||

the pair ((u1,s1),(u2,s2)), where (s1,s2):=(0,0) and where | ||||

u1 135993582308059710871118067705651831584215992415511174727 | ||||

255533641033816319052989477276487981998957706382391254504 | ||||

484510842833065141388 | ||||

(=0x31276f5f d399d1cd 5d18c46a eba5388f 93effaf7 9574b23b | ||||

ce34ba45 5050c160 477ae803 9c3112be 596281a7 b7ae4da6 | ||||

e9dd7688 191fa7f4) | ||||

u2 300725936379847215929002275525633229576034707671620463143 | ||||

626393832660436027759737097637786753095880885199368686863 | ||||

187789449179730426477 | ||||

(=0xb65c5ee8 597b5b55 a87e266f b9c1f5cb 5d224ec3 8fb22f32 | ||||

b0378e70 47ecc389 9585b06e 7fb4f70b 38a3b453 ab5c03d8 | ||||

37b5093b 9a4cd796), | ||||

where this uses the default completed mapping defined in Appendix K.6 | ||||

and the mapping of Appendix K.4.3 (with the default square root | ||||

function) and underlying 4-isogenous mapping between Edwards448 and | ||||

Curve448 of Appendix N.2. | ||||

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

Any probability distribution on the interval [0,N-1] can be converted | Any probability distribution on the interval [0,N-1] can be converted | |||

to a probability distribution on [0,n-1], via a suitable function | to a probability distribution on [0,n-1], via a suitable function | |||

that maps inputs from the source distribution [0,N-1] to values in | that maps inputs from the source distribution [0,N-1] to values in | |||

the interval [0,n-1]. We consider three such functions, each with | the interval [0,n-1]. We consider three such functions, each with | |||

the property that if the source distribution on [0,N-1] is | the property that if the source distribution on [0,N-1] is | |||

statistically close to the uniform distribution, then so is the | statistically close to the uniform distribution, then so is the | |||

output distribution on [0,n-1]. In practical applications, one can | output distribution on [0,n-1]. In practical applications, one can | |||

use these functions to convert the output of a cryptographically | use these functions to convert the output of a cryptographically | |||

skipping to change at page 119, line 16 ¶ | skipping to change at page 130, line 50 ¶ | |||

This function (defined for N at least n) is the identity map on the | This function (defined for N at least n) is the identity map on the | |||

interval [0,n-1] and fails for each integer y outside this interval. | interval [0,n-1] and fails for each integer y outside this interval. | |||

One can show that the statistical distance of the distribution on Z_n | One can show that the statistical distance of the distribution on Z_n | |||

is at most roughly N/n times as large as the statistical distance of | is at most roughly N/n times as large as the statistical distance of | |||

the source distribution on Z_N (if the latter is relatively | the source distribution on Z_N (if the latter is relatively | |||

negligible compared to n/N). Details are out of scope. | negligible compared to n/N). Details are out of scope. | |||

Note that, under the above conditions, if N:=2^m and if n has bit- | Note that, under the above conditions, if N:=2^m and if n has bit- | |||

length m, this conversion function fails with probability less than | length m, this conversion function fails with probability 1- n/N | |||

1/2 and, if it succeeds, does not inflate the statistical distance by | (which is at most 1/2) and, if it succeeds, does not inflate the | |||

more than (roughly) a factor two. | statistical distance by more than (roughly) a factor two. | |||

Author's Address | Author's Address | |||

Rene Struik | Rene Struik | |||

Struik Security Consultancy | Struik Security Consultancy | |||

Email: rstruik.ext@gmail.com | Email: rstruik.ext@gmail.com | |||

End of changes. 83 change blocks. | ||||

300 lines changed or deleted | | 789 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/ |