2. 背景 (Background)
2.1. 椭圆曲线 (Elliptic Curves)
下面简要定义椭圆曲线，重点说明重要参数及其与哈希到曲线的关系。关于椭圆曲线的进一步参考，可查阅 [CFADLNV05] 或 [W08]。
令 F 为素数特征 p > 3 的有限域 GF(q)。（本文档不考虑特征为 2 或 3 的域上的椭圆曲线。）大多数情况下，F 是一个素数域，因此 q = p。否则，F 是一个扩张域，因此 q = p^m，其中整数 m > 1。本文档采用本原元基或多项式基来书写扩张域的元素，即写作一个由 m 个 GF(p) 元素按次数升序排列构成的向量。该向量的各分量按升序从 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 的代数群，即该群有 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，且 #F = q = p^m。 | 对于素数域，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)
映射（mapping）是一个从域 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)
随机预言机编码满足一个很强的性质：在适当的假设下，可以证明其不可区分于（indifferentiable from）一个随机预言机 [MRH04]。
当按照本文档的指导原则实例化时，第 3 节描述的两种构造都不可区分于随机预言机 [MRH04]。这两种构造的输出分布不同：一种给出曲线上的一个均匀随机点，另一种给出按非均匀分布采样得到的点。
具有均匀输出分布的随机预言机编码，适用于在以随机预言机模型证明安全的许多密码学协议中使用。进一步讨论见第 10.1 节。
2.2.4. 序列化 (Serialization)
与编码相关的另一个过程，是将椭圆曲线上的点转换为位串。这称为序列化（serialization），通常用于紧凑地存储或传输点。其逆操作反序列化（deserialization）将位串转换为椭圆曲线上的点。例如，[SEC1] 和 [p1363a] 给出了序列化和反序列化的标准方法。
反序列化与编码的不同之处在于，只有某些字符串（即由序列化过程输出的那些字符串）才能被反序列化。相比之下，本文档关注的是从任意字符串到椭圆曲线点的编码。本文档不涵盖序列化或反序列化。
2.2.5. 域分离 (Domain Separation)
在随机预言机模型中证明安全的密码学协议，其安全性分析通常基于这样的假设：该随机预言机只回答与该协议相关联的查询（包括由敌手发起的查询）[BR93]。在实践中，如果两个协议使用同一个函数来实例化随机预言机，这一假设就不成立。具体来说，考虑查询随机预言机 RO 的协议 P1 和 P2：如果 P1 和 P2 都在同一个值 x 上查询 RO，那么对其中一个或两个协议的安全性分析就可能失效。
解决这一问题的常见方法称为域分离（domain separation），它允许单个随机预言机模拟出多个相互独立的预言机。这是通过确保每一个被模拟的预言机所看到的查询，都不同于所有其他被模拟预言机所看到的查询来实现的。例如，给定一个预言机 RO 来模拟两个预言机 RO1 和 RO2，可以定义
RO1(x) := RO("RO1" || x)
RO2(x) := RO("RO2" || x)
其中 || 是连接运算符。在此例中，"RO1" 和 "RO2" 称为域分离标签（domain separation tags，DST）；它们确保对 RO1 和 RO2 的查询不会导致对 RO 的相同查询，这意味着将 RO1 和 RO2 视为独立预言机是安全的。
一般而言，域分离要求为每一个被模拟的预言机定义一个不同的单射编码。在上述例子中，"RO1" 和 "RO2" 长度相同，因此作为前缀使用时满足这一要求。本文档规定了一套不同的方法来确保单射性；详见第 5.3 节和第 10.7 节。