数字签名背后原理

最近在学习区块链的知识，觉得其中的数字签名挺有意思的，想了解一下背后的大致数学原理。当然了，数字签名有很多种，一般采用非对称密钥密码体制来实现，常见的非对称加密算法有RSA和椭圆曲线加密算法，下面记录一下基于这两种算法的数字签名大致原理,注意，本文并不是在强调如何调用高级API，而是打算从数学原理出发。

RSA数字签名

该算法的数字签名原理比较简单，在此之前，我希望你了解一下什么是RSA算法，可以在之前的【文章】中找到该算法的介绍。

假设阿珍和阿强在通信，双方持有自己的私钥和对方的公钥。

在之前的【文章】中，我们证明了 $$ m^{e*d}\equiv m\pmod{n} \tag{1} $$ 其中<e,n>作为公钥，<d,n>作为对应的私钥。

我们假设<d,n>是阿强的私钥，<e,n>是其公钥，公钥在阿珍手上有相应的一份副本。

先来整理一下流程：阿强准备发送的消息是"我是阿强，我喜欢你！"，然后在后面附上了他的签名，接着将消息和签名进行简单整合:

{
    message: "xxx",
    signature: "yyy"
}

利用阿珍的公钥进行加密，然后传输到阿珍，阿珍收到了，利用她的私钥解密，是可以还原到原消息和一个签名。

{
    message: "xxx",
    signature: "yyy"
}

传输过程加密解密我们不关心，因为在之前介绍RSA的时候介绍过了，这里说一下签名的原理。

假设m是“我是阿强，我喜欢你！”的哈希值，阿强利用私钥对其求下面的式子： $$ c=m^d\pmod{n} $$ 阿珍解密传输信息后，一定可以解析到signature: "yyy"的，即可以获得到$c$。

阿珍要验证这句话是不是阿强说的，万一是隔壁老王说的呢，是吧？毕竟隔壁老王那里也有她的公钥呢。

验证过程很简单，她手上有阿强的公钥，她做一下运算： $$ m1=c^e\pmod{n}=m^{d*e}\pmod{n}\tag{2} $$ 根据式子（1）,我们很容易可以得到： $$ m1=m\pmod{n} $$ 因此她直接将之前得到的消息计算哈希值，跟数字签名部分进行对比，二者一致，则说明该消息的确是由阿强发出的，因为计算签名值的过程需要用到阿强的私钥，而该私钥只有他自己本人有，这就达到了防伪造的目的。

实际上，如果我们把流程再次简化，即阿强向大家（其他人有阿强的公钥）宣布“我是阿强，我喜欢阿珍！”，其他人收到消息后，只要利用阿强的公钥计算，即可验证阿强一定有说过这句话，无法抵赖！

椭圆曲线算法数字签名

在此之前，我们先来了解一下【椭圆曲线加密原理】，其也是利用了“根据公钥，难以反推私钥”来达到安全目的，相比于RSA，可以使用更短的密钥实现同等的安全强度，区块链中用的数字签名算法就是椭圆曲线加密算法。

假设还是刚刚的阿强和阿珍的场景，阿强的私钥为$k_a$，公钥为$p_a=k_a\cdot G$.

签名过程

该过程由阿强完成，流程如下：

1. 先随机产生一对公私钥，即$K$和$P=K\cdot G$
2. 然后将随机产生的公钥的X坐标拿出来，即$r=x_P \pmod {n}$。
3. 计算$S=(K^{-1}(hash(m)+k_a \cdot r)) \pmod{n}$，其中$K^{-1}\cdot K=1\pmod{n}$的逆元。
4. $r$和$S$作为签名结果。

验证过程

该过程由阿珍完成，流程如下：

1. 计算$\alpha=(S^{-1}\cdot hash(m))\pmod{n}$
2. 计算$\beta=(S^{-1}\cdot r)\pmod{n}$
3. 计算$Y=(\alpha \cdot G+\beta \cdot p_a)\pmod{n}$
4. 如果点$Y$的X坐标和$r$相同，则验证通过

下面我们来证明第四点：

对于签名过程的第3点的式子，我们两边同乘$S^{-1}\cdot K$，得到 $$ K=(S^{-1}\cdot(hash(m)+k_a\cdot r))\pmod{n}\tag{3} $$ 继续将验证过程的第一点第二点代入到第三点中，有： $$ Y=(S^{-1}(hash(m)\cdot G+r\cdot p_a))\pmod{n} $$ 同时注意到，$p_a=k_a\cdot G$，代入到上市，有 $$ Y=(S^{-1}(hash(m)+r\cdot k_a)\cdot G)\pmod{n} \tag{4} $$ 结合式子（3）和式子（4），我们有 $$ Y=K\cdot G \pmod{n}=P\pmod{n} $$ 进而证明了第四点。