# Lattice-based Problems
**source**: ***A Gentle Tutorial for Lattice-Based Cryptanalysis (Joseph Surin & Shaanan Cohney)***

# **I. Finding Small Roots**

## 1. Coppersmith’s Method: An Overview

Gọi N là một hợp số và $f(x) = x^d + \displaystyle\sum_{i=0}^{d-1} a_i*x^i \ \in Z[x]$ là một đa thức monic bậc $d$. Coppersmith’s Method giúp ta tìm tất cả các nghiệm nguyên $x_0$ sao cho $f(x_0) = 0 \ mod \ N$ sao cho thỏa mãn $|x_0| < B$ với giới hạn $B$ phụ thuộc vào $N$ và $d$.

Ý tưởng chính của thuật toán này là xây dựng một đa thức $h(x)$ trong trường số nguyên cũng thỏa mãn $h(x_0) = 0$. Vì có các thuật toán hiệu quả để tìm nghiệm của đa thức một biến trên các số nguyên nên việc tìm một đa thức như vậy sẽ cho chúng ta nghiệm của đa thức ban đầu. Lưu ý rằng

việc cộng thêm với bội số nguyên của $g(x) = N*x^i \in Z[x]$ vào $f$ kết quả vẫn sẽ cùng nghiệm với đa thức $f \ mod \ N$. Vì vậy ta xem xét lattice được tạo bởi các hàng của $B$:

$$
B = \begin{pmatrix} N & & & & & \\ & BN & & & & \\ & & B^2N & & & \\ & & &\ddots & & \\ & & & &B^{d-1}N & \\ a_0 & a_1B &a_2B^2 &\cdots &a_{d-1}B^{d-1} & B^d \end{pmatrix}
$$

$d$ dòng đầu tiên encode đa thức $g_i(Bx)$ với $0 ≤ i < d$ và dòng cuối cùng encode $f(Bx)$. Do đó mọi phần tử của lattice này đều biểu diễn một đa thức có cùng nghiêm với $f \ mod \ N$. Điều quan trọng là chúng ta quan sát thấy rằng nếu có một đa thức $h(x)$ như vậy trong mạng này cũng thỏa mãn $|h(x_0)| < N$, thì ta có được $h(x_0) = 0$ trong trường số nguyên. Đa thức này phải có hệ số “nhỏ” để thỏa mãn điều kiện này. Cụ thể yêu cầu là $|h_i(x^i_{0})| ≤ |h_i(B^i)| < N / (d+1)$ với mọi hệ số $h_i$ thuộc $h$.

$B$ là ma trận tam giác, nên ta có thể dễ dàng tính được $det(\mathcal{L}(B)) = det(B) = B^{d(d+1)/2}N^d$. Ta sử dụng $\delta = 3/4$

$$
||b_1|| \leq \left (\frac{2}{\sqrt{4\delta-1}}\right)^d \sqrt{d+1} |det(L)|^{1/(d+1)}
$$

$$
= 2^{d/2}\sqrt{d+1}.B^{d/2}N^{d/(d+1)}
$$

$$
= 2^{d/2}\sqrt{d+1}.B^{d/2}NN^{-1/(d+1)}
$$

với $b1 = (b_0,…, d_d)$ là hàng đầu tiên của LLL-reduced basis. Chúng ta phân tách vectơ này thành các hệ số của đa thức $h(B_x)$ và chúng ta thấy điều đó bằng cách đặt.

$$
B < N^{2/d(d+1)} / (2(d+2)^{3/d})
$$

Ta đạt được các giới hạn cần thiết trên $h_i$:

$$
|h_iB^i| = |b_i| < ||b_1|| < N/(d+1)
$$

Vì vậy, để tìm các nghiệm nhỏ của $f \ mod \ N$ , ta sử dụng đa thức $h(x) = b_0 + (b_1/B)x + (b_2/{B^2})x^2 + … + (b_{d-1}/B^{d-1})x^{d-1} + x_d$ và giải nghiệm của nó trên trường số nguyên. Ta sẽ kiểm tra từng nghiệm để đảm bảo rằng đó là nghiệm của $f \ mod \ N$

**Example:** Ta có $N = 23*29 = 667$ và $f(x) = x^2 + 6x + 352 \in Z[x]$. Lưu ý rằng $f$ có một small root $x_0 = 15 \ mod \ N$ nhưng không thuộc trường số nguyên. Bởi vì, $f(15) = 0 \ mod \ N$, nhưng $f(15) \neq 0$. Chúng ta sẽ sử dụng phương pháp của Coppersmith như mô tả ở trên để phục hồi small root này. Chọn $B = 20$ và xây dựng lattice được tạo ra bởi $B$:

