III. Một số bài toán trên lưới

1. Bài toán Knapsack và Subset Sum

Bài toán:

Tìm các giá trị $x_1,x_2,...x_n$ biết rằng:

• $x_i \in \{0,1\}$
• $A = \sum x_i a_i$

Với $A, a_i$ là các giá trị cho trước.

Bài toán này có hai cách gọi phổ biến:

• Knapsack Problem (bài toán balo), xuất phát từ ý tưởng chọn một tập hợp con tối ưu từ các vật phẩm.
• Subset Sum Problem (bài toán tổng tập con), tập trung vào việc tìm một tập con của các số $a_i$ sao cho tổng của chúng bằng $A$.

Bài toán này liên quan mật thiết đến mật mã công khai Merkle-Damgård, trong đó bài toán subset sum được sử dụng làm cơ sở toán học để xây dựng các hệ thống mã hóa. Tuy nhiên, nếu bài toán subset sum có mật độ thấp (low-density subset sum), nó có thể bị phá vỡ bằng phương pháp Lattice Reduction, cụ thể là thuật toán LLL (Lenstra–Lenstra–Lovász).

Phân tích và ý tưởng giải

Bài toán có thể được đưa về bài toán trên mạng số nguyên (lattice). Cụ thể, ta dựng một ma trận $B$ có kích thước $(n+1)\times (n+1)$ như sau:

$$\begin{pmatrix} 2 & & & & & a_1 \\ & . & & & & a_2\\ & & . & & & .\\ & & & 2 & & .\\ & & & & 2 & a_n\\ 1 & 1 & . & 1 & 1 & A \\ \end{pmatrix}$$

Xét các Vector theo hàng ta thấy $v = (2x_1-1,2x_2-1,...,2x_n-1,0) \in \mathcal{L}$

Vector này chỉ nhận giá trị $\pm 1$ nên ta mong nó có thể đủ nhỏ để hoặc $v$ hoặc $-v$ lọt vào mạng LLL.

Mẫu giải bài toán này sử dụng Sagemath:

def solve(A, a: list): """ Return tuple (x1,x2,...xn) such x1*a1 + x2*a2 + ... + xn*an = A for xi in {0,1} """ # Generate Matrix n = len(a) list_mat = [] for i in range(0,n): v = [0,] * i + [2,] + [0,] * (n - 1 - i) + [a[i],] list_mat.append(v) v = [1,] * n + [A,] list_mat.append(v) B = matrix(ZZ, list_mat) B = B.LLL() # Find solution in B after LLL solution = [] for v in B: if v[n] == 0: x = [] for i in range(n): if v[i] != 1 and v[i] != -1: break x.append((v[i]+1) // 2) if len(x) == n: # Check solution t = 0 for i in range(0,n): t += x[i] * a[i] if t == A: solution.append(x) t = 0 for i in range(0, n): t += (1-x[i]) * a[i] x[i] = 1 - x[i] if t == A: solution.append(x) return solution 

Thuật toán giải

Xây dựng ma trận $\mathbf{B}$:

• Với mỗi $a_i$, tạo một hàng trong ma trận $v_i = (0, \ldots, 2, \ldots, 0, a_i)$, với $2$ nằm ở vị trí thứ $i$.
• Hàng cuối cùng là $(1, 1, \ldots, 1, A)$.

Áp dụng thuật toán LLL trên ma trận:

• Thuật toán LLL sẽ tìm các vector ngắn trong lattice.
• Một vector ngắn có dạng $(2x_1-1, 2x_2-1, \ldots, 2x_n-1, 0)$ có thể được tìm ra.

Xác định nghiệm từ vector ngắn:

• Từ vector ngắn $v = (2x_1-1, 2x_2-1, \ldots, 2x_n-1, 0)$, tính:

  $$x_i = \frac{v_i + 1}{2}, \forall i \in \{1, \ldots, n\}.$$

• Kiểm tra tính chính xác của nghiệm:

  $$\sum_{i=1}^n x_i a_i = A.$$

Xét các hoán vị khác:

• Có thể cần xem xét nghiệm đảo $1 - x_i$ (vì $x_i$ thuộc $\{0, 1\}$) để tìm tất cả các nghiệm.

