RSA解密技术求助：已知p、q、n、e、c，无法恢复flag

核心思路 #

RSA解密的关键是求出私钥d，通过m = pow(c, d, n)得到明文后，再转换为字节形式的flag。以下是具体实现步骤：

基础解法（适用于e与φ(n)互质的情况） #

1. 计算欧拉函数φ(n)
   已知n = p*q，p、q为素数，欧拉函数公式：

phi = (p - 1) * (q - 1)

2. 求解私钥d
   d是e在模phi下的乘法逆元，Python 3.8+可直接用内置函数计算：

d = pow(e, -1, phi)

3. 解密密文得到明文

m = pow(c, d, n)

4. 转换为flag
   将整数明文转回字节并解码：

from Crypto.Util.number import long_to_bytes
flag = long_to_bytes(m).decode()
print(flag)

通用CRT解法（兼容所有情况） #

如果出现逆元不存在的报错（说明gcd(e, φ(n)) > 1），改用中国剩余定理(CRT)分解计算：

from Crypto.Util.number import long_to_bytes

# 替换为题目给出的实际参数
p = 0x... 
q = 0x...
e = 88
c = 0x...

# 扩展欧几里得算法，用于CRT结果合并
def extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    g, x, y = extended_gcd(b, a % b)
    return (g, y, x - (a // b) * y)

# CRT合并两个模下的结果
def crt(a1, m1, a2, m2):
    g, x, y = extended_gcd(m1, m2)
    assert (a2 - a1) % g == 0, "无解"
    lcm = m1 * m2 // g
    tmp = (a2 - a1) // g * x % (m2 // g)
    return (a1 + m1 * tmp) % lcm

# 分别在模p和模q下解密
c_p = c % p
c_q = c % q
d_p = pow(e, -1, p-1)
d_q = pow(e, -1, q-1)
m_p = pow(c_p, d_p, p)
m_q = pow(c_q, d_q, q)

# 合并得到最终明文
m = crt(m_p, p, m_q, q)
flag = long_to_bytes(m).decode()
print(flag)

注意事项 #

• 务必将代码中的占位符（p、q、c）替换为题目给出的实际数值，注意大整数的格式（避免遗漏前缀或位数错误）
• 如果运行报错，优先检查参数复制是否正确

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