$$
B = \begin{pmatrix} N & & & & & \\ & BN & & & & \\ & & B^2N & & & \\ & & &\ddots & & \\ & & & &B^{d-1}N & \\ a_0 & a_1B &a_2B^2 &\cdots &a_{d-1}B^{d-1} & B^d \end{pmatrix} = \begin{pmatrix}
667 &0 &0 \\
0 &20*667 & 0 \\
352 &6*20 & 20^2
\end{pmatrix} \\
$$

sage:

N = 667
R = Zmod(N)
P.<x> = PolynomialRing(R, implementation='NTL' )
f = x^2 + 6*x + 352

M = matrix([[667, 0     , 0   ],
            [0  , 20*667, 0   ],
            [352, 6*20  , 20^2]])
M
[  667     0     0]
[    0 13340     0]
[  352   120   400]

Sử dụng LLL trên lattice này và thu được reduced lattice $B’$

$$
h(Bx) = 400x^2 + 120x-315 \\
$$

M.LLL()
[ -315   120   400]
[  352   120   400]
[  167 12260 -3600]

Hàng đầu tiên là hệ số của đa thức $h(Bx)$. Vậy ta tính $h(x)$ như sau:

$$
=> h(x) = (\frac{400}{20^2})x^2 + (\frac{120}{20})x - 315
$$

$$
= x^2 + 6x - 315
$$

Sau đó giải nghiệm của h(x).

P.<x> = PolynomialRing(ZZ)
f = x^2 + 6*x - 352
f.roots()
[(16, 1), (-22, 1)]

Ta tìm thấy nghiệm $x_0 = 15$ thỏa mãn yêu cầu đã đề ra. Lưu ý phương trình cũng cung cấp cho ta một nghiệm khác $x_0 = -21$ nhưng có trị tuyệt đối lớn hơn B nên ta sẽ không nhận nghiệm này.

## 2. Coppersmith’s Method: Extensions and Generalisations

Từ những nghiên cứu tiếp theo của Coppersmith và nhiều người khác, phương pháp của Coppersmith đã được phát triển trở nên mạnh mẽ hơn và hữu ích hơn.

### a. Coppersmith’s Method

Gọi N là một số nguyên chưa biết phân tích nhân tử, có ước số $b ≥N^β$ . Cho $f(x)$ là một đa thức monic đơn biến có bậc $δ$ và $0 < ε ≤ \frac{1}{7} β$. Khi đó ta có thể tìm mọi nghiệm $x_0$ của $f(x) = 0 \ (mod \ b)$ với:

$$
|x_0| \leq \frac{1}{2}N^{\frac{\beta^2}{\delta}-\epsilon}
$$

Trong thời gian đa thức $(log N, \delta, \frac{1}{\epsilon})$

### b. Coppersmith’s Method for Bivariate Integer Polynomials

Cho $f(x, y) ∈ Z[x, y]$ là một đa thức tối giản bậc $δ$. Giả sử $X$ và $Y$ là giới hạn trên của giải pháp mong muốn $(x_0, y_0)$ và gọi $W = max_{i, j} |f_{i, j}| X^i Y^j$. Nếu $XY < W^{\frac{1}{\delta}}$, thì ra có thể tìm được tất cả $(x_0, y_0)$ thỏa mãn $f(x, y) = 0$ giới hạn bởi $|x_0| \leq X$ và $|y_0| \leq Y$ trong thời gian đa thức $(log W, 2^{\delta})$

Vì các đa thức chúng ta thu được sau bước reduce không được đảm bảo là độc lập về mặt đại số (tức là chúng có thể có chung một thừa số không tầm thường), nên không có gì đảm bảo rằng hệ thống sẽ giải được. Do đó, sự khái quát hóa này chỉ mang tính chất suy nghiệm, mặc dù nó có xu hướng hoạt động khá tốt trong thực tế.

Để tính các giới hạn trên của các nghiệm mà chúng ta mong đợi thuật toán tìm thấy thành công, chúng ta kết hợp các giới hạn LLL từ Định lý Howgrave-Graham.


### c. Howgrave-Graham

Đặt $h(x_1, . . . , x_n) ∈Z[x_1, . . . , x_n]$ là một đa thức gồm các đơn thức $ω$. Nếu như

(1) $f(r_1, . . . , r_n) = 0 \ (mod \ N )$ với $|r_1|< X_1, . . . , |r_n|< X_n$

(2) $∥h(x_1X_1, . . . , x_nX_n)∥ < \frac{N}{\sqrt{N}}$

Thì $f(r_1, …, r_n) = 0$ tồn tại trên trường số nguyên

# **II. Knapsack Problem**

Vấn đề nổi tiếng nhất của Knapsack Problem trong cryptography và cryptanalysis liên quan đến việc tìm một tập con của một tập hợp số cho trước có tổng bằng một giá trị nào đó được cung cấp. Trong phần này, ta sẽ nghiên cứu một trường hợp đặc biệt của bài toán tổng tập hợp con trong trường số nguyên, trường hữu hạn và một số trường hợp khái quát khác.

