跳到主要内容

12. 附录 (Appendices)

将任意位串映射到椭圆曲线点的问题一直是实践和理论研究的主题。本节简要描述了本文档中建议的背景和研究结果。本节仅供参考。

A.1. 背景​

将字符串 msg 映射到具有 n 个点的椭圆曲线 E 上的点的一个简单但通常不安全的方法是：首先固定生成椭圆曲线群的点 P，以及从位串到小于 n 的整数的哈希函数 Hn；然后计算 Hn(msg) * P，其中 * 运算符表示标量乘法。这种方法不安全的原因是结果点与 P 具有已知的离散对数关系。因此，除非协议指定此方法，否则不得使用它；这样做会导致灾难性的安全故障。

A.2. 历史方法​

Boneh 等人 [BLS01] 描述了一种称为 MapToGroup 的编码方法，它大致如下工作：首先使用输入字符串初始化伪随机数生成器，然后使用生成器产生 F 中的值 x。如果 x 是椭圆曲线上点的 x 坐标，则输出该点。否则，在 F 中生成新值 x 并重试。由于 F 中的随机值 x 对应曲线上点的概率约为 1/2，预期尝试次数仅为两次。然而，这种方法（通常称为概率试错递增算法）的运行时间取决于输入字符串。因此，在对时序侧信道敏感的协议中使用并不安全，正如 Dragonblood 攻击 [VR20] 所示。

A.3. 确定性方法的发展​

Schinzel 和 Skalba [SS04] 引入了一种确定性构造椭圆曲线点的方法，适用于受限类别的曲线和极少数点。Skalba [S05] 将此构造推广到更多曲线和这些曲线上的更多点。Shallue 和 van de Woestijne [SW06] 进一步推广和简化了 Skalba 的构造，对几乎任何曲线产生了映射到曲线上常数部分点的具体高效映射。

Ulas [U07] 描述了 Shallue-van de Woestijne 映射的更简单版本，Brier 等人 [BCIMRT10] 进行了进一步简化，作者称之为"简化 SWU"映射。该简化映射仅适用于特征 p = 3 (mod 4) 的域；Wahby 和 Boneh [WB19] 推广到任何特征的域并给出了进一步的优化。

A.4. 特定曲线的映射​

Boneh 和 Franklin 给出了一种确定性算法，映射到特征 p = 2 (mod 3) 的域上的某些超奇异曲线 [BF01]。Icart 给出了另一种确定性算法，映射到特征 p = 2 (mod 3) 的域上的任何曲线 [Icart09]。这项工作之后有几个扩展和推广，包括 [FSV09]、[FT10]、[KLR10]、[F11] 和 [CK11]。

继 Farashahi [F11] 的工作之后，Fouque 等人 [FJT13] 描述了对特征 p = 3 (mod 4) 的域上具有可被 4 整除的点数的曲线的映射。Bernstein 等人 [BHKL13] 优化了此映射并描述了称为"Elligator 2"的相关映射，它适用于奇特征域上具有 2 阶点的任何曲线。这包括 Curve25519 和 Curve448，两者都是 CFRG 推荐的曲线 [RFC7748]。

A.5. 随机预言机编码​

关于上述所有确定性映射函数的一个重要警告是，它们都不映射到整个曲线，而是映射到点的某个部分。这意味着它们不能直接用于构造在曲线上输出点的随机预言机。

Brier 等人 [BCIMRT10] 给出了此问题的两个解决方案。第一个计算 f(H0(msg)) + f(H1(msg))，用于从位串到 F 的两个不同哈希函数 H0 和 H1 以及从 F 到椭圆曲线 E 的映射 f。第二个计算 f(H0(msg)) + H2(msg) * P，其中 P 是椭圆曲线群的生成元。

Farashahi 等人 [FFSTV13] 改进了第一种方法的分析，表明它本质上适用于所有确定性映射。Tibouchi 和 Kim [TK17] 进一步完善了分析并描述了额外的优化。

附录 B. 哈希到 ristretto255​

ristretto255 [ristretto255-decaf448] 提供基于 curve25519 [RFC7748] 的素数阶群。本节描述 hash_to_ristretto255，它实现了对该群的随机预言机编码，具有均匀输出分布（第 2.2.3 节）并与 hash_to_curve 函数（第 3 节）具有相同的安全属性和接口。

附录 C. 哈希到 decaf448​

与 ristretto255 类似，decaf448 [ristretto255-decaf448] 提供基于 curve448 [RFC7748] 的素数阶群。本节描述 hash_to_decaf448。

附录 D. Montgomery 和扭曲 Edwards 曲线的有理映射​

本附录给出了 Montgomery 和扭曲 Edwards 曲线之间的有理映射，允许在这些曲线形式之间进行转换。

附录 E. 同源映射 (Isogeny Maps)​

本附录给出了某些曲线的同源映射的显式形式，用于 AB == 0 的简化 SWU 方法（第 6.6.3 节）。

E.1. secp256k1 的 3-同源映射​

E.2. BLS12-381 G1 的 11-同源映射​

E.3. BLS12-381 G2 的同源映射​

附录 F. 直线实现 (Straight-Line Implementations)​

本附录给出了本文档中某些映射的优化直线实现。

F.1. Shallue-van de Woestijne 方法​

F.2. 简化 SWU 方法​

附录 G. 特定曲线的优化 (Curve-Specific Optimizations)​

本附录给出了某些曲线的特定优化。

G.1. 关于选择 Z 的说明​

G.2. 25519 和 448 曲线的映射​

G.2.1. curve25519 (Montgomery 形式)​

G.2.2. edwards25519 (扭曲 Edwards 形式)​

G.2.3. curve448 (Montgomery 形式)​

G.2.4. edwards448 (扭曲 Edwards 形式)​

G.3. BLS12-381 的余因子清除​

附录 H. 选择 Z 的 Sage 脚本​

本附录给出了用于为某些映射选择推荐 Z 值的 Sage [SAGE] 脚本。

H.1. Shallue-van de Woestijne 方法​

H.2. 简化 SWU 方法​

附录 I. 平方根计算 (Square Root Computation)​

本附录给出了在某些域中计算平方根的算法。

I.1. 素域的平方根​

I.1.1. p = 3 (mod 4)​

I.1.2. p = 5 (mod 8)​

I.1.3. 通用情况：Tonelli-Shanks 算法​

I.2. 扩展域的平方根​

I.2.1. GF(p^2) 的平方根，p = 3 (mod 4)​

I.2.2. GF(p^2) 的平方根，p = 1 (mod 4)​

I.3. 扩展域的 sgn0​

I.4. 扩展域的 sqrt 和 is_square​

I.5. GF(p^2) 的优化 is_square​

注意：附录包含大量技术细节、算法实现和参数。完整的附录内容（包括具体算法、代码示例和数学证明）请参考原始 RFC 9380 文档：https://www.rfc-editor.org/rfc/rfc9380.html

本附录提供的概述涵盖了主要主题，但实现者应参考完整的 RFC 文档以获取详细的技术规范和示例代码。

最后于 更新