ECDSA

椭圆曲线签名算法(Elliptic Curve Digital Signature Algorithm)简称 ECDSA, 是一种基于椭圆曲线的数字签名算法。

假设有通信双方 A 和 B, 已知椭圆曲线 $E_p(a, b)$ 、基点 $G$、 $G$ 的阶 $n$, 要签名的消息 $m$。

A 首先生成自己的私钥和公钥, 即从 $\{1,\cdots,n-1\}$ 随机选择一个数 $k_A$ 作为私钥, 公钥 $H_A=k_AG$

A 签名过程如下:

• 在$\{1,\cdots,n-1\}$ 中选择另一个随机私钥 $k$

• 计算公钥 $R$ 的坐标: $R = kG$, 取 $R$ 的 $x$ 坐标为 $r$。 若 $r=0$, 则重新选择一个 $k$ 并重新计算

• 计算 $s = k^{-1}(m + rk_A) \mod \ n$, 若 $s=0$, 则重新选择一个$k$ 并重新计算

最后组合 $r$ 和 $s$ 即为最终的签名数据。

为了验证签名，需要将 A 的公钥 $H_A$, 消息 $m$，签名数据 $r$ 和 $s$ 发送给 B

B 验证签名过程如下:

• 计算$u_1 = s^{-1}m \mod \ n$
• 计算$u_2 = s^{-1}r \mod \ n$
• 计算$P = u_1G + u_2H_A$, 若 $P$ 的 $x$ 坐标等于 $r$ 则签名有效。

证明:

由于$s=k^{-1} (m+rk_A) \mod\ n$

所以$P=(m+rk_A) \frac {k}{m+rk_A}G = kG$, 因此如果签名正确, 则 $P$ 的 $x$ 坐标等于 $r$。

以一个实际的例子介绍 ECDSA 签名过程:

已知椭圆曲线 $E_{17}(2,3): y^2=x^3+2x+3$

选择基点 $G=(5, 6)$, $G$ 的阶 $n=22$, 要签名的消息 $m = 33$

A 签名

• 在 $[1, 21]$ 选择 7 作为私钥，则公钥 $H=kG=7(5, 6)=(9, 6)$
• 在 $[1, 21]$ 选择随机数 $k=5$
• 计算 $P=kG = 5(5, 6) = (2, 7)$, 得到 $r=2$
• 计算$s = k^{-1} (m+rk_A) \mod\ n = 9 * (33 + 2 * 7) \mod 22 = 423 \mod 22 = 5$
• 发送$(r, s)$ 、A 的公钥$H_A$、消息$m$ 给 B

B 验证签名

• 计算$u_1=s^{-1}m \mod n = 9 * 33 \mod 22 = 11$
• 计算$u_2 = s^{-1}r \mod n = 9 * 2 \mod 22 = 18$
• 计算$R = u_1G + u_2H_A = 11(5, 6) + 18(9, 6) = (16, 0) + (12, 15) = (2, 7)$
• $R$ 的 $x$ 坐标等于 $r$, 签名有效