比特币背后的数学

比特币系统会让新人迷惑不解的原因之一是其背后的技术重塑了“所有者”这一概念。

传统意义上，“拥有”某物——诸如房产或金钱——意味着该物要么是个人保管，要么是委托一个可信实体（如银行）来保管。

比特币系统的情况则不然。比特币本身既不集中存储也不本地存储，因此没有任何一个实体是其保管人。

比特币是以记录的形式存储于一个被称为“区块链”的帐薄之中，该帐薄的副本在互联计算机所组成的志愿者网络中共享。

“拥有”比特币仅仅意味着拥有移交控制权给他人的能力——通过在区块链中创建一条转帐记录来实现。但这种能力是如何保证的呢？通过一个ECDSA私钥、公钥密钥对。这又是什么意思？怎么保障比特币系统安全的呢？

让我们掀开盖子看一看下面到底是什么。

ECDSA是椭圆曲线数字签名算法(Elliptic Curve Digital Signature Algorithm) 的缩写。它是利用一条椭圆曲线和一个有限域来“签名”数据的流程，通过这种方法，在第三方能验证签名的真实性同时，还能让签名者继续保留创建签名的专属能力。比特币系统中，被“签名”的数据指的是转移所有权时的交易。ECDSA将签名流程和验证流程分离。每个流程都是由几步算术运算所组成的算法。签名算法使用私钥，验证算法使用公钥。稍后我们将演示一个示例。

不过首先，先铺垫一个关于椭圆曲线和有限域的速成教程。

椭圆曲线

椭圆曲线在代数上的表示是下面这个方程：

y2 = x3 + ax + b

其中，a = 0, b = 7 (比特币系统所使用的版本)，它的图形如下：

椭圆曲线有一些很有用的特征。例如，一条非垂直的直线与椭圆曲线相交于两点，若这两点均不是切点，则曲线上必有第三点与那条直线相交。另一个特征是，过曲线上任意一点的非垂直切线与该曲线必有且仅有另一个交点。

利用这些特征，我们可以定义两种运算：“异点相加”和“同点加倍”。（译者注：用弦切法规则来定义加法运算）

“异点相加”, P + Q = R, 定义为：R为R’基于x轴的反射点（对称点）。其中，R’为包含P和Q的直线与曲线的第三个交点。用图解的方式最容易理解：

同样，“同点加倍”，P + P = R, 定义为：作一条过P点的切线，先求出该切线与曲线的另一交点R’,再计算R‘基于x轴的反射点R。

将这两种运算结合起来可以用于标量乘法，R = a P, 定义为将P点与其自身相加a次。例如：

R = 7P

R = P + (P + (P + (P + (P + (P + P)))))

标量乘法的运算过程可以通过“异点相加”与“同点加倍”运算相结合来简化。例如：

R = 7P

R = P + 6P

R = P + 2 (3P)

R = P + 2 (P + 2P)

这里，7P被分解为两步“同点加倍”和两步“异点相加”。

有限域

ECDSA中的有限域可以理解为一个预定义的正数区间，使得每种运算的结果必包含于这个区间中（译者注：对上面定义的加法运算封闭）。区间外的任何数要通过“回绕”来使其落于该区间内。

达到这一目标的最简单的方法是求余数，即用模运算(mod)来实现。例如，9/7 的结果是商1余2：

9 mod 7 = 2

这里，我们的有限域是模数7，所有在这个有限域上的模运算，都会得到一个落在0到6区间内的结果。

综合运用

ECDSA使用的椭圆曲线基于一个有限域，使曲线外观发生了极大变化，而不是改变曲线所基于的方程或特殊属性。用与上图相同的方程式，在模数为67的有限域中绘制后中看起来成了这个样：

现在变成了一个点的集合，所有的x值和y值都是0至66间的整数。注意这个“曲线”仍保持着水平方向的对称。

“异点相加”和“同点加倍”在视觉上稍有不同。图上绘制的直线在水平和垂直方向上要作回绕，就象“小行星”游戏里那样，保持着相同的斜率。因此，（2，22）和（6，25）”异点相加”的图形是这样的：

