idnits 2.17.1 draft-hdevalence-cfrg-ristretto-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There are 23 instances of too long lines in the document, the longest one being 6 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 date (January 20, 2019) is 1913 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 551 -- Looks like a reference, but probably isn't: '11' on line 552 -- Looks like a reference, but probably isn't: '12' on line 553 -- Looks like a reference, but probably isn't: '13' on line 554 -- Looks like a reference, but probably isn't: '14' on line 555 -- Looks like a reference, but probably isn't: '15' on line 556 -- Looks like a reference, but probably isn't: '1' on line 560 Summary: 1 error (**), 0 flaws (~~), 1 warning (==), 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: July 24, 2019 6 G. Tankersley 8 F. Valsorda 10 I. Lovecruft 11 January 20, 2019 13 The ristretto255 Group 14 draft-hdevalence-cfrg-ristretto-00 16 Abstract 18 This memo specifies a prime-order group, ristretto255, suitable for 19 implementing complex cryptographic protocols such as zero-knowledge 20 proofs. The ristretto255 group can be implemented using Curve25519, 21 allowing existing Curve25519 implementations to be reused and 22 extended to provide a prime-order group. 24 Status of This Memo 26 This Internet-Draft is submitted in full conformance with the 27 provisions of BCP 78 and BCP 79. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF). Note that other groups may also distribute 31 working documents as Internet-Drafts. The list of current Internet- 32 Drafts is at https://datatracker.ietf.org/drafts/current/. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 This Internet-Draft will expire on July 24, 2019. 41 Copyright Notice 43 Copyright (c) 2019 IETF Trust and the persons identified as the 44 document authors. All rights reserved. 46 This document is subject to BCP 78 and the IETF Trust's Legal 47 Provisions Relating to IETF Documents 48 (https://trustee.ietf.org/license-info) in effect on the date of 49 publication of this document. Please review these documents 50 carefully, as they describe your rights and restrictions with respect 51 to this document. Code Components extracted from this document must 52 include Simplified BSD License text as described in Section 4.e of 53 the Trust Legal Provisions and are provided without warranty as 54 described in the Simplified BSD License. 56 Table of Contents 58 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 59 2. Notation and Conventions Used In This Document . . . . . . . 4 60 3. ristretto255 . . . . . . . . . . . . . . . . . . . . . . . . 4 61 3.1. Internal utility functions . . . . . . . . . . . . . . . 5 62 3.1.1. Negative field elements . . . . . . . . . . . . . . . 5 63 3.1.2. Constant time operations . . . . . . . . . . . . . . 6 64 3.1.3. Square root of a ratio of field elements . . . . . . 6 65 3.2. External ristretto255 functions . . . . . . . . . . . . . 7 66 3.2.1. DECODE . . . . . . . . . . . . . . . . . . . . . . . 7 67 3.2.2. ENCODE . . . . . . . . . . . . . . . . . . . . . . . 8 68 3.2.3. EQUALS . . . . . . . . . . . . . . . . . . . . . . . 9 69 3.2.4. FROM_UNIFORM_BYTES . . . . . . . . . . . . . . . . . 10 70 3.3. Operations on internal representations . . . . . . . . . 11 71 3.4. Scalar functions . . . . . . . . . . . . . . . . . . . . 11 72 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 73 5. Security Considerations . . . . . . . . . . . . . . . . . . . 11 74 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 12 75 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 12 76 7.1. Normative References . . . . . . . . . . . . . . . . . . 12 77 7.2. Informative References . . . . . . . . . . . . . . . . . 12 78 Appendix A. Test vectors . . . . . . . . . . . . . . . . . . . . 13 79 A.1. Multiples of the generator . . . . . . . . . . . . . . . 13 80 A.2. Invalid encodings . . . . . . . . . . . . . . . . . . . . 13 81 A.3. Group elements from uniform bytestrings . . . . . . . . . 14 82 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 15 84 1. Introduction 86 Ristretto is a technique for constructing prime order groups with 87 non-malleable encodings from non-prime-order elliptic curves. It 88 extends the [Decaf] approach to cofactor elimination to support 89 cofactor-8 curves such as Curve25519 [RFC7748]. In particular, this 90 allows an existing Curve25519 library to provide a prime-order group 91 with only a thin abstraction layer. 93 Edwards curves provide a number of implementation benefits for 94 cryptography, such as complete addition formulas with no exceptional 95 points and the fastest known formulas for curve operations. However, 96 every Edwards curve has a point of order 4, so that the group of 97 points on the curve is not of prime order but has a small cofactor. 99 This abstraction mismatch is usually handled by means of ad-hoc 100 protocol tweaks (such as multiplying by the cofactor in an 101 appropriate place), or not at all. 103 Even for simple protocols such as signatures, these tweaks can cause 104 subtle issues. For instance, Ed25519 implementations may have 105 different validation behaviour between batched and singleton 106 verification, and at least as specified in [RFC8032], the set of 107 valid signatures is not defined by the standard. 109 For more complex protocols, careful analysis is required for each 110 protocol, as the original security proofs may no longer apply, and 111 the tweaks for one protocol may have disastrous effects when applied 112 to another (for instance, the octuple-spend vulnerability in 113 [Monero]). 115 Decaf and Ristretto fix this abstraction mismatch in one place for 116 all protocols, providing an abstraction to protocol implementors that 117 matches the abstraction commonly assumed in protocol specifications, 118 while still allowing the use of high-performance curve 119 implementations internally. 121 While Ristretto is a general method, and can be used in conjunction 122 with any Edwards curve with cofactor 4 or 8, this document specifies 123 the ristretto255 group, which MAY be implemented using Curve25519. 125 It is also possible to implement ristretto255 using a different 126 elliptic curve internally, but that construction is out-of-scope for 127 this document. 129 The ristretto255 abstraction layer provides the following API to 130 higher-level protocols: 132 o "ENCODE", an encoding function from internal representations to 133 bytestrings so that all equivalent representations on the same 134 ristretto255 element are encoded as identical bytestrings; 136 o "DECODE", a decoding function from bytestrings to internal 137 representations with built-in validation, so that only the 138 canonical encodings of valid ristretto255 elements are accepted; 140 o "EQUALS", an equality check that operates on internal 141 representations, so that all representations of the same 142 ristretto255 element are considered equivalent; 144 o "FROM_UNIFORM_BYTES", a map from uniformly distributed bytestrings 145 to ristretto255 elements suitable for hash-to-group and random- 146 point operations. 148 The internal representatives are elliptic curve points, and 149 internally, group element addition and subtraction (and therefore 150 scalar multiplication) is implemented by applying point addition, 151 subtraction and scalar multiplication to the internal representation. 153 In other words, an existing Edwards curve implementation can 154 implement ristretto255 by adding four functions: "ENCODE", "DECODE", 155 "EQUALS", and "FROM_UNIFORM_BYTES". 157 The abstraction layer imposes minor overhead, and certain operations 158 (like "EQUALS") are faster than corresponding operations on the 159 elliptic curve points used internally. 161 The Ristretto construction and its ristretto255 instantiation are 162 described and justified in detail at https://ristretto.group. 164 2. Notation and Conventions Used In This Document 166 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 167 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 168 "OPTIONAL" in this document are to be interpreted as described in BCP 169 14 [RFC2119] [RFC8174] when, and only when, they appear in all 170 capitals, as shown here. 172 A "ristretto255 group element" is the abstract element of the prime 173 order group. An "element encoding" is the unique reversible encoding 174 of a group element. An "internal representation" is a point on the 175 curve used to implement ristretto255, alternatively called a 176 "representative". Each group element can have multiple equivalent 177 internal representations. 179 Elliptic curve points are represented in extended coordinates in the 180 (x, y, z, t) format [Twisted]. All formulas specify field operations 181 unless otherwise noted. 183 3. ristretto255 185 This documents describes how to implement the ristretto255 group 186 using Curve25519 points as an internal representation. Note that 187 implementations MAY choose to use a different internal 188 representation, possibly based on a different curve, as long as they 189 provide a group of order 191 l = 2**252 + 27742317777372353535851937790883648493 192 whose encoding and decoding functions match the ones in this 193 document. 195 In particular, implementations MUST NOT expose the internal 196 representation and MUST NOT apply any operations defined on the 197 internal representations unless specified in this document. 199 Since ristretto255 is a prime order group, every element is a 200 generator, but for interoperability a canonical generator is 201 selected, which can be internally represented by the Curve25519 202 basepoint, enabling reuse of existing precomputation for scalar 203 multiplication. This is its encoding: 205 e2f2ae0a 6abc4e71 a884a961 c500515f 58e30b6a a582dd8d b6a65945 e08d2d76 207 3.1. Internal utility functions 209 The following functions are defined on field elements, and are used 210 to implement the other ristretto255 functions. These are defined in 211 this document for convenience in extending a Curve25519 212 implementation to provide the ristretto255 API. Implementations 213 SHOULD NOT expose these to their API consumers. 215 The order of the field is p, the Curve25519 prime 2^255-19, as 216 specified in Section 4.1 of [RFC7748]. Other parameters used in this 217 document are: 219 o SQRT_M1 = 19681161376707505956807079304988542015446066515923890162 220 744021073123829784752 222 o SQRT_AD_MINUS_ONE = 2506306895338462347411141415870215270124453150 223 2492656460079210482610430750235 225 o INVSQRT_A_MINUS_D = 5446930700890931692099581386874514160539359729 226 2927456921205312896311721017578 228 o ONE_MINUS_D_SQ = 1159843021668779879193775521855586647937357759715 229 417654439879720876111806838 231 o D_MINUS_ONE_SQ = 4044083434630853685810104246932319082624839914623 232 8708352240133220865137265952 234 3.1.1. Negative field elements 236 As in [RFC8032], given a field element e, define IS_NEGATIVE(e) as 237 TRUE if the least significant bit of the encoding of e is 1, and 238 FALSE otherwise. 240 3.1.2. Constant time operations 242 We assume that the field element implementation supports the 243 following operations, which SHOULD be implemented in constant time: 245 o CT_EQ(u, v): Return TRUE if u = v, FALSE otherwise. 247 o CT_SELECT(v IF cond ELSE u): Return v if cond is TRUE, else return 248 u. 250 o CT_NEG(u, cond): Return -u if cond is TRUE, else return u. 252 o CT_ABS(u): Return -u if u is negative, else return u. 254 Note that if they are not already provided, CT_NEG can be implemented 255 as CT_SELECT(-u IF cond ELSE u) and CT_ABS can be implemented as 256 CT_SELECT(-u IF IS_NEGATIVE(u) ELSE u). 258 3.1.3. Square root of a ratio of field elements 260 On input field elements u and v, the function SQRT_RATIO_M1(u, v) 261 returns: 263 o (TRUE, +sqrt(u/v)) if v is non-zero and u/v is square; 265 o (TRUE, zero) if u is zero; 267 o (FALSE, zero) if v is zero and u is non-zero; 269 o (FALSE, +sqrt(SQRT_M1*(u/v))) if u/v is non-square (so SQRT_M1*(u/ 270 v) is square). 272 The computation is similar to Section 5.1.3 of [RFC8032], with the 273 difference that if the input is non-square, the function returns a 274 result with a defined relationship to the inputs. This result is 275 used for efficient implementation of the from-uniform-bytes 276 functionality. The function can be refactored from an existing 277 Ed25519 implementation. 279 SQRT_RATIO_M1(u, v) is defined as follows: 281 v3 = v^2 * v 282 v7 = v3^2 * v 283 r = (u * v3) * (u * v7)^((p-5)/8) 284 check = v * r^2 286 correct_sign_sqrt = CT_EQ(check, u) 287 flipped_sign_sqrt = CT_EQ(check, -u) 288 flipped_sign_sqrt_i = CT_EQ(check, -u*SQRT_M1) 290 r_prime = SQRT_M1 * r 291 r = CT_SELECT(r_prime IF flipped_sign_sqrt | flipped_sign_sqrt_i ELSE r) 293 // Choose the nonnegative square root. 294 r = CT_ABS(r) 296 was_square = correct_sign_sqrt | flipped_sign_sqrt 298 return (was_square, r) 300 3.2. External ristretto255 functions 302 A ristretto255 implementation MUST implement the following functions: 304 3.2.1. DECODE 306 All elements are encoded as a 32-byte string. Decoding proceeds as 307 follows: 309 1. First, interpret the string as an integer s in little-endian 310 representation. If the resulting value is >= p, decoding fails. 312 2. If IS_NEGATIVE(s) returns TRUE, decoding fails. 314 3. Process s as follows: 316 ss = s^2 317 u1 = 1 - ss 318 u2 = 1 + ss 319 u2_sqr = u2^2 321 v = -(D * u1^2) - u2_sqr 323 (was_square, invsqrt) = SQRT_RATIO_M1(1, v * u2_sqr) 325 den_x = invsqrt * u2 326 den_y = invsqrt * den_x * v 328 x = CT_ABS(2 * s * den_x) 329 y = u1 * den_y 330 t = x * y 332 4. If was_square is FALSE, or IS_NEGATIVE(t) returns TRUE, or y = 0, 333 decoding fails. Otherwise, return the internal representation in 334 extended coordinates (x, y, 1, t). 336 3.2.2. ENCODE 338 An internal representation (x0, y0, z0, t0) is encoded as follows: 340 1. Process the internal representation into a field element s as 341 follows: 343 u1 = (z0 + y0) * (z0 - y0) 344 u2 = x0 * y0 346 // Ignore was_square since this is always square 347 (_, invsqrt) = SQRT_RATIO_M1(1, u1 * u2^2) 349 den1 = invsqrt * u1 350 den2 = invsqrt * u2 351 z_inv = den1 * den2 * t0 353 ix0 = x0 * SQRT_M1 354 iy0 = y0 * SQRT_M1 355 enchanted_denominator = den1 * INVSQRT_A_MINUS_D 357 rotate = IS_NEGATIVE(t0 * z_inv) 359 x = CT_SELECT(iy0 IF rotate ELSE x0) 360 y = CT_SELECT(ix0 IF rotate ELSE y0) 361 z = z0 362 den_inv = CT_SELECT(enchanted_denominator IF rotate ELSE den2) 364 y = CT_NEG(y, IS_NEGATIVE(x * z_inv)) 366 s = CT_ABS(den_inv * (z - y)) 368 2. Return the canonical little-endian encoding of s. 370 Note that decoding and then re-encoding a valid group element will 371 yield an identical bytestring. 373 3.2.3. EQUALS 375 The equality function returns TRUE when two representatives 376 correspond to the same group element. Note that internal 377 representations MUST NOT be compared in any other way than specified 378 here. 380 For two representatives (x1, y1, z1, t1) and (x2, y2, z2, t2), if 382 (x1 * y2 == y1 * x2 || y1 * y2 == -a * x1 * x2) 384 evaluates to TRUE, then return TRUE. Otherwise, return FALSE. Note 385 that a = -1 when using Curve25519 internally, simplifying the check 386 to 388 (x1 * y2 == y1 * x2 || y1 * y2 == x1 * x2) 389 Note that the equality function always returns TRUE when applied to 390 an internal representation and to the internal representation 391 obtained by encoding and then re-decoding it. However, the internal 392 representations themselves might not be identical. 394 Unlike the equality check for an elliptic curve point in projective 395 coordinates, the equality check for a ristretto255 group element does 396 not require an inversion. 398 3.2.4. FROM_UNIFORM_BYTES 400 Define the function MAP(t) on field element t as: 402 r = SQRT_M1 * t^2 403 u = (r + 1) * ONE_MINUS_D_SQ 404 c = -1 405 v = (c - r*D) * (r + D) 407 (was_square, s) = SQRT_RATIO_M1(u, v) 408 s_prime = -CT_ABS(s*t) 409 s = CT_SELECT(s IF was_square ELSE s_prime) 410 c = CT_SELECT(c IF was_square ELSE r) 412 N = c * (r - 1) * D_MINUS_ONE_SQ - v 414 w0 = 2 * s * v 415 w1 = N * SQRT_AD_MINUS_ONE 416 w2 = 1 - s^2 417 w3 = 1 + s^2 419 return (w0*w3, w2*w1, w1*w3, w0*w2) 421 Then, given a uniformly distributed 64-byte string b: 423 1. Set r0 to the low 255 bits of b[ 0..32], taken mod p 425 2. Set r1 to the low 255 bits of b[32..64], taken mod p 427 3. Compute group element P1 as MAP(r0) 429 4. Compute group element P2 as MAP(r1). 431 5. Return the group element P1 + P2. 433 3.3. Operations on internal representations 435 Group addition, subtraction and (multi-)scalar multiplication are 436 performed without modification using the internal representations. 438 Implementations MUST NOT perform any other operation on internal 439 representations and MUST NOT construct group elements except via 440 "DECODE" and "FROM_UNIFORM_BYTES". 442 3.4. Scalar functions 444 The scalars for the ristretto255 group are integers mod 446 l = 2**252 + 27742317777372353535851937790883648493. 448 Scalars are encoded as 32-byte strings in little-endian order. 449 Implementations SHOULD check that scalars are reduced modulo l when 450 parsing them and reject non-canonical scalar encodings. 451 Implementations SHOULD reduce scalars modulo l when encoding them as 452 byte strings. 454 Given a uniformly distributed 64-byte string b, implementations can 455 obtain a scalar by interpreting the 64-byte string as a 512-bit 456 integer in little-endian order and reducing the integer modulo l, as 457 in [RFC8032]. 459 4. IANA Considerations 461 This document has no IANA actions. 463 5. Security Considerations 465 ristretto255 elements are represented by curve points, but they are 466 not curve points. Not every curve point is a representative of a 467 ristretto255 element. The ristretto255 group is not a subgroup of 468 the curve, and the ristretto255 group is logically distinct from the 469 group of curve points. 471 For these reasons, ristretto255 elements SHOULD have a different type 472 than curve points, and it SHOULD be a type error to mix them. In 473 particular, implementations MUST NOT define the ristretto255 474 functions as operating on arbitrary curve points, rather than only on 475 the representatives obtained by decoding a ristretto255 encoding or 476 by mapping arbitrary bytestrings. 478 There is no function to test whether an elliptic curve point is a 479 valid internal representative of a group element. The decoding 480 function always returns a valid representative, or an error, and 481 allowed operations on valid internal representations return valid 482 internal representations. In this way, an implementation can 483 maintain the invariant that an internal representative is always 484 valid, so that checking is never necessary, and invalid states are 485 unrepresentable. 487 6. Acknowledgements 489 Ristretto was originally designed by Mike Hamburg as a variant of 490 [Decaf]. 492 7. References 494 7.1. Normative References 496 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 497 Requirement Levels", BCP 14, RFC 2119, 498 DOI 10.17487/RFC2119, March 1997, 499 . 501 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 502 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 503 May 2017, . 505 7.2. Informative References 507 [Decaf] Hamburg, M., "Decaf: Eliminating cofactors through point 508 compression", 2015, 509 . 511 [Monero] Nick, J., "Exploiting Low Order Generators in One-Time 512 Ring Signatures", 2017, 513 . 516 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 517 for Security", RFC 7748, DOI 10.17487/RFC7748, January 518 2016, . 520 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 521 Signature Algorithm (EdDSA)", RFC 8032, 522 DOI 10.17487/RFC8032, January 2017, 523 . 525 [Twisted] Hisil, H., Wong, K., Carter, G., and E. Dawson, "Twisted 526 Edwards Curves Revisited", 2008, 527 . 529 Appendix A. Test vectors 531 This section contains test vectors for ristretto255. The octets are 532 hex encoded, and whitespace is inserted for readability. 534 A.1. Multiples of the generator 536 The following are the encodings of the multiplies 0 to 15 of the 537 canonical generator. That is, the first line is the encoding of the 538 identity point, and each successive line is obtained by adding the 539 generator to the previous line. 541 B[ 0]: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 542 B[ 1]: e2f2ae0a 6abc4e71 a884a961 c500515f 58e30b6a a582dd8d b6a65945 e08d2d76 543 B[ 2]: 6a493210 f7499cd1 7fecb510 ae0cea23 a110e8d5 b901f8ac add3095c 73a3b919 544 B[ 3]: 94741f5d 5d52755e ce4f23f0 44ee27d5 d1ea1e2b d196b462 166b1615 2a9d0259 545 B[ 4]: da808627 73358b46 6ffadfe0 b3293ab3 d9fd53c5 ea6c9553 58f56832 2daf6a57 546 B[ 5]: e882b131 016b52c1 d3337080 187cf768 423efccb b517bb49 5ab812c4 160ff44e 547 B[ 6]: f64746d3 c92b1305 0ed8d802 36a7f000 7c3b3f96 2f5ba793 d19a601e bb1df403 548 B[ 7]: 44f53520 926ec81f bd5a3878 45beb7df 85a96a24 ece18738 bdcfa6a7 822a176d 549 B[ 8]: 903293d8 f2287ebe 10e2374d c1a53e0b c887e592 699f02d0 77d5263c dd55601c 550 B[ 9]: 02622ace 8f7303a3 1cafc63f 8fc48fdc 16e1c8c8 d234b2f0 d6685282 a9076031 551 B[10]: 20706fd7 88b2720a 1ed2a5da d4952b01 f413bcf0 e7564de8 cdc81668 9e2db95f 552 B[11]: bce83f8b a5dd2fa5 72864c24 ba1810f9 522bc600 4afe9587 7ac73241 cafdab42 553 B[12]: e4549ee1 6b9aa030 99ca208c 67adafca fa4c3f3e 4e5303de 6026e3ca 8ff84460 554 B[13]: aa52e000 df2e16f5 5fb1032f c33bc427 42dad6bd 5a8fc0be 0167436c 5948501f 555 B[14]: 46376b80 f409b29d c2b5f6f0 c5259199 0896e571 6f41477c d30085ab 7f10301e 556 B[15]: e0c418f7 c8d9c4cd d7395b93 ea124f3a d99021bb 681dfc33 02a9d99a 2e53e64e 558 Note that because 560 B[i+1] = B[i] + B[1] 562 these test vectors allow testing the encoding function and the 563 implementation of addition simultaneously. 565 A.2. Invalid encodings 567 These are examples of encodings that MUST be rejected according to 568 Section 3.2.1. 570 # Non-canonical field encodings. 571 00ffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 572 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff7f 573 f3ffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff7f 574 edffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff7f 576 # Negative field elements. 577 01000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 578 01ffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff7f 579 ed57ffd8 c914fb20 1471d1c3 d245ce3c 746fcbe6 3a3679d5 1b6a516e bebe0e20 580 c34c4e18 26e5d403 b78e246e 88aa051c 36ccf0aa febffe13 7d148a2b f9104562 581 c940e5a4 404157cf b1628b10 8db051a8 d439e1a4 21394ec4 ebccb9ec 92a8ac78 582 47cfc549 7c53dc8e 61c91d17 fd626ffb 1c49e2bc a94eed05 2281b510 b1117a24 583 f1c6165d 33367351 b0da8f6e 4511010c 68174a03 b6581212 c71c0e1d 026c3c72 584 87260f7a 2f124951 18360f02 c26a470f 450dadf3 4a413d21 042b43b9 d93e1309 586 # Non-square x^2. 587 26948d35 ca62e643 e26a8317 7332e6b6 afeb9d08 e4268b65 0f1f5bbd 8d81d371 588 4eac077a 713c57b4 f4397629 a4145982 c661f480 44dd3f96 427d40b1 47d9742f 589 de6a7b00 deadc788 eb6b6c8d 20c0ae96 c2f20190 78fa604f ee5b87d6 e989ad7b 590 bcab477b e20861e0 1e4a0e29 5284146a 510150d9 817763ca f1a6f4b4 22d67042 591 2a292df7 e32cabab bd9de088 d1d1abec 9fc0440f 637ed2fb a145094d c14bea08 592 f4a9e534 fc0d216c 44b218fa 0c42d996 35a0127e e2e53c71 2f706096 49fdff22 593 8268436f 8c412619 6cf64b3c 7ddbda90 746a3786 25f9813d d9b84570 77256731 594 2810e5cb c2cc4d4e ece54f61 c6f69758 e289aa7a b440b3cb eaa21995 c2f4232b 596 # Negative xy value. 597 3eb858e7 8f5a7254 d8c97311 74a94f76 755fd394 1c0ac937 35c07ba1 4579630e 598 a45fdc55 c76448c0 49a1ab33 f17023ed fb2be358 1e9c7aad e8a61252 15e04220 599 d483fe81 3c6ba647 ebbfd3ec 41adca1c 6130c2be eee9d9bf 065c8d15 1c5f396e 600 8a2e1d30 050198c6 5a544831 23960ccc 38aef684 8e1ec8f5 f780e852 3769ba32 601 32888462 f8b486c6 8ad7dd96 10be5192 bbeaf3b4 43951ac1 a8118419 d9fa097b 602 22714250 1b9d4355 ccba2904 04bde415 75b03769 3cef1f43 8c47f8fb f35d1165 603 5c37cc49 1da847cf eb9281d4 07efc41e 15144c87 6e0170b4 99a96a22 ed31e01e 604 44542511 7cb8c90e dcbc7c1c c0e74f74 7f2c1efa 5630a967 c64f2877 92a48a4b 606 # s = -1, which causes y = 0. 607 ecffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff7f 609 A.3. Group elements from uniform bytestrings 611 The following pairs are inputs to "FROM_UNIFORM_BYTES", and their 612 encoded outputs. 614 I: 5d1be09e3d0c82fc538112490e35701979d99e06ca3e2b5b54bffe8b4dc772c1 615 4d98b696a1bbfb5ca32c436cc61c16563790306c79eaca7705668b47dffe5bb6 616 O: 3066f82a 1a747d45 120d1740 f1435853 1a8f04bb ffe6a819 f86dfe50 f44a0a46 618 I: f116b34b8f17ceb56e8732a60d913dd10cce47a6d53bee9204be8b44f6678b27 619 0102a56902e2488c46120e9276cfe54638286b9e4b3cdb470b542d46c2068d38 620 O: f26e5b6f 7d362d2d 2a94c5d0 e7602cb4 773c95a2 e5c31a64 f133189f a76ed61b 622 I: 8422e1bbdaab52938b81fd602effb6f89110e1e57208ad12d9ad767e2e25510c 623 27140775f9337088b982d83d7fcf0b2fa1edffe51952cbe7365e95c86eaf325c 624 O: 006ccd2a 9e6867e6 a2c5cea8 3d3302cc 9de128dd 2a9a57dd 8ee7b9d7 ffe02826 626 I: ac22415129b61427bf464e17baee8db65940c233b98afce8d17c57beeb7876c2 627 150d15af1cb1fb824bbd14955f2b57d08d388aab431a391cfc33d5bafb5dbbaf 628 O: f8f0c87c f237953c 5890aec3 99816900 5dae3eca 1fbb0454 8c635953 c817f92a 630 I: 165d697a1ef3d5cf3c38565beefcf88c0f282b8e7dbd28544c483432f1cec767 631 5debea8ebb4e5fe7d6f6e5db15f15587ac4d4d4a1de7191e0c1ca6664abcc413 632 O: ae81e7de df20a497 e10c304a 765c1767 a42d6e06 029758d2 d7e8ef7c c4c41179 634 I: a836e6c9a9ca9f1e8d486273ad56a78c70cf18f0ce10abb1c7172ddd605d7fd2 635 979854f47ae1ccf204a33102095b4200e5befc0465accc263175485f0e17ea5c 636 O: e2705652 ff9f5e44 d3e841bf 1c251cf7 dddb77d1 40870d1a b2ed64f1 a9ce8628 638 I: 2cdc11eaeb95daf01189417cdddbf95952993aa9cb9c640eb5058d09702c7462 639 2c9965a697a3b345ec24ee56335b556e677b30e6f90ac77d781064f866a3c982 640 O: 80bd0726 2511cdde 4863f8a7 434cef69 6750681c b9510eea 557088f7 6d9e5065 642 Authors' Addresses 644 Henry de Valence 646 Email: ietf@hdevalence.ca 648 Jack Grigg 650 Email: ietf@jackgrigg.com 652 George Tankersley 654 Email: ietf@gtank.cc 656 Filippo Valsorda 658 Email: ietf@filippo.io 659 Isis Lovecruft 661 Email: ietf@en.ciph.re