比特币和密码学中的数字签名

为什么需要签名

在日常生活中，我们经常会遇到需要签名的情况，比如我们在使用信用卡消费后，需要在收据的持卡人签名栏签上自己的名字，或者一些纸质文件需要领导签字在各种审批程序中。 签名的目的是使文件/文件得到签字人的授权，使文件/文件所载的权利和义务依法生效。 签字即表示您认可您的信用卡消费，领导同意本文件内容的执行。

按理说，上述签约情节大致包括三个基本因素：

简单理解，数字签名就是对计算机信息进行数字签名，可以实现与文档/文档签名相同的功能：验证签名者的身份和签名时间，验证签名信息的正确性。 数字签名通常应用于发送方和接收方对相互传输的信息内容（即明文传输）没有保密要求的情况。 有两种基本的生成方法：加密算法生成和签名算法生成。

加密算法产生的数字签名是基于Hash函数的，RSA和DSA签名算法属于这一类。 哈希函数H是一个公共函数，用于将任意长度的信息M1映射成固定长度的值H(M1)，H(M1)也称为消息摘要。 Hash函数H的特点是，当消息M1发生任何变化，变成M2时，H(M1)不等于H(M2)，即信息发生任何变化都会改变信息概要。 发送方使用公钥密码算法和自己的私钥对信息的Hash值进行加密，生成数字签名，即S=Sig(PrivateKey,Hash(M))，PrivateKey为发送方的私钥公钥算法的加密函数Sig()。 接收方对签名的验证过程是：计算D=Ver(S,PublicKey)是否与Hash(M)一致，Ver()为解密函数，PublicKey为公钥。

签名算法生成的数字签名如下： 假设明文消息标记为M，Sig()为签名算法，密钥标记为x，则数字签名为S=Sig(x,M ). 在知道了 M 和 S 的情况下，就不能反算出 x 了； 签名验证算法为：Ver(x,S,M)，可以看成是一个三元函数，即有三个输入的函数。 当S=Sig(x,M)时，Ver(x,S,M)为True，否则输出为False，即在伪造另一个消息N时，Ver(x,S,N)的输出一定为False .

我们知道数学问题有难有易，困难的问题不一定能用大量的计算能力和时间得到正确的结果。 为了实现“已知M和S不能反推x”的思想，我们需要找到一些合适的数学问题。

椭圆曲线数字签名算法

椭圆曲线数字签名算法基于椭圆曲线密码学。 签名方法类似于DSA数字签名算法。 它需要了解三个基本知识：有限域上的椭圆曲线、椭圆曲线中嵌入的明文和椭圆曲线上的离散对数问题。 思路如下：

以上思路加上ElGamal密码和DSA数字签名算法（略），开始踏上真正理解椭圆曲线数字签名之路。 Standards for Efficient Cryptography Group 网站有关于椭圆曲线密码学和椭圆曲线签名的详细文档。 比特币使用 Koblitz 曲线，其参数记录为 secp256k1（但比特币将可选密钥限制为 Koblitz 椭圆曲线密码签名密钥的子集），以 secp256k1 命名的前三个字母是 Standards for Efficient Cryptography，p 的缩写是指椭圆曲线参数有限域的素数特征值，256为p的位数，k为Koblitz曲线。 secp256k1椭圆曲线有限域的p阶为：

p=2^256-2^32-2^9-2^8-2^7-2^6-2^4-1,

曲线的第一象限集合、集合的生成器、私钥等参数的选择可以参考这里。 当椭圆曲线的参数定义在GF(p)上时，求解曲线上的离散对数问题需要接近2^t次运算。 2t是不小于log(p)的最大整数，log是以2为底的对数。对于比特币中基于椭圆曲线密码学的签名来说，这个数大约是2^128，相当于找SHA256碰撞的难度. 开裂时间是天文数字。 目前，另一种攻击椭圆曲线上离散对数问题的方法是攻击任意循环群上的大步长和小步长的离散对数问题。 计算时间复杂度为：

O(exp(log(Pmax^(1/2))))

这里Pmax是由椭圆曲线构成的循环群阶的最大素因子。 时间复杂度反映了随着输入规模的增加，算法执行所需时间的大小。 显然，这是一个指数时间，所以理论上破解比特币数字签名算法ECDSA目前还是一个NP问题，即没有多项式时间。 解开。 只要比特币中的签名存在安全隐患，都可以通过修改曲线参数来增加破解难度。 在不知道P问题是否等同于NP问题的情况下，NP问题仍然是现代加密技术安全性的基本假设，这意味着问题本身非常复杂，我们永远无法解决它。

比特币中的数字签名

在本系列上一篇文章的结尾，我们说过比特币是一种基于密码学的计算机协议。 但不得不承认，一个可悲的事实是，比特币既不是一种数字货币比特币使用的数字签名方案叫什么，也不是一种信息，更不是哈希反转的解决方案。 它的本质只是一个庞大的信息链账本。 分类帐由无数（比特币）交易收据组成。 每一段交易码都有一个数字表示交易金额（比特币），看起来这个数字让人更安心。 这个账本大致是这样工作的：当学生A决定支付1个BTC给学生B时，他会从自己的比特币钱包中选择一个或几个“输入”，签署交易信息，并广播到比特币网络中，其他一些网络中的交易与coinbase交易一起组成一个区块（block），代表计算机计算能力的网络矿工验证（Bitcoin）区块中每笔交易的数字签名的有效性，正确确认后，在同时矿工获得coinbase交易输出的（比特币）奖励，交易码输出正常，接收方收到比特币。

一笔比特币交易的代码可以简写为CoinMaster的三部分，标记、输入和输出：

第一行是这笔交易的标记，“in”后面是交易的输入部分，“out”后面是交易的输出部分。 假设这是Alice发送给Bob的交易码，Alice的数字签名生成如下：

ECDSASig+PreTransaction_scriptPubKey构成本次交易的最终签名行scriptSig，记录为New_scriptSig。 值得一提的是，虽然两次Hash运算不一定能降低发现碰撞的难度，但可以防止SHA256长度扩展攻击的问题。 粗体表示交易的简化版（simplified version of the transaction），只是正式去除签名行，因为此时签名行本身还没有生成。 可以看到最后签名行的两个内容是：

比特币钱包Bitcoin-qt会在每笔交易的输出部分检查scriptPubKey比特币使用的数字签名方案叫什么，经过Hash运算后与钱包文件中本地存储的公钥Hash文件进行比较。 全网的算力主要消耗在数字签名（包括Hash）的验证过程中。 本次交易的最终哈希标记为：

tx_id=Hash(Transaction-scriptSig+New_scriptSig)

关于tx_id，bitcointalk上有两种说法。 另一种观点是 tx_id=Hash (Transaction-scriptSig)。 实际代码要复杂得多，需要进一步研究。 tx_id 的 Hash 函数输入是否包含 New_scriptSig 是 Mt.Gox 事件中声称的交易延展性问题的原因之一。 现在比较普遍的看法是，比特币数字签名部分的输入过于复杂，没有体现出目前复杂度的实际意义。

后记

限于篇幅，ElGamal和DSA不做详细介绍，其基本原理与RSA类似。 另外，Bitcoin-qt的版本变化暂未研究。 关于本文及后续内容，请各位阅读本文的朋友多提宝贵意见。 比特币：19fZ5WVfhrDToC3ioMFY71D1ARXsQJu8MK