椭圆曲线数字签名相关攻击

• 对于ECDSA的攻击最核心的部分就是随机数k和私钥d，一般都是在这俩个数据做文章，结合近期比赛上遇到的ECDSA相关的密码题目，更经常的是在随机数k这边做文章。难度加大一点就是对k、d二者都做点事情。
• 对数据签名攻击的最终目的是为了伪造数字签名数据对即(s,r)这俩个数据对，而这两个数据对与k、d是相关的，对于ECDSA攻击的核心点基本上都是在k、d这两点上。

题型1—随机数k的复用

题型1推导

• 在ECDSA数字签名的时候， 如果随机数k复用就会导致私钥的泄露，首先回顾一下ECDSA数字签名的过程。主要就是下面这俩个式子

$$r = x~mod(~n)\\ s = k^{-1}(h+r*d)~mod(~n)$$

• 对于俩次不同的签名，有如下的式子

$$r_1 = x_1~mod(~n)\\ s_1 = k_1^{-1}(h_1+r_1*d)~mod(~n)\\ \\ r_2 = x_2~mod(~n)\\ s_2 = k_2^{-1}(h_2+r_2*d)~mod(~n)\\$$

• 当随机数k重复使用就会出现$k_1=k_2=k$这一情况，由于$x = (k*G).x()$，这就导致了$r_1=r_2=r$上面的式子就可以写成这样：

$$r = x~mod(~n)\\ s_1 = k^{-1}(h_1+r*d)~mod(~n)\\ \\ r = x~mod(~n)\\ s_2 = k^{-1}(h_2+r*d)~mod(~n)\\$$

• 所以就有：

$$s_1-s_2=\frac{h1+r*d-h2-r*d}{k}~mod(~n)\\ s_1-s_2=\frac{h1-h2}{k}~mod(n)\\ \therefore k = (h_1-h_2)*(s_1-s_2)^{-1}~mod(~n)\\ \therefore d = (s_1*k-h_1)*r^{-1}~mod(n)$$

题型1例题

• 接下来给出一个例题：

from Crypto.Util.number import *
from hashlib import sha256
import random
p = 104013039882501274693449938443150870046676177290878392003647959897761590749237
a = 10
b = 55
E = EllipticCurve(GF(p),[a,b]) # 创建一个椭圆曲线
O = E.order()                  # 计算该椭圆曲线的阶
G = E.gen(0)                   # 获取该椭圆曲线的一个生成元
d = random.randint(1,O-1)      # 生成一个私钥

def h(message):                # 计算消息的哈希值
    t = sha256(message.encode('utf-8')).digest()
    return int.from_bytes(t,'big')


def ecdsa(k,G,d,h_,O):             # 进行椭圆曲线数字签名
    K = k*G
    x = int(K.x())
    r = x % O
    k_ = inverse_mod(k,O)
    s = k_ * (h_ + r * d) % O
    return (r,s)
    
message = ["Hello_world","this_is_a_meesage"]
h1 = h(message[0])
h2 = h(message[1])
k = random.randint(1,O-1)
sig1 = ecdsa(k,G,d,h1,O)
sig2 = ecdsa(k,G,d,h2,O) # k的复用
print(f"(r1,s1) = {sig1}")
print(f"(r2,s2) = {sig2}")
#print(f"flag=flag{{{str(d)}}}")
"""
(r1,s1) = (40006709387573641419946125303569413158469101955768758583457507808179101337206, 1585768849918578394723965791955160503009311951479720516547647283934983942200)
(r2,s2) = (40006709387573641419946125303569413158469101955768758583457507808179101337206, 85267507776229139224293234455627206003745480460349166116613720730622564486718)
"""

• 对随机数k的复用推导就像上面那样，这里给出exp：

from Crypto.Util.number import *
from hashlib import sha256
import random
p = 104013039882501274693449938443150870046676177290878392003647959897761590749237
a = 10
b = 55
E = EllipticCurve(GF(p),[a,b]) # 创建一个椭圆曲线
O = E.order()                  # 计算该椭圆曲线的阶
G = E.gen(0)                   # 获取该椭圆曲线的一个生成元
d = random.randint(1,O-1)      # 生成一个私钥

def h(message):                # 计算消息的哈希值
    t = sha256(message.encode('utf-8')).digest()
    return int.from_bytes(t,'big')
