企业官网建设流程全解析

前阵子查Oracle调优文档，看到一句“禁止对大表使用 broadcast”，还以为是性能优化技巧。结果在攻防世界的CRYPTO区翻题，翻到一道名字一模一样的Broadcast，下载附件一看，三个大n、三个大c、一个e=3，这才反应过来，此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，再加一个显眼的公钥指数e=3。数据是几百位的大十进制数，没有给私钥，没有给p和q，也没有给任何函数名提示，整道题就这几个数字。

我当时的第一反应是：这不是逗我吧，三个n三个c，想让我分解哪个？试着把n丢进factordb，发现有的n确实能分解，但是分解完要干嘛？p和q拿下来算φ(n)、求私钥d，再解密c1？这条路不是走不通，但非常绕，而且你得同时分解三个模数，还要祈祷每个都能成功分解。事实上这道题的考点根本不在这里。

把e=3、三组密文、三组模数这三个条件放在一起，答案就呼之欲出了：同一个明文m，分别用三个不同的RSA公钥加密，且加密指数都是3。题目叫Broadcast，意思是“广播”——发送方把同一条消息广播给三个不同的接收方，每个接收方有自己的公钥(n_i, 3)。结果攻击者截获了三份密文，不需要私钥也能恢复出原始明文。

这里有一个很关键的前提：三个模数必须两两互素，否则CRT没法直接用；这道题里三个n显然互素，否则题目会引导你去求GCD做素数共享分解。所以想都不用想，先把GCD检验放一边，直接走广播攻击的流程。

1.2 快速判断攻击面：RSA题的第一反应不能是硬算

做RSA相关的CTF题，最忌讳的就是拿到题就开始暴力。我的习惯是先列一个特征表，把所有已知条件摆出来，再对照经典攻击类型：

把表一套就很清楚：Broadcast这题的特征落在第一行。多个模数、多个密文、同一个e=3，而且密文数量正好和e相等，这就是教科书级的广播攻击。

为什么“密文数量正好和e相等”这么重要？下面这部分是整道题的数学核心，也是你写脚本时必须真正理解的原理。

2. 广播攻击的数学原理：三次模运算如何拼出原明文

2.1 e=3意味着什么

RSA加密公式是c = m^e mod n。在Broadcast这道题里，发送方做了三次加密：

• c1 = m^3 mod n1
• c2 = m^3 mod n2
• c3 = 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、c3，x就是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，就说明数据有错。

为了验证这套原理，我写代码前先用小数字手推过一遍。模拟三个模数n1=33、n2=35、n3=34，它们两两互素，明文m=7，e=3：

• c1 = 7^3 mod 33 = 13
• c2 = 7^3 mod 35 = 28
• c3 = 7^3 mod 34 = 3

用CRT合并，N=39270，算出来的x恰好是343，而343就是7^3，直接开三次方根得到7。整个过程非常清爽，也说明了这个攻击不需要任何私钥信息，只需要三个公钥和对应密文。

3. 完整解题代码：CRT合并、开立方根、转flag

3.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("开根失败，请检查数据")

如果一切正常，运行后输出就是一串字节：

b'flag{...}'

然后把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比赛环境不一定有Sage，Python脚本的通用性更强，所以我个人拿这道题教别人的时候都是先用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更大怎么办

广播攻击不只在e=3时成立。只要同一明文被加密的次数k满足k >= e，并且m^e < n1n2...*nk，那么CRT合并后开e次方根就能恢复明文。

比如e=5时，需要至少5组加密数据；e=7时需要7组。题目要是给你5个n、5个c、e=5，框架脚本完全不用改，把列表长度从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通信很少会被广播攻击直接打穿，原因有两个：

第一，现代系统普遍使用e=65537作为公钥指数。如果e=65537，广播攻击至少需要65537组同一明文的加密结果，这在现实中几乎不可能凑齐，直接让攻击失去可行性。第二，加密前基本都有随机填充，同样的明文经过OAEP填充后，得到的是完全不同的加密中间值。

但这两条并不代表广播攻击没有意义。在脆弱的协议设计里，如果大家图省事用e=3，又不对消息做随机化处理，然后把同一条消息发给多个接收者，这个漏洞链就成立了。防御要点总结起来就三条：用大公钥指数、用标准随机填充、避免对同一明文做无随机化的多路分发。

最后再分享一个题外话。如果你是被Oracle优化那波热搜带进来的，那这篇可能跟你预期的不太一样，但至少你现在分清了：数据库优化里的broadcast提示，和攻防世界Crypto区的Broadcast，只是同名不同命。后者考的是数学，是RSA里一个看起来不起眼却能要命的组合条件。下次在CTF里看到多个n、多个c、同一个e，别犹豫，先把广播攻击的脚本甩上去再说。