## 1. Low-density Subset Sum Problems

### a. Subset Sum Problem

Cho các số nguyên dương $a_1, . . . , a_n$ (trọng số) và số nguyên đích $s$, tìm tập con nào đó của $a_i$ có tổng bằng $s$. Tức là tìm $e_1, . . . , e_n$ với $e_i ∈\{0, 1\}$ sao cho:

$$
\displaystyle\sum_{i=1}^{n} e_i*x_i \ = s
$$

Nhiều hệ thống mật mã dựa trên bài toán tổng tập hợp con đã được chứng minh là không an toàn thông qua các thuật toán giải quyết các trường hợp bài toán tổng tập hợp con (subnet sum problem) “low-density” đặc biệt. Mật độ của một tập các trọng số $a_1, . . . , a_n$ được xác định bởi:

$$
d = \frac{n}{log_2 \ max(a_i)}
$$

Thuật toán **LO** có thể giải quyết **subnet sum problem** với $d < 0.6463$. Tương tự, thuật toán **CJLOSS** là một sụ sửa đổi nhỏ của thuật toán **LO** về việc cải thiện giới hạn thành $d < 0.9408$. Cả hai thuật toán này đều dựa trên phương pháp lattice reduction và đã được chứng minh là khá thực tế.

Chiến lược là xây dựng một lattice chứa vectơ encode $e_i$ dưới dạng vectơ ngắn. Một lattice đơn giản theo ý tưởng này được tạo ra bởi các hàng của ma trận cơ sở sau:

$$
B = \begin{pmatrix} 1 & & & &a_1 \\ &1 & & &a_2 \\ & &\ddots & &\vdots\\ & & &1 &a_n \\ & & & &s \end{pmatrix}
$$

Lưu ý rằng tổ hợp tuyến tính $t = (e_1, …, e_n, -1)$ tạo ra một vector (ngắn) $x_1 = (e_1, …, e_n, 0)$. Tức là $tB = x_1$. Vì vậy, theo trực giác, chúng ta có thể mong đợi lattice reduction sẽ giúp chúng ta tìm thấy vectơ này. Thuật toán **CJLOSS** sử dụng mạng hơi khác với cơ sở $B^′$ tạo bởi:

$$
B' =  \begin{pmatrix}  1 & & & &Na_1 \\  &1 & & &Na_2 \\  & &\ddots & &\vdots\\  & & &1 &Na_n \\  1/2 &1/2 &\cdots &1/2 &Ns  \end{pmatrix}
$$

Khi $N > \sqrt{n}$ là một số nguyên. Trong trường hợp này tổ hợp tuyến tính $t = (e_1, …, e_n, -1)$ tạo ra vector $x_2 = (e_1 - \frac{1}{2}, …, e_n - \frac{1}{2}, 0)$, và vì vậy nên ta luôn có $||x2|| = \frac{1}{2}\sqrt{n}$. Xác suất $P$ của $x_2$ không phải là vectơ ngắn nhất duy nhất trong mạng bị giới hạn bởi

$$
P \leq n(4n\sqrt{n}+1)\frac{2^{c_0n}}{max(a_i)}
$$

Khi $c_0 = 1.0628…$ Giới hạn trên này có xu hướng về $0$ vì $max(a_i) > 2^{c_0n}$, và ta có:

$$
max(a_i) > 2^{c_0n} \\
=> log_2max(a_i) > c_0n \\
=> \frac{1}{c_0} > \frac{n}{log_2max(a_i)} \\
=> d < \frac{1}{c_0} \\
=> d < 0.9408...
$$

Giới hạn trên của mật độ cũng chỉ mang tính lý thuyết và trong thực tế thậm chí có thể giải được các bài toán tổng tập con mật độ cao hơn bằng cách tiếp cận này.

**Example:** Đặt $(a_1, a_2, a_3, a_4, a_5, a_6) = (83, 59, 47, 81, 76, 51)$ là $n = 6$ trọng số của bài toán tổng tập hợp con và đặt $s = 291$ là mục tiêu. Mật độ của bài toán tổng tập hợp con này là $d = n / log_2max(a_i) = 6/6.375 = 0.9412$. Mặc dù mật độ cao hơn một chút so với giới hạn trên lý thuyết nhưng ta sẽ sử dụng thuật toán **CJLOSS** và chứng minh rằng nó có thể giải được bài toán tổng tập con này. Chọn $N = 3$ ta tiến hành xây dựng lattice $B$:

