RFC 9380: Hashing to Elliptic Curves
- A. Faz-Hernandez,
- S. Scott,
- N. Sullivan,
- R. S. Wahby,
- C. A. Wood
Abstract
This document specifies a number of algorithms for encoding or hashing an arbitrary string to a point on an elliptic curve. This document is a product of the Crypto Forum Research Group (CFRG) in the IRTF.¶
Status of This Memo
This document is not an Internet Standards Track specification; it is published for informational purposes.¶
This document is a product of the Internet Research Task Force
(IRTF). The IRTF publishes the results of Internet
Information about the current status of this document, any
errata, and how to provide feedback on it may be obtained at
https://
Copyright Notice
Copyright (c) 2023 IETF Trust and the persons identified as the document authors. All rights reserved.¶
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://
1. Introduction
Many cryptographic protocols require a procedure that encodes an arbitrary input,
e.g., a password, to a point on an elliptic curve. This procedure is known
as hashing to an elliptic curve, where the hashing procedure provides collision
resistance and does not reveal the discrete logarithm of the output point.
Prominent examples of cryptosystems that hash to elliptic curves include
password
Unfortunately for implementors, the precise hash function that is suitable for a given protocol implemented using a given elliptic curve is often unclear from the protocol's description. Meanwhile, an incorrect choice of hash function can have disastrous consequences for security.¶
This document aims to bridge this gap by providing a comprehensive set of
recommended algorithms for a range of curve types.
Each algorithm conforms to a common interface: it takes as input an arbitrary
Readers wishing to quickly specify or implement a conforming hash function should consult Section 8, which lists recommended hash-to-curve suites and describes both how to implement an existing suite and how to specify a new one.¶
This document does not specify probabilistic rejection sampling methods, sometimes
referred to as "try
This document represents the consensus of the Crypto Forum Research Group (CFRG).¶
1.1. Requirements Notation
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶
2. Background
2.1. Elliptic Curves
The following is a brief definition of elliptic curves, with an emphasis on important parameters and their relation to hashing to curves. For further reference on elliptic curves, consult [CFADLNV05] or [W08].¶
Let F be the finite field GF(q) of prime characteristic p > 3. (This document does not consider elliptic curves over fields of characteristic 2 or 3.) In most cases, F is a prime field, so q = p. Otherwise, F is an extension field, so q = p^m for an integer m > 1. This document writes elements of extension fields in a primitive element or polynomial basis, i.e., as a vector of m elements of GF(p) written in ascending order by degree. The entries of this vector are indexed in ascending order starting from 1, i.e., x = (x_1, x_2, ..., x_m). For example, if q = p^2 and the primitive element basis is (1, I), then x = (a, b) corresponds to the element a + b * I, where x_1 = a and x_2 = b. (Note that all choices of basis are isomorphic, but certain choices may result in a more efficient implementation; this document does not make any particular assumptions about choice of basis.)¶
An elliptic curve E is specified by an equation in two variables and a finite field F. An elliptic curve equation takes one of several standard forms, including (but not limited to) Weierstrass, Montgomery, and Edwards.¶
The curve E induces an algebraic group of order n, meaning that the group has n distinct elements. (This document uses additive notation for the elliptic curve group operation.) Elements of an elliptic curve group are points with affine coordinates (x, y) satisfying the curve equation, where x and y are elements of F. In addition, all elliptic curve groups have a distinguished element, the identity point, which acts as the identity element for the group operation. On certain curves (including Weierstrass and Montgomery curves), the identity point cannot be represented as an (x, y) coordinate pair.¶
For security reasons, cryptographic applications of elliptic curves generally require using a (sub)group of prime order. Let G be such a subgroup of the curve of prime order r, where n = h * r. In this equation, h is an integer called the cofactor. An algorithm that takes as input an arbitrary point on the curve E and produces as output a point in the subgroup G of E is said to "clear the cofactor." Such algorithms are discussed in Section 7.¶
Certain hash-to-curve algorithms restrict the form of the curve equation, the characteristic of the field, or the parameters of the curve. For each algorithm presented, this document lists the relevant restrictions.¶
The table below summarizes quantities relevant to hashing to curves:¶
2.2. Terminology
In this section, we define important terms used throughout the document.¶
2.2.1. Mappings
A mapping is a deterministic function from an element of the field F to a point on an elliptic curve E defined over F.¶
In general, the set of all points that a mapping can produce over all possible inputs may be only a subset of the points on an elliptic curve (i.e., the mapping may not be surjective). In addition, a mapping may output the same point for two or more distinct inputs (i.e., the mapping may not be injective). For example, consider a mapping from F to an elliptic curve having n points: if the number of elements of F is not equal to n, then this mapping cannot be bijective (i.e., both injective and surjective), since the mapping is defined to be deterministic.¶
Mappings may also be invertible, meaning that there is an efficient algorithm that, for any point P output by the mapping, outputs an x in F such that applying the mapping to x outputs P. Some of the mappings given in Section 6 are invertible, but this document does not discuss inversion algorithms.¶
2.2.2. Encodings
Encodings are closely related to mappings.
Like a mapping, an encoding is a function that outputs a point on an elliptic curve.
In contrast to a mapping, however, the input to an encoding is an arbitrary
This document constructs deterministic encodings by composing a hash function Hf
with a deterministic mapping.
In particular, Hf takes as input an arbitrary string and outputs an element of F.
The deterministic mapping takes that element as input and outputs a point on an
elliptic curve E defined over F.
Since Hf takes arbitrary
Like mappings, encodings may be invertible, meaning that there is an efficient algorithm that, for any point P output by the encoding, outputs a string s such that applying the encoding to s outputs P. However, the instantiation of Hf used by all encodings specified in this document (Section 5) is not invertible; thus, those encodings are also not invertible.¶
In some applications of hashing to elliptic curves, it is important that encodings do not leak information through side channels. [VR20] is one example of this type of leakage leading to a security vulnerability. See Section 10.3 for further discussion.¶
2.2.3. Random Oracle Encodings
A random-oracle encoding satisfies a strong property: it can be proved
indifferentiabl
Both constructions described in Section 3 are indifferentiabl
A random-oracle encoding with a uniform output distribution is suitable for use in many cryptographic protocols proven secure in the random-oracle model. See Section 10.1 for further discussion.¶
2.2.4. Serialization
A procedure related to encoding is the conversion of an elliptic curve point to a bit string.
This is called serialization, and it is typically used for compactly storing or transmitting points.
The inverse operation, deserialization
Deserialization is different from encoding in that only certain strings
(namely, those output by the serialization procedure) can be deserialized.
In contrast, this document is concerned with encodings from arbitrary strings
to elliptic curve points.
This document does not cover serialization or deserialization
2.2.5. Domain Separation
Cryptographic protocols proven secure in the random-oracle model are often analyzed under the assumption that the random oracle only answers queries associated with that protocol (including queries made by adversaries) [BR93]. In practice, this assumption does not hold if two protocols use the same function to instantiate the random oracle. Concretely, consider protocols P1 and P2 that query a random-oracle RO: if P1 and P2 both query RO on the same value x, the security analysis of one or both protocols may be invalidated.¶
A common way of addressing this issue is called domain separation, which allows a single random oracle to simulate multiple, independent oracles. This is effected by ensuring that each simulated oracle sees queries that are distinct from those seen by all other simulated oracles. For example, to simulate two oracles RO1 and RO2 given a single oracle RO, one might define¶
where || is the concatenation operator. In this example, "RO1" and "RO2" are called domain separation tags (DSTs); they ensure that queries to RO1 and RO2 cannot result in identical queries to RO, meaning that it is safe to treat RO1 and RO2 as independent oracles.¶
In general, domain separation requires defining a distinct injective encoding for each oracle being simulated. In the above example, "RO1" and "RO2" have the same length and thus satisfy this requirement when used as prefixes. The algorithms specified in this document take a different approach to ensuring injectivity; see Sections 5.3 and 10.7 for more details.¶
3. Encoding Byte Strings to Elliptic Curves
This section presents a general framework and interface for encoding byte strings to points on an elliptic curve. The constructions in this section rely on three basic functions:¶
The two encodings (Section 2.2.2) defined in this section have the same interface and are both random-oracle encodings (Section 2.2.3). Both are implemented as a composition of the three basic functions above. The difference between the two is that their outputs are sampled from different distributions:¶
Each hash-to-curve suite in Section 8 instantiates one of these encoding functions for a specific elliptic curve.¶
3.1. Domain Separation Requirements
All uses of the encoding functions defined in this document MUST include domain separation (Section 2.2.5) to avoid interfering with other uses of similar functionality.¶
Applications that instantiate multiple, independent instances of either hash_to_curve or encode_to_curve MUST enforce domain separation between those instances. This requirement applies in both the case of multiple instances targeting the same curve and the case of multiple instances targeting different curves. (This is because the internal hash_to_field primitive (Section 5) requires domain separation to guarantee independent outputs.)¶
Domain separation is enforced with a domain separation tag (DST), which is a byte string constructed according to the following requirements:¶
As an example, consider a fictional application named Quux
that defines several different ciphersuites, each for a different curve.
A reasonable choice of tag is "QUUX
As another example, consider a fictional application named Baz that requires
two independent random oracles to the same curve.
Reasonable choices of tags for these oracles are
"BAZ
The example tags given above are assumed to be ASCII-encoded byte strings without null termination, which is the RECOMMENDED format. Other encodings can be used, but in all cases the encoding as a sequence of bytes MUST be specified unambiguously.¶
4. Utility Functions
Algorithms in this document use the utility functions described below,
plus standard arithmetic operations (addition, multiplication, modular
reduction, etc.) and elliptic curve point operations (point addition and
scalar multiplication
For security, implementations of these functions SHOULD be constant time:
in brief, this means that execution time and memory access patterns SHOULD NOT
depend on the values of secret inputs, intermediate values, or outputs.
For such constant-time implementations
Guidance on implementing low-level operations (in constant time or otherwise) is beyond the scope of this document; readers should consult standard reference material [MOV96] [CFADLNV05].¶
4.1. The sgn0 Function
This section defines a generic sgn0 implementation that applies to any field F = GF(p^m). It also gives simplified implementations for the cases F = GF(p) and F = GF(p^2).¶
The definition of the sgn0 function for extension fields relies on the polynomial basis or vector representation of field elements, and iterates over the entire vector representation of the input element. As a result, sgn0 depends on the primitive polynomial used to define the polynomial basis; see Section 8 for more information about this basis, and see Section 2.1 for a discussion of representing elements of extension fields as vectors.¶
When m == 1, sgn0 can be significantly simplified:¶
The case m == 2 is only slightly more complicated:¶
5. Hashing to a Finite Field
The hash_to_field function hashes a byte string msg of arbitrary length into one or more elements of a field F. This function works in two steps: it first hashes the input byte string to produce a uniformly random byte string, and then interprets this byte string as one or more elements of F.¶
For the first step, hash_to_field calls an auxiliary function expand_message.
This document defines two variants of expand_message: one appropriate
for hash functions like SHA-2 [FIPS180-4] or SHA-3 [FIPS202], and another
appropriate for extendable
Implementors MUST NOT use rejection sampling to generate a uniformly random
element of F, to ensure that the hash_to_field function is amenable to
constant-time implementation.
The reason is that rejection sampling procedures are difficult to implement
in constant time, and later well-meaning "optimizations" may silently render
an implementation non
The hash_to_field function is also suitable for securely hashing to scalars. For example, when hashing to the scalar field for an elliptic curve (sub)group with prime order r, it suffices to instantiate hash_to_field with target field GF(r).¶
The hash_to_field function is designed to be indifferentiabl
To control bias, hash_to_field instead uses random integers whose length is at least ceil(log2(p)) + k bits, where k is the target security level for the suite in bits. Reducing such integers mod p gives bias at most 2^-k for any p; this bias is appropriate when targeting k-bit security. For each such integer, hash_to_field uses expand_message to obtain L uniform bytes, where¶
These uniform bytes are then interpreted as an integer via OS2IP. For example, for a 255-bit prime p, and k = 128-bit security, L = ceil((255 + 128) / 8) = 48 bytes.¶
Note that k is an upper bound on the security level for the corresponding curve. See Section 10.8 for more details and Section 8.9 for guidelines on choosing k for a given curve.¶
5.1. Efficiency Considerations in Extension Fields
The hash_to_field function described in this section is inefficient for certain extension fields. Specifically, when hashing to an element of the extension field GF(p^m), hash_to_field requires expanding msg into m * L bytes (for L as defined above). For extension fields where log2(p) is significantly smaller than the security level k, this approach is inefficient: it requires expand_message to output roughly m * log2(p) + m * k bits, whereas m * log2(p) + k bytes suffices to generate an element of GF(p^m) with bias at most 2^-k. In such cases, applications MAY use an alternative hash_to_field function, provided it meets the following security requirements:¶
For example, Pornin [P20] describes a method for hashing to GF(9767^19) that meets these requirements while using fewer output bits from expand_message than hash_to_field would for that field.¶
5.2. hash_to_field Implementation
The following procedure implements hash_to_field.¶
The expand_message parameter to this function MUST conform to the requirements given in Section 5.3. Section 3.1 discusses the REQUIRED method for constructing DST, the domain separation tag. Note that hash_to_field may fail (ABORT) if expand_message fails.¶
5.3. expand_message
expand_message is a function that generates a uniformly random byte string. It takes three arguments:¶
This document defines the following two variants of expand_message:¶
These variants should suffice for the vast majority of use cases, but other variants are possible; Section 5.3.4 discusses requirements.¶
5.3.1. expand_message_xmd
The expand
SHA-2 [FIPS180-4] and SHA-3 [FIPS202] are typical and RECOMMENDED choices. As an example, for the 128-bit security level, b >= 256 bits and either SHA-256 or SHA3-256 would be an appropriate choice.¶
The hash function H is assumed to work by repeatedly ingesting fixed-length blocks of data. The length in bits of these blocks is called the input block size (s). As examples, s = 1024 for SHA-512 [FIPS180-4] and s = 576 for SHA3-512 [FIPS202]. For correctness, H requires b <= s.¶
The following procedure implements expand
Note that the string Z_pad (step 6) is prefixed to msg before computing b_0 (step 7). This is necessary for security when H is a Merkle-Damgaard hash, e.g., SHA-2 (see Section 10.6). Hashing this additional data means that the cost of computing b_0 is higher than the cost of simply computing H(msg). In most settings, this overhead is negligible, because the cost of evaluating H is much less than the other costs involved in hashing to a curve.¶
It is possible, however, to entirely avoid this overhead by taking advantage
of the fact that Z_pad depends only on H, and not on the arguments to
expand
5.3.2. expand_message_xof
The expand
The SHAKE XOF family [FIPS202] is a typical and RECOMMENDED choice. As an example, for 128-bit security, SHAKE128 would be an appropriate choice.¶
The following procedure implements expand
5.3.3. Using DSTs Longer than 255 Bytes
The expand_message variants defined in this section accept domain separation tags of at most 255 bytes. If applications require a domain separation tag longer than 255 bytes, e.g., because of requirements imposed by an invoking protocol, implementors MUST compute a short domain separation tag by hashing, as follows:¶
Here, a_very_long_DST is the DST whose length is greater than 255 bytes,
"H2C
5.3.4. Defining Other expand_message Variants
When defining a new expand_message variant, the most important consideration
is that hash_to_field models expand_message as a random oracle.
Thus, implementors SHOULD prove indifferentiabi
In addition, expand_message variants:¶
In addition, each expand_message variant MUST specify a unique EXP_TAG that identifies that variant in a Suite ID. See Section 8.10 for more information.¶
6. Deterministic Mappings
The mappings in this section are suitable for implementing either nonuniform or uniform encodings using the constructions in Section 3. Certain mappings restrict the form of the curve or its parameters. For each mapping presented, this document lists the relevant restrictions.¶
Note that mappings in this section are not interchangeable
6.1. Choosing a Mapping Function
This section gives brief guidelines on choosing a mapping function for a given elliptic curve. Note that the suites given in Section 8 are recommended mappings for the respective curves.¶
If the target elliptic curve is a Montgomery curve (Section 6.7), the Elligator 2 method (Section 6.7.1) is recommended. Similarly, if the target elliptic curve is a twisted Edwards curve (Section 6.8), the twisted Edwards Elligator 2 method (Section 6.8.2) is recommended.¶
The remaining cases are Weierstrass curves. For curves supported by the Simplified Shallue-van de Woestijne-Ulas (SWU) method (Section 6.6.2), that mapping is the recommended one. Otherwise, the Simplified SWU method for AB == 0 (Section 6.6.3) is recommended if the goal is best performance, while the Shallue-van de Woestijne method (Section 6.6.1) is recommended if the goal is simplicity of implementation. (The reason for this distinction is that the Simplified SWU method for AB == 0 requires implementing an isogeny map in addition to the mapping function, while the Shallue-van de Woestijne method does not.)¶
The Shallue-van de Woestijne method (Section 6.6.1) works with any curve and may be used in cases where a generic mapping is required. Note, however, that this mapping is almost always more computationally expensive than the curve-specific recommendations above.¶
6.2. Interface
The generic interface shared by all mappings in this section is as follows:¶
The input u and outputs x and y are elements of the field F. The affine coordinates (x, y) specify a point on an elliptic curve defined over F. Note, however, that the point (x, y) is not a uniformly random point.¶
6.4. Sign of the Resulting Point
In general, elliptic curves have equations of the form y^2 = g(x). The mappings in this section first identify an x such that g(x) is square, then take a square root to find y. Since there are two square roots when g(x) != 0, this may result in an ambiguity regarding the sign of y.¶
When necessary, the mappings in this section resolve this ambiguity by
specifying the sign of the y-coordinate in terms of the input to the mapping
function.
Two main reasons support this approach: first, this covers elliptic curves
over any field in a uniform way, and second, it gives implementors leeway
in optimizing square-root implementations
6.5. Exceptional Cases
Mappings may have exceptional cases, i.e., inputs u
on which the mapping is undefined. These cases must be handled
carefully, especially for constant-time implementations
For each mapping in this section, we discuss the exceptional cases and show how to handle them in constant time. Note that all implementations SHOULD use inv0 (Section 4) to compute multiplicative inverses, to avoid exceptional cases that result from attempting to compute the inverse of 0.¶
6.6. Mappings for Weierstrass Curves
The mappings in this section apply to a target curve E defined by the equation¶
where 4 * A^3 + 27 * B^2 != 0.¶
6.6.1. Shallue-van de Woestijne Method
Shallue and van de Woestijne [SW06] describe a mapping that applies to essentially any elliptic curve. (Note, however, that this mapping is more expensive to evaluate than the other mappings in this document.)¶
The parameterizatio
Preconditions: A Weierstrass curve y^2 = x^3 + A * x + B.¶
Constants:¶
Sign of y: Inputs u and -u give the same x-coordinate for many values of u. Thus, we set sgn0(y) == sgn0(u).¶
Exceptions: The exceptional cases for u occur when (1 + u^2 * g(Z)) * (1 - u^2 * g(Z)) == 0. The restrictions on Z given above ensure that implementations that use inv0 to invert this product are exception free.¶
Operations:¶
Appendix F.1 gives an example straight-line implementation of this mapping.¶
6.6.2. Simplified Shallue-van de Woestijne-Ulas Method
The function map
Preconditions: A Weierstrass curve y^2 = x^3 + A * x + B where A != 0 and B != 0.¶
Constants:¶
Sign of y: Inputs u and -u give the same x-coordinate. Thus, we set sgn0(y) == sgn0(u).¶
Exceptions: The exceptional cases are values of u such that Z^2 * u^4 + Z * u^2 == 0. This includes u == 0 and may include other values that depend on Z. Implementations must detect this case and set x1 = B / (Z * A), which guarantees that g(x1) is square by the condition on Z given above.¶
Operations:¶
Appendix F.2 gives a general and optimized straight-line implementation of this mapping. For more information on optimizing this mapping, see Section 4 of [WB19] or the example code found at [hash2curve-repo].¶
6.6.3. Simplified SWU for AB == 0
Wahby and Boneh [WB19] show how to adapt the Simplified SWU mapping to Weierstrass curves having A == 0 or B == 0, which the mapping of Section 6.6.2 does not support. (The case A == B == 0 is excluded because y^2 = x^3 is not an elliptic curve.)¶
This method applies to curves like secp256k1 [SEC2] and to pairing
This method requires finding another elliptic curve E' given by the equation¶
that is isogenous to E and has A' != 0 and B' != 0. (See [WB19], Appendix A, for one way of finding E' using [SAGE].) This isogeny defines a map iso_map(x', y') given by a pair of rational functions. iso_map takes as input a point on E' and produces as output a point on E.¶
Once E' and iso_map are identified, this mapping works as follows: on input u, first apply the Simplified SWU mapping to get a point on E', then apply the isogeny map to that point to get a point on E.¶
Note that iso_map is a group homomorphism, meaning that point addition commutes with iso_map. Thus, when using this mapping in the hash_to_curve construction discussed in Section 3, one can effect a small optimization by first mapping u0 and u1 to E', adding the resulting points on E', and then applying iso_map to the sum. This gives the same result while requiring only one evaluation of iso_map.¶
Preconditions: An elliptic curve E' with A' != 0 and B' != 0 that is isogenous to the target curve E with isogeny map iso_map from E' to E.¶
Helper functions:¶
Sign of y: For this map, the sign is determined by map
Exceptions: map
Operations:¶
See [hash2curve-repo] or Section 4.3 of [WB19] for details on implementing the isogeny map.¶
6.7. Mappings for Montgomery Curves
The mapping defined in this section applies to a target curve M defined by the equation¶
6.7.1. Elligator 2 Method
Bernstein, Hamburg, Krasnova, and Lange give a mapping that applies to any curve with a point of order 2 [BHKL13], which they call Elligator 2.¶
Preconditions: A Montgomery curve K * t^2 = s^3 + J * s^2 + s where J != 0, K != 0, and (J^2 - 4) / K^2 is non-zero and non-square in F.¶
Constants:¶
Sign of t: This mapping fixes the sign of t as specified in [BHKL13]. No additional adjustment is required.¶
Exceptions: The exceptional case is Z * u^2 == -1, i.e., 1 + Z * u^2 == 0. Implementations must detect this case and set x1 = -(J / K). Note that this can only happen when q = 3 (mod 4).¶
Operations:¶
Appendix F.3 gives an example straight-line implementation of this mapping. Appendix G.2 gives optimized straight-line procedures that apply to specific classes of curves and base fields.¶
6.8. Mappings for Twisted Edwards Curves
Twisted Edwards curves (a class of curves that includes Edwards curves) are given by the equation¶
with a != 0, d != 0, and a != d [BBJLP08].¶
These curves are closely related to Montgomery curves (Section 6.7): every twisted Edwards curve is birationally equivalent to a Montgomery curve ([BBJLP08], Theorem 3.2). This equivalence yields an efficient way of hashing to a twisted Edwards curve: first, hash to an equivalent Montgomery curve, then transform the result into a point on the twisted Edwards curve via a rational map. This method of hashing to a twisted Edwards curve thus requires identifying a corresponding Montgomery curve and rational map. We describe how to identify such a curve and map immediately below.¶
6.8.1. Rational Maps from Montgomery to Twisted Edwards Curves
There are two ways to select a Montgomery curve and rational map for use when hashing to a given twisted Edwards curve. The selected Montgomery curve and rational map MUST be specified as part of the hash-to-curve suite for a given twisted Edwards curve; see Section 8.¶
6.8.2. Elligator 2 Method
Preconditions: A twisted Edwards curve E and an equivalent Montgomery curve M meeting the requirements in Section 6.8.1.¶
Helper functions:¶
Sign of t (and v): For this map, the sign is determined by map
Exceptions: The exceptions for the Elligator 2 mapping are as given in Section 6.7.1. The exceptions for the rational map are as given in Section 6.8.1. No other exceptions are possible.¶
The following procedure implements the Elligator 2 mapping for a twisted Edwards curve. (Note that the output point is denoted (v, w) because it is a point on the target twisted Edwards curve.)¶
7. Clearing the Cofactor
The mappings of Section 6 always output a point on the elliptic curve, i.e., a point in a group of order h * r (Section 2.1). Obtaining a point in G may require a final operation commonly called "clearing the cofactor," which takes as input any point on the curve and produces as output a point in the prime-order (sub)group G (Section 2.1).¶
The cofactor can always be cleared via scalar multiplication by h. For elliptic curves where h = 1, i.e., the curves with a prime number of points, no operation is required. This applies, for example, to the NIST curves P-256, P-384, and P-521 [FIPS186-4].¶
In some cases, it is possible to clear the cofactor via a faster method than scalar multiplication by h. These methods are equivalent to (but usually faster than) multiplication by some scalar h_eff whose value is determined by the method and the curve. Examples of fast cofactor clearing methods include the following:¶
The clear_cofactor function is parameterized by a scalar h_eff. Specifically,¶
where * represents scalar multiplication. When a curve does not support a fast cofactor clearing method, h_eff = h and the cofactor MUST be cleared via scalar multiplication.¶
When a curve admits a fast cofactor clearing method, clear_cofactor MAY be evaluated either via that method or via scalar multiplication by the equivalent h_eff; these two methods give the same result. Note that in this case scalar multiplication by the cofactor h does not generally give the same result as the fast method and MUST NOT be used.¶
8. Suites for Hashing
This section lists recommended suites for hashing to standard elliptic curves.¶
A hash-to-curve suite fully specifies the procedure for hashing byte strings to points on a specific elliptic curve group. Section 8.1 describes how to implement a suite. Applications that require hashing to an elliptic curve should use either an existing suite or a new suite specified as described in Section 8.9.¶
All applications using a hash-to-curve suite MUST choose a domain separation tag (DST) in accordance with the guidelines in Section 3.1. In addition, applications whose security requires a random oracle that returns uniformly random points on the target curve MUST use a suite whose encoding type is hash_to_curve; see Section 3 and immediately below for more information.¶
A hash-to-curve suite comprises the following parameters:¶
In addition to the above parameters, the mapping f may require additional parameters Z, M, rational_map, E', or iso_map. When applicable, these MUST be specified.¶
The table below lists suites RECOMMENDED for some elliptic curves. The corresponding parameters are given in the following subsections. Applications instantiating cryptographic protocols whose security analysis relies on a random oracle that outputs points with a uniform distribution MUST NOT use a nonuniform encoding. Moreover, applications that use a nonuniform encoding SHOULD carefully analyze the security implications of nonuniformity. When the required encoding is not clear, applications SHOULD use a uniform encoding for security.¶
8.1. Implementing a Hash-to-Curve Suite
A hash-to-curve suite requires the following functions. Note that some of these require utility functions from Section 4.¶
8.2. Suites for NIST P-256
This section defines ciphersuites for the NIST P-256 elliptic curve [FIPS186-4].¶
P256
P256
An optimized example implementation of the Simplified SWU mapping to P-256 is given in Appendix F.2.¶
8.3. Suites for NIST P-384
This section defines ciphersuites for the NIST P-384 elliptic curve [FIPS186-4].¶
P384
P384
An optimized example implementation of the Simplified SWU mapping to P-384 is given in Appendix F.2.¶
8.4. Suites for NIST P-521
This section defines ciphersuites for the NIST P-521 elliptic curve [FIPS186-4].¶
P521
P521
An optimized example implementation of the Simplified SWU mapping to P-521 is given in Appendix F.2.¶
8.5. Suites for curve25519 and edwards25519
This section defines ciphersuites for curve25519 and edwards25519 [RFC7748].
Note that these ciphersuites MUST NOT be used when hashing to ristretto255
[ristretto255
curve25519
edwards25519
curve25519
edwards25519
Optimized example implementations of the above mappings are given in Appendix G.2.1 and Appendix G.2.2.¶
8.6. Suites for curve448 and edwards448
This section defines ciphersuites for curve448 and edwards448 [RFC7748].
Note that these ciphersuites MUST NOT be used when hashing to decaf448
[ristretto255
curve448
edwards448
curve448
edwards448
Optimized example implementations of the above mappings are given in Appendix G.2.3 and Appendix G.2.4.¶
8.7. Suites for secp256k1
This section defines ciphersuites for the secp256k1 elliptic curve [SEC2].¶
secp256k1
secp256k1
An optimized example implementation of the Simplified SWU mapping to the curve E' isogenous to secp256k1 is given in Appendix F.2.¶
8.8. Suites for BLS12-381
This section defines ciphersuites for groups G1 and G2 of the BLS12-381 elliptic curve [BLS12-381].¶
8.8.1. BLS12-381 G1
BLS12381G1
BLS12381G1
Note that the h_eff values for these suites are chosen for compatibility with the fast cofactor clearing method described by Scott ([WB19], Section 5).¶
An optimized example implementation of the Simplified SWU mapping to the curve E' isogenous to BLS12-381 G1 is given in Appendix F.2.¶
8.8.2. BLS12-381 G2
BLS12381G2
BLS12381G2
Note that the h_eff values for these suites are chosen for compatibility with the fast cofactor clearing method described by Budroni and Pintore ([BP17], Section 4.1) and are summarized in Appendix G.3.¶
An optimized example implementation of the Simplified SWU mapping to the curve E' isogenous to BLS12-381 G2 is given in Appendix F.2.¶
8.9. Defining a New Hash-to-Curve Suite
For elliptic curves not listed elsewhere in Section 8, a new hash-to-curve suite can be defined by the following:¶
8.10. Suite ID Naming Conventions
Suite IDs MUST be constructed as follows:¶
The fields CURVE_ID, HASH_ID, MAP_ID, and ENC_VAR are ASCII-encoded strings of at most 64 characters each. Fields MUST contain only ASCII characters between 0x21 and 0x7E (inclusive), except that underscore (i.e., 0x5F) is not allowed.¶
As indicated above, each field (including the last) is followed by an underscore ("_", ASCII 0x5F). This helps to ensure that Suite IDs are prefix free. Suite IDs MUST include the final underscore and MUST NOT include any characters after the final underscore.¶
Suite ID fields MUST be chosen as follows:¶
9. IANA Considerations
This document has no IANA actions.¶
10. Security Considerations
This section contains additional security considerations about the hash-to-curve mechanisms described in this document.¶
10.1. Properties of Encodings
Each encoding type (Section 3) accepts an arbitrary byte string and maps it to a point on the curve sampled from a distribution that depends on the encoding type. It is important to note that using a nonuniform encoding or directly evaluating one of the mappings of Section 6 produces an output that is easily distinguished from a uniformly random point. Applications that use a nonuniform encoding SHOULD carefully analyze the security implications of nonuniformity. When the required encoding is not clear, applications SHOULD use a uniform encoding.¶
Both encodings given in Section 3 can output the identity element of the group G.
The probability that either encoding function outputs the identity element is
roughly 1/r for a random input, which is negligible for cryptographical
When the hash_to_curve function (Section 3) is instantiated with a
hash_to_field function that is indifferentiabl
10.2. Hashing Passwords
When hashing passwords using any function described in this document, an adversary who learns the output of the hash function (or potentially any intermediate value, e.g., the output of hash_to_field) may be able to carry out a dictionary attack. To mitigate such attacks, it is recommended to first execute a more costly key derivation function (e.g., PBKDF2 [RFC8018], scrypt [RFC7914], or Argon2 [RFC9106]) on the password, then hash the output of that function to the target elliptic curve. For collision resistance, the hash underlying the key derivation function should be chosen according to the guidelines listed in Section 5.3.1.¶
10.3. Constant-Time Requirements
Constant-time implementations of all functions in this document are STRONGLY RECOMMENDED for all uses, to avoid leaking information via side channels. It is especially important to use a constant-time implementation when inputs to an encoding are secret values; in such cases, constant-time implementations are REQUIRED for security against timing attacks (e.g., [VR20]). When constant-time implementations are required, all basic operations and utility functions must be implemented in constant time, as discussed in Section 4. In some applications (e.g., embedded systems), leakage through other side channels (e.g., power or electromagnetic side channels) may be pertinent. Defending against such leakage is outside the scope of this document, because the nature of the leakage and the appropriate defense depend on the application.¶
10.4. encode_to_curve: Output Distribution and Indifferentiability
The encode_to_curve function (Section 3) returns points sampled from a distribution that is statistically far from uniform. This distribution is bounded roughly as follows: first, it includes at least one eighth of the points in G, and second, the probability of points in the distribution varies by at most a factor of four. These bounds hold when encode_to_curve is instantiated with any of the map_to_curve functions in Section 6.¶
The bounds above are derived from several works in the literature. Specifically:¶
Indifferentiabil
10.5. hash_to_field Security
The hash_to_field function, defined in Section 5, is indifferentiabl
We very briefly sketch the indifferentiabi
10.6. expand_message_xmd Security
The expand
For cases (1) and (2), the indifferentiabi
For case (3), i.e., where H is a Merkle-Damgaard hash function, indifferentiabi
The essential difference between the construction discussed in [CDMP05] and
expand
We note that expand
10.7. Domain Separation for expand_message Variants
As discussed in Section 2.2.5, the purpose of domain separation is to ensure that security analyses of cryptographic protocols that query multiple independent random oracles remain valid even if all of these random oracles are instantiated based on one underlying function H.¶
The expand_message variants in this document (Section 5.3) ensure
domain separation by appending a suffix
This section suggests four methods for enforcing domain separation from expand_message variants, explains how each method achieves domain separation, and lists the situations in which each is appropriate. These methods share a high-level structure: the application designer fixes a tag DST_ext distinct from DST_prime and augments calls to H with DST_ext. Each method augments calls to H differently, and each may impose additional requirements on DST_ext.¶
These methods can be used to instantiate multiple domain
10.8. Target Security Levels
Each ciphersuite specifies a target security level (in bits) for the underlying curve. This parameter ensures the corresponding hash_to_field instantiation is conservative and correct. We stress that this parameter is only an upper bound on the security level of the curve and is neither a guarantee nor endorsement of its suitability for a given application. Mathematical and cryptographic advancements may reduce the effective security level for any curve.¶
11. References
11.1. Normative References
- [Err4730]
-
RFC Errata, "Erratum ID 4730", RFC 7748, , <https://
www >..rfc -editor .org /errata /eid4730 - [RFC2119]
-
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10
.17487 , , <https:///RFC2119 www >..rfc -editor .org /info /rfc2119 - [RFC7748]
-
Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10
.17487 , , <https:///RFC7748 www >..rfc -editor .org /info /rfc7748 - [RFC8017]
-
Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2", RFC 8017, DOI 10
.17487 , , <https:///RFC8017 www >..rfc -editor .org /info /rfc8017 - [RFC8174]
-
Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10
.17487 , , <https:///RFC8174 www >..rfc -editor .org /info /rfc8174
11.2. Informative References
- [AFQTZ14]
-
Aranha, D. F., Fouque, P.-A., Qian, C., Tibouchi, M., and J. C. Zapalowicz, "Binary Elligator Squared", In Selected Areas in Cryptography - SAC 2014, pages 20-37, DOI 10
.1007 , , <https:///978 -3 -319 -13051 -4 _2 doi >..org /10 .1007 /978 -3 -319 -13051 -4 _2 - [AR13]
-
Adj, G. and F. Rodríguez
-Henríquez , "Square Root Computation over Even Extension Fields", In IEEE Transactions on Computers. vol 63 issue 11, pages 2829-2841, DOI 10.1109 , , <https:///TC .2013 .145 doi >..org /10 .1109 /TC .2013 .145 - [BBJLP08]
-
Bernstein, D. J., Birkner, P., Joye, M., Lange, T., and C. Peters, "Twisted Edwards Curves", In AFRICACRYPT 2008, pages 389-405, DOI 10
.1007 , , <https:///978 -3 -540 -68164 -9 _26 doi >..org /10 .1007 /978 -3 -540 -68164 -9 _26 - [BCIMRT10]
-
Brier, E., Coron, J.-S., Icart, T., Madore, D., Randriam, H., and M. Tibouchi, "Efficient Indifferentiabl
e , In Advances in Cryptology - CRYPTO 2010, pages 237-254, DOI 10Hashing into Ordinary Elliptic Curves" .1007 , , <https:///978 -3 -642 -14623 -7 _13 doi >..org /10 .1007 /978 -3 -642 -14623 -7 _13 - [BDPV08]
-
Bertoni, G., Daemen, J., Peeters, M., and G. Van Assche, "On the Indifferentiabi
lity , In Advances in Cryptology - EUROCRYPT 2008, pages 181-197, DOI 10of the Sponge Construction" .1007 , , <https:///978 -3 -540 -78967 -3 _11 doi >..org /10 .1007 /978 -3 -540 -78967 -3 _11 - [BF01]
-
Boneh, D. and M. Franklin, "Identity-Based Encryption from the Weil Pairing", In Advances in Cryptology - CRYPTO 2001, pages 213-229, DOI 10
.1007 , , <https:///3 -540 -44647 -8 _13 doi >..org /10 .1007 /3 -540 -44647 -8 _13 - [BHKL13]
-
Bernstein, D. J., Hamburg, M., Krasnova, A., and T. Lange, "Elligator: elliptic-curve points indistinguishab
le , In Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security, pages 967-980, DOI 10from uniform random strings" .1145 , , <https:///2508859 .2516734 doi >..org /10 .1145 /2508859 .2516734 - [BLAKE2X]
-
Aumasson, J.-P., Neves, S., Wilcox-O'Hearn, Z., and C. Winnerlein, "BLAKE2X", , <https://
blake2 >..net /blake2x .pdf - [BLMP19]
-
Bernstein, D. J., Lange, T., Martindale, C., and L. Panny, "Quantum Circuits for the CSIDH: Optimizing Quantum Evaluation of Isogenies", In Advances in Cryptology - EUROCRYPT 2019, pages 409-441, DOI 10
.1007 , , <https:///978 -3 -030 -17656 -3 doi >..org /10 .1007 /978 -3 -030 -17656 -3 _15 - [BLS-SIG]
-
Boneh, D., Gorbunov, S., Wahby, R. S., Wee, H., Wood, C. A., and Z. Zhang, "BLS Signatures", Work in Progress, Internet-Draft, draft
-irtf , , <https://-cfrg -bls -signature -05 datatracker >..ietf .org /doc /html /draft -irtf -cfrg -bls -signature -05 - [BLS01]
-
Boneh, D., Lynn, B., and H. Shacham, "Short Signatures from the Weil Pairing", In Journal of Cryptology, vol 17, pages 297-319, DOI 10
.1007 , , <https:///s00145 -004 -0314 -9 doi >..org /10 .1007 /s00145 -004 -0314 -9 - [BLS03]
-
Barreto, P. S. L. M., Lynn, B., and M. Scott, "Constructing Elliptic Curves with Prescribed Embedding Degrees", In Security in Communication Networks, pages 257-267, DOI 10
.1007 , , <https:///3 -540 -36413 -7 _19 doi >..org /10 .1007 /3 -540 -36413 -7 _19 - [BLS12-381]
-
Bowe, S., "BLS12-381: New zk-SNARK Elliptic Curve Construction", , <https://
electriccoin >..co /blog /new -snark -curve / - [BM92]
-
Bellovin, S. M. and M. Merritt, "Encrypted key exchange: password-based protocols secure against dictionary attacks", In IEEE Symposium on Security and Privacy - Oakland 1992, pages 72-84, DOI 10
.1109 , , <https:///RISP .1992 .213269 doi >..org /10 .1109 /RISP .1992 .213269 - [BMP00]
-
Boyko, V., MacKenzie, P., and S. Patel, "Provably Secure Password
-Authenticated , In Advances in Cryptology - EUROCRYPT 2000, pages 156-171, DOI 10Key Exchange Using Diffie-Hellman" .1007 , , <https:///3 -540 -45539 -6 _12 doi >..org /10 .1007 /3 -540 -45539 -6 _12 - [BN05]
-
Barreto, P. S. L. M. and M. Naehrig, "Pairing
-Friendly , In Selected Areas in Cryptography 2005, pages 319-331, DOI 10Elliptic Curves of Prime Order" .1007 , , <https:///11693383 _22 doi >..org /10 .1007 /11693383 _22 - [BP17]
-
Budroni, A. and F. Pintore, "Efficient hash maps to \mathbb{G}_2 on BLS curves", Cryptology ePrint Archive, Paper 2017/419, , <https://
eprint >..iacr .org /2017 /419 - [BR93]
-
Bellare, M. and P. Rogaway, "Random oracles are practical: a paradigm for designing efficient protocols", In Proceedings of the 1993 ACM Conference on Computer and Communications Security, pages 62-73, DOI 10
.1145 , , <https:///168588 .168596 doi >..org /10 .1145 /168588 .168596 - [C93]
-
Cohen, H., "A Course in Computational Algebraic Number Theory", Springer-Verlag, ISBN 9783642081422, DOI 10
.1007 , , <https:///978 -3 -662 -02945 -9 doi >..org /10 .1007 /978 -3 -662 -02945 -9 - [CDMP05]
-
Coron, J.-S., Dodis, Y., Malinaud, C., and P. Puniya, "Merkle-Damgård Revisited: How to Construct a Hash Function", In Advances in Cryptology -- CRYPTO 2005, pages 430-448, DOI 10
.1007 , , <https:///11535218 _26 doi >..org /10 .1007 /11535218 _26 - [CFADLNV05]
-
Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., and F. Vercauteren, "Handbook of Elliptic and Hyperelliptic Curve Cryptography", Chapman and Hall / CRC, ISBN 9781584885184, , <https://
www >..crcpress .com /9781584885184 - [CK11]
-
Couveignes, J.-M. and J.-G. Kammerer, "The geometry of flex tangents to a cubic curve and its parameterizatio
ns" , In Journal of Symbolic Computation, vol 47 issue 3, pages 266-281, DOI 10.1016 , , <https:///j .jsc .2011 .11 .003 doi >..org /10 .1016 /j .jsc .2011 .11 .003 - [F11]
-
Farashahi, R. R., "Hashing into Hessian Curves", In AFRICACRYPT 2011, pages 278-289, DOI 10
.1007 , , <https:///978 -3 -642 -21969 -6 _17 doi >..org /10 .1007 /978 -3 -642 -21969 -6 _17 - [FFSTV13]
-
Farashahi, R. R., Fouque, P.-A., Shparlinski, I. E., Tibouchi, M., and J. F. Voloch, "Indifferentiabl
e , In Mathematics of Computation. vol 82, pages 491-512, DOI 10deterministic hashing to elliptic and hyperelliptic curves" .1090 , , <https:///S0025 -5718 -2012 -02606 -8 doi >..org /10 .1090 /S0025 -5718 -2012 -02606 -8 - [FIPS180-4]
-
National Institute of Standards and Technology (NIST), "Secure Hash Standard (SHS)", FIPS 180-4, DOI 10
.6028 , , <https:///NIST .FIPS .180 -4 nvlpubs >..nist .gov /nistpubs /FIPS /NIST .FIPS .180 -4 .pdf - [FIPS186-4]
-
National Institute of Standards and Technology (NIST), "Digital Signature Standard (DSS)", FIPS 186-4, DOI 10
.6028 , , <https:///NIST .FIPS .186 -4 nvlpubs >..nist .gov /nistpubs /FIPS /NIST .FIPS .186 -4 .pdf - [FIPS202]
-
National Institute of Standards and Technology (NIST), "SHA-3 Standard: Permutation
-Based , FIPS 202, DOI 10Hash and Extendable -Output Functions" .6028 , , <https:///NIST .FIPS .202 nvlpubs >..nist .gov /nistpubs /FIPS /NIST .FIPS .202 .pdf - [FJT13]
-
Fouque, P.-A., Joux, A., and M. Tibouchi, "Injective Encodings to Elliptic Curves", In ACISP 2013, pages 203-218, DOI 10
.1007 , , <https:///978 -3 -642 -39059 -3 _14 doi >..org /10 .1007 /978 -3 -642 -39059 -3 _14 - [FKR11]
-
Fuentes
-Castañeda, , Knapp, E., and F. RodriguezL. -Henriquez , "Faster Hashing to G2", In Selected Areas in Cryptography, pages 412-430, DOI 10.1007 , , <https:///978 -3 -642 -28496 -0 _25 doi >..org /10 .1007 /978 -3 -642 -28496 -0 _25 - [FSV09]
-
Farashahi, R. R., Shparlinski, I. E., and J. F. Voloch, "On hashing into elliptic curves", In Journal of Mathematical Cryptology, vol 3 no 4, pages 353-360, DOI 10
.1515 , , <https:///JMC .2009 .022 doi >..org /10 .1515 /JMC .2009 .022 - [FT10]
-
Fouque, P.-A. and M. Tibouchi, "Estimating the Size of the Image of Deterministic Hash Functions to Elliptic Curves", In Progress in Cryptology - LATINCRYPT 2010, pages 81-91, DOI 10
.1007 , , <https:///978 -3 -642 -14712 -8 _5 doi >..org /10 .1007 /978 -3 -642 -14712 -8 _5 - [FT12]
-
Fouque, P.-A. and M. Tibouchi, "Indifferentiabl
e , In Progress in Cryptology - LATINCRYPT 2012, pages 1-17, DOI 10Hashing to Barreto --Naehrig Curves" .1007 , , <https:///978 -3 -642 -33481 -8 _1 doi >..org /10 .1007 /978 -3 -642 -33481 -8 _1 - [H20]
-
Hamburg, M., "Indifferentiabl
e , Cryptology ePrint Archive, Paper 2020/1513, , <https://hashing from Elligator 2" eprint >..iacr .org /2020 /1513 - [hash2curve
-repo] -
"Hashing to Elliptic Curves", commit 664b135, , <https://
github >..com /cfrg /draft -irtf -cfrg -hash -to -curve - [Icart09]
-
Icart, T., "How to Hash into Elliptic Curves", In Advances in Cryptology - CRYPTO 2009, pages 303-316, DOI 10
.1007 , , <https:///978 -3 -642 -03356 -8 _18 doi >..org /10 .1007 /978 -3 -642 -03356 -8 _18 - [J96]
-
Jablon, D. P., "Strong password-only authenticated key exchange", In SIGCOMM Computer Communication Review, vol 26 issue 5, pages 5-26, DOI 10
.1145 , , <https:///242896 .242897 doi >..org /10 .1145 /242896 .242897 - [jubjub-fq]
-
"zkcrypto/jubjub - fq.rs", , <https://
github >..com /zkcrypto /jubjub /pull /18 - [KLR10]
-
Kammerer, J.-G., Lercier, R., and G. Renault, "Encoding Points on Hyperelliptic Curves over Finite Fields in Deterministic Polynomial Time", In Pairing-Based Cryptography - Pairing 2010, pages 278-297, DOI 10
.1007 , , <https:///978 -3 -642 -17455 -1 _18 doi >..org /10 .1007 /978 -3 -642 -17455 -1 _18 - [L13]
-
Langley, A., "Implementing Elligator for Curve25519", , <https://
www >..imperialviolet .org /2013 /12 /25 /elligator .html - [LBB19]
-
Lipp, B., Blanchet, B., and K. Bhargavan, "A Mechanised Cryptographic Proof of the WireGuard Virtual Private Network Protocol", In INRIA Research Report 9269, , <https://
hal >..inria .fr /hal -02100345 / - [MOV96]
-
Menezes, A. J., van Oorschot, P. C., and S. A. Vanstone, "Handbook of Applied Cryptography", CRC Press, ISBN 9780849385230, , <http://
cacr >..uwaterloo .ca /hac / - [MRH04]
-
Maurer, U., Renner, R., and C. Holenstein, "Indifferentiabi
lity, , In TCC 2004: Theory of Cryptography, pages 21-39, DOI 10Impossibility Results on Reductions, and Applications to the Random Oracle Methodology" .1007 , , <https:///978 -3 -540 -24638 -1 _2 doi >..org /10 .1007 /978 -3 -540 -24638 -1 _2 - [MRV99]
-
Micali, S., Rabin, M., and S. Vadhan, "Verifiable random functions", 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), pages 120-130, DOI 10
.1109 , , <https:///SFFCS .1999 .814584 doi >..org /10 .1109 /SFFCS .1999 .814584 - [MT98]
-
Matsumoto, M. and T. Nishimura, "Mersenne twister: A 623
-dimensionally , In ACM Transactions on Modeling and Computer Simulation (TOMACS), vol 8 issue 1, pages 3-30, DOI 10equidistributed uniform pseudo-random number generator" .1145 , , <https:///272991 .272995 doi >..org /10 .1145 /272991 .272995 - [NR97]
-
Naor, M. and O. Reingold, "Number
-theoretic , In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 458-467, DOI 10constructions of efficient pseudo-random functions" .1109 , , <https:///SFCS .1997 .646134 doi >..org /10 .1109 /SFCS .1997 .646134 - [OPRFs]
-
Davidson, A., Faz-Hernandez, A., Sullivan, N., and C. A. Wood, "Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups", Work in Progress, Internet-Draft, draft
-irtf , , <https://-cfrg -voprf -21 datatracker >..ietf .org /doc /html /draft -irtf -cfrg -voprf -21 - [p1363.2]
-
IEEE, "IEEE Standard Specification for Password-Based Public-Key Cryptography Techniques", IEEE 1363.2-2008, , <https://
standards >..ieee .org /standard /1363 _2 -2008 .html - [p1363a]
-
IEEE, "IEEE Standard Specifications for Public-Key Cryptography - Amendment 1: Additional Techniques", IEEE 1363a-2004, , <https://
standards >..ieee .org /standard /1363a -2004 .html - [P20]
-
Pornin, T., "Efficient Elliptic Curve Operations On Microcontroller
s , Cryptology ePrint Archive, Paper 2020/009, , <https://With Finite Field Extensions" eprint >..iacr .org /2020 /009 - [RCB16]
-
Renes, J., Costello, C., and L. Batina, "Complete Addition Formulas for Prime Order Elliptic Curves", In Advances in Cryptology - EUROCRYPT 2016, pages 403-428, DOI 10
.1007 , , <https:///978 -3 -662 -49890 -3 _16 doi >..org /10 .1007 /978 -3 -662 -49890 -3 _16 - [RFC2104]
-
Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-Hashing for Message Authentication", RFC 2104, DOI 10
.17487 , , <https:///RFC2104 www >..rfc -editor .org /info /rfc2104 - [RFC5869]
-
Krawczyk, H. and P. Eronen, "HMAC-based Extract
-and , RFC 5869, DOI 10-Expand Key Derivation Function (HKDF)" .17487 , , <https:///RFC5869 www >..rfc -editor .org /info /rfc5869 - [RFC7693]
-
Saarinen, M., Ed. and J. Aumasson, "The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC)", RFC 7693, DOI 10
.17487 , , <https:///RFC7693 www >..rfc -editor .org /info /rfc7693 - [RFC7914]
-
Percival, C. and S. Josefsson, "The scrypt Password-Based Key Derivation Function", RFC 7914, DOI 10
.17487 , , <https:///RFC7914 www >..rfc -editor .org /info /rfc7914 - [RFC8018]
-
Moriarty, K., Ed., Kaliski, B., and A. Rusch, "PKCS #5: Password-Based Cryptography Specification Version 2.1", RFC 8018, DOI 10
.17487 , , <https:///RFC8018 www >..rfc -editor .org /info /rfc8018 - [RFC9106]
-
Biryukov, A., Dinu, D., Khovratovich, D., and S. Josefsson, "Argon2 Memory-Hard Function for Password Hashing and Proof-of-Work Applications", RFC 9106, DOI 10
.17487 , , <https:///RFC9106 www >..rfc -editor .org /info /rfc9106 - [ristretto255
-decaf448] -
de Valence, H., Grigg, J., Hamburg, M., Lovecruft, I., Tankersley, G., and F. Valsorda, "The ristretto255 and decaf448 Groups", Work in Progress, Internet-Draft, draft
-irtf , , <https://-cfrg -ristretto255 -decaf448 -07 datatracker >..ietf .org /doc /html /draft -irtf -cfrg -ristretto255 -decaf448 -07 - [RSS11]
-
Ristenpart, T., Shacham, H., and T. Shrimpton, "Careful with Composition: Limitations of the Indifferentiabi
lity , In Advances in Cryptology - EUROCRYPT 2011, pages 487-506, DOI 10Framework" .1007 , , <https:///978 -3 -642 -20465 -4 _27 doi >..org /10 .1007 /978 -3 -642 -20465 -4 _27 - [S05]
-
Skałba, M., "Points on elliptic curves over finite fields", In Acta Arithmetica, vol 117 no 3, pages 293-301, DOI 10
.4064 , , <https:///aa117 -3 -7 doi >..org /10 .4064 /aa117 -3 -7 - [S85]
-
Schoof, R., "Elliptic curves over finite fields and the computation of square roots mod p", In Mathematics of Computation, vol 44 issue 170, pages 483-494, DOI 10
.1090 , , <https:///S0025 -5718 -1985 -0777280 -6 doi >..org /10 .1090 /S0025 -5718 -1985 -0777280 -6 - [SAGE]
-
The Sage Developers, "SageMath, the Sage Mathematics Software System", <https://
www >..sagemath .org - [SBCDK09]
-
Scott, M., Benger, N., Charlemagne, M., Dominguez Perez, L. J., and E. J. Kachisa, "Fast Hashing to G2 on Pairing
-Friendly , In Pairing-Based Cryptography - Pairing 2009, pages 102-113, DOI 10Curves" .1007 , , <https:///978 -3 -642 -03298 -1 _8 doi >..org /10 .1007 /978 -3 -642 -03298 -1 _8 - [SEC1]
-
Standards for Efficient Cryptography Group (SECG), "SEC 1: Elliptic Curve Cryptography", , <http://
www >..secg .org /sec1 -v2 .pdf - [SEC2]
-
Standards for Efficient Cryptography Group (SECG), "SEC 2: Recommended Elliptic Curve Domain Parameters", , <http://
www >..secg .org /sec2 -v2 .pdf - [SS04]
-
Schinzel, A. and M. Skałba, "On equations y^2 = x^n + k in a finite field", In Bulletin Polish Academy of Sciences. Mathematics, vol 52 no 3, pages 223-226, DOI 10
.4064 , , <https:///ba52 -3 -1 doi >..org /10 .4064 /ba52 -3 -1 - [SW06]
-
Shallue, A. and C. E. van de Woestijne, "Construction of Rational Points on Elliptic Curves over Finite Fields", In Algorithmic Number Theory - ANTS 2006, pages 510-524, DOI 10
.1007 , , <https:///11792086 _36 doi >..org /10 .1007 /11792086 _36 - [T14]
-
Tibouchi, M., "Elligator Squared: Uniform Points on Elliptic Curves of Prime Order as Uniform Random Strings", In Financial Cryptography and Data Security - FC 2014, pages 139-156, DOI 10
.1007 , , <https:///978 -3 -662 -45472 -5 _10 doi >..org /10 .1007 /978 -3 -662 -45472 -5 _10 - [TK17]
-
Tibouchi, M. and T. Kim, "Improved elliptic curve hashing and point representation", In Designs, Codes, and Cryptography, vol 82, pages 161-177, DOI 10
.1007 , , <https:///s10623 -016 -0288 -2 doi >..org /10 .1007 /s10623 -016 -0288 -2 - [U07]
-
Ulas, M., "Rational Points on Certain Hyperelliptic Curves over Finite Fields", In Bulletin Polish Academy of Science. Mathematics, vol 55 no 2, pages 97-104, DOI 10
.4064 , , <https:///ba55 -2 -1 doi >..org /10 .4064 /ba55 -2 -1 - [VR20]
-
Vanhoef, M. and E. Ronen, "Dragonblood: Analyzing the Dragonfly Handshake of WPA3 and EAP-pwd", In IEEE Symposium on Security & Privacy (SP), , <https://
eprint >..iacr .org /2019 /383 - [VRF]
-
Goldberg, S., Reyzin, L., Papadopoulos, D., and J. Včelák, "Verifiable Random Functions (VRFs)", Work in Progress, Internet-Draft, draft
-irtf , , <https://-cfrg -vrf -15 datatracker >..ietf .org /doc /html /draft -irtf -cfrg -vrf -15 - [W08]
-
Washington, L. C., "Elliptic Curves: Number Theory and Cryptography, Second Edition", Chapman and Hall / CRC, ISBN 9781420071467, , <https://
www >..crcpress .com /9781420071467 - [W19]
-
Wahby, R. S., "An explicit, generic parameterizatio
n , commit e2a625f, , <https://for the Shallue--van de Woestijne map" github >..com /cfrg /draft -irtf -cfrg -hash -to -curve /blob /draft -irtf -cfrg -hash -to -curve -14 /doc /svdw _params .pdf - [WB19]
-
Wahby, R. S. and D. Boneh, "Fast and simple constant-time hashing to the BLS12-381 elliptic curve", In IACR Transactions on Cryptographic Hardware and Embedded Systems, vol 2019 issue 4, Cryptology ePrint Archive, Paper 2019/403, DOI 10
.13154 , , <https:///tches .v2019 .i4 .154 -179 eprint >..iacr .org /2019 /403
Appendix B. Hashing to ristretto255
ristretto255 [ristretto255
The ristretto255 API defines a one-way map ([ristretto255
The hash
Since hash
For example, if expand_message is expand
Appendix C. Hashing to decaf448
Similar to ristretto255, decaf448 [ristretto255
The decaf448 API defines a one-way map ([ristretto255
The hash
Since hash
For example, if expand_message is expand
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:¶
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¶
is birationally equivalent to the Montgomery curve¶
which has the form required by the Elligator 2 mapping of Section 6.7.1. The coefficients of the Montgomery curve are¶
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¶
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.¶
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¶
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¶
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¶
to the point (x, y) on the equivalent Weierstrass curve¶
is given by¶
The inverse map, from the point (x, y) to the point (s, t), is given by¶
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.¶
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:¶
The constants used to compute x_num are as follows:¶
The constants used to compute x_den are as follows:¶
The constants used to compute y_num are as follows:¶
The constants used to compute y_den are as follows:¶
E.2. 11-Isogeny Map for BLS12-381 G1
The 11-isogeny map from (x', y') on E' to (x, y) on E is given by the following rational functions:¶
The constants used to compute x_num are as follows:¶
The constants used to compute x_den are as follows:¶
The constants used to compute y_num are as follows:¶
The constants used to compute y_den are as follows:¶
E.3. 3-Isogeny Map for BLS12-381 G2
The 3-isogeny map from (x', y') on E' to (x, y) on E is given by the following rational functions:¶
The constants used to compute x_num are as follows:¶
The constants used to compute x_den are as follows:¶
The constants used to compute y_num are as follows:¶
The constants used to compute y_den are as follows:¶
Appendix F. Straight-Line Implementations of Deterministic Mappings
This section gives straight-line implementations of the mappings of Section 6. These implementations are generic, i.e., they are defined for any curve and field. Appendix G gives further implementations that are optimized for specific classes of curves and fields.¶
F.1. Shallue-van de Woestijne Method
This section gives a straight-line implementation of the Shallue-van de Woestijne method for any Weierstrass curve of the form given in Section 6.6. See Section 6.6.1 for information on the constants used in this mapping.¶
Note that the constant c3 below MUST be chosen such that sgn0(c3) = 0. In other words, if the square-root computation returns a value cx such that sgn0(cx) = 1, set c3 = -cx; otherwise, set c3 = cx.¶
F.2. Simplified SWU Method
This section gives a straight-line implementation of the Simplified SWU method for any Weierstrass curve of the form given in Section 6.6. See Section 6.6.2 for information on the constants used in this mapping.¶
This optimized, straight-line procedure applies to any base field. The sqrt_ratio subroutine is defined in Appendix F.2.1.¶
F.2.1. sqrt_ratio Subroutine
This section defines three variants of the sqrt_ratio subroutine used by the above procedure. The first variant can be used with any field; the others are optimized versions for specific fields.¶
The routines given in this section depend on the constant Z from the Simplified SWU map.
For correctness, sqrt_ratio and map
F.3. Elligator 2 Method
This section gives a straight-line implementation of the Elligator 2 method for any Montgomery curve of the form given in Section 6.7. See Section 6.7.1 for information on the constants used in this mapping.¶
Appendix G.2 gives optimized straight-line procedures that apply to specific classes of curves and base fields, including curve25519 and curve448 [RFC7748].¶
Appendix G. Curve-Specific Optimized Sample Code
This section gives sample implementations optimized for some of the elliptic curves listed in Section 8. Sample Sage code [SAGE] for each algorithm can also be found in [hash2curve-repo].¶
G.1. Interface and Projective Coordinate Systems
The sample code in this section uses a different interface than the mappings of Section 6. Specifically, each mapping function in this section has the following signature:¶
The resulting affine point (x, y) is given by (xn / xd, yn / yd).¶
The reason for this modified interface is that it enables further optimizations when working with points in a projective coordinate system. This is desirable, for example, when the resulting point will be immediately multiplied by a scalar, since most scalar multiplication algorithms operate on projective points.¶
Projective coordinates are also useful when implementing random-oracle encodings (Section 3). One reason is that, in general, point addition is faster using projective coordinates. Another reason is that, for Weierstrass curves, projective coordinates allow using complete addition formulas [RCB16]. This is especially convenient when implementing a constant-time encoding, because it eliminates the need for a special case when Q0 == Q1, which incomplete addition formulas usually do not handle.¶
The following are two commonly used projective coordinate systems and the corresponding conversions:¶
G.2. Elligator 2
G.2.1. curve25519 (q = 5 (mod 8), K = 1)
The following is a straight-line implementation of Elligator 2 for curve25519 [RFC7748] as specified in Section 8.5.¶
This implementation can also be used for any Montgomery curve with K = 1 over GF(q) where q = 5 (mod 8).¶
G.2.2. edwards25519
The following is a straight-line implementation of Elligator 2
for edwards25519 [RFC7748] as specified in Section 8.5.
The subroutine map
Note that the sign of the constant c1 below is chosen as specified in Section 6.8.1, i.e., applying the rational map to the edwards25519 base point yields the curve25519 base point (see erratum [Err4730]).¶
G.2.3. curve448 (q = 3 (mod 4), K = 1)
The following is a straight-line implementation of Elligator 2 for curve448 [RFC7748] as specified in Section 8.6.¶
This implementation can also be used for any Montgomery curve with K = 1 over GF(q) where q = 3 (mod 4).¶
G.2.4. edwards448
The following is a straight-line implementation of Elligator 2
for edwards448 [RFC7748] as specified in Section 8.6.
The subroutine map
G.2.5. Montgomery Curves with q = 3 (mod 4)
The following is a straight-line implementation of Elligator 2 that applies to any Montgomery curve defined over GF(q) where q = 3 (mod 4).¶
For curves where K = 1, the implementation given in Appendix G.2.3 gives identical results with slightly reduced cost.¶
G.2.6. Montgomery Curves with q = 5 (mod 8)
The following is a straight-line implementation of Elligator 2 that applies to any Montgomery curve defined over GF(q) where q = 5 (mod 8).¶
For curves where K = 1, the implementation given in Appendix G.2.1 gives identical results with slightly reduced cost.¶
G.3. Cofactor Clearing for BLS12-381 G2
The curve BLS12-381, whose parameters are defined in Section 8.8.2, admits an efficiently computable endomorphism, psi, that can be used to speed up cofactor clearing for G2 [SBCDK09] [FKR11] [BP17] (see also Section 7). This section implements the endomorphism psi and a fast cofactor clearing method described by Budroni and Pintore [BP17].¶
The functions in this section operate on points whose coordinates are represented as ratios, i.e., (xn, xd, yn, yd) corresponds to the point (xn / xd, yn / yd); see Appendix G.1 for further discussion of projective coordinates. When points are represented in affine coordinates, one can simply ignore the denominators (xd == 1 and yd == 1).¶
The following function computes the Frobenius endomorphism for an element of F = GF(p^2) with basis (1, I), where I^2 + 1 == 0 in F. (This is the base field of the elliptic curve E defined in Section 8.8.2.)¶
The following function computes the endomorphism psi for points on the elliptic curve E defined in Section 8.8.2.¶
The following function efficiently computes psi(psi(P)).¶
The following function maps any point on the elliptic curve E (Section 8.8.2) into the prime-order subgroup G2. This function returns a point equal to h_eff * P, where h_eff is the parameter given in Section 8.8.2.¶
Appendix H. Scripts for Parameter Generation
This section gives Sage scripts [SAGE] used to generate parameters for the mappings of Section 6.¶
H.1. Finding Z for the Shallue-van de Woestijne Map
The below function outputs an appropriate Z for the Shallue-van de Woestijne map (Section 6.6.1).¶
H.2. Finding Z for Simplified SWU
The below function outputs an appropriate Z for the Simplified SWU map (Section 6.6.2).¶
H.3. Finding Z for Elligator 2
The below function outputs an appropriate Z for the Elligator 2 map (Section 6.7.1).¶
Appendix I. sqrt and is_square Functions
This section defines special-purpose sqrt functions for the three most common cases, q = 3 (mod 4), q = 5 (mod 8), and q = 9 (mod 16), plus a generic constant-time algorithm that works for any prime modulus.¶
In addition, it gives an optimized is_square method for GF(p^2).¶
I.4. Constant-Time Tonelli-Shanks Algorithm
This algorithm is a constant-time version of the classic Tonelli-Shanks algorithm ([C93], Algorithm 1.5.1) due to Sean Bowe, Jack Grigg, and Eirik Ogilvie-Wigley [jubjub-fq], adapted and optimized by Michael Scott.¶
This algorithm applies to GF(p) for any p. Note, however, that the special-purpose algorithms given in the prior sections are faster, when they apply.¶
I.5. is_square for F = GF(p^2)
The following is_square method applies to any field F = GF(p^2) with basis (1, I) represented as described in Section 2.1, i.e., an element x = (x_1, x_2) = x_1 + x_2 * I.¶
Other optimizations of this type are possible in other extension fields; see, for example, [AR13] for more information.¶
Appendix J. Suite Test Vectors
This section gives test vectors for each suite defined in Section 8. The test vectors in this section were generated using code that is available from [hash2curve-repo].¶
Each test vector in this section lists values computed by the appropriate encoding function, with variable names defined as in Section 3. For example, for a suite whose encoding type is random oracle, the test vector gives the value for msg, u, Q0, Q1, and the output point P.¶
Appendix K. Expand Test Vectors
This section gives test vectors for expand_message variants specified in Section 5.3. The test vectors in this section were generated using code that is available from [hash2curve-repo].¶
Each test vector in this section lists the expand_message name, hash function, and DST,
along with a series of tuples of the function inputs (msg and len_in_bytes),
output
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.¶