作者:Hans Knutson

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

image

引言

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

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

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

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

公钥密码学

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

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

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

椭圆曲线密码学

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

$$
y^2 = x^3 + ax + b
$$

同时 $4a^3 + 27b^2 \neq 0$ (这是为了避免奇点(singular points))。

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

img

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

$$
y^2 = x^3 + ax + b
$$

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

$$
y = \pm \sqrt{x^3 + ax + b}
$$

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

下面这个椭圆曲线是比特币、以太坊等项目使用的椭圆曲线,叫做 “secp256k1”。这条曲线的等式是 $y^2 = x^3 + 7$,图像是:

img

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

点加法

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

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

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

img

首先,作出一条穿过这两个点的直线:

img

然后找出这条直线与椭圆曲线相交的点(第三个点):

img

最后,找出与该点 x 轴对称的点:

img

所以,P + Q = R。

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

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

img

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

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

img

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

img

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

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

img

我们可以继续加下去,得出 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 个点,而你只要将前一个点与自身相加就可以得到后一个点。这是因为 $2^n•P + 2^n•P = 2^{n+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 坐标值都有可能过大。

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

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

$$
y^2 = x^3 + ax + b
$$

转化成:

公式

y2 mod p = (x3 + ax + b) mod p

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

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

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

img

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

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

img

如上图所示,你会发现,把 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 月之后才能在比特币上使用。)

(完)