idnits 2.17.1 draft-sullivan-hash-to-curve-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 05, 2018) is 2243 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'A' is mentioned on line 660, but not defined == Missing Reference: 'B' is mentioned on line 591, but not defined -- Looks like a reference, but probably isn't: '0' on line 660 -- Looks like a reference, but probably isn't: '1' on line 660 == Unused Reference: 'ECOPRF' is defined on line 440, but no explicit reference was found in the text == Unused Reference: 'SECG1' is defined on line 478, but no explicit reference was found in the text Summary: 0 errors (**), 0 flaws (~~), 5 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group N. Sullivan 3 Internet-Draft Cloudflare 4 Intended status: Informational C. Wood 5 Expires: September 6, 2018 Apple Inc. 6 March 05, 2018 8 Hashing to Elliptic Curves 9 draft-sullivan-hash-to-curve-00 11 Abstract 13 This document specifies a number of algorithms that may be used to 14 hash arbitrary strings to Elliptic Curves. 16 Status of This Memo 18 This Internet-Draft is submitted in full conformance with the 19 provisions of BCP 78 and BCP 79. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF). Note that other groups may also distribute 23 working documents as Internet-Drafts. The list of current Internet- 24 Drafts is at http://datatracker.ietf.org/drafts/current/. 26 Internet-Drafts are draft documents valid for a maximum of six months 27 and may be updated, replaced, or obsoleted by other documents at any 28 time. It is inappropriate to use Internet-Drafts as reference 29 material or to cite them other than as "work in progress." 31 This Internet-Draft will expire on September 6, 2018. 33 Copyright Notice 35 Copyright (c) 2018 IETF Trust and the persons identified as the 36 document authors. All rights reserved. 38 This document is subject to BCP 78 and the IETF Trust's Legal 39 Provisions Relating to IETF Documents 40 (http://trustee.ietf.org/license-info) in effect on the date of 41 publication of this document. Please review these documents 42 carefully, as they describe your rights and restrictions with respect 43 to this document. Code Components extracted from this document must 44 include Simplified BSD License text as described in Section 4.e of 45 the Trust Legal Provisions and are provided without warranty as 46 described in the Simplified BSD License. 48 Table of Contents 50 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 51 1.1. Requirements . . . . . . . . . . . . . . . . . . . . . . 3 52 2. Algorithm Recommendations . . . . . . . . . . . . . . . . . . 3 53 3. Generic Interface . . . . . . . . . . . . . . . . . . . . . . 4 54 3.1. Utility Functions . . . . . . . . . . . . . . . . . . . . 4 55 4. Hashing Variants . . . . . . . . . . . . . . . . . . . . . . 5 56 4.1. Icart Method . . . . . . . . . . . . . . . . . . . . . . 5 57 4.2. Shallue-Woestijne-Ulas Method . . . . . . . . . . . . . . 6 58 4.3. Simplified SWU Method . . . . . . . . . . . . . . . . . . 6 59 4.4. Elligator2 Method . . . . . . . . . . . . . . . . . . . . 8 60 5. Curve Transformations . . . . . . . . . . . . . . . . . . . . 10 61 6. Cost Comparison . . . . . . . . . . . . . . . . . . . . . . . 10 62 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 63 8. Security Considerations . . . . . . . . . . . . . . . . . . . 11 64 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11 65 10. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 11 66 11. Normative References . . . . . . . . . . . . . . . . . . . . 11 67 Appendix A. Try-and-Increment Method . . . . . . . . . . . . . . 13 68 Appendix B. Sample Code . . . . . . . . . . . . . . . . . . . . 13 69 B.1. Icart Method . . . . . . . . . . . . . . . . . . . . . . 13 70 B.2. Shallue-Woestijne-Ulas Method . . . . . . . . . . . . . . 14 71 B.3. Simplified SWU Method . . . . . . . . . . . . . . . . . . 15 72 B.4. Elligator2 Method . . . . . . . . . . . . . . . . . . . . 16 73 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 17 75 1. Introduction 77 Many cryptographic protocols require a procedure which maps arbitrary 78 input, e.g., passwords, to points on an elliptic curve (EC). 79 Prominent examples include Simple Password Exponential Key Exchange 80 [Jablon96], Password Authenticated Key Exchange [BMP00], and Boneh- 81 Lynn-Shacham signatures [BLS01]. 83 Let E be an elliptic curve over base field GF(p). In practice, 84 efficient (polynomial-time) functions that hash arbitrary input to E 85 can be constructed by composing a cryptographically secure hash 86 function F1 : {0,1}^* ->GF(p) and an injection F2 : GF(p) -> E, i.e., 87 Hash(m) = F2(F1(m)). Probabilistic constructions of Hash, e.g., the 88 MapToGroup function described by Boneh et al. [BLS01]. Their 89 algorithm fails with probability 2^I, where I is a tunable parameter 90 that one can control. Another variant, dubbed the "Try and 91 Increment" approach, was described by Boneh et al. [BLS01]. This 92 function works by hashing input m using a standard hash function, 93 e.g., SHA256, and then checking to see if the resulting point E(m, 94 f(m)), for curve function f, belongs on E. This algorithm is 95 expected to find a valid curve point after approximately two 96 attempts, i.e., when ctr=1, on average. (See Appendix Appendix A for 97 a more detailed description of this algorithm.) Since the running 98 time of the algorithm depends on m, this algorithm is NOT safe for 99 cases sensitive to timing side channel attacks. Deterministic 100 algorithms are needed in such cases where failures are undesirable. 101 Shallue and Woestijne [SWU] first introduced a deterministic 102 algorithm that maps elements in F_{q} to an EC in time O(log^4 q), 103 where q = p^n for some prime p, and time O(log^3 q) when q = 3 mod 4. 104 Icart introduced yet another deterministic algorithm which maps F_{q} 105 to any EC where q = 2 mod 3 in time O(log^3 q) [Icart09]. Elligator 106 (2) [Elligator2] is yet another deterministic algorithm for any odd- 107 characteristic EC that has a point of order 2. Elligator2 can be 108 applied to Curve25519 and Curve448, which are both CFRG-recommended 109 curves [RFC7748]. 111 This document specifies several algorithms for deterministically 112 hashing onto a curve with varying properties: Icart, SWU, Simplified 113 SWU, and Elligator2. Each algorithm conforms to a common interface, 114 i.e., it maps an element from a base field F to a curve E. For each 115 variant, we describe the requirements for F and E to make it work. 116 Sample code for each variant is presented in the appendix. Unless 117 otherwise stated, all elliptic curve points are assumed to be 118 represented as affine coordinates, i.e., (x, y) points on a curve. 120 1.1. Requirements 122 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 123 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 124 document are to be interpreted as described in [RFC2119]. 126 2. Algorithm Recommendations 128 The following table lists recommended algorithms to use for specific 129 curves. 131 +------------+------------------------+ 132 | Curve | Algorithm | 133 +------------+------------------------+ 134 | P-256 | SWU Section 4.3 | 135 | | | 136 | P-384 | Icart Section 4.1 | 137 | | | 138 | Curve25519 | Elligator2 Section 4.4 | 139 | | | 140 | Curve448 | Elligator2 Section 4.4 | 141 +------------+------------------------+ 143 The SWU variant from Section Section 4.2 applies to any curve. As 144 such, this algorithm SHOULD be used if no other better alternative is 145 known. More efficient variants and their curve requirements are 146 shown in the table below. These MAY be used if the target curve 147 meets the listed criteria. 149 +--------------------+----------------------------------------------+ 150 | Algorithm | Requirement | 151 +--------------------+----------------------------------------------+ 152 | Icart Section 4.1 | p = 2 mod 3 | 153 | | | 154 | SWU Section 4.2 | None | 155 | | | 156 | Simplified SWU | p = 3 mod 4 | 157 | Section 4.3 | | 158 | | | 159 | Elligator2 Section | p is large and there is a point of order two | 160 | 4.4 | and j-invariant != 1728 | 161 +--------------------+----------------------------------------------+ 163 3. Generic Interface 165 The generic interface for hashing to elliptic curves is as follows: 167 hash_to_curve(alpha) 169 where alpha is a message to hash onto a curve. 171 3.1. Utility Functions 173 Algorithms in this document make use of utility functions described 174 below. 176 o HashToBase(x): H(x)[0:log2(p) + 1], i.e., hash-truncate-reduce, 177 where H is a cryptographic hash function, such as SHA256, and p is 178 the prime order of base field Fp. 180 o CMOV(a, b, c): If c = 1, return a, else return b. 182 Note: We assume that HashToBase maps its input to the base field 183 uniformly. In practice, there may be inherent biases in p, e.g., p = 184 2^k - 1 will have non-negligible bias in higher bits. 186 ((TODO: expand on this problem)) 188 4. Hashing Variants 190 4.1. Icart Method 192 The following hash_to_curve_icart(alpha) implements the Icart method 193 from [Icart09]. This algorithm works for any curve over F_{p^n}, 194 where p^n = 2 mod 3 (or p = 2 mod 3 and for odd n), including: 196 o P384 198 o Curve1174 200 o Curve448 202 Unsupported curves include: P224, P256, P521, and Curve25519 since, 203 for each, p = 1 mod 3. 205 Mathematically, given input alpha, and A and B from E, the Icart 206 method works as follows: 208 u = HashToBase(alpha) 209 x = (v^2 - b - (u^6 / 27))^(1/3) + (u^2 / 3) 210 y = ux + v 212 where v = ((3A - u^4) / 6u). 214 The following procedure implements this algorithm in a straight-line 215 fashion. It requires knowledge of A and B, the constants from the 216 curve Weierstrass form. It outputs a point with affine coordinates. 218 hash_to_curve_icart(alpha) 220 Input: 222 alpha - value to be hashed, an octet string 224 Output: 226 (x, y) - a point in E 228 Steps: 230 1. u = HashToBase(alpha) // {0,1}^* -> Fp 231 2. u2 = u^2 (mod p) // u^2 232 3. t2 = u2^2 (mod p) // u^4 233 4. v1 = 3 * A (mod p) // 3A 234 5. v1 = v1 - t2 (mod p) // 3A - u^4 235 6. t1 = 6 * u (mod p) // 6u 236 7. t3 = t1 ^ (-1) (mod p) // modular inverse 237 8. v = v1 * t3 (mod p) // (3A - u^4)/(6u) 238 9. x = v^2 (mod p) // v^2 239 10. x = x - B (mod p) // v^2 - b 240 11. t1 = 27 ^ (-1) (mod p) // 1/27 241 12. t1 = t1 * u2 (mod p) // u^4 / 27 242 13. t1 = t1 * t2 (mod p) // u^6 / 27 243 14. x = x - t1 (mod p) // v^2 - b - u^6/27 244 15. t1 = (2 * p) - 1 (mod p) // 2p - 1 245 16. t1 = t1 / 3 (mod p) // (2p - 1)/3 246 17. x = x^t1 (mod p) // (v^2 - b - u^6/27) ^ (1/3) 247 18. t2 = u2 / 3 (mod p) // u^2 / 3 248 19. x = x + t2 (mod p) // (v^2 - b - u^6/27) ^ (1/3) + (u^2 / 3) 249 20. y = u * x (mod p) // ux 250 21. y = y + v (mod p) // ux + v 251 22. Output (x, y) 253 4.2. Shallue-Woestijne-Ulas Method 255 ((TODO: write this section)) 257 4.3. Simplified SWU Method 259 The following hash_to_curve_simple_swu(alpha) implements the 260 simplfied Shallue-Woestijne-Ulas algorithm from [SimpleSWU]. This 261 algorithm works for any curve over F_{p^n}, where p = 3 mod 4, 262 including: 264 o P256 265 o ... 267 Given curve equation g(x) = x^3 + Ax + B, this algorithm works as 268 follows: 270 1. t = HashToBase(alpha) 271 2. alpha = (-b / a) * (1 + (1 / (t^4 + t^2))) 272 3. beta = -t^2 * alpha 273 4. z = t^3 * g(alpha) 274 5. Output (-g * alpha) * (g * beta) 276 The following procedure implements this algorithm. It outputs a 277 point with affine coordinates. 279 hash_to_curve_simple_swu(alpha) 281 Input: 283 alpha - value to be hashed, an octet string 285 Output: 287 (x, y) - a point in E 289 Steps: 291 1. t = HashToBase(alpha) 292 2. alpha = t^2 (mod p) 293 3. alpha = alpha * -1 (mod p) 294 4. right = alpha^2 + alpha (mod p) 295 5. right = right^(-1) (mod p) 296 6. right = right + 1 (mod p) 297 7. left = B * -1 (mod p) 298 8. left = left / A (mod p) 299 9. x2 = left * right (mod p) 300 10. x3 = alpha * x2 (mod p) 301 11. h2 = x2 ^ 3 (mod p) 302 12. i2 = x2 * A (mod p) 303 13. i2 = i2 + B (mod p) 304 14. h2 = h2 + i2 (mod p) 305 15. h3 = x3 ^ 3 (mod p) 306 16. i3 = x3 * A (mod p) 307 17. i3 = i3 + B (mod p) 308 18. h3 = h3 + i3 (mod p) 309 19. y1 = h2 ^ ((p + 1) // 4) (mod p) 310 20. y2 = h3 ^ ((p + 1) // 4) (mod p) 311 21. e = (y1 ^ 2 == h2) 312 22. x = CMOV(x2, x3, e) // If e = 1, choose x2, else choose x3 313 23. y = CMOV(y1, y2, e) // If e = 1, choose y1, else choose y2 314 24. Output (x, y) 316 4.4. Elligator2 Method 318 The following hash_to_curve_elligator2(alpha) implements the 319 Elligator2 method from [Elligator2]. This algorithm works for any 320 curve with a point of order 2 and j-invariant != 1728. Given curve 321 equation f(x) = y^2 = x(x^2 + Ax + B), i.e., a Montgomery form with 322 the point of order 2 at (0,0), this algorithm works as shown below. 323 (Note that any curve with a point of order 2 is isomorphic to this 324 representation.) 325 1. r = HashToBase(alpha) 326 2. If f(-A/(1+ur^2)) is square, then output f(-A/(1+ur^2))^(1/2) 327 3. Else, output f(-Aur^2/(1+ur^2))^(1/2) 329 Another way to express this algorithm is as follows: 331 1. r = HashToBase(alpha) 332 2. d = -A / (1 + ur^2) 333 3. e = f(d)^((p-1)/2) 334 4. u = ed - (1 - e)A/u 336 Here, e is the Legendre symbol of y = (d^3 + Ad^2 + d), which will be 337 1 if y is a quadratic residue (square) mod p, and -1 otherwise. 338 (Note that raising y to ((p -1) / 2) is a common way to compute the 339 Legendre symbol.) 341 The following procedure implements this algorithm. 343 hash_to_curve_elligator2(alpha) 345 Input: 347 alpha - value to be hashed, an octet string 349 u - fixed non-square value in Fp. 350 f() - Curve function 352 Output: 354 (x, y) - a point in E 356 Steps: 358 1. r = HashToBase(alpha) 359 2. r = r^2 (mod p) 360 3. nu = r * u (mod p) 361 4. r = nu 362 5. r = r + 1 (mod p) 363 6. r = r^(-1) (mod p) 364 7. v = A * r (mod p) 365 8. v = v * -1 (mod p) // -A / (1 + ur^2) 366 9. v2 = v^2 (mod p) 367 10. v3 = v * v2 (mod p) 368 11. e = v3 * v (mod p) 369 12. v2 = v2 * A (mod p) 370 13. e = v2 * e (mod p) 371 14. e = e^((p - 1) / 2) // Legendre symbol 372 15. nv = v * -1 (mod p) 373 16. v = CMOV(v, nv, e) // If e = 1, choose v, else choose nv 374 17. v2 = CMOV(0, A, e) // If e = 1, choose 0, else choose A 375 18. u = v - v2 (mod p) 376 19. Output (u, f(u)) 378 Elligator2 can be simplified with projective coordinates. 380 ((TODO: write this variant)) 382 5. Curve Transformations 384 ((TODO: write this section)) 386 6. Cost Comparison 388 The following table summarizes the cost of each hash_to_curve 389 variant. We express this cost in terms of additions (A), 390 multiplications (M), squares (SQ), and square roots (SR). 392 ((TODO: finish this section)) 394 +--------------------------+-------------------+ 395 | Algorithm | Cost (Operations) | 396 +--------------------------+-------------------+ 397 | hash_to_curve_icart | TODO | 398 | | | 399 | hash_to_curve_swu | TODO | 400 | | | 401 | hash_to_curve_simple_swu | TODO | 402 | | | 403 | hash_to_curve_elligator2 | TODO | 404 +--------------------------+-------------------+ 406 7. IANA Considerations 408 This document has no IANA actions. 410 8. Security Considerations 412 Each hash function variant accepts arbitrary input and maps it to a 413 pseudorandom point on the curve. Points are close to 414 indistinguishable from randomly chosen elements on the curve. Some 415 variants variants are not full-domain hashes. Elligator2, for 416 example, only maps strings to "about half of all curve points," 417 whereas Icart's method only covers about 5/8 of the points. 419 9. Acknowledgements 421 The authors would like to thank Adam Langley for this detailed 422 writeup up Elligator2 with Curve25519 [ElligatorAGL]. We also thank 423 Sean Devlin and Thomas Icart for feedback on earlier versions of this 424 document. 426 10. Contributors 428 o Sharon Goldberg 429 Boston University 430 goldbe@cs.bu.edu 432 11. Normative References 434 [BLS01] "Short signatures from the Weil pairing", n.d., 435 . 437 [BMP00] "Provably secure password-authenticated key exchange using 438 diffie-hellman", n.d.. 440 [ECOPRF] "EC-OPRF - Oblivious Pseudorandom Functions using Elliptic 441 Curves", n.d.. 443 [Elligator2] 444 "Elligator -- Elliptic-curve points indistinguishable from 445 uniform random strings", n.d., . 448 [ElligatorAGL] 449 "Implementing Elligator for Curve25519", n.d., 450 . 453 [Icart09] "How to Hash into Elliptic Curves", n.d., 454 . 456 [Jablon96] 457 "Strong password-only authenticated key exchange", n.d.. 459 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 460 Requirement Levels", BCP 14, RFC 2119, 461 DOI 10.17487/RFC2119, March 1997, . 464 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 465 for Security", RFC 7748, DOI 10.17487/RFC7748, January 466 2016, . 468 [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, 469 "PKCS #1: RSA Cryptography Specifications Version 2.2", 470 RFC 8017, DOI 10.17487/RFC8017, November 2016, 471 . 473 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 474 Signature Algorithm (EdDSA)", RFC 8032, 475 DOI 10.17487/RFC8032, January 2017, . 478 [SECG1] "SEC 1 -- Elliptic Curve Cryptography", n.d., 479 . 481 [SimpleSWU] 482 "Efficient Indifferentiable Hashing into Ordinary Elliptic 483 Curves", n.d.. 485 [SWU] "Rational points on certain hyperelliptic curves over 486 finite fields", n.d., . 488 Appendix A. Try-and-Increment Method 490 In cases where constant time execution is not required, the so-called 491 try-and-increment method may be appropriate. As discussion in 492 Section Section 1, this variant works by hashing input m using a 493 standard hash function ("Hash"), e.g., SHA256, and then checking to 494 see if the resulting point E(m, f(m)), for curve function f, belongs 495 on E. This is detailed below. 497 1. ctr = 0 498 3. h = "INVALID" 499 4. While h is "INVALID" or h is EC point at infinity: 500 A. CTR = I2OSP(ctr, 4) 501 B. ctr = ctr + 1 502 C. attempted_hash = Hash(m || CTR) 503 D. h = RS2ECP(attempted_hash) 504 E. If h is not "INVALID" and cofactor > 1, set h = h^cofactor 505 5. Output h 507 I2OSP is a function that converts a nonnegative integer to octet 508 string as defined in Section 4.1 of [RFC8017], and RS2ECP is a 509 function that converts of a random 2n-octet string to an EC point as 510 specified in Section 5.1.3 of [RFC8032]. 512 Appendix B. Sample Code 514 B.1. Icart Method 516 The following Sage program implements hash_to_curve_icart(alpha) for 517 P-384. 519 p = 394020061963944792122790401001436138050797392704654466679482934042 \ 520 45721771496870329047266088258938001861606973112319 521 F = GF(p) 522 A = p - 3 523 B = 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875a \ 524 c656398d8a2ed19d2a85c8edd3ec2aef 525 q = 394020061963944792122790401001436138050797392704654466679469052796 \ 526 27659399113263569398956308152294913554433653942643 527 E = EllipticCurve([F(A), F(B)]) 528 g = E(0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a \ 529 385502f25dbf55296c3a545e3872760ab7, \ 530 0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c0 \ 531 0a60b1ce1d7e819d7a431d7c90ea0e5f) 532 E.set_order(q) 534 def icart(u): 535 u = F(u) 536 v = (3*A - u^4)//(6*u) 537 x = (v^2 - B - u^6/27)^((2*p-1)//3) + u^2/3 538 y = u*x + v 539 return E(x, y) 541 def icart_straight(u): 542 u = F(u) 543 u2 = u ^ 2 544 t2 = u2 ^ 2 545 assert t2 == u^4 547 v1 = 3 * A 548 v1 = v1 - t2 549 t1 = 6 * u 550 t3 = t1 ^ (-1) 551 v = v1 * t3 552 assert v == (3 * A - u^4) // (6 * u) 554 x = v ^ 2 555 x = x - B 556 assert x == (v^2 - B) 558 t1 = F(27) ^ (-1) 559 t1 = t1 * u2 560 t1 = t1 * t2 561 assert t1 == ((u^6) / 27) 563 x = x - t1 564 t1 = (2 * p) - 1 565 t1 = t1 / 3 566 assert t1 == ((2*p) - 1) / 3 568 x = x ^ t1 570 t2 = u2 / 3 571 x = x + t2 572 y = u * x 573 y = y + v 574 return E(x, y) 576 B.2. Shallue-Woestijne-Ulas Method 578 ((TODO: write this section)) 580 B.3. Simplified SWU Method 582 The following Sage program implements hash_to_curve_swu(alpha) for 583 P-256. 585 p = 115792089210356248762697446949407573530086143415290314195533631308 \ 586 867097853951 587 F = GF(p) 588 A = F(p - 3) 589 B = F(ZZ("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2 \ 590 604b", 16)) 591 E = EllipticCurve([A, B]) 593 def simple_swu(alpha): 594 t = F(alpha) 596 alpha = -(t^2) 597 frac = (1 / (alpha^2 + alpha)) 598 x2 = (-B / A) * (1 + frac) 600 x3 = alpha * x2 601 h2 = x2^3 + A * x2 + B 602 h3 = x3^3 + A * x3 + B 604 if is_square(h2): 605 return E(x2, h2^((p + 1) // 4)) 606 else: 607 return E(x3, h3^((p + 1) // 4)) 609 def simple_swu_straight(alpha): 610 t = F(alpha) 612 alpha = t^2 613 alpha = alpha * -1 615 right = alpha^2 + alpha 616 right = right^(-1) 617 right = right + 1 619 left = B * -1 620 left = left / A 622 x2 = left * right 623 x3 = alpha * x2 625 h2 = x2 ^ 3 626 i2 = x2 * A 627 i2 = i2 + B 628 h2 = h2 + i2 630 h3 = x3 ^ 3 631 i3 = x3 * A 632 i3 = i3 + B 633 h3 = h3 + i3 635 y1 = h2^((p + 1) // 4) 636 y2 = h3^((p + 1) // 4) 638 # Is it square? 639 e = y1^2 == h2 641 x = x2 642 if e != 1: 643 x = x3 645 y = y1 646 if e != 1: 647 y = y2 649 return E(x, y) 651 B.4. Elligator2 Method 653 The following Sage program implements hash_to_curve_elligator2(alpha) 654 for Curve25519. 656 p = 2**255 - 19 657 F = GF(p) 658 A = 486662 659 B = 1 660 E = EllipticCurve(F, [0, A, 0, 1, 0]) 662 def curve25519(x): 663 return x^3 + (A * x^2) + x 665 def elligator2(alpha): 667 r = F(alpha) 669 # u is a fixed nonsquare value, eg -1 if p==3 mod 4. 670 u = F(2) # F(2) 671 assert(not u.is_square()) 673 # If f(-A/(1+ur^2)) is square, return its square root. 674 # Else, return the square root of f(-Aur^2/(1+ur^2)). 675 x = -A / (1 + (u * r^2)) 676 y = curve25519(x) 677 if y.is_square(): # is this point square? 678 y = y.square_root() 679 else: 680 x = (-A * u * r^2) / (1 + (u * r^2)) 681 y = curve25519(x).square_root() 683 return (x, curve25519(x)) 685 def elligator2_straight(alpha): 686 r = F(alpha) 688 r = r^2 689 r = r * 2 690 r = r + 1 691 r = r^(-1) 692 v = A * r 693 v = v * -1 # d 695 v2 = v^2 696 v3 = v * v2 697 e = v3 + v 698 v2 = v2 * A 699 e = v2 + e 701 # Legendre symbol 702 e = e^((p - 1) / 2) 704 nv = v * -1 705 if e != 1: 706 v = nv 708 v2 = 0 709 if e != 1: 710 v2 = A 712 u = v - v2 714 return (u, curve25519(u)) 716 Authors' Addresses 717 Nick Sullivan 718 Cloudflare 719 101 Townsend St 720 San Francisco 721 United States of America 723 Email: nick@cloudflare.com 725 Christopher A. Wood 726 Apple Inc. 727 One Apple Park Way 728 Cupertino, California 95014 729 United States of America 731 Email: cawood@apple.com