RSA Pell 方程 hint 攻击:已知 x·p+y·q 且 x²-D·y²=1,用韦达定理求 xp/yq 后连分数解 Pell 还原 p、q
crypto/rsa · verified
一句话结论
当题目给出 hint = x*p + y*q,且 (x, y) 是 Pell 方程 x² - D·y² = 1 的解时,令 a = x*p、b = y*q,可推出 a、b 是 z² - hint·z + x·y·n = 0 的两根;又因 x/y 逼近 √D,可用连分数枚举 Pell 解 (x, y),对每组检查判别式 hint² - 4·x·y·n 是否为完全平方,命中即解出 a, b,再 p = a/x、q = b/y 完成分解。
原理
- 构造二次方程消去 p、q:设
a = x*p、b = y*q,则a + b = hint,且a² - a·hint = x²p² - x·p·(x*p + y*q) = -x·y·p·q = -x·y·n; 同理b² - b·hint = -x·y·n。所以a, b都满足z² - hint·z + x·y·n = 0,由韦达定理即为此方程的两根。 - 判别式给出可验证条件:该二次方程的判别式为
Δ = hint² - 4·x·y·n。只要(x, y)猜对且a, b为整数,Δ必须是完全平方数;开方后a, b = (hint ± √Δ)/2。 - Pell 解可枚举:
x² - D·y² = 1的全部正整数解由基本解(√D的连分数收敛子)的幂给出,也可用递推x_{i+1} = x₁x_i + D·y₁y_i、y_{i+1} = x₁y_i + y₁x_i生成。题目通常给较小的D(例0x1337),基本解很快求出,解序列的规模有限(x, y与 512 位素数同量级),枚举几十项即可覆盖。 - 为什么能恢复 p、q:真实
(x, y)必在 Pell 解序列里;一旦找到使Δ为平方的(x, y),就得到a = x*p、b = y*q,整除即得两个 1024 位素数,最后常规φ = (p-1)(q-1)、d = e⁻¹ mod φ解密。 - 与“Pell 生成素数”的区别:那种场景是
p = next_prime(x_k)、q = next_prime(y_k),攻击靠枚举 k 与gcd(p·q, n);本场景的素数本身随机,泄漏的是因子与 Pell 解的线性组合x*p + y*q,攻击靠二次方程 + 判别式。
触发条件
- 已知
n、e、c与一个整数hint,且题目/源码提示hint = x*p + y*q。 (x, y)满足某 Pell 方程x² - D·y² = 1,D已知且较小(可求基本解并枚举解序列)。p、q为常规大素数(本例各 1024 位),hint与√n同量级。- 攻击者能运行 Sage(连分数、多项式/整数开方)。
利用步骤
- 读题确认
hint = x*p + y*q与 Pell 方程参数D;令a=xp, b=yq,写出方程z² - hint·z + x·y·n = 0。 - 用连分数求
√D的基本解(x1, y1):遍历i取收敛子(numer, denom),检查numer² - D·denom² == 1。 - 按递推生成 Pell 解序列
(x, y),逐个计算Δ = hint² - 4·x·y·n。 - 判断
Δ是否为完全平方;若是,解出a=(hint+√Δ)/2、b=(hint-√Δ)/2,令p=a//x、q=b//y,断言p*q == n。 - 常规 RSA 解密:
d = pow(e, -1, (p-1)*(q-1)),m = pow(c, d, n),long_to_bytes(m)得 flag。 - 若解序列跑完无平方判别式,检查
D、hint 符号或a/b交换(x,q与y,p配对)后重试。
PoC
from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
def solve_pell(N, numTry=100):
cf = continued_fraction(sqrt(N))
for i in range(numTry):
denom = cf.denominator(i)
numer = cf.numerator(i)
if numer^2 - N * denom^2 == 1:
return numer, denom
return None, None
def gen_pell(D):
x, y = solve_pell(D)
xs, ys = [x], [y]
while True:
yield xs[-1], ys[-1]
xs.append(xs[0] * xs[-1] + D * ys[0] * ys[-1])
ys.append(xs[0] * ys[-1] + ys[0] * xs[-1])
# c, n, hint, D 由题目给出;e = 0x10001
for (x, y) in gen_pell(D):
delta = hint**2 - 4 * x * y * n
if iroot(delta, 2)[1]:
z = var('z')
sol = solve(z**2 - hint*z + x*y*n == 0, z, solution_dict=True)
a, b = int(z.subs(sol[0])), int(z.subs(sol[1]))
a, b = (a, b) if a > b else (b, a)
p, q = a // x, b // y
break
assert p * q == n
d = pow(e, -1, (p - 1) * (q - 1))
print(long_to_bytes(int(pow(c, d, n))))
变体与关联
- hint 形式变体:
hint = p + q、p - q、a*p + b*q等线性组合可用同类二次方程/韦达思路(不含 Pell 约束时直接解一元二次);Pell 约束的价值是把(x, y)的搜索空间从二维压到一维解序列。 - Pell 生成素数:
p = next_prime(x_k)、q = next_prime(y_k)的弱密钥场景见[[crypto-rsa-pell-equation-prime-generation]],攻击方式不同。 - 相关卡:已知
p+q/p²+q²的分解见[[crypto-rsa-known-prime-sum-quadratic-factorization]]、[[crypto-rsa-known-p2-plus-q2-cornacchia-factor]];两个线性 hint 求 gcd 见[[crypto-rsa-two-linear-hints-small-coefficient-gcd]]。 - 边界:若
D很大、Pell 解数量级远超素数规模,或x, y与p, q交错配对导致a//x不整除,需要扩大枚举/检查配对;判别式非平方就继续下一组。
检测与防御
- 出题/实现侧:不要泄漏因子的线性组合(哪怕带 Pell 约束);RSA 素数应独立随机生成,避免任何可枚举的代数关系。
- 参数选择:若必须给出 hint,确保
D、x、y的组合空间足够大且 hint 不暴露因子量级;对 hint 做模 n 归约并混入随机量。 - 测试边界:CTF 题目只对本地实例求解,不涉及真实系统。