已知共享素数的两个RSA公钥及e，私钥求解问题排查

问题描述 #

近期正在学习网络安全课程，遇到问题：给定两个共享素数的RSA公钥n1、n2及指数e，如何生成n1对应的私钥？
已知公式：
𝑑=𝑒^(−1) 𝑚𝑜𝑑 (𝑝−1)(𝑞−1)
因n1和n2共享素数p，可轻松求出对应q，但计算d时遇阻。尝试用中国剩余定理（CRT）实现，编写了Python代码但结果错误，想请教问题所在，是否公式实现有误？

原实现代码 #

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

补充的工具函数 #

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

问题排查 #

1. CRT应用场景错误
   计算n1对应的私钥完全不需要使用CRT。既然已经分解出n1=pq1，直接计算phi1=(p-1)(q1-1)，再求e在模phi1下的逆元就是n1的私钥d1。代码中引入n2相关的phi2、d2、q2_inv等属于冗余操作，混淆了CRT的适用场景（CRT用于合并同余式，此处无合并需求）。

2. 模逆元计算参数顺序错误
   find_modular_inverse函数的参数设计和内部逻辑完全颠倒：

   • 函数定义应为find_modular_inverse(a, m)，表示求a在模m下的逆元，但当前定义的参数顺序不符合常规逻辑。
   • 内部调用extended_euclidean(p, q2)时参数顺序错误，正确应调用extended_euclidean(a, m)——扩展欧几里得算法是寻找x使得a*x + m*y = gcd(a,m)，当gcd(a,m)=1时，x才是a的模m逆元。当前参数顺序会计算出p的模q2逆元，而非预期结果，这是核心错误。

修正后的代码 #

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:
        g, x, y = extended_euclidean(b, a % b)
        return g, y, x - (a // b) * y

# 修正模逆元函数：求a在模m下的逆元，要求gcd(a,m)=1
def find_modular_inverse(a, m):
    g, x, _ = extended_euclidean(a, m)
    if g != 1:
        raise ValueError("模逆元不存在，因为a和m不互质")
    if x < 0:
        x += m
    return x

def calculate_private_key(n1, n2, e):
    # 步骤1：求共享素数p
    p = gcd(n1, n2)
    # 步骤2：求n1的另一个素因子q1
    q1 = n1 // p
    # 步骤3：计算n1的欧拉函数phi1
    phi1 = (p - 1) * (q1 - 1)
    # 步骤4：计算e的模phi1逆元，即n1的私钥d1
    d1 = find_modular_inverse(e, phi1)
    return d1

验证示例 #

测试一组合法数据：

• 共享素数p=11，q1=13，q2=17
• n1=1113=143，n2=1117=187
• 取e=7（满足gcd(7, (11-1)*(13-1))=1，合法）
• 计算得phi1=120，d1=103（7*103 mod120=1）
  运行修正后的代码calculate_private_key(143,187,7)会返回103，符合预期。

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