作者：Hans Knutson

来源：https://hackernoon.com/what-is-the-math-behind-elliptic-curve-cryptography-f61b25253da3

引言

某人要给你发送比特币时，他们是把比特币发送到你的地址上。要是你想花费你的地址上的这些比特币，你需要创建一笔交易来指定把比特币发送到哪里。一笔交易的含义就像下文：

从 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa（你的地址）转移 5 BTC 到 12c6DSiU4Rq3P4ZxziKxzrL5LmMBrzjrJX（收款人地址）

当然，任何人都能创建出上面这样的交易，所以，如果区块链会径直接受这种形式的交易，那无论是谁发起了它，你地址里面的 5 个比特币就会不翼而飞。幸运的是，区块链不会接受这种形式的交易，因为它缺少一个有效的数字签名（digital signature）。数字签名是用来证明你知道这个地址 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfN 对应的私钥的，如果你不知道对应的私钥，那 —— 你就不应该让人把钱发到这个地址，因为你没法花费其中的比特币！

你在给自己创建一个比特币地址（或者创建任意某种密码学货币的 地址/账户 时），你要先生成一个私钥。使用私钥，你可以计算出相应的公钥，并通过公钥哈希和转码生成相应的地址。幸好你不能先选择地址然后反向算出它的私钥，不然你就可以用同样的方法解出任何地址的私钥了。那还有 “账户” 这回事吗？

公钥密码学

公钥、私钥和数字签名，都是来自公钥密码学的基本概念。不论使用什么数学原理来实现一种公钥密码系统，它都必须满足下列属性（至少就我们的使用目的而言）：

1. 从给定的公钥倒推出相应的私钥在计算上是不可行的。
2. 无需揭晓关于私钥的信息，就能证明一个人知道对应于某个公钥的私钥。进一步地，这样的证明可以被构造成需要结合一条具体的消息来验证。如此一来，这个证据就成了那条消息的数字签名。

打造公钥密码学的其中一种方法就是椭圆曲线。另一种办法是 RSA，它是围绕质数的。大部分的密码学货币 —— 包括比特币和以太坊 —— 都使用椭圆曲线，因为一个 256 位的椭圆曲线私钥跟一个 3072 位的 RSA 私钥的安全性相当。体积更小的私钥更易于管理和使用。

椭圆曲线密码学

那什么是椭圆曲线呢？一条椭圆曲线由满足下列形式的等式的所有点构成：

y2=x3+ax+by2=x3+ax+b

同时 4a3+27b2≠04a3+27b2≠0 （这是为了避免奇点（singular points））。

下面是一些椭圆曲线的例子：

注意，上面所有的椭圆曲线都是 X 轴对称的。实际上，所有的椭圆曲线都如此，这是其形式所决定的。

y2=x3+ax+by2=x3+ax+b

如果你取等式两边的平方根，就可以得到：

y=±x3+ax+b−−−−−−−−−√y=±x3+ax+b

所以，如果取 a 为 27 而 b 为 2， 那么插入 x = 2 时，可得 y = ±8，也就是两个点 （2, -8）和（2, 8）。

下面这个椭圆曲线是比特币、以太坊等项目使用的椭圆曲线，叫做 “secp256k1”。这条曲线的等式是 y2=x3+7y2=x3+7，图像是：

中本聪选择 spec256k1 并无特殊的理由。

点加法

你肯定知道如何把两个数相加，得出第三个数吧？在椭圆曲线上，你可以把两个点相加，得出第三个点。

要在一条椭圆曲线上把两个点相加，你先要找出一条穿过这两个点的直线。然后，这条直线与椭圆曲线的交点就是第三个点，最后，这个点跟 x 轴的对称点（也即其 y 坐标值乘以 -1 ）即是两个点相加的结果。

我们来举个例子，假设我们要把下图所示的两个点相加：

首先，作出一条穿过这两个点的直线：

然后找出这条直线与椭圆曲线相交的点（第三个点）：

最后，找出与该点 x 轴对称的点：

所以，P + Q = R。

为了方便实现椭圆曲线密码学，我们不是把两个点相加，而是在曲线上定义一个基本点，总是让这个点与自身相加。

举个例子，假设我们在下列曲线上有基本点 P：

自然，我们就有了 P，或者说 1·P。

