参考博客：独奏の小屋

参考博客：Coder小Q

image-20250717225013460

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 hs^{-1}\equiv hk*(h+rd_A)^{-1}~mod(~n)$
    • 计算$u_2\equiv rs^{-1}~mod(~n)$
    • 计算$u_1G+u_2Q_A$，取最后的结果$x_1$，如果$x_1=r$就说明验证成功
    • 验证的准确性：

$$
\begin{align}
u_1G+u_2Q_A&=hs^{-1}G+rs^{-1}Q_A
\&=s^{-1}(hG+rQ_A)
\&=s^{-1}(hG+rd_AG)
\&=s^{-1}(h+rd_A)G
\&=k(h+rd_A)^{-1}(h+r*d_A)G
\&=kG=(x_1,y_1)
\end{align}
$$

算法实现

  • ECDSA签名和认证的代码如下，使用Sagemath进行编写：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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("数字签名验证成功")

EdDSA

  • EdDSA英文全称为 Edwards-curve Digital Signature Algorithm，其中文意思为，爱德华兹曲线数字签名算法，而爱德华兹曲线其实是如下形式的一个椭圆曲线：

$$
x^2+y^2=1+dx^2y^2
$$

  • 所以EdDSA本质上也是椭圆曲线数字签名算法，但是要与最常见的ECDSA椭圆曲线数字签名算法区别开。