哈希到椭圆曲线 | Codeboy's Blog

形式陈述

哈希到曲线把字节串 $m$ 确定地映为一个椭圆曲线点。输入不是点的编码：普通点反序列化会拒绝许多字节串，这里则要为每条合法消息给出结果。本页固定RFC9380的 P256_XMD:SHA-256_SSWU_RO_ 套件，并用完整的坐标计算复现其公开向量。[1]

固定坐标域和目标群

坐标在有限域 $\mathbb F_p$ 中，曲线为 $y^2=g(x)=x^3+Ax+B$ ，其中

p=2^{256}-2^{224}+2^{192}+2^{96}-1,\qquad A=-3,

$B$ 的十六进制值是

text

5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b

P256整个点群的阶为素数

text

q = ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551

这里 $p$ 是坐标模数， $q$ 是标量模数；求坐标逆元用 $p$ ，点的重复加法次数按 $q$ 约简。套件余因子为1，所以最终不再乘额外余因子。换一条曲线时，不能保留这一结论。

接口 hash_curve(m,DST) 接受字节串和非空、至多255字节的用途标签DST，返回点 $P_m$ 及中间量。参考程序只实现这个短DST接口；RFC还规定了长DST处理，未在这里隐式截断。输出可能是群单位元 $O$ ；需要非单位元的上层协议必须检查。

第一步：得到两个域元素

取 $L=48$ 。这里用密码学哈希函数 SHA-256 实现XMD扩展；SHA-256的输出是32字节，输入块是64字节。要产生96字节，令

D'=DST\Vert\operatorname{I2OSP}(|DST|,1),

