Appendices

Appendix A. Related Work

The problem of mapping arbitrary bit strings to elliptic curve points has been the subject of both practical and theoretical research. This section briefly describes the background and research results that underlie the recommendations in this document. This section is provided for informational purposes only.

A naive but generally insecure method of mapping a string msg to a point on an elliptic curve E having n points is to first fix a point P that generates the elliptic curve group, and a hash function Hn from bit strings to integers less than n; then compute Hn(msg) * P, where the * operator represents scalar multiplication. The reason this approach is insecure is that the resulting point has a known discrete log relationship to P. Thus, except in cases where this method is specified by the protocol, it must not be used; doing so risks catastrophic security failures.

Boneh et al. [BLS01] describe an encoding method they call MapToGroup, which works roughly as follows: first, use the input string to initialize a pseudorandom number generator, then use the generator to produce a value x in F. If x is the x-coordinate of a point on the elliptic curve, output that point. Otherwise, generate a new value x in F and try again. Since a random value x in F has probability about 1/2 of corresponding to a point on the curve, the expected number of tries is just two. However, the running time of this method, which is generally referred to as a probabilistic try- and-increment algorithm, depends on the input string. As such, it is not safe to use in protocols sensitive to timing side channels, as was exemplified by the Dragonblood attack [VR20].

Schinzel and Skalba [SS04] introduce a method of constructing elliptic curve points deterministically, for a restricted class of curves and a very small number of points. Skalba [S05] generalizes this construction to more curves and more points on those curves. Shallue and van de Woestijne [SW06] further generalize and simplify Skalba's construction, yielding concretely efficient maps to a constant fraction of the points on almost any curve. Fouque and Tibouchi [FT12] give a parameterization of this mapping for Barreto- Naehrig pairing-friendly curves [BN05].

Ulas [U07] describes a simpler version of the Shallue-van de Woestijne map, and Brier et al. [BCIMRT10] give a further simplification, which the authors call the "Simplified SWU" map. That simplified map applies only to fields of characteristic p = 3 (mod 4); Wahby and Boneh [WB19] generalize to fields of any characteristic and give further optimizations.

Boneh and Franklin give a deterministic algorithm mapping to certain supersingular curves over fields of characteristic p = 2 (mod 3) [BF01]. Icart gives another deterministic algorithm that maps to any curve over a field of characteristic p = 2 (mod 3) [Icart09]. Several extensions and generalizations follow this work, including [FSV09], [FT10], [KLR10], [F11], and [CK11].

Following the work of Farashahi [F11], Fouque et al. [FJT13] describe a mapping to curves over fields of characteristic p = 3 (mod 4) having a number of points divisible by 4. Bernstein et al. [BHKL13] optimize this mapping and describe a related mapping that they call "Elligator 2," which applies to any curve over a field of odd characteristic having a point of order 2. This includes Curve25519 and Curve448, both of which are CFRG-recommended curves [RFC7748]. Bernstein et al. [BLMP19] extend the Elligator 2 map to a class of supersingular curves over fields of characteristic p = 3 (mod 4).

An important caveat regarding all of the above deterministic mapping functions is that none of them map to the entire curve, but rather to some fraction of the points. This means that they cannot be used directly to construct a random oracle that outputs points on the curve.

Brier et al. [BCIMRT10] give two solutions to this problem. The first, which Brier et al. prove applies to Icart's method, computes f(H0(msg)) + f(H1(msg)) for two distinct hash functions H0 and H1 from bit strings to F and a mapping f from F to the elliptic curve E. The second, which applies to essentially all deterministic mappings but is more costly, computes f(H0(msg)) + H2(msg) * P, where P is a generator of the elliptic curve group, H2 is a hash from bit strings to integers modulo r, and r is the order of the elliptic curve group.

Farashahi et al. [FFSTV13] improve the analysis of the first method, showing that it applies to essentially all deterministic mappings. Tibouchi and Kim [TK17] further refine the analysis and describe additional optimizations.

Complementary to the problem of mapping from bit strings to elliptic curve points, Bernstein et al. [BHKL13] study the problem of mapping from elliptic curve points to uniformly random bit strings, giving solutions for a class of curves that includes Montgomery and twisted Edwards curves. Tibouchi [T14] and Aranha et al. [AFQTZ14] generalize these results. This document does not deal with this complementary problem.

