--- 1/draft-ietf-lwig-curve-representations-22.txt 2022-01-21 15:13:30.722850882 -0800 +++ 2/draft-ietf-lwig-curve-representations-23.txt 2022-01-21 15:13:30.998857830 -0800 @@ -1,28 +1,28 @@ lwig R. Struik Internet-Draft Struik Security Consultancy -Intended status: Informational Oct 25, 2021 -Expires: April 28, 2022 +Intended status: Informational Jan 21, 2022 +Expires: July 25, 2022 Alternative Elliptic Curve Representations - draft-ietf-lwig-curve-representations-22 + draft-ietf-lwig-curve-representations-23 Abstract This document specifies how to represent Montgomery curves and (twisted) Edwards curves as curves in short-Weierstrass form and illustrates how this can be used to carry out elliptic curve - computations using existing implementations of, e.g., ECDSA and ECDH - using NIST prime curves. We also provide extensive background - material that may be useful for implementers of elliptic curve - cryptography. + computations leveraging existing implementations and specifications + of, e.g., ECDSA and ECDH using NIST prime curves. We also provide + extensive background material that may be useful for implementers of + elliptic curve cryptography. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here. Status of This Memo @@ -33,25 +33,25 @@ Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." - This Internet-Draft will expire on April 28, 2022. + This Internet-Draft will expire on July 25, 2022. Copyright Notice - Copyright (c) 2021 IETF Trust and the persons identified as the + Copyright (c) 2022 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as @@ -108,125 +108,125 @@ 12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 29 12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 29 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 30 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 30 14.1. Normative References . . . . . . . . . . . . . . . . . . 30 14.2. Informative References . . . . . . . . . . . . . . . . . 33 Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 35 A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 35 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 36 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 36 - Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 36 + Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 37 B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 37 B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 39 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 40 C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 40 C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 41 C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 42 Appendix D. Relationships Between Curve Models . . . . . . . . . 43 D.1. Mapping between Twisted Edwards Curves and Montgomery Curves . . . . . . . . . . . . . . . . . . . . . . . . . 43 D.2. Mapping between Montgomery Curves and Weierstrass Curves 44 D.3. Mapping between Twisted Edwards Curves and Weierstrass Curves . . . . . . . . . . . . . . . . . . . . . . . . . 45 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 45 E.1. Curve Definition and Alternative Representations . . . . 45 - E.2. Switching between Alternative Representations . . . . . . 45 + E.2. Switching between Alternative Representations . . . . . . 46 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 47 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 49 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 49 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 50 - F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 50 - F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 51 + F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 51 + F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 52 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 53 G.1. Further Alternative Representations . . . . . . . . . . . 53 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 53 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 54 - G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 55 + G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 56 G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 56 G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 62 Appendix H. Point Compression . . . . . . . . . . . . . . . . . 68 - H.1. Point Compression for Weierstrass Curves . . . . . . . . 68 - H.2. Point Compression for Montgomery Curves . . . . . . . . . 69 + H.1. Point Compression for Weierstrass Curves . . . . . . . . 69 + H.2. Point Compression for Montgomery Curves . . . . . . . . . 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, - I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 72 + I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 73 I.4. Conversion between Octet Strings and Bit Strings (OS2BS, - BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 72 + BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 73 I.5. Conversion between Field Elements and Octet Strings - (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 73 + (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 74 I.6. Conversion between Elements of Z_n and Octet Strings - (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 73 - I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 74 - I.8. Conversion Between Curve Points and Octet Strings . . . . 75 - Appendix J. Representation Examples Curve25519 Family Members . 77 - J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 78 - J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 80 - J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 82 - J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 85 - J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 87 - Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 89 - K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 89 - 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) . . . . . 90 - K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 90 - K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 91 - K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 91 - K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 92 - K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 93 - K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 94 - K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 94 - K.4.2. Mapping to High-Order Points of Montgomery Curve . . 95 - K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 96 - K.5. Randomized Representation of Curve Points . . . . . . . . 97 - K.6. Completing the Mappings to Curve Points . . . . . . . . . 98 - Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 101 - L.1. Curve Definition and Alternative Representation . . . . . 102 - L.2. Switching Between Representations . . . . . . . . . . . . 102 - L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 102 - L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 104 - L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 104 - L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 105 - Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 105 - M.1. Curve Definition and Alternative Representations . . . . 105 - M.2. Switching between Alternative Representations . . . . . . 106 - M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 107 - Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 110 - N.1. Further Alternative Representations . . . . . . . . . . . 110 - N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 110 - N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 113 - N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 115 - N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 115 - N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 116 - Appendix O. Representation Examples Curve448 Family Members . . 116 - O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 117 - O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 120 - O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 123 - O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 126 - O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 129 - O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 131 - Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 134 - P.1. Conversion to Integers in Z_n via Modular Reduction . . . 135 - P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 136 - P.3. Conversion to Integers in Z_n via the Discard Method . . 137 - Appendix Q. ECDSA signatures . . . . . . . . . . . . . . . . . . 137 - Q.1. ECDSA Signing Operation . . . . . . . . . . . . . . . . . 137 - Q.2. ECDSA Verification Operation . . . . . . . . . . . . . . 138 - Q.3. Representation Examples ECDSA . . . . . . . . . . . . . . 139 - Q.3.1. Example of ECDSA with Wei25519 and SHA-256 . . . . . 140 - Q.3.2. Example of ECDSA with Wei25519 and SHAKE128 . . . . . 142 - Q.3.3. Example of ECDSA with Wei448 and SHAKE256 . . . . . . 144 - Q.3.4. Example of ECDSA with P-256 and SHA-256 . . . . . . . 146 - Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 149 + (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 74 + I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 75 + I.8. Conversion Between Curve Points and Octet Strings . . . . 76 + Appendix J. Representation Examples Curve25519 Family Members . 78 + J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 79 + J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 81 + J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 83 + J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 86 + J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 88 + Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 90 + K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 90 + K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 91 + K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 91 + K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 91 + K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 92 + K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 92 + K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 93 + K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 94 + K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 95 + K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 95 + K.4.2. Mapping to High-Order Points of Montgomery Curve . . 96 + K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 97 + K.5. Randomized Representation of Curve Points . . . . . . . . 98 + K.6. Completing the Mappings to Curve Points . . . . . . . . . 99 + Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 102 + L.1. Curve Definition and Alternative Representation . . . . . 103 + L.2. Switching Between Representations . . . . . . . . . . . . 103 + L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 103 + L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 105 + L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 105 + L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 106 + Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 106 + M.1. Curve Definition and Alternative Representations . . . . 106 + M.2. Switching between Alternative Representations . . . . . . 107 + M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 108 + Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 111 + N.1. Further Alternative Representations . . . . . . . . . . . 111 + N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 111 + N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 114 + N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 116 + N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 116 + N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 117 + Appendix O. Representation Examples Curve448 Family Members . . 117 + O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 118 + O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 121 + O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 124 + O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 127 + O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 130 + O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 132 + Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 135 + P.1. Conversion to Integers in Z_n via Modular Reduction . . . 136 + P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 137 + P.3. Conversion to Integers in Z_n via the Discard Method . . 138 + Appendix Q. ECDSA signatures . . . . . . . . . . . . . . . . . . 138 + Q.1. ECDSA Signing Operation . . . . . . . . . . . . . . . . . 138 + Q.2. ECDSA Verification Operation . . . . . . . . . . . . . . 139 + Q.3. Representation Examples ECDSA . . . . . . . . . . . . . . 140 + Q.3.1. Example of ECDSA with Wei25519 and SHA-256 . . . . . 141 + Q.3.2. Example of ECDSA with Wei25519 and SHAKE128 . . . . . 143 + Q.3.3. Example of ECDSA with Wei448 and SHAKE256 . . . . . . 145 + Q.3.4. Example of ECDSA with P-256 and SHA-256 . . . . . . . 147 + Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 150 1. Fostering Code Reuse with New Elliptic Curves Elliptic curves can be represented using different curve models. Recently, IETF standardized elliptic curves that are claimed to have better performance and improved robustness against "real world" attacks than curves represented in the traditional short-Weierstrass curve model. These so-called CFRG curves [RFC7748] use the Montgomery curve model and the model of twisted Edwards curves. @@ -388,31 +388,32 @@ 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 RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature scheme, with instantiation by the twisted Edwards curve Edwards25519. One can implement the computation of the ephemeral key pair for Ed25519 using an existing Montgomery curve implementation by (1) - 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 - Ed25519. As before, the representation change can be implemented via - a simple wrapper. Note that the Montgomery ladder specified in - Section 5 of RFC7748 [RFC7748] does not provide sufficient - information to reconstruct R':=(u, v) (since it does not compute the - v-coordinate of R'). However, this deficiency can be remedied by - using a slightly modified version of the Montgomery ladder that - 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 - G' of Curve25519 as well). For details, see Appendix C.2. + generating a random public-private key pair (k, R':=k*G') for + Curve25519; (2) representing this public-private key as the pair (k, + R:=k*G) for Ed25519. As before, the representation change can be + implemented via a simple wrapper. Note that the Montgomery ladder + specified in Section 5 of RFC7748 [RFC7748] does not provide + sufficient information to reconstruct R':=(u, v) (since it does not + compute the v-coordinate of R'). However, this deficiency can be + remedied by using a slightly modified version of the Montgomery + ladder that 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 G' of Curve25519 as well). For details, see + Appendix C.2. 4.3. Specification of ECDSA25519 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 with other Weierstrass curves (that satisfy additional cryptographic criteria). In particular, one can instantiate this scheme with the Weierstrass curve Wei25519 and the hash function SHA-256 [FIPS-180-4], where an implementation may generate an ephemeral public-private key pair for Wei25519 by (1) internally carrying out @@ -458,24 +459,24 @@ Edwards curve (Ed448) or as points of a short-Weierstrass curve (Wei448). For the specification of Wei448 and its relationship to Curve448 and Ed448, see Appendix M. As with ECDH25519, one can now easily define a NIST-compliant version of co-factor Diffie-Hellman key agreement (denoted by ECDH448), by simply reusing the example of Section 4.1, but now using the short-Weierstrass curve Wei448, rather than Wei25519 (with the same representation and bit/byte-ordering conventions). Similarly, one can easily specify ECDSA with Wei448 and a suitable hash function, by simply reusing the example of Section 4.3, but now using the short-Weierstrass curve Wei448, rather - than Wei25519, and picking as hash function SHAKE256 [FIPS-202] with - output size of d0=512 bits. We denote by ECDSA448 the resulting - signature scheme (with the same representation and bit/byte-ordering - conventions). + than Wei25519, and picking as hash function SHAKE256 (see Section 6.3 + of [FIPS-202]) with output size of d0=512 bits. We denote by + ECDSA448 the resulting signature scheme (with the same representation + and bit/byte-ordering 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 @@ -578,28 +579,28 @@ these finite field operations, by specifying curves defined over a field GF(q), where the field size q has a special form or a specific bit-length (typically, close to a multiple of a machine word). Depending on the implementation strategy, the bit-length of q may also facilitate reduced so-called "carry-effects" of integer arithmetic. Most curves use a combination of these design philosophies. All NIST curves [FIPS-186-4] and Brainpool curves [RFC5639] are Weierstrass curves with a=-3 domain parameter, thus facilitating more efficient - elliptic curve group operations (via so-called Jacobian coordinates). - The NIST curves and the Montgomery curve Curve25519 are defined over - prime fields, where the prime number has a special form, whereas the - Brainpool curves - by design - use a generic prime number. None of - the NIST prime curves, nor the Brainpool curves, can be expressed as - Montgomery or twisted Edwards curves, whereas - conversely - - Montgomery curves and twisted curves can be expressed as Weierstrass - curves. + elliptic curve group operations than with a<>-3 (via so-called + Jacobian coordinates). The NIST curves and the Montgomery curve + Curve25519 are defined over prime fields, where the prime number has + a special form, whereas the Brainpool curves - by design - use a + generic prime number. None of the NIST prime curves, nor the + Brainpool curves, can be expressed as Montgomery or twisted Edwards + curves, whereas - conversely - Montgomery curves and twisted curves + can be expressed as Weierstrass curves. While use of Wei25519 allows reuse of existing generic code that implements short-Weierstrass curves, such as the NIST curve P-256, to also implement the CFRG curves Curve25519 or Edwards25519, this obviously does not result in an implementation of these CFRG curves that exploits the specific structure of the underlying field or other specific domain parameters (since generic). Reuse of generic code, therefore, may result in a less computationally efficient curve implementation than would have been possible if the implementation had specifically targeted Curve25519 or Edwards25519 alone (with the @@ -640,20 +641,29 @@ and feedback that have made the implemented protocols more mature. It is up to the individual working groups to use this information as they see fit. Nikolas Rosener evaluated the performance of switching between different curve models in his Master's thesis [Rosener]. For an implementation of Wei25519, see . For support of this curve in tinydtls, see . + ANSSI (the national cybersecurity agency of France) implemented the + Ed25519 signature scheme using a generic ECC library for short- + Weierstrass curves instantiated with the Wei25519 domain parameters, + where this was motivated by the desire to both keep the library core + mathematical foundations simple and keep the defense-in-depth + (regarding software security and side-channels) focused on a rather + limited part. For further details, see + . + According to , an implementation of Wei25519 on the Kinets LTC ECC HW platform improves the performance by over a factor ten compared to a stand-alone implementation of Curve25519 without hardware support. The signature scheme ECDSA25519 (see Section 4.3) is supported in [RFC8928]. 8. Security Considerations @@ -1067,23 +1077,23 @@ 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 + Wei25519 and the hash function SHA-256, 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- + where ECDSA with SHA-256 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), @@ -1361,21 +1371,22 @@ encodings, see Section 10.3; Algorithm Analysis Document(s): Section 4.4 of this specification. 13. Acknowledgements Thanks to Nikolas Rosener for discussions surrounding implementation details of the techniques described in this document and to Phillip Hallam-Baker for triggering inclusion of verbiage on the use of Montgomery ladders with recovery of the y-coordinate. Thanks to - Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews. + Stanislav Smyshlyaev, Vasily Nikolaev, and Benjamin Smith for their + careful reviews. 14. References 14.1. Normative References [ANSI-X9.62] ANSI X9.62-2005, "Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)", American National Standard for Financial Services, Accredited Standards Committee X9, @@ -1398,20 +1409,24 @@ Extendable-Output Functions, Federal Information Processing Standards Publication 202", US Department of Commerce/National Institute of Standards and Technology, Gaithersburg, MD, August 2015. [I-D.ietf-cose-rfc8152bis-algs] Schaad, J., "CBOR Object Signing and Encryption (COSE): Initial Algorithms", draft-ietf-cose-rfc8152bis-algs-12 (work in progress), September 2020. + [RFC0020] Cerf, V., "ASCII format for network interchange", STD 80, + RFC 20, DOI 10.17487/RFC0020, October 1969, + . + [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006, . [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., @@ -1696,82 +1711,85 @@ The set of points of each curve defined in Appendix A forms a commutative group under addition (denoted by '+'). In Appendix C we specify the group laws, which depend on the curve model in question. For completeness, we here include some common elliptic curve nomenclature and basic properties (primarily so as to keep this document self-contained). These notions are mainly used in Appendix E and Appendix G and not essential for our exposition. This section can be skipped at first reading. Any point P of a curve E is a generator of the cyclic subgroup - (P):={k*P | k = 0, 1, 2,...} of the curve. (Here, k*P denotes the +

:={k*P | k = 0, 1, 2,...} of the curve. (Here, k*P denotes the sum of k copies of P, where 0*P is the identity element O of the 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

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 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. 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 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 denoted by G, while a point of order dividing h is said to be in the small subgroup (or said to be a low-order point). For curves of prime order, this small subgroup is the singleton set, consisting of only the identity element O. A point that is not in the small subgroup is said to be a high-order point (since it has order at least n). A point P of the curve is in the small subgroup if h*P=O - (and is a high-order point otherwise); this point has order n if + (and is a high-order point otherwise); this point P has order n if n*P=O and if it is not the identity element O. (The latter order check is commonly called full public key validation.) The above definitions extend to curves with a relatively large co-factor, by defining n to be the size of its largest prime-order subgroup. - 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

, there 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 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 of the curve, if such a number exists. - Random points R of (P), where P has order l, can be computed by + Random points R of

, where P has order l, can be computed by generating a random integer k in the interval [0, l-1] and by - subsequently computing R:=k*P, where R has order l/gcd(k,l). In - particular, if P is a high-order point, then so is R, unless k is a - multiple of n (in which case R is a low-order point). For methods - for generating k, see Appendix P. + subsequently computing R:=k*P, where R then has order l/gcd(k,l). In + particular, if P is a high-order point (of curve E of order h*n), + then so is R, unless k is a multiple of n (in which case R is a low- + order point). For methods for generating k, see Appendix P. 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 key, and the point R the corresponding public key. The private key k can be represented as an integer in the interval [0,n-1], where G has order n. If this representation is nonzero, R has order n; otherwise, it has order one and is the identity element O of the curve. A curve E defined over the field GF(q) has order |E| relatively close - to q, where, in fact, |E|=q+1-t for some integer t (the so-called + to q. More precisely, |E|=q+1-t for some integer t (the so-called trace) with absolute value at most 2*|sqrt(q)|. This is commonly referred to as the Hasse bound. In this document, a quadratic twist of a curve E defined over a field GF(q) is a specific curve E' related to E defined over the same field, with cardinality |E'|, where |E|+|E'|=2*(q+1). If E is a curve in one of the curve models specified in this document, a quadratic twist E' of this curve can be expressed using the same curve model, although (naturally) with its own curve parameters (see - Appendix A). Points that are both points of E and E' have order one - or two. Two curves E and E' defined over a field GF(q) are said to - be isogenous if these have the same order and are said to be - isomorphic if these have the same group structure. Note that - isomorphic curves have necessarily the same order and are, thus, a - special case of isogenous curves. Further details are out of scope. + Appendix A). Points that are points of both E and E' have order one + or two. Two curves E1 and E2 defined over the field GF(q) are said + to be isogenous if these have the same order and are said to be + isomorphic if the defining equation of E1 can be transformed into the + defining equation of E2 via a so-called admissible change of + variables. Note that isomorphic curves have necessarily the same + order and are, thus, a special case of isogenous curves. Isomorphic + curves have the same group structure, whereas this is not necessarily + the case for isogenous curves. Further details are out of scope. Curves in short-Weierstrass form can have prime order, whereas Montgomery curves and twisted Edwards curves always have an order that is a multiple of four (and, thereby, a small subgroup of cardinality four). An ordered pair (x, y) whose coordinates are elements of GF(q) can be associated with any ordered triple of the form [x*z: y*z: z], where z is a nonzero element of GF(q), and can be uniquely recovered from such a representation. The latter representation is commonly called @@ -1787,21 +1805,22 @@ Montgomery curve). Those can also be represented in projective coordinates. Further details are out of scope. B.2. Finite Fields The field GF(q), where q is a prime power, is defined as follows. If q:=p is a prime number, the field GF(p) consists of the integers in the interval [0,p-1] and two binary operations on this set: addition and multiplication modulo p. This field is commonly called - a prime field. + a prime field. The additive and multiplicative identity elements are + 0 and 1, respectively. If q:=p^m, where p is a prime number and where m>0, the field GF(q) is defined in terms of an irreducible polynomial f(z) in z of degree m with coefficients in GF(p) (i.e., f(z) cannot be written as the product of two polynomials in z of lower degree with coefficients in GF(p)): in this case, GF(q) consists of the polynomials in z of degree smaller than m with coefficients in GF(p) and two binary operations on this set: polynomial addition and polynomial multiplication modulo the irreducible polynomial f(z). By definition, each element x of GF(q) is a polynomial in z of degree @@ -1810,81 +1829,83 @@ coefficients in GF(p), where x_i is the coefficient of z^i of polynomial x. Note that this representation depends on the irreducible polynomial f(z) of the field GF(p^m) in question (which is often fixed in practice). Note that GF(q) contains the prime field GF(p) as a subset. If m=1, the definitions of GF(p) and GF(p^1) above coincide, since each nonzero element of GF(p) can be viewed as a polynomial in z of degree zero. If m>1 (i.e., if q is a strict prime power), then GF(q) is called a (nontrivial) extension field of GF(p). The number p is called the characteristic of GF(q). - Any nonzero element g of GF(q) is a generator of the cyclic subgroup - (g):={g^k | k = 0, 1, 2,...} of GF(q)\{0}. (Here, g^k denotes the - product of k copies of g, where g^0 is the identity element 1 of - GF(q).) If (g) has cardinality l, then l is called the order of g - and l is the smallest positive integer so that g^l=1. For each - finite field GF(q), the set GF(q)\{0} is cyclic, i.e., it is - generated by some nonzero element hereof. Each such generator is - called a primitive element of GF(q) and has order q-1. Each nonzero - element of GF(q) has order dividing q-1 (commonly referred to as - Fermat's Little Theorem). + Any nonzero element g of GF(q) is a generator of the cyclic + multiplicative subgroup :={g^k | k = 0, 1, 2,...} of GF(q)\{0}. + (Here, g^k denotes the product of k copies of g, where g^0 is the + multiplicative identity element 1 of GF(q)\{0}.) If has + cardinality l, then l is called the order of g and l is the smallest + positive integer so that g^l=1. For each finite field GF(q), the set + GF(q)\{0} forms a cyclic group, i.e., it is generated by some nonzero + element hereof. Each such generator is called a primitive element of + GF(q) and has order q-1. Each nonzero element of GF(q) has order + dividing q-1 (a property commonly referred to as Fermat's Little + Theorem). A field element y is called a square in GF(q) if it can be expressed as y:=x^2 for some x in GF(q); it is called a non-square in GF(q) otherwise. If y is a square in GF(q), we denote by sqrt(y) one of its square roots (the other one being -sqrt(y)). For methods for - computing square roots and inverses in GF(q) - if these exist - see - Appendix K.1 and Appendix K.2, respectively. For methods for mapping - a nonzero field element that is not a square in GF(q) to a point of a - curve, see Appendix K.3 (or see Appendix K.4, if one wishes to always - obtain a high-order point of the curve in question). + computing square roots in GF(q) - if these exist - and for computing + inverses in GF(q)\{0}, see Appendix K.1 and Appendix K.2, + respectively. For methods for mapping a nonzero field element that + is not a square in GF(q) to a point of a curve, see Appendix K.3 (or + see Appendix K.4, if one wishes to always obtain a high-order point + of the curve in question). NOTE: The curves in Appendix E and Appendix G are all defined over a prime field GF(p), thereby reducing all operations to simple modular integer arithmetic. Strictly speaking we could, therefore, have refrained from introducing extension fields. Nevertheless, we included the more general exposition, so as to accommodate potential introduction of new curves that are defined over a (nontrivial) extension field at some point in the future. This includes curves proposed for post-quantum isogeny-based schemes, which are defined over a quadratic extension field (i.e., where q:=p^2), and elliptic curves used with pairing-based cryptography. The exposition in either case is almost the same and now automatically yields, e.g., data conversion routines for any finite field object (see - Appendix I). Readers not interested in this, could simply view all + Appendix I). Readers not interested in this could simply view all fields as prime fields. Appendix C. Elliptic Curve Group Operations This section specifies group operations for elliptic curves in short- Weierstrass form, for Montgomery curves, and for twisted Edwards curves. C.1. Group Laws for Weierstrass Curves For each point P of the Weierstrass curve W_{a,b}, the point at infinity O serves as identity element, i.e., P + O = O + P = P. For each affine point P:=(X, Y) of the Weierstrass curve W_{a,b}, the point -P is the point (X, -Y) and one has P + (-P) = O (i.e., -P is the inverse of P). For the point at infinity O, one has -O:=O. Let P1:=(X1, Y1) and P2:=(X2, Y2) be distinct affine points of the Weierstrass curve W_{a,b} and let Q:=P1 + P2, where Q is not the - identity element. Then Q:=(X, Y), where + identity element. Then Q=(X, Y), where X + X1 + X2 = lambda^2 and Y + Y1 = lambda*(X1 - X), where lambda:= (Y2 - Y1)/(X2 - X1). Let P:=(X1, Y1) be an affine point of the Weierstrass curve W_{a,b} - and let Q:=2*P, where Q is not the identity element. Then Q:=(X, Y), + and let Q:=2*P, where Q is not the identity element. Then Q=(X, Y), where X + 2*X1 = lambda^2 and Y + Y1 = lambda*(X1 - X), where lambda:=(3*X1^2 + a)/(2*Y1). From the group laws above it follows that if P=(X, Y), P1=(X1, Y1), and P2=(X2, Y2) are distinct affine points of the Weierstrass curve W_{a,b} with P2:=P+P1 and if Y is nonzero, then the Y-coordinate of P1 can be expressed in terms of the X-coordinates of P, P1, and P2, @@ -1904,28 +1925,28 @@ For each point P of the Montgomery curve M_{A,B}, the point at infinity O serves as identity element, i.e., P + O = O + P = P. For each affine point P:=(u, v) of the Montgomery curve M_{A,B}, the point -P is the point (u, -v) and one has P + (-P) = O (i.e., -P is the inverse of P). For the point at infinity O, one has -O:=O. Let P1:=(u1, v1) and P2:=(u2, v2) be distinct affine points of the Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the - identity element. Then Q:=(u, v), where + identity element. Then Q=(u, v), where u + u1 + u2 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), where lambda:=(v2 - v1)/(u2 - u1). Let P:=(u1, v1) be an affine point of the Montgomery curve M_{A,B} - and let Q:=2*P, where Q is not the identity element. Then Q:=(u, v), + and let Q:=2*P, where Q is not the identity element. Then Q=(u, v), where u + 2*u1 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), where lambda:=(3*u1^2 + 2*A*u1+1)/(2*B*v1). From the group laws above it follows that if P=(u, v), P1=(u1, v1), and P2=(u2, v2) are distinct affine points of the Montgomery curve M_{A,B} with P2:=P+P1 and if v is nonzero, then the v-coordinate of P1 can be expressed in terms of the u-coordinates of P, P1, and P2, @@ -1950,29 +1971,28 @@ Edwards curves are out of scope. For each point P of the twisted Edwards curve E_{a,d}, the point O:=(0,1) serves as identity element, i.e., P + O = O + P = P. For each point P:=(x, y) of the twisted Edwards curve E_{a,d}, the point -P is the point (-x, y) and one has P + (-P) = O (i.e., -P is the inverse of P). Let P1:=(x1, y1) and P2:=(x2, y2) be points of the twisted Edwards - curve E_{a,d} and let Q:=P1 + P2. Then Q:=(x, y), where + curve E_{a,d} and let Q:=P1 + P2. Then Q=(x, y), where x = (x1*y2 + x2*y1)/(1 + d*x1*x2*y1*y2) and y = (y1*y2 - a*x1*x2)/(1 - d*x1*x2*y1*y2). Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and - let Q:=2*P. Then Q:=(x, y), where - + let Q:=2*P. Then Q=(x, y), where x = (2*x1*y1)/(1 + d*x1^2*y1^2) and y = (y1^2 - a*x1^2)/(1 - d*x1^2*y1^2). Note that one can use the formulae for point addition for point doubling, taking inverses, and adding the identity element as well (i.e., the point addition formulae are uniform and complete (subject to our Note above)). From the group laws above (subject to our Note above) it follows that @@ -2008,26 +2029,30 @@ where a is a square in GF(q), whereas d is not), this defines a one- to-one correspondence, which - in fact - is an isomorphism between M_{A,B} and E_{a,d}, thereby showing that, e.g., the discrete logarithm problem in either curve model is equally hard. For the Montgomery curves and twisted Edwards curves we consider, the mapping from M_{A,B} to E_{a,d} is defined by mapping the point at infinity O and the point (0, 0) of order two of M_{A,B} to, respectively, the point (0, 1) and the point (0, -1) of order two of E_{a,d}, while mapping each other point (u, v) of M_{A,B} to the - point (x,y):=(u/v,(u-1)/(u+1)) of E_{a,d}. The inverse mapping from - E_{a,d} to M_{A,B} is defined by mapping the point (0, 1) and the - point (0, -1) of order two of E_{a,d} to, respectively, the point at - infinity O and the point (0, 0) of order two of M_{A,B}, while each - other point (x, y) of E_{a,d} is mapped to the point - (u,v):=((1+y)/(1-y),(1+y)/((1-y)*x)) of M_{A,B}. + point (x,y):=(u/v,(u-1)/(u+1)) of E_{a,d}. (Note that this is well- + defined, since neither (A-2)/B nor A^2-4 are squares in GF(q), so + M_{A,B} has a single point of order two and no affine points (u,v) + with u=-1.) The inverse mapping from E_{a,d} to M_{A,B} is defined + by mapping the point (0, 1) and the point (0, -1) of order two of + E_{a,d} to, respectively, the point at infinity O and the point (0, + 0) of order two of M_{A,B}, while each other point (x, y) of E_{a,d} + is mapped to the point (u,v):=((1+y)/(1-y),(1+y)/((1-y)*x)) of + M_{A,B}. (Note that this is well-defined, since for points (x,y) of + E_{a,d}, x=0 only if y=(+/-)1.) Implementations may take advantage of this mapping to carry out elliptic curve group operations originally defined for a twisted Edwards curve on the corresponding Montgomery curve, or vice-versa, and translating the result back to the original curve, thereby potentially allowing code reuse. D.2. Mapping between Montgomery Curves and Weierstrass Curves One can map points of the Montgomery curve M_{A,B} to points of the @@ -2035,25 +2060,25 @@ b:=(2*A^3-9*A)/(27*B^3). This defines a one-to-one correspondence, which - in fact - is an isomorphism between M_{A,B} and W_{a,b}, thereby showing that, e.g., the discrete logarithm problem in either curve model is equally hard. The mapping from M_{A,B} to W_{a,b} is defined by mapping the point at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while mapping each other point (u,v) of M_{A,B} to the point (X,Y):=((u+A/3)/B,v/B) of W_{a,b}. - Note that not all Weierstrass curves can be injectively mapped to - Montgomery curves, since the latter have a point of order two and the - former may not. In particular, if a Weierstrass curve has prime - order, such as is the case with the so-called "NIST prime curves", - this inverse mapping is not defined. + Note that not all Weierstrass curves can be mapped to Montgomery + curves, since the latter have a point of order two and the former may + not. In particular, if a Weierstrass curve has prime order, such as + is the case with the so-called NIST prime curves, this inverse + mapping is not defined. If the Weierstrass curve W_{a,b} has a point (alpha,0) of order two and c:=a+3*(alpha)^2 is a square in GF(q), one can map points of this curve to points of the Montgomery curve M_{A,B}, where A:=3*alpha/ gamma and B:=1/gamma and where gamma is any square root of c. In this case, the mapping from W_{a,b} to M_{A,B} is defined by mapping the point at infinity O of W_{a,b} to the point at infinity O of M_{A,B}, while mapping each other point (X,Y) of W_{a,b} to the point (u,v):=((X-alpha)/gamma,Y/gamma) of M_{A,B}. As before, this defines a one-to-one correspondence, which - in fact - is an isomorphism @@ -2119,23 +2144,22 @@ Each affine point (u, v) of Curve25519 corresponds to the point (X, Y):=(u + A/3, v) of Wei25519, while the point at infinity of Curve25519 corresponds to the point at infinity of Wei25519. (Here, we used the mappings of Appendix D.2 and that B=1.) Under this mapping, the base point (Gu, Gv) of Curve25519 corresponds to the base point (GX, GY) of Wei25519. The inverse mapping maps the affine point (X, Y) of Wei25519 to (u, v):=(X - A/3, Y) of Curve25519, while mapping the point at infinity of Wei25519 to the point at infinity of Curve25519. Note that this mapping involves a simple shift of the first coordinate and can be implemented via integer-only arithmetic - as a shift of (p+A)/3 for the isomorphic mapping and a shift of - -(p+A)/3 for its inverse, where delta=(p+A)/3 is the element of GF(p) - defined by + as a shift of delta for the isomorphic mapping and a shift of -delta + for its inverse, where delta:=(p+A)/3 is the integer defined by delta 19298681539552699237261830834781317975544997444273427339909597 334652188435537 (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaad2451). (Note that, depending on the implementation details of the field arithmetic, one may have to shift the result by +p or -p if this integer is not in the interval [0,p-1].) @@ -3324,64 +3349,96 @@ Appendix I. Data Conversions This section introduces various data conversion routines that are useful when representing integers, finite field elements, and curve points as binary or octet strings. I.1. Strings and String Operations The string over some alphabet S consisting of the symbols x_{l-1}, x_{l-2}, ..., x_1, x_0 (each in S), in this order, is denoted by - str(x_{l-1}, x_{l-2}, ..., x_1, x_0). The length of this string - (over S) is the number of symbols it contains (here: l). The empty - string is the (unique) string of length l=0. + str(x_{l-1}, x_{l-2}, ..., x_1, x_0) (or simply as x_{l-1} x_{l-2} + ... x_1 x0, if the individual symbols can be uniquely identified). + The length of this string (over S) is the number of symbols it + contains (here: l). The empty string is the (unique) string of + length l=0. Strings are commonly indicated by surrounding these by + double quotation marks. The right-concatenation of two strings X and Y (defined over the same alphabet) is the string Z consisting of the symbols of X (in the same order) followed by the symbols of Y (in the same order). The length of the resulting string Z is the sum of the lengths of X and Y. This string operation is denoted by Z:=X||Y. The string X is called a - prefix of Z; the string Y a postfix. The t-prefix of a string Z of - length l is its unique prefix X of length t; the t-postfix its unique - postfix Y of length t (where in both cases t is an integer in the - interval [0,l]). One can define these notions as well if t is + prefix of Z; the string Y a postfix of Z. The t-prefix of a string Z + of length l is its unique prefix X of length t; the t-postfix its + unique postfix Y of length t (where in both cases t is an integer in + the interval [0,l]). One can define these notions as well if t is outside the interval [0,l] by stipulating that a t-prefix or t-postfix is the empty string if t is negative and that it is the entire string Z if t is larger than l. Sometimes, a t-prefix of a string Z is denoted by trunc-left(Z,t); a t-postfix by trunc- right(Z,t). A string X is called a substring of Z if it is a prefix of some postfix of Z. The string resulting from prepending the - string Y with X is the string X||Y. + string Y with X is the string X||Y. The symbols of a string Z of + length l can be labelled from left to right, using consecutive + integers in the interval [0,l) starting with zero, where each label + identifies a symbol via its position in the string. An octet (or byte) is an integer in the interval [0,256). An octet string is a string, where the alphabet is the set of all octets. A binary string (or bit string, for short) is a string, where the - alphabet is the set {0,1} of binary digits. Note that the length of - a string is defined in terms of the underlying alphabet, as are the - operations in the previous paragraph. + alphabet is the set {0,1} of binary digits. A hex digit is an + integer in the interval [0,16), with the convention to denote the + integers 10, 11, 12, 13, 14, and 15 by the symbols 'a', 'b', 'c', + 'd', 'e', and 'f', respectively. A hexadecimal string (or hex + string, for short) is a string, where the alphabet is the set of all + hex digits. Note that the length of a string is defined in terms of + the underlying alphabet, as are the operations in the previous + paragraph. + + Note that an octet z can be uniquely represented in base 16 as the + integer z:=16*z1+z0, where z1 and z0 are hex digits, and, thereby, as + the hexadecimal string z1||z0 of length two. This allows a concise + description of octet strings as hex strings (commonly indicated by + the "0x"-prefix). + + An ASCII character is a symbol of the so-called ASCII alphabet: the + set of symbols corresponding to the set of integers in the interval + [0,128) according to the ASCII-table (see [RFC0020]). An ASCII + string is a string, where the alphabet is the set of all ASCII + characters. All ASCII characters corresponding to integers in the + interval [33,126] are single printable characters (and can therefore + be uniquely identified in a printable ASCII string). There is a 1-1 + correspondence between ASCII characters and integers in the interval + [0,128), thereby allowing each ASCII character to be uniquely + represented by an octet. I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) There is a 1-1 correspondence between bit strings of length l and 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:=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 while the mapping from bit strings to integers is uniquely defined, 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 string of length at least t (due to leading zero coefficients in base 2 representation). The latter representation is called tight if the bit string representation has minimal length (the so-called bit- length of the integer in question). This defines the mapping BS2I from bit strings to integers and the mapping I2BS(x,l) from non- - negative integers smaller than 2^l to bit strings of length l. + negative integers smaller than 2^l to bit strings of length l. Note + that this also defines a 1-1 correspondence between bit strings of + length four and hex digits, and the encoding of ASCII characters as + bit strings of length eight (where the leftmost bit has the value + zero), as stipulated in [RFC0020]. I.3. Conversion between Octet Strings and Integers (OS2I, I2OS) There is a 1-1 correspondence between octet strings of length l and 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:=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 that while the mapping from octet strings to integers is uniquely defined, the inverse mapping from integers to octet strings is not, @@ -4247,21 +4304,21 @@ K.2. Inversion If y is an integer and gcd(y,n)=1, one can efficiently compute 1/y (mod n) via the extended Euclidean Algorithm (see Section 2.2.5 of [GECC]). One can use this algorithm as well to compute the inverse of a nonzero element y of a prime field GF(p), since gcd(y,p)=1. The inverse of a nonzero element y of GF(q) can be computed as - 1/y:=y^{q-2} (since y^{q-1}=1). + 1/y:=y^{q-2} (since y^{q-1}=1 by Fermat's Little Theorem). If inverses are easy to compute in GF(q), then so are these in GF(q^2). Further details are out of scope. The inverses of two nonzero elements y1 and y2 of GF(q) can be computed by first computing the inverse z of y1*y2 and by subsequently computing y2*z=:1/y1 and y1*z=:1/y2. NOTE 1: This method can be used to compute the inverse of a nonzero element y of GF(q) indirectly, as lambda*(lambda*y)^{-1}, where @@ -4426,24 +4483,24 @@ The description below assumes that the domain parameters a and b of the Weierstrass curve W_{a,b} are nonzero. For ease of exposition, we define f(z):=z^3+a*z+b. (Note that for an affine point (X,Y) of W_{a,b} one has Y^2=f(X).) If t is an element of GF(q) that is not a square in GF(q) and that is unequal to -1, the mapping of Appendix K.3.1 yields an affine point P(t):=(X, Y) of W_{a,b}. Let P0:=(X0, Y0) be a fixed affine point of W_{a,b} for which neither P0, P0 + P(t), nor P0 - P(t) is in the - small subgroup of W_{a,b}. (Note that this implies that P0 and P(t) - are distinct affine points of the curve and that these are not each - other's inverse.) For binary digit s, the point Q(t,s) is now - defined as follows: + small subgroup of W_{a,b} (for any non-square element t<>-1 of + GF(q)). (Note that this implies that P0 and P(t) are distinct affine + points of the curve and that these are not each other's inverse.) + For binary digit s, the point Q(t,s) is now defined as follows: a. If par(Y0*Y)=s, then the pair (t,s) is mapped to the point Q(t,s):=P0 + P(t); b. If par(Y0*Y)<>s, then the pair (t,s) is mapped to the point Q(t,s):=P0 - P(t). Note that this mapping is properly defined as long as the fixed point P0 (the so-called "curve offset") alluded to above indeed exists. In cases of practical interest that we are aware of, this is indeed the @@ -4468,24 +4525,24 @@ The description below assumes that the domain parameters A and B of the Montgomery curve M_{A,B} are nonzero. For ease of exposition, we define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of M_{A,B} one has B*v^2=f(u).) If t is an element of GF(q) that is not a square in GF(q) and that is unequal to -1, the mapping of Appendix K.3.2 yields an affine point P(t):=(u, v) of M_{A,B}. Let P0:=(u0, v0) be a fixed affine point of M_{A,B} for which neither P0, P0 + P(t), nor P0 - P(t) is in the - small subgroup of M_{A,B}. (Note that this implies that P0 and P(t) - are distinct affine points of the curve and that these are not each - other's inverse.) For binary digit s, the point Q(t,s) is now - defined as follows: + small subgroup of M_{A,B} (for any non-square element t<>-1 of + GF(q)). (Note that this implies that P0 and P(t) are distinct affine + points of the curve and that these are not each other's inverse.) + For binary digit s, the point Q(t,s) is now defined as follows: a. If par(B*v0*v)=s, then the pair (t,s) is mapped to the point Q(t,s):=P0 + P(t); b. If par(B*v0*v)<>s, then the pair (t,s) is mapped to the point Q(t,s):=P0 - P(t). Note that this mapping is properly defined as long as the fixed point P0 (the so-called "curve offset") alluded to above indeed exists. In cases of practical interest that we are aware of, this is indeed the @@ -4989,23 +5046,23 @@ Each affine point (u, v) of Curve448 corresponds to the point (X, Y):=(u + A/3, v) of Wei448, while the point at infinity of Curve448 corresponds to the point at infinity of Wei448. (Here, we used the mappings of Appendix D.2 and that B=1.) Under this mapping, the base point (Gu, Gv) of Curve448 corresponds to the base point (GX, GY) of Wei448. The inverse mapping maps the affine point (X, Y) of Wei448 to (u, v):=(X - A/3, Y) of Curve448, while mapping the point at infinity of Wei448 to the point at infinity of Curve448. Note that this mapping involves a simple shift of the first coordinate and can - be implemented via integer-only arithmetic as a shift of -(p-A)/3 for - the isomorphic mapping and a shift of (p-A)/3 for its inverse, where - delta=(p-A)/3 is the element of GF(p) defined by + be implemented via integer-only arithmetic as a shift of -delta for + the isomorphic mapping and a shift of delta for its inverse, where + delta:=(p-A)/3 is the integer defined by delta 24227957476520229684977460262933484478454712022910602009383006 63935374427222435908954654612328921819766962948206145457870178326 72736371 (=0x55555555 55555555 55555555 55555555 55555555 55555555 55555554 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffff3473). (Note that, depending on the implementation details of the field @@ -6549,36 +6606,38 @@ retroactively put the ECDSA signature in a form where the y-coordinate of the ephemeral signing key R has a fixed parity. This observation can be used to put ECDSA signatures in a form that generally allows unique and efficient recovery of R from r for prime- order curves (due to NOTE 1 above) and more efficient signature verification methods. Further details are out of scope. Q.3. Representation Examples ECDSA We present some examples of ECDSA computations, when used with curve - Wei25519 and SHA256 (see Appendix Q.3.1), with Wei25519 and SHAKE128 + Wei25519 and SHA-256 (see Appendix Q.3.1), with Wei25519 and SHAKE128 with output size d0=256 (see Appendix Q.3.2), and with Wei448 and SHAKE256 with output size d0=512 (see Appendix Q.3.3). In each case, we indicate the signer's public key Q:=d*G, the ephemeral signing key R:=k*G ,the message m that is signed, and some intermediate values in the ECDSA signing operation resulting in signature (r,s). We write - R:=(xR, yR) and Q:=(xQ, yQ), and include the ascii representation of - message m. Note that the domain parameter n of curve Wei25519 has - bit-length l:=253, whereas the corresponding domain parameter for - Wei448 has bit-length l:=446 (which, in either case, differs from the - digest size of the underlying hash function). For completeness, we - also provide an example of ECDSA computations, when used with NIST - curve P-256 (see [FIPS-186-4]) and hash function SHA256 (see - [FIPS-180-4]), where the domain parameter n of the curve in question - has bit-length l:=256, which is equal to the digest size of the - underlying hash function (see Appendix Q.3.4). + R:=(xR, yR) and Q:=(xQ, yQ), and include the ASCII string + corresponding to message m. Note that the domain parameter n of + curve Wei25519 has bit-length l:=253, whereas the corresponding + domain parameter for Wei448 has bit-length l:=446 (which, in either + case, differs from the digest size of the underlying hash function). + + For completeness, we also provide an example of ECDSA computations, + when used with NIST curve P-256 (see [FIPS-186-4]) and hash function + SHA-256 (see [FIPS-180-4]), where the domain parameter n of the curve + in question has bit-length l:=256, which is equal to the digest size + of the underlying hash function (see Appendix Q.3.4). For details of + the encoding of ASCII strings as bit strings, see Appendix I.4. Q.3.1. Example of ECDSA with Wei25519 and SHA-256 d 47941274660029138864396347947568908774951195017212284524777080461 79444885588 (=0x0a996146 d73d096f 6a606ad8 72e11b12 ce973033 524591c3 ebcc630d b6368854). xQ 34422557393689369648095312405803933433606568476197477554293337733 @@ -6706,69 +6765,65 @@ c8da192d 330c8954). r 99977679631995777258326002355330115438507449798639944497879219280 0526704820 (=0x0235da86 6c184868 db1060f4 c57414ba bb409e23 c6ae150b 5d6b4658 fd8c20b4). 1/k 16237902548817115200666748510759761693156732885271500846541777492 82633956147 - 1/k 16237902548817115200666748510759761693156732885271500846541777492 - 82633956147 - (=0x03970860 022244d0 1cee5f2e 973372d7 2000b51d 2d75731c 0e27428a 7e723b33). m "example ECDSA w/ Wei25519 and SHAKE128" (=0x6578 616d706c 65204543 44534120 772f2057 65693235 35313920 616e6420 5348414b 45313238). - E 52885769330535495835899107243770360963478954388007874330946529931 - 479220563171 + E 37558481186175098606278970911021056916472038320089875122503537502 + 754552388537 - (=0x74ec48e0 d8b9c37c 7ad823b5 e1d9e837 45b4c7c5 d02f2938 - 1f99196f f2052ce3). + (=0x530958d6 432ba571 6a20fd9b d3592234 943da1d6 57f55f07 + 2ab01860 3f9f9bb9). - e 66107211663169369794873884054712951204348692985009842913683162414 - 34902570396 + e 46948101482718873257848713638776321145590047900112343903129421878 + 44319048567 - (=0x0e9d891c 1b17386f 8f5b0476 bc3b3d06 e8b698f8 ba05e527 - 03f3232d fe40a59c). + (=0x0a612b1a c86574ae 2d441fb3 7a6b2446 9287b43a cafeabe0 + e556030c 07f3f377). - s 21018124433820277670749322033999530145769351947494095769585139740 - 41491232262 + s 60979034974035506260645462098255401877898928730177415844489376261 + 15704732698 - (=0x04a5956c 6d03d578 40764c7d 33e8159a 2c875830 0b5a4228 - f585dc0f b8135606). + (=0x0d7b4a83 96b37670 d6ef4ac7 6ce69d43 a65859de 4ecbe649 + f56a7a1f 7fb5bc1a). The ECDSA signature (r,s) can be represented uniquely as the 64-octet string 0x0235da86 6c184868 db1060f4 c57414ba bb409e23 c6ae150b 5d6b4658 fd8c20b4 - 04a5956c 6d03d578 40764c7d 33e8159a 2c875830 0b5a4228 f585dc0f - b8135606, + 0d7b4a83 96b37670 d6ef4ac7 6ce69d43 a65859de 4ecbe649 f56a7a1f + 7fb5bc1a, where this string is the right-concatenation of the integers r and s, each represented as fixed-size octet string in tight MSB/msb-order using the ZnE2OS mapping of Appendix I.6. Since an ECDSA signature (r, s) is valid only if the ECDSA signature (r,-s) is, one can alternatively use the representation - 0x0235da86 6c184868 db1060f4 c57414ba bb409e23 c6ae150b 5d6b4658 fd8c20b4 - 0b5a6a93 92fc2a87 bf89b382 cc17ea65 e857a1ae 979d5aad 628c870a - a4e27de7, + 0284b57c 694c898f 2910b538 931962bc 6e86a000 542bb68c 62a7e8fa + dd4017d3, with the same representation conventions. Q.3.3. Example of ECDSA with Wei448 and SHAKE256 d 83773921833883065724152755040779926324701042667680137762329241115 92597160376444120699241862910141955866217224630560765595890572227 9690 (=0x1d818b12 92af6ef4 3f0ed657 b55d2ab7 a0cd1e64 516414d1 @@ -6828,64 +6883,64 @@ (=0x2f96a107 4a355722 1f20fd90 aed12db3 83b3c32f 593079f4 779e2942 3ad2b5e6 0ea15bdc a57e5827 04ed1f09 e42b8352 68428208 502444de). m "example ECDSA w/ Wei448 and SHAKE256" (=0x6578616d 706c6520 45434453 4120772f 20576569 34343820 616e6420 5348414b 45323536). - E 12090734314062687821830960462859241481351750980975210807010692417 - 87788290188009052883047169049228170145424614719943072950310100584 - 3039685804727137826504734 + E 70518111636481318756745253634149479528712660170653218748970032198 + 09200302878838207999610865248047293428251821985248449616335015355 + 074462070358583196774165 - (=0xe6da473c 90ccc33d 35b6f458 dda7a718 6296d1fc f6ed5139 - 49978903 10c3eb0b 448726c3 470051e9 4562c319 070156c1 36b6818b - eb9b4c18 873fbc40 3b38001e). + (=0x86a488f3 62da4be6 147ef640 34ad43ca 3fde6613 456cc034 + 55555f34 c34778b9 02f05145 62e2113c f4894daf 4446bb10 636b43df + fa5e2434 b1262bee 420fef15). - e 16386000512814751750588212096686160936149469654286309627413103110 - 39082128948717862895885154262738521307509222558257976323832793566 - 29766 + e 95569862294810470138539721873942452276898897320233558414699702549 + 60123138804500061287999759232209252819044656295606728178066107449 + 5757 - (=0x39b691cf 243330cf 4d6dbd16 3769e9c6 18a5b47f 3dbb544e - 5265e240 c430fac2 d121c9b0 d1c0147a 5158b0c6 41c055b0 4dada062 - fae6d306). + (=0x21a9223c d8b692f9 851fbd90 0d2b50f2 8ff79984 d15b300d + 155557cd 30d1de2e 40bc1451 58b8844f 3d22536b d111aec4 18dad0f7 + fe97890d). - s 13548644118210160703789217445495123183108197273149701428544426319 - 69721549289474790694640600902913761876631795267154847305287335592 - 32284 + s 15256839162738057100463520332129958798673106244466764276882516437 + 65316731861037119394561858696609193031230290965981228906529672536 + 92957 - (=0x2fb83e89 3ce77084 18cfff70 d02c01df d4c10a3f 90e0546e - 993d82ba 823b5b5b d9b62b3d 521cdbf5 c6144ade c58d1084 401c1f21 - 45f3971c). + (=0x35bc73be 7e3fd7a1 de9fdb4f be96cbcd 0bb9beec f8286d04 + 026f3440 d6e68e25 9916ea2b c4407e9a 83ecf91a 8473c1a1 cda742d0 + dab5d21d). The ECDSA signature (r,s) can be represented uniquely as the 112-octet string 0x237ff9a3 9734a3dc 9ccf72b7 cb3b8e5e 20d4e1f1 655c973a c72e4aa5 757f4d55 fc1416a3 c77851e9 820a019f 40fdadcf a1f00d1c eb890450 - 2fb83e89 3ce77084 18cfff70 d02c01df d4c10a3f 90e0546e 993d82ba - 823b5b5b d9b62b3d 521cdbf5 c6144ade c58d1084 401c1f21 45f3971c, + 35bc73be 7e3fd7a1 de9fdb4f be96cbcd 0bb9beec f8286d04 026f3440 + d6e68e25 9916ea2b c4407e9a 83ecf91a 8473c1a1 cda742d0 dab5d21d, where this string is the right-concatenation of the integers r and s, each represented as fixed-size octet string in tight MSB/msb-order using the ZnE2OS mapping of Appendix I.6. Since an ECDSA signature (r, s) is valid only if the ECDSA signature (r,-s) is, one can alternatively use the representation 0x237ff9a3 9734a3dc 9ccf72b7 cb3b8e5e 20d4e1f1 655c973a c72e4aa5 757f4d55 fc1416a3 c77851e9 820a019f 40fdadcf a1f00d1c eb890450 - 1047c176 c3188f7b e730008f 2fd3fe20 2b3ef5c0 6f1fab91 66c27d44 - fa8ec88d ea98b00c 5cb95a9a 5b587793 c8387ed0 e35ca371 6564add7, + 0a438c41 81c0285e 216024b0 41693432 f4464113 07d792fb fd90cbbe + a5e395c4 2b37f11d ea95b7f5 9d7fc958 0951cdb3 55d17fc1 d0a272d6, with the same representation conventions. Q.3.4. Example of ECDSA with P-256 and SHA-256 d 64502400493437371358766275827725703314178640739253280897215993954 599262549170 (=0x8e9b109e 719098bf 980487df 1f5d77e9 cb29606e bed2263b 5f57c213 df84f4b2).