Treasury Audit

RSA-2048 done correctly (random PKCS#1 v1.5 padding, e = 65537), but a memory dump leaks the top 574 bits of the 1024-bit prime p. Knowing more than half of the high bits of a factor makes the rest recoverable by univariate Coppersmith. The unknown low 450 bits of p are a small root of f(x) = p_high + x modulo the secret factor p, so a Howgrave-Graham lattice reduced with LLL pulls them out. Sage is not required; the lattice and reduction are done in pure Python (mpmath).

Solve

1. Read challenge.txt: n, e = 65537, p_high (p with its low 450 bits zeroed), and ciphertext c. With 574 known high bits the unknown part is 2^450 < n^0.22, comfortably inside the n^0.25 Coppersmith limit for a degree-1 root modulo a half-size factor.
2. Build the Howgrave-Graham lattice for the monic polynomial f(x) = p_high + x:
   • g_i(x) = n^(h-i) * f(x)^i for i = 0..h
   • h_i(x) = x^i * f(x)^h for i = 1..t Scale column k by X^k (X = 2^450). With h = t = 4 (dimension 9) the bound is met.
3. LLL-reduce. The shortest reduced vector is a polynomial that vanishes at the true small root over the integers, not just mod p. Find its integer root, set p = p_high + x, and confirm n % p == 0.
4. Decrypt: q = n // p, d = e^-1 mod (p-1)(q-1), m = c^d mod n. The plaintext is a PKCS#1 v1.5 block; the flag is plain ASCII inside it.

Full working solver (pure Python, no Sage; saved as solve.py next to challenge.txt):

#!/usr/bin/env python3
import re

import mpmath
from Crypto.Util.number import inverse, long_to_bytes

mpmath.mp.dps = 1500

n = 20617455663957563943267326918617398723675048338700713508388960337975656074956983954064553970232006105633822724545049106949889041967134068405950797243962890380652813070549392311724315694576720318394577417831762411162063790168382307801789490753058437672849231668739056316117671801790905154610394734059247857646044105297843204679863793846337246723259252782851848506544277634589232584330688766380641104405598348156924547283668145466744363813519320248440414734847004384358617700598907088226681244793505417553863937933376546436886127459797975723513300591424081072414325387861807381952526820669185389031630281315242655170717
e = 65537
p_high = 135821285288920085946400642493014096417179798771949765976749043914308535043229221291771123359432312700587822143272544010115732019245443039378869303523804196896440047381409730337025746802127495444758067618759291612503761938664380636654095888464531365956441579793480169836657177615766339596852373964556817399808
c = 15399453910127061789675963240803320036190619586685886168849952792176844266710864840696934360866933747435426651819430663651239409026723624056591682946786774471942295921105659579581045823901601924759841105403281205054712833860982070982224894217765296106283067730766592746637151191786740864644672613168298236545616220412521561818761283896777842924383090123845548849139149118912752576502103168975646962571588150298263392656503798048473829431960775446201697629078858470141849733084816666011136002572028379569782708766506079759764753618433774520470069158597532689469756907803181662085381061072253761074271076342865689340509

UNKNOWN_BITS = 450


def lll(B, delta=0.99):
    B = [row[:] for row in B]
    n = len(B)
    width = len(B[0])
    mp = mpmath
    G = [[mp.mpf(sum(a * b for a, b in zip(B[i], B[j]))) for j in range(n)] for i in range(n)]
    mu = [[mp.mpf(0)] * n for _ in range(n)]
    Bnorm = [mp.mpf(0)] * n

    def recompute_row(i):
        for j in range(i):
            s = G[i][j] - sum(mu[j][k] * mu[i][k] * Bnorm[k] for k in range(j))
            mu[i][j] = s / Bnorm[j]
        Bnorm[i] = G[i][i] - sum(mu[i][k] ** 2 * Bnorm[k] for k in range(i))

    for i in range(n):
        recompute_row(i)

    k = 1
    while k < n:
        for j in range(k - 1, -1, -1):
            if abs(mu[k][j]) > 0.5:
                q = int(mp.nint(mu[k][j]))
                if q != 0:
                    B[k] = [B[k][i] - q * B[j][i] for i in range(width)]
                    for i in range(n):
                        if i != k:
                            G[k][i] = mp.mpf(sum(a * b for a, b in zip(B[k], B[i])))
                            G[i][k] = G[k][i]
                    G[k][k] = mp.mpf(sum(a * a for a in B[k]))
                    recompute_row(k)
        if Bnorm[k] >= (delta - mu[k][k - 1] ** 2) * Bnorm[k - 1]:
            k += 1
        else:
            B[k], B[k - 1] = B[k - 1], B[k]
            G[k], G[k - 1] = G[k - 1], G[k]
            for r in range(n):
                G[r][k], G[r][k - 1] = G[r][k - 1], G[r][k]
            recompute_row(k - 1)
            recompute_row(k)
            for i in range(k + 1, n):
                recompute_row(i)
            k = max(k - 1, 1)
    return B


def polymul(p, q):
    r = [0] * (len(p) + len(q) - 1)
    for i, pi in enumerate(p):
        for j, qj in enumerate(q):
            r[i + j] += pi * qj
    return r


def coppersmith_known_high(N, a, X, h, t):
    f = [a, 1]
    fpows = [[1]]
    for _ in range(h + t):
        fpows.append(polymul(fpows[-1], f))
    polys = []
    for i in range(h + 1):
        polys.append([(N ** (h - i)) * coef for coef in fpows[i]])
    for i in range(1, t + 1):
        polys.append([0] * i + fpows[h][:])
    deg = max(len(p) for p in polys)
    M = []
    for p in polys:
        row = [0] * deg
        for k, coef in enumerate(p):
            row[k] = coef * (X ** k)
        M.append(row)
    red = lll(M)
    for row in red:
        coeffs = [row[k] // (X ** k) for k in range(deg)]
        while len(coeffs) > 1 and coeffs[-1] == 0:
            coeffs.pop()
        if len(coeffs) <= 1:
            continue
        try:
            roots = mpmath.polyroots([mpmath.mpf(c) for c in coeffs[::-1]], maxsteps=500, extraprec=600)
        except Exception:
            continue
        for r in roots:
            if abs(mpmath.im(r)) > 1e-6:
                continue
            ri = int(mpmath.nint(mpmath.re(r)))
            for cand_x in (ri - 1, ri, ri + 1):
                cand = a + cand_x
                if 1 < cand < N and N % cand == 0:
                    return cand
    return None


p = coppersmith_known_high(n, p_high, 1 << UNKNOWN_BITS, h=4, t=4)
assert p is not None and n % p == 0, "Coppersmith failed to recover p"
q = n // p
d = inverse(e, (p - 1) * (q - 1))
m = pow(c, d, n)
mb = long_to_bytes(m)
print("recovered p bit length:", p.bit_length())
flag = re.search(rb"SVIUSCG\{[^}]*\}", mb)
print("flag =", flag.group(0).decode() if flag else mb)

$ python3 solve.py
recovered p bit length: 1024
flag = SVIUSCG{c0pp3rsm1th_wh1sp3rs_4cr0ss_th3_l4tt1c3}

The recovered p is a genuine 1024-bit prime and n % p == 0, confirming the factorisation. Runtime is about half a minute.

Flag: SVIUSCG{c0pp3rsm1th_wh1sp3rs_4cr0ss_th3_l4tt1c3}