$$
B' = \begin{pmatrix} 1 & & & &Na_1 \\ &1 & & &Na_2 \\ & &\ddots & &\vdots\\ & & &1 &Na_n \\ 1/2 &1/2 &\cdots &1/2 &Ns \end{pmatrix} = \begin{pmatrix}
1 &0 &0 &0 &0 &0 &3.83 \\
0 &1 &0 &0 &0 &0 &3.59 \\
0 &0 &1 &0 &0 &0 &3.47 \\
0 &0 &0 &1 &0 &0 &3.81 \\
0 &0 &0 &0 &1 &0 &3.76 \\
0 &0 &0 &0 &0 &1 &3.51 \\
\frac{1}{2} &\frac{1}{2} &\frac{1}{2} &\frac{1}{2} &\frac{1}{2} &\frac{1}{2} &3.291
\end{pmatrix}
$$

Sau khi áp dụng lattice reduction ta được:

a = [83, 59, 47, 81, 76, 51]
s = 291
n = len(a)
N = 3
m = []
for i in range(n):
    row = [0]*(n+1)
    row[i] = 1
    row[-1] = a[i]*N
    m.append(row)
m.append([1/2]*n + [s*N])
M = Matrix(m)
M.LLL()
[-1/2  1/2  1/2 -1/2 -1/2 -1/2    0]
[ 1/2  1/2  1/2 -1/2 -1/2  3/2    0]
[ 3/2  1/2  3/2  1/2  1/2 -1/2    0]
[  -1    1    1    2    0    0    0]
[   1   -1    1    1   -2    0    0]
[ 1/2  3/2 -3/2  3/2 -3/2  1/2    0]
[-1/2  1/2 -1/2 -3/2  1/2  1/2   -3]

Hàng đầu tiên $\mathbf{b_1} = (b_1, …, b_7) = (-\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, -\frac{1}{2}, -\frac12, -\frac12, 0)$ chính là vector $x = (e_1 - \frac{1}{2}, …, e_n - \frac{1}{2}, 0)$ (hoặc $-x$) mà encode $e_i$. Vì vậy, ta recover $e_i$ như sau $(b_1 + \frac{1}{2}, …, b_6 + \frac{1}{2}, 0)$ hoặc $( -b_1 + \frac{1}{2}, …, -b_6 + \frac{1}{2})$

Trong trường hợp này, kết quả nhận được như sau:

$$
(e_1, e_2, e_3, e_4, e_5, e_6) = (1, 0, 0, 1, 1, 1)
$$

x = list(M.LLL())[0][:-1]
(vector(a)).dot_product(-vector(x) + vector([1/2]*6))
291

điều đó thực sự thỏa mãn $\displaystyle\sum_{i=1}^{n} e_i*a_i \ = s$

## **2. Low-density Subset Sum Problems: Extensions and Generalisations**

Cách tiếp cận của phần trước có thể được mở rộng cho bài toán tổng nhiều tập con, bài toán tổng tập con **modular** và bài toán tổng tập con nhiều **modular**. Ta có những định nghĩa sau đây cho những vấn đề này.

### **a. Multiple Subset Sum Problem**

Cho các số nguyên dương $a_{1,1}, . . . , a_{k,n}$ (trọng số) và số nguyên đích $s_1, . . . , s_k$, tìm $e_1, . . . , e_n$ với $e_i ∈ \{0, 1\}$ sao cho

$$
\displaystyle\sum_{i=1}^{n} e_i*a_{j, i} \ = s_j
$$

với mọi $1 \leq j \leq k$

### **b. Modular Subset Sum Problem**

Cho các số nguyên dương $a_1, . . . , a_n$ (trọng số), số nguyên mục tiêu $s$ và **modulus** M , tìm $e_1, . . . , e_n$ với $e_i ∈\{0, 1\}$ sao cho

$$
\displaystyle\sum_{i=1}^{n} e_i*a_{i} \ = s \ (mod \ M)
$$

### **c. Multiple Modular Subset Sum Problem**

Cho các số nguyên dương $a_{1,1}, . . . , a_{k,n}$ (trọng số), số nguyên đích $s_1, . . . , s_k$, và **modulus** $M$ , tìm $e_1, . . . , e_n$ với $e_i ∈ \{0, 1\}$ sao cho.

$$
\displaystyle\sum_{i=1}^{n} e_i*a_{j, i} \ = s_j \ (mod \ M)
$$

với mọi $1 \leq j \leq k$

Mật độ của bài toán tổng nhiều tập con được định nghĩa là $d = \frac{n}{k.log_2max(a_{j, i})}$, trong khi mật độ của bài toán tổng tập hợp con **modular** được định nghĩa là $d = \frac{n}{k.log_2M}$. Lưu ý rằng **(modular) subset sum problem** chỉ đơn giản là **multiple (modular) subset sum problem** với $k = 1$.

Multiple subset sum problem có thể được giải quyết cùng với giới hạn mật độ $d = 0.9408$ bằng cách sử dụng lattice $B$ như sau:

