1. 从一道CTF题看RSA的实战攻防最近在复盘一些经典的CTFCapture The Flag题目特别是密码学方向的发现很多朋友对RSA的理解还停留在“公钥加密、私钥解密”的公式层面一旦题目稍微变个花样比如给一些特殊的参数或者残缺的信息就不知道从何下手了。正好借着复盘“[RoarCTF 2019]RSA”这道题的机会我想和大家深入聊聊RSA在CTF赛题中常见的“非标准”考法以及背后对应的那些真实的密码学原理和攻击手段。这道题本身不算最难的但它非常典型地融合了多个知识点像是一份精致的“考点拼盘”非常适合用来检验和巩固我们对RSA的整体理解。无论你是正在备战CTF的新手还是想更深入了解RSA实际应用与潜在脆弱性的开发者相信接下来的内容都能给你带来一些实实在在的收获。我们会从最基础的RSA原理快速回顾开始然后一步步拆解这道题可能涉及的攻击路径最后分享一些我在实战中调试和解题的通用技巧。2. RSA核心原理与CTF常见变形快速回顾在深入题目之前我们必须确保站在同一条起跑线上。RSA的安全性基于大数分解的困难性这个大家应该都清楚。它的算法步骤教科书上都有我这里用最直白的语言再捋一遍并重点强调那些容易被忽略、却在CTF里经常成为突破口的细节。2.1 算法流程与关键参数首先密钥生成随机选择两个大质数p和q。计算模数n p * q。这个n是公开的也是RSA安全的基石因为从n倒推p和q在计算上不可行。计算欧拉函数φ(n) (p-1)*(q-1)。这个值必须保密。选择一个整数e满足1 e φ(n)且e与φ(n)互质最大公约数为1。e通常是655370x10001因为它在安全性和计算效率之间取得了很好的平衡。计算e对于φ(n)的模逆元d即满足e * d ≡ 1 (mod φ(n))的d。d就是私钥的核心部分。至此我们得到了公钥(n, e)和私钥(n, d)。加密过程很简单对于明文m需要先转换为小于n的整数计算密文c ≡ m^e (mod n)。解密则是计算m ≡ c^d (mod n)。注意这里有一个至关重要的细节m必须小于n。如果m大于或等于n就需要先进行分组。但在CTF题中为了简化明文往往就是一个可以直接转换的数字或短字符串。2.2 CTF中RSA的常见“考点”分类CTF出题人不会老老实实地给你完整的(n, e, c)让你去分解n那在现在的计算机能力下对正常大小的n几乎不可能。他们会想方设法地“挖坑”或者“给提示”把问题转化为其他可解的数学问题。常见的考点可以归纳为以下几类模数n相关攻击直接分解当n很小比如小于512比特或者本身有缺陷如由两个非常接近的质数生成时可以用工具如yafu、factordb网站直接分解。模数共享共模攻击同样的明文m用相同的n但不同的e加密得到多个密文c1, c2。如果这两个e互质就可以利用扩展欧几里得算法恢复明文。素数重用多个n之间使用了相同的质数p或q那么计算它们的最大公约数GCD就能直接分解这些n。指数e相关攻击小公钥指数攻击如e3如果e很小比如3并且明文m也很小使得m^e n那么加密实际上没有取模直接对密文c开e次方根就能得到m。小私钥指数攻击Wiener攻击如果私钥d相对于n来说太小可以通过连分数展开的方法在多项式时间内破解。填充或格式相关攻击基于填充预言Padding Oracle的攻击这更多出现在实际应用协议如PKCS#1 v1.5中CTF题也可能模拟。通过服务器对密文解密后填充格式正确与否的反馈可以逐步推算出明文。明文相关攻击如果知道明文的某些部分或格式比如以“flag{”开头可以结合Coppersmith等算法进行攻击。侧信道与错误注入这类题目可能给出一些非标准的参数比如错误的φ(n)或者加密、解密过程中产生的错误结果要求你利用这些信息反推密钥。“[RoarCTF 2019]RSA”这道题从名称和常见考法来看很可能不是单一考点的题目而是需要你像侦探一样根据题目给出的“线索”可能是多个文件、一段交互脚本的输出等识别出它属于上述哪种或哪几种情况的组合然后选择正确的工具链进行破解。3. 解题环境准备与通用工具链在具体分析题目之前搭建一个顺手的解题环境至关重要。密码学题目尤其是RSA高度依赖数学计算和脚本编写。下面是我个人多年实战总结下来的一套高效工具组合。3.1 核心编程语言与库Python 3是绝对的主力。因为它有极其强大的第三方库支持。gmpy2 / pycryptodome这是我们的“重型武器库”。gmpy2提供了高精度的大整数运算能力速度远超Python原生整数类型在计算模逆、大数幂模运算时必不可少。pycryptodome则是一个全面的密码学库不仅实现了RSA还包含AES、DES等多种算法以及一些常用的攻击脚本工具函数。# 安装命令 pip install gmpy2 pycryptodomesympy一个符号计算库在解方程、求模逆、进行一些代数推导时非常有用。pip install sympyrequests如果题目是网络交互型的给你一个IP和端口这个库用于自动化通信。pip install requests3.2 专用分解与计算工具有些计算不适合用通用脚本有现成的轮子会快很多。yafu一个强大的整数分解工具尤其擅长自动选择算法如Pollard-rho、ECM来分解中等大小的n。在CTF中如果n在256-1024比特之间yafu往往是第一选择。你需要将其下载到本地并配置好环境变量。factordb.com一个在线的因子分解数据库。对于常见的、或者之前有人分解过的n直接提交上去可能瞬间就得到结果。这是你的“第一道搜索引擎”。RsaCtfTool一个用Python编写的、集成了几乎所有常见RSA攻击方法的“瑞士军刀”。你只需要把题目给的参数n, e, c, p, q, d等有什么给什么以一定格式输入它就能自动尝试各种攻击方法。对于不熟悉具体攻击算法实现的同学来说这是一个非常好的学习和验证工具。可以从GitHub上克隆它的仓库。3.3 解题思路框架拿到一个RSA题目我通常会遵循以下步骤形成一个排查清单信息收集仔细阅读题目描述和所有附件。提取出所有给出的数字n,e,c可能还有p,q,d,dp,dq,invq, 或者多个n、多个e、多个c。把它们整理好。初步检查检查n的长度比特数。太小如256则尝试直接分解factordb或yafu。检查e的值。常见的有65537、3等。如果是3警惕小公钥指数攻击。检查是否有多个n。尝试计算每两个n之间的gcd(n1, n2)看是否有非1的公约数素数重用。检查是否有多个e对应同一个n和多个c。警惕共模攻击。尝试已知攻击根据初步检查的结果套用对应的攻击方法。例如共模攻击、小公钥指数、Wiener攻击等。深入分析如果常规攻击都无效可能需要更仔细地审视参数之间的关系。比如题目给的d是否是真的私钥φ(n)是否正确是否使用了非标准的素数生成方法这时可能需要一些数学推导或者利用Coppersmith定理等更高级的工具。解密与格式化一旦恢复出私钥参数或直接计算出明文整数m需要将其转换为字节字符串。注意m可能是大端序或小端序的字节转换后可能还需要进一步解码如ASCII、UTF-8才能得到可读的flag。实操心得一定要养成好习惯把题目给出的所有数字单独保存到一个文本文件或脚本的变量里。经常有同学因为看错一个数字或者复制漏了一位导致算了半天都是错的。另外对于得到的明文整数m不要只用hex(m)看一定要用long_to_bytes(m)这样的函数转换因为flag可能藏在字节流的中间位置。4. 针对“[RoarCTF 2019]RSA”的模拟推演与攻击路径解析由于我无法获取到该题目的原始附件我将基于“RoarCTF”赛事的风格和RSA常见考点模拟构建一道可能符合“[RoarCTF 2019]RSA”难度的题目并详细演示完整的攻击路径。这比直接给答案更有价值因为它展示的是解题的思考过程。4.1 模拟题目场景设定假设我们拿到的是一个压缩包解压后包含以下文件public.pem: 一个PEM格式的公钥文件。flag.enc: 一个二进制文件是使用上述公钥加密后的密文。hint.txt: 一个文本文件内容如下“Sometimes the key is not generated in a standard way. Maybe you should check the source code of the key generation.”这很常见公钥和密文是标准配置hint则指向密钥生成过程可能有问题。4.2 第一步信息提取与初步观察首先我们从PEM文件中提取n和e。from Crypto.PublicKey import RSA with open(public.pem, r) as f: pub_key RSA.import_key(f.read()) n pub_key.n e pub_key.e print(fn {n}) print(fe {e}) print(fn的比特长度: {n.bit_length()})假设输出如下n 12345678901234567890123456789012345678901234567890123456789012345678901234567 e 65537 n的比特长度: 256n只有256比特这在现代密码学标准中是非常不安全的但在CTF中很常见意味着很可能可以直接分解。同时e是标准的65537。接着读取密文文件它通常就是密文整数c的字节表示。with open(flag.enc, rb) as f: c_bytes f.read() # 将字节转换为整数注意是大端序 c int.from_bytes(c_bytes, big) print(fc {c})4.3 第二步尝试直接分解n对于256比特的n我们首先求助在线数据库。访问 factordb.com。将n的十进制值粘贴进去查询。 如果运气好数据库里已经有它的因子我们会直接得到p和q。如果factordb没有结果我们就使用yafu。 在命令行中进入yafu目录执行./yafu “factor(12345678901234567890123456789012345678901234567890123456789012345678901234567)”或者将n保存到文件num.txt中然后执行./yafu “factor()” -batchfile num.txt。假设我们通过yafu成功分解得到p 1234567890123456789012345678901234567890123456789012345678901237 q 1000000000000000000000000000000000000000000000000000000000000001但这里请注意hint“密钥生成过程非标准”。如果我们直接使用这对p, q去计算φ(n) (p-1)*(q-1)然后求私钥d inverse(e, φ(n))最后解密m pow(c, d, n)很可能得到的是一堆乱码。这说明我们的思路可能太简单了或者这对因子并不是真正的p和q。4.4 第三步深入分析hint与密钥生成hint提示要检查密钥生成源码。在CTF中这通常意味着出题人修改了标准的RSA密钥生成算法。一个非常常见的修改点是用于计算φ(n)的并不是(p-1)*(q-1)而是别的值。在标准RSA中φ(n)是欧拉函数。但有一个相关的概念叫卡迈克尔函数λ(n) lcm(p-1, q-1)。在RSA的实际应用中如PKCS#1标准私钥d通常是基于λ(n)计算的即满足e * d ≡ 1 (mod λ(n))。因为λ(n)是φ(n)的一个约数所以这样计算出的d可能更小但同样能用于解密。然而出题人可能玩得更“花”。一种经典的变形是“变种RSA”或“错误使用φ(n)”的RSA。例如错误地使用了φ(n) (p-1)*(q)或(p)*(q-1)。使用了φ(n) (p1)*(q1)。甚至使用了完全随机的一个与φ(n)近似的大数。我们的任务变成了已知n,e,c以及可能错误的φ(n)与φ(n)之间的关系来推导出正确的解密指数d。但在这个模拟场景中我们只有n, e, c。hint让我们看生成源码但源码没直接给。这通常意味着我们需要从n本身或者附加信息中推断出生成方式。一个合理的推测既然n能被轻易分解且hint指向生成过程那么很可能p和q不是随机的质数而是有特殊结构的数使得φ(n)很容易计算或者与某个简单函数相关。例如p和q可能是安全素数Sophie Germain素数相关的形式或者p-1和q-1非常光滑有很多小因子这会导致n容易通过Pollard‘s p-1算法分解。但我们的n已经分解了。让我们重新审视分解得到的p和q。把它们减1看看p-1 1234567890123456789012345678901234567890123456789012345678901236 q-1 1000000000000000000000000000000000000000000000000000000000000000q-1是一个非常光滑的数全是因子2和5。这强烈提示密钥生成时可能使用了“光滑数”来构造p和q。一个著名的攻击是Pollard‘s p-1 算法它能在p-1或q-1的质因子都很小时高效分解n。但这里我们已经分解了。关键在于如果出题人故意使用了光滑的p-1那么他可能并没有使用φ(n) (p-1)*(q-1)来计算d。为什么因为如果使用标准的φ(n)那么由于p-1光滑φ(n)也会很光滑这会导致私钥d可能很小从而容易遭受Wiener攻击或Boneh-Durfee攻击。但我们的e是标准的65537通常对应一个很大的d。这里存在矛盾。另一种可能性也许题目给的n和e只是幌子真正的考点隐藏在flag.enc文件本身或者需要结合其他信息。但根据题目名“[RoarCTF 2019]RSA”它很可能就是一个纯粹的RSA题目。鉴于我们是在模拟我假设一个更典型的、符合2019年CTF难度的考点已知私钥部分参数泄露。这在CTF中非常常见比如给出n, e, c, dp其中dp d mod (p-1)。4.5 模拟攻击路径已知dp泄露让我们修改一下模拟场景。假设我们从题目中额外得到了一个参数dp也许藏在源代码注释里或者另一个文件中。已知n,e65537,c,dp其中dp d mod (p-1)。攻击原理如下 由定义d * e ≡ 1 (mod φ(n))所以d * e ≡ 1 (mod (p-1))。 因此dp * e ≡ 1 (mod (p-1))即dp * e - 1 k * (p-1)其中k是一个整数。因为dp p-1所以k (dp * e -1) / (p-1)应该是一个不大的整数。我们可以通过枚举k来求解p。具体步骤枚举k从1开始。计算p_candidate (dp * e - 1) // k 1。检查p_candidate是否大于1且能整除n。如果能则找到了p。找到p后q n // p。计算φ(n) (p-1)*(q-1)和d inverse(e, φ(n))。解密m pow(c, d, n)。Python实现如下from Crypto.Util.number import inverse, long_to_bytes import gmpy2 n ... # 你的n e 65537 c ... # 你的c dp ... # 你的dp for k in range(1, e): # k的范围通常不大可以从1到e-1枚举 if (dp * e - 1) % k 0: p_candidate (dp * e - 1) // k 1 if p_candidate 1 and n % p_candidate 0: p p_candidate q n // p print(fFound p: {p}) print(fFound q: {q}) phi (p-1) * (q-1) d inverse(e, phi) m pow(c, d, n) print(fDecrypted message: {long_to_bytes(m)}) break这种攻击非常高效几乎瞬间就能完成。这很可能是“[RoarCTF 2019]RSA”这类题目的一种考法。5. 进阶攻击场景与Coppersmith方法简介如果题目再难一点可能涉及Coppersmith定理的应用。这个定理是RSA相关攻击中的一把“神器”它允许我们在模数n的某个因子如p或q已知部分比特时恢复出完整的因子。5.1 场景模拟已知p的高位或低位假设题目没有直接给出dp而是给出了p的大部分高位比特例如通过某种侧信道或错误信息泄露。比如我们知道p是一个512比特的数并且给出了它最高的450比特。设完整的p p_high x其中p_high是已知的高位部分左移对齐后x是未知的低位部分且x相对较小比特数少。我们知道p是n的因子所以n ≡ 0 (mod p)。我们可以构造多项式f(x) p_high x在模n下的根x0满足f(x0) ≡ 0 (mod p)。由于p是n的一个因子这等价于在模p下求解。Coppersmith定理告诉我们如果未知部分x足够小小于p的约β^2次方β是p相对于n的大小这里约为0.5我们就可以在多项式时间内找到它。在Python中我们可以使用sage环境一个基于Python的数学计算系统来轻松实现Coppersmith攻击。如果本地没有安装sage可以使用在线Sage计算器或者用Python的sympy库进行有限度的计算但sympy的Coppersmith实现可能不完整。以下是SageMath的示例代码框架# 假设在SageMath环境中运行 n ... # 已知的n p_high ... # 已知的p的高位部分需要左移到正确的位置 # 例如如果p是512比特已知高450比特那么 # p_high known_high_bits (512 - 450) PR.x PolynomialRing(Zmod(n)) f p_high x # 需要设定根的边界即x的最大可能值。如果未知低位有62比特则边界是 2^62 roots f.small_roots(X2^62, beta0.5) # beta是p/n的近似下界通常取0.5 if roots: x0 roots[0] p p_high int(x0) if n % p 0: print(fFound p: {p}) q n // p # ... 后续计算私钥和解密这种攻击在CTF中越来越常见因为它需要选手对RSA的数学结构有更深的理解并且能够运用现成的数学工具。5.2 场景模拟基于明文的攻击另一种Coppersmith的经典应用是当明文m具有某种特殊形式时。例如如果知道flag的格式是flag{...}我们可以将未知部分设为变量构造多项式。假设我们知道m的开头是b‘flag{’对应的整数是M_high末尾是b‘}’中间是未知字符串。我们可以将m表示为m M_high * 2^k x * 256 M_low其中x是中间未知部分对应的整数k是未知部分的比特位移量。加密方程为c ≡ (M_high * 2^k x * 256 M_low)^e (mod n)。这构成了一个关于x的高次模方程。同样如果未知部分x足够小Coppersmith方法可能可以求解。不过这种攻击对未知部分的大小限制更严格实现起来也更复杂通常出现在更高难度的赛题中。6. 实战调试与问题排查技巧即便知道了原理和算法在实战解题时还是会遇到各种“坑”。下面分享几个我踩过的坑和总结的技巧。6.1 数据格式处理这是最常见的问题来源。PEM文件读取确保使用正确的库如Crypto.PublicKey.RSA.import_key。有时文件可能包含多余的空格或换行。密文读取密文文件可能是纯二进制rb模式读取也可能是十六进制或Base64编码的文本。一定要先用file命令或文本编辑器查看一下文件头或者尝试用不同方式解码。常见的顺序是Base64解码 - 得到二进制数据 - 转换为整数。整数与字节转换Python的int.from_bytes()和long_to_bytes()要特别注意字节序‘big’ 或 ‘little’。CTF中绝大多数情况使用大端序‘big’。转换后得到的字节串可能需要尝试.decode(‘utf-8’)、‘ascii’或‘latin-1’来解码为字符串。6.2 解密结果验证解密得到整数m后不要只看hex(m)的输出。直接print(long_to_bytes(m))。如果输出是乱码尝试long_to_bytes(m)[::-1]反转字节序。尝试将m转换为十六进制字符串后看其中是否包含可读的ASCII段如666c6167对应 ‘flag’。检查你的私钥d计算是否正确。重新计算φ(n)并验证e * d % φ(n) 1。最根本的检查你的p和q是否正确。验证p * q n且p和q都是质数可以用gmpy2.is_prime进行概率性检测。6.3 工具使用注意事项yafu对于较大的nyafu可能需要很长时间。可以尝试在命令中指定算法如‘factor(n) -methodp-1’先尝试Pollard‘s p-1。记得在安静的环境下运行它需要大量计算资源。RsaCtfTool这是一个很好的起点。使用./RsaCtfTool.py –publickey public.pem –uncipherfile flag.enc可以自动尝试多种攻击。但不要完全依赖它理解它背后尝试的攻击原理更重要。在线分解网站factordb.com 是最常用的。但对于比赛中的新鲜题目大概率没有结果。此外要注意不要将比赛中还未公开的、其他题目的n提交到公共网站这可能有违比赛规则。6.4 思维误区避免不是所有RSA题都需要分解n这是最大的误区。共模攻击、小指数攻击、已知部分密钥攻击等都不需要分解n。hint是重要的像我们模拟题中的hint直接指引了方向。一定要仔细分析每一句提示。多参数综合审视当题目给出多个n,e,c,d,dp,dq等参数时要思考它们之间的组合可能对应哪种攻击模式。例如给dp和dq通常用于中国剩余定理CRT加速解密但如果只给其中一个可能就是dp泄露攻击。编码与加密是两回事Flag可能先经过某种编码如Base64、hex再加密所以解密后可能需要进一步解码。回过头看“[RoarCTF 2019]RSA”它可能考察的就是上述某一种或几种技巧的组合。真正的赛题可能需要你在分析文件、提取参数、识别漏洞类型上花费更多功夫。但万变不离其宗扎实理解RSA的数学原理熟悉常见攻击方法的条件和流程配备好顺手的工具链你就能应对绝大多数CTF中的RSA挑战。密码学解题就像解谜享受一步步推导并最终“捕获旗帜”的过程本身就是最大的乐趣所在。 从CTF实战看RSA非标准攻击：原理、工具链与解题思路
1. 从一道CTF题看RSA的实战攻防最近在复盘一些经典的CTFCapture The Flag题目特别是密码学方向的发现很多朋友对RSA的理解还停留在“公钥加密、私钥解密”的公式层面一旦题目稍微变个花样比如给一些特殊的参数或者残缺的信息就不知道从何下手了。正好借着复盘“[RoarCTF 2019]RSA”这道题的机会我想和大家深入聊聊RSA在CTF赛题中常见的“非标准”考法以及背后对应的那些真实的密码学原理和攻击手段。这道题本身不算最难的但它非常典型地融合了多个知识点像是一份精致的“考点拼盘”非常适合用来检验和巩固我们对RSA的整体理解。无论你是正在备战CTF的新手还是想更深入了解RSA实际应用与潜在脆弱性的开发者相信接下来的内容都能给你带来一些实实在在的收获。我们会从最基础的RSA原理快速回顾开始然后一步步拆解这道题可能涉及的攻击路径最后分享一些我在实战中调试和解题的通用技巧。2. RSA核心原理与CTF常见变形快速回顾在深入题目之前我们必须确保站在同一条起跑线上。RSA的安全性基于大数分解的困难性这个大家应该都清楚。它的算法步骤教科书上都有我这里用最直白的语言再捋一遍并重点强调那些容易被忽略、却在CTF里经常成为突破口的细节。2.1 算法流程与关键参数首先密钥生成随机选择两个大质数p和q。计算模数n p * q。这个n是公开的也是RSA安全的基石因为从n倒推p和q在计算上不可行。计算欧拉函数φ(n) (p-1)*(q-1)。这个值必须保密。选择一个整数e满足1 e φ(n)且e与φ(n)互质最大公约数为1。e通常是655370x10001因为它在安全性和计算效率之间取得了很好的平衡。计算e对于φ(n)的模逆元d即满足e * d ≡ 1 (mod φ(n))的d。d就是私钥的核心部分。至此我们得到了公钥(n, e)和私钥(n, d)。加密过程很简单对于明文m需要先转换为小于n的整数计算密文c ≡ m^e (mod n)。解密则是计算m ≡ c^d (mod n)。注意这里有一个至关重要的细节m必须小于n。如果m大于或等于n就需要先进行分组。但在CTF题中为了简化明文往往就是一个可以直接转换的数字或短字符串。2.2 CTF中RSA的常见“考点”分类CTF出题人不会老老实实地给你完整的(n, e, c)让你去分解n那在现在的计算机能力下对正常大小的n几乎不可能。他们会想方设法地“挖坑”或者“给提示”把问题转化为其他可解的数学问题。常见的考点可以归纳为以下几类模数n相关攻击直接分解当n很小比如小于512比特或者本身有缺陷如由两个非常接近的质数生成时可以用工具如yafu、factordb网站直接分解。模数共享共模攻击同样的明文m用相同的n但不同的e加密得到多个密文c1, c2。如果这两个e互质就可以利用扩展欧几里得算法恢复明文。素数重用多个n之间使用了相同的质数p或q那么计算它们的最大公约数GCD就能直接分解这些n。指数e相关攻击小公钥指数攻击如e3如果e很小比如3并且明文m也很小使得m^e n那么加密实际上没有取模直接对密文c开e次方根就能得到m。小私钥指数攻击Wiener攻击如果私钥d相对于n来说太小可以通过连分数展开的方法在多项式时间内破解。填充或格式相关攻击基于填充预言Padding Oracle的攻击这更多出现在实际应用协议如PKCS#1 v1.5中CTF题也可能模拟。通过服务器对密文解密后填充格式正确与否的反馈可以逐步推算出明文。明文相关攻击如果知道明文的某些部分或格式比如以“flag{”开头可以结合Coppersmith等算法进行攻击。侧信道与错误注入这类题目可能给出一些非标准的参数比如错误的φ(n)或者加密、解密过程中产生的错误结果要求你利用这些信息反推密钥。“[RoarCTF 2019]RSA”这道题从名称和常见考法来看很可能不是单一考点的题目而是需要你像侦探一样根据题目给出的“线索”可能是多个文件、一段交互脚本的输出等识别出它属于上述哪种或哪几种情况的组合然后选择正确的工具链进行破解。3. 解题环境准备与通用工具链在具体分析题目之前搭建一个顺手的解题环境至关重要。密码学题目尤其是RSA高度依赖数学计算和脚本编写。下面是我个人多年实战总结下来的一套高效工具组合。3.1 核心编程语言与库Python 3是绝对的主力。因为它有极其强大的第三方库支持。gmpy2 / pycryptodome这是我们的“重型武器库”。gmpy2提供了高精度的大整数运算能力速度远超Python原生整数类型在计算模逆、大数幂模运算时必不可少。pycryptodome则是一个全面的密码学库不仅实现了RSA还包含AES、DES等多种算法以及一些常用的攻击脚本工具函数。# 安装命令 pip install gmpy2 pycryptodomesympy一个符号计算库在解方程、求模逆、进行一些代数推导时非常有用。pip install sympyrequests如果题目是网络交互型的给你一个IP和端口这个库用于自动化通信。pip install requests3.2 专用分解与计算工具有些计算不适合用通用脚本有现成的轮子会快很多。yafu一个强大的整数分解工具尤其擅长自动选择算法如Pollard-rho、ECM来分解中等大小的n。在CTF中如果n在256-1024比特之间yafu往往是第一选择。你需要将其下载到本地并配置好环境变量。factordb.com一个在线的因子分解数据库。对于常见的、或者之前有人分解过的n直接提交上去可能瞬间就得到结果。这是你的“第一道搜索引擎”。RsaCtfTool一个用Python编写的、集成了几乎所有常见RSA攻击方法的“瑞士军刀”。你只需要把题目给的参数n, e, c, p, q, d等有什么给什么以一定格式输入它就能自动尝试各种攻击方法。对于不熟悉具体攻击算法实现的同学来说这是一个非常好的学习和验证工具。可以从GitHub上克隆它的仓库。3.3 解题思路框架拿到一个RSA题目我通常会遵循以下步骤形成一个排查清单信息收集仔细阅读题目描述和所有附件。提取出所有给出的数字n,e,c可能还有p,q,d,dp,dq,invq, 或者多个n、多个e、多个c。把它们整理好。初步检查检查n的长度比特数。太小如256则尝试直接分解factordb或yafu。检查e的值。常见的有65537、3等。如果是3警惕小公钥指数攻击。检查是否有多个n。尝试计算每两个n之间的gcd(n1, n2)看是否有非1的公约数素数重用。检查是否有多个e对应同一个n和多个c。警惕共模攻击。尝试已知攻击根据初步检查的结果套用对应的攻击方法。例如共模攻击、小公钥指数、Wiener攻击等。深入分析如果常规攻击都无效可能需要更仔细地审视参数之间的关系。比如题目给的d是否是真的私钥φ(n)是否正确是否使用了非标准的素数生成方法这时可能需要一些数学推导或者利用Coppersmith定理等更高级的工具。解密与格式化一旦恢复出私钥参数或直接计算出明文整数m需要将其转换为字节字符串。注意m可能是大端序或小端序的字节转换后可能还需要进一步解码如ASCII、UTF-8才能得到可读的flag。实操心得一定要养成好习惯把题目给出的所有数字单独保存到一个文本文件或脚本的变量里。经常有同学因为看错一个数字或者复制漏了一位导致算了半天都是错的。另外对于得到的明文整数m不要只用hex(m)看一定要用long_to_bytes(m)这样的函数转换因为flag可能藏在字节流的中间位置。4. 针对“[RoarCTF 2019]RSA”的模拟推演与攻击路径解析由于我无法获取到该题目的原始附件我将基于“RoarCTF”赛事的风格和RSA常见考点模拟构建一道可能符合“[RoarCTF 2019]RSA”难度的题目并详细演示完整的攻击路径。这比直接给答案更有价值因为它展示的是解题的思考过程。4.1 模拟题目场景设定假设我们拿到的是一个压缩包解压后包含以下文件public.pem: 一个PEM格式的公钥文件。flag.enc: 一个二进制文件是使用上述公钥加密后的密文。hint.txt: 一个文本文件内容如下“Sometimes the key is not generated in a standard way. Maybe you should check the source code of the key generation.”这很常见公钥和密文是标准配置hint则指向密钥生成过程可能有问题。4.2 第一步信息提取与初步观察首先我们从PEM文件中提取n和e。from Crypto.PublicKey import RSA with open(public.pem, r) as f: pub_key RSA.import_key(f.read()) n pub_key.n e pub_key.e print(fn {n}) print(fe {e}) print(fn的比特长度: {n.bit_length()})假设输出如下n 12345678901234567890123456789012345678901234567890123456789012345678901234567 e 65537 n的比特长度: 256n只有256比特这在现代密码学标准中是非常不安全的但在CTF中很常见意味着很可能可以直接分解。同时e是标准的65537。接着读取密文文件它通常就是密文整数c的字节表示。with open(flag.enc, rb) as f: c_bytes f.read() # 将字节转换为整数注意是大端序 c int.from_bytes(c_bytes, big) print(fc {c})4.3 第二步尝试直接分解n对于256比特的n我们首先求助在线数据库。访问 factordb.com。将n的十进制值粘贴进去查询。 如果运气好数据库里已经有它的因子我们会直接得到p和q。如果factordb没有结果我们就使用yafu。 在命令行中进入yafu目录执行./yafu “factor(12345678901234567890123456789012345678901234567890123456789012345678901234567)”或者将n保存到文件num.txt中然后执行./yafu “factor()” -batchfile num.txt。假设我们通过yafu成功分解得到p 1234567890123456789012345678901234567890123456789012345678901237 q 1000000000000000000000000000000000000000000000000000000000000001但这里请注意hint“密钥生成过程非标准”。如果我们直接使用这对p, q去计算φ(n) (p-1)*(q-1)然后求私钥d inverse(e, φ(n))最后解密m pow(c, d, n)很可能得到的是一堆乱码。这说明我们的思路可能太简单了或者这对因子并不是真正的p和q。4.4 第三步深入分析hint与密钥生成hint提示要检查密钥生成源码。在CTF中这通常意味着出题人修改了标准的RSA密钥生成算法。一个非常常见的修改点是用于计算φ(n)的并不是(p-1)*(q-1)而是别的值。在标准RSA中φ(n)是欧拉函数。但有一个相关的概念叫卡迈克尔函数λ(n) lcm(p-1, q-1)。在RSA的实际应用中如PKCS#1标准私钥d通常是基于λ(n)计算的即满足e * d ≡ 1 (mod λ(n))。因为λ(n)是φ(n)的一个约数所以这样计算出的d可能更小但同样能用于解密。然而出题人可能玩得更“花”。一种经典的变形是“变种RSA”或“错误使用φ(n)”的RSA。例如错误地使用了φ(n) (p-1)*(q)或(p)*(q-1)。使用了φ(n) (p1)*(q1)。甚至使用了完全随机的一个与φ(n)近似的大数。我们的任务变成了已知n,e,c以及可能错误的φ(n)与φ(n)之间的关系来推导出正确的解密指数d。但在这个模拟场景中我们只有n, e, c。hint让我们看生成源码但源码没直接给。这通常意味着我们需要从n本身或者附加信息中推断出生成方式。一个合理的推测既然n能被轻易分解且hint指向生成过程那么很可能p和q不是随机的质数而是有特殊结构的数使得φ(n)很容易计算或者与某个简单函数相关。例如p和q可能是安全素数Sophie Germain素数相关的形式或者p-1和q-1非常光滑有很多小因子这会导致n容易通过Pollard‘s p-1算法分解。但我们的n已经分解了。让我们重新审视分解得到的p和q。把它们减1看看p-1 1234567890123456789012345678901234567890123456789012345678901236 q-1 1000000000000000000000000000000000000000000000000000000000000000q-1是一个非常光滑的数全是因子2和5。这强烈提示密钥生成时可能使用了“光滑数”来构造p和q。一个著名的攻击是Pollard‘s p-1 算法它能在p-1或q-1的质因子都很小时高效分解n。但这里我们已经分解了。关键在于如果出题人故意使用了光滑的p-1那么他可能并没有使用φ(n) (p-1)*(q-1)来计算d。为什么因为如果使用标准的φ(n)那么由于p-1光滑φ(n)也会很光滑这会导致私钥d可能很小从而容易遭受Wiener攻击或Boneh-Durfee攻击。但我们的e是标准的65537通常对应一个很大的d。这里存在矛盾。另一种可能性也许题目给的n和e只是幌子真正的考点隐藏在flag.enc文件本身或者需要结合其他信息。但根据题目名“[RoarCTF 2019]RSA”它很可能就是一个纯粹的RSA题目。鉴于我们是在模拟我假设一个更典型的、符合2019年CTF难度的考点已知私钥部分参数泄露。这在CTF中非常常见比如给出n, e, c, dp其中dp d mod (p-1)。4.5 模拟攻击路径已知dp泄露让我们修改一下模拟场景。假设我们从题目中额外得到了一个参数dp也许藏在源代码注释里或者另一个文件中。已知n,e65537,c,dp其中dp d mod (p-1)。攻击原理如下 由定义d * e ≡ 1 (mod φ(n))所以d * e ≡ 1 (mod (p-1))。 因此dp * e ≡ 1 (mod (p-1))即dp * e - 1 k * (p-1)其中k是一个整数。因为dp p-1所以k (dp * e -1) / (p-1)应该是一个不大的整数。我们可以通过枚举k来求解p。具体步骤枚举k从1开始。计算p_candidate (dp * e - 1) // k 1。检查p_candidate是否大于1且能整除n。如果能则找到了p。找到p后q n // p。计算φ(n) (p-1)*(q-1)和d inverse(e, φ(n))。解密m pow(c, d, n)。Python实现如下from Crypto.Util.number import inverse, long_to_bytes import gmpy2 n ... # 你的n e 65537 c ... # 你的c dp ... # 你的dp for k in range(1, e): # k的范围通常不大可以从1到e-1枚举 if (dp * e - 1) % k 0: p_candidate (dp * e - 1) // k 1 if p_candidate 1 and n % p_candidate 0: p p_candidate q n // p print(fFound p: {p}) print(fFound q: {q}) phi (p-1) * (q-1) d inverse(e, phi) m pow(c, d, n) print(fDecrypted message: {long_to_bytes(m)}) break这种攻击非常高效几乎瞬间就能完成。这很可能是“[RoarCTF 2019]RSA”这类题目的一种考法。5. 进阶攻击场景与Coppersmith方法简介如果题目再难一点可能涉及Coppersmith定理的应用。这个定理是RSA相关攻击中的一把“神器”它允许我们在模数n的某个因子如p或q已知部分比特时恢复出完整的因子。5.1 场景模拟已知p的高位或低位假设题目没有直接给出dp而是给出了p的大部分高位比特例如通过某种侧信道或错误信息泄露。比如我们知道p是一个512比特的数并且给出了它最高的450比特。设完整的p p_high x其中p_high是已知的高位部分左移对齐后x是未知的低位部分且x相对较小比特数少。我们知道p是n的因子所以n ≡ 0 (mod p)。我们可以构造多项式f(x) p_high x在模n下的根x0满足f(x0) ≡ 0 (mod p)。由于p是n的一个因子这等价于在模p下求解。Coppersmith定理告诉我们如果未知部分x足够小小于p的约β^2次方β是p相对于n的大小这里约为0.5我们就可以在多项式时间内找到它。在Python中我们可以使用sage环境一个基于Python的数学计算系统来轻松实现Coppersmith攻击。如果本地没有安装sage可以使用在线Sage计算器或者用Python的sympy库进行有限度的计算但sympy的Coppersmith实现可能不完整。以下是SageMath的示例代码框架# 假设在SageMath环境中运行 n ... # 已知的n p_high ... # 已知的p的高位部分需要左移到正确的位置 # 例如如果p是512比特已知高450比特那么 # p_high known_high_bits (512 - 450) PR.x PolynomialRing(Zmod(n)) f p_high x # 需要设定根的边界即x的最大可能值。如果未知低位有62比特则边界是 2^62 roots f.small_roots(X2^62, beta0.5) # beta是p/n的近似下界通常取0.5 if roots: x0 roots[0] p p_high int(x0) if n % p 0: print(fFound p: {p}) q n // p # ... 后续计算私钥和解密这种攻击在CTF中越来越常见因为它需要选手对RSA的数学结构有更深的理解并且能够运用现成的数学工具。5.2 场景模拟基于明文的攻击另一种Coppersmith的经典应用是当明文m具有某种特殊形式时。例如如果知道flag的格式是flag{...}我们可以将未知部分设为变量构造多项式。假设我们知道m的开头是b‘flag{’对应的整数是M_high末尾是b‘}’中间是未知字符串。我们可以将m表示为m M_high * 2^k x * 256 M_low其中x是中间未知部分对应的整数k是未知部分的比特位移量。加密方程为c ≡ (M_high * 2^k x * 256 M_low)^e (mod n)。这构成了一个关于x的高次模方程。同样如果未知部分x足够小Coppersmith方法可能可以求解。不过这种攻击对未知部分的大小限制更严格实现起来也更复杂通常出现在更高难度的赛题中。6. 实战调试与问题排查技巧即便知道了原理和算法在实战解题时还是会遇到各种“坑”。下面分享几个我踩过的坑和总结的技巧。6.1 数据格式处理这是最常见的问题来源。PEM文件读取确保使用正确的库如Crypto.PublicKey.RSA.import_key。有时文件可能包含多余的空格或换行。密文读取密文文件可能是纯二进制rb模式读取也可能是十六进制或Base64编码的文本。一定要先用file命令或文本编辑器查看一下文件头或者尝试用不同方式解码。常见的顺序是Base64解码 - 得到二进制数据 - 转换为整数。整数与字节转换Python的int.from_bytes()和long_to_bytes()要特别注意字节序‘big’ 或 ‘little’。CTF中绝大多数情况使用大端序‘big’。转换后得到的字节串可能需要尝试.decode(‘utf-8’)、‘ascii’或‘latin-1’来解码为字符串。6.2 解密结果验证解密得到整数m后不要只看hex(m)的输出。直接print(long_to_bytes(m))。如果输出是乱码尝试long_to_bytes(m)[::-1]反转字节序。尝试将m转换为十六进制字符串后看其中是否包含可读的ASCII段如666c6167对应 ‘flag’。检查你的私钥d计算是否正确。重新计算φ(n)并验证e * d % φ(n) 1。最根本的检查你的p和q是否正确。验证p * q n且p和q都是质数可以用gmpy2.is_prime进行概率性检测。6.3 工具使用注意事项yafu对于较大的nyafu可能需要很长时间。可以尝试在命令中指定算法如‘factor(n) -methodp-1’先尝试Pollard‘s p-1。记得在安静的环境下运行它需要大量计算资源。RsaCtfTool这是一个很好的起点。使用./RsaCtfTool.py –publickey public.pem –uncipherfile flag.enc可以自动尝试多种攻击。但不要完全依赖它理解它背后尝试的攻击原理更重要。在线分解网站factordb.com 是最常用的。但对于比赛中的新鲜题目大概率没有结果。此外要注意不要将比赛中还未公开的、其他题目的n提交到公共网站这可能有违比赛规则。6.4 思维误区避免不是所有RSA题都需要分解n这是最大的误区。共模攻击、小指数攻击、已知部分密钥攻击等都不需要分解n。hint是重要的像我们模拟题中的hint直接指引了方向。一定要仔细分析每一句提示。多参数综合审视当题目给出多个n,e,c,d,dp,dq等参数时要思考它们之间的组合可能对应哪种攻击模式。例如给dp和dq通常用于中国剩余定理CRT加速解密但如果只给其中一个可能就是dp泄露攻击。编码与加密是两回事Flag可能先经过某种编码如Base64、hex再加密所以解密后可能需要进一步解码。回过头看“[RoarCTF 2019]RSA”它可能考察的就是上述某一种或几种技巧的组合。真正的赛题可能需要你在分析文件、提取参数、识别漏洞类型上花费更多功夫。但万变不离其宗扎实理解RSA的数学原理熟悉常见攻击方法的条件和流程配备好顺手的工具链你就能应对绝大多数CTF中的RSA挑战。密码学解题就像解谜享受一步步推导并最终“捕获旗帜”的过程本身就是最大的乐趣所在。