ecdsa 笔记

发表于 2022-07-25 更新于 2023-09-16 本文字数： 9.1k 阅读时长 ≈ 8 分钟

有关 ecdsa 椭圆曲线数字签名算法的简要笔记

ECDSA 原理

密钥生成

私钥

随机选取一个在 \((1,n-1)\) 区间上的整数 \(d_A\) 作为私钥，其中 \(n\) 为椭圆曲线的 \(order\)，即椭圆曲线加密方程的模数。

公钥

\(Q=d_A\cdot G\)，其中 \(Q\) 即为公钥， \(G\) 为椭圆曲线上的基点（一般是随机选取的一点）。

由上式可知公钥由私钥生成。

数字签名

生成

随机生成一个临时密钥 \(k\)
计算 \(P=k\cdot G\)，其中 \(G\) 为椭圆曲线上的基点
取 \(P\) 的 \(x\) 轴坐标，\(r\equiv x\pmod{n}\)
使用哈希函数（可能选取 \(sha\) 系列函数较为安全）计算 \(m\) 的哈希值（\(m\) 一般为签名信息），使用 \(\mathrm{H}(m)\) 表示（得到的哈希值应为数值）
\(s\equiv k^{-1}\times(\mathrm{H}(m)+d_A\cdot r)\pmod{n}\)
最终 \((r,s)\) 即为数字签名

验证

校验 \(r,s\in[1,n-1]\)
计算哈希值 \(h=\mathrm{H}(m)\)
计算 \(w=s^{-1}\pmod{n}\)
计算 \(u_1=hw,u_2=rw\)
计算 \(X=(x_1,y_1)=u_1G+u_2Q\)
如果 \(X\) 不存在，那么签名错误；否则计算 \(v=x_1\pmod{n}\)
当 \(v=r\) 时，签名正确

Python 实现

一般来说仅使用 Python 的话我们需要使用 ecdsa 模块。

import ecdsa
# 使用 NIST256p 椭圆生成密钥
gen = ecdsa.NIST256p.generator
# 获取该椭圆模数
order = gen.order()
# 生成私钥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)
# 签名信息
m = "message"
Hm = int(hashlib.sha1(message.encode("utf8")).hexdigest(),16)
# 临时密钥
k = random.randrange(1, order-1)
# 签名
signature = private_key.sign(Hm, k)
r = signature.r 
s = signature.s

其默认哈希函数为 sha1。

ECDSA 实例

题目

import hashlib
import ecdsa
from Crypto.Util.number import *
import random
import os

flag = b"xxx"

assert flag.startswith(b'DASCTF{') and flag.endswith(b'}')
assert len(flag) == 40

def init():
    """
    initiation
    """
    global pub_key, priv_key, order, base, secret
    gen = ecdsa.NIST256p.generator
    order = gen.order()
    secret = bytes_to_long(flag[7:-1])
    
    pub_key = ecdsa.ecdsa.Public_key(gen, gen * secret)
    priv_key = ecdsa.ecdsa.Private_key(pub_key, secret)

def sign(msg, nonce):
    """
    sign msg
    """
    msg = int(hashlib.sha256(msg).hexdigest(), 16)
    
    sign = priv_key.sign(msg, nonce)
    print("R:", hex(sign.r)[2:])
    print("S:", hex(sign.s)[2:])

init()
nonce = random.getrandbits(order.bit_length())
sign(b'welcome to ecdsa', nonce)
print(nonce)

'''
R: 7b35712a50d463ac5acf7af1675b4b63ba0da23b6452023afddd58d4891ef6e5
S: a452fc44cc36fa6964d1b4f47392ff0a91350cfd58f11a4645c084d56e387e5c
57872441580840888721108499129165088876046881204464784483281653404168342111855
'''

题解

import hashlib
import ecdsa
from Crypto.Util.number import *

