跳到主要内容

6. 确定性映射 (Deterministic Mappings)

本节中的映射适用于使用第 3 节的构造来实现非均匀或均匀编码。某些映射会限制曲线或其参数的形式。对于本文档给出的每个映射，都列出了相关的限制条件。

注意，本节中的映射不可互换：不同的映射在对相同输入求值时，几乎必然输出不同的点。

6.1. 选择映射函数 (Choosing a Mapping Function)​

本节给出关于为给定椭圆曲线选择映射函数的简要指导。注意，第 8 节给出的套件是针对相应曲线的推荐映射。

如果目标椭圆曲线是 Montgomery 曲线（第 6.7 节），则推荐使用 Elligator 2 方法（第 6.7.1 节）。类似地，如果目标椭圆曲线是 twisted Edwards 曲线（第 6.8 节），则推荐使用 twisted Edwards Elligator 2 方法（第 6.8.2 节）。

其余情况是 Weierstrass 曲线。对于被 Simplified Shallue-van de Woestijne-Ulas（SWU）方法（第 6.6.2 节）支持的曲线，推荐使用该方法。否则，若目标是获得最佳性能，则推荐使用针对 AB == 0 的 Simplified SWU 方法（第 6.6.3 节）；若目标是实现简单，则推荐使用 Shallue-van de Woestijne 方法（第 6.6.1 节）。（作此区分的原因是，针对 AB == 0 的 Simplified SWU 方法除了映射函数外还需要实现一条同源映射（isogeny map），而 Shallue-van de Woestijne 方法则不需要。）

Shallue-van de Woestijne 方法（第 6.6.1 节）适用于任何曲线，在需要通用映射的情况下可以使用。然而请注意，这个映射几乎总是比上面针对特定曲线的推荐方法计算开销更大。

6.2. 接口 (Interface)​

本节所有映射共享的通用接口如下：

(x, y) = map_to_curve(u)

输入 u 以及输出 x、y 都是域 F 的元素。仿射坐标 (x, y) 指定了定义在 F 上的椭圆曲线上的一个点。然而请注意，点 (x, y) 并非一个均匀随机点。

6.3. 记号 (Notation)​

作为一个粗略指南，伪代码中使用了以下约定：

  • 除非显式说明，所有算术运算都在域 F 上执行。

  • u：映射函数的输入。这是 hash_to_field 函数产生的 F 的一个元素。

  • (x, y)、(s, t)、(v, w)：映射输出的点的仿射坐标。带索引的变量（例如 x1、y2、…）用于表示候选值。

  • tv1、tv2、…：可复用的临时变量。

  • c1、c2、…：常量值，可以预先计算。

6.4. 结果点的符号 (Sign of the Resulting Point)​

一般而言，椭圆曲线具有形如 y^2 = g(x) 的方程。本节中的映射首先确定一个使得 g(x) 为平方元的 x，然后取平方根以求得 y。由于当 g(x) != 0 时存在两个平方根，这可能会导致关于 y 符号的歧义。

在需要时，本节中的映射通过以映射函数输入来规定 y 坐标的符号，来解决这一歧义。支持这一方法的两个主要原因是：首先，它以统一的方式覆盖任意域上的椭圆曲线；其次，它给予实现者在优化平方根实现方面以灵活性。

6.5. 例外情况 (Exceptional Cases)​

映射可能存在例外情况，即映射未定义的输入 u。这些情况必须小心处理，特别是对于常量时间实现。

对于本节中的每个映射，我们都讨论其例外情况，并展示如何以常量时间处理它们。注意，所有实现 SHOULD 使用 inv0（第 4 节）来计算乘法逆元，以避免因尝试对 0 求逆而导致的例外情况。

6.6. Weierstrass 曲线的映射 (Mappings for Weierstrass Curves)​

本节中的映射适用于由以下方程定义的目标曲线 E：

y^2 = g(x) = x^3 + A * x + B

其中 4 * A^3 + 27 * B^2 != 0。

6.6.1. Shallue-van de Woestijne 方法 (Shallue-van de Woestijne Method)​

Shallue 和 van de Woestijne [SW06] 描述了一种几乎适用于任何椭圆曲线的映射。（然而请注意，这一映射的求值开销比其他映射更大。）

