idnits 2.17.1 draft-irtf-cfrg-hash-to-curve-05.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 14 instances of too long lines in the document, the longest one being 9 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 seems to use 'NOT RECOMMENDED' as an RFC 2119 keyword, but does not include the phrase in its RFC 2119 key words list. -- The document date (November 02, 2019) is 1636 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 ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 692 -- Looks like a reference, but probably isn't: '37' on line 692 == Unused Reference: 'BLAKE2X' is defined on line 2210, but no explicit reference was found in the text ** Obsolete normative reference: RFC 2898 (Obsoleted by RFC 8018) Summary: 2 errors (**), 0 flaws (~~), 3 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group A. Faz-Hernandez 3 Internet-Draft Cloudflare 4 Intended status: Informational S. Scott 5 Expires: May 5, 2020 Cornell Tech 6 N. Sullivan 7 Cloudflare 8 R. Wahby 9 Stanford University 10 C. Wood 11 Apple Inc. 12 November 02, 2019 14 Hashing to Elliptic Curves 15 draft-irtf-cfrg-hash-to-curve-05 17 Abstract 19 This document specifies a number of algorithms that may be used to 20 encode or hash an arbitrary string to a point on an elliptic curve. 22 Status of This Memo 24 This Internet-Draft is submitted in full conformance with the 25 provisions of BCP 78 and BCP 79. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF). Note that other groups may also distribute 29 working documents as Internet-Drafts. The list of current Internet- 30 Drafts is at https://datatracker.ietf.org/drafts/current/. 32 Internet-Drafts are draft documents valid for a maximum of six months 33 and may be updated, replaced, or obsoleted by other documents at any 34 time. It is inappropriate to use Internet-Drafts as reference 35 material or to cite them other than as "work in progress." 37 This Internet-Draft will expire on May 5, 2020. 39 Copyright Notice 41 Copyright (c) 2019 IETF Trust and the persons identified as the 42 document authors. All rights reserved. 44 This document is subject to BCP 78 and the IETF Trust's Legal 45 Provisions Relating to IETF Documents 46 (https://trustee.ietf.org/license-info) in effect on the date of 47 publication of this document. Please review these documents 48 carefully, as they describe your rights and restrictions with respect 49 to this document. Code Components extracted from this document must 50 include Simplified BSD License text as described in Section 4.e of 51 the Trust Legal Provisions and are provided without warranty as 52 described in the Simplified BSD License. 54 Table of Contents 56 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 57 1.1. How to use this document . . . . . . . . . . . . . . . . 4 58 1.2. Requirements . . . . . . . . . . . . . . . . . . . . . . 5 59 2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 5 60 2.1. Elliptic curves . . . . . . . . . . . . . . . . . . . . . 5 61 2.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 6 62 2.2.1. Mappings . . . . . . . . . . . . . . . . . . . . . . 6 63 2.2.2. Encodings . . . . . . . . . . . . . . . . . . . . . . 7 64 2.2.3. Random oracle encodings . . . . . . . . . . . . . . . 7 65 2.2.4. Serialization . . . . . . . . . . . . . . . . . . . . 8 66 2.2.5. Domain separation . . . . . . . . . . . . . . . . . . 8 67 3. Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 68 3.1. Domain separation requirements . . . . . . . . . . . . . 10 69 4. Utility Functions . . . . . . . . . . . . . . . . . . . . . . 11 70 4.1. sgn0 variants . . . . . . . . . . . . . . . . . . . . . . 12 71 4.1.1. Big endian variant . . . . . . . . . . . . . . . . . 13 72 4.1.2. Little endian variant . . . . . . . . . . . . . . . . 14 73 5. Hashing to a Finite Field . . . . . . . . . . . . . . . . . . 14 74 5.1. Security considerations . . . . . . . . . . . . . . . . . 15 75 5.2. Performance considerations . . . . . . . . . . . . . . . 16 76 5.3. Implementation . . . . . . . . . . . . . . . . . . . . . 16 77 5.4. Alternative hash_to_base functions . . . . . . . . . . . 17 78 6. Deterministic Mappings . . . . . . . . . . . . . . . . . . . 18 79 6.1. Choosing a mapping function . . . . . . . . . . . . . . . 18 80 6.2. Interface . . . . . . . . . . . . . . . . . . . . . . . . 19 81 6.3. Notation . . . . . . . . . . . . . . . . . . . . . . . . 19 82 6.4. Sign of the resulting point . . . . . . . . . . . . . . . 20 83 6.5. Exceptional cases . . . . . . . . . . . . . . . . . . . . 20 84 6.6. Mappings for Weierstrass curves . . . . . . . . . . . . . 20 85 6.6.1. Shallue-van de Woestijne Method . . . . . . . . . . . 20 86 6.6.2. Simplified Shallue-van de Woestijne-Ulas Method . . . 24 87 6.6.3. Simplified SWU for AB == 0 . . . . . . . . . . . . . 25 88 6.7. Mappings for Montgomery curves . . . . . . . . . . . . . 27 89 6.7.1. Elligator 2 Method . . . . . . . . . . . . . . . . . 27 90 6.8. Mappings for Twisted Edwards curves . . . . . . . . . . . 29 91 6.8.1. Rational maps from Montgomery to twisted Edwards 92 curves . . . . . . . . . . . . . . . . . . . . . . . 29 93 6.8.2. Elligator 2 Method . . . . . . . . . . . . . . . . . 31 94 6.9. Mappings for Supersingular curves . . . . . . . . . . . . 32 95 6.9.1. Boneh-Franklin Method . . . . . . . . . . . . . . . . 32 96 6.9.2. Elligator 2, A == 0 Method . . . . . . . . . . . . . 32 98 7. Clearing the cofactor . . . . . . . . . . . . . . . . . . . . 34 99 8. Suites for Hashing . . . . . . . . . . . . . . . . . . . . . 35 100 8.1. Defining a new hash-to-curve suite . . . . . . . . . . . 36 101 8.2. Suite ID naming conventions . . . . . . . . . . . . . . . 36 102 8.3. Suites for NIST P-256 . . . . . . . . . . . . . . . . . . 38 103 8.4. Suites for NIST P-384 . . . . . . . . . . . . . . . . . . 38 104 8.5. Suites for NIST P-521 . . . . . . . . . . . . . . . . . . 39 105 8.6. Suites for curve25519 and edwards25519 . . . . . . . . . 40 106 8.7. Suites for curve448 and edwards448 . . . . . . . . . . . 41 107 8.8. Suites for secp256k1 . . . . . . . . . . . . . . . . . . 42 108 8.9. Suites for BLS12-381 . . . . . . . . . . . . . . . . . . 44 109 8.9.1. BLS12-381 G1 . . . . . . . . . . . . . . . . . . . . 44 110 8.9.2. BLS12-381 G2 . . . . . . . . . . . . . . . . . . . . 45 111 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 46 112 10. Security Considerations . . . . . . . . . . . . . . . . . . . 46 113 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 47 114 12. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 47 115 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 47 116 13.1. Normative References . . . . . . . . . . . . . . . . . . 47 117 13.2. Informative References . . . . . . . . . . . . . . . . . 48 118 Appendix A. Related Work . . . . . . . . . . . . . . . . . . . . 54 119 Appendix B. Rational maps . . . . . . . . . . . . . . . . . . . 56 120 B.1. Twisted Edwards to Weierstrass and Montgomery curves . . 56 121 B.2. Montgomery to Weierstrass curves . . . . . . . . . . . . 57 122 Appendix C. Isogeny maps for Suites . . . . . . . . . . . . . . 58 123 C.1. 3-isogeny map for secp256k1 . . . . . . . . . . . . . . . 58 124 C.2. 11-isogeny map for BLS12-381 G1 . . . . . . . . . . . . . 59 125 C.3. 3-isogeny map for BLS12-381 G2 . . . . . . . . . . . . . 63 126 Appendix D. Sample Code . . . . . . . . . . . . . . . . . . . . 65 127 D.1. Interface and projective coordinate systems . . . . . . . 65 128 D.2. Simplified SWU for p = 3 (mod 4) . . . . . . . . . . . . 66 129 D.3. curve25519 (Elligator 2) . . . . . . . . . . . . . . . . 68 130 D.4. edwards25519 (Elligator 2) . . . . . . . . . . . . . . . 69 131 D.5. curve448 (Elligator 2) . . . . . . . . . . . . . . . . . 69 132 D.6. edwards448 (Elligator 2) . . . . . . . . . . . . . . . . 70 133 Appendix E. Scripts for parameter generation . . . . . . . . . . 72 134 E.1. Finding Z for the Shallue and van de Woestijne map . . . 72 135 E.2. Finding Z for Simplified SWU . . . . . . . . . . . . . . 72 136 E.3. Finding Z for Elligator 2 . . . . . . . . . . . . . . . . 73 137 Appendix F. sqrt functions . . . . . . . . . . . . . . . . . . . 73 138 F.1. p = 3 (mod 4) . . . . . . . . . . . . . . . . . . . . . . 74 139 F.2. p = 5 (mod 8) . . . . . . . . . . . . . . . . . . . . . . 74 140 F.3. p = 9 (mod 16) . . . . . . . . . . . . . . . . . . . . . 74 141 F.4. Constant-time Tonelli-Shanks algorithm . . . . . . . . . 75 142 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 77 144 1. Introduction 146 Many cryptographic protocols require a procedure that encodes an 147 arbitrary input, e.g., a password, to a point on an elliptic curve. 148 This procedure is known as hashing to an elliptic curve. Prominent 149 examples of cryptosystems that hash to elliptic curves include Simple 150 Password Exponential Key Exchange [J96], Password Authenticated Key 151 Exchange [BMP00], Identity-Based Encryption [BF01] and Boneh-Lynn- 152 Shacham signatures [BLS01]. 154 Unfortunately for implementors, the precise hash function that is 155 suitable for a given scheme is not necessarily included in the 156 description of the protocol. Compounding this problem is the need to 157 pick a suitable curve for the specific protocol. 159 This document aims to bridge this gap by providing a thorough set of 160 recommended algorithms for a range of curve types. Each algorithm 161 conforms to a common interface: it takes as input an arbitrary-length 162 bit string and produces as output a point on an elliptic curve. We 163 provide implementation details for each algorithm, describe the 164 security rationale behind each recommendation, and give guidance for 165 elliptic curves that are not explicitly covered. 167 This document does not cover rejection sampling methods, sometimes 168 known as "try-and-increment" or "hunt-and-peck," because the goal is 169 to describe algorithms that can plausibly be made constant time. Use 170 of these rejection methods is NOT RECOMMENDED, because they have been 171 a perennial cause of side-channel vulnerabilities. 173 1.1. How to use this document 175 This document is intended for use by both implementors and protocol 176 designers. 178 For implementors, the necessary and sufficient level of specification 179 is a hash-to-curve suite, which fixes all of the parameters listed in 180 Section 8, plus a domain separation tag (Section 3.1). Starting from 181 working operations on the target elliptic curve and its base field, a 182 hash-to-curve suite requires implementing the specified encoding 183 function (Section 3), its constituent subroutines (Section 5, 184 Section 6, Section 7), and a few utility functions (Section 4). 186 Correspondingly, designers specifying a protocol that requires 187 hashing to an elliptic curve should either choose an existing hash- 188 to-curve suite or specify a new one (see Section 8.1). In addition, 189 designers should choose a domain separation tag following the 190 guidelines in Section 3.1. 192 1.2. Requirements 194 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 195 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 196 document are to be interpreted as described in [RFC2119]. 198 2. Background 200 2.1. Elliptic curves 202 The following is a brief definition of elliptic curves, with an 203 emphasis on important parameters and their relation to hashing to 204 curves. For further reference on elliptic curves, consult 205 [CFADLNV05] or [W08]. 207 Let F be the finite field GF(q) of prime characteristic p. In most 208 cases F is a prime field, so q = p. Otherwise, F is a field 209 extension, so q = p^m for an integer m > 1. This document writes 210 elements of field extensions in a primitive element or polynomial 211 basis, i.e., as a vector of m elements of GF(p) written in ascending 212 order by degree. The entries of this vector are indexed in ascending 213 order starting from 1, i.e., x = (x_1, x_2, ..., x_m). For example, 214 if q = p^2 and the primitive element basis is (1, i), then x = (a, b) 215 corresponds to the element a + b * i, where x_1 = a and x_2 = b. 217 An elliptic curve E is specified by an equation in two variables and 218 a finite field F. An elliptic curve equation takes one of several 219 standard forms, including (but not limited to) Weierstrass, 220 Montgomery, and Edwards. 222 The curve E induces an algebraic group whose elements are those 223 points with coordinates (x, y) satisfying the curve equation, and 224 where x and y are elements of F. This group has order n, meaning 225 that there are n distinct points. This document uses additive 226 notation for the elliptic curve group operation. 228 For security reasons, groups of prime order MUST be used. Elliptic 229 curves induce subgroups of prime order. Let G be a subgroup of the 230 curve of prime order r, where n = h * r. In this equation, h is an 231 integer called the cofactor. An algorithm that takes as input an 232 arbitrary point on the curve E and produces as output a point in the 233 subgroup G of E is said to "clear the cofactor." Such algorithms are 234 discussed in Section 7. 236 Certain hash-to-curve algorithms restrict the form of the curve 237 equation, the characteristic of the field, and/or the parameters of 238 the curve. For each algorithm presented, this document lists the 239 relevant restrictions. 241 Summary of quantities: 243 +--------+----------------------------+-----------------------------+ 244 | Symbol | Meaning | Relevance | 245 +--------+----------------------------+-----------------------------+ 246 | F,q,p | Finite field F of | For prime fields, q = p; | 247 | | characteristic p and #F = | otherwise, q = p^m and m>1. | 248 | | q = p^m. | | 249 | | | | 250 | E | Elliptic curve. | E is specified by an | 251 | | | equation and a field F. | 252 | | | | 253 | n | Number of points on the | n = h * r, for h and r | 254 | | elliptic curve E. | defined below. | 255 | | | | 256 | G | A subgroup of the elliptic | Destination group to which | 257 | | curve. | bit strings are encoded. | 258 | | | | 259 | r | Order of G. | This number MUST be prime. | 260 | | | | 261 | h | Cofactor, h >= 1. | An integer satisfying n = h | 262 | | | * r. | 263 +--------+----------------------------+-----------------------------+ 265 2.2. Terminology 267 In this section, we define important terms used in the rest of this 268 document. 270 2.2.1. Mappings 272 A mapping is a deterministic function from an element of the field F 273 to a point on an elliptic curve E defined over F. 275 In general, the set of all points that a mapping can produce over all 276 possible inputs may be only a subset of the points on an elliptic 277 curve (i.e., the mapping may not be surjective). In addition, a 278 mapping may output the same point for two or more distinct inputs 279 (i.e., the mapping may not be injective). For example, consider a 280 mapping from F to an elliptic curve having n points: if the number of 281 elements of F is not equal to n, then this mapping cannot be 282 bijective (i.e., both injective and surjective) since it is defined 283 to be deterministic. 285 Mappings may also be invertible, meaning that there is an efficient 286 algorithm that, for any point P output by the mapping, outputs an x 287 in F such that applying the mapping to x outputs P. Some of the 288 mappings given in Section 6 are invertible, but this document does 289 not discuss inversion algorithms. 291 2.2.2. Encodings 293 Encodings are closely related to mappings. Like a mapping, an 294 encoding is a function that outputs a point on an elliptic curve. In 295 contrast to a mapping, however, the input to an encoding is an 296 arbitrary bit string. Encodings can be deterministic or 297 probabilistic. Deterministic encodings are preferred for security, 298 because probabilistic ones can leak information through side 299 channels. 301 This document constructs deterministic encodings by composing a hash 302 function H with a deterministic mapping. In particular, H takes as 303 input an arbitrary bit string and outputs an element of F. The 304 deterministic mapping takes that element as input and outputs a point 305 on an elliptic curve E defined over F. Since the hash function H 306 takes arbitrary bit strings as inputs, it cannot be injective: the 307 set of inputs is larger than the set of outputs, so there must be 308 distinct inputs that give the same output (i.e., there must be 309 collisions). Thus, any encoding built from H is also not injective. 311 Like mappings, encodings may be invertible, meaning that there is an 312 efficient algorithm that, for any point P output by the encoding, 313 outputs a bit string s such that applying the encoding to s outputs 314 P. The hash function used by all encodings specified in this 315 document (Section 5) is not invertible; thus, the encodings are also 316 not invertible. 318 2.2.3. Random oracle encodings 320 Two different types of encodings are possible: nonuniform encodings, 321 whose output distribution is not uniformly random, and random oracle 322 encodings, whose output distribution is indistinguishable from 323 uniformly random. Some protocols require a random oracle for 324 security, while others can be securely instantiated with a nonuniform 325 encoding. When the required encoding is not clear, applications 326 SHOULD use a random oracle. 328 Care is required when constructing a random oracle from a mapping 329 function. A simple but insecure approach is to use the output of a 330 cryptographically secure hash function H as the input to the mapping. 331 Because in general the mapping is not surjective, the output of this 332 construction is distinguishable from uniformly random, i.e., it does 333 not behave like a random oracle. 335 Brier et al. [BCIMRT10] describe two generic constructions whose 336 outputs are indifferentiable from a random oracle when the 337 constructions are instantiated with appropriate hash functions 338 modeled as random oracles. Farashahi et al. [FFSTV13] and Tibouchi 339 and Kim [TK17] refine the analysis of one of these constructions. 340 That construction is described in Section 3. 342 2.2.4. Serialization 344 A procedure related to encoding is the conversion of an elliptic 345 curve point to a bit string. This is called serialization, and is 346 typically used for compactly storing or transmitting points. The 347 reverse operation, deserialization, converts a bit string to an 348 elliptic curve point. For example, [SEC1] and [p1363a] give standard 349 methods for serialization and deserialization. 351 Deserialization is different from encoding in that only certain 352 strings (namely, those output by the serialization procedure) can be 353 deserialized. In contrast, this document is concerned with encodings 354 from arbitrary bit strings to elliptic curve points. This document 355 does not cover serialization or deserialization. 357 2.2.5. Domain separation 359 Cryptographic protocols that use random oracles are often analyzed 360 under the assumption that random oracles answer only queries 361 generated by that protocol. In practice, this assumption does not 362 hold if two protocols query the same random oracle. Concretely, 363 consider protocols P1 and P2 that query random oracle R: if P1 and P2 364 both query R on the same value x, the security analysis of one or 365 both protocols may be invalidated. 367 A common approach to addressing this issue is called domain 368 separation, which allows a single random oracle to simulate multiple, 369 independent oracles. This is effected by ensuring that each 370 simulated oracle sees queries that are distinct from those seen by 371 all other simulated oracles. For example, to simulate two oracles R1 372 and R2 given a single oracle R, one might define 374 R1(x) := R("R1" || x) 375 R2(x) := R("R2" || x) 377 In this example, "R1" and "R2" are called domain separation tags; 378 they ensure that queries to R1 and R2 cannot result in identical 379 queries to R. Thus, it is safe to treat R1 and R2 as independent 380 oracles. 382 3. Roadmap 384 This section presents a general framework for encoding bit strings to 385 points on an elliptic curve. To construct these encodings, we rely 386 on three basic functions: 388 o The function hash_to_base, {0, 1}^* x {0, 1, 2} -> F, hashes 389 arbitrary-length bit strings to elements of a finite field; its 390 implementation is defined in Section 5. 392 o The function map_to_curve, F -> E, calculates a point on the 393 elliptic curve E from an element of the finite field F over which 394 E is defined. Section 6 describes mappings for a range of curve 395 families. 397 o The function clear_cofactor, E -> G, sends any point on the curve 398 E to the subgroup G of E. Section 7 describes methods to perform 399 this operation. 401 We describe two high-level encoding functions (Section 2.2.2). 402 Although these functions have the same interface, the distributions 403 of their outputs are different. 405 o Nonuniform encoding (encode_to_curve). This function encodes bit 406 strings to points in G. The distribution of the output is not 407 uniformly random in G. 409 encode_to_curve(alpha) 411 Input: alpha, an arbitrary-length bit string. 412 Output: P, a point in G. 414 Steps: 415 1. u = hash_to_base(alpha, 2) 416 2. Q = map_to_curve(u) 417 3. P = clear_cofactor(Q) 418 4. return P 420 o Random oracle encoding (hash_to_curve). This function encodes bit 421 strings to points in G. This function is suitable for 422 applications requiring a random oracle returning points in G, 423 provided that map_to_curve is "well distributed" ([FFSTV13], Def. 424 1). All of the map_to_curve functions defined in Section 6 meet 425 this requirement. 427 hash_to_curve(alpha) 429 Input: alpha, an arbitrary-length bit string. 430 Output: P, a point in G. 432 Steps: 433 1. u0 = hash_to_base(alpha, 0) 434 2. u1 = hash_to_base(alpha, 1) 435 3. Q0 = map_to_curve(u0) 436 4. Q1 = map_to_curve(u1) 437 5. R = Q0 + Q1 // Point addition 438 6. P = clear_cofactor(R) 439 7. return P 441 Instances of these functions are given in Section 8, which defines a 442 list of suites that specify a full set of parameters matching 443 elliptic curves and algorithms. 445 3.1. Domain separation requirements 447 All uses of the encoding functions defined in this document MUST 448 include domain separation (Section 2.2.5) to avoid interfering with 449 other uses of similar functionality. 451 Protocols that instantiate multiple, independent hash functions based 452 on either hash_to_curve or encode_to_curve MUST enforce domain 453 separation between those hash functions. This requirement applies 454 both in the case of multiple hashes to the same curve and in the case 455 of multiple hashes to different curves. (This is because the 456 hash_to_base primitive (Section 5) requires domain separation to 457 guarantee independent outputs.) 459 Domain separation is enforced with a domain separation tag (DST), 460 which is an octet string. Care is required when selecting and using 461 a domain separation tag. The following requirements apply: 463 1. Tags MUST be supplied as the DST parameter to hash_to_base, as 464 described in Section 5. 466 2. Tags MUST begin with a fixed protocol identification string. 467 This identification string should be unique to the protocol. 469 3. Tags SHOULD include a protocol version number. 471 4. For protocols that define multiple ciphersuites, each 472 ciphersuite's tag MUST be different. For this purpose, it is 473 RECOMMENDED to include a ciphersuite identifier in each tag. 475 5. For protocols that use multiple encodings, either to the same 476 curve or to different curves, each encoding MUST use a different 477 tag. For this purpose, it is RECOMMENDED to include the 478 encoding's Suite ID (Section 8) in the domain separation tag. 479 For independent encodings based on the same suite, each tag 480 should also include a distinct identifier, e.g., "ENC1" and 481 "ENC2". 483 As an example, consider a fictional protocol named Quux that defines 484 several different ciphersuites. A reasonable choice of tag is "QUUX- 485 V-CS", where and are two-digit numbers indicating 486 the version and ciphersuite, respectively. 488 As another example, consider a fictional protocol named Baz that 489 requires two independent random oracles, where one oracle outputs 490 points on the curve E1 and the other outputs points on the curve E2. 491 Reasonable choices of tags for the E1 and E2 oracles are "BAZ-V- 492 CS-E1" and "BAZ-V-CS-E2", respectively, where and 493 are as described above. 495 4. Utility Functions 497 Algorithms in this document make use of utility functions described 498 below. 500 For security reasons, all field operations, comparisons, and 501 assignments MUST be implemented in constant time (i.e., execution 502 time MUST NOT depend on the values of the inputs), and without 503 branching. Guidance on implementing these low-level operations in 504 constant time is beyond the scope of this document. 506 o CMOV(a, b, c): If c is False, CMOV returns a, otherwise it returns 507 b. To prevent against timing attacks, this operation must run in 508 constant time, without revealing the value of c. Commonly, 509 implementations assume that the selector c is 1 for True or 0 for 510 False. In this case, given a bit string C, the desired selector c 511 can be computed by OR-ing all bits of C together. The resulting 512 selector will be either 0 if all bits of C are zero, or 1 if at 513 least one bit of C is 1. 515 o is_square(x): This function returns True whenever the value x is a 516 square in the field F. Due to Euler's criterion, this function 517 can be calculated in constant time as 519 is_square(x) := { True, if x^((q - 1) / 2) is 0 or 1 in F; 520 { False, otherwise. 522 o sqrt(x): The sqrt operation is a multi-valued function, i.e. there 523 exist two roots of x in the field F whenever x is square. To 524 maintain compatibility across implementations while allowing 525 implementors leeway for optimizations, this document does not 526 require sqrt() to return a particular value. Instead, as 527 explained in Section 6.4, any higher-level function that computes 528 square roots also specifies how to determine the sign of the 529 result. 531 The preferred way of computing square roots is to fix a 532 deterministic algorithm particular to F. We give several 533 algorithms in Appendix F. Regardless of the method chosen, the 534 sqrt function should be implemented in a way that resists timing 535 side channels, i.e., in constant time. 537 o sgn0(x): This function returns either +1 or -1 indicating the 538 "sign" of x, where sgn0(x) == -1 just when x is "negative". In 539 other words, this function always considers 0 to be positive. 540 This function may be implemented in multiple ways; Section 4.1 541 defines two variants. Throughout the document, sgn0 is used 542 generically to mean either of these variants. Each suite in 543 Section 8 specifies the sgn0 variant to be used. 545 o abs(x): The absolute value of x is defined in terms of sgn0 in the 546 natural way, namely, abs(x) := sgn0(x) * x. 548 o inv0(x): This function returns the multiplicative inverse of x in 549 F, extended to all of F by fixing inv0(0) == 0. To implement inv0 550 in constant time, compute inv0(x) := x^(q - 2). Notice on input 551 0, the output is 0 as required. 553 o I2OSP and OS2IP: These functions are used to convert an octet 554 string to and from a non-negative integer as described in 555 [RFC8017]. 557 o a || b: denotes the concatenation of bit strings a and b. 559 4.1. sgn0 variants 561 This section defines two ways of determining the "sign" of an element 562 of F. The variant that should be used is a matter of convention. 563 Other sgn0 variants are possible, but the two given below cover 564 commonly used notions of sign. 566 It is RECOMMENDED to select the variant that matches the point 567 decompression method of the target curve. In particular, since point 568 decompression requires computing a square root and then choosing the 569 sign of the resulting point, all decompression methods specify, 570 implicitly or explicitly, a method for determining the sign of an 571 element of F. It is convenient for hash-to-curve and decompression 572 to agree on a notion of sign, since this may permit simpler 573 implementations. 575 See Section 2.1 for a discussion of representing elements of field 576 extensions as vectors; this representation is used in both of the 577 sgn0 variants below. 579 Note that any valid sgn0 function for field extensions must iterate 580 over the entire vector representation of the input element. To see 581 why, imagine a function sgn0* that ignores the final entry in its 582 input vector, and consider a field element x = (0, x_2). Since sgn0* 583 ignores x_2, sgn0*(x) == sgn0*(-x), which is incorrect when x_2 != 0. 584 The same argument applies to all entries of any x, establishing the 585 claim. 587 4.1.1. Big endian variant 589 The following sgn0 variant is defined such that sgn0_be(x) = -1 just 590 when the big-endian encoding of x is lexically greater than the 591 encoding of -x. 593 This variant SHOULD be used when points on the target elliptic curve 594 are serialized using the SORT compression method given in IEEE 595 1363a-2004 [p1363a], Section 5.5.6.1.2, and other similar methods. 597 sgn0_be(x) 599 Parameters: 600 - F, a finite field of characteristic p and order q = p^m. 601 - p, the characteristic of F (see immediately above). 602 - m, the extension degree of F, m >= 1 (see immediately above). 604 Input: x, an element of F. 605 Output: -1 or 1 (an integer). 607 Notation: x_i is the i^th element of the vector representation of x. 609 Steps: 610 1. sign = 0 611 2. for i in (m, m - 1, ..., 1): 612 3. sign_i = CMOV(1, -1, x_i > ((p - 1) / 2)) 613 4. sign_i = CMOV(sign_i, 0, x_i == 0) 614 5. sign = CMOV(sign, sign_i, sign == 0) 615 6. return CMOV(sign, 1, sign == 0) // Regard x == 0 as positive 617 4.1.2. Little endian variant 619 The following sgn0 variant is defined such that sgn0_le(x) = -1 just 620 when x != 0 and the parity of the least significant nonzero entry of 621 the vector representation of x is 1. 623 This variant SHOULD be used when points on the target elliptic curve 624 are serialized using any of the following methods: 626 o the LSB compression method given in IEEE 1363a-2004 [p1363a], 627 Section 5.5.6.1.1, 629 o the method given in [SEC1] Section 2.3.3, or 631 o the method given in ANSI X9.62-1998 [x9.62], Section 4.2.1. 633 This variant is also compatible with the compression method specified 634 for the Ed25519 and Ed448 elliptic curves [RFC8032]. 636 sgn0_le(x) 638 Parameters: 639 - F, a finite field of characteristic p and order q = p^m. 640 - p, the characteristic of F (see immediately above). 641 - m, the extension degree of F, m >= 1 (see immediately above). 643 Input: x, an element of F. 644 Output: -1 or 1 (an integer). 646 Notation: x_i is the i^th element of the vector representation of x. 648 Steps: 649 1. sign = 0 650 2. for i in (1, 2, ..., m): 651 3. sign_i = CMOV(1, -1, x_i mod 2 == 1) 652 4. sign_i = CMOV(sign_i, 0, x_i == 0) 653 5. sign = CMOV(sign, sign_i, sign == 0) 654 6. return CMOV(sign, 1, sign == 0) // regard x == 0 as positive 656 5. Hashing to a Finite Field 658 The hash_to_base function hashes a string msg of any length into an 659 element of a field F. This function is parametrized by the field F 660 (Section 2.1) and by H, a cryptographic hash function that outputs b 661 bits. 663 Implementors MUST NOT use rejection sampling to generate a uniformly 664 random element of F. The reason is that these procedures are 665 difficult to implement in constant time, and later well-meaning 666 "optimizations" may silently render an implementation non-constant- 667 time. 669 5.1. Security considerations 671 For security, hash_to_base should be collision resistant and its 672 output distribution should be uniform over F. To this end, 673 hash_to_base requires a cryptographic hash function H which satisfies 674 the following properties: 676 1. The number of bits output by H should be b >= 2 * k for 677 sufficient collision resistance, where k is the target security 678 level in bits. (This is needed for a birthday bound of 679 approximately 2^(-k).) 681 2. H is modeled as a random oracle, so care should be taken when 682 instantiating it. Hash functions in the SHA-2 [FIPS180-4] and 683 SHA-3 [FIPS202] families are typical and RECOMMENDED choices. 685 For example, for 128-bit security, b >= 256 bits; in this case, 686 SHA256 would be an appropriate choice for H. 688 Ensuring that the hash_to_base output is a uniform random element of 689 F requires care, even when H is modeled as a random oracle. For 690 example, if H is SHA256 and F is a field of characteristic p = 2^255 691 - 19, then the result of reducing H(msg) (a 256-bit integer) modulo p 692 is slightly more likely to be in [0, 37] than if the value were 693 selected uniformly at random. In this example the bias is 694 negligible, but in general it can be significant. 696 To control bias, the input msg should be hashed to an integer 697 comprising at least ceil(log2(p)) + k bits; reducing this integer 698 modulo p gives bias at most 2^-k, which is a safe choice for a 699 cryptosystem with k-bit security. To obtain such an integer, HKDF 700 [RFC5869] is used to expand the input msg to a L-byte string, where L 701 = ceil((ceil(log2(p)) + k) / 8); this string is then interpreted as 702 an integer via OS2IP [RFC8017]. For example, for p a 255-bit prime 703 and k = 128-bit security, L = ceil((255 + 128) / 8) = 48 bytes. 705 Finally, hash_to_base appends one zero byte to msg in the invocation 706 of HKDF-Extract. This ensures that the use of HKDF in hash_to_base 707 is indifferentiable from a random oracle (see [LBB19], Lemma 8 and 708 [DRST12], Theorems 4.3 and 4.4). (In particular, this approach works 709 because it ensures that the final byte of each HMAC invocation in 710 HKDF-Extract and HKDF-Expand is distinct.) 711 Section 3.1 discusses requirements for domain separation and 712 recommendations for choosing domain separation tags. The 713 hash_to_curve function takes such a tag as a parameter, DST; this is 714 the REQUIRED method for applying domain separation. 716 Section 5.3 details the hash_to_base procedure. 718 5.2. Performance considerations 720 The hash_to_base function uses HKDF-Extract to combine the input msg 721 and domain separation tag DST into a short digest, which is then 722 passed to HKDF-Expand [RFC5869]. For short messages, this entails at 723 most two extra invocations of H, which is a negligible overhead in 724 the context of hashing to elliptic curves. 726 A related issue is that the random oracle construction described in 727 Section 3 requires evaluating two independent hash functions H0 and 728 H1 on msg. One way to instantiate independent hashes is to append a 729 counter to the value being hashed, e.g., H(msg || 0) and H(msg || 1). 730 If msg is long, however, this is either inefficient (because it 731 entails hashing msg twice) or requires non-black-box use of H (e.g., 732 partial evaluation). 734 To sidestep both of these issues, hash_to_base takes a second 735 argument, ctr, which it passes to HKDF-Expand. This means that two 736 invocations of hash_to_base on the same msg with different ctr values 737 both start with identical invocations of HKDF-Extract. This is an 738 improvement because it allows sharing one evaluation of HKDF-Extract 739 among multiple invocations of hash_to_base, i.e., by factoring out 740 the common computation. 742 5.3. Implementation 744 The following procedure implements hash_to_base. 746 hash_to_base(msg, ctr) 748 Parameters: 749 - DST, a domain separation tag (see discussion above). 750 - H, a cryptographic hash function. 751 - F, a finite field of characteristic p and order q = p^m. 752 - p, the characteristic of F (see immediately above). 753 - m, the extension degree of F, m >= 1 (see immediately above). 754 - L = ceil((ceil(log2(p)) + k) / 8), where k is the security 755 parameter of the cryptosystem (e.g., k = 128). 756 - HKDF-Extract and HKDF-Expand are as defined in RFC5869, 757 instantiated with the hash function H. 759 Inputs: 760 - msg is the message to hash. 761 - ctr is 0, 1, or 2. 762 This is used to efficiently create independent 763 instances of hash_to_base (see discussion above). 765 Output: 766 - u, an element in F. 768 Steps: 769 1. msg_prime = HKDF-Extract(DST, msg || I2OSP(0, 1)) 770 2. info_pfx = "H2C" || I2OSP(ctr, 1) // "H2C" is a 3-byte ASCII string 771 3. for i in (1, ..., m): 772 4. info = info_pfx || I2OSP(i, 1) 773 5. t = HKDF-Expand(msg_prime, info, L) 774 6. e_i = OS2IP(t) mod p 775 7. u = (e_1, ..., e_m) 776 8. return u 778 5.4. Alternative hash_to_base functions 780 The hash_to_base function is suitable for use with a wide range of 781 hash functions, including SHA-2 [FIPS180-4], SHA-3 [FIPS202], BLAKE2 782 [RFC7693], and others. In some cases, however, implementors may wish 783 to replace the HKDF-based function defined in this section with one 784 built on a different pseudorandom function. This section briefly 785 describes the REQUIRED way of doing so. 787 The security considerations of Section 5.1 continue to apply. In 788 particular, an alternative hash_to_base function: 790 o MUST give collision resistance commensurate with the security 791 level of the target elliptic curve. 793 o MUST be built on a pseudorandom function that is designed for use 794 in applications requiring cryptographic randomness. 796 o MUST NOT use rejection sampling. 798 o MUST output an element of F whose statistical distance from 799 uniform is commensurate with the security level of the target 800 elliptic curve. It is RECOMMENDED to follow the guidelines for 801 controlling bias in Section 5.1. 803 o MUST give independent output values for distinct (msg, ctr) 804 inputs. 806 o MUST support domain separation via a supplied domain separation 807 tag (DST). Care is required when implementing domain separation: 808 this document assumes that instantiating hash_to_base with 809 distinct DSTs yields independent hash functions. 811 The efficiency considerations of Section 5.2 should also be followed. 812 In particular, it SHOULD be possible to hash one msg with multiple 813 ctr values without requiring multiple passes over msg. 815 Finally, the Suite ID value MUST be modified to indicate that an 816 alternative hash_to_base function is being used. Section 8.2 gives 817 details. 819 6. Deterministic Mappings 821 The mappings in this section are suitable for constructing either 822 nonuniform or random oracle encodings using the constructions of 823 Section 3. Certain mappings restrict the form of the curve or its 824 parameters. For each mapping presented, this document lists the 825 relevant restrictions. 827 Note that mappings in this section are not interchangeable: different 828 mappings will almost certainly output different points when evaluated 829 on the same input. 831 6.1. Choosing a mapping function 833 This section gives brief guidelines on choosing a mapping function 834 for a given elliptic curve. Note that the suites given in Section 8 835 are recommended mappings for the respective curves. 837 If the target elliptic curve is a supersingular curve supported by 838 either the Boneh-Franklin method (Section 6.9.1) or the Elligator 2 839 method for A == 0 (Section 6.9.2), that mapping is the recommended 840 one. 842 Otherwise, if the target elliptic curve is a Montgomery curve 843 (Section 6.7), the Elligator 2 method (Section 6.7.1) is recommended. 844 Similarly, if the target elliptic curve is a twisted Edwards curve 845 (Section 6.8), the twisted Edwards Elligator 2 method (Section 6.8.2) 846 is recommended. 848 The remaining cases are Weierstrass curves. For curves supported by 849 the Simplified SWU method (Section 6.6.2), that mapping is the 850 recommended one. Otherwise, the Simplified SWU method for AB == 0 851 (Section 6.6.3) is recommended if the goal is best performance, while 852 the Shallue-van de Woestijne method (Section 6.6.1) is recommended if 853 the goal is simplicity of implementation. (The reason for this 854 distinction is that the Simplified SWU method for AB == 0 requires 855 implementing an isogeny map in addition to the mapping function, 856 while the Shallue-van de Woestijne method does not.) 858 The Shallue-van de Woestijne method (Section 6.6.1) works with any 859 curve, and may be used in cases where a generic mapping is required. 860 Note, however, that this mapping is almost always more 861 computationally expensive than the curve-specific recommendations 862 above. 864 6.2. Interface 866 The generic interface shared by all mappings in this section is as 867 follows: 869 (x, y) = map_to_curve(u) 871 The input u and outputs x and y are elements of the field F. The 872 coordinates (x, y) specify a point on an elliptic curve defined over 873 F. Note that the point (x, y) is not a uniformly random point. If 874 uniformity is required for security, the random oracle construction 875 of Section 3 MUST be used instead. 877 6.3. Notation 879 As a rough style guide the following convention is used: 881 o All arithmetic operations are performed over a field F, unless 882 explicitly stated otherwise. 884 o u: the input to the mapping function. This is an element of F 885 produced by the hash_to_base function. 887 o (x, y): are the affine coordinates of the point output by the 888 mapping. Indexed values are used when the algorithm calculates 889 some candidate values. 891 o t1, t2, ...: are reusable temporary variables. For notable 892 variables, distinct names are used easing the debugging process 893 when correlating with test vectors. 895 o c1, c2, ...: are constant values, which can be computed in 896 advance. 898 6.4. Sign of the resulting point 900 In general, elliptic curves have equations of the form y^2 = g(x). 901 Most of the mappings in this section first identify an x such that 902 g(x) is square, then take a square root to find y. Since there are 903 two square roots when g(x) != 0, this results in an ambiguity 904 regarding the sign of y. 906 To resolve this ambiguity, the mappings in this section specify the 907 sign of the y-coordinate in terms of the input to the mapping 908 function. Two main reasons support this approach. First, this 909 covers elliptic curves over any field in a uniform way, and second, 910 it gives implementors leeway to optimize their square-root 911 implementations. 913 6.5. Exceptional cases 915 Mappings may have have exceptional cases, i.e., inputs u on which the 916 mapping is undefined. These cases must be handled carefully, 917 especially for constant-time implementations. 919 For each mapping in this section, we discuss the exceptional cases 920 and show how to handle them in constant time. Note that all 921 implementations SHOULD use inv0 (Section 4) to compute multiplicative 922 inverses, to avoid exceptional cases that result from attempting to 923 compute the inverse of 0. 925 6.6. Mappings for Weierstrass curves 927 The following mappings apply to elliptic curves defined by the 928 equation E: y^2 = g(x) = x^3 + A * x + B, where 4 * A^3 + 27 * B^2 != 929 0. 931 6.6.1. Shallue-van de Woestijne Method 933 Shallue and van de Woestijne [SW06] describe a mapping that applies 934 to essentially any elliptic curve. (Note, however, that this mapping 935 is more expensive to evaluate than the other mappings in this 936 document.) 937 The parameterization given below is for Weierstrass curves; its 938 derivation is detailed in [W19]. This parameterization also works 939 for Montgomery (Section 6.7) and twisted Edwards (Section 6.8) curves 940 via the rational maps given in Appendix B: first evaluate the 941 Shallue-van de Woestijne mapping to an equivalent Weierstrass curve, 942 then map that point to the target Montgomery or twisted Edwards curve 943 using the corresponding rational map. 945 Preconditions: A Weierstrass curve y^2 = x^3 + A * x + B over F = 946 GF(p^m) where p > 5 and odd. 948 Constants: 950 o A and B, the parameter of the Weierstrass curve. 952 o Z, an element of F meeting the below criteria. Appendix E.1 gives 953 a Sage [SAGE] script that outputs the RECOMMENDED Z. 955 1. g(Z) != 0 in F. 957 2. -(3 * Z^2 + 4 * A) / (4 * g(Z)) != 0 in F. 959 3. -(3 * Z^2 + 4 * A) / (4 * g(Z)) is square in F. 961 4. At least one of g(Z) and g(-Z / 2) is square in F. 963 Sign of y: Inputs u and -u give the same x-coordinate. Thus, we set 964 sgn0(y) == sgn0(u). 966 Exceptions: The exceptional cases for u occur when (1 + u^2 * g(Z)) * 967 (1 - u^2 * g(Z)) == 0. The restrictions on Z given above ensure that 968 implementations that use inv0 to invert this product are exception 969 free. 971 Operations: 973 1. t1 = u^2 * g(Z) 974 2. t2 = 1 + t1 975 3. t1 = 1 - t1 976 4. t3 = inv0(t1 * t2) 977 5. t4 = u * t1 * t3 * sqrt(-g(Z) * (3 * Z^2 + 4 * A)) 978 6. x1 = -Z / 2 - t4 979 7. x2 = -Z / 2 + t4 980 8. t5 = 2 * t2^2 * t3 * sqrt(-g(Z) / (3 * Z^2 + 4 * A)) 981 9. x3 = Z + t5^2 982 10. If is_square(g(x1)), set x = x1 and y = sqrt(g(x1)) 983 11. Else If is_square(g(x2)), set x = x2 and y = sqrt(g(x2)) 984 12. Else set x = x3 and y = sqrt(g(x3)) 985 13. If sgn0(u) != sgn0(y), set y = -y 986 14. return (x, y) 988 6.6.1.1. Implementation 990 The following procedure implements the Shallue and van de Woestijne 991 method in a straight-line fashion. 993 map_to_curve_svdw(u) 994 Input: u, an element of F. 995 Output: (x, y), a point on E. 997 Constants: 998 1. c1 = g(Z) 999 2. c2 = -Z / 2 1000 3. c3 = sqrt(-g(Z) * (3 * Z^2 + 4 * A)) // sgn0(c3) MUST equal 1 1001 4. c4 = -4 * g(Z) / (3 * Z^2 + 4 * A) 1003 Steps: 1004 1. t1 = u^2 1005 2. t1 = t1 * c1 1006 3. t2 = 1 + t1 1007 4. t1 = 1 - t1 1008 5. t3 = t1 * t2 1009 6. t3 = inv0(t3) 1010 7. t4 = u * t1 1011 8. t4 = t4 * t3 1012 9. t4 = t4 * c3 1013 10. x1 = c2 - t4 1014 11. gx1 = x1^2 1015 12. gx1 = gx1 + A 1016 13. gx1 = gx1 * x1 1017 14. gx1 = gx1 + B 1018 15. e1 = is_square(gx1) 1019 16. x2 = c2 + t4 1020 17. gx2 = x2^2 1021 18. gx2 = gx2 + A 1022 19. gx2 = gx2 * x2 1023 20. gx2 = gx2 + B 1024 21. e2 = is_square(gx2) AND NOT e1 // Avoid short-circuit logic ops 1025 22. x3 = t2^2 1026 23. x3 = x3 * t3 1027 24. x3 = x3^2 1028 25. x3 = x3 * c4 1029 26. x3 = x3 + Z 1030 27. x = CMOV(x3, x1, e1) // x = x1 if gx1 is square, else x = x3 1031 28. x = CMOV(x, x2, e2) // x = x2 if gx2 is square and gx1 is not 1032 29. gx = x^2 1033 30. gx = gx + A 1034 31. gx = gx * x 1035 32. gx = gx + B 1036 33. y = sqrt(gx) 1037 34. e3 = sgn0(u) == sgn0(y) 1038 35. y = CMOV(-y, y, e3) // Select correct sign of y 1039 36. return (x, y) 1040 6.6.2. Simplified Shallue-van de Woestijne-Ulas Method 1042 The function map_to_curve_simple_swu(u) implements a simplification 1043 of the Shallue-van de Woestijne-Ulas mapping [U07] described by Brier 1044 et al. [BCIMRT10], which they call the "simplified SWU" map. Wahby 1045 and Boneh [WB19] generalize this mapping to curves over fields of odd 1046 characteristic p > 3. 1048 Preconditions: A Weierstrass curve y^2 = x^3 + A * x + B over F = 1049 GF(p^m) where p > 5 and odd, A != 0, and B != 0. 1051 Constants: 1053 o A and B, the parameters of the Weierstrass curve. 1055 o Z, an element of F meeting the below criteria. Appendix E.2 gives 1056 a Sage [SAGE] script that outputs the RECOMMENDED Z. The criteria 1057 are: 1059 1. Z is non-square in F, 1061 2. Z != -1 in F, 1063 3. the polynomial g(x) - Z is irreducible over F, and 1065 4. g(B / (Z * A)) is square in F. 1067 Sign of y: Inputs u and -u give the same x-coordinate. Thus, we set 1068 sgn0(y) == sgn0(u). 1070 Exceptions: The exceptional cases are values of u such that Z^2 * u^4 1071 + Z * u^2 == 0. This includes u == 0, and may include other values 1072 depending on Z. Implementations must detect this case and set x1 = B 1073 / (Z * A), which guarantees that g(x1) is square by the condition on 1074 Z given above. 1076 Operations: 1078 1. t1 = inv0(Z^2 * u^4 + Z * u^2) 1079 2. x1 = (-B / A) * (1 + t1) 1080 3. If t1 == 0, set x1 = B / (Z * A) 1081 4. gx1 = x1^3 + A * x1 + B 1082 5. x2 = Z * u^2 * x1 1083 6. gx2 = x2^3 + A * x2 + B 1084 7. If is_square(gx1), set x = x1 and y = sqrt(gx1) 1085 8. Else set x = x2 and y = sqrt(gx2) 1086 9. If sgn0(u) != sgn0(y), set y = -y 1087 10. return (x, y) 1089 6.6.2.1. Implementation 1091 The following procedure implements the simplified SWU mapping in a 1092 straight-line fashion. Appendix D gives an optimized straight-line 1093 procedure for P-256 [FIPS186-4]. For more information on optimizing 1094 this mapping, see [WB19] Section 4 or the example code found at 1095 [hash2curve-repo]. 1097 map_to_curve_simple_swu(u) 1098 Input: u, an element of F. 1099 Output: (x, y), a point on E. 1101 Constants: 1102 1. c1 = -B / A 1103 2. c2 = -1 / Z 1105 Steps: 1106 1. t1 = Z * u^2 1107 2. t2 = t1^2 1108 3. x1 = t1 + t2 1109 4. x1 = inv0(x1) 1110 5. e1 = x1 == 0 1111 6. x1 = x1 + 1 1112 7. x1 = CMOV(x1, c2, e1) // If (t1 + t2) == 0, set x1 = -1 / Z 1113 8. x1 = x1 * c1 // x1 = (-B / A) * (1 + (1 / (Z^2 * u^4 + Z * u^2))) 1114 9. gx1 = x1^2 1115 10. gx1 = gx1 + A 1116 11. gx1 = gx1 * x1 1117 12. gx1 = gx1 + B // gx1 = g(x1) = x1^3 + A * x1 + B 1118 13. x2 = t1 * x1 // x2 = Z * u^2 * x1 1119 14. t2 = t1 * t2 1120 15. gx2 = gx1 * t2 // gx2 = (Z * u^2)^3 * gx1 1121 16. e2 = is_square(gx1) 1122 17. x = CMOV(x2, x1, e2) // If is_square(gx1), x = x1, else x = x2 1123 18. y2 = CMOV(gx2, gx1, e2) // If is_square(gx1), y2 = gx1, else y2 = gx2 1124 19. y = sqrt(y2) 1125 20. e3 = sgn0(u) == sgn0(y) // Fix sign of y 1126 21. y = CMOV(-y, y, e3) 1127 22. return (x, y) 1129 6.6.3. Simplified SWU for AB == 0 1131 Wahby and Boneh [WB19] show how to adapt the simplified SWU mapping 1132 to Weierstrass curves having A == 0 or B == 0, which the mapping of 1133 Section 6.6.2 does not support. (The case A == B == 0 is excluded 1134 because y^2 = x^3 is not an elliptic curve.) 1135 This method applies to curves like secp256k1 [SEC2] and to pairing- 1136 friendly curves in the Barreto-Lynn-Scott [BLS03], Barreto-Naehrig 1137 [BN05], and other families. 1139 This method requires finding another elliptic curve 1141 E': y^2 = g'(x) = x^3 + A' * x + B' 1143 that is isogenous to E and has A' != 0 and B' != 0. (One might do 1144 this, for example, using [SAGE]; for details, see [WB19], 1145 Appendix A.) This isogeny defines a map iso_map(x', y') that takes 1146 as input a point on E' and produces as output a point on E. 1148 Once E' and iso_map are identified, this mapping works as follows: on 1149 input u, first apply the simplified SWU mapping to get a point on E', 1150 then apply the isogeny map to that point to get a point on E. 1152 Note that iso_map is a group homomorphism, meaning that point 1153 addition commutes with iso_map. Thus, when using this mapping in the 1154 hash_to_curve construction of Section 3, one can effect a small 1155 optimization by first mapping u0 and u1 to E', adding the resulting 1156 points on E', and then applying iso_map to the sum. This gives the 1157 same result while requiring only one evaluation of iso_map. 1159 Preconditions: An elliptic curve E' with A' != 0 and B' != 0 that is 1160 isogenous to the target curve E with isogeny map iso_map(x, y) from 1161 E' to E. 1163 Helper functions: 1165 o map_to_curve_simple_swu is the mapping of Section 6.6.2 to E' 1167 o iso_map is the isogeny map from E' to E 1169 Sign of y: for this map, the sign is determined by 1170 map_to_curve_simple_swu. No further sign adjustments are necessary. 1172 Exceptions: map_to_curve_simple_swu handles its exceptional cases. 1173 Exceptional cases of iso_map MUST return the identity point on E. 1175 Operations: 1177 1. (x', y') = map_to_curve_simple_swu(u) // (x', y') is on E' 1178 2. (x, y) = iso_map(x', y') // (x, y) is on E 1179 3. return (x, y) 1181 See [hash2curve-repo] or [WB19], Section 4.3 for details on 1182 implementing the isogeny map. 1184 6.7. Mappings for Montgomery curves 1186 The mapping defined in Section 6.7.1 implements Elligator 2 [BHKL13] 1187 for curves defined by the Weierstrass equation y^2 = x^3 + A * x^2 + 1188 B * x. 1190 Such a Weierstrass curve is related to the Montgomery curve B' * t^2 1191 = s^3 + A' * s^2 + s by the following change of variables: 1193 o A = A' / B' 1195 o B = 1 / B'^2 1197 o x = s / B' 1199 o y = t / B' 1201 The Elligator 2 mapping given below returns a point (x, y) on the 1202 Weierstrass curve defined above. This point can be converted to a 1203 point (s, t) on the original Montgomery curve by computing 1205 o s = B' * x 1207 o t = B' * y 1209 Note that when B and B' are equal to 1, the above two curve equations 1210 are identical and no conversion is necessary. This is the case, for 1211 example, for Curve25519 and Curve448 [RFC7748]. 1213 6.7.1. Elligator 2 Method 1215 Preconditions: A Weierstrass curve y^2 = x^3 + A * x^2 + B * x where 1216 A != 0, B != 0, and A^2 - 4 * B is non-zero and non-square in F. 1218 Constants: 1220 o A and B, the parameters of the elliptic curve. 1222 o Z, a non-square element of F. Appendix E.3 gives a Sage [SAGE] 1223 script that outputs the RECOMMENDED Z. 1225 Sign of y: Inputs u and -u give the same x-coordinate. Thus, we set 1226 sgn0(y) == sgn0(u). 1228 Exceptions: The exceptional case is Z * u^2 == -1, i.e., 1 + Z * u^2 1229 == 0. Implementations must detect this case and set x1 = -A. Note 1230 that this can only happen when q = 3 (mod 4). 1232 Operations: 1234 1. x1 = -A * inv0(1 + Z * u^2) 1235 2. If x1 == 0, set x1 = -A. 1236 3. gx1 = x1^3 + A * x1^2 + B * x1 1237 4. x2 = -x1 - A 1238 5. gx2 = x2^3 + A * x2^2 + B * x2 1239 6. If is_square(gx1), set x = x1 and y = sqrt(gx1) 1240 7. Else set x = x2 and y = sqrt(gx2) 1241 8. If sgn0(u) != sgn0(y), set y = -y 1242 9. return (x, y) 1244 6.7.1.1. Implementation 1246 The following procedure implements Elligator 2 in a straight-line 1247 fashion. Appendix D gives optimized straight-line procedures for 1248 curve25519 and curve448 [RFC7748]. 1250 map_to_curve_elligator2(u) 1251 Input: u, an element of F. 1252 Output: (x, y), a point on E. 1254 Steps: 1255 1. t1 = u^2 1256 2. t1 = Z * t1 // Z * u^2 1257 3. e1 = t1 == -1 // exceptional case: Z * u^2 == -1 1258 4. t1 = CMOV(t1, 0, e1) // if t1 == -1, set t1 = 0 1259 5. x1 = t1 + 1 1260 6. x1 = inv0(x1) 1261 7. x1 = -A * x1 // x1 = -A / (1 + Z * u^2) 1262 8. gx1 = x1 + A 1263 9. gx1 = gx1 * x1 1264 10. gx1 = gx1 + B 1265 11. gx1 = gx1 * x1 // gx1 = x1^3 + A * x1^2 + B * x1 1266 12. x2 = -x1 - A 1267 13. gx2 = t1 * gx1 1268 14. e2 = is_square(gx1) 1269 15. x = CMOV(x2, x1, e2) // If is_square(gx1), x = x1, else x = x2 1270 16. y2 = CMOV(gx2, gx1, e2) // If is_square(gx1), y2 = gx1, else y2 = gx2 1271 17. y = sqrt(y2) 1272 18. e3 = sgn0(u) == sgn0(y) // Fix sign of y 1273 19. y = CMOV(-y, y, e3) 1274 20. return (x, y) 1275 6.8. Mappings for Twisted Edwards curves 1277 Twisted Edwards curves (a class of curves that includes Edwards 1278 curves) are given by the equation a * v^2 + w^2 = 1 + d * v^2 * w^2, 1279 with a != 0, d != 0, and a != d [BBJLP08]. 1281 These curves are closely related to Montgomery curves (Section 6.7): 1282 every twisted Edwards curve is birationally equivalent to a 1283 Montgomery curve ([BBJLP08], Theorem 3.2). This equivalence yields 1284 an efficient way of hashing to a twisted Edwards curve: first, hash 1285 to the equivalent Montgomery curve, then transform the result into a 1286 point on the twisted Edwards curve via a rational map. This method 1287 of hashing to a twisted Edwards curve thus requires identifying a 1288 corresponding Montgomery curve and rational map. We describe how to 1289 identify such a curve and map immediately below. 1291 6.8.1. Rational maps from Montgomery to twisted Edwards curves 1293 There are two ways to identify the correct Montgomery curve and 1294 rational map for use when hashing to a given twisted Edwards curve. 1296 When hashing to a standardized twisted Edwards curve for which a 1297 corresponding Montgomery form and rational map are also standardized, 1298 the standard Montgomery form and rational map MUST be used to ensure 1299 compatibility with existing software. Two such standardized curves 1300 are the edwards25519 and edwards448 curves, which correspond to the 1301 Montgomery curves curve25519 and curve448, respectively. For both of 1302 these curves, [RFC7748] lists both the Montgomery and twisted Edwards 1303 forms and gives the corresponding rational maps. 1305 The rational map for edwards25519 ([RFC7748], Section 4.1) uses the 1306 constant sqrt_neg_486664 = sqrt(-486664) (mod 2^255 - 19). To ensure 1307 compatibility, this constant MUST be chosen such that 1308 sgn0(sqrt_neg_486664) == 1. Analogous ambiguities in other 1309 standardized rational maps MUST be resolved in the same way: for any 1310 constant k whose sign is ambiguous, k MUST be chosen such that 1311 sgn0(k) == 1. 1313 The 4-isogeny map from curve448 to edwards448 ([RFC7748], 1314 Section 4.2) is unambiguous with respect to sign. 1316 When defining new twisted Edwards curves, a Montgomery equivalent and 1317 rational map SHOULD be specified, and the sign of the rational map 1318 SHOULD be stated unambiguously. 1320 When hashing to a twisted Edwards curve that does not have a 1321 standardized Montgomery form or rational map, the following procedure 1322 MUST be used to derive them. For a twisted Edwards curve given by a 1323 * v^2 + w^2 = 1 + d * v^2 * w^2, first compute A and B, the 1324 parameters of the equivalent Weierstrass curve given by y^2 = x^3 + A 1325 * x^2 + B * x, as follows: 1327 o A = (a + d) / 2 1329 o B = (a - d)^2 / 16 1331 Note that the above curve is given in the Weierstrass form required 1332 by the Elligator 2 mapping of Section 6.7.1. The rational map from 1333 the point (x, y) on this Weierstrass curve to the point (v, w) on the 1334 twisted Edwards curve is given by 1336 o B' = 1 / sqrt(B) = 4 / (a - d) 1338 o v = x / y 1340 o w = (B' * x - 1) / (B' * x + 1) 1342 For completeness, we give the inverse map in Appendix B.1. Note that 1343 the inverse map is not used when hashing to a twisted Edwards curve. 1345 Rational maps may be undefined on certain inputs, e.g., when the 1346 denominator of one of the rational functions is zero. In the map 1347 described above, the exceptional cases are y == 0 or B' * x == -1. 1348 Implementations MUST detect exceptional cases and return the value 1349 (v, w) = (0, 1), which is a valid point on all twisted Edwards curves 1350 given by the equation above. 1352 The following straight-line implementation of the above rational map 1353 handles the exceptional cases. Implementations of other rational 1354 maps (e.g., the ones give in [RFC7748]) are analogous. 1356 rational_map(x, y) 1357 Input: (x, y), a point on the curve y^2 = x^3 + A * x^2 + B * x. 1358 Output: (v, w), a point on an equivalent twisted Edwards curve. 1360 1. t1 = x * B' 1361 2. t2 = t1 + 1 1362 3. t3 = y * t2 1363 4. t3 = inv0(t3) 1364 5. v = t2 * t3 1365 6. v = v * x 1366 7. w = t1 - 1 1367 8. w = w * y 1368 9. w = w * t3 1369 10. e = w == 0 1370 11. w = CMOV(w, 1, e) 1371 12. return (v, w) 1373 6.8.2. Elligator 2 Method 1375 Preconditions: A twisted Edwards curve E and an equivalent curve M 1376 meeting the requirements in Section 6.8.1. 1378 Helper functions: 1380 o map_to_curve_elligator2 is the mapping of Section 6.7.1 to the 1381 curve M. 1383 o rational_map is a function that takes a point (x, y) on M and 1384 returns a point (v, w) on E, as defined in Section 6.8.1. 1386 Sign of y (and w): for this map, the sign is determined by 1387 map_to_curve_elligator2. No further sign adjustments are required. 1389 Exceptions: The exceptions for the Elligator 2 mapping are as given 1390 in Section 6.7.1. The exceptions for the rational map are as given 1391 in Section 6.8.1. No other exceptions are possible. 1393 The following procedure implements the Elligator 2 mapping for a 1394 twisted Edwards curve. (Note that the output point is denoted (v, w) 1395 because it is a point on the target twisted Edwards curve.) 1397 map_to_curve_elligator2_edwards(u) 1398 Input: u, an element of F. 1399 Output: (v, w), a point on E. 1401 1. (x, y) = map_to_curve_elligator2(u) // (x, y) is on M 1402 2. (v, w) = rational_map(x, y) // (v, w) is on E 1403 3. return (v, w) 1405 6.9. Mappings for Supersingular curves 1407 6.9.1. Boneh-Franklin Method 1409 The function map_to_curve_bf(u) implements the Boneh-Franklin method 1410 [BF01] which covers the supersingular curves defined by y^2 = x^3 + B 1411 over a field F such that q = 2 (mod 3). 1413 Preconditions: A supersingular curve over F such that q = 2 (mod 3). 1415 Constants: B, the parameter of the supersingular curve. 1417 Sign of y: determined by sign of u. No adjustments are necessary. 1419 Exceptions: none. 1421 Operations: 1423 1. w = (2 * q - 1) / 3 // Integer arithmetic 1424 2. x = (u^2 - B)^w 1425 3. y = u 1426 4. return (x, y) 1428 6.9.1.1. Implementation 1430 The following procedure implements the Boneh-Franklin's algorithm in 1431 a straight-line fashion. 1433 map_to_curve_bf(u) 1434 Input: u, an element of F. 1435 Output: (x, y), a point on E. 1437 Constants: 1438 1. c1 = (2 * q - 1) / 3 // Integer arithmetic 1440 Steps: 1441 1. t1 = u^2 1442 2. t1 = t1 - B 1443 3. x = t1^c1 // x = (u^2 - B)^((2 * q - 1) / 3) 1444 4. y = u 1445 5. return (x, y) 1447 6.9.2. Elligator 2, A == 0 Method 1449 The function map_to_curve_ell2A0(u) implements an adaptation of 1450 Elligator 2 [BLMP19] targeting curves given by y^2 = x^3 + B * x over 1451 F such that q = 3 (mod 4). 1453 Preconditions: An elliptic curve over F such that q = 3 (mod 4). 1455 Constants: B, the parameter of the elliptic curve. 1457 Sign of y: Inputs u and -u give the same x-coordinate. Thus, we set 1458 sgn0(y) == sgn0(u). 1460 Exceptions: none. 1462 Operations: 1464 1. x1 = u 1465 2. gx1 = x1^3 + B * x1 1466 3. x2 = -x1 1467 4. gx2 = -gx1 1468 5. If is_square(gx1), set x = x1 and y = sqrt(gx1) 1469 6. Else set x = x2 and y = sqrt(gx2) 1470 7. If sgn0(u) != sgn0(y), set y = -y. 1471 8. return (x, y) 1473 6.9.2.1. Implementation 1475 The following procedure implements the Elligator 2 mapping for A == 0 1476 in a straight-line fashion. 1478 map_to_curve_ell2A0(u) 1479 Input: u, an element of F. 1480 Output: (x, y), a point on E. 1482 Constants: 1483 1. c1 = (p + 1) / 4 // Integer arithmetic 1485 Steps: 1486 1. x1 = u 1487 2. x2 = -x1 1488 3. gx1 = x1^2 1489 4. gx1 = gx1 + B 1490 5. gx1 = gx1 * x1 // gx1 = x1^3 + B * x1 1491 6. y = gx1^c1 // This is either sqrt(gx1) or sqrt(gx2) 1492 7. e1 = (y^2) == gx1 1493 8. x = CMOV(x2, x1, e1) 1494 9. e2 = sgn0(u) == sgn0(y) 1495 10. y = CMOV(-y, y, e2) 1496 11. return (x, y) 1498 7. Clearing the cofactor 1500 The mappings of Section 6 always output a point on the elliptic 1501 curve, i.e., a point in a group of order h * r (Section 2.1). 1502 Obtaining a point in G may require a final operation commonly called 1503 "clearing the cofactor," which takes as input any point on the curve. 1505 The cofactor can always be cleared via scalar multiplication by h. 1506 For elliptic curves where h = 1, i.e., the curves with a prime number 1507 of points, no operation is required. This applies, for example, to 1508 the NIST curves P-256, P-384, and P-521 [FIPS186-4]. 1510 In some cases, it is possible to clear the cofactor via a faster 1511 method than scalar multiplication by h. These methods are equivalent 1512 to (but usually faster than) multiplication by some scalar h_eff 1513 whose value is determined by the method and the curve. Examples of 1514 fast cofactor clearing methods include the following: 1516 o For certain pairing-friendly curves having subgroup G2 over an 1517 extension field, Scott et al. [SBCDK09] describe a method for 1518 fast cofactor clearing that exploits an efficiently-computable 1519 endomorphism. Fuentes-Castaneda et al. [FKR11] propose an 1520 alternative method that is sometimes more efficient. Budroni and 1521 Pintore [BP18] give concrete instantiations of these methods for 1522 Barreto-Lynn-Scott pairing-friendly curves [BLS03]. 1524 o Wahby and Boneh ([WB19], Section 5) describe a trick due to Scott 1525 for fast cofactor clearing on any elliptic curve for which the 1526 prime factorization of h and the structure of the elliptic curve 1527 group meet certain conditions. 1529 The clear_cofactor function is parameterized by a scalar h_eff. 1530 Specifically, 1532 clear_cofactor(P) := h_eff * P 1534 where * represents scalar multiplication. When a curve does not 1535 support a fast cofactor clearing method, h_eff = h and the cofactor 1536 MUST be cleared via scalar multiplication. 1538 When a curve admits a fast cofactor clearing method, clear_cofactor 1539 MAY be evaluated either via that method or via scalar multiplication 1540 by the equivalent h_eff; these two methods give the same result. 1541 Note that in this case scalar multiplication by the cofactor h does 1542 not generally give the same result as the fast method, and SHOULD NOT 1543 be used. 1545 8. Suites for Hashing 1547 This section lists recommended suites for hashing to standard 1548 elliptic curves. 1550 A suite fully specifies the procedure for hashing bit strings to 1551 points on a specific elliptic curve group. Each suite comprises the 1552 following parameters: 1554 o Suite ID, a short name used to refer to a given suite. The ID 1555 also indicates whether a suite is a random oracle or nonuniform 1556 encoding (Section 2.2.3, Section 3). Section 8.2 discusses the 1557 naming conventions for suite IDs. 1559 o E, the target elliptic curve over a field F. 1561 o p, the characteristic of the field F. 1563 o m, the extension degree of the field F. 1565 o sgn0, one of the variants specified in Section 4.1. 1567 o H, the hash function used by hash_to_base (Section 5.1). 1569 o L, the length of HKDF-Expand output in hash_to_base (Section 5.1). 1571 o f, a mapping function from Section 6. 1573 o h_eff, the scalar parameter for clear_cofactor (Section 7). 1575 In addition to the above parameters, the mapping f may require 1576 additional parameters Z, M, rational_map, E', and/or iso_map. These 1577 MUST be specified when applicable. 1579 All applications MUST choose a domain separation tag (DST) for use 1580 with hash_to_base (Section 5), in accordance with the guidelines of 1581 Section 3.1. In addition, applications whose security requires a 1582 random oracle MUST use a suite specifying hash_to_curve (Section 3); 1583 see Section 8.2. 1585 The below table lists the curves for which suites are defined and the 1586 subsection that gives the corresponding parameters. 1588 +---------------------------+-------------+ 1589 | E | Section | 1590 +---------------------------+-------------+ 1591 | NIST P-256 | Section 8.3 | 1592 | | | 1593 | NIST P-384 | Section 8.4 | 1594 | | | 1595 | NIST P-521 | Section 8.5 | 1596 | | | 1597 | curve25519 / edwards25519 | Section 8.6 | 1598 | | | 1599 | curve448 / edwards448 | Section 8.7 | 1600 | | | 1601 | secp256k1 | Section 8.8 | 1602 | | | 1603 | BLS12-381 | Section 8.9 | 1604 +---------------------------+-------------+ 1606 8.1. Defining a new hash-to-curve suite 1608 The RECOMMENDED way to define a new hash-to-curve suite is: 1610 1. E, F, p, and m are determined by the elliptic curve and the 1611 field. 1613 2. Choose a sgn0 variant following the guidelines in Section 4.1. 1615 3. Choose a hash function H meeting the requirements in Section 5.1, 1616 and compute L as described in that section. 1618 4. Choose a mapping following the guidelines in Section 6.1, and 1619 select any required parameters for that mapping. 1621 5. Choose h_eff to be either the cofactor of E or, if a fast 1622 cofactor clearing method is to be used, a value appropriate to 1623 that method as discussed in Section 7. 1625 6. Construct a Suite ID following the guidelines in Section 8.2. 1627 When hashing to an elliptic curve not listed in this section, 1628 corresponding hash-to-curve suites SHOULD be specified as described 1629 in this section. 1631 8.2. Suite ID naming conventions 1633 Suite IDs MUST be constructed as follows: 1635 CURVE_ID || "-" || HASH_ID || "-" || MAP_ID || "-" || ENC_VAR || "-" 1636 The fields CURVE_ID, HASH_ID, MAP_ID, and ENC_VAR are ASCII-encoded 1637 strings of at most 64 characters each. Fields can contain only ASCII 1638 characters between 0x21 and 0x7E (inclusive) other than hyphen and 1639 underscore (i.e., 0x2d, and 0x5f). As indicated above, each field 1640 (including the last) is followed by a hyphen ("-", ASCII 0x2d); this 1641 helps to ensure that Suite IDs are prefix free. 1643 Fields MUST be chosen as follows: 1645 o CURVE_ID: a human-readable representation of the target elliptic 1646 curve. 1648 o HASH_ID: a human-readable representation of the hash function used 1649 in hash_to_base (Section 5). 1651 If a suite uses an alternative hash_to_base function 1652 (Section 5.4), a short descriptive name MUST be chosen for that 1653 function using only the allowed characters listed above. That 1654 name MUST be appended to the HASH_ID field, separated by a colon. 1655 For example, a hash_to_base function based on KMAC128 [SP.800-185] 1656 might use the short name "h2b/kmac128", and a reasonable value for 1657 the HASH_ID field would be "SHA3:h2b/kmac128". 1659 o MAP_ID: a human-readable representation of the map_to_curve 1660 function (Section 6). 1662 o ENC_VAR: a string indicating the encoding type and other 1663 information. The first two characters of this string indicate 1664 whether the suite represents a hash_to_curve or an encode_to_curve 1665 operation (Section 3), as follows: 1667 * If ENC_VAR begins with "RO", the suite uses hash_to_curve. 1669 * If ENC_VAR begins with "NU", the suite uses encode_to_curve. 1671 * ENC_VAR MUST NOT begin with any other string. 1673 ENC_VAR MAY also be used to encode other information used to 1674 identify variants, for example, a version number. The RECOMMENDED 1675 way to do so is to add one or more subfields separated by colons. 1676 For example, "RO:V02" is an appropriate ENC_VAR value for the 1677 second version of a random-oracle suite, while 1678 "RO:V02:FOO01:BAR17" might be used to indicate a variant of that 1679 suite. 1681 8.3. Suites for NIST P-256 1683 This section defines ciphersuites for the NIST P-256 elliptic curve 1684 [FIPS186-4]. 1686 The suites P256-SHA256-SSWU-RO- and P256-SHA256-SSWU-NU- share the 1687 following parameters, in addition to the common parameters below. 1689 o f: Simplified SWU method, Section 6.6.2 1691 o Z: -10 1693 The suites P256-SHA256-SVDW-RO- and P256-SHA256-SVDW-NU- share the 1694 following parameters, in addition to the common parameters below. 1696 o f: Shallue-van de Woestijne method, Section 6.6.1 1698 o Z: -3 1700 The common parameters for the above suites are: 1702 o E: y^2 = x^3 + A * x + B, where 1704 * A = -3 1706 * B = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e2 1707 7d2604b 1709 o p: 2^256 - 2^224 + 2^192 + 2^96 - 1 1711 o m: 1 1713 o sgn0: sgn0_le (Section 4.1.2) 1715 o H: SHA-256 1717 o L: 48 1719 o h_eff: 1 1721 An optimized example implementation of the Simplified SWU mapping to 1722 P-256 is given in Appendix D.2. 1724 8.4. Suites for NIST P-384 1726 This section defines ciphersuites for the NIST P-384 elliptic curve 1727 [FIPS186-4]. 1729 The suites P384-SHA512-SSWU-RO- and P384-SHA512-SSWU-NU- share the 1730 following parameters, in addition to the common parameters below. 1732 o f: Simplified SWU method, Section 6.6.2 1734 o Z: -12 1736 The suites P384-SHA512-SVDW-RO- and P384-SHA512-SVDW-NU- share the 1737 following parameters, in addition to the common parameters below. 1739 o f: Shallue-van de Woestijne method, Section 6.6.1 1741 o Z: -1 1743 The common parameters for the above suites are: 1745 o E: y^2 = x^3 + A * x + B, where 1747 * A = -3 1749 * B = 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5 1750 013875ac656398d8a2ed19d2a85c8edd3ec2aef 1752 o p: 2^384 - 2^128 - 2^96 + 2^32 - 1 1754 o m: 1 1756 o sgn0: sgn0_le (Section 4.1.2) 1758 o H: SHA-512 1760 o L: 72 1762 o h_eff: 1 1764 An optimized example implementation of the Simplified SWU mapping to 1765 P-384 is given in Appendix D.2. 1767 8.5. Suites for NIST P-521 1769 This section defines ciphersuites for the NIST P-521 elliptic curve 1770 [FIPS186-4]. 1772 The suites P521-SHA512-SSWU-RO- and P521-SHA512-SSWU-NU- share the 1773 following parameters, in addition to the common parameters below. 1775 o f: Simplified SWU method, Section 6.6.2 1776 o Z: -4 1778 The suites P521-SHA512-SVDW-RO- and P521-SHA512-SVDW-NU- share the 1779 following parameters, in addition to the common parameters below. 1781 o f: Shallue-van de Woestijne method, Section 6.6.1 1783 o Z: 1 1785 The common parameters for the above suites are: 1787 o E: y^2 = x^3 + A * x + B, where 1789 * A = -3 1791 * B = 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b4899 1792 18ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451f 1793 d46b503f00 1795 o p: 2^521 - 1 1797 o m: 1 1799 o sgn0: sgn0_le (Section 4.1.2) 1801 o H: SHA-512 1803 o L: 96 1805 o h_eff: 1 1807 An optimized example implementation of the Simplified SWU mapping to 1808 P-521 is given in Appendix D.2. 1810 8.6. Suites for curve25519 and edwards25519 1812 This section defines ciphersuites for curve25519 and edwards25519 1813 [RFC7748]. 1815 The suites curve25519-SHA256-ELL2-RO- and curve25519-SHA256-ELL2-NU- 1816 share the following parameters, in addition to the common parameters 1817 below. 1819 o E: B * y^2 = x^3 + A * x^2 + x, where 1821 * A = 486662 1823 * B = 1 1825 o f: Elligator 2 method, Section 6.7.1 1827 The suites edwards25519-SHA256-EDELL2-RO- and 1828 edwards25519-SHA256-EDELL2-NU- share the following parameters, in 1829 addition to the common parameters below. 1831 o E: a * x^2 + y^2 = 1 + d * x^2 * y^2, where 1833 * a = -1 1835 * d = 0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca1 1836 35978a3 1838 o f: Twisted Edwards Elligator 2 method, Section 6.8.2 1840 o M: curve25519 defined in [RFC7748], Section 4.1 1842 o rational_map: the birational map defined in [RFC7748], Section 4.1 1844 The common parameters for all of the above suites are: 1846 o p: 2^255 - 19 1848 o m: 1 1850 o sgn0: sgn0_le (Section 4.1.2) 1852 o H: SHA-256 1854 o L: 48 1856 o Z: 2 1858 o h_eff: 8 1860 Optimized example implementations of the above mappings are given in 1861 Appendix D.3 and Appendix D.4. 1863 8.7. Suites for curve448 and edwards448 1865 This section defines ciphersuites for curve448 and edwards448 1866 [RFC7748]. 1868 The suites curve448-SHA512-ELL2-RO- and curve448-SHA512-ELL2-NU- 1869 share the following parameters, in addition to the common parameters 1870 below. 1872 o E: B * y^2 = x^3 + A * x^2 + x, where 1873 * A = 156326 1875 * B = 1 1877 o f: Elligator 2 method, Section 6.7.1 1879 The suites edwards448-SHA512-EDELL2-RO- and 1880 edwards448-SHA512-EDELL2-NU- share the following parameters, in 1881 addition to the common parameters below. 1883 o E: a * x^2 + y^2 = 1 + d * x^2 * y^2, where 1885 * a = 1 1887 * d = -39081 1889 o f: Twisted Edwards Elligator 2 method, Section 6.8.2 1891 o M: curve448, defined in [RFC7748], Section 4.2 1893 o rational_map: the 4-isogeny map defined in [RFC7748], Section 4.2 1895 The common parameters for all of the above suites are: 1897 o p: 2^448 - 2^224 - 1 1899 o m: 1 1901 o sgn0: sgn0_le (Section 4.1.2) 1903 o H: SHA-512 1905 o L: 84 1907 o Z: -1 1909 o h_eff: 4 1911 Optimized example implementations of the above mappings are given in 1912 Appendix D.5 and Appendix D.6. 1914 8.8. Suites for secp256k1 1916 This section defines ciphersuites for the secp256k1 elliptic curve 1917 [SEC2]. 1919 The suites secp256k1-SHA256-SSWU-RO- and secp256k1-SHA256-SSWU-NU- 1920 share the following parameters, in addition to the common parameters 1921 below. 1923 o f: Simplified SWU for AB == 0, Section 6.6.3 1925 o Z: -11 1927 o E': y'^2 = x'^3 + A' * x' + B', where 1929 * A': 0x3f8731abdd661adca08a5558f0f5d272e953d363cb6f0e5d405447c01 1930 a444533 1932 * B': 1771 1934 o iso_map: the 3-isogeny map from E' to E given in Appendix C.1 1936 The suites secp256k1-SHA256-SVDW-RO- and secp256k1-SHA256-SVDW-NU- 1937 share the following parameters, in addition to the common parameters 1938 below. 1940 o f: Shallue-van de Woestijne method, Section 6.6.1 1942 o Z: 1 1944 The common parameters for all of the above suites are: 1946 o E: y^2 = x^3 + 7 1948 o p: 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 1950 o m: 1 1952 o sgn0: sgn0_le (Section 4.1.2) 1954 o H: SHA-256 1956 o L: 48 1958 o h_eff: 1 1960 An optimized example implementation of the Simplified SWU mapping to 1961 the curve E' isogenous to secp256k1 is given in Appendix D.2. 1963 8.9. Suites for BLS12-381 1965 This section defines ciphersuites for groups G1 and G2 of the 1966 BLS12-381 elliptic curve [draft-yonezawa-pfc-01]. 1968 8.9.1. BLS12-381 G1 1970 The suites BLS12381G1-SHA256-SSWU-RO- and BLS12381G1-SHA256-SSWU-NU- 1971 share the following parameters, in addition to the common parameters 1972 below. 1974 o f: Simplified SWU for AB == 0, Section 6.6.3 1976 o Z: 11 1978 o E': y'^2 = x'^3 + A' * x' + B', where 1980 * A' = 0x144698a3b8e9433d693a02c96d4982b0ea985383ee66a8d8e8981aef 1981 d881ac98936f8da0e0f97f5cf428082d584c1d 1983 * B' = 0x12e2908d11688030018b12e8753eee3b2016c1f0f24f4070a0b9c14f 1984 cef35ef55a23215a316ceaa5d1cc48e98e172be0 1986 o iso_map: the 11-isogeny map from E' to E given in Appendix C.2 1988 The suites BLS12381G1-SHA256-SVDW-RO- and BLS12381G1-SHA256-SVDW-NU- 1989 share the following parameters, in addition to the common parameters 1990 below. 1992 o f: Shallue-van de Woestijne method, Section 6.6.1 1994 o Z: -3 1996 The common parameters for the above suites are: 1998 o E: y^2 = x^3 + 4 2000 o p: 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f 2001 6241eabfffeb153ffffb9feffffffffaaab 2003 o m: 1 2005 o sgn0: sgn0_be (Section 4.1.1) 2007 o H: SHA-256 2009 o L: 64 2010 o h_eff: 0xd201000000010001 2012 Note that this h_eff value is chosen for compatibility with the fast 2013 cofactor clearing method described by Scott ([WB19] Section 5). 2015 An optimized example implementation of the Simplified SWU mapping to 2016 the curve E' isogenous to BLS12-381 G1 is given in Appendix D.2. 2018 8.9.2. BLS12-381 G2 2020 Group G2 of BLS12-381 is defined over a field F = GF(p^m) defined as: 2022 o p: 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f 2023 6241eabfffeb153ffffb9feffffffffaaab 2025 o m: 2 2027 o (1, I) is the basis for F, where I^2 + 1 == 0 in F 2029 The suites BLS12381G2-SHA256-SSWU-RO- and BLS12381G2-SHA256-SSWU-NU- 2030 share the following parameters, in addition to the common parameters 2031 below. 2033 o f: Simplified SWU for AB == 0, Section 6.6.3 2035 o Z: -(2 + I) 2037 o E': y'^2 = x'^3 + A' * x' + B', where 2039 * A' = 240 * I 2041 * B' = 1012 * (1 + I) 2043 o iso_map: the isogeny map from E' to E given in Appendix C.3 2045 The suites BLS12381G2-SHA256-SVDW-RO- and BLS12381G2-SHA256-SVDW-NU- 2046 share the following parameters, in addition to the common parameters 2047 below. 2049 o f: Shallue-van de Woestijne method, Section 6.6.1 2051 o Z: I 2053 The common parameters for the above suites are: 2055 o E: y^2 = x^3 + 4 * (1 + I) 2057 o p, m, F: defined above 2058 o sgn0: sgn0_be (Section 4.1.1) 2060 o H: SHA-256 2062 o L: 64 2064 o h_eff: 0xbc69f08f2ee75b3584c6a0ea91b352888e2a8e9145ad7689986ff0315 2065 08ffe1329c2f178731db956d82bf015d1212b02ec0ec69d7477c1ae954cbc06689 2066 f6a359894c0adebbf6b4e8020005aaa95551 2068 Note that this h_eff value is chosen for compatibility with the fast 2069 cofactor clearing method described by Budroni and Pintore ([BP18], 2070 Section 4.1). 2072 9. IANA Considerations 2074 This document has no IANA actions. 2076 10. Security Considerations 2078 When constant-time implementations are required, all basic operations 2079 and utility functions must be implemented in constant time, as 2080 discussed in Section 4. 2082 Each encoding function accepts arbitrary input and maps it to a 2083 pseudorandom point on the curve. Directly evaluating the mappings of 2084 Section 6 produces an output that is distinguishable from random. 2085 Section 3 shows how to use these mappings to construct a function 2086 approximating a random oracle. 2088 Section 3.1 describes considerations related to domain separation for 2089 random oracle encodings. 2091 Section 5 describes considerations for uniformly hashing to field 2092 elements. 2094 When the hash_to_curve function (Section 3) is instantiated with 2095 hash_to_base (Section 5), the resulting function is indifferentiable 2096 from a random oracle. In most cases such a function can be safely 2097 used in protocols whose security analysis assumes a random oracle 2098 that outputs points on an elliptic curve. As Ristenpart et al. 2099 discuss in [RSS11], however, not all security proofs that rely on 2100 random oracles continue to hold when those oracles are replaced by 2101 indifferentiable functionalities. This limitation should be 2102 considered when analyzing the security of protocols relying on the 2103 hash_to_curve function. 2105 When hashing passwords using any function described in this document, 2106 an adversary who learns the output of the hash function (or 2107 potentially any intermediate value, e.g., the output of hash_to_base) 2108 may be able to carry out a dictionary attack. To mitigate such 2109 attacks, it is recommended to first execute a more costly key 2110 derivation function (e.g., PBKDF2 [RFC2898] or scrypt [RFC7914]) on 2111 the password, then hash the output of that function to the target 2112 elliptic curve. For collision resistance, the hash underlying the 2113 key derivation function should be chosen according to the guidelines 2114 listed in Section 5.1. 2116 11. Acknowledgements 2118 The authors would like to thank Adam Langley for his detailed writeup 2119 of Elligator 2 with Curve25519 [L13]; Christopher Patton and Benjamin 2120 Lipp for educational discussions; and Sean Devlin, Justin Drake, Dan 2121 Harkins, Thomas Icart, Leonid Reyzin, Michael Scott, and Mathy 2122 Vanhoef for helpful feedback. 2124 12. Contributors 2126 o Sharon Goldberg 2127 Boston University 2128 goldbe@cs.bu.edu 2130 o Ela Lee 2131 Royal Holloway, University of London 2132 Ela.Lee.2010@live.rhul.ac.uk 2134 13. References 2136 13.1. Normative References 2138 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2139 Requirement Levels", BCP 14, RFC 2119, 2140 DOI 10.17487/RFC2119, March 1997, 2141 . 2143 [RFC2898] Kaliski, B., "PKCS #5: Password-Based Cryptography 2144 Specification Version 2.0", RFC 2898, 2145 DOI 10.17487/RFC2898, September 2000, 2146 . 2148 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 2149 Key Derivation Function (HKDF)", RFC 5869, 2150 DOI 10.17487/RFC5869, May 2010, 2151 . 2153 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 2154 for Security", RFC 7748, DOI 10.17487/RFC7748, January 2155 2016, . 2157 [RFC7914] Percival, C. and S. Josefsson, "The scrypt Password-Based 2158 Key Derivation Function", RFC 7914, DOI 10.17487/RFC7914, 2159 August 2016, . 2161 [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, 2162 "PKCS #1: RSA Cryptography Specifications Version 2.2", 2163 RFC 8017, DOI 10.17487/RFC8017, November 2016, 2164 . 2166 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 2167 Signature Algorithm (EdDSA)", RFC 8032, 2168 DOI 10.17487/RFC8032, January 2017, 2169 . 2171 13.2. Informative References 2173 [AFQTZ14] Aranha, D., Fouque, P., Qian, C., Tibouchi, M., and J. 2174 Zapalowicz, "Binary Elligator squared", In Selected Areas 2175 in Cryptography - SAC 2014, pages 20-37, 2176 DOI 10.1007/978-3-319-13051-4_2, 2014, 2177 . 2179 [AR13] Adj, G. and F. Rodriguez-Henriquez, "Square Root 2180 Computation over Even Extension Fields", In IEEE 2181 Transactions on Computers. vol 63 issue 11, 2182 pages 2829-2841, DOI 10.1109/TC.2013.145, November 2014, 2183 . 2185 [BBJLP08] Bernstein, D., Birkner, P., Joye, M., Lange, T., and C. 2186 Peters, "Twisted Edwards curves", In AFRICACRYPT 2008, 2187 pages 389-405, DOI 10.1007/978-3-540-68164-9_26, 2008, 2188 . 2190 [BCIMRT10] 2191 Brier, E., Coron, J., Icart, T., Madore, D., Randriam, H., 2192 and M. Tibouchi, "Efficient Indifferentiable Hashing into 2193 Ordinary Elliptic Curves", In Advances in Cryptology - 2194 CRYPTO 2010, pages 237-254, 2195 DOI 10.1007/978-3-642-14623-7_13, 2010, 2196 . 2198 [BF01] Boneh, D. and M. Franklin, "Identity-based encryption from 2199 the Weil pairing", In Advances in Cryptology - CRYPTO 2200 2001, pages 213-229, DOI 10.1007/3-540-44647-8_13, August 2201 2001, . 2203 [BHKL13] Bernstein, D., Hamburg, M., Krasnova, A., and T. Lange, 2204 "Elligator: elliptic-curve points indistinguishable from 2205 uniform random strings", In Proceedings of the 2013 ACM 2206 SIGSAC conference on computer and communications 2207 security., pages 967-980, DOI 10.1145/2508859.2516734, 2208 November 2013, . 2210 [BLAKE2X] Aumasson, J-P., Neves, S., Wilcox-O'Hearn, Z., and C. 2211 Winnerlein, "BLAKE2X", December 2016, 2212 . 2214 [BLMP19] Bernstein, D., Lange, T., Martindale, C., and L. Panny, 2215 "Quantum circuits for the CSIDH: optimizing quantum 2216 evaluation of isogenies", In Advances in Cryptology - 2217 EUROCRYPT 2019, DOI 10.1007/978-3-030-17656-3, 2019, 2218 . 2220 [BLS01] Boneh, D., Lynn, B., and H. Shacham, "Short signatures 2221 from the Weil pairing", In Journal of Cryptology, vol 17, 2222 pages 297-319, DOI 10.1007/s00145-004-0314-9, July 2004, 2223 . 2225 [BLS03] Barreto, P., Lynn, B., and M. Scott, "Constructing 2226 Elliptic Curves with Prescribed Embedding Degrees", 2227 In Security in Communication Networks, pages 257-267, 2228 DOI 10.1007/3-540-36413-7_19, 2003, 2229 . 2231 [BMP00] Boyko, V., MacKenzie, P., and S. Patel, "Provably secure 2232 password-authenticated key exchange using Diffie-Hellman", 2233 In Advances in Cryptology - EUROCRYPT 2000, pages 156-171, 2234 DOI 10.1007/3-540-45539-6_12, May 2000, 2235 . 2237 [BN05] Barreto, P. and M. Naehrig, "Pairing-Friendly Elliptic 2238 Curves of Prime Order", In Selected Areas in Cryptography 2239 2005, pages 319-331, DOI 10.1007/11693383_22, 2006, 2240 . 2242 [BP18] Budroni, A. and F. Pintore, "Hashing to G2 on BLS pairing- 2243 friendly curves", In ACM Communications in Computer 2244 Algebra, pages 63-66, DOI 10.1145/3313880.3313884, 2245 September 2018, . 2247 [C93] Cohen, H., "A Course in Computational Algebraic Number 2248 Theory", publisher Springer-Verlag, ISBN 9783642081422, 2249 1993, . 2251 [CFADLNV05] 2252 Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., 2253 Nguyen, K., and F. Vercauteren, "Handbook of Elliptic and 2254 Hyperelliptic Curve Cryptography", publisher Chapman and 2255 Hall / CRC, ISBN 9781584885184, 2005, 2256 . 2258 [CK11] Couveignes, J. and J. Kammerer, "The geometry of flex 2259 tangents to a cubic curve and its parameterizations", 2260 In Journal of Symbolic Computation, vol 47 issue 3, 2261 pages 266-281, DOI 10.1016/j.jsc.2011.11.003, 2012, 2262 . 2264 [draft-yonezawa-pfc-01] 2265 Yonezawa, S., Chikara, S., Kobayashi, T., and T. Saito, 2266 "Pairing-friendly Curves", March 2019, 2267 . 2270 [DRST12] Dodis, Y., Ristenpart, T., Steinberger, J., and S. 2271 Tessaro, "To hash or not to hash again? 2272 (In)differentiability results for H^2 and HMAC", 2273 In Advances in Cryptology - CRYPTO 2012, pages 348-366, 2274 DOI 10.1007/978-3-642-32009-5_21, August 2012, 2275 . 2277 [F11] Farashahi, R., "Hashing into Hessian curves", 2278 In AFRICACRYPT 2011, pages 278-289, 2279 DOI 10.1007/978-3-642-21969-6_17, 2011, 2280 . 2282 [FFSTV13] Farashahi, R., Fouque, P., Shparlinski, I., Tibouch, M., 2283 and J. Voloch, "Indifferentiable deterministic hashing to 2284 elliptic and hyperelliptic curves", In Math. Comp. vol 82, 2285 pages 491-512, DOI 10.1090/S0025-5718-2012-02606-8, 2013, 2286 . 2288 [FIPS180-4] 2289 National Institute of Standards and Technology (NIST), 2290 "Secure Hash Standard (SHS)", August 2015, 2291 . 2294 [FIPS186-4] 2295 National Institute of Standards and Technology (NIST), 2296 "FIPS Publication 186-4: Digital Signature Standard", July 2297 2013, . 2300 [FIPS202] National Institute of Standards and Technology (NIST), 2301 "SHA-3 Standard: Permutation-Based Hash and Extendable- 2302 Output Functions", August 2015, 2303 . 2306 [FJT13] Fouque, P., Joux, A., and M. Tibouchi, "Injective 2307 encodings to elliptic curves", In ACISP 2013, 2308 pages 203-218, DOI 10.1007/978-3-642-39059-3_14, 2013, 2309 . 2311 [FKR11] Fuentes-Castaneda, L., Knapp, E., and F. Rodriguez- 2312 Henriquez, "Fast Hashing to G2 on Pairing-Friendly 2313 Curves", In Selected Areas in Cryptography, pages 412-430, 2314 DOI 10.1007/978-3-642-28496-0_25, 2011, 2315 . 2317 [FSV09] Farashahi, R., Shparlinski, I., and J. Voloch, "On hashing 2318 into elliptic curves", In Journal of Mathematical 2319 Cryptology, vol 3 no 4, pages 353-360, 2320 DOI 10.1515/JMC.2009.022, 2009, 2321 . 2323 [FT10] Fouque, P. and M. Tibouchi, "Estimating the size of the 2324 image of deterministic hash functions to elliptic 2325 curves.", In Progress in Cryptology - LATINCRYPT 2010, 2326 pages 81-91, DOI 10.1007/978-3-642-14712-8_5, 2010, 2327 . 2329 [FT12] Fouque, P. and M. Tibouchi, "Indifferentiable Hashing to 2330 Barreto-Naehrig Curves", In Progress in Cryptology - 2331 LATINCRYPT 2012, pages 1-7, 2332 DOI 10.1007/978-3-642-33481-8_1, 2012, 2333 . 2335 [hash2curve-repo] 2336 "Hashing to Elliptic Curves - GitHub repository", 2019, 2337 . 2339 [Icart09] Icart, T., "How to Hash into Elliptic Curves", In Advances 2340 in Cryptology - CRYPTO 2009, pages 303-316, 2341 DOI 10.1007/978-3-642-03356-8_18, 2009, 2342 . 2344 [J96] Jablon, D., "Strong password-only authenticated key 2345 exchange", In SIGCOMM Computer Communication Review, vol 2346 26 issue 5, pages 5-26, DOI 10.1145/242896.242897, 1996, 2347 . 2349 [jubjub-fq] 2350 "zkcrypto/jubjub - fq.rs", 2019, 2351 . 2354 [KLR10] Kammerer, J., Lercier, R., and G. Renault, "Encoding 2355 points on hyperelliptic curves over finite fields in 2356 deterministic polynomial time", In PAIRING 2010, 2357 pages 278-297, DOI 10.1007/978-3-642-17455-1_18, 2010, 2358 . 2360 [L13] Langley, A., "Implementing Elligator for Curve25519", 2361 2013, . 2364 [LBB19] Lipp, B., Blanchet, B., and K. Bhargavan, "A Mechanised 2365 Proof of the WireGuard Virtual Private Network Protocol", 2366 In INRIA Research Report No. 9269, April 2019, 2367 . 2369 [p1363a] IEEE Computer Society, "IEEE Standard Specifications for 2370 Public-Key Cryptography---Amendment 1: Additional 2371 Techniques", March 2004, 2372 . 2374 [RFC7693] Saarinen, M-J., Ed. and J-P. Aumasson, "The BLAKE2 2375 Cryptographic Hash and Message Authentication Code (MAC)", 2376 RFC 7693, DOI 10.17487/RFC7693, November 2015, 2377 . 2379 [RSS11] Ristenpart, T., Shacham, H., and T. Shrimpton, "Careful 2380 with Composition: Limitations of the Indifferentiability 2381 Framework", In Advances in Cryptology - EUROCRYPT 2011, 2382 pages 487-506, DOI 10.1007/978-3-642-20465-4_27, May 2011, 2383 . 2385 [S05] Skalba, M., "Points on elliptic curves over finite 2386 fields", In Acta Arithmetica, vol 117 no 3, pages 293-301, 2387 DOI 10.4064/aa117-3-7, 2005, 2388 . 2390 [S85] Schoof, R., "Elliptic Curves Over Finite Fields and the 2391 Computation of Square Roots mod p", In Mathematics of 2392 Computation vol 44 issue 170, pages 483-494, 2393 DOI 10.1090/S0025-5718-1985-0777280-6, April 1985, 2394 . 2396 [SAGE] The Sage Developers, "SageMath, the Sage Mathematics 2397 Software System", 2019, . 2399 [SBCDK09] Scott, M., Benger, N., Charlemagne, M., Dominguez Perez, 2400 L., and E. Kachisa, "Fast Hashing to G2 on Pairing- 2401 Friendly Curves", In Pairing-Based Cryptography - Pairing 2402 2009, pages 102-113, DOI 10.1007/978-3-642-03298-1_8, 2403 2009, . 2405 [SEC1] Standards for Efficient Cryptography Group (SECG), "SEC 1: 2406 Elliptic Curve Cryptography", May 2009, 2407 . 2409 [SEC2] Standards for Efficient Cryptography Group (SECG), "SEC 2: 2410 Recommended Elliptic Curve Domain Parameters", January 2411 2010, . 2413 [SP.800-185] 2414 Kelsey, J., Chang, S., and R. Perlner, "SHA-3 Derived 2415 Functions: cSHAKE, KMAC, TupleHash and ParallelHash", 2416 December 2016, . 2418 [SS04] Schinzel, A. and M. Skalba, "On equations y^2 = x^n + k in 2419 a finite field.", In Bulletin Polish Acad. Sci. Math. vol 2420 52, no 3, pages 223-226, DOI 10.4064/ba52-3-1, 2004, 2421 . 2423 [SW06] Shallue, A. and C. van de Woestijne, "Construction of 2424 rational points on elliptic curves over finite fields", 2425 In Algorithmic Number Theory. ANTS 2006., pages 510-524, 2426 DOI 10.1007/11792086_36, 2006, 2427 . 2429 [T14] Tibouchi, M., "Elligator squared: Uniform points on 2430 elliptic curves of prime order as uniform random strings", 2431 In Financial Cryptography and Data Security - FC 2014, 2432 pages 139-156, DOI 10.1007/978-3-662-45472-5_10, 2014, 2433 . 2435 [TK17] Tibouchi, M. and T. Kim, "Improved elliptic curve hashing 2436 and point representation", In Designs, Codes, and 2437 Cryptography, vol 82, pages 161-177, 2438 DOI 10.1007/s10623-016-0288-2, 2017, 2439 . 2441 [U07] Ulas, M., "Rational points on certain hyperelliptic curves 2442 over finite fields", In Bulletin Polish Acad. Sci. Math. 2443 vol 55, no 2, pages 97-104, DOI 10.4064/ba55-2-1, 2007, 2444 . 2446 [W08] Washington, L., "Elliptic curves: Number theory and 2447 cryptography", edition 2nd, publisher Chapman and Hall / 2448 CRC, ISBN 9781420071467, 2008, 2449 . 2451 [W19] Wahby, R., "An explicit, generic parameterization for the 2452 Shallue--van de Woestijne map", n.d., 2453 . 2456 [WB19] Wahby, R. and D. Boneh, "Fast and simple constant-time 2457 hashing to the BLS12-381 elliptic curve", In IACR Trans. 2458 CHES, volume 2019, issue 4, 2459 DOI 10.13154/tches.v2019.i4.154-179, ePrint 2019/403, 2460 August 2019, . 2462 [x9.62] ANSI, "Public Key Cryptography for the Financial Services 2463 Industry: the Elliptic Curve Digital Signature Algorithm 2464 (ECDSA)", ANSI X9.62-1998, September 1998. 2466 Appendix A. Related Work 2468 The problem of mapping arbitrary bit strings to elliptic curve points 2469 has been the subject of both practical and theoretical research. 2470 This section briefly describes the background and research results 2471 that underly the recommendations in this document. This section is 2472 provided for informational purposes only. 2474 A naive but generally insecure method of mapping a string alpha to a 2475 point on an elliptic curve E having n points is to first fix a point 2476 P that generates the elliptic curve group, and a hash function Hn 2477 from bit strings to integers less than n; then compute Hn(alpha) * P, 2478 where the * operator represents scalar multiplication. The reason 2479 this approach is insecure is that the resulting point has a known 2480 discrete log relationship to P. Thus, except in cases where this 2481 method is specified by the protocol, it must not be used; doing so 2482 risks catastrophic security failures. 2484 Boneh et al. [BLS01] describe an encoding method they call 2485 MapToGroup, which works roughly as follows: first, use the input 2486 string to initialize a pseudorandom number generator, then use the 2487 generator to produce a pseudorandom value x in F. If x is the 2488 x-coordinate of a point on the elliptic curve, output that point. 2489 Otherwise, generate a new pseudorandom value x in F and try again. 2490 Since a random value x in F has probability about 1/2 of 2491 corresponding to a point on the curve, the expected number of tries 2492 is just two. However, the running time of this method depends on the 2493 input string, which means that it is not safe to use in protocols 2494 sensitive to timing side channels. 2496 Schinzel and Skalba [SS04] introduce a method of constructing 2497 elliptic curve points deterministically, for a restricted class of 2498 curves and a very small number of points. Skalba [S05] generalizes 2499 this construction to more curves and more points on those curves. 2500 Shallue and van de Woestijne [SW06] further generalize and simplify 2501 Skalba's construction, yielding concretely efficient maps to a 2502 constant fraction of the points on almost any curve. Fouque and 2503 Tibouchi [FT12] give a parameterization of this mapping for Barreto- 2504 Naehrig pairing-friendly curves [BN05]. 2506 Ulas [U07] describes a simpler version of the Shallue-van de 2507 Woestijne map, and Brier et al. [BCIMRT10] give a further 2508 simplification, which the authors call the "simplified SWU" map. 2509 That simplified map applies only to fields of characteristic p = 3 2510 (mod 4); Wahby and Boneh [WB19] generalize to fields of any 2511 characteristic, and give further optimizations. 2513 Boneh and Franklin give a deterministic algorithm mapping to certain 2514 supersingular curves over fields of characteristic p = 2 (mod 3) 2515 [BF01]. Icart gives another deterministic algorithm which maps to 2516 any curve over a field of characteristic p = 2 (mod 3) [Icart09]. 2517 Several extensions and generalizations follow this work, including 2518 [FSV09], [FT10], [KLR10], [F11], and [CK11]. 2520 Following the work of Farashahi [F11], Fouque et al. [FJT13] 2521 describe a mapping to curves of characteristic p = 3 (mod 4) having a 2522 number of points divisible by 4. Bernstein et al. [BHKL13] optimize 2523 this mapping and describe a related mapping that they call "Elligator 2524 2," which applies to any curve over a field of odd characteristic 2525 having a point of order 2. This includes Curve25519 and Curve448, 2526 both of which are CFRG-recommended curves [RFC7748]. 2528 An important caveat regarding all of the above deterministic mapping 2529 functions is that none of them map to the entire curve, but rather to 2530 some fraction of the points. This means that they cannot be used 2531 directly to construct a random oracle that outputs points on the 2532 curve. 2534 Brier et al. [BCIMRT10] give two solutions to this problem. The 2535 first, which Brier et al. prove applies to Icart's method, computes 2536 f(H0(msg)) + f(H1(msg)) for two distinct hash functions H0 and H1 2537 from bit strings to F and a mapping f from F to the elliptic curve E. 2538 The second, which applies to essentially all deterministic mappings 2539 but is more costly, computes f(H0(msg)) + H2(msg) * P, for P a 2540 generator of the elliptic curve group and H2 a hash from bit strings 2541 to integers modulo r, the order of the elliptic curve group. 2542 Farashahi et al. [FFSTV13] improve the analysis of the first method, 2543 showing that it applies to essentially all deterministic mappings. 2544 Tibouchi and Kim [TK17] further refine the analysis and describe 2545 additional optimizations. 2547 Complementary to the problem of mapping from bit strings to elliptic 2548 curve points, Bernstein et al. [BHKL13] study the problem of mapping 2549 from elliptic curve points to uniformly random bit strings, giving 2550 solutions for a class of curves including Montgomery and twisted 2551 Edwards curves. Tibouchi [T14] and Aranha et al. [AFQTZ14] 2552 generalize these results. This document does not deal with this 2553 complementary problem. 2555 Appendix B. Rational maps 2557 This section gives several useful rational maps. 2559 B.1. Twisted Edwards to Weierstrass and Montgomery curves 2561 The inverse of the rational map specified in Section 6.8.1, i.e., the 2562 map from the point (v, w) on the twisted Edwards curve a * v^2 + w^2 2563 = 1 + d * v^2 * w^2 to the point (x, y) on the Weierstrass curve y^2 2564 = x^3 + A * x^2 + B * x is given by: 2566 o A = (a + d) / 2 2568 o B = (a - d)^2 / 16 2570 o B' = 1 / sqrt(B) = 4 / (a - d) 2572 o x = (1 + w) / (B' * (1 - w)) 2573 o y = (1 + w) / (B' * v * (1 - w)) 2575 This map is undefined when w == 1 or v == 0. In this case, return 2576 the point (x, y) = (0, 0). 2578 It may also be useful to map to a Montgomery curve of the form B' * 2579 t^2 = s^3 + A' * s^2 + s. This curve is equivalent to the twisted 2580 Edwards curve above via the following rational map ([BBJLP08], 2581 Theorem 3.2): 2583 o A' = 2 * (a + d) / (a - d) 2585 o B' = 4 / (a - d) 2587 o s = (1 + w) / (1 - w) 2589 o t = (1 + w) / (v * (1 - w)) 2591 whose inverse is given by: 2593 o v = s / t 2595 o w = (s - 1) / (s + 1) 2597 Composing the mapping immediately above with the mapping from 2598 Montgomery to Weierstrass curves in Appendix B.2 yields a mapping 2599 from twisted Edwards curves to Weierstrass curves of the form 2600 required by the mappings in Section 6.6. This mapping can be used to 2601 apply the Shallue-van de Woestijne method (Section 6.6.1) to twisted 2602 Edwards curves. 2604 B.2. Montgomery to Weierstrass curves 2606 The rational map from the point (s, t) on the Montgomery curve B' * 2607 t^2 = s^3 + A' * s^2 + s to the point (x, y) on the equivalent 2608 Weierstrass curve y^2 = x^3 + C * x + D is given by: 2610 o C = (3 - A'^2) / (3 * B'^2) 2612 o D = (2 * A'^3 - 9 * A') / (27 * B'^3) 2614 o x = (3 * s + A') / (3 * B') 2616 o y = t / B' 2618 The inverse map, from the point (x, y) to the point (s, t), is given 2619 by 2620 o s = (3 * B' * x - A') / 3 2622 o t = y * B' 2624 This mapping can be used to apply the Shallue-van de Woestijne method 2625 (Section 6.6.1) to Montgomery curves. 2627 Appendix C. Isogeny maps for Suites 2629 This section specifies the isogeny maps for the secp256k1 and 2630 BLS12-381 suites listed in Section 8. 2632 These maps are given in terms of affine coordinates. Wahby and Boneh 2633 ([WB19], Section 4.3) show how to evaluate these maps in a projective 2634 coordinate system (Appendix D.1), which avoids modular inversions. 2636 Refer to the draft repository [hash2curve-repo] for a Sage [SAGE] 2637 script that constructs these isogenies. 2639 C.1. 3-isogeny map for secp256k1 2641 This section specifies the isogeny map for the secp256k1 suite listed 2642 in Section 8.8. 2644 The 3-isogeny map from (x', y') on E' to (x, y) on E is given by the 2645 following rational functions: 2647 o x = x_num / x_den, where 2649 * x_num = k_(1,3) * x'^3 + k_(1,2) * x'^2 + k_(1,1) * x' + 2650 k_(1,0) 2652 * x_den = x'^2 + k_(2,1) * x' + k_(2,0) 2654 o y = y' * y_num / y_den, where 2656 * y_num = k_(3,3) * x'^3 + k_(3,2) * x'^2 + k_(3,1) * x' + 2657 k_(3,0) 2659 * y_den = x'^3 + k_(4,2) * x'^2 + k_(4,1) * x' + k_(4,0) 2661 The constants used to compute x_num are as follows: 2663 o k_(1,0) = 2664 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa8c7 2666 o k_(1,1) = 2667 0x7d3d4c80bc321d5b9f315cea7fd44c5d595d2fc0bf63b92dfff1044f17c6581 2669 o k_(1,2) = 2670 0x534c328d23f234e6e2a413deca25caece4506144037c40314ecbd0b53d9dd262 2672 o k_(1,3) = 2673 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c 2675 The constants used to compute x_den are as follows: 2677 o k_(2,0) = 2678 0xd35771193d94918a9ca34ccbb7b640dd86cd409542f8487d9fe6b745781eb49b 2680 o k_(2,1) = 2681 0xedadc6f64383dc1df7c4b2d51b54225406d36b641f5e41bbc52a56612a8c6d14 2683 The constants used to compute y_num are as follows: 2685 o k_(3,0) = 2686 0x4bda12f684bda12f684bda12f684bda12f684bda12f684bda12f684b8e38e23c 2688 o k_(3,1) = 2689 0xc75e0c32d5cb7c0fa9d0a54b12a0a6d5647ab046d686da6fdffc90fc201d71a3 2691 o k_(3,2) = 2692 0x29a6194691f91a73715209ef6512e576722830a201be2018a765e85a9ecee931 2694 o k_(3,3) = 2695 0x2f684bda12f684bda12f684bda12f684bda12f684bda12f684bda12f38e38d84 2697 The constants used to compute y_den are as follows: 2699 o k_(4,0) = 2700 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffff93b 2702 o k_(4,1) = 2703 0x7a06534bb8bdb49fd5e9e6632722c2989467c1bfc8e8d978dfb425d2685c2573 2705 o k_(4,2) = 2706 0x6484aa716545ca2cf3a70c3fa8fe337e0a3d21162f0d6299a7bf8192bfd2a76f 2708 C.2. 11-isogeny map for BLS12-381 G1 2710 The 11-isogeny map from (x', y') on E' to (x, y) on E is given by the 2711 following rational functions: 2713 o x = x_num / x_den, where 2715 * x_num = k_(1,11) * x'^11 + k_(1,10) * x'^10 + k_(1,9) * x'^9 + 2716 ... + k_(1,0) 2718 * x_den = x'^10 + k_(2,9) * x'^9 + k_(2,8) * x'^8 + ... + k_(2,0) 2720 o y = y' * y_num / y_den, where 2722 * y_num = k_(3,15) * x'^15 + k_(3,14) * x'^14 + k_(3,13) * x'^13 2723 + ... + k_(3,0) 2725 * y_den = x'^15 + k_(4,14) * x'^14 + k_(4,13) * x'^13 + ... + 2726 k_(4,0) 2728 The constants used to compute x_num are as follows: 2730 o k_(1,0) = 0x11a05f2b1e833340b809101dd99815856b303e88a2d7005ff2627b 2731 56cdb4e2c85610c2d5f2e62d6eaeac1662734649b7 2733 o k_(1,1) = 0x17294ed3e943ab2f0588bab22147a81c7c17e75b2f6a8417f565e3 2734 3c70d1e86b4838f2a6f318c356e834eef1b3cb83bb 2736 o k_(1,2) = 0xd54005db97678ec1d1048c5d10a9a1bce032473295983e56878e50 2737 1ec68e25c958c3e3d2a09729fe0179f9dac9edcb0 2739 o k_(1,3) = 0x1778e7166fcc6db74e0609d307e55412d7f5e4656a8dbf25f1b332 2740 89f1b330835336e25ce3107193c5b388641d9b6861 2742 o k_(1,4) = 0xe99726a3199f4436642b4b3e4118e5499db995a1257fb3f086eeb6 2743 5982fac18985a286f301e77c451154ce9ac8895d9 2745 o k_(1,5) = 0x1630c3250d7313ff01d1201bf7a74ab5db3cb17dd952799b9ed3ab 2746 9097e68f90a0870d2dcae73d19cd13c1c66f652983 2748 o k_(1,6) = 0xd6ed6553fe44d296a3726c38ae652bfb11586264f0f8ce19008e21 2749 8f9c86b2a8da25128c1052ecaddd7f225a139ed84 2751 o k_(1,7) = 0x17b81e7701abdbe2e8743884d1117e53356de5ab275b4db1a682c6 2752 2ef0f2753339b7c8f8c8f475af9ccb5618e3f0c88e 2754 o k_(1,8) = 0x80d3cf1f9a78fc47b90b33563be990dc43b756ce79f5574a2c596c 2755 928c5d1de4fa295f296b74e956d71986a8497e317 2757 o k_(1,9) = 0x169b1f8e1bcfa7c42e0c37515d138f22dd2ecb803a0c5c99676314 2758 baf4bb1b7fa3190b2edc0327797f241067be390c9e 2760 o k_(1,10) = 0x10321da079ce07e272d8ec09d2565b0dfa7dccdde6787f96d50af 2761 36003b14866f69b771f8c285decca67df3f1605fb7b 2763 o k_(1,11) = 0x6e08c248e260e70bd1e962381edee3d31d79d7e22c837bc23c0bf 2764 1bc24c6b68c24b1b80b64d391fa9c8ba2e8ba2d229 2766 The constants used to compute x_den are as follows: 2768 o k_(2,0) = 0x8ca8d548cff19ae18b2e62f4bd3fa6f01d5ef4ba35b48ba9c95886 2769 17fc8ac62b558d681be343df8993cf9fa40d21b1c 2771 o k_(2,1) = 0x12561a5deb559c4348b4711298e536367041e8ca0cf0800c0126c2 2772 588c48bf5713daa8846cb026e9e5c8276ec82b3bff 2774 o k_(2,2) = 0xb2962fe57a3225e8137e629bff2991f6f89416f5a718cd1fca64e0 2775 0b11aceacd6a3d0967c94fedcfcc239ba5cb83e19 2777 o k_(2,3) = 0x3425581a58ae2fec83aafef7c40eb545b08243f16b1655154cca8a 2778 bc28d6fd04976d5243eecf5c4130de8938dc62cd8 2780 o k_(2,4) = 0x13a8e162022914a80a6f1d5f43e7a07dffdfc759a12062bb8d6b44 2781 e833b306da9bd29ba81f35781d539d395b3532a21e 2783 o k_(2,5) = 0xe7355f8e4e667b955390f7f0506c6e9395735e9ce9cad4d0a43bce 2784 f24b8982f7400d24bc4228f11c02df9a29f6304a5 2786 o k_(2,6) = 0x772caacf16936190f3e0c63e0596721570f5799af53a1894e2e073 2787 062aede9cea73b3538f0de06cec2574496ee84a3a 2789 o k_(2,7) = 0x14a7ac2a9d64a8b230b3f5b074cf01996e7f63c21bca68a81996e1 2790 cdf9822c580fa5b9489d11e2d311f7d99bbdcc5a5e 2792 o k_(2,8) = 0xa10ecf6ada54f825e920b3dafc7a3cce07f8d1d7161366b74100da 2793 67f39883503826692abba43704776ec3a79a1d641 2795 o k_(2,9) = 0x95fc13ab9e92ad4476d6e3eb3a56680f682b4ee96f7d03776df533 2796 978f31c1593174e4b4b7865002d6384d168ecdd0a 2798 The constants used to compute y_num are as follows: 2800 o k_(3,0) = 0x90d97c81ba24ee0259d1f094980dcfa11ad138e48a869522b52af6 2801 c956543d3cd0c7aee9b3ba3c2be9845719707bb33 2803 o k_(3,1) = 0x134996a104ee5811d51036d776fb46831223e96c254f383d0f9063 2804 43eb67ad34d6c56711962fa8bfe097e75a2e41c696 2806 o k_(3,2) = 0xcc786baa966e66f4a384c86a3b49942552e2d658a31ce2c344be4b 2807 91400da7d26d521628b00523b8dfe240c72de1f6 2809 o k_(3,3) = 0x1f86376e8981c217898751ad8746757d42aa7b90eeb791c09e4a3e 2810 c03251cf9de405aba9ec61deca6355c77b0e5f4cb 2812 o k_(3,4) = 0x8cc03fdefe0ff135caf4fe2a21529c4195536fbe3ce50b879833fd 2813 221351adc2ee7f8dc099040a841b6daecf2e8fedb 2815 o k_(3,5) = 0x16603fca40634b6a2211e11db8f0a6a074a7d0d4afadb7bd76505c 2816 3d3ad5544e203f6326c95a807299b23ab13633a5f0 2818 o k_(3,6) = 0x4ab0b9bcfac1bbcb2c977d027796b3ce75bb8ca2be184cb5231413 2819 c4d634f3747a87ac2460f415ec961f8855fe9d6f2 2821 o k_(3,7) = 0x987c8d5333ab86fde9926bd2ca6c674170a05bfe3bdd81ffd038da 2822 6c26c842642f64550fedfe935a15e4ca31870fb29 2824 o k_(3,8) = 0x9fc4018bd96684be88c9e221e4da1bb8f3abd16679dc26c1e8b6e6 2825 a1f20cabe69d65201c78607a360370e577bdba587 2827 o k_(3,9) = 0xe1bba7a1186bdb5223abde7ada14a23c42a0ca7915af6fe06985e7 2828 ed1e4d43b9b3f7055dd4eba6f2bafaaebca731c30 2830 o k_(3,10) = 0x19713e47937cd1be0dfd0b8f1d43fb93cd2fcbcb6caf493fd1183 2831 e416389e61031bf3a5cce3fbafce813711ad011c132 2833 o k_(3,11) = 0x18b46a908f36f6deb918c143fed2edcc523559b8aaf0c2462e6bf 2834 e7f911f643249d9cdf41b44d606ce07c8a4d0074d8e 2836 o k_(3,12) = 0xb182cac101b9399d155096004f53f447aa7b12a3426b08ec02710 2837 e807b4633f06c851c1919211f20d4c04f00b971ef8 2839 o k_(3,13) = 0x245a394ad1eca9b72fc00ae7be315dc757b3b080d4c158013e663 2840 2d3c40659cc6cf90ad1c232a6442d9d3f5db980133 2842 o k_(3,14) = 0x5c129645e44cf1102a159f748c4a3fc5e673d81d7e86568d9ab0f 2843 5d396a7ce46ba1049b6579afb7866b1e715475224b 2845 o k_(3,15) = 0x15e6be4e990f03ce4ea50b3b42df2eb5cb181d8f84965a3957add 2846 4fa95af01b2b665027efec01c7704b456be69c8b604 2848 The constants used to compute y_den are as follows: 2850 o k_(4,0) = 0x16112c4c3a9c98b252181140fad0eae9601a6de578980be6eec323 2851 2b5be72e7a07f3688ef60c206d01479253b03663c1 2853 o k_(4,1) = 0x1962d75c2381201e1a0cbd6c43c348b885c84ff731c4d59ca4a103 2854 56f453e01f78a4260763529e3532f6102c2e49a03d 2856 o k_(4,2) = 0x58df3306640da276faaae7d6e8eb15778c4855551ae7f310c35a5d 2857 d279cd2eca6757cd636f96f891e2538b53dbf67f2 2859 o k_(4,3) = 0x16b7d288798e5395f20d23bf89edb4d1d115c5dbddbcd30e123da4 2860 89e726af41727364f2c28297ada8d26d98445f5416 2862 o k_(4,4) = 0xbe0e079545f43e4b00cc912f8228ddcc6d19c9f0f69bbb0542eda0 2863 fc9dec916a20b15dc0fd2ededda39142311a5001d 2865 o k_(4,5) = 0x8d9e5297186db2d9fb266eaac783182b70152c65550d881c5ecd87 2866 b6f0f5a6449f38db9dfa9cce202c6477faaf9b7ac 2868 o k_(4,6) = 0x166007c08a99db2fc3ba8734ace9824b5eecfdfa8d0cf8ef5dd365 2869 bc400a0051d5fa9c01a58b1fb93d1a1399126a775c 2871 o k_(4,7) = 0x16a3ef08be3ea7ea03bcddfabba6ff6ee5a4375efa1f4fd7feb34f 2872 d206357132b920f5b00801dee460ee415a15812ed9 2874 o k_(4,8) = 0x1866c8ed336c61231a1be54fd1d74cc4f9fb0ce4c6af5920abc575 2875 0c4bf39b4852cfe2f7bb9248836b233d9d55535d4a 2877 o k_(4,9) = 0x167a55cda70a6e1cea820597d94a84903216f763e13d87bb530859 2878 2e7ea7d4fbc7385ea3d529b35e346ef48bb8913f55 2880 o k_(4,10) = 0x4d2f259eea405bd48f010a01ad2911d9c6dd039bb61a6290e591b 2881 36e636a5c871a5c29f4f83060400f8b49cba8f6aa8 2883 o k_(4,11) = 0xaccbb67481d033ff5852c1e48c50c477f94ff8aefce42d28c0f9a 2884 88cea7913516f968986f7ebbea9684b529e2561092 2886 o k_(4,12) = 0xad6b9514c767fe3c3613144b45f1496543346d98adf02267d5cee 2887 f9a00d9b8693000763e3b90ac11e99b138573345cc 2889 o k_(4,13) = 0x2660400eb2e4f3b628bdd0d53cd76f2bf565b94e72927c1cb748d 2890 f27942480e420517bd8714cc80d1fadc1326ed06f7 2892 o k_(4,14) = 0xe0fa1d816ddc03e6b24255e0d7819c171c40f65e273b853324efc 2893 d6356caa205ca2f570f13497804415473a1d634b8f 2895 C.3. 3-isogeny map for BLS12-381 G2 2897 The 3-isogeny map from (x', y') on E' to (x, y) on E is given by the 2898 following rational functions: 2900 o x = x_num / x_den, where 2902 * x_num = k_(1,3) * x'^3 + k_(1,2) * x'^2 + k_(1,1) * x' + 2903 k_(1,0) 2905 * x_den = x'^2 + k_(2,1) * x' + k_(2,0) 2907 o y = y' * y_num / y_den, where 2908 * y_num = k_(3,3) * x'^3 + k_(3,2) * x'^2 + k_(3,1) * x' + 2909 k_(3,0) 2911 * y_den = x'^3 + k_(4,2) * x'^2 + k_(4,1) * x' + k_(4,0) 2913 The constants used to compute x_num are as follows: 2915 o k_(1,0) = 0x5c759507e8e333ebb5b7a9a47d7ed8532c52d39fd3a042a88b5842 2916 3c50ae15d5c2638e343d9c71c6238aaaaaaaa97d6 + 0x5c759507e8e333ebb5b7 2917 a9a47d7ed8532c52d39fd3a042a88b58423c50ae15d5c2638e343d9c71c6238aaa 2918 aaaaa97d6 * I 2920 o k_(1,1) = 0x11560bf17baa99bc32126fced787c88f984f87adf7ae0c7f9a208c 2921 6b4f20a4181472aaa9cb8d555526a9ffffffffc71a * I 2923 o k_(1,2) = 0x11560bf17baa99bc32126fced787c88f984f87adf7ae0c7f9a208c 2924 6b4f20a4181472aaa9cb8d555526a9ffffffffc71e + 0x8ab05f8bdd54cde1909 2925 37e76bc3e447cc27c3d6fbd7063fcd104635a790520c0a395554e5c6aaaa9354ff 2926 ffffffe38d * I 2928 o k_(1,3) = 0x171d6541fa38ccfaed6dea691f5fb614cb14b4e7f4e810aa22d610 2929 8f142b85757098e38d0f671c7188e2aaaaaaaa5ed1 2931 The constants used to compute x_den are as follows: 2933 o k_(2,0) = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2 2934 a0f6b0f6241eabfffeb153ffffb9feffffffffaa63 * I 2936 o k_(2,1) = 0xc + 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf 2937 6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaa9f * I 2939 The constants used to compute y_num are as follows: 2941 o k_(3,0) = 0x1530477c7ab4113b59a4c18b076d11930f7da5d4a07f649bf54439 2942 d87d27e500fc8c25ebf8c92f6812cfc71c71c6d706 + 0x1530477c7ab4113b59a 2943 4c18b076d11930f7da5d4a07f649bf54439d87d27e500fc8c25ebf8c92f6812cfc 2944 71c71c6d706 * I 2946 o k_(3,1) = 0x5c759507e8e333ebb5b7a9a47d7ed8532c52d39fd3a042a88b5842 2947 3c50ae15d5c2638e343d9c71c6238aaaaaaaa97be * I 2949 o k_(3,2) = 0x11560bf17baa99bc32126fced787c88f984f87adf7ae0c7f9a208c 2950 6b4f20a4181472aaa9cb8d555526a9ffffffffc71c + 0x8ab05f8bdd54cde1909 2951 37e76bc3e447cc27c3d6fbd7063fcd104635a790520c0a395554e5c6aaaa9354ff 2952 ffffffe38f * I 2954 o k_(3,3) = 0x124c9ad43b6cf79bfbf7043de3811ad0761b0f37a1e26286b0e977 2955 c69aa274524e79097a56dc4bd9e1b371c71c718b10 2957 The constants used to compute y_den are as follows: 2959 o k_(4,0) = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2 2960 a0f6b0f6241eabfffeb153ffffb9feffffffffa8fb + 0x1a0111ea397fe69a4b1 2961 ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9fef 2962 fffffffa8fb * I 2964 o k_(4,1) = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2 2965 a0f6b0f6241eabfffeb153ffffb9feffffffffa9d3 * I 2967 o k_(4,2) = 0x12 + 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512b 2968 f6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaa99 * I 2970 Appendix D. Sample Code 2972 This section gives sample implementations optimized for some of the 2973 elliptic curves listed in Section 8. A future version of this 2974 document will include all listed curves, plus accompanying test 2975 vectors. Sample Sage [SAGE] code for each algorithm can also be 2976 found in the draft repository [hash2curve-repo]. 2978 D.1. Interface and projective coordinate systems 2980 The sample code in this section uses a different interface than the 2981 mappings of Section 6. Specifically, each mapping function in this 2982 section has the following signature: 2984 (xn, xd, yn, nd) = map_to_curve(u) 2986 The resulting point (x, y) is given by (xn / xd, yn / yd). 2988 The reason for this modified interface is that it enables further 2989 optimizations when working with points in a projective coordinate 2990 system. This is desirable, for example, when the resulting point 2991 will be immediately multiplied by a scalar, since most scalar 2992 multiplication algorithms operate on projective points. 2994 The following are two commonly used projective coordinate systems and 2995 the corresponding conversions: 2997 o A point (X, Y, Z) in homogeneous projective coordinates 2998 corresponds to the affine point (x, y) = (X / Z, Y / Z); the 2999 inverse conversion is given by (X, Y, Z) = (x, y, 1). To convert 3000 (xn, xd, yn, yd) to homogeneous projective coordinates, compute 3001 (X, Y, Z) = (xn * yd, yn * xd, xd * yd). 3003 o A point (X', Y', Z') in Jacobian projective coordinates 3004 corresponds to the affine point (x, y) = (X' / Z'^2, Y' / Z'^3); 3005 the inverse conversion is given by (X', Y', Z') = (x, y, 1). To 3006 convert (xn, xd, yn, yd) to Jacobian projective coordinates, 3007 compute (X', Y', Z') = (xn * xd * yd^2, yn * yd^2 * xd^3, xd * 3008 yd). 3010 D.2. Simplified SWU for p = 3 (mod 4) 3012 The following is a straight-line implementation of the Simplified SWU 3013 mapping that applies to any curve over GF(p) for p = 3 (mod 4). This 3014 includes the ciphersuites for NIST curves P-256, P-384, and P-521 3015 [FIPS186-4] given in Section 8. It also includes the curves 3016 isogenous to secp256k1 (Section 8.8) and BLS12-381 G1 3017 (Section 8.9.1). 3019 The implementations for these curves differ only in the constants and 3020 the base field. The constant definitions below are given in terms of 3021 the parameters for the Simplified SWU mapping; for parameter values 3022 for the curves listed above, see Section 8.3 (P-256), Section 8.4 3023 (P-384), Section 8.5 (P-521), Section 8.8 (E' isogenous to 3024 secp256k1), and Section 8.9.1 (E' isogenous to BLS12-381 G1). 3026 map_to_curve_simple_swu_3mod4(u) 3028 Input: u, an element of F. 3029 Output: (xn, xd, yn, yd) such that (xn / xd, yn / yd) is a 3030 point on the target curve. 3032 Constants: defined per curve; see above. 3033 1. c1 = B / 3 3034 2. c2 = (p - 3) / 4 // Integer arithmetic 3035 3. c3 = sqrt(-Z^3) 3037 Steps: 3038 1. t1 = u^2 3039 2. t3 = Z * t1 3040 3. t2 = t3^2 3041 4. xd = t2 + t3 3042 5. x1n = xd + 1 3043 6. x1n = x1n * B 3044 7. xd = -A * xd 3045 8. e1 = xd == 0 3046 9. xd = CMOV(xd, Z * A, e1) // If xd == 0, set xd = Z * A 3047 10. t2 = xd^2 3048 11. gxd = t2 * xd // gxd == xd^3 3049 12. t2 = A * t2 3050 13. gx1 = x1n^2 3051 14. gx1 = gx1 + t2 // x1n^2 + A * xd^2 3052 15. gx1 = gx1 * x1n // x1n^3 + A * x1n * xd^2 3053 16. t2 = B * gxd 3054 17. gx1 = gx1 + t2 // x1n^3 + A * x1n * xd^2 + B * xd^3 3055 18. t4 = gxd^2 3056 19. t2 = gx1 * gxd 3057 20. t4 = t4 * t2 // gx1 * gxd^3 3058 21. y1 = t4^c2 // (gx1 * gxd^3)^((p - 3) / 4) 3059 22. y1 = y1 * t2 // gx1 * gxd * (gx1 * gxd^3)^((p - 3) / 4) 3060 23. x2n = t3 * x1n // x2 = x2n / xd = -10 * u^2 * x1n / xd 3061 24. y2 = y1 * c3 // y2 = y1 * sqrt(-Z^3) 3062 25. y2 = y2 * t1 3063 26. y2 = y2 * u 3064 27. t2 = y1^2 3065 28. t2 = t2 * gxd 3066 29. e2 = t2 == gx1 3067 30. xn = CMOV(x2n, x1n, e2) // If e2, x = x1, else x = x2 3068 31. y = CMOV(y2, y1, e2) // If e2, y = y1, else y = y2 3069 32. e3 = sgn0(u) == sgn0(y) // Fix sign of y 3070 33. y = CMOV(-y, y, e3) 3071 34. return (xn, xd, y, 1) 3072 D.3. curve25519 (Elligator 2) 3074 The following is a straight-line implementation of Elligator 2 for 3075 curve25519 [RFC7748] as specified in Section 8.6. 3077 map_to_curve_elligator2_curve25519(u) 3079 Input: u, an element of F. 3080 Output: (xn, xd, yn, yd) such that (xn / xd, yn / yd) is a 3081 point on curve25519. 3083 Constants: 3084 1. c1 = (p + 3) / 8 // Integer arithmetic 3085 2. c2 = 2^c1 3086 3. c3 = sqrt(-1) 3087 4. c4 = (p - 5) / 8 // Integer arithmetic 3089 Steps: 3090 1. t1 = u^2 3091 2. t1 = 2 * t1 3092 3. xd = t1 + 1 // Nonzero: -1 is square (mod p), t1 is not 3093 4. x1n = -486662 // x1 = x1n / xd = -486662 / (1 + 2 * u^2) 3094 5. t2 = xd^2 3095 6. gxd = t2 * xd // gxd = xd^3 3096 7. gx1 = 486662 * xd // 486662 * xd 3097 8. gx1 = gx1 + x1n // x1n + 486662 * xd 3098 9. gx1 = gx1 * x1n // x1n^2 + 486662 * x1n * xd 3099 10. gx1 = gx1 + t2 // x1n^2 + 486662 * x1n * xd + xd^2 3100 11. gx1 = gx1 * x1n // x1n^3 + 486662 * x1n^2 * xd + x1n * xd^2 3101 12. t3 = gxd^2 3102 13. t2 = t3^2 // gxd^4 3103 14. t3 = t3 * gxd // gxd^3 3104 15. t3 = t3 * gx1 // gx1 * gxd^3 3105 16. t2 = t2 * t3 // gx1 * gxd^7 3106 17. y11 = t2^c4 // (gx1 * gxd^7)^((p - 5) / 8) 3107 18. y11 = y11 * t3 // gx1 * gxd^3 * (gx1 * gxd^7)^((p - 5) / 8) 3108 19. y12 = y11 * c3 3109 20. t2 = y11^2 3110 21. t2 = t2 * gxd 3111 22. e1 = t2 == gx1 3112 23. y1 = CMOV(y12, y11, e1) // If g(x1) is square, this is its sqrt 3113 24. x2n = x1n * t1 // x2 = x2n / xd = 2 * u^2 * x1n / xd 3114 25. y21 = y11 * u 3115 26. y21 = y21 * c2 3116 27. y22 = y21 * c3 3117 28. gx2 = gx1 * t1 // g(x2) = gx2 / gxd = 2 * u^2 * g(x1) 3118 29. t2 = y21^2 3119 30. t2 = t2 * gxd 3120 31. e2 = t2 == gx2 3121 32. y2 = CMOV(y22, y21, e2) // If g(x2) is square, this is its sqrt 3122 33. t2 = y1^2 3123 34. t2 = t2 * gxd 3124 35. e3 = t2 == gx1 3125 36. xn = CMOV(x2n, x1n, e3) // If e3, x = x1, else x = x2 3126 37. y = CMOV(y2, y1, e3) // If e3, y = y1, else y = y2 3127 38. e4 = sgn0(u) == sgn0(y) // Fix sign of y 3128 39. y = CMOV(-y, y, e4) 3129 40. return (xn, xd, y, 1) 3131 D.4. edwards25519 (Elligator 2) 3133 The following is a straight-line implementation of Elligator 2 for 3134 edwards25519 [RFC7748] as specified in Section 8.6. The subroutine 3135 map_to_curve_elligator2_curve25519 is defined in Appendix D.3. 3137 map_to_curve_elligator2_edwards25519(u) 3139 Input: u, an element of F. 3140 Output: (xn, xd, yn, yd) such that (xn / xd, yn / yd) is a 3141 point on edwards25519. 3143 Constants: 3144 1. c1 = sqrt(-486664) // sgn0(c1) MUST equal 1 3146 Steps: 3147 1. (xMn, xMd, yMn, yMd) = map_to_curve_elligator2_curve25519(u) 3148 2. xn = xMn * yMd 3149 3. xn = xn * c1 3150 4. xd = xMd * yMn // xn / xd = c1 * xM / yM 3151 5. yn = xMn - xMd 3152 6. yd = xMn + xMd // (n / d - 1) / (n / d + 1) = (n - d) / (n + d) 3153 7. t1 = xd * yd 3154 8. e = t1 == 0 3155 9. xn = CMOV(xn, 0, e) 3156 10. xd = CMOV(xd, 1, e) 3157 11. yn = CMOV(yn, 1, e) 3158 12. yd = CMOV(yd, 1, e) 3159 13. return (xn, xd, yn, yd) 3161 D.5. curve448 (Elligator 2) 3163 The following is a straight-line implementation of Elligator 2 for 3164 curve448 [RFC7748] as specified in Section 8.7. 3166 map_to_curve_elligator2_curve448(u) 3168 Input: u, an element of F. 3169 Output: (xn, xd, yn, yd) such that (xn / xd, yn / yd) is a 3170 point on curve448. 3172 Constants: 3173 1. c1 = (p - 3) / 4 // Integer arithmetic 3175 Steps: 3176 1. t1 = u^2 3177 2. e1 = t1 == 1 3178 3. t1 = CMOV(t1, 0, e1) // If Z * u^2 == -1, set t1 = 0 3179 4. xd = 1 - t1 3180 5. x1n = -156326 3181 6. t2 = xd^2 3182 7. gxd = t2 * xd // gxd = xd^3 3183 8. gx1 = 156326 * xd // 156326 * xd 3184 9. gx1 = gx1 + x1n // x1n + 156326 * xd 3185 10. gx1 = gx1 * x1n // x1n^2 + 156326 * x1n * xd 3186 11. gx1 = gx1 + t2 // x1n^2 + 156326 * x1n * xd + xd^2 3187 12. gx1 = gx1 * x1n // x1n^3 + 156326 * x1n^2 * xd + x1n * xd^2 3188 13. t3 = gxd^2 3189 14. t2 = gx1 * gxd // gx1 * gxd 3190 15. t3 = t3 * t2 // gx1 * gxd^3 3191 16. y1 = t3^c1 // (gx1 * gxd^3)^((p - 3) / 4) 3192 17. y1 = y1 * t2 // gx1 * gxd * (gx1 * gxd^3)^((p - 3) / 4) 3193 18. x2n = -t1 * x1n // x2 = x2n / xd = -1 * u^2 * x1n / xd 3194 19. y2 = y1 * u 3195 20. y2 = CMOV(y2, 0, e1) 3196 21. t2 = y1^2 3197 22. t2 = t2 * gxd 3198 23. e2 = t2 == gx1 3199 24. xn = CMOV(x2n, x1n, e2) // If e2, x = x1, else x = x2 3200 25. y = CMOV(y2, y1, e2) // If e2, y = y1, else y = y2 3201 26. e3 = sgn0(u) == sgn0(y) // Fix sign of y 3202 27. y = CMOV(-y, y, e3) 3203 28. return (xn, xd, y, 1) 3205 D.6. edwards448 (Elligator 2) 3207 The following is a straight-line implementation of Elligator 2 for 3208 edwards448 [RFC7748] as specified in Section 8.7. The subroutine 3209 map_to_curve_elligator2_curve448 is defined in Appendix D.5. 3211 map_to_curve_elligator2_edwards448(u) 3213 Input: u, an element of F. 3214 Output: (xn, xd, yn, yd) such that (xn / xd, yn / yd) is a 3215 point on edwards448. 3217 Steps: 3218 1. (xn, xd, yn, yd) = map_to_curve_elligator2_curve448(u) 3219 2. xn2 = xn^2 3220 3. xd2 = xd^2 3221 4. xd4 = xd2^2 3222 5. yn2 = yn^2 3223 6. yd2 = yd^2 3224 7. xEn = xn2 - xd2 3225 8. t2 = xEn - xd2 3226 9. xEn = xEn * xd2 3227 10. xEn = xEn * yd 3228 11. xEn = xEn * yn 3229 12. xEn = xEn * 4 3230 13. t2 = t2 * xn2 3231 14. t2 = t2 * yd2 3232 15. t3 = 4 * yn2 3233 16. t1 = t3 + yd2 3234 17. t1 = t1 * xd4 3235 18. xEd = t1 + t2 3236 19. t2 = t2 * xn 3237 20. t4 = xn * xd4 3238 21. yEn = t3 - yd2 3239 22. yEn = yEn * t4 3240 23. yEn = yEn - t2 3241 24. t1 = xn2 + xd2 3242 25. t1 = t1 * xd2 3243 26. t1 = t1 * xd 3244 27. t1 = t1 * yn2 3245 28. t1 = -2 * t1 3246 29. yEd = t2 + t1 3247 30. t4 = t4 * yd2 3248 31. yEd = yEd + t4 3249 32. t1 = xEd * yEd 3250 33. e = t1 == 0 3251 34. xEn = CMOV(xEn, 0, e) 3252 35. xEd = CMOV(xEd, 1, e) 3253 36. yEn = CMOV(yEn, 1, e) 3254 37. yEd = CMOV(yEd, 1, e) 3255 38. return (xEn, xEd, yEn, yEd) 3257 Appendix E. Scripts for parameter generation 3259 This section gives Sage [SAGE] scripts used to generate parameters 3260 for the mappings of Section 6. 3262 E.1. Finding Z for the Shallue and van de Woestijne map 3264 The below function outputs an appropriate Z for the Shallue and van 3265 de Woestijne map (Section 6.6.1). 3267 def find_z_svdw(F, A, B): 3268 g = lambda x: F(x)^3 + F(A) * F(x) + F(B) 3269 h = lambda Z: -(F(3) * Z^2 + F(4) * A) / (F(4) * g(Z)) 3270 ctr = F.gen() 3271 while True: 3272 for Z_cand in (F(ctr), F(-ctr)): 3273 if g(Z_cand) == F(0): 3274 # Criterion 1: g(Z) != 0 in F. 3275 continue 3276 if h(Z_cand) == F(0): 3277 # Criterion 2: -(3 * Z^2 + 4 * A) / (4 * g(Z)) != 0 in F. 3278 continue 3279 if not h(Z_cand).is_square(): 3280 # Criterion 3: -(3 * Z^2 + 4 * A) / (4 * g(Z)) is square in F. 3281 continue 3282 if g(Z_cand).is_square() or g(-Z_cand / F(2)).is_square(): 3283 # Criterion 4: At least one of g(Z) and g(-Z / 2) is square in F. 3284 return Z_cand 3285 ctr += 1 3287 E.2. Finding Z for Simplified SWU 3289 The below function outputs an appropriate Z for the Simplified SWU 3290 map (Section 6.6.2). 3292 # Arguments: 3293 # - F, a field object, e.g., F = GF(2^521 - 1) 3294 # - A and B, the coefficients of the curve equation y^2 = x^3 + A * x + B 3295 def find_z_sswu(F, A, B): 3296 R. = F[] # Polynomial ring over F 3297 g = xx^3 + F(A) * xx + F(B) # y^2 = g(x) = x^3 + A * x + B 3298 ctr = F.gen() 3299 while True: 3300 for Z_cand in (F(ctr), F(-ctr)): 3301 if Z_cand.is_square(): 3302 # Criterion 1: Z is non-square in F. 3303 continue 3304 if Z_cand == F(-1): 3305 # Criterion 2: Z != -1 in F. 3306 continue 3307 if not (g - Z_cand).is_irreducible(): 3308 # Criterion 3: g(x) - Z is irreducible over F. 3309 continue 3310 if g(B / (Z_cand * A)).is_square(): 3311 # Criterion 4: g(B / (Z * A)) is square in F. 3312 return Z_cand 3313 ctr += 1 3315 E.3. Finding Z for Elligator 2 3317 The below function outputs an appropriate Z for the Elligator 2 map 3318 (Section 6.7.1). 3320 # Argument: 3321 # - F, a field object, e.g., F = GF(2^255 - 19) 3322 def find_z_ell2(F): 3323 ctr = F.gen() 3324 while True: 3325 for Z_cand in (F(ctr), F(-ctr)): 3326 if Z_cand.is_square(): 3327 # Z must be a non-square in F. 3328 continue 3329 return Z_cand 3330 ctr += 1 3332 Appendix F. sqrt functions 3334 This section defines special-purpose sqrt functions for the three 3335 most common cases, p = 3 (mod 4), p = 5 (mod 8), and p = 9 (mod 16). 3336 In addition, it gives a generic constant-time algorithm that works 3337 for any prime modulus. 3339 F.1. p = 3 (mod 4) 3341 sqrt_3mod4(x) 3343 Parameters: 3344 - F, a finite field of characteristic p and order q = p^m. 3345 - p, the characteristic of F (see immediately above). 3346 - m, the extension degree of F, m >= 1 (see immediately above). 3348 Input: x, an element of F. 3349 Output: s, an element of F such that (s^2) == x. 3351 Constants: 3352 1. c1 = (q + 1) / 4 // Integer arithmetic 3354 Procedure: 3355 1. return x^c1 3357 F.2. p = 5 (mod 8) 3359 sqrt_5mod8(x) 3361 Parameters: 3362 - F, a finite field of characteristic p and order q = p^m. 3363 - p, the characteristic of F (see immediately above). 3364 - m, the extension degree of F, m >= 1 (see immediately above). 3366 Input: x, an element of F. 3367 Output: s, an element of F such that (s^2) == x. 3369 Constants: 3370 1. c1 = sqrt(-1) in F, i.e., (c1^2) == -1 in F 3371 2. c2 = (q + 3) / 8 // Integer arithmetic 3373 Procedure: 3374 1. t1 = x^c2 3375 2. e = (t1^2) == x 3376 3. s = CMOV(t1 * c1, t1, e) 3377 3. return s 3379 F.3. p = 9 (mod 16) 3381 Note that this case also applies to GF(p^2) when p = 3 (mod 8). 3382 [AR13] and [S85] describe methods that work for other field 3383 extensions. 3385 sqrt_9mod16(x) 3387 Parameters: 3388 - F, a finite field of characteristic p and order q = p^m. 3389 - p, the characteristic of F (see immediately above). 3390 - m, the extension degree of F, m >= 1 (see immediately above). 3392 Input: x, an element of F. 3393 Output: s, an element of F such that (s^2) == x. 3395 Constants: 3396 1. c1 = sqrt(-1) in F, i.e., (c1^2) == -1 in F 3397 2. c2 = sqrt(c1) in F, i.e., (c2^2) == c1 in F 3398 3. c3 = sqrt(-c1) in F, i.e., (c3^2) == -c1 in F 3399 4. c4 = (q + 7) / 16 // Integer arithmetic 3401 Procedure: 3402 1. t1 = x^c4 3403 2. t2 = c1 * t1 3404 3. t3 = c2 * t1 3405 4. t4 = c3 * t1 3406 5. e1 = (t2^2) == x 3407 6. e2 = (t3^2) == x 3408 7. t1 = CMOV(t1, t2, e1) // Select t2 if (t2^2) == x 3409 8. t2 = CMOV(t4, t3, e2) // Select t3 if (t3^2) == x 3410 9. e3 = (t2^2) == x 3411 10. s = CMOV(t1, t2, e3) // Select the sqrt from t1 and t2 3412 11. return s 3414 F.4. Constant-time Tonelli-Shanks algorithm 3416 This algorithm is a constant-time version of the classic Tonelli- 3417 Shanks algorithm ([C93], Algorithm 1.5.1) due to Sean Bowe, Jack 3418 Grigg, and Eirik Ogilvie-Wigley [jubjub-fq], adapted and optimized by 3419 Michael Scott. 3421 This algorithm applies to GF(p) for any p. Note, however, that the 3422 special-purpose algorithms given in the prior sections are faster, 3423 when they apply. 3425 sqrt_ts_ct(x) 3427 Parameters: 3428 - F, a finite field of order p 3429 - p, the characteristic of F (see immediately above) 3431 Input x, an element of F. 3432 Output: r, an element of F such that (r^2) == 2. 3434 Constants (see discussion below): 3435 1. c1, the largest integer such that 2^c1 divides p - 1. 3436 2. c2 = (p - 1) / (2^c1) // Integer arithmetic 3437 3. c3 = (c2 - 1) / 2 // Integer arithmetic 3438 4. c4, a non-square value in F 3439 5. c5 = c4^c2 in F 3441 Procedure: 3442 1. r = x^c3 3443 2. t = r * r * x 3444 3. r = r * x 3445 4. b = t 3446 5. c = c5 3447 6. for k in (m, m - 1, ..., 2): 3448 7. for j in (1, 2, ..., k - 1): 3449 8. b = b * b 3450 9. r = CMOV(r, r * c, b != 1) 3451 10. c = c * c 3452 11. t = CMOV(t, t * c, b != 1) 3453 12. b = t 3454 13. return r 3456 The constants used in this procedure can be computed as follows: 3458 precompute_ts(p) 3460 Input: p, a prime 3461 Output: the required constants c1, ..., c5 3463 Procedure: 3464 1. c1 = 0 3465 2. c2 = p - 1 3466 3. while c2 is even: 3467 4. c2 = c2 / 2 // Integer arithmetic 3468 5. c1 = c1 + 1 3469 6. c3 = (c2 - 1) / 2 // Integer arithmetic 3470 7. c4 = 1 3471 8. while c4 is square mod p: 3472 9. c4 = c4 + 1 3473 10. c5 = c4^c2 mod p 3474 11. return (c1, c2, c3, c4, c5) 3476 Authors' Addresses 3478 Armando Faz-Hernandez 3479 Cloudflare 3480 101 Townsend St 3481 San Francisco 3482 United States of America 3484 Email: armfazh@cloudflare.com 3486 Sam Scott 3487 Cornell Tech 3488 2 West Loop Rd 3489 New York, New York 10044 3490 United States of America 3492 Email: sam.scott@cornell.edu 3494 Nick Sullivan 3495 Cloudflare 3496 101 Townsend St 3497 San Francisco 3498 United States of America 3500 Email: nick@cloudflare.com 3501 Riad S. Wahby 3502 Stanford University 3504 Email: rsw@cs.stanford.edu 3506 Christopher A. Wood 3507 Apple Inc. 3508 One Apple Park Way 3509 Cupertino, California 95014 3510 United States of America 3512 Email: cawood@apple.com