RSA密码挑战：如何通过n、e、c、r提取素因子p和q

首先，你当前的pa/qa计算逻辑存在错误，这是导致后续无法推进的核心问题。先修正这一步，再用格基还原方法（Coppersmith）补全未知位。

1. 修正pa和qa的计算 #

生成r的逻辑是：

• mask = 0x555...555（1024位，二进制010101...01），保留p的偶数位（从0开始数，最低位是位0）
• mask << 1 = 0xAAAA...AAAA（1024位，二进制101010...10），保留q的奇数位
• r = (p & mask) + (q & mask<<1)：r的二进制位从高位到低位，依次是q的奇数位、p的偶数位交替排列（比如r的最高位是q的第1023位，次高位是p的第1022位，以此类推）

你的原代码把r的偶数索引位（高位到低位）分配给pa，这搞反了对应关系。修正后的代码如下：

# 转换为1024位二进制字符串，高位在前，不足补0
r_bin = bin(r)[2:].zfill(1024)
pa_bits = []
qa_bits = []

for idx, bit in enumerate(r_bin):
    if idx % 2 == 1:
        # 奇数索引位对应p的偶数位（位1022、1020...0）
        pa_bits.append(bit)
        qa_bits.append('0')
    else:
        # 偶数索引位对应q的奇数位（位1023、1021...1）
        qa_bits.append(bit)
        pa_bits.append('0')

pa = int(''.join(pa_bits), 2)
qa = int(''.join(qa_bits), 2)

2. 用Coppersmith算法补全未知位 #

修正后，pa是p的已知位（偶数位），未知位（奇数位）全为0；qa是q的已知位（奇数位），未知位（偶数位）全为0。我们需要找到x（p的未知位组成的数），使得p = pa + x是n的素因子，且x仅在pa的0位上有值（即x是512位的数，对应p的1023、1021...1位）。

Coppersmith算法可以在模数n下找到多项式的小根，这里我们构造多项式f(x) = pa + x，寻找x使得f(x)整除n。

方法1：使用SageMath（推荐）

SageMath内置了Coppersmith算法的实现，直接调用即可：

# 替换为题目给定的n、pa
n = 0x...
pa = 0x...

# 定义多项式环，模数为n
PR.<x> = PolynomialRing(Zmod(n))
f = pa + x

# 寻找x < 2^512的小根（x是512位）
roots = f.small_roots(X=2^512, beta=0.5)

for root in roots:
    p_candidate = pa + int(root)
    if n % p_candidate == 0:
        q_candidate = n // p_candidate
        # 验证是否为素数
        if is_prime(p_candidate) and is_prime(q_candidate):
            print(f"p = {p_candidate}")
            print(f"q = {q_candidate}")
            break

方法2：使用Python的coppersmith库

如果用纯Python，安装coppersmith库后执行：

import coppersmith

# 替换为题目给定的n、pa
n = 0x...
pa = 0x...

# 寻找小根，x的上限是2^512
root = coppersmith.small_roots(pa + coppersmith.X, n, X=2**512, beta=0.5)[0]
p_candidate = pa + int(root)
q_candidate = n // p_candidate

print(f"p = {p_candidate}")
print(f"q = {q_candidate}")

3. 破解明文 #

得到p和q后，计算私钥d并解密：

# 替换为题目给定的e、c
e = 0x...
c = 0x...

phi = (p_candidate - 1) * (q_candidate - 1)
d = pow(e, -1, phi)
m_int = pow(c, d, n)
# 转换为bytes得到flag
flag = m_int.to_bytes((m_int.bit_length() + 7) // 8, byteorder='big')
print(flag.decode())

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