蓑衣网比特币与密码学之数字签名
为什么需要签名
在生活中，我们经常会遇到需要签名的情况。比如用信用卡消费后，需要在单据的持卡人签名栏签上自己的名字，或者一些纸质单据在各种审批程序中需要领导签字。签字的目的是使文件/文件得到签字人的授权，使文件/文件所包含的权利和义务依法生效。通过签字，你承认你的信用卡消费，领导同意执行文件的内容。
理性来看，上述签名情节大致包含三个基本因素：
第一，签名能够代表签名人本人，个人签名笔迹的特殊性能够保证他人更难冒名顶替。如果有人冒充，一定能骗过中华人民蓑衣网小编2022共和国司法部的《笔迹鉴定规范》。第二，签名必须附有日期，日期代表授权内容的生效时间。通常，没有附加日期的签名不会被文件/文件接收单位识别。第三，签名的纸质文件整洁，即没有粘贴、污损、涂改，说明签名与文件完全相关。简单理解，数字签名就是计算机信息的数字签名，可以实现与文档/文件签名相同的功能：验证签名人的身份和签名时间，确认签名信息的正确性。数字签名通常用于发送方和接收方对相互传输的信息内容没有保密要求的情况(即明文传输)。数字签名有两种基本的生成方式：加密算法生成和签名算法生成。
加密算法生成的数字签名是基于哈希函数的，RSA和DSA签名算法属于这一类。Hash H是一个公共函数，用于将任意长度的信息M1映射成固定长度的值H(M1)，H(M1)也称为消息摘要。散列函数H的特征在于，当消息M1改变为M2时，H(M1)不等于H(M2)，即消息的任何改变都会改变消息摘要。发送方用公钥算法和自己的私钥对信息的哈希值进蓑衣网小编2022行加密，生成数字签名，即S=Sig(PrivateKey，Hash(M))，这是公钥算法的加密函数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)的输出为真，否则为假，即当另一个消息N被伪造时，Ver(x，S，N)的输出必然为假。
我们知道数学题很难，也很容易。利用大量的计算能力和时间，困难的问题可能得不到正确的结果。为了实现“已知M和S时不能反算X”的思想，我们需要找到一些合适的数学问题。
椭圆曲线数字签名算法
椭圆曲线数字签名算法基于椭圆曲线密码体制，签名方法类似于DSA数字签名算法。需要知道三个基础知识：有限域上的椭圆曲线，明文嵌入椭圆曲线，椭圆曲线上的离散对数问题。思路如下：
1)定义一组p元数，定义相应的加法等算术规则，然后定义椭圆曲线方程y 2=x 3axb，(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)。如果这两点不变，以上思路，加上ElGamal密码和DSA数字签名算法(略)，开始走上真正理解椭圆曲线数字签名的道路。在高效密码组标准的网站上有关于椭圆曲线密码和椭圆曲线签名的详细文档。比特币使用参数为secp256k1的Koblitz曲线(除了比特币将可选密钥限制为Koblitz椭圆曲线加密签名密钥的子集)。secp256k1的前三个字母是高效加密标准的缩写。P是指椭圆曲线参数有限域内素数的特征值，256是P的位数，K代表Koblitz曲线。secp256k1椭圆曲线有限域的阶p为：
p=2 256-2 32-2 9-2 8-2 7-2 6-2 4-1，
其他曲线的第一象限集合，集合的生成元和私钥。2t是不小于log (p)的最大整数，log是2的底对数。对于比特币中基于椭圆曲线密码体制的签名，这个数字大约是2 ^ 128，相当于发现SHA256碰撞的难度，破解时间是天文数字。目前攻击椭圆曲线上的离散对数问题的另一种方法是攻击任意循环群上的离散对数问题的大步进法。其计算时间复杂度为：
o(exp(log(Pmax(1/2)))
其中Pmax是椭圆曲线形成的循环群的阶的最大素因子。时间复杂度反映了执行算法所需的时间随着输入规模的增加而增加的幅度。很明显，这是一个指数时间，所以理论上，破解比特币的数字签名算法ECDSA目前还是一个NP问题，即没有多项式时间的解。只要比特币中的签名存在可能的安全风险，就可以修改曲线参数，增加破解问题的难度。在未知P问题是否与NP问题相同的情况下，NP问题仍然是现代加密技术安全性的基本假设，这意味着问题本身是如此复杂，我们永远无法解决。
比特币中的数字签名
在本系列上一篇文章的最后，我们说比特币是一种基于密码学的计算机协议。不得不承认，一个可悲的事实是，比特币既不是数字货币，也不是一条信息，更不是哈希求逆的解。本质上只是一个庞大的信息链账本，由无数(比特币)交易账单组成。每个交易码中都有表示交易金额的数字，看起来数字让人感觉更踏实。这个账本的工作原理大致是这样的：当同学A决定向同学B支付一个BTC时，他会从自己的比特币钱包中选择一个或几个“输入”，在这个交易信息上签名，并广播到比特币网络。网络中的一些其他事务与coinbase事务一起形成一个块。代表计算机计算能力的网络矿工验证(比特币)块中每笔交易的数字签名的有效性，无误后进行确认。同时矿工从coinbase交易输出中获得(比特币)奖励，交易码输出正常，接收者收到比特币。
比特币交易的代码可以简单记录为以下三个部分，标记，输入，输出：
{"hash": "7C4025 …"，" in": [？scriptSig''304502.“042b2d”】，“出”:[？script pubkey '' OP _ DUP OP _ hash 160 a7db 6 f OP _ equal verify？OP_CHECKSIG']}第一行是这个事务的标记，“in”后面是事务的输入部分，“out”后面是事务的输出部分。假设这是Alice发给Bob的一个交易代码，Alice的数字签名是这样生成的：
ECD sasig(hash(transaction-script SIG)，私钥)=ECD sasig(sha 256(transaction-script SIG)，私钥)，ECD sasig pre transaction _ script pubkey构成了这个交易的最终签名行，命名为new _ scriptSig。值得一提的是，虽然两次散列操作可能不会降低发现冲突的难度，但它可以防止对SHA256的扩展长度攻击。 粗体字体表示交易的简化版本，它只是正式删除了签名行，因为此时签名行本身还没有生成。可以看到，最终签名行的两个内容是：
1)本交易码中数字签名行scriptSig的所有其他输入输出的哈希值的椭圆曲线签名；2)用于验证数字签名的scriptPubKey。比特币钱包Bitcoin-qt会检查每个交易输出部分的scriptPubKey，对其进行哈希处理，并与钱包文件中本地存储的公钥哈希文件进行比较。整个网络的计算能力主要消耗在数字签名(包括Hash)的验证过程中。最终事务的哈希标志是：
tx_id=Hash(transaction-script SIG new _ script SIG)
bitcointalk中关于TX _ ID有两种观点，另一种观点是TX _ ID=Hash(transaction-script SIG)，实际代码要复杂得多，需要进一步研究。tx_id的Hash函数输入是否包含New_scriptSig是Mt.Gox事件中声称的事务扩展性问题的原因之一。目前普遍认为比特币数字签名的输入过于复杂，并没有表现出当前复杂性的实际意义。
后记
由于篇幅原因，不详细介绍ElGamal和DSA，基本原理和RSA差不多。另外，比特币-qt的版本变化也没有研究过。关于这篇文章以及后续的内容，请给看这篇文章的人你宝贵的意见。BTC:19fz 5 wvfhrdtoc 3 iomfy 71 D1 arxsqju 8 MK