♧ Godown 安全知识树

二维格解线性同余双小未知量:[[1,A],[0,M]] 约出 (x,y),余数/偏移未知时再枚举收尾

ctf/crypto · verified

一句话结论

当题目给出一条模线性关系 A*x + y ≡ 0 (mod M),且两个未知量 x、y 的位长都明显小于模数 M 时,把 [[1, A], [0, M]](第二行符号按等式方向取 ±)作为二维格基做 LLL,最短向量就是 (x, -y) 一类组合;从向量还原 x、y 后即可继续 RSA 解密。若余数或偏移只是“很小但未知”,LLL 先给出去掉小偏移的基值,再对小参数做枚举并用明文格式筛选即可。

原理

  • 一般形式:A*x + y ≡ 0 (mod M) 等价于存在整数 k 使 A*x + y = k*M。取格基

text B = [[1, A], [0, M]]

整数系数向量 (x, -k) 在 B 上的像为 (x, x*A - k*M) = (x, -y),因此格中存在短向量 ±(x, y)。若把第二行写成 -M,对应系数取 (x, k),结论相同,只需在还原时按符号处理。 - 为什么 LLL 能找到:二维格的行列式 det(B) = M,Hermite 上界为 ||v|| <= sqrt(2) * sqrt(M);当 sqrt(x^2 + y^2) 明显小于 sqrt(M)(实际要留出 LLL 的近似因子余量)时,规约结果的第一行就是这个目标短向量。二维格里 LLL 基本等价于高斯约减,稳定性好。 - 形态一:模逆隐藏的等式(ezRSA):hint = (p - C) * inverse(s, M) % M 两边乘 s 得 hint*s = p - C + k*M,即 s*hint - k*M = p - C。取 [[1, hint], [0, M]],系数 (s, -k) 得到 (s, p - C);LLL 恢复 s 与 p - C,加回常数 C 即得 RSA 素数 p。本形态中 s 只有 256 bit、p - C 约 512 bit,而 M 有 5048 bit。 - 形态二:大模数下的小素数因子(LRSA):先由 gcd(P*P*Q, P*Q*Q) = P*Q 拆出 P = (P*P*Q)/(P*Q)、Q = (P*Q*Q)/(P*Q);题目关系 t = (p*P - 58*P + q) % Q 即 t - q = (p - 58)*P + k*Q,也就是 (p - 58)*P - k*Q = t - q。取 [[1, P], [0, -Q]],LLL 得到 (p - 58, t - q),于是 p = |v0| + 58、q = |v1| + t。这里 p,q 只有 1023 bit,Q 有 2048 bit。 - 形态三:余数很小但未知(Lattice1):((p - r)*a + q) % b = x,其中 x < 50、r 只有 14~15 bit、b 有 1536 bit。展开 (p - r)*a + q - x = k*b,取 [[1, a], [0, b]],LLL 得到 (p - r, x - q)。由于 r 和 x 本身未知,短向量只给出 p - r 与 q - x;之后枚举 r ∈ [2^14, 2^15)、x ∈ [0, 50),对每组 P = (p - r) + r、Q = (q - x) + x 尝试 RSA 解密并按 flag 前缀筛选。 - 为什么这些题都能用二维格:共同点是“一条模线性方程 + 两个搜索空间远小于模数的未知量”。未知量越短、模数越大,目标向量相对格基越短,LLL 越稳。若两个未知量位长相差悬殊,可像模逆藏数场景那样乘缩放因子配平两个分量。

触发条件

  • 题目公开一条模线性关系(可能以模逆、取模等式、带小余数的不等式形式给出),且能将未知量整理成 A*x + y ≡ 0 (mod M)。
  • x、y 的位长上界已知且 sqrt(x^2 + y^2) 明显小于 sqrt(M)(用 Hermite 判据先估算)。
  • 对小余数/小偏移变体:剩余的小参数范围可枚举(几十到几万次),且后续步骤(RSA 解密、明文格式)能验证唯一解。
  • 已知模数或可先恢复模数(如通过 GCD 拆分乘积)。

