今年3月的9号和10号是bctf资格赛。
在游玩了两天之后，来分享一下比赛中遇到的两道好玩的题目~
##0x01 他乡遇故知 题目链接
这题非常有意思。
<!-- more -->
点击链接进去后是个txt，文本是Tupper和Mitnick的对话。
开头几句话还挺正常，后来就变成了一串串数字，让人摸不清头脑。
然而，在正常的话中，Tupper提到了他的paper（论文）。于是google搜，”tupper 论文“，居然找到了一篇Matrix67大神一篇07年的博文。
博文内容大致意思是一个函数的图象里显示这个函数本身。其中，有个变量n引起了我的注意。思考：如果把txt对话中的数字替换为n，那函数的图像是什么样的呢？
随后就是上wiki，google学术等搜这玩意儿。
先是找到了一个javascript版的实现方案，于是下载到本地，改了改变量，把n替换成了txt中的数字串。居然显示出了字母！
这个发现让我眼前一亮！
于是尝试吧所有的数字都放进去看看结果，但是。。。
后面比较关键的信息，被人动了手脚！
后来，我才发现前面的数字串显示出的图像中的字母，并不能正确地释义，读不懂啊！
所以我猜测估计这后面还有些信息没显示完。无奈这个javascript写得太乱。。我改了好久都改不出什么所以然。
最后，终于wiki上找到了个“塔珀自指公式”，正好就是这个。
在wiki页面的底部外部链接中，有一个这个公式的python版本实现。经过一番研究，发现这个python脚本可以把函数图像以字符形式输出到控制台！
又是让我兴奋不已，在几番调试后终于显示出了完整的信息。
以下是解读后的信息：
Tupper: LOL, I think they bastard hacks nothing about math.
Mitnick: It's not safe! You should use 61. 17 is too weak.
Tupper: Fine, then , here is your flag in 61.
这之后的对话又是让人看不懂的了。
不过结合他们对话的信息，以及wiki上的内容，可以想到Tupper是把函数中的17换成了61加密了Flag.
于是改一下Python代码，把输出重定向到文件，再运行就能看到Flag了！
（图比较长，就截取开头一点点好了。。）
####0x02 地铁难挤
这个题吸引我的原因是 题目描述中的那句充满信息学竞赛味道的“设计一个尽量少移动次数的方案”。
此题分为两个部分。
我先是nc了题目给出的 ip:port 之后，发现一来就要我求出一个X值，使得这个等式成立。
等式中的两个字符串都是随机的，而且经过了SHA-1加密。
然而X输出错误一次便会断开连接。
显然不能对SHA-1下手，于是考虑爆破。
于是我就写了个py脚本。由于没什么经验，我写了个单线程爆破的脚本，所以一开始成功率挺低的，大概是20次中有1次能够成功突破。
随后就是第二部分，出来了一个意义不明的游戏。。
一来就是让你输入数字。
习惯了ACM比赛题，所以遇到这种只有输入和输出，没有题目描述的题，而且每次尝试还有95%的高概率不能突破第一部分，我觉得很是蛋疼。。
然而在经过了大量的尝试过后，加上主办方给出的提示，我终于搞懂了此题的意思。
转换成ACM的题目风格大概是这样的：
字符串s 长度小于20，只包含'R' 'L' 和1个空格
如：RLRLR LLRLRL
求最少多少次操作使得R全部在空格左边，L全部在空格右边
如：RRRRR LLLLL
可以执行两种操作
1. 把空格左/右移一位
RLRLRL LRLRLL 左移一位==> RLRLRLL RLRLL
2. 把空格与 空格下标+2/空格下标-2 位置的字母交换
RLRLRL LRLRLL 与+2位的交换==> RLRLRLLR LRLL
好嘛，搞懂题目之后，算法自然我最擅长的。
分析一下，字符串长度小于20，于是字符串的种类很显然有$2^{20}*20$种，大概是$10^7$左右。
如果使用bfs+记忆化判重，算法时间复杂度是O($10^7$)，不会超时（…至少在acm中不会）。
于是我开始用python写。
另外感到诧异的是，python写出来后，运行效率特别低。表现为一组数据跑很久都跑不出来（10秒以上），而只要在几秒之内没有输入，连接就会断开，于是只能重新来过。
纠结了非常久，最后甚至想到什么多线程，什么分布式…
后来，我才想到可能是python的执行效率导致得这个原因。于是我换成了ACM比赛中常用的java，又敲了一份。果然，这次运行则非常顺利，每组数据都跑得非常快！
最后，调整了一下链接的输入输出，用java执行爆破，然后再用java来执行bfs记忆化，顺利拿到Flag。
（由于赛后主办方关闭了链接，所以此题没有截图）