<div style="text-align:center">
<h1>Lattice-Based Cryptography</h1>
</div>
Kể từ khi được phát minh vào năm 1982, **thuật toán LLL**, và rộng hơn là **giảm lưới (lattice reduction)**, đã làm phong phú thêm lĩnh vực phân tích mật mã nhờ khả năng ứng dụng rộng rãi của nó trong việc tấn công nhiều dạng hệ mật khóa công khai. Trong số nhiều ứng dụng, kỹ thuật **giảm lưới** đã được sử dụng để tấn công **hệ mật Merkle-Hellman**, bộ tạo số ngẫu nhiên tuyến tính bị cắt cụt **(truncated LCGs)**, **RSA với số mũ công khai nhỏ, RSA với số mũ bí mật nhỏ**, và **(EC)DSA với giá trị nonce không an toàn**.
Mặc dù tài liệu nghiên cứu về ứng dụng của **kỹ thuật giảm lưới (lattice reduction)** vào phân tích mật mã rất phong phú, thế nhưng các thuật toán được trình bày cùng với yêu cầu về nền tảng toán học thường khiến chủ đề này trở nên khó tiếp cận. Chính vì vậy, mình sẽ cố gắng trình bày thật chi tiết về Lưới **(Lattice)**, một số cuộc tấn công dựa trên lưới **(lattice-based attacks)**,... cùng với những kiến thức nền tảng cần thiết để hiểu và phát triển các cuộc tấn công đó. Chắc chắn nó sẽ không thể đầy đủ và chính xác tuyệt đối, nên mong quý độc giả hãy để lại Feedback để mình hoàn thiện hơn :smiling_face_with_smiling_eyes_and_hand_covering_mouth:
# Các kiến thức cần có
Trước khi vào với Lattice thì ta cần phải ôn lại một chút về Đại số tuyến tính.
## Vectors
Vector là một đoạn thẳng có hướng. Đoạn thẳng này biểu thị phương, chiều, độ lớn (chiều dài của vectơ). Ví dụ trong mặt phẳng cho hai điểm phân biệt A và B bất kì ta có thể xác định được vectơ $\overrightarrow{AB}$ hoặc $\overrightarrow{BA}$
Ví dụ : Trong mặt phẳng $Oxy$, hay không gian $\mathbb{R}^2$, cho điểm $A(x_a,y_a)$ và $B(x_b,y_b)$. Khi đó Vector $\overrightarrow{AB}=(x_b-x_a, y_b-y_a)$. Giả sử ta lấy $A(0,1)$ và $B(2,2)$, khi đó Vector $\overrightarrow{AB}=(2-0, 2-1)=(2,1)$.
Ta có thể tính toán Vector trên Sagemath như sau :
```python=
sage: OA = vector([0,1])
sage: OB = vector([2,2])
sage: OA + OB
(2, 3)
sage: OB - OA
(2, 1)
```
Hình minh họa : 
## Không gian Vectors
### Định nghĩa
Một vectơ được định nghĩa qua trường $F$ là một tập $V$ cùng với 2 toán tử thỏa mãn 8 tiên đề dưới đây. Theo đó, $V × V$ kí hiệu cho phép nhân **Cartesian** của $V$ với chính nó, và $→$ kí hiệu cho một ánh xạ từ một nhóm đến một nhóm khác
Toán tử đầu tiên, được gọi là phép cộng vector hoặc đơn giản là phép cộng $(+)$ :$V×V→V$, lấy 2 vectơ bất kì $v$ và $w$ và đánh dấu một vector thứ 3 được viết là $v + w$, được gọi là tổng của các vector.
Toán tử thứ hai được gọi là phép nhân vô hướng: $F × V → V$, lấy một vô hướng $a$ bất kì và một vector $v$, cho ta một vector khác $av$
Cho $V$ là một tập hợp với phép toán $(+),(\times)$. $V$ được gọi là **không gian vector** trên $\mathbb{R}$ nếu với mọi $u,v,w \in V$ và $\alpha, \beta \in \mathbb{R}$ ta có 8 tính chất sau :
- $u+v=v+u$
- $(u+v)+w=u+(v+w)$
- Tồn tại $0\in V$ : $u+0=0+u=u$
- Tồn tại $u'\in V$ : $u'+u=u+u'=0$
- $(\alpha\beta).u=\alpha(\beta.u)$
- $(\alpha+\beta).u=\alpha.u+\beta.u$
- $\alpha.(u+v)=\alpha.u+\alpha.v$
- $1.u=u$
Bổ sung thêm :
- Với mọi $u,v\in V$, ta có $u+v∈V$
- Với mọi $u∈V$ và $\alpha∈\mathbb{R}$, ta có $\alpha.u∈V$
Ví dụ : Cho $W=[(x_1,x_2,x_3)\in\mathbb{R}^3|x_1+x_2-2x_3=1]$. Khi đó, $W$ không phải không gian Vector bởi vì :
- $u=(1,2,1)\in W$ và $v=(2,3,2)\in W$
- Nhưng $u+v=(3,5,3)\notin W$
Ví dụ khác : Cho $V=[(x_1,x_2,x_3)\in\mathbb{R}^3|2x_1+3x_2+x_3=0]$. Khi đó $V$ là không gian Vector bởi vì :
- Chọn $a=(a_1,a_2,a_3$) và $b=(b_1,b_2,b_3$) $\in V$. Khi này, $2a_1+3a_2+a_3=0$ và $2b_1+3b_2+b_3=0$
- Xét $c=(c_1,c_2,c_3)=a+b=(a_1+b_1,a_2+b_2,a_3+b_3)$, ta có :
$$
2c_1+3c_2+c_3=2(a_1+b_1)+3(a_2+b_2)+(a_3+b_3)
$$
$$
\Leftrightarrow (2a_1+3a_2+a_3) + (2b_1+3b_2+b_3)=0+0=0
$$
- Xét $d=(d_1,d_2,d_3)=\alpha.a=(\alpha.a_1,\alpha.a_2,\alpha.a_3)$. Dễ thấy $2d_1+3d_2+d_3=\alpha.(2a_1+3a_2+a_3)=0$
Như vậy, $V$ là không gian Vector
### Tổ hợp tuyến tính - Biểu diễn tuyến tính
Cho $u_1,u_2,..,u_n\in V$. Một tổ hợp tuyến tính của $u_1,u_2,..,u_n$ là một vector $u$ có dạng:
$$
u =\sum_{i=1}^{n} \alpha_iu_i=\alpha_1u_1+\alpha_2u_2+...+\alpha_nu_n, \text{ }\alpha_i\in\mathbb{R}
$$
Khi đó đẳng thức trên được gọi là ***dạng biểu diễn*** của $u$ theo các vector $u_1,u_2,...,u_n$.
Ví dụ : Vector $u=(4,4,2)$ là tổ hợp tuyến tính của các vector $u_1=(1,-1,2)$, $u_2=(2,3,-1)$, $u_3=(0,1,-2)$ vì :
$$
u=0u_1+2u_2-2u_3
$$
Vector $\overrightarrow{0}$ luôn là tổ hợp tuyến tính của $u_1,u_2,...,u_n$ vì :
$$
0=0u_1+0u_2+...+0u_n
$$
Trong không gian $\mathbb{R}^n$. Giả sử :
$$
\begin{cases}
u = (b_1,b_2,...,b_n)\\
u_1 = (u_{11},u_{21},...,u_{n1})\\
u_2 = (u_{12},u_{22},...,u_{n2})\\
\quad \vdots \\
u_n = (u_{1n},u_{2n},...,u_{nn})
\end{cases}
$$
Xét phương trình :
$$
u=\alpha_1u_1+\alpha_2u_2+...+\alpha_nu_n
$$
Khi đó ta có :
$$
\begin{cases}
u_{11}\alpha_1+u_{12}\alpha_2+...+u_{1n}\alpha_n=b_1\\
u_{21}\alpha_1+u_{22}\alpha_2+...+u_{2n}\alpha_n=b_2\\
\quad \vdots \\
u_{n1}\alpha_1+u_{n2}\alpha_2+...+u_{nn}\alpha_n=b_1\\
\end{cases}
$$
- Nếu hệ phương trình trên vô nghiệm thì $u$ không phải là tổ hợp tuyến tính của $u_1,u_2,..,u_n$
- Nếu hệ phương trình trên có nghiệm $(\alpha_1,\alpha_2,...\alpha_n)$ thì $u$ là tổ hợp tuyến tính của $u_1,u_2,..,u_n$ có dạng :
$$
u=\alpha_1u_1+\alpha_2u_2+...+\alpha_nu_n
$$
Ví dụ : Cho $u=(9,13,10)$. Hỏi $u$ có là tổ hợp tuyến tính của các vector $u_1=(1,2,3)$, $u_2=(1,-1,4)$, $u_3=(1,3,-2)$
Ta lập hệ phương trình như sau :
$$
\begin{cases}
\alpha_1+\alpha_2+\alpha_3=9\\
2\alpha_1-\alpha_2+3\alpha_3=13\\
3\alpha_1+4\alpha_2-2\alpha_3=10\\
\end{cases}
$$
Viết dưới dạng ma trận ta có :
$$
\begin{bmatrix}
1 & 1 & 1 \\
2 & -1 & 3 \\
3 & 4 & -2 \\
\end{bmatrix}
\times
\begin{bmatrix}
\alpha1 \\
\alpha2 \\
\alpha3 \\
\end{bmatrix} =
\begin{bmatrix}
9 \\
13 \\
10 \\
\end{bmatrix}
$$
$$
\Leftrightarrow
\begin{bmatrix}
\alpha1 \\
\alpha2 \\
\alpha3 \\
\end{bmatrix} =
\begin{bmatrix}
1 & 1 & 1 \\
2 & -1 & 3 \\
3 & 4 & -2 \\
\end{bmatrix}^{-1}
\times
\begin{bmatrix}
9 \\
13 \\
10 \\
\end{bmatrix} =
\begin{bmatrix}
2 \\
3 \\
4 \\
\end{bmatrix}
$$
Vậy $u$ là tổ hợp tuyến tính của $u_1,u_2,u_3$ có dạng :
$$
u=2u_1+3u_2+4u_3
$$
### Độc lập tuyến tính - Phụ thuộc tuyến tính
Cho $u_1,u_2,..,u_n\in V$. Xét phương trình :
$$
\alpha_1u_1+\alpha_2u_2+...+\alpha_nu_n=0
$$
- Nếu phương trình chỉ có nghiệm tầm thường : $\alpha_1=\alpha_2=...=\alpha_n=0$ thì ta nói {$u_1,u_2,..,u_n$} ***độc lập tuyến tính.***
- Nếu ngoài nghiệm tầm thường, phương trình còn có nghiệm khác thì ta nói {$u_1,u_2,..,u_n$} ***phụ thuộc tuyến tính.***
Một cách phát biểu khác :
- Nếu phương trình có nghiệm duy nhất thì {$u_1,u_2,..,u_n$} ***độc lập tuyến tính.***
- Nếu phương trình có vô số nghiệm thì {$u_1,u_2,..,u_n$} ***phụ thuộc tuyến tính.***
**Ví dụ 1** : Trong không gian $\mathbb{R}^3$ cho các vector vector $u_1=(1,2,3)$, $u_2=(1,-1,4)$, $u_3=(1,3,-2)$. Hỏi $u_1,u_2,u_3$ độc lập hay phụ thuộc tuyến tính.
Xét phương trình :
$$
\alpha_1u_1+\alpha_2u_2+\alpha_3u_3=0
$$
$$
\Leftrightarrow
\begin{cases}
\alpha_1+\alpha_2+\alpha_3=0\\
2\alpha_1-\alpha_2+3\alpha_3=0\\
3\alpha_1+4\alpha_2-2\alpha_3=0\\
\end{cases}
$$
Ma trận hệ số của phương trình trên là :
$$
A =
\begin{bmatrix}
1 & 1 & 1 \\
2 & -1 & 3 \\
3 & 4 & -2 \\
\end{bmatrix}
$$
Ta có : $det(A)=14\neq0$ nên phương trình có nghiệm duy nhất $\alpha_1=\alpha_2=\alpha_3=0$.
$\Rightarrow u_1,u_2,u_3$ độc lập tuyến tính.
**Ví dụ 2** : Trong không gian $\mathbb{R}^3$ cho các vector vector $u_1=(1,1,1)$, $u_2=(2,1,3)$, $u_3=(1,2,0)$. Hỏi $u_1,u_2,u_3$ độc lập hay phụ thuộc tuyến tính.
Có hệ phương trình :
$$
\begin{cases}
\alpha_1+2\alpha_2+\alpha_3=0\\
\alpha_1+\alpha_2+2\alpha_3=0\\
\alpha_1+3\alpha_2+0\alpha_3=0\\
\end{cases}
$$
Ma trận hệ số của phương trình trên là :
$$
B =
\begin{bmatrix}
1 & 2 & 1 \\
1 & 1 & 2 \\
1 & 3 & 0 \\
\end{bmatrix}
$$
Ta có : $det(B)=0$ nên phương trình có vô số nghiệm
$\Rightarrow u_1,u_2,u_3$ phụ thuộc tuyến tính.
### Cơ sở của không gian Vector
- **Định nghĩa tập sinh** : Cho $V$ là không gian Vector và $B\subset V$. Khi này, $B$ được gọi là tập sinh của $V$ nếu mọi vector $u\in V$ đều là tổ hợp tuyến tính của $B$. Ta nói $B$ sinh ra $V$ hoặc $V$ được sinh bởi $B$. Kí hiệu : $V=span(B)$ hoặc $V = \langle B\rangle$
- **Định nghĩa cơ sở** : Cho $V$ là không gian Vector và $B\subset V$. $B$ được gọi là một cơ sở của $V$ nếu thỏa mãn 2 điều kiện sau :
- $B$ là một tập sinh của $V$
- $B$ độc lập tuyến tính
Trong không gian $\mathbb{R}^n$, xét $\mathbb{B}_0=(e_1,e_2,...,e_n)$ với :
\begin{cases}
e_1 = (1,0,...,0)\\
e_2 = (0,1,...,0)\\
\quad \vdots \\
e_n = (0,0,...,1)
\end{cases}
Với $u=(x_1,x_2,...x_n)\in \mathbb{R}^n$ ta có :
$$
u=x_1e_1+x_2e_2+...+x_ne_n
$$
Do đó, $\mathbb{B}_0$ là tập sinh của $\mathbb{R}^n$. Và $\mathbb{B}_0$ cũng độc lập tuyến tính nên $\mathbb{B}_0$ là cơ sở của $\mathbb{R}^n$. Ta gọi $\mathbb{B}_0$ là **cơ sở chính tắc** của $\mathbb{R}^n$. Như vậy số chiều của $\mathbb{R}^n$ là :
$$
dim(\mathbb{R}^n)=n
$$
>Cho $V$ là không gian vector. Số chiều là số vector trong một cơ sở nào đó của không gian vector $V$. Kí hiệu : $dim(V)$
### Tích vô hướng của Vector
Cho $V$ là không gian vector. Ánh xạ :
$$
V \times V \to \mathbb{R}
$$
$$
(u, v) \mapsto \langle u, v \rangle
$$
được gọi là một tích vô hướng trong $V$ nếu $\forall u,v,w \in V$, $\forall \alpha,\beta \in \mathbb{R}$ thỏa mãn bốn tính chất sau:
- $\langle \alpha.u+\beta.v, w \rangle=\alpha \langle u, w \rangle+\beta \langle v, w \rangle$
- $\langle u, \alpha.v+\beta.w \rangle=\alpha \langle u, v \rangle+\beta \langle u, w \rangle$
- $\langle u, v \rangle=\langle v, u \rangle$
- $\langle u, u \rangle \geq0$, trong đó $\langle u, u \rangle =0$ khi $u=0$
Cho $V=\mathbb{R}^n$ là không gian vector, với $u=(x_1,x_2,...x_n)$ và $v=(y_1,y_2,...y_n)$. Ta định nghĩa:
$$
\langle u, v \rangle:=x_1y_1+x_2y_2+...+x_ny_n
$$
Khi đó $V$ là không gian Euclid - là không gian vector hữu hạn chiều với tích vô hướng. Tích vô hướng ở trên được gọi là **tích vô hướng chính tắc** trong $\mathbb{R}^n$.
Chuẩn hay độ dài của vector $u=(u_1,u_2,...,u_n)$, kí hiệu là $\|u\|$ được định nghĩa như sau:
$$
\|u\|:=\sqrt{\langle u, u \rangle}=\sqrt{u_1^2+u_2^2+...+u_n^2}
$$
>$u$ sẽ được gọi là vector đơn vị nếu $\|u\|=1$
Ta có các tính chất sau :
- $\|u\|^2=\langle u, u \rangle$
- $\|u\|=0\Leftrightarrow u=0$
- $\|\lambda u\|=|\lambda|.\|u\|$, $\lambda \in \mathbb{R}$
### Trực giao và trực chuẩn
#### Trực giao
- Cho $V$ là một không gian Euclid. $\forall u,v \in V$, ta nói $u$ **trực giao** với $v$ nếu $\langle u, v \rangle=0$, ký hiệu : $u \perp v$
- Nếu $\emptyset \neq A \subseteq V$ thì ta đặt :
$$
A^\perp:=(u\in V|\langle u, a \rangle=0, \forall a \in A)
$$
Khi đó, $A^\perp$ là một không gian con của $V$ và ta gọi $A^\perp$ là không gian trực giao với A.
#### Cơ sở trực giao và trực chuẩn
Cho $V$ là không gian Euclid $n$ chiều và $B=(u_1,u_2,...,u_n)$ là cơ sở của $V$
- Ta nói $B$ là **cơ sở trực giao** nếu :
$$
\langle u_i, u_j \rangle=0, \forall i \neq j
$$
- Ta nói $B$ là **cơ sở trực chuẩn** nếu $B$ là **cơ sở trực giao** và :
$$
\|u_i\|=1, \forall i=\overline{1,n}
$$
>Ví dụ là các vector đơn vị trong không gian $n$ chiều là cơ sở trực chuẩn.
Hiển nhiên nếu $\{ u_1, \dots, u_n \}$ là cơ sở trực giao thì $\left\{ \frac{u_1}{\| u_1 \|}, \dots, \frac{u_n}{\| u_n \|} \right\}$ là cơ sở trực chuẩn.
>Từ đó ta có định lý : Trong một không gian Euclid bất kì luôn tồn tại các cơ sở trực giao.
#### Thuật toán Gram-Schmidt
**Thuật toán Gram–Schmidt** là một quy trình trong đại số tuyến tính dùng để biến đổi một tập hợp các vectơ độc lập tuyến tính thành một tập hợp các vectơ trực giao (hoặc trực chuẩn) cùng sinh ra không gian con ban đầu. Quá trình này rất hữu ích trong việc đơn giản hóa các tính toán, chẳng hạn như trong giải hệ phương trình hoặc phân tích Fourier.
Cho $(v_1,v_2,...,v_n)$ là các vector độc lập tuyến tính của không gian Euclid $V$ và $W=\langle v_1,v_2,...,v_n \rangle$ là không gian con sinh bởi các vector trên. Đầu tiên ta đặt :
$$
\begin{cases}
u_1:=v_1 \\
u_2:=v_2+\lambda u_1,\text{ với }\lambda \in \mathbb{R} \text{ sao cho } u_1 \perp u_2
\end{cases}
$$
Với điều kiện như này thì ta có :
$$
\langle u_1,u_2\rangle=0
$$
$$
\Leftrightarrow \langle u_1,v_2+\lambda u_1 \rangle=\ \langle u_1, v_2 \rangle+\lambda \langle u_1, u_1 \rangle=0
$$
Do $u_1\neq 0$ nên ta có :
$$
\lambda = -\frac{\langle u_1, v_2 \rangle}{\|u_1\|^2}
$$
Như vậy là ta đã có được $u_2$ dưới dạng :
$$
u_2:=v_2-\frac{\langle u_1, v_2 \rangle}{\|u_1\|^2} u_1
$$
Để tính $u_3$ thì ta sẽ đặt $u_3$ dưới dạng :
$$
u_3 = v_3 + \lambda u_1 + \mu u_2
$$
Cũng với cách tìm $\lambda$ như trên, ta có :
$$
\begin{cases}
\lambda = -\frac{\langle u_1, v_3 \rangle}{\|u_1\|^2} \\
\mu = -\frac{\langle u_2, v_3 \rangle}{\|u_2\|^2}
\end{cases}
$$
Cứ như vậy ta có công thức tổng quát để tìm $u_i$ là :
$$
u_i=v_i - \sum_{j=1}^{i-1} \frac{\langle u_j, v_i \rangle}{\|u_j\|^2} u_j
$$
Công thức này sẽ đảm bảo rằng $u_i$ trực giao với tất cả các $u_1,u_2,...,u_{i-1}$.
Ta sẽ có một cơ sở trực giao là $(u_1,u_2,...,u_n)$, ta có thể chuẩn hóa để thu được cơ sở trực chuẩn $(e_1,e_2,...,e_n)$ với :
$$
e_k = \frac{u_k}{\|u_k\|}
$$
Ví dụ : Trong không gian $\mathbb{R}^2$, cho hai vector $v_1=(1,1)$ và $v_2=(0,1)$. Bây giờ ta sẽ biến đổi chúng thành các vector trực giao, rồi sẽ tìm cơ sở trực chuẩn.
Hiển nhiên ta thấy được vector $v_1, v_2$ độc lập tuyến tính nên khi này ta đặt :
$$
\begin{cases}
u_1=v_1 \\
u_2=v_2-\frac{\langle u_1, v_2 \rangle}{\|u_1\|^2} u_1
\end{cases}
$$
Có :
$$
-\frac{\langle u_1, v_2 \rangle}{\|u_1\|^2} = -\frac{1}{1^2+1^2}=-\frac{1}{2}
$$
Vì vậy ta có :
$$
\begin{cases}
u_1=v_1=(1,1) \\
u_2=v_2-\frac{\langle u_1, v_2 \rangle}{\|u_1\|^2} u_1=(0,1)-\frac{1}{2}(1,1)=(\frac{1}{2},-\frac{1}{2})
\end{cases}
$$
Như vậy ta đã có một cơ sở trực giao mới là $B=(u_1,u_2)$ với $\langle u_1,u_2\rangle=0$.
Cơ sở trực chuẩn thì sẽ là : $B'=[e_1=(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}),e_2=(\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}}))]$
Hình ảnh đầy đủ về **thuật toán Gram-Schmidt**, trích từ cuốn "An Introduction to Mathematical Cryptography", Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman:
# Lattices
Tôi khi mới tìm hiểu về Lattice belike :
>Ưtf ưhats th4t??? :smiley: Ơ mà nhìn vậy thôi chứ kênh này làm về nội dung cũng khá là Creepy đấy :crying_cat_face:
Link tham khảo cực kì uy tín, dễ hiểu : **[Lattices](https://youtu.be/QDdOoYdb748?si=TTa1BU0tbFdikT2G)**
## Định nghĩa và tính chất
**Định nghĩa** : Trong toán học, một lattice $\mathcal{L}$ (mạng tinh thể) là một tập hợp các điểm rời rạc trong trong không gian $n$ chiều, được tạo ra theo tổ hợp tuyến tính của $n$ vector trong một cơ sở $B=(b_1,b_2,...,b_n)$ với hệ số nguyên.
$$
\mathcal{L}=\mathcal{L}(B) = \sum_{i=1}^{n} a_ib_i = a_1b_1+a_2b_2+...+a_nb_n \mid a_i \in \mathbb{Z}
$$
Ví dụ : Trong không gian $\mathbb{R}^2$, cho một cơ sở gồm hai vector $a=(1,2)$ và $b=(3,4)$. Khi này, một Lattice $\mathcal{L}$ gồm các điểm rời rạc sẽ được tạo nên từ tổ hợp tuyến tính với hệ số nguyên của hai vector trên, chẳng hạn :
$$
\begin{cases}
A(-2,-2) = a-b=(1,2)-(3,4)\\
B(2,2) = -a+b=-(1,2)+(3,4)\\
...
\end{cases}
$$
Hình vẽ mô tả : 
Hoặc :
---
**Tính chất** :
- Một không gian Lattice là không độc nhất, tức là có thể tạo ra một Lattice $\mathcal{L}$ từ nhiều vector cơ sở khác nhau. Ví dụ : 
>Ở đây ta có 2 cơ sở $B=(b_1,b_2)$ và $B'=(b_1',b_2')$. Dù mỗi cơ sở có 2 vector khác nhau nhưng chúng vẫn đều tạo ra các điểm xanh như nhau (Lattice $\mathcal{L}$)
Các cơ sở tạo ra cùng một Lattice thì vẫn được xem là một cơ sở của Lattice đó, và người ta chứng minh được là **một Lattice sẽ có vô số cơ sở** tạo nên nó.
Vậy nếu cho trước một Lattice $\mathcal{L}$ và một cơ sở bất kì, làm thế nào để ta biết đó là cơ sở của Lattice đó? Để trả lời câu hỏi trên, ta cần định nghĩa một số đại lượng bất biến mà sẽ không thay đổi dù ta chọn bất kỳ cơ sở nào.
---
- Định nghĩa về **Fundamental Parallelepiped** (tạm dịch là hình hộp cơ sở) : Cho $B=(b_1,b_2,...,b_n)$ là một cơ sở, Fundamental Parallelepiped được định nghĩa là :
$$
\mathcal{P}(B) = \sum_{i=1}^{n} a_ib_i = a_1b_1+a_2b_2+...+a_nb_n \mid a_i \in [0;1)
$$
Công thức trên giống với Lattice, chỉ khác ở chỗ $a_i \in [0;1)$. Điều đó sẽ khiến cho Vector cơ sở thay vì tạo ra các điểm rời rạc thì nó sẽ tạo ra một miền (hình màu xám ở bên dưới)
>Chú ý một điều rằng : Miền ở hình trên là một **miền nửa mở (half-open)**, tức là nó không bao gồm 3 điểm Lattice nằm ở biên
Miền này có thể lấp đầy cả không gian Lattice $\mathcal{L}$ thông qua phép tịnh tiến của các Vector trong cơ sở
Bằng cách kiểm tra xem hình hộp do một cơ sở tạo ra có chứa một điểm khác không thuộc Lattice $\mathcal{L}$ nào khác hay không? Nếu không thì đó sẽ là cơ sở của Lattice và ngược lại. Ta có thể biểu diễn dưới dạng công thức như sau :
$$
\mathcal{P}(\mathbf{B}) \cap \mathcal{L} = \{0\}
$$
>Tức là trên miền của hình hộp cơ sở không có bất kì điểm nào khác của Lattice $\mathcal{L}$, ngoại trừ gốc tọa độ $O$.
---
- Định nghĩa về **Determinant** (tạm dịch là định thức) : Cho $B$ là một cơ sở của Lattice $\mathcal{L}$. Định thức của Lattice $\mathcal{L}$, kí hiệu là $det(\mathcal{L})$, được định nghĩa là thể tích (volume) của hình khối $n$ chiều $\mathcal{P}(B)$ :
$$
\text{det}(\mathcal{L}) = \text{vol}(\mathcal{P}(B)) = |\text{det}(B)|
$$
Hãy xét ví dụ trên không gian $\mathbb{R}^2$ : Cho một cơ sở $B$ gồm 2 vector $u=(0,1)$ và $v=(2,1)$. Khi đó Lattice sẽ được tạo ra dựa trên cơ sở này có hình vẽ như sau :
Định thức của Lattice lúc này sẽ đươc tính bởi :
$$
\det(\mathcal{L}) = \text{vol}(\mathcal{P}(\mathbf{B})) = |\det(\mathbf{B})| =
\begin{vmatrix} \begin{vmatrix} 0 & 2 \\ 1 & 1 \end{vmatrix} \end{vmatrix} = |0.1-1.2|=2
$$
Ta có thể viết :
$$
\begin{vmatrix} 0 & 2 \\ 1 & 1 \end{vmatrix} = \begin{vmatrix} 0 & 1 \\ 2 & 1 \end{vmatrix}
$$
bởi vì ta có tính chất : $det(A) = det(A^T)$
Kết quả $det(\mathcal{L})=2$ có ý nghĩa là diện tích của **hình bình hành ACBD** như hình vẽ trên. Đó là trong không gian 2 chiều, còn trong không gian 3 chiều hoặc $n$ chiều thì nó có nghĩa là thể tích của một hình khối được tạo ra bởi các vector trong cơ sở như trên.
Điều đó cho ta một nhận xét như sau :
- Nếu $det(\mathcal{L})$ nhỏ thì các điểm trong Lattice sẽ nằm gần nhau hơn, nằm “dày” hơn (mật độ cao hơn).
- Nếu $det(\mathcal{L})$ lớn thì đồng nghĩa với việc các điểm nằm “thưa” hơn trong không gian $n$ chiều.
Xét ví dụ về một Lattice $\mathcal{L'}$có mật độ các điểm thưa hơn trong không gian 2 chiều sau đây :
>Lattice $\mathcal{L'}$ có cơ sở $B=[u=(3,4),v=(2,1)]$ và $det(\mathcal{L'})=5$
Có thể nói, **Determinant** là đại lượng bất biến, tức mỗi hình hộp cơ sở do các cơ sở khác nhau của một Lattice tạo ra đều sẽ có chung định thức. Ví dụ như ta xét hình bình hành **ACBD** ở Lattice $\mathcal{L'}$ như trên có $det(\mathcal{L'})=5$. Và ta cũng có thể chọn một cơ sở khác như $B'=(\overrightarrow{CF},\overrightarrow{CE})$. Khi đó diện tích hình bình hành **$CFE_1E$** cũng bằng $5$.
Và nếu như ta chọn một cơ sở khác như $B''=(\overrightarrow{CH},\overrightarrow{CW})$ chẳng hạn, thì nó sẽ không phải là một cơ sở của Lattice $\mathcal{L'}$ vì nó đã vi phạm 2 tính chất :
- Không phải là **Fundamental Parallelepiped** do chứa điểm $R$ trên $CW$
- $|\det(\mathbf{B})| \neq |\det(\mathbf{B''})| = S_{CHVW} = 10$
---
**Một định lý khác của Lattice** : Cho $B$ và $B'$ là hai cơ sở của hai Lattice bất kì. Ta nói hai Lattice đó giống nhau $(\mathcal{L}(\mathbf{B}) = \mathcal{L}(\mathbf{B}'))$ khi và chỉ khi tồn tại một ma trận số nguyên $U$ bất kì có $det(U)=1$ thỏa mãn : $B=UB'$
Từ đó ta sẽ chứng minh được rằng thể tích của các hình hộp cơ bản trong Lattice là bất biến bởi vì :
$$
B=UB' \Rightarrow \det(B)=\det(UB')=\det(U).\det(B')=1.\det(B')=\det(B')
$$
Hay :
$$
\det(B)=\det(B')
$$
Ta sẽ lấy ví dụ ở phần định nghĩa **Determinant** để xét : Lattice $\mathcal{L}$ có một cơ sở $B$ gồm 2 vector $u=(0,1)$ và $v=(2,1)$. Ta lập được một ma trận như sau :
$$
B =
\begin{bmatrix}
0 & 1 \\
2 & 1 \\
\end{bmatrix}
$$
Chọn một ma trận $U$ có $det(U)=1$ là :
$$
U =
\begin{bmatrix}
3 & 1 \\
5 & 2 \\
\end{bmatrix}
$$
Khi này ta có ma trận $B'=U^{-1}.B$ :
$$
B'=
\begin{bmatrix}
3 & 1 \\
5 & 2 \\
\end{bmatrix}^{-1}
\times
\begin{bmatrix}
0 & 1 \\
2 & 1 \\
\end{bmatrix} =
\begin{bmatrix}
-2 & 1 \\
6 & -2 \\
\end{bmatrix}
$$
Và hiển nhiên ta có :
$$
|\det(B')| =
\begin{vmatrix} \begin{vmatrix} -2 & 1 \\ 6 & -2 \end{vmatrix} \end{vmatrix} = |4-6|=2=|\det(B)|
$$
Hình vẽ minh họa :
>$\det(B')=S_{CLZM_1}=2$
---
Ngoài các tính chất trên, ta còn một số đại lượng bất biến quan trọng khác :
- Định nghĩa **(Successive Minima)** : $\lambda_i(\mathcal{L})$ là bán kính Euclid nhỏ nhất sao cho tồn tại ít nhất $i$ vector độc lập tuyến tính trong Lattice $\mathcal{L}$ với tâm hinh cầu tại gốc tọa độ
Với $i = \overline{(1,n)}$ thì ta có $(\lambda_1, \lambda_2,\dots, \lambda_n)$, trong đó Successive Minima đầu tiên, kí hiệu $\lambda_1(\mathcal{L})$, là chiều dài của vector khác không nhỏ nhất trong Lattice. Một Lattice có $n$ chiều thì sẽ có $n$ Successive Minima. Từ đó ta có :
$$
\lambda_1(\mathcal{L}) \leq \lambda_2(\mathcal{L}) \leq \dots \leq \lambda_n(\mathcal{L})
$$
Điều thú vị là không có thuật toán hiệu quả nào để tính toán các Successive Minima của một Lattice. Tuy nhiên, có một định lý được Minkowski đưa ra :
- Định lý **(Minkowski’s First Theorem)** : Cho Lattice $\mathcal{L}$ trong không gian $n$ chiều. Khi đó, Successive Minima đầu tiên $\lambda_1(\mathcal{L})$ phải thỏa mãn điều kiện sau :
$$
\lambda_1(\mathcal{L}) \leq \sqrt{n} \cdot |\text{det}(\mathcal{L})|^{1/n}
$$
Hình ảnh minh họa về $\lambda_1(\mathcal{L})$ :
Successive Minima đầu tiên có ý nghĩa đặc biệt quan trọng vì nó đưa ra một tiêu chuẩn để đánh giá độ dài của các vector trong một Lattice. Có thể nói, đó là một định lý quan trọng khi ta sử dụng LLL vì ta phải Scale ma trận ban đầu sao vector ngắn nhất thỏa mãn định lý trên.
Ta tiếp tục lấy ví dụ ở trên : Lattice $\mathcal{L}$ có một cơ sở $B$ gồm 2 vector $u=(0,1)$ và $v=(2,1)$. Ta lập được một ma trận như sau :
$$
B =
\begin{bmatrix}
0 & 2 \\
1 & 1 \\
\end{bmatrix}
$$
Các giá trị Successive Minima $\lambda_1(\mathcal{L})$, $\lambda_2(\mathcal{L})$ lần lượt là độ dài của các vector ngắn nhất độc lập tuyến tính trong Lattice. Ta có :
$$
\lambda_1(\mathcal{L}) = \lVert (0,1) \rVert = \sqrt{0^2 + 1^2} = 1
$$
$$
\lambda_2(\mathcal{L}) = \lVert (2,2) \rVert = \sqrt{2^2 + 1^2} = \sqrt{5}
$$
Như vậy, Successive Minima của lattice này là:
$$
\begin{cases}
\lambda_1(\mathcal{L}) = 1\\ \lambda_2(\mathcal{L})=\sqrt{5}
\end{cases}
$$
Trong đó, Successive Minima đầu tiên là $\lambda_1(\mathcal{L})$ do :
$$
\lambda_1(\mathcal{L}) \leq \sqrt{n} \cdot |\text{det}(\mathcal{L})|^{1/n}
$$
$$
\Leftrightarrow \lambda_1(\mathcal{L}) = 1 \leq \sqrt{2}.|1|^{1/2} = \sqrt{2}
$$
Trong khi đó :
$$
\lambda_2(\mathcal{L})=\sqrt{5} \geq \sqrt{2}
$$
Nên đó không phải là Successive Minima đầu tiên. Hình vẽ minh họa :
## Lattice Problems
Độ khó của Lattice dựa trên hai bài toán khó là bài toán tìm vector ngắn nhất trong một mạng Lattice **(Shortest Vector Problem (SVP))** và bài toán tìm vector gần một điểm nhất **(Closest Vector Problem (CVP)).**
- **Shortest Vector Problem (SVP)** : Cho Lattice $\mathcal{L}$ có cơ sở là $B$. Yêu cầu khi này là tìm một vector $\mathbf{v}$ sao cho : $||\mathbf{v}|| = \lambda_1(\mathcal{L})$
- **Closest Vector Problem (CVP)** : Cho Lattice $\mathcal{L}$ có cơ sở là $B$ và một vector $t$ bất kỳ (không nhất thiết phải là một điểm trong $\mathcal{L}$). Yêu cầu khi này là tìm một vector $\mathbf{v}$ sao cho : $||\mathbf{v} - \mathbf{t}|| = \text{min}_{\mathbf{w} \in \mathcal{L}}||\mathbf{w} - \mathbf{t}||$
Ngoài ra ta còn có định nghĩa về :
- **Approximate Shortest Vector Problem** ($SVP_{\gamma}$) : Cho Lattice $\mathcal{L}$ có cơ sở là $B$ và hằng số $\gamma$. Yêu cầu khi này là tìm một vector $\mathbf{v}$ sao cho : $\|\mathbf{v}\| \leq \gamma \cdot \lambda_1(\mathcal{L})$
- **Approximate Closest Vector Problem** ($CVP_{\gamma}$) : Cho Lattice $\mathcal{L}$ có cơ sở là $B$ và hằng số $\gamma$. Yêu cầu khi này là tìm một vector $\mathbf{v}$ sao cho : $||\mathbf{v} - \mathbf{t}|| \leq \gamma.\text{min}_{\mathbf{w} \in \mathcal{L}}||\mathbf{w} - \mathbf{t}||$
Để giải quyết các bài toán này, chúng ta sử dụng **giảm mạng (lattice reduction)**. Ý tưởng là chúng ta có thể chuyển đổi một cơ sở mạng bất kỳ thành một cơ sở "tốt hơn", bao gồm các vector ngắn hơn và trực giao hơn. Trong phần tiếp theo, chúng ta mô tả thuật toán LLL, một thuật toán giảm mạng cung cấp lời giải trong thời gian đa thức cho các bài toán này với các hệ số xấp xỉ theo hàm mũ của số chiều mạng.
## Lattice Reduction
Như đã nói, mục tiêu của **giảm cơ sở Lattice (Lattice Reduction)** là lấy một cơ sở bất kỳ của lattice và biến đổi nó thành một cơ sở khác của cùng lattice đó nhưng có các vector ngắn hơn và trực giao hơn. Vì chúng ta tìm kiếm các vector ngắn, nên quá trình này có thể giúp tìm ra nghiệm cho bài toán xấp xỉ vector ngắn nhất.
Ta có thể xem ví dụ ở hình ảnh này :
Có thể thấy, một **cơ sở tốt (good basis)** là một hệ cơ sở gồm các vector ngắn, dễ dàng tính toán. Trong khi đó, một **cơ sở xấu (bad basis)** thì lại có các vector dài, từ đó gây khó khăn cho việc tính toán.
### Gaussian Lattice Reduction
- Thuật toán Gauss hoạt động bằng cách trừ bội số của một vector cơ sở này cho vector cơ sở còn lại cho đến khi không thể làm chúng nhỏ hơn nữa thì dừng, thuật toán này chỉ hoạt động trên không gian hai chiều nên có thể dễ dàng minh họa được.
- Thuật toán :
>Trích từ cuốn "An Introduction to Mathematical Cryptography", Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman:
Code mẫu :
```python=
from sage.all import *
def Gaussian_Lattices_Reduction(v1, v2):
while True:
if v2.norm() < v1.norm():
v1, v2 = v2, v1
m = round((v1*v2) // (v1*v1))
if m == 0:
return v1, v2
v2 -= m*v1
v1 = vector([5,7])
v2 = vector([9,8])
a, b = Gaussian_Lattices_Reduction(v1, v2)
print((a, b))
# ((4, 1), (1, 6))
```
Hình minh họa trước khi giảm cơ sở :
Sau khi dùng thuật toán Gauss thì ta có cơ sở mới :
### LLL Algorithm
**[LLL](https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm)** là tên viết tắt của ba nhà toán học **Arjen Lenstra, Hendrik Lenstra và László Lovász**. Thuật toán **LLL** hoạt động bằng cách thực hiện trực giao hóa liên tục các vector cơ sở bằng Gram-Schmidt và đồng thời kiểm tra hai điều kiện là :
- Điều kiện Lovász
- Điều kiện giảm số hạng
Nếu hai điều kiện thỏa mãn thì thuật toán kết thúc. Thuật toán này sẽ giúp ta tính xấp xỉ vector ngắn nhất trong Lattice, hay nó sẽ giúp ta giải bài toán SVP một cách tương đối.
Đầu tiên, cho cơ sở $B=\left\{b_1,b_2,...,b_n\right\}$. Ta sẽ dùng **thuật toán Gram-Schmidt** để trực giao hóa cơ sở này thành cơ sở trực giao $B^*=\left\{b_1^*,b_2^*,...,b_n^*\right\}$, với công thức như sau :
$$
\begin{cases}
b_1^* = b_1 \\
b_i^* = b_i - \sum_{j=1}^{i-1} \frac{\langle b^*_j, b_i \rangle}{\|b^*_j\|^2} b^*_j
\end{cases}
$$
>Có thể đặt $\
\mu_{i,j} = \frac{\langle \mathbf{b}_i, \mathbf{b}_j^* \rangle}{\langle \mathbf{b}_j^*, \mathbf{b}_j^* \rangle}$
Với điều này, chúng ta có khái niệm về một cơ sở giảm **LLL**, đó là mục tiêu cuối cùng của chúng ta.
Cho $\delta \in (\frac{1}{4}, 1)$. Một cơ sở $B=\left\{b_1,b_2,...,b_n\right\}$ sẽ giảm mạng thành công nếu thoả mãn hai điều kiện sau:
- **Điều kiện Lovász** : $(\delta - \mu_{i+1, i}^2) \times \|\mathbf{b}_i^*\|^2 \leq \|\mathbf{b}_{i+1}^*\|^2 \quad \forall 1 \leq i \leq n - 1$
- **Điều kiện giảm số hạng** : $\|\mu_{i, j}\| \leq \frac{1}{2} \quad \forall i > j$
Như vậy ta có thuật toán LLL như sau :
```pseudo
function LLL(Basis {b₁, ..., bₙ}, δ)
while true do
for i = 2 to n do
for j = i - 1 to 1 do
b*_i, μᵢⱼ ← Gram-Schmidt(b₁, ..., bₙ) ⟶ size-reduction
bᵢ ← bᵢ - ⌊μᵢⱼ⌉ bⱼ
if ∃i such that (δ - μ²_{i+1,i})‖b*_i‖² > ‖b*_{i+1}‖² then ⟶ Lovász condition
Swap bᵢ and bᵢ₊₁
else
return {b₁, ..., bₙ}
```
Ví dụ : Cho Lattice $\mathcal{L}$ có cơ sở $B=\left\{b_1=(-2,2),b_2=(-2,1)\right\}$. Chọn $\delta = 0.75$, ta sẽ dùng thuật toán lên cơ sở này.
Đầu tiên ta đặt :
$$
\begin{cases}
b_1^* = b_1 = (-2,2)\\
b_2^* = b_2 - \frac{\langle b^*_1, b_2 \rangle}{\|b^*_1\|^2} b^*_1 = (-2,1) - 0.75\times (-2,2)=(-0,5,-0,5)
\end{cases}
$$
Tiếp theo, ta tính $b_2 = b_2 - \left \lfloor\mu_{2,1}\right \rceil \times b_1 = (-2,1) - \left \lfloor0.75\right \rceil.(-2,2) =(0, -1)$
Bây giờ ta có :
$$
\begin{cases}
b_1^* = (-2,2)\\
b_2^* = (-0.5,-0.5)
\end{cases}
\text{ và }
\begin{cases}
b_1 = (-2,2)\\
b_2 = (0,-1)
\end{cases}
$$
Tuy nhiên, $b_1^*,b_2^*$ không thỏa mãn vì :
$$
(\delta - \mu_{2, 1}^2) \times \|b_1^*\|^2 = [0.75 - (0.75)^2] \cdot 8 = 1.5 \nleqslant \|b_{2}^*\|^2 = 0.5
$$
Vì vậy khi này ta sẽ hoán đổi $b_1,b_2$ lại, tức là :
$$
\begin{cases}
b_1 = (0,-1)\\
b_2 = (-2,2)
\end{cases}
$$
Lặp lại các bước tính toán trên :
$$
\begin{cases}
b_1^* = b_1 = (0,-1)\\
b_2^* = b_2 - \frac{\langle b^*_1, b_2 \rangle}{\|b^*_1\|^2} b^*_1 = (-2,2) - (-2)\times (0,-1)=(-2,0)
\end{cases}
$$
$$
\Leftrightarrow (\delta - \mu_{2, 1}^2) \times \|\mathbf{b}_1^*\|^2 = (0.75 - (-2)^2) \cdot 1 = -3.25 \leq \|\mathbf{b}_{2}^*\|^2 = 4
$$
Vậy là xong. Ta có cơ sở mới $B' = \left\{b_1^*=(0,-1), b_2^*=(-2,0) \right\}$
Ta có thể tính LLL ngay trong SageMath :
```python=
from sage.all import *
a = vector([-2,1])
b = vector([-2,2])
M = matrix([a,b])
print(M.LLL())
# [ 0 1] Vector có độ dài ngắn nhất
# [-2 0]
```
Chúng ta lưu ý rằng trong ví dụ đơn giản này, một vector ngắn nhất trong Lattice được tìm thấy trong vector đầu tiên của cơ sở đã được giảm!
Tất nhiên, LLL không phải lúc nào cũng tìm được vector ngắn nhất. Nhưng chúng ta có thể chứng minh rằng nó sẽ luôn tìm được một vector trong một khoảng xấp xỉ theo hệ số mũ của số chiều của Lattice so với vector ngắn nhất. Để làm điều đó, trước tiên chúng ta sẽ nói đến một định lý về cận dưới của vector ngắn nhất trong một Lattice.
---
**Định lý :** Cho $B = \left\{b_1,b_2,...,b_n \right\}$ là một cơ sở vector và $B^* = \left\{b^*_1,b_2^*,...,b^*_n \right\}$ là cơ sơ trực giao theo **thuật toán Gram-Schmidt**. Khi này ta có :
$$
\lambda_1(\mathcal{L}(\mathbf{B})) \geq \text{min}_{i \in \left\{1,\dots,n \right\}}\|\mathbf{b}_i^*\|
$$
Từ đó ta có **các tính chất** : Cho $B = \left\{b_1,b_2,..., b_n \right\}$ là cơ sở mới sau khi giảm mạng thì:
$$
\|b_1\| \leq \left( \frac{2}{\sqrt{4\delta -1}} \right)^{n-1} .\lambda_1
$$
$$
\Leftrightarrow \|b_1\| \leq \left (\frac{2}{\sqrt{4\delta-1}}\right )^{n-1} \times \sqrt{n} \times |\text{det}(\mathcal{L})|^{1/n}
$$
Kết quả này sẽ quan trọng đối với chúng ta vì nó cung cấp một ý tưởng sơ bộ về các vector ngắn mà thuật toán LLL sẽ tìm thấy. Nếu chúng ta có thể mô hình hóa một bài toán cụ thể trong đó nghiệm tồn tại dưới dạng một vector ngắn của một số mạng, chúng ta có thể giải nó bằng cách sử dụng phương pháp giảm mạng nếu vector ngắn nằm trong một hệ số xấp xỉ theo hàm mũ của vector ngắn nhất. Chúng ta sẽ bỏ qua phần phân tích và chứng minh, đồng thời mặc định rằng thuật toán LLL chạy trong thời gian đa thức theo kích thước của mạng.
### An Application of Lattice Reduction
Trước khi thảo luận về ứng dụng của Lattice Reduction trong phân tích mật mã, chúng ta sẽ xem xét một ứng dụng của giảm lattice trong đại số. Vấn đề chúng ta xem xét ở đây là việc tái dựng đa thức tối thiểu có nghiệm là một xấp xỉ của một số. Vấn đề này đã được chứng minh là có thể giải được bằng Lattice Reduction.
---
Trước hết, ta hãy xem lại cách mà LLL hoạt động theo cách hiểu của mình :
- Một cơ sở $B$ khi áp dụng LLL thì sẽ cho ra một cơ sở mới có các vector ngắn hơn cơ sở ban đầu
- Trong các vector của cơ sở mới đó thì sẽ có **một vector có độ dài ngắn nhất**. LLL sẽ có nhiệm vụ là tìm ra nó bằng cách tìm một ma trận $a$ sao cho khi nhân nó với ma trận cơ sở $B$ thì sẽ thu được vector ngắn nhất.
- Nếu $B$ là một cơ sở chứa các vector độc lập tuyến tính trong không gian $n$ chiều thì khi này ma trận cơ sở $B$ sẽ có cấp là $n\times n$. Biểu diễn dưới dạng phương trình sau :
$$
a_{1\times n}.B_{n\times n}=x_{1\times n}
$$
- $x$ là vector ngắn nhất thuộc Lattice ban đầu
- LLL sẽ không có lưu lại giá trị của $a$ mà chỉ in ra giá trị của $x$ nên ta sẽ tìm hiểu về cách tìm ra được $a$.
- Ví du : Cho một ma trận cấp $2\times 2$ được tạo từ hai vector cơ sở là $B = \left\{(A,B),(C,D)\right\}$ có dạng là :
$$
M =
\begin{bmatrix}
A & B \\
C & D \\
\end{bmatrix}
$$
- Khi ta áp dụng LLL với ma trận trên, thì thuật toán LLL sẽ đi tìm một ma trận $a$ cấp $1\times 2$ sao cho kết quả của phép nhân hai ma trận mới này là một vector mới có kích thước nhỏ. Ta giả sử ma trận $a$ là : $a=[x,y]$. Khi này ta có :
$$
[x, y]
\times
\begin{bmatrix}
A & B \\
C & D \\
\end{bmatrix}
=
[xA + yC,\hspace{3mm} xB + yD]
$$
Khi này ma trận $[xA + yC,\hspace{3mm} xB + yD]$ sẽ là một trong các vector của cơ sở mới, tùy vào $[x,y]$ thay đổi thì sẽ có các vector khác nhau. Nhưng ta vẫn chưa hề biết $[x,y]$ sẽ có giá trị như nào, phải làm sao để biết được $[x,y]$ đây?
Đơn giản là ta chỉ cần ghép ma trận cơ sở $B$ ban đầu với ma trận đơn vị cấp tương ứng là được. Ví dụ ta sẽ lấy ma trận cơ sở $B$ ở trên ghép với ma trận đơn vị thì khi này ta có :
$$
B =
\begin{bmatrix}
A & B & 1 & 0\\
C & D & 0 & 1\\
\end{bmatrix}
$$
Lúc này khi nhân ma trận $a=[x,y]$ vào thì ta được :
$$
[x, y] \times
\begin{bmatrix}
A & B & 1 & 0\\
C & D & 0 & 1\\
\end{bmatrix} =
[xA + yC, \hspace{3mm} xB + yD,\hspace{3mm} x,\hspace{3mm} y]
$$
Như vậy, hai số cuối của ma trận kết quả chính là ma trận mà LLL đã dùng để tìm ra vector ngắn trong cơ sở mới.
Ví dụ trong SageMath :
```python=
from sage.all import *
M = Matrix(ZZ, [[-2,2],[-2,1]])
print(M.LLL())
# [ 0 -1]
# [-2 0]
print(M.solve_left(M.LLL()[0]))
# [-1 1]
print(M.solve_left(M.LLL()[1]))
# [-1 2]
```
Như vậy ta có :
$$
[-1, 1] \times
\begin{bmatrix}
-2 & 2 \\
-2 & 1 \\
\end{bmatrix}=
[0, -1]
$$
$$
[-1, 2] \times
\begin{bmatrix}
-2 & 2 \\
-2 & 1 \\
\end{bmatrix}=
[-2, 0]
$$
Để biết trực tiếp ma trận $a=[x,y]$ luôn thì ta sẽ ghép ma trận đơn vị vào :
```python=
from sage.all import *
M = Matrix(ZZ, [[-2,2,1,0],[-2,1,0,1]])
print(M.LLL())
# [ 0 -1 -1 1]
# [-2 1 0 1]
'''
Nếu để ý thì vector hàng 2 của ma trận mới này nó khác với ma trận ban đầu.
Điều này chả sao vì cái ta cần để ý đến là vector ngắn nhất hàng trên.
'''
```
---
Định nghĩa **Minimal Polynomial** (tạm dịch là đa thức tối thiểu): Cho $\alpha \in F$ với $F$ là một trường. Một đa thức tối thiểu của $\alpha$ là một đa thức monic có bậc thấp nhất trong $F[x]$ sao cho $\alpha$ là nghiệm của đa thức đó.
Lấy ví dụ ta sẽ dùng LLL để tìm một đa thúc $f(x)$ sao cho $\alpha = 8+\sqrt{19}$ là một nghiệm của đa thức đó.
- Ta có : $\alpha = 8+\sqrt{19} \approx 12.35889894$. Đặt $\beta = 12.35889894$. Hãy giả sử rằng $f(x)$ có bậc là hai (do nghiệm có dạng $a+\sqrt{b}$), ta có $f(x)$ là :
$$
f(x)=a_2x^2 + a_1x + a_0 \text{ , }a_i\in \mathbb{R}
$$
- $f(\alpha)=0\Rightarrow f(\beta)\approx 0 \Leftrightarrow \beta^2.a_2 + \beta.a_1 + a_0\approx0$
- Ta thấy rằng $\beta$ có 8 số thập phân sau dấu phẩy nên ta sẽ nhân đẳng thức trên với $10^8$ để biến các hệ số thành số nguyên :
$$
\left \lfloor10^8\beta^2\right \rfloor a_2 + \left \lfloor10^8\beta\right \rfloor a_1 + 10^8a_0 \approx 0
$$
- Lúc này ta sẽ phải tìm các hệ số $a_0,a_1,a_2$ để hoàn thành đa thức. Vì đây là đa thức monic nên hệ số $a_2=1$.
- Ta lập một ma trận như sau :
$$
B =
\begin{bmatrix}
10^8 & 1 & 0 & 0\\
\left \lfloor10^8\beta\right \rfloor & 0 & 1 & 0\\
\left \lfloor10^8\beta^2\right \rfloor & 0 & 0 & 1\\
\end{bmatrix}
=
\begin{bmatrix}
100000000 & 1 & 0 & 0 \\
1235889894 & 0 & 1 & 0\\
15274238309 & 0 & 0 & 0\\
\end{bmatrix}
$$
- Khi này khi áp dụng LLL thì ta sẽ thu được một vector **ngắn nhất** có dạng :
$$
[10^8a_0 + \left \lfloor10^8\beta\right \rfloor a_1 + \left \lfloor10^8\beta^2\right \rfloor a_2, \hspace{3mm} a_0, \hspace{3mm} a_1, \hspace{3mm} a_2,] = [\approx0, a_0, a_1, a_2]
$$
Áp dụng LLL cho ma trận này ta có :
```python=
from sage.all import *
B = matrix([
[100000000, 1, 0, 0],
[1235889894, 0, 1, 0],
[15274238309, 0, 0, 1],
])
print(B.LLL())
# [ 5 45 -16 1]
# [-11832 -2867 -11682 964]
# [ 11386 -6256 -13929 1168]
```
Ta có thể thấy rằng : Hàng đầu tiên chính là vector ngắn nhất của ta nên khi này có phương trình $f(x)$ là :
$$
f(x) = x^2 - 16x + 45
$$
Và vừa hay thì phương trình này có nghiệm chính là $\alpha = 8+\sqrt{19} \approx 12.35889894$, hay $f(\alpha)=0$.
Có một điều cần lưu ý là : LLL chỉ quan tâm đến độ lớn của các Vector nên nó sẽ không quan tâm dấu của các hệ số, vì thế nó hoàn toàn có thể trả về vector đã bị nhân cho $-1$. Ta sẽ phải thử đổi dấu nếu các hệ số không thỏa mãn phương trình.
## Lattice-based Problems
Trong phần này, chúng ta nghiên cứu một số bài toán có thể được giải bằng cách mô hình hóa tình huống dưới dạng một bài toán SVP hoặc CVP. Những bài toán này có thể được đặc trưng bởi tính chất tuyến tính của chúng, và chúng ta sẽ gọi những bài toán này là **bài toán dựa trên lưới (Lattice-based Problems)**.
### Finding Small Roots
Chúng ta bắt đầu với một trong những bài toán có ảnh hưởng nhất và được ứng dụng rộng rãi nhất trong phân tích mật mã khóa công khai: **bài toán tìm nghiệm "nhỏ" của một đa thức theo Modulo của một số nguyên**. Bài toán này được nghiên cứu trong một công trình quan trọng của Coppersmith, trong đó ông cũng áp dụng kỹ thuật của mình để phá mã RSA có số mũ thấp trong một số trường hợp đặc biệt.
Sức mạnh của phương pháp Coppersmith nằm ở khả năng tìm nghiệm nhỏ của phương trình đa thức theo Modulo của một hợp số, mà không cần biết phân tích thừa số của nó. Việc tìm nghiệm theo Modulo của một số nguyên tố thì dễ, trong khi đó tìm nghiệm theo Modulo của một hợp số $N$ lại khó tương đương với việc phân tích thừa số của $N$. Do đó phương pháp tìm nghiệm nhỏ của Coppersmith được coi là phương pháp hiệu quả và đem lại vô số ứng dụng trong phân tích mật mã.
---
Cho $N$ là hợp số và một đa thức $f(x)$ có dạng :
$$
f(x) = x^d + \displaystyle\sum_{i=0}^{d-1} a_ix^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$ thỏa mãn phương trình : $f(x_0) \equiv 0 \pmod N$ với $|x_0| < B$, với một số nguyên $B$ có giới hạn 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 :
- Ta có một tính chất nếu $f(x_0) \equiv 0 \pmod N$ thì khi ta cộng $f(x)$ cho các đa thức $g(x)$ có dạng : $g_i(x) = Nx^i \hspace{3mm}\forall i \in [0, d)$ thì đa thức $f(x)$ của ta vẫn giữ nguyên nghiệm $x_0$ ban đầu.
- Ý nghĩa của việc làm này là ta sẽ làm giảm đi các hệ số của đa thức $f(x)$, khi mà trong một vài trường hợp đa thức monic $f(x)$ có nghiệm nhỏ nhưng mà hệ số đa thức lại quá lớn. Áp dụng lý thuyết trên thì ta sẽ thu được một đa thức mới có hệ số nhỏ, từ đó ta có thể dùng các phương pháp tìm nghiệm của đa thức trên tập $\mathbb{Z}$ để tìm ra $x_0$.
Chính vì điều đó, ta có thể lập được một cơ sở Lattice tạo nên từ $f(x)$ và $g_i(x)$ như sau :
$$
A =
\begin{bmatrix}
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{bmatrix}
$$
Tại sao ta có được ma trận như vậy?
- Ta biết rằng : $g_i(x)\equiv 0\pmod{N}$. Do đó, nếu $x_0$ là nghiệm của $f(x)$ theo Modulo $N$ thì với bất kì hệ số nguyên $c_i$ nào ta cũng có :
$$
f(x_0) + \sum_{i=0}^{d}c_i.N(x_0)^i\equiv0 \pmod{N}
$$
- Nói cách khác, điều đó tương đương với việc cộng hoặc trừ các đa thức $g_i(x)$ vào đa thức $f(x)$ sẽ tạo ra một đa thức mới vẫn có nghiệm là $x_0$
- Khi này thay $x=Bx$ ta sẽ có :
$$
g_i(Bx)=N.(Bx)^i=NB^ix^i
$$
$$
f(Bx)= (Bx)^d+a_{d-1}(Bx)^{d-1}+...+a_1Bx+a_0
$$
- Mỗi đa thức khi được biểu diễn theo cơ sở $(x^0,x^1,...,x^d)$ sẽ cho ta một vector hệ số.
- Tập hợp tất cả các vector hệ số của $g_i(Bx)$ và $f(Bx)$ sẽ sinh ra một Lattice $\mathcal{L}(A)$
- Bất kỳ tổ hợp tuyến tính nào của các hàng trong ma trận này cũng biểu diễn một đa thức có nghiệm trùng với nghiệm của $f(x)$ trong Modulo $N$.
Phân tích cấu trúc ma trận $A$ :
$$
A =
\begin{bmatrix}
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{bmatrix}
$$
- $d$ hàng đầu tiên :
- Mỗi hàng tương ứng với đa thức $g_i(Bx)=NB^ix^i$.
- Ví dụ:
- Hàng 1 (trên cùng) chứa hệ số $N$ ở cột $x^0$, vì đó là $NB^0x^0$.
- Hàng 2 chứa hệ số $BN$ ở cột $x^1$, vì đó là $NB^1x^1$.
- ...
- Hàng $i$ chứa $B^{i-1}N$ ở cột $x^{i-1}$.
- Hàng cuối cùng (hàng $d+1$)
- Tương ứng với đa thức : $f(Bx) = (Bx)^d + a_{d-1} (Bx)^{d-1} + \dots + a_1 (Bx) + a_0$
- Khi "trải" ra theo cơ sở $(x^0,x^1,...,x^d)$, hệ số trước $x^0$ là $a_0$, trước $x^1$ là $a_1B$,..., và trước $x^d$ là $B^d$.
Như vậy là ta đã có được một ma trận $A$ chứa các vector cơ sở cấp $d+1$
Khi áp dụng LLL vào ma trận cơ sở trên thì kết quả cuối cùng sẽ một vector chứa các hệ số của một đa thức $h(x)$ nào đó có nghiệm $x_0$ thỏa $h(x_0)=0$. Ta giả sử vector có dạng $b=(b_0,b_1,...,b_d)$. Khi này, đa thức $h(x)$ có dạng :
$$
h(x)=b_0 + \frac{b_1}{B}x + \frac{b_2}{B^2}x^2 + … + \frac{b_{d-1}}{B^{d-1}}x^{d-1} + \frac{b_{d}}{B^{d}}x^d
$$
>Khi này, $h(x)$ sẽ có nghiệm là $x_0$
Lấy ví dụ : Cho $N=23.29=667$ và $f(x)=x^2+6x+352 \in Z[x]$. Biết rằng $f(x)$ có một **nghiệm nhỏ** là $x_0<20 \mod(N)$ và $f(x_0)\neq0$. Chúng ta sẽ sử dụng phương pháp của Coppersmith như mô tả ở trên để tìm **nghiệm nhỏ** này. Chọn $B=20$ và xây dựng lattice được tạo ra bởi $A$ :
$$
A =
\begin{bmatrix}
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{bmatrix} =
\begin{bmatrix}
N &0 &0\\
0 &B.N & 0 \\
352 &6.B & B^2
\end{bmatrix} \\
$$
Sử dụng LLL ta có :
```python=
from sage.all import *
N = 667
B = 20
M = matrix([
[N , 0 , 0 ],
[0 , B*N, 0 ],
[352, 6*B, B^2 ],
])
print(M.LLL())
# [ -315 120 400]
# [ 352 120 400]
# [ 167 12260 -3600]
```
Hàng ở trên chính là hệ số của đa thức $h(Bx)$ là :
$$
h(Bx)=400x^2+120x-315
$$
Và để có được $h(x)$ thì ta chỉ cần :
$$
h(x)=\frac{400x^2}{20^2}+\frac{120x}{20}-315=x^2+6x-315
$$
Giải phương trình bậc hai trên là ta sẽ có được $x_0$
```python=
from sage.all import *
P.<x> = PolynomialRing(ZZ)
h = x^2 + 6*x - 315
print(h.roots())
# [(15, 1), (-21, 1)]
```
Ta có 2 nghiệm là $x_1=15$ và $x_2=-21$. Ta sẽ chỉ lấy nghiệm $x_1=15$ do $x_2$ không thỏa mãn điều kiện $|x_0|<B$
Nếu bạn tò mò đa thức $f(x)$ đã được biến đổi thành $h(x)$ như thế nào thì ta chỉ cần biến đổi ma trận $A$ ghép thêm ma trận đơn vị cấp $3\times 3$ là được :
```python=
from sage.all import *
N = 667
B = 20
M = matrix([
[N , 0 , 0 , 1, 0, 0 ],
[0 , B*N, 0 , 0, 1, 0 ],
[352, 6*B, B^2, 0, 0, 1 ],
])
print(M.LLL())
# [ -315 120 400 -1 0 1]
# [ 352 120 400 0 0 1]
# [ 167 12260 -3600 5 1 -9]
```
>Nhìn vào vector đầu tiên ta thấy : $h(x)=f(x)-N$
---
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.
- **Coppersmith’s Method** : Cho $N$ là một số nguyên chưa biết phân tích thừa số nguyên tố và $N$ có ước số $b\geq B^{\beta}$. Cho $f(x)$ là một đa thức monic đơn biến có bậc là $\delta$ và $0<\epsilon\leq\frac{1}{7}\beta$. Khi đó ta có thể tìm mọi nghiệm $x_0$ của $f(x) \equiv 0 \pmod 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})$
- Có một số cách để xác định $\beta$ như sau :
- Nếu biết được $b$ thì ta có : $\beta = \log_N(b)$
- Nếu chưa biết $b$ mà biết được `bitsize` của $b$ thì $\beta=\frac{bitsize(b) - 1}{bitsize(N)}$
- Nếu $N=pq$ và $bitsize(p) = bitsize(q)$ thì $\beta \approx0.499$
### Knapsack Problem
**Bài toán ba lô (Knapsack Problem)** là một bài toán với độ phức tạp **NP-complete** và đã được sử dụng trong quá khứ như một hàm trapdoor trong một vài hệ mã khóa công khai như **Merkle–Hellman**. Phiên bản phổ biến của nó trong mật mã học là bài toán **subset sum** hay tìm một tập con của một tập các số cho trước sao cho tổng của tập con đó bằng một giá trị $S$ cho trước.
#### Low-density Subset Sum Problems
**Định nghĩa** : Cho các số nguyên dương $a_1,a_2,...,a_n$ và một số nguyên dương $s$. Tìm một tập hợp $a_i$ mà tổng của chúng bằng $s$. Tức là tìm các hệ số $e_1,e_2,...,e_n$ với $e_i\in\left\{0,1\right\}$ sao cho :
$$
\sum_{i=1}^{n} e_ia_i \ = s
$$
Ví dụ : Cho $a=\left\{1,11,15,28,56,112\right\}$ và một giá trị $s=85$. Khi này ta sẽ có một tập $e=\left\{1,0,0,1,1,0\right\}$ vì $1+28+56=85$
Rất nhiều hệ mã dựa trên bài toán Subset Sum Problem được chỉ ra là không an toàn vì tồn tại một số thuật toán có thể giải trường hợp đặc biệt là "low-density" của bài toán tổng tập con. **"The density"** hay mật độ của tập $a_1,a_2,...,a_n$ được xác định bởi :
$$
d = \frac{n}{\log_2\text{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 của ta là xây dụng một Lattice sao cho nó chứa một vector ngắn có $e_i$ ở trong. Một Lattice như thế sẽ được tạo nên từ một cơ sở như sau:
$$
B=
\begin{bmatrix}
1 & & & &a_1 \\
&1 & & &a_2 \\
& &\ddots & &\vdots\\
& & &1 &a_n \\
& & & &s
\end{bmatrix}
$$
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) dạng $x_1 = (e_1, …, e_n, 0)$, hay có nó có nghĩa là $tB=x_1$. Vì vậy chúng ta có thể mong đợi Lattice Reduction sẽ giúp chúng ta tìm thấy vector này. Thuật toán **CJLOSS** có thay đổi cơ sở $B$ của ta một xíu bằng cách nhân thêm một số nguyên $N>\sqrt{n}$ và thêm vào hàng cuối số $\frac{1}{2}$ như sau :
$$
B'=
\begin{bmatrix}
1 & & & &Na_1 \\
&1 & & &Na_2 \\
& &\ddots & &\vdots\\
& & &1 &Na_n \\
\frac{1}{2} &\frac{1}{2} &\cdots &\frac{1}{2} &Ns
\end{bmatrix}
$$
Trong trường hợp này tổ hợp tuyến tính $t = (e_1, …, e_n, -1)$ tạo ra một vector $x_2 = (e_1 - \frac{1}{2}, e_2-\frac{1}{2}, \dots,e_n -\frac{1}{2}, 0)$ và ta luôn có $\|x_2\| = \frac{1}{2}\sqrt{n}$. Xác suất để $x_2$ không phải là vector ngắn nhất là:
$$
P \leq n(4n\sqrt{n}+1)\frac{2^{c_0 \cdot n}}{\text{max}(a_i)}
$$
Khi $c_0 \approx 1.0628$ thì giới hạn trên tiến về $0$ hay $max(a_i) > 2^{c_0.n}$ và ta có :
$$
max(a_i)>2^{c_0.n}
$$
$$
\Leftrightarrow log_2[max(a_i)]>c_0.n
$$
$$
\Leftrightarrow \frac{1}{c_0} > \frac{n}{log_2[max(a_i)]}
$$
$$
\Leftrightarrow \frac{1}{c_0} > d
$$
$$
\Leftrightarrow d < 0.9408
$$
**Ví dụ** : Cho tập $a=(a_1,...,a_6) = (83,59,47,81,76,51), n=6$ và $s=291$. Mật độ của tập $a$ này là :
$$
d=\frac{n}{log_2[max(a_i)]} = \frac{6}{log_2(83)} \approx 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 **Subset sum** này.
Chọn $N=3$ ta sẽ xây dựng một Lattice $B$ như sau :
$$
B=
\begin{bmatrix} 1 & & & &Na_1 \\
&1 & & &Na_2 \\
& &\ddots & &\vdots\\
& & &1 &Na_n \\
\frac{1}{2} &\frac{1}{2} &\cdots &\frac{1}{2} &Ns
\end{bmatrix} =
\begin{bmatrix}
1 &0 &0 &0 &0 &0 &3\times83\\
0 &1 &0 &0 &0 &0 &3\times59\\
0 &0 &1 &0 &0 &0 &3\times47\\
0 &0 &0 &1 &0 &0 &3\times81\\
0 &0 &0 &0 &1 &0 &3\times76\\
0 &0 &0 &0 &0 &1 &3\times51\\
\frac{1}{2} &\frac{1}{2} &\frac{1}{2} &\frac{1}{2} &\frac{1}{2} &\frac{1}{2} &3\times291
\end{bmatrix}
$$
Áp dụng LLL với ma trận $B$ trên ta thu được ma trận $B'$ có dạng :
$$
B'=\frac{1}{2}
\begin{bmatrix}
-1 & 1 & 1 & -1 & -1 & -1 & 0 \\
1 & 1 & 1 & -1 & -1 & 3 & 0 \\
2 & -2 & 2 & 2 & -4 & 0 & 0 \\
1 & 3 & -3 & 3 & -3 & 1 & 0 \\
2 & -2 & -2 & -4 & 0 & 0 & 0 \\
-3 & -1 & -3 & -1 & -1 & 1 & 0 \\
0 & -2 & 0 & 0 & -2 & -2 & -6
\end{bmatrix}
$$
Hàng đầu tiên của ta là một vector ngắn có dạng : $b=(-\frac{1}{2}, \frac{1}{2},\frac{1}{2},-\frac{1}{2},-\frac{1}{2},-\frac{1}{2}, 0)$. Nó chính là vector $x=(e_1-\frac{1}{2},...,e_6-\frac{1}{2}, 0)$, hoặc nó có thể là vector $-x$. Và giờ ta có thể khôi phục lại $e_i$ với $$
e=(b_1+\frac{1}{2},...,b_6+\frac{1}{2}), \text{ nếu là x}
$$
Hoặc :
$$
e=(-b_1+\frac{1}{2},...,-b_6+\frac{1}{2}), \text{ nếu là -x}
$$
Như vậy ta thu được :
$$
(e_1,e_2,e_3,e_4,e_5,e_6) = (1,0,0,1,1,1)
$$
Hay : $83+81+76+51=291$
Code :
```python=
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()
#source từ a no.more.caffeine
```
#### Low-density Subset Sum Problems: Extensions and Generalisations
Ở phần trước ta chỉ nghiên cứu đơn thuần về **Subnet Sum Problem** với một giá trị $s$ cho trước. Còn bây giờ, ta sẽ mở rộng chúng ra thành :
- **Multiple Subset Sum Problem** : nhiều tập $a$, nhiều giá trị $s$
- **Modular Subset Sum Problem** : một giá trị $s$ nhưng thêm Modulo $M$
- **Multiple Modular Subset Sum Problem** : Kết hợp của hai cái trên
Ta sẽ định nghĩa chúng như sau :
---
Định nghĩa **Multiple Subset Sum Problem** : Cho các số nguyên dương $a_{1,1},a_{1,2},...,a_{k,n}$ và các số nguyên $s_1,s_2,...,s_k$. Hãy tìm các số $e_1, e_2,...,e_n$ với $e_i\in\left\{0,1\right\}$ sao cho :
$$
\sum_{i=1}^{n} e_i.a_{j, i}=s_j, \hspace{3mm}\forall 1 \leq j \leq k
$$
Định nghĩa **Modular Subset Sum Problem** : Cho các số nguyên dương $a_1,...,a_n$ và hai số nguyên $s$ và $M$. Hãy tìm các số $e_1, e_2,...,e_n$ với $e_i\in\left\{0,1\right\}$ sao cho :
$$
\sum_{i=1}^{n} e_i.a_{i}\equiv s \pmod M
$$
Định nghĩa **Multiple Modular Subset Sum Problem** : Cho các số nguyên dương $a_{1,1},a_{1,2},...,a_{k,n}$, các số nguyên $s_1,s_2,...,s_k$, và một số nguyên $M$. Hãy tìm các số $e_1, e_2,...,e_n$ với $e_i\in\left\{0,1\right\}$ sao cho :
$$
\sum_{i=1}^{n} e_i.a_{j, i}\equiv s_j \pmod M ,\hspace{3mm} \forall 1 \leq j \leq k
$$
Mật độ của **Multiple Subset Sum Problem** được định nghĩa qua công thức :
$$
d = \frac{n}{k.\log_2[{max}(a_{j, i})]}
$$
Trong khi đó, mật độ của **Multiple Modular Subset Sum problem** là :
$$
d = \frac{n}{k.\log_2M}
$$
Người ta chứng minh rằng **Multiple Subset Sum Problem** có thể được giải với giới hạn $d<0.9408$, tương tự **Subset Sum Problem** với thuật toán **CJLOSS**. Ta sẽ tạo ra một Lattice $B$ có dạng như sau :
$$
B=
\begin{bmatrix}
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{bmatrix}
$$
Với $N>\sqrt{\frac{n+1}{4}}$, tương tự lần trước, tổ hợp tuyến tính $(e_1,...,e_n,−1)$ sẽ **có thể** tạo ra một vector ngắn có dạng :
$$
x=(e_1−\frac12,...,e_n−\frac12,−\frac12,0,...,0)
$$
>hoặc đó có thể là $-x$
Bài toán **Modular Multiple Subset Sum Problem** có thể được giải với $d<0.9408$ và $k = O(\frac{n}{log_2((n+1)\sqrt{n}+1)})$ bằng cách sử dụng LLL với cơ sở **B'** này :
$$
B'=
\begin{bmatrix} 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{bmatrix}
$$
Để biết tại sao vector mục tiêu lại nằm trong Lattice này, ta viết lại các phương trình Modular :
$$
\sum_{i=1}^{n} e_i.a_{j, i}= s_j\pmod{M}=\sum_{i=1}^{n} e_i.a_{j, i}= s_j + j_jM
$$
Nhận thấy rằng, tổ hợp tuyến tính $(e_1,...,e_n,−l_1,...,−l_k,−1)$ sẽ tạo ra vector mục tiêu có dạng :
$$
x=(e_1−\frac12,...,e_n−\frac12,−\frac12,0,...,0)
$$
### Hidden Number Problem
**Hidden Number Problem (HNP)** hay bài toán tìm số bị giấu được giới thiệu lần đầu cho mục đích chứng minh mức độ bảo mật bit của giao thức trao đổi khóa Diffie-Hellman. Ở mức độ cao hơn, bài toán HNP giúp ta khôi phục một số $\alpha$ bị giấu khi cho trước một vài đại lượng có mối quan hệ tuyến tính với $\alpha$.
Công thức ban đầu của HNP là tìm số nguyên bí mật $\alpha$ modulo với một số nguyên tố $p$ khi được cho trước **most significant bits (msb)** của một số $t_i.\alpha \mod p$ với $t_i$ là các số ngẫu nhiên và đã biết. Chúng ta sẽ tiến hành nghiên cứu bài toán trên bằng cách chuyển nó về bài toán tìm nghiệm của một hệ phương trình tuyến tính.
---
Định nghĩa **(Hidden Number Problem)** : Cho $p$ là một số nguyên tố và $\alpha\in[1,p-1]$ là một số nguyên bí mật. Hãy tìm lại $\alpha$ khi được cho $m$ cặp số nguyên $\{(t_i, a_i) \}^m_{i=1}$ sao cho :
$$
\beta_i-t_i\alpha+a_i\equiv 0\pmod p
$$
với $\beta_i$ chưa biết và thỏa mãn $|\beta_i|<B$ với một số $B<p$ nào đó.
Bài toán trên có thể được giải theo hai hướng là : chuyển nó về bài toán **CVP** hoặc chuyển nó về bài toán **SVP**.
- **Sử dụng CVP** : Nếu có các tham số thích hợp, ta có thể giải bài toán HNP bằng cách chuyển nó về bài toán CVP. Cho một cơ sở $B$ có dạng :
$$
B=
\begin{bmatrix}
p & & & & \\
&p & & & \\
& &\ddots & & \\
& & &p & \\
t_1 &t_2 &\cdots &t_m & 1/p
\end{bmatrix}
$$
Bằng cách viết lại phương trình $\beta_i-t_i\alpha+a_i\equiv 0\pmod p$ thành $\beta_i + a_i = t_i \alpha + k_ip$, ta thấy rằng tổ hợp tuyến tính $x=(k_1,...,k_m, \alpha)$ sẽ tạo ra một vector $t=xB=(\beta_1+a_1,...,\beta_m+a_m,\frac{\alpha}{p})$. Ta đặt $t=(a_1,...,a_m,0)$ thì khi này ta có :
$$
xB-t=u=(\beta_1,...,\beta_m,\frac{\alpha}{p})
$$
Khi này, $u\leq\sqrt{m+1}.B$. Ngoài ra, định thức của cơ sở trên là $p^{m-1}$ nên ta có thể sử dụng thuật toán xấp xỉ CVP để tính được giá trị của $u$, có được $u$ rồi thì ta chỉ cần nhân thêm $p$ vào nữa là sẽ thu được $\alpha$.
- **Sử dụng SVP** : 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 vector mục tiêu CVP dưới dạng một hàng trong cơ sở lattice để có được cơ sở $B'$ :
$$
B'=
\begin{bmatrix}
p & & & & & \\
&p & & & & \\
& &\ddots & & & \\
& & &p & & \\
t_1 &t_2 &\cdots &t_m & B/p \\a_1 &a_2 &\cdots &a_m & & B
\end{bmatrix}
$$
Lattice này chứa vector:
$$
u'=(β_1,...,β_m,\frac{αB}{p}, −B)
$$
được tạo nên từ tổ hợp tuyến tính $(k_1,…,k_m,\alpha,-1)$. Ngoài ra 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**. Một điểm đáng chú ý là khi ta áp dụng LLL với cơ sở trên thì ta sẽ được vector ngắn nhất là $(0,...,0,B,0)$, tạo nên từ tổ hợp tuyến tính $(-t_1,...,-t_m,p,0)$ nên $u'$ nhiều khả năng sẽ là vector thứ hai của cơ sở được rút gọn chứ không phải vector ngắn nhất.
Lấy một ví dụ cơ bản để các bạn dễ hiểu : 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 $\alpha=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à $β_i<B=20$. Ta xây dựng ma trận $B$ như sau :
$$
B=
\begin{bmatrix}p & & & & & \\
&p & & & & \\
& &\ddots & & & \\
& & &p & & \\
t_1 &t_2 &\cdots &t_m & B/p \\
a_1 &a_2 &\cdots &a_m & & B
\end{bmatrix} =
\begin{bmatrix}
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{bmatrix}
$$
Áp dụng LLL, ta được cơ sở $B'$ như sau :
$$
B'=
\begin{bmatrix}
0 & 0 & 0 & 20 & 0 \\
-15 & -12 & -16 & \frac{1840}{401} & 20 \\
24 & -5 & -6 & \frac{-1800}{401} & 20 \\
6 & -42 & -5 & \frac{-1440}{401} & -40 \\
-11 & -1 & 57 & \frac{-3880}{401} & 20
\end{bmatrix}
$$
Nhìn vào hàng đầu tiên ta thấy vector có dạng $(0,0,0,20,0)$. Với lý thuyết đã nhắc ở trên thì vector ta tìm kiếm sẽ có dạng $u=(β_1,...,β_m,\frac{αB}{p}, −B)$.
Tuy nhiên nhìn vào ma trận trên thì không có vector nào có dạng như vậy cả. Thế nhưng, vector $-u$ nó lại xuất hiện ở hàng thứ hai bởi vì $(\beta_1,\beta_2,\beta_3) = (15,12,16) < B = 20$.
Tuy chỉ có $-u$ nhưng ta có $\|-u\|=\|u\|$ nên có thể xem như là một và dùng nó để tìm ra $\alpha$ :
$$
\alpha=\frac{\alpha B}{p}.\frac{p}{B}=-\frac{1840}{401}.\frac{401}{20}=-92\mod(401)=309\mod(401)
$$
Code :
```python=
from sage.all import *
M = Matrix(QQ, [
[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]
])
# [ 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]
```
## Lattice Attacks
Trong mục này, chúng ta sẽ học một vài kiểu tấn công thường gặp trên hệ mã phổ biến là RSA. Ta sẽ tập trung vào cách chuyển một bài toán mật mã thông thường thành bài toán dựa trên Lattice mà chúng ta đã học lúc trước để giải chúng một cách gián tiếp.
### RSA Stereotyped Message
Một trong những ứng dụng đầu tiên và nổi tiếng nhất của Coppersmith trong việc tìm nghiệm nhỏ của một đa thức modulo là phương pháp tấn công vào low-exponent RSA (RSA sử dụng mũ nhỏ). Kiểu tấn công này sử dụng phương pháp Coppersmith (Coppersmith's method) để khôi phục lại toàn bộ Plaintext khi Ciphertext sử dụng mã hóa RSA với số mũ thấp là $3$ và có ít nhất $\frac23$ của Plaintext đã bị lộ.
Cho $N=p.q$, $e$ là một số mũ nhỏ. Giả sử cho $m=m'+x_0$. Nếu $x_0$ đủ nhỏ thì ta có công thức mã hóa là một phương trình, với bài toán là tìm nghiệm nhỏ và áp dụng phương pháp Coppersmith để giải nó, biến đổi như sau:
$$
c\equiv m^e\pmod{N}
$$
$$
\Leftrightarrow c\equiv (m'+x_0)^e\pmod{N}
$$
$$
\Leftrightarrow (m'+x_0)^e-c\equiv0\pmod{N}
$$
Đặt $f(x)=(m'+x)^e-c\pmod{N}$, ta sẽ có một đa thức Modulo bậc $e$. Ta hoàn toàn có thể sử dụng phương pháp của Coppersmith để tìm ra nghiệm $x_0$ với điều kiện :
$$
|x_0|\leq\frac{1}{2}N^{\frac{1}{e}}
$$
Với $e=3$ ta hoàn toàn có thể tìm được $x_0$ khi mà ta biết được $\frac23$ PLaintext.
Ví dụ : Cho
```python=
N = 318110533564846846327681562969806306267050757360741
e = 3
m = "My secret pin is XXXX"
c = pow(m,e,N)
print(c)
#c = 258334833041340726335779052313496169375744575431510
```
Ở đây `XXXX` là thứ mà ta cần tìm. Vì đã biết được $\frac23$ PLaintext nên ta có thể viết thành $m=m'+x_0$. Với $|x_0| < 2^{32}$, đây là một nghiệm nhỏ khi so sánh với kích thước của $N$, nên ta hoàn toàn có thể khôi phục được nó nhờ Coppersmith's method. Đặt :
$$
f(x)=(m'+x)^e-c\pmod{N}
$$
Ta sẽ giải phương trình trên
```python=
from sage.all import *
from Crypto.Util.number import *
N = 318110533564846846327681562969806306267050757360741
e = 3
c = 258334833041340726335779052313496169375744575431510
m_comma = bytes_to_long(b"My secret pin is \x00\x00\x00\x00")
x = PolynomialRing(Zmod(N), "x").gen()
f = (m_comma + x)^3 - c
x0 = f.small_roots(X = 256**4)
print(x0)
#[825831480]
```
Decode `[825831480]` sang bytes ta có : `1908` chính là mã PIN cần tìm.
---
Và vì cũng sắp tới giới hạn của HackMD nên mình sẽ viết wu các challenge CryptoHack **[ở đây](https://youtu.be/dQw4w9WgXcQ?si=uCdgOEF8xvY3IwgC)**.
Sign in with Wallet
Connect another wallet