Problem: [LitCTF 2025]baby
思路
有data\equiv m^{-1}t\pmod{g}，因为t未知，故考虑将代求的m移到等式另一边，得到：
data\cdot m\equiv t\pmod{g}
那么可以得到一条线性方程：
data\cdot m+kg=t
构造格：
\pmb{B}=\left(\begin{matrix}
1&data\\
0&g
\end{matrix}\right)
有(m,k)\pmb{B}=(m,t)，但是t是150位的，m猜测大于150位，那么有||(m,t)||\approx m，而：
2\cdot|\det(\pmb{B})|^{1/2}\approx2^{256}
大概率是会导致2\cdot|\det(\pmb{B})|^{1/2}<||(m,t)||的，那么要进行配平，给最右侧一列配上一个数K可以得到：
\pmb{B}'=\left(\begin{matrix}
1&K\cdot data\\
0&Kg
\end{matrix}\right)
此时有2\cdot|\det(\pmb{B}')|^{1/2}\approx2^{256}\sqrt{K}，若要满足2\cdot|\det(\pmb{B}')|^{1/2}\ge||(m,t)||则需要使2^{256}\sqrt{K}尽可能接近m，经过测试可以知道K=2^{128}的时候可以得到flag
EXP
from Crypto.Util.number import *
g = 7835965640896798834809247993719156202474265737048568647376673642017466116106914666363462292416077666356578469725971587858259708356557157689066968453881547
data = 2966297990428234518470018601566644093790837230283136733660201036837070852272380968379055636436886428180671888655884680666354402224746495312632530221228498
K = 2**128
L = matrix(ZZ, [[1, data * K], [0, g * K]])
res = L.LLL()[0]
print(long_to_bytes(int(abs(res[0]))))
