ECDSA Cracking Methods

Chữ kí số dựa trên Elliptic Curve

Posted Jun 5, 2025 Updated Jun 6, 2025

By Lê Trí Đức

17 min read

ECDSA’s Scheme

Bài viết có tham khảo các paper/bài viết sau:

[1] https://eprint.iacr.org/2025/654.pdf

[2] https://eprint.iacr.org/2019/023.pdf

[3] https://eprint.iacr.org/2023/032.pdf

[4] https://magicfrank00.github.io/writeups/posts/lll-to-solve-linear-equations/

[5] https://ur4ndom.dev/static/files/latticetraining/practical_lattice_reductions.pdf

Lược đồ chữ kí số ECDSA bao gồm các thành phần sau: Đầu tiên là một khóa bí mật $\displaystyle d$ và khóa công khai sẽ được tính bởi $\displaystyle Q=d.G$ trong đó $\displaystyle G$ là generator của elliptic curve có order là $\displaystyle n$.

Như vậy $\displaystyle \left(\text{pk} ,\text{sk}\right) =( dG,d)$

Tạo chữ kí:

Với message $\displaystyle ( m)$, mục tiêu của ta là dùng priv key để tạo ra một cặp chữ kí $\displaystyle ( r,s)$. Đầu tiên ta cần sử dụng một nonce $\displaystyle k$ để tính giá trị của

\[\begin{equation*} P=kG \end{equation*}\]

Khi đó ta sẽ lấy

\[\begin{equation*} r=P_{x}(\bmod n) \end{equation*}\]

Tiếp theo ta sẽ tính $\displaystyle s$ như sau

\[\begin{equation*} s=k^{-1}( e+dr)(\bmod n) \end{equation*}\]

trong đó $\displaystyle e=H( m)$ với $\displaystyle H$ là một hàm Hash.

Vậy ta có cặp $\displaystyle ( r,s)$ là chữ kí số của msg $\displaystyle m$.

Xác minh chữ kí:

Để xác minh chữ kí số $\displaystyle ( m,( r,s))$ ta làm như sau:

Ta sẽ tính $\displaystyle e=H( m)$. Sau đó sẽ tính

\[\begin{gather*} w=s^{-1}(\bmod n)\\ u_{1} =ew\\ u_{2} =rw \end{gather*}\]

\[\begin{gather*} X=u_{1} G+u_{2} Q\\ x=X_{x}(\bmod n) \end{gather*}\]

và kiểm tra xem $\displaystyle x=r$ thì chữ kí là hợp lệ.

Vì sao ta lại có $\displaystyle x=r?$.

Đầu tiên ta xét

\[\begin{equation*} P=kG \end{equation*}\]

Và $\displaystyle Q=dG$ cho nên

\[\begin{gather*} X=u_{1} G+u_{2} Q=u_{1} G+u_{2} dG\\ =( u_{1} +u_{2} d) G \end{gather*}\]

Vậy ta cần chỉ ra $\displaystyle u_{1} +u_{2} d\equiv k(\bmod n)$. Cụ thể

\[\begin{gather*} w=s^{-1}(\bmod n)\\ \Longrightarrow ew+rwd=w( e+rd) =sks^{-1} =k(\bmod n) \end{gather*}\]

Lưu ý rằng khi làm việc trên đường cong Elliptic thì

\[\begin{equation*} aG=bG \end{equation*}\]

khi và chỉ khi $\displaystyle a\equiv b\bmod G.order()$. Ở đây order là $\displaystyle n$ cho nên ta có điều phải chứng minh.

Breaking ECDSA

Sẽ có một vài trường hợp mà tại đó lược đồ ECDSA không còn an toàn nữa.

Revealed nonce

Trong trường hợp người kí để lộ nonce dù chỉ một lần, thì attacker có thể khôi phục lại privkey bằng cách tính

\[\begin{equation*} priv\ =\ ( sk-e) r^{-1}\bmod n \end{equation*}\]

Ta cần có $\displaystyle ( r,n) =1$ để tồn tại nghịch đảo modulo. Trên thực tế thì điều này hoàn toàn được đảm bảo vì các đường cong được dùng cho chữ kí số thường có order là một số nguyên tố lớn.

