ECDSA签名算法原理
阿牛哥 Lv4

非对称密钥的加密算法除了能在通信中用于加密数据外,还能用于数字签名,这一点是对称密钥加密实现不了的。

什么是数字签名

和现实世界中的签名一样,在文件上签名表示这份文件中的内容由署名者自己作出或者决定,而非其他人伪造的,所以签名是一个确认身份的过程。

在数字世界,同样会遇到需要签名的情况,如何实现数字签名曾经是个问题,直到出现了非对称加密算法,数字签名才成为可能。

和现实世界一样,对文件签名并不意味着文件内容需要保密,签名只是为了确认身份,数字签名设计也遵循相同的性质。

什么是ECDSA?

ECDSA, Elliptic Curve Digital Signature Algorithm

ECDSA是Elliptic Curve Digital Signature Algorithm(椭圆曲线数字签名)的缩写,通过ECC算法实现数字签名。

ECDSA的基本思路是这样的:假设甲和乙通信,甲发送给乙消息后,乙需要确认消息内容确实是甲做出的,那么甲需要对消息签名,乙收到消息后需要验证签名。如果验证失败,那么乙就能得知此消息并非甲签署的;而如果验证成功,则表示乙可以相信该消息。

ECDSA消息签名和验证

ECC加密简单回顾

上一篇文章《椭圆曲线加密算法原理》描述了ECC加密的过程和数学证明。ECC加密的私钥和公钥的关系如下:

Q=kPQ = kP

其中,整数 kk 是私钥,点 PP 是基点,点 QQ 是公钥。

通过 kk PP 可以快速计算出 QQ ;而在已知公钥的情况下,计算私钥 kk 却非常困难,这构成了ECC加密安全性的基础。

ECDSA数字签名的过程

乙要验证甲发送的消息,双方需要在通信之前先确定两个参数:一是对消息进行摘要的哈希函数 Hash(x)Hash(x) ,二是乙需要通过某种途径预先知道甲的公钥。

甲计算签名的过程:

  1. mm 为甲要发给乙的消息,消息的哈希值是 h=Hash(m)h = Hash(m)

  2. 选择一个随机数 tt ,计算 O=tPO = tP

  3. 设点 OO 的坐标为 (x1, y1)(x_1,\ y_1) ,计算 r=x1 mod pr = x_1 \ mod \ p

  4. 计算 s=t1(h+rk) mod ps = t^{-1}(h + rk) \ mod \ p

(r, s)(r,\ s) 即为甲的签名

乙验证签名的过程:

  1. 计算消息 mm 的哈希值 hh

  2. 计算 u1=s1h mod pu_1 = s^{-1} h \ mod \ p

  3. 计算 u2=s1r mod pu_2 = s^{-1} r \ mod \ p

  4. 计算 O=u1P+u2QO' = u_1 P + u_2 Q

  5. 确认 O=OO' = O ,即 OO' 点的横坐标 x1x_1' rr 满足关系 r=x1 mod pr = x_1' \ mod \ p ,若等式成立则表明 x1=x1x_1 = x_1' ,于是甲的签名验证通过

数学证明

接下来,我们证明ECDSA签名在数学上的正确性。

要证明以上过程正确,就是要证明

u1P+u2Q=Ou_1 P + u_2 Q = O

证明:

u1P+u2Q=u1P+u2kP=(u1+u2k)P=(s1h mod p+(s1r mod p)k)P=(s1(h+rk) mod p)P=t t1(s1(h+rk) mod p)P=t(s1t1(h+rk) mod p)P=t(s1s)P=tP=O\quad u_1 P + u_2 Q \\ = u_1 P + u_2 kP \\ = (u_1 + u_2 k)P \\ = (s^{-1} h \ mod \ p + (s^{-1} r \ mod \ p) k)P \\ = (s^{-1} (h + rk) \ mod \ p)P \\ = t \ t^{-1}(s^{-1}(h + rk) \ mod \ p)P \\ = t(s^{-1}t^{-1}(h + rk) \ mod \ p)P \\ = t(s^{-1}s)P \\ = tP \\ = O

证明完毕!