Lưu ý

• Thuật toán LLL hiệu quả cho bài toán mật độ thấp (low-density subset sum). Nếu mật độ cao, bài toán trở nên khó hơn và có thể yêu cầu các kỹ thuật khác.
• SageMath hoặc các thư viện toán học tương tự như NumPy không tích hợp trực tiếp LLL, vì vậy cần cài đặt thư viện hoặc sử dụng SageMath.

Challenge CTF bạn có thể thử: Knapsack Ls Cookie Arena CTF 2022.

2. Approximate GCD

Bài toán:

Cho các số $x_i = q_i p + r_i$, với $r_i$ nhỏ. Tìm $p$ là ước chung lớn nhất (GCD) của các mẫu, với sai số $r_i$

Trong một số trường hợp $r_0 = 0$: Tức là $x_0 = q_0p$, ta có thể nghĩ đến trường hợp RSA với 1 số thông tin bổ sung

Phân tích và ý tưởng

Với $x_i=q_ip+r$, ta có thể viết:

$$q_0x_i-q_ix_0=q_0r_i-q_ir_0$$

Vế trái $q_0x_i-q_ix_0$ phụ thuộc vào các $x_i, x_0, q_i, q_0$, vế phải $q_0r_i-q_ir_0$ rất nhỏ vì $r_i, r_0$ rất nhỏ.

Do đó, ta có thể tạo ra một vector ngắn trong một lattice (mạng số nguyên) chứa các phần tử của $q_0x_i-q_ix_0$. Kỹ thuật lattice reduction (LLL) sẽ giúp chúng ta tìm các vector ngắn, từ đó suy ra $p$.

Giới hạn $r_i$ bẳng cách đặt $W = 2^\lambda$ thoả mãn $r_i \leq W$ và $W$ nhỏ nhất.

Tăng trọng số các sai số $r_i$ trong lattice để tối ưu tìm vector ngắn.

Xây dựng ma trận:

\begin{pmatrix} 2^{\lambda+1} & x_1 & x_2 & \ldots & x_n \ 0 & x_0 & 0 & \ldots & 0 \ 0 & 0 & x_0 & \ldots & 0 \ \vdots & \vdots & \vdots & \ddots & \vdots \ 0 & 0 & 0 & \ldots & x_0 \end{pmatrix}

Để ý rằng $$q_0x_i - q_ix_0 = q_0r_i - q_ir_0$$.

Nên shortvector là $$v = (2^{\lambda+1} q_0, q_0 r_1 - q_1 r_0, ...,q_0r_n - q_nr_0)$$ sẽ lọt vào mạng lưới Lattice, và để ý rằng $q_0x_i - q_ix_0$ sẽ có giá trị rất nhỏ do $$ \frac{x_i}{x_0} \approx \frac{q_i}{q_0}$$.

Vì vậy ta có thể tìm ra giá trị $q_0$.

Bạn đọc có thể dựng lại Code để có thể hiểu hơn về bài toán này.

Một challenge CTF có thể thử: Sign trong ISITDTU CTF Quals 2024.

#!/usr/bin/env python3 import os from Crypto.Util.number import *
from Crypto.Signature import PKCS1_v1_5
from Crypto.PublicKey import RSA
from Crypto.Hash import SHA256 flag = b'ISITDTU{aaaaaaaaaaaaaaaaaaaaaaaaaa}'
flag = os.urandom(255 - len(flag)) + flag def genkey(e=11): while True: p = getPrime(1024) q = getPrime(1024) if GCD(p-1, e) == 1 and GCD(q-1, e) == 1: break n = p*q d = pow(e, -1, (p-1)*(q-1)) return RSA.construct((n, e, d)) def gensig(key: RSA.RsaKey) -> bytes: m = os.urandom(256) h = SHA256.new(m) s = PKCS1_v1_5.new(key).sign(h) ss = bytes_to_long(s) return s def getflagsig(key: RSA.RsaKey) -> bytes: return long_to_bytes(pow(bytes_to_long(flag), key.d, key.n)) key = genkey() while True: print( """=================
1. Generate random signature
2. Get flag signature
=================""" ) try: choice = int(input('> ')) if choice == 1: sig = gensig(key) print('sig =', sig.hex()) elif choice == 2: sig = getflagsig(key) print('sig =', sig.hex()) except Exception as e: print('huh') exit(-1)