Nonce Reuse

Trường hợp nonce được dùng lại và ta có 2 chữ kí số của 2 văn bản khác nhau:

\[\begin{gather*} r_{1} =kG\\ s_{1} =k^{-1}( H( m_{1}) +dr)\\ r_{2} =kG\\ s_{2} =k^{-1}( H( m_{2}) +dr) \end{gather*}\]

Trong đó $\displaystyle d$ là privkey. Ta sẽ khôi phục lại giá trị này như sau:

\[\begin{gather*} s_{1} k=H( m_{1}) +dr\\ s_{2} k=H( m_{2}) +dr\\ \Longrightarrow s_{1} k-s_{2} k=H( m_{1}) -H( m_{2})\\ \Longrightarrow k=\frac{H( m_{1}) -H( m_{2})}{s_{1} -s_{2}} \end{gather*}\]

Sau khi có được $\displaystyle k$ thì ta hoàn toàn tính được priv từ công thức ở trên. Cụ thể

\[\begin{gather*} \frac{s_{2} H( m_{1}) -s_{1} H( m_{2})}{r( s_{1} -s_{2})} =priv\\ priv\ =\ ( sk-H( m_{1})) r^{-1} \end{gather*}\]

Two keys and shared nonce

Như ta đã biết thì ECDSA là non-deterministic, tức là mỗi lần kí cho cùng 1 msg sẽ cho ra 2 kết quả khác nhau. Lý do là vì ta sử dụng số $\displaystyle k$ là một nonce cho nên các giá trị sẽ được random. Attacks này xảy ra khi người kí, ta tạm gọi là Alice, kí 4 msgs khác nhau với 2 keys và 2 nonces.

Cụ thể như sau: Alice kí 2 msgs $\displaystyle ( m_{1}) ,( m_{2})$ với hai priv key khác nhau là $\displaystyle x_{1} ,x_{2}$ nhưng dùng chung 1 nonce là $\displaystyle k_{1}$. Tương tự với 2 msgs $\displaystyle ( m_{3}) ,( m_{4})$ với hai priv key $\displaystyle x_{1} ,x_{2}$ và một nonce khác là $\displaystyle k_{2}$.

Bây giờ ta sẽ tính được từ hàm Hash các giá trị sau:

\[\begin{equation*} h_{i} =H( m_{i}) ,i=\overline{1,4} \end{equation*}\]

Và ta có 4 chữ kí

\[\begin{gather*} s_{1} =k_{1}^{-1}( h_{1} +r_{1} x_{1})\\ s_{2} =k_{1}^{-1}( h_{2} +r_{1} x_{2})\\ s_{3} =k_{2}^{-1}( h_{3} +r_{2} x_{1})\\ s_{4} =k_{2}^{-1}( h_{4} +r_{2} x_{2}) \end{gather*}\]

Trong đó $\displaystyle r_{1} =k_{1} G,r_{2} =k_{2} G$. Ta có thể dùng khử gauss để tính lại

\[\begin{gather*} x_{1} =\frac{h_{1} r_{2} s_{2} s_{3} -h_{2} r_{2} s_{1} s_{3} -h_{3} r_{1} s_{1} s_{4} +h_{4} r_{1} s_{1} s_{3}}{r_{1} r_{2}( s_{1} s_{4} -s_{2} s_{3})}\\ x_{2} =\frac{h_{1} r_{2} s_{2} s_{4} -h_{2} r_{2} s_{1} s_{4} -h_{3} r_{1} s_{1} s_{4} +h_{4} r_{1} s_{1} s_{3}}{r_{1} r_{2}( s_{2} s_{3} -s_{1} s_{4})} \end{gather*}\]

Ở đây do dùng 2 priv key khác nhau cho nên kể cả khi biết $\displaystyle s_{1} ,s_{2}$ thì ta cũng không khôi phục lại nonce $\displaystyle k_{1}$ được. Cách duy nhất là giải hệ phương trình.

