1. 项目概述一次经典的RSA模数攻击实战复盘如果你玩过CTF尤其是Web或Crypto方向的题目大概率遇到过RSA。RSA作为非对称加密的基石其安全性建立在“大数分解难题”之上。但密码学从来不是简单的套公式它更像一个精密的钟表任何一个齿轮参数的错用或暴露都可能让整个系统停摆。[GXYCTF2019]CommonModulusAttack这道题就是一个绝佳的案例。它没有考察复杂的数学推导而是聚焦于一个在现实世界和CTF赛场上都屡见不鲜的“错误用法”在不更换模数N的情况下重复使用公钥对同一消息进行加密。乍一看这似乎没什么问题。公钥本来就是公开的用同一个N加密不同消息很常见。但关键在于如果攻击者能够获取到用同一模数N、不同公钥指数e加密同一明文m的两组密文那么在特定条件下他就可以在不分解N、不知道私钥d的情况下直接恢复出明文m。这就是所谓的“共模攻击”Common Modulus Attack。这道题目的场景非常典型服务器用同一个大整数N但两套不同的公钥(e1, N)和(e2, N)分别加密了同一个flag明文生成了两个密文c1和c2。我们的任务就是利用c1, c2, e1, e2, N反推出flag。这不仅仅是解一道题更是理解RSA实现中一个关键禁忌的窗口。在实际的软件开发中比如密钥轮转设计不当、缓存机制误用都可能无意中引入此类漏洞。接下来我将带你完整复盘这次攻击从原理推导、脚本编写到实战中的各种坑和技巧让你不仅会“抄作业”更能明白背后的“所以然”。2. 攻击原理深度拆解为什么共模是危险的要理解共模攻击我们得先回到RSA最基础的加密公式对于公钥(e, N)加密过程是c ≡ m^e (mod N)。这里m是明文c是密文≡表示模N同余。现在假设我们有以下已知条件同一个大模数N两个互质的公钥指数e1和e2这是攻击成立的关键前提即gcd(e1, e2) 1同一明文m分别用这两套公钥加密得到的密文c1 ≡ m^e1 (mod N)c2 ≡ m^e2 (mod N)作为攻击者我们手上有(N, e1, e2, c1, c2)目标是求m。2.1 核心数学武器扩展欧几里得算法与贝祖等式攻击的核心在于扩展欧几里得算法。因为e1和e2互质根据数论中的贝祖定理一定存在两个整数s和t使得e1 * s e2 * t gcd(e1, e2) 1扩展欧几里得算法就是用来求解这个s和t的高效方法。得到s和t之后神奇的推导就开始了我们有c1 ≡ m^e1 (mod N)和c2 ≡ m^e2 (mod N)。将同余式两边同时取幂c1^s ≡ (m^e1)^s ≡ m^(e1*s) (mod N)c2^t ≡ (m^e2)^t ≡ m^(e2*t) (mod N)将上面两个式子相乘c1^s * c2^t ≡ m^(e1*s) * m^(e2*t) ≡ m^(e1*s e2*t) (mod N)代入贝祖等式e1*s e2*t 1c1^s * c2^t ≡ m^1 ≡ m (mod N)至此我们得到了一个直接计算明文m的公式m ≡ c1^s * c2^t (mod N)。注意这里s或t很可能是一个负数。在模运算中一个数的负指数次幂需要先计算其模逆元。即如果s是负数则c1^s (mod N)的实际计算方式是(c1的模逆元)^(|s|) (mod N)。Python的pow()函数内置支持模运算下的负指数它会自动处理模逆元这是非常方便的一点。2.2 攻击成立的条件与边界思考理解攻击的边界和失败场景比记住成功公式更重要核心条件e1与e2必须互质。如果它们的最大公约数不是1比如gcd(e1, e2)g那么贝祖等式右边是g公式将变成m^g你需要对结果开g次方根才能得到m这在模N下通常是困难的除非g很小且m^g未超过N。明文相同攻击的前提是同一个明文m被加密了两次。如果加密的是不同的消息此攻击无效。模数N相同这是“共模”的定义无需赘述。明文格式恢复出的m是整数形式需要根据题目约定的编码方式如ASCII、十六进制、Base64转换为字符串。有时m可能很大直接转换会失败需要先尝试long_to_bytes。这个攻击之所以危险在于它完全绕过了RSA的安全假设。攻击者不需要分解N这是RSA安全的基石也不需要计算私钥d仅仅利用公钥材料和不安全的用法模式就直捣黄龙。在真实场景中如果一套RSA密钥对长期不更换模数N只是定期更换e和d那么一旦某次加密的明文被攻击者通过其他方式猜出或获取到一部分就可能危及历史所有使用该N加密的密文。3. 实战解题步骤全解析理论清晰后我们进入实战。假设我们已经从题目描述、网络流量包或服务器响应中提取到了以下关键参数N 0x... (一个很大的十六进制整数) e1 65537 c1 0x... (密文1的十六进制) e2 12345 c2 0x... (密文2的十六进制)我们的目标是解出m。3.1 环境与工具准备工欲善其事必先利其器。CTF密码学题目尤其是涉及大整数运算的强烈推荐使用Python因为它内置了对任意精度整数的原生支持并且有强大的第三方库。必备工具Python 3.x这是我们的主力。gmpy2库这是一个高性能的多精度算术库是libgmp的Python封装。它在处理非常大的整数模幂运算如pow(c, s, N)时速度远超Python内置的pow。安装命令pip install gmpy2。如果安装失败可以尝试先安装libgmp的开发包如Ubuntu下的libgmp-dev。PyCryptodome库一个功能全面的密码学库。虽然本题核心用不到但它提供的Crypto.Util.number模块中的long_to_bytes和bytes_to_long函数是编码转换的瑞士军刀非常方便。安装pip install pycryptodome。备用方案如果实在装不上gmpy2纯Python内置的pow(a, b, c)函数也能完成模幂运算只是当指数特别是负指数取模逆元时或模数极大时速度会慢一些。对于CTF题目通常内置pow也够用。3.2 攻击脚本编写与逐行解读下面是一个健壮、可读性高的攻击脚本我为你添加了详尽的注释#!/usr/bin/env python3 # -*- coding: utf-8 -*- Common Modulus Attack 共模攻击脚本 适用于 [GXYCTF2019]CommonModulusAttack 及类似题型 import gmpy2 from Crypto.Util.number import long_to_bytes, bytes_to_long # 扩展欧几里得算法返回 (gcd, s, t) def extended_gcd(a, b): if b 0: return (a, 1, 0) else: gcd, s1, t1 extended_gcd(b, a % b) s t1 t s1 - (a // b) * t1 return (gcd, s, t) def common_modulus_attack(N, e1, e2, c1, c2): 执行共模攻击 参数: N: 公共模数 (整数) e1, e2: 两个公钥指数 (整数需互质) c1, c2: 两个密文 (整数) 返回: 解密得到的明文整数 m或 None如果攻击失败 # 1. 验证e1和e2是否互质 g, s, t extended_gcd(e1, e2) print(f[*] 扩展欧几里得算法结果: gcd({e1}, {e2}) {g}, s {s}, t {t}) if g ! 1: print(f[-] 错误e1({e1}) 和 e2({e2}) 的最大公约数不为1无法直接使用标准共模攻击。) # 如果g很小且m^g N可以尝试计算 (c1^s * c2^t) % N 再开g次方 # 但这种情况在CTF中较少见通常题目会确保e1,e2互质。 return None # 2. 使用扩展欧几里得算法得到的系数s和t计算明文 # 注意s或t可能为负数gmpy2.powmod支持负指数自动计算模逆元 # 公式: m (c1^s * c2^t) mod N if s 0: # 如果s是负数计算c1模N的逆元然后取正指数次幂 # 等效于 gmpy2.powmod(c1, s, N)因为powmod内部处理了负指数 c1_inv gmpy2.invert(c1, N) part1 gmpy2.powmod(c1_inv, -s, N) else: part1 gmpy2.powmod(c1, s, N) if t 0: c2_inv gmpy2.invert(c2, N) part2 gmpy2.powmod(c2_inv, -t, N) else: part2 gmpy2.powmod(c2, t, N) # 将两部分相乘后模N得到明文整数m m (part1 * part2) % N print(f[] 计算得到明文整数 m {m}) return m # 以下是题目具体数据填充区域 # 请将题目给出的数据替换下面的值 # 数据通常以10进制或16进制字符串给出注意转换 N 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929 e1 17 c1 0x4b7d3fe3ff12c7ea22843dac6e5c1c0d22d6bc7a3c2e4f1c9f1f2c0c9b0c8c7c6c5c4c3c2c1c0bfbebdbcbbbab9b8b7b6b5b4b3b2b1b0afaeadacabaaa9a8a7a6a5a4a3a2a1a09f9e9d9c9b9a999897969594939291908f8e8d8c8b8a898887868584838281807f7e7d7c7b7a797877767574737271706f6e6d6c6b6a696867666564636261605f5e5d5c5b5a595857565554535251504f4e4d4c4b4a494847464544434241403f3e3d3c3b3a393837363534333231302f2e2d2c2b2a292827262524232221201f1e1d1c1b1a191817161514131211100f0e0d0c0b0a09080706050403020100 e2 65537 c2 0x4b7d3fe3ff12c7ea22843dac6e5c1c0d22d6bc7a3c2e4f1c9f1f2c0c9b0c8c7c6c5c4c3c2c1c0bfbebdbcbbbab9b8b7b6b5b4b3b2b1b0afaeadacabaaa9a8a7a6a5a4a3a2a1a09f9e9d9c9b9a999897969594939291908f8e8d8c8b8a898887868584838281807f7e7d7c7b7a797877767574737271706f6e6d6c6b6a696867666564636261605f5e5d5c5b5a595857565554535251504f4e4d4c4b4a494847464544434241403f3e3d3c3b3a393837363534333231302f2e2d2c2b2a292827262524232221201f1e1d1c1b1a191817161514131211100f0e0d0c0b0a09080706050403020100 # 注意上面的N, c1, c2是我随意写的超大整数并非真实题目数据。 # 真实解题时请务必替换为题目给出的确切数值。 # 数据可能是10进制数、16进制字符串以0x开头、Base64等形式需要正确转换。 # 执行攻击 print([*] 开始共模攻击...) print(f[*] N {hex(N)[:50]}...) # 打印N的前一部分避免输出过长 print(f[*] e1 {e1}, e2 {e2}) m common_modulus_attack(N, e1, e2, c1, c2) if m is not None: print(\n[*] 尝试将明文整数转换为字节...) # 尝试直接转换 flag_bytes long_to_bytes(m) print(f[] 明文字节: {flag_bytes}) # 尝试以字符串形式输出 try: flag_str flag_bytes.decode(utf-8) print(f[] 明文 (UTF-8): {flag_str}) except UnicodeDecodeError: print([-] UTF-8解码失败尝试其他编码或检查格式。) # 可能是flag包含特殊格式如flag{...}直接打印十六进制或尝试ASCII print(f[] 明文十六进制: {hex(m)}) # 有时flag被填充需要去除尾部不可见字符 flag_str_ascii flag_bytes.decode(ascii, errorsignore).strip() print(f[] 明文 (ASCII忽略错误): {flag_str_ascii}) else: print([-] 攻击失败。)3.3 关键操作与避坑指南数据输入格式处理这是新手最容易出错的地方。题目给出的数据可能是多种形式十六进制字符串通常以0x开头或直接是一长串0-9a-f的字符。Python中直接用int(hex_str, 16)转换。如果字符串有0x前缀int()也能识别。十进制字符串直接int(dec_str)。Base64编码先用base64.b64decode()解码成字节再用bytes_to_long()转成整数。直接写在源代码里像上面的示例一样直接赋值给变量。务必仔细核对一个字符错误就会导致结果天差地别。负指数的处理脚本中已经优雅地处理了。原理是c^(-s) mod N (c的模逆元)^s mod N。我们通过判断s和t的正负分别计算。使用gmpy2.powmod(c, s, N)是更简洁的方式因为它内部自动处理了负指数。明文解码计算出的m是一个大整数。long_to_bytes(m)会将其转换为字节串。但这里有个坑如果m的二进制表示的最高位不是1转换时可能会丢失开头的零字节。例如明文是b\x00flag转换后可能变成bflag导致格式错误。CTF的flag通常有固定格式如flag{或GXY{如果解码后开头不对可以尝试long_to_bytes(m).rjust(128, b\x00)等方式补零或者检查hex(m)的十六进制表示是否以00开头。使用gmpy2的必要性当N是2048位或更大指数s和t的绝对值也可能很大时纯Python的pow(c, s, N)计算可能会非常慢甚至内存溢出。gmpy2.powmod()底层是C实现的GMP库速度有数量级的提升。在CTF比赛中时间就是分数所以强烈建议配置好gmpy2环境。4. 从CTF到现实漏洞场景与防御解出这道题我们不应该只停留在“会了”的层面。更要思考这种漏洞在现实中是怎么产生的又该如何避免4.1 真实的漏洞场景模拟想象一个简化版的Web服务用户密码重置流程服务器生成一对RSA密钥(N, e)和(N, d)其中N固定作为系统长期使用的“主模数”。当用户申请重置密码时服务器生成一个随机令牌token明文。服务器用(e1, N)加密这个token将密文c1发送到用户注册邮箱的链接里。同时服务器在内部也用另一套公钥(e2, N)可能用于审计或另一套接口加密了同一个token密文c2存储到数据库。攻击者通过某种方式如渗透数据库、中间人攻击获取邮件流量同时获取到了c1和c2并且通过分析前端代码或API文档知道了公钥e1和e2公钥本来就是公开的。攻击者利用共模攻击即可恢复出token从而能够重置任意用户的密码。这个场景中问题的根源在于使用同一个模数N加密了同一个敏感信息。4.2 开发者视角如何正确使用RSA最重要的原则一对密钥对应一个模数。每次生成新的RSA密钥对时必须重新生成新的、随机的大素数p和q从而得到新的N。绝对不要在不同密钥对之间复用N。加密的语义安全标准的RSA加密教科书式RSA本身不是语义安全的即同样的明文每次加密会产生同样的密文。为了防御此类攻击在实际应用如PKCS#1 v1.5或OAEP填充方案中会在加密前对明文进行随机填充。这样即使加密同一个消息每次产生的密文也完全不同从而有效抵御共模攻击。所以永远不要使用“裸”的RSA加密即直接对明文进行m^e mod N运算。密钥管理与轮转建立规范的密钥生命周期管理策略定期轮换密钥。即使使用了安全填充长期使用同一对密钥也有风险。使用更现代的算法对于新的系统可以考虑使用基于椭圆曲线的加密算法如ECC其密钥更短、性能更好且不同的密钥对自然拥有不同的曲线参数从根本上避免了“共模”问题。4.3 CTF中的变种与拓展这道题是共模攻击最标准的形式。在更复杂的CTF题目中可能会遇到以下变种多个密文n 2如果同一个明文被多个互质的公钥指数e1, e2, ..., ek加密攻击依然成立。你需要找到一组系数si使得sum(ei * si) 1然后计算Π(ci^si) mod N。这可以通过求解多元一次丢番图方程或多次两两组合使用扩展欧几里得算法来实现。e1和e2不互质如前所述如果gcd(e1, e2) g 1那么恢复出的是m^g。如果g很小比如2或3并且m^g N即没有模运算溢出那么可以直接在整数域对m^g开g次方根得到m。Python中可以用gmpy2.iroot(m_power_g, g)来尝试。结合其他攻击题目可能不会直接给你N你需要从证书、网络流量或代码中自己提取。也可能需要先进行其他操作如解密一层对称加密、解码某种格式才能得到标准的(N, e, c)元组。5. 常见问题与调试技巧实录即使原理和脚本都清楚了实战中还是会遇到各种稀奇古怪的问题。下面是我在多次解题和教学中总结的“排坑手册”。5.1 问题排查清单问题现象可能原因排查步骤与解决方案运行脚本后输出的m转换成的字节串是乱码或者开头不是预期的flag{。1.数据输入错误N, e, c的值拷贝错误特别是十六进制字符串漏了0x前缀或多/少了字符。2.编码问题m可能正确但flag被hex或base64编码过需要二次解码。3.填充问题明文在加密前可能有PKCS#1等填充恢复的m包含填充数据需要正确剥离。4.攻击条件不满足e1和e2不互质或者c1/c2对应的明文根本不同。1.逐字核对将题目给出的原始数据与脚本中的变量值进行比对最好用print(hex(N))等方式完整打印出来对比。2.检查gcd在攻击函数开头打印g gcd(e1, e2)确保其为1。3.输出中间值打印s和t确保扩展欧几里得算法计算正确。4.尝试多种解码对long_to_bytes(m)的结果依次尝试.decode(utf-8),.decode(ascii),hex()查看或者用binascii.unhexlify()处理其十六进制串。脚本运行非常慢甚至卡死。1.未使用gmpy2使用纯Python的pow计算大数模幂尤其是负指数时需要先求模逆元再计算正指数幂效率极低。2.指数s/t的绝对值过大。1.安装并使用gmpy2这是最有效的解决方案。2.优化算法虽然扩展欧几里得算法得到的s和t可能很大但可以通过模逆元性质简化计算。实际上我们只需要s mod e2和t mod e1等简化后的系数。但对于CTF题直接用gmpy2处理通常足够快。报错OverflowError: int too large to convert to float或MemoryError。在计算pow(c, s)时没有模运算试图先计算巨大的幂结果再取模这会导致中间结果大到内存无法容纳。绝对不要先算幂再取模必须使用支持模运算的幂函数即pow(c, s, N)或gmpy2.powmod(c, s, N)。这个函数使用了模幂运算算法如快速幂中间结果始终不会超过模数N。得到的结果m比模数N还大。这违反了RSA的基本原理密文和明文都应小于N。几乎可以肯定是数据错误或计算错误。重新检查所有输入数据的完整性和正确性。确认c1和c2确实小于N。检查在计算c1^s * c2^t mod N时是否每一步都及时取了模或者最终结果是否忘了取模。解码后得到类似\x02\xf3\xa5...flag{real_flag}的字符串。这是典型的PKCS#1 v1.5填充。明文在加密前被添加了随机填充格式通常是0x00 0x02 [随机非零字节] 0x00 [原始明文]。你需要从恢复的数据中找到第一个0x00字节之后的部分即为真正的明文。可以用Python的.split(b\x00)[-1]来提取。这提醒我们题目可能模拟了更真实的加密环境。5.2 一个实用的调试脚本片段在编写最终攻击脚本前我通常会先写一个简单的验证脚本确保我理解对了数据# debug.py import gmpy2 from Crypto.Util.number import long_to_bytes, bytes_to_long, GCD # 假设从题目文件提取的数据 N 0x123...abc e1 65537 e2 49 c1 0x456...def c2 0x789...ghi print(fN 是 {N.bit_length()} 位) print(fc1 N? {c1 N}) print(fc2 N? {c2 N}) print(fgcd(e1, e2) {GCD(e1, e2)}) # 快速验证共模攻击公式的“可行性”不实际计算大幂运算 # 计算 e1*s e2*t 1 的一组解 g, s, t gmpy2.gcdext(e1, e2) print(f扩展欧几里得: s{s}, t{t}) print(f验证: e1*s e2*t {e1*s e2*t}) # 如果s, t的绝对值不大可以快速计算 if abs(s) 1000 and abs(t) 1000: # 注意这里仅当指数很小时才直接计算用于快速验证 # 实际攻击必须用 pow(c, s, N) 的形式 pass这个脚本能快速帮你确认数据是否基本合规密文小于N指数互质以及扩展欧几里得算法是否给出了预期的结果和为1。先通过这个小测试能避免在复杂脚本中浪费大量调试时间。5.3 心态与思维CTF密码学解题通法遇到任何RSA题我的第一反应是形成一个检查清单给了哪些参数找齐N, e, c, p, q, d, dp, dq... 任何数字都可能是突破口。参数之间有什么关系N p * qφ(N) (p-1)*(q-1)d e^(-1) mod φ(N)。检查是否有不寻常的关系比如p和q很接近、e很大可能是维纳攻击、e很小可能是低加密指数攻击、dp泄露等。有没有多次加密或相关加密如果是同一明文多次加密思考广播攻击、共模攻击。如果是相关明文如m和m1思考Franklin-Reiter相关消息攻击。模数N能否分解第一步永远是尝试用factordb.com这样的网站或yafu工具分解N。如果N很小512bit现代计算机可以秒破。即使很大也可能因为生成不当如p和q接近而被费马分解法破解。密文c本身有特征吗如果e非常小比如3且m^e N那么c就是m^e的整数直接对c开e次方就能得到m。CommonModulusAttack这道题就是上述第3点的典型应用。它训练的是你对RSA算法本身特性的深刻理解而非复杂的数学工具。掌握了它你就拿到了解开一类CTF Crypto题目的钥匙更重要的是在你自己设计或审查用到RSA的系统时你会本能地避开“共模”这个坑。密码学的安全往往就藏在这些对细节的深刻理解和严格遵守之中。