Đoạn mã trên chứa một hệ RSA với:

• $n=p\times q$ là module RSA
• $e=11$ là số mũ công khai
• $d = e^{-1} \mod \phi(n)$ là số mũ bí mật

Trường hợp sai số nhỏ: Sai số $r_i$ có thể được mô hình hóa, và bài toán trở thành Approximate GCD. Sử dụng các chữ ký $x_i=q_ip+r$, ta có thể xây dựng lattice để tìm 𝑝 p

Trong trường hợp $r_0=0$, tấn công có thể dễ dàng hơn nếu $x_0$ là một bội của $p$.

3. Một số ứng dụng khác

Recovery a Polynomial from one solution in $\mathbb{C}$

Như mình đã biết một đa thức bậc $n$ thì phải cần ít nhất $n+1$ cặp giá trị $(x_i,f(x_i))$ để khôi phục lại nó, hoặc là $n$ nghiệm phức của nó.

Như vậy nếu có 1 thì sao? LLL cho phép ta làm điều đó!

Challenge:

import os
import random
bits = 1111
C = ComplexField(bits)
P = PolynomialRing(C, names='x')
(x,) = P.gens()
key = os.urandom(256)
coeff = [int.from_bytes(key[i:i+16], 'little') for i in range(0, len(key), 16)]
f = sum([a * x ** i for i, a in enumerate(coeff)])
r = random.choice(f.roots())[0]
print(r) # Hint

Xét đa thức $f(x) = a_0 + a_1x+ a_2x^2 + ... + a_nx^n$ có nghiệm $r$.

Đặt $r_j = re(r^j), i_j = im(r^j)$ với $j = \overline{1,n}$.

Xét ma trận kích thức $n+1 \times n+3$ sau:

$$\begin{pmatrix} 1 & & & & & & 0 & 1 \\ & 1 & . & & & & i_1 & r_1\\ & & 1 & . & & & i_2 & r_2\\ & & & 1 &. & &. & .\\ & & & & 1 & . & i_{n-1} & r_{n-1}\\ .& & . & & & 1 & i_n & r_n \\ \end{pmatrix}$$

Ta thấy Vector $(a_0, a_1 , a_2, ..., a_n , \epsilon_0, \epsilon_1)$ sẽ thuộc LLL nhưng mà LLL không dùng được trong số thực, vậy làm sao để fix.

Như ta đã biết thì số thực trong máy tính sẽ được lưu với độ chính xác nhất định, như ở code trên có lấy độ chính xác là 1111 bits, như vậy ta chỉ cần nhân với $2^{1111}$ và làm tròn về số nguyên, khi dùng LLL thì Vector $(a_0, a_1 , a_2, ..., a_n , k_0, k_1)$ cũng sẽ thuộc LLL với $k_0$, $k_1$ là 2 số gần $0$.

round(2**1111 * i_j)

Như vậy ta có hàm giải bài này như sau:

def solve(n, bits, r): """ ::param n số bậc của đa thức ::param bits độ chính xác của số thực ::param r nghiệm của đa thức có thể ở dạng (re,im) return tuple của hệ số (a_0, a_1, ..., a_n) """ C = ComplexField(bits) r = C(r) real = [(r ** i)[0] for i in range(n + 1)] imag = [(r ** i)[1] for i in range(n + 1)] K = 2 ** (bits) M = matrix([ [round(K * x) for x in imag], [round(K * x) for x in real] ]) M = matrix.identity(n + 1).stack(M) M = M.T.LLL() coeff = M[0].list()[:n+1] if all(i < 0 for i in coeff): coeff = [-i for i in coeff] return coeff M = solve(15, 1111, r)
print(M)

Tài liệu tham khảo

• https://cryptohack.org/challenges/post-quantum/
• https://en.wikipedia.org/wiki/Lattice-based_cryptography