Cụ thể ta có $\displaystyle k_{1} =\frac{h_{1} +r_{1} x_{1}}{s_{1}} =\frac{h_{2} +r_{1} x_{2}}{s_{2}}$ cho nên $\displaystyle s_{2}( h_{1} +r_{1} x_{1}) =s_{1}( h_{2} +r_{1} x_{2})$ và tương tự cho $\displaystyle s_{3}, s_{4}$. Ta có hệ

\[\begin{equation*} \begin{cases} s_{2} r_{1} x_{1} -s_{1} r_{1} x_{2} =s_{1} h_{2} -s_{2} h_{1} & \\ s_{4} r_{2} x_{1} -s_{3} r_{2} x_{2} =s_{3} h_{4} -s_{4} h_{3} & \end{cases} \end{equation*}\]

Và đưa về hệ có dạng

\[\begin{bmatrix} a & b\\ c & d \end{bmatrix}\begin{bmatrix} x_{1}\\ x_{2} \end{bmatrix} =\begin{bmatrix} e\\ f \end{bmatrix}\]

Có một nghiệm, chẳng hạn $\displaystyle x_{1} =\frac{ed-bf}{ad-bc}$.

Fault Attack

Fault attack là một kiểu side channel attack tức là attacker sẽ cố gắng làm cho chữ kí số xuất hiện lỗi. Giả sử ta có một cặp $\displaystyle ( r,s)$ là chữ kí hợp lệ còn $\displaystyle ( r_{f} ,s_{f})$ là chữ kí lỗi. Lúc này ta có

\[\begin{gather*} s_{f} =k^{-1}( h+dr_{f})\\ s=k^{-1}( h+dr) \end{gather*}\]

Lúc này nếu ta lấy hiệu 2 giá trị thì

\[\begin{gather*} s-s_{f} =k^{-1}( h+dr-h-dr_{f})\\ =k^{-1}( d( r-r_{f}))\\ \Longrightarrow s-s_{f} =k^{-1} d( r-r_{f})\\ \Longrightarrow k=( s-s_{f})^{-1} d( r-r_{f}) \end{gather*}\]

Ta có thể thay giá trị này vào lại

\[\begin{equation*} s=k^{-1}( h+dr) \end{equation*}\]

để tính $\displaystyle d$ như sau:

\[\begin{gather*} s=( s-s_{f})( dr-dr_{f})^{-1}( h+dr)(\bmod n)\\ \Longrightarrow s( dr-dr_{f}) =( s-s_{f})( h+dr)\\ \Longrightarrow sdr-sdr_{f} =sh+sdr-hs_{f} -drs_{f}\\ \Longrightarrow -sdr_{f} =sh-hs_{f} -drs_{f}\\ \Longrightarrow drs_{f} -sdr_{f} =sh-hs_{f}\\ \Longrightarrow d( rs_{f} -sr_{f}) =h( s-s_{f})\\ \Longrightarrow d=h( s-s_{f})( rs_{f} -sr_{f})^{-1} \end{gather*}\]

Ví dụ:

  
import ecdsa
import random
import libnum
import hashlib
import sys

G = ecdsa.SECP256k1.generator
order = G.order()

priv1 = random.randrange(1,order)
 
Public_key = ecdsa.ecdsa.Public_key(G, G * priv1)
d = ecdsa.ecdsa.Private_key(Public_key, priv1)

k = random.randrange(1, 2**127)

msg="Hello"

if (len(sys.argv)>1):
	msg=(sys.argv[1])

h = int(hashlib.sha256(msg.encode()).hexdigest(),base=16)
sig = d.sign(h, k)

r,s = sig.r,sig.s

# Now generate a fault
rf = sig.r+1
sf=(libnum.invmod(k,order)*(h+priv1*rf)) % order

k = h*(s-sf) * libnum.invmod(sf*r-s*rf,order)

valinv = libnum.invmod( (sf*r-s*rf),order)

dx =(h*(s-sf)* valinv) % order

print(f"Message: {msg}")
print(f"k: {k}")

print(f"Sig 1 (Good): r={r}, s={s}")
print(f"Sig 2 (Faulty): r={rf}, s={sf}")

print (f"\nGenerated private key: {priv1}")
print (f"\nRecovered private key: {dx}")

Weak nonce and LLL

Trước tiên ta nhắc lại bài toán HNP.

