# Lexington Informatics Tournament CTF 2023 (LITCTF)
## Polypoint
- encode.py

from secrets import SystemRandom

gen = SystemRandom()

with open("flag.txt", "rb") as f:
    flag = f.read().strip()

assert len(flag) == 76
c = int.from_bytes(flag)

poly = [c]
for _ in range(10):
    poly.append(gen.randrange(pow(10, 11), pow(10, 12)))

for _ in range(10):
    x = gen.randrange(pow(10, 11), pow(10, 12))
    v = 1
    y = 0
    for i in range(11):
        y += poly[i] * v
        v *= x
    print(f"({x},{y})")
    

- [encode.txt](https://github.com/tvdat20004/CTF_write-up/blob/main/LIT2023/polypoint/encoded.txt)
- Bài này đại khái sẽ cho ta 1 đa thức p bậc 11 gồm các hệ số a0,...,a10 (a0 là flag, a1,...,a10 là số nguyên từ $10^{11}$ đến $10^{12}$), sau đó cho 10 tuple có dạng`(x,p(x))`.
- Dễ dàng nhận ra mình phải đưa về giải hệ phương trình để a0,... a10, tuy nhiên hệ chúng ta có chỉ có 10 phương trình mà 11 ẩn. Về cơ bản thì hệ này sẽ có vô số nghiệm, tuy nhiên ta sẽ dựa vào các điều kiện sau để tìm flag:
- Tất cả các nghiệm là số nguyên
- $10^{11}$ < a1,...,a10 < $10^{12}$
- Ta sẽ dùng 1 chút kiến thức đại số tuyến tính để giải quyết hệ này. Đầu tiên ta lập ma trận:$\begin{bmatrix}
x_{1}^{10} &... &x_1 &1 &y_1 \\
x_2^{10} &... &x_2 &1 &y_2\\
...& ...& ...& ...& ...\\
x_{10}^{10}&...&x_{10} &1 &y_{10}
\end{bmatrix}$

mat = []
with open("./encoded.txt", "r") as f:
    for _ in range(10):
        x, y = eval(f.readline().strip())        
        row  = [x**i for i in reversed(range(11))] + [y]
        mat.append(row)

Sau đó chuyển nó về ma trận bậc thang thu gọn (reduced echelon form), lấy hàng cuối để thu được phương trình chỉ gồm 2 ẩn.

mat  = matrix(ZZ, mat)
last = mat.rref()[-1]
p, q = last[-2:]
# a1 + p*a0 == q

Do p,q là các phân số nên mình sẽ phải quy đồng để đưa về số nguyên.

m, n = p.as_integer_ratio()
u, v = q.as_integer_ratio()
A, B, C = n*v, m*v, n*u
# A*a1 + B*a0 == C

Nhìn vào phương trình $A.a_1 + B.a_0 = C$(1) thì mình nghĩ đến [extended Euclid](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm).

_, x0, y0 = xgcd(A, B)

x0 *= C//_ 
y0 *= C//_ 
tx = B//gcd(A, B)
ty = A//gcd(A, B)

Khi đó, từ (1) => $A(x_0-a_1) = B(a_0-y_0)$ => $\frac{x_0-a_1}{tx} = \frac{a_0-y_0}{ty}$.
Do $(tx,ty) = 1$ nên 2 phân số trên phải là số nguyên, suy ra $x_0 - a_1 = k*tx$ và $k > \frac{x_0-a_{1max}}{tx}$, tới đây mình bruteforce k thôi :v
- solve.py

from Crypto.Util.number import *
from sage.all import *
mat = []

with open("./encoded.txt", "r") as f:
    for _ in range(10):
        x, y = eval(f.readline().strip())        
        row  = [x**i for i in reversed(range(11))] + [y]
        mat.append(row)

mat  = matrix(ZZ, mat)
last = mat.rref()[-1]
p, q = last[-2:]

# a1 + p*a0 == q

m, n = p.as_integer_ratio()
u, v = q.as_integer_ratio()
A, B, C = n*v, m*v, n*u

# A*a1 + B*a0 == C

_, x0, y0 = xgcd(A, B)

x0 *= C//_ 
y0 *= C//_ 

tx = B//gcd(A, B)
ty = A//gcd(A, B)
# print(tx,ty)
k = (x0 - 10**12)//tx

while True:
    a1 = x0 - k*tx 
    if a1 > 10**11 and a1 < 10**12:
        a0 = (C - A*a1)//B 
        print(long_to_bytes(int(a0)))
        break
    k += 1

> Flag: LITCTF{h4h4_1ts_n0t_th4t_345y__almOst_ThEre_hAVe_somE_gibbeRish__d6570c3b3f}

## are YOU smarter than Joseph-Louis Lagrange????
- File pdf:
- Trước tiên là tìm giá trị 4 loại trái cây trước.

df = [1825147270203874538950085, 1755355241290944436019489,  150220311113190713333212, 1826562141290875830948785]
coef = matrix([
    [1, 1, 0, 0],
    [0, 1, 1, 0],
    [1, 0, 1, 0],
    [0, 1, 0, 1]
])
ans = coef \ vector(df)

- Sau đó tìm hàm f (theo mình đoán nó phải là đa thức bậc 3 để việc giải hpt trở nên khả thi), mình sẽ dùng phương thức [lagrange_polynomial](https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/polynomial_ring.html#sage.rings.polynomial.polynomial_ring.PolynomialRing_field.lagrange_polynomial) để giải quyết việc này (hoặc bạn có thể lập hệ phương trình rồi giải như trên nếu muốn =)))
- solve.sage

df = [1825147270203874538950085, 1755355241290944436019489,  150220311113190713333212, 1826562141290875830948785]
coef = matrix([
    [1, 1, 0, 0],
    [0, 1, 1, 0],
    [1, 0, 1, 0],
    [0, 1, 0, 1]
])
ans = coef \ vector(df)
X = [i+1 for i in range(4)]
P.<x> = PolynomialRing(QQ)
fx = P.lagrange_polynomial([
    (x, y) for x,y in zip(X,ans)
])
flag = "".join([str(i) for i in ans]) + str(fx(5))
print(flag)

## E(Z/C)LCG
- chall.sage

from random import SystemRandom
random = SystemRandom()

def fun_prime(n): # not as smooth as my brain but should be enough
    while True:
        ps = 16
        p = 1
        for i in range(n//ps):
            p *= random_prime(2^ps)
        p += 1
        if is_prime(p):
            return p
def gen(b):
    p = fun_prime(b)
    E = EllipticCurve(GF(p), [random.randint(1, 2^b), random.randint(1,2^b)])
    return E, p, E.order()

C, p, order = gen(80)
# woah thats an lcg
class lcg:
    def __init__(self, C: EllipticCurve):
        self.order = order
        self.a = random.randint(1, self.order)
        self.x = C.gens()[0]
        self.b = self.x * random.randint(1, self.order)
    def next(self):
        self.x = (self.a * self.x + self.b)
        return self.x

prng = lcg(C)
x0 = prng.next()
x1 = prng.next()
x0, y0 = x0.xy()
x1, y1 = x1.xy()
print(f"{x0 = }")
print(f"{y0 = }")
print(f"{x1 = }")
print(f"{y1 = }")
print(f"{p = }")



from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes as l2b
from Crypto.Util.Padding import pad
from os import urandom
v = int(prng.next().xy()[0])
k = pad(l2b(v**2), 16)
iv = urandom(16)
cipher = AES.new(k, AES.MODE_CBC, iv=iv)
print(f"iv = '{iv.hex()}'")
f = open("flag.txt",'rb').read().strip()
enc = cipher.encrypt(pad(f,16))
print(f"enc = '{enc.hex()}'")

- [out.txt](https://github.com/tvdat20004/CTF_write-up/blob/main/LIT2023/ECLCG/out.txt)
- Bài này cho một LCG nhưng có liên quan đến ECC. Đầu tiên chương trình gen 1 Elliptic Curve trên GF(p) với a,b chưa biết. Tuy nhiên mình có thể tính được nó dựa vào 2 điểm X0,X1 và phương trình $y^2 = x^3 + ax+b$.

F = GF(p)
coeff = Matrix(F,[[x0,1 ],[x1,1 ]])
df = vector(F, [y0**2  - x0**3 , y1**2  - x1**3 ])
[a,b] = coeff \ df
print(a,b)

- LCG này có phương trình `X[n] = a*X[n-1] + b*G` với `G = E.gens()[0]` và `X[-1] = G`, do đó dễ dàng có được `X0 = (a+b)*G = kp*G` và `X1 = a*X0 + b*G = (a*(a+b) + b)*G = kq*G`
- Mình có thể tìm được kp và kq bằng hàm `discrete_log()` (tuy nhiên máy mình chạy tới hơn 5 phút mới có kết quả =)) ). Tiếp theo ta chỉ cần lập hệ và tìm a,b, sau đó lắp vào LCG và chạy để tìm key.
- solve.sage

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes as l2b
from Crypto.Util.Padding import pad

x0 = 2029673067800379268 
y0 = 1814239535542268363 
x1 = 602316613633809952 
y1 = 1566131331572181793 
p = 2525114415681006599 
iv = bytes.fromhex('6959dbf6bf22344d452c3831a3b68897')
enc = bytes.fromhex('a490e177c3838c8f24d36be5ee10e0c9e244ac2e54cd306eddfb0d585d5f27535835fab1cd83d26a669e6c08096b58cc4cc4cb082f4534ce80fab16e21f119adc45a5f59d179ca3683b77a942e4cf4081e01d921a51ec3a3a48c13f850c04b80c997367739bbde0a5415ff921d77a6ef')

F = GF(p)
coeff = Matrix(F,[[x0,1 ],[x1,1 ]])
df = vector(F, [y0**2  - x0**3 , y1**2  - x1**3 ])
[a,b] = coeff \ df
print(a,b)
# assert int(y1**2 - (x1**3 + int(a)*x1 + int(b))) % int(p) == 0
E = EllipticCurve(F, [a,b])
X0 = E(x0,y0)
X1 = E(x1,y1)
G = E.gens()[0 ]
# kp = G.discrete_log(X0)
# kq = G.discrete_log(X1)
kp = 916472720818205535 # để tiết kiệm thời gian chạy nên mình tính trước kết quả luôn :v
kq = 1673271260266693096 
# kp = a + b
# kq = b + a(a+b) = b + a*kp
order = E.order()
coeff = matrix(Zmod(order),[[1 ,1 ], [kp,1 ]])
df = vector([kp,kq])
[a,b] = coeff \ df
v = int((G*int(b) + int(a)*X1).xy()[0 ])
k = pad(l2b(v**2 ), 16 )
cipher = AES.new(k, AES.MODE_CBC, iv=iv)

flag = cipher.decrypt(enc)
print(flag)

> Flag: LITCTF{Youre_telling_me_I_cant_just_throw_elliptic_curves_on_something_and_make_it_100x_secure?_:<}