现在，我们让 P 与自身相加。首先，我们找出一个过 P 和 P 的直线（及其等式）。这样的直线有无数条！所以，在这种特殊的情形中，我们选择 P 点上椭圆曲线的切线：

现在，我们可以找出 “第三点” 并通过 x 轴对称找到结果：

这就是 P 与自身相加的结果，P + P 或者说 2·P。

如果我们使之再与 P 相加，那是让 P 加上自身再加上自身，结果就是 3·P。为了计算 3·P，我们直接让两点相加即可：

我们可以继续加下去，得出 4·P、5·P，等等。

secp256k1 所用的基本点的 x 坐标值和 y 坐标值为：

x 坐标值：55066263022277343669578718895168534326250603453777594175500187360389116729240

y 坐标值：32670510020758816978083085130507043184471273380659243275938904335757337482424

在上面的例子中，我们为了让所有的点都能在一个小窗口中显示，所以使用了不同的基本点。

快速点加法

如果你要计算 10·P，需要多少步呢？直觉来看，需要 9 步，因为 10·P 等于：

P + P + P + P + P + P + P + P + P + P

需要 9 次点加法。

但事实证明，你只需 4 步就可以计算 10·P，因为点加法满足下列属性：

n•P + r•P = (n + r)•P

举个例子：

4•P + 6•P = (4 + 6)•P = 10•P

那么，你可以这样计算 10·P：

P + P = 2•P

2•P + 2•P = 4•P

4•P + 4•P = 8•P

2•P + 8•P=10•P

这就只需要 4 次点加法。

那么，计算 x·P 需要多少步呢？x 是一个随机的 256 位整数，在我们这个例子中，x 的取值范围是从 0 到 1.1579209e+77。

事实又证明，你计算 x·P 最多只需要 510 次的点加法运算。解释一下：首先，你计算下列值：

2⁰•P、2¹•P、2²•P、2³•P、2⁴•P、2⁵•P、2⁶•P、…、2²⁵⁵•P

你可以用 255 次点加法计算出上面的所有值，因为这里有 256 个点，而你只要将前一个点与自身相加就可以得到后一个点。这是因为 2n∙P+2n∙P=2n+1∙P2n•P+2n•P=2n+1•P。

下一步就是找出 x 的二进制表示。举个例子，如果 x 是 246，那么其二进制展开就是 2⁷ + 2⁶ + 2⁵ + 2⁴ +2² + 2¹ = 246 。那么，我们就可以使用其二进制展开式来计算 246·P 的结果：2⁷•P + 2⁶•P + 2⁵•P + 2⁴•P + 2²•P + 2¹•P。我们不再需要一个一个点计算，因为这些点我们都提前算好了。

因为 x 的二进制展开式最多包含 256 个元素（从 2⁰ 到 2²⁵⁵），所以我们最多只需要把 256 个点相加，因此，最多只需要 255 次点加法。因此，总的来说，计算 x·P 最多只需要 510 次点加法。

椭圆曲线密码学中的私钥和公钥

假设我们要计算 x·P，而 x 是一个 256 位的随机整数。结果将是椭圆曲线上的一个点，我们称为点 X。

如果我给你 X，你能计算出 x 来吗？换句话来说，你能确定我相加了几次 P 来得到 X 吗？假设你是知道 P，也知道我使用的是哪条曲线。

事实证明，即使你拥有一台超级计算机，计算出 x 也是不可行的。没有已知的算法能计算出 x，所以你的唯一解法便是不断把 P 与自身相加，直至获得 X，或者从 X 中持续减去 P，直到结果就是 P。 x 是 0 到 2²⁵⁶-1 之间的某个数，所以其平均值为 2¹²⁸；因此，你需要做平均 2¹²⁸ 次点加法来求得 x。即使你的计算机可以每秒做 10000 亿次点加法，你从宇宙初创的那一刻开始跑计算机，到今天你也只能完成 2⁹⁸ 次点加法。而 2⁹⁸/2¹²⁸ =1/1073741824。

从正中间开始会不会快一点呢？比如，不到 510 步就能先算出 2¹²⁸•P。嗯，因为平均而言，x 接近 2¹²⁸ 的概率并不比它接近 0 或者 2²⁵⁶-1 的概率更大，它是随机分布的，所以你从哪里开始，结果都是一样的。平均而言你还是必须做 2¹²⁸ 次点加法。