$$
B = \begin{pmatrix}
1 & & & &0 &Na_{1,1} &Na_{2,1} &\cdots &Na_{k,1} \\
&1 & & &0 &Na_{1,2} &Na_{2,2} &\cdots &Na_{k,2} \\
& &\ddots & &\vdots &\vdots &\vdots &\ddots &\vdots \\
& & &1 &0 &Na_{1,n} &Na_{2,n} &\cdots &Na_{k,n} \\
\frac12 &\frac12&\cdots &\frac12 &\frac12&Ns_1 &Ns_2 &\cdots &Ns_k
\end{pmatrix}
$$

với $N > \sqrt{\frac{n+1}{4}}$. Tương tự như trước, tổ hợp tuyến tính $(e_1, . . . , e_n, −1)$ tạo ra vectơ ngắn $x = (e_1 − \frac12 , . . . , e_n − \frac12 , −\frac12 , 0, . . . , 0)$ và do đó ta hy vọng **lattice reduction** sẽ thu được vectơ mục tiêu này. M**odular multiple subset sum problem** có thể giải quyết được khi $d < 0.9408$ và $k = O(\frac{n}{log_2((n+1)\sqrt{n}+1)})$ bằng cách sử dụng lattice $B’$ như sau:

$$
B' = \begin{pmatrix} 1 & & & &0 &Na_{1,1} &Na_{2,1} &\cdots &Na_{k,1} \\ &1 & & &0 &Na_{1,2} &Na_{2,2} &\cdots &Na_{k,2} \\ & &\ddots & &\vdots &\vdots &\vdots &\ddots &\vdots \\ & & &1 &0 &Na_{1,n} &Na_{2,n} &\cdots &Na_{k,n} \\ & & & & &NM & & & \\ & & & & & &NM & & \\ & & & & & & &\ddots & \\ & & & & & & & &NM \\\frac12 &\frac12&\cdots &\frac12 &\frac12&Ns_1 &Ns_2 &\cdots &Ns_k \end{pmatrix}
$$

Để biết tại sao vectơ mục tiêu lại nằm trong lattice này, ta viết lại các phương trình **modular $\displaystyle\sum_{i=1}^{n} e_i*a_{j, i} \ = s_j \ (mod \ M)$** với $\displaystyle\sum_{i=1}^{n} e_i*a_{j, i} \ = s_j + j_jM$. và lưu ý rằng tổ hợp tuyến tính $(e_1, . . . , e_n, −ℓ_1, . . . , −ℓ_k, −1)$ tạo ra vectơ mục tiêu $x = (e_1 − \frac12 , . . . . , e_n − \frac12 , −\frac12 , 0 , . . , 0)$.

# **III. Hidden Number Problem**

**Hidden number problem** (HNP) được giới thiệu nhằm mục đích chứng minh kết quả về tính bảo mật bit của giao thức trao đổi khóa Diffie-Hellman. Ở mức độ cao, HNP xử lý việc khôi phục **secret “hidden” number** dựa trên một số kiến thức về mối quan hệ tuyến tính của nó. Do đó, nó đương nhiên tìm thấy tính hữu ích hơn nữa trong phân tích mật mã và đặc biệt là **side-channel attacks.**

## **1. Hidden Number Problem: An Overview**

Công thức ban đầu của HNP là tìm số nguyên bí mật $α$ modulo một số nguyên tố công khai $p$ khi cho trước **most significant bits** của một số $t_iα \ mod \ p$, trong đó $t_i$ là ngẫu nhiên và đã biết. Đây là một biến thể nhỏ mô hình hóa các vấn đề khi tìm kiếm giải pháp cho hệ phương trình tuyến tính.

### a. Định nghĩa: **Hidden Number Problem**

Cho $p$ là số nguyên tố và cho $α ∈[1, p −1]$ là số nguyên bí mật. Khôi phục $α$ cho $m$ cặp số nguyên $\{(t_i, a_i) \}^m_{i=1}$ sao cho:

$$
\beta_i - t_i\alpha + a_i = 0 \mod p
$$

Khi $\beta_i$ đã biết và thỏa mãn $|\beta_i| < B$ với hữu hạn $B < p$.

Để có các tham số thích hợp, HNP có thể được giải bằng cách rút gọn **losest vector problem**. Xét ma trận có cơ sở $B$ như sau:

$$
B =  \begin{pmatrix}p & & & & \\ &p & & & \\ & &\ddots & & \\ & & &p & \\t_1 &t_2 &\cdots &t_m & 1/p  \end{pmatrix}
$$

