Spreading Secrets - LA CTF 2025 Crypto Writeup

Category: Crypto Difficulty: Medium Points: 205 Solves: 76 Flag: lactf{d0nt_d3r1v3_th3_wh0l3_p0lyn0m14l_fr0m_th3_s3cr3t_t00!!!} Solved by: Smothy @ 0xN1umb

"I heard you like sharing secrets, so I put the secret inside the secret sharer that shares the secret."

Challenge Description

I heard you like sharing secrets, so I shared my secret with the polynomial that shares the secret.

Downloads: chall.py

We're given a single Python file implementing Shamir's Secret Sharing... but with a twist that makes a cryptographer weep. The polynomial coefficients that are supposed to be random are instead generated by an RNG seeded with the secret itself. One share is enough to recover everything.

TL;DR

Shamir's Secret Sharing uses a random polynomial to split a secret into shares. This challenge seeds the "random" coefficient generator with the secret, making all coefficients deterministic functions of the secret. We build a degree-19,683 univariate polynomial over GF(p) and solve for roots using PARI/GP. Polynomial algebra go brrr.

Initial Recon

One file. One share. One prayer. Let's see what we're working with.

The challenge gives us:

• chall.py — Shamir's Secret Sharing implementation with a custom RNG
• p — a 512-bit prime modulus
• Share_1 = (1, y) — a single share point

In standard Shamir's, you need threshold shares to recover the secret. Here threshold = 10, but we only have 1 share. Normally that's game over. But this isn't standard Shamir's...

Step 1: Spotting the Vulnerability

The RNG class implements a cubic polynomial state update:

class RNG:
    def next(self):
        self.state = (
            a * self.state**3
            + b * self.state**2
            + c * self.state
            + d
        ) % self.modulus
        return self.state

And the critical flaw — the RNG is seeded with the secret itself:

def create_shares(secret, threshold, num_shares, p):
    rng = RNG(secret, p)  # <-- SECRET IS THE SEED
    coefficients = [secret]
    for i in range(threshold - 1):
        coefficients.append(rng.next())  # <-- ALL DERIVED FROM SECRET

For the homies who haven't touched Shamir's Secret Sharing: the whole security depends on the polynomial coefficients being independently random. If they're all functions of the secret, the whole scheme collapses. One share tells us everything.

Step 2: The Math — Degree Explosion

Let R(x) = a·x³ + b·x² + c·x + d be the RNG step function. The coefficients of the sharing polynomial are:

Since our share is at x = 1, the polynomial evaluates to the sum of all coefficients:

This gives us a single equation in one unknown (s):

g(s) = s + R(s) + R²(s) + ... + R⁹(s) - T ≡ 0 (mod p)

The degree? Each RNG step cubes the previous degree: 3⁹ = 19,683. That's a chunky polynomial, but it's solvable over a finite field.

Step 3: Building the Polynomial

We use PARI/GP to symbolically construct the degree-19,683 polynomial. Starting with state = x (the unknown secret), we iteratively apply the RNG:

state = Mod(1,p) * x;
total = Mod(1,p) * x;

for(i = 1, 9,
  state = a * state^3 + b * state^2 + c * state + d;
  total = total + state;
);

g = lift(total - T);

Each step cubes the polynomial's degree. The last step cubes a degree-6,561 polynomial into degree-19,683 — PARI handles this with fast polynomial multiplication.

Step 4: Root Finding with PARI/GP

With the polynomial built, we use polrootsmod to find roots over GF(p):

roots = polrootsmod(g, p);

This uses Cantor-Zassenhaus factorization under the hood — computing gcd(g(x), x^p - x) via modular polynomial exponentiation. With a 512-bit prime and degree ~20K, it takes about a minute.

The solver found exactly 2 roots out of a possible 19,683. The polynomial is very sparse in solutions.

Step 5: Extracting the Flag

Converting both roots to bytes:

from Crypto.Util.number import long_to_bytes

