Skip to main content

8. Suites for Hashing

  1. 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:

  • Suite ID, a short name used to refer to a given suite. Section 8.10 discusses the naming conventions for Suite IDs.

  • encoding type, either uniform (hash_to_curve) or nonuniform (encode_to_curve). See Section 3 for definitions of these encoding types.

  • E, the target elliptic curve over a field F.

  • p, the characteristic of the field F.

  • m, the extension degree of the field F. If m > 1, the suite MUST also specify the polynomial basis used to represent extension field elements.

  • k, the target security level of the suite in bits. (See Section 10.8 for discussion.)

  • L, the length parameter for hash_to_field (Section 5).

  • expand_message, one of the variants specified in Section 5.3 plus any parameters required for the specified variant (for example, H, the underlying hash function).

  • f, a mapping function from Section 6.

  • h_eff, the scalar parameter for clear_cofactor (Section 7).

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.

  +==============+===================================+=========+
  | E            | Suites                            | Section |
  +==============+===================================+=========+
  | NIST P-256   | P256_XMD:SHA-256_SSWU_RO_         | 8.2     |
  |              | P256_XMD:SHA-256_SSWU_NU_         |         |
  +--------------+-----------------------------------+---------+
  | NIST P-384   | P384_XMD:SHA-384_SSWU_RO_         | 8.3     |
  |              | P384_XMD:SHA-384_SSWU_NU_         |         |
  +--------------+-----------------------------------+---------+
  | NIST P-521   | P521_XMD:SHA-512_SSWU_RO_         | 8.4     |
  |              | P521_XMD:SHA-512_SSWU_NU_         |         |
  +--------------+-----------------------------------+---------+
  | curve25519   | curve25519_XMD:SHA-512_ELL2_RO_   | 8.5     |
  |              | curve25519_XMD:SHA-512_ELL2_NU_   |         |
  +--------------+-----------------------------------+---------+
  | edwards25519 | edwards25519_XMD:SHA-512_ELL2_RO_ | 8.5     |
  |              | edwards25519_XMD:SHA-512_ELL2_NU_ |         |
  +--------------+-----------------------------------+---------+
  | curve448     | curve448_XOF:SHAKE256_ELL2_RO_    | 8.6     |
  |              | curve448_XOF:SHAKE256_ELL2_NU_    |         |
  +--------------+-----------------------------------+---------+
  | edwards448   | edwards448_XOF:SHAKE256_ELL2_RO_  | 8.6     |
  |              | edwards448_XOF:SHAKE256_ELL2_NU_  |         |
  +--------------+-----------------------------------+---------+
  | secp256k1    | secp256k1_XMD:SHA-256_SSWU_RO_    | 8.7     |
  |              | secp256k1_XMD:SHA-256_SSWU_NU_    |         |
  +--------------+-----------------------------------+---------+
  | BLS12-381 G1 | BLS12381G1_XMD:SHA-256_SSWU_RO_   | 8.8     |
  |              | BLS12381G1_XMD:SHA-256_SSWU_NU_   |         |
  +--------------+-----------------------------------+---------+
  | BLS12-381 G2 | BLS12381G2_XMD:SHA-256_SSWU_RO_   | 8.8     |
  |              | BLS12381G2_XMD:SHA-256_SSWU_NU_   |         |
  +--------------+-----------------------------------+---------+

         Table 2: Suites for hashing to elliptic curves.

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.

  1. Base field arithmetic operations for the target elliptic curve, e.g., addition, multiplication, and square root.

  2. Elliptic curve point operations for the target curve, e.g., point addition and scalar multiplication.

  3. The hash_to_field function; see Section 5. This includes the expand_message variant (Section 5.3) and any constituent hash function or XOF.

  4. The suite-specified mapping function; see the corresponding subsection of Section 6.

  5. A cofactor clearing function; see Section 7. This may be implemented as scalar multiplication by h_eff or as a faster equivalent method.

  6. The desired encoding function; see Section 3. This is either hash_to_curve or encode_to_curve.

