Description
Last time we went easy on you. You'll never get the flag this time! Download: chall.py and output.txt .
Setup
Download chall.py and output.txt.
Read chall.py carefully to understand how the Shamir Secret Sharing scheme is modified.
cat chall.py
cat output.txt
Solution
- Step 1Understand the schemeThis is a variant of Shamir Secret Sharing where the polynomial coefficients have an algebraic relationship. The secret is the polynomial's constant term, and the shares are evaluations at specific points. LLL lattice reduction can exploit the structure to recover the secret.
- Step 2Set up the latticeExpress the shares as a system of polynomial constraints. The coefficients satisfy a small norm condition. Use LLL basis reduction to find the short vector that corresponds to the secret.# In SageMath: sage << 'EOF' from output import shares, modulus # load from output.txt # Build the lattice matrix from the share evaluations # Each share: y_i = f(x_i) mod p where f has small coefficients # Set up a lattice and apply LLL # Example structure (adjust to match chall.py): n = len(shares) deg = n - 1 M = Matrix(ZZ, n+1, n+1) for i, (x, y) in enumerate(shares): for j in range(deg+1): M[i, j] = (x^j * modulus) M[i, n] = y M[n, n] = 1 # small-entry anchor L = M.LLL() secret = int(L[0][-1]) % modulus print("Secret:", secret) print(bytes.fromhex(hex(secret)[2:])) EOF
Flag
picoCTF{mss_lll_r3v3ng3_...}
The modified Shamir scheme's polynomial coefficients satisfy a short-norm condition exploitable with LLL lattice reduction.