参考博客：Coder小Q

ECDSA

椭圆曲线数字签名算法(Elliptic Cureve Digital Signature Algorithm，简称ECDSA)，是一种基于椭圆曲线密码学的公开密钥加密算法。1985年，Koblitz和Miller这两个人把数字签名算法移植到椭圆曲线上，椭圆曲线数字签名算法由此诞生。

其中ECDSA这个椭圆曲线数字签名算法是目前最常用的椭圆曲线数字签名算法，最近的密码题中也经常出现ECDSA这个考点(好像都是在随机数k这边做文章)。

签名过程

先确定一个椭圆曲线，以及求得该椭圆曲线的阶n和基点G：

y^2 \equiv x^3+ax+b ~mod(~p)\\ n*G = O

必要参数：
- 私钥： $d_A\in[1,n-1]$ 此为一个数。公钥： $Q_A=d_A*G$ (此为一个点)。
- 需要进行数字签名的消息m，并计算该消息的哈希值 $h=Hash(m)$
- 生成一个随机数 $k\in(1,n-1)$
签名过程：
- 计算 $k*G=(x_1,y_1)$
- 计算 $r=x_1~mod(~n)$
- 计算 $s=k^{-1}*(h+rd_A)~mod(~n)$
- 最后得到签名对 $(r,s)$
验证过程：
- 先判断 $1<r,s<n$ ，如果不在此范围内说明消息被修改
- 计算 $u_1\equiv h*s^{-1}\equiv h*k*(h+rd_A)^{-1}~mod(~n)$
- 计算 $u_2\equiv rs^{-1}~mod(~n)$
- 计算 $u_1*G+u_2*Q_A$ ，取最后的结果 $x_1$ ，如果 $x_1=r$ 就说明验证成功
- 验证的准确性：

\begin{align} u_1*G+u_2*Q_A&=h*s^{-1}*G+rs^{-1}*Q_A \\&=s^{-1}*(h*G+r*Q_A) \\&=s^{-1}*(h*G+r*d_A*G) \\&=s^{-1}*(h+r*d_A)*G \\&=k*(h+r*d_A)^{-1}*(h+r*d_A)*G \\&=k*G=(x_1,y_1) \end{align}

算法实现

ECDSA签名和认证的代码如下，使用Sagemath进行编写：

import hashlib
import random
from pwn import *
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663 # 定义模数
a = 0   # 定义椭圆曲线的参数
b = 7   # 定义椭圆曲线的参数
E = EllipticCurve(GF(p),[a,b]) # 定义椭圆曲线 y^2 = x^3 + 7 mod p
m = b'this_is_message' # 确定一个消息
h = int.from_bytes(hashlib.sha256(m).digest(),'big') # 计算消息的哈希值
n = E.order() # 获取椭圆曲线上的阶
G = E.gens()[0] # 获取椭圆曲线的基点
k = random.randint(2,n-1)
d = random.randint(1,n-1)
Q = d*G
print("[*] 椭圆曲线E为:",E)
print("[*] 椭圆曲线E的阶n为:",n)
print("[*] 椭圆曲线E的基点G为:",G)
print("[*] 消息m为:",m)
print("[*] 消息m对应的哈希值h为:",h)
print("[*] 数字签名所使用的密钥d为:",d)
print("[*] 数字签名所使用的随机数k为:",k)
print("[*] 数字签名所使用的公钥Q为:",Q)

# 签名过程
print("\n-------------签名过程----------------")
r = int((k*G).x())% n # 计算数字签名其中一个参数r
k_1 = inverse_mod(k,n) # 计算k在阶n下的逆元
s = k_1*(h+r*d) % n # 计算数字签名另一个参数s
print("[*] 数字签名参数r为:",r)
print("[*] 数字签名参数s为:",s)

print("\n-------------验证过程----------------")
assert(1< r < n and 1< s < n) # 确保r,s在(1,n)之间
s_1 = inverse_mod(s,n) # 求s_1在mod n下的逆元
u1 = (h * s_1) % n # 计算中间量u1
u2 = r*s_1 % n     # 计算中间量u2
T = u1*G + u2*Q    # 计算要验证的值
x_1 = int(T.x())
assert(x_1 == r)
log.success("数字签名验证成功")