2. 背景 (Background)
2.1. 椭圆曲线 (Elliptic Curves)
以下是椭圆曲线的简要定义，重点介绍重要参数及其与哈希到曲线的关系。有关椭圆曲线的进一步参考，请参阅 [CFADLNV05] 或 [W08]。
设 F 是特征为 p > 3 的有限域 GF(q)。（本文档不考虑特征为 2 或 3 的椭圆曲线。）在大多数情况下，F 是素域，因此 q = p。否则，F 是扩展域，因此对于整数 m > 1，q = p^m。本文档以原始元素或多项式基来表示扩展域的元素，即作为 GF(p) 的 m 个元素的向量，按升序排列。此向量的条目从 1 开始按升序索引，即 x = (x_1, x_2, ..., x_m)。例如，如果 q = p^2 且原始元素基为 (1, I)，则 x = (a, b) 对应于元素 a + b * I，其中 x_1 = a 和 x_2 = b。（请注意，所有基的选择都是同构的，但某些选择可能导致更高效的实现；本文档不对基的选择做任何特定假设。）
椭圆曲线 E 由两个变量的方程和有限域 F 指定。椭圆曲线方程采用几种标准形式之一，包括（但不限于）Weierstrass、Montgomery 和 Edwards 形式。
曲线 E 产生一个阶为 n 的代数群 (algebraic group)，这意味着该群有 n 个不同的元素。（本文档对椭圆曲线群运算使用加法记号。）椭圆曲线群的元素是具有仿射坐标 (x, y) 的点，满足曲线方程，其中 x 和 y 是 F 的元素。此外，所有椭圆曲线群都有一个特殊元素，即单位元 (identity point)，它作为群运算的单位元。在某些曲线上（包括 Weierstrass 和 Montgomery 曲线），单位元不能表示为 (x, y) 坐标对。
出于安全原因，椭圆曲线的密码学应用通常需要使用素数阶的（子）群。设 G 是曲线的素数阶为 r 的子群，其中 n = h * r。在此方程中，h 是称为余因子 (cofactor) 的整数。接受曲线 E 上任意点作为输入并产生 E 的子群 G 中的点作为输出的算法称为"清除余因子" (clear the cofactor)。第 7 节讨论了此类算法。
某些哈希到曲线算法限制曲线方程的形式、域的特征或曲线的参数。对于所提出的每个算法，本文档列出了相关限制。
下表总结了与哈希到曲线相关的量：
| 符号 | 含义 | 相关性 |
|---|---|---|
| F,q,p | 特征为 p 且 #F = q = p^m 的有限域 F。 | 对于素域，q = p；否则，q = p^m 且 m>1。 |
| E | 椭圆曲线。 | E 由方程和域 F 指定。 |
| n | 椭圆曲线 E 上的点数。 | n = h * r，h 和 r 定义如下。 |
| G | E 上点的素数阶子群。 | G 是字节串被编码到的目标群。 |
| r | G 的阶。 | r 是 n 的素因子（通常是最大的此类因子）。 |
| h | 余因子，h >= 1。 | h 是满足 n = h * r 的整数。 |
表 1：符号及其定义的摘要
2.2. 术语 (Terminology)
在本节中，我们定义了本文档中使用的重要术语。
2.2.1. 映射 (Mappings)
映射是从域 F 的元素到定义在 F 上的椭圆曲线 E 上的点的确定性函数。
一般来说，映射在所有可能输入上可以产生的所有点的集合可能只是椭圆曲线上点的一个子集（即，映射可能不是满射的）。此外，映射可能为两个或多个不同的输入输出相同的点（即，映射可能不是单射的）。例如，考虑从 F 到具有 n 个点的椭圆曲线的映射：如果 F 的元素数量不等于 n，则此映射不能是双射的（即，既是单射又是满射），因为映射被定义为确定性的。
映射也可能是可逆的，这意味着存在一个高效算法，对于映射输出的任何点 P，输出 F 中的 x，使得将映射应用于 x 输出 P。第 6 节中给出的一些映射是可逆的，但本文档不讨论逆算法。
2.2.2. 编码 (Encodings)
编码与映射密切相关。像映射一样，编码是输出椭圆曲线上点的函数。与映射不同的是，编码的输入是任意长度的字节串。
本文档通过将哈希函数 Hf 与确定性映射组合来构造确定性编码。特别是，Hf 接受任意字符串作为输入并输出 F 的一个元素。确定性映射将该元素作为输入并输出定义在 F 上的椭圆曲线 E 上的一个点。由于 Hf 接受任意长度的字节串作为输入，它不能是单射的：输入集大于输出集，因此必须存在给出相同输出的不同输入（即，必须存在碰撞）。因此，从 Hf 构建的任何编码也不是单射的。
像映射一样，编码可能是可逆的，这意味着存在一个高效算法，对于编码输出的任何点 P，输出字符串 s，使得将编码应用于 s 输出 P。然而，本文档指定的所有编码使用的 Hf 实例化（第 5 节）不是可逆的；因此，这些编码也不是可逆的。
在某些哈希到椭圆曲线的应用中，重要的是编码不通过侧信道泄露信息。[VR20] 是此类泄露导致安全漏洞的一个示例。有关进一步讨论，请参见第 10.3 节。
2.2.3. 随机预言机编码 (Random Oracle Encodings)
随机预言机编码满足一个强性质：在适当的假设下，它可以被证明与随机预言机不可区分 [MRH04]。
第 3 节中描述的两种构造在按照本文档中的指南实例化时，都与随机预言机不可区分 [MRH04]。这些构造在输出分布上有所不同：一个在曲线上给出均匀随机点，另一个给出从非均匀分布中采样的点。
具有均匀输出分布的随机预言机编码适用于许多在随机预言机模型中被证明安全的密码学协议。有关进一步讨论，请参见第 10.1 节。
2.2.4. 序列化 (Serialization)
与编码相关的过程是将椭圆曲线点转换为位串。这称为序列化，通常用于紧凑地存储或传输点。逆操作，反序列化，将位串转换为椭圆曲线点。例如，[SEC1] 和 [p1363a] 给出了序列化和反序列化的标准方法。
反序列化与编码不同，因为只有某些字符串（即，由序列化过程输出的字符串）可以被反序列化。相反，本文档关注的是从任意字符串到椭圆曲线点的编码。本文档不涵盖序列化或反序列化。
2.2.5. 域分离 (Domain Separation)
在随机预言机模型中被证明安全的密码学协议通常在假设随机预言机仅回答与该协议相关的查询（包括对手的查询）[BR93] 的情况下进行分析。实际上，如果两个协议使用相同的函数来实例化随机预言机，则此假设不成立。具体而言，考虑查询随机预言机 RO 的协议 P1 和 P2：如果 P1 和 P2 都在相同的值 x 上查询 RO，则一个或两个协议的安全分析可能无效。
解决此问题的一种常见方法称为域分离，它允许单个随机预言机模拟多个独立的预言机。这通过确保每个模拟预言机看到的查询与所有其他模拟预言机看到的查询不同来实现。例如，要使用单个预言机 RO 模拟两个预言机 RO1 和 RO2，可以定义
RO1(x) := RO("RO1" || x)
RO2(x) := RO("RO2" || x)
其中 || 是连接运算符。在此示例中，"RO1" 和 "RO2" 称为域分离标签 (domain separation tags, DSTs)；它们确保对 RO1 和 RO2 的查询不能导致对 RO 的相同查询，这意味着将 RO1 和 RO2 视为独立预言机是安全的。
一般来说，域分离需要为正在模拟的每个预言机定义一个独特的单射编码。在上面的示例中，"RO1" 和 "RO2" 具有相同的长度，因此在用作前缀时满足此要求。本文档中指定的算法采用不同的方法来确保单射性；有关更多详细信息，请参见第 5.3 节和第 10.7 节。