RSA部分大整数密码泄露

Question

有木有人知道RSA部分密码泄露怎么做？（不能使用python中的math模块）
(1)RSA密码的公开密钥为,用户秘密保管的私钥为,其中是两个512比特素数的乘积,私钥满足;
(2)密文数据, 这里是明文消息字符串经编码后的整数值并且满足;，即的取值范围为[1,];
(3)为降低赛题求解难度,用户的私钥特定比特位置的密钥信息发生泄漏，即本赛题每组数据均额外已知部分密钥信息;
(4)记MSBs 为最高数位比特 (Most Significant Bits), LSBs 为最低数位比特 (Least Significant Bits). 以整数=0b10000000000000001为例,其比特长度为17, 其中最高10位比特MSBs的二进制形式为0b1000000000=512，最低7位比特LSBs为"0000001",其二进制形式为0b1=1,满足关系: .

题目1：25分
N1=0xa4d80845630d3b332f74f667ec8a0e49aba15b6f0c4f4006161d62c91b78cf6811421cc76609d2d9dba2c43be9d8ecdc6a0dff64a8041dcde52c7f92820b0a38fc91419e8ec9a5c69d47edc6e347934b4d87f97c5759886dac6c1143ff55b8eb11acfaa6cc70956a8ec7796e1a063b123bc2e467e30937c5a69c7ab5f8ed17e1;
e1=0x3458c2e97adef45f741c7db11ece6c0814aa5b6fad9144242cdaa16a6b4f3622477935f98a41765b92892b4de22a391cf08767447df113f5151c86edd109b97f9b045fd8ad5d7a51084684d4e2353db6c0e474d5d79f399a2bf4fd867ec85b7960845ab5497f705914912f797804c06dcff57139e040596d22b141e54835e0d3;
c1=0x91b097a5b1f6b12accdbda15cd2247384e1b3ed8311085a0f3e0dbb5fffce650a355600a02674189d1b7f4075df079c70354a08646e85ecf31dd150220cd1d4ce22d55a946500f4bd8def74fb0acea3e8d2e7bb1d27ebf2ca2e80fc28c3f0d88a041d4a556a18147f66b88c65f19c99b4b94c3f78d468b8accb4da7e7ce31b29;
已知信息: 私钥d1的取值范围为[2的249次方,2的250次方]

Answer 1

引自免费微信小程序：皆我百晓生

要解决这个问题，我们需要利用给定的信息来逼近私钥d1的值。由于私钥d1的取值范围是 [2^249, 2^250)，我们可以采用穷举法遍历这个范围内的数字，然后通过欧拉函数φ(N)、模逆运算以及加密公式来验证每个可能的d1值是否正确。

首先，我们需要计算出欧拉函数φ(N)，根据公式 φ(N) = (p-1)(q-1)，其中 p 和 q 是 N 的两个素因子。由于我们没有 p 和 q 的具体值，但可以通过分解 N 来找到它们。不过，由于 N 是一个512比特的大整数，手动分解非常困难。因此，我们将使用一些优化的方法来寻找这两个素因子。

为了简化问题，我们可以尝试使用Pollard's rho算法或者ECM（Elliptic Curve Method）来尝试分解N。在Python中，我们可以使用gmpy2库来进行大整数操作和素数分解。然而，这里我们不依赖math模块，所以将使用sympy库，它提供了用于大整数操作的功能。

以下是步骤：

1. 使用 sympy 库进行大整数操作和素数分解。
2. 计算欧拉函数φ(N)。
3. 遍历私钥d1的可能范围，计算模逆运算 d1 mod φ(N)。
4. 对于每个d1值，检查是否满足加密公式的等式 c1 ≡ M^e1 mod N。

下面是相应的Python代码实现：

from sympy import isprime, factorint, mod_inverse, powmod

# 给定的N1, e1, c1
N1 = int('a4d80845630d3b332f74f667ec8a0e49aba15b6f0c4f4006161d62c91b78cf6811421cc76609d2d9dba2c43be9d8ecdc6a0dff64a8041dcde52c7f92820b0a38fc91419e8ec9a5c69d47edc6e347934b4d87f97c5759886dac6c1143ff55b8eb11acfaa6cc70956a8ec7796e1a063b123bc2e467e30937c5a69c7ab5f8ed17e1', 16)
e1 = int('3458c2e97adef45f741c7db11ece6c0814aa5b6fad9144242cdaa16a6b4f3622477935f98a41765b92892b4de22a391cf08767447df113f5151c86edd109b97f9b045fd8ad5d7a51084684d4e2353db6c0e474d5d79f399a2bf4fd867ec85b7960845ab5497f705914912f797804c06dcff57139e040596d22b141e54835e0d3', 16)
c1 = int('91b097a5b1f6b12accdbda15cd2247384e1b3ed8311085a0f3e0dbb5fffce650a355600a02674189d1b7f4075df079c70354a08646e85ecf31dd150220cd1d4ce22d55a946500f4bd8def74fb0acea3e8d2e7bb1d27ebf2ca2e80fc28c3f0d88a041d4a556a18147f66b88c65f19c99b4b94c3f78d468b8accb4da7e7ce31b29', 16)

# 素数分解N1
factors = factorint(N1)

# 找到两个素因子p和q
p, q = None, None
for factor in factors:
    if isprime(factor):
        if p is None:
            p = factor
        else:
            q = factor
        break

if p is None or q is None:
    raise ValueError("Could not find prime factors for N1")

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

# 私钥d1的取值范围
start_d1 = 2**249
end_d1 = 2**250

# 寻找满足条件的d1值
for d1 in range(start_d1, end_d1):
    # 模逆运算 d1 mod phi(N)
    d1_inv = mod_inverse(d1, phi_N)

    # 检查加密公式的等式 c1 ≡ M^e1 mod N
    m = powmod(c1, d1_inv, N1)

    if m == 1:
        print(f"Found private key d1: {d1}")
        break

这段代码会输出找到的私钥d1值。注意，由于涉及到大整数运算和素数分解，这个过程可能会非常耗时。在实际应用中，可以考虑使用更高效的算法或者工具来加速素数分解过程。此外，由于我们没有足够的信息来进一步缩小搜索范围，穷举法在这里可能是唯一可行的方案。