ECDSA算法（深入浅出密码学笔记）

ECDSA标准中的步骤与DSA方案的步骤在概念上紧密相连，但ECDSA中的离散对数问题是在椭圆曲线群中构建起来的。因此，实际计算一个ECDSA签名所执行的算术运算与DSA中的完全不同。

ECDSA标准是针对素数域${\mathbb{Z}}_p$和有限域$GF(2^m)$上的椭圆曲线定义的

密钥生成

1. 使用椭圆曲线$E$，其中：模数为$p$；系数为$a$和$b$；生成素数阶$q$的循环群的点A
2. 选择一个随机整数$d$，且$0<d<q$.
3. 计算$B=dA$

密钥为：
$k_{pub}=(p,a,b,q,A,B)$
$k_{pr}=(d)$

注意：我们已经建立了一个离散对数问题，其中整数d为私钥，标量乘法的结果点B为公钥。与DSA一样，循环群的阶是q；而为了达到更高的安全等级，这个数的长度大小应该大于等于160位。

签名与验证

与DSA一样，$ECDSA$签名由一对整数$(r,s)$组成，其中每个值的位长度都与$q$相同，这也有助于实现十分简洁的签名。使用公钥和私钥计算消息$x$的签名的方式如下：

ECDSA签名生成

1. 选择一个整数作为随机临时密钥$k_E$，且$0<k_E<q$。
2. 计算$R=k_{E}A$。
3. 设置$r=x_R$。
4. 设置$s\equiv (h(x)+d\cdot r)k_E^{-1}\mathrm{m}\mathrm{o}\mathrm{d}q$。

在步骤3中，点R的x坐标赋给变量r。在计算s时，必须使用函数h对消息x进行哈希。哈希函数的输出长度必须至少与q一样长。

ECDSA签名验证

1. 计算辅助值$w\equiv s^{-1}\mathrm{m}\mathrm{o}\mathrm{d}q$。
2. 计算辅助值$u_1\equiv w\cdot h(x)\mathrm{m}\mathrm{o}\mathrm{d}q$。
3. 计算辅助值$u_2\equiv w\cdot r\mathrm{m}\mathrm{o}\mathrm{d}q$。
4. 计算$P=u_{1}A+u_{2}B$。
5. 验证$ve{r}_{k_{pub}}(x,(r,s))$为：
   若$x_p\equiv r\mathrm{m}\mathrm{o}\mathrm{d}q$则为有效签名；
   若$x_p\not\equiv r\mathrm{m}\mathrm{o}\mathrm{d}q$则为无效签名。

最后一步中的$x_p$表示点P的x坐标。只有当$x_p$与签名参数r模q相等时，验证者才会接受签名（r,s)；否则，此签名将被看做时无效的。

证明就不放了，放个小例子吧

举例

首先，椭圆曲线为：$E:y^2\equiv x^3+2x+2\mathrm{m}\mathrm{o}\mathrm{d}17$

$Bob选择p=17,a=2,b=2的曲线E和q=19的点A=(5,1)。选择d=7；计算B=dA=7\cdot (5,1)=(0,6)$

$Bob向Alice发送公钥(p,a,b,q,A,B)=(17,2,2,19,(5,1),(0,6))$

$签名：Bob计算消息h(x)=26的哈希值；选择临时密钥k_E=10,R=10\cdot (5,1)=(7,11),r=x_R=7,s=(26+7\cdot 7)\cdot 2\equiv 17\mathrm{m}\mathrm{o}\mathrm{d}19$

$发送签名：(x,(r,s))=(x,(7,17))$

$Alice方验证：$
$w=17^{-1}\equiv 9\mathrm{m}\mathrm{o}\mathrm{d}19$
$u_1=9\cdot 26=6\mathrm{m}\mathrm{o}\mathrm{d}19$
$u_2=9\cdot 7\equiv 6\mathrm{m}\mathrm{o}\mathrm{d}19$
$P=6\cdot (5,1)+6\cdot (0,6)=(7,11)$
$x_p\equiv r\mathrm{m}\mathrm{o}\mathrm{d}19\Rightarrow 有效的签名$

Python实现

需要引入模块ecdsa

import ecdsa

选取一个椭圆曲线，这里以NIST256p为例

gen = ecdsa.NIST256p.generator
order = gen.order()

ecdsa模块中有封装好了的函数可以赋值直接生成ecdsa公钥，私钥的对象

# 生成私钥d_A
d_A = random.randrange(1,order-1)
# 生成公私钥对象
public_key = ecdsa.ecdsa.Public_key(gen,gen * d_A)
private_key = ecdsa.ecdsa.Private_key(public_key,d_A)

数字签名

message = "message"
m = int(hashlib.sha1(message.encode("utf8")).hexdigest(),16)
# 临时密钥
k = random.randrange(1,order-1)
# 签名
signature = private_key.sign(m,k)
r = signature.r 
s = signature.s