Rabin密码系统原理与CTF实战解密

1. 项目背景与核心价值

Rabin密码系统作为首个被证明在特定条件下与整数分解问题等价的非对称加密方案，在CTF密码学挑战中占据着独特地位。这道来自BUUOJ平台的"坏蛋是雷宾"题目，巧妙地将Rabin算法的数学特性转化为需要逆向破解的暗号系统。我在实际解题过程中发现，许多参赛者面对这类非标准RSA变种时容易陷入两个误区：要么过度依赖现成工具而忽略数学本质，要么被复杂的模运算吓退。本文将用实战视角拆解Rabin的加密原理，并逐步还原题目破解的全过程。

不同于教科书式的理论讲解，这里我会重点分享三个实战要点：如何快速识别Rabin加密特征、当模数可分解时的攻击路径选择、以及中国剩余定理在解密中的巧妙应用。去年在0CTF中遇到的变形Rabin题目，其解题思路就源于对这些核心要点的深入理解。

2. Rabin密码系统原理解析

2.1 算法数学基础

Rabin加密的核心在于二次剩余问题。给定大素数p和q（通常满足p≡q≡3 mod 4），公钥为n=pq。加密过程简单得令人惊讶：对明文m，计算密文c ≡ m² mod n。正是这种看似简单的平方运算，在不知道p和q的情况下，使得求平方根变得异常困难。

举个具体例子：取p=7，q=11（实际应用中应为大素数），则n=77。加密明文m=20：

• c ≡ 20² mod 77 ≡ 400 mod 77 ≡ 15

此时要从c=15恢复m，就需要解决x² ≡ 15 mod 77这个方程。这个过程的困难性正是Rabin系统的安全基础。

2.2 与RSA的关键区别

虽然都基于大数分解难题，Rabin与RSA有三点本质不同：

1. 加密指数固定为2（RSA通常为65537）
2. 解密会得到四个可能解（RSA有唯一解）
3. 安全性证明更强：破译Rabin等价于分解n

在CTF题目中，这些特性往往会成为解题突破口。比如去年HackTM竞赛中就出现过利用多解特性构造flag验证的变种题。

3. 题目实战拆解

3.1 题目特征分析

拿到BUUOJ这道题时，首先观察到两个关键提示：

1. 题目名称明确指向Rabin
2. 给出的公钥文件包含模数n=798321817573328185527646107613495929846147444322791353283989998016278802836109003612812499731758050699162101795605064970751325249020868811203722136266418794684919368609766869336308696738269726199383219515991467448076533010760265779495796183315027763039834855660464854310395417084671414082602200985927612450106785923475018941762695805104597296336734680684671441997445637318263621026088110334008878137547802826280994434901700160878386069980174904566013158024485677724116238262817453456359427490638279662852093914290377787289965798163293540442000281843339517329903053714121114296530274671571434023317019439859488273613

通过factordb尝试分解这个1024位的n，发现竟然成功分解为： p=3136613344949483826690446667480256392626468638370607457454515818992872287033042078245651295956858327870436443371543333504500526102278124006991700585180256248279464294934903121449076263873734210325094560839052977649 q=2545580940228351080557481115403590697351364558898337805920808455106355296680008878315298802863983015431966989695130220349386896586935073621281803452260201

注意：在实际CTF比赛中，遇到可直接分解的n要立即警觉——这要么是故意降低难度，要么暗示着特殊攻击方式。

3.2 解密过程实现

根据Rabin解密原理，我们需要计算c的模p和模q平方根。由于p≡q≡3 mod 4，可以使用Tonelli-Shanks算法的简化版本：