私钥和公钥

所以，因为别人无法根据给定的 X 求得 x（X = x·P），所以 x 很适合用作你的私钥，而 X 就是你的公钥。因此，你的私钥是一个 256 位的随机整数，而公钥则是椭圆曲线上的点的 x 坐标值和 y 坐标值。这就满足了私钥和公钥所需的属性：

“从给定的公钥中推导出对应的私钥在计算上是不可行的”。

此外，虽然我们还没解释过，但确实，你可以无需揭示任何关于 x 的有用信息，就向别人证明你知道 x。也就是说，你可以向别人证明，你知道 P 与自身相加多少次可以得到 X，而无需告诉他们 x 到底是多少。

更新的椭圆曲线模型

在我们向其他人证明自己知道 x 之前，我们需要更新我们的椭圆曲线模型。

我们当前的模型的一个问题在于，x·P 的结果的 x 坐标值和 y 坐标值可能过大，无法存储在一个标准的 512 位的公钥中。x 坐标值和 y 坐标值都有可能过大。

接近方案是将我们的椭圆曲线定义在一个有限域上。基本上，就是确保只有椭圆曲线上只有整数点，而且这个点的坐标值是有上限的。

为达成这个目标，我们将等式

y2=x3+ax+by2=x3+ax+b

转化成：

公式

y² mod p = (x³ + ax + b) mod p

p 是某个指数（p 必须是质数，以保证加法和乘法总是能被还原（can always be undone））。

在 secp256k1 中， p 是小于 2²⁵⁶ 的最大质数。

我们的椭圆曲线因此看起来就像这样：

注意，这里依然有一条水平的对称线。

那么，现在你想把两个点相加，穿过这两个点的直线在跟第三个点相交之前就会飞到值域之外，那怎么办呢？让线从另一边开始继续延伸！

如上图所示，你会发现，把 P 跟 Q 相加需要让 P 跟 Q 之间的线来回环绕多次。

除了这个变化，其余东西都暂时不需要改变。

如何证明你知道 x

现在，你算出了 X = x·P，而 x 是一个 256 位的整数，你如何证明你知道对应于 X 的 x，且无需暴露关于 x 的任何有用信息呢？

你可以使用我们前面提到的点加法的属性：

n•P + r•P = (n + r)•P

稍微修改一下，可得：

hash(m, r•P)•n•P + r•P = (hash(m, r•P)*n + r)•P

你把方程的右半部分展开，就可以得到左边的部分，所以它对任意的 m、r 和 n，都是成立的。

那，不如我们令 n·P = X？这样就有：

hash(m, r•P)•X + r•P = (hash(m, r•P)*n + r)•P

如果 n·P = X，那 n 就等于 x，再转写一下，就是：

hash(m, r•P)•X + r•P = (hash(m, r•P)*x + r)•P

最后，我们做一下代换，令 R = r·P、 s = hash(m, R) * x + r 。

于是：

hash(m, R)•X + R = s•P

那么，我们再来回顾这个命题：如果你能提供一组 m、R 和 s，满足上述方程，那就能证明你知道对应于 X 的 x，即 x·P = X 。

要使该命题为真，需要满足两个前提：

1. 只要你知道 x，那你就能提供合适的 m、R 和 s 值来满足上述方程
2. 如果你不知道 x，那么你不可能找出满足上述方程的 m、R 和 s

如果你知道 x，显然你可以找出可以满足上述方程的值。选择随机的 m 和 r，然后计算 R = r·P，然后 s = hash(m, R) * x + r，代入方程 hash(m, R)•X + R = s•P，可得：

hash(m, r•P)•n•P + r•P = (hash(m, r•P)*n + r)•P

正是我们前面说的，对任意 m、r 和 n（在我们这里就是 x）都成立的等式。

那要是你不知道 x 呢？你可以计算出能满足上述方程的 m、R 和 s 吗？问题就在于，你要解出 hash(m,R)•X + R = s•P。基本上，你这是要找出一个哈希值的原像，而这是不可能的，至少在计算上是不可行的，因为密码学哈希函数有原像攻击抗性。

