为什么 Curve25519 不需要验证公钥

本来以为算法竞赛退役之后，可能没什么机会再碰数论相关内容了。没想到这么快数论就又找上我了（笑）这篇文章是我自己对 Curve25519 的学习和理解。俺数学功底薄弱，非常菜菜🥬，如有疏漏请指出！非常感谢数学迷和其他朋友在数学方面给我的指导

Curve25519 是一个基于椭圆曲线的 Diffie-Hellman(DH) 函数。基于椭圆曲线的密码学是当下最为安全和先进的公私钥加密系统。

通常椭圆曲线加密算法需要对公钥进行验证，以防止小子群攻击和无效曲线攻击。但是 Curve25519 却不需要对公钥进行验证。在 cr.yp.to 上有如下记录：

How do I validate Curve25519 public keys?

Don’t. The Curve25519 function was carefully designed to allow all 32-byte strings as Diffie-Hellman public keys.

这是为什么呢？

TL;DR 对公钥进行验证的原因是对应的点可能并没有落在椭圆曲线上，而是落在曲线的二次扭曲上。如果二次扭曲是不安全的，会使计算出的共享密钥“有问题”从而泄露信息。而 Curve25519 曲线的参数经过精心挑选，对应的二次扭曲也是安全的。

看不懂？打个比方吧。 你是奇异博士，你挑选了一块你战无不胜的空间领域，但是并在其他空间领域里都是如此。每个空间都附带一个镜像空间 （也就是二次扭曲），虽然你在本体空间战无不胜，但镜像空间内并不一定。本来你要费力辨别狡猾的邪恶魔法师是否是在镜像空间内向你发起挑战的，如果是那么你要拒绝挑战 （检查公钥）。后来你找到了一个空间，在这个空间和这个空间的镜像空间里你都百战百胜。于是便可不费力辨别邪恶魔法师是在哪向你发出挑战的了 （Curve25519 的设计）。

还看不懂？那要不直接看数学原理？

在开始之前，不妨先简单介绍一下椭圆曲线算法大概是如何进行的：

椭圆曲线算法会事先选择一个素数 $q$，把所有运算转换为在 $[0, q-1]$ 内的模 $q$ 整数运算。事先规定一条椭圆曲线和这条曲线上的一个点 $G$ 作为基点。算法会选择一个随机整数 $k$ 作为私钥；并计算值 $P=k*G$ 作为公钥，之后便是使用 $DH$ 函数根据自己的私钥和对方的公钥计算出共享密钥了。至于如何定义两个点的加法和使用快速幂的思想计算点的标量乘法的这里就不过多赘述了，相关的介绍应该有很多了。

在一条曲线上如果对一个点重复的加自身，最终会兜回这个点自身形成一个循环。这个循环的长度再减一叫做这个点的阶。

椭圆曲线在设计的时候都会确保基点 $G$ 的阶有一个足够大的素因子的原因是为了防止小子群攻击。如果 $G$ 的阶可以被分解为好多个小素数的乘积，那主动攻击者可以利用这个性质缩小共享密钥可能的取值范围，并且暴力尝试所有可能的共享密钥之后得出对方私钥的一部分信息，然后在多次探测后使用中国剩余定理求解出私钥。这种情况同样可能会发生在攻击者发送了一个没有落在规定曲线上的“假”公钥而没有对公钥进行验证的情况下。

对于 Curve25519 这类采用 $P$ 点的横坐标 $x$ 作为公钥的协议来说，要验证公钥是否有效就需要验证椭圆曲线 $y^2 = x^3 + Ax^2 + Bx + C\pmod{q}$ 是否有解。$x$ 是已知的，所以方程右侧的值是固定的，那么判断是否有解其实就是判断是否存在一个 $y$ 使得 $y^2$ 的值在取模意义下等于方程右侧的值 ———— 二次剩余。

