速度需求：椭圆曲线章节

介绍

椭圆曲线 (EC) 作为密码学工具已被广泛接受。与其他方法（如 RSA）相比，它们具有多个优势，以更短的密钥提供同等安全级别（例如，EC 密码学中的 228 位密钥与 2300 位 RSA 密钥一样好）。这是一个优势，因为越来越多的密码学是在智能手机上完成的，而智能手机的功能不如计算机强大。这些曲线由某个 域（例如，实数）上的方程 $y^2=x^3+ax+b$ 定义。它们的形状取决于 $a$ 和 $b$，但它们或多或少看起来像下图：

在密码学中，我们对实数上定义的曲线不感兴趣。我们使用一些有限域 $F_p$（即，具有有限数量元素的集合，例如 53、101 或 $2^{255}-19$）来处理它们，因为这为我们提供了一个数学结构（一个有限群），这非常方便。曲线看起来像分散的点，在有限域上没有明显的模式：

当通过 SSH 连接到服务器或证明比特币中的所有权时，椭圆曲线在密钥交换中起着作用。它们也出现在执行数字签名、生成随机数（尽管存在一些问题）时，甚至对于分解数字也很有用（Lenstra 算法）。例如，在椭圆曲线数字签名算法 (ECDSA) 中，你有以下步骤（如果你现在不理解所有术语，请不要担心，我们稍后会逐一介绍）：

1. 计算 $E=hash(message)$，其中 hash 是一个安全的 哈希函数。
2. 取 $Z$ 等于 $E$ 最左边的 $n$ 位，其中 $n$ 是群的阶数（即，构成群的元素的数量）。
3. 选择一个密码学上安全的随机数 $k$（永远不要使用相同的 $k$ 两次，否则你会泄露你的密钥）。
4. 计算 $(x_1,y_1)=kg$，其中 $g$ 是群的生成元。
5. 令 $r=x_1$。
6. 计算 $s=k^{-1}(Z+r \cdot sk) \pmod{n}$，其中 $sk$ 是私钥。
7. 签名是二元组 $(r,s)$。

在此示例中，我们必须在步骤 4 中评估曲线上的加法才能到达点 $(x_1,y_1)$，这给了我们 $r$。通常，$k$ 是一个很大的数字（例如，有 256 位），因此该操作可能非常昂贵。此外，如果实现不正确，椭圆曲线密码学可能会成为侧信道攻击的目标，例如定时和缓存攻击。一些椭圆曲线具有允许恒定时间实现的属性，这使得它们能够抵抗这些策略。

椭圆曲线也出现在 zk-SNARK（零知识简洁非交互式知识论证；我们将在另一篇文章中寻找 SNARK）中，以提供同态隐藏。这个词听起来很重要，但其背后的想法很简单。假设有两个变量 $x$ 和 $y$，你想要（或需要）知道 $x+y$。问题是，你不知道它们的值，但你有它们的加密形式 $E(x)$ 和 $E(y)$。如果你有同态隐藏，你可以计算 $E(x+y)=E(x) \times E(y)$，其中 $\times$ 是加密变量上的运算。因此，即使你不知道变量本身，也可以对它们执行数学运算（幸运的是，这正是你所需要的）。这在实践中是通过两条椭圆曲线来实现的（称为配对；并非所有椭圆曲线都如此善于交际或与其他曲线相处融洽）。为了很好地匹配，我们需要尽可能快地执行操作（除其他外）。一个简单的例子是指数函数，$f:R \rightarrow R^+/f(x)=\exp(x)$。如果你有 $x=2.303$，$\exp(2.303) \approx 10$，$y=3$，$\exp(3) \approx 20.09$，那么 $\exp(x+y)=\exp(x)\exp(y)=10 \times 20.09=200.9$，这等于 $\exp(5.303)$ 和 $x+y=5.303$。当然，在这种情况下，很容易返回并知道确切的数字 $x$、$y$ 和 $x+y$；对于椭圆曲线，由于其特殊的群结构，这非常困难。

为了能够使用椭圆曲线，我们需要定义一个涉及曲线上点的运算。我们可以使用割线和切线构造来做到这一点：给定曲线上的两个点，我们可以画一条连接它们的线；这条线与曲线相交于第三个点，我们将其绕 $x$ 轴反射以获得总和（记住在实数上定义的曲线的图片）。公式是

