文章总结： 文档详细解析了一道CTF密码学题目，核心在于通过代码审计发现RSA加密脚本中复用素数q的漏洞，导致两个模数共享公因子。解题过程涵盖公钥提取、音频摩斯电码解码获取密文、利用GCD算法分解模数以及最终解密还原Flag。文章深入剖析了共享因子攻击原理，并结合Python实践代码，强调了密码学实现中代码审计与密钥管理的重要性。
综合评分： 88
文章分类： CTF,代码审计,漏洞分析
不仅仅是RSA – CTF密码学综合题目完整解析
原创
破镜安全
破镜安全
2026年1月11日 08:00
四川
不仅仅是RSA – CTF密码学综合题目完整解析
题目背景
本题是一道综合性的CTF密码学挑战题，题目名称”不仅仅是RSA”揭示了这道题的特点：虽然核心是RSA加密算法，但解题过程涉及多个技术领域的知识。这道题目考察了参赛者对RSA密码学原理的理解、代码审计能力、信号处理技能以及综合运用多种工具的能力。
题目文件清单
题目提供了以下文件：
- RSA.py – 加密脚本源代码
- pubkey1.pem – 第一个RSA公钥文件
- pubkey2.pem – 第二个RSA公钥文件
- C1.wav – 第一个音频文件
- C2.wav – 第二个音频文件
从文件类型可以看出，这道题结合了密码学、逆向分析和信号处理等多个方向。
解题思路概览
解题的整体流程可以分为以下几个阶段：
- 代码审计：分析RSA.py源码，寻找加密实现中的漏洞
- 公钥分析：从PEM文件中提取RSA公钥参数
- 密文获取：从音频文件中解码摩斯电码，获取密文
- 密钥破解：利用发现的漏洞分解RSA模数
- 解密还原：使用破解的密钥解密密文，获取flag
接下来，我们将逐步深入分析每个环节。
第一阶段：代码审计与漏洞发现
RSA.py源码分析
首先，我们来分析题目提供的加密脚本RSA.py：
from flag import flag
from Crypto.Util.number import *
import random
p=getPrime(256)
q=getPrime(256)
e=random.randint(1,65537)
n=p*q
m=bytes_to_long(flag1)
c=pow(m,e,n)
print c,e,n
p=getPrime(256)
n=p*q
m=bytes_to_long(flag2)
c=pow(m,e,n)
print c,e,n
代码执行流程分析
让我们逐行分析这段代码的执行流程：
第一组加密（第1-8行）：
- 生成256位素数p
- 生成256位素数q
- 生成随机公钥指数e（范围1到65537）
- 计算模数n = p * q
- 将flag的第一部分转换为整数m
- 使用RSA加密：c = m^e mod n
- 输出密文c、公钥指数e和模数n
第二组加密（第10-14行）：
- 重新生成256位素数p
- 计算模数n = p * q
- 将flag的第二部分转换为整数m
- 使用RSA加密：c = m^e mod n
- 输出密文c、公钥指数e和模数n
关键漏洞识别
通过仔细对比两组加密代码，我们发现了一个严重的安全漏洞：
在第二组加密中，变量q没有被重新赋值！
具体来说：
- 第一组加密：
p=getPrime(256),q=getPrime(256),n=p*q - 第二组加密：
p=getPrime(256),n=p*q（注意：q没有重新生成）
这意味着：
- 第一个模数：n1 = p1 * q
- 第二个模数：n2 = p2 * q
两个模数共享了同一个素因子q！这是RSA实现中的致命错误。
漏洞利用原理
当两个RSA模数共享一个公因子时，我们可以使用最大公约数（GCD）算法轻松破解：
数学原理：
如果 n1 = p1 * q 且 n2 = p2 * q
那么 gcd(n1, n2) = q
一旦获得q，就可以计算：
p1 = n1 / q
p2 = n2 / q
为什么这个攻击如此有效？
计算两个大整数的最大公约数（使用欧几里得算法）的时间复杂度是O(log n)，这是一个非常快速的算法。而直接分解一个大整数需要指数级时间。因此，共享因子攻击可以在毫秒级完成，而暴力分解可能需要数年甚至数百年。
第二阶段：提取RSA公钥参数
PEM文件格式说明
题目提供的两个公钥文件采用PEM（Privacy Enhanced Mail）格式，这是一种常见的密钥存储格式。PEM文件使用Base64编码，包含在-----BEGIN PUBLIC KEY-----和-----END PUBLIC KEY-----标记之间。
提取公钥参数的方法
我们可以使用Python的PyCrypto或PyCryptodome库来解析PEM格式的公钥文件：
from Crypto.PublicKey import RSA
# 读取第一个公钥
f = open("pubkey1.pem", "r")
key1 = RSA.importKey(f.read())
n1 = key1.n
e1 = key1.e
f.close()
# 读取第二个公钥
f = open("pubkey2.pem", "r")
key2 = RSA.importKey(f.read())
n2 = key2.n
e2 = key2.e
f.close()
提取结果
运行上述代码后，我们得到以下RSA公钥参数：
N1 = 10285341668836655607404515118077620322010982612318568968318582049362470680277495816958090140659605052252686941748392508264340665515203620965012407552377979
E1 = 41221
N2 = 8559553750267902714590519131072264773684562647813990967245740601834411107597211544789303614222336972768348959206728010238189976768204432286391096419456339
E2 = 41221
可以看到，两个公钥使用了相同的加密指数E = 41221，这与我们在源码中看到的逻辑一致（e在两次加密中没有改变）。
第三阶段：从音频文件中获取密文
音频文件分析
题目提供了两个WAV格式的音频文件C1.wav和C2.wav。通过文件名可以推测，这两个文件包含了密文C1和C2。
首先检查音频文件的基本信息：
file C1.wav C2.wav
输出结果：
C1.wav: RIFF (little-endian) data, WAVE audio, Microsoft PCM, 8 bit, mono 8000 Hz
C2.wav: RIFF (little-endian) data, WAVE audio, Microsoft PCM, 8 bit, mono 8000 Hz
这些是标准的8位单声道WAV音频文件，采样率为8000 Hz。
摩斯电码识别
播放音频文件后，可以听到典型的摩斯电码信号：短音”滴”（点）和长音”嗒”（划）。摩斯电码是一种时通时断的信号代码，通过不同的排列顺序来表达字母、数字和标点符号。
摩斯电码基础知识：
- 点（.）：短信号
- 划（-）：长信号，长度约为点的3倍
- 字母之间的间隔为3个点的长度
- 单词之间的间隔为7个点的长度
解码工具选择
可以使用以下工具来解码音频中的摩斯电码：
- Morse Code Reader（在线工具）- 直接上传音频文件自动解码
- Audacity – 可视化波形，手动识别点划
- CW Decoder – 专业的连续波信号解码软件
解码结果
使用Morse Code Reader等工具对两个音频文件进行解码后，得到两个大整数：
C1 = 4314251881242803343641258350847424240197348270934376293792054938860756265727535163218661012756264314717591117355736219880127534927494986120542485721347351
C2 = 485162209351525800948941613977942416744737316759516157292410960531475083863663017229882430859161458909478412418639172249660818299099618143918080867132349
这两个数值就是RSA加密后的密文。
第四阶段：利用共享因子破解RSA
使用GCD算法分解模数
现在我们已经获得了所有必要的信息：
- 两个模数 N1 和 N2
- 公钥指数 E（都是41221）
- 两个密文 C1 和 C2
接下来利用第一阶段发现的漏洞，使用GCD算法来分解模数。
方法一：使用Python的math.gcd()函数
import math
n1 = 10285341668836655607404515118077620322010982612318568968318582049362470680277495816958090140659605052252686941748392508264340665515203620965012407552377979
n2 = 8559553750267902714590519131072264773684562647813990967245740601834411107597211544789303614222336972768348959206728010238189976768204432286391096419456339
# 计算最大公约数
q = math.gcd(n1, n2)
print(f"共享因子 q = {q}")
# 计算另一个因子
p1 = n1 // q
p2 = n2 // q
print(f"p1 = {p1}")
print(f"p2 = {p2}")
运行结果：
共享因子 q = 95652716952085928904432251307911783641637100214166105912784767390061832540987
p1 = 107527961531806336468215094056447603422487078704170855072884726273308088647617
p2 = 89485735722023752007114986095340626130070550475022132484632643785292683293897
方法二：使用FactorDB在线分解
FactorDB（http://www.factordb.com/）是一个大整数分解数据库。对于CTF题目中使用的较小素数（如256位），通常已经被分解并存储在数据库中。
将N1和N2分别提交到FactorDB查询，可以直接获得分解结果：
N1的分解：
p1 = 95652716952085928904432251307911783641637100214166105912784767390061832540987
q1 = 107527961531806336468215094056447603422487078704170855072884726273308088647617
N2的分解：
p2 = 89485735722023752007114986095340626130070550475022132484632643785292683293897
q2 = 95652716952085928904432251307911783641637100214166105912784767390061832540987
验证分解结果
注意到一个关键事实：q2 == p1，这正好验证了我们在代码审计阶段的发现。
验证分解的正确性：
# 验证N1的分解
print(f"p1 * q1 == N1: {p1 * q1 == n1}") # True
# 验证N2的分解
print(f"p2 * q2 == N2: {p2 * q2 == n2}") # True
至此，我们成功获得了两组RSA密钥的所有素因子。
第五阶段：RSA解密与获取Flag
RSA解密数学原理
在获得素因子p和q后，我们可以按照以下步骤进行RSA解密：
- 计算欧拉函数：φ(n) = (p – 1) * (q – 1)
- 计算私钥指数：d = e^(-1) mod φ(n)
- 解密密文：m = c^d mod n
- 转换为明文：将整数m转换为字符串
欧拉函数的意义：
欧拉函数φ(n)表示小于n且与n互质的正整数的个数。当n是两个素数的乘积时，φ(n) = (p-1)(q-1)。这个值在RSA算法中用于计算私钥。
模逆元的计算：
私钥d是e在模φ(n)下的乘法逆元，即满足：e * d ≡ 1 (mod φ(n))
可以使用扩展欧几里得算法或gmpy2库的invert函数来计算。
完整解密脚本
下面是完整的解密脚本：
import gmpy2
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
# 步骤1: 从公钥文件提取参数
f = open("pubkey1.pem", "r")
key = RSA.importKey(f.read())
n1 = key.n
e1 = key.e
f.close()
f = open("pubkey2.pem", "r")
key = RSA.importKey(f.read())
n2 = key.n
e2 = key.e
f.close()
print('N1 =', n1)
print('E1 =', e1)
print('N2 =', n2)
print('E2 =', e2)
# 步骤2: 从FactorDB或GCD获得的分解结果
p1 = 95652716952085928904432251307911783641637100214166105912784767390061832540987
q1 = 107527961531806336468215094056447603422487078704170855072884726273308088647617
p2 = 89485735722023752007114986095340626130070550475022132484632643785292683293897
q2 = 95652716952085928904432251307911783641637100214166105912784767390061832540987
# 步骤3: 从音频文件解码得到的密文
c1 = 4314251881242803343641258350847424240197348270934376293792054938860756265727535163218661012756264314717591117355736219880127534927494986120542485721347351
c2 = 485162209351525800948941613977942416744737316759516157292410960531475083863663017229882430859161458909478412418639172249660818299099618143918080867132349
继续添加解密代码：
# 步骤4: 解密第一部分
phi1 = (p1 - 1) * (q1 - 1)
d1 = gmpy2.invert(e1, phi1)
m1 = gmpy2.powmod(c1, d1, n1)
flag1 = long_to_bytes(int(m1))
print("Flag第一部分:", flag1.decode())
# 步骤5: 解密第二部分
phi2 = (p2 - 1) * (q2 - 1)
d2 = gmpy2.invert(e2, phi2)
m2 = gmpy2.powmod(c2, d2, n2)
flag2 = long_to_bytes(int(m2))
print("Flag第二部分:", flag2.decode())
# 步骤6: 拼接完整flag
print("\n完整Flag:", flag1.decode() + flag2.decode())
运行结果
执行上述脚本后，得到以下输出：
Flag第一部分: UNCTF{ac01dff95336a
Flag第二部分: a470e3b55d3fe43e9f6}
完整Flag: UNCTF{ac01dff95336aa470e3b55d3fe43e9f6}
成功获取完整flag：UNCTF{ac01dff95336aa470e3b55d3fe43e9f6}
技术总结与深度分析
本题涉及的核心技术
通过这道题目，我们综合运用了以下技术：
1. 代码审计能力
- 静态分析Python源码
- 识别变量作用域和生命周期
- 发现编程逻辑错误
2. RSA密码学知识
- RSA加密解密原理
- 欧拉函数的计算
- 模逆元的求解
- 大整数运算
3. 共享因子攻击
- GCD算法的应用
- 时间复杂度分析
- 攻击可行性评估
4. 信号处理技能
- 音频文件格式识别
- 摩斯电码解码
- 数字信号分析
5. 工具使用能力
- Python密码学库（PyCrypto/PyCryptodome）
- gmpy2大整数运算库
- FactorDB在线分解工具
- 摩斯电码解码工具
共享因子攻击的深度剖析
攻击原理：
当两个RSA模数n1和n2共享一个素因子时，攻击者可以通过计算gcd(n1, n2)快速获得这个共享因子。这是因为：
n1 = p1 * q
n2 = p2 * q
gcd(n1, n2) = gcd(p1*q, p2*q) = q * gcd(p1, p2)
由于p1和p2是不同的素数，gcd(p1, p2) = 1，因此gcd(n1, n2) = q。
攻击效率：
欧几里得算法的时间复杂度为O(log n)，对于512位的RSA模数，只需要几毫秒就能完成计算。相比之下，直接分解一个512位的RSA模数需要数天到数周的时间。
历史案例：
2012年，研究人员对互联网上公开的数百万个RSA公钥进行了大规模分析，发现约0.2%的密钥存在共享因子问题。这些脆弱的密钥主要来自：
- 嵌入式设备和路由器
- 随机数生成器实现不当的系统
- 启动时熵池不足的设备
这次研究证明了共享因子攻击不仅是理论威胁，在现实世界中确实存在。
RSA安全实现的最佳实践
基于本题揭示的安全问题，总结以下RSA实现的安全建议：
1. 密钥生成原则
- 每个RSA密钥对必须使用独立生成的素数
- 绝对不要在不同密钥对之间重用素数p或q
- 每次生成新密钥时都应该生成全新的随机素数
2. 素数大小要求
- 现代标准建议使用至少2048位的RSA模数
- 高安全场景应使用3072位或4096位模数
- 本题使用的256位素数在实际应用中完全不安全
3. 随机数生成器
- 必须使用密码学安全的随机数生成器（CSPRNG）
- 不要使用普通的伪随机数生成器（如Python的random模块）
- 确保系统熵池有足够的熵值
4. 公钥指数选择
- 推荐使用65537（0x10001）作为公钥指数
- 避免使用过小的e值（如3），可能导致特定攻击
- 确保e与φ(n)互质
5. 使用成熟的密码学库
- 不要自己实现RSA算法
- 使用经过广泛测试的库（OpenSSL、PyCryptodome、cryptography）
- 这些库已内置各种安全检查和最佳实践
学习建议与资源推荐
给初学者的学习路径
1. 数学基础
- 模运算、素数、最大公约数
- 欧拉函数和费马小定理
- 模逆元的概念和计算
2. RSA算法学习
- RSA的数学原理和证明
- 加密解密的完整流程
- 常见的RSA攻击方法
3. Python密码学编程
- PyCryptodome库的使用
- gmpy2大整数运算
- 数据格式转换技巧
4. CTF实战练习
- 从简单题目开始
- 学习使用常用工具
- 参加在线CTF平台
推荐工具和资源
在线工具：
- FactorDB – 大整数分解数据库
- Morse Code Reader – 摩斯电码解码
- CyberChef – 综合数据处理工具
Python库：
- PyCryptodome – Python密码学库
- gmpy2 – 高性能大整数运算
- cryptography – 现代密码学库
学习资源：
- 《应用密码学》- Bruce Schneier
- 《密码编码学与网络安全》- William Stallings
- Cryptopals Challenges – 密码学挑战平台
全文总结
本文通过对”不仅仅是RSA”这道CTF题目的完整分析，展示了一个综合性密码学挑战的解题全过程。
核心要点回顾
漏洞本质：题目的核心漏洞是RSA加密实现中的素数重用问题。在第二次加密时，变量q没有重新生成，导致两个RSA模数共享了同一个素因子。
攻击方法：利用GCD算法可以在毫秒级时间内从两个共享因子的模数中提取出公因子，从而完全破解RSA加密。
技术综合性：这道题目不仅考察RSA密码学知识，还涉及代码审计、信号处理（摩斯电码）、工具使用等多个方面，充分体现了CTF题目的综合性特点。
安全启示
通过这道题目，我们获得了以下重要启示：
- 实现细节决定安全性即使是数学上安全的算法，如果实现不当，也会导致严重的安全问题。一个看似微小的编程错误（重用变量q），就可能导致整个加密系统的崩溃。
- 代码审计的重要性在密码学应用中，代码审计是发现潜在漏洞的关键手段。需要仔细检查变量的作用域、生命周期和重用情况。
- 密码学知识的实践价值理论知识必须与实践相结合。了解各种攻击方法（如共享因子攻击）可以帮助我们更好地评估系统安全性。
- 多层防御的必要性不应该依赖单一的安全机制。在实际应用中，应该采用多层防御策略，包括密钥管理、访问控制、审计日志等。
- 持续学习的重要性密码学是一个不断发展的领域，新的攻击方法和防御技术层出不穷。保持学习和关注最新研究成果是必要的。
结语
“不仅仅是RSA”这道题目名副其实，它确实不仅仅是一道简单的RSA题目。通过这道题，我们学习了：
- 如何通过代码审计发现安全漏洞
- 共享因子攻击的原理和实现
- 摩斯电码解码等信号处理技能
- Python密码学编程的实践技巧
- RSA安全实现的最佳实践
密码学的魅力在于数学的严谨性和实现的复杂性之间的平衡。一个理论上完美的算法，如果实现不当，就会变得脆弱不堪。这也是为什么在实际应用中，我们应该始终使用经过充分测试和验证的密码学库，而不是自己从零开始实现。
希望这篇文章能够帮助密码学初学者更好地理解RSA算法及其安全性，同时也提醒开发者在实现密码系统时必须格外谨慎，避免类似的安全漏洞。
感谢出题者设计了这道富有教育意义的题目，让我们在实践中深入理解了RSA的安全性问题。
题目信息：
- 题目名称：不仅仅是RSA
- 题目类型：Crypto（密码学）
- 难度评级：中等
- Flag：UNCTF{ac01dff95336aa470e3b55d3fe43e9f6}
涉及知识点：
- RSA加密算法
- 共享因子攻击（Common Factor Attack）
- 代码审计
- 摩斯电码解码
- 大整数分解
- Python密码学编程
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全《不仅仅是RSA – CTF密码学综合题目完整解析》