# Lattices trong cuộc sống =(((
## Không gian vector
Trước khi bắt đầu nói về lattices, ta nói về không gian vector. Không gian vector có thể được định nghĩa theo tính tổng quát là một tập hợp của các đại lượng gọi là vectơ, một đại lượng có thể cộng và nhân bởi một số, được gọi là vô hướng.
Cho một không gian vector V là một tập con của $R^m$ với tính chất:
$$\alpha_1v_1 + \alpha_2v_2 \in V\ \hspace{1cm} \forall v_1,v_2 \in V \text{và}\ \forall \alpha_1, \alpha_2 \in R. $$
## Tổ hợp tuyến tính
Ta có $v_1,v_2,...,v_k \in V$. Một tổ hợp tuyến tính của $v_1,v_2,...,v_k \in V$ có dạng:
$$w = \alpha_1v_1 + \alpha_2v_2 +...+ \alpha_kv_k\ \text{với}\ \alpha_1,...,\alpha_k\ \in\ R$$
Tập hợp các tổ hợp tuyến tính như vậy, $\{\alpha_1v_1 + ... + \alpha_kv_k:\alpha_1,...,\alpha_k \in R \}$ được gọi là **span** của $\{v_1,...,v_k\}$.
## Độc lập tuyến tính.
Một tổ hợp các vector $v_1,v_2,...,v_k \in V$ độc lập tuyến tính nếu nghiệm duy nhất của phương trình
$$\alpha_1v_1 + \alpha_2v_2 + ...+ \alpha_kv_k = 0$$
là $$\alpha_1 = \alpha_2 = ... = \alpha_k = 0$$
Từ đó, ta có được đề xuất sau:
Cho $V \subset R^m$ là một không gian vector thỏa mãn:
- Có cơ sở cho V
- Hai cơ sở bất kỳ cho V có cùng số phần tử vector
- Cho $v_1,v_2,...,v_k$ làm cơ sở cho V và cho $w_1,w_2,...,w_k$ làm cơ sở cho tập hợp n khác V. Ta có thể viết được như sau:
$$w_1 = \alpha_{1_1}v_1 + \alpha_{1_2} + ... + \alpha_{1_n}v_n,$$
$$w_2 = \alpha_{2_1}v_1 + \alpha_{2_2} + ... + \alpha_{2_n}v_n,$$
$$...$$
$$w_n = \alpha_{n_1}v_1 + \alpha_{n_2} + ... + \alpha_{n_n}v_n.$$
Khi đó, $w_1,...,w_n$ cũng là cơ sở cho V khi và chỉ khi nghiệm của ma trận
$$
\begin{pmatrix}
\alpha_{1_1} & \alpha_{1_2} & \dots & \alpha_{1_n} \\
\alpha_{2_1} & \alpha_{2_2} & \dots & \alpha_{2_n} \\
\vdots & \vdots & \ddots & \vdots \\
\alpha_{n_1} & \alpha_{n_2} & \dots & \alpha_{n_n}
\end{pmatrix}
$$
không bằng 0.
## Sizes
Cho $v,w \in V \subset R^m$ như sau
$v = (x_1,x_2,...,x_n)$ và $w = (y_1,y_2,...y_n)$
Tích của hai vector đó là
$$v.w = x_1y_1 + x_2y_2 + ... + x_ny_n$$
Ta nói rằng hai vector trực giao với nhau nếu $v.w = 0$
Chiều dài của một vector ký hiệu là $||v||$ được tính theo công thức như sau
$$||v|| = \sqrt{x_1^2 + x_2^2 + ... + x_n^2}$$
hoặc cũng có thể tính như sau
$$v.v = ||v||^2$$
## Lattices: Định nghĩa và tính chất cơ bản
Định nghĩa: Cho $v_1,...,v_n \in R^m$ tập hợp các vector độc lập tuyến tính. Lattice L được tạo bởi $v_1,...,v_n$ là tổ hợp tuyến tính với các hệ số trong tập hợp Z,
$$L = \{\alpha_1v_1 + \alpha_2v_2 + ... +\alpha_nv_n : \alpha_1, \alpha_2,...,\alpha_n \in Z \}$$
Giả sử $v_1,...,v_n$ là cơ sở cho mạng tinh thể L và $w_1,...,w_n \in L$ là một tập hợp các vectơ khác trong L. Giống như chúng ta đã làm cho các không gian vector, chúng ta có thể viết được như sau
$$w_1 = \alpha_{1_1}v_1 + \alpha_{1_2} + ... + \alpha_{1_n}v_n,$$
$$w_2 = \alpha_{2_1}v_1 + \alpha_{2_2} + ... + \alpha_{2_n}v_n,$$
$$...$$
$$w_n = \alpha_{n_1}v_1 + \alpha_{n_2} + ... + \alpha_{n_n}v_n.$$
Nhưng giờ ta đang xử lý ở Lattice, ta sẽ có được như sau
$$
A = \begin{pmatrix}
\alpha_{1_1} & \alpha_{1_2} & \dots & \alpha_{1_n} \\
\alpha_{2_1} & \alpha_{2_2} & \dots & \alpha_{2_n} \\
\vdots & \vdots & \ddots & \vdots \\
\alpha_{n_1} & \alpha_{n_2} & \dots & \alpha_{n_n}
\end{pmatrix}
$$
và ta có rằng
$$1 = det(I) = det(AA^{-1}) = det(A)det(A^{-1})$$
Ví dụ: Cho lattice $L \subset R^3$ được tạo bởi 3 vector
$$v_1=(2,1,3),\ v_2=(1,2,0),\ v_3=(2,−3,−5)$$
Ta chuyển nó thành ma trận A như sau
$$
A = \begin{pmatrix}
2 & 1 & 3 \\
1 & 2 & 0 \\
2 & - 3 & -5\\
\end{pmatrix}
$$
Ta chọn 3 vector mới thuộc L theo công thức
$$ w_1=v_1+v_3, w_2=v_1−v_2+2v_3, w_3=v_1+2v_2.$$
Ta có được ma trận U theo các hệ số của 3 vector trên.
$$
U = \begin{pmatrix}
1 & 0 & 1 \\
1 & -1 & 2 \\
1 & 2 & 0\\
\end{pmatrix}
$$
Ta có thể thấy được 3 vector w khi mà lấy U.A
$$
B =U.A= \begin{pmatrix}
4 & -2 & -2 \\
5 & -7 & -7 \\
4 & 5 & 3\\
\end{pmatrix}
$$
Ma trận U có định thức là -1 != 0 thế nên các vector w cũng là cơ sở của L. Ma trận nghịch đảo của U là:
$$
U^{-1} = \begin{pmatrix}
4 & -2 & -1 \\
-2 & 1 & 1 \\
-3 & 2 & 1\\
\end{pmatrix}
$$
Và các dòng của $U^{-1}$ cũng có thể biểu diễn các vector v theo vector w
$$v_1=4w_1−2w_2−w_3,\ v_2=−2w_1+w_2+w_3,\ v_3=−3w_1+2w_2+w_3.
$$
Giờ mình ví dụ cho một lattice cho các bạn hiểu nha.
Cho vector cơ sở của L là $v_1 = (2,3) ,\ v_2 = (4,5)$. Từ đó ta được $$L = \{\alpha_1v_1 + \alpha_2v_2 : \alpha_1, \alpha_2 \in Z \}$$ 1 điểm $(a,b)$ trong L sẽ có 2 giá trị x, y thỏa mãn
$$x*v_1 + y*v_2 = (a,b)$$
Giờ ta sẽ lập lattice bằng sage nha.
```sage
sage: L = matrix(ZZ, [[2,3], [4,5]])
sage: L
[2 3]
[4 5]
```
Giờ để check coi điểm (a,b) này có thuộc L không thì ta sẽ dùng span.
```sage
sage: vector([1,2]) in span(L)
False
sage: vector([34,45]) in span(L) # x = 5, y = 6
True
sage: vector([100,130]) in span(L) #x = 10, y = 20
True
```
## Lenstra, Lenstra và Lovász
Thuật toán LLL là một thuật toán giảm lattice, nghĩa là sẽ trả về một cơ sở khác cho cùng một mạng với các vector cơ sở ngắn hơn. Nếu số bé có thể sử dụng Gram-Schmidt, thế nhưng, trong nhiều trường hợp thì LLL vẫn tối ưu nhất.
Vì det() của các lattice là cố định và được tính bằng định thức của các vector cơ sở, thế nên trước và sau LLL đều sẽ có det() như nhau.
Ta ví dụ trong bài **FIND THE LATTICE**
```python
from Crypto.Util.number import getPrime, inverse, bytes_to_long
import random
import math
FLAG = b'crypto{?????????????????????}'
def gen_key():
q = getPrime(512)
upper_bound = int(math.sqrt(q // 2))
lower_bound = int(math.sqrt(q // 4))
f = random.randint(2, upper_bound)
while True:
g = random.randint(lower_bound, upper_bound)
if math.gcd(f, g) == 1:
break
h = (inverse(f, q)*g) % q
return (q, h), (f, g)
def encrypt(q, h, m):
assert m < int(math.sqrt(q // 2))
r = random.randint(2, int(math.sqrt(q // 2)))
e = (r*h + m) % q
return e
def decrypt(q, h, f, g, e):
a = (f*e) % q
m = (a*inverse(f, g)) % g
return m
public, private = gen_key()
q, h = public
f, g = private
m = bytes_to_long(FLAG)
e = encrypt(q, h, m)
print(f'Public key: {(q,h)}')
print(f'Encrypted Flag: {e}')
```
Bạn cũng có thể đọc lời giải của Drago từ Cryptohack
Ta có rằng
$$h = f^{-1}*g \mod q$$
$$\iff h*f = g \mod q$$
$$\iff h*f = g + q*k$$
$$\iff h*f - q*k = g$$
Giờ ta sẽ đặt ma trận
$$
\begin{pmatrix}
h&1 \\
q&0\\
\end{pmatrix}
$$
Như mình có ví dụ ở trên về lattice, sẽ có 1 điểm $(a,b)$ trong L sẽ có 2 giá trị x, y thỏa mãn
$$x*v_1 + y*v_2 = (a,b)$$
Thế nên, ta sẽ có cơ hội tìm cơ sở nhỏ nhất của lattice sao cho
$$x*v_1 + y*v_2 = (h,1)$$
$$x*v_1 + y*v_2 = (q,1)$$
Ta thấy rằng, $f\cdot(h,1)+(-k)\cdot(q,0)=(g,f)$, thế nên khi ta LLL, ta sẽ thu được giá trị g và f ở row đầu tiên. Thực ra, LLL sẽ tìm cơ sở nhỏ nhất sao cho $(h,1)$ và $(q,0)$ trong span của cơ sở đó.
Có thể bạn sẽ không hiểu, nên mình lấy số nguyên tố 8 bit cho dễ hiểu nha.
Ta có bộ key là **((179, 52), (7, 6))** và
Giờ ta sẽ LLL ma trận trên
```sage
sage: M = matrix([[52,1],[179,0]]);M.LLL()
[ 6 7]
[ 17 -10]
```
Giờ ta sẽ lấy ví dụ khác về LLL nha, lấy của Merkle Hellman đi. Chall này là bài warmup trong ACSC 2023.
```python
#!/usr/bin/env python3
import random
import binascii
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
def gcd(a, b):
if a == 0:
return b
return gcd(b % a, a)
flag = open("flag.txt","rb").read()
# Generate superincreasing sequence
w = [random.randint(1,256)]
s = w[0]
for i in range(6):
num = random.randint(s+1,s+256)
w.append(num)
s += num
# Generate private key
total = sum(w)
q = random.randint(total+1,total+256)
r = 0
while gcd(r,q) != 1:
r = random.randint(100, q)
# Calculate public key
b = []
for i in w:
b.append((i * r) % q)
# Encrypting
c = []
for f in flag:
s = 0
for i in range(7):
if f & (64>>i):
s += b[i]
c.append(s)
print(f"Public Key = {b}")
print(f"Ciphertext = {c}")
print()
# Output:
# PublicKey = [7352, 2356, 7579, 19235, 1944, 14029, 1084]
# Ciphertext = [8436, 22465, 30044, 22465, 51635, 10380, 11879, 50551, 35250, 51223, 14931, 25048, 7352, 50551, 37606, 39550]
```
Bài này sẽ kiểu có 1 public key, sau đó sẽ chuyển từng ký tự của flag thành binary, nếu là 1 thì sẽ cộng public key tương ứng lại.
Ví dụ:
```python
A = 1000001
Ciphertext[0] = 7352 + 1084 = 8436
C = 1000011
Ciphertext[1] = 7352 + 14029 + 1084 = 22465
```
Bài này nếu nhiều giá trị hơn thì mình nghĩ nên dùng quy hoạch động, bạn có thể tham khảo cách làm của mình sau đây. Mình mất code rồi chỉ còn ảnh thui, tự chép ra nha hihihi.
Còn nếu dùng LLL, thì bạn nên dùng ví dụ sau đây trước đã.
Ta có 3 số là [9,7,5]. Giờ mình sẽ lấy ngẫu nhiên số 37 đi. Giờ làm sao để có thể tìm lại được các giá trị a, b, c nhỏ nhất thỏa mãn: $9a + 7b + 5c = 23$.
Ta đặt được ma trận sau đây
$$
a*\begin{pmatrix}
1 & 0 & 0 & 9 \\
\end{pmatrix}
$$
$$
b*\begin{pmatrix}
0 & 1 & 0 & 7\\
\end{pmatrix}
$$
$$
c*\begin{pmatrix}
0 & 0 & 1 & 5\\
\end{pmatrix}
$$
$$
d*\begin{pmatrix}
0 & 0 & 0 & -23\\
\end{pmatrix}
$$
Từ đó, ta sẽ 4 vector cơ sở có dạng $(a,b,c,9*a+7*b+5*c-23*d)$ định thức bằng ma trận cũ và các chỉ số cũng là đơn giản nhất.
```sage
sage: M = matrix([[1,0,0,9],[0,1,0,7],[0,0,1,5],[0,0,0,-23]])
sage: M.LLL()
[ 2 0 1 0]
[-1 -2 0 0]
[-1 1 0 -2]
[-1 0 2 1]
```
Từ đó, ta tìm được $a =2, b = 0, c = 1$.
Giờ quay lại bài, ta sẽ làm như thế, nhưng mà phải biết xử lý code và mảng.
```python
PublicKey = [7352, 2356, 7579, 19235, 1944, 14029, 1084]
Ciphertext = [8436, 22465, 30044, 22465, 51635, 10380, 11879, 50551, 35250, 51223, 14931, 25048, 7352, 50551, 37606, 39550]
flag = ""
for i in range(len(Ciphertext)):
I = identity_matrix(7)
I = I.insert_row(7, [0 for x in range(8)])
L_helper = [[x] for x in PublicKey]
L_helper.append([-Ciphertext[i]])
L = I.augment(matrix(L_helper))
L.LLL()
bs = "0" + "".join([str(x) for x in L.LLL()[0][:-1]])
flag += (chr(int(bs,2)))
print(flag)
```
**Flag: ACSC{E4zY_P3@zy}**
## Knapsack Low-density Subset Sum Problems
Giờ mình cùng giải bài Backpack Cryptography trong Cryptohack nhé.
```python
import random
from collections import namedtuple
import gmpy2
from Crypto.Util.number import isPrime, bytes_to_long, inverse, long_to_bytes
FLAG = b'crypto{??????????????????????????}'
PrivateKey = namedtuple("PrivateKey", ['b', 'r', 'q'])
def gen_private_key(size):
s = 10000
b = []
for _ in range(size):
ai = random.randint(s + 1, 2 * s)
assert ai > sum(b)
b.append(ai)
s += ai
while True:
q = random.randint(2 * s, 32 * s)
if isPrime(q):
break
r = random.randint(s, q)
assert q > sum(b)
assert gmpy2.gcd(q,r) == 1
return PrivateKey(b, r, q)
def gen_public_key(private_key: PrivateKey):
a = []
for x in private_key.b:
a.append((private_key.r * x) % private_key.q)
return a
def encrypt(msg, public_key):
assert len(msg) * 8 <= len(public_key)
ct = 0
msg = bytes_to_long(msg)
for bi in public_key:
ct += (msg & 1) * bi
msg >>= 1
return ct
def decrypt(ct, private_key: PrivateKey):
ct = inverse(private_key.r, private_key.q) * ct % private_key.q
msg = 0
for i in range(len(private_key.b) - 1, -1, -1):
if ct >= private_key.b[i]:
msg |= 1 << i
ct -= private_key.b[i]
return long_to_bytes(msg)
private_key = gen_private_key(len(FLAG) * 8)
public_key = gen_public_key(private_key)
encrypted = encrypt(FLAG, public_key)
decrypted = decrypt(encrypted, private_key)
assert decrypted == FLAG
print(f'Public key: {public_key}')
print(f'Encrypted Flag: {encrypted}')
```
```python
Public key: [260288377891444370372615148009023640057294926547602419331406531383682223097787288755377467188515435381259752760746, 322734358011758862401399370931929863052553602421714393280581187496537763321855751120439457234561080720455397490349, 88092359256403564783665281993130133541226601877969436905267415353041909757324746080398461245281826552421872983184,....]
Encrypted Flag: 45690752833299626276860565848930183308016946786375859806294346622745082512511847698896914843023558560509878243217521
```
Bài này sẽ lấy từng bit cuối của flag, sau đó sẽ nhân với publickey tương ứng, khá là giống bài kia.
Giờ ta ví dụ chữ **cry** (vì chơi crypto chỉ có cry thui :cry:) đi, ta chuyển về bin thì ta sẽ được: ``01100011 01110010 01111001`` và thành int thì được ``109343314834543``.
Ta được bộ khóa sau đây
```python
Public key: [465443350468751008273841, 388551119148645079751987, 343715354189941964948557, 330832332266399085890144, 103304596681497730652466, 310926191372308658937420, 468189417003846036789371, 91380799065178968673274, 82560478948417404325909, 72910404280386082175094, 94833434312839833614073, 223734867649585469571881, 10928493595651490421109, 88276179981998524041147, 458969066633003948955271, 189316628509949317294639, 247725789070163904095505, 193849447948042202844838, 163106627729620370072474, 16908000900925708559205, 406490158737578495095064, 364171498820932152712359, 52539039291931227399734, 315410863617702072989429, 111221116449322665652614, 3528750617528780395977, 24461696115861382313779, 146319650160550984815748, 188081465522708218762065, 330105612726783049597743, 134269047352348664012240, 263333365773046655615680, 249109861465724598174638, 23816340941431473692250, 8215380269090481722943, 472256516973403457705030, 326506725965448435804152, 163026815594448541060866, 398662957842018521831786, 351091696578124718549518, 129724196813917573974560, 51097234473893552626139, 162021641317480642692620, 36525717111137166264096, 264068419426627724252212, 348176988829670665271493, 168775654796921949578917, 247289760476687024537852]
Encrypted Flag: 6303649443293291803510650
```
Vì là bị ngược từ dưới lên trên và cộng dồn các bit vào, nên ta không thể làm như merkle hellman được.
Bài này sẽ dựa vào Knapsack Problem (vấn đề cặp sách) để giải quyết vấn đề này. Bạn có thể tìm hiểu ở [**paper1**](https://eprint.iacr.org/2007/066.pdfhttps://eprint.iacr.org/2009/537.pdf) [**paper2**](https://eprint.iacr.org/2009/537.pdf) này hoặc là của anh [**Quốc**](https://hackmd.io/@nomorecaffeine/r1xstVfxC#1-Low-density-Subset-Sum-Problems) nhoeeee.
Cho các số nguyên dương $a_1, . . . , a_n$ và một số nguyên đích là $s$, tìm một dãy con nào đó mà có tổng là $s$. Giống như bài mình đang làm thôi.
Nhiều hệ thống mật mã dựa trên bài toán tổng tập hợp con đã được chứng minh là không an toàn thông qua các thuật toán giải quyết các trường hợp bài toán tổng tập hợp con (subnet sum problem) “low-density” đặc biệt. Mật độ của một tập các trọng số $a_1, . . . , a_n$ được xác định bởi:
$$d = \frac{n}{log_2 \ max(a_i)}$$
Và khi $d < 0.6463$ thì ta có thể sử dụng thuật toán Lagarias and Odlyzko’s, nhưng có lúc $d < 0.9408$, thì ta sẽ sử dụng J.coster. Ta sẽ tao được một ma trận như sau:
$$
B' = \begin{pmatrix} 1 & & & &Na_1 \\ &1 & & &Na_2 \\ & &\ddots & &\vdots\\ & & &1 &Na_n \\ 1/2 &1/2 &\cdots &1/2 &Ns \end{pmatrix}
$$
Với $N > \frac{1}{2}.\sqrt{n}$
Khi đó, ta sẽ thu được $e = (e'_1,...,e'_n)$ với $e'_i = e_i - \frac{1}{2}$
Quay trở lại bài này, ta thấy được giá trị $max = 601684701300110945921036937572461050140352984401874675917155063594305583314408001377505387079690115000992094388032$, ta thu được giá trị d
```sage
sage: round(log(601684701300110945921036937572461050140352984401874675917155063594305583314408001377505387079690115000992094388032,2),10)
377.9668823969
sage: round(272/377.9668823969,10)
0.7196397692
```
Ta sẽ dùng J.coster, thay vì LO như bài đầu tiên.
Ta lấy giá trị $N = 10 > \frac{sqrt(272)}{2}$. Giờ thì làm như bình thường thôi.
```python
PublicKey = [260288377891444370372615148009023640057294926547602419331406531383682223097787288755377467188515435381259752760746, 322734358011758862401399370931929863052553602421714393280581187496537763321855751120439457234561080720455397490349, 88092359256403564783665281993130133541226601877969436905267415353041909757324746080398461245281826552421872983184, 601684701300110945921036937572461050140352984401874675917155063594305583314408001377505387079690115000992094388032, 193814643850628739958152744041743058858484088269609293429408490294552345005365776962194365813796130165113184925621, 51510606914703888409341761261103125433754505248101513818740574350196563260563818621033222936301769697693287778876, 502702742677974540308798846750017003106263447846689040491266463798703222616320168069962523670400796196343460832764, 86989835783586738140883150201327374176124588410464188692884973334241681514702306716383785095564084499563152815246, 515511378187957676256419959601984383408150348796281656976955880729383340611785836962788715725367023923811376366815, 119845178983025037005174732553931706284024826223176718982111213579707091766057320315419827781508690979405126062061, 207867794910968434026003881920029657224591376925067493713968219177352819759854486838459675245909787840416982457750, 239399986603216503029402544900610984881160101923294396792665204486222975420081300661354603175384772323551980155480, 306665236132315336961576566094908486196981556971172170145299174389720334940261512384837950321772782983903454058725, 558130280550827068212352576387713811027468233905173944680355562037815257403446113128895937326412940859588204361963, 123471925832174980344066571541132411467266736109103860421447462536930482316849470378251137263190870093702164003085, 146089706629012142384661350988216882483919264673129621404831339166566056469572087759748854086023354002641923689390, 446097892684389219719742914373867457099954499449824602532333181169038249081395758983133906564840000962001976506057, 204029934276059225352901134714823317920576872465404508059719045291560482057171052793698580294637069578017200124432, 412333373143000457741307988470055504576675151299345387733692618218275177027643785881042018546460452418506341967356, 171418413940299360322712423004114364681865276057786947919043883366302567169869592290151559269290446563185553350080, 401593473337411114258578268223784182795068785564101722335215736591292301602077751376477881087346810602041717163104, 204003688543820354337113938494979311981574571424756883928855286926734578790400322291262042466654212377708831289347, 555612926496986208337317871061684502803594375654879680702581403987248292734014139717756900004905653768133795128973, 462785612281910846822645629160953231999037081137615204334672445418078665808070086646804794186256411131615189487813, 77961961618173276050791733447969083544152711482614563228085622136316525792569658878271751219358260960116292497570, 517789370221435419776588087490678991824021927945387533283088388790482913301281733115458601414668206432512998904516, 281870328340314395150658482932699114581743200279996227099530744754750289102031518563761975024621347281374162044877, 60204977937304337797770029325498234132893935850995809547662640467737007197647697381430963693698522962733473746281, 395936787836195675178388359277761575381601972138693830435288611414489963379399027975388601714741876831895709497105, 90921357930302550361827901642067284191268695594120415817202534786924330392421221829361546010764453051928814876700, 238523907687908075601117120608130752369082206676107364350347208286323115036939777325067473364465438898353765093766, 277515010021988996116595000889051160811249034599876556819610707794016612800585201793339332495839495779526504613846, 187215937497318890199135284983515062319988136636108170852591598862524363777870331888216170582220867500042557737272, 411220029331367081136918789112083235781237730079305782620378994961505282090962448446931628731751970521853108685376, 433613620456520979627974441205441942311133790647897226320388205340695256818608765746266662314499649013982035729731, 509613591091334719216567967380183602959933686617275815879939870258332674755345348802452058256788513837941126219238, 352708166022264045150842358964512080203788453464883319778517822047480718640858804837886057264514786742694419419735, 486272357335492500753956372299255798603575392697018451800774427752724312455328655650777691830508441976819499348269, 1291533249748053824342851185451970324561531056195308125673915619130780992270420765078102812914222570167615953050, 520707501920546816250915326019351261090208813534492143136485743644939372232638461802625700978801768541842624647274, 272359456788721692618768612190222453304838934916628492701462591276450281926223118982602858211688086607842351391495, 119534191144397164327417397593964021477488683311215644770010641745736480039094209273092223959694752862193314087240, 394945131470603614379767959704654538029557537489316246092982427107641617479545488843535929537498546432123287486437, 395979428475608101765230328218274625986674115712051764903732593018454264017781340199795540039285257513438842708672, 322101629493887220159199019582810892418957941946300752245249462093036697035162212557261470168522953435341905295650, 60610073299031334532969727880668989046838926047395613981473675505442500833244137863225398782029541439420403686372, 492582431835005621441922899995666806499437611069193099072247918597047415020628078410849119945608854080040163699375, 356290614124448077864884136922409291617128370298210212357882465167338600485728936925448944675136056707929560080237, 469737185578879122378016959759297464132272432425745272107998534197014940235018335349886398896979254122985841196030, 522871107234918024128768136315123497251902274681110489386594944387181296826024289163431880961506314580935567743910, 407151723612481391724375429193917289623669496278028982297086458062111012958436324350527302865535766565677711383191, 597354385774970715448797740483856119139152021834911852144490298736330354118482480147237280491305029710326837274157, 541106433608213985607913120402276000940203625086988929757276286018099336445558864548353610869729642196223750468493, 417269959280528548156948994397262973057821055108288565091113745409730174626359955737489143948177504667498654245449, 165844467199853002181647516786815801413939363188955720855463610698066730208657222822269457713666541555820608908443, 54875733171006797537647859403084623422036246809497621662400918381496284440644503330411668895858884933248328986102, 465819050441857934210906305127374377291850450707906416261994960542649394393702032587209990932960399224341143990297, 369322923825463715724411404444452360125845865658673947242361968271863944079047696087621731311243573179527276498509, 553158781749591211954659671173145767949897795287325677938373702443265138456771264711232588438786042792968904732769, 409812013938165700887519758386718364160025926340003407045361393371862966914817952304595560620453598830906305966865, 494654868138757552768371639418237489264099471894419220273147503624077564865563661914136003656825657044284503346448, 583613295252460993144403074130901622751986348055784728175987246652496523293580989652454868505577305787293683850652, 45623098408168398769971239387495928980835555721564847009059790575158770295430426790200773274288087331109699336204, 39196430635656777174378129146834600960125068266405306877726260536750371354188413207203531511343645151492477471286, 269811462520469960288594953357779332541515563494806499705455036716689694055741096626927182558039773813984145657639, 56129158162087034209035841739296133948708529713411817898928727109770418208078239244331640522507423413446203417794, 524210107239750288249530336771864024916995632570549267972428294539507299820629133801771958736839361325798918246415, 74499040113803277306263886217659673645883223840279171192334357737741618882160648968176974754905084576184804774369, 537566085689080717108870646705458338163437075433046077845999622035879463636776663759447985884960181167857417860517, 67053890181708018909161683393261532526993578729770554741021482840348299866927821016301415949708659944497709907470, 226687291544149270579995169198961617407190234578516732237756117257869929434434889879973211444301745820066870869034, 30119130560797352224094299766590747178156378314088092947830899847927767559391822485618397327733723834195435500170, 273554685078063587415670757725663508130498751998110442807136494763920302805098071555958936900406570453984774374060, 87980277743580170573607118853300224477595233902389343863665172738347967268089655736029345194767280704236057718111, 415325115863346791298232938393411393462777451386243842830553121689594926353646948497680883539360608323603975987452, 291860381996369849963997875749710331697722876276851205203280910491894467229365951220031470367159168511107680106262, 554653569462940342418063467925252548314485118886100002832290030505991378878498660088540140703141291011055029173137, 323189774384600834625013268084915768916855209746568551595158521873406091567687194674213765428238599317205811518692, 271805885895959097314720980134407607645324820417975238169874050425279962478579515969226563851125481000349196674810, 273580504244152469063405670227951980303621824057876058884978331188257821496852334599050020207990127348359965113465, 89994080154200685717636930068317931325931168723237899144166312528962957042842197915530047017893088501681215899095, 179903529806043505032581494908566846659773117049401056767669943330229935007822437549131470977810261112485254094386, 337553339737054880017288314951575451797426862530219763936855885416298554494199226261714888518914541341927073075939, 55576723594346882914517616915509260915444308762551400560217462518909289055446940809390878002725822401595827206530, 16748220768196858904499918524709172735166549515085689048938405549141121222201553686060172878474455615920723669801, 317380564633191615800168658676142557493413060315417096622564923156521630376263849705099633192226251101432134441153, 533990888376667129575141849433166253104032964155895368357797314378260092470904627861359175864364684662961150582207, 51339665999563119517609216115086272052501396280925354694804471629521639434841281422984348587180771099209184749005, 598751671521816401429095343374521592165563401213195481604556405443389323390172923217639290327197434030974530635632, 502516418942980462174586089858060912235797554801782186782319843655355616321036648106166017773986280053024012403712, 96757697084956246010025820107260538706827163135748809142998937362457169471061108292297066769079020843197361323396, 160715027762704553320571142674023737670353756130518440136900430091151963142004047232920245715827837173811719927140, 279138292123840748082780689543574043699162822819208361733228093396335579794292477744981338016264347327181324984710, 76445842054689324523514421681098261857514827631364695255959418519245612571199123499205752729124353901548286671941, 383675319414133753635121914615218464358220814208747712016103562476157464944897131756675168140846189629485664787044, 260741648290568813857849033448155840373964568801980310694295413631289231242930901519918814851819352903132884286000, 572815144956474380133620797676157654285774633299428534205241845335783095326631133195133798583360396067031309578073, 326258465939147178368353573060965288327891986807699582822092415027094204965326681853802159504539722937811913340954, 270266570242986488258809014590807152136633692716132669770748395523214017062557603428657196661342410476403164567952, 594635668324174018778140793057815156885870465660609865234586849536688338135131804764199647040009222634146148815637, 112066852946512058163194024984815176069074331367673763590415760757313750687675218022751871678411881684718198988959, 72643140251973593561700085821570131390914743121754868577502110904091989089708201436984242838820806097191225214858, 418558767829526524235103555737958351573183096833081038769308995724925326439890724874671213539641031754157727776067, 196559288823369030489094238610617412012659194878611686482089456487889879135369906410569754176462601644487717691079, 484475844260869041475828428835126624027291693283800645559775410528136122290210564467730445814182429120097372738911, 397895531572254423225385975618860549078025992059379971480526615942245245283818149065605766495091059477544617632303, 173098235745543952336517747078283517802667869630628062474315240281111485771833849083340162673485620557610425012773, 395438744730241817782361196255681827924847041028664896503460681041226871979986416514203189980456170013127549062319, 470021990867207717347003710359490169212637212255796418181420825247262094876084196634243149241752002339736588912053, 116393009019558569654503508922282193810180596603376432764270301486325221610807518426481578453602546466299515294456, 312679236344738874814229979243462639486594453393064312671149009880980836289564409215088541509970023077739205203468, 125633612607015147027292740679836345332097512816636698981581758992992116056276272361001165705597842757882238693825, 550545747650576990464265884382499274254872311986381675090751886824037811235625095205217845451891396561893492715391, 582344947379262203945082609921047126789902458640974947174265099323728700596079597139164883619347159500887293859913, 597445807393853093495564866081359122814348105478914638258595339515168987499771664924728981250079847198831836930965, 203086100710322798737771097067197649738932976573837729229038404179992238381339090779534246758253939763462200026384, 366083021996787911206272856169665720981308167177143125303074466648545813452157612764258146407782634619278092168081, 568425067761875823198893591966757461338470700675615033946429149483970138055665377562238998722395767377075284081587, 292063178202410186631443519138674436645163233411161937085629856088259050827382985093506892763617302007759121037731, 572237520943575841301998365238940412928982617335768155394691567092595694943290938278464533099223273214233507106207, 130730938892686892107630262721901246969052318133502728671984157629171554435251506312878040499761922665301495030981, 185117108148352276973404708807613996548096583954940273525781406848525491758486946236965943611210198389159091280333, 37060990092986925132287820152354618271473589014825595897838753632315007172710154561879917551705194656825456571032, 403396730776194870459199627544122636010870768257463359235766775533882938128146112838489577777497432203020030499998, 390519053219213422305599109947414047895590808796368085342860468917268018310638864392199371679272174634278410878307, 128444781947873592602609418783055715736876557725608932301613294446934930933474014020041434831899064316552264614235, 543291373538613455155809248493830432520680330961337677793905220928838352322514565851452650441518480234729892153780, 488514444383813071753894478409325136755661751625837651637348989332739608743318097848609715931362718450900659714726, 345584582429475420526208382863826459005483455209655712636957752389218040279848223862500232738960994712140028026289, 93010878843154734421543561265196548806562081923037074596459052686633775723171466088126269822057315393084026072218, 12533412965882925987419497258660569237455714460582608620237638858642686843645624645184949324869641399446820464020, 562770032030414047557952904910126027215456025343530350248616818594366525600180778011275466074764589844321872364272, 128451705070871056157396910591766296038989235798264982434769256144115712608648937222298167066517556774062311420353, 490278961434267039693706795888817653385586689501848271165345121922956317504140732421546020494675482464550410472502, 212287543946551782522399704940695532581109453008804375002654843122502975490312129477869621998080277682674199046031, 351228167329138957128592454766411142609836239330479331051630155591459798299725613134325016512314887321869487481161, 364056580106158102895694571253671943571916920885795142960090311722444269241247963009814588199874030295862636577768, 323410613174912128865174768949092780979646178505039555025194364419990442219941948707117457621400459111231556621585, 555979459475319018276106133189578589964687373772995549423813902773304274184448885651570001083614054140692063026580, 471645896888183848879918063770091917659270906648819201901346651975957177950753583099047587304484006413716362087065, 595746107902898270905714635379070716651708771264047581902664532594897071557252807014533004074458867603957329534516, 557816517693603351719661411054144374250247040672226934534604151399902780319198098821629853612396635344596388943480, 75653615683769023911143698869320584951015514055697266638646507368530841035631560833198288977975782471517557394092, 386729218862361591185009654369415880766336899946663823664818477204172007165198875809899277634660190797185025579614, 393108265477944240661308455550612796769200470498502703905073280606596277788078742986164286625262059483908055127428, 365065802583204450004435661912506592532468753723399406740663534070289404492293680764078659588454240436160849321237, 343474792575856700080726394177083134771079426798042359193966109700850531408037245425173307797050676647933775237484, 449270583610225180914452784540333562631570453995885992409935055758994173533991695282410200635020830187612444056607, 152477148608000973940085532267319492932629609199964217167273279315109403426434432473053141371160594251975646390787, 215758046810520029171417357963508549726865838830930981174495643955719506571398771447950049727234258305885220507020, 388644732079570479249894814593945177309689613386566508292336098907992239994635374799070003303374928382563877494312, 33174396496627497383579687586254392056231321534282758587681567913835717050445163816449882425899904436708697640574, 293328356964375951072242072976851267186828242468018707810599907336525314670450502681522283876131924077746023996643, 292804486280753504026674757794166015519590385505528937148184945726179320137391480944836180610675717906694042510411, 278315915715399524055936806996907092937794467054749462150463756152176847617395557111508306851465386462011262385630, 103884040577296119486012754822466682224025370872916939490159319500421058932999421365377738193002421767097172706341, 111463652129659874006915288174831654634146152513640366449316440114829594116719772451443937868409442532699879776869, 475152124260969797265060453354454799124845717445357239027249597786029156307488697633998763174770332805926500738683, 220597335944113643138040910019263318251616203954548724660953303915089233301354511542662225751359573592406567125779, 460838912228809947843094986154780694841314087685379351551107763714127613789323858795003275958350186756130179585099, 140183105024444619512158726537661171898184380568070161231133567610679885584873426652521827961950911404383912561621, 100258312363732149931656549158547430770829888011033153048299126820116382987576385251423248018523377569893042593237, 405290867185420593972711092047858403431415058957648108848290712855486205273135789994549738296802436972506132007215, 256955277068974586752505570703153051582682851398012077625721880852140628262494489158976679841716540706155916871083, 598549159802958710401362839481280273681933957841944662088149512518476573000011803427513695903373248355980692446393, 308263288681016807641714404434630877489176754884164049322636274036076916608089721011418189274379096133290778967977, 8342859679410179631729508842147337278025979845268212054683951869690623917413242667876438120214556608223950514653, 439895086294728342454449126955941890844828534912064877350830376651948083146591737071488196253116258629344717466258, 91881226123407259536921548434174382841001791568169293198769940131230256611806601058471105885254628422499512141440, 377266324363766263400630205724731218877243980277025204567255708828742612895175112462476548764041808998472515741645, 116673062533491873681185131034931580572262852751033929144868000941380674942800523209276875356733463592351603448680, 57238242567269156027816815706946539463493497634492900168501163766058930300567388616552782194562204025116893421410, 589774086517371498643669747060802896861503240906569357013148621028285639980785543690656162836694887880501379427719, 299125626128142030020988742420785075132372751191528474146303145649473683269241675130370288768899920531289674244113, 304688395547666111898109663337992917557352968749730125549180444196974698222351897080702952045364871753888027443342, 482739851676824100473920409347215848398789318900117561465297399614115666738614477259195415015272146741220074932513, 223546862652113236935862556158177901803806229739994958195958127700830125319767534179348037800919714328649801362322, 150425375689725206871177727482717625428944121456212788472446922564113718518867636855506280578641904259888006038685, 143374483079122348274771015162872747263883105211675941440480524305910827744168931572051691220561136775398957657059, 128633351158033453796356108560970241527889904619011394383277988372280437398843373552825146090070247278923404428730, 249625701621261544438183108711205773478938560640571200325127252485779481701078452759513943692466279038851599018511, 330098489762871879773681019559732262466172018773272582308614672671671001199307865518506835519360693927579848132122, 97272570979206528424127336981516817168566955222510512261839537633559389914877185855268875504270285494647179225542, 74718841026645027941391238796126141775030441881552798010185595153873780524478674202965665888738730228577064111032, 59009205910055868684561742529451214311094377006520731342399475542159755492342086349692903126315766192176134558364, 147954106872023713951463145691216475084430006306060416221364896834795769425749212897622105818492094458111589403860, 555992830271936179812799550002813412539390844307434015514327261249472823762801208645240806724751727789206958497458, 459223438688559571249116685914649450095540121668933258507609746609794374539448063463326591749261191192370815662117, 571393209200912648822312183637054598815269397678580613768957089116765483865121162495918269935152288322187647411253, 177286186824084038346767370297094817293812392957721642873053028629715330336525966361030541938870465423944241324109, 587491267113142201933590855412985429253948652679543672927232780837039223665539177593879438262959884768626979925026, 121073719992748558849282996502703446279240313956823650619682240860630373634948798695523514085879310433388769297911, 326992821821879354165502695961028240084978294787383957718963930070776372845305415470613976088436935751047043512627, 55897462658973985554837453480984923331777372313619418297379632868358904708526448610515770876401568010074036247, 474281517111080897542557845865286041097457650249727914745876496139882777461227076272058949306156001543709356614827, 40880447006931568560802817837347288973549001731224760995212446282117046967004745589464560120352241602331262757637, 199377582253379978414081552664345738394226248383486423477706857549702059554694037264958719644482986837756496613246, 67583806809325529684782118654476643411516600285151896093983454855502714712133346956141976654071062935812737453191, 452546341988439193982297214011678766258506490290911066090290647614068455151806621409756646430532117713333419814200, 63154079944843452528208874183624055953361990336542165468695871390964383215223885775202331596927466794955939855669, 334551033942583568474606741839213957101383590286251155186668543235920975897931743928357631453433934808796703330473, 437000125133660712403788025992205090698484430907657894066272071296035483375078474260228687865444802416063967634962, 79996507523856267942889507576300340014719316733731500178081582238768493408405645914333660158893963260211116177267, 136957270824318341027124989034235585855646981093281453761145461440890955503793684517186875995202144027265329969201, 280204753198588906275980318398478729285287961542920285529979812275266316580102545873587416433404212703776245726478, 537734235993878341769434982550042490365981751251428660237179942734374485415922424357453321846937022328664895920607, 498357256878949571854248804622370932859926894994690120526235824883083753765132401863605500892090016764206939698756, 593183658694608014094449104249771865876595121367209656250471158771632486392533730913932393504513988512194994235126, 471525047958971655208534107052287853913949987926476676197514310320411235020283503103705707957701802098089852040455, 515550195522086342769232739520750768345601850976320014312405876943691700378141377151414091085616391824613041356222, 229784654767967355149909497709811119368560654037206880944035229827691011815016913131119422451043820980926353941725, 217169654015051285238559403576147518221573574303291047729813710960725792892550445720464605476174663800328177597453, 445865555254101127829958642102675927687168710569707725467286103803938348116926832834254624089519482737855028080263, 83946997792088073746354410376458121354546477090285151121896293987266118404260723878401677521317330022928683440101, 472119354862263268431251633432424976904384210603399093568806291862332048310282050100842204125396472101319620313029, 46843467515693389983627938872598324284244171067988563260495985345821466093790361374194115630948136965603015643581, 277302589126799360982750111603442360555051934636756171066424884732490616874962892980005637968336486277371298105284, 37796860324947087933757452089444569583341754367174335457777874936449439863762482510080776848131952814291888228252, 329201662631483519275850208043421059140347420462580260818216051307977255139454956805683010032538225008290753339066, 410958260744814455637908317160979333881545314073457621559204623145344687279791103290567233048673594441768330391568, 391184069150039601440639067557184862816991051523817132396666190555512106382919904848895224325098711230221328168893, 341778180155955688649827271577690269253924367106359453768062062983194302766144996692233530585116870343939549344048, 482885184891891026832543019680624112333051960746415331234199075553060933581630480706330420552017650892318225421994, 227417029879602291913898154454350465334192275455983368980997243946371067766121862949125088496933933053493304375082, 131891059077173823480681683274809296700667012054595015489329798567668841455882278540434006611778254351469315756836, 103977685400575936876007245351080422734569291709540152622222483086840011211808484758839889045266405362833100572217, 430039690420862864710328860317916251552162738538460131045295388990486621940999260820629946807283129550503791042360, 336054039341779369078755981618338727567421739252984379060088264565052065080902800664605952509539644185937023210384, 414650487301520195860820485747902373712957920758077572646321108690388934071745453432265035539090489903222596288408, 589576193361941267176015154197092338077060428665767302320550323024382985851379047593411265195718688560873123744185, 218382333622730104159935425552756841820388948639519923842495333910150980936866251625988964615764772159578862214025, 2542356543181698813075957157401385706512468063673241076844194782908937880847391489213422972872487843717747974071, 19012712934576590810330358701965194246607393288484627129050567402003333386833300009773236871643918870071025370112, 261459449945270346696260426170010104493420330959761424072408598127181246567262293489464049721489266230568086023687, 393057872763078249377870634042993942252544393136978340205701555086856991894130814830449765311294161681995357980571, 31706670785655144489258744219717253455873175486088498446357251628824725653898017817866303775262383346847940227722, 352845629675989592022318947558037109666715372268243939061740352176833050420783754677666411876876865226448815643420, 579523499570692157776642365278787278074363193157128877724940050501652213832135926670258239249988403301949338255538, 534781322034571849183222718240938369181782069830117215874801137890227720544463940037268498986061166881241864175911, 293947547828174245724554745263997068016996177889470503383528004805559670712802640725469343616840367100443153534752, 20256488447976344493484944853334005566670073013412177398480406734598723283264289836587474269370253077015786359305, 475307340957345844876811923970449788514706891727480716267956523131203845997503382023500463149439850432076379159007, 9532193777031501443256432870520743234491840911054244783623102207162388499144070592024440812057106927678514406207, 30376455906399256126534181227692885553266283699913099449205248506625206632827693466133644861846223565145288661633, 310323302397755654510284518631138079981439265632852684852876254116989091445393487579911757256043570018377230904180, 407387187512823516321154849212634322952876110252179375736935664859854509488826142049903683991617538259494461983206, 211765773488300500716796064525502573590145731868562963063378748592341237756767589777342751660513980880169703658019, 118119996850569812443799306306875048213209686043987665925365129711742300844060014347898233682054000714610165352429, 456288037921986114882644161559494182818651772335241262800783776696209877706906644069180867207555069937013686421247, 321798425169971169912343295962697085577508076571119888196289113181080013814133443673221049860354996979915353284172, 324976521789232911848337505841284978746361536915903971011255451438673522500730537005137182463678372897314198988595, 395621759076694189110473461483468243816716472466025836871653502259071450104902960119128530517955567830675053452079, 539300517585750216948117617165146582589224695990488749904551961039061424290129525221984586819908097960720708938354, 29279302128607422250205549520059282069518559284219582605487413142781822276106373289432262133635053599391124926385, 554047387889265384869858916477442181952403597250555948392949469296673941793381852004501421929101000148453680659392, 117780825424837288494479009381221759361151487239443821133102414888864152904732196195473813006762420646998382258677, 513764579681988270425418630365712613073908798769959690739998792846173650211508078458011456784363312999085649615413, 421686906289957894155024887354760839265000904451245772175308131137467275202489561700021659858819873604538650489994, 420037832423259525388141394520857134457021929872555809167052539034540217718781279113965175987358081438109891771580, 36451605745112040602804954235939462081346791770310181663631699054048414835838956409055640948581948016033003511333, 65866443469866248828119099994518897685990064406903627156894902667947376070679854260383038634727146436274230980496, 27676413701492447763964945205769602759768347623741189980278225943728587187940271050634054217590942659542302722334, 500312789935788689187812810985806111797362028998353677843819125485045576943472901976055579663665267905809820905862, 520064354401353505774803720281331074080600746212325401527048530022713769008774050816490541356142354757805595273068, 495854656037423684061417113244964481431602915324717605570975073575414392233479237472936965636133612283412033946051, 91739870792230359210043046401786959190045929124141709653873699398574077579395785555200462734509728806350612588545, 484531754577892922131892661653620989224382080321025512011181426678442547912964573223048519566085582623517825865418, 112714684344084391078866980839255594355187885339701715768009153551270432322826715969989728340963213693095849427668, 404429204723786534299525333122163342588586991421902466839808468487493896330979873416105908841447535426923681220957, 92404742424217640040375362532444172359091402942418950195520660310216430170054358290537973281349284862065214755739, 224043393969043013532511880223075809120842856165608086692928112430171548569493398551019081676395857489451126409940, 4305919427803364191555497499680058924116536587126751817219863902878291078989381194676206640960307162723876513248]
Ciphertext = 45690752833299626276860565848930183308016946786375859806294346622745082512511847698896914843023558560509878243217521
N = 10
M = []
for i in range(272):
row = [0 for _ in range(272 + 1)]
row[i] = 1
row[-1] = N*PublicKey[i]
M.append(row)
M.append([1 / 2 for _ in range(272)] + [N * Ciphertext])
M = matrix(M)
L = M.LLL()
for i in L:
if set(i) == {0, -1/2, 1/2}:
found = i
break
flag = ""
for i in found:
if i == -1/2:
flag += "1"
else:
flag += "0"
print(flag[:-1][::-1])
```
**Flag: crypto{my_kn4ps4ck_1s_l1ghtw31ght}**
## Knapsack Low-density Multiple Subset Sum Problem
Cũng giống như trên, nhưng mà giờ là sẽ nhiều hơn 1 đích đến.
Này sẽ giải quyết vấn đề cho câu hỏi recover $(e_1,e_2,...,e_n) \in \{0,1\}^n$ từ các trọng số $a_{ji} (1 \leq j \leq k, 1 \leq i \leq n)$ sao cho được các đích đến $s_1,s_2,...,s_k$.
$$\displaystyle\sum_{i=1}^{n} e_i*a_{1, i} \ = s_1$$
$$\displaystyle\sum_{i=1}^{n} e_i*a_{2, i} \ = s_2$$
$$\cdot \cdot \cdot \cdot \cdot \cdot \cdot$$
$$\displaystyle\sum_{i=1}^{n} e_i*a_{k, i} \ = s_k$$
Và mật độ của tổng nhiều tập con được xác định bởi công thức
$$d = \frac{n}{k.log_2max(a_{j, i})}$$
Giờ mình sẽ cho bạn một ví dụ để hiểu thêm về cái này.
Ta có 2 giá trị đích và 2 mảng giá trị trọng số như sau
```python
[3,7,19,43,89,195], 260
#3 + 19+43+ 195 = 260
[4,12,16,36,75,162] 218
# 4, 16+36 +162 = 218
```
Từ ví dụ này, ta có thể thấy được rằng chúng có 1 vector cơ sở đó là $(1,0,1,1,0,1)$. Giờ ta sẽ sử dụng ma trận và LLL để có thể recover vector này với mật độ $d \leq 0.9408$.
$$
\begin{pmatrix}
1 & & & &0 &Na_{1,1} &Na_{2,1} &\cdots &Na_{k,1} \\
&1 & & &0 &Na_{1,2} &Na_{2,2} &\cdots &Na_{k,2} \\
& &\ddots & &\vdots &\vdots &\vdots &\ddots &\vdots \\
& & &1 &0 &Na_{1,n} &Na_{2,n} &\cdots &Na_{k,n} \\
\frac12 &\frac12&\cdots &\frac12 &\frac12&Ns_1 &Ns_2 &\cdots &Ns_k
\end{pmatrix}
$$
với giá trị $N \geq \sqrt{\frac{n+1}{4}}$.
Sau khi LLL ma trận này, ta sẽ thu được vector ngắn nhất có dạng $\mathbf{\bar{e}} = (e_1 - \frac{1}{2}, ..., e_n - \frac{1}{2}, -\frac{1}{2}, 0,...,0)$. Đó chính là vector ta cần tìm.
Giờ mình sẽ code sage thử
```sage
M =[
[1 , 0, 0, 0, 0, 0, 0, 5*3 , 5*4 ],
[0 , 1, 0, 0, 0, 0, 0, 5*7 , 5*12 ],
[0 , 0, 1, 0, 0, 0, 0, 5*19 , 5*16 ],
[0 , 0, 0, 1, 0, 0, 0, 5*43 , 5*36 ],
[0 , 0, 0, 0, 1, 0, 0, 5*89 , 5*75],
[0 , 0, 0, 0, 0, 1, 0, 5*195, 5*162],
[1/2, 1/2, 1/2, 1/2, 1/2,1/2, 1/2, 5*260, 5*218]
]
# [3,7,19,43,89,195], 260
# 3 + 19 + 43+ 195 = 260
# [4,12,16,36,75,162] 218
# 4, 16+36 +162 = 218
M = matrix(M)
print(M.LLL())
```
```sage
[-1/2 1/2 -1/2 -1/2 1/2 -1/2 1/2 0 0]
[ -3 0 -1 2 -1 1 -1 0 0]
[ -2 -1 1 2 3 -1 -1 0 0]
[ 3/2 1/2 1/2 -3/2 -3/2 1/2 1/2 -5 0]
[-1/2 -1/2 1/2 -3/2 1/2 1/2 -1/2 0 -5]
[ 3/2 -5/2 -5/2 -7/2 3/2 5/2 -5/2 0 0]
[-7/2 3/2 11/2 -7/2 -3/2 1/2 1/2 0 0]
```
Ta nhận thấy rằng vector đầu tiên chính là vector $(1,0,1,1,0,1)$ cần tìm, đôi khi phải đổi lại dấu để có được giá trị chính xác nhất.
## Modular Subset Sum Problem
Dạng này thì sẽ có một dãy trọng số nguyên dương $a_1,a_2,...,a_n$, số đích là $s$ và modulo $M$, tìm $e_1,e_2,...,e_n$ sao cho
$$\displaystyle\sum_{i=1}^{n} e_i*a_{i} \ = s \ (mod \ M)$$
Bài này thì mình không thấy tài liệu nào sử dụng knapsack, cũng không thấy sử dụng ma trận để tìm, nhưng mình tìm được quả code python khá hay.
```python
import random
def ModularSubsetSum(W, m):
p = 1234567891
r = random.randint(0,p)
powr = [1]
for i in range(2*m):
powr.append((powr[-1] * r) % p)
tree = [0] * (2*m)
def read(i):
if i<=0: return 0
return tree[i-1] + read(i-(i&-i))
def update(i, v):
while i < len(tree):
tree[i] += v
i += (i+1)&-(i+1)
def FindNewSums(a,b,w):
h1 = (read(b)-read(a))*powr[m-w] % p
h2 = (read(b+m-w)-read(a+m-w)) % p
if h1 == h2: return []
if b == a+1:
if sums[a] is None: return [a]
return []
return FindNewSums(a,(a+b)//2,w) + FindNewSums((a+b)//2,b,w)
def AddNewSum(s, w):
sums[s] = w
update(s,powr[s]), update(s+m,powr[s+m])
sums = [None] * m
AddNewSum(0,0)
for w in W:
for s in FindNewSums(0,m,w):
AddNewSum(s,w)
return sums
def RecoverSubset(sums, s):
if sums[s] is None: return None
if s <= 0: return []
return RecoverSubset(sums, (s-sums[s]) % len(sums)) + [ sums[s] ]
sum = (ModularSubsetSum([2,3,5,7,11], 13))
print(RecoverSubset(sum,12))
```
Với các trọng số là $2,3,5,7,11$ và modulo $m = 13$, ta có thể tìm được dãy con có giá trị đích là $s = 12$. Bạn cũng có thể thay giá trị khác vào để test thử.
## Knapsack Multiple Modular Subset Sum Problem
Giờ là kết hợp giữa 2 cái trên. Cho 1 giá trị $q$ là một số nguyên lớn hơn $\sqrt{\frac{n+1}{4}}$, và cho các trọng số $a_{ji} (1 \leq j \leq k, 1 \leq i \leq n)$ là các số nguyên ngẫu nhiên giữa 1 và q - 1. Cho vector $\bar{e} = (e_1,e_2,...,e_n)$ thỏa mãn
$$\displaystyle\sum_{i=1}^{n} e_i*a_{1, i} \ = s_1 \mod q$$
$$\displaystyle\sum_{i=1}^{n} e_i*a_{2, i} \ = s_2 \mod q$$
$$\cdot \cdot \cdot \cdot \cdot \cdot \cdot$$
$$\displaystyle\sum_{i=1}^{n} e_i*a_{k, i} \ = s_k \mod q$$
Thì nếu mật độ $d < 0.9408$ thì ta sẽ có thể tìm được $\bar{e}$ bằng cách sử dụng lattice. Ma trận sẽ khá giống phần ban nãy tìm hiểu, được build như sau:
$$
\begin{pmatrix} 1 & & & &0 &Na_{1,1} &Na_{2,1} &\cdots &Na_{k,1} \\ &1 & & &0 &Na_{1,2} &Na_{2,2} &\cdots &Na_{k,2} \\ & &\ddots & &\vdots &\vdots &\vdots &\ddots &\vdots \\ & & &1 &0 &Na_{1,n} &Na_{2,n} &\cdots &Na_{k,n} \\ & & & & &NM & & & \\ & & & & & &NM & & \\ & & & & & & &\ddots & \\ & & & & & & & &NM \\\frac12 &\frac12&\cdots &\frac12 &\frac12&Ns_1 &Ns_2 &\cdots &Ns_k \end{pmatrix}
$$
Cũng như Multiple, ta cũng sẽ thu được vector ngắn nhất $\bar{e}$
Ta có ví dụ sau
```python
[3,7,19,43,89,195], 260
3 + 19 + 43+ 195 = 60 % 200
q = 200
[4,12,16,36,75,162] 218
4, 16+36 +162 = 18 % 200
```
Giờ mính sẽ code sage, build ma trận như trên.
```sage
M =[
[1 , 0, 0, 0, 0, 0, 0, 5*3 , 5*4 ],
[0 , 1, 0, 0, 0, 0, 0, 5*7 , 5*12 ],
[0 , 0, 1, 0, 0, 0, 0, 5*19 , 5*16 ],
[0 , 0, 0, 1, 0, 0, 0, 5*43 , 5*36 ],
[0 , 0, 0, 0, 1, 0, 0, 5*89 , 5*75],
[0 , 0, 0, 0, 0, 1, 0, 5*195, 5*162],
[0 , 0, 0, 0, 0, 0, 0, 5*200, 0 ],
[0 , 0, 0, 0, 0, 0, 0, 0, 5*200],
[1/2, 1/2, 1/2, 1/2, 1/2,1/2, 1/2, 5*60, 5*18]
]
# [3,7,19,43,89,195], 260
# 3 + 19 + 43+ 195 = 60 % 200
# q = 200
# [4,12,16,36,75,162] 218
# 4, 16+36 +162 = 18 % 200
M = matrix(M)
print(M.LLL())
```
```python
[-1/2 1/2 -1/2 -1/2 1/2 -1/2 1/2 0 0]
[ -3 0 -1 2 -1 1 -1 0 0]
[ -2 -1 1 2 3 -1 -1 0 0]
[ -1 3 0 0 1 3 -3 0 0]
[ -2 2 2 0 0 -2 -4 0 0]
[ 3/2 1/2 1/2 -3/2 -3/2 1/2 1/2 -5 0]
[-1/2 -1/2 1/2 -3/2 1/2 1/2 -1/2 0 -5]
[ 3/2 -5/2 -5/2 -7/2 3/2 5/2 -5/2 0 0]
[ -3 -2 5 -1 1 2 3 0 0]
```
Ta thấy vector đầu tiên chính là vector cần tìm.
## Hidden Number Problem
Trong Hidden Number Problem, sẽ có 1 số bí mật $\alpha$ và một số modulo public là $n$. Chọn các số random $0 < t_i < n$, tính toán $s_i= t_i.\alpha \mod n$. Và sẽ nhận được những bit quan trọng nhất của $s_i$ cùng với giá trị $t_i$. Ta có thể viết lại được là $a_i + k_i = t_i.\alpha \mod n$ với $k_i < 2^l$ với $l \in {Z}$. Từ đó, ta sẽ được các cặp $( a_i,t_i)$.
Việc triển khai MSB (những bit quan trọng nhất) có thể được tìm bằng code sage này.
```sage
p = next_prime(2^16)
n = ceil(log(p, 2))
# k - The number of significant bits revealed by the oracle.
# Using parameters from Thereom 1.
k = ceil(sqrt(n)) + ceil(log(n, 2))
def msb(query):
"""Returns the MSB of query based on the global paramters p, k.
"""
while True:
z = randint(1, p-1)
answer = abs(query - z)
if answer < p / 2^(k+1):
break
return z
def create_oracle(alpha):
"""Returns a randomized MSB oracle using the specified alpha value.
"""
alpha = alpha
def oracle():
random_t = randint(1, p-1)
return random_t, msb((alpha * random_t) % p)
return oracle
alpha = 23223
oracle = create_oracle(alpha)
print(oracle())
```
Để giải quyết vấn đề này, ta có thể sử dụng ma trận của Boneh and Venkatesan
$$
\begin{pmatrix}n & & & & \\ &n & & & \\ & &\ddots & & \\ & & &n & \\t_1 &t_2 &\cdots &t_m & 1/n \end{pmatrix}
$$
Mục tiêu là vector $(a_0,...a_{m-1},0)$ và vector cơ sở $(t_0.\alpha\mod n,...,t_{m-1}.\alpha \mod n, \frac{\alpha}{n})$.
Ta có thể sử dụng **Babais Nearest Plane Algorithm** để có thể giải được vấn đề này.
```sage
# Some parameters of the game, chosen for simplicity.
# p - A prime number for our field.
p = next_prime(2^16)
# n - The number of bits in `p`.
n = ceil(log(p, 2))
# k - The number of significant bits revealed by the oracle.
# Using parameters from Thereom 1.
k = ceil(sqrt(n)) + ceil(log(n, 2))
def msb(query):
"""Returns the MSB of query based on the global paramters p, k.
"""
while True:
z = randint(1, p-1)
answer = abs(query - z)
if answer < p / 2^(k+1):
break
return z
def create_oracle(alpha):
"""Returns a randomized MSB oracle using the specified alpha value.
"""
alpha = alpha
def oracle():
random_t = randint(1, p-1)
return random_t, msb((alpha * random_t) % p)
return oracle
# d - The number of oracle queries.
# Using parameters from Thereom 1.
d = 2 * ceil(sqrt(n))
def build_basis(oracle_inputs):
"""Returns a basis using the HNP game parameters and inputs to our oracle
"""
basis_vectors = []
for i in range(d):
p_vector = [0] * (d+1)
p_vector[i] = p
basis_vectors.append(p_vector)
basis_vectors.append(list(oracle_inputs) + [QQ(1)/QQ(p)])
return Matrix(QQ, basis_vectors)
def approximate_closest_vector(basis, v):
"""Returns an approximate CVP solution using Babai's nearest plane algorithm.
"""
BL = basis.LLL()
print(BL)
G, _ = BL.gram_schmidt()
_, n = BL.dimensions()
print(G, BL.LLL())
small = vector(ZZ, v)
for i in reversed(range(n)):
c = QQ(small * G[i]) / QQ(G[i] * G[i])
c = c.round()
small -= BL[i] * c
print(small)
return (v - small).coefficients()
# Hidden alpha scalar
alpha = randint(1, p-1)
# Create a MSB oracle using the secret alpha scalar
oracle = create_oracle(alpha)
# Using terminology from the paper: inputs = `t` values, answers = `a` values
inputs, answers = zip(*[ oracle() for _ in range(d) ])
# Build a basis using our oracle inputs
lattice = build_basis(inputs)
print("Solving CVP using lattice with basis:\n%s\n" % str(lattice))
# The non-lattice vector based on the oracle's answers
print(inputs)
u = vector(ZZ, list(answers) + [0])
print("Vector of MSB oracle answers:\n%s\n" % str(u))
# Solve an approximate CVP to find a vector v which is likely to reveal alpha.
v = approximate_closest_vector(lattice, u)
print("Closest lattice vector:\n%s\n" % str(v))
# Confirm the recovered value of alpha matches the expected value of alpha.
recovered_alpha = (v[-1] * p) % p
assert recovered_alpha == alpha
print("Recovered alpha! Alpha is %d" % recovered_alpha)
```
```
Solving CVP using lattice with basis:
[ 65537 0 0 0 0 0 0 0 0 0 0]
[ 0 65537 0 0 0 0 0 0 0 0 0]
[ 0 0 65537 0 0 0 0 0 0 0 0]
[ 0 0 0 65537 0 0 0 0 0 0 0]
[ 0 0 0 0 65537 0 0 0 0 0 0]
[ 0 0 0 0 0 65537 0 0 0 0 0]
[ 0 0 0 0 0 0 65537 0 0 0 0]
[ 0 0 0 0 0 0 0 65537 0 0 0]
[ 0 0 0 0 0 0 0 0 65537 0 0]
[ 0 0 0 0 0 0 0 0 0 65537 0]
[ 31181 61379 53230 21935 8582 15108 60375 17258 54605 36393 1/65537]
(31181, 61379, 53230, 21935, 8582, 15108, 60375, 17258, 54605, 36393)
Vector of MSB oracle answers:
(50494, 11104, 43501, 31498, 40928, 56575, 48978, 55830, 19406, 3011, 0)
[ 0 0 0 0 0 0 0 0 0 0 1]
[ 155 -4548 11316 -6270 6077 -7874 -7443 -9116 1377 6045 24873/65537]
[ 8509 6558 3050 395 16916 287 4075 -11237 -4320 4166 18345/65537]
[ -213 1176 -11745 4388 -17653 -2287 -1188 -8191 -4852 -8307 -18536/65537]
[ 6518 8320 -1507 -9972 -12097 9678 4970 -5342 -444 -7946 15539/65537]
[ 11928 -319 2350 16420 5513 -3002 991 -63 9564 6433 -10576/65537]
[ -13343 1670 6393 -3577 -14480 9347 -7037 -9737 -7336 3919 -32564/65537]
[ -5463 -1222 17220 -993 -7849 2265 -2778 375 -754 -16446 3657/65537]
[ -3619 4289 -7559 6864 9904 13449 -6339 -12096 1252 -10067 1055/65537]
[ 4774 4103 -5367 3495 3668 -6586 -19526 7590 -10018 -10425 32074/65537]
[ 236 -17918 -7294 3138 10944 14226 -3299 -4155 -15239 9204 17153/65537]
[ 0 0 0 0 0 0 0 0 0 0 1]
[ 155 -4548 11316 -6270 6077 -7874 -7443 -9116 1377 6045 0]
[ 3917383275181/463940749 3931248348438/463940749 -796240863982/463940749 1408477621895/463940749 6660514824080/463940749 1671809744411/463940749 3344995569211/463940749 -3431944162481/463940749 -2273303677284/463940749 751523395994/463940749 0]
[ 136322268497/54838829 86002763286/54838829 -367737216643/54838829 123026777307/54838829 -559441920212/54838829 -276669164164/54838829 -143335579478/54838829 -821348612978/54838829 -312352422239/54838829 -264716788252/54838829 0]
[ 31173132809/6065536 16743065075/3032768 34760103893/6065536 -81651565245/6065536 -9329126413/1516384 13051234791/1516384 8718845869/3032768 -6689033905/3032768 16405811673/6065536 -5573200943/1516384 0]
[ 6931389731/588643 -8061051/53513 2317912616/588643 5619535602/588643 -2779030948/588643 -265686998/588643 -102499868/588643 -204672051/588643 6843045855/588643 1699243336/588643 0]
[ -108463735/14097 15991028/4699 85001489/14097 33358333/4699 -58131319/14097 154667320/14097 -36045350/14097 -20447544/4699 -16580861/4699 117901063/14097 0]
[ -1376277/661 196611/1322 15794417/1322 9109643/1322 2424869/1322 -393222/661 458759/661 458759/1322 -1966110/661 -20644155/1322 0]
[ -851981/278 -589833/278 -917518/139 0 917518/139 1179666/139 -1376277/139 -1376277/278 2687017/278 -917518/139 0]
[ 65537/8 65537/8 0 0 0 0 -65537/4 65537/8 -65537/8 0 0]
[ 65537/7 -131074/7 0 0 0 65537/7 0 0 -65537/7 0 0] [ 0 0 0 0 0 0 0 0 0 0 1]
[ 155 -4548 11316 -6270 6077 -7874 -7443 -9116 1377 6045 24873/65537]
[ 8509 6558 3050 395 16916 287 4075 -11237 -4320 4166 18345/65537]
[ -213 1176 -11745 4388 -17653 -2287 -1188 -8191 -4852 -8307 -18536/65537]
[ 6518 8320 -1507 -9972 -12097 9678 4970 -5342 -444 -7946 15539/65537]
[ 11928 -319 2350 16420 5513 -3002 991 -63 9564 6433 -10576/65537]
[ -13343 1670 6393 -3577 -14480 9347 -7037 -9737 -7336 3919 -32564/65537]
[ -5463 -1222 17220 -993 -7849 2265 -2778 375 -754 -16446 3657/65537]
[ -3619 4289 -7559 6864 9904 13449 -6339 -12096 1252 -10067 1055/65537]
[ 4774 4103 -5367 3495 3668 -6586 -19526 7590 -10018 -10425 32074/65537]
[ 236 -17918 -7294 3138 10944 14226 -3299 -4155 -15239 9204 17153/65537]
(50258, 29022, 50795, 28360, 29984, 42349, 52277, 59985, 34645, -6193, -17153/65537)
(50258, 29022, 50795, 28360, 29984, 42349, 52277, 59985, 34645, -6193, -17153/65537)
(46639, 33311, 43236, 35224, 39888, 55798, 45938, 47889, 35897, -16260, -16098/65537)
(57565, 35755, 8796, 37210, 55586, 51268, 51494, 47139, 37405, 16632, -23412/65537)
(57565, 35755, 8796, 37210, 55586, 51268, 51494, 47139, 37405, 16632, -23412/65537)
(21781, 36712, 1746, -12050, 39047, 60274, 48521, 47328, 8713, -2667, 8316/65537)
(8745, 20072, 4760, 7894, 63241, 40918, 38581, 58012, 9601, 13225, -22762/65537)
(7893, 24776, -42220, 25446, -7371, 31770, 33829, 25248, -9807, -20003, -96906/65537)
(-616, 18218, -45270, 25051, -24287, 31483, 29754, 36485, -5487, -24169, -115251/65537)
(4, 26, -6, -29, 21, -13, -18, 21, 21, 11, -15759/65537)
(4, 26, -6, -29, 21, -13, -18, 21, 21, 11, -15759/65537)
Closest lattice vector:
[50490, 11078, 43507, 31527, 40907, 56588, 48996, 55809, 19385, 3000, 15759/65537]
Recovered alpha! Alpha is 15759
```
Nhưng mà hầu hết sử dụng ma trận của Kannan như sau
$$
\begin{pmatrix}n & & & & & \\ &n & & & & \\ & &\ddots & & & \\ & & &n & & \\t_1 &t_2 &\cdots &t_m & B/n \\a_1 &a_2 &\cdots &a_m & & B \end{pmatrix}
$$
Thắc mắc $B$ là giá trị gì đúng không, ban nãy mình có viết HNP có thể viết bằng $a_i + k_i = t_i.\alpha \mod n$ với $k_i < 2^l$ với $l \in {Z}$, thì giá trị $B = 2^l$.
Lattice này chứa vector $(k_0,k_1,...,k_{m-1}, \frac{B.\alpha}{n},-B).$ Giờ mình sẽ lấy ví dụ nha, vẫn lấy thuật toán như trên nhưng mà sẽ dụng ma trận khác. Nhưng trước hết, ta cần phải tìm giá trị B đã.
```python
def msb(query):
"""Returns the MSB of query based on the global paramters p, k.
"""
while True:
z = randint(1, p-1)
answer = abs(query - z)
if answer < p / 2^(k+1):
break
return z
```
Vì giá trị answer rất nhỏ, bạn tính ra thì chỉ tầm dưới 50 thuiii, nên mình sẽ lấy $B = 100$ nha.
```python
p = next_prime(2^16)
# n - The number of bits in `p`.
n = ceil(log(p, 2))
# k - The number of significant bits revealed by the oracle.
# Using parameters from Thereom 1.
k = ceil(sqrt(n)) + ceil(log(n, 2))
def msb(query):
"""Returns the MSB of query based on the global paramters p, k.
"""
while True:
z = randint(1, p-1)
answer = abs(query - z)
if answer < p / 2^(k+1):
print(answer)
break
return z
def create_oracle(alpha):
"""Returns a randomized MSB oracle using the specified alpha value.
"""
alpha = alpha
def oracle():
random_t = randint(1, p-1)
return random_t, msb((alpha * random_t) % p)
return oracle
def build_basis(oracle_inputs, answers, bound):
"""Returns a basis using the HNP game parameters and inputs to our oracle
"""
basis_vectors = []
for i in range(d):
p_vector = [0] * (d+2)
p_vector[i] = p
basis_vectors.append(p_vector)
basis_vectors.append(list(oracle_inputs) + [QQ(bound)/QQ(p)] + [0])
basis_vectors.append(list(answers) + [0] + [QQ(bound)])
return Matrix(QQ, basis_vectors)
# return basis_vectors
d = 2 * ceil(sqrt(n))
alpha = randint(1, p-1)
# Create a MSB oracle using the secret alpha scalar
oracle = create_oracle(alpha)
# Using terminology from the paper: inputs = `t` values, answers = `a` values
inputs, answers = zip(*[ oracle() for _ in range(d) ])
print("alpha is:",alpha)
bound = 100
M = (build_basis(inputs,answers, bound))
print(M.LLL())
```
```sage
11
24
31
3
20
15
13
29
30
12
alpha is: 3620
[ 0 0 0 0 0 0 0 0 0 0 -100 0]
[ -11 -24 -31 -3 -20 -15 13 -29 30 12 -362000/65537 100]
[ 502 4591 6563 -2853 -73 -3011 4175 -2950 990 -13111 872500/65537 2500]
[ -15865 2802 -846 2441 -4372 2224 2329 -1075 -12855 -10243 -1697200/65537 2700]
[ -17186 -3598 2433 -6742 5944 3303 11588 -8709 1792 -5170 -2085400/65537 -4500]
[ 1994 18857 -5525 8009 -3809 -4071 -2822 926 544 8481 -796700/65537 1300]
[ 9514 5381 4231 -14756 3396 10301 -5893 5749 -1174 -5866 -2724500/65537 8900]
[ -4269 -4536 -6434 12486 -8845 3016 -11589 -2188 5882 -10194 -1638900/65537 -4200]
[ 2831 1900 -17206 -5266 14471 2200 6216 2735 7989 -1796 -2412400/65537 -3700]
[ 6310 8674 -7348 3248 -6737 13222 11411 6340 3615 -5612 -1253700/65537 1200]
[ 4930 2225 16912 1081 15879 4217 831 11965 4571 6138 2632200/65537 11400]
[ -10582 2337 -8177 -9985 -16531 -1016 2998 12659 1349 -3177 -2462600/65537 -3600]
```
Ta thấy rằng dòng thứ 2 sẽ là vector có dạng $(k_0,k_1,...,k_{m-1}, \frac{B.\alpha}{n},-B).$ Nếu mà là $B$ thì ta chỉ cần đổi dầu thôi. Do đó ta tìm được giá trị $\alpha$ cần tìm.
```python
alpha = M.LLL()[1][-2]
alpha = -alpha*p//bound % p
print(alpha)
```
## Resources
https://hackmd.io/@nomorecaffeine/r1xstVfxC
https://eprint.iacr.org/2011/525.pdf
https://kel.bz/post/hnp/
https://eprint.iacr.org/2020/1540.pdf
Sign in with Wallet
Connect another wallet