为什么需要签名

在生活中，我们经常会遇到需要签名的情况，例如用信用卡刷卡消费后需要在单据的持卡人签名栏签自己的名字， 又或者在各种审批程序中有些纸质文件需要找领导签名。签名的目的是为了使单据/文件得到签字人的授权，从而单据/文件内容所包含的权利与义务依法生效。签了字，代表你承认自己的此次信用卡消费，领导同意文件内容的实施。

理一理，上述签字情节中大致包含了三个基本因素：

• 一是签字能够代表签字者本人，个人签字字迹的特殊性可以保证他人冒充的难度较大。如果有人冒充，那么必须能够骗得过中华人民共和国司法部的《笔迹鉴定规范》。
• 二是签字的同时必然要附上日期，日期代表授权内容的生效时间。通常情况下，没有附加日期的签名是不被单据/文件接收单位认可的。
• 三是签字纸质文件是整洁的，即没有粘贴，没有污损，没有涂改，这表示签名与单据文件是完整关联的。

简单理解，数字签名就是对计算机信息的数字化签名，可以实现与单据/文件签字一样的作用：验证签字者的身份和签字时间，证实被签信息的正确性。数字签名通常应用在发送方和接收方对相互传送的信息内容没有保密性要求的情况下（即明文传送），有两种基本的生成方式：由加密算法产生和由签名算法产生。

由加密算法产生的数字签名建立在Hash函数的基础上，RSA和DSA签名算法就属于这一类。Hash函数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数字签名算法，需要了解三项基础知识：有限域上的椭圆曲线，明文嵌入椭圆曲线，椭圆曲线上的离散对数问题。思路如下：

• 1）定义一种p进制的数字集合，定义加法等相应的运算法则，再定义系数和变量属于这个集合的椭圆曲线方程y^2=x^3+ax+b，(4a^3+27b^2不为0)；
• 2）设定一个较大的整数k，计算明文m的函数x(m)，这里的x是椭圆曲线方程里的x。之后通过曲线方程得到y(x)，于是生成一个数对(x(m),y(m))。这个过程表示消息m嵌入到曲线上；
• 3）假设对这个曲线上的点P=(X(m0),Y(m0))，Q=(X(m1),Y(m1))来讲有，X(m1)=kX(m0)，Y(m1)=kY(m0)，如果这两个点都是常量，那么通过P和Q求解k很困难，这个问题称之为椭圆曲线上的离散对数问题。

上述思路加上ElGamal密码和DSA数字签名算法（略），就开始走上真正理解椭圆曲线数字签名的道路了。高效密码标准工业共同体（Standards for Efficient Cryptography Group）网站上有关于椭圆曲线密码及椭圆曲线签名的详细文档。比特币中使用的是参数记为secp256k1的Koblitz曲线（只不过比特币将可选密钥限制为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问题仍是现代加密技术安全性的基础假设，意味着问题本身过于复杂以至于使得我们永远没有能力去解决它。

比特币中的数字签名

在本系列文章上一篇的最后，我们说比特币是一个基于密码学的计算机协议。可不得不承认，一个令人忧伤的事实是，比特币既不是指数字化的币，也不是一段信息，不是Hash求逆的解，它的本质只是一个庞大的信息化的链条式的账本，这个账本由无数的（比特币）交易账单组成。每一段交易代码里面都有标明（比特币）交易数额的数字，似乎数字看起来才让人感觉比较踏实。这个账本大致是这么运行的：当A同学决定把1个BTC付给B同学时，他会从自己的比特币钱包中选择一个或几个“输入”，把这个交易信息进行签名，再广播至比特币网络，网络中的其他一些交易与coinbase交易一起构成一个区块（block），代表计算机算力的网络矿工对（比特币）区块内每个交易的数字签名的有效性进行验证，正确后进行确认，同时矿工获得coinbase交易输出的（比特币）奖励，交易代码输出正常，接收者收到比特币。

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

• {“hash”:”7c4025…”,
• “in”:[
•     "scriptSig":"304502... 042b2d..."],
• “out”:[
•      "scriptPubKey":"OP_DUP OP_HASH160 a7db6f OP_EQUALVERIFY          OP_CHECKSIG"]}

第一行是本次交易的标记，“in”后面是交易的输入部分，“out”后面是交易的输出部分。假设这是一个Alice发给Bob的交易代码，Alice的数字签名是这样产生的：

• ECDSASig (Hash(Transaction-scriptSig), Private Key)
• =ECDSASig (SHA256(SHA256(Transaction-scriptSig)), Private Key)，

ECDSASig+PreTransaction_scriptPubKey构成了本次交易最终的签名行scriptSig，记为New_scriptSig。值得一提的是，虽然两次Hash运算不见得会降低寻找一个碰撞的难度，但却可以预防对SHA256进行延伸长度攻击的问题。粗字体表示的是本次交易的简化版本（simplified version of the transaction）,这只是形式上把签名行去掉，因为此时签名行本身还没有生成。可以看到最终的签名行的两项内容分别是：

• 1）本次交易代码中的不包括数字签名行scriptSig的其余所有输入输出的HASH值的椭圆曲线签名；
• 2）用来验证数字签名的scriptPubKey。

比特币钱包Bitcoin-qt会检查每个交易输出部分的scriptPubKey，对其进行Hash运算后和钱包文件中的本地存储公钥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的版本变迁。关于本篇和后续内容，请阅读本文的诸位多提宝贵意见。BTC：19fZ5WVfhrDToC3ioMFY71D1ARXsQJu8MK