因此，唯一能够提供有效的 m、R 和 s 值的方法就是使用 x 来计算它们。因此，你可以通过提供满足等式 hash(m, R)•X + R = s•P 的 m、R 和 s 值来证明你知道 x。

在这个过程中，你真的没有暴露关于 x 的信息吗？

如果你已经提供了有效的 m、R 和 s，别人能从中知道关于 x 的有效信息吗？

m 和 R 都跟 x 无关，所以这些值不会暴露关于 x 的有效信息。

而我们知道，s = hash(m, R) * x + r 。能不能从 s 中计算出 x 呢？

这就是在讨论，我们能否解出 x = (s-r)/hash(m, R) 。

因为我们不知道 r，所以无法从 s 中计算出 x。而我们也无法从 R = r·P 中计算出 r，因为这就是想知道 P 与自己相加多少次能得到 R，也就是想从 X 中知道 x，在计算上是不可能的。

s 也不会暴露关于 x 的信息（比如 “x 必然小于 bala bala”）。如果 r 是随机生成的，而我们允许 hash(m, R) * x + r 溢出使得 r 可以是任何 256 位的整数，那么 s 的值就是完全随机的，s 可以是任何 256 位的整数。一个随机的 256 位整数，所蕴含的有关 x 的信息，恐怕就跟新西兰的 GDP 所蕴含的一样多。

数字签名

m、R 和 s 可以用来证明某人知道相应于 X 的 x（X = x·P）。验证这个证据需要把 m、R 和 s 代入等式 hash(m,R)•X + R = s•P。那么，我们是否能然验证依赖于一条特定的消息，使得这个证据 —— m、R 和 s —— 变成对该消息的一个数字签名？当然可以！

假设 m 就是那条消息，而 R 和 s 就是这条消息的数字签名。验证将仅在这条消息，也即是 m，代入验证等式之时，才会成功。如果代入的是另一条消息，则左右两边将不相等，因为计算 s 所用的 m 值与代入得消息不等。

因此，你可以通过提供一个数字签名 R 和 s，以及相应的消息 m，来证明你知道相应于公钥 X 的私钥 x。

在密码学货币中，这个消息就是一笔交易的待签名的部分。一条交易的数字签名，通常是 R 的 x 坐标值后面跟着 s（R 是椭圆曲线上的一个点，s 是近乎随机的 256 位整数），然后还要编码成十六进制的形式。

（译者注：作者在此处解释的数字签名方案，并不是比特币和以太坊一开始使用的 ECDSA 签名，而是一种叫做 “Schnorr 签名” 的方案（的简化版）。在 2021 年 12 月以前，比特币上也无法使用 Schnorr 签名，而只能使用 ECDSA 签名；2021 年 12 月，比特币激活 taproot 升级，该升级便引入了 Schnorr 签名，从此比特币交易可以使用 Schnorr 签名方案了。）

结论

如果你想获得一个比特币地址或者以太坊账户，你只需生成一个随机的 256 位整数 x，x 就是你的私钥。然后你使用 secp256k1 的参数就可以计算出公钥 X = x·P。你的公钥可以放心地展示给别人，无法用来反算出你的私钥。再对公钥哈希计算，就得到了地址。

（译者注：以太坊的地址确实是这样得出来地，但是比特币的地址需要经过更多的编码步骤，不过原理上是差不多的）。

当你想把自己地址里的比特币发给其他人时，你要创建一笔比特币交易。把交易的待签名部分设置成 m，并使用该 m 计算出 R 和 s。然后在交易中附加上 R 和 s。在你把这笔交易广播到比特币网络中以后，收到交易的节点会验证 m（交易的待签名部分）、R 和 s 满足等式 hash(m,R)•X + R = s•P。当然，这也假设了你要在交易中提供 X，因为你的公钥无法从地址中推测出来。在以太坊交易中，你无需提供 X，可以提供 v，v 可用来从 R 和 s 中计算出 X。

（译者注：再次提醒，作者解释的并不是 ECDSA 签名算法，而是 Schnorr 签名算法，该算法在 2021 年 12 月之后才能在比特币上使用。）

（完）

Hans Knutson 2022-02-12
https://www.btcstudy.org/2022/02/12/what-is-the-math-behind-elliptic-curve-cryptography/