5. 哈希到有限域 (Hashing to a Finite Field)

hash_to_field 函数将任意长度的字节串 msg 哈希为一个或多个域 F 中的元素。该函数分两步工作：它首先将输入字节串哈希，产生一个均匀随机的字节串，然后将该字节串解释为一个或多个 F 中的元素。

第一步，hash_to_field 调用辅助函数 expand_message。本文档定义了 expand_message 的两种变体：一种适用于 SHA-2 [FIPS180-4] 或 SHA-3 [FIPS202] 这类哈希函数，另一种适用于 SHAKE128 [FIPS202] 这类可扩展输出函数（XOF）。每种 expand_message 变体的安全性考虑在下面讨论（第 5.3.1 节和第 5.3.2 节）。

实现者 MUST NOT 使用拒绝采样来生成 F 的均匀随机元素，以确保 hash_to_field 函数便于以常量时间实现。原因是拒绝采样过程难以以常量时间实现，而且后来善意的"优化"可能会悄然使某个实现变为非常量时间。这意味着任何基于拒绝采样的 hash_to_field 函数都将与常量时间实现不兼容。

hash_to_field 函数也适用于安全地哈希到标量。例如，当哈希到素数阶 r 的椭圆曲线（子）群的标量域时，只需用目标域 GF(r) 实例化 hash_to_field 即可。

当把 expand_message（第 5.3 节）建模为随机预言机时，hash_to_field 函数被设计为不可区分于随机预言机 [MRH04]（关于其不可区分性，详见第 10.5 节）。确保不可区分性需要谨慎；要理解其中原因，考虑一个接近 3/4 * 2^256 的素数 p。将一个随机的 256 位整数对该 p 取模，得到的值落在区间 [0, p / 3] 内的概率大约为 1/2，这意味着该值在统计上远非 [0, p - 1] 上的均匀分布。

为了控制偏差，hash_to_field 改为使用长度至少为 ceil(log2(p)) + k 比特的随机整数，其中 k 是该套件的目标安全级别（以比特计）。将这样的整数对 p 取模，对任何 p 产生的偏差至多为 2^-k；当以 k 比特安全性为目标时，这一偏差是合适的。对于每一个这样的整数，hash_to_field 使用 expand_message 得到 L 个均匀字节，其中

L = ceil((ceil(log2(p)) + k) / 8)

随后通过 OS2IP 将这些均匀字节解释为一个整数。例如，对于一个 255 位的素数 p，且 k = 128 比特安全性，L = ceil((255 + 128) / 8) = 48 字节。

注意 k 是相应曲线安全级别的上界。更多细节见第 10.8 节，关于为给定曲线选择 k 的指导见第 8.9 节。

5.1. 扩张域中的效率考量 (Efficiency Considerations in Extension Fields)

本节描述的 hash_to_field 函数对某些扩张域效率低下。具体地，当哈希到扩张域 GF(p^m) 的一个元素时，hash_to_field 需要将 msg 扩展为 m * L 字节（L 如上定义）。对于 log2(p) 远小于安全级别 k 的扩张域，这种方法效率低下：它要求 expand_message 输出大约 m * log2(p) + m * k 比特，而生成偏差至多为 2^-k 的 GF(p^m) 元素，只需 m * log2(p) + k 字节就足够了。在这种情况下，应用 MAY 使用替代的 hash_to_field 函数，前提是它满足以下安全要求：

该函数 MUST 输出一个或多个域元素，这些元素除至多 2^-k 的偏差外是均匀随机的。
该函数 MUST NOT 使用拒绝采样。
该函数 SHOULD 便于直线式（straight-line）实现。

例如，Pornin [P20] 描述了一种哈希到 GF(9767^19) 的方法，它满足这些要求，同时使用的 expand_message 输出比特数少于 hash_to_field 对该域所需的数量。

5.2. hash_to_field 实现 (hash_to_field Implementation)

下面的过程实现 hash_to_field。

该函数的 expand_message 参数 MUST 符合第 5.3 节给出的要求。第 3.1 节讨论了构造 DST（域分离标签）的 REQUIRED 方法。注意，如果 expand_message 失败，hash_to_field 也可能失败（ABORT）。

hash_to_field(msg, count)

Parameters:
- DST, 一个域分离标签（见第 3.1 节）。
- F, 特征为 p、阶为 q = p^m 的有限域。
- p, F 的特征（见上）。
- m, F 的扩张次数，m >= 1（见上）。
- L = ceil((ceil(log2(p)) + k) / 8)，其中 k 是套件的安全
  参数（例如 k = 128）。
- expand_message, 将字节串和域分离标签扩展为
  均匀随机字节串的函数（见第 5.3 节）。

Input:
- msg, 包含待哈希消息的字节串。
- count, 要输出的 F 的元素个数。

Output:
- (u_0, ..., u_(count - 1)), 一个域元素列表。

