idnits 2.17.1 draft-ietf-lwig-curve-representations-08.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 (July 24, 2019) is 1738 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'ECC' is defined on line 735, but no explicit reference was found in the text == Unused Reference: 'SWUmap' is defined on line 780, 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 July 24, 2019 5 Expires: January 25, 2020 7 Alternative Elliptic Curve Representations 8 draft-ietf-lwig-curve-representations-08 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. 18 Requirements Language 20 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 21 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 22 "OPTIONAL" in this document are to be interpreted as described in RFC 23 2119 [RFC2119]. 25 Status of This Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at https://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on January 25, 2020. 42 Copyright Notice 44 Copyright (c) 2019 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents 49 (https://trustee.ietf.org/license-info) in effect on the date of 50 publication of this document. Please review these documents 51 carefully, as they describe your rights and restrictions with respect 52 to this document. Code Components extracted from this document must 53 include Simplified BSD License text as described in Section 4.e of 54 the Trust Legal Provisions and are provided without warranty as 55 described in the Simplified BSD License. 57 Table of Contents 59 1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 4 60 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 4 61 3. Use of Representation Switches . . . . . . . . . . . . . . . 5 62 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 6 63 4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 6 64 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 6 65 4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 7 66 4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 7 67 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 68 6. Implementation Considerations . . . . . . . . . . . . . . . . 9 69 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 10 70 8. Security Considerations . . . . . . . . . . . . . . . . . . . 11 71 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 12 72 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 73 10.1. COSE Elliptic Curves Registration . . . . . . . . . . . 12 74 10.2. COSE Algorithms Registration (1/2) . . . . . . . . . . . 12 75 10.3. COSE Algorithms Registration (2/2) . . . . . . . . . . . 13 76 10.4. JOSE Elliptic Curves Registration . . . . . . . . . . . 13 77 10.5. JOSE Algorithms Registration (1/2) . . . . . . . . . . . 13 78 10.6. JOSE Algorithms Registration (2/2) . . . . . . . . . . . 14 79 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14 80 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 14 81 12.1. Normative References . . . . . . . . . . . . . . . . . . 14 82 12.2. Informative References . . . . . . . . . . . . . . . . . 16 83 Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 17 84 A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 17 85 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 18 86 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 18 87 Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 18 88 B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 18 89 B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 20 90 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 21 91 C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 21 92 C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 22 93 C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 22 94 Appendix D. Relationship Between Curve Models . . . . . . . . . 23 95 D.1. Mapping between Twisted Edwards Curves and Montgomery 96 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 24 98 D.2. Mapping between Montgomery Curves and Weierstrass Curves 24 99 D.3. Mapping between Twisted Edwards Curves and Weierstrass 100 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 25 101 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 25 102 E.1. Curve Definition and Alternative Representations . . . . 25 103 E.2. Switching between Alternative Representations . . . . . . 26 104 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 27 105 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 29 106 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 30 107 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 30 108 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 31 109 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 32 110 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 33 111 G.1. Further Alternative Representations . . . . . . . . . . . 33 112 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 33 113 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 34 114 Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 36 115 H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 36 116 H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 36 117 H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 38 118 H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 41 119 H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 42 120 H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 42 121 H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 44 122 H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 47 123 Appendix I. Point Compression . . . . . . . . . . . . . . . . . 48 124 I.1. Point Compression for Weierstrass Curves . . . . . . . . 49 125 I.2. Point Compression for Montgomery Curves . . . . . . . . . 49 126 I.3. Point Compression for Twisted Edwards Curves . . . . . . 50 127 Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 51 128 J.1. Conversion between Bit Strings and Integers . . . . . . . 52 129 J.2. Conversion between Octet Strings and Integers (OS2I, 130 I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 52 131 J.3. Conversion between Octet Strings and Bit Strings (BS2OS, 132 OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 52 133 J.4. Conversion between Field Elements and Octet Strings 134 (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 53 135 J.5. Conversion between Elements of Z mod n and Octet Strings 136 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 53 137 J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 54 138 Appendix K. Representation Examples Curve25519 Family Members . 55 139 K.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 55 140 K.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 57 141 K.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 59 142 K.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 61 143 K.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 63 144 Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 64 145 L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 64 146 L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 64 147 L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 64 148 L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 65 149 L.3. Mapping to Curve Points . . . . . . . . . . . . . . . . . 65 150 L.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 65 151 L.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 66 152 L.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 68 153 L.4. Randomized Representation of Curve Points . . . . . . . . 68 154 Appendix M. Curve secp256k1 and Friend . . . . . . . . . . . . . 68 155 M.1. Curve Definition and Alternative Representation . . . . . 68 156 M.2. Switching Between Representations . . . . . . . . . . . . 69 157 M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 69 158 M.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 71 159 M.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 71 160 M.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 72 161 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 72 163 1. Fostering Code Reuse with New Elliptic Curves 165 It is well-known that elliptic curves can be represented using 166 different curve models. Recently, IETF standardized elliptic curves 167 that are claimed to have better performance and improved robustness 168 against "real world" attacks than curves represented in the 169 traditional "short" Weierstrass model. This document specifies an 170 alternative representation of points of Curve25519, a so-called 171 Montgomery curve, and of points of Edwards25519, a so-called twisted 172 Edwards curve, which are both specified in [RFC7748], as points of a 173 specific so-called "short" Weierstrass curve, called Wei25519. We 174 also define how to efficiently switch between these different 175 representations. 177 Use of Wei25519 allows easy definition of new signature schemes and 178 key agreement schemes already specified for traditional NIST prime 179 curves, thereby allowing easy integration with existing 180 specifications, such as NIST SP 800-56a [SP-800-56a], FIPS Pub 186-4 181 [FIPS-186-4], and ANSI X9.62-2005 [ANSI-X9.62], and fostering code 182 reuse on platforms that already implement some of these schemes using 183 elliptic curve arithmetic for curves in "short" Weierstrass form (see 184 Appendix C.1). 186 2. Specification of Wei25519 188 For the specification of Wei25519 and its relationship to Curve25519 189 and Edwards25519, see Appendix E. For further details and background 190 information on elliptic curves, we refer to the other appendices. 192 The use of Wei25519 allows reuse of existing generic code that 193 implements short-Weierstrass curves, such as the NIST curve P-256, to 194 also implement the CFRG curves Curve25519 and Edwards25519. We also 195 cater to reusing of existing code where some domain parameters may 196 have been hardcoded, thereby widening the scope of applicability. To 197 this end, we specify the short-Weierstrass curves Wei25519.2 and 198 Wei25519.-3, with hardcoded domain parameter a=2 and a=-3 (mod p), 199 respectively; see Appendix G. (Here, p is the characteristic of the 200 field over which these curves are defined.) 202 3. Use of Representation Switches 204 The curves Curve25519, Edwards25519, and Wei25519, as specified in 205 Appendix E.3, are all isomorphic, with the transformations of 206 Appendix E.2. These transformations map the specified base point of 207 each of these curves to the specified base point of each of the other 208 curves. Consequently, a public-private key pair (k,R:=k*G) for any 209 one of these curves corresponds, via these isomorphic mappings, to 210 the public-private key pair (k, R':=k*G') for each of these other 211 curves (where G and G' are the corresponding base points of these 212 curves). This observation extends to the case where one also 213 considers curve Wei25519.2 (which has hardcoded domain parameter 214 a=2), as specified in Appendix G.3, since it is isomorphic to 215 Wei25519, with the transformation of Appendix G.2, and, thereby, also 216 isomorphic to Curve25519 and Edwards25519. 218 The curve Wei25519.-3 (which has hardcoded domain parameter a=-3 (mod 219 p)) is not isomorphic to the curve Wei25519, but is related in a 220 slightly weaker sense: the curve Wei25519 is isogenous to the curve 221 Wei25519.-3, where the mapping of Appendix G.2 is an isogeny of 222 degree l=47 that maps the specified base point G of Wei25519 to the 223 specified base point G' of Wei25519.-3 and where the so-called dual 224 isogeny (which maps Wei25519.-3 to Wei25519) has the same degree 225 l=47, but does not map G' to G, but to a fixed multiple hereof, where 226 this multiple is l=47. Consequently, a public-private key pair 227 (k,R:=k*G) for Wei25519 corresponds to the public-private key pair 228 (k, R':= k*G') for Wei25519.-3 (via the l-isogeny), whereas the 229 public-private key pair (k, R':=k*G') corresponds to the public- 230 private key pair (l*k, l*R=l*k*G) of Wei25519 (via the dual isogeny). 231 (Note the extra scalar l=47 here.) 233 Alternative curve representations can, therefore, be used in any 234 cryptographic scheme that involves computations on public-private key 235 pairs, where implementations may carry out computations on the 236 corresponding object for the isomorphic or isogenous curve and 237 convert the results back to the original curve (where, in case this 238 involves an l-isogeny, one has to take into account the factor l). 239 This includes use with elliptic-curve based signature schemes and key 240 agreement and key transport schemes. 242 For some examples of curve computations on each of the curves 243 specified in Appendix E.3 and Appendix G.3, see Appendix K. 245 4. Examples 247 4.1. Implementation of X25519 249 RFC 7748 [RFC7748] specifies the use of X25519, a co-factor Diffie- 250 Hellman key agreement scheme, with instantiation by the Montgomery 251 curve Curve25519. This key agreement scheme was already specified in 252 Section 6.1.2.2 of NIST SP 800-56a [SP-800-56a] for elliptic curves 253 in short Weierstrass form. Hence, one can implement X25519 using 254 existing NIST routines by (1) representing a point of the Montgomery 255 curve Curve25519 as a point of the Weierstrass curve Wei25519; (2) 256 instantiating the co-factor Diffie-Hellman key agreement scheme of 257 the NIST specification with the resulting point and Wei25519 domain 258 parameters; (3) representing the key resulting from this scheme 259 (which is a point of the curve Wei25519 in Weierstrass form) as a 260 point of the Montgomery curve Curve25519. The representation change 261 can be implemented via a simple wrapper and involves a single modular 262 addition (see Appendix D.2). Using this method has the additional 263 advantage that one can reuse the public-private key pair routines, 264 domain parameter validation, and other checks that are already part 265 of the NIST specifications. A NIST-compliant version of co-factor 266 Diffie-Hellman key agreement (denoted by ECDH25519) results if one 267 keeps inputs (key contributions) and outputs (shared key) in the 268 short-Weierstrass format (and, hence, does not perform Step (3) 269 above). 271 NOTE: At this point, it is unclear whether this implies that a FIPS- 272 accredited module implementing co-factor Diffie-Hellman for, e.g., 273 P-256 would also extend this accreditation to X25519. 275 4.2. Implementation of Ed25519 277 RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature 278 scheme, with instantiation by the twisted Edwards curve Edwards25519. 279 One can implement the computation of the ephemeral key pair for 280 Ed25519 using an existing Montgomery curve implementation by (1) 281 generating a public-private key pair (k, R':=k*G') for Curve25519; 282 (2) representing this public-private key as the pair (k, R:=k*G) for 283 Ed25519. As before, the representation change can be implemented via 284 a simple wrapper. Note that the Montgomery ladder specified in 285 Section 5 of RFC7748 [RFC7748] does not provide sufficient 286 information to reconstruct R':=(u, v) (since it does not compute the 287 v-coordinate of R'). However, this deficiency can be remedied by 288 using a slightly modified version of the Montgomery ladder that 289 includes reconstruction of the v-coordinate of R':=k*G' at the end of 290 hereof (which uses the v-coordinate of the base point of Curve25519 291 as well). For details, see Appendix C.1. 293 4.3. Specification of ECDSA25519 295 FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and 296 can be instantiated not just with the NIST prime curves, but also 297 with other Weierstrass curves (that satisfy additional cryptographic 298 criteria). In particular, one can instantiate this scheme with the 299 Weierstrass curve Wei25519 and the hash function SHA-256, where an 300 implementation may generate an ephemeral public-private key pair for 301 Wei25519 by (1) internally carrying out these computations on the 302 Montgomery curve Curve25519, the twisted Edwards curve Edwards25519, 303 or even the Weierstrass curve Wei25519.-3 (with hardcoded a=-3 domain 304 parameter); (2) representing the result as a key pair for the curve 305 Wei25519. Note that, in either case, one can implement these schemes 306 with the same representation conventions as used with existing NIST 307 specifications, including bit/byte-ordering, compression functions, 308 and the-like. This allows generic implementations of ECDSA with the 309 hash function SHA-256 and with the NIST curve P-256 or with the curve 310 Wei25519 specified in this specification to reuse the same 311 implementation (instantiated with, respectively, the NIST P-256 312 elliptic curve domain parameters or with the domain parameters of 313 curve Wei25519 specified in Appendix E). 315 4.4. Other Uses 317 Any existing specification of cryptographic schemes using elliptic 318 curves in Weierstrass form and that allows introduction of a new 319 elliptic curve (here: Wei25519) is amenable to similar constructs, 320 thus spawning "offspring" protocols, simply by instantiating these 321 using the new curve in "short" Weierstrass form, thereby allowing 322 code and/or specifications reuse and, for implementations that so 323 desire, carrying out curve computations "under the hood" on 324 Montgomery curve and twisted Edwards curve cousins hereof (where 325 these exist). This would simply require definition of a new object 326 identifier for any such envisioned "offspring" protocol. This could 327 significantly simplify standardization of schemes and help keeping 328 the resource and maintenance cost of implementations supporting 329 algorithm agility [RFC7696] at bay. 331 5. Caveats 333 The examples above illustrate how specifying the Weierstrass curve 334 Wei25519 (or any curve in short-Weierstrass format, for that matter) 335 may facilitate reuse of existing code and may simplify standards 336 development. However, the following caveats apply: 338 1. Wire format. The transformations between alternative curve 339 representations can be implemented at negligible relative 340 incremental cost if the curve points are represented as affine 341 points. If a point is represented in compressed format, 342 conversion usually requires a costly point decompression step. 343 This is the case in [RFC7748], where the inputs to the co-factor 344 Diffie-Hellman scheme X25519, as well as its output, are 345 represented in u-coordinate-only format. This is also the case 346 in [RFC8032], where the EdDSA signature includes the ephemeral 347 signing key represented in compressed format (see Appendix I for 348 details); 350 2. Representation conventions. While elliptic curve computations 351 are carried-out in a field GF(q) and, thereby, involve large 352 integer arithmetic, these integers are represented as bit- and 353 byte-strings. Here, [RFC8032] uses least-significant-byte 354 (LSB)/least-significant-bit (lsb) conventions, whereas [RFC7748] 355 uses LSB/most-significant-bit (msb) conventions, and where most 356 other cryptographic specifications, including NIST SP800-56a 357 [SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005 358 [ANSI-X9.62] use MSB/msb conventions. Since each pair of 359 conventions is different (see Appendix J for details and 360 Appendix K for examples), this does necessitate bit/byte 361 representation conversions; 363 3. Domain parameters. All traditional NIST curves are Weierstrass 364 curves with domain parameter a=-3, while all Brainpool curves 365 [RFC5639] are isomorphic to a Weierstrass curve of this form. 366 Thus, one can expect there to be existing Weierstrass 367 implementations with a hardcoded a=-3 domain parameter 368 ("Jacobian-friendly"). For those implementations, including the 369 curve Wei25519 as a potential vehicle for offering support for 370 the CFRG curves Curve25519 and Edwards25519 is not possible, 371 since not of the required form. Instead, one has to implement 372 Wei25519.-3 and include code that implements the isogeny and dual 373 isogeny from and to Wei25519. This isogeny has degree l=47 and 374 requires roughly 9kB of storage for isogeny and dual-isogeny 375 computations (see the tables in Appendix H). Note that storage 376 would have reduced to a single 64-byte table if only the curve 377 would have been generated so as to be isomorphic to a Weierstrass 378 curve with hardcoded a=-3 parameter (this corresponds to l=1). 380 NOTE 1: An example of a Montgomery curve defined over the same 381 field as Curve25519 that is isomorphic to a Weierstrass curve 382 with hardcoded a=-3 parameter is the Montgomery curve M_{A,B} 383 with B=1 and A=-1410290 (or, if one wants the base point to still 384 have u-coordinate u=9, with B=1 and A=-3960846). In either case, 385 the resulting curve has the same cryptographic properties as 386 Curve25519 and the same performance (which relies on A being a 387 3-byte integer, as is the case with the domain parameter A=486662 388 of Curve25519, and using the same special prime p=2^255-19), 389 while at the same time being "Jacobian-friendly" by design. 391 NOTE 2: While an implementation of Curve25519 via an isogenous 392 Weierstrass curve with domain parameter a=-3 requires a 393 relatively large table (of size roughly 9kB), for the quadratic 394 twist of Curve25519 (i.e., the Montgomery curve M_{A,B'} with 395 A=486662 and B'=2) this implementation approach only requires a 396 table of size less than 0.5kB (over 20x smaller), solely due to 397 the fact that it is l-isogenous to a Weierstrass curve with a=-3 398 parameter with relatively small parameter l=2 (compared to l=47, 399 as is the case with Curve25519 itself). 401 6. Implementation Considerations 403 The efficiency of elliptic curve arithmetic is primarily determined 404 by the efficiency of its group operations (see Appendix C). Numerous 405 optimized formulae exist, such as the use of so-called Montgomery 406 ladders with Montgomery curves [Mont-Ladder] or with Weierstrass 407 curves [Wei-Ladder], the use of hardcoded a=-3 domain parameter for 408 Weierstrass curves [ECC-Isogeny], and the use of hardcoded a=-1 409 domain parameters for twisted Edwards curves [tEd-Formulas]. These 410 all target reduction of the number of finite field operations 411 (primarily, finite field multiplications and squarings). Other 412 optimizations target more efficient modular reductions underlying 413 these finite field operations, by specifying curves defined over a 414 field GF(q), where the field size q has a special form or a specific 415 bit-size (typically, close to a multiple of a machine word). 416 Depending on the implementation strategy, the bit-size of q may also 417 facilitate reduced so-called "carry-effects" of integer arithmetic. 419 Most curves use a combination of these design philosophies. All NIST 420 curves [FIPS-186-4] and Brainpool curves [RFC5639] are Weierstrass 421 curves with a=-3 domain parameter, thus facilitating more efficient 422 elliptic curve group operations (via so-called Jacobian coordinates). 423 The NIST curves and the Montgomery curve Curve25519 are defined over 424 prime fields, where the prime number has a special form, whereas the 425 Brainpool curves - by design - use a generic prime number. None of 426 the NIST curves, nor the Brainpool curves, can be expressed as 427 Montgomery or twisted Edwards curves, whereas - conversely - 428 Montgomery curves and twisted curves can be expressed as Weierstrass 429 curves. 431 While use of Wei25519 allows reuse of existing generic code that 432 implements short Weierstrass curves, such as the NIST curve P-256, to 433 also implement the CFRG curves Curve25519 or Edwards25519, this 434 obviously does not result in an implementation of these CFRG curves 435 that exploits the specific structure of the underlying field or other 436 specific domain parameters (since generic). Reuse of generic code, 437 therefore, may result in a less computationally efficient curve 438 implementation than would have been possible if the implementation 439 had specifically targeted Curve25519 or Edwards25519 alone (with the 440 overall cost differential estimated to be somewhere in the interval 441 [1.00-1.25]). If existing generic code offers hardware support, 442 however, the overall speed may still be larger, since less efficient 443 formulae for curve arithmetic using Wei25519 curves compared to a 444 direct implementation of Curve25519 or Edwards25519 arithmetic may be 445 more than compensated for by faster implementations of the finite 446 field arithmetic itself. 448 Overall, one should consider not just code reuse and computational 449 efficiency, but also development and maintenance cost, and, e.g, the 450 cost of providing effective implementation attack countermeasures 451 (see also Section 8). 453 7. Implementation Status 455 [Note to the RFC Editor] Please remove this entire section before 456 publication, as well as the reference to [RFC7942]. 458 This section records the status of known implementations of the 459 protocol defined by this specification at the time of posting of this 460 Internet-Draft, and is based on a proposal described in [RFC7942]. 461 The description of implementations in this section is intended to 462 assist the IETF in its decision processes in progressing drafts to 463 RFCs. Please note that the listing of any individual implementation 464 here does not imply endorsement by the IETF. Furthermore, no effort 465 has been spent to verify the information presented here that was 466 supplied by IETF contributors. This is not intended as, and must not 467 be construed to be, a catalog of available implementations or their 468 features. Readers are advised to note that other implementations may 469 exist. 471 According to [RFC7942], "this will allow reviewers and working groups 472 to assign due consideration to documents that have the benefit of 473 running code, which may serve as evidence of valuable experimentation 474 and feedback that have made the implemented protocols more mature. 475 It is up to the individual working groups to use this information as 476 they see fit. 478 Nikolas Rosener evaluated the performance of switching between 479 different curve models in his Master's thesis [Rosener]. For an 480 implementation of Wei25519, see . 482 For support of this curve in tinydtls, see . 485 According to , an 486 implementation of Wei25519 on the Kinets LTC ECC HW platform improves 487 the performance by over a factor ten compared to a stand-alone 488 implementation of Curve25519 without hardware support. 490 The signature scheme ECDSA25519 (see Section 4.3) is supported in 491 . 493 8. Security Considerations 495 The different representations of elliptic curve points discussed in 496 this document are all obtained using a publicly known transformation, 497 which is either an isomorphism or a low-degree isogeny. It is well- 498 known that an isomorphism maps elliptic curve points to equivalent 499 mathematical objects and that the complexity of cryptographic 500 problems (such as the discrete logarithm problem) of curves related 501 via a low-degree isogeny are tightly related. Thus, the use of these 502 techniques does not negatively impact cryptographic security of 503 elliptic curve operations. 505 As to implementation security, reusing existing high-quality code or 506 generic implementations that have been carefully designed to 507 withstand implementation attacks for one curve model may allow a more 508 economical way of development and maintenance than providing this 509 same functionality for each curve model separately (if multiple curve 510 models need to be supported) and, otherwise, may allow a more gradual 511 migration path, where one may initially use existing and accredited 512 chipsets that cater to the pre-dominant curve model used in practice 513 for over 15 years. 515 Elliptic curves are generally used as objects in a broader 516 cryptographic scheme that may include processing steps that depend on 517 the representation conventions used (such as with, e.g., key 518 derivation following key establishment). These schemes should 519 (obviously) unambiguously specify fixed representations of each input 520 and output (e.g., representing each elliptic curve point always in 521 short-Weierstrass form and in uncompressed tight MSB/msb format). 523 To prevent cross-protocol attacks, private keys SHOULD only be used 524 with one cryptographic scheme. Private keys MUST NOT be reused 525 between Ed25519 (as specified in [RFC8032]) and ECDSA25519 (as 526 specified in Section 4.3). 528 To prevent intra-protocol cross-instantiation attacks, ephemeral 529 private keys MUST NOT be reused between instantiations of ECDSA25519. 531 9. Privacy Considerations 533 The transformations between different curve models described in this 534 document are publicly known and, therefore, do not affect privacy 535 provisions. 537 The randomized representation described in Appendix L.4 allows random 538 curve points to be represented as random pairs of field elements, 539 thereby assisting in obfuscating the presence of these curve points 540 in some applications. 542 10. IANA Considerations 544 An object identifier is requested for curve Wei25519 and its use with 545 ECDSA and co-factor ECDH, using the representation conventions of 546 this document. 548 There is *currently* no further IANA action required for this 549 document. New object identifiers would be required in case one 550 wishes to specify one or more of the "offspring" protocols 551 exemplified in Section 4.4. 553 10.1. COSE Elliptic Curves Registration 555 This section registers the following value in the IANA "COSE Elliptic 556 Curves" registry [IANA.COSE.Curves]. 558 Name: Wei25519; 560 Value: TBD (Requested value: -1); 562 Key Type: EC2 or OKP (where OKP uses the squeezed MSB/msb 563 representation of this specification); 565 Description: short-Weierstrass curve Wei25519; 567 Reference: Appendix E.3 of this specification; 569 Recommended: Yes. 571 (Note that The "kty" value for Wei25519 may be "OKP" or "EC2".) 573 10.2. COSE Algorithms Registration (1/2) 575 This section registers the following value in the IANA "COSE 576 Algorithms" registry [IANA.COSE.Algorithms]. 578 Name: ECDSA25519; 579 Value: TBD (Requested value: -1); 581 Description: ECDSA w/ SHA-256 and curve Wei25519; 583 Reference: Section 4.3 of this specification; 585 Recommended: Yes. 587 10.3. COSE Algorithms Registration (2/2) 589 This section registers the following value in the IANA "COSE 590 Algorithms" registry [IANA.COSE.Algorithms]. 592 Name: ECDH25519; 594 Value: TBD (Requested value: -2); 596 Description: NIST-compliant co-factor Diffie-Hellman w/ curve 597 Wei25519 and key derivation function HKDF SHA256; 599 Reference: Section 4.1 of this specification (for key derivation, 600 see Section 11.1 of [RFC8152]); 602 Recommended: Yes. 604 10.4. JOSE Elliptic Curves Registration 606 This section registers the following value in the IANA "JSON Web Key 607 Elliptic Curve" registry [IANA.JOSE.Curves]. 609 Curve Name: Wei25519; 611 Curve Description: short-Weierstrass curve Wei25519; 613 JOSE Implementation Requirements: optional; 615 Change Controller: IANA; 617 Reference: Appendix E.3 of this specification. 619 10.5. JOSE Algorithms Registration (1/2) 621 This section registers the following value in the IANA "JSON Web 622 Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. 624 Algorithm Name: ECDSA25519; 626 Algorithm Description: ECDSA w/ SHA-256 and curve Wei25519; 627 Algorithm Usage Locations: alg; 629 JOSE Implementation Requirements: optional; 631 Change Controller: IANA; 633 Reference: Section 4.3 of this specification; 635 Algorithm Analysis Documents: Section 4.3 of this specification. 637 10.6. JOSE Algorithms Registration (2/2) 639 This section registers the following value in the IANA "JSON Web 640 Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms]. 642 Algorithm Name: ECDH25519; 644 Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/ 645 curve Wei25519 and key derivation function HKDF SHA256; 647 Algorithm Usage Locations: alg; 649 Change Controller: IANA; 651 Reference: Section 4.1 of this specification (for key derivation, 652 see Section 5 of [SP-800-56c]); 654 Algorithm Analysis Documents: Section 4.1 of this specification (for 655 key derivation, see Section 5 of [SP-800-56c]). 657 11. Acknowledgements 659 Thanks to Nikolas Rosener for discussions surrounding implementation 660 details of the techniques described in this document and to Phillip 661 Hallam-Baker for triggering inclusion of verbiage on the use of 662 Montgomery ladders with recovery of the y-coordinate. Thanks to 663 Stanislav Smyshlyaev and Vasily Nikolaev for their careful reviews. 665 12. References 667 12.1. Normative References 669 [ANSI-X9.62] 670 ANSI X9.62-2005, "Public Key Cryptography for the 671 Financial Services Industry: The Elliptic Curve Digital 672 Signature Algorithm (ECDSA)", American National Standard 673 for Financial Services, Accredited Standards Committee X9, 674 Inc, Anapolis, MD, 2005. 676 [FIPS-186-4] 677 FIPS 186-4, "Digital Signature Standard (DSS), Federal 678 Information Processing Standards Publication 186-4", US 679 Department of Commerce/National Institute of Standards and 680 Technology, Gaithersburg, MD, July 2013. 682 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 683 Requirement Levels", BCP 14, RFC 2119, 684 DOI 10.17487/RFC2119, March 1997, 685 . 687 [RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography 688 (ECC) Brainpool Standard Curves and Curve Generation", 689 RFC 5639, DOI 10.17487/RFC5639, March 2010, 690 . 692 [RFC7696] Housley, R., "Guidelines for Cryptographic Algorithm 693 Agility and Selecting Mandatory-to-Implement Algorithms", 694 BCP 201, RFC 7696, DOI 10.17487/RFC7696, November 2015, 695 . 697 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 698 for Security", RFC 7748, DOI 10.17487/RFC7748, January 699 2016, . 701 [RFC7942] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 702 Code: The Implementation Status Section", BCP 205, 703 RFC 7942, DOI 10.17487/RFC7942, July 2016, 704 . 706 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 707 Signature Algorithm (EdDSA)", RFC 8032, 708 DOI 10.17487/RFC8032, January 2017, 709 . 711 [RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)", 712 RFC 8152, DOI 10.17487/RFC8152, July 2017, 713 . 715 [SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0", 716 Standards for Efficient Cryptography, , June 2009. 718 [SEC2] SEC2, "SEC 2: Elliptic Curve Cryptography, Version 2.0", 719 Standards for Efficient Cryptography, , January 2010. 721 [SP-800-56a] 722 NIST SP 800-56a, "Recommendation for Pair-Wise Key 723 Establishment Schemes Using Discrete Log Cryptography, 724 Revision 3", US Department of Commerce/National Institute 725 of Standards and Technology, Gaithersburg, MD, April 2018. 727 [SP-800-56c] 728 NIST SP 800-56c, "Recommendation for Key-Derivation 729 Methods in Key-Establishment Schemes, Revision 1", US 730 Department of Commerce/National Institute of Standards and 731 Technology, Gaithersburg, MD, April 2018. 733 12.2. Informative References 735 [ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in 736 Cryptography", Cambridge University Press, Lecture Notes 737 Series 265, July 1999. 739 [ECC-Isogeny] 740 E. Brier, M. Joye, "Fast Point Multiplication on Elliptic 741 Curves through Isogenies", AAECC, Lecture Notes in 742 Computer Science, Vol. 2643, New York: Springer-Verlag, 743 2003. 745 [GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to 746 Elliptic Curve Cryptography", New York: Springer-Verlag, 747 2004. 749 [IANA.COSE.Algorithms] 750 IANA, "COSE Algorithms", IANA, 751 https://www.iana.org/assignments/cose/ 752 cose.xhtml#algorithms. 754 [IANA.COSE.Curves] 755 IANA, "COSE Elliptic Curves", IANA, 756 https://www.iana.org/assignments/cose/cose.xhtml#elliptic- 757 curves. 759 [IANA.JOSE.Algorithms] 760 IANA, "JSON Web Signature and Encryption Algorithms", 761 IANA, 762 https://www.iana.org/assignments/jose/jose.xhtml#web- 763 signature-encryption-algorithms. 765 [IANA.JOSE.Curves] 766 IANA, "JSON Web Key Elliptic Curve", IANA, 767 https://www.iana.org/assignments/jose/jose.xhtml#web-key- 768 elliptic-curve. 770 [Mont-Ladder] 771 P.L. Montgomery, "Speeding the Pollard and Elliptic Curve 772 Methods of Factorization", Mathematics of 773 Computation, Vol. 48, 1987. 775 [Rosener] N. Rosener, "Evaluating the Performance of Transformations 776 Between Curve Representations in Elliptic Curve 777 Cryptography for Constrained Device Security", 778 M.Sc. Universitat Bremen, August 2018. 780 [SWUmap] E. Brier, J-S. Coron, Th. Icart, D. Madore, H. Randriam, 781 M. Tibouchi, "Efficient Indifferentiable Hashing into 782 Ordinary Elliptic Curves", CRYPTO 2010, Lecture Notes in 783 Computer Science, Vol. 6223, New York: Springer-Verlag, 784 2010. 786 [tEd] D.J. Bernstein, P. Birkner, M. Joye, T. Lange, C. Peters, 787 "Twisted Edwards Curves", Africacrypt 2008, Lecture Notes 788 in Computer Science, Vol. 5023, New York: Springer-Verlag, 789 2008. 791 [tEd-Formulas] 792 H. Hisil, K.K.H. Wong, G. Carter, E. Dawson, "Twisted 793 Edwards Curves Revisited", ASIACRYPT 2008, Lecture Notes 794 in Computer Science, Vol. 5350, New York: Springer-Verlag, 795 2008. 797 [Tibouchi] 798 M. Tibouchi, "Elligator Squared -- Uniform Points on 799 Elliptic Curves of Prime Order as Uniform Random Strings", 800 Financial Cryptography 2014, Lecture Notes in Computer 801 Science, Vol. 8437, New York: Springer-Verlag, 2014. 803 [Wei-Ladder] 804 T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve 805 Multiplication Resistant Against Side Channel Attacks", 806 Centre for Applied Cryptographic Research, Corr 2002-03, 807 2002. 809 Appendix A. Some (non-Binary) Elliptic Curves 811 A.1. Curves in short-Weierstrass Form 813 Let GF(q) denote the finite field with q elements, where q is an odd 814 prime power and where q is not divisible by three. Let W_{a,b} be 815 the Weierstrass curve with defining equation Y^2 = X^3 + a*X + b, 816 where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is 817 nonzero. The points of W_{a,b} are the ordered pairs (X, Y) whose 818 coordinates are elements of GF(q) and that satisfy the defining 819 equation (the so-called affine points), together with the special 820 point O (the so-called "point at infinity"). This set forms a group 821 under addition, via the so-called "secant-and-tangent" rule, where 822 the point at infinity serves as the identity element. See 823 Appendix C.1 for details of the group operation. 825 A.2. Montgomery Curves 827 Let GF(q) denote the finite field with q elements, where q is an odd 828 prime power. Let M_{A,B} be the Montgomery curve with defining 829 equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q) 830 and where A is unequal to (+/-)2 and where B is nonzero. The points 831 of M_{A,B} are the ordered pairs (u, v) whose coordinates are 832 elements of GF(q) and that satisfy the defining equation (the so- 833 called affine points), together with the special point O (the so- 834 called "point at infinity"). This set forms a group under addition, 835 via the so-called "secant-and-tangent" rule, where the point at 836 infinity serves as the identity element. See Appendix C.2 for 837 details of the group operation. 839 A.3. Twisted Edwards Curves 841 Let GF(q) denote the finite field with q elements, where q is an odd 842 prime power. Let E_{a,d} be the twisted Edwards curve with defining 843 equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct 844 nonzero elements of GF(q). The points of E_{a,d} are the ordered 845 pairs (x, y) whose coordinates are elements of GF(q) and that satisfy 846 the defining equation (the so-called affine points). It can be shown 847 that this set forms a group under addition if a is a square in GF(q), 848 whereas d is not, where the point O:=(0, 1) serves as the identity 849 element. (Note that the identity element satisfies the defining 850 equation.) See Appendix C.3 for details of the group operation. 852 An Edwards curve is a twisted Edwards curve with a=1. 854 Appendix B. Elliptic Curve Nomenclature and Finite Fields 856 B.1. Elliptic Curve Nomenclature 858 Each curve defined in Appendix A forms a commutative group under 859 addition (denoted by '+'). In Appendix C we specify the group laws, 860 which depend on the curve model in question. For completeness, we 861 here include some common elliptic curve nomenclature and basic 862 properties (primarily so as to keep this document self-contained). 863 These notions are mainly used in Appendix E and Appendix G and not 864 essential for our exposition. This section can be skipped at first 865 reading. 867 Any point P of a curve E is a generator of the cyclic subgroup 868 (P):={k*P | k = 0, 1, 2,...} of the curve. (Here, k*P denotes the 869 sum of k copies of P, where 0*P is the identity element O of the 870 curve.) If (P) has cardinality l, then l is called the order of P. 871 The order of curve E is the cardinality of the set of its points, 872 commonly denoted by |E|. A curve is cyclic if it is generated by some 873 point of this curve. All curves of prime order are cyclic, while all 874 curves of order h*n, where n is a large prime number and where h is a 875 small number (the so-called co-factor), have a large cyclic subgroup 876 of prime order n. In this case, a generator of order n is called a 877 base point, commonly denoted by G. A point of order dividing h is 878 said to be in the small subgroup. For curves of prime order, this 879 small subgroup is the singleton set, consisting of only the identity 880 element O. If a point is not in the small subgroup, it has order at 881 least n. 883 If R is a point of the curve that is also contained in (P), there is 884 a unique integer k in the interval [0, l-1] so that R=k*P, where l is 885 the order of P. This number is called the discrete logarithm of R to 886 the base P. The discrete logarithm problem is the problem of finding 887 the discrete logarithm of R to the base P for any two points P and R 888 of the curve, if such a number exists. 890 If P is a fixed base point G of the curve, the pair (k, R:=k*G) is 891 commonly called a public-private key pair, the integer k the private 892 key, and the point R the corresponding public key. The private key k 893 can be represented as an integer in the interval [0,n-1], where G has 894 order n. 896 In this document, a quadratic twist of a curve E defined over a field 897 GF(q) is a curve E' related to E, with cardinality |E'|, 898 where |E|+|E'|=2*(q+1). If E is a curve in one of the curve models 899 specified in this document, a quadratic twist of this curve can be 900 expressed using the same curve model, although (naturally) with its 901 own curve parameters. Two curves E and E' defined over a field GF(q) 902 are said to be isogenous if these have the same order and are said to 903 be isomorphic if these have the same group structure. Note that 904 isomorphic curves have necessarily the same order and are, thus, a 905 special type of isogenous curves. Further details are out of scope. 907 Weierstrass curves can have prime order, whereas Montgomery curves 908 and twisted Edwards curves always have an order that is a multiple of 909 four (and, thereby, a small subgroup of cardinality four). 911 An ordered pair (x, y) whose coordinates are elements of GF(q) can be 912 associated with any ordered triple of the form [x*z: y*z: z], where z 913 is a nonzero element of GF(q), and can be uniquely recovered from 914 such a representation. The latter representation is commonly called 915 a representation in projective coordinates. Sometimes, yet other 916 representations are useful (e.g., representation in Jacobian 917 coordinates). Further details are out of scope. 919 The group laws in Appendix C are mostly expressed in terms of affine 920 points, but can also be expressed in terms of the representation of 921 these points in projective coordinates, thereby allowing clearing of 922 denominators. The group laws may also involve non-affine points 923 (such as the point at infinity O of a Weierstrass curve or of a 924 Montgomery curve). Those can also be represented in projective 925 coordinates. Further details are out of scope. 927 B.2. Finite Fields 929 The field GF(q), where q is an odd prime power, is defined as 930 follows. 932 If p is a prime number, the field GF(p) consists of the integers in 933 the interval [0,p-1] and two binary operations on this set: addition 934 and multiplication modulo p. 936 If q=p^m and m>0, the field GF(q) is defined in terms of an 937 irreducible polynomial f(z) in z of degree m with coefficients in 938 GF(p) (i.e., f(z) cannot be written as the product of two polynomials 939 in z of lower degree with coefficients in GF(p)): in this case, GF(q) 940 consists of the polynomials in z of degree smaller than m with 941 coefficients in GF(p) and two binary operations on this set: 942 polynomial addition and polynomial multiplication modulo the 943 irreducible polynomial f(z). By definition, each element x of GF(q) 944 is a polynomial in z of degree smaller than m and can, therefore, be 945 uniquely represented as a vector (x_{m-1}, x_{m-2}, ..., x_1, x_0) of 946 length m with coefficients in GF(p), where x_i is the coefficient of 947 z^i of polynomial x. Note that this representation depends on the 948 irreducible polynomial f(z) of the field GF(p^m) in question (which 949 is often fixed in practice). Note that GF(q) contains the prime 950 field GF(p) as a subset. If m=1, we always pick f(z):=z, so that the 951 definitions of GF(p) and GF(p^1) above coincide. If m>1, then GF(q) 952 is called a (nontrivial) extension field over GF(p). The number p is 953 called the characteristic of GF(q). 955 A field element y is called a square in GF(q) if it can be expressed 956 as y:=x^2 for some x in GF(q); it is called a non-square in GF(q) 957 otherwise. If y is a square in GF(q), we denote by sqrt(y) one of 958 its square roots (the other one being -sqrt(y)). For methods for 959 computing square roots and inverses in GF(q) - if these exist - see 960 Appendix L.1 and Appendix L.2, respectively. For methods for mapping 961 a nonzero field element that is not a square in GF(q) to a point of a 962 curve, see Appendix L.3. 964 NOTE: The curves in Appendix E and Appendix G are all defined over a 965 prime field GF(p), thereby reducing all operations to simple modular 966 integer arithmetic. Strictly speaking we could, therefore, have 967 refrained from introducing extension fields. Nevertheless, we 968 included the more general exposition, so as to accommodate potential 969 introduction of new curves that are defined over a (nontrivial) 970 extension field at some point in the future. This includes curves 971 proposed for post-quantum isogeny-based schemes, which are defined 972 over a quadratic extension field (i.e., where q:=p^2), and elliptic 973 curves used with pairing-based cryptography. The exposition in 974 either case is almost the same and now automatically yields, e.g., 975 data conversion routines for any finite field object (see 976 Appendix J). Readers not interested in this, could simply view all 977 fields as prime fields. 979 Appendix C. Elliptic Curve Group Operations 981 C.1. Group Law for Weierstrass Curves 983 For each point P of the Weierstrass curve W_{a,b}, the point at 984 infinity O serves as identity element, i.e., P + O = O + P = P. 986 For each affine point P:=(X, Y) of the Weierstrass curve W_{a,b}, the 987 point -P is the point (X, -Y) and one has P + (-P) = O. 989 Let P1:=(X1, Y1) and P2:=(X2, Y2) be distinct affine points of the 990 Weierstrass curve W_{a,b} and let Q:=P1 + P2, where Q is not the 991 identity element. Then Q:=(x, y), where 993 X + X1 + X2 = lambda^2 and Y + Y1 = lambda*(X1 - X), where 995 lambda:= (Y2 - Y1)/(X2 - X1). 997 Let P:=(X1, Y1) be an affine point of the Weierstrass curve W_{a,b} 998 and let Q:=2*P, where Q is not the identity element. Then Q:=(X, Y), 999 where 1001 X + 2*X1 = lambda^2 and Y + Y1 = lambda*(X1 - X), where 1003 lambda:=(3*X1^2 + a)/(2*Y1). 1005 From the group laws above it follows that if P=(X, Y), P1=k*P=(X1, 1006 Y1), and P2=(k+1)*P=(X2, Y2) are distinct affine points of the 1007 Weierstrass curve W_{a,b} and if Y is nonzero, then the Y-coordinate 1008 of P1 can be expressed in terms of the X-coordinates of P, P1, and 1009 P2, and the Y-coordinate of P, as 1011 Y1=((X*X1+a)*(X+X1)+2*b-X2*(X-X1)^2)/(2*Y). 1013 This property allows recovery of the Y-coordinate of a point P1=k*P 1014 that is computed via the so-called Montgomery ladder, where P is an 1015 affine point with nonzero Y-coordinate (i.e., it does not have order 1016 two). Further details are out of scope. 1018 C.2. Group Law for Montgomery Curves 1020 For each point P of the Montgomery curve M_{A,B}, the point at 1021 infinity O serves as identity element, i.e., P + O = O + P = P. 1023 For each affine point P:=(u, v) of the Montgomery curve M_{A,B}, the 1024 point -P is the point (u, -v) and one has P + (-P) = O. 1026 Let P1:=(u1, v1) and P2:=(u2, v2) be distinct affine points of the 1027 Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the 1028 identity element. Then Q:=(u, v), where 1030 u + u1 + u2 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), where 1032 lambda:=(v2 - v1)/(u2 - u1). 1034 Let P:=(u1, v1) be an affine point of the Montgomery curve M_{A,B} 1035 and let Q:=2*P, where Q is not the identity element. Then Q:=(u, v), 1036 where 1038 u + 2*u1 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), where 1040 lambda:=(3*u1^2 + 2*A*u1+1)/(2*B*v1). 1042 From the group laws above it follows that if P=(u, v), P1=k*P=(u1, 1043 v1), and P2=(k+1)*P=(u2, v2) are distinct affine points of the 1044 Montgomery curve M_{A,B} and if v is nonzero, then the v-coordinate 1045 of P1 can be expressed in terms of the u-coordinates of P, P1, and 1046 P2, and the v-coordinate of P, as 1048 v1=((u*u1+1)*(u+u1+2*A)-2*A-u2*(u-u1)^2)/(2*B*v). 1050 This property allows recovery of the v-coordinate of a point P1=k*P 1051 that is computed via the so-called Montgomery ladder, where P is an 1052 affine point with nonzero v-coordinate (i.e., it does not have order 1053 one or two). Further details are out of scope. 1055 C.3. Group Law for Twisted Edwards Curves 1057 Note: The group laws below hold for twisted Edwards curves E_{a,d} 1058 where a is a square in GF(q), whereas d is not. In this case, the 1059 addition formulae below are defined for each pair of points, without 1060 exceptions. Generalizations of this group law to other twisted 1061 Edwards curves are out of scope. 1063 For each point P of the twisted Edwards curve E_{a,d}, the point 1064 O:=(0,1) serves as identity element, i.e., P + O = O + P = P. 1066 For each point P:=(x, y) of the twisted Edwards curve E_{a,d}, the 1067 point -P is the point (-x, y) and one has P + (-P) = O. 1069 Let P1:=(x1, y1) and P2:=(x2, y2) be points of the twisted Edwards 1070 curve E_{a,d} and let Q:=P1 + P2. Then Q:=(x, y), where 1072 x = (x1*y2 + x2*y1)/(1 + d*x1*x2*y1*y2) and 1074 y = (y1*y2 - a*x1*x2)/(1 - d*x1*x2*y1*y2). 1076 Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and 1077 let Q:=2*P. Then Q:=(x, y), where 1079 x = (2*x1*y1)/(1 + d*x1^2*y1^2) and 1081 y = (y1^2 - a*x1^2)/(1 - d*x1^2*y1^2). 1083 Note that one can use the formulae for point addition for point 1084 doubling, taking inverses, and adding the identity element as well 1085 (i.e., the point addition formulae are uniform and complete (subject 1086 to our Note above)). 1088 From the group laws above (subject to our Note above) it follows that 1089 if P=(x, y), P1=k*P=(x1, y1), and P2=(k+1)*P=(x2, y2) are affine 1090 points of the twisted Edwards curve E_{a,d} and if x is nonzero, then 1091 the x-coordinate of P1 can be expressed in terms of the y-coordinates 1092 of P, P1, and P2, and the x-coordinate of P, as 1094 x1=(y*y1-y2)/(x*(a-d*y*y1*y2)). 1096 This property allows recovery of the x-coordinate of a point P1=k*P 1097 that is computed via the so-called Montgomery ladder, where P is an 1098 affine point with nonzero x-coordinate (i.e., it does not have order 1099 one or two). Further details are out of scope. 1101 Appendix D. Relationship Between Curve Models 1103 The non-binary curves specified in Appendix A are expressed in 1104 different curve models, viz. as curves in short-Weierstrass form, as 1105 Montgomery curves, or as twisted Edwards curves. These curve models 1106 are related, as follows. 1108 D.1. Mapping between Twisted Edwards Curves and Montgomery Curves 1110 One can map points of the Montgomery curve M_{A,B} to points of the 1111 twisted Edwards curve E_{a,d}, where a:=(A+2)/B and d:=(A-2)/B and, 1112 conversely, map points of the twisted Edwards curve E_{a,d} to points 1113 of the Montgomery curve M_{A,B}, where A:=2(a+d)/(a-d) and where 1114 B:=4/(a-d). For twisted Edwards curves we consider (i.e., those 1115 where a is a square in GF(q), whereas d is not), this defines a one- 1116 to-one correspondence, which - in fact - is an isomorphism between 1117 M_{A,B} and E_{a,d}, thereby showing that, e.g., the discrete 1118 logarithm problem in either curve model is equally hard. 1120 For the Montgomery curves and twisted Edwards curves we consider, the 1121 mapping from M_{A,B} to E_{a,d} is defined by mapping the point at 1122 infinity O and the point (0, 0) of order two of M_{A,B} to, 1123 respectively, the point (0, 1) and the point (0, -1) of order two of 1124 E_{a,d}, while mapping each other point (u, v) of M_{A,B} to the 1125 point (x,y):=(u/v,(u-1)/(u+1)) of E_{a,d}. The inverse mapping from 1126 E_{a,d} to M_{A,B} is defined by mapping the point (0, 1) and the 1127 point (0, -1) of order two of E_{a,d} to, respectively, the point at 1128 infinity O and the point (0, 0) of order two of M_{A,B}, while each 1129 other point (x, y) of E_{a,d} is mapped to the point 1130 (u,v):=((1+y)/(1-y),(1+y)/((1-y)*x)) of M_{A,B}. 1132 Implementations may take advantage of this mapping to carry out 1133 elliptic curve group operations originally defined for a twisted 1134 Edwards curve on the corresponding Montgomery curve, or vice-versa, 1135 and translating the result back to the original curve, thereby 1136 potentially allowing code reuse. 1138 D.2. Mapping between Montgomery Curves and Weierstrass Curves 1140 One can map points of the Montgomery curve M_{A,B} to points of the 1141 Weierstrass curve W_{a,b}, where a:=(3-A^2)/(3*B^2) and 1142 b:=(2*A^3-9*A)/(27*B^3). This defines a one-to-one correspondence, 1143 which - in fact - is an isomorphism between M_{A,B} and W_{a,b}, 1144 thereby showing that, e.g., the discrete logarithm problem in either 1145 curve model is equally hard. 1147 The mapping from M_{A,B} to W_{a,b} is defined by mapping the point 1148 at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while 1149 mapping each other point (u,v) of M_{A,B} to the point 1150 (X,Y):=((u+A/3)/B,v/B) of W_{a,b}. Note that not all Weierstrass 1151 curves can be injectively mapped to Montgomery curves, since the 1152 latter have a point of order two and the former may not. In 1153 particular, if a Weierstrass curve has prime order, such as is the 1154 case with the so-called "NIST curves", this inverse mapping is not 1155 defined. 1157 If the Weierstrass curve W_{a,b} has a point (alpha,0) of order two 1158 and c:=a+3*(alpha)^2 is a square in GF(q), one can map points of this 1159 curve to points of the Montgomery curve M_{A,B}, where A:=3*alpha/ 1160 gamma and B:=1/gamma and where gamma is any square root of c. In 1161 this case, the mapping from W_{a,b} to M_{A,B} is defined by mapping 1162 the point at infinity O of W_{a,b} to the point at infinity O of 1163 M_{A,B}, while mapping each other point (X,Y) of W_{a,b} to the point 1164 (u,v):=((X-alpha)/gamma,Y/gamma) of M_{A,B}. As before, this defines 1165 a one-to-one correspondence, which - in fact - is an isomorphism 1166 between W_{a,b} and M_{A,B}. It is easy to see that the mapping from 1167 W_{a,b} to M_{A,B} and that from M_{A,B} to W_{a,b} (if defined) are 1168 each other's inverse. 1170 This mapping can be used to implement elliptic curve group operations 1171 originally defined for a twisted Edwards curve or for a Montgomery 1172 curve using group operations on the corresponding elliptic curve in 1173 short-Weierstrass form and translating the result back to the 1174 original curve, thereby potentially allowing code reuse. 1176 Note that implementations for elliptic curves with short-Weierstrass 1177 form that hard-code the domain parameter a to a= -3 (which value is 1178 known to allow more efficient implementations) cannot always be used 1179 this way, since the curve W_{a,b} resulting from an isomorphic 1180 mapping cannot always be expressed as a Weierstrass curve with a=-3 1181 via a coordinate transformation. For more details, see Appendix F. 1183 D.3. Mapping between Twisted Edwards Curves and Weierstrass Curves 1185 One can map points of the twisted Edwards curve E_{a,d} to points of 1186 the Weierstrass curve W_{a,b}, via function composition, where one 1187 uses the isomorphic mapping between twisted Edwards curves and 1188 Montgomery curves of Appendix D.1 and the one between Montgomery and 1189 Weierstrass curves of Appendix D.2. Obviously, one can use function 1190 composition (now using the respective inverses - if these exist) to 1191 realize the inverse of this mapping. 1193 Appendix E. Curve25519 and Cousins 1195 E.1. Curve Definition and Alternative Representations 1197 The elliptic curve Curve25519 is the Montgomery curve M_{A,B} defined 1198 over the prime field GF(p), with p:=2^{255}-19, where A:=486662 and 1199 B:=1. This curve has order h*n, where h=8 and where n is a prime 1200 number. For this curve, A^2-4 is not a square in GF(p), whereas A+2 1201 is. The quadratic twist of this curve has order h1*n1, where h1=4 1202 and where n1 is a prime number. For this curve, the base point is 1203 the point (Gu, Gv), where Gu=9 and where Gv is an odd integer in the 1204 interval [0, p-1]. 1206 This curve has the same group structure as (is "isomorphic" to) the 1207 twisted Edwards curve E_{a,d} defined over GF(p), with as base point 1208 the point (Gx, Gy), where parameters are as specified in 1209 Appendix E.3. This curve is denoted as Edwards25519. For this 1210 curve, the parameter a is a square in GF(p), whereas d is not, so the 1211 group laws of Appendix C.3 apply. 1213 The curve is also isomorphic to the elliptic curve W_{a,b} in short- 1214 Weierstrass form defined over GF(p), with as base point the point 1215 (GX, GY), where parameters are as specified in Appendix E.3. This 1216 curve is denoted as Wei25519. 1218 E.2. Switching between Alternative Representations 1220 Each affine point (u, v) of Curve25519 corresponds to the point (X, 1221 Y):=(u + A/3, v) of Wei25519, while the point at infinity of 1222 Curve25519 corresponds to the point at infinity of Wei25519. (Here, 1223 we used the mappings of Appendix D.2 and that B=1.) Under this 1224 mapping, the base point (Gu, Gv) of Curve25519 corresponds to the 1225 base point (GX, GY) of Wei25519. The inverse mapping maps the affine 1226 point (X, Y) of Wei25519 to (u, v):=(X - A/3, Y) of Curve25519, while 1227 mapping the point at infinity of Wei25519 to the point at infinity of 1228 Curve25519. Note that this mapping involves a simple shift of the 1229 first coordinate and can be implemented via integer-only arithmetic 1230 as a shift of (p+A)/3 for the isomorphic mapping and a shift of 1231 -(p+A)/3 for its inverse, where delta=(p+A)/3 is the element of GF(p) 1232 defined by 1234 delta 19298681539552699237261830834781317975544997444273427339909597 1235 334652188435537 1237 (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa 1238 aaaaaaaa aaad2451). 1240 (Note that, depending on the implementation details of the field 1241 arithmetic, one may have to shift the result by +p or -p if this 1242 integer is not in the interval [0,p-1].) 1244 The curve Edwards25519 is isomorphic to the curve Curve25519, where 1245 the base point (Gu, Gv) of Curve25519 corresponds to the base point 1246 (Gx,Gy) of Edwards25519 and where the point at infinity and the point 1247 (0,0) of order two of Curve25519 correspond to, respectively, the 1248 point (0, 1) and the point (0, -1) of order two of Edwards25519 and 1249 where each other point (u, v) of Curve25519 corresponds to the point 1250 (c*u/v, (u-1)/(u+1)) of Edwards25519, where c is the element of GF(p) 1251 defined by 1253 c sqrt(-(A+2)/B) 1254 51042569399160536130206135233146329284152202253034631822681833788 1255 666877215207 1257 (=0x70d9120b 9f5ff944 2d84f723 fc03b081 3a5e2c2e b482e57d 1258 3391fb55 00ba81e7). 1260 (Here, we used the mapping of Appendix D.1 and normalized this using 1261 the mapping of Appendix F.1 (where the element s of that appendix is 1262 set to c above).) The inverse mapping from Edwards25519 to 1263 Curve25519 is defined by mapping the point (0, 1) and the point (0, 1264 -1) of order two of Edwards25519 to, respectively, the point at 1265 infinity and the point (0,0) of order two of Curve25519 and having 1266 each other point (x, y) of Edwards25519 correspond to the point ((1 + 1267 y)/(1 - y), c*(1 + y)/((1-y)*x)) of Curve25519. 1269 The curve Edwards25519 is isomorphic to the Weierstrass curve 1270 Wei25519, where the base point (Gx, Gy) of Edwards25519 corresponds 1271 to the base point (GX,GY) of Wei25519 and where the identity element 1272 (0,1) and the point (0,-1) of order two of Edwards25519 correspond 1273 to, respectively, the point at infinity O and the point (A/3, 0) of 1274 order two of Wei25519 and where each other point (x, y) of 1275 Edwards25519 corresponds to the point (X, Y):=((1+y)/(1-y)+A/3, 1276 c*(1+y)/((1-y)*x)) of Wei25519, where c was defined before. (Here, 1277 we used the mapping of Appendix D.3.) The inverse mapping from 1278 Wei25519 to Edwards25519 is defined by mapping the point at infinity 1279 O and the point (A/3, 0) of order two of Wei25519 to, respectively, 1280 the identity element (0,1) and the point (0,-1) of order two of 1281 Edwards25519 and having each other point (X, Y) of Wei25519 1282 correspond to the point (c*(3*X-A)/(3*Y), (3*X-A-3)/(3*X-A+3)) of 1283 Edwards25519. 1285 Note that these mappings can be easily realized if points are 1286 represented in projective coordinates, using a few field 1287 multiplications only, thus allowing switching between alternative 1288 curve representations with negligible relative incremental cost. 1290 E.3. Domain Parameters 1292 The parameters of the Montgomery curve and the corresponding 1293 isomorphic curves in twisted Edwards curve and short-Weierstrass form 1294 are as indicated below. Here, the domain parameters of the 1295 Montgomery curve Curve25519 and of the twisted Edwards curve 1296 Edwards25519 are as specified in [RFC7748]; the domain parameters of 1297 Wei25519 are "new". 1299 General parameters (for all curve models): 1301 p 2^{255}-19 1302 (=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff 1303 ffffffff ffffffed) 1305 h 8 1307 n 72370055773322622139731865630429942408571163593799076060019509382 1308 85454250989 1310 (=2^{252} + 0x14def9de a2f79cd6 5812631a 5cf5d3ed) 1312 h1 4 1314 n1 14474011154664524427946373126085988481603263447650325797860494125 1315 407373907997 1317 (=2^{253} - 0x29bdf3bd 45ef39ac b024c634 b9eba7e3) 1319 Montgomery curve-specific parameters (for Curve25519): 1321 A 486662 (=0x076d06) 1323 B 1 (=0x01) 1325 Gu 9 (=0x09) 1327 Gv 14781619447589544791020593568409986887264606134616475288964881837 1328 755586237401 1330 (=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2 1331 29e9c5a2 7eced3d9) 1333 Twisted Edwards curve-specific parameters (for Edwards25519): 1335 a -1 (-0x01) 1337 d -121665/121666 = - (A-2)/(A+2) 1339 (=370957059346694393431380835087545651895421138798432190163887855 1340 33085940283555) 1342 (=0x52036cee 2b6ffe73 8cc74079 7779e898 00700a4d 4141d8ab 1343 75eb4dca 135978a3) 1345 Gx 15112221349535400772501151409588531511454012693041857206046113283 1346 949847762202 1348 (=0x216936d3 cd6e53fe c0a4e231 fdd6dc5c 692cc760 9525a7b2 1349 c9562d60 8f25d51a) 1351 Gy 4/5 1353 (=463168356949264781694283940034751631413079938662562256157830336 1354 03165251855960) 1356 (=0x66666666 66666666 66666666 66666666 66666666 66666666 1357 66666666 66666658) 1359 Weierstrass curve-specific parameters (for Wei25519): 1361 a 19298681539552699237261830834781317975544997444273427339909597334 1362 573241639236 1364 (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa 1365 aaaaaa98 4914a144) 1367 b 55751746669818908907645289078257140818241103727901012315294400837 1368 956729358436 1370 (=0x7b425ed0 97b425ed 097b425e d097b425 ed097b42 5ed097b4 1371 260b5e9c 7710c864) 1373 GX 19298681539552699237261830834781317975544997444273427339909597334 1374 652188435546 1376 (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa 1377 aaaaaaaa aaad245a) 1379 GY 14781619447589544791020593568409986887264606134616475288964881837 1380 755586237401 1382 (=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2 1383 29e9c5a2 7eced3d9) 1385 Appendix F. Further Mappings 1387 The non-binary curves specified in Appendix A are expressed in 1388 different curve models, viz. as curves in short-Weierstrass form, as 1389 Montgomery curves, or as twisted Edwards curves. In Appendix D we 1390 already described relationships between these various curve models. 1391 Further mappings exist between elliptic curves within the same curve 1392 model. These can be exploited to force some of the domain parameters 1393 to specific values that allow for a more efficient implementation of 1394 the addition formulae. 1396 F.1. Isomorphic Mapping between Twisted Edwards Curves 1398 One can map points of the twisted Edwards curve E_{a,d} to points of 1399 the twisted Edwards curve E_{a',d'}, where a:=a'*s^2 and d:=d'*s^2 1400 for some nonzero element s of GF(q). This defines a one-to-one 1401 correspondence, which - in fact - is an isomorphism between E_{a,d} 1402 and E_{a',d'}. 1404 The mapping from E_{a,d} to E_{a',d'} is defined by mapping the point 1405 (x,y) of E_{a,d} to the point (x', y'):=(s*x, y) of E_{a',d'}. The 1406 inverse mapping from E_{a',d'} to E_{a,d} is defined by mapping the 1407 point (x', y') of E_{a',d'} to the point (x, y):=(x'/s, y') of 1408 E_{a,d}. 1410 Implementations may take advantage of this mapping to carry out 1411 elliptic curve group operations originally defined for a twisted 1412 Edwards curve with generic domain parameters a and d on a 1413 corresponding isomorphic twisted Edwards curve with domain parameters 1414 a' and d' that have a more special form, which are known to allow for 1415 more efficient implementations of addition laws. In particular, it 1416 is known that such efficiency improvements exist if a':=-1 (see 1417 [tEd-Formulas]). 1419 F.2. Isomorphic Mapping between Montgomery Curves 1421 One can map points of the Montgomery curve M_{A,B} to points of the 1422 Montgomery curve M_{A',B'}, where A:=A' and B:=B'*s^2 for some 1423 nonzero element s of GF(q). This defines a one-to-one 1424 correspondence, which - in fact - is an isomorphism between M_{A,B} 1425 and M_{A',B'}. 1427 The mapping from M_{A,B} to M_{A',B'} is defined by mapping the point 1428 at infinity O of M_{A,B} to the point at infinity O of M_{A',B'}, 1429 while mapping each other point (u,v) of M_{A,B} to the point (u', 1430 v'):=(u, s*v) of M_{A',B'}. The inverse mapping from M_{A',B'} to 1431 M_{A,B} is defined by mapping the point at infinity O of M_{A',B'} to 1432 the point at infinity O of M_{A,B}, while mapping each other point 1433 (u',v') of M_{A',B'} to the point (u,v):=(u',v'/s) of M_{A,B}. 1435 One can also map points of the Montgomery curve M_{A,B} to points of 1436 the Montgomery curve M_{A',B'}, where A':=-A and B':=-B. This 1437 defines a one-to-one correspondence, which - in fact - is an 1438 isomorphism between M_{A,B} and M_{A',B'}. 1440 In this case, the mapping from M_{A,B} to M_{A',B'} is defined by 1441 mapping the point at infinity O of M_{A,B} to the point at infinity O 1442 of M_{A',B'}, while mapping each other point (u,v) of M_{A,B} to the 1443 point (u',v'):=(-u,v) of M_{A',B'}. The inverse mapping from 1444 M_{A',B'} to M_{A,B} is defined by mapping the point at infinity O of 1445 M_{A',B'} to the point at infinity O of M_{A,B}, while mapping each 1446 other point (u',v') of M_{A',B'} to the point (u,v):=(-u',v') of 1447 M_{A,B}. 1449 Implementations may take advantage of this mapping to carry out 1450 elliptic curve groups operations originally defined for a Montgomery 1451 curve with generic domain parameters A and B on a corresponding 1452 isomorphic Montgomery curve with domain parameters A' and B' that 1453 have a more special form, which is known to allow for more efficient 1454 implementations of addition laws. In particular, it is known that 1455 such efficiency improvements exist if B' assumes a small absolute 1456 value, such as B':=(+/-)1. (see [Mont-Ladder]). 1458 F.3. Isomorphic Mapping between Weierstrass Curves 1460 One can map points of the Weierstrass curve W_{a,b} to points of the 1461 Weierstrass curve W_{a',b'}, where a':=a*s^4 and b':=b*s^6 for some 1462 nonzero element s of GF(q). This defines a one-to-one 1463 correspondence, which - in fact - is an isomorphism between W_{a,b} 1464 and W_{a',b'}. 1466 The mapping from W_{a,b} to W_{a',b'} is defined by mapping the point 1467 at infinity O of W_{a,b} to the point at infinity O of W_{a',b'}, 1468 while mapping each other point (X,Y) of W_{a,b} to the point 1469 (X',Y'):=(X*s^2, Y*s^3) of W_{a',b'}. The inverse mapping from 1470 W_{a',b'} to W_{a,b} is defined by mapping the point at infinity O of 1471 W_{a',b'} to the point at infinity O of W_{a,b}, while mapping each 1472 other point (X', Y') of W_{a',b'} to the point (X,Y):=(X'/s^2,Y'/s^3) 1473 of W_{a,b}. 1475 Implementations may take advantage of this mapping to carry out 1476 elliptic curve group operations originally defined for a Weierstrass 1477 curve with generic domain parameters a and b on a corresponding 1478 isomorphic Weierstrass curve with domain parameter a' and b' that 1479 have a more special form, which is known to allow for more efficient 1480 implementations of addition laws, and translating the result back to 1481 the original curve. In particular, it is known that such efficiency 1482 improvements exist if a'=-3 (mod p), where p is the characteristic of 1483 GF(q), and one uses so-called Jacobian coordinates with a particular 1484 projective version of the addition laws of Appendix C.1. While not 1485 all Weierstrass curves can be put into this form, all traditional 1486 NIST curves have domain parameter a=-3, while all Brainpool curves 1487 [RFC5639] are isomorphic to a Weierstrass curve of this form. 1489 Note that implementations for elliptic curves with short-Weierstrass 1490 form that hard-code the domain parameter a to a= -3 cannot always be 1491 used this way, since the curve W_{a,b} cannot always be expressed in 1492 terms of a Weierstrass curve with a'=-3 via a coordinate 1493 transformation: this only holds if a'/a is a fourth power in GF(q) 1494 (see Section 3.1.5 of [GECC]). However, even in this case, one can 1495 still express the curve W_{a,b} as a Weierstrass curve with a small 1496 domain parameter value a', thereby still allowing a more efficient 1497 implementation than with a general domain parameter value a. 1499 F.4. Isogenous Mapping between Weierstrass Curves 1501 One can still map points of the Weierstrass curve W_{a,b} to points 1502 of the Weierstrass curve W_{a',b'}, where a':=-3 (mod p) and where p 1503 is the characteristic of GF(q), even if a'/a is not a fourth power in 1504 GF(q). In that case, this mappping cannot be an isomorphism (see 1505 Appendix F.3). Instead, the mapping is a so-called isogeny (or 1506 homomorphism). Since most elliptic curve operations process points 1507 of prime order or use so-called "co-factor multiplication", in 1508 practice the resulting mapping has similar properties as an 1509 isomorphism. In particular, one can still take advantage of this 1510 mapping to carry out elliptic curve group operations originally 1511 defined for a Weierstrass curve with domain parameter a unequal to -3 1512 (mod p) on a corresponding isogenous Weierstrass curve with domain 1513 parameter a'=-3 (mod p) and translating the result back to the 1514 original curve. 1516 In this case, the mapping from W_{a,b} to W_{a',b'} is defined by 1517 mapping the point at infinity O of W_{a,b} to the point at infinity O 1518 of W_{a',b'}, while mapping each other point (X,Y) of W_{a,b} to the 1519 point (X',Y'):=(u(X)/w(X)^2,Y*v(X)/w(X)^3) of W_{a',b'}. Here, u(X), 1520 v(X), and w(X) are polynomials in X that depend on the isogeny in 1521 question. The inverse mapping from W_{a',b'} to W_{a,b} is again an 1522 isogeny and defined by mapping the point at infinity O of W_{a',b'} 1523 to the point at infinity O of W_{a,b}, while mapping each other point 1524 (X', Y') of W_{a',b'} to the point 1525 (X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of W_{a,b}, where -- 1526 again -- u'(X'), v'(X'), and w'(X') are polynomials in X' that depend 1527 on the isogeny in question. These mappings have the property that 1528 their composition is not the identity mapping (as was the case with 1529 the isomorphic mappings discussed in Appendix F.3), but rather a 1530 fixed multiple hereof: if this multiple is l then the isogeny is 1531 called an isogeny of degree l (or l-isogeny) and u, v, and w (and, 1532 similarly, u', v', and w') are polynomials of degrees l, 3*(l-1)/2, 1533 and (l-1)/2, respectively. Note that an isomorphism is simply an 1534 isogeny of degree l=1. Details of how to determine isogenies are out 1535 of scope of this document. 1537 Implementations may take advantage of this mapping to carry out 1538 elliptic curve group operations originally defined for a Weierstrass 1539 curve with a generic domain parameter a on a corresponding isogenous 1540 Weierstrass curve with domain parameter a'=-3 (mod p), where one can 1541 use so-called Jacobian coordinates with a particular projective 1542 version of the addition laws of Appendix C.1. Since all traditional 1543 NIST curves have domain parameter a=-3, while all Brainpool curves 1544 [RFC5639] are isomorphic to a Weierstrass curve of this form, this 1545 allows taking advantage of existing implementations for these curves 1546 that may have a hardcoded a=-3 (mod p) domain parameter, provided one 1547 switches back and forth to this curve form using the isogenous 1548 mapping in question. 1550 Note that isogenous mappings can be easily realized using 1551 representations in projective coordinates and involves roughly 3*l 1552 finite field multiplications, thus allowing switching between 1553 alternative representations at relatively low incremental cost 1554 compared to that of elliptic curve scalar multiplications (provided 1555 the isogeny has low degree l). Note, however, that this does require 1556 storage of the polynomial coefficients of the isogeny and dual 1557 isogeny involved. This illustrates that low-degree isogenies are to 1558 be preferred, since an l-isogeny (usually) requires storing roughly 1559 6*l elements of GF(q). While there are many isogenies, we therefore 1560 only consider those with the desired property with lowest possible 1561 degree. 1563 Appendix G. Further Cousins of Curve25519 1565 G.1. Further Alternative Representations 1567 The Weierstrass curve Wei25519 is isomorphic to the Weierstrass curve 1568 Wei25519.2 defined over GF(p), with as base point the pair (G2X,G2Y), 1569 and isogenous to the Weierstrass curve Wei25519.-3 defined over 1570 GF(p), with as base point the pair (G3X, G3Y), where parameters are 1571 as specified in Appendix G.3 and where the related mappings are as 1572 specified in Appendix G.2. 1574 G.2. Further Switching 1576 Each affine point (X, Y) of Wei25519 corresponds to the point (X', 1577 Y'):=(X*s^2,Y*s^3) of Wei25519.2, where s is the element of GF(p) 1578 defined by 1580 s 20343593038935618591794247374137143598394058341193943326473831977 1581 39407761440 1583 (=0x047f6814 6d568b44 7e4552ea a5ed633d 02d62964 a2b0a120 1584 5e7941e9 375de020), 1586 while the point at infinity of Wei25519 corresponds to the point at 1587 infinity of Wei25519.2. (Here, we used the mapping of Appendix F.3.) 1588 Under this mapping, the base point (GX, GY) of Wei25519 corresponds 1589 to the base point (G2X,G2Y) of Wei25519.2. The inverse mapping maps 1590 the affine point (X', Y') of Wei25519.2 to (X,Y):=(X'/s^2,Y'/s^3) of 1591 Wei25519, while mapping the point at infinity O of Wei25519.2 to the 1592 point at infinity O of Wei25519. Note that this mapping (and its 1593 inverse) involves a modular multiplication of both coordinates with 1594 fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which 1595 can be precomputed. 1597 Each affine point (X,Y) of Wei25519 corresponds to the point 1598 (X',Y'):=(X1*t^2,Y1*t^3) of Wei25519.-3, where 1599 (X1,Y1)=(u(X)/w(X)^2,Y*v(X)/w(X)^3), where u, v, and w are the 1600 polynomials with coefficients in GF(p) as defined in Appendix H.1 and 1601 where t is the element of GF(p) defined by 1603 t 35728133398289175649586938605660542688691615699169662967154525084 1604 644181596229 1606 (=0x4efd6829 88ff8526 e189f712 5999550c e9ef729b ed1a7015 1607 73b1bab8 8bfcd845), 1609 while the point at infinity of Wei25519 corresponds to the point at 1610 infinity of Wei25519.-3. (Here, we used the isogenous mapping of 1611 Appendix F.4.) Under this isogenous mapping, the base point (GX,GY) 1612 of Wei25519 corresponds to the base point (G3X,G3Y) of Wei25519.-3. 1613 The dual isogeny maps the affine point (X',Y') of Wei25519.-3 to the 1614 affine point (X,Y):=(u'(X1)/w'(X1)^2,Y1*v'(X1)/w'(X1)^3) of Wei25519, 1615 where (X1,Y1)=(X'/t^2,Y'/t^3) and where u', v', and w' are the 1616 polynomials with coefficients in GF(p) as defined in Appendix H.2, 1617 while mapping the point at infinity O of Wei25519.-3 to the point at 1618 infinity O of Wei25519. Under this dual isogenous mapping, the base 1619 point (G3X, G3Y) of Wei25519.-3 corresponds to a multiple of the base 1620 point (GX, GY) of Wei25519, where this multiple is l=47 (the degree 1621 of the isogeny; see the description in Appendix F.4). Note that this 1622 isogenous map (and its dual) primarily involves the evaluation of 1623 three fixed polynomials involving the x-coordinate, which takes 1624 roughly 140 modular multiplications (or less than 5-10% relative 1625 incremental cost compared to the cost of an elliptic curve scalar 1626 multiplication). 1628 G.3. Further Domain Parameters 1630 The parameters of the Weierstrass curve with a=2 that is isomorphic 1631 with Wei25519 and the parameters of the Weierstrass curve with a=-3 1632 that is isogenous with Wei25519 are as indicated below. Both domain 1633 parameter sets can be exploited directly to derive more efficient 1634 point addition formulae, should an implementation facilitate this. 1636 General parameters: same as for Wei25519 (see Appendix E.3) 1638 Weierstrass curve-specific parameters (for Wei25519.2, i.e., with 1639 a=2): 1641 a 2 (=0x02) 1643 b 12102640281269758552371076649779977768474709596484288167752775713 1644 178787220689 1646 (=0x1ac1da05 b55bc146 33bd39e4 7f94302e f19843dc f669916f 1647 6a5dfd01 65538cd1) 1649 G2X 10770553138368400518417020196796161136792368198326337823149502681 1650 097436401658 1652 (=0x17cfeac3 78aed661 318e8634 582275b6 d9ad4def 072ea193 1653 5ee3c4e8 7a940ffa) 1655 G2Y 54430575861508405653098668984457528616807103332502577521161439773 1656 88639873869 1658 (=0x0c08a952 c55dfad6 2c4f13f1 a8f68dca dc5c331d 297a37b6 1659 f0d7fdcc 51e16b4d) 1661 Weierstrass curve-specific parameters (for Wei25519.-3, i.e., with 1662 a=-3): 1664 a -3 1666 (=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff 1667 ffffffff ffffffea) 1669 b 29689592517550930188872794512874050362622433571298029721775200646 1670 451501277098 1672 (=0x41a3b6bf c668778e be2954a4 b1df36d1 485ecef1 ea614295 1673 796e1022 40891faa) 1675 G3X 53837179229940872434942723257480777370451127212339198133697207846 1676 219400243292 1678 (=0x7706c37b 5a84128a 3884a5d7 1811f1b5 5da3230f fb17a8ab 1679 0b32e48d 31a6685c) 1681 G3Y 69548073091100184414402055529279970392514867422855141773070804184 1682 60388229929 1683 (=0x0f60480c 7a5c0e11 40340adc 79d6a2bf 0cb57ad0 49d025dc 1684 38d80c77 985f0329) 1686 Appendix H. Isogeny Details 1688 The isogeny and dual isogeny are both isogenies with degree l=47. 1689 Both are specified by a triple of polynomials u, v, and w (resp. u', 1690 v', and w') of degree 47, 69, and 23, respectively, with coefficients 1691 in GF(p). The coeffients of each of these polynomials are specified 1692 in Appendix H.1 (for the isogeny) and in Appendix H.2 (for the dual 1693 isogeny). For each polynomial in variable x, the coefficients are 1694 tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in 1695 hexadecimal format. 1697 H.1. Isogeny Parameters 1699 H.1.1. Coefficients of u(x) 1701 0 0x670ed14828b6f1791ceb3a9cc0edfe127dee8729c5a72ddf77bb1abaebbba1e8 1703 1 0x1135ca8bd5383cb3545402c8bce2ced14b45c29b241e4751b035f27524a9f932 1705 2 0x3223806ff5f669c430efd74df8389f058d180e2fcffa5cdef3eacecdd2c34771 1707 3 0x31b8fecf3f17a819c228517f6cd9814466c8c8bea2efccc47a29bfc14c364266 1709 4 0x2541305c958c5a326f44efad2bec284e7abee840fadb08f2d994cd382fd8ce42 1711 5 0x6e6f9c5792f3ff497f860f44a9c469cec42bd711526b733e10915be5b2dbd8c6 1713 6 0x3e9ad2e5f594b9ce6b06d4565891d28a1be8790000b396ef0bf59215d6cabfde 1715 7 0x278448895d236403bbc161347d19c913e7df5f372732a823ed807ee1d30206be 1717 8 0x42f9d171ea8dc2f4a14ea46cc0ee54967175ecfe83a975137b753cb127c35060 1719 9 0x128e40efa2d3ccb51567e73bae91e7c31eac45700fa13ce5781cbe5ddc985648 1721 10 0x450e5086c065430b496d88952dd2d5f2c5102bc27074d4d1e98bfa47413e0645 1723 11 0x487ef93da70dfd44a4db8cb41542e33d1aa32237bdca3a59b3ce1c59585f253d 1725 12 0x33d209270026b1d2db96efb36cc2fa0a49be1307f49689022eab1892b010b785 1727 13 0x4732b5996a20ebc4d5c5e2375d3b6c4b700c681bd9904343a14a0555ef0ecd48 1729 14 0x64dc9e8272b9f5c6ad3470db543238386f42b18cb1c592cc6caf7893141b2107 1730 15 0x52bbacd1f85c61ef7eafd8da27260fa2821f7a961867ed449b283036508ac5c5 1732 16 0x320447ed91210985e2c401cfe1a93db1379424cf748f92fd61ab5cc356bc89a2 1734 17 0x23d23a49bbcdf8cf4c4ce8a4ff7dd87d1ad1970317686254d5b4d2ec050d019f 1736 18 0x1601fca063f0bbbf15f198b3c20e474c2170294fa981f73365732d2372b40cd4 1738 19 0x7bf3f93840035e9688cfff402cee204a17c0de9779fc33503537dd78021bf4c4 1740 20 0x311998ce59fb7e1cd6af591ece3e84dfcb1c330cbcf28c0349e37b9581452853 1742 21 0x7ae5e41acfd28a9add2216dfed34756575a19b16984c1f3847b694326dad7f99 1744 22 0x704957e279244a5b107a6c57bd0ab9afe5227b7c0be2052cd3513772a40efee7 1746 23 0x56b918b5a0c583cb763550f8f71481e57c13bdcef2e5cfc8091d0821266f233b 1748 24 0x677073fed43ab291e496f798fbcf217bac3f014e35d0c2fa07f041ae746a04d7 1750 25 0x22225388e76f9688c7d4053b50ba41d0d8b71a2f21da8353d98472243ef50170 1752 26 0x66930b3dffdd3995a2502cef790d78b091c875192d8074bb5d5639f736400555 1754 27 0x79eb677c5e36971e8d64d56ebc0dedb4e9b7dd2d7b01343ebbd4d358d376e490 1756 28 0x48a204c2ca6d8636e9994842605bd648b91b637844e38d6c7dd707edce8256e2 1758 29 0x0fb3529b0d4b9ce2d70760f33e8ce997a58999718e9277caf48623d27ae6a788 1760 30 0x4352604bffd0c7d7a9ed898a2c6e7cf2512ffb89407271ba1f2c2d0ead8cc5aa 1762 31 0x6667697b29785fb6f0bd5e04d828991a5fe525370216f347ec767a26e7aac936 1764 32 0x09fc950b083c56dbd989badf9887255e203c879f123a7cb28901e50aea6d64dc 1766 33 0x41e51b51b5caadd1c15436bbf37596a1d7288a5f495d6b5b1ae66f8b2942b31d 1768 34 0x073b59fec709aa1cabd429e981c6284822a8b7b07620c831ab41fd31d5cf7430 1770 35 0x67e9b88e9a1bfbc2554107d67d814986f1b09c3107a060cba21c019a2d5dc848 1772 36 0x6881494a1066ca176c5e174713786040affb4268b19d2abf28ef4293429f89c1 1774 37 0x5f4d30502ff1e1ccd624e6f506569454ab771869d7483e26afc09dea0c5ccd3d 1776 38 0x02a814cfc5859bca51e539c159955cbe729a58978b52329575d09bc6c3bf97ad 1777 39 0x1313c8aaae20d6f4397f0d8b19e52cfcdf8d8e10fba144aec1778fd10ddf4e9c 1779 40 0x7008d38f434b98953a996d4cc79fcbef9502411dcdf92005f725cea7ce82ad47 1781 41 0x5a74d1296aaaa245ffb848f434531fa3ba9e5cb9098a7091d36c2777d4cf5a13 1783 42 0x4bd3b700606397083f8038177bdaa1ac6edbba0447537582723cae0fd29341a9 1785 43 0x573453fb2b093016f3368356c786519d54ed05f5372c01723b4da520597ec217 1787 44 0x77f5c605bdb3a30d7d9c8840fce38650910d4418eed707a212c8927f41c2c812 1789 45 0x16d6b9f7ff57ca32350057de1204cc6d69d4ef1b255dfef8080118e2fef6ace3 1791 46 0x34e8595832a4021f8b5744014c6b4f7da7df0d0329e8b6b4d44c8fadad6513b7 1793 47 0x01 1795 H.1.2. Coefficients of v(x) 1797 0 0x0f9f5eb7134e6f8dafa30c45afa58d7bfc6d4e3ccbb5de87b562fd77403972b2 1799 1 0x36c2dcd9e88f0d2d517a15fc453a098bbbb5a05eb6e8da906fae418a4e1a13f7 1801 2 0x0b40078302c24fa394a834880d5bf46732ca1b4894172fb7f775821276f558b3 1803 3 0x53dd8e2234573f7f3f7df11e90a7bdd7b75d807f9712f521d4fb18af59aa5f26 1805 4 0x6d4d7bb08de9061988a8cf6ff3beb10e933d4d2fbb8872d256a38c74c8c2ceda 1807 5 0x71bfe5831b30e28cd0fbe1e9916ab2291c6beacc5af08e2c9165c632e61dd2f5 1809 6 0x7c524f4d17ff2ee88463da012fc12a5b67d7fb5bd0ab59f4bbf162d76be1c89c 1811 7 0x758183d5e07878d3364e3fd4c863a5dc1fe723f48c4ab4273fc034f5454d59a4 1813 8 0x1eb41ef2479444ecdccbc200f64bde53f434a02b6c3f485d32f14da6aa7700e1 1815 9 0x1490f3851f016cc3cf8a1e3c16a53317253d232ed425297531b560d70770315c 1817 10 0x09bc43131964e46d905c3489c9d465c3abbd26eab9371c10e429b36d4b86469c 1819 11 0x5f27c173d94c7a413a288348d3fc88daa0bcf5af8f436a47262050f240e9be3b 1821 12 0x1d20010ec741aaa393cd19f0133b35f067adab0d105babe75fe45c8ba2732ceb 1823 13 0x01b3c669ae49b86be2f0c946a9ff6c48e44740d7d9804146915747c3c025996a 1824 14 0x24c6090f79ec13e3ae454d8f0f98e0c30a8938180595f79602f2ba013b3c10db 1826 15 0x4650c5b5648c6c43ac75a2042048c699e44437929268661726e7182a31b1532f 1828 16 0x0957a835fb8bac3360b5008790e4c1f3389589ba74c8e8bf648b856ba7f22ba5 1830 17 0x1cd1300bc534880f95c7885d8df04a82bd54ed3e904b0749e0e3f8cb3240c7c7 1832 18 0x760b486e0d3c6ee0833b34b64b7ebc846055d4d1e0beeb6aedd5132399ada0ea 1834 19 0x1c666846c63965ef7edf519d6ada738f2b676ae38ff1f4621533373931b3220e 1836 20 0x365055118b38d4bc0df86648044affea2ef33e9a392ad336444e7d15e45585d1 1838 21 0x736487bde4b555abfccd3ea7ddcda98eda0d7c879664117dee906a88bc551194 1840 22 0x70de05ab9520222a37c7a84c61eedff71cb50c5f6647fc2a5d6e0ff2305cea37 1842 23 0x59053f6cdf6517ab3fe4bd9c9271d1892f8cf353d8041b98409e1e341a01f8b5 1844 24 0x375db54ed12fe8df9a198ea40200e812c2660b7022681d7932d89fafe7c6e88d 1846 25 0x2a070c31d1c1a064daf56c79a044bd1cd6d13f1ddb0ff039b03a6469aaa9ed77 1848 26 0x41482351e7f69a756a5a2c0b3fa0681c03c550341d0ca0f76c5b394db9d2de8d 1850 27 0x747ac1109c9e9368d94a302cb5a1d23fcc7f0fd8a574efb7ddcaa738297c407a 1852 28 0x45682f1f2aab6358247e364834e2181ad0448bb815c587675fb2fee5a2119064 1854 29 0x148c5bf44870dfd307317f0a0e4a8c163940bee1d2f01455a2e658aa92c13620 1856 30 0x6add1361e56ffa2d2fbbddba284b35be5845aec8069fc28af009d53290a705ce 1858 31 0x6631614c617400dc00f2c55357f67a94268e7b5369b02e55d5db46c935be3af5 1860 32 0x17cffb496c64bb89d91c8c082f4c288c3c87feabd6b08591fe5a92216c094637 1862 33 0x648ff88155969f54c955a1834ad227b93062bb191170dd8c4d759f79ad5da250 1864 34 0x73e50900b89e5f295052b97f9d0c9edb0fc7d97b7fa5e3cfeefe33dd6a9cb223 1866 35 0x6afcb2f2ffe6c08508477aa4956cbd3dc864257f5059685adf2c68d4f2338f00 1868 36 0x372fd49701954c1b8f00926a8cb4b157d4165b75d53fa0476716554bf101b74c 1870 37 0x0334ed41325f3724ff8becbf2b3443fea6d30fa543d1ca13188aceb2bdaf5f4e 1871 38 0x70e629c95a94e8e1b3974acb25e18ba42f8d5991786f0931f650c283adfe82fd 1873 39 0x738a625f4c62d3d645f1274e09ab344e72d441f3c0e82989d3e21e19212f23f3 1875 40 0x7093737294b29f21522f5664a9941c9b476f75d443b647bd2c777040bcd12a6a 1877 41 0x0a996bad5863d821ccb8b89fa329ddbe5317a46bcb32552db396bea933765436 1879 42 0x2da237e3741b75dd0264836e7ef634fc0bc36ab187ebc790591a77c257b06f53 1881 43 0x1902f3daa86fa4f430b57212924fdc9e40f09e809f3991a0b3a10ab186c50ee5 1883 44 0x12baffec1bf20c921afd3cdf67a7f1d87c00d5326a3e5c83841593c214dadcb1 1885 45 0x6460f5a68123cb9e7bc1289cd5023c0c9ccd2d98eea24484fb3825b59dcd09aa 1887 46 0x2c7d63a868ffc9f0fd034f821d84736c5bc33325ce98aba5f0d95fef6f230ec8 1889 47 0x756e0063349a702db7406984c285a9b6bfba48177950d4361d8efa77408dc860 1891 48 0x037f3e30032b21e0279738e0a2b689625447831a2ccf15c638672da9aa7255ae 1893 49 0x1107c0dbe15d6ca9e790768317a40bcf23c80f1841f03ca79dd3e3ef4ea1ae30 1895 50 0x61ff7f25721d6206041c59a788316b09e05135a2aad94d539c65daa68b302cc2 1897 51 0x5dbfe346cbd0d61b9a3b5c42ec0518d3ae81cabcc32245060d7b0cd982b8d071 1899 52 0x4b6595e8501e9ec3e75f46107d2fd76511764efca179f69196eb45c0aa6fade3 1901 53 0x72d17a5aa7bd8a2540aa9b02d9605f2a714f44abfb4c35d518b7abc39b477870 1903 54 0x658d8c134bac37729ec40d27d50b637201abbf1ab4157316358953548c49cf22 1905 55 0x36ac53b9118581ace574d5a08f9647e6a916f92dda684a4dbc405e2646b0243f 1907 56 0x1917a98f387d1e323e84a0f02d53307b1dd949e1a27b0de14514f89d9c0ef4b6 1909 57 0x21573434fde7ce56e8777c79539479441942dba535ade8ecb77763f7eb05d797 1911 58 0x0e0bf482dc40884719bea5503422b603f3a8edb582f52838caa6eaab6eeac7ef 1913 59 0x3b0471eb53bd83e14fbc13928fe1691820349a963be8f7e9815848a53d03f5eb 1915 60 0x1e92cb067b24a729c42d3abb7a1179c577970f0ab3e6b0ce8d66c5b8f7001262 1917 61 0x74ea885c1ebed6f74964262402432ef184c42884fceb2f8dba3a9d67a1344dd7 1918 62 0x433ebce2ce9b0dc314425cfc2b234614d3c34f2c9da9fff4fdddd1ce242d035b 1920 63 0x33ac69e6be858dde7b83a9ff6f11de443128b39cec6e410e8d3b570e405ff896 1922 64 0x0dab71e2ae94e6530a501ed8cf3df26731dd1d41cd81578341e12dca3cb71aa3 1924 65 0x537f58d52d18ce5b1d5a6bd3a420e796e64173491ad43dd4d1083a7dcc7dd201 1926 66 0x49c2f6afa93fdcc4e0f8128a8b06da4c75049be14edf3e103821ab604c60f8ae 1928 67 0x10a333eabd6135aeaa3f5f5f7e73d102e4fd7e4bf0902fc55b00da235fa1ad08 1930 68 0x0f5c86044bf6032f5102e601f2a0f73c7bce9384bedd120f3e72d78484179d9c 1932 69 0x01 1934 H.1.3. Coefficients of w(x) 1936 0 0x3da24d42421264f30939ff00203880f2b017eb3fecf8933ae61e18df8c8ba116 1938 1 0x0457f20bc393cdc9a66848ce174e2fa41d77e6dbae05a317a1fb6e3ae78760f8 1940 2 0x7f608a2285c480d5c9592c435431fae94695beef79d770bb6d029c1d10a53295 1942 3 0x3832accc520a485100a0a1695792465142a5572bed1b2e50e1f8f662ac7289bb 1944 4 0x2df1b0559e31b328eb34beedd5e537c3f4d7b9befb0749f75d6d0d866d26fbaa 1946 5 0x25396820381d04015a9f655ddd41c74303ded05d54a7750e2f58006659adda28 1948 6 0x6fa070a70ca2bc6d4d0795fb28d4990b2cc80cd72d48b603a8ac8c8268bef6a6 1950 7 0x27f488578357388b20fbc7503328e1d10de602b082b3c7b8ceb33c29fea7a0d2 1952 8 0x15776851a7cabcfe84c632118306915c0c15c75068a47021968c7438d46076e6 1954 9 0x101565b08a9af015c172fb194b940a4df25c4fb1d85f72d153efc79131d45e8f 1956 10 0x196b0ffbf92f3229fea1dac0d74591b905ccaab6b83f905ee813ee8449f8a62c 1958 11 0x01f55784691719f765f04ee9051ec95d5deb42ae45405a9d87833855a6d95a94 1960 12 0x628858f79cca86305739d084d365d5a9e56e51a4485d253ae3f2e4a379fa8aff 1962 13 0x4a842dcd943a80d1e6e1dab3622a8c4d390da1592d1e56d1c14c4d3f72dd01a5 1964 14 0x0f3bfc9cb17a1125f94766a4097d0f1018963bc11cb7bc0c7a1d94d65e282477 1965 15 0x1c4bd70488c4882846500691fa7543b7ef694446d9c3e3b4707ea2c99383e53c 1967 16 0x2d7017e47b24b89b0528932c4ade43f09091b91db0072e6ebdc5e777cb215e35 1969 17 0x781d69243b6c86f59416f91f7decaca93eab9cdc36a184191810c56ed85e0fdc 1971 18 0x5f20526f4177357da40a18da054731d442ad2a5a4727322ba8ed10d32eca24fb 1973 19 0x33e4cab64ed8a00d8012104fe8f928e6173c428eff95bbbe569ea46126a4f3cd 1975 20 0x050555b6f07e308d33776922b6566829d122e19b25b7bbacbb0a4b1a7dc40192 1977 21 0x533fa4bf1e2a2aae2f979065fdbb5b667ede2f85543fddbba146aa3a4ef2d281 1979 22 0x5a742cac1952010fc5aba200a635a7bed3ef868194f45b5a6a2647d6d6b289d2 1981 23 0x01 1983 H.2. Dual Isogeny Parameters 1985 H.2.1. Coefficients of u'(x) 1987 0 0x0f0eddb584a20aaac8f1419efdd02a5cca77b21e4cfae78c49b5127d98bc5882 1989 1 0x7115e60d44a58630417df33dd45b8a546fa00b79fea3b2bdc449694bade87c0a 1991 2 0x0b3f3a6f3c445c7dc1f91121275414e88c32ff3f367ba0edad4d75b7e7b94b65 1993 3 0x1eb31bb333d7048b87f2b3d4ec76d69035927b41c30274368649c87c52e1ab30 1995 4 0x552c886c2044153e280832264066cce2a7da1127dc9720e2a380e9d37049ac64 1997 5 0x4504f27908db2e1f5840b74ae42445298755d9493141f5417c02f04d47797dda 1999 6 0x082c242cce1eb19698a4fa30b5affe64e5051c04ae8b52cb68d89ee85222e628 2001 7 0x480473406add76cf1d77661b3ff506c038d9cdd5ad6e1ea41969430bb876d223 2003 8 0x25f47bb506fba80c79d1763365fa9076d4c4cb6644f73ed37918074397e88588 2005 9 0x10f13ed36eab593fa20817f6bb70cac292e18d300498f6642e35cbdf772f0855 2007 10 0x7d28329d695fb3305620f83a58df1531e89a43c7b3151d16f3b60a8246c36ade 2009 11 0x02c5ec8c42b16dc6409bdd2c7b4ffe9d65d7209e886badbd5f865dec35e4ab4a 2011 12 0x7f4f33cd50255537e6cde15a4a327a5790c37e081802654b56c956434354e133 2012 13 0x7d30431a121d9240c761998cf83d228237e80c3ef5c7191ec9617208e0ab8cec 2014 14 0x4d2a7d6609610c1deed56425a4615b92f70a507e1079b2681d96a2b874cf0630 2016 15 0x74676df60a9906901d1dc316c639ff6ae0fcdb02b5571d4b83fc2eedcd2936a8 2018 16 0x22f8212219aca01410f06eb234ed53bd5b8fbe7c08652b8002bcd1ea3cdae387 2020 17 0x7edb04449565d7c566b934a87fadade5515f23bda1ce25daa19fff0c6a5ccc2f 2022 18 0x106ef71aa3aa34e8ecf4c07a67d03f0949d7d015ef2c1e32eb698dd3bec5a18c 2024 19 0x0017913eb705db126ac3172447bcd811a62744d505ad0eea94cfcfdde5ca7428 2026 20 0x2cc793e6d3b592dcf5472057a991ff1a5ab43b4680bb34c0f5faffc5307827c1 2028 21 0x6dafcc0b16f98300cddb5e0a7d7ff04a0e73ca558c54461781d5a5ccb1ea0122 2030 22 0x7e418891cf222c021b0ae5f5232b9c0dc8270d4925a13174a0f0ac5e7a4c8045 2032 23 0x76553bd26fecb019ead31142684789fea7754c2dc9ab9197c623f45d60749058 2034 24 0x693efb3f81086043656d81840902b6f3a9a4b0e8f2a5a5edf5ce1c7f50a3898e 2036 25 0x46c630eac2b86d36f18a061882b756917718a359f44752a5caf41be506788921 2038 26 0x01dcfa01773628753bc6f448ac11be8a3bffa0011b9284967629b827e064f614 2040 27 0x08430b5b97d49b0938d1f66ecb9d2043025c6eec624f8f02042b9621b2b5cb19 2042 28 0x66f66a6669272d47d3ec1efea36ee01d4a54ed50e9ec84475f668a5a9850f9be 2044 29 0x539128823b5ef3e87e901ab22f06d518a9bad15f5d375b49fe1e893ab38b1345 2046 30 0x2bd01c49d6fff22c213a8688924c10bf29269388a69a08d7f326695b3c213931 2048 31 0x3f7bea1baeccea3980201dc40d67c26db0e3b15b5a19b6cdac6de477aa717ac1 2050 32 0x6e0a72d94867807f7150fcb1233062f911b46e2ad11a3eac3c6c4c91e0f4a3fa 2052 33 0x5963f3cc262253f56fc103e50217e7e5b823ae8e1617f9e11f4c9c595fbb5bf6 2054 34 0x41440b6fe787777bc7b63afac9f4a38ddadcebc3d72f8fc73835247ba05f3a1d 2056 35 0x66d185401c1d2d0b84fcf6758a6a985bf9695651271c08f4b69ce89175fb7b34 2058 36 0x2673fb8c65bc4fe41905381093429a2601c46a309c03077ca229bac7d6ccf239 2059 37 0x1ce4d895ee601918a080de353633c82b75a3f61e8247763767d146554dd2f862 2061 38 0x18efa6c72fa908347547a89028a44f79f22542baa588601f2b3ed25a5e56d27c 2063 39 0x53de362e2f8ff220f8921620a71e8faa1aa57f8886fcbb6808fa3a5560570543 2065 40 0x0dc29a73b97f08aa8774911474e651130ed364e8d8cffd4a80dee633aacecc47 2067 41 0x4e7eb8584ae4de525389d1e9300fc4480b3d9c8a5a45ecfbe33311029d8f6b99 2069 42 0x6c3cba4aa9229550fa82e1cfaee4b02f2c0cb86f79e0d412b8e32b00b7959d80 2071 43 0x5a9d104ae585b94af68eeb16b1349776b601f97b7ce716701645b1a75b68dcf3 2073 44 0x754e014b5e87af035b3d5fe6fb49f4631e32549f6341c6693c5172a6388e273e 2075 45 0x6710d8265118e22eaceba09566c86f642ab42da58c435083a353eaa12d866c39 2077 46 0x6e88ac659ce146c369f8b24c3a49f8dca547827250cf7963a455851cfc4f8d22 2079 47 0x0971eb5f253356cd1fde9fb21f4a4902aa5b8d804a2b57ba775dc130181ae2e8 2081 H.2.2. Coefficients of v'(x) 2083 0 0x043c9b67cc5b16e167b55f190db61e44d48d813a7112910f10e3fd8da85d61d3 2085 1 0x72046db07e0e7882ff3f0f38b54b45ca84153be47a7fd1dd8f6402e17c47966f 2087 2 0x1593d97b65a070b6b3f879fe3dc4d1ef03c0e781c997111d5c1748f956f1ffc0 2089 3 0x54e5fec076b8779338432bdc5a449e36823a0a7c905fd37f232330b026a143a0 2091 4 0x46328dd9bc336e0873abd453db472468393333fbf2010c6ac283933216e98038 2093 5 0x25d0c64de1dfe1c6d5f5f2d98ab637d8b39bcf0d886a23dabac18c80d7eb03ce 2095 6 0x3a175c46b2cd8e2b313dde2d5f3097b78114a6295f283cf58a33844b0c8d8b34 2097 7 0x5cf4e6f745bdd61181a7d1b4db31dc4c30c84957f63cdf163bee5e466a7a8d38 2099 8 0x639071c39b723eea51cfd870478331d60396b31f39a593ebdd9b1eb543875283 2101 9 0x7ea8f895dcd85fc6cb2b58793789bd9246e62fa7a8c7116936876f4d8dff869b 2103 10 0x503818acb535bcaacf8ad44a83c213a9ce83af7c937dc9b3e5b6efedc0a7428c 2105 11 0x0e815373920ec3cbf3f8cae20d4389d367dc4398e01691244af90edc3e6d42b8 2106 12 0x7e4b23e1e0b739087f77910cc635a92a3dc184a791400cbceae056c19c853815 2108 13 0x145322201db4b5ec0a643229e07c0ab7c36e4274745689be2c19cfa8a702129d 2110 14 0x0fde79514935d9b40f52e33429621a200acc092f6e5dec14b49e73f2f59c780d 2112 15 0x37517ac5c04dc48145a9d6e14803b8ce9cb6a5d01c6f0ad1b04ff3353d02d815 2114 16 0x58ae96b8eefe9e80f24d3b886932fe3c27aaea810fa189c702f93987c8c97854 2116 17 0x6f6402c90fa379096d5f436035bebc9d29302126e9b117887abfa7d4b3c5709a 2118 18 0x01dbdf2b9ec09a8defeb485cc16ea98d0d45c5b9877ff16bd04c0110d2f64961 2120 19 0x53c51706af523ab5b32291de6c6b1ee7c5cbd0a5b317218f917b12ff38421452 2122 20 0x1b1051c7aec7d37a349208e3950b679d14e39f979db4fcd7b50d7d27dc918650 2124 21 0x1547e8d36262d5434cfb029cdd29385353124c3c35b1423c6cca1f87910b305b 2126 22 0x198efe984efc817835e28f704d41e4583a1e2398f7ce14045c4575d0445c6ce7 2128 23 0x492276dfe9588ee5cd9f553d990f377935d721822ecd0333ce2eb1d4324d539c 2130 24 0x77bad5319bacd5ed99e1905ce2ae89294efa7ee1f74314e4095c618a4e580c9b 2132 25 0x2cb3d532b8eac41c61b683f7b02feb9c2761f8b4286a54c3c4b60dd8081a312e 2134 26 0x37d189ea60443e2fee9b7ba8a34ed79ff3883dcefc06592836d2a9dd2ee3656e 2136 27 0x79a80f9a0e6b8ded17a3d6ccf71eb565e3704c3543b77d70bca854345e880aba 2138 28 0x47718530ef8e8c75f069acb2d9925c5537908e220b28c8a2859b856f46d5f8db 2140 29 0x7dc518f82b55a36b4fa084b05bf21e3efce481d278a9f5c6a49701e56dac01ec 2142 30 0x340a318dad4b8d348a0838659672792a0f00b7105881e6080a340f708a9c7f94 2144 31 0x55f04d9d8891636d4e9c808a1fa95ad0dae7a8492257b20448023aad3203278e 2146 32 0x39dc465d58259f9f70bb430d27e2f0ab384a550e1259655443e14bdecba85530 2148 33 0x757385464cff265379a1adfadfd6f6a03fa8a2278761d4889ab097eff4d1ac28 2150 34 0x4d575654dbe39778857f4e688cc657416ce524d54864ebe8995ba766efa7ca2b 2152 35 0x47adb6aecc1949f2dc9f01206cc23eb4a0c29585d475dd24dc463c5087809298 2153 36 0x30d39e8b0c451a8fcf3d2abab4b86ffa374265abbe77c5903db4c1be8cec7672 2155 37 0x28cf47b39112297f0daeaa621f8e777875adc26f35dec0ba475c2ee148562b41 2157 38 0x36199723cc59867e2e309fe9941cd33722c807bb2d0a06eeb41de93f1b93f2f5 2159 39 0x5cdeb1f2ee1c7d694bdd884cb1c5c22de206684e1cafb8d3adb9a33cb85e19a2 2161 40 0x0f6e6b3fc54c2d25871011b1499bb0ef015c6d0da802ae7eccf1d8c3fb73856c 2163 41 0x0c1422c98b672414344a9c05492b926f473f05033b9f85b8788b4bb9a080053c 2165 42 0x19a8527de35d4faacb00184e0423962247319703a815eecf355f143c2c18f17f 2167 43 0x7812dc3313e6cf093da4617f06062e8e8969d648dfe6b5c331bccd58eb428383 2169 44 0x61e537180c84c79e1fd2d4f9d386e1c4f0442247605b8d8904d122ee7ef9f7be 2171 45 0x544d8621d05540576cfc9b58a3dab19145332b88eb0b86f4c15567c37205adf9 2173 46 0x11be3ef96e6e07556356b51e2479436d9966b7b083892b390caec22a117aa48e 2175 47 0x205cda31289cf75ab0759c14c43cb30f7287969ea3dc0d5286a3853a4d403187 2177 48 0x048d8fc6934f4f0a99f0f2cc59010389e2a0b20d6909bfcf8d7d0249f360acdc 2179 49 0x42cecc6d9bdca6d382e97fcea46a79c3eda2853091a8f399a2252115bf9a1454 2181 50 0x0117d41b24f2f69cb3270b359c181607931f62c56d070bbd14dc9e3f9ab1432e 2183 51 0x7c51564c66f68e2ad4ce6ea0d68f920fafa375376709c606c88a0ed44207aa1e 2185 52 0x48f25191fc8ac7d9f21adf6df23b76ccbca9cb02b815acdbebfa3f4eddc71b34 2187 53 0x4fc21a62c4688de70e28ad3d5956633fc9833bc7be09dc7bc500b7fae1e1c9a8 2189 54 0x1f23f25be0912173c3ef98e1c9990205a69d0bf2303d201d27a5499247f06789 2191 55 0x3131495618a0ac4cb11a702f3f8bab66c4fa1066d0a741af3c92d5c246edd579 2193 56 0x0d93fe40faa53913638e497328a1b47603cb062c7afc9e96278603f29fd11fd4 2195 57 0x6b348bc59e984c91d696d1e3c3cfae44021f06f74798c787c355437fb696093d 2197 58 0x65af00e73043edcb479620c8b48098b89809d577a4071c8e33e8678829138b8a 2199 59 0x5e62ffb032b2ddb06591f86a46a18effd5d6ecf3f129bb2bacfd51a3739a98b6 2200 60 0x62c974ef3593fc86f7d78883b8727a2f7359a282cbc0196948e7a793e60ce1a1 2202 61 0x204d708e3f500aad64283f753e7d9bab976aa42a4ca1ce5e9d2264639e8b1110 2204 62 0x0a90f0059da81a012e9d0a756809fab2ce61cb45965d4d1513a06227783ee4ea 2206 63 0x39fa55971c9e833f61139c39e243d40869fd7e8a1417ee4e7719dd2dd242766f 2208 64 0x22677c1e659caa324f0c74a013921facf62d0d78f273563145cc1ddccfcc4421 2210 65 0x3468cf6df7e93f7ff1fe1dd7e180a89dec3ed4f72843b4ea8a8d780011a245b2 2212 66 0x68f75a0e2210f52a90704ed5f511918d1f6bcfcd26b462cc4975252369db6e9d 2214 67 0x6220c0699696e9bcab0fe3a80d437519bd2bdf3caef665e106b2dd47585ddd9f 2216 68 0x553ad47b129fb347992b576479b0a89f8d71f1196f83e5eaab5f533a1dd6f6d7 2218 69 0x239aef387e116ec8730fa15af053485ca707650d9f8917a75f22acf6213197df 2220 H.2.3. Coefficients of w'(x) 2222 0 0x6bd7f1fc5dd51b7d832848c180f019bcbdb101d4b3435230a79cc4f95c35e15e 2224 1 0x17413bb3ee505184a504e14419b8d7c8517a0d268f65b0d7f5b0ba68d6166dd0 2226 2 0x47f4471beed06e5e2b6d5569c20e30346bdba2921d9676603c58e55431572f90 2228 3 0x2af7eaafd04f6910a5b01cdb0c27dca09487f1cd1116b38db34563e7b0b414eb 2230 4 0x57f0a593459732eef11d2e2f7085bf9adf534879ba56f7afd17c4a40d3d3477b 2232 5 0x4da04e912f145c8d1e5957e0a9e44cca83e74345b38583b70840bdfdbd0288ed 2234 6 0x7cc9c3a51a3767d9d37c6652c349adc09bfe477d99f249a2a7bc803c1c5f39ed 2236 7 0x425d7e58b8adf87eebf445b424ba308ee7880228921651995a7eab548180ad49 2238 8 0x48156db5c99248234c09f43fedf509005943d3d5f5d7422621617467b06d314f 2240 9 0x0d837dbbd1af32d04e2699cb026399c1928472aa1a7f0a1d3afd24bc9923456a 2242 10 0x5b8806e0f924e67c1f207464a9d025758c078b43ddc0ea9afe9993641e5650be 2244 11 0x29c91284e5d14939a6c9bc848908bd9df1f8346c259bbd40f3ed65182f3a2f39 2246 12 0x25550b0f3bceef18a6bf4a46c45bf1b92f22a76d456bfdf19d07398c80b0f946 2247 13 0x495d289b1db16229d7d4630cb65d52500256547401f121a9b09fb8e82cf01953 2249 14 0x718c8c610ea7048a370eabfd9888c633ee31dd70f8bcc58361962bb08619963e 2251 15 0x55d8a5ceef588ab52a07fa6047d6045550a5c52c91cc8b6b82eeb033c8ca557d 2253 16 0x620b5a4974cc3395f96b2a0fa9e6454202ef2c00d82b0e6c534b3b1d20f9a572 2255 17 0x4991b763929b00241a1a9a68e00e90c5df087f90b3352c0f4d8094a51429524e 2257 18 0x18b6b49c5650fb82e36e25fd4eb6decfdd40b46c37425e6597c7444a1b6afb4e 2259 19 0x6868305b4f40654460aad63af3cb9151ab67c775eaac5e5df90d3aea58dee141 2261 20 0x16bc90219a36063a22889db810730a8b719c267d538cd28fa7c0d04f124c8580 2263 21 0x3628f9cf1fbe3eb559854e3b1c06a4cd6a26906b4e2d2e70616a493bba2dc574 2265 22 0x64abcc6759f1ce1ab57d41e17c2633f717064e35a7233a6682f8cf8e9538afec 2267 23 0x01 2269 Appendix I. Point Compression 2271 Point compression allows a shorter representation of affine points of 2272 an elliptic curve by exploiting algebraic relationships between the 2273 coordinate values based on the defining equation of the curve in 2274 question. Point decompression refers to the reverse process, where 2275 one tries and recover the affine point from its compressed 2276 representation and information on the domain parameters of the curve. 2277 Consequently, point compression followed by point decompression is 2278 the identity map. 2280 The description below makes use of an auxiliary function (the parity 2281 function), which we first define for prime fields GF(p) and then 2282 extend to all fields GF(q), where q is an odd prime power. We assume 2283 each finite field to be unambiguously defined. 2285 Let y be a nonzero element of GF(q). If q:=p is an odd prime number, 2286 y and p-y can be uniquely represented as integers in the interval 2287 [1,p-1] and have odd sum p. Consequently, one can distinguish y from 2288 -y via the parity of this representation, i.e., via par(y):=y (mod 2289 2). If q:=p^m, where p is an odd prime number and where m>0, both y 2290 and -y can be uniquely represented as vectors of length m, with 2291 coefficients in GF(p) (see Appendix B.2). In this case, the leftmost 2292 nonzero coordinate values of y and -y are in the same position and 2293 have representations in [1,p-1] with different parity. As a result, 2294 one can distinguish y from -y via the parity of the representation of 2295 this coordinate value. This extends the definition of the parity 2296 function to any odd-size field GF(q), where one defines par(0):=0. 2298 I.1. Point Compression for Weierstrass Curves 2300 If P:=(X, Y) is an affine point of the Weierstrass curve W_{a,b} 2301 defined over the field GF(q), then so is -P:=(X, -Y). Since the 2302 defining equation Y^2=X^2+a*X+b has at most two solutions with fixed 2303 X-value, one can represent P by its X-coordinate and one bit of 2304 information that allows one to distinguish P from -P, i.e., one can 2305 represent P as the ordered pair compr(P):=(X, par(Y)). If P is a 2306 point of order two, one can uniquely represent P by its X-coordinate 2307 alone, since Y=0 and has fixed parity. Conversely, given the ordered 2308 pair (X, t), where X is an element of GF(q) and where t=0 or t=1, and 2309 the domain parameters of the curve, one can use the defining equation 2310 of the curve to try and determine candidate values for the 2311 Y-coordinate given X, by solving the quadratic equation Y^2:=alpha, 2312 where alpha:=X^3+a*X+b. If alpha is not a square in GF(q), this 2313 equation does not have a solution in GF(q) and the ordered pair (X, 2314 t) does not correspond to a point of this curve. Otherwise, there 2315 are two solutions, viz. Y=sqrt(alpha) and -Y. If alpha is a nonzero 2316 element of GF(q), one can uniquely recover the Y-coordinate for which 2317 par(Y):=t and, thereby, the point P:=(X, Y). This is also the case 2318 if alpha=0 and t=0, in which case Y=0 and the point P has order two. 2319 However, if alpha=0 and t=1, the ordered pair (X, t) does not 2320 correspond to the outcome of the point compression function. 2322 We extend the definition of the point compression function to all 2323 points of the curve W_{a,b}, by associating the (non-affine) point at 2324 infinity O with any ordered pair compr(O):=(X,0), where X is any 2325 element of GF(q) for which alpha:=X^3+a*X+b is not a square in GF(q), 2326 and recover this point accordingly. In this case, the point at 2327 infinity O can be represented by any ordered pair (X,0) of elements 2328 of GF(q) for which X^3+a*X+b is not a square in GF(q). Note that 2329 this ordered pair does not satisfy the defining equation of the curve 2330 in question. An application may fix a specific suitable value of X 2331 or choose multiple such values and use this to encode additonal 2332 information. Further details are out of scope. 2334 I.2. Point Compression for Montgomery Curves 2336 If P:=(u, v) is an affine point of the Montgomery curve M_{A,B} 2337 defined over the field GF(q), then so is -P:=(u, -v). Since the 2338 defining equation B*v^2=u^3+A*u^2+u has at most two solutions with 2339 fixed u-value, one can represent P by its u-coordinate and one bit of 2340 information that allows one to distinguish P from -P, i.e., one can 2341 represent P as the ordered pair compr(P):=(u, par(v)). If P is a 2342 point of order two, one can uniquely represent P by its u-coordinate 2343 alone, since v=0 and has fixed parity. Conversely, given the ordered 2344 pair (u, t), where u is an element of GF(q) and where t=0 or t=1, and 2345 the domain parameters of the curve, one can use the defining equation 2346 of the curve to try and determine candidate values for the 2347 v-coordinate given u, by solving the quadratic equation v^2:=alpha, 2348 where alpha:=(u^3+A*u^2+u)/B. If alpha is not a square in GF(q), 2349 this equation does not have a solution in GF(q) and the ordered pair 2350 (u, t) does not correspond to a point of this curve. Otherwise, 2351 there are two solutions, viz. v=sqrt(alpha) and -v. If alpha is a 2352 nonzero element of GF(q), one can uniquely recover the v-coordinate 2353 for which par(v):=t and, thereby, the affine point P:=(u, v). This 2354 is also the case if alpha=0 and t=0, in which case v=0 and the point 2355 P has order two. However, if alpha=0 and t=1, the ordered pair (u, 2356 t) does not correspond to the outcome of the point compression 2357 function. 2359 We extend the definition of the point compression function to all 2360 points of the curve M_{A,B}, by associating the (non-affine) point at 2361 infinity O with the ordered pair compr(O):=(0,1) and recover this 2362 point accordingly. (Note that this corresponds to the case alpha=0 2363 and t=1 above.) The point at infinity O can be represented by the 2364 ordered pair (0, 1) of elements of GF(q). Note that this ordered 2365 pair does not satisfy the defining equation of the curve in question. 2367 I.3. Point Compression for Twisted Edwards Curves 2369 If P:=(x, y) is an affine point of the twisted Edwards curve E_{a,d} 2370 defined over the field GF(q), then so is -P:=(-x, y). Since the 2371 defining equation a*x^2+y^2=1+d*x^2*y^2 has at most two solutions 2372 with fixed y-value, one can represent P by its y-coordinate and one 2373 bit of information that allows one to distinguish P from -P, i.e., 2374 one can represent P as the ordered pair compr(P):=(par(x), y). If P 2375 is a point of order one or two, one can uniquely represent P by its 2376 y-coordinate alone, since x=0 and has fixed parity. Conversely, 2377 given the ordered pair (t, y), where y is an element of GF(q) and 2378 where t=0 or t=1, and the domain parameters of the curve, one can use 2379 the defining equation of the curve to try and determine candidate 2380 values for the x-coordinate given y, by solving the quadratic 2381 equation x^2:=alpha, where alpha:=(1-y^2)/(a-d*y^2). If alpha is not 2382 a square in GF(q), this equation does not have a solution in GF(q) 2383 and the ordered pair (t, y) does not correspond to a point of this 2384 curve. Otherwise, there are two solutions, viz. x=sqrt(alpha) and 2385 -x. If alpha is a nonzero element of GF(q), one can uniquely recover 2386 the x-coordinate for which par(x):=t and, thereby, the affine point 2387 P:=(x, y). This is also the case if alpha=0 and t=0, in which case 2388 x=0 and the point P has order one or two. However, if alpha=0 and 2389 t=1, the ordered pair (t, y) does not correspond to the outcome of 2390 the point compression function. 2392 Note that the point compression function is defined for all points of 2393 the twisted Edwards curve E_{a,d} (subject to the Note in 2394 Appendix C.3). Here, the identity element O:=(0,1) is associated 2395 with the compressed point compr(O):=(0,1). (Note that this 2396 corresponds to the case alpha=0 and t=0 above.) 2398 We extend the definition of the compression function further, to also 2399 include a special marker element 'btm', by associating this marker 2400 element with the ordered pair compr(btm):=(1,1) and recover this 2401 marker element accordingly. (Note that this corresponds to the case 2402 alpha=0 and t=1 above.) The marker element 'btm' can be represented 2403 by the ordered pair (1,1) of elements of GF(q). Note that this 2404 ordered pair does not satisfy the defining equation of the curve in 2405 question. 2407 Appendix J. Data Conversions 2409 The string over some alphabet S consisting of the symbols x_{l-1}, 2410 x_{l-2}, ..., x_1, x_0 (each in S), in this order, is denoted by 2411 str(x_{l-1}, x_{l-2}, ..., x_1, x_0). The length of this string 2412 (over S) is the number of symbols it contains (here: l). The empty 2413 string is the (unique) string of length l=0. 2415 The right-concatenation of two strings X and Y (defined over the same 2416 alphabet) is the string Z consisting of the symbols of X (in the same 2417 order) followed by the symbols of Y (in the same order). The length 2418 of the resulting string Z is the sum of the lengths of X and Y. This 2419 string operation is denoted by Z:=X||Y. The string X is called a 2420 prefix of Z; the string Y a postfix. The t-prefix of a string Z of 2421 length l is its unique prefix X of length t; the t-postfix its unique 2422 postfix Y of length t (where we define these notions as well if t is 2423 outside the interval [0,l]: a t-prefix or t-postfix is the empty 2424 string if t is negative and is the entire string Z if t is larger 2425 than l). Sometimes, a t-prefix of a string Z is denoted by trunc- 2426 left(Z,t); a t-postfix by trunc-right(Z,t). A string X is called a 2427 substring of Z if it is a prefix of some postfix of Z. The string 2428 resulting from prepending the string Y with X is the string X||Y. 2430 An octet is an integer in the interval [0,256). An octet string is a 2431 string, where the alphabet is the set of all octets. A binary string 2432 (or bit string, for short) is a string, where the alphabet is the set 2433 {0,1}. Note that the length of a string is defined in terms of the 2434 underlying alphabet, as are the operations in the previous paragraph. 2436 J.1. Conversion between Bit Strings and Integers 2438 There is a 1-1 correspondence between bit strings of length l and the 2439 integers in the interval [0, 2^l), where the bit string 2440 X:=str(x_{l-1}, x_{l-2}, ..., x_1, x_0) corresponds to the integer 2441 x:=x_{l-1}*2^{l-1} + x_{l-2}*2^{l-2} + ... + x_1*2 + x_0*1. (If l=0, 2442 the empty bit string corresponds to the integer zero.) Note that 2443 while the mapping from bit strings to integers is uniquely defined, 2444 the inverse mapping from integers to bit strings is not, since any 2445 non-negative integer smaller than 2^t can be represented as a bit 2446 string of length at least t (due to leading zero coefficients in base 2447 2 representation). The latter representation is called tight if the 2448 bit string representation has minimal length. 2450 J.2. Conversion between Octet Strings and Integers (OS2I, I2OS) 2452 There is a 1-1 correspondence between octet strings of length l and 2453 the integers in the interval [0, 256^l), where the octet string 2454 X:=str(X_{l-1}, X_{l-2}, ..., X_1, X_0) corresponds to the integer 2455 x:=X_{l-1}*256^{l-1} + X^{l-2}*256^{l-2} + ... + X_1*256 + X_0*1. 2456 (If l=0, the empty string corresponds to the integer zero.) Note 2457 that while the mapping from octet strings to integers is uniquely 2458 defined, the inverse mapping from integers to octet strings is not, 2459 since any non-negative integer smaller than 256^t can be represented 2460 as an octet string of length at least t (due to leading zero 2461 coefficients in base 256 representation). The latter representation 2462 is called tight if the octet string representation has minimal 2463 length. This defines the mapping OS2I from octet strings to integers 2464 and the mapping I2OS(x,l) from non-negative integers smaller than 2465 256^l to octet strings of length l. 2467 J.3. Conversion between Octet Strings and Bit Strings (BS2OS, OS2BS) 2469 There is a 1-1 correspondence between octet strings of length l and 2470 and bit strings of length 8*l, where the octet string X:=str(X_{l-1}, 2471 X_{l-2}, ..., X_1, X_0) corresponds to the right-concatenation of the 2472 8-bit strings x_{l-1}, x_{l-2}, ..., x_1, x_0, where each octet X_i 2473 corresponds to the 8-bit string x_i according to the mapping of 2474 Appendix J.1 above. Note that the mapping from octet strings to bit 2475 strings is uniquely defined and so is the inverse mapping from bit 2476 strings to octet strings, if one prepends each bit string with the 2477 smallest number of 0 bits so as to result in a bit string of length 2478 divisible by eight (i.e., one uses pre-padding). This defines the 2479 mapping OS2BS from octet strings to bit strings and the corresponding 2480 mapping BS2OS from bit strings to octet strings. 2482 J.4. Conversion between Field Elements and Octet Strings (FE2OS, OS2FE) 2484 There is a 1-1 correspondence between elements of a fixed finite 2485 field GF(q), where q=p^m and m>0, and vectors of length m, with 2486 coefficients in GF(p), where each element x of GF(q) is a vector 2487 (x_{m-1}, x_{m-2}, ..., x_1, x_0) according to the conventions of 2488 Appendix B.2. In this case, this field element can be uniquely 2489 represented by the right-concatenation of the octet strings X_{m-1}, 2490 X_{m-2}, ..., X_1, X_0, where each octet string X_i corresponds to 2491 the integer x_i in the interval [0,p-1] according to the mapping of 2492 Appendix J.2 above. Note that both the mapping from field elements 2493 to octet strings and the inverse mapping are only uniquely defined if 2494 each octet string X_i has the same fixed size (e.g., the smallest 2495 integer l so that 256^l >= p) and if all integers are reduced modulo 2496 p. If so, the latter representation is called tight if l is minimal 2497 so that 256^l >= p. This defines the mapping FE2OS(x,l) from field 2498 elements to octet strings and the mapping OS2FE(X,l) from octet 2499 strings to field elements, where the underlying field is implicit and 2500 assumed to be known from context. In this case, the octet string has 2501 length l*m. 2503 J.5. Conversion between Elements of Z mod n and Octet Strings (ZnE2OS, 2504 OS2ZnE) 2506 There is a 1-1 correspondence between elements of a fixed set Z(n) of 2507 integers modulo n and integers in the interval [0,n), where each 2508 element x can be uniquely represented by the octet string 2509 corresponding to the integer x modulo n according to the mapping of 2510 Appendix J.2 above. Note that both the mapping from elements of Z(n) 2511 to octet strings and the inverse mapping are only uniquely defined if 2512 the octet string has a fixed size (e.g., the smallest integer l so 2513 that 256^l >= n) and if all integers are reduced modulo n. If so, 2514 the latter representation is called tight if l is minimal so that 2515 256^l >= n. This defines the mapping ZnE2OS(x,l) from elements of 2516 Z(n) to octet strings and the mapping OS2ZnE(X,l) from octet strings 2517 to elements of Z(n), where the underlying modulus n is implicit and 2518 assumed to be known from context. In this case, the octet string has 2519 length l. 2521 Note that if n is a prime number p, the conversions ZnE2OS and FE2OS 2522 are consistent, as are OS2ZnE and OS2FE. This is, however, no longer 2523 the case if n is a strict prime power. 2525 The conversion rules for composite n values are useful, e.g., when 2526 encoding the modulus n of RSA (or elements of any other non-prime set 2527 Z(n), for that matter). 2529 J.6. Ordering Conventions 2531 One can consider various representation functions, depending on bit- 2532 ordering and octet-ordering conventions. 2534 The description below makes use of an auxiliary function (the 2535 reversion function), which we define both for bit strings and octet 2536 strings. For a bit string [octet string] X:=str(x_{l-1}, x_{l-2}, 2537 ..., x_1, x_0), its reverse is the bit string [octet string] 2538 X':=rev(X):=str(x_0, x_1, ..., x_{l-2}, x_{l-1}). 2540 We now describe representations in most-significant-bit first (msb) 2541 or least-significant-bit first (lsb) order and those in most- 2542 significant-byte first (MSB) or least-significant-byte first (LSB) 2543 order. 2545 One distinguishes the following octet-string representations of 2546 integers and field elements: 2548 1. MSB, msb: represent field elements and integers as above, 2549 yielding the octet string str(X_{l-1}, X_{l-2}, ..., X_1, X_0). 2551 2. MSB, lsb: reverse the bit-order of each octet, viewed as 8-bit 2552 string, yielding the octet string str((rev(X_{l-1}), 2553 rev(X_{l-2}), ..., rev(X_1), rev(X_0)). 2555 3. LSB, lsb: reverse the octet string and bit-order of each octet, 2556 yielding the octet string str(rev(X_{0}), rev(X_{1}), ..., 2557 rev(X_{l-2}), rev(X_{l-1})). 2559 4. LSB, msb: reverse the octet string, yielding the octet string 2560 str(X_{0}, X_{1}, ..., X_{l-2}, X_{l-1}). 2562 Thus, the 2-octet string "07e3" represents the integer 2019 (=0x07e3) 2563 in MSB/msb order, the integer 57,543 (0xe0c7) in MSB/lsb order, the 2564 integer 51,168 (0xc7e0) in LSB/lsb order, and the integer 58,119 2565 (=0xe307) in LSB/msb order. 2567 Note that, with the above data conversions, there is still some 2568 ambiguity as to how to represent an integer or a field element as a 2569 bit string or octet string (due to leading zeros). However, tight 2570 representations (as defined above) are non-ambiguous. (Note, in 2571 particular, that tightness implies that elements of GF(q) are always 2572 uniquely represented.) 2574 Note that elements of a prime field GF(p), where p is a 255-bit prime 2575 number, have a tight representation as a 32-byte string, where a 2576 fixed bit position is always set to zero. (This is the leftmost bit 2577 position of this octet string if one follows the MSB/msb 2578 representation conventions.) This allows the parity bit of a 2579 compressed point (see Appendix I) to be encoded in this bit position 2580 and, thereby, allows a compressed point and a field element of GF(p) 2581 to be represented by an octet string of the same length. This is 2582 called the squeezed point representation. Obviously, other 2583 representations (e.g., those of elements of Z(n)) may also have fixed 2584 bit values on certain positions, which can be used to squeeze-in 2585 additional information. Further details are out of scope. 2587 Appendix K. Representation Examples Curve25519 Family Members 2589 We present some examples of computations using the curves introduced 2590 in this document. In each case, we indicate the values of P, k*P, 2591 and (k+1)*P, where P is a fixed multiple (here: 2019) of the base 2592 point of the curve in question and where the private key k is the 2593 integer 2595 k 45467544759954639344191351164156560595299236761702065033670739677 2596 691372543056 2598 (=0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3 2599 c08d5abd 15e29c50). 2601 K.1. Example with Curve25519 2603 Pm=(u, v), k*Pm=(u1, v1), and (k+1)*Pm=(u2, v2) with Curve25519: 2605 u 53025657538808013645618620393754461319535915376830819974982289332 2606 088255623750 2608 (=0x753b7566 df35d574 4734142c 9abf931c ea290160 aa75853c 2609 7f972467 b7f13246). 2611 v 53327798092436462013048370302019946300826511459161905709144645521 2612 233690313086 2614 (=0x75e676ce deee3b3c 12942357 22f1d884 ac06de07 330fb07b 2615 ae35ca26 df75417e). 2617 u1 42039618818474335439333192910143029294450651736166602435248528442 2618 691717668056 2620 (=0x5cf194be f0bdd6d6 be58e18a 8f16740a ec25f4b0 67f7980a 2621 23bb6468 88bb9cd8). 2623 v1 76981661982917351630937517222412729130882368858134322156485762195 2624 67913357634 2625 (=0x110501f6 1dff511e d6c4e9b9 bfd5acbe 8bf043b8 c3e381dd 2626 f5771306 479ad142). 2628 u2 34175116482377882355440137752573651838273760818624557524643126101 2629 82464621878 2631 (=0x078e3e38 41c3e0d0 373e5454 ecffae33 2798b10a 55c72117 2632 62629f97 f1394d36). 2634 v2 43046985853631671610553834968785204191967171967937842531656254539 2635 962663994648 2637 (=0x5f2bbb06 f7ec5953 2c2a1a62 21124585 1d2682e0 cc37307e 2638 fbc17f7f 7fda8518). 2640 As suggested in Appendix C.2, the v-coordinate of k*Pm can be 2641 indirectly computed from the u-coordinates of Pm, k*Pm, and (k+1)*Pm, 2642 and the v-coordinate of Pm, which allows computation of the entire 2643 point k*Pm (and not just its u-coordinate) if k*Pm is computed using 2644 the Montgomery ladder (as, e.g., [RFC7748] recommends), since that 2645 algorithm computes both u1 and u2 and the v-coordinate of the point 2646 Pm may be available from context. 2648 The representation of k and the compressed representations of Pm and 2649 k*Pm in tight LSB/msb-order are given by 2651 repr(k) 0x509ce215 bd5a8dc0 c3328c77 5dc6f59c 4d4915f9 e4bf5d0d 2652 c2e583cd e6b78564 2654 repr(Pm) 0x4632f1b7 6724977f 3c8575aa 600129ea 1c93bf9a 2c143447 2655 74d535df 66753b75; 2657 repr(k*Pm) 0xd89cbb88 6864bb23 0a98f767 b0f425ec 0a74168f 8ae158be 2658 d6d6bdf0 be94f15c, 2660 where the leftmost bit of the rightmost octet indicates the parity of 2661 the v-coordinate of the point of Curve25519 in question (which, in 2662 this case, are both zero, since v and v1 are even). See Appendix I.2 2663 and Appendix J for further detail on (squeezed) point compression. 2665 The scalar representation and (squeezed) point representation 2666 illustrated above are consistent with the representations specified 2667 in [RFC7748], except that in [RFC7748] only an affine point's 2668 u-coordinate is represented (i.e., the v-coordinate of any point is 2669 always implicitly assumed to have an even value) and that the 2670 representation of the point at infinity is not specified. Another 2671 difference is that [RFC7748] allows non-unique representations of 2672 some elements of GF(p), whereas our representation conventions do not 2673 (since tight). 2675 A randomized representation (t1, t2) of the point k*Pm in tight LSB/ 2676 msb order is given by 2678 t1 409531317901122685707535715924445398426503483189854716584 2679 37762538294289253464 2681 (=0x5844b232 8c4586dc 62f593c5 599c2a8c e61ba893 bb052de6 2682 77510a42 b3a68a5a) 2684 t2 451856098332889407421278004628150814449259902023388533929 2685 08848927625430980881 2687 (=0x11598452 e65138dc ce948d7e d8f46a18 b640722c 8e170957 2688 751b7729 1b26e663), 2690 where this representation is defined in Appendix L.4 and uses the 2691 mapping of Appendix L.3.2 with the default square root function. 2693 K.2. Example with Edwards25519 2695 Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Edwards25519: 2697 x 25301662348702136092602268236183361085863932475593120475382959053 2698 365387223252 2700 (=0x37f03bc0 1070ed12 d3218f8b ba1abb74 fd6b94eb 62033d09 2701 83851e21 d6a460d4). 2703 y 54434749145175762798550436656748568411099702168121592090608501578 2704 942019473360 2706 (=0x7858f9e7 6774ed8e 23d614d2 36715fc7 56813b02 9aa13c18 2707 960705c5 b3a30fd0). 2709 x1 42966967796585460733861724865699548279978730460766025087444502812 2710 416557284873 2712 (=0x5efe7124 465b5bdb b364bb3e e4f106e2 18d59b36 48f4fe83 2713 c11afc91 785d7e09). 2715 y1 46006463385134057167371782068441558951541960707376246310705917936 2716 352255317084 2718 (=0x65b6bc49 985badaf bc5fdd96 fb189502 35d5effd 540b439d 2719 60508827 80bc945c). 2721 x2 42629294840915692510487991904657367226900127896202625319538173473 2722 104931719808 2724 (=0x5e3f536a 3be2364a 1fa775a3 5f8f65ae 93f4a89d 81a04a2e 2725 87783748 00120a80). 2727 y2 29739282897206659585364020239089516293417836047563355347155817358 2728 737209129078 2730 (=0x41bfd66e 64bdd801 c581a720 f48172a8 187445fa 350924a2 2731 c92c791e 38d57876). 2733 The representation of k and the compressed representations of Pe and 2734 k*Pe in tight LSB/lsb-order are given by 2736 repr(k) =0x0a3947a8 bd5ab103 c34c31ee ba63af39 b292a89f 27fdbab0 2737 43a7c1b3 67eda126; 2739 repr(Pe) =0x0bf0c5cd a3a0e069 183c8559 40dc816a e3fa8e6c 4b286bc4 2740 71b72ee6 e79f1a1e; 2742 repr(k*Pe) =0x3a293d01 e4110a06 b9c2d02a bff7abac 40a918df 69bbfa3d 2743 f5b5da19 923d6da7, 2745 where the rightmost bit of the rightmost octet indicates the parity 2746 of the x-coordinate of the point of Edwards25519 in question (which, 2747 in this case, are zero and one, respectively, since x is even and x1 2748 is odd). See Appendix I.3 and Appendix J for further detail on 2749 (squeezed) point compression. 2751 The scalar representation and (squeezed) point representation 2752 illustrated above are fully consistent with the representations 2753 specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032] 2754 requires unique representations of all elements of GF(p). 2756 A randomized representation (t1, t2) of the point k*Pe in tight LSB/ 2757 lsb order is given by 2759 t1 577913017083163641949634219017190182170288776648725395935 2760 97750427519399254040 2762 (=0x181a32c5 10e06dbc ea321882 f3519055 535e289e 8faac654 2763 82e26f61 aded23fe) 2765 t2 454881407940919718426608573125377401686255068210624245884 2766 05479716220480287974 2767 (=0x672e36c5 ae353073 cdfac343 e8297b05 1b010d0f 5b1016db 2768 dd4baf54 28068926), 2770 where this representation is defined in Appendix L.4 and uses the 2771 mapping of Appendix L.3.3 with the default square root function and 2772 underlying isomorphic mapping between Edwards25519 and Curve25519 of 2773 Appendix E.2. 2775 K.3. Example with Wei25519 2777 Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519: 2779 X 14428294459702615171094958724191825368445920488283965295163094662 2780 783879239338 2782 (=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7 2783 2a41cf12 629e56aa). 2785 Y 53327798092436462013048370302019946300826511459161905709144645521 2786 233690313086 2788 (=0x75e676ce deee3b3c 12942357 22f1d884 ac06de07 330fb07b 2789 ae35ca26 df75417e). 2791 X1 34422557393689369648095312405803933433606568476197477554293337733 2792 87341283644 2794 (=0x079c3f69 9b688181 69038c35 39c11eb5 96d09f5b 12a242b4 2795 ce660f13 3368c13c). 2797 Y1 76981661982917351630937517222412729130882368858134322156485762195 2798 67913357634 2800 (=0x110501f6 1dff511e d6c4e9b9 bfd5acbe 8bf043b8 c3e381dd 2801 f5771306 479ad142). 2803 X2 22716193187790487472805844610038683159372373526135883092373909944 2804 834653057415 2806 (=0x3238e8e2 ec6e8b7a e1e8feff 97aa58dd d2435bb5 0071cbc2 2807 0d0d4a42 9be67187). 2809 Y2 43046985853631671610553834968785204191967171967937842531656254539 2810 962663994648 2812 (=0x5f2bbb06 f7ec5953 2c2a1a62 21124585 1d2682e0 cc37307e 2813 fbc17f7f 7fda8518). 2815 The representation of k and the compressed representations of Pw and 2816 k*Pw in tight MSB/msb-order are given by 2818 repr(k) =0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3 2819 c08d5abd 15e29c50; 2821 repr(Pw) =0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7 2822 2a41cf12 629e56aa; 2824 repr(k*Pw) =0x079c3f69 9b688181 69038c35 39c11eb5 96d09f5b 12a242b4 2825 ce660f13 3368c13c, 2827 where the leftmost bit of the leftmost octet indicates the parity of 2828 the Y-coordinate of the point of Wei25519 in question (which, in this 2829 case, are both zero, since Y and Y1 are even). See Appendix I.1 and 2830 Appendix J for further detail on (squeezed) point compression. 2832 The scalar representation is consistent with the representations 2833 specified in [SEC1]; the (squeezed) point representation illustrated 2834 above is "new". For completeness, we include a SEC1-consistent 2835 representation of the point Pw in affine format and in compressed 2836 format below. 2838 The SEC1-compliant affine representation of the point Pw in tight 2839 MSB/msb-order is given by 2841 aff(Pw) =0x04 1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 2842 55202fe7 2a41cf12 629e56aa 2844 75e676ce deee3b3c 12942357 22f1d884 ac06de07 330fb07b 2845 ae35ca26 df75417e, 2847 whereas the SEC1-compliant compressed representation of the point Pw 2848 in tight MSB/msb-order is given by 2850 compr(Pw) =0x02 1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 2851 55202fe7 2a41cf12 629e56aa; 2853 The SEC1-compliant uncompressed format aff(Pw) of an affine point Pw 2854 corresponds to the right-concatenation of its X- and Y-coordinates, 2855 each in tight MSB/msb-order, prepended by the string 0x04, where the 2856 reverse procedure is uniquely defined, since elements of GF(p) have a 2857 unique fixed-size representation. The (squeezed) compressed format 2858 repr(Pw) corresponds to the SEC1-compliant compressed format by 2859 extracting the parity bit t from the leftmost bit of the leftmost 2860 octet of repr(Pw), replacing the bit position by the value zero, and 2861 prepending the octet string with 0x02 or 0x03, depending on whether 2862 t=0 or t=1, respectively, where the reverse procedure is uniquely 2863 defined, since GF(p) is a 255-bit prime field. For further details, 2864 see [SEC1]. 2866 A randomized representation (t1, t2) of the point k*Pw in tight MSB/ 2867 msb order is given by 2869 t1 446363445988889734093446280484122107283059206243307955388 2870 84223152228795899590 2872 (=0x62af4697 4dd469ac 96c64809 c16c8517 b6a0cee5 40ba0e2e 2873 6dd2b36a fcc75ec6) 2875 t2 213890166610228613105792710708385961712211281744756216061 2876 11930888059603107561 2878 (=0x2f49c121 8fed7912 031157ee ae066507 a972320b 6180e267 2879 4025b006 2e67bee9), 2881 where this representation is defined in Appendix L.4 and uses the 2882 mapping of Appendix L.3.1 with the default square root function. 2884 K.4. Example with Wei25519.2 2886 Pw2=(X, Y), k*Pw2=(X1, Y1), and (k+1)*Pw2=(X2, Y2) with Wei25519.2: 2888 X 17830493209951148331008014701079988862634531394137235438571836389 2889 227198459763 2891 (=0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c 2892 f21c8672 d1ecaf73). 2894 Y 21064492012933896105338241940477778461866060481408222122979836206 2895 137075789640 2897 (=0x2e921479 5ad47af7 784831de 572ed8e9 7e20e137 cc67378c 2898 184ca19f f9136f48). 2900 X1 65470988951686461979789632362377759464688342154017353834939203791 2901 39281908968 2903 (=0x0e7986d2 e94354ab 8abd8806 3154536a 4dcf8e6e 65557183 2904 e242192d 3b87f4e8). 2906 Y1 51489590494292183562535790579480033229043271539297275888817125227 2907 35262330110 2909 (=0x0b623521 c1ff84bc 1522ff26 3376796d be77fcad 1fcabc28 2910 98f1be85 d7576cfe). 2912 X2 83741788501517200942826153677682120998854086551751663061374935388 2913 3494226693 2915 (=0x01d9f633 b2ac2606 9e6e93f7 6917446c 2b27c16f 729121d7 2916 709c0a58 00ef9b05). 2918 Y2 42567334190622848157611574766896093933050043101247319937794684825 2919 168161540336 2921 (=0x5e1c41e1 fb74e41b 3a19ce50 e1b2caf7 7cabcbb3 0c1c1474 2922 a4fd13e6 6c4c08f0). 2924 The representation of k and the compressed representations of Pw2 and 2925 k*Pw2 in tight MSB/msb-order are given by 2927 repr(k) =0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3 2928 c08d5abd 15e29c50; 2930 repr(Pw2) =0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c 2931 f21c8672 d1ecaf73; 2933 repr(k*Pw2) =0x0e7986d2 e94354ab 8abd8806 3154536a 4dcf8e6e 65557183 2934 e242192d 3b87f4e8, 2936 where the leftmost bit of the leftmost octet indicates the parity of 2937 the Y-coordinate of the point of Wei25519.2 in question (which, in 2938 this case, are both zero, since Y and Y1 are even). See 2939 Appendix Appendix I.1 and Appendix J for further detail on (squeezed) 2940 point compression. 2942 A randomized representation (t1, t2) of the point k*Pw2 in tight MSB/ 2943 msb order is given by 2945 t1 416669672354928148679758598803660112405431159793278161879 2946 36189858804289581274 2948 (=0x5c1eaaef 80f9d4af 33c119fc c99acd58 f81e7d69 999c7048 2949 e4043a77 87a930da) 2951 t2 361115271162391608083096560179337391059615651279123199921 2952 18531180247832114098 2954 (=0x4fd66668 e7174775 de44c852 92df8cfe b9832ef8 2570b3b8 2955 fe5ec21a b2d4b3b2), 2957 where this representation is defined in Appendix L.4 and uses the 2958 mapping of Appendix L.3.1 with the default square root function. 2960 K.5. Example with Wei25519.-3 2962 Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei25519.-3: 2964 X 14780197759513083469009623947734627174363231692126610860256057394 2965 455099634096 2967 (=0x20ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00 2968 eb4c9272 03ca71b0). 2970 Y 45596733430378470319805536538617129933663237960146030424392249401 2971 952949482817 2973 (=0x64ced628 e982648e 4bfcf30c 71c4d267 ba48b0ce fee20062 2974 b43ef4c9 73f7b541). 2976 X1 47362979975244556396292400751828272600887612546997532158738958926 2977 60745725532 2979 (=0x0a78a650 a39995ef dcf4de88 940d4ce9 5b2ca35c c5d70e06 2980 63b8455e 2e04e65c). 2982 Y1 30318112837157047703426636957515037640997356617656007157255559136 2983 153389790354 2985 (=0x64ced628 e982648e 4bfcf30c 71c4d267 ba48b0ce fee20062 2986 b43ef4c9 73f7b541). 2988 X2 23778942085873786433506063022059853212880296499622328201295446580 2989 293591664363 2991 (=0x3492677e 6ae9d1c3 e08f908b 61033f3d 4e8322c9 fba6da81 2992 2c95b067 9b1486eb). 2994 Y2 44846366394651736248316749170687053272682847823018287439056537991 2995 969511150494 2997 (=0x632624d4 ab94c83a 796511c0 5f5412a3 876e56d2 ed18eca3 2998 21b95bef 7bf9939e). 3000 The representation of k and the compressed representations of Pw3 and 3001 k*Pw3 in tight MSB/msb-order are given by 3003 repr(k) =0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3 3004 c08d5abd 15e29c50; 3006 repr(Pw3) =0xa0ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00 3007 eb4c9272 03ca71b0; 3009 repr(k*Pw3) =0x0a78a650 a39995ef dcf4de88 940d4ce9 5b2ca35c c5d70e06 3010 63b8455e 2e04e65c, 3012 where the leftmost bit of the leftmost octet indicates the parity of 3013 the Y-coordinate of the point of Wei25519.-3 in question (which, in 3014 this case, are one and zero, respectively, since Y is odd and Y1 is 3015 even). See Appendix I.1 and Appendix J for further detail on 3016 (squeezed) point compression. 3018 A randomized representation (t1, t2) of the point k*Pw3 in tight MSB/ 3019 msb order is given by 3021 t1 573714937613596601525680684642155667097217474964816246889 3022 88981227297409008259 3024 (=0x7ed71d5f 566d2259 99bdb404 bfb9d6cf d2e86ccb 1894d4a6 3025 c75e3c69 e5eb0283) 3027 t2 269945781324580189815142015663892935722419453863927287235 3028 57891665397640090729 3030 (=0x3bae63c8 70f60de0 c2e35f94 d24220f1 bb6efd00 37625869 3031 f84923de ff4c5469), 3033 where this representation is defined in Appendix L.4 and uses the 3034 mapping of Appendix L.3.1 with the default square root function. 3036 Appendix L. Auxiliary Functions 3038 L.1. Square Roots in GF(q) 3040 Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see 3041 Appendix L.1.1) or if q = 5 (mod 8) (see Appendix L.1.2). Details on 3042 how to compute square roots for other values of q are out of scope. 3043 If square roots are easy to compute in GF(q), then so are these in 3044 GF(q^2). 3046 L.1.1. Square Roots in GF(q), where q = 3 (mod 4) 3048 If y is a nonzero element of GF(q) and z:= y^{(q-3)/4}, then y is a 3049 square in GF(q) only if y*z^2=1. If y*z^2=1, z is a square root of 3050 1/y and y*z is a square root of y in GF(q). 3052 L.1.2. Square Roots in GF(q), where q = 5 (mod 8) 3054 If y is a nonzero element of GF(q) and z:=y^{z-5)/8}, then y is a 3055 square in GF(q) only if y^2*z^4=1. 3057 a. If y*z^2=+1, z is a square root of 1/y and y*z is a square root 3058 of y in GF(q); 3060 b. If y*z^2=-1, i*z is a square root of 1/y and i*y*z is a square 3061 root of y. 3063 Here, i is an element of GF(q) for which i^2=-1 (e.g., 3064 i:=2^{(q-1)/4}). This field element can be precomputed. 3066 L.2. Inversion 3068 If y is an integer and gcd(y,n)=1, one can efficiently compute 1/y 3069 (mod n) via the extended Euclidean Algorithm (see Section 2.2.5 of 3070 [GECC]). One can use this algorithm as well to compute the inverse 3071 of a nonzero element y of a prime field GF(p), since gcd(y,p)=1. 3073 The inverse of a nonzero element y of GF(q) can be computed as 3075 1/y:=y^{q-2} (since y^{q-1}=1). 3077 Further details are out of scope. If inverses are easy to compute in 3078 GF(q), then so are these in GF(q^2). 3080 The inverses of two nonzero elements y1 and y2 of GF(q) can be 3081 computed by first computing the inverse z of y1*y2 and by 3082 subsequently computing y2*z=:1/y1 and y1*z=:1/y2. 3084 L.3. Mapping to Curve Points 3086 One can map elements of GF(q) that are not a square in GF(q) to 3087 points of a Weierstrass curve (see Appendix L.3.1), to points of a 3088 Montgomery curve (see Appendix L.3.2), or to points of a twisted 3089 Edwards curve (see Appendix L.3.3), under some mild conditions on the 3090 domain parameters. Full details on mappings that apply if these 3091 conditions are not satisfied are out of scope. 3093 L.3.1. Mapping to Points of Weierstrass Curve 3095 The description below assumes that the domain parameters a and b of 3096 the Weierstrass curve W_{a,b} are nonzero. For ease of exposition, 3097 we define f(z):=z^3+a*z+b. (Note that for an affine point (X,Y) of 3098 W_{a,b} one has Y^2=f(X).) 3100 If t is an element of GF(q) that is not a square in GF(q) and that is 3101 unequal to -1, then the element X:=(-b/a)*(1+1/(t+t^2)) is the unique 3102 solution of the equation f(t*X)=t^3*f(X) and is nonzero. 3103 Consequently, either X or X':=t*X is the x-coordinate of an affine 3104 point of W{a,b}, depending on whether f(X) is a square in GF(q). 3106 a. If f(X) is a square in GF(q) and Y:=sqrt(f(X)), then t is mapped 3107 to the point P(t):=(X, Y); 3109 b. If f(X) is not a square in GF(q) and Y':=sqrt(f(X')), then t is 3110 mapped to the point P(t):=(X', -Y'). 3112 Formally, this mapping is not properly defined, since a nonzero 3113 square y:=x^2 in GF(q) has two solutions, viz. x and -x; it is 3114 properly defined, however, if one designates for each element in 3115 GF(q) that is a square in GF(q) precisely one square root as "the" 3116 square root of this element. Note that always picking the square 3117 root with zero parity (see Appendix I) satisfies this condition 3118 (henceforth called the default square root function). 3120 If -1 is not a square in GF(q), this element is mapped to the point 3121 at infinity O of W_{a,b}. 3123 The set of points of W_{a,b} that arises this way has size roughly 3124 3/8 of the order of the curve and each such point arises as image of 3125 one or two t values. Further details are out of scope. 3127 NOTE 1: If -1 is not a square in GF(q), the mapping above yields the 3128 point at infinity for t=-1. One can modify this mapping to always 3129 yield an affine point, by mapping the element -1 to, e.g., the base 3130 point G of W_{a,b} and leaving the remainder of the mapping the same. 3131 Suitability of such a modification is application-specific. Details 3132 are out of scope. 3134 NOTE 2: The description above assumes that the domain parameters a 3135 and b of the Weierstrass curve are nonzero. If this is not the case, 3136 one can often find an isogenous curve W_{a',b'} for which the domain 3137 parameters a' and b' are nonzero. If so, one can map elements of 3138 GF(q) that are not a square in GF(q) to points of W_{a,b} via 3139 function composition, where one uses the mapping above to arrive at a 3140 point of W_{a',b'} and where one subsequently uses the dual isogeny 3141 from W_{a',b'} to W_{a,b} to arrive at a point of W_{a,b}. As an 3142 example, one can show that if a is zero and -4*b is a cube in GF(q) 3143 (such as is the case with, e.g., the "BitCoin" curve secp256k1 3144 [SEC2]), this curve is 3-isogenous to a curve with this property and 3145 the strategy above applies (for an example with secp256k1, see 3146 Appendix M). Further details are out of scope. 3148 L.3.2. Mapping to Points of Montgomery Curve 3150 The description below assumes that the domain parameter A of the 3151 Montgomery curve M_{A,B} is nonzero. For ease of exposition, we 3152 define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of 3153 M_{A,B} one has B*v^2=f(u).) 3154 If t is an element of GF(q) that is not a square in GF(q) and that is 3155 unequal to -1, then the element u:=-(1+1/t)/A is the unique nonzero 3156 solution of the equation f(t*u)=t^3*f(u). Consequently, either u or 3157 u':=t*u is the u-coordinate of an affine point of M{A,B}, depending 3158 on whether f(u)/B is a square in GF(q). 3160 a. If f(u)/B is a square in GF(q) and v:=sqrt(f(u)/B), then t is 3161 mapped to the point P(t):=(u, v); 3163 b. If f(u)/B is a not a square in GF(q) and v':=sqrt(f(u')/B), then 3164 t is mapped to the point P(t):=(u', -v'). 3166 As before, formally, this mapping is not properly defined, since a 3167 nonzero square y:=x^2 in GF(q) has two solutions, viz. x and -x; it 3168 is properly defined, however, if one designates for each element in 3169 GF(q) that is a square in GF(q) precisely one square root as "the" 3170 square root of this element. Note that always picking the square 3171 root with zero parity (see Appendix I) satisfies this condition 3172 (henceforth called the default square root function). 3174 If -1 is not a square in GF(q), this element is mapped to the point 3175 at infinity O of M_{A,B}. 3177 The set of points of M_{A,B} that arises this way has size roughly 3178 1/2 of the order of the curve and each such point arises as image of 3179 precisely one t value. Further details are out of scope. 3181 NOTE 1: If -1 is not a square in GF(q), the mapping above yields the 3182 point at infinity for t=-1. One can modify this mapping to always 3183 yield an affine point, by mapping the element -1 to, e.g., the base 3184 point G of M_{A,B} and leaving the remainder of the mapping the same. 3185 Suitability of such a modification is application-specific. Details 3186 are out of scope. 3188 NOTE 2: The description above assumes that the domain parameter A of 3189 the Montgomery curve is nonzero. If this is not the case, the curve 3190 is a Weierstrass curve for which the domain parameter b is zero and 3191 Note 2 of Appendix L.3.1 applies. If q = 3 (mod 4), an even simpler 3192 approach is possible, where one modifies the construction above and 3193 simply takes u:=t and u':=-t (which works, since -1 is not a square 3194 in GF(q) and f(-t)=-f(t)). In this case, this construction can be 3195 extended to all elements t of GF(q) and, if so, yields a 1-1 mapping 3196 between GF(q) and all affine curve points. 3198 L.3.3. Mapping to Points of Twisted Edwards Curve 3200 One can map elements of GF(q) that are not a square in GF(q) to 3201 points of the twisted Edwards curve E_{a,d} via function composition, 3202 where one uses the mapping of Appendix L.3.1 to arrive at a point of 3203 the Weierstrass curve W_{a,b} and where one subsequently uses the 3204 isomorphic mapping between twisted Edwards curves and Weierstrass 3205 curves of Appendix D.3 to arrive at a point of E_{a,d}. Another 3206 mapping is obtained by function composition, where one instead uses 3207 the mapping of Appendix L.3.2 to arrive at a point of the Montgomery 3208 curve M_{A,B} and where one subsequently uses the isomorphic mapping 3209 between twisted Edwards curves and Montgomery curves of Appendix D.1 3210 to arrive at a point of E_{a,d}. Obviously, one can use function 3211 composition (now using the respective pre-images - if these exist) to 3212 realize the pre-images of either mapping. 3214 L.4. Randomized Representation of Curve Points 3216 The mappings of Appendix L.3.1, Appendix L.3.2, and Appendix L.3.3 3217 allow one to represent a curve point Q as a specific element of 3218 GF(q), provided this point arises as a point in the range of the 3219 mapping at hand. For Montgomery curves and twisted Edwards curves, 3220 this covers roughly half of the curve points; for Weierstrass curves, 3221 roughly 3/8 of the curve points. One can extend the mappings above, 3222 by mapping a pair (t1, t2) of inputs to the point Q:=P2(t1, 3223 t2):=P(t1) + P(t2). In this case, each curve point has roughly q/4 3224 representations as an ordered pair (t1, t2) on average. In fact, one 3225 can show that if the input pairs are generated uniformly at random, 3226 then the corresponding curve points follow a distribution that is 3227 also (statistically indistinguishable from) a uniform distribution, 3228 and vice-versa. Here, each pair (t1, t2) deterministically yields a 3229 curve point, whereas for each curve point Q, a randomized algorithm 3230 yields an ordered pair (t1, t2) of pre-images of Q, where the 3231 expected number of randomized pre-images one has to try is small 3232 (four if one uses the mapping of Appendix L.3.1; two if one uses the 3233 mapping of Appendix L.3.2). For further details, see Algorithm 1 of 3234 [Tibouchi]. 3236 Appendix M. Curve secp256k1 and Friend 3238 M.1. Curve Definition and Alternative Representation 3240 The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined 3241 over the prime field GF(p), with p:=2^256-2^32-2^9-2^8-2^7-2^6-2^4-1, 3242 where a:=0 and b:=7. This curve has order h*n, where h=1 and where n 3243 is a prime number. For this curve, domain parameter a is zero, 3244 whereas b is not. The quadratic twist of this curve has order h1*n1, 3245 where h1 is a 37-bit integer and where n1 is a prime number. For 3246 this curve, the base point is the point (GX, GY). 3248 The curve secp256k1 is 3-isogenous to the Weierstrass curve 3249 secp256k1.m defined over GF(p), which has nonzero domain parameters a 3250 and b and has as base point the pair (GmX,GmY), where parameters are 3251 as specified in Appendix M.3 and where the related mappings are as 3252 specified in Appendix M.2. 3254 M.2. Switching Between Representations 3256 Each affine point (X,Y) of secp256k1 corresponds to the point 3257 (X',Y'):=(u(X)/w(X)^2,Y*v(X)/w(X)^3) of secp256k1.m, where u, v, and 3258 w are the polynomials with coefficients in GF(p) as defined in 3259 Appendix M.4.1, while the point at infinity of secp256k1 corresponds 3260 to the point at infinity of secp256k1.m. Under this isogenous 3261 mapping, the base point (GX,GY) of secp256k1 corresponds to the base 3262 point (GmX,GmY) of secp256k1.m. The dual isogeny maps the affine 3263 point (X',Y') of secp256k1.m to the affine point 3264 (X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of secp256k1, where u', 3265 v', and w' are the polynomials with coefficients in GF(p) as defined 3266 in Appendix M.4.2, while mapping the point at infinity O of 3267 secp256k1.m to the point at infinity O of secp256k1. Under this dual 3268 isogenous mapping, the base point (GmX, GmY) of secp256k1.m 3269 corresponds to a multiple of the base point (GX, GY) of secp256k1, 3270 where this multiple is l=3 (the degree of the isogeny; see the 3271 description in Appendix F.4). Note that this isogenous map (and its 3272 dual) primarily involves the evaluation of three fixed polynomials 3273 involving the x-coordinate, which takes roughly 10 modular 3274 multiplications (or less than 1% relative incremental cost compared 3275 to the cost of an elliptic curve scalar multiplication). 3277 M.3. Domain Parameters 3279 The parameters of the curve sec256k1 and the corresponding 3280 3-isogenous curve sec256k1.m are as indicated below. Here, the 3281 domain parameters of the curve secp256k1 are as specified in [SEC2]; 3282 the domain parameters of secp256k1.m are "new". 3284 General parameters (for all curves): 3286 p 2^256-2^32-2^9-2^8-2^7-2^6-2^4-1 3288 (=0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 3289 fffffffe fffffc2f) 3291 h 1 3292 n 11579208923731619542357098500868790785283756427907490438260516314 3293 1518161494337 3295 (=0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b 3296 bfd25e8c d0364141) 3298 h1 23479460174521 (=0x1a 9bfcab89) 3300 n1 10131766773001318469008702396060356387381009972480920692566974370 3301 31 3303 (=0x099ee564 ea5d84f5 08913936 a761b0d5 d792a426 a7779817 3304 ae2f5b67) 3306 Weierstrass curve-specific parameters (for secp256k1): 3308 a 0 (=0x00) 3310 b 7 (=0x07) 3312 GX 55066263022277343669578718895168534326250603453777594175500187360 3313 389116729240 3315 (=0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 3316 59f2815b 16f81798) 3318 GY 32670510020758816978083085130507043184471273380659243275938904335 3319 757337482424 3321 (=0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 3322 9c47d08f fb10d4b8) 3324 Weierstrass curve-specific parameters (for secp256k1.m): 3326 a 93991599167772749909245591943117186381494883464374162770646538702 3327 960816911535 3329 (=0xcfcd5c21 75e2ef7d ccdce737 770b7381 5a2f13c5 09035ca2 3330 54a14ac9 f08974af) 3332 b 1771 (=0x06eb) 3334 GmX 26591621185618668069038227574782692264471832498547635565821216767 3335 730887659845 3337 (=0x3aca5300 959fa1d0 baf78dcf f77a616f 395e586d 67aced0a 3338 88798129 0c279145) 3340 GmY 67622516283223102233819216063319565850973524550533340939716651159 3341 860372686848 3343 (=0x9580fce5 3a170f4f b744579f f3d62086 12cd6a23 3e2de237 3344 f976c6a7 8611c800) 3346 M.4. Isogeny Details 3348 The isogeny and dual isogeny are both isogenies with degree l=3. 3349 Both are specified by a triple of polynomials u, v, and w (resp. u', 3350 v', and w') of degree 3, 3, and 1, respectively, with coefficients in 3351 GF(p). The coeffients of each of these polynomials are specified in 3352 Appendix M.4.1 (for the isogeny) and in Appendix M.4.2 (for the dual 3353 isogeny). For each polynomial in variable x, the coefficients are 3354 tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in 3355 hexadecimal format. 3357 M.4.1. Isogeny Parameters 3359 M.4.1.1. Coefficients of u(x) 3361 0 0x54 3363 1 0xa4d89db3ed06c81e6143ec2eca9f761d8d17260dc229e1da1f73f714506872a9 3365 2 0xcc58ffccbd9febb4a66222c7d1311d988d88c0624bcd68ec4c758a8e67dfd99b 3367 3 0x01 3369 M.4.1.2. Coefficients of v(x) 3371 0 0x1c 3373 1 0x94c7bc69befd17f2fae2e3ebf24df1f355d181fa1a8056103ba9baad4b40f029 3375 2 0xb2857fb31c6fe18ef993342bb9c9ac64d44d209371b41d6272b04fd61bcfc851 3377 3 0x01 3379 M.4.1.3. Coefficients of w(x) 3381 0 0xe62c7fe65ecff5da53311163e8988ecc46c4603125e6b476263ac546b3efeae5 3383 1 0x01 3385 M.4.2. Dual Isogeny Parameters 3387 M.4.2.1. Coefficients of u'(x) 3389 0 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa8c7 3391 1 0x44cd5cd7ce55a801725891578fbe7356bd936355fd0e2f538797cecff7a37244 3393 2 0x668d0011162006c3c889f4680f9a4b77d0d26a89e6bb87b13bd8d1cfdd600a41 3395 3 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c 3397 M.4.2.2. Coefficients of v'(x) 3399 0 0x4bda12f684bda12f684bda12f684bda12f684bda12f684bda12f684b8e38e23c 3401 1 0x519ba9c1f48f68054def6a410f0fa6e8b71c6c3b4a8958324681f6508c01fada 3403 2 0xb34680088b100361e444fa3407cd25bbe8693544f35dc3d89dec68e76eb00338 3405 3 0x2f684bda12f684bda12f684bda12f684bda12f684bda12f684bda12f38e38d84 3407 M.4.2.3. Coefficients of w'(x) 3409 0 0x4d7a804ce3901e71066ccbd44636539b2bb2df6c8e4be29d8d4fb028e43033de 3411 1 0x01 3413 Author's Address 3415 Rene Struik 3416 Struik Security Consultancy 3418 Email: rstruik.ext@gmail.com