Hidden number problem. Cho $\displaystyle p$ là một số nguyên tố và $\displaystyle \alpha \in [ 1,p-1]$ là một số nguyên bí mật. Ta có thể recover $\displaystyle \alpha$ nếu như biết giá trị của $\displaystyle m$ cặp giá trị $\displaystyle {( t_{i} ,a_{i})}_{i=1}^{m}$ thỏa mãn

\[\begin{equation*} \beta_{i} -t_{i} \alpha +a_{i} =0(\bmod p) \end{equation*}\]

trong đó $\displaystyle \beta_{i}$ không được cho biết và $\displaystyle \mid \beta_{i} \mid < B$ với $\displaystyle B< p$ nào đó.

Để giải bài HNP ta làm như sau. Xét một ma trận $\displaystyle \mathbb{B}$ với cơ sở:

\[\mathbb{B} =\begin{bmatrix} p & & & & \\ & p & & & \\ & & \ddots & & \\ & & & p & \\ t_{1} & t_{2} & \dotsc & t_{m} & 1/p \end{bmatrix}\]

Ta viết lại các phương trình HNP dưới dạng

\[\begin{equation*} \beta_{i} +a_{i} =t_{i} \alpha +k_{i} p,k_{i} \in \mathbb{Z} \end{equation*}\]

Khi đó ta thấy tổ hợp tuyến tính $\displaystyle \mathbf{x} =( k_{1} ,k_{2} ,…,k_{m} ,\alpha )$ sinh ra một vector của lattice đó là $\displaystyle \mathbf{x} B=( \beta_{1} +a_{1} ,…,\beta_{m} +a_{m} ,\alpha /p)$. Đặt $\displaystyle t=( a_{1} ,…,a_{m} ,0)$ và $\displaystyle u=( \beta_{1} ,…,\beta_{m} ,\alpha /p)$ thì ta có

\[\begin{equation*} \mathbf{x} B-t=u \end{equation*}\]

và $\displaystyle | u| < \sqrt{m+1} B$ trong khi đó định thức của lattice là $\displaystyle p^{m-1}$. Như vậy ta có thể sử dụng thuật toán $\displaystyle \text{apprCVP}$ để khôi phục lại giá trị của vector $\displaystyle u$ và tính toán $\displaystyle \alpha$ bằng cách lấy $\displaystyle u[ m+1] \times p$.

Nếu chuyển từ bài CVP sang SVP thì ta có thể mở rộng ma trận $\displaystyle \mathbb{B}$ sang một ma trận $\displaystyle \mathbb{B} ‘$ bằng cách nhúng vector cần rút gọn vào một hàng của $\displaystyle \mathbb{B}$

