draft-ietf-lwig-curve-representations-18.txt   draft-ietf-lwig-curve-representations-19.txt 
lwig R. Struik lwig R. Struik
Internet-Draft Struik Security Consultancy Internet-Draft Struik Security Consultancy
Intended status: Standards Track December 15, 2020 Intended status: Standards Track December 17, 2020
Expires: June 18, 2021 Expires: June 20, 2021
Alternative Elliptic Curve Representations Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-18 draft-ietf-lwig-curve-representations-19
Abstract Abstract
This document specifies how to represent Montgomery curves and This document specifies how to represent Montgomery curves and
(twisted) Edwards curves as curves in short-Weierstrass form and (twisted) Edwards curves as curves in short-Weierstrass form and
illustrates how this can be used to carry out elliptic curve illustrates how this can be used to carry out elliptic curve
computations using existing implementations of, e.g., ECDSA and ECDH computations using existing implementations of, e.g., ECDSA and ECDH
using NIST prime curves. We also provide extensive background using NIST prime curves. We also provide extensive background
material that may be useful for implementers of elliptic curve material that may be useful for implementers of elliptic curve
cryptography. cryptography.
skipping to change at page 1, line 44 skipping to change at page 1, line 44
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on June 18, 2021. This Internet-Draft will expire on June 20, 2021.
Copyright Notice Copyright Notice
Copyright (c) 2020 IETF Trust and the persons identified as the Copyright (c) 2020 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 27 skipping to change at page 2, line 27
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 5 1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 5
2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 6 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 6
3. Use of Representation Switches . . . . . . . . . . . . . . . 6 3. Use of Representation Switches . . . . . . . . . . . . . . . 6
4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.1. Implementation of X25519, Specification of ECDH25519 . . 7 4.1. Implementation of X25519, Specification of ECDH25519 . . 7
4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 8 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 9
4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 8 4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 9
4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 9 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 10
5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 10 5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 11
5.2. Representation Conventions . . . . . . . . . . . . . . . 10 5.2. Representation Conventions . . . . . . . . . . . . . . . 11
5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 11 5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 12
6. Implementation Considerations . . . . . . . . . . . . . . . . 11 6. Implementation Considerations . . . . . . . . . . . . . . . . 12
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 13 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 14
8. Security Considerations . . . . . . . . . . . . . . . . . . . 13 8. Security Considerations . . . . . . . . . . . . . . . . . . . 14
9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 14 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 15
10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 15 10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 16
10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 15 10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 16
10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 15 10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 16
10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 16 10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 17
10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 17 10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 18
10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 18 10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 19
10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 19 10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 20
10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 20 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 21
10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 21 10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 22
10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 21 10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 22
11. Using Wei25519 and Wei448 with PKIX and CMS . . . . . . . . . 21 11. Using Wei25519 and Wei448 with PKIX and CMS . . . . . . . . . 22
11.1. Encoding of Short-Weierstrass Curves with PKIX . . . . . 22 11.1. Encoding of Short-Weierstrass Curves with PKIX . . . . . 23
11.2. Encoding of ECDSA Instantiations with PKIX . . . . . . . 22 11.2. Encoding of ECDSA Instantiations with PKIX . . . . . . . 23
11.3. Encoding of co-factor ECDH and Other Algorithms with 11.3. Encoding of co-factor ECDH and Other Algorithms with
PKIX . . . . . . . . . . . . . . . . . . . . . . . . . . 22 PKIX . . . . . . . . . . . . . . . . . . . . . . . . . . 23
11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS . . 23 11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS . . 24
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24
12.1. OIDs for Use with PKIX and CMS . . . . . . . . . . . . . 23 12.1. OIDs for Use with PKIX and CMS . . . . . . . . . . . . . 24
12.2. COSE/JOSE IANA Considerations for Wei25519 . . . . . . . 23 12.2. COSE/JOSE IANA Considerations for Wei25519 . . . . . . . 24
12.2.1. COSE Elliptic Curves Registration . . . . . . . . . 23 12.2.1. COSE Elliptic Curves Registration . . . . . . . . . 24
12.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 24 12.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 25
12.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 24 12.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 25
12.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 25 12.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 26
12.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 25 12.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 26
12.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 25 12.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 26
12.3. COSE/JOSE IANA Considerations for Wei448 . . . . . . . . 26 12.3. COSE/JOSE IANA Considerations for Wei448 . . . . . . . . 27
12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 26 12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 27
12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 26 12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 27
12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 27 12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 28
12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 27 12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 28
12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 28 12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 29
12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 28 12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 29
13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 28 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 29
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 29 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 30
14.1. Normative References . . . . . . . . . . . . . . . . . . 29 14.1. Normative References . . . . . . . . . . . . . . . . . . 30
14.2. Informative References . . . . . . . . . . . . . . . . . 32 14.2. Informative References . . . . . . . . . . . . . . . . . 33
Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 34 Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 35
A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 34 A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 35
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 34 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 35
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 34 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 36
Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 35 Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 36
B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 35 B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 36
B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 37 B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 38
Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 38 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 39
C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 38 C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 40
C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 39 C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 40
C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 40 C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 41
Appendix D. Relationships Between Curve Models . . . . . . . . . 41 Appendix D. Relationships Between Curve Models . . . . . . . . . 42
D.1. Mapping between Twisted Edwards Curves and Montgomery D.1. Mapping between Twisted Edwards Curves and Montgomery
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 41
D.2. Mapping between Montgomery Curves and Weierstrass Curves 42
D.3. Mapping between Twisted Edwards Curves and Weierstrass
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 43 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 43
Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 43 D.2. Mapping between Montgomery Curves and Weierstrass Curves 43
E.1. Curve Definition and Alternative Representations . . . . 43 D.3. Mapping between Twisted Edwards Curves and Weierstrass
E.2. Switching between Alternative Representations . . . . . . 44 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 44
E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 45 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 44
Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 47 E.1. Curve Definition and Alternative Representations . . . . 45
F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 47 E.2. Switching between Alternative Representations . . . . . . 45
F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 48 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 47
F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 49 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 49
F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 50 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 49
Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 51 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 49
G.1. Further Alternative Representations . . . . . . . . . . . 51 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 50
G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 51 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 51
G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 52 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 53
G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 54 G.1. Further Alternative Representations . . . . . . . . . . . 53
G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 54 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 53
G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 60 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 54
Appendix H. Point Compression . . . . . . . . . . . . . . . . . 66 G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 55
H.1. Point Compression for Weierstrass Curves . . . . . . . . 67 G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 55
H.2. Point Compression for Montgomery Curves . . . . . . . . . 67 G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 62
H.3. Point Compression for Twisted Edwards Curves . . . . . . 68 Appendix H. Point Compression . . . . . . . . . . . . . . . . . 68
Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 69 H.1. Point Compression for Weierstrass Curves . . . . . . . . 68
I.1. Strings and String Operations . . . . . . . . . . . . . . 69 H.2. Point Compression for Montgomery Curves . . . . . . . . . 69
I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 70 H.3. Point Compression for Twisted Edwards Curves . . . . . . 70
Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 71
I.1. Strings and String Operations . . . . . . . . . . . . . . 71
I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 72
I.3. Conversion between Octet Strings and Integers (OS2I, I.3. Conversion between Octet Strings and Integers (OS2I,
I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 70 I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 72
I.4. Conversion between Octet Strings and Bit Strings (OS2BS, I.4. Conversion between Octet Strings and Bit Strings (OS2BS,
BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 71 BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 72
I.5. Conversion between Field Elements and Octet Strings I.5. Conversion between Field Elements and Octet Strings
(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 71 (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 73
I.6. Conversion between Elements of Z mod n and Octet Strings I.6. Conversion between Elements of Z_n and Octet Strings
(ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 72 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 73
I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 72 I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 74
I.8. Conversion Between Curve Points and Octet Strings . . . . 73 I.8. Conversion Between Curve Points and Octet Strings . . . . 75
Appendix J. Representation Examples Curve25519 Family Members . 75 Appendix J. Representation Examples Curve25519 Family Members . 77
J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 76 J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 78
J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 78 J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 80
J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 81 J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 82
J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 83 J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 85
J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 85 J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 87
Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 87 Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 89
K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 87 K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 89
K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 88 K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 90
K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 88 K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 90
K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 88 K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 90
K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 89 K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 91
K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 89 K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 91
K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 90 K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 92
K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 91 K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 93
K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 91 K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 93
K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 92 K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 94
K.4.2. Mapping to High-Order Points of Montgomery Curve . . 93 K.4.2. Mapping to High-Order Points of Montgomery Curve . . 95
K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 94 K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 96
K.5. Randomized Representation of Curve Points . . . . . . . . 95 K.5. Randomized Representation of Curve Points . . . . . . . . 97
K.6. Completing the Mappings to Curve Points . . . . . . . . . 96 K.6. Completing the Mappings to Curve Points . . . . . . . . . 98
Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 99 Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 101
L.1. Curve Definition and Alternative Representation . . . . . 100 L.1. Curve Definition and Alternative Representation . . . . . 102
L.2. Switching Between Representations . . . . . . . . . . . . 100 L.2. Switching Between Representations . . . . . . . . . . . . 102
L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 100 L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 102
L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 102 L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 104
L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 102 L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 104
L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 103 L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 105
Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 103 Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 105
M.1. Curve Definition and Alternative Representations . . . . 103 M.1. Curve Definition and Alternative Representations . . . . 105
M.2. Switching between Alternative Representations . . . . . . 104 M.2. Switching between Alternative Representations . . . . . . 106
M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 105 M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 107
Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 108 Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 110
N.1. Further Alternative Representations . . . . . . . . . . . 108 N.1. Further Alternative Representations . . . . . . . . . . . 110
N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 108 N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 110
N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 111 N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 113
N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 113 N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 115
N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 113 N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 115
N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 114 N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 116
Appendix O. Representation Examples Curve448 Family Members . . 114 Appendix O. Representation Examples Curve448 Family Members . . 116
O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 115 O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 117
O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 118 O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 120
O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 121 O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 123
O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 124 O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 126
O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 127 O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 129
O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 129 O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 131
Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 132 Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 134
P.1. Conversion to Integers in Z_n via Modular Reduction . . . 133 P.1. Conversion to Integers in Z_n via Modular Reduction . . . 135
P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 134 P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 136
P.3. Conversion to Integers in Z_n via the Discard Method . . 135 P.3. Conversion to Integers in Z_n via the Discard Method . . 137
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 135 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 137
1. Fostering Code Reuse with New Elliptic Curves 1. Fostering Code Reuse with New Elliptic Curves
Elliptic curves can be represented using different curve models. Elliptic curves can be represented using different curve models.
Recently, IETF standardized elliptic curves that are claimed to have Recently, IETF standardized elliptic curves that are claimed to have
better performance and improved robustness against "real world" better performance and improved robustness against "real world"
attacks than curves represented in the traditional short-Weierstrass attacks than curves represented in the traditional short-Weierstrass
curve model. These so-called CFRG curves [RFC7748] use the curve model. These so-called CFRG curves [RFC7748] use the
Montgomery curve model and the model of twisted Edwards curves. Montgomery curve model and the model of twisted Edwards curves.
skipping to change at page 8, line 24 skipping to change at page 8, line 24
A NIST-compliant version of the co-factor Diffie-Hellman key A NIST-compliant version of the co-factor Diffie-Hellman key
agreement scheme (denoted by ECDH25519) results if one keeps inputs agreement scheme (denoted by ECDH25519) results if one keeps inputs
(key contributions) and pre-output (shared key K) in the short- (key contributions) and pre-output (shared key K) in the short-
Weierstrass format (and, hence, does not perform Steps (1) and (3) Weierstrass format (and, hence, does not perform Steps (1) and (3)
above), where the actual output (shared secret Z) is the x-coordinate above), where the actual output (shared secret Z) is the x-coordinate
of K (if this is an affine point of the curve), represented as a of K (if this is an affine point of the curve), represented as a
fixed-size octet string in tight MSB/msb-order using the FE2OS fixed-size octet string in tight MSB/msb-order using the FE2OS
mapping of Appendix I.5, and where the output is an error indicator mapping of Appendix I.5, and where the output is an error indicator
otherwise (i.e., if K is the point at infinity O of the curve). otherwise (i.e., if K is the point at infinity O of the curve).
NOTE: At this point, it is unclear whether this implies that a FIPS- NOTE 1: A Montgomery version of the co-factor Diffie-Hellman key
accredited module implementing co-factor Diffie-Hellman for, e.g., agreement scheme (denoted by X25519+) results by incorporating Steps
P-256 would also extend this accreditation to X25519. (1), (2), and (3) above, i.e., where one keeps inputs (key
contributions) and pre-output (shared key K) in the Montgomery curve
format, as points of Curve25519, where one represents each affine
point by only its x-coordinate, represented as a fixed-size octet
string in tight LSB/msb-order using the FE2OS mapping and its
reverse, the strict OS2FE mapping, of Appendix I.5, and where the
actual output (shared secret Z) is the representation of the shared
key K as defined above (if this is an affine point of the curve), and
where the output is an error indicator otherwise (i.e., if K is the
point at infinity O of the curve). The scheme X25519, as specified
in [RFC7748], is a more lenient version of this X25519+ scheme,
whereby one does not mandate rejection of shared keys in the small
subgroup (which are instead represented as if these were the point
(0,0) of order two), where one does not check whether a received key
contribution is a point of Curve25519 rather than a point of a
quadratic twist of this curve (for definitions of these terms, see
Appendix B.1), and where one uses the non-strict (rather than strict)
OS2FE mapping (which, in this case, is always applied after setting
the leftmost bit of the rightmost octet to zero). Moreover, with
X25519, private keys are generated in the interval [2^251,2^252-1]
rather than in the interval [1,n-1] (the so-called "clamping") and
one uses as base point G':=h*G, where G, n, and h are, respectively,
the fixed base point, the order of the base point, and the co-factor
of the curve in question.
NOTE 2: At this point, it is unclear whether a FIPS-accredited module
implementing the co-factor Diffie-Hellman scheme with, e.g., P-256
would also extend this accreditation to the Montgomery versions
X25519+ or X25519. (For cryptographic module validation program
guidance, see, e.g., [FIPS-140-2].)
4.2. Implementation of Ed25519 4.2. Implementation of Ed25519
RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature
scheme, with instantiation by the twisted Edwards curve Edwards25519. scheme, with instantiation by the twisted Edwards curve Edwards25519.
One can implement the computation of the ephemeral key pair for One can implement the computation of the ephemeral key pair for
Ed25519 using an existing Montgomery curve implementation by (1) Ed25519 using an existing Montgomery curve implementation by (1)
generating a public-private key pair (k, R':=k*G') for Curve25519; generating a public-private key pair (k, R':=k*G') for Curve25519;
(2) representing this public-private key as the pair (k, R:=k*G) for (2) representing this public-private key as the pair (k, R:=k*G) for
Ed25519. As before, the representation change can be implemented via Ed25519. As before, the representation change can be implemented via
a simple wrapper. Note that the Montgomery ladder specified in a simple wrapper. Note that the Montgomery ladder specified in
Section 5 of RFC7748 [RFC7748] does not provide sufficient Section 5 of RFC7748 [RFC7748] does not provide sufficient
information to reconstruct R':=(u, v) (since it does not compute the information to reconstruct R':=(u, v) (since it does not compute the
v-coordinate of R'). However, this deficiency can be remedied by v-coordinate of R'). However, this deficiency can be remedied by
using a slightly modified version of the Montgomery ladder that using a slightly modified version of the Montgomery ladder that
includes reconstruction of the v-coordinate of R':=k*G' at the end of includes reconstruction of the v-coordinate of R':=k*G' at the end of
the Montgomery ladder (which uses the v-coordinate of the base point the Montgomery ladder (which uses the v-coordinate of the base point
of Curve25519 as well). For details, see Appendix C.2. G' of Curve25519 as well). For details, see Appendix C.2.
4.3. Specification of ECDSA25519 4.3. Specification of ECDSA25519
FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and
can be instantiated not just with the NIST prime curves, but also can be instantiated not just with the NIST prime curves, but also
with other Weierstrass curves (that satisfy additional cryptographic with other Weierstrass curves (that satisfy additional cryptographic
criteria). In particular, one can instantiate this scheme with the criteria). In particular, one can instantiate this scheme with the
Weierstrass curve Wei25519 and the hash function SHA-256 Weierstrass curve Wei25519 and the hash function SHA-256
[FIPS-180-4], where an implementation may generate an ephemeral [FIPS-180-4], where an implementation may generate an ephemeral
public-private key pair for Wei25519 by (1) internally carrying out public-private key pair for Wei25519 by (1) internally carrying out
skipping to change at page 10, line 13 skipping to change at page 10, line 43
Section 4.1, but now using the short-Weierstrass curve Wei448, rather Section 4.1, but now using the short-Weierstrass curve Wei448, rather
than Wei25519 (with the same representation and bit/byte-ordering than Wei25519 (with the same representation and bit/byte-ordering
conventions). Similarly, one can easily specify ECDSA with Wei448 conventions). Similarly, one can easily specify ECDSA with Wei448
and a suitable hash function, by simply reusing the example of and a suitable hash function, by simply reusing the example of
Section 4.3, but now using the short-Weierstrass curve Wei448, rather Section 4.3, but now using the short-Weierstrass curve Wei448, rather
than Wei25519, and picking as hash function SHAKE256 [FIPS-202] with than Wei25519, and picking as hash function SHAKE256 [FIPS-202] with
output size of d=512 bits. We denote by ECDSA448 the resulting output size of d=512 bits. We denote by ECDSA448 the resulting
signature scheme (with the same representation and bit/byte-ordering signature scheme (with the same representation and bit/byte-ordering
conventions). conventions).
NOTE: A Montgomery version of the co-factor Diffie-Hellman key
agreement scheme (denoted by X448+) results by reusing the
description of X25519+ in Section 4.1, but now using the Montgomery
curve Curve448, rather than Curve25519 (with the same checks and
representation and bit/byte-ordering conventions). The scheme X448,
as specified in [RFC7748], is a more lenient version of this X448+
scheme, whereby one does not mandate rejection of shared keys in the
small subgroup (which are instead represented as if these were the
point (0,0) of order two), nor checks whether a received key
contribution is a point of Curve448 rather than a point of a
quadratic twist of this curve, and where one uses the non-strict
(rather than the strict) OS2FE mapping for converting octet strings
to field elements. Moreover, with X448, private keys are generated
in the interval [2^445,2^446-1] rather than in the interval [1,n-1]
(the so-called "clamping") and one uses as base point G':=h*G, where
G, n, and h are, respectively, the fixed base point, the order of the
base point, and the co-factor of the curve in question.
5. Caveats 5. Caveats
The examples above illustrate how specifying the Weierstrass curve The examples above illustrate how specifying the Weierstrass curve
Wei25519 (or any curve in short-Weierstrass format, for that matter) Wei25519 (or any curve in short-Weierstrass format, for that matter)
may facilitate reuse of existing code and may simplify standards may facilitate reuse of existing code and may simplify standards
development. However, the following caveats apply: development. However, the following caveats apply:
5.1. Wire Format 5.1. Wire Format
The transformations between alternative curve representations can be The transformations between alternative curve representations can be
skipping to change at page 32, line 12 skipping to change at page 33, line 12
Department of Commerce/National Institute of Standards and Department of Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, April 2018. Technology, Gaithersburg, MD, April 2018.
14.2. Informative References 14.2. Informative References
[comm-FIPS-186-5] [comm-FIPS-186-5]
FIPS 186-5, "Public Comments Received on Draft FIPS Pub FIPS 186-5, "Public Comments Received on Draft FIPS Pub
186-5", US Department of Commerce/National Institute of 186-5", US Department of Commerce/National Institute of
Standards and Technology, Gaithersburg, MD, April 6, 2020. Standards and Technology, Gaithersburg, MD, April 6, 2020.
[draft-FIPS-186-5]
FIPS 186-5, "Digital Signature Standard (DSS) (Draft)", US
Department of Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, October 31, 2019.
[draft-NIST-800-186]
NIST SP 800-186, "Recommendations for Discrete Logarithm-
Based Cryptography, Elliptic Curve Domain Parameters
(Draft)", US Department of Commerce/National Institute of
Standards and Technology, Gaithersburg, MD, October 31,
2019.
[ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in [ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in
Cryptography", Cambridge University Press, Lecture Notes Cryptography", Cambridge University Press, Lecture Notes
Series 265, July 1999. Series 265, July 1999.
[ECC-Isogeny] [ECC-Isogeny]
E. Brier, M. Joye, "Fast Point Multiplication on Elliptic E. Brier, M. Joye, "Fast Point Multiplication on Elliptic
Curves through Isogenies", AAECC, Lecture Notes in Curves through Isogenies", AAECC, Lecture Notes in
Computer Science, Vol. 2643, New York: Springer-Verlag, Computer Science, Vol. 2643, New York: Springer-Verlag,
2003. 2003.
[FIPS-140-2]
FIPS 140-2, "Implementation Guidance for FIPS 140-2 and
the Cryptographic Module Validation Program", US
Department of Commerce/National Institute of Standards and
Technology, Gaithersburg, MD, August 28, 2020.
[GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to [GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to
Elliptic Curve Cryptography", New York: Springer-Verlag, Elliptic Curve Cryptography", New York: Springer-Verlag,
2004. 2004.
[Handbook]
A.J. Menezes, P. van Oorschot, S.A. Vanstone,, "Handbook
of Applied Cryptography", Boca Raton: CRC Press, 1995.
[IANA.COSE.Algorithms] [IANA.COSE.Algorithms]
IANA, "COSE Algorithms", IANA, IANA, "COSE Algorithms", IANA,
https://www.iana.org/assignments/cose/ https://www.iana.org/assignments/cose/
cose.xhtml#algorithms. cose.xhtml#algorithms.
[IANA.COSE.Curves] [IANA.COSE.Curves]
IANA, "COSE Elliptic Curves", IANA, IANA, "COSE Elliptic Curves", IANA,
https://www.iana.org/assignments/cose/cose.xhtml#elliptic- https://www.iana.org/assignments/cose/cose.xhtml#elliptic-
curves. curves.
skipping to change at page 34, line 25 skipping to change at page 35, line 42
the Weierstrass curve with defining equation Y^2 = X^3 + a*X + b, the Weierstrass curve with defining equation Y^2 = X^3 + a*X + b,
where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is
nonzero. The points of W_{a,b} are the ordered pairs (X, Y) whose nonzero. The points of W_{a,b} are the ordered pairs (X, Y) whose
coordinates are elements of GF(q) and that satisfy the defining coordinates are elements of GF(q) and that satisfy the defining
equation (the so-called affine points), together with the special equation (the so-called affine points), together with the special
point O (the so-called "point at infinity"). This set forms a group point O (the so-called "point at infinity"). This set forms a group
under addition, via the so-called "chord-and-tangent" rule, where the under addition, via the so-called "chord-and-tangent" rule, where the
point at infinity serves as the identity element. See Appendix C.1 point at infinity serves as the identity element. See Appendix C.1
for details of the group operation. for details of the group operation.
A quadratic twist of W_{a,b} is a curve W_{a',b'} for which a':= A quadratic twist of W_{a,b} is a curve W_{a',b'} defined over the
a*gamma^2 and b':=b*gamma^3, where gamma is an element of GF(q) that same field for which a':= a*gamma^2 and b':=b*gamma^3, where gamma is
is not a square in GF(q). an element of GF(q) that is not a square in GF(q).
A.2. Montgomery Curves A.2. Montgomery Curves
Let GF(q) denote the finite field with q elements, where q is an odd Let GF(q) denote the finite field with q elements, where q is an odd
prime power. Let M_{A,B} be the Montgomery curve with defining prime power. Let M_{A,B} be the Montgomery curve with defining
equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q) equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q)
and where A is unequal to (+/-)2 and where B is nonzero. The points and where A is unequal to (+/-)2 and where B is nonzero. The points
of M_{A,B} are the ordered pairs (u, v) whose coordinates are of M_{A,B} are the ordered pairs (u, v) whose coordinates are
elements of GF(q) and that satisfy the defining equation (the so- elements of GF(q) and that satisfy the defining equation (the so-
called affine points), together with the special point O (the so- called affine points), together with the special point O (the so-
called "point at infinity"). This set forms a group under addition, called "point at infinity"). This set forms a group under addition,
via the so-called "chord-and-tangent" rule, where the point at via the so-called "chord-and-tangent" rule, where the point at
infinity serves as the identity element. See Appendix C.2 for infinity serves as the identity element. See Appendix C.2 for
details of the group operation. details of the group operation.
A quadratic twist of M_{A,B} is a curve M_{A',B'} for which A':= A A quadratic twist of M_{A,B} is a curve M_{A',B'} defined over the
and B':=B*gamma, where gamma is an element of GF(q) that is not a same field for which A':= A and B':=B*gamma, where gamma is an
square in GF(q). element of GF(q) that is not a square in GF(q).
A.3. Twisted Edwards Curves A.3. Twisted Edwards Curves
Let GF(q) denote the finite field with q elements, where q is an odd Let GF(q) denote the finite field with q elements, where q is an odd
prime power. Let E_{a,d} be the twisted Edwards curve with defining prime power. Let E_{a,d} be the twisted Edwards curve with defining
equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct
nonzero elements of GF(q). The points of E_{a,d} are the ordered nonzero elements of GF(q). The points of E_{a,d} are the ordered
pairs (x, y) whose coordinates are elements of GF(q) and that satisfy pairs (x, y) whose coordinates are elements of GF(q) and that satisfy
the defining equation (the so-called affine points). It can be shown the defining equation (the so-called affine points). It can be shown
that this set forms a group under addition if a is a square in GF(q), that this set forms a group under addition if a is a square in GF(q),
whereas d is not, where the point O:=(0, 1) serves as the identity whereas d is not, where the point O:=(0, 1) serves as the identity
element. (Note that the identity element satisfies the defining element. (Note that the identity element satisfies the defining
equation.) See Appendix C.3 for details of the group operation. equation.) See Appendix C.3 for details of the group operation.
(All curves E_{a,d} in this document are assumed to satisfy the (All curves E_{a,d} in this document are assumed to satisfy the
condition on domain parameters a and d above and, thereby, the Note condition on domain parameters a and d above and, thereby, satisfy
in that appendix.) the Note in that appendix.)
An Edwards curve is a twisted Edwards curve with a=1. An Edwards curve is a twisted Edwards curve with a=1.
A quadratic twist of E_{a,d} is a curve E_{a',d'} for which a':= A quadratic twist of E_{a,d} is a curve E_{a',d'} defined over the
a*gamma and d':=d*gamma, where gamma is an element of GF(q) that is same field for which a':= a*gamma and d':=d*gamma, where gamma is an
not a square in GF(q). element of GF(q) that is not a square in GF(q).
Appendix B. Elliptic Curve Nomenclature and Finite Fields Appendix B. Elliptic Curve Nomenclature and Finite Fields
This section provides brief background information on elliptic curves This section provides brief background information on elliptic curves
and finite fields that should be sufficient to understand and finite fields that should be sufficient to understand
constructions and examples in this document. constructions and examples in this document.
B.1. Elliptic Curve Nomenclature B.1. Elliptic Curve Nomenclature
The set of points of each curve defined in Appendix A forms a The set of points of each curve defined in Appendix A forms a
skipping to change at page 72, line 5 skipping to change at page 73, line 38
field is implicit and assumed to be known from context. In this field is implicit and assumed to be known from context. In this
case, the octet string has length l*m. (Observe that with tight case, the octet string has length l*m. (Observe that with tight
representations, the parameter l is uniquely defined by the representations, the parameter l is uniquely defined by the
characteristic p of the field GF(q) in question.) The OS2FE(X,l) characteristic p of the field GF(q) in question.) The OS2FE(X,l)
mapping is called strict if it operates as the OS2FE(X,l) function, mapping is called strict if it operates as the OS2FE(X,l) function,
except that it fails whenever it would require at least one modular except that it fails whenever it would require at least one modular
reduction. Notice that the tight FE2OS mapping followed by the reduction. Notice that the tight FE2OS mapping followed by the
strict OS2FE mapping is the identity map (and, hence, OS2FE never strict OS2FE mapping is the identity map (and, hence, OS2FE never
fails in this case). fails in this case).
I.6. Conversion between Elements of Z mod n and Octet Strings (ZnE2OS, I.6. Conversion between Elements of Z_n and Octet Strings (ZnE2OS,
OS2ZnE) OS2ZnE)
There is a 1-1 correspondence between elements of the set Z_n of There is a 1-1 correspondence between elements of the set Z_n of
integers modulo n and integers in the interval [0,n), where each integers modulo n and integers in the interval [0,n), where each
element x of Z_n is uniquely represented by the integer x mod n. In element x of Z_n is uniquely represented by the integer x mod n. In
this case, x mod n can be uniquely represented by the octet string X this case, x mod n can be uniquely represented by the octet string X
according to the mapping of Appendix I.3 above. Note that both the according to the mapping of Appendix I.3 above. Note that both the
mapping from elements of Z_n to octet strings and the inverse mapping mapping from elements of Z_n to octet strings and the inverse mapping
from octet strings to elements of Z_n are only uniquely defined if from octet strings to elements of Z_n are only uniquely defined if
the octet string has a fixed size (e.g., the smallest integer l so the octet string has a fixed size (e.g., the smallest integer l so
skipping to change at page 74, line 6 skipping to change at page 75, line 41
coordinates are the octet string representations of the elements X coordinates are the octet string representations of the elements X
and Y of GF(q), respectively, using the tight FE2OS mapping of and Y of GF(q), respectively, using the tight FE2OS mapping of
Appendix I.5. Note that, since we use a tight representation, this Appendix I.5. Note that, since we use a tight representation, this
results in a pair of octet strings (each of length l*m), where the results in a pair of octet strings (each of length l*m), where the
parameters l and m are uniquely defined by the field GF(q) in parameters l and m are uniquely defined by the field GF(q) in
question. The inverse mapping results by converting the first and question. The inverse mapping results by converting the first and
second coordinate of this pair (each an octet string of length l*m) second coordinate of this pair (each an octet string of length l*m)
to, respectively, the elements X and Y of GF(q) via the strict OS2FE to, respectively, the elements X and Y of GF(q) via the strict OS2FE
mapping of Appendix I.5. Note that if it is not a priori known mapping of Appendix I.5. Note that if it is not a priori known
whether the input to this inverse mapping actually represents an whether the input to this inverse mapping actually represents an
affine curve point, one should check that this is indeed an ordered affine curve point, one should check that the output (X,Y) -- if
pair of octet strings (each of length l*m) and that the output (X,Y) defined -- is indeed an affine point of the curve in question, where
-- if defined -- is indeed an affine point of the curve in question, this operation fails if this is not the case. (This check involves
where this mapping fails if either condition is not satisfied. simply checking whether the ordered pair (X,Y) satisfies the defining
equation for this curve.)
The compressed point (X, t) or (t, X) is represented by the ordered The compressed point (X, t) or (t, X) is represented by the ordered
pair whose coordinates are the octet string representations of the pair whose coordinates are the octet string representations of the
parity bit t in {0,1} and the element X of GF(q), respectively, using parity bit t in {0,1} and the element X of GF(q), respectively, using
the tight FE2OS mapping of Appendix I.5. Note that, since we use the tight FE2OS mapping of Appendix I.5. Note that, since we use
tight representations, this results in an ordered pair of octet tight representations, this results in an ordered pair of octet
strings (of length 1 and l*m, respectively), where the parameters l strings (of length 1 and l*m, respectively), where the parameters l
and m are uniquely defined by the field GF(q) in question. The and m are uniquely defined by the field GF(q) in question. The
inverse mapping results by converting the first and second coordinate inverse mapping results by converting the first and second coordinate
of this pair (each an octet string, of length 1 and l*m, of this pair (each an octet string, of length 1 and l*m,
respectively) to, respectively, the element t of {0,1} and the respectively) to, respectively, the element t of {0,1} and the
element X of GF(q) via the strict OS2FE mapping of Appendix I.5, and element X of GF(q) via the strict OS2FE mapping of Appendix I.5, and
representing this as the compressed point (X, t) or (t, X) according representing this as the compressed point (X, t) or (t, X) according
to the curve model in question. Note that if it is not a priori to the curve model in question. Note that if it is not a priori
known whether the input to this inverse mapping actually represents a known whether the input to this inverse mapping actually represents a
compressed curve point, one should check that this is indeed an compressed curve point, one should check that the output (X, t) or
ordered pair of octet strings (of length 1 and l*m, respectively) and (t, X) -- if defined -- is indeed a compressed point of the curve in
that the output (X, t) or (t, X) -- if defined -- is indeed a question, using the point decompression process for this curve (see
compressed point of the curve in question, using the point Appendix H), where this operation fails if this is not the case.
decompression process for this curve (see Appendix H), where this (This check does include checking whether an element is a square in
mapping fails if either condition is not satisfied. GF(q), but does not require actually computing square roots (see also
the Note in Appendix K.1).)
NOTE 1: The representations of affine and compressed points above are NOTE 1: The representations of affine and compressed points above are
as ordered pairs of octet strings. In practice, one often represents as ordered pairs of octet strings. In practice, one often represents
these as octet strings instead, via right-concatenation of its these as octet strings instead, via right-concatenation of its
coordinates (in left-to-right order). Since each coordinate has coordinates (in left-to-right order). Since each coordinate has
known length, this operation is reversible. When appropriate, we known length, this operation is reversible. When appropriate, we
refer to the latter as the octet (rather than the pair) refer to the latter as the octet (rather than the pair)
representation of a point. representation of a point.
NOTE 2: The octet representation of compressed points above NOTE 2: The octet representation of compressed points above
skipping to change at page 88, line 5 skipping to change at page 89, line 42
outlier points in the small subgroup. outlier points in the small subgroup.
K.1. Square Roots in GF(q) K.1. Square Roots in GF(q)
Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see
Appendix K.1.1) or if q = 5 (mod 8) (see Appendix K.1.2). Details on Appendix K.1.1) or if q = 5 (mod 8) (see Appendix K.1.2). Details on
how to compute square roots for other values of q are out of scope. how to compute square roots for other values of q are out of scope.
If square roots are easy to compute in GF(q), then so are these in If square roots are easy to compute in GF(q), then so are these in
GF(q^2). GF(q^2).
NOTE: If one wishes to check whether an element is a square in GF(q),
rather than actually compute square roots, more efficient methods can
be used. As an example, if GF(q) is a prime field (i.e., q:=p), one
can efficiently check whether an element y is a square in GF(p) by
computing its Legendre symbol (y/p) (see Section 2.4.5 of
[Handbook]). Details on how to efficiently check whether an element
is a square in GF(q) for other values of q are out of scope. If
checking whether an element is a square is easy in GF(q), then so it
is in GF(q^2).
K.1.1. Square Roots in GF(q), where q = 3 (mod 4) K.1.1. Square Roots in GF(q), where q = 3 (mod 4)
If y is a nonzero element of GF(q) and z:=y^{(q-3)/4}, then y is a If y is a nonzero element of GF(q) and z:=y^{(q-3)/4}, then y is a
square in GF(q) only if y*z^2=1. If y*z^2=1, z is a square root of square in GF(q) only if y*z^2=1. If y*z^2=1, z is a square root of
1/y and y*z is a square root of y in GF(q). 1/y and y*z is a square root of y in GF(q).
K.1.2. Square Roots in GF(q), where q = 5 (mod 8) K.1.2. Square Roots in GF(q), where q = 5 (mod 8)
If y is a nonzero element of GF(q) and z:=y^{(q-5)/8}, then y is a If y is a nonzero element of GF(q) and z:=y^{(q-5)/8}, then y is a
square in GF(q) only if y^2*z^4=1. square in GF(q) only if y^2*z^4=1.
 End of changes. 25 change blocks. 
172 lines changed or deleted 253 lines changed or added

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