要么改变世界,要么适应世界

数字签名背后原理

2022-10-29 23:36:33
54
目录

最近在学习区块链的知识,觉得其中的数字签名挺有意思的,想了解一下背后的大致数学原理。当然了,数字签名有很多种,一般采用非对称密钥密码体制来实现,常见的非对称加密算法有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} $$ 进而证明了第四点。

历史评论
开始评论