(r1,s1) = (40006709387573641419946125303569413158469101955768758583457507808179101337206, 1585768849918578394723965791955160503009311951479720516547647283934983942200)
(r2,s2) = (40006709387573641419946125303569413158469101955768758583457507808179101337206, 85267507776229139224293234455627206003745480460349166116613720730622564486718)
message = ["Hello_world","this_is_a_meesage"]
s1_s2 = s1 - s2 
h1 = h(message[0])
h2 = h(message[1])
h1_h2 = h1-h2
s1_s2_ = inverse_mod(s1_s2,O)
k = h1_h2 * s1_s2_ % O
r1_ = inverse_mod(r1,O)
d = (s1*k - h1)*r1_ % O
print(f"flag{{{d}}}")
# flag{39293969871044977010378459455218809487719269197611508380642557837535793765188}

题型2—随机数k1与k2有关系

题型2综述

• 对于这种题型，其实主要考察的重点其实并不是ECDSA这个数字签名的过程，而是伪随机数生成器了。这个就需要对一些伪随机数生成的机制有一定的了解。
• 简单一点的伪随机数生成考点就是LCG的基础题型了，难度上来就变种的LCG或者其他的伪随机数生成器了。主要还是积累伪随机数生成器的相关算法和对应的破解方法吧。

题型2例题

题型3—结合其他加密方式

刷题

题目1—2025年春秋杯夏季赛_eccccc

• 题目附件如下：

from sage.all import *
from hashlib import sha256
from secret import flag
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

assert flag.startswith(b'flag{') and flag.endswith(b'}')

class ECDSA:
    def __init__(self, E=None, G=None, n=None):
        p = 115792089237316195423570985008687907853269984665640564039457584007908834671663 # 定义模数
        a = 0; b = 7
        self.E = E if E else EllipticCurve(GF(p), [a, b]) # 定义椭圆曲线y^2 = x^3 + 7 mod p
        self.G = G if G else self.E.gen(0) # 获得椭圆曲线的基点
        self.n = n if n else self.E.order() # 获得椭圆曲线的阶
        self.d = randint(1, self.n - 1)    # 随机选取一个数d
        self.Q = self.d * self.G           # 计算 d*G 椭圆曲线点运算
        self.k = randint(1, self.n - 1) % self.n # 计算k = 随机数 % n (即椭圆曲线的阶)

    def sign(self, m:bytes): # 签名操作
        self.k = (7 * self.k ** 2 + 3 * self.k + 11) % self.n  # 另 k = (7*k^2 + 3*k +11 ) % n
        R = self.k * self.G                                    # R = k*G
        r = ZZ(R.x()) % self.n                                 # r = R_x % n 取点R的橫坐标%n
        h = int.from_bytes(sha256(m).digest(), 'big')          # h = 消息的哈希值
        s = self.k**(-1) * (h + self.d * r) % self.n           # 签名结果: s = k^(-1) * (h + d*r) % n
        return (r, s)

    def verify(self, m:bytes, r:int, s:int):  # 验证过程
        if not (0 < r < self.n and 0 < s < self.n): # 判断 0 < r,s < n and
            return False
        w = pow(s, -1, self.n)          # 计算 w = s^(-1) mod n
        h = int.from_bytes(sha256(m).digest(), 'big') # 计算消息的哈希值
        u1 = (h * w) % self.n           # 计算u1 = (h*w) %n
        u2 = (r * w) % self.n           # 计算u2 = (r*w) %n
        R = u1 * self.G + u2 * self.Q   # 计算点R = u1*G + u2*Q
        return ZZ(R.x()) % self.n == r  # 验证R_x == r



e = ECDSA()
print(AES.new(key=sha256(str(e.d).encode()).digest(), mode=AES.MODE_ECB).encrypt(pad(flag, 16))) # 用随机数d作为密钥将flag进行加密,输出密文
print(e.sign(b'32748923ur8934u893ygf893h34t3453453'))   # 使用e对该消息进行签名
print(e.sign(b'ehfw9h8r039u82678ifjewf9024r2323423'))   # 使用e对该消息进行签名
# 对下一次签名的随机数k2与前一次签名的随机数k1满足一个二次模的关系
'''
b'\xa7\x13\xd5j\x10*\xc9\x04\xda\x8b\xaaf\xde\xae\xdc\xdb\xb7T\xcd\x8b\xc9K\xf4\xb4^p\x8da\x1bS\xef\x92\xaf\x03\xe9\xc2\x0c\x8c\x83\x83\xf9\xc6\xc7\t\xf9\x9cp\x9d'
(18507930132802310344248699822628576170242868593944128167302942018134209256936, 23965013559564325260453725916491832279556345092147805659950905735422363429946)
(61645219796227967861807301237829197706412124807702206247291322591426944615554, 84283844402102709520391794221564573160907887711307574424747605446691209453247)
'''

