p = 151240196317566398919874094060690044886978001146739221635377812709640347441550250665168046149125216617951660209690860015625296899030453965800801283336223544189902980591153121592938172963303968803995733283426759581586368403208379337416298836517168491618212440911971420911495272791409112867645195821357346746831 h = 124332746104765845147133491132959579184849644379099440465281812273660434050281263409975356196112560300248343107170084466976976410232928660489912629913525776979726428263975968343564076005019264661696777686114079504603568726429498116488469855127100166072195548037981863885014261706582936943023968781022607949646
for row in L: f_candidate = abs(row[0]) g_candidate = abs(row[1]) # Check if g_candidate is 350-bit prime if g_candidate.nbits() == 350and is_prime(g_candidate): flag = long_to_bytes(f_candidate) ifb'0xGame'in flag: print("Found flag:", flag) break
n = 92873040755425037862453595432032305849700597051458113741962060511759338242511707376645887864988028778023918585157853023538298808432423892753226386473625357887471318145132753202886684219309732628049959875215531475307942392884965913932053771541589293948849554008069165822411930991003624635227296915315188938427 gift = 10911712225716809560802315710689854621004330184657267444255298781464639032414821020145885934381310240257843204972266622870698161556175406337237650652528640
pbits = 512 kbits = 242
# 直接使用标准已知高位分解方法 deffactor_with_high_bits(n, high, unknown_bits, p_total_bits=512): from sage.allimport Zmod, PolynomialRing PR.<x> = PolynomialRing(Zmod(n)) f = high + x # 尝试不同的 beta 值 for beta in [0.48, 0.45, 0.42, 0.4, 0.38, 0.35]: for epsilon in [0.01, 0.03, 0.05, 0.08, 0.1]: roots = f.small_roots(X=2^unknown_bits, beta=beta, epsilon=epsilon) if roots: return roots[0] returnNone
x0 = factor_with_high_bits(n, gift, kbits) if x0 isnotNone: p = gift + int(x0) if n % p == 0: q = n // p print("成功分解!") print(f"p = {p}") print(f"q = {q}") # 解密 e = 65537 c = 78798946231057858237017891544035026520248922588969396262361286907576401467816384819451190528802344534495780520382462432888103466971743435370588783181267466189564132373143717299869053172848786781320750631382630113459268771330862538801774075395201914653025347332312015985213462835680853607187971669296490439714 phi = (p-1) * (q-1) d = pow(e, -1, phi) m = pow(c, d, n) from Crypto.Util.number import long_to_bytes flag = long_to_bytes(int(m)) print(f"Flag: {flag}") else: print("p 不整除 n") else: print("没有找到解")
# 4. 分析规约后的基向量 print("[*] 正在分析规约后的短向量...") for i inrange(n): # 获取一个规约后的向量 v v = list(B_reduced[i]) # 5. 尝试从向量 v 中恢复 Flag # 向量 v 可能是 flag 向量的整数倍 k*f。通过计算最大公约数(GCD)来找到 k。 non_zero_elements = [abs(x) for x in v if x != 0] ifnot non_zero_elements: continue# 跳过零向量 # 计算所有非零元素的 GCD common_divisor = non_zero_elements[0] for j inrange(1, len(non_zero_elements)): common_divisor = math.gcd(common_divisor, non_zero_elements[j])
# LLL 找到的向量方向可能相反,所以要同时尝试 k 和 -k for sign in [1, -1]: k = common_divisor * sign try: # 用向量 v 除以 k,得到 flag 候选 f_candidate = [x // k for x in v] # 检查候选向量的所有元素是否都在0-127的 ASCII 范围内 is_ascii = all(0 < x < 128for x in f_candidate) if is_ascii: flag_str = "".join(map(chr, f_candidate)) # 检查是否符合已知的 flag 格式 if flag_str.startswith("0xGame{") and flag_str.endswith("}"): return flag_str except (ZeroDivisionError, TypeError): continue except ImportError: print("\n[-] 错误:未找到 fpylll 库。") print("[-] 请使用 'pip install fpylll' 命令进行安装。") # Exit the whole script if the library is missing exit(1) except Exception as e: print(f"\n[-] 在 LLL 规约或分析过程中发生错误: {e}") returnNone
# --- 5. 合并结果并立即发送 --- pwnlog.info("Combining results with CRT and sending secret...") x = crt([Integer(x_mod_p), Integer(x_mod_q)], [p, q]) secret_bytes = x.to_bytes(126, 'big')[:35] secret_hex = secret_bytes.hex() pwnlog.success(f"Secret recovered (hex): {secret_hex}")
io.sendlineafter(b'[-] Give me the secret:', secret_hex.encode()) flag = io.recvall().decode(errors='ignore') pwnlog.success("Received response:\n" + flag) io.close()
# ========= 工具函数 (无变动) ========= defget_prime_factors(n, limit=1000000): factors = {} d = 2 temp_n = n while d * d <= temp_n: if d > limit: break while temp_n % d == 0: factors[d] = factors.get(d, 0) + 1 temp_n //= d d += 1 if temp_n > 1and temp_n <= limit: factors[temp_n] = factors.get(temp_n, 0) + 1 returnsorted(factors.keys())
defextended_gcd(a, b): if a == 0: return b, 0, 1 d, x1, y1 = extended_gcd(b % a, a) x = y1 - (b // a) * x1 y = x1 return d, x, y
defchinese_remainder_theorem(congruences): M = 1 for _, n_i in congruences: M *= n_i result = 0 for a_i, n_i in congruences: M_i = M // n_i _, N_i, _ = extended_gcd(M_i, n_i) result = (result + a_i * M_i * N_i) % M return result
# ========= 离线解密主逻辑 ========= defsolve_offline(): n = p * q phi_n = (p - 1) * (q - 1)
print(f"[+] n: {str(n)[:30]}...") print(f"[+] phi(n): {str(phi_n)[:30]}...") factors = get_prime_factors(phi_n, limit=1000000) print(f"[+] Found {len(factors)} small prime factors of phi(n) up to 1,000,000.")
for p_i in factors: print(f"\n[*] Trying to find e mod {p_i}")
# 寻找合适的基 m base_m = -1 for m insorted(encrypted_data.keys()): # 检查这个基 m 是否能用 ifpow(m, phi_n // p_i, n) != 1: base_m = m break if base_m == -1: print(f" - Could not find a suitable base in provided data for p_i = {p_i}. Skipping.") continue print(f" - Using base m = {base_m} from provided data.") m_prime = pow(base_m, phi_n // p_i, n) c_m = encrypted_data[base_m] c_prime = pow(c_m, phi_n // p_i, n) found_x = -1 for x inrange(p_i): ifpow(m_prime, x, n) == c_prime: found_x = x break if found_x != -1: print(f" - Solved! e \u2261 {found_x} (mod {p_i})") congruences.append((found_x, p_i)) moduli_product *= p_i else: print(f" - Failed to solve for e mod {p_i}.") if moduli_product > E_UPPER_BOUND: print("\n[+] Collected enough congruences to determine e.") break if moduli_product <= E_UPPER_BOUND: print("\n[-] Could not find enough small prime factors to determine e. The attack failed.") return
print("\n[*] Solving for e using Chinese Remainder Theorem...") e = chinese_remainder_theorem(congruences) print(f"[+] Found e: {e}")
if gmpy2.is_prime(e): print("[+] Verification successful: e is a prime number.") else: print("[!] Warning: Calculated e is not a prime number.")
print("\n[*] Calculating private key d and decrypting the flag...") d = pow(e, -1, phi_n) flag_val = pow(c_flag, d, n) try: flag = long_to_bytes(flag_val) print("\n" + "="*50) print(f"[*] DECRYPTED FLAG: {flag.decode()}") print("="*50) except Exception as err: print(f"\n[-] Failed to decode the flag: {err}") print(f"[*] Decrypted integer value: {flag_val}")