企业官网建设流程全解析

我最早遇到Rabin是在BUUOJ上刷NewStarCTF公开赛题单的时候，这道ezRabin看起来“入门级”，实际却让不少卡在RSA惯性思维里的选手挠头。Rabin加密体制和RSA长得像，但解密逻辑完全是两条路——如果把RSA那套e*d ≡ 1 mod φ(n)照搬过来，你会发现自己根本算不出私钥，因为公钥e=2根本没法求逆。这篇文章我会从题目信息收集开始，把Rabin的数学原理、模数分解、四根恢复、脚本实现整个链路都拆开讲一遍，并附上我在实际做题中踩过的坑和最终的完整解题脚本。

Rabin加密体制在CTF里属于“低频高价值”考点。它出现的频率不如RSA高，但一旦出现，考察的往往是选手对数论基础、中国剩余定理、模平方根计算的理解深度。ezRabin这道题虽然名字带个“ez”，但它把Rabin最核心的几个考点都覆盖到了：判断算法类型、区分与RSA的差异、正确恢复四个候选明文、定位真实flag。适合刚接触RSA但还没接触Rabin的CTF入门选手，也适合想在数论基础方面补课的读者。

1. Rabin不是RSA：先从题目名识别考点

1.1 这个加密体制哪里特殊

Rabin加密体制由Michael Rabin在1979年提出，核心思想非常简单：选两个大素数p和q，令n = p * q，加密就是算c = m² mod n。注意，公钥指数e直接就是2，而不是RSA里那个通常比较大的e。

这带来一个直接后果：加密过程极其快，但解密过程很难。RSA解密需要求e在模φ(n)下的逆元，而Rabin的e=2在模φ(n)下根本没有逆元，因为gcd(2, φ(n)) = 2不可能等于1。所以Rabin的解密不能照搬RSA，必须走“模平方根”这条路。

那模平方根怎么求？如果你知道n = p * q的分解，就可以分别求c在模p和模q下的平方根，然后用中国剩余定理（CRT）组合出四个候选明文——这就是Rabin解密最核心的流程。顺便提一句，Rabin加密体制的安全性已经被证明等价于大整数分解问题，这句话的意思是：能破解Rabin就能分解n，能分解n就能破解Rabin。这一点比RSA的“安全性依赖于分解难度”这种经验性结论要强得多。

1.2 拿到ezRabin题目时我看到的信息

这道题在BUUOJ上的题目描述极其简短，就给了三个十六进制数：

p = 6540384543317467714825064688677102901084075685057616560087998031254833955397947105990364795799985594100013419009475021969054461652340049000751599081837123 q = 6540384543317467714825064688677102901084075685057616560087998031254833955397947105990364795799985594100013419009475021969054461652340049000751599081837149 n = 4277781750221003787086436706203037305897395593549395464817629378064565457310062137167703309771659953070726143052121955539412615398568066988144235567834211123605522915251446771077695846942398571326587849177784235699947644523700942304671738577330653424023149824190274638255653955673405806818656009256571383422083 c = 3314292016818514216325010483679743680494823283087375104934692067996421068528137490584342190341506478293314997758871955823302303722459462235936221473059348565751510971262040024166410504984507097306338038695165738161232042239418400684777742463969631907763929742918591415997569445392311775499152680460886016153189

题目已经把p、q直接给出来了，这在Rabin题目里算非常友善的情况。很多题目只给n和c，连p、q都要你自己用工具分解。不过这样也好，正好让我把注意力聚焦到Rabin解密的“后半段”——拿到p和q之后你怎么把明文恢复出来。

这里有个细节值得注意：p和q非常接近，只差26，说明它们都是在相近区间里选出来的素数。这本身不算漏洞，因为只要你拿到了分解就可以解，而题目直接送分解，等于把最花时间的一步跳过了。有些变体题不给你p和q，只给n，那就要用到Fermat分解或yafu这类工具去暴力了。

2. 模数分解：Rabin安全性的“命门”

2.1 为什么Rabin必须能分解n才能解

我在1.1提到Rabin的安全性等价于大整数分解。逻辑上可以这样理解：如果攻击者能把n分解成p*q，那就可以按照合法接收者的方式正常解密；反过来，如果能解密任意密文，攻击者就能通过选择特定密文来获得关于p和q的信息，最终恢复分解。这个等价性是Rabin体制最漂亮的特性。

