[TOC]
# Qui ước
Các kí hiệu: Các vector với các phần tử trong $\displaystyle \mathbb{R}$ được xem như là vector cột và được biểu thị bằng các chữ in thường đậm, ví dụ $\displaystyle \mathbf{x} ,\mathbf{y} ,\mathbf{z}$. Các ma trận được biểu thị bằng các chữ cái in hoa đậm, ví dụ $\displaystyle \mathbf{A} ,\mathbf{S} ,\mathbf{B} ,...$
Chuyển vị của một vector hoặc ma trận được biểu thị bằng $\displaystyle \mathbf{v}^{T}$ hoặc $\displaystyle \mathbf{V}^{T}$ tương ứng. Ngoài ra, chúng ta biểu thị tích trong của hai vector cột $\displaystyle \mathbf{v} ,\mathbf{w} \in \mathbb{R}^{n}$ theo $\displaystyle \langle \mathbf{v} ,\mathbf{w} \rangle =\mathbf{v}^{T}\mathbf{w}$.
Một số kí hiệu khác:
- $\displaystyle \mathbb{R}^{n\times m}$: không gian của ma trận $\displaystyle n\times m$ với các mục số thực
- $\displaystyle \| \cdotp \| ,\ \| \cdotp \| _{\infty }$: Chuẩn Euclid và chuẩn tối đa
- $\displaystyle \mathcal{L}$: Một lưới
- $\displaystyle \mathcal{L}(\mathbf{B})$: lưới với các cột của ma trận $\displaystyle \mathbf{B}$ làm cơ sở.
- $\displaystyle \lambda _{i}(\mathcal{L})$: Số nhỏ nhất sao cho có $\displaystyle i$ vector độc lập tuyến tính trong $\displaystyle \mathcal{L}$ mà mỗi vector đó có chuẩn không vượt quá $\displaystyle \lambda _{i}$.
- $\displaystyle \gamma$ : Hệ số xấp xỉ (gần đúng) trong các bài toán lưới
- $\displaystyle \mathbf{b}_{i}$: một vector cơ sở lưới
- $\displaystyle \mathbf{b}_{i}^{*}$: một vector trong cơ sở trực giao Gram-Schmidt của một lưới.
## Nhắc lại một số định nghĩa
Một lattice ${\displaystyle \mathcal{L} \subset \mathbb{R}^{m}}$ là một không gian vector được sinh bởi các tổ hợp tuyến tính nguyên của các vector độc lập tuyến tính. Tức là
\begin{equation*}
\mathcal{L} =\left\{\sum _{i=1}^{n} x_{i}\mathbf{b}_{i} \ \middle| x_{i} \in \mathbb{Z}\right\}
\end{equation*}
trong đó $\displaystyle \{\mathbf{b}_{i}\}_{i=1}^{n} \subset \mathbb{R}^{m}$. Đặt $\displaystyle \mathbf{B} \in \mathbb{R}^{m\times n}$ thì $\displaystyle \mathcal{L} =\mathbf{B}\mathbb{Z}^{n}$, đồng nghĩa với việc $\displaystyle \mathcal{L}$ là ảnh của $\displaystyle \mathbb{Z}^{n}$ dưới ánh xạ tuyến tính $\displaystyle \mathbf{B} :\mathbb{R}^{n}\rightarrow \mathbb{R}^{m}$.
Ta có thể định nghĩa lưới theo một cách khác. Cho $\displaystyle m,n,k\in \mathbb{Z}_{ >0}$ với $\displaystyle m\geqslant k$. Một lưới $\displaystyle m$ chiều $\displaystyle \mathcal{L}$ là một nhóm con cộng rời rạc của $\displaystyle \mathbb{R}^{m}$ chứa tất cả các tổ hợp tuyến tính nguyên của $\displaystyle k$ vector độc lập tuyến tính $\displaystyle \{\mathbf{b}_{1} ,\mathbf{b}_{2} ,...,\mathbf{b}_{k}\}$. Đó là $\displaystyle \mathcal{L} =\left\{\mathbf{Bx} \ |\ \mathbf{x} \in \mathbb{Z}^{k}\right\}$ với ma trận $\displaystyle \mathbf{B} =(\mathbf{b}_{1} ,...,\mathbf{b}_{k}) \in \mathbb{R}^{m\times k}$. Ta gọi $\displaystyle \mathbf{B}$ là cơ sở của $\displaystyle \mathcal{L}$ và $\displaystyle k$ là rank của lưới. Sau này ta chỉ quan tâm tới các full rank lattice tức là các lattice có hạng bằng với số chiều.
Định thức của một lưới $\displaystyle \mathcal{L}$ với cơ sở $\displaystyle \mathbf{B}$ được xác định bởi $\displaystyle \det(\mathcal{L}) =\sqrt{| \det\left(\mathbf{B}^{T}\mathbf{B}\right)| }$. Nếu lattice $\displaystyle \mathcal{L}$ là full rank thì $\displaystyle \det(\mathcal{L}) =| \det(\mathbf{B})|$.
Lưu ý rằng cơ sở của một lưới không là duy nhất, hay nói đúng hơn với mỗi ma trận đơn nhất $\displaystyle \mathbf{U} \in \mathbb{Z}^{n\times n}$ thì $\displaystyle \mathbf{BU}$ cũng là cơ sở cho cùng một lưới. Vì ta có tính chất sau: Với hai cơ sở $\displaystyle \mathbf{B}$ và $\displaystyle \mathbf{B} '$ cho lưới $\displaystyle \mathcal{L}$ thì $\displaystyle \mathcal{L}(\mathbf{B}) =\mathcal{L}(\mathbf{B} ')$ cho nên suy ra $\displaystyle \det(\mathbf{B}) =\det(\mathbf{B} ')$.
Một ma trận đơn nhất $\displaystyle \mathbf{U}$ là một ma trận thỏa mãn $\displaystyle \det(\mathbf{U}) =1$. Như vậy nếu ta lấy $\displaystyle \mathbf{B} '=\mathbf{BU}$ thì sẽ thỏa mãn định thức hai ma trận trên là như nhau.
Tính chất trên tuy đơn giản nhưng rất quan trọng đối với việc triển khai các hệ mật, vì một số cơ sở dễ xử lí hơn những cơ sở khác.
Mỗi lưới $\displaystyle \mathcal{L}$ có một lưới đối ngẫu (dual lattice), kí hiệu $\displaystyle \mathcal{L}^{*} =\left\{\mathbf{w} \in \mathbb{R}^{m} \ \middle| \ \langle \mathbf{w} ,\mathbf{x} \rangle \in \mathbb{Z} ,\ \forall \mathbf{x} \in \mathcal{L}\right\}$.
# Các bài toán khó
**Bài toán tìm vector ngắn nhất - SVP** : Cho một cơ sở tùy ý $\displaystyle \mathbf{B}$ của một lưới $\displaystyle \mathcal{L}$ có số chiều $\displaystyle m$, hãy tìm một $\displaystyle x\in \mathcal{L}$ khác không với $\displaystyle \| x\| \leqslant \gamma ( m) \lambda _{1}(\mathcal{L})$
Trong đó $\displaystyle \lambda _{1}(\mathcal{L})$ là độ dài cực tiểu thứ nhất của lưới $\displaystyle \mathcal{L}$ (first successive minimum). Mà theo định lí thứ nhất của Minkowski thì với một full rank lattice $\displaystyle \mathcal{L}$ với rank là $\displaystyle n$ thì
\begin{equation*}
\lambda _{1}(\mathcal{L}) \leqslant \sqrt{n} \mid \det(\mathcal{L}) \mid ^{1/n}
\end{equation*}
Hiểu một cách trực quan: $\displaystyle \lambda _{i}(\mathcal{L})$ là bán kính của một quả cầu có tâm tại gốc tọa độ sao cho trong quả cầu đó tồn tại $\displaystyle i$ vector độc lập tuyến tính.
Biến thể của bài SVP là bài uSVP là tìm vector ngắn nhất và duy nhất.
**Bài toán vector gần nhất - CVP**: Cho một cơ sở tùy ý $\displaystyle \mathbf{B}$ của một lưới $\displaystyle \mathcal{L} =\mathcal{L}(\mathbf{B})$ và một vector đích $\displaystyle \mathbf{t}$ (không nhất thiết thuộc vào $\displaystyle \mathcal{L}$). Tìm một vector $\displaystyle \mathbf{v}$ thuộc lưới sao cho $\displaystyle \| \mathbf{v} -\mathbf{t} \| =\min_{\mathbf{w} \in \mathcal{L}} \| \mathbf{w} -\mathbf{t} \|$.
# Các thuật toán rút gọn lưới
Các thuật toán rút gọn lưới nhằm mục đích lấy một cơ sở đưa ra của một lưới và biến đổi nó thành một cơ sở khác cho cùng lưới nhưng với các vector ngắn hơn và trực giao hơn. Bằng cách này, một vector lưới ngắn có thể được khôi phục. Các thuật toán thường không được thiết kế để tìm chính xác, mà là để trích xuất một vector ngắn trong một số yếu tố gần đúng, nói cách khác là để giải một số bài toán lưới khó gần đúng.
## Thuật toán Gram-Schmidt
Hai vector $\displaystyle \mathbf{u} ,\mathbf{v}$ được gọi là trực giao nếu như tích trong của chúng bằng 0 tức là $\displaystyle \langle \mathbf{u} ,\mathbf{v} \rangle =0$. \ Một hệ các vector $\displaystyle \mathbf{S} =(\mathbf{v}_{1} ,...,\mathbf{v}_{n})$ được gọi là một hệ trực giao nếu như chúng đôi một trực giao. Tương tự, một hệ trực giao các vector đơn vị được gọi là một hệ trực chuẩn.
Ta có thể chứng minh rằng mọi hệ trực chuẩn đều độc lập tuyến tính.
Định lí: Cho $\displaystyle \mathbf{S} =(\mathbf{v}_{1} ,...,\mathbf{v}_{n})$ là một hệ các vector độc lập tuyến tính của không gian Euclid $\displaystyle V$. Khi đó ta có thể tìm được một hệ trực chuẩn $\displaystyle \mathbf{S} '=(\mathbf{u}_{1} ,...,\mathbf{u}_{n})$ sao cho
\begin{equation*}
span\{\mathbf{v}_{1} ,..,\mathbf{v}_{k}\} =span\{\mathbf{u}_{1} ,...,\mathbf{u}_{k}\} ,\forall k=1,...,n
\end{equation*}
Để xây dựng một hệ trực chuẩn thì trước hết ta sẽ xây dựng một hệ trực giao rồi lấy từng vector chia cho chuẩn của chính nó.
```python
from sage.all import *
def gram_schmidt(vectors):
orthogonal_vectors = []
for v in vectors:
for u in orthogonal_vectors:
v -= (v * u) / (u * u) * u
orthogonal_vectors.append(v)
return orthogonal_vectors
v1 = vector([4, 1, 3, -1])
v2 = vector([2, 1, -3, 4])
v3 = vector([1, 0, -2, 7])
v4 = vector([6, 2, 9, -5])
v = [v1,v2,v3,v4]
output = gram_schmidt(v)
print(output)
```
## Thuật toán LLL
Thuật toán rút gọn lưới đầu tiên là LLL. Mục tiêu của thuật toán LLL là tìm ra một cơ sở $\displaystyle \mathbf{b}_{i}$ của lưới sao cho các vector Gram-Schmidt $\displaystyle \mathbf{b}_{i}^{*}$ không quá giảm về kích thước. Cụ thể, với $\displaystyle \delta \in ( 1/4,1)$ ta gọi một cơ sở $\displaystyle \mathbf{B} =\{\mathbf{b}_{1} ,...,\mathbf{b}_{n}\}$ là một cơ sở rút gọn $\displaystyle \delta -LLL$ nếu như
1. $\displaystyle | \mu _{i,j} | \leqslant \frac{1}{2}$ với mọi $\displaystyle 1\leqslant j< i$.
2. $\displaystyle \left( \delta -\mu _{i+1,i}^{2}\right) \| \mathbf{b}_{i}^{*} \| ^{2} \leqslant \| \mathbf{b}_{i+1}^{*} \| ^{2} ,\forall 1\leqslant i\leqslant n-1$.
Mọi người có thể xem implement của key-moon tại đây https://github.com/key-moon/pylll/blob/main/pylll/lll.py
**Cài đặt flatter** Tham khảo tại link sau https://github.com/keeganryan/flatter.
Để cài thì đầu tiên cần clone repo về terminal của mình
`git clone https://github.com/keeganryan/flatter`.
Tool được build bằng cmake nên cần cài thêm như sau
```
sudo apt update
sudo apt install build-essential cmake
```
Tiếp theo tạo một thư mục build và chạy cmake
```
mkdir build
cd build
cmake ..
```
Mình gặp một cái lỗi như này
Lỗi này là do ta chưa cài Eigen, một dependency cần có để build `flatter`.
Tải nốt bằng lệnh sau:
```
sudo apt install libeigen3-dev
```
Rồi sau đó chạy lại toàn bộ quá trình một lần nữa
```
cd ~/flatter/build
cmake ..
make -j$(nproc)
```
Mọi người thấy thông báo như này hiện ra thì coi như oke
```
-- Found FPLLL: /usr/include (found suitable version "5.4.1", minimum required is "5.1.0")
-- Configuring done
-- Generating done
-- Build files have been written to: /home/duc112006/flatter/build
```
Cuối cùng là sao chép file thực thi vào `/usr/local/bin` để chạy trong VSCode
```
duc112006@LAPTOP-VB45ARKK:~/flatter/build$ sudo cp bin/flatter /usr/local/bin/flatter
duc112006@LAPTOP-VB45ARKK:~/flatter/build$ which flatter
/usr/local/bin/flatter
duc112006@LAPTOP-VB45ARKK:~/flatter/build$
```
Test:
```python
from sage.all import *
from Crypto.Util.number import *
def flatter(M):
import re
from subprocess import check_output
# compile https://github.com/keeganryan/flatter and put it in $PATH
z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
ret = check_output(["flatter"], input=z.encode())
return matrix(M.nrows(), M.ncols(), list(map(int, re.findall(b"-?\\d+", ret))))
M = [[-2, 2], [-2, 1]]
M = Matrix(ZZ, M)
M = M.transpose()
M = flatter(M)
print(M)
M = [[-2, 2], [-2, 1]]
M = Matrix(ZZ, M)
m = M.transpose()
print(m.LLL())
```
**Lưu ý:** Do thuật toán LLL thực hiện rút gọn theo cột của ma trận nên trước khi rút gọn cần phải dùng cú pháp `M.transpose()` để chuyển vị ma trận hoặc nếu ta đã sắp xếp đúng theo định dạng thì không cần phải chuyển vị nữa.
**Một số định lí và tính chất**
Mục đích ban đầu của thuật toán LLL là phân tích các đa thức trong $\displaystyle \mathbb{Q}[ x]$, điều này thực hiện trong thời gian đa thức. Tuy nhiên trên đường đi, nó khôi phục một vector lưới có độ dài tối đa $\displaystyle \left(\frac{2}{\sqrt{3}}\right)^{m}$ lần so với vector ngắn nhất trong một số lưới $\displaystyle \mathcal{L}$, tức là nó có thể giải được $\displaystyle SVP_{\left( 2/\sqrt{3}\right)^{m}}$ trong thời gian $\displaystyle O\left( n^{6}\log_{3} B\right)$ trong đó $\displaystyle B$ là độ dài của vector cơ sở đầu vào dài nhất.
Cụ thể ta có các định lí sau đây
**Định lí 1.** Cho $\displaystyle \mathbf{B} =\{\mathbf{b}_{1} ,...,\mathbf{b}_{n}\}$ là một cơ sở lattice và $\displaystyle \mathbf{B}^{*} =\left\{\mathbf{b}_{1}^{*} ,...,\mathbf{b}_{n}^{*}\right\}$ là cơ sở sau khi trực giao hóa Gram Schmidt. Khi đó $\displaystyle \lambda _{1}(\mathcal{L}(\mathbf{B})) \geqslant \min_{i\in \{1,...,n\}} \| \mathbf{b}_{i}^{*} \|$.
Chứng minh.
Xét $\displaystyle \mathbf{x} =( x_{1} ,...,x_{n}) \in \mathbb{Z}^{n}$ là vector nhỏ nhất khác 0 và vì $\displaystyle \mathbf{x}$ khác vector 0 cho nên tồn tại một chỉ số $\displaystyle j$ lớn nhất sao cho $\displaystyle x_{j} \neq 0$. Khi đó $\displaystyle x_{i} =0,\forall i >j$. Bây giờ xét điểm nguyên $\displaystyle \mathbf{xB}$ thì ta
\begin{gather*}
| \langle \mathbf{xB} ,\mathbf{b}_{j}^{*} \rangle | =\mid \langle \sum _{i=1}^{n} x_{i}\mathbf{b}_{i} ,\mathbf{b}_{j}^{*} \rangle | \\
=\mid \sum _{i=1}^{n} x_{i} \langle \mathbf{b}_{i} ,\mathbf{b}_{j}^{*} \rangle | \geqslant |x_{j} |\langle \mathbf{b}_{j} ,\mathbf{b}_{j}^{*} \rangle = | x_{j} | \| \mathbf{b}_{j}^{*} \| ^{2}
\end{gather*}
Mà lại có
\begin{gather*}
| \langle \mathbf{xB} ,\mathbf{b}_{j}^{*} \rangle | \leqslant \| \mathbf{xB} \| \cdotp \| \mathbf{b}_{j}^{*} \| \Longrightarrow | x_{j} | \cdotp \| \mathbf{b}_{j}^{*} \| ^{2} \leqslant \| \mathbf{xB} \| \cdotp \| \mathbf{b}_{j}^{*} \| \\
\Longrightarrow | x_{j} | \cdotp \| \mathbf{b}_{j}^{*} \| \leqslant \| \mathbf{xB} \| \\
\Longrightarrow \min_{i\in \{1,...,n\}} \| \mathbf{b}_{i}^{*} \| \leqslant \| \mathbf{xB} \|
\end{gather*}
**Định lí 2.** Cho $\displaystyle \mathbf{B} =\{\mathbf{b}_{1} ,...,\mathbf{b}_{n}\}$ là một cơ sở rút gọn $\displaystyle \delta -LLL$ rút gọn. Khi đó $\displaystyle \| \mathbf{b}_{1} \| \leqslant \left(\frac{2}{\sqrt{4\delta -1}}\right)^{n-1} \lambda _{1}$.
Định lí này có ý nghĩa rằng: vector đầu tiên sau khi rút gọn LLL chưa chắc là vector ngắn nhất nhưng nó là một vector gần với vector ngắn nhất của mạng.
Từ điều kiện rút gọn lattice ta có
\begin{equation*}
\left( \delta -\mu _{i+1,i}^{2}\right) \| \mathbf{b}_{i}^{*} \| ^{2} \leqslant \| \mathbf{b}_{i+1}^{*} \| ^{2}
\end{equation*}
Mà ta có $\displaystyle \mu _{i+1,i} \leqslant \frac{1}{2}$ kéo theo $\displaystyle \left(\frac{4\delta -1}{4}\right) \| \mathbf{b}_{i}^{*} \| ^{2} \leqslant \mathbf{\| b}_{i+1}^{*} \| ^{2}$
Cho nên
\begin{gather*}
\| \mathbf{b}_{i}^{*} \| ^{2} \leqslant \mathbf{\| b}_{i+1}^{*} \| ^{2}\left(\frac{4}{4\delta -1}\right)\\
\Longrightarrow \| \mathbf{b}_{1}^{*} \| \leqslant \| \mathbf{b}_{i}^{*} \| \left(\frac{2}{\sqrt{4\delta -1}}\right)^{i-1}\\
\Longrightarrow \| \mathbf{b}_{1}^{*} \| \leqslant \| \mathbf{b}_{n}^{*} \| \left(\frac{2}{\sqrt{4\delta -1}}\right)^{n-1}
\end{gather*}
### Một vài ví dụ
**Giải phương trình nghiệm nguyên**
**Bài tập 1 :**
```python=
import math
from decimal import *
getcontext().prec = 100
FLAG = "crypto{???????????????}"
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103]
h = Decimal(0.0)
for i, c in enumerate(FLAG):
h += ord(c) * Decimal(PRIMES[i]).sqrt()
ct = math.floor(h*16**64)
print(f"ciphertext: {ct}")
# ciphertext: 1350995397927355657956786955603012410260017344805998076702828160316695004588429433
```
Phân tích: Ở bài này ta thấy rằng, giá trị $\displaystyle h$ được tính bởi
\begin{equation*}
h=\sum ord[ i] \times \sqrt{p_{i}}
\end{equation*}
Trong đó $\displaystyle ord[ i]$ là giá trị ASCII của từng kí tự của flag. Giá trị này sau đó được nhân với một số nguyên tố trong list và lấy tổng lại. Kết quả trả về sẽ là $\displaystyle \left\lfloor h\times 16^{64}\right\rfloor$.
Vậy ta sẽ dùng lattice vào bài này như thế nào? Đầu tiên ta xét phương trình
\begin{gather*}
h=\sum x_{i}\sqrt{p_{i}} \Longrightarrow c=\left\lfloor \left(\sum x_{i}\sqrt{p_{i}}\right) \times 2^{256}\right\rfloor \\
\Longrightarrow \sum x_{i}\sqrt{p_{i}} \sim \frac{c}{2^{256}}
\end{gather*}
Đây là dạng bài approximate subset sum. Đầu tiên ta viết lại dưới dạng tổ hợp tuyến tính:
\begin{equation*}
x_{0}\begin{bmatrix}
\sqrt{p_{0}}\\
1\\
0\\
0\\
\vdots \\
0
\end{bmatrix} +x_{1}\begin{bmatrix}
\sqrt{p_{1}}\\
0\\
1\\
0\\
\vdots \\
0
\end{bmatrix} +....+x_{n}\begin{bmatrix}
\sqrt{p_{n}}\\
0\\
0\\
0\\
\vdots \\
1
\end{bmatrix} +1\begin{bmatrix}
-c/2^{256}\\
0\\
0\\
0\\
\vdots \\
0
\end{bmatrix} \sim \begin{bmatrix}
0\\
x_{0}\\
x_{1}\\
\vdots \\
x_{n-1}\\
x_{n}
\end{bmatrix}
\end{equation*}
Vấn đề là thuật LLL của chúng ta sẽ làm việc với các số nguyên trong khi đó $\displaystyle \sqrt{p_{i}}$ là các số vô tỉ cho nên không thể đưa vào tính toán được. Một cách để giải quyết đó chính là nhân thêm vào nó hệ số (scale) và làm tròn bằng hàm phần nguyên.
\begin{equation*}
x_{0}\begin{bmatrix}
\left\lfloor \sqrt{p_{0}} \times 2^{k}\right\rfloor \\
1\\
0\\
0\\
\vdots \\
0
\end{bmatrix} +x_{1}\begin{bmatrix}
\left\lfloor \sqrt{p_{1}} \times 2^{k}\right\rfloor \\
0\\
1\\
0\\
\vdots \\
0
\end{bmatrix} +....+x_{n}\begin{bmatrix}
\left\lfloor \sqrt{p_{n}} \times 2^{k}\right\rfloor \\
0\\
0\\
0\\
\vdots \\
1
\end{bmatrix} +1\begin{bmatrix}
\left\lfloor -c/2^{256} \times 2^{k}\right\rfloor \\
0\\
0\\
0\\
\vdots \\
0
\end{bmatrix} \sim \begin{bmatrix}
0\\
x_{0}\\
x_{1}\\
\vdots \\
x_{n-1}\\
x_{n}
\end{bmatrix}
\end{equation*}
Hmm sau một hồi thử nghiệm thì mình nhận ra cách tốt nhất là để nguyên các giá trị như ban đầu, tức là chọn $k=256$.
Sau khi sử dụng LLL thì ta sẽ check xem trong ma trận kết quả, hàng nào có phần tử đầu tiên = 0 thì đó là hàng mà ta cần tìm.
Code giải:
```python
from sage.all import *
def flatter(M):
import re
from subprocess import check_output
# compile https://github.com/keeganryan/flatter and put it in $PATH
z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
ret = check_output(["flatter"], input=z.encode())
return matrix(M.nrows(), M.ncols(), list(map(int, re.findall(b"-?\\d+", ret))))
P = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83]
c = 1350995397927355657956786955603012410260017344805998076702828160316695004588429433
n = len(P)
M = Matrix(ZZ,n+1,n+1)
for i in range(n):
M[0,i] = int(16**64*sqrt(P[i]))
M[0,n] = -c
for i in range(n):
M[i+1,i] = 1
M = M.transpose()
M = flatter(M)
print(''.join(chr(abs(v)) for v in M[0][1:]))
```
Câu hỏi: Dựa vào ma trận mình xây dựng ở trên thì theo lí thuyết phần tử đầu tiên của hàng đầu tiên phải gần hoặc xấp xỉ với 0 nhất có thể. Nhưng sau khi thử in ma trận ra để kiểm tra thì có vẻ không như vậy
```
[-1030 99 114 121 112 116 111 123 114 51 52 108 95 116 48 95 50 51 68 95 109 52 112 125]
```
## Bài toán CVP
Như đã trình bày ở trên thì thuật toán LLL giúp ta giải bài toán SVP và apprSVP. Bài toán tiếp theo mà ta tìm hiểu sẽ là bài toán CVP và apprCVP tức là bài toán tìm vector gần nhất với vector cho trước. Cụ thể với lưới $\displaystyle \mathcal{L}$ và một target vector $\displaystyle t$, ta sẽ tìm $\displaystyle v\in \mathcal{L}$ sao cho $\displaystyle \| v-t\|$ là nhỏ nhất.
## Thuật toán Babai
Đầu tiên để sinh ra một cơ sở thuận tiện cho tính toán thì ta cần làm 2 việc đó là rút gọn LLL cho cơ sở và chuyển cơ sở thành cơ sở trực giao với thuật toán gram schmidt. Chẳng hạn với cơ sở trực giao $\displaystyle \mathbf{B} =\{\mathbf{b}_{1} ,...,\mathbf{b}_{n}\}$ thì độ dài của mỗi vector trong $\displaystyle \mathcal{L}(\mathbf{B})$ được tính bởi
\begin{equation*}
\| a_{1}\mathbf{b}_{1} +...+a_{n}\mathbf{b}_{n} \| ^{2} =a_{1}^{2} \| \mathbf{b}_{1} \| ^{2} +...+a_{n}^{2} \| \mathbf{b}_{n} \| ^{2}
\end{equation*}
Ta xét một siêu phẳng sinh bởi $\displaystyle n-1$ vectors đầu tiên của lưới và đặt $\displaystyle t'=t-c_{n} b_{n}$ trong đó $\displaystyle c_{n}$ là số nguyên được chọn sao cho siêu phẳng được tịnh tiến bởi $\displaystyle c_{n}\mathbf{b}_{n}$ gần $\displaystyle t$ nhất có thể. $\displaystyle c_{n}$ sẽ được tính bởi $\displaystyle c_{n} =\left\lfloor \frac{\langle \mathbf{b} ,\mathbf{b}_{n}^{*} \rangle }{\langle \mathbf{b}_{n}^{*} ,\mathbf{b}_{n}^{*} \rangle }\right\rfloor$. Tiếp tục làm tương tự cho tới khi thu được tổng $\displaystyle c_{i}\mathbf{b}_{i}$ và cũng chính là giá trị mà ta cần tìm.
**Định nghĩa siêu phẳng:** Tập $X$ là siêu phẳng trong $\mathbb{R}^n$ nếu $X$ là không gian affine $n-1$ chiều.
Chi tiêt mọi người có thể xem ở đây https://ecampusontario.pressbooks.pub/daisotuyentinh/chapter/hyperplanes-and-half-spaces/
Implement:
```python
from sage.all import *
from sage.modules.free_module_integer import IntegerLattice
def flatter(M):
import re
from subprocess import check_output
# compile https://github.com/keeganryan/flatter and put it in $PATH
z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
ret = check_output(["flatter"], input=z.encode())
return matrix(M.nrows(), M.ncols(), list(map(int, re.findall(b"-?\\d+", ret))))
def Babai_CVP(mat,target):
M = flatter(mat)
G = M.gram_schmidt()[0]
diff = target
for i in reversed(range(G.nrows())):
diff -= M[i] * ((diff*G[i]) / (G[i]*G[i])).round()
return target - diff
```
## Kannan's Embedding
Một cách khác để xử lí CVP đó là nhúng vector cần tính vào trong ma trận cơ sở của lưới và chuyển từ bài CVP thành SVP.
ét $\displaystyle \mathbf{B} =\{\mathbf{b}_{1} ,...,\mathbf{b}_{n}\}$ là cơ sở của lưới và $\displaystyle \mathbf{t} =( t_{1} ,...,t_{n})$ là target vector. Nghiệm của CVP lúc này sẽ có dạng $\displaystyle c_{1}\mathbf{b}_{1} +...+c_{n}\mathbf{b}_{n}$. Như vậy
\begin{gather*}
\mathbf{t} \approx \sum _{i=1}^{n} c_{i}\mathbf{b}_{i}\\
\Longrightarrow \mathbf{t} =\sum _{i=1}^{n} c_{i}\mathbf{b}_{i} +e\\
\Longrightarrow \mathbf{t} =\mathbf{xB} +e\
\end{gather*}
trong đó ta có thể coi $\displaystyle e$ là sai số nhỏ. Xét một lưới $\displaystyle ( n+1) \times ( n+1)$ với các cơ sở như sau:
\begin{equation*}
\mathbf{B} '=\begin{bmatrix}
\mathbf{B} & 0\\
\mathbf{t} & q
\end{bmatrix}
\end{equation*}
Viết đầy đủ ma trận ra như sau:
\begin{equation*}
\mathbf{B} '=\begin{bmatrix}
b_{11} & b_{12} & \cdots & b_{1n} & 0\\
b_{21} & b_{22} & \cdots & b_{2n} & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots \\
b_{n1} & b_{n2} & \cdots & b_{nn} & 0\\
t_{1} & t_{2} & \cdots & t_{n} & q
\end{bmatrix}
\end{equation*}
Như vậy lưới này sẽ có một vector nhỏ $\displaystyle ( e,q) =( e_{1} ,e_{2} ,...,e_{n} ,q)$ sinh bởi tổ hợp tuyến tính $\displaystyle ( -c_{1} ,...,-c_{n} ,1)$.
Ví dụ:
Giả sử ta có một ma trận như sau:
\begin{equation*}
B=\begin{pmatrix}
35 & 72 & -100\\
-10 & 0 & -25\\
-20 & -279 & 678
\end{pmatrix}
\end{equation*}
là một lattice trong $\displaystyle \mathbb{R}^{3}$. Vector mục tiêu của ta là $\displaystyle w=( 100,100,100)$. Ta chọn trọng số $\displaystyle q=1$. Xây dựng ma trận mới và làm theo thuật toán ở trên:
\begin{equation*}
B'=\begin{pmatrix}
35 & 72 & -100 & 0\\
-10 & 0 & -25 & 0\\
-20 & -279 & 678 & 0\\
100 & 100 & 100 & 1
\end{pmatrix}
\end{equation*}
```python=
M = Matrix(ZZ, [[35,72,-100,0],[-10,0,-25,0],[-20,-279,678,0],[100,100,100,1]])
target = vector(ZZ,[100,100,100])
M = flatter(M)
print(M)
for row in M:
if row[-1] == 1:
vec = target - vector(row[:-1])
print(f"solution là {vec}")
```
```
[ 0 1 0 1]
[ 5 0 1 0]
[ 0 5 1 -4]
[ 5 4 -21 -5]
solution là (100, 99, 100)
```
## Ví dụ
### sharsable SECCON 2020
Source code của bài:
```python
from Crypto.Util.number import getPrime, GCD
from flag import FLAG
import random
def egcd(a, b):
r0, r1 = a, b
s0, s1 = 1, 0
t0, t1 = 0, 1
while r1 > 0:
q = r0 // r1
r0, r1 = r1, r0 % r1
s0, s1 = s1, s0 - q * s1
t0, t1 = t1, t0 - q * t1
return s0, t0
def generateKey():
p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p-1)*(q-1)
while True:
d1 = getPrime(int(n.bit_length()*0.16))
e1 = random.randint(1, phi)
ed1 = e1 * d1 % phi
d2 = getPrime(int(n.bit_length()*0.16))
e2, k = egcd(d2, phi)
e2 = e2 * (phi + 1 - ed1) % phi
ed2 = e2 * d2 % phi
if GCD(e1, e2) > 10:
break
assert((ed1 + ed2) % phi == 1)
return (n, (e1, d1), (e2, d2))
n, A, B = generateKey()
M = int.from_bytes(FLAG, 'big')
C1 = pow(M, A[0], n)
C2 = pow(M, B[0], n)
assert(pow(C1, A[1], n) * pow(C2, B[1], n) % n == M)
import json
print(json.dumps({
"n": n,
"A": (A[0], C1),
"B": (B[0], C2),
#"d": (A[1], B[1]), # for debug
}))
```
Hàm genkey tạo ra hai số nguyên tố $\displaystyle p,q$ lớn và sau đó tính $\displaystyle \varphi ( n) =( p-1)( q-1)$. Tiếp theo nó sẽ tính các giá trị sau: $\displaystyle d_{1}$ là một số nguyên tố, $\displaystyle e_{1}$ chọn bất kì sao cho $\displaystyle e_{1} \in [ 1,phi)$ và lấy $\displaystyle ed_{1} =e_{1} d_{1}\bmod \varphi ( n)$.
Tiếp theo $\displaystyle e_{2} ,k$ được tạo ra như thế nào. Thuật Euclid mở rộng trên sẽ trả về cặp giá trị $\displaystyle ( s_{0} ,t_{0})$ thỏa mãn
\begin{equation*}
s_{0} a+t_{0} b=\gcd( a,b)
\end{equation*}
Như vậy $\displaystyle e_{2} ,k$ là các số thỏa mãn
\begin{equation*}
e_{2} d_{2} +k\varphi ( n) =\gcd( d_{2} ,\varphi ( n))
\end{equation*}
Sau đó $\displaystyle e_{2}$ được tính lại
\begin{gather*}
e_{2} =e_{2} \times ( \varphi ( n) +1-ed_{1}) \ (\bmod \varphi ( n))\\
=e_{2} \times ( 1-e_{1} d_{1}) \ \bmod \varphi ( n)
\end{gather*}
Cuối cùng ta có
\begin{equation*}
ed_{2} =e_{2} d_{2} \ \bmod \varphi ( n)
\end{equation*}
Lúc này
\begin{equation*}
ed_{1} +ed_{2} =e_{1} d_{1} +e_{2} d_{2}
\end{equation*}
Vấn đề là bài không nói cụ thể $\displaystyle \gcd( d_{2} ,\varphi ( n))$ có giá trị là bao nhiêu nên mình cũng không rõ sao. Nhưng nếu như ta xem lại cách tạo $\displaystyle d_{2}$ thì có thể đoán rằng $\displaystyle \gcd( d_{2} ,\varphi ( n)) =1$. Như vậy
\begin{equation*}
e_{2} =d_{2}^{-1}\bmod \varphi ( n)
\end{equation*}
Và lúc này
\begin{equation*}
e_{1} d_{1} +e_{2} d_{2} \equiv e_{1} d_{1} +1-e_{1} d\equiv 1\bmod \varphi ( n)
\end{equation*}
Bài trả lại cho ta các giá trị $\displaystyle n,e_{1} ,e_{2} ,c_{1} ,c_{2}$ trong đó $\displaystyle c_{1} =m^{e_{1}}\bmod \ n$ và $\displaystyle c_{2} =m^{e_{2}}\bmod n$.
Để giải bài này thì ta cần khôi phục lại cả hai giá trị $\displaystyle d_{1} ,d_{2}$ để tính
\begin{equation*}
m^{e_{1} d_{1} +e_{2} d_{2}} =m\bmod n
\end{equation*}
Xét phương trình
\begin{equation*}
e_{1} d_{1} +e_{2} d_{2} =k\phi ( n) +1
\end{equation*}
Nếu ta cố dựng một lattice giống bài SVP thì không được vì ở đây có tới 2 giá trị mà ta không rõ là $\displaystyle k$ và $\displaystyle \phi ( n)$.
\begin{equation*}
d_{1} \times \begin{bmatrix}
e_{1}\\
1\\
0\\
0
\end{bmatrix} +d_{2} \times \begin{bmatrix}
e_{2}\\
0\\
1\\
0
\end{bmatrix} +...???
\end{equation*}
https://eprint.iacr.org/2012/666.pdf
### Bounded Noise - CryptoHack
Source code của bài:
```python
import random
import json
FLAG = b"crypto{?????????????????????????????????????????}"
def keygen(secret, q, erange=range(2)):
n, m = len(secret), len(secret) ** 2
A = Matrix(GF(q), m, n, lambda i, j: randint(0, q - 1))
e = vector(random.choices(erange, k=m), GF(q))
b = (A * secret) + e
return A, b, e
flag_int = int.from_bytes(FLAG, "big")
q = 0x10001
secret_key = []
while flag_int:
secret_key.append(flag_int % q)
flag_int //= q
secret_key = vector(GF(q), secret_key)
A, b, e = keygen(secret_key, q)
with open("output.txt", "w") as f:
json.dump({"A": str(list(A)), "b": str(b)}, f)
```
Hàm keygen sinh một ma trận $\displaystyle A\in \mathbb{F}_{q}^{m\times n}$ gồm $\displaystyle m$ hàng và $\displaystyle n$ cột. $\displaystyle e$ là vector chứa các errors, các giá trị của $\displaystyle e$ chỉ bao gồm $\displaystyle \{0,1\}$ và $\displaystyle e$ gồm $\displaystyle m$ phần tử $\displaystyle e=( e_{1} ,...,e_{m})$. $\displaystyle s$ là flag và ta có
\begin{equation*}
As+e=b
\end{equation*}
Ta viết lại các phương trình dưới dạng
\begin{gather*}
\mathbf{a}_{1} s+e_{1} =b_{1}\bmod q\\
\mathbf{a}_{2} s+e_{2} =b_{2}\bmod q\\
...\\
\mathbf{a}_{m} s+e_{m} =b_{m}\bmod q
\end{gather*}
Vì lấy theo modulo $\displaystyle q$ nên ta viết lại
\begin{gather*}
\mathbf{a}_{1} s+e_{1} =b_{1} +k_{1} q\\
...\\
\mathbf{a}_{m} s+e_{m} =b_{m} +k_{m} q
\end{gather*}
$\displaystyle \mathbf{a}_{i}$ ở đây là các vector hàng của ma trận $\displaystyle A$. $\displaystyle s$ là một ma trận có kích thước $\displaystyle n\times 1$.
Ta sẽ dựng một ma trận để giải bài CVP.
\begin{equation*}
\mathbf{a}_{m} s-k_{m} q=b_{m} -e_{m}
\end{equation*}
Đưa về ma trận
\begin{equation*}
\begin{bmatrix}
A & qI_{M}
\end{bmatrix}\begin{bmatrix}
s_{1}\\
\vdots \\
s_{n}\\
k_{1}\\
\vdots \\
k_{m}
\end{bmatrix} =b-e
\end{equation*}
Do $\displaystyle e$ chỉ gồm các giá trị $\displaystyle ( 0,1)$ nên ta có thể coi đây là bài CVP với target vector là $\displaystyle b$ và sinh bởi lattice
\begin{equation*}
\begin{bmatrix}
A & qI_{M}
\end{bmatrix}
\end{equation*}
Nhưng mình thử code theo như trên thì thuật LLL chạy khá lâu :V. Lí do nó chạy lâu là bởi vì kích thước ma trận cơ sở quá lớn.
### RSARSA
```python
from secret import flag
from Crypto.Util.number import bytes_to_long, getPrime
from os import urandom
p, q, P, Q = 1, 1, 1, 1
while p%3 == 1: p = getPrime(1001)
while q%3 == 1: q = getPrime(1001)
while P%3 == 1: P = getPrime(1024)
while Q%3 == 1: Q = getPrime(1024)
n = p*q
N = P*Q
m = bytes_to_long(flag.encode() + urandom(250-len(flag)))
e = 3
c = pow(m,e,n)
C = (pow(p,e,N)*q)%N
with open('out.txt','w') as file:
file.write(f'{n = }\n')
file.write(f'{c = }\n')
file.write(f'{N = }\n')
file.write(f'{C = }\n')
'''
n = 236165963974549843165116395504697902191713379536628118224442456369682302266394059291805550850454501790983078745877277808465242450967192483721221804260097540207577805062483656523327027127554710603966355779002569448126827875849586909708264874355346913072634179303036432164732044525075631421114547665911909245396864649081324916352615048804238378500443339490430805687717735684234839495464001575301049381927288871113238709183695134250935765261299598697578849137375656662373462784922948497996422774555641898913228531573884546030084889237337034678567704892293682351242487623366576639394595575585737748297628969
c = 70937012742384298918498947273158135897378405817961054208468507698675885078698256087375111837428304573078062065633783770628342991758025350342481268180700230612722899026588541878904025893741429507151056686887872849449670311554735563584135338155830845926213289013822577616362794865255147852918994796746331323556683930502366845200103692080775988066038363189731329287562177600843653604176315077351590599271405298532429144976167210974674215140921019287905291182057378400248332045718636113089603523143042785670709665781815838353423684587315486764254364359269569359888642641186171777475467206816292957014109298
N = 13559643931510231890645252059392928830324878403065777432078047001203751827960606291671049295745925572045928516195747933143730424354729124065331936456182264578676144427400292605461916569434409294456724314100819999479249740665646695282083306225220537019377541170020872360049287615554093874460563300874852415511897525645607710048718121342471391046511248087651223041929052149218448630378746909560110882899655656687984011210519333987281129803478797350285596913131043564417404130060868808451206852147929161483360924558387919617786314342462258102165618528861476250258876654302439406603504196138731002715669914240460335010891
C = 8275456195949033635467084095519107709201520788369843769112612900914126045121100567953979244052722913960259224583894825296560682673296622047075175324016507276388107904876439908187727967560228110789357765846667845045209064071847259841181338077835834748735605960343420564692832127030070311244168918947119031684158691819391344400702542409477570193678230185099108849985093513086193902773249508226511128276263713550182135750315888219451287568184957554794890731479934946953654922694958015237442372049821287406228796371974841586661090969263065535555883597103891939136230373286602239899758144274469967582717851587584634595648
'''
```
Đầu tiên bài cho 4 số $p,q,P,Q$ trong đó $p,q$ có độ lớn 1001 bits còn $P,Q$ thì có độ lớn 1024 bits. Ta được biết thêm thông tin về $C=p^eq \ \bmod N =p^3q \ \bmod N$. Ở đây là mod $N$ chứ không phải mod $n$ nếu không thì $C=0$. Bây giờ ta có thể biến đổi
$$
n^2C^{-1} \bmod N \leftrightarrow p^2q^2p^{-3}q^{-1}=p^{-1}q \bmod N
$$
Từ đây, đặt $t=p^{-1}q\bmod N$ thì ta có
$$
tp-q=kN
$$
Có thể chuyển về lattice để tính
$$
p\times(t,1)+(-k)\times(N,0) = (q,p)
$$
Vector target của ta sẽ là $(q,p)$. Vector này có norm là $\sqrt{p^2+q^2} \sim 2^{1001}$ trong khi đó các cơ sở của lưới có độ lớn khoảng $2^{2000}$ cho nên ta có thể kì vọng hàng đầu tiên sau khi rút gọn sẽ chứa $q$.
Script:
```python
from Crypto.Util.number import *
from sage.all import *
from sage.modules.free_module_integer import IntegerLattice
n = 236165963974549843165116395504697902191713379536628118224442456369682302266394059291805550850454501790983078745877277808465242450967192483721221804260097540207577805062483656523327027127554710603966355779002569448126827875849586909708264874355346913072634179303036432164732044525075631421114547665911909245396864649081324916352615048804238378500443339490430805687717735684234839495464001575301049381927288871113238709183695134250935765261299598697578849137375656662373462784922948497996422774555641898913228531573884546030084889237337034678567704892293682351242487623366576639394595575585737748297628969
c = 70937012742384298918498947273158135897378405817961054208468507698675885078698256087375111837428304573078062065633783770628342991758025350342481268180700230612722899026588541878904025893741429507151056686887872849449670311554735563584135338155830845926213289013822577616362794865255147852918994796746331323556683930502366845200103692080775988066038363189731329287562177600843653604176315077351590599271405298532429144976167210974674215140921019287905291182057378400248332045718636113089603523143042785670709665781815838353423684587315486764254364359269569359888642641186171777475467206816292957014109298
N = 13559643931510231890645252059392928830324878403065777432078047001203751827960606291671049295745925572045928516195747933143730424354729124065331936456182264578676144427400292605461916569434409294456724314100819999479249740665646695282083306225220537019377541170020872360049287615554093874460563300874852415511897525645607710048718121342471391046511248087651223041929052149218448630378746909560110882899655656687984011210519333987281129803478797350285596913131043564417404130060868808451206852147929161483360924558387919617786314342462258102165618528861476250258876654302439406603504196138731002715669914240460335010891
C = 8275456195949033635467084095519107709201520788369843769112612900914126045121100567953979244052722913960259224583894825296560682673296622047075175324016507276388107904876439908187727967560228110789357765846667845045209064071847259841181338077835834748735605960343420564692832127030070311244168918947119031684158691819391344400702542409477570193678230185099108849985093513086193902773249508226511128276263713550182135750315888219451287568184957554794890731479934946953654922694958015237442372049821287406228796371974841586661090969263065535555883597103891939136230373286602239899758144274469967582717851587584634595648
t = (n*n*pow(C,-1,N)) % N
M = Matrix([[t,1],[N,0]]).LLL()
for row in M:
print(row,'\n')
for row in M:
if gcd(row[0],n) > 1 :
q = ZZ(int(abs(row[0])))
print(abs(row[0]))
p = n//int(q)
phi = (p-1)*(q-1)
d = pow(3,-1,phi)
m = pow(int(c),int(d),int(n))
print(long_to_bytes(int(m)))
# b'ictf{my_d0u813D_RSA_D!D_n07_Cook}
```
Lúc đầu thay vì dùng `LLL` build in của sage thì mình sử dụng `flatter` và nó bị lỗi
```python
from Crypto.Util.number import *
from sage.all import *
from sage.modules.free_module_integer import IntegerLattice
def flatter(M, delta=None):
import re
from subprocess import check_output
z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
cmd = ["flatter"]
if delta is not None:
cmd.extend(["-delta", str(delta)])
ret = check_output(cmd, input=z.encode())
return matrix(M.nrows(), M.ncols(), list(map(int, re.findall(b"-?\d+", ret))))
n = 236165963974549843165116395504697902191713379536628118224442456369682302266394059291805550850454501790983078745877277808465242450967192483721221804260097540207577805062483656523327027127554710603966355779002569448126827875849586909708264874355346913072634179303036432164732044525075631421114547665911909245396864649081324916352615048804238378500443339490430805687717735684234839495464001575301049381927288871113238709183695134250935765261299598697578849137375656662373462784922948497996422774555641898913228531573884546030084889237337034678567704892293682351242487623366576639394595575585737748297628969
c = 70937012742384298918498947273158135897378405817961054208468507698675885078698256087375111837428304573078062065633783770628342991758025350342481268180700230612722899026588541878904025893741429507151056686887872849449670311554735563584135338155830845926213289013822577616362794865255147852918994796746331323556683930502366845200103692080775988066038363189731329287562177600843653604176315077351590599271405298532429144976167210974674215140921019287905291182057378400248332045718636113089603523143042785670709665781815838353423684587315486764254364359269569359888642641186171777475467206816292957014109298
N = 13559643931510231890645252059392928830324878403065777432078047001203751827960606291671049295745925572045928516195747933143730424354729124065331936456182264578676144427400292605461916569434409294456724314100819999479249740665646695282083306225220537019377541170020872360049287615554093874460563300874852415511897525645607710048718121342471391046511248087651223041929052149218448630378746909560110882899655656687984011210519333987281129803478797350285596913131043564417404130060868808451206852147929161483360924558387919617786314342462258102165618528861476250258876654302439406603504196138731002715669914240460335010891
C = 8275456195949033635467084095519107709201520788369843769112612900914126045121100567953979244052722913960259224583894825296560682673296622047075175324016507276388107904876439908187727967560228110789357765846667845045209064071847259841181338077835834748735605960343420564692832127030070311244168918947119031684158691819391344400702542409477570193678230185099108849985093513086193902773249508226511128276263713550182135750315888219451287568184957554794890731479934946953654922694958015237442372049821287406228796371974841586661090969263065535555883597103891939136230373286602239899758144274469967582717851587584634595648
t = (n*n*pow(C,-1,N)) % N
print(t)
M = Matrix(ZZ,[[t,1],[N,0]])
A = M.LLL()
B = flatter(M,delta = 0.99)
for row in A:
print(row,'\n')
for row in B:
print(row,'\n')
'''
(16980142774580494256808634333109531222867582013924271809971152676804925984313656469784874933470936830578748176438608622056906182820277368894687592701948972028744495071872949851330056673249325479507828616192846301254747547225546760406847548523387532662974476939495916676769250388501603757799643754665239, 13908361496706230180173871801989702194942804003794936670880306417445628743538260657476926414121490785820329067259626927207346735892861416631843108509251957737631737539126585787587382001403842078844478687878019904939516723131200872302368147303065165584184047854800090474667423308083832121225600828123071)
(-391459209243361204525581981616951543125468853766696315105789717830611748489278438572153182984381821175270180980090894338668033352158758690992587924249479579864791142305556683123320553296824562527019287466314414779753466535562879963910354754208245665931350604184727340408778372853405694829910347850071504969624018796, 477916342981944565114102615898187688698105728317905396572519260667110230044748919294531550853074596564510267116286076018295985766033199532411014379424888593622347450669295775010029650767393972685463855112345819468192457796980772347411709192462951225697606968251549376415399675205580126147266117972279778258717046625)
(-3065612959800546347791798536136069551797959934797163122862744099865632473704833379025411117256792513274523842310650188520487243114495459953212355819192225746516664667379877939069156540484819260928203225208376488678898787132171715607077419608689699290722619696983239676504850778490009658161196175026743512737889430482865784666850429030591080773008175089116387995634833506953730795217705709166243230128704797011025426149726679408797524880402315022390735572642368952498899605704627806599016819521599473286513151179625806029823643981221218920709740384595208157280544558338050188595820635335323908501981691457290563900494, 1)
(13559643931510231890645252059392928830324878403065777432078047001203751827960606291671049295745925572045928516195747933143730424354729124065331936456182264578676144427400292605461916569434409294456724314100819999479249740665646695282083306225220537019377541170020872360049287615554093874460563300874852415511897525645607710048718121342471391046511248087651223041929052149218448630378746909560110882899655656687984011210519333987281129803478797350285596913131043564417404130060868808451206852147929161483360924558387919617786314342462258102165618528861476250258876654302439406603504196138731002715669914240460335010891, 0)
'''
```
Mình cx k rõ vì sao nữa :v `LLL` mặc định trong sage rút gọn với tham số LLL là `0.99` nên mình cũng nhập tương tự với `flatter` nhưng vẫn k ra đúng. Hmmmm
# Tài liệu tham khảo
[1] https://eprint.iacr.org/2023/032.pdf
[2] https://magicfrank00.github.io/writeups/posts/lll-to-solve-linear-equations/
[3] https://www.math.auckland.ac.nz/~sgal018/crypto-book/main.pdf
Sign in with Wallet
Connect another wallet