做 CTF Crypto 的朋友肯定遇到过这种场景题目只给了一串n、一个e、一段密文c整个交互界面干净得没有一点多余提示。很多初学者第一反应是拿 RSA 公式硬套然后把字母对着流程图抄一遍最后一头雾水。其实这类题目十有八九考的是 RSA 小模数分解攻击——只要n的位数小到可以被现有工具轻松分解公钥体系就直接崩塌你甚至不需要拿到任何私钥文件仅凭公开的n/e参数就能逐步推导出d最后把明文完整还原回来。这篇文章会把完整的链路拆开讲清楚先讲小模数攻击为什么成立再做数学推导再走到实际分解、解密脚本最后聊聊我踩过的坑。适合刚入 Crypto 方向、想把 RSA 这类题彻底搞明白的同学收藏。1. RSA 小模数攻击的底层逻辑1.1 先理解 RSA 这条公式链RSA 的核心其实只有两条公式加密c ≡ m^e (mod n)解密m ≡ c^d (mod n)其中m是明文对应的整数c是密文对应的整数。公钥是(n, e)私钥是d而n p × qp和q是两个大素数。e是加密指数CTF 里最常见的值是65537。私钥d满足e × d ≡ 1 (mod φ(n))这里的φ(n)是欧拉函数当n p × q且p、q都是素数时φ(n) (p - 1) × (q - 1)。我一直喜欢用一个生活化的类比来记这条链公钥是一把能锁上的锁别人用你的公钥把明文数字关进箱子只有拿着私钥d的人才能开箱。攻击者如果能把n拆成p和q他就可以自己“配一把钥匙”算出φ(n)再求e的逆元得到d整个箱子就完全对他敞开了。这也是 RSA 安全性的全部前提大整数分解的困难性。n越大拆分越难n一旦小到可以分解RSA 就只是个摆设。1.2 小模数为什么是致命伤小模数攻击的核心思路非常朴素如果n不够大攻击者可以直接分解它。分解出p和q之后后面全是数学课上的常规计算。CTF 题目里所谓的“小模数”通常指n的二进制位长很小。常见范围从 64 bit 到 256 bit也偶尔见过 512 bit 左右的弱因子题。这个规模在真实世界当然不够安全但在比赛环境下恰恰是出题人留给你的破绽。模数二进制位长常见情况分解耗时参考常用手段64 bit 以下入门送分题秒级在线因子库、试除法64 ~ 128 bit基础练习秒级到分钟级在线因子库、YAFU、Pollard Rho128 ~ 256 bit中等偏难几分钟到更久YAFU、ECM、SageMath512 bit 及以上普通强度通常超出常规题目范围小模数攻击不适用需换思路这个表是经验值不同机器、不同运气差别很大。但核心判断标准只有一条n的二进制位长n.bit_length()越小分解越可行。很多人会误以为十进制位数才是关键其实 RSA 安全性看的是二进制位长。一个 20 位十进制数换算下来只有约 66 bit用在线因子库可能一瞬间就出结果。2. 数学推导从公钥到私钥的完整链条2.1 欧拉函数能不能配钥匙就看它前面提到φ(n) (p - 1) × (q - 1)这背后的含义是在 1 到n之间与n互素的整数个数。因为p、q是素数所以除了p的倍数、q的倍数之外其余数都与n互素数量正好是(p - 1) × (q - 1)。攻击者拿到p和q后第一件事就是算φ(n)。有了φ(n)加上公开的e就能求私钥d。整个过程不需要任何秘密信息这就是“公钥体系崩塌”的数学含义。有人会问不知道p和q能不能直接算φ(n)理论上如果你能统计出与n互素的整数个数也可以但这种方法在n很大的时候同样困难本质上和分解n难度相当。所以φ(n)的保密性完全建立在p、q不可知之上。2.2 扩展欧几里得求逆元拿来算私钥 d求d的标准方法是解同余方程e × d ≡ 1 (mod φ(n))只要gcd(e, φ(n)) 1逆元一定存在。扩展欧几里得算法不仅能算最大公约数还能把这个最大公约数表示成两个数的线性组合所以可以直接用来求逆元。这里用一个经典的小例子走一遍取p 61q 53那么n 3233φ(n) 60 × 52 3120取e 17。现在求d。先做普通欧几里得3120 17 × 183 917 9 × 1 89 8 × 1 18 1 × 8 0最后余数是 1说明gcd(17, 3120) 1。接着反向回代1 9 - 81 9 - (17 - 9) 2 × 9 - 171 2 × (3120 - 17 × 183) - 17 2 × 3120 - 367 × 17所以-367 × 17 ≡ 1 (mod 3120)。把-367取模后得到d ≡ -367 ≡ 3120 - 367 2753这就是经典的d 2753。实际写脚本时不需要手算Python 里gmpy2.invert(e, phi_n)一行就能完成。但手动走一遍的好处是你能真正理解逆元不是凭空出现的而是通过辗转相除的回代过程得到的。2.3 解密为什么能还原明文从欧拉定理说起有了d之后为什么c^d ≡ m (mod n)一定成立关键在e × d ≡ 1 (mod φ(n))这个设置。设e × d 1 k × φ(n)那么c^d ≡ (m^e)^d ≡ m^(ed) ≡ m^(1 kφ(n)) ≡ m × (m^(φ(n)))^k (mod n)如果gcd(m, n) 1根据欧拉定理m^(φ(n)) ≡ 1 (mod n)于是(m^(φ(n)))^k ≡ 1最终得到c^d ≡ m (mod n)这就是 RSA 解密能还原明文的完整理由。至于gcd(m, n) 1的情况比如明文恰好是p或q的倍数欧拉定理的初始条件不满足但实际题目里m是随机生成的明文数字和n不互素的概率极低。严谨的数学处理可以用中国剩余定理或者 Carmichaeal 函数补齐CTF 实战中基本不需要额外处理。理解这一节的核心收获是一旦攻击者算出φ(n)整个 RSA 就退化成“一道求逆元、一次快速幂取模”的简单计算。后面的脚本环节基本就是照着公式写代码。3. 实战流程从 n/e/c 到明文完整还原3.1 拿到题目先判断该不该走分解路线我个人的习惯是任何 RSA 题到手先做三件事。第一看n的位长。用 Python 一行代码print(n.bit_length())如果结果小于 256基本可以考虑小模数分解攻击如果只有 64 到 128那几乎就是送分题。第二看e和c的形态。e 65537是最常见的常规配置。c如果和n差不多长说明加密过程没有太多花哨操作就是标准 RSA。第三把n丢进在线因子库先试一次。很多题目里的n小到在线库直接秒出结果这一步能帮你省掉本地工具的时间。在线库不行再上 YAFU 等本地工具。如果题目名称里还带small n、weak key、easy rsa这类提示基本就是明确告诉你去分解它。3.2 分解 n 的几种常用姿势本地分解工具里我最常用的是 YAFU。它会把试除、Pollard Rho、ECM 等算法自动组合起来整体体验很省心。用法很简单yafu factor(3233)输出里能看到类似53 * 61或者分行的质因子结果。拿到结果后记得用assert p * q n验证一下防止题目里n其实是多因子乘积后面计算φ(n)的公式要跟着调整。SageMath 也很方便一条命令搞定factor(3233)它返回的格式是53 * 61阅读起来非常直观。Python 里也可以自己写一个简单的 Pollard Rho 分解函数但效率通常不如 YAFU。实战中我建议优先用专门工具把时间花在解题思路上而不是在重复造轮子上。3.3 从 n/e/c 到明文还原的完整脚本这里给一份可以直接跑通的模板假设你已经从 YAFU 或在线因子库得到了p和qfrom Crypto.Util.number import long_to_bytes import gmpy2 # 题目给出的三个参数 n 3233 e 17 c 2790 # 分解 n 得到的两个质因子 p 53 q 61 assert p * q n # 1. 计算欧拉函数 phi_n (p - 1) * (q - 1) # 2. 求私钥 d d gmpy2.invert(e, phi_n) # 3. 解密得到明文整数 m pow(c, d, n) # 4. 转成字节串再转字符串 print(m) print(long_to_bytes(m))如果环境里没有gmpy2也可以自己写扩展欧几里得函数来求逆元def egcd(a, b): if b 0: return a, 1, 0 g, x, y egcd(b, a % b) return g, y, x - (a // b) * y g, x, _ egcd(e, phi_n) d x % phi_n重点解释一下pow(c, d, n)这个函数。Python 内置的三参数pow会执行快速幂取模效率远高于先算c ** d再取模。CTF 里密文和私钥都可能是大整数直接做幂运算会非常慢甚至内存爆炸所以务必使用三参数形式。long_to_bytes(m)来自Crypto.Util.number它把一个大整数按字节流还原。如果没装这个库也可以用bytes.fromhex(hex(m)[2:])达到类似效果。3.4 用一个超小例子手算验证整条链路为了让上面的数学推导落地我再用一个更小的参数手动走一遍。取p 17q 23那么n 391φ(n) 16 × 22 352。取e 7。求d352 7 × 50 27 2 × 3 12 1 × 2 0反向回代1 7 - 2 × 31 7 - (352 - 7 × 50) × 3 7 × 151 - 352 × 3所以d 151。验证加密取明文m 42那么c 42^7 mod 391 15。再验证解密15^151 mod 391 42明文被完整还原。这个例子里的数字很小方便你手动在纸上推一遍也能用来验证自己的脚本逻辑是否正确。真实比赛里不会直接把p和q给你但拿到p、q之后的计算流程和这个例子完全一致。4. 常见翻车现场与排查技巧4.1 分解出来的因子不止两个怎么办有些题目里的n并不是两个大素数的乘积而是三个甚至更多个素数的乘积。这时候φ(n)的公式要改成φ(n) (p - 1) × (q - 1) × (r - 1) ...然后继续用e求逆元流程完全一样。还有一种情况是n含有重复因子比如n p^2 × q此时φ(n) p × (p - 1) × (q - 1)要小心别直接用(p - 1)^2 × (q - 1)。判断方法很简单拿到分解结果后先看列出来的质因子数量。如果超过两个就逐个减一再相乘。assert p * q * r n这类验证能帮你第一时间发现遗漏。4.2 解密出来是一串数字不是可读字符pow(c, d, n)得到的是明文对应的整数直接打印当然是一串大数字。要把它转成字符串需要先转字节再解码。最常见的方式是我前面写的long_to_bytes(m)。如果出现乱码优先检查编码。CTF 里的 flag 大多是 ASCII 或 UTF-8直接用.decode()通常没问题。偶尔遇到题目用十六进制表示明文那就先把m转成十六进制字符串再还原。还有一种隐蔽情况是m转成字节后前面带了\x00肉眼看不出来但对解码有影响这时可以尝试去掉前导零再处理。4.3 e 和 φ(n) 不互素导致求逆失败用gmpy2.invert(e, phi_n)报错ZeroDivisionError说明gcd(e, phi_n)不等于 1逆元不存在。这类题已经不是普通的小模数攻击了更可能涉及低加密指数根、非互素指数攻击这类进阶玩法。遇到这种情况不要硬算逆元先执行一句gcd(e, phi_n)看看结果。如果gcd是 2、3 或 4 这类小数字题目往往是想让你先解一个“m 的 k 次方”问题再接开方或其它手段。这属于另一套攻击体系本文先不展开但你至少要知道在求d这一步报错不等于题目无解只是走错了分支。4.4 其他隐蔽坑位速查现场表现可能原因处理思路n本身是素数题目故意给素数模数不能直接当常规 RSA 处理试试φ(n) n - 1以及对应变体c 0或c 1加密数据比较特殊直接观察明文可能就很特殊先别急着跑脚本n能被小素数整除因子结构太弱先把小质因子全部试除出来再看剩余部分YAFU 卡住很久n位长略超范围换 SageMath 或更专业的数域筛工具或调整 ECM 参数m转出来不像 flag编码或字节序问题尝试交换高低字节序、尝试 UTF-8 之外的常见编码这些坑我都踩过至少一轮尤其是在m转字符串那步因为编码问题浪费过不少时间。后来学乖了每次解密先打印m的十六进制和字节两种形态再决定下一步。5. 再往深走一步小模数攻击的衍生与训练路线5.1 同一个 n 被多次使用共模攻击与分解n不同还有一种经典攻击不依赖模数大小而是因为同一个n被多个用户重复使用。如果题目里给了同一个n、两个不同的e_1和e_2且gcd(e_1, e_2) 1那么可以找到整数a、b满足e_1 × a e_2 × b 1于是m ≡ c_1^a × c_2^b (mod n)这种攻击利用了公开参数之间的代数关系不需要分解n。我在刷题时经常和小模数攻击混着遇到建议把两种思路都记熟。毕竟拿到题先判断攻击类型才是最快的解题路径。5.2 多因子 RSA 与光滑 p-1 攻击小模数攻击不只是“位数小”也包括“因子结构弱”。比如p - 1只由一些小素数因子组成这种情况称为光滑数。此时即使用 Pollard p-1 算法也能在没有完整分解n的情况下把p找出来。这类题的典型表现是n看起来有 512 bit理论上不好分解但 YAFU 跑一会儿直接报出因子有时候输出里还会提示p-1相关的信息。我的建议是只要拿到题发现n偏大但题目设计很“弱”不妨先让 YAFU 跑一轮很多光滑因子题根本不需要手动写特殊算法。5.3 准备一套自动化武器库比赛时时间很宝贵我习惯把常见的 RSA 攻击写成模板输入n/e/c后自动判断位长、尝试在线因子库、调用 YAFU再自动解密。核心流程大致是读入n/e/c计算n.bit_length()如果位数很小先查在线因子库查不到就调用 YAFU 分解拿到所有质因子后计算φ(n)求d用pow(c, d, n)得到明文整数再转字符串这个流程写成一个函数后每次遇到 RSA 题都能秒级响应。唯一的注意点是YAFU 的调用可能是交互式的自动化时最好用命令行参数方式传入并设定合理超时时间避免卡在等待输入上。5.4 新手该怎么练这类题我的建议是从最小规模开始。先找 64 bit 左右的n把在线因子库和脚本流程跑熟。然后再挑战 128 bit、256 bit 的题目感受一下分解耗时的变化。等小模数这条路完全走通之后再去学低加密指数、共模攻击、低解密指数、光滑 p-1 等变体会顺利很多。练习的时候不要只看 writeup一定要亲手把 YAFU 装好、把gmpy2和pycryptodome装好、把脚本模板调通。这些前置准备工作看起来琐碎但比赛时决定成败的往往就是工具熟不熟。很多新手不是不会数学而是卡在工具使用和编码转换上。我在实际刷题过程中最常犯的错不是数学推导而是拿到题第一眼不看n的位数直接在白纸上推公式。后来养成了一个习惯拿到 RSA 题先写一行 Python 看bit_length再决定攻击路线。这个习惯帮我省下的时间比任何技巧都多。最后送大家一个实战小技巧在线因子库查不到时不要立刻放弃很多题目里的n只是稍微大了几个数量级YAFU 默认参数跑上几分钟可能就出结果。Crypto 解题里耐心和工具熟练度往往比灵光一闪更重要。