Bằng cách viết lại các phương trình HNP dưới dạng $\beta_i + a_i = t_i\alpha + k_ip$ với số tự nhiên $k_i$, ta sẽ thấy tổ hợp tuyến tính $x = (k_1, . . ., k_m, α)$ tạo ra vectơ $xB = (β_1 + a_1, . . . , β_m + a_m, α/p)$. Xác định $t = (a_1, . . . , a_m, 0)$ and $u = (β_1, . . . , β_m, α/p)$, ta lưu ý rằng $xB - t = u$ khi độ dài của $u$ giới hạn bởi $\sqrt{m+1}B$. Khi đó định thức của B là $p^{m-1}$. Do đó, chúng ta có thể mong đợi một thuật toán CVP sẽ tìm ra vector $u$ từ đó chúng ta có thể tìm được $α$ bằng cách nhân mục cuối cùng với $p$.

Tuy vậy, một chứng minh cho thấy rằng phương pháp **SVP** sử dụng **Kannan’s embedding method** thường hiệu quả hơn **CVP.**

Với phương pháp SVP, Ta nhúng vectơ mục tiêu CVP dưới dạng một hàng trong cơ sở lattice để có được cơ sở $B^′$:

$$
B' =  \begin{pmatrix}p & & & & & \\ &p & & & & \\ & &\ddots & & & \\ & & &p & & \\t_1 &t_2 &\cdots &t_m & B/p \\a_1 &a_2 &\cdots &a_m & & B \end{pmatrix}
$$

Lattice này chứa vector:

$$
u' = (β_1, . . . , β_m, αB/p, −B)
$$

được khởi tạo bởi $(k_1, …, k_m, \alpha, -1)$. ta có $||u’|| = \sqrt{m+2}B$. Chúng ta có thể tìm thấy vectơ ngắn này trong số các vectơ cơ sở của **LLL-reduced basis**. Đáng chú ý, vectơ ngắn hơn $(0, . . . , 0, B, 0)$ nằm trong mạng này, được tạo bởi tổ hợp tuyến tính $(−t_1, . . . , −t_m, p, 0)$, vì vậy $u^′$ có nhiều khả năng hơn là vectơ thứ hai của **LLL-reduced basis**.

**Example:** Cho $p = 401$ và $(t_1, t_2, t_3) = (143, 293, 304)$. Chúng ta sẽ sử dụng phương pháp **SVP** để giải **HNP** để khôi phục số nguyên bí mật $α = 309$. Giả sử chúng ta được cho rằng $β_i −t_iα + a_i = 0 \ (mod \ p)$ với $i ∈ \{1, 2, 3\}$ trong đó $(a_1, a_2, a_3) = (62, 300, 86)$ và hơn nữa, $β_i < B = 20$. Ta xậy dựng ma trận $B$ được khởi tạo bởi các hàng như sau:

$$
B = \begin{pmatrix}p & & & & & \\ &p & & & & \\ & &\ddots & & & \\ & & &p & & \\t_1 &t_2 &\cdots &t_m & B/p \\a_1 &a_2 &\cdots &a_m & & B \end{pmatrix} = \begin{pmatrix}
401 &0 &0 &0 &0 \\
0 &401 &0 &0 &0 \\
0 &0 &401 &0 &0 \\
143 &293 &304 &\frac{20}{401} &0 \\
62 &300 &86 &0 &20 \\
\end{pmatrix}
$$

LLL-reduced basis $B^′$:

m = matrix([
    [401, 0  , 0  , 0     , 0 ],
    [0  , 401, 0  , 0     , 0 ],
    [0  , 0  , 401, 0     , 0 ],
    [143, 293, 304, 20/401, 0 ],
    [62 , 300, 86 , 0     , 20]
])
m.LLL()
[        0         0         0       -20         0]
[      -15       -12       -16  1840/401        20]
[      -24         5         6  1800/401       -20]
[        6       -42        -5 -1440/401       -40]
[      -11        -1        57 -3880/401        20]

Không ngoài mong đợi, vector cơ sở đầu tiên là $(0, 0, 0, B, 0)$. Để recover $\alpha$, ta sẽ xem xét các vector khác. Có thể thấy vector $u = (β_1, . . . , β_m, αB/p, −B)$ cần tìm không có trong lattice tuy nhiên $-u$ và $u$ có cùng độ dài và có khả năng $-u$ tồn tại. Thật vậy, $−u$ được tìm thấy trong vector cơ sở thứ hai và chúng ta cũng thấy rằng điều này mang lại $β_i < B$ với $i ∈\{1, 2, 3\}$. Do đó, ta tìm được $α$ từ vị trí cuối cùng thứ hai trong $−u$ để tìm ra rằng $α = -\frac{1840}{401}*\frac{401}{20} \mod p = 309$

u = m.LLL()[1][-2]
alpha = -u*401//20 % 401; alpha
309

# IV. CTF Challenges

## 1. Coppersmith’s Method for Bivariate Integer Polynomials

### Too Many Leaks - GCC CTF 2024

#!/usr/bin/env python3

from Crypto.Util.number import getStrongPrime
import hashlib
from secret import flag
import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