def mod_sqrt(a, p): """求解x² ≡ a mod p 的平方根""" assert legendre_symbol(a, p) == 1, "a不是模p的二次剩余" if p % 4 == 3: x = pow(a, (p + 1) // 4, p) return x, p - x # 此处省略完整Tonelli-Shanks实现...

对密文c求解四个平方根：

1. 计算mp1 = c^((p+1)/4) mod p
2. 计算mq1 = c^((q+1)/4) mod q
3. 用CRT组合四种情况：
   • (mp1, mq1)
   • (mp1, q-mq1)
   • (p-mp1, mq1)
   • (p-mp1, q-mq1)

具体代码实现：

from Crypto.Util.number import inverse def rabin_decrypt(c, p, q): n = p * q mp = pow(c, (p + 1) // 4, p) mq = pow(c, (q + 1) // 4, q) yp = inverse(p, q) yq = inverse(q, p) # 四种组合 r1 = (yp * p * mq + yq * q * mp) % n r2 = n - r1 r3 = (yp * p * mq - yq * q * mp) % n r4 = n - r3 return r1, r2, r3, r4

3.3 明文识别技巧

解密得到四个候选明文后，如何识别真正的flag？根据经验有三种方法：

1. 检查字节格式：通常flag以可读ASCII开头（如"flag{"）
2. 检查PKCS#1填充格式
3. 题目可能提供额外验证条件

在本题中，第二个解"18013880950059508654282450983807213631937442352032620639874846385385451642"转换为字节后得到可读flag。

4. 进阶技巧与变种分析

4.1 当p≡1 mod 4的情况

虽然题目中p≡q≡3 mod 4简化了解密过程，但实际可能遇到更复杂情况。此时需要使用完整的Tonelli-Shanks算法：

def tonelli_shanks(a, p): """通用二次剩余求解算法""" # 找出Q和S使得p-1 = Q*2^S Q = p - 1 S = 0 while Q % 2 == 0: Q //= 2 S += 1 # 寻找二次非剩余z z = 2 while legendre_symbol(z, p) != -1: z += 1 c = pow(z, Q, p) x = pow(a, (Q + 1) // 2, p) t = pow(a, Q, p) m = S while t != 1: # 找出最小的i使得t^(2^i) ≡ 1 i, temp = 0, t while temp != 1 and i < m: temp = pow(temp, 2, p) i += 1 b = pow(c, 1 << (m - i - 1), p) x = (x * b) % p t = (t * b * b) % p c = (b * b) % p m = i return x, p - x

4.2 选择密文攻击

Rabin系统易受选择密文攻击的特性在CTF中常被利用。攻击者可以构造特定密文获取解密结果来恢复私钥。防御方法是添加消息冗余（如OAEP填充）。

5. 实战中的常见陷阱

5.1 模数分解失败

当n无法分解时，可以考虑：

1. 检查是否为特殊形式的数（如费马数）
2. 尝试Pollard's rho等算法
3. 题目可能隐藏其他攻击路径

5.2 填充方案混淆

标准Rabin使用PKCS#1等填充方案，但CTF题目常使用原始方案。我曾在一道题上浪费两小时，就是因为没注意到题目说明中的"no padding"提示。

5.3 编码转换问题

解密得到的数字需要正确转换为字节串。Python中要注意：

from Crypto.Util.number import long_to_bytes # 而不是直接使用bytes()

6. 完整解题脚本

以下是整合所有步骤的最终解题代码：

from Crypto.Util.number import inverse, long_to_bytes import math def legendre_symbol(a, p): """计算勒让德符号""" ls = pow(a, (p - 1) // 2, p) return -1 if ls == p - 1 else ls def mod_sqrt(a, p): """求解x² ≡ a mod p""" assert legendre_symbol(a, p) == 1, "不是二次剩余" if p % 4 == 3: x = pow(a, (p + 1) // 4, p) return x, p - x # 完整Tonelli-Shanks实现此处省略... def rabin_decrypt(c, p, q): n = p * q # 分别求解模p和模q的平方根 mp1, mp2 = mod_sqrt(c % p, p) mq1, mq2 = mod_sqrt(c % q, q) # 中国剩余定理组合四种情况 yp = inverse(p, q) yq = inverse(q, p) solutions = [] for mp in (mp1, mp2): for mq in (mq1, mq2): # CRT组合 x = (mp * q * yq + mq * p * yp) % n solutions.append(x) return solutions # 题目参数 n = 798321817573328185527646107613495929846147444322791353283989998016278802836109003612812499731758050699162101795605064970751325249020868811203722136266418794684919368609766869336308696738269726199383219515991467448076533010760265779495796183315027763039834855660464854310395417084671414082602200985927612450106785923475018941762695805104597296336734680684671441997445637318263621026088110334008878137547802826280994434901700160878386069980174904566013158024485677724116238262817453456359427490638279662852093914290377787289965798163293540442000281843339517329903053714121114296530274671571434023317019439859488273613 p = 3136613344949483826690446667480256392626468638370607457454515818992872287033042078245651295956858327870436443371543333504500526102278124006991700585180256248279464294934903121449076263873734210325094560839052977649 q = 2545580940228351080557481115403590697351364558898337805920808455106355296680008878315298802863983015431966989695130220349386896586935073621281803452260201 c = 0x4b27a5e0c413271060bab2ed2453b8f9b9b006b1a8b1c24b0470996e93cd30b3e3f8b7a0d6d0d6e07a0b1d0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6e0d6