RSA n=p·q² 的二项式提示分解 + 二次剩余逐位还原((p±q)^e 与欧拉判别式)
crypto/rsa · verified
一句话结论
当 RSA 模数形如 n = p·q² 且给出 hint1=(p+q)^e mod n、hint2=(p−q)^e mod n 时,二项式展开后两式的奇次项相加抵消、含 q² 的项在模 n 下消失,因此 hint1+hint2 ≡ 2p^e (mod n),与 n 求 gcd 即得 p,再开方得 q;分解后,对于逐位加密 c_i = secret_i²·z^{m_i} mod n(z 是模 p、q 的非二次剩余),用欧拉判别式判断 c_i 是否为模 p 的二次剩余即可逐位还原 m_i(剩余→0,非剩余→1),最后把二进制串转回字节。
原理
- 模数结构:
n = p·q²(p、q 为素数,非半素数)。任何含q²因子的整数模 n 为 0,这是二项式化简的关键。 - 提示展开:
(p+q)^e = Σ C(e,k) p^{e-k} q^k,(p−q)^e = Σ C(e,k) p^{e-k} (−q)^k。- 两者相加时奇次项(k 为奇数)符号相反互相抵消,只剩偶数 k:
hint1+hint2 = 2·Σ_{k even} C(e,k) p^{e-k} q^k。 - k=0 项为
2p^e;k≥2 的偶数项都含q²(或更高次),模n=pq²为 0。因此hint1+hint2 ≡ 2p^e (mod n)。 - 于是
gcd(hint1+hint2, n)包含素因子 p;2p^e不含 q,故 gcd 通常恰为 p(若返回 p 的倍数需按素数性判断)。q = sqrt(n/p)。 - 注意:文章把单条 hint 简写成
p^e ± q^e并不严格(奇次交叉项仍在),真正成立的是“两式相加”的结论;按 gcd 相加式实现即可。 - 二次剩余逐位:z 的选取保证
z^((p−1)/2) ≡ −1 (mod p)且模 q 同样为 −1,即 z 在模 p、q 下都不是二次剩余。密文c_i = secret_i² · z^{m_i} mod n,其中m_i ∈ {0,1}: - 若
m_i=0,c_i ≡ secret_i² (mod p)是二次剩余,欧拉判别式c_i^((p−1)/2) ≡ 1 (mod p); - 若
m_i=1,c_i ≡ secret_i²·z (mod p),二次剩余乘非剩余仍是非剩余,判别式≡ −1 (mod p)。 - 因此只需在模 p(或 q)下计算
pow(c_i,(p−1)//2,p)即可恢复每个十进制位。 - 位序与还原:加密端把 flag 转整数后
int(bin(m)[2:])当成十进制数,再反复%10、//10从最低位逐位加密,所以ciphertext[0]对应最低位。解密得到的 0/1 串要反转,再int(bits[::-1], 2)转字节。 - 为什么有效:模数分解泄露 + 非二次剩余的选择使每位密文的二次剩余性唯一对应明文位;这是“把整数分解信息与二次剩余判定结合”的典型 CTF 构造。
触发条件
- 题目/实现给出
n = p·q²、指数 e(如 65537)、hint1=(p+q)^e mod n、hint2=(p−q)^e mod n。 - 另给非二次剩余 z(满足模 p、q 的欧拉判别均为 −1)与逐位密文列表。
- 明文被编码为二进制字符串再当作十进制数逐位加密(每位 0/1)。
- 典型 CTF 场景;真实系统中若密钥生成重复使用素因子或泄露 p±q 的幂,同样会破坏 RSA。
利用步骤
- 计算
g = gcd(hint1 + hint2, n);若 g 不是素数,尝试gcd(hint1 − hint2, n)、对 g 分解或结合n/g判断。 p = g,q = isqrt(n // p)(验证p*q*q == n)。- 对每个密文
c_i计算pow(c_i, (p-1)//2, p):结果为 1 → 该位 0;结果为 p−1 → 该位 1。 - 把得到的 0/1 序列反转(ciphertext[0] 是最低位),
int(bits[::-1], 2)后long_to_bytes。 - 若模 p 判别失败(p 选取不对),改用模 q 或重新验证分解。
PoC
from math import gcd, isqrt
from Crypto.Util.number import long_to_bytes
p = gcd(hint1 + hint2, n)
assert n % (p * p) != 0
q = isqrt(n // p)
assert p * q * q == n
bits = ""
for c in ciphertext:
if pow(c, (p - 1) // 2, p) == 1:
bits += "0"
else:
bits += "1"
flag = long_to_bytes(int(bits[::-1], 2))
print(flag)
变体与关联
- 提示形式变体:给
(p+q)^e与(p−q)^e的任意线性组合/差值;只要能把奇次项消掉或把 q² 项分离即可。 - 模数变体:
n=p^2·q(交换角色)、多素数n=p·q^2·r等,思路相同:找模 n 下含高次素因子的项。 - 关联卡:
crypto-rsa-hint-difference-gcd-factorization(提示差值 GCD)、crypto-rsa-two-linear-hints-small-coefficient-gcd(线性 hint 系数抵消)、crypto-rsa-perfect-square-modulus-p-squared(p² 模数)、crypto-rsa-known-prime-sum-quadratic-factorization(已知 p+q)。 - 边界:gcd 可能返回 p 的倍数或 1(提示构造退化/计算错误);z 若不是非二次剩余,逐位判定会失效。
检测与防御
- CTF/实现侧:RSA 密钥生成不要重复使用素因子(
n不能有平方因子);不要把(p±q)^e之类的中间值或非二次剩余提示与密文一起输出。 - 密码学审计:对 n 做平方因子检测(
gcd(n, φ 相关)、完全平方检测、isqrt验证);发现n=p·q²直接判定密钥不安全。 - 防御:使用标准库生成 RSA 密钥并校验 p≠q、n 无平方因子;敏感参数不出现在日志/调试输出中。