我最早遇到Rabin是在BUUOJ上刷NewStarCTF公开赛题单的时候这道ezRabin看起来“入门级”实际却让不少卡在RSA惯性思维里的选手挠头。Rabin加密体制和RSA长得像但解密逻辑完全是两条路——如果把RSA那套e*d ≡ 1 mod φ(n)照搬过来你会发现自己根本算不出私钥因为公钥e2根本没法求逆。这篇文章我会从题目信息收集开始把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的e2在模φ(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 ≈ (pq)/2, b ≈ (q-p)/2p和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的思路分两个阶段先把p - 1写成Q * 2^S的形式其中Q为奇数。这是所有基于二次剩余性质算法的通用预处理。找到一个模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 rTonelli-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^((p1)/4) mod p验证一下r² ≡ c^((p1)/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^((p3)/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 4print(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但如果想把脚本沉淀下来供后续复用我会再改造成一个更健壮的版本。几个关键改进点自动检测p、q模4余数。如果模4余3或模4余5可以直接用快速公式减少对Tonelli-Shanks的依赖跑得更快也更稳。四根候选的自动评分。把每个根转成bytes之后检查是否为可打印ASCII过滤掉乱码候选。在实际比赛中flag几乎总是可读字符串用这个特征能把四个根快速筛到只剩一到两个。对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 decryptsympy.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大整数运算但进制转换依然是最容易翻车的地方。具体来说有三类错误十六进制字符串忘了0x前缀或用了错误的base。to_bytes时没有考虑字节长度导致OverflowError。输出结果直接打印十进制数字而不是bytes导致肉眼无法分辨。我在测ezRabin时第一版脚本就把c从十进制str转int后忘了检查位数结果算出来的根全不对。排查半天发现是n和c读反了变量名。这类错误不涉及任何数学难度纯粹是粗心但不注意真的会卡死。5.3 特殊模数下的加速度验证如果p ≡ 3 (mod 4)用c^((p1)/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解密脚本打天下看到e2也不换思路直接跑RSA流程。这是Rabin题目最经典的坑。Rabin和RSA是有血缘关系但解密机制完全不一样。遇到e2的题第一反应应该是“这是Rabin”而不是“改改RSA脚本”。如果你用RSA的思路去求逆元pow(e, -1, phi)会直接报错因为逆元不存在。做题时要养成先看e的习惯。e2直接走Rabine很大可能是Wiener攻击或Boneh-Durfeee3且消息很短可能是低加密指数攻击e65537很常规优先考虑分解模数或共模攻击。这个判断矩阵能帮你快速定位攻击思路而不是每题都从零开始猜。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混在一起比如用两个不同的公钥加密同一个消息一个e2一个e65537这就是标准的共模攻击变体。还有的题目会把Rabin加密作为中间步骤后面再接一层AES那就要先用Rabin解出密钥再解AES。遇到这种题Rabin这步的脚本是可以直接复用的所以把这套解密流程练熟很划算。ezRabin作为一道公开赛题核心目标就是帮你把Rabin的基调定住看到e2想到开平方拿到p、q直接Tonelli-Shanks加CRT四个根出来挑可读的提交。这套动作熟练之后再遇到Rabin的变体无非是在前后流程里加加减减。6.3 学习路线建议如果这是你第一次接触Rabin我的建议是按下面的顺序练先用ezRabin这种直接给p、q的题把Tonelli-Shanks和CRT跑通。再找只给n、c的题补上Fermat分解或yafu的流程。挑战一下需要从n的位运算规律里恢复p、q的题目比如p和q有重叠比特。最后把Rabin和AES、RSA、随机数预测结合的题目做一遍强化综合能力。在做题过程中我强烈建议自己手敲一遍Tonelli-Shanks而不是直接抄库函数。原因很简单CTF赛场上你可能没有sympy也没有sage但Python标准库一定在。能把算法核心写明白哪怕现场优化得慢一点也比依赖黑盒工具心里有底。最后分享一个小技巧赛前把Rabin解密脚本按“快速公式版”和“Tonelli-Shanks通用版”各备一份并确保脚本里包含平方验证和四根输出。这样连调试时间都省了拿到题直接喂参数五秒出flag。这次ezRabin我就是这么处理的。