idnits 2.17.00 (12 Aug 2021) /tmp/idnits54103/draft-irtf-cfrg-ristretto255-decaf448-03.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 24 instances of too long lines in the document, the longest one being 6 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document date (25 February 2022) is 78 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: '10' on line 1059 -- Looks like a reference, but probably isn't: '11' on line 1061 -- Looks like a reference, but probably isn't: '12' on line 1063 -- Looks like a reference, but probably isn't: '13' on line 1065 -- Looks like a reference, but probably isn't: '14' on line 1067 -- Looks like a reference, but probably isn't: '15' on line 1069 -- Looks like a reference, but probably isn't: '1' on line 896 Summary: 1 error (**), 0 flaws (~~), 0 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Crypto Forum Research Group H. de Valence 3 Internet-Draft 4 Intended status: Informational J. Grigg 5 Expires: 29 August 2022 6 M. Hamburg 8 I. Lovecruft 10 G. Tankersley 12 F. Valsorda 13 25 February 2022 15 The ristretto255 and decaf448 Groups 16 draft-irtf-cfrg-ristretto255-decaf448-03 18 Abstract 20 This memo specifies two prime-order groups, ristretto255 and 21 decaf448, suitable for safely implementing higher-level and complex 22 cryptographic protocols. The ristretto255 group can be implemented 23 using Curve25519, allowing existing Curve25519 implementations to be 24 reused and extended to provide a prime-order group. Likewise, the 25 decaf448 group can be implemented using edwards448. 27 Status of This Memo 29 This Internet-Draft is submitted in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF). Note that other groups may also distribute 34 working documents as Internet-Drafts. The list of current Internet- 35 Drafts is at https://datatracker.ietf.org/drafts/current/. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 This Internet-Draft will expire on 29 August 2022. 44 Copyright Notice 46 Copyright (c) 2022 IETF Trust and the persons identified as the 47 document authors. All rights reserved. 49 This document is subject to BCP 78 and the IETF Trust's Legal 50 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 51 license-info) in effect on the date of publication of this document. 52 Please review these documents carefully, as they describe your rights 53 and restrictions with respect to this document. Code Components 54 extracted from this document must include Revised BSD License text as 55 described in Section 4.e of the Trust Legal Provisions and are 56 provided without warranty as described in the Revised BSD License. 58 Table of Contents 60 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 61 2. Notation and Conventions Used In This Document . . . . . . . 4 62 2.1. Negative field elements . . . . . . . . . . . . . . . . . 5 63 2.2. Constant time operations . . . . . . . . . . . . . . . . 5 64 3. The group abstraction . . . . . . . . . . . . . . . . . . . . 5 65 4. ristretto255 . . . . . . . . . . . . . . . . . . . . . . . . 6 66 4.1. Internal constants . . . . . . . . . . . . . . . . . . . 7 67 4.2. Square root of a ratio of field elements . . . . . . . . 7 68 4.3. External ristretto255 functions . . . . . . . . . . . . . 8 69 4.3.1. Decode . . . . . . . . . . . . . . . . . . . . . . . 8 70 4.3.2. Encode . . . . . . . . . . . . . . . . . . . . . . . 9 71 4.3.3. Equals . . . . . . . . . . . . . . . . . . . . . . . 10 72 4.3.4. One-way map . . . . . . . . . . . . . . . . . . . . . 11 73 4.4. Scalar field . . . . . . . . . . . . . . . . . . . . . . 12 74 5. decaf448 . . . . . . . . . . . . . . . . . . . . . . . . . . 12 75 5.1. Internal constants . . . . . . . . . . . . . . . . . . . 13 76 5.2. Square root of a ratio of field elements . . . . . . . . 14 77 5.3. External decaf448 functions . . . . . . . . . . . . . . . 15 78 5.3.1. Decode . . . . . . . . . . . . . . . . . . . . . . . 15 79 5.3.2. Encode . . . . . . . . . . . . . . . . . . . . . . . 15 80 5.3.3. Equals . . . . . . . . . . . . . . . . . . . . . . . 16 81 5.3.4. One-way map . . . . . . . . . . . . . . . . . . . . . 16 82 5.4. Scalar field . . . . . . . . . . . . . . . . . . . . . . 17 83 6. API Considerations . . . . . . . . . . . . . . . . . . . . . 17 84 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 85 8. Security Considerations . . . . . . . . . . . . . . . . . . . 18 86 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 18 87 10. Normative References . . . . . . . . . . . . . . . . . . . . 18 88 11. Informative References . . . . . . . . . . . . . . . . . . . 19 89 Appendix A. Test vectors for ristretto255 . . . . . . . . . . . 19 90 A.1. Multiples of the generator . . . . . . . . . . . . . . . 20 91 A.2. Invalid encodings . . . . . . . . . . . . . . . . . . . . 20 92 A.3. Group elements from uniform byte strings . . . . . . . . 21 93 A.4. Square root of a ratio of field elements . . . . . . . . 22 94 Appendix B. Test vectors for decaf448 . . . . . . . . . . . . . 23 95 B.1. Multiples of the generator . . . . . . . . . . . . . . . 23 96 B.2. Invalid encodings . . . . . . . . . . . . . . . . . . . . 24 97 B.3. Group elements from uniform byte strings . . . . . . . . 26 98 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 27 100 1. Introduction 102 Decaf [Decaf] is a technique for constructing prime-order groups with 103 non-malleable encodings from non-prime-order elliptic curves. 104 Ristretto extends this technique to support cofactor-8 curves such as 105 Curve25519 [RFC7748]. In particular, this allows an existing 106 Curve25519 library to provide a prime-order group with only a thin 107 abstraction layer. 109 Edwards curves provide a number of implementation benefits for 110 cryptography, such as complete addition formulas with no exceptional 111 points and formulas among the fastest known for curve operations. 112 However, the group of points on the curve is not of prime order, 113 i.e., it has a cofactor larger than 1. This abstraction mismatch is 114 usually handled by means of ad-hoc protocol tweaks (such as 115 multiplying by the cofactor in an appropriate place), or not at all. 117 Even for simple protocols such as signatures, these tweaks can cause 118 subtle issues. For instance, Ed25519 implementations may have 119 different validation behavior between batched and singleton 120 verification, and at least as specified in [RFC8032], the set of 121 valid signatures is not defined by the standard. 123 For more complex protocols, careful analysis is required as the 124 original security proofs may no longer apply, and the tweaks for one 125 protocol may have disastrous effects when applied to another (for 126 instance, the octuple-spend vulnerability in [MoneroVuln]). 128 Decaf and Ristretto fix this abstraction mismatch in one place for 129 all protocols, providing an abstraction to protocol implementors that 130 matches the abstraction commonly assumed in protocol specifications, 131 while still allowing the use of high-performance curve 132 implementations internally. The abstraction layer imposes minor 133 overhead, and only in the encoding and decoding phases. 135 While Ristretto is a general method, and can be used in conjunction 136 with any Edwards curve with cofactor 4 or 8, this document specifies 137 the ristretto255 group, which can be implemented using Curve25519, 138 and the decaf448 group, which can be implemented using edwards448. 140 There are other elliptic curves that can be used internally to 141 implement ristretto255 or decaf448, and those implementations would 142 be interoperable with a Curve25519- or edwards448-based one, but 143 those constructions are out-of-scope for this document. 145 The Ristretto construction is described and justified in detail at 146 [RistrettoGroup]. 148 2. Notation and Conventions Used In This Document 150 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 151 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 152 "OPTIONAL" in this document are to be interpreted as described in BCP 153 14 [RFC2119] [RFC8174] when, and only when, they appear in all 154 capitals, as shown here. 156 Readers are cautioned that the term "Curve25519" has varying 157 interpretations in the literature, and that the canonical meaning of 158 the term has shifted over time. Originally it referred to a specific 159 Diffie-Hellman key exchange mechanism. Over time, use shifted, and 160 "Curve25519" has been used to refer to either the abstract underlying 161 curve, or its concrete representation in Montgomery form, or the 162 specific Diffie-Hellman mechanism. This document uses the term 163 "Curve25519" to refer to the abstract underlying curve, as 164 recommended in [Naming]. The abstract Edwards form of the curve we 165 refer to here as "Curve25519" is in [RFC7748] referred to as 166 "edwards25519" and its isogenous Montgomery form is referred to as 167 "curve25519". 169 Elliptic curve points in this document are represented in extended 170 Edwards coordinates in the (x, y, z, t) format [Twisted], also called 171 extended homogeneous coordinates in Section 5.1.4 of [RFC8032]. 172 Field elements are values modulo p, the Curve25519 prime 2^255 - 19 173 or the edwards448 prime 2^448 - 2^224 - 1, as specified in Sections 174 4.1 and 4.2 of [RFC7748], respectively. All formulas specify field 175 operations unless otherwise noted. 177 The | symbol represents a constant-time logical OR. 179 The notation array[A:B] means the elements of array from A to B-1. 180 That is, it is exclusive of B. Arrays are indexed starting from 0. 182 A byte is an 8-bit entity (also known as "octet") and a byte string 183 is an ordered sequence of bytes. A N-byte string is a byte string of 184 N bytes length. 186 Element encodings are presented as hex encoded byte strings with 187 whitespace added for readability. 189 2.1. Negative field elements 191 As in [RFC8032], given a field element e, define IS_NEGATIVE(e) as 192 TRUE if the least non-negative integer representing e is odd, and 193 FALSE if it is even. This SHOULD be implemented in constant time. 195 2.2. Constant time operations 197 We assume that the field element implementation supports the 198 following operations, which SHOULD be implemented in constant time: 200 * CT_EQ(u, v): return TRUE if u = v, FALSE otherwise. 202 * CT_SELECT(v IF cond ELSE u): return v if cond is TRUE, else return 203 u. 205 * CT_ABS(u): return -u if u is negative, else return u. 207 Note that CT_ABS MAY be implemented as: 209 CT_SELECT(-u IF IS_NEGATIVE(u) ELSE u) 211 3. The group abstraction 213 Ristretto and Decaf implement an abstract prime-order group interface 214 that exposes only the behavior that is useful to higher-level 215 protocols, without leaking curve-related details and pitfalls. 217 The only operations exposed by each abstract group are decoding, 218 encoding, equality, a one-way map, addition, negation, and the 219 derived subtraction and (multi-)scalar multiplication. 221 Decoding is a function from byte strings to abstract elements with 222 built-in validation, so that only the canonical encodings of valid 223 elements are accepted. The built-in validation avoids the need for 224 explicit invalid curve checks. 226 Encoding is a function from abstract elements to byte strings so that 227 all equivalent representations of the same element are encoded as 228 identical byte strings. Decoding the output of the encoding function 229 always succeeds and returns an equivalent element to the encoding 230 input. 232 The equality check reports whether two representations of an abstract 233 element are equivalent. 235 The one-way map is a function from uniformly distributed byte strings 236 of a fixed length to uniformly distributed abstract elements. This 237 map is suitable for hash-to-group operations and to select random 238 elements. The map is not invertible, but also not pre-image 239 resistant, meaning an attacker can find a valid input for a given 240 output. 242 Addition is the group operation. The group has an identity element 243 and prime order. Adding an element to itself as many times as the 244 order of the group returns the identity element. Adding the identity 245 element to any element returns that element unchanged. Negation 246 returns an element that added to the negation input returns the 247 identity element. Subtraction is the addition of a negated element, 248 and scalar multiplication is the repeated addition of an element. 250 4. ristretto255 252 ristretto255 is an instantiation of the abstract prime-order group 253 interface defined in Section 3. This document describes how to 254 implement the ristretto255 prime-order group using Curve25519 points 255 as internal representations. 257 A "ristretto255 group element" is the abstract element of the prime 258 order group. An "element encoding" is the unique reversible encoding 259 of a group element. An "internal representation" is a point on the 260 curve used to implement ristretto255. Each group element can have 261 multiple equivalent internal representations. 263 Encoding, decoding, equality, and one-way map are defined in 264 Section 4.3. Element addition, subtraction, negation, and scalar 265 multiplication are implemented by applying the corresponding 266 operations directly to the internal representation. 268 The group order is the same as the order of the Curve25519 prime- 269 order subgroup: 271 l = 2^252 + 27742317777372353535851937790883648493 273 Since ristretto255 is a prime-order group, every element except the 274 identity is a generator, but for interoperability a canonical 275 generator is selected, which can be internally represented by the 276 Curve25519 basepoint, enabling reuse of existing precomputation for 277 scalar multiplication. This is its encoding: 279 e2f2ae0a 6abc4e71 a884a961 c500515f 58e30b6a a582dd8d b6a65945 e08d2d76 280 Implementations MUST NOT expose either the internal representation or 281 its field implementation and MUST NOT expose any operations defined 282 on the internal representations unless specified in this document. 284 4.1. Internal constants 286 This document references the following constant field element values. 287 Implementations MUST NOT expose them to their API consumers. 289 * D = 37095705934669439343138083508754565189542113879843219016388785 290 533085940283555 292 - This is the Edwards d parameter for Curve25519, as specified in 293 Section 4.1 of [RFC7748]. 295 * SQRT_M1 = 19681161376707505956807079304988542015446066515923890162 296 744021073123829784752 298 * SQRT_AD_MINUS_ONE = 2506306895338462347411141415870215270124453150 299 2492656460079210482610430750235 301 * INVSQRT_A_MINUS_D = 5446930700890931692099581386874514160539359729 302 2927456921205312896311721017578 304 * ONE_MINUS_D_SQ = 1159843021668779879193775521855586647937357759715 305 417654439879720876111806838 307 * D_MINUS_ONE_SQ = 4044083434630853685810104246932319082624839914623 308 8708352240133220865137265952 310 4.2. Square root of a ratio of field elements 312 The following function is defined on field elements, and is used to 313 implement other ristretto255 functions. Implementations MUST NOT 314 expose it to their API consumers. 316 On input field elements u and v, the function SQRT_RATIO_M1(u, v) 317 returns: 319 * (TRUE, +sqrt(u/v)) if u and v are non-zero, and u/v is square; 321 * (TRUE, zero) if u is zero; 323 * (FALSE, zero) if v is zero and u is non-zero; 325 * (FALSE, +sqrt(SQRT_M1*(u/v))) if u and v are non-zero, and u/v is 326 non-square (so SQRT_M1*(u/v) is square), 328 where +sqrt(x) indicates the non-negative square root of x. 330 The computation is similar to Section 5.1.3 of [RFC8032], with the 331 difference that if the input is non-square, the function returns a 332 result with a defined relationship to the inputs. This result is 333 used for efficient implementation of the one-way map functionality. 334 The function can be refactored from an existing Ed25519 335 implementation. 337 SQRT_RATIO_M1(u, v) is defined as follows: 339 v3 = v^2 * v 340 v7 = v3^2 * v 341 r = (u * v3) * (u * v7)^((p-5)/8) // Note: (p - 5) / 8 is an integer. 342 check = v * r^2 344 correct_sign_sqrt = CT_EQ(check, u) 345 flipped_sign_sqrt = CT_EQ(check, -u) 346 flipped_sign_sqrt_i = CT_EQ(check, -u*SQRT_M1) 348 r_prime = SQRT_M1 * r 349 r = CT_SELECT(r_prime IF flipped_sign_sqrt | flipped_sign_sqrt_i ELSE r) 351 // Choose the nonnegative square root. 352 r = CT_ABS(r) 354 was_square = correct_sign_sqrt | flipped_sign_sqrt 356 return (was_square, r) 358 4.3. External ristretto255 functions 360 4.3.1. Decode 362 All elements are encoded as a 32-byte string. Decoding proceeds as 363 follows: 365 1. First, interpret the string as an integer s in little-endian 366 representation. If the length of the string is not 32 bytes, or 367 if the resulting value is >= p, decoding fails. 369 * Note: unlike [RFC7748] field element decoding, the most 370 significant bit is not masked, and non-canonical values are 371 rejected. The test vectors in Appendix A.2 exercise these 372 edge cases. 374 2. If IS_NEGATIVE(s) returns TRUE, decoding fails. 376 3. Process s as follows: 378 ss = s^2 379 u1 = 1 - ss 380 u2 = 1 + ss 381 u2_sqr = u2^2 383 v = -(D * u1^2) - u2_sqr 385 (was_square, invsqrt) = SQRT_RATIO_M1(1, v * u2_sqr) 387 den_x = invsqrt * u2 388 den_y = invsqrt * den_x * v 390 x = CT_ABS(2 * s * den_x) 391 y = u1 * den_y 392 t = x * y 394 4. If was_square is FALSE, or IS_NEGATIVE(t) returns TRUE, or y = 0, 395 decoding fails. Otherwise, return the group element represented 396 by the internal representation (x, y, 1, t). 398 4.3.2. Encode 400 A group element with internal representation (x0, y0, z0, t0) is 401 encoded as follows: 403 1. Process the internal representation into a field element s as 404 follows: 406 u1 = (z0 + y0) * (z0 - y0) 407 u2 = x0 * y0 409 // Ignore was_square since this is always square. 410 (_, invsqrt) = SQRT_RATIO_M1(1, u1 * u2^2) 412 den1 = invsqrt * u1 413 den2 = invsqrt * u2 414 z_inv = den1 * den2 * t0 416 ix0 = x0 * SQRT_M1 417 iy0 = y0 * SQRT_M1 418 enchanted_denominator = den1 * INVSQRT_A_MINUS_D 420 rotate = IS_NEGATIVE(t0 * z_inv) 422 // Conditionally rotate x and y. 423 x = CT_SELECT(iy0 IF rotate ELSE x0) 424 y = CT_SELECT(ix0 IF rotate ELSE y0) 425 z = z0 426 den_inv = CT_SELECT(enchanted_denominator IF rotate ELSE den2) 428 y = CT_SELECT(-y IF IS_NEGATIVE(x * z_inv) ELSE y) 430 s = CT_ABS(den_inv * (z - y)) 432 2. Return the 32-byte little-endian encoding of s. 434 Note that decoding and then re-encoding a valid group element will 435 yield an identical byte string. 437 4.3.3. Equals 439 The equality function returns TRUE when two internal representations 440 correspond to the same group element. Note that internal 441 representations MUST NOT be compared in any other way than specified 442 here. 444 For two internal representations (x1, y1, z1, t1) and (x2, y2, z2, 445 t2), if 447 (x1 * y2 == y1 * x2) | (y1 * y2 == x1 * x2) 449 evaluates to TRUE, then return TRUE. Otherwise, return FALSE. 451 Note that the equality function always returns TRUE when applied to 452 an internal representation and to the internal representation 453 obtained by encoding and then re-decoding it. However, the internal 454 representations themselves might not be identical. 456 Implementations MAY also perform byte comparisons on encodings for an 457 equivalent, although less efficient, result. 459 4.3.4. One-way map 461 The one-way map operates on uniformly distributed 64-byte strings. 462 To obtain such an input from an arbitrary length byte string, 463 applications should use a domain-separated hash construction, the 464 choice of which is out-of-scope for this document. 466 The one-way map on an input string b proceeds as follows: 468 1. Compute P1 as MAP(b[0:32]). 470 2. Compute P2 as MAP(b[32:64]). 472 3. Return P1 + P2. 474 The MAP function is defined on a 32-byte string as: 476 1. First, mask the most significant bit in the final byte of the 477 string, and interpret the string as an integer r in little-endian 478 representation. Reduce r modulo p to obtain a field element t. 480 * Masking the most significant bit is equivalent to interpreting 481 the whole string as an integer in little-endian representation 482 and then reducing it modulo 2^255. 484 * Note: similarly to [RFC7748] field element decoding, and 485 unlike field element decoding in Section 4.3.1, the most 486 significant bit is masked, and non-canonical values are 487 accepted. 489 2. Process t as follows: 491 r = SQRT_M1 * t^2 492 u = (r + 1) * ONE_MINUS_D_SQ 493 v = (-1 - r*D) * (r + D) 495 (was_square, s) = SQRT_RATIO_M1(u, v) 496 s_prime = -CT_ABS(s*t) 497 s = CT_SELECT(s IF was_square ELSE s_prime) 498 c = CT_SELECT(-1 IF was_square ELSE r) 500 N = c * (r - 1) * D_MINUS_ONE_SQ - v 502 w0 = 2 * s * v 503 w1 = N * SQRT_AD_MINUS_ONE 504 w2 = 1 - s^2 505 w3 = 1 + s^2 507 3. Return the group element represented by the internal 508 representation (w0*w3, w2*w1, w1*w3, w0*w2). 510 4.4. Scalar field 512 The scalars for the ristretto255 group are integers modulo the order 513 l of the ristretto255 group. Note that this is the same scalar field 514 as Curve25519, allowing existing implementations to be reused. 516 Scalars are encoded as 32-byte strings in little-endian order. 517 Implementations SHOULD check that any scalar s falls in the range 0 518 <= s < l when parsing them and reject non-canonical scalar encodings. 519 Implementations SHOULD reduce scalars modulo l when encoding them as 520 byte strings. Omitting these strict range checks is NOT RECOMMENDED 521 but is allowed to enable reuse of scalar arithmetic implementations 522 in existing Curve25519 libraries. 524 Given a uniformly distributed 64-byte string b, implementations can 525 obtain a uniformly distributed scalar by interpreting the 64-byte 526 string as a 512-bit integer in little-endian order and reducing the 527 integer modulo l, as in [RFC8032]. 529 5. decaf448 531 decaf448 is an instantiation of the abstract prime-order group 532 interface defined in Section 3. This document describes how to 533 implement the decaf448 prime-order group using edwards448 points as 534 internal representations. 536 A "decaf448 group element" is the abstract element of the prime order 537 group. An "element encoding" is the unique reversible encoding of a 538 group element. An "internal representation" is a point on the curve 539 used to implement decaf448. Each group element can have multiple 540 equivalent internal representations. 542 Encoding, decoding, equality, and one-way map are defined in 543 Section 5.3. Element addition, subtraction, negation, and scalar 544 multiplication are implemented by applying the corresponding 545 operations directly to the internal representation. 547 The group order is the same as the order of the edwards448 prime- 548 order subgroup: 550 l = 2^446 - 551 13818066809895115352007386748515426880336692474882178609894547503885 553 Since decaf448 is a prime-order group, every element except the 554 identity is a generator, but for interoperability a canonical 555 generator is selected, which can be internally represented by the 556 edwards448 basepoint, enabling reuse of existing precomputation for 557 scalar multiplication. This is its encoding: 559 66666666 66666666 66666666 66666666 66666666 66666666 66666666 560 33333333 33333333 33333333 33333333 33333333 33333333 33333333 562 This repetitive constant is equal to 1/sqrt(5) in decaf448's field, 563 corresponding to the curve448 base point with x = 5. 565 Implementations MUST NOT expose either the internal representation or 566 its field implementation and MUST NOT expose any operations defined 567 on the internal representations unless specified in this document. 569 5.1. Internal constants 571 This document references the following constant field element values. 572 Implementations MUST NOT expose them to their API consumers. 574 * D = 72683872429560689054932380788800453435364136068731806028149019 575 918061232816673077268639638369867654593008888446184363736105349801 576 8326358 578 - This is the Edwards d parameter for edwards448, as specified in 579 Section 4.2 of [RFC7748], and is equal to -39081 in the field. 581 * ONE_MINUS_D = 39082 583 * ONE_MINUS_TWO_D = 78163 584 * SQRT_MINUS_D = 989442336477322197691770048769290191284175762955299 585 010740998895980437021160012578568021315638965153739277122320928458 586 83226922417596214 588 * INVSQRT_MINUS_D = 315019913931389607337177038330951043522456072897 589 266928557328499619017160722351061360252776265186336876723201881398 590 623946864393857820716 592 5.2. Square root of a ratio of field elements 594 The following function is defined on field elements, and is used to 595 implement other decaf448 functions. Implementations MUST NOT expose 596 it to their API consumers. 598 On input field elements u and v, the function SQRT_RATIO_M1(u, v) 599 returns: 601 * (TRUE, +sqrt(u/v)) if u and v are non-zero, and u/v is square; 603 * (TRUE, zero) if u is zero; 605 * (FALSE, zero) if v is zero and u is non-zero; 607 * (FALSE, +sqrt(-u/v)) if u and v are non-zero, and u/v is non- 608 square (so -(u/v) is square), 610 where +sqrt(x) indicates the non-negative square root of x. 612 The computation is similar to Section 5.2.3 of [RFC8032], with the 613 difference that if the input is non-square, the function returns a 614 result with a defined relationship to the inputs. This result is 615 used for efficient implementation of the one-way map functionality. 616 The function can be refactored from an existing edwards448 617 implementation. 619 SQRT_RATIO_M1(u, v) is defined as follows: 621 r = u * (u * v)^((p - 3) / 4) // Note: (p - 3) / 4 is an integer. 623 check = v * r^2 624 was_square = CT_EQ(check, u) 626 // Choose the nonnegative square root. 627 r = CT_ABS(r) 629 return (was_square, r) 631 5.3. External decaf448 functions 633 5.3.1. Decode 635 All elements are encoded as a 56-byte string. Decoding proceeds as 636 follows: 638 1. First, interpret the string as an integer s in little-endian 639 representation. If the length of the string is not 56 bytes, or 640 if the resulting value is >= p, decoding fails. 642 * Note: unlike [RFC7748] field element decoding, non-canonical 643 values are rejected. The test vectors in Appendix B.2 644 exercise these edge cases. 646 2. If IS_NEGATIVE(s) returns TRUE, decoding fails. 648 3. Process s as follows: 650 ss = s^2 651 u1 = 1 + ss 652 u2 = u1^2 - 4 * D * ss 653 (was_square, invsqrt) = SQRT_RATIO_M1(1, u2 * u1^2) 654 u3 = CT_ABS(2 * s * invsqrt * u1 * SQRT_MINUS_D) 655 x = u3 * invsqrt * u2 * INVSQRT_MINUS_D 656 y = (1 - ss) * invsqrt * u1 657 t = x * y 659 4. If was_square is FALSE then decoding fails. Otherwise, return 660 the group element represented by the internal representation (x, 661 y, 1, t). 663 5.3.2. Encode 665 A group element with internal representation (x0, y0, z0, t0) is 666 encoded as follows: 668 1. Process the internal representation into a field element s as 669 follows: 671 u1 = (x0 + t0) * (x0 - t0) 673 // Ignore was_square since this is always square. 674 (_, invsqrt) = SQRT_RATIO_M1(1, u1 * ONE_MINUS_D * x0^2) 676 ratio = CT_ABS(invsqrt * u1 * SQRT_MINUS_D) 677 u2 = INVSQRT_MINUS_D * ratio * z0 - t0 678 s = CT_ABS(ONE_MINUS_D * invsqrt * x0 * u2) 679 2. Return the 56-byte little-endian encoding of s. 681 Note that decoding and then re-encoding a valid group element will 682 yield an identical byte string. 684 5.3.3. Equals 686 The equality function returns TRUE when two internal representations 687 correspond to the same group element. Note that internal 688 representations MUST NOT be compared in any other way than specified 689 here. 691 For two internal representations (x1, y1, z1, t1) and (x2, y2, z2, 692 t2), if 694 x1 * y2 == y1 * x2 696 evaluates to TRUE, then return TRUE. Otherwise, return FALSE. 698 Note that the equality function always returns TRUE when applied to 699 an internal representation and to the internal representation 700 obtained by encoding and then re-decoding it. However, the internal 701 representations themselves might not be identical. 703 Implementations MAY also perform byte comparisons on encodings for an 704 equivalent, although less efficient, result. 706 5.3.4. One-way map 708 The one-way map operates on uniformly distributed 112-byte strings. 709 To obtain such an input from an arbitrary length byte string, 710 applications should use a domain-separated hash construction, the 711 choice of which is out-of-scope for this document. 713 The one-way map on an input string b proceeds as follows: 715 1. Compute P1 as MAP(b[0:56]). 717 2. Compute P2 as MAP(b[56:112]). 719 3. Return P1 + P2. 721 The MAP function is defined on a 56-byte string as: 723 1. Interpret the string as an integer r in little-endian 724 representation. Reduce r modulo p to obtain a field element t. 726 * Note: similarly to [RFC7748] field element decoding, and 727 unlike field element decoding in Section 5.3.1, non-canonical 728 values are accepted. 730 2. Process t as follows: 732 r = -t^2 733 u0 = d * (r-1) 734 u1 = (u0 + 1) * (u0 - r) 736 (was_square, v) = SQRT_RATIO_M1(ONE_MINUS_TWO_D, (r + 1) * u1) 737 v_prime = CT_SELECT(v IF was_square ELSE t * v) 738 sgn = CT_SELECT(1 IF was_square ELSE -1) 739 s = v_prime * (r + 1) 741 w0 = 2 * CT_ABS(s) 742 w1 = s^2 + 1 743 w2 = s^2 - 1 744 w3 = v_prime * s * (r - 1) * ONE_MINUS_TWO_D + sgn 746 3. Return the group element represented by the internal 747 representation (w0*w3, w2*w1, w1*w3, w0*w2). 749 5.4. Scalar field 751 The scalars for the decaf448 group are integers modulo the order l of 752 the decaf448 group. Note that this is the same scalar field as 753 edwards448, allowing existing implementations to be reused. 755 Scalars are encoded as 56-byte strings in little-endian order. 756 Implementations SHOULD check that any scalar s falls in the range 0 757 <= s < l when parsing them and reject non-canonical scalar encodings. 758 Implementations SHOULD reduce scalars modulo l when encoding them as 759 byte strings. Omitting these strict range checks is NOT RECOMMENDED 760 but is allowed to enable reuse of scalar arithmetic implementations 761 in existing edwards448 libraries. 763 Given a uniformly distributed 64-byte string b, implementations can 764 obtain a scalar by interpreting the 64-byte string as a 512-bit 765 integer in little-endian order and reducing the integer modulo l. 767 6. API Considerations 769 ristretto255 and decaf448 are abstractions which implement two prime- 770 order groups, and their elements are represented by curve points, but 771 they are not curve points. The API needs to reflect that: the type 772 representing an element of the group SHOULD be opaque and MUST NOT 773 expose the underlying curve point or field elements. 775 It is expected that a ristretto255 or decaf448 implementation can 776 change its underlying curve without causing any breaking change. The 777 ristretto255 and decaf448 constructions are carefully designed so 778 that this will be the case, as long as implementations do not expose 779 internal representations or operate on them except as described in 780 this document. In particular, implementations MUST NOT define any 781 external ristretto255 or decaf448 interface as operating on arbitrary 782 curve points, and they MUST NOT construct group elements except via 783 decoding, the one-way map, or group operations on other valid group 784 elements per Section 3. They are however allowed to apply any 785 optimization strategy to the internal representations as long as it 786 doesn't change the exposed behavior of the API. 788 It is RECOMMENDED that implementations do not perform a decoding and 789 encoding operation for each group operation, as it is inefficient and 790 unnecessary. Implementations SHOULD instead provide an opaque type 791 to hold the internal representation through multiple operations. 793 7. IANA Considerations 795 This document has no IANA actions. 797 8. Security Considerations 799 The ristretto255 and decaf448 groups provide higher-level protocols 800 with the abstraction they expect: a prime-order group. Therefore, 801 it's expected to be safer for use in any situation where Curve25519 802 or edwards448 is used to implement a protocol requiring a prime-order 803 group. Note that the safety of the abstraction can be defeated by 804 implementations that do not follow the guidance in Section 6. 806 There is no function to test whether an elliptic curve point is a 807 valid internal representation of a group element. The decoding 808 function always returns a valid internal representation, or an error, 809 and allowed operations on valid internal representations return valid 810 internal representations. In this way, an implementation can 811 maintain the invariant that an internal representation is always 812 valid, so that checking is never necessary, and invalid states are 813 unrepresentable. 815 9. Acknowledgements 817 The authors would like to thank Daira Hopwood, Riad S. Wahby, Chris 818 Wood, and Thomas Pornin for their comments on the draft. 820 10. Normative References 822 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 823 Requirement Levels", BCP 14, RFC 2119, 824 DOI 10.17487/RFC2119, March 1997, 825 . 827 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 828 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 829 May 2017, . 831 11. Informative References 833 [Naming] Bernstein, D. J., "[Cfrg] 25519 naming", 2014, 834 . 837 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 838 for Security", RFC 7748, DOI 10.17487/RFC7748, January 839 2016, . 841 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 842 Signature Algorithm (EdDSA)", RFC 8032, 843 DOI 10.17487/RFC8032, January 2017, 844 . 846 [MoneroVuln] 847 Nick, J., "Exploiting Low Order Generators in One-Time 848 Ring Signatures", 2017, 849 . 852 [RistrettoGroup] 853 de Valence, H., Lovecruft, I., Arcieri, T., and M. 854 Hamburg, "The Ristretto Group", 2018, 855 . 857 [Decaf] Hamburg, M., "Decaf: Eliminating cofactors through point 858 compression", 2015, 859 . 861 [Twisted] Hisil, H., Wong, K. K., Carter, G., and E. Dawson, 862 "Twisted Edwards Curves Revisited", 2008, 863 . 865 Appendix A. Test vectors for ristretto255 867 This section contains test vectors for ristretto255. The octets are 868 hex encoded, and whitespace is inserted for readability. 870 A.1. Multiples of the generator 872 The following are the encodings of the multiples 0 to 15 of the 873 canonical generator. That is, the first line is the encoding of the 874 identity element, and each successive line is obtained by adding the 875 generator to the previous line. 877 B[ 0]: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 878 B[ 1]: e2f2ae0a 6abc4e71 a884a961 c500515f 58e30b6a a582dd8d b6a65945 e08d2d76 879 B[ 2]: 6a493210 f7499cd1 7fecb510 ae0cea23 a110e8d5 b901f8ac add3095c 73a3b919 880 B[ 3]: 94741f5d 5d52755e ce4f23f0 44ee27d5 d1ea1e2b d196b462 166b1615 2a9d0259 881 B[ 4]: da808627 73358b46 6ffadfe0 b3293ab3 d9fd53c5 ea6c9553 58f56832 2daf6a57 882 B[ 5]: e882b131 016b52c1 d3337080 187cf768 423efccb b517bb49 5ab812c4 160ff44e 883 B[ 6]: f64746d3 c92b1305 0ed8d802 36a7f000 7c3b3f96 2f5ba793 d19a601e bb1df403 884 B[ 7]: 44f53520 926ec81f bd5a3878 45beb7df 85a96a24 ece18738 bdcfa6a7 822a176d 885 B[ 8]: 903293d8 f2287ebe 10e2374d c1a53e0b c887e592 699f02d0 77d5263c dd55601c 886 B[ 9]: 02622ace 8f7303a3 1cafc63f 8fc48fdc 16e1c8c8 d234b2f0 d6685282 a9076031 887 B[10]: 20706fd7 88b2720a 1ed2a5da d4952b01 f413bcf0 e7564de8 cdc81668 9e2db95f 888 B[11]: bce83f8b a5dd2fa5 72864c24 ba1810f9 522bc600 4afe9587 7ac73241 cafdab42 889 B[12]: e4549ee1 6b9aa030 99ca208c 67adafca fa4c3f3e 4e5303de 6026e3ca 8ff84460 890 B[13]: aa52e000 df2e16f5 5fb1032f c33bc427 42dad6bd 5a8fc0be 0167436c 5948501f 891 B[14]: 46376b80 f409b29d c2b5f6f0 c5259199 0896e571 6f41477c d30085ab 7f10301e 892 B[15]: e0c418f7 c8d9c4cd d7395b93 ea124f3a d99021bb 681dfc33 02a9d99a 2e53e64e 894 Note that because 896 B[i+1] = B[i] + B[1] 898 these test vectors allow testing the encoding function and the 899 implementation of addition simultaneously. 901 A.2. Invalid encodings 903 These are examples of encodings that MUST be rejected according to 904 Section 4.3.1. 906 # Non-canonical field encodings. 907 00ffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 908 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff7f 909 f3ffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff7f 910 edffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff7f 912 # Negative field elements. 913 01000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 914 01ffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff7f 915 ed57ffd8 c914fb20 1471d1c3 d245ce3c 746fcbe6 3a3679d5 1b6a516e bebe0e20 916 c34c4e18 26e5d403 b78e246e 88aa051c 36ccf0aa febffe13 7d148a2b f9104562 917 c940e5a4 404157cf b1628b10 8db051a8 d439e1a4 21394ec4 ebccb9ec 92a8ac78 918 47cfc549 7c53dc8e 61c91d17 fd626ffb 1c49e2bc a94eed05 2281b510 b1117a24 919 f1c6165d 33367351 b0da8f6e 4511010c 68174a03 b6581212 c71c0e1d 026c3c72 920 87260f7a 2f124951 18360f02 c26a470f 450dadf3 4a413d21 042b43b9 d93e1309 922 # Non-square x^2. 923 26948d35 ca62e643 e26a8317 7332e6b6 afeb9d08 e4268b65 0f1f5bbd 8d81d371 924 4eac077a 713c57b4 f4397629 a4145982 c661f480 44dd3f96 427d40b1 47d9742f 925 de6a7b00 deadc788 eb6b6c8d 20c0ae96 c2f20190 78fa604f ee5b87d6 e989ad7b 926 bcab477b e20861e0 1e4a0e29 5284146a 510150d9 817763ca f1a6f4b4 22d67042 927 2a292df7 e32cabab bd9de088 d1d1abec 9fc0440f 637ed2fb a145094d c14bea08 928 f4a9e534 fc0d216c 44b218fa 0c42d996 35a0127e e2e53c71 2f706096 49fdff22 929 8268436f 8c412619 6cf64b3c 7ddbda90 746a3786 25f9813d d9b84570 77256731 930 2810e5cb c2cc4d4e ece54f61 c6f69758 e289aa7a b440b3cb eaa21995 c2f4232b 932 # Negative xy value. 933 3eb858e7 8f5a7254 d8c97311 74a94f76 755fd394 1c0ac937 35c07ba1 4579630e 934 a45fdc55 c76448c0 49a1ab33 f17023ed fb2be358 1e9c7aad e8a61252 15e04220 935 d483fe81 3c6ba647 ebbfd3ec 41adca1c 6130c2be eee9d9bf 065c8d15 1c5f396e 936 8a2e1d30 050198c6 5a544831 23960ccc 38aef684 8e1ec8f5 f780e852 3769ba32 937 32888462 f8b486c6 8ad7dd96 10be5192 bbeaf3b4 43951ac1 a8118419 d9fa097b 938 22714250 1b9d4355 ccba2904 04bde415 75b03769 3cef1f43 8c47f8fb f35d1165 939 5c37cc49 1da847cf eb9281d4 07efc41e 15144c87 6e0170b4 99a96a22 ed31e01e 940 44542511 7cb8c90e dcbc7c1c c0e74f74 7f2c1efa 5630a967 c64f2877 92a48a4b 942 # s = -1, which causes y = 0. 943 ecffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff7f 945 A.3. Group elements from uniform byte strings 947 The following pairs are inputs to the one-way map of Section 4.3.4, 948 and their encoded outputs. 950 I: 5d1be09e3d0c82fc538112490e35701979d99e06ca3e2b5b54bffe8b4dc772c1 951 4d98b696a1bbfb5ca32c436cc61c16563790306c79eaca7705668b47dffe5bb6 952 O: 3066f82a 1a747d45 120d1740 f1435853 1a8f04bb ffe6a819 f86dfe50 f44a0a46 954 I: f116b34b8f17ceb56e8732a60d913dd10cce47a6d53bee9204be8b44f6678b27 955 0102a56902e2488c46120e9276cfe54638286b9e4b3cdb470b542d46c2068d38 956 O: f26e5b6f 7d362d2d 2a94c5d0 e7602cb4 773c95a2 e5c31a64 f133189f a76ed61b 958 I: 8422e1bbdaab52938b81fd602effb6f89110e1e57208ad12d9ad767e2e25510c 959 27140775f9337088b982d83d7fcf0b2fa1edffe51952cbe7365e95c86eaf325c 960 O: 006ccd2a 9e6867e6 a2c5cea8 3d3302cc 9de128dd 2a9a57dd 8ee7b9d7 ffe02826 962 I: ac22415129b61427bf464e17baee8db65940c233b98afce8d17c57beeb7876c2 963 150d15af1cb1fb824bbd14955f2b57d08d388aab431a391cfc33d5bafb5dbbaf 964 O: f8f0c87c f237953c 5890aec3 99816900 5dae3eca 1fbb0454 8c635953 c817f92a 966 I: 165d697a1ef3d5cf3c38565beefcf88c0f282b8e7dbd28544c483432f1cec767 967 5debea8ebb4e5fe7d6f6e5db15f15587ac4d4d4a1de7191e0c1ca6664abcc413 968 O: ae81e7de df20a497 e10c304a 765c1767 a42d6e06 029758d2 d7e8ef7c c4c41179 970 I: a836e6c9a9ca9f1e8d486273ad56a78c70cf18f0ce10abb1c7172ddd605d7fd2 971 979854f47ae1ccf204a33102095b4200e5befc0465accc263175485f0e17ea5c 972 O: e2705652 ff9f5e44 d3e841bf 1c251cf7 dddb77d1 40870d1a b2ed64f1 a9ce8628 974 I: 2cdc11eaeb95daf01189417cdddbf95952993aa9cb9c640eb5058d09702c7462 975 2c9965a697a3b345ec24ee56335b556e677b30e6f90ac77d781064f866a3c982 976 O: 80bd0726 2511cdde 4863f8a7 434cef69 6750681c b9510eea 557088f7 6d9e5065 978 The following one-way map inputs all produce the same encoded output. 980 I: edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff 981 1200000000000000000000000000000000000000000000000000000000000000 982 I: edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f 983 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff 984 I: 0000000000000000000000000000000000000000000000000000000000000080 985 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f 986 I: 0000000000000000000000000000000000000000000000000000000000000000 987 1200000000000000000000000000000000000000000000000000000000000080 989 O: 30428279 1023b731 28d277bd cb5c7746 ef2eac08 dde9f298 3379cb8e 5ef0517f 991 A.4. Square root of a ratio of field elements 993 The following are inputs and outputs of SQRT_RATIO_M1(u, v) defined 994 in Section 4.2. The values are little-endian encodings of field 995 elements. 997 u: 0000000000000000000000000000000000000000000000000000000000000000 998 v: 0000000000000000000000000000000000000000000000000000000000000000 999 was_square: TRUE 1000 r: 0000000000000000000000000000000000000000000000000000000000000000 1002 u: 0000000000000000000000000000000000000000000000000000000000000000 1003 v: 0100000000000000000000000000000000000000000000000000000000000000 1004 was_square: TRUE 1005 r: 0000000000000000000000000000000000000000000000000000000000000000 1007 u: 0100000000000000000000000000000000000000000000000000000000000000 1008 v: 0000000000000000000000000000000000000000000000000000000000000000 1009 was_square: FALSE 1010 r: 0000000000000000000000000000000000000000000000000000000000000000 1012 u: 0200000000000000000000000000000000000000000000000000000000000000 1013 v: 0100000000000000000000000000000000000000000000000000000000000000 1014 was_square: FALSE 1015 r: 3c5ff1b5d8e4113b871bd052f9e7bcd0582804c266ffb2d4f4203eb07fdb7c54 1017 u: 0400000000000000000000000000000000000000000000000000000000000000 1018 v: 0100000000000000000000000000000000000000000000000000000000000000 1019 was_square: TRUE 1020 r: 0200000000000000000000000000000000000000000000000000000000000000 1022 u: 0100000000000000000000000000000000000000000000000000000000000000 1023 v: 0400000000000000000000000000000000000000000000000000000000000000 1024 was_square: TRUE 1025 r: f6ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff3f 1027 Appendix B. Test vectors for decaf448 1029 This section contains test vectors for decaf448. The octets are hex 1030 encoded, and whitespace is inserted for readability. 1032 B.1. Multiples of the generator 1034 The following are the encodings of the multiples 0 to 15 of the 1035 canonical generator. That is, the first pair of lines is the 1036 encoding of the identity element, and each successive line is 1037 obtained by adding the generator to the previous line. 1039 B[ 0]: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 1040 00000000 00000000 00000000 00000000 00000000 00000000 00000000 1041 B[ 1]: 66666666 66666666 66666666 66666666 66666666 66666666 66666666 1042 33333333 33333333 33333333 33333333 33333333 33333333 33333333 1043 B[ 2]: c898eb4f 87f97c56 4c6fd61f c7e49689 314a1f81 8ec85eeb 3bd5514a 1044 c816d387 78f69ef3 47a89fca 817e66de fdedce17 8c7cc709 b2116e75 1045 B[ 3]: a0c09bf2 ba7208fd a0f4bfe3 d0f5b29a 54301230 6d43831b 5adc6fe7 1046 f8596fa3 08763db1 5468323b 11cf6e4a eb8c18fe 44678f44 545a69bc 1047 B[ 4]: b46f1836 aa287c0a 5a5653f0 ec5ef9e9 03f436e2 1c1570c2 9ad9e5f5 1048 96da97ee af17150a e30bcb31 74d04bc2 d712c8c7 789d7cb4 fda138f4 1049 B[ 5]: 1c5bbecf 4741dfaa e79db72d face00ea aac502c2 060934b6 eaaeca6a 1050 20bd3da9 e0be8777 f7d02033 d1b15884 232281a4 1fc7f80e ed04af5e 1051 B[ 6]: 86ff0182 d40f7f9e db786251 5821bd67 bfd6165a 3c44de95 d7df79b8 1052 779ccf64 60e3c68b 70c16aaa 280f2d7b 3f22d745 b97a8990 6cfc476c 1053 B[ 7]: 502bcb68 42eb06f0 e49032ba e87c554c 031d6d4d 2d7694ef bf9c468d 1054 48220c50 f8ca2884 3364d70c ee92d6fe 246e6144 8f9db980 8b3b2408 1055 B[ 8]: 0c9810f1 e2ebd389 caa78937 4d780079 74ef4d17 227316f4 0e578b33 1056 6827da3f 6b482a47 94eb6a39 75b971b5 e1388f52 e91ea2f1 bcb0f912 1057 B[ 9]: 20d41d85 a18d5657 a2964032 1563bbd0 4c2ffbd0 a37a7ba4 3a4f7d26 1058 3ce26faf 4e1f74f9 f4b590c6 9229ae57 1fe37fa6 39b5b8eb 48bd9a55 1059 B[10]: e6b4b8f4 08c7010d 0601e7ed a0c309a1 a42720d6 d06b5759 fdc4e1ef 1060 e22d076d 6c44d42f 508d67be 462914d2 8b8edce3 2e709430 5164af17 1061 B[11]: be88bbb8 6c59c13d 8e9d09ab 98105f69 c2d1dd13 4dbcd3b0 863658f5 1062 3159db64 c0e139d1 80f3c89b 8296d0ae 324419c0 6fa87fc7 daaf34c1 1063 B[12]: a456f936 9769e8f0 8902124a 0314c7a0 6537a06e 32411f4f 93415950 1064 a17badfa 7442b621 7434a3a0 5ef45be5 f10bd7b2 ef8ea00c 431edec5 1065 B[13]: 186e452c 4466aa43 83b4c002 10d52e79 22dbf977 1e8b47e2 29a9b7b7 1066 3c8d10fd 7ef0b6e4 1530f91f 24a3ed9a b71fa38b 98b2fe47 46d51d68 1067 B[14]: 4ae7fdca e9453f19 5a8ead5c be1a7b96 99673b52 c40ab279 27464887 1068 be53237f 7f3a21b9 38d40d0e c9e15b1d 5130b13f fed81373 a53e2b43 1069 B[15]: 841981c3 bfeec3f6 0cfeca75 d9d8dc17 f46cf010 6f2422b5 9aec580a 1070 58f34227 2e3a5e57 5a055ddb 051390c5 4c24c6ec b1e0aceb 075f6056 1072 B.2. Invalid encodings 1074 These are examples of encodings that MUST be rejected according to 1075 Section 5.3.1. 1077 # Non-canonical field encodings. 1078 8e24f838 059ee9fe f1e20912 6defe53d cd74ef9b 6304601c 6966099e 1079 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 1081 86fcc721 2bd4a0b9 80928666 dc28c444 a605ef38 e09fb569 e28d4443 1082 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 1084 866d54bd 4c4ff41a 55d4eefd beca73cb d653c7bd 3135b383 708ec0bd 1085 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 1086 4a380ccd ab9c8636 4a89e77a 464d64f9 157538cf dfa686ad c0d5ece4 1087 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 1089 f22d9d4c 945dd44d 11e0b1d3 d3d358d9 59b4844d 83b08c44 e659d79f 1090 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 1092 8cdffc68 1aa99e9c 818c8ef4 c3808b58 e86acdef 1ab68c84 77af185b 1093 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 1095 0e1c12ac 7b5920ef fbd044e8 97c57634 e2d05b5c 27f8fa3d f8a086a1 1096 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 1098 # Negative field elements. 1099 15141bd2 121837ef 71a0016b d11be757 507221c2 6542244f 23806f3f 1100 d3496b7d 4c368262 76f3bf5d eea2c60c 4fa4cec6 9946876d a497e795 1102 455d3802 38434ab7 40a56267 f4f46b7d 2eb2dd8e e905e51d 7b0ae8a6 1103 cb2bae50 1e67df34 ab21fa45 946068c9 f233939b 1d9521a9 98b7cb93 1105 810b1d8e 8bf3a9c0 23294bbf d3d905a9 7531709b dc0f4239 0feedd70 1106 10f77e98 686d400c 9c86ed25 0ceecd9d e0a18888 ffecda0f 4ea1c60d 1108 d3af9cc4 1be0e5de 83c0c627 3bedcb93 51970110 044a9a41 c7b9b226 1109 7cdb9d7b f4dc9c2f db8bed32 87818460 4f1d9944 305a8df4 274ce301 1111 9312bcab 09009e43 30ff89c4 bc1e9e00 0d863efc 3c863d3b 6c507a40 1112 fd2cdefd e1bf0892 b4b5ed97 80b91ed1 398fb4a7 344c605a a5efda74 1114 53d11bce 9e62a29d 63ed82ae 93761bdd 76e38c21 e2822d6e bee5eb1c 1115 5b8a03ea f9df749e 2490eda9 d8ac27d1 f71150de 93668074 d18d1c3a 1117 697c1aed 3cd88585 15d4be8a c158b229 fe184d79 cb2b06e4 9210a6f3 1118 a7cd537b cd9bd390 d96c4ab6 a4406da5 d9364072 6285370c fa95df80 1120 # Non-square x^2. 1121 58ad4871 5c9a1025 69b68b88 362a4b06 45781f5a 19eb7e59 c6a4686f 1122 d0f0750f f42e3d7a f1ab38c2 9d69b670 f3125891 9c9fdbf6 093d06c0 1124 8ca37ee2 b15693f0 6e910cf4 3c4e32f1 d5551dda 8b1e48cb 6ddd55e4 1125 40dbc7b2 96b60191 9a4e4069 f59239ca 247ff693 f7daa42f 086122b1 1127 982c0ec7 f43d9f97 c0a74b36 db0abd9c a6bfb981 23a90782 787242c8 1128 a523cdc7 6df14a91 0d544711 27e7662a 1059201f 902940cd 39d57af5 1130 baa9ab82 d07ca282 b968a911 a6c3728d 74bf2fe2 58901925 787f03ee 1131 4be7e3cb 6684fd1b cfe5071a 9a974ad2 49a4aaa8 ca812642 16c68574 1133 2ed9ffe2 ded67a37 2b181ac5 24996402 c4297062 9db03f5e 8636cbaf 1134 6074b523 d154a7a8 c4472c4c 353ab88c d6fec7da 7780834c c5bd5242 1136 f063769e 4241e76d 815800e4 933a3a14 4327a30e c40758ad 3723a788 1137 388399f7 b3f5d45b 6351eb8e ddefda7d 5bff4ee9 20d338a8 b89d8b63 1139 5a0104f1 f55d152c eb68bc13 81824998 91d90ee8 f09b4003 8ccc1e07 1140 cb621fd4 62f781d0 45732a4f 0bda73f0 b2acf943 55424ff0 388d4b9c 1142 B.3. Group elements from uniform byte strings 1144 The following pairs are inputs to the one-way map of Section 5.3.4, 1145 and their encoded outputs. 1147 I: cbb8c991fd2f0b7e1913462d6463e4fd2ce4ccdd28274dc2ca1f4165 1148 d5ee6cdccea57be3416e166fd06718a31af45a2f8e987e301be59ae6 1149 673e963001dbbda80df47014a21a26d6c7eb4ebe0312aa6fffb8d1b2 1150 6bc62ca40ed51f8057a635a02c2b8c83f48fa6a2d70f58a1185902c0 1151 O: 0c709c96 07dbb01c 94513358 745b7c23 953d03b3 3e39c723 4e268d1d 1152 6e24f340 14ccbc22 16b965dd 231d5327 e591dc3c 0e8844cc fd568848 1154 I: b6d8da654b13c3101d6634a231569e6b85961c3f4b460a08ac4a5857 1155 069576b64428676584baa45b97701be6d0b0ba18ac28d443403b4569 1156 9ea0fbd1164f5893d39ad8f29e48e399aec5902508ea95e33bc1e9e4 1157 620489d684eb5c26bc1ad1e09aba61fabc2cdfee0b6b6862ffc8e55a 1158 O: 76ab794e 28ff1224 c727fa10 16bf7f1d 329260b7 218a39ae a2fdb17d 1159 8bd91190 17b093d6 41cedf74 328c3271 84dc6f2a 64bd90ed dccfcdab 1161 I: 36a69976c3e5d74e4904776993cbac27d10f25f5626dd45c51d15dcf 1162 7b3e6a5446a6649ec912a56895d6baa9dc395ce9e34b868d9fb2c1fc 1163 72eb6495702ea4f446c9b7a188a4e0826b1506b0747a6709f37988ff 1164 1aeb5e3788d5076ccbb01a4bc6623c92ff147a1e21b29cc3fdd0e0f4 1165 O: c8d7ac38 4143500e 50890a1c 25d64334 3accce58 4caf2544 f9249b2b 1166 f4a69210 82be0e7f 3669bb5e c24535e6 c45621e1 f6dec676 edd8b664 1168 I: d5938acbba432ecd5617c555a6a777734494f176259bff9dab844c81 1169 aadcf8f7abd1a9001d89c7008c1957272c1786a4293bb0ee7cb37cf3 1170 988e2513b14e1b75249a5343643d3c5e5545a0c1a2a4d3c685927c38 1171 bc5e5879d68745464e2589e000b31301f1dfb7471a4f1300d6fd0f99 1172 O: 62beffc6 b8ee11cc d79dbaac 8f0252c7 50eb052b 192f41ee ecb12f29 1173 79713b56 3caf7d22 588eca5e 80995241 ef963e7a d7cb7962 f343a973 1175 I: 4dec58199a35f531a5f0a9f71a53376d7b4bdd6bbd2904234a8ea65b 1176 bacbce2a542291378157a8f4be7b6a092672a34d85e473b26ccfbd4c 1177 dc6739783dc3f4f6ee3537b7aed81df898c7ea0ae89a15b5559596c2 1178 a5eeacf8b2b362f3db2940e3798b63203cae77c4683ebaed71533e51 1179 O: f4ccb31d 263731ab 88bed634 304956d2 603174c6 6da38742 053fa37d 1180 d902346c 3862155d 68db63be 87439e3d 68758ad7 268e239d 39c4fd3b 1182 I: df2aa1536abb4acab26efa538ce07fd7bca921b13e17bc5ebcba7d1b 1183 6b733deda1d04c220f6b5ab35c61b6bcb15808251cab909a01465b8a 1184 e3fc770850c66246d5a9eae9e2877e0826e2b8dc1bc08009590bc677 1185 8a84e919fbd28e02a0f9c49b48dc689eb5d5d922dc01469968ee81b5 1186 O: 7e79b00e 8e0a76a6 7c0040f6 2713b8b8 c6d6f05e 9c6d0259 2e8a22ea 1187 896f5dea cc7c7df5 ed42beae 6fedb900 0285b482 aa504e27 9fd49c32 1189 I: e9fb440282e07145f1f7f5ecf3c273212cd3d26b836b41b02f108431 1190 488e5e84bd15f2418b3d92a3380dd66a374645c2a995976a015632d3 1191 6a6c2189f202fc766e1c82f50ad9189be190a1f0e8f9b9e69c9c18cc 1192 98fdd885608f68bf0fdedd7b894081a63f70016a8abf04953affbefa 1193 O: 20b171cb 16be977f 15e013b9 752cf86c 54c631c4 fc8cbf7c 03c4d3ac 1194 9b8e8640 e7b0e930 0b987fe0 ab504466 9314f6ed 1650ae03 7db853f1 1196 Authors' Addresses 1198 Henry de Valence 1199 Email: ietf@hdevalence.ca 1201 Jack Grigg 1202 Email: ietf@jackgrigg.com 1204 Mike Hamburg 1205 Email: ietf@shiftleft.org 1207 Isis Lovecruft 1208 Email: ietf@en.ciph.re 1210 George Tankersley 1211 Email: ietf@gtank.cc 1213 Filippo Valsorda 1214 Email: ietf@filippo.io