<h1 style="text-align:center;">Lattices in Cryptography</h1>
**Máy tính lượng tử** đã đặt ra nhiều thách thức lớn cho các thuật toán mật mã học, đặc biệt là các thuật toán mã hóa khóa công khai như **RSA** và **Diffie-Hellman**, vì thuật toán **Shor** hoàn toàn có thể giải được chúng trong thời gian **đa thức**. Dù hiện tại, số lớn nhất bị phân tích bằng thuật toán Shor chỉ là **21**, nhưng sự phát triển của công nghệ lượng tử đã thúc đẩy nghiên cứu về mật mã hậu lượng tử (**PQC**) – những thuật toán được thiết kế để chống lại cả máy tính lượng tử.
PQC tập trung vào các thuật toán khóa công khai vì mã hóa khóa đối xứng vẫn có thể được bảo mật bằng cách tăng **độ dài khóa** (ví dụ, **AES-256** vẫn đảm bảo **128 bit** an toàn trước thuật toán **Grover**). Ngược lại, RSA sẽ cần khóa kích thước lên đến **1 terabyte** để đảm bảo an toàn trước Shor. Do đó, NIST đã khởi động quy trình tiêu chuẩn hóa PQC từ năm 2017, tìm kiếm các thuật toán có kích thước **khóa nhỏ** mà hiệu suất cao và an toàn trước cả tấn công cổ điển lẫn lượng tử. Trong đó, mật mã dựa trên lattice (**Lattice-Based Cryptography**) được đánh giá là tiềm năng nhất.
**Lattice** không chỉ hữu ích trong thiết kế thuật toán mà còn trong phân tích mật mã (**cryptanalysis**). Thuật toán **LLL** đã giúp phá vỡ nhiều hệ mật như **knapsack**, **RSA** với tham số đặc biệt và cả **NTRUEncrypt**. Việc nghiên cứu lattice giúp hiểu rõ hơn về bảo mật hậu lượng tử cũng như các kỹ thuật tấn công mật mã hiện đại. Trong Blog này, chúng ta sẽ tìm hiểu về LLL thông qua bài báo cáo [này](https://eprint.iacr.org/2023/032.pdf) và đi giải một số Challenge trên **CryptoHack** để nắm rõ hơn ứng dụng của nó trong **CTF**.
<img style="display: block; margin: auto;" width="500" src="https://hackmd.io/_uploads/rkVdaEyhkg.png"/>
<p style="text-align:center;">Lattice</p>
# I. Lattice
## Định nghĩa
- **++Định nghĩa++ (Lattice):** Một Lattice $\mathcal{L}$ là một không gian $n$-chiều được tạo nên từ các tổ hợp tuyến tính với hệ số ++nguyên++ của một tập các vector cơ sở $\mathbf{B} = \left\{\mathbf{b}_1, \mathbf{b}_2, \dots,\mathbf{b}_m \right\}$ trong không gian $\mathbb{R}^n$:
$$\mathcal{L} = \mathcal{L}(\mathbf{B}) = \left\{ \sum_{i=1}^{m} a_i \mathbf{b}_i \mid a_i \in \mathbb{Z} \right\}
$$
- **++Ví dụ++:** Trong không gian $\mathbb{R}^2$, cho hai vector cơ sở là $a = (3,5)$ và $b = (4, 9)$ thì không gian Lattice $\mathcal{L}$ 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, ví dụ: $1 \cdot a + 2 \cdot b = (11, 23)$, $3 \cdot a + 4 \cdot b = (25, 51) \dots$
- **++Minh họa++:**
- Ta có tổ hợp tuyến tính với hệ số **thực** của hai vector cơ sở có thể tạo nên một **span** ví dụ như thế này (thực tế nó có thể phủ kín toàn bộ không gian):
- Còn với **Lattice**, vì hệ số của tổ hợp tuyến tính là **nguyên** nên nó sẽ tạo nên các điểm rời rạc, một điểm chú ý là các vector cơ sở phải có đuôi ở gốc tọa độ:
<p style="text-align:center;">Một Lattice được tạo ra từ vector (1, 0) và vector (0, 1)</p>
> Sử dụng một cơ sở, chúng ta có thể đạt đến bất kỳ điểm nào trong Lattice
> với bội số nguyên của các vectơ cơ sở.
---
## Tính chất
Một không gian Lattice là **không độc nhất**, nghĩa là hoàn toàn có thể tạo ra một Lattice giống y hệt nhau từ nhiều vector cơ sở khác nhau:
<img style="display: block; margin: auto;" width="600" src="https://hackmd.io/_uploads/ByCZ3TS9Je.png"/>
<p style="text-align:center;">Dù (b1, b2) và (b1', b2') là khác nhau nhưng chúng đều tạo ra một Lattice (các chấm xanh) giống nhau</p>
- Các vector cơ sở mà tạo ra một Lattice giống nhau đều được tính là các cơ sở của Lattice đó và người ta chứng minh rằng một Lattice sẽ có vô số vector cơ sở.
- **Ví dụ:** ta có hai cơ sở là $[(0,1), (1, 0)]$ và $[(2, 1), (7,3)]$ thì sẽ được hai Lattice như sau:
- Lattice tạo từ vector cơ sở $[(0,1), (1, 0)]$:
- Lattice tạo từ vector cơ sở $[(2, 1), (7,3)]$:
---
> Nếu số lượng cơ sở là vô hạn, vậy có cách nào để nhận biết liệu một cơ sở có phải là cơ sở **đúng** của một Lattice hay không?
> Để 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++ (Fundamental Parallelepiped):** Có thể dịch là hình hộp cơ sở, gọi $\mathbf{B} = \left\{ \mathbf{b}_1, \dots , \mathbf{b}_m \right\}$ là cơ sở của một Lattice thì hình hộp cơ sở $\mathbf{B}$ được định nghĩa là:
$$\mathcal{P}(\mathbf{B}) = \left\{ \sum_{i=1}^{m} a_i \mathbf{b}_i \mid a_i \in [0,1) \right\}$$
- Ta thấy rằng công thức trên khá giống công thức của Lattice, chỉ khác là bây giờ hệ số $a_i \in [0, 1)$, điều đó khiến cho các vector cở sở thay vì tạo ra các điểm rời rạc thì chúng sẽ tạo thành **một** hình hộp (màu xám bên dưới) và ta có thể dùng hình hộp đó để lát đầy toàn bộ không gian Lattice:
<img style="display: block; margin: auto;" width="400" src="https://hackmd.io/_uploads/r16tk6L51e.png"/>
> Lưu ý đây là hình hộp nửa mở (**half-open**) nên nó sẽ không chứa các điểm Lattice nằm ở biên.
- Bằng cách kiểm tra xem hình hộp do một vector cơ sở tạo ra có chứa một điểm **khác không** nào khác hay không? Nếu không thì vector đó sẽ là cơ sở của Lattice và ngược lại.
> Cặp Vector của hình bên trái không phải là vector cơ sở của Lattice vì nó chứa một điểm khác không nằm trong hình hộp cơ sở. Và ngược lại vector của hình bên phải sẽ thỏa mãn.
---
- **++Định nghĩa++ (Determinant):** Có thể dịch là định thức. Gọi $\mathbf{B}$ là một cơ sở của một Lattice $\mathcal{L}$. Định thức của $\mathcal{L}$, ký hiệu $\text{det}(\mathcal{L})$ là thể tích (**volume**) n-chiều của hình hộp $\mathcal{P}(\mathbf{B})$, tức:
$$\text{det}(\mathcal{L}) = \text{vol}(\mathcal{P}(\mathbf{B})) = |\text{det}(\mathbf{B})|$$
- Đây là một đại lượng bất biến, tức mỗi hình hộp cơ sở do các vector cơ sở tạo ra đều sẽ có **chung** định thức.
- **++Định lý++:** Gọi $\mathbf{B}$ và $\mathbf{B}'$ là cơ sở của hai Lattice thì hai Lattice đó giống nhau hay $\mathcal{L}(\mathbf{B}) = \mathcal{L}(\mathbf{B}')$ khi và chỉ khi $\mathbf{B} = \mathbf{U}\mathbf{B}'$ với $\mathbf{U}$ là một ma trận số nguyên bất kỳ có $\text{det}(\mathbf{U}) = 1$.
- Từ định lý này 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: giả sử $\mathbf{B}$ và $\mathbf{B}'$ là cơ sở của Lattice $\mathcal{L}$ thì $\mathbf{B} = \mathbf{U}\mathbf{B}' \Rightarrow \text{det}(\mathbf{B}) = \text{det}(\mathbf{U}) \cdot \text{det}(\mathbf{B}') = 1 \cdot \text{det}(\mathbf{B}') = \text{det}(\mathbf{B}')$.
---
Một bất biến quan trọng khác của Lattice là **Successive Minima** $(\lambda_1, \lambda_2,\dots, \lambda_n)$. Ta có Successive Minima **đầu tiên** ký hiệu là $\lambda_1(\mathcal{L})$, là **chiều dài** của vector khác không **nhỏ nhất** trong Lattice, một Lattice bậc $n$ sẽ có $n$ successive minima.
- **++Đị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 $\mathcal{L}$ với tâm hình cầu tại gốc tọa độ.
$$\lambda_1(\mathcal{L}) \leq \lambda_2(\mathcal{L}) \leq \dots \leq \lambda_n(\mathcal{L}) $$
<img style="display: block; margin: auto;" width="400" src="https://hackmd.io/_uploads/rkFgECIq1l.png"/>
<p style="text-align:center;">First successive minima</p>
- **++Định lý++ (Minkowski’s First Theorem):** Gọi $\mathcal{L}$ là một Lattice bậc $n$ thì chiều dài vector ngắn nhất hay $\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}$$
- Khi ta sử dụng các thuật toán giảm cơ sở mạng như **LLL** hoặc **BKZ**, thì các vector trong cơ sở mới phải có độ dài gần bằng với các successive minima.
> Đây là một định lý quan trọng khi ta sử dụng **Latice Reduction** vì ta phải **Scale** ma trận ban đầu sao vector ngắn nhất thỏa mãn định lý trên. Mình sẽ nói rõ hơn sau này.
---
## Các bài toán khó của Lattice
Độ 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))**.
- **++Định nghĩa++ (Shortest Vector Problem):** Cho một cơ sở $\mathbf{B}$ của một Lattice $\mathcal{L} = \mathcal{L}(\mathbf{B})$, yêu cầu của bài toán là tìm một vector $\mathbf{v}$ khác không sao cho $||\mathbf{v}|| = \lambda_1(\mathcal{L})$.
- **++Định nghĩa++ (Closest Vector Problem (CVP)):** Cho một cơ sở $\mathbf{B}$ của một Lattice $\mathcal{L} = \mathcal{L}(\mathbf{B})$, và một vector $\mathbf{t}$ bất kỳ (không nhất thiết phải là một điểm trong $\mathcal{L}$), target của ta 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}||$.
> Hai bài toán trên được cho là rất khó với độ khó là **NP-Hard** nên đây được xem là nền móng cho các thuật toán mã hóa có thể chống lại máy tính lượng tử.
---
# II. Lattice Reduction
Lattice Reduction hay giảm cơ sở mạng, mục đích của nó là biến một cơ sở lattice bất kỳ (**bad basis**) thành một cơ sở khác mà các vector cơ sở phải ngắn và gần trực giao với nhau hơn (**good basis**). Cũng như giúp chúng ta giải bài toán **SVP** hoặc **CVP**.
Đối với một Lattice **hai** chiều, ta có thể sử dụng một thuật toán gọi là **Gaussian Reduction** với đầu ra là một vector $v_1$ khác không nhắn nhất, qua đó giải được bài toán **SVP**. Nhưng với một Lattice nhiều chiều hơn, ta sẽ làm quen với thuật toán **LLL** được tích hợp sẵn trong **sagemath** có thể chạy trong thời gian đa thức.
---
## Gaussian Reduction
Thuật toán Gauss hoạt động bằng cách **trừ** bội số của 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:
```
Loop
(a) If ||v2|| < ||v1||, swap v1, v2
(b) Compute m = ⌊ v1∙v2 / v1∙v1 ⌉
(c) If m = 0, return v1, v2
(d) v2 = v2 - m*v1
Continue Loop
```
- Mô phỏng bẳng `sagemath`:
```python=
from sage.all import *
u = vector([10,10])
v = vector([5,6])
def gaussian_reduction(v1, v2):
while True:
if v2.norm() < v1.norm(): # sử dụng .norm() để tính chiều dài
v1, v2 = v2, v1
m = round((v1*v2) // (v1*v1)) # làm tròn tới số nguyên gần nhất
if m == 0:
return v1, v2
v2 -= m*v1
a, b = gaussian_reduction(u, v)
print((a, b))
#((0, 2), (5, 0))
```
## LLL Algorithm
Được đặt theo tên ba nhà toán học phát minh ra nó là **Lenstra**, **Lenstra** and **Lovász**. Thuật toán này 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` và `đ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.
- Bước đầu tiên của mỗi lần lặp là sử dụng **Gram-Schmidt** để trực giao hóa cơ sở $\mathbf{B} = \left\{\mathbf{b}_1,\dots, \mathbf{b}_n \right\}$. Nó trả lại cho ta vector trực giao $\mathbf{b}^*_1,\dots, \mathbf{b}^*_n$ và hệ số $\mu_{i,j}$ được định nghĩa như sau:
$$
\begin{cases}
\mathbf{b}_i^* = \mathbf{b}_i, & i = 1 \\
\mathbf{b}_i^* = \mathbf{b}_i - \sum\limits_{j=1}^{i-1} \mu_{i, j} \times \mathbf{b}_j^*, & 1 < i \leq n
\end{cases}
\quad
\mu_{i,j} = \frac{\langle \mathbf{b}_i, \mathbf{b}_j^* \rangle}{\langle \mathbf{b}_j^*, \mathbf{b}_j^* \rangle}
$$
- Cho $\delta \in (0.25, 1)$. Một cơ sở $\mathbf{B} = \left\{\mathbf{b}_1,\dots, \mathbf{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**: Cơ sở phải được rút gọn.
$$(\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**: Các hệ số Gram-Schmidt không quá lớn.
$$\|\mu_{i, j}\| \leq 1/2 \quad \forall i > j $$
- Từ định nghĩa trên, ta có thuật toán của **LLL** như sau:
```!
while True:
for i = 2 to n:
for j = i-1 to 1:
b*[i], μ[i, j] = Gram-Schmidt(b[1]...b[n])
b[i] = b[i] - round(μ[i, j]) * b[j] # làm tròn μ tới số nguyên gần nhất
if Lovász's condition is satisfied:
return {b[1]...b[n]}
break
else:
swap b[i] and b[i+1]
```
- **Ví dụ:** Cho $\mathbf{B} = \left\{\mathbf{b}_1, \mathbf{b}_2\right\}$ với $\mathbf{b}_1 = (-2, 2), \mathbf{b}_2 = (-2, 1)$, ta sẽ áp dụng **LLL** cho cơ sở trên với $\delta = 0.75$.
- Đầu tiên ta sẽ đi tính **Gram-Schmidt**:
$$\mathbf{b}^*_1 = \mathbf{b}_1 = (-2, 2)$$
$$\mathbf{b}^*_2 = \mathbf{b}_2 - \frac{\langle \mathbf{b}_2, \mathbf{b}_1^* \rangle}{\langle \mathbf{b}_1^*, \mathbf{b}_1^* \rangle} \times\mathbf{b}_1^* = (-2, 1) - 0.75 \cdot(-2, 2) = (-0.5, -0.5)$$
$$\mu_{2,1} = \frac{\langle \mathbf{b}_2, \mathbf{b}_1^* \rangle}{\langle \mathbf{b}_1^*, \mathbf{b}_1^* \rangle} = 0.75$$
- Tiếp theo ta tính $\mathbf{b}_2 = \mathbf{b}_2 - \left \lfloor\mu_{2,1}\right \rceil \times \mathbf{b}_1 = (0, -1)$
- Giờ ta có $\mathbf{b}_1 = (-2, 2)$ và $\mathbf{b}_2 = (0, -1)$
- Nhưng điều kiện **Lovász** của $\mathbf{b}_1^*$ và $\mathbf{b}_2^*$ không thỏa mãn vì:
$$(\delta - \mu_{2, 1}^2) \times \|\mathbf{b}_1^*\|^2 = (0.75 - (0.75)^2) \cdot 8 = 1.5 \nleqslant \|\mathbf{b}_{2}^*\|^2 = 0.5$$
- Vì vậy ta tiến hành hoán đổi $\mathbf{b}_1$ và $\mathbf{b}_2$ thành $\mathbf{b}_1 = (0, -1), \mathbf{b}_2 = (-2, 2)$. Sau đó vẫn thực hiện các bước như trên được:
$$\mathbf{b}^*_1 = \mathbf{b}_1 = (0, -1)$$
$$\mathbf{b}^*_2 = (-2, 0)$$
$$\mu_{2, 1} = -2$$
- Giờ thì điều kiện của **Lovász** đã thỏa mãn:
$$(\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à kết thúc thuật toán rùi, ta được cơ sở rút gọn mới là $\mathbf{B}^* = \left\{\mathbf{b}_1^*, \mathbf{b}_2^* \right\} = \left\{(0, -1), (-2, 0) \right\}$.
- Ta thực hiện trong **Sagemath** như sau:
```python=
from sage.all import *
b1 = vector([-2,2])
b2 = vector([-2,1])
M = Matrix([b1, b2])
print(M.LLL())
# [ 0 -1] đây sẽ là vector ngắn nhất
# [-2 0]
```
:::info
Nếu bạn chú ý thì sẽ thấy **Vector ngắn nhất** trong Lattice sẽ luôn là vector thứ nhất của cơ sở mới!
:::
**++Định lý++:** Cho $\mathbf{B} = \left\{\mathbf{b}_1,\dots, \mathbf{b}_n \right\}$ là một cơ sở vector và $\mathbf{B}^* = \left\{\mathbf{b}^*_1,\dots, \mathbf{b}^*_n \right\}$ là cơ sở mới trực giao theo **Gram schmidt** thì: $$\lambda_1(\mathcal{L}(\mathbf{B})) \geq \text{min}_{i \in \left\{1,\dots,n \right\}}\|\mathbf{b}_i^*\|$$
**++Tính chất++:** Cho $\mathbf{B} = \left\{\mathbf{b}_1,\dots, \mathbf{b}_n \right\}$ là cơ sở mới sau khi giảm mạng thì:
$$\|\mathbf{b}_1\| \leq \left (\frac{2}{\sqrt{4\delta-1}}\right )^{n-1} \times \sqrt{n} \times |\text{det}(\mathcal{L})|^{1/n} $$
---
Nếu các bạn còn đang mơ hồ vì chưa biết hình dung nó như thế nào thì có thể hiểu theo ý hiểu thế này:
- Khi ta áp dụng LLL với một cơ sở $\mathbf{B}$ thì LLL sẽ **đi tìm** một tổ hợp tuyến tính $\mathbf{t}$ sao cho:
$$\mathbf{tB=x}$$
- Với $\mathbf{x}$ là một vector ngắn hoặc ngắn nhất thuộc Lattice ban đầu.
- LLL sẽ **không** lưu lại giá trị của $\mathbf{t}$ mà chỉ in ra giá trị của $\mathbf{x}$ vì thế ta cần biết một số mẹo để in ra $\mathbf{t}$.
- **Ví dụ:** Cho một ma trận $2\times 2$ được tạo từ hai vector cơ sở $[(A,B), (C,D)]$ như sau:
$$
\text{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 tổ hợp tuyến tính sao cho kết quả của tổ hợp tuyến tính là một vector mới có kích thước **nhỏ**.
- Hay nó sẽ **đi tìm** một vector $[x, y]$ sao cho khi nhân với ma trận cơ sở sẽ cho ra kết quả mới là nhỏ nhất:
$$
[x, y]
\times
\begin{bmatrix}
A & B \\
C & D \\
\end{bmatrix}
=
[x\cdot A + y \cdot C,\hspace{3mm} x \cdot B + y \cdot D]
$$
- Lấy từ ví dụ trên, cho một ma trận cơ sở như sau:
$$
\text{M} =
\begin{bmatrix}
-2 & 2 \\
-2 & 1 \\
\end{bmatrix}
$$
- Sau khi ta áp dụng LLL, được hai vector là $u =[0, -1]$ và $v = [-2, 0]$, vector $u$ của ta sẽ là vector ngắn nhất trong mạng.
- Nhưng LLL nó không lưu lại cặp số $[x,y]$ đó. Để biết được tổ hợp tuyến tính mà LLL đã dùng, ta sẽ sử dụng `.solve_left()` hoặc `solve_right()`:
```python=
from sage.all import *
b1 = vector([-2,2])
b2 = vector([-2,1])
M = Matrix([b1, b2])
u = Matrix([0, -1])
v = Matrix([-2, 0])
print(M.solve_left(u))
# [-1 1]
print(M.solve_left(v))
# [-1 2]
```
$$
[-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]
$$
- Có một cách rất hay để biết được tổ hợp tuyến tính mà LLL đã dùng đó là thiết lập một ma trận kết hợp từ ma trận cơ sở và ma trận đơn vị như sau:
$$
B =
\begin{bmatrix}
A & B & 1 & 0\\
C & D & 0 & 1\\
\end{bmatrix}
$$
- LLL phải đi tìm một vector có dạng là $[x, y]$ để nhân cho $B$ sao cho ra được vector nhỏ nhất, khi này vector nhỏ nhất của ta sẽ có dạng:
$$
[x, y] \times
\begin{bmatrix}
A & B & 1 & 0\\
C & D & 0 & 1\\
\end{bmatrix}
=
[x\cdot A + y \cdot C, \hspace{3mm} x\cdot B + y \cdot D,\hspace{3mm} x,\hspace{3mm} y]
$$
- Nhìn vào hai số cuối của vector trên, ta sẽ biết được tổ hợp tuyến tính $[x,y]$ mà LLL đã dùng :wink:
- Ví dụ:
```python=
from sage.all import *
M = Matrix([[-2, 2, 1, 0], [-2, 1, 0, 1]])
print(M.LLL())
# [ 0 -1 -1 1] tìm được vector ngắn nhất là [0, -1], tổ hợp tuyến tính được dùng là [-1, 1]
# [-2 1 0 1]
```
> Nhưng không phải lúc nào LLL nó cũng trả về vector ta cần tìm nhé, vì đôi lúc vector ta cần tìm lại không phải vector ngắn mà quá lớn, khi này ta phải biết cách để scale ma trận cơ sở. Tham khảo đường dẫn [này](https://valter.wiki/blog/lattices/) để nắm rõ cách dùng và một vài ví dụ của LLL.
---
## An Application of Lattice Reduction
Trước khi bàn sâu hơn về ứng dụng của LLL trong mật mã học, thì ta sẽ nhìn sơ qua về ứng dụng của nó trong toán đại số. Vấn đề chúng ta sẽ tìm hiểu là xây dựng lại một đa thức tối thiểu có nghiệm là một xấp xỉ của một số.
- Cho $\alpha \in F$ với $F$ là một trường. Một đa thức monic 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 đó.
- Chúng ta sẽ sử dụng LLL để tìm đa thức tối thiểu $f(x)$ của $\alpha = 7 + \sqrt[3]{5}$ với xấp xỉ của $\alpha$ là $\beta \approx 8.70997594$ có độ chính xác $8$ chữ số thập phân.
- Đầu tiên, ta giả sử rằng $f$ sẽ có bậc là $3$ vì thấy có $\sqrt[3]{5}$, vì vậy ta sẽ viết lại đa thức như sau: $f(x) = a_0 + a_1x + a_2x^2 + a_3x^3$ với $a_i \in \mathbb{R}$. Ta có $f(\alpha) = 0$, vì thế $f(\beta) \approx 0$. Để chuyển $\beta$ thành số nguyên, ta nhân thêm $10^8$ cho đa thức để có:
$$10^8a_0 + \left \lfloor10^8\beta\right \rfloor a_1 + \left \lfloor10^8\beta^2\right \rfloor a_2 + \left \lfloor10^8\beta^3\right \rfloor a_3 \approx 0$$
- Nhiệm vụ của ta là đi tìm các hệ số $a_0,a_1,a_2$ là hoàn thành được đa thức trên, đây là đa thức monic nên $a_3$ sẽ bằng $1$.
- Tiến hành lập một Ma trận cơ sở 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 \\
\left \lfloor10^8\beta^3\right \rfloor & 0 & 0 & 0 \\
\end{bmatrix}
=
\begin{bmatrix}
100000000 & 1 & 0 & 0 \\
870997594 & 0 & 1 & 0 \\
7586368087 & 0 & 0 & 1 \\
66077083514 & 0 & 0 & 0 \\
\end{bmatrix}
$$
- Như mình đã nhắc ở phần `LLL Algorithm` thì LLL nó sẽ đi tìm một tổ hợp tuyến tính để khi nhân với ma trận $B$ sẽ cho ra vector ngắn nhất, khi này vector ngắn nhất của ta sẽ có dạng:
$$[10^8a_0 + \left \lfloor10^8\beta\right \rfloor a_1 + \left \lfloor10^8\beta^2\right \rfloor a_2 + \left \lfloor10^8\beta^3\right \rfloor a_3, \hspace{3mm} a_0, \hspace{3mm} a_1, \hspace{3mm} a_2,] = [\approx0, a_0, a_1, a_2]$$
- Tiến hành LLL ma trận $B$, ta được ma trận như sau:
$$
\begin{bmatrix}
5 &-348 &147 & -21\\
-438 & 75& -116& -188\\
357 & 136 &220 &-419\\
109 & -214 &-563 &-159
\end{bmatrix}
$$
- Hàng đầu tiên chính là vector ngắn nhất của ta, ta thấy rằng số đầu tiên là $5$ dù không bằng $0$ nhưng như vậy là $\approx 0$ rồi. Các số tiếp theo của vector chính là các hệ số $a_0, a_1, a_2$ của đa thức của ta, vì vậy đa thức tối giản của $\alpha = 7 + \sqrt[3]{5}$ là:
$$f(x) = x^3 - 21x^2 + 147x - 348$$
- Sagemath:
```python=
from sage.all import *
M = Matrix([
[100000000, 1, 0, 0],
[870997594, 0, 1, 0],
[7586368087, 0, 0, 1],
[66077083514, 0, 0, 0]])
print(M.LLL())
# [ 5 -348 147 -21]
# [-438 75 -116 -188]
# [ 357 136 220 -419]
# [ 109 -214 -563 -159]
```
> Một **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 cần chú ý chia hai trường hợp.
---
# III. Lattice-based cryptanalysis
Trong phần này chúng ta sẽ tiến hành nghiên cứu một số bài toán có thể giải được bằng cách mô hình hóa chúng thành bài toán **CVP** hoặc **SVP**. Các bài toán này được đặc trưng bởi bản chất tuyến tính của chúng và trong phần này, ta gọi chúng là các bài toán dựa trên Lattice (**lattice-based problems**).
## Finding Small Roots
Bắt đầu với một trong những vấn đề có thể nói là có ảnh hưởng và được ứng dụng rộng rãi nhất trong lĩnh vực phân tích mật mã: bài toán tìm nghiệm "**nhỏ**" của một đa thức Modulo một số nguyên. Nó được nghiên cứu bởi **Coppersmith** và ông cũng áp dụng các kỹ thuật của mình để phá vỡ **RSA** với số mũ thấp trong một số trường hợp nhất định (Coppersmith's attack).
Phương pháp của Coppersmith đó là tìm ra một nghiệm nhỏ trong một phương trình đa thức Modulo một hợp số mà không cần biết phân tích thừa số nguyên tố của số đó. Với điều kiện $x_0$ là nghiệm của phương trình $f(x_0) \equiv 0 \pmod N$ và $x_0 \leq N^{1/d}$.
Việc tìm nghiệm của một đa thức Modulo một số nguyên tố thì dễ, trong khi tìm nghiệm của một đa thức trong Modulo một hợp số $N$ thì khó tương đương với việc phân tích thừa số nguyên tố của số $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ã.
### Coppersmith’s ideas
- Cho $F(x) = x^d + a_{d-1}x^{d-1}+\cdots+a_1x+a_0$ là một đa thức monic bậc $d$ với hệ số nguyên. Giả sử ta biết rằng chắc chắn tồn tại một nghiệm nguyên $x_0$ nhỏ sao cho $F(x_0) \equiv 0 \pmod N$ và $|x_0| < N^{1/d}$ thì bài toán của chúng ta là đi tìm nghiệm $x_0$ nhỏ đó.
- Vì $|x^i_0| < N$ với mọi $0 \leq i \leq d$ nên nếu hệ số của đa thức $F(x)$ đủ nhỏ, thậm chị một số đa thức có thể thỏa mãn $F(x_0) = 0$ trên tập số nguyên $\mathbb{Z}$, thì ta có thể sử dụng các phương pháp tìm nghiệm nguyên của một đa thức trên tập $\mathbb{Z}$ như là **Newton's method** rồi sau đó xấp xỉ các nghiệm đó tới các số nguyên gần nhất và kiểm tra xem liệu nó có phải nghiệm của $F(x)$ hay không.
- Vấn đề ở đây chính là ta phải đối mặt với các đa thức monic $F(x)$ có nghiệm nhỏ nhưng hệ số của nó thì rất lớn. Coppersmith nảy ra ý tưởng đó là xây dựng một đa thức $G(x)$ từ đa thức $F(x)$ ban đầu nhưng sao cho các hệ số của đa thức mới là đủ nhỏ để có thể áp dụng các phương pháp ở trên.
- Ta có một tính chất nếu $F(x_0) \equiv 0 \pmod N$ thì khi ta cộng cho $F(x)$ các đa thức 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. Vì thế ý tưởng của ông là ông sẽ cộng đa thức $F(x)$ cho các đa thức $g_i(x)$ đến khi các hệ số của $F(x)$ đủ nhỏ thì ông sẽ 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$.
- **Ví dụ:** Cho $N = 17 \cdot 19 = 323$ và cho $F(x) = x^2 + 33x+215$, yêu cầu hãy tìm một nghiệm nhỏ $x_0$ sao cho $F(x_0) \equiv 0 \pmod N$.
- Lưu ý rằng $F(x_0) \neq 0$ trên tập $\mathbb{Z}$.
- Ta tạo một đa thức $G(x)$ trên tập $\mathbb{Z}$ có dạng như sau:
$$G(x) = 9F(x) - N\cdot x - N\cdot6$$
$$\Leftrightarrow G(x) = 9x^2 + 287x + 1935 - 323x - 1938$$
$$\Leftrightarrow G(x) = 9x^2-26x-3$$
- Sử dụng **Newton’s method** hoặc giải phương trình bậc hai, ta giải được một nghiệm nguyên của $G(x)$ là $x = 3$
- Vậy nghiệm của phương trình $F(x_0) \equiv 0 \pmod {323}$ là $x_0=3$.
### Introduction to Coppersmith's method
- Gọi $N$ là một hợp số của nhiều số nguyên tố, $F(x) = x^d + \displaystyle\sum_{i=0}^{d-1} a_ix^i$ là một đa thức monic bậc $d$ và $g_i(x) = Nx^i \hspace{3mm}\forall i \in [0, d)$ là các đa thức có nghiệm $x_0 \pmod N$. Giả định $F(x)$ có ít nhất một nghiệm $x_0$ modulo $N$ sao cho $|x_0| < B$ với một số nguyên $B$ cụ thể thì ta có thể lập được một cơ sở Lattice tạo nên từ $F(x)$ và $g_i(x)$ như sau:
$$
\mathbf{B} = \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}
$$
- Khi ta áp dụng LLL với cơ sở trên, đ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 ở hàng cuối cùng, kết quả cuối cùng sẽ một vector chứa các **hệ số** của một đa thức $G(x)$ có nghiệm $x_0$ thỏa $G(x_0) = 0$, đặt vector đó là $b = (b_0,\dots, b_d)$.
> Vector chứa các hệ số của $G(x)$ không nhất thiết phải là vector ngắn nhất.
- Khi này nghiệm $x_0$ của phương trình $G(x_0) = 0$ cũng thỏa mãn phương trình $F(x_0) \equiv 0 \pmod N$. Đa thức $G(x)$ của ta sẽ có dạng:
$$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$$
- **Ví dụ:** Cho $N = 10001$ và đa thức $F(x) = x^3 + 10x^2 + 5000x - 222$, ta biết rằng tồn tại một nghiệm $x_0 < 10$ thỏa mãn $F(x_0) \equiv 0 \pmod N$, ta đặt $B = 10$ làm giới hạn cho nghiệm $x_0$ và thiết lập một cơ sở Lattice như sau:
$$
\mathbf{B} = \begin{bmatrix}
N &0 &0 & 0 \\
0 & BN & 0 & 0 \\
0 &0 & B^2N & 0 \\
-222 & 5000B & 10B^2 & B^{3}
\end{bmatrix}
$$
- Áp dụng LLL ta được một cơ sở mới như sau:
```python
[ 444 10 -2000 -2000]
[ 9557 -10 2000 2000]
[ -222 50000 1000 1000]
[ 989 2500 500100 -500000]
```
- Nhìn vào vector đầu tiên, ta thấy nó có dạng $\left ( b_0, b_1 \times B, b_2\times B^2, b_3\times B^3 \right )$, vì vậy nó chính là hệ số của đa thức $G(x)$:
$$G(x) = 444 + \frac{10}{10}x+\frac{-2000}{10^2}x^{2} + \frac{-2000}{10^3}x^3$$
$$\Rightarrow G(x) = -2x^3 - 20x^2 + x + 444$$
- Giải phương trình $G(x) = 0$ trên tập $\mathbb{Z}$ ta được $x_0 = 4$.
- Thay vào phương trình ban đầu ta có $F(4) \equiv 20002 \equiv 0 \pmod {10001}$, vậy $x_0 = 4$ là nghiệm cần tìm.
- **Script**:
```python=
from sage.all import *
N = 10001
B = 10
M = matrix([[N, 0, 0, 0 ],
[0, B*N, 0, 0 ],
[0, 0, B**2*N, 0 ],
[-222, 5000*B, 10*B**2, B**3]])
coeff = M.LLL()[0]
# tạo biến x trên tập số nguyên
x = ZZ["x"].gen()
f = x**3 + 10*x**2 + 5000*x - 222
g = coeff[0] + (coeff[1]//B)*x + (coeff[2]//B**2)*x**2 + (coeff[3]//B**3)*x**3
x_0 = g.roots()[0][0] # dùng .roots() để giải g(x) = 0
print(f"{x_0 = }")
print(f(x_0) % N)
# x_0 = 4
# 0
```
- Nếu bạn tò mò đa thức $F(x)$ được biến đổi như thế nào để ra đa thức $G(x)$ thì ta có thể biến đổi ma trận $M$ bằng cách ghép thêm vào $M$ một ma trận đơn vị như dưới rồi áp dụng LLL:
```python=
from sage.all import *
N = 10001
B = 10
M = matrix([[N, 0, 0, 0 , 1, 0, 0, 0],
[0, B*N, 0, 0 , 0, 1, 0, 0],
[0, 0, B**2*N, 0 , 0, 0, 1, 0],
[-222, 5000*B, 10*B**2, B**3, 0, 0, 0, 1]])
print(M.LLL())
# [ 444 10 -2000 -2000 0 1 0 -2]
# [ 9557 -10 2000 2000 1 -1 0 2]
# [ -222 50000 1000 1000 0 0 0 1]
# [ 989 2500 500100 -500000 -11 250 1 -500]
```
- Nhìn vào vector đầu tiên ta biết được rằng $G(x) = -2F(x) + Nx$ .
- Thư viện **sagemath** có một phương thức gọi là `small_roots()` có thể giúp ta giải bài toán tìm nghiệm nhỏ của một đa thức Modulo một số nguyên:
```python=
from sage.all import *
N = 10001
B = 10
x = PolynomialRing(Zmod(N), "x").gen()
f = x**3 + 10*x**2 + 5000*x - 222
print(f.small_roots(X = 10)) # small_roots() nhận vào X, beta và epsilon
# [4]
# ví dụ này cho số khá là nhỏ nên ta cũng không cần truyền gì nhiều
```
- **++Định lý:++** Cho $N$ là một số nguyên chưa biết phân tích thừa số nguyên tố và $N$ phải có một ước $b$ sao cho $b \geq N^{\beta}$. Cho $f(x)$ là một đa thức đơn biến, monic, có bậc là $\delta$ và $0 < \epsilon \leq \frac{1}{7} \beta$. Thì ta có thể tìm được tất cả các nghiệm $x_0$ của $f(x) \equiv 0 \pmod b$ trong thời gian đa thức với:
<span style="font-size:1.4em; text-align:center">$$|x_0| \leq \frac{1}{2} N ^{\frac{\beta^2}{\delta} - \epsilon}$$</span>
- Có một số cách để xác định $\beta$ như sau:
- Nếu biết giá trị của $b$, thì $\beta = \log_N(b)$
- Nếu $b$ chưa biết nhưng biết `bitsize` của $b$, thì $\beta = (\text{bitsize(b) - 1}) \div (\text{bitsize(N)})$
- Nếu $N = pq$ với $\text{bitsize}(p) = \text{bitsize}(q)$ thì $\beta \approx0.499$
---
## Knapsack Problem
Knapsack Problem hay "bài toán ba lô" 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$ target cho trước.
Trong phần này chúng ta sẽ tìm hiểu qua một hệ mã sử dụng bài toán ba lô là **Merkle – Hellman** và tìm hiểu cách giải một số trường hợp đặc biệt của bài toán **subset sum** cũng như bài toán **modular subset sum**.
### Merkle – Hellman Cryptosystem
Đây là một hệ mã khóa công khai do ông **Ralph Merkle** và **Mertin Hellman** phát minh vào năm 1978. Đây là một trong những hệ mật khóa công khai đầu tiên trên thế giới nhưng hiện nay thì hong được dùng nữa vì vào năm 1982 nó bị ông **Adi Shamir** chứng minh là có thể bị LLL bẻ gãy trong thời gian đa thức.
Hệ mã này dựa trên bài toán **Subset Sum Problem** (bài toán tổng tập con), cụ thể là một dạng đặc biệt gọi là **Superincreasing Knapsack**. Một dãy số được gọi là superincreasing nếu mỗi phần tử trong dãy lớn hơn tổng của tất cả các phần tử đứng trước nó. Quá trình sinh khóa và mã hóa, giải mã diễn ra như sau:
#### Sinh khóa
- Chọn một số nguyên $n$ làm kích thước của khóa bí mật.
- Khóa **bí mật** của ta sẽ là một **Superincreasing Knapsack** tức là một dãy số có số phía sau phải lớn hơn tổng của các số phía trước, ta sẽ gọi nó là $W = \left(w_1, w_2,\dots,w_n \right)$ và $w_i$ thỏa mãn điều kiện sau:
$$w_k > \sum_{i=1}^{k-1}w_i \hspace{5mm} 1 < k \leq n$$
- Tiếp theo chọn một số nguyên $q$ làm **modulo** sao cho:
$$q > \sum_{i=1}^{n}w_i$$
- Chọn một số nguyên $r$ sao cho $\text{GCD}(r, q) = 1$.
- Tính khóa công khai $B = \left( b_1,b_2,\dots,b_n\right)$ theo công thức:
$$b_i = r \cdot w_i \mod q$$
> Vậy khóa công khai của chúng ta là $B$ và khóa bí mật là $(W,q,r)$.
#### Mã hóa
- Gọi $m$ là một văn bản **nhị phân** dài $n$ bit dạng $\left\{m_1, m_2,\dots,m_n \right\}$ với $m_1$ là bit lớn nhất và $b_i$ là khóa công khai của ta thì văn bản $m$ được mã hóa theo công thức:
$$c = \sum_{i=1}^{n}m_i.b_i$$
#### Giải mã
- Để giải mã $c$, ta phải tìm một tập con của $B$ sao cho nó có tổng là $c$. Ta có thể giải bài toán này bằng cách chuyển nó về bài toán tìm tập con của $W$. Vấn đề trên có thể được giải trong thời gian đa thức vì $W$ là một dãy siêu tăng.
- Đầu tiên tính nghịch đảo của $r$ trong modulo $q$.
$$r' \equiv r^{-1} \pmod q$$
- Tiếp theo ta tính:
$$c' \equiv c \cdot r' \pmod q$$
- Bây giờ ta sẽ phải giải bài toán subnet sum của $c'$ với khóa bí mật $W$. Thuật toán **greedy algorithm** có thể giải bài toán trên trong thời gian đa thức.
- Sau khi giải bài toán subnet sum của $c'$ ta được một tập $X = (x_1,x_2,\dots,x_k)$ là tập chứa các **index** của các phần tử $\in W$ mà cho ra tổng bằng $c'$ tức:
$$c' = \sum_{i=1}^{k}w_{x_i}$$
- Ta sẽ khôi phục lại $m$ bằng cách xây dựng lại một chuỗi nhị phân với $1$ tại index $x_i$ và $0$ tại các vị trí khác:
$$m = \sum_{i=1}^{k}2^{n-x_i}$$
---
Mô tả thuật toán **greedy algorithm** tìm tập con của dãy $W$ mà cho ra tổng bằng $c'$ trong thời gian đa thức:
1. Khởi tạo $X$ là một list rỗng.
2. Tìm phần tử lớn nhất trong $W$ sao cho bé hơn hoặc bằng $c'$, gọi là $w_j$.
3. Trừ $c' := c' - w_j$.
4. Thêm $j$ vào list $X$.
5. Bỏ $w_j$ ra khỏi khóa bí mật $W$.
6. Nếu $c' > 0$, quay lại bước 2.
#### Ví dụ
Chọn khóa bí mật $W$ là một dãy siêu tăng dài $8$ đơn vị:
$$W = (2,7,11,21,42,89,180,354)$$
Ta có $\text{sum}(W) = 706$ nên ta chọn Modulo $q = 881$.
Tiếp theo chọn $r$ nguyên tố với $q$, ta cho $r = 588$.
Tạo khóa công khai $B$ bằng cách nhân từng phần tử trong $W$ với $r$ rồi lấy modulo $q$ được khóa công khai:
$$B = (295, 592,301,14,28,353,120,236)$$
Giả sử mã hóa văn bản $m = 97 = 01100001_2$, ta nhân bit $1$ của $m$ với index tương ứng của bit $1$ tại $B$ rồi lấy tổng của chúng là được ciphertext $c$:
$$c = 1 \cdot 592 + 1 \cdot 301 + 1\cdot 236 = 1129$$
Để giải mã $c$, ta tính $r' = r^{-1} \mod q = 588^{-1} \mod 881 = 442$
Tiếp theo tính $c' = c \cdot r' \mod q = 1129 \cdot 442 \mod 881 = 372$.
Giờ ta dùng **greedy algorithm** để tìm tập con của $W$ sao cho có tổng là $c'$:
```
c' = 372
w8 = 354 <= 372
c' = 372 - 354 = 18
w3 = 11 <= 18
c' = 18 - 11 = 7
w2 = 7 <= 7
c' = 7 - 7 = 0
```
Vì thế $372 = 354 + 11 + 7 = w_8 + w_3 + w_2$ nên ta được tập $X = (8,3,2)$. Văn bản $m$ của ta sẽ là:
$$m = \sum_{i=1}^{3}2^{n-x_i} = 2^{8-8} + 2^{8-3} + 2^{8-2} = 1+ 32 + 64 = 97$$
#### **Code merkle-hellman:**
```python=
# thuật toán giải mã và mã hóa merkle-hellman do mình nấu
from random import randint
from math import gcd
# tạo W
def generate_private_key(n: int):
W = [randint(1, 100)]
for i in range(n-1):
W.append(sum(W) + randint(1, 100))
q = sum(W) + randint(1, 100)
r = randint(0, q)
while gcd(r, q) != 1:
r = randint(0, q)
return W, q, r
# tạo B
def generate_public_key(private_key: list):
W, q, r = private_key
B = []
for wi in W:
B.append((wi * r) % q)
return B
# mã hóa
def encrypt(plaintext: str, public_key: list):
# chuyển plaintext về bin
bin_pt = "".join([bin(ord(i))[2:].zfill(8) for i in plaintext])
bin_pt = [int(bit) for bit in bin_pt]
C = []
for i in range(0, len(bin_pt), 8):
block = bin_pt[i:i+8]
c = sum(m * b for m, b in zip(block, public_key))
C.append(c)
return C
# giải mã
def decrypt(ciphertext: list, private_key: list):
W, q, r = private_key
r_inverse = pow(r, -1, q)
plaintext = ""
for c in ciphertext:
c_ = (c * r_inverse) % q
bin_plaintext = []
# greedy algorithm
for wi in reversed(W):
if c_ >= wi:
bin_plaintext.append(1)
c_ -= wi
else:
bin_plaintext.append(0)
plaintext += "".join(map(str, bin_plaintext[::-1]))
# chuyển bin về string
plaintext = "".join([chr(int(plaintext[i:i+8], 2)) for i in range(0, len(plaintext), 8)])
return plaintext
private_key = generate_private_key(8)
public_key = generate_public_key(private_key)
plaintext = "abcdefghijklmnopqrstuvwxyz"
ciphertext = encrypt(plaintext, public_key)
print(f"{private_key = }")
print(f"{public_key = }")
print(f"{ciphertext = }")
print("plaintext =", decrypt(ciphertext, private_key))
```
---
### Low-density Subset Sum Problems
- **++Định nghĩa:++ (Subset Sum Problem)** Cho các số nguyên dương $a_1, \dots, a_n$ và một số nguyên $s$, tìm một tập con của $a_i$ mà có tổng là $s$. Nghĩa là: tìm $e_1, \dots,e_n$ với $e_i \in \left\{0,1\right\}$ sao cho:
$$\sum_{i=1}^{n}e_i\cdot a_i = s$$
- **Ví dụ:** cho $a = (11,32,39,54, 98, 101), s = 144$ thì tập $e$ của ta là $e = (1,1,0,0,0,1)$ vì $11+32+101 = 144$.
- Rất nhiều hệ mã dựa trên bài toán tổng tập con đượ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, \dots, a_n$ được định nghĩa như sau:
$$d = \frac{n}{\log_2\text{max}(a_i)}$$
- Thuật toán $\text{LO}$ có thể giải bài toán tổng tập con với $d < 0.6463$ nếu được cho trước một **SVP oracle**. Tương tự, thuật toán $\text{CJLOSS}$ là một phiên bản nâng cấp hơn của thuật toán trên và nó tăng giới hạn $d$ lên $d<0.9408$. Cả hai thuật toán trên đều dựa trên "**giảm cơ sở mạng**" và được cho là khá thực tiễn.
- 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:
$$
\mathbf{B} = \begin{bmatrix} 1 & & & &a_1 \\ &1 & & &a_2 \\ & &\ddots & &\vdots\\ & & &1 &a_n \\ & & & &s \end{bmatrix}
$$
- Khi ta áp dụng LLL với cơ sở trên thì ta sẽ nhận được một vector ngắn có dạng $\mathbf{x}_1 = (e_1, e_2, \dots, 0)$ hoặc sẽ nhận được $-\mathbf{x}_1$.
- Thuật toán $\text{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ố $N > \sqrt{n}$ vào cột cuối và thêm một hàng các giá trị $\frac{1}{2}$ vào hàng cuối cùng như sau:
$$
\mathbf{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}
$$
- Khi ta áp dụng LLL với $B'$ ta được một vector $\mathbf{x}_2 = (e_1 - \frac{1}{2}, e_2-\frac{1}{2}, \dots,e_n -\frac{1}{2}, 0)$ hoặc là $-\mathbf{x}_2$, và ta luôn có $\|\mathbf{x}_2\| = \frac{1}{2}\sqrt{n}$. Xác suất để $\mathbf{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 $\text{max}(a_i) > 2^{c_0 \cdot n}$ tức xác suất $\mathbf{x}_2$ là vector ngắn nhất rất cao thì:
$$\text{max}(a_i) > 2^{c_0 \cdot n}$$
$$\Rightarrow \log_2\text{max}(a_i) > c_0 \cdot n$$
$$\Rightarrow \frac{1}{c_0} > \frac{n}{\log_2\text{max}(a_i)}$$
$$\Rightarrow d < \frac{1}{c_0}$$
$$\Rightarrow d < 0.9408$$
- **Ví dụ:** Cho $(a_1,...,a_6) = (83,59,47,81,76,51), n= 6$ và $s = 291$. Mật độ là $d = \frac{6}{\log_283} = 0.9412$, dù $d$ có cao hơn tiêu chuẩn một xíu nhưng ta vẫn có thể dùng thuật toán $\text{CJLOSS}$ để giải bài toán subnet sum được. Với $N=3$ ta xây dựng một cơ sở sau:
$$
\mathbf{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.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{bmatrix}
$$
- Áp dụng LLL với $\mathbf{B}$ ta được một cơ sở $\mathbf{B'}$ mới như sau:
$$
\mathbf{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 $\mathbf{b}_1 = (b_1,...,b_7) = (-\frac{1}{2}, \frac{1}{2},\frac{1}{2},-\frac{1}{2},-\frac{1}{2},-\frac{1}{2}, 0)$ là vector $\mathbf{x} = (e_1-\frac{1}{2},...,e_6-\frac{1}{2}, 0)$ hoặc có thể là $-\mathbf{x}$, ta khôi phục $e_i$ bằng cách lấy $(b_1 + \frac{1}{2}, …, b_6 + \frac{1}{2})$ nếu là $\mathbf{x}$ và $( -b_1 + \frac{1}{2}, …, -b_6 + \frac{1}{2})$ nếu là $-\mathbf{x}$, ta được:
$$(e_1,e_2,e_3,e_4,e_5,e_6) = (1,0,0,1,1,1)$$
thỏa mãn $\sum_{n=1}^{n}e_i\cdot a_i = s$.
- **Code:**
```python=
from sage.all import *
a = [83, 59, 47, 81, 76, 51]
s = 291
N = 3
M = []
# nhớ thêm QQ vào vì ma trận của ta có 0.5
M = Matrix(QQ, [[1, 0, 0, 0, 0, 0, N * 83],
[0, 1, 0, 0, 0, 0, N * 59],
[0, 0, 1, 0, 0, 0, N * 47],
[0, 0, 0, 1, 0, 0, N * 81],
[0, 0, 0, 0, 1, 0, N * 76],
[0, 0, 0, 0, 0, 1, N * 51],
[0.5, 0.5, 0.5, 0.5, 0.5, 0.5, N * s]])
# có thể code như thế này nếu như gặp ma trận kích thước lớn hơn
# 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)
print(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]
```
### 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, bây giờ ta sẽ mở rộng bài toán đó 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 phép $\mod M$) và **multiple modular** subset sum problem (nhiều $a,s$ và thêm $\mod M$). Ta tiến hành định nghĩa chúng như sau:
- **++Định nghĩa:++ (Multiple Subset Sum Problem):** Cho trước các số nguyên dương $a_{1,1}, a_{1,2},...,a_{k,n}$ và các số nguyên mục tiêu $s_1,s_2,...,s_k$, tìm $e_1, e_2,...,e_n$ với $e_i \in \left\{0,1 \right\}$ sao cho:
$$\displaystyle\sum_{i=1}^{n} e_i \cdot a_{j, i} \ = s_j \hspace{5mm}\forall 1 \leq j \leq k$$
- **++Định nghĩa:++ (Modular Subset Sum Problem):** Cho trước các số nguyên $a_,...,a_n$, một số nguyên $s$ và một Modulus $M$, tìm $e_1,...,e_n$ với $e_i \in \left\{0,1 \right\}$ sao cho:
$$\displaystyle\sum_{i=1}^{n} e_i \cdot a_{i} \ \equiv s \pmod M$$
- **++Định nghĩa:++ (Multiple Modular Subset Sum Problem):** Cho trước các số nguyên dương $a_{1,1}, a_{1,2},...,a_{k,n}$, các số nguyên mục tiêu $s_1,s_2,...,s_k$ và một Modulus $M$, tìm $e_1, e_2,...,e_n$ với $e_i \in \left\{0,1 \right\}$ sao cho:
$$\displaystyle\sum_{i=1}^{n} e_i \cdot a_{j, i} \ \equiv s_j \pmod M \hspace{5mm} \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\text{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 mình rằng **Multiple subset sum problem** có thể được giải với giới hạn $d < 0.9408$ bằng cách sử dụng giảm mạng Lattice với cơ sở $\mathbf{B}$ sau:
$$
\mathbf{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ự như trước đây, áp dụng LLL ta có thể nhận được một vector dạng $\mathbf{x} = (e_1 − \frac12 , . . . , e_n − \frac12 , −\frac12 , 0, . . . , 0)$ hoặc $-\mathbf{x}$.
- Còn với 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ở $\mathbf{B'}$ dưới đây:
$$
\mathbf{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}
$$
- Áp dụng LLL ta sẽ được một vector ngắn dạng:
$$\mathbf{x} = (e_1 − \frac12 , . . . . , e_n − \frac12 , −\frac12 , 0 , . .. , 0)$$
hoặc có thể là $-\mathbf{x}$ :hear_no_evil:
---
## Hidden Number Problem
The hidden number problem (**HNP**) hay bài toán tìm số bị dấ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$. Trong phần này chúng ta sẽ tìm hiểu sơ qua về bài toán **HNP** và cách dùng LLL để giải nó.
Công thức ban đầu của **HNP** là để tìm một số nguyên bí mật $\alpha$ modulo một số nguyên tố $p$ khi được cho trước **msb** của $t_i \cdot \alpha \mod p$ với $t_i$ là các số đã 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à co $\alpha \in [1, p-1]$ là số bí mật. Yêu cầu 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$ nào đó bé hơn $p$.
> Có **hai** cách để giải bài toán trên đó là chuyển nó về bài toán **CVP** và cách thứ hai là chuyển về bài toán **SVP**.
- **++Cách 1:++** 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ở $\mathbf{B}$ như sau:
$$
\mathbf{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 **HNP** là $\beta_i + a_i = t_i \alpha + k_ip$, ta thấy rằng tổ hợp tuyến tính $\mathbf{x} = (k_1,...,k_m, \alpha)$ sẽ tạo ra một vector $\mathbf{xB} = (β_1 + a_1, . . . , β_m + a_m, α/p)$. Định nghĩa hai vector $\mathbf{t} = (a_1, \dots, a_m, 0), \mathbf{u} = (\beta_1, \dots, \beta_m, \alpha/p)$, ta có được $\mathbf{xB-t = u}$ với $\mathbf{u} \leq \sqrt{m+1}\cdot B$, mà đị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ị $\mathbf{u}$, có $\mathbf{u}$ thì ta nhân $p$ với tham số cuối cùng của nó ($\alpha/p$) là có được $\alpha$.
- **++Cách 2:++** Ta chuyển sang hướng tiếp cận **SVP**, đặt ma trận cơ sở $\mathbf{B'}$ như sau:
$$
\mathbf{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 tạo từ cơ sở này sẽ chứa vector $\mathbf{u'} = (β_1, . . . , β_m, αB/p, −B)$ được tạo nên từ tổ hợp tuyến tính $(k_1, …, k_m, \alpha, -1)$. 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 $(-t_1,...,-t_m,p,0)$, nên $\mathbf{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.
> Người ta chứng minh rằng hướng giải **SVP** sử dụng **Kannan's embeding** hiệu quả hơn so với hướng tiếp cận **CVP** nên ví dụ dưới đây ta sẽ sử dụng hướng tiếp cận **SVP** để giải bài toán **HNP**.
- **Ví dụ:** Cho $p = 401$ và $(t_1,t_2,t_3) = (143,293,304)$, ta sẽ sử dụng hướng tiếp cận **SVP** để tìm ra số bị dấu $\alpha = 309$. Giả sử chúng ta được cho $\beta_i - t_i \alpha + a_i \equiv 0 \pmod p$ với $i \in \left\{1,2,3 \right\}$, $(a_1,a_2,a_3) = (62, 300, 86)$ và $\beta_i < B = 20$. Ta xây dựng được một cơ sở Lattice $\mathbf{B}$ sau:
$$
\mathbf{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ở mới $\mathbf{B'}$ như sau:
$$
\mathbf{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ư dự đoán thì vector $(0, 0, 0, B, 0)$ là vector ngắn nhất nên nó sẽ nằm đầu tiên. Với lý thuyết đã nhắc ở trên thì vector ta tìm kiếm sẽ có dạng $\mathbf{u}=(β_1, . . . , β_m, αB/p, −B)$, nhưng nhìn sơ qua thì có vẻ không có vector nào của cơ sở mới giống như thế.
- Tuy nhiên vector $-\mathbf{u}$ thì **có** xuất hiện trong cơ sở trên, nó chính là vector **thứ hai** vì độ lớn của các hệ số $(\beta_1,\beta_2,\beta_3) = (15,12,16) < B = 20$. Ta chỉ có $-\mathbf{u}$ nhưng $\|-\mathbf{u}\| =\| \mathbf{u} \|$ nên có thể xem chúng là một và có thể sử dụng $-\mathbf{u}$ để khôi phục giá trị của $\alpha$ như thế này: $$-(\frac{1840}{401}) \cdot \frac{p}B \mod p = -92 \mod 401 = 309 = \alpha$$
- **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]
])
print(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]
```
---
# IV. 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 $2/3$ của Plaintext đã bị lộ.
Cho $N$ là một Modulus, $e$ là một số mũ **nhỏ** và $c \equiv m^e \pmod N$ là công thức Ciphertext của Plaintext $m$. Giả sử $m$ có dạng $m = m'+x_0$. Nếu $x_0$ đủ nhỏ, ta có thể viết lại công thức của $c$ thành một bài toán 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$$
$$\Rightarrow c \equiv (m' + x_0) ^e \pmod N$$
$$\Rightarrow (m' + x_0)^e - c \equiv 0 \pmod N$$
Viết lại $f(x) \equiv (m' + x_0)^e - c \pmod N$, chúng ta có $f(x)$ là 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 để giải được $x$ ra $x_0$ Với điều kiện:
<span style="font-size:1.3em; text-align:center">$$|x_0| \leq \frac{1}{2}N^{\frac{1}{e}}$$</span>
Trong trường hợp $e=3$, phương trình $f(x)$ có thể giải được nếu ta đã biết trước $2/3$ Plaintext.
**++Ví dụ 1:++** Ta có một số thông tin như sau:
```
N = 318110533564846846327681562969806306267050757360741
e = 3
m = "my secret pin is XXXX"
c = 312332738778608882264230787188876936416561274050341 #c = pow(m, e, N)
```
- Với `XXXX` là một mã pin gồm $4$ ký tự.
- Vì chúng ta biết một phần của Plaintext $m$, ta có thể viết nó lại thành $m = m' + x_0$ với $m'$ là đoạn đã biết, $x_0$ là đoạn ta cần tìm. Ta có được $m'$ sẽ là giá trị của đoạn `my secret pin is \x00\x00\x00\x00`.
- Vì $|x_0| < 2^{32}$, đây là một nghiệm nhỏ khi so sánh với kích thước của $N$, vì thế ta hoàn toàn có thể khôi phục được nó nhờ **Coppersmith's method**.
- Ta đặt phương trình $f(x)$ là:
$$f(x) \equiv (m' + x_0)^e - c \pmod N$$
- **Script:**
```python=
from sage.all import *
from Crypto.Util.number import *
N = 318110533564846846327681562969806306267050757360741
e = 3
m_ = int.from_bytes(b"my secret pin is \x00\x00\x00\x00", byteorder="big")
c = 312332738778608882264230787188876936416561274050341
# tạo biến x trên vành N
x = PolynomialRing(Zmod(N), "x").gen()
f = (m_ + x)**e - c
# X là giới hạn của số cần tìm
x0 = f.small_roots(X = 256**4)
print(f"{x0 = }")
print(f(x0) % N)
# 825439031
```
- Ta tìm được $x_0 = 825439031$, đổi nó sang bytes, ta được mã pin là `"1337"`.
---
Với các Challenge sử dụng số lớn, ta cần phải truyền giá trị `epsilon` hay $\epsilon$ một cách phù hợp, không cần truyền `beta` nên `small_roots()` sẽ mặc định $\beta = 1$. Với $X$ là giá trị ta cần tìm, $\delta$ là bậc của đa thức, $N$ là modulus, ta cần phải truyền $\epsilon$ sao cho:
<span style="font-size:1.2em; text-align:center">$$X \leq N^{\frac{1}{\delta} - \epsilon}$$</span>
**++Ví dụ 2:++** KMACTF 2023: **Similar But …**
```python=
from Crypto.Util.number import *
p = getPrime(2048)
q = getPrime(2048)
n = p*q
e = 2
print(f'{n = }')
flag = "KMA{anh che roi!!!!!!!}"
l = len(flag)
print(f'{l = }')
msg = f'''
Gửi đến những người em thân yêu của anh, hôm nay anh muốn chia sẻ với các em một câu chuyện về kho báu.
Trong câu chuyện này, kho báu được chia thành hai nửa, và mỗi nửa mang trong mình một ý nghĩa đặc biệt.
Nửa đầu tiên anh giấu ở đây: {flag[:l//2]}
Còn đây là nửa thứ hai: {flag[l//2:]}
Hãy tìm ra kho báu của anh đi, anh để hết trong msg rồi đó.
Chúc các em may mắn !!!
'''
c = pow(bytes_to_long(msg.encode()), e,n)
print(f'{c = }')
# n = 284195696721751741542976970377246384163200746062783759329661617188815436776424189078521874168074640320924439097731870753354899953210403298438375686437215681238598996375382536537768278254146374135440697791835320902172928838535170207920563260188268857178412014945665843067884706362429213081345697201062048319151146709862154724701120787598264599428501030945241764332469820283330386978451487308358496070493019375227430237712951734594609189071738774562063639368050519599690219339371888693892756654714125742546793650545564645761412676393745546867317157950660276413454704121923686068169935524575099441009254762051678974615084672006274688302115077734407074204036930371634952480748870905140950407665202776686680232626404222734370828402377048157739018826752500816695651244608931659579045297636939347065142654266415418100162785201594053030962306454285243690682313810711305540434910861763618201288903763117959626276874769295456013747611282355250494278056557319959998777444026981083893016148032869660521587008308779834135343779295437340050873017686606894792594175473683376016830206421076702465312246840917660142641545140295983913838540847955749716541937276104901379735588334581049297927341758018775135576856481243743641314705618868934645861372761
# l = 46
# c = 197348052174145638785229215457497516691585910055835441125583073645980013777032065006627024581136020897300252228534006100306209234223154204281916399887451961006595700453576912583653484661863741375270305419615721406198781214515934675523007505165820308082654403780811498250984535336719680589351485735567955825720119048693747519278867766555710216038040229689357846375187513096350835998852728799656866437148777620905204000517049701112204778019184506339386241329691058153055354968087261832501249138236077313408204182929051641521267083356295624561257562991234261668632037087231724232716833294744291699334965334803826200727633700589654688863746449952492047286765973034494755978048670534899135052018421945310658805856492088479095070115314198579191182336314746398558742288499341372595578846975164079893641205584309595266932028754927985671375042116891444819656916960144209962788439147210122667753145683940192069926363191913583924164601419393905729897192079336412469978182139715148777895764888053578167383521367586833983484951931519842177634434322107919818397921097644416813823140565831649561406124639176188646350960425853516784830094432718779747088309513889971075211757981041043652016970888838329334179083984287540371718185534696012444989603691
```
:::spoiler Solution
```python=
from sage.all import *
from Crypto.Util.number import *
from hashlib import sha512
n =
l = 46
e = 2
c =
# chuỗi tiếng việt ở Source tương ứng với chuỗi này, chuỗi này cũng được thêm 46 bytes \x00
msg = b'\nG\xe1\xbb\xadi \xc4\x91\xe1\xba\xbfn nh\xe1\xbb\xafng ng\xc6\xb0\xe1\xbb\x9di em th\xc3\xa2n y\xc3\xaau c\xe1\xbb\xa7a anh, h\xc3\xb4m nay anh mu\xe1\xbb\x91n chia s\xe1\xba\xbb v\xe1\xbb\x9bi c\xc3\xa1c em m\xe1\xbb\x99t c\xc3\xa2u chuy\xe1\xbb\x87n v\xe1\xbb\x81 kho b\xc3\xa1u. \nTrong c\xc3\xa2u chuy\xe1\xbb\x87n n\xc3\xa0y, kho b\xc3\xa1u \xc4\x91\xc6\xb0\xe1\xbb\xa3c chia th\xc3\xa0nh hai n\xe1\xbb\xada, v\xc3\xa0 m\xe1\xbb\x97i n\xe1\xbb\xada mang trong m\xc3\xacnh m\xe1\xbb\x99t \xc3\xbd ngh\xc4\xa9a \xc4\x91\xe1\xba\xb7c bi\xe1\xbb\x87t.\nN\xe1\xbb\xada \xc4\x91\xe1\xba\xa7u ti\xc3\xaan anh gi\xe1\xba\xa5u \xe1\xbb\x9f \xc4\x91\xc3\xa2y: \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\nC\xc3\xb2n \xc4\x91\xc3\xa2y l\xc3\xa0 n\xe1\xbb\xada th\xe1\xbb\xa9 hai: \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\nH\xc3\xa3y t\xc3\xacm ra kho b\xc3\xa1u c\xe1\xbb\xa7a anh \xc4\x91i, anh \xc4\x91\xe1\xbb\x83 h\xe1\xba\xbft trong msg r\xe1\xbb\x93i \xc4\x91\xc3\xb3.\nCh\xc3\xbac c\xc3\xa1c em may m\xe1\xba\xafn !!!\n'
msg0 = msg[:308]
msg1 = msg[308: 387]
msg2 = msg[387:]
assert sha512(msg).hexdigest() == sha512(msg0 + msg1 + msg2).hexdigest()
x = PolynomialRing(Zmod(n), "x").gen()
f = (bytes_to_long(msg0 + msg1) * 2**(8 * len(msg2)) + bytes_to_long(msg2) + x*2**(8 * len(msg2)))**e - c
f = f.monic()
# beta = 1, epsilon < 0.35
flag = int(f.small_roots(X = 2**(8 * len(msg1)), epsilon = 0.35)[0])
print(long_to_bytes(flag)[:23] + long_to_bytes(flag)[-23:])
# KMA{So_litttt_c0pp33r_Sm1th_Savageeeee!!!!!!!}
```
:::
---
## Factoring with high bits known
Trong phần này, ta sẽ tìm hiểu cách sử dụng Lattice để có thể factor được modulus $N$ của RSA nếu như được biết trước một lượng bit liên tiếp đủ lớn của một trong số các số nguyên tố tạo nên $N$. [link](https://eprint.iacr.org/2020/1506.pdf)
Cho $N=p\times q$ là một Modulus RSA với bitsize của $p$ = bitsize $q$.
Giả sử ta biết được một lượng lớn các significant bit $b$ của $p$, sao cho $p = a + r$, chúng ta chưa biết $r$ nhưng biết rằng $a = 2^l \times b$ với $l$ là số bit bị mất.
Để tìm được $r$, ta biến đổi $p$ thành phương trình $f(x) = p = a+x \equiv 0 \pmod p$. Ta không biết $p$ nhưng biết $p|N$ và biết rằng $|r| < R$ với một giới hạn $R$ nào đó nhỏ hơn $N$. Ta thiết lập một cơ sở như sau:
$$
B =
\begin {bmatrix}
R^2 & Ra & 0 \\
0 & R & a \\
0 & 0 & N
\end {bmatrix}
$$
Sau khi áp dụng thuật toán LLL với cơ sở trên, ta được một vector ngắn nhất có dạng:
$$v = (v_2R^2, v_1R, v_0)$$
Từ $v$ ta thiết lập được một đa thức như sau:
$$f(x) = v_2x^2 + v_1x + v_0$$
Giải phương trình $f(x) = 0$ trên tập số nguyên ta sẽ được nghiệm $x = r$ thỏa mãn $f(r) = a + r \equiv 0 \pmod p$
> Cơ sở Lattice $3\times 3$ trên có thể hoạt động với bất kỳ $|r| < p^{1/3}$ nào, và nó có thể khôi phục được $170$ bit bị mất của $p$ dài $512$ bit, $341$ bit bị mất của $p$ dài $1024$ bit.
++**Ví dụ 1:**++ Cho các thông số là $N$ và $a$ như sau, yêu cầu khôi phục lại giá trị $p$, biết rằng $a = 2^{30}\cdot b$:
```python!
N = 0x4d14933399708b4a5276373cb5b756f312f023c43d60b323ba24cee670f5
a = 0x68323401cb3a10959e7bfdc0000000
```
- Đặt $R = 2^{30}$, ta thiết lập một một cơ sở $M$ như sau:
$$
M =
\begin {bmatrix}
R^2 & Ra & 0 \\
0 & R & a \\
0 & 0 & N
\end {bmatrix}
$$
- Áp dụng LLL với cơ sở trên, ta được một vector có dạng:
$$v = (v_2R^2, v_1R, v_0)$$
```python!
v = (-1589470870676 * R^2, -8713867990575925977473 * R, 77331120627754853095042030173)
```
- Tiến hành thiết lập đa thức:
$$f(x) = v_2x^2 + v_1x + v_0$$
- Giải $f(x) = 0$ ta được $x = 8860169$.
- **Script:**
```python!
from sage.all import *
N = 0x4d14933399708b4a5276373cb5b756f312f023c43d60b323ba24cee670f5
a = 0x68323401cb3a10959e7bfdc0000000
R = 2**30
M = Matrix([[R**2, R*a, 0],
[0, R, a],
[0, 0, N]])
M = M.LLL()
# [ -1832535147748529008013817675776 -9356444510296209569540841930752 77331120627754853095042030173]
# [ 125465963356050137550933687533568 -23665155082317389734684846456832 186734182252719079109663356819]
# [ 92002922975771047388767823331328 4455311849740456949966438282559488 540980344135723641720389670447626517]
# chưa viết cái nào có dạng (v2 * R^2, v1 * R, v0) nên ta sẽ dùng for chạy qua hết
for coeffiction in M:
v2, v1, v0 = coeffiction
x = PolynomialRing(ZZ, "x").gen()
f = (v2 // R**2) * x**2 + (v1 // R) * x + v0
# giải f(x) = 0
r = f.roots()
if r:
p = a + int(r[0][0])
assert N % p == 0
print(f"{p = }")
# p = 541017114187426553022141142812537353
```
- Có thể dùng phương thức `.small_roots()` của **sage** để giải, nhưng chúng ta phải truyền các tham số `X, beta, epsilon` một cách hợp lý, với bài này số nhỏ nên ta chỉ cần truyền `X, beta` thôi:
```python!
from sage.all import *
N = 0x4d14933399708b4a5276373cb5b756f312f023c43d60b323ba24cee670f5
a = 0x68323401cb3a10959e7bfdc0000000
x = PolynomialRing(Zmod(N), "x").gen()
f = a + x
beta = (120 - 1)/(N.bit_length()) #120 là bit của p
# 0.49
print(f.small_roots(X = 2**30, beta = beta))
# 8860169
```
++**Ví dụ 2:**++ Ta có một Challenge như sau:
```python=
from Crypto.Util.number import *
p = getPrime(1024)
q = getPrime(1024)
N = p * q
p_200 = p >> 200
e = 0x10001
m = bytes_to_long(b"Flag{??????????????????????????????????}")
c = pow(m, e, N)
print(f"{N = }")
print(f"{p_200 = }")
print(f"{c = }")
# N = 14924791356855268716763277466848462439196532957376415007713766861497645327210542584120644547673073574173842472377777755309744220581265721682661854085804741672313385149484550155768107297340492182166127335026498596185861404961100962828287658099470786015613853818103886316909495018945229361548661038375421870976935169965208255357997446301856436985418140354292031641916577735174993727872981003832697803361994094859814551961246282634888906942020960881102601809591104539762791550344854920593843539008794481137949232786953517621458184532256323174695362728131981528186733748130289550062069755820732012453626649715946180584697
# p_200 = 63382634170067990365271805195176232487959140685857837865519911829508942933068983888840496588141216306176800966954258511355009662680916005412008827856710134150628943052969076715498026083307593642492890106883416862749228481397958018487673301620219250
# c = 14406732481051783557643637462770756489084204247553435097359819147772009730614678151163490445537864908740499056123250153176111766250016229534811278320388332783698890104005917638150934173926633311618748906233407916112622487230200721671649791239559259906005576585218425301779082643290000469669904057232477546779219911828771693638431441222853556143208190588378624018968388739812216050918145946993605300621035748475638135599936298422788726850028212990650345844311073689464701746054634214776533254289263219139624883593061501114547853480092187101049755584227080944725060148898135644230744898829177635334276927150821109246382
```
- $p$ của ta dài $1024$ bit bị dịch phải mất $200$ bit, chỉ còn giữ lại $824$ **msb** mà thôi, vì chỉ mất $200$ bit nên ta hoàn toàn có thể dùng lý thuyết đã học bên trên để khôi phục lại nó.
- Giá trị $a$ của ta sẽ là $p_{200} \cdot 2^{200}$ và $r$ sẽ là $200$ bit mà ta cần tìm, ta có hai cách giải như sau:
- **Cách 1:** Tự thiết lập cơ sở Lattice.
```python!
from sage.all import *
from Crypto.Util.number import long_to_bytes
N =
p_200 =
p_ = p_200 * 2**200
e = 0x10001
R = 2**200
M = Matrix([[R**2, R*p_, 0],
[0, R, p_],
[0, 0, N]]).LLL()
for coeffiction in M:
a, b, c = coeffiction
x = PolynomialRing(ZZ, "x").gen()
f = (a // R**2) * x**2 + (b // R) * x + c
roots = f.roots()
if roots:
p = p_ + int(roots[0][0])
assert N % p == 0
print(f"{p = }")
# p = 101851966193232105672862010794989144815507095330743970735255353226695070316639067427899924043779127962880974382671870356643050565849761175343465638138458493269280954814950372642647501307209116528908538858928574310752657212798046821269630160126324263930422665834878142999501973074183600289190137281216953127573
```
- **Cách 2:** Sử dụng `small_roots()`.
```python!
from sage.all import *
N =
p_200 =
p_ = p_200 * 2**200
x = PolynomialRing(Zmod(N), "x").gen()
f = p_ + x
beta = (1024-1)/(N.bit_length()) #1024 là bit của p
# 0.499
x = f.small_roots(X = 2**200, beta = beta)[0]
p = p_ + int(x)
assert N % p == 0
print(f"{p = }")
#p = 101851966193232105672862010794989144815507095330743970735255353226695070316639067427899924043779127962880974382671870356643050565849761175343465638138458493269280954814950372642647501307209116528908538858928574310752657212798046821269630160126324263930422665834878142999501973074183600289190137281216953127573
```
---
# V. CryptoHack Challenges
<img style="display: block; margin: auto;" width="400" src="https://hackmd.io/_uploads/BJWVBmg31e.png"/>
Vì đã đến giới hạn của **HackMD** nên mình sẽ viết **write up** các challenge mình giải được ở link **này**.
# END
>12/3/2025
Sign in with Wallet
Connect another wallet