玩币族移动版
比特币背后的数学
时间:2014-11-27 来源:巴比特 作者:chehw 校对：少平
比特币系统会让新人迷惑不解的原因之一是其背后的技术重塑了“ 传统意义上，“拥有”某物——诸如房产或金钱——意味着该物要么是个人保管，要么是委托一个可信实体（如银行）来保管。 比特币系统的情况则不然。比特币本身既不集中存储也不本地存储，因此没有任何一个实体是其保管人。 比特币是以记录的形式存储于一个被称为“区块链”的帐薄之中，该帐薄的副本在互联计算机所组成的志愿者网络中共享。
“拥有”比特币仅仅意味着拥有移交控制权给他人的能力——通过在区块链中创建一条转帐记录来实现。但这种能力是如何保证的呢？通过一个 让我们掀开盖子看一看下面到底是什么。
不过首先，先铺垫一个关于椭圆曲线和有限域的速成教程。
椭圆曲线
其中，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次。例如：
标量乘法的运算过程可以通过“异点相加”与“同点加倍”运算相结合来简化。例如：
这里，7P被分解为两步“同点加倍”和两步“异点相加”。
有限域
ECDSA中的 达到这一目标的最简单的方法是求余数，即用模运算(mod)来实现。例如，9/7 的结果是商1余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都使用极大的数值。基于这些数值的算法安全性非常高，试图暴力破解或逆向工程的做法是不切实际的。 比特币系统中：
谁选择的这些数字，为什么这样选？围绕适合参数的选择问题，产生了大量的研究，同时还有相当数量的阴谋论也被抛了出来。毕竟，一个巨大的，看起来随机的数字有可能隐藏了重构私钥的后门。简言之，这一特定实现被定名为
私钥和公钥
先把这些规定放到一边，现在到了了解私钥、公钥以及它们的关系的时候了。简要概括一下：ECDSA中， 公钥 = 私钥 × 基点 这表明私钥的最大可取的数值（这也是比特币地址的数量）等于“序次”。 在一个连续的域上，我们可以绘制切线并在图上标出公钥来，不过，有公式可以在有限域上完成同样的工作。p + q “异点相加”求r用分量表示的计算公式如下：
p“同点加倍”求r的公式如下：
实际计算中，公钥的计算被分解为从“基点”开始的一系列“同点加倍”和“异点相加”运算。 下面我们用一个小的数字作示例演示底层的运算过程，以便直观上了解密钥是如何构建并如何用于签名和验证的。我们使用的参数为：
首先，求出公钥。由于我们选择的是一个最简单的取值为２的私钥，所以只需对“基点”进行一次“同点加倍”运算即可。计算过程如下：
这里，我们不得不先停下来使出些手法：当结果必须始终是整数时，怎么做有限域下的除法？我们必须使用倒数来做乘法，不过没有足够篇幅在这里解释（如果对此感兴趣，建议参考这里和这里）。此刻，请您先权且相信我们的计算吧：
下面继续：
由此可知，我们的公钥对应的点是（52，7）。上面这些就是一个数值为2的私钥所需的运算！ 比起试图由公钥推导出私钥来，从私钥到公钥容易计算。在实际应用中的椭圆曲线加密由于使用大数值作为参数，由公钥推导私钥在理论上是可能的，但在计算上行不通的。 因此，从私钥得到公钥是设计使然的单向行程。 与私钥一样，公钥通常用一个十六进制数的字符串来表示。但等等，我们是怎么把平面上的一个由两个数字所代表的点变成了一个数？在非压缩格式的公钥中，代表x坐标和y坐标的两个256位的数字粘合在一起就生成了一个长字符串。我们还可利用椭圆曲线的对称性生成一个压缩格式的公钥，只保留x值标明该点在位于曲线上的哪一侧。由这个部分数据我们就可以把两个轴的坐标都还原出来。
用私钥签名 现在我们有了一个私钥和公钥对，签名些数据吧！ 数据可以上任意长度。通常第一步是哈希数据来生成一个与曲线的“序次”位数（256）相同的数字。这里为了使文章简洁，我们省略了哈希的步骤，只签名原始数据z。我们用G来代表“基点“，n代表“序次”，d代表私钥。签名的方法如下：
需要提醒的是，在步骤４中，若计算结果出现分数（在实际计算中总会出现），要用分子去乘以分母的倒数。在步骤１中，进行不同的签名时，一定要注意使用的k值不能出现重复，并且不能被第三方猜出来。也就是说，k值要么是一个随机数，要么是使用让第三方无法窃密的确定性方法来生成。否则，私钥会从第4步中被提取出来，因为s, z, r, k和n都是已知的。你可以在这里了解一个过去出现过的此类型的漏洞。 我们选取数字17作为待签名的数据，按下面的方法来计算。变量如下：
1．选取一个随机数：
2．将点计算出来。这与前面确定公钥时方法相同，为了简明扼要，我们省略了“同点加倍”和“异点相加”的算术计算。
3．计算r.
4. 计算s:
注意上面的计算中３能被除开，结果是个整数。实际计算中，我们需要使用k的倒数（和前面一样，我们隐藏了一些令人作呕的计算细节）：
5. 我们的签名就是（r, s） = (62, 47)。 与私钥和公钥一样，签名通常用一个十六进制的字符串来表示。
用公钥来验证签名 现在，我们有了数据和该数据的签名。掌握我们的公钥的第三方机构可以收到该数据和签名，并能验证出我们是发送者。让我们看看具体是怎样工作的。 用Q来表示公钥，其他的变量同上，验证签名的步骤如下：
为什么这些步骤能有用？我们省略了证明过程，不过你可以从这里了解更多细节。 依照上面的方法我们看一下验证过程是如何进行的。变量如下：
1. 验证r和s介于１与n-1之间。
2. 计算w:
3. 计算u:
4. 计算v:
5. 计算点(x, y):
我们将uG和vQ分解为“同点加倍”和“异点相加”，分别进行计算。
稍坐片刻来体会一下吧，通过使用分组技巧，我们将75次连续的加法运算减少为6次“同点加倍”和2次“异点相加”运算。当数字真的变得很大时，这些技巧将会派上用场。
将工作结果算出来:
下面是 vQ:
把两个加到一起:
显然步骤5在整个计算中占了大部分。最后一步是, 6. 验证 r = x mod n
我们的签名有效！ 结论 那些看完了所有的公式然后跳转到底部的读者，我们刚刚学到了什么？ 我们对存在于公钥和私钥间的深层数学关系有了一些直观认识。我们看到即使在这个最简单的示例中，签名和验证的过程也立刻变得非常复杂，从而我们可以体会到一旦相关参数变成了256位，相应会带来多么巨大的复杂度。我们看到了最简单的数学运算是如何巧妙应用，使其实现了保护信息所需要的单向“陷阱门”功能，此功能定义了比特币的所有权。我们对系统的强健度有了新的自信，只要我们能细心保护好我们的私钥。 换句话说，这就是人们常说比特币是“基于数学”的原因。 如果你面对这些复杂的二进制位仍能坚持看下来，我希望这可以给你一些信心迈向下一步，尝试自己用数学算一算（这里有一个模运算计算器能让有限域的运算更容易些）。我觉得手工进行数据的签名和验证能令人更深地理解这一密码学算法，正是它塑成了比特币系统的独一无二的“所有者”形式。 |