\[\mathbb{B} '=\begin{bmatrix} p & & & & & \\ & p & & & & \\ & & \ddots & & & \\ & & & p & & \\ t_{1} & t_{2} & \dotsc & t_{m} & B/p & \\ a_{1} & a_{2} & \dotsc & a_{m} & & B \end{bmatrix}\]

Như vậy lattice sẽ có một vector $\displaystyle \mathbf{u} ‘=( \beta_{1} ,…,\beta_{m} ,\alpha B/p,-B)$ sinh bởi tổ hợp tuyến tính $\displaystyle ( k_{1} ,…,k_{m} ,\alpha ,-1)$. Ta có $\displaystyle | \mathbf{u} ‘| < \sqrt{m+2} B$ và vector này đủ ngắn để có thể được tìm thấy bởi thuật toán LLL. Lưu ý thêm vector $\displaystyle ( 0,0,….,B,0)$ cũng thuộc vào lattice này và được sinh bởi $\displaystyle ( -t_{1} ,…,-t_{m} ,p,0)$ cho nên ta kỳ vọng rằng $\displaystyle \mathbf{u} ‘$ sẽ rơi vào vector thứ 2 của cơ sở rút gọn LLL.

Chi tiết về tối ưu và cơ sở thuật toán mình sẽ đề cập trong một bài khác về Lattice.

Liên hệ với Weak nonce: Attack sẽ rơi vào một trong các trường hợp, chẳng hạn như khi nonce $\displaystyle k$ khá nhỏ so với modulo $\displaystyle n$ hoặc các nonce có chung suffix, prefix.

Ví dụ đơn giản nhất là khi các MSB của $\displaystyle k$ đều bằng 0. Giả sử các nonces $\displaystyle k_{i}$ được tính sao cho $\displaystyle l$ bit đầu tiên của nó là 0. Khi đó ta có thể viết $\displaystyle \mid k_{i} \mid < 2^{\log_{2} n-l}$ và đồng thời

\[\begin{gather*} s_{i} k_{i} =z_{i} +r_{i} d(\bmod n)\\ \Longrightarrow z_{i} -s_{i} k_{i} =r_{i} d(\bmod n)\\ \Longrightarrow k_{i} -\left( s_{i}^{-1} r_{i}\right) d+\left( -s_{i}^{-1} z_{i}\right) =0(\bmod n) \end{gather*}\]

Đây chính là bài toán HNP, ẩn ta cần tìm là $\displaystyle d$, các giá trị nhiễu là các nonce $\displaystyle k_{i}$ nhỏ. Ta cũng biết và tính được $\displaystyle s_{i} ,z_{i}$.

Một số trường hợp khác mọi người có thể xem ở paper sau: https://eprint.iacr.org/2019/023.pdf và [3]

Bài tập

CryptoHack/ No Random, No Bias

Source code của bài:

  
from hashlib import sha1
from Crypto.Util.number import bytes_to_long, long_to_bytes
from ecdsa import ellipticcurve
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from random import randint

G = generator_256
q = G.order()

FLAG = b'crypto{??????????????????}'


def hide_flag(privkey):
    x = bytes_to_long(FLAG)
    p = curve_256.p()
    b = curve_256.b()
    ysqr = (x**3 - 3*x + b) % p
    y = pow(ysqr, (p+1)//4, p)
    Q = ellipticcurve.Point(curve_256, x, y)
    T = privkey.secret_multiplier*Q
    return (int(T.x()), int(T.y()))


def genKeyPair():
    d = randint(1,q-1)
    pubkey = Public_key(G, d*G)
    privkey = Private_key(pubkey, d)
    return pubkey, privkey


def ecdsa_sign(msg, privkey):
    hsh = sha1(msg.encode()).digest()
    nonce = sha1(long_to_bytes(privkey.secret_multiplier) + hsh).digest()
    sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nonce))
    return {"msg": msg, "r": hex(sig.r), "s": hex(sig.s)}



pubkey, privkey = genKeyPair()
hidden_flag = hide_flag(privkey)

sig1 = ecdsa_sign('I have hidden the secret flag as a point of an elliptic curve using my private key.', privkey)
sig2 = ecdsa_sign('The discrete logarithm problem is very hard to solve, so it will remain a secret forever.', privkey)
sig3 = ecdsa_sign('Good luck!', privkey)

print('Hidden flag:', hidden_flag)
print('\nPublic key:', (int(pubkey.point.x()), int(pubkey.point.y())), '\n')
print(sig1)
print(sig2)
print(sig3)

Và output.txt

Hidden flag: (16807196250009982482930925323199249441776811719221084165690521045921016398804, 72892323560996016030675756815328265928288098939353836408589138718802282948311)

Public key: (48780765048182146279105449292746800142985733726316629478905429239240156048277, 74172919609718191102228451394074168154654001177799772446328904575002795731796)

{'msg': 'I have hidden the secret flag as a point of an elliptic curve using my private key.', 'r': '0x91f66ac7557233b41b3044ab9daf0ad891a8ffcaf99820c3cd8a44fc709ed3ae', 's': '0x1dd0a378454692eb4ad68c86732404af3e73c6bf23a8ecc5449500fcab05208d'}
{'msg': 'The discrete logarithm problem is very hard to solve, so it will remain a secret forever.', 'r': '0xe8875e56b79956d446d24f06604b7705905edac466d5469f815547dea7a3171c', 's': '0x582ecf967e0e3acf5e3853dbe65a84ba59c3ec8a43951bcff08c64cb614023f8'}
{'msg': 'Good luck!', 'r': '0x566ce1db407edae4f32a20defc381f7efb63f712493c3106cf8e85f464351ca6', 's': '0x9e4304a36d2c83ef94e19a60fb98f659fa874bfb999712ceb58382e2ccda26ba'}

