♧ Godown 安全知识树

hint = n + noise·(p+q+noise) 的小噪声泄露:分解 hint-n 恢复 p+q 并解二次方程

crypto/rsa · verified

一句话结论

当题目给出 hint = n + noise·(p+q) + noise²(noise 只有 40 bit)时,hint - n = noise·(p+q+noise) 是一个「小素数 × 1025 位整数」的乘积,直接对 hint-n 分解即可拿到 noise,进而得到 p+q,再由 (p+q)² - 4n 开方恢复 p-q,解出 p, q。

原理

  • 展开 hint:hint = pq + noise·p + noise·q + noise² = n + noise·(p+q+noise),故 Δ = hint - n = noise·(p+q+noise)。
  • noise 是 40 bit 素数,而 p+q+noise 约 1025 bit;Δ 的唯一小因子就是 noise,试除到 2^40 量级(或直接 factor(Δ))即可分离。
  • 得到 noise 后 s = p+q = Δ/noise - noise,于是 p, q 是方程 x² - s·x + n = 0 的两根:p-q = sqrt(s² - 4n),p = (s + p-q)/2。
  • 为什么成立:RSA 的安全性依赖 n 的因子不可知;但任何把 p、q 的线性组合(尤其 p+q)以「几乎明文」的形式泄露出来的 hint,都等价于泄露因子分解——p+q 与 n 两个方程即可解出两个未知数。

触发条件

  • 给出 n、e、c 及形如 n + a·(p+q) + a² 的 hint,其中 a 足够小(可分解、可试除);
  • s² - 4n 为完全平方(一定成立,因为 s=p+q);
  • e 与 φ 互素。

利用步骤

  1. 计算 Δ = hint - n。
  2. 分解 Δ,取小因子 noise(或用 gcd(Δ, n)、试除小素数集合确认)。
  3. s = Δ // noise - noise,得到 p + q。
  4. 解 x² - s·x + n = 0 得 p, q。
  5. φ = (p-1)(q-1),d = e^{-1} mod φ,m = c^d mod n。

PoC

from Crypto.Util.number import long_to_bytes, inverse
from sage.all import var, solve

n = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565066224724927142875488372745811265526082952677738164529563954987228906850399133238995317510054164641775620492640261304545177255239344267408541100183257566363663184114386155791750269054370153318333985294770328952530538998873255288249682710758780563400912097941615526239960620378046855974566511497666396320752739097426013141
e = 65537
c = 1443781085228809103260687286964643829663045712724558803386592638665188285978095387180863161962724216167963654290035919557593637853286347618612161170407578261345832596144085802169614820425769327958192208423842665197938979924635782828703591528369967294598450115818251812197323674041438116930949452107918727347915177319686431081596379288639254670818653338903424232605790442382455868513646425376462921686391652158186913416425784854067607352211587156772930311563002832095834548323381414409747899386887578746299577314595641345032692386684834362470575165392266454078129135668153486829723593489194729482511596288603515252196
hint = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565315879035806034866363781260326863226820493638303543900551786806420978685834963920605455531498816171226961859405498825422799670404315599803610007692517859020686506546933013150302023167306580068646104886750772590407299332549746317286972954245335810093049085813683948329319499796034424103981702702886662008367017860043529164

noise = 942430120937            # 分解 hint-n 得到的 40 bit 小因子
s = (hint - n) // noise - noise # p + q
assert s * s - 4 * n >= 0

import math
disc = math.isqrt(s * s - 4 * n)
p = (s + disc) // 2
q = n // p
assert p * q == n

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
print(long_to_bytes(pow(c, d, n)))

变体与关联

  • 变体:hint 以 a·(p+q) + b 形式出现(系数已知)时同样先减去已知项再分解;若 a 较大无法分解,可用 gcd(a·(p+q), n) 或 Coppersmith 求小根。
  • 变体:泄露 p-q、p+q+常数、p²+q² 都可转成「和/差已知」的二次方程求解。
  • 关联:[[crypto-rsa-known-prime-sum-quadratic-factorization]](已知 p+q 解二次)、[[crypto-rsa-hint-difference-gcd-factorization]](hint 差值取 gcd)、[[crypto-rsa-known-p2-plus-q2-cornacchia-factor]](已知 p²+q²)。
  • 边界:noise 与 p+q 同量级(不可分解)时本方法失效,需要格/Coppersmith;hint-n 不是 noise 的倍数说明 hint 形式假设错误。

检测与防御

  • 检测(CTF 视角):看到 hint ≈ n 且差值是「小素数 × 大数」,直接分解差值。
  • 防御(实现视角):不要泄露 p、q 的任何线性组合;必须给提示时改成「单向校验值」(哈希/截断)并对小因子做掩码;密钥生成后校验 hint 不含 p+q 的结构信息。