1. 项目概述当RSA遇上CTF从数学原理到Python实战如果你玩过CTFCapture The Flag比赛尤其是其中的密码学Crypto方向那你一定绕不开RSA。这个在现实世界中守护着无数网络通信安全的非对称加密算法在CTF赛场上却成了出题人“折磨”选手的利器。标题里的“大素数分解”和“共模攻击”正是RSA在CTF中最经典、也最考验选手密码学功底和编程能力的两种攻击场景。很多人一看到数学公式和长长的密钥就头疼觉得密码学高深莫测。但我想说只要用Python把原理实现一遍你会发现这些攻击思路其实非常直观甚至有点“巧妙”。这篇文章我就以一个老CTF选手和Python开发者的双重身份带你亲手用Python代码把这两个攻击场景从理论变成实战。我们不止要“解出flag”更要弄懂背后的“为什么”以及在实际操作中会遇到哪些坑。2. RSA基础回顾与CTF中的常见设定在深入攻击之前我们必须统一语言确保我们在同一个频道上讨论问题。RSA的安全性建立在“大数分解难题”之上但CTF题目往往会人为地制造一些弱点让分解成为可能。2.1 RSA加密解密的核心流程RSA算法围绕三个核心步骤展开密钥生成、加密和解密。在CTF中我们通常拿到的是公开的(N, e)和密文c我们的目标是求出明文m。密钥生成选择两个大素数p和q。计算模数N p * q。计算欧拉函数φ(N) (p-1)*(q-1)。选择一个整数e作为公钥指数满足1 e φ(N)且gcd(e, φ(N)) 1即e与φ(N)互质。常见取值为655370x10001。计算私钥指数d满足e * d ≡ 1 (mod φ(N))。即d是e模φ(N)的乘法逆元。加密过程对于明文m需转换为整数且m N加密得到密文cc ≡ m^e (mod N)解密过程使用私钥d解密密文cm ≡ c^d (mod N)在CTF题目中p和q是绝对保密的。攻击的突破口往往就隐藏在N、e、c的特定关系或不当选择中。2.2 CTF中RSA题目的典型“套路”CTF不是密码学的标准应用它更像是一场“找茬”游戏。出题人会故意在以下环节设置漏洞模数N过小这是最直接的弱点。如果N的位数如512比特以下不够大现代计算机完全可以在可接受的时间内通过暴力或数据库如factordb直接分解出p和q。素数生成不当p和q不是真正的“随机”大素数。例如它们可能过于接近、是光滑数所有素因子都很小、或者存在某种数学关系如共用素数。这为特殊的分解算法如Pollard‘s p-1, Williams’s p1提供了可能。公钥指数e选择不当例如e非常小如3可能导致低加密指数攻击。或者当相同的明文用不同的e加密时可能适用中国剩余定理攻击。共模攻击多个用户使用相同的N但不同的e对同一明文加密。这是我们今天要重点攻克的场景之一。侧信道与选择密文攻击这类题目更偏向于协议逻辑漏洞比如可以提交密文并获取解密结果但不返回明文只返回一些状态信息从而推断出私钥信息。理解这些“套路”就像掌握了出题人的心理。我们接下来的实战就是针对“大素数分解”对应套路1和2和“共模攻击”对应套路4的精准打击。注意在真实世界的密码学应用中N的长度至少应为2048比特p和q必须由密码学安全的随机数生成器产生且满足一系列严格的安全属性。CTF中的场景是特化的、弱化的旨在教学和挑战切勿将CTF中的技巧误用于实际安全评估。3. 实战一大素数分解攻击——当N不够“大”“大素数分解”攻击的核心思想简单粗暴既然RSA的安全基于Np*q难以分解那么如果我能分解N一切就结束了。在CTF中分解N的途径主要有两种一是N本身太小二是p或q本身有弱点。3.1 场景一直接暴力分解与小N查询这是最简单的情况。题目给出的N可能只有几十位或一百多位十进制数。对于这种规模的整数利用本地数学库或在线分解数据库可以瞬间解决。实战案例解析假设我们拿到一个题目N 322831561921859 e 23 c 0xdc2eeeb2782c这个N只有15位十进制数在现代计算机面前不堪一击。Python实战步骤分解N我们可以使用sympy库的factorint函数或者更专业的gmpy2库。但最简单快捷的方式是访问像factordb.com这样的网站。将N提交立刻得到结果322831561921859 13574881 * 23781539。计算私钥d得到p和q后计算φ(N) (p-1)*(q-1)然后求e模φ(N)的逆元d。解密计算m c^d mod N。import gmpy2 from Crypto.Util.number import long_to_bytes # 题目数据 N 322831561921859 e 23 c 0xdc2eeeb2782c # 分解N得到的p和q (来自factordb) p 13574881 q 23781539 # 验证 assert p * q N # 计算私钥指数d phi (p - 1) * (q - 1) d gmpy2.invert(e, phi) # 求e模phi的乘法逆元 # 解密 m pow(c, d, N) # 使用pow函数进行模幂运算更高效 print(f”解密后的整数m: {m}“) print(f”十六进制: {hex(m)}“) print(f”转换为字符串: {long_to_bytes(m).decode()}“)执行结果与Flag提取运行上述代码你会得到m0x33613559转换为ASCII字符串是”3a5Y“。根据题目描述这可能就是flag的一部分或者需要进一步处理如Base64解码、栅栏密码等。CTF中解密出的明文经常需要经过二次判断。实操心得第一反应遇到RSA题先把N丢到factordb.com试试。很多入门题就是考你这个。工具选择对于本地分解gmpy2是Python数论计算的事实标准速度远超纯Python实现。安装可能稍麻烦特别是Windows但绝对值得。long_to_bytesCrypto.Util.number中的这个函数是将解密后的大整数转换为字节串的利器能自动处理0x开头的十六进制和补零问题比手动hex(m)[2:]然后decode(‘hex’)更稳健。3.2 场景二利用素数弱点——Pollard‘s p-1算法当N很大比如1024比特无法直接暴力分解时我们需要寻找p或q的弱点。Pollard‘s p-1算法攻击的是这样一个场景p-1是一个光滑数B-smooth即p-1的所有素因子都不大于某个边界B。算法原理浅析算法的核心基于费马小定理。如果p是N的一个素因子且对于任意与p互质的整数a有a^(p-1) ≡ 1 (mod p)。 如果我们能计算出一个数M使得(p-1)整除M。那么根据费马小定理a^M ≡ 1 (mod p)。这意味着a^M - 1是p的倍数。 因此计算gcd(a^M - 1, N)结果有很大的概率就是p或者是N本身如果q-1也整除M。如何构造这样的M呢如果p-1是B-smooth的那么我们可以令M为所有小于等于B的素数幂的乘积。这样p-1的每个素因子及其幂次都包含在M中从而(p-1)整除M。Python实战实现我们假设p-1是光滑的但不知道边界B。可以采用迭代的方式让M依次为2!, 3!, 4!, ...直到成功分解。import gmpy2 from math import gcd import random def pollard_p_minus_1(N, max_B100000): ”“” 尝试使用Pollard‘s p-1算法分解N。 :param N: 待分解的合数 :param max_B: 光滑数边界B的最大尝试值 :return: N的一个非平凡因子若失败则返回None ”“” # 随机选择一个基数a通常取2 a 2 # 迭代计算M k! k从2开始递增 for k in range(2, max_B): a pow(a, k, N) # 计算 a^(k!) mod N 采用迭代方式避免大数计算a (a^(k-1)!)^k mod N # 计算 gcd(a-1, N) p gcd(a - 1, N) if p 1 and p N: print(f”在k{k}时成功分解“) return p elif p N: # 如果gcd等于N说明选的a或当前路径不好可以换一个a重试 print(f”在k{k}时gcd等于N尝试更换基数a“) a random.randint(3, N-2) # 避免选0,1,N-1 return None # 示例使用一个已知p-1光滑的N进行测试此处为示例实际N应很大 # 假设N p * q, 其中 p-1 有很多小因子 # 这里用一个小的例子演示原理 N_test 143 # 实际应使用CTF题目中很大的N result pollard_p_minus_1(N_test, max_B20) if result: print(f”找到因子: {result}“) print(f”另一个因子: {N_test // result}“) else: print(f”在max_B范围内未找到因子“)CTF真题思路还原以”2017 SECCON very smooth“为例这个题目的名字就是提示very smooth。给了一个HTTPS流量包从中提取出SSL证书证书里包含了RSA公钥(N, e)。N是1024比特直接分解几乎不可能。提取公钥用openssl或binwalk从pcap包中提取证书得到N和e。判断攻击方式题目名提示smooth指向p-1或p1光滑。使用primefac一个集成多种分解算法的Python库或自己实现上述算法进行尝试。实施攻击实际解题中发现使用Williams‘s p1算法针对p1光滑成功分解了N。这说明出题人构造的素数p满足p1是光滑数。构造私钥解密得到p和q后计算d生成私钥文件PEM格式。导入Wireshark将私钥导入Wireshark的SSL密钥列表解密TLS流量直接在HTTP流中看到包含flag的明文。注意事项算法效率Pollard‘s p-1算法在p-1确实光滑时非常快但如果p-1有一个稍大的素因子算法就会失效或需要极大的B。a的选择通常a2开始。如果遇到gcd(a^M-1, N) N说明算法走到了“坏”的情况可以尝试更换a如3, 5, 7...。与P1算法Williams‘s p1算法是类似的思路但针对p1光滑的情况。在CTF中如果p-1攻击无效可以尝试p1。primefac库内置了这两种算法。4. 实战二共模攻击——一把锁配多把钥匙的隐患共模攻击Common Modulus Attack是CTF中非常经典的场景。想象一下一扇门明文m用同一把锁芯模数N配了两把不同的钥匙公钥e1和e2来上锁加密得到了两个不同的锁具状态密文c1和c2。如果你同时拥有这两个锁具状态你有可能在不接触锁芯内部结构私钥d的情况下直接把门打开。4.1 攻击原理的数学推导攻击成立的条件是相同的模数N。两个公钥指数e1和e2互质即gcd(e1, e2) 1。设明文为m加密过程为c1 ≡ m^(e1) (mod N)c2 ≡ m^(e2) (mod N)攻击者已知N,e1,e2,c1,c2。因为e1和e2互质根据扩展欧几里得算法Extended Euclidean Algorithm一定存在两个整数s和t满足e1 * s e2 * t 1注意s和t中通常有一个是负数。假设s为负数我们可以将等式改写为e1 * (-s) e2 * t 1其中-s为正数。 那么原式即为e2 * t - e1 * s 1这里用s代表正数。现在我们来看密文c1^s ≡ (m^(e1))^s ≡ m^(e1 * s) (mod N)c2^t ≡ (m^(e2))^t ≡ m^(e2 * t) (mod N)由于s是负数c1^s在模运算中无法直接计算指数为负需要求模逆元。所以我们需要处理一下 因为c1 ≡ m^(e1) (mod N)且gcd(m, N)在RSA中一般为1m是明文通常与N互质所以c1在模N下存在逆元c1_inv。 那么c1^(-s) ≡ (c1_inv)^s (mod N)。最终我们将两个式子相乘(c1_inv)^s * c2^t ≡ m^(e2 * t - e1 * s) ≡ m^1 ≡ m (mod N)这样我们就绕过了私钥d直接利用c1,c2,e1,e2和N恢复出了明文m。4.2 Python代码实现与逐行解析理论可能有点绕但代码实现非常清晰。我们以一道经典例题的数据为例import gmpy2 from Crypto.Util.number import long_to_bytes # 题目数据相同的N不同的e和c N 6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249 e1 773 e2 839 c1 3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349 c2 5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535 # 第一步使用扩展欧几里得算法求 s 和 t使得 e1*s e2*t gcd(e1, e2) # gmpy2.gcdext(a, b) 返回 (g, s, t)其中 ggcd(a,b)且满足 a*s b*t g gcd, s, t gmpy2.gcdext(e1, e2) print(f”gcd(e1, e2) {gcd}“) print(f”s {s}, t {t}“) # 因为e1和e2互质所以gcd应为1。验证e1*s e2*t 是否等于1 assert e1 * s e2 * t gcd 1 # 第二步处理s或t为负数的情况 # 如果s为负我们需要计算 c1 的模逆元然后对 -s 次方 # 如果t为负我们需要计算 c2 的模逆元然后对 -t 次方 if s 0: # s为负计算 c1 模 N 的逆元 c1_inv gmpy2.invert(c1, N) # 将负指数转为正指数计算 part1 gmpy2.powmod(c1_inv, -s, N) # 计算 (c1_inv)^(-s) mod N part2 gmpy2.powmod(c2, t, N) # 计算 c2^t mod N else: # 此时t必然为负因为s为正和为1t必为负 c2_inv gmpy2.invert(c2, N) part1 gmpy2.powmod(c1, s, N) part2 gmpy2.powmod(c2_inv, -t, N) # 第三步恢复明文 m (part1 * part2) mod N m (part1 * part2) % N print(f”恢复的明文整数 m {m}“) # 第四步将整数m转换为可读字符串 # 这里得到的m是一个大整数需要转换为字节。通常有两种情况 # 1. m直接是ASCII码拼接的十进制数。 # 2. m的16进制表示对应字节。 # 我们先尝试直接转换为字节 try: flag_bytes long_to_bytes(m) print(f”直接转换字节: {flag_bytes}“) # 如果看起来像乱码可能m是ASCII码十进制拼接 # 例如 m10210897103...每2或3位数字对应一个ASCII字符 m_str str(m) flag_ascii ”“ i 0 while i len(m_str): # 如果以‘1’开头取3位因为ASCII 100-127是三位数 if m_str[i] ‘1’: char_code int(m_str[i:i3]) i 3 else: # 否则取2位ASCII 32-99是两位数 char_code int(m_str[i:i2]) i 2 flag_ascii chr(char_code) print(f”作为ASCII十进制拼接解析: {flag_ascii}“) except Exception as e: print(f”转换出错: {e}“) # 也可以尝试hex解码 hex_str hex(m)[2:] # 去掉‘0x‘前缀 if len(hex_str) % 2 ! 0: hex_str ‘0’ hex_str try: print(f”尝试Hex解码: {bytes.fromhex(hex_str).decode(‘utf-8’, errors‘ignore’)}“) except: print(“Hex解码失败”)代码执行与结果分析运行这段代码gcd结果为1确认e1和e2互质。计算出的s和t一正一负。程序会自动处理负数指数的情况。 最终计算出的m是一个很长的整数1021089710312311910410111011910111610410511010710511610511511211111511510598108101125。 直接long_to_bytes会得到乱码因为这里的m实际上是ASCII码的十进制数字直接拼接而成的字符串。例如102对应字符‘f’108对应‘l’97对应‘a’103对应‘g’。 按照代码中的解析逻辑三位数‘1xx’或两位数我们可以成功提取出flagflag{whenwethinkitispossible}。实操心得与避坑指南gmpy2.gcdext是关键这个函数一次性求出最大公约数和系数s、t比自己实现扩展欧几里得算法方便得多。负数指数的处理这是共模攻击代码中最容易出错的地方。一定要判断s和t的符号并对负指数项求其底数的模逆元再对正指数进行模幂运算。gmpy2.invert(a, N)用于求a模N的逆元。明文的编码解密得到整数m后如何将其变为flag字符串是最后一道关卡。常见的编码有直接转为字节long_to_bytes。整数是ASCII码十进制拼接如本题。整数是ASCII码十六进制拼接先hex(m)[2:]然后每两位一组转字符。Base64编码需要将整数先转为字节再解码。其他自定义编码。多尝试几种观察输出中是否有flag{、CTF{等常见格式。攻击的前提务必确认gcd(e1, e2) 1。如果不互质这个攻击方法无效。为什么现实中少见在真实的公钥基础设施PKI中每个用户都会生成自己独立的(p, q)对从而得到独一无二的N。共模攻击的场景通常只出现在CTF题目或极不规范的系统设计中。5. 工具链、调试技巧与进阶学习方向掌握了核心攻击原理和代码实现你已经有能力解决大部分基础的RSA CTF题目了。但要成为高手还需要顺手的工具和调试技巧。5.1 Python密码学与数学计算库推荐gmpy2/gmpy2-cffi这是最重要的库。它提供了GMPGNU多精度算术库的Python接口支持高速的大整数运算、模运算、数论函数如gcdext,invert,powmod,next_prime,is_prime等。几乎所有涉及大数的CTF密码学题目都离不开它。安装pip install gmpy2。如果安装失败可能需要从非官方whl文件或源码编译这是新手最大的门槛之一。pycryptodome/Crypto一个功能强大的密码学工具包。我们主要用它的Crypto.Util.number模块里面的long_to_bytes和bytes_to_long函数在整数和字节串之间转换非常方便。getPrime函数可以用来生成测试用的素数。sympy一个纯Python的符号数学库。它的factorint函数可以进行整数分解对于较小的数isprime用于素数测试还有很多解方程、求模逆的函数在探索思路时很有用。primefac一个集成了多种因数分解算法包括Pollard‘s p-1, Williams’s p1, ECM等的库。在遇到“光滑数”类题目时可以直接调用省去自己实现的麻烦。安装pip install primefac注意它依赖gmpy2。5.2 CTF解题中的通用调试技巧从小处着手验证逻辑在编写攻击脚本时先用自己生成的、小参数的RSA密钥进行测试。确保你的脚本能正确解密你自己加密的消息。这能快速排除代码逻辑错误。善用打印和断言在关键步骤后打印中间变量如计算出的p、q、phi、d、s、t等。使用assert语句验证条件如p*q N,e*d % phi 1让程序在出错时立刻停止而不是给出一个莫名其妙的结果。处理编码陷阱解密出整数m后如果直接转换不对思考可能的编码。写一个通用的尝试函数def try_decode(m_int): results [] # 1. 直接转bytes try: results.append((”bytes“, long_to_bytes(m_int).decode(‘utf-8’, errors‘ignore’))) except: pass # 2. 作为十进制ASCII拼接 s str(m_int) # ... 实现之前提到的2/3位分割逻辑 # 3. 作为十六进制ASCII拼接 hex_str hex(m_int)[2:] # ... 补零并尝试每两位分割 # 4. Base64 import base64 try: results.append((”base64“, base64.b64decode(long_to_bytes(m_int)).decode())) except: pass for fmt, val in results: if ‘flag’ in val.lower() or ‘ctf’ in val.lower(): print(f”Found in {fmt}: {val}“) return val return None利用在线工具辅助分解N首先访问 factordb.com 。对于不大的N它是神器。数论计算 wolframalpha.com 可以计算模逆、最大公约数等用于验证你的结果。编码转换 cyberchef 是一个万能的数据格式转换、编解码、加解密网站当你对明文的编码方式不确定时可以在这里手动尝试各种组合。5.3 从入门到精通其他常见RSA攻击模式简介掌握了分解和共模攻击你已经打开了RSA CTF的大门。门后的世界更广阔以下是一些进阶的攻击类型建议你以此为路线图继续深入学习低加密指数攻击e很小如e3如果e很小且明文m满足m^e N那么加密过程c m^e就没有起到模运算的作用直接对c开e次方根即可得到m。低解密指数攻击d很小Wiener攻击如果私钥d相对于N来说过小可以通过连分数展开的方法在多项式时间内恢复出d。这要求d (1/3) * N^(1/4)。模不互素如果两个不同的RSA公钥N1和N2共享一个素因子即gcd(N1, N2) ! 1那么直接计算最大公约数就能分解这两个N从而破解两个密钥。这在密钥生成器使用劣质随机数时可能发生。Coppersmith相关攻击这是一类非常强大的攻击用于在已知明文部分比特、或已知p或q的部分比特等情况下恢复出完整的密钥。它基于LLL格基约化算法是CTF中高难度RSA题的常客。选择密文攻击例如Bleichenbacher攻击针对PKCS#1 v1.5填充允许攻击者通过向服务器提交大量精心构造的密文并根据服务器的错误反馈如填充是否正确来逐步推算出明文。学习这些攻击最好的方式依然是找到对应的CTF题目在BUUOJ、CTFHub、攻防世界等平台有很多分类题库理解原理后自己动手用Python实现一遍。密码学的魅力在于看似坚不可摧的数学堡垒往往因为一个细微的实现疏忽或参数选择不当而土崩瓦解。而CTF正是寻找和利用这些疏忽的绝佳战场。