CU29

Author: 0xIDA
Platform: FlagYard · Category: crypto · Difficulty: Medium

Solvers

solve.py

Summary

RSA-1024 with public exponent e=23 forced to share a factor with φ(n) (so 23 | p−1 or q−1), a small private-related value ee, and a leak (p+q)>>200. Factor via Howgrave–Graham Coppersmith on known MSBs of p derived from the p+q leak; decrypt by taking 23-rd roots mod p and mod q (unique mod the prime where 23 ∤ p−1, 23 roots where 23 | q−1) and CRT.

Solution

Step 1: Factor from (p+q) high bits

# p+q = (pq << 200) + r, r < 2^200
# estimate p from midpoint s, then Coppersmith:
# f(x) = x + pbar  (monic), beta=0.5, X=2^200
# recover p = pbar + x0 dividing n

Step 2: Decrypt non-coprime e

# gcd(e, p-1)=1 → m_p = c^{inv(e,p-1)} mod p
# gcd(e, q-1)=23 → 23 roots of m^23 ≡ c (mod q) via AMM / BSGS on 23-Sylow
# CRT all pairs; keep the printable FlagY{...}

Flag

FlagY{1_b17_7h15_w45_fun_n0nc0pr1m3_4nd_c0pp3r5m17h_mul71v4r1473_4774ck}

Live submitted: success (2026-07-12).

Tools

fpylll LLL (Howgrave–Graham)
gmpy2, sympy (root filtering)
Flagyard MCP submit