can_you_guess_me
from Crypto.Util.number import *
from random import *
from secret import flag
q = getPrime(128)
n = 5
T = 2**48
E = 2**32
t = [randint(1,T) for i in range(n)]
e = [randint(1,E) for i in range(n)]
a = [(t[i] * flag - e[i]) % q for i in range(n)]
print('q =', q)
print('a =', a)
flag = "L3HSEC{" + hex(flag)[2:] + "}"
print('flag =', flag)
# q = 313199526393254794805899275326380083313
# a = [258948702106389340127909287396807150259, 130878573261697415793888397911168583971, 287085364108707601156242002650192970665, 172240654236516299340495055728541554805, 206056586779420225992168537876290239524]$a_i\equiv t_i\cdot s - e_i\pmod{q}$，给出5组 $a_i$，要恢复 $s$。
这里 flag 是从 secret 里 import 进来的，没有明确说明 $s$ 是多大，算是题目描述得不够清楚的一个地方，那我们就默认它和q一样为128比特。
这个问题形式其实比较接近 ACDP，但是是带模的。可以模仿它造格的思路来解决这题。因为 $s$ 比较大，得把它从目标向量里面消去。这里通过乘积把带 $s$ 的项都转化成一样的。
$$ \begin{align*} a_{i}t_{0} &\equiv t_{0}t_{i}s - e_{i}t_{0}\pmod{q} \\ a_{0}t_{i} &\equiv t_{0}t_{i}s - e_{0}t_{i}\pmod{q} \end{align*} $$
两式作差便消去了 $s$
$$ a_it_0-a_0t_i\equiv e_0t_i-e_it_0 \pmod{q} $$
记右边为 $x_i$，再把同余式展开得
$$ a_it_0-a_0t_i-k_iq= x_i $$
一开始这样造格：
$$ A = \begin{bmatrix} 2^{32} & 0 & 0 & 0 & 0 & -a_1 & -a_2 & -a_3 & -a_4 \\ 0 & 2^{32} & 0 & 0 & 0 & a_0 & 0 & 0 & 0 \\ 0 & 0 & 2^{32} & 0 & 0 & 0 & a_0 & 0 & 0 \\ 0 & 0 & 0 & 2^{32} & 0 & 0 & 0 & a_0 & 0 \\ 0 & 0 & 0 & 0 & 2^{32} & 0 & 0 & 0 & a_0 \\ 0 & 0 & 0 & 0 & 0 & q & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & q & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & q & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & q \\ \end{bmatrix} $$
对于 $v=(t_0,t_1,t_2,t_3,t_4,-k_0,-k_1,-k_2,-k_3)$
有 $vA=(2^{32}t_0,2^{32}t_1,2^{32}t_2,2^{32}t_3,2^{32}t_4,x_0,x_1,x_2,x_3)$
但是只能解到 T 是40比特多一点，以为是卡界了就换了思路，最后也没做出来。。
赛后看到群里一句话：
对啊，我们只用到了
$$ a_it_0-a_0t_i-k_iq= x_i $$
但实际上可以用到
$$ a_it_j-a_jt_i-k_iq= x_i $$
问题出在错误地认为额外的式子是和前4个式子线性相关的，但稍微分析一下就会发现并不相关。还是类似的格，我们把右上角换成如下矩阵（完整的矩阵过大不便展示）：
$$ \begin{bmatrix} -a_1 & -a_2 & -a_3 & -a_4 & 0 & 0 & 0 & 0 & 0 & 0 \\ a_0 & 0 & 0 & 0 & -a_2 & -a_3 & -a_4 & 0 & 0 & 0 \\ 0 & a_0 & 0 & 0 & a_1 & 0 & 0 & -a_3 & -a_4 & 0 \\ 0 & 0 & a_0 & 0 & 0 & a_1 & 0 & a_2 & 0 & -a_4 \\ 0 & 0 & 0 & a_0 & 0 & 0 & a_1 & 0 & a_2 & a_3 \\ \end{bmatrix} $$
就能搞定了。发现卡界的时候，记得检查一下还有没有没利用上的信息。