利用步骤

  1. 整理等式:把题目关系改写成 A*x + y = k*M;确定哪个是“模数”、哪两个是短未知量。
  2. Hermite 估算:n = 2、det = M,比较 sqrt(x^2 + y^2) 与 sqrt(2*M);差距越大越稳,若太接近先考虑缩放或增加信息。
  3. 构造格基并 LLL:M = Matrix(ZZ, [[1, A], [0, ±mod]]),M.LLL();先看第一行的两个分量是否符合预期位长。
  4. 还原未知量:按符号/常数还原(如 p = |v0| + 58、q = |v1| + t、p = |pc| + C);代入原等式或做整除/PQ 关系验证。
  5. 处理未知小量:若短向量只是 (p - r, q - x),枚举 r、x 的候选,构造 P、Q 并计算 n % P == 0 或解密后匹配 flag。
  6. 继续常规密码流程:恢复素因子后求 d = e^{-1} mod φ(n),解密并检查明文。

PoC

from sage.all import *
from Crypto.Util.number import long_to_bytes

# 形态一(ezRSA):hint = (p - C) * inverse(s, M) % M
Mmod = 28858066896535909755146975040720031655813099454455588895434479778600245612915775220883088811806723015938061791264869678085304248608125313205719043320256733514389739252845381708094678596099621503299764646358765107958130065721737938646850422959290465490270263553423913213684958592738500488797707239673645370968467090153285601432966586133693641854092761919184904521240074718850103356119966387029699913571443658384564840234765103070736676067458391659605655580766436276719610283460962533141261830775028138998594269732067550977245136631815804641115446066102981044849495663224005844657686979516481904043008222498344271373989609634617315702887646444506965035406154183377067490922195507071571055579654138590566650703038341939225657159668601565182939447340585110418258653618384852356058444795156595720943362884361136229430356254095673818462046182310826133487611183265532844700265640889105864909560170846171486510513240630480729194415061752698286990999064594811803482429976978688266632277914610443963726561921790718480343488391563503774868490108659902216386976683532579945706490286814310031310144410303859633785939399012605326754445715302492704458881700872467560968264583996658711892595658439058034434031646411995511168849724976850557976639662545139917517675296224197763447929417263845949813741362574641118781293171167041592771305352186419565096347024619027397784780864922205105185970180629777320680707022011697404359388540366320053501502698747763307336114482530784826238326983596966436776918503653153420281803168537703048371580451
hint = 24302462761412867722556483860201357169283131384498485449193507018526006760633350601593235386242712333885826513399701577522498685938541691414316724804357523659514319083860507720945068584985970098437482386854188516742033184163273293005356970701527614010961471490166306765208284126815267752826036846338185010168551115391901008731195800723630612524215610302192763771954146943262822909368086155537366851998954401585888789660061750804720858175620022924944428882337005545535959410243692854073069775794945154943244522898330286785483043492678802461244624116832548150221211726044545331789932659966539042635768789637635754297830131948383991027466194455817875377950516103513735000718642093769229006510961952865719649517629939801014585849419818774317178973918720330390674833583065434312010539617630210110724391629534996688713945139529416075521015600392479980677759342058040778532467875961508475990300178277703011765698425360329342396347848373844031930655143343217447877587074485794273364964346235973542157189093330870952677683308479410235841331914353677363106473914986073397716367455628483060709281215783434084559550690248426391913205234184130354155776334292729262232484610747771114078013979494659835579574006801652858265173309736540235377076956677464263798132149783780830729103485354096234062135454873557941791812722418582207577124971978987895472250326100927372068822672582017222521124179752698654114839303426099426224351872025466618402675104161895600513776962289703455252021742990686505176582638132300246212598903123706906104217087
C = 297498275426
n = 99499509473364452726944770421623721217675378717234178828554602484867641740497277374806036356486848621495917213623425604565104435195783450029879177770305417469850119739921527698744700219067563802483159458398895082044997907953256062342593605652927874232404778144112740505724215742062859322375891810785229735653
e, c = 65537, 11223534598141520071392544441952727165225232358333005778273904279807651365082135278999006409297342081157139972503703772556228315654837441044781410960887536342197257046095815516053582104516752168718754752274252871063410625756822861003235434929734796245933907621657696650609132419469456238860601166224944487116

