Python RSA 私钥解密 - 使用已知公钥计算d

使用 Python 已知 RSA 公钥生成参数，求解私钥 d

假设已知 RSA 公钥参数如下：

• p = 3487583947589437589237958723892346254777
• q = 8767867843568934765983476584376578389
• e = 65537

目标是求解私钥 d。可以使用 RSA 算法中的扩展欧几里得算法来计算。

首先，需要计算 n 的值，即 p 和 q 的乘积：

n = p * q

然后，需要计算 φ(n) 的值，即 (p-1) 和 (q-1) 的乘积：

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

接下来，可以使用扩展欧几里得算法来计算 d 的值。该算法用于求解方程：

e * d ≡ 1 (mod φ(n))

可以使用以下 Python 代码计算 d 的值：

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = extended_gcd(b, a % b)
        return d, y, x - (a // b) * y

p = 3487583947589437589237958723892346254777
q = 8767867843568934765983476584376578389
e = 65537

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

d = extended_gcd(e, phi)[1] % phi

通过以上代码，可以得到 d 的值，从而完成 RSA 私钥的生成。