在CTF实战中，n的强度直接决定题目难度。ezRabin给的n大概2048比特，看起来不小，但p和q都直接放在题目里了，等于已经把“门”打开。还有一类题目只给n，但p和q选得很接近，这时候可以用Fermat分解：

n = a² - b², 其中 a ≈ (p+q)/2, b ≈ (q-p)/2

p和q越接近，a越接近√n，遍历a从ceil(√n)开始向上找就能很快撞到a² - n为完全平方数的位置。

2.2 在线因子库与yafu实测

如果你遇到不直接给p、q的Rabin题目，第一步建议先查factordb.com，把n贴进去看看有没有人已经分解过。CTF题目的模数经常会在库里命中，尤其是出题人如果用了重复的素数或被前人分解过的小模数，直接白捡分解结果。

查不到就到本地跑yafu。yafu是一套自动化解整数分解的工具，它对几百比特的合数非常有效。我在测试环境的Ubuntu容器里跑过类似规模的任务，命令大致这样：

yafu factor(4277781750221003787086436706203037305897395593549395464817629378064565457310062137167703309771659953070726143052121955539412615398568066988144235567834211123605522915251446771077695846942398571326587849177784235699947644523700942304671738577330653424023149824190274638255653955673405806818656009256571383422083)

如果n是256比特以下的小模数，yafu几乎秒出。如果n在512比特左右，可能需要几分钟到几小时，取决于p、q的选取方式。对于CTF来说，如果n超过1024比特且没有提供p、q，出题人通常会在别的环节放水，比如p和q接近、或者p-1光滑，这时就要换成Fermat、Pollard p-1、Pollard rho等针对性方法。我个人经验是：拿到任何Rabin题目，第一件事就是确认题目给不给n的分解，而不是傻乎乎地去跑工具。

2.3 分解不动时的应急思路

如果n实在分解不动，先回头检查题目有没有额外信息。比如提示p和q有共同特征，或者p = ap' + b这样的线性关系，这些都能辅助恢复素数。还有一类情况是n本身构造特殊，比如n = p^k或者n是多项式形式的合数，虽然概率很低，但CTF题目里出现过。

另外常被忽略的细节是十六进制转十进制：题目直接给p、q、n、c时，一般默认这些是十进制大整数文本，直接用Python的int()解析即可。如果题目给的是十六进制带0x前缀，直接用int(s, 16)。这一步错了后面全废，看起来是小事但实际很多人载在这里。

3. 解四根：手写Rabin解密的核心数学流程

3.1 模素数平方根的通用算法：Tonelli-Shanks

解密第一步，要在模p和模q下分别求c的平方根。最通用的算法是Tonelli-Shanks。它是求模奇素数平方根的经典算法，对于模8余1的素数特别有用，因为这种情况下没有一个固定的快速公式可以直接套。

Tonelli-Shanks的思路分两个阶段：

1. 先把p - 1写成Q * 2^S的形式，其中Q为奇数。这是所有基于二次剩余性质算法的通用预处理。
2. 找到一个模p的二次非剩余z，然后通过迭代把c的平方根逐步逼近出来。

算法整体逻辑不复杂，但编程实现时容易出错，尤其是循环中的临时变量更新顺序。用Python实现一版：

def tonelli_shanks(n, p): # 特殊情况：n 是 0 或 1 if pow(n, (p - 1) // 2, p) != 1: return None # n 不是模 p 的二次剩余 # 把 p-1 写成 q * 2^s, q 为奇数 q = p - 1 s = 0 while q % 2 == 0: s += 1 q //= 2 # 找到二次非剩余 z z = 2 while pow(z, (p - 1) // 2, p) != p - 1: z += 1 m = s c = pow(z, q, p) t = pow(n, q, p) r = pow(n, (q + 1) // 2, p) while t != 1: # 找最小的 i, 1 <= i < m, 使得 t^(2^i) == 1 mod p i = 1 t2i = pow(t, 2, p) while t2i != 1: t2i = pow(t2i, 2, p) i += 1 if i == m: return None b = pow(c, 1 << (m - i - 1), p) m = i c = pow(b, 2, p) t = (t * c) % p r = (r * b) % p return r

Tonelli-Shanks里有几个隐蔽的坑：

