1. 简介 (Introduction)

许多密码学协议都需要一个将任意输入（例如口令）编码为椭圆曲线上一点的过程. 这一过程被称为"哈希到椭圆曲线" (hashing to an elliptic curve), 其中的哈希过程需提供抗碰撞性, 并且不能泄露输出点的离散对数. 采用哈希到椭圆曲线方式的密码系统的突出例子包括: 口令认证密钥交换 (password-authenticated key exchanges) [BM92] [J96] [BMP00] [p1363.2]、基于身份的加密 (Identity-Based Encryption) [BF01]、Boneh-Lynn-Shacham 签名 [BLS01] [BLS-SIG]、可验证随机函数 (Verifiable Random Functions) [MRV99] [VRF], 以及不经意伪随机函数 (Oblivious Pseudorandom Functions) [NR97] [OPRFs].

对于实现者而言不幸的是, 对于一个使用特定椭圆曲线实现的特定协议, 究竟哪一种哈希函数才适用, 往往无法从协议的描述中得到明确答案. 与此同时, 一旦哈希函数选择不当, 就可能对安全性造成灾难性后果.

本文档旨在弥合这一鸿沟, 为一系列曲线类型提供一套全面的推荐算法. 每种算法都遵循一个统一的接口: 它以任意长度的字节串作为输入, 并产生椭圆曲线上的一个点作为输出. 我们为每种算法提供了实现细节, 阐述了每条推荐背后的安全依据, 并为未明确覆盖的椭圆曲线给出了指导意见. 我们还给出了这些算法所用内部函数的优化实现.

希望快速指定或实现一套合规哈希函数的读者, 应查阅第 8 节, 该节列出了推荐的哈希到曲线套件 (hash-to-curve suites), 并说明了如何实现已有套件以及如何指定新的套件.

本文档不规定概率性拒绝采样方法 (probabilistic rejection sampling methods), 有时亦称为 "try-and-increment" (试错递增) 或 "hunt-and-peck" (试探啄取), 因为我们的目标是规定出能够在常数时间内合理计算的算法. 不建议 (NOT RECOMMENDED) 使用这些概率性拒绝方法, 因为它们一直以来都是侧信道漏洞的根源. 关于这一问题的实际例子, 可参见 Dragonblood [VR20]; 关于拒绝采样方法及其所引入的时序侧信道的非正式描述, 见附录 A.

本文档代表了密码论坛研究组 (Crypto Forum Research Group, CFRG) 的共识.

1.1. 需求表示法 (Requirements Notation)

本文档中的关键词 "MUST" (必须)、"MUST NOT" (禁止)、"REQUIRED" (要求)、"SHALL" (应)、"SHALL NOT" (不应)、"SHOULD" (应当)、"SHOULD NOT" (不应)、"RECOMMENDED" (推荐)、"NOT RECOMMENDED" (不推荐)、"MAY" (可以) 和 "OPTIONAL" (可选), 当且仅当它们以全大写形式出现时 (如此处所示), 才应按照 BCP 14 [RFC2119] [RFC8174] 中的描述进行解释.