CTF中RSA小模数分解攻击：原理、工具与实战脚本详解

1. 项目概述当RSA的“门锁”变得脆弱在CTF的密码学Crypto赛题里RSA就像一座经典又常新的堡垒。很多新手入门时会觉得它高深莫测涉及大素数、模运算、欧拉函数光是理解加解密流程就得花不少功夫。但实战中出题人往往不会考察一个完美无缺的RSA实现而是故意在其中埋下一些“瑕疵”。这些瑕疵就是我们的突破口。今天要拆解的“小模数分解攻击”就是其中最常见、也最基础的一种。你可以把它想象成房主装了一把理论上无比坚固的锁但却粗心地把锁做得很小用的材料也很薄。攻击者不需要掌握高深的开锁技巧直接用蛮力就能把锁砸开。所谓“小模数”指的是RSA公钥中的模数n太小。在标准的RSA应用中n是两个大素数的乘积通常长度在2048位甚至4096位以上想要分解它即使用上最先进的算法和超级计算机也需要以年为单位的时间这在计算上是不可行的。然而在CTF赛题中为了降低计算难度、突出攻击逻辑出题人常常会故意使用一个很小的n可能只有256位、512位甚至更小。这时n的分解就从“不可能”变成了“几分钟甚至几秒钟”的事情。这个攻击的核心逻辑极其直接既然RSA的安全性建立在“大整数分解是困难的”这一假设上那么如果n本身不够大这个假设就不成立了。我们拿到公钥对(n, e)和密文c后攻击路径清晰得惊人分解 n - 计算私钥 d - 解密得到明文 m。整个攻击过程更像是一次对RSA底层数学原理的“暴力验证”非常适合作为理解RSA乃至公钥密码学攻击思维的起点。接下来我们就从数学原理到实操脚本完整走一遍这个流程。2. 攻击原理与数学推导为什么分解n就能破解要理解为什么分解n就能破解RSA我们必须回到RSA的密钥生成过程。这里我会省略最基础的加解密公式推导直接切入到与攻击相关的核心数学关系。2.1 RSA密钥生成回顾选择两个大素数p和q。计算模数n p * q。计算欧拉函数φ(n) (p-1)*(q-1)。这个值表示在小于n的正整数中与n互质的数的个数是密钥计算中的关键。选择公钥指数e通常为65537 (0x10001)满足1 e φ(n)且gcd(e, φ(n)) 1即e与φ(n)互质。计算私钥指数d使得d是e模φ(n)的模逆元即满足e * d ≡ 1 (mod φ(n))。公钥是(n, e)私钥是(n, d)。加密过程是c ≡ m^e (mod n)解密过程是m ≡ c^d (mod n)。2.2 攻击的数学支点攻击者的视角里他只知道公开的(n, e)和密文c。而私钥d的计算依赖于φ(n)。关键点在于φ(n)的值直接由p和q决定φ(n)(p-1)(q-1)。因此整个攻击的逻辑链就建立起来了目标计算d。前提需要知道φ(n)。方法通过分解n得到p和q。推导n p * q- 分解得到p, q- 计算φ(n) (p-1)*(q-1)- 计算d ≡ e^(-1) (mod φ(n))。一旦我们算出了d我们就拥有了完整的私钥解密就是一次幂模运算m pow(c, d, n)。注意这里有一个非常重要的细节。计算模逆元d时我们使用的是φ(n)而不是n。这是新手在写脚本时最容易出错的地方之一误写成d gmpy2.invert(e, n)会导致解密失败。务必记住密钥对的核心是e * d ≡ 1 (mod φ(n))。2.3 “小”到什么程度可以被攻击这里的“小”是一个相对概念取决于你拥有的计算资源。对于个人电脑Python sympy/gmpy2分解一个256位约78位十进制数或以下的n通常是秒级。512位约154位十进制数可能需要数秒到数分钟取决于素数的大小和库的效率。在线分解网站如 factordb.com它拥有庞大的已分解数据库和一定的计算能力对于512位甚至768位的n都可能直接查询到结果或快速分解。专业的分解工具如YAFU、Msieve配合多核CPU可以攻击更大的整数但对于CTF赛题通常不会超过1024位。所以在CTF中看到n的长度明显短于2048位就应该第一时间怀疑是小模数攻击。3. 实战工具链与分解操作理论清晰后实战就是选择顺手的工具。下面我按推荐顺序介绍几种主流方法。3.1 利用在线数据库Factordb这是最快捷的第一选择。http://www.factordb.com 是一个神奇的网站它收录了海量整数的分解结果。很多CTF出题人为了省事会直接使用该数据库中已有的n和其对应的p, q。操作方法拿到题目给出的n通常是一个十进制或十六进制大整数。直接将其粘贴到Factordb首页的搜索框。点击查询。结果解读如果状态显示为FFFully Factored并且下面列出了两个因数恭喜你直接复制p和q即可。如果状态是CComposite说明网站知道它是合数但还没分解你可以点击“Factorize”按钮让它尝试分解对于较小的n很可能成功。如果是PPrime那说明题目可能不是小模数攻击或者n本身就是素数这违反了RSA的基本要求可能是其他考点。实操心得优先使用Factordb它能节省大量本地计算时间。复制p和q时注意其格式可能需要转换为整数或十六进制用于后续脚本。对于十六进制的n通常以0x开头可以先在Python里转成十进制再查询或者有些题目直接贴十进制形式。3.2 使用Python本地库分解当在线数据库没有结果时我们就需要本地计算。Python有几个强大的库。方案A使用sympy库适合初学者sympy是一个纯Python的符号计算库它的factorint函数对于小整数分解非常方便。import sympy n 1234567890123456789012345678901234567890 # 你的n factors sympy.factorint(n) print(factors)如果n是两个素数的乘积输出会是类似{p: 1, q: 1}的字典。对于超过100位的nsympy可能会比较慢。方案B使用gmpy2库推荐效率高gmpy2是GMP多精度算术库的Python封装速度极快。它本身不直接提供分解函数但我们可以用其强大的next_prime和试除法或者结合其他方法。更常见的做法是使用gmpy2进行大数运算分解则用专门工具。不过对于“小”n一个简单的试除法脚本也够用import gmpy2 from gmpy2 import mpz, is_prime def factor_small_n(n): n mpz(n) i mpz(2) while i * i n: if n % i 0: p i q n // i if is_prime(p) and is_prime(q): return p, q i gmpy2.next_prime(i) # 跳过偶数加速 return None n mpz(你的n) p, q factor_small_n(n) print(fp {p}\nq {q})注意这个试除法脚本仅适用于真正“小”的n比如100位。对于更大的数需要使用更高效的算法如Pollard‘s rho或者直接调用专业工具。3.3 调用专业分解工具YAFU当n大到本地Python脚本跑不动时就该请出“大杀器”YAFU了。YAFU集成了多种先进的整数分解算法QS、NFS等自动化程度高。基本使用步骤下载YAFU从其项目发布页下载对应系统的可执行文件。准备输入文件创建一个文本文件如n.txt里面只写一行factor(你的n)。例如factor(1234567890123456789012345678901234567890)运行分解在命令行中执行yafu-x64.exe factor() -batchfile n.txtWindows下。YAFU会自动选择算法进行分解。解析输出YAFU会在控制台输出详细的分解过程和最终结果。找到类似Pxxx(素数) 和Cxxx(合数) 的行最终得到p和q。踩坑记录YAFU对输入格式很敏感确保n.txt中没有多余空格或换行。分解时间可能从几分钟到几小时不等取决于n的大小和你的CPU性能。对于CTF赛题通常不会设置需要数小时才能分解的n。可以尝试在命令中指定算法如-siqs指定使用SIQS算法有时更快。4. 从分解结果到明文还原的全流程脚本分解得到p和q只是第一步接下来我们需要完成计算私钥和解密的完整流程。下面给出一个功能完整、容错性强的Python脚本模板并附上详细注释。import gmpy2 from Crypto.Util.number import long_to_bytes # 第一步输入数据 # 通常题目会以十进制或十六进制形式给出 n, e, c # 示例数据请替换为你的实际数据 n 0x7266397b3e7c7d7a7b7c7d7e7f808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9fa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3b4b5b6b7b8b9babbbcbdbebfc0c1c2c3c4c5c6c7c8c9cacbcccdcecfd0d1d2d3d4d5d6d7d8d9dadbdcdddedfe0e1e2e3e4e5e6e7e8e9eaebecedeeeff0f1f2f3f4f5f6f7f8f9fafbfcfdfeff e 65537 c 0x1234567890abcdef1234567890abcdef1234567890abcdef1234567890abcdef # 如果给出的是十进制字符串直接转int # n int(1234567890...) # e int(65537) # c int(1234567890...) # 第二步分解n此处需手动替换p,q # 通过factordb、yafu或脚本分解后将结果填入 p 0xabcdef1234567890abcdef1234567890abcdef1234567890abcdef1234567890 q 0xfedcba0987654321fedcba0987654321fedcba0987654321fedcba0987654321 # 验证分解是否正确 assert gmpy2.is_prime(p) and gmpy2.is_prime(q), p或q不是素数 assert p * q n, p * q 不等于 n分解可能有误 print(f[] 分解成功\n p {p}\n q {q}) # 第三步计算私钥d # 计算欧拉函数 φ(n) phi_n (p - 1) * (q - 1) print(f[] φ(n) {phi_n}) # 计算 e 模 φ(n) 的模逆元即私钥 d # 注意这里是 mod phi_n不是 mod n d gmpy2.invert(e, phi_n) print(f[] 私钥 d {d}) # 验证 ed ≡ 1 mod φ(n) 是否成立 assert (e * d) % phi_n 1, e和d的模逆关系不成立 # 第四步解密得到明文m # 使用私钥 d 进行解密 m c^d mod n # gmpy2.powmod(c, d, n) 比 pow(c, d, n) 效率更高尤其对于大指数d m gmpy2.powmod(c, d, n) print(f[] 解密得到的十进制明文 m {m}) # 第五步将明文转换为可读格式 # RSA加密的明文通常是字节形式需要将长整数转换为字节 try: plaintext long_to_bytes(m) print(f[] 明文字节: {plaintext}) # 尝试以UTF-8解码如果是文本的话 try: flag plaintext.decode(utf-8) print(f[] 明文文本: {flag}) except UnicodeDecodeError: print([!] 明文不是有效的UTF-8文本可能是二进制数据或flag格式。) # 可能是16进制表示的flag hex_str plaintext.hex() print(f[] 明文十六进制: {hex_str}) # 有时flag是 hex 解码后的字符串 try: possible_flag bytes.fromhex(hex_str).decode(utf-8) if flag in possible_flag or { in possible_flag: print(f[] 可能的Flag: {possible_flag}) except: pass except Exception as ex: print(f[!] 转换明文时出错: {ex}) print(f[*] 原始解密整数 m 已输出请手动处理。)脚本使用要点与避坑指南数据类型使用gmpy2.mpz()将大整数包裹起来能获得更好的性能和精度。上述脚本中gmpy2.invert和gmpy2.powmod会自动处理。核心验证assert语句不是必须的但强烈建议加上。它能快速帮你定位是分解错误、参数输入错误还是计算逻辑错误。解密结果处理解密得到的m是一个大整数。long_to_bytes函数来自pycryptodome库的Crypto.Util.number模块是标准转换方式。如果提示没有这个模块可以安装pip install pycryptodome或者使用Python内置的int.to_bytes()方法但需要自己计算长度。编码问题不是所有明文都是UTF-8文本。它可能是二进制数据、Base64编码后的字符串、或者直接是Flag的十六进制表示。脚本中尝试了多种常见转换方式。如果都失败请结合题目描述如“flag格式为 flag{...}”手动分析plaintext字节。5. 典型赛题变形与进阶思考纯粹的“给n,e,c分解n”是入门题。出题人往往会加一些变化来增加趣味性。5.1 变体1n由多个素数相乘多素数RSA有时n可能不是两个素数而是三个或更多素数的乘积n p * q * r。这并不影响攻击的本质反而因为每个素数更小使得n更容易被分解。攻击流程调整分解n得到所有素因子p, q, r, ...。计算欧拉函数φ(n) (p-1)*(q-1)*(r-1)*...。后续计算d和解密m的步骤完全不变。实操提示使用sympy.factorint(n)会直接返回所有素因子及其幂次例如{p:1, q:1, r:1}处理起来非常方便。5.2 变体2e与φ(n)不互质这是小模数攻击中一个常见的坑。在密钥生成中要求gcd(e, φ(n)) 1。但如果出题人故意设置了一个错误的e使得它与φ(n)有公因数那么e在模φ(n)下就没有逆元d标准解密流程会失败。排查与解决分解n后先计算φ(n)和g gcd(e, φ(n))。如果g ! 1则标准RSA解密无效。此时可能需要使用AMM算法Adleman-Manders-Miller algorithm在有限域开根或者利用中国剩余定理CRT求解方程m^e ≡ c (mod n)。这已经超出了基础小模数攻击的范围属于中等难度的考点。但第一步永远是先分解n。5.3 变体3n以其他形式给出n不一定直接给出一个数字。可能隐藏在证书文件.pem里或者需要从一组数据中计算得到比如给出p和q让你自己算n。这就需要你熟悉各种数据格式的解析。处理.pem公钥文件from Crypto.PublicKey import RSA with open(public.pem, r) as f: key RSA.import_key(f.read()) n key.n e key.e print(fn {n}\ne {e})6. 常见问题排查与技巧实录即使原理和脚本都清楚实战中还是会遇到各种奇怪的问题。下面是我踩过的一些坑和解决方法。Q1分解n成功了也计算出了d但解密出来的明文是一堆乱码或者根本不是flag格式。检查1密文c是否正确确认你使用的c是真正的密文。有时题目会给多个数据别用错了。c通常是一个很大的整数。检查2编码转换是否正确尝试不同的解码方式。先用long_to_bytes(m)得到字节串b。直接打印b看是否有可读字符。尝试b.decode(‘utf-8’)。尝试b.decode(‘latin-1’)。将b.hex()的结果进行Hex解码bytes.fromhex(hex_str).decode(‘utf-8’)。对b进行Base64解码base64.b64decode(b)。检查3解密过程本身是否正确用一个极小的例子验证你的脚本。例如自己用小的p61, q53, e17生成一对密钥加密一个数字m65然后用你的脚本去解密看是否能还原。检查4题目是否有其他步骤解密得到的m可能还不是最终flag它可能是一个新的密钥、一个URL、或者需要进一步解压的数据。仔细阅读题目描述。Q2在线分解网站和本地脚本都分解不了n怎么办确认n的大小如果n超过1024位基本就不是预期的小模数分解了要考虑其他攻击方式如共模攻击、低加密指数攻击、维纳攻击等。尝试YAFU本地Python脚本能力有限YAFU的算法更强。检查n是否为素数用gmpy2.is_prime(n)检查。如果n是素数那根本不是标准的RSA可能是其他密码体系或考察对RSA条件的理解。重新审题是不是需要从其他信息里推导出p或q比如给出了pq或p-q的提示。Q3计算d的时候报错“invert() no inverse exists”怎么回事这就是上面提到的e和φ(n)不互质的情况。计算g gcd(e, phi_n)如果g ! 1则说明标准解密行不通。你需要寻找其他解法比如如果g很小且c是g的倍数这种情况很少见。更可能的是需要用到AMM算法在模p和q下分别对c开e次方再用CRT组合。这是一个进阶话题遇到时建议搜索“RSA e and phi not coprime”或“RSA decryption when e not coprime to phi”。个人经验中的独家技巧养成验证习惯分解得到p, q后立刻验证p*q n且p和q都是素数。这能避免90%因复制错误或分解错误导致的问题。善用断言在脚本的关键步骤加入assert让程序自动帮你检查中间结果的正确性。标准化输入处理写一个通用的输入解析函数能自动识别十进制、十六进制0x开头、Base64编码的n, e, c。这在打CTF时能节省大量时间。留意非文本flag解密出的明文可能直接是flag{xxxx}的字节形式也可能是一个图片的二进制数据需要保存为文件查看或者是一个压缩包的字节流。不要只盯着解码后的文本。小模数分解攻击是CTF Crypto中RSA类题目的基石。掌握它不仅意味着你能解决一大批基础题更重要的是你彻底理解了RSA安全性的根本来源——大整数分解的困难性。当你以后再看到RSA题目时第一反应就应该是去观察n的大小这个习惯能帮你快速定位解题方向。从这个小漏洞入手逐步去探索共模攻击、低加密指数广播攻击、维纳攻击等更精妙的攻击方式你会发现密码学的攻防世界充满了这种“在完美理论中寻找现实瑕疵”的乐趣。