idnits 2.17.1 draft-irtf-cfrg-hash-to-curve-02.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 (October 22, 2018) is 2014 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'ECOPRF' is defined on line 785, but no explicit reference was found in the text == Unused Reference: 'FIPS-186-4' is defined on line 801, but no explicit reference was found in the text == Unused Reference: 'RFC5869' is defined on line 826, but no explicit reference was found in the text == Unused Reference: 'RFC8032' is defined on line 845, but no explicit reference was found in the text Summary: 1 error (**), 0 flaws (~~), 6 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: April 25, 2019 Cloudflare 6 C. Wood 7 Apple Inc. 8 October 22, 2018 10 Hashing to Elliptic Curves 11 draft-irtf-cfrg-hash-to-curve-02 13 Abstract 15 This document specifies a number of algorithms that may be used to 16 encode or hash an arbitrary string to a point on an Elliptic Curve. 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 April 25, 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 . . . . . . . . . . . . . . . . . . . . . . . . 3 53 1.1. Requirements . . . . . . . . . . . . . . . . . . . . . . 3 54 2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 3 55 2.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 56 2.1.1. Encoding . . . . . . . . . . . . . . . . . . . . . . 4 57 2.1.2. Serialization . . . . . . . . . . . . . . . . . . . . 5 58 2.1.3. Random Oracle . . . . . . . . . . . . . . . . . . . . 5 59 3. Algorithm Recommendations . . . . . . . . . . . . . . . . . . 6 60 4. Utility Functions . . . . . . . . . . . . . . . . . . . . . . 6 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 . . . . . . . . . . . . . . . . 11 67 5.2.4. Elligator2 Method . . . . . . . . . . . . . . . . . . 12 68 5.3. Cost Comparison . . . . . . . . . . . . . . . . . . . . . 14 69 6. Random Oracles . . . . . . . . . . . . . . . . . . . . . . . 14 70 6.1. Interface . . . . . . . . . . . . . . . . . . . . . . . . 14 71 6.2. General Construction (FFSTV13) . . . . . . . . . . . . . 14 72 7. Curve Transformations . . . . . . . . . . . . . . . . . . . . 15 73 8. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 15 74 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 75 10. Security Considerations . . . . . . . . . . . . . . . . . . . 17 76 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 17 77 12. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 17 78 13. Normative References . . . . . . . . . . . . . . . . . . . . 17 79 Appendix A. Related Work . . . . . . . . . . . . . . . . . . . . 19 80 A.1. Probabilistic Encoding . . . . . . . . . . . . . . . . . 20 81 A.2. Naive Encoding . . . . . . . . . . . . . . . . . . . . . 20 82 A.3. Deterministic Encoding . . . . . . . . . . . . . . . . . 21 83 A.4. Supersingular Curves . . . . . . . . . . . . . . . . . . 21 84 A.5. Twisted Variants . . . . . . . . . . . . . . . . . . . . 21 85 Appendix B. Try-and-Increment Method . . . . . . . . . . . . . . 22 86 Appendix C. Sample Code . . . . . . . . . . . . . . . . . . . . 22 87 C.1. Icart Method . . . . . . . . . . . . . . . . . . . . . . 22 88 C.2. Shallue-Woestijne-Ulas Method . . . . . . . . . . . . . . 23 89 C.3. Simplified SWU Method . . . . . . . . . . . . . . . . . . 25 90 C.4. Elligator2 Method . . . . . . . . . . . . . . . . . . . . 25 91 C.5. HashToBase . . . . . . . . . . . . . . . . . . . . . . . 26 92 C.5.1. Considerations . . . . . . . . . . . . . . . . . . . 27 93 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 28 95 1. Introduction 97 Many cryptographic protocols require a procedure which maps arbitrary 98 input, e.g., passwords, to points on an elliptic curve (EC). 99 Prominent examples include Simple Password Exponential Key Exchange 100 [Jablon96], Password Authenticated Key Exchange [BMP00], Identity- 101 Based Encryption [BF01] and Boneh-Lynn-Shacham signatures [BLS01]. 103 Unfortunately for implementors, the precise mapping which is suitable 104 for a given scheme is not necessarily included in the description of 105 the protocol. Compounding this problem is the need to pick a 106 suitable curve for the specific protocol. 108 This document aims to address this lapse by providing a thorough set 109 of recommendations across a range of implementations, and curve 110 types. We provide implementation and performance details for each 111 mechanism, along with references to the security rationale behind 112 each recommendation and guidance for applications not yet covered. 114 Each algorithm conforms to a common interface, i.e., it maps a 115 bitstring {0, 1}^* to a point on an elliptic curve E. For each 116 variant, we describe the requirements for E to make it work. Sample 117 code for each variant is presented in the appendix. Unless otherwise 118 stated, all elliptic curve points are assumed to be represented as 119 affine coordinates, i.e., (x, y) points on a curve. 121 1.1. Requirements 123 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 124 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 125 document are to be interpreted as described in [RFC2119]. 127 2. Background 129 Here we give a brief definition of elliptic curves, with an emphasis 130 on defining important parameters and their relation to encoding. 132 Let F be the finite field GF(p^k). We say that F is a field of 133 characteristic p. For most applications, F is a prime field, in 134 which case k=1 and we will simply write GF(p). 136 Elliptic curves can be represented by equations of different standard 137 forms, including, but not limited to: Weierstrass, Montgomery, and 138 Edwards. Each of these variants correspond to a different category 139 of curve equation. For example, the short Weierstrass equation is 140 "y^2 = x^3 + Ax + B". Certain encoding functions may have 141 requirements on the curve form, the characteristic of the field, and 142 the parameters, such as A and B in the previous example. 144 An elliptic curve E is specified by its equation, and a finite field 145 F. The curve E forms a group, whose elements correspond to those who 146 satisfy the curve equation, with values taken from the field F. As a 147 group, E has order n, which is the number of points on the curve. 148 For security reasons, it is a strong requirement that all 149 cryptographic operations take place in a prime order group. However, 150 not all elliptic curves generate groups of prime order. In those 151 cases, it is allowed to work with elliptic curves of order n = qh, 152 where q is a large prime, and h is a short number known as the 153 cofactor. Thus, we may wish an encoding that returns points on the 154 subgroup of order q. Multiplying a point P on E by the cofactor h 155 guarantees that hP is a point in the subgroup of order q. 157 Summary of quantities: 159 +--------+-------------------+--------------------------------------+ 160 | Symbol | Meaning | Relevance | 161 +--------+-------------------+--------------------------------------+ 162 | p | Order of finite | Curve points need to be represented | 163 | | field, F = GF(p) | in terms of p. For prime power | 164 | | | extension fields, we write F = | 165 | | | GF(p^k). | 166 | | | | 167 | n | Number of curve | For map to E, needs to produce n | 168 | | points, #E(F) = n | elements. | 169 | | | | 170 | q | Order of the | If n is not prime, may need mapping | 171 | | largest prime | to q. | 172 | | subgroup of E, n | | 173 | | = qh | | 174 | | | | 175 | h | Cofactor | For mapping to subgroup, need to | 176 | | | multiply by cofactor. | 177 +--------+-------------------+--------------------------------------+ 179 2.1. Terminology 181 In the following, we categorize the terminology for mapping 182 bitstrings to points on elliptic curves. 184 2.1.1. Encoding 186 In practice, the input of a given cryptographic algorithm will be a 187 bitstring of arbitrary length, denoted {0, 1}^*. Hence, a concern for 188 virtually all protocols involving elliptic curves is how to convert 189 this input into a curve point. The general term "encoding" refers to 190 the process of producing an elliptic curve point given as input a 191 bitstring. In some protocols, the original message may also be 192 recovered through a decoding procedure. An encoding may be 193 deterministic or probabilistic, although the latter is problematic in 194 potentially leaking plaintext information as a side-channel. 196 Suppose as the input to the encoding function we wish to use a fixed- 197 length bitstring of length L. Comparing sizes of the sets, 2^L and 198 n, an encoding function cannot be both deterministic and bijective. 199 We can instead use an injective encoding from {0, 1}^L to E, with "L 200 < log2(n)- 1", which is a bijection over a subset of points in E. 201 This ensures that encoded plaintext messages can be recovered. 203 2.1.2. Serialization 205 A related issue is the conversion of an elliptic curve point to a 206 bitstring. We refer to this process as "serialization", since it is 207 typically used for compactly storing and transporting points, or for 208 producing canonicalized outputs. Since a deserialization algorithm 209 can often be used as a type of encoding algorithm, we also briefly 210 document properties of these functions. 212 A straightforward serialization algorithm maps a point (x, y) on E to 213 a bitstring of length 2*log(p), given that x, y are both elements in 214 GF(p). However, since there are only n points in E (with n 215 approximately equal to p), it is possible to serialize to a bitstring 216 of length log(n). For example, one common method is to store the 217 x-coordinate and a single bit to determine whether the point is (x, 218 y) or (x, -y), thus requiring log(p)+1 bits. This method reduces 219 storage, but adds computation, since the deserialization process must 220 recover the y coordinate. 222 2.1.3. Random Oracle 224 It is often the case that the output of the encoding function 225 Section 2.1.1 should be distributed uniformly at random on the 226 elliptic curve. That is, there is no discernible relation existing 227 between outputs that can be computed based on the inputs. In 228 practice, this requirement stems from needing a random oracle which 229 outputs elliptic curve points: one way to construct this is by first 230 taking a regular random oracle, operating entirely on bitstrings, and 231 applying a suitable encoding function to the output. 233 This motivates the term "hashing to the curve", since cryptographic 234 hash functions are typically modeled as random oracles. However, 235 this still leaves open the question of what constitutes a suitable 236 encoding method, which is a primary concern of this document. 238 A random oracle onto an elliptic curve can also be instantiated using 239 direct constructions, however these tend to rely on many group 240 operations and are less efficient than hash and encode methods. 242 3. Algorithm Recommendations 244 The following table lists algorithms recommended by use-case: 246 +----------------+-----------------+--------------------------------+ 247 | Application | Requirement | Additional Details | 248 +----------------+-----------------+--------------------------------+ 249 | SPEKE | Naive | H(x)*G | 250 | [Jablon96] | | | 251 | | | | 252 | PAKE [BMP00] | Random Oracle | - | 253 | | | | 254 | BLS [BLS01] | Random Oracle | - | 255 | | | | 256 | IBE [BF01] | Random Oracle | Supersingular, pairing- | 257 | | | friendly curve | 258 | | | | 259 | PRF | Injective | F(k, m) = k*H(m) | 260 | | encoding | | 261 +----------------+-----------------+--------------------------------+ 263 To find the suitable algorithm, lookup the requirement from above, 264 with the chosen curve in the below: 266 +------------+--------------------------+---------------+ 267 | Curve | Inj. Encoding | Random Oracle | 268 +------------+--------------------------+---------------+ 269 | P-256 | Simple SWU Section 5.2.3 | FFSTV(SWU) | 270 | | | | 271 | P-384 | Icart Section 5.2.1 | FFSTV(Icart) | 272 | | | | 273 | Curve25519 | Elligator2 Section 5.2.4 | ... | 274 | | | | 275 | Curve448 | Elligator2 Section 5.2.4 | ... | 276 +------------+--------------------------+---------------+ 278 4. Utility Functions 280 Algorithms in this document make use of utility functions described 281 below. 283 o HashToBase(x, i). This method is parametrized by p and H, where p 284 is the prime order of the base field Fp, and H is a cryptographic 285 hash function which outputs at least floor(log2(p)) + 2 bits. The 286 function first hashes x, converts the result to an integer, and 287 reduces modulo p to give an element of Fp. 289 We provide a more detailed algorithm in Appendix C.5. The value 290 of i is used to separate inputs when used multiple times in one 291 algorithm (see Section 6.2 for example). When i is omitted, we 292 set it to 0. 294 o CMOV(a, b, c): If c = 1, return a, else return b. 296 Common software implementations of constant-time selects assume c 297 = 1 or c = 0. CMOV may be implemented by computing the desired 298 selector (0 or 1) by ORing all bits of c together. The end result 299 will be either 0 if all bits of c are zero, or 1 if at least one 300 bit of c is 1. 302 o CTEQ(a, b): Returns a == b. Inputs a and b must be the same 303 length (as bytestrings) and the comparison must be implemented in 304 constant time. 306 o Legendre(x, p): x^((p-1)/2). The Legendre symbol computes whether 307 the value x is a "quadratic residue" modulo p, and takes values 1, 308 -1, 0, for when x is a residue, non-residue, or zero, 309 respectively. Due to Euler's criterion, this can be computed in 310 constant time, with respect to a fixed p, using the equation 311 x^((p-1)/2). For clarity, we will generally prefer using the 312 formula directly, and annotate the usage with this definition. 314 5. Deterministic Encodings 316 5.1. Interface 318 The generic interface for deterministic encoding functions to 319 elliptic curves is as follows: 321 map2curve(alpha) 323 where alpha is a message to encode on a curve. 325 5.2. Encoding Variants 327 5.2.1. Icart Method 329 The following map2curve_icart(alpha) implements the Icart method from 330 [Icart09]. This algorithm works for any curve over F_{p^n}, where 331 p^n = 2 mod 3 (or p = 2 mod 3 and for odd n), including: 333 o P384 334 o Curve1174 336 o Curve448 338 Unsupported curves include: P224, P256, P521, and Curve25519 since, 339 for each, p = 1 mod 3. 341 Mathematically, given input alpha, and A and B from E, the Icart 342 method works as follows: 344 u = HashToBase(alpha) 345 v = ((3A - u^4) / 6u) 346 x = (v^2 - B - (u^6 / 27))^(1/3) + (u^2 / 3) 347 y = ux + v 349 The following procedure implements this algorithm in a straight-line 350 fashion. It requires knowledge of A and B, the constants from the 351 curve Weierstrass form. It outputs a point with affine coordinates. 353 map2curve_icart(alpha) 355 Input: 357 alpha - value to be hashed, an octet string 359 Output: 361 (x, y) - a point in E 363 Steps: 365 1. u = HashToBase(alpha) // {0,1}^* -> Fp 366 2. u2 = u^2 (mod p) // u^2 367 3. t2 = u2^2 (mod p) // u^4 368 4. v1 = 3 * A (mod p) // 3A in Fp 369 5. v1 = v1 - t2 (mod p) // 3A - u^4 370 6. t1 = 6 * u (mod p) // 6u 371 7. t3 = t1 ^ (-1) (mod p) // modular inverse 372 8. v = v1 * t3 (mod p) // (3A - u^4)/(6u) 373 9. x = v^2 (mod p) // v^2 374 10. x = x - B (mod p) // v^2 - B 375 11. t1 = 27 ^ (-1) (mod p) // 1/27 376 12. t1 = t1 * u2 (mod p) // u^4 / 27 377 13. t1 = t1 * t2 (mod p) // u^6 / 27 378 14. x = x - t1 (mod p) // v^2 - B - u^6/27 379 15. t1 = (2 * p) - 1 // 2p - 1 in ZZ 380 16. t1 = t1 / 3 // (2p - 1)/3 in ZZ 381 17. x = x^t1 (mod p) // (v^2 - B - u^6/27) ^ (1/3) 382 18. t2 = u2 / 3 (mod p) // u^2 / 3 383 19. x = x + t2 (mod p) // (v^2 - B - u^6/27) ^ (1/3) + (u^2 / 3) 384 20. y = u * x (mod p) // ux 385 21. y = y + v (mod p) // ux + v 386 22. Output (x, y) 388 5.2.2. Shallue-Woestijne-Ulas Method 390 The Shallue-Woestijne-Ulas (SWU) method, originated in part by 391 Shallue and Woestijne [SW06] and later simplified and extended by 392 Ulas [SWU07], deterministically encodes an arbitrary string to a 393 point on a curve. This algorithm works for any curve over F_{p^n}. 394 Given curve equation g(x) = x^3 + Ax + B, this algorithm works as 395 follows: 397 1. t = HashToBase(alpha, 0) 398 2. u = HashToBase(alpha, 1) 399 3. X1 = u 400 4. X2 = (-B / A)(1 + 1 / (t^4 * g(u)^2 + t^2 * g(u))) 401 5. X3 = t^3 * g(u)^2 * g(X2) 402 6. If g(X1) is square, output (X1, sqrt(g(X1))) 403 7. If g(X2) is square, output (X2, sqrt(g(X2))) 404 8. Output (X3(t, u), sqrt(g(X3))) 406 The algorithm relies on the following equality: 408 t^3 * g(u)^2 * g(X2(t, u)) = g(X1(t, u)) * g(X2(t, u)) * g(X3(t, u)) 410 The algorithm computes three candidate points, constructed such that 411 at least one of them lies on the curve. 413 The following procedure implements this algorithm. It outputs a 414 point with affine coordinates. It requires knowledge of A and B, the 415 constants from the curve Weierstrass form. 417 map2curve_swu(alpha) 419 Input: 421 alpha - value to be hashed, an octet string 423 Output: 425 (x, y) - a point in E 427 Steps: 429 1. t = HashToBase(alpha, 0) // {0,1}^* -> Fp 430 2. u = HashToBase(alpha, 1) // {0,1}^* -> Fp 431 3. t2 = t^2 432 4. t4 = t2^2 433 5. gu = u^3 434 6. gu = gu + (A * u) 435 7. gu = gu + B // gu = g(u) 436 8. x1 = u // x1 = X1(t, u) = u 437 9. x2 = B * -1 438 10. x2 = x2 / A 439 11. gx1 = x1^3 440 12. gx1 = gx1 + (A * x1) 441 13. gx1 = gx1 + B // gx1 = g(X1(t, u)) 442 14. d1 = gu^2 443 15. d1 = d1 * t4 444 16. d2 = t2 * gu 445 17. d3 = d1 + d2 446 18. d3 = d3^(-1) 447 19. n1 = 1 + d3 448 20. x2 = x2 * n1 // x2 = X2(t, u) 449 21. gx2 = x2^3 450 22. gx2 = gx2 + (A * x2) 451 23. gx2 = gx2 + B // gx2 = g(X2(t, u)) 452 24. x3 = t2 * gu 453 25. x3 = x3 * x2 // x3 = X3(t, u) 454 26. gx3 = x3^3 455 27. gx3 = gx3 + (A * x3) 456 28. gx3 = gx3 + B // gx3 = g(X3(t, u)) 457 29. l1 = gx1^((p - 1) / 2) 458 30. l2 = gx2^((p - 1) / 2) 459 31. s1 = gx1^(1/2) 460 32. s2 = gx2^(1/2) 461 33. s3 = gx3^(1/2) 462 34. if l1 == 1: 463 35. Output (x1, s1) 464 36. if l2 == 1: 465 37. Output (x2, s2) 466 38. Output (x3, s3) 468 5.2.3. Simplified SWU Method 470 The following map2curve_simple_swu(alpha) implements the simplified 471 Shallue-Woestijne-Ulas algorithm from [SimpleSWU]. This algorithm 472 works for any curve over F_{p^n}, where p = 3 mod 4, including: 474 o P256 476 o ... 478 Given curve equation g(x) = x^3 + Ax + B, this algorithm works as 479 follows: 481 1. t = HashToBase(alpha) 482 2. alpha = (-B / A) * (1 + (1 / (t^4 + t^2))) 483 3. beta = -t^2 * alpha 484 4. If g(alpha) is square, output (alpha, sqrt(g(alpha))) 485 5. Output (beta, sqrt(g(beta))) 487 The following procedure implements this algorithm. It outputs a 488 point with affine coordinates. It requires knowledge of A and B, the 489 constants from the curve Weierstrass form. 491 map2curve_simple_swu(alpha) 493 Input: 495 alpha - value to be encoded, an octet string 497 Output: 499 (x, y) - a point in E 501 Steps: 503 1. t = HashToBase(alpha) 504 2. alpha = t^2 (mod p) 505 3. alpha = alpha * -1 (mod p) 506 4. right = alpha^2 + alpha (mod p) 507 5. right = right^(-1) (mod p) 508 6. right = right + 1 (mod p) 509 7. left = B * -1 (mod p) 510 8. left = left / A (mod p) 511 9. x2 = left * right (mod p) 512 10. x3 = alpha * x2 (mod p) 513 11. h2 = x2 ^ 3 (mod p) 514 12. i2 = x2 * A (mod p) 515 13. i2 = i2 + B (mod p) 516 14. h2 = h2 + i2 (mod p) 517 15. h3 = x3 ^ 3 (mod p) 518 16. i3 = x3 * A (mod p) 519 17. i3 = i3 + B (mod p) 520 18. h3 = h3 + i3 (mod p) 521 19. y1 = h2 ^ ((p + 1) / 4) (mod p) 522 20. y2 = h3 ^ ((p + 1) / 4) (mod p) 523 21. e = CTEQ(y1 ^ 2, h2) // Constant-time equality 524 22. x = CMOV(x2, x3, e) // If e = 1, choose x2, else choose x3 525 23. y = CMOV(y1, y2, e) // If e = 1, choose y1, else choose y2 526 24. Output (x, y) 528 5.2.4. Elligator2 Method 530 The following map2curve_elligator2(alpha) implements the Elligator2 531 method from [Elligator2]. This algorithm works for any curve with a 532 point of order 2 and j-invariant != 1728. Given curve equation y^2 = 533 x(x^2 + Ax + B), i.e., a Montgomery form with (0,0), a point of order 534 2, this algorithm works as shown below. (Note that any curve with a 535 point of order 2 is isomorphic to this representation.) 536 1. r = HashToBase(alpha) 537 2. Let u be a non-square value in Fp 538 3. v = -A/(1+ur^ 2) 539 4. e = Legendre(v^3+Av^2+Bv) 540 5.1. If r != 0, then 541 5.2. x = ev - (1 - e)A/2 542 5.3. y = -e*sqrt(x^3+Ax^2+x) 543 5.4. Else, x=0 and y=0 544 6. Output (x,y) 546 Here, e is the Legendre symbol defined as in Section 4. 548 The following procedure implements this algorithm. 550 map2curve_elligator2(alpha) 552 Input: 554 alpha - value to be encoded, an octet string 556 u - fixed non-square value in Fp. 558 Output: 560 (x, y) - a point in E 562 Steps: 564 1. r = HashToBase(alpha) 565 2. r = r^2 (mod p) 566 3. nu = r * u (mod p) 567 4. r = nu 568 5. r = r + 1 (mod p) 569 6. r = r^(-1) (mod p) 570 7. v = A * r (mod p) 571 8. v = v * -1 (mod p) // -A / (1 + ur^2) 572 9. v2 = v^2 (mod p) 573 10. v3 = v * v2 (mod p) 574 11. e = v3 + v (mod p) 575 12. v2 = v2 * A (mod p) 576 13. e = v2 + e (mod p) 577 14. e = e^((p - 1) / 2) // = Legendre(e) 578 15. nv = v * -1 (mod p) 579 16. v = CMOV(v, nv, e) // If e = 1, choose v, else choose nv 580 17. v2 = CMOV(0, A, e) // If e = 1, choose 0, else choose A 581 18. x = v - v2 (mod p) 582 19. y = -e*sqrt(x^3+Ax^2+Bx) 583 19. Output (x, y) 584 Elligator2 can be simplified with projective coordinates. 586 ((TODO: write this variant)) 588 5.3. Cost Comparison 590 The following table summarizes the cost of each map2curve variant. 591 We express this cost in terms of additions (A), multiplications (M), 592 squares (SQ), and square roots (SR). 594 ((TODO: finish this section)) 596 +----------------------+-------------------+ 597 | Algorithm | Cost (Operations) | 598 +----------------------+-------------------+ 599 | map2curve_icart | TODO | 600 | | | 601 | map2curve_swu | TODO | 602 | | | 603 | map2curve_simple_swu | TODO | 604 | | | 605 | map2curve_elligator2 | TODO | 606 +----------------------+-------------------+ 608 6. Random Oracles 610 6.1. Interface 612 The generic interface for deterministic encoding functions to 613 elliptic curves is as follows: 615 hash2curve(alpha) 617 where alpha is a message to encode on a curve. 619 6.2. General Construction (FFSTV13) 621 When applications need a Random Oracle (RO), they can be constructed 622 from deterministic encoding functions. In particular, let F : 623 {0,1}^* -> E be a deterministic encoding function onto curve E, and 624 let H0 and H1 be two hash functions modeled as random oracles that 625 map input messages to the base field of E, i.e., Z_q. Farashahi et 626 al. [FFSTV13] showed that the following mapping is indistinguishable 627 from a RO: 629 hash2curve(alpha) = F(H0(alpha)) + F(H1(alpha)) 630 This construction works for the Icart, SWU, and Simplfied SWU 631 encodings. 633 Here, H0 and H1 are constructed as follows: 635 H0(alpha) = HashToBase(alpha, 2) 636 H1(alpha) = HashToBase(alpha, 3) 638 7. Curve Transformations 640 Every elliptic curve can be converted to an equivalent curve in short 641 Weierstrass form ([BL07] Theorem 2.1), making SWU a generic algorithm 642 that can be used for all curves. Curves in either Edwards or Twisted 643 Edwards form can be transformed into equivalent curves in Montgomery 644 form [BL17] for use with Elligator2. [RFC7748] describes how to 645 convert between points on Curve25519 and Ed25519, and between 646 Curve448 and its Edwards equivalent, Goldilocks. 648 8. Ciphersuites 650 To provide concrete recommendations for algorithms we define a hash- 651 to-curve "ciphersuite" as a four-tuple containing: 653 o Destination Group (e.g. P256 or Curve25519) 655 o HashToBase algorithm 657 o HashToCurve algorithm (e.g. SSWU, Icart) 659 o (Optional) Transformation (e.g. FFSTV, cofactor clearing) 661 A ciphersuite defines an algorithm that takes an arbitrary octet 662 string and returns an element of the Destination Group defined in the 663 ciphersuite by applying HashToCurve and Transformation (if defined). 665 This document describes the following set of ciphersuites: * H2C- 666 P256-SHA256-SSWU- * H2C-P384-SHA512-Icart- * H2C- 667 Curve25519-SHA512-Elligator2-Clear * H2C- 668 Curve448-SHA512-Elligator2-Clear * H2C- 669 Curve25519-SHA512-Elligator2-FFSTV * H2C- 670 Curve448-SHA512-Elligator2-FFSTV 672 H2C-P256-SHA256-SWU- is defined as follows: 674 o The destination group is the set of points on the NIST P-256 675 elliptic curve, with curve parameters as specified in [DSS] 676 (Section D.1.2.3) and [RFC5114] (Section 2.6). 678 o HashToBase is defined as {#hashtobase} with the hash function 679 defined as SHA-256 as specified in [RFC6234], and p set to the 680 prime field used in P-256 (2^256 - 2^224 + 2^192 + 2^96 - 1). 682 o HashToCurve is defined to be {#sswu} with A and B taken from the 683 definition of P-256 (A=-3, B=4105836372515214212932612978004726840 684 9114441015993725554835256314039467401291). 686 H2C-P384-SHA512-Icart- is defined as follows: 688 o The destination group is the set of points on the NIST P-384 689 elliptic curve, with curve parameters as specified in [DSS] 690 (Section D.1.2.4) and [RFC5114] (Section 2.7). 692 o HashToBase is defined as {#hashtobase} with the hash function 693 defined as SHA-512 as specified in [RFC6234], and p set to the 694 prime field used in P-384 (2^384 - 2^128 - 2^96 + 2^32 - 1). 696 o HashToCurve is defined to be {#icart} with A and B taken from the 697 definition of P-384 (A=-3, B=2758019355995970587784901184038904809 698 305690585636156852142870730198868924130986086513626076488374510776 699 5439761230575). 701 H2C-Curve25519-SHA512-Elligator2-Clear is defined as follows: 703 o The destination group is the points on Curve25519, with curve 704 parameters as specified in [RFC7748] (Section 4.1). 706 o HashToBase is defined as {#hashtobase} with the hash function 707 defined as SHA-512 as specified in [RFC6234], and p set to the 708 prime field used in Curve25519 (2^255 - 19). 710 o HashToCurve is defined to be {#elligator2} with the curve function 711 defined to be the Montgomery form of Curve25519 (y^2 = x^3 + 712 486662x^2 + x) and u = 2. 714 o The final output is multiplied by the cofactor of Curve25519, 8. 716 H2C-Curve448-SHA512-Elligator2-Clear is defined as follows: 718 o The destination group is the points on Curve448, with curve 719 parameters as specified in [RFC7748] (Section 4.1). 721 o HashToBase is defined as {#hashtobase} with the hash function 722 defined as SHA-512 as specified in [RFC6234], and p set to the 723 prime field used in Curve448 (2^448 - 2^224 - 1). 725 o HashToCurve is defined to be {#elligator2} with the curve function 726 defined to be the Montgomery form of Curve448 (y^2 = x^3 + 727 156326x^2 + x) and u = -1. 729 o The final output is multiplied by the cofactor of Curve448, 4. 731 H2C-Curve25519-SHA512-Elligator2-FFSTV is defined as in H2C- 732 Curve25519-SHA-512-Elligator2-Clear except HashToCurve is defined to 733 be {#ffstv} where F is {#elligator2}. 735 H2C-Curve448-SHA512-Elligator2-FFSTV is defined as in H2C-Curve448- 736 SHA-512-Elligator2-Clear except HashToCurve is defined to be {#ffstv} 737 where F is {#elligator2}. 739 9. IANA Considerations 741 This document has no IANA actions. 743 10. Security Considerations 745 Each encoding function variant accepts arbitrary input and maps it to 746 a pseudorandom point on the curve. Points are close to 747 indistinguishable from randomly chosen elements on the curve. Not 748 all encoding functions are full-domain hashes. Elligator2, for 749 example, only maps strings to "about half of all curve points," 750 whereas Icart's method only covers about 5/8 of the points. 752 11. Acknowledgements 754 The authors would like to thank Adam Langley for this detailed 755 writeup up Elligator2 with Curve25519 [ElligatorAGL]. We also thank 756 Sean Devlin and Thomas Icart for feedback on earlier versions of this 757 document. 759 12. Contributors 761 o Sharon Goldberg 762 Boston University 763 goldbe@cs.bu.edu 765 13. Normative References 767 [BF01] "Identity-based encryption from the Weil pairing", n.d.. 769 [BL07] "Faster addition and doubling on elliptic curves", n.d., 770 . 772 [BL17] "Montgomery curves and the Montgomery ladder", n.d., 773 . 775 [BLS01] "Short signatures from the Weil pairing", n.d., 776 . 778 [BMP00] "Provably secure password-authenticated key exchange using 779 diffie-hellman", n.d.. 781 [DSS] National Institute of Standards and Technology, U.S. 782 Department of Commerce, "Digital Signature Standard, 783 version 4", NIST FIPS PUB 186-4, 2013. 785 [ECOPRF] "EC-OPRF - Oblivious Pseudorandom Functions using Elliptic 786 Curves", n.d.. 788 [Elligator2] 789 "Elligator -- Elliptic-curve points indistinguishable from 790 uniform random strings", n.d., . 793 [ElligatorAGL] 794 "Implementing Elligator for Curve25519", n.d., 795 . 798 [FFSTV13] "Indifferentiable deterministic hashing to elliptic and 799 hyperelliptic curves", n.d.. 801 [FIPS-186-4] 802 "Digital Signature Standard (DSS), FIPS PUB 186-4, July 803 2013", n.d., 804 . 807 [hacspec] "hacspec", n.d., . 810 [Icart09] "How to Hash into Elliptic Curves", n.d., 811 . 813 [Jablon96] 814 "Strong password-only authenticated key exchange", n.d.. 816 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 817 Requirement Levels", BCP 14, RFC 2119, 818 DOI 10.17487/RFC2119, March 1997, . 821 [RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman 822 Groups for Use with IETF Standards", RFC 5114, 823 DOI 10.17487/RFC5114, January 2008, . 826 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 827 Key Derivation Function (HKDF)", RFC 5869, 828 DOI 10.17487/RFC5869, May 2010, . 831 [RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms 832 (SHA and SHA-based HMAC and HKDF)", RFC 6234, 833 DOI 10.17487/RFC6234, May 2011, . 836 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 837 for Security", RFC 7748, DOI 10.17487/RFC7748, January 838 2016, . 840 [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, 841 "PKCS #1: RSA Cryptography Specifications Version 2.2", 842 RFC 8017, DOI 10.17487/RFC8017, November 2016, 843 . 845 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 846 Signature Algorithm (EdDSA)", RFC 8032, 847 DOI 10.17487/RFC8032, January 2017, . 850 [SECG1] "SEC 1 -- Elliptic Curve Cryptography", n.d., 851 . 853 [SimpleSWU] 854 "Efficient Indifferentiable Hashing into Ordinary Elliptic 855 Curves", n.d.. 857 [SW06] "Construction of rational points on elliptic curves over 858 finite fields", n.d.. 860 [SWU07] "Rational points on certain hyperelliptic curves over 861 finite fields", n.d., . 863 Appendix A. Related Work 865 In this chapter, we give a background to some common methods to 866 encode or hash to the curve, motivated by the similar exposition in 867 [Icart09]. Understanding of this material is not required in order 868 to choose a suitable encoding function - we defer this to Section 3 - 869 the background covered here can work as a template for analyzing 870 encoding functions not found in this document, and as a guide for 871 further research into the topics covered. 873 A.1. Probabilistic Encoding 875 As mentioned in Section 2, as a rule of thumb, for every x in GF(p), 876 there is approximately a 1/2 chance that there exist a corresponding 877 y value such that (x, y) is on the curve E. 879 This motivates the construction of the MapToGroup method described by 880 Boneh et al. [BLS01]. For an input message m, a counter i, and a 881 standard hash function H : {0, 1}^* -> GF(p) x {0, 1}, one computes 882 (x, b) = H(i || m), where i || m denotes concatenation of the two 883 values. Next, test to see whether there exists a corresponding y 884 value such that (x, y) is on the curve, returning (x, y) if 885 successful, where b determines whether to take +/- y. If there does 886 not exist such a y, then increment i and repeat. A maximum counter 887 value is set to I, and since each iteration succeeds with probability 888 approximately 1/2, this process fails with probability 2^-I. (See 889 Appendix B for a more detailed description of this algorithm.) 891 Although MapToGroup describes a method to hash to the curve, it can 892 also be adapted to a simple encoding mechanism. For a bitstring of 893 length strictly less than log2(p), one can make use of the spare bits 894 in order to encode the counter value. Allocating more space for the 895 counter increases the expansion, but reduces the failure probability. 897 Since the running time of the MapToGroup algorithm depends on m, this 898 algorithm is NOT safe for cases sensitive to timing side channel 899 attacks. Deterministic algorithms are needed in such cases where 900 failures are undesirable. 902 A.2. Naive Encoding 904 A naive solution includes computing H(m)*G as map2curve(m), where H 905 is a standard hash function H : {0, 1}^* -> GF(p), and G is a 906 generator of the curve. Although efficient, this solution is 907 unsuitable for constructing a random oracle onto E, since the 908 discrete logarithm with respect to G is known. For example, given y1 909 = map2curve(m1) and y2 = map2curve(m2) for any m1 and m2, it must be 910 true that y2 = H(m2) / H(m1) * map2curve(m1). This relationship 911 would not hold (with overwhelming probability) for truly random 912 values y1 and y2. This causes catastrophic failure in many cases. 913 However, one exception is found in SPEKE [Jablon96], which constructs 914 a base for a Diffie-Hellman key exchange by hashing the password to a 915 curve point. Notably the use of a hash function is purely for 916 encoding an arbitrary length string to a curve point, and does not 917 need to be a random oracle. 919 A.3. Deterministic Encoding 921 Shallue, Woestijne, and Ulas [SW06] first introduced a deterministic 922 algorithm that maps elements in F_{q} to a curve in time O(log^4 q), 923 where q = p^n for some prime p, and time O(log^3 q) when q = 3 mod 4. 924 Icart introduced yet another deterministic algorithm which maps F_{q} 925 to any EC where q = 2 mod 3 in time O(log^3 q) [Icart09]. Elligator 926 (2) [Elligator2] is yet another deterministic algorithm for any odd- 927 characteristic EC that has a point of order 2. Elligator2 can be 928 applied to Curve25519 and Curve448, which are both CFRG-recommended 929 curves [RFC7748]. 931 However, an important caveat to all of the above deterministic 932 encoding functions, is that none of them map injectively to the 933 entire curve, but rather some fraction of the points. This makes 934 them unable to use to directly construct a random oracle on the 935 curve. 937 Brier et al. [SimpleSWU] proposed a couple of solutions to this 938 problem, The first applies solely to Icart's method described above, 939 by computing F(H0(m)) + F(H1(m)) for two distinct hash functions H0, 940 H1. The second uses a generator G, and computes F(H0(m)) + H1(m)*G. 941 Later, Farashahi et al. [FFSTV13] showed the generality of the 942 F(H0(m)) + F(H1(m)) method, as well as the applicability to 943 hyperelliptic curves (not covered here). 945 A.4. Supersingular Curves 947 For supersingular curves, for every y in GF(p) (with p>3), there 948 exists a value x such that (x, y) is on the curve E. Hence we can 949 construct a bijection F : GF(p) -> E (ignoring the point at 950 infinity). This is the case for [BF01], but is not common. 952 A.5. Twisted Variants 954 We can also consider curves which have twisted variants, E^d. For 955 such curves, for any x in GF(p), there exists y in GF(p) such that 956 (x, y) is either a point on E or E^d. Hence one can construct a 957 bijection F : GF(p) x {0,1} -> E ∪ E^d, where the extra bit is 958 needed to choose the sign of the point. This can be particularly 959 useful for constructions which only need the x-coordinate of the 960 point. For example, x-only scalar multiplication can be computed on 961 Montgomery curves. In this case, there is no need for an encoding 962 function, since the output of F in GF(p) is sufficient to define a 963 point on one of E or E^d. 965 Appendix B. Try-and-Increment Method 967 In cases where constant time execution is not required, the so-called 968 try-and-increment method may be appropriate. As discussion in 969 Section 1, this variant works by hashing input m using a standard 970 hash function ("Hash"), e.g., SHA256, and then checking to see if the 971 resulting point E(m, f(m)), for curve function f, belongs on E. This 972 is detailed below. 974 1. ctr = 0 975 2. h = "INVALID" 976 3. While h is "INVALID" or h is EC point at infinity: 977 4.1 CTR = I2OSP(ctr, 4) 978 4.2 ctr = ctr + 1 979 4.3 attempted_hash = Hash(m || CTR) 980 4.4 h = RS2ECP(attempted_hash) 981 4.5 If h is not "INVALID" and cofactor > 1, set h = h * cofactor 982 5. Output h 984 I2OSP is a function that converts a nonnegative integer to octet 985 string as defined in Section 4.1 of [RFC8017], and RS2ECP(h) = 986 OS2ECP(0x02 || h), where OS2ECP is specified in Section 2.3.4 of 987 [SECG1], which converts an input string into an EC point. 989 Appendix C. Sample Code 991 This section contains reference implementations for each map2curve 992 variant built using [hacspec]. 994 C.1. Icart Method 996 The following hacspec program implements map2curve_icart(alpha) for 997 P-384. 999 from hacspec.speclib import * 1001 prime = 2**384 - 2**128 - 2**96 + 2**32 - 1 1003 felem_t = refine(nat, lambda x: x < prime) 1004 affine_t = tuple2(felem_t, felem_t) 1006 @typechecked 1007 def to_felem(x: nat_t) -> felem_t: 1008 return felem_t(nat(x % prime)) 1010 @typechecked 1011 def fadd(x: felem_t, y: felem_t) -> felem_t: 1013 return to_felem(x + y) 1015 @typechecked 1016 def fsub(x: felem_t, y: felem_t) -> felem_t: 1017 return to_felem(x - y) 1019 @typechecked 1020 def fmul(x: felem_t, y: felem_t) -> felem_t: 1021 return to_felem(x * y) 1023 @typechecked 1024 def fsqr(x: felem_t) -> felem_t: 1025 return to_felem(x * x) 1027 @typechecked 1028 def fexp(x: felem_t, n: nat_t) -> felem_t: 1029 return to_felem(pow(x, n, prime)) 1031 @typechecked 1032 def finv(x: felem_t) -> felem_t: 1033 return to_felem(pow(x, prime-2, prime)) 1035 a384 = to_felem(prime - 3) 1036 b384 = to_felem(27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575) 1038 @typechecked 1039 def map2p384(u:felem_t) -> affine_t: 1040 v = fmul(fsub(fmul(to_felem(3), a384), fexp(u, 4)), finv(fmul(to_felem(6), u))) 1041 u2 = fmul(fexp(u, 6), finv(to_felem(27))) 1042 x = fsub(fsqr(v), b384) 1043 x = fsub(x, u2) 1044 x = fexp(x, (2 * prime - 1) // 3) 1045 x = fadd(x, fmul(fsqr(u), finv(to_felem(3)))) 1046 y = fadd(fmul(u, x), v) 1047 return (x, y) 1049 C.2. Shallue-Woestijne-Ulas Method 1051 The following hacspec program implements map2curve_swu(alpha) for 1052 P-256. 1054 from p256 import * 1055 from hacspec.speclib import * 1057 a256 = to_felem(prime - 3) 1058 b256 = to_felem(41058363725152142129326129780047268409114441015993725554835256314039467401291) 1060 @typechecked 1061 def f_p256(x:felem_t) -> felem_t: 1062 return fadd(fexp(x, 3), fadd(fmul(to_felem(a256), x), to_felem(b256))) 1064 @typechecked 1065 def x1(t:felem_t, u:felem_t) -> felem_t: 1066 return u 1068 @typechecked 1069 def x2(t:felem_t, u:felem_t) -> felem_t: 1070 coefficient = fmul(to_felem(-b256), finv(to_felem(a256))) 1071 t2 = fsqr(t) 1072 t4 = fsqr(t2) 1073 gu = f_p256(u) 1074 gu2 = fsqr(gu) 1075 denom = fadd(fmul(t4, gu2), fmul(t2, gu)) 1076 return fmul(coefficient, fadd(to_felem(1), finv(denom))) 1078 @typechecked 1079 def x3(t:felem_t, u:felem_t) -> felem_t: 1080 return fmul(fsqr(t), fmul(f_p256(u), x2(t, u))) 1082 @typechecked 1083 def map2p256(t:felem_t) -> felem_t: 1084 u = fadd(t, to_felem(1)) 1085 x1v = x1(t, u) 1086 x2v = x2(t, u) 1087 x3v = x3(t, u) 1089 exp = to_felem((prime - 1) // 2) 1090 e1 = fexp(f_p256(x1v), exp) 1091 e2 = fexp(f_p256(x2v), exp) 1093 if e1 == 1: 1094 return x1v 1095 elif e2 == 1: 1096 return x2v 1097 else: 1098 return x3v 1100 C.3. Simplified SWU Method 1102 The following hacspec program implements map2curve_simple_swu(alpha) 1103 for P-256. 1105 from p256 import * 1106 from hacspec.speclib import * 1108 a256 = to_felem(prime - 3) 1109 b256 = to_felem(41058363725152142129326129780047268409114441015993725554835256314039467401291) 1111 def f_p256(x:felem_t) -> felem_t: 1112 return fadd(fexp(x, 3), fadd(fmul(to_felem(a256), x), to_felem(b256))) 1114 def map2p256(t:felem_t) -> affine_t: 1115 alpha = to_felem(-(fsqr(t))) 1116 frac = finv((fadd(fsqr(alpha), alpha))) 1117 coefficient = fmul(to_felem(-b256), finv(to_felem(a256))) 1118 x2 = fmul(coefficient, fadd(to_felem(1), frac)) 1120 x3 = fmul(alpha, x2) 1121 h2 = fadd(fexp(x2, 3), fadd(fmul(a256, x2), b256)) 1122 h3 = fadd(fexp(x3, 3), fadd(fmul(a256, x3), b256)) 1124 exp = fmul(fadd(to_felem(prime), to_felem(-1)), finv(to_felem(2))) 1125 e = fexp(h2, exp) 1127 exp = to_felem((prime + 1) // 4) 1128 if e == 1: 1129 return (x2, fexp(f_p256(x2), exp)) 1130 else: 1131 return (x3, fexp(f_p256(x3), exp)) 1133 C.4. Elligator2 Method 1135 The following hacspec program implements map2curve_elligator2(alpha) 1136 for Curve25519. 1138 from curve25519 import * 1139 from hacspec.speclib import * 1141 a25519 = to_felem(486662) 1142 b25519 = to_felem(1) 1143 u25519 = to_felem(2) 1145 @typechecked 1146 def f_25519(x:felem_t) -> felem_t: 1147 return fadd(fmul(x, fsqr(x)), fadd(fmul(a25519, fsqr(x)), x)) 1149 @typechecked 1150 def map2curve25519(r:felem_t) -> felem_t: 1151 d = fsub(to_felem(p25519), fmul(a25519, finv(fadd(to_felem(1), fmul(u25519, fsqr(r)))))) 1152 power = nat((p25519 - 1) // 2) 1153 e = fexp(f_25519(d), power) 1154 x = 0 1155 if e != 1: 1156 x = fsub(to_felem(-d), to_felem(a25519)) 1157 else: 1158 x = d 1160 return x 1162 C.5. HashToBase 1164 The following procedure implements HashToBase. 1166 HashToBase(x, i) 1168 Parameters: 1170 H - cryptographic hash function to use 1171 hbits - number of bits output by H 1172 p - order of the base field Fp 1173 label - context label for domain separation 1175 Preconditions: 1177 floor(log2(p)) + 1 >= hbits 1179 Input: 1181 x - value to be hashed, an octet string 1182 i - hash call index, a non-negative integer 1184 Output: 1186 y - a value in the field Fp 1188 Steps: 1190 1. t1 = H("h2c" || label || I2OSP(i, 4) || x) 1191 2. t2 = OS2IP(t1) 1192 3. y = t2 (mod p) 1193 4. Output y 1195 where I2OSP, OS2IP [RFC8017] are used to convert an octet string to 1196 and from a non-negative integer, and a || b denotes concatenation of 1197 a and b. 1199 C.5.1. Considerations 1201 Performance: HashToBase requires hashing the entire input x. In some 1202 algorithms/ciphersuite combinations, HashToBase is called multiple 1203 times. For large inputs, implementers can therefore consider hashing 1204 x before calling HashToBase. I.e. HashToBase(H'(x)). 1206 Most algorithms assume that HashToBase maps its input to the base 1207 field uniformly. In practice, there will be inherent biases. For 1208 example, taking H as SHA256, over the finite field used by Curve25519 1209 we have p = 2^255 - 19, and thus when reducing from 255 bits, the 1210 values of 0 .. 19 will be twice as likely to occur. This is a 1211 standard problem in generating uniformly distributed integers from a 1212 bitstring. In this example, the resulting bias is negligible, but 1213 for others this bias can be significant. 1215 To address this, our HashToBase algorithm greedily takes as many bits 1216 as possible before reducing mod p, in order to smooth out this bias. 1217 This is preferable to an iterated procedure, such as rejection 1218 sampling, since this can be hard to reliably implement in constant 1219 time. 1221 Authors' Addresses 1223 Sam Scott 1224 Cornell Tech 1225 2 West Loop Rd 1226 New York, New York 10044 1227 United States of America 1229 Email: sam.scott@cornell.edu 1231 Nick Sullivan 1232 Cloudflare 1233 101 Townsend St 1234 San Francisco 1235 United States of America 1237 Email: nick@cloudflare.com 1239 Christopher A. Wood 1240 Apple Inc. 1241 One Apple Park Way 1242 Cupertino, California 95014 1243 United States of America 1245 Email: cawood@apple.com