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与φ互素。
利用步骤
- 计算
Δ = hint - n。 - 分解
Δ,取小因子noise(或用gcd(Δ, n)、试除小素数集合确认)。 s = Δ // noise - noise,得到p + q。- 解
x² - s·x + n = 0得p, q。 φ = (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的结构信息。