Rabin密码系统实战：从二次剩余到CRT破解CTF多解难题

CTF里很多密码题翻来覆去就是那几个老熟人的变装RSA换换e、AES换换模式、DES换换key顺序。但前两天在BUUOJ刷到“坏蛋是雷宾”这道题时我盯着题面愣了好一会儿——它考的是Rabin密码系统一个长得跟RSA几乎一模一样的加密方案却又处处跟RSA对着干公钥指数是2、解密结果不唯一、安全性理论上还比RSA更强。这道题与其说在考你会不会解方程不如说在考你有没有从“解密必然得到唯一答案”的惯性思维里跳出来。这篇文章就从这道题出发完整讲一遍Rabin密码系统的原理、数学工具和实战解题脚本适合刚入门CTF、想系统搞懂Rabin的新手也适合想复习一下二次剩余和CRT的老手。我不会把网上那些抄来抄去的公式再贴一遍而是按我实际做题的思路来先看题面再拆数学最后写脚本拿flag。全程用的都是能直接跑通的代码和真实可复现的参数。1. 拿到“坏蛋是雷宾”时我以为是道RSA题1.1 题面给人的第一印象BUUOJ上这道题的名字叫“坏蛋是雷宾”题目描述通常很简略一上来就给一组数。第一次刷到的时候我的第一反应是“哦又是RSA变种”因为题面结构太像了一个大整数n一个密文c让你解出明文m。跟RSA题唯一的区别是它的公钥指数长得非常离谱——e2。很多人看到e2下意识就开始做RSA流程算φ(n)、求d、然后pow(c, d, n)。结果要么直接报错要么算出来的东西是一团乱码。原因其实很简单gcd(e, φ(n)) gcd(2, φ(n))几乎不可能等于1私钥d根本不存在。Rabin和RSA的密钥生成阶段几乎一样但从这一步开始就分道扬镳了。如果你拿到题目时发现n是两个素数的乘积、e又是2那就是Rabin密码系统。这类题目在各大CTF平台都很常见除了BUUOJ这道“坏蛋是雷宾”很多入门赛也喜欢用Rabin来考二次剩余、中国剩余定理和“多解筛选”这三个基本功。1.2 为什么Rabin值得单独花时间读如果仅仅为了刷一道题直接抄脚本就够了。但Rabin这套东西值得多花点时间是因为它捅破了一层窗户纸公钥加密不一定只能解密出唯一结果多解也不代表方案是错的。Rabin的安全性跟大整数分解是严格等价的——注意是“等价”不是RSA那种“可以归约到分解但方向没完全证明”的关系。这句话翻译成人话就是如果有人能破解Rabin他就能直接分解n反过来能分解n就一定能破解Rabin。在密码学理论里这是非常漂亮的一个性质实战中也经常被拿来跟RSA做对比。另外Rabin的解密过程天然会用到两个高价值知识点欧拉准则判断一个数在模素数下是不是二次剩余。中国剩余定理CRT把模p和模q下的小方程组合回模n下的大结果。这两个知识点在CTF里出现频率极高后面解RSA-CRT、解同余方程组、甚至是一部分格密码题都会用到。所以哪怕你只打算刷题拿flag也不要把Rabin当孤立的题型处理它更像是一块中转站把数论基础接进密码分析的地界。2. 解密不唯一Rabin的数学内核到底长什么样2.1 密钥生成与加密公式Rabin的密钥生成步骤几乎就是RSA的青春版随机选两个不相等的素数p和q通常要求两者位数接近。计算n p * q。公钥就是n私钥是(p, q)。加密更简短c m^2 mod n其中明文m要满足0 m n。注意公钥里压根没有e的概念因为e固定为2加密就是一次平方模n。攻击者手里只有n和c任务就是解出某个m使得m^2 ≡ c (mod n)。这里有个非常关键的反直觉点加密过程不需要知道p和q只需要n所以严格说Rabin的公钥不是“(n, e)”这样的二元组而是只有“n”这一个数。公钥越短效率越高但代价就是解密函数是一对多映射——这是Rabin所有“妖蛾子”的根源。2.2 解密的关键模素数开平方要解x^2 ≡ c (mod n)直接对模合数开根很难但可以先拆到素数上分别解x_p^2 ≡ c (mod p) x_q^2 ≡ c (mod q)拿到这两个小方程的解后再组合。对模素数开平方就有非常成熟的工具。先介绍判断工具欧拉准则。对素数p和任意整数a如果a是模p的二次剩余也就是说存在x满足x^2 ≡ a (mod p)那么a^((p-1)/2) ≡ 1 (mod p)如果a不是二次剩余则结果等于p-1也就是-1 (mod p)。这个定理可以直接用快速幂验证。有了欧拉准则不难推出开根公式。如果题目比较善良把p和q选成满足p ≡ 3 (mod 4)、q ≡ 3 (mod 4)的素数——这在Rabin实现里其实是最常见的选法因为开根有闭式解。对c直接计算r_p c^((p1)/4) mod p为什么这样能开出根因为r_p^2 ≡ c^((p1)/2) ≡ c^((p-1)/2) * c ≡ 1 * c ≡ c (mod p)中间那一步用到的正是欧拉准则因为我们的c来自m^2 mod n它在模p下天然就是二次剩余。注意这里的“根”不只一个r_p和-r_p mod p (p - r_p)都是方程的解。2.3 中国剩余定理组合出四个候选解现在我们有四条小路x ≡ ±r_p (mod p) x ≡ ±r_q (mod q)把模p下的两个根和模q下的两个根做任意组合用中国剩余定理合起来就能得到模n下的四个解。这就是Rabin“解密不唯一”的来源。写出来就是x1 CRT( r_p, r_q) x2 CRT( r_p, -r_q) x3 CRT(-r_p, r_q) x4 CRT(-r_p, -r_q)四个解里只有一个是真的明文。后面筛flag要做的就是把这四个候选都还原成字节串看哪个像人话。这里顺带说一个Rabin非常著名的性质如果攻击者能拿到一个“解密预言机”——也就是说给他一个密文他返回四个解中的某一个——那么攻击者可以很快分解n。因为把两个不同的解记作x和y它们的差在多组情况下会被p或q整除于是gcd(x - y, n)就能直接吐出p或者q。所以真实世界的Rabin如果直接拿来做加密还需要加冗余校验、选一个带格式的明文否则很容易被选择密文攻击打穿。CTF题里不搞这些花活基本就是裸的m^2 mod n但我们心里要有数题目的“多解”不是bug是系统的固有属性。3. 动手写脚本前先把数学工具备齐3.1 两种模数下的开平方方案上一节说到了p ≡ 3 (mod 4)时的快速开根公式root pow(c, (p 1) // 4, p)但如果题目给的p或者q不满足这个条件就需要更通用的Tonelli-Shanks算法。CTF里Rabin题目的p、q大部分都是模4余3不过一旦遇到模4余1的素数Tonelli-Shanks就是唯一靠谱的常规解法。我直接把能跑的Python实现放这里def tonelli_shanks(n, p): # 先判断二次剩余 if pow(n, (p - 1) // 2, p) ! 1: return None # 快速路径p ≡ 3 (mod 4) if p % 4 3: return pow(n, (p 1) // 4, p) # p - 1 q * 2^s其中q为奇数 q p - 1 s 0 while q % 2 0: q // 2 s 1 # 找一个非二次剩余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 0 temp t while temp ! 1: temp temp * temp % p i 1 if i m: return None b pow(c, 1 (m - i - 1), p) r r * b % p c b * b % p t t * c % p m i return r这段代码在普通Python 3环境下可以直接用不需要gmpy2。实际做题时可以先检查p和q模4的值如果两个都等于3就别上重型武器直接用快速公式只有遇到非3的情况才调Tonelli-Shanks。3.2 分解n与确定p、q的实操路径Rabin题目的第一道坎永远是“怎么拿到p和q”。BUUOJ这道题有时候会直接把p、q给你那种就属于送分题直接往下算。但更多情况下题面只给n和c这时候你就要靠分解大整数来夺回私钥。CTF入门最常用的分解路径是先丢factordbhttps://factordb.com查一下。很多赛题的n都是刻意构造的小数早就在数据库里躺着输入n回车直接出p、q。查不到再用yafu本地分解。命令形式类似yafu factor(n)yafu会自动尝试pollard rho、p-1、ECM这些方法对几百bit的CTF模数通常够用。如果环境里有sagemath直接factor(n)最省事。分解之后要养成一个好习惯确认p ! q。如果p q那n是平方数Rabin整套公式都不适用要单独用sqrt(n)开出来当素数做公式细节也会有变化。CTF题一般不会这么缺德但检查一下永远不亏。还有一个常见坑题目给的n和c可能是十六进制字符串尤其从文件读入时容易带着换行符或者0x前缀。写脚本时统一用int(n, 16)或int(n.strip(), 16)转成十进制整数避免一上来就是TypeError或者多位数错位。3.3 初版脚本还原四路候选明文把上面的工具都备好后解密脚本其实没有多少代码核心就三步。第一步用快速公式或Tonelli-Shanks分别算模p和模q下的根第二步用中国剩余定理做四种组合第三步把每个解从整数转字节串并打印。from itertools import product import gmpy2 from Crypto.Util.number import long_to_bytes def crt_pair(rp, rq, p, q): # x ≡ rp (mod p), x ≡ rq (mod q) t ((rq - rp) * gmpy2.invert(p, q)) % q return rp p * t def rabin_decrypt(n, p, q, c): # 这里假设 p、q 都满足 ≡ 3 (mod 4) rp pow(c, (p 1) // 4, p) rq pow(c, (q 1) // 4, q) roots_p [rp, (-rp) % p] roots_q [rq, (-rq) % q] candidates [] for sp, sq in product(roots_p, roots_q): m_candidate crt_pair(sp, sq, p, q) candidates.append(m_candidate) print(f[*] candidate m {m_candidate}) print(f[*] candidate bytes {long_to_bytes(m_candidate)}) return candidates # 示例参数正式做题时替换为题目给的 p, q, c p 23 q 31 n p * q c pow(65, 2, n) # 明文演示为AASCII65 print(f[*] n {n}, c {c}) rabin_decrypt(n, p, q, c)这段代码跑出来后你会看到四个候选解其中一个就是65转成bytes后是bA。另外三个通常是一堆不可读字节或者数值巨大但在n以内。这就是手动做Rabin和多解筛选的完整雏形。4. 完整复现与实战避坑汇总4.1 用一组演示参数走一遍流程为了避免把原题flag直接贴出来剧透会毁掉刷题体验我用一组小参数演示完整流程取p23, q31, n713明文m65也就是字符A。加密后c 65^2 mod 713 4225 mod 713 678等等这里我重新算一下713*535654225-3565660所以实际上c660。我上一节代码里的写法是c pow(65, 2, n)它算出来的就是660不会骗人。接下来解密c mod p 660 mod 23 16快速开根rp 16^6 mod 23 4另一根是23-419。c mod q 660 mod 31 9快速开根rq 9^8 mod 31 28另一根是31-283。为什么这组数据是一个很好的示例因为它清楚地展示了“明文的模分量”和“明文本身”的区别。m65比p23大所以它在模p下的分量是65 mod 23 19对应的是开根后那次组合里的19而不是直接看到65。只有把(rp19, rq3)这个组合拿去做中国剩余定理才会得到x ≡ 19 (mod 23) x ≡ 3 (mod 31) x 65这一步很多人第一次会犯迷糊为什么明明加密的是65开根出来的却是4、19、28、3这些乱七八糟的数别急它们是在“模p世界”和“模q世界”里的分身CRT就是把这些分身重新拼成“模n世界”里的完整实体。四组排列里65只是其中一个分身组合的结果。脚本输出大约会是这样[*] candidate m 420 [*] candidate bytes b\xa4 [*] candidate m 316 [*] candidate bytes b\x13 [*] candidate m 293 [*] candidate bytes b% [*] candidate m 65 [*] candidate bytes bA只有bA是可打印的其他要么是控制字符要么在终端里显示成乱七八糟的符号。真实题目里正确解往往就是那个转出来是以flag{开头的干净字符串四个候选中一眼就能挑出来。4.2 从四个解里怎么把flag捞出来手动看四个打印结果当然可行但如果肉眼看花眼或者密文包含大量不可打印字符最好在脚本里直接加过滤逻辑。CTF的flag基本遵循两种格式flag{...}、ctf{...}或者题目自定义前缀。我习惯按“可打印ASCII占比”来筛写起来简单粗暴def looks_like_flag(x): data long_to_bytes(x) printable sum(1 for b in data if 32 b 126) return printable / len(data) 0.9 flag_candidates [m for m in candidates if looks_like_flag(m)] print(flag_candidates)如果题目给的是纯数字明文比如某种编码后的整数那就还需要结合题目描述去判断。另外有时一个候选解转出来可读但被杂字节包围不要急着排除先试试能不能从里面抠出flag片段。我在实际做题时还经常把四个候选值都存成十六进制再丢给随波逐流这类编码工具看一遍反正多看一眼不亏。4.3 变体题目和一些容易翻车的边界情况Rabin题目在CTF里的变化其实不多但每种变化都有一个对应的坑。变体一p、q不是模4余3的素数。这时候快速公式失效pow(c, (p1)//4, p)算出来的压根不是根。解决方案就是我上面给的Tonelli-Shanks没有别的捷径。加密方选素数时也往往会特意选模4余3来省事所以你遇到模4余1的概率不高但一旦遇到就别硬套公式。变体二题目只给n和c不给p、q。先用factordb查查不到再用yafu。有些模数达到1024bit的题理论上没法硬分解但CTF里至少会留一条路比如n实际由小因子相乘、或者p和q生成方式有漏洞。这种题考的就是“识别出Rabin之后你能不能找到私钥”而不是真的让你算数。变体三c直接大于n。可能是从文件读入时把十六进制和十进制搞混了也可能是出题人故意把c给了个带模的值。实际计算前最好把c先mod n一下c c % n这一步不影响正确结果因为密文本来就是模n下的一个余数。变体四四个候选里有两个长得都可读。这种情况一般是明文本身用两个不同的padding方式或者明文长度很小导致字节串补零方式不同。实在分不出来就只能结合题目描述确认格式。真有歧义题的话通常题面会暗示flag格式按那个格式筛就行。4.4 我总结的避坑清单坑现象解决办法当RSA做尝试算dgcd(2, phi) ! 1d不存在第一时间识别e2转向Rabin流程只开模p或模q的根就输出得到一堆无意义短数必须做CRT组合取四个解p、q模4余1时用了快速公式候选里永远没有flag因为根就是错的换Tonelli-Shanks把n和c当成十进制读数字巨大或脚本报错判断十六进制格式统一int转换不筛候选直接找flag被不可读bytes干扰按可打印ASCII比例过滤n分解漏了小因子p、q识别错根全错用factordb确认完整分解p、q相等整套公式失效单独处理平方数情况最后补充一点经验Rabin的解密脚本最好封装成函数把快速开根、Tonelli-Shanks、CRT、候选过滤四段逻辑分开。别问为什么——等你遇到下一道题需要在Rabin脚本里塞一堆辅助逻辑时就懂这种模块化的好处了。实测下来封装好的脚本碰到任何Rabin变体最多改两行参数三分钟内就能出结果。刷题这回事拼的不是临时想公式的速度而是你的工具箱里有没有趁手的家伙。