本期将为大家讲解，数字签名与比特币的爱恨纠缠。
首先我们来看下什么叫数字签名。如果前文提到的，现在安全我们得用一个非常严格的定义来描述它，因此，这里我们假设几个变量，首先是密钥生成器keygen(pk,sk),可以看到的是这个函数能够生成一对密钥对，目前我们先假装不知道它这个函数里面到底是怎么实现的。我们假设这个密钥生成器是按照二进制，或者说更简单一点，它就是n个1组成的一串序列，n是一个未知的数字。学过密码学的同学都知道，用私钥去加密，就是一个签名的过程。现再假设一个恶意攻击者，他叫bob。好人alice可以从密钥生成器这里获取到密钥对，正常情况下，用私钥加密（签名），公钥解密（验证），若通过，则说明签名有效。可以写成这样的形式：alice的签名 = Sign(sk_alice,m_alice)
以上，很好理解，它就是一个正常的签名过程。
所以有如下定义：我们要求 bob的伪签名 = Sign(sk_alice,m_bob) <= negl(n),这里的意思是说，bob通过未知的手法，更改了alice的签名，但是这个bob的伪签名是有效并且是全新的（指向alice签名的），我们要让这个概率小于等于一个微小函数。看到这里的小伙伴或许有些迷茫，为什么bob知道alice的私钥呢，这里我们只是假设，有这么一种情况，甚至可能，在bob未获取alice的私钥的情况下，依旧达到了这个效果也就是利用新的签名和新的消息验证成功，那么，我们认为，bob它攻击成功。如果最后我们发现这个概率是一个微小函数，那我们就可以说，他是一个：对所有的无限时间和无限算力的恶意攻击者都有这么一个不等式，也就是 恶意攻击者伪造数字签名成功的几率 <= negl(n),也就是小于微小函数。
通过前面的阐述，小伙伴们已经大致知道了，对于数字签名的严格定义。接下来，我们就以开发者或者创世者的角度思考，如果，我想要达到这么一个目的，我该如何做呢？要让人很难从这个结果中推出我们的私钥，聪明的开发者想到了，离散对数问题。
通常来说我们很容易计算 y=g^x , 当我们知道g ，知道x，y是很容易就算出来了，但是如果我们知道y，知道g，想要推出x，这就有点难了。至此，其实使用椭圆曲线算法的雏形已经出现，学过一些初等数论的同学肯定知道，我们上面提到的这个g就很像群里面的这个生成器，没学过的同学也别慌，其实不用过多的去考虑它群的性质，我的理解比较粗暴，我认为当我们做交易时，这个私钥也好，公钥也好，我肯定希望它是个整数，如果它是个小数就会很尴尬，因为会提升计算量，举个例子，比方说2^10次方，我可以在代码里这么算2*2*2。。。就这么乘10次，但如果2的10.83456次方，不管怎么说，它的计算量就变大了，我们不想搞这么复杂，于是就想用整数，但是使用整数又出现一个问题，如果它太小，那么很容易爆破，我从1开始爆破，就正整数一个一个试验，就很容易就能试验出来，而这里又牵涉到这个密钥空间大小的问题，当密钥空间大小至少为多少时，我们才能保证安全呢？
这里就不证明一遍了，有兴趣的同学留言，我可以专门再写一篇，这里给出结论，只有当密钥空间最少等于明文长度时，才能保证安全，原因是因为，我们必须保证，明文的分布概率，与（在生成密文下的明文分布概率相同），更通俗易懂的解释是，如果维吉尼亚密码的密钥是很短的，也就是说会有可能我同样的明文用了相同的密钥加密，那么我通过词频分析等手段，是不是就可以一定程度上推断出你的那个位置上的那个字母是啥。那么问题又来了，如何能够在减少密钥长度的情况下，我还能利用这个离散对数问题，还能使用这个特性来做签名呢？
答案就是ECDSA，全称叫Elliptic Curve Digital Siganature Algorithm，椭圆曲线数字签名算法。不过上次预告说了，主要说schnorr siganature，所以椭圆曲线先讲到这里。顺带提一句，这个算法确实是现在比特币正在使用的，并且使用了Secp256k1密钥对，根据维基百科的解释，在比特币变流行之前，这个secp256k1都没被用过，一直到比特币流行了之后，然后它的特点之一就是会构造一个非随机的曲线，也就是说，它计算起来比较快。然后我们还是回到schnorr signature上来，这个传说是比特币官方一直都想替代ECDSA的一个算法，但为啥没有用它呢，就是因为它没有被标准化，不在标准的加密算法库里，那开发人员也不好写，但是跟ECDSA比起来它还是有很多优点，比方说，它在数学逻辑上可以被证明是安全的，但是ECDSA却做不到，然后它体积也小一点，唯一缺点就是还没标准化。好了，接下来看算法了。
假设几个变量: G ， G是由素数q构成的群 ，g ，还是生成器。 H（），是一个哈希函数。
先，我们从[0,q-1]随机取一个整数x，私钥sk=x，计算公钥pk=g^x，现有密钥对(sk,pk),也就是（x,g^x）。
签名过程，用私钥x，对我们的消息m签名。取随机数r，有R=g^r , c= H(m,R)=H(m,g^r) ,计算 s = r + xc mod q , 输出 签名=（c,s）。
如何确认？我们知道的参数有pk，m，(c,s) ,确认c和s是不是这个群里的元素，如果G是一条椭圆曲线，那么就是看这俩是不是曲线上的点。另外还需要验证的是：是否 c = H(m, g^s pk^-c) mod q ？
因为由上面可以知道， c = H( m, g^r )=H( m , g^(s-xc)) = H( m, g^s *g^x^-c) = H(m,g^s*pk^-c)
我们把安全性相当于压在，这个G的离散对数问题上。
#关于组签，为什么我们要使用组签呢，我觉得有两点，一点是节约了空间，本来一笔交易就需要一个签名，现在我把一组人的签名，利用schnorr签名的线性特性，使其相加，（从上面的式子我们可以看到，是线性的，所以容易相加），这样既节约了空间，又保证了匿名性，因为你没法反向推算是哪几个子签名，但是最后还是容易验证。目前来说它是一种优于ECDSA的算法。
本期对于数字签名的定义，及对schnorr签名的描述就到这里了，下期看点，比特承诺。
p.s 如果版主看到的话，请问下如何才能加精，在这个板块发表也有可能加精吗？？想要获得rank- -
最后，如有不严谨或有错误请不吝赐教，感谢大家。
[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！
