首页
社区
课程
招聘
[原创] 第十一题 虫洞末世 算法题把机器都跑废了
2022-6-3 19:46 16490

[原创] 第十一题 虫洞末世 算法题把机器都跑废了

xym 活跃值
4
2022-6-3 19:46
16490

面对纯算法题,心里还是比较虚的。但好在这道题一眼看去没有涉及什么高深的数学知识。虽然看着半懂不懂的,却也能硬着头皮看下去。
程序很简洁,主函数获取输入,createkey利用输入的16个字符生成key,cheakkey对key进行校验。本来秉持着每一步都尽量分析清楚的心理,对每一行代码都进行了功能判断,前面基本都是输入到keywords1的等价变换,最后卡在createkey里生成Q的一个循环里。程序运行速度并不快,也是这里造成的。无奈跳过这段代码,来到cheakkey函数,先不管奇怪的doom子函数,这里居然直接对key[0]和key[-1]做了判断,也就是说key[0]和key[-1]的值是已知的。结合createkey里key是Q轮流除以keywords1生成的,可以得到第一个等式

1
Q = key[0] * keywords1[0] = key[-1] * keywords1[-1]

对于每个keywords1最多不到16384情况,而且keywords1是稀疏的,满足等式的情况应该不多,编写代码应该可以遍历的起。在不考虑多解的情况下,把取值范围限制到[32,223),大概不到10分钟,跑出了第一组解[108,114],[97,115]。即Serial以“lr”开头,以“as”结尾。
再分析doom函数,不难发现mode1就是mode3,当mode1比mode2和mode4都小时,mode1为remembermode的公约数。经分析remembermode的最大公约数为32,有点偏小。抱着侥幸心理利用int((key[1]/key[6])10*16) == 32跑了一遍也确实没有结果。

1
2
>>> math.gcd(30413574359725275612744778689984,49715060849837149374468109364128)
32

于是换个思路,既然mode1不是最小的,那么mode2和mode4里至少有一个比mode1小,那比mode1小的值必然是remembermode里面的因子。于是分别利用

1
2
remembermode[0] % int((key[3]/key[5])*10**16) == 0
remembermode[1] % int((key[2]/key[4])*10**16) == 0

作为条件进行遍历,各得一个结果,并且利用得到的mode2和mode4都可以推出
mode1的值为14109109473780244。最后利用

1
int(( (Q/key1) / (Q/key6)) * 10 ** 16) == 14109109473780244

作为判断条件,遍历出最后4位的值。最终得到Serial为lrY1314cXy2920as。
多解分析:
在lists的第一步处理中p<=57和p>=48时取值范围为223-232,否则根据p为可见字符时推出取值范围为100-147,158-227。其中出现的223-227的重合表明凡是出现在答案中的数字,只要小于等于5就可以找到另一个可见字符进行替换。


[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》,视频+靶场+题目!助力进入CTF世界

收藏
点赞3
打赏
分享
最新回复 (2)
雪    币: 144
活跃值: (1021)
能力值: ( LV3,RANK:33 )
在线值:
发帖
回帖
粉丝
whereslow 2022-6-8 19:58
2
0
早知道不给那么多条件了。直接给绕过了
游客
登录 | 注册 方可回帖
返回