前几天整理解题笔记翻到某平台上一道挂着 Crypto 标签的 Xman-RSA当时为了把它彻底吃透我把 RSA 常见的攻击姿势重新捋了一遍。今天就把这道题的完整 writeup 写出来重点不是让你背脚本而是看懂每一步为什么这么做。如果你刚入门 CTF 的密码学卡在各种 RSA 题上或者刷题时见过这种给两个公钥、两个密文但不知道从哪下手的题这篇应该能帮你省不少时间。先说结论这道题表面上是让你解 RSA实际上考的是参数之间的复用关系——同一个模数被反复使用或者两个模数共享同一个素数因子。只要发现这层关系根本不需要暴力分解几百位的 n。整个过程我会从附件分析、工具使用、数学原理到最后的 Python 脚本一一拆开代码可以直接拿去跑换到同类型的题上也能用。1. 题目初探与附件分析1.1 拿到题目的第一眼文件清单与信息收集压缩包解压以后通常是一组看着很普通的文件两个.pem公钥文件两个.enc密文文件。没有私钥没有加密脚本连提示都没有。这种配置在 RSA 题里非常典型基本就是在告诉你破解点不在大数分解的硬功夫而在参数之间的关系上。我第一次拿到附件时先是例行公事地看了一下文件大小。公钥 PEM 文件一般就几百字节密文文件长度往往和模数的字节长度一致。如果密文文件长度是 128 字节左右对应的就是 1024 bit 的 RSA如果 256 字节那就是 2048 bit。这个细节可以帮你先确认 RSA 的规模也能在后续解析公钥时做个对照防止文件读取姿势不对导致密文数值错位。文件清单大致如下文件类型我的猜测pubkey1.pem / pubkey2.pem公钥文件内含 RSA 的 n 和 eflag1.enc / flag2.enc密文文件待解密的二进制数据文件名如果不一样也没关系比如有些版本叫 public1.pem、cipher1.txt核心思路完全一致。重点是先搞清楚公钥里到底写了什么。这里要提醒一句PEM 文件本质是 Base64 编码后的 DER 结构不要用文本编辑器看一眼就完事必须用工具解析成具体的 n、e 数值否则后面什么都做不了。1.2 用命令行和 Python 提取公钥参数最直接的方式是 OpenSSL命令如下openssl rsa -pubin -in pubkey1.pem -text -noout输出大致长这样RSA Public-Key: (1024 bit, 2 num) Modulus: 00:aa:bb:cc:dd:... Exponent: 65537 (0x10001)其中 Modulus 冒号后面那一大串十六进制就是模数 nExponent 就是公钥指数 e。把两个公钥都跑一遍重点看 Modulus 是否完全一致。不过比赛中不一定有 OpenSSL 环境用 Python 反而更省事。只要有pycryptodome库解析公钥只需要三行from Crypto.PublicKey import RSA key RSA.import_key(open(pubkey1.pem, rb).read()) print(hex(key.n), key.e)这样我们能拿到两个公钥的(n1, e1)和(n2, e2)。这一步是整个题的核心情报收集阶段信息就藏在 n 和 n 的关系里。2. 突破口两个公钥之间的“复用关系”2.1 为什么单个公钥看起来完全正常只看 pubkey1.pem 时它就是一把正常的 RSA 公钥一个几百位的大数 n加上常见的指数 e65537。单独看没有任何毛病。如果这时候想的是“1024 bit 好像可以尝试分解”那就掉进最费时间的坑里了。现代 RSA 分解 1024 bit 不是完全不可能但绝对不应该作为第一选择尤其是在题目刻意给了两把公钥的情况下。把两个公钥的 n 放在一起比对问题就暴露了。常见结果有两种要么n1 n2要么n1 ! n2但gcd(n1, n2) 1。这两种情况分别对应 RSA 密钥管理里最经典的失误模数复用和素数复用。我猜当年出题人就是想让选手意识到RSA 参数不是孤立存在的多个公钥之间的数学关联可以直接宣判 RSA 的死刑。2.2 共模复用与素数复用两种典型情况先给一个简单的对照表复用类型判断条件攻击方法共模复用n1 n2扩展欧几里得求 s1、s2用共模攻击恢复明文素数复用gcd(n1, n2) 1求出共享素数 p分解两个 n再求私钥解密生活化一点理解共模复用就像两个人共用一个保险箱但各自配了一把齿形不同的钥匙。虽然你单独看某一把钥匙很正常但只要同时拿到两把钥匙就能通过齿形之间的数学关系把保险箱打开。素数复用更像两个保险箱的锁芯里都有一根完全一样的销钉你只要把这根销钉抽出来两个保险箱同时垮掉。2.3 为什么这种关系是设计好的考点CTF 题来源于真实世界。现实中因为随机数生成器缺陷、系统迁移、固件模板复制等原因确实出现过大量密钥之间存在共享素数的事件。出题人把这种事故包装成一道题目本质上是在训练选手用“参数审计”的眼光看待公钥而不是一上来就无脑跑分解工具。所以拿到这种附件时先写三行代码打印 n1 的 hex、打印 n2 的 hex、打印gmpy2.gcd(n1, n2)。这一套组合能过滤掉一多半参数复用类的 RSA 题。当年我做这道题时最开始的半小时浪费在硬解一个看起来普通的 n 上后来把两个 n 一对比才发现真相就这么摆在眼前。3. 核心攻击原理与数学推导3.1 共模攻击的完整推导共模攻击的适用条件非常清晰同一个模数 n两个不同的加密指数 e1、e2并且gcd(e1, e2) 1。如果两个密文是同一个明文 m 分别用 e1、e2 加密得到的c1 m^e1 mod nc2 m^e2 mod n因为 e1 和 e2 互素根据扩展欧几里得算法一定存在整数 s1、s2 满足e1 * s1 e2 * s2 1然后计算c1^s1 * c2^s2 ≡ m^(e1s1) * m^(e2s2) ≡ m^(e1s1 e2s2) ≡ m^1 ≡ m (mod n)一个很小的例子帮你确认思路。比如 n35e15e211m3那么 c13^5 mod 35 33c23^11 mod 35 12。扩展欧几里得算出 5*(-2) 11*1 1也就是 s1-2s21。这里 s1 是负数需要先对 c1 求模逆33 mod 35 的逆是 17所以 c1^s1 等价于 17^2 mod 35 9再乘上 c212得到 108 mod 35 3。明文 m3 就恢复了。核心代码就是这么来的。要注意负数指数的处理不能直接pow(c, -2, n)必须先取模逆再对指数取绝对值。3.2 共享素数分解的推导如果两个模数不同但它们的最大公约数大于 1情况就更直接了。设n1 p * q1n2 p * q2这里的 p 就是两个模数共享的那个素数。gcd(n1, n2)可以直接算出来因为它就是 p。得到 p 之后q1 n1 // pq2 n2 // p两个 n 都完成了分解。有了 p 和 q欧拉函数就是phi (p - 1) * (q - 1)。公钥指数 e 已知就可以求私钥d inverse(e, phi)然后用m pow(c, d, n)解密。如果两个密文分别来自两个不同的明文那就对 n1、n2 各自解一次再把两个解出的字节拼接起来。通常题目会把 flag 分成两段分别加密所以拼接顺序需要留意一般就是明文顺序。3.3 为什么参数复用会“秒杀”大数分解RSA 的安全性建立在“由 n 分解出 p、q 很难”这个假设上。可一旦两个 n 共享素数 p求 gcd 是非常快的多项式时间运算几百位的大数立刻被撕开一个口子。而共模攻击更离谱它甚至不需要分解 n只要知道两个密文和两个指数的线性关系就能把明文直接从密文里“提”出来。这两个攻击原理都不复杂但它们很有代表性RSA 的安全性不只是取决于单把密钥的参数强度还取决于整个密钥集合里是否存在可被利用的数学关联。这也是为什么在密码学的实际工作里密钥审计和复用检测比单纯追求大位长更重要。4. 完整 WriteUp脚本实现与逐步解读4.1 环境准备与依赖库建议直接用 Python 3需要安装两个库pip install pycryptodome gmpy2pycryptodome用来解析 PEM 公钥和做字节转换gmpy2提供快速的大整数扩展欧几里得和模逆运算。后者在处理几百位的大数时比 Python 自带的pow辅助函数更顺手而且很多 CTF 选手的环境里已经默认装好了。如果遇到ImportError大概率是 Python 环境里同时存在旧版Crypto和pycryptodome冲突可以先把旧的pycryptodome卸载再装或者用pip install --upgrade pycryptodome处理。4.2 自动判断攻击路径的完整脚本下面这个脚本把两种攻击路径都写了。你只需要把文件名替换成实际附件里的文件名运行后它会自动判断是共模复用还是素数复用并输出解密结果。import gmpy2 from Crypto.PublicKey import RSA from Crypto.Util.number import long_to_bytes def load_pubkey(path): with open(path, rb) as f: key RSA.import_key(f.read()) return key.n, key.e def load_cipher(path): data open(path, rb).read().strip() # 如果密文文件是十六进制文本先转成整数 try: text data.decode() if all(c in 0123456789abcdefABCDEF for c in text) and len(text) % 2 0: return int(text, 16) except UnicodeDecodeError: pass # 大多数 .enc 文件直接是二进制按大端读取即可 return int.from_bytes(data, big) def common_modulus_attack(n, e1, e2, c1, c2): # 扩展欧几里得e1 * s1 e2 * s2 1 _, s1, s2 gmpy2.gcdext(e1, e2) # 负数指数需要先求模逆再取绝对值 if s1 0: c1 gmpy2.invert(c1, n) s1 -s1 if s2 0: c2 gmpy2.invert(c2, n) s2 -s2 m (pow(c1, s1, n) * pow(c2, s2, n)) % n return m def solve(n1, e1, c1, n2, e2, c2): # 情况一共模复用 if n1 n2: print([*] common modulus detected) m common_modulus_attack(n1, e1, e2, c1, c2) return long_to_bytes(m) # 情况二素数复用 p gmpy2.gcd(n1, n2) if p 1: print([*] shared prime detected:, p) res b for n, e, c in [(n1, e1, c1), (n2, e2, c2)]: q n // p phi (p - 1) * (q - 1) d gmpy2.invert(e, phi) m pow(c, d, n) res long_to_bytes(m) return res raise ValueError(No common modulus or shared prime found) n1, e1 load_pubkey(pubkey1.pem) n2, e2 load_pubkey(pubkey2.pem) c1 load_cipher(flag1.enc) c2 load_cipher(flag2.enc) flag solve(n1, e1, c1, n2, e2, c2) print(flag)脚本逻辑并不复杂但有几个细节值得展开。第一load_cipher同时兼容了二进制和十六进制文本实战里.enc文件有相当概率是直接用int.from_bytes保存的二进制但也有人会把密文打印成 hex 存成文本写一个自适应读取函数能省很多事。第二common_modulus_attack里必须先判断s1和s2的符号再决定是否取模逆否则一运行就会抛ValueError: pow() 2nd argument cannot be negative。第三两种路径都覆盖之后不管题目实际是哪种复用脚本都能正确处理。4.3 跑通脚本后的输出解读脚本运行后如果走的是共模攻击打印结果通常直接就是可见的 flag比如flag{...}或RCTF{...}。如果走的是素数分解路径会把两个 n 分别解密后的字节拼在一起同样输出一个完整的 flag 格式字符串。如果输出里出现大量不可见字符先不要慌。把结果转成 hex 看一眼print(flag.hex())有时候只是long_to_bytes的长度不对或者明文的字节序是大端、小端搞反了。RSA 密文转整数时常见的是int.from_bytes(data, big)如果文件是从某个脚本生成且用了小端你就需要改成little。这个细节虽然低级但非常容易在复现的时候让人怀疑人生。5. 踩坑记录与常见问题速查5.1 密文文件读了半天读不对这是最常见的问题。int(open(flag1.enc).read())这种写法在密文是二进制时直接报错在密文是十六进制文本时又可能因为末尾换行而解析失败。正确做法是用二进制模式读取并且先判断文件内容形态。如果文件头是30开头且整体是乱码几乎可以确定是二进制如果全是可见的十六进制字符就走int(text, 16)。上面脚本里的load_cipher已经处理了这两种情况。还有一种坑同一个题目里两个密文文件的编码方式可能不一样。我之前遇到过公钥解析正常、但一个密文是十六进制、另一个是二进制的情况。所以load_cipher要对每个文件独立判断不要想当然认为所有文件格式一致。5.2 共模攻击脚本报了负数指数错误很多人第一次写共模攻击时会直接写m pow(c1, s1, n) * pow(c2, s2, n) % n当s1或s2为负时Python 会立刻报错。正确做法是用模逆把负指数“掰正”。具体来说如果s1 0就计算c1_inv gmpy2.invert(c1, n)然后用pow(c1_inv, -s1, n)。需要特别注意的是invert(c1, n)要求c1和n互质在绝大多数正常 RSA 题目里都满足。如果真遇到不互质的情况说明密文泄露了 n 的因子那反而是更好的突破口。5.3 还有一种情况两个 n 既不相同也互素如果你发现n1 ! n2而且gcd(n1, n2) 1这时脚本会报错题目大概率不是参数复用类。那就要看看公钥指数 e 是不是很小比如 e3、e5以及密文是不是只有一组。如果同一明文被多个不同模数加密可以考虑低加密指数广播攻击如果密文之间存在线性关系可以考虑相关消息攻击。总之路是死的人是活的公钥关系检查只是第一步不是万能药。5.4 输出结果拼接顺序混乱素数复用路径里我默认按n1的解密结果在前、n2的解密结果在后进行拼接。但有些题故意把两段明文反着放或者明文中夹杂填充字符导致拼出来不是完整的 flag。遇到这种情况可以分别解密后把两个十六进制结果先打印出来肉眼确认哪段像 flag 开头再调整顺序。这个检查比反复跑脚本快得多。6. 攻击面扩展从一道题看 RSA 密钥管理的影响范围6.1 现实中的参数复用来自哪里很多人觉得这种题只是 CTF 里的理想化模型其实现实中 RSA 参数复用的案例并不罕见。老旧的随机数生成器如果初始化不良可能在短时间内为不同用户生成相同的大素数系统镜像、虚拟机模板、IoT 设备出厂固件里如果直接打包了同样的密钥文件也会造成一堆设备共用同一个私钥或共用同一个模数还有不少公司在做密钥迁移时图省事直接把旧证书的模数复制到新证书里只改了指数这类操作都会埋下参数复用的种子。所以这道题看似在考数学实际上是在提醒从业者密钥生成过程必须要有足够的熵并且不能为了兼容去复用任何关键参数。6.2 一旦泄露影响是“链式”的如果某个 RSA 公钥池里存在共享素数攻击者只要拿到两份公钥就能用 gcd 快速分解出这个素数进而分解所有共享该素数的模数。换句话说一个短板会拖垮一整批密钥。共模攻击的影响范围也类似同一个模数被多个不同指数复用只要攻击者拿到了同一明文在不同指数下的密文就能在不分解 n 的情况下恢复明文。这种“链式”效应在真实环境里非常可怕。你以为只是某个边缘系统的密钥出了问题结果其他用同一个 n 或共享素数的系统全部跟着遭殃。安全工作的重点之一就是在密钥未出事之前把这些关联关系扫出来。6.3 防御建议与自查清单从这道题延伸出来我觉得每个涉及 RSA 密钥管理的人都应该把下面几条记下来密钥生成必须使用密码学安全的随机源不要用random.random()这类伪随机数生成大素数。生成多个 RSA 密钥后一定要做两两 gcd 检查。这个检查非常快但能直接发现共享素数问题。公钥池要定期审计扫描模数是否重复、是否存在共享因子。不要试图通过给不同用户分配不同 e 的方式来复用同一个 n。这种做法在数学上已经证明是不安全的。推荐位长至少 2048 bit重要系统 3072 bit 或更高但位长只是底线参数独立性同样重要。我个人在实际解题中最大的体会是RSA 题拿到手的第一件事永远不是急着分解而是先检查参数之间的“关系”。打印三条信息——n1、n2、gcd(n1, n2)——这几乎成了我的固定动作能过滤掉一大批题。最后再分享一个小技巧解密得到的字节先看 hex再尝试decode()很多奇怪的编码问题都能这样轻松绕过去。这种参数复用类的题目刷过一次之后以后再遇到类似的附件结构基本就能秒判攻击路径了。