阅读 320

ECDSA详解

ECDSA(Elliptic Curve Digital Signature Algorithm),椭圆曲线数字签名算法。

椭圆曲线数字签名生成

假设Alice希望对消息m进行签名,所采用的椭圆曲线参数为D=(p,a,b,G,n,h),对应的密钥对为(k,Q),其中Q为公钥,k为私钥。

Alice将按如下步骤进行签名:

  1. 产生一个随机数d1 \leq d \leq n-1. (签名算法首先生成一个临时私公钥对,该临时密钥对用于计算rs值。)
  2. 计算dG=(x_1,y_1),将x_1转化为整数\overline{x_1}.
  3. 计算r=\overline{x_1} \ mod \  n,若r=0,则转向第1步. (r值为临时公钥的x坐标值)
  4. 计算d^{-1} \ mod \ n.
  5. 计算哈希值H(m),并将得到的比特串转化为整数e.
  6. 计算s=d^{-1}(e+kr) \ mod \ n,若s=0,则转向第1步.
  7. (r,s)即为Alice对消息m的签名.

d^{-1} is the multiplicative inverse of d modulo n.逆元。

椭圆曲线签名验证

为验证Alice对消息m的签名(r,s),Bob需要得到Alice所用的椭圆曲线参数D=(p,a,b,G,n,h)以及Alice的公钥Q

步骤如下:

  1. 验证rs是区间[1,n-1]上的整数.
  2. 计算H(m)并将其转化为整数e.
  3. 计算w=s^{-1} \ mod \ n.
  4. 计算u_1=ew \ mod \ n以及u_2=rw \ mod \ n.
  5. 计算X=(x_1,y_1)=u_1G+u_2Q.
  6. X=O,则拒绝签名,否则将Xx坐标x_1转化为整数\overline{x_1},并计算v=\overline{x_1} \ mod \ n.
  7. 当且仅当v=r时,签名通过验证.

椭圆曲线签名正确性

要证明v=r,只需要证明X=dG即可。

证明步骤:

令:C=u_1G + u_2Q = u_1G+u_2kG=(u_1+u_2k)G

u_1u_2带入:C=(ew+rwk)G=(e+rk)wG=(e+rk)s^{-1}G

s=d^{-1}(e+kr) \mod  n得出s^{-1}=d(e+kr)^{-1} \mod n,带入: C=(e+kr)d(d+kr)^{-1}G = dG

证明完毕。

参考文档:
Elliptic Curve Digital Signature Algorithm
Elliptic Curve Cryptography: ECDH and ECDSA
Understanding How ECDSA Protects Your Data.