這幾天準備模考有點累，剛好看到有好玩的CTF，主要還是打crypto，這次8題打出5題，覺得還行，找幾題有趣的題目寫writeup。

I’ve been a bit tired these days preparing for the GSAT, and I happened to come across an interesting CTF. I mainly focused on crypto challenges. There were 8 problems this time, and I solved 5 of them, which I think is pretty decent. I’m planning to write writeups for a few of the more interesting ones.

rot727h3

i rotated my flag 727 times! that’s super secure right

aeg{at_imuf_nussqd_zgynqd_paqezf_yqmz_yadq_eqogdq}

就凱撒加密 Caesar Cipher

Flag: osu{oh_wait_bigger_number_doesnt_mean_more_secure}

ssssh3

can you ss this secret sharing scheme?

nc ssss.challs.sekai.team 1337

#!/usr/local/bin/python3
from Crypto.Util.number import *
import random

p = 2**255 - 19
k = 15
SECRET = random.randrange(0, p)

def lcg(x, a, b, p):
    return (a * x + b) % p

a = random.randrange(0, p)
b = random.randrange(0, p)
poly = [SECRET]
while len(poly) != k: poly.append(lcg(poly[-1], a, b, p))

def evaluate_poly(f, x):
    return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p

print("welcome to ssss", flush=True)
for _ in range(k - 1):
    x = int(input())
    assert 0 < x < p, "no cheating!"
    print(evaluate_poly(poly, x), flush=True)

if int(input("secret? ")) == SECRET:
    FLAG = open("flag.txt").read()
    print(FLAG, flush=True)

解法：h4

假設質數 $p = 2^{255} - 19$

現有一個未知的 $14$ 次多項式

其係數滿足遞推關係：

我們可以查詢 $f$ 在任意 $14$ 個非零點的值，目標是求出 $c_0$。

首先，對 $f(x)$ 在 $14$ 個非零點進行查詢，可以得到包含 $c_0, c_1, \dots, c_{14}$ 的 $14$ 條線性方程式。
由於變數共有 $15$ 個，透過高斯消元可以將每個 $c_i$ 表示為 $c_0$ 的線性函數。

由遞推關係可得：

將前一步的線性表示代入，可得到一個關於 $c_0$ 的二次方程式。

最後，在 $mod$ $p$ 下對此二次方程求解，並透過二次剩餘檢查來確定正確的 $c_0$。

Solution:h4

Assume the prime $p = 2^{255} - 19$

We have an unknown degree-$14$ polynomial

whose coefficients satisfy the recurrence:

We are allowed to query the value of $f$ at any $14$ non-zero points, and the goal is to determine $c_0$.

First, by querying $f(x)$ at $14$ distinct non-zero points, we obtain $14$ linear equations involving $c_0, c_1, \dots, c_{14}$.
Since there are $15$ variables in total, we can use Gaussian elimination to express each $c_i$ as a linear function of $c_0$.

From the recurrence relation we have:

Substituting the linear expressions obtained above yields a quadratic equation in $c_0$.

Finally, we solve this quadratic equation modulo $p$ and determine the correct solution by checking quadratic residues.

Flag: osu{0n3_hundr3d_p3rc3nt_4ccur4cy!}