• exp如下，具体过程这里就不说明了，放在wp那边说明：

# ECCCCC
from hashlib import sha256
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663 # 定义模数
a = 0 
b = 7
e = EllipticCurve(GF(p),[a,b])
print(e)
G = e.gen(0)
n = e.order()
c = b'\xa7\x13\xd5j\x10*\xc9\x04\xda\x8b\xaaf\xde\xae\xdc\xdb\xb7T\xcd\x8b\xc9K\xf4\xb4^p\x8da\x1bS\xef\x92\xaf\x03\xe9\xc2\x0c\x8c\x83\x83\xf9\xc6\xc7\t\xf9\x9cp\x9d'
m1 = b'32748923ur8934u893ygf893h34t3453453'
m2 = b'ehfw9h8r039u82678ifjewf9024r2323423'
h1 = int.from_bytes(sha256(m1).digest(), 'big')
h2 = int.from_bytes(sha256(m2).digest(), 'big')   
r1,s1 = (18507930132802310344248699822628576170242868593944128167302942018134209256936, 23965013559564325260453725916491832279556345092147805659950905735422363429946)
r2,s2 = (61645219796227967861807301237829197706412124807702206247291322591426944615554, 84283844402102709520391794221564573160907887711307574424747605446691209453247)
print("基点G=",G)
print("阶n=",n)
print(r1,r2)
print(s1,s2)
print(h1,h2)
r1_ = inverse_mod(r1,n)
r2_ = inverse_mod(r2,n)
x = h1*r1_ - h2*r2_ % n
y1 = s1*r1_ 
y2 = s2*r2_
k = var('k')
P = PolynomialRing(Zmod(n), 'k')
k = P.gen()
f = y1*k - y2*(7*k^2 + 3*k + 11) - x 
roots = f.roots() # 在mod n 下求一个关于未知数k的二次剩余,得到俩个解其中一个解就是key
print(roots)
k1 = roots[1][0]
d = (s1*k1-h1)*r1_ % n
from Crypto.Cipher import AES
print(AES.new(key=sha256(str(d).encode()).digest(), mode=AES.MODE_ECB).decrypt(c))
# b'flag{14537d3b-2567-4f1a-a011-2df9635dad20}\x06\x06\x06\x06\x06\x06'

题目2—L3HCTF_ECDSA

• 题目附件如下：

import hashlib
import random
from ecdsa import NIST256p, SigningKey

class FlawedNonceGenerator:
    def __init__(self, n):
        self.n = n
        self.a = random.randrange(1, n)
        self.b = random.randrange(1, n)
        self.c = random.randrange(1, n)
        self.last_k = random.randrange(1, n)

    def generate_nonce(self):
        current_k = self.last_k
        next_k = (self.a * current_k**2 + self.b * current_k + self.c) % self.n
        self.last_k = next_k
        
        return current_k


curve = NIST256p
n = curve.order
G = curve.generator
#print(curve.curve)
print(G.x())
print(G.y())
#print(n)
private_key = SigningKey.from_secret_exponent(random.randrange(1, n), curve=curve)
d = private_key.privkey.secret_multiplier
public_key = private_key.get_verifying_key()

messages = [
    b"Hello player, welcome to L3HCTF 2025!",
    b"This is a crypto challenge, as you can probably tell.",
    b"It's about ECDSA, a very... robust algorithm.",
    b"I'm sure there are no implementation flaws whatsoever.",
    b"Anyway, here are your signatures. Good luck!",
    f"Oh, and the flag is L3HCTF{{{d}}}. Don't tell anyone!".encode(),
]
nonce_generator = FlawedNonceGenerator(n)
f = open('signatures.txt', 'w')

for i in range(6):
    k = nonce_generator.generate_nonce()
    message = messages[i]
    h = int.from_bytes(hashlib.sha256(message).digest(), 'big')
    R = k * curve.generator # 计算R
    r = R.x() % n # 取Rx % n 为r
    s_inv = pow(k, -1, n) # k^(-1) mod n
    s = (s_inv * (h + d * r)) % n #s = k^(-1) * (h+d*r)
    # ki = a*k_i-1 **2 + b*k_i-1 + c % n
    f.write(f"h: {h}, r: {r}, s: {s}\n")
    print(f"Oh, and the flag is L3HCTF{{{d}}}. Don't tell anyone!".encode())