第三个交点是（47，39），它的反射点是（47，28）。（译者注： 28 = 67 – 39）

回到ECDSA和比特币

诸如比特币这样的协议为椭圆曲线和其有限域选择了一套参数，协议下所有用户使用的参数是固定的。这套参数包括所用的方程式、有限域的质数模数、落在曲线上的“基点”（G）的一个点。基点的“序次”（n）不是单独选定的，它与其他参数构成一个函数，图形上可以想象成“基点”反复与自身相加，直至切线的斜率无穷大（或成为重直线）为止时所叠加的次数。（译者注： “序次”的算术表示是nG = O中的n ）

比特币系统把一些非常大的数设为“基点”、质数模数和“序次”。实际上，所有实际应用中的ECDSA都使用极大的数值。基于这些数值的算法安全性非常高，试图暴力破解或逆向工程的做法是不切实际的。

比特币系统中：

椭圆曲线方程：y2 = x3 + 7

质数模数 = 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

基点 = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

序次 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

谁选择的这些数字，为什么这样选？围绕适合参数的选择问题，产生了大量的研究，同时还有相当数量的阴谋论也被抛了出来。毕竟，一个巨大的，看起来随机的数字有可能隐藏了重构私钥的后门。简言之，这一特定实现被定名为secp256k1，它是密码学用途所使用的基于有限域椭圆曲线解决方案体系中的一员。

私钥和公钥

先把这些规定放到一边，现在到了了解私钥、公钥以及它们的关系的时候了。简要概括一下：ECDSA中，私钥是一个用无法预知的方法选择出的介于1和“序次”之间的数。公钥由私钥演算而得，通过将“基点”和一个等于私钥的数值做标量乘法计算得出。计算公式为：

公钥 = 私钥 × 基点

这表明私钥的最大可取的数值（这也是比特币地址的数量）等于“序次”。

在一个连续的域上，我们可以绘制切线并在图上标出公钥来，不过，有公式可以在有限域上完成同样的工作。p + q “异点相加”求r用分量表示的计算公式如下：

c = (qy – py) / (qx – px)

rx = c2 – px – qx
ry = c (px – rx) – py

p“同点加倍”求r的公式如下：

c = (3px2 + a) / 2py

rx = c2 – 2px
ry = c (px – rx) – py

实际计算中，公钥的计算被分解为从“基点”开始的一系列“同点加倍”和“异点相加”运算。

下面我们用一个小的数字作示例演示底层的运算过程，以便直观上了解密钥是如何构建并如何用于签名和验证的。我们使用的参数为：

方程式：y2 = x3 + 7（亦即：a = 0, b = 7）

质数模数：67

基点：（2，22）

序次：79

私钥：2

首先，求出公钥。由于我们选择的是一个最简单的取值为２的私钥，所以只需对“基点”进行一次“同点加倍”运算即可。计算过程如下：

c = (3 * 22 + 0) / (2 * 22) mod 67

c = (3 * 4) / (44) mod 67
c = 12 / 44 mod 67

这里，我们不得不先停下来使出些手法：当结果必须始终是整数时，怎么做有限域下的除法？我们必须使用倒数来做乘法，不过没有足够篇幅在这里解释（如果对此感兴趣，建议参考这里和这里）。此刻，请您先权且相信我们的计算吧：

44-1 = 32

下面继续：

c = 12 * 32 mod 67

c = 384 mod 67
c = 49

rx = (492 – 2 * 2) mod 67
rx = (2401 – 4) mod 67
rx = 2397 mod 67
rx = 52

ry = (49 * (2 – 52) – 22) mod 67
ry = (49 * (-50) – 22) mod 67
ry = (-2450 – 22) mod 67
ry = -2472 mod 67
ry = 7

由此可知，我们的公钥对应的点是（52，7）。上面这些就是一个数值为2的私钥所需的运算！

