idnits 2.17.1 draft-ietf-lwig-curve-representations-09.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 9, 2020) is 1503 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'ECC' is defined on line 942, but no explicit reference was found in the text == Unused Reference: 'SWUmap' is defined on line 987, but no explicit reference was found in the text ** Obsolete normative reference: RFC 8152 (Obsoleted by RFC 9052, RFC 9053) Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 lwig R. Struik 3 Internet-Draft Struik Security Consultancy 4 Intended status: Informational March 9, 2020 5 Expires: September 10, 2020 7 Alternative Elliptic Curve Representations 8 draft-ietf-lwig-curve-representations-09 10 Abstract 12 This document specifies how to represent Montgomery curves and 13 (twisted) Edwards curves as curves in short-Weierstrass form and 14 illustrates how this can be used to carry out elliptic curve 15 computations using existing implementations of, e.g., ECDSA and ECDH 16 using NIST prime curves. We also provide extensive background 17 material that may be useful for implementers of elliptic curve 18 cryptography. 20 Requirements Language 22 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 23 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 24 "OPTIONAL" in this document are to be interpreted as described in BCP 25 14 [RFC2119] [RFC8174] when, and only when, they appear in all 26 capitals, as shown here. 28 Status of This Memo 30 This Internet-Draft is submitted in full conformance with the 31 provisions of BCP 78 and BCP 79. 33 Internet-Drafts are working documents of the Internet Engineering 34 Task Force (IETF). Note that other groups may also distribute 35 working documents as Internet-Drafts. The list of current Internet- 36 Drafts is at https://datatracker.ietf.org/drafts/current/. 38 Internet-Drafts are draft documents valid for a maximum of six months 39 and may be updated, replaced, or obsoleted by other documents at any 40 time. It is inappropriate to use Internet-Drafts as reference 41 material or to cite them other than as "work in progress." 43 This Internet-Draft will expire on September 10, 2020. 45 Copyright Notice 47 Copyright (c) 2020 IETF Trust and the persons identified as the 48 document authors. All rights reserved. 50 This document is subject to BCP 78 and the IETF Trust's Legal 51 Provisions Relating to IETF Documents 52 (https://trustee.ietf.org/license-info) in effect on the date of 53 publication of this document. Please review these documents 54 carefully, as they describe your rights and restrictions with respect 55 to this document. Code Components extracted from this document must 56 include Simplified BSD License text as described in Section 4.e of 57 the Trust Legal Provisions and are provided without warranty as 58 described in the Simplified BSD License. 60 Table of Contents 62 1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 5 63 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 5 64 3. Use of Representation Switches . . . . . . . . . . . . . . . 5 65 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 6 66 4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 6 67 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 7 68 4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 7 69 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 8 70 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 71 5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 9 72 5.2. Representation Conventions . . . . . . . . . . . . . . . 9 73 5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 9 74 6. Implementation Considerations . . . . . . . . . . . . . . . . 10 75 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 11 76 8. Security Considerations . . . . . . . . . . . . . . . . . . . 12 77 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 13 78 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 79 10.1. IANA Considerations for Wei25519 . . . . . . . . . . . . 13 80 10.1.1. COSE Elliptic Curves Registration . . . . . . . . . 14 81 10.1.2. COSE Algorithms Registration (1/2) . . . . . . . . . 14 82 10.1.3. COSE Algorithms Registration (2/2) . . . . . . . . . 14 83 10.1.4. JOSE Elliptic Curves Registration . . . . . . . . . 15 84 10.1.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 15 85 10.1.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 16 86 10.2. IANA Considerations for Wei448 . . . . . . . . . . . . . 16 87 10.2.1. COSE Elliptic Curves Registration . . . . . . . . . 16 88 10.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 17 89 10.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 17 90 10.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 17 91 10.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 18 92 10.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 18 94 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 18 95 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 19 96 12.1. Normative References . . . . . . . . . . . . . . . . . . 19 97 12.2. Informative References . . . . . . . . . . . . . . . . . 20 98 Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 22 99 A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 22 100 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 22 101 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 23 102 Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 23 103 B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 23 104 B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 25 105 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 26 106 C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 26 107 C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 27 108 C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 28 109 Appendix D. Relationship Between Curve Models . . . . . . . . . 29 110 D.1. Mapping between Twisted Edwards Curves and Montgomery 111 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 29 112 D.2. Mapping between Montgomery Curves and Weierstrass Curves 30 113 D.3. Mapping between Twisted Edwards Curves and Weierstrass 114 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 31 115 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 31 116 E.1. Curve Definition and Alternative Representations . . . . 31 117 E.2. Switching between Alternative Representations . . . . . . 31 118 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 33 119 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 35 120 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 35 121 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 36 122 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 36 123 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 37 124 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 39 125 G.1. Further Alternative Representations . . . . . . . . . . . 39 126 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 39 127 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 40 128 G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 41 129 G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 42 130 G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 48 131 Appendix H. Point Compression . . . . . . . . . . . . . . . . . 54 132 H.1. Point Compression for Weierstrass Curves . . . . . . . . 54 133 H.2. Point Compression for Montgomery Curves . . . . . . . . . 55 134 H.3. Point Compression for Twisted Edwards Curves . . . . . . 56 135 Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 57 136 I.1. Conversion between Bit Strings and Integers (BS2I, I2BS) 57 137 I.2. Conversion between Octet Strings and Integers (OS2I, 138 I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 58 139 I.3. Conversion between Octet Strings and Bit Strings (OS2BS, 140 BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 58 141 I.4. Conversion between Field Elements and Octet Strings 142 (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 58 143 I.5. Conversion between Elements of Z mod n and Octet Strings 144 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 59 145 I.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 59 146 Appendix J. Representation Examples Curve25519 Family Members . 61 147 J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 61 148 J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 63 149 J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 65 150 J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 67 151 J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 68 152 Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 70 153 K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 70 154 K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 70 155 K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 70 156 K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 71 157 K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 71 158 K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 71 159 K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 72 160 K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 74 161 K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 74 162 K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 74 163 K.4.2. Mapping to High-Order Points of Montgomery Curve . . 75 164 K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 76 165 K.5. Randomized Representation of Curve Points . . . . . . . . 77 166 Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 78 167 L.1. Curve Definition and Alternative Representation . . . . . 78 168 L.2. Switching Between Representations . . . . . . . . . . . . 79 169 L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 79 170 L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 81 171 L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 81 172 L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 81 173 Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 82 174 M.1. Curve Definition and Alternative Representations . . . . 82 175 M.2. Switching between Alternative Representations . . . . . . 83 176 M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 84 177 Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 87 178 N.1. Further Alternative Representations . . . . . . . . . . . 87 179 N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 87 180 N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 89 181 N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 91 182 N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 92 183 N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 92 184 Appendix O. Representation Examples Curve448 Family Members . . 93 185 O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 93 186 O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 96 187 O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 98 188 O.4. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 101 189 O.5. Example with Edwards448 . . . . . . . . . . . . . . . . . 103 191 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 105 193 1. Fostering Code Reuse with New Elliptic Curves 195 Elliptic curves can be represented using different curve models. 196 Recently, IETF standardized elliptic curves that are claimed to have 197 better performance and improved robustness against "real world" 198 attacks than curves represented in the traditional "short" 199 Weierstrass model. This document specifies an alternative 200 representation of points of Curve25519, a so-called Montgomery curve, 201 and of points of Edwards25519, a so-called twisted Edwards curve, 202 which are both specified in [RFC7748], as points of a specific so- 203 called "short" Weierstrass curve, called Wei25519. We also define 204 how to efficiently switch between these different representations. 206 Use of Wei25519 allows easy definition of new instantiations of 207 signature schemes and key agreement schemes already specified for 208 traditional NIST prime curves, thereby allowing easy integration with 209 existing specifications, such as NIST SP 800-56a [SP-800-56a], FIPS 210 Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005 [ANSI-X9.62], and 211 fostering code reuse on platforms that already implement some of 212 these schemes using elliptic curve arithmetic for curves in "short" 213 Weierstrass form (see Appendix C.1). 215 2. Specification of Wei25519 217 For the specification of Wei25519 and its relationship to Curve25519 218 and Edwards25519, see Appendix E. For further details and background 219 information on elliptic curves, we refer to the other appendices. 221 The use of Wei25519 allows reuse of existing generic code that 222 implements short-Weierstrass curves, such as the NIST curve P-256, to 223 also implement the CFRG curves Curve25519 and Edwards25519. (Here, 224 generic code refers to an implementation that does not depend on 225 hardcoded domain parameters (see also Section 6).) We also cater to 226 reusing of existing code where some domain parameters may have been 227 hardcoded, thereby widening the scope of applicability. To this end, 228 we specify the short-Weierstrass curves Wei25519.2 and Wei25519.-3, 229 with hardcoded domain parameter a=2 and a=-3 (mod p), respectively; 230 see Appendix G. (Here, p is the characteristic of the field over 231 which these curves are defined.) 233 3. Use of Representation Switches 235 The curves Curve25519, Edwards25519, and Wei25519, as specified in 236 Appendix E.3, are all isomorphic, with the transformations of 237 Appendix E.2. These transformations map the specified base point of 238 each of these curves to the specified base point of each of the other 239 curves. Consequently, a public-private key pair (k,R:=k*G) for any 240 one of these curves corresponds, via these isomorphic mappings, to 241 the public-private key pair (k, R':=k*G') for each of these other 242 curves (where G and G' are the corresponding base points of these 243 curves). This observation extends to the case where one also 244 considers curve Wei25519.2 (which has hardcoded domain parameter 245 a=2), as specified in Appendix G.3, since it is isomorphic to 246 Wei25519, with the transformation of Appendix G.2, and, thereby, also 247 isomorphic to Curve25519 and Edwards25519. 249 The curve Wei25519.-3 (which has hardcoded domain parameter a=-3 (mod 250 p)) is not isomorphic to the curve Wei25519, but is related in a 251 slightly weaker sense: the curve Wei25519 is isogenous to the curve 252 Wei25519.-3, where the mapping of Appendix G.2 is an isogeny of 253 degree l=47 that maps the specified base point G of Wei25519 to the 254 specified base point G' of Wei25519.-3 and where the so-called dual 255 isogeny (which maps Wei25519.-3 to Wei25519) has the same degree 256 l=47, but does not map G' to G, but to a fixed multiple hereof, where 257 this multiple is l=47. Consequently, a public-private key pair 258 (k,R:=k*G) for Wei25519 corresponds to the public-private key pair 259 (k, R':= k*G') for Wei25519.-3 (via the l-isogeny), whereas the 260 public-private key pair (k, R':=k*G') corresponds to the public- 261 private key pair (l*k, l*R=l*k*G) of Wei25519 (via the dual isogeny). 262 (Note the extra scalar l=47 here.) 264 Alternative curve representations can, therefore, be used in any 265 cryptographic scheme that involves computations on public-private key 266 pairs, where implementations may carry out computations on the 267 corresponding object for the isomorphic or isogenous curve and 268 convert the results back to the original curve (where, in case this 269 involves an l-isogeny, one has to take into account the factor l). 270 This includes use with elliptic-curve based signature schemes and key 271 agreement and key transport schemes. 273 For some examples of curve computations on each of the curves 274 specified in Appendix E.3 and Appendix G.3, see Appendix J. 276 4. Examples 278 4.1. Implementation of X25519 280 RFC 7748 [RFC7748] specifies the use of X25519, a co-factor Diffie- 281 Hellman key agreement scheme, with instantiation by the Montgomery 282 curve Curve25519. This key agreement scheme was already specified in 283 Section 6.1.2.2 of NIST SP 800-56a [SP-800-56a] for elliptic curves 284 in short Weierstrass form. Hence, one can implement X25519 using 285 existing NIST routines by (1) representing a point of the Montgomery 286 curve Curve25519 as a point of the Weierstrass curve Wei25519; (2) 287 instantiating the co-factor Diffie-Hellman key agreement scheme of 288 the NIST specification with the resulting point and Wei25519 domain 289 parameters; (3) representing the key resulting from this scheme 290 (which is a point of the curve Wei25519 in Weierstrass form) as a 291 point of the Montgomery curve Curve25519. The representation change 292 can be implemented via a simple wrapper and involves a single modular 293 addition (see Appendix E.2). Using this method has the additional 294 advantage that one can reuse the public-private key pair routines, 295 domain parameter validation, and other checks that are already part 296 of the NIST specifications. A NIST-compliant version of co-factor 297 Diffie-Hellman key agreement (denoted by ECDH25519) results if one 298 keeps inputs (key contributions) and outputs (shared key) in the 299 short-Weierstrass format (and, hence, does not perform Step (3) 300 above). 302 NOTE: At this point, it is unclear whether this implies that a FIPS- 303 accredited module implementing co-factor Diffie-Hellman for, e.g., 304 P-256 would also extend this accreditation to X25519. 306 4.2. Implementation of Ed25519 308 RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature 309 scheme, with instantiation by the twisted Edwards curve Edwards25519. 310 One can implement the computation of the ephemeral key pair for 311 Ed25519 using an existing Montgomery curve implementation by (1) 312 generating a public-private key pair (k, R':=k*G') for Curve25519; 313 (2) representing this public-private key as the pair (k, R:=k*G) for 314 Ed25519. As before, the representation change can be implemented via 315 a simple wrapper. Note that the Montgomery ladder specified in 316 Section 5 of RFC7748 [RFC7748] does not provide sufficient 317 information to reconstruct R':=(u, v) (since it does not compute the 318 v-coordinate of R'). However, this deficiency can be remedied by 319 using a slightly modified version of the Montgomery ladder that 320 includes reconstruction of the v-coordinate of R':=k*G' at the end of 321 the Montgomery ladder (which uses the v-coordinate of the base point 322 of Curve25519 as well). For details, see Appendix C.1. 324 4.3. Specification of ECDSA25519 326 FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and 327 can be instantiated not just with the NIST prime curves, but also 328 with other Weierstrass curves (that satisfy additional cryptographic 329 criteria). In particular, one can instantiate this scheme with the 330 Weierstrass curve Wei25519 and the hash function SHA-256 331 [FIPS-180-4], where an implementation may generate an ephemeral 332 public-private key pair for Wei25519 by (1) internally carrying out 333 these computations on the Montgomery curve Curve25519, the twisted 334 Edwards curve Edwards25519, or even the Weierstrass curve Wei25519.-3 335 (with hardcoded a=-3 domain parameter); (2) representing the result 336 as a key pair for the curve Wei25519. Note that, in either case, one 337 can implement these schemes with the same representation conventions 338 as used with existing NIST specifications, including bit/byte- 339 ordering, compression functions, and the-like. This allows generic 340 implementations of ECDSA with the hash function SHA-256 and with the 341 NIST curve P-256 or with the curve Wei25519 specified in this 342 specification to reuse the same implementation (instantiated with, 343 respectively, the NIST P-256 elliptic curve domain parameters or with 344 the domain parameters of curve Wei25519 specified in Appendix E). We 345 denote by ECDSA25519 the instantiation of ECDSA with SHA-256 and with 346 curve Wei25519, where the signature (r,s) is represented as the 347 right-concatenation of the integers r and s, each represented as 348 fixed-size strings with tight MSB/msb ordering (see Appendix I). 350 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) 352 Any existing specification of cryptographic schemes using elliptic 353 curves in Weierstrass form and that allows introduction of a new 354 elliptic curve (here: Wei25519) is amenable to similar constructs, 355 thus spawning "offspring" protocols, simply by instantiating these 356 using the new curve in "short" Weierstrass form, thereby allowing 357 code and/or specifications reuse and, for implementations that so 358 desire, carrying out curve computations "under the hood" on 359 Montgomery curve and twisted Edwards curve cousins hereof (where 360 these exist). This would simply require definition of a new object 361 identifier for any such envisioned "offspring" protocol. This could 362 significantly simplify standardization of schemes and help keeping 363 the resource and maintenance cost of implementations supporting 364 algorithm agility [RFC7696] at bay. 366 We illustrate the construction of such offspring protocols for 367 Curve448, another Montgomery curve recently standardized by IETF (see 368 [RFC7748]). Similar to the case with Curve25519, one can represent 369 points of this curve via different curve models, viz. as points of an 370 Edwards curve (Ed448) or as points of a short-Weierstrass curve 371 (Wei448). For the specification of Wei448 and its relationship to 372 Curve448 and Ed448, see Appendix M. As with ECDH25519, one can now 373 easily define a NIST-compliant version of co-factor Diffie-Hellman 374 key agreement (denoted by ECDH448), by simply reusing the example of 375 Section 4.1, but now using the short-Weierstrass curve Wei448, rather 376 than Wei25519. Similarly, one can easily specify ECDSA with Wei448 377 and a suitable hash function, by simply reusing the example of 378 Section 4.3, but now using the short-Weierstrass curve Wei448, rather 379 than Wei25519, and picking as hash function SHAKE256 [FIPS-202] with 380 output size of d=446 bits. We denote by ECDSA448 the resulting 381 signature scheme (with the same bit/byte-ordering conventions). 383 5. Caveats 385 The examples above illustrate how specifying the Weierstrass curve 386 Wei25519 (or any curve in short-Weierstrass format, for that matter) 387 may facilitate reuse of existing code and may simplify standards 388 development. However, the following caveats apply: 390 5.1. Wire Format 392 The transformations between alternative curve representations can be 393 implemented at negligible relative incremental cost if the curve 394 points are represented as affine points. If a point is represented 395 in compressed format, conversion usually requires a costly point 396 decompression step. This is the case in [RFC7748], where the inputs 397 to the co-factor Diffie-Hellman scheme X25519, as well as its output, 398 are represented in u-coordinate-only format. This is also the case 399 in [RFC8032], where the EdDSA signature includes the ephemeral 400 signing key represented in compressed format (see Appendix H for 401 details). Note that in the latter case compression is lossless, 402 whereas it is lossy in the former case; 404 5.2. Representation Conventions 406 While elliptic curve computations are carried-out in a field GF(q) 407 and, thereby, involve large integer arithmetic, these integers are 408 represented as bit- and byte-strings. Here, [RFC8032] uses least- 409 significant-byte (LSB)/least-significant-bit (lsb) conventions, 410 whereas [RFC7748] uses LSB/most-significant-bit (msb) conventions, 411 and where most other cryptographic specifications, including NIST 412 SP800-56a [SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI 413 X9.62-2005 [ANSI-X9.62] use MSB/msb conventions. Since each pair of 414 conventions is different (see Appendix I for details and Appendix J 415 for examples), this does necessitate bit/byte representation 416 conversions; 418 5.3. Domain Parameters 420 All traditional NIST curves are Weierstrass curves with domain 421 parameter a=-3, while all Brainpool curves [RFC5639] are isomorphic 422 to a Weierstrass curve of this form. Thus, one can expect there to 423 be existing Weierstrass implementations with a hardcoded a=-3 domain 424 parameter ("Jacobian-friendly"). For those implementations, 425 including the curve Wei25519 as a potential vehicle for offering 426 support for the CFRG curves Curve25519 and Edwards25519 is not 427 possible, since not of the required form. Instead, one has to 428 implement Wei25519.-3 and include code that implements the isogeny 429 and dual isogeny from and to Wei25519. The lowest odd-degree isogeny 430 has degree l=47 and requires roughly 9kB of storage for isogeny and 431 dual-isogeny computations (see the tables in Appendix G.4). Note 432 that storage would have reduced to a single 64-byte table if only the 433 curve would have been generated so as to be isomorphic to a 434 Weierstrass curve with hardcoded a=-3 parameter (this corresponds to 435 l=1). 437 NOTE 1: An example of a Montgomery curve defined over the same field 438 as Curve25519 that is isomorphic to a Weierstrass curve with 439 hardcoded a=-3 parameter is the Montgomery curve M_{A,B} with B=1 and 440 A=-1410290 (or, if one wants the base point to still have 441 u-coordinate u=9, with B=1 and A=-3960846). In either case, the 442 resulting curve has the same cryptographic properties as Curve25519 443 and the same performance (which relies on A being a 3-byte integer, 444 as is the case with the domain parameter A=486662 of Curve25519, and 445 using the same special prime p=2^255-19), while at the same time 446 being "Jacobian-friendly" by design. 448 NOTE 2: While an implementation of Curve25519 via an isogenous 449 Weierstrass curve with domain parameter a=-3 requires a relatively 450 large table (of size roughly 9kB), for the quadratic twist of 451 Curve25519 (i.e., the Montgomery curve M_{A,B'} with A=486662 and 452 B'=2) this implementation approach only requires a table of size less 453 than 0.5kB (over 20x smaller), solely due to the fact that it is 454 l-isogenous to a Weierstrass curve with a=-3 parameter with 455 relatively small parameter l=2 (compared to l=47, as is the case with 456 Curve25519 itself). 458 6. Implementation Considerations 460 The efficiency of elliptic curve arithmetic is primarily determined 461 by the efficiency of its group operations (see Appendix C). Numerous 462 optimized formulae exist, such as the use of so-called Montgomery 463 ladders with Montgomery curves [Mont-Ladder] or with Weierstrass 464 curves [Wei-Ladder], the use of hardcoded a=-3 domain parameter for 465 Weierstrass curves [ECC-Isogeny], and the use of hardcoded a=-1 466 domain parameters for twisted Edwards curves [tEd-Formulas]. These 467 all target reduction of the number of finite field operations 468 (primarily, finite field multiplications and squarings). Other 469 optimizations target more efficient modular reductions underlying 470 these finite field operations, by specifying curves defined over a 471 field GF(q), where the field size q has a special form or a specific 472 bit-size (typically, close to a multiple of a machine word). 473 Depending on the implementation strategy, the bit-size of q may also 474 facilitate reduced so-called "carry-effects" of integer arithmetic. 476 Most curves use a combination of these design philosophies. All NIST 477 curves [FIPS-186-4] and Brainpool curves [RFC5639] are Weierstrass 478 curves with a=-3 domain parameter, thus facilitating more efficient 479 elliptic curve group operations (via so-called Jacobian coordinates). 480 The NIST curves and the Montgomery curve Curve25519 are defined over 481 prime fields, where the prime number has a special form, whereas the 482 Brainpool curves - by design - use a generic prime number. None of 483 the NIST prime curves, nor the Brainpool curves, can be expressed as 484 Montgomery or twisted Edwards curves, whereas - conversely - 485 Montgomery curves and twisted curves can be expressed as Weierstrass 486 curves. 488 While use of Wei25519 allows reuse of existing generic code that 489 implements short Weierstrass curves, such as the NIST curve P-256, to 490 also implement the CFRG curves Curve25519 or Edwards25519, this 491 obviously does not result in an implementation of these CFRG curves 492 that exploits the specific structure of the underlying field or other 493 specific domain parameters (since generic). Reuse of generic code, 494 therefore, may result in a less computationally efficient curve 495 implementation than would have been possible if the implementation 496 had specifically targeted Curve25519 or Edwards25519 alone (with the 497 overall cost differential estimated to be somewhere in the interval 498 [1.00-1.25]). If existing generic code offers hardware support, 499 however, the overall speed may still be larger, since less efficient 500 formulae for curve arithmetic using Wei25519 curves compared to a 501 direct implementation of Curve25519 or Edwards25519 arithmetic may be 502 more than compensated for by faster implementations of the finite 503 field arithmetic itself. 505 Overall, one should consider not just code reuse and computational 506 efficiency, but also development and maintenance cost, and, e.g, the 507 cost of providing effective implementation attack countermeasures 508 (see also Section 8). 510 7. Implementation Status 512 [Note to the RFC Editor] Please remove this entire section before 513 publication, as well as the reference to [RFC7942]. 515 This section records the status of known implementations of the 516 protocol defined by this specification at the time of posting of this 517 Internet-Draft, and is based on a proposal described in [RFC7942]. 518 The description of implementations in this section is intended to 519 assist the IETF in its decision processes in progressing drafts to 520 RFCs. Please note that the listing of any individual implementation 521 here does not imply endorsement by the IETF. Furthermore, no effort 522 has been spent to verify the information presented here that was 523 supplied by IETF contributors. This is not intended as, and must not 524 be construed to be, a catalog of available implementations or their 525 features. Readers are advised to note that other implementations may 526 exist. 528 According to [RFC7942], "this will allow reviewers and working groups 529 to assign due consideration to documents that have the benefit of 530 running code, which may serve as evidence of valuable experimentation 531 and feedback that have made the implemented protocols more mature. 532 It is up to the individual working groups to use this information as 533 they see fit. 535 Nikolas Rosener evaluated the performance of switching between 536 different curve models in his Master's thesis [Rosener]. For an 537 implementation of Wei25519, see . 538 For support of this curve in tinydtls, see . 541 According to , an 542 implementation of Wei25519 on the Kinets LTC ECC HW platform improves 543 the performance by over a factor ten compared to a stand-alone 544 implementation of Curve25519 without hardware support. 546 The signature scheme ECDSA25519 (see Section 4.3) is supported in 547 . 549 8. Security Considerations 551 The different representations of elliptic curve points discussed in 552 this document are all obtained using a publicly known transformation, 553 which is either an isomorphism or a low-degree isogeny. It is well- 554 known that an isomorphism maps elliptic curve points to equivalent 555 mathematical objects and that the complexity of cryptographic 556 problems (such as the discrete logarithm problem) of curves related 557 via a low-degree isogeny are tightly related. Thus, the use of these 558 techniques does not negatively impact cryptographic security of 559 elliptic curve operations. 561 As to implementation security, reusing existing high-quality code or 562 generic implementations that have been carefully designed to 563 withstand implementation attacks for one curve model may allow a more 564 economical way of development and maintenance than providing this 565 same functionality for each curve model separately (if multiple curve 566 models need to be supported) and, otherwise, may allow a more gradual 567 migration path, where one may initially use existing and accredited 568 chipsets that cater to the pre-dominant curve model used in practice 569 for over 15 years. 571 Elliptic curves are generally used as objects in a broader 572 cryptographic scheme that may include processing steps that depend on 573 the representation conventions used (such as with, e.g., key 574 derivation following key establishment). These schemes should 575 (obviously) unambiguously specify fixed representations of each input 576 and output (e.g., representing each elliptic curve point always in 577 short-Weierstrass form and in uncompressed tight MSB/msb format). 579 To prevent cross-protocol attacks, private keys SHOULD only be used 580 with one cryptographic scheme. Private keys MUST NOT be reused 581 between Ed25519 (as specified in [RFC8032]) and ECDSA25519 (as 582 specified in Section 4.3). 584 To prevent intra-protocol cross-instantiation attacks, ephemeral 585 private keys MUST NOT be reused between instantiations of ECDSA25519. 587 9. Privacy Considerations 589 The transformations between different curve models described in this 590 document are publicly known and, therefore, do not affect privacy 591 provisions. 593 Use of a public key in any protocol for which successful execution 594 evidences knowledge of the corresponding private key implicitly 595 indicates the entity holding this private key. Reuse of this public 596 key with more than one protocol or more than one protocol 597 instantiation may, therefore, allow traceability of this entity. It 598 may also allow correlation of meta-data communicated with this common 599 data element (e.g., different addressing information), even if an 600 observer cannot technically verify the binding of this meta-data. 602 The randomized representation described in Appendix K.5 allows random 603 curve points to be represented as random pairs of field elements, 604 thereby assisting in obfuscating the presence of these curve points 605 in some applications. 607 10. IANA Considerations 609 Code points are requested for curve Wei25519 and Wei448 and its use 610 with ECDSA and co-factor ECDH, using the representation conventions 611 of this document. 613 New code points would be required in case one wishes to specify one 614 or more other "offspring" protocols beyond those exemplified in 615 Section 4.4. Specification hereof is, however, outside scope of the 616 current document. 618 10.1. IANA Considerations for Wei25519 619 10.1.1. COSE Elliptic Curves Registration 621 This section registers the following value in the IANA "COSE Elliptic 622 Curves" registry [IANA.COSE.Curves]. 624 Name: Wei25519; 626 Value: TBD (Requested value: -1); 628 Key Type: EC2 or OKP (where OKP uses the squeezed MSB/msb 629 representation of this specification); 631 Description: short-Weierstrass curve Wei25519; 633 Change Controller: IESG; 635 Reference: Appendix E.3 of this specification; 637 Recommended: Yes. 639 (Note that The "kty" value for Wei25519 may be "OKP" or "EC2".) 641 10.1.2. COSE Algorithms Registration (1/2) 643 This section registers the following value in the IANA "COSE 644 Algorithms" registry [IANA.COSE.Algorithms]. 646 Name: ECDSA25519; 648 Value: TBD (Requested value: -1); 650 Description: ECDSA with SHA-256 and curve Wei25519; 652 Change Controller: IESG; 654 Reference: Section 4.3 of this specification; 656 Recommended: Yes. 658 10.1.3. COSE Algorithms Registration (2/2) 660 This section registers the following value in the IANA "COSE 661 Algorithms" registry [IANA.COSE.Algorithms]. 663 Name: ECDH25519; 665 Value: TBD (Requested value: -2); 666 Description: NIST-compliant co-factor Diffie-Hellman w/ curve 667 Wei25519 and key derivation function HKDF SHA256; 669 Change Controller: IESG; 671 Reference: Section 4.1 of this specification (for key derivation, 672 see Section 11.1 of [RFC8152]); 674 Recommended: Yes. 676 10.1.4. JOSE Elliptic Curves Registration 678 This section registers the following value in the IANA "JSON Web Key 679 Elliptic Curve" registry [IANA.JOSE.Curves]. 681 Curve Name: Wei25519; 683 Curve Description: short-Weierstrass curve Wei25519; 685 JOSE Implementation Requirements: Optional; 687 Change Controller: IESG; 689 Reference: Appendix E.3 of this specification. 691 10.1.5. JOSE Algorithms Registration (1/2) 693 This section registers the following value in the IANA "JSON Web 694 Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. 696 Algorithm Name: ECDSA25519; 698 Algorithm Description: ECDSA using SHA-256 and curve Wei25519; 700 Algorithm Usage Locations: alg; 702 JOSE Implementation Requirements: Optional; 704 Change Controller: IESG; 706 Reference: Section 4.3 of this specification; 708 Algorithm Analysis Document(s): Section 4.3 of this specification. 710 10.1.6. JOSE Algorithms Registration (2/2) 712 This section registers the following value in the IANA "JSON Web 713 Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. 715 Algorithm Name: ECDH25519; 717 Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/ 718 curve Wei25519 and key derivation function HKDF SHA256; 720 Algorithm Usage Locations: alg; 722 JOSE Implementation Requirements: Optional; 724 Change Controller: IESG; 726 Reference: Section 4.1 of this specification (for key derivation, 727 see Section 5 of [SP-800-56c]); 729 Algorithm Analysis Document(s): Section 4.1 of this specification 730 (for key derivation, see Section 5 of [SP-800-56c]). 732 10.2. IANA Considerations for Wei448 734 10.2.1. COSE Elliptic Curves Registration 736 This section registers the following value in the IANA "COSE Elliptic 737 Curves" registry [IANA.COSE.Curves]. 739 Name: Wei448; 741 Value: TBD (Requested value: -2); 743 Key Type: EC2 or OKP (where OKP uses the squeezed MSB/msb 744 representation of this specification); 746 Description: short-Weierstrass curve Wei448; 748 Change Controller: IESG; 750 Reference: Appendix M.3 of this specification; 752 Recommended: Yes. 754 (Note that The "kty" value for Wei448 may be "OKP" or "EC2".) 756 10.2.2. COSE Algorithms Registration (1/2) 758 This section registers the following value in the IANA "COSE 759 Algorithms" registry [IANA.COSE.Algorithms]. 761 Name: ECDSA448; 763 Value: TBD (Requested value: -21); 765 Description: ECDSA with SHAKE256 and curve Wei448; 767 Change Controller: IESG; 769 Reference: Section 4.4 of this specification; 771 Recommended: Yes. 773 10.2.3. COSE Algorithms Registration (2/2) 775 This section registers the following value in the IANA "COSE 776 Algorithms" registry [IANA.COSE.Algorithms]. 778 Name: ECDH448; 780 Value: TBD (Requested value: -22); 782 Description: NIST-compliant co-factor Diffie-Hellman w/ curve 783 Wei25519 and key derivation function HKDF SHA512; 785 Change Controller: IESG; 787 Reference: Section 4.4 of this specification (for key derivation, 788 see Section 11.1 of [RFC8152]); 790 Recommended: Yes. 792 10.2.4. JOSE Elliptic Curves Registration 794 This section registers the following value in the IANA "JSON Web Key 795 Elliptic Curve" registry [IANA.JOSE.Curves]. 797 Curve Name: Wei448; 799 Curve Description: short-Weierstrass curve Wei448; 801 JOSE Implementation Requirements: Optional; 803 Change Controller: IESG; 804 Reference: Appendix M.3 of this specification. 806 10.2.5. JOSE Algorithms Registration (1/2) 808 This section registers the following value in the IANA "JSON Web 809 Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. 811 Algorithm Name: ECDSA448; 813 Algorithm Description: ECDSA using SHAKE256 and curve Wei448; 815 Algorithm Usage Locations: alg; 817 JOSE Implementation Requirements: Optional; 819 Change Controller: IESG; 821 Reference: Section 4.4 of this specification; 823 Algorithm Analysis Document(s): Section 4.4 of this specification. 825 10.2.6. JOSE Algorithms Registration (2/2) 827 This section registers the following value in the IANA "JSON Web 828 Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. 830 Algorithm Name: ECDH448; 832 Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/ 833 curve Wei25519 and key derivation function HKDF SHA512; 835 Algorithm Usage Locations: alg; 837 JOSE Implementation Requirements: Optional; 839 Change Controller: IESG; 841 Reference: Section 4.4 of this specification (for key derivation, 842 see Section 5 of [SP-800-56c]); 844 Algorithm Analysis Document(s): Section 4.4 of this specification 845 (for key derivation, see Section 5 of [SP-800-56c]). 847 11. Acknowledgements 849 Thanks to Nikolas Rosener for discussions surrounding implementation 850 details of the techniques described in this document and to Phillip 851 Hallam-Baker for triggering inclusion of verbiage on the use of 852 Montgomery ladders with recovery of the y-coordinate. Thanks to 853 Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews. 855 12. References 857 12.1. Normative References 859 [ANSI-X9.62] 860 ANSI X9.62-2005, "Public Key Cryptography for the 861 Financial Services Industry: The Elliptic Curve Digital 862 Signature Algorithm (ECDSA)", American National Standard 863 for Financial Services, Accredited Standards Committee X9, 864 Inc, Anapolis, MD, 2005. 866 [FIPS-180-4] 867 FIPS 180-4, "Secure Hash Standard (SHS), Federal 868 Information Processing Standards Publication 180-4", US 869 Department of Commerce/National Institute of Standards and 870 Technology, Gaithersburg, MD, August 2015. 872 [FIPS-186-4] 873 FIPS 186-4, "Digital Signature Standard (DSS), Federal 874 Information Processing Standards Publication 186-4", US 875 Department of Commerce/National Institute of Standards and 876 Technology, Gaithersburg, MD, July 2013. 878 [FIPS-202] 879 FIPS 202, "SHA-3 Standard: Permutation-Based Hash and 880 Extendable-Output Functions, Federal Information 881 Processing Standards Publication 202", US Department of 882 Commerce/National Institute of Standards and 883 Technology, Gaithersburg, MD, August 2015. 885 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 886 Requirement Levels", BCP 14, RFC 2119, 887 DOI 10.17487/RFC2119, March 1997, 888 . 890 [RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography 891 (ECC) Brainpool Standard Curves and Curve Generation", 892 RFC 5639, DOI 10.17487/RFC5639, March 2010, 893 . 895 [RFC7696] Housley, R., "Guidelines for Cryptographic Algorithm 896 Agility and Selecting Mandatory-to-Implement Algorithms", 897 BCP 201, RFC 7696, DOI 10.17487/RFC7696, November 2015, 898 . 900 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 901 for Security", RFC 7748, DOI 10.17487/RFC7748, January 902 2016, . 904 [RFC7942] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 905 Code: The Implementation Status Section", BCP 205, 906 RFC 7942, DOI 10.17487/RFC7942, July 2016, 907 . 909 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 910 Signature Algorithm (EdDSA)", RFC 8032, 911 DOI 10.17487/RFC8032, January 2017, 912 . 914 [RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)", 915 RFC 8152, DOI 10.17487/RFC8152, July 2017, 916 . 918 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 919 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 920 May 2017, . 922 [SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0", 923 Standards for Efficient Cryptography, , June 2009. 925 [SEC2] SEC2, "SEC 2: Elliptic Curve Cryptography, Version 2.0", 926 Standards for Efficient Cryptography, , January 2010. 928 [SP-800-56a] 929 NIST SP 800-56a, "Recommendation for Pair-Wise Key 930 Establishment Schemes Using Discrete Log Cryptography, 931 Revision 3", US Department of Commerce/National Institute 932 of Standards and Technology, Gaithersburg, MD, April 2018. 934 [SP-800-56c] 935 NIST SP 800-56c, "Recommendation for Key-Derivation 936 Methods in Key-Establishment Schemes, Revision 1", US 937 Department of Commerce/National Institute of Standards and 938 Technology, Gaithersburg, MD, April 2018. 940 12.2. Informative References 942 [ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in 943 Cryptography", Cambridge University Press, Lecture Notes 944 Series 265, July 1999. 946 [ECC-Isogeny] 947 E. Brier, M. Joye, "Fast Point Multiplication on Elliptic 948 Curves through Isogenies", AAECC, Lecture Notes in 949 Computer Science, Vol. 2643, New York: Springer-Verlag, 950 2003. 952 [GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to 953 Elliptic Curve Cryptography", New York: Springer-Verlag, 954 2004. 956 [IANA.COSE.Algorithms] 957 IANA, "COSE Algorithms", IANA, 958 https://www.iana.org/assignments/cose/ 959 cose.xhtml#algorithms. 961 [IANA.COSE.Curves] 962 IANA, "COSE Elliptic Curves", IANA, 963 https://www.iana.org/assignments/cose/cose.xhtml#elliptic- 964 curves. 966 [IANA.JOSE.Algorithms] 967 IANA, "JSON Web Signature and Encryption Algorithms", 968 IANA, 969 https://www.iana.org/assignments/jose/jose.xhtml#web- 970 signature-encryption-algorithms. 972 [IANA.JOSE.Curves] 973 IANA, "JSON Web Key Elliptic Curve", IANA, 974 https://www.iana.org/assignments/jose/jose.xhtml#web-key- 975 elliptic-curve. 977 [Mont-Ladder] 978 P.L. Montgomery, "Speeding the Pollard and Elliptic Curve 979 Methods of Factorization", Mathematics of 980 Computation, Vol. 48, 1987. 982 [Rosener] N. Rosener, "Evaluating the Performance of Transformations 983 Between Curve Representations in Elliptic Curve 984 Cryptography for Constrained Device Security", 985 M.Sc. Universitat Bremen, August 2018. 987 [SWUmap] E. Brier, J-S. Coron, Th. Icart, D. Madore, H. Randriam, 988 M. Tibouchi, "Efficient Indifferentiable Hashing into 989 Ordinary Elliptic Curves", CRYPTO 2010, Lecture Notes in 990 Computer Science, Vol. 6223, New York: Springer-Verlag, 991 2010. 993 [tEd] D.J. Bernstein, P. Birkner, M. Joye, T. Lange, C. Peters, 994 "Twisted Edwards Curves", Africacrypt 2008, Lecture Notes 995 in Computer Science, Vol. 5023, New York: Springer-Verlag, 996 2008. 998 [tEd-Formulas] 999 H. Hisil, K.K.H. Wong, G. Carter, E. Dawson, "Twisted 1000 Edwards Curves Revisited", ASIACRYPT 2008, Lecture Notes 1001 in Computer Science, Vol. 5350, New York: Springer-Verlag, 1002 2008. 1004 [Tibouchi] 1005 M. Tibouchi, "Elligator Squared -- Uniform Points on 1006 Elliptic Curves of Prime Order as Uniform Random Strings", 1007 Financial Cryptography 2014, Lecture Notes in Computer 1008 Science, Vol. 8437, New York: Springer-Verlag, 2014. 1010 [Wei-Ladder] 1011 T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve 1012 Multiplication Resistant Against Side Channel Attacks", 1013 Centre for Applied Cryptographic Research, Corr 2002-03, 1014 2002. 1016 Appendix A. Some (Non-Binary) Elliptic Curves 1018 This section defines the three different curve models we consider, 1019 viz. short-Weierstrass curves, Montgomery curves, and twisted Edwards 1020 curves. 1022 A.1. Curves in Short-Weierstrass Form 1024 Let GF(q) denote the finite field with q elements, where q is an odd 1025 prime power and where q is not divisible by three. Let W_{a,b} be 1026 the Weierstrass curve with defining equation Y^2 = X^3 + a*X + b, 1027 where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is 1028 nonzero. The points of W_{a,b} are the ordered pairs (X, Y) whose 1029 coordinates are elements of GF(q) and that satisfy the defining 1030 equation (the so-called affine points), together with the special 1031 point O (the so-called "point at infinity"). This set forms a group 1032 under addition, via the so-called "chord-and-tangent" rule, where the 1033 point at infinity serves as the identity element. See Appendix C.1 1034 for details of the group operation. 1036 A.2. Montgomery Curves 1038 Let GF(q) denote the finite field with q elements, where q is an odd 1039 prime power. Let M_{A,B} be the Montgomery curve with defining 1040 equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q) 1041 and where A is unequal to (+/-)2 and where B is nonzero. The points 1042 of M_{A,B} are the ordered pairs (u, v) whose coordinates are 1043 elements of GF(q) and that satisfy the defining equation (the so- 1044 called affine points), together with the special point O (the so- 1045 called "point at infinity"). This set forms a group under addition, 1046 via the so-called "chord-and-tangent" rule, where the point at 1047 infinity serves as the identity element. See Appendix C.2 for 1048 details of the group operation. 1050 A.3. Twisted Edwards Curves 1052 Let GF(q) denote the finite field with q elements, where q is an odd 1053 prime power. Let E_{a,d} be the twisted Edwards curve with defining 1054 equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct 1055 nonzero elements of GF(q). The points of E_{a,d} are the ordered 1056 pairs (x, y) whose coordinates are elements of GF(q) and that satisfy 1057 the defining equation (the so-called affine points). It can be shown 1058 that this set forms a group under addition if a is a square in GF(q), 1059 whereas d is not, where the point O:=(0, 1) serves as the identity 1060 element. (Note that the identity element satisfies the defining 1061 equation.) See Appendix C.3 for details of the group operation. 1063 An Edwards curve is a twisted Edwards curve with a=1. 1065 Appendix B. Elliptic Curve Nomenclature and Finite Fields 1067 This section provides brief background information on elliptic curves 1068 and finite fields that should be sufficient to understand 1069 constructions and examples in this document. 1071 B.1. Elliptic Curve Nomenclature 1073 Each curve defined in Appendix A forms a commutative group under 1074 addition (denoted by '+'). In Appendix C we specify the group laws, 1075 which depend on the curve model in question. For completeness, we 1076 here include some common elliptic curve nomenclature and basic 1077 properties (primarily so as to keep this document self-contained). 1078 These notions are mainly used in Appendix E and Appendix G and not 1079 essential for our exposition. This section can be skipped at first 1080 reading. 1082 Any point P of a curve E is a generator of the cyclic subgroup 1083 (P):={k*P | k = 0, 1, 2,...} of the curve. (Here, k*P denotes the 1084 sum of k copies of P, where 0*P is the identity element O of the 1085 curve; k*P is commonly referred to as scalar multiplication of P by 1086 k.) If (P) has cardinality l, then l is called the order of P. The 1087 order of curve E is the cardinality of the set of its points, 1088 commonly denoted by |E|. A curve is cyclic if it is generated by some 1089 point of this curve. All curves of prime order are cyclic, while all 1090 curves of order h*n, where n is a large prime number and where h is a 1091 small number (the so-called co-factor), have a large cyclic subgroup 1092 of prime order n. In this case, a generator of order n is called a 1093 base point, commonly denoted by G. A point of order dividing h is 1094 said to be in the small subgroup. For curves of prime order, this 1095 small subgroup is the singleton set, consisting of only the identity 1096 element O. A point that is not in the small subgroup is said to be a 1097 high-order point (since it has order at least n). 1099 If R is a point of the curve that is also contained in (P), there is 1100 a unique integer k in the interval [0, l-1] so that R=k*P, where l is 1101 the order of P. This number is called the discrete logarithm of R to 1102 the base P. The discrete logarithm problem is the problem of finding 1103 the discrete logarithm of R to the base P for any two points P and R 1104 of the curve, if such a number exists. 1106 If P is a fixed base point G of the curve, the pair (k, R:=k*G) is 1107 commonly called a public-private key pair, the integer k the private 1108 key, and the point R the corresponding public key. The private key k 1109 can be represented as an integer in the interval [0,n-1], where G has 1110 order n. If this representation is nonzero, R has order n; 1111 otherwise, it has order one and is the identity element O of the 1112 curve. 1114 In this document, a quadratic twist of a curve E defined over a field 1115 GF(q) is a curve E' related to E, with cardinality |E'|, 1116 where |E|+|E'|=2*(q+1). If E is a curve in one of the curve models 1117 specified in this document, a quadratic twist of this curve can be 1118 expressed using the same curve model, although (naturally) with its 1119 own curve parameters. Two curves E and E' defined over a field GF(q) 1120 are said to be isogenous if these have the same order and are said to 1121 be isomorphic if these have the same group structure. Note that 1122 isomorphic curves have necessarily the same order and are, thus, a 1123 special type of isogenous curves. Further details are out of scope. 1125 Weierstrass curves can have prime order, whereas Montgomery curves 1126 and twisted Edwards curves always have an order that is a multiple of 1127 four (and, thereby, a small subgroup of cardinality four). 1129 An ordered pair (x, y) whose coordinates are elements of GF(q) can be 1130 associated with any ordered triple of the form [x*z: y*z: z], where z 1131 is a nonzero element of GF(q), and can be uniquely recovered from 1132 such a representation. The latter representation is commonly called 1133 a representation in projective coordinates. Sometimes, yet other 1134 representations are useful (e.g., representation in Jacobian 1135 coordinates). Further details are out of scope. 1137 The group laws in Appendix C are mostly expressed in terms of affine 1138 points, but can also be expressed in terms of the representation of 1139 these points in projective coordinates, thereby allowing clearing of 1140 denominators. The group laws may also involve non-affine points 1141 (such as the point at infinity O of a Weierstrass curve or of a 1142 Montgomery curve). Those can also be represented in projective 1143 coordinates. Further details are out of scope. 1145 B.2. Finite Fields 1147 The field GF(q), where q is a prime power, is defined as follows. 1149 If q:=p is a prime number, the field GF(p) consists of the integers 1150 in the interval [0,p-1] and two binary operations on this set: 1151 addition and multiplication modulo p. This field is commonly called 1152 a prime field. 1154 If q:=p^m, where p is a prime number and where m>0, the field GF(q) 1155 is defined in terms of an irreducible polynomial f(z) in z of degree 1156 m with coefficients in GF(p) (i.e., f(z) cannot be written as the 1157 product of two polynomials in z of lower degree with coefficients in 1158 GF(p)): in this case, GF(q) consists of the polynomials in z of 1159 degree smaller than m with coefficients in GF(p) and two binary 1160 operations on this set: polynomial addition and polynomial 1161 multiplication modulo the irreducible polynomial f(z). By 1162 definition, each element x of GF(q) is a polynomial in z of degree 1163 smaller than m and can, therefore, be uniquely represented as a 1164 vector (x_{m-1}, x_{m-2}, ..., x_1, x_0) of length m with 1165 coefficients in GF(p), where x_i is the coefficient of z^i of 1166 polynomial x. Note that this representation depends on the 1167 irreducible polynomial f(z) of the field GF(p^m) in question (which 1168 is often fixed in practice). Note that GF(q) contains the prime 1169 field GF(p) as a subset. If m=1, the definitions of GF(p) and 1170 GF(p^1) above coincide, since each nonzero element of GF(p) can be 1171 viewed as a polynomial in z of degree zero. If m>1, then GF(q) is 1172 called a (nontrivial) extension field of GF(p). The number p is 1173 called the characteristic of GF(q). 1175 A field element y is called a square in GF(q) if it can be expressed 1176 as y:=x^2 for some x in GF(q); it is called a non-square in GF(q) 1177 otherwise. If y is a square in GF(q), we denote by sqrt(y) one of 1178 its square roots (the other one being -sqrt(y)). For methods for 1179 computing square roots and inverses in GF(q) - if these exist - see 1180 Appendix K.1 and Appendix K.2, respectively. For methods for mapping 1181 a nonzero field element that is not a square in GF(q) to a point of a 1182 curve, see Appendix K.3. 1184 NOTE: The curves in Appendix E and Appendix G are all defined over a 1185 prime field GF(p), thereby reducing all operations to simple modular 1186 integer arithmetic. Strictly speaking we could, therefore, have 1187 refrained from introducing extension fields. Nevertheless, we 1188 included the more general exposition, so as to accommodate potential 1189 introduction of new curves that are defined over a (nontrivial) 1190 extension field at some point in the future. This includes curves 1191 proposed for post-quantum isogeny-based schemes, which are defined 1192 over a quadratic extension field (i.e., where q:=p^2), and elliptic 1193 curves used with pairing-based cryptography. The exposition in 1194 either case is almost the same and now automatically yields, e.g., 1195 data conversion routines for any finite field object (see 1196 Appendix I). Readers not interested in this, could simply view all 1197 fields as prime fields. 1199 Appendix C. Elliptic Curve Group Operations 1201 This section specifies group operations for elliptic curves in short- 1202 Weierstrass form, for Montgomery curves, and for twisted Edwards 1203 curves. 1205 C.1. Group Laws for Weierstrass Curves 1207 For each point P of the Weierstrass curve W_{a,b}, the point at 1208 infinity O serves as identity element, i.e., P + O = O + P = P. 1210 For each affine point P:=(X, Y) of the Weierstrass curve W_{a,b}, the 1211 point -P is the point (X, -Y) and one has P + (-P) = O (i.e., -P is 1212 the inverse of P). For the point at infinity O, one has -O:=O. 1214 Let P1:=(X1, Y1) and P2:=(X2, Y2) be distinct affine points of the 1215 Weierstrass curve W_{a,b} and let Q:=P1 + P2, where Q is not the 1216 identity element. Then Q:=(X, Y), where 1218 X + X1 + X2 = lambda^2 and Y + Y1 = lambda*(X1 - X), where 1220 lambda:= (Y2 - Y1)/(X2 - X1). 1222 Let P:=(X1, Y1) be an affine point of the Weierstrass curve W_{a,b} 1223 and let Q:=2*P, where Q is not the identity element. Then Q:=(X, Y), 1224 where 1226 X + 2*X1 = lambda^2 and Y + Y1 = lambda*(X1 - X), where 1228 lambda:=(3*X1^2 + a)/(2*Y1). 1230 From the group laws above it follows that if P=(X, Y), P1=(X1, Y1), 1231 and P2=(X2, Y2) are distinct affine points of the Weierstrass curve 1232 W_{a,b} with P2:=P+P1 and if Y is nonzero, then the Y-coordinate of 1233 P1 can be expressed in terms of the X-coordinates of P, P1, and P2, 1234 and the Y-coordinate of P, since 1236 2*Y*Y1=(X*X1+a)*(X+X1)+2*b-X2*(X-X1)^2. 1238 This property allows recovery of the Y-coordinate of a point P1=k*P 1239 that is computed via the so-called Montgomery ladder, where P is an 1240 affine point with nonzero Y-coordinate (i.e., it does not have order 1241 two). For future reference, note that the expression above uniquely 1242 determines the X-coordinate of P2 in terms of the X-coordinates of P 1243 and P1 and the product of their Y-coordinates. Further details are 1244 out of scope. 1246 C.2. Group Laws for Montgomery Curves 1248 For each point P of the Montgomery curve M_{A,B}, the point at 1249 infinity O serves as identity element, i.e., P + O = O + P = P. 1251 For each affine point P:=(u, v) of the Montgomery curve M_{A,B}, the 1252 point -P is the point (u, -v) and one has P + (-P) = O (i.e., -P is 1253 the inverse of P). For the point at infinity O, one has -O:=O. 1255 Let P1:=(u1, v1) and P2:=(u2, v2) be distinct affine points of the 1256 Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the 1257 identity element. Then Q:=(u, v), where 1259 u + u1 + u2 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), where 1261 lambda:=(v2 - v1)/(u2 - u1). 1263 Let P:=(u1, v1) be an affine point of the Montgomery curve M_{A,B} 1264 and let Q:=2*P, where Q is not the identity element. Then Q:=(u, v), 1265 where 1267 u + 2*u1 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), where 1269 lambda:=(3*u1^2 + 2*A*u1+1)/(2*B*v1). 1271 From the group laws above it follows that if P=(u, v), P1=(u1, v1), 1272 and P2=(u2, v2) are distinct affine points of the Montgomery curve 1273 M_{A,B} with P2:=P+P1 and if v is nonzero, then the v-coordinate of 1274 P1 can be expressed in terms of the u-coordinates of P, P1, and P2, 1275 and the v-coordinate of P, since 1277 2*B*v*v1=(u*u1+1)*(u+u1+2*A)-2*A-u2*(u-u1)^2. 1279 This property allows recovery of the v-coordinate of a point P1=k*P 1280 that is computed via the so-called Montgomery ladder, where P is an 1281 affine point with nonzero v-coordinate (i.e., it does not have order 1282 two). For future reference, note that the expression above uniquely 1283 determines the u-coordinate of P2 in terms of the u-coordinates of P 1284 and P1 and the product of their v-coordinates. Further details are 1285 out of scope. 1287 C.3. Group Laws for Twisted Edwards Curves 1289 Note: The group laws below hold for twisted Edwards curves E_{a,d} 1290 where a is a square in GF(q), whereas d is not. In this case, the 1291 addition formulae below are defined for each pair of points, without 1292 exceptions. Generalizations of this group law to other twisted 1293 Edwards curves are out of scope. 1295 For each point P of the twisted Edwards curve E_{a,d}, the point 1296 O:=(0,1) serves as identity element, i.e., P + O = O + P = P. 1298 For each point P:=(x, y) of the twisted Edwards curve E_{a,d}, the 1299 point -P is the point (-x, y) and one has P + (-P) = O (i.e., -P is 1300 the inverse of P). 1302 Let P1:=(x1, y1) and P2:=(x2, y2) be points of the twisted Edwards 1303 curve E_{a,d} and let Q:=P1 + P2. Then Q:=(x, y), where 1305 x = (x1*y2 + x2*y1)/(1 + d*x1*x2*y1*y2) and 1307 y = (y1*y2 - a*x1*x2)/(1 - d*x1*x2*y1*y2). 1309 Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and 1310 let Q:=2*P. Then Q:=(x, y), where 1312 x = (2*x1*y1)/(1 + d*x1^2*y1^2) and 1314 y = (y1^2 - a*x1^2)/(1 - d*x1^2*y1^2). 1316 Note that one can use the formulae for point addition for point 1317 doubling, taking inverses, and adding the identity element as well 1318 (i.e., the point addition formulae are uniform and complete (subject 1319 to our Note above)). 1321 From the group laws above (subject to our Note above) it follows that 1322 if P=(x, y), P1=(x1, y1), and P2=P=(x2, y2) are points of the twisted 1323 Edwards curve E_{a,d} with P2:=P+P1 and if x is nonzero, then the 1324 x-coordinate of P1 can be expressed in terms of the y-coordinates of 1325 P, P1, and P2, and the x-coordinate of P, since 1326 x*x1*(a-d*y*y1*y2)=y*y1-y2. 1328 (Here, observe that a-d*y*y1*y2 is nonzero per our Note above.) This 1329 property allows recovery of the x-coordinate of a point P1=k*P that 1330 is computed via the so-called Montgomery ladder, where P is an affine 1331 point with nonzero x-coordinate (i.e., it does not have order one or 1332 two). For future reference, note that the group law (subject to our 1333 Note above) uniquely determines the y-coordinate of P2 in terms of 1334 the y-coordinates of P and P1 and the product of their x-coordinates. 1335 Further details are out of scope. 1337 Appendix D. Relationship Between Curve Models 1339 The non-binary curves specified in Appendix A are expressed in 1340 different curve models, viz. as curves in short-Weierstrass form, as 1341 Montgomery curves, or as twisted Edwards curves. These curve models 1342 are related, as follows. 1344 D.1. Mapping between Twisted Edwards Curves and Montgomery Curves 1346 One can map points of the Montgomery curve M_{A,B} to points of the 1347 twisted Edwards curve E_{a,d}, where a:=(A+2)/B and d:=(A-2)/B and, 1348 conversely, map points of the twisted Edwards curve E_{a,d} to points 1349 of the Montgomery curve M_{A,B}, where A:=2*(a+d)/(a-d) and where 1350 B:=4/(a-d). For twisted Edwards curves we consider (i.e., those 1351 where a is a square in GF(q), whereas d is not), this defines a one- 1352 to-one correspondence, which - in fact - is an isomorphism between 1353 M_{A,B} and E_{a,d}, thereby showing that, e.g., the discrete 1354 logarithm problem in either curve model is equally hard. 1356 For the Montgomery curves and twisted Edwards curves we consider, the 1357 mapping from M_{A,B} to E_{a,d} is defined by mapping the point at 1358 infinity O and the point (0, 0) of order two of M_{A,B} to, 1359 respectively, the point (0, 1) and the point (0, -1) of order two of 1360 E_{a,d}, while mapping each other point (u, v) of M_{A,B} to the 1361 point (x,y):=(u/v,(u-1)/(u+1)) of E_{a,d}. The inverse mapping from 1362 E_{a,d} to M_{A,B} is defined by mapping the point (0, 1) and the 1363 point (0, -1) of order two of E_{a,d} to, respectively, the point at 1364 infinity O and the point (0, 0) of order two of M_{A,B}, while each 1365 other point (x, y) of E_{a,d} is mapped to the point 1366 (u,v):=((1+y)/(1-y),(1+y)/((1-y)*x)) of M_{A,B}. 1368 Implementations may take advantage of this mapping to carry out 1369 elliptic curve group operations originally defined for a twisted 1370 Edwards curve on the corresponding Montgomery curve, or vice-versa, 1371 and translating the result back to the original curve, thereby 1372 potentially allowing code reuse. 1374 D.2. Mapping between Montgomery Curves and Weierstrass Curves 1376 One can map points of the Montgomery curve M_{A,B} to points of the 1377 Weierstrass curve W_{a,b}, where a:=(3-A^2)/(3*B^2) and 1378 b:=(2*A^3-9*A)/(27*B^3). This defines a one-to-one correspondence, 1379 which - in fact - is an isomorphism between M_{A,B} and W_{a,b}, 1380 thereby showing that, e.g., the discrete logarithm problem in either 1381 curve model is equally hard. 1383 The mapping from M_{A,B} to W_{a,b} is defined by mapping the point 1384 at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while 1385 mapping each other point (u,v) of M_{A,B} to the point 1386 (X,Y):=((u+A/3)/B,v/B) of W_{a,b}. 1388 Note that not all Weierstrass curves can be injectively mapped to 1389 Montgomery curves, since the latter have a point of order two and the 1390 former may not. In particular, if a Weierstrass curve has prime 1391 order, such as is the case with the so-called "NIST prime curves", 1392 this inverse mapping is not defined. 1394 If the Weierstrass curve W_{a,b} has a point (alpha,0) of order two 1395 and c:=a+3*(alpha)^2 is a square in GF(q), one can map points of this 1396 curve to points of the Montgomery curve M_{A,B}, where A:=3*alpha/ 1397 gamma and B:=1/gamma and where gamma is any square root of c. In 1398 this case, the mapping from W_{a,b} to M_{A,B} is defined by mapping 1399 the point at infinity O of W_{a,b} to the point at infinity O of 1400 M_{A,B}, while mapping each other point (X,Y) of W_{a,b} to the point 1401 (u,v):=((X-alpha)/gamma,Y/gamma) of M_{A,B}. As before, this defines 1402 a one-to-one correspondence, which - in fact - is an isomorphism 1403 between W_{a,b} and M_{A,B}. It is easy to see that the mapping from 1404 W_{a,b} to M_{A,B} and that from M_{A,B} to W_{a,b} (if defined) are 1405 each other's inverse. 1407 This mapping can be used to implement elliptic curve group operations 1408 originally defined for a twisted Edwards curve or for a Montgomery 1409 curve using group operations for the corresponding elliptic curve in 1410 short-Weierstrass form and translating the result back to the 1411 original curve, thereby potentially allowing code reuse. 1413 Note that implementations for elliptic curves with short-Weierstrass 1414 form that hard-code the domain parameter a to a= -3 (which value is 1415 known to allow more efficient implementations) cannot always be used 1416 this way, since the curve W_{a,b} resulting from an isomorphic 1417 mapping cannot always be expressed as a Weierstrass curve with a=-3 1418 via a coordinate transformation. For more details, see Appendix F. 1420 D.3. Mapping between Twisted Edwards Curves and Weierstrass Curves 1422 One can map points of the twisted Edwards curve E_{a,d} to points of 1423 the Weierstrass curve W_{a,b}, via function composition, where one 1424 uses the isomorphic mapping between twisted Edwards curves and 1425 Montgomery curves of Appendix D.1 and the one between Montgomery and 1426 Weierstrass curves of Appendix D.2. Obviously, one can use function 1427 composition (now using the respective inverses - if these exist) to 1428 realize the inverse of this mapping. 1430 Appendix E. Curve25519 and Cousins 1432 This section introduces curves related to Curve25519 and explains 1433 their relationships. 1435 E.1. Curve Definition and Alternative Representations 1437 The elliptic curve Curve25519 is the Montgomery curve M_{A,B} defined 1438 over the prime field GF(p), with p:=2^{255}-19, where A:=486662 and 1439 B:=1. This curve has order h*n, where h=8 and where n is a prime 1440 number. For this curve, A^2-4 is not a square in GF(p), whereas A+2 1441 is. The quadratic twist of this curve has order h1*n1, where h1=4 1442 and where n1 is a prime number. For this curve, the base point is 1443 the point (Gu, Gv), where Gu=9 and where Gv is an odd integer in the 1444 interval [0, p-1]. 1446 This curve has the same group structure as (is "isomorphic" to) the 1447 twisted Edwards curve E_{a,d} defined over GF(p), with as base point 1448 the point (Gx, Gy), where parameters are as specified in 1449 Appendix E.3. This curve is denoted as Edwards25519. For this 1450 curve, the parameter a is a square in GF(p), whereas d is not, so the 1451 group laws of Appendix C.3 apply. 1453 The curve is also isomorphic to the elliptic curve W_{a,b} in short- 1454 Weierstrass form defined over GF(p), with as base point the point 1455 (GX, GY), where parameters are as specified in Appendix E.3. This 1456 curve is denoted as Wei25519. 1458 E.2. Switching between Alternative Representations 1460 Each affine point (u, v) of Curve25519 corresponds to the point (X, 1461 Y):=(u + A/3, v) of Wei25519, while the point at infinity of 1462 Curve25519 corresponds to the point at infinity of Wei25519. (Here, 1463 we used the mappings of Appendix D.2 and that B=1.) Under this 1464 mapping, the base point (Gu, Gv) of Curve25519 corresponds to the 1465 base point (GX, GY) of Wei25519. The inverse mapping maps the affine 1466 point (X, Y) of Wei25519 to (u, v):=(X - A/3, Y) of Curve25519, while 1467 mapping the point at infinity of Wei25519 to the point at infinity of 1468 Curve25519. Note that this mapping involves a simple shift of the 1469 first coordinate and can be implemented via integer-only arithmetic 1470 as a shift of (p+A)/3 for the isomorphic mapping and a shift of 1471 -(p+A)/3 for its inverse, where delta=(p+A)/3 is the element of GF(p) 1472 defined by 1474 delta 19298681539552699237261830834781317975544997444273427339909597 1475 334652188435537 1477 (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa 1478 aaaaaaaa aaad2451). 1480 (Note that, depending on the implementation details of the field 1481 arithmetic, one may have to shift the result by +p or -p if this 1482 integer is not in the interval [0,p-1].) 1484 The curve Edwards25519 is isomorphic to the curve Curve25519, where 1485 the base point (Gu, Gv) of Curve25519 corresponds to the base point 1486 (Gx,Gy) of Edwards25519 and where the point at infinity and the point 1487 (0,0) of order two of Curve25519 correspond to, respectively, the 1488 point (0, 1) and the point (0, -1) of order two of Edwards25519 and 1489 where each other point (u, v) of Curve25519 corresponds to the point 1490 (c*u/v, (u-1)/(u+1)) of Edwards25519, where c is the element of GF(p) 1491 defined by 1493 c sqrt(-(A+2)/B) 1495 51042569399160536130206135233146329284152202253034631822681833788 1496 666877215207 1498 (=0x70d9120b 9f5ff944 2d84f723 fc03b081 3a5e2c2e b482e57d 1499 3391fb55 00ba81e7). 1501 (Here, we used the mapping of Appendix D.1 and normalized this using 1502 the mapping of Appendix F.1 (where the element s of that appendix is 1503 set to c above).) The inverse mapping from Edwards25519 to 1504 Curve25519 is defined by mapping the point (0, 1) and the point (0, 1505 -1) of order two of Edwards25519 to, respectively, the point at 1506 infinity and the point (0,0) of order two of Curve25519 and having 1507 each other point (x, y) of Edwards25519 correspond to the point ((1 + 1508 y)/(1 - y), c*(1 + y)/((1-y)*x)) of Curve25519. 1510 The curve Edwards25519 is isomorphic to the Weierstrass curve 1511 Wei25519, where the base point (Gx, Gy) of Edwards25519 corresponds 1512 to the base point (GX,GY) of Wei25519 and where the identity element 1513 (0,1) and the point (0,-1) of order two of Edwards25519 correspond 1514 to, respectively, the point at infinity O and the point (A/3, 0) of 1515 order two of Wei25519 and where each other point (x, y) of 1516 Edwards25519 corresponds to the point (X, Y):=((1+y)/(1-y)+A/3, 1517 c*(1+y)/((1-y)*x)) of Wei25519, where c was defined before. (Here, 1518 we used the mapping of Appendix D.3.) The inverse mapping from 1519 Wei25519 to Edwards25519 is defined by mapping the point at infinity 1520 O and the point (A/3, 0) of order two of Wei25519 to, respectively, 1521 the identity element (0,1) and the point (0,-1) of order two of 1522 Edwards25519 and having each other point (X, Y) of Wei25519 1523 correspond to the point (c*(X-A/3)/Y, (X-A/3-1)/(X-A/3+1)) of 1524 Edwards25519. 1526 Note that these mappings can be easily realized if points are 1527 represented in projective coordinates, using a few field 1528 multiplications only, thus allowing switching between alternative 1529 curve representations with negligible relative incremental cost. 1531 E.3. Domain Parameters 1533 The parameters of the Montgomery curve and the corresponding 1534 isomorphic curves in twisted Edwards curve and short-Weierstrass form 1535 are as indicated below. Here, the domain parameters of the 1536 Montgomery curve Curve25519 and of the twisted Edwards curve 1537 Edwards25519 are as specified in [RFC7748]; the domain parameters of 1538 Wei25519 are "new". 1540 General parameters (for all curve models): 1542 p 2^{255}-19 1544 (=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff 1545 ffffffff ffffffed) 1547 h 8 1549 n 72370055773322622139731865630429942408571163593799076060019509382 1550 85454250989 1552 (=2^{252} + 0x14def9de a2f79cd6 5812631a 5cf5d3ed) 1554 h1 4 1556 n1 14474011154664524427946373126085988481603263447650325797860494125 1557 407373907997 1559 (=2^{253} - 0x29bdf3bd 45ef39ac b024c634 b9eba7e3) 1561 Montgomery curve-specific parameters (for Curve25519): 1563 A 486662 (=0x076d06) 1564 B 1 (=0x01) 1566 Gu 9 (=0x09) 1568 Gv 14781619447589544791020593568409986887264606134616475288964881837 1569 755586237401 1571 (=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2 1572 29e9c5a2 7eced3d9) 1574 Twisted Edwards curve-specific parameters (for Edwards25519): 1576 a -1 (-0x01) 1578 d -121665/121666 = - (A-2)/(A+2) 1580 (=370957059346694393431380835087545651895421138798432190163887855 1581 33085940283555) 1583 (=0x52036cee 2b6ffe73 8cc74079 7779e898 00700a4d 4141d8ab 1584 75eb4dca 135978a3) 1586 Gx 15112221349535400772501151409588531511454012693041857206046113283 1587 949847762202 1589 (=0x216936d3 cd6e53fe c0a4e231 fdd6dc5c 692cc760 9525a7b2 1590 c9562d60 8f25d51a) 1592 Gy 4/5 1594 (=463168356949264781694283940034751631413079938662562256157830336 1595 03165251855960) 1597 (=0x66666666 66666666 66666666 66666666 66666666 66666666 1598 66666666 66666658) 1600 Weierstrass curve-specific parameters (for Wei25519): 1602 a 19298681539552699237261830834781317975544997444273427339909597334 1603 573241639236 1605 (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa 1606 aaaaaa98 4914a144) 1608 b 55751746669818908907645289078257140818241103727901012315294400837 1609 956729358436 1610 (=0x7b425ed0 97b425ed 097b425e d097b425 ed097b42 5ed097b4 1611 260b5e9c 7710c864) 1613 GX 19298681539552699237261830834781317975544997444273427339909597334 1614 652188435546 1616 (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa 1617 aaaaaaaa aaad245a) 1619 GY 14781619447589544791020593568409986887264606134616475288964881837 1620 755586237401 1622 (=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2 1623 29e9c5a2 7eced3d9) 1625 Appendix F. Further Mappings 1627 The non-binary curves specified in Appendix A are expressed in 1628 different curve models, viz. as curves in short-Weierstrass form, as 1629 Montgomery curves, or as twisted Edwards curves. In Appendix D we 1630 already described relationships between these various curve models. 1631 Further mappings exist between elliptic curves within the same curve 1632 model. These can be exploited to force some of the domain parameters 1633 to specific values that allow for a more efficient implementation of 1634 the addition formulae. 1636 F.1. Isomorphic Mapping between Twisted Edwards Curves 1638 One can map points of the twisted Edwards curve E_{a,d} to points of 1639 the twisted Edwards curve E_{a',d'}, where a:=a'*s^2 and d:=d'*s^2 1640 for some nonzero element s of GF(q). This defines a one-to-one 1641 correspondence, which - in fact - is an isomorphism between E_{a,d} 1642 and E_{a',d'}. 1644 The mapping from E_{a,d} to E_{a',d'} is defined by mapping the point 1645 (x,y) of E_{a,d} to the point (x', y'):=(s*x, y) of E_{a',d'}. The 1646 inverse mapping from E_{a',d'} to E_{a,d} is defined by mapping the 1647 point (x', y') of E_{a',d'} to the point (x, y):=(x'/s, y') of 1648 E_{a,d}. 1650 Implementations may take advantage of this mapping to carry out 1651 elliptic curve group operations originally defined for a twisted 1652 Edwards curve with generic domain parameters a and d on a 1653 corresponding isomorphic twisted Edwards curve with domain parameters 1654 a' and d' that have a more special form and that are known to allow 1655 for more efficient implementations of addition laws and translating 1656 the result back to the original curve. In particular, it is known 1657 that such efficiency improvements exist if a':=(+/-)1 (see 1658 [tEd-Formulas]). 1660 F.2. Isomorphic Mapping between Montgomery Curves 1662 One can map points of the Montgomery curve M_{A,B} to points of the 1663 Montgomery curve M_{A',B'}, where A:=A' and B:=B'*s^2 for some 1664 nonzero element s of GF(q). This defines a one-to-one 1665 correspondence, which - in fact - is an isomorphism between M_{A,B} 1666 and M_{A',B'}. 1668 The mapping from M_{A,B} to M_{A',B'} is defined by mapping the point 1669 at infinity O of M_{A,B} to the point at infinity O of M_{A',B'}, 1670 while mapping each other point (u,v) of M_{A,B} to the point (u', 1671 v'):=(u, s*v) of M_{A',B'}. The inverse mapping from M_{A',B'} to 1672 M_{A,B} is defined by mapping the point at infinity O of M_{A',B'} to 1673 the point at infinity O of M_{A,B}, while mapping each other point 1674 (u',v') of M_{A',B'} to the point (u,v):=(u',v'/s) of M_{A,B}. 1676 One can also map points of the Montgomery curve M_{A,B} to points of 1677 the Montgomery curve M_{A',B'}, where A':=-A and B':=-B. This 1678 defines a one-to-one correspondence, which - in fact - is an 1679 isomorphism between M_{A,B} and M_{A',B'}. 1681 In this case, the mapping from M_{A,B} to M_{A',B'} is defined by 1682 mapping the point at infinity O of M_{A,B} to the point at infinity O 1683 of M_{A',B'}, while mapping each other point (u,v) of M_{A,B} to the 1684 point (u',v'):=(-u,v) of M_{A',B'}. The inverse mapping from 1685 M_{A',B'} to M_{A,B} is defined by mapping the point at infinity O of 1686 M_{A',B'} to the point at infinity O of M_{A,B}, while mapping each 1687 other point (u',v') of M_{A',B'} to the point (u,v):=(-u',v') of 1688 M_{A,B}. 1690 Implementations may take advantage of these mappings to carry out 1691 elliptic curve groups operations originally defined for a Montgomery 1692 curve with generic domain parameters A and B on a corresponding 1693 isomorphic Montgomery curve with domain parameters A' and B' that 1694 have a more special form and that are known to allow for more 1695 efficient implementations of addition laws and translating the result 1696 back to the original curve. In particular, it is known that such 1697 efficiency improvements exist if B' assumes a small absolute value, 1698 such as B':=(+/-)1. (see [Mont-Ladder]). 1700 F.3. Isomorphic Mapping between Weierstrass Curves 1702 One can map points of the Weierstrass curve W_{a,b} to points of the 1703 Weierstrass curve W_{a',b'}, where a':=a*s^4 and b':=b*s^6 for some 1704 nonzero element s of GF(q). This defines a one-to-one 1705 correspondence, which - in fact - is an isomorphism between W_{a,b} 1706 and W_{a',b'}. 1708 The mapping from W_{a,b} to W_{a',b'} is defined by mapping the point 1709 at infinity O of W_{a,b} to the point at infinity O of W_{a',b'}, 1710 while mapping each other point (X,Y) of W_{a,b} to the point 1711 (X',Y'):=(X*s^2, Y*s^3) of W_{a',b'}. The inverse mapping from 1712 W_{a',b'} to W_{a,b} is defined by mapping the point at infinity O of 1713 W_{a',b'} to the point at infinity O of W_{a,b}, while mapping each 1714 other point (X', Y') of W_{a',b'} to the point (X,Y):=(X'/s^2,Y'/s^3) 1715 of W_{a,b}. 1717 Implementations may take advantage of this mapping to carry out 1718 elliptic curve group operations originally defined for a Weierstrass 1719 curve with generic domain parameters a and b on a corresponding 1720 isomorphic Weierstrass curve with domain parameter a' and b' that 1721 have a more special form and that are known to allow for more 1722 efficient implementations of addition laws and translating the result 1723 back to the original curve. In particular, it is known that such 1724 efficiency improvements exist if a'=-3 (mod p), where p is the 1725 characteristic of GF(q), and one uses so-called Jacobian coordinates 1726 with a particular projective version of the addition laws of 1727 Appendix C.1. While not all Weierstrass curves can be put into this 1728 form, all traditional NIST curves have domain parameter a=-3, while 1729 all Brainpool curves [RFC5639] are isomorphic to a Weierstrass curve 1730 of this form via the above mapping. 1732 Note that implementations for elliptic curves with short-Weierstrass 1733 form that hard-code the domain parameter a to a= -3 cannot always be 1734 used this way, since the curve W_{a,b} cannot always be expressed in 1735 terms of a Weierstrass curve with a'=-3 via a coordinate 1736 transformation: this only holds if a'/a is a fourth power in GF(q) 1737 (see Section 3.1.5 of [GECC]). However, even in this case, one can 1738 still express the curve W_{a,b} as a Weierstrass curve with a small 1739 domain parameter value a', thereby still allowing a more efficient 1740 implementation than with a general domain parameter value a. 1742 F.4. Isogenous Mapping between Weierstrass Curves 1744 One can still map points of the Weierstrass curve W_{a,b} to points 1745 of the Weierstrass curve W_{a',b'}, where a':=-3 (mod p) and where p 1746 is the characteristic of GF(q), even if a'/a is not a fourth power in 1747 GF(q). In that case, this mappping cannot be an isomorphism (see 1748 Appendix F.3). Instead, the mapping is a so-called isogeny (or 1749 homomorphism). Since most elliptic curve operations process points 1750 of prime order or use so-called "co-factor multiplication", in 1751 practice the resulting mapping has similar properties as an 1752 isomorphism. In particular, one can still take advantage of this 1753 mapping to carry out elliptic curve group operations originally 1754 defined for a Weierstrass curve with domain parameter a unequal to -3 1755 (mod p) on a corresponding isogenous Weierstrass curve with domain 1756 parameter a'=-3 (mod p) and translating the result back to the 1757 original curve. 1759 In this case, the mapping from W_{a,b} to W_{a',b'} is defined by 1760 mapping the point at infinity O of W_{a,b} to the point at infinity O 1761 of W_{a',b'}, while mapping each other point (X,Y) of W_{a,b} to the 1762 point (X',Y'):=(u(X)/w(X)^2,Y*v(X)/w(X)^3) of W_{a',b'}. Here, u(X), 1763 v(X), and w(X) are polynomials in X that depend on the isogeny in 1764 question, as do domain parameters a' and b'. The inverse mapping 1765 from W_{a',b'} to W_{a,b} is again an isogeny (called the dual 1766 isogeny) and defined by mapping the point at infinity O of W_{a',b'} 1767 to the point at infinity O of W_{a,b}, while mapping each other point 1768 (X', Y') of W_{a',b'} to the point 1769 (X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of W_{a,b}, where -- 1770 again -- u'(X'), v'(X'), and w'(X') are polynomials in X' that depend 1771 on the isogeny in question. These mappings have the property that 1772 their composition is not the identity mapping (as was the case with 1773 the isomorphic mappings discussed in Appendix F.3), but rather a 1774 fixed multiple hereof: if this multiple is l then the isogeny is 1775 called an isogeny of degree l (or l-isogeny) and u, v, and w (and, 1776 similarly, u', v', and w') are polynomials of degrees l, 3*(l-1)/2, 1777 and (l-1)/2, respectively. Note that an isomorphism is simply an 1778 isogeny of degree l=1. Details of how to determine isogenies are out 1779 of scope of this document. The above formulas assume that the 1780 isogeny has odd degree (i.e., l is odd); detailed formulas for even- 1781 degree isogenies are similar, but out of scope. 1783 Implementations may take advantage of this mapping to carry out 1784 elliptic curve group operations originally defined for a Weierstrass 1785 curve with a generic domain parameter a on a corresponding isogenous 1786 Weierstrass curve with domain parameter a'=-3 (mod p), where one can 1787 use so-called Jacobian coordinates with a particular projective 1788 version of the addition laws of Appendix C.1. Since all traditional 1789 NIST curves have domain parameter a=-3, while all Brainpool curves 1790 [RFC5639] are isomorphic to a Weierstrass curve of this form, this 1791 allows taking advantage of existing implementations for these curves 1792 that may have a hardcoded a=-3 (mod p) domain parameter, provided one 1793 switches back and forth to this curve form using the isogenous 1794 mapping in question. 1796 Note that isogenous mappings can be easily realized using 1797 representations in projective coordinates and involves roughly 3*l 1798 finite field multiplications, thus allowing switching between 1799 alternative representations at relatively low incremental cost 1800 compared to that of elliptic curve scalar multiplications (provided 1801 the isogeny has low degree l). Note, however, that this does require 1802 storage of the polynomial coefficients of the isogeny and dual 1803 isogeny involved. This illustrates that low-degree isogenies are to 1804 be preferred, since an l-isogeny (usually) requires storing roughly 1805 6*l elements of GF(q). While there are many isogenies, we therefore 1806 only consider those with the desired property with lowest possible 1807 degree. 1809 Appendix G. Further Cousins of Curve25519 1811 This section introduces some further curves related to Curve25519 and 1812 explains their relationships. 1814 G.1. Further Alternative Representations 1816 The Weierstrass curve Wei25519 is isomorphic to the Weierstrass curve 1817 Wei25519.2 defined over GF(p), with as base point the pair (G2X,G2Y), 1818 and isogenous to the Weierstrass curve Wei25519.-3 defined over 1819 GF(p), with as base point the pair (G3X, G3Y), where parameters are 1820 as specified in Appendix G.3 and where the related mappings are as 1821 specified in Appendix G.2. 1823 G.2. Further Switching 1825 Each affine point (X, Y) of Wei25519 corresponds to the point (X', 1826 Y'):=(X*s^2,Y*s^3) of Wei25519.2, where s is the element of GF(p) 1827 defined by 1829 s 20343593038935618591794247374137143598394058341193943326473831977 1830 39407761440 1832 (=0x047f6814 6d568b44 7e4552ea a5ed633d 02d62964 a2b0a120 1833 5e7941e9 375de020), 1835 while the point at infinity of Wei25519 corresponds to the point at 1836 infinity of Wei25519.2. (Here, we used the mapping of Appendix F.3.) 1837 Under this mapping, the base point (GX, GY) of Wei25519 corresponds 1838 to the base point (G2X,G2Y) of Wei25519.2. The inverse mapping maps 1839 the affine point (X', Y') of Wei25519.2 to (X,Y):=(X'/s^2,Y'/s^3) of 1840 Wei25519, while mapping the point at infinity O of Wei25519.2 to the 1841 point at infinity O of Wei25519. Note that this mapping (and its 1842 inverse) involves a modular multiplication of both coordinates with 1843 fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which 1844 can be precomputed. 1846 Each affine point (X,Y) of Wei25519 corresponds to the point 1847 (X',Y'):=(X1*t^2,Y1*t^3) of Wei25519.-3, where 1848 (X1,Y1)=(u(X)/w(X)^2,Y*v(X)/w(X)^3), where u, v, and w are the 1849 polynomials with coefficients in GF(p) as defined in Appendix G.4.1 1850 and where t is the element of GF(p) defined by 1852 t 35728133398289175649586938605660542688691615699169662967154525084 1853 644181596229 1855 (=0x4efd6829 88ff8526 e189f712 5999550c e9ef729b ed1a7015 1856 73b1bab8 8bfcd845), 1858 while the point at infinity of Wei25519 corresponds to the point at 1859 infinity of Wei25519.-3. (Here, we used the isogenous mapping of 1860 Appendix F.4.) Under this isogenous mapping, the base point (GX,GY) 1861 of Wei25519 corresponds to the base point (G3X,G3Y) of Wei25519.-3. 1862 The dual isogeny maps the affine point (X',Y') of Wei25519.-3 to the 1863 affine point (X,Y):=(u'(X1)/w'(X1)^2,Y1*v'(X1)/w'(X1)^3) of Wei25519, 1864 where (X1,Y1)=(X'/t^2,Y'/t^3) and where u', v', and w' are the 1865 polynomials with coefficients in GF(p) as defined in Appendix G.4.2, 1866 while mapping the point at infinity O of Wei25519.-3 to the point at 1867 infinity O of Wei25519. Under this dual isogenous mapping, the base 1868 point (G3X, G3Y) of Wei25519.-3 corresponds to a multiple of the base 1869 point (GX, GY) of Wei25519, where this multiple is l=47 (the degree 1870 of the isogeny; see the description in Appendix F.4). Note that this 1871 isogenous map (and its dual) primarily involves the evaluation of 1872 three fixed polynomials involving the x-coordinate, which takes 1873 roughly 140 modular multiplications (or less than 5-10% relative 1874 incremental cost compared to the cost of an elliptic curve scalar 1875 multiplication). 1877 G.3. Further Domain Parameters 1879 The parameters of the Weierstrass curve with a=2 that is isomorphic 1880 with Wei25519 and the parameters of the Weierstrass curve with a=-3 1881 that is isogenous with Wei25519 are as indicated below. Both domain 1882 parameter sets can be exploited directly to derive more efficient 1883 point addition formulae, should an implementation facilitate this. 1885 General parameters: same as for Wei25519 (see Appendix E.3) 1887 Weierstrass curve-specific parameters (for Wei25519.2, i.e., with 1888 a=2): 1890 a 2 (=0x02) 1892 b 12102640281269758552371076649779977768474709596484288167752775713 1893 178787220689 1895 (=0x1ac1da05 b55bc146 33bd39e4 7f94302e f19843dc f669916f 1896 6a5dfd01 65538cd1) 1898 G2X 10770553138368400518417020196796161136792368198326337823149502681 1899 097436401658 1901 (=0x17cfeac3 78aed661 318e8634 582275b6 d9ad4def 072ea193 1902 5ee3c4e8 7a940ffa) 1904 G2Y 54430575861508405653098668984457528616807103332502577521161439773 1905 88639873869 1907 (=0x0c08a952 c55dfad6 2c4f13f1 a8f68dca dc5c331d 297a37b6 1908 f0d7fdcc 51e16b4d) 1910 Weierstrass curve-specific parameters (for Wei25519.-3, i.e., with 1911 a=-3): 1913 a -3 1915 (=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff 1916 ffffffff ffffffea) 1918 b 29689592517550930188872794512874050362622433571298029721775200646 1919 451501277098 1921 (=0x41a3b6bf c668778e be2954a4 b1df36d1 485ecef1 ea614295 1922 796e1022 40891faa) 1924 G3X 53837179229940872434942723257480777370451127212339198133697207846 1925 219400243292 1927 (=0x7706c37b 5a84128a 3884a5d7 1811f1b5 5da3230f fb17a8ab 1928 0b32e48d 31a6685c) 1930 G3Y 69548073091100184414402055529279970392514867422855141773070804184 1931 60388229929 1933 (=0x0f60480c 7a5c0e11 40340adc 79d6a2bf 0cb57ad0 49d025dc 1934 38d80c77 985f0329) 1936 G.4. Isogeny Details 1938 The isogeny and dual isogeny are both isogenies with degree l=47. 1939 Both are specified by a triple of polynomials u, v, and w (resp. u', 1940 v', and w') of degree 47, 69, and 23, respectively, with coefficients 1941 in GF(p). The coeffients of each of these polynomials are specified 1942 in Appendix G.4.1 (for the isogeny) and in Appendix G.4.2 (for the 1943 dual isogeny). For each polynomial in variable x, the coefficients 1944 are tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in 1945 hexadecimal format. 1947 G.4.1. Isogeny Parameters 1949 G.4.1.1. Coefficients of u(x) 1951 0 0x670ed14828b6f1791ceb3a9cc0edfe127dee8729c5a72ddf77bb1abaebbba1e8 1953 1 0x1135ca8bd5383cb3545402c8bce2ced14b45c29b241e4751b035f27524a9f932 1955 2 0x3223806ff5f669c430efd74df8389f058d180e2fcffa5cdef3eacecdd2c34771 1957 3 0x31b8fecf3f17a819c228517f6cd9814466c8c8bea2efccc47a29bfc14c364266 1959 4 0x2541305c958c5a326f44efad2bec284e7abee840fadb08f2d994cd382fd8ce42 1961 5 0x6e6f9c5792f3ff497f860f44a9c469cec42bd711526b733e10915be5b2dbd8c6 1963 6 0x3e9ad2e5f594b9ce6b06d4565891d28a1be8790000b396ef0bf59215d6cabfde 1965 7 0x278448895d236403bbc161347d19c913e7df5f372732a823ed807ee1d30206be 1967 8 0x42f9d171ea8dc2f4a14ea46cc0ee54967175ecfe83a975137b753cb127c35060 1969 9 0x128e40efa2d3ccb51567e73bae91e7c31eac45700fa13ce5781cbe5ddc985648 1971 10 0x450e5086c065430b496d88952dd2d5f2c5102bc27074d4d1e98bfa47413e0645 1973 11 0x487ef93da70dfd44a4db8cb41542e33d1aa32237bdca3a59b3ce1c59585f253d 1975 12 0x33d209270026b1d2db96efb36cc2fa0a49be1307f49689022eab1892b010b785 1977 13 0x4732b5996a20ebc4d5c5e2375d3b6c4b700c681bd9904343a14a0555ef0ecd48 1979 14 0x64dc9e8272b9f5c6ad3470db543238386f42b18cb1c592cc6caf7893141b2107 1981 15 0x52bbacd1f85c61ef7eafd8da27260fa2821f7a961867ed449b283036508ac5c5 1983 16 0x320447ed91210985e2c401cfe1a93db1379424cf748f92fd61ab5cc356bc89a2 1985 17 0x23d23a49bbcdf8cf4c4ce8a4ff7dd87d1ad1970317686254d5b4d2ec050d019f 1987 18 0x1601fca063f0bbbf15f198b3c20e474c2170294fa981f73365732d2372b40cd4 1989 19 0x7bf3f93840035e9688cfff402cee204a17c0de9779fc33503537dd78021bf4c4 1991 20 0x311998ce59fb7e1cd6af591ece3e84dfcb1c330cbcf28c0349e37b9581452853 1993 21 0x7ae5e41acfd28a9add2216dfed34756575a19b16984c1f3847b694326dad7f99 1994 22 0x704957e279244a5b107a6c57bd0ab9afe5227b7c0be2052cd3513772a40efee7 1996 23 0x56b918b5a0c583cb763550f8f71481e57c13bdcef2e5cfc8091d0821266f233b 1998 24 0x677073fed43ab291e496f798fbcf217bac3f014e35d0c2fa07f041ae746a04d7 2000 25 0x22225388e76f9688c7d4053b50ba41d0d8b71a2f21da8353d98472243ef50170 2002 26 0x66930b3dffdd3995a2502cef790d78b091c875192d8074bb5d5639f736400555 2004 27 0x79eb677c5e36971e8d64d56ebc0dedb4e9b7dd2d7b01343ebbd4d358d376e490 2006 28 0x48a204c2ca6d8636e9994842605bd648b91b637844e38d6c7dd707edce8256e2 2008 29 0x0fb3529b0d4b9ce2d70760f33e8ce997a58999718e9277caf48623d27ae6a788 2010 30 0x4352604bffd0c7d7a9ed898a2c6e7cf2512ffb89407271ba1f2c2d0ead8cc5aa 2012 31 0x6667697b29785fb6f0bd5e04d828991a5fe525370216f347ec767a26e7aac936 2014 32 0x09fc950b083c56dbd989badf9887255e203c879f123a7cb28901e50aea6d64dc 2016 33 0x41e51b51b5caadd1c15436bbf37596a1d7288a5f495d6b5b1ae66f8b2942b31d 2018 34 0x073b59fec709aa1cabd429e981c6284822a8b7b07620c831ab41fd31d5cf7430 2020 35 0x67e9b88e9a1bfbc2554107d67d814986f1b09c3107a060cba21c019a2d5dc848 2022 36 0x6881494a1066ca176c5e174713786040affb4268b19d2abf28ef4293429f89c1 2024 37 0x5f4d30502ff1e1ccd624e6f506569454ab771869d7483e26afc09dea0c5ccd3d 2026 38 0x02a814cfc5859bca51e539c159955cbe729a58978b52329575d09bc6c3bf97ad 2028 39 0x1313c8aaae20d6f4397f0d8b19e52cfcdf8d8e10fba144aec1778fd10ddf4e9c 2030 40 0x7008d38f434b98953a996d4cc79fcbef9502411dcdf92005f725cea7ce82ad47 2032 41 0x5a74d1296aaaa245ffb848f434531fa3ba9e5cb9098a7091d36c2777d4cf5a13 2034 42 0x4bd3b700606397083f8038177bdaa1ac6edbba0447537582723cae0fd29341a9 2036 43 0x573453fb2b093016f3368356c786519d54ed05f5372c01723b4da520597ec217 2038 44 0x77f5c605bdb3a30d7d9c8840fce38650910d4418eed707a212c8927f41c2c812 2040 45 0x16d6b9f7ff57ca32350057de1204cc6d69d4ef1b255dfef8080118e2fef6ace3 2041 46 0x34e8595832a4021f8b5744014c6b4f7da7df0d0329e8b6b4d44c8fadad6513b7 2043 47 0x01 2045 G.4.1.2. Coefficients of v(x) 2047 0 0x0f9f5eb7134e6f8dafa30c45afa58d7bfc6d4e3ccbb5de87b562fd77403972b2 2049 1 0x36c2dcd9e88f0d2d517a15fc453a098bbbb5a05eb6e8da906fae418a4e1a13f7 2051 2 0x0b40078302c24fa394a834880d5bf46732ca1b4894172fb7f775821276f558b3 2053 3 0x53dd8e2234573f7f3f7df11e90a7bdd7b75d807f9712f521d4fb18af59aa5f26 2055 4 0x6d4d7bb08de9061988a8cf6ff3beb10e933d4d2fbb8872d256a38c74c8c2ceda 2057 5 0x71bfe5831b30e28cd0fbe1e9916ab2291c6beacc5af08e2c9165c632e61dd2f5 2059 6 0x7c524f4d17ff2ee88463da012fc12a5b67d7fb5bd0ab59f4bbf162d76be1c89c 2061 7 0x758183d5e07878d3364e3fd4c863a5dc1fe723f48c4ab4273fc034f5454d59a4 2063 8 0x1eb41ef2479444ecdccbc200f64bde53f434a02b6c3f485d32f14da6aa7700e1 2065 9 0x1490f3851f016cc3cf8a1e3c16a53317253d232ed425297531b560d70770315c 2067 10 0x09bc43131964e46d905c3489c9d465c3abbd26eab9371c10e429b36d4b86469c 2069 11 0x5f27c173d94c7a413a288348d3fc88daa0bcf5af8f436a47262050f240e9be3b 2071 12 0x1d20010ec741aaa393cd19f0133b35f067adab0d105babe75fe45c8ba2732ceb 2073 13 0x01b3c669ae49b86be2f0c946a9ff6c48e44740d7d9804146915747c3c025996a 2075 14 0x24c6090f79ec13e3ae454d8f0f98e0c30a8938180595f79602f2ba013b3c10db 2077 15 0x4650c5b5648c6c43ac75a2042048c699e44437929268661726e7182a31b1532f 2079 16 0x0957a835fb8bac3360b5008790e4c1f3389589ba74c8e8bf648b856ba7f22ba5 2081 17 0x1cd1300bc534880f95c7885d8df04a82bd54ed3e904b0749e0e3f8cb3240c7c7 2083 18 0x760b486e0d3c6ee0833b34b64b7ebc846055d4d1e0beeb6aedd5132399ada0ea 2085 19 0x1c666846c63965ef7edf519d6ada738f2b676ae38ff1f4621533373931b3220e 2087 20 0x365055118b38d4bc0df86648044affea2ef33e9a392ad336444e7d15e45585d1 2088 21 0x736487bde4b555abfccd3ea7ddcda98eda0d7c879664117dee906a88bc551194 2090 22 0x70de05ab9520222a37c7a84c61eedff71cb50c5f6647fc2a5d6e0ff2305cea37 2092 23 0x59053f6cdf6517ab3fe4bd9c9271d1892f8cf353d8041b98409e1e341a01f8b5 2094 24 0x375db54ed12fe8df9a198ea40200e812c2660b7022681d7932d89fafe7c6e88d 2096 25 0x2a070c31d1c1a064daf56c79a044bd1cd6d13f1ddb0ff039b03a6469aaa9ed77 2098 26 0x41482351e7f69a756a5a2c0b3fa0681c03c550341d0ca0f76c5b394db9d2de8d 2100 27 0x747ac1109c9e9368d94a302cb5a1d23fcc7f0fd8a574efb7ddcaa738297c407a 2102 28 0x45682f1f2aab6358247e364834e2181ad0448bb815c587675fb2fee5a2119064 2104 29 0x148c5bf44870dfd307317f0a0e4a8c163940bee1d2f01455a2e658aa92c13620 2106 30 0x6add1361e56ffa2d2fbbddba284b35be5845aec8069fc28af009d53290a705ce 2108 31 0x6631614c617400dc00f2c55357f67a94268e7b5369b02e55d5db46c935be3af5 2110 32 0x17cffb496c64bb89d91c8c082f4c288c3c87feabd6b08591fe5a92216c094637 2112 33 0x648ff88155969f54c955a1834ad227b93062bb191170dd8c4d759f79ad5da250 2114 34 0x73e50900b89e5f295052b97f9d0c9edb0fc7d97b7fa5e3cfeefe33dd6a9cb223 2116 35 0x6afcb2f2ffe6c08508477aa4956cbd3dc864257f5059685adf2c68d4f2338f00 2118 36 0x372fd49701954c1b8f00926a8cb4b157d4165b75d53fa0476716554bf101b74c 2120 37 0x0334ed41325f3724ff8becbf2b3443fea6d30fa543d1ca13188aceb2bdaf5f4e 2122 38 0x70e629c95a94e8e1b3974acb25e18ba42f8d5991786f0931f650c283adfe82fd 2124 39 0x738a625f4c62d3d645f1274e09ab344e72d441f3c0e82989d3e21e19212f23f3 2126 40 0x7093737294b29f21522f5664a9941c9b476f75d443b647bd2c777040bcd12a6a 2128 41 0x0a996bad5863d821ccb8b89fa329ddbe5317a46bcb32552db396bea933765436 2130 42 0x2da237e3741b75dd0264836e7ef634fc0bc36ab187ebc790591a77c257b06f53 2132 43 0x1902f3daa86fa4f430b57212924fdc9e40f09e809f3991a0b3a10ab186c50ee5 2134 44 0x12baffec1bf20c921afd3cdf67a7f1d87c00d5326a3e5c83841593c214dadcb1 2135 45 0x6460f5a68123cb9e7bc1289cd5023c0c9ccd2d98eea24484fb3825b59dcd09aa 2137 46 0x2c7d63a868ffc9f0fd034f821d84736c5bc33325ce98aba5f0d95fef6f230ec8 2139 47 0x756e0063349a702db7406984c285a9b6bfba48177950d4361d8efa77408dc860 2141 48 0x037f3e30032b21e0279738e0a2b689625447831a2ccf15c638672da9aa7255ae 2143 49 0x1107c0dbe15d6ca9e790768317a40bcf23c80f1841f03ca79dd3e3ef4ea1ae30 2145 50 0x61ff7f25721d6206041c59a788316b09e05135a2aad94d539c65daa68b302cc2 2147 51 0x5dbfe346cbd0d61b9a3b5c42ec0518d3ae81cabcc32245060d7b0cd982b8d071 2149 52 0x4b6595e8501e9ec3e75f46107d2fd76511764efca179f69196eb45c0aa6fade3 2151 53 0x72d17a5aa7bd8a2540aa9b02d9605f2a714f44abfb4c35d518b7abc39b477870 2153 54 0x658d8c134bac37729ec40d27d50b637201abbf1ab4157316358953548c49cf22 2155 55 0x36ac53b9118581ace574d5a08f9647e6a916f92dda684a4dbc405e2646b0243f 2157 56 0x1917a98f387d1e323e84a0f02d53307b1dd949e1a27b0de14514f89d9c0ef4b6 2159 57 0x21573434fde7ce56e8777c79539479441942dba535ade8ecb77763f7eb05d797 2161 58 0x0e0bf482dc40884719bea5503422b603f3a8edb582f52838caa6eaab6eeac7ef 2163 59 0x3b0471eb53bd83e14fbc13928fe1691820349a963be8f7e9815848a53d03f5eb 2165 60 0x1e92cb067b24a729c42d3abb7a1179c577970f0ab3e6b0ce8d66c5b8f7001262 2167 61 0x74ea885c1ebed6f74964262402432ef184c42884fceb2f8dba3a9d67a1344dd7 2169 62 0x433ebce2ce9b0dc314425cfc2b234614d3c34f2c9da9fff4fdddd1ce242d035b 2171 63 0x33ac69e6be858dde7b83a9ff6f11de443128b39cec6e410e8d3b570e405ff896 2173 64 0x0dab71e2ae94e6530a501ed8cf3df26731dd1d41cd81578341e12dca3cb71aa3 2175 65 0x537f58d52d18ce5b1d5a6bd3a420e796e64173491ad43dd4d1083a7dcc7dd201 2177 66 0x49c2f6afa93fdcc4e0f8128a8b06da4c75049be14edf3e103821ab604c60f8ae 2179 67 0x10a333eabd6135aeaa3f5f5f7e73d102e4fd7e4bf0902fc55b00da235fa1ad08 2181 68 0x0f5c86044bf6032f5102e601f2a0f73c7bce9384bedd120f3e72d78484179d9c 2182 69 0x01 2184 G.4.1.3. Coefficients of w(x) 2186 0 0x3da24d42421264f30939ff00203880f2b017eb3fecf8933ae61e18df8c8ba116 2188 1 0x0457f20bc393cdc9a66848ce174e2fa41d77e6dbae05a317a1fb6e3ae78760f8 2190 2 0x7f608a2285c480d5c9592c435431fae94695beef79d770bb6d029c1d10a53295 2192 3 0x3832accc520a485100a0a1695792465142a5572bed1b2e50e1f8f662ac7289bb 2194 4 0x2df1b0559e31b328eb34beedd5e537c3f4d7b9befb0749f75d6d0d866d26fbaa 2196 5 0x25396820381d04015a9f655ddd41c74303ded05d54a7750e2f58006659adda28 2198 6 0x6fa070a70ca2bc6d4d0795fb28d4990b2cc80cd72d48b603a8ac8c8268bef6a6 2200 7 0x27f488578357388b20fbc7503328e1d10de602b082b3c7b8ceb33c29fea7a0d2 2202 8 0x15776851a7cabcfe84c632118306915c0c15c75068a47021968c7438d46076e6 2204 9 0x101565b08a9af015c172fb194b940a4df25c4fb1d85f72d153efc79131d45e8f 2206 10 0x196b0ffbf92f3229fea1dac0d74591b905ccaab6b83f905ee813ee8449f8a62c 2208 11 0x01f55784691719f765f04ee9051ec95d5deb42ae45405a9d87833855a6d95a94 2210 12 0x628858f79cca86305739d084d365d5a9e56e51a4485d253ae3f2e4a379fa8aff 2212 13 0x4a842dcd943a80d1e6e1dab3622a8c4d390da1592d1e56d1c14c4d3f72dd01a5 2214 14 0x0f3bfc9cb17a1125f94766a4097d0f1018963bc11cb7bc0c7a1d94d65e282477 2216 15 0x1c4bd70488c4882846500691fa7543b7ef694446d9c3e3b4707ea2c99383e53c 2218 16 0x2d7017e47b24b89b0528932c4ade43f09091b91db0072e6ebdc5e777cb215e35 2220 17 0x781d69243b6c86f59416f91f7decaca93eab9cdc36a184191810c56ed85e0fdc 2222 18 0x5f20526f4177357da40a18da054731d442ad2a5a4727322ba8ed10d32eca24fb 2224 19 0x33e4cab64ed8a00d8012104fe8f928e6173c428eff95bbbe569ea46126a4f3cd 2226 20 0x050555b6f07e308d33776922b6566829d122e19b25b7bbacbb0a4b1a7dc40192 2228 21 0x533fa4bf1e2a2aae2f979065fdbb5b667ede2f85543fddbba146aa3a4ef2d281 2229 22 0x5a742cac1952010fc5aba200a635a7bed3ef868194f45b5a6a2647d6d6b289d2 2231 23 0x01 2233 G.4.2. Dual Isogeny Parameters 2235 G.4.2.1. Coefficients of u'(x) 2237 0 0x0f0eddb584a20aaac8f1419efdd02a5cca77b21e4cfae78c49b5127d98bc5882 2239 1 0x7115e60d44a58630417df33dd45b8a546fa00b79fea3b2bdc449694bade87c0a 2241 2 0x0b3f3a6f3c445c7dc1f91121275414e88c32ff3f367ba0edad4d75b7e7b94b65 2243 3 0x1eb31bb333d7048b87f2b3d4ec76d69035927b41c30274368649c87c52e1ab30 2245 4 0x552c886c2044153e280832264066cce2a7da1127dc9720e2a380e9d37049ac64 2247 5 0x4504f27908db2e1f5840b74ae42445298755d9493141f5417c02f04d47797dda 2249 6 0x082c242cce1eb19698a4fa30b5affe64e5051c04ae8b52cb68d89ee85222e628 2251 7 0x480473406add76cf1d77661b3ff506c038d9cdd5ad6e1ea41969430bb876d223 2253 8 0x25f47bb506fba80c79d1763365fa9076d4c4cb6644f73ed37918074397e88588 2255 9 0x10f13ed36eab593fa20817f6bb70cac292e18d300498f6642e35cbdf772f0855 2257 10 0x7d28329d695fb3305620f83a58df1531e89a43c7b3151d16f3b60a8246c36ade 2259 11 0x02c5ec8c42b16dc6409bdd2c7b4ffe9d65d7209e886badbd5f865dec35e4ab4a 2261 12 0x7f4f33cd50255537e6cde15a4a327a5790c37e081802654b56c956434354e133 2263 13 0x7d30431a121d9240c761998cf83d228237e80c3ef5c7191ec9617208e0ab8cec 2265 14 0x4d2a7d6609610c1deed56425a4615b92f70a507e1079b2681d96a2b874cf0630 2267 15 0x74676df60a9906901d1dc316c639ff6ae0fcdb02b5571d4b83fc2eedcd2936a8 2269 16 0x22f8212219aca01410f06eb234ed53bd5b8fbe7c08652b8002bcd1ea3cdae387 2271 17 0x7edb04449565d7c566b934a87fadade5515f23bda1ce25daa19fff0c6a5ccc2f 2273 18 0x106ef71aa3aa34e8ecf4c07a67d03f0949d7d015ef2c1e32eb698dd3bec5a18c 2275 19 0x0017913eb705db126ac3172447bcd811a62744d505ad0eea94cfcfdde5ca7428 2276 20 0x2cc793e6d3b592dcf5472057a991ff1a5ab43b4680bb34c0f5faffc5307827c1 2278 21 0x6dafcc0b16f98300cddb5e0a7d7ff04a0e73ca558c54461781d5a5ccb1ea0122 2280 22 0x7e418891cf222c021b0ae5f5232b9c0dc8270d4925a13174a0f0ac5e7a4c8045 2282 23 0x76553bd26fecb019ead31142684789fea7754c2dc9ab9197c623f45d60749058 2284 24 0x693efb3f81086043656d81840902b6f3a9a4b0e8f2a5a5edf5ce1c7f50a3898e 2286 25 0x46c630eac2b86d36f18a061882b756917718a359f44752a5caf41be506788921 2288 26 0x01dcfa01773628753bc6f448ac11be8a3bffa0011b9284967629b827e064f614 2290 27 0x08430b5b97d49b0938d1f66ecb9d2043025c6eec624f8f02042b9621b2b5cb19 2292 28 0x66f66a6669272d47d3ec1efea36ee01d4a54ed50e9ec84475f668a5a9850f9be 2294 29 0x539128823b5ef3e87e901ab22f06d518a9bad15f5d375b49fe1e893ab38b1345 2296 30 0x2bd01c49d6fff22c213a8688924c10bf29269388a69a08d7f326695b3c213931 2298 31 0x3f7bea1baeccea3980201dc40d67c26db0e3b15b5a19b6cdac6de477aa717ac1 2300 32 0x6e0a72d94867807f7150fcb1233062f911b46e2ad11a3eac3c6c4c91e0f4a3fa 2302 33 0x5963f3cc262253f56fc103e50217e7e5b823ae8e1617f9e11f4c9c595fbb5bf6 2304 34 0x41440b6fe787777bc7b63afac9f4a38ddadcebc3d72f8fc73835247ba05f3a1d 2306 35 0x66d185401c1d2d0b84fcf6758a6a985bf9695651271c08f4b69ce89175fb7b34 2308 36 0x2673fb8c65bc4fe41905381093429a2601c46a309c03077ca229bac7d6ccf239 2310 37 0x1ce4d895ee601918a080de353633c82b75a3f61e8247763767d146554dd2f862 2312 38 0x18efa6c72fa908347547a89028a44f79f22542baa588601f2b3ed25a5e56d27c 2314 39 0x53de362e2f8ff220f8921620a71e8faa1aa57f8886fcbb6808fa3a5560570543 2316 40 0x0dc29a73b97f08aa8774911474e651130ed364e8d8cffd4a80dee633aacecc47 2318 41 0x4e7eb8584ae4de525389d1e9300fc4480b3d9c8a5a45ecfbe33311029d8f6b99 2320 42 0x6c3cba4aa9229550fa82e1cfaee4b02f2c0cb86f79e0d412b8e32b00b7959d80 2322 43 0x5a9d104ae585b94af68eeb16b1349776b601f97b7ce716701645b1a75b68dcf3 2323 44 0x754e014b5e87af035b3d5fe6fb49f4631e32549f6341c6693c5172a6388e273e 2325 45 0x6710d8265118e22eaceba09566c86f642ab42da58c435083a353eaa12d866c39 2327 46 0x6e88ac659ce146c369f8b24c3a49f8dca547827250cf7963a455851cfc4f8d22 2329 47 0x0971eb5f253356cd1fde9fb21f4a4902aa5b8d804a2b57ba775dc130181ae2e8 2331 G.4.2.2. Coefficients of v'(x) 2333 0 0x043c9b67cc5b16e167b55f190db61e44d48d813a7112910f10e3fd8da85d61d3 2335 1 0x72046db07e0e7882ff3f0f38b54b45ca84153be47a7fd1dd8f6402e17c47966f 2337 2 0x1593d97b65a070b6b3f879fe3dc4d1ef03c0e781c997111d5c1748f956f1ffc0 2339 3 0x54e5fec076b8779338432bdc5a449e36823a0a7c905fd37f232330b026a143a0 2341 4 0x46328dd9bc336e0873abd453db472468393333fbf2010c6ac283933216e98038 2343 5 0x25d0c64de1dfe1c6d5f5f2d98ab637d8b39bcf0d886a23dabac18c80d7eb03ce 2345 6 0x3a175c46b2cd8e2b313dde2d5f3097b78114a6295f283cf58a33844b0c8d8b34 2347 7 0x5cf4e6f745bdd61181a7d1b4db31dc4c30c84957f63cdf163bee5e466a7a8d38 2349 8 0x639071c39b723eea51cfd870478331d60396b31f39a593ebdd9b1eb543875283 2351 9 0x7ea8f895dcd85fc6cb2b58793789bd9246e62fa7a8c7116936876f4d8dff869b 2353 10 0x503818acb535bcaacf8ad44a83c213a9ce83af7c937dc9b3e5b6efedc0a7428c 2355 11 0x0e815373920ec3cbf3f8cae20d4389d367dc4398e01691244af90edc3e6d42b8 2357 12 0x7e4b23e1e0b739087f77910cc635a92a3dc184a791400cbceae056c19c853815 2359 13 0x145322201db4b5ec0a643229e07c0ab7c36e4274745689be2c19cfa8a702129d 2361 14 0x0fde79514935d9b40f52e33429621a200acc092f6e5dec14b49e73f2f59c780d 2363 15 0x37517ac5c04dc48145a9d6e14803b8ce9cb6a5d01c6f0ad1b04ff3353d02d815 2365 16 0x58ae96b8eefe9e80f24d3b886932fe3c27aaea810fa189c702f93987c8c97854 2367 17 0x6f6402c90fa379096d5f436035bebc9d29302126e9b117887abfa7d4b3c5709a 2369 18 0x01dbdf2b9ec09a8defeb485cc16ea98d0d45c5b9877ff16bd04c0110d2f64961 2370 19 0x53c51706af523ab5b32291de6c6b1ee7c5cbd0a5b317218f917b12ff38421452 2372 20 0x1b1051c7aec7d37a349208e3950b679d14e39f979db4fcd7b50d7d27dc918650 2374 21 0x1547e8d36262d5434cfb029cdd29385353124c3c35b1423c6cca1f87910b305b 2376 22 0x198efe984efc817835e28f704d41e4583a1e2398f7ce14045c4575d0445c6ce7 2378 23 0x492276dfe9588ee5cd9f553d990f377935d721822ecd0333ce2eb1d4324d539c 2380 24 0x77bad5319bacd5ed99e1905ce2ae89294efa7ee1f74314e4095c618a4e580c9b 2382 25 0x2cb3d532b8eac41c61b683f7b02feb9c2761f8b4286a54c3c4b60dd8081a312e 2384 26 0x37d189ea60443e2fee9b7ba8a34ed79ff3883dcefc06592836d2a9dd2ee3656e 2386 27 0x79a80f9a0e6b8ded17a3d6ccf71eb565e3704c3543b77d70bca854345e880aba 2388 28 0x47718530ef8e8c75f069acb2d9925c5537908e220b28c8a2859b856f46d5f8db 2390 29 0x7dc518f82b55a36b4fa084b05bf21e3efce481d278a9f5c6a49701e56dac01ec 2392 30 0x340a318dad4b8d348a0838659672792a0f00b7105881e6080a340f708a9c7f94 2394 31 0x55f04d9d8891636d4e9c808a1fa95ad0dae7a8492257b20448023aad3203278e 2396 32 0x39dc465d58259f9f70bb430d27e2f0ab384a550e1259655443e14bdecba85530 2398 33 0x757385464cff265379a1adfadfd6f6a03fa8a2278761d4889ab097eff4d1ac28 2400 34 0x4d575654dbe39778857f4e688cc657416ce524d54864ebe8995ba766efa7ca2b 2402 35 0x47adb6aecc1949f2dc9f01206cc23eb4a0c29585d475dd24dc463c5087809298 2404 36 0x30d39e8b0c451a8fcf3d2abab4b86ffa374265abbe77c5903db4c1be8cec7672 2406 37 0x28cf47b39112297f0daeaa621f8e777875adc26f35dec0ba475c2ee148562b41 2408 38 0x36199723cc59867e2e309fe9941cd33722c807bb2d0a06eeb41de93f1b93f2f5 2410 39 0x5cdeb1f2ee1c7d694bdd884cb1c5c22de206684e1cafb8d3adb9a33cb85e19a2 2412 40 0x0f6e6b3fc54c2d25871011b1499bb0ef015c6d0da802ae7eccf1d8c3fb73856c 2414 41 0x0c1422c98b672414344a9c05492b926f473f05033b9f85b8788b4bb9a080053c 2416 42 0x19a8527de35d4faacb00184e0423962247319703a815eecf355f143c2c18f17f 2417 43 0x7812dc3313e6cf093da4617f06062e8e8969d648dfe6b5c331bccd58eb428383 2419 44 0x61e537180c84c79e1fd2d4f9d386e1c4f0442247605b8d8904d122ee7ef9f7be 2421 45 0x544d8621d05540576cfc9b58a3dab19145332b88eb0b86f4c15567c37205adf9 2423 46 0x11be3ef96e6e07556356b51e2479436d9966b7b083892b390caec22a117aa48e 2425 47 0x205cda31289cf75ab0759c14c43cb30f7287969ea3dc0d5286a3853a4d403187 2427 48 0x048d8fc6934f4f0a99f0f2cc59010389e2a0b20d6909bfcf8d7d0249f360acdc 2429 49 0x42cecc6d9bdca6d382e97fcea46a79c3eda2853091a8f399a2252115bf9a1454 2431 50 0x0117d41b24f2f69cb3270b359c181607931f62c56d070bbd14dc9e3f9ab1432e 2433 51 0x7c51564c66f68e2ad4ce6ea0d68f920fafa375376709c606c88a0ed44207aa1e 2435 52 0x48f25191fc8ac7d9f21adf6df23b76ccbca9cb02b815acdbebfa3f4eddc71b34 2437 53 0x4fc21a62c4688de70e28ad3d5956633fc9833bc7be09dc7bc500b7fae1e1c9a8 2439 54 0x1f23f25be0912173c3ef98e1c9990205a69d0bf2303d201d27a5499247f06789 2441 55 0x3131495618a0ac4cb11a702f3f8bab66c4fa1066d0a741af3c92d5c246edd579 2443 56 0x0d93fe40faa53913638e497328a1b47603cb062c7afc9e96278603f29fd11fd4 2445 57 0x6b348bc59e984c91d696d1e3c3cfae44021f06f74798c787c355437fb696093d 2447 58 0x65af00e73043edcb479620c8b48098b89809d577a4071c8e33e8678829138b8a 2449 59 0x5e62ffb032b2ddb06591f86a46a18effd5d6ecf3f129bb2bacfd51a3739a98b6 2451 60 0x62c974ef3593fc86f7d78883b8727a2f7359a282cbc0196948e7a793e60ce1a1 2453 61 0x204d708e3f500aad64283f753e7d9bab976aa42a4ca1ce5e9d2264639e8b1110 2455 62 0x0a90f0059da81a012e9d0a756809fab2ce61cb45965d4d1513a06227783ee4ea 2457 63 0x39fa55971c9e833f61139c39e243d40869fd7e8a1417ee4e7719dd2dd242766f 2459 64 0x22677c1e659caa324f0c74a013921facf62d0d78f273563145cc1ddccfcc4421 2461 65 0x3468cf6df7e93f7ff1fe1dd7e180a89dec3ed4f72843b4ea8a8d780011a245b2 2463 66 0x68f75a0e2210f52a90704ed5f511918d1f6bcfcd26b462cc4975252369db6e9d 2464 67 0x6220c0699696e9bcab0fe3a80d437519bd2bdf3caef665e106b2dd47585ddd9f 2466 68 0x553ad47b129fb347992b576479b0a89f8d71f1196f83e5eaab5f533a1dd6f6d7 2468 69 0x239aef387e116ec8730fa15af053485ca707650d9f8917a75f22acf6213197df 2470 G.4.2.3. Coefficients of w'(x) 2472 0 0x6bd7f1fc5dd51b7d832848c180f019bcbdb101d4b3435230a79cc4f95c35e15e 2474 1 0x17413bb3ee505184a504e14419b8d7c8517a0d268f65b0d7f5b0ba68d6166dd0 2476 2 0x47f4471beed06e5e2b6d5569c20e30346bdba2921d9676603c58e55431572f90 2478 3 0x2af7eaafd04f6910a5b01cdb0c27dca09487f1cd1116b38db34563e7b0b414eb 2480 4 0x57f0a593459732eef11d2e2f7085bf9adf534879ba56f7afd17c4a40d3d3477b 2482 5 0x4da04e912f145c8d1e5957e0a9e44cca83e74345b38583b70840bdfdbd0288ed 2484 6 0x7cc9c3a51a3767d9d37c6652c349adc09bfe477d99f249a2a7bc803c1c5f39ed 2486 7 0x425d7e58b8adf87eebf445b424ba308ee7880228921651995a7eab548180ad49 2488 8 0x48156db5c99248234c09f43fedf509005943d3d5f5d7422621617467b06d314f 2490 9 0x0d837dbbd1af32d04e2699cb026399c1928472aa1a7f0a1d3afd24bc9923456a 2492 10 0x5b8806e0f924e67c1f207464a9d025758c078b43ddc0ea9afe9993641e5650be 2494 11 0x29c91284e5d14939a6c9bc848908bd9df1f8346c259bbd40f3ed65182f3a2f39 2496 12 0x25550b0f3bceef18a6bf4a46c45bf1b92f22a76d456bfdf19d07398c80b0f946 2498 13 0x495d289b1db16229d7d4630cb65d52500256547401f121a9b09fb8e82cf01953 2500 14 0x718c8c610ea7048a370eabfd9888c633ee31dd70f8bcc58361962bb08619963e 2502 15 0x55d8a5ceef588ab52a07fa6047d6045550a5c52c91cc8b6b82eeb033c8ca557d 2504 16 0x620b5a4974cc3395f96b2a0fa9e6454202ef2c00d82b0e6c534b3b1d20f9a572 2506 17 0x4991b763929b00241a1a9a68e00e90c5df087f90b3352c0f4d8094a51429524e 2508 18 0x18b6b49c5650fb82e36e25fd4eb6decfdd40b46c37425e6597c7444a1b6afb4e 2510 19 0x6868305b4f40654460aad63af3cb9151ab67c775eaac5e5df90d3aea58dee141 2511 20 0x16bc90219a36063a22889db810730a8b719c267d538cd28fa7c0d04f124c8580 2513 21 0x3628f9cf1fbe3eb559854e3b1c06a4cd6a26906b4e2d2e70616a493bba2dc574 2515 22 0x64abcc6759f1ce1ab57d41e17c2633f717064e35a7233a6682f8cf8e9538afec 2517 23 0x01 2519 Appendix H. Point Compression 2521 Point compression allows a shorter representation of affine points of 2522 an elliptic curve by exploiting algebraic relationships between the 2523 coordinate values based on the defining equation of the curve in 2524 question. Point decompression refers to the reverse process, where 2525 one tries and recover an affine point from its compressed 2526 representation and information on the domain parameters of the curve. 2527 Consequently, point compression followed by point decompression is 2528 the identity map. 2530 The description below makes use of an auxiliary function (the parity 2531 function), which we first define for prime fields GF(p), with p odd, 2532 and then extend to all fields GF(q), where q is an odd prime power. 2533 We assume each finite field to be unambiguously defined and known 2534 from context. 2536 Let y be a nonzero element of GF(q). If q:=p is an odd prime number, 2537 y and p-y can be uniquely represented as integers in the interval 2538 [1,p-1] and have odd sum p. Consequently, one can distinguish y from 2539 -y via the parity of this representation, i.e., via par(y):=y (mod 2540 2). If q:=p^m, where p is an odd prime number and where m>0, both y 2541 and -y can be uniquely represented as vectors of length m, with 2542 coefficients in GF(p) (see Appendix B.2). In this case, the leftmost 2543 nonzero coordinate values of y and -y are in the same position and 2544 have representations in [1,p-1] with different parity. As a result, 2545 one can distinguish y from -y via the parity of the representation of 2546 this coordinate value. This extends the definition of the parity 2547 function to any odd-size field GF(q), where one defines par(0):=0. 2549 H.1. Point Compression for Weierstrass Curves 2551 If P:=(X, Y) is an affine point of the Weierstrass curve W_{a,b} 2552 defined over the field GF(q), then so is -P:=(X, -Y). Since the 2553 defining equation Y^2=X^2+a*X+b has at most two solutions with fixed 2554 X-value, one can represent P by its X-coordinate and one bit of 2555 information that allows one to distinguish P from -P, i.e., one can 2556 represent P as the ordered pair compr(P):=(X, par(Y)). If P is a 2557 point of order two, one can uniquely represent P by its X-coordinate 2558 alone, since Y=0 and has fixed parity. Conversely, given the ordered 2559 pair (X, t), where X is an element of GF(q) and where t=0 or t=1, and 2560 the domain parameters of the curve W_{a,b}, one can use the defining 2561 equation of the curve to try and determine candidate values for the 2562 Y-coordinate given X, by solving the quadratic equation Y^2:=alpha, 2563 where alpha:=X^3+a*X+b. If alpha is not a square in GF(q), this 2564 equation does not have a solution in GF(q) and the ordered pair (X, 2565 t) does not correspond to a point of this curve. Otherwise, there 2566 are two solutions, viz. Y=sqrt(alpha) and -Y. If alpha is a nonzero 2567 element of GF(q), one can uniquely recover the Y-coordinate for which 2568 par(Y):=t and, thereby, the point P:=(X, Y). This is also the case 2569 if alpha=0 and t=0, in which case Y=0 and the point P has order two. 2570 However, if alpha=0 and t=1, the ordered pair (X, t) does not 2571 correspond to the outcome of the point compression function. 2573 We extend the definition of the point compression function to all 2574 points of the curve W_{a,b}, by associating the (non-affine) point at 2575 infinity O with any ordered pair compr(O):=(X,0), where X is any 2576 element of GF(q) for which alpha:=X^3+a*X+b is not a square in GF(q), 2577 and recover this point accordingly. In this case, the point at 2578 infinity O can be represented by any ordered pair (X,0) of elements 2579 of GF(q) for which X^3+a*X+b is not a square in GF(q). Note that 2580 this ordered pair does not satisfy the defining equation of the curve 2581 in question. An application may fix a specific suitable value of X 2582 or choose multiple such values and use this to encode additonal 2583 information. Further details are out of scope. 2585 H.2. Point Compression for Montgomery Curves 2587 If P:=(u, v) is an affine point of the Montgomery curve M_{A,B} 2588 defined over the field GF(q), then so is -P:=(u, -v). Since the 2589 defining equation B*v^2=u^3+A*u^2+u has at most two solutions with 2590 fixed u-value, one can represent P by its u-coordinate and one bit of 2591 information that allows one to distinguish P from -P, i.e., one can 2592 represent P as the ordered pair compr(P):=(u, par(v)). If P is a 2593 point of order two, one can uniquely represent P by its u-coordinate 2594 alone, since v=0 and has fixed parity. Conversely, given the ordered 2595 pair (u, t), where u is an element of GF(q) and where t=0 or t=1, and 2596 the domain parameters of the curve M_{A,B}, one can use the defining 2597 equation of the curve to try and determine candidate values for the 2598 v-coordinate given u, by solving the quadratic equation v^2:=alpha, 2599 where alpha:=(u^3+A*u^2+u)/B. If alpha is not a square in GF(q), 2600 this equation does not have a solution in GF(q) and the ordered pair 2601 (u, t) does not correspond to a point of this curve. Otherwise, 2602 there are two solutions, viz. v=sqrt(alpha) and -v. If alpha is a 2603 nonzero element of GF(q), one can uniquely recover the v-coordinate 2604 for which par(v):=t and, thereby, the affine point P:=(u, v). This 2605 is also the case if alpha=0 and t=0, in which case v=0 and the point 2606 P has order two. However, if alpha=0 and t=1, the ordered pair (u, 2607 t) does not correspond to the outcome of the point compression 2608 function. 2610 We extend the definition of the point compression function to all 2611 points of the curve M_{A,B}, by associating the (non-affine) point at 2612 infinity O with the ordered pair compr(O):=(0,1) and recover this 2613 point accordingly. (Note that this corresponds to the case alpha=0 2614 and t=1 above.) The point at infinity O can be represented by the 2615 ordered pair (0, 1) of elements of GF(q). Note that this ordered 2616 pair does not satisfy the defining equation of the curve in question. 2618 H.3. Point Compression for Twisted Edwards Curves 2620 If P:=(x, y) is an affine point of the twisted Edwards curve E_{a,d} 2621 defined over the field GF(q), then so is -P:=(-x, y). Since the 2622 defining equation a*x^2+y^2=1+d*x^2*y^2 has at most two solutions 2623 with fixed y-value, one can represent P by its y-coordinate and one 2624 bit of information that allows one to distinguish P from -P, i.e., 2625 one can represent P as the ordered pair compr(P):=(par(x), y). If P 2626 is a point of order one or two, one can uniquely represent P by its 2627 y-coordinate alone, since x=0 and has fixed parity. Conversely, 2628 given the ordered pair (t, y), where y is an element of GF(q) and 2629 where t=0 or t=1, and the domain parameters of the curve E_{a,d}, one 2630 can use the defining equation of the curve to try and determine 2631 candidate values for the x-coordinate given y, by solving the 2632 quadratic equation x^2:=alpha, where alpha:=(1-y^2)/(a-d*y^2). 2633 (Here, observe that the denominator is nonzero for any point of 2634 E_{a,d}.) If alpha is not a square in GF(q), this equation does not 2635 have a solution in GF(q) and the ordered pair (t, y) does not 2636 correspond to a point of this curve. Otherwise, there are two 2637 solutions, viz. x=sqrt(alpha) and -x. If alpha is a nonzero element 2638 of GF(q), one can uniquely recover the x-coordinate for which 2639 par(x):=t and, thereby, the affine point P:=(x, y). This is also the 2640 case if alpha=0 and t=0, in which case x=0 and the point P has order 2641 one or two. However, if alpha=0 and t=1, the ordered pair (t, y) 2642 does not correspond to the outcome of the point compression function. 2644 Note that the point compression function is defined for all points of 2645 the twisted Edwards curve E_{a,d}. Here, the identity element 2646 O:=(0,1) is associated with the compressed point compr(O):=(0,1). 2647 (Note that this corresponds to the case alpha=0 and t=0 above.) 2649 We extend the definition of the compression function further, to also 2650 include a special marker element 'btm', by associating this marker 2651 element with the ordered pair compr(btm):=(1,1) and recover this 2652 marker element accordingly. (Note that this corresponds to the case 2653 alpha=0 and t=1 above.) The marker element 'btm' can be represented 2654 by the ordered pair (1,1) of elements of GF(q). Note that this 2655 ordered pair does not satisfy the defining equation of the curve in 2656 question. 2658 Appendix I. Data Conversions 2660 The string over some alphabet S consisting of the symbols x_{l-1}, 2661 x_{l-2}, ..., x_1, x_0 (each in S), in this order, is denoted by 2662 str(x_{l-1}, x_{l-2}, ..., x_1, x_0). The length of this string 2663 (over S) is the number of symbols it contains (here: l). The empty 2664 string is the (unique) string of length l=0. 2666 The right-concatenation of two strings X and Y (defined over the same 2667 alphabet) is the string Z consisting of the symbols of X (in the same 2668 order) followed by the symbols of Y (in the same order). The length 2669 of the resulting string Z is the sum of the lengths of X and Y. This 2670 string operation is denoted by Z:=X||Y. The string X is called a 2671 prefix of Z; the string Y a postfix. The t-prefix of a string Z of 2672 length l is its unique prefix X of length t; the t-postfix its unique 2673 postfix Y of length t (where in both cases t is an integer in the 2674 interval [0,l]). One can define these notions as well if t is 2675 outside the interval [0,l] by stipulating that a t-prefix or 2676 t-postfix is the empty string if t is negative and that it is the 2677 entire string Z if t is larger than l. Sometimes, a t-prefix of a 2678 string Z is denoted by trunc-left(Z,t); a t-postfix by trunc- 2679 right(Z,t). A string X is called a substring of Z if it is a prefix 2680 of some postfix of Z. The string resulting from prepending the 2681 string Y with X is the string X||Y. 2683 An octet is an integer in the interval [0,256). An octet string is a 2684 string, where the alphabet is the set of all octets. A binary string 2685 (or bit string, for short) is a string, where the alphabet is the set 2686 {0,1}. Note that the length of a string is defined in terms of the 2687 underlying alphabet, as are the operations in the previous paragraph. 2689 I.1. Conversion between Bit Strings and Integers (BS2I, I2BS) 2691 There is a 1-1 correspondence between bit strings of length l and 2692 integers in the interval [0, 2^l), where the bit string 2693 X:=str(x_{l-1}, x_{l-2}, ..., x_1, x_0) corresponds to the integer 2694 x:=x_{l-1}*2^{l-1} + x_{l-2}*2^{l-2} + ... + x_1*2 + x_0*1. (If l=0, 2695 the empty bit string corresponds to the integer zero.) Note that 2696 while the mapping from bit strings to integers is uniquely defined, 2697 the inverse mapping from integers to bit strings is not, since any 2698 non-negative integer smaller than 2^t can be represented as a bit 2699 string of length at least t (due to leading zero coefficients in base 2700 2 representation). The latter representation is called tight if the 2701 bit string representation has minimal length. This defines the 2702 mapping BS2I from bit strings to integers and the mapping I2BS(x,l) 2703 from non-negative integers smaller than 2^l to bit strings of length 2704 l. 2706 I.2. Conversion between Octet Strings and Integers (OS2I, I2OS) 2708 There is a 1-1 correspondence between octet strings of length l and 2709 integers in the interval [0, 256^l), where the octet string 2710 X:=str(X_{l-1}, X_{l-2}, ..., X_1, X_0) corresponds to the integer 2711 x:=X_{l-1}*256^{l-1} + X^{l-2}*256^{l-2} + ... + X_1*256 + X_0*1. 2712 (If l=0, the empty string corresponds to the integer zero.) Note 2713 that while the mapping from octet strings to integers is uniquely 2714 defined, the inverse mapping from integers to octet strings is not, 2715 since any non-negative integer smaller than 256^t can be represented 2716 as an octet string of length at least t (due to leading zero 2717 coefficients in base 256 representation). The latter representation 2718 is called tight if the octet string representation has minimal 2719 length. This defines the mapping OS2I from octet strings to integers 2720 and the mapping I2OS(x,l) from non-negative integers smaller than 2721 256^l to octet strings of length l. 2723 I.3. Conversion between Octet Strings and Bit Strings (OS2BS, BS2OS) 2725 There is a 1-1 correspondence between octet strings of length l and 2726 bit strings of length 8*l, where the octet string X:=str(X_{l-1}, 2727 X_{l-2}, ..., X_1, X_0) corresponds to the right-concatenation of the 2728 8-bit strings x_{l-1}, x_{l-2}, ..., x_1, x_0, where each octet X_i 2729 corresponds to the 8-bit string x_i according to the mapping of 2730 Appendix I.1 above. Note that the mapping from octet strings to bit 2731 strings is uniquely defined and so is the inverse mapping from bit 2732 strings to octet strings, if one prepends each bit string with the 2733 smallest number of 0 bits so as to result in a bit string of length 2734 divisible by eight (i.e., one uses pre-padding). This defines the 2735 mapping OS2BS from octet strings to bit strings and the corresponding 2736 mapping BS2OS from bit strings to octet strings. 2738 I.4. Conversion between Field Elements and Octet Strings (FE2OS, OS2FE) 2740 There is a 1-1 correspondence between elements of the fixed finite 2741 field GF(q), where q:=p^m, where p is a prime number and where m>0, 2742 and vectors of length m, with coefficients in GF(p), where each 2743 element x of GF(q) is a vector (x_{m-1}, x_{m-2}, ..., x_1, x_0) 2744 according to the conventions of Appendix B.2. In this case, this 2745 field element can be uniquely represented by the right-concatenation 2746 of the octet strings X_{m-1}, X_{m-2}, ..., X_1, X_0, where each 2747 octet string X_i corresponds to the integer x_i in the interval 2748 [0,p-1] according to the mapping of Appendix I.2 above. Note that 2749 both the mapping from field elements to octet strings and the inverse 2750 mapping from octet strings to field elements are only uniquely 2751 defined if each octet string X_i has the same fixed size (e.g., the 2752 smallest integer l so that 256^l >= p) and if all integers are 2753 reduced modulo p. If so, the latter representation is called tight 2754 if l is minimal so that 256^l >= p. This defines the mapping 2755 FE2OS(x,l) from field elements to octet strings and the mapping 2756 OS2FE(X,l) from octet strings to field elements, where the underlying 2757 field is implicit and assumed to be known from context. In this 2758 case, the octet string has length l*m. (Observe that with tight 2759 representations, the parameter l is uniquely defined by the 2760 characteristic p of the field GF(q) in question.) 2762 I.5. Conversion between Elements of Z mod n and Octet Strings (ZnE2OS, 2763 OS2ZnE) 2765 There is a 1-1 correspondence between elements of the set Z_n of 2766 integers modulo n and integers in the interval [0,n), where each 2767 element x of Z_n is uniquely represented by the integer x mod n. In 2768 this case, x mod n can be uniquely represented by the octet string X 2769 according to the mapping of Appendix I.2 above. Note that both the 2770 mapping from elements of Z_n to octet strings and the inverse mapping 2771 from octet strings to elements of Z_n are only uniquely defined if 2772 the octet string has a fixed size (e.g., the smallest integer l so 2773 that 256^l >= n) and if all integers are first reduced modulo n. If 2774 so, the latter representation is called tight if l is minimal so that 2775 256^l >= n. This defines the mapping ZnE2OS(x,l) from elements of 2776 Z_n to octet strings and the mapping OS2ZnE(X,l) from octet strings 2777 to elements of Z_n, where the underlying modulus n is implicit and 2778 assumed to be known from context. In this case, the octet string has 2779 length l. (Observe that with tight representations, the parameter l 2780 is uniquely defined by the parameter n in question.) 2782 Note that if n is a prime number p, the conversions ZnE2OS and FE2OS 2783 are consistent, as are OS2ZnE and OS2FE. This is, however, no longer 2784 the case if n is a strict prime power. 2786 The conversion rules for composite n values may be useful, e.g., when 2787 encoding RSA parameters (or elements of any other non-prime size set 2788 Z_n, for that matter). 2790 I.6. Ordering Conventions 2792 One can consider various representation functions, depending on bit- 2793 ordering and octet-ordering conventions. 2795 The description below makes use of an auxiliary function (the 2796 reversion function), which we define both for bit strings and octet 2797 strings. For a bit string [octet string] X:=str(x_{l-1}, x_{l-2}, 2798 ..., x_1, x_0), its reverse is the bit string [octet string] 2799 X':=rev(X):=str(x_0, x_1, ..., x_{l-2}, x_{l-1}). 2801 We now describe representations in most-significant-bit first (msb) 2802 or least-significant-bit first (lsb) order and those in most- 2803 significant-byte first (MSB) or least-significant-byte first (LSB) 2804 order. 2806 One distinguishes the following octet-string representations of 2807 integers and field elements: 2809 1. MSB, msb: represent field elements and integers as above, 2810 yielding the octet string str(X_{l-1}, X_{l-2}, ..., X_1, X_0). 2812 2. MSB, lsb: reverse the bit-order of each octet, viewed as 8-bit 2813 string, yielding the octet string str((rev(X_{l-1}), 2814 rev(X_{l-2}), ..., rev(X_1), rev(X_0)). 2816 3. LSB, lsb: reverse the octet string and bit-order of each octet, 2817 yielding the octet string str(rev(X_{0}), rev(X_{1}), ..., 2818 rev(X_{l-2}), rev(X_{l-1})). 2820 4. LSB, msb: reverse the octet string, yielding the octet string 2821 str(X_{0}, X_{1}, ..., X_{l-2}, X_{l-1}). 2823 Thus, the 2-octet string "07e3" represents the integer 2019 (=0x07e3) 2824 in MSB/msb order, the integer 57,543 (0xe0c7) in MSB/lsb order, the 2825 integer 51,168 (0xc7e0) in LSB/lsb order, and the integer 58,119 2826 (=0xe307) in LSB/msb order. 2828 Note that, with the above data conversions, there is still some 2829 ambiguity as to how to represent an integer or a field element as a 2830 bit string or octet string (due to leading zeros). However, tight 2831 representations (as defined above) are non-ambiguous. (Note, in 2832 particular, that tightness implies that elements of GF(q) are always 2833 uniquely represented.) 2835 Note that elements of a prime field GF(p), where p is a 255-bit prime 2836 number, have a tight representation as a 32-byte string, where a 2837 fixed bit position is always set to zero. (This is the leftmost bit 2838 position of this octet string if one follows the MSB/msb 2839 representation conventions.) This allows the parity bit of a 2840 compressed point (see Appendix H) to be encoded in this bit position 2841 and, thereby, allows a compressed point and a field element of GF(p) 2842 to be represented by an octet string of the same length. This is 2843 called the squeezed point representation. Obviously, other 2844 representations (e.g., those of elements of Z_n) may also have fixed 2845 bit values in certain positions, which can be used to squeeze-in 2846 additional information. Further details are out of scope. 2848 Appendix J. Representation Examples Curve25519 Family Members 2850 We present some examples of computations using the curves introduced 2851 in this document. In each case, we indicate the values of P, k*P, 2852 and (k+1)*P, where P is a fixed multiple (here: 2019) of the base 2853 point of the curve in question and where the private key k is the 2854 integer 2856 k 45467544759954639344191351164156560595299236761702065033670739677 2857 691372543056 2859 (=0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3 2860 c08d5abd 15e29c50). 2862 J.1. Example with Curve25519 2864 Pm=(u, v), k*Pm=(u1, v1), and (k+1)*Pm=(u2, v2) with Curve25519: 2866 u 53025657538808013645618620393754461319535915376830819974982289332 2867 088255623750 2869 (=0x753b7566 df35d574 4734142c 9abf931c ea290160 aa75853c 2870 7f972467 b7f13246). 2872 v 53327798092436462013048370302019946300826511459161905709144645521 2873 233690313086 2875 (=0x75e676ce deee3b3c 12942357 22f1d884 ac06de07 330fb07b 2876 ae35ca26 df75417e). 2878 u1 42039618818474335439333192910143029294450651736166602435248528442 2879 691717668056 2881 (=0x5cf194be f0bdd6d6 be58e18a 8f16740a ec25f4b0 67f7980a 2882 23bb6468 88bb9cd8). 2884 v1 76981661982917351630937517222412729130882368858134322156485762195 2885 67913357634 2887 (=0x110501f6 1dff511e d6c4e9b9 bfd5acbe 8bf043b8 c3e381dd 2888 f5771306 479ad142). 2890 u2 34175116482377882355440137752573651838273760818624557524643126101 2891 82464621878 2892 (=0x078e3e38 41c3e0d0 373e5454 ecffae33 2798b10a 55c72117 2893 62629f97 f1394d36). 2895 v2 43046985853631671610553834968785204191967171967937842531656254539 2896 962663994648 2898 (=0x5f2bbb06 f7ec5953 2c2a1a62 21124585 1d2682e0 cc37307e 2899 fbc17f7f 7fda8518). 2901 As suggested in Appendix C.2, the v-coordinate of k*Pm can be 2902 indirectly computed from the u-coordinates of Pm, k*Pm, and (k+1)*Pm, 2903 and the v-coordinate of Pm, which allows computation of the entire 2904 point k*Pm (and not just its u-coordinate) if k*Pm is computed using 2905 the Montgomery ladder (as, e.g., [RFC7748] recommends), since that 2906 algorithm computes both u1 and u2 and the v-coordinate of the point 2907 Pm may be available from context. 2909 The representation of k and the compressed representations of Pm and 2910 k*Pm in tight LSB/msb-order are given by 2912 repr(k) 0x509ce215 bd5a8dc0 c3328c77 5dc6f59c 4d4915f9 e4bf5d0d 2913 c2e583cd e6b78564 2915 repr(Pm) 0x4632f1b7 6724977f 3c8575aa 600129ea 1c93bf9a 2c143447 2916 74d535df 66753b75; 2918 repr(k*Pm) 0xd89cbb88 6864bb23 0a98f767 b0f425ec 0a74168f 8ae158be 2919 d6d6bdf0 be94f15c, 2921 where the leftmost bit of the rightmost octet indicates the parity of 2922 the v-coordinate of the point of Curve25519 in question (which, in 2923 this case, are both zero, since v and v1 are even). See Appendix H.2 2924 and Appendix I for further detail on (squeezed) point compression. 2926 The scalar representation and (squeezed) point representation 2927 illustrated above are consistent with the representations specified 2928 in [RFC7748], except that in [RFC7748] only an affine point's 2929 u-coordinate is represented (i.e., the v-coordinate of any point is 2930 always implicitly assumed to have an even value) and that the 2931 representation of the point at infinity is not specified. Another 2932 difference is that [RFC7748] allows non-unique representations of 2933 some elements of GF(p), whereas our representation conventions do not 2934 (since tight). 2936 A randomized representation (t1, t2) of the point k*Pm in tight LSB/ 2937 msb order is given by 2938 t1 409531317901122685707535715924445398426503483189854716584 2939 37762538294289253464 2941 (=0x5844b232 8c4586dc 62f593c5 599c2a8c e61ba893 bb052de6 2942 77510a42 b3a68a5a) 2944 t2 451856098332889407421278004628150814449259902023388533929 2945 08848927625430980881 2947 (=0x11598452 e65138dc ce948d7e d8f46a18 b640722c 8e170957 2948 751b7729 1b26e663), 2950 where this representation is defined in Appendix K.5 and uses the 2951 mapping of Appendix K.3.2 with the default square root function. 2953 J.2. Example with Edwards25519 2955 Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Edwards25519: 2957 x 25301662348702136092602268236183361085863932475593120475382959053 2958 365387223252 2960 (=0x37f03bc0 1070ed12 d3218f8b ba1abb74 fd6b94eb 62033d09 2961 83851e21 d6a460d4). 2963 y 54434749145175762798550436656748568411099702168121592090608501578 2964 942019473360 2966 (=0x7858f9e7 6774ed8e 23d614d2 36715fc7 56813b02 9aa13c18 2967 960705c5 b3a30fd0). 2969 x1 42966967796585460733861724865699548279978730460766025087444502812 2970 416557284873 2972 (=0x5efe7124 465b5bdb b364bb3e e4f106e2 18d59b36 48f4fe83 2973 c11afc91 785d7e09). 2975 y1 46006463385134057167371782068441558951541960707376246310705917936 2976 352255317084 2978 (=0x65b6bc49 985badaf bc5fdd96 fb189502 35d5effd 540b439d 2979 60508827 80bc945c). 2981 x2 42629294840915692510487991904657367226900127896202625319538173473 2982 104931719808 2984 (=0x5e3f536a 3be2364a 1fa775a3 5f8f65ae 93f4a89d 81a04a2e 2985 87783748 00120a80). 2987 y2 29739282897206659585364020239089516293417836047563355347155817358 2988 737209129078 2990 (=0x41bfd66e 64bdd801 c581a720 f48172a8 187445fa 350924a2 2991 c92c791e 38d57876). 2993 The representation of k and the compressed representations of Pe and 2994 k*Pe in tight LSB/lsb-order are given by 2996 repr(k) =0x0a3947a8 bd5ab103 c34c31ee ba63af39 b292a89f 27fdbab0 2997 43a7c1b3 67eda126; 2999 repr(Pe) =0x0bf0c5cd a3a0e069 183c8559 40dc816a e3fa8e6c 4b286bc4 3000 71b72ee6 e79f1a1e; 3002 repr(k*Pe) =0x3a293d01 e4110a06 b9c2d02a bff7abac 40a918df 69bbfa3d 3003 f5b5da19 923d6da7, 3005 where the rightmost bit of the rightmost octet indicates the parity 3006 of the x-coordinate of the point of Edwards25519 in question (which, 3007 in this case, are zero and one, respectively, since x is even and x1 3008 is odd). See Appendix H.3 and Appendix I for further detail on 3009 (squeezed) point compression. 3011 The scalar representation and (squeezed) point representation 3012 illustrated above are fully consistent with the representations 3013 specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032] 3014 requires unique representations of all elements of GF(p). 3016 A randomized representation (t1, t2) of the point k*Pe in tight LSB/ 3017 lsb order is given by 3019 t1 577913017083163641949634219017190182170288776648725395935 3020 97750427519399254040 3022 (=0x181a32c5 10e06dbc ea321882 f3519055 535e289e 8faac654 3023 82e26f61 aded23fe) 3025 t2 454881407940919718426608573125377401686255068210624245884 3026 05479716220480287974 3028 (=0x672e36c5 ae353073 cdfac343 e8297b05 1b010d0f 5b1016db 3029 dd4baf54 28068926), 3031 where this representation is defined in Appendix K.5 and uses the 3032 mapping of Appendix K.3.3 with the default square root function and 3033 underlying isomorphic mapping between Edwards25519 and Curve25519 of 3034 Appendix E.2. 3036 J.3. Example with Wei25519 3038 Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519: 3040 X 14428294459702615171094958724191825368445920488283965295163094662 3041 783879239338 3043 (=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7 3044 2a41cf12 629e56aa). 3046 Y 53327798092436462013048370302019946300826511459161905709144645521 3047 233690313086 3049 (=0x75e676ce deee3b3c 12942357 22f1d884 ac06de07 330fb07b 3050 ae35ca26 df75417e). 3052 X1 34422557393689369648095312405803933433606568476197477554293337733 3053 87341283644 3055 (=0x079c3f69 9b688181 69038c35 39c11eb5 96d09f5b 12a242b4 3056 ce660f13 3368c13c). 3058 Y1 76981661982917351630937517222412729130882368858134322156485762195 3059 67913357634 3061 (=0x110501f6 1dff511e d6c4e9b9 bfd5acbe 8bf043b8 c3e381dd 3062 f5771306 479ad142). 3064 X2 22716193187790487472805844610038683159372373526135883092373909944 3065 834653057415 3067 (=0x3238e8e2 ec6e8b7a e1e8feff 97aa58dd d2435bb5 0071cbc2 3068 0d0d4a42 9be67187). 3070 Y2 43046985853631671610553834968785204191967171967937842531656254539 3071 962663994648 3073 (=0x5f2bbb06 f7ec5953 2c2a1a62 21124585 1d2682e0 cc37307e 3074 fbc17f7f 7fda8518). 3076 The representation of k and the compressed representations of Pw and 3077 k*Pw in tight MSB/msb-order are given by 3079 repr(k) =0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3 3080 c08d5abd 15e29c50; 3082 repr(Pw) =0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7 3083 2a41cf12 629e56aa; 3085 repr(k*Pw) =0x079c3f69 9b688181 69038c35 39c11eb5 96d09f5b 12a242b4 3086 ce660f13 3368c13c, 3088 where the leftmost bit of the leftmost octet indicates the parity of 3089 the Y-coordinate of the point of Wei25519 in question (which, in this 3090 case, are both zero, since Y and Y1 are even). See Appendix H.1 and 3091 Appendix I for further detail on (squeezed) point compression. 3093 The scalar representation is consistent with the representations 3094 specified in [SEC1]; the (squeezed) point representation illustrated 3095 above is "new". For completeness, we include a SEC1-consistent 3096 representation of the point Pw in affine format and in compressed 3097 format below. 3099 The SEC1-compliant affine representation of the point Pw in tight 3100 MSB/msb-order is given by 3102 aff(Pw) =0x04 1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 3103 55202fe7 2a41cf12 629e56aa 3105 75e676ce deee3b3c 12942357 22f1d884 ac06de07 330fb07b 3106 ae35ca26 df75417e, 3108 whereas the SEC1-compliant compressed representation of the point Pw 3109 in tight MSB/msb-order is given by 3111 compr(Pw) =0x02 1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 3112 55202fe7 2a41cf12 629e56aa; 3114 The SEC1-compliant uncompressed format aff(Pw) of an affine point Pw 3115 corresponds to the right-concatenation of its X- and Y-coordinates, 3116 each in tight MSB/msb-order, prepended by the string 0x04, where the 3117 reverse procedure is uniquely defined, since elements of GF(p) have a 3118 unique fixed-size representation. The (squeezed) compressed format 3119 repr(Pw) corresponds to the SEC1-compliant compressed format by 3120 extracting the parity bit t from the leftmost bit of the leftmost 3121 octet of repr(Pw), replacing the bit position by the value zero, and 3122 prepending the octet string with 0x02 or 0x03, depending on whether 3123 t=0 or t=1, respectively, where the reverse procedure is uniquely 3124 defined, since GF(p) is a 255-bit prime field. For further details, 3125 see [SEC1]. Note that, due to the bit-size of the prime p, the 3126 squeezed compressed format repr(Pw) is one octet shorter than the 3127 SEC1-compliant compressed format compr(Pw). 3129 A randomized representation (t1, t2) of the point k*Pw in tight MSB/ 3130 msb order is given by 3131 t1 446363445988889734093446280484122107283059206243307955388 3132 84223152228795899590 3134 (=0x62af4697 4dd469ac 96c64809 c16c8517 b6a0cee5 40ba0e2e 3135 6dd2b36a fcc75ec6) 3137 t2 213890166610228613105792710708385961712211281744756216061 3138 11930888059603107561 3140 (=0x2f49c121 8fed7912 031157ee ae066507 a972320b 6180e267 3141 4025b006 2e67bee9), 3143 where this representation is defined in Appendix K.5 and uses the 3144 mapping of Appendix K.3.1 with the default square root function. 3146 J.4. Example with Wei25519.2 3148 Pw2=(X, Y), k*Pw2=(X1, Y1), and (k+1)*Pw2=(X2, Y2) with Wei25519.2: 3150 X 17830493209951148331008014701079988862634531394137235438571836389 3151 227198459763 3153 (=0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c 3154 f21c8672 d1ecaf73). 3156 Y 21064492012933896105338241940477778461866060481408222122979836206 3157 137075789640 3159 (=0x2e921479 5ad47af7 784831de 572ed8e9 7e20e137 cc67378c 3160 184ca19f f9136f48). 3162 X1 65470988951686461979789632362377759464688342154017353834939203791 3163 39281908968 3165 (=0x0e7986d2 e94354ab 8abd8806 3154536a 4dcf8e6e 65557183 3166 e242192d 3b87f4e8). 3168 Y1 51489590494292183562535790579480033229043271539297275888817125227 3169 35262330110 3171 (=0x0b623521 c1ff84bc 1522ff26 3376796d be77fcad 1fcabc28 3172 98f1be85 d7576cfe). 3174 X2 83741788501517200942826153677682120998854086551751663061374935388 3175 3494226693 3177 (=0x01d9f633 b2ac2606 9e6e93f7 6917446c 2b27c16f 729121d7 3178 709c0a58 00ef9b05). 3180 Y2 42567334190622848157611574766896093933050043101247319937794684825 3181 168161540336 3183 (=0x5e1c41e1 fb74e41b 3a19ce50 e1b2caf7 7cabcbb3 0c1c1474 3184 a4fd13e6 6c4c08f0). 3186 The representation of k and the compressed representations of Pw2 and 3187 k*Pw2 in tight MSB/msb-order are given by 3189 repr(k) =0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3 3190 c08d5abd 15e29c50; 3192 repr(Pw2) =0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c 3193 f21c8672 d1ecaf73; 3195 repr(k*Pw2) =0x0e7986d2 e94354ab 8abd8806 3154536a 4dcf8e6e 65557183 3196 e242192d 3b87f4e8, 3198 where the leftmost bit of the leftmost octet indicates the parity of 3199 the Y-coordinate of the point of Wei25519.2 in question (which, in 3200 this case, are both zero, since Y and Y1 are even). See 3201 Appendix Appendix H.1 and Appendix I for further detail on (squeezed) 3202 point compression. 3204 A randomized representation (t1, t2) of the point k*Pw2 in tight MSB/ 3205 msb order is given by 3207 t1 416669672354928148679758598803660112405431159793278161879 3208 36189858804289581274 3210 (=0x5c1eaaef 80f9d4af 33c119fc c99acd58 f81e7d69 999c7048 3211 e4043a77 87a930da) 3213 t2 361115271162391608083096560179337391059615651279123199921 3214 18531180247832114098 3216 (=0x4fd66668 e7174775 de44c852 92df8cfe b9832ef8 2570b3b8 3217 fe5ec21a b2d4b3b2), 3219 where this representation is defined in Appendix K.5 and uses the 3220 mapping of Appendix K.3.1 with the default square root function. 3222 J.5. Example with Wei25519.-3 3224 Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei25519.-3: 3226 X 14780197759513083469009623947734627174363231692126610860256057394 3227 455099634096 3228 (=0x20ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00 3229 eb4c9272 03ca71b0). 3231 Y 45596733430378470319805536538617129933663237960146030424392249401 3232 952949482817 3234 (=0x64ced628 e982648e 4bfcf30c 71c4d267 ba48b0ce fee20062 3235 b43ef4c9 73f7b541). 3237 X1 47362979975244556396292400751828272600887612546997532158738958926 3238 60745725532 3240 (=0x0a78a650 a39995ef dcf4de88 940d4ce9 5b2ca35c c5d70e06 3241 63b8455e 2e04e65c). 3243 Y1 30318112837157047703426636957515037640997356617656007157255559136 3244 153389790354 3246 (=0x4307719a 20d08741 58d5889e 8c8ec27e 246b0342 55f8fd62 3247 dbc9ca09 e79c7492). 3249 X2 23778942085873786433506063022059853212880296499622328201295446580 3250 293591664363 3252 (=0x3492677e 6ae9d1c3 e08f908b 61033f3d 4e8322c9 fba6da81 3253 2c95b067 9b1486eb). 3255 Y2 44846366394651736248316749170687053272682847823018287439056537991 3256 969511150494 3258 (=0x632624d4 ab94c83a 796511c0 5f5412a3 876e56d2 ed18eca3 3259 21b95bef 7bf9939e). 3261 The representation of k and the compressed representations of Pw3 and 3262 k*Pw3 in tight MSB/msb-order are given by 3264 repr(k) =0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3 3265 c08d5abd 15e29c50; 3267 repr(Pw3) =0xa0ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00 3268 eb4c9272 03ca71b0; 3270 repr(k*Pw3) =0x0a78a650 a39995ef dcf4de88 940d4ce9 5b2ca35c c5d70e06 3271 63b8455e 2e04e65c, 3273 where the leftmost bit of the leftmost octet indicates the parity of 3274 the Y-coordinate of the point of Wei25519.-3 in question (which, in 3275 this case, are one and zero, respectively, since Y is odd and Y1 is 3276 even). See Appendix H.1 and Appendix I for further detail on 3277 (squeezed) point compression. 3279 A randomized representation (t1, t2) of the point k*Pw3 in tight MSB/ 3280 msb order is given by 3282 t1 573714937613596601525680684642155667097217474964816246889 3283 88981227297409008259 3285 (=0x7ed71d5f 566d2259 99bdb404 bfb9d6cf d2e86ccb 1894d4a6 3286 c75e3c69 e5eb0283) 3288 t2 269945781324580189815142015663892935722419453863927287235 3289 57891665397640090729 3291 (=0x3bae63c8 70f60de0 c2e35f94 d24220f1 bb6efd00 37625869 3292 f84923de ff4c5469), 3294 where this representation is defined in Appendix K.5 and uses the 3295 mapping of Appendix K.3.1 with the default square root function. 3297 Appendix K. Auxiliary Functions 3299 This section illustrates how one could implement common routines, 3300 such as taking square roots and inverses in finite fields, and how to 3301 map field elements to curve points and to curve points that avoid 3302 some outliers. 3304 K.1. Square Roots in GF(q) 3306 Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see 3307 Appendix K.1.1) or if q = 5 (mod 8) (see Appendix K.1.2). Details on 3308 how to compute square roots for other values of q are out of scope. 3309 If square roots are easy to compute in GF(q), then so are these in 3310 GF(q^2). 3312 K.1.1. Square Roots in GF(q), where q = 3 (mod 4) 3314 If y is a nonzero element of GF(q) and z:=y^{(q-3)/4}, then y is a 3315 square in GF(q) only if y*z^2=1. If y*z^2=1, z is a square root of 3316 1/y and y*z is a square root of y in GF(q). 3318 K.1.2. Square Roots in GF(q), where q = 5 (mod 8) 3320 If y is a nonzero element of GF(q) and z:=y^{(q-5)/8}, then y is a 3321 square in GF(q) only if y^2*z^4=1. 3323 a. If y*z^2=+1, z is a square root of 1/y and y*z is a square root 3324 of y in GF(q); 3326 b. If y*z^2=-1, i*z is a square root of 1/y and i*y*z is a square 3327 root of y in GF(q). 3329 Here, i is an element of GF(q) for which i^2=-1 (e.g., 3330 i:=2^{(q-1)/4}). This field element can be precomputed. 3332 K.2. Inversion 3334 If y is an integer and gcd(y,n)=1, one can efficiently compute 1/y 3335 (mod n) via the extended Euclidean Algorithm (see Section 2.2.5 of 3336 [GECC]). One can use this algorithm as well to compute the inverse 3337 of a nonzero element y of a prime field GF(p), since gcd(y,p)=1. 3339 The inverse of a nonzero element y of GF(q) can be computed as 3341 1/y:=y^{q-2} (since y^{q-1}=1). 3343 If inverses are easy to compute in GF(q), then so are these in 3344 GF(q^2). Further details are out of scope. 3346 The inverses of two nonzero elements y1 and y2 of GF(q) can be 3347 computed by first computing the inverse z of y1*y2 and by 3348 subsequently computing y2*z=:1/y1 and y1*z=:1/y2. 3350 K.3. Mappings to Curve Points 3352 One can map elements of GF(q) that are not a square in GF(q) to 3353 points of a Weierstrass curve (see Appendix K.3.1), to points of a 3354 Montgomery curve (see Appendix K.3.2), or to points of a twisted 3355 Edwards curve (see Appendix K.3.3), under some mild conditions on the 3356 domain parameters. Full details on mappings that apply if these 3357 conditions are not satisfied are out of scope. 3359 K.3.1. Mapping to Points of Weierstrass Curve 3361 The description below assumes that the domain parameters a and b of 3362 the Weierstrass curve W_{a,b} are nonzero. For ease of exposition, 3363 we define f(z):=z^3+a*z+b. (Note that for an affine point (X,Y) of 3364 W_{a,b} one has Y^2=f(X).) 3366 If t is an element of GF(q) that is not a square in GF(q) and that is 3367 unequal to -1, then the element X:=(-b/a)*(1+1/(t+t^2)) is the unique 3368 solution of the equation f(t*X)=t^3*f(X) and is nonzero. 3369 Consequently, either X or X':=t*X is the x-coordinate of an affine 3370 point of W{a,b}, depending on whether f(X) is a square in GF(q). 3372 a. If f(X) is a square in GF(q) and Y:=sqrt(f(X)), then t is mapped 3373 to the point P(t):=(X, Y); 3375 b. If f(X) is not a square in GF(q) and Y':=sqrt(f(X')), then t is 3376 mapped to the point P(t):=(X', -Y'). 3378 Formally, this mapping is not properly defined, since a nonzero 3379 square y:=x^2 in GF(q) has two solutions, viz. x and -x; it is 3380 properly defined, however, if one designates for each element in 3381 GF(q) that is a square in GF(q) precisely one square root as "the" 3382 square root of this element. Note that always picking the square 3383 root with zero parity (see Appendix H) satisfies this condition 3384 (henceforth called the default square root function). 3386 If -1 is not a square in GF(q), this element is mapped to the point 3387 at infinity O of W_{a,b}. 3389 The set of points of W_{a,b} that arises this way has size roughly 3390 3/8 of the order of the curve and each such point arises as image of 3391 one or two t values. Further details are out of scope. 3393 NOTE 1: If -1 is not a square in GF(q), the mapping above yields the 3394 point at infinity for t=-1. One can modify this mapping to always 3395 yield an affine point, by mapping the element -1 to, e.g., the base 3396 point G of W_{a,b} and leaving the remainder of the mapping the same. 3397 Suitability of such a modification is application-specific. Details 3398 are out of scope. 3400 NOTE 2: The description above assumes that the domain parameters a 3401 and b of the Weierstrass curve are nonzero. If this is not the case, 3402 one can often find an isogenous curve W_{a',b'} for which the domain 3403 parameters a' and b' are nonzero. If so, one can map elements of 3404 GF(q) that are not a square in GF(q) to points of W_{a,b} via 3405 function composition, where one uses the mapping above to arrive at a 3406 point of W_{a',b'} and where one subsequently uses the dual isogeny 3407 from W_{a',b'} to W_{a,b} to arrive at a point of W_{a,b}. As an 3408 example, one can show that if a is zero and if -4*b is a cube in 3409 GF(q) (such as is the case with, e.g., the "BitCoin" curve secp256k1 3410 [SEC2]), this curve is 3-isogenous to a curve with this property and 3411 the strategy above applies (for an example with secp256k1, see 3412 Appendix L). Further details are out of scope. 3414 K.3.2. Mapping to Points of Montgomery Curve 3416 The description below assumes that the domain parameter A of the 3417 Montgomery curve M_{A,B} is nonzero. For ease of exposition, we 3418 define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of 3419 M_{A,B} one has B*v^2=f(u).) 3420 If t is an element of GF(q) that is not a square in GF(q) and that is 3421 unequal to -1, then the element u:=-(1+1/t)/A is the unique nonzero 3422 solution of the equation f(t*u)=t^3*f(u). Consequently, either u or 3423 u':=t*u is the u-coordinate of an affine point of M{A,B}, depending 3424 on whether f(u)/B is a square in GF(q). 3426 a. If f(u)/B is a square in GF(q) and v:=sqrt(f(u)/B), then t is 3427 mapped to the point P(t):=(u, v); 3429 b. If f(u)/B is a not a square in GF(q) and v':=sqrt(f(u')/B), then 3430 t is mapped to the point P(t):=(u', -v'). 3432 As before, formally, this mapping is not properly defined, since a 3433 nonzero square y:=x^2 in GF(q) has two solutions, viz. x and -x; it 3434 is properly defined, however, if one designates for each element in 3435 GF(q) that is a square in GF(q) precisely one square root as "the" 3436 square root of this element. Note that always picking the square 3437 root with zero parity (see Appendix H) satisfies this condition 3438 (henceforth called the default square root function). 3440 If -1 is not a square in GF(q), this element is mapped to the point 3441 at infinity O of M_{A,B}. 3443 The set of points of M_{A,B} that arises this way has size roughly 3444 1/2 of the order of the curve and each such point arises as image of 3445 precisely one t value. Further details are out of scope. 3447 NOTE 1: If -1 is not a square in GF(q), the mapping above yields the 3448 point at infinity for t=-1. One can modify this mapping to always 3449 yield an affine point, by mapping the element -1 to, e.g., the base 3450 point G of M_{A,B} and leaving the remainder of the mapping the same. 3451 Suitability of such a modification is application-specific. Details 3452 are out of scope. 3454 NOTE 2: The description above assumes that the domain parameter A of 3455 the Montgomery curve is nonzero. If this is not the case, the curve 3456 is a Weierstrass curve for which the domain parameter b is zero and 3457 Note 2 of Appendix K.3.1 applies. If q = 3 (mod 4), an even simpler 3458 approach is possible, where one modifies the construction above and 3459 simply takes u:=t and u':=-t (which works, since -1 is not a square 3460 in GF(q) and f(-t)=-f(t)). In this case, this construction can be 3461 extended to all elements t of GF(q) and, if so, yields a 1-1 mapping 3462 between GF(q) and all affine curve points. 3464 K.3.3. Mapping to Points of Twisted Edwards Curve 3466 One can map elements of GF(q) that are not a square in GF(q) to 3467 points of the twisted Edwards curve E_{a,d} via function composition, 3468 where one uses the mapping of Appendix K.3.1 to arrive at a point of 3469 the Weierstrass curve W_{a,b} and where one subsequently uses the 3470 isomorphic mapping between twisted Edwards curves and Weierstrass 3471 curves of Appendix D.3 to arrive at a point of E_{a,d}. Another 3472 mapping is obtained by function composition, where one instead uses 3473 the mapping of Appendix K.3.2 to arrive at a point of the Montgomery 3474 curve M_{A,B} and where one subsequently uses the isomorphic mapping 3475 between twisted Edwards curves and Montgomery curves of Appendix D.1 3476 to arrive at a point of E_{a,d}. Obviously, one can use function 3477 composition (now using the respective pre-images - if these exist) to 3478 realize the pre-images of either mapping. 3480 K.4. Mappings to High-Order Curve Points 3482 Appendix K.3 described how one can map elements of GF(q) that are not 3483 a square in GF(q) to points of a Weierstrass curve, to points of a 3484 Montgomery curve, or to points of a twisted Edwards curve, under some 3485 mild conditions on the domain parameters. Below, we use the mappings 3486 of that appendix and the parity function par(.) specified in 3487 Appendix H to construct mappings to high-order curve points only 3488 (i.e., mappings that avoid points in the small subgroup, see 3489 Appendix B.1). We consider mappings to high-order points of a 3490 Weierstrass curve (see Appendix K.4.1), to high-order points of a 3491 Montgomery curve (see Appendix K.4.2), and to high-order points of a 3492 twisted Edwards curve (see Appendix K.4.3). As before, full details 3493 on mappings that apply if the mild conditions on the domain 3494 parameters are not satisfied are out of scope. 3496 K.4.1. Mapping to High-Order Points of Weierstrass Curve 3498 The description below assumes that the domain parameters a and b of 3499 the Weierstrass curve W_{a,b} are nonzero. For ease of exposition, 3500 we define f(z):=z^3+a*z+b. (Note that for an affine point (X,Y) of 3501 W_{a,b} one has Y^2=f(X).) 3503 If t is an element of GF(q) that is not a square in GF(q) and that is 3504 unequal to -1, the mapping of Appendix K.3.1 yields an affine point 3505 P(t):=(X, Y) of W_{a,b}. Let P0:=(X0, Y0) be a fixed affine point of 3506 W_{a,b} for which neither P0, P0 + P(t), nor P0 - P(t) is in the 3507 small subgroup of W_{a,b}. (Note that this implies that P0 and P(t) 3508 are distinct affine points of the curve and that these are not each 3509 other's inverse.) For binary digit s, the point Q(t,s) is now 3510 defined as follows: 3512 a. If par(Y0*Y)=s, then the pair (t,s) is mapped to the point 3513 Q(t,s):=P0 + P(t); 3515 b. If par(Y0*Y)<>s, then the pair (t,s) is mapped to the point 3516 Q(t,s):=P0 - P(t). 3518 Note that this mapping is properly defined as long as the fixed point 3519 P0 (the so-called "curve offset") alluded to above indeed exists. In 3520 cases of practical interest that we are aware of, this is indeed the 3521 case (see, e.g., Table 1). 3523 If -1 is not a square in GF(q), the pair (-1,s) is mapped to the 3524 affine point P0 of W_{a,b} (irrespective of the value of s). 3526 The set of points of W_{a,b} that arises this way has size roughly 3527 3/8 of the order of the curve and each such point arises as image of 3528 up to four values of the pair (t,s). Further details are out of 3529 scope. 3531 From the group law for Weierstrass curves (see Appendix C.1) it 3532 follows that one can express the coordinates of Q(t,s), with t<>-1, 3533 in terms of the X-coordinates of P0 and P(t) and the product of their 3534 Y-coordinates. (Here, observe that Y0*Y is a square root of 3535 f(X0)*f(X).) Thus, Q(t,s) can be computed without the need to fully 3536 compute P(t). 3538 K.4.2. Mapping to High-Order Points of Montgomery Curve 3540 The description below assumes that the domain parameters A and B of 3541 the Montgomery curve M_{A,B} are nonzero. For ease of exposition, we 3542 define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of 3543 M_{A,B} one has B*v^2=f(u).) 3545 If t is an element of GF(q) that is not a square in GF(q) and that is 3546 unequal to -1, the mapping of Appendix K.3.2 yields an affine point 3547 P(t):=(u, v) of M_{A,B}. Let P0:=(u0, v0) be a fixed affine point of 3548 M_{A,B} for which neither P0, P0 + P(t), nor P0 - P(t) is in the 3549 small subgroup of M_{A,B}. (Note that this implies that P0 and P(t) 3550 are distinct affine points of the curve and that these are not each 3551 other's inverse.) For binary digit s, the point Q(t,s) is now 3552 defined as follows: 3554 a. If par(B*v0*v)=s, then the pair (t,s) is mapped to the point 3555 Q(t,s):=P0 + P(t); 3557 b. If par(B*v0*v)<>s, then the pair (t,s) is mapped to the point 3558 Q(t,s):=P0 - P(t). 3560 Note that this mapping is properly defined as long as the fixed point 3561 P0 (the so-called "curve offset") alluded to above indeed exists. In 3562 cases of practical interest that we are aware of, this is indeed the 3563 case (see, e.g., Table 1). 3565 If -1 is not a square in GF(q), the pair (-1,s) is mapped to the 3566 affine point P0 of M_{A,B} (irrespective of the value of s). 3568 The set of points of M_{A,B} that arises this way has size roughly 3569 1/2 of the order of the curve and each such point arises as image of 3570 up to two values of the pair (t,s). Further details are out of 3571 scope. 3573 From the group law for Montgomery curves (see Appendix C.2) it 3574 follows that one can express the coordinates of Q(t,s), with t<>-1, 3575 in terms of the u-coordinates of P0 and P(t) and the product of their 3576 v-coordinates. (Here, observe that B*v0*v is a square root of 3577 f(u0)*f(u).) Thus, Q(t,s) can be computed without the need to fully 3578 compute P(t). 3580 +----------------------------+------------------------+ 3581 | Curve | Fixed curve offset P0 | 3582 +----------------------------+------------------------+ 3583 | NIST P-224 [FIPS-186-4] | Base point (Gx,Gy) | 3584 | NIST P-256 [FIPS-186-4] | P0:=(0,y) with y even | 3585 | NIST P-384 [FIPS-186-4] | P0:=(0,y) with y even | 3586 | NIST P-521 [FIPS-186-4] | P0:=(0,y) with y even | 3587 | Brainpool224r1 [RFC5639] | Base point (Gx, Gy) | 3588 | Brainpool256r1 [RFC5639] | Base point (Gx, Gy) | 3589 | Brainpool320r1 [RFC5639] | Base point (Gx, Gy) | 3590 | Brainpool384r1 [RFC5639] | Base point (Gx, Gy) | 3591 | Brainpool512r1 [RFC5639] | P0:=(3,y), y even | 3592 | Curve25519 [RFC7748] | P0:=(90,v), v even | 3593 | Curve448 [RFC7748] | P0:=(50,v), v even | 3594 | Wei25519 [Appendix E.3] | P0:=(3,y), y even | 3595 | Wei25519.2 [Appendix G.3] | P0:=(244,y), y even | 3596 | Wei25519.-3 [Appendix G.3] | P0:=(41,y), y even | 3597 | secp256k1.m [Appendix L.3] | P0:=(0,y), y even | 3598 +----------------------------+------------------------+ 3600 Table 1: Curve offsets P0 for mappings that avoid low-order points 3602 K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 3604 One can map elements of GF(q) that are not a square in GF(q) to 3605 points of the twisted Edwards curve E_{a,d} via function composition, 3606 where one uses the mapping of Appendix K.4.1 to arrive at a point of 3607 the Weierstrass curve W_{a,b} that does not have low order and where 3608 one subsequently uses the isomorphic mapping between twisted Edwards 3609 curves and Weierstrass curves of Appendix D.3 to arrive at a point of 3610 E_{a,d} with this property. Another mapping is obtained by function 3611 composition, where one instead uses the mapping of Appendix K.4.2 to 3612 arrive at a point of the Montgomery curve M_{A,B} that does not have 3613 low order and where one subsequently uses the isomorphic mapping 3614 between twisted Edwards curves and Montgomery curves of Appendix D.1 3615 to arrive at a point of E_{a,d} with this property. Obviously, one 3616 can use function composition (now using the respective pre-images - 3617 if these exist) to realize the pre-images of either mapping. 3619 K.5. Randomized Representation of Curve Points 3621 The mappings of Appendix K.3 allow one to represent a curve point Q 3622 as a specific element t of GF(q), provided this point arises as a 3623 point in the range of the mapping at hand. For Montgomery curves and 3624 twisted Edwards curves, this covers roughly half of the curve points; 3625 for Weierstrass curves, roughly 3/8 of the curve points. One can 3626 extend the mappings above, by mapping a pair (t1, t2) of inputs to 3627 the point Q:=P2(t1, t2):=P(t1) + P(t2). In this case, each curve 3628 point has roughly q/4 representations as an ordered pair (t1, t2) on 3629 average. In fact, one can show that if the input pairs are generated 3630 uniformly at random, then the corresponding curve points follow a 3631 distribution that is also (statistically indistinguishable from) a 3632 uniform distribution, and vice-versa. Here, each pair (t1, t2) 3633 deterministically yields a curve point, whereas for each curve point 3634 Q, a randomized algorithm yields an ordered pair (t1, t2) of pre- 3635 images of Q, where the expected number of randomized pre-images one 3636 has to try is small (four if one uses the mapping of Appendix K.3.1; 3637 two if one uses the mapping of Appendix K.3.2). For further details, 3638 see Algorithm 1 of [Tibouchi]. 3640 Similar properties hold if one uses the mappings of Appendix K.4 3641 (rather than those of Appendix K.3): in this case, the mapping allows 3642 one to represent a curve point Q as a specific element (t,s) of 3643 GF(q)x{0,1}, provided this point arises as a point in the range of 3644 the mapping at hand. For Montgomery curves and twisted Edwards 3645 curves, this covers roughly half of the curve points; for Weierstrass 3646 curves, roughly 3/8 of the curve points. One can extend the mappings 3647 above, by mapping a pair ((t1,s1), (t2,s2)) of inputs to the point 3648 Q:=Q2((t1,s1), (t2,s2)):=Q(t1,s1) - Q(t2,s2). In this case, each 3649 curve point has roughly q representations as an ordered pair 3650 ((t1,s1), (t2,s2)) on average. In fact, one can show that if the 3651 input pairs are generated uniformly at random, then the corresponding 3652 curve points follow a distribution that is also (statistically 3653 indistinguishable from) a uniform distribution, and vice-versa. 3654 Here, each pair ((t1,s1), (t2,s2)) deterministically yields a curve 3655 point, whereas for each curve point Q, a randomized algorithm yields 3656 an ordered pair ((t1,s1), (t2,s2)) of pre-images of Q, where the 3657 expected number of randomized pre-images one has to try is small 3658 (four if one uses the mapping of Appendix K.4.1; two if one uses the 3659 mapping of Appendix K.4.2). Further details are out of scope. 3661 NOTE 1: The main difference between the two constructions above is 3662 that that the first construction uses the mappings to curve points 3663 described in Appendix K.3, while the second construction uses the 3664 mappings to high-order curve points described in Appendix K.4. Note 3665 that Q2((t1,s1), (t2,s2)) assumes all values (+/-) P(t1) (+/-) P(t2) 3666 if one considers all possible values for the binary digits s1 and s2. 3667 (This, thereby, includes the value P2(t1, t2).) 3669 NOTE 2: The second mapping above operates on input pairs (t,s), where 3670 t is an element of GF(q) that is not a square in GF(q) and where s is 3671 a binary digit from the set {0,1}. One can use these mappings to 3672 produce a mapping from the nonzero elements of GF(q) to points of a 3673 curve via function composition, where one first maps any nonzero 3674 element u of GF(q) to the pair (t,s):=(delta*u^2, par(u)), where 3675 delta is a fixed element of GF(q) that is not a square in GF(q), and 3676 where one subsequently applies any of the mappings above to yield a 3677 point of the curve in question. The resulting mapping from the 3678 nonzero elements of GF(q) to high-order curve points can be extended 3679 further to one that operates on all elements of GF(q) by mapping 0 to 3680 any fixed high-order point of the curve in question (e.g., to the 3681 fixed "curve offset" P0 of this curve [henceforth called the default 3682 completed mapping]). Depending on application-specific criteria, yet 3683 other function compositions may be preferred. For the first mapping 3684 above, one can use a similar function composition, where one simply 3685 drops the binary digit s and maps 0 to the point at infinity or any 3686 other suitable curve point. Further details are out of scope. 3688 Appendix L. Curve secp256k1 and Friend 3690 This section illustrates how isogenies can be used to yield curves 3691 with specific properties (here, for illustrated for the "BitCoin" 3692 curve secp256k1). 3694 L.1. Curve Definition and Alternative Representation 3696 The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined 3697 over the prime field GF(p), with p:=2^256-2^32-2^9-2^8-2^7-2^6-2^4-1, 3698 where a:=0 and b:=7. This curve has order h*n, where h=1 and where n 3699 is a prime number. For this curve, domain parameter a is zero, 3700 whereas b is not. The quadratic twist of this curve has order h1*n1, 3701 where h1 is a 37-bit integer and where n1 is a prime number. For 3702 this curve, the base point is the point (GX, GY). 3704 The curve secp256k1 is 3-isogenous to the Weierstrass curve 3705 secp256k1.m defined over GF(p), which has nonzero domain parameters a 3706 and b and has as base point the pair (GmX,GmY), where parameters are 3707 as specified in Appendix L.3 and where the related mappings are as 3708 specified in Appendix L.2. 3710 L.2. Switching Between Representations 3712 Each affine point (X,Y) of secp256k1 corresponds to the point 3713 (X',Y'):=(u(X)/w(X)^2,Y*v(X)/w(X)^3) of secp256k1.m, where u, v, and 3714 w are the polynomials with coefficients in GF(p) as defined in 3715 Appendix L.4.1, while the point at infinity of secp256k1 corresponds 3716 to the point at infinity of secp256k1.m. Under this isogenous 3717 mapping, the base point (GX,GY) of secp256k1 corresponds to the base 3718 point (GmX,GmY) of secp256k1.m. The dual isogeny maps the affine 3719 point (X',Y') of secp256k1.m to the affine point 3720 (X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of secp256k1, where u', 3721 v', and w' are the polynomials with coefficients in GF(p) as defined 3722 in Appendix L.4.2, while mapping the point at infinity O of 3723 secp256k1.m to the point at infinity O of secp256k1. Under this dual 3724 isogenous mapping, the base point (GmX, GmY) of secp256k1.m 3725 corresponds to a multiple of the base point (GX, GY) of secp256k1, 3726 where this multiple is l=3 (the degree of the isogeny; see the 3727 description in Appendix F.4). Note that this isogenous map (and its 3728 dual) primarily involves the evaluation of three fixed polynomials 3729 involving the x-coordinate, which takes roughly 10 modular 3730 multiplications (or less than 1% relative incremental cost compared 3731 to the cost of an elliptic curve scalar multiplication). 3733 L.3. Domain Parameters 3735 The parameters of the curve sec256k1 and the corresponding 3736 3-isogenous curve sec256k1.m are as indicated below. Here, the 3737 domain parameters of the curve secp256k1 are as specified in [SEC2]; 3738 the domain parameters of secp256k1.m are "new". 3740 General parameters (for all curves): 3742 p 2^256-2^32-2^9-2^8-2^7-2^6-2^4-1 3744 (=0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 3745 fffffffe fffffc2f) 3747 h 1 3749 n 11579208923731619542357098500868790785283756427907490438260516314 3750 1518161494337 3751 (=0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b 3752 bfd25e8c d0364141) 3754 h1 23479460174521 (=0x1a 9bfcab89) 3756 n1 10131766773001318469008702396060356387381009972480920692566974370 3757 31 3759 (=0x099ee564 ea5d84f5 08913936 a761b0d5 d792a426 a7779817 3760 ae2f5b67) 3762 Weierstrass curve-specific parameters (for secp256k1): 3764 a 0 (=0x00) 3766 b 7 (=0x07) 3768 GX 55066263022277343669578718895168534326250603453777594175500187360 3769 389116729240 3771 (=0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 3772 59f2815b 16f81798) 3774 GY 32670510020758816978083085130507043184471273380659243275938904335 3775 757337482424 3777 (=0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 3778 9c47d08f fb10d4b8) 3780 Weierstrass curve-specific parameters (for secp256k1.m): 3782 a 93991599167772749909245591943117186381494883464374162770646538702 3783 960816911535 3785 (=0xcfcd5c21 75e2ef7d ccdce737 770b7381 5a2f13c5 09035ca2 3786 54a14ac9 f08974af) 3788 b 1771 (=0x06eb) 3790 GmX 26591621185618668069038227574782692264471832498547635565821216767 3791 730887659845 3793 (=0x3aca5300 959fa1d0 baf78dcf f77a616f 395e586d 67aced0a 3794 88798129 0c279145) 3796 GmY 67622516283223102233819216063319565850973524550533340939716651159 3797 860372686848 3798 (=0x9580fce5 3a170f4f b744579f f3d62086 12cd6a23 3e2de237 3799 f976c6a7 8611c800) 3801 L.4. Isogeny Details 3803 The isogeny and dual isogeny are both isogenies with degree l=3. 3804 Both are specified by a triple of polynomials u, v, and w (resp. u', 3805 v', and w') of degree 3, 3, and 1, respectively, with coefficients in 3806 GF(p). The coeffients of each of these polynomials are specified in 3807 Appendix L.4.1 (for the isogeny) and in Appendix L.4.2 (for the dual 3808 isogeny). For each polynomial in variable x, the coefficients are 3809 tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in 3810 hexadecimal format. 3812 L.4.1. Isogeny Parameters 3814 L.4.1.1. Coefficients of u(x) 3816 0 0x54 3818 1 0xa4d89db3ed06c81e6143ec2eca9f761d8d17260dc229e1da1f73f714506872a9 3820 2 0xcc58ffccbd9febb4a66222c7d1311d988d88c0624bcd68ec4c758a8e67dfd99b 3822 3 0x01 3824 L.4.1.2. Coefficients of v(x) 3826 0 0x1c 3828 1 0x94c7bc69befd17f2fae2e3ebf24df1f355d181fa1a8056103ba9baad4b40f029 3830 2 0xb2857fb31c6fe18ef993342bb9c9ac64d44d209371b41d6272b04fd61bcfc851 3832 3 0x01 3834 L.4.1.3. Coefficients of w(x) 3836 0 0xe62c7fe65ecff5da53311163e8988ecc46c4603125e6b476263ac546b3efeae5 3838 1 0x01 3840 L.4.2. Dual Isogeny Parameters 3841 L.4.2.1. Coefficients of u'(x) 3843 0 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa8c7 3845 1 0x44cd5cd7ce55a801725891578fbe7356bd936355fd0e2f538797cecff7a37244 3847 2 0x668d0011162006c3c889f4680f9a4b77d0d26a89e6bb87b13bd8d1cfdd600a41 3849 3 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c 3851 L.4.2.2. Coefficients of v'(x) 3853 0 0x4bda12f684bda12f684bda12f684bda12f684bda12f684bda12f684b8e38e23c 3855 1 0x519ba9c1f48f68054def6a410f0fa6e8b71c6c3b4a8958324681f6508c01fada 3857 2 0xb34680088b100361e444fa3407cd25bbe8693544f35dc3d89dec68e76eb00338 3859 3 0x2f684bda12f684bda12f684bda12f684bda12f684bda12f684bda12f38e38d84 3861 L.4.2.3. Coefficients of w'(x) 3863 0 0x4d7a804ce3901e71066ccbd44636539b2bb2df6c8e4be29d8d4fb028e43033de 3865 1 0x01 3867 Appendix M. Curve448 and Cousins 3869 This section introduces curves related to Curve448 and explains their 3870 relationships. 3872 M.1. Curve Definition and Alternative Representations 3874 The elliptic curve Curve448 is the Montgomery curve M_{A,B} defined 3875 over the prime field GF(p), with p:=2^{448}-2^{224}-1, where 3876 A:=156326 and B:=1. This curve has order h*n, where h=4 and where n 3877 is a prime number. For this curve, A^2-4 is not a square in GF(p), 3878 whereas A-2 is. The quadratic twist of this curve has order h1*n1, 3879 where h1=4 and where n1 is a prime number. For this curve, the base 3880 point is the point (Gu, Gv), where Gu=5 and where Gv is an even 3881 integer in the interval [0, p-1]. 3883 This curve has the same group structure as (is "isomorphic" to) the 3884 twisted Edwards curve E_{a,d} defined over GF(p), with as base point 3885 the point (Gx, Gy), where parameters are as specified in 3886 Appendix M.3. This curve is denoted as Ed448. For this curve, the 3887 parameter a is a square in GF(p), whereas d is not, so the group laws 3888 of Appendix C.3 apply. 3890 The curve is also isomorphic to the elliptic curve W_{a,b} in short- 3891 Weierstrass form defined over GF(p), with as base point the point 3892 (GX, GY), where parameters are as specified in Appendix M.3. This 3893 curve is denoted as Wei448. 3895 M.2. Switching between Alternative Representations 3897 Each affine point (u, v) of Curve448 corresponds to the point (X, 3898 Y):=(u + A/3, v) of Wei448, while the point at infinity of Curve448 3899 corresponds to the point at infinity of Wei448. (Here, we used the 3900 mappings of Appendix D.2 and that B=1.) Under this mapping, the base 3901 point (Gu, Gv) of Curve448 corresponds to the base point (GX, GY) of 3902 Wei448. The inverse mapping maps the affine point (X, Y) of Wei448 3903 to (u, v):=(X - A/3, Y) of Curve448, while mapping the point at 3904 infinity of Wei448 to the point at infinity of Curve448. Note that 3905 this mapping involves a simple shift of the first coordinate and can 3906 be implemented via integer-only arithmetic as a shift of -(p-A)/3 for 3907 the isomorphic mapping and a shift of (p-A)/3 for its inverse, where 3908 delta=(p-A)/3 is the element of GF(p) defined by 3910 delta 24227957476520229684977460262933484478454712022910602009383006 3911 63935374427222435908954654612328921819766962948206145457870178326 3912 72736371 3914 (=0x55555555 55555555 55555555 55555555 55555555 55555555 3915 55555554 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 3916 ffff3473). 3918 (Note that, depending on the implementation details of the field 3919 arithmetic, one may have to shift the result by +p or -p if this 3920 integer is not in the interval [0,p-1].) 3922 The curve Ed448 is isomorphic to the curve Curve448, where the base 3923 point (Gu, Gv) of Curve448 corresponds to the base point (Gx,Gy) of 3924 Ed448 and where the point at infinity and the point (0,0) of order 3925 two of Curve448 correspond to, respectively, the point (0, 1) and the 3926 point (0, -1) of order two of Ed448 and where each other point (u, v) 3927 of Curve448 corresponds to the point (c*u/v, (u+1)/(u-1)) of Ed448, 3928 where c is the element of GF(p) defined by 3930 c sqrt((A-2)/B) 3932 19788846729546443953835400975385803825683515259105980214819977919 3933 60874042320025157136042631277930307478554244641856917664538448351 3934 92428 3935 (=0x45b2c5f7 d649eed0 77ed1ae4 5f44d541 43e34f71 4b71aa96 3936 c945af01 2d182975 0734cde9 faddbda4 c066f7ed 54419ca5 2c85de1e 3937 8aae4e6c). 3939 (Here, we used the mapping of Appendix D.1 and normalized this using 3940 the mapping of Appendix F.1 (where the element s of that appendix is 3941 set to c above).) The inverse mapping from Ed448 to Curve448 is 3942 defined by mapping the point (0, 1) and the point (0, -1) of order 3943 two of Ed448 to, respectively, the point at infinity and the point 3944 (0,0) of order two of Curve448 and having each other point (x, y) of 3945 Ed448 correspond to the point ((y + 1)/(y - 1), c*(y + 1)/((y-1)*x)) 3946 of Curve448. 3948 The curve Ed448 is isomorphic to the Weierstrass curve Wei448, where 3949 the base point (Gx, Gy) of Ed448 corresponds to the base point 3950 (GX,GY) of Wei448 and where the identity element (0,1) and the point 3951 (0,-1) of order two of Ed448 correspond to, respectively, the point 3952 at infinity O and the point (A/3, 0) of order two of Wei448 and where 3953 each other point (x, y) of Ed448 corresponds to the point (X, 3954 Y):=((y+1)/(y-1)+A/3, c*(y+1)/((y-1)*x)) of Wei448, where c was 3955 defined before. (Here, we used the mapping of Appendix D.3.) The 3956 inverse mapping from Wei448 to Ed448 is defined by mapping the point 3957 at infinity O and the point (A/3, 0) of order two of Wei448 to, 3958 respectively, the identity element (0,1) and the point (0,-1) of 3959 order two of Ed448 and having each other point (X, Y) of Wei448 3960 correspond to the point (c*(X-A/3)/Y, (X-A/3+1)/(X-A/3-1)) of Ed448. 3962 Note that these mappings can be easily realized if points are 3963 represented in projective coordinates, using a few field 3964 multiplications only, thus allowing switching between alternative 3965 curve representations with negligible relative incremental cost. 3967 M.3. Domain Parameters 3969 The parameters of the Montgomery curve and the corresponding 3970 isomorphic curves in twisted Edwards curve and short-Weierstrass form 3971 are as indicated below. Here, the domain parameters of the 3972 Montgomery curve Curve448 and of the twisted Edwards curve Ed448 are 3973 as specified in [RFC7748]; the domain parameters of Wei448 are "new". 3975 IMPORTANT NOTE: the supposed base point of Ed448 specified in 3976 [RFC7748] is incorrect, since it has order 2*n, and - in the notation 3977 below - that point is the point (Gx,-Gy)=-(Gx, Gy)+(0,-1). The 3978 birational map in that document is also incorrect. 3980 General parameters (for all curve models): 3982 p 2^{448}-2^{224}-1 3983 (=0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 3984 fffffffe ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 3985 ffffffff) 3987 h 4 3989 n 18170968107390172263733095197200113358841034017182951507037254979 3990 51460039615395857161957552916923759633102937090916623047737558596 3991 49779 3993 (=2^{446} - 0x8335dc16 3bb124b6 5129c96f de933d8d 723a70aa 3994 dc873d6d 54a7bb0d) 3996 h1 4 3998 n1 18170968107390172263733095197200113358841034017182951507037254979 3999 51601601218258006270024365576458970017341485218301563757529931495 4000 32941 4002 (=2^{446} + 0x0335dc16 3bb124b6 5129c96f de933d8d 723a70aa 4003 dc873d6d 54a7bb0d) 4005 Montgomery curve-specific parameters (for Curve448): 4007 A 156326 (=0x0262a6) 4009 B 1 (=0x01) 4011 Gu 5 (=0x05) 4013 Gv 35529392678556817526412750206378333480897639938771427183188089843 4014 51690887869674100029326737658645509101427741472681058389855952906 4015 06362 4017 (=0x7d235d12 95f5b1f6 6c98ab6e 58326fce cbae5d34 f55545d0 4018 60f75dc2 8df3f6ed b8027e23 46430d21 1312c4b1 50677af7 6fd7223d 4019 457b5b1a) 4021 Edwards curve-specific parameters (for Ed448): 4023 a 1 (0x01) 4025 d 39082/39081 = (A+2)/(A-2) 4027 (=611975850744529176160423220965553317543219696871016626328968936 4028 41508786004263647489178559928366602041476867897998937814706546281 4029 5545017) 4030 (=0xd78b4bdc 7f0daf19 f24f38c2 9373a2cc ad461572 42a50f37 4031 809b1da3 412a12e7 9ccc9c81 264cfe9a d0809970 58fb61c4 243cc32d 4032 baa156b9) 4034 Gx 34539749303972951637400860415053741026665526007518329021640697028 4035 16456950736723444304817877593406332217083915834240417889241245677 4036 00732 4038 (=0x79a70b2b 70400553 ae7c9df4 16c792c6 1128751a c9296924 4039 0c25a07d 728bdc93 e21f7787 ed697224 9de732f3 8496cd11 69871309 4040 3e9c04fc) 4042 Gy 3/2 4044 36341936214780344527466190394400226717682068034365903014074509959 4045 03061640833653863431981918493382729650444422309218186805267490091 4046 82721 4048 (=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff 4049 ffffffff 80000000 00000000 00000000 00000000 00000000 00000000 4050 00000001) 4052 Weierstrass curve-specific parameters (for Wei448): 4054 a 48455914953040459369954920525866968956909424045821204018766013278 4055 70748854444871817909309224657843639533925896412290915740356571996 4056 37535 4058 (=0xaaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa 4059 aaaaaaa9 ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe 4060 1a76d41f) 4062 b 26919952751689144094419400292148316087171902247678446677092229599 4063 28193808024928787727394013698802021963292164673494953191916856645 4064 13904 4066 (=0x5ed097b4 25ed097b 425ed097 b425ed09 7b425ed0 97b425ed 4067 097b425e 71c71c71 c71c71c7 1c71c71c 71c71c71 c71c71c7 1c72c87b 4068 7cc69f70) 4070 GX 48455914953040459369954920525866968956909424045821204018766013278 4071 70748854444871817909309224657843639533925896412290915740356653456 4072 29073 4074 (=0xaaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa 4075 aaaaaaaa 00000000 00000000 00000000 00000000 00000000 00000000 4076 0000cb91) 4078 GY 35529392678556817526412750206378333480897639938771427183188089843 4079 51690887869674100029326737658645509101427741472681058389855952906 4080 06362 4082 (=0x7d235d12 95f5b1f6 6c98ab6e 58326fce cbae5d34 f55545d0 4083 60f75dc2 8df3f6ed b8027e23 46430d21 1312c4b1 50677af7 6fd7223d 4084 457b5b1a) 4086 Appendix N. Further Cousins of Curve448 4088 This section introduces some further curves related to Curve448 and 4089 explains their relationships. 4091 N.1. Further Alternative Representations 4093 The Weierstrass curve Wei448 is isomorphic to the Weierstrass curve 4094 Wei448.1 defined over GF(p), with as base point the pair (G1X,G1Y), 4095 and isogenous to the Weierstrass curve Wei448.-3 defined over GF(p), 4096 with as base point the pair (G3X, G3Y), where parameters are as 4097 specified in Appendix N.3 and where the related mappings are as 4098 specified in Appendix N.2. The Edwards curve Ed448 is isogenous to 4099 the Edwards curve Edwards448 defined over GF(p), with as base point 4100 the pair (G1x,G1y), where parameters are as specified in Appendix N.3 4101 and where the related mappings are as specified in Appendix N.2. 4103 N.2. Further Switching 4105 Each affine point (X, Y) of Wei448 corresponds to the point (X', 4106 Y'):=(X*s^2,Y*s^3) of Wei448.1, where s is the element of GF(p) 4107 defined by 4109 s 52322274343677442779379520589771028818568404587729117919590511061 4110 93509510238347880134473888687471465216641846232724641298954890800 4111 00881 4113 (=0xb848cd01 981d2f83 f2829b42 eb86914e 88f44c9d 05dcbdff 4114 dbdd1e56 c4674bc8 d6d90d91 862a38f5 ca797ca7 f21c05cf a7ac32bf 4115 d2ca0171), 4117 while the point at infinity of Wei448 corresponds to the point at 4118 infinity of Wei448.1. (Here, we used the mapping of Appendix F.3.) 4119 Under this mapping, the base point (GX, GY) of Wei448 corresponds to 4120 the base point (G1X,G1Y) of Wei448.1. The inverse mapping maps the 4121 affine point (X', Y') of Wei448.1 to (X,Y):=(X'/s^2,Y'/s^3) of 4122 Wei448, while mapping the point at infinity O of Wei448.1 to the 4123 point at infinity O of Wei448. Note that this mapping (and its 4124 inverse) involves a modular multiplication of both coordinates with 4125 fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which 4126 can be precomputed. 4128 Each affine point (X,Y) of Wei448 for which the Y-coordinate is 4129 nonzero (i.e., each point with order larger than two) corresponds to 4130 the point (X',Y'):=(X1*t^2,Y1*t^3) of Wei448.-3, where 4131 (X1,Y1)=(u(X)/w(X),Y*v(X)/w(X)^2), where u, v, and w are the 4132 polynomials with coefficients in GF(p) as defined in Appendix N.4.1 4133 and where t is the element of GF(p) defined by 4135 t 23579450751475691430882365546539966269774125426758968522698856022 4136 13378944265540874438945283200254318223329383397068961863760712339 4137 07365 4139 (=0x530c9a1d7cf071d09646b83db246626b4e57ba5d6a791bef761972543209d 4140 c5c20d81498d5ab8d7a2fb22507ca68c040a6c82eb3b6c7aaa5), 4142 while the point at infinity and the point (A/3,0) of order two of 4143 Wei448 corresponds to the point at infinity of Wei448.-3. (Here, we 4144 used the isogenous mapping of Appendix F.4.) Under this isogenous 4145 mapping, the base point (GX,GY) of Wei448 corresponds to the base 4146 point (G3X,G3Y) of Wei448.-3. The dual isogeny maps the affine point 4147 (X',Y') of Wei448.-3 to the affine point 4148 (X,Y):=(u'(X1)/w'(X1),Y1*v'(X1)/w'(X1)^2) of Wei448, where 4149 (X1,Y1)=(X'/t^2,Y'/t^3) and where u', v', and w' are the polynomials 4150 with coefficients in GF(p) as defined in Appendix N.4.2, while 4151 mapping the point at infinity O of Wei448.-3 to the point at infinity 4152 O of Wei448. Under this dual isogenous mapping, the base point (G3X, 4153 G3Y) of Wei448.-3 corresponds to a multiple of the base point (GX, 4154 GY) of Wei448, where this multiple is l=2 (the degree of the isogeny; 4155 see the description in Appendix F.4). Note that this isogenous map 4156 (and its dual) primarily involves the evaluation of three fixed 4157 polynomials involving the x-coordinate, which takes only a few 4158 modular multiplications (less than 0.5% relative incremental cost 4159 compared to the cost of an elliptic curve scalar multiplication). 4161 Each point (x1,y1) of Edwards448 corresponds to the point (x,y) of 4162 Ed448, where 4164 x = c*x1*y1/(1-d1*x1^2*y1^2) = c*x1*y1/(2-x1^2-y1^2) and 4166 y =(1 + d1*x1^2*y1^2)/(y1^2-x1^2) = -(x1^2+y1^2)/(x1^2-y1^2). 4168 (Here, we used the 4-isogenous mapping of Appendix F.4. Under this 4169 isogenous mapping, the base point (G1x, G1y) of Edwards448 4170 corresponds to the base point (Gx,Gy) of Ed448. The dual isogeny 4171 maps each point (x,y) of Ed448 to the point (x1,y1) of Edwards448, 4172 where 4173 x1 = (4*x*y/c)/(y^2-x^2) and 4175 y1 = (1 - d*x^2*y^2)/(1 + d*x^2*y^2) = (2-x^2-y^2)/(x^2+y^2). 4177 Under this dual isogenous mapping, the base point (Gx, Gy) of Ed448 4178 corresponds to a multiple of the base point (G1x, G1y) of Edwards448, 4179 where this multiple is l=4 (the degree of the isogeny; see the 4180 description in Appendix F.4). Note that this isogenous map (and its 4181 dual) primarily involves the evaluation of three fixed polynomials, 4182 which takes only a few multiplications (less than 0.5% relative 4183 incremental cost compared to the cost of an elliptic curve scalar 4184 multiplication). 4186 The point (0,1) and the point (0,-1) of order two of Edwards448 4187 correspond to, respectively, the point at infinity and the point 4188 (0,0) of order two of Curve448, while each other point (x1,y1) of 4189 Edwards448 corresponds to the point (u,v) of Curve448, where 4191 u = y1^2/x1^2 and v = y1*(2-x1^2-y1^2)/x1^3. 4193 Under this isogenous mapping, the base point (G1x, G1y) of Edwards448 4194 corresponds to the base point (Gu,Gv) of Curve448. The dual isogeny 4195 maps both the point at infinity and the point (0,0) of order two of 4196 Curve448 to the point (0,1) of Edwards448, while each other point 4197 (u,v) of Curve448 corresponds to the point (x1,y1) of Edwards448, 4198 where 4200 x1 = 4*(u^2-1)*v/((u^2-1)^2+4*v^2) and 4202 y1 = u*((u^2-1)^2-4*v^2)/(2*(u^2+1)*v^2-u*(u^2-1)^2). 4204 Under this dual isogenous mapping, the base point (Gu, Gv) of 4205 Curve448 corresponds to a multiple of the base point (G1x, G1y) of 4206 Edwards448, where this multiple is l=4 (the degree of the isogeny; 4207 see above). 4209 N.3. Further Domain Parameters 4211 The parameters of the Weierstrass curve with a=1 that is isomorphic 4212 with Wei448 and the parameters of the Weierstrass curve with a=-3 4213 that is isogenous with Wei448 are as indicated below. Both domain 4214 parameter sets can be exploited directly to derive more efficient 4215 point addition formulae, should an implementation facilitate this. 4216 The domain parameters of the twisted Edwards curve Edwards448 are as 4217 specified in [RFC7748]. 4219 General parameters: same as for Wei448 (see Appendix M.3) 4220 Weierstrass curve-specific parameters (for Wei448.1, i.e., with a=1): 4222 a 1 (=0x01) 4224 b 65961281701807170531944804985907990287225248056560036392380945951 4225 38183088507635437786021044927715119224497407914895790669345268896 4226 52743 4228 (=0xe8528596 bfbcbac9 7ebdbe4e 9683e25c 73a5ff37 6c4cd400 4229 5a75c425 8e3eb05a 9f6f8c24 24cb5aa9 0dcf9fa4 cab6691d 5530347c 4230 28437207) 4232 G1X 19236211982508211644805033459306273038523230481309141518540414163 4233 72091186292458482231912460243257247478684005448999746809691007995 4234 9723 4236 (=0x06c672d5 b5bae33b 010fa210 9de7937a 95db8ffc 043c507f 4237 5e0d07a1 25382eaf 13f5fc3b 75db2614 6e6d002f d8364ed6 c9bc8fbf 4238 bbda22ab) 4240 G1Y 30319443056877169804488072384563064288675576234196773667920807567 4241 79177927858755621958756222206632465988308466319556948821775845861 4242 64158 4244 (=0x6ac9c53c 767cd3ae cbf904a1 2923502f 115355d1 6ae8911c 4245 5c92f612 aa854455 d1e6d29f 4db4ddea 519a174f c0dd2505 ec3328ba 4246 250a07be) 4248 Weierstrass curve-specific parameters (for Wei448.-3, i.e., with a=- 4249 3): 4251 a -3 4253 (=0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 4254 fffffffe ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 4255 fffffffc) 4257 b 69993768681000150084833669961900533067383335592494498709534693464 4258 91314250731583068774689950893229681024927315747794587331422088592 4259 54465 4261 (=0xf686723d 80e29d06 2d00a9f1 3305b698 85790019 cca78035 4262 9dac226b efb1ae21 125397dd 16f255b0 cc5d18e5 43582a1c af90dfe2 4263 c0aeaec1) 4265 G3X 40677474994869876470916133424311516856662407970799424837841348421 4266 87696274665113140719001227030116551378877280368526334985627104680 4267 88795 4268 (=0x8f452c6b dc3265dd 580b2638 59a02b20 198cc020 1dd7fba1 4269 8b431694 4a936052 fb4e4a41 93d01fa5 5fb5c732 7393208b 8170f3f2 4270 be78d3db) 4272 G3Y 54594210970205994927260789585006437115117066846498189378285031510 4273 90310290468347714929366106635470978666795512446629051235704504868 4274 06147 4276 (=0xc0494f90 461db11c 35fb7646 8349399a ae230351 11330cce 4277 b7473244 ab63c955 cf6ec02f 2656b439 44b19f4b 52eef12e 73026bbc 4278 84444683) 4280 Edwards curve-specific parameters (for Edwards448): 4282 a 1 (0x01) 4284 d1 -39081 = -(A-2)/4 4286 (=726838724295606890549323807888004534353641360687318060281490199 4287 18061232816673077268639638369867654593008888446184363736105349801 4288 8326358) 4290 (=0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 4291 fffffffe ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 4292 ffff6756) 4294 G1x 22458004029592430018760433409989603624678964163256413424612546168 4295 69504154674060329090291928693579532825780320751464461736746026352 4296 47710 4298 (=0x4f1970c6 6bed0ded 221d15a6 22bf36da 9e146570 470f1767 4299 ea6de324 a3d3a464 12ae1af7 2ab66511 433b80e1 8b00938e 2626a82b 4300 c70cc05e) 4302 G1y 29881921007848149267601793044393067343754404015408024209592824137 4303 23315061898358760035368786554187847339823032335034625005315450628 4304 32660 4306 (=0x693f4671 6eb6bc24 88762037 56c9c762 4bea7373 6ca39840 4307 87789c1e 05a0c2d7 3ad3ff1c e67c39c4 fdbd132c 4ed7c8ad 9808795b 4308 f230fa14) 4310 N.4. Isogeny Details 4312 The isogeny and dual isogeny are both isogenies with degree l=2. 4313 Both are specified by a triple of polynomials u, v, and w (resp. u', 4314 v', and w') of degree 2, 2, and 1, respectively, with coefficients in 4315 GF(p). The coeffients of each of these polynomials are specified in 4316 Appendix N.4.1 (for the isogeny) and in Appendix N.4.2 (for the dual 4317 isogeny). For each polynomial in variable x, the coefficients are 4318 tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in 4319 hexadecimal format. 4321 N.4.1. Isogeny Parameters 4323 N.4.1.1. Coefficients of u(x) 4325 0 0x01 4327 1 0x55555555555555555555555555555555555555555555555555555554ffffffff 4328 ffffffffffffffffffffffffffffffffffffffffffff3473 4330 2 0x01 4332 N.4.1.2. Coefficients of v(x) 4334 0 0x1c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c55555555 4335 5555555555555555555555555555555555555555f72db94a 4337 1 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa9ffffffff 4338 fffffffffffffffffffffffffffffffffffffffffffe68e6 4340 2 0x01 4342 N.4.1.3. Coefficients of w(x) 4344 0 0x55555555555555555555555555555555555555555555555555555554ffffffff 4345 ffffffffffffffffffffffffffffffffffffffffffff3473 4347 1 0x01 4349 N.4.2. Dual Isogeny Parameters 4351 N.4.2.1. Coefficients of u'(x) 4353 0 0x016c26e0e8 4355 1 0x5555555555555555555555555555555555555555555555555555555500000000 4356 0000000000000000000000000000000000000000000065c6 4358 2 0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffc0000000 4359 000000000000000000000000000000000000000000000000 4361 N.4.2.2. Coefficients of v'(x) 4363 0 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaaaaa 4364 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa45836c31 4366 1 0x5555555555555555555555555555555555555555555555555555555500000000 4367 0000000000000000000000000000000000000000000065c6 4369 2 0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffe0000000 4370 000000000000000000000000000000000000000000000000 4372 N.4.2.3. Coefficients of w'(x) 4374 0 0x5555555555555555555555555555555555555555555555555555555500000000 4375 000000000000000000000000000000000000000000019719 4377 1 0x01 4379 Appendix O. Representation Examples Curve448 Family Members 4381 We present some examples of computations using the curves introduced 4382 in this document. In each case, we indicate the values of P, k*P, 4383 and (k+1)*P, where P is a fixed multiple (here: 2019) of the base 4384 point of the curve in question and where the private key k is the 4385 integer 4387 k 62662039304523906689788124833289384446202946474440057655160773695 4388 63756342505410402166230018620066482794080866641616932013327623579 4389 01952 4391 (=0xdcb3bbb9 e42d7aca fe62052d 902123c7 0872b984 4c1e199f 4392 7c5d37bd 1171102b c20a6352 d9c91886 29b685de 51441e84 3afe2665 4393 5251aa80). 4395 O.1. Example with Curve448 4397 Pm=(u, v), k*Pm=(u1, v1), and (k+1)*Pm=(u2, v2) with Curve448: 4399 u 53298594738299085772373536080133483236673782578895339676785179923 4400 90764298300090102709453866054695061082746243636045110750296444932 4401 27715 4403 (=0xbbb91ba3 b0ef74c3 214394b4 d8f0d32d c4a92193 5f573009 4404 39fd86a3 8d54be2a 4d63380b 692381bb ed7339fd dca7b0cd a80166fe 4405 18c086c3). 4407 v 30578727850066757341435137807347775064915058999485530015946871157 4408 86794631407274936870618580714107931661730999350222644894729285604 4409 97149 4411 (=0x6bb38e82 8d52337f 6f0395ef dc16c776 52162f5e 309112ae 4412 fc7401bf 0cfb0499 eb1ed555 bf507ebc c33b4753 2d6dc6c5 d68dea1c 4413 c1e4c1fd). 4415 u1 64579461799301726935877447646800238443923683299745374127971411973 4416 12515295161791889743228049222279188968365877164188075095074418806 4417 82513 4419 (=0xe37497bf 9f704689 54ec6537 cbbe91d0 3ffcdcdb 8b707253 4420 a2212cdb e020ba9a 0bf65a1d 5d9a128a f85c63a2 79a00139 7aca56db 4421 15335011). 4423 v1 55735504615964066386264989698774850924544182484936624265048483231 4424 35693859362627880184586282439234602798023594054611737412667543758 4425 11547 4427 (=0xc44e5e0f 2c254d23 1dc082db 77175e8c fd37793c 22ebe200 4428 77905a5f 750b3c9f 4a95d4d5 4e1a1e54 d2d31689 4249252d 0c8b1c45 4429 1c1481db). 4431 u2 32685564331119553171673802371596819258307818641496728161547328225 4432 07595618587323619256769558535630624960575212644680149034661008254 4433 8876 4435 (=0x0b831eca 9c6215b0 5d830361 4013732f 7a9dd07f ebb9441e 4436 49129264 eb724f44 dc53671c ffabb9ee 0c02aa74 b083cd82 a821a4cf 4437 6f6d8c8c). 4439 v2 57682103223585233918507344950062950306770296215271320612937204938 4440 77499282103483092990510136901415757273082719665657484294344333591 4441 20741 4443 (=0xcb2988a4 6e37f9a9 a7a1255b 2fd2eea9 82308e7c eb8e18b8 4444 2252175f fd416a10 5984c6b8 36470e48 31879293 8f6139c6 f96164cb 4445 14010965). 4447 As suggested in Appendix C.2, the v-coordinate of k*Pm can be 4448 indirectly computed from the u-coordinates of Pm, k*Pm, and (k+1)*Pm, 4449 and the v-coordinate of Pm, which allows computation of the entire 4450 point k*Pm (and not just its u-coordinate) if k*Pm is computed using 4451 the Montgomery ladder (as, e.g., [RFC7748] recommends), since that 4452 algorithm computes both u1 and u2 and the v-coordinate of the point 4453 Pm may be available from context. 4455 The representation of k and the compressed representations of Pm and 4456 k*Pm in tight LSB/msb-order are given by 4458 repr(k) 0x80aa5152 6526fe3a 841e4451 de85b629 8618c9d9 52630ac2 4459 2b107111 bd375d7c 9f191e4c 84b97208 c7232190 2d0562fe 4460 ca7a2de4 b9bbb3dc; 4462 repr(Pm) 0xc386c018 fe6601a8 cdb0a7dc fd3973ed bb812369 0b38634d 4463 2abe548d a386fd39 0930575f 9321a9c4 2dd3f0d8 b4944321 4464 c374efb0 a31bb9bb 80; 4466 repr(k*Pm) 0x11503315 db56ca7a 3901a079 a2635cf8 8a129a5d 1d5af60b 4467 9aba20e0 db2c21a2 5372708b dbdcfc3f d091becb 3765ec54 4468 8946709f bf9774e3 80, 4470 where the leftmost bit of the rightmost octet indicates the parity of 4471 the v-coordinate of the point of Curve448 in question (which, in this 4472 case, are both one, since v and v1 are odd). See Appendix H.2 and 4473 Appendix I for further detail on (squeezed) point compression. 4475 The scalar representation and (squeezed) point representation 4476 illustrated above are consistent with the representations specified 4477 in [RFC7748], except that in [RFC7748] only an affine point's 4478 u-coordinate is represented (i.e., the v-coordinate of any point is 4479 always implicitly assumed to have an even value) and that the 4480 representation of the point at infinity is not specified. (Note that 4481 due to the bit-size of the prime p, the lossless representation 4482 requires an additional octet compared to the lossy representation 4483 without v-coordinate.) Another difference is that [RFC7748] allows 4484 non-unique representations of some elements of GF(p), whereas our 4485 representation conventions do not (since tight). 4487 A randomized representation (t1, t2) of the point k*Pm in tight LSB/ 4488 msb order is given by 4490 t1 642695971489808425948939115432957219707501931105169269237 4491 122551860533279049805112466411050091592893048844749561382 4492 909707113070546618079 4494 (=0xdf86cb83 ae1ca6e6 da6afbaf afbb2fc0 606a136f 80eea078 4495 c868a5d7 7e638d09 99518385 65250cf1 9c034f96 1fa28f54 4496 f3016600 68335de2) 4498 t2 569275737967591640709387827593956375775147481657775744720 4499 460881642951497067363381071471046477130052706607411985560 4500 522861593611384288817 4501 (=0x3176361c 580a7bcd d7880d84 aba10bc6 57010328 afb728cc 4502 2016461b 246bef46 0eb4bb04 8c1a3616 c3f74a56 3cc1790f 4503 6472256b ca3481c8), 4505 where this representation is defined in Appendix K.5 and uses the 4506 mapping of Appendix K.3.2 with the default square root function. 4508 O.2. Example with Ed448 4510 Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Ed448: 4512 x 12711234107145442394649604543297947887906244696692372551963816418 4513 93066253979844478364753304240794498368174540810674220788120782656 4514 62747 4516 (=0x2cc52fd1 6370554f 00c0f73f 64bda240 f5950177 d9033f6d 4517 74acd12d 68c79a51 315f556f 240973f9 e5f71ed7 9314ee9d c87f0b1b 4518 bcc0fd1b). 4520 y 69251010954633529003803699627438795111055087299023774963200632446 4521 22677618700964599963790149315020469517869703738619380660774687159 4522 85238 4524 (=0xf3e8bb95 c9675fd0 0c388fc5 e96cfbc7 3c19d945 76849979 4525 34c4ab60 73c4a763 c2a89bac d3879838 f4de11a3 3a4710c2 396dea1d 4526 cc012956). 4528 x1 69268794439088733926883958090256942256857349796922332363888137509 4529 71700910417786272464007666020220956482611896297610096130434552586 4530 39205 4532 (=0xf3f8c472 ca2e730b 05cc9092 f9d40956 029113e3 e92c2d55 4533 76406db2 c2903721 62f43371 1c0ec80c f8d7222d 1d701467 9da18531 4534 0fb5bb65). 4536 y1 50516707418203531159001223293623288296803299598968490915066154362 4537 78541820739332329525138363312119838075438487384161435963107103409 4538 09734 4540 (=0xb1eccbfc 5f5f92e8 d9129d14 b721c524 96fc1b1f a4c17c5f 4541 e4979b0c 763f34ba 91299376 d2499220 19b05f56 c3bb6b5d ac988271 4542 287d7aa6). 4544 x2 67287262124444231243108222498849910362455590990935326363062127166 4545 04126947894055981270997819628982374416022607672923451356182938105 4546 87868 4547 (=0xecfe1a4f a4cd7e2f 19afcf16 1ce2198f 0a850beb 41afa209 4548 94741609 5b1a858a 8e9548f5 011d188e d50484d3 119103f6 8bcd5ba2 4549 a6e3e8dc). 4551 y2 13744276256057290540518554008940700979716578667786691114397525367 4552 92684542875757407063179870154307882588988293167000249160114881659 4553 30341 4555 (=0x3068a338 4016ebfd a229ac73 b5c30bba ff67e183 71d1185f 4556 19dfbbee 28478baf 9034ebad 51407f01 35162743 c2c234bc 2d484c13 4557 552ea565). 4559 The representation of k and the compressed representations of Pe and 4560 k*Pe in tight LSB/lsb-order are given by 4562 repr(k) =0x01558a4a a6647f5c 2178228a 7ba16d94 6118939b 4ac65043 4563 d4088e88 bdecba3e f9987832 219d4e10 e3c48409 b4a0467f 4564 535eb427 9dddcd3b; 4566 repr(Pe) =0x6a948033 b857b69c 4308e25c c5887b2f 1c19e1cb 35d91543 4567 c6e523ce 06d5232c 9e99216e a29b983c e3df3697 a3f11c30 4568 0bfae693 a9dd17cf 01; 4570 repr(k*Pe) =0x655ebe14 8e411935 bad6ddc3 6afa0d98 0449924b 6ec99489 4571 5d2cfc6e 30d9e927 fa3e8325 f8d83f69 24a384ed 28b9489b 4572 1749fafa 3fd3378d 01, 4574 where the rightmost bit of the rightmost octet indicates the parity 4575 of the x-coordinate of the point of Ed448 in question (which, in this 4576 case, are both one, since x and x1 are odd). See Appendix H.3 and 4577 Appendix I for further detail on (squeezed) point compression. 4579 The scalar representation and (squeezed) point representation 4580 illustrated above are fully consistent with the representations 4581 specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032] 4582 requires unique representations of all elements of GF(p). 4584 A randomized representation (t1, t2) of the point k*Pe in tight LSB/ 4585 lsb order is given by 4587 t1 397357047759003459380102071532091085834125520561197668989 4588 747600577137881485970346806080038194336473483709104865191 4589 806326006691504231547 4591 (=0xde295d0e 5efceb9b f43967ca be45a54b a1f75bdd a4b1b1b3 4592 b24a8d1d f2056329 e506867e c968aa8b 866017e4 f0cbc343 4593 2cf8e7fa 0b202fd1) 4595 t2 711800301530600330791068062467600183663589340593884950808 4596 136091389056251997893995894309660827763434071897306280320 4597 151044063120296064809 4599 (=0x94ecb72a 069a5322 e62d9357 c49d5664 1c351611 d1f361a8 4600 cbb8a12c f410e821 4fbe8e02 8d85d404 399b4c7c 5a6a72ce 4601 deef7b08 96302d5f), 4603 where this representation is defined in Appendix K.5 and uses the 4604 mapping of Appendix K.3.3 with the default square root function and 4605 underlying isomorphic mapping between Ed448 and Curve448 of 4606 Appendix M.2. 4608 O.3. Example with Wei448 4610 Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei448: 4612 X 29070637261778856087396075817199998758219070555984737667402173284 4613 55389871077654193754799253725773241315783295429899652880118118204 4614 91344 4616 (=0x6663c64e 5b9a1f6d cbee3f5f 839b7dd8 6f53cc3e 0a01dab3 4617 e4a8314e 8d54be2a 4d63380b 692381bb ed7339fd dca7b0cd a80166fe 4618 18c15250). 4620 Y 30578727850066757341435137807347775064915058999485530015946871157 4621 86794631407274936870618580714107931661730999350222644894729285604 4622 97149 4624 (=0x6bb38e82 8d52337f 6f0395ef dc16c776 52162f5e 309112ae 4625 fc7401bf 0cfb0499 eb1ed555 bf507ebc c33b4753 2d6dc6c5 d68dea1c 4626 c1e4c1fd). 4628 X1 40351504322781497250899987383866753965468971276834772118588405333 4629 77140867939355980788573436893357369201402928958042617224896092079 4630 46142 4632 (=0x8e1f426a 4a1af133 ff970fe2 76693c7a eaa78786 361b1cfe 4633 4ccbd786 e020ba9a 0bf65a1d 5d9a128a f85c63a2 79a00139 7aca56db 4634 15341b9e). 4636 Y1 55735504615964066386264989698774850924544182484936624265048483231 4637 35693859362627880184586282439234602798023594054611737412667543758 4638 11547 4640 (=0xc44e5e0f 2c254d23 1dc082db 77175e8c fd37793c 22ebe200 4641 77905a5f 750b3c9f 4a95d4d5 4e1a1e54 d2d31689 4249252d 0c8b1c45 4642 1c1481db). 4644 X2 51724471386152414687122300763026650882740205909970876834920746101 4645 21508416303604179834986180511406702029983417676758930643822754281 4646 77944 4648 (=0xb62dc975 470cc05b 082dae0b eabe1dda 25487b2a 9663eec8 4649 f3bd3d0e eb724f44 dc53671c ffabb9ee 0c02aa74 b083cd82 a821a4cf 4650 6f6e5818). 4652 Y2 57682103223585233918507344950062950306770296215271320612937204938 4653 77499282103483092990510136901415757273082719665657484294344333591 4654 20741 4656 (=0xcb2988a4 6e37f9a9 a7a1255b 2fd2eea9 82308e7c eb8e18b8 4657 2252175f fd416a10 5984c6b8 36470e48 31879293 8f6139c6 f96164cb 4658 14010965). 4660 The representation of k and the compressed representations of Pw and 4661 k*Pw in tight MSB/msb-order are given by 4663 repr(k) =0xdcb3bbb9 e42d7aca fe62052d 902123c7 0872b984 4c1e199f 4664 7c5d37bd 1171102b c20a6352 d9c91886 29b685de 51441e84 4665 3afe2665 5251aa80; 4667 repr(Pw) =0x80 6663c64e 5b9a1f6d cbee3f5f 839b7dd8 6f53cc3e 4668 0a01dab3 e4a8314e 8d54be2a 4d63380b 692381bb ed7339fd 4669 dca7b0cd a80166fe 18c15250; 4671 repr(k*Pw) =0x80 8e1f426a 4a1af133 ff970fe2 76693c7a eaa78786 4672 361b1cfe 4ccbd786 e020ba9a 0bf65a1d 5d9a128a f85c63a2 4673 79a00139 7aca56db 15341b9e, 4675 where the leftmost bit of the leftmost octet indicates the parity of 4676 the Y-coordinate of the point of Wei448 in question (which, in this 4677 case, are both one, since Y and Y1 are odd). See Appendix H.1 and 4678 Appendix I for further detail on (squeezed) point compression. 4680 The scalar representation is consistent with the representations 4681 specified in [SEC1]; the (squeezed) point representation illustrated 4682 above is "new". For completeness, we include a SEC1-consistent 4683 representation of the point Pw in affine format and in compressed 4684 format below. 4686 The SEC1-compliant affine representation of the point Pw in tight 4687 MSB/msb-order is given by 4689 aff(Pw) =0x6663c64e 5b9a1f6d cbee3f5f 839b7dd8 6f53cc3e 0a01dab3 4690 e4a8314e 8d54be2a 4d63380b 692381bb ed7339fd dca7b0cd 4691 a80166fe 18c15250 4692 6bb38e82 8d52337f 6f0395ef dc16c776 52162f5e 309112ae 4693 fc7401bf 0cfb0499 eb1ed555 bf507ebc c33b4753 2d6dc6c5 4694 d68dea1c c1e4c1fd, 4696 whereas the SEC1-compliant compressed representation of the point Pw 4697 in tight MSB/msb-order is given by 4699 compr(Pw) =0x03 6663c64e 5b9a1f6d cbee3f5f 839b7dd8 6f53cc3e 4700 0a01dab3 e4a8314e 8d54be2a 4d63380b 692381bb ed7339fd 4701 dca7b0cd a80166fe 18c15250. 4703 The SEC1-compliant uncompressed format aff(Pw) of an affine point Pw 4704 corresponds to the right-concatenation of its X- and Y-coordinates, 4705 each in tight MSB/msb-order, prepended by the string 0x04, where the 4706 reverse procedure is uniquely defined, since elements of GF(p) have a 4707 unique fixed-size representation. The (squeezed) compressed format 4708 repr(Pw) corresponds to the SEC1-compliant compressed format by 4709 extracting the parity bit t from the leftmost bit of the leftmost 4710 octet of repr(Pw), and replacing this leftmost octet with 0x02 or 4711 0x03, depending on whether t=0 or t=1, respectively, where the 4712 reverse procedure is uniquely defined. For further details, see 4713 [SEC1]. Note that, due to the bit-size of the prime p, the squeezed 4714 compressed format repr(Pw) and the SEC1-compliant compressed format 4715 compr(Pw) have the same size. 4717 A randomized representation (t1, t2) of the point k*Pw in tight MSB/ 4718 msb order is given by 4720 t1 655783099225353926682910498535559663266263823350679216116 4721 172951494291735730803127024621397533084891460609898061397 4722 896825551162064841608 4724 (=0xe6f93655 2765628b accfe61c 7dc6a594 e06fb243 70195ded 4725 74d88a53 fdedc2e8 077e0eff 62fa6a80 fa26b499 1f8796f5 4726 21f2f03b f7e92b88) 4728 t2 357918241879339174086992006475988394618511927120788596330 4729 507910466738735762660894972854331591097934354210992993787 4730 402433561014235472657 4732 (=0x7e0ffcaf 7add27bc bb723629 95fdedd0 8769f676 78d953bc 4733 0d38f4f6 d63a59dc 00f2d55a a4db7dab 16364503 591edcb1 4734 e095a577 43dea311), 4736 where this representation is defined in Appendix K.5 and uses the 4737 mapping of Appendix K.3.1 with the default square root function. 4739 O.4. Example with Wei448.-3 4741 Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei448.-3: 4743 X 54121793865726175505902038600562190720650456678500106168173285986 4744 99999531708218763586616425010404811083912084906688745035466757984 4745 48968 4747 (=0xbe9f5a23 51709e13 d5ad50c2 a27be8ee 1b051970 2580d5c3 4748 c2de7f75 3010635e d89ef547 8b67dc54 16d63c5b 1cc1116f dd453515 4749 71b39b48). 4751 Y 14962282101304548030627835311887275833718070818965306362006934455 4752 59168773381983445709256615887526455657034051121085622763637035580 4753 12661 4755 (=0x34b2dcc4 92d6a940 e6249c14 122d0ba4 5dc040e9 3f060d8f 4756 a65fa300 eb3cc969 25188b59 2d31039c f7a8e14a 48320a32 efe9b42b 4757 986afef5). 4759 X1 18808295916646645825216065847266150404062470629833854840155953858 4760 63091795696773741607659794828181692381790403935750135247605982648 4761 6547 4763 (=0x069fdd7c 2ec1ecbf d3cd0e27 1e8110c6 d2e478f2 aa393928 4764 64a5511e da0b8dc7 3834fd57 b5ef8527 361a8176 c6da44ee 63701c0c 4765 f49d7d13). 4767 Y1 12212945244064471634326466576257313927639904273911210953487761656 4768 77684161144865373513143868308041748047828401098060667767703779846 4769 85920 4771 (=0x2b03e68e b61581c4 9f977443 3e1ddc63 976f8f1d cdb185ee 4772 9c53328d b425973d 359bbc09 468645c4 0996a2c7 fda561be acb4d0b5 4773 745ab760). 4775 X2 58672976485086436102048679093716482249296622848351051568512020319 4776 97872083950108489407370832733527154843728068195507632886574086695 4777 12670 4779 (=0xcea6f66e e741e7b3 ee50acd4 bd6eacbf 821fab72 bf5fe85b 4780 8f614af9 04aff677 15e820b9 e4bcc159 f67a97f3 2c176d2c d9b7cdeb 4781 f753f3de). 4783 Y2 63661899992109030051219177516378471383513217472497460517936503629 4784 79522840238080543318627428149249774773108009447466292682661818280 4785 41265 4786 (=0xe0394408 ed2b4efb b6b6ac7e bc815516 fdf31a6e d32db3f9 4787 54cd8ac1 c7ddf0cc e7507688 a70f219a 57eef863 49003560 66747ca3 4788 00105a31). 4790 The representation of k and the compressed representations of Pw3 and 4791 k*Pw3 in tight MSB/msb-order are given by 4793 repr(k) =0xdcb3bbb9 e42d7aca fe62052d 902123c7 0872b984 4c1e199f 4794 7c5d37bd 1171102b c20a6352 d9c91886 29b685de 51441e84 4795 3afe2665 5251aa80; 4797 repr(Pw3) =0x80 be9f5a23 51709e13 d5ad50c2 a27be8ee 1b051970 4798 2580d5c3 c2de7f75 3010635e d89ef547 8b67dc54 16d63c5b 4799 1cc1116f dd453515 71b39b48; 4801 repr(k*Pw3) =0x00 069fdd7c 2ec1ecbf d3cd0e27 1e8110c6 d2e478f2 4802 aa393928 64a5511e da0b8dc7 3834fd57 b5ef8527 361a8176 4803 c6da44ee 63701c0c f49d7d13, 4805 where the leftmost bit of the leftmost octet indicates the parity of 4806 the Y-coordinate of the point of Wei448.-3 in question (which, in 4807 this case, are one and zero, respectively, since Y is odd and Y1 is 4808 even). See Appendix H.1 and Appendix I for further detail on 4809 (squeezed) point compression. 4811 A randomized representation (t1, t2) of the point k*Pw3 in tight MSB/ 4812 msb order is given by 4814 t1 450833060883286904091316612794941178576639837300736625958 4815 696097131313213727115363096930063001237631586932727905179 4816 306828042642854311987 4818 (=0x9ec9ba07 3fb2bb5e 9dbee995 067ce094 63601ecd 325f0930 4819 aea79cb8 745fa71d 4caa37ee f04fab67 ab2de747 4ac0a025 4820 830f4828 429cf833) 4822 t2 339205723274519707955026734148022275762579914421865223818 4823 363622725164496136165251928391223173879522521195772276587 4824 373445978123589677750 4826 (=0x7778c1f9 9d900633 d161d7ea a963ddad e9101d3f f4f04710 4827 623d2a51 6ca10133 3db9ccc3 86df9271 fbb72740 77f79dd1 4828 9aed0bfb e3bc72b6), 4830 where this representation is defined in Appendix K.5 and uses the 4831 mapping of Appendix K.3.1 with the default square root function. 4833 O.5. Example with Edwards448 4835 Pe1=(x, y), k*Pe1=(x1, y1), and (k+1)*Pe1=(x2, y2) with Edwards448: 4837 x 70320395893028961673046639985409870226249442701760956079298956688 4838 26896600999421897751877804946848997852325361659665744287620719558 4839 67733 4841 (=0xf7acf3ca b79b29c2 aa44863d 9edaeca4 8c90ad84 e460df42 4842 7dd9ab59 1bd8a844 07cb3419 59309b33 1e22bfa1 a2d37e10 e2e42a1f 4843 170f0855). 4845 y 70628706854857281648863291487942166052137991441320055237644304464 4846 58787938273165391464653528929699350754224243613996187734424074211 4847 98773 4849 (=0xf8c2f181 3bceee8e 085ecd70 d1b6aa4c ea9b95bd 8f36ab44 4850 c79e9124 1ea625b7 f9f5ec57 89cc5af2 a2eb255a b252b874 509dc0d9 4851 685841b5). 4853 x1 38125875041649701211705790554244713713134918749445854542272999596 4854 74058986304488795258334978838809456257721496105769894880185657328 4855 40277 4857 (=0x864880b9 e1900c68 ba4a545a 6fe2b161 62dcc3b9 fa218e4b 4858 feba9828 5cee5193 f2c989f6 c3b94eb6 2914dce7 b4818e4d 8fc8d51f 4859 05a13355). 4861 y1 11060653846610182753991162627427631707898421166839907726978369444 4862 53337541552746428662176632660036639406375548888849623833963458813 4863 1154 4865 (=0x03e54af3 7f4cf5e6 5f1e2acd 5c4a4554 76adc652 b198ab2a 4866 719e5aa9 ee749871 0193da82 ab6d000b f55836b1 0615653f 69514297 4867 f4459f52). 4869 x2 15620503788413497044804517304021524439062374489822547728508337937 4870 50606335270276724725939683726318058744384611584731365019896485812 4871 8760 4873 (=0x05806f71 95e85352 ef3960ac 1ff9cf6c 3c99e0ee 2e75edfc 4874 a133cafc 4a4b5fbf e4339859 c5fa123b 70ad2faf 7584ab9d 264540e7 4875 7d560978). 4877 y2 40019917514121727463122190125689377890703570698337158159153510836 4878 68442386516751945577468473801561261386285902585868517988506010293 4879 44096 4880 (=0x8cf44811 3cec6e07 d1bbe9f5 4062075c 6fec0ac5 31272dce 4881 1f446aeb d895373d e312c18d 6a345755 2861e014 0cc23158 a46ace4c 4882 9ca21b60). 4884 The representation of k and the compressed representations of Pe1 and 4885 k*Pe1 in tight LSB/lsb-order are given by 4887 repr(k) =0x01558a4a a6647f5c 2178228a 7ba16d94 6118939b 4ac65043 4888 d4088e88 bdecba3e f9987832 219d4e10 e3c48409 b4a0467f 4889 535eb427 9dddcd3b; 4891 repr(Pe1) =0xad821a16 9b03b90a 2e1d4a4d 5aa4d745 4f5a3391 ea37af9f 4892 eda46578 248979e3 22d56cf1 bda9d957 32556d8b 0eb37a10 4893 717773dc 818f431f 01; 4895 repr(k*Pe1) =0x4af9a22f e9428a96 fca6a860 8d6c1aaf d000b6d5 415bc980 4896 8e192e77 955a798e 54d5198d 4a63b56e 2aa2523a b35478fa 4897 67af32fe cf52a7c0 01, 4899 where the rightmost bit of the rightmost octet indicates the parity 4900 of the x-coordinate of the point of Edwards448 in question (which, in 4901 this case, are both one, since x and x1 are odd). See Appendix H.3 4902 and Appendix I for further detail on (squeezed) point compression. 4904 The scalar representation and (squeezed) point representation 4905 illustrated above are fully consistent with the representations 4906 specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032] 4907 requires unique representations of all elements of GF(p). 4909 A randomized representation (t1, t2) of the point k*Pe1 in tight LSB/ 4910 lsb order is given by 4912 t1 125390048858887400104074787879402833851854739339836093733 4913 734638776755983021034212058415891288350265701101219981698 4914 849086128138510420407 4916 (=0xed921f3d 6ea4e452 dd06e783 782cbeb3 c5847a79 d9e6b993 4917 bd387cf5 feeddafe af8c038d f2732362 92724d37 273eedfc 4918 f2ab2499 98a79434) 4920 t2 365268494484253132875102676783560666625109899133767696106 4921 602723958322248430160651314075127005631031993354968950936 4922 71875730862008188281 4924 (=0x9ebc28c0 86176a1a c7f0cf71 ca5f2a8f 908bb27b e85c0bbd 4925 1641c052 e542f7d3 88e18886 5afdca32 8df45408 8b6da28c 4926 0bc09d83 309ebb30), 4928 where this representation is defined in Appendix K.5 and uses the 4929 mapping of Appendix K.3.3 with the default square root function and 4930 underlying 4-isogenous mapping between Edwards448 and Curve448 of 4931 Appendix N.2. 4933 Author's Address 4935 Rene Struik 4936 Struik Security Consultancy 4938 Email: rstruik.ext@gmail.com