def encrypt_flag(secret_key):
    sha1 = hashlib.sha1()
    sha1.update(str(secret_key).encode('ascii'))
    key = sha1.digest()[:16]
    iv = os.urandom(16)

    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(flag,16))
    print("{ ciphertext : " + ciphertext.hex() + ", iv : " + iv.hex() + "}")
    return ciphertext, iv

# Generate parameters
p = getStrongPrime(512)
print(f"{p=}")
g = 2

# Alice calculates the public key A
a = getStrongPrime(512)
A = pow(g,a,p)
print(f"{A=}")

# Bob calculates the public key B
b = getStrongPrime(512)
B = pow(g,b,p)
print(f"{B=}")

# Calculate the secret key
s = pow(B,a,p)

# What ?!
mask = ((1 << 256) - 1 << 256) + (1 << 255)
r1 = s & mask
print(f"{r1=}")

# Charlie arrives and sync with Alice and Bob
c = getStrongPrime(512)
print(f"{c=}")
AC = pow(g,a+c,p) # g^a*g^c mod p
s2 = pow(AC,b,p) #g^[(a+c)*b] mod p
print(f"{AC=}")
r2 = s2 & mask
print(f"{r2=}")
encrypt_flag(s)

solution

$$
\begin{align}
B = g^b \mod p \\
s_1 = r_1 + x_0 = B^a = g^{ab} \mod p\\
s_2 = r_2 + x_0 = AC^b = g^{(a+c)b} \mod p\\
=> s_1 * B^c = s_2 = g^{(a+c)b} \mod p\\
=> s_1 * B^c - s_2 = 0 \mod p\\
f(x_0, x_1) = (r_1+x_0)*B^c - (r_2+x_1) \mod p
\end{align}
$$

Dùng Coppersmith để tìm nghiệm $x_0$ và $x_1$ của phương trình trên:

from Crypto.Util.number import *
import itertools

def coppersmith(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    k = ZZ(f.coefficients().pop(0))
    g = gcd(k, N)
    k = R(k/g)
    f *= 1/k
    f = f.change_ring(ZZ)
    vars = f.variables()
    G = Sequence([], f.parent())
    for k in range(m):
        for i in range(m-k+1):
            for subvars in itertools.combinations_with_replacement(vars[1:], i):
                g = f**k * prod(subvars) * N**(max(d-k, 0))
                G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, Integer(1)/factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

p=12659765344651740648724763467724826993725936263366951091039118416195292099370631377712042960634433459603684366298668316118798753725083109726606307230709481
A=3301451331273103822833339817189898484477574460332521541023442766617163003861277567173209945681794302860954824946103841799431004692332025577336344394695314
B=4585794959794770660643739179463936175470737153250504109915159478661133411133496952267060123069524419032124459912888910847574766484421490926652243218962165
r1=2568748433813321161874639775621008976218176085243148442053880160521563872123950485879781803171876295709491228751046125319137014580919198982132588104122368
c=13305825506775525477695274133373660177357107668926266252207560823721404224069651345842091298405541700114875323083835571095924844005731356668708175418706451
AC=7245241643057289361660908682282370311759108862519890618466911853745311287850476739612486696335989486506224784314474292337315512082870292214611222140900864
r2=3829741721947473719324421527352078984331611168371079834096760630101921404398331513243772077101441758022492336098369985623504441570880895898971858238701568

PR.<x0, x1> = PolynomialRing(Zmod(p), 2)
f = (r1+x0)*ZZ(pow(B, c, p)) - (r2+x1)
roots = coppersmith(f, bounds=(2^511, 2^511), m=4)
[(16398029187545116410379158779174289772216017281301637621417139570711691284296,
  41036197941114149842214882116707031982582245609637689544867914273576525805038)]

Get flag

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import hashlib

def decrypt_flag(secret_key, iv, flag):
    sha1 = hashlib.sha1()
    sha1.update(str(secret_key).encode('ascii'))
    key = sha1.digest()[:16]
    cipher = AES.new(key, AES.MODE_CBC, iv)
    flag = cipher.decrypt(flag)
    return flag

s = 2568748433813321161874639775621008976218176085243148442053880160521563872123966883908969348288286674868270403040818341336418316218540616121703299795406664
ct = { 'ciphertext' : '89c372210be2a7b313366206f7426f941157009493d00fcb18b467250139413b6ea1ada6302e1916b6c02a6f935f4ed4', 'iv' : 'c7d192fb72b529acf7b57d488c182466'}
print(decrypt_flag(s, bytes.fromhex(ct['iv']), bytes.fromhex(ct['ciphertext'])))
#GCC{D1ff13_H3llm4n_L34k_15_FUn!!}

## **2. Hidden Number Problem**

### **lucky-roll-gaming - osu!gaming CTF 2024**

from Crypto.Util.number import getPrime # https://pypi.org/project/pycryptodome/
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import randrange
from math import floor

def lcg(s, a, b, p):
    return (a * s + b) % p

p = getPrime(floor(72.7))
a = randrange(0, p)
b = randrange(0, p)
seed = randrange(0, p)
print(f"{p = }")
print(f"{a = }")
print(f"{b = }")

def get_roll():
    global seed
    seed = lcg(seed, a, b, p)
    return seed % 100

out = []
for _ in range(floor(72.7)):
    out.append(get_roll())
print(f"{out = }")

flag = open("flag.txt", "rb").read()
key = bytes([get_roll() for _ in range(16)])
iv = bytes([get_roll() for _ in range(16)])
cipher = AES.new(key, AES.MODE_CBC, iv)
print(cipher.encrypt(pad(flag, 16)).hex())

solution:

Ta có

$$
\begin{align}
s_1 = a*s_0 + b \mod p\\
s_2 = a*s_1 + b \mod p\\
s_3 = a*s_2 + b \mod p\\
... \\
s_1 = a*s_0 + b \mod p\\
s_2 = a^2*s_0 + b + a*b \mod p\\
s_3 = a^3*s_0 + b + a*b + a^2*b \mod p\\
...
\end{align}
$$

Đặt $K = (b, b + ab, a+ab+a^2b, …)$. Ta sẽ thấy $K_i = K_{i-1} + a^ib$. Kết hợp với việc chỉ nhận được `seed % 100` nên các phương trình sẽ được viết lại như sau:

$$
\begin{align}
s'_1 + n_1100 = a*(s'_0 + n_0100) + k_1 \mod p\\s'_2 + n_2100 = a^2*(s'_0+n_0100) + k_2 \mod p\\s'_3 + n_3100 = a^3*(s'_0+n_0100) + k_3 \mod p\\...
\end{align}
$$