下面给出的参数化针对 Weierstrass 曲线；其推导详见 [W19]。该参数化也适用于 Montgomery 曲线（第 6.7 节）和 twisted Edwards 曲线（第 6.8 节），方式是使用附录 D 给出的有理映射：首先，将 Shallue-van de Woestijne 映射求值到一条等价的 Weierstrass 曲线，然后使用该曲线对应的有理映射将该点映射到目标的 Montgomery 或 twisted Edwards 曲线。

前置条件： 一条 Weierstrass 曲线 y^2 = x^3 + A * x + B。

常量：

  • A 和 B，Weierstrass 曲线的参数。

  • Z，满足下列判据的 F 的一个非零元素。附录 H.1 给出一个输出 RECOMMENDED Z 的 Sage 脚本 [SAGE]。

    1. g(Z) != 0（在 F 中）。
    2. -(3 * Z^2 + 4 * A) / (4 * g(Z)) != 0（在 F 中）。
    3. -(3 * Z^2 + 4 * A) / (4 * g(Z)) 在 F 中为平方元。
    4. g(Z) 和 g(-Z / 2) 中至少有一个在 F 中为平方元。

y 的符号： 对于许多 u 值，输入 u 和 -u 给出相同的 x 坐标。因此，我们设定 sgn0(y) == sgn0(u)。

例外情况： u 的例外情况发生在 (1 + u^2 * g(Z)) * (1 - u^2 * g(Z)) == 0 时。上述对 Z 的限制确保了使用 inv0 对该乘积求逆的实现是无例外的。

运算：

1. tv1 = u^2 * g(Z)
2. tv2 = 1 + tv1
3. tv1 = 1 - tv1
4. tv3 = inv0(tv1 * tv2)
5. tv4 = sqrt(-g(Z) * (3 * Z^2 + 4 * A))    # 可预先计算
6. If sgn0(tv4) == 1, set tv4 = -tv4        # sgn0(tv4) MUST 等于 0
7. tv5 = u * tv1 * tv3 * tv4
8. tv6 = -4 * g(Z) / (3 * Z^2 + 4 * A)      # 可预先计算
9.  x1 = -Z / 2 - tv5
10. x2 = -Z / 2 + tv5
11. x3 = Z + tv6 * (tv2^2 * tv3)^2
12. If is_square(g(x1)), set x = x1 and y = sqrt(g(x1))
13. Else If is_square(g(x2)), set x = x2 and y = sqrt(g(x2))
14. Else set x = x3 and y = sqrt(g(x3))
15. If sgn0(u) != sgn0(y), set y = -y
16. return (x, y)

附录 F.1 给出了该映射的一个直线式实现示例。

6.6.2. Simplified Shallue-van de Woestijne-Ulas 方法 (Simplified Shallue-van de Woestijne-Ulas Method)​

函数 map_to_curve_simple_swu(u) 实现了由 Brier 等人 [BCIMRT10] 所描述的 Shallue-van de Woestijne-Ulas 映射 [U07] 的简化版本，他们称之为"simplified SWU"（简化 SWU）映射。Wahby 和 Boneh [WB19] 对该映射进行了推广和优化。

前置条件： 一条 Weierstrass 曲线 y^2 = x^3 + A * x + B，其中 A != 0 且 B != 0。

常量：

  • A 和 B，Weierstrass 曲线的参数。

  • Z，满足下列判据的 F 的一个元素。附录 H.2 给出一个输出 RECOMMENDED Z 的 Sage 脚本 [SAGE]。判据如下：

    1. Z 在 F 中非平方，
    2. Z != -1（在 F 中），
    3. 多项式 g(x) - Z 在 F 上不可约，且
    4. g(B / (Z * A)) 在 F 中为平方元。

y 的符号： 输入 u 和 -u 给出相同的 x 坐标。因此，我们设定 sgn0(y) == sgn0(u)。

例外情况： 例外情况是满足 Z^2 * u^4 + Z * u^2 == 0 的 u 值。这包括 u == 0，也可能包括其他依赖于 Z 的值。实现必须检测这种情况并设定 x1 = B / (Z * A)，这由上述对 Z 的条件保证了 g(x1) 是平方元。

运算：

1. tv1 = inv0(Z^2 * u^4 + Z * u^2)
2.  x1 = (-B / A) * (1 + tv1)
3.  If tv1 == 0, set x1 = B / (Z * A)
4. gx1 = x1^3 + A * x1 + B
5.  x2 = Z * u^2 * x1
6. gx2 = x2^3 + A * x2 + B
7.  If is_square(gx1), set x = x1 and y = sqrt(gx1)
8.  Else set x = x2 and y = sqrt(gx2)
9.  If sgn0(u) != sgn0(y), set y = -y
10. return (x, y)

