THE GARDEN

hello

Updated 19 Sep 2026

• •

  Attribution

  • •

    Solved by rn. AI-assisted solve; the original assistance link is preserved below.

• •

  What it asked

  • •

    Decrypt an RSA-like ciphertext whose plaintext is a polynomial in $A=(\mathbb Z/N\mathbb Z)[t]/(t^{10}-2)$. The generator chose $e$ as the inverse of $\Phi_{\mathrm{gen}}-d$ modulo $\Phi_{\mathrm{gen}}$, where $\Phi_{\mathrm{gen}}=(p^{10}-1)(q^{10}-1)$ and $d$ is small.

• •

  Math — factor N

  • •

    From $e(\Phi_{\mathrm{gen}}-d)\equiv1\pmod{\Phi_{\mathrm{gen}}}$, obtain $ed+1=k\Phi_{\mathrm{gen}}$. Since $\Phi_{\mathrm{gen}}$ is close to $N^{10}$ and $d$ is small, $k/d$ appears among the useful continued-fraction convergents of $e/N^{10}$ for this instance.

  • •

    For every candidate $(k,d)$, compute $\Phi=(ed+1)/k$. Then $S=N^{10}-\Phi+1=p^{10}+q^{10}$ and $p^{10}q^{10}=N^{10}$.

  • •

    The roots of $X^2-SX+N^{10}$ are $p^{10}$ and $q^{10}$. Require a nonnegative square discriminant, exact parity, exact tenth roots, $pq=N$, and primality. These checks reject continued-fraction false positives.

• •

  Math — decrypt in the quotient ring

  • •

    $\Phi_{\mathrm{gen}}$ is not the Euler totient of this polynomial quotient ring, so the small generator value $d$ is not automatically the decryption exponent.

  • •

    Factor $x^{10}-2$ over $\mathrm{GF}(p)$ and $\mathrm{GF}(q)$. For each square-free irreducible factor of degree $f$, the component is $\mathrm{GF}(p^f)$ or $\mathrm{GF}(q^f)$, whose nonzero elements have order $p^f-1$ or $q^f-1$.

  • •

    Take $\lambda$ as the least common multiple of those component orders, then $d_{\mathrm{true}}\equiv e^{-1}\pmod\lambda$. Positive exponentiation also preserves zero components, so $c^{d_{\mathrm{true}}}$ recovers the polynomial even when a component is zero.

  • •

    Serialize all ten coefficients at one fixed byte width, preserve leading zero bytes, and validate complete PKCS#7 padding plus the COMPFEST18{ prefix. Finally require $m^e=c$ in the quotient ring.

• •

  Solution

  • •

    from sage.all import *
    
    def exact_tenth_root(v):
        root, exact = Integer(v).nth_root(10, truncate_mode=True)
        if not exact:
            raise ValueError('not a tenth power')
        return root
    
    def recover_factors(N, e):
        for conv in continued_fraction(QQ(e) / N**10).convergents():
            k, d = conv.numerator(), conv.denominator()
            if k == 0 or d <= 1 or (e*d + 1) % k:
                continue
            phi_guess = (e*d + 1) // k
            S = N**10 - phi_guess + 1
            disc = S*S - 4*N**10
            if disc < 0 or not disc.is_square():
                continue
            root = isqrt(disc)
            if (S + root) % 2:
                continue
            try:
                p = exact_tenth_root((S + root) // 2)
                q = exact_tenth_root((S - root) // 2)
            except ValueError:
                continue
            if p*q == N and p.is_prime() and q.is_prime():
                return p, q
        raise ValueError('no valid convergent')
    
    def component_exponent(prime):
        R = PolynomialRing(GF(prime), 'x'); x = R.gen()
        factors = (x**10 - 2).factor()
        assert all(mult == 1 for _, mult in factors)
        return lcm(prime**f.degree() - 1 for f, _ in factors)
    
    p, q = recover_factors(N, e)
    lam = lcm(component_exponent(p), component_exponent(q))
    d_true = inverse_mod(e, lam)
    m = c**d_true
    assert m**e == c
    
    coefficients = list(m) + [0] * (10 - len(list(m)))
    for width in range(1, 50):
        try:
            padded = b''.join(int(v).to_bytes(width, 'big') for v in coefficients)
        except OverflowError:
            continue
        pad = padded[-1]
        if (1 <= pad <= 10 and padded.endswith(bytes([pad]) * pad)
                and padded.startswith(b'COMPFEST18{')):
            print(padded[:-pad].decode())
            break
    else:
        raise ValueError('no valid fixed-width, padded plaintext')
    

• •

  Verification

  • •

    Reproduced from the printed $N$, $e$, and ciphertext: $N$ is 2043 bits; the successful continued-fraction candidate was number 2903; $x^{10}-2$ factors with degrees $[2,4,4]$ over both prime fields; coefficient width is 6 bytes. The plaintext matches the PDF and re-encrypts to the supplied ciphertext exactly.

• •

  Concepts

  • •

    Wiener's Attack (Continued Fractions, Small Private Exponent)

  • •

    Finite Fields (Galois Fields: GF(p) and GF(2^n))

  • •

    Polynomial quotient rings; CRT decomposition; exact integer-root validation.

• •

  Source

  • •

    Source: team PDF, “Write Up COMPFEST18 Qualifier by PLN - Dokter Amnesia Pecinta PDF”. Page numbers below refer to the PDF’s printed page numbers. Printed pp. 60–70.

  • •

    AI assistance: https://share.gemini.google/MovTvzN8WSNf

◌ Explore connections in Graph view