已知n、c1、c2、ct，如何破解随机生成p、q、a的RSA密文？

分析已知条件 #

给定参数的生成逻辑核心关系：

• c1 = (p - a)² >> 128 等价于 (p - a)² = c1 * 2^128 + r1，其中 0 ≤ r1 < 2^128，因此 p - a 与 sqrt(c1 << 128) 误差极小
• c2 = (q + a)² >> 128 同理，q + a 接近 sqrt(c2 << 128)
• 结合 p * q = n，可推导出关于 a 的二次方程，进而求解所有参数

具体步骤 #

1. 计算p-a的候选值m：
   计算 m0 = isqrt(c1 << 128)，验证 m0² - (c1 << 128) < 2^128，满足则m0即为p-a
2. 计算q+a的候选值k：
   计算 k0 = isqrt(c2 << 128)，验证 k0² - (c2 << 128) < 2^128，满足则k0即为q+a
3. 构造二次方程求解a：
   由 p = m + a、q = k - a 和 p*q = n，代入得：

   a² + (m - k)a + (n - mk) = 0
   

   计算判别式 D = (m + k)² - 4n，若D为完全平方数，即可解出a的候选值
4. 筛选合法a：
   从候选值中筛选出128位素数的a
5. 验证参数并解密：
   计算p=m+a、q=k-a，验证p*q=n且均为素数；随后计算私钥d，解密密文ct得到flag

代码实现 #

from math import isqrt
from Crypto.Util.number import isPrime

# 已知参数
n = 6512617643749294302589095438675618776167938720843890101758895197157390356137924323241304471444329557183412977161734627116921570790884877938134980599305707
c1 = 10907285669560468551647268462406489962787063891723057307575398016663082759381321634953803867684535258520696953786905
c2 = 33582698092528772294080029653133275670665396243438255829051457928307809349340703410415434062259818693740005488773964
ct = 2127264588321127239854001986698891905875335763381083235961453034717795577362487952867927688262105005181067989744994023793619461569137294308259815910038249
e = 65537

shift_128 = 1 << 128

# 计算p-a的候选值m
m0 = isqrt(c1 * shift_128)
assert (m0 ** 2) - (c1 * shift_128) < shift_128, "m0不符合误差要求"
m = m0

# 计算q+a的候选值k
k0 = isqrt(c2 * shift_128)
assert (k0 ** 2) - (c2 * shift_128) < shift_128, "k0不符合误差要求"
k = k0

# 求解a的二次方程
D = (m + k) ** 2 - 4 * n
sqrt_D = isqrt(D)
assert sqrt_D ** 2 == D, "判别式非完全平方数"

a1 = ((k - m) + sqrt_D) // 2
a2 = ((k - m) - sqrt_D) // 2

# 筛选合法的a：正整数、128位素数
a = None
for candidate in [a1, a2]:
    if candidate > 0 and isPrime(candidate) and (1 << 127) <= candidate < (1 << 128):
        a = candidate
        break

assert a is not None, "未找到合法的a"

# 验证p、q
p = m + a
q = k - a
assert p * q == n, "p*q与n不匹配"
assert isPrime(p) and isPrime(q), "p或q非素数"

# 解密得到flag
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
pt = pow(ct, d, n)
flag = pt.to_bytes((pt.bit_length() + 7) // 8, byteorder='little').decode()

print(f"p = {p}")
print(f"q = {q}")
print(f"a = {a}")
print(f"flag = {flag}")

运行说明 #

执行代码后会输出正确的p、q、a值及解密后的flag，所有验证步骤确保参数合法性，避免无效计算。

内容的提问来源于stack exchange，提问作者joram