Appendix B. Hashing to ristretto255

ristretto255 [ristretto255-decaf448] provides a prime-order group based on curve25519 [RFC7748]. This section describes hash_to_ristretto255, which implements a random-oracle encoding to this group that has a uniform output distribution (Section 2.2.3) and the same security properties and interface as the hash_to_curve function (Section 3).

The ristretto255 API defines a one-way map ([ristretto255-decaf448], Section 4.3.4); this section refers to that map as ristretto255_map.

The hash_to_ristretto255 function MUST be instantiated with an expand_message function that conforms to the requirements given in Section 5.3. In addition, it MUST use a domain separation tag constructed as described in Section 3.1, and all domain separation recommendations given in Section 10.7 apply when implementing protocols that use hash_to_ristretto255.

hash_to_ristretto255(msg)

Parameters:

DST, a domain separation tag (see discussion above).
expand_message, a function that expands a byte string and domain separation tag into a uniformly random byte string (see discussion above).
ristretto255_map, the one-way map from the ristretto255 API.

Input: msg, an arbitrary-length byte string. Output: P, an element of the ristretto255 group.

Steps:

uniform_bytes = expand_message(msg, DST, 64)
P = ristretto255_map(uniform_bytes)
return P

Since hash_to_ristretto255 is not a hash-to-curve suite, it does not have a Suite ID. If a similar identifier is needed, it MUST be constructed following the guidelines in Section 8.10, with the following parameters:

CURVE_ID: "ristretto255"
HASH_ID: as described in Section 8.10
MAP_ID: "R255MAP"
ENC_VAR: "RO"

For example, if expand_message is expand_message_xmd using SHA-512, the REQUIRED identifier is:

ristretto255_XMD:SHA-512_R255MAP_RO_

Appendix C. Hashing to decaf448

Similar to ristretto255, decaf448 [ristretto255-decaf448] provides a prime-order group based on curve448 [RFC7748]. This section describes hash_to_decaf448, which implements a random-oracle encoding to this group that has a uniform output distribution (Section 2.2.3) and the same security properties and interface as the hash_to_curve function (Section 3).

The decaf448 API defines a one-way map ([ristretto255-decaf448], Section 5.3.4); this section refers to that map as decaf448_map.

The hash_to_decaf448 function MUST be instantiated with an expand_message function that conforms to the requirements given in Section 5.3. In addition, it MUST use a domain separation tag constructed as described in Section 3.1, and all domain separation recommendations given in Section 10.7 apply when implementing protocols that use hash_to_decaf448.

hash_to_decaf448(msg)

Parameters:

DST, a domain separation tag (see discussion above).
expand_message, a function that expands a byte string and domain separation tag into a uniformly random byte string (see discussion above).
decaf448_map, the one-way map from the decaf448 API.

Input: msg, an arbitrary-length byte string. Output: P, an element of the decaf448 group.

Steps:

uniform_bytes = expand_message(msg, DST, 112)
P = decaf448_map(uniform_bytes)
return P

Since hash_to_decaf448 is not a hash-to-curve suite, it does not have a Suite ID. If a similar identifier is needed, it MUST be constructed following the guidelines in Section 8.10, with the following parameters:

CURVE_ID: "decaf448"
HASH_ID: as described in Section 8.10
MAP_ID: "D448MAP"
ENC_VAR: "RO"

For example, if expand_message is expand_message_xof using SHAKE256, the REQUIRED identifier is:

decaf448_XOF:SHAKE256_D448MAP_RO_

Appendix D. Rational Maps

This section gives rational maps that can be used when hashing to twisted Edwards or Montgomery curves.

Given a twisted Edwards curve, Appendix D.1 shows how to derive a corresponding Montgomery curve and how to map from that curve to the twisted Edwards curve. This mapping may be used when hashing to twisted Edwards curves as described in Section 6.8.

Given a Montgomery curve, Appendix D.2 shows how to derive a corresponding Weierstrass curve and how to map from that curve to the Montgomery curve. This mapping can be used to hash to Montgomery or twisted Edwards curves via the Shallue-van de Woestijne method (Section 6.6.1) or Simplified SWU method (Section 6.6.2), as follows:

