BTC.com手机客户端

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

沣述 发布在 技术指南 24 9697

为什么需要签名

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

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

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

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

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

版权声明: by nc" sa 作者保留权利。文章为作者独立观点,不代表巴比特立场。

评论:24

您需要登录后才可以回复 登录|注册
    Author Image
    马伯 937 天前

    1)公钥和私钥可以取什么值有条件吗?有一个函数f(私钥,随机数)就可以生成公钥了吗?
    2)别人没有私钥,如何验证签名是你签的?
    3)x(m,k)是一个什么样的函数?kX(m0,k) 是常数k 乘以X(m0,k)吗?那么必须是知道m0要解方程X(m1,k)=kX(m0,k)才能得到确定的m1吗?也就是m1不可以随便取值,对吧。

    +1
    +1
    我要点评
      Author Image
      StandardCAT 936 天前

      第二个我也想问。一般办法是,签名用公钥签,加密才用私钥加密,公钥是大家都看得到的。为了保证公钥的真实性,一般会引进证书机制,但是比特币好像不是这样解决的。

      +1
      +1
      我要点评
        Author Image
        BigChubbyCat 936 天前

        ……….这片文章的评论,我已经没有智力理清关系了。。。有压力。

        +1
        +1
        我要点评
      Author Image
      沣述 936 天前

      1. 私钥是伪随机数d,公钥Q是这个随机数d与椭圆曲线第一象限点集合的生成元G的点乘,Q=dG;
      2. 网络节点验证还是用发送方的公钥Q来验证的啊,椭圆曲线数字签名属于数字签名的第一种生成方式;
      3. 实际是这样的: x={mk+j, j=0,1,…},是一个集合,集合的最大的数是x0,则(x0)^3+a(x0)+b是模p的平方根。

      我不忍心直接让你去看公式,但我发现不写公式还是讲不清楚。
      看看这个:SEC 1: Elliptic Curve Cryptography,http://www.secg.org/collateral/sec1_final.pdf
      本文力求理出一个简洁的思路,更加详细的分析还需我练练功力,后续加以完善。

      +1
      +1
      我要点评
        Author Image
        BigChubbyCat 936 天前

        @沣述 ….密码专业。。。是数学系的一个分支吗?膜拜。。。。

        +1
        +1
        我要点评
          Author Image
          沣述 935 天前

          把数学一级学科分为分析、代数、统计、方程、几何的话,密码学属于代数方向,研究和分析密码算法主要使用数论、抽象代数、符号计算、代数几何等理论,所以学密码的基本都到本科之后了。

          +1
          +1
          我要点评
        Author Image
        StandardCAT 936 天前

        我没看懂,回头翻下密码学的书…椭圆曲线那章我没看过。但是隐约感觉公钥的真实性(即不被冒名者复制)和算法原理是不相关的。下次你要解释可以用LaTex/Markdown,我有浏览器插件。回复里写的公式实在是没看懂。

        +1
        +1
        我要点评
          chehw
          chehw 935 天前

          对签名算法的简化表述:
          公钥:y。一个65字节(非压缩)后33字节(压缩)的数字。
          私钥:x。一个32字节(256二进制位)的数字。
          密钥生成算法:一个数学公式,用于通过私钥换算出公钥,类似于 y = f(x)。比特币使用的是ECDSA算法。
          签名(sig):sig = x(msg) , y(sig)=msg

          验证签名时提供的已知项: sig(签名),y(pubkey,公钥), msg(交易原始数据的hash值)
          如果用y和sig通过公式运算,得到的结果与msg一致,则该签名必为x(私钥)签署的。

          +1
          +1
          我要点评
            Author Image
            StandardCAT 935 天前

            懂了。

            +1
            +1
            我要点评
            Author Image
            巴比特资讯 935 天前

            …..佩服@chehw

            +1
            +1
            我要点评
            Author Image
            沣述 935 天前

            “……,则该签名必为x(私钥)签署的。”
            你这句话的逻辑不对,应该说只要是私钥签署的,那么就能够用对应的公钥完成验证。

            +1
            +1
            我要点评
            Author Image
            BigChubbyCat 934 天前

            。。…..@chehw_1 好像也是搞密码学的。

            +1
            +1
            我要点评
          Author Image
          沣述 935 天前

          好的,担心公式多了没人看哈。我发现要把算法用一种简洁又不失准确的方式描述出来还需要增加功力。

          +1
          +1
          我要点评
            Author Image
            BigChubbyCat 935 天前

            很多兴趣,真的和个人经历有关系,和智力差距反而不是很大。我记得在校读书的时候,有那么一段日子,也沉迷过数学……但因为各种其他原因,最终不再关注这些东西。长时间不关注,就不会产生疑问,没有了疑问,也就失去了兴趣,也就无法体会研究者的乐趣。

            +1
            +1
            我要点评
    Author Image
    BigChubbyCat 937 天前

    aec2cef03b531864a4cf40e22fe05ca38395a778875a1693ce6eb4547dccfa3e-000

    +1
    +1
    我要点评
      Author Image
      沣述 936 天前

      谢谢CAT

      +1
      +1
      我要点评
    Author Image
    沣述 937 天前

    1. D=Ver(S,PublicKey)中PublicKey是该加密算法的公钥,加密算法有两个函数分别用于加密和解密;
    2. 对于基于签字算法的数字签名,只要一个密钥x,只有签字者可以进行验证;
    3. 是这样的:“计算明文m的函数x(m)”,应该是计算一个二元函数x(m,k);
    4. 首先X(m1)=kX(m0),Y(m1)=kY(m0)与Q=kP不等价,所以写X(m1)=kX(m0)这样的式子无意义。
    (0,0)是指坐标原点,而这里的加法的定义只针对曲线上的点,除非曲线经过原点,即b=0。

    你很细心啊,最后一个问题我前几天也注意到了,但是看到帖子已经沉了就没有再改正了,本来准备下次有机会的时候和其他不是很细致流畅的地方一起再修改。

    +1
    +1
    我要点评
      Author Image
      BigChubbyCat 936 天前

      …………..@沣述 是搞科学计算的??…觉厉

      +1
      +1
      我要点评
        Author Image
        沣述 936 天前

        以前上研究生的时候是密码专业

        +1
        +1
        我要点评
    Author Image
    马伯 937 天前

    D=Ver(S,PublicKey)中PublicKey是什么》是否就是Hash(M)?

    Ver(x,S,M)中,x是否是私钥?如果是,是否只有自己可以Ver?

    “设定一个较大的整数k,计算明文m的函数x(m),这里的x是椭圆曲线方程里的x。之后通过曲线方程得到y(x),于是生成一个数对(x(m),y(m))。这个过程表示消息m嵌入到曲线上;”中,k是什么?X(m1)=kX(m0),Y(m1)=kY(m0),表示{X(m1),Y(m1)},{X(m0),Y(m0)},{0,0}在一条直线上吗?

    椭圆曲线和H(),Sig(),Ver()是什么关系?

    +1
    +1
    我要点评
    龙蓉阁
    龙蓉阁 941 天前

    //@魔力大熊: 每次看@沣述 @昌用 老师都是种享受;能深入浅出的把一件事讲明白,很考验功底,又学习了。

    +1
    +1
    我要点评
    魔力大熊
    魔力大熊 941 天前

    每次看@沣述 @昌用 老师都是种享受;能深入浅出的把一件事讲明白,很考验功底,又学习了。

    +1
    +1
    我要点评
    巴比特资讯
    巴比特资讯 941 天前

    【@沣述 :比特币与密码学之数字签名】数字签名就是对计算机信息的数字化签名,可以实现与单据/文件签字一样的作用:验证签字者的身份和签字时间,证实被签信息的正确性。本文详细介绍了数字签名的基本生成方式:由加密算法产生和由签名算法产生,及比特币中的数字签名 http://t.cn/8seKCwP

    +1
    +1
    我要点评
    沣述
    沣述 942 天前

    系列文章第二篇:《比特币与密码学之数字签名》,http://t.cn/8seKCwP

    +1
    +1
    我要点评