# LaCTF 2024

## hOlyT

Server.py

from Crypto.Util.number import getPrime, bytes_to_long
import random
def legendre(a, p):
    return pow(a, (p - 1) // 2, p)

def tonelli(n, p):
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    if s == 1:
        return pow(n, (p + 1) // 4, p)
    for z in range(2, p):
        if p - 1 == legendre(z, p):
            break
    c = pow(z, q, p)
    r = pow(n, (q + 1) // 2, p)
    t = pow(n, q, p)
    m = s
    t2 = 0
    while (t - 1) % p != 0:
        t2 = (t * t) % p
        for i in range(1, m):
            if (t2 - 1) % p == 0:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        r = (r * b) % p
        c = (b * b) % p
        t = (t * c) % p
        m = i
    return r
def xgcd(a, b): 
    if a == 0 : 
        return 0,1
             
    x1,y1 = xgcd(b%a, a) 
    x = y1 - (b//a) * x1 
    y = x1 
    return x,y 
def crt(x1, x2, p, q):
    m1, n1 = xgcd(p, q)
    return ((x2 *p * m1 + x1*q*n1) % (p * q))

def advice(x, p, q):
    if legendre(x, p) != 1:
        exit()
    if legendre(x, q) != 1:
        exit()
    
    x1 = tonelli(x, p) * random.choice([1, -1])
    x2 = tonelli(x, q) * random.choice([1, -1])
    y = crt(x1, x2, p, q)
    return y
    
def main():
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q
    e = 65537
    m = bytes_to_long(b"lactf{day-la-flag-dayy}")
    ct = pow(m, e, N)
    print(f"ct = {ct}")
    print(f"N = {N}")
    print(f"e = {e}")
    while 1:
        x = int(input("What do you want to ask? > "))
        ad = advice(x, p, q)
        print(ad)

if __name__ == "__main__":
    main()

Bài này ta thấy rằng, sau khi gen các khóa, ta sẽ được nhập 1 giá trị $$x$$, và rồi ta sẽ thu được các giá trị

$$x1 = tonelli(x,p)*random(1,-1)$$
$$x2 = tonelli(x,q)*random(1,-1)$$

Thế ``tonelli`` là gì nhỉ. Ta có rằng, $$tonelli(a,p) = x$$ với $$x^2 = a \pmod {p}$$

Giờ tiếp tục với bài, ta sẽ nhập giá trị của $$x = 1$$, ta sẽ được như sau

Thì giá trị $$x1, x2 \in {(-1,1)}$$.

Sau đó, ta sẽ khai thác hàm crt của bài này.

def crt(x1, x2, p, q):
    m1, n1 = xgcd(p, q)
    return ((x2 *p * m1 + x1*q*n1) % (p * q))

Ta sẽ được 2 giá trị $$m1$$ và $$n1$$, mà thỏa mãn $$m1*p + n1*q = 1$$

Hàm sẽ trả về $$ad = x2*p*m1 + x1*q*n1 \pmod {n}$$. Mà $$x1, x2 \in {(-1,1)}$$. Giả sử $$x1 = -1$$, $$x2 = 1$$ (1 số âm 1 số dương sẽ có xác suất cao hơn), thì ta sẽ được:

$$ad = p*m1 - *q*n1 \pmod {n}$$
$$ad = p*m1 - *q*n1 \pmod {n}$$
$$ad = 1 - q*n1 \pmod {n}$$
$$ad + 1 = - q*n1 \pmod {n}$$

Khi đó
$$gcd(ad+1,n) == q$$

from pwn import*
from Crypto.Util.number import*
def gcda(a,b):
        remainder=a%b
        while remainder>0:
            a=b
            b=remainder
            remainder=a%b
        return b

io = process(["python3", "real_server.py"])
io.recvuntil(b'ct = ')
ct = int(io.recvuntil(b'\n',drop=True))
io.recvuntil(b'N = ')
N = int(io.recvuntil(b'\n',drop=True))
io.recvuntil(b'e = ')
e = int(io.recvuntil(b'\n',drop=True))

io.recvuntil(b'What do you want to ask? > ')
io.sendline(b'1')
ad = int(io.recvuntil(b'\n',drop=True))

q = (gcda(ad + 1,N))
p = N//q
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(ct,d,N)))

## shuffle

#!/usr/local/bin/python3

from secrets import randbits
import math
from base64 import b64encode
MESSAGE_LENGTH = 617

class LCG:

    def __init__(self,a,c,m,seed):
        self.a = a
        self.c = c
        self.m = m
        self.state = seed

    def next(self):
        self.state = (self.a * self.state + self.c) % self.m
        return self.state

def generate_random_quad():
    return randbits(64),randbits(64),randbits(64),randbits(64)

initial_iters = randbits(16)

def encrypt_msg(msg, params):
    global initial_iters
    a, c, m, seed = params
    L = LCG(a, c, m, seed)
    for i in range(initial_iters):
        L.next()
    l = len(msg)
    permutation = []
    chosen_nums = set()
    while len(permutation) < l:
        pos = L.next() % l
        if pos not in chosen_nums:
            permutation.append(pos)
            chosen_nums.add(pos)
    output = ''.join([msg[i] for i in permutation])
    return output

# period is necessary
secret = b64encode(open('secret_message.txt','rb').read().strip()).decode() + '.'
length = len(secret)
assert(length == MESSAGE_LENGTH)

a, c, m, seed = params = generate_random_quad()
enc_secret = encrypt_msg(secret,params)

while True:
    choice = input("What do you want to do?\n1: Shuffle a message.\n2: Get the encrypted secret.\n3: Quit.\n> ")
    if choice == "1":
        message = input("Ok. What do you have to say?\n")
        if (len(message) >= length):
            print("I ain't reading allat.\n")
        elif (math.gcd(len(message),m) != 1):
            print("Are you trying to hack me?\n")
        else:
            print(f"Here you go: {encrypt_msg(message,params)}\n")
    elif choice == "2":
        print(f"Here you go: {enc_secret}\n")
    elif choice == "3":
        print("bye bye")
        exit(0)
    else:
        print("Bad choice.\n")

Trước hết, ta cần phải hiểu quy trình của bài này. Ta thấy sẽ có 1 hàm `LCG()` để sinh số ngẫu nhiên theo thuật toán dựa trên các biến ban đầu. Các biến số này đều có độ dài là 64 bits, và đầu ra của nó cũng sẽ là 64 bits.

class LCG:

    def __init__(self,a,c,m,seed):
        self.a = a
        self.c = c
        self.m = m
        self.state = seed

    def next(self):
        self.state = (self.a * self.state + self.c) % self.m
        return self.state

Sau đó sẽ lấy 1 giá trị ``initial_iters`` có độ dài 16 bits, sau đó sẽ thực hiện LCG ``initial_iters``lần.

Tùy theo độ dài của message nhập vào, ta sẽ sinh ra một bộ số theo LCG dựa trên độ dài đó. Ta có thể thử đoạn code sau đây để hiểu hơn.

class LCG:

    def __init__(self,a,c,m,seed):
        self.a = a
        self.c = c
        self.m = m
        self.state = seed

    def next(self):
        self.state = (self.a * self.state + self.c) % self.m
        return self.state

a = 18210600138061944481 
c = 9986678927328624706 
m = 4346234229968742460 
seed = 2841115211505391955
initial_iters = 41491
L = LCG(a, c, m, seed)
for i in range(initial_iters):
    (L.next())
l = 7
permutation = []
chosen_nums = set()
while len(permutation) < l:
        pos = L.next() % l
        if pos not in chosen_nums:
            permutation.append(pos)
            chosen_nums.add(pos)
print(permutation)
print(chosen_nums)

# [2, 3, 6, 1, 4, 5, 0]
# {0, 1, 2, 3, 4, 5, 6}

Hiện tại, mình đều chưa biết được các giá trị ban đầu của LCG, thế nhưng, chỉ cần có 6 giá trị đầu ra từ LCG, ta có thể tìm lại được $$a$$, $$c$$, $$m$$.

Bạn nên đọc đường [**LINK**](https://crypto.stackexchange.com/questions/87220/cryptographically-secure-linear-congruential-generator-is-it-possible) này để có thể hiểu hơn

Ta có:

$$X_{n+1} = a \cdot X_n + c \pmod{m}$$

Với giá trị $$X_0 = seed$$

**Tìm lại giá trị m**

Có 6 giá trị từ $$X_1, X_2, \cdots, X_6$$ thỏa mãn như sau

$$
\begin{align*}
X_1 &= aX_0 + c \\
X_2 &= aX_1 + c \\
&\vdots \\
X_6 &= aX_5 + c \\
\end{align*}
$$

Ta biến đổi được

$$
\begin{align*}
T_0 &\rightarrow X_2 - X_1 \equiv a.(X_1 - X_0) \pmod{m} \\
T_1 &\rightarrow X_3 - X_2 \equiv a.(X_2 - X_1) \pmod{m} \\
T_2 &\rightarrow X_4 - X_3 \equiv a.(X_3 - X_2) \pmod{m} \\
T_3 &\rightarrow X_5 - X_4 \equiv a.(X_4 - X_3) \pmod{m} \\
T_4 &\rightarrow X_6 - X_5 \equiv a.(X_5 - X_4) \pmod{m} \\
\end{align*}
$$
Ta lấy từng cặp một, ta được

$$
\begin{aligned}
\frac{T_1}{T_2} &\equiv \frac{X_3 - X_2}{X_4 - X3} \equiv \frac{X_2 - X_1}{X_3 - X_2} &\mod m \\
\rightarrow \frac{T_1}{T_2} &\equiv \frac{X_2 - X_1}{X_3 - X_2} &\mod m \\
\rightarrow \frac{T_1}{T_2} &\equiv \frac{T_0}{T_1} &\mod m \\
\rightarrow T_1 ^ 2 &\equiv T_0 \cdot T_2 &\mod m \\
\rightarrow T1^2 - T_0 \cdot T_2 &= k_1 \cdot m
\end{aligned}
$$

Tương tự như thế

$$
\begin{aligned}
T2^2 - T_1 \cdot T_3 &= k_2 \cdot m \\
T3^2 - T_2 \cdot T_4 &= k_3 \cdot m
\end{aligned}
$$

Bây giờ ta chỉ cần lấy ước chung là sẽ thu được m
$$GCD(k_1 \cdot m, k_2 \cdot m, k_3 \cdot m) = m $$

Ta đọc hàm ``encrypt_msg`` như sau

def encrypt_msg(msg, params):
    global initial_iters
    a, c, m, seed = params
    L = LCG(a, c, m, seed)
    for i in range(initial_iters):
        L.next()
    l = len(msg)
    permutation = []    
    chosen_nums = set()
    while len(permutation) < l:
        pos = L.next() % l
        if pos not in chosen_nums:
            permutation.append(pos)
            chosen_nums.add(pos)
    output = ''.join([msg[i] for i in permutation])
    return output

Thì mỗi lần encrypt một msg, ta sẽ bắt đầu lại cơ chế LGC, tức là, khi gửi **abc** thì sẽ được 3 giá trị là $$X_{n+1}$$, $$X_{n+2}$$, $$X_{n+3}$$ $$\pmod 3$$ và khi gửi **abcd** thì sẽ được 3 giá trị trên và thêm giá trị $$X_{n+4}$$ nhưng mà chỉ $$\pmod{4}$$ thui (với n là giá trị initial_iters)


Thế thì theo bảng này, ta sẽ có được như sau:

$$
\begin{aligned}
X_{n} &\equiv 5 &\mod 7 \\
X_{n + 1} &\equiv 3 &\mod 7 \\
X_{n + 2} &\equiv 6 &\mod 7 \\
\vdots \\
X_{n + 6} &\equiv 1 &\mod 7 \\
\end{aligned}
$$

Bây giờ, ta sẽ gửi các message có độ dài là các số nguyên tố, ta lấy luôn printable của string, ta có $$msg = printable[0:length]$$ với length là số nguyên tố. Gửi đến bao giờ có một phần dư đủ lớn, số 64 bits thì chỉ cần số 65 bits là được. Sau đó sẽ dùng CRT để recover lại được giá trị ban đầu.

$$
\underbrace{X_n \mod (7 \cdot 11 \cdot 13 \cdots \cdot 67)}_{\text{CRT}}
\begin{cases}
\begin{aligned}
X_{n} &\equiv 5 &\mod 7 \\
X_{n} &\equiv 8 &\mod 11 \\
X_{n} &\equiv 2 &\mod 13 \\
\vdots \\
X_{n} &\equiv 43 &\mod 67
\end{aligned}
\end{cases}
$$

Cứ làm như thế với $$X_{n+1}, \cdots, X_{n+5}$$, ta sẽ có được 6 số, từ đó có thể crack được LCG và tìm lại được flag.

Thế nhưng, đôi lúc sẽ bị tìm sai giá trị của $$m$$ và sẽ bị crack, hoặc không thể tiếp tục chạy do tôi số đó lớn hơn 64 bits nhưng mà không chia hết cho 2 hoặc 3 như thuật toán của tôi.

from sage.all import *
from functools import reduce
import math
from Crypto.Util.number import*
from pwn import*
from string import printable

class LCG:

    def __init__(self,a,c,m,seed):
        self.a = a
        self.c = c
        self.m = m
        self.state = seed

    def next(self):
        s = self.state
        self.state = (self.a * self.state + self.c) % self.m
        return s

def decrypt_msg(msg, params):
    a, c, m, seed = params
    L = LCG(a, c, m, seed)
    l = len(msg)
    permutation = []
    chosen_nums = set()
    while len(permutation) < l:
        thing = int(L.next())
        pos = thing % l
        if pos not in chosen_nums:
            permutation.append(pos)
            chosen_nums.add(pos)
    out = [0]*l
    for i,p in enumerate(permutation):
        out[p] = msg[i]
    output = base64.b64decode(''.join(out))
    return output

def get_prime():
    factors = []
    # Muốn lấy số to lắm nhưng mà mình sẽ gửi printable[0:prime] nên không thể lớn hơn 89 được
    for i in range(89,3,-1):
        if isPrime(i):
            factors.append(i)
    return factors   

def determine_states(msg,transposed):
    states = []
    for i in range(6):
        states.append(msg.index(transposed[i]))
    return states

while True:
    io = process(["python3", "shuffler.py"])
    io.recvuntil(b"> ")
    io.sendline(b"2")
    io.recvuntil(b'Here you go: ')
    data = io.recvuntil(b'\n', drop=True).decode()
    factors = get_prime()
    accept_prime = []
    modulos = 1
    i = 0
    output = []
    while modulos < 2**64:
        io.recvuntil(b'> ')
        io.sendline(b'1')
        msg = printable[0:factors[i]]
        io.recvuntil(b"\n")
        io.sendline(msg.encode())
        out = io.recvuntil(b'\n',drop=True).decode()
        if out == "Are you trying to hack me?":
            i+=1
            continue
        if "Here you go" in out:
            shuffled = out.split(' ')
            states = determine_states(msg,shuffled[-1])
            output.append(states)
            modulos*=factors[i]
            accept_prime.append(factors[i])
            i+=1
    io.close()
    X_list = []
    print(output, accept_prime)
    for i in range(6):
        X_list.append(crt([j[i] for j in output],accept_prime))
    t_list = []
    for i in range(5):
        t_list.append(X_list[i+1] - X_list[i])
    tt_list = []
    for i in range(3):
        tt_list.append(t_list[i+2]*t_list[i] - t_list[i+1]*t_list[i+1])
    m = math.gcd(*tt_list)
    if (m < 2**32):
        print("new process")
        continue
    else:
        while (m > (2 ** 64)):
            if m % 2 == 0:
                m //=2
            elif m % 3 == 0:
                m //=3
    a = ((X_list[2] - X_list[3]) * pow(X_list[1] - X_list[2],-1,m)) % m
    c = (X_list[1] - a*X_list[0]) % m
    msg = decrypt_msg(data,(a,c,m,X_list[0]))
    print(msg)
    exit(0)

I just invented the best shuffling algorithm!
Nobody can read this!
Here, let me hide a flag here: lactf{th3_h0us3_c0uld_n3v3r_l0se_r1ght}
I better not see anyone try to lay their three fingers sideways (mod m) and declare "with this breath, I determine a to be congruent to (X_2 - X_3)/(X_2 - X_1) and c to be trivial"
I mean, it's surely impossible to decipher this message right
I'm going to sell this algorithm to every casino ever and get rich mwahaha

**Flag: lactf{th3_h0us3_c0uld_n3v3r_l0se_r1ght}**

## prove it!

#!/usr/local/bin/python
import random

flag = "lactf{2kp_1s_ov3rr4t3d}"
p = 171687271187362402858253153317226779412519708415758861260173615154794651529095285554559087769129718750696204276854381696836947720354758929262422945910586370154930700427498878225153794722572909742395687687136063410003254320613429926120729809300639276228416026933793038009939497928563523775713932771366072739767


if __name__ == "__main__":
    
    s = random.getrandbits(128)
    alpha = random.getrandbits(40)
    g = redacted
    ss = [pow(g, s**i, p) for i in range(1,8)]
    alphas = [pow(g, alpha * s**i, p) for i in range(1,8)]
    print(f"Use these values to evaluate your polynomials on s")
    print(f"Powers of s: {ss}")
    print(f"Powers of alpha*s: {alphas}")
    tries = 0
    while True:
        if tries >= 2:
            print("Fool me once shame on you, fool me twice shame on me")
            break
        print("Can you prove to me you know the polynomial f that im thinking of?")
        target = []
        for i in range(8):
            target.append(random.randrange(p))
        print(f"Coefficients of target polynomial: {target}")
        ts = sum([(pow(s,7 - i, p) * target[i]) % p for i in range(len(target))]) % p
        f = int(input("give me your evaluation of f(s) > ")) % p
        h = int(input("give me your evaluation of h(s) > ")) % p
        fa = int(input("give me your evaluation of f(alpha * s) > ")) % p
        if f <= 1 or h <= 1 or fa <=1 or f == p-1 or h == p-1 or fa == p-1:
            print("nope")
            exit()
            
        if pow(f, alpha, p) != fa or f != pow(h, ts, p):
            print(f"failed! The target was {ts}")
            tries += 1
            continue

        print(f"you made it! here you got {flag}")
        break

Muốn chạy local thì $$g = 2$$ nha
Bài này như sau:
- Tạo ra một số $$s$$ 128 bits, và $$alpha$$ 40 bits
- Ta sẽ có được 2 dãy đó là $$ss = g^{s^1}, g^{s^2}, \cdots, g^{s^8} \mod p$$ và $$alphas = g^{alpha \cdot \ s^1}, g^{alpha \cdot \ s^2}, \cdots, g^{alpha \cdot \ s^8} \mod p$$.
- Ta sẽ có 1 list $$targets$$ gồm 8 số ngẫu nhiên nhỏ hơn giá trị $$p$$. List này cũng được công khai lun.
- Có 1 giá trị $$ts = s^{7-0}.target[0] + s^{7-1}.target[1] + \cdots + s^{7-7}.target[7] \pmod{p}$$

- Ta sẽ phải đoán các giá trị $$f$$, $$fa$$, $$h$$ sao cho $$fa = f^{alpha} \mod p$$ và $$f = h^{ts} \mod p$$

- Bạn có thể đoán sai lượt đầu, và sẽ được leak giá trị $$ts$$, thế nhưng bạn không thể đoán sai lần 2.

Bây giờ, ta có được $$ss_0 = g^{s^{1}} \mod p$$, $$alphas_0 = g^{alpha.s^{1}} \mod p$$

Từ đó, ta có được

$$alphas_0 = ss_0^{alpha} \mod p$$

Như thuật toán Pohlig Hellman, ta có thể sử dụng các thừa số nguyên tố của $$(p-1)$$ và kết hợp CRT để có thể tìm được log. Trường hợp này cũng thế, thật may vì $$p$$ có độ dài 128 bits nhưng $$(p-1)$$ lại có các thừa số đủ nhỏ mà vẫn đủ bit để dùng discrete_log

$$p - 1 =  2 × \underbrace{7 × 13 × 19 × 53 × 1777 × 13873}_{\text{42 bits}} × 375066 324492 304430 531233 × 101 \cdots 063$$

Thế nên, ta có thể tìm được $$alpha$$ đơn giản bằng discrete_log của Sage.

Sau khi tìm được $$alpha$$ rồi, tìm lại $$s$$ thì đơn giản hơn.

Ta sẽ làm sai 1 lần, rồi lấy lại giá trị $$ts$$, sau đó tìm lại s và sẽ pass được vòng thứ 2.

Ta có

$$ts = s^{7-0}.target[0] + s^{7-1}.target[1] + \cdots + s^{7-7}.target[7] \pmod{p}$$
$$ts - (s^{7-0}.target[0] + s^{7-1}.target[1] + \cdots + s^{7-7}.target[7]) = k*p$$

Giờ sẽ đặt phương trình trong trường số nguyên tố, sau đó sẽ sử dụng hàm ``roots()`` sẽ tìm lại được giá trị $$s$$.

P.<x> = PolynomialRing(Zmod(p))
f = -sum(x^(7-i)*int_targets[i] for i in range(8))
f = f + ts
f = f.monic()
results = f.roots()

from pwn import *

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

p = 171687271187362402858253153317226779412519708415758861260173615154794651529095285554559087769129718750696204276854381696836947720354758929262422945910586370154930700427498878225153794722572909742395687687136063410003254320613429926120729809300639276228416026933793038009939497928563523775713932771366072739767
F = GF(p)
io.recvuntil(b"Powers of s: [")
ss = io.recvuntil(b']',drop=True).decode()
ss = (ss.split(', '))
int_ss = []
for s in ss:
    int_ss.append(int(s))
io.recvuntil(b'Powers of alpha*s: [')
alphas = io.recvuntil(b']',drop=True).decode()
alphas = (alphas.split(', '))
int_alphas = []
for alpha in alphas:
    int_alphas.append(int(alpha))
    
io.recvuntil(b'Coefficients of target polynomial: [')
targets = io.recvuntil(b']',drop=True).decode()
targets = (targets.split(', '))
int_targets = []
for target in targets:
    int_targets.append(int(target))

alpha = discrete_log_lambda(F(int_alphas[0]), F(int_ss[0]), bounds=[0,2^40])

io.sendlineafter(b"give me your evaluation of f(s) > ", b'2')
io.sendlineafter(b"give me your evaluation of h(s) > ", b'2')
io.sendlineafter(b"give me your evaluation of f(alpha * s) > ", b'2')
io.recvuntil(b'failed! The target was ')
ts = int(io.recvuntil(b'\n',drop=True).decode())
P.<x> = PolynomialRing(Zmod(p))
f = -sum(x^(7-i)*int_targets[i] for i in range(8))
f = f + ts
f = f.monic()
results = f.roots()
for result in results:
    s = result[0]
    if s < 2**128:
        break
io.recvuntil(b'Coefficients of target polynomial: [')
targets = io.recvuntil(b']',drop=True).decode()
targets = (targets.split(', '))
int_targets = []
for target in targets:
    int_targets.append(int(target))
ts = sum([(pow(s,7 - i, p) * int_targets[i]) % p for i in range(len(int_targets))]) % p
f = pow(2,ts,p)
io.sendlineafter(b"give me your evaluation of f(s) > ", str(f).encode())
io.sendlineafter(b"give me your evaluation of h(s) > ", b'2')
io.sendlineafter(b"give me your evaluation of f(alpha * s) > ", str(pow(f,alpha,p)).encode())
io.interactive()

**Flag: lactf{2kp_1s_ov3rr4t3d}**