8.2. Suites for NIST P-256

This section defines ciphersuites for the NIST P-256 elliptic curve [FIPS186-4].

P256_XMD:SHA-256_SSWU_RO_ is defined as follows:

  • encoding type: hash_to_curve (Section 3)

  • E: y^2 = x^3 + A * x + B, where

    • A = -3

    • B = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e2 7d2604b

  • p: 2^256 - 2^224 + 2^192 + 2^96 - 1

  • m: 1

  • k: 128

  • expand_message: expand_message_xmd (Section 5.3.1)

  • H: SHA-256

  • L: 48

  • f: Simplified SWU method (Section 6.6.2)

  • Z: -10

  • h_eff: 1

P256_XMD:SHA-256_SSWU_NU_ is identical to P256_XMD:SHA-256_SSWU_RO_, except that the encoding type is encode_to_curve (Section 3).

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_XMD:SHA-384_SSWU_RO_ is defined as follows:

  • encoding type: hash_to_curve (Section 3)

  • E: y^2 = x^3 + A * x + B, where

    • A = -3

    • B = 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5 013875ac656398d8a2ed19d2a85c8edd3ec2aef

  • p: 2^384 - 2^128 - 2^96 + 2^32 - 1

  • m: 1

  • k: 192

  • expand_message: expand_message_xmd (Section 5.3.1)

  • H: SHA-384

  • L: 72

  • f: Simplified SWU method (Section 6.6.2)

  • Z: -12

  • h_eff: 1

P384_XMD:SHA-384_SSWU_NU_ is identical to P384_XMD:SHA-384_SSWU_RO_, except that the encoding type is encode_to_curve (Section 3).

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_XMD:SHA-512_SSWU_RO_ is defined as follows:

  • encoding type: hash_to_curve (Section 3)

  • E: y^2 = x^3 + A * x + B, where

    • A = -3

    • B = 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b4899 18ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451f d46b503f00

  • p: 2^521 - 1

  • m: 1

  • k: 256

  • expand_message: expand_message_xmd (Section 5.3.1)

  • H: SHA-512

  • L: 98

  • f: Simplified SWU method (Section 6.6.2)

  • Z: -4

  • h_eff: 1

P521_XMD:SHA-512_SSWU_NU_ is identical to P521_XMD:SHA-512_SSWU_RO_, except that the encoding type is encode_to_curve (Section 3).

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-decaf448]. See Appendix B for information on how to hash to that group.

curve25519_XMD:SHA-512_ELL2_RO_ is defined as follows:

  • encoding type: hash_to_curve (Section 3)

  • E: K * t^2 = s^3 + J * s^2 + s, where

    • J = 486662

    • K = 1

  • p: 2^255 - 19

  • m: 1

  • k: 128

  • expand_message: expand_message_xmd (Section 5.3.1)

  • H: SHA-512

  • L: 48

  • f: Elligator 2 method (Section 6.7.1)

  • Z: 2

  • h_eff: 8

edwards25519_XMD:SHA-512_ELL2_RO_ is identical to curve25519_XMD:SHA- 512_ELL2_RO_, except for the following parameters:

  • E: a * v^2 + w^2 = 1 + d * v^2 * w^2, where

    • a = -1

    • d = 0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca1 35978a3

  • f: Twisted Edwards Elligator 2 method (Section 6.8.2)

  • M: curve25519, defined in [RFC7748], Section 4.1

  • rational_map: the birational maps defined in [RFC7748], Section 4.1

curve25519_XMD:SHA-512_ELL2_NU_ is identical to curve25519_XMD:SHA- 512_ELL2_RO_, except that the encoding type is encode_to_curve (Section 3).

edwards25519_XMD:SHA-512_ELL2_NU_ is identical to edwards25519_XMD:SHA-512_ELL2_RO_, except that the encoding type is encode_to_curve (Section 3).

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-decaf448]. See Appendix C for information on how to hash to that group.

