---
tags: 翻译
---

# 哈希到secp256k1椭圆曲线

:::info
原文：https://geometry.xyz/notebook/Hashing-to-the-secp256k1-Elliptic-Curve
作者：[weijie.eth](https://twitter.com/weijie_eth)
译者：[Kurt Pan](https://twitter.com/kurtpan666)
:::

## 引言
许多密码学协议，比如[可聚合分布式密钥生成](https://www.iacr.org/cryptodb/data/paper.php?pubkey=30862)和BLS签名方案，都需要用到**哈希到曲线**算法，确定性地将任意字节串转换成椭圆曲线上的一个点。这样的算法并非平凡，因为不仅仅是要产生有效的曲线点，而且还要以安全且高效的方式来产生。

这篇文章中，我将总结哈希到曲线函数的技术现状，重点是其在`secp256k1`椭圆曲线上的应用，以及一般的哈希到曲线算法背后的一些安全考虑和性能优化。

## 背景
在 [Geometry](https://geometry.xyz/) ，我们与[0xPARC](https://0xparc.org/) 和 [Personae Labs](https://personaelabs.org/) 的Aayush 和 Lakshman 合作开发了一个[产生唯一确定性nullifiers的签名方案](https://eprint.iacr.org/2022/1255)。该方案旨在与现有的以太坊钱包兼容，所以会使用到[secp256k1 曲线](https://en.bitcoin.it/wiki/Secp256k1) 上的密钥对。为产生一个签名，签名者需要导出一个椭圆曲线点，作为对消息和公钥的哈希到曲线函数的输出。

为最大限度地提高这个签名方案被广泛采用和标准化的机会，我们选择了一个哈希到曲线的密码套件[`secp256k1_XMD:SHA-256_SSWU_RO_`](https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-16.html#name-secp256k1_xmdsha-256_sswu_r)，它本身就是一组正在进行标准化的函数的一部分。是在提交给[互联网研究任务组（IRTF）](https://irtf.org/) 的标准草案[哈希到椭圆曲线](https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-16.html) 中定义的。注意在本文撰写时，该文档相对较新，尚未正式成为[IETF标准](https://www.ietf.org/standards/)。

在未来的文章中，我将详细介绍这个哈希到曲线函数的一个[circom实现](https://github.com/geometryresearch/secp256k1_hash_to_curve) ，这使得它可以应用于zk-SNARK电路中。

## 关于哈希到椭圆曲线
**哈希到椭圆曲线**（以下简称标准草案）提供了将任意字节串哈希到椭圆曲线的具体算法。它为各种椭圆曲线，如`secp256k1`、`P-256`和`BLS12-381`，定义了特定的密码套件--即一系列的常数和算法。虽然它只为这有限的一组椭圆曲线提供了密码套件，但如果读者需要，它也为如何为其他曲线构建安全的密码套件提供了一般指导。

标准草案定义了`hash_to_curve`函数如下：
1. 给定任意长输入消息`msg`，使用`hash_to_field`确定性地产生两个域元素`u[0]` 和 `u[1]`
2. 计算`Q0 = map_to_curve(u[0])`
3. 计算`Q1 = map_to_curve(u[1])`
4. 使用点加计算`R = Q0 + Q1`
5. 清除`R`的协因子并返回结果
### `hash_to_field`
`hash_to_field` 运行 `expand_message_xmd`， 对`msg`进行哈希并输出一个96字节的数组。输出 `u[0]` 是前48字节， `u[1`] 是后48字节。对于`expand_message_xmd`我将在另外的小节中详述；现在只需简单的认为是输出了一个输入的均匀随机哈希即可。
### `map_to_curve`

`map_to_curve`使用一个常数时间方法，给定一个域元素，总是能找到一个椭圆曲线上的点。根据曲线的类型和参数的不同，该方法有不同的变体。

该规范草案为**Montgomery曲线**规定了Elligator 2方法，为**twisted Edwards曲线**规定了twisted Edwards Elligator 2方法。对**Weierstrass曲线**，如`secp256k1`，有如下三种选择：

1. **Shallue-van de Woestijne (SW) 方法**，适用于任意椭圆曲线，但是最慢的。
2. **Simplified Shallue-van de Woestijne-Ulas (SSWU) 方法**，适用于定义为 $y^2=x^3+A x+B$ （其中 $A \neq 0,B \neq 0$）的曲线。
3. 应用在$A B$ 等于0的曲线的**Simplified SWU 方法** 。这是这三种方法中最高效的。

针对我们的目的，应用在$A B$ 等于0的曲线的Simplified SWU 方法是相关的，因为`secp256k1`曲线的定义中 $A=0$ 且 $B=7$，所以$A B=0$。

### `clear_cofactor`
这个函数将曲线上的一个点转换为素数阶子群中的一个点。要做到这一点，只需将该点与一个常数$h$（译者注：协因子cofactor）相乘。在`secp256k1`曲线的情况下，不需要做任何事情，因为这个曲线中$h$等于1。

## 安全考虑
任何哈希到曲线函数或其实现都应该具有特定的安全性质，以保持采用它的密码学协议的安全。否则，一个弱的哈希到曲线函数会使协议受到攻击。正如该标准草案所指出的，哈希到曲线函数不仅必须是抗碰撞的，而且不应暴露输出点的离散对数。

为了分析一个密码学协议的安全性，密码学家基于其组成部分的假设来写证明。这些理论上的假设可以被描述为模型。该标准草案的作者认为，他们的方法在所谓的[随机预言模型](https://link.springer.com/referenceworkentry/10.1007/978-1-4419-5906-5_220) （ROM）中是安全的。因此，如果设计正确，依靠这种哈希到曲线函数的协议也可以在ROM中证明是安全的。

### 随机预言模型

该标准草案的作者认为，他们的哈希到曲线算法在ROM中是安全的。这些函数通过两种方式实现这一点：确保算法通过哈希函数将输入信息转换为均匀随机的域元素，并确保哈希到曲线算法的输出曲线点在统计上是均匀的。

首先，`hash_to_field`过程依赖于一种将字节串扩展为均匀随机的字节串的方法。这个方法有两个变种：`expand_message_xof`和`expand_message_xmd`。

`expand_message_xof`依赖于一个哈希函数，它原生提供了一个所需长度的输出。由于这个哈希函数（推荐用SHAKE XOF类）在ROM下是可证明安全的，因此很容易证明`hash_to_field`函数在ROM下也是安全的。

`expand_message_xmd`则依赖于一个具有固定长度输出的哈希函数。虽然有些哈希函数与随机预言不可区分，或者说基于海绵的哈希函数，其内部函数可以证明是随机置换或随机变换，因此可以认为`expand_message_xmd`与随机预言不可区分，但有些哈希函数就不是这种情况，比如Merkle-Damgård哈希函数。

该标准草案引用了Coron等人在[CDMP05](https://cs.nyu.edu/~dodis/ps/merkle.pdf) 中的观点，认为像SHA这样的哈希函数所采用的增强Merkle-Damgård变换不满足以下安全性质：

> 当固定长度的构造组件被看作是一个随机预言或一个理想分组加密（ideal block-cipher）时，任意长度的哈希函数$H$一定会表现得像一个随机预言。

为了让`expand_message_xmd`在 ROM 中证明安全且使用像 `SHA256` 这样的 Merkle-Damgård 哈希函数，作者在 CDMP05 中（第12页）使用了一个名为 **HMAC** $^f$ 的构造。 这种构造的粗略描述（为简单起见跳过了后缀填充步骤）如下：
1. 令$k$ 为Merkle-Damgård哈希函数$\mathrm{MD}^f$ 所要求的输入字节个数，$m$为消息。
2. 令$m_0$ 为$k$个0的字节数组。
3. 令 $y^{\prime}=\mathrm{MD}^f\left(\left[m_0 \| m\right]\right)$ 其中 $\|$ 指代级联。
4. 返回 $\mathrm{MD}^f\left(\left[y^{\prime}\right]\right)$

回顾**长度扩展攻击**：当给定一个哈希值$h\left(m_a\right)$时，*即使不知道$m_a$的值*，敌手也能够通过平凡地实例化$h\left(m_a\right)$底层哈希的内部状态以导出$h\left(\left[m_a \| m_b\right]\right)$。这违背了随机预言模型的一个关键性质——即一个消息 $\left(m_b\right)$ 的哈希值不应该可以从另一个消息 $\left(m_a\right)$ 的哈希值中确定。

HMAC$^f$ 构造不受此问题的影响。 仅知道 $y^{\prime}$ 希望导出 $\operatorname{HMAC}^f([m \| x])$ 的敌手不太可能成功。 考虑敌手可能的尝试：

1. 得到 $a=\operatorname{HMAC}^f([m])$.
- 注意 $a$ 等价于 $\mathrm{MD}^f\left(\mathrm{MD}^f\left(\left[m_0 \| m\right]\right)\right)$.
2. 仅指导 $\mathrm{MD}^f$ 和 $y$，敌手想要导出 $b=\operatorname{HMAC}^f([m \| x])$.
- 注意 $b$ 等价于 $\operatorname{MD}^f\left(\operatorname{MD}^f\left(\left[m_0\|m\| x\right]\right)\right)$.
3. 敌手需要$\operatorname{MD}^f\left(\left[m_0 \| m\right]\right)$ 等于$m_0$以使其可以用$m_0$实例化$\mathrm{MD}^f$ 的内部状态，然后在$x$上处理$\mathrm{MD}^f$ 的其余部分以得到$\operatorname{MD}^f\left(\left[m_0\|m\| x\right]\right)$。
4. 然而， $\operatorname{MD}^f\left(\left[m_0 \| m\right]\right)$ 等于$m_0$是极不可能的。

因此，$\operatorname{HMAC}^f([m])$ 不会受到长度扩展攻击，因此更容易在 ROM 下被证明是安全的。

`expand_message_xmd` 实现了这种构造，通常称为[**基于哈希的消息认证码 (HMAC)**](https://en.wikipedia.org/wiki/HMAC)。 作为参考，请注意其实现遵循以下模式。 对使用 `SHA256` 并需要 96 字节输出的哈希到曲线密码套件，`expand_message_xmd` 大致定义如下：

1. 令 `Z_pad` 为 64 个零的字节数组（因为对于 SHA256，$k=64$）。 这类似于上述的 $m_0$。
2. `msg_prime` 构造为 `Z_pad`、消息和一些常量例如 `DST_prime`的级联。
3. 计算 `b_0 = SHA256 (msg_prime)`。 这类似于如上所述的 $y^{\prime}$。
4. 计算 `b_1 = SHA256 (b_0 || 1|| DST_prime )`。
5. 计算 `b_2 = SHA256 (strxor(b_0, b_1) || 2 || DST_prime)`。
6. 计算 `b_3 = SHA256 (strxor(b_0, b_2) || 3 || DST_prime)`。
7. 返回 `b_1 || b_2 || b_3`。

如上所述，在步骤 2 中添加 `Z_pad` 可以防止长度扩展攻击，该攻击可使敌手更容易影响 `b_1`、`b_2` 和 `b_3` 的值。

### 域分隔
读者可能会注意到上面 `expand_message_xmd` 算法中的 `DST_prime `常量，它编码了表示**域分隔标记 (DST)** 的字节串，后跟 DST 长度作为单个字节。 每个密码套件都有一个唯一的 DST，例如 `secp256k1_XMD:SHA-256_SSWU_RO_` 套件的 `QUUX-V01-CS02-with-secp256k1_XMD:SHA-256_SSWU_RO_`。
在 `expand_message_xmd` 中包含唯一` DST_prime` 的原因是为了确保其输出特定于唯一一个密码套件。 实际上，每个密码套件都可以理解为与独立的随机预言机一起运行，这是在随机预言机模型下被证明是安全的协议的[重要安全假设](https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-16.html#section-2.2.5)。

### 输出均匀性

在标准草案中，每条椭圆曲线都带有两个密码套件：一个执行**哈希到曲线**，另一个执行**编码到曲线**。两者的区别在于前者函数的输出在统计上比后者更均匀，但后者的效率更高。作者指出，安全的默认设置是使用哈希到曲线，除非有人确定在自己的密码协议中可以接受不均匀性。

哈希到曲线不同的原因在于它的实现。 哈希到曲线函数从输入消息中导出两个不同的椭圆曲线点（使用 `map_to_curve` 函数）并将它们相加。相比之下，编码到曲线函数只调用一次 `map_to_curve`。由于 `map_to_curve `的输出是非均匀的，因此编码到曲线的输出是非均匀的。但由于哈希到曲线对两个非均匀点进行了点加，因此输出是均匀的。作者引用了 [Brier 等人](https://eprint.iacr.org/2009/340.pdf) 的文章，证明情况确实如此。

### 常数时间实现

标准草案中哈希到曲线密码套件的一个重要安全性质就是可以*在常数时间内*计算。如果要哈希的消息需要保密的，则此性质至关重要。

拥有安全的常数时间哈希到曲线函数是重要的进展，因为之前关于哈希到曲线算法的许多工作都使用了**尝试-增量方法**，输入消息被转换为域元素，测试它是否是曲线中有效的 $x$ 坐标，如果不是，则递增并重复测试。

这种尝试-增量方法的缺点有两方面。首先，即使在 $n-x$ 次尝试中已经找到了有效点，也必须执行到特定次数 $n$。这是为了防止**侧信道时序攻击**。其次，总是存在 $n$ 不够大的可能性，因此必须使用新消息再次尝试。处理这些情况所需的额外复杂性可能会导致协议中出现安全漏洞的可能性更大，如在 WPA3 和 EAP-pwd 协议的实现中发现的 [Dragonblood 漏洞](https://eprint.iacr.org/2019/383) 中所见。

## 结论

在这篇文章中，我概述了**哈希到椭圆曲线**的作者提出的各种安全和性能考虑。 我相信一组设计良好且安全的哈希到曲线密码套件将极大地有益于密码学领域，因为这些函数是许多重要协议的核心。 为此，有必要对本标准草案进行更具建设性的审查。