root1 = 866141263118392010733924793414412614315005185909326749918386069...
root2 = 307429842859570912195587502326480040609281170885067924581517303...

print(long_to_bytes(root1))
# b'lactf{d0nt_d3r1v3_th3_wh0l3_p0lyn0m14l_fr0m_th3_s3cr3t_t00!!!}'

print(long_to_bytes(root2))
# b':\xb2\xdb\x92...'  (non-ASCII garbage)

Root 1 decodes to valid ASCII with the lactf{ prefix. GG.

The Flag

Translation: "Don't derive the whole polynomial from the secret too!!!"

The flag itself is the lesson. Respect.

The Attack Flow

The Solve Script

\\ solve.gp — Spreading Secrets solver
\\ Smothy @ 0xN1umb — LA CTF 2025
allocatemem(4000000000);

p = 12670098302188507742440574100120556372985016944156009521523684257469947870807586552014769435979834701674318132454810503226645543995288281801918123674138911;

av = Mod(4378187236568178488156374902954033554168817612809876836185687985356955098509507459200406211027348332345207938363733672019865513005277165462577884966531159, p);
bv = Mod(5998166089683146776473147900393246465728273146407202321254637450343601143170006002385750343013383427197663710513197549189847700541599566914287390375415919, p);
cv = Mod(4686793799228153029935979752698557491405526130735717565192889910432631294797555886472384740255952748527852713105925980690986384345817550367242929172758571, p);
dv = Mod(4434206240071905077800829033789797199713643458206586525895301388157719638163994101476076768832337473337639479654350629169805328840025579672685071683035027, p);

T = Mod(6435837956013280115905597517488571345655611296436677708042037032302040770233786701092776352064370211838708484430835996068916818951183247574887417224511655, p);

state = Mod(1,p) * x;
total = Mod(1,p) * x;

{for(i = 1, 9,
  state = av * state^3 + bv * state^2 + cv * state + dv;
  total = total + state;
);}

g = lift(total - T);
roots = polrootsmod(g, p);

{for(i = 1, #roots,
  print(lift(roots[i]));
);}

quit;

Then convert roots to bytes in Python:

from Crypto.Util.number import long_to_bytes

for root in [<root1>, <root2>]:
    b = long_to_bytes(root)
    if b.isascii():
        print(f"FLAG: {b.decode()}")

The Graveyard of Failed Attempts

Honestly? This one was pretty clean. The vulnerability was obvious from reading the source code — the real challenge was the computational math:

1. Tried SageMath first — not installed, package sagemath not in Kali repos. RIP.
2. Considered Python-only approach — degree 19,683 polynomial arithmetic with naive multiplication would take hours. Needed proper computer algebra.
3. PARI/GP to the rescue — apt install pari-gp, fast polynomial arithmetic over finite fields, polrootsmod just works. Clean solve.

The 30 seconds spent troubleshooting package managers

Key Takeaways

1. Shamir's Secret Sharing requires truly random coefficients. If the coefficients are derived from the secret, a single share can break the entire scheme.
2. Deterministic RNG from secret = no security. The "randomness" must be independent of the secret being shared. This is crypto 101 but easy to mess up.
3. Polynomial root-finding over finite fields is powerful. Even a degree-19,683 polynomial over a 512-bit prime field is solvable in under a minute with proper tools (PARI/GP, SageMath).
4. Composition of degree-d maps creates degree d^k polynomials. 9 iterations of a cubic map = degree 3⁹ = 19,683. The degree explodes exponentially, but modern CAS handles it.
5. PARI/GP is an underrated CTF tool. When SageMath isn't available, gp is lightweight, fast, and perfect for number theory.

Tools Used

• PARI/GP — Polynomial construction & root-finding over GF(p)
• Python + PyCryptodome — Integer-to-bytes conversion
• matplotlib — Screenshot generation (Catppuccin Mocha theme, obviously)
• Way too much caffeine

Writeup by Smothy from 0xN1umb team. One share, one equation, one polynomial of degree 19,683. Math always wins. GG.