msg = b'welcome to ecdsa'
nonce = 57872441580840888721108499129165088876046881204464784483281653404168342111855
R = 0x7b35712a50d463ac5acf7af1675b4b63ba0da23b6452023afddd58d4891ef6e5
S = 0xa452fc44cc36fa6964d1b4f47392ff0a91350cfd58f11a4645c084d56e387e5c
msg = int(hashlib.sha256(msg).hexdigest(), 16)
n = ecdsa.NIST256p.generator.order()
import gmpy2
secret = (S * nonce - msg) * gmpy2.invert(R, n) % n
print(secret)
print(long_to_bytes(secret))

ECDSA 攻击

\(k\) 较小

我们考虑一对随机数 \((k_0,k_i)\)，有 \[ k_0\equiv m_0s_0^{-1}+d_Ar_0s_0^{-1}\pmod{n}\\ k_i\equiv m_is_i^{-1}+d_Ar_is_i^{-1}\pmod{n} \] 将 \(d_A\) 消去，可以得到 \[ k_0-s_0^{-1}s_ir_0r_i^{-1}\cdot k_i+s_0^{-1}r_im_ir_i^{-1}-s_0^{-1}m_0\equiv0\pmod{n} \] 那么可以从中改写为方程 \[ F_i(X,Y)=X+t_iY+u_i \] 满足 \(F_i(k_i,k_0)=0\pmod{n}\)

其中系数一一对应为 \[ t_i=-s_i^{-1}s_0r_ir_0^{-1}\\ u_i=s_i^{-1}r_im_0r_0^{-1}-s_i^{-1}m_i \] 不妨构建格 \[ M=\begin{bmatrix} N&0&\cdots&0&0&0\\ 0&N&\cdots&0&0&0\\ \vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ 0&0&\cdots&N&0&0\\ -t_1&-t_2&\cdots&-t_d&1&0\\ -u_1&-u_2&\cdots&-u_d&0&K \end{bmatrix} \] 可以证明解向量 \((k_1,\cdots,k_d,k_0,K)\) 在格中，其中 \(K\) 是 \(k\) 的上界。

rs = rs
ss = ss
msgs = msgs
N = ZZ(order)
kbits = 64
K = 2 ** kbits
d = len(rs) - 1
ti = []
ui = []
for i in range(1, d + 1):
    t = -inverse_mod(ss[i], N) * ss[0] * rs[i] * inverse_mod(rs[0], N)
    u = inverse_mod(ss[i], N) * rs[i] * msgs[0] * inverse_mod(rs[0], N) - inverse_mod(ss[i], N) * msgs[i]
    ti.append(t)
    ui.append(u)
P = diagonal_matrix([N] * d)
E = diagonal_matrix([1, K])
R = matrix([-vector(ti), -vector(ui)])
M = block_matrix([[P, 0], [R, E]], subdivide=False)
shortest_vector = M.LLL()[0]
shortest_vector = list(shortest_vector)
ks = shortest_vector[d:-1] + shortest_vector[:d]
ks

\(k\) 复用

原理

我们可以知道 \[ s\equiv k^{-1}\times(\mathrm{H}(m)+d_A\cdot r)\pmod{n} \] 那么当 \(k\) 被泄露时，可以攻击得到 \[ d_A=r^{-1}\times(ks-H(m)) \] 所以 \(k\) 需要保密。

但如果 \(k\) 被重复用于签名，那么也可以立即恢复密钥。

不妨设 \((r,s_1),(r,s_2)\) 为从相同的 \(k\) 生成的签名（\(r=(kG)_x\)），那么将有 \[ s_1=k^{-1}(H(m_1)+d_Ar)\newline s_2=k^{-1}(H(m_2)+d_Ar) \] 推导可得 \[ k(s_1-s_2)=H(m_1)-H(m_2) \] 即 \[ k=(s_1-s_2)^{-1}(H(m_1)-H(m_2)) \] 此时我们就从 \(k\) 复用的签名中恢复了 \(k\)，从而获取密钥 \(d_A\)。

\(k\) 固定位

爆破

