<h1 style="text-align:center;">FITM</h1>


:::spoiler **server․py**

from Crypto.Util.number import *
import random
import os

class idek():

	def __init__(self, secret : bytes): 

		self.secret = secret
		self.p = None	

		self.poly = None 

	def set_p(self, p : int):

		if isPrime(p):
			self.p = p

	def gen_poly(self, deg : int):

		s = bytes_to_long(self.secret)
		l = s.bit_length()
		self.poly = [random.randint(0, 2**l) for _ in range(deg + 1)]
		index = random.randint(deg//4 + 1, 3*deg//4 - 1)
		self.poly[index] = s

	def get_share(self, point : int):

		if not self.p or not self.poly:
			return None

		return sum([coef * pow(point, i, self.p) for i, coef in enumerate(self.poly)]) % self.p

	def get_shares(self, points : list[int]):

		return [self.get_share(point) for point in points]

def banner():

	print("==============================================")
	print("=== Welcome to idek Secret Sharing Service ===")
	print("==============================================")
	print("")

def menu():

	print("")
	print("[1] Oracle")
	print("[2] Verify")
	print("[3] Exit")
		
	op = int(input(">>> "))
	return op

if __name__ == '__main__':

	S = idek(os.urandom(80))
	deg = 16
	seen = []

	banner()

	for _ in range(17):

		op = menu()
		if op == 1:
			p = int(input("What's Your Favorite Prime : "))
			assert p.bit_length() == 64 and isPrime(p) and p not in seen
			seen += [p]
			S.set_p(p)
			S.gen_poly(deg)
			L = list(map(int, input("> ").split(",")))
			assert len(L) <= 3*deg//4
			print(f"Here are your shares : {S.get_shares(L)}")
		elif op == 2:
			if S.secret.hex() == input("Guess the secret : "):
				with open("flag.txt", "rb") as f:
					print(f.read())
			else:
				print("Try harder.")
		elif op == 3:
			print("Bye!")
			break
		else:
			print("Unknown option.")

:::
++**Mô tả:**++ Để nhận được **Flag** thì ta cần gửi cho server đúng giá trị của $\text{secret}$ với $\text{secret}$ là $80$ bytes ngẫu nhiên được tạo thông qua đoạn `S = idek(os.urandom(80))`.

Thông qua phương thức `gen_poly` của **class** `idek` ta biết rằng giá trị $\text{secret}$ sẽ được chọn làm **hệ số** cho một **hạng tử** nào đó có bậc $\in [5, 11]$ của một đa thức có bậc là $16$:

def gen_poly(self, deg : int):
    s = bytes_to_long(self.secret)
    l = s.bit_length()
    self.poly = [random.randint(0, 2**l) for _ in range(deg + 1)]
    index = random.randint(deg//4 + 1, 3*deg//4 - 1)
    self.poly[index] = s

Ở hàm `__main__` Challenge cho phép ta gửi $17$ lần **option** với các option là:
- ++**option 1 (Oracle)**++: Gửi một số nguyên tố $p$ dài $64$ bit (không trùng các số đã gửi) để làm **modulus** cho một đa thức $f$ bậc $16$ tạo bởi `gen_poly`, và một tập **tối đa** $12$ giá trị $x_i$ để server trả về tập giá trị của các $f(x_i)$.
- ++**option 2 (Verify)**++: Gửi cho server giá trị $\text{secret}$, nếu đúng thì trả về **Flag** (ta cần option này để kiểm tra $\text{secret}$ nên chỉ được phép gửi tối đa $16$ lần option 1 thôi).
- ++**option 3 (Exit)**++: Thoát.

> Vì **option 1** cho phép ta toàn quyền thao túng các đa thức và các giá trị đầu ra nên đây sẽ là option ta tập trung khai thác.

---
>Ý tưởng ban đầu để có được $\text{secret}$

Mỗi lần gửi **option 1**, ta được một đa thức $f_i$ có dạng:
$$f_i(x) = a_0.x^0 + a_1.x^1 + ... + a_{11}.x^{11} + ... + a_{16}.x^{16} \mod p_i$$

Các hệ số $[a_0, a_{16}]$ có giá trị lên đến $640$ bit. Nhưng khi sử dụng modulo $p_i$ thì giá trị của chúng sẽ giảm còn $a_i \mod p_i$, tức khoảng $64$ bit.

Vì vậy ở mỗi đa thức $f_i$, ta chỉ được giá trị của $\text{secret} \mod p_i$ mà thôi, nên ta cần tối thiểu $10$ giá trị của $\text{secret} \mod p_i$ để có thể **CRT** và khôi phục được $\text{secret}$ ban đầu. Nhưng để chắc ăn thì ta cần đến $11$ giá trị của $\text{secret} \mod p_i$.

Biết rằng $\text{secret}$ sẽ nằm đâu đó trong $[a_5, a_{11}]$, vì vậy mục tiêu của ta là phải khôi phục được $7$ hệ số đó, và làm tương tự thêm $10$ lần để được $11$ tập $7$ hệ số, sau đó sẽ **CRT** $11$ giá trị được chọn từ $11$ tập trên đến khi nào cho ra một giá trị $640$ bit thì dừng. Số khả năng sẽ là $7^{11} \approx 2\times10^9$ khả năng.

> Vì vậy mục tiêu là khôi phục được $7$ hệ số $[a_5, a_{11}]$ của từng đa thức và sau đó là brute force CRT.
---

> Nhưng ta cần gửi $12$ giá trị $x_i$ như thế nào để khôi phục được $[a_5, a_{11}]$ bây giờ?

++**Định nghĩa**++ (nth Roots of unity): Roots of unity (căn bậc $n$ của $1$) là tập nghiệm của phương trình:
$$x^n ≡ 1 \pmod {p}$$

Khi ta gửi một giá trị $\alpha$ thỏa mãn $\alpha^{12} \equiv 1 \pmod p$ thì giá trị của $f_i(\alpha)$ sẽ là một đa thức bậc $11$, cụ thể
$$f_i(\alpha) = a_0 + a_1.\alpha + ... + a_{11}.\alpha^{11} + a_{12}.\alpha^{12} + ... + a_{16}.\alpha^{16} \mod p_i$$

sẽ trở thành:
$$
\begin{align}
f_i(\alpha) &= a_0 + a_1.\alpha +... + a_{11}.\alpha^{11} + a_{12}.1 + a_{13}.\alpha + a_{14}.\alpha^2+a_{15}.\alpha^3+a_{16}.\alpha^4 \mod p \\
&= (a_0 +a_{12}) + (a_1+a_{13}).\alpha + (a_2+a_{14}).\alpha^2 + (a_3+a_{15}).\alpha^3 + (a_4+a_{16}).\alpha^4 + a_5.\alpha^5 + ...+a_{11}.\alpha^{11} \mod p
\end{align}
$$

>Ta có thể thấy rằng sau khi giảm đa thức xuống bậc $11$ thì hệ số của các hạng từ bậc $[5, 11]$ không bị ảnh hưởng.

Và chỉ cần $12$ giá trị của $f_i(\alpha)$ là ta có thể khôi phục được một đa thức bậc $11$ bằng cách sử dụng **nội suy Lagrange** rồi. Thực hiện như sau:

from sage.all import *
from Crypto.Util.number import *
from pwn import *

io = process(["python3", "test.py"])

def get_prime(bit):
    while True:
        p = random_prime(2**bit-1)
        if (p-1) % 12 == 0 and int(p).bit_length() == 64:
            return p

p = get_prime(64)
F = GF(p)

io.sendlineafter(b">>> ", b"1")
io.sendlineafter(b"What's Your Favorite Prime : ", str(p).encode())

# 12 nth roots of unity
xs = F(1).nth_root(12, all=True)
io.sendlineafter(b"> ", (str(xs)[1:-1]).encode())

io.recvuntil(b"Here are your shares : ")
shares = eval(io.recvline())
print(f'{shares = }')

# dùng nội suy lagrange để khôi phục đa thức
f = F['x'].lagrange_polynomial([(x, y) for x, y in zip(xs, shares)])
print(f"{f = }")

# các hệ số từ hạng tử bậc 5 -> bậc 11
print("coeff =", list(f)[5:12])

shares = [13379219776720937450, 3326527810211339491, 2378981999536643856, 7840626321412605432, 4485945519959469335, 12757951963989228338, 8072494239011614900, 10970588307241728698, 3727521368134737807, 2249841198579344259, 4225367033123703864, 2569351500044112903]

f = 7716181063822066518*x^11 + 4875901018263340840*x^10 + 10461334028605144605*x^9 + 14157561016959196210*x^8 + 2987340253583948559*x^7 + 11144078947878743074*x^6 + 10015271764829555125*x^5 + 97274108209637550*x^4 + 5932895930200515590*x^3 + 5872318399395312417*x^2 + 11265107907658820477*x + 5061902303723639150

coeff = [10015271764829555125, 11144078947878743074, 2987340253583948559, 14157561016959196210, 10461334028605144605, 4875901018263340840, 7716181063822066518]

>Có được $f_i$ là ta có được $7$ hệ số $[a_5, a_{11}]$ rồi.

---

Làm tương tự như trên thêm $10$ lần để có được $11$ tập các hệ số, sau đó brute force **CRT** $11$ khả năng của $11$ tập đến khi nào nhận được một giá trị $640$ bit thì gửi đến cho **server**, số khả năng $\approx 2\times 10^9$.

>Nhưng brute force như vậy thì không ổn 💀
Bởi vì $7^{11}$ rất lớn, khi mình test thì thấy máy chỉ chạy được $10^6$ lần trong $1$ phút, tức để chạy được $7^{11}$ lần thì cần đến $\approx \frac{2\times10^9}{10^6} \approx 2\times 10^3$ phút, gần $33$ tiếng 💀
Đã có cao thủ sử dụng **Go** và thuật toán **DFS** để brute force và thành công nhưng mà mình không rành cái này lắm nên hướng này bị phá sản 💀

---

Nhưng. Thay vì brute force, ta có thể chuyển bài toán **CRT** trên thành bài toán **CVP** và có thể sử dụng **LLL** để giải.

Gửi $16$ lần **option 1** để nhận được $16$ tập giá trị hệ số, ta có công thức **CRT** của $\text{secret}$ là:
$$\text{secret} = \sum_{i=0}^{15} a_i.P_i.(P_i^{-1}\mod p_i) \mod {P}$$

với $a_i$ là một giá trị ta chưa biết trong $7$ giá trị của từng tập, $P_i = P_i/p_i$ và $P = \prod p_i$.

Có đến $7\times 16 = 112$ giá trị của $a_i.P_i.(P_i^{-1}\mod p_i)$ nên ta sẽ sử dụng **LLL** để tìm ra tổ hợp nào cho ra tổng là $\text{secret}$ và tổ hợp tuyến tính sử dụng chỉ là $(0, 1)$.

Ta thực hiện như sau:

from sage.all import *
from Crypto.Util.number import *
from pwn import *

# 16 modulus và 16 tập giá trị của coeffs
moduli = [14207592708883017181, 10012797967413308521, 11256947420891896081, 15975084889170437929, 17352751759822822633, 11305923156573456013, 14593219012188673453, 13028403860447837233, 16773430975492615273, 12392266231593005929, 16311518893738925449, 12408889590198605293, 13209029987801343757, 10320808321062007669, 14538777260494265533, 15096024307049373229]
coeffs = [[7343786932122325788, 1531708632736406932, 7021093627964790724, 6155594654744319344, 2422029046288643143, 7149146699413499132, 7203011443081298618], [6085707018947905289, 9802821445233360662, 4198696477676754188, 6877002068981497756, 7850379469552284297, 7810865182318498775, 7778948996438779628], [8266598966889430248, 7547472533347860409, 2205584723401481736, 5547521719210223797, 9419998638534745648, 1973569764662589423, 6706195781171471785], [9752900188060296443, 14025237253959351487, 9300002187186108083, 12177018658621629065, 1332546373463644867, 13748106986933465445, 11567633185563406358], [11226320921940378620, 7865068582733153698, 15824106775668779270, 11398280201559368473, 3854916402690351366, 3233613526002374193, 545159241023866157], [2813168747139545150, 9559059035093731563, 3279531677162254089, 1843958335543221092, 7134962343848721586, 122195966153949728, 8945421196172024792], [13027449536398214230, 14399482603885139478, 6455073347686062903, 2262664515083279283, 10078080638004842669, 4515699677890080372, 9978361395510574876], [8011829286750794337, 936658106626424326, 5298959105330075419, 6284448660381861918, 1102143692394838763, 7214216707027995568, 3321217169949202036], [4712385194088114124, 9013625163786438384, 6987095292730357855, 11512636866253912693, 7453727719704408568, 15947227039550694676, 13168365016120621025], [3674828986210200099, 4774108316783110607, 3973516658292580817, 2191538702742486655, 7755709720415714551, 1985226935163765291, 439299652395380688], [6698711644255747188, 11100718334240470016, 5229774246649697075, 15103289510908680522, 5972568158999580397, 9498352337980224350, 2379323689291447578], [6854948825770222294, 1918962678799687610, 4879308337682420766, 8259745771639878097, 9924549129519379880, 4575883341865904976, 6991552479239543226], [9705946746392421278, 1608745003511901650, 1395490988051377120, 1206958117269760111, 3717045757465239245, 11627440754935760666, 5561500230315604780], [6107556501545361289, 4449341385089113259, 6814934533985398327, 487981438438091022, 7415310943221260965, 9343172500687412919, 4794309107188561321], [8844549216553889500, 1062352798333546710, 464227322414474632, 11824807292376098493, 6177587828518586839, 8237008110648216543, 8837995601519053808], [8604656886838668891, 7983430122303026108, 11462360679587955497, 5946428625809837994, 12311880808624393594, 10161119410794904924, 11465177300754799498]]

P = prod(moduli)
cols = []
for coeff, prime in zip(coeffs, moduli):
    Pi = P // prime
    Pi_inv = int(pow(Pi, -1, prime))
    cols += [int(Pi * Pi_inv * xi) for xi in coeff]

M = block_matrix(ZZ, [
    [column_matrix(cols), 1],
    [P, 0]
])

W = 2**641
Ws = diagonal_matrix([W] + [1] * len(cols), sparse = 0)
print("❕LLL...")
M /= Ws
M = M.LLL()
M *= Ws

for row in M:
    if len(set(row[1:])) == 2 and int(row[0]).bit_length() <= 641:
        print(row, "✅")

❕LLL...
(254380118451082565644902058727558798861513860749836719760818192753904765370781760018310415757187599933465947585268880254201651083219299741602457552623709288296160034182746333720719936831529963, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0) ✅

Vậy là ta tìm được giá trị của $\text{secret}$ rồi, ta chắc chắn rằng đây là giá trị đúng vì tổ hợp tuyến tình mà **LLL** sử dụng chỉ bao gồm $1$ và $0$ thôi.

Sau đó gửi $\text{secret}$ với **option 2** và ta sẽ nhận được **FLAG**.
++**Solution:**++

from sage.all import *
from Crypto.Util.number import *
from pwn import *

io = process(["python3", "test.py"])

def get_prime(bit):
    while True:
        p = random_prime(2**bit-1)
        if (p-1) % 12 == 0 and int(p).bit_length() == 64:
            return p

moduli = [get_prime(64) for i in range(16)]

coeffs = []
for i in range(16):
    p = moduli[i]
    io.sendlineafter(b">>> ", b"1")
    io.sendlineafter(b"What's Your Favorite Prime : ", str(p).encode())
    F = GF(p)
    xs = F(1).nth_root(12, all=True)
    io.sendlineafter(b"> ", (str(xs)[1:-1]).encode())
    io.recvuntil(b"Here are your shares : ")
    shares = eval(io.recvline())
    
    # dùng nội suy lagrange để khôi phục đa thức
    poly = F['X'].lagrange_polynomial([(x, y) for x, y in zip(xs, shares)]).list()[5:12]

    # chuyển về int chứ để GF(p) sẽ ảnh hưởng đến LLL
    coeffs.append(list(map(int, poly)))

P = prod(moduli)
cols = []
for coeff, prime in zip(coeffs, moduli):
    Pi = P // prime
    Pi_inv = int(pow(Pi, -1, prime))
    cols += [int(Pi * Pi_inv * xi) for xi in coeff]

M = block_matrix(ZZ, [
    [column_matrix(cols), 1],
    [P, 0]
])

W = 2**641
Ws = diagonal_matrix([W] + [1] * len(cols), sparse = 0)
print("❕LLL...")
M /= Ws
M = M.LLL()
M *= Ws

# đề phòng trường hợp hex thiếu bit 0
def pad_to_mul2(a):
    while len(a) % 2 != 0:
        a = "0" + a
    return a

for row in M:
    if len(set(row[1:])) == 2 and int(row[0]).bit_length() <= 641:
        print(row, "✅")
        io.sendlineafter(b">>> ", b"2")
        io.sendlineafter(b"Guess the secret : ", pad_to_mul2(hex(abs(row[0]))[2:]).encode())
        flag = io.recvline()
        print(flag)


# Ghi Chú
- Nếu trong quá trình **LLL** mà không tìm được vector mong muốn thì hãy chạy lại code nhiều lần, sau 2-3 lần thử là sẽ tìm được giá trị của $\text{secret}$.

- Lý do mà ta scale ma trận bằng cách chia cột đầu cho $2^{641}$ là vì nó giúp cho giá trị đầu của vector kết quả có giá trị lớn ($\approx 641$ bit), nếu nhân cột đầu cho $2^{641}$ thì giá trị đầu của vector kết quả luôn là $0$.

---