Challenge Description#

it isnt a CTF without RSA

Analysis#

The provided script looked like a normal RSA setup at first, but the key clue was that it also published ten polynomial points with an added random noise term and a matching RSA-encrypted version of that noise. Pulling the crucial lines out of galatical.py made the weakness obvious: the noise was only 16 bits, and the script output both y_noisy = y + r (mod n) and r_enc = r^e mod n.

python extract_core_lines.py

13: NOISE_BITS = 16
88:             y = poly_eval_mod(coeffs, x, n)
89:             r = secrets.randbelow(1 << NOISE_BITS)
90:             y_noisy = (y + r) % n
91:             r_enc = pow(r, E, n)
94:         f_m = poly_eval_mod(coeffs, m, n)
98:         c1 = pow(m, E, n)
99:         c2 = pow(f_m, E, n)

Then I checked the published parameters in output.txt to confirm the shape of the instance (e = 17, degree 9 polynomial, and 16-bit noise). Because r < 2^16, r^17 is far smaller than a 2048-bit modulus, so r_enc = r^17 mod n is just the exact integer power with no wraparound. That means each r can be recovered by exact integer 17th root, which instantly removes the noise from every point.

python -c "from pathlib import Path; t=Path('output.txt').read_text(); print('\n'.join([line for line in t.splitlines() if line.startswith(('n =','e =','deg =','noise_bits =','c1 =','c2 ='))]))"

n = 21795931982959810520942863253123932350006550281673221741324389746441489588991691784228362252631862821241876624167634299253224012371185010989980972276294863120930187293561186408413794501225854649333475546641202394219469315718499032427794894336784303091789112740065030697184580712820317698061315065029994965000331675762255319964208064800895206524399505312735194878932683089429730306737687182410525781623616904466313063331314814981761501664490445059865564935765420577375894805622643041732346768897425640062528994058910747278648497266970687062720587080127756482814143522566541416793580032910516069598797363246158893559203
e = 17
deg = 9
noise_bits = 16
c1 = 17069480607381333340837059621017041514461037312661575749074463467593711378468501917601145213696262157081974590275851364318126946432567619623442558856499278049000634859710386939661034781830101841558737028294620534431460584889198939890743582295134418218234863044625794900789252930749138452915364022716617829366398541818209985678600543910238332239757640924205524654998000872497132900300803106929276168403073803078292990833759803062978594282481693044544928540953522758918780829701611071981841179667387496533021549067145744230245674295353326670788674422134235059172059397648763177319296047417510386887263201663685604459270
c2 = 22017604496222855387400089488783882102774559652391746781635976591924702436082247234343029133767824949950873390768790867821809530150727619420302922605868959289862308167072315580390032286804422072742556634741359609108164215568204513995809834871745948638995210622023605193809961374191659533045113161205072671662931939694847470718069118230862749096690727993074315524642611506095071814885193074966029279617628571492730244236406415232861297020381115027941652762550708861288283690502892471616548245255984354646123110490438594329667864637941033723511769203613511959066641052710958145498270486098531267360662949728464981997

From there the solve is neat: recover every r_i by exact root, compute clean y_i, interpolate the degree-9 polynomial f(x) over Z_n, and use a Franklin-Reiter-style common-root trick with P(x)=x^17-c1 and Q(x)=f(x)^17-c2. Their gcd yields a linear factor containing m, which decodes directly to the flag. This one felt very clean once the tiny-noise leak clicked.

Solution#

# solve_galatical.sage
#!/usr/bin/env sage
import re
from math import gcd
from gmpy2 import iroot


def parse_output(path):
    vals = {}
    points = {}
    with open(path, "r", encoding="utf-8") as f:
        for line in f:
            line = line.strip()
            if not line or "=" not in line:
                continue
            k, v = [x.strip() for x in line.split("=", 1)]
            if k[0] in ("x", "y", "r") and k[1:].isdigit():
                idx = int(k[1:])
                points.setdefault(idx, {})[k[0]] = Integer(v)
            else:
                vals[k] = Integer(v)
    return vals, points


def interpolate_mod_n(points, n):
    Zn = Zmod(n)
    R = PolynomialRing(Zn, "X")
    X = R.gen()

    f = R(0)
    m = len(points)
    for i in range(m):
        xi, yi = points[i]
        num = R(1)
        den = Zn(1)
        for j in range(m):
            if i == j:
                continue
            xj, _ = points[j]
            num *= (X - xj)
            den *= (xi - xj)

        den_int = int(den)
        g = gcd(den_int, n)
        if g != 1:
            raise ValueError(f"Non-invertible interpolation denominator; gcd={g}")
        f += yi * num * den.inverse_of_unit()
    return f


def gcd_over_zn(a, b, n):
    R = a.parent()
    while b != 0:
        lc = b.leading_coefficient()
        g = gcd(int(lc), n)
        if g != 1:
            return None, g
        b = b * lc.inverse_of_unit()
        a, b = b, a % b

    if a == 0:
        return R(0), None

    lc = a.leading_coefficient()
    g = gcd(int(lc), n)
    if g != 1:
        return None, g
    a = a * lc.inverse_of_unit()
    return a, None


def int_to_bytes(x):
    x = int(x)
    if x == 0:
        return b"\x00"
    return x.to_bytes((x.bit_length() + 7) // 8, "big")


def main():
    vals, raw_points = parse_output("output.txt")
    n = int(vals["n"])
    e = int(vals["e"])
    c1 = int(vals["c1"])
    c2 = int(vals["c2"])

    points = []
    for idx in sorted(raw_points):
        x = int(raw_points[idx]["x"])
        y_noisy = int(raw_points[idx]["y"])
        r_enc = int(raw_points[idx]["r"])

        r, exact = iroot(r_enc, e)
        if not exact:
            raise ValueError(f"r{idx} root is not exact")
        r = int(r)
        y = (y_noisy - r) % n
        points.append((x, y))

    f = interpolate_mod_n([(Zmod(n)(x), Zmod(n)(y)) for x, y in points], n)

    R = f.parent()
    X = R.gen()
    P = X**e - Zmod(n)(c1)
    Q = f**e - Zmod(n)(c2)

    g, nontrivial = gcd_over_zn(P, Q, n)

    m = None
    if g is not None and g.degree() == 1:
        b = g[0]
        m = int((-b) % n)
    elif nontrivial is not None and 1 < nontrivial < n:
        p = int(nontrivial)
        q = n // p
        phi = (p - 1) * (q - 1)
        d = inverse_mod(e, phi)
        m = int(pow(c1, int(d), n))
    else:
        gg = P.gcd(Q)
        if gg.degree() == 1:
            m = int((-gg[0] / gg[1]) % n)

    if m is None:
        raise RuntimeError("Failed to recover m")

    msg = int_to_bytes(m)
    print("m_bytes:", msg)

    try:
        s = msg.decode()
    except Exception:
        s = msg.decode(errors="ignore")

    print("decoded:", s)
    mm = re.search(r"CodeVinci\{[^}]+\}", s)
    if mm:
        print("FLAG:", mm.group(0))


if __name__ == "__main__":
    main()

sage solve_galatical.sage

m_bytes: b'CodeVinci{p0lyn0m14l_rs4_l34ks_r00t5_lm4o}'
decoded: CodeVinci{p0lyn0m14l_rs4_l34ks_r00t5_lm4o}
FLAG: CodeVinci{p0lyn0m14l_rs4_l34ks_r00t5_lm4o}