比起试图由公钥推导出私钥来，从私钥到公钥容易计算。在实际应用中的椭圆曲线加密由于使用大数值作为参数，由公钥推导私钥在理论上是可能的，但在计算上行不通的。

因此，从私钥得到公钥是设计使然的单向行程。

与私钥一样，公钥通常用一个十六进制数的字符串来表示。但等等，我们是怎么把平面上的一个由两个数字所代表的点变成了一个数？在非压缩格式的公钥中，代表x坐标和y坐标的两个256位的数字粘合在一起就生成了一个长字符串。我们还可利用椭圆曲线的对称性生成一个压缩格式的公钥，只保留x值标明该点在位于曲线上的哪一侧。由这个部分数据我们就可以把两个轴的坐标都还原出来。

用私钥签名

现在我们有了一个私钥和公钥对，签名些数据吧！

数据可以上任意长度。通常第一步是哈希数据来生成一个与曲线的“序次”位数（256）相同的数字。这里为了使文章简洁，我们省略了哈希的步骤，只签名原始数据z。我们用G来代表“基点“，n代表“序次”，d代表私钥。签名的方法如下：

1．选择一个介于1和n-1之间的整数k；

2．用标量乘法计算点（x, y） = k × G；

3. 令r = x mod n。若r = 0则返回步骤1；

4. 令s = (z + r × d) / k mod n。若s = 0则返回步骤1；

5．（r, s）即为签名。

需要提醒的是，在步骤４中，若计算结果出现分数（在实际计算中总会出现），要用分子去乘以分母的倒数。在步骤１中，进行不同的签名时，一定要注意使用的k值不能出现重复，并且不能被第三方猜出来。也就是说，k值要么是一个随机数，要么是使用让第三方无法窃密的确定性方法来生成。否则，私钥会从第4步中被提取出来，因为s, z, r, k和n都是已知的。你可以在这里了解一个过去出现过的此类型的漏洞。

我们选取数字17作为待签名的数据，按下面的方法来计算。变量如下：

z = 17 (数据)

n = 79 (序次)
G = (2, 22) (基点)
d = 2 (私钥)

1．选取一个随机数：

k = rand(1, n – 1)

k = rand(1, 79 – 1)

k = 3（“这真的是随机的吗？我读书少，不要骗我哦！”“好吧，被你看出来了，不过这个数能让我们的示例更简单点！”）

2．将点计算出来。这与前面确定公钥时方法相同，为了简明扼要，我们省略了“同点加倍”和“异点相加”的算术计算。

(x, y) = 3G

(x, y) = G + 2G

(x, y) = (2, 22) + (52, 7)

(x, y) = (62, 63)

x = 62

y = 63

3．计算r.

r = x mod n

r = 62 mod 79

r = 62

4. 计算s:

s = (z + r × d) / k mod n

s = (17 + 62 × 2) / 3 mod 79

s = (17 + 124) / 3 mod 79

s = 141 / 3 mod 79

s = 47 mod 79

s = 47

注意上面的计算中３能被除开，结果是个整数。实际计算中，我们需要使用k的倒数（和前面一样，我们隐藏了一些令人作呕的计算细节）：

s = (z + r * d) / k mod n
s = (17 + 62 * 2) / 3 mod 79
s = (17 + 124) / 3 mod 79
s = 141 / 3 mod 79
s = 141 * 3-1 mod 79
s = 141 * 53 mod 79
s = 7473 mod 79
s = 47

5. 我们的签名就是（r, s） = (62, 47)。

与私钥和公钥一样，签名通常用一个十六进制的字符串来表示。

用公钥来验证签名

现在，我们有了数据和该数据的签名。掌握我们的公钥的第三方机构可以收到该数据和签名，并能验证出我们是发送者。让我们看看具体是怎样工作的。

用Q来表示公钥，其他的变量同上，验证签名的步骤如下：

1. 验证r和s在1和n-1之间；

2. 计算 w = s mod n ；

3. 计算 u = z × w mod n ；

4. 计算 v = r × w mod n ；

