Writeup for V&NCTF's crypto

whitegive

密码方向签到题，先分解n，详细推导过程如下：

$$
e\cdot d \equiv 1\pmod{lcm(p,p-1,q-1)}=k\cdot \frac{p\times(p-1)\times(q-1)}{gcd}+1
$$

$$
m^{e\cdot d}=m\pmod{((p-1)\times p)}\ 且\ m^{e\cdot d}=m\pmod{(q-1)}
$$

$$
m^{ed}\equiv m\pmod{((p-1)\times(q-1)\times p)}
$$

$$
e\cdot d=k\times p\times(p-1)\times(q-1)+1
$$

$$
(e\cdot d)^e=\sum^{e}_{i=0}C^i_e\cdot (k\times p\times (p-1)\times(q-1))^i\times 1^{e-i}=K\times p +1
$$

所以n很容易被分解，从而算得前一步的e，此时发现d较小（满足如下关系）

$$
\frac{1}{3}N^{\frac{1}{4}}\leq d\leq N^{0.292}
$$

我们这里使用维纳攻击，但是因为d相对于连分数还是比较大的，需要理解原理稍微优化一下，得到一个URL，下载后得到另一个的脚本，最后一步较为简单，先在sage里用small_roots算出来padding，然后related_message_attack即可解决

Strange_function & Strange_function_revenge

交互题，在data数组已知的情况下需要连续正确提交五次token

服务器提供计算f(x)满足
$$
f(x)=\sum^{len(token)}_{i=1}\frac{ord(token_i)}{x-data_i}
$$

显然ord(token[i])不超过130，而data却是2^32左右的数字，我们简单计算下
$$
130\div 2^{32}\times16\times5\approx 0.000002421438694000244140625
$$
$$
130\div 2^{17}\times 8 \times5\approx 0.0396728515625
$$
所以当我们的x逼近其中的一个data_i时对f(x)的影响微乎其微，基本可以忽略，所以可以通过这一点来得到token[i]，思路如下：

我们发现：

$$
f(data_1+1)=\sum^{len(token)}_{i=1}\frac{ord(token_i)}{(data_1+1)-data_i}=
$$

$$
ord(token_1)+\sum^{len(token)}_{i=2}\frac{ord(token_i)}{x-data_i}\approx
$$

$$
ord(token_1)+\sum^{len(token)}_{i=2}\frac{1}{\infty}= ord(token_1)
$$

当然分子部分显然离无穷还是比较远的，那么我们要么想办法扩大data之间的距离，要么想办法抵消或者减小掉后面部分的影响，因为data和token均不可控，这里我们选择如下的方法来逼近ord(token[i])
$$
k\times token(i)=\bigg(\frac{f(data_i+1)+f(data_i-1)}{2}\bigg)+\bigg(f(data_i+2)+f(data_i-2)\bigg)+\cdots
$$
交互时间大概几分钟

其实+1-1之后已经就消掉了，后面的只是为了更加确保

Factor

给了两组特别的RSA公钥，特点是共用一个d，但
$$
d=inv(e,(p+1)*(q+1))
$$
具体推导如下：

对于每一组公钥，我们有：
$$
e_i\cdot d=k_i(N_i+s_i)+1
$$
我们也可以给他们进行重新排序，使之满足：
$$
N_1<N_2<2N_1
$$
这里我们的推导过程如下：
$$
令M=\lfloor N_2^{\frac{1}{2}}\rfloor\ 有：
$$
$$
dM ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ =dM ~~~~~~~~~~~
$$
$$
e_1d-N_1k_1 ~~~~~~~~~~~~~~~ =1+k_1s_1 ~~
$$
$$
e_2d ~~~~~~~~~~~~~~~ -N_2k_2=1+k_2s_2 ~~
$$

这样的三个方程组我们可以写成这样的向量矩阵方程
$$
XB=V
$$
$$
X={\begin{bmatrix}
dM & e1 & e2
\end{bmatrix}}
$$
$$
B={\begin{bmatrix}
M & e1 & e2 \\
& -N_1 & \\
& & -N_2
\end{bmatrix}}
$$
$$
V={\begin{bmatrix}
dM & 1+k_1s_1 & 1+k_2s_2
\end{bmatrix}}
$$
LLL格基规约后即可算出 d和每一个not_phi，接着就可以轻松分解N，RSA正常解密即可