如何破解共享素数的RSA模数？求解p和q的高效方法

Alice与Bob使用共享素数生成了RSA模数：

• pk_alice: 93145558017597242451057840020003423492065036505715635939073421584870064178836557007438920905568366141278155363295217244442270120551665563816731464612225841456174904661719015967457696683736586858513914335501922092345895701281682242489324726462415020945038049322877151602626496388802926568113827098181488546541
• pk_bob: 130627775975870619265103967461863569685393719623259606834494161761353696231137838485596006850409649916631767658717771142397327842476766835551088514711108732237134464583834085414090472465465656901718533120526240047672780456483182231171430047581628792398849389571220237028177673312592572286345009761324975840273

目标是找出这两个模数对应的素数p和q，但使用sympy的factorint直接分解单个模数耗时极久无输出，求解决方法。

用户原实现代码：

import sympy

def factorize(n):
    factors = sympy.ntheory.factorint(n)
    
    # Les clés du dictionnaire factors contiennent les facteurs premiers et les valeurs correspondent à leurs exposants.
    # Si n est le produit de deux nombres premiers, il y aura deux clés avec des exposants de 1.
    prime_factors = [factor for factor in factors if factors[factor] == 1]

    if len(prime_factors) == 2:
        p, q = prime_factors
        return p, q
    else:
        return None, None  # La factorisation a échoué

# Remplacez n par la valeur de n que vous souhaitez factoriser
n = 130627775975870619265103967461863569685393719623259606834494161761353696231137838485596006850409649916631767658717771142397327842476766835551088514711108732237134464583834085414090472465465656901718533120526240047672780456483182231171430047581628792398849389571220237028177673312592572286345009761324975840273

p, q = factorize(n)

if p and q:
    print(f"Les facteurs premiers de {n} sont {p} et {q}")
else:
    print("La factorisation a échoué.")

核心思路 #

题目明确说明两个模数共享一个素数，这是关键突破口：
假设pk_alice = p * q1，pk_bob = p * q2，那么两个数的最大公约数（gcd）就是共享素数p。得到p后，分别用两个模数除以p就能得到另一个素数q1和q2。

直接分解大整数属于NP难问题，时间复杂度随数字位数指数增长；而求gcd的时间复杂度为O(log(min(n1,n2)))，效率极高，完全不需要暴力分解。

优化后代码 #

import math

# 定义两个RSA模数
pk_alice = 93145558017597242451057840020003423492065036505715635939073421584870064178836557007438920905568366141278155363295217244442270120551665563816731464612225841456174904661719015967457696683736586858513914335501922092345895701281682242489324726462415020945038049322877151602626496388802926568113827098181488546541
pk_bob = 130627775975870619265103967461863569685393719623259606834494161761353696231137838485596006850409649916631767658717771142397327842476766835551088514711108732237134464583834085414090472465465656901718533120526240047672780456483182231171430047581628792398849389571220237028177673312592572286345009761324975840273

# 计算最大公约数，得到共享素数p
p = math.gcd(pk_alice, pk_bob)

# 计算两个模数对应的另一个素数（用整数除法避免浮点数精度问题）
q_alice = pk_alice // p
q_bob = pk_bob // p

# 验证分解结果的正确性
assert pk_alice == p * q_alice
assert pk_bob == p * q_bob

print(f"共享素数p: {p}")
print(f"pk_alice的另一个素数q1: {q_alice}")
print(f"pk_bob的另一个素数q2: {q_bob}")

代码说明 #

1. 用math.gcd直接计算两个大整数的最大公约数，瞬间得到共享素数p；
2. 用整数除法//计算另一个素数，避免浮点数运算带来的精度丢失；
3. 添加断言语句验证分解结果的正确性，确保逻辑无误。

原方法效率低的原因 #

sympy的factorint针对超大素数乘积的分解，本质是尝试暴力搜索或通用分解算法，这类算法的时间复杂度随数字位数指数增长，对于几百位的大整数，耗时会达到天文数字，完全不适用。而利用题目给出的共享素数条件，用gcd方法可以直接绕过复杂的分解过程，效率呈数量级提升。

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