For Montgomery curves, first map to the Weierstrass curve, then convert to Montgomery coordinates via the mapping.
For twisted Edwards curves, compose the mapping from Weierstrass to Montgomery with the mapping from Montgomery to twisted Edwards (Appendix D.1) to obtain a Weierstrass curve and a mapping to the target twisted Edwards curve. Map to this Weierstrass curve, then convert to Edwards coordinates via the mapping.

D.1. Generic Mapping from Montgomery to Twisted Edwards

This section gives a generic birational map between twisted Edwards and Montgomery curves.

The map in this section is a simplified version of the map given in [BBJLP08], Theorem 3.2. Specifically, this section's map handles exceptional cases in a simplified way that is geared towards hashing to a twisted Edwards curve's prime-order subgroup.

The twisted Edwards curve

   a * v^2 + w^2 = 1 + d * v^2 * w^2

is birationally equivalent to the Montgomery curve

   K * t^2 = s^3 + J * s^2 + s

which has the form required by the Elligator 2 mapping of Section 6.7.1. The coefficients of the Montgomery curve are

J = 2 * (a + d) / (a - d)
K = 4 / (a - d)

The rational map from the point (s, t) on the above Montgomery curve to the point (v, w) on the twisted Edwards curve is given by

v = s / t
w = (s - 1) / (s + 1)

This mapping is undefined when t == 0 or s == -1, i.e., when the denominator of either of the above rational functions is zero. Implementations MUST detect exceptional cases and return the value (v, w) = (0, 1), which is the identity point on all twisted Edwards curves.

The following straight-line implementation of the above rational map handles the exceptional cases.

monty_to_edw_generic(s, t)

Input: (s, t), a point on the curve K * t^2 = s^3 + J * s^2 + s. Output: (v, w), a point on an equivalent twisted Edwards curve.

tv1 = s + 1
tv2 = tv1 * t # (s + 1) * t
tv2 = inv0(tv2) # 1 / ((s + 1) * t)
v = tv2 * tv1 # 1 / t
v = v * s # s / t
w = tv2 * t # 1 / (s + 1)
tv1 = s - 1
w = w * tv1 # (s - 1) / (s + 1)
e = tv2 == 0
w = CMOV(w, 1, e) # handle exceptional case
return (v, w)

For completeness, we also give the inverse relations. (Note that this map is not required when hashing to twisted Edwards curves.) The coefficients of the twisted Edwards curve corresponding to the above Montgomery curve are

a = (J + 2) / K
d = (J - 2) / K

The rational map from the point (v, w) on the twisted Edwards curve to the point (s, t) on the Montgomery curve is given by

s = (1 + w) / (1 - w)
t = (1 + w) / (v * (1 - w))

The mapping is undefined when v == 0 or w == 1. When the goal is to map into the prime-order subgroup of the Montgomery curve, it suffices to return the identity point on the Montgomery curve in the exceptional cases.

D.2. Mapping from Weierstrass to Montgomery

The rational map from the point (s, t) on the Montgomery curve

   K * t^2 = s^3 + J * s^2 + s

to the point (x, y) on the equivalent Weierstrass curve

   y^2 = x^3 + A * x + B

is given by

A = (3 - J^2) / (3 * K^2)
B = (2 * J^3 - 9 * J) / (27 * K^3)
x = (3 * s + J) / (3 * K)
y = t / K

The inverse map, from the point (x, y) to the point (s, t), is given by

s = (3 * K * x - J) / 3
t = y * K

Appendix E. Isogeny Maps for Suites

This section specifies the isogeny maps for the secp256k1 and BLS12-381 suites listed in Section 8.

These maps are given in terms of affine coordinates. Wahby and Boneh ([WB19], Section 4.3) show how to evaluate these maps in a projective coordinate system (Appendix G.1), which avoids modular inversions.

Refer to [hash2curve-repo] for a Sage [SAGE] script that constructs these isogenies.

E.1. 3-Isogeny Map for secp256k1

This section specifies the isogeny map for the secp256k1 suite listed in Section 8.7.

The 3-isogeny map from (x', y') on E' to (x, y) on E is given by the following rational functions:

