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 = 15 coefficients generated by an LCG modulo another 256‑bit prime pp.
• 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.