当两把锁共用同一把钥匙：RSA模不互素攻击的侦探故事
想象一下，你住在一栋高级公寓里，每户人家都有自己独特的门锁系统。物业公司为了节省成本，偷偷在所有锁芯里使用了相同的核心零件。有一天，一位聪明的住户发现了这个秘密——他只需要拆解自己家的锁，就能推导出整栋楼所有门锁的结构。这就是RSA加密中"模不互素攻击"的生动写照。
1. 从门锁到密钥：理解RSA的基本原理
RSA加密就像一套精密的数字门锁系统，每个用户都拥有两把特殊的"钥匙"：
- 公钥相当于任何人都能复制的门禁卡（由模数
n和指数e组成） - 私钥则是只有主人持有的机械钥匙（包含模数
n和私密指数d）
这个系统的安全性建立在"大数分解难题"上——就像你很难通过观察门禁卡的外形来复制出机械钥匙的内部结构。具体来说：
# 典型RSA密钥生成过程 from Crypto.Util.number import getPrime p = getPrime(1024) # 第一个大素数 q = getPrime(1024) # 第二个大素数 n = p * q # 模数（锁的核心结构） e = 65537 # 公共指数（门禁卡的通用部分)关键点在于p和q必须是随机生成且独立的大素数。如果两套不同的RSA系统意外使用了相同的素数会怎样？就像两把不同的锁使用了相同的核心零件。
2. 粗心的锁匠：模不互素漏洞的产生
让我们回到公寓锁具的比喻。假设物业公司为A住户和B住户安装门锁时：
- A住户的锁：使用零件
p和q₁组装 - B住户的锁：使用零件
p和q₂组装
虽然两把锁看起来完全不同，但它们共享了关键零件p。在RSA加密中，这就表现为：
n₁ = p × q₁ n₂ = p × q₂当这两个模数n₁和n₂出现在CTF赛题或实际系统中时，敏锐的安全工程师会发现：
提示：计算两个大数的最大公约数(GCD)在计算机上是高效操作，即使数字非常大
from math import gcd p = gcd(n₁, n₂) # 轻松提取出共享素数 q₁ = n₁ // p q₂ = n₂ // p3. 侦探工具箱：实战破解步骤详解
让我们以"[羊城杯 2021]Bigrsa"赛题为例，演示完整的攻击流程：
3.1 收集证据
我们获得以下关键信息：
| 参数 | 值 |
|---|---|
| n₁ | 103835296409081751... |
| n₂ | 115383198584677147... |
| e | 65537 |
| 密文c | 604061683027688608... |
3.2 寻找共同点
计算两个模数的GCD：
from Crypto.Util.number import long_to_bytes from gmpy2 import gcd q = gcd(n₁, n₂) p₁ = n₁ // q p₂ = n₂ // q3.3 复制钥匙
现在我们可以为两个系统分别生成私钥：
def get_private_key(e, p, q): phi = (p-1)*(q-1) d = pow(e, -1, phi) # 模反元素 return d d₁ = get_private_key(e, p₁, q) d₂ = get_private_key(e, p₂, q)3.4 层层解密
由于密文经过了双重加密（先n₁后n₂），我们需要按相反顺序解密：
# 第一步解密 m_intermediate = pow(c, d₂, n₂) # 第二步解密 m_plain = pow(m_intermediate, d₁, n₁) print(long_to_bytes(m_plain))4. 安全启示与防御措施
这种攻击之所以有效，根本原因在于密钥生成过程中的随机性缺陷。以下是关键防御策略：
严格的素数生成：
- 使用密码学安全的随机数生成器
- 确保不同密钥间无共享因子
- 推荐使用FIPS 186-4标准
系统级检查：
# 密钥部署前的简单检查 def check_key_safety(n_list): for i in range(len(n_list)): for j in range(i+1, len(n_list)): if gcd(n_list[i], n_list[j]) != 1: raise ValueError("检测到模数共享因子！")架构设计原则：
- 避免同一服务使用多个RSA密钥
- 考虑使用ECC等替代算法
- 实施密钥轮换时确保新旧密钥完全独立
在CTF比赛中，这类题目通常会留下一些蛛丝马迹：
- 提供多个模数n
- 加密链涉及多个RSA操作
- 题目描述暗示"共享"或"重复"元素
下次当你看到两个大模数时，不妨先计算它们的GCD——也许就能像侦探一样，发现隐藏的"共享秘密"。