L = Matrix(ZZ, [[1, hint], [0, Mmod]]).LLL()
s, pc = map(abs, L[0])
p = pc + C
q = n // p
d = inverse_mod(e, (p - 1) * (q - 1))
print(long_to_bytes(int(power_mod(c, d, n))))
# 形态二(LRSA):gcd(P*P*Q, P*Q*Q) 得 P*Q,再拆出 P、Q
PQ = gcd(P2Q, PQ2)
P, Q = P2Q // PQ, PQ2 // PQ
L = Matrix(ZZ, [[1, P], [0, -Q]]).LLL()
p = abs(int(L[0][0])) + 58
q = abs(int(L[0][1])) + t
# 形态三(Lattice1):((p-r)*a+q) % b < 50,先 LLL 再枚举 r, x
L = Matrix(ZZ, [[1, a], [0, b]]).LLL()
p_r, q_x = map(abs, L[0])
for r in range(2**14, 2**15):
    for x in range(50):
        P, Q = p_r + r, q_x + x
        if P * Q == 0:
            continue
        try:
            d = inverse_mod(65537, (P - 1) * (Q - 1))
        except ZeroDivisionError:
            continue
        m = power_mod(c, d, P * Q)
        if b'NSSCTF' in long_to_bytes(int(m)):
            print(long_to_bytes(int(m)))
            break

三个形态都能在 LLL 输出的第一行直接看到约 512/1023 bit 的短分量;运行后分别得到对应 flag。

变体与关联

  • 缩放配平:当 x 与 y 位长差很大时,给其中一个分量乘 2^k 再拼格(见 [[ctf-crypto-lll-modular-inverse-small-multiplier]] 的 2×2 缩放做法);本组题目两个分量量级接近或都远小于模数,可先直接 LLL。
  • 余数未知更一般化:小余数可来自掩码、截断、错误注入等;只要上界足够小,就可以把“余数”并入短向量,再用小范围枚举或 CVP 处理。
  • 更多样本:只有一条关系时只能解二维格;有多条同未知量的模方程时可联立成更高维格,或用 HNP 的连分数/Kannan 嵌入方法(见 [[ctf-crypto-hnp-2h-continued-fraction-kannan-embedding]]、[[ctf-crypto-lll-hidden-short-vector-kannan-embedding-lwe]])。
  • 边界:若未知量接近模数位长、或短向量与格基其他向量长度差不足,LLL 不保证约出目标;此时需要更多信息、BKZ 或换问题建模。
  • 关联:[[ctf-crypto-lll-modular-inverse-small-multiplier]](t·m^{-1} mod g 的二维缩放格,方程形态不同);[[ctf-crypto-noise-crt-lattice-recovery]](含噪 CRT 的格恢复)。

检测与防御

  • CTF 识别:题目同时给出大模数与“某个小素数/小随机数参与的模线性等式”(模逆、取模后的小余数、带小偏移的乘积)时,优先估计未知量位长并尝试二维格。
  • 设计视角:RSA/同余方案中不要让小素数、小随机数以线性方式出现在模等式里;模数应与秘密同量级或引入足够噪声,避免秘密成为格的短向量。
  • 实现视角:若必须公开 a*x + y mod M 这类关系,应保证 x、y 不可枚举或位长接近 M,并对异常输入做来源校验。