给定两个公钥和 e 来查找私钥

问：

我最近正在上网络安全课。我想知道如果我有两个公钥，n1 和 n2（以及指数）——如何为 n1 生成私钥？在此方案中，n1 和 n2 共享素数。

我知道我需要使用

d=e^（−1） mod （p−1）（q−1）

而且我也知道，由于它们共享素数 （p），我可以很容易地找到它们对应的 q。然而，我被困在计算 d。

def calculate_private_key(n1, n2, e):
    # Step 1: Calculate the prime factor (p) shared by n1 and n2
    p = gcd(n1, n2)
    # Step 2: Calculate the remaining factors (q1 and q2)
    q1 = n1 // p
    q2 = n2 // p

    # Step 3: Calculate the totient (phi) of the modulus (n)
    phi1 = (p - 1) * (q1 - 1)
    phi2 = (p - 1) * (q2 - 1)

    # Step 4: Calculate the modular inverse 
    d1 = find_modular_inverse(e, phi1)
    d2 = find_modular_inverse(e, phi2)

    q1_inv = find_modular_inverse(q1, p)
    q2_inv = find_modular_inverse(q2, p)

    d = (d1 * q1 * q2_inv + d2 * q2 * q1_inv) % (p * q1 *q2)

    return d

我假设需要 CRT 来解决 d，这就是我写的，但答案是错误的。我想知道它哪里出了问题。任何见解将不胜感激。我想知道我是否错误地实施了顶级公式。

编辑： 更明确的是，gcd/find_modular_inverse是自定义函数。

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

def find_modular_inverse(q2, p):
    gcd, x, _ = extended_euclidean(p, q2)
    if x < 0:
        x += p
    return x