curve448_XOF:SHAKE256_ELL2_RO_ is defined as follows:

  • encoding type: hash_to_curve (Section 3)

  • E: K * t^2 = s^3 + J * s^2 + s, where

    • J = 156326

    • K = 1

  • p: 2^448 - 2^224 - 1

  • m: 1

  • k: 224

  • expand_message: expand_message_xof (Section 5.3.2)

  • H: SHAKE256

  • L: 84

  • f: Elligator 2 method (Section 6.7.1)

  • Z: -1

  • h_eff: 4

edwards448_XOF:SHAKE256_ELL2_RO_ is identical to curve448_XOF:SHAKE256_ELL2_RO_, except for the following parameters:

  • E: a * v^2 + w^2 = 1 + d * v^2 * w^2, where

    • a = 1

    • d = -39081

  • f: Twisted Edwards Elligator 2 method (Section 6.8.2)

  • M: curve448, defined in [RFC7748], Section 4.2

  • rational_map: the 4-isogeny map defined in [RFC7748], Section 4.2

curve448_XOF:SHAKE256_ELL2_NU_ is identical to curve448_XOF:SHAKE256_ELL2_RO_, except that the encoding type is encode_to_curve (Section 3).

edwards448_XOF:SHAKE256_ELL2_NU_ is identical to edwards448_XOF:SHAKE256_ELL2_RO_, except that the encoding type is encode_to_curve (Section 3).

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_XMD:SHA-256_SSWU_RO_ is defined as follows:

  • encoding type: hash_to_curve (Section 3)

  • E: y^2 = x^3 + 7

  • p: 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1

  • m: 1

  • k: 128

  • expand_message: expand_message_xmd (Section 5.3.1)

  • H: SHA-256

  • L: 48

  • f: Simplified SWU for AB == 0 (Section 6.6.3)

  • Z: -11

  • E': y'^2 = x'^3 + A' * x' + B', where

    • A': 0x3f8731abdd661adca08a5558f0f5d272e953d363cb6f0e5d405447c01 a444533

    • B': 1771

  • iso_map: the 3-isogeny map from E' to E given in Appendix E.1

  • h_eff: 1

secp256k1_XMD:SHA-256_SSWU_NU_ is identical to secp256k1_XMD:SHA- 256_SSWU_RO_, except that the encoding type is encode_to_curve (Section 3).

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_XMD:SHA-256_SSWU_RO_ is defined as follows:

  • encoding type: hash_to_curve (Section 3)

  • E: y^2 = x^3 + 4

  • p: 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f 6241eabfffeb153ffffb9feffffffffaaab

  • m: 1

  • k: 128

  • expand_message: expand_message_xmd (Section 5.3.1)

  • H: SHA-256

  • L: 64

  • f: Simplified SWU for AB == 0 (Section 6.6.3)

  • Z: 11

  • E': y'^2 = x'^3 + A' * x' + B', where

    • A' = 0x144698a3b8e9433d693a02c96d4982b0ea985383ee66a8d8e8981aef d881ac98936f8da0e0f97f5cf428082d584c1d

    • B' = 0x12e2908d11688030018b12e8753eee3b2016c1f0f24f4070a0b9c14f cef35ef55a23215a316ceaa5d1cc48e98e172be0

  • iso_map: the 11-isogeny map from E' to E given in Appendix E.2

  • h_eff: 0xd201000000010001

BLS12381G1_XMD:SHA-256_SSWU_NU_ is identical to BLS12381G1_XMD:SHA- 256_SSWU_RO_, except that the encoding type is encode_to_curve (Section 3).

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_XMD:SHA-256_SSWU_RO_ is defined as follows:

  • encoding type: hash_to_curve (Section 3)

  • E: y^2 = x^3 + 4 * (1 + I)

  • base field F is GF(p^m), where

    • p: 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6 b0f6241eabfffeb153ffffb9feffffffffaaab

    • m: 2

    • (1, I) is the basis for F, where I^2 + 1 == 0 in F

  • k: 128

  • expand_message: expand_message_xmd (Section 5.3.1)

  • H: SHA-256

  • L: 64

  • f: Simplified SWU for AB == 0 (Section 6.6.3)

  • Z: -(2 + I)

  • E': y'^2 = x'^3 + A' * x' + B', where

    • A' = 240 * I

    • B' = 1012 * (1 + I)

  • iso_map: the isogeny map from E' to E given in Appendix E.3

  • h_eff: 0xbc69f08f2ee75b3584c6a0ea91b352888e2a8e9145ad7689986ff0315 08ffe1329c2f178731db956d82bf015d1212b02ec0ec69d7477c1ae954cbc06689 f6a359894c0adebbf6b4e8020005aaa95551

