Writeup for MAR DASCTF's crypto
Writeup for MAR DASCTF’s crypto
crypto_threshold
签到题，给了LCG的所有参数，而且求的还是后一位，求得 $e$
RSA部分给的_lambda和我上次出的VNCTF的hint是一个样子，求得明文
FeedBack
给了个函数
1 | def cycle(c:list,a:list)->int: |
功能就是把 $c$ 和 $a$ 两两相乘再相加
显然如果有 $key$ ，逆推回去就很容易，那么就想办法找 $key$ 的关系，因为有
$$
c = \sum_{i=1}^{lenth}m_i\cdot key_i
$$
结合数据即
$$
{\begin{bmatrix}
x_1&x_2&x_3&\cdots&x_n \\
x_2&x_3&x_4&\cdots&x_{n+1} \\
\vdots&\vdots&\vdots&\ddots&\vdots \\
x_n&x_{n+1}&x_{n+2}&\cdots&x_{2n} \\
\end{bmatrix}}
\cdot
{\begin{bmatrix}
key_1 \\
key_2 \\
\vdots \\
key_n \\
\end{bmatrix}}
=
{\begin{bmatrix}
x_{n+1}&x_{n+2}&x_{n+3}&\cdots&x_{2n}
\end{bmatrix}}
$$
拿到 $key$ 之后，想怎么做怎么做
son_of_NTRU
数字类的NTRU，甚至是原题，抄起之前的exp直接就秒了（
NTRU原理不多说了，对矩阵
$$
M=
{\begin{bmatrix}
h&1\\
p&0
\end{bmatrix}}
$$
一定存在一个向量 $\vec{v}=(f,-k)$ 满足
$$
\vec{v}\cdot M=\vec{x}=(g,f)
$$
而且是最短的，格基规约后就能拿到 $g$ 和 $f$ 了
threshold
还nm是个NTRU，出题人是有多喜欢NTRU
多项式下的NTRU，构造矩阵
$$
B=
{\begin{bmatrix}
\pmb{1}&\pmb{h(x)} \\
\pmb{0}&\pmb{q}
\end{bmatrix}}
$$
格基规约后拿最短的作为新的 $f(x)$ 和 $g(x)$ 重新实现一下解密就能求得 $m(x)$
wechat
