翻译: 璐, 校对/版面: 公理

英文: plus.maths.org/content/elliptic-cryptography

椭圆曲线是近几十年来被广泛探索的一个重要数学新领域。它作为一种解决复杂数字问题的工具，以及在密码学中的应用显示出巨大的潜力。

1994年，安德鲁怀尔斯(Andrew Wiles )和他以前的学生理查德泰勒(Richard Taylor)用椭圆曲线解决了过去 400 年来最著名的数学问题之一一费马定理(Fermat's last Theorem)。在过去的几十年里，也有很多研究使用椭圆曲线代替所谓的 RSA 加密来保证数据传输的安全。

公钥与私钥

椭圆曲线密码学(Elliptic curve cryptography，缩写为 ECC)与 RSA 密码学一样,都是一种建立公开密钥加密的算法。这背后的基本思想是挂锁。如果我想给你一个秘密消息，我可以叫你寄给我一个打开的挂锁，但只有你有钥匙。然后我把我的信放在一个盒子里，用挂锁锁上，然后寄给你。这种方法带来的好处是，消息可以通过不安全的通道发送——即使有人截获了该盒子，他们也没有密钥——而且我们并不都需要该盒子的密钥。你甚至可以让很多人用这种方式给你发送秘密信息，而不需要泄露任何一个密钥。

在公钥密码学中，消息使用特定的数学信息进行加密，这些信息构成公钥。而执行加密就是用公钥把信息加密，这就像将挂锁关闭-样。解密只能使用一个不公开的数学私钥，这样即便知道公钥也不能用于解密。

在RSA密码学中，公钥涉及一个自然数 N，被计算机用于加密消息。要解密消需要知道 N 的因数。如果 N 非常大，那么分解它需要巨大的计算能力，以至实际上不可能破解开。只有拥有私钥(即 N 的因数)的人(或者实际上是计算机)能轻松地解密消息。

椭圆曲线

椭圆曲线密码学是基于解决椭圆曲线数字问题的困难性上所建立的。在一个简单的层次这些可以看作是由下面代数方程给出的曲线：

其中 a 和 b 是常数。下面是一些例子。在每种情况下， 图中显示了坐标为 (x,y) 的所有点，其中 x 和 y 满足上述形式的方程。

a 在 -2 和 1 之间的整数值对应的椭圆曲线，b 在 -1 和 2 之间的整数值对应的椭圆曲线。只有 a=b=0 的曲线不符合椭圆曲线，因为它有一个奇异点。

为了精确起见，我们需要对常数 a 和 b 有所限制。上面给出的每个曲线方程能作为一个椭圆曲线，我们需要

。这确保了曲线没有奇异点。通俗地说，这意味着曲线各处都很漂亮平滑，不包含任何尖点或自相交。在上面的例子中， 常数 a 和 b 分别被选择为 -2 和 1、-1 和 2 之间的整数。但总的来说，它们也可以有其他的值。(在密码学中，a 和 b 必须来自称为有限域的特殊数字集)。在下面链接中， 您可以了解更多关于椭圆曲线的信息。

plus.maths.org/content/very-old-question-very-latest-maths-fields-medal-lecture-manjul-bhargava

定义椭圆曲线加密中的加法和乘法

给定一个椭圆曲线，我们可以定义两个点的加法，如接下来例子所示。

先让我们先考虑曲线

两点 A=(2,1) 和 B=(-2,1) 都在曲线上。我们现在想要找到 A+B 的答案，我们也希望它在椭圆曲线上。如果我们像向量那样把它们加起来，我们可以 (2,1)+(-2-1)=(0,0) 。但不幸的是，该点不在曲线上。因此，我们通过以下几个步骤定义椭圆曲线上的加法 A+B。

我们把点 A 和 B 用直线连接起来。这条线通常与曲线相交于另一个点 C。然后我们经过 x 轴反射 C 点。

我们定义这个反射后的镜像点 C'' 为 A 与 B 的和。所以

在我们的例子中，这意味着

再来看另一个例子，

(如下所示)，A=(1,0) 和 B=(0,2),我们有 C=(3,4) 和 C'=(3,-4)。因此(1,0)+(0,2)=(3,4)

我们还需要定义当 B=A 时的总和，以理解我们所说的 A+A=2A 是什么意思。在这种情况下，我们取点 A 处的曲线的正切值，然后像之前一样求出这条切线和曲线的交点，然后再找到这个镜像点。用另一个例子中的图可能更容易理解。

这里我们考虑下面这条椭圆曲线

考虑点 (-2,4) 我们画出了曲线在点 A 处的切线(即 A,B 是同一点)，点 A 与曲线相交于点 C=(4,4) 反映 x 轴给 C'=(4,-4)。因此我们说 2A=C''，或 2(-2,4)=(4,-4) 。

现在我们可以定义曲线上任意一点的A和任意自然数的 n>0 的意义:

等等这样累加的过程。

我们对 A+B 的定义不起作用的唯一情况是, B 就是 A 在 (x,y) 轴上的反射镜像点, 也就是在 B

, A 在同一条垂直 x 轴直线情况下。在这种情况下, 我们把两个位于同一垂直线上的点相加，是压根没有第三个点与它们相交的。

我们可以通过在通常的 (x,y) 平面上添加一个额外的点来解决这个问题，这个点称为无穷大，用 O 表示。为了使加法适用于我们的特殊情况，我们简单地定义了 A+B=O 。对于任意一点，我们也定义了 A+O=A ，所以有了加法的新概念，点 O 和普通加法中的数字，起着相同的作用。

椭圆曲线加密算法安全性基础在于，给定椭圆曲线上的两点 A 和 B ，想要找到一个数字 n ,使 B=n A (如果存在的话)需要巨大的计算能力，特别是当 n 很大的时候。椭圆曲线密码学利用了这个事实: 点 A 和点 B 可以用作公钥，数字 n 可以用作私钥。任何人都可以使用公开可用的公钥加密消息(这里我们不会详细介绍加密方法)，但是只有拥有私钥(数字 n)的个人(或计算机)才能解密它们。

美国国家安全局和黑客数据

椭圆曲线密码学比 RSA 密码学有一些优点一—— RSA 密码学基于分解极大整数的难度 —— ECC 需要更短的密钥来产生同样或更高等级的安全。因此，与 RSA 加密相比，可以更有效(从而硬快)地对数据进行编码。目前， 数字货币比特币使用的是椭圆曲线加密，随着越来越多的数据数字化，它的使用可能会变得更加广泛。然而，值得注意的是，到目前为止还没有人证明破解椭圆曲线是困难的一也许有一 种新的方法可以在更短的时间内解决这个问题。事实 上,许多数学家和计算机科学家都在这个领域工作。

美国国家安全局(NSA)和英国政府通信总部(GCHQ)等政府数字间谍机构也对此类加密技术非常感兴趣。如果有一种快速解决这个问题的方法，那么一夜之间就可以访问大量加密数据——例如，比特币货币兑换将不再安全。最近还有消息称，美国国家安全局(NSA)在一些椭圆曲线加密算法中植入了“后门”条目，这些算法允许NSA访问其他人自以为安全的数据。而数学是这场新的数字军备竞赛的真正核心力量。(完)