比特币与密码学之数字签名

区块链技术巴比特2017-11-25 06:48:18  阅读 -评论 0

为什么需要签名

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

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

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

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

由加密算法产生的数字签名建立在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

声明:链世界登载此文仅出于分享区块链知识,并不意味着赞同其观点或证实其描述。文章内容仅供参考,不构成投资建议。投资者据此操作,风险自担。此文如侵犯到您的合法权益,请联系我们100@7234.cn

    参与讨论 (0 人参与讨论)

    相关推荐

    区块链投资趋势报告:巨头入场布局行业趋于成熟

    区块链投资趋势报告:巨头入场布局行业趋于成熟

    来自:https://mp.weixin.qq.com/s?__biz=MzI4NzIxOTY1NA==&mid=2650632639&idx=1&sn=e6d1c29731d992a80410aaee82ec3ea6&chksm=f3d8db16c4af520097e4a64a71b1d4743ac326b9f027

    重新发明货币

    重新发明货币

    一、货币的演化过程 先简单回顾一下人类货币的演化过程,大概有以下阶段: a. 1.0版本:自然货币(贝壳、牲口、金银……) 这个阶段,货币基于一般等价物的稀有性或者实用性,货币不可能出现人为操纵的超发。 b. 2.0版本:早期纸币、银票到本位纸币 当贸易量越来越大,实物货币太不方便了,而且大家发现其实并不在意货币本身有什么价值,在意的只是这么多的货币能不能交换到足够的物品,于是纸币这种信用货

    从比特币交易看欧洲央行虚拟货币分类

    从比特币交易看欧洲央行虚拟货币分类

      互联网对传统社会的颠覆从未停止,在其完成对信息流、商流、物流、资金流的初步改造之后,或将以虚拟货币的形式打破现有货币体系   4月18日,在中国极客张沈鹏创办的比特币交易平台(42BTC.com)上,比特币对人民币的平均交易价为576元。当天,该平台完成了100个比特币的交易量。仅仅过去一周,4月25日上午,比特币对人民币的平均交易价已达到906元。据42BTC网站统计:在过去的32个月

    欧洲央行-比特币报告

    3.1 比特币 3.1.1 基本特征          比特币可能是最成功的,也可能是最有争议的虚拟货币方案,由日本程序员中本聪(译者注:事实上,中本聪是不是日本人,甚至是不是单个人无从考证)在2009年设计并实现。该计划基于一个类似于BitTorrent的P2P网络。BitTorrent是互联网上著名的共享文件协议,应用在电影,游戏和音乐领域。比特币在全球层面上运作,可用于各类货币交易(虚

    彻底玩转比特币地址和私匙

    彻底玩转比特币地址和私匙

    比特币地址和私匙是所有比特币初学者面对的一大难题,再加上那一串超长的字符串,让人更是摸不到头脑。 现在编者以问答的形式,带你一步步的揭开比特币地址和私匙的面纱。 还不知道什么是比特币地址和私匙的同学请点这里 问题一、比特币钱包由什么组成? 答 我们知道,比特币地址和私匙组成了比特币钱包,而私匙则决定了比特币地址上比特币的归属。 地址和私匙 问题二、如果只记得私匙我们还能还原比特币地址么? 答

    用GO语言实现比特币算法

    用GO语言实现比特币算法

    本节的这个例子展示一点点高精度数学包math/big、一点点散列包hash、一点点加密包crypto,还有一点点测试包testing的知识。这里不介绍bitcoin协议和算法——尽管它们很有趣,而是试图指出,Go对多种操作系统的支持,是实现这种跨平台应用的理想语言。 位钱(bitcoin)是一种使用加密手段制作的分布式电子货币。它最初于1998年由Wei Dai提出,并由中本聪(Satoshi

    详解比特币的找零机制

    详解比特币的找零机制

    比特币的找零机制一直让人有些迷惑,明明只向一个地址发送了比特币为什么 blockchain 上面的显示的有时是1个地址对多个地址,有时是多个地址对1个地址,有时又显示多个地址对多个地址? 为什么比特币资深用户要提醒大家当比特币钱包交易100次以上时再次交易后要重新备份钱包,恢复以前的钱包备份有可能会遭遇损失? 是的,这一切都是因为比特币的找零(Change)机制。本文参考 Bitcoin的维

    玩转比特币客户端之一:C盘转移和加速下载

    玩转比特币客户端之一:C盘转移和加速下载

    C盘空间不足?交易数据下载速度太慢?别着急,乐享比特币教你轻松玩转比特币官方客户端。 所有新人开始接触比特币时做的第一件事情大多数是安装比特币的官方客户端。 安全起见大家最好直接访问官方发布渠道sourceforge的地址进行下载:http://sourceforge.net/projects/bitcoin/files/Bitcoin/ 该网页列出了各版本的官方比特币客户端,目前

    麦妖榜
    更新日期 2019-03-21
    排名用户贡献值
    1BitettFan23752
    2等待的宿命23696
    3六叶树20309
    4天下无双16192
    5区块大康15902
    6lizhen00214889
    7让时间淡忘14256
    8linjm122712327
    9冷风大q11188
    10momo11174
    返回顶部 ↑