Phân tích: Đầu tiên là hàm hide flag: Nó nhận vào $\displaystyle privkey$, chuyển flag thành số nguyên và lấy nó làm tọa độ $\displaystyle x$ của một điểm $\displaystyle Q$ thuộc đường cong NIST256p. Sau đó nó sẽ tính $\displaystyle T=dQ$ và trả về $\displaystyle ( T_{x} ,T_{y})$.

Hàm tiếp theo là hàm gen key. Thì hàm này sinh cặp khóa công khai và bí mật thôi.

Như vậy ở bài này để lấy lại flag thì ta cần tính lại $\displaystyle privkey$ vì flag được giấu bằng $\displaystyle T=dQ$ cho nên nếu có $\displaystyle T$ thì ta tính $\displaystyle d^{-1} T=Q$ với $\displaystyle d^{-1} d=1\bmod q$.

Vấn đề của bài này nằm ở hàm hash được dùng để tạo nonce $\displaystyle k$.

  
nonce = sha1(long_to_bytes(privkey.secret_multiplier) + hsh).digest()

Cụ thể thì mỗi $\displaystyle k$ được tính bởi $\displaystyle k=\text{SHA1}( d| h( m))$ trong đó $\displaystyle h( m)$ là giá trị hash của $\displaystyle m$ đã được tính trước đó.

Ta biết rằng SHA1 chỉ trả về đầu ra có độ dài cố định là 160 bit, so với 256 bit của order thì rất nhỏ. Như vậy khi lấy modulo, một số các MSB của $\displaystyle k$ sẽ trở về 0 và ta chuyển về bài HNP như ở trên với mỗi $\displaystyle \mid k_{i} \mid < 2^{160}$:

\[\begin{array}{l} k_{i} -\left( s_{i}^{-1} r_{i}\right) d+\left( -s_{i}^{-1} z_{i}\right) =0(\bmod q)\\ \Longrightarrow k_{i} -\left( s_{i}^{-1} r_{i}\right) d+\left( -s_{i}^{-1} z_{i}\right) +t_{i} n=0 \end{array}\]

Ta có được 3 msgs cùng các giá trị $\displaystyle ( s_{i} ,r_{i})$.Ta sẽ xây dựng 1 ma trận dạng

\[B=\begin{bmatrix} q & & & & \\ & q & & & \\ & & q & & \\ s_{1}^{-1} r_{1} & s_{2}^{-1} r_{2} & s_{3}^{-3} r_{3} & B/q & \\ -s_{1}^{-1} z_{1} & -s_{2}^{-1} z_{2} & -s_{3}^{-1} z_{3} & & B \end{bmatrix}\]

Và áp dụng LLL để rút gọn nó.

Code giải như sau:

  
from hashlib import sha1
from Crypto.Util.number import *
from random import randint
from sage.all import *
from ecdsa.ecdsa import curve_256, generator_256

modulus = curve_256.p()
a_curve = curve_256.a()
b_curve = curve_256.b()

E = EllipticCurve(GF(modulus), [a_curve, b_curve])

G = E(generator_256.x(), generator_256.y())
q = G.order()

# =))) hơi phiền, vì generator của thư viện ecdsa khác với sage

T1 = E(16807196250009982482930925323199249441776811719221084165690521045921016398804, 72892323560996016030675756815328265928288098939353836408589138718802282948311)

P = E(48780765048182146279105449292746800142985733726316629478905429239240156048277, 74172919609718191102228451394074168154654001177799772446328904575002795731796)

payload1 = {'msg': 'I have hidden the secret flag as a point of an elliptic curve using my private key.', 'r': '0x91f66ac7557233b41b3044ab9daf0ad891a8ffcaf99820c3cd8a44fc709ed3ae', 's': '0x1dd0a378454692eb4ad68c86732404af3e73c6bf23a8ecc5449500fcab05208d'}
payload2 = {'msg': 'The discrete logarithm problem is very hard to solve, so it will remain a secret forever.', 'r': '0xe8875e56b79956d446d24f06604b7705905edac466d5469f815547dea7a3171c', 's': '0x582ecf967e0e3acf5e3853dbe65a84ba59c3ec8a43951bcff08c64cb614023f8'}
payload3 = {'msg': 'Good luck!', 'r': '0x566ce1db407edae4f32a20defc381f7efb63f712493c3106cf8e85f464351ca6', 's': '0x9e4304a36d2c83ef94e19a60fb98f659fa874bfb999712ceb58382e2ccda26ba'}