当 \(k\) 拥有相同的前缀时，我们可以看作 \[ k_i=k-e_i \] 不妨设 \((r_1,s_1),(r_2,s_2)\) 为从相同的 \(k\) 生成的签名（\(r_i=(k_iG)_x\)），那么将有 \[ s_1=k_1^{-1}(H(m_1)+d_Ar_1)\newline s_2=k_2^{-1}(H(m_2)+d_Ar_2) \] 推导可得 \[ (k+e_1)s_1=H(m_1)+d_Ar_1\newline (k+e_2)s_2=H(m_2)+d_Ar_2 \] 相减可得 \[ e_1-e_2=H(m_1)/s_1-H(m_2)/s_2+d_A(r_1/s_1-r_2/s_2) \] 即 \[ d_A=[(e_1-e_2)-(H(m_1)/s_1-H(m_2)/s_2)](r_1/s_1-r_2/s_2)^{-1} \] 简单爆破求解 \(e_1-e_2\) 即可。

题目

import os
import ecdsa
import hashlib
from Crypto.Util.number import *
from Crypto.Util.strxor import strxor as xor

p = getPrime(256)
gen = lambda: p + getPrime(16)
pad = lambda m: m + os.urandom(32 - len(m) % 32)

key = os.urandom(30)
sk = ecdsa.SigningKey.from_secret_exponent(
    secexp=bytes_to_long(key),
    curve=ecdsa.SECP256k1
)
sig1 = sk.sign(data=b'This is the first message.', k=gen())
sig2 = sk.sign(data=b'Here is another message.', k=gen())
print(f"{sig1 = }")
print(f"{sig2 = }")

代码

import ecdsa
import hashlib

order = ecdsa.SECP256k1.generator.order()

r1, s1 = ecdsa.keys.sigdecode_string(sig1, order)
r2, s2 = ecdsa.keys.sigdecode_string(sig2, order)

print(f"{(r1, s1) = }")
print(f"{(r2, s2) = }")

msg1 = hashlib.sha1(b'This is the first message.').digest()
msg2 = hashlib.sha1(b'Here is another message.').digest()

msg1 = bytes_to_long(msg1)
msg2 = bytes_to_long(msg2)

msg1_bar = msg1 * pow(s1, -1, order)
msg2_bar = msg2 * pow(s2, -1, order)
r1_bar = r1 * pow(s1, -1, order)
r2_bar = r2 * pow(s2, -1, order)
for i in range(-2**16, 2**16):
    dA = (i - (msg1_bar - msg2_bar)) * pow(r1_bar - r2_bar, -1, order) % order
    """
    TODO: dA forge.
    """

HNP

由于 \[ k_i=k-e_i \] 存在错误的数，还可以将其转化为 HNP 问题。

首先，我们有 \[ s_i\equiv k_i^{-1}(m_i+d_A\cdot r_i)\pmod{n} \] 我们变换方程可以得到 \[ k_i\equiv m_is_i^{-1}+d_Ar_is_i^{-1}\pmod{n} \] 那么还原 \(k_i\) 可以构造格 \[ M=\begin{bmatrix} n\\ & n\\ & & \ddots\\ & & & n\\ r_1s_1^{-1} & r_1s_1^{-2} & \cdots & r_ls_l^{-1} & K/n &\\ m_1s_1^{-1} & m_2s_2^{-1} & \cdots & m_ls_l^{-1} & & K \end{bmatrix} \] 其中 \(K\) 是 \(k_i\) 的上界。

例如对于两对签名 \((r_1,s_1),(r_2,s_2)\)，由以下代码生成

import ecdsa
import random
 
gen = ecdsa.NIST256p.generator
order = gen.order()
secret = random.randrange(1,order)
 
pub_key = ecdsa.ecdsa.Public_key(gen, gen * secret)
priv_key = ecdsa.ecdsa.Private_key(pub_key, secret)
 
nonce1 = random.randrange(1, 2**127)
nonce2 = random.randrange(1, 2**127)
 
msg1 = random.randrange(1, order)
msg2 = random.randrange(1, order)
 
sig1 = priv_key.sign(msg1, nonce1)
sig2 = priv_key.sign(msg2, nonce2)

我们获得签名后，使用 sagemath 写出代码如下

order = order
kbits = 127
r1, s1 = sig1.r, sig1.s
r2, s2 = sig2.r, sig2.s
msg1 = msg1
msg2 = msg2

