Challenge
We are given access to a remote server (nc ssss.challs.sekai.team 1337) which:
- Picks a large prime
p = 2^255 − 19. - Uses
k = 15coefficients generated by an LCG modulo another 256‑bit primepp. - Builds a polynomial
f(x) = Σ c_i * x^i (mod p). - Allows 14 evaluations of
f(x). - Finally asks for the secret (
c_0) — if correct, it reveals the flag.
Step 1 --- First Thoughts
At first glance, 14 evaluations of a degree‑14 polynomial are insufficient to recover all coefficients. However, the LCG structure introduces a linear dependency among coefficients, drastically reducing the entropy.
Key idea: ( c_{n+1} = a c_n + b ) modulo the separate 256‑bit prime pp. Only three unknowns remain: (S, a, b).
Step 2 --- Structural Observation
We rewrite the polynomial as:
[ f(x) = S H(x) + b Q(x) ]
with H and Q derived from the geometric series depending on a and x. Because we can compute H and Q analytically, three distinct queries suffice to solve for (S, a, b) over the finite field.
Step 3 --- Implementation
The solver queries the server for several x values, obtains f(x) results, and solves the symbolic relation for a, b, and S over F_p. After validating results, it submits the recovered S as the secret.
Refer to Solver.py for the full implementation.
Step 4 --- Result
Running locally reproduces the server logic correctly, and running remotely yields:
Recovered SECRET: 4567624288816757066280175774901590738503309764390513849026509987390355624781
secret? osu{0r_d1d_y0u_us3_fl45hl1ght_1nst34d?}
Flag
osu{0r_d1d_y0u_us3_fl45hl1ght_1nst34d?}
Notes
- Only three equations are required to determine the polynomial parameters.
- The linear recurrence eliminates the need for full interpolation.
- The logic is self-contained; see Solver.py for detailed computation steps.
- Works instantly for both local and remote modes.