BLS12381G2_XMD:SHA-256_SSWU_NU_ is identical to BLS12381G2_XMD:SHA- 256_SSWU_RO_, except that the encoding type is encode_to_curve (Section 3).

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:

  1. E, F, p, and m are determined by the elliptic curve and its base field.

  2. k is an upper bound on the target security level of the suite (Section 10.8). A reasonable choice of k is ceil(log2(r) / 2), where r is the order of the subgroup G of the curve E (Section 2.1).

  3. Choose encoding type, either hash_to_curve or encode_to_curve (Section 3).

  4. Compute L as described in Section 5.

  5. Choose an expand_message variant from Section 5.3 plus any underlying cryptographic primitives (e.g., a hash function H).

  6. Choose a mapping following the guidelines in Section 6.1, and select any required parameters for that mapping.

  7. Choose h_eff to be either the cofactor of E or, if a fast cofactor clearing method is to be used, a value appropriate to that method as discussed in Section 7.

  8. Construct a Suite ID following the guidelines in Section 8.10.

8.10. Suite ID Naming Conventions

Suite IDs MUST be constructed as follows:

CURVE_ID || "" || HASH_ID || "" || MAP_ID || "" || ENC_VAR || ""

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:

  • CURVE_ID: a human-readable representation of the target elliptic curve.

  • HASH_ID: a human-readable representation of the expand_message function and any underlying hash primitives used in hash_to_field (Section 5). This field MUST be constructed as follows:

    EXP_TAG || ":" || HASH_NAME

    EXP_TAG indicates the expand_message variant:

    • "XMD" for expand_message_xmd (Section 5.3.1).

    • "XOF" for expand_message_xof (Section 5.3.2).

    HASH_NAME is a human-readable name for the underlying hash primitive. As examples:

    1. For expand_message_xof (Section 5.3.2) with SHAKE128, HASH_ID is "XOF:SHAKE128".

    2. For expand_message_xmd (Section 5.3.1) with SHA3-256, HASH_ID is "XMD:SHA3-256".

    Suites that use an alternative hash_to_field function that meets the requirements in Section 5.1 MUST indicate this by appending a tag identifying that function to the HASH_ID field, separated by a colon (":", ASCII 0x3A).

  • MAP_ID: a human-readable representation of the map_to_curve function as defined in Section 6. These are defined as follows:

    • "SVDW" for Shallue and van de Woestijne (Section 6.6.1).

    • "SSWU" for Simplified SWU (Sections 6.6.2 and 6.6.3).

    • "ELL2" for Elligator 2 (Sections 6.7.1 and 6.8.2).

  • ENC_VAR: a string indicating the encoding type and other information. The first two characters of this string indicate whether the suite represents a hash_to_curve or an encode_to_curve operation (Section 3), as follows:

    • If ENC_VAR begins with "RO", the suite uses hash_to_curve.

    • If ENC_VAR begins with "NU", the suite uses encode_to_curve.

    • ENC_VAR MUST NOT begin with any other string.

    ENC_VAR MAY also be used to encode other information used to identify variants, for example, a version number. The RECOMMENDED way to do so is to add one or more subfields separated by colons. For example, "RO:V02" is an appropriate ENC_VAR value for the second version of a uniform encoding suite, while "RO:V02:FOO01:BAR17" might be used to indicate a variant of that suite.

Last updated on