idnits 2.17.1 draft-irtf-cfrg-hash-to-curve-01.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 : ---------------------------------------------------------------------------- ** There are 7 instances of too long lines in the document, the longest one being 61 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (July 02, 2018) is 2124 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'ECOPRF' is defined on line 676, but no explicit reference was found in the text == Unused Reference: 'SECG1' is defined on line 720, but no explicit reference was found in the text Summary: 1 error (**), 0 flaws (~~), 4 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group S. Scott 3 Internet-Draft Cornell Tech 4 Intended status: Informational N. Sullivan 5 Expires: January 3, 2019 Cloudflare 6 C. Wood 7 Apple Inc. 8 July 02, 2018 10 Hashing to Elliptic Curves 11 draft-irtf-cfrg-hash-to-curve-01 13 Abstract 15 This document specifies a number of algorithms that may be used to 16 hash arbitrary strings to Elliptic Curves. 18 Status of This Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at http://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on January 3, 2019. 35 Copyright Notice 37 Copyright (c) 2018 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (http://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 Table of Contents 52 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 53 1.1. Requirements . . . . . . . . . . . . . . . . . . . . . . 3 54 2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 3 55 2.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 56 2.1.1. Encoding . . . . . . . . . . . . . . . . . . . . . . 5 57 2.1.2. Serialization . . . . . . . . . . . . . . . . . . . . 5 58 2.1.3. Random Oracle . . . . . . . . . . . . . . . . . . . . 5 59 3. Algorithm Recommendations . . . . . . . . . . . . . . . . . . 6 60 4. Utility Functions . . . . . . . . . . . . . . . . . . . . . . 7 61 5. Deterministic Encodings . . . . . . . . . . . . . . . . . . . 7 62 5.1. Interface . . . . . . . . . . . . . . . . . . . . . . . . 7 63 5.2. Encoding Variants . . . . . . . . . . . . . . . . . . . . 7 64 5.2.1. Icart Method . . . . . . . . . . . . . . . . . . . . 7 65 5.2.2. Shallue-Woestijne-Ulas Method . . . . . . . . . . . . 9 66 5.2.3. Simplified SWU Method . . . . . . . . . . . . . . . . 10 67 5.2.4. Elligator2 Method . . . . . . . . . . . . . . . . . . 12 68 5.3. Cost Comparison . . . . . . . . . . . . . . . . . . . . . 13 69 6. Random Oracles . . . . . . . . . . . . . . . . . . . . . . . 14 70 6.1. Interface . . . . . . . . . . . . . . . . . . . . . . . . 14 71 6.2. General Construction (FFSTV13) . . . . . . . . . . . . . 14 72 7. Curve Transformations . . . . . . . . . . . . . . . . . . . . 14 73 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 74 9. Security Considerations . . . . . . . . . . . . . . . . . . . 15 75 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 15 76 11. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 15 77 12. Normative References . . . . . . . . . . . . . . . . . . . . 15 78 Appendix A. Related Work . . . . . . . . . . . . . . . . . . . . 17 79 A.1. Probabilistic Encoding . . . . . . . . . . . . . . . . . 17 80 A.2. Naive Encoding . . . . . . . . . . . . . . . . . . . . . 17 81 A.3. Deterministic Encoding . . . . . . . . . . . . . . . . . 18 82 A.4. Supersingular Curves . . . . . . . . . . . . . . . . . . 18 83 A.5. Twisted Variants . . . . . . . . . . . . . . . . . . . . 18 84 Appendix B. Try-and-Increment Method . . . . . . . . . . . . . . 19 85 Appendix C. Sample Code . . . . . . . . . . . . . . . . . . . . 19 86 C.1. Icart Method . . . . . . . . . . . . . . . . . . . . . . 19 87 C.2. Shallue-Woestijne-Ulas Method . . . . . . . . . . . . . . 21 88 C.3. Simplified SWU Method . . . . . . . . . . . . . . . . . . 23 89 C.4. Elligator2 Method . . . . . . . . . . . . . . . . . . . . 23 90 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 24 92 1. Introduction 94 Many cryptographic protocols require a procedure which maps arbitrary 95 input, e.g., passwords, to points on an elliptic curve (EC). 96 Prominent examples include Simple Password Exponential Key Exchange 98 [Jablon96], Password Authenticated Key Exchange [BMP00], Identity- 99 Based Encryption [BF01] and Boneh-Lynn-Shacham signatures [BLS01]. 101 Unfortunately for implementors, the precise mapping which is suitable 102 for a given scheme is not necessarily included in the description of 103 the protocol. Compounding this problem is the need to pick a 104 suitable curve for the specific protocol. 106 This document aims to address this lapse by providing a thorough set 107 of recommendations across a range of implementations, and curve 108 types. We provide implementation and performance details for each 109 mechanism, along with references to the security rationale behind 110 each recommendation and guidance for applications not yet covered. 112 Each algorithm conforms to a common interface, i.e., it maps an 113 element from a bitstring {0, 1}^* to a curve E. For each variant, we 114 describe the requirements for E to make it work. Sample code for 115 each variant is presented in the appendix. Unless otherwise stated, 116 all elliptic curve points are assumed to be represented as affine 117 coordinates, i.e., (x, y) points on a curve. 119 1.1. Requirements 121 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 122 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 123 document are to be interpreted as described in [RFC2119]. 125 2. Background 127 Here we give a brief definition of elliptic curves, with an emphasis 128 on defining important parameters and their relation to encoding. 130 Let F be the finite field GF(p^k). We say that F is a field of 131 characteristic p. For most applications, F is a prime field, in 132 which case k=1 and we will simply write GF(p). 134 Elliptic curves come in many variants, including, but not limited to: 135 Weierstrass, Montgomery, and Edwards. Each of these variants 136 correspond to a different category of curve equation. For example, 137 the short Weierstrauss equation is of the form "y^2 = x^3 + Ax + B". 138 Certain encoding functions may have requirements on the curve form 139 and the parameters, such as A and B in the previous example. 141 An elliptic curve E is specified by the equation, and a finite field 142 F. The curve E forms a group, whose elements correspond to those who 143 satisfy the curve equation, with values taken from the field F. As a 144 group, E has order n, which is the number of points on the curve. 145 When n is not prime, we write n = qh + r, where q is prime, and h is 146 said to be the cofactor. It is frequently a requirement that all 147 cryptographic operations take place in a prime order group. In this 148 case, we may wish an encoding to return elements of order q. For a 149 mapping outputting elements on E, we can multiply by the cofactor h 150 to obtain an element in the subgroup. 152 In practice, the input of a given cryptographic algorithm will be a 153 bitstring of arbitrary length, denoted {0, 1}^*. Hence, a concern for 154 virtually all protocols involving elliptic curves is how to convert 155 this input into a curve point. 157 Note that the number of points on an elliptic curve E is within 158 2*sqrt(p) of p by Hasse's Theorem. As a rule of thumb, for every x 159 in GF(p), there is approximately a 1/2 chance that there exist a 160 corresponding y value such that (x, y) is on the curve E. Since the 161 point (x, -y) is also on the curve, then this sums to approximately p 162 points. 164 Ultimately, an encoding function takes a bitstring {0, 1}^* to an 165 element of E, of order n (or q), and represented by variables in 166 GF(p). 168 Summary of quantities: 170 +--------+-------------------+--------------------------------------+ 171 | Symbol | Meaning | Relevance | 172 +--------+-------------------+--------------------------------------+ 173 | p | Order of finite | Curve points need to be represented | 174 | | field, F = GF(p) | in terms of p. For prime powers, we | 175 | | | write F = GF(p^k). | 176 | | | | 177 | n | Number of curve | For map to E, needs to produce n | 178 | | points, #E(F) = n | elements. | 179 | | | | 180 | q | Order of prime | If n is not prime, may need mapping | 181 | | subgroup of E, n | to q. | 182 | | = qh + r | | 183 | | | | 184 | h | Cofactor of prime | For mapping to subgroup, need to | 185 | | subgroup | multiply by cofactor. | 186 +--------+-------------------+--------------------------------------+ 188 2.1. Terminology 190 In the following, we categorize the terminology for mapping between 191 bitstrings and elliptic curves. 193 2.1.1. Encoding 195 The general term "encoding" is used to refer to the process of 196 producing an elliptic curve point given as input a bitstring. In 197 some protocols, the original message may also be recovered through a 198 decoding procedure. An encoding may be deterministic or 199 probabilistic, although the latter is problematic in potentially 200 leaking plaintext information as a side-channel. 202 In most cases, the curve E is over a finite field GF(p^k), with p > 203 2. Suppose as the input to the encoding function we wish to use a 204 fixed-length bitstring of length L. Comparing sizes of the sets, 2^L 205 and n, an encoding function cannot be both deterministic and 206 bijective. 208 We can instead use an injective encoding from {0, 1}^L to E, with "L 209 < log2(n)- 1", which is a bijection over a subset of points in E. 210 This ensures that encoded plaintext messages can be recovered. 212 2.1.2. Serialization 214 A related issue is the conversion of an elliptic curve point to a 215 bitstring. We refer to this process as "serialization", since it is 216 typically used for compactly storing and transporting points, or for 217 producing canonicalized outputs. Since a deserialization algorithm 218 can often be used as a type of encoding algorithm, we also briefly 219 document properties of these functions. 221 A naive serialization algorithm maps a point (x, y) on E to a 222 bitstring of length 2*log(p), given that x, y are both elements in 223 GF(p). However, since there are only n points in E (with n 224 approximately equal to p), it is possible to serialize to a bitstring 225 of length log(n). For example, one common method is to store the 226 x-coordinate and a single bit to determine whether the point is (x, 227 y) or (x, -y), thus requiring log(p)+1 bits. Thus exchanging 228 computation (recovering the y coordinate) for storage. 230 2.1.3. Random Oracle 232 It is often the case that the output of the encoding function 233 Section 2.1.1 should be distributed uniformly at random on the 234 elliptic curve. That is, there is no discernible relation existing 235 between outputs that can be computed based on the inputs. In 236 practice, this requirement stems from needing a random oracle which 237 outputs elliptic curve points: one way to construct this is by first 238 taking a regular random oracle, operating entirely on bitstrings, and 239 applying a suitable encoding function to the output. 241 This motivates the term "hashing to the curve", since cryptographic 242 hash functions are typically modeled as random oracles. However, 243 this still leaves open the question of what constitutes a suitable 244 encoding method, which is a primary concern of this document. 246 A random oracle onto an elliptic curve can also be instantiated using 247 direct constructions, however these tend to rely on many group 248 operations and are less efficient than hash and encode methods. 250 3. Algorithm Recommendations 252 The following table lists algorithms recommended by use-case: 254 +----------------+-----------------+--------------------------------+ 255 | Application | Requirement | Additional Details | 256 +----------------+-----------------+--------------------------------+ 257 | SPEKE | Naive | H(x)*G | 258 | [Jablon96] | | | 259 | | | | 260 | PAKE [BMP00] | Random Oracle | - | 261 | | | | 262 | BLS [BLS01] | Random Oracle | - | 263 | | | | 264 | IBE [BF01] | Random Oracle | Supersingular, pairing- | 265 | | | friendly curve | 266 | | | | 267 | PRF | Injective | F(k, m) = k*H(m) | 268 | | encoding | | 269 +----------------+-----------------+--------------------------------+ 271 To find the suitable algorithm, lookup the requirement from above, 272 with the chosen curve in the below: 274 +------------+--------------------------+---------------+ 275 | Curve | Inj. Encoding | Random Oracle | 276 +------------+--------------------------+---------------+ 277 | P-256 | Simple SWU Section 5.2.3 | FFSTV(SWU) | 278 | | | | 279 | P-384 | Icart Section 5.2.1 | FFSTV(Icart) | 280 | | | | 281 | Curve25519 | Elligator2 Section 5.2.4 | ... | 282 | | | | 283 | Curve448 | Elligator2 Section 5.2.4 | ... | 284 +------------+--------------------------+---------------+ 286 4. Utility Functions 288 Algorithms in this document make use of utility functions described 289 below. 291 o HashToBase(x): H(x)[0:log2(p) + 1], i.e., hash-truncate-reduce, 292 where H is a cryptographic hash function, such as SHA256, and p is 293 the prime order of base field Fp. 295 o CMOV(a, b, c): If c = 1, return a, else return b. 297 Note: We assume that HashToBase maps its input to the base field 298 uniformly. In practice, there may be inherent biases in p, e.g., p = 299 2^k - 1 will have non-negligible bias in higher bits. 301 5. Deterministic Encodings 303 5.1. Interface 305 The generic interface for deterministic encoding functions to 306 elliptic curves is as follows: 308 map2curve(alpha) 310 where alpha is a message to encode on a curve. 312 5.2. Encoding Variants 314 5.2.1. Icart Method 316 The following map2curve_icart(alpha) implements the Icart method from 317 [Icart09]. This algorithm works for any curve over F_{p^n}, where 318 p^n = 2 mod 3 (or p = 2 mod 3 and for odd n), including: 320 o P384 322 o Curve1174 324 o Curve448 326 Unsupported curves include: P224, P256, P521, and Curve25519 since, 327 for each, p = 1 mod 3. 329 Mathematically, given input alpha, and A and B from E, the Icart 330 method works as follows: 332 u = HashToBase(alpha) 333 x = (v^2 - b - (u^6 / 27))^(1/3) + (u^2 / 3) 334 y = ux + v 336 where v = ((3A - u^4) / 6u). 338 The following procedure implements this algorithm in a straight-line 339 fashion. It requires knowledge of A and B, the constants from the 340 curve Weierstrass form. It outputs a point with affine coordinates. 342 map2curve_icart(alpha) 344 Input: 346 alpha - value to be hashed, an octet string 348 Output: 350 (x, y) - a point in E 352 Steps: 354 1. u = HashToBase(alpha) // {0,1}^* -> Fp 355 2. u2 = u^2 (mod p) // u^2 356 3. t2 = u2^2 (mod p) // u^4 357 4. v1 = 3 * A (mod p) // 3A 358 5. v1 = v1 - t2 (mod p) // 3A - u^4 359 6. t1 = 6 * u (mod p) // 6u 360 7. t3 = t1 ^ (-1) (mod p) // modular inverse 361 8. v = v1 * t3 (mod p) // (3A - u^4)/(6u) 362 9. x = v^2 (mod p) // v^2 363 10. x = x - B (mod p) // v^2 - b 364 11. t1 = 27 ^ (-1) (mod p) // 1/27 365 12. t1 = t1 * u2 (mod p) // u^4 / 27 366 13. t1 = t1 * t2 (mod p) // u^6 / 27 367 14. x = x - t1 (mod p) // v^2 - b - u^6/27 368 15. t1 = (2 * p) - 1 (mod p) // 2p - 1 369 16. t1 = t1 / 3 (mod p) // (2p - 1)/3 370 17. x = x^t1 (mod p) // (v^2 - b - u^6/27) ^ (1/3) 371 18. t2 = u2 / 3 (mod p) // u^2 / 3 372 19. x = x + t2 (mod p) // (v^2 - b - u^6/27) ^ (1/3) + (u^2 / 3) 373 20. y = u * x (mod p) // ux 374 21. y = y + v (mod p) // ux + v 375 22. Output (x, y) 377 5.2.2. Shallue-Woestijne-Ulas Method 379 The Shallue-Woestijne-Ulas (SWU) method, originated in part by 380 Shallue and Woestijne [SW06] and later simplified and extended by 381 Ulas [SWU07], deterministically encodes an artbirary string to a 382 point on a curve. This algorithm works for any curve over F_{p^n}. 383 Given curve equation g(x) = x^3 + Ax + B, two separate HashToBase 384 implementations, H0 and H1, this algorithm works as follows: 386 1. t = H0(alpha) 387 2. u = H1(alpha) 388 3. X1 = u 389 4. X2 = (-B / A)(1 + 1 / (t^4 * g(u)^2 + t^2 * g(u))) 390 5. X3 = t^3 * g(u)^2 * g(X2) 391 6. If g(X1) is square, output (X1, sqrt(g(X1))) 392 7. If g(X2) is square, output (X2, sqrt(g(X2))) 393 8. Output (X3(t, u), sqrt(g(X3))) 395 The algorithm relies on the following equality: 397 t^3 * g(u)^2 * g(X2(t, u)) = g(X1(t, u)) * g(X2(t, u)) * g(X3(t, u)) 399 The algorithm computes three candidate points, constructed such that 400 at least one of them lies on the curve. 402 The following procedure implements this algorithm. It outputs a 403 point with affine coordinates. It requires knowledge of A and B, the 404 constants from the curve Weierstrass form. 406 map2curve_squ(alpha) 408 Input: 410 alpha - value to be hashed, an octet string 411 H0 - HashToBase implementation 412 H1 - HashToBase implementation 414 Output: 416 (x, y) - a point in E 418 Steps: 420 1. t = H0(alpha) // {0,1}^* -> Fp 421 2. u = H1(alpha) // {0,1}^* -> Fp 422 3. t2 = t^2 423 4. t4 = t2^2 424 5. gu = u^3 425 6. gu = gu + (A * u) 426 7. gu = gu + B // gu = g(u) 427 8. x1 = u // x1 = X1(t, u) = u 428 9. x2 = B * -1 429 10. x2 = x2 / A 430 11. gx1 = x1^3 431 12. gx1 = gx1 + (A * x1) 432 13. gx1 = gx1 + B // gx1 = g(X1(t, u)) 433 14. d1 = gu^2 434 15. d1 = d1 * t4 435 16. d2 = t2 * gu 436 17. d3 = d1 + d2 437 18. d3 = d3^(-1) 438 19. n1 = 1 + d3 439 20. x2 = x2 * n1 // x2 = X2(t, u) 440 21. gx2 = x2^3 441 22. gx2 = gx2 + (A * x2) 442 23. gx2 = gx2 + B // gx2 = g(X2(t, u)) 443 24. x3 = t2 * gu 444 25. x3 = x3 * x2 // x3 = X3(t, u) 445 26. gx3 = x3^3 446 27. gx3 = gx3 + (A * x3) 447 28. gx3 = gx3 + B // gx3 = g(X3(t, u)) 448 29. l1 = gx1^((p - 1) / 2) 449 30. l2 = gx2^((p - 1) / 2) 450 31. s1 = gx1^(1/2) 451 32. s2 = gx2^(1/2) 452 33. s3 = gx3^(1/2) 453 34. if l1 == 1: 454 35. Output (x1, s1) 455 36. if l2 == 1: 456 37. Output (x2, s2) 457 38. Output (x3, s3) 459 5.2.3. Simplified SWU Method 461 The following map2curve_simple_swu(alpha) implements the simplfied 462 Shallue-Woestijne-Ulas algorithm from [SimpleSWU]. This algorithm 463 works for any curve over F_{p^n}, where p = 3 mod 4, including: 465 o P256 467 o ... 469 Given curve equation g(x) = x^3 + Ax + B, this algorithm works as 470 follows: 472 1. t = HashToBase(alpha) 473 2. alpha = (-b / a) * (1 + (1 / (t^4 + t^2))) 474 3. beta = -t^2 * alpha 475 4. If g(alpha) is square, output (alpha, sqrt(g(alpha))) 476 5. Output (beta, sqrt(g(beta))) 478 The following procedure implements this algorithm. It outputs a 479 point with affine coordinates. It requires knowledge of A and B, the 480 constants from the curve Weierstrass form. 482 map2curve_simple_swu(alpha) 484 Input: 486 alpha - value to be encoded, an octet string 488 Output: 490 (x, y) - a point in E 492 Steps: 494 1. t = HashToBase(alpha) 495 2. alpha = t^2 (mod p) 496 3. alpha = alpha * -1 (mod p) 497 4. right = alpha^2 + alpha (mod p) 498 5. right = right^(-1) (mod p) 499 6. right = right + 1 (mod p) 500 7. left = B * -1 (mod p) 501 8. left = left / A (mod p) 502 9. x2 = left * right (mod p) 503 10. x3 = alpha * x2 (mod p) 504 11. h2 = x2 ^ 3 (mod p) 505 12. i2 = x2 * A (mod p) 506 13. i2 = i2 + B (mod p) 507 14. h2 = h2 + i2 (mod p) 508 15. h3 = x3 ^ 3 (mod p) 509 16. i3 = x3 * A (mod p) 510 17. i3 = i3 + B (mod p) 511 18. h3 = h3 + i3 (mod p) 512 19. y1 = h2 ^ ((p + 1) // 4) (mod p) 513 20. y2 = h3 ^ ((p + 1) // 4) (mod p) 514 21. e = (y1 ^ 2 == h2) 515 22. x = CMOV(x2, x3, e) // If e = 1, choose x2, else choose x3 516 23. y = CMOV(y1, y2, e) // If e = 1, choose y1, else choose y2 517 24. Output (x, y) 519 5.2.4. Elligator2 Method 521 The following map2curve_elligator2(alpha) implements the Elligator2 522 method from [Elligator2]. This algorithm works for any curve with a 523 point of order 2 and j-invariant != 1728. Given curve equation f(x) 524 = y^2 = x(x^2 + Ax + B), i.e., a Montgomery form with the point of 525 order 2 at (0,0), this algorithm works as shown below. (Note that 526 any curve with a point of order 2 is isomorphic to this 527 representation.) 529 1. r = HashToBase(alpha) 530 2. If f(-A/(1+ur^2)) is square, then output f(-A/(1+ur^2))^(1/2) 531 3. Else, output f(-Aur^2/(1+ur^2))^(1/2) 533 Another way to express this algorithm is as follows: 535 1. r = HashToBase(alpha) 536 2. d = -A / (1 + ur^2) 537 3. e = f(d)^((p-1)/2) 538 4. u = ed - (1 - e)A/u 540 Here, e is the Legendre symbol of y = (d^3 + Ad^2 + d), which will be 541 1 if y is a quadratic residue (square) mod p, and -1 otherwise. 542 (Note that raising y to ((p -1) / 2) is a common way to compute the 543 Legendre symbol.) 545 The following procedure implements this algorithm. 547 map2curve_elligator2(alpha) 549 Input: 551 alpha - value to be encoded, an octet string 553 u - fixed non-square value in Fp. 554 f() - Curve function 556 Output: 558 (x, y) - a point in E 560 Steps: 562 1. r = HashToBase(alpha) 563 2. r = r^2 (mod p) 564 3. nu = r * u (mod p) 565 4. r = nu 566 5. r = r + 1 (mod p) 567 6. r = r^(-1) (mod p) 568 7. v = A * r (mod p) 569 8. v = v * -1 (mod p) // -A / (1 + ur^2) 570 9. v2 = v^2 (mod p) 571 10. v3 = v * v2 (mod p) 572 11. e = v3 * v (mod p) 573 12. v2 = v2 * A (mod p) 574 13. e = v2 * e (mod p) 575 14. e = e^((p - 1) / 2) // Legendre symbol 576 15. nv = v * -1 (mod p) 577 16. v = CMOV(v, nv, e) // If e = 1, choose v, else choose nv 578 17. v2 = CMOV(0, A, e) // If e = 1, choose 0, else choose A 579 18. u = v - v2 (mod p) 580 19. Output (u, f(u)) 582 Elligator2 can be simplified with projective coordinates. 584 ((TODO: write this variant)) 586 5.3. Cost Comparison 588 The following table summarizes the cost of each map2curve variant. 589 We express this cost in terms of additions (A), multiplications (M), 590 squares (SQ), and square roots (SR). 592 ((TODO: finish this section)) 593 +----------------------+-------------------+ 594 | Algorithm | Cost (Operations) | 595 +----------------------+-------------------+ 596 | map2curve_icart | TODO | 597 | | | 598 | map2curve_swu | TODO | 599 | | | 600 | map2curve_simple_swu | TODO | 601 | | | 602 | map2curve_elligator2 | TODO | 603 +----------------------+-------------------+ 605 6. Random Oracles 607 6.1. Interface 609 The generic interface for deterministic encoding functions to 610 elliptic curves is as follows: 612 hash2curve(alpha) 614 where alpha is a message to encode on a curve. 616 6.2. General Construction (FFSTV13) 618 When applications need a Random Oracle (RO), they can be constructed 619 from deterministic encoding functions. In particular, let F : 620 {0,1}^* -> E be a deterministic encoding function onto curve E, and 621 let H0 and H1 be two hash functions modeled as random oracles that 622 map input messages to the base field of E, i.e., Z_q. Farashahi et 623 al. [FFSTV13] showed that the following mapping is indistinguishable 624 from a RO: 626 hash2curve(alpha) = F(H0(alpha)) + F(H1(alpha)) 628 This construction works for the Icart, SWU, and Simplfied SWU 629 encodings. 631 Here, H0 and H1 could be constructed as follows: 633 H0(alpha) = HashToBase(0 || alpha) 634 H1(alpha) = HashToBase(1 || alpha) 636 7. Curve Transformations 638 ((TODO: write this section)) 640 8. IANA Considerations 642 This document has no IANA actions. 644 9. Security Considerations 646 Each encoding function variant accepts arbitrary input and maps it to 647 a pseudorandom point on the curve. Points are close to 648 indistinguishable from randomly chosen elements on the curve. Not 649 all encoding functions are full-domain hashes. Elligator2, for 650 example, only maps strings to "about half of all curve points," 651 whereas Icart's method only covers about 5/8 of the points. 653 10. Acknowledgements 655 The authors would like to thank Adam Langley for this detailed 656 writeup up Elligator2 with Curve25519 [ElligatorAGL]. We also thank 657 Sean Devlin and Thomas Icart for feedback on earlier versions of this 658 document. 660 11. Contributors 662 o Sharon Goldberg 663 Boston University 664 goldbe@cs.bu.edu 666 12. Normative References 668 [BF01] "Identity-based encryption from the Weil pairing", n.d.. 670 [BLS01] "Short signatures from the Weil pairing", n.d., 671 . 673 [BMP00] "Provably secure password-authenticated key exchange using 674 diffie-hellman", n.d.. 676 [ECOPRF] "EC-OPRF - Oblivious Pseudorandom Functions using Elliptic 677 Curves", n.d.. 679 [Elligator2] 680 "Elligator -- Elliptic-curve points indistinguishable from 681 uniform random strings", n.d., . 684 [ElligatorAGL] 685 "Implementing Elligator for Curve25519", n.d., 686 . 689 [FFSTV13] "Indifferentiable deterministic hashing to elliptic and 690 hyperelliptic curves", n.d.. 692 [hacspec] "hacspec", n.d., . 695 [Icart09] "How to Hash into Elliptic Curves", n.d., 696 . 698 [Jablon96] 699 "Strong password-only authenticated key exchange", n.d.. 701 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 702 Requirement Levels", BCP 14, RFC 2119, 703 DOI 10.17487/RFC2119, March 1997, . 706 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 707 for Security", RFC 7748, DOI 10.17487/RFC7748, January 708 2016, . 710 [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, 711 "PKCS #1: RSA Cryptography Specifications Version 2.2", 712 RFC 8017, DOI 10.17487/RFC8017, November 2016, 713 . 715 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 716 Signature Algorithm (EdDSA)", RFC 8032, 717 DOI 10.17487/RFC8032, January 2017, . 720 [SECG1] "SEC 1 -- Elliptic Curve Cryptography", n.d., 721 . 723 [SimpleSWU] 724 "Efficient Indifferentiable Hashing into Ordinary Elliptic 725 Curves", n.d.. 727 [SW06] "Construction of rational points on elliptic curves over 728 finite fields", n.d.. 730 [SWU07] "Rational points on certain hyperelliptic curves over 731 finite fields", n.d., . 733 Appendix A. Related Work 735 In this chapter, we give a background to some common methods to 736 encode or hash to the curve, motivated by the similar exposition in 737 [Icart09]. Understanding of this material is not required in order 738 to choose a suitable encoding function - we defer this to Section 3 - 739 the background covered here can work as a template for analyzing 740 encoding functions not found in this document, and as a guide for 741 further research into the topics covered. 743 A.1. Probabilistic Encoding 745 As mentioned in Section 2, as a rule of thumb, for every x in GF(p), 746 there is approximately a 1/2 chance that there exist a corresponding 747 y value such that (x, y) is on the curve E. 749 This motivates the construction of the MapToGroup method described by 750 Boneh et al. [BLS01]. For an input message m, a counter i, and a 751 standard hash function H : {0, 1}^* -> GF(p) x {0, 1}, one computes 752 (x, b) = H(i || m), where i || m denotes concatenation of the two 753 values. Next, test to see whether there exists a corresponding y 754 value such that (x, y) is on the curve, returning (x, y) if 755 successful, where b determines whether to take +/- y. If there does 756 not exist such a y, then increment i and repeat. A maximum counter 757 value is set to I, and since each iteration succeeds with probability 758 approximately 1/2, this process fails with probability 2^-I. (See 759 Appendix B for a more detailed description of this algorithm.) 761 Although MapToGroup describes a method to hash to the curve, it can 762 also be adapted to a simple encoding mechanism. For a bitstring of 763 length strictly less than log2(p), one can make use of the spare bits 764 in order to encode the counter value. Allocating more space for the 765 counter increases the expansion, but reduces the failure probability. 767 Since the running time of the MapToGroup algorithm depends on m, this 768 algorithm is NOT safe for cases sensitive to timing side channel 769 attacks. Deterministic algorithms are needed in such cases where 770 failures are undesirable. 772 A.2. Naive Encoding 774 A naive solution includes computing H(m)*G as map2curve(m), where H 775 is a standard hash function H : {0, 1}^* -> GF(p), and G is a 776 generator of the curve. Although efficient, this solution is 777 unsuitable for constructing a random oracle onto E, since the 778 discrete logarithm with respect to G is known. For example, given y1 779 = map2curve(m1) and y2 = map2curve(m2) for any m1 and m2, it must be 780 true that y2 = H(m2) / H(m1) * map2curve(m1). This relationship 781 would not hold (with overwhelming probability) for truly random 782 values y1 and y2. This causes catastrophic failure in many cases. 783 However, one exception is found in SPEKE [Jablon96], which constructs 784 a base for a Diffie-Hellman key exchange by hashing the password to a 785 curve point. Notably the use of a hash function is purely for 786 encoding an arbitrary length string to a curve point, and does not 787 need to be a random oracle. 789 A.3. Deterministic Encoding 791 Shallue, Woestijne, and Ulas [SW06] first introduced a deterministic 792 algorithm that maps elements in F_{q} to a curve in time O(log^4 q), 793 where q = p^n for some prime p, and time O(log^3 q) when q = 3 mod 4. 794 Icart introduced yet another deterministic algorithm which maps F_{q} 795 to any EC where q = 2 mod 3 in time O(log^3 q) [Icart09]. Elligator 796 (2) [Elligator2] is yet another deterministic algorithm for any odd- 797 characteristic EC that has a point of order 2. Elligator2 can be 798 applied to Curve25519 and Curve448, which are both CFRG-recommended 799 curves [RFC7748]. 801 However, an important caveat to all of the above deterministic 802 encoding functions, is that none of them map injectively to the 803 entire curve, but rather some fraction of the points. This makes 804 them unable to use to directly construct a random oracle on the 805 curve. 807 Brier et al. [SimpleSWU] proposed a couple of solutions to this 808 problem, The first applies solely to Icart's method described above, 809 by computing F(H1(m)) + F(H2(m)) for two distinct hash functions H1, 810 H2. The second uses a generator G, and computes F(H1(m)) + H2(m)*G. 811 Later, Farashahi et al. [FFSTV13] showed the generality of the 812 F(H1(m)) + F(H2(m)) method, as well as the applicability to 813 hyperelliptic curves (not covered here). 815 A.4. Supersingular Curves 817 For supersingular curves, for every y in GF(p) (with p>3), there 818 exists a value x such that (x, y) is on the curve E. Hence we can 819 construct a bijection F : GF(p) -> E (ignoring the point at 820 infinity). This is the case for [BF01], but is not common. 822 A.5. Twisted Variants 824 We can also consider curves which have twisted variants, E^d. For 825 such curves, for any x in GF(p), there exists y in GF(p) such that 826 (x, y) is either a point on E or E^d. Hence one can construct a 827 bijection F : GF(p) x {0,1} -> E ∪ E^d, where the extra bit is 828 needed to choose the sign of the point. This can be particularly 829 useful for constructions which only need the x-coordinate of the 830 point. For example, x-only scalar multiplication can be computed on 831 Montgomery curves. In this case, there is no need for an encoding 832 function, since the output of F in GF(p) is sufficient to define a 833 point on one of E or E^d. 835 Appendix B. Try-and-Increment Method 837 In cases where constant time execution is not required, the so-called 838 try-and-increment method may be appropriate. As discussion in 839 Section Section 1, this variant works by hashing input m using a 840 standard hash function ("Hash"), e.g., SHA256, and then checking to 841 see if the resulting point E(m, f(m)), for curve function f, belongs 842 on E. This is detailed below. 844 1. ctr = 0 845 3. h = "INVALID" 846 4. While h is "INVALID" or h is EC point at infinity: 847 A. CTR = I2OSP(ctr, 4) 848 B. ctr = ctr + 1 849 C. attempted_hash = Hash(m || CTR) 850 D. h = RS2ECP(attempted_hash) 851 E. If h is not "INVALID" and cofactor > 1, set h = h^cofactor 852 5. Output h 854 I2OSP is a function that converts a nonnegative integer to octet 855 string as defined in Section 4.1 of [RFC8017], and RS2ECP is a 856 function that converts of a random 2n-octet string to an EC point as 857 specified in Section 5.1.3 of [RFC8032]. 859 Appendix C. Sample Code 861 This section contains reference implementations for each map2curve 862 variant built using [hacspec]. 864 C.1. Icart Method 866 The following hacspec program implements map2curve_icart(alpha) for 867 P-384. 869 from hacspec.speclib import * 871 prime = 2**384 - 2**128 - 2**96 + 2**32 - 1 873 felem_t = refine(nat, lambda x: x < prime) 874 affine_t = tuple2(felem_t, felem_t) 876 @typechecked 877 def to_felem(x: nat_t) -> felem_t: 878 return felem_t(nat(x % prime)) 880 @typechecked 881 def fadd(x: felem_t, y: felem_t) -> felem_t: 882 return to_felem(x + y) 884 @typechecked 885 def fsub(x: felem_t, y: felem_t) -> felem_t: 886 return to_felem(x - y) 888 @typechecked 889 def fmul(x: felem_t, y: felem_t) -> felem_t: 890 return to_felem(x * y) 892 @typechecked 893 def fsqr(x: felem_t) -> felem_t: 894 return to_felem(x * x) 896 @typechecked 897 def fexp(x: felem_t, n: nat_t) -> felem_t: 898 return to_felem(pow(x, n, prime)) 900 @typechecked 901 def finv(x: felem_t) -> felem_t: 902 return to_felem(pow(x, prime-2, prime)) 904 a384 = to_felem(prime - 3) 905 b384 = to_felem(27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575) 907 @typechecked 908 def map2p384(u:felem_t) -> affine_t: 909 v = fmul(fsub(fmul(to_felem(3), a384), fexp(u, 4)), finv(fmul(to_felem(6), u))) 910 u2 = fmul(fexp(u, 6), finv(to_felem(27))) 911 x = fsub(fsqr(v), b384) 912 x = fsub(x, u2) 913 x = fexp(x, (2 * prime - 1) // 3) 914 x = fadd(x, fmul(fsqr(u), finv(to_felem(3)))) 915 y = fadd(fmul(u, x), v) 916 return (x, y) 918 C.2. Shallue-Woestijne-Ulas Method 920 The following hacspec program implements map2curve_swu(alpha) for 921 P-256. 923 from p256 import * 924 from hacspec.speclib import * 926 a256 = to_felem(prime - 3) 927 b256 = to_felem(41058363725152142129326129780047268409114441015993725554835256314039467401291) 929 @typechecked 930 def f_p256(x:felem_t) -> felem_t: 931 return fadd(fexp(x, 3), fadd(fmul(to_felem(a256), x), to_felem(b256))) 933 @typechecked 934 def x1(t:felem_t, u:felem_t) -> felem_t: 935 return u 937 @typechecked 938 def x2(t:felem_t, u:felem_t) -> felem_t: 939 coefficient = fmul(to_felem(-b256), finv(to_felem(a256))) 940 t2 = fsqr(t) 941 t4 = fsqr(t2) 942 gu = f_p256(u) 943 gu2 = fsqr(gu) 944 denom = fadd(fmul(t4, gu2), fmul(t2, gu)) 945 return fmul(coefficient, fadd(to_felem(1), finv(denom))) 947 @typechecked 948 def x3(t:felem_t, u:felem_t) -> felem_t: 949 return fmul(fsqr(t), fmul(f_p256(u), x2(t, u))) 951 @typechecked 952 def map2p256(t:felem_t) -> felem_t: 953 u = fadd(t, to_felem(1)) 954 x1v = x1(t, u) 955 x2v = x2(t, u) 956 x3v = x3(t, u) 958 exp = to_felem((prime - 1) // 2) 959 e1 = fexp(f_p256(x1v), exp) 960 e2 = fexp(f_p256(x2v), exp) 962 if e1 == 1: 963 return x1v 964 elif e2 == 1: 965 return x2v 966 else: 967 return x3v 969 C.3. Simplified SWU Method 971 The following hacspec program implements map2curve_simple_swu(alpha) 972 for P-256. 974 from p256 import * 975 from hacspec.speclib import * 977 a256 = to_felem(prime - 3) 978 b256 = to_felem(41058363725152142129326129780047268409114441015993725554835256314039467401291) 980 def f_p256(x:felem_t) -> felem_t: 981 return fadd(fexp(x, 3), fadd(fmul(to_felem(a256), x), to_felem(b256))) 983 def map2p256(t:felem_t) -> affine_t: 984 alpha = to_felem(-(fsqr(t))) 985 frac = finv((fadd(fsqr(alpha), alpha))) 986 coefficient = fmul(to_felem(-b256), finv(to_felem(a256))) 987 x2 = fmul(coefficient, fadd(to_felem(1), frac)) 989 x3 = fmul(alpha, x2) 990 h2 = fadd(fexp(x2, 3), fadd(fmul(a256, x2), b256)) 991 h3 = fadd(fexp(x3, 3), fadd(fmul(a256, x3), b256)) 993 exp = fmul(fadd(to_felem(prime), to_felem(-1)), finv(to_felem(2))) 994 e = fexp(h2, exp) 996 exp = to_felem((prime + 1) // 4) 997 if e == 1: 998 return (x2, fexp(f_p256(x2), exp)) 999 else: 1000 return (x3, fexp(f_p256(x3), exp)) 1002 C.4. Elligator2 Method 1004 The following hacspec program implements map2curve_elligator2(alpha) 1005 for Curve25519. 1007 from curve25519 import * 1008 from hacspec.speclib import * 1010 a25519 = to_felem(486662) 1011 b25519 = to_felem(1) 1012 u25519 = to_felem(2) 1014 @typechecked 1015 def f_25519(x:felem_t) -> felem_t: 1016 return fadd(fmul(x, fsqr(x)), fadd(fmul(a25519, fsqr(x)), x)) 1018 @typechecked 1019 def map2curve25519(r:felem_t) -> felem_t: 1020 d = fsub(to_felem(p25519), fmul(a25519, finv(fadd(to_felem(1), fmul(u25519, fsqr(r)))))) 1021 power = nat((p25519 - 1) // 2) 1022 e = fexp(f_25519(d), power) 1023 x = 0 1024 if e != 1: 1025 x = fsub(to_felem(-d), to_felem(a25519)) 1026 else: 1027 x = d 1029 return x 1031 Authors' Addresses 1033 Sam Scott 1034 Cornell Tech 1035 2 West Loop Rd 1036 New York, New York 10044 1037 United States of America 1039 Email: sam.scott@cornell.edu 1041 Nick Sullivan 1042 Cloudflare 1043 101 Townsend St 1044 San Francisco 1045 United States of America 1047 Email: nick@cloudflare.com 1048 Christopher A. Wood 1049 Apple Inc. 1050 One Apple Park Way 1051 Cupertino, California 95014 1052 United States of America 1054 Email: cawood@apple.com