from Crypto.Util.number import * from gmpy2 import *

BITS = 233

def broken(x, bits): return x >> bits

def gen(): p, q = getPrime(512), getPrime(512) n = p * q e = 65537 return n, broken(p + q, BITS)

n, hint = gen() e = 0x10001 c = 16589212605025468264862689939961340646400626438824064459026078002373801735937861932598660491280834517490394340315480853421268981930217857435669572426110105938015092688880859031418213297139875807487434491329423279700179082306961439610731922669459168752958192842026918421354512654494583087220572962719510130677

1. 将 hint 左移 BITS 位

approx_pq = hint << BITS

2. 计算 p+q 的平方根

approx_pq_sqrt = isqrt(approx_pq)

3. 构造一个近似 n

n_approx = next_prime(approx_pq_sqrt)

4. 分解 n，得到 p 和 q

p, q = gmpy2.next_prime(n_approx, 512), gmpy2.next_prime(n_approx, 512)

5. 计算私钥 d

d = invert(e, (p-1)*(q-1))

6. 使用私钥解密密文 c

m = pow(c, d, n)

7. 得到最终结果

flag = long_to_bytes(m) print(flag)