msg1 = payload1["msg"]
z1 = bytes_to_long(sha1(msg1.encode()).digest())
s1 = int(payload1['s'],16)
r1 = int(payload1['r'],16)

msg2 = payload2["msg"]
z2 = bytes_to_long(sha1(msg2.encode()).digest())
s2 = int(payload2['s'],16)
r2 = int(payload2['r'],16)

msg3 = payload3["msg"]
z3 = bytes_to_long(sha1(msg3.encode()).digest())
s3 = int(payload3['s'],16)
r3 = int(payload3['r'],16)

# M cần là một matrix over QQ
B = 2**160
T = [r1*pow(s1,-1,q),r2*pow(s2,-1,q),r3*pow(s3,-1,q)]
A = [-pow(s1,-1,q)*z1,-pow(s2,-1,q)*z2,-pow(s3,-1,q)*z3]
T = [t % q for t in T]
A = [a % q for a in A]
m = len(T)
M = q*Matrix.identity(QQ,m)
M = M.stack(Matrix(QQ,T))
M = M.stack(Matrix(QQ,A))
M = M.augment(vector([0]*m + [B/q]+[0]))
M = M.augment(vector([0]*(m+1) + [B]))
M = M.dense_matrix()
print(M)
# https://github.com/josephsurin/lattice-based-cryptanalysis/blob/main/lbc_toolkit/problems/hidden_number_problem.sage
M = M.LLL()
for row in M:
    if int(row[-1]) == B:
        secret = (-row[3]*q/B) % q
    elif int(row[-1]) == -B:
        secret = (row[3]*q/B) % q
print(secret)
d = int(secret)
print(type(d))
assert G*d == P
d_inv = inverse_mod(d, q)
d_inv = Integer(d_inv)
print(type(d_inv))
flag = long_to_bytes(int((T1*d_inv)[0]))
print(flag.deocde())

ECLCG/ HITCON CTF 2024

Source code của bài:

  
from Crypto.Util.number import getPrime
from Crypto.Cipher import AES
from fastecdsa.curve import secp256k1
from hashlib import sha256
from secrets import randbelow


G = secp256k1.G
q = secp256k1.q


def sign(d, z, k):
    r = (k * G).x
    s = (z + r * d) * pow(k, -1, q) % q
    return r, s


def verify(P, z, r, s):
    u1 = z * pow(s, -1, q) % q
    u2 = r * pow(s, -1, q) % q
    x = (u1 * G + u2 * P).x
    return x == r


def lcg(a, b, p, x):
    while True:
        x = (a * x + b) % p
        yield x


msgs = [
    b"https://www.youtube.com/watch?v=kv4UD4ICd_0",
    b"https://www.youtube.com/watch?v=IijOKxLclxE",
    b"https://www.youtube.com/watch?v=GH6akWYAtGc",
    b"https://www.youtube.com/watch?v=Y3JhUFAa9bk",
    b"https://www.youtube.com/watch?v=FGID8CJ1fUY",
    b"https://www.youtube.com/watch?v=_BfmEjHVYwM",
    b"https://www.youtube.com/watch?v=zH7wBliAhT0",
    b"https://www.youtube.com/watch?v=NROQyBPX9Uo",
    b"https://www.youtube.com/watch?v=ylH6VpJAoME",
    b"https://www.youtube.com/watch?v=hI34Bhf5SaY",
    b"https://www.youtube.com/watch?v=bef23j792eE",
    b"https://www.youtube.com/watch?v=ybvXNOWX-dI",
    b"https://www.youtube.com/watch?v=dt3p2HtLzDA",
    b"https://www.youtube.com/watch?v=1Z4O8bKoLlU",
    b"https://www.youtube.com/watch?v=S53XDR4eGy4",
    b"https://www.youtube.com/watch?v=ZK64DWBQNXw",
    b"https://www.youtube.com/watch?v=tLL8cqRmaNE",
]