附录 F.2 给出了该映射的一个通用且优化过的直线式实现。关于优化该映射的更多信息，见 [WB19] 的第 4 节或 [hash2curve-repo] 中的示例代码。

6.6.3. 针对 AB == 0 的 Simplified SWU (Simplified SWU for AB == 0)​

Wahby 和 Boneh [WB19] 展示了如何将 Simplified SWU 映射改造以适用于具有 A == 0 或 B == 0 的 Weierstrass 曲线，而第 6.6.2 节的映射不支持这类曲线。（A == B == 0 的情况被排除，因为 y^2 = x^3 不是椭圆曲线。）

该方法适用于像 secp256k1 [SEC2] 这样的曲线，以及 Barreto-Lynn-Scott 族 [BLS03]、Barreto-Naehrig 族 [BN05] 等配对友好（pairing-friendly）曲线族。

该方法需要找到另一条由以下方程给出的椭圆曲线 E'：

y'^2 = g'(x') = x'^3 + A' * x' + B'

该曲线与 E 同源（isogenous），且 A' != 0、B' != 0。（关于使用 [SAGE] 寻找 E' 的一种方法，见 [WB19] 附录 A。）该同源定义了一组有理函数给出的映射 iso_map(x', y')。iso_map 以 E' 上的一点为输入，输出 E 上的一点。

一旦确定了 E' 和 iso_map，该映射的工作方式如下：给定输入 u，先应用 Simplified SWU 映射得到 E' 上的一点，然后对该点应用同源映射得到 E 上的一点。

注意 iso_map 是一个群同态，即点的加法与 iso_map 可交换。因此，当在第 3 节讨论的 hash_to_curve 构造中使用该映射时，可以通过先将 u0 和 u1 映射到 E'、将所得点在 E' 上相加、然后再对求和结果应用 iso_map，来实现一个小优化。这给出相同的结果，同时只需对 iso_map 求值一次。

前置条件： 一条椭圆曲线 E'，其 A' != 0、B' != 0，且与目标曲线 E 同源，同源映射 iso_map 从 E' 到 E。

辅助函数：

  • map_to_curve_simple_swu 是到第 6.6.2 节所定义 E' 的映射

  • iso_map 是从 E' 到 E 的同源映射

y 的符号： 对于该映射，符号由 map_to_curve_simple_swu 决定。无需作进一步的符号调整。

例外情况： map_to_curve_simple_swu 处理其自身的例外情况。iso_map 的例外情况是使任一有理函数分母求值到零的输入；这类情况 MUST 返回 E 上的单位点。

运算：

1. (x', y') = map_to_curve_simple_swu(u)    # (x', y') 在 E' 上
2.   (x, y) = iso_map(x', y')               # (x, y) 在 E 上
3. return (x, y)

关于实现同源映射的细节，见 [hash2curve-repo] 或 [WB19] 的第 4.3 节。

6.7. Montgomery 曲线的映射 (Mappings for Montgomery Curves)​

本节定义的映射适用于由以下方程定义的目标曲线 M：

K * t^2 = s^3 + J * s^2 + s

6.7.1. Elligator 2 方法 (Elligator 2 Method)​

Bernstein、Hamburg、Krasnova 和 Lange 给出了一种适用于任何具有 2 阶点的曲线的映射 [BHKL13]，他们称之为 Elligator 2。

前置条件： 一条 Montgomery 曲线 K * t^2 = s^3 + J * s^2 + s，其中 J != 0、K != 0，且 (J^2 - 4) / K^2 在 F 中非零且非平方。

常量：

  • J 和 K，椭圆曲线的参数。

  • Z，F 的一个非平方元素。附录 H.3 给出一个输出 RECOMMENDED Z 的 Sage 脚本 [SAGE]。

t 的符号： 该映射将 t 的符号固定为 [BHKL13] 中所规定的形式。无需额外调整。

例外情况： 例外情况是 Z * u^2 == -1，即 1 + Z * u^2 == 0。实现必须检测这种情况并设定 x1 = -(J / K)。注意这仅在 q = 3 (mod 4) 时才可能发生。

运算：

1.  x1 = -(J / K) * inv0(1 + Z * u^2)
2.  If x1 == 0, set x1 = -(J / K)
3. gx1 = x1^3 + (J / K) * x1^2 + x1 / K^2
4.  x2 = -x1 - (J / K)
5. gx2 = x2^3 + (J / K) * x2^2 + x2 / K^2
6.  If is_square(gx1), set x = x1, y = sqrt(gx1) with sgn0(y) == 1.
7.  Else set x = x2, y = sqrt(gx2) with sgn0(y) == 0.
8.   s = x * K
9.   t = y * K
10. return (s, t)

附录 F.3 给出了该映射的一个直线式实现示例。附录 G.2 给出了适用于特定曲线类和基域的优化直线式过程。

6.8. Twisted Edwards 曲线的映射 (Mappings for Twisted Edwards Curves)​

Twisted Edwards 曲线（包含 Edwards 曲线在内的一类曲线）由以下方程给出：

a * v^2 + w^2 = 1 + d * v^2 * w^2

其中 a != 0、d != 0 且 a != d [BBJLP08]。

这些曲线与 Montgomery 曲线（第 6.7 节）密切相关：每条 twisted Edwards 曲线都双有理等价于一条 Montgomery 曲线（[BBJLP08]，定理 3.2）。这一等价性产生了一种对 twisted Edwards 曲线进行哈希的有效方法：首先哈希到等价的 Montgomery 曲线，然后通过有理映射将结果转换为 twisted Edwards 曲线上的一点。因此，这种对 twisted Edwards 曲线哈希的方法需要确定一条相应的 Montgomery 曲线和有理映射。我们立即在下文描述如何确定这样的曲线和映射。

6.8.1. 从 Montgomery 到 Twisted Edwards 曲线的有理映射 (Rational Maps from Montgomery to Twisted Edwards Curves)​

在为给定的曲线选择时，有两种方法可以选择一条 Montgomery 曲线和有理映射，用于哈希到给定的 twisted Edwards 曲线。所选的 Montgomery 曲线和有理映射 MUST 作为给定 twisted Edwards 曲线的哈希到曲线套件的一部分加以规定；见第 8 节。

  1. 当哈希到一个标准化的 twisted Edwards 曲线，且其对应的 Montgomery 形式和有理映射也已被标准化时，SHOULD 使用标准的 Montgomery 形式和有理映射，以确保与现有软件的兼容性。

    在某些情况下，例如 edwards25519 [RFC7748]，从 twisted Edwards 曲线到其对应 Montgomery 曲线的有理映射的符号并未被显式给出。在这种情况下，MUST 固定该符号，使得将有理映射应用于 twisted Edwards 曲线的基点时，得到具有正确符号的 Montgomery 曲线的基点。（对于 edwards25519，见 [RFC7748] 和 [Err4730]。）

    在定义新的 twisted Edwards 曲线时，SHOULD 同时规定一个 Montgomery 等价形式和有理映射，并且 SHOULD 显式说明有理映射的符号。

  2. 当哈希到一个没有标准化 Montgomery 形式或标准化有理映射的 twisted Edwards 曲线时，SHOULD 使用附录 D 中给出的映射。

6.8.2. Elligator 2 方法 (Elligator 2 Method)​

前置条件： 一条 twisted Edwards 曲线 E 和一条满足第 6.8.1 节要求的等价 Montgomery 曲线 M。

辅助函数：

  • map_to_curve_elligator2 是到第 6.7.1 节所定义曲线 M 的映射。

  • rational_map 是一个函数，接受 M 上的一点 (s, t) 并返回 E 上的一点 (v, w)。该有理映射应如第 6.8.1 节所定义加以选择。

t（和 v）的符号： 对于该映射，符号由 map_to_curve_elligator2 决定。无需作进一步的符号调整。

例外情况： Elligator 2 映射的例外情况如第 6.7.1 节所述。有理映射的例外情况如第 6.8.1 节所述。不存在其他可能的例外情况。

下面的过程实现对一条 twisted Edwards 曲线的 Elligator 2 映射。（注意输出点记为 (v, w)，因为它是目标 twisted Edwards 曲线上的一点。）

map_to_curve_elligator2_edwards(u)

Input: u, F 的一个元素。
Output: (v, w), E 上的一点。

1. (s, t) = map_to_curve_elligator2(u)      # (s, t) 在 M 上
2. (v, w) = rational_map(s, t)              # (v, w) 在 E 上
3. return (v, w)