5. 计算点（x, y） = uG + vQ ；

6. 验证r = x mod n. 若等式不成立则签名无效。

为什么这些步骤能有用？我们省略了证明过程，不过你可以从这里了解更多细节。

依照上面的方法我们看一下验证过程是如何进行的。变量如下：

z = 17 (数据)

(r, s) = (62, 47) (签名)

n = 79 (序次)

G = (2, 22) (基点)

Q = (52, 7) (公钥)

1. 验证r和s介于１与n-1之间。

检查、再检查

r: 1 <= 62 < 79

s: 1 <= 47 < 79

2. 计算w:

w = s mod n

w = 47 mod 79

w = 37

3. 计算u:

u = zw mod n

u = 17 * 37 mod 79

u = 629 mod 79

u = 76

4. 计算v:

v = rw mod n

v = 62 * 37 mod 79

v = 2294 mod 79

v = 3

5. 计算点(x, y):

(x, y) = uG + vQ

我们将uG和vQ分解为“同点加倍”和“异点相加”，分别进行计算。

uG = 76G

uG = 2(38G)

uG = 2( 2(19G) )

uG = 2( 2(G + 18G) )

uG = 2( 2(G + 2(9G) ) )

uG = 2( 2(G + 2(G + 8G) ) )

uG = 2( 2(G + 2(G + 2(4G) ) ) )

uG = 2( 2(G + 2(G + 2( 2(2G) ) ) ) )

稍坐片刻来体会一下吧，通过使用分组技巧，我们将75次连续的加法运算减少为6次“同点加倍”和2次“异点相加”运算。当数字真的变得很大时，这些技巧将会派上用场。

将工作结果算出来:

uG = 2( 2(G + 2(G + 2( 2( 2(2, 22) ) ) ) ) )

uG = 2( 2(G + 2(G + 2( 2(52, 7) ) ) ) )

uG = 2( 2(G + 2(G + 2(25, 17) ) ) )

uG = 2( 2(G + 2( (2, 22) + (21, 42) ) ) )

uG = 2( 2(G + 2(13, 44) ) )

uG = 2( 2( (2, 22) + (66, 26) ) )

uG = 2( 2(38, 26) )

uG = 2(27, 40)

uG = (62, 4)

下面是 vQ:

vQ = 3Q

vQ = Q + 2Q

vQ = Q + 2(52, 7)

vQ = (52, 7) + (25, 17)

vQ = (11, 20)

把两个加到一起:

(x, y) = uG + vQ

(x, y) = (62, 4) + (11, 20)

(x, y) = (62, 63)

显然步骤5在整个计算中占了大部分。最后一步是,

6. 验证 r = x mod n

r = x mod n

62 = 62 mod 79

62 = 62

我们的签名有效！

结论

那些看完了所有的公式然后跳转到底部的读者，我们刚刚学到了什么？

我们对存在于公钥和私钥间的深层数学关系有了一些直观认识。我们看到即使在这个最简单的示例中，签名和验证的过程也立刻变得非常复杂，从而我们可以体会到一旦相关参数变成了256位，相应会带来多么巨大的复杂度。我们看到了最简单的数学运算是如何巧妙应用，使其实现了保护信息所需要的单向“陷阱门”功能，此功能定义了比特币的所有权。我们对系统的强健度有了新的自信，只要我们能细心保护好我们的私钥。

换句话说，这就是人们常说比特币是“基于数学”的原因。

如果你面对这些复杂的二进制位仍能坚持看下来，我希望这可以给你一些信心迈向下一步，尝试自己用数学算一算（这里有一个模运算计算器能让有限域的运算更容易些）。我觉得手工进行数据的签名和验证能令人更深地理解这一密码学算法，正是它塑成了比特币系统的独一无二的“所有者”形式。

—-

文章来源：http://www.8btc.com/the-math-behind-bitcoin

原文链接：http://blog.chain.com/post/95218566791/the-math-behind-bitcoin

原文作者：Eric Rykwalder

编译者/作者：chehw 校对：少平

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。