b_0=\operatorname{SHA256}(0^{64\text{字节}}\Vert m\Vert \operatorname{I2OSP}(96,2)\Vert 00\Vert D'),

b_1=\operatorname{SHA256}(b_0\Vert01\Vert D'),\qquad b_i=\operatorname{SHA256}((b_0\oplus b_{i-1})\Vert\operatorname{I2OSP}(i,1)\Vert D') \quad(i=2,3).

数字前缀均为定长大端字节，00/01指一个字节。把 $b_1\Vert b_2\Vert b_3$ 分成两个48字节段，以大端整数解释后分别模 $p$ ，得到 $u_0,u_1$ 。这就是此套件的 hash_to_field(m,2)；它还没有产生曲线点。

第二步：把一个域元素映成点

固定 $Z=-10\pmod p$ 。RFC要求 $Z$ 非平方、 $Z\ne-1$ 、 $g(X)-Z$ 不可约，以及 $g(B/(ZA))$ 为平方；P256套件给出的常量满足这些条件。SSWU接收 $u\in\mathbb F_p$ ，令 $t=Zu^2$ ，按以下顺序计算：

若 $t^2+t\ne0$ ，取 $x_1=-\dfrac BA\left(1+\dfrac1{t^2+t}\right)$
若 $t^2+t=0$ ，改取 $x_1=B/(ZA)$ ，不对零求逆
令 $x_2=tx_1$ ；若 $g(x_1)$ 是平方，选 $x=x_1$ ，否则选 $x=x_2$
取平方根 $y$ ，再在 $y,-y$ 中选择整数代表奇偶性与 $u$ 相同者

由于 $p\equiv3\pmod4$ ，对平方 $v$ 可用 $v^{(p+1)/4}$ 求根，随后仍检查 $y^2=v$ 。P256群阶为奇素数，曲线上没有 $y=0$ 的非单位二阶点，因而这里的符号选择没有零根歧义。

最后分别计算 $Q_0=\operatorname{SSWU}(u_0)$ 、 $Q_1=\operatorname{SSWU}(u_1)$ ，输出

\boxed{P_m=Q_0+Q_1.}

点加法沿用曲线群公式，包含两点互为逆元时输出 $O$ 的分支。只映射一个域元素是另一种非均匀编码，不能省去第二次映射后仍称为上述RO套件。

直觉

直接把哈希字节当作横坐标，未必能找到纵坐标，因为 $g(x)$ 未必是平方。SSWU预先安排两个相关横坐标：一般分支中，一个候选失败时，另一个就能成功。它不靠不断尝试下一个横坐标，因而计算步骤有固定的代数结构。

两次映射再相加承担另一项责任：单个映射的像和原像数通常不均匀，点“在曲线上”只证明代数合法。让整条构造适用于理想群随机预言机，需要额外的分布与模拟论证。RFC称之为indifferentiability，即相对理想随机预言机的不可区分模拟性质；它不是微积分中的可微性。[1,2]

字节经过96字节扩展、两个48字节域元素、两次SSWU映射，最后相加为P256点 — P256哈希到曲线的三个阶段

例子与边界

从空串走到一个规范压缩点

采用RFC9380 Appendix J.1.1的标签

text

QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_RO_

空消息产生的两个域元素为

text

u0 = ad5342c66a6dd0ff080df1da0ea1c04b96e0330dd89406465eeba11582515009
u1 = 8c0f1d43204bd6f6ea70ae8013070a1518b43873bcd850aafa0a9e220e2eea5a

两次映射点和最终点的压缩编码为

text

Q0 = 03ab640a12220d3ff283510ff3f4b1953d09fad35795140b1c5d64f313967934d5
Q1 = 0251cce63c50d972a6e51c61334f0f4875c9ac1cd2d3238412f84e31da7d980ef5
P  = 032c15230b26dbc6fc9a37051158c95b79656e17a1a920b11394ca91c44247d3e4

编码的首字节 02/03 表示纵坐标偶/奇，余下32字节是横坐标；它不是对点再次做哈希。把消息换为ASCII的 abc，最终压缩点为

text

020bb8b87485551aa43ed54f009230450b492fead5f1cc91658775dac4a3388a0f

参考程序同时打印两份域元素、两份映射点与最终点。逐层比较能区分“扩展字节错”“模数错”“符号错”和“点加法错”，而不仅看到最终摘要不同。

零输入也需要合法输出

SSWU的 $u=0$ 使 $t^2+t=0$ ，必须用 $B/(ZA)$ 。对P256还存在 $u^2=-1/Z$ 的两个非零解，它们同样触发例外；只写 if u == 0 会漏掉这两种输入。程序直接检查分母，并用这三个值作回归。

哈希到域的384位整数按 $p$ 约简，哈希到标量则可以把目标域换为 $\mathbb F_q$ 。二者都合法，但模数与用途不同。把OPRF的挑战标量误用 $p$ 约简，不能靠后面再检查点是否合法纠正。

另一个有害替代是先公开算标量 $h(m)$ ，再输出 $h(m)G$ 。它确实是曲线点，却向所有人暴露其相对 $G$ 的离散对数。不经意伪随机函数的迁移任务会利用这一关系，在一次服务器求值后算出全部新输入的值。

推论与应用

两个候选为何至少有一个可开平方

在非例外分支， $t=Zu^2\ne0$ 是非平方，且 $t\ne-1$ 。把 $x=x_1$ 代入可直接展开：

g(tx)-t^3g(x) =(1-t)\bigl(Axt(1+t)+B(1+t+t^2)\bigr)=0.

最后一步恰好使用 $x=-\frac BA\frac{t^2+t+1}{t^2+t}$ 。所以 $g(x_2)=t^3g(x_1)$ 。若 $g(x_1)=0$ ，它本身就是平方；否则乘非平方 $t^3$ 会交换平方与非平方两类，至少一个候选有根。例外分支另由常量条件保证 $g(B/(ZA))$ 是平方。两条理由覆盖全部 $u$ ，并没有把不可求逆的点藏进一般公式。[2]

48字节控制的是什么偏差

暂把一段48字节视为均匀整数 $U\in\{0,\ldots,M-1\}$ ， $M=2^{384}$ 。写 $M=ap+r$ ， $0\le r<p$ 。模 $p$ 后，前 $r$ 个余数各有 $a+1$ 个原像，其余各有 $a$ 个。由此与均匀域元素的总变差距离精确为

\Delta=\frac{r(p-r)}{pM}\le\frac p{4M}<2^{-130}.

这解释为什么不只取256位再约简。此计算的前提是扩展字节均匀；现实SHA-256是固定确定函数，不能把这项理想分布计算当作其无条件安全证明。完整哈希到曲线的模拟性质按RFC的哈希模型和映射条件使用，点加法闭包证明也不能替代它。

执行代价和终点任务

固定P256时，扩展96字节调用4次SHA-256，其中第一次读取整个消息；两次映射各用常数次模逆和模幂，再做一次点加法。若消息有 $n$ 字节，参考程序的字节处理为 $O(n+1)$ ，另加这些域运算，临时拼接占 $O(n+1)$ 字节。若讨论可变位宽 $b$ ，模幂需 $O(b)$ 次模乘，不能把256位常量界当作任意安全参数下的常数时间。

终点任务：复算空串的三个压缩点；把DST换成另一非空标签并报告两个新域元素；找到 $u^2=-1/Z$ 的两根，确认都走例外分支。最后只保留 $Q_0$ ，说明新程序仍输出曲线点，却已经改变了哪个公开接口。共同的盲求值与公钥核验练习接着使用这条完整管线。

参考资料

Armando Faz-Hernandez等，RFC9380: Hashing to Elliptic Curves，2023-08，§§2.2.3–3、5.2–5.3.1、6.6.2、8.2、10.1及Appendix J.1.1：编码与反序列化、P256套件、异常值和公开向量。
Éric Brier等，Efficient Indifferentiable Hashing into Ordinary Elliptic Curves，CRYPTO2010扩展版，§7 Proposition7，PDF pp.15–16：消去三次项得到两个相关候选；RFC所用Z及符号约定以[1]为准。

形式陈述 ​

固定坐标域和目标群 ​

第一步：得到两个域元素 ​

第二步：把一个域元素映成点 ​

从空串走到一个规范压缩点 ​

零输入也需要合法输出 ​

两个候选为何至少有一个可开平方 ​

48字节控制的是什么偏差 ​

执行代价和终点任务 ​

反向链接

形式陈述

固定坐标域和目标群

第一步：得到两个域元素

第二步：把一个域元素映成点

从空串走到一个规范压缩点

零输入也需要合法输出

两个候选为何至少有一个可开平方

48字节控制的是什么偏差

执行代价和终点任务