密码学/椭圆曲线

椭圆曲线密码学是一种依赖于称为“椭圆曲线”和“有限域”的数学结构的密码学。椭圆曲线是形如$y^{2}=x^{3}+ax+b$的关系，其中$a$ 和 $b$ 是曲线的预设参数，而 $x$ 和 $y$ 是坐标。任何满足该关系的$(x,y)$ 对都被认为是椭圆曲线上的点。在椭圆曲线点上，可以定义一个称为“加法”的操作，如下所示

要添加两个点$P$ 和 $Q$，通过它们画一条线，找到该线穿过曲线的第三个点；称之为$R$。如果$P$ 和 $Q$ 具有相同的 x 坐标，则连接它们的线将是垂直的，并且 R 将不存在，因此在这种情况下，我们将 $P+Q$ 称为“无穷远点”。无穷远点加到任何其他点都是该点本身，因此可以将无穷远点视为数字零的椭圆曲线点类似物。否则，从$R$ 处画一条垂直线到曲线另一侧的相同 x 坐标上的点。该点定义为 $P+Q$。要计算$P+P$，而是取曲线在$P$ 处的切线，将其延伸到$R$，并取垂直对面的点作为答案，就像在$P+Q$ 案例中一样。

由于椭圆曲线是数学函数，我们可以使用高中代数和微积分的工具来推导出$P+Q$和$P+P$的公式。对于$P+Q$，公式为

$m={\frac {P_{y}-Q_{y}}{P_{x}-Q_{x}}}$

$(P+Q)_{x}=m^{2}-P_{x}-Q_{x}$

$(P+Q)_{y}=P_{y}+m(R_{x}-P_{x})$


对于 P+P

$m={\frac {3P_{x}^{2}+a}{2P_{y}}}$
$(P+P)_{x}=m^{2}-2*P_{x}$

$(P+P)_{y}=P_{y}+m(R_{x}-P_{x})$

请注意，两种情况下算法都是相同的：首先我们在$P$处找到斜率，然后我们得到答案的 x 坐标，然后我们使用斜率-点公式得到 y 坐标。然而，从这些公式中，我们得到一个非常令人惊讶的结果：$(A+B)+C=A+(B+C)$，无论$A$，$B$ 和 $C$ 是否不同或相同。此外，从视觉定义中可以明显看出$A+B=B+A$。这些事实表明椭圆曲线点形成了一个被称为_阿贝尔群_的结构——支持加法，因此通过扩展支持整数的乘法。例如，$4A=(A+A)+(A+A)=(A+(A+A))+A=(A+(A+(A+A)))$。

将椭圆曲线点乘以非常大的数字也很容易。您可能会认为将一个点乘以十亿需要将其自身加十亿次，但实际上有一个更简单的算法。

  define multiply(P, k) {
    if (k == 0) return point_at_infinity()
    if (k == 1) return P;
    if (k % 2 == 0) return double(multiply(P,k/2))
    if (k % 2 == 1) return add(P,double(multiply(P,(k-1)/2)))
  }

基本上，该算法不是将原始点多次重复加到零，而是重复使用加倍，在每一步都将问题的大小减半。例如，对于$k=83$，该算法扩展为

 83p
 add(p,double(41p))
 add(p,double(add(p,double(20p))))
 add(p,double(add(p,double(double(10p)))))
 add(p,double(add(p,double(double(double(5p))))))
 add(p,double(add(p,double(double(double(add(p,double(2p))))))))
 add(p,double(add(p,double(double(double(add(p,double(double(p)))))))))

对于$k=1000000000$，该算法只需三十步。这使得我们可以将椭圆曲线数字乘以极大的数字——实际上，这些数字大到宇宙中没有足够的原子来计数它们。

有限域

现在，我们进入椭圆曲线数学中更有趣的部分。不久前，数学家发现，我们今天使用的加法、减法、乘法和除法的形式并不是唯一数学上一致的形式。实际上，还有许多其他结构，有些使用数字，有些使用更复杂的形式（例如多项式），我们可以以特殊的方式定义基本运算，并且仍然拥有一个有效的代数系统。最常见的是“模算术”。模加法和模乘法就像普通的加法和乘法一样，只是在计算完成后，您将结果除以一个预设值（称为“模数”），只取余数。例如，在模 7 中

$3+6=9\equiv 2{\pmod {7}}$

以及

$5*4=20\equiv 6{\pmod {7}}$

减法类似，只是如果结果变为负数，则添加模数以使其再次变为正数。因此

$1-2=-1\equiv 6{\pmod {7}}$

除法实现起来比较复杂，但可以通过乘法来定义 - 也就是说，$a/b{\pmod {7}}$ 定义为一个数字 $c$，满足 $bc\equiv a{\pmod {7}}$。可以证明，当且仅当模数为素数时，所有模除法都有答案，并且没有模除法有多个可能的答案。因此，我们通常只关心“素数域”。

那么这种怪异的算术有什么用呢？基本上，它非常适合对椭圆曲线进行运算。无论你加减多少次点，结果的坐标始终是范围在 $[0...p-1]$ 内的整数，其中 $p$ 是模数。“循环”属性也使结构在密码学上安全；给定一个普通的椭圆曲线，给定两个点 $G$ 和 $Q=k*G$，你可以通过查看输出的大小，并利用这些信息缩小可能的范围来计算 $k$ 的值。对于素数域上的椭圆曲线，所有点看起来都差不多；它们都是范围在 $[0...p-1]$ 内的数字，分布大致均匀。这个问题的难度，即给定 $G$ 和 $k*G$ 计算 $k$，实际上是椭圆曲线密码学安全性的基础。

在椭圆曲线中最著名的两种算法是椭圆曲线Diffie–Hellman协议和椭圆曲线数字签名算法，分别用于加密和签名消息。

密码学 图书中的此页面或部分是残缺的。你可以通过扩展它来帮助维基教科书。