if __name__ == "__main__":
    d = randbelow(q)
    P = d * G

    p = getPrime(0x137)
    a, b, x = [randbelow(p) for _ in range(3)]
    rng = lcg(a, b, p, x)

    sigs = []
    for m, k in zip(msgs, rng):
        z = int.from_bytes(sha256(m).digest(), "big") % q
        r, s = sign(d, z, k)
        assert verify(P, z, r, s)
        sigs.append((r, s))
    print(f"{sigs = }")

    with open("flag.txt", "rb") as f:
        flag = f.read().strip()
    key = sha256(str(d).encode()).digest()
    cipher = AES.new(key, AES.MODE_CTR)
    ct = cipher.encrypt(flag)
    nonce = cipher.nonce
    print(f"{ct = }")
    print(f"{nonce = }")

File output.txt

sigs = [(49045447930003829750162655581084595201459949397872275714162821319721992870137, 21098529732134205108109967746034152237233232924371095998223311603901491079093), (8434794394718599667511164042594333290182358521589978655877119244796681096882, 72354802978589927520869194867196234684884793779590432238701483883808233102754), (98981626295463797155630472937996363226644024571226330936699150156804724625467, 78572251404021563757924042999423436619062431666136174495628629970067579789086), (39876682309182176406603789159148725070536832954790314851840125453779157261498, 57493814845754892728170466976981074324110106533966341471105757201624065653133), (65207470758289014032792044615136252007114423909119261801100552919825658080689, 35801670032389332886673836105411894683051812268221960643533854039645456103322), (62310615350331421137050446859674467271639363124966403418757056624834651785981, 35521772482874533704942922179876531774398711539124898773478624535131725819343), (112968103298671409136981160931495676458802276287280410415332578623201858813402, 69136482735760979952358359721969881674752452777485098096528689791122554903910), (65185852906255515620576935005939230631603582432998989514260597054881976462676, 85379997570993122627264764907519703985819259494167121515303052416417601678111), (89525951822575634807524099747751997083879407738240060351122435098952102365970, 73032937908295382442051096857786822685807890991333822263666894552392531234105), (10051482171127490286979879686762557184173302546674808492445781875620932719446, 26217862064468074441046914792412948081058029471697661868711999974556608497458), (8842758449685028748615236698968197767772820788773190926335075554397256573640, 31652804170027719136589492610452674938583230853203431940531961290992398961987), (23751070894286517351443200111133743672788640335816140651282619979550868046371, 62545547750389706281745923819072901405095067763677430386609805435019439100532), (73526459114147520989492697207756783950511563270716718674108128391637651652182, 70851054921933366241324896134628440370210434216441807412696261358563604784468), (57753594385723283080008450150285839290328959323728215111064869128180653466512, 48682503345807264543892350428384011994195616727229911040222271121395096668630), (65263395028919805249304292530249376748389080058707453448295007353333046365479, 10365290276028966530454805043630476285018698618883354555344947391544138993674), (87437293666767613034832827186884716590065056433713359026118257811657437100576, 89500859891014369107213802143650102492250691913844472777312272074978411403745), (82006715584380621917183646856144618837928013528296150149335800289034986391573, 66403597255556240236430083902481022812584785679596388450322939858389337923701)]
ct = b'\xc6*\x17\xcce\xc1y\xb8\xb4\x8d\x87L\xf8\x81QK\xf4\x02\xf2\xf7\x8d\xe0\xe8\x92\xc7\xe7\x8fg\xb1M\xb4.\x89\x18\xf5\x7f\xed\xc3I\x92\x82\xfd\xfe9\x95\xc9(\x90\xce\x93\xb9+\xce\x958\xf3\x05PH'
nonce = b'6\xe7m\xcc\x8e\x0eG '

Đọc đề bài thì mình biết được bài này kết hợp giữa LCG và ECDSA. Cụ thể thì như sau:

ctf

Crypto

This post is licensed under CC BY 4.0 by the author.