Python RSA加密挑战：如何破解readme变量？

核心原理 #

加密过程本质是将明文m（readme转成的整数）进行多次模幂运算，最终等价于：
cipher = m^E mod N
其中E是keys中所有16位素数的乘积，N是RSA的模数。我们需要通过已知的N、私钥d、E和cipher反向求解m。

步骤1：计算总加密指数E #

把keys里的10个素数相乘，得到总指数：

E = 1
for _, e_i in keys:
    E *= e_i

步骤2：分解模数N #

使用Pollard's Rho算法分解N得到两个大素数p和q（这是分解大整数的高效算法，适合RSA模数）：

import math
import random

def pollards_rho(n):
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3
    if n % 5 == 0:
        return 5
    while True:
        c = random.randint(1, n-1)
        f = lambda x: (pow(x, 2, n) + c) % n
        x, y, d = 2, 2, 1
        while d == 1:
            x = f(x)
            y = f(f(y))
            d = math.gcd(abs(x-y), n)
        if d != n:
            return d

N, d = my_key
p = pollards_rho(N)
q = N // p
assert p * q == N  # 验证分解正确性

步骤3：分别求解模p和模q的明文 #

根据欧拉定理，对素数p，有m^E ≡ cipher mod p，我们需要求m：

• 计算φ(p) = p-1，求E模φ(p)的逆元d_p，然后m_p = pow(cipher, d_p, p)
• 同理对q计算m_q = pow(cipher, d_q, q)，其中d_q是E模φ(q)=q-1的逆元

如果E和φ(p)/φ(q)不互质（逆元不存在），因为m是短字节串转成的整数（长度约25字节），可以直接暴力枚举候选值：

# 处理模p的情况
phi_p = p - 1
cipher_mod_p = cipher % p
try:
    d_p = pow(E, -1, phi_p)
    m_p = pow(cipher_mod_p, d_p, p)
except ValueError:
    m_p = None
    max_candidate = 256 * 25  # 对应readme的大致字节长度
    for candidate in range(max_candidate):
        if pow(candidate, E, p) == cipher_mod_p:
            m_p = candidate
            break
    assert m_p is not None, "模p枚举失败"

# 处理模q的情况同理
phi_q = q - 1
cipher_mod_q = cipher % q
try:
    d_q = pow(E, -1, phi_q)
    m_q = pow(cipher_mod_q, d_q, q)
except ValueError:
    m_q = None
    max_candidate = 256 * 25
    for candidate in range(max_candidate):
        if pow(candidate, E, q) == cipher_mod_q:
            m_q = candidate
            break
    assert m_q is not None, "模q枚举失败"

步骤4：用中国剩余定理合并结果 #

现在我们有两个同余式：
m ≡ m_p mod p
m ≡ m_q mod q
通过中国剩余定理合并得到最终的m：

inv_p_q = pow(p, -1, q)
m = (m_q - m_p) * inv_p_q % q
m = m_p + m * p

步骤5：转换为原始字节串 #

最后把整数m转回字节串，得到readme：

from Crypto.Util.number import long_to_bytes
readme = long_to_bytes(m)
print(readme.decode('utf-8'))

完整可运行代码 #

from Crypto.Util.number import long_to_bytes
import math
import random

def pollards_rho(n):
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3
    if n % 5 == 0:
        return 5
    while True:
        c = random.randint(1, n-1)
        f = lambda x: (pow(x, 2, n) + c) % n
        x, y, d = 2, 2, 1
        while d == 1:
            x = f(x)
            y = f(f(y))
            d = math.gcd(abs(x-y), n)
        if d != n:
            return d

# 替换为已知的输入值
my_key = (YOUR_N_VALUE, YOUR_D_VALUE)
keys = [(YOUR_N_VALUE, e1), (YOUR_N_VALUE, e2), ..., (YOUR_N_VALUE, e10)]
cipher = YOUR_CIPHER_VALUE

# 步骤1：计算总指数E
E = 1
for _, e_i in keys:
    E *= e_i

# 步骤2：分解N
N, d = my_key
p = pollards_rho(N)
q = N // p
assert p * q == N, "N分解失败"

# 步骤3：求解模p和模q的明文
phi_p = p - 1
cipher_mod_p = cipher % p
try:
    d_p = pow(E, -1, phi_p)
    m_p = pow(cipher_mod_p, d_p, p)
except ValueError:
    m_p = None
    max_candidate = 256 * 25  # 对应readme的大致字节长度
    for candidate in range(max_candidate):
        if pow(candidate, E, p) == cipher_mod_p:
            m_p = candidate
            break
    assert m_p is not None, "模p枚举失败"

phi_q = q - 1
cipher_mod_q = cipher % q
try:
    d_q = pow(E, -1, phi_q)
    m_q = pow(cipher_mod_q, d_q, q)
except ValueError:
    m_q = None
    max_candidate = 256 * 25
    for candidate in range(max_candidate):
        if pow(candidate, E, q) == cipher_mod_q:
            m_q = candidate
            break
    assert m_q is not None, "模q枚举失败"

# 步骤4：中国剩余定理合并
inv_p_q = pow(p, -1, q)
m = (m_q - m_p) * inv_p_q % q
m = m_p + m * p

# 步骤5：转换为字节串
readme = long_to_bytes(m)
print("原始readme:", readme.decode('utf-8'))

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