感想
前段时间在学校几位大佬的带领下参加了今年的第二届强网杯CTF，虽然最后没能进线下赛，也没拿到什么奖，我最后也只搞出来一个题，感觉还是挺有收获的，学到不少东西。
这届题目感觉上比网上看到的上一届的题目要难一些。
一开始我就完全放弃了 pwn 和 reverse 题，只希望能做出来道 web 的水题，然而还是太 naïve 了。这次 web 题的考点除了那道最水的 md5 的那道我都没接触过，最后看了其他人的 writeup 也是很懵逼，而且我对 php 也不熟，知道最后要生成俩 md5 一样的文件碰撞，不知道咋上传，最后是还是队友解决的。
有一道据说 AI 相关的 misc 题我也一直在看，还以为是生成对抗样本的，最后大佬们发现上传原图就行了？？？我一开始是试过用 sendall 直接传原图，而且本地跑他 server 的代码也可以通过比较，他那边的服务器就是不给我过。还学了半天 tensorflow, 结果只要分段传原图就行了？ 仿佛在刻意逗我笑。这题的收获就是只会调参的TensorFlow Boys 也不是好当的，以前都是用的 keras，到现在也没弄清楚 tf 的 API。
最没想到的密码学怒拿一个中的我最后唯一搞出来的是密码学的题，最后电脑上装了一堆科学计算的软件，PARI/GP, sagemath, gmpy
唯一的 writeup
nextrsa
这个题目几乎涵盖了 RSA 的所有考点…..
一直到最后才发现竟然一共有 10 关之多…
1
首先 nc , 与服务器交互。
第一关最简单，给出了三个字节各自的范围和sha256的结果。就暴力跑基本秒出。
因为每次连接产生的密文都是随机的，于是开始写了一个 socket 脚本提交结果, 密文从输出中用固定格式的正则找出来。一开始没想到能连续出这么多题，脚本就写的很随意，也给自己带来不少麻烦。
2
然后进入了正题，RSA。这一关给了一个比较小的 n，于是直接 factordb 上面找分解。
分解之后得 p, q, 进而得 phi, 一开始我是用的 PARI/GP 直接求逆算出来的 d，因为 n，e 一直没变，就硬编码到脚本里了。然后 m = pow(c, d, n) 即可得到明文。
我一开始以为这道是个水题，没想到接下来还有这么多关
3
这一关的特点是 e 非常的大， 于是就会导致 d 会很小。从网上找到了一个脚本，使用 wiener attack，专门针对这一类问题。改一下脚本的参数，然后就可以秒解出来 d。
得到 d 之后，照抄上一关的代码就好了。
4
这关花了不少时间，最后在 ctf-wiki 这个 gitbook 里面找到了已知部分明文的攻击方法。
并且看到了一个使用该算法的 github 的 repo
于是安装 sage, 继续修改代码, 直接秒解出来 m
./coppersmith.sage 脚本, 替换成题目里的值就好。
5
这关花的时间比较多，给出 了 n 和 next_prime(p) * next_prime(q)
因为一开始不想暴力跑,认为暴力跑范围太广了,于是花了很多时间去找有没有这类固定的题型，结果一直没找到。
最后经过简单计算后，打算暴力跑，果然秒出
$$n = p * q$$
分别设 间距 为 $t_1$ 和 $t_2$, 于是
$$ n_1 = (p + t_1) * (q + t_2) = pq + pt_2 + qt_1 + t_1t_2 $$
我们还知道:
$$ (pt_2 + qt_1)^2 - 4nt_1t_2 = (pt_2-qt_1)^2 $$
检测等号右边能否开方，开出来之后就可以联立
$$ pt_2 + qt_1 = n_1 - n - t_1t_2 $$
$$ pt_2 - qt_1 = \sqrt{(n_1-n-t_1t_2)^2 - 4nt_1t_2} $$
枚举 $t_1$ 和 $t_2$ 就可以算出 $p$ 和 $q$, 验证一下 $p * q$ 的结果是不是等于 $n$ 就可以了
至于枚举的范围，因为要保证被开方的是正数，于是整理出来了一个二次函数, $t_1 * t_2$ 的值受到了 $n_1-n$ 以及 $n$ 的制约
最后发现不用算也没事，$t_1$ 很小的时候就跑出来结果了……
具体见脚本 RSA4.py
for t1 in range(2, 478128, 2):
if t1 % 5000 == 0:
print(t1)
for t2 in range(2, 478128, 2):
if t1 * t2 >= 956252:
break
pt2_plus_qt1 = ((n1 - n) - t1 * t2)
pt2_minu_qt1 = pow(pt2_plus_qt1, 2) - 4 * n * t1 * t2
if gmpy.iroot(pt2_minu_qt1, 2)[1] is False:
continue
pt2_minu_qt1 = gmpy.isqrt(pt2_minu_qt1)
p = (pt2_minu_qt1 + pt2_plus_qt1) // (2 * t2)
q = n // p
if p * q == n:
print(p)
print(q)
sys.exit(0)
也是从这关开始，经大佬队友提醒， python 有一个 gmpy2 的库，可以求逆，开方，不用跑到 PARI/GP 的终端里面算….
6
这关的 n 也可以 factordb 分解，跟前面一样。
发现 p 和 q 相差较大，其实好像有一种特别的攻击方法，既然能查到，最后就没再仔细学这种方法。
7
这关是 小加密指数 $e = 3$ 的情况，可以枚举 c + k * N, 开三次方，就能得到 m
8
这一关给出了两个 n, n1 和 n2, 但是可以发现 n1 和 n2 果然并不互质，于是 gcd 一下得到其中一个因子，免去了分解的麻烦。
然后分别得到两个 n 的 p 和 q, 还是一样的办法，就可以得到两个明文了。
9
这一关是传说中的共模攻击。两个明文用同一个 n 和 不同的 e 来加密, 可以在不分解n的情况下还原出明文。网上找一下相关的文章可以看到相关的算法。
10
这一关给出了三对 n 和 c, 共用同一个 很小的e, 出题的意向比较明显,可以采用低加密指数广播攻击 ，正好队友做过类似的题目，给了我一个用中国剩余定理解决问题的代码，我就把代码硬插进脚本里跑，也是秒出。做完这一关终于见到了 flag
得到 flag
终于在 ok! 之后不是下一道题目…….
最后脚本还有一个小 bug, 没有改好， 就是 有一关服务器传过来的 “c=xxxx"的数据时而分两次接收到，时而一次性接收到，如果一次性收到脚本就会卡住，需要kill掉重新跑，不过并不影响拿到 flag
总结
我的水平还是太差了，羡慕白帽大佬特别是精通 pwn 和逆向的大佬们。
顺便想起来之前 52pojie 开放注册，我注册完之后到现在都没登录过。XD