1. 项目概述从一道CTF赛题看Rabin密码系统的实战攻防最近在复盘一些经典的CTFCapture The Flag密码学赛题2022年网鼎杯的“crypto661-rabin”这道题给我留下了挺深的印象。它没有用更常见的RSA而是选择了Rabin密码系统作为考点这本身就挺有意思。Rabin算法在教科书和理论介绍里往往被一笔带过很多人只知道它“基于整数分解的困难性”和“解密有四个可能结果”但真到了实战里面对一个具体的、包装过的赛题怎么把理论转化成一行行能跑出flag的代码中间的门道可就多了。这道题的核心就是要求选手在已知Rabin加密的公钥和密文的情况下恢复出原始的明文消息。听起来和RSA很像对吧但它的解密逻辑和陷阱设置截然不同。如果你直接用处理RSA的思路去套大概率会卡住或者得到一堆乱码。这正体现了CTF密码学的魅力——它考验的不是死记硬背而是对密码学原理深刻的理解和灵活的运用能力。接下来我就结合这道题把Rabin算法的里里外外、在CTF中的常见变形以及我踩过的坑给大家掰开揉碎了讲清楚。无论你是正在备赛的CTF新手还是想深入了解非对称加密细节的开发者相信都能从中获得直接的帮助。2. Rabin密码系统原理深度拆解要攻克这道题绝不能停留在“调用库函数”的层面必须吃透Rabin的数学原理。它比RSA更直接地依赖于大整数分解的难度。2.1 算法核心简洁的数学构造Rabin加密算法的核心过程异常简洁。密钥生成选择两个大素数p和q满足p ≡ q ≡ 3 (mod 4)。这个条件是为了让解密过程更高效利用Tonelli-Shanks算法求模平方根的特殊情况。计算模数n p * q。公钥就是n私钥是(p, q)。 你会发现公钥极其简单只有一个n。这和我们熟悉的RSA公钥(n, e)中e通常取65537不同Rabin的加密指数e固定为2。加密过程对于明文m要求0 m n加密就是计算密文cc ≡ m^2 (mod n)是的加密就是求明文的平方再模n。从计算上看它比RSA的模幂运算m^e mod n更简单。解密过程这才是Rabin的精华和难点所在。已知密文c和私钥(p, q)我们需要解方程m^2 ≡ c (mod n)由于n p * q这个方程等价于求解以下两个方程组的公共解m^2 ≡ c (mod p)m^2 ≡ c (mod q)因为p和q是素数且满足≡ 3 (mod 4)所以模素数下的平方根有非常高效的解法计算c在模p下的解m_p c^((p1)/4) mod p计算c在模q下的解m_q c^((q1)/4) mod q这里利用了费马小定理和p ≡ 3 (mod 4)的性质使得(p1)/4是整数并且(c^((p1)/4))^2 ≡ c^((p1)/2) ≡ c * c^((p-1)/2) ≡ c (mod p)当c是模p的二次剩余时c^((p-1)/2) ≡ 1 (mod p)。得到m_p和m_q后每个都有两个可能的值正和负即m_p和p - m_pm_q和q - m_q。然后利用中国剩余定理CRT将这四个组合两两配对就能得到原始明文m在模n下的四个可能的平方根。注意这里有一个关键点c必须同时是模p和模q的二次剩余加密解密才能正常进行。在CTF题中这通常是默认成立的但你需要知道这个前提。2.2 与RSA的对比为什么CTF爱考Rabin理解Rabin和RSA的区别能帮你更好地把握解题方向。特性Rabin 密码系统RSA 密码系统安全性基础等价于大整数分解问题已被证明基于大整数分解和RSA问题的困难性未被证明等价加密指数固定为 2通常为 65537与φ(n)互质即可解密结果有4个可能的明文有1个确定的明文计算速度加密解密更快计算平方/平方根相对较慢模幂运算密钥结构公钥仅为(n)公钥为(n, e)CTF常见考点利用解密多解性、选择密文攻击、与填充结合的攻击低加密指数、共模攻击、侧信道、p和q选取不当最大的不同就是解密结果的唯一性。RSA解密永远得到一个确定的结果而Rabin会得到四个。这在CTF中意味着Flag识别解密后你需要从四个候选明文中根据格式如flag{...}、CTF{...}或可读性人工识别出正确的那个。攻击面Rabin对选择密文攻击是极度脆弱的。如果你能获取一个解密Oracle即服务器能为你解密任意密文并返回四个结果之一或全部理论上你可以在多项式时间内分解模数n。这在CTF中经常以“服务器提供解密服务”的交互题形式出现。实操心得很多Rabin的CTF题最后一步解密出来的四个结果里可能只有一个是符合人类阅读的ASCII字符串另外三个是看起来像乱码的大整数。不要轻易放弃任何一个结果务必把它们都转换成字节看看。有时候出题人甚至会故意把flag放在那个“看起来不像”的结果里。3. “crypto661-rabin” 赛题实战还原与解析光讲理论不够过瘾我们直接回到“网鼎杯2022 crypto661-rabin”这道题。通常这类题目会提供一个压缩包或描述里面包含类似以下的信息我根据常见模式进行还原public.key或直接给出n 123456789...一个很大的整数ciphertext或encrypted_flagc 987654321...另一个很大的整数可能附带一个简单的encrypt.py脚本展示加密过程就是c m^2 mod n。我们的任务很明确已知 (n, c)求 m。3.1 解题第一步分解模数 n这是所有基于分解困难性密码系统的共同突破口。在CTF中n通常不会真的不可分解出题人会用一些有特点的素数来构造它。尝试在线分解数据库对于不是特别大的n比如小于512位可以尝试在factordb.com这类网站查询可能已被收录。检查是否为光滑数使用yafu或sage等工具尝试分解。如果p和q接近可以用费马分解法。关注特殊结构在这道“网鼎杯”的题中经过尝试很可能发现n可以直接分解或者p和q非常接近以至于(pq)/2接近sqrt(n)(p-q)/2很小。我们可以用以下Python脚本进行费马分解的尝试import gmpy2 from Crypto.Util.number import * n 0xabcdef... # 替换为题目给出的n def fermat_factor(n): a gmpy2.isqrt(n) 1 b2 a*a - n while not gmpy2.is_square(b2): a 1 b2 a*a - n b gmpy2.isqrt(b2) p a b q a - b return int(p), int(q) p, q fermat_factor(n) print(fp {p}) print(fq {q}) print(fn p*q? {n p*q})假设我们成功分解得到p和q。踩坑记录一定要验证p和q是否满足p % 4 3和q % 4 3。虽然理论上Rabin要求这样但有些CTF题会故意不满足这时解密公式c^((p1)/4)就不适用了需要使用更一般的Tonelli-Shanks算法来求模平方根复杂度会提升。如果发现不满足第一时间要反应过来。3.2 解题第二步实现Rabin解密并处理多解得到p和q后我们就可以编写解密脚本了。核心步骤就是前面原理部分讲到的计算c在模p和模q下的“平方根”。组合所有可能的根。用CRT还原出模n下的四个可能明文。import gmpy2 from Crypto.Util.number import * # 题目数据 n 0xabcdef... # 替换 c 0x123456... # 替换 # 分解得到的 p ... q ... assert p * q n assert p % 4 3 and q % 4 3 # 确认条件满足 def rabin_decrypt(c, p, q): Rabin解密返回四个可能的明文整数 # 计算模p和模q下的平方根 mp pow(c, (p 1) // 4, p) mq pow(c, (q 1) // 4, q) # 每个都有两个根 r1 mp r2 p - mp s1 mq s2 q - mq # 使用中国剩余定理组合 def crt(a, m, b, n): 解同余方程组 x ≡ a (mod m), x ≡ b (mod n) g, x, y gmpy2.gcdext(m, n) if (b - a) % g ! 0: return None lcm m // g * n return (a (b - a) // g * x * m) % lcm # 得到四个候选解 solutions [] for r in (r1, r2): for s in (s1, s2): root crt(r, p, s, q) if root is not None: solutions.append(root) return solutions possible_ms rabin_decrypt(c, p, q) print(fFound {len(possible_ms)} possible plaintexts:) for i, m in enumerate(possible_ms): try: # 尝试转换为字节串 flag_candidate long_to_bytes(m) # 通常flag会有可打印前缀过滤一下 if bflag in flag_candidate or bCTF in flag_candidate or flag_candidate.isascii(): print(f[{i}] (Possible Flag): {flag_candidate}) else: print(f[{i}] (Hex): {hex(m)[:50]}...) except: print(f[{i}] (Too large or invalid): {hex(m)[:50]}...)运行这个脚本你大概率会在四个输出中看到一个包含flag{或类似格式的字符串那就是本题的答案。3.3 解题第三步处理填充与编码上面的脚本假设明文m直接就是数字。但在实际中为了增加安全性同时也是CTF的考点明文通常会经过填充Padding和编码。常见套路明文是字符串的字节形式比如flag{this_is_a_sample}被直接转换成整数m。我们的解密脚本最后long_to_bytes就能直接看到。使用了PKCS#1 v1.5或OAEP等填充这会使明文结构变复杂直接解密得到的数字需要解析填充格式才能提取出真·明文。Rabin本身很少直接套用这些复杂填充但CTF题可能会模仿。混合了其他编码如Base64、Hex编码后的字符串再做加密。解密后得到的是编码后的文本需要进一步解码。对于“crypto661-rabin”根据网鼎杯的风格很可能就是第一种最简单的情况。但如果遇到更复杂的情况你的解密脚本就需要增加一个“后处理”模块。实操心得在写解密脚本时long_to_bytes后不要只打印十六进制缩写一定要尝试用decode(utf-8, errorsignore)或者直接print(repr(flag_candidate))看看原始字节。有时候flag可能包含不可见字符或特殊结构直接打印会丢失信息。另外四个结果都要仔细检查我曾遇到过flag藏在那个“看起来最小”或者“看起来最大”的整数对应的字节串里。4. Rabin在CTF中的进阶攻击模式掌握了基础解密我们来看看CTF中Rabin更“狡猾”的考法。这能帮你未来遇到变种题时快速定位思路。4.1 选择密文攻击CCA这是Rabin算法理论上的一个严重弱点。如果攻击者可以访问一个解密Oracle即“你给我任意密文我告诉你对应的一个明文”那么攻击者可以通过精心构造的密文来分解n。简化攻击原理攻击者随机选择一个整数r计算密文c ≡ r^2 * c (mod n)其中c是目标密文。将c发送给Oracle进行解密Oracle返回一个明文m它是c的四个平方根之一。由于c ≡ r^2 * c ≡ r^2 * m^2 ≡ (r*m)^2 (mod n)所以m应该等于± r*m mod n或± 其他根。攻击者计算gcd(m - r*m, n)。如果m是± r*m那么这个最大公约数就是1或n没用。但如果Oracle返回的是其他根概率为1/2那么gcd(m - r*m, n)就极有可能是p或q从而分解n。CTF中的应用题目通常会给你一个网络服务你可以发送加密后的数据给它它会返回解密结果可能是四个结果中的某一个或者拼接后的全部。你的目标就是利用这个交互分解出n的因子从而解密真正的flag密文。注意在实际的、安全的Rabin方案中必须引入抗CCA的填充方案如OAEP否则不能直接使用。CTF题为了考察算法本身常常会省略填充。4.2 已知部分明文或相关明文攻击如果攻击者知道明文m的某些部分信息或者知道多个明文之间存在某种线性关系结合Rabin的数学性质可能可以构建方程来求解。例如如果知道m是一个较短字符串填充到很长那么m可能小于sqrt(n)。在整数域下不模nc m^2这个关系成立那么直接对c开平方就能得到m完全不需要分解n。这就是“小明文攻击”。检查方法在解题时一个很好的习惯是计算gmpy2.isqrt(c)看看它的平方是否恰好等于c。如果是恭喜你题目比想象中简单。4.3 模数n构造不当除了p和q接近导致费马分解外还有其他不当构造p或q过小可以直接暴力分解或查表。n可以被其他特殊方法分解如Pollards p-1算法当p-1的质因子都很小时有效。共模攻击虽然Rabin公钥只有n但如果两套密钥使用了相同的n或者n1和n2有公因数同样可以通过欧几里得算法快速分解。5. 实战工具链与脚本编写心得工欲善其事必先利其器。处理CTF密码学尤其是Rabin这类需要大数运算的题目一套顺手的工具和脚本模板能节省大量时间。5.1 核心工具推荐Python gmpy2/pycryptodome这是绝对的主力。gmpy2提供高性能的大整数运算和开方、gcd等函数pycryptodome或旧的pycrypto中的Crypto.Util.number模块提供了long_to_bytes、bytes_to_long、getPrime等常用函数不可或缺。pip install gmpy2 pycryptodomeSageMath一个基于Python的数学软件系统集成了大量数论、代数函数。对于复杂的模平方根计算当p % 4 ! 3时、有限域运算Sage是神器。它的Mod(a, p).sqrt()可以轻松求二次剩余根。yafu强大的整数分解工具适用于在本地尝试分解中等大小的n数百位。对于CTF中的常规赛题yafu通常能搞定。factordb.com在线分解数据库。对于常见的、或之前有人分解过的n直接查询可能瞬间得到结果。5.2 脚本编写避坑指南类型处理Python原生整数虽然可以处理大数但gmpy2.mpz类型在连续运算中效率和功能更优。注意gmpy2函数返回的通常是mpz类型与Pythonint混用时可能需要显式转换。import gmpy2 n gmpy2.mpz(12345678901234567890) # 使用gmpy2函数 root gmpy2.isqrt(n) # 与python int交互 if n % 4 3: # do something中国剩余定理CRT的实现一定要自己会写。虽然gmpy2有gmpy2.gcdext可以用来实现pycryptodome的number模块也有inverse函数但理解其原理并能快速写出正确的CRT合并代码是关键。def crt(remainders, moduli): 求解同余方程组 x ≡ remainders[i] (mod moduli[i]) total 0 prod 1 for m in moduli: prod * m for r_i, m_i in zip(remainders, moduli): p prod // m_i total r_i * gmpy2.invert(p, m_i) * p return total % prod对于Rabin的两两组合用简单的两两合并函数更直观。结果验证解密出候选明文m_candidate后一个重要的验证步骤是检查pow(m_candidate, 2, n) c是否成立。如果成立说明解密过程在数学上是正确的。这是一个很好的排错手段。编码与解码long_to_bytes和bytes_to_long是双向的。但要注意当明文数字m以0x00开头时long_to_bytes可能会丢失这个开头的零。在有些涉及填充的复杂场景下这会导致错误。此时可能需要指定字节长度如long_to_bytes(m, (n.bit_length()7)//8)。5.3 针对“crypto661-rabin”的完整解题脚本模板结合以上所有点一个健壮的、可用于此类题目的通用脚本模板如下#!/usr/bin/env python3 import gmpy2 from Crypto.Util.number import long_to_bytes, bytes_to_long import sys def fermat_factor(n): 费马分解 a gmpy2.isqrt(n) 1 b2 a*a - n while not gmpy2.is_square(b2): a 1 b2 a*a - n b gmpy2.isqrt(b2) return int(ab), int(a-b) def rabin_decrypt_crt(c, p, q): 使用CRT解密Rabin返回四个根 assert p % 4 3 and q % 4 3 mp pow(c, (p1)//4, p) mq pow(c, (q1)//4, q) roots_p [mp, p - mp] roots_q [mq, q - mq] roots [] for rp in roots_p: for rq in roots_q: # 解同余方程组: x ≡ rp (mod p), x ≡ rq (mod q) # 使用gmpy2.gcdext g, x, y gmpy2.gcdext(p, q) if (rq - rp) % g ! 0: continue lcm p // g * q root (rp (rq - rp) // g * x * p) % lcm roots.append(int(root)) return roots def main(): # --- 从这里开始替换为题目数据 --- n 0xabcdef... # 模数 c 0x123456... # 密文 # --- 替换结束 --- print(f[*] n {n}) print(f[*] c {c}) # 尝试直接开方小明文攻击 m_sqrt gmpy2.isqrt(c) if m_sqrt * m_sqrt c: print(f[!] Found by direct sqrt: {long_to_bytes(int(m_sqrt))}) return # 分解n print(f[*] Factoring n...) # 方法1: 尝试费马分解适用于p,q接近 try: p, q fermat_factor(n) if p * q n: print(f[] Fermat factorization succeeded!) print(f p {p}) print(f q {q}) else: print(f[-] Fermat failed.) # 这里应转向yafu或factordb为演示我们假设已知p,q # p, q known_p, known_q except Exception as e: print(f[-] Factorization error: {e}) # 假设我们通过其他方式知道了p, q # p, q known_p, known_q return # 检查p,q是否满足Rabin要求 if not (p % 4 3 and q % 4 3): print(f[!] Warning: p or q not ≡ 3 mod 4. Need general sqrt algorithm.) # 可以使用SageMath的Mod(c, p).sqrt()此处略 return # Rabin解密 print(f[*] Decrypting with Rabin...) possible_plaintexts rabin_decrypt_crt(c, p, q) print(f[] Found {len(possible_plaintexts)} possible plaintexts.) flags [] for idx, m in enumerate(possible_plaintexts): # 验证解密正确性 if pow(m, 2, n) ! c % n: print(f [-] Candidate {idx} failed verification.) continue try: mb long_to_bytes(m) # 尝试以UTF-8解码忽略错误 try: text mb.decode(utf-8) print(f [{idx}] (UTF-8): {text[:80]}) if flag in text or CTF in text: flags.append((idx, text)) except UnicodeDecodeError: # 如果不是UTF-8显示hex和可能的ASCII部分 print(f [{idx}] (Hex): {mb.hex()[:80]}...) # 检查是否有可打印ASCII字符 ascii_part .join(chr(b) if 32 b 127 else . for b in mb[:50]) print(f (ASCII): {ascii_part}) if bflag in mb or bCTF in mb: flags.append((idx, mb)) except Exception as e: print(f [{idx}] (Error processing): {e}) if flags: print(f\n[] Potential flag(s) found:) for idx, flag in flags: print(f Candidate {idx}: {flag}) else: print(f\n[-] No obvious flag pattern found. Review the candidates above.) if __name__ __main__: main()这个模板包含了从分解、解密到结果筛选和验证的完整流程并加入了小明文攻击的检查。你可以把它保存下来遇到类似的Rabin题目只需替换n和c的值就能快速跑出结果。6. 从这道题延伸开的密码学学习建议通过“crypto661-rabin”这道题我们不仅解决了一个具体问题更打开了一扇窗看到了公钥密码学中一个优美而直接的设计。要在这个领域走得更远我个人的体会是不要只停留在“解出题”。每做一道题就去深挖它背后的算法。比如这次遇到Rabin就去读一读它的原始论文理解它安全性证明为什么等价于整数分解。对比一下RSA-OAEP和Rabin-Williams填充方案的区别。动手实现一遍完整的密钥生成、加密、解密流程甚至模拟一下选择密文攻击。建立自己的“武器库”。就像上面的脚本模板把常用的数论函数CRT、模逆、快速幂、素性检测、常见的攻击脚本费马分解、Pollard-rho、低指数攻击都封装成函数归拢到一个工具包里。下次遇到问题你就能快速组合出击。关注数学。密码学的根基是数学。模运算、群论、有限域、椭圆曲线……这些概念起初可能令人畏惧但当你通过CTF题目反复应用它们时理解会越来越深刻。从Rabin的二次剩余到RSA的欧拉定理再到ECC的离散对数数学是连接所有点的线。最后回到这道题本身它像是一个引子提醒我们密码学不仅仅是黑盒调用API。理解原理洞察弱点才能在攻击与防御的博弈中占据主动。当你再看到c m^2 mod n时希望你的第一反应不再是迷茫而是能会心一笑脑海里清晰地浮现出那四个平方根以及找到它们的那条路径。