Rabin 加密 e=2 解密:已知 p/q 用 (p+1)/4 或 Tonelli-Shanks 求模平方根,CRT 组合四个根并按明文筛选
crypto/rsa · verified
一句话结论
Rabin 加密就是 e=2 的 RSA:c = m² mod n(n=p·q)。已知 p、q 时,分别在模 p、模 q 下求 c 的平方根(p≡q≡3 (mod 4) 时直接 pow(c,(p+1)//4,p),否则用 Tonelli-Shanks),再用中国剩余定理把“± 根”的四种组合拼起来,得到模 n 的四个候选明文,按 flag 格式/冗余编码筛出唯一正确解。
原理
- 模素数平方根:若
m² ≡ c (mod p),则解为m ≡ ±r (mod p),其中r是任一平方根。欧拉准则判断可解性:c^((p-1)/2) ≡ 1 (mod p)时 c 是二次剩余;对p ≡ 3 (mod 4),有r = c^((p+1)/4) mod p,因为r² = c^((p+1)/2) = c·c^((p-1)/2) ≡ c。 - 一般素数用 Tonelli-Shanks:当
p ≡ 1 (mod 4)时(p+1)/4不是整数,需要 Tonelli-Shanks 算法(把 p−1 写成q·2^s,找非剩余 z,迭代求根);Sage 的sqrt(c, p)或Mod(c,p).sqrt()内部即此算法。 - CRT 组合:得到
m ≡ ±r (mod p)、m ≡ ±s (mod q)后,四种符号组合各对应模 n 的一个根(共 4 个)。用 CRT 系数inv_p = p^{-1} mod q、inv_q = q^{-1} mod p,可写出:a = (inv_p·p·s + inv_q·q·r) mod n、b = n − a、c' = (inv_p·p·s − inv_q·q·r) mod n、d = n − c',四个根即a,b,c',d(顺序取决于 r、s 的符号取法,全部列出即可)。 - 为什么要筛:Rabin 解密天生不唯一(四个根),正确明文只有一个。CTF 中按
long_to_bytes后是否可打印、是否含flag{/题目前缀、是否满足给定哈希/校验位筛选;工程实现则靠加密前的冗余编码(如加固定头、哈希)在解密后唯一确定。 - 与 Rabin 预言机攻击的区别:本卡是“已分解 n、求明文”的正常解密算法;
e=2且服务随机返回平方根时的预言机攻击(两次查询分解 N)见[[crypto-rsa-rabin-random-square-root-oracle]],两者场景不同。
触发条件
- 密文满足
c = m² mod n(题目给出e=2或省略 e、提示 Rabin)。 n=p·q且 p、q 已知,或已通过其它方式分解 n。- p、q 为奇素数;
p≡q≡3 (mod 4)时可用快速公式,否则需 Tonelli-Shanks/Sage。 - 明文有可识别的格式或额外校验信息用于在四个根中筛选。
利用步骤
- 确认
e=2、拿到n、p、q、c;验证p*q == n。 - 求
r = sqrt(c) mod p:若p % 4 == 3,r = pow(c,(p+1)//4,p);否则用 Tonelli-Shanks 或 Sagesqrt(Mod(c,p))。 - 同法求
s = sqrt(c) mod q。 - 计算 CRT 组合的四个根(
a、n-a、b、n-b)。 - 对每个根
long_to_bytes,按可打印性/flag 前缀/题目校验位筛选,得到正确明文。 - 若四个根都不像明文,检查 c 是否真的是二次剩余(欧拉准则)、p/q 是否写反或 e 是否为 2 的倍数。
PoC
p ≡ q ≡ 3 (mod 4) 的简化写法:
import gmpy2, libnum
p, q, n, c = ..., ..., ..., ...
inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)
mp = pow(c, (p + 1) // 4, p)
mq = pow(c, (q + 1) // 4, q)
a = (inv_p * p * mq + inv_q * q * mp) % n
b = n - int(a)
c2 = (inv_p * p * mq - inv_q * q * mp) % n
d = n - int(c2)
for x in (a, b, c2, d):
print(libnum.n2s(int(x)))
一般素数用 Tonelli-Shanks(或直接用 Sage sqrt(Mod(c,p))):
def Legendre(n, p):
return pow(n, (p - 1) // 2, p)
def Tonelli_Shanks(n, p):
assert Legendre(n, p) == 1
if p % 4 == 3:
return pow(n, (p + 1) // 4, p)
q, s = p - 1, 0
while q % 2 == 0:
q //= 2; s += 1
for z in range(2, p):
if Legendre(z, p) == p - 1:
c_ = pow(z, q, p); break
r = pow(n, (q + 1) // 2, p); t = pow(n, q, p); m = s
if t % p == 1:
return r
i = 0
while t % p != 1:
temp = pow(t, 2 ** (i + 1), p); i += 1
if temp % p == 1:
b = pow(c_, 2 ** (m - i - 1), p)
r = r * b % p; c_ = b * b % p; t = t * c_ % p; m = i; i = 0
return r
r1 = Tonelli_Shanks(c, p)
r2 = Tonelli_Shanks(c, q)
from sympy.ntheory.modular import crt
for a1 in (r1, p - r1):
for a2 in (r2, q - r2):
m, _ = crt([p, q], [a1, a2])
print(long_to_bytes(m))
变体与关联
- Rabin 预言机攻击:
e=2服务随机返回平方根,用gcd(a−y,N)分解 N,见[[crypto-rsa-rabin-random-square-root-oracle]];本卡假设已分解 n。 - Schmidt-Samoa:
N=p²q、解密在p·q上进行且解唯一,见[[crypto-rsa-schmidt-samoa-known-d-factor]];与本卡的 e=2 四根不同。 - AMM/一般模平方根:
e=2可视为 AMM 的特例,模 p 求根算法见[[crypto-rsa-amm-nth-root-mod-p-unit-roots-crt]]。 - 其它分解后解密:Pollard p−1(
[[crypto-rsa-pollard-pminus1-smooth-prime]])、Williams p+1([[crypto-rsa-williams-p-plus-1-smooth-factor]])用于先得到 p/q,再回到本卡求根。
检测与防御
- 实现侧:Rabin 加密必须配合冗余/确定性编码(固定头、哈希、OAEP 类方案),解密后校验冗余以唯一选根;不要把四个候选根或选根提示返回给调用方。
- 密钥侧:使用足够大的随机素数(避免 Pollard p−1/p+1、费马等分解),私钥与明文不重复使用。
- 测试边界:CTF 场景仅在本地求解,不对真实系统发起预言机查询。