Steps:
1. len_in_bytes = count * m * L
2. uniform_bytes = expand_message(msg, DST, len_in_bytes)
3. for i in (0, ..., count - 1):
4.   for j in (0, ..., m - 1):
5.     elm_offset = L * (j + i * m)
6.     tv = substr(uniform_bytes, elm_offset, L)
7.     e_j = OS2IP(tv) mod p
8.   u_i = (e_0, ..., e_(m - 1))
9. return (u_0, ..., u_(count - 1))

5.3. expand_message

expand_message 是一个生成均匀随机字节串的函数。它接受三个参数：

msg，包含待哈希消息的字节串，
DST，充当域分离标签的字节串，以及
len_in_bytes，要生成的字节数。

本文档定义了以下两种 expand_message 变体：

expand_message_xmd（第 5.3.1 节）适用于范围广泛的哈希函数，包括 SHA-2 [FIPS180-4]、SHA-3 [FIPS202]、BLAKE2 [RFC7693] 等。
expand_message_xof（第 5.3.2 节）适用于可扩展输出函数（XOF），包括 SHAKE [FIPS202] 或 BLAKE2X [BLAKE2X] 系列中的函数。

这些变体应该足以满足绝大多数用例，但也可能有其他变体；第 5.3.4 节讨论了相关要求。

5.3.1. expand_message_xmd

expand_message_xmd 函数使用一个输出 b 比特的密码学哈希函数 H 来生成均匀随机字节串。出于安全性考虑，H MUST 满足以下要求：

H 输出的比特数 MUST 为 b >= 2 * k，其中 k 是目标安全级别（比特），且 b MUST 能被 8 整除。第一个要求确保了 k 比特的抗碰撞性；第二个要求确保了 expand_message_xmd 输出的均匀性。
H MAY 是像 SHA-2 这样的 Merkle-Damgaard 哈希函数。在这种情况下，当底层压缩函数被建模为随机预言机 [CDMP05] 时，安全性成立。（讨论见第 10.6 节。）
H MAY 是像 SHA-3 或 BLAKE2 这样的基于海绵结构的哈希函数。在这种情况下，当内部函数被建模为随机变换或随机置换 [BDPV08] 时，安全性成立。
否则，H MUST 是一个在合理密码学假设下已被证明不可区分于随机预言机 [MRH04] 的哈希函数。

SHA-2 [FIPS180-4] 和 SHA-3 [FIPS202] 是典型且 RECOMMENDED 的选择。作为一个例子，对于 128 比特安全级别，b >= 256 比特，此时 SHA-256 或 SHA3-256 都是合适的选择。

哈希函数 H 被假定通过重复吸收固定长度的数据块来工作。这些块的长度（以比特计）称为输入块大小（s）。例如，SHA-512 [FIPS180-4] 的 s = 1024，SHA3-512 [FIPS202] 的 s = 576。为保证正确性，H 要求 b <= s。

下面的过程实现 expand_message_xmd。

expand_message_xmd(msg, DST, len_in_bytes)

Parameters:
- H, 一个哈希函数（见上述要求）。
- b_in_bytes, H 输出大小（以比特计）b / 8。
  例如，对于 b = 256，b_in_bytes = 32。
- s_in_bytes, H 的输入块大小，以字节计（见上
  述讨论）。例如，对于 SHA-256，s_in_bytes = 64。

Input:
- msg, 一个字节串。
- DST, 至多 255 字节的字节串。
  使用更长 DST 的信息见下文。
- len_in_bytes, 请求输出的长度（字节），
  不大于 (255 * b_in_bytes) 与 2^16-1 两者中的较小值。

Output:
- uniform_bytes, 一个字节串。

Steps:
1.  ell = ceil(len_in_bytes / b_in_bytes)
2.  ABORT if ell > 255 or len_in_bytes > 65535 or len(DST) > 255
3.  DST_prime = DST || I2OSP(len(DST), 1)
4.  Z_pad = I2OSP(0, s_in_bytes)
5.  l_i_b_str = I2OSP(len_in_bytes, 2)
6.  msg_prime = Z_pad || msg || l_i_b_str || I2OSP(0, 1) || DST_prime
7.  b_0 = H(msg_prime)
8.  b_1 = H(b_0 || I2OSP(1, 1) || DST_prime)
9.  for i in (2, ..., ell):
10.    b_i = H(strxor(b_0, b_(i - 1)) || I2OSP(i, 1) || DST_prime)
11. uniform_bytes = b_1 || ... || b_ell
12. return substr(uniform_bytes, 0, len_in_bytes)

注意字符串 Z_pad（第 6 步）在计算 b_0（第 7 步）之前被前缀到 msg 上。当 H 是 Merkle-Damgaard 哈希（例如 SHA-2）时，这对安全性是必要的（见第 10.6 节）。哈希这段额外的数据意味着计算 b_0 的代价高于仅仅计算 H(msg)。在大多数设置中，这一开销可以忽略不计，因为计算 H 的代价远小于哈希到曲线所牵涉的其他代价。