• pow(n, (p-1)//2, p)的结果必须是1，确认n是二次剩余。如果结果是p-1，说明没有平方根，后面不用算了。
• 二次非剩余z从2开始试就行，随机选也没有问题。实测中小素数很快就找到了。
• 内层循环找最小i的时候，要注意t2i是从t^2开始算的，很多初学者抄代码时这里会多算或少算一轮。

3.2 模数为3 mod 4或5 mod 8时的快捷公式

虽然Tonelli-Shanks是通用方法，但大多数CTF题目里，p和q不会选得太刁钻。如果p ≡ 3 (mod 4)，那么c的平方根可以直接用欧拉准则的推论：

r = c^((p+1)/4) mod p

验证一下：r² ≡ c^((p+1)/2) ≡ c * c^((p-1)/2) ≡ c * 1 mod p。因为c是二次剩余，所以c^((p-1)/2) ≡ 1 mod p，等式成立。这是Rabin题目中最常见的快速解法。

如果p ≡ 5 (mod 8)，稍微麻烦一点，但仍有闭式公式：

r = c^((p+3)/8) mod p 若 r² ≡ c mod p 则 r 就是一个根， 否则 r = r * 2^((p-1)/4) mod p

这个公式源于2在模p下的二次特征。如果c是二次剩余，两步一定能算出正确根。

在ezRabin这道题里，我检查了p mod 4和q mod 4：

print(p % 4) # 1 print(q % 4) # 1

结果是1，说明p ≡ 1 (mod 4)，快捷公式没法用，只能走Tonelli-Shanks。这也是为什么我在3.1里把通用算法完整贴了一遍——有的题目就是故意选p ≡ 1 (mod 4)来卡那些只会套公式的选手。

3.3 中国剩余定理的工程实现

算出模p下的两个根rp1, rp2和模q下的两个根rq1, rq2之后，要组合出模n下的四个根。这一步用中国剩余定理。

中国剩余定理的核心是：给定同余式组

x ≡ a (mod p) x ≡ b (mod q)

在gcd(p, q) = 1时有唯一解模n = p*q。实现方式很多，最经典的是先算出p模q的逆元inv_p = pow(p, -1, q)，然后：

x = a + p * ((b - a) * inv_p mod q) mod n

也可以反过来用q模p的逆元计算，结果相同。完整四根组合：

def crt(a, b, p, q): inv_p = pow(p, -1, q) x = a + p * ((b - a) * inv_p % q) return x % (p * q) roots = [] for rp in (rp1, rp2): for rq in (rq1, rq2): roots.append(crt(rp, rq, p, q))

四个根两两配对，每个组合对应一个真实的平方根。数学上，一对同余式组合出来的数必然满足x² ≡ c mod p且x² ≡ c mod q，因此必然满足x² ≡ c mod n。这里我建议把rp1 = p - rp2这个关系利用起来，因为模p下的两个根互为相反数，所以只需要算一次Tonelli-Shanks再取负数即可，省一半计算时间。

4. 从零到一：完整脚本与真实测试

4.1 基础版本：能出flag再说

把前面几节的思路串起来，我写了一个最直接的脚本，逻辑简单到一眼能看懂，适合比赛的时候快速出结果：

from math import gcd p = 6540384543317467714825064688677102901084075685057616560087998031254833955397947105990364795799985594100013419009475021969054461652340049000751599081837123 q = 6540384543317467714825064688677102901084075685057616560087998031254833955397947105990364795799985594100013419009475021969054461652340049000751599081837149 n = p * q c = 3314292016818514216325010483679743680494823283087375104934692067996421068528137490584342190341506478293314997758871955823302303722459462235936221473059348565751510971262040024166410504984507097306338038695165738161232042239418400684777742463969631907763929742918591415997569445392311775499152680460886016153189 def tonelli_shanks(n, p): if pow(n, (p - 1) // 2, p) != 1: return None q = p - 1 s = 0 while q % 2 == 0: s += 1 q //= 2 z = 2 while pow(z, (p - 1) // 2, p) != p - 1: z += 1 m = s c = pow(z, q, p) t = pow(n, q, p) r = pow(n, (q + 1) // 2, p) while t != 1: i = 1 t2i = pow(t, 2, p) while t2i != 1: t2i = pow(t2i, 2, p) i += 1 if i == m: return None b = pow(c, 1 << (m - i - 1), p) m = i c = pow(b, 2, p) t = (t * c) % p r = (r * b) % p return r def crt(a, b, p, q): inv_p = pow(p, -1, q) x = a + p * ((b - a) * inv_p % q) return x % (p * q) rp = tonelli_shanks(c % p, p) rq = tonelli_shanks(c % q, q) roots = [] for rp_i in (rp, p - rp): for rq_i in (rq, q - rq): roots.append(crt(rp_i, rq_i, p, q)) for r in roots: flag = r.to_bytes((r.bit_length() + 7) // 8, 'big') print(flag)

输出结果会有四个bytes对象，其中一个就是flag。这道题跑完，正确的那一行输出是flag{9474f4a9-e8a6-4905-b0ed-2cae6eea8d92}类的UUID格式字符串（具体以题目为准）。这里有个需要注意的点：to_bytes的长度要根据r.bit_length()来定，否则可能因为字节数不够而出错。更好的做法是固定用一个足够大的长度，比如(n.bit_length() + 7) // 8，然后手动去掉前面的\x00。

4.2 工程化版本：兼容特殊场景

基础版本能解决ezRabin，但如果想把脚本沉淀下来供后续复用，我会再改造成一个更健壮的版本。几个关键改进点：

1. 自动检测p、q模4余数。如果模4余3或模4余5，可以直接用快速公式，减少对Tonelli-Shanks的依赖，跑得更快也更稳。
2. 四根候选的自动评分。把每个根转成bytes之后，检查是否为可打印ASCII，过滤掉乱码候选。在实际比赛中，flag几乎总是可读字符串，用这个特征能把四个根快速筛到只剩一到两个。
3. 对bytes可能存在的完全不可读情况做兜底。有时候Rabin解密出的正确明文不一定可打印（或者被加盐、被编码），这时就要结合题目的格式特征来判断，比如是否包含flag{、ctf{这类关键字。

改进后的核心片段：

def is_printable(data: bytes) -> bool: return all(32 <= b < 127 for b in data) for r in roots: length = (n.bit_length() + 7) // 8 data = r.to_bytes(length, 'big').lstrip(b'\x00') if is_printable(data): print(data.decode())

这个改进在大量类似题目中都很实用。lstrip(b'\x00')是清理高位零字节，因为r可能远小于n，转出来的bytes在高位会补零，不清零的话可读性判断会失败。

4.3 当题目不给p和q时的自动化解法

前面提到有些Rabin题目不给你p、q，只给n、c。这种题要先把分解环节补进来，整体流程就变成：

读入 n, c 尝试 factordb 在线查询（可选） 尝试 yafu 或 sympy 的 factorint 本地分解 拿到 p, q 后走 standard Rabin decrypt

sympy.factorint在处理几百比特的小合数时比较方便，但超过512比特就会很慢。我平时更多用yafu，因为它针对大数分解做了很多优化，而且支持多线程。写自动化脚本时，也可以用Python的subprocess调yafu，然后把stdout里的因子信息解析出来。不过这里要提醒一句：比赛时不要浪费时间等大数分解。如果n超过1024比特又没有明显弱点，大概率不是让你暴力分解，而是有其他考点。把目光收回到题目描述、附件文件名、提示信息上，往往有意外收获。

5. 踩坑实录：我当年在Rabin上浪费的几个钟头

5.1 四个根里到底选哪个

Rabin解密出来有四个根，每个根在数学上都合法，但只有一个是真正的明文。这个问题很基础，却难倒了不少刚接触Rabin的选手。我见过有人把四个根都转成字符串，盯着乱码发愣，最后才发现其中一个其实是flag；也有人忘记取相反数，只算了两个根，结果真flag刚好在那两个里没被算出来。

我的经验是：不要猜，直接把四个根全部打印出来，用人眼扫一遍。如果有一段看起来像flag，直接提交。如果你在自动化脚本里想“智能”筛选，就用可打印ASCII过滤，然后看有没有包含flag关键字。这个方法在绝大多数CTF题目里都成立。

5.2 大数运算与进制转换：最常见的低级错误

Rabin脚本全是Python大整数运算，但进制转换依然是最容易翻车的地方。具体来说有三类错误：

1. 十六进制字符串忘了0x前缀或用了错误的base。
2. to_bytes时没有考虑字节长度，导致OverflowError。
3. 输出结果直接打印十进制数字而不是bytes，导致肉眼无法分辨。

我在测ezRabin时，第一版脚本就把c从十进制str转int后忘了检查位数，结果算出来的根全不对。排查半天发现是n和c读反了变量名。这类错误不涉及任何数学难度，纯粹是粗心，但不注意真的会卡死。

5.3 特殊模数下的加速度验证

如果p ≡ 3 (mod 4)，用c^((p+1)/4)求根，算完后一定要验证r² % p == c % p。如果不等，说明要么c不是二次剩余，要么代码算错。把验证写进脚本里，能在出错时第一时间暴露问题。

Tonelli-Shanks也一样，返回后先做平方验证。我在3.1的代码里while t != 1循环中就有很多出错机会，尤其是b的指数1 << (m - i - 1)，如果m - i - 1是负数，Python里左移负数会直接报错。好的防御式写法是在内层循环加一个边界判断if i == m: return None，防止死循环和负数移位。

5.4 不要把期望押在单一工具上

很多选手习惯了一个RSA解密脚本打天下，看到e=2也不换思路，直接跑RSA流程。这是Rabin题目最经典的坑。Rabin和RSA是有血缘关系，但解密机制完全不一样。遇到e=2的题，第一反应应该是“这是Rabin”，而不是“改改RSA脚本”。如果你用RSA的思路去求逆元，pow(e, -1, phi)会直接报错，因为逆元不存在。

做题时要养成先看e的习惯。e=2直接走Rabin；e很大可能是Wiener攻击或Boneh-Durfee；e=3且消息很短可能是低加密指数攻击；e=65537很常规，优先考虑分解模数或共模攻击。这个判断矩阵能帮你快速定位攻击思路，而不是每题都从零开始猜。

6. 从ezRabin到其他Rabin变体

6.1 Rabin与Blum整数

在Rabin相关题目中，一个常见的设定是p ≡ 3 (mod 4)且q ≡ 3 (mod 4)，这样的n叫Blum整数。在Blum整数下，模平方根有一个很好的性质：四个根中恰好有一个是二次剩余。这个性质被用于一些伪随机数生成器（Blum Blum Shub）的设计，也偶尔出现在CTF题目的随机数预测考点里。

如果题目问“这是一个Blum整数，请恢复明文”，本质就是在暗示你用p ≡ 3 (mod 4)的快速开方公式，然后再用四次组合出根。某些题目甚至会把Rabin的四个根之一设计成flag，让你在四选一中找到那个最“自然”的根，也就是二次剩余根。

6.2 Rabin与RSA共存时的高阶考察

有的进阶题会把Rabin和RSA混在一起，比如用两个不同的公钥加密同一个消息，一个e=2，一个e=65537，这就是标准的共模攻击变体。还有的题目会把Rabin加密作为中间步骤，后面再接一层AES，那就要先用Rabin解出密钥，再解AES。遇到这种题，Rabin这步的脚本是可以直接复用的，所以把这套解密流程练熟很划算。

ezRabin作为一道公开赛题，核心目标就是帮你把Rabin的基调定住：看到e=2，想到开平方；拿到p、q，直接Tonelli-Shanks加CRT；四个根出来，挑可读的提交。这套动作熟练之后，再遇到Rabin的变体，无非是在前后流程里加加减减。

6.3 学习路线建议

如果这是你第一次接触Rabin，我的建议是按下面的顺序练：

1. 先用ezRabin这种直接给p、q的题把Tonelli-Shanks和CRT跑通。
2. 再找只给n、c的题，补上Fermat分解或yafu的流程。
3. 挑战一下需要从n的位运算规律里恢复p、q的题目（比如p和q有重叠比特）。
4. 最后，把Rabin和AES、RSA、随机数预测结合的题目做一遍，强化综合能力。

在做题过程中，我强烈建议自己手敲一遍Tonelli-Shanks而不是直接抄库函数。原因很简单：CTF赛场上你可能没有sympy，也没有sage，但Python标准库一定在。能把算法核心写明白，哪怕现场优化得慢一点，也比依赖黑盒工具心里有底。

最后分享一个小技巧：赛前把Rabin解密脚本按“快速公式版”和“Tonelli-Shanks通用版”各备一份，并确保脚本里包含平方验证和四根输出。这样连调试时间都省了，拿到题直接喂参数，五秒出flag。这次ezRabin我就是这么处理的。