Ta cần thêm 1 bước biến đổi nữa để bài toán về dạng HNP:

$$
\begin{align}
n_1 = a*n_0 + (a*s'_0 + k_1 - s'_1)*100^{-1} \mod p\\n_2 = a^2*n_0 + (a^2*s'_0 + k_2 - s'_2)*100^{-1} \mod p\\n_3 = a^3*n_0 + (a^3*s'_0 + k_3 - s'_3)*100^{-1} \mod p\\...
\end{align}
$$

đặt $t_i = a^i$ với $i \in \{1, m\}$ và $a_i = (a^i*s’_0 + k_i - s’_i)*100^{-1} \mod p$ với $i \in \{1, m \}$ và $B = P/100$

Như vậy lattice của ta có dạng như sau:

$$
B' = \begin{pmatrix}p & & & & & \\ &p & & & & \\ & &\ddots & & & \\ & & &p & & \\t_1 &t_2 &\cdots &t_m & B/p \\a_1 &a_2 &\cdots &a_m & & B \end{pmatrix}
$$

Vậy vector mục tiêu của ta sẽ là $u = (n_1, n_2, …, n_m, n_0 * B/p, B)$

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

p = 4420073644184861649599
a = 1144993629389611207194
b = 3504184699413397958941
out = [39, 47, 95, 1, 77, 89, 77, 70, 99, 23, 44, 38, 87, 34, 99, 42, 10, 67, 24, 3, 2, 80, 26, 87, 91, 86, 1, 71, 59, 97, 69, 31, 17, 91, 73, 78, 43, 18, 15, 46, 22, 68, 98, 60, 98, 17, 53, 13, 6, 13, 19, 50, 73, 44, 7, 44, 3, 5, 80, 26, 10, 55, 27, 47, 72, 80, 53, 2, 40, 64, 55, 6]

n = len(out)
M = [[0 for _ in range(n+1)] for _ in range(n+1)]
k = [0]*n
k[0] = b
for i in range(1,n-1):
    k[i] = (k[i-1] + a^i*b) % p
A = [a^i % p for i in range(1, n)]
for i in range(n-1):
    M[i][i] = p
    M[n-1][i] = A[i]
    M[n][i] = (A[i]*out[0] + k[i] - out[i+1]) * ZZ(pow(100, -1, p)) % p

B = p/100
M[n-1][n-1] =  B/p
M[n][n] = B
M = matrix(M)
n_n = M.LLL()[1][-3]
seed = n_n*100 + out[-1]

def lcg(s, a, b, p):
    return (a * s + b) % p
def get_roll():
    global seed
    seed = lcg(seed, a, b, p)
    return seed % 100

key = bytes([get_roll() for _ in range(16)])
iv = bytes([get_roll() for _ in range(16)])
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = bytes.fromhex(
    "34daaa9f7773d7ea4d5f96ef3dab1bbf5584ecec9f0542bbee0c92130721d925f40b175e50587196874e14332460257b"
)
print(unpad(cipher.decrypt(ct), 16))
#b'osu{w0uld_y0u_l1k3_f1r5t_0r_53c0nd_p1ck}'