然而，可以利用 Z_pad 仅依赖于 H、而不依赖于 expand_message_xmd 参数的事实，来完全避免这一开销。为此，先预计算并保存吸收 Z_pad 之后 H 的内部状态。然后，在计算 b_0 时，使用该保存的状态初始化 H。进一步的细节取决于具体实现，超出了本文档的范围。

5.3.2. expand_message_xof

expand_message_xof 函数使用一个可扩展输出函数（XOF）H 来生成均匀随机字节串。出于安全性考虑，H MUST 满足以下标准：

H 的抗碰撞性 MUST 至少为 k 比特。
H MUST 是一个已被证明在合理密码学假设下不可区分于随机预言机的 XOF。

SHAKE XOF 系列 [FIPS202] 是典型且 RECOMMENDED 的选择。作为一个例子，对于 128 比特安全性，SHAKE128 是一个合适的选择。

下面的过程实现 expand_message_xof。

expand_message_xof(msg, DST, len_in_bytes)

Parameters:
- H(m, d), 一个处理输入消息 m 并返回 d 字节的
  可扩展输出函数。

Input:
- msg, 一个字节串。
- DST, 至多 255 字节的字节串。
  使用更长 DST 的信息见下文。
- len_in_bytes, 请求输出的长度（字节）。

Output:
- uniform_bytes, 一个字节串。

Steps:
1. ABORT if len_in_bytes > 65535 or len(DST) > 255
2. DST_prime = DST || I2OSP(len(DST), 1)
3. msg_prime = msg || I2OSP(len_in_bytes, 2) || DST_prime
4. uniform_bytes = H(msg_prime, len_in_bytes)
5. return uniform_bytes

5.3.3. 使用长于 255 字节的 DST (Using DSTs Longer than 255 Bytes)

本节定义的 expand_message 变体接受的域分离标签至多为 255 字节。如果应用需要一个长于 255 字节的域分离标签（例如由于调用协议施加的要求），实现者 MUST 通过哈希来计算一个短的域分离标签，如下所示：

对于使用哈希函数 H 的 expand_message_xmd，DST 计算为

DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST)

对于使用可扩展输出函数 H 的 expand_message_xof，DST 计算为

DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST, ceil(2 * k / 8))

此处，a_very_long_DST 是长度大于 255 字节的 DST，"H2C-OVERSIZE-DST-" 是一个 17 字节的 ASCII 字符串字面量，k 是目标安全级别（比特）。

5.3.4. 定义其他 expand_message 变体 (Defining Other expand_message Variants)

在定义新的 expand_message 变体时，最重要的考量是 hash_to_field 将 expand_message 建模为随机预言机。因此，实现者 SHOULD 在关于底层密码学原语的适当假设下，证明其不可区分于随机预言机；更多信息见第 10.5 节。

此外，expand_message 变体：

MUST 提供与目标椭圆曲线安全级别相称的抗碰撞性。
MUST 建立在为需要密码学随机性的应用而设计的原语之上。例如，安全的流密码是合适的原语，而 Mersenne twister 伪随机数生成器 [MT98] 则不是。
MUST NOT 使用拒绝采样。
MUST 对不同的 (msg, DST, length) 输入给出独立的值。满足这一要求很微妙。作为一个简化的例子，哈希 msg || DST 是行不通的，因为在这种情况下，其连接结果相等的不同的 (msg, DST) 对会返回相同的输出（例如 ("AB", "CDEF") 和 ("ABC", "DEF")）。本文档定义的变体使用 DST 的无后缀编码来避免此问题。
MUST 使用域分离标签 DST，以确保 expand_message 内部对密码学原语的调用，与 expand_message 外部对密码学原语的调用是域分离的。例如，如果 expand_message 变体使用哈希函数 H，则 MUST 在每个对 H 的调用中，将 DST 的某种编码作为前缀或后缀加入。RECOMMENDED 的方法是将 DST 作为后缀加入。
SHOULD 恰好读取 msg 一次，以便在 msg 较长时提高效率。

此外，每个 expand_message 变体 MUST 指定一个唯一的 EXP_TAG，用于在 Suite ID 中标识该变体。更多信息见第 8.10 节。

5.1. 扩张域中的效率考量 (Efficiency Considerations in Extension Fields)​

5.2. hash_to_field 实现 (hash_to_field Implementation)​

5.3. expand_message​

5.3.1. expand_message_xmd​

5.3.2. expand_message_xof​

5.3.3. 使用长于 255 字节的 DST (Using DSTs Longer than 255 Bytes)​

5.3.4. 定义其他 expand_message 变体 (Defining Other expand_message Variants)​