RSA 隐写术：从泄露的提示中恢复私钥

from Crypto.Util.number import *\nfrom gmpy2 import \n\nBITS = 233\n\ndef broken(x, bits):\n return x >> bits\n\ndef gen():\n p, q = getPrime(512), getPrime(512)\n n = p * q\n e = 65537\n return n, broken(p + q, BITS)\n\nn, hint = gen()\n# e = 0x10001\ne = 65537\nc = 16589212605025468264862689939961340646400626438824064459026078002373801735937861932598660491280834517490394340315480853421268981930217857435669572426110105938015092688880859031418213297139875807487434491329423279700179082306961439610731922669459168752958192842026918421354512654494583087220572962719510130677\n\n# 1. 将 hint 左移 BITS 位\napprox_pq = hint << BITS\n\n# 2. 计算 p+q 的平方根\napprox_pq_sqrt = isqrt(approx_pq)\n\n# 3. 构造一个近似 n\nn_approx = next_prime(approx_pq_sqrt)\n\n# 4. 分解 n，得到 p 和 q\np, q = gmpy2.next_prime(n_approx, 512), gmpy2.next_prime(n_approx, 512)\n\n# 5. 计算私钥 d\nd = invert(e, (p-1)(q-1))\n\n# 6. 使用私钥解密密文 c\nm = pow(c, d, n)\n\n# 7. 得到最终结果\nflag = long_to_bytes(m)\nprint(flag)