椭圆曲线等式右侧的值 $f(x) = x^3 + Ax^2 + Bx + C$ 算出来要么是一个二次剩余，要么不是二次剩余/*废话*/，也就是二次非剩余。

由于两个二次非剩余相除可以得到一个二次剩余，所以虽然在右侧是二次非剩余的情况下点并不落在椭圆曲线上，但是方程 $y^2 = (x^3 + Ax^2 + Bx + C) / d$ 却会有解，其中 $d$ 是模 $q$ 意义下的一个二次非剩余。把 $d$ 乘在等式左侧可以得到：$dy^2 = x^3 + Ax^2 + Bx + C$。
一通操作之后会发现这个方程可以写为 $y^2 = x^3 + dAx^2 + d^2Bx + d^3C$，也符合椭圆曲线的形式。

两个二次非剩余相除可以得到一个二次剩余？

证明方法应该有很多，比如使用欧拉准则：

$d$ 是模 $p$ 的二次剩余当且仅当：
$d^{\frac{p-1}{2}} \equiv 1 \pmod{p}$

$d$ 是模 $p$ 的非二次剩余当且仅当：
$d^{\frac{p-1}{2}} \equiv -1 \pmod{p}$

不难推出两个二次非剩余相除可以得到一个二次剩余

一通操作？咋操作的？

将方程左右两侧同时乘以 $d^3$，得到：$d^4y^2 = d^3x^3 + d^3Ax^2 + d^3Bx + d^3C$
进行换元：$y’ = d^2y, x’=dx$，得到：$y’^2 = x’^3 + dAx’^2 + d^3Bx’ + d^3C$
令 $y = y’, x = x’$，得到：$y^2 = x^3 + dAx^2 + d^2Bx + d^3C$

举一个实际的栗子🌰，比如我们有一条椭圆曲线 $y^2 = x^3 + 3x^2 +2\pmod{7}$，在模 $7$ 意义下 $1, 4, 2$ （分别是 $1^2\pmod{7}, 2^2\pmod{7}, 3^2\pmod{7}$）是二次剩余，剩下的 $3, 5, 6$ 是二次非剩余。

我们可以随意选取一个二次非剩余（假设是 $5$）乘在等式左侧，就可以得到一条椭圆曲线的二次扭曲：

$5y^2 = x^3 + 3x^2 +2\pmod{7}$

$d$ 选取哪一个二次非剩余没有影响吗？

选取不同的二次剩余 $d$ 得到的式子经过一个简单的换元就一样了，见解答

如果公钥对应的点落在了椭圆曲线之外，那么这个公钥实际上对应着来自二次扭曲上的一个点。而二次扭曲如果是不安全的，（也就是阶可以被分解为多个小素数）就使得攻击者仍然可以进行前面提到过的小子群攻击了。

如果…二次扭曲也是安全的呢？

Curve25519 正是这么设计的。Curve25519 曲线本身和 Curve25519 所对应的二次扭曲都是安全的，哪怕攻击者使用了一个落在曲线外的 $x$ 坐标作为公钥，这个点也是落在同样保证安全的二次扭曲上的，攻击者仍然没有办法缩小计算出的共享密钥的范围。

具体而言...

具体而言 Curve25519 曲线本身上的点数是 $8 * p1$，其中 $p1$ 是素数 $2^{252} + 27742317777372353535851937790883648493$
Curve25519 曲线的二次扭曲上的点数是 $4 * p2$，其中 $p2$ 是素数 $2^{253} - 55484635554744707071703875581767296995$

这里没有选取点数本身是素数的曲线，原因是 Curve25519 使用的是形式为蒙哥马利的椭圆曲线，这类椭圆曲线更易于计算，但是这类曲线阶数只能是 $4$ 的倍数。
这也是 Curve25519 在进行生成私钥的时候抹除了最低三位的原因

这正是 Curve25519 在 Diff-Hellman 中不需要验证公钥的原因。有关 Curve25519 在设计时的更多考量，可以翻阅 Curve25519 的论文