CTF实战：Python脚本秒解BUUCTF RSA共模攻击题

当你第一次在BUUCTF平台看到那道名为"[BJDCTF2020]rsa_output"的题目时，可能会被那一长串数字搞得晕头转向。别担心，这正是CTF比赛的魅力所在——看似复杂的问题背后往往隐藏着优雅的数学原理。本文将带你从零开始，一步步拆解这道RSA共模攻击题，让你不仅知其然，更知其所以然。

1. 题目分析与攻击识别

打开题目附件，我们首先看到两组看似杂乱无章的数据：

{210583393373...67111, 2767}
{210583393373...67111, 3659}

以及两段密文message1和message2。有经验的CTF选手一眼就能认出这是RSA加密的参数格式——大数字是模数n，较小的数字是公钥指数e。这里有几个关键观察点：

• 两组数据中的n值完全相同
• 两个e值不同（e1=2767，e2=3659）
• 提供了对应的两条密文c1和c2

这种配置正是 RSA共模攻击 的典型场景。共模攻击利用了同一个模数n被多个公钥使用时的安全漏洞。具体来说，当两个公钥(n,e1)和(n,e2)的指数e1和e2互质时，攻击者可以恢复出明文，而无需知道私钥d。

提示：在真实的密码学应用中，绝对不要重复使用相同的模数n，这正是本题想要传达的安全教训。

2. 共模攻击的数学原理

理解攻击背后的数学原理至关重要，这能帮助你在遇到变种题目时灵活应对。共模攻击的核心在于 扩展欧几里得算法 和 中国剩余定理 的结合应用。

假设我们有以下两个加密过程：

c1 ≡ m^e1 mod n
c2 ≡ m^e2 mod n

如果e1和e2互质（即gcd(e1,e2)=1），那么根据扩展欧几里得算法，存在整数s1和s2使得：

e1*s1 + e2*s2 = 1

然后我们可以通过以下方式恢复明文m：

m ≡ (c1^s1 * c2^s2) mod n

这个等式的正确性可以通过简单的数学推导验证：

(c1^s1 * c2^s2) ≡ (m^e1)^s1 * (m^e2)^s2 ≡ m^(e1*s1 + e2*s2) ≡ m^1 ≡ m mod n

3. 实战Python脚本编写

现在让我们把理论转化为实践。我们将使用Python的gmpy2和libnum库来实现攻击。以下是完整的解题脚本：

import gmpy2
import libnum

# 题目提供的参数
n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
e1 = 2767
e2 = 3659
c1 = 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
c2 = 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227

# 使用扩展欧几里得算法求系数
gcd, s1, s2 = gmpy2.gcdext(e1, e2)

# 确保s1为正数，若为负则需要处理
if s1 < 0:
    s1 = -s1
    c1 = gmpy2.invert(c1, n)
if s2 < 0:
    s2 = -s2
    c2 = gmpy2.invert(c2, n)

# 计算明文
m = (pow(c1, s1, n) * pow(c2, s2, n)) % n

# 将数字转换为可读文本
flag = libnum.n2s(int(m)).decode()
print("Flag:", flag)

4. 代码逐行解析与常见问题

让我们深入理解脚本中的每个关键部分：

4.1 gmpy2.gcdext函数

gcdext(e1, e2) 执行扩展欧几里得算法，返回三个值：

• gcd: e1和e2的最大公约数
• s1, s2: 满足e1 s1 + e2 s2 = gcd的系数

在我们的例子中，因为e1和e2互质，gcd=1，所以有e1 s1 + e2 s2 = 1。

4.2 负指数的处理

当s1或s2为负数时，我们需要计算对应密文的模逆元：

if s1 < 0:
    s1 = -s1
    c1 = gmpy2.invert(c1, n)

这是因为c1^s1 mod n当s1为负时等于(c1^-1)^|s1| mod n。

4.3 大数运算优化

我们使用Python的pow函数的三参数形式 pow(a,b,c) 来计算a^b mod c，这比先计算a^b再取模要高效得多，特别是对于CTF中常见的大数运算。

4.4 常见错误与调试

在实际操作中，你可能会遇到以下问题：

1. 环境配置问题 ：

   • 确保安装了gmpy2和libnum库：

     pip install gmpy2 libnum
     

   • 如果安装失败，可能需要先安装依赖：

     sudo apt-get install libgmp-dev libmpfr-dev libmpc-dev
     

2. 数据类型问题 ：

   • gmpy2处理的是mpz类型大整数，有时需要显式转换
   • libnum.n2s需要传入Python的int类型

3. 错误的结果 ：

   • 检查n、e、c是否复制正确
   • 确认s1和s2的符号处理是否正确
   • 验证gcd(e1,e2)确实等于1

5. 扩展知识与防御措施

理解了共模攻击后，我们应该思考如何在实际应用中避免这类漏洞：

5.1 RSA最佳实践

安全实践	说明
不重复使用模数n	每个用户/每次加密应生成独立的n
使用足够大的密钥	现代推荐至少2048位
选择合适的填充方案	如OAEP而非PKCS#1 v1.5
定期更换密钥	降低密钥泄露风险

5.2 其他相关攻击

共模攻击只是RSA众多攻击方式之一，CTF中常见的其他攻击包括：

• 小指数攻击 ：当e很小时（如e=3），可能直接开e次方
• 因数分解攻击 ：当n可以被分解时（如Pollard's p-1算法）
• 侧信道攻击 ：通过时间、功耗等物理信息泄露密钥
• 选择密文攻击 ：利用解密预言机恢复密钥

5.3 CTF中的变种题目

在实际CTF比赛中，出题者可能会对基础题目进行各种变形：

1. 隐藏的共模 ：可能需要从流量数据或内存dump中提取n和e
2. 多组共模 ：提供多组(n,e,c)组合，需要识别哪几组共用相同的n
3. 组合攻击 ：共模攻击与其他攻击方式结合，如先需要分解n

6. 实战演练与技巧提升

为了真正掌握这一技术，我建议你：

1. 在BUUCTF上找到这道题实际尝试
2. 修改脚本中的参数，观察不同情况下的结果
3. 尝试用纯数学方法（如手算小数字例子）理解过程
4. 查阅更多关于RSA和数论的资料

注意：在实际CTF比赛中，flag的格式可能有特定要求（如加上特定前缀），提交时要注意题目说明。

最后，记住密码学攻防的核心在于深入理解原理而非死记硬背脚本。当你真正理解了共模攻击背后的数学之美，就能在面对各种变种题目时游刃有余。