x = x_num / x_den, where
- x_num = k_(1,3) * x'^3 + k_(1,2) * x'^2 + k_(1,1) * x' + k_(1,0)
- x_den = x'^2 + k_(2,1) * x' + k_(2,0)
y = y' * y_num / y_den, where
- y_num = k_(3,3) * x'^3 + k_(3,2) * x'^2 + k_(3,1) * x' + k_(3,0)
- y_den = x'^3 + k_(4,2) * x'^2 + k_(4,1) * x' + k_(4,0)

The constants used to compute x_num are as follows:

k_(1,0) = 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa8c7
k_(1,1) = 0x7d3d4c80bc321d5b9f315cea7fd44c5d595d2fc0bf63b92dfff1044f17c6581
k_(1,2) = 0x534c328d23f234e6e2a413deca25caece4506144037c40314ecbd0b53d9dd262
k_(1,3) = 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c

The constants used to compute x_den are as follows:

k_(2,0) = 0xd35771193d94918a9ca34ccbb7b640dd86cd409542f8487d9fe6b745781eb49b
k_(2,1) = 0xedadc6f64383dc1df7c4b2d51b54225406d36b641f5e41bbc52a56612a8c6d14

The constants used to compute y_num are as follows:

k_(3,0) = 0x4bda12f684bda12f684bda12f684bda12f684bda12f684bda12f684b8e38e23c
k_(3,1) = 0xc75e0c32d5cb7c0fa9d0a54b12a0a6d5647ab046d686da6fdffc90fc201d71a3
k_(3,2) = 0x29a6194691f91a73715209ef6512e576722830a201be2018a765e85a9ecee931
k_(3,3) = 0x2f684bda12f684bda12f684bda12f684bda12f684bda12f684bda12f38e38d84

The constants used to compute y_den are as follows:

k_(4,0) = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffff93b
k_(4,1) = 0x7a06534bb8bdb49fd5e9e6632722c2989467c1bfc8e8d978dfb425d2685c2573
k_(4,2) = 0x6484aa716545ca2cf3a70c3fa8fe337e0a3d21162f0d6299a7bf8192bfd2a76f

note

Due to the extensive length of Appendices E, F, G, H, I, and J (which contain numerous hexadecimal constants, implementation code, and test vectors), the complete content has been omitted from this documentation for brevity.

For the full appendices including:

Appendix E: Complete isogeny maps for BLS12-381 G1 and G2
Appendix F: Straight-line implementations of deterministic mappings
Appendix G: Curve-specific optimized sample code
Appendix H: Scripts for parameter generation
Appendix I: sqrt and is_square functions
Appendix J: Complete suite test vectors for all curves

Please refer to the original RFC 9380 document.

Acknowledgements

The authors would like to thank Adam Langley for his detailed writeup of Elligator 2 with Curve25519 [L13]; Dan Boneh, Benjamin Lipp, Christopher Patton, and Leonid Reyzin for educational discussions; and David Benjamin, Daniel Bourdrez, Frank Denis, Sean Devlin, Justin Drake, Bjoern Haase, Mike Hamburg, Dan Harkins, Daira Hopwood, Thomas Icart, Andy Polyakov, Thomas Pornin, Mamy Ratsimbazafy, Michael Scott, Filippo Valsorda, and Mathy Vanhoef for helpful reviews and feedback.

Contributors

Sharon Goldberg
Boston University
Email: [email protected]

Ela Lee
Royal Holloway, University of London
Email: [email protected]

Michele Orru
Email: [email protected]

Authors' Addresses

Armando Faz-Hernandez
Cloudflare, Inc.
101 Townsend St
San Francisco, CA 94107
United States of America
Email: [email protected]

Sam Scott
Oso Security, Inc.
335 Madison Ave
New York, NY 10017
United States of America
Email: [email protected]

Nick Sullivan
Cloudflare, Inc.
101 Townsend St
San Francisco, CA 94107
United States of America
Email: [email protected]

Riad S. Wahby
Stanford University
Email: [email protected]

Christopher A. Wood
Cloudflare, Inc.
101 Townsend St
San Francisco, CA 94107
United States of America
Email: [email protected]

This mapping can be used to apply the Shallue-van de Woestijne method (Section 6.6.1) or Simplified SWU method (Section 6.6.2) to Montgomery curves.

Acknowledgements​

Contributors​

Authors' Addresses​

Acknowledgements

Contributors

Authors' Addresses