from sympy import symbols, solve, isprime from sympy.ntheory import sqrt_mod from sympy.ntheory.modular import crt from Crypto.Util.number import long_to_bytes import itertools
x = symbols('x') polynomial = x**3 - 15264966144147258587171776703005926730518438603688487721465*x**2 + 76513250180666948190254989703768338299723386154619468700730085586057638716434556720233473454400881002065319569292923*x - 125440939526343949494022113552414275560444252378483072729156599143746741258532431664938677330319449789665352104352620658550544887807433866999963624320909981994018431526620619 # 解多项式并验证根 roots = solve(polynomial, x) n = [] for root in roots: p = int(root) if not isprime(p): continue if (p + 1) % 4 != 0: continue q = (p + 1) // 4 if isprime(q): n.append(p) else: continue print("找到素数根:", n) N = n[0] * n[1] * n[2] print("计算得到 N =", N)
c = 24884251313604275189259571459005374365204772270250725590014651519125317134307160341658199551661333326703566996431067426138627332156507267671028553934664652787411834581708944
# 获取每个素数的所有平方根 sqrt_list = [] for p in n: roots_p = sqrt_mod(c, p, all_roots=True) sqrt_list.append(roots_p) valid_flags = [] for combo in itertools.product(*sqrt_list): solution = crt(n, combo) if solution: x = solution[0] if (x * x) % N == c: valid_flags.append(x) # 同时检查 N - x x_alt = N - x if (x_alt * x_alt) % N == c: valid_flags.append(x_alt) for candidate in set(valid_flags): flag = long_to_bytes(candidate) print(flag)