前阵子查Oracle调优文档看到一句“禁止对大表使用 broadcast”还以为是性能优化技巧。结果在攻防世界的CRYPTO区翻题翻到一道名字一模一样的Broadcast下载附件一看三个大n、三个大c、一个e3这才反应过来此broadcast非彼broadcast——数据库的broadcast是大表广播提示而CTF里的这道Broadcast是经典的RSA广播攻击RSA Broadcast Attack也叫Håstad广播攻击。这道题在攻防世界的Crypto分类里属于“看完原理就秒懂”的典型。只要你清楚RSA的加密过程、会写两行Python、知道中国剩余定理基本十分钟就能拿flag。但它也很有意思题目描述极简附件里就几个数字没有任何提示很多人拿到手会先想着去分解n或者怀疑是共模攻击结果绕一大圈。这篇文章我就把这道题的完整思路、推导过程和实战代码写清楚顺便聊聊我踩过的几个坑以及广播攻击在变体场景下还能怎么玩。1. 先看题为什么叫Broadcast以及它想考什么1.1 附件内容长什么样攻防世界这道Broadcast下载下来通常是一个文本文件内容结构非常朴实三个公钥模数n1、n2、n3以及三段对应的密文c1、c2、c3再加一个显眼的公钥指数e3。数据是几百位的大十进制数没有给私钥没有给p和q也没有给任何函数名提示整道题就这几个数字。我当时的第一反应是这不是逗我吧三个n三个c想让我分解哪个试着把n丢进factordb发现有的n确实能分解但是分解完要干嘛p和q拿下来算φ(n)、求私钥d再解密c1这条路不是走不通但非常绕而且你得同时分解三个模数还要祈祷每个都能成功分解。事实上这道题的考点根本不在这里。把e3、三组密文、三组模数这三个条件放在一起答案就呼之欲出了同一个明文m分别用三个不同的RSA公钥加密且加密指数都是3。题目叫Broadcast意思是“广播”——发送方把同一条消息广播给三个不同的接收方每个接收方有自己的公钥(n_i, 3)。结果攻击者截获了三份密文不需要私钥也能恢复出原始明文。这里有一个很关键的前提三个模数必须两两互素否则CRT没法直接用这道题里三个n显然互素否则题目会引导你去求GCD做素数共享分解。所以想都不用想先把GCD检验放一边直接走广播攻击的流程。1.2 快速判断攻击面RSA题的第一反应不能是硬算做RSA相关的CTF题最忌讳的就是拿到题就开始暴力。我的习惯是先列一个特征表把所有已知条件摆出来再对照经典攻击类型题目特征大概率攻击方向多个不同n、多个c、同一个e且e很小广播攻击Håstad广播攻击同一个n、多个互素的e、对应多个c共模攻击两个n的公因子不是1共享素数分解直接GCD单个n、单个c、e3且c很小低加密指数直接开根同一个e和n多条相关明文Franklin-Reiter相关消息攻击把表一套就很清楚Broadcast这题的特征落在第一行。多个模数、多个密文、同一个e3而且密文数量正好和e相等这就是教科书级的广播攻击。为什么“密文数量正好和e相等”这么重要下面这部分是整道题的数学核心也是你写脚本时必须真正理解的原理。2. 广播攻击的数学原理三次模运算如何拼出原明文2.1 e3意味着什么RSA加密公式是c m^e mod n。在Broadcast这道题里发送方做了三次加密c1 m^3 mod n1c2 m^3 mod n2c3 m^3 mod n3注意所有等式左边都是同一个m因为广播的就是同一条消息。而m是作为明文被加密的RSA要求明文整数必须小于模数所以m一定小于n1、n2、n3中的每一个也就是说m min(n1, n2, n3)。于是可以得到一个重要的大小关系m^3 min(n)^3而n1 * n2 * n3远大于min(n)^3因为另外两个模数都比min(n)大且互素所以m^3 n1 * n2 * n3。这句话看起来平平无奇但是整个攻击成立的基石。如果m^3比三个模数的乘积还大那下面CRT合并出来的结果就只是m^3的一个模N的余数而不是m^3本身直接开根就会得到错误结果。2.2 中国剩余定理把三个方程压成一个现在我们有三个同余方程但模数各不相同。想直接开立方根最好能把三个方程合并成一个让右边变成同一个模数N并且让左边仍然是m^3的完整值而不是带模运算的余数。中国剩余定理CRT干的正是这件事。只要模数两两互素给定一组同余x ≡ a1 (mod n1)x ≡ a2 (mod n2)x ≡ a3 (mod n3)就可以在模N n1 * n2 * n3下求出唯一解x。放到我们的场景里a1、a2、a3就是c1、c2、c3x就是m^3。因为x满足x ≡ c1 ≡ m^3 (mod n1)x ≡ c2 ≡ m^3 (mod n2)x ≡ c3 ≡ m^3 (mod n3)由中国剩余定理x在模n1n2n3下有唯一解。也就是说x和m^3在模N下同余。再加上2.1里说过的m^3 N这个“模N下同余”就直接变成了“相等”。于是x就是m^3开三次方根就得到m。CRT的具体构造是通用的。设N n1 * n2 * n3然后对每个方程计算部分解M_i N / n_i再求M_i在模n_i下的逆元t_i那么x (a1 * M1 * t1 a2 * M2 * t2 a3 * M3 * t3) mod N。放在代码里就是几行循环的事后面我会给出实现。2.3 为什么开三次方根就能出flag因为合并出来的x就是m^3所以对x精确开三次方根得到m。m是整数明文再转换成字节串大概率会看到flag{...}。这里有一个需要留意的边界条件如果m^3恰好等于N的整数倍再加一点点那x和m^3虽然相等但取模后没问题如果m^3大于N那CRT求出的x只是m^3 mod N开根就gg了。所以实战中我先用m min(n)这个条件做预估再开根后做个二次验证如果开出来的根再立方后不等于x就说明数据有错。为了验证这套原理我写代码前先用小数字手推过一遍。模拟三个模数n133、n235、n334它们两两互素明文m7e3c1 7^3 mod 33 13c2 7^3 mod 35 28c3 7^3 mod 34 3用CRT合并N39270算出来的x恰好是343而343就是7^3直接开三次方根得到7。整个过程非常清爽也说明了这个攻击不需要任何私钥信息只需要三个公钥和对应密文。3. 完整解题代码CRT合并、开立方根、转flag3.1 环境准备与库的选择这道题的代码量其实很小核心就两个函数CRT合并、大整数开立方根。环境上我建议用Python 3.8以上版本因为Python 3.8开始内置的pow函数支持负指数求模逆元也就是pow(a, -1, m)这样我们连gmpy2的invert都不用写代码干净不少。大整数开根建议用gmpy2.iroot。它是专门处理大整数的整数开n次方函数返回二元组(root, exact)root是精确的整数根exact是布尔值表示是否开尽了。如果是小数字Python的math.isclose加浮点开根也能糊弄但遇到几百位的大整数浮点精度完全没法看必须用整数级算法。安装依赖只需要一条命令pip install gmpy2如果你实在不想装第三方库也可以用二分法手动写一个整数开立方根几行就能搞定但没必要折腾这个gmpy2在CTF环境里基本是标配。3.2 CRT与开根实现细节CRT的代码逻辑完全按照数学定义来。我写的时候特意把模数列表和余数列表分开传参因为后面可能扩展成5组、7组数据接口好复用def crt(remainders, moduli): N 1 for n in moduli: N * n x 0 for c, n in zip(remainders, moduli): Mi N // n inv pow(Mi, -1, n) # Python 3.8 x c * Mi * inv return x % N这里要注意pow(Mi, -1, n)只有在Python 3.8以上才支持。如果你还在用老版本换成gmpy2.invert也可以from gmpy2 import invert inv invert(Mi, n)整个CRT的流程就是累加每一项“余数乘以部分模数乘以逆元”最后统一取模。你可能会问为什么不每步都取模实际代码里x会变得非常大但Python的大整数完全扛得住最后模一次就行当然你每步取模也完全没问题看个人习惯。开立方根就更简单from gmpy2 import iroot m_cubed crt(c_list, n_list) m, exact iroot(m_cubed, 3)如果exact为False说明m_cubed不是完全立方数那就是前面的条件出了问题需要回头检查数据配对和格式。3.3 完整脚本与运行结果把上面的函数拼起来针对攻防世界这道题完整脚本长得像这样from gmpy2 import iroot def crt(remainders, moduli): N 1 for n in moduli: N * n x 0 for c, n in zip(remainders, moduli): Mi N // n inv pow(Mi, -1, n) x c * Mi * inv return x % N # 题目附件中的数据以十进制整数形式填入 n_list [ int(这里填n1), int(这里填n2), int(这里填n3), ] c_list [ int(这里填c1), int(这里填c2), int(这里填c3), ] m_cubed crt(c_list, n_list) m, exact iroot(m_cubed, 3) if exact: flag m.to_bytes((m.bit_length() 7) // 8, big) print(flag) else: print(开根失败请检查数据)如果一切正常运行后输出就是一串字节bflag{...}然后把b前缀去掉提交就行。如果题目给的数据是十六进制那么填入时就要转换n_list [int(..., 16), int(..., 16), int(..., 16)]这个判断很关键因为很多人第一步就栽在进制上。3.4 用Sage也能更快如果你装了SageMath这道题的代码会短得离谱from sage.all import CRT, Integer M CRT(c_list, n_list) m Integer(M).nth_root(3) print(bytes.fromhex(hex(m)[2:]))Sage自带CRT函数和Integer.nth_root方法连手动实现都省了。不过CTF比赛环境不一定有SagePython脚本的通用性更强所以我个人拿这道题教别人的时候都是先用Python讲原理再顺手提一嘴Sage的写法。4. 跑题过程中最容易踩的四个坑4.1 密文与模数的配对顺序这个坑看起来蠢实际上特别容易犯。攻防世界的附件有时候会按“n1、c1、n2、c2、n3、c3”的顺序排但也有可能把三个n先全部列完再列三个c甚至混着排。我见过有人读文件时把c_list和n_list的顺序搞反了导致CRT算出来的值根本不对开根结果自然是一堆乱码。解决办法很简单在读数据的时候不要只读数字要保留它们前面的标签。比如解析成字典data {} for line in open(data.txt): key, val line.strip().split() data[key.strip()] int(val.strip())然后按n1、n2、n3和c1、c2、c3分别取值组列表。这样绝对不会错位。4.2 数据格式解析十进制、十六进制还是Base64攻防世界这题通常给的是十进制但其他平台的同类题目不一定。有的直接把数字写成十六进制字符串有的前缀带0x还有的用BASE64编码密文。我的判断顺序是如果字符串里出现a-f或前缀0x先按十六进制解析如果字符串以base64常见字符集结尾带先考虑base64解码再转整数如果全是0-9那大概率是十进制直接int处理。这里有个小技巧用int(string, 0)可以自动识别0x前缀但对不带前缀的纯十六进制字符串没辙。所以最稳妥的还是先人工看一眼文件开头判断一下数据特征再选择进制。4.3 开了根之后怎么变成flag很多人卡在最后一步m已经算出来了是个几百位的大整数怎么变成flag常规做法是把整数转字节。Python的int对象有一个to_bytes方法需要指定字节长度。一个快速算法是byte_len (m.bit_length() 7) // 8 flag_bytes m.to_bytes(byte_len, big)big表示大端字节序RSA的整数转字节通常都用big。如果你发现转出来的结果前面有几个不可见字符也不要慌可能是无符号填充之类的历史包袱这道题一般直接就是可见的ASCII打印出来就是flag。如果题目给的flag是十六进制字符串形式那就用bytes.fromhex(hex(m)[2:])效果一样。4.4 别急着找n的分解再强调一遍这道题的核心不是分解模数。虽然三个n里面很可能有能分解的但分解不是出题人的本意。你哪怕把三个n全部分解成功得到p、q、d再解密那也是绕远路而且还可能因为e的选取、密文格式等问题解出乱码。我把话放这儿在RSA题目里看到三个n和三个c第一时间就该怀疑广播攻击如果你还在第一反应去factordb分解说明脑子里还没有建立起攻击类型和题目特征之间的映射表。做CTF识别题型的速度和解题的速度一样重要。5. 广播攻击的变体、关联攻击与现实防御5.1 e更大怎么办广播攻击不只在e3时成立。只要同一明文被加密的次数k满足k e并且m^e n1n2...*nk那么CRT合并后开e次方根就能恢复明文。比如e5时需要至少5组加密数据e7时需要7组。题目要是给你5个n、5个c、e5框架脚本完全不用改把列表长度从3换成5开根次数从3换成5就行。但要注意密文组数刚好等于e是最理想的情况。如果组数少于e这种情况就退化到需要Coppersmith方法求解小根问题本质上是解一个更高次的多项式方程。不过CTF里出现的一般都是组数刚好够用不需要上那么复杂的工具。5.2 有padding后还能不能打简单说如果发送方在加密前给明文加了随机填充比如OAEP或者PKCS#1 v1.5那么即使明文内容一样填充后得到的m数值也不一样这三个m在数值上不再相等广播攻击的方程组就建立不起来了。学术界有个Håstad广播攻击的带填充变体思路是把填充看成某种函数然后在多项式的层次上利用Coppersmith恢复明文但那是高级玩法需要格基也行、需要代数技巧也行不适合新手一上来就啃。攻防世界这道题之所以经典就是因为它用无填充的原始RSA把广播攻击的最小可行模型完整地展示了出来。5.3 现实中怎么防这类攻击现实世界里的RSA通信很少会被广播攻击直接打穿原因有两个第一现代系统普遍使用e65537作为公钥指数。如果e65537广播攻击至少需要65537组同一明文的加密结果这在现实中几乎不可能凑齐直接让攻击失去可行性。第二加密前基本都有随机填充同样的明文经过OAEP填充后得到的是完全不同的加密中间值。但这两条并不代表广播攻击没有意义。在脆弱的协议设计里如果大家图省事用e3又不对消息做随机化处理然后把同一条消息发给多个接收者这个漏洞链就成立了。防御要点总结起来就三条用大公钥指数、用标准随机填充、避免对同一明文做无随机化的多路分发。最后再分享一个题外话。如果你是被Oracle优化那波热搜带进来的那这篇可能跟你预期的不太一样但至少你现在分清了数据库优化里的broadcast提示和攻防世界Crypto区的Broadcast只是同名不同命。后者考的是数学是RSA里一个看起来不起眼却能要命的组合条件。下次在CTF里看到多个n、多个c、同一个e别犹豫先把广播攻击的脚本甩上去再说。