N = ZZ(order)
K = 2 ^ kbits
P = diagonal_matrix([N] * 2)
E = diagonal_matrix([K / N, K])
R = matrix([[ZZ(r1) * inverse_mod(s1, N), ZZ(r2) * inverse_mod(s2, N)],
            [ZZ(msg1) * inverse_mod(s1, N), ZZ(msg2) * inverse_mod(s2, N)]])
M = block_matrix([[P, ZZ(0)], [R, E]])
shortest_vector = M.LLL()[1]
k1, k2 = shortest_vector[:2]
# dA = shortest_vector[2] / K * N
dA = (k1 - ZZ(msg1) * inverse_mod(s1, N)) / (ZZ(r1) * inverse_mod(s1, N)) % N
k1, k2, dA

我们可以从格中寻找到 \(k_1,k_2,d_A\)。

固定前缀

我们考虑一对误差 \((e_0,e_i)\)，有 \[ k+e_0\equiv m_0s_0^{-1}+d_Ar_0s_0^{-1}\pmod{n}\\ k+e_i\equiv m_is_i^{-1}+d_Ar_is_i^{-1}\pmod{n} \] 相减可得 \[ e_0-e_i=(m_0s_0^{-1}-m_is_i^{-1})+(r_0s_0^{-1}-r_is_i^{-1})\cdot d_A\pmod{n} \] 记 \(\tilde{e}_i=e_0-e_i\)，可以从中改写为方程 \[ F_i(X)=A_iX+B_i \] 满足 \(F_i(d_A)=\tilde{e}_i\pmod{n}\)

其中系数一一对应为 \[ A_i=s_0^{-1}-r_is_i^{-1}\\ B_i=m_0s_0^{-1}-m_is_i^{-1} \] 不妨构建格 \[ M=\begin{bmatrix} N&0&\cdots&0&0&0\\ 0&N&\cdots&0&0&0\\ \vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ 0&0&\cdots&N&0&0\\ A_1&A_2&\cdots&A_d&K/N&0\\ B_1&B_2&\cdots&B_d&0&K \end{bmatrix} \] 可以证明解向量 \((\tilde{e}_1,\tilde{e}_2,\cdots,\tilde{e}_d,\frac{Kd_A}{N},K)\) 在格中，其中 \(K\) 是 \(e_i\) 的上界。

由如下代码产生存在 \(d\) 对 \((e_0,e_i)\) 误差的签名，

import ecdsa
import random
 
gen = ecdsa.NIST256p.generator
order = gen.order()
secret = random.randrange(1,order)

pub_key = ecdsa.ecdsa.Public_key(gen, gen * secret)
priv_key = ecdsa.ecdsa.Private_key(pub_key, secret)
k = getPrime(256)
nonces = []
msgs = []
rs = []
ss = []
for i in range(3):
    nonce = k + getPrime(16)
    nonces.append(nonce)
    msg = random.randrange(1, order)
    msgs.append(msg)
    sig = priv_key.sign(msg, nonce)
    rs.append(ZZ(sig.r))
    ss.append(ZZ(sig.s))

nonces, msgs, rs, ss

那么在获取到 msgs, rs, ss 后，使用如下代码寻找解

order = order
rs = rs
ss = ss
msgs = msgs
kbits = 16
N = ZZ(order)
K = 2 ^ kbits

d = len(rs) - 1
Ai = []
Bi = []
for i in range(1, d + 1):
    Ai.append(ZZ(rs[0]) * inverse_mod(ss[0], N) - ZZ(rs[i]) * inverse_mod(ss[i], N))
    Bi.append(ZZ(msgs[0]) * inverse_mod(ss[0], N) - ZZ(msgs[i]) * inverse_mod(ss[i], N))

P = diagonal_matrix([N] * d)
E = diagonal_matrix([K / N, K])
R = matrix([Ai, Bi])
M = block_matrix([[P, ZZ(0)], [R, E]], subdivide=False)
shortest_vector = M.LLL()[1]
errs = shortest_vector[:d]
# dA = shortest_vector[d] * N / K
dA = (errs[0] - Bi[0]) * inverse_mod(Ai[0], N) % N
dA, errs

需要注意的是，从格中还原的 \(d_A\) 可能不准确。