$s=\frac{y_2-y_1}{x_2-x_1}$

$x_3=s^2-x_1-x_2$

$y_3=s(x_1-x_3)-y_1$

有一些特殊情况，例如当我们想要将一个点加到自身时（我们称之为“加倍”）。为了使工作正常进行，我们需要添加一个特殊的点 $O$，即无穷远点。曲线与运算一起，形成一个有限循环群。简单来说，每次我们将两个点相加时，我们都会得到第三个点，该点属于曲线（它在运算下是闭合的）。我们还有一个单位元（无穷远点，$P+O$），并且每个点 $P$ 都有一个逆元 $P'$，使得 $P+P'=O$。此外，群的元素可以通过重复将一个点 $g$ (生成元) 加到自身来生成。换句话说，对于群中的 $P$，存在一些 $k$ 使得 $kg=P$。如果给定 $k$，我们可以快速计算 $P$，但以相反的方式执行操作（即，给定 $P$，找到 $k$）可能非常困难（这被称为离散对数问题），我们在上一段中使用了这个想法。

所有这些计算都是使用有限域 $F_p$ 的运算完成的。我们看到，在每个加法步骤中，我们都必须计算直线的斜率，这涉及到有限域元素的除法。这可以重写为 $s=(x_2-x_1)^{-1}(y_2-y_1)$，其中 $(x_2-x_1)^{-1}=b$ 是 $x_2-x_1$ 的乘法逆元。以更简单的形式，$b(x_2-x_1) \equiv 1 \pmod{p}$ (当我们写 $a \equiv b \pmod{p}$ 时，我们说存在一些整数 $q$ 使得 $a=pq+b$。可读作 $a$ 与 $b$ 模 $p$ 同余）。计算逆元是可能的，但比乘法昂贵得多。数论中有一个结果称为 费马小定理，它告诉我们，如果 $a$ 和 $p$ 除了 1 之外没有公约数（我们说 $a$ 和 $p$ 互质），则 $a^{p-1} \equiv 1 \pmod{p}$。我们可以用不同的方式写这个，

$a^{p-2}a \equiv 1 \pmod{p}$

我们看到 $b=a^{p-2}$（我们可以使事情变得简单，然后将 $b$ 减少到 $a^{p-2} \pmod{p}$）。因此，要获得乘法逆元，我们必须执行多次乘法。（有时它要容易得多。让我们取 $p=5$，我们尝试找到 $4^{-1}$。我们可以看到，如果我们做 $4 \times 4=16 \equiv 1 \pmod{5}$，那么 $4^{-1}=4$。这很奇怪，但我们必须记住，有限域上的运算具有不同的行为）。事实上，$p-1$ 给出了我们必须应用于域元素 $a$ 才能获得其逆元的幂 $n$ 的上限，即 $a^n \equiv 1 \pmod{p}$。我们将满足 $a^n \equiv 1 \pmod{p}$ 的最小（正）指数 $n$ 称为元素的阶。拉格朗日定理 表明阶 $n$ 整除 $p-1$。例如，取 $p=7$，因此 $p-1=6$。我们看到 $4^3=64 \equiv 1 \pmod{7}$，因此 $4^2 \equiv 2 \pmod{7}$ 是 $4$ 的逆元（$2 \times 4=8 \equiv 1 \pmod{7}$）。同样，$2^3 \equiv 1 \pmod{7}$。对于 $3$，$3^6 \equiv 1 \pmod{7}$ 和 $3^5 \equiv 5 \pmod{7}$，我们也有 $5^6 \equiv 1 \pmod{7}$。因此，我们看到阶 $n$ 是 $p-1=6$ 的约数。

因此，即使椭圆曲线上点加法的方程看起来非常简单，但它们涉及许多计算，这些计算可能非常昂贵。如果我们每次想要添加两个点时，都必须找到模一个大素数的乘法逆元，那么我们就会发现我们付出了很高的代价。我们可以执行一些技巧，例如转换曲线，以获得很大的速度或避免一些其他问题，例如侧信道攻击。

如果你是不愿意支付寻找逆元的成本并节省一些时间，或者只是为了速度而喜欢速度的人，那么下一节适合你。

射影坐标

如果我们将自己从漂亮的二维空间转移到三维空间，我们可以免于昂贵的求逆运算。这是由 Moebius 引入的，它还有助于我们正确地表示无穷远点。我们可以将椭圆曲线上的点 $(x,y)$ 映射到射影空间 $(X,Y,Z)$ 中的点，如 $(x,y) \rightarrow (X=x,Y=y,Z=1)$ 和 $O \rightarrow (0,1,0)$。我们可以使用变换 $(X,Y,Z) \rightarrow (x=X/Z,y=Y/Z)$ 返回，无穷远点除外，它没有定义。我们可以用下图来可视化这个过程，图中我们从椭圆曲线上取三个点并将它们转换为 3-d。

我们可以将其视为将我们的 2-d 点转换为穿过 3-d 空间原点的线。例如，2-d 中的点 $(x_1,y_1)$ 转换为线 $(\mu x_1,\mu y_1,\mu)$，其中 $\mu$ 是域中的一个元素。因此，如果我们可以找到 $\eta$ 使得 $(\eta X_1,\eta Y_1,\eta Z_1)=(X_2,Y_2,Z_2)$，则两个点 $P_1=(X_1,Y_1,Z_1)$ 和 $P_2=(X_2,Y_2,Z_2)$ 在 2-d 中是相同的（更准确地说，是同余的）。这些线不包含原点 $(0,0,0)$。通常将射影空间中的点写为 $(X:Y:Z)$，而不是 $(X,Y,Z)$。在我们的图中，点 A（黄色）被映射到点 D（它上面的红色）。所有位于穿过原点和 D 的同一条直线上的点（粉色虚线）都被认为等价于 D。同样，点 B（蓝色）被映射到点 F（浅蓝色），并且浅绿色虚线上方（原点除外）的所有点都等价于 F。当我们在这个空间中添加点时，分量 $(X,Y,Z)$ 将会改变，但我们可以通过沿着穿过原点的直线重新追踪我们的步骤到 $Z=1$ 来返回到属于曲线的点。为什么要走这么远？我们很快就会看到，我们在每个加法步骤都避免了求逆，并且只在找到 2-d 中的点时才进行一次求逆（例如，当我们需要在 ECDSA 中找到 $r=x_1$ 时）。当然，如果我们必须做 $P=2g$，我们什么也没得到，但如果我们必须执行 $P=kg$，其中 $k$ 的阶数为 256 位，我们就节省了许多昂贵的求逆。

将替换代入椭圆曲线方程

$(\frac{Y}{Z})^2=(\frac{X}{Z})^3+a(\frac{X}{Z})+b$

我们可以乘以 $Z^3$ 并得到方程

$ZY^2=X^3+aZ^2+bZ^3$

如果我们想在射影空间中将 $P$ 和 $Q$ 相加得到 $R=P+Q$，我们可以使用公式：

$Z_R=Z_P Z_Q(X_P Z_Q-X_Q Z_P)^3$

$X_R=(X_P Z_Q-X_Q Z_P)(Z_Q Z_P(Y_P Z_Q-Y_Q Z_P)^2-(X_P Z_Q-X_Q Z_P)^2(X_P Z_Q+X_Q Z_P))$

$Y_R=Z_P Z_Q(X_Q Y_P-X_P Y_Q)(X_P Z_Q-X_Q Z_P)^2-(Y_P Z_Q-Y_Q Z_P)A$

$A=Z_P Z_Q(Y_P Z_Q-Y_Q Z_P)^2-(X_P Z_Q+X_Q Z_P)(X_P Z_Q-X_Q Z_P)^2$.

这看起来比二维 (2-d) 空间的简单公式更复杂和困难。但是，我们不必计算任何逆元！要获得总和，我们必须执行 12 次乘法和 2 次平方。在 2-d 中，我们有 2 次乘法、一次平方和一次求逆。求逆可能比乘法昂贵 20 倍或更多，因此我们至少节省了 10 次乘法（一些作者说求逆比乘法贵 80 倍左右）。

某些曲线的速度甚至可以更快。如果 $x^3+ax+b$ 在 $F_p$ 中有一个解，我们可以使用等效的 Jacobi 四次曲线 $v^2=a'u^4+du^2+1$，其中 $a'$ 和 $d$ 取决于根。我们可以使用 $u=U/W$ 和 $v=V/W^2$ 将曲线 $(u,v)$ 转换为 3-d 空间 $(U,V,W)$，并得到方程

$V^2=a'U^4+dU^2W^2+W^4$

如果我们想在这些坐标中求和 $P_3=P_1+P_2$，我们有：

$U_3=U_1 W_1 V_2+U_2 W_2 V_1$

$V_3=((W_1 W_2)^2+a'(U_1 U_2)^2)(V_1 V_2+dU_1 U_2 W_1 W_2)+2a'U_1 U_2 W_1 W_2(U_1^2 W_2^2+U_2^2 W_1^2)$

$W_3=(W_1 W_2)^2-a'(U_1 U_2)^2$

这些使我们能够将加法成本进一步降低到 6 次乘法和 4 次平方。其他具有快速实现的模型是 Edwards 曲线和 Montgomery 曲线，它们具有一些最快的实现。

Montgomery 曲线满足以下方程

$By^2=x^3+Ax^2+x$

其中 $B(A^2-4) \neq 0$。可以通过进行一些变换将此表达式转换为 Weierstrass 形式。如果我们取 $(x,y)$ 并将其映射到由 $(x,y) \rightarrow (x/B+A/3B,y/B)$ 给定的 $(x',y')$，我们得到

$y^2=x^3+(\frac{3-A^2}{3B^2})x+\frac{2A^3-9A}{27B^3}$

但是，将 Weierstrass 曲线转换为 Montgomery 曲线并非总是可能的。群的阶数必须能被 4 整除，并且 $x^3+ax+b=0$ 必须有解。

Montgomery 曲线也可以与 twisted Edwards 曲线相关联，twisted Edwards 曲线遵循以下方程

$ax^2+y^2=1+dx^2y^2$

参数通过 $A=2(a+d)/(a-d)$ 和 $B=4/(a-d)$ 相关。我们说这两条曲线是双有理等价的。例如，著名的 Edwards 曲线 25519，其中 $p=2^{255}-19$，与 Montgomery 曲线 $t^2=u^3+486662u^2+u$ (双有理) 等价。映射是

$(x,y)=(\sqrt{-486664}u/t,(u-1)/(u+1))$

$(u,t)=((1+y)/(1-y),\sqrt{-486664}(1+y)/(x(1-y)))$

Montgomery 曲线具有一些有趣的特性，这些特性有利于恒定时间实现。我们可以只使用 $x$ 分量在射影坐标中工作，并使用变换 $x=X/Z$。加倍一个点采用简单的形式：

$4R=(X_1+Z_1)^2-(X_1-Z_1)^2$

$X_2=(X_1+Z_1)^2(X_1-Z_1)^2$

$Z_2=R((X_1-Z_1)^2+((A+2)/4)R)$

Twisted Edwards 曲线也有其优点。点加法和加倍的表达式相同。给定 $P_1=(x_1,y_1)$，$P_2=(x_2,y_2)$，我们得到

$x_3=\frac{x_1y_2+x_2y_1}{1+dx_1x_2y_1y_2}$

$y_3=\frac{y_1y_2-ax_1x_2}{1-dx_1x_2y_1y_2}$

如果我们令 $x_1=x_2$ 和 $y_1=y_2$，我们得到点加倍的表达式。有几种加速计算的替代方法，例如射影坐标、倒置坐标或扩展坐标。

还有一些其他技巧可以添加和乘椭圆曲线上的点，例如 Gallant、Lambert 和 Vanstone (GLV) 的技术，以及 Galbraith、Lin 和 Scott (GLS) 推广的技术。

总结

椭圆曲线在密码学中得到了广泛的接受，因为它们以较短的密钥长度提供了良好的安全级别，并允许比 RSA 等其他方法更快的实现。这使得智能手机和其他功能较弱的设备能够以快速可靠的方式执行密码操作。

使用割线和切线的方法，我们可以生成有限循环群；在应用中，我们通常对计算 $kg$ 感兴趣，其中 $k$ 是一个整数，$g$ 是椭圆曲线上的一个点。主要的缺点是我们需要找到域元素的乘法逆元，这涉及到很多乘法。

我们可以通过执行曲线之间的变换（例如，将 Weierstrass 曲线转换为 Montgomery 形式）并使用射影坐标来提高这些计算的速度。通过这种方式，我们避免了在每一步都计算乘法逆元，但代价是一些额外的乘法（这种额外的成本通常可以忽略不计，与求逆的总成本相比）。还有更先进的技术可以让我们从一个点跳到非常远的点，例如使用 GLS。

• 原文链接： blog.lambdaclass.com/nee...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～