BUUCTF_Crypto进阶：RSA多组n与c的共模攻击与模不互素实战

1. RSA多组n与c的共模攻击原理剖析

当面对20组不同的(n, c)对时，首先要理解模不互素（即存在公共因子）的数学含义。假设有两个模数n₁和n₂，如果它们不是互质的（gcd(n₁, n₂) ≠ 1），那么通过计算最大公约数可以直接分解出公共素数因子p。例如：

• 给定n₁ = p * q₁，n₂ = p * q₂
• 计算gcd(n₁, n₂) = p，即可得到公共因子

实战案例：在BUUCTF题目中，遍历所有n的组合后发现n₅和n₁₈存在公共因子p=132585806383798...，此时：

1. 分解n₅得到p和q = n₅ // p
2. 计算欧拉函数φ(n) = (p-1)*(q-1)
3. 通过私钥指数d ≡ e⁻¹ mod φ(n)解密密文

from Crypto.Util.number import * from math import gcd n5 = 22822039733049388110936778173014765663663303811791283234361230649775805923902173438553927805407463106104699773994158375704033093471761387799852168337898526980521753614307899669015931387819927421875316304591521901592823814417756447695701045846773508629371397013053684553042185725059996791532391626429712416994990889693732805181947970071429309599614973772736556299404246424791660679253884940021728846906344198854779191951739719342908761330661910477119933428550774242910420952496929605686154799487839923424336353747442153571678064520763149793294360787821751703543288696726923909670396821551053048035619499706391118145067 n18 = 19591441383958529435598729113936346657001352578357909347657257239777540424811749817783061233235817916560689138344041497732749011519736303038986277394036718790971374656832741054547056417771501234494768509780369075443550907847298246275717420562375114406055733620258777905222169702036494045086017381084272496162770259955811174440490126514747876661317750649488774992348005044389081101686016446219264069971370646319546429782904810063020324704138495608761532563310699753322444871060383693044481932265801505819646998535192083036872551683405766123968487907648980900712118052346174533513978009131757167547595857552370586353973 p = gcd(n5, n18) q = n5 // p

2. 模不互素攻击的数学基础

核心定理：若两个模数n₁和n₂共享同一个素数因子p，则：

• gcd(n₁, n₂) = p
• 分解n₁和n₂的时间复杂度降为O(log n)

攻击条件：

1. 存在多组(n, c)对
2. 至少有两组n值非互质
3. 使用相同的公钥指数e（如常见的e=65537）

数学推导：

• 当p已知时，q = n // p
• φ(n) = (p-1)*(q-1)
• d ≡ e⁻¹ mod φ(n)
• 明文m ≡ cᵈ mod n

3. Python自动化攻击实现

完整攻击脚本需要实现以下功能：

1. 遍历所有n的组合计算gcd
2. 自动识别存在公共因子的n对
3. 解密对应的密文

from Crypto.Util.number import long_to_bytes def attack(n_list, c_list, e=65537): for i in range(len(n_list)): for j in range(i+1, len(n_list)): p = gcd(n_list[i], n_list[j]) if p != 1: n = n_list[i] q = n // p phi = (p-1)*(q-1) d = pow(e, -1, phi) m = pow(c_list[i], d, n) return long_to_bytes(m) return None # 示例数据 n_values = [n1, n2, ..., n20] # 替换为实际的n列表 c_values = [c1, c2, ..., c20] # 替换为实际的c列表 print(attack(n_values, c_values))

4. CTF实战中的优化技巧

性能优化：

• 使用gmpy2库加速大数运算
• 并行计算gcd（多线程处理n的组合）
• 提前终止：发现第一个有效p后立即停止计算

常见陷阱：

1. 大数运算溢出：确保使用支持大整数的库
2. 错误的字节转换：注意long_to_bytes的端序问题
3. 模数顺序混淆：确保n和c的索引对应

进阶场景：

• 当e与φ(n)不互素时，需处理解密异常
• 使用中国剩余定理(CRT)加速解密过程
• 结合Coppersmith攻击处理部分密钥泄露

5. 防御措施与出题思路

安全建议：

1. 生成密钥时确保所有模数互质
2. 使用足够大的素数差距（避免随机数生成器缺陷）
3. 定期更换密钥

CTF出题技巧：

• 隐藏公共因子：让p的差值大于1e5
• 混合攻击手段：结合低加密指数攻击
• 增加干扰项：插入完全随机的(n,c)对

我曾在一个实际项目中遇到类似场景，当时通过批量处理500组(n,c)数据，发现其中3组存在公共因子。通过优化gcd计算算法，将原本需要2小时的任务缩短到15分钟完成。关键点在于使用欧几里得算法的迭代实现而非递归，并采用并行计算框架。