# -*- coding: utf-8 -*- from Crypto.Util.number import long_to_bytes, inverse, GCD import sympy as sp
from fpylll import IntegerMatrix, LLL
# ===================== given ===================== c = 83677258507096298448838473157410968562663844066692785784795808568831104839808973945430904217176612281847780586315531356996541690190721036805002490234088269244928701049252093198328154082985532165306398300581341772147191549267469846165106567529323633427454813950145233569952080565179636978713867195303589950560 N = 99731820183974258509491930788425315687997383070140288617931730219025238256184394629749310800530369706494739983435809537993544901646755147227424129804516752136774736421075294396109951803322879567801060761407401694794176564353979061285525272805898515319706858347858066368622209147353721655141025433249553782243 phigh = 206878744347352036226523952451410430637894370598850007775437213854137659947239582113486 e = 65537
# ===================== coppersmith (univariate) ===================== defcoppersmith_univariate_linear(p0: int, N: int, X: int, m: int = 4, t: int = 4): """ Solve f(x)=p0+x has a small root x0 < X modulo an unknown factor of N (p ~ N^0.5). Classic Howgrave-Graham style lattice. For this challenge it works well with m=4,t=4 (you can tweak). """ x = sp.Symbol("x") f = sp.Poly(p0 + x, x) d = f.degree() assert d == 1
# Build polynomials: # g_i(x) = f(x)^i * N^(m-i) for i=0..m-1 # h_j(x) = x^j * f(x)^m for j=0..t-1 polys = [] for i inrange(m): polys.append((f**i) * (N**(m - i))) fm = f**m for j inrange(t): polys.append(fm * sp.Poly(x**j, x))
# max degree = m + t - 1 (since d=1) max_deg = m + t - 1 dim = m + t
# Lattice basis matrix (dim x (max_deg+1)) # Each coefficient of x^k is scaled by X^k M = IntegerMatrix(dim, max_deg + 1) for row, poly inenumerate(polys): poly = sp.Poly(poly, x) for (k,), coeff in poly.terms(): if k <= max_deg: M[row, k] = int(coeff) * (X**k)
# LLL reduce M_red = LLL.reduction(M)
# Take the first reduced vector -> build integer polynomial H(x) v0 = [int(M_red[0, j]) for j inrange(max_deg + 1)] H_coeff = [v0[k] // (X**k) for k inrange(max_deg + 1)] H = sp.Poly(sum(sp.Integer(H_coeff[k]) * x**k for k inrange(max_deg + 1)), x)
# Find integer roots of H (degree small, factor is fine) roots = [] cont, facs = H.factor_list() for fac, exp in facs: if fac.degree() == 1: a, b = fac.all_coeffs() # a*x + b a, b = int(a), int(b) if a != 0and (-b) % a == 0: r = (-b) // a if0 <= r < X: roots.append(r)
# If not found via linear factors, fallback: brute check any integer roots returned by sympy # (Usually not needed for this kind of linear-leak RSA) roots = sorted(set(roots)) return roots, H
defmain(): k = 225 X = 1 << k p0 = phigh << k
roots, H = coppersmith_univariate_linear(p0, N, X, m=4, t=4) ifnot roots: # try a couple of parameter tweaks if needed for (m, t) in [(5, 5), (6, 6), (6, 4), (4, 6)]: roots, H = coppersmith_univariate_linear(p0, N, X, m=m, t=t) if roots: break
ifnot roots: print("[!] No roots found. Try adjusting m/t or ensure fpylll installed correctly.") return
for x0 in roots: p = GCD(p0 + x0, N) if1 < p < N and N % p == 0: q = N // p phi = (p - 1) * (q - 1) d = inverse(e, phi) m = pow(c, d, N) print(long_to_bytes(m)) return
print("[!] Roots found but failed to recover factor. Something is off.")
defencode_flag(flag: str) -> str: parts = flag.split('_') encoded_parts = []
for part in parts: shift = random.randint(1, 9) encoded = ''.join(shift_char(ch, shift) for ch in part) encoded_parts.append(encoded) return'_'.join(encoded_parts)
if __name__ == "__main__": random.seed() flag = '**********' encoded_flag = encode_flag(flag) print(encoded_flag)
defdecode_part(part: str, shift: int) -> str: return''.join(unshift_char(ch, shift) for ch in part)
# 简单打分：更像 flag/英文的得分更高 COMMON = { "NSSCTF", "CTF", "flag", "this", "that", "cipher", "crypto", "box", "hello" } defscore_text(s: str) -> int: sc = 0 # 字符集正常（字母/数字/{}_-）加分 ok = set(string.ascii_letters + string.digits + "{}_-") sc += sum(1for ch in s if ch in ok) # 出现常见关键词加分（忽略大小写） low = s.lower() for w in COMMON: if w.lower() in low: sc += 20 # flag 前缀强约束 if s.startswith("NSSCTF{"): sc += 200 if s.endswith("}"): sc += 30 # 下划线段落结构合理加分 sc += s.count("_") * 5 return sc
defmain(): parts = cipher.split("_") candidates = []
# 每段列出 1..9 的候选 per_part = [] for i, part inenumerate(parts): opts = [] for sh inrange(1, 10): opts.append((sh, decode_part(part, sh))) per_part.append(opts)
# 打印每段候选，方便人工看 print("=== Per-part candidates ===") for i, opts inenumerate(per_part): print(f"\n[Part {i}] cipher = {parts[i]}") for sh, txt in opts: print(f" shift={sh}: {txt}")
# 全组合搜索（段数一般很少，9^n 很小） best = None best_sc = -10**9 for choice in product(range(1, 10), repeat=len(parts)): dec_parts = [decode_part(parts[i], choice[i]) for i inrange(len(parts))] plain = "_".join(dec_parts) sc = score_text(plain) if sc > best_sc: best_sc = sc best = (choice, plain, sc)
print("\n=== Best guess ===") shifts, plain, sc = best print("shifts =", shifts) print("score =", sc) print("plain =", plain)
